Abstract
Data replication results in a fundamental trade-off between operation latency and consistency. At the weak end of the spectrum of possible consistency models is eventual consistency, which provides no limit to the staleness of data returned. However, anecdotally, eventual consistency is often "good enough" for practitioners given its latency and availability benefits. In this work, we explain this phenomenon and demonstrate that, despite their weak guarantees, eventually consistent systems regularly return consistent data while providing lower latency than their strongly consistent counterparts. To quantify the behavior of eventually consistent stores, we introduce Probabilistically Bounded Staleness (PBS), a consistency model that provides expected bounds on data staleness with respect to both versions and wall clock time. We derive a closed-form solution for version-based staleness and model real-time staleness for a large class of quorum replicated, Dynamo-style stores. Using PBS, we measure the trade-off between latency and consistency for partial, non-overlapping quorum systems under Internet production workloads. We quantitatively demonstrate how and why eventually consistent systems frequently return consistent data within tens of milliseconds while offering large latency benefits.
- Abadi, D.J. Consistency tradeoffs in modern distributed database system design: CAP is only part of the story. IEEE Comput. 45, 2 (2012), 37--42. Google ScholarDigital Library
- Aiyer, A., Alvisi, L., Bazzi, R.A. On the availability of non-strict quorum systems. In DISC 2005. Google ScholarDigital Library
- Aiyer, A.S., Alvisi, L., Bazzi, R.A. Byzantine and multi-writer k-quorums. In DISC (2006), 443--458. Google ScholarDigital Library
- Bailis, P., Ghodsi, A. Eventual consistency today: Limitations, extensions, and beyond. ACM Queue 11, 3 (Mar. 2013), 20:20--20:32. Google ScholarDigital Library
- Bailis, P., Venkataraman, S., Franklin, M.J., Hellerstein, J.M., Stoica, I. Probabilistically bounded staleness for practical partial quorums. PVLDB 5, 8 (2012), 776--787. Google ScholarDigital Library
- Bailis, P., Venkataraman, S., Franklin, M.J., Hellerstein, J.M., Stoica, I. PBS at work: Advancing data management with consistency metrics. In SIGMOD 2013 Demo. Google ScholarDigital Library
- Bailis, P., Venkataraman, S., Franklin, M.J., Hellerstein, J.M., Stoica, I. Quantifying eventual consistency with PBS. VLDB J. (2014). (see http://link.springer.com/article/10.1007/s00778-013-0330-1).Google Scholar
- Cooper, B.F., Ramakrishnan, R., Srivastava, U., Silberstein, A., Bohannon, P., Jacobsen, H.A., Puz, N., Weaver, D., Yerneni, R. Pnuts: Yahoo!'s hosted data serving platform. In VLDB 2008. Google ScholarDigital Library
- Davidson, S., Garcia-Moina, H., Skeen, D. Consistency in partitioned networks. ACM Comput. Surv. 17, 3 (1985), 314--370. Google ScholarDigital Library
- 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 SOSP 2007, 205--220. Google ScholarDigital Library
- Golab, W., Li, X., Shah, M.A. Analyzing consistency properties for fun and profit. In PODC (2011), 197--206. Google ScholarDigital Library
- Hamilton, J. Perspectives: I love eventual consistency but… http://perspectives.mvdirona.com/2010/02/24/ILoveEventualConsistencyBut.aspx (24 Feb. 2010).Google Scholar
- Herlihy, M., Wing, J.M. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12, 3 (1990), 463--492. Google ScholarDigital Library
- Kirkell, J. Consistency or bust: Breaking a Riak cluster. http://www.oscon.com/oscon2011/public/schedule/detail/19762. Talk at O'Reilly OSCON 2011 (27 Jul. 2011).Google Scholar
- Linden, G. Make data useful. https://sites.google.com/site/glinden/Home/StanfordDataMining.2006-11-29.ppt (29 Nov. 2006).Google Scholar
- Linden, G. Marissa Mayer at Web 2.0. http://glinden.blogspot.com/2006/11/marissa-mayer-at-web-20.html (9 Nov. 2006).Google Scholar
- Lloyd, W., Freedman, M.J., Kaminsky, M., Andersen, D.G. Stronger semantics for low-latency geo-replicated storage. In NSDI 2013. Google ScholarDigital Library
- Mahajan, P., Alvisi, L., Dahlin, M. Consistency, Availability, Convergence. Technical Report TR-11-22, Computer Science Department, University of Texas at Austin, 2011.Google Scholar
- Malkhi, D., Reiter, M., Wool, A., Wright, R. Probabilistic quorum systems. Inform. Commun. 170 (2001), 184--206. Google ScholarDigital Library
- Merideth, M., Reiter, M. Selected results from the latest decade of quorum systems research. In Replication, B. Charron-Bost, F. Pedone, and A. Schiper, eds. Volume 5959 of LNCS (2010). Springer, 185--206. Google ScholarDigital Library
- Rahman, M., Golab, W., AuYoung, A., Keeton, K., Wylie, J. Toward a principled framework for benchmarking consistency. In Proceedings of the 8th Workshop on Hot Topics in System Dependability (Hollywood, CA, 2012), USENIX. Google ScholarDigital Library
- Schurman, E., Brutlag, J. Performance related changes and their user impact. Presented at Velocity Web Performance and Operations Conference (San Jose, CA, Jun. 2009).Google Scholar
- Sovran, Y., Power, R., Aguilera, M.K., Li, J. Transactional storage for geo-replicated systems. In SOSP 2011. Google ScholarDigital Library
- Stonebraker, M. Urban myths about SQL. http://voltdb.com/_pdf/VoltDB-MikeStonebrakerSQLMythsWebinar-060310.pdf. VoltDB Webinar (Jun. 2010).Google Scholar
- Terry, D.B., Demers, A.J., Petersen, K., Spreitzer, M.J., Theimer, M.M., Welch, B.B. Session guarantees for weakly consistent replicated data. In PDIS 1994. Google ScholarDigital Library
- Vogels, W. Eventually consistent. CACM 52 (2009), 40--44. Google ScholarDigital Library
- Yu, H., Vahdat, A. Design and evaluation of a conit-based continuous consistency model for replicated services. ACM Trans. Comput. Syst. 20, 3 (2002), 239--282. Google ScholarDigital Library
Index Terms
- Quantifying eventual consistency with PBS
Recommendations
Constraining the eventual in eventual consistency
PaPoC '18: Proceedings of the 5th Workshop on the Principles and Practice of Consistency for Distributed DataCRDTs are highly available replicated data structures which offer strong eventual consistency in the face of concurrent operations [3]. By their definition, CRDTs eventually converge to a consistent state given enough time. However, this is not strict ...
On Mixing Eventual and Strong Consistency: Acute Cloud Types
In this article we study the properties of distributed systems that mix eventual and strong consistency. We formalize such systems through <italic>acute cloud types</italic> (ACTs), abstractions similar to conflict-free replicated data types (CRDTs), ...
The Weakest Failure Detector for Eventual Consistency
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingIn its classical form, a consistent replicated service requires all replicas to witness the same evolution of the service state. Assuming a message-passing environment with a majority of correct processes, the necessary and sufficient information about ...
Comments