Consistent hashing
The ring algorithm behind Cassandra, DynamoDB, Redis Cluster, and every CDN.
You built a photo-sharing app. It got popular. Right now every request — "give me photo #42," "give me Alice's profile," "give me the top posts" — hits your database. Your database is slowing down because it is answering the same questions over and over again.
The obvious fix is to put a cache in front of your database. A cache is a small, fast, in-memory store that remembers recent answers so you don't need to ask the database twice. Think of a notepad on your desk: before you dig through the filing cabinet, you glance at your notepad. If the answer is there already, you skip the cabinet entirely.
Cache hit: cache had the answer → 1 ms response, database untouched. Cache miss: cache didn't have it → falls through to database → 50 ms response.
One cache is not enough — you add more
One cache works fine at first. But your app grows. Millions of things to remember. Traffic is high. A single cache machine can only hold so much and answer so fast. So you scale out and add more caches.
Now you have 3 caches — call them Cache 0, Cache 1, Cache 2. Each key (like photo:42 or user:99) lives on exactly ONE of these three caches. When your app wants a key, it has to decide, for every single request: "Which cache holds this?" If the app asks the wrong cache, that cache says "I don't have it" — a cache miss — and the request falls through to the slow database. Cache misses are exactly what caches were supposed to prevent.
The natural first attempt — hash(key) mod N
Here's the simplest possible rule: turn the key into a number (a hash), take that number modulo N (the number of caches), and use the result as the cache index.
Clean, fast, deterministic. The same key always maps to the same cache, so the app never gets confused. Every cache does its share. For a while, this works beautifully.
Why hash % N was the industry standard for years
Before I show you what breaks, understand why engineers picked this scheme in the first place. It has real benefits — it wasn't a stupid choice. It was the obvious choice, and it served the industry well through the 1990s.
Perfectly deterministic
Given the same key and the same N, every server, every client, every process on Earth computes the same answer. Nobody has to coordinate. The client library on the app server independently knows where each key lives — no lookup service needed. This is the biggest engineering win.
Perfectly balanced (with a good hash)
A good hash function distributes outputs uniformly. Mod N of uniform numbers gives you roughly K/N keys per cache — no cache is overloaded, no cache is idle. Load is even, latency is predictable. Beautiful.
Blazing fast
A hash + one modulo op. Sub-microsecond. No I/O, no lookup table, no round-trip. Every request pays essentially zero overhead to figure out its cache. At millions of requests per second, this matters.
Stateless everywhere
No node needs to know about any other node. No cluster coordinator. No health-check protocol. Just a shared config "N=3" and the same hash function. Add clients, remove clients, migrate clients — nothing changes about the cache mapping.
These properties are what a distributed system engineer craves — determinism, balance, speed, and no coordination. Hash mod N delivers all four. The tragedy is that it delivers them only when N never changes. And in real production, N always changes.
Then you add a cache — and everything breaks
Traffic keeps growing. You need a 4th cache. So you add one. Suddenly your database is on fire — a wave of traffic hits it that shouldn't be there. Something is very wrong.
The problem is that N changed from 3 to 4. The math hash % N now gives a DIFFERENT answer for almost every key. Watch this happen with 12 keys — click the button to add the 4th cache:
Nine of twelve keys just moved to different caches. Each one is now a cache miss — the new cache doesn't have that data yet, so the request falls all the way through to the database. All at once. For a real system with a million keys, that's ~750,000 database queries hitting at the same moment. Your database melts.
And this is not a rare accident. It happens every single time you add or remove a cache. Deploy a new server? Stampede. A server crashes? Stampede. Auto-scaling event at 3 AM? Pager. The mod-N scheme has a fundamental design flaw: changing N remaps almost everything.
The search for a better way
We want a way to map keys to caches such that adding or removing a cache moves only a small fraction of keys — ideally about 1 out of N, not 3 out of 4. If we can find that, cache churn stops being a database-killing event. Servers can come and go without dread.
In 1997, three MIT researchers — David Karger, Eric Lehman, and Tom Leighton — published the answer. They called it consistent hashing, and the trick is beautifully geometric: put both caches and keys on a circle. Once you see it, you'll understand why every major distributed database, cache, and CDN uses this idea. The rest of this chapter shows you exactly how it works.
The 1997 Akamai origin story
Karger and colleagues at MIT were working on a hot-spot problem for the early web: some pages went viral (the paper called them "flash crowds"), overloading their origin server. The fix was to distribute those pages across many caching proxies, but every time a proxy joined or left the fleet, mod-N hashing re-shuffled the entire cache and made things worse — exactly the problem you just saw. Consistent hashing was the answer. The paper became the technical foundation of Akamai, which spun out of MIT in 1998 and became the internet's largest CDN. Almost every distributed-cache paper since builds on this idea.
Watch it happen — the animated walkthrough
Below the algorithm plays out step by step: an empty ring, nodes arrive one by one, then keys are assigned by walking clockwise, then a new node joins and you see exactly which keys move and which don't. This is the mental model you keep for the rest of your career.
Now try it yourself — the interactive ring
The algorithm in detail
The interactive ring and walkthrough above show what happens. Here is how a real implementation actually does it in code. The whole algorithm fits on one page.
Put nodes on a ring
Hash each node's name to a number in the ring's address space (typically [0, 2³²) or [0, 2⁶⁴)). Place it at that position on a circular ring. The ring is just the number line wrapped so that 2³² connects back to 0.
Put keys on the same ring
Hash each key with the SAME hash function. A key at angle θ belongs to the first node you hit going clockwise from θ. That is the entire routing rule.
Only ~K/N keys move
Add a node — only the keys that used to point to the node clockwise of the new node get reassigned. Remove a node — only its keys move to the next clockwise node. Everything else stays put.
Here is the pseudocode. Every implementation from Amazon Dynamo to Redis Cluster is a variation of this:
Hash function requirements
- Uniform distribution — outputs spread evenly across the ring
- Deterministic — same input always → same output (no wall-clock, no random seed)
- Fast — called on every lookup; must be sub-microsecond
- Non-cryptographic is fine — Murmur3, xxHash, CityHash. MD5 is common historically but overkill.
- NOT hash(a)+hash(b) — never compose; you break uniformity
Complexity
- Lookup: O(log N) with a sorted array + binary search, or O(log N) with a red-black tree
- Add node: O(log N) to insert into the ring
- Remove node: O(log N)
- Space: O(N × V) where V = virtual nodes per physical (see below). For N=100 nodes × 150 vnodes = 15K entries — trivial memory.
- Keys moved on add/remove: approximately K/N — the whole point
Implementation decisions — the three questions every implementer answers
When you actually write consistent hashing (or read someone else's code), you'll see three specific design decisions made explicitly. Understanding them is the difference between using a library and debugging one.
Question 1: What size is the ring? 2³² or 2⁶⁴?
The "ring" is just an integer range wrapped into a circle. But what range? Every real implementation picks one of these:
The choice depends on two factors: how many virtual nodes you'll place (you need enough slots that collisions are astronomically rare) and what fits your hash function's output. If you use MD5 you already have 128 bits and can afford to waste some. If you use Murmur3-32 you naturally get 32 bits and use the full space.
Rule of thumb
2³² (4.29 billion slots) is enough for any practical deployment. Even at 1,000 nodes × 256 vnodes = 256,000 positions, you use 0.006% of the ring. Collision probability is negligible. Ketama, memcached clients, and HAProxy all use 32-bit rings. 2⁶⁴ (18 quintillion slots) is chosen by paranoid engineers or systems that natively produce 64-bit hashes (Cassandra's Murmur3, DynamoDB). It doesn't "help" distribution — 32 bits was already over-sized — but costs nothing except 4 extra bytes per entry. 2¹²⁸ (MD5's output) is used by DynamoDB and Riak because they just take the whole MD5 output as the position without truncating. Also fine.
Question 2: What do you hash — the node's name, or its index?
You could number nodes 0, 1, 2, ... and place them at fixed positions on the ring. Simple, right? Wrong. Every real implementation hashes the node's NAME (a string like cache-us-east-1a or an IP:port). Here's why:
✅ Hash the name
Nodes get pseudo-random positions on the ring, spread out statistically. When node cache-3 leaves and a replacement cache-9 joins, the new node lands somewhere completely different — which means it doesn't inherit the old node's keyspace. Different arc gets rebalanced.
Also enables virtual nodes trivially: hash("cache-us-east-1a#0"), hash("cache-us-east-1a#1"), ..., hash("cache-us-east-1a#255"). Each vnode has an independent, random-looking position.
❌ Number them 0..N-1
Positions become predictable — node k at k × (ring_size / N). Adding a 4th node fundamentally changes every existing node's position — you're back to the mod-N stampede problem.
No natural way to add virtual nodes (they'd all cluster around the physical node's slot). No way to have "bigger" nodes carry more load. And you need a coordinator to assign the next available number — losing the stateless property.
Question 3: Which hash function?
Not all hash functions are equal for this. Speed, distribution quality, and output size all matter. But cryptographic strength does not — we don't care whether an attacker can find collisions on purpose; we care whether outputs spread evenly for real keys.
Modern default: Murmur3 for new code. It's fast, well-distributed, used by Cassandra, and available in every language. Use MD5 only if you're maintaining a system that already does (Ketama, old memcached clusters) — the CPU cost is 5-10× higher for zero gain in distribution quality.
Why crypto doesn't help here
Cryptographic hashes (MD5, SHA-1, SHA-256) resist adversarial collision finding. That property costs CPU cycles. Consistent hashing has no adversary — we're not defending against someone who wants to steer keys to a specific node. We just need uniform distribution over random-ish keys. Non-crypto hashes (Murmur3, xxHash, CityHash) do this just as well at 5-10× the speed. Redis Cluster is more extreme: they use CRC16 (16-bit, 1976 vintage) because it's plenty for their fixed 16,384-slot scheme.
Virtual nodes — the practical fix for the hot-shard problem
Now the honest story about real deployments. The plain-vanilla algorithm has a serious problem in practice: random hash positions cluster. If you have 4 nodes on the ring and one of them happens to land right after a big gap, that node inherits a huge fraction of the keyspace and becomes a hot shard. This is not rare — it happens statistically whenever N is small.
The math of imbalance
With N random positions on a unit ring, the largest arc is expected to be (log N)/N — not 1/N. For N=10 nodes, one node inherits ~23% of the keys on average (vs the ideal 10%). For N=100 nodes it's still ~4.6% (vs 1%). Real production without vnodes routinely sees 2–3× imbalance between the biggest and smallest node.
The fix is beautifully simple: give each physical node V virtual positions on the ring (typically 100–256). Each virtual node is hashed independently: hash("nodeA#0"), hash("nodeA#1"), etc. Any key that falls into any of A's 150 arcs routes to physical node A. With enough vnodes, the law of large numbers takes over: distribution converges to K/N ± a few percent even at small N.
The V trade-off
More V = tighter balance but more ring entries to store + slightly slower lookup (still O(log N × V)). Fewer V = faster lookups but more variance in load. Sweet spot for most systems: 128–256. Google's Jump Consistent Hash (2014) trades away this parameter for a different algorithm that doesn't need vnodes at all — worth reading.
Bigger machines = more V
If some nodes are more powerful (2× RAM, 2× disk), give them 2×V vnodes. They'll own proportionally more of the ring and receive more keys automatically. This is how Cassandra num_tokens tuning handles heterogeneous clusters.
Failure modes you'll actually hit
🔥 Hot key
One super-popular key (a viral URL, a celebrity user) can overload the single node that owns it. Consistent hashing cannot help — no matter how many nodes you add, that one key lives on one node. Fix at a higher layer: CDN cache the hot key, or shard it further (append a shard suffix and fan out reads).
📡 Flapping node
A node keeps disconnecting and reconnecting. Every event triggers a rebalance, migrating keys back and forth and wasting IO. Mitigation: add a grace period (30–120s) before considering a node dead. Cassandra's phi_convict_threshold controls exactly this.
💥 Rebalance stampede
When you add a node, the ~K/N keys that need to move do so simultaneously — bursting the network and the source node's disk. Fix: throttled bootstrap (Cassandra's stream_throughput_outbound_megabits_per_sec) and hinted handoff so writes buffer during the migration window.
🎯 Cold-start miss cascade
A new node joins the ring with empty caches. All its keys miss. Requests fall through to origin. Origin melts. Fix: warm the new node before promoting it to the production ring (many systems have a "bootstrapping" state where the node accepts writes but is invisible to reads until its data is caught up).
When NOT to use consistent hashing
Range queries
"Give me all users with IDs 1000-2000." Consistent hashing scatters those across every node — you have to scatter-gather. If range queries dominate, use range partitioning (HBase, Bigtable, sharded Postgres by range) instead.
Very small N (< 10) without vnodes
Without virtual nodes, N < 10 gets 50%+ imbalance. If you can't afford vnodes (very memory-constrained edge caches), use manual sharding with hand-tuned hash slots — the tradeoff favors predictability at tiny N.
Frequent membership changes
If nodes join and leave every minute (containerized elastic scale), the rebalance overhead eats you alive. Use a load-balancer-in-front pattern (client always talks to a stable LB, LB talks to backends by whatever scheme) or bounded consistent hashing.
You control the placement
For static data with predictable access patterns, a hand-designed shard map beats consistent hashing on predictability. YouTube stores video metadata by hash(video_id) — Vitess handles this — but stores the CDN distribution using a hand-crafted geographic map.
Real-world scenarios — visualized
Before the deep-dive cards, look at how two production systems actually use consistent hashing. These aren't abstract — they are the exact patterns you'll see in DynamoDB source code, Redis Cluster protocol, and Cassandra token maps.
Scenario 1: DynamoDB — preference lists of 3 replicas
DynamoDB replicates every key to 3 nodes. Which 3? The first three going clockwise from the key's position on the ring. This ordered triple is called the "preference list." The first node is the primary; the other two are hot standbys that keep async replicas. Drag the key below to see the preference list update:
Scenario 2: Redis Cluster — 16,384 fixed slots
Redis Cluster doesn't hash into a giant 2⁶⁴ ring. Instead it uses a fixed set of 16,384 "hash slots"(chosen so the cluster membership state fits in 2 KB gossiped between nodes). Every key maps to a slot via CRC16(key) mod 16384. Each shard owns a contiguous range of slots. Adding a shard = handing it a range. Watch it below:
Notice the difference: DynamoDB uses a continuous ring (2¹²⁸ positions) with vnodes for balance. Redis Cluster uses a discrete 16,384-slot ring with shards owning ranges. Both are consistent hashing. The trade-off: DynamoDB scales to arbitrary node counts; Redis Cluster tops out around 1,000 nodes practical (each node must track ownership of a slice of 16K slots) but is simpler to reason about.
Applied in real systems — the deep dive
Every entry below is a real production system. Each one implements consistent hashing slightly differently — the choices they made are instructive. Click any card to read the full deep-dive on that system — with animations, code walkthroughs, and the design decisions behind it.
Amazon Dynamo → DynamoDB
128-bit MD5 hash space. Each physical host owns ~100 virtual tokens. For each key, walks the ring clockwise to find the first node (the "coordinator") plus the next N-1 (the "preference list" — usually 3 for replication factor 3). Writes go to the preference list; reads can be served from any. This is the reference implementation of "consistent hashing for real production." DeCandia et al., SOSP 2007.
Apache Cassandra
64-bit Murmur3 partitioner. Every node has num_tokens=256 virtual tokens by default. Ring topology is propagated via gossip protocol — every node knows the full ring within a few seconds. Data is replicated to the next replication_factor nodes clockwise. Lakshman & Malik, SIGOPS 2010.
Redis Cluster — the 16384-slot variant
Uses a fixed set of 16,384 hash slots (chosen because 16384 = 2¹⁴ fits in 2 KB of state gossiped between nodes). Formula: slot = CRC16(key) % 16384. Each shard owns a range of slot IDs. Adding a shard = transferring a set of slots (not individual keys), which is fast. Simpler than pure consistent hashing at the cost of max cluster size (~1000 nodes practical).
Akamai — the original industrial user
CDN edge servers use consistent hashing to decide which peer edge server to fetch from on a cache miss. Hash key = URL. If node A doesn't have a URL cached, it asks the peer that owns that URL's hash slot — which acts as a mid-tier cache before falling through to origin. This is where consistent hashing was first deployed at billion-request scale in ~1999.
Discord — chat channel routing
Every chat channel is owned by exactly one chat server at any time. Consistent hashing on hash(channel_id) picks which server. When a chat server dies, its channels migrate to neighbors on the ring. Discord scaled this pattern to over 100M concurrent users. See their blog "How Discord scaled Elixir to 5,000,000 concurrent users."
Last.fm Ketama — the OSS reference
Ketama was the widely-copied 2007 C library used for memcached client-side sharding. Every memcached driver in every language (pylibmc, spymemcached, java-memcached-client) has a "ketama" setting. 160 vnodes per host, MD5 hash, and a beautiful C implementation you can read in ~200 lines.
L7 load balancers
HAProxy's balance uri + hash-type consistent and Nginx's hash $variable consistent both implement consistent hashing for backend selection. Use case: sticky routing so a given URL always goes to the same upstream cache — even if you add or remove upstreams — maximizing cache hit rate at the backend.
Your own system
Ch 7 sharding: we shard the urls table by hash(short_code) so adding a shard rebalances ~1/N of URLs. Ch 6.5 Redis Cluster: caching tier uses the 16,384-slot variant. Ch 8 L7 multi-region: consistent hashing selects which region should coordinate writes for each short_code.
Newer variants (2010s–2020s)
Jump Consistent Hash (Google, 2014)
Lamping & Veach's 2014 paper. No ring, no vnodes, no memory overhead — just a tiny mathematical function that maps (key, num_buckets) → bucket_id. Perfectly balanced, O(log N) lookup, minimal key movement. Trade-off: buckets must be numbered 0..N-1 sequentially (you can only add/remove from the end). Used inside Google's internal systems.
Rendezvous (Highest Random Weight)
Also called HRW. For each key, compute hash(key, node_i) for every node; pick the node with the highest score. No ring at all. Simpler mental model, comparable movement guarantees to consistent hashing at the cost of O(N) lookup per key. Used in some Microsoft and Twitter systems.
Bounded-Load Consistent Hashing (Google, 2016)
Mirrokni, Thorup, & Zadimoghaddam. Adds a "bounded load" constraint so no single node ever exceeds (1+ε) × K/N keys. Used inside Google's Vimeo-Vitess and Cloud Load Balancer to smooth out hot spots.
Maglev (Google, 2016)
Google's software load balancer uses a variant that pre-computes a lookup table of ~65K slots, each pointing to a backend. Any packet's 5-tuple hash maps to a slot → backend in O(1) time. Rebalance is table swap. Trade-off: table size vs memory. See "Maglev: A Fast and Reliable Software Network Load Balancer" (NSDI 2016).
Interview soundbites
When the interviewer probes this, these are the sentences that signal fluency:
hash(id) mod N."Why it's wrong: resharding moves ~90% of keys, guaranteed cache stampede.
References
- Karger, Lehman, Leighton, Panigrahy, Levine, Lewin (1997) — "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web." STOC '97. The founding paper. This became Akamai's technical foundation.
- DeCandia et al. (2007) — "Dynamo: Amazon's Highly Available Key-value Store." SOSP '07. The production case study that made consistent hashing mainstream. Every NoSQL DB since references this paper.
- Lakshman & Malik (2010) — "Cassandra: A Decentralized Structured Storage System." SIGOPS Operating Systems Review. The vnode extension for heterogeneous clusters.
- Lamping & Veach (2014) — "A Fast, Minimal Memory, Consistent Hash Algorithm." arxiv:1406.2294. Google's Jump Consistent Hash — a math trick that beats ring implementations on speed and memory.
- Mirrokni, Thorup, Zadimoghaddam (2016) — "Consistent Hashing with Bounded Loads." arxiv:1608.01350. The bounded-load variant that Google uses in production.
- Eisenbud et al. (2016) — "Maglev: A Fast and Reliable Software Network Load Balancer." NSDI '16. Google's load balancer implementation.
- Ketama library — Last.fm's 2007 C implementation, the canonical reference implementation for memcached clients across every language.
- Redis Cluster documentation — redis.io/topics/cluster-tutorial. Complete spec of the 16,384-slot fixed variant.
- Discord Engineering Blog — "How Discord Scaled Elixir to 5,000,000 Concurrent Users." (2017) The chat-channel routing story.
Practice what you just read
Every foundation concept has a companion quiz to close the loop.