Design and implement consistent hashing to distribute keys across a dynamic set of backend nodes. Use a sorted map (e.g., a TreeMap keyed by hash values) to find the next node clockwise from a key’s hash. Specify the hash function choice, how many virtual nodes to use and why, and how to handle node additions/removals with minimal key movement. Provide APIs for put/get that map keys to nodes, analyze time/space complexity, and discuss failure handling, rebalancing, and testing strategies.

This question evaluates understanding of consistent hashing, virtual nodes, sorted-map ring representation, replication and quorum strategies, membership changes and failure handling, complexity analysis, and testing considerations for distributed key-value or cache sharding systems.

How do I approach System Design interview questions?

System Design questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master system design interviews.

What difficulty level is this interview question?

This is a medium difficulty System Design question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Design consistent hashing with a sorted map | DoorDash Interview Question

Consistent Hashing with a Sorted Map (Virtual Nodes)

Context

You are building a client-side library to map arbitrary keys to backend nodes (cache/storage shards) that can be added or removed at runtime with minimal remapping. Represent the consistent hash ring with a sorted map (e.g., a TreeMap keyed by 64-bit hash tokens). Lookups should find the next node clockwise from a key's hash, with wrap-around to the beginning of the ring.

Requirements

Hashing and Ring

Choose a hash function; justify the choice.
Use virtual nodes; specify how many per physical node and why. Support weights for heterogeneous node capacity.
Represent the ring using a sorted map keyed by hash tokens.

Membership Changes

Implement addNode/removeNode with minimal key movement.
Handle wrap-around and token collisions.

APIs

getNodeForKey(key) and getNNodesForKey(key, R) for replication.
put(key, value) and get(key) that route to the selected node(s). You may simulate per-node storage in-process.

Complexity

Analyze time and space complexity for lookup, add, remove, and put/get with replication factor R.

Reliability and Operations

Discuss node failure detection and what happens when a node is down.
Replication strategy, read/write quorum options, rebalancing, and capacity weighting.

Testing

Outline tests for correctness, distribution fairness, churn (add/remove), and failure scenarios.

Assume a single-process demo is fine. Use any language with a sorted map (e.g., TreeMap) and include code for the library and a brief example.

Consistent Hashing with a Sorted Map (Virtual Nodes)

Context

Requirements

Hashing and Ring

Choose a hash function; justify the choice.
Use virtual nodes; specify how many per physical node and why. Support weights for heterogeneous node capacity.
Represent the ring using a sorted map keyed by hash tokens.

Membership Changes

Implement addNode/removeNode with minimal key movement.
Handle wrap-around and token collisions.

APIs

getNodeForKey(key) and getNNodesForKey(key, R) for replication.
put(key, value) and get(key) that route to the selected node(s). You may simulate per-node storage in-process.

Complexity

Analyze time and space complexity for lookup, add, remove, and put/get with replication factor R.

Reliability and Operations

Discuss node failure detection and what happens when a node is down.
Replication strategy, read/write quorum options, rebalancing, and capacity weighting.

Testing

Outline tests for correctness, distribution fairness, churn (add/remove), and failure scenarios.

Assume a single-process demo is fine. Use any language with a sorted map (e.g., TreeMap) and include code for the library and a brief example.

Design consistent hashing with a sorted map

Quick Overview

Consistent Hashing with a Sorted Map (Virtual Nodes)

Context

Requirements

Solution

Submit Your Answer to Earn 20XP

Design consistent hashing with a sorted map

Quick Overview

Consistent Hashing with a Sorted Map (Virtual Nodes)

Context

Requirements

Solution

Submit Your Answer to Earn 20XP