Consistent Hashing - Ring, Vnodes, Rendezvous, Jump
hash(key) % Nis not consistent: going from N to N+1 servers keeps only 1/(N+1) of the keys where they were, so N/(N+1) move (75% for 3 to 4, 91% for 10 to 11). Every move is a cache miss or a data migration.- On a hash ring a key belongs to the first node clockwise from its hash. Adding a node takes over one arc, so only about 1/(N+1) of the keys move, and all of them move to the new node.
- One token per node gives lumpy load (a node at 2x the average is normal). Give each node 100 to 200 virtual nodes and load lands within roughly 10% of average.
- Replicas are the next distinct physical nodes clockwise, not the next tokens (those may be the same host).
- Alternatives trade memory for lookup cost: rendezvous (no state, O(N) lookup), jump (no state, O(log N), only grows at the end), bounded loads (cap any node at c times average), Maglev (lookup table for L4 load balancers).
Mental model
Picture a round table with seats numbered around the rim. Each guest has a number on their name tag and walks clockwise from that number to the first occupied seat, then sits at that seat's table of food (the seat's owner serves them). When a new seat is added, only the guests standing in the stretch just behind the new seat switch to it. Everyone else keeps walking to the same seat as before. If instead every guest had to compute "my number divided by the seat count", adding one seat would change almost everyone's answer.
Where it breaks: with only a few seats, the gaps between them are uneven, so one seat can serve far more guests than another. The real fix is giving every server many seats scattered around the rim.
The ring is a sorted array of (hash, node) pairs plus binary search: an ordered map where a lookup is "find the smallest key greater than or equal to this one, wrapping to the first entry if there is none". That is TreeMap.ceilingKey in Java or bisect_right in Python. Placing a node is just inserting its tokens into the map, and only the keys between the new tokens and their predecessors change owner.
Where it breaks: a TreeMap does not care how evenly its keys are spread, but a ring does. Load is the gap between tokens, so a ring with few random tokens is lopsided in a way no ordinary map is.
How it works
Start with the problem the ring solves. You have N cache servers and want each key to go to one server, the same one every time, without a central table. The obvious function is server = hash(key) % N.
Why mod N reshuffles
Say hash(key) is just a number h. The key sits on server h mod N. Add a server and the rule becomes h mod (N+1). Take N = 3 and the hash values 0 to 11 (one full cycle of both rules, because 12 = 3 x 4):
| h | h mod 3 | h mod 4 | Moves? |
|---|---|---|---|
| 0 | 0 | 0 | no |
| 1 | 1 | 1 | no |
| 2 | 2 | 2 | no |
| 3 | 0 | 3 | yes |
| 4 | 1 | 0 | yes |
| 5 | 2 | 1 | yes |
| 6 | 0 | 2 | yes |
| 7 | 1 | 3 | yes |
| 8 | 2 | 0 | yes |
| 9 | 0 | 1 | yes |
| 10 | 1 | 2 | yes |
| 11 | 2 | 3 | yes |
Only h = 0, 1, 2 keep their server: 3 of 12 stay, 9 of 12 (75%) move. The pattern repeats forever because h mod 12 decides everything.
The general result follows. If a key stays, h mod N = h mod (N+1) = r for some remainder r. Then h - r is divisible by both N and N+1. Those two numbers share no factor (consecutive integers), so h - r is divisible by their product N(N+1), which means h = r + m x N(N+1) with r < N. In every block of N(N+1) consecutive hash values exactly N of them (those with r from 0 to N-1 and m fixed) satisfy this, so the fraction that stay is N / (N(N+1)) = 1/(N+1) and the fraction that move is N/(N+1).
| Change | mod-N moves | Ring moves | Ring formula |
|---|---|---|---|
| 3 to 4 nodes | 3/4 = 75.0% | 1/4 = 25.0% | 1/(N+1) |
| 10 to 11 nodes | 10/11 = 90.9% | 1/11 = 9.1% | 1/(N+1) |
| 100 to 101 nodes | 100/101 = 99.0% | 1/101 = 0.99% | 1/(N+1) |
The bigger the fleet, the closer mod-N gets to "everything moves". Behind a cache that means the hit rate falls off a cliff every time you scale, which is exactly when the backend can least afford it.
The ring
Map both nodes and keys onto the same circle: the hash space, usually 0 to 232 - 1 (or 264 - 1), with the top value wrapping to 0. Hash each node's name to get its token, a position on the circle. To find a key's owner, hash the key and walk clockwise to the first token you meet.
Adding a node
Place D between B and C. The keys that were walking past B to reach C, but whose position is now before D, stop at D. Only the arc from B to D changes hands. Nothing else moves, and nothing moves between old nodes: every moved key goes from C to the new node D.
Why 1/(N+1)? By symmetry: once D exists, the N+1 nodes are interchangeable, so each owns the same expected share of the circle, 1/(N+1). D's share is exactly what it took from others, and keys only move into D. A measured run agrees: 10,000 keys, nodes a, b, c plus d, 100 tokens each, moved 24.2% (the script is in Hands-on). The exact value wobbles with the hash, which is why the claim is "about 1/(N+1)".
Virtual nodes
With one token per node the gaps are random and uneven. With N tokens thrown at random on a circle, the largest gap is typically a multiple of the average, not close to it. A measured run, 5 nodes and 10,000 keys, 200 trials each, md5 token positions:
| Tokens per node | Mean of busiest node / average | Worst trial | Typical spread (std dev / average) |
|---|---|---|---|
| 1 | 2.19x | 3.84x | 74% |
| 16 | 1.29x | 1.75x | 20% |
| 100 | 1.13x | 1.40x | 9% |
| 200 | 1.08x | 1.21x | 6% |
That is the reason for virtual nodes (vnodes): each physical node owns many tokens (a#0, a#1, ... hashed separately) scattered around the ring. A node's load is then the sum of many small random arcs, and sums of many independent pieces concentrate near their mean, with relative spread shrinking roughly as 1/sqrt(tokens). That fits the table: about 20% at 16 tokens, 9% at 100, 6% at 200. This is the improvement the Dynamo paper describes as its refined partitioning (DeCandia et al., "Dynamo", section 6.2). The numbers above are from a script like the one in Hands-on; they vary a little with the hash and the key names.
Vnodes also help a new node: its tokens land all around the ring, so it takes a small slice from every existing node instead of a large slice from one neighbour, and the streaming work is spread across the fleet.
Try it: add and remove nodes, switch between 1 and 128 vnodes and watch the load bars flatten, compare the moved-key counts against mod-N, then turn on the hot key and bounded loads.
Change the topology to see how many keys move.
key-1-1 hashes to 0x6811b6a4 (146.3 degrees); first token clockwise belongs to B; owner ■ B.
| Scheme | moved | share | note |
|---|---|---|---|
| no change yet | |||
Deep dive
Lookup cost and ring maintenance
Keep the tokens as a sorted array of T = N x v entries (N nodes, v tokens each). A lookup hashes the key and binary searches for the first token at or above it, wrapping to index 0: O(log T). Python's bisect_right and Java's TreeMap.ceilingEntry are exactly this. Adding or removing a node inserts or deletes v tokens; rebuilding the sorted array is O(T log T), and since membership changes are rare relative to lookups, clients typically rebuild and swap the array atomically. Envoy's ring_hash policy builds such a ring and bounds its size with minimum_ring_size and maximum_ring_size (Envoy load balancers).
Replication on the ring
To store a key on R replicas, find its owner and then keep walking clockwise, collecting nodes until you have R distinct physical nodes. This is the Dynamo preference list (Dynamo, section 4.3). The word "distinct" matters: with vnodes the next token clockwise is often another token of the same host, and counting it would put two "replicas" on one machine. Production systems go further and skip nodes in the same rack or zone so one failure domain cannot hold every copy; Cassandra's NetworkTopologyStrategy does this (Cassandra architecture: Dynamo). With replicas, a quorum read or write needs a majority of them (2 of 3 for R = 3), so any read quorum overlaps any write quorum and one failed replica per key is tolerated.
Rendezvous (highest random weight) hashing
Instead of a ring, give every (key, node) pair a score, score = hash(key, node), and send the key to the node with the highest score. It comes from Thaler and Ravishankar's 1996 paper "A Name-Based Mapping Scheme for Rendezvous". Properties:
- No ring state. A client needs only the node list.
- Even in expectation with no vnodes, because every node wins each key with equal probability.
- Minimal disruption. Remove a node and only the keys it had win elsewhere (each goes to its second-highest scorer). Add one and it wins about 1/(N+1) of the keys.
- O(N) lookup, one hash per node. Fine for tens of nodes, painful for thousands. For replicas, take the top R scorers, which are automatically distinct nodes.
GitHub's load balancer director uses rendezvous hashing to pick a backend for a connection (GLB Director announcement).
Jump consistent hash
Lamping and Veach (Google, 2014) published a function with no memory and no ring: jump(key, n) returns a bucket number from 0 to n-1 in expected O(log n) time (arXiv:1406.2294). When n grows to n+1, a key either stays or moves to the new last bucket, and exactly 1/(n+1) of keys move. The cost of that elegance: buckets are numbered, so you can only add or remove at the end. You cannot remove bucket 4 of 10, which makes it a fit for sharded storage where shards are added in order and failures are handled by replicas, and a poor fit for a cache fleet where any server can die. A direct port of the paper's C++ (checked below):
Running it over 100,000 keys moved 25.0% going from 3 to 4 buckets, 9.0% from 10 to 11 and 1.0% from 100 to 101, and every moved key landed in the new bucket.
Bounded loads
Plain consistent hashing balances in expectation but a popular key still lands on one node. Consistent hashing with bounded loads (Mirrokni, Thorup and Zadimoghaddam, 2016) sets a capacity for every node of ceil(c x average load) for some c = 1 + epsilon. A key walks clockwise as usual, but if the target is at capacity it keeps walking to the next node with room (paper, Google Research summary). The price is that the tighter you set c, the more keys get reassigned when load or membership changes; the paper bounds that reassignment as a function of epsilon. Vimeo engineers implemented it in HAProxy, where it is exposed as hash-balance-factor, a percentage of average load a server may carry (HAProxy configuration manual, see the hash-balance-factor keyword).
Maglev hashing
Google's Maglev software load balancer needs something different: every packet of a connection must reach the same backend, lookups must be a single array read, and a backend change must disturb as few connections as possible. Maglev builds a lookup table of prime size M (the paper uses 65,537 and 655,373). Each backend gets a pseudo-random permutation of the table slots, and backends take turns claiming their next free preferred slot until the table is full. Lookup is then table[hash(5-tuple) mod M]. Disruption on backend change is small but not minimal (it trades some disruption for near-perfect balance), so Maglev pairs the table with a per-connection tracking cache (Eisenbud et al., "Maglev", NSDI 2016). Envoy ships both ring_hash and maglev policies. For where this sits in an L4 load balancer, see Load Balancing.
The algorithms side by side
| Scheme | State per client | Lookup | Balance | On add / remove |
|---|---|---|---|---|
| hash mod N | node list | O(1) | even | moves N/(N+1) of keys on add |
| Ring, 1 token | N tokens | O(log N) | poor (2x average is normal) | moves about 1/(N+1); one neighbour pays |
| Ring, vnodes | N x v tokens | O(log(N x v)) | good (about 1/sqrt(v) spread) | moves about 1/(N+1); every node pays a little |
| Rendezvous | node list | O(N) | even in expectation | moves about 1/(N+1); remove sends keys to each key's runner-up |
| Jump | bucket count only | O(log N) expected | even | moves exactly 1/(n+1) on add; can only add or remove the last bucket |
| Maglev | table of M entries (M prime, 65,537 and up) | O(1) | near-perfect | small but not minimal disruption; pair with connection tracking |
Hot keys
Hashing spreads keys, not requests. One celebrity key is one position on the ring and one node, however well the ring is balanced, and bounded loads cannot split a single key's traffic because the key still has exactly one owner at a time. Fixes live above the hash:
- Replicate the hot key across several nodes and let readers pick one at random (or the least loaded).
- A small in-process cache in the client or front tier, with a short TTL, absorbs repeat reads before they reach the ring at all.
- Split the key (
counter#0tocounter#7) for write-hot counters and sum on read. - Coalesce concurrent misses so a stampede on one expiring key sends one request upstream.
Where this sits in the course
Consistent hashing picks which node owns a key, and it is the single owner page for that idea. Load Balancing covers how L4 and L7 balancers use it (and the other balancing algorithms), including how anycast and ECMP keep a flow on one balancer. CDN and caching covers cache sharding at the edge. Dynamo-style databases (Cassandra, Riak, Dynamo) apply the same ring to data partitioning, with replication, hinted handoff and anti-entropy on top; the full treatment is outside this networking course, and the Dynamo paper is the place to start.
Textbook vs real world
| The textbook says | Production does | Why |
|---|---|---|
| One token per node on the ring | Many tokens per node; Cassandra used 256 by default and changed the default to 16 in 4.0 | Random arcs are lumpy; more tokens flatten load, but each token adds repair and streaming overhead, which is why the default came back down |
| Consistent hashing gives an even load | Balanced in expectation only; bounded loads (HAProxy hash-balance-factor) cap nodes at c times average | Even a well-balanced ring cannot split one hot key, and popular keys skew the tail |
| Adding a node rebalances instantly | The new node must stream its arc from the old owners; reads in the meantime go to the old owners or miss | Moving data costs bandwidth and time; for a cache the cost is cold misses, for a database it is streaming and hinted handoff |
| Hash the client IP to keep a user on one backend | Hash a session, user or tenant key | Many users share one IP behind a NAT or proxy, so IP hashing piles them onto one node; mobile users change IP |
| The key space must be a ring | Redis Cluster uses 16,384 fixed slots (CRC16 of the key mod 16384) assigned to nodes | A slot table is simple to inspect and migrate by hand: you move slots, not arcs |
| Consistent hashing is for caches | Dynamo-style databases, L4 load balancers, sharded queues and actor routing all use it | Anything that must route a key to a stable owner without a central directory |
In production
- Akamai is where the idea came from: the 1997 paper's authors include Akamai's co-founders Leighton and Lewin, and the problem it addresses (web cache hot spots) is the CDN problem (Karger et al., STOC 1997).
- Amazon Dynamo partitions with a ring and vnodes, replicates to the next distinct nodes, and describes the refinements it tried (Dynamo, SOSP 2007). Cassandra's design follows Dynamo's and its docs describe its token and replication behaviour (Cassandra architecture).
- memcached clients adopted the ring through ketama, written at Last.fm in 2007 (RJ/ketama). nginx's
hash $key consistent;is ketama-compatible (ngx_http_upstream_module). Facebook describes spreading items over memcached servers with consistent hashing in Scaling Memcache at Facebook. - Envoy offers
ring_hashandmaglevload-balancing policies (Envoy load balancers); HAProxy hashash-type consistentandhash-balance-factor(configuration manual). - Google Maglev forwards traffic with a lookup table built from permutations (NSDI 2016). GitHub's GLB director uses rendezvous hashing (GLB Director).
- Redis Cluster deliberately does not use a ring: 16,384 hash slots,
HASH_SLOT = CRC16(key) mod 16384(Redis cluster spec).
History and evolution
- 1996 Thaler and Ravishankar publish rendezvous (highest random weight) hashing for mapping names to servers, a ring-free answer to the same problem.
- 1997 Karger and colleagues at MIT publish "Consistent Hashing and Random Trees" at STOC, motivated by hot spots in web caching: add or remove a cache and only a small share of pages should move. Akamai is founded the following year by Leighton and Lewin.
- 2001 Chord (SIGCOMM) uses a ring for peer-to-peer lookup. What broke: P2P systems had no central index, and a ring gave O(log N) routing with graceful churn (Stoica et al.).
- 2007 Dynamo (SOSP) and ketama (Last.fm) put the ring into production for storage and for memcached clients. What broke: one token per node is lumpy, so both systems use many tokens per host; Dynamo section 6.2 compares three partitioning strategies and what each costs in balance and membership changes.
- 2014 Lamping and Veach publish jump consistent hash: no ring, no memory, but buckets only grow at the end.
- 2016 Bounded-load consistent hashing caps per-node load (Google Research, implemented in HAProxy), and Google's Maglev paper (NSDI) describes lookup-table hashing for its L4 balancer. What broke: ring balance is only statistical, and a load balancer wants a single array read per packet.
- 2018 GitHub open-sources GLB Director, which uses rendezvous hashing, so the 1996 idea is in production.
- Now Cassandra 4.0 defaults to 16 tokens per node instead of 256, Envoy ships ring and Maglev policies, and Redis Cluster sticks with fixed slots; "which scheme" is a per-workload choice.
- Next Shard managers such as Google's Slicer (OSDI 2016) assign key ranges dynamically using load and failures instead of a fixed hash function; expect more adaptive placement (Adya et al.).
Hands-on
Count moved keys with a ring vs mod N (Python 3, no dependencies; works on macOS and Linux):
About 24% of keys move on the ring and about 75% with mod N, matching 1/(N+1) and N/(N+1) for N = 3. The exact decimals depend on the hash function. Count owner(after, k) per node and you will see all four nodes near 2,500 of 10,000, which is the vnodes at work (one token each would not look like this).
Mod N with only the shell: cksum is a CRC32, good enough to see the effect (real output, same on macOS and Linux):
Take each first number mod 3 and mod 4 (echo $((3744522271 % 3)) $((3744522271 % 4))): the three keys go from servers 1, 1, 1 to servers 3, 0, 0. All three moved when one server was added.
A system that does not use a ring (Redis Cluster, needs a running cluster):
12182 is CRC16("foo") mod 16384; I computed it independently and it matches. redis-cli cluster slots then lists which node owns which slot range. Resharding moves slots, never arcs.
A system that does (Cassandra, if you have a node; the output columns vary by version):
Each row is a token owned by a node; with vnodes you see many rows per host, the tokens interleaved between hosts, which is the vnodes figure above for real. nodetool status shows each node's share ("Owns") of the ring.
Gotchas
Interview questions
Show answer
It works until N changes. Going from N to N+1 servers keeps only 1/(N+1) of the keys on their old server, so N/(N+1) of them move: 75% for 3 to 4 and about 91% for 10 to 11. For a cache that is a mass of simultaneous misses hitting the backend; for a database it is a mass data migration. A hash ring moves only about 1/(N+1) of the keys instead.
Follow-ups:
- How do you derive N/(N+1)? A key stays only when its hash has the same remainder mod N and mod N+1; that happens for N out of every N(N+1) consecutive hash values.
- What happens when a node is removed? Same problem in reverse for mod N: the remainder rule changes for most keys. On a ring only that node's arc moves, to its clockwise neighbour.
Show answer
Hash nodes and keys onto the same circle. A key belongs to the first node clockwise from its position, so adding or removing a node only changes ownership for the arc next to it, about 1/(N+1) of the keys. One token per node leaves the arcs uneven, so each physical node gets many virtual tokens scattered around the ring. Its load is the sum of many small random arcs, which concentrates near the average.
Follow-ups:
- How many vnodes? Around 100 to 200 gives roughly 6 to 9% spread in my measurements; the spread shrinks like 1/sqrt(v). More tokens cost memory, slower rebuilds and more streaming work when nodes change; Cassandra's default went from 256 to 16 in 4.0 for that reason.
- Why do vnodes help a new node? It takes a small slice from every existing node instead of a big slice from one, so no single node is stressed during rebalancing.
Show answer
Take the key's owner and keep walking clockwise, collecting nodes until you have R distinct physical nodes (R = 3 is typical). That list is Dynamo's preference list. With vnodes you must skip tokens belonging to a host you already picked, and production systems also skip nodes in the same rack or zone.
Follow-ups:
- How do reads and writes use them? Quorum reads and writes each need a majority of replicas (2 of 3), so any read quorum overlaps any write quorum.
- What if a replica is down? Dynamo-style stores write to the next healthy node with a hint and hand the data back later (hinted handoff).
Show answer
Keep all tokens in a sorted array of (hash, node). Hash the key and binary search for the first token at or above it, wrapping to the start if none. That is O(log T) for T total tokens, so a few thousand tokens is about a dozen comparisons. Membership changes rebuild the array, which is O(T log T) but rare.
Follow-ups:
- Why not a hash map? A hash map answers exact matches; the ring needs "first token at or after this position", which needs ordered data.
- What if the key hashes past the last token? Wrap to index 0; that is the "ring".
Show answer
A ring keeps a sorted token array and does an O(log T) lookup, needs vnodes for balance, and supports arbitrary node add and remove. Rendezvous keeps no state beyond the node list: score every node with hash(key, node) and take the highest, which is O(N) but naturally even and trivially gives R distinct replicas as the top R. Jump hash needs no memory and runs in O(log N), but it only works with numbered buckets, so you can only grow or shrink at the end.
Follow-ups:
- When does jump hash fail? When an arbitrary node dies; you cannot remove bucket 4 of 10 without renumbering, so it suits shards, not cache servers.
- When is rendezvous the right call? Small fleets and L4 directors; GitHub's GLB uses it.
Show answer
Pick a ring with 100 to 200 vnodes per node (or a slot table like Redis Cluster) in a smart client or proxy tier so there is no central lookup. Size nodes so no single one carries more than its share at peak, with headroom for losing one. Replicate to 2 or 3 distinct racks if misses are expensive. Add a short-TTL in-process cache in the clients for hot keys, and request coalescing so a stampede on one expiring key produces one backend fetch. On node failure, accept misses for that arc, and warm the replacement gradually.
Follow-ups:
- How do you handle a hot key? Replicate it across k nodes and read from a random one, or key-split counters; hashing cannot spread one key.
- What happens on rebalance? Only about 1/(N+1) of keys move to the new node, so the hit rate dips by about that fraction, not to zero.
- What do you watch? Per-node request rate and memory, not just key count, since a ring balances counts.
Show answer
Use bounded loads: cap each node at ceil(c x average load) for some c above 1 such as 1.25, and when a key's target is full, keep walking clockwise to the next node with room. This guarantees no node exceeds c times average. The cost is extra reassignments when load or membership changes, which grows as c shrinks. HAProxy exposes it as hash-balance-factor.
Follow-ups:
- What breaks if c is too tight? Constant reshuffling: nearly every key is at capacity, so a small change cascades.
- Does this solve a single hot key? No; the key still lives on one node at a time, so replicate or cache it.
Show answer
It combines a connection-tracking table with a consistent mapping for new flows. Existing flows are looked up by 5-tuple in the tracking table and keep their backend even if the table would now map them elsewhere. New flows use a hash of the 5-tuple into a lookup table such as Maglev, which is built so a backend change reassigns few slots. If the tracking entry is lost (a different balancer instance took the packet, or the table was evicted), the lookup table sends the flow to the same backend with high probability.
Follow-ups:
- Why not tracking alone? It is per-instance state; behind ECMP different packets of one flow can reach different balancers, so a deterministic hash is the fallback (Load Balancing).
- Why not hash alone? Backend set changes would still break some live connections, so tracking protects the existing ones.
Fun facts
- Redis Cluster deliberately uses 16,384 fixed slots instead of a ring:
CRC16(key) mod 16384. The maintainer's stated reason was the size of the slot bitmap carried in cluster heartbeat messages (redis issue 2576). - At 100 servers, adding the 101st with plain mod N moves 99% of keys (100/101), so a cache fleet that scales one node at a time effectively flushes itself.
- Jump hash fits in a handful of lines of C++ and needs no memory at all, because it replays a pseudo-random generator seeded by the key instead of storing a ring.
- The 1997 paper behind the idea was about web caches, not databases; Dynamo made it famous a decade later.
Cheat sheet
- N/(N+1) - share of keys that move with mod N when one node is added (75% for 3 to 4, 91% for 10 to 11, 99% for 100 to 101)
- 1/(N+1) - share that moves on a ring, jump hash or rendezvous
- 100 to 200 - typical vnodes per node for roughly 6 to 9% load spread (spread is about 1/sqrt of tokens)
- 16 / 256 - Cassandra
num_tokensdefault since 4.0 / before - 16,384 - Redis Cluster hash slots (CRC16 mod 16384)
- 65,537 - Maglev lookup table size in the paper (a prime)
- O(log T) - ring lookup over T tokens; O(N) rendezvous; O(log N) jump