Consistent Hashing

Foundations

Partitioning spreads keys across several nodes, so each node owns a share. The simplest rule, hash(key) % N, spreads them evenly, but changing N moves almost every key: going from 3 nodes to 4, about three quarters of keys land on a different node, and every moved key is a cache miss or a data copy.

Consistent hashing places nodes and keys on the same circular hash space, a ring. A key belongs to the first node clockwise from its position. Adding a node takes over only the arc between it and the node before it, about 1/N of the keys, and removing one hands its arc to the next node. Each physical node takes many virtual positions, so the arcs stay even.

Take a ring of positions 0 to 99 with nodes A at 20, B at 55, and C at 85. Key 30 belongs to B, the first node clockwise, and key 90 wraps around to A. Adding D at 70 moves only the keys between 55 and 70, such as key 60, from C to D; with % N, going from 3 nodes to 4 would move most keys.

• Caching

  Cache-aside is the read path everything here builds on.

  Open lesson

Case Scenario

To see how consistent hashing limits what moves, consider the cache tier of a URL shortener like bit.ly: redirect traffic no longer fits one cache node, so short codes are spread over a ring of cache nodes. Adding a node must move only a small slice of codes, not flush nearly every cached mapping at once.

Redirect traffic no longer fits one cache node, so every short code needs a predictable owner among several nodes. Capacity changes and failures must not make clients disagree or turn the next request for nearly every code into a database miss. Adding one cache node must move only a small fraction of mappings, not flush the whole cache fleet.