Concurrent Writes: LWW, CRDTs, and Version Vectors

Multi-leader and leaderless replication buy availability and multi-region/offline writes, and hand you a hard problem in return: two replicas can write the same key concurrently, and someone must resolve it. Get it wrong and data silently vanishes (the infamous disappearing cart item). Get it right — CRDTs, version vectors — and you get local-first apps and real-time collaboration. Here it is, simulated.

Runnable companion: replication-conflict-resolution on GitHub. make conflicts && make vectors reproduces every number below (pure Python).

Last-writer-wins loses data; CRDTs converge

Two replicas edit one shopping cart concurrently, then sync:

Replica A cart: ['book', 'pen']
Replica B cart: ['book', 'milk']
LWW  → ['book', 'pen']            lost: ['milk']
CRDT → ['book', 'milk', 'pen']   lost: {}

Over 5,000 concurrent cart merges:
  items silently dropped by LWW : 7,114
  items dropped by CRDT (union) : 0
  LWW winner chosen against real order (clock skew): 31%

LWW (keep the newer timestamp) is trivial and it converges — but it converges by throwing data away (7,114 dropped items here), and "newer" depends on clocks, so skew picked the wrong write 31% of the time. A CRDT — here an add-wins set — merges to the union, losing nothing. Same story for a counter: two concurrent +1s give LWW 101 (one increment lost) but a G-Counter 102. CRDTs (sets, counters, RGA text) are the foundation of local-first and collaborative software.

Version vectors detect concurrency

To merge safely you must know whether one write happened after another or concurrently. A version vector (one counter per replica) decides it; a single scalar clock can't:

1) Causal chain:  v1={R1:1}, v2={R1:2}
   compare(v2, v1) → a supersedes b    (no conflict)

2) Concurrent:    x={R1:2}, y={R1:1, R2:1}
   compare(x, y) → concurrent (siblings)   → keep BOTH and merge → {R1:2, R2:1}

3) Same writes under ONE scalar clock: x=2, y=2
   'max wins' → drop one → a LOST UPDATE

If one vector dominates the other, the writes are causal (one supersedes). If they're incomparable, they're concurrent siblings that must both be kept. A lone timestamp conflates "after" with "concurrent" and silently drops updates — which is why Dynamo/Riak and CRDTs are built on version vectors, not clocks.

Some conflicts can't be merged at all

The demos converge because a cart and a counter have a natural "keep everything" merge. But unique username or stock >= 0 have no correct after-the-fact merge — two replicas each sell the last item, both succeed, and no merge un-sells one. Invariants like these need a single point that serializes writes (single-leader, or a linearizable store). Conflict resolution runs after both writes were accepted; by then the invariant is already violated. If your domain has hard invariants, that decides the topology.

What I'd say in an interview

• Multi-leader/leaderless require conflict resolution — choose it by data shape (counter → G-Counter, set → OR-Set, text → RGA, "latest" → LWW only if loss is OK).
• LWW loses data and trusts clocks; CRDTs converge without loss at the cost of metadata and fixed merge semantics.
• Version vectors detect concurrent vs causal writes; a scalar clock causes lost updates.
• Invariants (unique, non-negative) can't be merged after the fact — keep that data single-leader, and push tolerant data (carts, feeds, docs) to the eventually-consistent edge.