Vector Clocks & CRDTs

In a distributed system without a single source of truth, two replicas can accept writes to the same key at the same time, neither aware of the other. When they finally sync, you face the question that haunts every eventually-consistent store: which write wins, and how do you even know there was a conflict? Wall-clock timestamps lie (clocks drift; “last write wins” silently discards data). This page is about two ideas that confront the problem head-on: vector clocks, which detect concurrency, and CRDTs, which make conflicts resolve themselves.

Why timestamps can’t tell you what happened

The deep issue is that “happened before” is about causality, not calendar time. If write A could have influenced write B (B’s author had seen A), then A is causally before B and B is the obvious winner. But if A and B were made independently, in ignorance of each other, then there is no “right” winner — they are concurrent, and you have a genuine conflict that no timestamp can adjudicate honestly. This is the territory mapped out in Time, Clocks & Ordering: physical clocks measure the wrong thing. We need a clock that measures causality instead.

Vector clocks: a clock that counts causality

A vector clock gives every replica a counter, and every value carries a vector of all replicas’ counters as last seen by the writer. The rules are tiny:

• Each node increments its own entry on every local write.
• When a node receives/merges a value, it takes the element-wise maximum of the two vectors, then increments its own entry.

To compare two vectors V and W:

V "happened before" W   if every V[i] <= W[i]  and at least one V[i] < W[i]
W "happened before" V   (the mirror of the above)
V and W are CONCURRENT   if neither dominates — each has some entry the other lacks

Worked example with three replicas A, B, C:

A writes x:  [A:1, B:0, C:0]
B reads that, then writes:  [A:1, B:1, C:0]   ← B saw A, so B's write is causally AFTER A
                                                ([1,0,0] <= [1,1,0]) — B wins cleanly.

Meanwhile C, never having seen A, writes:  [A:0, B:0, C:1]
Compare [A:1,B:1,C:0] vs [A:0,B:0,C:1]:
   neither <= the other  →  CONCURRENT  →  real conflict, surface BOTH versions.

That last line is the magic and the catch. A vector clock won’t resolve the conflict — it will honestly tell you one exists so you don’t silently lose data. Systems like Dynamo and Riak return both sibling versions to the application and say “you decide” (merge a shopping cart by union, ask the user, pick by a domain rule).

The cost of honesty

Vector clocks buy you correct conflict detection — no more silent lost updates from last-write-wins. The cost: the vector grows with the number of writers, the application must handle sibling versions, and pruning old entries safely is fiddly. You’ve traded a comfortable lie for an uncomfortable truth you now have to act on.

CRDTs: data types that merge themselves

Surfacing siblings to the application is honest but exhausting. What if the data type itself were designed so that any two replicas, merged in any order, always converge to the same answer — no conflicts to resolve, ever? That is a Conflict-free Replicated Data Type (CRDT).

The trick is mathematical. If the merge operation is commutative, associative, and idempotent (a join-semilattice, formally), then it doesn’t matter what order updates arrive, whether they arrive twice, or which replica merges first — everyone ends up identical. The network can reorder, duplicate, and delay messages all it wants; convergence is guaranteed by algebra, not by careful coordination.

Some workhorse CRDTs:

G-Counter   grow-only counter. Each node keeps its own count; value = SUM,
            merge = element-wise MAX. Increments never conflict.

PN-Counter  two G-Counters (one for + , one for -); value = P_sum - N_sum.
            Now you can decrement too.

OR-Set      observed-remove set. Each add tags the element with a unique id;
            remove deletes only the ids it has SEEN. Merge = union of adds
            minus union of seen-removes. Re-adding after a concurrent remove
            survives — "add wins."

LWW-Register single value with a timestamp; merge keeps the higher timestamp.
            (Simple, but reintroduces last-write-wins data loss.)

A G-Counter shows the whole idea in miniature:

Node A increments 3x → {A:3, B:0}
Node B increments 2x → {A:0, B:2}
merge (element-wise max) → {A:3, B:2}  → value = 5
Merge it again, or in the other order: still {A:3, B:2} → 5. Convergent.

Collaborative editors (the text-CRDT behind real-time docs), distributed counters (likes, view counts), shopping carts, and presence systems all lean on CRDTs to let many replicas accept writes offline and reconcile automatically.

CRDTs vs vector clocks

They’re not rivals — they’re different layers. A vector clock detects concurrency and hands you two siblings. A CRDT defines a merge so the siblings collapse automatically. Many CRDTs use vector-clock-like causal metadata internally; the CRDT is what you build on top of detection so the application never has to choose a winner by hand.

The price of automatic merging

CRDTs make eventual consistency usable — replicas accept writes independently, tolerate partitions, and converge with no coordination — which is enormous for availability and offline-first apps. But the price is steep and specific. You must model your data as one of these constrained algebraic types; not every operation fits (“set this field to exactly X, overriding all concurrent writers” is fundamentally non-mergeable, so you fall back to LWW and accept loss). The metadata can balloon (tombstones in an OR-Set must linger so a delete isn’t forgotten). And the merge semantics may not match human intent — “add wins” is a policy, and sometimes the user wanted “remove wins.” You buy coordination-free convergence; you pay in expressiveness and bookkeeping.

It actually happened — Amazon Dynamo’s resurrected shopping-cart items

Amazon’s 2007 Dynamo paper — the source of the vector-clock approach this page describes — also documented its most famous quirk. Dynamo kept shopping carts highly available by letting any replica accept writes and merging concurrent versions by union: “add to cart” must never fail, even during a partition. The cost was a genuinely odd user-visible effect — an item you had removed could reappear in your cart. If a “remove item” write happened concurrently with an “add” (or an older replica resurfaced after healing), the union merge favored the add, and the deleted item came back. Amazon judged that an acceptable trade: a resurrected item is a minor annoyance, whereas a dropped add is lost revenue. It’s this page’s thesis made concrete — a merge policy (“add wins,” exactly like an OR-Set) is a deliberate choice about what you’re willing to lose, and it won’t always match what the user meant.

The thread

How do mutually-out-of-sync replicas agree on one value? You can’t use wall-clock time, because the real question is causal, not chronological. Vector clocks give you an honest causal comparison — ordered or concurrent — so you never silently lose a write. CRDTs go further: by constraining the data to types whose merges are commutative, associative, and idempotent, they let replicas converge automatically, turning “eventual consistency” from a polite way of saying “we might drop your data” into a real, well-defined guarantee.

The architect’s lens

Two layered tools for concurrent writes without a single source of truth. Run them through the five questions:

• Why do they exist? Because two replicas can accept writes to the same key concurrently, and wall-clock timestamps lie — clocks drift, so “last write wins” silently discards data. The real question is causal, not chronological, and these tools measure causality instead.
• What problem do they solve? A vector clock detects concurrency honestly — it tells you whether one write happened-before another or whether they’re genuinely concurrent (neither vector dominates), so you never silently lose an update. A CRDT goes further: it defines a merge (commutative, associative, idempotent) so concurrent replicas converge automatically — convergence guaranteed by algebra, not coordination.
• What are the trade-offs? Vector clocks trade a comfortable lie for an uncomfortable truth: the vector grows with the number of writers, the app must handle sibling versions, and pruning is fiddly. CRDTs trade expressiveness — you must model data as constrained algebraic types, metadata can balloon (OR-Set tombstones linger), and the merge policy (“add wins”) may not match human intent.
• When should I avoid them? When a single leader can serialize writes, you don’t need either — order is already defined. And when an operation is fundamentally non-mergeable (“set this field to exactly X, overriding all”), no CRDT fits; you fall back to LWW and accept the loss.
• What breaks if I remove them? Without vector clocks you’re back to last-write-wins and silent lost updates. Without CRDTs every concurrent conflict surfaces as siblings the application must resolve by hand — and Dynamo’s resurrected shopping-cart item is the visible cost of choosing “add wins” anyway.

Check your understanding

1. Why can’t a wall-clock timestamp correctly decide a winner between two writes? What property is it measuring instead of the one that matters?
2. Given two vectors, state the exact test for “A happened before B” versus “A and B are concurrent.”
3. A vector clock tells you a conflict exists but not how to resolve it. Whose job is resolution, and name two real strategies.
4. What three algebraic properties must a CRDT’s merge satisfy, and why does each one matter given an unreliable network?
5. Give one real operation that cannot be modeled as a clean CRDT, and explain what you give up if you force it.

Show answers

1. A wall-clock timestamp measures chronological time, but the real question is causal — “did write A happen before B (could A have influenced B)?” Clocks drift, so “last write wins” by timestamp silently discards a write that was actually concurrent (made independently, in ignorance of the other), which is a genuine conflict no timestamp can adjudicate honestly.
2. A happened before B if every A[i] <= B[i] and at least one A[i] < B[i] (A is dominated by B). If neither vector dominates the other — each has some entry the other lacks — then A and B are concurrent, a real conflict.
3. Resolution is the application’s job — a vector clock only detects the conflict and surfaces both sibling versions. Two real strategies: merge by a domain rule (e.g. union a shopping cart) or ask the user / pick by a business rule (as Dynamo and Riak do).
4. Commutative, associative, and idempotent (a join-semilattice). Each matters because the network is unreliable: commutativity handles messages arriving in any order, associativity handles any grouping of merges (which replica merges first), and idempotence handles duplicate delivery — so convergence is guaranteed by algebra, not coordination.
5. Open-ended — e.g. “set this field to exactly X, overriding all concurrent writers” is fundamentally non-mergeable. If you force it, you fall back to an LWW-Register (keep the higher timestamp), which reintroduces last-write-wins data loss — you give up the CRDT’s guarantee that no concurrent write is silently dropped.