Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Eventual consistency, convergence and CRDTs

What does last-write-wins lose?

Eventual consistency, and how convergence is really achieved

Given the framing of Distributed consistency, the only substantive question left is the merge rule (what do when they hold different values). There are exactly two families.

Arbitrate: pick a winner

Last-write-wins (LWW) needs a total order on timestamps, so it needs a clock, and ties break on node id. Therefore clock skew decides which write survives, and the loser is discarded with no error anywhere in the system. It is the Thomas write rule (ignore a write whose timestamp is older than the stored one), promoted from an optimization to a consistency model. It is also the default in Cassandra, which is why the failure is common.

The usable rule: LWW is correct for idempotent of state whose authority lives elsewhere, and wrong for anything accumulative. (A sensor's last reported temperature: fine. A points counter: wrong.)

Merge: combine

Merging requires an algebra (next section).

What belongs here from the mechanisms

Anti-entropy (background comparison of replicas), (fixing stale copies when a read finds them) and (a node holds a write for a node that is down) are mechanisms for . What belongs here is the consequence: convergence is a background process, and its lag is your real guarantee. So the guarantee you can state and monitor is .

Strong eventual consistency and CRDTs

Let us derive CRDTs rather than accept them. We want reads and writes to be local, with no coordination on the critical path. If nothing coordinates, nothing decides the order in which updates arrive at each replica. Therefore the outcome must not depend on the order. That forces the merge function to be:

  • commutative (a ⊕ b = b ⊕ a),
  • associative ((a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)),
  • idempotent (a ⊕ a = a, so receiving the same update twice is harmless).

A CRDT (conflict-free replicated data type) is not a clever construction. It is the closure of that requirement: this is .

Two formulations. The difference is where the cost went.

  • State-based (CvRDT). States form a (a set with a "least upper bound" operation, the smallest state that is above both). Merge is the least upper bound. Updates are inflationary (a state only moves up). Because merge is idempotent and order-insensitive, the channel may lose, duplicate and reorder messages freely. Cost: the whole state is sent. exist to send only the recent change.
  • Op-based (CmRDT). Ship operations that . This requires underneath (every operation reaches every replica exactly once, in causal order). The requirement did not disappear; it moved into the delivery layer.

So the honest statement: a CRDT is not coordination-free. It is coordination-free on the write path, with the requirement pushed either into the merge algebra or into the channel.

G-counter

A vector of per-replica counts, merged pointwise by max, valued by the sum.

Replica A: {A: 3, B: 0}        Replica B: {A: 2, B: 4}
merge  = {A: max(3,2)=3, B: max(0,4)=4}      value = 3 + 4 = 7

Why one slot per replica? max is the natural idempotent merge for a number that only grows. If all replicas shared one integer and merged with max, two concurrent "+1" operations (5 → 6 at both) would merge to 6 and lose an increment. With per-replica slots, each replica only increments its own slot, so nothing is lost. Decrement would violate "only moves up", hence the : two , one for increments and one for decrements. Metadata is O(replicas), and "replicas" frequently means clients, so it meets writer churn again.

A crucial limit: a counter cannot enforce a bound. "Never negative" is not expressible, since merging two locally legal decrements can go below zero. The fix is the (escrow CRDT): pre-allocate quota to each replica, let each act locally within its quota, and coordinate only when a replica exhausts its reservation. That is the concrete preview of The unification and its price: coordination reappears exactly where the binds, and nowhere else.

OR-Set (observed-remove set)

Each add creates a unique tag. A remove deletes the tags it has observed. A concurrent add survives, because its tag was never observed by the remove: add wins.

A: add(x) → {(x,tag1)}                     B (concurrently): remove(x) sees nothing → no effect
Later, A: remove(x) → deletes tag1;  B: add(x) → {(x,tag2)}
merge → {(x,tag2)}      (x is present: the add that nobody had observed survives)

Naive sets cannot decide between an add and a remove that happen at the same time, and 2P-sets ("a removed element can never come back") are plainly wrong for real use. The tags are worth noticing: a random unique identifier standing in for a coordinated sequence number is , here inside a data type instead of a load balancer.

LWW register

As above. It is the CRDT that converges by choosing what to lose.

The sharpest point: garbage collection

Removal-capable CRDTs accumulate metadata: (markers saying "this was deleted"), tags, vectors. To collect it safely, you must know that every replica has observed the removal. That is called , and it requires membership knowledge and hearing from everyone.

This is the immutable-substrate rule (never overwrite, so you need an indirection layer and a garbage collector) with a new wrinkle: this collector needs global knowledge. Coordination avoided per write returns per epoch. The familiar failure also appears: the collector falls behind under exactly the conditions that produce the most garbage, because one partitioned or offline replica blocks causal stability for everybody.

CRDTs guarantee convergence, not correctness

This is the most common CRDT mistake. Two replicas that converge on the same business-invalid state are a fully successful CRDT. Set union converges beautifully. "Only one person may book this room" is not a set union. The unification and its price supplies a theorem about when this is a problem ().