Marek Zawirski
Marc Shapiro
ABSTRACT
Client-side apps (e.g., mobile or in-browser) need cloud data to be available in a local cache, for both reads and updates. For optimal user experience and developer support, the cache should be consistent and fault-tolerant. In order to scale to high numbers of unreliable and resource-poor clients, and large database, the system needs to use resources sparingly. The SwiftCloud distributed object database is the first to provide fast reads and writes via a causally-consistent client-side local cache backed by the cloud. It is thrifty in resources and scales well, thanks to consistent versioning provided by the cloud, using small and bounded metadata. It remains available during faults, switching to a different data centre when the current one is not responsive, while maintaining its consistency guarantees. This paper presents the SwiftCloud algorithms, design, and experimental evaluation. It shows that client-side apps enjoy the high performance and availability, under the same guarantees as a remote cloud data store, at a small cost.
- Introducing Riak 2.0: Data types, strong consistency, full-text search, and much more, Oct. 2013. URL http://basho.com/introducing-riak-2-0/.Google Scholar
- M. Ahamad, G. Neiger, J. E. Burns, P. Kohli, and P. W. Hutto. Causal memory: definitions, implementation, and programming. Distributed Computing, 9(1):37--49, Mar. 1995.Google ScholarDigital Library
- S. Almeida, J. Leitão, and L. Rodrigues. ChainReaction: a causal+ consistent datastore based on Chain Replication. In Euro. Conf. on Comp. Sys. (EuroSys), Apr. 2013. Google ScholarDigital Library
- H. Attiya, F. Ellen, and A. Morrison. Limitations of highly-available eventually-consistent data stores. In Symp. on Principles of Dist. Comp. (PODC), pages 385--394. ACM, 2015. Google ScholarDigital Library
- P. Bailis, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Bolt-on causal consistency. In Int. Conf. on the Mgt. of Data (SIGMOD), pages 761--772, New York, NY, USA, 2013. Google ScholarDigital Library
- P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica. Highly Available Transactions: Virtues and limitations. In Int. Conf. on Very Large Data Bases (VLDB), Riva del Garda, Trento, Italy, 2014. Google ScholarDigital Library
- V. Balegas, N. Preguiça, R. Rodrigues, S. Duarte, C. Ferreira, M. Najafzadeh, and M. Shapiro. Putting the consistency back into eventual consistency. In Euro. Conf. on Comp. Sys. (EuroSys), Bordeaux, France, Apr. 2015. Google ScholarDigital Library
- N. Belaramani, M. Dahlin, L. Gao, A. Nayate, A. Venkataramani, P. Yalagandula, and J. Zheng. PRACTI replication. In Networked Sys. Design and Implem. (NSDI), pages 59--72, San Jose, CA, USA, May 2006. Usenix. Google ScholarDigital Library
- F. Benevenuto, T. Rodrigues, M. Cha, and V. Almeida. Characterizing user behavior in online social networks. In Internet Measurement Conference (IMC), 2009. Google ScholarDigital Library
- S. Burckhardt. Bringing TouchDevelop to the cloud. Inside Microsoft Research Blog, Oct. 2013. URL http://blogs.technet.com/b/inside_microsoft_research/archive/2013/10/28/bringing-touchdevelop-to-the-cloud.aspx.Google Scholar
- S. Burckhardt, A. Gotsman, H. Yang, and M. Zawirski. Replicated data types: Specification, verification, optimality. In Symp. on Principles of Prog. Lang. (POPL), pages 271--284, San Diego, CA, USA, Jan. 2014. Google ScholarDigital Library
- B. Cairns. Build collaborative apps with Google Drive Realtime API. Google Apps Developers Blog, Mar. 2013. URL http://googleappsdeveloper.blogspot.com/2013/03/build-collaborative-apps-with-google.html.Google Scholar
- B.-G. Chun, C. Curino, R. Sears, A. Shraer, S. Madden, and R. Ramakrishnan. Mobius: Unified messaging and data serving for mobile apps. In Int. Conf. on Mobile Sys., Apps. and Services (MobiSys), pages 141--154, New York, NY, USA, 2012. Google ScholarDigital Library
- B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears. Benchmarking cloud serving systems with YCSB. In Symp. on Cloud Computing, pages 143--154, Indianapolis, IN, USA, 2010. Google ScholarDigital Library
- J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's globally-distributed database. In Symp. on Op. Sys. Design and Implementation (OSDI), pages 251--264, Hollywood, CA, USA, Oct. 2012. Usenix. 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 Symp. on Op. Sys. Principles (SOSP), volume 41 of Operating Systems Review, pages 205--220, Stevenson, Washington, USA, Oct. 2007. Assoc. for Computing Machinery. Google ScholarDigital Library
- J. Du, S. Elnikety, A. Roy, and W. Zwaenepoel. Orbe: Scalable causal consistency using dependency matrices and physical clocks. In Symp. on Cloud Computing, pages 11:1--11:14, Santa Clara, CA, USA, Oct. 2013. Assoc. for Computing Machinery. Google ScholarDigital Library
- J. Du, C. Iorgulescu, A. Roy, and W. Zwaenepoel. GentleRain: Cheap and scalable causal consistency with physical clocks. In Symp. on Cloud Computing, 2014. Google ScholarDigital Library
- R. Friedman and K. Birman. Trading consistency for availability in distributed systems. Technical Report TR96-1579, Cornell U., Computer Sc., Ithaca NY, USA, Apr. 1996. Google ScholarDigital Library
- S. Gilbert and N. Lynch. Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News, 33(2):51--59, 2002. Google ScholarDigital Library
- P. R. Johnson and R. H. Thomas. The maintenance of duplicate databases. Internet Request for Comments RFC 677, Information Sciences Institute, Jan. 1976. Google ScholarDigital Library
- A. Kansal, B. Urgaonkar, and S. Govindan. Using dark fiber to displace diesel generators. In Hot Topics in Operating Systems, Santa Ana Pueblo, NM, USA, 2013. Google ScholarDigital Library
- R. Ladin, B. Liskov, and L. Shrira. Lazy replication: Exploiting the semantics of distributed services. Operating Systems Review, 25(1):49--55, Jan. 1991. Google ScholarDigital Library
- C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. Making geo-replicated systems fast as possible, consistent when necessary. In Symp. on Op. Sys. Design and Implementation (OSDI), pages 265-- 278, Hollywood, CA, USA, Oct. 2012. Google ScholarDigital Library
- W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Don't settle for eventual: scalable causal consistency for wide-area storage with COPS. In Symp. on Op. Sys. Principles (SOSP), pages 401--416, Cascais, Portugal, Oct. 2011. Assoc. for Computing Machinery. Google ScholarDigital Library
- W. Lloyd, M. J. Freedman, M. Kaminsky, and D. G. Andersen. Stronger semantics for low-latency geo-replicated storage. In Networked Sys. Design and Implem. (NSDI), pages 313--328, Lombard, IL, USA, Apr. 2013. Google ScholarDigital Library
- P. Mahajan, L. Alvisi, and M. Dahlin. Consistency, availability, and convergence. Technical Report UTCS TR-11-22, Dept. of Comp. Sc., The U. of Texas at Austin, Austin, TX, USA, 2011.Google Scholar
- P. Mahajan, S. Setty, S. Lee, A. Clement, L. Alvisi, M. Dahlin, and M. Walfish. Depot: Cloud storage with minimal trust. Trans. on Computer Systems, 29(4): 12:1--12:38, Dec. 2011. Google ScholarDigital Library
- K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible update propagation for weakly consistent replication. In Symp. on Op. Sys. Principles (SOSP), pages 288--301, Saint Malo, Oct. 1997. ACM SIGOPS. Google ScholarDigital Library
- Redis. An open source key-value store. http://redis.io/, May 2014.Google Scholar
- N. Schiper, P. Sutra, and F. Pedone. P-Store: Genuine partial replication in wide area networks. In Symp. on Reliable Dist. Sys. (SRDS), pages 214--224, New Dehli, India, Oct. 2010. IEEE Comp. Society. Google ScholarDigital Library
- M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. A comprehensive study of Convergent and Commutative Replicated Data Types. Rapp. de Recherche 7506, Institut National de la Recherche en Informatique et Automatique (Inria), Rocquencourt, France, Jan. 2011.Google Scholar
- M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In X. Défago, F. Petit, and V. Villain, editors, Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 6976 of Lecture Notes in Comp. Sc., pages 386--400, Grenoble, France, Oct. 2011. Springer-Verlag. Google ScholarDigital Library
- Y. Sovran, R. Power, M. K. Aguilera, and J. Li. Transactional storage for geo-replicated systems. In Symp. on Op. Sys. Principles (SOSP), pages 385--400, Cascais, Portugal, Oct. 2011. Assoc. for Computing Machinery. Google ScholarDigital Library
- D. B. Terry, A. J. Demers, K. Petersen, M. J. Spreitzer, M. M. Theimer, and B. B. Welch. Session guarantees for weakly consistent replicated data. In Int. Conf. on Para. and Dist. Info. Sys. (PDIS), pages 140--149, Austin, Texas, USA, Sept. 1994. Google ScholarDigital Library
- M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, and M. Shapiro. Write fast, read in the past: Causal consistency for client-side applications. Rapp. de Recherche RR-8729, Institut National de la Recherche en Informatique et Automatique (Inria), Rocquencourt, France, May 2015.Google Scholar
Index Terms
- Write Fast, Read in the Past: Causal Consistency for Client-Side Applications
Recommendations
Bolt-on causal consistency
SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of DataWe consider the problem of separating consistency-related safety properties from availability and durability in distributed data stores via the application of a "bolt-on" shim layer that upgrades the safety of an underlying general-purpose data store. ...
Limitations of Highly-Available Eventually-Consistent Data Stores
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed ComputingModern replicated data stores aim to provide high availability, by immediately responding to client requests, often by implementing objects that expose concurrency. Such objects, for example, multi-valued registers (MVRs), do not have sequential ...
GentleRain: Cheap and Scalable Causal Consistency with Physical Clocks
SOCC '14: Proceedings of the ACM Symposium on Cloud ComputingGentleRain is a new causally consistent geo-replicated data store that provides throughput comparable to eventual consistency and superior to current implementations of causal consistency.
GentleRain uses a periodic aggregation protocol to determine ...
Comments