Key-value stores
The simplest database: a hash map spread over machines.
01The intuition
The problem it solves
A cloakroom at a concert takes your coat and gives you a numbered token. To get the coat back you show the token; nobody searches by colour or by owner's name. The whole system is "put this under that number, give me what is under that number", and it serves thousands of people a night because it never has to think.
A huge share of what a service needs to store is exactly this shape: a session id to the logged-in user, a user id to their settings, a short code to its long URL, a video id to its view count. A key-value store is a database stripped down to that one pair of operations, which is why it can be made faster and larger than a general database, and why it is the first thing to reach for when the question is "look this up, by this key, very fast".
Build it one piece at a time
Step 1: a hash map on one machine. put(key, value) and get(key) over an in-memory map. Reads and writes take microseconds. The limits are obvious: memory is finite, and a restart loses everything.
Step 2: make it durable. Append every write to a log file before acknowledging it. On restart, replay the log. Now the map survives a crash. Writes are still fast because appending to a file is sequential. (For data bigger than memory, the on-disk structure matters; that is the LSM versus B-tree article.)
Step 3: spread keys over machines. Use consistent hashing to assign each key to a node. The client (or a thin router) hashes the key and talks to that node directly, so there is no central coordinator on the read path.
| After step | Where key "user:42" lives | A read costs | Survives |
|---|---|---|---|
| 1 | memory of the one node | microseconds | nothing |
| 2 | memory + append log | microseconds | a crash |
| 3 | node 7 of 50, by hash | one network hop, under 1 ms | a crash of one node's data, but that node's keys are unavailable |
| 4 | nodes 7, 8, 9 (3 copies) | one hop to any of them | losing two of the three |
Step 4: copy each key to the next nodes. Each key is written to N = 3 consecutive nodes on the hash ring. A write waits for W of them, a read asks R of them and takes the newest answer. With W + R > N, every read overlaps the last write (quorums).
Step 5: handle the awkward cases. A node that was down comes back with stale data: a background anti-entropy process compares hashes of key ranges between replicas and repairs differences. Two writes to the same key reach different replicas during a partition: keep both with vector clocks and let the application resolve, or let the last timestamp win and accept rare lost updates. A node joins: it takes over a slice of the ring and streams those keys from its neighbours.
Why it works, with the numbers
Speed comes from doing one thing. A read is hash, hop, memory lookup:
read latency ≈ 0.5 ms network + 0.01 ms lookup, versus 5 to 50 ms for a relational query with joins and a planner
Capacity adds with nodes. If a node holds 100 GB in memory and serves 200,000 operations a second, 50 nodes with 3 copies hold 1.6 TB of distinct data and serve about 10 million operations a second. The guarantee depends on the quorum setting: with N = 3, W = 2, R = 2 a read sees the latest acknowledged write; with W = 1, R = 1 it is fast and may be stale. The failure modes are a hot key that overloads its three nodes (fix with client caching or key splitting), a value that grows huge (a list of a million followers under one key), and treating the store as if it supported range queries or transactions it does not.
The trade-off you must say out loud
You give up queries. No "all users in Hyderabad", no joins, no multi-key transactions. If the access pattern is anything other than "by this key", a key-value store is the wrong tool or needs a second index beside it. Say what the key is, what the value is and how big it can get, and which quorum setting you chose. The next question is "what happens to a key when its node dies?", and the answer is the replicas plus a hinted handoff or repair.
Where it shows up in the 100 Google problems
- Design a distributed key-value store: the question is this article; the deep dives are the ring, the quorums and repair.
- Design a distributed rate limiter: counters per client key in a fast store with a short TTL.
- Design a Drive-style usage quota limiter: per-user usage as a key-value counter with a strongly consistent write path.
- Manage user preferences across many Google products: one key per user, read by every product in a millisecond.
- Design a distributed cache: a key-value store that is allowed to forget.