Consistent Hashing
Consistent hashing is one of the most practically important algorithms in distributed systems. It solves a deceptively simple problem: how do you distribute data across N nodes such that adding or removing a node requires moving only a minimal amount of data?
Why It Exists
The Naive Approach and Its Failure
The obvious way to distribute keys across nodes:
This works perfectly — until you add or remove a node. When changes to , the modulus changes for almost every key:
With N=3:
hash("user:1") % 3 = 1 → Node B
hash("user:2") % 3 = 0 → Node A
hash("user:3") % 3 = 2 → Node C
With N=4 (added Node D):
hash("user:1") % 4 = 2 → Node C ← MOVED
hash("user:2") % 4 = 3 → Node D ← MOVED
hash("user:3") % 4 = 1 → Node B ← MOVED
On average, when going from to nodes, the fraction of keys that need to move is:
For nodes, adding one node moves 99% of all keys. In a caching layer with billions of keys, this means a near-total cache miss storm — a thundering herd that can take down your backend.
The Consistent Hashing Solution
Consistent hashing, introduced by David Karger et al. in 1997, guarantees that when going from to nodes, only keys need to move (where is the total number of keys). This is the theoretical minimum — you can't do better.
Why is the minimum? After the change, a balanced scheme must give the new node of the keys, and every one of those keys used to live somewhere else. So at least that many must move. The goal of every algorithm on this page is to move only those keys, while keeping the load balanced, using little memory and answering lookups fast. They differ in which of those four goals they compromise on.
The Karger paper's motivation was web caching: a client should find which cache holds a URL without a central directory, and caches should be added and removed without invalidating everything. Akamai, which Karger's co-authors went on to found, was built on the idea.
A Worked Example of the Difference
A cache tier holds 100 million keys on 10 nodes, and you add an 11th.
| Scheme | Keys that move | What that means |
|---|---|---|
hash(key) mod N | About , roughly 90.9 million | Nearly the whole cache is cold at once |
| Consistent hashing | About , roughly 9.1 million | Only the new node starts cold |
If the backing database can absorb 5,000 extra misses per second and each key is read about once every 10 minutes, the modulo scheme suddenly creates around 150,000 misses per second (90.9 million keys over 600 seconds), 30 times what the database can take. Consistent hashing creates about 15,000, still three times the budget, which is why even consistent rehashing is usually done one node at a time and with cache warming.
Core Mechanics
The Hash Ring
Imagine the output space of a hash function as a circle (ring) from to :
- Nodes are placed on the ring by hashing their identifier (IP address, hostname, etc.)
- Keys are placed on the ring by hashing the key
- Assignment rule: A key is assigned to the first node encountered when walking clockwise from the key's position
Ring (0 → 2^32):
0 ─────── Node A (pos: 100) ─────── Node B (pos: 500) ─────── Node C (pos: 800) ─────── 2^32
↑ ↑ ↑
Keys 0-100 Keys 101-500 Keys 501-800
assigned to A assigned to B assigned to C
Keys 801-2^32
assigned to A (wraps)
Adding a Node
When Node D is added at position 300:
Before:
Node A (100) ──────────── Node B (500) ──── Node C (800)
Keys: 801-100 Keys: 101-500 Keys: 501-800
After adding Node D at 300:
Node A (100) ── Node D (300) ── Node B (500) ── Node C (800)
Keys: 801-100 Keys: 101-300 Keys: 301-500 Keys: 501-800
Only keys in the range 101-300 moved — from Node B to Node D. Nodes A and C are completely unaffected. The fraction of keys that moved is approximately .
Removing a Node
When Node B is removed:
Before:
Node A (100) ── Node D (300) ── Node B (500) ── Node C (800)
After removing Node B:
Node A (100) ── Node D (300) ──────────────── Node C (800)
Keys: 801-100 Keys: 101-300 Keys: 301-800
Only Node B's keys (301-500) moved to Node C. All other assignments unchanged.
Notice where B's keys went: all of them to a single node, its clockwise successor C. Without virtual nodes, a node failure doubles (on average) the load of exactly one neighbour, and that neighbour is the node most likely to fall over next. The same is true in reverse on a join: the new node takes all of its keys from one node. Virtual nodes, below, fix both by spreading each node's arcs around the ring.
The Ring Math
Treat node positions as points dropped uniformly at random on a circle of circumference 1. The gaps between neighbouring points (the "arcs", each owned by the point at its clockwise end) have a well-known distribution: each gap is approximately exponential with mean . Three consequences follow directly.
1. Individual nodes are very unbalanced. An exponential variable has a standard deviation equal to its mean, so with one point per node the load of a node varies by about ±100% of the average. Some nodes get almost nothing.
2. The biggest arc is about times the average. The largest of exponential gaps with mean has expected value , where . For 10 nodes the hottest gets about 2.9× the average share, for 100 nodes about 5.2×. That is the imbalance stated below.
3. A key's owner is found by a successor search. Keep the node positions in a sorted array. A lookup hashes the key and binary-searches for the first position at or after it, wrapping to index 0 at the end, so it costs .
Key movement on join. A new node lands in some existing arc and takes the part of it that precedes its position. Its expected share is , but without virtual nodes the actual share is again exponential, so one join may move almost nothing and the next may move three times the average.
The Load Balancing Problem and Virtual Nodes
The Problem
With physical nodes placed randomly on a ring of size , the expected arc length per node is . But the variance is high. By the birthday paradox and properties of uniform distributions, some nodes will get arcs that are significantly larger or smaller than average.
For nodes uniformly distributed on a ring, the expected maximum load ratio is:
With 10 nodes, some node will handle roughly the average load. With 100 nodes, the hottest node handles average. This is unacceptable.
Virtual Nodes (vnodes)
The solution: instead of placing each physical node at one position on the ring, place it at positions (virtual nodes).
Physical Node A → Virtual nodes: A-0, A-1, A-2, ..., A-149
Physical Node B → Virtual nodes: B-0, B-1, B-2, ..., B-149
Physical Node C → Virtual nodes: C-0, C-1, C-2, ..., C-149
Each virtual node is hashed independently and placed on the ring. With virtual nodes per physical node, the ring has points, and the load distribution approaches uniform.
The standard deviation of load per node with virtual nodes is:
With (Cassandra's default), the standard deviation is less than 10% of the mean — most nodes carry between 90% and 110% of the average load.
Correction
150 is not Cassandra's default. Cassandra's num_tokens defaulted to 256 from version 1.2 (when virtual nodes were introduced) until 4.0, which changed the default to 16, paired with a token allocation algorithm (allocate_tokens_for_local_replication_factor) that places tokens deliberately rather than at random, so that 16 tokens give good balance. The 1/√V arithmetic in this paragraph is right: at V = 150 the standard deviation is about 8% of the mean. The "Choosing V" table below has the same mistake in its 150 row. A commonly quoted 150-or-160 figure comes from libketama, the memcached client library, which places 160 points per server by default.
Where comes from. With virtual nodes per physical node, a node's share is the sum of roughly independent exponential arcs, each with mean . The sum of independent variables each with standard deviation has standard deviation , so the node's share has mean and standard deviation . Relative to the mean, that is , the formula above.
A simulation with 100 physical nodes, MD5 positions, measuring each node's share of the ring:
| V | Std dev of load (% of mean) | Most loaded node (× mean) |
|---|---|---|
| 1 | 112% | 5.1 |
| 10 | 28% | 1.9 |
| 100 | 10% | 1.27 |
| 256 | 6.3% | 1.16 |
| 1,000 | 3.2% | 1.07 |
The middle column follows closely. The right column is the one that matters for capacity planning, because you have to provision for the most loaded node: even at , one node in a hundred carries 16% more than average. That residual imbalance is what bounded-load hashing (below) removes.
What Virtual Nodes Cost
More virtual nodes is not free, and the trend in real systems has been toward fewer, better-placed tokens:
- Memory and lookup: the ring has entries. At 1,000 nodes and that is 256,000 entries, which is fine for one router but adds up when every client holds the ring.
- Replica sets touch many nodes. With many random tokens, the ranges a node replicates are shared with almost every other node. In a cluster with replication factor 3, losing any two nodes then makes some range lose two of its three replicas. With few tokens per node, a node shares ranges with only a few neighbours, so most two-node failures leave every range with a quorum.
- Repair and streaming fan-out. Background repair and bootstrap must talk to every node that shares a range. With hundreds of tokens, that is effectively every node in the cluster.
This is why Cassandra 4.0 moved to 16 tokens with a placement algorithm. The algorithm gets most of the balance that 256 random tokens gave, without the availability and repair costs.
Choosing V
| V (virtual nodes) | Load std dev | Memory per node | Recommended for |
|---|---|---|---|
| 1 | ~100% of mean | Minimal | Never use in production |
| 10 | ~32% of mean | Low | Small clusters (<10 nodes) |
| 100 | ~10% of mean | Moderate | Most production systems |
| 150 | ~8% of mean | Moderate | Common choice (libketama uses 160). Cassandra's default was 256, and 16 since 4.0 |
| 256 | ~6% of mean | Higher | Large clusters, strict balance requirements |
| 1000+ | ~3% of mean | High | Rarely worth the memory cost |
Heterogeneous Nodes
Virtual nodes elegantly handle nodes with different capacities. A node with 2x the CPU and memory gets 2x the virtual nodes:
class ConsistentHashRing<T> {
private ring: Map<number, T> = new Map();
private sortedHashes: number[] = [];
addNode(node: T, id: string, weight: number = 1, baseVnodes: number = 150): void {
const vnodeCount = Math.round(baseVnodes * weight);
for (let i = 0; i < vnodeCount; i++) {
const hash = this.hash(`${id}:${i}`);
this.ring.set(hash, node);
this.sortedHashes.push(hash);
}
this.sortedHashes.sort((a, b) => a - b);
}
removeNode(id: string, weight: number = 1, baseVnodes: number = 150): void {
const vnodeCount = Math.round(baseVnodes * weight);
for (let i = 0; i < vnodeCount; i++) {
const hash = this.hash(`${id}:${i}`);
this.ring.delete(hash);
const idx = this.sortedHashes.indexOf(hash);
if (idx !== -1) this.sortedHashes.splice(idx, 1);
}
}
getNode(key: string): T | undefined {
if (this.sortedHashes.length === 0) return undefined;
const hash = this.hash(key);
// Binary search for the first hash >= key's hash
let idx = this.binarySearchCeil(hash);
if (idx >= this.sortedHashes.length) idx = 0; // Wrap around
return this.ring.get(this.sortedHashes[idx]);
}
// Get N distinct physical nodes for replication
getNodes(key: string, count: number): T[] {
const result: T[] = [];
const seen = new Set<T>();
if (this.sortedHashes.length === 0) return result;
const hash = this.hash(key);
let idx = this.binarySearchCeil(hash);
while (result.length < count && seen.size < this.ring.size) {
if (idx >= this.sortedHashes.length) idx = 0;
const node = this.ring.get(this.sortedHashes[idx])!;
if (!seen.has(node)) {
seen.add(node);
result.push(node);
}
idx++;
}
return result;
}
private hash(key: string): number {
// MurmurHash3 or similar — using simple hash for illustration
let hash = 0;
for (let i = 0; i < key.length; i++) {
const char = key.charCodeAt(i);
hash = ((hash << 5) - hash) + char;
hash = hash & hash; // Convert to 32-bit integer
}
return Math.abs(hash);
}
private binarySearchCeil(target: number): number {
let lo = 0;
let hi = this.sortedHashes.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.sortedHashes[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
}
Production Implementation
Here's a production-grade consistent hash ring with proper hashing, replication awareness, and monitoring:
import { createHash } from 'crypto';
interface NodeInfo {
id: string;
host: string;
port: number;
weight: number;
zone: string; // Availability zone for rack-aware placement
}
interface RingConfig {
baseVnodes: number;
replicationFactor: number;
hashFunction: 'md5' | 'sha256' | 'murmur3';
}
class ProductionHashRing {
private ring: Map<number, string> = new Map(); // hash → nodeId
private sortedHashes: number[] = [];
private nodes: Map<string, NodeInfo> = new Map();
private config: RingConfig;
constructor(config: Partial<RingConfig> = {}) {
this.config = {
baseVnodes: 150,
replicationFactor: 3,
hashFunction: 'md5',
...config,
};
}
addNode(node: NodeInfo): { movedKeys: number; affectedNodes: string[] } {
this.nodes.set(node.id, node);
const vnodeCount = Math.round(this.config.baseVnodes * node.weight);
const affectedNodes = new Set<string>();
for (let i = 0; i < vnodeCount; i++) {
const hash = this.hashKey(`${node.id}#${i}`);
// Find which node previously owned this portion of the ring
const previousOwner = this.getNodeIdForHash(hash);
if (previousOwner) affectedNodes.add(previousOwner);
this.ring.set(hash, node.id);
this.insertSorted(hash);
}
// Estimate moved keys (proportional to arc length acquired)
const movedKeys = Math.round(vnodeCount / this.sortedHashes.length * 100);
return { movedKeys, affectedNodes: [...affectedNodes] };
}
removeNode(nodeId: string): { movedKeys: number; targetNodes: string[] } {
const node = this.nodes.get(nodeId);
if (!node) throw new Error(`Node ${nodeId} not found`);
const vnodeCount = Math.round(this.config.baseVnodes * node.weight);
const targetNodes = new Set<string>();
for (let i = 0; i < vnodeCount; i++) {
const hash = this.hashKey(`${nodeId}#${i}`);
this.ring.delete(hash);
const idx = this.sortedHashes.indexOf(hash);
if (idx !== -1) this.sortedHashes.splice(idx, 1);
// Find which node now owns this portion
const newOwner = this.getNodeIdForHash(hash);
if (newOwner) targetNodes.add(newOwner);
}
this.nodes.delete(nodeId);
const movedKeys = Math.round(vnodeCount / (this.sortedHashes.length + vnodeCount) * 100);
return { movedKeys, targetNodes: [...targetNodes] };
}
// Get the primary node for a key
getNode(key: string): NodeInfo | undefined {
const nodeId = this.getNodeIdForHash(this.hashKey(key));
return nodeId ? this.nodes.get(nodeId) : undefined;
}
// Get replication set — N distinct physical nodes, preferably in different zones
getReplicaSet(key: string): NodeInfo[] {
const result: NodeInfo[] = [];
const seenIds = new Set<string>();
const seenZones = new Set<string>();
const hash = this.hashKey(key);
let idx = this.binarySearchCeil(hash);
let attempts = 0;
// First pass: try to get nodes in different zones
while (result.length < this.config.replicationFactor && attempts < this.sortedHashes.length) {
if (idx >= this.sortedHashes.length) idx = 0;
const nodeId = this.ring.get(this.sortedHashes[idx])!;
const node = this.nodes.get(nodeId)!;
if (!seenIds.has(nodeId)) {
// Prefer nodes in different zones for fault tolerance
if (!seenZones.has(node.zone) || result.length >= this.availableZoneCount()) {
seenIds.add(nodeId);
seenZones.add(node.zone);
result.push(node);
}
}
idx++;
attempts++;
}
// If we couldn't fill the replica set with zone diversity, relax the constraint
if (result.length < this.config.replicationFactor) {
idx = this.binarySearchCeil(hash);
attempts = 0;
while (result.length < this.config.replicationFactor && attempts < this.sortedHashes.length) {
if (idx >= this.sortedHashes.length) idx = 0;
const nodeId = this.ring.get(this.sortedHashes[idx])!;
const node = this.nodes.get(nodeId)!;
if (!seenIds.has(nodeId)) {
seenIds.add(nodeId);
result.push(node);
}
idx++;
attempts++;
}
}
return result;
}
// Ring statistics for monitoring
getStats(): {
nodeCount: number;
vnodeCount: number;
loadDistribution: Map<string, { vnodes: number; loadPercent: number }>;
} {
const loadMap = new Map<string, number>();
for (const nodeId of this.ring.values()) {
loadMap.set(nodeId, (loadMap.get(nodeId) || 0) + 1);
}
const totalVnodes = this.sortedHashes.length;
const loadDistribution = new Map<string, { vnodes: number; loadPercent: number }>();
for (const [nodeId, vnodes] of loadMap) {
loadDistribution.set(nodeId, {
vnodes,
loadPercent: (vnodes / totalVnodes) * 100,
});
}
return {
nodeCount: this.nodes.size,
vnodeCount: totalVnodes,
loadDistribution,
};
}
private availableZoneCount(): number {
const zones = new Set<string>();
for (const node of this.nodes.values()) zones.add(node.zone);
return zones.size;
}
private getNodeIdForHash(hash: number): string | undefined {
if (this.sortedHashes.length === 0) return undefined;
let idx = this.binarySearchCeil(hash);
if (idx >= this.sortedHashes.length) idx = 0;
return this.ring.get(this.sortedHashes[idx]);
}
private hashKey(key: string): number {
const hashBuffer = createHash(this.config.hashFunction)
.update(key)
.digest();
// Use first 4 bytes as a 32-bit unsigned integer
return hashBuffer.readUInt32BE(0);
}
private binarySearchCeil(target: number): number {
let lo = 0;
let hi = this.sortedHashes.length;
while (lo < hi) {
const mid = (lo + hi) >>> 1;
if (this.sortedHashes[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
private insertSorted(hash: number): void {
const idx = this.binarySearchCeil(hash);
this.sortedHashes.splice(idx, 0, hash);
}
}
Alternative: Jump Consistent Hashing
Google's Jump Consistent Hash (Lamping & Veach, 2014) achieves perfect balance with O(1) memory and O(ln n) time — but only works when nodes are numbered 0 to N-1 (no arbitrary node IDs).
function jumpConsistentHash(key: bigint, numBuckets: number): number {
let b = -1n;
let j = 0n;
while (j < BigInt(numBuckets)) {
b = j;
key = ((key * 2862933555777941757n) + 1n) & 0xFFFFFFFFFFFFFFFFn;
j = BigInt(Math.floor((Number(b) + 1) * (Number(1n << 31n) / Number((key >> 33n) + 1n))));
}
return Number(b);
}
Properties:
- Perfect balance: each bucket gets exactly of keys
- Minimal movement: when going from to , exactly of keys move
- O(1) memory: no ring structure needed
- O(ln N) time: the loop executes approximately times
- Limitation: buckets must be numbered 0 to N-1. You can't remove bucket 3 and keep bucket 4 — you can only add/remove from the end.
How it works. Think of growing the number of buckets one at a time, from 1 to . When bucket is added, each key should move to it with probability (for buckets numbered from 0, going from to buckets), and otherwise stay where it was. Simulating that step by step would take time. The trick is to compute, with the key's own pseudo-random sequence, the next at which the key jumps, skipping all the steps in between. The chance that a key jumps at step is about , so the number of jumps up to is about . That explains both properties: perfect balance and minimal movement come from the step-by-step definition, and time comes from the jumps.
A Python version with a check of the movement claim:
def jump_hash(key: int, num_buckets: int) -> int:
b, j = -1, 0
while j < num_buckets:
b = j
key = (key * 2862933555777941757 + 1) & 0xFFFFFFFFFFFFFFFF
j = int((b + 1) * (float(1 << 31) / float((key >> 33) + 1)))
return b
keys = range(200_000)
before = [jump_hash(k * 0x9E3779B97F4A7C15 & 0xFFFFFFFFFFFFFFFF, 10) for k in keys]
after = [jump_hash(k * 0x9E3779B97F4A7C15 & 0xFFFFFFFFFFFFFFFF, 11) for k in keys]
moved = [a for b, a in zip(before, after) if a != b]
assert all(a == 10 for a in moved) # keys only ever move to the new bucket
assert abs(len(moved) / len(keys) - 1 / 11) < 0.01
print(f"moved {len(moved) / len(keys):.4f}, expected {1 / 11:.4f}")
Using it with real servers. Because buckets are numbers, jump hash fits systems where shards are numbered and the cluster only grows or shrinks at the end: storage shards, or replicas of a numbered partition. A common pattern is two levels. Jump hash maps keys to a fixed, generous number of logical shards, and a separate table maps logical shards to whichever physical machines currently hold them. Machines can then fail and be replaced in any order, because only the table changes.
Alternative: Rendezvous Hashing (Highest Random Weight)
function rendezvousHash(key: string, nodes: string[]): string {
let maxWeight = -Infinity;
let selectedNode = nodes[0];
for (const node of nodes) {
const weight = hash(`${key}:${node}`);
if (weight > maxWeight) {
maxWeight = weight;
selectedNode = node;
}
}
return selectedNode;
}
Properties:
- O(N) per lookup (must check all nodes)
- Perfect balance without virtual nodes
- Minimal disruption: adding/removing a node moves only of keys
- Simple to implement — no ring structure
- Limitation: O(N) lookup makes it impractical for large N (thousands of nodes)
Rendezvous hashing (Thaler and Ravishankar, 1996) actually predates the consistent hashing paper by a year. The idea: every key holds an "election" among the nodes, each node's score is a hash of the (key, node) pair, and the highest score wins. If a node leaves, only the keys it had won are re-elected, and each goes to its second-highest scorer, which is a different node for different keys. So a departing node's load spreads evenly over all survivors with no virtual nodes. Replica sets fall out naturally too: the top scorers are the replicas.
Weighted rendezvous. To give node a share proportional to weight , map the hash to a uniform value and use the score
This is the form described by Schindelhauer and Schomaker (2005). It gives each node exactly its weighted share, and changing one node's weight only moves keys to or from that node.
import { createHash } from "node:crypto";
function unitHash(s: string): number {
// 53 random bits mapped to (0, 1), never 0 or 1
const h = createHash("sha256").update(s).digest().readBigUInt64BE(0) >> 11n;
return (Number(h) + 0.5) / 2 ** 53;
}
export function weightedRendezvous(key: string, nodes: { id: string; weight: number }[], replicas = 1): string[] {
return nodes
.map((n) => ({ id: n.id, score: -n.weight / Math.log(unitHash(`${key}|${n.id}`)) }))
.sort((a, b) => b.score - a.score)
.slice(0, replicas)
.map((n) => n.id);
}
The cost is less of a problem than it sounds. Scoring 50 nodes is 50 hashes, a few microseconds, and for larger clusters there is a hierarchical ("skeleton") variant: arrange nodes in a tree of small groups and run rendezvous at each level, for cost. Rendezvous hashing is used, for example, by GitHub's GLB Director load balancer to build its forwarding tables, and by Apache Ignite as its default affinity function for assigning partitions to nodes.
Alternative: Bounded-Load Consistent Hashing
Google's 2017 paper addresses the remaining load imbalance in consistent hashing. It guarantees that no node receives more than times the average load.
Algorithm: When assigning a key, walk clockwise on the ring as usual, but skip any node that is already at . Continue to the next node.
This is used in Google's load balancers for backend server selection.
Correction
The two public deployments described with the paper are Google Cloud Pub/Sub, mentioned in Google's 2017 research blog post about the work, and Vimeo, whose engineer Andrew Rodland implemented the algorithm in HAProxy (the hash-balance-factor option) to spread video traffic across cache servers. "Google's load balancers" is not a claim we could confirm, so read the sentence above as "used in Google infrastructure such as Cloud Pub/Sub". The paper is Mirrokni, Thorup and Zadimoghaddam, first posted in 2016 and published at SODA 2018.
Why it is needed even with virtual nodes. Virtual nodes balance key counts in expectation, but traffic is not spread by key count. When the items being placed are requests or active sessions, a node can be overloaded by a lucky run of popular keys, and the vnode table above shows the most loaded of 100 nodes still carries 16% more than average at . Bounded loads gives a hard cap instead of a statistical one.
How the cap works in practice. Pick , for example 1.25. Each node may hold at most items. A lookup walks clockwise from the key's position and takes the first node with spare room. Most keys land on their normal owner. Only keys whose owner is full overflow to the next node on the ring.
// Bounded-load lookup on top of the ring above. `load` tracks live assignments
// (connections, sessions, in-flight requests), not stored keys.
function pickBounded(ring: { hashes: number[]; owner: Map<number, string> },
keyHash: number, load: Map<string, number>, c = 1.25): string {
const total = [...load.values()].reduce((a, b) => a + b, 0) + 1; // +1 for this one
const cap = Math.ceil((c * total) / load.size);
let i = lowerBound(ring.hashes, keyHash);
for (let step = 0; step < ring.hashes.length; step++, i++) {
const node = ring.owner.get(ring.hashes[i % ring.hashes.length])!;
if ((load.get(node) ?? 0) < cap) {
load.set(node, (load.get(node) ?? 0) + 1);
return node;
}
}
throw new Error("unreachable: total capacity exceeds load when c > 1");
}
function lowerBound(a: number[], x: number): number {
let lo = 0, hi = a.length;
while (lo < hi) { const m = (lo + hi) >>> 1; if (a[m] < x) lo = m + 1; else hi = m; }
return lo;
}
The trade-off is set by . Close to 1 gives tight balance but more keys overflow past their natural owner, which hurts cache locality and causes more reassignments when load changes. Larger values keep more keys at home. HAProxy expresses the factor as a percentage (hash-balance-factor 150 means ); something between 1.25 and 2 is a reasonable place to start tuning.
Alternative: Maglev Hashing
Google's Maglev network load balancer (Eisenbud et al., NSDI 2016) needed something different again: per-packet lookups at line rate, near-perfect balance across backends, and mostly stable assignments when backends change, so that existing TCP connections keep reaching the same backend. A ring lookup was too slow and too unbalanced, so Maglev precomputes a lookup table of size , a prime much larger than the number of backends. A lookup is then one hash and one array read: table[hash(5-tuple) % M].
Building the table. Each backend gets its own permutation of the table slots, from two hashes of its name:
Because is prime and , each permutation visits every slot exactly once. Backends then take turns: each claims the next slot in its own permutation that is still empty, round-robin, until the table is full. Every backend ends up with either or slots, so balance is essentially perfect.
import { createHash } from "node:crypto";
const h = (s: string, seed: string) =>
createHash("sha256").update(seed + s).digest().readUInt32BE(0);
export function maglevTable(backends: string[], M = 65537): number[] {
const N = backends.length;
const offset = backends.map((b) => h(b, "o") % M);
const skip = backends.map((b) => (h(b, "s") % (M - 1)) + 1);
const next = new Array(N).fill(0); // next index into each permutation
const table = new Array<number>(M).fill(-1);
let filled = 0;
while (true) {
for (let i = 0; i < N; i++) {
let slot = (offset[i] + next[i] * skip[i]) % M;
while (table[slot] >= 0) { // walk this backend's permutation
next[i]++;
slot = (offset[i] + next[i] * skip[i]) % M;
}
table[slot] = i;
next[i]++;
if (++filled === M) return table;
}
}
}
// lookup: backends[table[hash(flow) % M]]
The trade-off. Maglev deliberately gives up minimal disruption for balance and speed. When a backend is removed, its slots are refilled, and because the round-robin fill order changes slightly, a small number of slots owned by other backends also change hands. The paper reports that this extra churn is small when is large relative to (they recommend at least 100 times ), and Maglev additionally keeps a connection-tracking table so that established flows stick to their backend even if the table changes. Envoy's MAGLEV load-balancing policy uses this algorithm with a default table size of 65,537.
Worked example: with 100 backends and , each backend owns 655 or 656 slots, an imbalance of 0.15%. A ring with 100 points per backend would leave the busiest backend about 27% above average (from the simulation table earlier). The table takes 65,537 entries of 2 bytes each, about 128 KB, which fits in a CPU's L2 cache. Running the code above and then removing one of the 100 backends reassigns that backend's 1% of slots plus about 0.5% of slots that belonged to other backends: that 0.5% is the price of Maglev's balance.
Comparison Table
| Algorithm | Balance | Memory | Lookup Time | Node Add/Remove | Arbitrary Node IDs |
|---|---|---|---|---|---|
| Modulo hash | Perfect | O(1) | O(1) | Moves ~100% keys | Yes |
| Consistent hash (no vnodes) | O(log N) imbalance | O(N) | O(log N) | Moves ~1/N keys | Yes |
| Consistent hash (V vnodes) | ~1/√V imbalance | O(N·V) | O(log(N·V)) | Moves ~1/N keys | Yes |
| Jump consistent hash | Perfect | O(1) | O(ln N) | Moves ~1/N keys | No (0..N-1 only) |
| Rendezvous hashing | Perfect | O(N) | O(N) | Moves ~1/N keys | Yes |
| Bounded-load | (1+ε) of average | O(N·V) | O(log(N·V)) | Moves ~1/N keys | Yes |
| Maglev | Near perfect ( vs slots) | O(M) table | O(1) | Slightly more than 1/N | Yes |
| Fixed slots + table (Redis Cluster style) | Set by the table | O(S) slots | O(1) | Exactly the slots you choose to move | Yes |
The last row is worth a note because it is what many production systems actually use. Redis Cluster hashes every key with CRC16 into one of 16,384 fixed hash slots, and a cluster-wide table assigns slots to nodes. Rebalancing means moving chosen slots, one at a time, with the MIGRATING/IMPORTING protocol redirecting clients during the move. Riak's fixed number of ring partitions and Cassandra 4's allocated tokens follow the same idea: hash into a fixed space, then manage the assignment of that space explicitly, rather than letting node identities decide it at random. You keep consistent hashing's "only move what must move" property and gain control over exactly what moves and when.
Real-World Usage
| System | Algorithm | Virtual Nodes | Hash Function |
|---|---|---|---|
| Cassandra | Consistent hash ring | 256 (configurable) | Murmur3 |
| DynamoDB | Consistent hash ring | Undisclosed | MD5 |
| Riak | Consistent hash ring | 64 (default) | SHA-1 |
| Memcached (libketama) | Consistent hash ring | 100-200 per server | MD5 |
| Akka Cluster | Consistent hash ring | Configurable | Murmur3 |
| HAProxy | Consistent hash ring | Configurable | SDBM |
| Google Load Balancer | Bounded-load consistent hash | Internal | Internal |
| Vimeo | Jump consistent hash | N/A | Internal |
Corrections to this table
- DynamoDB is not the same system as the Dynamo described in the 2007 paper. The paper's Dynamo used an MD5-based ring with virtual nodes. The DynamoDB service hashes each item's partition key and stores items in partitions that each cover a range of the hashed key space. Partitions are split when they grow too large or too hot, and a metadata service tracks where each one lives (described in the 2022 USENIX ATC paper "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service"). Its hash function is not publicly documented.
- Cassandra's default is 256 tokens per node before 4.0 and 16 from 4.0 on.
- libketama places 160 points per server by default (40 MD5 digests, 4 points from each), scaled by server weight.
- Vimeo used bounded-load consistent hashing, which it implemented in HAProxy, not jump hashing.
- Google Load Balancer should read Google Cloud Pub/Sub for bounded loads. Google's network load balancer, Maglev, uses Maglev hashing (above).
What Dynamo, Cassandra and Discord-Style Systems Use
Dynamo (the 2007 paper). The paper is unusually candid about how its partitioning evolved, and it is a good lesson in why plain consistent hashing is not the end of the story. It describes three strategies:
- T random tokens per node, partition by token value. Classic consistent hashing with virtual nodes. Its problems: when a node joined, it had to "steal" key ranges from others, which meant scanning their local stores to find the keys to hand over, and the partition boundaries changed with every join, which made archiving and anti-entropy (Merkle trees per range) awkward.
- T random tokens per node, equal-sized partitions. The hash space is divided into Q fixed, equal partitions, and tokens only decide placement.
- Q/S tokens per node, equal-sized partitions. Each of S nodes holds Q/S of the fixed partitions. When a node joins or leaves, whole partitions are reassigned.
Strategy 3 had the best balance efficiency in their measurements, and it turns the problem into exactly the "fixed slots plus an assignment table" approach from the comparison table. Each key's preference list is the first N distinct physical nodes clockwise from its position, skipping virtual nodes of a host already chosen, which is what getNodes in the code above does.
Cassandra. A token ring built on the Murmur3 partitioner (64-bit tokens) since 1.2, virtual nodes via num_tokens, and replica placement by the replication strategy: NetworkTopologyStrategy walks the ring and picks replicas in distinct racks within each data centre, the same idea as getReplicaSet's zone diversity. Membership and token ownership spread by gossip, and ring changes are applied by streaming the affected ranges to their new owners.
Discord. Discord's 2017 engineering post on scaling Elixir to five million concurrent users describes routing each guild (server) to the Erlang node that runs its process with a consistent hash ring, and Discord open-sourced the Elixir ring library (ex_hash_ring). Using a ring means a node joining or leaving only relocates the guild processes in its arcs. Discord's message storage, Cassandra and later ScyllaDB, is itself a token ring, with messages partitioned by (channel_id, bucket), where the bucket is a fixed time window. That composite key exists to stop one busy channel from growing a single partition without bound, a reminder that the partition key matters as much as the hashing scheme.
Load balancers and proxies. Envoy offers both RING_HASH (a ketama-style ring, with a default minimum ring size of 1,024 entries) and MAGLEV. Both are used for session affinity and cache locality: send the same user, or the same cache key, to the same backend.
| Need | What production systems do |
|---|---|
| Data placement with replication | Token ring (vnodes or allocated tokens), replicas on distinct racks or zones |
| Explicit, controllable rebalancing | Fixed slots or partitions plus an assignment table |
| Request routing for cache affinity | Ring hash or Maglev in the proxy |
| Strict balance of live load | Bounded-load consistent hashing |
| Numbered shards that only grow | Jump hash, usually to logical shards |
War Story (illustrative)
The Memcached Thundering Herd (2008)
Correction: this story was previously presented as a documented incident. We could not find a public source for it. Facebook's NSDI 2013 paper "Scaling Memcache at Facebook" confirms that its web servers locate keys with consistent hashing, but does not describe this incident or the switch. Treat what follows as an illustration of a failure that many teams did experience with modulo hashing.
In the early days of Facebook, their Memcached fleet used modular hashing (hash(key) % N). When a Memcached server crashed and was replaced, N changed, causing nearly all cached keys to map to different servers. This triggered a cache stampede where millions of requests hit the backend database simultaneously, causing a cascading failure.
After this incident, Facebook adopted consistent hashing via the libketama library (originally from Last.fm). With consistent hashing, losing one server only invalidated the ~ of keys that mapped to that server. This single change eliminated an entire class of outages.
The lesson: in any caching tier with more than a few nodes, consistent hashing is not optional — it's a correctness requirement.
War Story
DynamoDB's Partition Rebalancing
Amazon's original Dynamo paper (2007) used consistent hashing with virtual nodes for partition assignment. But they discovered that with heterogeneous hardware and varying data sizes, virtual nodes alone weren't enough. Some partitions grew much larger than others due to hot keys or uneven data distribution.
In later versions, DynamoDB moved to a model where partition assignment is still based on consistent hashing, but the system can split hot partitions and redistribute them. The consistent hashing provides the base assignment, but an orchestration layer on top handles dynamic rebalancing.
The lesson: consistent hashing provides a good starting point for data distribution, but production systems often need an additional rebalancing mechanism on top.
Accuracy note: the documented part of this story is in the Dynamo paper itself, which describes moving from random tokens to fixed, equal-sized partitions (strategies 1 to 3 above) because of load balance, bootstrapping cost and archival complexity. The DynamoDB service's split-based partitioning is described in its own 2022 paper. Hot-partition handling in DynamoDB is real, but the motivation given in the first paragraph above is a simplification.
Edge Cases and Failure Modes
Hot Keys
Consistent hashing distributes keys uniformly, but it cannot protect against hot keys — a single key that receives disproportionate traffic. If user:beyonce gets 1000x more reads than average, the node responsible for that key becomes a hotspot regardless of how well the ring is balanced.
Mitigations:
- Key splitting: Append a random suffix (
user:beyonce:0throughuser:beyonce:9) and read from a random replica - Client-side caching: Cache hot keys in the application layer
- Read replicas: Route reads for hot keys to replicas, not just the primary
Ring Membership Changes During Requests
When a node is being added or removed, there's a window where different clients may have different views of the ring. Client A might think key X maps to Node 2, while Client B (with an updated ring) thinks key X maps to Node 5.
Mitigations:
- Two-phase migration: First copy data to the new owner, then update the ring. Reads during migration check both old and new owners.
- Versioned ring: Clients include the ring version in requests. Nodes redirect if the version is stale.
Hash Collisions
With 32-bit hashes and thousands of virtual nodes, hash collisions become non-negligible. Two virtual nodes mapping to the same hash position means one of them gets zero arc length (zero keys).
Mitigation: Use a collision-resistant hash (SHA-256) and a large hash space (128-bit or 256-bit). With positions and 10,000 virtual nodes, the collision probability is negligible ().
The birthday bound makes the sizing concrete: with points in a space of size , the chance of any collision is about . For 10,000 points in a 32-bit space that is about 1.2%, in a 64-bit space about . A fast 64-bit hash such as Murmur3 or xxHash is therefore enough. Cryptographic strength matters only if an adversary can choose keys to pile onto one node, and then a keyed hash is the better answer. Whatever you choose, handle a collision deterministically (for example, break ties by node id) so that every client builds the same ring.
Clients with Different Views of the Ring
Every client must compute the same ring, or two clients will send the same key to different nodes. That requires identical node lists, identical vnode naming ("host:port#i" versus "host#i" changes everything), the same hash function, the same byte order, and the same tie-breaking. Mixed-language fleets break this surprisingly often. libketama-compatible clients exist in most languages precisely so that a PHP front end and a Java back end agree on placement. Write a cross-language test that hashes a fixed list of keys and compares owners.
Cascading Overload on Failure
Without virtual nodes, a failed node's whole range goes to its successor, which now has about double the load and is the most likely next failure, which passes a triple load to its successor. With virtual nodes the failed node's arcs are spread across many nodes, and with bounded loads no survivor can be pushed beyond its cap. For caches, also consider whether a failed node's keys should be remapped at all: some memcached setups mark a failed server as temporarily down and fail the reads, rather than remapping and warming a different node, because a server that is only briefly unreachable would otherwise cause two rounds of misses.
Decision Framework
graph TD
A[Need to distribute data<br/>across N nodes?] --> B{Can nodes be<br/>numbered 0..N-1?}
B -->|Yes, and only<br/>add/remove at end| C[Jump Consistent Hash]
B -->|No, need arbitrary<br/>node IDs| D{How many nodes?}
D -->|< 100| E{Need simplicity?}
D -->|100+| F[Consistent Hash Ring<br/>with virtual nodes]
E -->|Yes| G[Rendezvous Hashing]
E -->|No| F
F --> H{Need strict<br/>load balance?}
H -->|Yes| I[Bounded-Load<br/>Consistent Hashing]
H -->|No| J[Standard virtual<br/>nodes V=150]
style C fill:#51cf66,color:#fff
style F fill:#51cf66,color:#fff
style G fill:#51cf66,color:#fff
style I fill:#ffd43b,color:#000
Interview Questions
1. Why does hash(key) mod N fail when N changes, and how much does consistent hashing improve it?
Changing N changes the result for almost every key: going from N to N+1 moves about of them. Consistent hashing moves about , the minimum possible, because only keys in the new node's arcs change owner.
2. Why do we need virtual nodes, and how many?
With one point per node, arc sizes are roughly exponential, so loads vary by about ±100% and the biggest node gets about times the average. With V points per node the relative standard deviation is about : 10% at 100, 6% at 256. Virtual nodes also spread a failed node's load over many survivors. But many random tokens raise replica overlap and repair fan-out, which is why Cassandra 4.0 uses 16 allocated tokens.
3. Compare rendezvous hashing and a ring.
Rendezvous scores every node per key and picks the highest. It needs no vnodes, balances well, spreads a departing node's keys over all survivors, and gives replica sets as the top r scorers. It costs O(N) per lookup, against O(log NV) for a ring. It is ideal for tens to hundreds of nodes.
4. When would you use jump consistent hash?
When shards are numbered 0 to N-1 and only grow or shrink at the end: it has no memory overhead, perfect balance and minimal movement. For arbitrary server identities, map keys to logical shards with jump hash and map logical shards to servers with a table.
5. What problem does bounded-load consistent hashing solve?
Even with vnodes, the busiest node carries noticeably more than average, and popular keys make it worse. Bounded loads cap every node at times the average live load, overflowing keys clockwise to the next node with room. Used for Cloud Pub/Sub and, through HAProxy, at Vimeo.
6. How does Maglev build its table and what does it trade away?
Each backend gets a permutation of a prime-sized table from an offset and a skip derived from its name, and backends claim slots round-robin until the table is full, so each has or slots. Lookups are one array read. It trades a little extra churn on backend changes for near-perfect balance, and relies on connection tracking to keep existing flows stable.
7. How does Dynamo choose replicas for a key?
It walks clockwise from the key's position and takes the first N distinct physical nodes, skipping additional virtual nodes of hosts already chosen. Production systems also require the replicas to be in different racks or zones.
8. A node in a ring-based cache cluster dies and the next node falls over a minute later. Why, and what would you change?
Without virtual nodes, the dead node's entire range moves to its successor, doubling that node's load and its miss rate. Use virtual nodes or bounded loads so the load spreads, warm caches gradually, and consider failing reads for briefly unreachable nodes instead of remapping immediately.
9. Why does Redis Cluster use 16,384 fixed slots instead of a ring?
Fixed slots separate hashing from placement: keys always hash to the same slot, and a table assigns slots to nodes. Rebalancing moves chosen slots explicitly, with client redirection during migration, which gives operators precise control over what moves and when.
Further Reading
- Thaler & Ravishankar: "Using Name-Based Mappings to Increase Hit Rates" (rendezvous hashing, 1998 journal version)
- Eisenbud et al.: "Maglev: A Fast and Reliable Software Network Load Balancer" (NSDI 2016)
- Quorums and Leaderless Replication — How Dynamo-style systems read and write the replicas that the ring chooses
- Gossip Protocols — How ring membership spreads
- Karger et al.: "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" (1997)
- Lamping & Veach: "A Fast, Minimal Memory, Consistent Hash Algorithm" (Jump Consistent Hash, 2014)
- Mirrokni et al.: "Consistent Hashing with Bounded Loads" (Google, 2017)
- DeCandia et al.: "Dynamo: Amazon's Highly Available Key-value Store" (2007)
- Next: Byzantine Fault Tolerance — when nodes can lie