Consistent hashing

In short: Consistent hashing places keys and servers on a ring. A key belongs to the next server clockwise. When a server joins or leaves, only a small part of the assignment changes.

In more detail: With simple hash(key) % n almost all assignments change when n changes. With the ring only about K/n keys move on average. Virtual nodes (each server appears several times on the ring) ensure even distribution.

In Depth

• Ring: Hash space 0 … 2^32−1 imagined as a circle.
• Assignment: Key → first server clockwise.
• Virtual nodes: Smooths uneven gaps and servers of different strength.
• Replication: Also place the key on the next N servers.
• Use: Caches (Memcached clusters), Dynamo, Cassandra, CDNs.
• Alternative: Rendezvous (HRW) hashing.

See also: Sharding and partitioning, Gossip protocols