ABSTRACT
Over the last few years, Cloud storage systems and so-called NoSQL datastores have found widespread adoption. In contrast to traditional databases, these storage systems typically sacrifice consistency in favor of latency and availability as mandated by the CAP theorem, so that they only guarantee eventual consistency. Existing approaches to benchmark these storage systems typically omit the consistency dimension or did not investigate eventuality of consistency guarantees. In this work we present a novel approach to benchmark staleness in distributed datastores and use the approach to evaluate Amazon's Simple Storage Service (S3). We report on our unexpected findings.
- E. Anderson, X. Li, M. Shah, J. Tucek, and J. Wylie. What consistency does your key-value store actually provide. In Proceedings of the Sixth Workshop on Hot Topics in System Dependability (HotDep), 2010. Google ScholarDigital Library
- R. Baldoni, A. Corsaro, L. Querzoni, S. Scipioni, and S. Tucci-Piergiovanni. An adaptive coupling-based algorithm for internal clock synchronization of large scale dynamic systems. In Proceedings of the 2007 OTM Confederated international conference on On the move to meaningful internet systems-Volume Part I, pages 701--716. Springer-Verlag, 2007. Google ScholarDigital Library
- D. Bermbach, M. Klems, M. Menzel, and S. Tai. Metastorage: A federated cloud storage system to manage consistency-latency tradeoffs. In Proceedings of the 4th International Conference on Cloud Computing (IEEE Cloud 2011). IEEE, 2011. Google ScholarDigital Library
- B. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H. Jacobsen, N. Puz, D. Weaver, and R. Yerneni. PNUTS: Yahoo!'s hosted data serving platform. Proceedings of the VLDB Endowment, 1(2):1277--1288, 2008. Google ScholarDigital Library
- B. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with ycsb. In Proceedings of the 1st ACM symposium on Cloud computing, pages 143--154. ACM, 2010. Google ScholarDigital Library
- G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: amazon's highly available key-value store. In Proc. SOSP, 2007. Google ScholarDigital Library
- A. Fox and E. Brewer. Harvest, yield, and scalable tolerant systems. In Proceedings of the 7th Workshop on Hot Topics in Operating Systems, 1999, pages 174--178. IEEE, 2002. Google ScholarDigital Library
- S. Ghemawat, H. Gobioff, and S. Leung. The Google file system. ACM SIGOPS Operating Systems Review, 37(5):29--43, 2003. Google ScholarDigital Library
- M. Klems, M. Menzel, and R. Fischer. Consistency benchmarking: Evaluating the consistency behavior of middleware services in the cloud. In Proceedings of the 8th International Conference on Service Oriented Computing (ICSOC). Springer, Dec. 2010.Google ScholarCross Ref
- D. Kossmann, T. Kraska, and S. Loesing. An evaluation of alternative architectures for transaction processing in the cloud. In Proceedings of the 2010 international conference on Management of data, pages 579--590. ACM, 2010. Google ScholarDigital Library
- T. Kraska, M. Hentschel, G. Alonso, and D. Kossmann. Consistency Rationing in the Cloud: Pay only when it matters. Proceedings of the VLDB Endowment, 2(1):253--264, 2009. Google ScholarDigital Library
- J. Kubiatowicz, D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, C. Wells, et al. Oceanstore: An architecture for global-scale persistent storage. ACM SIGARCH Computer Architecture News, 28(5):190--201, 2000. Google ScholarDigital Library
- A. Lakshman and P. Malik. Cassandra: a decentralized structured storage system. ACM SIGOPS Operating Systems Review, 44(2):35--40, 2010. Google ScholarDigital Library
- M. Menzel, M. Schoenherr, and S. Tai. (mc2)2: criteria, requirements and a software prototype for cloud infrastructure decisions. Software: Practice and Experience, 2011.Google Scholar
- ntp.org. NTP Algorithm. http://www.ntp.org/ntpfaq/NTP-s-algo.htm (accessed on September 6, 2011).Google Scholar
- S. Sakr, L. Zhao, H. Wada, and A. Liu. Clouddb autoadmin: Towards a truly elastic cloud-based data store. In The 9th IEEE International Conference on Web Services (ICWS 2011), Washington DC, USA, July 2011. Google ScholarDigital Library
- M. Satyanarayanan, J. Kistler, P. Kumar, M. Okasaki, E. Siegel, and D. Steere. Coda: A highly available file system for a distributed workstation environment. IEEE Transactions on computers, pages 447--459, 1990. Google ScholarDigital Library
- A. S. Tanenbaum and M. V. Steen. Distributed Systems - Principles and Paradigms. Pearson Education, Upper Saddle River, NJ, 2nd edition, 2007. Google ScholarDigital Library
- D. Terry, M. Theimer, K. Petersen, A. Demers, M. Spreitzer, and C. Hauser. Managing update conflicts in Bayou, a weakly connected replicated storage system. ACM SIGOPS Operating Systems Review, 29(5):172--182, 1995. Google ScholarDigital Library
- W. Vogels. Eventually consistent. Queue, 6:14--19, October 2008. Google ScholarDigital Library
- H. Wada, A. Fekete, L. Zhao, K. Lee, and A. Liu. Data consistency properties and the trade offs in commercial cloud storages: the consumers' perspective. In 5th biennial Conference on Innovative Data Systems Research, CIDR, volume 11, 2011.Google Scholar
- H. Yu and A. Vahdat. Design and evaluation of a conit-based continuous consistency model for replicated services. ACM Transactions on Computer Systems (TOCS), 20(3):239--282, 2002. Google ScholarDigital Library
- L. Zhao, A. Liu, and J. Keung. Evaluating cloud platform architecture with the care framework. In 2010 Asia Pacific Software Engineering Conference, pages 60--69. IEEE, 2010. Google ScholarDigital Library
Index Terms
- Eventual consistency: How soon is eventual? An evaluation of Amazon S3's consistency behavior
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 ...
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 ...
Eventual Consistency Formalized
System Analysis and Modeling. Languages, Methods, and Tools for Industry 4.0AbstractDistribution of computation is well-known, and there are several frameworks, including some formal frameworks, that capture distributed computation. As yet, however, models of distributed computation are based on the idea that data is conceptually ...
Comments