CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 5 of 7 · 2 min read

Spreading keys over many cache nodes

Hashing, and why a plain modulus moves too many keys when a node is added.

Think of a post office with several counters. A rule such as "surnames A to F at counter 1" decides where each customer goes. If a new counter opens and the rule is re-drawn for everyone, nearly every customer moves. A rule that moves only a few customers is better.

When one cache node is too small, the keys are spread over many nodes. A client needs a rule to find the node for a key. The simple rule is: node = hash(key) mod N, where N is the number of nodes.

A worked example of the problem. There are 4 nodes and 1,000,000 keys. Adding a fifth node changes N from 4 to 5. A key stays on its node only if its hash gives the same remainder for 4 and for 5. Looking at hash values 0 to 19, that holds only for 0, 1, 2 and 3, which is 4 of 20, or one fifth. So about 80 percent of the keys, around 800,000, now map to a different node and miss. The database sees a storm of misses just when the cache is being enlarged.

Consistent hashing

Consistent hashing maps both keys and nodes onto a ring of hash values. A key belongs to the first node found going clockwise from the key's position. When a node is added or removed, only the keys between it and its neighbour move.

Example: with 4 nodes, adding a fifth moves about one fifth of the keys (about 200,000 of 1,000,000), not 800,000.

The book "Understanding Distributed Systems" recommends it: when the external cache needs to scale out, as little data as possible should move, so that availability does not drop and misses do not rise sharply. It names consistent hashing, or a similar partitioning technique. The book "Designing Data-Intensive Applications" lists a consistent hashing library for Memcached clients in its references, which shows the use.

A ring gets uneven if each node has one position. A node may hold a large arc by chance. The usual fix is to give each node many positions on the ring (called virtual nodes), so the load evens out. This detail comes from standard practice and is covered in Level 4.

Effect on a node failure. With 10 nodes and consistent hashing, if one node fails, about 10 percent of the keys lose their home and miss. Those keys are loaded from the database to the neighbouring nodes. The other 90 percent are untouched. With mod N, changing N from 10 to 9 would reshuffle about 90 percent of the keys.

Rule Keys moved when a node is added to 10 Keys moved when one of 10 fails
hash mod N about 91 percent about 90 percent
Consistent hashing about 9 percent about 10 percent

Check yourself:

  • With mod N, about what share of keys move when N goes from 9 to 10?
  • Why do cache clusters prefer consistent hashing?