Consistent Hashing Interview Questions for Senior Engineers (2026)

Why Consistent Hashing Dominates Senior Engineering Interviews

Consistent hashing is one of the most frequently tested distributed systems concepts in senior and staff engineering interviews. It appears in nearly every system design question that involves data partitioning, caching, or load distribution. Interviewers expect senior candidates to move beyond textbook definitions and demonstrate a nuanced understanding of how consistent hashing behaves under real-world conditions: node failures, hot keys, heterogeneous hardware, and dynamic cluster membership.

The reason consistent hashing receives so much attention is that it solves one of the most fundamental problems in distributed computing: how to distribute data across a cluster of machines so that adding or removing a node does not require rehashing everything. Traditional modulo-based hashing (key mod N) remaps nearly all keys when N changes. Consistent hashing limits disruption to approximately K/N keys, where K is the total number of keys and N is the number of nodes. This property is essential for systems that must remain available during scaling events and failures.

At companies like Amazon, Google, and Netflix, consistent hashing underpins critical infrastructure: DynamoDB's partitioning scheme, Cassandra's token ring, Memcached client-side sharding, and content delivery network routing. Understanding the theory is necessary but not sufficient. Interviewers want to see that you can apply consistent hashing to novel problems, reason about its failure modes, and choose appropriate variations for specific workloads.

For foundational knowledge, review our deep dive on how consistent hashing works and the conceptual overview of consistent hashing. For broader preparation, see the system design interview guide and distributed systems guide. Explore structured learning paths for a step-by-step study plan.

1. Explain consistent hashing and why it is preferred over modulo-based hashing for distributed systems.

What the interviewer is really asking: Can you articulate the core problem that consistent hashing solves and demonstrate understanding of both approaches with concrete numbers?

Answer framework:

Begin by framing the problem. In any distributed system that partitions data across multiple nodes, you need a function that maps each key to a node. The simplest approach is modulo hashing: compute hash(key) mod N, where N is the number of nodes. This works when the cluster is static, but the moment you add or remove a node, N changes and almost every key maps to a different node. If you have 1 million keys across 10 nodes and add an 11th node, roughly 90 percent of keys need to be remapped. For a distributed cache like Redis or Memcached, this means a near-total cache miss storm that can overwhelm the backend database.

Consistent hashing eliminates this problem by mapping both keys and nodes onto a circular hash space (typically 0 to 2^32 - 1). Each node is assigned a position on the ring by hashing its identifier. Each key is assigned to the first node encountered when walking clockwise from the key's hash position. When a node is added, only the keys in the arc between the new node and its predecessor are reassigned. When a node is removed, only its keys move to the next node clockwise. The expected number of keys that move is K/N, which for 1 million keys across 10 nodes is only about 100,000 keys rather than 900,000.

Explain the practical implications: during a rolling deployment or a node failure, the majority of requests continue to hit the correct node. This keeps cache hit rates high, avoids thundering herd problems on the database, and allows the system to scale incrementally without downtime. Mention that Amazon's Dynamo paper (2007) popularized consistent hashing for production key-value stores, and it is now a standard pattern in distributed databases, caches, and load balancers.

Conclude by noting the limitation of basic consistent hashing: with a small number of nodes, the key distribution can be uneven because random hash positions do not guarantee equal arc lengths. This motivates virtual nodes, which you should mention briefly but save detail for when the interviewer asks.

Follow-up questions:

• What is the worst-case key distribution with basic consistent hashing and how uneven can it get?
• How does consistent hashing interact with the CAP theorem when nodes fail?
• Can you name three production systems that use consistent hashing and describe which variation each uses?

2. What are virtual nodes and why are they essential in practice?

What the interviewer is really asking: Do you understand why naive consistent hashing fails in production and how virtual nodes fix the distribution problem?

Answer framework:

Start with the problem. In basic consistent hashing with N physical nodes, each node owns one arc of the ring. The expected arc length is 1/N of the ring, but the variance is high. With 5 nodes, standard deviation of load per node is approximately 60 percent of the mean. One node might handle 40 percent of keys while another handles 5 percent. This imbalance worsens cache efficiency, creates hotspots, and complicates capacity planning.

Virtual nodes solve this by mapping each physical node to multiple positions on the ring. Instead of hashing the node identifier once, you hash it with suffixes (for example, node-A-1, node-A-2, through node-A-150) to create 150 virtual nodes per physical node. Each virtual node owns an arc, and the total load on a physical node is the sum of its virtual node arcs. By the law of large numbers, with 150 virtual nodes per physical node, the load variance drops dramatically. The standard deviation shrinks to approximately 5-10 percent of the mean, giving near-uniform distribution.

Discuss the additional benefits. First, heterogeneous hardware support: a more powerful machine can be assigned more virtual nodes (for example, 300 instead of 150), receiving proportionally more traffic. This is critical in real clusters where machines have different CPU, memory, and disk capacities. Second, smoother rebalancing: when a node is removed, its virtual nodes are scattered across the ring, so the load is distributed among many surviving nodes rather than dumped entirely on one successor. Third, during planned maintenance, you can gradually remove virtual nodes to drain traffic before taking a machine offline.

Discuss the trade-offs. Virtual nodes increase the size of the routing table: with 100 physical nodes and 150 virtual nodes each, the ring has 15,000 entries. This must be stored in memory on every client or routing layer, consuming a few megabytes. For most systems this is negligible, but for embedded clients or very large clusters (thousands of nodes), the memory overhead becomes a consideration. Also, the virtual-to-physical node mapping adds a layer of indirection that slightly increases lookup complexity from O(log N) to O(log V) where V is the total number of virtual nodes, though in practice this is still sub-microsecond.

Mention that Cassandra uses 256 virtual nodes per physical node by default (configurable via num_tokens), and Amazon DynamoDB uses a similar approach for partition distribution.

Follow-up questions:

• How do you choose the optimal number of virtual nodes per physical node?
• What happens to virtual node assignment when you need to replace a failed node with a machine that has different capacity?
• How do virtual nodes affect the replication strategy in a system like Cassandra?

3. How does consistent hashing work in a distributed cache like Memcached or Redis Cluster?

What the interviewer is really asking: Can you connect the abstract concept to a concrete caching architecture and discuss the client-side vs server-side implementation?

Answer framework:

Distinguish between two models. In Memcached, consistent hashing is implemented client-side. Each cache client maintains a local copy of the hash ring containing all Memcached server addresses. When the application performs a cache operation, the client library hashes the key, finds the responsible server on the ring, and sends the request directly to that server. The Memcached servers themselves have no knowledge of each other. This is a shared-nothing architecture. Libraries like libketama (originally from Last.fm) implemented this pattern and became the de facto standard. The advantage is simplicity: no coordination between servers, no cluster management. The disadvantage is that every client must have an identical, up-to-date view of the server list, and there is no automatic failover.

In Redis Cluster, the approach is different. Redis uses hash slots: the key space is divided into 16,384 fixed slots using CRC16(key) mod 16384. Each node owns a contiguous range of slots. This is not exactly consistent hashing but achieves similar goals. When a node is added, a portion of slots is migrated from existing nodes to the new node. The cluster itself manages slot assignment through a gossip protocol, and clients are redirected (MOVED response) if they contact the wrong node. The advantage is automatic rebalancing and built-in replication. The disadvantage is operational complexity.

Discuss the cache stampede problem in the context of consistent hashing. When a cache node fails, all of its keys are remapped to the next node on the ring. That node suddenly receives both its own traffic and the failed node's traffic. If the failed node held popular keys, the successor is hit with a flood of cache misses that all go to the backend database. Mitigation strategies include replication (each key is stored on multiple consecutive nodes on the ring), bounded load consistent hashing (Google's approach, which caps the maximum load on any single node by probing the next node when the first is overloaded), and background cache warming.

Discuss monitoring considerations: track per-node cache hit rates, memory utilization, and request latency. Uneven metrics across nodes indicate a consistent hashing configuration problem, such as too few virtual nodes or a hot key issue.

Follow-up questions:

• How would you handle a hot key that overwhelms a single cache node despite consistent hashing?
• What happens during a network partition between cache clients and some cache servers?
• How would you implement consistent hashing for a cache cluster that spans multiple data centers?

4. Walk through what happens when a node is added to or removed from a consistent hash ring.

What the interviewer is really asking: Can you trace the exact sequence of operations during cluster membership changes and identify potential data loss or inconsistency windows?

Answer framework:

Trace the node addition scenario step by step. Suppose you have nodes A, B, C on the ring and add node D. Node D's virtual nodes are computed and placed on the ring. For each virtual node of D, the keys in the arc between D's predecessor and D must be migrated from D's successor to D. During migration, there is a transition window. The system must handle requests for keys that are being migrated.

Discuss migration strategies. In a cache system, you may choose not to migrate data at all. Instead, let the new node start with an empty cache and serve cache misses, which will naturally populate it. The cost is a temporary increase in backend load proportional to the fraction of keys remapped (approximately K/N). For a data store where durability matters, active migration is required. The source node streams data to the new node. During streaming, the source continues to serve reads and writes for the migrating keys. Once streaming completes, ownership is atomically transferred.

Discuss the double-write problem: during migration, a write to a migrating key must be applied to both the old owner and the new owner to prevent data loss. Alternatively, use a split-phase approach: route all reads and writes to the old owner until migration completes, then switch. This is simpler but does not spread the load benefit of the new node until migration finishes.

For node removal (planned or unplanned), the keys owned by the removed node become the responsibility of its successor on the ring. If the removal is planned (graceful shutdown), the node can proactively stream its data to the successor before departing. If the removal is a crash, the successor has no data for those keys. This is why replication is essential: if each key is stored on R consecutive nodes, a single node failure causes no data loss because the next replica has a copy.

Discuss how systems like DynamoDB use a preference list: each key is stored on the first N distinct physical nodes encountered clockwise on the ring (skipping virtual nodes of the same physical node). This ensures that a single physical node failure does not affect availability for any key, because at least N-1 replicas remain on distinct machines.

Follow-up questions:

• How do you minimize the performance impact on the cluster during data migration?
• What consistency guarantees can you provide during the migration window?
• How does the system detect that a node has failed versus being temporarily unreachable?

5. How would you handle hot keys (skewed access patterns) in a consistent hashing scheme?

What the interviewer is really asking: Do you understand that consistent hashing distributes keys uniformly but not access uniformly, and can you propose solutions for real-world skew?

Answer framework:

First, clarify the distinction between key distribution and access distribution. Consistent hashing with virtual nodes achieves near-uniform key distribution, meaning each node stores approximately the same number of keys. However, access patterns are rarely uniform. A viral tweet, a flash sale product, or a popular user profile can generate orders of magnitude more requests than average keys. The node responsible for that hot key becomes a bottleneck while other nodes sit idle.

Discuss multiple solutions at different layers. First, application-level caching: for read-heavy hot keys, cache the value in application memory (local cache) or a dedicated hot-key cache in front of the consistent hash ring. This absorbs the majority of reads without hitting the assigned node. The challenge is cache invalidation when the hot key's value changes.

Second, key splitting (sharding the hot key): append a random suffix to the key (for example, popular_item_data_0 through popular_item_data_9) to spread it across 10 different nodes on the ring. Writes go to all 10 shards. Reads randomly pick one shard. This distributes load but adds complexity for writes and consistency. Twitter uses this approach for celebrity timelines.

Third, bounded-load consistent hashing (from Google's 2017 paper by Mirrokni, Thorup, and Zadimoghaddam): modify the ring lookup so that each node has a maximum load capacity (for example, 1.25 times the average load). When a key maps to an overloaded node, the lookup algorithm probes the next node on the ring, and so on until finding a node with available capacity. This provides provable load balance guarantees with at most epsilon extra load on each node. The trade-off is that key-to-node mapping becomes dynamic and depends on current load.

Fourth, reactive splitting: monitor per-key access rates in real time. When a key crosses a threshold, automatically trigger the key-splitting strategy. When access drops, collapse the shards back. This requires a monitoring layer and an orchestration system but handles unpredictable hotspots gracefully.

Discuss how load balancing at the request routing layer complements consistent hashing. Even with consistent hashing for data placement, a separate load-aware routing layer can redirect overflow traffic to replicas.

Follow-up questions:

• How does bounded-load consistent hashing maintain data locality when keys are redirected to different nodes?
• What monitoring metrics would you track to detect hot keys before they cause outages?
• How would you handle a hot key in a write-heavy workload where caching does not help?

6. Compare consistent hashing with rendezvous hashing (highest random weight). When would you choose one over the other?

What the interviewer is really asking: Do you know alternatives to ring-based consistent hashing and understand the trade-offs in terms of performance, distribution quality, and implementation complexity?

Answer framework:

Explain rendezvous hashing (also called HRW hashing). For each key, compute a score for every node using a hash function: score = hash(key, node_id). Assign the key to the node with the highest score. When a node is removed, only the keys that were assigned to it are remapped, because all other keys still have the same highest-scoring node. When a node is added, it steals keys for which it scores highest, approximately K/N keys. This provides the same minimal disruption property as consistent hashing.

Compare the two approaches across several dimensions. Lookup complexity: consistent hashing with a sorted ring uses binary search for O(log V) lookups, where V is the number of virtual nodes. Rendezvous hashing requires computing a hash for each of the N nodes, so lookups are O(N). For small clusters (under 100 nodes), this difference is negligible. For large clusters (thousands of nodes), rendezvous hashing becomes expensive per lookup.

Distribution quality: rendezvous hashing provides perfectly uniform distribution by construction, since each key independently and uniformly selects the highest-scoring node. Consistent hashing requires virtual nodes to approximate uniform distribution, and the quality depends on the number of virtual nodes. Rendezvous hashing achieves uniformity without any tuning parameter.

Memory overhead: consistent hashing with virtual nodes requires storing the ring (V entries). Rendezvous hashing requires only the list of N node identifiers. For clusters with hundreds of virtual nodes per physical node, consistent hashing uses significantly more memory for the routing table.

Weighted distribution: both support heterogeneous nodes. In consistent hashing, assign more virtual nodes to bigger machines. In rendezvous hashing, apply a weight multiplier to the hash score.

When to choose rendezvous hashing: small to medium clusters where O(N) lookup is acceptable, when you need perfect distribution without tuning virtual node counts, and when memory for the routing table is constrained. When to choose consistent hashing: large clusters (hundreds or thousands of nodes) where O(log V) lookup is necessary, when you need to minimize the per-request computation overhead, and in established ecosystems with library support.

Mention that Microsoft uses rendezvous hashing in their Caching Service, and many CDN providers use it for request routing.

Follow-up questions:

• Can you implement rendezvous hashing to support node priorities or weights?
• How does rendezvous hashing handle the addition of multiple nodes simultaneously?
• What are the implications for replication when using rendezvous hashing versus ring-based hashing?

7. How does consistent hashing apply to database sharding? Walk through a design for sharding a user database.

What the interviewer is really asking: Can you apply consistent hashing to a stateful system where data migration is expensive and correctness is critical?

Answer framework:

Start with the requirements: a user database with hundreds of millions of records, growing at 10 percent annually, with a need to add shards without downtime. The shard key is user_id.

Design the sharding layer. Hash each user_id onto a consistent hash ring with virtual nodes. The ring maps each hash position to a shard (a database instance or replica set). Maintain a routing table derived from the ring in a coordination service like ZooKeeper or etcd. Every application server caches this routing table and routes queries to the appropriate shard.

Discuss shard splitting. When a shard grows too large (by data size or query load), you need to split it. With consistent hashing, you add a new shard to the ring, which claims a portion of the overloaded shard's key range. The data migration process: (1) create the new shard as a replica of the source shard, (2) start replicating writes to both shards, (3) run a background migration job that copies the relevant key range to the new shard, (4) once caught up, update the routing table to point the migrated key range to the new shard, (5) delete the migrated data from the source shard.

Discuss the critical consistency requirement during migration. Reads for migrating keys must continue to hit the source shard until migration is complete. You can implement this with a two-phase routing table: the routing layer first checks if a key is in the "migrating" state and routes to the source shard for reads and to both shards for writes.

Address cross-shard queries. Consistent hashing distributes users across shards, so queries that span multiple users (for example, "find all users in a city") require scatter-gather across all shards. This is a fundamental limitation of hash-based sharding. Mitigate with secondary indexes stored in a search engine like Elasticsearch, or use a different sharding strategy (range-based on geographic region) for queries with known access patterns.

Discuss how DynamoDB handles this: it uses consistent hashing for partition assignment and automatically splits partitions when they exceed size or throughput limits. The application is unaware of the underlying partitioning. This abstraction simplifies operations but limits query flexibility.

Reference the CAP theorem implications: during shard migration, the system must choose between availability (serve potentially stale data) and consistency (block queries for migrating keys).

Follow-up questions:

• How do you handle a resharding operation that must migrate terabytes of data without downtime?
• What happens to in-flight transactions when a shard split occurs?
• How would you handle a schema change that must be applied to all shards consistently?

8. Explain how Amazon DynamoDB uses consistent hashing internally.

What the interviewer is really asking: Can you connect the textbook concept to a real production system, showing depth of knowledge beyond academic theory?

Answer framework:

DynamoDB's design is rooted in the Amazon Dynamo paper (2007), one of the most influential papers in distributed systems. The original Dynamo used consistent hashing with virtual nodes to partition data across a cluster of commodity servers.

In the original design, each physical node was assigned multiple virtual nodes (tokens) on the ring. The partition key of each item was hashed using MD5 to produce a 128-bit hash. The item was stored on the first N distinct physical nodes clockwise from its hash position (the preference list), providing replication factor N (typically 3).

Discuss how DynamoDB evolved beyond the original paper. Modern DynamoDB uses a refined partitioning scheme. The key space is divided into partitions, each responsible for a contiguous range of the hash space. Each partition is a storage unit hosted on SSDs, replicated 3 times across different availability zones. The partition assignment is managed by a metadata service rather than a peer-to-peer gossip protocol, which simplifies operations and improves consistency.

DynamoDB automatically splits partitions when they exceed 10GB of data or when the read/write throughput exceeds the partition's capacity. When a split occurs, the hash range is divided, a new partition is created, and data is migrated. This is transparent to the application. The routing layer (request routers) maintain an in-memory cache of the partition map and route requests to the correct partition.

Discuss the adaptive capacity feature. In earlier versions, hot partitions could throttle even if the table's overall capacity was underutilized. Adaptive capacity solved this by allowing individual partitions to borrow unused capacity from the table, effectively load-balancing at the partition level. This is conceptually similar to bounded-load consistent hashing.

Address global tables: DynamoDB replicates data across multiple AWS regions using last-writer-wins conflict resolution. Each region has its own consistent hash ring, and cross-region replication is asynchronous.

This design illustrates the evolution from academic consistent hashing to a production system that adds layers of optimization, monitoring, and automatic management.

Follow-up questions:

• What are the limitations of DynamoDB's partition key design and how do they relate to consistent hashing?
• How does DynamoDB handle the hot partition problem differently from a naive consistent hashing implementation?
• Why did DynamoDB move from a peer-to-peer architecture to a centralized metadata service?

9. How would you implement consistent hashing for a load balancer that distributes requests across backend servers?

What the interviewer is really asking: Can you apply consistent hashing in the networking/infrastructure layer, handling session affinity, health checks, and graceful degradation?

Answer framework:

Explain the use case. In a load balancer, consistent hashing ensures that requests from the same client (or with the same session key) are routed to the same backend server. This provides session affinity without sticky sessions stored in the load balancer. The hash key can be the client IP, a session cookie, a user ID, or a combination.

Design the implementation. Build a hash ring with virtual nodes for each healthy backend server. On each incoming request, extract the hash key, compute its position on the ring, and find the first server clockwise. This is the primary backend for that request. Maintain the ring in the load balancer's memory and update it when backend servers are added, removed, or fail health checks.

Discuss health checking integration. When a backend fails a health check, remove its virtual nodes from the ring. Requests that were routed to the failed backend automatically shift to the next server on the ring. When the backend recovers, re-add its virtual nodes. This causes a small fraction of requests to shift (only those that were originally assigned to the recovered server), minimizing disruption.

Address the connection draining problem. When a backend is being removed (for deployment or maintenance), you want to stop sending new requests to it while allowing existing connections to complete. Implement this by removing the node from the ring for new lookups but keeping existing connections alive until they close naturally or a timeout expires.

Discuss the trade-off between consistent hashing and other load balancing algorithms. Round-robin provides perfect load distribution but no affinity. Least-connections adapts to slow backends but also has no affinity. Consistent hashing provides affinity but can create imbalance if some hash keys generate more load than others. In practice, many load balancers (Envoy, HAProxy, Nginx) offer consistent hashing as one option alongside others. Envoy's implementation uses the Maglev algorithm (from Google), which provides both consistent hashing properties and excellent distribution.

Discuss Maglev hashing briefly: it builds a lookup table rather than a ring, providing O(1) lookups and near-perfect distribution. The table is constructed so that adding or removing a backend disrupts only a minimal fraction of mappings.

Follow-up questions:

• How would you handle a backend server that is healthy but slow and accumulating requests?
• What happens when multiple load balancer instances need to agree on the same consistent hashing ring?
• How would you implement weighted consistent hashing to send more traffic to more powerful backends?

10. What is jump consistent hashing and how does it differ from ring-based consistent hashing?

What the interviewer is really asking: Do you know about modern alternatives to ring-based hashing and can you evaluate when they are appropriate?

Answer framework:

Jump consistent hashing, published by Google's Lamping and Veach in 2014, is a remarkably simple algorithm. The entire implementation is about 5 lines of code. Given a key and the number of buckets N, it returns a bucket number in the range 0, N). It provides perfectly uniform distribution and minimal disruption: when the number of buckets changes from N to N+1, only 1/(N+1) fraction of keys move, which is the theoretical minimum. [blocked]

The algorithm works by simulating a series of coin flips. For each key, it starts at bucket 0 and progressively jumps forward. At each step, the jump distance increases so that the probability of landing in each bucket is exactly 1/N. The beauty is that the algorithm needs no stored ring or routing table; it is purely computational.

Compare with ring-based consistent hashing. Distribution quality: jump consistent hashing is perfectly uniform by construction. Ring-based hashing with virtual nodes approximates uniformity but is never perfect. Memory: jump consistent hashing uses O(1) memory (no ring, no table). Ring-based uses O(V) memory where V is the total virtual nodes. Speed: jump consistent hashing runs in O(ln N) time with very small constants. Ring-based uses O(log V) binary search with hash computation.

However, jump consistent hashing has critical limitations. Buckets must be numbered 0 through N-1 sequentially. You can only add or remove the last bucket. You cannot remove an arbitrary node from the middle. If server 3 out of 10 fails, you cannot simply remove it; you would need to map its data to server 9 and decrement to 9 buckets, which disrupts many more keys. In contrast, ring-based hashing handles arbitrary node additions and removals gracefully.

This means jump consistent hashing is ideal for systems where nodes are numbered sequentially and failures are handled by replacement rather than removal: for example, sharded databases where a failed shard is replaced by a new machine that takes the same shard number. It is not suitable for dynamic clusters where arbitrary nodes join and leave.

Mention that Google uses jump consistent hashing internally for data partitioning in systems with stable cluster membership.

Follow-up questions:

• How would you adapt jump consistent hashing to handle weighted nodes?
• Can jump consistent hashing be combined with replication, and if so how?
• In what scenarios would you choose jump consistent hashing over ring-based despite its limitations?

11. How do you handle replication in a consistent hashing scheme? Explain the interaction between hashing and replica placement.

What the interviewer is really asking: Can you reason about the interplay between data distribution and fault tolerance, particularly the subtlety of avoiding co-located replicas?

Answer framework:

The standard approach is successor-based replication. For a replication factor of 3, each key is stored on 3 consecutive distinct physical nodes clockwise from the key's position on the ring. The first node is the primary; the second and third are replicas. This ensures that reads can be served from any of the three nodes, and the system tolerates up to 2 node failures for any given key.

Explain the virtual node complication. With virtual nodes, walking clockwise from a key's position might hit multiple virtual nodes belonging to the same physical node. If you store replicas on the first 3 virtual nodes, two replicas might reside on the same physical machine, which defeats the purpose. The solution is to walk clockwise and skip virtual nodes that belong to a physical node already in the replica set. This is the preference list approach from Amazon's Dynamo paper.

Extend this to rack-awareness and availability zone awareness. In a production deployment at Amazon or Google, you want replicas on different racks (to survive rack switch failure) and in different availability zones (to survive zone failures). Modify the replica selection algorithm: walk clockwise and select nodes that satisfy diversity constraints (different physical machine, different rack, different AZ). This requires encoding topology information into the node metadata.

Discuss the trade-off between diversity and latency. Placing replicas in different AZs provides maximum fault tolerance but increases write latency (cross-AZ replication) and read latency (if the nearest replica is in a different AZ). Some systems use synchronous replication within the same AZ and asynchronous replication across AZs, accepting a small window of potential data loss for cross-AZ failures.

Discuss quorum reads and writes. With R replicas, configure a write quorum W and read quorum R such that W + R > N (the replication factor). For example, with N=3, W=2, R=2: writes are acknowledged after 2 replicas confirm, reads query 2 replicas and return the latest version. This guarantees strong consistency while tolerating 1 node failure for both reads and writes. This is directly tied to the CAP theorem trade-offs.

Follow-up questions:

• How do you handle the case where there are not enough nodes in distinct failure domains to satisfy the replication policy?
• What happens to consistency during a network partition when replicas are in different availability zones?
• How would you implement read repair in a consistent hashing system with replicated data?

12. Design a consistent hashing scheme for a multi-region distributed database.

What the interviewer is really asking: Can you extend consistent hashing to a global scale, handling cross-region replication, latency, and data sovereignty?

Answer framework:

Describe a hierarchical approach. At the top level, route data to a region based on data sovereignty requirements or user preference (for example, EU data stays in EU regions for GDPR compliance). Within each region, use consistent hashing to distribute data across nodes.

For global data that must be available in all regions (for example, user profiles), use a per-region consistent hash ring with cross-region replication. Each region has its own ring with its own nodes. A key is assigned to a node within each region independently. Writes in one region are asynchronously replicated to all other regions. This is the approach used by CockroachDB and Cassandra with NetworkTopologyStrategy.

Discuss conflict resolution for multi-region writes. With asynchronous replication, two regions can independently update the same key. Strategies include last-writer-wins using synchronized timestamps (NTP provides millisecond accuracy; vector clocks provide causal ordering), application-specific merge functions (for CRDTs), and single-leader per key (route all writes for a key to one region, replicate to others). The Raft consensus protocol can be extended across regions for strong consistency, but at the cost of latency proportional to the inter-region round-trip time.

Discuss the latency implications. A strongly consistent multi-region system using Raft requires a majority quorum across regions. If replicas are in US-East, US-West, and EU-West, every write must wait for 2 of 3 regions to acknowledge, adding 60-100ms to writes. Google Spanner solves this with TrueTime (GPS and atomic clock-synchronized timestamps) to provide strong consistency with lower commit latency, but this requires specialized hardware.

Address the client routing problem. Global clients need to discover the nearest region and the correct node within that region. Use GeoDNS or Anycast for region selection, then a region-local routing service that maintains the consistent hash ring for that region.

Discuss failover. If an entire region goes down, redirect traffic to the nearest surviving region. The surviving region must have up-to-date replicas. With asynchronous replication, some recent writes may be lost. With synchronous replication, no data is lost but normal-case latency is higher. This is a fundamental trade-off in distributed systems.

Follow-up questions:

• How do you handle a scenario where data sovereignty rules conflict with the nearest-region routing?
• What happens to in-flight cross-region replications when a region fails?
• How would you implement consistent hashing for a database that must support both global and region-local tables?

13. How would you test a consistent hashing implementation to verify correctness and performance?

What the interviewer is really asking: Can you think about correctness properties, edge cases, and performance characteristics of distributed algorithms, not just implement them?

Answer framework:

Define the correctness properties to test. First, monotonicity: when a node is added, no key should move from one existing node to another existing node. Keys can only move from an existing node to the new node. Second, balance: with virtual nodes, the key distribution across nodes should be approximately uniform. Third, minimal disruption: when adding or removing a node, the number of keys that change assignment should be approximately K/N. Fourth, consistency: the same key should always map to the same node given the same ring configuration.

Design the test suite. For unit tests: hash a large number of random keys (1 million), verify distribution uniformity using chi-squared tests (no node should have more than 1.5 times the average number of keys with 150+ virtual nodes). For monotonicity: hash 1 million keys with N nodes, add a node, re-hash, and verify that every key that moved went to the new node. For minimal disruption: measure the fraction of keys that moved and assert it is within 10 percent of the theoretical K/(N+1).

For edge cases: test with 1 node (all keys should map to it), test with 2 nodes (should be approximately 50/50), test adding a node with the same hash as an existing node (collision handling), test with keys that produce hash collisions, and test with empty string keys and very long keys.

For performance tests: benchmark lookup latency with varying ring sizes (100 to 100,000 virtual nodes). Measure memory consumption of the ring data structure. Benchmark the time to rebuild the ring when adding or removing a node. For a production system, latency should be under 1 microsecond for lookups and under 10 milliseconds for ring rebuilds.

For chaos testing: simulate node failures during a traffic simulation. Verify that keys are correctly reassigned. Simulate rapid node additions and removals and verify the ring converges to a correct state. Use property-based testing (like Jepsen for distributed systems) to discover edge cases through random exploration.

Follow-up questions:

• How would you benchmark the distribution quality of different hash functions for consistent hashing?
• What metrics would you monitor in production to detect consistent hashing problems?
• How would you test the interaction between consistent hashing and the replication layer?

14. Explain the relationship between consistent hashing and the CAP theorem in the context of a distributed key-value store.

What the interviewer is really asking: Can you connect consistent hashing (a data placement mechanism) to the fundamental consistency and availability trade-offs in distributed systems?

Answer framework:

First, clarify that consistent hashing and the CAP theorem operate at different levels. Consistent hashing is a data placement strategy: it determines which nodes store which keys. The CAP theorem governs the behavior of the system during network partitions: you must choose between consistency (all reads return the most recent write) and availability (all requests receive a response).

However, the two interact in important ways. Consistent hashing with replication means each key is stored on multiple nodes. When a network partition separates some replicas from others, the CAP trade-off manifests. Suppose key X is replicated on nodes A, B, and C. A network partition isolates node C from A and B.

CP choice: the system requires a quorum (2 of 3 nodes) for reads and writes. A and B can form a quorum, so reads and writes for key X succeed on the A/B side. Node C rejects reads and writes because it cannot reach a quorum. Consistency is maintained, but clients connected to C experience unavailability. This is the approach of systems like ZooKeeper and etcd.

AP choice: all three nodes continue to accept reads and writes independently. Node C serves stale data for reads and accepts writes that may conflict with writes on A/B. Availability is maintained, but consistency is sacrificed. After the partition heals, conflicts must be resolved (last-writer-wins, vector clocks, application merge). This is the approach of DynamoDB and Cassandra.

Discuss how consistent hashing affects the partition scenario. Because consistent hashing distributes keys across nodes, a partition that isolates one node affects only the keys assigned to that node (or its replicas). Other keys on non-partitioned nodes are unaffected. This is a significant advantage over centralized architectures where a partition can affect all data.

Discuss tunable consistency. Systems like Cassandra allow per-query consistency levels. A read with consistency ONE hits one replica (fast, available, possibly stale). A read with consistency QUORUM hits a majority of replicas (slower, consistent). This flexibility is enabled by the consistent hashing replication scheme where the client knows all replica locations and can query as many as needed.

Follow-up questions:

• How does consistent hashing affect the probability of a given key being affected by a network partition?
• Can you design a system that provides strong consistency for some keys and eventual consistency for others using the same consistent hashing ring?
• How does the Raft consensus protocol interact with consistent hashing for partition management?

15. You need to migrate a production system from modulo-based hashing to consistent hashing with zero downtime. How would you approach this?

What the interviewer is really asking: Can you design a safe migration plan for a critical distributed system, handling the dual-write problem, gradual rollout, and rollback?

Answer framework:

This is a real-world scenario many engineers face. The migration is essentially changing the key-to-node mapping for every key in the system while the system is serving live traffic. A naive approach (switch all at once) would cause massive cache misses or data unavailability.

Design a phased migration plan. Phase 1 - dual-write setup: deploy a new routing layer that maintains both the old modulo hash function and the new consistent hash ring. For writes, compute both the old and new node assignments. If they differ, write to both nodes. For reads, continue reading from the old node. This phase has zero user impact. Duration: deploy and monitor for 1-2 days.

Phase 2 - background data migration: run a background job that iterates over all keys in the old system. For each key, compute the new assignment. If the key should move to a different node, copy it to the new node. Use a progress tracker to resume from where you left off if the job fails. Throttle the migration to avoid overloading the cluster. Duration: depends on data volume, typically days to weeks for large datasets.

Phase 3 - read migration with fallback: switch reads to use the new consistent hash ring. If a read misses on the new node (because migration has not reached that key yet), fall back to the old node. This is a shadow migration pattern. Monitor the fallback rate; it should decrease as migration progresses. Duration: until fallback rate reaches near zero.

Phase 4 - cutover: once all data is migrated and the fallback rate is zero, stop dual-writes and route all traffic through the new consistent hash ring. Keep the old system running in read-only mode for a rollback window (1-2 weeks). Duration: 1-2 weeks of monitoring.

Phase 5 - cleanup: decommission the old routing logic and the old hashing function. Remove the fallback code path. Archive the old data.

Discuss rollback at each phase. In Phase 1-2, rollback is trivial: stop dual-writes and background migration. In Phase 3, rollback means switching reads back to the old hash function. In Phase 4, rollback means re-enabling dual-writes and the old hash function. The old data is still available during the rollback window.

Discuss risk mitigation: canary the migration on a small subset of keys first (for example, keys matching a specific hash prefix). Monitor error rates, latency, and cache hit rates throughout. Set up automated alerts that trigger a pause if metrics degrade.

Reference the broader pattern: this is similar to database migration strategies used at Google and Amazon, where zero-downtime schema changes require careful multi-phase rollouts.

Follow-up questions:

• How would you handle the migration if the old system uses 10 nodes and the new consistent hash ring starts with 15 nodes?
• What happens to in-flight requests during the cutover from Phase 3 to Phase 4?
• How would you estimate the total migration time and resource cost before starting?

Common Mistakes in Consistent Hashing Interviews

1. Describing only the basic ring without discussing virtual nodes. Production systems never use naive consistent hashing with one position per node. If you stop at the basic algorithm, the interviewer will think your knowledge is purely theoretical. Always proactively mention virtual nodes and their impact on distribution quality.

2. Ignoring hot key problems. Consistent hashing distributes keys uniformly, not access uniformly. Many candidates claim consistent hashing solves load balancing, but a single viral key can overwhelm one node. Always address what happens when access patterns are skewed.

3. Forgetting about replication and the preference list. In any real distributed system, data must be replicated for durability. Simply saying the key goes to the next node on the ring is incomplete. Discuss how replicas are placed on distinct physical nodes across failure domains.

4. Not quantifying the disruption. Saying consistent hashing causes minimal disruption is vague. Be specific: when adding a node to a cluster of N nodes, approximately 1/N of keys move. With 10 nodes, adding an 11th moves about 9 percent of keys. These numbers demonstrate real understanding.

5. Treating consistent hashing as a silver bullet. Every approach has trade-offs. Consistent hashing adds complexity (ring management, virtual node configuration), introduces potential for uneven distribution (without enough virtual nodes), and complicates cross-shard queries. Acknowledge these limitations.

How to Prepare for Consistent Hashing Interview Questions

Start by understanding the theory deeply. Read the original Karger et al. paper (1997) and the Amazon Dynamo paper (2007). Implement a consistent hash ring from scratch in your preferred language, including virtual nodes, node addition and removal, and key lookup. Benchmark your implementation for distribution quality and lookup latency.

Study how consistent hashing is used in production systems you are likely to discuss in interviews. Understand Cassandra's token ring, DynamoDB's partitioning, Redis Cluster's hash slots, and Memcached's client-side consistent hashing. For each, know the specific variation used and why.

Practice connecting consistent hashing to broader system design questions. When designing a URL shortener or a distributed cache, consistent hashing should be one of your tools. Practice explaining how it fits into the overall architecture.

For a comprehensive preparation plan, follow our system design interview guide and explore the distributed systems guide. Use the structured learning paths to build systematic knowledge. Review pricing plans for full access to practice problems and detailed solutions.

Related Resources

• How Consistent Hashing Works
• Consistent Hashing Concepts
• How Load Balancing Works
• CAP Theorem Deep Dive
• Distributed Cache with Redis
• URL Shortener System Design
• Redis vs Memcached
• System Design Interview Guide
• Distributed Systems Guide
• Learning Paths