Notesreplication🌱 seedling
Version Vector
Also: Dotted Version Vector · Siblings · Version Number
One counter per replica attached to each key's value. Comparing two version vectors tells you whether one write overwrote the other or whether they were concurrent and both must be kept.
Why it exists
Timestamps can't tell "overwrote" from "didn't know about". To avoid silently dropping writes you need to know whether a writer had seen the previous version: Happens-Before.
How it works
- Single replica: a version number per key. A write says which version it read. If that's the latest, it replaces it; if older, it's concurrent and both values are kept as siblings.
- Many replicas: each keeps its own counter for the key; the set of counters is the version vector.
- Compare vectors: every counter ≥ means descends (overwrite); each ahead somewhere means concurrent (siblings).
- A reader merges siblings and writes back with the merged vector, replacing them.
- Dotted version vectors add per-write dots so duplicate or retried writes don't multiply siblings.
Trade-offs
| Gains | Costs |
|---|---|
| no acknowledged write silently lost | application must merge siblings |
| exact concurrency detection | metadata grows with replicas; truncation loses precision |
In practice
- Dynamo used vector clocks, truncated at about ten entries; its shopping cart merged siblings by union, so deleted items could resurface.
- Riak 2.0 added dotted version vectors to curb sibling explosion.
Pitfalls
- Merging by union can't express deletes: removed items come back unless you keep tombstones.
Connections
- Part of
- Write Conflict
- Learn first
- Happens-Before
- Contrasts with
- Last Write Wins
- In real systems
- Dynamo
Recall
These cards are also in your review deck, scheduled with spaced repetition.