Katkat
Back

Implement a Consistent Hash Ring

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to implement a distributed hashing mechanism that minimizes data movement when adding or removing nodes.

Consistent Hash Ring Implementation

Implement a consistent hash ring data structure to map keys to backend servers. Use virtual nodes to ensure uniform data distribution and minimize remapping overhead.

Requirements:

  1. add_node(node_id, weight): Adds a physical server to the ring. The weight determines how many virtual nodes are created for this server.
  2. remove_node(node_id): Removes a physical server and all its associated virtual nodes from the ring.
  3. get_node(key): Returns the node_id that should store the given key based on the consistent hashing logic.

Technical Constraints:

  • Use a cryptographic or stable non-cryptographic hash function to map nodes and keys to a fixed range (e.g., 0 to 2^32 - 1).
  • The data structure must be optimized for get_node operations (O(log N) time complexity).
  • You must provide a way to map virtual nodes back to their physical host.

Example:

ring = ConsistentHashRing()
ring.add_node("Server_A", weight=2)
# Server_A might map to positions [100, 500] in the ring

ring.get_node("order_123") # Returns "Server_A"

Edge Cases to Consider:

  • What happens if two virtual nodes hash to the same value? (Implement deterministic collision handling).
  • How does the ring behave when it is empty?
  • Ensure the implementation is thread-safe for concurrent read/write access.

Hints

Hint 1

Use a sorted list or a balanced binary search tree to store the hash positions of virtual nodes.

Hint 2

For `get_node(key)`, hash the key and find the first virtual node in the sorted structure with a hash value greater than or equal to the key's hash (the 'successor').

Hint 3

To handle weights, assign each physical node multiple virtual node identifiers by appending an index to the `node_id` (e.g., "Server_A_0", "Server_A_1").

Follow-up questions

  • How would you modify this to support replication, where a key is stored on the primary node and the next N-1 successor nodes?
  • If a physical node experiences a sudden increase in load, how could you dynamically rebalance the cluster using virtual node weights?
  • Explain the strategy for migrating keys when a node is removed from the ring to minimize downtime.