CRDTs are fundamentally a lie that the system tells itself to keep data consistent.
Let’s see one in action. Imagine two users, Alice and Bob, editing the same document simultaneously. We’ll use a simple counter CRDT.
// Example using Go's github.com/go-kudzu/crdt
package main
import (
"fmt"
"sync"
"github.com/go-kudzu/crdt/counters"
)
func main() {
var wg sync.WaitGroup
// Alice's counter
aliceCounter := counters.NewGDTInt(0)
// Bob's counter
bobCounter := counters.NewGDTInt(0)
// Alice increments
wg.Add(1)
go func() {
defer wg.Done()
aliceCounter.Add(5)
fmt.Printf("Alice increments by 5. Current value: %d\n", aliceCounter.Value())
}()
// Bob increments
wg.Add(1)
go func() {
defer wg.Done()
bobCounter.Add(3)
fmt.Printf("Bob increments by 3. Current value: %d\n", bobCounter.Value())
}()
wg.Wait()
// Simulate network transmission: Alice sends her state to Bob
bobCounter.Merge(aliceCounter.State())
// Simulate network transmission: Bob sends his state to Alice
aliceCounter.Merge(bobCounter.State())
fmt.Printf("After merge, Alice's value: %d\n", aliceCounter.Value())
fmt.Printf("After merge, Bob's value: %d\n", bobCounter.Value())
// Expected output: Both will eventually see 8
}
This looks like a simple counter, but the magic is in how Add and Merge work under the hood. The system doesn’t actually resolve conflicts; it designs the data structure such that conflicts cannot happen.
CRDTs solve the problem of maintaining data consistency across multiple replicas in a distributed system without relying on a central coordinator or complex locking mechanisms. This is crucial for applications requiring high availability and low latency, like collaborative editors, multiplayer games, and distributed databases. The core idea is to design data types where concurrent operations are commutative and idempotent, meaning the order of operations doesn’t matter, and applying an operation multiple times has the same effect as applying it once.
There are two main categories:
- State-based (or Convergent) CRDTs: Each replica maintains a state. When replicas communicate, they exchange their entire state, and a merge function combines them. The merge function must be associative, commutative, and idempotent. Our counter example above is a state-based CRDT.
- Operation-based (or Commutative) CRDTs: Replicas exchange operations (e.g., "increment by 5"). These operations must be delivered to all replicas in a causally consistent manner, and the operations themselves must be commutative. This often relies on a reliable broadcast mechanism.
Internally, CRDTs achieve this through various techniques. For counters, a common implementation is the Grow-Only Counter (G-Counter), where each replica has its own counter, and the total value is the sum of all replica counters. Another is the PN-Counter (Positive-Negative), which supports increments and decrements, but requires more careful state management to ensure it never goes below zero. For sets, we have G-Set (Grow-only Set), 2P-Set (Two-Phase Set, allowing additions and removals), LWW-Set (Last-Writer-Wins Set), and OR-Set (Observed-Remove Set). Each has different trade-offs in terms of expressiveness and convergence guarantees.
The "lie" CRDTs tell is that there’s no single, definitive version of the truth that needs to be agreed upon. Instead, each replica independently updates its local state based on incoming information, and the structure of the CRDT ensures that all replicas will eventually converge to the same, correct state, regardless of the order in which updates are received or the network partitions that occur. It’s like each participant in a conversation has their own notepad, and they jot down what they hear. The CRDT structure is the rulebook that ensures if everyone follows it, all notepads will eventually look identical, even if some people heard things in a different order or missed some messages and got them later.
Many people struggle with the mental model of how data can be "consistent" when there’s no central authority and operations can happen in any order. They assume there must be some hidden locking or consensus protocol. The key insight is that the data type itself is designed to be conflict-free. For a Grow-Only Set (G-Set), you can only add elements. If Alice adds 'X' and Bob adds 'Y', and then they merge, the resulting set is {X, Y}. If Alice adds 'X' and Bob also adds 'X', merging doesn’t change the set. The operation of adding an element is idempotent. The merge operation (set union) is associative and commutative. There’s no conflict to resolve.
The next hurdle is often understanding how to model more complex data structures like JSON documents or graphs using these basic CRDT primitives, and the performance implications of merging large states.