Concept 6: Consistent Hashing

System Design Bible — File 06 of 10 Difficulty: ★★★☆☆ Prerequisites: Files 01, 02, 04, plus the hashing fundamentals in Section 0.

Table of Contents#

0Prerequisites — What You Must Understand First#

Consistent hashing is a clever twist on ordinary hashing. You need two plain ideas — what a hash function is, and what "mod N" does — before the twist lands.

0.1What a hash function is and does#

A hash function takes any input (a string like "user:42", a file, an IP address) and deterministically produces a fixed-size number called the hash. "Deterministic" means the same input always yields the same output — hash("user:42") gives, say, 1000, every single time, on every machine, forever. Two other properties matter: the output is uniformly spread (good hash functions scatter inputs evenly across the whole number range, so even very similar inputs like "user:42" and "user:43" produce wildly different, unpredictable hashes — no clustering), and it's fast to compute. That's the whole toolkit: turn any key into a repeatable, evenly-distributed number. We use this to answer "which server should hold this key?" — because if we can turn a key into a number, we can map that number to a server. (Common real hash functions: MurmurHash, MD5, SHA-1 — for distribution purposes, not cryptographic security.)

0.2The modulo operation and the naive "hash mod N" placement#

The modulo operator (mod, written %) gives the remainder of a division: 1000 mod 3 = 1 (because 1000 = 333×3 + 1). Its useful property here is that X mod N always lands in the range 0 … N−1 — so if you have N servers numbered 0 to N−1, then hash(key) mod N deterministically maps any key to one of your N servers. This is the obvious way to distribute keys across servers, and it's used everywhere at first: server_index = hash(key) mod N. It works beautifully — as long as N never changes. The entire reason consistent hashing exists is that the moment N changes (a server is added or removed), hash(key) mod N remaps almost every key to a different server (because the divisor changed), which is catastrophic (Section 2 makes this vivid). So hold both halves: hash mod N is the naive, tempting distribution method, and its fatal flaw is fragility when N changes.

0.3Why "N changes all the time" in real systems#

You might think "N rarely changes, so who cares?" — but in real distributed systems, the number of servers changes constantly, and that's the point. Servers crash (hardware fails at scale every day — File 09 §1.2). Autoscaling adds servers under load and removes them when quiet. Deploys roll servers out and in. Cache nodes get added as data grows. So N is not a fixed constant you set once — it's a number that drifts up and down throughout every normal day. Any key-placement scheme that breaks when N changes (like hash mod N) is therefore broken in practice, not just in theory. This is why consistent hashing — which barely reshuffles anything when N changes — is foundational to caches (File 02), sharded databases (File 04), and load balancers (File 01). Keep this framing: **elasticity is the normal state, so stability under elasticity is the requirement.**

0.4The four properties of a hash function that actually matter here#

Section 0.1 gave you the one-line version: a hash function turns any input into a repeatable, evenly-spread number. That sentence hides four separate properties, and every one of them is load-bearing for consistent hashing. If any one fails, your cluster develops a hot node, a correctness bug, or a security hole. Learn them by name, because interviewers ask "what makes a hash function good for partitioning?" and the answer is not "it's random."

Property 1 — Determinism. The same input must produce the same output, always: on every machine, in every process, in every language binding, today and in three years. This sounds trivial and it is the property most often broken in practice, by accident. Three classic ways to break it: (a) seeding with a random value at process start — many hash libraries (Python's built-in hash() for strings, Java's Object.hashCode() for non-overridden objects) deliberately randomize per process to defend against the hash-flooding attack you will meet in §0.5; if two application servers use hash("user:42") from such a function, they will disagree about which cache node owns user:42 and you get a silent 50% miss rate that no dashboard explains. (b) Encoding drift — hashing the characters of a string rather than a defined byte encoding, so a UTF-8 client and a UTF-16 client hash the same logical key to different numbers. (c) Version drift — upgrading a library and getting a "improved" hash function, which silently re-partitions your entire dataset on deploy. The rule you carry into production: the hash function used for partitioning must be pinned by name and version, take bytes (not language-level objects) as its input, and be unseeded or seeded with a constant that is part of the cluster configuration. This is why systems like Cassandra name their partitioner in the config file (partitioner: org.apache.cassandra.dht.Murmur3Partitioner) and treat changing it as a "you must rebuild the cluster" operation.

Property 2 — Uniformity. The outputs must be spread evenly across the entire output range, so that if you feed the function a million real-world keys, roughly the same number of them land in every equal-sized slice of the output space. This is what makes "hash the key, take the result mod 4" produce four roughly equal groups. Uniformity is what fails when people invent their own hash functions: a naive sum of character codes hash maps "ab" and "ba" to the same value and maps almost all short English strings into a narrow band of small integers, so nine of your ten shards sit idle. Formally, what you want is that for a uniformly random key, P(hash(key) lands in any given 1/M slice of the range) ≈ 1/M. Real, tested hash functions (MurmurHash3, xxHash, CityHash, SipHash, MD5, SHA-1) achieve this to within measurement noise; hand-rolled ones almost never do. Diagnostic: hash a sample of one million production keys, bucket them into 256 buckets by the top byte of the hash, and plot the counts. A good function gives you 256 bars all within a few percent of 3,906. A bad one gives you a skyline.

Property 3 — The avalanche effect. This is uniformity's stricter, more useful cousin, and it is the property nobody explains. Avalanche means: flipping a single bit of the input flips, on average, half the bits of the output, and which bits flip is unpredictable. A function with good avalanche maps "user:42" and "user:43" — which differ in one bit of one character — to two numbers that look completely unrelated, like 0x9F3A11C4 and 0x2D7B80E9. Why does this matter for partitioning specifically? Because real keys are not random — they are sequential and structured. Your keys are user:1, user:2, user:3, …, or 2026-07-22T10:00:00, 2026-07-22T10:00:01, …, or order_0000001, order_0000002. If the hash function preserves any of that structure — if similar inputs give nearby outputs — then a contiguous run of your keys lands on one node, which is precisely the hot spot you are trying to avoid. Avalanche is the property that destroys input structure. The standard way it is engineered into a function is a finalization mix (also called a "bit mixer" or "finalizer"): after the main loop, the function XORs the accumulator with a right-shifted copy of itself and multiplies by an odd constant, repeatedly. MurmurHash3's finalizer is literally five lines:

   h ^= h >> 16
   h *= 0x85ebca6b
   h ^= h >> 13
   h *= 0xc2b2ae35
   h ^= h >> 16

Each h ^= h >> k step lets high bits influence low bits; each multiplication by a large odd constant lets low bits influence high bits. Five rounds of that and one input bit has reached every output bit. The measurable version: a "strict avalanche criterion" test flips each input bit in turn over a large corpus and checks that each output bit flips 50% ± 1% of the time. What breaks without it: you use the low bits of a weak hash for mod N and discover that all your user:* keys land on shard 0 because the low bits encoded the prefix.

Property 4 — Speed. You will call this function on every single request — for a cache client, once per GET; for a proxy, once per connection; for a storage node, once per row read and once per row write. At 500,000 requests per second, a hash function costing 1 microsecond costs you half a CPU core doing nothing but hashing; one costing 20 nanoseconds costs you 1% of a core. Modern non-cryptographic hashes are measured in bytes per cycle: xxHash3 runs at roughly 10–30 GB/s on a modern core for large inputs, MurmurHash3 at roughly 3–4 GB/s, and SHA-256 at roughly 1–2 GB/s with hardware acceleration and around 0.2 GB/s without. For the short keys typical of partitioning (10–60 bytes), what dominates is not throughput but fixed setup cost, and the gap is still roughly an order of magnitude. That order of magnitude is the entire reason the next sub-section exists.

Hold this: determinism makes the cluster agree, uniformity makes the shards equal, avalanche destroys the structure your real keys unavoidably have, and speed is why you do not reach for a cryptographic hash by reflex.

0.5Cryptographic vs non-cryptographic hashes — and the one case where you need the expensive one#

A cryptographic hash function (MD5, SHA-1, SHA-256, SHA-3, BLAKE3) is designed to make three things computationally infeasible for an adversary who is actively trying: (1) pre-image resistance — given an output h, find any input x with hash(x) = h; (2) second pre-image resistance — given a specific input x, find a different x' with the same hash; (3) collision resistance — find any pair x ≠ x' with the same hash. Achieving these requires many rounds of deliberately expensive mixing, and that expense is the entire product.

A non-cryptographic hash function (MurmurHash3, xxHash / xxHash3, CityHash / FarmHash, wyhash, FNV-1a, CRC32) is designed for exactly the four properties in §0.4 and nothing else. It gives you determinism, uniformity, avalanche, and speed, and makes no promise whatsoever that an adversary cannot construct collisions — in fact, for MurmurHash3 and CityHash, constructing collisions is easy and published.

Why partitioning uses the cheap ones. Ask what a collision actually costs you in a partitioner. If hash("user:42") and hash("photo:9981") happen to produce the same 32-bit number, what breaks? Nothing. Both keys map to the same ring position, walk clockwise to the same node, and are stored under their own distinct key names in that node's local map. Two keys sharing a ring position is not a data-integrity event; it is a shrug. Collisions in a partitioner cost you a microscopic amount of load imbalance and no correctness at all. You are not using the hash as an identity, a signature, or a deduplication key — you are using it as a dartboard coordinate. Paying SHA-256's price to get adversary-resistance you do not consume is pure waste: 10–50× the CPU per request for a property that buys you nothing. This is the reasoning to say out loud in an interview, because the naive answer ("SHA-256 is the best hash, use it") is exactly the tell of someone who has not thought about what the hash is for.

There is one important historical exception worth naming so you are not confused when you see it: **memcached's ketama (§12.3) uses MD5, and Cassandra originally used MD5** via its RandomPartitioner before switching to MurmurHash3 in Murmur3Partitioner. Neither did so for security. Ketama used MD5 because in 2007 it was the well-distributed hash everyone had in every language's standard library, and its 128-bit output conveniently yields four 32-bit ring points per hash call — an efficiency trick, not a security decision. Cassandra's switch to Murmur3 was explicitly a performance change (roughly 3–5× faster partitioning), and it was a breaking change requiring a full rewrite of the data, which is the determinism lesson of §0.4 in production form.

**Sub-Concept: Hash-flooding (algorithmic complexity) attacks — the case where you do need the strong hash.**

What it is. A hash-flooding attack is a denial-of-service attack in which an attacker deliberately submits inputs that all hash to the same value, in order to destroy the performance of a hash-based data structure.

Why it exists. A hash table gets its O(1) average lookup from the assumption that keys scatter across buckets. If every key lands in one bucket, the bucket degenerates into a linear list and lookups become O(n); inserting n colliding keys costs O(n²) total. In 2011, researchers (Klink and Wälde, at 28C3) showed that for PHP, Python, Java, Ruby, and others, an attacker could compute thousands of colliding strings offline and send them as HTTP POST parameters — the web framework would dutifully build a hash map of the parameters and burn minutes of CPU on a single request. A few kilobytes of request body consumed an entire core.

Where it sits. This is an attack on the hash table inside a process, not on your partitioner. It applies wherever an untrusted party controls the keys going into a hash structure: HTTP query parameters, JSON object keys, HTTP headers, cache keys derived from user input.

How it works, step by step. Suppose a server uses a weak, publicly-known, unseeded hash. The attacker (1) obtains the hash function's source, (2) runs a meet-in-the-middle search to generate 10,000 distinct strings all hashing to, say, 0, (3) sends them as a[k1]=1&a[k2]=1&…. The server inserts key 1 (0 comparisons), key 2 (1 comparison), key 3 (2 comparisons)… key 10,000 (9,999 comparisons) — about 50 million string comparisons for one request. Repeat at 10 requests per second and the machine is gone.

The named fixes. (a) Randomized seeding — the process picks a random seed at startup and mixes it into every hash, so the attacker cannot precompute collisions because they do not know the seed. This is what Python's PYTHONHASHSEED controls and why Python's string hash() is not stable across processes. (b) Keyed cryptographic-strength hashing — use SipHash, a fast pseudorandom function specifically designed for this job (Aumasson and Bernstein, 2012); it takes a 128-bit secret key, runs at a few GB/s (much faster than SHA-256, much slower than xxHash), and is provably hard to collide without the key. SipHash is now the default string hasher in Rust's HashMap, in Python, in Perl, and in the Linux kernel. (c) Cap the number of parameters the framework will parse.

What breaks / how you diagnose it. Symptom: single requests pinning a core to 100% with a flat CPU profile inside the hash-map insert path; the request body is unremarkable in size. perf top shows time inside string comparison.

The tie-back — and the important boundary. Hash flooding is why you must not use MurmurHash or xxHash for a hash table whose keys come from an attacker. It is not a reason to abandon them for partitioning, because in partitioning the "buckets" are your handful of nodes and a collision costs nothing. But there is one genuine partitioning-adjacent case: if an attacker can choose cache keys or shard keys and knows your unseeded hash function, they can compute a set of keys that all land on one node and aim a targeted overload at it — a "shard-flooding" attack. The mitigations are to seed the partitioner hash with a cluster-wide secret (a constant, so determinism is preserved — §0.4), to rate-limit per client (File 03), and to use bounded loads (§6.3) so a single node cannot be pushed past a cap.

Hold this: use a fast non-cryptographic hash for partitioning because collisions there are harmless; use a keyed hash like SipHash whenever an adversary controls the keys of an in-process hash table; use a real cryptographic hash only when you need identity, integrity, or signatures — never for "which shard."

0.6Modular arithmetic and "the keyspace" — the two pieces of maths you need#

Modular arithmetic in the amount you need. §0.2 introduced mod as "the remainder." Three consequences are worth stating explicitly because the rest of the file leans on them.

First, **X mod N is always in [0, N−1]** — never negative, never N. This is the property that makes it a bucket selector: if you have exactly N buckets numbered 0 through N−1, X mod N names one of them and nothing else. (A real bug to know: in Java and C, % on a negative number returns a negative result — -7 % 4 == -3 — so if your hash function returns a signed 32-bit integer that happens to be negative, hash % N can index -3 and throw an ArrayIndexOutOfBoundsException. The standard fixes are to mask off the sign bit with hash & 0x7fffffff, to use Math.floorMod(hash, N), or to treat the hash as unsigned. This exact bug has shipped in real cache clients.)

Second, **mod partitions the integers into N interleaved arithmetic sequences.** Bucket 0 gets 0, N, 2N, 3N, …; bucket 1 gets 1, N+1, 2N+1, …. That interleaving is why mod N distributes well when N is fixed — consecutive hashes go to consecutive different buckets — and it is also exactly why it distributes catastrophically differently when N changes, because changing N changes every one of those sequences at once. Hold that thought; §2 quantifies it.

Third, the choice of N interacts with the hash's weaknesses. If your hash function's low bits are poor (a real weakness in old hashes and in String.hashCode() in Java, which is s[0]*31^(n-1) + s[1]*31^(n-2) + …), then mod N for a power-of-two N reduces to "take the low log2(N) bits," and you inherit that weakness directly. mod by a prime N mixes the high bits into the result and hides weak low bits, which is the historical reason textbooks tell you to size hash tables at primes. With a modern avalanche-quality hash (§0.4) this concern evaporates, which is why production systems freely use power-of-two bucket counts — Redis Cluster's 16,384 and Elasticsearch's arbitrary shard counts both rely on the partitioner being good enough that the modulus choice does not matter.

Sub-Concept: The keyspace (and the hash space / token space).

Plain definition. The keyspace is the set of all keys your system could ever be asked about — every possible user:* id, every possible cache key, every possible row primary key. It is conceptually infinite and has no useful structure. The hash space (used interchangeably with token space in Cassandra and partition space in Swift) is the finite set of all possible outputs of your hash function — and it is the thing you actually partition.

Why the distinction exists. You cannot draw a picture of "all possible strings," and you certainly cannot assign ranges of them to servers. But you can draw a picture of "all integers from 0 to 2³²−1," and you can hand out ranges of that to servers. The hash function's real job in this file is to project an unbounded, unstructured, non-uniform keyspace onto a bounded, uniformly-populated integer space that you can carve up with a ruler. Everything consistent hashing does happens in the hash space; the keyspace is only ever visited through the hash.

Where it sits — the concrete ranges. The hash space size is set by the hash function's output width: - A 32-bit hash gives 0 … 2³²−1 = 0 … 4,294,967,295 — about 4.29 billion positions. This is what classic ketama (§12.3) and NGINX's ring use. - A 64-bit hash gives 0 … 2⁶⁴−1 ≈ 1.8 × 10¹⁹. Cassandra's Murmur3Partitioner actually uses the signed 64-bit range, −2⁶³ … 2⁶³−1, i.e. −9,223,372,036,854,775,808 … 9,223,372,036,854,775,807. That negative lower bound surprises people reading nodetool ring output for the first time; it is just a signed integer, and the ring wraps from the maximum back to the minimum exactly as an unsigned ring wraps from 2⁶⁴−1 to 0. - A 128-bit hash (MD5, or Murmur3's 128-bit variant) gives 0 … 2¹²⁸−1 ≈ 3.4 × 10³⁸. Riak and Dynamo-family systems commonly use 160-bit SHA-1 space, 0 … 2¹⁶⁰−1.

How wide is wide enough? The only thing the width buys you is resolution: with V total ring points, you want the space to be enormously larger than V so that two ring points essentially never collide and so that arcs can be finely sized. With a 32-bit space and 1,000 nodes × 200 vnodes = 200,000 points, the birthday-problem collision probability (the counterintuitive statistical fact that random collisions become likely far sooner than intuition suggests — with k random draws from M slots, the chance of at least one collision is roughly 1 − e^(−k²/2M)) is 1 − e^(−200000²/(2×4.29e9)) ≈ 99.1% — you will absolutely have colliding ring points and must define a tie-break rule. With a 64-bit space the same calculation gives about 1 in 10⁹. This is a real reason modern systems moved from 32-bit to 64-bit or 128-bit rings.

What breaks. Too-narrow a hash space plus many vnodes gives colliding tokens, which most implementations resolve by refusing to add the node or by nudging the token — either way an operational surprise. Cassandra will refuse to bootstrap a node whose token collides with an existing one.

The tie-back. Consistent hashing is nothing more than "cut the hash space into arcs and give each arc to a node." Knowing the exact size and signedness of that space is how you read nodetool ring, size vnode counts, and reason about collisions.

Hold this: the keyspace is what users name, the hash space is what you partition; the hash is the projection from one onto the other; and its width (32 / 64 / 128 / 160 bits) sets how finely you can slice.

0.7Node, shard, partition, replica, token — the vocabulary, pinned down#

These five words are used loosely everywhere, including in the papers, and mixing them up is the single most common source of confusion in this topic. Here they are, each nailed to a definition this file will use consistently.

Node. A node is one running process that owns some data or serves some requests, together with the machine (physical server, VM, or container) it runs on. In a Cassandra cluster, a node is one cassandra JVM on one machine. In a memcached fleet, a node is one memcached process listening on one host:port. In this file, "node" means a member of the pool we are distributing across — the thing that gets added and removed and whose count is N. When precision matters, we say physical node to mean the actual machine/process, as distinct from the virtual nodes of §5 which are merely multiple ring positions belonging to the same physical node. That distinction is not pedantry: replication correctness (§9.1) depends entirely on counting distinct physical nodes, not ring positions.

Partition (a.k.a. shard). A partition is a subset of the data, defined by a rule, that is stored together. "Shard" is the same idea; the words are interchangeable in practice, with "shard" more common in the relational/Elasticsearch world and "partition" more common in Kafka, Cassandra, and the academic literature (File 04 uses them together deliberately). The crucial point is that a partition is a logical unit of data, and a node is a physical unit of capacity, and the mapping between them is the whole subject of this file. In a hash-slot system (§8) the partitions are explicit, numbered, and countable — Redis Cluster has exactly 16,384 of them, forever. In a pure hash ring, the "partitions" are the arcs between adjacent ring points, and they are implicit, unnumbered, and change shape whenever membership changes. Recognizing which of those two worlds a system lives in is the single most useful diagnostic in this whole topic.

Replica. A replica is a complete copy of a partition stored on a different node so the data survives that node's death. If a partition has a replication factor (RF) of 3, there are three copies of it on three distinct physical nodes. Two warnings. First, replicas are copies of partitions, not copies of nodes — node X might hold the primary copy of partition 7 and a secondary copy of partitions 3 and 91; there is no such thing as "X's replica machine." Second — and this is a genuine terminology trap — **the Dynamo paper and several ketama-derived libraries use the word "replica" to mean a virtual node (a ring point), not a data copy. When you read "200 replicas per node" in a consistent-hashing library's README, it means 200 ring positions, not 200 data copies. This file says vnode for ring points and replica** for data copies, always, and flags the ambiguity again in §5.2 where the collision actually appears.

Token. A token is Cassandra's word for a node's position on the ring — a single 64-bit integer. A node with num_tokens: 16 owns 16 tokens, i.e. 16 vnodes, i.e. 16 ring positions, i.e. 16 arcs of the token space. "Token range" means the arc (previous_token, this_token]. When you run nodetool ring you are printing the sorted list of all tokens and their owners — literally the ring data structure of §4.1.

Bucket / slot. In mod N and in jump hash (§7.2), the destinations are called buckets, numbered 0 … N−1. In Redis Cluster they are called slots, numbered 0 … 16383. Both are the fixed-partition world of §8: a numbered, countable set of destinations that is decoupled from the node list.

Hold this: keys hash into a hash space; the hash space is divided into partitions; partitions are assigned to nodes; each partition has RF replicas on distinct physical nodes; and a vnode/token is just one more ring position belonging to a physical node. Every scheme in this file is a different answer to "how are partitions assigned to nodes."

0.8Big-O, applied to the two costs that matter: lookup and rebalancing#

Big-O notation describes how a cost grows as a problem gets bigger, ignoring constant factors. O(1) means the cost does not depend on the size at all; O(log N) means the cost grows like the number of times you can halve N (for N = 1,000,000 that is about 20 steps); O(N) means the cost grows in direct proportion; O(N log N) grows slightly faster than proportionally. It is a statement about shape, not about speed: an O(N) operation with a tiny constant can beat an O(log N) one at small N, and for the node counts in this file (often N = 10 to N = 1,000) that caveat matters a lot — it is exactly why rendezvous hashing's O(N) lookup (§7.1) is perfectly acceptable at N = 20 and unusable at N = 10,000.

For every scheme in this file you must be able to state three costs, and the third one is the one candidates forget:

Cost 1 — Lookup time. Given a key, how much work is it to compute which node owns it? This is paid on every single request, so its constant factor is real money. A sorted-array ring costs O(log V) where V is the total number of ring points (nodes × vnodes) — that is a binary search: about 17 comparisons for V = 100,000. Rendezvous hashing costs O(N) hash computations — one per node. Jump hash costs O(ln N) iterations of a five-line loop. Maglev and hash slots cost O(1): one array index into a precomputed table.

Cost 2 — Memory / state. How much data must every client or node hold to answer lookups? The ring needs O(V) entries — with 1,000 nodes at 200 vnodes each, 200,000 entries of (token, node-id), roughly 3–5 MB, which must be held by every client and kept in sync. Rendezvous needs O(N) — just the node list, 1,000 entries. Jump hash needs O(1) — literally just the integer N. Maglev needs O(M) where M is the lookup-table size (65,537 or 655,373 entries per service). Hash slots need O(S) — 16,384 entries for Redis Cluster.

Cost 3 — Keys moved on a membership change. When you go from N nodes to N+1, what fraction of all keys changes owner? This is the cost that consistent hashing exists to minimize, it is paid in network bandwidth and disk I/O over hours, and it is invisible in a microbenchmark. The theoretical minimum is 1/(N+1) — you cannot do better, because the new node must receive its fair share 1/(N+1) of the data from somewhere. mod N moves about 1 − 1/N' ≈ 80% at N=4→5 (§2.4). A ring moves ≈ 1/(N+1) — optimal. Rendezvous moves exactly 1/(N+1) — optimal, and with a stronger guarantee (§7.1). Jump hash moves exactly 1/(N+1) — optimal. Maglev moves slightly more than optimal, by design, in exchange for perfect balance (§7.3). Hash slots move whole slots and therefore also ≈ 1/(N+1) of the data (§8.3).

There is a fourth cost that only shows up in operations, and it is worth naming now: the number of distinct peers involved in a rebalance. Moving 1/N of the data as one contiguous chunk from one neighbour (a ring with no vnodes) and moving 1/N of the data as two hundred small chunks from every peer in the cluster (a ring with vnodes) are the same number of bytes and completely different operational events — the first saturates one machine's disk and network for an hour, the second spreads the pain and finishes far faster. §5.5 works this through.

Hold this: judge every scheme in this file on lookup time, state size, and fraction-of-keys-moved — and remember that the third cost is paid in hours of production I/O, which is why it dominates the other two in importance.

1Architectural Definition & "The Why"#

1.1The Plain Definition#

Consistent hashing is a hashing technique for distributing keys (data, requests, sessions) across a set of nodes (servers, cache instances, shards) such that **when the number of nodes changes — a node is added or removed — only a small fraction (~K/N keys, roughly 1/N of all keys) need to be remapped**, instead of nearly all of them.

It answers the question: "How do I decide which server owns which key, in a way that stays stable when the server pool grows or shrinks?"

1.2"The Why" — Distributed Systems Are Elastic#

We've hit the "which node owns this key?" problem repeatedly:

In all three, the naive answer is hash(key) mod N. And in all three, that answer falls apart the moment N changes — which, in any real distributed system, happens constantly: servers crash, autoscaling adds/removes nodes, you deploy, hardware fails. Distributed systems are elastic and failure-prone by nature; the node count is never fixed.

Consistent hashing was invented (Karger et al., 1997, at MIT — originally for distributed web caching, later famous via Amazon's Dynamo paper) precisely to make key→node mapping stable under membership changes, so that adding/removing a node causes minimal data movement and minimal disruption. It is one of the most important primitives in distributed systems — the connective tissue under Files 02, 04, and much of 07/08/09.

2The mod N Catastrophe (the problem it solves)#

Let's make the pain concrete, because understanding *why mod N is catastrophic* is half of understanding consistent hashing.

2.1The Setup#

You have 4 cache servers (N=4). You place each key with:

server_index = hash(key) mod 4

Say hash("user:42") = 1000 → 1000 mod 4 = 0 → server 0. Every lookup recomputes the same formula, always lands on server 0. Fine.

2.2The Disaster: N Changes#

Now server 3 dies, so N=3. Every key is now placed with hash(key) mod 3. Recompute:

"user:42": 1000 mod 4 = 0   ->  1000 mod 3 = 1     MOVED
             (was on server 0, now expected on server 1)

Because the modulus changed, the mapping changes for almost every key — not just the keys that were on the dead server. Mathematically, changing the modulus from 4 to 3 remaps roughly 3/4 (≈ (N-1)/N) of all keys to different servers.

2.3Why This Is Catastrophic#

The core defect: mod N couples every key's placement to the total count N. Change N, and everything moves. We need a scheme where a key's placement depends on the node identities, not the node count — so removing one node only affects the keys that node held.

2.4The exact arithmetic: how much data really moves when N changes#

"Roughly all of it" is the right instinct and the wrong answer in an interview. Here is the precise statement, its derivation, and a worked table you can reproduce on a whiteboard.

The formula. Move from N nodes to N' = N+1 nodes. A key survives — i.e. does not move — only if hash(key) mod N == hash(key) mod N'. For a uniformly distributed hash (§0.4), the probability of that coincidence is:

   P(key stays) = 1 / max(N, N')  ... approximately, and exactly 1/N' when N' > N
   P(key moves) = 1 − 1/N'

The derivation in plain words. Under the new scheme the key lands in one of N' buckets, each with probability 1/N', and its choice of new bucket is effectively independent of its old bucket (because mod N and mod N' slice the integers along incommensurate periods — §0.6's second consequence). So the chance the new bucket happens to equal the old bucket is just the chance of hitting one specific bucket out of N': 1/N'. Everything else moves.

Plug in the numbers.

Read the last row and let it land: **adding one machine to a thousand-machine cluster under mod N invalidates 99.9% of your data placement.** The bigger your cluster, the worse mod N gets — which is exactly backwards from what you need. Contrast this with the number consistent hashing achieves for the same change: 1/1001 = 0.1% moved. That is a factor of one thousand.

Note the asymmetry with removal: going from N = 5 down to N' = 4, the surviving fraction is 1/5 = 20% (a key stays put only if its old bucket index, which was in 0..4, is also what mod 4 produces) — so about 80% moves either way. Growing and shrinking are equally catastrophic.

2.5The worked table — eight real keys, N=4 → N=5#

Formulas convince nobody. Here are eight concrete keys with (illustrative but internally consistent) hash values, placed on 4 servers and then on 5. Do this arithmetic yourself once and you will never forget the result.

Four of eight moved in this small sample (50%); the expected value over a large sample is 80%, and small samples are noisy — run the same experiment over a million keys and you will measure 80.0% to within a few hundredths of a percent. The important qualitative observation is visible even here: keys moved from server 2 to server 0, and from server 3 to server 2, and from server 1 to server 2. The reshuffle is not "the new server takes a fair slice from everyone" — it is a global permutation. Every server both loses keys and gains keys, and the network carries all of it simultaneously.

Now the same change under a hash ring (§4), for contrast:

One key moved, and it moved to the new node. No key moved between two pre-existing nodes — that is the structural guarantee, and it is what makes the operation safe: the only machine doing extra work is the one you just added, and the only machine losing data is its single ring predecessor.

2.6What 80% remapping actually does to a running system#

The percentage is abstract. Here is what it looks like on the pager, split by what kind of system you are running — because the failure mode is genuinely different for a cache and for a datastore.

Case A — the cache: an instant, self-amplifying stampede. You run 4 memcached nodes fronting a MySQL primary. Steady state: 500,000 requests/second at a 98% hit ratio, so the database sees 500,000 × 0.02 = 10,000 queries/second and is comfortable. One node dies. Under mod 4 → mod 3, ~67% of keys now hash to a node that has never seen them. The effective hit ratio collapses from 98% to roughly 33%, so the database instantaneously sees 500,000 × 0.67 = 335,000 queries/second — 33× its provisioned load. It does not serve them; it queues them, its connection pool exhausts, latency climbs from 2 ms to 30 s, and the application's threads all block waiting on the database. This is the cache avalanche (File 02 §6.2 — the failure where a large fraction of the cache becomes invalid at once and the resulting flood of misses overwhelms the origin), and here it was caused not by a TTL expiry wave but by a single machine reboot.

The self-amplifying part is the cruelty. Because the database is now slow, requests take longer, so more of them are in flight at once, so more connections are open, so the database is slower. And because each miss also writes the fetched value back into the cache, you get a thundering herd on individual keys — a thousand concurrent requests for the same missing key each independently query the database for it (File 02's cache stampede; the standard mitigations are request coalescing / single-flight, where only the first requester queries and the rest wait on its result, and probabilistic early expiration). Consistent hashing does not eliminate stampedes, but it reduces the blast radius from "67% of the keyspace" to "1/N of the keyspace" — with 4 nodes, from 67% to 25%, and with 40 nodes, from 97.5% to 2.5%.

Case B — the datastore: a multi-hour or multi-day migration you cannot abort. Now the same mod N scheme is placing durable rows, not cache entries. A miss is not a slow request — it is a wrong answer, because the data genuinely is not on the node the formula now points at. So you cannot simply change N and let the system heal; you must physically copy 80% of the data to new homes before or during the cutover. Work the arithmetic for a modest cluster: 4 nodes × 2 TB = 8 TB total; 80% of that is 6.4 TB that must cross the network. On a 10 Gbps network fully dedicated to the migration (1.25 GB/s theoretical, realistically ~0.8 GB/s after protocol overhead and because you also have to read it off disk and write it to disk at the far end) that is 6,400 GB ÷ 0.8 GB/s ≈ 8,000 seconds ≈ 2.2 hours — if you give the migration 100% of the network and the disks, which you cannot, because the cluster is also serving traffic. Give it 20% and it is 11 hours, during which every disk is saturated, every read is slow, and you cannot roll back without doing the whole thing again in reverse. Scale to 100 nodes × 8 TB and the same computation gives you days.

Under consistent hashing the same "add one node to a 100-node cluster" moves 1/101 of 800 TB ≈ 7.9 TB — but critically, that 7.9 TB is streamed to the new node rather than permuted among all the old ones, and (with vnodes, §5.5) it is sourced in small pieces from all 100 peers at once, so each peer contributes only ~79 GB. It is a background task, not an outage.

Case C — the load balancer: connection resets. If mod N is choosing a backend for a connection or a session (File 01 §4.6's IP-hash algorithm), then changing N re-pins ~80% of clients to a different backend. For stateless HTTP this costs you cache locality. For anything sticky — an in-memory session, a WebSocket, a long-lived gRPC stream, a video transcode in progress — it costs you a reset: the client is now talking to a machine that has no idea who it is. At Google's scale, an L4 balancer reshuffling flows on every backend change would break millions of TCP connections per deploy, which is precisely the problem Maglev hashing (§7.3) was built to solve.

2.7The two properties we are actually shopping for#

Everything from here on is a search for a key→node mapping with two properties simultaneously. Name them, because the whole algorithm catalogue in §7 is a set of different trade-offs between exactly these two:

Karger's 1997 insight was that you can have both, and the mechanism is startlingly simple: stop computing the node from the count, and start computing it from the node identities. If a key's owner is determined by "which node identifier is nearest to me in hash space," then removing a node can only affect keys that were nearest to that node, and adding a node can only affect keys that are now nearer to the new one. The count N never enters the formula at all — and a formula that does not mention N cannot be destabilized by N changing. That single sentence is the intellectual core of this entire file.

3The Recursive Sub-Concept Tree#

3.1Sub-Concept: Hash Function & Hash Space#

A hash function maps arbitrary input to a fixed-size integer (e.g., MD5/SHA-1/MurmurHash → a number). The hash space is the full range of possible outputs, e.g., 0 to 2^32 − 1. Consistent hashing's trick is to treat this linear range as a circle (ring): the largest value wraps around to 0. So the hash space becomes a ring of positions 0 … 2^32−1 … 0.

3.2Sub-Concept: Placing Nodes AND Keys on the Same Ring#

The key insight: hash the nodes onto the ring too, using the same hash function you use for keys. A server named "cache-node-A" gets a position hash("cache-node-A") somewhere on the ring. Now both keys and nodes live as points on the same circle. Ownership is defined by proximity on the ring, not by a modulus.

3.3Sub-Concept: The "Walk Clockwise" Ownership Rule#

To find which node owns a key: hash the key to a point on the ring, then walk clockwise until you hit the first node. That node owns the key. (Equivalently: each node owns the arc from the previous node up to itself.) That's the whole rule. Simple, and — crucially — a key's owner depends only on the positions of the nodes near it, not on the total node count.

3.4Sub-Concept: Data Movement on Membership Change#

When a node is removed, only the keys it owned (its arc) move — to the next clockwise node. Every other key stays put. When a node is added, it inserts itself at its hash position and takes over only the slice of the arc between it and the previous node — stealing a fraction of keys from exactly one successor node. Everything else is untouched. This is the ~1/N property. (Full mechanics in Section 4.)

3.5Sub-Concept: Skew & Virtual Nodes (preview)#

Placing N nodes at N random ring positions gives uneven arc sizes — by luck, one node might own a huge arc (lots of keys) and another a tiny one. This imbalance is skew (hot spots return, File 04). The fix is virtual nodes: represent each physical node as many points on the ring, so the law of large numbers evens out the arcs. Full treatment in Section 5.

4Deep-Dive Mechanics: The Hash Ring#

4.1The Ring, Step by Step#

Imagine the ring as a clock face numbered 0 to 2^32−1, wrapping at the top.

Step 1 — place the nodes. Hash each server's identifier onto the ring:

hash("A") -> position 10
hash("B") -> position 90
hash("C") -> position 200      (ring goes 0..359 in this toy example)

                0/360
                  │
        C(200)         A(10)
            \          /
             \        /
              (ring)
             /        \
            /          \
                B(90)

Step 2 — place a key and walk clockwise. To store key1 with hash("key1") = 50:

hash("key2") = 150 → walk clockwise → next node is C at 200 → C owns key2. hash("key3") = 250 → walk clockwise → wrap past 360→0 → next node is A at 10 → A owns key3.

The lookup implementation: keep the node positions in a sorted structure (a sorted array or a balanced BST / TreeMap). To find a key's owner, binary search for the smallest node position ≥ hash(key) (wrapping to the first node if none) — O(log N) lookup.

4.2Removing a Node (the payoff)#

Suppose B (at 90) dies. Which keys move? Only the keys in B's arc — the keys whose hash falls in (A=10, B=90], i.e., keys that used to walk clockwise and stop at B. They now walk past 90 and stop at the next clockwise node, C at 200. So B's keys migrate to C.

Every other key is completely unaffected:

Only ~1/N of keys (B's share) moved, and they all went to exactly one node (C). Contrast with mod N, where removing B would have reshuffled ~75% of all keys across all servers. This is the entire point.

4.3Adding a Node#

Add D at position 120. D inserts itself between B (90) and C (200). D now owns the arc (90, 120] — keys that previously walked past 90 to C now stop at D instead. So D steals a slice of C's keys, and only C's. A, B, and the rest are untouched. Adding a node pulls load from exactly one successor.

4.4Complexity Summary#

5Virtual Nodes — Fixing Skew#

5.1The Skew Problem#

With only one ring point per physical node and, say, 3 nodes, the three arcs are almost never equal — random placement might give A 50% of the ring, B 35%, C 15%. Then A holds 50% of the data and gets 50% of the traffic → hot spot, exactly what we were trying to avoid. Worse, when a node dies, all its load dumps onto a single successor (doubling that successor's load), which can trigger a cascading failure (File 01 thundering herd).

5.2The Fix: Virtual Nodes (a.k.a. vnodes / replicas)#

Instead of hashing each physical node once, hash it many times with different suffixes, placing many points on the ring per physical node:

hash("A#1"), hash("A#2"), ..., hash("A#200")   -> 200 points for node A
hash("B#1"), ..., hash("B#200")                -> 200 points for node B

Now the ring has N × 200 points, all interleaved. Each physical node owns many small arcs scattered around the ring rather than one big contiguous arc.

Two huge benefits:

Bonus — heterogeneous capacity: give a beefier server more vnodes (e.g., 400 vs 200) so it owns proportionally more of the ring — weighted distribution for mixed hardware (echoing File 01's weighted balancing).

5.3The Trade-off#

More vnodes = better balance but more ring points = more memory and slightly slower lookups (larger structure) and more metadata to gossip around the cluster. Typical values: 100–256 vnodes per physical node. Cassandra historically defaulted to 256 num_tokens (later reduced to ~16 with better allocation algorithms, since too many vnodes hurt other operations like repair and streaming).

6Adding/Removing Nodes & Bounded Loads#

6.1Replication on Top of the Ring (how Dynamo/Cassandra use it)#

Consistent hashing places the primary owner of a key, but real systems need replicas for availability (File 04's replication × partitioning grid). The standard extension: a key is stored on its owner node **plus the next R−1 distinct physical nodes clockwise on the ring (the preference list** in Dynamo terms). So R=3 means: walk clockwise to the owner, then keep walking to the next 2 distinct physical nodes (skipping additional vnodes of the same physical node). This gives 3 replicas, naturally derived from the ring, and it "just works" as nodes come and go. (Consistency across those replicas — quorums — is File 08.)

6.2The Hotspot-Key Problem Consistent Hashing Does NOT Solve#

Consistent hashing evens out many keys across nodes. It does not help when a single key is a hotspot (one viral item, one celebrity) — that key maps to one node regardless of vnodes, and that node melts. Fixes are orthogonal: replicate/caching the hot key (File 02), or key salting (File 04). Interviewers love catching candidates who think consistent hashing solves single-hot-key problems — it doesn't.

6.3Consistent Hashing with Bounded Loads (Google, 2017)#

A refinement: even with vnodes, transient imbalance and hot keys can overload a node. Consistent Hashing with Bounded Loads (CHWBL) adds a rule: each node has a capacity cap (e.g., no node may exceed (1+ε) × average load). If a key's clockwise-owner is already at capacity, the key overflows to the next node with spare capacity. This guarantees no node exceeds a bounded load while preserving most of consistent hashing's stability. Used in load-balancing contexts (e.g., Google's cloud LB, Vimeo's use for video). A great "do you know the modern refinement?" talking point.

6.4Failover / Rebalancing Flow#

When a node is detected dead — via health checks (File 01) or a gossip protocol (each node periodically picks a few random peers and exchanges everything it knows about cluster membership and health; like rumors, information reaches every node in O(log N) rounds with no central coordinator, and the whole cluster converges on "node X is dead" without anyone being in charge — full treatment in File 08):

Because only ~1/N of data ever moves, these operations are cheap relative to the cluster size — the property that makes elastic scaling practical.

7Variants: Rendezvous, Jump, Maglev, Multi-Probe & Anchor — The Full Algorithm Family#

Consistent hashing (the ring) is the famous one, but it is one member of a family. Five algorithms solve the same "stable key→node" problem with genuinely different trade-offs, and the ring is not always the right one. Each gets the full treatment below: mechanism, worked example, pros, cons, complexity, and when to choose it.

7.1Rendezvous Hashing (Highest Random Weight, HRW)#

Mechanism: For a given key, compute weight = hash(key, node) for every node, and pick the node with the highest weight. To place a key, you score it against all N nodes and take the max.

7.2Jump Consistent Hash (Google, 2014)#

Mechanism: A tiny, elegant algorithm (a few lines of code, no ring, no memory) that maps a key + a bucket count N to a bucket in [0, N), with the guarantee that increasing N from N to N+1 moves only ~1/(N+1) of keys.

7.3Maglev Hashing (Google, 2016) — even distribution and minimal disruption#

Rendezvous and jump hash each optimize one thing. Maglev hashing was designed when Google built its software load balancer (File 01 §9.1) and discovered that the ring's distribution quality was not good enough for their purpose, while jump hash's node-numbering constraint made it unusable for a fleet where any machine can fail. They needed both near-perfect balance and minimal remapping, and they were willing to spend memory to get it.

The problem it solves, stated concretely. A Maglev load balancer tier has many machines, all announcing the same VIP, with routers spreading flows across them by ECMP (File 01 §2.2). Two properties are non-negotiable. First, every Maglev machine must independently choose the same backend for the same flow, because a router can move a flow to a different Maglev box mid-connection and the connection must not break — so the mapping has to be a pure function of the key and the backend set, with no shared state. Second, the distribution across backends must be very even, because a load balancer that sends 15% of traffic to a backend sized for 10% has wasted capacity across the whole fleet. The ring with vnodes gives you the first but only approximates the second.

The mechanism — build a lookup table, not a ring. Maglev precomputes a flat array (the lookup table) of size M, where M is a prime number substantially larger than the number of backends — 65,537 is the common choice. Each entry holds a backend. At request time the algorithm is a single array index: backend = table[hash(key) mod M]. That is an O(1) lookup with one memory access, which is why it can run at line rate.

The interesting part is how the table is filled, and it is a beautifully simple idea: **give every backend a deterministic preference ordering over all M positions, then let the backends take turns claiming their most-preferred position that is still free.**

For each backend i, two hashes of its name produce an offset and a skip:

   offset = h1(name_i) mod M
   skip   = (h2(name_i) mod (M-1)) + 1        # 1..M-1, never 0
   permutation[i][j] = (offset + j * skip) mod M      for j = 0, 1, 2, ...

Because M is prime and skip is never zero, stepping by skip repeatedly visits every position in the table exactly once before repeating — that is the reason M must be prime, and it guarantees each backend has a complete preference list over all positions.

Then the fill is a round-robin draft:

   repeat:
     for each backend i in turn:
        advance through permutation[i] until you find an EMPTY position
        claim it for backend i
     until the table is full

Worked example. Take M = 7 (tiny, for illustration) and three backends A, B, C with:

   round 1:  A claims 3        table: [ _, _, _, A, _, _, _ ]
             B claims 0        table: [ B, _, _, A, _, _, _ ]
             C wants 3 (taken) -> 4   table: [ B, _, _, A, C, _, _ ]
   round 2:  A wants 3(taken),0(taken) -> 4? taken -> 1
                               table: [ B, A, _, A, C, _, _ ]
             B wants 0(taken) -> 2     table: [ B, A, B, A, C, _, _ ]
             C wants 3,4 taken -> 5    table: [ B, A, B, A, C, C, _ ]
   round 3:  A -> 5? taken -> 2? taken -> 6
                               table: [ B, A, B, A, C, C, A ]   FULL

Final counts: A holds 3 positions, B holds 2, C holds 2 — out of 7. With a real M of 65,537 and dozens of backends, the counts differ by at most one entry, which is as even as a discrete assignment can possibly be. That is Maglev's headline property.

What happens when a backend fails. You rebuild the table without it. Because each surviving backend's preference list is unchanged and the draft is deterministic, most positions are re-awarded to the same backend as before; only the failed backend's positions, plus a small amount of downstream churn from the shifted draft order, change hands. Google's paper reports disruption close to the theoretical minimum for practical table sizes — not exactly minimal like the ring, but very near it, and the balance is far better.

7.4Multi-Probe Consistent Hashing — the ring's balance without the vnodes#

The problem it attacks. Virtual nodes (§5) fix the ring's load skew, but they cost memory: 200 vnodes per node across 100 nodes means 20,000 ring entries to store, sort, and search, and every membership change touches all of them. Multi-probe consistent hashing (MPCH) asks whether the same balance can be bought with compute at lookup time instead of memory at rest.

The mechanism — move the multiplicity from the nodes to the key. Place each node on the ring exactly once (no vnodes at all). Then, to look up a key, hash it k different ways to get k distinct points on the ring, find the nearest node clockwise from each, and choose the node that was closest to any of its probes. In effect, instead of scattering each node into many positions so that keys are likely to find a nearby one, you scatter each key into many positions so it is likely to find a nearby node. The published result is that with roughly k = 21 probes you get peak-to-average load within a few percent — comparable to a vnode ring — while the ring itself stores only N entries.

Worked intuition. With one node per ring position and a single probe, a key lands in whatever arc it falls into, and arcs vary wildly in size — that is exactly the skew of §5. With 21 probes, the key gets 21 independent chances, and the minimum distance across 21 draws is far more tightly concentrated than a single draw. The variance reduction is the same statistical effect that makes power-of-two-choices work in load balancing (File 01 §4.8) — a small number of extra samples collapses the tail dramatically.

7.5Anchor Hashing — minimal disruption with full removal support#

The gap it fills. Look back at jump hash (§7.2): perfect balance, near-zero memory, O(ln N) lookup — and one crippling restriction, that you may only remove the last bucket. That makes it useless for a cluster where any machine can die. AnchorHash (published 2019) was designed to keep jump hash's efficiency while supporting removal of any bucket, and later re-addition, which is what real clusters actually do.

The mechanism, at the level that matters. Anchor hashing maintains a fixed-size "anchor" array of size A, representing the largest number of buckets the cluster will ever have, of which some subset is currently working and the rest are removed. The state is a handful of small integer arrays recording, for each removed bucket, how the keyspace it owned was redistributed and — crucially — enough information to undo that redistribution if the bucket comes back. A lookup hashes the key into the anchor space; if it lands on a working bucket it stops, and if it lands on a removed one it follows the recorded redistribution to a working bucket, repeating until it terminates. The expected number of hops is small and depends on the ratio of working to total buckets.

The properties it achieves: minimal disruption (removing a bucket moves only that bucket's keys; adding one back restores exactly the previous mapping), perfect balance across working buckets, O(1) expected lookup time when most buckets are working, and memory O(A) integers — kilobytes, not the ring's ring-array-times-vnodes.

7.6When to Use Which#

The decision rule in prose, because the table compresses too much. Start from the ring with virtual nodes: it is what every major system runs, it handles arbitrary churn, it supports replicas and weighting naturally, and its O(log V) lookup is fast enough for almost everything. Deviate only for a specific reason. Deviate to rendezvous when N is small and you want no ring bookkeeping at all — the O(N) lookup is irrelevant at N = 10. Deviate to jump hash only when your buckets are genuinely numbered and you only ever append — a fixed set of storage shards, not a cluster with failures. Deviate to Maglev when lookup speed and distribution quality are the product, as in an L4 load-balancer tier, and you can absorb a table rebuild on membership change. Deviate to multi-probe when the memory of vnodes is the binding constraint. Deviate to AnchorHash when you want removal support with jump-hash economics and can bound the cluster's maximum size.

The property that actually separates them, if you remember one thing: they differ in where they spend to buy stability. The ring spends memory (vnodes). Rendezvous spends lookup CPU (score every node). Multi-probe spends lookup CPU (probe k times). Maglev spends memory and rebuild time (the table). Jump hash and AnchorHash spend flexibility (constrained bucket identity). There is no free version.

8Fixed Partitions & Hash Slots — The Scheme Constantly Confused With Consistent Hashing#

Here is the single most useful correction in this entire file, and the one that separates a candidate who has read about consistent hashing from one who has operated it: several of the most famous systems that everybody describes as "using consistent hashing" do not have a ring at all. Redis Cluster has no ring. Elasticsearch has no ring. Kafka has no ring. DynamoDB's user-visible model has no ring. What they have instead is a fixed partition scheme, also called a hash slot scheme, and it solves the same problem — "changing the number of servers must not remap every key" — by a completely different and, in many ways, simpler trick.

If you say "Redis Cluster uses consistent hashing" in an interview, a good interviewer will ask you to describe the ring, and there isn't one. If instead you say "Redis Cluster uses a fixed slot map — 16,384 slots — which achieves the same stability property as consistent hashing through explicit indirection rather than through ring geometry," you have signalled that you understand the category, not just the famous algorithm. That is the whole point of this section.

8.1The plain definition, and the one idea it rests on#

A fixed-partition (hash slot) scheme is a key-placement design in which you choose, once and forever, at cluster creation time, a fixed number of buckets — call them slots, partitions, or shards depending on the product — and you hash every key into one of those buckets with plain modulo arithmetic. Then, separately, you maintain a small explicit table saying which physical node currently owns which slot.

Written as two lines of pseudocode, the entire scheme is:

slot = hash(key) mod S          # S is FIXED FOREVER. Never changes.
node = slot_map[slot]           # a small, explicitly managed lookup table

That first line is the same mod N arithmetic that Section 2 spent thousands of words condemning as catastrophic. It is not catastrophic here for exactly one reason: **S never changes.** The catastrophe in Section 2 came from N — the node count — appearing inside the modulo. Node counts change constantly: machines die, you autoscale, you replace hardware. Slot counts do not change, because you declared the slot count up front and you never touch it again. The modulo is safe precisely because its divisor is a constant of the universe rather than a property of your fleet.

Sub-Concept: Indirection. Indirection means solving a problem by inserting an intermediate name between the thing that refers and the thing referred to, so that the binding between them can change without the referrer changing. A postal forwarding address is indirection: your correspondents keep writing to the same address (the stable name) and the post office holds the mutable mapping to where you actually live. A pointer in C is indirection; a DNS name is indirection (clients hold api.example.com while the A record's IP changes underneath); a Kubernetes Service ClusterIP is indirection over a churning set of pod IPs. The famous aphorism, attributed to Butler Lampson, is that "all problems in computer science can be solved by another level of indirection." Here the intermediate name is the slot number. The key is bound to a slot permanently; the slot is bound to a node mutably. Every hard part of the problem has been pushed into the second, mutable binding — which is now small enough to manage explicitly, by hand if you like.

Hold this: **consistent hashing makes the key→node mapping computable and stable. Fixed slots make the key→node mapping stable by making it a lookup.** Both get stability; they get it from opposite directions. The ring gets it from geometry with no stored table. Slots get it from a stored table with no geometry.

8.2Why it exists — the physical reality that motivated it#

Recall the "why" driving all of this (Rule 6 reasoning, and Section 1.2): when a key moves between machines, bytes move over a network or a cache entry is lost and must be recomputed from a database. Both are expensive; at scale both are catastrophic when they happen to most keys at once. Any scheme that avoids mass remapping is therefore acceptable. Consistent hashing is one such scheme. Fixed slots are another. They were invented independently and for a very concrete engineering reason: the ring's implicitness is inconvenient when you want an operator, a tool, or a script to see and control exactly where data lives.

On a ring, the answer to "which node owns key X?" is computed by every participant from the ring state. That is elegant, and it is why decentralized systems like Dynamo love it. But it means:

The fixed-slot scheme answers all four. Slots have names — they are integers. The layout is a table you can print. "Move slot 4,231 from A to B" is a concrete, scriptable, resumable operation with an obvious progress indicator. And a client only has to agree with the server on the first line of the pseudocode (hash(key) mod S), which is trivial to reimplement identically, because the second line is data it is handed rather than logic it must reproduce.

The price, which we will quantify in §8.9, is that somebody has to hold, agree on, and distribute that table.

8.3Where it sits — the layer, and who computes what#

In a fixed-slot system there are three distinct participants, and confusing their roles is where most misunderstanding lives:

The slot number itself is not usually on the wire as a protocol field; it is derived. But it is the unit of every administrative operation, of every rebalance plan, and of every error message the system will ever hand you about routing.

8.4The mechanism, step by step, with a full worked example#

Take Redis Cluster's real parameters. S = 16384. The hash function is CRC16 of the key (specifically the CCITT variant Redis calls crc16), and the slot is CRC16(key) mod 16384. CRC16 is a cyclic redundancy check — an error-detecting checksum designed for data-transmission integrity, not for cryptography — which is fine here for the reasons §0.5 gave: we need cheap, fast, and well-mixed, not unforgeable. It produces a 16-bit value, 0–65535, and the modulo folds it into 0–16383.

You can compute this yourself against a live server with CLUSTER KEYSLOT <key>; for example CLUSTER KEYSLOT foo returns 12182.

Step 1 — Initial cluster: four nodes. When you create the cluster, redis-cli --cluster create assigns contiguous slot ranges evenly:

Now place five keys. Each key's slot is fixed by CRC16 and will never change for the life of the data:

(The middle column is the CRC16 computation; the slot values shown are what that computation yields. foo→12182 is the canonical documented example you can verify on any Redis Cluster.)

Step 2 — Add a fifth node, E. You want five nodes to share 16,384 slots evenly: 16384 / 5 = 3276.8, so the target is four nodes with 3,277 slots and one with 3,276 (or any near-equal split; the exact remainder distribution is an implementation detail). The rebalancer's job is to move 16384 − (4 × 3277) = 3276 slots onto E, taken 819 from each existing node (819 × 4 = 3276).

A natural plan — and roughly what redis-cli --cluster rebalance produces — moves the top of each existing range:

Step 3 — Re-check the five keys. This is the payoff, and it is worth staring at:

Three observations, each of which is an interview-grade point:

Complexity. Client-side lookup is O(1) time — one hash computation plus one array index into a 16,384-entry table — and O(S) memory for the map, which at 16,384 entries is a couple of tens of kilobytes per client at most (Redis clients typically store it as ranges, which compresses to O(number of nodes)). Contrast the ring's O(log V) lookup (binary search over V = vnodes × nodes sorted tokens) and O(V) memory. Rebalancing cost is O(keys in the moved slots) network transfer either way; the difference is bookkeeping, not bytes.

8.5Choosing the slot count — the parameter that cannot be taken back#

S is the one number you must get right at design time, so understand both directions of failure.

**If S is too small: the hard ceiling is that you can never have more nodes than slots.** With S = 16, a 20-node cluster is impossible; four nodes would own nothing. Long before that hard wall you hit the soft wall of granularity: balance can only be as even as 1/S allows. With S = 64 and 10 nodes, each node owns 6 or 7 slots — a node with 7 carries 16.7% more than a node with 6, and you cannot do better, because a slot is indivisible. With S = 16384 and 10 nodes, each owns 1,638 or 1,639 slots, a spread of 0.06%. The rule of thumb that follows: **S should exceed your maximum plausible node count by at least one, preferably two, orders of magnitude.** If you might one day run 100 nodes, S in the thousands to tens of thousands is right; S = 128 is a trap you will hit in year three.

**If S is too large: every slot is a row somebody must track. The costs are real and they show up in three places. First, metadata size in the routing table** — a slot-to-node array of S entries per client, per node, per tool. Second, gossip/heartbeat bandwidth: Redis nodes exchange, in every heartbeat packet, a bitmap of the slots they claim — one bit per slot. Third, per-slot fixed overheads inside the implementation (index structures, per-partition files, per-partition memory).

Redis's choice of 16,384 is a beautifully documented example of exactly this trade-off, and it makes a great interview anecdote. Antirez (Salvatore Sanfilippo) explained the number publicly: a 16,384-bit slot bitmap is 2 KB per heartbeat message, whereas the "obvious" 65,536 would be 8 KB — and because every node heartbeats every other node periodically, that difference multiplies by N² across the cluster and becomes a meaningful chunk of a small cluster's bandwidth. Since Redis Cluster was never designed to exceed roughly 1,000 nodes, 16,384 slots gives about 16 slots per node at the extreme — still enough granularity — at a quarter of the gossip cost. The general principle: **S is bounded below by your node count and balance requirements, and bounded above by whatever per-slot cost your control plane pays.**

Note also that in Elasticsearch the per-partition overhead is enormous compared to Redis: each shard is a complete Lucene index with its own segment files, its own memory for term dictionaries, and its own file handles and threads. So Elasticsearch's advice runs the opposite direction from Redis's — use few shards, sized in the tens of gigabytes each — because there S is expensive per unit. **The lesson is that "pick a big S" is not universal advice; it is advice calibrated to how cheap a partition is in the specific system.**

Failure mode and how you diagnose it: the symptom of S chosen too small is a cluster you cannot balance — redis-cli --cluster check reports a stubborn imbalance, or per-node memory/QPS graphs show a persistent 15–30% spread that never improves no matter how you rebalance. The symptom of S too large in Elasticsearch is the classic oversharding picture: heap pressure and slow cluster-state updates with a cluster holding tens of thousands of tiny shards, visible in GET _cat/shards and in master-node CPU spent publishing cluster state.

8.6Distributing the slot map — MOVED, ASK, and metadata refresh#

The slot map is mutable shared state, and distributed mutable shared state is always where the difficulty is. Every fixed-slot system needs an answer to: how does a client find out the map changed, and what happens to requests sent using a stale map?

Redis Cluster's answer is redirection, and it is elegant because it needs no push mechanism at all. A client keeps a cached slot map (fetched with CLUSTER SLOTS or the newer CLUSTER SHARDS, which returns each node's owned ranges). It routes optimistically. If it is wrong, the node it contacted tells it so:

**MOVED 3311 10.0.0.5:6379 — "Slot 3311 does not belong to me any more; it now permanently belongs to that node." The client must retry against the named node** and update its cached map — the well-behaved client refreshes the whole map, because if one slot moved, others probably did too. A MOVED is a stable, permanent statement of ownership.

**ASK 3311 10.0.0.5:6379** — "Slot 3311 is in the middle of being migrated. This particular key is already over there. Go ask that node — but do not update your map, because I still own the slot in general." The client must send the special one-shot command **ASKING** immediately before its retry, because the destination node does not yet officially own the slot and will otherwise reply MOVED right back, producing an infinite loop. ASKING is a one-command permission slip meaning "I was redirected here; serve this even though you don't own the slot yet."

The MOVED/ASK distinction exists entirely to make slot migration non-blocking and online. During a migration of slot 3311, the source node is marked MIGRATING and the destination IMPORTING. A request for a key still on the source is served normally; a request for a key already migrated gets ASK. When the migration finishes, CLUSTER SETSLOT ... NODE flips ownership and everyone starts getting MOVED instead. No client ever blocks, and no client ever needs to be told in advance.

The failure mode to know: a client library that treats ASK like MOVED will poison its map with a slot→node binding that is wrong for every key except the one it was redirected for, causing a redirection storm — every subsequent request to that slot takes two round trips instead of one, and latency roughly doubles for that slot's traffic until the map is refreshed. Conversely, a client that ignores MOVED's "update your map" implication takes an extra hop on every request forever. You diagnose both the same way: watch the ratio of redirections to commands (Redis exposes it in INFO and most client libraries count it); a healthy steady-state cluster should be at essentially zero.

Kafka's answer is metadata requests. A Kafka producer or consumer issues a Metadata request to any broker and receives, for each topic, the list of partitions and which broker is the leader for each. It caches this and refreshes it every metadata.max.age.ms (default 5 minutes) or immediately upon receiving a NOT_LEADER_OR_FOLLOWER error — which is Kafka's structural equivalent of MOVED. Same pattern: optimistic client-side routing over a cached map, with an authoritative error that triggers a refresh.

Elasticsearch's answer is that any node will route for you. Every node holds the full cluster state (published by the elected master), so a request to any node is forwarded internally to the right shard. This is the "smart server, dumb client" end of the spectrum: one extra internal hop in exchange for clients that need to know nothing. Elasticsearch clients optionally do their own routing to skip that hop, but they are not required to.

DynamoDB's answer is to hide the map entirely behind an HTTP request router that Amazon operates. You never see partitions; you see throttling errors when one is hot. That is the managed-service trade: zero routing complexity, zero routing visibility.

8.7Hash tags and co-location — forcing related keys into one slot#

A fixed-slot scheme scatters keys uniformly, which is exactly what you want for balance and exactly what you don't want when an operation must touch several keys at once. Redis has no cross-node transactions; a MSET, an MGET, a SUNIONSTORE, a MULTI/EXEC transaction, or a Lua script declaring multiple KEYS can only execute if every key involved lives in the same slot — because the command executes inside one node's single-threaded event loop and that node must own all the data. Otherwise the server replies:

**CROSSSLOT Keys in request don't hash to the same slot**

The escape hatch is the hash tag. The rule is precise: if the key contains a {, and there is a } after it, and there is at least one character between them, then the slot is computed from **only the substring between the first { and the first } following it**. Otherwise the whole key is hashed.

Worked example:

With the tagged form, MGET {user42}:profile {user42}:cart works, a MULTI/EXEC over user 42's keys works, and a Lua script can atomically read and write all of user 42's state. Without it, all of those fail with CROSSSLOT.

The trade-off, stated the way Rule 5 demands: the benefit is atomicity and single-round-trip multi-key access for related data. The cost is that you have deliberately destroyed the uniformity of the hash for those keys — every key belonging to user 42 is now pinned to one slot and therefore one node, so a single enormous or extremely hot entity concentrates all of its load on one machine. This is the same hot-key problem §6.2 described, now created on purpose. The mitigation is to choose tag granularity carefully: tag by tenant_id in a SaaS system where tenants are roughly comparable in size, but never tag by something with an unbounded whale (tagging by country puts all of a large country on one node forever). If you cannot avoid a whale, give it its own tag suffix bucket ({user42:shard3}) and accept that operations no longer span the whole entity.

Note the deep symmetry: hash tags are the fixed-slot world's version of what File 04 calls a co-location or partition-key prefix — the same idea as Citus co-locating tables sharded on the same column, and the same idea as a Cassandra partition key grouping clustering rows onto one node. Every partitioned system eventually needs a way to say "keep these together," because a system that can only scatter cannot support any multi-item operation.

8.8When the fixed count is genuinely immutable — Elasticsearch primary shards#

Redis Cluster's 16,384 slots are fixed, but the node count is freely variable, so nothing is really lost. Elasticsearch is the case where fixedness bites, and it is the best teaching example of the whole trade-off.

An Elasticsearch index is split into a number of primary shards chosen with "number_of_shards" at index-creation time, and a document is routed by:

shard = murmur3_hash(_routing) % number_of_primary_shards

where _routing defaults to the document's _id. **number_of_shards cannot be changed for the life of the index** — and unlike Redis, there is no slot-map indirection to save you, because here the partition is the unit of storage: shard 7 is a physical Lucene index on disk. Changing the divisor changes which shard every document belongs to, which would require moving essentially all documents and rewriting every shard's inverted index.

Contrast "number_of_replicas", which can be changed at any time (PUT /my-index/_settings {"number_of_replicas": 2}), because adding a replica copies a shard wholesale without changing any document's shard assignment. Primaries are structural; replicas are elastic. That distinction is the crisp answer to a very common interview question.

The consequences you must be able to state:

Kafka is the instructive counter-example within the same family. Kafka's partition count can be increased (kafka-topics --alter --partitions 24) — but doing so does remap keys, because the default partitioner computes partition = murmur2(key) % numPartitions with no indirection layer. Increase from 12 to 24 partitions and roughly half of all keys land in a different partition from then on. Since Kafka's only ordering guarantee is ordering within a partition, and a key's messages have now been split across two partitions, per-key ordering is permanently broken across the change boundary — old messages for key k sit in partition 5 while new ones go to partition 17, and two different consumers may process them concurrently in the wrong order. You also cannot decrease partitions at all, because Kafka would have to decide what to do with the existing data and its offsets. The operational rule that follows: over-provision Kafka partitions at topic creation, since adding them later is a correctness event and not merely a data-movement event. This is the cleanest illustration in the whole file of why the slot-map indirection matters: Redis has it and can rebalance freely; Kafka omits it and pays with a semantic break.

8.9The direct comparison — ring versus fixed slots#

Now the comparison the section exists for. Both schemes achieve ~1/N movement. They differ on everything else.

8.10The decision rule — say this out loud in an interview#

9Replication, Failure & Cluster Operations on the Ring#

Sections 4 through 7 taught placement: given a key and a set of nodes, which node owns it. That is the algorithm. This section is the system — what you actually have to build and operate once the ring is holding real data on real machines that really fail. Section 6.1 sketched replica placement in a paragraph; here we do it properly, because every one of these mechanisms is a standard interview question and every one of them has a specific bug that catches people.

Throughout, keep the physical reality in view (Rule 6): a node failure is not an abstraction. It is a machine whose disk is now unreachable, whose share of the read traffic has to go somewhere in the next few hundred milliseconds, and whose data — if you had only one copy — is gone. At a thousand machines, with commodity hardware, something is always failing. The ring must degrade gracefully under continuous failure, not merely tolerate an occasional one.

9.1Choosing the N replicas — the walk to N distinct physical nodes#

The definition. A replica is an additional complete copy of a piece of data held on a different machine, so that the data survives, and stays readable, when one machine dies. The replication factor, written N in the Dynamo paper and RF in Cassandra, is how many total copies exist — RF=3 means three machines each hold the full value, not one machine holding it and two holding fragments. (Fragment-based schemes are erasure coding, a different trade covered in File 09.)

Why it exists. A single copy makes durability a function of one disk's annualized failure rate — a few percent per year per drive, which across a thousand drives means you lose data continuously. It also makes availability a function of one machine's uptime, including planned reboots. Replication converts "the data is gone when one machine dies" into "the data is gone when RF specific machines die simultaneously," which at RF=3 and independent failures is astronomically unlikely.

Where it sits on the ring. The ring already answers "who owns this key" — the first node clockwise. Replication extends that answer from a single node to an ordered list of nodes, produced by continuing the clockwise walk. The rule is:

Walk clockwise from hash(key). Collect nodes as you encounter their tokens. Skip any token belonging to a physical node already in your list. Stop when you have N distinct physical nodes.

That "distinct physical" clause is the entire subtlety, and §9.2 shows what happens without it.

Step-by-step worked example. A 32-bit ring (positions 0 … 4,294,967,295), but we will use small numbers for legibility — imagine the ring runs 0–1000. Three physical machines, each with three virtual nodes (§5):

Key order:5512 hashes to position 75. Walk clockwise with N = 3:

So order:5512 lives on A (the coordinator / primary, the first node clockwise), and on B and C. All three hold the identical value.

Complexity. With V total tokens on the ring, finding the first token clockwise is O(log V) by binary search over the sorted token array. Then you scan forward until you have N distinct physical nodes. In the worst case — one machine holding a long run of consecutive tokens — that scan is O(V), but in expectation, with tokens well shuffled, you examine O(N × vnodes_per_node / total_nodes) extra tokens, which is a small constant. Practical implementations precompute the full replica list per token range once at ring-change time and cache it, making steady-state lookup O(log V) with O(V × N) memory. Cassandra does exactly this; it is why a ring change triggers a recomputation pass rather than being free.

9.2The bug when you forget "distinct physical" — and how to spot it#

This is the classic implementation error, and interviewers ask about it because it is silent: the system appears to work perfectly until the day it loses your data.

Take the same ring, but implement the walk naively — collect the next N tokens rather than the next N distinct machines:

Replica list: [A, A, B].

Everything looks healthy. There are three entries in the preference list. Writes at quorum (W=2, meaning two of the three must acknowledge — File 08) succeed easily, because two of the three "replicas" are the same machine and always agree with each other instantly. Monitoring shows RF=3. Repair tools report consistency. You have, in reality, two physical copies, not three — and worse, one machine holds two of the three votes.

Now machine A dies:

How you detect it before it hurts you. Assert the invariant explicitly in code and in tests: for every token range, len(set(physical_node(r) for r in replicas)) == RF. Operationally, run a property test over a randomized ring — generate 10,000 random rings and 100,000 random keys and assert distinctness — because the bug is a low-probability geometric coincidence that a hand-written unit test with three tidy tokens will never produce. In Cassandra terms, the equivalent operational check is nodetool getendpoints <keyspace> <table> <key>, which prints the endpoints for a key; seeing the same IP twice is the smoking gun.

Tie-back: the ring gives you replica placement almost for free, but "almost" is doing work. The vnodes of §5 that fixed your load skew are exactly what creates this hazard, so the two features must be implemented together and tested together.

9.3Rack, zone and region awareness — changing the walk to respect failure domains#

The definition. A failure domain (or fault domain) is a set of machines that can plausibly fail together because they share some physical dependency. The standard nesting, smallest to largest:

Why the plain walk is not enough. The clockwise walk of §9.1 picks nodes by hash position, which is deliberately random and therefore completely blind to physical topology. With 9 machines in 3 racks, a replica list of [A, B, C] has a perfectly ordinary chance of being three machines in the same rack. One PDU trip then takes all three copies simultaneously. Your RF=3 bought you nothing at all against the single most common correlated failure in a datacenter. The whole point of replication is that failures be independent; ignoring topology makes them correlated.

The mechanism — the topology-aware walk. Extend the rule from §9.1 with a second constraint:

Walk clockwise. Skip a node if its physical machine is already chosen (§9.1) or if its failure domain already contributed a replica, until every domain has one; only then allow a second replica per domain.

Cassandra implements this as **NetworkTopologyStrategy**, configured per keyspace as {'class': 'NetworkTopologyStrategy', 'dc1': 3, 'dc2': 3} — read as "keep 3 replicas in datacenter dc1 and 3 in dc2," and within each datacenter, place those 3 in distinct racks if enough racks exist. Which rack and datacenter a node belongs to is declared by a snitch — Cassandra's name for the component that tells the cluster the topology (GossipingPropertyFileSnitch reads cassandra-rackdc.properties on each node; Ec2Snitch derives region and AZ from the EC2 metadata service automatically).

Worked example. Nine nodes, three racks, RF=3, single datacenter:

A key hashing to position 95:

Now any single rack failure costs exactly one replica out of three, so R=2 reads and W=2 writes still succeed. That is the entire purpose of the exercise: convert a correlated failure into an independent one.

The trade-offs, honestly. First, balance degrades: forcing replicas across racks means the replica load per node is no longer the clean function of ring arcs it was, and if your racks are unequal in size (4 machines in r1, 2 in r2), the small rack's machines carry disproportionate replica load — the standard mitigation is to keep failure domains equal in capacity, which is a datacenter-design requirement flowing back from a hashing decision. Second, latency rises: a write with W=2 across AZs now pays inter-AZ round trips (about 1 ms) instead of intra-rack (about 0.1 ms), and across regions it pays tens of milliseconds — this is the PACELC "else latency" trade of File 19. Third, it can be unsatisfiable: with RF=3 and only 2 racks, some domain must hold 2 replicas; the strategy degrades gracefully rather than failing, but you must know it did. Diagnose with nodetool status, which prints each node's rack, and by checking that endpoint sets for sample keys span distinct racks.

9.4The preference list — Dynamo's name for the whole thing#

Dynamo formalizes all of the above into one concept. The preference list for a key is the ordered list of nodes responsible for that key — and, crucially, it is **longer than N.** Dynamo's paper is explicit: the list contains more than N nodes so that, when some of the top N are down, the coordinator can walk further and still find N healthy nodes to talk to.

For our §9.1 example the preference list for order:5512 might be [A, B, C, (then continuing clockwise) A′…] — in a real cluster of many machines it extends to perhaps N + 3 entries. The first N are the top-N preference list and hold the data in normal operation; the remainder are standbys that step in during failures (§9.7's hinted handoff is exactly what a standby does).

Two properties make this concept load-bearing:

Tie-back: the preference list is where consistent hashing hands off to consensus. Which nodes are involved is the ring's answer (this file). How many must respond and what happens when they disagree is the quorum question (R + W > N, sloppy quorums, vector clocks, read repair, Merkle-tree anti-entropy) — that is File 08's territory, and you should say so explicitly in an interview rather than blurring the two. Likewise, the relationship "partition = ring range, replica = additional copy of a range" is the same distinction File 04 §6 draws between partitioning and replication; the ring is simply a way to define the partitions.

9.5What actually happens when a node fails — and the cascade you must quantify#

The immediate mechanism. A node dies. Some detector notices (§6.4's gossip, or a health check from File 01). Its tokens are marked down. Every other participant, recomputing the walk, now skips those tokens. Concretely:

The load arithmetic — do this out loud in an interview.

Case 1: no virtual nodes, one token per machine. A 10-node ring, each owning ~10% of the keyspace, each running at, say, 60% CPU. Node D dies. Its entire arc passes to exactly one machine: its clockwise successor, E. E now owns 20% of the keyspace — its load doubles, from 60% to 120% of a single machine's capacity. It cannot serve 120%. Latency climbs, queues build, timeouts start.

Case 2: the cascade. E, overloaded, becomes unresponsive to health checks — or genuinely crashes on memory pressure from its request queue. E is now marked down. E's arc — which is now D's arc plus E's own, 20% of the keyspace — passes to F. F was at 60%; it is now asked for 60% + 60% + 60% = 180%. F dies faster than E did. Then G inherits 30% of the keyspace, and so on. Each successive node fails sooner than the last, because it inherits strictly more. This is a cascading failure, and the ring's naive geometry actively accelerates it: the failure walks around the ring in one direction, consuming the cluster. Real outages of this exact shape have taken down entire tiers in minutes.

Case 3: with virtual nodes. Now each of the 10 machines has 256 tokens, so 2,560 tokens are interleaved around the ring. When D dies, its 256 arcs each pass to whichever node happens to follow — and with tokens well shuffled, those successors are spread roughly uniformly over the other 9 machines. Each survivor inherits about 1/9 of D's load: 10% / 9 ≈ 1.1% of the keyspace each, so a node at 60% goes to roughly 66.7%, not 120%. Nobody is overloaded, nobody cascades. This is the strongest argument for virtual nodes and it is a better answer than "they improve balance," because it explains a failure mode rather than a statistic.

The two mitigations you must name alongside vnodes. First, headroom: run the cluster at a utilization such that utilization × N / (N−1) < 1 even in the worst tolerated failure count. For a 10-node cluster tolerating 2 simultaneous failures, u × 10/8 < 1 means keeping steady-state utilization below 80% — and in practice below 60–70%, since capacity is not perfectly fungible. Second, load shedding and bounded loads: §6.3's Consistent Hashing with Bounded Loads caps what any node will accept, so an overloaded successor sheds overflow to the next node with capacity rather than dying. Bounded loads is precisely a cascade-prevention mechanism, and framing it that way (rather than as a hot-key fix) is the sophisticated reading.

9.6Temporary versus permanent failure — the distinction that governs everything operational#

This is the operational heart of the section, and it is where naive designs go wrong.

The problem. A failure detector cannot tell you why a node stopped answering. A node that is down for 90 seconds because someone applied a kernel patch, and a node that is down forever because its motherboard died, look completely identical on the wire: no response to heartbeats. Yet the correct response differs enormously.

How real systems resolve it: automatic failover, manual membership change. Dynamo's design is explicit that node addition and removal are explicit administrative actions, precisely because the system cannot infer intent from silence. Cassandra follows the same philosophy:

The parameter that hurts people: that 3-hour hint window is a policy statement about how long you expect a reboot to take. Set it too short and ordinary maintenance forces expensive repairs; set it too long and a node down for two days accumulates hints that may exceed the peers' disk. There is a second bound for exactly this reason — Cassandra caps total hint storage (max_hints_size_per_host, default 0 = unlimited in some versions, otherwise a byte cap) and will drop hints rather than fill a disk. Dropped hints are silent divergence, repaired only by anti-entropy, which is why "run repair within gc_grace_seconds" is Cassandra's most repeated operational rule.

Say this in an interview: "Failover is automatic and instant because the replicas already exist; re-replication is manual because the system cannot distinguish a reboot from a dead motherboard, and guessing wrong costs a full data migration." That single sentence demonstrates you have operated one of these systems.

9.7Hinted handoff — parking writes for a node that is away#

Plain definition. Hinted handoff is a mechanism in which, when a write cannot be delivered to one of the key's proper replicas because that node is unreachable, some other node accepts and stores the write on its behalf, tagged with a hint — a note recording which node the data was really for — and replays it to that node when it comes back.

Why it exists. Without it, a write during a node's downtime leaves that node permanently stale for that key until a full repair runs, and — worse — if you demanded that all N replicas acknowledge, the write would fail entirely, meaning a single node reboot makes your system unavailable for writes to a third of your keyspace. Dynamo's entire design goal was to be always writeable (a shopping cart addition must never be rejected — a rejected "add to cart" is directly lost revenue). Hinted handoff is how you keep accepting writes without giving up on the missing replica.

Where it sits. It operates at the coordinator, in the write path, after the preference list is computed and before the quorum is counted. It is the mechanism that makes a sloppy quorum possible — a quorum counted over the first N healthy nodes in the (longer-than-N) preference list rather than the first N nodes outright.

Step by step, with concrete values. RF=3, W=2. Key cart:99 has preference list [A, B, C, D, …]. Node B is down.

Complexity and cost. Storage on the holder is O(writes to the down node's ranges × downtime) — for a node taking 5,000 writes/sec of 1 KB values, down for one hour, that is roughly 18 GB of hints, spread across its peers. Replay is a burst of exactly that volume, which is why implementations throttle replay (Cassandra: hinted_handoff_throttle_in_kb, default 1024 KB/s per delivery thread, with max_hints_delivery_threads) — otherwise the returning node, which is also busy catching up and rebuilding caches, gets hit with an hour of writes compressed into a few minutes and falls over again immediately. That specific "node comes back and is instantly killed by its own hint replay" failure is a real, named production pathology, and throttling is the answer.

The failure modes — this is the part people forget.

Tie-back: hinted handoff exists because the ring told us exactly which nodes should have a key and we found one of them missing. It is only expressible because the preference list is deterministic and longer than N — the ring's ordering is what gives the coordinator somewhere well-defined to park the write.

9.8Bootstrapping a new node — and why it hurts exactly the wrong machines#

What bootstrapping is. When a new machine joins the ring, it picks (or is assigned) its tokens, announces them, and then must acquire the data for the ranges it now owns. Until it has that data, it cannot serve reads for those ranges without returning wrong answers, so it joins in a distinct state — Cassandra calls it UJ (up/joining) — in which it receives writes but does not serve reads.

The mechanism, step by step.

The problem, stated precisely. The peers a bootstrapping node must stream from are, by construction, exactly the nodes that currently own — and are currently serving live traffic for — the ranges being handed over. You cannot stream from an idle machine, because idle machines do not have the data. So the act of adding capacity temporarily removes capacity: the very nodes that were hottest enough to justify the expansion now additionally spend disk I/O, page cache, and network egress on streaming. Adding a node to a cluster that is already at 90% utilization can push it over. This is the most counter-intuitive operational fact about elastic clusters and a superb interview point: **scaling out is a load increase before it is a load decrease.**

The mitigations, each with its cost.

9.9Decommissioning a node cleanly#

Removal is the mirror image, and the distinction between the two commands is a favourite interview question.

**nodetool decommission — for a node that is alive.** Run on the departing node itself. The node announces it is leaving (state UL, up/leaving), computes which nodes will own its ranges once its tokens are removed, and streams its data out to those new owners itself, then shuts down and removes its tokens from the ring. Because the departing node is the one doing the sending, the data comes from a machine you are about to stop caring about — the surviving nodes only pay receive cost. This is the clean path and the one to use for planned capacity reduction, hardware refresh, or instance-type changes.

**nodetool removenode <host-id> — for a node that is already dead.** Run from any surviving node. The dead machine obviously cannot stream anything, so the new owners must obtain the data from the other surviving replicas of those ranges. That means the recovery load falls on live, traffic-serving machines — the §9.8 problem again. It is strictly more disruptive than decommission, which is the operational argument for decommissioning nodes before they die when you have the choice (e.g. draining a node showing SMART disk errors rather than waiting for it to fail).

**nodetool assassinate is the last resort: it forcibly evicts a node from gossip without moving any data at all**, used when a node is stuck in a bad state and removenode will not complete. It leaves ranges under-replicated and must be followed by a full repair. Naming this hierarchy — decommission (best) → removenode (acceptable) → assassinate (emergency, repair afterwards) — is a strong operational signal.

The invariant that governs all three: at no point may a range drop below the replication factor's worth of live, complete copies without you knowing it. Every one of these operations is designed to move data before removing ownership, and every shortcut that reverses that order trades durability for speed.

9.10Avoiding the rebalancing thundering herd#

What a thundering herd is. A thundering herd is any pattern in which a large number of actors respond to a single event simultaneously, and the synchronized response is itself more damaging than the original event. The name comes from the classic OS problem where every process blocked on one socket wakes when a connection arrives, all contend, and all but one go back to sleep having burned CPU. In distributed systems the shape recurs constantly: every cache client missing at once and stampeding the database (File 02's cache stampede), every client retrying at the same instant after an outage, every node deciding to rebalance at the same moment.

How the ring produces one. A ring rebalance is triggered by a membership change event that every node observes at roughly the same time via gossip. If every node independently reacts by immediately streaming data, you get O(N) simultaneous large transfers. Concretely, in a network partition that briefly makes 15 nodes of a 60-node cluster look dead, and a system configured to auto-rebalance, all 15 ranges are re-replicated at once — tens of terabytes of streaming — and then the partition heals and it all has to be undone. The rebalance saturates the same network whose hiccup caused the event, which makes more nodes look dead, which triggers more rebalancing. The remediation becomes the outage.

The mitigations, and why each works.

Tie-back to the whole file: consistent hashing's headline property is that only ~1/N of the data must move on a membership change. §9 has been about the fact that *1/N of a petabyte is still a hundred terabytes*, moved by machines that are simultaneously serving your users. The algorithm bounds how much moves; operations decide how much it hurts. A candidate who can explain the 1/N property and then immediately explain throttling, serialization, and the temporary-vs-permanent distinction is demonstrating the difference between knowing the algorithm and being able to run it.

10Pros, Cons & Trade-offs#

10.1Benefits#

10.2Costs & Trade-offs#

11Interview Diagnostic Framework (Symptom → Solution)#

12Real Implementations & Product Landscape#

Everything up to here has been mechanism. This section is the catalogue: the actual systems, proxies, and libraries that implement key-to-node placement in production, what each one is, which scheme from §4–§8 it actually uses, what it is genuinely good at, where it falls down, and — the part that decides real designs — which one you should reach for in which situation.

This section matters more for consistent hashing than for most topics, because the name is applied loosely. "Uses consistent hashing" is said of systems using a token ring (Cassandra), of systems using a fixed slot map with no ring at all (Redis Cluster, §8), of systems using a completely different algorithm that merely satisfies the same property (Guava's consistentHash, which is jump hash), and of systems using a permutation-table variant (Maglev). Knowing which is which is the whole game.

The landscape splits into five families.

12.1Family 1 — Ring-based storage systems (the real token ring)#

These genuinely place nodes on a hash ring and walk clockwise, exactly as §4 described.

Amazon Dynamo — the origin. Dynamo is not a product you can buy; it is an internal Amazon key-value store described in the 2007 SOSP paper "Dynamo: Amazon's Highly Available Key-value Store" by DeCandia et al., and it is the single most influential distributed-systems paper of its decade. It was built for one specific and very concrete business reason: Amazon measured that an unavailable shopping cart is lost revenue, and had concluded that during their busiest periods a system that occasionally rejected writes was unacceptable while a system that occasionally returned a slightly stale cart was fine. That requirement — always writeable — dictated everything: no master (a master is a thing that can be unavailable), so leaderless replication; no consensus on the write path, so quorums plus conflict resolution after the fact (R + W > N, vector clocks, and application-level merge — a shopping cart merges by union, which is why the example is a cart and not a bank balance); and a placement scheme every node could compute alone, which is consistent hashing with virtual nodes. Dynamo introduced, or popularized, essentially every term in §9: the preference list, sloppy quorums, hinted handoff, Merkle-tree anti-entropy repair, and gossip-based membership. Best at: teaching you the vocabulary — every engineer at this level is expected to know this paper. Limits: the eventual-consistency model pushes real work onto the application (you must write merge logic), and Amazon themselves moved the user-facing product, DynamoDB, to a different, managed, fixed-partition model (§12.2). The distinction to state crisply: Dynamo the paper is a leaderless ring; DynamoDB the AWS service is not the same system and does not expose a ring.

Apache Cassandra. Originally built at Facebook (2008, by Avinash Lakshman — who had also worked on Dynamo — and Prashant Malik) for inbox search, then open-sourced and adopted by Apache. Its architecture is the famous hybrid: Dynamo's ring, replication, and gossip on the distribution side; Google Bigtable's column-family data model and LSM-tree storage engine (memtable + SSTables + compaction, File 11) on the storage side. Every node is identical — there is no master, no config server, no router tier — and a client can contact any node, which then acts as coordinator for the request.

The ring specifics you should know by name: each node is assigned one or more tokens, which are positions on a 64-bit ring (the default partitioner, **Murmur3Partitioner**, produces signed 64-bit values, so the ring spans −2^63 to 2^63 − 1). The number of tokens per node is the **num_tokens** setting, and its history is a genuinely useful story:

Best at: write-heavy, always-on, multi-datacenter workloads where you can model the schema per query. Limits: no joins, no ad-hoc queries, eventual consistency by default, and the operational burden of repair and compaction tuning is real. Concrete scale: clusters of many hundreds of nodes and petabytes are routine (Apple, Netflix, Discord — §13.2).

ScyllaDB. A ground-up C++ rewrite of Cassandra (2015, by the team behind the KVM hypervisor), wire-compatible with Cassandra's CQL protocol and using the same token ring. Its distinguishing mechanism is the Seastar framework's shard-per-core architecture: instead of threads sharing memory with locks, Scylla pins one thread per CPU core, gives each core its own memory and its own subset of the node's token ranges, and passes messages between cores rather than sharing state. It also does its own I/O scheduling and cache management rather than relying on the OS page cache and a JVM heap — which removes garbage-collection pauses, historically Cassandra's worst source of tail latency. The consequence for this file: Scylla effectively has two levels of consistent hashing — the ring distributes to nodes, and within a node a second hash distributes to cores. Best at: the same workloads as Cassandra at substantially fewer nodes and much better p99 latency. Limits: a smaller ecosystem, a smaller pool of experienced operators, and feature lag behind Cassandra on some newer capabilities; the open-source/enterprise split affects which features you get.

Riak. Basho's Erlang implementation of the Dynamo paper (2009), and the most literal one — it named its concepts after the paper's. Its architectural quirk is important precisely because it blurs the §8 boundary: Riak's ring is divided into a fixed number of partitions, set by ring_creation_size (default 64, always a power of two), and those partitions — Riak calls each one a vnode, in a slightly different sense than Cassandra's — are then claimed by physical nodes. So Riak is genuinely a hybrid: a consistent-hashing ring whose granularity is a fixed partition count, which behaves operationally much more like §8's slot map than like Cassandra's continuous ring. ring_creation_size cannot be changed after cluster creation, and it caps the node count exactly as S does in §8.5 — the standard guidance was at least 10 partitions per node. Best at: demonstrating Dynamo's ideas faithfully, with genuinely excellent operational simplicity (riak-admin cluster join). Limits: Basho went bankrupt in 2017; the project continues under community stewardship (riak_kv) but you are choosing a system with a thin commercial ecosystem. Learn it as a reference implementation, not as a default choice for new work.

OpenStack Swift. The object storage service of OpenStack (originally Rackspace Cloud Files), and a superb example of the same hybrid, with the clearest terminology of any of them. Swift calls its placement structure "the ring" but it is built on a **fixed partition count of exactly 2^part_power — the partition power** is chosen at ring-build time, and a typical value like part_power = 18 yields 262,144 partitions. Objects hash to a partition (MD5 of the object path, taking the high bits), and a ring file — literally a compressed data file distributed to every proxy and storage server — maps each partition to a list of devices. The ring builder supports device weights (a 12 TB drive gets twice the partitions of a 6 TB drive) and zones/regions as failure domains, honouring "as unique as possible" placement, which is §9.3's rack awareness expressed as a first-class ring-building constraint. Increasing partition power was historically impossible and is now supported only through a careful, multi-step, offline-ish procedure. Best at: cheap, very large, durable object storage on commodity disks with explicit operator control over placement. Limits: eventual consistency on listings, an ops-heavy deployment, and the partition-power decision being effectively permanent. The teaching value: Swift proves the point of §8 — a thing can be called a ring and still be a fixed partition table with an explicit, file-distributed map.

12.2Family 2 — Fixed-slot systems (the §8 contrast)#

Redis Cluster. The horizontally-scaled mode of Redis, introduced in Redis 3.0 (2015). 16,384 hash slots, CRC16(key) mod 16384, no ring (§8.4). Nodes gossip over the cluster bus (client port + 10000) and each holds the full slot map; clients cache it and are corrected by **MOVED and ASK (§8.6); related keys are grouped with hash tags (§8.7). Replication is primary/replica per shard**, not a preference-list walk: each slot range is owned by one primary with k replicas, and failover is an election among the primaries when a majority agree a primary is unreachable. Best at: microsecond-latency in-memory workloads that exceed one machine's RAM, with an operational model humans can hold in their heads. Limits, and they are sharp: multi-key operations only within a slot; no cross-slot transactions; a client library that mishandles redirections silently doubles latency; and because replication is primary/replica rather than leaderless, a shard whose primary and all replicas die takes its slots offline entirely (CLUSTER DOWN), unlike a Dynamo ring where any surviving replica keeps serving. Note the alternative deployment: Redis Sentinel is not sharding — it is automated failover for a single primary/replica group, and confusing Sentinel with Cluster is a common interview stumble. Managed variants (AWS ElastiCache, MemoryDB, Redis Enterprise) wrap the same slot model; Redis Enterprise adds a proxy tier so clients need not understand slots at all.

Elasticsearch / OpenSearch. Fixed primary shard count set at index creation and immutable (§8.8), routing by murmur3(_routing) % number_of_shards, with the cluster state held by an elected master and every node able to route. Best at full-text search and log analytics at scale; the limit that shapes every design is the immutability of the shard count and the resulting reliance on time-based indices, aliases, data streams and ILM. OpenSearch is the AWS-led fork after Elastic's 2021 licence change; architecturally identical for these purposes, and worth knowing exists because the licensing question comes up.

Apache Kafka. Topics are divided into a fixed partition count, and the default producer partitioner computes murmur2(key) % numPartitions. Consumer groups assign partitions to members; ordering is guaranteed within a partition only. As §8.8 explained, Kafka is the family member without the slot-map indirection, so increasing the partition count genuinely remaps keys and breaks per-key ordering across the change — over-provision at creation. Best at: high-throughput durable event streaming with replay (File 07). Limits: partition count is effectively one-way (can increase, never decrease), and partition count also bounds consumer parallelism — you cannot have more useful consumers in a group than partitions.

Amazon DynamoDB. Despite the name, the managed service does not expose the Dynamo paper's ring. Items are placed into partitions by hashing the partition key; AWS's control plane splits partitions automatically as they grow past roughly 10 GB or exceed throughput limits, and an internal request router holds the map. The limits that decide designs are per-partition: roughly 3,000 read capacity units and 1,000 write capacity units per second per partition. Adaptive capacity now shifts throughput toward hot partitions and can isolate a hot item onto its own partition, which softens but does not remove hot-key pain. Best at: genuinely zero-operations key-value at any scale with predictable single-digit-millisecond latency. Limits: you cannot see or control placement at all, the hot-partition failure appears to you only as throttling errors, and the data model (single-table design, no joins) has a real learning cost.

12.3Family 3 — Load balancers and proxies (hashing for affinity, not storage)#

Here the "keys" are requests and the "nodes" are backends, and the goal is affinity: send the same session, user, or URL to the same backend so its local cache stays warm — while surviving backend changes without reshuffling everyone. This is the same algorithm serving a different purpose, and File 01 §9 is the full catalogue of the products themselves; this is the hashing angle.

**Envoy — ring_hash and maglev.** Envoy (Lyft, 2016; CNCF) offers both algorithms as cluster load-balancing policies, and choosing between them is a real design question.

HAProxy. balance hash <expression> (or balance uri, balance hdr(...), balance source) combined with **hash-type consistent** switches from modulo-based mapping to a consistent-hashing ring; hash-type map-based is the plain-modulo alternative, and knowing that HAProxy exposes both is a nice illustration of §2's whole argument in one config directive. HAProxy also implements bounded loads (§6.3) via **hash-balance-factor**: set it to, say, 150 and no server may receive more than 1.5× the average number of requests — over-limit requests spill to the next server. HAProxy is, as far as mainstream proxies go, the most accessible production implementation of consistent hashing with bounded loads, and naming that directive in an interview is a strong signal. Best at: operational control and observability of the hashing (its stats page shows per-server session counts, so imbalance is immediately visible). Limits: as a proxy it is not a data store; affinity here is cache warmth, not ownership.

NGINX. The directive is **hash <key> [consistent];** inside an upstream block — for example hash $request_uri consistent;. Without the consistent keyword, NGINX uses plain hash mod N over the server list, with exactly §2's remapping behaviour when a server is added or removed; with it, NGINX uses a ketama-compatible ring (§12.4), which is deliberate: it means an NGINX cache tier and a memcached client library can be made to agree on placement. There is also the older ip_hash directive (hashes the first three octets of an IPv4 client address, which is a crude affinity mechanism with the NAT problem noted above). Best at: simple, extremely stable cache-affinity routing in front of an origin. Limits: open-source NGINX picks up upstream changes by config reload, so backend churn is a config-management problem rather than an API one (File 01 §9.2).

gRPC. gRPC's built-in **ring_hash** load-balancing policy is client-side (there is no proxy) and is configured via xDS or a service config, with min_ring_size / max_ring_size mirroring Envoy's knobs — unsurprising, since gRPC's xDS support is deliberately Envoy-compatible. It matters for a reason specific to gRPC: because gRPC multiplexes many RPCs over one long-lived HTTP/2 connection, connection-level balancing does nothing, so balancing must happen per-RPC in the client — and if you need affinity per-RPC (routing all RPCs for a given user to the same backend shard), ring_hash over a request attribute is the mechanism.

Cross-reference: the products themselves — what NGINX, HAProxy, and Envoy are, their config-reload models, their TLS stories, and when to choose each — are covered in File 01 §9. Do not re-derive that here; do know that the hashing policy is a per-cluster/per-upstream setting inside whichever you chose.

12.4Family 4 — Client libraries and algorithms as code#

Sometimes there is no cluster software at all: the client library does the hashing, and the servers are dumb. This is how memcached works and it is the oldest deployment of consistent hashing in the wild.

memcached and ketama. memcached is a plain in-memory cache server (Brad Fitzpatrick, 2003, for LiveJournal) that knows nothing about clustering — it is a single-node key-value cache with no replication, no persistence, and no awareness of other memcached instances. All distribution logic lives in the client. In the beginning clients used hash(key) mod N over the server list, and the consequence was §2's catastrophe made real: removing one of ten cache servers cold-missed roughly 90% of keys and stampeded the database.

libketama (Richard Jones, Last.fm, 2007) fixed this by implementing consistent hashing in the client. Its specifics have become a de-facto standard, and the details matter because they are the compatibility contract:

What "ketama-compatible" means, and why the compatibility is the point. A large web application typically has several languages talking to the same memcached fleet — PHP page rendering, a Python batch job, a Java service, an NGINX cache tier. If the PHP client and the Java client compute different servers for the same key, then each language has its own private cache: the Java service writes user:42 to server 3, the PHP front-end reads user:42 from server 7 and misses, and you silently get an L-fold reduction in effective cache hit rate plus a correctness hazard when one language invalidates a key on the wrong server. "Ketama-compatible" means a client reproduces libketama's exact MD5, exact point-generation, exact server-key string format, and exact ring construction, so that every client in every language independently computes the same answer. This is why spymemcached (Java) documents a KetamaConnectionFactory, why pylibmc and python-memcached expose ketama settings, why php-memcached has Memcached::DISTRIBUTION_CONSISTENT with OPT_LIBKETAMA_COMPATIBLE, and why NGINX's hash ... consistent explicitly advertises ketama compatibility. The failure mode to name in an interview: "mixed clients with different hashing produce partitioned caches, and it presents as an unexplained low hit rate rather than as an error" — nothing crashes, you just quietly pay for a cache you are not getting. Diagnose by hashing a sample of keys with each client and comparing the chosen servers.

**Guava's Hashing.consistentHash(long input, int buckets). Google's Guava library for Java exposes this under the name "consistent hash", and it is not a ring — it is jump consistent hash (§7.2). Everything jump hash's design implies therefore applies, and the method's own documentation says so: it returns a bucket index in [0, buckets)**, and its stability guarantee is only about growing or shrinking the bucket count at the end. Consequences you must internalize before using it:

So it is excellent for "I have a fixed, ordered set of shards that I grow by appending" — sharding a work queue across k workers, assigning users to a growing set of storage buckets — and wrong for a churny cache fleet. The interview trap is precisely the name: a candidate who says "I'll use Guava's consistent hashing to handle node failures" has picked the one variant that handles arbitrary node failure worst.

Other libraries worth naming. In Go: stathat/consistent and serialx/hashring are ketama-style rings; **buraksezer/consistent implements consistent hashing with bounded loads** (§6.3) and is the usual reference when someone wants CHWBL in Go; dgryski/go-* hosts reference implementations of jump, rendezvous, maglev, and multi-probe for benchmarking. In Java, beyond Guava, the memcached clients (spymemcached, xmemcached) carry ketama, and Cassandra's own driver contains a TokenAwarePolicy that computes the Murmur3 token client-side so the driver sends the request directly to a replica rather than to a random coordinator that would then forward it — saving one network hop and demonstrating that "the client knows the ring" is a performance feature, not just a routing detail. In Python, uhashring is the maintained ketama-compatible ring, while **pymemcache notably ships RendezvousHash as its default distribution** — a small but nice illustration of §7.1's argument that for a handful of servers, rendezvous's simplicity beats a ring.

12.5Family 5 — CDN and cache-affinity at the edge#

Maglev in Google's L4 tier. Maglev (NSDI 2016) is Google's software network load balancer, and it is the reason the algorithm in §7 exists. The problem it had to solve is worth restating because it is not the storage problem: many independent Maglev machines announce the same VIP via BGP and receive flows spread across them by the routers' ECMP hashing. ECMP (Equal-Cost Multi-Path) is a router feature that splits traffic across equal-cost next hops by hashing the packet's 5-tuple; when the set of Maglev machines changes — one is drained for a kernel upgrade — the routers rehash and a live TCP connection can land on a different Maglev machine mid-flow. That new machine has never seen the connection and holds no state for it. It must nevertheless choose the same backend, or the connection resets. Hence the requirement: machines that have never communicated must independently agree on backend selection for the same flow, with minimal disruption when backends change, and with near-perfect balance. Maglev hashing (a fixed-size prime lookup table filled by per-backend permutations, §7) delivers exactly that, at O(1) lookup — which matters when you are forwarding millions of packets per second per box. You consume this today as GCP's Network Load Balancer; the open equivalents are Facebook's Katran and Cloudflare's Unimog, both built on XDP/eBPF (File 01 §9.1). The transferable lesson: consistent hashing is not only about data placement; it is the standard tool for making independent, stateless routers agree without coordination, and that "agree without talking" property is what makes stateless horizontal scaling of a routing tier possible at all.

Cache-affinity routing at CDN edges. A CDN PoP (point of presence — a rack of cache servers in a city, File 05) has many cache machines and must decide which one holds a given object. Hashing the URL consistently across the PoP's machines gives each object one home, so it is fetched from origin once and served from RAM thereafter, and losing one machine cold-misses only 1/N of objects instead of all of them. Two refinements matter in practice. First, bounded loads (§6.3) are near-mandatory at the edge, because CDN traffic is intensely Zipfian — a handful of URLs (a breaking-news video, a game patch) can be a large fraction of all requests, and pure consistent hashing pins each of those to exactly one machine; this is precisely the deployment where Google published CHWBL and where Vimeo publicly reported adopting it (in their HAProxy-fronted video delivery, using hash-balance-factor) after single-video hot spots overloaded individual caches. Second, tiered caching — a mid-tier cache between edge and origin, itself consistently hashed — reduces origin fan-out when many PoPs miss the same object simultaneously. Say this in an interview: "At the edge I'd hash on the URL for cache affinity, but with bounded loads, because content popularity is Zipfian and pure consistent hashing has no answer for a single hot object (§6.2) — plus a local LRU in front so the hot object is served without ever consulting the hash."

12.6Comparison table#

12.7Decision rules — plain English#

12.8Anti-recommendations — the common wrong picks#

13Real-World Engineering Scenarios#

13.1Amazon DynamoDB / Dynamo — The Canonical Ring#

Amazon's Dynamo paper (2007) popularized consistent hashing in production:

13.2Discord / Cassandra — Ring-Based Message Storage#

Building on File 04's Discord example: Cassandra distributes partitions across nodes using consistent hashing over a token ring.

13.3CDN / Load Balancer Request Routing (Maglev, cache affinity)#

14Interview Gotchas & Failure Modes#

14.1Classic Questions#

14.2Failure Modes & Mitigations#

15Whiteboard Cheat Sheet#

   PROBLEM: hash(key) mod N  -> change N -> ~(N-1)/N of keys remap -> cache avalanche / mass data move

   SOLUTION: hash space as a RING (0 .. 2^32-1, wraps). Hash NODES onto ring too.
             Key owner = first node CLOCKWISE from hash(key).

                 0
              A•     •key3->A(wrap)
           •         •
       key2        key1
         •            •
          C•        •B        remove B -> only B's arc moves to C. Others untouched. (~1/N)
             •    •           add D between B,C -> D steals only C's slice.

   VIRTUAL NODES: each physical node = many ring points (100-256).
       -> even arcs (kills skew) ; dead node's load spreads over ALL peers (no cascade)
       -> more vnodes for bigger servers = weighting
   REPLICATION: owner + next R-1 DISTINCT physical nodes clockwise (Dynamo preference list)
   DOES NOT FIX: a single hot key (one key -> one node). Salt/replicate it separately.
   VARIANTS: Rendezvous/HRW (O(N), weighted, small N) | Jump hash (tiny, append-only scaling)
             Bounded-load (overflow to next node if owner at capacity cap)
   USED IN: Dynamo/Cassandra/Riak, memcached ketama, Maglev LB, CDN cache routing

One-sentence summary for an interviewer:

"Consistent hashing places both keys and nodes on a hash ring and assigns each key to the next node clockwise, so adding/removing a node remaps only ~1/N of keys instead of nearly all (as mod N would) — preventing cache avalanches and enabling elastic, leaderless clusters; you must use virtual nodes (100–256 per node) to keep the load even and to spread a failed node's load across all peers, you extend it to replication via the clockwise preference list, and you remember it does not solve single hot keys."

End of File 06. Next → File 07: Message Queues & Event Streaming (pub/sub, Kafka mechanics, delivery guarantees, backpressure).