What is a vector clock?

A Lamport timestamp gives every event a number, so that if one event could have caused another, the cause has the smaller number. The reverse is not true. A smaller number does not prove that one event came before the other; the two may have happened independently.

Friedemann Mattern pointed out that this loses information. Squeezing a partial order of events onto a line of integers makes events that were concurrent look as if they happened in a definite order. That does not matter for some uses, but it matters a great deal for sync. An offline app needs to know whether an incoming change replaces the local one, which is safe to apply, or was made concurrently with it, which is a conflict.

Vector clocks answer that question. Mattern and, independently, Fidge proposed them in 1988.

Each process keeps a vector with one entry per process. Mattern’s rules are short:

1. Each process increments its own entry by one whenever an event happens.
2. When it sends a message, it attaches its whole vector.
3. When it receives a message, it takes the componentwise maximum of its own vector and the one it received, entry by entry.

The result is that each process carries its best knowledge of how far every other process has got. Take two phones, Ana’s and Ben’s. Ana makes an edit, so her entry rises. If she then syncs with Ben, his vector absorbs her entry and he knows about her edit. If instead Ben edits while they are apart, each vector has moved ahead in a different entry, and neither knows of the other’s change.

Two vectors compare entry by entry:

• If every entry in A is less than or equal to the matching entry in B, and they are not identical, then A happened before B.
• If the reverse holds, B happened before A.
• If each has at least one entry larger than the other’s, the two are concurrent.

Mattern showed that this comparison captures causality exactly: one event happened before another if and only if its vector is smaller. That is the property a single counter lacks, and it is why vector clocks can detect conflicts rather than hide them.

Databases use the same structure to track versions of data rather than events. Mattern credits Parker and colleagues with version vectors, in which each copy of a file counts the updates made at each site. If two copies’ vectors are concurrent, they were modified independently and a conflict is flagged. If not, the copies can be reconciled without further action, and the result takes the maximum of both vectors.

Amazon’s Dynamo paper used vector clocks this way. Each version of an object carried a list of (node, counter) pairs. If one version’s counters were all less than or equal to another’s, it was an ancestor and could be forgotten. Otherwise the versions were in conflict, and both were returned to the application to reconcile.

Riak’s documentation describes the same behaviour. When vector clocks cannot decide which value is current, Riak can keep both as siblings for the application to resolve.

The weakness is size. The vector needs an entry for every participant that has written, so it grows with the number of nodes. The authors of the hybrid logical clock paper call that space requirement prohibitive.

Real systems cut corners, with consequences:

• Truncation. Dynamo dropped the oldest entry once a clock reached a threshold, which its authors gave as, say, ten pairs. They noted this could make reconciliation less accurate, because ancestry could no longer be worked out exactly.
• Sibling growth. Riak found that with plain vector clocks, sibling values could be duplicated depending on delivery order, leading to what it calls sibling explosion. From version 2.0 it recommends dotted version vectors, which tag each value with the update that created it.

For mobile apps the size question is practical. Every device that writes becomes an entry, and devices come and go. Some libraries use a lighter structure for the part they need.

Yjs is one example. It keeps a state vector holding the next expected clock from each client, and sends it to another client so that only the missing changes come back. The Yjs README says this is similar to a version vector, but is used only to describe the state of the local document, not to track causality.

Use a vector clock, or a version vector, when you must tell a replacement apart from a conflict. That includes keeping both versions for a person to choose, merging concurrent changes, and working out which changes a peer is missing.

If the rule is last writer wins, a single totally ordered timestamp is enough, because concurrent writes are resolved by discarding one anyway. Conflict-free replicated data types sit in between: Shapiro and colleagues build their multi-value register on version vectors precisely because a single timestamp cannot detect concurrency.