|
|
An efficient and highly available framework of data recency enhancement for eventually consistent data stores |
Yu TANG,Hailong SUN,Xu WANG(),Xudong LIU |
School of Computer Science and Engineering, Beihang University, Beijing 100191, China |
|
|
Abstract Data items are usually replicated in modern distributed data stores to obtain high performance and availability. However, the availability-consistency and latencyconsistency trade-offs exist in data replication, thus system designers intend to choose weak consistency models, such as eventual consistency, which may result in stale reads. Since stale data items may lead to serious application semantic problems, we consider how to increase the probability of data recency which provides a uniform view on recent versions of data items for all clients. In this work, we propose HARP, a framework that can enhance data recency of eventually consistent distributed data stores in an efficient and highly available way. Through detecting possible stale reads under failures or not, HARP can perform reread operations to eliminate stale results only when needed based on our analysis on write/read processes. We also present solutions on how to deal with some practical anomalies in HARP, including delayed, reordered and dropped messages and clock drift, and show how to extend HARP to multiple datacenters. Finally we implement HARP based on Cassandra, and the experiments show that HARP can effectively eliminate stale reads, with a low overhead (less than 6.9%) compared with original eventually consistent Cassandra.
|
Keywords
eventual consistency
high availability
data recency
stale read
|
Corresponding Author(s):
Xu WANG
|
Just Accepted Date: 16 June 2016
Online First Date: 05 December 2016
Issue Date: 11 January 2017
|
|
24 |
Bailis P, Ghodsi A. Eventual consistency today: limitations, extensions, and beyond. Queue, 2013, 11(3): 55–63
https://doi.org/10.1145/2447976.2447992
|
25 |
Lloyd W, Freedman M J, Kaminsky M, Andersen D G. Stronger semantics for low-latency geo-replicated storage. In: Proceedings of the USENIX Conference on Networked Systems Design and Implementation. 2013, 313–328
|
26 |
Du J, Iorgulescu C, Roy A, Zwaenepoel W. GentleRain: cheap and scalable causal consistency with physical clocks. ACM Symposium on Cloud Computing. 2014, 1–13
https://doi.org/10.1145/2670979.2670983
|
27 |
Bailis P, Davidson A, Fekete A, Ghodsi A, Hellerstein J M, Stoica I. Highly available transactions: virtues and limitations. In: Proceedings of International Conference on Very Large Data Bases. 2013, 181–192
https://doi.org/10.14778/2732232.2732237
|
1 |
DeCandia G, Hastorun D, Jampani M, Kakulapati G, Lakshman A, Pilchin A, Sivasubramanian S, Vosshall P, Vogels W. Dynamo: Amazon’s highly available key-value store. In: Proceedings of ACM Symposium on Operating Systems Principles. 2007, 205–220
https://doi.org/10.1145/1294261.1294281
|
2 |
Brewer E A. Towards robust distributed systems. In: Proceedings of the 19th ACM Symposium on Principles of Distributed Computing. 2000
|
28 |
Tang Y, Sun H L, Wang X, Liu X D. Harp: towards enhancing data recency for eventually consistent data stores. In: Proceedings of IEEE International Conference on Parallel and Distributed Systems. 2014, 685–692
https://doi.org/10.1109/padsw.2014.7097870
|
3 |
Abadi D. Consistency tradeoffs in modern distributed database system design: cap is only part of the story. IEEE Computer, 2012, 45(2): 37–42
https://doi.org/10.1109/MC.2012.33
|
4 |
Lakshman A, Malik P. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 2010, 44(2): 35–40
https://doi.org/10.1145/1773912.1773922
|
5 |
Vogels W. Eventually consistent. Communications of the ACM, 2009, 52(1): 14–19
https://doi.org/10.1145/1435417.1435432
|
6 |
Saito Y, Shapiro M. Optimistic replication. ACM Computing Surveys, 2005, 37(1): 42–81
https://doi.org/10.1145/1057977.1057980
|
7 |
Bailis P, Venkataraman S, Franklin M J, Hellerstein J M, Stoica I. Probabilistically bounded staleness for practical partial quorums. In: Proceedings of International Conference on Very Large Data Bases. 2012, 776–787
https://doi.org/10.14778/2212351.2212359
|
8 |
Bailis P, Venkataraman S, Franklin M J, Hellerstein J M, Stoica I. Quantifying eventual consistency with PBS. VLDB Journal, 2014, 23(2): 279–302
https://doi.org/10.1007/s00778-013-0330-1
|
9 |
Dcmers A, Greene D, Hauser C, Irish W, Larson J, Shenkcr S, Sturgis H, Swinehart D, Terry D. Epidemic algorithms for replicated database maintenance. In: Proceedings of ACM Symposium on Principles of Distributed Computing. 1987, 1–12
https://doi.org/10.1145/41840.41841
|
10 |
Cooper B F, Silberstein A, Tam E, Ramakrishnan R, Sears R. Benchmarking cloud serving systems with YCSB. In: Proceedings of ACM Symposium on Cloud Computing. 2010, 143–154
https://doi.org/10.1145/1807128.1807152
|
11 |
Herlihy M P, Wing J M. Linearizability: a correctness condition for concurrent objects. ACM Transactions on Programming Languages & Systems, 1990, 12(3): 463–492
https://doi.org/10.1145/78969.78972
|
12 |
Lamport L. On interprocess communication. Distributed Computing, 1986, 1(2): 86–101
https://doi.org/10.1007/BF01786228
|
13 |
Gilbert S, Lynch N. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant Web services. ACM SIGACT News, 2002, 33(2): 51–59
https://doi.org/10.1145/564585.564601
|
14 |
Mahajan P, Alvisi L, Dahlin M. Consistency, availability, convergence. Technical Report. 2011
|
15 |
Alpern B, Schneider F B. Recognizing safety and liveness. Distributed Computing, 1987, 2(3): 117–126
https://doi.org/10.1007/BF01782772
|
16 |
Lamport L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, 21(14): 558–565
https://doi.org/10.1145/359545.359563
|
17 |
Wang X, Sun H L, Deng T, Huai J D. A quantitative analysis of quorum system availability in data centers. In: Proceedings of the 22nd IEEE International Symposium on Quality of Service. 2014, 99–104
https://doi.org/10.1109/iwqos.2014.6914306
|
18 |
Ahamad M, Neiger G, Burns J E, Kohli P, Hutto P W. Causal memory: definitions, implementation, and programming. Distributed Computing, 1995, 9(1): 37–49
https://doi.org/10.1007/BF01784241
|
19 |
Bailis P, Ghodsi A, Hellerstein J M, Stoica I. Bolt-on causal consistency. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2013, 761–772
https://doi.org/10.1145/2463676.2465279
|
20 |
Lloyd W, Freedman M J, Kaminsky M, Andersen D G. Don’t settle for eventual: scalable causal consistency for wide-area storage with cops. In: Proceedings of ACMSymposium on Operating Systems Principles. 2011, 401–416
https://doi.org/10.1145/2043556.2043593
|
21 |
Davidson S B, Garcia-Molina H, Skeen D. Consistency in a partitioned network. ACM Computing Surveys, 1985, 17(3): 341–370
https://doi.org/10.1145/5505.5508
|
22 |
Dean J S. Designs, lessons and advice from building large distributed systems. In: Proceedings of the Workshop on Large-Scale Distributed Systems and Middleware. 2009
|
23 |
Gill P, Jain N, Nagappan N. Understanding network failures in data centers: measurement, analysis, and implications. In: Proceedings of ACM International Conference on the applications, technologies, architectures, and protocols for computer communication. 2011, 350–361
https://doi.org/10.1145/2018436.2018477
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|