Yunhao Mao
ABSTRACT
Conflict-free replicated data types (CRDTs) are popular for optimistic replication and ensuring strong eventual consistency (SEC) in distributed systems. However, reversibility is an underdeveloped functionality for CRDTs, despite its usefulness in system restoration from an erroneous state or undoing unwanted operations. In this paper, we define the concept and design of reversible CRDTs (rCRDTs). Reverse operations compensate for the effect of reversed updates, and they extend existing CRDT interfaces. Three abstractions for reversibility are proposed: reversing a single update, multiple causally related updates, and multiple logically related updates that capture the user intention behind the updates. Moreover, a replicated and distributed key-value store, rKVCRDT, is implemented as a proof of concept that integrates the support of reversible CRDTs. The rCRDTs' evaluation show that although adding reversibility affects the system's performance, the end result depends on multiple factors and varies based on the underlying CRDTs. System designers must consider the trade-off between the benefit of reversibility and the performance impact.
- AntidoteDB. 2021. Antidote: A planet scale, highly available, transactional database built on CRDT technology. Retrieved July, 2021 from https://github.com/AntidoteDB/antidoteGoogle Scholar
- Peter Bailis, Alan Fekete, Michael J. Franklin, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2014. Coordination Avoidance in Database Systems. Proc. VLDB Endow. 8, 3 (Nov. 2014), 185--196. Google ScholarDigital Library
- Peter Bailis and Ali Ghodsi. 2013. Eventual Consistency Today: Limitations, Extensions, and Beyond. Commun. ACM 56, 5 (May 2013), 55--63. Google ScholarDigital Library
- Leemon Baird. 2016. The Swirlds Hashgraph Consensus Algorithm: Fair, fast, Byzantine Fault Tolerance. Retrieved May 2022 from https://eclass.upatras.gr/modules/document/file.php/CEID1175/Pool-of-Research-Papers%5B0%5D/31.HASH-GRAPH.pdfGoogle Scholar
- Valter Balegas, Diogo Serra, Sérgio Duarte, Carla Ferreira, Marc Shapiro, Rodrigo Rodrigues, and Nuno M. Preguiça. 2015. Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants. In 34th IEEE Symposium on Reliable Distributed Systems, SRDS 2015 (Montreal, QC, Canada). IEEE Computer Society, 31--36. Google ScholarDigital Library
- Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. 2014. Making Operation-Based CRDTs Operation-Based. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency (Amsterdam, The Netherlands) (PaPEC '14). Association for Computing Machinery, New York, NY, USA, Article 7, 2 pages. Google ScholarDigital Library
- Carlos Baquero, Paulo Sergio Almeida, and Ali Shoker. 2017. Pure Operation-Based Replicated Data Types. (2017). arXiv:1710.04469 Google ScholarCross Ref
- Annette Bieniusa, Marek Zawirski, Nuno Preguiça, Marc Shapiro, Carlos Baquero, Valter Balegas, and Sérgio Duarte. 2012. An optimized conflict-free replicated set. (2012). arXiv:1210.3368 Google ScholarCross Ref
- Peter Bourgon. 2014. Roshi: a CRDT system for timestamped events. Retrieved July 2021 from https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-eventsGoogle Scholar
- Eric Brewer. 2012. CAP twelve years later: How the "rules" have changed. Computer 45, 2 (Jan. 2012), 23--29. Google ScholarDigital Library
- Sebastian Burckhardt, Daan Leijen, Manuel Fähndrich, and Mooly Sagiv. 2012. Eventually Consistent Transactions. In Programming Languages and Systems - 21st European Symposium on Programming (Tallinn, Estonia) (ESOP 2012, Vol. 7211). Springer, 67--86. Google ScholarDigital Library
- Badrish Chandramouli, Guna Prasaad, Donald Kossmann, Justin Levandoski, James Hunter, and Mike Barnett. 2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In Proceedings of the 2018 International Conference on Management of Data (Houston, TX, USA) (SIGMOD '18). Association for Computing Machinery, New York, NY, USA, 275--290. Google ScholarDigital Library
- David Chen and Chengzheng Sun. 2001. Undoing Any Operation in Collaborative Graphics Editing Systems. In Proceedings of the 2001 International ACM SIGGROUP Conference on Supporting Group Work (Boulder, Colorado, USA) (GROUP '01). Association for Computing Machinery, New York, NY, USA, 197--206. Google ScholarDigital Library
- George Coulouris, Jean Dollimore, and Tim Kindberg. 2002. Distributed Systems - Concepts and Designs (3. ed.). Addison-Wesley-Longman.Google Scholar
- Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: Amazon's Highly Available Key-Value Store. In Proceedings of Twenty-First ACM SIGOPS Symposium on Operating Systems Principles (Stevenson, Washington, USA) (SOSP '07). Association for Computing Machinery, New York, NY, USA, 205--220. Google ScholarDigital Library
- Hector Garcia-Molina and Kenneth Salem. 1987. Sagas. In Proceedings of the 1987 ACM SIGMOD International Conference on Management of Data (San Francisco, California, USA) (SIGMOD '87). Association for Computing Machinery, New York, NY, USA, 249--259. Google ScholarDigital Library
- Kristof Jannes, Bert Lagaisse, and Wouter Joosen. 2021. OWebSync: Seamless Synchronization of Distributed Web Clients. IEEE Transactions on Parallel and Distributed Systems 32, 9 (March 2021), 2338--2351. Google ScholarCross Ref
- Kolbeinn Karlsson, Weitao Jiang, Stephen Wicker, Danny Adams, Edwin Ma, Robbert van Renesse, and Hakim Weatherspoon. 2018. Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things. In 38th International Conference on Distributed Computing Systems (Vienna, Austria) (ICDCS 2018). IEEE Computer Society, 1150--1158. Google ScholarCross Ref
- Martin Kleppmann. 2016. Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems. O'Reilly.Google Scholar
- Martin Kleppmann. 2022. Making CRDTs Byzantine Fault Tolerant. In Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed Data (Rennes, France) (PaPoC '22). Association for Computing Machinery, New York, NY, USA, 8--15. Google ScholarDigital Library
- Henry F. Korth, Eliezer Levy, and Abraham Silberschatz. 1990. A Formal Approach to Recovery by Compensating Transactions. In 16th International Conference on Very Large Data Bases (Brisbane, Queensland, Australia) (VLDB '90). Morgan Kaufmann, 95--106. http://www.vldb.org/conf/1990/P095.PDFGoogle ScholarDigital Library
- Xiao Lv, Fazhi He, Weiwei Cai, and Yuan Cheng. 2018. Supporting selective undo of string-wise operations for collaborative editing systems. Future Generation Computer Systems 82 (May 2018), 41--62. Google ScholarCross Ref
- Xiao Lv, Fazhi He, Yuan Cheng, and Yiqi Wu. 2018. A novel CRDT-based synchronization method for real-time collaborative CAD systems. Advanced Engineering Informatics 38 (Oct. 2018), 381--391. Google ScholarDigital Library
- Yunhao Mao. 2022. rKVCRDT. Retrieved June 2022 from https://github.com/MSRG/rKVCRDTGoogle Scholar
- Pezhman Nasirifard, Ruben Mayer, and Hans-Arno Jacobsen. 2019. FabricCRDT: A Conflict-Free Replicated Datatypes Approach to Permissioned Blockchains (Middleware '19). Association for Computing Machinery, New York, NY, USA, 110--122. Google ScholarDigital Library
- M. Tamer Özsu and Patrick Valduriez. 2020. Principles of Distributed Database Systems, 4th Edition. Springer. Google ScholarCross Ref
- Nuno M. Preguiça, Carlos Baquero, and Marc Shapiro. 2018. Conflict-free Replicated Data Types (CRDTs). (2018). arXiv:1805.06358 http://arxiv.org/abs/1805.06358Google Scholar
- Redis. 2021. Redis: Developing applications with Active-Active databases. Retrieved July, 2021 from https://docs.redis.com/latest/rs/databases/active-active/develop/data-types/Google Scholar
- Riak. 2021. NoSQL Key Value Database | Riak KV. Retrieved July, 2021 from https://riak.com/products/riak-kv/Google Scholar
- Yasushi Saito and Marc Shapiro. 2005. Optimistic Replication. ACM Comput. Surv. 37, 1 (March 2005), 42--81. Google ScholarDigital Library
- Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. A comprehensive study of Convergent and Commutative Replicated Data Types. Technical Report. Inria Centre Paris-Rocquencourt.Google Scholar
- Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In Stabilization, Safety, and Security of Distributed Systems - 13th International Symposium (Grenoble, France) (SSS 2011, Vol. 6976). Springer, 386--400. Google ScholarCross Ref
- Stéphane Weiss, Pascal Urso, and Pascal Molli. 2009. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 29th IEEE International Conference on Distributed Computing Systems (Montreal, QC, Canada) (ICDCS 2009). IEEE Computer Society, 404--412. Google ScholarDigital Library
- Chenggang Wu, Jose M. Faleiro, Yihan Lin, and Joseph M. Hellerstein. 2021. Anna: A KVS for Any Scale. IEEE Transactions on Knowledge and Data Engineering 33, 2 (Feb. 2021), 344--358. Google ScholarDigital Library
- Weihai Yu. 2014. Supporting String-Wise Operations and Selective Undo for Peer-to-Peer Group Editing. In Proceedings of the 18th International Conference on Supporting Group Work (Sanibel Island, Florida, USA) (GROUP '14). Association for Computing Machinery, New York, NY, USA, 226--237. Google ScholarDigital Library
- Weihai Yu, Victorien Elvinger, and Claudia-Lavinia Ignat. 2019. A Generic Undo Support for State-Based CRDTs. In 23rd International Conference on Principles of Distributed Systems (Neuchâtel, Switzerland) (OPODIS 2019, Vol. 153). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 14:1--14:17. Google ScholarCross Ref
Index Terms
- Reversible conflict-free replicated data types
Recommendations
Abstraction for conflict-free replicated data types
PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and ImplementationStrong eventual consistency (SEC) has been used as a classic notion of correctness for Conflict-Free Replicated Data Types (CRDTs). However, it does not give proper abstractions of functionality, thus is not helpful for modular verification of client ...
Conflict-free replicated data types
SSS'11: Proceedings of the 13th international conference on Stabilization, safety, and security of distributed systemsReplicating data under Eventual Consistency (EC) allows any replica to accept updates without remote synchronisation. This ensures performance and scalability in large-scale distributed systems (e.g., clouds). However, published EC approaches are ad-hoc ...
Replicated data types: specification, verification, optimality
POPL '14: Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming LanguagesGeographically distributed systems often rely on replicated eventually consistent data stores to achieve availability and performance. To resolve conflicting updates at different replicas, researchers and practitioners have proposed specialized ...
Comments