KV: everything

Two copies that cannot reach each other, and the choice between answering and refusing. The last three builds chose to answer. This one pays the bill that choice runs up, then kills two machines and measures the whole store.

Before you start. KV: hinted handoff kept the store taking writes while machines were down: a healthy machine stood in for a dead one and kept the value as a hint, a note saying who it really belongs to, and handed it over when the owner came back; and a read that noticed a copy behind fixed it on the spot. Amazon - the case study tells how Amazon put these same pieces under its shopping cart. Two holes were left open: hints are only kept for a while, and a read only fixes keys somebody reads. This lesson closes both.

The idea in 30 seconds

Anti-entropy is a background sweep where two replicas compare and repair, and it is the backstop for every write that quicker delivery missed.
Hints last only as long as the hint window; a machine away longer returns with writes nobody is holding for it, and here that left 3,006 stale copies.
A single checksum tells you whether two copies differ, not where, so on its own it saves nothing once they differ.
A Merkle tree fingerprints slices of the keys and then fingerprints the fingerprints, so two replicas can walk down only the branches that differ: 43 comparisons found 3 lost keys among 3,464.
Killing two of five machines cost this store no accepted writes and no stale quorum reads, and one anti-entropy round brought every copy back.

Read the story · Skip to the numbers