DoorDash VO 面试真题解析：Round-Robin Traffic Router 与 Pod 可用性

You are a Backend Engineer at DoorDash and realized that your service can no longer keep up with traffic. In order to deal with the increased load, your team has decided to scale horizontally by adding more pods that run your service.

In order to achieve this, your colleague implemented a traffic router that distributes incoming traffic among pods using a round-robin algorithm (requests are routed to pods on a cyclical basis). Unfortunately, their implementation doesn’t quite seem to work, and you are tasked with debugging the code.

The implementation consists of the following classes:

• TrafficRouter: Represents the Traffic Router. Its constructor takes a list of Backend pods as an argument.
• Pod: Represents a Pod running your service application. Its constructor takes hostname and port as arguments.
• Backend: Represents a Pod and its state ("AVAILABLE", "UNAVAILABLE"). Its constructor takes a Pod and a state as arguments.
• HttpRequest: Represents an incoming Http Request. Its constructor takes an id as an argument. All requests from a user share the same request id.

And the following methods:

• TrafficRouter.getBackend(request: HttpRequest): Returns the next available Pod that can serve the request using a round robin heuristic. If all Pods are unavailable, returns null.
• TrafficRouter.reportAvailability(backend: Backend, state: State): Marks a Backend Pod as either available or unavailable.
• TrafficRouter.addBackend(backend: Backend): Adds new backends to the rotation at runtime.

这道题考察的是一个带状态的 round-robin 负载均衡器。核心思路是用一个列表或队列维护 backend 的轮询顺序，同时记录每个 pod 的可用状态；在处理请求时，按顺序寻找下一个可用节点，找到就返回对应 backend，否则返回 null。需要注意两点：一是同一用户请求需要尽量保持路由一致，二是当某个 backend 通过 reportAvailability 变成不可用时，轮询逻辑要能跳过它；当新增 backend 时，则要把它正确加入轮询结构中。实现时通常会结合数组 / 列表、索引指针和状态映射来完成，关键是保证更新状态后仍能稳定地做循环选择。