Consistent Hashing
Asked of: Software Engineer
Last updated

What's being tested
These problems test consistent hashing as a data-structure and routing algorithm: map arbitrary keys to nodes while minimizing remapping after addNode / removeNode. Interviewers expect clean APIs, deterministic hashing, sorted-ring lookup, virtual nodes, and complexity analysis.
Patterns & templates
-
Sorted ring representation — store hash positions in sorted order;
getNode(key)finds first position>= hash(key), wrapping to index0. -
Binary search lookup — use
bisect_left/TreeMap.ceilingEntry;getNodeisO(log V)whereV = nodes * virtualNodes. -
Virtual nodes — insert labels like
nodeId#replicaIndex; improves distribution versus one hash point per physical node. -
addNode(node)— hash each virtual node, insert into ring/map, track ownership metadata;O(R log V)forRreplicas. -
removeNode(node)— delete all virtual-node hashes for that node; maintainnode -> hashesto avoid scanning the whole ring. -
Collision handling — deterministic hashes can collide; resolve with bucket lists, rehashing salt, or storing
hash -> [virtualNodes]. -
Weighted distribution — allocate more virtual nodes to higher-capacity servers, e.g.
replicas = baseReplicas * weight.
Common pitfalls
Pitfall: Using Python’s built-in
hash()for routing; it is process-randomized, so use stable hashing likemd5,sha1,mmh3, orcrc32.
Pitfall: Forgetting ring wraparound when
bisect_leftreturns the end; the correct node is the first point on the ring.
Pitfall: Claiming removals are cheap without tracking each node’s virtual hashes; otherwise
removeNodecan degrade to scanning all virtual nodes.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Featured in interview prep guides
Practice questions
- Implement a consistent hashing ringDoorDash · Software Engineer · Onsite · easy
- Compute courier pay and implement load balancingDoorDash · Software Engineer · Onsite · medium
- Design consistent hashing for shardingDoorDash · Software Engineer · Onsite · hard
- Implement and compare round-robin and consistent hashingDoorDash · Software Engineer · Onsite · Medium
- Scale the cache to a distributed systemDoorDash · Software Engineer · Technical Screen · hard
- Implement consistent hashing ringDoorDash · Software Engineer · Technical Screen · Medium
- Design consistent hashing with a sorted mapDoorDash · Software Engineer · Technical Screen · medium
Related concepts
- Distributed Storage, Replication, and ConsistencySystem Design
- Distributed Key-Value Storage And TransactionsSystem Design
- Hashing-Based File IdentitySystem Design
- Round-Robin Load BalancingCoding & Algorithms
- Adobe Sharded Tenant Data And Transaction Integrity
- Distributed Systems Consistency And Low-Latency DesignSystem Design