Data Synchronisation · Lesson 03

Merge Is Not Add

In calibration you merged two counter replicas by adding them. Nearly everyone does, the first time. Working out exactly why it is wrong gives you the entire idea behind state-based CRDTs — and the line that separates them from operation-based ones.

The question, and the two answers

A grow-only counter (G-Counter, from Shapiro et al.'s 2011 catalogue) keeps one slot per replica. Each replica increments only its own slot; the value is the sum of all slots. Two replicas:

const atA = { a: 3, b: 5 }    // A has counted 3 of its own, and has heard b = 5
const atB = { a: 4, b: 2 }    // B has counted 2 of its own, and has heard a = 4

You answered { a: 7, b: 7 }, “because addition commutes.” Addition does commute. But look at what the slots mean. Slot a is “how many increments has A performed, as far as this replica knows.” A has performed either 3 or 4 — the two replicas hold two observations of the same fact, and the later observation is 4. Adding them says A performed 7, which never happened.

The merge is the pointwise maximum:

merge(atA, atB)  =  { a: max(3, 4), b: max(5, 2) }  =  { a: 4, b: 5 }      // value 9

Now run your version again with a wrinkle: A sends its state to B, the network duplicates the packet, and B merges it twice. With addition the counter climbs by another 3 the second time. With max it does not move. That is the property the whole design rests on.

Update and merge are different functions

The mistake is natural because the word “add” belongs to a different operation on the same type. A CRDT has two kinds of function, and conflating them is the whole error:

type GCounter = Record<ReplicaId, number>

// UPDATE — a local operation; changes one slot; this is the "add"
const increment = (s: GCounter, me: ReplicaId): GCounter =>
  ({ ...s, [me]: (s[me] ?? 0) + 1 })

// MERGE — combines two replicas' states; pointwise max; never "adds"
const merge = (x: GCounter, y: GCounter): GCounter =>
  Object.fromEntries([...new Set([...Object.keys(x), ...Object.keys(y)])]
    .map(k => [k, Math.max(x[k] ?? 0, y[k] ?? 0)]))

// QUERY — the value the application sees
const value = (s: GCounter): number => Object.values(s).reduce((a, b) => a + b, 0)

increment is what a user does. merge is what the network does. Only the second one has to be safe against the network's misbehaviour — reordering, duplication, delay — and that is what the three laws below are for.

Three laws, one shape

Kleppmann's slide 147 states what a state-based merge operator ⊔ must satisfy, for all states s₁, s₂, s₃:

Pointwise max satisfies all three; so does set union; so does “keep the pair with the greater timestamp”. An operator with these three properties is a join, and the states it acts on form a join-semilattice: there is a partial order on states (for the G-Counter, x ≤ y when every slot of x is ≤ the same slot of y) and ⊔ gives the least state above both inputs. The consequence you can feel without the algebra: a replica's state only ever moves up. Merging can never take information away, so no message arriving late, twice, or out of order can undo anything. Lars Hupel's interactive series is the place to push on this until it is obvious.

What the laws buy: strong eventual consistency

Shapiro et al. named the guarantee. Kleppmann's slide 145 gives its two halves:

“Eventual delivery: every update made to one non-faulty replica is eventually processed by every non-faulty replica. Convergence: any two replicas that have processed the same set of updates are in the same state.”

Convergence is the part the laws deliver: because ⊔ is commutative and associative, the order in which the updates arrived cannot matter; because it is idempotent, how many times each arrived cannot matter. “The same set of updates” is the only thing that determines the state. Shapiro's SSS 2011 paper describes the appeal in one clause — SEC “avoids the complexity of conflict resolution and of roll-back.” Compare lesson 01, whose entire loop was roll-back (rewind) and conflict resolution (the server's order). A CRDT is the claim that, for some data types, you can design the merge so that neither is needed.

State-based versus operation-based

Everything above ships states. There is a second family that ships operations, and the distinction is the calibration question you answered “don't know” to. Kleppmann gives the same key–value map both ways (slides 144 and 146):

The two rows that matter are “what must be true” and “network needed”, and they are one fact seen twice. Kleppmann: “The advantage of the state-based approach is that it can tolerate lost or duplicated messages: as long as two replicas eventually succeed in exchanging their latest states, they will converge … Duplicated messages are also fine because the merge operator is idempotent. This is why a state-based CRDT can use unreliable best-effort broadcast, while an operation-based CRDT requires reliable broadcast (and some even require causal broadcast).”

An operation is not idempotent in general — apply “increment” twice and you have counted twice — so an op-based CRDT pushes the duplicate-and-loss problem onto the transport. That is a real cost: reliable, exactly-once-effect, sometimes causally ordered delivery is the hard part of distributed systems, and lesson 06 is about what it takes. The state-based family pays in bandwidth instead, and pays it every time.

Glossary — added this lesson

What this unlocks

With lessons 01–03 in hand you can read Figma's design note as an argument rather than a story: a sequencer instead of commutativity, an LWW register borrowed from the CRDT catalogue, and the sentence “CRDTs are designed for decentralized systems where there is no single central authority” — that is lesson 04. Lesson 06 takes the op-based column seriously: what causal delivery is, why an observed-remove set needs it, and the retry trap Kleppmann shows on slide 91.

Sources: Kleppmann, Distributed Systems lecture notes (slides 90, 144–147) · Shapiro et al., Conflict-free Replicated Data Types (SSS 2011) · Shapiro et al., A comprehensive study of CvRDTs and CmRDTs (2011) · Hupel, An introduction to CRDTs · RESOURCES.md