# Consistent Hashing > Why hash-mod-N breaks when you resize, and how Amazon Dynamo, Cassandra, and Memcached avoid it with consistent hashing and virtual nodes. Canonical: https://ironclad.academy/system-design/articles/consistent-hashing | Difficulty: medium | Topics: Distributed Systems, Hashing, Sharding, Load Balancing Asked at: Amazon, Google, Microsoft ## Key takeaways - hash(key) % N remaps ~80% of keys when moving from 4 to 5 servers; consistent hashing cuts that to ~1/(N+1). - Each physical server gets 100–256 virtual ring positions so load distributes evenly and failure recovery spreads across all survivors, not one hot neighbor. - Lookup on a consistent hash ring is O(log V) binary search — fast at any practical scale, with trivially small memory overhead. - Cassandra 4.x cut vnodes from 256 to 16 by adding a deterministic token allocator, showing that allocator design matters as much as vnode count. - Hot-key traffic still lands on one node regardless of ring distribution — that requires key-level replication or local caching, not more vnodes. > **In one line:** Place servers and keys on a shared hash ring; each key belongs to the next clockwise server — so adding or removing a node shuffles only ~1/(N+1) of keys instead of nearly all of them. **The problem.** `hash(key) % N` is simple and fast, but changing N (adding or removing a server) remaps ~N/(N+1) of all keys — roughly 80% when you go from 4 to 5 nodes. Every cache miss hits the database simultaneously. Systems melt. **The fix — three ideas stacked.** 1. **Hash ring.** Hash both servers and keys into a large integer circle (0 to 2³²−1). Each key walks clockwise to its nearest server. Adding server E only steals keys from E's clockwise neighbor — ~1/(N+1) of the total. 2. **Virtual nodes (vnodes).** Each physical server gets 100–256 positions on the ring. This evens out the load distribution (each server owns ≈ 1/N of the ring) and spreads failure-recovery load across all remaining nodes rather than one neighbor. 3. **Weighted vnodes.** A beefier server gets more virtual positions — proportional scaling with no protocol changes. ```mermaid flowchart LR subgraph "Hash ring with vnodes" direction TB A1[A#1] --- B1[B#1] --- C1[C#1] --- A2[A#2] --- B2[B#2] --- C2[C#2] end K[key 'apple'] -->|"hash → walk clockwise"| A1 style A1 fill:#ff6b1a,color:#0a0a0f style A2 fill:#ff6b1a,color:#0a0a0f style B1 fill:#ffaa00,color:#0a0a0f style B2 fill:#ffaa00,color:#0a0a0f style C1 fill:#15803d,color:#fff style C2 fill:#15803d,color:#fff ``` **Key design decisions.** | Question | Answer | | --- | --- | | How many vnodes per server? | 100–256 typical; Cassandra 4.x uses 16 with a deterministic allocator | | Lookup cost? | O(log V) binary search on sorted vnode list; V = servers × vnodes | | Memory cost? | servers × vnodes entries — 1000 × 100 = 100k entries, trivially small | | Failure recovery? | With vnodes, failed node's keys scatter across all survivors (not just one neighbor) | | Heterogeneous hardware? | Give bigger servers more vnodes (weighted consistent hashing) | | Better alternatives? | Jump hash (O(log N), zero memory) when buckets are sequentially numbered; Rendezvous (HRW) when N is small | **If you have 60 seconds, say this.** "Naive mod-N hashing remaps ~80% of keys when you add one node — catastrophic for caches. Consistent hashing fixes this by placing both servers and keys on a hash ring; adding a node only steals keys from one neighbor, so only ~1/(N+1) keys move. Virtual nodes spread each server across 100-plus ring positions, giving even load distribution and scattering failure-recovery traffic across all survivors instead of one hot neighbor. Lookup is O(log V) binary search. Dynamo, Cassandra, and Memcached's Ketama client all use this." If you take only one algorithm from this whole site, take this one. Consistent hashing is the single most reused trick in distributed systems — caches, sharded databases, service meshes, CDNs, every load balancer at scale. Once you see it, you'll see it everywhere. ## The problem: naive sharding breaks on resize Suppose you have 4 cache servers and a million keys. The simplest sharding scheme: ``` server = hash(key) % 4 ``` Works great. Until you need to add a 5th server. Now: ``` server = hash(key) % 5 ``` Almost every key now hashes to a different server. Cache hit rate goes from 95% to ~0% overnight. Your databases melt, your latency explodes, you page someone at 3am. ```mermaid flowchart LR subgraph "Before: 4 servers" K1[key 'apple'
hash=46] -->|"46 % 4 = 2"| S2A[Server 2] K2[key 'orange'
hash=37] -->|"37 % 4 = 1"| S1A[Server 1] end subgraph "After: 5 servers" K1B[key 'apple'
hash=46] -->|"46 % 5 = 1"| S1B[Server 1] K2B[key 'orange'
hash=37] -->|"37 % 5 = 2"| S2B[Server 2] end style K1B fill:#ff2e88,color:#fff style K2B fill:#ff2e88,color:#fff ``` Roughly **N/(N+1)** of keys move when you go from N to N+1 servers. With 4 → 5, that's **80%** of keys remapped. Useless. ## The idea: a hash ring Consistent hashing puts both the keys _and_ the servers on the same conceptual circle (the "ring"). You hash both into the same large integer space (say, 0 to 2^32 - 1), arrange them around the ring, and assign each key to **the next server clockwise**. ```mermaid flowchart TD subgraph "Hash ring (0 to 2^32 - 1)" A[Server A
at hash 100] B[Server B
at hash 1000] C[Server C
at hash 2500] D[Server D
at hash 3500] end K1[key 'apple'
hash 50] -->|next clockwise| A K2[key 'banana'
hash 800] -->|next clockwise| B K3[key 'cherry'
hash 1500] -->|next clockwise| C K4[key 'durian'
hash 3000] -->|next clockwise| D K5[key 'elderberry'
hash 4000] -->|wraps around to| A style A fill:#ff6b1a,color:#0a0a0f style B fill:#ffaa00,color:#0a0a0f style C fill:#15803d,color:#fff style D fill:#0e7490,color:#fff ``` Now what happens when we add a new server E at hash 1800? Only the keys whose next-clockwise-server _was_ C (and who hash between B and 1800) move to E. Roughly `1/(N+1)` of keys move, not `N/(N+1)`. When we remove a server, only its keys redistribute to the next neighbor. ```mermaid flowchart LR subgraph "Add server E at 1800" direction TB NA[A: 100] NB[B: 1000] NE[E: 1800
NEW] NC[C: 2500] ND[D: 3500] end NK1[apple, banana — unchanged] NK2[cherry: 1500] -->|"used to go to C,
now goes to E"| NE style NE fill:#15803d,color:#fff ``` ## Why this matters **Adding a server moves only ~1/(N+1) keys.** This is the property that makes consistent hashing usable in practice. | Scheme | Keys remapped on N → N+1 | | --- | --- | | `hash(k) % N` | ≈ N/(N+1) (almost all) | | Consistent hashing | ≈ 1/(N+1) (a small slice) | For N = 100, going from 100 → 101 servers, the naive scheme reshuffles ~99% of keys; consistent hashing reshuffles ~1%. ## The unevenness problem There's a catch. Random hashing puts servers at random positions on the ring, and random points are not uniformly spaced. With 4 servers, you might end up with one server "owning" 60% of the ring and another only 5%. ```mermaid flowchart TD subgraph "Bad luck: uneven server placement" BA[A: 100] BB[B: 200] BC[C: 300] BD[D: 3500] end Note["A, B, C cluster together
D 'owns' ~60% of the ring"] style BD fill:#ff2e88,color:#fff ``` D will get most of the load. Not what we wanted. ## The fix: virtual nodes (vnodes) Instead of placing each server **once** on the ring, we place it **many times** — commonly 100–256 virtual copies, depending on fleet size and whether the allocator picks positions randomly or deterministically. Each virtual node is at a different position derived from `hash(server + "#" + i)`. ```mermaid flowchart TD subgraph "With virtual nodes (vnodes)" VA1[A#1] VA2[A#2] VA3[A#...] VB1[B#1] VB2[B#2] VB3[B#...] VC1[C#1] VC2[C#2] VC3[C#...] end Note["100 vnodes per server
distribution evens out"] style VA1 fill:#ff6b1a,color:#0a0a0f style VB1 fill:#ffaa00,color:#0a0a0f style VC1 fill:#15803d,color:#fff ``` With 100 vnodes per server the spread tightens sharply, but not to zero. The standard deviation of a server's load scales as ~`1/sqrt(V)`, so 100 random vnodes puts each server within roughly ±10% of `1/N`, and 256 within ~±6%. Getting to within ~1% with random placement would take ~10,000 vnodes; the practical route to near-perfect balance is a deterministic token allocator instead — which is exactly why Cassandra 4.x gets away with 16 tokens per node. There's a second benefit worth calling out: when a server fails, its keys get redistributed across _all_ remaining servers (not just one neighbor), spreading the recovery load. Without vnodes, you'd flood a single node; with them, every survivor absorbs a proportional share. ## Pseudocode ```python import bisect import hashlib class ConsistentHash: def __init__(self, replicas: int = 100): self.replicas = replicas self.ring: dict[int, str] = {} # hash -> server self.sorted_hashes: list[int] = [] # sorted keys of ring def _h(self, key: str) -> int: return int(hashlib.md5(key.encode()).hexdigest(), 16) def add_server(self, server: str): for i in range(self.replicas): h = self._h(f"{server}#{i}") self.ring[h] = server bisect.insort(self.sorted_hashes, h) def remove_server(self, server: str): for i in range(self.replicas): h = self._h(f"{server}#{i}") del self.ring[h] self.sorted_hashes.remove(h) def get_server(self, key: str) -> str: if not self.ring: return None h = self._h(key) idx = bisect.bisect(self.sorted_hashes, h) % len(self.sorted_hashes) return self.ring[self.sorted_hashes[idx]] ``` That's the entire algorithm. ~30 lines. ## Where consistent hashing is used in real systems | System | Use | | --- | --- | | **Amazon Dynamo / DynamoDB** | Partition data across nodes | | **Apache Cassandra** | Same. Each node owns a range of the ring | | **Memcached clients** (e.g. Ketama) | Pick which server holds a key | | **Riak** | Partition data | | **Akamai, CDN routing** | Map URLs to edge servers | | **Discord's Elixir services** | Map guild entities to nodes (via ex_hash_ring) | | **Many service meshes** | Sticky load balancing for stateful workloads | ## Variants and refinements ### Rendezvous hashing (HRW) The idea here is different: for each key, compute `hash(key + server_id)` for every server and pick the one that scores highest. There's no ring and no vnodes — just a list of servers and a comparison. The distribution is perfectly even, and you don't need to reason about ring positions at all. The cost is that lookup is O(N) — you must score every server. That's fine up to a few hundred nodes (the comparisons are embarrassingly parallelizable), but it becomes impractical at thousands. Used in Microsoft's CARP and some BitTorrent trackers. ### Jump consistent hash (Google, 2014) A clever closed-form algorithm that takes a key and a bucket count and returns the chosen bucket — no data structures at all. The paper describes it as ~5 lines of code: ```c // Jump consistent hash, from the paper int32_t jump_hash(uint64_t key, int32_t num_buckets) { int64_t b = -1, j = 0; while (j < num_buckets) { b = j; key = key * 2862933555777941757ULL + 1; j = (b + 1) * ((double)(1LL << 31) / (double)((key >> 33) + 1)); } return b; } ``` It runs in O(log N) and uses zero memory. The constraint is that your buckets must be numbered 0..N-1, and the only way to "remove a server" is to remove the highest-numbered bucket. You can't pull an arbitrary node out of the middle. That makes it well-suited to bulk storage systems with sequentially numbered shards (used inside Google for exactly that), but awkward for any cluster where arbitrary nodes come and go. ### Consistent hashing with bounded loads (CHBL) The plain ring has no back-pressure: whichever node sits clockwise of a hot arc just eats the load. CHBL (Google/Vimeo, 2017) adds a cap. Pick a limit of `(1 + ε)` times the mean load; when a key's target node is already at the cap, walk clockwise to the next node with spare capacity and place it there. Every node stays within a bounded factor of the average no matter how lumpy the key distribution is, and the spill is local — a resize still moves only a small slice. It's the standard modern answer to the load-imbalance and hot-spot problem, and it ships in both HAProxy and Envoy. ### Maglev hashing (Google, 2016) Maglev is the hashing scheme behind Google's software load balancer (and available in Envoy). It builds a lookup table via a permutation-fill procedure that gives near-perfect balance and minimal disruption when backends come and go, with O(1) lookups. If you're routing L4/L7 traffic across a backend pool rather than partitioning stored data, Maglev is the variant to reach for. ### Anchor hashing, Multi-probe consistent hashing Newer variants that try to combine the strengths of all the above. Mostly a research curiosity unless you're maintaining a hashing library. ## Picking the right approach ```mermaid flowchart TD Q1{"Buckets numbered
0..N-1 and grow
only at the end?"} Q1 -->|yes| JUMP["Jump hash
O(log N), zero memory"] Q1 -->|no| Q2{"Fleet size
≤ a few hundred?"} Q2 -->|yes| HRW["Rendezvous HRW
perfect balance, O(N) lookup"] Q2 -->|no| Q3{"Heterogeneous
node capacity?"} Q3 -->|yes| WRING[Weighted ring
more vnodes to bigger nodes] Q3 -->|no| RING[Ring + vnodes
the standard answer] style JUMP fill:#0e7490,color:#fff style HRW fill:#ffaa00,color:#0a0a0f style WRING fill:#a855f7,color:#fff style RING fill:#ff6b1a,color:#0a0a0f ``` Default to a ring with vnodes. It handles arbitrary node churn, gives you weighting for free, and every mature client library already implements it — you should need a specific reason to pick anything else. There are two reasons worth taking. Reach for jump hash only when your shards are genuinely append-only and sequentially numbered — bulk storage that grows at the tail — where its zero memory and lack of a ring structure are a real win. Drop to rendezvous (HRW) only when the fleet is small enough (a few hundred nodes) that an O(N) scan is cheap and you'd rather not maintain vnode bookkeeping. If you're load-balancing request traffic rather than partitioning stored data, that's a different question — see Maglev and CHBL under Variants above. ## Trade-offs to know **Memory** is essentially free. With 1000 servers × 100 vnodes you have 100k ring entries — trivially small. **Lookup speed** is O(log V) binary search over the sorted vnode list, where V is the total vnode count. Fast enough at any practical scale. **Rebalancing** when a node joins or leaves: ~1/(N+1) of keys move, and with vnodes those keys scatter across all surviving nodes rather than piling onto a single neighbor. That's the load-spreading property in action. **Heterogeneous servers** are handled naturally by giving bigger nodes more vnodes — weighted consistent hashing. No protocol changes needed. **Vnode count tuning** is worth understanding. More vnodes gives better balance but creates more data-streaming pairs at bootstrap time. Cassandra 3.x used 256 random positions per node; Cassandra 4.x dropped to 16 by adding a deterministic token allocator (`allocate_tokens_for_local_replication_factor`) that achieves similar balance with far less churn. The right count depends on whether your allocator is random or deterministic. **Hot-key problem** is a separate concern. Consistent hashing distributes keys across nodes evenly in aggregate, but if a single key is read or written at extreme rate — a viral tweet's media object, say — it still lands on exactly one node. More vnodes won't help — the load is one key, not one arc. That requires a different remedy: key-level replication, local caching, or sharding the key's value itself; when the imbalance is spread across several warm keys rather than one viral object, consistent hashing with bounded loads (above) caps how much any single node absorbs before spilling clockwise. **Gossip consistency of the ring** matters in practice. Every node needs an up-to-date view of ring membership for routing to work without a central coordinator. Cassandra gossips token ownership continuously. A stale ring view causes wrong-node routing, which the target node corrects with a redirect — a latency spike, not a correctness failure, but worth planning for. ## What breaks Consistent hashing bounds how many keys move on a resize, but it does not make a resize free. The thing it saves you from is a miss storm, so it's worth putting numbers on that. ```text Cache tier: 100k req/s, 95% steady-state hit rate → DB normally sees ~5k queries/s (the 5% that miss) Naive hash(k) % N, 4 → 5 servers: ~80% of keys remap → each one misses on first touch DB briefly sees ~100k × 0.80 = 80k queries/s (~16× normal) Consistent hashing, 4 → 5 servers: ~1/(N+1) = 20% of keys move → only those miss DB briefly sees ~100k × 0.20 = 20k queries/s (~4× normal) and it shrinks with N: at 100 → 101 nodes only ~1% move, ~1k extra q/s on top of 5k — a blip, not a surge ``` So consistent hashing turns a 16× cliff into a bounded bump that keeps shrinking as the fleet grows. The bump is real, though: every moved key is cold on its new node, and no amount of ring cleverness pre-warms it. Plan the resize for a low-traffic window and warm caches if you can. The failure that actually pages people is **cascading overload**. A node dies and its share of traffic — about `1/N` of the fleet — has to land somewhere. Without vnodes, all of it slams the single clockwise neighbor: that node's load roughly doubles, it tips over, its load lands on *its* neighbor, and the ring unzips one node at a time. Vnodes are the fix. With 100 vnodes per node the dead node's keys scatter across all `N−1` survivors, so each absorbs only ~`1/(N−1)` extra — a few percent, not a doubling. What vnodes do *not* fix is the cold-cache surge underneath: those redistributed keys are all misses on their new owners, so the DB still eats a burst while the caches refill. Even distribution of the load doesn't make the load disappear. ## Things you should now be able to answer If you got here from that hypothetical 3am page, here is what consistent hashing gives you: the ability to add a server without melting your database. The five questions below are the ones interviewers reach for — work through each one in your own words before moving on. - Why does `hash(key) % N` break when N changes? How much data moves? - What is a virtual node and why do we need them? - Why does Cassandra use consistent hashing? - When would jump hashing beat ring-based consistent hashing? - A new node is added to the ring. Which keys move and which don't? ## Further reading - Karger et al., "Consistent Hashing and Random Trees" (1997) — the original paper - DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store" (2007) - Lamping & Veach, "A Fast, Minimal Memory, Consistent Hash Algorithm" (2014) — jump hashing (arXiv:1406.2294) - Cassandra docs: "How data is distributed across a cluster (using virtual nodes)" — Datastax/Apache Cassandra documentation on vnode tuning ## Frequently asked questions Q: What is consistent hashing and why is it better than hash-mod-N sharding? A: Consistent hashing places both servers and keys on a shared hash ring spanning 0 to 2^32-1, assigning each key to the next clockwise server. Unlike hash(key) % N, which remaps roughly N/(N+1) of all keys when the server count changes — about 80% when going from 4 to 5 nodes — consistent hashing moves only ~1/(N+1) keys, so a cache cluster survives scaling events without a mass-miss storm. Q: What are virtual nodes and why does consistent hashing need them? A: Virtual nodes (vnodes) give each physical server 100–256 positions on the ring instead of one, derived from hash(server + "#" + i). Without them, random placement clusters servers unevenly and one node can own 60% of the ring while another owns 5%. The standard deviation of load scales as ~1/sqrt(V), so 100 random vnodes lands each server within roughly ±10% of 1/N and 256 within ~±6%; near-perfect balance needs a deterministic token allocator, not more random vnodes. When a server fails its keys also scatter across all survivors rather than flooding a single neighbor. Q: How many virtual nodes per server do Cassandra and other real systems use? A: The typical range is 100–256 vnodes per server. Cassandra 3.x used 256 random positions per node; Cassandra 4.x dropped to 16 by introducing a deterministic token allocator that achieves similar balance with far less churn at bootstrap time. The right count depends on whether the allocator picks positions randomly or deterministically. Q: When should I use jump hashing instead of ring-based consistent hashing? A: Use jump hashing when your buckets are numbered 0 through N-1 and you only ever add capacity at the end — you cannot remove an arbitrary node from the middle. It runs in O(log N) with zero memory and fits in about 5 lines of C. Ring-based consistent hashing is the standard answer whenever nodes can join or leave in arbitrary order, which covers most cache and database clusters. Q: What is the lookup cost and memory cost of consistent hashing with virtual nodes? A: Lookup is O(log V) binary search over the sorted vnode list, where V equals servers multiplied by vnodes per server. Memory cost is trivial: 1000 servers with 100 vnodes each produces 100,000 ring entries, well within any practical budget.