Katkat
Back

Debug Round-Robin and Consistent-Hash Routing

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the ability to identify flaws in load balancing implementations by evaluating consistency, distribution, and edge-case handling in Round-Robin and Consistent Hashing logic.

Problem Statement

You are working on a load-balancing service for a distributed delivery platform. You have two legacy components that are currently exhibiting intermittent issues under load. Your task is to analyze the bugs in the provided pseudo-logic and propose fixes.

1. The Round-Robin Router

The implementation tracks the next_server_index and increments it by 1 for each request, using next_server_index % servers.length.

The Bug: During peak traffic, the service experiences 'hot spots' because certain servers are consistently overwhelmed, and the router does not account for server health or dynamic membership changes. Additionally, the index increments beyond int capacity over long periods.

2. The Consistent-Hash Router

The router maps servers and requests onto a hash ring (integer space 0 to 2^32 - 1). Each server is assigned v virtual nodes to improve distribution.

The Bug:

  1. Ring Wraparound: Requests with a hash value greater than the last server's hash are sometimes dropped instead of being routed to the first server in the ring.
  2. Remapping Storms: When a single server node fails, the implementation causes a cascading remapping of almost all keys rather than shifting only the keys belonging to the failed node.

Your Tasks

  1. Provide a fix for the Round-Robin index overflow and suggest a strategy to incorporate server weights (e.g., higher capacity servers receive more requests).
  2. Write a function find_server(request_key) for the Consistent Hashing router that correctly handles ring wraparound using binary search.
  3. Identify why the remapping storm occurs and how virtual nodes mitigate this issue.
# Example signature for the Consistent Hashing find_server
def find_server(request_hash, sorted_ring_nodes):
    # sorted_ring_nodes is a list of tuples: (hash_value, server_id)
    # Returns the appropriate server_id
    pass

Hints

Hint 1

For Round-Robin, use a thread-safe atomic counter or reset the counter to zero when it reaches a high threshold to prevent overflow.

Hint 2

For Consistent Hashing, think of the ring as a circular array where the search should wrap back to index 0 if the request hash is larger than all elements in the sorted list.

Hint 3

Virtual nodes solve the 'remapping storm' by ensuring that a single physical server's hash space is fragmented across the ring, so its failure only impacts neighbors in the ring rather than the entire hash space.

Follow-up questions

  • How would you implement health checks to ensure the Round-Robin router doesn't route traffic to a crashed server?
  • If you have 100 virtual nodes per server, how does this affect the memory usage of the hash ring and the time complexity of the binary search?
  • In a production system, how would you handle the 'thundering herd' problem if a popular server node suddenly returns to the ring?