Distributed Key-Value Store

250 nodes. If one machine fails twice a year, 250 of them fail more than once a day. Node failure is not an incident here — it is the normal state. A design that needs every replica present would never be up.

1 trillion keys. No table can map key → node at that size; the lookup table would itself need sharding. Placement must be computed from the key, by every node, with no shared state.

Those two facts force everything that follows: placement must be computed (section 4), and operations must complete while machines are missing (section 5).

No scan. No join. No begin_transaction. No secondary index.

That is not an oversight — every one of them would require coordination between nodes, and coordination is what this design gave up in order to stay writable during a partition. The interface is the promise; sections 4 to 8 are how it is kept.

A small interface is what buys the scale. When someone asks for range queries later, the honest answer is "that is a different system", and this step is why you can say so.

Most stores fix consistency once, for everything they hold. Here the caller chooses per call.

A session token can be read with R=1 — fast, occasionally stale, and nobody is harmed. An account balance in the same cluster can be read with R=2 — slower, but it cannot miss a completed write.

Forcing one setting on all data means picking the strictest need and making everything else pay for it.

The store hands a version out on get and expects it back on put.

Without it, an arriving write is just bytes — the store cannot tell "an update to what I gave you" from "an update to something older that took a slow path". It would have to guess, and guessing loses data silently.

Carrying the version is what makes disagreement detectable, which is the entire subject of section 6.

Once a key's position is known, its replicas are the next few distinct physical nodes clockwise. No separate placement table is needed, and every node can compute the location of any key independently.

That is what removes the need for a central coordinator on the data path — any node can receive any request and route it correctly.

W + R > N   →   reads and writes overlap on at least one node
                → a read always sees the latest write

With N=3, W=2, R=2: any two writers and any two readers must share at least one node, so a read cannot miss a completed write.

Set W + R ≤ N and reads may return stale data — sometimes a deliberate choice for speed.

Requiring every replica to confirm sounds safest. It means a single slow or dead replica blocks all writes.

With three replicas and 99.9% availability each, W=3 gives you 99.7% — worse than any individual node. Quorums exist precisely so that a minority can fail without stopping the system.

It relies on wall-clock timestamps across machines, which drift. Two concurrent writes mean one is discarded with no record and no error.

For a cache that is fine. For a shopping basket it means items vanish, and nobody can explain why.

Vector clocks instead record which node saw which version, so the system can tell "B came after A" from "A and B happened concurrently". Genuine conflicts are handed to the client, which knows the semantics — a basket, for example, can merge by taking the union of items.

Comparing two replicas holding a billion keys sounds impossible. A Merkle tree hashes the data in a tree, so comparing roots is one comparison.

If the roots match, the replicas are identical — done. If not, descend only into the branches that differ. Finding a handful of differing keys among a billion costs a few dozen comparisons instead of a billion.

This is why anti-entropy repair is affordable enough to run continuously.