Distributed Systems

Consistent hashing

Hash both keys and servers onto a ring; each key belongs to the next server clockwise.

Main article: Consistent hashing simulator

In plain terms

Karger and colleagues at MIT, 1997. Adding or removing a server moves only about K/N of the K keys, instead of nearly all of them as with hash mod N. Used by Cassandra, Riak and many cache client libraries.

Origin

David Karger, Eric Lehman, Tom Leighton, Matt Levine, Daniel Lewin, and Rina Panigrahy, MIT 1997. The paper "Consistent Hashing and Random Trees" was about relieving hot spots on the web with a network of caches; the idea was later used in many distributed caches, CDNs and Dynamo-style databases. Leighton and Lewin co-founded Akamai a year later.

Where it shows up in production

Akamai CDN The original commercial application: assigns clients to edge caches.
Amazon Dynamo / Cassandra A ring with virtual nodes: each server owns many small ranges of the ring rather than one large one.
Memcached client libraries Libraries such as ketama map cache keys to servers, so removing a server only loses the keys it held (about 1/N).

On Semicolony

Simulator: consistent hashing Simulator: consistent hashing

Sources & further reading

Found this useful?