envoyproxy/envoy

Introduce prequal algorithm into envoy

Open

#42091 opened on Nov 18, 2025

View on GitHub
 (7 comments) (1 reaction) (0 assignees)C++ (27,997 stars) (5,373 forks)batch import
area/load balancingenhancementhelp wanted

Description

Title: Introduce prequal algorithm into envoy

Description: We have been experimenting with leveraging prequal as a load balancing algorithm in our service mesh and it has shown very good preliminary results for P99.9 latencies and beyond. We think it would be nice to have an official implementation of this algorithm in envoy. It is a type of cooperative load balancing algorithms where the upstream side has an important part to play. I have shared links in the description below that explain the algorithm in more detail.

[optional Relevant Links:] https://arxiv.org/pdf/2312.10172 https://www.usenix.org/system/files/nsdi24_slides-wydrowski.pdf

Contributor guide

Tech stack
cpp
Domain
backend
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
5
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
C++Envoy architectureLoad balancing concepts
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
15
Research direction
Study the prequal algorithm from the provided arXiv paper (2312.10172) and the USENIX slides. Familiarize yourself with Envoy's load balancing subsystem, particularly the existing algorithms (e.g., round robin, least request) in source/common/upstream/. Review the 7 comments on this issue for any additional context or constraints. Propose an implementation plan that outlines the necessary changes to Envoy's load balancer factory and upstream host selection logic.