Replicas copy all the data to every machine, so every machine still takes every write. To grow writes, the data itself has to be split across machines. Key-value stores are built around that split, and it spreads the load beautifully, as long as the load is spread across many keys.
Key-value stores
A key-value store (KV store) keeps each value under a single key and answers two questions: get the value for this key, and put a value under this key. A post's id is a key; the post is its value.
| Relational database | Key-value store | |
|---|---|---|
| Asks | any query: filters, joins, sorting | get or put one key |
| Changes several rows at once | yes, in a transaction | usually not |
| Writes to one row or key | one at a time, a few hundred a second | one at a time, up to about 1 000 a second |
| Grows by | a bigger machine, read replicas, then sharding by key | more partitions |
Giving up queries across many rows is what lets a KV store split its keys across machines without any machine needing to see the others. That suits data you always look up by one id: feeds, sessions, carts, counters. It's a poor fit for data you need to search, join or change together. Relational databases can be split by key too (Vitess for MySQL, Citus for PostgreSQL), but then queries and transactions that cross shards get slow and hard.
One partition has a limit
A key-value store keeps its data in partitions. Each partition is a slice of the keys with its own machine behind it, and each has a fixed budget per second:
| Partition size | Reads per second | Writes per second |
|---|---|---|
| Small | 5 000 | 1 000 |
| Medium | 25 000 | 5 000 |
| Large | 75 000 | 15 000 |
Past that budget, the partition throttles: it turns requests away rather than slowing everyone down. A store with one small partition can never take more than 1 000 writes a second, however fast each write is.
Partitioning by key
Add partitions and the store hashes each key to pick its partition. Different keys land on different partitions, so each one takes a share of the traffic, and the store's total budget is the per-partition budget times the number of partitions.
A hash of the key picks the partition. Each key always lands on the same one.
Adding partitions
The simplest way to pick a partition is the hash of the key modulo the number of partitions. That works until the count changes: go from 4 partitions to 5 and almost every key's partition changes, so almost all the data has to move at once.
Consistent hashing avoids that. Picture the hash values on a ring. Each partition owns a stretch of the ring, and a key belongs to the next partition clockwise from its hash. A new partition takes over part of one stretch, so only the keys in that part move.
A ring has a catch: with one point per node, the stretches are very uneven. Each partition usually owns many small stretches, called virtual nodes, which averages the unevenness out.
Virtual nodes also decide what happens when a node fails.
Hashing scatters neighbouring keys. Range partitioning instead gives each partition a range of keys (A to F, G to M...), which keeps a range scan on one machine, at the cost of hot ranges: if new keys are time-based, every new write lands on the last partition.
Hot partitions
Hashing spreads keys, not requests. Every request for one key goes to the one partition that owns it. When a single post goes viral and draws a fifth of all reads, its partition gets a fifth of all reads, whether the store has 4 partitions or 400. The others sit half idle while that one throttles.
Fixing a hot key
A hot key needs a fix that doesn't depend on which partition owns it:
| Hot key is | Fix |
|---|---|
| Read a lot | Cache it in front of the store, so most reads never reach the partition |
| Written a lot | Split it into several keys (a counter in 10 pieces, summed on read), or add up increments in the app and write the sum once a second |
| Both | Both, plus the edge if reads come from everywhere |
Some stores can also split a busy partition in two, but they can't split a single key. One key's traffic always ends up on one machine. Hot Keys, a few chapters on, works the written case through on one viral counter.
No placement scheme moves a hot key's traffic: put one key that takes a fifth of all requests on a ring, a modulo or a rendezvous scheme, and whichever node holds it carries about 1.5 to 2 times the average. Splitting the key into pieces that hash separately is what spreads it.
How many partitions
Start from the busiest second you expect, divide by what one partition can take, and leave headroom: traffic is never perfectly even, and growth is easier than a rushed split. Then check the keys: if one of them alone needs more than a partition, no partition count is enough, and that key needs a cache or a split of its own.
In the wild
The ideas in this chapter, and where you'll meet them in real systems and interviews:
| Idea | Where you'll meet it |
|---|---|
| Key-value stores | Amazon DynamoDB, Apache Cassandra, Redis |
| Consistent hashing | Cassandra's token ring with virtual nodes, Riak, and the Dynamo paper |
| Hash and range partitioning | MongoDB sharding (hashed or ranged), Redis Cluster's 16 384 hash slots |
Your practice
Inkwell stores every post in a key-value store with small partitions. Writers publish thousands of posts a second, and one post has gone viral. The store keeps throttling. Spread the writes and protect the viral post's partition.