This interview question evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer for Design consistent hashing with a sorted map states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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.
Quick Answer: This interview question evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer for Design consistent hashing with a sorted map states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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.
Constraints & Assumptions
Preserve the scope, facts, inputs, and requested outputs from the prompt above.
If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it.
Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate.
Clarifying Questions to Ask Guidance
Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
State explicit assumptions before making sizing or architecture decisions.
Prioritize the functional path first, then address reliability, security, observability, and rollout.
What a Strong Answer Covers Guidance
A scoped requirements summary with concrete non-goals and success metrics.
API, data model, architecture, consistency, capacity, and operations.
Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
A validation, monitoring, migration, and launch plan appropriate for the risk level.
Follow-up Questions Guidance
What breaks first at 10x traffic or data volume?
How would you degrade gracefully during dependency failures?
What metrics and alerts would prove the design is healthy after launch?