Consistent hashing explained: how hash rings limit remapping
Consistent hashing puts keys and servers on a hash ring, so adding an 11th server is expected to move about 1 key in 11; hash modulo N moves about 10 in 11.

Drafted with AI assistance, then checked and edited by a human engineer · How we write
Consistent hashing splits keys across servers so that adding or removing one server moves only a small share of the keys. With 10 equal servers, adding an 11th is expected to move about 1 key in 11 on a hash ring, while plain hash modulo the server count moves about 10 keys in 11.
The idea was introduced by Karger and colleagues in a 1997 paper on distributed web caching. The 2007 Dynamo paper describes its use with virtual nodes in a key-value store, and Apache Cassandra documents the same design.
Why hash modulo N remaps most keys
The simple rule is server = hash(key) mod N. It spreads keys evenly, but N is inside the formula.
Take N from 10 to 11. A key keeps its server only when h mod 10 equals h mod 11. Write h = 110q + r with 0 <= r < 110. Both remainders depend only on r, and they match only when r < 10 (a larger match would differ from its remainder by a multiple of 110). So 10 values of r out of 110 keep their server: 1 key in 11 stays, and about 90.9 percent move. In general, going from N to N + 1 keeps only 1/(N+1) of keys in place.
In a cache without migration or fallback reads, requests for remapped entries miss until those entries warm up again, and the database behind the cache takes that load. Adding servers to scale out changes N, so the placement rule has to cope with a changing N.
How does consistent hashing work?
Hash every server token and every key into the same space, say 0 to 2^32 minus 1, and treat that space as a ring that wraps from the largest value back to 0. A key belongs to the first token clockwise from its hash, wrapping to the first token if none sits after it. So each token owns the interval (previous token, this token].
What moves when a server joins
Each new token takes (previous token, new token] from whoever owned it. Existing tokens keep their positions, so every other interval keeps its owner and every key that moves goes to the new server. With 100 virtual nodes, the new server adds 100 such intervals, which can take keys from several existing servers.
For equally weighted servers, uniformly hashed keys and uniformly random tokens, the expected moved fraction is 1/(N+1), about 9.09 percent from 10 to 11 servers. The expectation is over random token placements. A particular ring can differ substantially, especially with one token per server; more virtual nodes reduce that variation.
| Rule | 10 to 11 servers | Who receives moved keys |
|---|---|---|
hash mod N | about 10/11 of keys move (90.9%) | every server, in a reshuffle |
| Hash ring | about 1/11 of keys move (9.09%), expected | only the new server |
Finding the owner
Keep the T tokens in a sorted array and binary search for the first token at or after the key's hash. This file runs with Node.js 22 and counts how many of 10,000 keys change owner when an 11th server joins a ring with 100 tokens per server. On our run it printed 757 of 10000 keys moved:
// ring-owner.mjs: node ring-owner.mjs
import { createHash } from 'node:crypto';
// 32-bit hash: first 4 bytes of MD5, so the ring is 0 .. 2^32 - 1
const h32 = (s) => createHash('md5').update(s).digest().readUInt32BE(0);
function buildRing(servers, vnodes) {
const tokens = [];
for (const s of servers)
for (let v = 0; v < vnodes; v++) tokens.push({ pos: h32(`${s}#vn-${v}`), server: s });
return tokens.sort((a, b) => a.pos - b.pos || (a.server < b.server ? -1 : 1));
}
function ringOwner(tokens, key) {
const k = h32(key);
let lo = 0, hi = tokens.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tokens[mid].pos < k) lo = mid + 1; else hi = mid;
}
return tokens[lo === tokens.length ? 0 : lo].server; // wrap around zero
}
const ten = Array.from({ length: 10 }, (_, i) => `server-${i}`);
const before = buildRing(ten, 100);
const after = buildRing([...ten, 'server-10'], 100);
let moved = 0;
for (let i = 0; i < 10_000; i++) {
if (ringOwner(before, `key-${i}`) !== ringOwner(after, `key-${i}`)) moved++;
}
console.log(`${moved} of 10000 keys moved`);
That is O(log T) per lookup. Ten servers with 100 tokens each is a 1,000-entry array that every client or router can hold.
What our lab measured
Our lab, labs/consistent-hashing-explained, extends the same code and also re-places every token 20 times to see how far one ring can land from the expectation. Run on 2026-11-14:
# shell
node labs/consistent-hashing-explained/simulate-ring-vs-modulo.mjs
| Setup | Keys moved, 10 to 11 | Spread at 10 servers (fullest, emptiest) | 20 other token placements |
|---|---|---|---|
hash % N | 9,051 (90.51%) | 1,053, 937 | does not apply |
| Ring, 1 token per server | 482 (4.82%) | 2,702, 130 | 0.13% to 26.1%, mean 8.21% |
| Ring, 100 tokens per server | 757 (7.57%) | 1,127, 869 | 7.05% to 9.98%, mean 8.79% |
On both rings every moved key went to the new server. With one token it took all 482 from a single neighbour; with 100 tokens it took keys from all 10. With one token per server, a single ring can land far from the expected 9.09 percent.
The lab is an in-memory placement model: it counts keys, not bytes, with no network, disk or replication.
Virtual nodes even out the load
With one token per server, each server's share is the length of one random arc, and random arcs vary a lot: some servers own several times the average while others own a sliver. The variation shrinks as each server gets more tokens, because its share becomes the sum of many small arcs. Tokens also act as weights: a machine with twice the capacity can take twice the tokens.
Extra tokens have costs. The Cassandra architecture documentation notes that every token can add neighbours on the ring, that more tokens raise the chance that some range loses availability when nodes fail, and that more tokens mean more discrete repair operations. Cassandra 2.x needed a default of 256 tokens per node to balance well, and later versions added a deterministic token allocator that balances with far fewer.
Joins, failures and what the ring does not do
Removing a server's tokens reassigns each interval to its next surviving token. With virtual nodes, several physical servers can receive those intervals, so the extra load is shared instead of landing on one neighbour. In our lab, removing one server sent its keys to 1 survivor with one token per server and to all 9 survivors with 100. After a failure, the data itself must come from surviving replicas or another durable copy; the ring only says where requests go next.
On a join, the ring says which keys the new server should own, and moving the data is a separate step. For a simple safe handoff, pause writes to the affected ranges, drain in-flight writes, copy and verify the data, then switch ownership. Keep forwarding requests from stale routers during the transition. Online migration needs concurrent-write synchronization.
Replica placement is layered on top. Dynamo's preference list skips repeated physical servers. Cassandra chooses replicas through a configured replication strategy; NetworkTopologyStrategy also accounts for datacenters and racks. Both solve the problem behind read replicas and failover, per range of the ring.
The ring also places keys without measuring traffic. One hot key always maps to one interval and one owner, whatever the token count, so hot keys need caching, key splitting or replication. Request routing for stateless servers is a different problem, covered by load balancing algorithms.
Our take
Use a hash ring with virtual nodes when servers join and leave while the data stays put, as in caches and partitioned stores. A membership change then moves roughly the share of keys the changed server should own. The data handoff, the replicas and hot-key handling are still yours to build.
If your shards are numbered and you only add or remove from the end, jump consistent hash by Lamping and Veach gives the same minimal movement with no ring to store. For a fixed cluster that never changes size, hash mod N is simpler and fine.
FAQ
What is consistent hashing in simple terms?
A way to split keys across servers by placing both on one hash ring. Each key belongs to the next server token clockwise. When a server joins, it takes only the keys between the token before it and its own token, so most keys stay where they were.
Why not just use hash modulo the server count?
The server count is part of the formula, so changing it changes the answer for most keys. Going from 10 to 11 servers, a key keeps its server only when its hash mod 110 is below 10, which leaves about 1 key in 11 in place and moves the rest.
What are virtual nodes for?
With one token per server the arcs between tokens are random and uneven, so some servers own far more keys than others. Giving each server many tokens averages those arcs out, lets a bigger machine take more tokens, and spreads a joining or failed server's ranges across many servers.
This article describes general, publicly documented designs (the 1997 paper, the Dynamo paper and Apache Cassandra's documentation), not any company's current private systems.
Frequently asked questions
What is consistent hashing in simple terms?
A way to split keys across servers by placing both on one hash ring. Each key belongs to the next server token clockwise. When a server joins, it takes only the keys between the token before it and its own token, so most keys stay where they were.
Why not just use hash modulo the server count?
The server count is part of the formula, so changing it changes the answer for most keys. Going from 10 to 11 servers, a key keeps its server only when its hash mod 110 is below 10, which leaves about 1 key in 11 in place and moves the rest.
What are virtual nodes for?
With one token per server the arcs between tokens are random and uneven, so some servers own far more keys than others. Giving each server many tokens averages those arcs out, lets a bigger machine take more tokens, and spreads a joining or failed server's ranges across many servers.
Sources
- Karger et al. (1997): Consistent Hashing and Random Treespeople.csail.mit.edu
- DeCandia et al. (2007): Dynamo, Amazon's highly available key-value storeallthingsdistributed.com
- Apache Cassandra documentation: Dynamo architecturecassandra.apache.org
- Lamping and Veach (2014): A Fast, Minimal Memory, Consistent Hash Algorithmarxiv.org