Consistent Hashing

Map both cache or storage nodes and data keys onto the same circular hash ring so that adding or removing a node reshuffles only (1/N) of all keys rather than requiring a full rehash of all data.

In distributed caches and data stores, adding or removing nodes with naive modulo sharding invalidates or migrates almost all data simultaneously, causing cache miss storms, I/O spikes, and service degradation during scaling events.

Naive modulo sharding (shard = hash(key) % N) has a critical operational flaw: when N changes (adding or removing a node), nearly all keys remap to different nodes. A cluster of 10 nodes growing to 11 reshuffles 91% of keys, causing a massive cache invalidation storm or a full data migration.

Consistent hashing solves this by placing both nodes and keys on a circular hash space (a ring of 2^32 positions). Each node occupies a position on the ring determined by hashing its identifier. A key is assigned to the node at the first ring position equal to or greater than the key's hash position (clockwise search). When a node is added, it takes responsibility only for keys between itself and the previous node: approximately (1/N) of total keys. When a node is removed, its keys move to the next node: again approximately (1/N) of total keys.

A naive consistent hash ring with N nodes has poor load distribution: with N random positions on the ring, one node might own 30% of the ring while another owns 5%. Virtual nodes (vnodes) solve this: each physical node is represented by V virtual nodes distributed across the ring (V = 100–300 is typical). Load distributes more uniformly as V increases. Virtual nodes also allow weighted assignment: a node with 2x the capacity gets 2x the vnodes.

Redis Cluster uses a variant called hash slots: 16,384 fixed slots are mapped to nodes, and keys hash to a slot. Adding a node migrates specific slot ranges with zero rehash of other keys. Cassandra and Dynamo use virtual node consistent hashing natively.