Lesson 3.6 · 25 min
Key-value store
Tune R and W while nodes fail and watch stale reads appear even with R + W > N, merge a cart with vector clocks, gossip a death across 256 nodes, and find 3 bad keys among 1,024 with a Merkle tree.
The idea in plain words
A key-value store is a giant dictionary: give it a key, it gives you back the value. Building one that spreads over hundreds of machines and keeps working when some fail brings together most ideas in this chapter.
The problem it solves
Many systems just need “store this value under this key, give it back later”, but at a size and rate one machine can’t handle, while machines keep failing.
How it works
- Split the keys across many nodes with consistent hashing.
- Store each key on N nodes (say 3) so a failure loses nothing.
- A write succeeds when W of them confirm, a read asks R of them; with R + W > N every read reaches a copy that saw the latest write.
- If two clients write at once, keep both versions and let the reader or a rule resolve them.
- Nodes track who is alive by gossiping, and repair missed writes in the background.
Example
N = 3, W = 2, R = 2. A write reaches nodes A and B but not C (C was down). A later read asks B and C: B has the new value, so the read returns it and quietly updates C.
Key terms
- put / get
- The two basic operations: store a value under a key, and read it back.
- Quorum
- Needing answers from enough replicas (for example 2 of 3) for a read or write to count.
- Vector clock
- A small counter per node attached to a value, used to tell which writes happened concurrently.
- Gossip
- Nodes chatting with random peers to spread who is alive, without a central list.
- Hinted handoff
- Another node temporarily holds writes for a node that is down and hands them over later.
In this lesson you'll learn
- How a Dynamo-style store combines partitioning, replication and quorums, and when R + W > N stops protecting you.
- How vector clocks, gossip, hinted handoff and Merkle trees handle conflicts and failures.
- How an LSM storage engine with Bloom filters makes writes cheap and reads bounded.
Sections
- Theory: the pieces
- Theory: quorums
- Theory: conflicts
- Theory: failure detection
- Theory: repair
- Theory: storage engine
- Design: pick R and W
- Check yourself
Cheat sheet
| Overlap | R + W > N (same N nodes) |
|---|---|
| Conflicts | vector clocks → siblings |
| Failures | gossip + timeout |
| Short outage | sloppy quorum + hinted handoff |
| Long outage | Merkle-tree anti-entropy |
The interactive simulations and the quiz load with JavaScript.