Vector Clocks and Versioning

Define the problem

A store keeps several replicas of each value so it stays up when one machine fails. A network partition can cut the replicas into groups that cannot talk.

During the partition, both groups keep accepting writes. The same value now has two different versions, and neither group knows about the other.

Wall clocks cannot settle which version is newer. Machine clocks drift apart, and two writes can carry the same timestamp.

Last-write-wins settles it by timestamp alone. It silently throws one write away, even when that write was never seen by the winner.

How a vector clock works

A version is one stored state of a value, produced by one write. The vector clock is the version's memory of where it came from.

Every replica owns one counter in the clock. When a replica writes a value, it raises its own counter by one and stamps the new version with the full clock.

Replica A writes a value for the first time. A's counter becomes 1, and the version carries a clock showing A at 1 and every other replica at 0.

When a replica receives a version from elsewhere, it merges the clocks. For each counter, it keeps the higher number, because the higher number has seen more writes.

The clock travels with the value on every read and write. No central machine assigns it, so partitioned groups can keep stamping versions on their own.

Comparing two clocks

One clock is older than another when every counter is equal or lower, and at least one counter is lower. The newer version has seen everything the older one saw, and more.

Two clocks are concurrent when each is higher in at least one counter. Each version saw a write the other never saw.

Concurrent versions are called siblings. The store keeps both, because picking one would delete a write nobody has seen.

A later read returns the siblings together. The application merges them, or a person chooses, and the merged result is written back with a clock that covers both.

That is the heart of the idea. A vector clock does not order every write. It proves when one write came after another, and it admits honestly when it cannot prove that.

Causal consistency

Causal consistency is a consistency promise built on this idea of one write depending on another. If a write depends on an earlier write, every replica shows them in that order.

A reply depends on the message it answers. Causal consistency guarantees no replica shows the reply before the message.

Writes that do not depend on each other may appear in different orders on different replicas. The promise only covers cause and effect.

Vector clocks are the machinery that makes the promise checkable. A replica can compare clocks and know whether a version it is about to show is missing a cause.

The cost of the clock

The clock grows with the number of replicas, not with the size of the value. A value stored on many replicas carries a long clock on every version.

Take a store with 100 replicas and 8 bytes per counter, as a stated demo choice.

100 replicas × 8 bytes = 800 bytes of clock on every version.

At 1,000,000 writes a day, that is 1,000,000 × 800 bytes = 800,000,000 bytes of clock data a day, about 800 MB.

Old counters can be pruned when a replica leaves for good. Pruning is risky, because a pruned replica that returns can produce versions the others can no longer compare.

Trade-offs and wrap-up

Against last-write-wins, the trade is clear. Last-write-wins is tiny and fast, and it loses concurrent writes without a sound.

Against a single leader, the trade is availability. A leader gives every write one order, but a partition can leave a group with no leader to write to.

Vector clocks fit stores that must accept writes in several places at once. Shopping carts and sync tools are the classic shape, because merging siblings there is natural.

The price is real. Versions multiply, applications must merge siblings, and every version carries the clock as overhead.

Comparing two vector clocks