load balancing

Consistent Hashing

Map keys to a hash ring — adding/removing nodes only redistributes a minimal fraction of keys

Nodes3
Keys0
Ring Size360
Node-ANode-BNode-C
// nodes (click ring nodes to remove)
// key assignments
No keys added yet.

// event log

No events yet.

// how it works

  • Hash nodes and keys onto a circular ring
  • Each key is assigned to the next node clockwise
  • Adding a node only steals keys from its neighbor
  • Removing a node only moves its keys to the next
  • Only ~K/N keys move on topology change

// trade-offs

  • Minimal key redistribution on changes
  • Used in DynamoDB, Cassandra, CDNs
  • Uneven distribution without virtual nodes
  • Hash function quality matters a lot