The Problem with Simple Hashing
With N servers, a simple hash assigns key K to server shard_id = hash(K) % N. This works fine until you add or remove a server. With N=4 servers, hash("user123") % 4 = 2 → Server 2. When you add a 5th server, hash("user123") % 5 = 3 → Server 3. Every key is potentially remapped to a different server. Migrating all data is expensive and causes downtime. For a cache, this means a complete cache miss storm — every key is suddenly on the wrong server.
Consistent Hashing — The Hash Ring
Map both servers and keys to points on a circular hash space (0 to 2^32 - 1). Servers are hashed by their name/IP: server_position = hash("Server_A"). Keys are hashed the same way: key_position = hash("user123"). Assign each key to the first server clockwise from the key's position on the ring.
When Server D is added between Server A and Server B: only the keys between Server A and Server D are remapped to Server D. All other keys are unaffected. This means only K/N keys are remapped, not all keys.
When Server B is removed: only the keys previously assigned to Server B (between Server A and Server B) are remapped to Server C (the next server clockwise). Again, O(1/N) fraction of keys are remapped.
graph TD Ring["Hash Ring (0 to 2^32)"] Ring --> SA["Server A (pos: 12)"] Ring --> SB["Server B (pos: 37)"] Ring --> SC["Server C (pos: 63)"] Ring --> Key1["Key 'user123' (pos: 15) → assigned to Server B"] Ring --> Key2["Key 'item456' (pos: 40) → assigned to Server C"]
Virtual Nodes for Uniform Distribution
With only 3 physical servers on a large ring, the key distribution may be uneven (one server gets a larger arc). Virtual nodes (vnodes) solve this: each physical server is mapped to multiple positions on the ring (typically 100-200 virtual nodes per server). For example, Server A maps to positions: hash("Server_A_0"), hash("Server_A_1"), ..., hash("Server_A_99").
With many virtual nodes, each server gets many small arcs around the ring that average out to an equal share. When a new server is added, it takes virtual node positions from all existing servers evenly. This balances load across servers naturally.
Vnodes also allow heterogeneous servers: a server with 2× RAM gets 2× virtual nodes and handles 2× the keys. Cassandra uses 256 vnodes per node by default.
Replication on the Ring
For fault tolerance, each key is stored on multiple servers. With replication factor R, a key assigned to Server A is also stored on the next R-1 clockwise servers (Server B, Server C). This means each key has R replicas on R consecutive servers.
When a server fails, its keys are served by the replica servers. When the failed server recovers, it resyncs from its replicas. This is how Cassandra, DynamoDB, and Riak implement replication — the ring position determines both primary assignment and replica placement.
Use Cases
Distributed caches: Memcached and Redis Cluster use consistent hashing to route cache keys to the right shard. Adding a cache shard only invalidates a 1/N fraction of keys rather than all keys.
Distributed databases: Cassandra and DynamoDB use consistent hashing for partitioning data across nodes. Automatic rebalancing on node add/remove.
Load balancers: some layer-4 load balancers use consistent hashing on client IP to maintain session affinity without a session store — the same client always hits the same backend server.
Distributed coordination: Chord, a peer-to-peer lookup protocol, uses consistent hashing to route queries to the responsible node in O(log N) hops.