Design a key-value store
Two billion keys on a ring of six nodes, three copies of each, and reads and writes that each wait for two copies, so a read always meets the last acknowledged write.
Why is W + R > N the rule for reading your own writes?
A write waits for W replicas and a read asks R of them. When W + R is more than N, the two sets must share at least one replica, and that replica holds the newest version, so the read sees it. With N = 3, W = 2 and R = 2 give 4, which is more than 3. With R = 1 the sum is 3, and a read can land on the one replica that missed the write.
Why use consistent hashing instead of hash(key) mod N?
With mod N, the node for almost every key changes when N changes. On this page, going from six nodes to seven moves 847 of 1,000 keys. On a ring a new node only takes the keys between its point and the point before it, so the same change moves 180 keys with one point per node and 111 with 64 points per node. Moving fewer keys means less copying while the cluster grows.
What is hinted handoff?
When one of a key’s replicas is down, the coordinator still accepts the write if W replicas took it, and it keeps a note, called a hint, saying which node missed which write. When that node comes back, the hint is replayed to it, so the third copy is restored without waiting for a background repair. It restores copies. It does not make a write succeed when fewer than W replicas are up.
Why do key-value stores use an LSM tree for storage?
An LSM tree turns every write into an append to a log and an update in memory, and it writes sorted files to disk in large sequential pieces. That keeps writes cheap on any disk. The price is on reads: a key that is not in memory may have to be looked for in several files, which is why the engine merges files in the background (compaction) and keeps a small filter per file to skip the ones that cannot hold the key.
What happens to a hot key in a partitioned store?
Every request for one key goes to the same replicas, so adding nodes does nothing for it. On this page one key’s reads are capped at one node’s worth of operations, 3,000 a second, whatever the size of the cluster. The usual fixes are a short-lived cache in front of the hot key, or splitting the key into several keys that land on different nodes.