Consistent Hashing

Why This Matters

Every distributed system has a key-to-node mapping problem. You have N machines and billions of keys — how do you decide which machine owns which key? And when a machine joins or leaves (which happens constantly in production), how do you redistribute keys without moving everything?

The naive answer — hash(key) % N — works perfectly for a fixed number of nodes. But the moment N changes, nearly every key maps to a different node. Adding one machine to a 10-node cluster causes ~90% of keys to remap. For a distributed cache, that means 90% cache misses. For a sharded database, that means 90% of data needs to physically migrate. At scale, this makes cluster membership changes catastrophic.

Consistent hashing solves this by mapping both keys and nodes onto a shared circular hash space. When N changes, only ~1/N of keys need to move. This property — incremental membership changes cause incremental data movement — is what makes distributed caches, databases, and storage systems operationally viable.

Interviewers use consistent hashing as a fluency check. If you can explain the ring, virtual nodes, and the add/remove behavior cleanly in under 60 seconds, you signal familiarity with distributed systems fundamentals. If you stumble on virtual nodes or claim "no keys move," you signal a gap that casts doubt on your distributed systems depth.

The 60-Second Version

• Hash both keys and nodes onto the same circular space (0 to 2^32 - 1). A key belongs to the first node found clockwise from its hash position.
• Without virtual nodes, distribution is wildly uneven — some nodes absorb roughly 3x the keys of others due to random clustering on the ring.
• Virtual nodes fix this: each physical node maps to 100–200 points on the ring, smoothing the distribution to under 10% variance with 150+ vnodes.
• Adding a node: only ~1/N keys migrate (the new node absorbs a slice from its clockwise neighbor). Everything else stays put.
• Removing a node: its slice transfers to the next clockwise node. Again, ~1/N keys move — not the full reshuffle you get with modular hashing.
• This is the property that matters at scale: incremental membership changes cause incremental data movement.
• You should be able to articulate ring + vnodes + add/remove cleanly in under 60 seconds. Interviewers treat this as a fluency check.

How Consistent Hashing Works

The Problem with Modular Hashing

Start with the simplest distribution: node = hash(key) % N. If you have 10 nodes, key "user:42" hashes to node 7, key "session:99" hashes to node 3, and so on. Perfectly balanced, O(1) lookup.

Now add an 11th node. hash(key) % 11 gives a completely different result from hash(key) % 10 for most keys. Roughly 10/11 (91%) of all keys now map to a different node. For a cache cluster, every one of those remapped keys is a cache miss that hits the database. For a storage cluster, every remapped key is data that needs to physically move.

# Modular hashing: adding 1 node to 10
Before: hash("user:42") % 10 = 7  → Node 7
After:  hash("user:42") % 11 = 3  → Node 3  (moved!)

Keys moved: ~(N-1)/N = 9/10 = 90%

This is unusable for any system that adds or removes nodes during operation.

The Ring

Consistent hashing maps both keys and nodes onto a circular hash space, typically 0 to 2^32 - 1. Each node is placed at one or more positions on the ring based on its hash. Each key is placed on the ring based on its hash, and it belongs to the first node found by walking clockwise from the key's position.

# Ring assignment (simplified)
Ring positions: 0 ──────────── 2³²

Node A at position 1000
Node B at position 3500
Node C at position 7200

Key "user:42" hashes to 2800 → walks clockwise → Node B (at 3500)
Key "session:99" hashes to 5100 → walks clockwise → Node C (at 7200)
Key "cart:17" hashes to 800 → walks clockwise → Node A (at 1000)

Why This Helps: Node Addition

When a new Node D joins at position 5000:

• Keys between 3500 and 5000 (previously owned by Node C) transfer to Node D
• Everything else stays put
• Keys moved: approximately 1/N of total keys

Before Node D:
  Keys 3500-7200 → Node C

After Node D joins at 5000:
  Keys 3500-5000 → Node D (these moved)
  Keys 5000-7200 → Node C (unchanged)

Keys moved: ~1/4 (with 4 nodes) instead of ~3/4 with modular hashing

Why This Helps: Node Removal

When Node B (at position 3500) leaves:

• Keys between 1000 and 3500 (previously owned by Node B) transfer to Node C
• Everything else stays put
• Keys moved: approximately 1/N of total keys

The Virtual Node Problem

With only N physical positions on the ring, the distribution is poor. Random hash positions cluster unpredictably — some nodes end up with large arc segments (many keys) and others with small segments (few keys). With 10 physical nodes, the standard deviation is roughly O(1/√N) of total keys, meaning some nodes may hold 3x the average.

Virtual nodes (vnodes) solve this by giving each physical node multiple positions on the ring. Instead of one position, Node A gets 150 positions (Node A-0, Node A-1, ..., Node A-149), each hashed independently. The key assignment rule is the same — walk clockwise to the nearest vnode, then map that vnode to its physical node.

The effect: the arc segments are much smaller and more numerous, so the statistical variation averages out.

The production target is 150 vnodes per node. This keeps variance under 10% with reasonable memory overhead. Going higher yields diminishing returns.

Hashing Strategy Comparison

Not every distribution problem calls for consistent hashing. Here's the full landscape:

When NOT to Use Consistent Hashing

Consistent hashing adds complexity. It's justified when cluster membership changes frequently and you need minimal data movement. It's not justified when:

• Fixed cluster size: If your cluster never grows or shrinks, modular hashing is simpler and gives perfect balance.
• Infrequent changes with tolerance for brief reshuffles: If you resize once a quarter and can tolerate a brief performance dip, modular hashing with a migration step is simpler to operate and debug.
• Small, stable clusters (<10 nodes): The operational complexity of vnodes, ring metadata gossip, and anti-entropy repair exceeds the benefit.

Implementation Patterns

Ring Lookup

The ring is typically implemented as a sorted array of vnode positions. Lookup uses binary search:

# Ring data structure
ring = SortedArray<(position: uint32, node: PhysicalNode)>

# Lookup: find the node responsible for a key
lookup(key):
    pos = hash(key) % 2^32
    # Binary search for the first vnode with position >= pos
    idx = ring.binary_search_ceiling(pos)
    if idx >= ring.length:
        idx = 0  # wrap around the ring
    return ring[idx].node

Cost: O(log V) where V is total vnodes across all physical nodes. For 100 nodes × 150 vnodes = 15,000 entries, that's ~14 comparisons per lookup — negligible.

Node Addition with Warming

Adding a node to a consistent hash ring is operationally dangerous if done naively. The new node starts with an empty cache/store, and ~1/N of keys now route to it — all cache misses that stampede the database.

# Safe node addition procedure
add_node(new_node):
    # 1. Compute which key ranges will move to the new node
    ranges = compute_key_ranges(new_node, ring)

    # 2. Copy data for those ranges from the current owner
    for range in ranges:
        current_owner = ring.lookup(range.start)
        copy_data(current_owner, new_node, range)

    # 3. Only add to ring after data is copied (warm)
    ring.add(new_node)

    # 4. Verify: new node serves requests for its ranges
    # Old owner can delete transferred data after confirmation

Staff insight: Treat node addition as a deployment, not a config change. Warm the node before adding it to the ring.

Replication on the Ring

Production systems don't store a key on just one node. They replicate to the next K clockwise nodes on the ring (typically K=3). This means:

• Node failure doesn't require emergency data movement — the replica already has the data
• Reads can be served from any replica (with consistency implications)
• The ring must skip vnodes that belong to the same physical node when selecting replicas

# Replication: store on N clockwise distinct physical nodes
replicate(key, value, replication_factor=3):
    pos = hash(key) % 2^32
    nodes_used = Set()
    idx = ring.binary_search_ceiling(pos)

    while len(nodes_used) < replication_factor:
        node = ring[idx % ring.length].node
        if node not in nodes_used:
            node.store(key, value)
            nodes_used.add(node)
        idx += 1

Visual Guide

Ring Mechanics

When Node D joins at position 5000: Only keys between 3500–5000 move from Node C to Node D. Everything else stays put.

When Node B leaves: Keys between 1000–3500 transfer to Node C (the next clockwise node). Only ~1/3 of keys move.

Decision Tree: Which Hashing Strategy?

The Numbers That Matter

How This Shows Up in Interviews

Scenario 1: "How would you distribute keys across cache nodes?"

Do not default to consistent hashing. Say: "Two questions first. Does the cluster size change? If it's a fixed 10-node cluster that never grows, modular hashing (key % 10) gives perfect balance with O(1) lookup — simpler to operate and debug. But if we add or remove nodes during operation, modular hashing remaps ~90% of keys — a cache miss storm. For a dynamic cluster, consistent hashing with 150 vnodes per node keeps variance under 10% and moves only ~1/N of keys per membership change. The operational complexity is justified only if membership changes are frequent."

Scenario 2: "Add 4 nodes to a 12-node cache cluster during a traffic spike" (Full Walkthrough)

This tests operational maturity around consistent hashing. Here's how a Staff engineer works through it:

Step 1 — Quantify the data movement. "Adding 4 nodes to 12 means ~4/16 = 25% of keys will migrate to the new nodes. The other 75% stay on their current nodes. With 150 vnodes per node, the distribution across the 4 new nodes is roughly even — each absorbs ~6.25% of total keys."

Step 2 — The migration window is the danger zone. "Those 25% of keys are now cache misses on the new nodes. If we're at 100K QPS with a 95% hit rate, that's 5K misses/sec normally. During migration, an additional 25K keys/sec will miss because they've been remapped to empty nodes. That's 30K misses/sec hitting the database — 6x normal load. The database may not survive."

Step 3 — Warm before adding. "We copy the key ranges that will migrate to the new nodes before adding them to the ring. The old nodes still serve traffic. Once the new nodes have warm caches (we can verify by checking the data transfer is complete), we update the ring. Miss rate during transition: near zero."

Step 4 — Stagger the addition. "Don't add all 4 nodes simultaneously, even with warming. Add one at a time with a 5-minute observation gap. Each addition moves ~1/13, ~1/14, ~1/15, ~1/16 of keys — manageable chunks. Monitor hit rate and database load between each addition."

Step 5 — Singleflight during transition. "Enable request coalescing on the new nodes. Even with warming, some keys will be missed due to writes that occurred during the copy window. Singleflight ensures that concurrent misses for the same key result in only one database query, not hundreds."

Why this is a Staff answer: It quantifies the blast radius (25% key movement → 6x miss rate), proposes a zero-downtime migration (warm then add), stages the rollout (one node at a time), and addresses the edge case (writes during copy window → singleflight).

Scenario 3: "A node just died. What happens?"

With replication factor K=3, the failed node's keys are already replicated on 2 other nodes. Reads are served by replicas immediately — no cold start. The ring removes the dead node's vnodes, and the keyspace is redistributed to the clockwise neighbors. Anti-entropy repair runs in the background to bring the new owners' replica count back to K=3.

Scenario 4: "Why not just use modular hashing?"

This is a trap. The right answer is "it depends." If the cluster is fixed or changes rarely and you can tolerate a brief cold-cache period, modular hashing is simpler. Consistent hashing's benefit scales with the frequency of membership changes and the cost of key movement. Don't default to consistent hashing without justifying why the operational complexity is worth it.

In the Wild

Amazon DynamoDB: Consistent Hashing with Virtual Nodes

DynamoDB's partition assignment uses consistent hashing with virtual nodes as described in the original Dynamo paper (2007). Each partition maps to multiple vnodes on the ring, and data is replicated across 3 nodes in different availability zones. When a node fails, the ring adjusts and replicas serve traffic immediately. When the DynamoDB team needs to add capacity, they split the busiest partition's key range and assign the new half to a different node — a targeted rebalancing that moves exactly 50% of one partition, not a global reshuffle.

The Staff-level insight: DynamoDB doesn't use consistent hashing to distribute all keys across all nodes. It uses it to distribute partitions across nodes, and then distributes keys across partitions using range-based partitioning. This two-level indirection means they can rebalance at the partition level without touching the key-to-partition mapping.

Discord: Millions of Guilds Across Cache Nodes

Discord uses consistent hashing to distribute guild (server) data across their cache and state clusters. Each guild is a unit of distribution — all messages, member lists, and presence data for a guild route to the same set of nodes. When they scale their cache cluster (which happens frequently as Discord grows), consistent hashing ensures that only ~1/N of guilds migrate per node addition. They use guild-ID-based vnodes to ensure even distribution, since guild sizes vary enormously (from 2-person DMs to million-member communities).

The Staff-level insight: The choice of guild ID as the hash key is a tradeoff. It keeps all data for one guild co-located (good for read locality), but means that a single viral guild (millions of members) can create a hot node. Discord handles this with a secondary mechanism: hot guild detection → dedicated node assignment → bypass the ring for the hottest guilds.

Apache Cassandra: Token Ranges and Vnodes

Cassandra pioneered the production use of consistent hashing with virtual nodes. Each Cassandra node owns multiple token ranges on the ring (256 vnodes by default, configurable down to 1). When a new node joins the cluster, it claims token ranges from existing nodes, and Cassandra streams the corresponding data in the background — a process called "bootstrap." The entire operation is online; the cluster continues serving reads and writes throughout.

The Staff-level insight: Cassandra's default of 256 vnodes is higher than the 150 recommended for cache systems because Cassandra uses vnodes for data storage, not just cache routing. More vnodes mean more granular rebalancing (smaller chunks to stream) but also more metadata to gossip. Cassandra 4.0 introduced a "token allocation" algorithm that places vnodes optimally rather than randomly, reducing variance to near-zero even with fewer vnodes.

Staff Calibration

The sections below are calibration tools for Staff-level interviews. If you already understand consistent hashing mechanics, start here to sharpen the framing that separates L5 from L6 answers.

What Staff Engineers Say (That Seniors Don't)

Common Interview Traps

• Forgetting virtual nodes entirely. Presenting the naive ring without vnodes will trigger "what about hot spots?" — and you'll have nowhere to go.
• Claiming "no keys move" when a node is added. Keys do move. The win is that only 1/N of them move, not (N-1)/N.
• Ignoring the operational cost of rebalancing. During rebalancing, you need replication and consistency mechanisms to avoid serving stale or missing data. The ring update is instant; the data migration is not.
• Defaulting to consistent hashing for every distribution problem. Interviewers use "how would you distribute keys?" as a probe to see whether you reason about tradeoffs or just pattern-match.
• Assuming consistent hashing is always the right answer. For a 3-node cluster that rarely changes, modular hashing is simpler and has perfect balance. Justify the complexity.
• Ignoring replication in the ring. Production systems replicate keys to K clockwise neighbors (typically K=3). Node removal means the replica already has the data — no cold start.
• Forgetting that vnodes have memory cost. 150 vnodes × 1,000 nodes = 150K entries in the ring. This is fine in memory but needs to be gossiped across the cluster for membership changes. At 10K nodes, gossip convergence time becomes a design concern.

Practice Drill

Where This Appears

These playbooks apply consistent hashing to complete system design problems with full Staff-level walkthroughs, evaluator-grade rubrics, and practice drills.

• Distributed Caching — Multi-node cache topologies, shard-key selection for cache clusters, and the operational playbook for scaling cache nodes without thundering herds
• Load Balancer — Consistent hashing for session-sticky routing, why round-robin breaks statefulness, and the tradeoff between even distribution and session affinity
• Rate Limiting — Distributed rate limit counters across multiple nodes, hash-based request routing for per-client isolation, and the consistency challenge of counting across shards
• Database Sharding — Hash-based shard key selection, shard splitting and merging, and why consistent hashing enables online shard rebalancing without downtime

Related Technologies: Redis · Cassandra · DynamoDB