Houssem-Eddine Chihoub

Shadi Ibrahim

Gabriel Antoniu
email: gabriel.antoniu@inria.frmperez@fi.upm.es

María S Pérez

Consistency in the Cloud: When Money Does Matter!

Keywords: Cloud storage, geographical replications, consistency, Monetary cost, efficiency

With the emergence of cloud computing, many organizations have moved their data to the cloud in order to provide scalable, reliable and highly available services. To meet ever growing user needs, these services mainly rely on geographically-distributed data replication to guarantee good performance and high availability. However, with replication, consistency comes into question.

Service providers in the cloud have the freedom to select the level of consistency according to the access patterns exhibited by the applications. Most optimizations efforts then concentrate on how to provide adequate trade-offs between consistency guarantees and performance. However, as the monetary cost completely relies on the service providers, in this paper we argue that monetary cost should be taken into consideration when evaluating or selecting a consistency level in the cloud. Accordingly, we define a new metric called consistency-cost efficiency. Based on this metric, we present a simple, yet efficient economical consistency model, called Bismar, that adaptively tunes the consistency level at run-time in order to reduce the monetary cost while simultaneously maintaining a low fraction of stale reads. Experimental evaluations with the Cassandra cloud storage on a Grid'5000 testbed show the validity of the metric and demonstrate the effectiveness of the proposed consistency model.

I. INTRODUCTION

Cloud computing has recently emerged as a popular paradigm for harnessing a large number of commodity machines. In such a paradigm, users acquire computational and storage resources with respect to a pricing scheme similar to the economic exchanges in the utility market place: users can lease the resources they need in a Pay-As-You-Go manner [START_REF] Jin | Tools and technologies for building the clouds[END_REF]. For example, the Amazon Elastic Compute Cloud (EC2) is using a pricing scheme based on virtual machine (VM) hours: Amazon currently charges per small instance hour at $0.065 [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF].

With data growing rapidly and applications becoming more data-intensive, many organizations have moved their data to the cloud aiming at providing scalable, reliable and highly available services. Cloud providers allow service providers to deploy and customize their environment in multiple physically separate data centers to meet the evergrowing user needs. Services therefore can replicate their state across geographically diverse sites and direct users to the closest or least loaded site. Leveraging Geographically-distributed data Replicas in the Cloud: Having replications in different datacenters results with fast access (Users1 located at Region (A) and therefore directed to R1 and Users(m+1) located at Region(B) and therefore directed R3); Under heavy load -when multiple replicas coexists -the load will be shared by these replicas and therefore improve the performance (The heavy load distributed between R1 and R2 in Region ); In case of failure, the load will be directed to the closest replica within the same datacenter if possible or on remote one (the replicas within DC(B1) and DC(C1) fails and the load is directed to DC(Bx))

Replication has become an essential feature in storage systems and is extensively leveraged in cloud environments [START_REF] Ghemawat | The Google file system[END_REF][4] [START_REF] Ibrahim | Maestro: Replica-aware map scheduling for mapreduce[END_REF]. It is the main reason behind several features such as fast accesses, enhanced performance, and high availability.(as shown in Figure 1). For fast access users' requests can be directed to the closest data center in order to avoid communications' delays and thus insure fast response time and low latency. For enhanced performance users' requests can be redirected to other replicas within the same data center (but different racks) in order to avoid overloading one single copy of the data and thus improve the performance under heavy load. For high availability failure and network partitions are common in large-scale distributed systems; by replicating we can avoid single points of failure.

A particularly challenging issue that arises in the context of storage systems with geographically-distributed data replication is how to ensure a consistent state of all the replicas. Insuring strong consistency by means of synchronous replication introduces an important performance overhead due to the high latencies of networks across data centers (the average round trip latency in Amazon sites varies from 0.3ms in the same site to 380ms in different sites [START_REF] Li | Making geo-replicated systems fast as possible, consistent when necessary[END_REF]). These high latencies may generate significant financial losses for service providers that use such storage systems. For instance, the cost of a single hour of downtime for a system doing credit card sales authorizations has been estimated to be between 2.2M$-3.1M$ [START_REF] Peglar | Eliminating planned downtime: the real impact and how to avoid it[END_REF]. Consequently, many Internet services tend to rely on storage systems with eventual consistency. Eventual consistency allows the system to return some stale data at some points in time, but ensures that all data will eventually become consistent.

Recently many cloud storage systems have been developed, such as Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF], Cassandra [START_REF]About Data Consistency in Cassandra[END_REF], BigTable [START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF], Yahoo! PNUTS [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF], and HBase [START_REF]Apache HBase[END_REF]. These solutions are practical to use as cloud and web service storage backends. They allow many web services to scale up their systems in an extreme way, while maintaining performance with very high availability. For example, Facebook uses Cassandra to scale up to host data for more than 800 million active users [START_REF]Facebook Statistcs[END_REF]. However, the undoubted availability and performance of such solutions prove to be too costly in terms of inconsistency. As shown in [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF], under heavy reads and writes some of these systems may return up to 66.61% stale reads. This is an alarming rate, as it means that most probably two out of three reads are useless. This in turn adversary impacts the financial profit of the services providers: it generates significant costs as it violates the SLAs of services users.

Consistency-performance and consistency-availability trade-offs have long been investigated in literature: many consistency optimization solutions have been devoted to improving the application's throughput and/or latency while preserving acceptable stale reads rate.However, in the area of cloud computing, the economical cost of using the rented resources is very important and should be considered when choosing the consistency policy.

To address these issues, this paper makes the following three contributions: 1) Service/bill details. To our knowledge, this is the first study to provide in-depth understanding of the monetary cost of cloud services with respect to their adopted consistency models. We discuss the different resources contributed to a service and the cost of these resources. This paper introduces an accurate decomposition of the total bill of the services into three parts with respect to the contributed resources:

• Instances cost: the cost of leasing the virtual machines' instances during the running time of the service.

• Storage cost: the cost of the storage space attached to the virtual machine and the cost of the requests as well.

• Network cost: the cost of the network traffic including the inter-and intra-datacenter commu-nications. To complement our analysis, a series of experiments are conducted to measure the monetary cost of different consistency levels in the Cassandra system [START_REF]About Data Consistency in Cassandra[END_REF] on Grid'5000 [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] and Amazon EC2 [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF]. Such a study is important, as a big-picture understanding of the consistency in geo-replicated systems must take into account the monetary cost within the cloud.

2) Novel metric. We define a new metric called consistency-cost efficiency to evaluate consistency in the cloud. 3) Equitable consistency and low cost. Based on our metric, we introduce a simple yet efficient approach named Bismar, which adaptively tunes the consistency level at run-time in order to reduce the monetary cost while simultaneously maintaining a low fraction of stale reads. Bismar relies on a consistency probabilistic model that estimates the stale reads and the relative costs of the application according to the current read/write rates and network latency. We have implemented Bismar with intensive evaluations on the Cassandra cloud storage system on Grid'5000 [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF]. We use the Yahoo! Cloud Serving Benchmark (YCSB) [START_REF]Yahoo Cloud Serving Benchmark[END_REF] to mimic a real cloud serving environment with elastic access pattern workloads. We show that Bismar can lead to efficient costs without exceeding the tolerated number of stale reads on the applications.

Our paper is the first to provide a thorough analysis of the consistency cost in cloud storage systems. We view our paper as a necessary step for bridging the gap between the business model of the cloud and the research community in distributed systems aiming at designing and building more efficient and economical-oriented consistency models for cloud services.

This paper is organized as follows. Section II briefly discusses the eventual consistency model in the cloud and focuses on the billing details when adopting this model in the cloud. Section III discusses the different resources contributed to service and the cost of these resources, and reports on our empirical study on the monetary cost of consistency models. Then section IV describes the new cost efficiency metric for consistency in the cloud. In section V we describe the Bismar implementation and present detailed results of experimental evaluations. Section VI discusses related work. Finally, section VII presents our conclusions and future work.

II. BACKGROUND AND MOTIVATION

A. Eventual Consistency in the Cloud

The way consistency is handled has a big impact on the performance. Traditional synchronous replication (strong consistency) dictates that an update must be propagated to all the replicas before returning success. In cloud services where data updates occur often, it is difficult to keep the consistency among replicas across the entire cloud storage system. To solve this problem, eventual consistency with an asynchronous quorum replication has been introduced. Here the consistency level is chosen on a per-operation basis and is represented by the number of replicas in the quorum (a subset of all the replicas). Data accesses and updates are performed to all replicas in the quorum. Thus, using this level for both read operations and write operations guarantees that the intersection of replicas involved in both operations contains at least one replica with the last update.

Many cloud storage systems such as Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF], Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF], Voledemort [START_REF]Project Voldemort[END_REF], and Riak [START_REF]Riak: An Open Source Scalable Data Store[END_REF] adopt asynchronous quorum replication [19][20]. This gives the application writer more flexibility when selecting the type of consistency that is appropriate for each operation.

B. Service's Bill Decomposition

Since cloud computing is an economically-driven distributed system paradigm, deploying and running services and applications in the cloud comes with monthly bill. In general, services require a set of linked servers (distributed in multi-sites) to run the web-services' applications; these servers are attached to a group of storage devices which store the services' data. With respect to cloud resources' offers, a basic service bill will include charges for the following resources1 : Computing resources. Virtual machines equipped with a certain amount of CPU and memory resources. Cloud IaaS providers offer different VM instances -varying in the resource's capacity and accordingly the prices -and typically charged for the incurred virtual machine hours. For example, Amazon EC2 [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF] offers a set of instances with different configurations and prices: while the cheapest instance (small instance, equivalent to a server with a CPU capacity of a 1.0-1.2GHz and memory size of 1.7GiB) comes at cost of 0.065$ per Hour, the most expensive instance (High I/O Quadruple Extra Large Instance, equivalent to a server with CPU capacity of 35 × 1.0 -1.2GHz and memory size of 60.5GiB) comes at cost of 3.100$ per Hour. Storage resources. Cloud IaaS providers offer two types of storage services that are different in their pricing and usability. Taking Amazon Web Services as an illustrating example, there are two representative storage services: Amazon Simple Storage Service (Amazon S3) and Amazon Elastic Block Store (Amazon EBS). The storage services are typically billed according to the used GBs per month and number of requests to the stored data. Taking into account the tremendous amount of data that current services need to manage and maintain, and the need to reduce the latency of data movement when processing data, Amazon EBS becomes the customer's first choice to achieve not only highly scalable and high performance services but highly reliable and predictable ones as well. This is despite the fact that Amazon EBS can be attached to any running Amazon EC2 instance and can be exposed as a device within the instance. Consequently, in this study we adapted the Amazon EBS pricing scheme. Network resources. Cloud IaaS providers equip their infrastructure with high speed networks not only within data centers but also across geographically distributed centers. This comes at a monetary cost, although services don't currently reflect the network usage and cost. The network cost is usually embedded within the cost of other services (computational service and storage services), and it varies in accordance to the service type and within/across sites (e.g., the cost of data transfer between Amazon EC2 instances is zero if they are located in the same availability zone).

C. Monetary Cost of consistency: Why it does matter?

With data growing rapidly and applications becoming more data-intensive, a large class of organizations have migrated their data along with their storage backends into the cloud as to provide efficient services in terms of scalability, reliability, and availability : Cloud providers allow service providers to deploy and customize their environment in multiple physically separated data centers to meet the evergrowing users' needs. Services therefore can replicate their date across geographically diverse sites and direct users to an appropriate site based on the locality of access and site load. Thus, replication has become a necessity in these services. However, with replication, consistency comes into question.

We observe that stronger consistency by the means of synchronous replications may introduce high latencies due to the cross-sites communication and therefore will significantly increase the monetary cost of the services:

1) High latency causes high monetary cost. Obviously because the cost of leasing a VM-instance is proportional to the latency (run-time), in addition to the increased cost of both the storage (e.g., number of requests to the copies) and the communication cost (e.g., number of cross-sites communication) due to the synchronous cross-site replication. 2) High latency causes significant financial losses for service providers that use such storage systems. For instance, the cost of a single hour of downtime for a system doing credit card sales authorizations has been estimated to be between 2.2M$-3.1M$ [START_REF] Anderson | What consistency does your key-value store actually provide?[END_REF]. On the other hand, we observe that eventual consistency or weaker consistency may reduce the monetary cost with respect to a lower maintained latency and therefore lower instance costs, but this comes at the risk of increasing the rate of stale data (e.g., [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF] demonstrated that under heavy reads and writes some of these systems may return up to 66.61% stale reads). This in turn adversarily impacts the financial profit of the service providers: it generates significant financial losses as it violates the SLAs of services users. This makes eventual consistency a two-edged sword. While the eventual consistency has been exploited extensively in literature and commercial products, its monetary cost and negative impacts on the stale reads rate have been largely ignored.

The aforementioned observations, combined with the urgent need to address the consistency-cost efficiency and stale reads problems associated with quorum replications, motivate us to an in-depth study of the monetary cost of the different consistency levels in the cloud and -as a result -to propose our cost efficient optimization.

III. MICROSCOPIC OF CONSISTENCY COST

In section 2.2, we gave a big-picture understanding of the cost of services deployed in the cloud by describing the different resources contributed to obtain a certain level of consistency in geo-replicated storage systems. In this section we complement our macroscopic analysis with a detailed analysis of the consistency cost in the cloud, using a widely used open source geo-replicated storage system that supports multi-level consistency as an illustrated example, namely Cassandra [START_REF]About Data Consistency in Cassandra[END_REF].

Ideally, we would like to get a deep idea of why different consistency levels may result in different costs, how the resources accordingly contribute to the total cost, and how background operations such as read repair can impact the overall cost.

The choice of consistency level cl affects all of these three costs. When higher consistency levels are required more replicas are involved in the requests. That affects both operations latency and throughput, which leads to higher runtime. Similarly, network traffic grows higher with higher consistency levels, which leads to a higher networking bill. Moreover, higher consistency levels generate a higher number of requests from storage devices, directly affecting storage cost.

Formula 1 presents the overall cost for geo-replicated based services for a given consistency level cl. Essentially, this cost is the combination of the VM instances cost Cost in (cl), the backend storage cost Cost st (cl), and network cost Cost tr (cl).

Cost all (cl) = Cost in (cl) + Cost tr (cl) + Cost st (cl) (1)

A. Computing unit: Instances cost

A common pricing scheme used by recent cloud providers is primarily based on virtual machine (VM) hours. Formula 2 presents the cost of leasing nbInstances VM-instances for a certain time runtime.

Cost in (cl) = nbInstances × price × ⌈ runtime timeUnit ⌉ (2)
Here the price is the dollar cost per timeUnit2 (e.g., In Amazon EC2 small instance the price is 0.065 per hour).

In order to generalize our pricing model and avoid inaccurate pricing due to unexpected network behavior (especially that we are studying the consistency cost in geo-distributed sites), we present the runtime in the form of number of operations nbOps in the workload while fixing the throughput of a specific consistency level.

runtime = nbOps throughput (3)
The throughput varies from one consistency level to another according to the size of the internal traffic between sites.

B. Storage cost

As mentioned earlier the storage cost includes the cost of leased storage volume (GB per month) and the cost of I/O requests to/from this attached storage volume. In Amazon EC2 for instance, this would be the cost of attaching Amazon EBS to VM-instances in order to increase the storage capacity using a highly durable and reliable way. The total storage cost is accordingly given by Formula 4:

Cost st (cl) = costPhysicalHosting + costIORequests (4)
Based on the size of hosted data ( including all data replications) nbNodes × dataSize where dataSize is the average data size per volume attached to VM-instance ( locality and load balancing are important features in current data centers), we calculate the costP hysicalHosting in Formula 5.

costPhysicalHosting = nbNodes × ⌈ dataSize sizeUnit ⌉ × price (5)
where the price is the dollar cost per sizeUnit (e.g., In Amazon EBS the price is 0.10 per GBmonth).

We further estimate costIORequests in Formula 6.

costIORequests = cl × nbOps + readRepairIO nbRequestsUnit × price (6)
where nbOps is the number of operation with respect to the consistency level cl (it varies according to the number of replications involved in an operation). The read repair in a background operation is mostly triggered when inconsistency is detected. It generates requests to the storage devices and therefore it is important to include the read repair operations in our formula readRepairIO (more details about the read repair function will be provided in next section 3.1).

C. Network cost

Network cost varies in accordance to the service type of the source and destination (e.g., computational service and storage services) and whether the data transfer is within or across sites. In general, inter-datacenter communications is more expensive than intra-datacenter communications. Formula 7 shows the total cost of network communications as the sum of inter-and intra-data center communications 3 (trafficInterDC and trafficIntraDC).

Cost tr (cl) = price(interDC) × ⌈ trafficInterDC sizeUnit ⌉ +price(intraDC) × ⌈ trafficIntraDC sizeUnit ⌉ (7)
where price(interDC) and price(intraDC) are the dollar cost per sizeUnit.

Hereafter we illustrate how to estimate both the inter-and intra-datacenter traffic.

Formula 8 shows our model of the inter datacenter, trafficInterDC, given the replicas communication interDcRep, the request routing requestrouting, and the internal mechanisms traffic IMechTraffic.

trafficInterDC = interDcRep + requestRouting +IMechTraffic (8)
The inter-site traffic generated by the replicas communications strongly depends on the consistency level and the distribution of replication among datacenters (i.e., the number of replicas involved in a request to other datacenters which can be estimated as ⌊(nbDc -1) × cl nbDc ⌋4 where nbDc is the number of datacenters). Formula 9 shows our estimation of the inter traffic generated by the replicas communications.

InterDcRep = ⌊(nbDc -1) × cl nbDc ⌋ ×AvgDataSize × nbOps ( 9
)
where avgDataSize is the average data size needed to be propagated to other replicas for one operation. The traffic generated by the request routing and internal mechanisms depends essentially on the storage system design and implementation. Since our approach is destined to run on Cassandra storage, hereafter we illustrate such values with respect to this particular storage system. In Cassandra, all nodes (peers) have equal ranges of data and thus have an equal number of keys: this implies that each node is responsible for 1 number of nodes fraction of the keys.

Giving the number of nodes as nbNodes and the average number of nodes per datacenter avgNodesDc, the average number of request routing for an operation can be estimated as nbNodes-avgNodesDc nbNodes . The size of inter traffic generated by request routing for a number of operations nbOps is therefore denoted as Formula 10. requestRouting(interDC) = nbNodes -avgNodesDc nbNodes ×nbOps × avgDataSize [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF] In Cassandra storage, the main internal traffic is generated by the gossip traffic and read repair mechanism as shown in Formula 11. The gossip traffic -used to share the state of nodes in the ring -is relatively small since it is just transmitting the state of one node which is negligible compared to data transfer.

IMechTraffic = gossip(interDc) +readRepair(interDc) (11)
On the other hand, the read repair is used to propagate data to out of date (stale) replicas. The read repair function is triggered in two cases:

1) At random times for some requests: defined by the system administrator. 2) Whenever inconsistency is detected.

Formula 12 shows that read repair traffic depends on the probability or chance of triggering the mechanism rrChance which is defined by the storage administrator, as well as the chance of detecting mismatching replicas' timestamps mmChance = rf-cl rf × nbWrites nbReads+nbWrites , where rf is the replication factor, nbWrites and nbReads are the number of write and reads.

readRepair(interDC) = nbOps × avgDataSize ×(rrChance × ⌊ rf nbDc ⌋ + mmChance × ⌊ rf -cl nbDc ⌋) (12)
Computing the intra datacenter traffic size is very similar to the one of inter datacenter traffic. However, the intra traffic size of request routing is given by Formula 15.

requestRouting(intraDC) = avgNodesDc -1 nbNodes × nbOps × avgDataSize (13)
Similarly, we only consider the traffic in-between replicas within the same datacenter: Accordingly, the intra-site traffic generated by the replicas communications is denoted as in Formula14 and the read repair traffic is given by Formula 15 intraDcRep = (⌈ cl nbDc ⌉ -1) × avgDataSize × nbOps ( 14)

readRepair(intraDC) = nbOps × avgDataSize ×(rrChance × (rf -⌊ rf nbDc ⌋) + rf -cl rf × ((rf -cl) -⌊ rf -cl nbDc ⌋)) (15)

D. Practical View of Consistency Cost in Cassandra

As we mentioned, our goal is to investigate the monetary cost variation of geo-replicated storage systems when adopting different consistency levels. Consequently we complement and benefit our earlier analyze, by evaluating the monetary cost in Cassandra.

1) Experimental setup: We run our experiments on Grid'5000 [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] and Amazon Elastic Compute Cloud (EC2). On Grid'5000, we deployed Cassandra on two datacenters (sites): with 30 nodes on the Sophia site and 20 nodes on the Nancy site as shown in Figure 2(a). All the nodes in Sophia are equipped with a 250GB hard disk, 4GB of Memory, and 4-cores AMD Opteron. The nodes in Nancy are equipped with disks of 320GB space, 16GB of Memory, and 8-cores Intel Xeon. The network connection between the two sites is provided by RENATER (The French national telecommunication network for technology, education, and research). It consists of a standard architecture of 10Gbit/s dark fibers. The network route between the two sites is the following: Nancy-Paris-Lyon-Marseille-Sophia: the average round trip latency is on average 0.230ms within the same site and 18.2ms in-between the two sites. On Amazon EC2, we also deployed Cassandra on 18 large instances (m1.large) on two availability zones: 10 instances on us-east-1a and 8 instances on us-east-1d. The average round trip latency is on average 0.284ms within the same site and 0.813ms inbetween the two availability zones.

We used Cassandra-1.0.2 with a replication factor of 5 replicas: 2 replicas are allocated in Nancy and 3 replicas in Sophia (The same replication factor is used in Amazon EC2: 2 replicas in us-east-1d and 3 replicas in us-east-1a). Our replication strategy uses NetworkTopologyStrategy to enforce replication across multiple datacenters. We adopt the pricing schemes from Amazon web services as shown in Table 1 5 . We study the cost variation by evaluating different consistency levels (e.g., eventual consistency: one, two, Quorum: three, and strong consistency: All).

2) Micro Benchmark: We aim at a micro benchmark representing typical workloads in current services hosted in clouds. Based on case studies [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF][22], we have selected the Yahoo! Cloud Serving Benchmark (YCSB) framework [START_REF]Yahoo Cloud Serving Benchmark[END_REF]. YCSB is used to benchmark Yahoo! cloud storage system "PNUTS" [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF]. It is extended to be used with a variety of open-source data stores such as mongoDB [START_REF]mongoDB[END_REF] ,

Hadoop HBase [START_REF]Apache HBase[END_REF] and Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF]. YCSB provides the features of a real cloud serving environment such as scaleout, elasticity and high availability. For this purpose, several workloads have already been proposed in order to apply a heavy read load, heavy update load, and read latest load, among other workloads. Also, the benchmark is designed to make the integration of new workloads very easy. We use YCSB-0.1.3 and we run WorkloadA which is a heavy read-update workload (read/update ratio: 60/40). In both environments, our workload consists of 10 million operations on 5 million rows with a total of 23.84GB of data after replication.

3) Results on Grid'5000: As shown in Figure 2(b), the total monetary cost decreases when degrading the consistency level: the cost reduces from $138.76 -when the consistency level is set to ALL -to $71.72 when the consistency level is ONE (i.e., weak consistency reduces the cost by almost 48%). This result was expected as lower consistency levels involve fewer replicas in the operations, and thus maintaining low latency, less I/O requests to the storage devices, and less network traffic in general (the runtime of WorkloadA varies from 4 hours to 7 hours according the consistency level). This cost reduction, however, comes at the cost of a significant increase in the stale reads rate: as shown in Figure 2(b) 79% of the reads are stale reads -only 21% of the reads are fresh reads -when the consistency level is set to ONE.

Furthermore, it is obvious that degrading the consistency level for Quorum (here the number of replicas involved in an operation is 3 replicas) reduces the total cost by 13% while maintaining a zero stale reads rate as shown in Figure 2(b). This is because the storage system answers the read requests with the most up-to-date replica (fresh reads), which is always in the replicas quorum. Moreover, degrading the consistency level to TWO reduces the total monetary cost by almost 36%, but it adversary impacts the system consistency: only 61% of the reads where fresh reads. Observation 1: The total cost of geo-replicated services strongly depends on the consistency level adopted: stronger consistency has higher cost but higher rate of fresh reads and vice versa. However, as services differ in their tolerable stale reads and their access pattern (within the same service: there is a significant diurnal variation in the access patten and the load levels). There is a need to define new metric to define the consistency level of an application. (e) Breakdown of the Monetary cost (Amazon) Figure 2. Experiments setup and results on Grid'5000 and Amazon EC2 ing to the contributed resources. In general, the instances cost has the higher cost amongst other resources (storage and network): it contributes to almost 90% of the service bill while the storage and network contribute on average to only 9% and 0.4%, respectively. This is due to our experiments' scale -number of operations -and the cheap prices of resources (as shown in Table I the intra communication is free of charges).

As shown in Figure 2(c), storage cost has a relatively lower contribution to the total cost for stronger consistency (ALL and Quorum) compared to weaker consistency (ONE and TWO): it contributes on average to 7.2% for the stronger one and 9% for the smaller one. The ALL consistency level requires higher nbOps compared to Quorum while both have zero/low readRepairIO and thus according to Formula (6) ALL has a relatively higher storage cost contribution in contrast to Quorum (e.g., it is 7% for Quorum and 7.5% for ALL). Moreover, although the nbOps is smaller for (ONE and TWO) compared to (ALL and Quorum) but the increasing number of readRepairIO increases the storage cost. Furthermore, as the cost of readRepairIO is proportional to the rate of stale reads, ONE has higher storage cost contribution in contrast to TWO.

In summary, the read repair function -ensuring that all outdated replicas become up to date -plays a very important role in determining the cost of storage with different consistency levels.

Network cost has also relatively a lower contribution to the total cost for stronger consistency (ALL and Quorum) compared to weaker consistency (ONE and TWO): it contributes on average to 0.175% for the stronger one and 0.275% for the smaller one. The ALL consistency level requires higher interDcRep compared to Quorum (higher number of involved replicas as well as Quorum always tends to answer the requests by involving the most close replicas "within the same data center if possible") while both have zero/low IMechTraffic and thus according to Formula 11 ALL has a relatively higher network cost contribution in contrast to Quorum. Moreover, although the interDcRep is smaller in for (ONE and TWO) compared to (ALL and Quorum) but the increasing size of IMechTraffic -due to the high rate of stale reads -increases the network cost. Furthermore, as the cost of IMechTraffic is proportional to the rate of stale reads, ONE has higher storage cost contribution in contrast to TWO.

Observation 2: Higher consistency causes a higher contribution to instances cost due to the high latency, and it causes a relatively lower contribution to both the storage and network cost as it avoids the extra cost caused by the read repair function. 2(d) and 2(e) support our earlier findings and observations with Grid'5000. The total cost variation in Amazon is lower than in Grid'5000, because of the more powerful machines and the lower cross-sites latency.

4) Results on AmazonEC2: Figures

As shown in Figure 2(d), the total monetary cost decreases when degrading the consistency level: the cost reduces from $32.39 -when the consistency level is set to ALLto $23.23 when the consistency level is ONE (i.e., weak consistency reduces the cost by almost 28%). This result was expected as lower consistency level involves fewer replicas in the operations, and thus maintaining low latency, less I/O requests to the storage devices, and less network traffic in general (the run-time of WorkloadA varies from 2 hours to 3 hours and 33 minutes according to the consistency level). This cost reduction, however, comes at the cost of a significant increase in the stale reads rate: as shown in Figure 2(d) 79% of the reads are stale reads -only 21% of the reads are fresh reads -when the consistency level is set to ONE.

Moreover, the costs of the ONE and TWO levels are the same, although there were significant variations in the running time (2hours and 1minutes for ONE and 2hours and 33minutes for TWO) and also significant variations in the network traffic and storage requests. This is because of the coarse-grained pricing units (per instance hour and per GB storage and per 1 million operations, etc).

Figure 2(e) shows the breakdown of the total cost according to the contributed resources. The instances cost has the higher cost amongst other resources (storage and network): it contributes to almost 74% of the service bill while the storage and network contribute on average to only 25.2% and 0.8%, respectively. This is due to our experiments' scalenumber of operations -and the cheap prices of resources (as shown in Table I the intra communication is free of charges). Moreover, the ratio of the cost of the instances, storage and network to the total cost in Amazon EC2 is different from Grid'5000, because the shorter running time (the high throughput and the powerful machines) which in turn makes the instances cost smaller compared to other resources. As shown in Figure 2(e), ALL has a relatively higher storage cost contribution in contrast to Quorum (e.g., it is 28% for ALL and 22% for Quorum). This is because the ALL consistency level requires higher nbOps compared to Quorum while both have zero/low readRepairIO. Moreover, although the nbOps is smaller for (ONE and TWO) compared to (ALL and Quorum) but the increasing number of readRepairIO increases the storage cost. Furthermore, as the cost of readRepairIO is proportional to the rate of stale reads, ONE has higher storage cost contribution in contrast to TWO. The Network cost has also relatively a lower contribution to the total cost for stronger consistency (ALL and Quorum) compared to weaker consistency (ONE and TWO): it contributes on average to 0.7% for the stronger one and 0.9% for the smaller one. This cost varies from one consistency level to another according to the number of involved replicas for the stronger consistencies and number of stale reads for the weaker ones.

IV. CONSISTENCY-COST EFFICIENCY METRIC

As discussed in earlier, data consistency can strongly impact the financial cost of a certain service (i.e., while stronger consistency with high latency implies higher monetary cost of operation as demonstrated in section 4, the weaker consistency with high throughput causes higher operational cost because of the high rate of stale rate). Consequently, monetary cost should be considered when evaluating the consistency in the cloud [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF].

As cloud computing is an economy-driven distributed system where monetary cost is explicate and measurable metric [START_REF] Wang | Distributed systems meet economics: pricing in the cloud[END_REF], we argue that the consistency-cost trade-off can be easily exposed in the cloud. Therefore in this paper, we define a new metric -consistency-cost efficiency -that exposes the tight relation between the degree of achieved consistency for a given monetary cost. Our goal is to define general yet accurate metric to evaluate consistency and thus using this metric as an optimization metric for cloud systems. Accordingly we define the consistency-cost efficiency as the ratio of consistency, measured by the rate of fresh reads, to the relative consistency cost as shown in Formula 16.

Consistency-Cost Efficiency

= Consistency(cl) Cost rel (cl) (16)
Where Consistency(cl) = 1stalereadsrate and Cost rel is the relative consistency cost with respect to the strong consistency and given by Formula 17.

Cost rel (cl

) = Cost(cl) Cost(cl all) (17)
It is important to mention that our metric is designed and can only be applied when strong consistency is not required by an application: we can consider our metric as system optimization for eventual consistency (i.e., tune the consistency to reduce the monetary cost without violating the application's requirements of fresh read rate).

V. ECONOMICAL CONSISTENCY APPROACH

A. Design

We design and implement our approach with the following goals: Extendable consistency-cost efficiency. Our solution aims at providing consistency guarantees while reducing the monetary cost. Therefore, we propose to use the consistency-cost efficiency (described in section IV) as an optimization metric: simply by selecting the consistency level with maximum consistency-cost efficiency. Moreover, to meet the diversity of applications requirements (e.g., cost constraint and fresh reads rate constraint), our solution can be easily extended to enable consistency-cost efficiency while favoring either cost or consistency. Self-adaptive. With the ever growing diversity in the access patterns of cloud applications along with the unpredictable diurnal/monthly changes in services loads, it is important to provide a self-adaptive approach that transparently scales the consistency level up/down at runtime without any human interaction. Our approach, therefore, embraces an estimation model for consistency-cost efficiency that could be achieved with different consistency levels: at runtime, the application's access pattern and network latency are fed to the consistency probabilistic estimation model (we have extended the model in [START_REF] Chihoub | Harmony: Towards automated self-adaptive consistency in cloud storage[END_REF] as will be explained later in this section) in order to estimate the rate of stale data that could be read in the storage system. Furthermore, these data along with information about pricing units in the targeted cloud platform are used to compute the monetary cost. Pricing independent. Our solution targets public cloud and is not limited to any cloud provider in terms of provided services or pricing schemes. The fine-grained monetary cost analysis that is used for cost estimation (introduced in Section III) can be easily adopted to different services and pricing. cloud storage systems independent. Since our solution is implemented as a separate layer at the top of the cloud storage system, it does not impose any modifications to the cloud system code. Our approach, therefore, can be applied to different cloud storage systems that are featured with flexible consistency rules.

1) Consistency Probabilistic Estimation: In our previous work [START_REF] Chihoub | Harmony: Towards automated self-adaptive consistency in cloud storage[END_REF], we propose an estimation of the stale read rate in the system by means of probabilistic computations. We define the situation that leads to a stale read in Figure 3. The read may be stale if its starting time X w is in the time interval between the starting time of the last write and the end of the propagation time of data to the other replicas. This situation is repeatable for any write dates that may occur in the system. T p in Figure 3 is the time necessary for the propagation of a write or an update to all the replicas. It is computed based on the network latency L n and the average write size avg w and should be represented as T p (L n , avg w ), but in order to simplify the representation, it will be denoted as T p in the rest of the paper.

Transactions arrivals are generally considered as a Poisson process as it is the common way to model them in literature [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF] [START_REF] Tai | Performability management in distributed database systems: An adaptive concurrency control protocol[END_REF]. We assume that the writes and the reads arrivals follow the Poisson distribution of parameter λ -1 w (we chose λ -1 w instead of λ w in order to simplify subsequent formulas where the parameter will be inverted) and λ r respectively. These parameters values change dynamically at run time following the read and write requests arrivals monitored in the storage system. Since the distribution of waiting time between two Poisson arrivals is an exponential process, the stochastic variables X w and X r of a write time and read time follow an exponential distribution of parameters λ -1 w and λ r respectively. The probability of the next read being stale corresponding to the aforementioned situation is given by formula [START_REF]Riak: An Open Source Scalable Data Store[END_REF] with N being the replication factor in the system and X being the number of replicas involved in the read operation. Here X n =1 for the basic eventual consistency.

P r(stale read) = ∞ i=0 ( N -(X n = 1) N P r(X i w < X r < X i w + T + T p ) + X n = 1 N P r(X i w < X r < X i w + T )) (18)
Having all the writes times (that may occur in the system) following the exponential distribution, the sum of X i w all the writes follows a Gamma distribution of parameters i and λ w . Hence, the probability in formula (18) becomes:

P r(stale read) = ∞ i=0 ( N -1 N ∞ 0 f i w (t)(F r (t + T + T p ) -F r (t))dt + 1 N ∞ 0 f i w (t)(F r (t + T ) -F r (t))dt) (19)
The time T to write in the local memory is negligible in comparison to T P and therefore, we can consider it as equal to 0. A simple replacement of the probability mass function of Poisson distribution and the cumulative distribution function of Gamma distribution results in the following probability:

P r(stale read) = ∞ i=0 N -1 N ∞ 0 t i-1 e -t λw γ(i)λ i w (e -λrt -e -λr(t+Tp) )dt (20)
After simplifying formula [START_REF] Gifford | Weighted voting for replicated data[END_REF], it becomes:

P r(stale read) = ∞ i=0 (N -1)(1 -e -λrTP ) N (1 + λ r λ w ) i ∞ 0 t i-1 e 1+λr λw λw t γ(i)( λw 1+λr λw ) i dt (21)
The right part of the function in [START_REF] Anderson | What consistency does your key-value store actually provide?[END_REF] is the the cumulative distribution function of a Gamma law of parameters 1+λr λw λw and i, its value is equal to 1. Moreover, if we consider that:

∞ i=0 ( 1 1 + λ r λ w ) i = 1 λ r λ w + 1 (22)
The final value of the probability of next read to be stale, after simplification, is given by:

P r(stale read) = (N -1)(1 -e -λr Tp )(1 + λ r λ w ) N λ r λ w (23)
Given that when the storage system supports multiple consistency levels, the consistency level for read and write operations (cl r and cl w respectively) may vary with time. Accordingly, we extend the probability model in Formula ?? to consider all the consistency levels for write operations that are smaller or equal to the Quorum level, where a quorum is computed as: ⌊ replicationf actor 2 + 1⌋. This probability is given in Formula 24.

P r(stale read) = (N -

(cl w + cl r -1))(1 -e -λrTp )(1 + λ r λ w ) N λ r λ w (24)
This estimation model requires basic knowledge of the application access pattern and of the storage system network latency. Network latency in this case is of high importance, since it is the determinant of the updates propagation time to other replicas. The access pattern, which includes read rates and write rates is a key factor to determine consistency requirements in the storage system. For instance, it is obvious that a heavy read-write access pattern would produce higher stale reads when adopting eventual consistency.

2) Efficiency-aware algorithm : Many applications do not strictly require strong consistency: a consistency optimization solution, therefore, can be introduced to improve system throughput, latency and monetary cost. To achieve this goal we consider our metric as an optimization metric as shown in the following algorithm.

while At run-time, our system feeds the efficiency-aware algorithm with data related to the system read/write rates along with the network latency. These data are used by the consistency probabilistic estimation model to compute the expected achieved fresh reads when using different consistency levels. The relative monetary cost is also computed according to the system configuration and the stale read estimation. So the algorithm selects the consistency level that offers the most equitable consistency, cost trade-off (the maximum consistency-cost efficiency value).

B. Implementation

We have built our approach as a separate layer on top of Apache Cassandra-1.0.2 [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF]. Cassandra gives the user flexible usage of consistency levels in a per-operation manner. In addition, Cassandra is proven to be very scalable, providing very good performance, and being widely used with large scale applications such as Facebook and Twitter. Our approach is introduced as an extra layer on Cassandra that aims to provide the most cost-efficient level of consistency for reading data. The core of this layer consists of two modules. Both modules were implemented in Python 2.7. The monitoring module collects relevant metrics needed for our approach of the storage system's information. The Cassandra nodetool was used to collect the number of reads and writes in Cassandra storage, and we used the ping tool to collect network latencies in the storage system network (the network latency and the average data size is used to compute the propagation time T p which later used in Formula 24). The monitoring module was designed in a multithreaded manner in order to make it time-efficient and to reduce the monitoring time. Each thread collects data from a set of nodes and at the end an aggregation process is applied. The monitoring time is measured and taken into account when computing the read rates and write rates. This data is further communicated to the dynamic consistency module. This module is the heart of our implementation. An estimation of cost-efficiency is computed -according to the estimated stale read rate and the monetary cost (instance, storage and network cost)-and then compared in order in to provide an adequate cost efficient consistency level (select the consistency level with the highest cost-efficiency ratio) for the running application at that point of time.

VI. EVALUATION

In this section, we present our detailed evaluation of our the consistency-cost efficiency metric and the Bismar prototype using Cassandra on Grid'5000 testbed (We used the same testbed described in Section 3.2.). Our experiments evaluate two aspects: (a) validate the effectiveness of the consistency-cost efficiency metric as a representative metric for measuring; (b) overall monetary cost reduction achieved by Bismar (c) the tolerable fresh reads rates with Bismar and (d) the distribution of monetary cost amongst the different used resources when using Bismar.

Micro Benchmark. We use YCSB and we run Work-loadA which is a heavy read-update workload (read/update ratio: 60/40). Our workload consists of 10 million operations In order to present the dynamicity of the system (i.e., the variation of throughput and the read/write rate during the run-time), we ran the workload, varying the number of threads starting with 1 thread, then, 50, 20, 7 and finally, 30 threads.

A. Effectiveness of the Consistency-cost efficiency

In order to validate our metric, we collect samples when running the same workload with different access patterns and different consistency levels. Figure 4 shows the results where each point shape represents a different access pattern: Higher consistency-cost efficiency values represents high rate of fresh reads for all samples when the fresh reads rate is lower or equal to 80%. This indicates the effectiveness of our metric: it is designed to achieve the best price without violating the consistency (we consider the 80% fresh reads as acceptable consistency).

B. Monetary Cost and Performance improvement

Figure 5(a) shows the monetary costs of running the workload with the three static consistencies (ONE, TWO and Quorum) and with our dynamic adaptive approach. As expected, ONE exhibits the lowest monetary cost but at the cost of fresh reads. Our experiments also show some interesting results: Bismar achieves lower cost in contrast to the consistency level TWO. Since Bismar always selects the consistency level with the highest consistency-cost efficiency to adapt to workload dynamicity, Bismar adopts the consistency level ONE for almost 70% of its running time while it adopts the consistency level Quorum for 30% of it is running time as shown in Figure 5(b). As a result the cost reduction when running with ONE overcomes the cost increase when running with Quorum.

Since Bismar targets applications that do not require strong consistency, we consider Bismar as an eventual consistency optimization for cloud. Therefore, improves the monetary cost of services while maintaining acceptable rate of fresh reads. Accordingly, we compare the cost monetary reduction and performance improvement by Bismar in contrast to the Quorum consistency level. As shown in Figure 5(a) and Figure 5(c), Bismar reduces the monetary cost by almost 31.5% in contrast to Quorum level (From $456 to $312). The cost reduction is mainly due to the performance improvements (Bismar improves the overall response time by almost 32.2%).However more detailed analysis on the impact of Bismar of the different resources' costs will be presented later.

C. Staleness evaluation

Figure 5(d) shows the stale reads rates caused by different consistency approaches. It is clear that static levels ONE and TWO produce higher stale reads rate: 61% of the reads where on stale data with ONE and 36% with TWO. Moreover, the Quorum consistency level returns always up-to-date data (i.e., stale reads rate is 0%) because at least one replica with the freshest data should be in the Quorum. Bismar however, returns very small portion of stale reads (only 3%), but with very important money saving (31.55% money reduction compared to Quorum). The 3% stale reads is considerably reasonable for many applications.

D. Zoom on resources cost in Bismar

Figure 5(e) shows the breakdown of the total cost according to the contributed resources for different consistency levels and Bismar. As shown and discussed earlier in Section 2.4, the instance portion of the total cost increases with upgrading consistency while the portion of both the storage and network costs increase with degrading the consistency level. However, the aforementioned observation is also applied on Bismar: comparing Bismar against Quorum, we notice that portion instance cost in Bismar is lower than in Quorum, furthermore, we observe that the portion of both the storage and network costs in Bismar is higher than in Quorum. This can explain why the cost reduction was only 31.5% while the performance improvement was 32.2%: because the adversary impacts of the storage and network costs in Bismar.

Moreover, we observe that the portion of both the storage and network costs in Bismar is higher than in all static consistencies, because Bismar combines both the high number of requests when adopting a higher consistency level and also read repair cost in the case of mismatched replicas' versions detection when Bismar adopts lower consistency level.

VII. RELATED WORK

With the explosive growth of data size and availability requirements of services in the cloud along with the 67897A BCDAE9 tremendous increase in users accessing theses services, geographically distributed replication has become a necessity in the cloud storage [START_REF] Ghemawat | The Google file system[END_REF][4] [START_REF] Dean | Mapreduce: simplified data processing on large clusters[END_REF]. At such scale, the strong consistency suffers of high latency and thus violating both the performance and availability requirements. Cloud storage is therefore evolving towards eventual consistency. Eventual consistency has been extensively exploited in literature and commercial products such as Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF] in Amazon S3 [START_REF]Amazon Simple Storage Service (Amazon S3)[END_REF] and Amazon DynamoDB [START_REF]Amazon DynamoDB[END_REF], Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] in Facebook [START_REF]Facebook Statistcs[END_REF] and PNUTS [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF] in Yahoo!. While the most of the work in literature have been dedicated to either measuring the actual provided consistency in cloud storage platforms [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF][21] [START_REF] Bermbach | Eventual consistency: How soon is eventual? an evaluation of amazon s3's consistency behavior[END_REF], or on adaptive consistency tuning in cloud storage systems [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF] [33] [34] [26] [6] in order to meet the consistency requirements of applications and reduce the consistency violation. Despite our work being focused on the monetary cost, a key difference between our work and their work is that we are seeking an adaptive consistency approach which is at the same time cost efficient and does not violate the applications needs.

A closely related work on improving the monetary cost of consistency in the cloud is [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF]. Kraska et al. [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF] propose consistency rationing: an automatic approach that adapts the level of consistency at run-time considering the performance and monetary cost. The authors define consistency levels at data level (i.e., categorizes the data into three types and provides a different consistency treatment for each category).

Consistency rationing at data level may incur additional meta data management overhead when the data size is large, our work therefore is at a transaction level: our adaptive tuning approach chooses the number of replications involved in an operation considering the best trade-off between the consistency level and monetary cost. The results discussed in our paper complement Kraskas work: monetary cost-oriented consistency approach at transaction levels to complement their work at data level.

With respect to monetary cost in cloud systems, a number of studies [START_REF] Palankar | Amazon s3 for science grids: a viable solution?[END_REF] [START_REF] Deelman | The cost of doing science on the cloud: the montage example[END_REF] have been dedicated to measure the cost of adopting the pay-as-you-go cloud in terms of monetary cost, performance, and availability. Some studies [START_REF] Wang | Distributed systems meet economics: pricing in the cloud[END_REF][37] [START_REF] Ibrahim | Towards pay-as-you-consume cloud computing[END_REF] have reported on the cost variations and fairness in the cloud. Many recent studies concentrate on monetary cost improvements of cloud services through reducing the virtualization interference [START_REF] Ibrahim | Adaptive disk i/o scheduling for mapreduce in virtualized environment[END_REF], using spot instance or levering the public cloud using free resources such as desktop grid [START_REF] Chohan | See spot run: using spot instances for mapreduce workflows[END_REF] [START_REF] Liu | Cutting mapreduce cost with spot market[END_REF]. In contrast, this paper investigates the interplay between economic issues and the consistency design and implementation.

VIII. CONCLUSION

With the pay-as-you-go charging, the public cloud has become an economic market for both cloud users and providers. Accordingly, many services have been deployed in the cloud in order to benefit from its low cost and its geographically distributed infrastructure: cloud allows these services to replicate their data and thus satisfy the ever growing users' needs and ensure availability. However, ensuring data consistency between these geographically distributed replicas calls for empirical evaluations and technical innovations.

In this study, we investigate the monetary cost of consistency in the cloud. Our detailed analysis and study revealed a noticeable monetary cost variation when different consistency levels are used. As a first step to understand the impacts of the different consistency on the monetary cost and fresh reads in the cloud, we define the consistencycost efficiency metric. Based on our metric, we introduce a simple, yet efficient approach, named Bismar, that adaptively tunes the consistency level at run-time in order to reduce the monetary cost while simultaneously maintaining a low fraction of stale reads. Bismar relies on a consistency probabilistic model that estimates the stale reads and the relative costs of the application according to the current read/write rate and network latency. We have implemented Bismar with intensive evaluations on Cassandra cloud storage system on Grid'5000. We show that Bismar can lead to efficient cost without exceeding the tolerated number of stale reads on the applications.

Regarding future work, we intend to perform more detailed theoretical and empirical analysis of the consistencycost efficiency metric. Also we are interested in building an efficient mechanism for dynamic resource provisioning based on our cost function.

  Figure 1.Leveraging Geographically-distributed data Replicas in the Cloud: Having replications in different datacenters results with fast access (Users1 located at Region (A) and therefore directed to R1 and Users(m+1) located at Region(B) and therefore directed R3); Under heavy load -when multiple replicas coexists -the load will be shared by these replicas and therefore improve the performance (The heavy load distributed between R1 and R2 in Region ); In case of failure, the load will be directed to the closest replica within the same datacenter if possible or on remote one (the replicas within DC(B1) and DC(C1) fails and the load is directed to DC(Bx))

Figure 2 (

 2 c) shows the breakdown of the total cost accord-

Figure 3 .

 3 Figure 3. Situation that leads to a stale read

Figure 4 .

 4 Figure 4. Effectiveness of the Consistency-cost efficiency

Figure 5 .

 5 Figure 5. Cost, Staleness, and Efficiency on Grid'5000

The pricing of some cloud services (computing and storage services) may vary at different providers or at different provider-sites. As the goal of our study is to explore the consistency cost variation, we assume that the computing and storage pricing is the same at different sites

We use the ceiling function because most providers charge each partial instance-hour as a full hour.

For simplicity, we consider only two geographical areas within which the prices differ. Some cloud providers may have more geographicallyoriented prices: within availably zone, within regions, between regions. However, our pricing model can be easily extended to any number of geographical-oriented pricing options.

[START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF] For example if the (nbDC=3) and number of replicas involved in an operation (cl=4), the estimated number of replicas involved in a request on other dataceters is ⌊2 ×[START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF] 3 ⌋ = ⌊ 8 3 ⌋ = 2 where ⌊ ⌋ is a floor function.

The price of Amazon EC2 large instance was $0.32 at the time of writing this paper and it is now $0.26. However, as this price is applied to all consistency levels the difference in the pricing therefore doesn't affect our results and findings.