Distribute data across nodes with minimal redistribution when nodes join or leave.
Published September 21, 2026
When data is spread across several servers (cache nodes, database shards), every request needs a rule for which server owns this key. Consistent hashing is a rule with one crucial property: when a server is added or removed, only a small fraction of keys move, about 1/N of them, instead of almost all of them. That property is what makes it possible to scale a cache or a database cluster up and down without a storm of misses or a massive data reshuffle.
The simplest rule is server = hash(key) % N:
N = 4 servers: hash("user:42") = 1234567 → 1234567 % 4 = 3 → server 3
N = 5 servers: hash("user:42") = 1234567 → 1234567 % 5 = 2 → server 2 (moved!)
Change N and the remainder changes for most keys. Going from 4 to 5 servers remaps about 80% of all keys (in general, only about 1/(N+1) of keys stay put). For a cache, that means a sudden flood of misses that all hit the database at once. For a sharded database, it means moving most of your data just to add one machine.
Consistent hashing maps both servers and keys onto the same circular number space (say 0 to 2³²−1, wrapping around):
0 / 2^32
│
S1 ●───────┼────────● S2
/ k1 │ k2 \ k1 → S2 (next server clockwise)
/ │ \ k2 → S3
● S4 │ ● S3 k3 → S4
\ k3 │ /
\________│_________/
Adding a server S5 between S1 and S2 only takes over the keys between S1 and S5, which previously belonged to S2. Every other key keeps its server. Removing a server hands its keys to the next server clockwise, and no other key moves.
With a handful of servers at random ring positions, the arcs between them are very unequal. One server might own 45% of the ring and another 10%. And when a server dies, all of its keys land on a single neighbour, which may then be overloaded too.
The fix is virtual nodes: place each physical server at many positions (100–200 is typical) by hashing "S1#0", "S1#1", … Each server then owns many small arcs scattered around the ring:
public class ConsistentHashRing<T> {
private final NavigableMap<Long, T> ring = new TreeMap<>();
private final int virtualNodes;
public ConsistentHashRing(int virtualNodes) { this.virtualNodes = virtualNodes; }
public void add(T server) {
for (int i = 0; i < virtualNodes; i++) ring.put(hash(server + "#" + i), server);
}
public void remove(T server) {
for (int i = 0; i < virtualNodes; i++) ring.remove(hash(server + "#" + i));
}
public T serverFor(String key) {
if (ring.isEmpty()) throw new IllegalStateException("no servers");
Map.Entry<Long, T> e = ring.ceilingEntry(hash(key)); // first position ≥ key's hash
return (e != null ? e : ring.firstEntry()).getValue(); // wrap around past the end
}
// A well-distributed hash matters: String.hashCode() clusters similar strings badly.
private static long hash(String s) {
try {
byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
return ((long) (d[0] & 0xFF) << 24) | ((d[1] & 0xFF) << 16) | ((d[2] & 0xFF) << 8) | (d[3] & 0xFF);
} catch (NoSuchAlgorithmException e) {
throw new IllegalStateException(e);
}
}
}
The TreeMap makes lookup O(log V), where V is the total number of virtual nodes. Production systems use fast non-cryptographic hashes such as MurmurHash3 or xxHash. MD5 is used here only because it's in the JDK and spreads values well.
To store each key on R servers for fault tolerance, walk clockwise from the key and take the next R distinct physical servers, skipping virtual nodes that belong to a server already chosen. This is how Dynamo-style databases (Cassandra, Riak, DynamoDB's design) place replicas.
CRC16(key) % 16384), each assigned to a node. Rebalancing moves whole slots between nodes. It achieves the same goal (adding a node moves only some data) with an explicit slot table instead of a ring.Q: How many keys move when you add a server to a ring of N servers?
A: About 1/(N+1) of all keys, the share the new server takes over. With hash % N, roughly N/(N+1) of keys would move instead.
Q: Why are virtual nodes necessary? A: With few physical positions the arcs are uneven, so some servers get much more load. A failed server's whole range would also fall on one neighbour. Many virtual positions per server even out ownership and spread a failed server's load across the cluster. They also let you weight servers by capacity.
Q: What's the time complexity of finding the server for a key? A: O(log V) with a sorted structure (a balanced tree or binary search over sorted positions), where V = servers × virtual nodes. With V in the thousands, that's a handful of comparisons.
Q: Does consistent hashing solve hot keys? A: No. It distributes the key space evenly, but one key always maps to one server. Hot keys need replication of that key, request coalescing, or a local cache in front.
Q: How is Redis Cluster's approach different? A: Redis Cluster hashes keys into 16,384 fixed slots and keeps an explicit slot-to-node table. Scaling moves slots between nodes, and clients learn the new mapping through redirect replies. It isn't a hash ring, but it gives the same benefit (limited data movement) with simpler, explicit control over which node owns what.