Distributed systems
Part 4 of 6 · Time, Clocks & OrderingVector Clocks vs Version Vectors - Detecting Concurrent Writes, Siblings & Dotted Version Vectors
Vector clock rules and four-way compare; runnable Dynamo-style sibling store with context and merge; vector clocks vs version vectors vs client-id vclocks vs dotted version vectors; runnable LWW vs per-server VV (lost write) vs DVV (siblings); size growth and pruning; LWW vs siblings vs CRDTs vs consensus; Dynamo, Riak 2.0, Cassandra.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
When are two vector clocks concurrent?
Answer
When neither dominates entry by entry.
L2
What is the difference between a vector clock and a version vector?
Answer
A vector clock orders events among processes. A version vector orders versions of one data item, with one entry per replica.
L3
What does the client send on the next put?
Answer
The merged context from the siblings it read, so the new clock descends those versions.
L4
Why did Riak move to dotted version vectors?
Answer
Server-id vectors cannot separate concurrent writes on the same replica. Client-id vectors grow without bound. A dot plus a context stays small and precise.
L5
When are CRDTs a better fit than siblings?
Answer
When the merge is mathematical, as with counters, sets, registers, and maps, so the application never sees siblings.
L6
What does pruning risk?
Answer
Lost causal information: later comparisons can report false siblings, or treat a newer version as older.
L7
What did the example server version vector drop?
Answer
milk,eggs. The later stamp S:3 dominated S:2 even though the writers had not seen each other. The dotted version vector kept both.
Failure modes
Same-server version vectors hide a concurrent write
Both clients read S:1. The second coordinated write is stamped S:3 and the S:2 version is discarded.
Siblings with no merge
Every read returns more versions. Riak operators capped sibling counts and alerted on them.
Pruned clocks change the compare
Dropping entries can turn a causal pair into an apparent conflict, or the reverse.
Misconceptions
A version vector with one entry per server detects every concurrent write.
Two writes coordinated by the same server can look ordered. Dotted version vectors keep the dot separate from the context.
Union is a complete cart merge.
It is safe for adds. Deletes reappear unless removes are tracked.
Vector clocks are the right tool for a balance.
They report the conflict after both writes exist. Uniqueness and money want a leader or consensus.
Interviewer traps
Using client-id vector clocks and ignoring growth.
Say the vector grows with writers, and pruning changes the compare. Prefer a server-sized dotted version vector.
Calling last-writer-wins concurrency detection.
Show the example where milk,eggs disappears.
Design scenario
Same prompt for every reader.
Requirements
Concurrent adds both survive. A remove must not be resurrected by a sibling that still lists the item.
Traffic / scale
The lesson trace: milk, then concurrent milk+eggs and milk+bread.
Latency
The vector or dot rides on the replica request. There is no consensus round trip on the add path.
Consistency
Concurrent versions stay siblings or merge by a CRDT. A per-server version vector is not enough.
Availability
The cart accepts writes on a minority of replicas. A balance would not.
Failure assumptions
- Two clients can read the same context and write through different replicas.
- Two clients can write through the same replica without seeing each other.
- Clocks will be pruned or bounded.
Constraints
- Do not resolve the cart with wall-clock last-writer-wins.
- Do not use a plain per-server version vector as the only concurrency check.
Prompt
A shopping cart is written by many clients through three replicas. Deletes must not reappear.
API
What does get return, and what must put include?
Data
Whose counters are in the clock, and how do you represent a remove?
Architecture
Where would a CRDT replace siblings, and where would a leader replace both?
What happens to two writes that did not see each other
Prefer
Keep siblings, or merge with a CRDT
If neither clock dominates, both values survive until a reader merges and writes the merged context back.
- The cart example keeps milk+eggs and milk+bread, then a union write collapses them.
- Dotted version vectors detect the same-server concurrent case.
- CRDTs merge counters and sets without showing siblings to the app.
Alternative
Let one timestamp win
Last-writer-wins and a plain per-server version vector both drop an edit that was concurrent.
- The example LWW keeps only milk,bread.
- The server version vector lets the second write dominate the first.
- Money and inventory should be serialized, not merged after the fact.
From two reads to one merged version
The shopping-cart trace on this page. Union is safe for adds and resurrects deletes.
- 1
Write and return a context
Alice writes milk via replica A. The clock is A:1. A get returns the values plus the merged context. - 2
Two clients write that same context
Alice adds eggs via A (A:2). Bob adds bread via B (A:1, B:1). Neither clock dominates. - 3
Keep both siblings
The store drops only versions the new clock descends. Concurrent ones stay. - 4
Merge and write back
The next reader unions the sets and puts with context A:2, B:1. The new clock A:3, B:1 dominates both.
Overview
A vector clock keeps one counter per participant instead of one counter total. Comparing two vectors entry by entry tells you exactly one of four things: equal, before, after, or concurrent. That last answer is the whole point: it lets a replicated store notice that two writes did not see each other and keep both (as siblings) for the application or a CRDT to merge, instead of silently dropping one. The engineering work is in whose counters go into the vector (clients, servers, or dots), how big it gets, and what you do when you prune it.
How vector clocks work
- Each participant i keeps a vector V with an entry per participant, all starting at 0.
- On a local event or send, increment your own entry V[i].
- Messages carry the whole vector.
- On receive, take the element-wise max with the incoming vector, then increment V[i].
- Compare:
V(a) <= V(b)entry-wise (and not equal) means a -> b; if neither dominates, a || b.
Unlike Lamport clocks, this is an if and only if: V(a) < V(b) exactly when a happens-before b.
Decisions
- 1
Step 1: Alice writes milk via replica A, clock A:1
- nextStep 2: Alice and Bob both read milk with context A:1
- 2
Step 2: Alice and Bob both read milk with context A:1
- nextStep 3a: Alice writes milk+eggs via A, clock A:2
- nextStep 3b: Bob writes milk+bread via B, clock A:1 B:1
- 3
Step 3a: Alice writes milk+eggs via A, clock A:2
- nextStep 4: compare A:2 vs A:1 B:1
- 4
Step 3b: Bob writes milk+bread via B, clock A:1 B:1
- nextStep 4: compare A:2 vs A:1 B:1
- ?
Step 4: compare A:2 vs A:1 B:1
- neither dominatesStep 5: concurrent, keep both as siblings
- 6
Step 5: concurrent, keep both as siblings
- nextStep 6: next reader merges (union) and writes with context A:2 B:1
- 7
Step 6: next reader merges (union) and writes with context A:2 B:1
- nextStep 7: new clock A:3 B:1 dominates both, siblings collapse
- 8
Step 7: new clock A:3 B:1 dominates both, siblings collapse
Lesson map
Vector Clocks vs Version Vectors - Detecting Concurrent Writes, Siblings & Dotted Version Vectors
Vector clock rules and four-way compare; runnable Dynamo-style sibling store with context and merge; vector clocks vs version vectors vs client-id vclocks vs dotted version vectors; runnable LWW vs per-server VV (lost write) vs DVV (siblings); size growth and pruning; LWW vs siblings vs CRDTs vs consensus; Dynamo, Riak 2.0, Cassandra.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB w1["Step 1: Alice writes milk via replica A, clock A:1"] r1["Step 2: Alice and Bob both read milk with context A:1"] wa["Step 3a: Alice writes milk+eggs via A, clock A:2"] wb["Step 3b: Bob writes milk+bread via B, clock A:1 B:1"] cmp["Step 4: compare A:2 vs A:1 B:1"] sib["Step 5: concurrent, keep both as siblings"] m["Step 6: next reader merges (union) and writes with context A:2 B:1"] one["Step 7: new clock A:3 B:1 dominates both, siblings collapse"] w1 -->|continues| r1 r1 -->|continues| wa r1 -->|continues| wb wa -->|continues| cmp wb -->|continues| cmp cmp -->|neither dominates| sib sib -->|continues| m m -->|continues| one
A sibling-keeping store (runnable)
# Vector clocks: compare, merge, and a Dynamo/Riak-style store that keeps siblings
# for concurrent writes instead of silently picking one.
def compare(a: dict, b: dict) -> str:
keys = set(a) | set(b)
a_ge = all(a.get(k, 0) >= b.get(k, 0) for k in keys)
b_ge = all(b.get(k, 0) >= a.get(k, 0) for k in keys)
if a_ge and b_ge: return "equal"
if a_ge: return "after" # a descends from b
if b_ge: return "before"
return "concurrent"
def merge(a: dict, b: dict) -> dict:
return {k: max(a.get(k, 0), b.get(k, 0)) for k in set(a) | set(b)}
class Store:
"""One key, many versions. A write carries the context (clock) the client last read."""
def __init__(self):
self.versions = [] # list of (clock, value)
def get(self):
ctx = {}
for clk, _ in self.versions:
ctx = merge(ctx, clk)
return [v for _, v in self.versions], ctx
def put(self, node: str, ctx: dict, value):
clk = dict(ctx)
clk[node] = clk.get(node, 0) + 1
# Drop versions the new write has seen (they are 'before' it); keep concurrent ones.
self.versions = [(c, v) for c, v in self.versions if compare(clk, c) != "after"]
self.versions.append((clk, value))
return clk
s = Store()
_, ctx0 = s.get()
s.put("A", ctx0, {"milk"}) # Alice adds milk via replica A
vals, ctx1 = s.get()
print("after write 1:", vals, ctx1)
# Alice (via A) and Bob (via B) both read ctx1, then write without seeing each other.
s.put("A", ctx1, {"milk", "eggs"})
s.put("B", ctx1, {"milk", "bread"})
vals, ctx2 = s.get()
print("siblings :", [sorted(v) for v in vals], "context", dict(sorted(ctx2.items())))
print("compare :", compare(s.versions[0][0], s.versions[1][0]))
# The next reader resolves: for a cart, union is a sensible merge (deletes need tombstones/CRDTs).
merged = set().union(*vals)
s.put("A", ctx2, merged)
vals, ctx3 = s.get()
print("resolved :", [sorted(v) for v in vals], dict(sorted(ctx3.items())))Output:
after write 1: [{'milk'}] {'A': 1}
siblings : [['eggs', 'milk'], ['bread', 'milk']] context {'A': 2, 'B': 1}
compare : concurrent
resolved : [['bread', 'eggs', 'milk']] {'A': 3, 'B': 1}This is the Dynamo shopping-cart model: a get returns all sibling values plus a merged context; the client reconciles and passes that context back on put. Note that union is safe for adds but resurrects deleted items, which is why Dynamo's paper mentions deleted items reappearing and why later systems moved to CRDTs (an OR-Set tracks removes properly).
Vector clocks vs version vectors vs dotted version vectors
These terms get mixed up in interviews, so pin them down:
| Structure | Entries are | Tracks | Strength | Weakness |
|---|---|---|---|---|
| Vector clock (Fidge/Mattern) | One per process, all events | Causality between arbitrary events | Exact happens-before | Size grows with participants |
| Version vector | One per replica (server) | Causality between versions of data | Small (bounded by replica count) | Cannot distinguish concurrent writes coordinated by the same server without help |
| Client-id vector clock (early Riak style) | One per client actor | Causality of each client's writes | Correct concurrency detection | Grows with number of clients; needs pruning |
| Dotted version vector (DVV) | Version vector + a single "dot" (replica, counter) per value | Which exact write produced each sibling | Server-sized and still precise; no false conflicts or lost writes | More complex to implement |
Why per-server version vectors are not enough (runnable)
Two clients read the same version and write concurrently, both through replica S. A plain per-server version vector stamps the second write {S:3}, which dominates the first write's {S:2}, so the first write is discarded as "old" even though it was concurrent. Dotted version vectors keep the writer's causal context separate from the new write's dot, so the server can see that neither write covered the other.
// Two clients write the same key concurrently through the SAME server replica "S".
// Compare: wall-clock LWW, a per-server version vector, and a dotted version vector (DVV).
type VV = Record<string, number>;
const covers = (ctx: VV, node: string, n: number): boolean => (ctx[node] ?? 0) >= n;
// --- 1) LWW: higher timestamp wins (example timestamps, Bob's clock happens to be later)
const lwwWinner = [{ v: "milk,eggs", ts: 1001 }, { v: "milk,bread", ts: 1002 }]
.reduce((a, b) => (b.ts > a.ts ? b : a));
console.log(`1) LWW keeps only [${lwwWinner.v}] -> eggs lost`);
// --- 2) Per-server version vector: server bumps ITS counter on every write it coordinates.
{
let serverCounter = 0;
let versions: { vv: VV; v: string }[] = [{ vv: { S: 1 }, v: "milk" }];
serverCounter = 1;
const ctx: VV = { S: 1 }; // both clients read "milk" with context {S:1}
for (const v of ["milk,eggs", "milk,bread"]) {
serverCounter += 1;
const vv: VV = { ...ctx, S: serverCounter };
// keep only versions NOT dominated by the new clock
versions = versions.filter((x) => !Object.keys(x.vv).every((k) => (vv[k] ?? 0) >= x.vv[k]!));
versions.push({ vv, v });
}
console.log(`2) server VV keeps [${versions.map((x) => x.v).join(" | ")}] -> {S:3} 'dominates' {S:2}, eggs lost`);
}
// --- 3) Dotted version vector: each version = (dot, causal context it was written with).
{
type Ver = { dot: [string, number]; ctx: VV; v: string };
let counter = 1;
let versions: Ver[] = [{ dot: ["S", 1], ctx: {}, v: "milk" }];
const readCtx = (): VV => {
const c: VV = {};
for (const x of versions) c[x.dot[0]] = Math.max(c[x.dot[0]] ?? 0, x.dot[1]);
return c;
};
const put = (ctx: VV, v: string): void => {
counter += 1;
// a version is obsolete only if the writer's context actually covers its dot
versions = versions.filter((x) => !covers(ctx, x.dot[0], x.dot[1]));
versions.push({ dot: ["S", counter], ctx, v });
};
const ctx = readCtx(); // {S:1}
put(ctx, "milk,eggs");
put(ctx, "milk,bread");
console.log(`3) DVV keeps [${versions.map((x) => x.v).join(" | ")}] -> concurrency detected, siblings`);
const merged = [...new Set(versions.flatMap((x) => x.v.split(",")))].sort().join(",");
put(readCtx(), merged); // a reader merges and writes back with context {S:3}
console.log(` after merge-write: [${versions.map((x) => x.v).join(" | ")}]`);
}
// --- Size: client-id vector clocks are exact but grow with the number of writers.
const clients = [10, 1_000, 100_000];
for (const c of clients) {
console.log(`vector size with ${String(c).padStart(6)} distinct clients: client-id VC=${c} entries, server-id VV/DVV<=3 entries (3 replicas)`);
}Output:
1) LWW keeps only [milk,bread] -> eggs lost
2) server VV keeps [milk,bread] -> {S:3} 'dominates' {S:2}, eggs lost
3) DVV keeps [milk,eggs | milk,bread] -> concurrency detected, siblings
after merge-write: [bread,eggs,milk]
vector size with 10 distinct clients: client-id VC=10 entries, server-id VV/DVV<=3 entries (3 replicas)
vector size with 1000 distinct clients: client-id VC=1000 entries, server-id VV/DVV<=3 entries (3 replicas)
vector size with 100000 distinct clients: client-id VC=100000 entries, server-id VV/DVV<=3 entries (3 replicas)Expected1) LWW keeps only [milk,bread] -> eggs lost 2) server VV keeps [milk,bread] -> {S:3} 'dominates' {S:2}, eggs lost 3) DVV keeps [milk,eggs | milk,bread] -> concurrency detected, siblings after merge-write: [bread,eggs,milk] vector size with 10 distinct clients: client-id VC=10 entries, server-id VV/DVV<=3 entries (3 replicas) vector size with 1000 distinct clients: client-id VC=1000 entries, server-id VV/DVV<=3 entries (3 replicas) vector size with 100000 distinct clients: client-id VC=100000 entries, server-id VV/DVV<=3 entries (3 replicas)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Riak 2.0 introduced dotted version vectors (dvv_enabled) for exactly this reason: client-id vector clocks grew without bound and needed pruning, while plain server-id vectors produced lost updates or false siblings.
Size growth and pruning
- Growth: vectors keyed by client or process id grow with every new writer. In a system with millions of users that is unworkable.
- Pruning: the Dynamo paper describes truncating the clock when it exceeds a threshold (it mentions about 10 entries), dropping the oldest entry by a stored timestamp. Pruning loses information: later comparisons may call two causally ordered versions concurrent (false siblings) or, worse, mis-order them.
- Server-keyed structures (version vectors, DVVs) bound the size by replica count, which is why modern designs use them.
- Interval tree clocks and other research structures handle dynamic membership without a global id space; they are rarely needed in application design but good to name.
Vector clocks vs LWW vs CRDTs
| Strategy | Concurrent writes | Who resolves | Metadata | Best for |
|---|---|---|---|---|
| LWW (timestamp) | One survives, other silently lost | Store, automatically | Tiny | Idempotent overwrites, caches, sensor readings where latest is fine |
| Vector clock + siblings | All survive as siblings | Application on read | O(writers) or O(replicas) | Data with domain-specific merges (carts, documents) |
| CRDT | Merged automatically by math | The data type | Type-dependent, sometimes large | Counters, sets, maps, collaborative text |
| Consensus / single leader | Prevented (serialized) | The leader | Log index | Money, inventory, uniqueness constraints |
What happens if you choose otherwise
- LWW where users edit the same object offline: lost edits nobody notices until a customer complains.
- Siblings without a merge function: sibling explosion; every read returns more versions, and objects grow until reads time out. Riak operators learned to cap sibling counts and alert on them.
- Client-id vectors at scale: unbounded metadata per key, then pruning that silently changes semantics.
- Vector clocks for money: you will detect the double spend after it happened; use a leader or consensus for invariants that must never be violated.
Real systems
- Amazon Dynamo (2007): vector clocks, sibling versions, client reconciliation, clock truncation.
- Riak: client vclocks, then dotted version vectors in 2.0, plus Riak data types (CRDTs).
- Voldemort: vector-clock versioning in the Dynamo tradition.
- Cassandra: chose per-cell LWW timestamps instead, trading conflict detection for simplicity; lightweight transactions (Paxos) when you need compare-and-set.
Interview Q&A
How do you decide whether two vector clocks are concurrent?
Answer
Compare entry by entry. If every entry of A is >= B's and at least one is greater, A is after B. If neither dominates, they are concurrent.
What's the difference between a vector clock and a version vector?
Answer
A vector clock orders events among processes; a version vector orders versions of a replicated data item, with one entry per replica. Version vectors are what storage systems actually keep.
Why did Riak move to dotted version vectors?
Answer
With server-id version vectors, concurrent writes coordinated by the same server can't be told apart, causing lost updates or false siblings; with client-id vectors, size grows without bound. DVVs track the exact write (the dot) separately from its causal context, keeping vectors small and precise.
When would you prefer CRDTs over siblings?
Answer
When there is a well-defined automatic merge (counters, sets, registers, maps) so the application never sees siblings. Siblings are better when merging needs domain judgment.
What does pruning a vector clock risk?
Answer
Losing causal information, so later comparisons may report concurrency where there was none (false siblings) or treat a newer version as older.
Why is a union merge unsafe for deletes?
Answer
Union treats absence as 'not yet added', so a removed item reappears when another sibling still contains it. An OR-Set or another CRDT tracks removes. The Dynamo paper notes deleted items reappearing.
When would you refuse vector clocks for money?
Answer
You detect a double spend after both writes exist. Invariants that must never be violated need a single leader or consensus, which prevents the conflict instead of merging it.
What does a Dynamo-style get return?
Answer
All sibling values plus one merged context. The client reconciles and passes that context back on put so the next write descends what it saw.
Check yourself
Take two versions of one key, each with a three-replica vector. Decide equal, before, after, or concurrent by hand. If they are concurrent, say whether the product should keep siblings, apply a CRDT, or refuse the second write with a leader.
Elsewhere in the library
These pages stay as they are. This lesson only points at them: Leaderless Replication — N/R/W Quorums, Hinted Handoff, Read Repair & Anti-Entropy, Multi-Leader & Active-Active — Conflict Detection, LWW, CRDTs & Home Regions, CRDTs — Conflict-Free Types, Convergence & When Consensus Wins, Database Replication — Leader-Follower, Multi-Leader & Leaderless Quorums.