Ismail Enegadi

Version Vectors, Siblings, and Tombstones

7 min readSystems
On this page6

The previous post reduced conflict handling to one mechanical question: for any two writes to the same key, did either know about the other? Answer it, and overwrites resolve themselves while genuine conflicts get surfaced instead of silently dropped.

This post is the answer. It is less clever than it sounds — the whole mechanism is a counter and a rule about which values to throw away.

Tracking Causality With a Counter

Start with the easy case: a single replica, no leaderlessness yet. Get this right and the multi-replica version is a generalisation rather than a new idea.

The server keeps a version number for every key, and increments it on every write. Around that, four rules:

  1. Every write is stamped with the new version number, and the server stores the value alongside it.
  2. A client must read before it writes. The read returns every value not yet overwritten, plus the current version number.
  3. When a client writes, it sends back the version number from that prior read, and merges together whatever values that read returned.
  4. On receiving a write based on version v, the server overwrites every value at or below v — those are the ones the client demonstrably saw — and keeps every value above v, because the client could not have known about them.

Rule 4 is the entire trick. The version number a client sends is a claim about what it had seen. Anything at or below it has been accounted for and can be safely discarded. Anything above it arrived after the client’s read, so it is concurrent, and throwing it away would lose a write that was acknowledged as successful.

Siblings: how concurrent writes branch and merge

Each write carries the version it was based on. The server overwrites anything at or below that version and keeps everything above it as a sibling, so no concurrent write is dropped before a client can merge it.

Follow the branch in the middle. v3 was written by a client that had read v1, so it supersedes v1 and that value disappears. But v2 landed after that client’s read, so v3 says nothing about it. The server holds both, and the two values sit side by side until someone reconciles them.

Riak calls those coexisting values siblings. They are not corruption or an error state — they are the database declining to guess.

A write sent with no version number at all is, by rule 4, concurrent with everything. It overwrites nothing and simply joins the pile.

Merging Siblings, and the Item That Won’t Die

Siblings buy safety at the cost of work: something has to merge them, and that something is usually application code.

For a set that only ever grows, the merge is a union, and it is genuinely trivial. Our playlist merges to {Bowie, Nina, Prince} and no one has to think about it.

Removal is where it falls apart.

Suppose one client removes Prince while another concurrently adds Nina. Now there are two siblings: one containing {Bowie, Nina}, another containing {Bowie, Prince}. Union them and Prince is back. The removal was a real, acknowledged write, and the merge quietly undid it.

This is the bug behind the shopping cart story from the write conflicts post — items reappearing after customers deleted them. The conflict handler was doing exactly what it was told. Union preserves everything, and “everything” includes the item whose entire point was to be gone.

The fix is to stop treating removal as absence. A deletion has to leave something behind:

sibling 1   { Bowie, Nina }
sibling 2   { Bowie, Prince }

union       -> { Bowie, Nina, Prince }     Prince is back

sibling 1   { Bowie, Nina, Prince:deleted@v3 }
sibling 2   { Bowie, Prince }

merge       -> { Bowie, Nina }             the marker wins

That marker is a tombstone: a record that says “this was removed, at this version”, carried through merges like any other value. Now the merge has enough information to distinguish “never seen” from “seen and deleted”, which union alone cannot express.

Tombstones are not free — they accumulate, and something has to reclaim them later, which is its own well-known problem in Dynamo-style stores. But an absent value simply cannot record intent, and intent is exactly what the merge needs.

Version Vectors

Everything so far assumed one replica handing out version numbers. Leaderless replication has no such thing.

With several replicas accepting writes independently, a single counter stops working: two replicas will happily issue the same version number for unrelated writes, and comparing those numbers tells you nothing about causality.

The fix is to stop keeping one number and start keeping one per replica. Each replica tracks its own counter for a key, and also what it has seen of every other replica’s counter. That collection of counters is a version vector.

It supports the comparison we actually need. Given two version vectors, one dominates another if every one of its counters is greater than or equal — meaning that write saw everything the other did, and supersedes it. If neither dominates, each replica saw something the other missed, and the writes are concurrent. That is the happens-before test from the previous post, made mechanical.

In practice the vector travels with the data: replicas hand it to clients on read, and clients hand it back on write. Riak exposes it as an opaque blob it calls the causal context — the client is not meant to interpret it, only to return it. Riak 2.0 uses a refinement called a dotted version vector, which handles some sibling-explosion cases the plain form does not.

Nothing else changes. Siblings still appear, merges are still the application’s job, tombstones are still how deletions survive. The vector only replaces the counter that decides which values to keep.

Version vectors and vector clocks are not the same thing. They are closely related and the terms get used interchangeably, which is a good way to end up confused reading the literature. Vector clocks order events in a general distributed system; version vectors compare the state of replicas. When the question is which replica’s data is newer, version vectors are the right tool — see the references if you want the distinction properly.

When You Don’t Want to Write the Merge

All of this hands the application a job it may not want. Writing correct merge logic per data type, remembering tombstones, reasoning about what “concurrent” means for your domain — it is real work, and it is easy to get subtly wrong in ways that only show up under partition.

Which is why the data structures from the write conflicts post matter here too. CRDTs are, in a sense, siblings and merging packaged up so the application does not have to think about them: types that merge correctly by construction, including handling deletions properly rather than resurrecting them. Riak ships them as first-class datatypes for exactly this reason.

The trade-off has not vanished — it has moved. You give up arbitrary data shapes and get correct automatic merging in exchange.

Key Takeaways

  • A server tracks causality with a version number per key: clients read before writing, send back the version they saw, and the server overwrites values at or below it while keeping everything above as concurrent.
  • Values kept side by side are siblings. They are the database refusing to guess, not an error.
  • A write carrying no version number is concurrent with everything and overwrites nothing.
  • Merging siblings by union works for grow-only sets and breaks on removal — a deleted item reappears, which is exactly the shopping-cart bug from part 8.
  • A tombstone records the deletion with a version so merges can tell “never seen” from “seen and deleted”. Absence cannot express intent.
  • With multiple replicas a single counter is meaningless, so each key carries one counter per replica — a version vector. One vector dominating another means supersession; neither dominating means concurrency.
  • Riak exposes the vector as an opaque causal context; clients return it rather than interpret it.
  • Version vectors are not vector clocks, despite the terms being used loosely.
  • CRDTs move the merge from application code into the data type, trading arbitrary data shapes for correctness by construction.

References

Subscribe via RSS