Distributed caches and hot keys

When one cache node is not enough, how keys are spread, and what to do when one key is too popular.

A single cache server is limited in memory and in requests per second. When your working set no longer fits, or traffic outgrows one machine, you spread keys across several cache nodes. The client (or a proxy) must decide which node owns a key, and everyone must agree, otherwise a key is stored on one node and looked for on another.

The naive rule is node = hash(key) mod N. It works until N changes. Going from 4 nodes to 5 keeps a key in place only when hash mod 4 equals hash mod 5, which is true for 1 in 5 keys. So adding one node moves about 80 percent of all keys, and 80 percent of requests suddenly miss. Consistent hashing fixes this: keys and nodes are placed on a ring, each key belongs to the next node clockwise, and adding or removing a node only moves the keys next to it, roughly 1/N of them.

That is the hot key problem. Suppose a celebrity restaurant's page key receives 150,000 reads per second, and one cache node can serve about 100,000. Adding nodes does nothing, because the hash always sends that key to the same node. The solutions copy the hot key: keep a tiny in-process local cache (even 1 second long) in each app server so most reads never leave the machine, or store the key under several names such as rest:7#1, rest:7#2, rest:7#3 and have each request pick one at random. Three copies turn 150,000 reads per second into 50,000 per node.