Design consistent hashing for sharding

Q: Design consistent hashing for sharding

This is a System Design interview question from DoorDash for Software Engineer roles. View the full question and solution on PracHub.

Q: 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.

Question

Design a Consistent-Hashing Router with Replication

You are building a stateless router that maps arbitrary keys (for example, request IDs or cache keys) to backend servers. The router must support dynamic membership, weighted capacity, and multi-replica placement while minimizing key movement when servers join or leave.

Requirements:

Hash Ring and Load Smoothing
- Describe the consistent-hash ring, token assignment, and how virtual nodes (vnodes) smooth load imbalance.
Membership Operations
- Provide addServer(id, weight) and removeServer(id) that change as few key-to-server assignments as possible.
Key Lookup and Rebalancing Impact
- Implement getServer(key) and explain the expected percentage of keys that move when servers join or leave (both equal-weight and weighted cases).
Replication to R Distinct Servers
- Extend the design to place each key on R distinct servers and discuss read/write semantics and client behavior under server failures.
Complexity and Overhead
- Analyze time complexity, space complexity, and storage/replication overhead. Include any operational guardrails or validation strategies you would use.

Design consistent hashing for sharding

Design a Consistent-Hashing Router with Replication

Solution (Locked)

Comments (0)