Consistent Hashing
Place nodes and keys on the same hash ring and assign each key to the first node clockwise; adding or removing a node then moves only about K/N keys instead of almost all of them, virtual nodes even out the load, and the lookup is a binary search on a sorted array — this is the DSA hash table becoming a production partitioning scheme.
Any scheme that maps keys to nodes with hash(key) mod N remaps almost every key when N changes, so adding one cache node empties the whole cache and adding one shard moves nearly all the data; the ring makes membership change proportional to the change, not to the fleet.
The problem with hash mod N
The Hash Table you learned maps a key to a bucket with hash(key) mod capacity, and when the table grows it rehashes everything — acceptable in memory, where a rehash is a few milliseconds. A distributed cache is the same structure with nodes as buckets, and the rehash is now a disaster. With 4 cache nodes and hash(key) mod 4, adding a fifth node changes the target for every key whose hash is not congruent under both moduli — about 80% of them. Every one of those keys is now a miss, and 80% of your read traffic arrives at the database at once, which is the cache stampede from Caching Architecture at fleet scale. Removing a failed node has the same effect. A cache that empties itself whenever the fleet changes cannot be scaled, and cannot survive an instance dying.
The requirement is therefore precise: when one of N nodes is added or removed, only the keys that *must* move — about K / N of the K keys — should move, and every other key should stay where it is. That is what "consistent" means in the name: the mapping is consistent across membership changes.
The ring, and the binary search on it
Hash both nodes and keys into the same space — say 32-bit integers — and picture that space as a circle where the largest value wraps to 0. Each node sits at hash(nodeId). A key belongs to the first node clockwise from hash(key). When node E joins between B and C, only the keys in the arc between B and E — which previously belonged to C — move to E; everything else is untouched. When C leaves, its arc is absorbed by the next node clockwise, D, and nothing else moves. Membership change is local to one arc.
The lookup is a sorted array of node positions and a Binary Search for the first position ≥ hash(key), wrapping to index 0 past the end: O(log N) per key against a table of a few thousand entries, which is why every implementation from Memcached’s ketama to Cassandra’s token map is essentially this code.
1export class HashRing {2 private points: { pos: number; node: string }[] = []3 constructor(private readonly hash: (s: string) => number, private readonly vnodes = 150) {}4 5 add(node: string) {6 for (let i = 0; i < this.vnodes; i++) this.points.push({ pos: this.hash(node + '#' + i), node })7 this.points.sort((a, b) => a.pos - b.pos)8 }9 remove(node: string) { this.points = this.points.filter((p) => p.node !== node) }10 11 lookup(key: string): string {12 const h = this.hash(key)13 let lo = 0, hi = this.points.length // first index with pos >= h14 while (lo < hi) {15 const mid = (lo + hi) >>> 116 if (this.points[mid].pos < h) lo = mid + 1; else hi = mid17 }18 return this.points[lo % this.points.length].node // wrap past the end to the start19 }20}Virtual nodes, hot spots, and replication along the ring
With one position per node, four random points on a circle divide it very unevenly — one node can easily own 45% of the keyspace while another owns 8%, which is the challenge hot-node-on-the-ring: the fleet is "balanced" by node count and one node is at 100% CPU. And when a node leaves, its *entire* arc lands on one neighbour, doubling that neighbour’s load exactly when the cluster is already short a node. Virtual nodes fix both: give each physical node 100–200 positions (hash(node + "#" + i)). The arcs are now many and small, the standard deviation of load per node drops to a few percent, a leaving node’s keys are spread across *all* the others, and a heterogeneous fleet is handled by giving a bigger machine more vnodes. The cost is a larger sorted array — 200 vnodes × 100 nodes = 20,000 points, still trivial to binary-search — and a slightly slower membership change.
Virtual nodes do not fix a hot key: if user:celebrity receives 30% of all reads, whichever node owns it is hot regardless of arc size. That needs a different tool — a local cache in front of the ring, or splitting the key (user:celebrity:0..9) across nodes. Replication follows the same walk: a key is stored on its owner and on the next R − 1 *distinct physical* nodes clockwise (skipping vnodes of the same machine), so that losing one node leaves the replicas one hop away. This is precisely how Dynamo-style stores and Cassandra place replicas; see Partitioning and Sharding for the database-side view of the same layout.
ring position 0 90 140 170 360
|--------|--------|-------|-----------------|
node A B C D
arc owned A: 25% B: 14% C: 8% D: 53% ◄── D is the hot node
with 150 vnodes each: every node owns 25% ± ~2%Where it shows up
Distributed caches: Memcached clients (ketama) and Redis Cluster’s client libraries place keys on a ring so that adding a cache node causes a 1/N miss burst instead of a total flush. Partitioned databases: DynamoDB and Cassandra partition by token ranges on a ring, which makes adding a node a matter of streaming one arc of data rather than reshuffling the table; Riak and Voldemort did the same. Load balancer affinity: Envoy’s ring-hash and Maglev balancers route requests with the same key (a session id, a tenant, a chat room) to the same backend, so per-backend caches and open connections stay useful across scale events; see Load Balancing and Stateless vs Stateful Services. Connection routing: a chat system with millions of WebSocket connections across hundreds of connection servers uses the ring to decide which server owns a user, so a message for user:42 is routed to exactly one server without a global lookup table — the exercise design-chat-app builds this.
The idea is the same in all four: this is the DSA hash table becoming a production partitioning scheme. The bucket array became a fleet, the rehash became a data migration, and the ring is what makes the migration proportional to the change instead of to the dataset.
| Scheme | Keys moved when 1 of N nodes changes | Load balance | Lookup | State per client |
|---|---|---|---|---|
hash mod N | About (N − 1)/N — nearly all | Even | O(1) | N |
| Ring, one point per node | About K/N, but all to one neighbour | Poor: arcs vary widely | O(log N) | N positions |
| Ring with V vnodes per node | About K/N, spread across all nodes | Good: ±2% at V ≈ 150 | O(log(N·V)) | N·V positions |
| Lookup table / directory | Exactly the chosen ranges | Whatever the operator sets | O(1) after a fetch | The table, plus a coordinator to keep it current |
Key points
hash mod Nremaps nearly every key when N changes; a ring with keys assigned to the first node clockwise remaps only about K/N.- Lookup is a binary search on a sorted array of node positions, wrapping to index 0 — O(log N) with a few thousand entries.
- Virtual nodes (100–200 per physical node) even out the arcs, spread a departing node’s keys across the fleet, and let bigger machines take more; they do not fix a hot key.
- Replicas are the next R − 1 distinct physical nodes clockwise; this is how Dynamo-style stores and Cassandra place data.
- Same mechanism for caches, partitioned databases, load-balancer affinity and connection routing: the DSA hash table becoming a production partitioning scheme.
The consistent hashing ring
How data moves through it
One request or event, hop by hop.
- 1Client → Ring:
hash(key)computed locally; binary search over the node positions returns the owning node (and R − 1 successors for replication). - 2Client → Node C:
GET user:42sent directly to the owner; no proxy, no directory lookup. - 3Node E joins → Membership: E’s vnode positions are inserted; clients learn of E via gossip or the registry.
- 4Node C → Node E: the keys in E’s new arcs are streamed (data stores) or simply missed and refilled from the source (caches).
- 5Node C fails → Successor D: reads for C’s arc go to the next replica clockwise until C is replaced.
When to use — and when not
- Distributed caches where a membership change must not empty the cache.
- Partitioned data stores that must add capacity by streaming one range rather than reshuffling everything.
- Routing that needs affinity to a specific backend — sessions, tenants, chat rooms, WebSocket connections — without a central directory.
- A fixed, small fleet that never changes:
hash mod Nis simpler and perfectly balanced. - When you need explicit control over placement (regulatory data residency, moving one hot tenant by hand): a directory or range-based scheme with a coordinator fits better.
- Workloads dominated by a few hot keys: the ring balances the keyspace, not the traffic; fix the keys first.
Tradeoffs
A small algorithm with an outsized payoff; the operational subtleties are vnode count, agreeing on membership across clients, and remembering that it balances keys, not load.
How it fails
- No virtual nodes: arcs are wildly uneven and one node owns 45% of the keyspace — the
hot-node-on-the-ringchallenge. - Clients disagree on membership (one has seen the new node, another has not): the same key is written to two nodes and reads are inconsistent until the view converges.
- Hot key: a single celebrity key saturates its owner no matter how even the arcs are.
- Node leaves without replication: its arc’s data is simply gone; caches tolerate this, data stores must replicate along the ring.
- Hash function with poor distribution (or hashing only a low-entropy prefix): keys cluster on one arc regardless of vnodes.
How it scales
- Adding a node moves about 1/N of the keys; the miss burst or data stream is proportional to one node’s share, so scaling from 100 to 101 nodes is a 1% event.
- The sorted array grows with N × V; at 1,000 nodes × 200 vnodes it is 200,000 entries, still microseconds to search and megabytes to hold.
- Membership must be distributed to every client — via gossip (Cassandra), a coordinator (ZooKeeper/etcd), or a registry as in Service Discovery — and the propagation delay is the window of inconsistency.
How it interacts with databases, queues, caches, APIs and external systems
- Caches: Memcached ketama and Redis Cluster client routing place keys on the ring so a node change is a 1/N miss burst; see Caching Architecture.
- Databases: DynamoDB, Cassandra and Riak partition token ranges on a ring and replicate to successors; see Partitioning and Sharding.
- Load balancers: ring-hash and Maglev balancing give request affinity (session, tenant) that survives backend changes; see Load Balancing.
- Message brokers: Kafka’s partitioner uses
hash(key) mod partitions, which is why changing the partition count reshuffles keys — the problem the ring avoids; see Kafka-Style Logs: Topics, Partitions, Offsets. - Service registry: the ring’s membership comes from somewhere; a registry with health checks is the usual source; see Service Discovery.