CRDTs: How Distributed Systems Agree Without Asking Permission

CRDTs: How Distributed Systems Agree Without Asking Permission

Conflict-free Replicated Data Types (CRDTs) were formally defined in 2011 at INRIA to solve the problem of multi-node synchronization without a shared clock. These structures ensure that if two replicas receive the same updates, they are mathematically guaranteed to converge to the same state.

Why This Matters

In the reality of distributed systems, network partitions and high latency make traditional locking mechanisms incompatible with high availability. CRDTs shift the paradigm from preventing divergence to designing data structures where divergence is inherently resolvable through algebraic properties. While they solve structural conflicts, engineers must still account for significant metadata overhead and the fact that CRDTs do not solve semantic business-logic conflicts. They represent a specialized tool for systems like collaborative editors and geo-distributed databases where availability and partition tolerance are prioritized over strict transactional ACID guarantees.

Key Insights

• Strong Eventual Consistency (SEC) was formally defined by Shapiro, Preguiça, Baquero, and Zawirski at INRIA in 2011.
• State-based CRDTs (CvRDTs) use merge functions that satisfy commutativity, associativity, and idempotency to compute the least upper bound of states.
• Delta-state CRDTs, introduced by Almeida, Shoker, and Baquero in 2016, optimize bandwidth by exchanging only incremental changes rather than full state.
• The G-Counter (Grow-only Counter) handles convergence by maintaining a vector of slots and applying element-wise maximums during merges.
• Tree relocation algorithms, such as those published by Kleppmann in 2020, address complex structural conflicts like moving nodes within a hierarchy.

Working Examples

Example of a G-Counter (Grow-only Counter) vector and the element-wise maximum merge operation.

Node A: [3, 0, 0]
Node B: [0, 5, 0]
Node C: [0, 0, 2]

merge([3,0,0], [0,5,0]) = [3,5,0]

Practical Applications

• Collaborative Editors: Yjs and Automerge use CRDTs to sync concurrent text insertions in tools like Jupyter Notebooks. Pitfall: Concurrent relocation of tree nodes can cause complex conflicts requiring specialized algorithms.
• Distributed Databases: Azure Cosmos DB and Redis Enterprise implement CRDTs for multi-master, active-active geo-distribution. Pitfall: High metadata overhead from ‘tombstones’ for deleted elements can impact performance without compression.
• Local-first Software: Systems following the 2019 Ink & Switch manifesto use CRDTs to treat device storage as primary and sync opportunistically. Pitfall: Optimistic updates are incompatible with strict ACID requirements like financial inventory management.

References:

• https://inria.hal.science/inria-00555588/document
• https://arxiv.org/abs/1805.06358
• https://arxiv.org/abs/1608.03960
• https://www.inkandswitch.com/essay/local-first/
• https://arxiv.org/pdf/1603.01529
• https://martin.kleppmann.com/2020/07/06/crdt-hard-parts-hydra.html