CRDTs Expert¶

What you'll learn¶

• The problem CRDTs solve (merging without coordination)
• Build a grow-only counter (G-Counter)
• Build a last-write-wins register (LWW)
• The three properties that make merges safe
• Where CRDTs are used in the real world

The problem¶

Multiple replicas accept writes offline and must converge without a central coordinator or conflicts.

When data is replicated across nodes that can update independently — offline apps, multi-region databases, collaborative editors — two replicas can change the same value at the same time. When they sync, whose value wins? Locking everything to coordinate is slow and defeats the point of replication.

CRDTs (Conflict-free Replicated Data Types) are data structures designed so that concurrent updates always merge to the same result, automatically, without coordination. No locks, no consensus, no "last writer clobbers everything." Any two replicas that have seen the same set of updates converge to identical state — a property called strong eventual consistency.

   Replica A: 3 ─┐                    ┌─▶ merge → 8
                 ├─ sync (both ways) ─┤
   Replica B: 5 ─┘                    └─▶ merge → 8   (both converge)

G-Counter: a grow-only counter¶

A counter each node increments locally; merging takes the max per node, so it always converges.

The simplest CRDT. The trick: instead of one shared number, each node keeps its own count, and the value is the sum. Merging takes the max per node — so no increment is ever lost. Fully runnable:

class GCounter:
    def __init__(self, node_id: str) -> None:
        self.node_id = node_id
        self.counts: dict[str, int] = {}

    def increment(self, n: int = 1) -> None:
        self.counts[self.node_id] = self.counts.get(self.node_id, 0) + n

    def value(self) -> int:
        return sum(self.counts.values())

    def merge(self, other: "GCounter") -> None:
        for node, cnt in other.counts.items():
            self.counts[node] = max(self.counts.get(node, 0), cnt)   # max per node

Two nodes increment concurrently, then sync:

a = GCounter("A")
b = GCounter("B")
a.increment(3)      # A's count: {A: 3}
b.increment(5)      # B's count: {B: 5}

a.merge(b)          # sync both directions
b.merge(a)

print("A value:", a.value(), " B value:", b.value())

Output:

A value: 8  B value: 8

Both replicas converge to 8 — neither increment was lost. Because each node owns its own slot, there's no conflict to resolve; merge just takes the highest count seen for each node. Merging is safe to repeat: a.merge(b) again leaves it at 8.

LWW-Register: last-write-wins¶

A single value where the newest timestamp wins — simple conflict resolution for a register.

For a single value (like a user's chosen theme color), a common CRDT attaches a timestamp and keeps whichever write is latest:

from dataclasses import dataclass

@dataclass
class LWWRegister:
    value: str = ""
    timestamp: float = 0.0

    def set(self, value: str, ts: float) -> None:
        if ts > self.timestamp:
            self.value, self.timestamp = value, ts

    def merge(self, other: "LWWRegister") -> None:
        if other.timestamp > self.timestamp:
            self.value, self.timestamp = other.value, other.timestamp

r1 = LWWRegister()
r2 = LWWRegister()
r1.set("red", ts=10.0)
r2.set("blue", ts=12.0)      # a later write

r1.merge(r2)
r2.merge(r1)
print("r1:", r1.value, " r2:", r2.value)

Output:

r1: blue  r2: blue

The later write (blue at t=12) wins on both replicas. Simple and convergent — but note the tradeoff: LWW discards the losing write. That's fine for a color preference, wrong for a bank balance.

What makes a merge safe¶

Merges must be commutative, associative, and idempotent so any order/duplication converges to the same state.

A CRDT merge works because it has three mathematical properties. Any operation with all three converges regardless of order or duplication:

max (G-Counter) and "keep latest timestamp" (LWW) both satisfy all three — which is why those merges are correct. This is also why CRDTs pair naturally with at-least-once message delivery (Distributed Queues): duplicates don't corrupt state.

Why these merges are safe (demonstrated)¶

Two short runs that prove the G-Counter merge is idempotent and commutative — the properties the table above claims.

The table says a safe merge is idempotent (duplicates are harmless) and commutative (order doesn't matter). Those aren't just claims — they're observable. Both runs reuse the GCounter from above.

Idempotent — merging the same update twice does nothing the second time. This is what makes CRDTs safe under at-least-once delivery: a re-delivered merge message can't corrupt state.

a = GCounter("A")
b = GCounter("B")
a.increment(3)
b.increment(5)

a.merge(b)
first = dict(a.counts)      # state after merging once
a.merge(b)                  # the SAME update arrives again (duplicate delivery)
second = dict(a.counts)     # state after merging twice

print("after 1 merge: ", first)
print("after 2 merges:", second)
print("idempotent (unchanged):", first == second)

Output:

after 1 merge:  {'A': 3, 'B': 5}
after 2 merges: {'A': 3, 'B': 5}
idempotent (unchanged): True

The second merge sees nothing it hasn't already applied — max(x, x) == x per node — so the state is byte-for-byte identical.

Commutative — merge order doesn't matter. Three replicas increment independently; merging them in opposite orders converges to the same result, so messages can arrive however the network delivers them.

def merge_in_order(order: list[str]) -> dict[str, int]:
    reps = {"X": GCounter("X"), "Y": GCounter("Y"), "Z": GCounter("Z")}
    reps["X"].increment(1)
    reps["Y"].increment(2)
    reps["Z"].increment(4)
    target = GCounter("T")
    for name in order:
        target.merge(reps[name])    # fold replicas in the given order
    return target.counts

forward = merge_in_order(["X", "Y", "Z"])
reverse = merge_in_order(["Z", "Y", "X"])

print("forward order:", forward)
print("reverse order:", reverse)
print("commutative (same result):", forward == reverse)

Output:

forward order: {'X': 1, 'Y': 2, 'Z': 4}
reverse order: {'Z': 4, 'Y': 2, 'X': 1}
commutative (same result): True

The two dicts list their keys in different orders, but Python dict equality ignores insertion order, so forward == reverse is True — both orderings reach the same state. (In Python, == on dicts compares keys and values, not order.)

The CRDT family¶

Counters, registers, sets, and maps — the common building blocks and what each is for.

• Counters — G-Counter (increment-only), PN-Counter (increment + decrement, using two G-Counters).
• Registers — LWW-Register, Multi-Value Register (keeps all concurrent values for the app to resolve).
• Sets — G-Set (add-only), OR-Set (add/remove with unique tags).
• Sequences — for collaborative text editing (the basis of tools like Yjs/Automerge).

Real-world use¶

Collaborative editors, offline-first apps, and distributed caches that sync without locking.

• Collaborative editors (Figma, Google Docs-style tools) — merge simultaneous edits without a central lock.
• Offline-first / local-first apps — edit offline, sync and merge cleanly when back online.
• Distributed databases — Redis has built-in CRDTs (in Redis Enterprise); Riak, Azure Cosmos DB use them for multi-region writes.
• Shopping carts — the classic Amazon Dynamo example: merge a cart edited on your phone and laptop without losing items.

CRDTs shine exactly where Multi-region Consistency is hard: they let every replica accept writes locally and reconcile later, no coordination required.

Practice exercises¶

1. Build a PN-Counter (supports decrement) using two G-Counters — one for increments, one for decrements; value is inc.value() - dec.value().
2. Show your G-Counter merge is commutative by asserting merge(a,b) and merge(b,a) give the same counts dict.
3. Implement a G-Set (add-only set) whose merge is set union, and confirm it's idempotent.
4. Demonstrate the LWW data-loss problem: two concurrent writes at the same timestamp, and discuss how you'd break the tie deterministically (e.g. by node id).
5. Explain why idempotent merges make CRDTs safe under at-least-once message delivery.