Conflict-Free Replicated Data Types (CRDTs)
What you'll learn: How CRDTs enable automatic convergence in distributed systems without requiring coordination between replicas.
The Problem CRDTs Solve
In eventually consistent systems, replicas accept writes independently and sync later. But what happens when two users edit the same data simultaneously on different replicas? Traditional approaches require conflict resolution logic—someone has to "win," or you merge manually.
CRDTs are special data structures that mathematically guarantee convergence. Any two replicas that have seen the same set of updates will reach identical state, regardless of the order those updates arrived.
The Core Idea
Think of a shared whiteboard where multiple people draw independently. With regular data structures, if two people write over the same spot, you need a referee to decide which mark stays. With CRDTs, the whiteboard itself has rules built in: maybe "marks can only be added, never removed" or "timestamps automatically determine which color shows."
CRDTs come in two flavors:
State-based CRDTs (CvRDTs): Replicas send their entire state to each other and merge using a commutative, associative, idempotent merge function. Like sharing the whole whiteboard periodically.
Operation-based CRDTs (CmRDTs): Replicas send operations (add, remove) that are commutative—order doesn't matter. Like sharing "I drew a circle at position X" messages.
Common Examples
- Counters: Increment-only counters where each replica tracks its own increments, then sums them
- Sets: Add-only sets or sets where removes are tracked separately to handle concurrent add/remove
- Registers: Last-write-wins registers using timestamps
Key Takeaway: CRDTs are specialized data structures that automatically converge to the same state across replicas without coordination, making them ideal for highly available, eventually consistent systems where conflicts must resolve deterministically.