Vector Clock

A vector clock is a per-node array of counters used to determine the partial causal ordering of events in a distributed system, distinguishing causal dependency from true concurrency without relying on synchronised wall-clock time.

Practical example

Riak returns a causal context (a Dotted Version Vector) with every GET, which the client must echo back on PUT so the server can tell whether the write updates a known version or is a genuinely concurrent sibling requiring reconciliation.

A vector clock is implemented as an array or map VC[N], where N is the number of nodes (or replicas, or actors) in the system. Each node maintains its own local counter within the vector. On every local event, a node increments only its own index: VC[self]++. On message send, the sender attaches its current full vector to the payload. On receipt, the receiver merges the incoming vector with its own by taking the element-wise maximum, then increments its own index: VC_local[i] = max(VC_local[i], VC_remote[i]) for all i, followed by VC_local[self]++.

The critical operation is the causal comparison between two vectors A and B. Three outcomes are possible: A happened-before B (every element of A is <= the corresponding element of B, with at least one strict inequality), B happened-before A (the inverse), or A and B are concurrent (neither dominates — some elements of A are greater, others of B are greater). This third case is the entire point of the structure: it is a mathematically rigorous signal that two writes occurred without either observer having knowledge of the other, and therefore represent a genuine conflict requiring application-level or CRDT-based resolution, rather than a timestamp race condition.

Storage growth: the vector’s size is proportional to the number of distinct writers that have ever touched an object, not the number of nodes in the cluster. In systems like the original Amazon Dynamo, unbounded client-side actor proliferation caused vector clock bloat, requiring pruning heuristics (e.g., dropping the oldest entry when a size threshold is exceeded), which introduces a small risk of false concurrency detection after pruning.
Comparison cost: determining causality is an O(N) operation per comparison, which becomes expensive on read-repair or anti-entropy paths across replica sets with high actor cardinality.
Contrast with HLC: a vector clock captures true causality (a partial order) at the cost of size and comparison complexity; a Hybrid Logical Clock provides a compact, comparable scalar-like timestamp but sacrifices precise concurrency detection — HLC tells you an approximate global order, a vector clock tells you exact causal dependency.

In production systems, vector clocks (or their dotted variants, such as Dotted Version Vectors, which fix the sibling explosion problem inherent to naive vector clocks under concurrent overwrites) are typically embedded as per-object metadata rather than per-message metadata. Riak’s use of DVVs and the object context field returned to clients on GET, which must be echoed back on PUT, is a canonical example: the client is effectively carrying causal history across the wire so the server can correctly detect whether a write is an update to a known version or a genuinely concurrent sibling requiring reconciliation.