Consistency hashing is a technique for distributing keys across a dynamic set of servers, like in caching systems and distributed databases. Standard hashing modulo N assigns key K to server K mod N. When servers are added or removed, most keys are reassigned, causing cache misses and data movement. Consistency hashing solves this. Servers and keys are hashed to a ring.
Each key is assigned to the next server clockwise on the ring. When a server is added, only keys between that server and the previous one are reassigned. When a server is removed, only its keys are redistributed. The percentage of keys that move is proportional to the fraction of the ring affected, not the total number of keys. This greatly reduces churn when cluster membership changes.
Virtual nodes, multiple hash values per server, improve load balancing and strength. Consistent hashing is used in memcached, Cassandra, Redis, and other distributed systems.
Interactive Visualizer
Consistency Hashing
Keys and servers are placed on a ring. Each key is assigned to the next server clockwise. When servers are added/removed, only nearby keys are reassigned, minimizing data movement.