The Rebalancing Act

Standard modulo hashing (hash(key) % n) breaks everything when n changes. If you add a server, almost every key gets remapped.

The Ring

Consistent hashing maps both servers and keys to a circle (0 to 2^32 - 1).

  1. Hash your servers to points on the ring.
  2. Hash your key to a point on the ring.
  3. Walk clockwise to find the first server.

Virtual Nodes

To prevent hotspots where one server handles too much of the ring, we use Virtual Nodes. Each physical server effectively exists at multiple points on the ring.

"Consistent hashing allows us to add or remove nodes with minimal disruption."

This is the backbone of systems like DynamoDB and Cassandra.