Design a distributed cache with hot keys
A million gets a second across ten nodes, and one key that wants a fifth of them. The round turns on two sentences: the client hashes each key to a node on a ring, and the few hot keys never leave the app.
The round this design follows
How many cache nodes does a million gets a second need?
Compute memory and load separately and take the larger. The hot set is 100 GB, 150 GB with the overhead of keys and pointers, which fits on three 64 GB boxes. At 200 thousand gets a second a node, load needs five. The prompt gives ten, which runs each node at under half its capacity, and that spare half is what absorbs a burst or a dead neighbour.
Why consistent hashing and not key hash modulo the node count?
Because the node count changes. With modulo, going from ten nodes to eleven moves 90.9 percent of the keys, and every moved key is a miss that lands on the database at once. On a ring, the new node takes only the arcs just before its positions, 9.09 percent of the keys. Virtual nodes, a hundred positions per node, keep the arcs even, so no node owns far more than its tenth.
What do you do about one key that takes a fifth of all reads?
Hashing cannot spread one key, so its node takes 275 thousand gets a second against a capacity of 200 thousand. The first fix is a near cache: each app server keeps the hot key in its own memory for a second, so those reads never cross the network, and the node sees one refresh a second per app server. If that is not enough, copy the key to several nodes and read from any of them. Detect hot keys with a per-key counter in the client library.
What is a cache stampede and how do you stop it?
When a hot key expires, every request that arrives before the first refill finishes misses and goes to the database. At 200 thousand gets a second and a 4 ms database read, that is 800 reads for one key. A lease fixes it: the first caller to miss gets the right to fill, and the rest wait a moment and retry the cache, so the database sees one read. The near cache also shrinks the herd, because only the app servers refreshing their copy reach the ring at all.
What happens when a cache node dies?
The ring itself barely notices: nine nodes have room for the tenth one's gets. The database notices, because every key that node held is now cold, and each first get for it is a miss. Here that raises the database from 50 thousand reads a second to 125 thousand, against the 100 thousand assumed it can serve. The answers are leases so each cold key costs one read, a database sized for one node down, or a replica per cache node.