What this module covers: Why hash(key) % N makes adding a single cache node an outage-grade event, and what the ring construction replaces it with. We cover the ring itself and the ~K/N movement guarantee, virtual nodes and the two genuinely separate problems they solve, bounded-load variants for a hot key, how Redis Cluster's 16,384 explicit hash slots differ from a pure ring and what happens to clients mid-resharding, how Cassandra's token ranges and vnodes compare, and why a rebalance is really a partial cache flush wearing a topology-change costume. It ends with the honest limit: this technique places keys and does nothing else.
Adding One Cache Node Should Not Be an Incident
The pager reason looks like this. Eleven o'clock on a busy evening, someone adds a node to the memcached tier because the working set has outgrown ten machines. Within thirty seconds the database's CPU is pinned, p99 has gone from 40 ms to eight seconds, and the application is timing out on endpoints that have nothing to do with the feature being launched. Nobody deployed code. Nobody changed a query. Somebody added capacity.
The mechanism is one line of client code that nearly every cache client shipped by default at some point:
ts
Ask what happens to a key when nodes.length goes from 10 to 11. The key keeps its home only if hash(key) % 10 === hash(key) % 11, and for a well-distributed hash the probability of that is roughly 1/11. Which means about 91% of keys now resolve to a node that has never seen them. Not evicted — the data is still sitting in RAM on the old node — just unreachable, because every client is now asking the wrong machine.
That is a near-total cache flush, delivered instantaneously, at peak. Module F-12 already made the point that caching a slow query converts a performance problem into an availability problem; this is the moment the bill arrives. The database is now serving the entire read workload cold, and it was provisioned to serve a small percentage of it.
Generalise the arithmetic, because it is the whole motivation for this module:
Change
Keys that keep their node
Keys that move
N = 4 → 5
~1/5 (20%)
~80%
N = 10 → 11
~1/11 (9%)
~91%
N = 100 → 101
~1/101 (1%)
~99%
The property is perverse: the bigger your cluster, the worse a single-node change hurts. Growth makes the operation more dangerous, exactly when you need to do it more often. And it is not only planned additions — a node crashing, a node being restarted for a kernel patch, an autoscaler removing one instance, all of these change N.
What we want instead is a mapping where changing N moves only the keys that have to move: roughly K/N of them, the new node's fair share. That is what consistent hashing provides.
The Ring: Hash Nodes and Keys Into the Same Space
The trick is to stop treating node identity as an index into an array, and start treating it as a value in the same space as the keys.
Pick a hash function with a fixed output range — say 32 or 64 bits. Treat that range as a circle: the largest value wraps around to zero.
Hash each node's identifier ("cache-03:11211") into that circle. Each node is now a point on the ring.
Hash each key into the same circle.
A key belongs to the first node encountered walking clockwise from the key's position.
That is the entire construction. What makes it work is that node positions and key positions are computed independently — a key's position never changes, and a node's position never changes, so the only thing that can reassign a key is a node appearing or disappearing near it.
Analogy: it is a circular corridor of hotel rooms with no numbers, only doorways at fixed positions. Every guest is dropped at a random spot in the corridor and told to walk clockwise until they reach a door. Open a new door halfway along an empty stretch, and the only guests who change rooms are the ones standing in that stretch — everyone else still walks to the same door they always did. Modulo hashing, by contrast, renumbers every room in the building the moment you add one.
Concretely: add node X to a ring of N nodes. X lands somewhere on the circle and takes over the arc between itself and the node counter-clockwise of it. The keys in that arc used to belong to X's clockwise successor. Only that one successor gives up keys, and only about K/(N+1) of them. Every other node is untouched. Remove a node, and only its clockwise successor gains keys.
That "only one neighbour is affected" property is simultaneously the ring's headline feature and, as we will see, its most important defect.
Here is the minimal version, which is worth being able to write from memory:
ts
Lookup is O(log(N × replicas)) — a binary search over a few thousand sorted integers, which is nanoseconds and entirely irrelevant to your latency budget. The cost that does matter is memory and rebuild time: 200 nodes × 160 points is 32,000 entries to sort whenever membership changes, which is fine, and is why nobody rebuilds the ring on the hot path.
Virtual Nodes Fix Two Problems That Have Nothing to Do With Each Other
The naive ring — one point per node — is unusable in practice, and it fails for two reasons that people routinely conflate.
Problem one: with few nodes, the arcs are wildly uneven. Hashing five node names into a circle does not produce five equal arcs. It produces five arcs whose lengths are, statistically, close to exponentially distributed: the longest is typically several times the shortest, and with five nodes it is unremarkable for one node to own 35–40% of the keyspace while another owns 5%. Since ownership share is load share, one machine is at 90% utilisation and paging while another is idle. Module F-4's utilisation curve is unforgiving about that asymmetry — the hot node's queueing delay explodes long before the cluster's average utilisation looks alarming.
Worse, the imbalance is arbitrary and sticky. It is a property of the hash of your hostnames. Renaming a node reshuffles it. You cannot reason about it, only measure it.
Problem two: a failed node dumps its entire load on exactly one survivor. This is the direct consequence of the ring's headline property. Node C dies; every one of C's keys now walks clockwise to D. D's load doubles instantly. If D was running at 60% before, it is now saturated, and if D falls over, its combined load lands on E. That is a cascading failure with a clean mechanism, triggered by a single hardware fault.
Virtual nodes solve both. Instead of hashing each node once, hash it V times with distinct suffixes (cache-03#0 … cache-03#159) and give every resulting point the same owner. The ring now has N × V points, and:
Distribution smooths out. Load imbalance falls roughly as 1/√(N × V). Going from 1 point per node to ~100–200 points per node takes typical worst-node overshoot from "several times the mean" down to single-digit percentages. The libketama scheme that memcached clients standardised on uses 160 points per server for precisely this reason.
Failure spreads. A dead node's 160 arcs each hand off to whichever node happens to sit clockwise of that arc — which, with enough points, is nearly all the other nodes in roughly equal measure. A node death now raises everyone's load by 1/(N−1) instead of doubling one machine's. This is the more important of the two benefits and the one usually left out of the explanation.
Problem three, which virtual nodes solve almost by accident: heterogeneous capacity. Real clusters are not uniform. You have three older machines with 32 GB and five newer ones with 128 GB, or you are mid-migration between instance types. With one point per node the ring has no way to express "this machine should take four times the traffic." With virtual nodes it is trivial — give it four times the points.
ts
This is why you should think of virtual nodes as the mechanism and weighting as a first-class feature, not a hack.
The cost, named: virtual nodes multiply ring size, which multiplies the memory the ring occupies in every client and the time to rebuild it on membership change. More significantly, in a replicated store they make replica placement harder. If replication means "the next R distinct nodes clockwise," then with hundreds of vnodes per node the R nodes following a given arc are effectively random — which is good for spread and bad for correlated-failure risk, because random selection will happily place two replicas of the same range in the same rack or availability zone. Systems that care fix this with topology-aware placement (skip nodes in a rack you have already used), and that constraint fights the even-distribution goal. Cassandra's later token-allocation work exists specifically because purely random vnode placement produced uneven replica distribution.
Why this matters in production: the single most common consistent-hashing bug in a homegrown implementation is too few virtual nodes. The system works fine in staging with three nodes because you are not measuring per-node hit ratio, and in production one shard runs 3× hotter than the others forever. Instrument per-node key count and per-node hit ratio from day one; the ring's imbalance is invisible in aggregate metrics.
Bounded Loads: When the Problem Is One Key, Not the Arcs
Virtual nodes make the keyspace even. They do nothing about an uneven request distribution over that keyspace. If one key is requested 100,000 times a second — a celebrity's profile, the homepage feed, a product that just went on a television advert — then the node owning that key is hot no matter how beautifully balanced the ring is. This is the hot-key problem, and it is a different problem with different fixes.
Bounded-load consistent hashing is the ring-native answer. Compute the average load per node, multiply by a factor (1 + ε) to get a per-node cap, and change the lookup rule: walk clockwise, and if the node you land on is already at its cap, keep walking to the next one. Requests overflow to neighbours instead of queueing.
The properties are worth stating precisely, because the trade-off is sharp:
With ε small (say 0.25, meaning no node exceeds 125% of average), balance is tight and key-to-node mapping is no longer stable — the same key can go to different nodes depending on current load. For a cache, that means duplicated entries and a lower effective hit ratio, because the same value now occupies memory on two or three machines. For a stateful assignment (a WebSocket session, a stream partition) it can be outright wrong.
With ε large, you approach plain consistent hashing: stable mapping, hot node stays hot.
So the cost of bounded load is cache efficiency and mapping stability, bought in exchange for tail-latency protection. HAProxy exposes this as a hash-balance-factor on consistent-hash backends, and several service proxies offer an equivalent balance factor on their ring-hash and Maglev policies. It is genuinely useful when you are hashing requests to servers (where a small amount of duplicated work is cheap) and genuinely dangerous when you are hashing data to owners.
The alternatives, since bounded load is not always the right tool:
Approach
What it does
What it costs
Bounded load (1+ε cap)
Overflows a saturated node's requests to neighbours
Unstable mapping; the same key cached in several places
Hot-key replication (salting)
Store the key as feed:home#0…#R, pick a suffix at random per read
R× memory for that key; writes must fan out to R copies
Local (in-process) cache in front
Hottest keys never leave the app process
Per-instance staleness with no coordinated invalidation (Module P-13)
Promote to the edge
Cache the hot object in the CDN with request collapsing (Module F-15)
Only works for shareable, non-personalised responses
In practice the hottest handful of keys are best handled above the ring, with a small local cache, and the ring is left to do the boring job of placing the other 40 million. Rate limiting (Module P-18) has the same shape of problem and reaches the same conclusion.
Redis Cluster Is Not a Ring — It Is 16,384 Explicitly Assigned Slots
This is the detail that catches people out in interviews and, more expensively, during their first resharding.
Redis Cluster does not hash keys onto a continuous circle. It defines exactly 16,384 hash slots. A key's slot is CRC16(key) mod 16384, and each slot is explicitly assigned to a specific master node. The mapping from slot to node is a piece of cluster state, gossiped over the cluster bus and cached by every client.
The indirection matters. A ring computes ownership; a slot table stores it. The consequences:
Ownership is an administrative decision, not a hash outcome. You can move slot 9,412 from node A to node B because A is hot, without touching any other slot. On a pure ring you cannot move an individual key — you can only move node positions, which drags whole arcs along.
Rebalancing is a finite, enumerable list of work. "Move 3,276 slots from these four nodes to the new one" is a plan with progress you can watch, pause, and resume.
16,384 slots means the granularity is fixed. Slots, not keys, are the unit of movement — you cannot split a slot, so a single catastrophically hot key is stuck on one node. The number itself is a deliberate trade-off: each cluster-bus gossip message carries a slot bitmap, and 16,384 bits is 2 KB per heartbeat, which is affordable to send between every pair of nodes frequently. A larger slot count would buy finer granularity at the cost of fatter gossip.
Multi-key operations must land in one slot.MGET a b c fails with a CROSSSLOT error unless all three keys hash to the same slot. That is what hash tags are for: if a key contains {...}, only the substring inside the braces is hashed. user:{4242}:profile and user:{4242}:sessions are guaranteed to share a slot and therefore a node, which is how you co-locate related data deliberately. This is the same modelling discipline as choosing a partition key (Module P-6) — and it is equally hard to reverse later.
What resharding actually does to your clients. Moving a slot is a live migration, and the protocol is explicit about the in-between state:
text
During that window, a client asking the source node for a key in the migrating slot gets one of two answers, and the difference between them is the thing to understand:
MOVED <slot> <host:port> — "this slot is not mine, permanently." The client must update its cached slot map and retry. A client that treats MOVED as a one-off redirect without updating its map will take an extra network round trip on every subsequent request to that slot, which shows up as a mysterious latency regression that never resolves.
ASK <slot> <host:port> — "this specific key has already been moved, but the slot is still mine." The client retries this one command against the destination, prefixed with ASKING, and does not update its map. Treating ASK like MOVED corrupts the client's routing table mid-migration.
Any competent client library handles both. The reason to know it anyway is that the failure signature of a client library that handles them badly — intermittent errors and doubled latency confined to a resharding window — is otherwise inscrutable.
Cassandra Does Use a Ring, and Names Its Parts Differently
Cassandra is the reference implementation of the ring in a database, and the vocabulary maps cleanly:
Concept
Ring / Cassandra
Redis Cluster
Hash space
64-bit token range, −2⁶³ to 2⁶³−1, via Murmur3
16,384 slots, via CRC16 mod 16384
Unit of ownership
A token range (an arc), computed
A slot, explicitly assigned
Virtual nodes
num_tokens per node — historically 256, recent versions default to a much smaller value paired with a token-allocation algorithm
Not applicable; slots are the granularity
Weighting a bigger node
Give it more tokens
Give it more slots
Adding a node
New tokens are chosen, ranges stream from current owners
Slots are migrated explicitly by the operator or a rebalance tool
Co-locating related rows
Same partition key → same token
Hash tag {...} → same slot
Who knows the map
Gossip; clients are token-aware and route directly
Gossip; clients cache the slot map, corrected by MOVED
The interesting difference is who decides. Cassandra computes placement from tokens, which means adding a node is a mostly-automatic operation and you have little control over which ranges land where. Redis Cluster stores placement, which means adding a node is a deliberate operation and you have complete control. Neither is better; they are the classic computed-versus-stored trade-off. Computed needs no coordination and gives no control. Stored gives control and needs the map to be agreed, propagated, and kept consistent — which is a small distributed-consensus problem in its own right (Module A-1).
Managed stores hide this entirely. DynamoDB partitions by the hash of the partition key and splits partitions as they grow past size or throughput thresholds, which is a stored map with automatic administration. You get the operational simplicity and lose the ability to reason about which physical partition anything lives on — which is why a hot partition key in DynamoDB is diagnosed from throttling metrics rather than from a topology you can inspect.
Every Rebalance Is a Partial Cache Flush
Here is the part that gets forgotten, and it is the reason this module sits next to the caching modules rather than in a chapter about hash functions.
Consistent hashing does not stop keys from moving. It reduces the fraction that move from ~100% to ~1/N. And for a cache, every key that moves is a guaranteed miss, because the new owner has never held it. So:
Adding one node to a 10-node cache tier is a deliberate, instantaneous 10% cache flush.
Ten percent sounds harmless. Run the arithmetic instead. Suppose the tier serves 50,000 reads/second at a 97% hit ratio, so the database sees 1,500 reads/second and was sized for roughly that. Move 10% of the keyspace and, for the duration of the refill, those requests miss: an extra ~5,000 reads/second arriving at a database provisioned for 1,500. Module F-12's point that hit ratio's marginal value increases near the top is the same observation from the other direction — small movements in hit ratio are enormous movements in origin load.
And it does not arrive as a smooth 10% increase. It arrives as a stampede, because the hottest keys are requested most often and therefore miss first, concurrently, many times over. A thousand in-flight requests for the same just-moved key all miss, all query the database, and all write the same value back. This is exactly Module F-12's cold-cache problem, except it was not triggered by a deploy or a restart — it was triggered by scaling up, which is the action you take when you are already under pressure. That is the trap: the remedy for load is itself a load spike.
What actually works:
Single-flight / request collapsing per key. One concurrent miss for a given key does the work, the rest wait for its result. This is the highest-leverage mitigation by a wide margin, and it is the same mechanism as the CDN origin shield in Module F-15.
Add nodes gradually. With virtual nodes you have a dial: introduce the new node with 10 points, then 40, then 160, over minutes. Each step moves a small slice of the keyspace, and the refill is spread out rather than simultaneous.
Warm before rotating in. Copy or replay traffic into the new node before clients start routing to it. Expensive to build, and the only approach that makes the transition genuinely invisible.
Fall back to the previous owner during a grace window. On a miss, ask the node that used to own the key (computable — remove the new node from a shadow copy of the ring and look up again), and promote what you find. Correct only for immutable or TTL-tolerant values, and it doubles the miss path's latency, but it converts a database stampede into an intra-cache copy.
Jittered TTLs, so the refilled keys do not all expire together and reproduce the stampede an hour later (Module F-12).
Rebalance at the traffic trough. Unglamorous, effective, and frequently unavailable when the reason you are adding a node is that you are out of capacity right now.
Why this matters in production: treat "add a cache node" as a change with a blast radius, not as routine capacity work. It belongs in a change window, with the origin's headroom checked first and a rollback plan — because removing the node again moves the same keys back and causes a second flush. The safest posture is to over-provision the cache tier so that you rarely need to resize it under duress.
What Consistent Hashing Does Not Do
The honest limits, because the technique is routinely credited with things it has no opinion about.
It answers "which node?" and nothing else. It is a deterministic, low-churn function from key to node. That is the entire contribution. Specifically:
It is not replication. The ring says where a key's primary lives. Storing R copies requires a replica placement rule on top — commonly "the next R distinct physical nodes clockwise" — plus rules to avoid placing replicas in the same rack or availability zone, plus a mechanism to repair a replica that fell behind. Module P-5 covers replication properly; the ring is only the input to it.
It is not consistency. If two clients hold different views of ring membership — one has seen the new node, one has not — they will write the same key to different nodes and neither is wrong. For a cache that is a wasted slot. For a store it is divergent data. The ring assumes agreement on membership and provides none; agreement is gossip plus failure detection plus, when correctness demands it, consensus (Module A-1). Which consistency guarantee you actually get from the resulting system is Module P-11's subject.
It is not a fix for a bad partition key. If your access pattern is "read all of one tenant's data," hashing individual keys scatters that tenant across every node and every read becomes a scatter-gather. Placement cannot repair a modelling error (Module P-6, and Module F-14's warning that the partition key is the hardest decision to reverse).
It does not eliminate hot spots, only structural ones. Uneven request distribution is untouched by even key distribution.
It is not always the right tool. Rendezvous hashing (highest-random-weight) gives you the same minimal-disruption property with weighting built in and no ring to maintain, at O(N) per lookup — often the better choice for small N. Maglev-style lookup tables give near-perfect balance with slightly more disruption on membership change, and constant-time lookup. And an explicit slot map, as Redis Cluster demonstrates, is worth its coordination cost whenever you want operational control over placement.
Pick the ring when membership changes often, coordination is expensive, and you need clients to agree without asking anyone. Pick a stored map when you need to move an individual shard on purpose.
Where This Shows Up in Your Stack
PostgreSQL: there is no ring, and that is the point — you shard Postgres with an explicit shard map (a directory table or a Citus distribution column), because you want to move a single tenant's shard deliberately during a migration rather than have a hash decide. hashtext() and hash-partitioned tables give you modulo-style bucketing inside one server, which is fine because the bucket count is fixed at design time and changing it is a rewrite you schedule.
Redis: a single instance handles 100K+ simple ops/s, so reach for Cluster when the working set exceeds one machine's RAM or you need multi-primary write throughput, not reflexively. Once in Cluster mode, design hash tags up front, verify your client handles ASK and MOVED distinctly, and expect CROSSSLOT errors on any multi-key command you did not co-locate. Module P-12 goes deeper.
Node.js: a client-side ring is per-process state, so N application instances hold N independently-built rings. Rebuild them from one authoritative membership source and log the ring's checksum — divergent rings across instances produce a hit ratio that is inexplicably low with no single node looking wrong. Also keep the ring immutable and swap the reference atomically; mutating a shared sorted array while requests are reading it is a real bug.
Load balancers and proxies: nginx's hash ... consistent and HAProxy's consistent-hash balancing exist to keep a given client or URL pinned to a backend so that backend's local cache stays warm — the same reasoning as sticky sessions in Module F-9, with the same cost, and it is why adding a backend to a hash-balanced pool degrades cache hit ratio on every backend at once.
Cassandra / ScyllaDB:num_tokens is the vnode dial, token-aware drivers route directly to a replica and skip a coordinator hop, and nodetool status showing wildly uneven ownership percentages is the imbalance from this module made visible.
Summary
hash(key) % N remaps nearly every key when N changes — only about 1/(N+1) of keys keep their node, so adding one machine to a ten-node cache invalidates roughly 91% of it, and the problem gets worse as the cluster grows.
The ring hashes nodes and keys into the same space; a key belongs to the next node clockwise. Adding a node moves only ~K/N keys, and only its immediate clockwise neighbour is affected.
Virtual nodes are mandatory, and they solve three separate problems — arc imbalance with few nodes (which falls as 1/√(N×V)), a dead node dumping its whole load on one survivor, and heterogeneous capacity, which becomes simple weighting by point count. The cost is ring size and harder topology-aware replica placement.
Bounded-load variants cap each node at (1+ε)× average and overflow past saturated nodes — buying tail-latency protection at the price of an unstable key-to-node mapping and duplicated cache entries. Sound for hashing requests to servers, risky for hashing data to owners.
Hot keys are not a ring problem. Fix them with hot-key replication, a small in-process cache, or the CDN — above the ring, not inside it.
Redis Cluster uses 16,384 explicitly assigned hash slots, not a ring. Stored ownership buys per-slot operational control; slots are the granularity, so a single hot key cannot be split. Hash tags co-locate related keys, and mid-resharding clients must treat MOVED (update the map) and ASK (redirect this one command only) differently.
Cassandra is the ring made explicit — Murmur3 tokens over a 64-bit range, num_tokens as the vnode count, ranges streamed on join. Computed placement needs no coordination and gives no control; stored placement is the reverse.
A rebalance is a partial cache flush, so scaling the cache tier is itself a load spike on the origin — Module F-12's cold-cache stampede arriving as a topology change. Mitigate with single-flight per key, gradual vnode introduction, pre-warming, previous-owner fallback, and jittered TTLs.
Consistent hashing solves placement only. It is not replication (Module P-5), not consistency, not membership agreement (Module A-1), and not a remedy for a wrong partition key.
The next module, Multi-Tenancy: Silo, Pool, Bridge, and Noisy Neighbours, takes the placement question and adds a tenant boundary to it: once many customers share one ring, "which node owns this key" becomes "which customers share a failure domain, a cache, and a noisy neighbour" — and the answer is an isolation model, not a hash function. Module P-11, Consistency Models, then supplies the guarantee that this module deliberately declined to provide.
Knowledge Check
A team runs ten memcached nodes with a client that selects a node using hash(key) % nodes.length. During evening peak they add an eleventh node for extra capacity. Within seconds the database saturates and every endpoint times out, despite no code deploy. What happened?
A five-node store uses a correctly implemented consistent hashing ring, one hash point per node. Monitoring shows one node holding roughly 38% of keys and running near saturation while another holds under 8%. Request rates per key are uniform. What does the module identify as the cause and the fix?
A team is resharding a Redis Cluster to add a node. Mid-migration, one service reports intermittent errors and permanently doubled latency on a subset of keys, while another service sees neither. The clients differ. What is going on?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
typeRing={ positions:number[]; owner: Map<number,string>};functionbuildRing(nodes:string[], replicas =160): Ring {const owner =newMap<number,string>();for(const node of nodes){// Each node contributes many points, not one — see the next section.for(let i =0; i < replicas; i++) owner.set(hash64(`${node}#${i}`), node);}// Sorted once so lookup is a binary search, not a scan of every point.return{ positions:[...owner.keys()].sort((a, b)=> a - b), owner };}functionlookup(ring: Ring, key:string):string{const h =hash64(key);let lo =0, hi = ring.positions.length -1;while(lo < hi){// first position >= hconst mid =(lo + hi)>>1;if(ring.positions[mid]< h) lo = mid +1;else hi = mid;}// The wrap: a key past the last point belongs to the first point.const pos = ring.positions[lo]>= h ? ring.positions[lo]: ring.positions[0];return ring.owner.get(pos)!;}
// Weight is expressed purely as point count. A 128 GB box takes ~4× the keys// of a 32 GB box because it occupies ~4× the ring.const weights ={"cache-01":40,"cache-02":40,"cache-03":160,"cache-04":160};
# On the destination, then the source — the slot is now in a migrating state.
CLUSTER SETSLOT <slot> IMPORTING <source-node-id> # run on destination
CLUSTER SETSLOT <slot> MIGRATING <dest-node-id> # run on source
# Then keys are moved in batches until the slot is empty:
MIGRATE <dest-host> <dest-port> "" 0 <timeout> KEYS key1 key2 ...
CLUSTER SETSLOT <slot> NODE <dest-node-id> # publish the new owner