Katkat
Back

Design consistent hashing for sharding

DoorDashSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSystem Design

Last updated

This question evaluates understanding of consistent hashing, replica placement, dynamic membership, weighted load distribution, rebalancing impact, and related distributed-systems competencies for routing and sharding.

Design and implement a consistent-hashing based router that maps arbitrary keys to backend servers. Requirements: (

  1. Describe the hash ring, token assignment, and use of virtual nodes to smooth load; (
  2. Support addServer(id, weight) and removeServer(id) with minimal key movement; (
  3. Implement getServer(key) and explain the expected percentage of keys that move when servers join/leave; (
  4. Extend to replicate each key to R distinct servers and discuss read/write semantics under failures; (
  5. Analyze time/space complexity and storage overhead.