System Design Interview: Design Consistent Hashing with Virtual Nodes

Problem and Applicable Scenarios

A distributed key-value store runs across three availability zones. It has 120 physical nodes, 24 TiB of logical data, three replicas, and two million key-placement lookups per second. A client or storage proxy must find the primary and two replicas locally; the request path cannot contact a central service for every lookup. Nodes join and leave because of scaling, maintenance, and failure. A membership change should move only the affected keys rather than cause a nearly complete cache cold start or data migration.

The scope is the placement layer from key to physical nodes and the safe ownership transition when membership changes. Read/write consistency, conflict resolution, the disk engine, and cross-region replication are outside the main design, but a strong answer must state that consistent hashing does not provide them. Assume a stable, well-distributed 64-bit hash. The data size, throughput, and SLOs are interview assumptions, not the reported scale of any company.

Current English and Chinese system-design interview material from 2026 explicitly covers consistent hashing, virtual nodes, and scaling. The Amazon Dynamo paper provides a primary-source example of consistent hashing for partition and replica placement. This question is suitable for senior backend, infrastructure, and distributed-systems roles because it turns “move less data” into a provable ownership rule, a versioned membership view, and a testable migration protocol.

What the Interviewer Is Evaluating

First, can the candidate explain why hash(key) % N fails when N changes instead of merely drawing a circle? A strong answer derives the remapping ratio and distinguishes fixed logical partitions from taking the modulus over live nodes.

Second, can the candidate separate balanced key counts from balanced request load? Virtual nodes spread many small ranges across physical nodes and can approximate capacity weights. A single extremely hot key still has one primary owner; adding virtual nodes does not split that key.

Third, can the candidate separate the data plane from the control plane? The data plane should perform lookups against a local, immutable ring snapshot. The control plane owns node identity, health, weight, snapshot version, and migration state. If every client immediately removes a node based on its own health check, the same key can acquire conflicting owners.

Fourth, does the candidate understand that consistent hashing only supplies placement? Replica diversity, completed data copying, failure recovery, and safe deletion all require additional protocols. “Walk clockwise to three nodes” is not a complete availability design.

Finally, can the candidate compare fixed logical partitions, rendezvous hashing, and jump consistent hash, then validate the choice against actual key distribution, membership flapping, and divergent snapshots? A memorized virtual-node count is not a substitute for evidence.

Clarifying Questions Before Answering

• Is this a cache or durable storage? A cache can refill after scaling. Durable data must be copied and caught up before

ownership changes.

• Can arbitrary members join and leave, or do numbered buckets only grow at the end? Arbitrary membership fits a ring or

rendezvous hashing. Sequential buckets that mostly append make jump consistent hash worth evaluating.

• Is load measured by key count, bytes, or QPS? Equal key counts do not imply equal capacity or traffic. Weighting and

rebalancing metrics must match the actual bottleneck.

• Do nodes have equal capacity? Heterogeneous nodes need weights. Token counts only approximate weights, so a fixed-seed

simulation and production metrics must verify the realized share.

• What failure-domain rules apply to replicas? Three copies in one availability zone all fail together. Replica selection

must skip the same physical node and enforce zone diversity.

• How long may migration take? A zero-downtime cutover needs snapshot versions, a bulk copy, incremental catch-up, and a

short period of dual reads or forwarding. A cold start permits a simpler path.

• Who publishes membership? Clients need an authoritative snapshot with an epoch and checksum. Independent membership

inference creates split ownership.

• Are range scans important? Hashing destroys business-key locality. Range-heavy workloads may need range partitioning or

a fixed logical-partition layer first.

30-Second Answer Framework

“I would not take the modulus over 120 live nodes. When the cluster grows to 121 nodes, uniform hashes and stable bucket IDs imply that about 120/121 of keys change buckets. I would place keys and virtual-node tokens in a fixed 64-bit hash space; the first token clockwise owns the key. A sorted token table supports binary search, so a lookup is O(log V). Each physical node owns many small ranges, and larger nodes receive more tokens. Replica selection continues clockwise but skips duplicate physical nodes and enforces availability-zone diversity. The control plane publishes immutable, epoch-versioned ring snapshots. Durable storage changes ownership only after copy and catch-up complete. I would validate movement, load variance, weights, and failure domains with a fixed-seed simulation, and handle hot keys separately because virtual nodes do not solve single-key skew.”

Step-by-Step Deep Dive

Step 1: Quantify the Remapping Cost of Modulo Hashing

The direct mapping is:

owner = nodes[hash(key) % N]

When stable bucket IDs grow from N to N + 1, a key retains its numeric bucket only if hash % N = hash % (N + 1). Consecutive integers are coprime. Across one complete N × (N + 1) residue cycle, exactly N hash values satisfy that equality. The retained fraction is therefore 1 / (N + 1), and the remapped fraction is N / (N + 1).

Growing this cluster from 120 to 121 nodes changes the expected owner of about 120/121 = 99.17% of keys. Roughly 23.8 TiB of the 24 TiB logical dataset receives a new placement. A cache may not physically copy those bytes, but it still experiences a nearly complete cold-miss event. This derivation assumes uniform hashes, stable bucket IDs, and a modulus over the live node count. If keys first map to a fixed number of logical partitions, and the control plane moves only selected partitions, live membership no longer changes the first mapping formula.

Step 2: Define the Ring, Tokens, and Local Lookup

Choose a fixed 64-bit hash function and encoding. Map both keys and virtual-node tokens into that space. Sort tokens as unsigned values and wrap from the maximum value to zero. The first token clockwise owns a key; a binary search that passes the end of the array returns the first token.

locate(key, snapshot):
  h = stableHash64(key)
  i = lowerBound(snapshot.sortedTokens, h)
  if i == snapshot.sortedTokens.length:
    i = 0
  return snapshot.sortedTokens[i].physicalNodeId

With V total tokens, lookup costs O(log V) and the snapshot uses O(V) memory. Token collisions need a deterministic ordering such as (token, physicalNodeId, vnodeIndex); map overwrite order is not a protocol. Use a persistent UUID or stable deployment identifier for a node. Using an ephemeral IP address causes an unnecessary membership change whenever a restarted node receives a new address.

Under ideal balance, the 121st equal-capacity node receives about 1/121 of the keys. For 24 TiB of logical data, expected movement is 24/121 TiB ≈ 203 GiB, drawn from many small ranges the new node acquires. This is an expectation for capacity planning, not a hard limit. Finite token counts, value-size variation, and access skew can all move the observed result away from 203 GiB.

Step 3: Use Virtual Nodes for Range Balance and Capacity Weights

With one token per physical node, random gaps can differ greatly, and a departing node transfers its whole range to one successor. Virtual nodes give each physical node many dispersed tokens, splitting a large range into smaller migration units. A failed physical node then transfers ranges to several successors rather than overloading one machine.

Do not copy a universal token count from an interview guide. Replay real or representative key, value-size, and QPS distributions while increasing tokens per node. Measure:

key_count_share, byte_share, qps_share
max_load / mean_load
coefficient_of_variation
snapshot_bytes and lookup_latency

Stop when additional tokens provide little balancing gain and snapshot, update, and binary-search costs remain within budget. For heterogeneous capacity, make a node's target token count approximately proportional to its weight; random tokens still produce a statistical approximation. When the system needs exact weights, explicit assignment of fixed logical partitions is usually easier to operate.

Virtual nodes smooth aggregate range ownership. A key responsible for 20% of requests still maps to one primary. Handle it with read replicas, request coalescing, a near cache, business-aware key splitting, or rate limits. Increasing virtual nodes from 100 to 1,000 does not change that fact.

Step 4: Design Replica Selection and the Snapshot Model

After finding the primary, continue clockwise and collect distinct physical nodes until there are three replicas. Skip another virtual token belonging to a physical node already selected. Availability-zone diversity must be a constraint, not a lucky property of three adjacent owners.

RingSnapshot {
  epoch,
  hashAlgorithm,
  tokens: [{ token, physicalNodeId, weight, zone, state }],
  checksum,
  activatedAt
}

Placement {
  keyHash,
  epoch,
  owners: [{ physicalNodeId, zone, role }]
}

The data plane atomically swaps immutable snapshots. A request records or carries its epoch; a server that observes an old version can return a version hint or forward to the current owner. The control plane validates physical-node uniqueness and failure domains for every replica set. If too few healthy nodes exist, it reports an under-replicated state instead of selecting the same machine twice and pretending to have three copies.

Consistent hashing proposes locations but does not define write acknowledgment. Durable storage must still decide how many replicas acknowledge a write, how reads reconcile versions, how repair verifies bytes, and whether a network partition favors consistency or availability.

Step 5: Make Membership Changes Versioned Migrations

A planned join can use this state machine:

joining -> copying -> catching_up -> active
active  -> draining -> removed

The control plane calculates the ownership difference from the current epoch. A joining node does not receive primary traffic. A background job copies affected ranges from old owners and verifies them by key version or log position. Writes made during the copy enter an incremental log or a dual-write path. After the bulk copy, the new node catches up. Only when the checksum and replica-health gates pass does the control plane publish a new epoch and atomically change routing. Old owners retain data for a bounded grace period to serve stale-snapshot requests and support rollback, then delete it.

Draining follows the same order: copy and catch up to new owners, publish a snapshot without the node, stop it, and finally reclaim old ranges. The mathematics of the ring identifies affected ranges; it does not replace copying, throttling, verification, or rollback. The migration worker also limits concurrent bytes so an expected 203 GiB move does not consume the foreground read/write budget.

Step 6: Separate Failure Handling from Membership Agreement

When a node fails abruptly, the system cannot copy from it first. The data plane serves from existing replicas while a repair worker rebuilds missing replicas on healthy nodes according to the authoritative membership epoch. A brief timeout should not immediately rewrite the ring, or flapping will trigger repeated migrations. A health manager uses consecutive failures, leases, or control-plane agreement to mark a node unavailable and distinguishes temporary forwarding from permanent removal.

All clients must observe one versioned membership sequence. If client A removes node X while client B still treats X as the primary, the same key can receive writes at different locations. A consensus-backed control plane can maintain ring configuration and distribute snapshots with epochs and checksums. During short version-skew windows, clients use server forwarding, dual reads, or an explicit retry protocol. “Everyone eventually receives the config” is not, by itself, a correctness mechanism.

If the control plane is unavailable, the data plane continues with its last verified snapshot. How long reads and writes can continue depends on replica consistency and the failure model. Individual nodes must not permanently rewrite the ring while the authoritative membership view is unavailable.

Step 7: Compare Alternatives Under the Actual Constraints

| Approach | Best fit | Lookup and state | Main cost | |---|---|---|---| | Ring with virtual nodes | Arbitrary membership; visible ranges and weights | Sorted tokens, O(log V) lookup | Snapshot and token tuning; migration protocol still required | | Rendezvous hashing | Smaller node set; direct top-one or top-k selection | Naive O(N) scoring per key | More compute at high node counts, but no ring and intuitive replicas | | Jump consistent hash | Sequential buckets that mostly append | Constant memory and fast bucket mapping | Awkward arbitrary removal; usually needs bucket-to-node indirection | | Fixed logical partitions | Controlled movement, precise weights, operational visibility | Key to partition, then control-plane placement | Partition metadata and a separate rebalancer |

If any stateless node can process any request, ordinary load balancing is simpler. Consistent hashing is valuable when a key must preserve an owner. If the workload is dominated by range scans, destroying key order may cost more than reduced movement saves. Choose the placement abstraction first and the algorithm second.

Step 8: Validate Properties, Load, and Failure Behavior

An offline test fixes the hash algorithm and seed, generates millions of synthetic keys, saves a baseline snapshot, and then performs joins, drains, and failures:

1. Measure movedkeys / totalkeys and prove keys outside the ownership-difference ranges do not move.
2. Compute max/mean and coefficient of variation by key count, bytes, and QPS, not just a key histogram.
3. Assign 1:2:4 weights, verify long-run shares approach the targets, and record diminishing returns from more tokens.
4. Check that every key's three replicas use distinct physical nodes and all three availability zones.
5. Run two epochs concurrently, drop snapshots, and corrupt checksums to test forwarding, retries, and old-version eviction.
6. Kill old and new nodes mid-copy and confirm an incomplete migration never deletes the only healthy copy.
7. Inject one hot key and repeated membership flapping to verify hotspot protection and membership debouncing independently.

Production monitoring includes adoption by epoch, key/byte/QPS skew, migration backlog and speed, old-version requests, forwarding rate, under-replicated ranges, hot keys, and hash-computation latency. A scaling operation is complete when these signals pass, not merely when the new node appears on the ring.

Strong Sample Answer

“I would first keep the scope to key placement. With a modulus over 120 live nodes, growing to 121 changes the bucket for about 120/121 of keys, which is close to a full remap of 24 TiB. Fixed logical partitions could avoid that problem. If I choose consistent hashing, I place keys and node tokens in a fixed 64-bit space and assign each key to the first token clockwise. Clients hold a sorted immutable snapshot and use binary search, so the hot path has no central call and costs O(log V).

Each physical node receives multiple virtual tokens to spread ranges and failure movement. Heterogeneous nodes get different token targets based on capacity. I would not declare 100 tokens per node without evidence; I would replay real key sizes and QPS and compare max-to-mean load, coefficient of variation, snapshot size, and lookup latency. Virtual nodes smooth ranges, while a single hot key still needs read replicas, request coalescing, key splitting, or rate limiting.

Replica placement walks clockwise to three distinct physical nodes and enforces all three availability zones. A consensus-backed control plane publishes ring snapshots with epochs and checksums. For a planned scale-out, the new node first copies its ranges and catches up incremental writes. A new epoch becomes active only after verification; old owners delete data after a grace period. An abrupt failure serves from healthy replicas and rebuilds them, because drawing the ring is not a recovery protocol.

Finally, I would use millions of fixed-seed keys to test movement, skew by keys/bytes/QPS, weights, and replica domains, then inject dual epochs, interrupted migration, membership flapping, and a hot key. If the targets are sequential buckets, I would compare jump hash. If precise, operator-controlled movement matters more, I would prefer fixed logical partitions.”

Common Mistakes

• Only drawing a ring → the answer never explains why modulo fails or how much moves → **derive the remapping ratio and

apply it to the dataset.**

• One point per physical node → random gaps skew ranges and one successor absorbs a failure → **use multiple tokens and

choose the count through replay.**

• Treating virtual nodes as a hot-key solution → one key still has one primary → **use replicas, request coalescing, key

splitting, or rate limits.**

• Taking the next three tokens as three replicas → they may belong to one machine or zone → **deduplicate physical nodes

and enforce failure-domain constraints.**

• Routing to a joining node immediately → durable data has not arrived yet → **copy, catch up, verify, publish the epoch,

and only then delete old copies.**

• Letting clients evict failed nodes independently → divergent membership creates split ownership → **publish versioned

snapshots from an authoritative control plane.**

• Claiming a join moves exactly 1/N → finite tokens and weights make ranges uneven → **state it as an expectation under

balance assumptions and measure the actual distribution.**

• Hard-coding “200 vnodes per node” → it ignores value size, QPS, snapshot size, and lookup cost → **replay workload and

find the point of diminishing returns.**

• Ignoring the hash-algorithm version → encoding or implementation differences remap every key → **put the algorithm,

encoding, epoch, and checksum in the snapshot.**

• Using consistent hashing for every sharding problem → range queries or precise operations may favor another approach →

compare fixed partitions, rendezvous, and jump hash.

Follow-Up Questions and Responses

Follow-up 1: Why does adding a ring node not move exactly 1/(N+1) of keys?

That fraction assumes uniformly distributed keys and nodes, equal capacity, and enough tokens. A finite random token set creates unequal intervals, while value sizes and QPS can also skew. It is an expectation. Replay real keys, bytes, and traffic before launch and reserve migration bandwidth above the expected value. If every operation needs a precisely bounded movement unit, fixed logical partitions are a better fit.

Follow-up 2: Why is a membership control plane still necessary when replicas span three zones?

Replica placement is meaningful only when participants agree on an epoch. Two clients with different rings can send new writes to different replica sets, and each may believe it achieved three copies. The control plane linearizes membership changes and publishes versions. During version skew, forwarding, dual reads, or rejection of stale writes drives convergence. Failure-domain diversity does not replace membership ordering.

Follow-up 3: One tenant produces 40% of QPS through a single key. Do more vnodes help?

No. Virtual nodes change how ranges are distributed; they do not assign one hash value to multiple primaries. A read-heavy key can use multiple read replicas and request coalescing. A write-heavy key needs a business-aware split, sharded mergeable state, or tenant rate limits. If writes must serialize, the single-key consistency requirement is the throughput limit and should be stated explicitly.

Follow-up 4: Writes continue during scale-out copying. How do you avoid losing the incremental changes?

The copy records a log position or version watermark. It first copies the range up to that watermark, then consumes later changes; a short dual-write window is another option. The new epoch is published only after the new node reaches the cutover watermark, verification passes, and replicas are healthy. Old owners keep a grace period for late requests and confirm no under-replicated ranges before deletion.

Follow-up 5: Can reads and writes continue when the control plane is down?

The data plane keeps using the last immutable snapshot with a valid checksum, so individual lookups continue. Safe writes after a node failure depend on the remaining replicas and write-consistency rule; clients cannot permanently change the ring on their own. Expose snapshot age and degrade or stop writes when the safety window or required replica count is exceeded. Continued reads do not prove that writes are safe.

Follow-up 6: When would you select jump consistent hash?

Choose it for sequentially numbered logical buckets that mainly grow at the end when fast mapping with constant memory matters. Arbitrary removal and identity-bearing physical nodes are awkward, so a system often maps keys to logical buckets first and lets the control plane place buckets on machines. That indirection also lets storage move buckets without changing the key-to-bucket algorithm.

Follow-up 7: How can the hash function be upgraded without causing incorrect routing for the whole dataset?

The function name, seed, and key encoding are part of the snapshot protocol. Create a new epoch, calculate the old-to-new ownership difference offline, then copy and catch up data through the normal migration process. During cutover, requests carry the algorithm version and servers can forward to new owners. Letting only some clients adopt the function creates nearly complete split ownership, so the upgrade must be handled as a controlled full repartition.