The encyclopedia · Software & IT · Technical decision · 1997
Consistent hashing spread cache keys so adding a server moves only ~1/n of them
Karger's MIT team, in 1997, hashed keys and servers onto a ring so any resize remaps only ~1/n of keys, and Akamai built its CDN on it.
MIT · Akamai Technologies
the move
Serving a website from a cache farm means deciding which server holds which key. The standard trick, modulo hashing, remaps nearly every key as soon as a server is added or dies, causing a thundering herd.
Karger's team solved it by laying both the keys and the servers on a circular space and sending each key to the next server clockwise. Adding or removing a node moves only the small arc immediately before it.
The insight is that membership is a position on a ring, not a division of a fixed number of buckets. Akamai's founders were co-authors, and the idea became the base of the content delivery network.
why it works
- A resize moves ~1/n of keys instead of nearly all, so no cache-storm.
- Servers sit on the same hash space as keys, so ownership is local and unambiguous.
- Virtual nodes smooth uneven key distribution among real servers.
- Membership can change in any order and the invariant still holds.
what transfers
If a membership change normally invalidates most of the system, map each unit to the next member on a ring. Then a resize touches only the slice around the new or gone member.
what came after
Consistent hashing became the standard way to shard and cache in distributed systems, powering Akamai's CDN, distributed databases, memcached clusters and peer-to-peer networks. It is the reason a growing cache farm scales without a full rebalance.
references
- Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web
- Consistent hashing
spotted an error? The archive wants to know.