envoyproxy / envoyproxy/envoy

lb: core support for latency-aware LB policies

Open
#44,686 9 comments 12 reactions 1 assignee Claimed by @tonya11en View on GitHub
area/load balancing enhancement
Dominant language
C++
Stars
28.9k
Forks
5.6k
Avg merge
1d 20h
Merged PRs (30d)
428

Description

cc @tonya11en @botengyao @wbpcode @ggreenway @frittentheke @kahirokunn

[In #43588 I said I'd come back with a starting point](https://github.com/envoyproxy/envoy/pull/43588#issuecomment-4095373533) before writing more code. This is it.

## Problem Statement

Latency-aware load balancers (Peak EWMA, Twitter Aperture's P2C+EWMA, etc.) make selection decisions on per-host per-response latency.

The current contrib `peak_ewma` extension gets that signal by [shipping a companion L7 HTTP filter that the user has to add to every listener](https://github.com/envoyproxy/envoy/pull/40653).

@tonya11en rightly flagged this architecture in #43588 as the wrong layer: ["requiring a supplementary L7 filter to track per-endpoint latency stats violates separation of concerns in an unacceptable way and is too hacky"](https://github.com/envoyproxy/envoy/pull/43588#issuecomment-4077107553).

The suggested direction is to use [core LB infrastructure support such tracking](https://github.com/envoyproxy/envoy/pull/43588#issuecomment-4093200472).

## Load balancing algorithms

@tonya11en [previously alluded to the general class of latency-aware/adaptive LB algorithms](https://github.com/envoyproxy/envoy/pull/43588#issuecomment-4093200472), mentioning Prequal and C3 by name and suggesting using "a more modern equivalent" to Peak EWMA.

I did a sweep of potential candidates:

| Algorithm | Inputs | Collection | Requires upstream cooperation? |
|---|---|---|---|
| P2C + Peak EWMA, including lineal descendants ([original contrib implementation](https://github.com/envoyproxy/envoy/pull/40653); [Linkerd2-proxy](https://github.com/linkerd/linkerd2-proxy/blob/main/linkerd/proxy/balance/src/lib.rs); [Twitter Finagle Aperture](https://twitter.github.io/finagle/guide/Clients.html#aperture-least-loaded); [DataStax `LatencyAndInflightCount`](https://github.com/datastax/java-driver-policies)) | per-response latency, in-flight count | passive observation, every response | no |
| [Prequal (Wydrowski et al., '24)](https://www.usenix.org/system/files/nsdi24-wydrowski.pdf) | requests-in-flight and latency reported in probe responses | active probes; server-side module ([see p. 1289](https://www.usenix.org/system/files/nsdi24-wydrowski.pdf#page=6)) | yes |
| [C3 (Suresh et al., '15)](https://www.usenix.org/system/files/conference/nsdi15/nsdi15-paper-suresh.pdf) | service rate, queue size, recent throughput | piggybacked on each response ([see p. 517](https://www.usenix.org/system/files/conference/nsdi15/nsdi15-paper-suresh.pdf#page=6)) | yes |
| [Meta ServiceRouter (Saokar et al., OSDI '23)](https://www.usenix.org/system/files/osdi23-saokar.pdf) | server-reported load (outstanding requests or CPU) plus cross-region RTT | piggybacked on each response, with polling fallback ([see p. 976](https://www.usenix.org/system/files/osdi23-saokar.pdf#page=9)) | yes |
| [Meta tail-utilization router (eng blog, '24)](https://engineering.fb.com/2024/07/10/production-engineering/tail-utilization-ads-inference-meta/) | per-model load counter (CPU time of active+queued requests) | polled pre-dispatch or piggybacked on each response (see "Tuning load balancing mechanisms") | yes |
| [L3 (Michaelis et al., Middleware '24)](https://schmiste.github.io/mw24.pdf): multi-cluster traffic-split, not per-host | per-backend latency, success rate, RPS, in-flight requests | sidecar-emitted metrics scraped every 5s; per-cluster aggregate ([see p. 6](https://schmiste.github.io/mw24.pdf#page=6)) | no |
| [Round-robin](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/extensions/load_balancing_policies/round_robin/round_robin_lb.h) / [least-request](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/extensions/load_balancing_policies/least_request/least_request_lb.cc) / [Maglev](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/extensions/load_balancing_policies/maglev/maglev_lb.cc) / [ring-hash](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/extensions/load_balancing_policies/ring_hash/ring_hash_lb.cc) | in-flight count or hash key | existing host stats / request hash | no |

Did I miss anything?

To my mind, the big distinction between Peak EWMA and Prequal/C3/etc. is that it doesn't require upstream cooperation. Perhaps this isn't a benefit in closed systems. But in many situations modifying upstreams to enable cooperation is either undesirable or impossible.

## Core API proposal

I propose adding a second callback on [`HostLbPolicyData`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/envoy/upstream/host_description.h#L100-L122), mirroring the ORCA pair, with the same [`receivesX() PURE`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/envoy/upstream/host_description.h#L107) flag the router already uses to skip work for non-consumers:

```cpp
// envoy/upstream/host_description.h: additions to HostLbPolicyData
virtual bool receivesUpstreamResponse() const PURE;

struct UpstreamResponseData {
// first_upstream_rx_byte_received_ minus first_upstream_tx_byte_sent_.
// Note: in current Envoy this fires after response headers are parsed,
// so it's "time to response headers received," not literal first byte.
std::chrono::nanoseconds time_to_response_headers{0};
};

virtual absl::Status onUpstreamResponse(const UpstreamResponseData&,
const StreamInfo::StreamInfo&) {
return absl::OkStatus();
}
```

The router would call this from [`Filter::onUpstreamComplete`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/common/router/router.cc#L1988), using the same pattern as [`maybeProcessOrcaLoadReport`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/source/common/router/router.cc#L2419-L2470). Non-consumers (round-robin, least-request, ring-hash, CSWR, maglev) pay one virtual `return false;` per response.

Notes:
1. Returning `absl::Status` and taking `const StreamInfo&` matches the ORCA callback exactly, so consumers can read response code, protocol, or bytes later without an API change.
2. 5xx filtering is intentionally not the LB's job here. Outlier detection ejects unhealthy hosts; the LB balances among what's left.

## Peak EWMA use sketch

Here's how the contrib `peak_ewma` extension would consume the new callback. The companion L7 filter disappears.

```cpp
// contrib/peak_ewma/load_balancing_policies/source/host_data.h
struct PeakEwmaHostLbPolicyData : public Upstream::HostLbPolicyData {
bool receivesOrcaLoadReport() const override { return false; }
bool receivesUpstreamResponse() const override { return true; }
absl::Status onUpstreamResponse(const UpstreamResponseData&,
const StreamInfo::StreamInfo&) override;
// ... existing ring buffer + EWMA state, unchanged ...
};
```

```cpp
// contrib/peak_ewma/load_balancing_policies/source/host_data.cc
absl::Status PeakEwmaHostLbPolicyData::onUpstreamResponse(
const UpstreamResponseData& data, const StreamInfo::StreamInfo&) {
if (data.time_to_response_headers.count() == 0) return absl::OkStatus();
const double rtt_ms = std::chrono::duration(
data.time_to_response_headers).count();
const uint64_t timestamp_ns = std::chrono::duration_cast(
time_source_.monotonicTime().time_since_epoch()).count();
recordRttSample(rtt_ms, timestamp_ns);
return absl::OkStatus();
}
```

The body of the override is the same logic the [current L7 filter runs](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/contrib/peak_ewma/filters/http/source/peak_ewma_filter.cc#L12-L51), minus the `StreamInfo` plumbing the filter has to do to get at the timing fields. The router has already extracted them.

What goes away:
- [`contrib/peak_ewma/filters/http/source/*`](https://github.com/envoyproxy/envoy/tree/70765d736d1e8cf86f3d140dea4a6a70e946e143/contrib/peak_ewma/filters/http/source) (filter, filter config, BUILD)
- [`contrib/peak_ewma/filters/http/test/*`](https://github.com/envoyproxy/envoy/tree/70765d736d1e8cf86f3d140dea4a6a70e946e143/contrib/peak_ewma/filters/http/test) (filter tests, BUILD)
- [`api/contrib/envoy/extensions/filters/http/peak_ewma/v3alpha/*`](https://github.com/envoyproxy/envoy/tree/70765d736d1e8cf86f3d140dea4a6a70e946e143/api/contrib/envoy/extensions/filters/http/peak_ewma/v3alpha) (filter proto)
- The `envoy.filters.http.peak_ewma` registration in [`contrib/contrib_build_config.bzl`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/contrib/contrib_build_config.bzl#L17) and [`contrib/extensions_metadata.yaml`](https://github.com/envoyproxy/envoy/blob/70765d736d1e8cf86f3d140dea4a6a70e946e143/contrib/extensions_metadata.yaml#L166-L172)

Thoughts?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.