Enhancement for Load Balancing During High-Concurrency Scenarios in EPP

[delavet]

What would you like to be added:

I would like to propose improvements to EPP's load balancing mechanism to better handle high-concurrency scenarios. Currently, when a large number of concurrent requests arrive simultaneously, EPP's routing decisions based on backend model server metrics snapshots can result in all requests being directed to the same model server, causing load imbalance.

Why is this needed:

During our customers' usage of GAIE's EPP, we identified a load imbalance issue in high-concurrency scenarios. When bursts of requests arrive simultaneously, since EPP makes routing decisions based on point-in-time snapshots of backend model server metrics, all concurrent requests tend to be scheduled to the same model server, resulting in load imbalance.

The following figure is a screenshot of the vllm Grafana dashboard, used to illustrate this issue. It can be observed that one of the pods was momentarily assigned significantly more requests than the others.

This behavior can lead to suboptimal resource utilization and potential performance degradation during traffic spikes.

We believe there's a opportunity to enhance EPP's routing algorithm to better distribute load during burst scenarios while maintaining its existing strengths. Therefore we implemented a BurstScorer plugin that tries to address this issue by tracking request frequencies to pods and adjusting scores accordingly during burst scenarios. This provides a simple solution to this problem.

This approach would differ from more complex solutions like latency prediction (as proposed in #1323) and could provide a more fundamental fix for burst-induced load imbalances. The idea shares some similarities with concepts discussed in #678 (Solution 3).

We're interested in community feedback on how to resolve this issue systematically and would appreciate guidance on potential approaches to address it. We're willing to contribute to implementing a solution if the community agrees this is a valuable enhancement.

[vMaroon]

This is a very interesting issue. I've also observed similar behavior when running demanding benchmarks on llm-d. I think an additional approach would be the utilization of these two new llm-d scorers:

1. Active request scoring ([feature] Added Active-Request-Scorer llm-d/llm-d-inference-scheduler#297) - introduced load-based scorer that looks at the active requests being served through the epp instance. Each request is tracked individually with its own TTL to ensure accurate timeout handling. Pods with fewer active requests receive higher scores
2. LRU Pod selection (feat: Add a scoring plugin to distribute new groups evenly llm-d/llm-d-inference-scheduler#357) - adds a new scoring plugin called "no-hit-lru-scorer" that helps distribute new groups evenly across pods by tracking which pods have least recently handled cache-miss requests. The plugin uses an LRU cache to give higher scores to pods that haven't recently served new groups, helping to balance cache growth

Note that (1) does not work with streaming currently, will be fixed after #1661.

[nirrozenbaum]

This is indeed an interesting issue.
additionally to what @vMaroon wrote (which I think point (1) sounds very close to what you suggested), we've also implemented weighted-random-picker, that uses score as weight of a pod and then performs random selection based on the weights.
This was tested in bursty workloads and has shows much better results than max score picker.
The main point is that there is some tradeoff - in bursty workloads in performs much better, but in non-bursty workloads - max-score-picker has shown better results.

more information in this thread:
llm-d/llm-d-inference-scheduler#298 (comment)