5 · Partitioning & consistency · Consistent hashing

Consistent hashing

ABCk1k2k3Keys walk clockwise to the next node:k1 → B, k2 → C, k3 → AAdd node D between A and B:only keys in that arc move (~1/N),not almost all of them like hash % N.

With hash % N, changing N remaps nearly every key. Consistent hashing places nodes and keys on a ring; adding/removing a node moves only its neighbors' keys. Virtual nodes (each server appears many times on the ring) smooth out the load. Used by DynamoDB, Cassandra, and cache clusters.