Consistent Hashing

Why This Matters#

Consistent hashing is not a hashing question. Every candidate can draw the ring. The interview question hiding underneath is: when the set of machines changes, how much data moves, how fast, and who notices? Adding one node to a cluster sounds like a capacity event. With the wrong placement scheme it is a cache-wide miss storm, a multi-hour data migration, or a hot spot that pages someone at 3am.

The textbook answer — "hash the key onto a ring, walk clockwise to the next node" — is correct and incomplete. It says nothing about load imbalance (a plain ring with 10 nodes typically gives the busiest node ~3× its fair share), nothing about replication and failure domains, nothing about hot keys (which no hash function can fix), and nothing about the operational reality that membership changes are the most dangerous routine operation a stateful system performs.

Staff engineers treat placement as a contract: a function from key to owner that many clients must agree on, that changes rarely and deliberately, and whose changes are throttled, observable, and reversible. They also know when not to use a ring at all — many production systems (Redis Cluster, Kafka, most sharded SQL) use a fixed number of logical partitions and a directory instead, because it makes rebalancing an explicit, controllable operation rather than a side effect of membership.

The 60-Second Version#

• Modulo hashing moves almost everything. hash(key) % N → % (N+1) remaps ~N/(N+1) of keys: going from 10 to 11 nodes moves ~91%. For a cache, that's a near-total miss storm.
• A consistent-hash ring moves ~1/(N+1). Adding an 11th node moves ~9% of keys, all of them to the new node. That minimal disruption is the whole point.
• A plain ring is badly balanced. With one token per node the busiest node owns ~(ln N) × its fair share in expectation — ~3× at N=10. Virtual nodes (100–256 tokens per node) bring the spread to roughly ±10% or better.
• Rendezvous (HRW) hashing gives minimal disruption and perfect balance with no ring state — at O(N) hash computations per lookup. Excellent for N ≤ a few hundred.
• Jump consistent hash is 5 lines, O(ln N), zero memory, near-perfect balance — but buckets are numbered 0..N−1, so you can only add or remove at the end. Ideal for sharded storage where you control numbering, useless for a cache fleet where arbitrary nodes die.
• Consistent hashing with bounded loads caps every node at (1+ε) × average load (ε ≈ 0.25) by spilling to the next node — fixes skew from uneven key popularity, not just uneven key counts.
• No hash function fixes a hot key. One celebrity key at 200K RPS lands on one node regardless of algorithm. That's a replication/caching problem, not a placement problem.

How Consistent Hashing Works#

The Problem It Solves#

You have K keys and N servers. You need a function owner(key) that every client computes identically, that spreads keys evenly, and that changes as little as possible when N changes.

Why Virtual Nodes Work#

Each physical node's share of the ring is the sum of v random arcs. Summing more arcs averages out the variance, so the spread shrinks roughly as 1/√v:

A second benefit: when a node dies, its v arcs are scattered across the ring, so its load spreads over many survivors instead of landing entirely on its single clockwise neighbor — which would otherwise double that neighbor's load at exactly the wrong moment.

Key Terms#

Where It Lives#

• Client-side routing — cache clients (Memcached ketama, many Redis clients), gRPC/Envoy ring-hash and Maglev load balancing policies.
• Storage placement — Dynamo-style stores (Cassandra, Riak, DynamoDB's internal partitioning lineage) place data on a token ring.
• L4 load balancers — Google Maglev and similar hash flows to backends so a connection keeps hitting the same backend across balancer instances.
• Stream/queue partitioning — Kafka uses hash(key) % partitions, which is not consistent: adding partitions changes key → partition mapping for existing keys.

Core Strategies#

Strategy 1: The Ring with Virtual Nodes#

build_ring(nodes, vnodes_per_node = 128):
    ring = SortedMap<uint64, Node>()
    for node in nodes:
        for i in 0 .. vnodes_per_node - 1:
            ring.put(hash64(node.id + "#" + i), node)
    return ring

owner(ring, key):
    h = hash64(key)
    entry = ring.ceiling(h)             # first token clockwise from h
    return entry ? entry.value : ring.first().value   # wrap around

preference_list(ring, key, replicas = 3):
    result = []
    for (token, node) in ring.walk_clockwise_from(hash64(key)):
        if node not in result and node.rack not in racks_of(result):
            result.append(node)
        if len(result) == replicas: break
    return result

When to use: Caches and Dynamo-style stores where nodes join and leave unpredictably and many clients route independently.

Failure mode: Too few vnodes and one node carries 2–3× its share; too many and ring rebuilds, gossip payloads, and per-token repair bookkeeping get expensive. Cassandra lowered its default from 256 tokens per node to 16 in version 4.0 (paired with a smarter token allocator) precisely because 256 random tokens made repair and streaming slower and availability worse at scale.

Strategy 2: Rendezvous (Highest Random Weight) Hashing#

owner(nodes, key):
    best, best_score = null, -inf
    for node in nodes:
        score = hash64(node.id + "|" + key)
        if score > best_score:
            best, best_score = node, score
    return best

# Weighted variant (node.weight ∝ capacity):
#   score = -node.weight / ln(uniform01(hash64(node.id + "|" + key)))

When to use: N up to a few hundred, where you want perfect balance, minimal disruption, and no ring data structure to keep in sync. Top-k for replication is trivial: take the k highest scores.

Failure mode: O(N) per lookup. At N=1,000 and ~20ns per hash, that's ~20µs per lookup — fine for per-request shard routing, too slow for per-packet load balancing.

Strategy 3: Jump Consistent Hash#

jump_hash(key: uint64, num_buckets: int) -> int:
    b, j = -1, 0
    while j < num_buckets:
        b = j
        key = key * 2862933555777941757 + 1
        j = int((b + 1) * (2^31 / ((key >> 33) + 1)))
    return b

Published by Lamping and Veach (Google, 2014). Expected O(ln N) iterations, no memory, and near-perfectly even distribution.

When to use: Sharded storage where shards are numbered and you grow by appending shards (0..N−1 → 0..N). Each shard is itself replicated, so "a node died" never means "bucket 7 disappears."

Failure mode: Removing an arbitrary bucket isn't supported. If bucket 3 of 10 dies and you renumber, you remap far more than 1/N of keys. Using jump hash directly over a fleet of unreliable cache hosts is a design error.

Strategy 4: Maglev Hashing#

Google's Maglev L4 load balancer builds a lookup table of prime size M (the paper uses 65,537) by letting each backend fill slots according to its own permutation. Lookup is a single array index.

When to use: Per-packet or per-connection routing at millions of packets per second, where O(1) lookup matters and a small amount of extra disruption on backend changes is acceptable.

Failure mode: Table rebuild on every backend change; M must be much larger than N (roughly 100× or more) for good balance.

Strategy 5: Fixed Logical Slots + Directory#

NUM_SLOTS = 16384                      # fixed forever — choose once

slot(key)  = crc16(hash_tag(key)) % NUM_SLOTS
owner(key) = directory[slot(key)]      # slot → node map, versioned

move_slot(s, from, to):
    directory.mark_migrating(s, from, to)
    stream_keys(s, from, to, throttle = 50MB/s)
    directory.commit(s, to, version + 1)   # clients refresh on MOVED/redirect

When to use: Data stores where rebalancing must be explicit, throttled, and reversible. Redis Cluster (16,384 slots), Couchbase (1,024 vBuckets), and Elasticsearch (fixed primary shards) all use variants of this.

Failure mode: The slot count is a one-way door. Too few slots (e.g., 64) and you can't spread across more than 64 nodes or rebalance finely; too many and the directory and per-slot overhead grow. The directory itself becomes a critical control plane.

Rebalancing: The Hard Sub-Problem#

"Only 1/(N+1) of keys move" is the promise. What it hides is that moving keys is the most dangerous routine operation a stateful system performs. The algorithm tells you which keys move. It says nothing about how fast, what breaks while they're moving, or what happens when membership flaps.

What Rebalancing Actually Costs#

The Four Rules of Safe Rebalancing#

1. Throttle the movement. Cap streaming bandwidth (e.g., 50–200MB/s per node) so client p99 stays within SLO. A rebalance that finishes in 2 hours and breaks the SLO is worse than one that finishes in 8 and doesn't.
2. Move one thing at a time. Add one node, let it settle, add the next. Parallel membership changes compound donor load and make failures impossible to attribute.
3. Damp membership flapping. A node that's marked down and up every 30 seconds causes repeated ownership churn. Require N consecutive failed health checks (e.g., 3 × 5s) before removal and a longer hold-down (e.g., 5–10 minutes) before rejoining the ring.
4. Keep old and new owners readable during migration. Double-read (new owner, fall back to old) or redirect (MOVED/ASK in Redis Cluster) so a key is never unreachable mid-move.

The Membership Agreement Problem#

Consistent hashing assumes every client has the same view of the ring. When they don't, the same key routes to two different owners:

Client A view: [n1..n10]        → key "user:42" → n7
Client B view: [n1..n11]        → key "user:42" → n11
Result for a cache: two copies, one stale after the next write.
Result for a store: writes split across owners until views converge.

🎯 Staff Move: "The ring gets me minimal movement, but I care more about who agrees on the ring. For the cache I'll accept a few seconds of divergent views, because the worst case is a duplicate entry with a short TTL. For the store I won't — clients get redirected by the owning node and the placement map is versioned, so a stale client finds out on its next request."

Hot Keys Are Not a Placement Problem#

A perfectly balanced key distribution still produces a hot node when request popularity is Zipfian. If one key receives 200K RPS and a node serves 100K RPS, no algorithm helps. Fixes live elsewhere:

Visual Guide#

The Ring with Virtual Nodes#

Choosing a Placement Scheme#

Adding a Node to a Dynamo-Style Store#

Node Lifecycle#

Implementation Patterns#

Replication on the Ring#

Walk clockwise and collect the next R distinct physical nodes — and in production, distinct racks or availability zones. Without the physical-node check, two vnodes of the same machine can both land in a preference list, and a single host failure takes out two of three replicas.

Weighted Nodes#

Heterogeneous hardware? Give a node vnodes in proportion to capacity (a 2× machine gets 2× tokens) or use weighted rendezvous. Weights are also the gentlest way to drain a node: lower its weight in steps (100% → 50% → 0%) instead of removing it in one shot.

Co-location with Hash Tags#

Multi-key operations need keys on the same owner. Redis Cluster hashes only the substring inside {…}, so {user:42}:profile and {user:42}:cart share a slot. The tradeoff: a hash tag with enormous fan-in ({global}) recreates a single hot shard.

Bounded Loads#

owner_bounded(ring, key, loads, eps = 0.25):
    cap = ceil((1 + eps) * total_load / num_nodes)
    for node in ring.walk_clockwise_from(hash64(key)):
        if loads[node] < cap:
            return node

Every node is capped at (1+ε) × average. With ε=0.25 no node exceeds 125% of the mean; the price is that some keys are served by a non-owner (a cache miss there) and a small increase in keys that move when load shifts. HAProxy exposes this as hash-balance-factor.

Hash Function Choice#

• Use a fast non-cryptographic 64-bit hash — MurmurHash3, xxHash — not MD5/SHA (5–10× slower, no benefit for placement).
• Pin the exact function, seed, and byte encoding across every language. A Java client hashing UTF-16 strings and a Go client hashing UTF-8 bytes produce different rings. This is the most common cross-team consistent-hashing bug.
• Never change it in place. Changing the hash function remaps ~100% of keys. Treat it as a migration.

When NOT to Use Consistent Hashing#

• Small, static clusters. Three Postgres shards that will never change can use a lookup table. A ring adds nothing but a hash function to get wrong.
• Range queries matter. Hashing destroys key order. If you need WHERE ts BETWEEN … or prefix scans, use range partitioning (with split/merge) — Bigtable, HBase, and Spanner do.
• Placement must follow business rules. Tenant isolation, data residency ("EU data stays in EU"), or dedicated hardware for a large customer need a directory, not a hash.
• You need per-key ordering under growth. Any hash-based scheme moves some keys when membership changes; if ordering is sacred, fix the partition count up front.

Failure Scenario: The Scale-Out That Took Down the Database#

t=0      Launch prep: cache team adds 4 nodes to a 12-node fleet by changing % 12 to % 16.
t=+30s   Config reaches 50% of 400 app servers. Hit rate drops 95% → 60%.
t=+60s   Config at 100%. Hit rate ~25%. DB read QPS 15K → 220K.
t=+90s   DB CPU 100%, connection pool exhausted; p99 for every DB-backed endpoint > 5s.
t=+2min  Incident declared. Rolling back the config remaps keys again — a second miss storm.
t=+12min Rollback complete; hit rate recovers over the TTL window (~10 min).
t=+25min Service normal. Launch delayed a week.

Detection: cache.hit_rate drop > 20 points in 5 minutes; db.read.qps > 3× baseline; placement.keys_moved (if you emit it) — most teams don't, which is why this is found by the DB alert. Blast radius: every service reading through the cache — and every service sharing the database. Mitigation: request coalescing and load shedding at the cache client; roll forward gradually rather than rolling back instantly (both directions remap). Prevention: consistent-hash ring in the shared client library; membership changes one node at a time; cache.hit_rate as a deploy gate. Owner: cache platform team owns the client library and the scale-out procedure; the DB team gets a say in the gate threshold.

Operational Reality Matrix#

The Numbers in Context#

How This Shows Up in Interviews#

Scenario 1: "How do you distribute keys across your cache cluster?"#

Do not stop at "consistent hashing." Say: "Ring with ~150 vnodes per node in the client library, so adding a node invalidates ~1/N of keys instead of ~all of them. I'd pin the hash function — xxHash64 over UTF-8 bytes — across every client language. And I'd call out that this does nothing for hot keys; the top few hundred keys get a local L1 with a 2-second TTL."

Scenario 2: "We need to add 5 nodes to our 20-node store during peak season." (Full Walkthrough)#

Step 1 — Size the movement. "Going from 20 to 25 nodes moves ~20% of the data to the new nodes. The cluster holds 40TB, so ~8TB streams. At a 100MB/s per-donor throttle with all 20 donors contributing, the raw transfer is under 2 hours — but I won't add all 5 at once."

Step 2 — Sequence it. "One node at a time. Each join moves ~1/21, 1/22… of the data, roughly 1.6–1.9TB each. I let each settle and check that client p99 and donor disk utilization return to baseline before the next. Total wall clock: likely 1–2 days, which is why this happens two weeks before peak, not during it."

Step 3 — Protect latency. "Streaming throttle tuned so donor p99 stays under SLO — I'd start at 50MB/s and raise it while watching client.read.latency.p99 and disk.io.util on donors. Compaction after the move is also throttled."

Step 4 — Keep data reachable. "While ranges move, writes go to both old and new owners and reads can be served by either. The node only moves to NORMAL once streaming completes and a repair pass confirms the ranges."

Step 5 — Plan the rollback. "If a joining node misbehaves, I decommission it — its ranges stream back. That's why one-at-a-time matters: a rollback moves 1/21 of the data, not 1/5."

Step 6 — Owners. "Storage platform owns the procedure and the throttle defaults; the product team owns the go/no-go on the date because they know the peak calendar."

Why this is a Staff answer: It converts "consistent hashing moves 1/N" into terabytes and hours, sequences the change for reversibility, protects the SLO during movement, and puts the scheduling decision with the people who own the business risk.

Scenario 3: "One cache node is at 95% CPU while the others sit at 30%."#

This tests whether you can tell key-count skew from popularity skew. "First I'd check whether that node owns more keys than its share — if yes, it's token imbalance and more vnodes or rebalanced tokens fix it. If key counts are even but requests aren't, it's a hot key. Hashing can't fix that — I'd find the top keys with sampling, then replicate them or put an L1 in front. Bounded-load hashing is a good backstop so the overflow spills rather than melting one node."

Scenario 4: "Why doesn't Kafka just use consistent hashing for partitions?"#

This tests whether you understand what the partition contract promises. "Kafka's contract is per-key ordering within a partition. The default partitioner is hash(key) % partitions, so adding partitions changes the mapping for most keys and breaks ordering at the boundary. Consistent hashing would reduce that to ~1/N of keys but not to zero — some keys would still switch partitions mid-stream. The real answer is to over-provision partitions up front, because the partition count is effectively a one-way door."

Advanced Patterns#

The Principal Lens#

Why L7 Sees This Problem Differently#

A Staff engineer picks the right placement algorithm and runs the rebalance safely. A Principal engineer notices that the company has seven different rings — one in each team's cache client, one in the sharded Postgres router, one in the job scheduler, one in the WebSocket gateway — each with a different hash function, vnode count, membership source, and rebalance runbook. Each is correct in isolation. Together they mean every capacity change is a bespoke, risky procedure performed by a team that does it twice a year. At L7, placement stops being an algorithm and becomes infrastructure the org provides once: a placement contract, a membership source of truth, and a rebalancing service with throttles and observability built in.

The Org-Level Fault Line#

Central placement service vs per-team hashing in client libraries.

The Principal position: shared library for stateless routing (caches, sticky LB), central slot directory for anything that stores data. The distinction is whether a wrong placement loses correctness or just costs a cache miss.

Cost Model#

Assumptions: DB read capacity ~$0.50 per 1K sustained RPS-month of headroom; storage node ~$1.5K/month; data transfer within an AZ ~free, cross-AZ ~$0.02/GB round trip; engineer ~$25K/month fully loaded.

The Principal argument at large scale isn't the algorithm — it's that 500 rebalances a year performed by hand is an incident generator. Automating the mover is cheaper than the incidents it prevents.

The 3-Year Evolution Path#

One-Way Doors vs Two-Way Doors#

The Standard I'd Write#

RFC: Key Placement and Rebalancing Standard (v1)

Scope: Any system that maps keys to nodes — caches, sharded stores, sticky routing, partitioned queues.

MUST:

1. Use the org placement library (xxHash64, seed 0, UTF-8 key bytes) for all hash-based routing. No hand-rolled hash functions.
2. Stores MUST use fixed logical slots (≥ 100× max expected nodes) with a versioned directory; stateless routing MAY use the ring library.
3. Rebalancing MUST be throttled (default 100MB/s per donor), MUST proceed one membership change at a time, and MUST be reversible.
4. Emit placement.keys_moved, placement.rebalance.bytes_remaining, node.load_ratio (node load ÷ mean), and alert when node.load_ratio > 1.5 for 10 minutes.
5. Replicas MUST land in distinct availability zones.

SHOULD: enable bounded loads (ε=0.25) for caches; identify top-100 keys continuously and replicate any above 20% of one node's capacity.

Exceptions: Latency-critical L4 routing (Maglev-style) is exempt from rule 1 but not rule 4.

Success metrics: zero miss-storm incidents from scale events; p99 node.load_ratio < 1.3 across fleets; median rebalance requires zero manual steps.

What I'd Tell the VP#

"Every time we add servers to one of our data systems, we move data around, and today each team does that with its own homegrown method. Twice this year, that caused an outage during a routine capacity add. We want one shared way to decide where data lives and one tool that moves it safely and slowly. That's a team of four to six engineers. The payoff is that adding capacity becomes a non-event instead of a risk, which matters most right before peak season. It also lets us react to viral traffic spikes automatically instead of paging people."

Principal Interview Signals#

Staff answers that L7 interviewers find insufficient:

• "We'll use consistent hashing with 256 vnodes." — Correct for one system; silent on the other six rings in the company.
• "Rebalancing is fine because only 1/N of keys move." — Ignores that 1/N of 10PB is still a multi-day, cross-AZ, SLO-threatening operation.
• "We'll add more partitions later if we need them." — Treats a one-way door as a two-way door.

In the Wild#

These are public, documented examples.

Amazon Dynamo (2007)#

The Dynamo paper described Amazon's internal key-value store behind the shopping cart. It placed data on a consistent-hash ring with virtual nodes, replicated each key to the next N nodes on its preference list, used gossip for membership, and used hinted handoff so writes succeeded while a replica was down. The paper also candidly reported that its original random-token strategy made bootstrapping and archival painful, and that Amazon moved to dividing the ring into equal-sized fixed partitions assigned to nodes — effectively the "fixed slots" strategy.

Staff insight: The most-cited consistent-hashing paper ends up recommending fixed partitions for operability. Quote that in an interview: the algorithm that minimizes movement isn't always the one that's easiest to operate.

Google Maglev (2016)#

Google's Maglev is a software L4 load balancer running on commodity servers. Each Maglev machine independently computes the same lookup table (size 65,537 in the paper) from the backend list, so any Maglev instance sends a given connection to the same backend — no shared state between balancers. The design trades a little extra disruption on backend changes for O(1) lookups and near-perfect balance at line rate.

Staff insight: Maglev chooses a different point on the balance/disruption/lookup-cost curve because the workload is per-packet. Naming why you'd pick Maglev over a ring (lookup cost at millions of packets per second) is the signal.

Vimeo and Consistent Hashing with Bounded Loads#

Vimeo engineers applied the bounded-loads algorithm (Mirrokni, Thorup, and Zadimoghaddam, 2016) to their video cache tier and contributed it to HAProxy, which exposes it as hash-balance-factor. Their public write-up described how plain consistent hashing overloaded the servers that happened to own popular content, and how capping each server's load and spilling the overflow kept cache locality while ending the overload.

Staff insight: Consistent hashing optimizes for key-count balance; real traffic has popularity skew. Bounded loads is the bridge — mention it whenever a cache or CDN tier appears in your design.

Staff Calibration#

What Staff Engineers Say (That Seniors Don't)#

Common Interview Traps#

• Using hash % N for anything that scales. 91% of keys move going from 10 to 11 nodes.
• Drawing a ring with one token per node. The busiest node owns ~3× its share at N=10. Say "vnodes" and a number.
• Believing consistent hashing fixes hot keys. It doesn't. Name the fix.
• Ignoring replicas' failure domains. Two vnodes of one host in a preference list, or three replicas in one AZ, is one failure away from data loss.
• Using jump hash over unreliable nodes. It only supports adding/removing at the end.
• Forgetting cross-language consistency. Same hash function, seed, and byte encoding everywhere.
• Treating rebalancing as instantaneous. It's terabytes over hours; throttle it and schedule it.
• Adding Kafka partitions to "scale" a keyed topic. You just broke per-key ordering.

Practice Drill#

Prompt: "We run a 12-node Memcached fleet behind 400 app servers using hash(key) % 12. We need to grow to 16 nodes next week for a launch. What do you do?"

Where This Appears#

• Distributed Caching — Client-side rings, miss storms on scale-out, and hot-key replication
• Database Sharding — Fixed slots vs rings, resharding, and the partition key as a one-way door
• Load Balancer — Maglev-style hashing, connection affinity, and bounded loads
• CDN & Edge Caching — Popularity skew and consistent hashing across edge caches
• Message Queues — Partition counts, keyed ordering, and why adding partitions breaks it
• Replicated Data Store — Preference lists, hinted handoff, and quorum on a ring
• Chat Messaging — Sticky routing of users to gateway hosts

Related Foundations & Patterns: Sharding & Partitioning · Consistency Models & Partition Behavior · Scaling Writes

Related Technologies: Cassandra · DynamoDB · Redis · Apache Kafka