Consistent Hashing: Why Adding a Cache Server Remaps 75% of Keys
By Matt Cullerton, founder of Mavric and Apso
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 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 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 (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 (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 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 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 still say the default is 256, but the trunk 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) "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 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) - the original paper
- ACM entry for the STOC '97 paper - citation
- Dynamo (SOSP 2007) - virtual nodes
- Maglev paper - overprovisioning measurements
- Maglev at USENIX NSDI '16 - venue and authors
- Jump consistent hash (2014) - Lamping and Veach
- Rendezvous hashing (1998) - Thaler and Ravishankar
- Redis cluster specification - 16384 hash slots
- memcached ConfiguringClient wiki - client-side distribution
- libmemcached behaviour docs - modulo default, ketama opt-in
- Cassandra topology changes docs - num_tokens and token ranges
- Cassandra trunk cassandra.yaml - current num_tokens default
- Envoy load balancers - ring hash and Maglev
- DynamoDB partitions - partition key hashing
- Devmaxx on the App Store - the creator's system design app, advertised at the end of the video
Published September 21, 2026. Based on a TikTok by @arjay_mccandless. Full video notes (markdown)