Suppose you spread data over ten cache servers by computing hash(key) mod 10. It works nicely until the day you add an eleventh server. Now every key must be recomputed as mod 11, and almost all of them land on a different server. Every cache suddenly misses, and the databases behind them get flooded.
In 1997, a group of MIT researchers described a fix in a paper about relieving hot spots on the World Wide Web, the moments when a popular page gets far more requests than one server can handle. Their tool, consistent hashing, changed how almost every large caching and storage system spreads data.
Hash both servers and keys onto a circle. A key belongs to the first server clockwise from it. When a server joins or leaves, only the keys in one arc of the circle move, about 1 in N of them, instead of nearly all.
The problem with hash mod N
Ordinary hashing spreads keys evenly when the number of buckets never changes. The paper points out that on the Web the set of caches does change, and different clients may not even agree on which caches exist. Plain hashing breaks as soon as clients disagree, because changing the count changes almost every answer.
The authors want a hash scheme that is consistent: when buckets are added or removed, as few items as possible should change buckets.
The ring
Imagine the possible hash values laid out on a circle. Pick a hash function and use it twice: once to place each server on the circle, and once to place each key. To find where a key lives, start at its position and walk clockwise until you meet a server.
