Vector Clocks

Overview

A vector clock is a per-version map from node identifier to counter that captures causality. It answers a question timestamps cannot: did this write see that earlier write, or did they happen independently? Dynamo and Riak used it to detect conflicting updates.

How it works

Each replica increments its own counter on a local update and takes the element-wise maximum when merging.

A writes:    {A:1}
B reads, writes: {A:1, B:1}   (descends from A's)
C reads {A:1}, writes: {A:1, C:1}
{A:1,B:1} vs {A:1,C:1}: neither dominates -> concurrent
client merges, writes {A:1,B:1,C:1,D:1}

Comparison rule: V1 precedes V2 when every counter in V1 is at most that in V2 and one is smaller. If neither precedes the other, both are kept as siblings. The reader receives all siblings plus the vector context and must send that context back with the merged write.

Pitfalls

• Vectors grow with every distinct writer. Servers writing on behalf of clients, rather than clients themselves, keep this bounded; dotted version vectors reduce sibling noise.
• Truncating old entries to save space can mislabel causal versions as concurrent.
• Without a merge strategy, such as set union or CRDTs, siblings accumulate forever.
• Do not confuse with Lamport clocks, which give a total order but cannot detect concurrency.

Key takeaways

• Vector clocks detect concurrency; they do not resolve it.
• Pair with an application merge function or a CRDT.
• Keep the writer set small and use dotted version vectors where available.