Design a key-value store
How do you build a store that never says no to a write, even when machines die?
Why did a cart lose three boxes?
The delivery service now cooks for Pune, Mumbai and Nashik. Since lesson 1.1, every cart and every login session lives in one shared database server, so any app server can serve any customer.
One Friday at 12:10 that server’s disk failed. The standby took over in about fifty seconds. For those fifty seconds every “Add to cart” returned an error.
A hostel student was building his floor’s Friday order: twelve boxes, one for each friend. He tapped “Add” twelve times and saw “Added” twelve times. When the app came back, his cart held nine. Three adds had been acknowledged by the old server and had not yet reached the standby. Forty-one carts were abandoned or checked out short that lunch. Each of those carts was a sale the kitchen lost, in part or in full.
The fixes that come to mind first are a bigger server, synchronous replication to the standby, and a faster failover. Each still lets only one machine accept a cart’s writes, and while that job moves to another machine, nobody may write. The pause shrinks to a few seconds, at best.
A sorting station at a railway yard works differently. When one sorter is ill, the station keeps taking boxes: another sorter takes his crate, with a slip saying whose it was, and hands it back when he returns.
Amazon’s 2007 Dynamo paper describes an “always writeable” store built for shopping carts, where writes are never rejected. To accept every write, it has to give something up, and this design has to make the same choice. Before reading on, say what a store must give up if two machines can each accept a write for the same cart.
Pause and predict Fifty seconds of errors and three acknowledged adds lost, because one server held every cart. What design never refuses an add when one machine dies?
What must never go wrong?
There are two rules. An acknowledged add must never disappear. And the store must not refuse an add because one machine is down.
Core entities, in two minutes
A Key with its Versions (a value and a vector clock each), a Node that stores key ranges, and a Hint: a copy held for a node that was down. Carts and sessions are values; the store does not look inside them.
The estimate that changes the design
At the 12:00 peak, 40,000 shoppers each write their cart or session about every 10 seconds and read it about every 4 seconds: 4,000 writes and 10,000 reads a second. About a million keys (a cart and a session for each of 500,000 recent customers) at about 2 KB each is 2 GB, 6 GB with three copies.
Pause and predict Two gigabytes fits in the memory of one ordinary server. So why spread this store over several machines at all?
The obvious version, and how it breaks
The first idea reuses what already runs. Split carts across three PostgreSQL boxes by customer_id mod 3. Each box carries a third of the load, and if one fails, only a third of customers suffer.
It works for a month. Then box 2 is restarted for a kernel patch, and for four minutes a third of all customers cannot add anything. The design has three single points of failure instead of one. Adding a standby per box brings back the fifty-second failover and the adds lost with it.
Growing hurts too. Adding a fourth box changes mod 3 to mod 4, which moves about three quarters of all carts (lesson 1.2, lesson 3.2). The flaw, whatever the database, is that each key has exactly one home that may accept its writes.
A mental model
- Quorum (N, R, W)
- Each key is stored on N nodes. A write counts as done when W of them confirm it; a read returns once R of them answer. If R + W is greater than N, every read hears from at least one node that has the latest acknowledged write.
- For example: N = 3, W = 2, R = 2: any two of three overlap with any other two of three. One node can be down and both reads and writes still succeed.
Try it before reading on. Make a stale read happen, then make the store refuse a write.
When two versions of a cart disagree
One goal is a rule the store applies on its own, with no merge code. The other is that no add is ever lost.
Last write wins is right for sessions: the newest login is the session, and a lost “last seen” update hurts nobody. For carts, a silently lost add is exactly what went wrong that Friday lunch. A dish that reappears is visible, and the customer can remove it before paying. What settles it is which mistake the customer can see and fix.
What to remember
- Each key lives on N nodes from its preference list. Writes wait for W, reads for R; with R + W > N every read meets the latest acknowledged write.
- Lower R or W for speed and availability, raise them for freshness and durability. Latency is set by the slowest of the R or W you wait for.
- A sloppy quorum with hinted handoff keeps accepting writes when replicas die, and gives up the overlap guarantee until the hints are delivered.
- Vector clocks tell a newer version from a concurrent one; concurrent versions are kept and merged by the application. Read repair and Merkle-tree anti-entropy bring replicas back together.
- Leaderless quorums suit data that must always accept writes and can be merged. Scarce counts need one leader and conditional writes.
A store that never refuses a write will sometimes hold two versions of the same key, so decide in advance how to merge them.
In the real world
Real stores add what the simulator leaves out. Cassandra lets each request choose its consistency level (ONE, QUORUM, LOCAL_QUORUM, ALL and others); its hints do not count towards a quorum except at level ANY, so its quorums are strict where Dynamo’s were sloppy. Riak kept Dynamo-style vector clocks and, from version 2.0, offered dotted version vectors, which produce far fewer false siblings. Dynamo truncated a clock once it reached a threshold number of entries (the paper says “say 10”), accepting rare false conflicts.
Quorums are not linearizability either: with R + W > N, a read that overlaps a write still in flight can return the new value while a later read returns the old one. Lesson 3.3 showed why that matters and where it does not.
The hostel’s Friday order now survives a dead disk. Next, in lesson 3.6, the cache in front of the menu starts evicting the wrong things.