# DDIA Ch. 6: a G-Counter converges; a naive counter loses 80 increments ## Concept Three replicas each bump a shared counter while partitioned — A does +100, B does +50, C does +30 — so the answer *must* be 180. Then they reconcile. Model the counter naively, as a single integer register merged by last-write-wins, and the merge keeps only **one** replica's work: the survivor is **100** and the other **80 increments vanish**. Model it as a **G-Counter CRDT** — each replica keeps a vector of per-replica sub-counts, increment bumps its own entry, merge takes the element-wise MAX, value is the sum — and the replicas converge to exactly **180**, in *every* merge order. Same increments, same true total; the only difference is what "merge" is allowed to know. ## Provenance *Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 6 — *Replication*, §"Conflict-free replicated datatypes and operational transformation" (and §"Automatic conflict resolution"): > CRDTs are data structures that can be concurrently edited [...] and which > automatically resolve conflicts in sensible ways. The book presents CRDTs as replicated types whose merge is associative, commutative, and idempotent, so replicas converge no matter the order updates arrive. Here you watch a counter do exactly that — and watch the naive version fail to. ## Prerequisites The surprise is about what a *merge* is allowed to remember. These help; each line notes where it shows up. 1. **Concurrent writes need conflict resolution** — while replicas are partitioned they each accept writes; on reconnect something must combine those divergent states. It shows up as the `merge()` method both counters implement. 2. **Last-write-wins (LWW) discards data** — picking one value and dropping the other is a valid *conflict resolution*, but for a counter it throws away real increments. It shows up as the naive counter losing 80 of 180. 3. **A CRDT merge is commutative, associative, and idempotent** — element-wise MAX over per-replica sub-counts has all three properties, which is exactly why merge order cannot change the result. It shows up as all six orders giving 180. 4. **Per-replica bookkeeping (a version vector)** — the G-Counter keeps one sub-count *per replica id* so it can tell "A's 100" apart from "B's 50" instead of collapsing them into one register. It shows up as the `{A:100, B:50, C:30}` dict whose sum is the value. ### Where to learn the prerequisites - **CRDTs and automatic conflict resolution (#1–#3):** DDIA §"Conflict-free replicated datatypes and operational transformation" and §"Automatic conflict resolution"; Shapiro et al., "Conflict-free Replicated Data Types" (2011) for the G-Counter and the merge-lattice argument. - **Why LWW loses writes (#2):** DDIA §"Last write wins (discarding concurrent writes)" — LWW is fine when losing writes is acceptable, and a counter is precisely when it is not. If only one is new, make it #3 — commutative + associative + idempotent merge is the whole reason a CRDT converges. ## Environment Deterministic, so the counts reproduce exactly: - macOS 26.5.2 (Darwin 25.5.0), arm64 - Python 3.15.0a8, standard library only — no Docker, no deps - No real concurrency: partitions and merges are simulated in one process, so the result is fixed every run - Fixed workload: A:+100, B:+50, C:+30 → true total 180 ## Mental model Two counters, same three replicas, same increments — only the merge differs. - **Naive replicated counter** — each replica is a single integer. Increment adds 1 to it. To merge two replicas, last-write-wins keeps the larger register (one value simply overwrites the other). There is no way to tell "100 from A" from "100 that already includes B and C," so concurrent increments cannot be summed. - **G-Counter CRDT** — each replica is a dict `{replica_id: count}`. Increment bumps *its own* entry. Merge takes, for every replica id, the MAX of the two sub-counts; the value is the sum of the merged dict. Because A's, B's, and C's contributions live in *separate* slots, no merge can overwrite one with another. Both counters implement the same two-method interface (`increment`, `merge`); the exercise runs both against the identical workload. The whole thing is one script, `code/g_counter_crdt.py`. ## Setup ``` cd study/ddia/ch06/code python3 g_counter_crdt.py ``` Do **not** read the output yet — make each prediction first. ## Steps ### Step 1 — the workload **Predict.** Three replicas increment while offline: A +100, B +50, C +30. Before any merge logic, what is the true total the counter *should* report after reconciliation? **Observe.** ``` 3 replicas increment a shared counter while partitioned, then merge. A: +100 B: +50 C: +30 true total = 180 ``` 180 — no surprise yet. The surprise is whether the merge can *recover* it. ### Step 2 — merge the naive counter **Predict.** Each replica holds a plain integer (A=100, B=50, C=30) and we merge them last-write-wins. What single number comes out — and how many of the 180 increments survive? **Observe.** ``` naive replicated counter (single integer register, last-write-wins merge): after merging A, B, C -> 100 LOST 80 of 180 increments (44%) -- the merge kept one replica and dropped the rest. ``` **100, not 180 — 80 increments gone.** LWW on a single register can only *pick* a value, never *combine* two. It keeps A's 100 (the largest) and silently discards B's 50 and C's 30. Nothing errored; the counter just quietly lost 44% of the writes. ### Step 3 — merge the G-Counter **Predict.** Same three replicas, but now each is a dict — A=`{A:100}`, B=`{B:50}`, C=`{C:30}` — merged by element-wise MAX and summed. What does it report? **Observe.** ``` G-Counter CRDT (per-replica sub-counts, element-wise max merge): after merging A, B, C -> 180 LOST 0 increments -- converged to the exact total. ``` **Exactly 180, nothing lost.** The MAX is taken *per replica id*, so merging `{A:100}` with `{B:50}` gives `{A:100, B:50}` — the entries don't collide, they coexist. Summing the merged dict recovers every increment. ### Step 4 — merge order doesn't matter **Predict.** There are six orders to merge three replicas. How many distinct final values will the G-Counter produce across all six? **Observe.** ``` order-independence -- merge the three G-Counters in every order: merge order A -> B -> C = 180 merge order A -> C -> B = 180 merge order B -> A -> C = 180 merge order B -> C -> A = 180 merge order C -> A -> B = 180 merge order C -> B -> A = 180 every order converges to the same value: the CRDT is order-independent. ``` **One value — 180 — across all six orders.** Element-wise MAX is commutative and associative, so the order the replicas reconcile in cannot change where they land. That is convergence: the replicas agree no matter how the network delivers their states. ## What you should see - The true total is **180**; both counters start from the identical workload. - The naive LWW register merges to **100**, losing **80** increments (44%). - The G-Counter merges to **180**, losing **0**. - All **six** merge orders of the G-Counter give **180** — one distinct value. ## Why A counter under concurrent updates is the cleanest case where "just pick a value" fails. When three replicas each accept increments during a partition, their states genuinely diverge, and reconciliation has to *combine* the divergent work, not choose among it. Last-write-wins can only choose. Its merge — keep the larger register — treats the two 3-digit numbers as rivals, so the moment it keeps A's 100 it has thrown B's 50 and C's 30 away. The bug isn't in the arithmetic; it's that a single integer has nowhere to *record* that its 100 and B's 50 came from different, non-overlapping streams of increments. With only one slot, one write must overwrite the other. The G-Counter fixes this by giving every replica its own slot. Because A only ever bumps `counts["A"]` and B only ever bumps `counts["B"]`, the sub-counts are independent — no increment made by one replica can ever be the "same" write as an increment made by another. Merge then doesn't have to choose: for each slot it takes the MAX, which for these disjoint streams just means "carry across whichever replica's entry we have," and the sum reassembles the whole. And because MAX is commutative (`max(a,b) = max(b,a)`), associative, and idempotent (`max(a,a) = a`), the merge forms a lattice — every replica climbs monotonically toward the same least-upper-bound state. That is why all six orders converge to 180: the destination is a property of the *set* of updates, not the order they arrive. **The boundary — a G-Counter only counts up, and convergence is not correctness.** The MAX-merge trick works *because* increments are monotonic; subtract, and MAX would happily discard the smaller value again (the fix is a PN-Counter: two G-Counters, one for increments and one for decrements, subtracted). More broadly, a CRDT guarantees the replicas *agree* on an answer, not that the answer is the one an atomic, linearizable counter would have produced — it dodges coordination by restricting the operations to ones that commute. When your update isn't naturally commutative (transfer money, enforce a uniqueness constraint), no merge function saves you and you're back to consensus. CRDTs move the cost from runtime coordination to design-time: you buy conflict-free merges by giving up operations that can't be made to commute. ### Go deeper 1. **Make it subtract.** Add a decrement to the G-Counter and watch a MAX-merge lose it, then build a PN-Counter (increments and decrements as two separate G-Counters, value = sum(P) − sum(N)) and confirm it converges again. 2. **Break idempotence.** Change the naive merge to *add* the two registers instead of MAX, then merge the same pair of replicas twice. Predict the double-count, and see why real CRDT merges must be idempotent to survive re-delivered messages. 3. **Grow a grow-only set.** Replace the counter with a G-Set (union-merge) and a fictional "remove" and discover why removal is the hard part of CRDTs — the jump from a G-Set to an OR-Set, and why tombstones appear.