Vector Clocks Explained with a Worked Example

A vector clock is a small piece of bookkeeping that lets a distributed database answer one question: did these two versions of the same record happen one after the other, or did they happen at the same time on different machines?

That question matters because the answer decides whether you can safely throw one version away. If write B came after write A, B contains everything A had, so keeping B is correct. If A and B happened independently on two machines that could not see each other, then throwing either one away silently deletes a user's data.

This article walks through a full vector clock example, one step at a time, with the actual numbers.

Why wall clock timestamps are not enough

The obvious way to order two writes is to attach a timestamp to each one and keep the newer one. This is called last write wins, and it is what many systems do by default.

It breaks for two reasons.

The first is that server clocks drift. Two machines in the same data center can disagree by tens or hundreds of milliseconds. If two writes land inside that window, the timestamps tell you nothing reliable about which one actually happened first.

The second reason is more serious. Even with perfect clocks, "later" is not the same as "aware of". Two users can add different items to the same shopping cart at the same moment on two different replicas. One write has a later timestamp, but it was not built on top of the other one. It does not contain the other user's item. Keeping only the later write deletes the earlier user's item, and nothing in the system reports an error.

A vector clock replaces "which one is newer" with "which one knows about the other". That is the property you actually need.

What a vector clock is

A vector clock is a list of counters, one counter per node that can accept writes. If a cluster has three nodes named N1, N2, and N3, then every version of every record carries a vector of three numbers, written here as [N1, N2, N3].

Three rules govern it:

1. When a node accepts a write, it increments its own counter and leaves the others alone.
2. When a version is copied to another node, the vector travels with it unchanged.
3. When a node merges two versions, it takes the larger of the two values in every position, then increments its own counter.

That is the whole mechanism. The rest is reading the numbers.

The worked example

Three replicas hold a shopping cart: N1, N2, and N3. The vector is [N1, N2, N3].

Step 1. The first write.

A user adds milk to the cart. The request goes to N1. N1 increments its own slot.

Step 2. Replication.

N1 copies the version to N2 and N3. The vector does not change during replication, because no new write happened.

All three replicas agree. There is nothing to resolve.

Step 3. The network splits.

A network partition separates N2 from N3. Both are still serving traffic. Neither can see the other's writes.

Step 4. Two writes land on two sides.

The user's phone adds eggs, and that request reaches N2. N2 starts from [1, 0, 0] and increments its own slot, which is the second one.

The user's laptop adds bread at the same moment, and that request reaches N3. N3 also starts from [1, 0, 0] and increments its own slot, which is the third one.

Step 5. The partition heals.

N2 and N3 can talk again, and they exchange versions. Now the system has to decide what to do with [1, 1, 0] and [1, 0, 1].

How to compare two vector clocks

The rule is a position-by-position comparison.

Version B descends from version A (meaning A happened before B, and B already contains A's changes) when both of these are true:

• B's counter is greater than or equal to A's counter in every position.
• The two vectors are not identical.

If neither vector descends from the other, the two versions are concurrent. They were produced independently, and neither one contains the other's changes.

Applying that to the example:

• Does [1, 1, 0] descend from [1, 0, 1]? Check every position: 1 is greater than or equal to 1, and 1 is greater than or equal to 0, but 0 is not greater than or equal to 1. The third position fails. No.
• Does [1, 0, 1] descend from [1, 1, 0]? 1 is greater than or equal to 1, but 0 is not greater than or equal to 1. The second position fails. No.

Neither descends from the other, so the two versions are concurrent. This is a genuine conflict, and the system now knows it. That is the entire value of the mechanism. A wall clock timestamp would have reported a clean winner and quietly discarded a grocery item.

What the system does with a conflict

Once concurrency is detected, the database has three options.

Keep both versions as siblings. The next read returns both, and the application decides. Amazon's Dynamo paper describes exactly this for shopping carts, where the application merges by taking the union of the items. Riak calls these siblings and exposes them the same way.

Merge automatically using a data type that cannot conflict. If the value is a set, a counter, or another conflict-free replicated data type, the merge rule is built into the type and no application code is needed.

Apply a deterministic tiebreak. Pick the version with the higher node id, or the higher timestamp. This loses data, but it does so predictably, and for some values that is acceptable.

Step 6. The merge.

The application reads the cart, receives both siblings, and merges them into milk, eggs, bread. It writes the merged value back through N2, passing both original vectors as context.

N2 takes the position-by-position maximum of [1, 1, 0] and [1, 0, 1], which is [1, 1, 1], then increments its own slot.

Now check the new version against the two old ones. [2, 1, 1] is greater than or equal to [1, 1, 0] in every position, and greater than or equal to [1, 0, 1] in every position. It descends from both. Both siblings can be safely deleted, and nothing was lost.

Vector clocks, version vectors, and Lamport clocks

These three names get used interchangeably, and they are not the same thing.

What databases like Dynamo and Riak actually use is a version vector, one counter per replica. The industry calls them vector clocks anyway, and interviewers will use that word. Knowing the distinction is worth one sentence in an interview, and no more than one.

A Lamport clock is smaller and cheaper, but it gives you a single ordering with no way to tell a real ordering from an arbitrary one. If you only need a consistent tiebreak, that is fine. If you need to detect conflicts, it is not enough.

The cost

Vector clocks are not free, and interviewers like to probe this.

The vector grows with the number of writer nodes. A cluster with 200 nodes that all accept writes means a 200-entry vector attached to every version of every record. For small records, the metadata can be larger than the data.

Client-side vectors grow worse. If every client is a separate entry, the vector grows with your user base, which does not work.

The standard mitigations are:

• Only count nodes that coordinate writes, not every node and not clients. Dynamo increments the counter of the coordinating node, not the client.
• Truncate the vector. Dynamo stores a timestamp with each entry and drops the oldest entries beyond a size limit, which introduces a small chance of a false conflict but bounds the size.
• Use dotted version vectors, which Riak adopted to keep the vector proportional to the number of replicas rather than the number of clients, and to avoid a sibling explosion under concurrent writes.

What to say in a system design interview

If you are asked how a system handles concurrent writes to the same key across replicas, a complete answer covers four points:

1. Name the failure. Last write wins silently loses data when two writes are concurrent, because a later timestamp does not mean the write saw the earlier one.
2. Name the mechanism. A vector clock, one counter per writer node, incremented on write and merged by taking the maximum in each position.
3. Show the comparison. One version descends from another if it is greater than or equal in every position. If neither descends, they are concurrent, and that is a conflict the system can now see.
4. Name the cost and the mitigation. The vector grows with the number of writer nodes, and real systems truncate it or use dotted version vectors.

That is the shape of a strong answer: the failure, the mechanism, the comparison rule, and the tradeoff. Reciting a definition without the failure it prevents reads as memorization.

Conflict detection is one of several replication topics that come up together. Quorums, read repair, and anti-entropy all sit next to it, and they are covered in Grokking System Design Fundamentals. For how these choices play out inside a full design conversation, Grokking the System Design Interview works through them in the context of complete systems.

Frequently asked questions

Do vector clocks order all events?

No. They produce a partial order. Some pairs of events are ordered, and some are concurrent with no ordering between them. That is intentional. The concurrent pairs are exactly the conflicts you need to know about.

Do vector clocks resolve conflicts?

No. They detect conflicts. Resolution is a separate decision made by the application, by a conflict-free data type, or by a tiebreak rule. Confusing detection with resolution is the most common mistake on this topic.

Which databases use them?

Amazon Dynamo introduced the approach for shopping carts. Riak and Voldemort adopted it. Cassandra chose last write wins with timestamps instead, which is simpler and faster but does lose concurrent writes.

Are vector clocks needed if I use a single leader?

No. With a single leader, every write to a key goes through one node, so writes to that key are already ordered and cannot be concurrent. Vector clocks matter for leaderless or multi-leader replication, where more than one node accepts writes for the same key.

What happens if a node is removed from the cluster?

Its entry stays in existing vectors and stops incrementing. Old entries can be pruned once every live replica has a version that descends past them, which is what truncation schemes do.

Related reading

• 10 Must-Know System Design Failure Modes
• System Design Research Papers Every Engineer Should Read
• System Design Interview Questions and Case Studies