Paper: CRDTs: Consistency without concurrency control
Thursday, December 23, 2010 at 8:12AM 
For a great Christmas read forget The Night Before Christmas, a heart warming poem written by Clement Moore for his children, that created the modern idea of Santa Clause we all know and anticipate each Christmas eve. Instead, curl up with a some potent eggnog, nog being any drink made with rum, and read CRDTs: Consistency without concurrency control by Mihai Letia, Nuno Preguiça, and Marc Shapiro, which talks about CRDTs (Commutative Replicated Data Type), a data type whose operations commute when they are concurrent.
From the introduction, which also serves as a nice concise overview of distributed consistency issues:
Shared read-only data is easy to scale by using well-understood replication techniques. However, sharing mutable data at a large scale is a difficult problem, because of the CAP impossibility result [5]. Two approaches dominate in practice. One ensures scalability by giving up consistency guarantees, for instance using the Last-Writer-Wins (LWW) approach [7]. The alternative guarantees consistency by serialising all updates, which does not scale beyond a small cluster [12]. Optimistic replication allows replicas to diverge, eventually resolving conflicts either by LWW-like methods or by serialisation [11].
In some (limited) cases, a radical simplification is possible. If concurrent updates to some datum commute, and all of its replicas execute all updates in causal order, then the replicas converge. We call this a Commutative Replicated Data Type (CRDT). The CRDT approach ensures that there are no conflicts, hence, no need for consensus-based concurrency control. CRDTs are not a universal solution, but, perhaps surprisingly, we were able to design highly useful CRDTs. This new research direction is promising as it ensures consistency in the large scale at a low cost, at least for some applications.
A trivial example of a CRDT is a set with a single add-element operation. A delete-element operation can be emulated by adding "deleted" elements to a second set. This suffices to implement a mailbox [1]. However, this is not practical, as the data structures grow without bound. A more interesting example is WOOT, a CRDT for concurrent editing [9], pioneering but inefficient, and its successor Logoot [13].
As an existence proof of non-trivial, useful, practical and ecient CRDT, we exhibit one that implements an ordered set with insert-at-position and delete operations. It is called Treedoc, because sequence elements are identified compactly using a naming tree, and because its first use was concurrent document editing [10]. Its design presents original solutions to scalability issues, namely restructuring the tree without violating commutativity, supporting very large and variable numbers of writable replicas, and leveraging the data structure to ensure causal ordering without vector clocks.
Another non-trivial CRDT that we developed (but we do not describe here) is a high-performance shared, distributed graph structure, the multilog [2]. While the advantages of commutativity are well documented, we are the first (to our knowledge) to address the design of CRDTs. In future work, we plan to explore what other interesting CRDTs may exist, and what are the theoretical and practical requirements for CRDTs.
May all your christmases be bright.
Related Articles
- Replication: Optimistic approaches by Yasushi Saito and Marc Shapiro.
- Designing a commutative replicated data type by Marc Shapiro and Nuno Preguiça.
Reader Comments (2)
Does anybody know of efforts to add CRDTs to a widely used data store? The paper appears to be purely academic. I would think that a real-world deployment via something like Cassandra would be a good next step to see what sorts of applications can actually fit this data model and how it really scales.
The fact that the problem is much easier to solve if the mutating operations are all commutative is hardly a new idea. I first heard this at a lecture by some Oracle guys about their master-master replication design, MANY years ago, I think in the 1970s but no fewer than 20 years ago.
It's related to lock compatibility matrices with commutative operations. See "Concurrency Control and Recovery in Database Systems", section 3.8. There was also work in Barbara Liskov's group about concurrency control on abstract datatypes that dealt with this concept.
And, as they say, only in limited cases are all operations commutative.