Vector clocks and causality

The problem it solves

Two replicas receive writes to the same key at nearly the same moment. Later they exchange them, and something must decide what the value is now. The universal default is to compare timestamps and keep the later one — last-write-wins.

There are two problems with that, and the second is the serious one. The first is that machine clocks disagree: a few milliseconds under good NTP, hundreds under bad, and occasionally they step backwards. So “later” is not reliably later. The second is deeper: even with perfect clocks, a timestamp cannot distinguish two writes that happened concurrently from two writes where one saw the other. Those are entirely different situations. In the second, the newer write is a legitimate update and should win. In the first, there are two independent intentions, and picking one by timestamp silently deletes a user’s acknowledged work.

The mechanism

Causality, not time, is the right relation. Lamport’s happens-before: event A happens-before B if they are on the same node in order, or if A is the sending of a message that B received, or by transitivity. If neither A happens-before B nor B happens-before A, they are concurrent — and concurrency is a real answer, not an inability to decide.

A vector clock tracks this exactly. Each replica keeps a counter per replica. On a local write it increments its own counter; when it receives a value it takes the element-wise maximum and increments its own. Comparing two vectors gives one of three verdicts:

• Every element of A is ≤ B, and at least one is strictly less: A happens-before B. B is the newer version; take it.
• The mirror image: B happens-before A.
• Some elements greater, others less: concurrent. Neither saw the other, and no rule internal to the system can rank them.

That third case is what a timestamp can never express. The vector converts “which is later?” — unanswerable — into “did either see the other?” — answerable from data the system already has.

What to do with a detected conflict is then an application decision. Keep both as siblings and let the application merge (Riak’s model, and shopping carts are the canonical example: union the items). Or use a data type that merges automatically — a CRDT — which is the modern version of the same idea. Or resolve by timestamp anyway, which is a legitimate choice provided you say out loud that you are choosing to lose data.

What the simulation shows

Concurrent writes go to different replicas with realistic clock skew between machines, and a partition to make the concurrency unavoidable.

Run timestamp ordering and read the panel counting concurrent writes against how many were noticed. Every genuinely concurrent write is resolved by comparing two machines’ clocks, and one update is discarded, silently, every time. There is no error, no log line, and no metric in a real system that would tell you.

Now vector clocks with siblings kept. Every concurrent write is detected, and none is thrown away. The merge panel shows two writes to two replicas and the reconciliation between them.

Two more things worth checking. Most writes are not conflicts: when one write saw the other, the vector says so and the newer simply supersedes, with no siblings and no application involvement. Vector clocks are not a tax on every write, only on the genuinely ambiguous ones.

And the trap: detect concurrency and then resolve it by timestamp anyway. You now pay for the vectors — storage, transmission, comparison — and keep the data loss. If you are not going to handle siblings, be honest about that; it is a cheaper wrong answer than the expensive wrong answer.

The numbers worth carrying

A vector clock is one counter per writer, and its size is the number of writers that have ever touched the key. With a fixed set of replicas that is small and bounded. With per-client vectors it grows without limit, which is why Dynamo used node-level vectors and pruned old entries with a timestamp, accepting a small chance of false concurrency in exchange for a bound.

NTP-synchronised clocks are typically within 1–10 ms in a datacentre and can be much worse across the internet or on a VM under contention. Any conflict window shorter than clock skew is decided by noise. Spanner’s TrueTime attacks this directly by exposing an uncertainty interval and waiting it out before committing — buying real ordering with real latency, which is the honest price.

Version vectors — the same structure applied to replicas of an object rather than to events — are what you almost always want in practice, and the terminology distinction is worth having ready.

Where it breaks down

Siblings must be handled. A system that returns two values to an application unprepared for them will have an application that picks the first one, and you have re-implemented last-write-wins with more steps. The application needs a merge function, and writing one is real work.

Unbounded growth. Per-client vectors grow with the client count. Pruning is required and pruning can create false positives (reporting concurrency where there was causality), which is a safe direction to err in — extra siblings, never lost writes.

Not a total order. Vector clocks tell you the partial order of causality. They cannot give you a global sequence for, say, an audit log. That needs consensus — see Raft — or a hybrid logical clock, which combines physical time with a logical counter and is what many modern systems use.

They do not prevent conflicts. They detect them. Preventing them means a single writer per key, which means partitioning or leadership, which costs availability during a partition — see CAP in practice.

What people get wrong

“Use timestamps, clocks are synchronised now.” They are close, not equal, and closeness is not ordering. More importantly, even perfect clocks cannot represent concurrency.

“Last-write-wins is simple.” It is simple and it is a decision to lose data. Say the second half whenever you say the first.

“Vector clocks solve conflicts.” They detect them. Resolution is yours.

“CRDTs make this unnecessary.” CRDTs make resolution automatic for data types that admit a commutative merge — counters, sets, some sequences. They are a wonderful answer when your data fits, and most business objects do not fit without design work.

In production

Riak exposed vector clocks and siblings directly, and its shopping-cart example remains the clearest teaching case. DynamoDB chose last-write-wins with a conditional-write escape hatch, which is the pragmatic industrial position. Cassandra is last-write-wins on cell timestamps, which is why its documentation warns about clock skew so insistently. CRDT libraries — Automerge, Yjs — are how collaborative editors solve the same problem, and CockroachDB and YugabyteDB use hybrid logical clocks to get a usable ordering without Spanner’s atomic hardware.

The design question that generalises: can two clients modify the same object concurrently? If no — because a partition key or a leader serialises them — none of this is needed. If yes, you need detection, and then you need a merge. Deciding which of those you are in is the first move.

The follow-up questions

“Two replicas take conflicting writes. Who wins?” — If the answer is “the later timestamp”, the follow-up is “how do you know which is later”, and there is no good answer.

“What is a vector clock?” — Counter per replica, element-wise max on merge, three-way comparison, and concurrency as a first-class outcome.

“How big does it get?” — One entry per writer; bounded with node-level vectors, unbounded with client-level, hence pruning.

“When would you use last-write-wins anyway?” — When the data is a cache, a presence flag, or telemetry, and losing one of two concurrent updates costs nothing. Saying when it is fine is as valuable as knowing when it is not.