Version Vectors: Making the Conflict Visible

A version vector is a Vector Clocks: Buying Concurrency Detection at O(N) specialised for replicated data. The algorithm is the same — a per-replica counter, element-wise max on merge — and the differences are all about scope and cost.

Per object, not per node. The vector stamps a value, so the counters advance only when *that object* is written. An object written twice carries a tiny vector regardless of how busy the cluster is.

Indexed by replica, not by actor. The components correspond to storage replicas, of which there are three or five, rather than to clients, of which there may be millions. This is the change that makes the mechanism affordable, and it is why version vectors ship in real systems where general vector clocks do not.

Carried by the client through a read-modify-write. The client reads a value with its vector (often opaquely, as a "context"), modifies it, and sends the vector back with the write. That returned vector is the evidence of what the client saw — which is exactly what lets the replica distinguish "this client is updating the version it read" from "this client never saw the version I have".

When a conflict is detected, the store does not choose. It keeps both versions as siblings under the same key, and the next read returns a set rather than a value. This is Dynamo's design and it remains the clearest expression of the idea: the store's job is to preserve, the application's job is to decide.

The consequences are worth being concrete about, because "just keep both" hides real work. Every read path must handle a set of size ≥ 1. Every client must be able to merge, or at least present a choice. And siblings only disappear when somebody resolves them and writes back with the combined context — a read that ignores siblings leaves them in place forever.

That last point produces the characteristic failure: sibling explosion. If nothing resolves, each new conflicting write adds another sibling, objects grow, reads slow down, and eventually a size limit is hit. The pathological version is a client that reads siblings, ignores them, and writes a fresh value *without* the combined context — which conflicts with all of them and adds one more. Resolution must be a real, exercised path, not a TODO.

There is one sibling that behaves unlike the others and catches people: a delete. If one replica deletes an object and another concurrently writes it, the merge sees a conflict between "gone" and a value. Deleting the record entirely loses the fact that a delete happened, so the write resurrects the object at the next anti-entropy pass. The fix is a tombstone — a deletion recorded as a version, with its own place in the vector — which then has to be garbage-collected safely, and that is a coordination problem of its own (Anti-Entropy: Repairing Divergence Nobody Reported).

A plain version vector has a defect that shows up under load, and the fix is the reason modern implementations look more complicated than the textbook version.

The issue: a version vector summarises a *set* of writes, but a stored value is a *single* write. When two clients write concurrently against the same context, the replica must represent "these two specific writes are concurrent" — and a vector of maxima cannot distinguish "I have replica A's writes 1 and 2" from "I have replica A's write 2 only". The practical consequence is false conflicts: sequential writes from the same client can be reported as concurrent, and each one spawns a sibling. Under a workload of repeated updates to one key, siblings accumulate for no semantic reason at all.

Dotted version vectors fix this by attaching, to each stored version, both the vector (what it has seen) and a dot — the single (replica, counter) pair identifying the write that produced it. Comparison then asks whether one version's dot is contained in the other's vector, which distinguishes "this write is included in what you have" from "this write is a branch". The result is that the sibling count reflects genuine concurrency rather than an artefact of the encoding.

The practical advice is short: if you are implementing this yourself, implement dotted version vectors, and test the specific case of a client doing repeated sequential writes to one key. If a plain version vector produces siblings there, your users will see them constantly.

The value of version vectors is not that they solve conflicts. It is that they convert an invisible, unrecoverable loss into a visible, deferrable decision — and the difference between those two situations is enormous operationally.

With detection you get: a conflict *count* you can put on a dashboard and argue about; both values preserved, so any later decision is still possible; and an explicit place in the code where the resolution rule lives, which can be reviewed and tested. Without it you get a number that is always zero and a support queue.

What you do not get is the rule itself. A version vector will tell you that "Q3 Plan" and "Q3 Planning" are concurrent; it has no opinion about which a user wants, and cannot have one. That is Only the Application Knows What the Merge Means. Nor does it help with causality that travelled outside the system, and nor does it extend across objects — two objects with an invariant between them are not protected by per-object vectors, which is why multi-object invariants need coordination rather than better metadata (Start From the Invariant, Not From the Architecture).