Conflict-free replicated data type
In our increasingly interconnected world, where data is constantly being updated across many devices and servers, ensuring everyone sees the correct information can be a monumental challenge. Traditional methods often grind to a halt waiting for perfect synchronization, but what if data could be updated independently, even offline, and still gracefully resolve conflicts on its own? This is where Conflict-free Replicated Data Types, or CRDTs, step in, offering a clever solution to a fundamental problem in distributed computing. CRDTs allow multiple copies of data to be updated independently and concurrently across a network without needing central coordination, always guaranteeing eventual consistency. There are two main categories of CRDTs, state-based and operation-based, each with distinct communication patterns and trade-offs in complexity and bandwidth. A wide variety of CRDTs exist for common data structures like counters, sets, and lists, enabling robust real-time collaboration and distributed database systems in major applications.
AI Summary
In our increasingly interconnected world, where data is constantly being updated across many devices and servers, ensuring everyone sees the correct information can be a monumental challenge. Traditional methods often grind to a halt waiting for perfect synchronization, but what if data could be updated independently, even offline, and still gracefully resolve conflicts on its own? This is where Conflict-free Replicated Data Types, or CRDTs, step in, offering a clever solution to a fundamental problem in distributed computing.
- CRDTs allow multiple copies of data to be updated independently and concurrently across a network without needing central coordination, always guaranteeing eventual consistency.
- There are two main categories of CRDTs, state-based and operation-based, each with distinct communication patterns and trade-offs in complexity and bandwidth.
- A wide variety of CRDTs exist for common data structures like counters, sets, and lists, enabling robust real-time collaboration and distributed database systems in major applications.
The Challenge of Distributed Data
Imagine a shared document or a shopping cart on an e-commerce site. In a distributed system, copies of this data might live on many different servers or even your own device. When multiple people try to update these copies at the same time, traditional systems often struggle with inconsistencies, leading to lost data or errors.
The core problem is how to handle concurrent updates without forcing everyone to wait for a central authority to synchronize every single change. This is especially tricky when network connections are unreliable or devices are offline, leading to what's known as 'eventual consistency' — the idea that all replicas will eventually become consistent, but might differ for a while.
Introducing Conflict-free Replicated Data Types
A Conflict-free Replicated Data Type, or CRDT, is a special kind of data structure designed for distributed systems. The magic of CRDTs lies in their inherent ability to allow independent, concurrent updates across multiple replicas without any upfront coordination. Even if conflicts arise, the data type itself contains an algorithm to automatically resolve them.
This means that while different replicas of a CRDT might temporarily show different states, they are mathematically guaranteed to eventually converge to the same correct state. This property, known as 'strong eventual consistency,' is incredibly powerful for building robust and responsive distributed applications.
The concept was formally defined in 2011, born from the needs of collaborative text editing and mobile computing. Today, CRDTs power online chat, gaming platforms, music services like SoundCloud, and even major NoSQL databases like Redis and Riak, where high availability and responsiveness are paramount.
A Simple Example: The Boolean Event Flag
To grasp the core idea, consider a simple 'event flag' — a Boolean value that starts at false. If an event occurs, the flag is set to true. Once true, it can never revert to false because an event cannot 'un-occur.' This is a trivial CRDT.
If one replica sees the event and sets its flag to true, while another hasn't seen it and keeps its flag false, how do they merge? The rule is simple: 'true wins'. The resolved result is true, because the event did happen somewhere. This merge function ensures consistency without losing information.
Two Paths to Consistency: State-Based vs. Operation-Based
There are two fundamental approaches to building CRDTs, both achieving strong eventual consistency: state-based CRDTs and operation-based CRDTs. They differ primarily in what information they transmit between replicas to achieve convergence.
State-based CRDTs (CvRDTs)
State-based CRDTs work by sending their entire local state to other replicas whenever an update occurs. When a replica receives a new state, it merges it with its own local state using a special merge function. This function must be commutative, associative, and idempotent.
These mathematical properties mean that the order in which replicas receive updates doesn't matter, nor does receiving the same update multiple times. The merge function computes the 'join' of states, ensuring a monotonic increase in information. This forms what's known as a semilattice structure, where every merge operation moves towards a 'more complete' state.
Essentially, state-based CRDTs broadcast their current 'knowledge' of the data. The only requirement for communication is a reliable way to eventually transmit states to all other replicas, often using simple gossip protocols.
\text{state}_{new} = \text{merge}(\text{state}_{local}, \text{state}_{remote})A clever optimization, called Delta CRDTs, only transmits the changes (deltas) to the state, rather than the entire state, significantly reducing bandwidth while retaining the robust properties of state-based CRDTs.
Operation-based CRDTs (CmRDTs)
In contrast, operation-based CRDTs don't send full states. Instead, they directly transmit the update operations themselves to other replicas. For example, a counter might broadcast an 'increment by 10' operation rather than its new value.
Like state-based CRDTs, the application of these operations must be commutative and associative. However, operation-based CRDTs typically require stronger guarantees from the communication layer — specifically, that operations are delivered exactly once and in causal order to all replicas.
Comparing the Approaches
While theoretically equivalent, state-based and operation-based CRDTs have practical differences. State-based CRDTs are generally simpler to implement, relying only on a gossip protocol to eventually propagate full states. Their downside can be high bandwidth usage if states are large.
Operation-based CRDTs are more bandwidth-efficient for frequently updated, small changes, as they only send the operations. But this efficiency comes at the cost of more complex communication middleware, which must ensure reliable, ordered, and non-duplicated delivery of operations.
Common CRDT Implementations
G-Counter (Grow-only Counter)
A G-Counter is a simple, state-based counter that only allows increments. Each node in the distributed system has its own counter, often an element in an array. When merging, the value for each element in the array is simply the maximum of the corresponding elements from the merging counters. It ensures that the counter only ever 'grows'.
PN-Counter (Positive-Negative Counter)
Need to both increment and decrement? The PN-Counter cleverly combines two G-Counters: one for positive increments (P) and one for negative decrements (N). The actual value of the PN-Counter is then P minus N. Merging simply means merging the two underlying G-Counters independently.
G-Set (Grow-only Set)
The G-Set is a set that only allows elements to be added — never removed. If an element is added once, it's there forever. Merging two G-Sets simply involves taking their union. This is useful for tracking things like 'users who have viewed this page'.
2P-Set (Two-Phase Set)
To allow removals, the 2P-Set uses two G-Sets: an 'add set' and a 'remove set' (often called a 'tombstone set'). An element is considered present if it's in the add set and not in the remove set. Once an element is added to the remove set, it can never be re-added. This is 'remove-wins' semantics.
LWW-Element-Set (Last-Write-Wins-Element-Set)
The LWW-Element-Set improves upon the 2P-Set by allowing elements to be reinserted after removal. It also uses 'add' and 'remove' sets, but crucially, each element in these sets comes with a timestamp. An element is present if its latest add timestamp is more recent than its latest remove timestamp. If timestamps are equal, a 'bias' (e.g., add-wins or remove-wins) breaks the tie.
OR-Set (Observed-Remove Set)
The OR-Set takes a different approach to reinsertions by using unique 'tags' instead of timestamps. Each element stores lists of 'add-tags' and 'remove-tags'. An element is considered in the set if its add-tag list contains any tags not present in its remove-tag list. This allows for very fine-grained tracking of additions and removals.
Sequence CRDTs
Perhaps one of the most complex yet impactful applications of CRDTs is in building 'sequence' CRDTs. These are specialized CRDTs for ordered data like lists or strings, which are essential for collaborative real-time editors, where multiple users are typing and reordering content simultaneously. They offer a robust alternative to older methods like Operational Transformation (OT).
Implementations like Yjs CRDT have shown how to build highly performant, real-time collaborative editors that can handle complex scenarios, even with users working offline and merging their changes later without any lost work.
CRDTs in the Wild: Industry Adoption
CRDTs are no longer just an academic curiosity; they are a cornerstone of modern distributed systems. Microsoft's Fluid Framework, for example, is an open-source platform built on CRDTs to enable real-time web applications, from collaborative documents to shared whiteboards.
The popular note-taking app Nimbus Note uses Yjs CRDT for its collaborative editing features. Redis, a widely used in-memory database, includes CRDT-enabled database features for high availability. SoundCloud even open-sourced Roshi, a custom LWW-element-set CRDT built on Redis to manage its massive audio stream.
Riak, a distributed NoSQL database, heavily leverages CRDTs. It's used by companies like League of Legends for their in-game chat system, supporting millions of concurrent users and thousands of messages per second. Bet365 also relies on Riak's OR-Set implementation for storing large volumes of critical betting data.
Beyond these, companies like TomTom use CRDTs to synchronize navigation data across devices, and even Apple's Notes app implements CRDTs to seamlessly sync offline edits between multiple Apple devices. CRDTs are quietly powering much of the real-time, resilient, and collaborative digital experiences we use every day.
Article
Conflict-free replicated data type
In distributed computing, a conflict-free replicated data type (CRDT) is a data structure that is replicated across multiple computers in a network, with the following features:
• The application can update any replica independently, concurrently and without coordinating with other replicas. • An algorithm (itself part of the data type) automatically resolves any inconsistencies that might occur. • Although replicas may have different state at any particular point in time, they are guaranteed to eventually converge.
The CRDT concept was formally defined in 2011 by Marc Shapiro, Nuno Preguiça, Carlos Baquero and Marek Zawirski. Development was initially motivated by collaborative text editing and mobile computing. CRDTs have also been used in online chat systems, online gambling, and in the SoundCloud audio distribution platform. The NoSQL distributed databases Redis, Riak and Cosmos DB have CRDT data types.
Background
Conflict-free replicated data type
Concurrent updates to multiple replicas of the same data, without coordination between the computers hosting the replicas, can result in inconsistencies between the replicas, which in the general case may not be resolvable. Restoring consistency and data integrity when there are conflicts between updates may require some or all of the updates to be entirely or partially dropped.
Accordingly, much of distributed computing focuses on the problem of how to prevent concurrent updates to replicated data. But another possible approach is optimistic replication, where all concurrent updates are allowed to go through, with inconsistencies possibly created, and the results are merged or "resolved" later. In this approach, consistency between the replicas is eventually re-established via "merges" of differing replicas. While optimistic replication might not work in the general case, there is a significant and practically useful class of data structures, CRDTs, where it does work — where it is always possible to merge or resolve concurrent updates on different replicas of the data structure without conflicts. This makes CRDTs ideal for optimistic replication.
As an example, a one-way boolean event flag is a trivial CRDT: one bit, with a value of true or false. True means some particular event has occurred at least once. False means the event has not occurred. Once set to true, the flag cannot be set back to false (an event having occurred cannot un-occur). The resolution method is "true wins": when merging a replica where the flag is true (that replica has observed the event), and another one where the flag is false (that replica hasn't observed the event), the resolved result is true — the event has been observed.
Types of CRDTs
Conflict-free replicated data type
There are two approaches to CRDTs, both of which can provide strong eventual consistency: state-based CRDTs and operation-based CRDTs.
State-based CRDTs
State-based CRDTs (also called convergent replicated data types, or CvRDTs) are defined by two types, a type for local states and a type for actions on the state, together with three functions: a function to produce an initial state, a merge function of states, and a function to apply an action to update a state. State-based CRDTs simply send their full local state to other replicas on every update, where the received new state is then merged into the local state. To ensure eventual convergence the functions should fulfill the following properties: The merge function should compute the join for any pair of replica states, and should form a semilattice with the initial state as the neutral element. In particular, this means that the merge function must be commutative, associative, and idempotent. The intuition behind commutativity, associativity and idempotence is that these properties are used to make the CRDT invariant under package re-ordering and duplication. Furthermore, the update function must be monotone with regard to the partial order defined by said semilattice.
Delta state CRDTs (or simply delta CRDTs) are optimized state-based CRDTs where only recently applied changes to a state are disseminated instead of the entire state.
Operation-based CRDTs
Operation-based CRDTs (also called commutative replicated data types, or CmRDTs) are defined without a merge function. Instead of transmitting states, the update actions are transmitted directly to replicas and applied. For example, an operation-based CRDT of a single integer might broadcast the operations “+10” or “−20”. The application of operations should still be commutative and associative. However, instead of requiring that application of operations is idempotent, stronger assumptions on the communications infrastructure are expected — all operations must be delivered to the other replicas without duplication.
Pure operation-based CRDTs are a variant of operation-based CRDTs that reduces the metadata size.
Comparison
The two alternatives are theoretically equivalent, as each can emulate the other. However, there are practical differences. State-based CRDTs are often simpler to design and to implement; their only requirement from the communication substrate is some kind of gossip protocol. Their drawback is that the entire state of every CRDT must be transmitted eventually to every other replica, which may be costly. In contrast, operation-based CRDTs transmit only the update operations, which are typically small. However, operation-based CRDTs require guarantees from the communication middleware; that the operations are not dropped or duplicated when transmitted to the other replicas, and that they are delivered in causal order.
While operations-based CRDTs place more requirements on the protocol for transmitting operations between replicas, they use less bandwidth than state-based CRDTs when the number of transactions is small in comparison to the size of internal state. However, since the state-based CRDT merge function is associative, merging with the state of some replica yields all previous updates to that replica. Gossip protocols work well for propagating state-based CRDT state to other replicas while reducing network use and handling topology changes.
Some lower bounds on the storage complexity of state-based CRDTs are known.
Known CRDTs
G-Counter (Grow-only Counter)
This state-based CRDT implements a counter for a cluster of n nodes. Each node in the cluster is assigned an ID from 0 to n - 1, which is retrieved with a call to myId(). Thus each node is assigned its own slot in the array P, which it increments locally. Updates are propagated in the background, and merged by taking the max() of every element in P. The compare function is included to illustrate a partial order on the states. The merge function is commutative, associative, and idempotent. The update function monotonically increases the internal state according to the compare function. This is thus a correctly defined state-based CRDT and will provide strong eventual consistency. The operations-based CRDT equivalent broadcasts increment operations as they are received.
PN-Counter (Positive-Negative Counter)
A common strategy in CRDT development is to combine multiple CRDTs to make a more complex CRDT. In this case, two G-Counters are combined to create a data type supporting both increment and decrement operations. The "P" G-Counter counts increments; and the "N" G-Counter counts decrements. The value of the PN-Counter is the value of the P counter minus the value of the N counter. Merge is handled by letting the merged P counter be the merge of the two P G-Counters, and similarly for N counters. Note that the CRDT's internal state must increase monotonically, even though its external state as exposed through query can return to previous values.
G-Set (Grow-only Set)
The G-Set (grow-only set) is a set which only allows adds. An element, once added, cannot be removed. The merger of two G-Sets is their union.
2P-Set (Two-Phase Set)
Two G-Sets (grow-only sets) are combined to create the 2P-set. With the addition of a remove set (called the "tombstone" set), elements can be added and also removed. Once removed, an element cannot be re-added; that is, once an element e is in the tombstone set, query will never again return True for that element. The 2P-set uses "remove-wins" semantics, so remove(e) takes precedence over add(e).
LWW-Element-Set (Last-Write-Wins-Element-Set)
LWW-Element-Set is similar to 2P-Set in that it consists of an "add set" and a "remove set", with a timestamp for each element. Elements are added to an LWW-Element-Set by inserting the element into the add set, with a timestamp. Elements are removed from the LWW-Element-Set by being added to the remove set, again with a timestamp. An element is a member of the LWW-Element-Set if it is in the add set, and either not in the remove set, or in the remove set but with an earlier timestamp than the latest timestamp in the add set. Merging two replicas of the LWW-Element-Set consists of taking the union of the add sets and the union of the remove sets. When timestamps are equal, the "bias" of the LWW-Element-Set comes into play. A LWW-Element-Set can be biased towards additions or removals. The advantage of LWW-Element-Set over 2P-Set is that, unlike 2P-Set, LWW-Element-Set allows an element to be reinserted after having been removed.
OR-Set (Observed-Remove Set)
OR-Set resembles LWW-Element-Set, but using unique tags instead of timestamps. For each element in the set, a list of add-tags and a list of remove-tags are maintained. An element is inserted into the OR-Set by having a new unique tag generated and added to the add-tag list for the element. Elements are removed from the OR-Set by having all the tags in the element's add-tag list added to the element's remove-tag (tombstone) list. To merge two OR-Sets, for each element, let its add-tag list be the union of the two add-tag lists, and likewise for the two remove-tag lists. An element is a member of the set if and only if the add-tag list less the remove-tag list is nonempty. An optimization that eliminates the need for maintaining a tombstone set is possible; this avoids the potentially unbounded growth of the tombstone set. The optimization is achieved by maintaining a vector of timestamps for each replica.
Sequence CRDTs
A sequence, list, or ordered set CRDT can be used to build a collaborative real-time editor, as an alternative to operational transformation (OT).
Some known Sequence CRDTs are Treedoc, RGA, Woot, Logoot, and LSEQ. CRATE is a decentralized real-time editor built on top of LSEQSplit (an extension of LSEQ) and runnable on a network of browsers using WebRTC. LogootSplit was proposed as an extension of Logoot in order to reduce the metadata for sequence CRDTs. MUTE is an online web-based peer-to-peer real-time collaborative editor relying on the LogootSplit algorithm.
Industrial sequence CRDTs, including open-source ones, are known to out-perform academic implementations due to optimizations and a more realistic testing methodology. The main popular example is Yjs CRDT, a pioneer in using a plainlist instead of a tree (ala Kleppmann's automerge).
Industry use
Conflict-free replicated data type
• Fluid Framework is an open-source collaborative platform built by Microsoft that provides both server reference implementations and client-side SDKs for creating modern real-time web applications using CRDTs. • Nimbus Note is a collaborative note-taking application that uses the Yjs CRDT for collaborative editing. • Redis is a distributed, highly available, and scalable in-memory database with a "CRDT-enabled database" feature. • SoundCloud open-sourced Roshi, a LWW-element-set CRDT for the SoundCloud stream implemented on top of Redis. • Riak is a distributed NoSQL key-value data store based on CRDTs. League of Legends uses the Riak CRDT implementation for its in-game chat system, which handles 7.5 million concurrent users and 11,000 messages per second. • Bet365 stores hundreds of megabytes of data in the Riak implementation of OR-Set. • TomTom employs CRDTs to synchronize navigation data between the devices of a user. • Phoenix, a web framework written in Elixir, uses CRDTs to support real-time multi-node information sharing in version 1.2. • Facebook implements CRDTs in their Apollo low-latency "consistency at scale" database. • Facebook uses CRDTs in their FlightTracker system for managing the Facebook graph internally. • Teletype for Atom employs CRDTs to enable developers share their workspace with team members and collaborate on code in real time. • Apple implements CRDTs in the Notes app for syncing offline edits between multiple devices. • Novell, Inc. introduced a state-based CRDT with "loosely consistent" directory replication (NetWare Directory Services), included in NetWare 4.0 in 1995. The successor product, eDirectory, delivered improvements to the replication process. • Figma's real-time multiplayer editing uses a server-authoritative, per-property last-writer-wins replication scheme (akin to an LWW register in CRDT literature); for ordered sequences (e.g., layer ordering) it uses fractional indexing with server tie-breaking for concurrent inserts (rather than operational transformation-style transforms). • AutoMerge is an open-source library offering several CRDTs in JavaScript and Rust, a compression format, and a sync protocol.