Consistent hashing for stable key placement

13 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Consistent hashing maps keys and servers onto the same circular hash space; a key belongs to the first server clockwise from its position.
When a server joins or leaves, only the keys in its arc move, about 1/N of the total, instead of nearly all keys as with hash(key) mod N.
Each physical server is placed many times on the ring (virtual nodes) so load evens out and a departing server's keys spread across all survivors.
Variants trade memory, speed and flexibility: ring hashing, rendezvous hashing, jump hash and Maglev all keep movement minimal.
It answers the problem shape "finding things fast" under churn, and it is a tool against "hot spots" only when combined with replication or bounded loads.

How it works

The problem with mod N

The obvious shard choice is hash(key) mod N: fast and even, until N changes. Going from 9 to 10 servers, a key stays put only when h mod 9 == h mod 10, about 1 key in 10. The other 90% move: a miss storm for a cache, or a 90% data copy for a store.

The ring

Consistent hashing hashes servers and keys into the same space, say 0 to 2^32 - 1, and treats that space as a circle. To find a key's owner, hash the key and walk clockwise until you hit a server's position. Each server owns the arc between its predecessor and itself.

Add a server and it takes over part of one arc; every other key keeps its owner. Remove one and its arc merges into its successor's. Movement is local by construction. Karger and colleagues introduced the idea in 1997 for web caches, defining the properties this lesson relies on: balance, monotonicity and spread (Karger et al.).

Virtual nodes

With one position per server the arcs are uneven: with 4 servers, one can own 40% of the ring and another 4%. When a server dies, its whole arc lands on one neighbour.

The fix is to place each server many times, as cache-3#0, cache-3#1, and so on. With 100 to 200 virtual nodes per server, each share is the sum of many small arcs and stays within roughly 10% of the mean. A failed server's arcs are scattered, so its load spreads across every survivor. Virtual nodes also give weighting: a machine with twice the memory gets twice the virtual nodes.

Replication on the ring

Dynamo, Cassandra and Riak also use the ring to choose replicas. A key's preference list is the first R distinct physical servers found walking clockwise; skipping virtual nodes of already-chosen servers (and zones) keeps two replicas off one machine. Dynamo's paper also reports that purely random tokens hurt in operation: bootstrapping a new node took almost a day in peak season, Merkle trees had to be rebuilt for changed ranges, and archiving was awkward. Amazon moved to equal-sized fixed partitions handed out to nodes, the same idea as logical shards (DeCandia et al.).

Other members of the family

Rendezvous hashing: score every server with hash(key, server) and pick the highest. No ring, minimal movement, O(N) per lookup. GitHub's GLB load balancer precomputes it into a table of about 65,000 rows, each holding the top two servers, so a draining server can hand unknown flows to its second choice (GitHub).
Jump consistent hash: a few lines of arithmetic map a key to a bucket in 0, N) with no memory, but buckets can only be added or removed at the end ([Lamping and Veach).
Maglev hashing: a fixed lookup table built from per-server permutations, whose size must be prime (65,537 entries by default in Envoy); lookup is one array index (Eisenbud et al.).
Bounded loads: cap each server at, say, 1.25 times the average; a key whose owner is full moves to the next server clockwise (Mirrokni et al.). HAProxy ships this as hash-balance-factor, off by default, with 125 to 200 suggested as reasonable values (HAProxy docs).

Down the stack

Layer 1The contract

Given a membership set M and a key k, owner(k, M) is a pure function: every client holding the same M and the same hash function computes the same owner with no coordination. Monotonicity: if M' = M plus one server s, then for every key either owner(k, M') == owner(k, M) or owner(k, M') == s. Removal is symmetric. Expected movement on one change is K/N keys. Balance is probabilistic: with V virtual nodes per server, the largest share exceeds the mean by roughly a factor of 1 + O(sqrt(log N / V)). The contract says nothing about agreement. Two clients with different views of M will route the same key to different servers, and nothing in the algorithm detects that.

Layer 2The mechanism

A ring is a sorted array of (token, server) pairs. Lookup hashes the key and binary-searches for the first token greater than or equal to it, wrapping to index 0 past the end. Cassandra's Murmur3Partitioner uses signed 64-bit tokens from -2^63 to 2^63 - 1, and the num_tokens setting picks virtual nodes per node (256 in older releases, 16 by default since 4.0, paired with allocate_tokens_for_local_replication_factor: 3 so the allocator places tokens deliberately rather than randomly) (Cassandra NEWS). A node that joins with a different num_tokens from the rest of its datacenter owns a different share of data, so treat the value as fixed for the cluster's life. Membership travels by gossip, so ring views converge over seconds. Envoy's RING_HASH policy builds a ring of at least minimum_ring_size (1,024) and at most 8M entries, hashing with xxHash by default (Envoy docs). Memcached's libketama places servers 160 times each on average, taking four 32-bit chunks from each of 40 MD5 digests and scaling the count by each server's share of total memory (libketama).

Layer 3The machine

A ring with 50 servers and 160 virtual nodes each holds 8,000 entries. At 8 bytes of token plus an 8-byte pointer that is 128 KB, which fits in a typical 1 to 2 MB L2 cache. A binary search touches about 13 entries; when the ring is warm in cache that is well under 100 ns, and hashing a 40-byte key with xxHash or Murmur3 adds about 10 ns. Maglev's single array index is a few nanoseconds, which is why it fits packet-rate load balancers that handle millions of packets per second per core. The real cost is data movement: rebalancing 1/10 of a 20 TB cluster is 2 TB, about 27 minutes at a full 10 Gbps, and hours once streaming is throttled to protect foreground I/O.

Why it's built this way

Networks and disks are the scarce resource, so the algorithm minimises the data that has to move when membership changes.
Coordinating every routing decision through a central directory adds a round trip and a single point of failure, so ownership is computed locally from a shared hash function and membership list.
Random placement of a few points is uneven, so each server gets many points, trading memory for balance.
Big rings and per-lookup searches cost CPU at packet rates, so load balancers moved to fixed tables (Maglev) that trade a little extra movement for constant-time lookups.

Diagram

flowchart LR
  K["key: user:42"] --> H["hash32 = 0x9A31..."]
  H --> S["binary search sorted tokens"]
  S --> T["first token >= hash"]
  T --> W{"past the end?"}
  W -- "yes" --> Z["wrap to token 0"]
  W -- "no" --> V["vnode cache-3#17"]
  Z --> V
  V --> P["physical server cache-3"]
  P --> R["next distinct servers for replicas"]

Worked example

A product catalogue cache runs on 9 Memcached nodes at 200,000 reads per second with a 95% hit rate, so the database sees 10,000 reads per second and is sized for about 25,000.

The team adds a tenth node before Black Friday. With mod N, about 90% of keys change owner, the hit rate drops toward 10%, and the database sees up to 180,000 reads per second. It falls over, and the cache never warms because the warming requests time out.

With a ring of 160 virtual nodes per server, the new node takes about 1/10 of the keyspace from all nine existing nodes evenly. The hit rate dips from 95% to about 85% and recovers as the new node fills. The database sees roughly 30,000 reads per second at the peak of the dip. That still exceeds its budget, so the team adds the node in a quiet hour or pre-warms it by mirroring reads for its arc.

If one node dies at peak, its 1/9 share, spread over 160 arcs, falls to the other eight, each picking up about 1/72 of the keyspace. Without virtual nodes, one neighbour would absorb the whole 1/9 and double its load.

In the wild

Monzo, 2019: new ring members answer before they have data. Monzo added 6 nodes to a 21-node Cassandra cluster with auto_bootstrap off, expecting them to sit idle until data was streamed. Instead they took ownership of their token ranges at once and answered reads with "not found", so balances and transactions looked wrong and payments failed for about two hours; full reconciliation took until 23:00. A single-node test had not shown the quorum effect of adding six (Monzo).
Vimeo, 2016: bounded loads for a video cache tier. Plain consistent hashing balances keys, not requests, so some cache servers ran far hotter than others. Vimeo's Andrew Rodland implemented Google's bounded-load variant in HAProxy (now the hash-balance-factor option), which cut cache bandwidth by a factor of almost 8 and removed a scaling bottleneck (Google Research).
GitHub, 2018: rendezvous hashing in the load balancer. GLB Director keeps a table of about 65,000 rows, each holding a primary and secondary proxy chosen by rendezvous hashing. Adding a proxy moves about 1/N of flows, and draining swaps primary and secondary so in-flight connections finish on the old server while new ones move (GitHub).

Trade-offs

Option	Strengths	Weaknesses	Choose when
`hash mod N`	Trivial, perfectly even, O(1)	Nearly all keys move when N changes	N never changes, or a full reshuffle is cheap
Ring with virtual nodes	Named servers, weights, replicas by walking clockwise	Memory per vnode; balance only statistical	Caches and storage with arbitrary membership
Rendezvous hashing	No ring state, exact minimal movement, easy weights	O(N) hashes per lookup	Tens of servers, or choosing top-k replicas
Jump hash	Zero memory, very even, fast	Only add or remove the last bucket	Numbered shards that grow append-only
Maglev table	O(1) lookup, small fixed table	Slightly more than minimal movement; rebuild on change	L4 load balancers at packet rate
Directory (lookup service)	Any placement, moves one range at a time	Extra hop, a service to run and keep consistent	Range scans, manual hot-spot splitting

Pitfalls in production

Inconsistent membership views. Clients that learn of a new server at different times write one key to two places. Distribute versioned membership from one source.
Too few virtual nodes. Ten vnodes per server leaves some servers with twice the load of others. Measure the actual share per server and raise vnodes, or use an allocator that places tokens deliberately.
Weak or unstable hash functions. Using a language's built-in string hash, which may be seeded per process, gives every client a different ring. Pin a named hash such as Murmur3, xxHash or MD5 and document it as part of the protocol.
Hot keys. Consistent hashing balances key counts, not traffic. One celebrity key still lands on one server. Add replicas for reads, a local cache in front, or bounded-load hashing.
Replicas on the same machine or zone. Walking vnodes without skipping duplicates puts two copies on one box. Skip already-chosen physical servers and zones when building preference lists.

Leadership lens

Ask in design review what happens to hit rate and backend load in the first five minutes after adding or losing a node, with numbers.
Treat the hash function, vnode count and membership source as a versioned protocol; changing any of them is a migration, not a config tweak.
Budget for rebalancing time and bandwidth in capacity plans. Adding capacity to a stateful cluster takes hours, so it must happen before the peak, not during it.

Check yourself

A cluster grows from 4 to 5 servers. Roughly what fraction of keys move under mod N, and under a ring?
Show answer
Under mod N, about 4/5 of keys move, because only keys where h mod 4 == h mod 5 stay. Under a ring, about 1/5 move, all of them to the new server.
Why do virtual nodes help when a server fails, not just in steady state?
Show answer
The failed server's arcs are scattered around the ring, so each arc's keys go to a different successor. The extra load spreads over all survivors instead of doubling one neighbour.
Two clients use the same ring code but route the same key to different servers. Name two likely causes.
Show answer
They hold different membership lists, for example one has not yet seen a join, or they use a hash that differs between processes, such as a per-process seeded string hash.
When would jump hash be a poor choice?
Show answer
When servers are named and can fail in any order. Jump hash only supports removing the highest-numbered bucket, so losing bucket 3 of 10 forces an extra remapping layer.

Sources and further study

Primary

Stoica et al., Chord (SIGCOMM 2001): consistent hashing in a peer-to-peer lookup service, with O(log N) routing and virtual nodes for balance.
Mirrokni, Thorup and Zadimoghaddam, Consistent Hashing with Bounded Loads (2016): the capacity cap and its guarantees on movement.

Systems docs

Apache Cassandra NEWS: num_tokens default change: why 4.0 moved from 256 to 16 tokens and the token allocator.
Envoy: Cluster configuration: ring size bounds, hash function and Maglev table size.
HAProxy: hash-balance-factor: bounded-load consistent hashing in a production proxy.
libketama source: the memcached continuum, with weighting by memory.

Books

System Design Interview, Volume 1, Alex Xu, chapter 5 "Design Consistent Hashing": the ring, virtual nodes and affected-key arithmetic.
Designing Data-Intensive Applications, Martin Kleppmann, chapter 6 "Partitioning" (1st edition), section "Rebalancing Partitions": argues for fixed partitions over mod N and notes how loosely "consistent hashing" is used.

Other curricula

Azure Architecture Center: Sharding pattern: treats consistent hashing as the fix for hash mod N resharding, next to virtual shards in a lookup map.

Watch

Consistent Hashing | Algorithms You Should Know #1 (ByteByteGo): animated walkthrough of the ring, virtual nodes and data movement.
What is CONSISTENT HASHING and Where is it used? (Gaurav Sen): whiteboard explanation starting from the mod N problem.

Free resources

Consistent Hashing and Random Trees (Karger et al., 1997): the original paper defining balance, monotonicity and spread.
Dynamo: Amazon's Highly Available Key-value Store: virtual nodes, preference lists and partitioning strategies in a production store.
A Fast, Minimal Memory, Consistent Hash Algorithm (Lamping and Veach): jump consistent hash in a few lines, with its limits.
Maglev: A Fast and Reliable Software Network Load Balancer: the lookup-table variant built for packet-rate balancing.
Consistent Hashing with Bounded Loads (Google Research): capping per-server load while keeping keys mostly stable.
Envoy load balancers: ring hash and Maglev as configurable policies in a real proxy.

Open in the interactive app: practice, quiz, mock interview →