Katkat
Back

Implement a consistent hashing ring

DoorDashSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates understanding of consistent hashing, virtual nodes, deterministic hash functions, and data structure design for efficient key-to-server mapping and dynamic membership changes.

Implement a class ConsistentHashRing that distributes keys across servers using a hash ring with virtual nodes.

Required API:

  • ConsistentHashRing(replicas_per_server: int)
  • add_server(server_id: str) -> None
  • remove_server(server_id: str) -> None
  • get_server(key: str) -> Optional[str]

Behavior:

  • Use any deterministic hash function that maps a string to a 32-bit integer.
  • When a server is added, create replicas_per_server virtual nodes at positions hash(server_id + "#" + i) for i = 0..replicas_per_server-1.
  • get_server(key) computes hash(key) and returns the server owning the first virtual node found when moving clockwise around the ring.
  • If there is no virtual node with position greater than or equal to hash(key), wrap around and return the server at the smallest position.
  • If the ring is empty, return None.
  • Removing a server removes all of its virtual nodes.

Target complexity:

  • add_server / remove_server: O(R log N) where R is the number of replicas added or removed
  • get_server: O(log N)