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 resilience. Consistent hashing is used in memcached, Cassandra, Redis, and other distributed systems.
Back to Glossary