Adaptive checkpointing with reliable storage in cloud environment

Abstract

Cloud computing has recently gained popularity as a resource platform for on-demand, high availability and high scalability access to resources, while offering dynamic flexible infrastructures and QoS (Quality of Services) guaranteed services. In this environment, reliability is very important to ensure the effectiveness of the system and meet the desired SLA (System Level Agreement). Our work proposed in this paper uses the checkpointing of tasks to ensure the reliability and the replication of checkpointing files to ensure the accessibility. To ensure the reliability of services, we used a fault tolerance strategy based on adaptive checkpointing of two levels. This strategy takes into account the complexity and characteristics of cloud computing and it minimizes the overhead. To ensure the accessibility and the availability of checkpointing storage, we used a dynamic passive replication based on an availability degree specified by SLA criteria to decide the placement and the number of replicas.

Keywords

Checkpointing cloud reliability fault tolerance availability replication coordination consistency storage

1. Introduction

Cloud computing has emerged as the next generation of computing. It offers a high level of resource virtualization as: computing devices, storages, communication infrastructures. Cloud computing allows users to focus on their own application rather than other related issues (installations, configuration, management…). Cloud computing delivers hardware infrastructures and software application as services, and the user can consume theses services based on SLA (System Level Agreement) which defines theirs QoS parameters based on pay-as-you-go concept.

Since reliability is a critical parameter to ensure the service-ability of the cloud, it is necessary to implement a fault tolerance tool. Fault-tolerance is the property that enables a system to continue operating properly in the event of the failure of some of its components.

Fault tolerance can be classified on two categories: proactive and reactive.

Proactive fault tolerance: It predicts the fault and avoids recovery from fault, errors and failure and proactively replace the suspected component, means detect the problem before it actually come. It is a concept that prevents compute node failures from impacting running parallel applications by preemptively migrating parts of an application (task, process, or virtual machine) away from nodes that are about to fail.

Reactive fault tolerance: It reduces the effort of failures, when the failure occurs. This technique makes system more robust. In other words, we can say that it an On-demand fault tolerance.

To achieve a reactive fault tolerance, several techniques are proposed such as: replication, resubmission and checkpointing.

Replication: Means copying. Several replicas of tasks are created and they are run on different resources, for effective execution and for getting the desired result. Hadoop, HA-Proxy, Amazon EC2 like tools are there on which replication can be implemented. Also, there are mainly three different types of replication schemes such as Active Replication, Semi-Active Replication and Passive Replication.

Resubmission: Many times it happens that due to high network traffic or due to heavy work load, a task may fail, whenever such failed task is detected, at runtime the task is resubmitted either to the same or different working resource for execution. For these, certain algorithms are designed, which assigns task to resources on the basis of certain properties.

Checkpointing [27]: It is a proficient task level fault tolerance technique for large applications. In this method, check pointing is done in system. When a task fails, instead of initiating from beginning it is restarted from the recently checked pointed state. Checkpointing is carried out periodically i.e., checkpoints are kept and process is executed from the recent check point, once system governs the fault.

Each of these strategies has its own advantages and limits and views the characteristics and the complexity of cloud computing, the choice of the fault tolerance technique becomes more difficult. The good strategy ensures the reliability and availability with minimum overhead and without affecting the SLA. Reliability is concerned with willingness for correct service and availability is concern with continuity of correct service.

In this paper, we propose a fault tolerance strategy based on the adaptive multi-level checkpointing. The proposed checkpointing uses an adaptive time-based coordinated checkpointing at the VMs (Virtual machines) of the same server and min-process coordinated checkpointing at the server level. The adaptive time based checkpointing reduces the overhead of classical time based checkpointing by minimizing the piggybacked and stored message. The minimum coordinated checkpointing is already used in several works. What is new in our strategy is that we used this checkpointing in the server level rather than the CIC (Communication induced checkpointing) as it is proposed in many works. In addition, we made our strategy fault tolerant by storing the dependency matrix in the broker and the updates are done only if there is an external communication. Generally in classical strategies this matrix is created in each checkpointing process which increases the overhead. More details can be found in the next sections.

To ensure the availability of checkpointing files even if a storage server fails, we improve the storage process using a dynamic and passive replication. The new in this strategy is using it for the checkpointing files and it is based on certain degree of availability specified by the SLA rules. The details are also in Section 4.

The rest of this paper is organized as follows. Section 2 briefly describes related work on different reactive fault tolerance strategies existing in literature. In Section 3, we provide an overview of our cloud model and introduce the fault-tolerance mechanism. In Section 4, we detail our fault tolerance technique based on the multi-level checkpointing for the reliability and the dynamic replication for the storage availability. We present experimental results in Section 5 and a comparative study in Section 6. Finally, we provide concluding remarks and perspectives for future work in Section 7.

2. Literature review

In order to tolerate faults, the strategies based on checkpointing save the executed portion of processes on stable storage. Hence, the executed portion can be retrieved in case of failure and further computation can be carried out [30]. The checkpointing protocols can be classified in three categories according to the synchronization among the application nodes:

In Independent checkpointing (uncoordinated) [1]: the checkpoints at each process are taken independently without any synchronization among the processes. Because of absence of synchronization, there is no guarantee that a set of local checkpoints taken will be a consistent set of checkpoints. It may require cascaded rollbacks that may lead to the initial state due to domino-effect [1]. The domino effect appears when a subset of processes, which have to be resumed after a failure, rollback unboundedly while determining a set of mutually consistent checkpoints. The independent checkpointing store all the checkpoints file during the job life. To overcome the problems of the domino effect in this protocol, the authors in [2, 3] propose to use an optimistic sender based messages logging. The time based coordinated checkpointing is an independent checkpointing where the coordination in done only in the timer level [28]. In this type of checkpointing the timers are synchronized to ensure the checkpointing approximately at the same time.

The coordinated or synchronous checkpointing forces the processes to synchronize to take checkpoints in such a manner that the resulting global state is consistent. The main advantage is that it sores only one permanent checkpoint in the stable memory and it is domino-effect free. The Chandy-Lamport [4] algorithm is the earliest coordinated checkpointing algorithm. This technique requires that at least one process sends a marker to notify the other ones to take a snapshot of their local states and then form a global checkpoint. To reduce the overhead caused by the synchronization, it was necessary to reduce the number of nodes involved in the checkpointing process. The paper [29] minimizes the overhead by synchronizing between the communicating nodes during the previous checkpointing interval. In [5, 6]; the authors propose a coordinated checkpointing where only the nodes depending on a selected initiator are forced to created theirs checkpoints. Time based coordinated checkpointing proposed in [8, 9] supposes that the logical timers of nodes are approximately synchronized which allows to creates a consistent checkpoints with a simple management of messages during a certain periods.

The last protocol is communication induced checkpointing (CIC). In this protocol, the processes take two kinds of checkpoints, local and forced [7]. Local checkpoints can be taken independently, while forced checkpoints are taken to guarantee the eventual progress of the recovery line. However the messages are piggybacked and useless checkpoints can be created.

Each protocol has advantages and limits, which makes the combination among two or three protocols necessary to adapt to the system levels and complexities [10].

All the cited works assume the ability to store the checkpoints images (files) in a reliable media which is not subject to failures (stable storage servers). But these dedicated servers may become a bottleneck when the system size increases. To overcome this problem, the authors in [11] introduced the concept of diskless checkpointing. In checkpointing stable storage media is replaced by memory for checkpoint storage. In checkpoint mirroring (MIR) [11], the checkpoint mirroring technique is used in which each processor saves a copy of its checkpoint to another processor’s local disk. In the case of processor failure the copy of that checkpoint will be available for a spare processor to continue the execution of that process. The paper [12] uses the same concept except that all the computational processors and the checkpoint processor are organized in chain. Each processor receives the data segment from its predecessor, calculates the checksum and sends it to the next processor in the chain. The process continues until the segment reaches the checkpoint server which is at the end of the chain. Diskless checkpointing is scalable but it is costly in terms of mapping and consistency management of checkpointing files. One way to provide checkpoint storage reliability with some degree of scalability is replication. In replication, multiple copies of a checkpoint are stored on different storage servers. Thus, data can be recovered even when part of the system is unavailable [13, 14].

3. Adaptive checkpointing protocol and storage

View the characteristics of each level, fault management must consider and adapt to the each level complexity. For this reason, our checkpointing strategy MLCp (Multi-Level Checkpointing) uses two different cooperative strategies in each level to minimize overhead and meet SLA. And since storage servers are not 100% reliable, it is necessary to ensure the availability of files in case of rollback checkpoints. In this case we add a dynamic replication service. In this section we explain in details our strategy of fault tolerance that hybrids between replication and checkpointing.

3.1 System overview

The infrastructure-level services (IaaS) in cloud organizations can be provided by a group of datacenters. Each datacenter entity manages a number of storage services and host entities. The hosts (servers) are assigned to one or more VMs (Virtual Machines) running on them. The virtualization offers a complete environment in which an operating system and many processes, probably belonging to various clients, may reside mutually. Using the VMs, a single-host hardware platform may be compatible with multiple, isolated guest operating system environments concurrently [15]. The use of Virtualization provided by hypervisors otherwise known as Virtual Machine Monitors (VMM), forms an innovative virtualization level that separates the service workload from the resource management.

According to the Cloud architecture, there are three types of failure in a cloud platform: hardware failure, (storage server/host), VM failure and application failure (all VMs executing the applications fail). The broker is an intelligent agent that takes care of many functions that distributed applications require such as: SLA negotiation, application management (discovering the right resources meeting the SLA, scheduling jobs in order to meet deadlines), and handling failure that may occur during execution (all the three types) using fault tolerance. The fault tolerance used by the broker is based on the checkpointing. And to ensure the availability of checkpointing failures, the broker uses also the replicate these files among several storage services.

The user application consists of a set of tasks distributed among different VMs of different hosts (according to the allocation strategies) that communicate by exchanging messages, which creates dependencies between VMs and hosts where these tasks are running. In this case, two levels of communication of different characteristic and complexity are generated:

VM level: This level comprises VMs of the same server involved in application performance. This level is characterized by a high level of communication and very small transfer times message (in some works it is considered as null).

Server level: This level includes the system servers that participate in the execution of application. The communication in this level is rare and costly.

3.2 Multi-level checkpointing (MLCp)

Each server runs independently its checkpointing according to its own checkpointing interval specified by the SLA rules. The checkpointing of a server is the set of local checkpoints of all its VMs. Since there are dependencies between servers, it is possible to force one or multiple servers to create their checkpoints together to ensure a consistent state.

3.2.1 VM level checkpointing

According to [9, 10], the transfer time of messages between VMs of the same server is negligible compared to the time of transfer of messages between servers. In addition, the VMs clocks are synchronized or approximately synchronized in the worst cases. These characteristics make time based coordinated checkpointing the most suitable for this level.

In the based coordinated checkpointing: All the processes are approximately synchronized and have a deviation from real time in their local clock timers. The local clock drift rate between the processes being assumed as $\rho$ . The timer will terminate at most $(2\rho T/(1-\rho^{2})\approx 2\rho T)$ seconds apart. Here $T$ is the initial timer value. Normally drift rate $\rho$ attains values between 10 ${}^{-5}$ sec to 10 ${}^{-8}$ sec. We assume that the message transmission time in the same server can be known and included in the interval [ $t_{\min}$ , $t_{\max}$ ] which $t_{\min}$ is the minimum transmission time of message, $t_{\max}$ is the maximum transmission time of a message in the server. In this case, it is possible to detect the potential transit and orphan messages depending on the sending time of a message compared to the checkpointing time of the sender. Messages sent during the effective deviation of consistency $\alpha$ (see Eq. (1)) after the checkpointing are potential orphan messages, and those sent during the effective deviation of recoverability $\beta$ (see Eq. (2)) before the checkpointing are potential in-transit messages.

$\displaystyle\alpha=\textit{MD}-t_{\min}$ (1) $\displaystyle\beta=\textit{MD}+t_{\max}$ (2)

where MD is the maximum deviation and it is calculated as below:

$\textit{MD}=D+2\rho nT$ (3)

where $D$ : the initial deviation of checkpointing intervals, n: number of checkpoints intervals.

The orphan messages can be eliminated by blocking the communication during $\alpha$ or by using communication induced approach. In this case, the checkpointing will cause more overhead. In our approach, we reduce this overhead by using the minimum of piggybacked messages. During the period $\alpha$ , the sender will piggyback only the first message sent to a new destination. The information piggybacked is the $c s n$ (checkpointing sequence number). The Integer $csn_{i}$ keeps track of sequence number of the current checkpoint of $\textit{VM}_{i}$ . It is initialized to 0 and increased by one each time a new checkpoint is taken. Since all the VMs of the server use the same checkpointing interval, their $c s n$ must be the same.

So when a $\textit{VM}_{i}$ receives a message with $c s n$ higher than its local csn, it knows that the sender has created its checkpoints. In this case, the receiver ( $\textit{VM}_{i}$ ) creates its checkpoint and resynchronizes its timer according to the sender timer.

Blocking the communication during $\beta$ before the checkpointing may resolve the problem of in-transit messages but it adds an extra overhead. Our proposition is storing the sent messages in the checkpointing file. In case of rollback and if the receiver asks to resend a message, the sender will be able to do it using its stored image. Since the VMs use the same checkpointing interval, only the message sent during the previous checkpointing interval will be stored.

The checkpointing strategy at this level is the following: the checkpointing of a server is the collect of all checkpoints of its VMs. As the server interval checkpointing expires, each VM creates its local checkpoint independently of other VMs. Among the period $\alpha$ after the checkpointing, the VM will piggyback the first message sent to a new destination to force the destination to create its local checkpoint and resynchronize its timer before processing the received message.

Figure 1.

Checkpointing at VM level.

The local checkpointing file contains all the information necessary for correct VM recovery, it also contains the list of potential in-transit messages. These checkpointing files will be sent to a VM initiator in the server and the VMs continue their performances immediately. The initiator VM is responsible for collecting checkpoints of VMs and ensuring the checkpointing atomicity. It is also responsible to ensure the checkpointing storage. Figure 1 illustrates a communication scenario inside the server and between three servers ( $a, b$ and $c$ ). The message m4 is a potential orphan message because it is sent during the period $\alpha$ after the last checkpointing.

3.2.2 Server level checkpointing

If an external communication is detected during the checkpointing of a server, the server level checkpointing is triggered. The majority of existing studies use CIC (Communication Induced Checkpointing) in this level, but this strategy requires more storage checkpointing files and the recovery is expensive. In our work, we used minimum – Coordinated checkpointing process where only the dependent servers will be forced to create their checkpoints. A server can monitor its direct dependencies but it cannot know its transitive dependencies. In Fig. 2, the server $a$ depends on the server $b$ . The server $c$ depends also on the server $b$ , so the server $c$ depends also on the server $a$ . To solve the problem of indirect dependencies we used a dependency matrix $\textit{Dep}_{\textit{Matrix}}$ . If $\textit{Dep}_{\textit{Matrix}}[i,j]=1$ so the server $j$ depends on $i$ . The broker uses the $\textit{Dep}_{\textit{Matrix}}$ to track dependencies servers. This matrix is updated each checkpointing or external communication between servers.

After receiving a request from a server, the broker consults $\textit{Dep}_{\textit{Matrix}}$ matrix to detect dependent servers and then sends these servers a checkpointing a checkpointing request. After receiving this request, the server triggers the checkpointing by forcing its VMs to create their local checkpoints.

Figure 2.

Checkpointing at server level.

3.3 Checkpointing storage

In most checkpointing works, it is assumed that the checkpoint files are stored in 100% reliable and stable memory, which is difficult to guarantee in the real world. In this case, the checkpointing file can be unavailable or lost and the system reliability will be not assured. The diskless checkpointing storage ensures reliability storage but it is expensive in terms of mapping and consistency management of checkpoints files.

In our adaptive storage, we adopt the replication strategy to ensure the storage reliability. The replication is widely used in the literature for different raisons such as the performances or the reliability. The replication based on the reliability focuses on the accessibility [21]. However the replication based on the QoS uses the response time, the consistency management and the cost to decide the number and the placement of the replicas in the system. The replication can be used for files [21], tasks [22], data bases or even objects.

Since the checkpointing file is also a file and its existence is very important to the recovery process, we decide to replicate it to ensure both of reliability and QoS. Replicating the checkpointing file is not new in the literature but our work deals with the majority of checkpointing storage and replication problems such as: when, what, how much and where replicating without increasing the checkpointing overhead. In the next paragraphs we will explain in details our storage strategy.

In our approach, we assume that each datacenter ${\textit{DC}}_{i}$ has a set of storage servers $\{S_{1},S_{2},\ldots,S_{n}\}$ . Each storage server $S_{i}$ has an availability probability $P(S_{i})$ . A checkpointing file has the same availability probability of the server where it is stored. Therefore creating $k$ replicas of a file $F$ provides a reliability degree of $R_{F}$ which can be calculated as below.

$R_{F}=1-\prod\limits_{i=1}^{k}(1-P(S_{i}))$ (4)

For example, a data center contains only storage servers with $P(D_{i})=$ 50%. To ensure the desired reliability cited in SLA contract $R_{D}=$ 93%, it is necessary to create at least four replicas. That is to say it must satisfy the condition as below:

$R_{F}\geqslant R_{D}$ (5)

So as long as the constraint of Eq. (5) is not satisfied, the replication manager in the broker continues creating replicas.

To designate the location of replicas in the group of available storage servers at the datacenter, we used a QoS criteria to select the $k$ storage servers. The quality $Q$ of the server $S_{i}$ is calculated as below:

$Q(S_{i})=\sum\limits_{i=1}^{n}{{(w}_{i}\times p_{i})}$ (6)

where $w_{i}$ : is the weight associated with the parameter $p_{i}$ . Weights must satisfy the following condition:

$\sum\limits_{i=1}^{n}{w_{i}=1}$ (7)

$p_{i}$ : is the standardized parameter that is taken into consideration. Without loss of generality, we can map a parameter value to the interval [0, 1] using the function:

$p_{i}=(p_{\textit{Real}}-p_{\min})/(p_{\max}-p_{\min})$ (8)

where $p_{\textit{Real}}$ , $p_{\max}$ and $p_{\min}$ are the real, the maximum and the minimum values of parameter $p$ respectively [16]. In this case, the $Q(S_{i})$ will be automatically normalized in the interval [0 $,$ 1].

In our work, we have considered three main parameters: the server reliability $P(S_{i})$ , the storage cost $C(S_{i})$ in the server $S_{i}$ and the load $L(S_{i})$ (see Eq. (9)). The load of the server $S_{i}$ represents the number of access during a unit time (one hour, for example):

$L(S_{j})=\frac{\sum\limits_{i=1}^{m}{\textit{AF}(F_{i})}}{T}$ (9)

where $F_{i}$ : file $i$ stored in the storage server $S_{j}$ , $m$ : number of files stored in the storage server $S_{j}$ , $AF(F_{i})$ : the access frequency of the file $F_{i}$ , $T$ : a period of time.

We also assumed that these three parameters have the same weight, that is to say:

$w_{1}=w_{2}=w_{3}=\frac{1}{3}$

The broker module will choose the server which has the highest rating value, as the primary server. The primary server is responsible for ensuring the atomicity of storage checkpoints files and replicating the files on other shadow servers (Creating replicas).

To select the shadow servers; the broker remains using formulae. 6 with one difference: it must also consider the distance between the primary server and its replica, in this case the selection criteria is as below:

$\acute{Q}(S_{i})=\frac{Q(S_{i})}{\textit{BW}(S_{i},S_{\textit{prim}})}$ (10)

where $\textit{BW}(S_{i},S_{\textit{prim}})$ : is the bandwidth between the server $S_{i}$ and the primary server $S_{\textit{prim}}$ . So the $(k-1)$ placements of replicas are selected using Eq. (10).

To reduce even more the checkpointing storage overhead, our approach uses a hierarchical storage; in this case, a powerful VM is selected as a mediator (generally it is the initiator). The role of the mediator is ensuring the correctness and the atomicity of checkpointing storage of its VMs. A server can use one or more mediators depending on the number of VMs involved in the application. The storage of the checkpointing file in the primary server is done by the mediator but the replication of this file to other shadow servers is done asynchronously to reduce the storage time.

In Fig. 3, the mediators are VM4 for the server $a$ and VM5 for the server $b$ . When the checkpointing interval expires, these mediators (may be one or both mediators depending on their dependencies) send their checkpointing files to the primary server and then they resume immediately the work. The primary storage server replicates the file in the shadow storage servers (three servers in this example). The broker ensures the existence of the replicas necessary to meet the desired file availability.

Table 1

Comparison of checkpointng techniques

Approach	Multi-level	Type	Transit	Synch	Orphan	FT	Blocking	Storage	Time
[1]	No	Uncord	No	No	Yes	No	No	No	No
[2]	No	Uncord	Yes	No	Yes	No	No	No	No
[3]	No	Uncord	Yes	No	Yes	No	No	No	No
[4]	No	Coord	No	All	Yes	No	Yes	No	No
[5]	No	Coord	No	Min	Yes	No	Yes	No	No
[6]	No	Coord	No	Min	Yes	No	No	No	No
[7]	No	Uncord/Coord	Yes	All	No	No	No	No	No
[8]	No	Uncord	Yes	No	Yes	No	No	No	Yes
[9]	Yes	Uncord/Coord	Yes	All	Yes	No	No	No	One level
[17]	Yes	Uncord/CIC	Yes	No	Yes	Yes	No	No	No
[18]	No	Uncord	No	No	Yes	No	Yes	No	Yes
[28]	No	Uncord	Yes	Yes	Yes	Yes	No	No	Yes
[29]	No	Coord	Yes	Communicated nodes	Yes	Yes	No	No	No
Our approach (MLCp)	Yes	Uncord/Coord	Yes	Min	Yes	Yes	No	Yes	One level

Figure 3.

Hierarchical checkpointing storage.

4. Simulation results

To evaluate our approach, we used two parts of experimentations. The first part focuses of the checkpointing technique, so we compared our MLCp approach with the strategy proposed in [9] because it is the most similar work compared to ours (see Table 1).

In the second part, we compared our storage strategy that we call adaptive replication ARS (adaptive replication strategy) with:

Classical Checkpointing Storage (CCS): In this case, a single storage server responsible for storing the checkpoint file.

With k replication storage kRS: In this case, the checkpoint files k will be stored in storage servers randomly selected.

4.1 Checkpointing evaluation

We used two parameters to evaluate our MLCp approach: the checkpointing overhead and the SLA violation.

4.1.1 Checkpointing overhead

Checkpointing overhead is the most important parameter to measure the effectiveness of checkpointing [7]. The overhead can be measured in several ways depending on the simulation requirements. In our case, the overhead Overh is calculated as below:

$\textit{Overh}=\frac{{\textit{RT}}_{cp}}{{\textit{RT}}_{\bar{\textit{CP}}}}$ (11)

where ${\textit{RT}}_{cp}$ : Application runtime using the checkpointing, ${\textit{RT}}_{\bar{cp}}$ : Application runtime without using the checkpointing.

Figure 4.

Impact of the number of checkpoints on the overhead with 70% of internal checkpointing.

In this experiment, we used 40 VMs in seven servers, we used a Poisson Distribution to present the failure behavior with a failure rate $\lambda=3$ . In order to evaluate each checkpointing level without eliminating the other level, we used the same scenario in two cases:

In the first case, the internal communication rate (communication inter-server) is 70% of the total communications of the system. The results presented in Fig. 4 show a small overhead rate in all approaches because the checkpointing will be the majority of the time inside the servers. In addition of that; the time-based checkpointing does not require many control or synchronization messages (except for the synchronization of the time that can be made periodically or during the communication). Our MLCp approach does not cause many overhead because it does not piggyback messages even during the $\alpha$ period, in contrary to the approach in [9] that piggybacks all the messages sent during $\alpha$ . MLCp stores only the messages sent during $\beta$ before the checkpointing as potential in- transit messages which reduces the size of the checkpointing file and reduces the checkpointing time.

In the second case, the external communication rate (communication inter-server) is 70% of the total communications of the system. The results presented in Fig. 5 show that the overhead rate is high for both approaches because of the synchronization needed for creating the checkpoints between the servers which also indicates an intra-server checkpointing. But our approach has minimized the overhead because it ensures the minimum synchronization between the servers by the use of the dependency idea. In addition our strategy also minimizes the intra-server overhead (the first case).

Figure 5.

Impact of the number of checkpoints on the overhead with 70% of external checkpointing.

Figure 6.

Impact of $\lambda$ on the SLA violation.

4.1.2 SLA violation

The SLA can be determined in terms of several constraints such as the minimum throughput or maximum response time provided by the deployed system. Since these characteristics may vary depending on the applications, it is necessary to define a generic metric that can be used in our simulations to estimate the level of SLA that is delivered by the approach.

For this purposes, we define the overall level of SLA violation caused by the system as the sum of overheads in terms of cost and Energy as below:

$V=\alpha 1(\textit{OM})+\beta 1(\textit{OC})$ (12)

where $\alpha 1,\beta 1$ weight factors and $\alpha 1+\beta 1=1$ , OC: overhead in term of cost, OE: overhead in term of energy. OC and OE are calculated in the same way as Overh of Eq. (11).

To evaluate our MLCp approach in term of SLA violation we used the same scenario of the previous experiment except that we fixed the internal communication at 80% (which is the general case in the cloud) but the failure rate $\lambda$ will varies between 2 and 14. The results are illustrated in Fig. 6.

According to the results presented in Fig. 6, the SLA violation increases if the failure rate increases due to:

The checkpointing process that requires time which increases the time of resource occupancy and consequently increases the cost and the energy.

The recovery procedure that checks alternative resources to re-execute the task from the last checkpoint stored in the memory and then loads the checkpointing file into this resource (VM).

However, our approach has succeeded in minimizing the SLA violation because the checkpointing procedure consumes less time and the recovery only concerns the VMs depending on the failed VM.

Figure 7.

Impact of the number of checkpoints on the overhead.

4.2 Storage evaluation

This section compares our storage service ARS to other storage strategies and evaluates its performances.

4.2.1 Impact of the number of checkpoints on the overhead

We used the following scenario: Number of VMs $=$ 120, Number of servers $=$ 7, $\lambda=$ 3, internal communication rate $=$ 80%. However the number of checkpoints varies between 10 and 60. We used also storage servers $S_{i}$ with $P(S_{i})=$ 80% and a desired reliability $R_{F}=$ 99.9%. The checkpointing number varies between 10 to 60.

According to the results presented in Fig. 7, the number of checkpoints automatically increases the overhead in all the checkpointing storage approaches. The overhead caused by the storage with kRS replication was high compared to conventional storage in CCS. In kRS, the mediators will be blocked to ensure $k$ replication of checkpoint files in storage servers. However, in CCS a single file will be sent to a storage server. Our replication approach ARS minimizes the overhead because the nodes are responsible for storing only one checkpointing file, the rest ( $k\neq$ 1) files are created Asynchronously by the primary server regardless of the number of replicas needed to ensure the desired availability. In addition, the primary server is selected according to its QoS.

4.2.2 Impact of the size of checkpointing file on the overhead

We used the same scenario of the previous experiment with Number of Checkpoints equal to 30 but we increase the size of checkpointing file, we studied the impact of the size of checkpointing file on the overhead. Increasing the size of checkpointing files increases the overhead since the storage time increases (see Fig. 8). Our strategy ARS ensures minimum overhead due to hierarchical storage (Primary server node and shadows servers). kSR strategy gives bad results because of the number of checkpointing files that must be replicated and stored in different storage services Asynchronously.

4.2.3 Impact of the number of failed storage severs on data availability

Figure 8.

Impact of checkpointing file size on the overhead.

Figure 9.

Impact of $\delta$ on availability.

The unavailability of checkpoints file indicates the impossibility of recovery in case of failure detection. In this experiment we used the parameter $\delta$ that represents the number of failed storage servers. We increased $\delta$ and recorded the availability of the checkpointing files. The number of VMs $=$ 140, Number of servers $=$ 7, $\lambda=$ 2, internal communication rate $=$ 80%, the number of checkpoints was 50 and the desired reliability $R_{F}=$ 99.0%. The reliability of storage servers $S_{i}$ is $P(S_{i})=$ 75%. The results are presented in Fig. 9. The CCS strategy does not ensure the availability of checkpoints in case the storage server failure since it contains the only copy of checkpoints. Our ARS strategy provides better results compared to kRS because the storage servers are already selected according to their degree of reliability to increase the availability of files without increasing their number.

5. Comparative study

Table 1 presents a comparison between different checkpointing strategies cited in the paper including our checkpointing strategy MLCp. The column “Synch” indicates the degree of synchronization requested to ensure the consistency. “FT” column indicates if the strategy is fault tolerant or not. In “Storage” column we can see if the strategy takes in consideration the process of checkpointing storage or not. The column “Transit” indicates the consideration or not of the in-transit messages.

To position our approach of checkpointing storage in relation to other existing works, we used Table 2. “Replicating Column” indicates the replication granularity. “FT Column” indicates if the strategy is fault tolerant or not. “Rep type Column” indicates if the replication is active (Active), Passive (P). “Recov Column” concerns only the checkpointing file and it shows if the recovery process in considered in the replication process. In “Number of Rep”, “n” indicates that the number of replicas is fixed however $\gamma$ indicates that this number is calculated.

Table 2
Comparison of replication techniques

Approach	Replicating	Number rep	Placement rep	FT	Recov	Rep method	Rep type	Cost
[11]	CP	1	Random	No	No	Static	A	No
[12]	CP	1	Predecessor	No	Yes	Static	A	No
[13]	CP	n	/	No	No	Static	A	No
[14]	CP	n	/	No	No	Static	A	No
[20]	CP	n	Random	Yes	Yes	Static	P	No
[21]	Files	n	Availability	Yes	/	Dynamic	A	No
[25]	Files	n	Availability & popularity	Yes	/	Dynamic	A	No
[26]	Files	n	Availability	No	/	Dynamic	A	No
[22]	Tasks	n	Idle slots	No	/	Static	A	Yes
[23]	Tasks	3F $+$ 1 (F: number	Random	No	/	Static	A	Yes
		of failures)
[24]	Tasks	n	Lower energy consummation	No	/	Static	P	No
Our approach	CP	$\gamma$	Reliability $+$ availability	Yes	Yes	Dynamic	P	Yes

6. Conclusion

Checkpointing is a popular strategy of fault tolerance in cloud environment. The weak point of the checkpointing is the overhead and the availability of checkpointing files. In this paper we proposed a checkpointing strategy that minimizes the overhead by minimizing the degree of coordination and the management of complex levels.

To ensure the availability of checkpointing files, we also used another fault tolerance technology based on replication. The storage manager in our approach provides a degree of reliability for each file checkpointing with the minimum cost of storage and updating. The results prove the effectiveness of our approach in terms of availability and minimizing the overhead. In future work, we expect to integrate cognitive agents for intelligent management of fault tolerance at checkpointing level and storage level.

Footnotes

Authors’ Bios

Bakhta Meroufel graduated from the Department of Computer Science in the Faculty of Sciences at the University of Oran1 in Algeria, where she received her PhD degree in Computer Science in 2016. Her research interests are: distributed system, grid computing, cloud computing, fault tolerance, replication strategies, mobile environment and multi-agents systems.

Ghalem Belalem Graduated from Department of computer science, Faculty of exact and applied sciences, University of Oran1 Ahmed Ben Bella, Algeria, where he received PhD degree in computer science in 2007. His current research interests are distributed system; grid computing, cloud computing, replication, consistency, fault tolerance, resource management, economic models, energy consumption, Big data, IoT, mobile environment, images processing, Supply chain optimization, Decision support systems, High Performance Computing.

References

Feller

Spahn

J.-M.

Schoettner

and Morin

, Independent checkpointing in a heterogeneous grid environment, Future Generation Comp Syst 28(1) (2012), 163–170.

Mostefaoui

and Raynal

, Efficient message logging for uncoordinated checkpointing protocols, Proceedings of the Second European Dependable Computing, Springer-Verlag London, UK, (October 1996), 353–364.

Elnozahy

E.N.

and Zwaenepoel

, Manetho: Transparent rollback-recovery with low overhead, limited rollback and fast output commit, IEEE Transactions on Computers 41(5) (1992), 526–531.

Chandy

K.M.

and Lamport

, Distributed snapshots: Determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS) 3(1) (1985), 63–75.

Prakash

and Singhal

, Low-cost checkpointing and failure recovery in mobile computing systems, IEEE Transactions on Parallel and Distributed Systems 7(10) (1996), 1035–1048.

Tunga

Datta

and Mitra

, A fast and efficient non-blocking coordinated movement-based check pointing approach for distributed systems, International Journal of Computational Engineering Research (IJCER) 2(1) (2012), 136–142.

Manivannan

Jiang

Yang

and Singhal

, A quasi-synchronous checkpointing algorithm that prevents contention for stable storage, Inf Sci 178(15) (2008), 3110–3117.

Suri

P.-K.

and Satiza

, System progress estimation in time based coordinated checkpointing protocols, International Journal of Computer Applications 52(11) (2012), 1–6.

Hui

Zhan

Ling

W.-B.

Cheng

Z.-D.

and Zong

Y.-X.

, A two-level application transparent checkpointing scheme in cloud computing environment, International Journal of Database Theory and Application 6(2) (2013), 61–71.

10.

Ndiaye

N.-M.

Sens

and Thiare

, Performance comparison of hierarchical checkpoint protocols grid computing, International Journal of Interactive Multimedia and Artificial Intelligence 1(5) (2012), 46–53.

11.

Plank

J.S.

, Improving the performance of coordinated checkpointers on networks of workstations using RAID techniques, in: Proceedings of the 15th Symposium on Reliable Distributed Systems (SRDS’96), Nigara-on-the-Lake, Ontario, Canada, Canada, (October 1996), 76–85.

12.

Chen

and Dongarra

, A scalable checkpoint encoding algorithm for diskless checkpointing, in: Proceedings of IEEE International Symposium on High Assurance Systems Engineering, Nanjing, China, (Dec 2008), 71–79.

13.

Bouabache

Herault

Fedak

and Cappello

, A distributed and replicated service for checkpoint storage, Proceedings of the CoreGRID Workshop on Programming Models Grid and P2P System Architecture Grid Systems, Tools and Environments, Heraklion, Crete, Greece, (June 2007), 295–306.

14.

Sun

Chang

Miao

and Wang

, Analyzing, modeling and evaluating dynamic adaptive fault tolerance strategies in cloud computing environments, The Journal of Supercomputing 66(1) (2013), 193–228.

15.

Sadiku

M.-N.O.

Musa

S.-M.

and MoMOh

O.-D.

, Cloud computing: Opportunities and challenges, Potentials, IEEE 33(1) (Feb 2014), 34–36.

16.

Amin

Sethi

and Singh

, Review on fault tolerance techniques in cloud computing, International Journal of Computer Applications 116(18) 2015, 11–17.

17.

Singh

and Chhabra

, Evaluating overheads of integrated multilevel checkpointing algorithms in cloud computing environment, International Journal of Computer Network and Information Security 4(5) (2012), 29–39.

18.

Neogy

Sinha

and Das

P.K.

, Checkpointing with synchronized clocks in distributed systems, International Journal of UbiComp 1(2) (2010), 64–91.

19.

Tripathy

and Tripathy

C.R.

, A new coordinated checkpointing and rollback recovery scheme for distributed shared memory clusters, International Journal of Distributed and Parallel Systems (IJDPS) 2(1) (2011), 49–58.

20.

Sadi

and Yagoubi

, Improved fault tolerance through a multi-zone checkpointing approach, in: Proceedings of de The 3rd Edition of the Student Days at the JEESI, Algeria, (Mai 2014), 61–67.

21.

Chen

C.-T.

Hsu

C.-C.

J.-J.

and Liu

, GFS: A distributed file system with multi-source data access and replication for grid computing, Grid and Pervasive Computing, Geneva, Switzerland, (May 2009), 119–130.

22.

Calheiros

R.-N.

and Buyya

, Meeting deadlines of scientific workflows in public clouds with tasks replication, IEEE Transactions on Parallel and Distributed Systems (TPDS) 25(7) (2014), 1787–1796.

23.

Zhang

Zheng

and Lyu

M.-R.

, BFTCloud: A byzantine fault tolerance framework for voluntary-resource cloud computing, in: Proceedings of the 4th IEEE International Conference on Cloud Computing (CLOUD 2011), Washington DC, USA, (4–9 Jul 2011), 444–451.

24.

Mills

Znati

and Melhem

, Shadow computing: An energy-aware fault tolerant computing model, International Conference on Computing, Networking and Communications (ICNG), Honolulu, HI., (2014), 73–77.

25.

Park

S.M.

Kim

J.-H.

Y.-B.

and Yoon

W.-S.

, Dynamic data grid replication strategy based on internet hierarchy, Lecture Notes in Computer Science (Springer), Berlin, Heidelberg, (2004), 838–846.

26.

Lei

and Vrbsky

, A data replication strategy to increase availability in data grids, In: Grid Computing and Applications, Las Vegas, NV, (2006), 221–227.

27.

Cao

Simonin

Cooperman

and Morin

, Checkpointing as a service in heterogeneous cloud environments, Proceedings of the 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CC-GRID 2015), Shenzhen, Guangdong, China, (2015), 60–71.

28.

Meroufel

and Belalem

, Adaptive time-based coordinated checkpointing for cloud computing workflows, Scalable Computing: Practice and Experience 15(2) (2014), 153–168.

29.

Meroufel

and Belalem

, Service to fault tolerance in cloud computing environment, WSEAS Transactions on Computers 14(1) (2015), 782–791.

30.

Meroufel

and Belalem

, Abstraction checkpointing levels: Problems and solutions, International Journal of Computing 13(3) (2014), 158–169.

Adaptive checkpointing with reliable storage in cloud environment

Abstract

Keywords

1. Introduction

2. Literature review

3. Adaptive checkpointing protocol and storage

3.1 System overview

3.2 Multi-level checkpointing (MLCp)

3.2.1 VM level checkpointing

4.1 Checkpointing evaluation

4.1.1 Checkpointing overhead

4.2.1 Impact of the number of checkpoints on the overhead

4.2.2 Impact of the size of checkpointing file on the overhead

4.2.3 Impact of the number of failed storage severs on data availability

Table 2 Comparison of replication techniques

Footnotes

Authors’ Bios

References

Table 2
Comparison of replication techniques