---
title: "Consistent Hashing: Why Adding a Cache Server Remaps 75% of Keys"
date: "2026-09-21"
video_id: "7688056579656060174"
tiktok_url: "https://www.tiktok.com/@arjay_mccandless/video/7688056579656060174"
creator: "@arjay_mccandless"
category: "Coding"
tags: ["consistent hashing", "caching", "system design", "virtual nodes", "redis cluster"]
excerpt: "Going from 3 to 4 cache servers under hash % N moves exactly 75% of keys. How consistent hashing fixes it, why virtual nodes matter and what Redis really uses."
---
Consistent hashing places cache servers and keys on the same hash ring so that adding a server moves only about 1/N of keys instead of most of them. A TikTok from @arjay_mccandless explains this well, and its 75% figure for going from 3 to 4 servers under `hash(key) % N` is exact. The ring it draws, with one point per server, is a simplified version of the published algorithm and loses the load-balance guarantee.

## Why does hash % N break when you add a server?

With `server = hash(key) % N`, changing N changes the answer for most keys. A key stays put across a resize from 3 to 4 servers only when `h mod 3 == h mod 4`. Both residues are fixed by `h mod 12`, and they agree only at h = 0, 1 and 2. That keeps 3 of 12 keys and moves 9 of 12, which is exactly 75%.

In general, going from n to n+1 servers keeps 1/(n+1) of keys, so n/(n+1) move. Each moved key is a cache miss that falls through to the database, which is how the video's database ends up overloaded.

## How does consistent hashing work?

Every possible hash value sits on a ring, from 0 to 2³² − 1. Each server is hashed onto the ring, and each key is hashed onto it too. A key belongs to the first server found moving clockwise from its position.

When you add a server, only the keys in the arc it takes over move. Everything else stays on the same server. Envoy's [load balancer docs](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers) state the result: "With the ring partitioned appropriately, the addition or removal of one host from a set of N hosts will affect only 1/N requests." In the video, adding a fourth server moves 3 of 12 keys, which is 1/4.

## Why do you need virtual nodes?

The video places one point per server. The [original 1997 paper](https://people.csail.mit.edu/karger/Papers/web.pdf) by Karger, Lehman, Leighton, Levine, Lewin and Panigrahy does not. Section 4.2 says "we will need k log(C) points for each bucket for some constant k," and the paper's balance theorem is proved from that replication. With one point per server, the arcs are whatever a few random draws produce.

Amazon's [Dynamo paper](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) (SOSP 2007) names the problem: "the random position assignment of each node on the ring leads to non-uniform data and load distribution." Its fix is "virtual nodes," where each node gets multiple points on the ring. Dynamo lists three benefits: a failed node's load spreads evenly, a new node takes roughly equal load from every other node, and the number of virtual nodes can match each machine's capacity.

Google's [Maglev paper](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf) (NSDI '16) measured the imbalance. With 1000 backends, "Karger and Rendezvous require backends to be overprovisioned by 29.7% and 49.5% respectively."

The 1/N figure is also an average. With one point per server, a new server that lands just behind another takes almost no keys, and one that lands far away takes too many. What the paper guarantees unconditionally is monotonicity: when a server is added, "No items move between old buckets."

## Do Redis and memcached use consistent hashing?

Mostly not in the way the video draws.

- **Redis Cluster** has no ring. The [cluster spec](https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/) splits the key space into 16384 slots with `HASH_SLOT = CRC16(key) mod 16384`. The modulus never changes, and nodes take ownership of slots that migrate during resharding.
- **memcached** leaves placement to the client. [libmemcached](https://awesomized.github.io/libmemcached/libmemcached/memcached_behavior.html) defaults to `MEMCACHED_DISTRIBUTION_MODULA`, "hash of the key modulo number of servers." Consistent (ketama) hashing is an opt-in flag, so the video's broken setup is the library default.
- **Cassandra** uses a token ring with virtual nodes. Its [docs](https://cassandra.apache.org/doc/stable/cassandra/managing/operating/topo_changes.html) still say the default is 256, but the [trunk cassandra.yaml](https://raw.githubusercontent.com/apache/cassandra/trunk/conf/cassandra.yaml) sets `num_tokens: 16`.
- **Envoy** ring hash matches the diagram directly, and its docs note it "is also commonly known as 'Ketama' hashing."
- **DynamoDB** documentation says only that an "internal hash function" picks the partition. It does not mention a ring.

## Consistent hashing vs jump hash, Maglev and rendezvous hashing

- **Jump consistent hash** ([Lamping and Veach, 2014](https://arxiv.org/abs/1406.2294)) "requires no storage, is faster, and does a better job of evenly dividing the key space." It requires sequentially numbered buckets, which suits storage shards better than cache servers that come and go by name.
- **Maglev hashing** gets "almost perfect load balancing." Envoy reports it is less stable when hosts change: "approximately double the keys will move." For a cache in front of a database, that doubles the miss spike.
- **Rendezvous hashing** (highest random weight) is not newer. Thaler and Ravishankar [published it](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/HRW98.pdf) in IEEE/ACM Transactions on Networking in February 1998. It scores every server for every key, so it has no placement variance but costs O(n) per lookup.

## What does it cost to switch to consistent hashing?

The video, titled "How to add a cache server safely," leaves out two costs.

First, moving from `hash(key) % 3` to a ring changes the owner of nearly every key once, because the two mappings share no structure. It is worth paying once, but not during peak traffic.

Second, 1/N is still a real miss spike. On a four-server ring, about 25% of requests hit a cold new server and fall through to the database. Bring the new node in gradually, or put request coalescing in front of the database. The Karger paper pairs consistent hashing with "random cache trees" and a section on "Swamping" for this reason.

## Bottom line

The video's 75% is exact, and consistent hashing does cut the remap to about 1/N. Real implementations need many virtual nodes per server to balance load, and Redis Cluster uses fixed hash slots instead of a ring. Expect a one-time remap when you switch and a cold-cache spike every time you add a server.

## Sources

- [Consistent Hashing and Random Trees (Karger et al., 1997)](https://people.csail.mit.edu/karger/Papers/web.pdf) - the original paper
- [ACM entry for the STOC '97 paper](https://dl.acm.org/doi/10.1145/258533.258660) - citation
- [Dynamo (SOSP 2007)](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) - virtual nodes
- [Maglev paper](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf) - overprovisioning measurements
- [Maglev at USENIX NSDI '16](https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud) - venue and authors
- [Jump consistent hash (2014)](https://arxiv.org/abs/1406.2294) - Lamping and Veach
- [Rendezvous hashing (1998)](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/HRW98.pdf) - Thaler and Ravishankar
- [Redis cluster specification](https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/) - 16384 hash slots
- [memcached ConfiguringClient wiki](https://github.com/memcached/memcached/wiki/ConfiguringClient) - client-side distribution
- [libmemcached behaviour docs](https://awesomized.github.io/libmemcached/libmemcached/memcached_behavior.html) - modulo default, ketama opt-in
- [Cassandra topology changes docs](https://cassandra.apache.org/doc/stable/cassandra/managing/operating/topo_changes.html) - num_tokens and token ranges
- [Cassandra trunk cassandra.yaml](https://raw.githubusercontent.com/apache/cassandra/trunk/conf/cassandra.yaml) - current num_tokens default
- [Envoy load balancers](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers) - ring hash and Maglev
- [DynamoDB partitions](https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html) - partition key hashing
- [Devmaxx on the App Store](https://apps.apple.com/us/app/devmaxx/id6758278144) - the creator's system design app, advertised at the end of the video


## Video description and verification notes

**This is a 79-second (1:19) vertical clip at 1080x1920, H.265 video with AAC audio in a 4,919,406-byte MP4, posted 2026-09-21 at 18:26:33 UTC by @arjay_mccandless, whose TikTok channel nickname is "Arjay McCandless". At capture time on 2026-10-05 it showed 44,500 views, 3,430 likes, 27 comments, 68 reposts and 1,084 saves. The audio track is listed as "original sound" by Arjay McCandless, meaning there is no licensed music bed. I read 22 of the 40 extracted frames (2-second intervals) and all 325 words of the transcript. The clip opens on a living room with a wall-mounted Sony TV showing a live cache dashboard headed "ARJAY MCCANDLESS" with nav items "Tools", "Sponsor" and a blue "Newsletter" button; its stat tiles read "HIT RATE 31%", "REQS / SEC 245", "DB OPS / SEC 176" in red, and "CACHE FILL 2 / 3", above a chart labeled "THROUGHPUT · LAST 30 SECONDS" with a legend of "hits/s", "misses/s", "db ops/s" and "writes/s", a bar panel "ACCESS BY KEY · LAST 5 SECONDS / 24 keys · hottest highlighted", a table "CACHE CONTENTS · HOTTEST KEYS" with columns "KEY VALUE HITS TTL LEFT" and rows for "key:5" and "key:3" both at "42s", and a right-hand "LOAD" panel with sliders reading "Read rate 241 req/s", "20 req/s" and "TTL 42 s". A wood-burned sign reading "Claire & Arjay McCandless Est. 9-12-26" sits on the credenza next to a copy of "Designing Data-Intensive Applications" and a Monopoly box. Burned-in captions run throughout, starting "DUDE THIS IS REALLY BAD". The TV then switches to a whiteboard diagram labeled "hash(key) % 3" with a Chrome logo fanning into three boxes labeled "Cache" and dashed lines converging on a cylinder labeled "Database", which becomes an all-red "hash(key) % 4" diagram with four "Cache" boxes under the captions "SHOULD ADD ANOTHER CACHE", "TO HELP HANDLE SOME", "TRAFFIC IS EVENLY DISTRIBUTED" and "AND OUR DATABASE GOT OVERLOADED". A full-screen animation follows: a code bar reading "server = hash(key) % 4" with the 3 crossfading to a highlighted 4, four boxes "Cache 0", "Cache 1", "Cache 2" and "Cache 3 NEW", twelve tiles "h = 0" through "h = 11" redistributing between the columns, a "Database load 22%" meter, and counters that tick from "7 / 12 keys remapped" under the caption "ABOUT 75% OF YOUR KEYS" up to "9 / 12 keys remapped" while "cache hit rate" falls from "90%" to "25%" and the database bar turns red at "OVERLOADED 100%" under the caption "CAUSING THE OVERLOAD OKAY". The second half shows a code bar "server = hash(key) % N" under "WITH CONSISTENT HASHING", then a titled slide "Consistent hashing" with a ring drawn from "0" labeled "Every possible hash / 0 → 2³² − 1", servers placed as "Hash each server / onto the same ring" with a legend of 'hash("cache-A") → 0x1555…', 'hash("cache-B") → 0x6AAA…' and 'hash("cache-C") → 0xC000…', a lookup walkthrough of 'hash("user:42") / lands at a point on the ring' with a pipeline "request GET user:42 → hash 0x3C71…" and a green clockwise arc landing on Cache B, then "Add Cache D / one more point on the ring" with 'hash("cache-D") → 0x9B05…', "Only one arc moves / keys between B and D → D" and "9 of 12 stay put / same servers as before", all above a comparison panel headed "Keys remapped when you add a server" with "hash % N" at "9 / 12" in red and "hash ring" at "3 / 12" in green. The clip closes on b-roll in a kitchen with the caption "YOU CAN STUDY CONSISTENT HASHING", then screen recordings of an iOS app showing a "CACHING" module, a "CORE CONCEPTS" page titled "Where to put the cache" marked "2 of 5", and a quiz question "Which cache write strategy keeps the cache and database in lockstep at the cost of slower writes?" with "Write-through" selected over "Write-around", "Write-behind" and "Read-through", overlaid with an App Store card reading "Devmaxx / Master System Design / Open".**

## The 75% figure in the caption is exact, not approximate, and the archived auto-transcript in this repository renders it wrong

The counter in the animation settles on "9 / 12 keys remapped" and the burned-in caption at roughly 36 seconds reads "ABOUT 75% OF YOUR KEYS". The Whisper transcript stored alongside this video renders the same line as "Going from 3 to 4 servers can remap about 80% of your keys." The video description written by the creator says "going from 3 servers to 4 can remap roughly 75% of your keys". Two of the three sources say 75%, so the 80% is almost certainly a speech-recognition artifact in the archive rather than something the creator said. I could not resolve the audio myself, so I am reporting the discrepancy rather than asserting which syllable was spoken.

The underlying arithmetic resolves it either way, and it is exact. A key stays on the same server across a resize from 3 to 4 only when `h mod 3 == h mod 4`. By the Chinese remainder theorem both residues are determined by `h mod 12`, and the two agree only at h = 0, 1 and 2. That is 3 of 12 keys retained and 9 of 12 moved, which is 75.0% and not an approximation. The animation's own 12-tile grid is this exact calculation rendered as boxes. Generalizing, a resize from n to n+1 servers retains exactly 1/(n+1) of keys, so the remap fraction is n/(n+1). The clip's visual is right and the word "about" in the caption is doing no work.

Worth flagging for contrast: the [memcached project's own client configuration wiki](https://github.com/memcached/memcached/wiki/ConfiguringClient) states that "With a normal hashing function, adding an eleventh server may cause 40%+ of your keys to suddenly point to different servers than normal." By the same formula the real figure for 10 to 11 servers is 1 − 1/11, which is 90.9%. The TikTok's number is more accurate than the number in the memcached wiki.

## Karger's 1997 paper requires k log(C) points per server, and the clip's ring places exactly one

The clip draws Cache A at 0x1555…, Cache B at 0x6AAA…, Cache C at 0xC000… and Cache D at 0x9B05…, one ring position each. That is the textbook cartoon, and the [original paper](https://people.csail.mit.edu/karger/Papers/web.pdf) does not define the algorithm that way. Karger, Lehman, Leighton, Levine, Lewin and Panigrahy published "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" at [STOC '97](https://dl.acm.org/doi/10.1145/258533.258660) in May 1997. Section 4.2 of the paper states plainly: "For reasons that will become apparent, we actually need to have more than one point in the unit interval associated with each bucket. Assuming that the number of buckets in the range is always less than C, we will need k log(C) points for each bucket for some constant k. The easiest way to view this is that each bucket is replicated k log(C) times, and then rB maps each replicated bucket randomly."

The replication is load-bearing, not decorative. Theorem 4.1's balance guarantee, "with high probability the fraction of items mapped to each bucket is O(1/|V|)", is proved from the fact that "when k log(C) points are randomly mapped to the unit interval, each bucket is with high probability responsible for no more than a O(1/|V|) fraction of the interval." With one point per server, that proof does not apply and the arcs are whatever three uniform draws happen to produce.

The [Dynamo paper](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf) by DeCandia and co-authors at Amazon, published at SOSP 2007, names the failure directly: "The basic consistent hashing algorithm presents some challenges. First, the random position assignment of each node on the ring leads to non-uniform data and load distribution. Second, the basic algorithm is oblivious to the heterogeneity in the performance of nodes." Dynamo's fix is the same as Karger's: "instead of mapping a node to a single point in the circle, each node gets assigned to multiple points in the ring. To this end, Dynamo uses the concept of 'virtual nodes'." The paper lists three advantages, quoted in full: load from a failed node "is evenly dispersed across the remaining available nodes"; a newly added node "accepts a roughly equivalent amount of load from each of the other available nodes"; and "The number of virtual nodes that a node is responsible can decided based on its capacity, accounting for heterogeneity in the physical infrastructure."

The size of the imbalance has been measured. The [Maglev paper](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf) by Eisenbud and co-authors at Google, published at the 13th USENIX Symposium on Networked Systems Design and Implementation ([NSDI '16](https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud)), reports in section 5.3 that with 1000 backends and a 65537-entry lookup table, "Karger and Rendezvous require backends to be overprovisioned by 29.7% and 49.5% respectively to accommodate the imbalanced traffic." The clip's ring is the Karger case with the replication removed, which is worse than that measurement, not better. Anyone who implements what the whiteboard shows gets correctness and loses the balance property.

## The 3-of-12 number on screen is the K/n bound, and it is a mean rather than a guarantee

The clip never names a bound. Its comparison panel just reads "hash % N 9 / 12" against "hash ring 3 / 12". That 3 of 12 is 25%, which is 1/4, which is 1 over the new server count. Expressed generally, adding the nth server moves K/n keys in expectation, where K is the total key count. [Envoy's own load balancer documentation](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers) states the same bound for its ring hash implementation: "With the ring partitioned appropriately, the addition or removal of one host from a set of N hosts will affect only 1/N requests." Note the conditional clause "With the ring partitioned appropriately", which is the virtual-node requirement again.

The reason the clip's number is exactly 3 of 12 is that the animation hand-placed the key dots. On a real ring with one point per server, 3 of 12 is the expected value and the realized value depends on where hash("cache-D") happens to fall. If D lands close behind B, almost nothing moves and the new server absorbs almost no load. If D lands far behind B, it takes an oversized arc. The Karger paper's monotonicity property is what actually holds unconditionally: "if items are initially assigned to a set of buckets V1 and then some new buckets are added to form V2, then an item may move from an old bucket to a new bucket, but not from one old bucket to another." The proof sketch says it more operationally: "When a new bucket is added, the only items that move are those that are now closest to one of the new bucket's associated points. No items move between old buckets." Monotonicity is a guarantee. The 1/N share is an average.

## Most of the caches a viewer would reach for do not use the ring the clip draws

The clip generalizes from "cache server" without naming any system, which leaves the viewer to assume Redis or memcached works this way. Checked against each project's own documentation, that assumption mostly fails.

Redis Cluster does not use a hash ring at all. The [Redis cluster specification](https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/) states that "The cluster's key space is split into 16384 slots" and gives the formula "HASH_SLOT = CRC16(key) mod 16384", with the note that "14 out of 16 CRC16 output bits are used (this is why there is a modulo 16384 operation in the formula above)." Slots are then assigned to nodes and migrated explicitly during resharding. This is a fixed-modulus scheme with an indirection layer, and the fixed modulus of 16384 is precisely what prevents the clip's failure mode: the modulus never changes when you add a node, only the slot-to-node map does.

memcached does no distribution at all on the server side. Key placement is entirely the client's job, and [libmemcached's behavior documentation](https://awesomized.github.io/libmemcached/libmemcached/memcached_behavior.html) states that "The default method is MEMCACHED_DISTRIBUTION_MODULA (hash of the key modulo number of servers)." Consistent hashing is opt-in via MEMCACHED_DISTRIBUTION_CONSISTENT, which "is an alias for the value MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA", and MEMCACHED_BEHAVIOR_KETAMA "Sets the default distribution to MEMCACHED_DISTRIBUTION_CONSISTENT_KETAMA and the hash to MEMCACHED_HASH_MD5." So the exact broken configuration in the clip's story is the shipped default of the most widely used memcached client library, and the fix is a one-line behavior flag.

Cassandra does use a token ring with virtual nodes. The [Apache Cassandra operations documentation](https://cassandra.apache.org/doc/stable/cassandra/managing/operating/topo_changes.html) says "The `num_tokens` parameter will define the amount of virtual nodes (tokens) the joining node will be assigned during bootstrap" and that "The tokens define the sections of the ring (token ranges) the node will become responsible for." That same page still claims "The default of 256 virtual nodes should provide a reasonable load balance with acceptable overhead", which no longer matches the shipped configuration. I pulled `conf/cassandra.yaml` from the [Cassandra trunk branch](https://raw.githubusercontent.com/apache/cassandra/trunk/conf/cassandra.yaml) and read `num_tokens: 16` on line 42. The documentation page is stale relative to the default file.

DynamoDB is the one I cannot confirm. The [AWS partition documentation](https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html) says only that "DynamoDB uses the value of the partition key as input to an internal hash function. The output value from the hash function determines the partition in which the item will be stored." It never says consistent hashing and never mentions a ring. Given that the 2007 Dynamo paper is the origin of the virtual-node variant, it would be reasonable to assume continuity, but AWS does not document it and I am not going to assert it.

Envoy ships both options and names the ring explicitly. Its documentation describes ring hash as a load balancer where "Each host is mapped onto a circle (the 'ring') by hashing its address; each request is then routed to a host by hashing some property of the request, and finding the nearest corresponding host clockwise around the ring", and notes that this "is also commonly known as 'Ketama' hashing." That is a direct match for the clip's diagram, and it is the clearest real-world example of the technique as drawn.

## Two later algorithms beat the plain ring on balance, and one older one is contemporaneous with it

The clip presents consistent hashing as the answer with no mention of what came after. Three alternatives are worth knowing, and one of them is not actually newer.

Jump consistent hash, published by John Lamping and Eric Veach in 2014 as ["A Fast, Minimal Memory, Consistent Hash Algorithm"](https://arxiv.org/abs/1406.2294), states in its abstract that compared to Karger et al.'s algorithm it "requires no storage, is faster, and does a better job of evenly dividing the key space among the buckets." It fits in about five lines of code. The catch is stated in the same abstract: "the buckets must be numbered sequentially, which makes it more suitable for data storage applications than for distributed web caching." Named cache servers that come and go in arbitrary order do not fit that model, so it is not a drop-in replacement for the clip's scenario.

Maglev hashing, from the NSDI '16 Google paper cited above, builds a fixed-size lookup table instead of a ring and achieves "almost perfect load balancing no matter what the table size is." The tradeoff is stability, and Envoy's documentation quantifies it from its own implementation at table size 65537: "it is not as stable as ring hash when upstream hosts change. More keys will move position when hosts are removed (simulations show approximately double the keys will move)." For a cache fronting a database, doubling the key movement doubles the miss spike, which is the exact thing the clip is trying to avoid. Maglev is the better choice for network load balancing and the worse choice for the cache in this story.

Rendezvous hashing, also called highest random weight, is often presented as a modern alternative but is not newer. David G. Thaler and Chinya V. Ravishankar published ["Using Name-Based Mappings to Increase Hit Rates"](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/HRW98.pdf) in IEEE/ACM Transactions on Networking, volume 6, number 1, February 1998, roughly nine months after the Karger STOC paper, and the conference version predates that. It defines "the disruption coefficient, which we define as the fraction of the total number of objects that must be remapped when a server comes up or goes down", and proves a lower bound on it for any mapping that divides objects evenly. HRW scores every server for every key and picks the maximum, so it has no ring and no placement variance, at the cost of O(n) work per lookup. The Maglev measurement above put its overprovisioning requirement at 49.5%, worse than Karger's 29.7%, at a 65537-entry table.

## Switching to the ring costs one full remap, and the new server still cold-misses its share

The clip is titled "How to add a cache server safely" and never states two costs that the engineer in the story would hit on Monday.

The first is the migration itself. Moving from `hash(key) % 3` to a ring with A, B and C placed by hash does not preserve any existing assignment. The mapping is computed differently, so essentially every key changes owner once. The fix for a 75% remap is a one-time near-total remap. That is still the right trade because it is paid once instead of on every resize, but a team that deploys the change during peak traffic reproduces the exact outage they are trying to prevent.

The second is that 1/N is still a real miss spike. On a four-server ring, roughly 25% of requests land on a cold Cache D and fall through to the database. The clip's own animation shows the "hash % N" bar at 9 of 12 next to "hash ring" at 3 of 12 and treats the second as a win, which it is, but 3 of 12 is still a quarter of traffic arriving at a database that the premise says is already near capacity. Nothing in consistent hashing warms a cache. Adding a server safely needs the new node brought in with its share of traffic ramped, or a request-coalescing layer in front of the database, which is the other half of the very same 1997 paper. Karger's abstract pairs consistent hashing with "random cache trees", and section 5.1 of that paper is titled "Swamping", bounding the number of requests any single cache receives. The clip teaches one of the paper's two mechanisms and the problem in its own cold open is partly the other one.

## Key Takeaways

- **Verified:** The on-screen counter "9 / 12 keys remapped" is exactly right. A resize from 3 to 4 servers under `hash(key) % N` moves exactly 75% of keys, because `h mod 3 == h mod 4` only at h = 0, 1, 2 within each block of 12. The general form is n/(n+1).
- **Partial correction:** The auto-generated transcript archived with this video reads "about 80% of your keys". The creator's burned-in caption reads "ABOUT 75% OF YOUR KEYS" and the video description says "roughly 75%". The correct value is 75% and the 80% appears to be a transcription error, not a claim the creator made.
- **Correction:** The ring the clip draws places one point per cache server. That is not the algorithm Karger et al. published. Section 4.2 of the 1997 paper requires `k log(C)` points per bucket, and the balance guarantee in Theorem 4.1 is proved from that replication. The clip never says the word "virtual node" or "replica".
- **Correction:** The clip implies cache servers in general use this scheme. Redis Cluster uses `CRC16(key) mod 16384` fixed hash slots with no ring. libmemcached defaults to plain modulo distribution, so the broken configuration in the clip's story is the shipped default and consistent hashing is opt-in. Cassandra does use a token ring, with `num_tokens: 16` in current trunk. Envoy's ring hash is a direct match for the diagram.
- **Unverified:** AWS's public DynamoDB documentation describes only an "internal hash function" determining the partition and never mentions consistent hashing or a ring, so I cannot confirm from primary sources that DynamoDB still uses the scheme its 2007 ancestor paper described.
- **Unstated cost:** Migrating from `hash % 3` to a ring remaps nearly every key once, because the two mappings share no structure. The fix for a 75% remap is a one-time near-total remap, which has to be scheduled rather than shipped at peak.
- **Unstated cost:** The ring still sends roughly 1/N of traffic to a cold new server. On the clip's own numbers that is 3 of 12 requests falling through to a database the premise already describes as near capacity. Consistent hashing reduces the miss spike and does not eliminate it.
- **Unstated cost:** With one ring point per server, the "3 / 12" result is an expected value, not a guarantee. Where `hash("cache-D")` lands determines whether the new server takes an undersized or oversized arc. Google measured Karger-style hashing at 1000 backends as needing 29.7% backend overprovisioning to absorb the imbalance.
- **Verified:** The newer algorithms are real but conditional. Jump consistent hash needs sequentially numbered buckets, which caches named by hostname do not have. Maglev balances better and moves roughly twice as many keys on host removal per Envoy's own simulations, which is the wrong trade for a cache in front of a database.
- **Context:** Rendezvous hashing is contemporaneous with consistent hashing rather than newer. Thaler and Ravishankar published it in IEEE/ACM Transactions on Networking in February 1998.
- **Context:** The app plugged at the end is spelled "Devmaxx" on the App Store, listed as "Master System Design" by Arjay McCandless LLC in Education, free with a $8.99/month or $59.99/year subscription and 4.3 stars from 521 ratings. The audio transcript renders the name as "DevMax".

## Resources

- [Consistent Hashing and Random Trees (Karger, Lehman, Leighton, Levine, Lewin, Panigrahy), full PDF](https://people.csail.mit.edu/karger/Papers/web.pdf). The original 1997 paper; section 4.1 defines balance, monotonicity, spread and load, section 4.2 gives the `k log(C)` points-per-bucket construction, and section 5.1 covers swamping.
- [ACM Digital Library entry for the STOC '97 paper](https://dl.acm.org/doi/10.1145/258533.258660). Canonical citation, pages 654 to 663, May 1997.
- [Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf). Section 4.2 states the two challenges of the basic ring and defines virtual nodes with their three listed advantages.
- [Maglev: A Fast and Reliable Software Network Load Balancer, PDF](https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf). Section 3.4 gives the lookup-table algorithm, section 5.3 gives the 29.7% and 49.5% overprovisioning measurements for Karger and Rendezvous hashing.
- [USENIX NSDI '16 page for the Maglev paper](https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/eisenbud). Venue and authorship confirmation.
- [A Fast, Minimal Memory, Consistent Hash Algorithm (Lamping and Veach, 2014)](https://arxiv.org/abs/1406.2294). Jump consistent hash, including the sequential-bucket limitation stated in the abstract.
- [Using Name-Based Mappings to Increase Hit Rates (Thaler and Ravishankar, 1998)](https://www.microsoft.com/en-us/research/wp-content/uploads/2017/02/HRW98.pdf). Rendezvous / highest random weight hashing, with the disruption coefficient definition and bound.
- [Redis cluster specification](https://redis.io/docs/latest/operate/oss_and_stack/reference/cluster-spec/). The 16384 hash slots and the `HASH_SLOT = CRC16(key) mod 16384` formula, with no ring.
- [memcached ConfiguringClient wiki](https://github.com/memcached/memcached/wiki/ConfiguringClient). The project's own consistent hashing section, including the understated "40%+" figure for adding an eleventh server.
- [libmemcached memcached_behavior documentation](https://awesomized.github.io/libmemcached/libmemcached/memcached_behavior.html). Confirms MEMCACHED_DISTRIBUTION_MODULA is the default and ketama is opt-in.
- [Apache Cassandra adding/replacing nodes documentation](https://cassandra.apache.org/doc/stable/cassandra/managing/operating/topo_changes.html). `num_tokens`, token ranges, and the stale claim that 256 is the default.
- [Apache Cassandra trunk conf/cassandra.yaml](https://raw.githubusercontent.com/apache/cassandra/trunk/conf/cassandra.yaml). Line 42 reads `num_tokens: 16`, the actual shipped default.
- [Envoy supported load balancers documentation](https://www.envoyproxy.io/docs/envoy/latest/intro/arch_overview/upstream/load_balancing/load_balancers). Ring hash described as ketama with the 1/N claim, and the Maglev stability comparison.
- [DynamoDB partitions and data distribution](https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/HowItWorks.Partitions.html). The "internal hash function" wording, with no mention of consistent hashing.
- [Devmaxx on the App Store](https://apps.apple.com/us/app/devmaxx/id6758278144). The app shown in the closing screen recording, by Arjay McCandless LLC.
