Hi.
This is the peak EWMA option for "balance random" that I announced with
the random draws patches [1]. I send it for the archive, not for
merging: in my tests it only beat leastconn when servers were slow for a
long time for a reason their number of streams does not show. The long
version, with charts, is in two blog posts [2] [3].
The option:
balance random(<draws>) peak-ewma [tau <time>] [default-rtt <time>]
The drawn servers are then compared on a peak EWMA of their response
time, multiplied by their number of streams plus one and divided by
their weight, as in the balancer of Finagle and Linkerd. The series
applies on top of [1].
Compared to my first attempt [4], there is no new algorithm and no tree
anymore. Only the comparison in get_server_rnd() changes, the estimate
is fed from stream_update_time_stats() and kept per thread group, with
integer arithmetic only. A failed connect or response counts as a
sample of tau. doc/internals/peak-ewma.txt and the commit messages have
the details.
On a test bed with 32 servers, 4 of them always at 50 ms and the others
at 5 ms, with 128 clients ("slow" is the share of the requests sent to
the 4 slow servers):
algorithm slow p99 req/s
random(2) 4.0 % 52 ms 15537
leastconn 2.0 % 51 ms 18098
random(2) peak-ewma 1.63 % 51 ms 18674
random(3) peak-ewma 0.40 % 8.3 ms 20355
A Lua prototype with "use-server" distributed the same way, at a much
higher CPU cost.
But that is the one case the option is made for. I also rebuilt Willy's
2019 "power of two" test [5] (MyTime, slowness from CPU contention) and
ran gRPC services on JVMs with real GC pauses, once behind one central
HAProxy and once with one sidecar per client. In MyTime leastconn was
still the best with 2 and 1 cores and tied with 4, random(3) peak-ewma
landed between leastconn and random(2). With gRPC, leastconn and peak
EWMA were within 1 ms at p99. Each setting ran only once or twice, so
small differences are within the noise.
My reading is that leastconn sees a stalled server at once through its
outstanding streams, while a response time only arrives once the slow
response is back, and that leastconn compares all servers instead of 2
or 3. My runs do not tell which of the two matters more. For servers of
different capacity, leastconn with matching weights plus "observe
layer7" looks simpler to me, though I did not measure that against peak
EWMA.
If someone still wants it, these would be the open questions:
- In #1570 [6] Willy suggested to adjust the weights continuously
instead. I compare at selection time to avoid constant tree updates
and oscillating weights.
- Should failures add a penalty sample, or be left to the health
checks and "observe"?
- Millisecond resolution is too coarse for servers answering in less
than 1 ms; nanoseconds would cost 8 bytes per stream.
- The estimate is not shared between thread groups.
The test beds and scripts are in [7]. I will close #1570 with these
results.
[1] https://www.mail-archive.com/[email protected]/msg47703.html
[2] https://blog.none.at/blog/2026/2026-10-31-peak-ewma-in-haproxy/
[3] https://blog.none.at/blog/2026/2026-11-01-haproxy-leastconn-vs-power-of-two/
[4] https://www.mail-archive.com/[email protected]/msg46569.html
[5] https://www.haproxy.com/blog/power-of-two-load-balancing
[6] https://github.com/haproxy/haproxy/issues/1570
[7] https://github.com/git001/peak-ewma-hap
Regards,
Aleksandar
Aleksandar Lazic (6):
MINOR: server: add a peak EWMA of the response time
MINOR: stream: feed the peak EWMA of the servers
MEDIUM: backend: add the peak-ewma option to the random algorithm
DOC: config: document the peak-ewma option of the random algorithm
DOC: internals: describe the peak EWMA load balancing
REGTESTS: balance: add a test for random peak-ewma
doc/configuration.txt | 60 +++++++++++-
doc/internals/peak-ewma.txt | 240
+++++++++++++++++++++++++++++++++++++++++++++
include/haproxy/backend-t.h | 2 +
include/haproxy/lb_pewma.h | 139 ++++++++++++++++++++++++++
include/haproxy/server-t.h | 2 +
reg-tests/balance/balance-random-peak-ewma.vtc | 62 ++++++++++++
src/backend.c | 101 ++++++++++++++++++-
src/proxy.c | 2 +
src/stream.c | 30 +++++-
9 files changed, 631 insertions(+), 7 deletions(-)
From 7cd6c67cee82f3fdcdae3c31ad427990a4120c4c Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:38:06 +0100
Subject: [RFC PATCH 6/6] REGTESTS: balance: add a test for random peak-ewma
Two servers, one answering after 200ms. After one request forced on each
of them to give them a sample, all requests must reach the fast one.
With 20 draws, the slow one can only be picked if all draws hit it
(probability 2^-20). The test fails without the peak-ewma option.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
.../balance/balance-random-peak-ewma.vtc | 62 +++++++++++++++++++
1 file changed, 62 insertions(+)
create mode 100644 reg-tests/balance/balance-random-peak-ewma.vtc
diff --git a/reg-tests/balance/balance-random-peak-ewma.vtc b/reg-tests/balance/balance-random-peak-ewma.vtc
new file mode 100644
index 000000000..27ff9fb28
--- /dev/null
+++ b/reg-tests/balance/balance-random-peak-ewma.vtc
@@ -0,0 +1,62 @@
+vtest "Test for balance random peak-ewma"
+feature ignore_unknown_macro
+
+# srv1 answers after 200ms, srv2 at once. One request is forced to each
+# server to give it a sample, then all other requests must go to srv2: with
+# 20 draws, srv1 can only be picked when all of them hit it, which happens
+# with a probability of 2^-20. A request sent to srv1 would fail as s1 only
+# accepts one connection.
+
+server s1 {
+ rxreq
+ delay 0.2
+ txresp -hdr "Server: s1"
+} -start
+
+server s2 {
+ rxreq
+ txresp -hdr "Server: s2"
+} -repeat 11 -start
+
+haproxy h1 -arg "-L A" -conf {
+ global
+ .if feature(THREAD)
+ thread-groups 1
+ .endif
+
+ defaults
+ mode http
+ timeout server "${HAPROXY_TEST_TIMEOUT-5s}"
+ timeout connect "${HAPROXY_TEST_TIMEOUT-5s}"
+ timeout client "${HAPROXY_TEST_TIMEOUT-5s}"
+
+ listen px
+ bind "fd@${px}"
+ balance random(20) peak-ewma
+ http-reuse never
+ use-server srv1 if { path /warm1 }
+ use-server srv2 if { path /warm2 }
+ server srv1 ${s1_addr}:${s1_port}
+ server srv2 ${s2_addr}:${s2_port}
+} -start
+
+client c1 -connect ${h1_px_sock} {
+ txreq -url "/warm1"
+ rxresp
+ expect resp.status == 200
+ expect resp.http.Server ~ s1
+} -run
+
+client c2 -connect ${h1_px_sock} {
+ txreq -url "/warm2"
+ rxresp
+ expect resp.status == 200
+ expect resp.http.Server ~ s2
+} -run
+
+client c3 -connect ${h1_px_sock} {
+ txreq -url "/"
+ rxresp
+ expect resp.status == 200
+ expect resp.http.Server ~ s2
+} -repeat 10 -run
--
2.56.0
From 40974c41cfd7be8437a1ccba75c82681e2743cad Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:36:49 +0100
Subject: [RFC PATCH 5/6] DOC: internals: describe the peak EWMA load balancing
There is no specification of the peak EWMA, only the Finagle code and a
few blog posts. This document describes the algorithm with references,
how it is implemented in HAProxy (state per thread group, samples,
penalty, integer approximations of the exponentials) and how it differs
from Finagle's. It also explains what the number of draws, the repeated
draws and the weights mean for the share of requests sent to slow
servers, with measurements of the core implementation against a Lua
prototype on a Kubernetes test bed.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
doc/internals/peak-ewma.txt | 240 ++++++++++++++++++++++++++++++++++++
1 file changed, 240 insertions(+)
create mode 100644 doc/internals/peak-ewma.txt
diff --git a/doc/internals/peak-ewma.txt b/doc/internals/peak-ewma.txt
new file mode 100644
index 000000000..d0f0ef9e6
--- /dev/null
+++ b/doc/internals/peak-ewma.txt
@@ -0,0 +1,240 @@
+2026/10/30 - Peak EWMA load balancing - Aleksandar Lazic <[email protected]>
+
+This document describes the peak EWMA option of the "random" load balancing
+algorithm ("balance random(<draws>) peak-ewma"), where it comes from, how it
+is implemented in HAProxy and how it differs from the original.
+
+
+1. Origin and references
+------------------------
+
+Peak EWMA was introduced around 2014 in Finagle, the RPC library of Twitter,
+and later reused by Linkerd 1, Tower (Rust) and Envoy. There is no paper nor
+specification, the reference is the Finagle code. Useful descriptions:
+
+ - Finagle code, the reference implementation (about 100 lines):
+ https://github.com/twitter/finagle/blob/develop/finagle-core/src/main/scala/com/twitter/finagle/loadbalancer/PeakEwma.scala
+
+ - Finagle user guide, "Power of Two Choices (P2C) + Peak EWMA":
+ https://twitter.github.io/finagle/guide/Clients.html#power-of-two-choices-p2c-peak-ewma
+
+ - "Beyond Round Robin: Load Balancing for Latency", Steve Jenson and Ruben
+ Oanta, Linkerd blog, 2016/03/16, with simulations comparing round robin,
+ least loaded and peak EWMA:
+ https://linkerd.io/2016/03/16/beyond-round-robin-load-balancing-for-latency/
+
+ - Tower, tower::load::PeakEwma:
+ https://docs.rs/tower/latest/tower/load/peak_ewma/struct.PeakEwma.html
+
+ - The power of two random choices, the selection used around it:
+ http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
+
+
+2. The algorithm
+----------------
+
+Each server has an estimate of its response time (RTT), and a cost:
+
+ cost = rtt_estimate * (outstanding requests + 1)
+
+A few servers are drawn at random (two in Finagle), and the one with the
+lowest cost gets the request. Counting the outstanding requests alone (least
+connections) does not tell a slow server from a fast one: a slow server with
+few requests wins against a fast one with a few more. Multiplying by the
+response time makes a server twice as slow look twice as loaded.
+
+The estimate is a moving average with two particularities:
+
+ - "peak": a sample above the average replaces it at once. A server
+ becoming slow is avoided from its first slow response, instead of after
+ many of them.
+
+ - the weights depend on the time, not on the number of samples. A sample
+ taken dt after the previous one weighs 1 - exp(-dt / tau), and the
+ average decays with exp(-dt / tau) in between. A server which becomes
+ fast again gets back to its normal estimate within a few tau, whatever
+ its request rate. A server which was avoided, and thus gets no samples,
+ sees its estimate decay towards zero, so that it is tried again.
+
+tau is the time constant (decay time), 10 seconds by default in Finagle.
+
+
+3. Implementation in HAProxy
+----------------------------
+
+3.1. Configuration
+
+ balance random(<draws>) peak-ewma [tau <time>] [default-rtt <time>]
+
+The option only changes how the drawn servers are compared in
+get_server_rnd(): the cost replaces the number of served streams, and is
+divided by the server's weight (cross multiplied, as before). Everything
+else of "random" is unchanged, including the tie-break on the request rate,
+the "avoid" server, and the checks on maxconn and queues. tau defaults to
+10s and default-rtt to 10ms.
+
+3.2. State
+
+Each server has, per thread group (struct srv_per_tgroup), the estimate in
+microseconds and the date of its last update in nanoseconds (now_ns). The
+estimate is updated with a CAS loop, the date stored after it. Keeping it
+per thread group avoids contention between groups on one cache line; each
+group thus has its own view, like separate load balancers would. The
+functions are in include/haproxy/lb_pewma.h.
+
+3.3. Samples
+
+stream_update_time_stats() feeds the estimate at the end of each stream,
+only when the backend uses the option:
+
+ - HTTP: the response time "Tr" (time to the response headers, without
+ queue and connect time). In other modes: the connect time "Tc".
+
+ - The timers are truncated to milliseconds. 500 us are added to take the
+ middle of the range, otherwise a server answering in less than one
+ millisecond gets 1 us and a single 1 ms answer makes it look 1000 times
+ slower. Below one millisecond the estimates do not tell the servers
+ apart and the choice mostly depends on the number of streams.
+
+ - A server which failed to connect or to respond (SF_ERR_SRVTO or
+ SF_ERR_SRVCL without a response) gets a sample of tau. Otherwise a
+ server failing fast would look like the fastest one and attract the
+ traffic. A stream aborted by the client counts as nothing.
+
+ - A response is a sample, whatever its status. A server quickly
+ answering 503 thus looks fast and attracts the traffic, as it does
+ with leastconn. Deciding which statuses are server failures is left
+ to "observe layer7" and "on-error", which take such a server out for
+ all algorithms, instead of doing it a second time here.
+
+ - A server without any sample yet costs default-rtt, the first sample
+ replaces it.
+
+3.4. Integer arithmetic
+
+No floating point is used in the core, so the exponentials are
+approximated:
+
+ - The weight of a sample, 1 - exp(-dt / tau), becomes dt / (dt + tau). Both
+ are about dt / tau for small dt and tend to 1 for large dt, which is what
+ matters while a server receives traffic.
+
+ - The decay, v * exp(-dt / tau), decides when an avoided server is tried
+ again, so it needs the right tail. The value is halved for each half-life
+ tau * ln(2) elapsed (ln(2) written as 693 / 1000), and linearly
+ interpolated within the last one. This stays within 6% of the
+ exponential. The simpler v * tau / (tau + dt) would keep a penalized
+ server away for hours instead of about a minute:
+
+ 10 s penalty, tau = 10 s exp halving tau/(tau+dt)
+ after 10 s 3.68 s 3.89 s 5.0 s
+ after 60 s 25 ms 26 ms 1.43 s
+ after 120 s 0.06 ms 0.06 ms 0.77 s
+
+ - The decay is only applied when reading. An update blends the sample into
+ the stored value with the weight of the elapsed time, which already
+ accounts for the decay; decaying first and blending then would decay
+ twice.
+
+ - The cost, rtt * (served + 1), is capped to ULLONG_MAX / SRV_EWGHT_MAX so
+ that it can be multiplied by a weight.
+
+
+4. Differences with Finagle
+---------------------------
+
+ - Finagle uses floating point and exp(); HAProxy uses the approximations
+ of 3.4.
+
+ - Finagle measures the RTT in nanoseconds from the request to the
+ response; HAProxy uses Tr (or Tc) in milliseconds, see 3.3.
+
+ - Finagle has no penalty for failures, they are handled by a separate
+ mechanism (failure accrual). Its "Penalty" only applies to a server
+ without any sample which already has outstanding requests. HAProxy
+ penalizes failures with a sample of tau, see 3.3.
+
+ - Finagle gives a server without any sample a cost of zero. HAProxy uses
+ default-rtt, like Envoy and Tower do.
+
+ - Finagle always draws two servers; HAProxy uses the number of draws of
+ "random". The draws reuse the ring of consistent hashing (with a
+ random number instead of a hash of the request), and a draw returning
+ the best server so far is repeated, so that different servers are
+ compared.
+
+ - Finagle keeps one estimate per client; HAProxy keeps one per server and
+ thread group, not shared between thread groups nor instances.
+
+
+5. Number of draws and measurements
+-----------------------------------
+
+A slow server is only picked when all draws hit slow servers. With S slow
+servers out of N and d distinct draws, this happens for C(S,d) / C(N,d) of
+the requests, about (S/N)^d for large farms, whatever the estimates. Two
+properties of "random" matter for this to hold:
+
+ - the draws must compare different servers. Drawing the best server
+ again used to waste the draw; it is now repeated.
+
+ - the servers must have the same chance to be drawn. "random" hashes
+ nothing from the request, but reuses the ring of consistent hashing:
+ a server gets 16 points per unit of weight, placed by hashing its ID,
+ and each draw takes the server with the point nearest to a random
+ 32-bit number. With the default weight of 1, the shares of the ring
+ vary between about 2% and 4% for 32 servers, and the servers drawn
+ more often have more streams, so they lose more comparisons against
+ slow servers. The same weight of 100 for all servers (1600 points
+ each) makes the shares almost even, without changing the relative
+ weights:
+
+ backend app
+ balance random(3) peak-ewma
+ default-server weight 100
+ server s1 ...
+
+Test bed: 32 servers on 3 nodes, 4 of them answering in 50 ms and the
+others in 5 ms, one of the fast ones slowed down to 100 ms during each
+run, 2 HAProxy instances with 3 threads each, h2load with 32 or 128
+concurrent clients, 3 runs of 30 s per algorithm. "slow" is the share of
+the requests sent to the 4 slow servers, "idle" the Idle_pct of the two
+HAProxy instances. The Lua prototype implements the same algorithm with
+distinct and uniform draws, the core implementation ran with the repeated
+draws and weight 100. The lines for random(2), leastconn and "Lua, all
+servers" come from an earlier run on the same test bed.
+
+ 32 clients slow mean p99 req/s
+ random(2) 7.2 % 9.9 ms 52 ms 3217
+ leastconn 3.3 % 7.7 ms 51 ms 4125
+ Lua, 2 draws 1.57 % 6.8 ms 51 ms 4664
+ random(2) peak-ewma 1.53 % 6.7 ms 51 ms 4732
+ Lua, 3 draws 0.20 % 6.1 ms 7.3 ms 5263
+ random(3) peak-ewma 0.20 % 6.0 ms 7.0 ms 5298
+ Lua, all servers 0.0 % 6.3 ms 8.9 ms 5092
+
+ 128 clients slow mean p99 req/s idle
+ random(2) 4.0 % 8.2 ms 52 ms 15537 59/70 %
+ leastconn 2.0 % 7.0 ms 51 ms 18098 59/61 %
+ Lua, 2 draws 1.67 % 7.3 ms 51 ms 17298 57/59 %
+ random(2) peak-ewma 1.63 % 6.8 ms 51 ms 18674 61/62 %
+ Lua, 3 draws 0.23 % 6.5 ms 13 ms 19351 51/39 %
+ random(3) peak-ewma 0.40 % 6.2 ms 8.3 ms 20355 58/58 %
+ Lua, all servers 0.0 % 6.9 ms 12 ms 18286 24/10 %
+
+The core implementation and the Lua prototype send the same share of the
+requests to the slow servers, but the core one costs much less CPU, which
+shows at 128 clients in the throughput and the p99. With weight 1 and
+draws that could hit the same server, the core implementation sent 2.5%
+(2 draws) and 0.5% to 0.6% (3 draws) of the requests to the slow servers.
+
+The measured shares are above C(S,d) / C(N,d) (1.2% for 2 draws, 0.08%
+for 3), because the fast servers sometimes answer slowly too (up to 54 ms
+in this test bed) and the peak EWMA reacts to it, which is its purpose.
+
+With 2 draws the p99 stays at the slow servers' response time, as more
+than 1% of the requests still reach them. With 3 draws, it drops to the
+fast servers' one at almost no extra cost. Comparing all servers removes
+the last slow requests but sends many requests to the currently cheapest
+server (herding): the fast servers received between 1.1% and 5.4% of the
+requests instead of about 3.6%, and in Lua it costs most of the CPU.
--
2.56.0
From c6d8da057dec4924b6327fe46690282af708611e Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:36:23 +0100
Subject: [RFC PATCH 4/6] DOC: config: document the peak-ewma option of the
random algorithm
Describe "balance random(<draws>) peak-ewma [tau <time>]
[default-rtt <time>]": how the cost of a server is computed, what is
measured, the penalty for failing servers, the meaning and reasonable
range of "tau", and the limits of the option (the share of requests
still sent to slow servers depending on the number of draws and on the
shares of the hash ring, the millisecond resolution, the per thread
group averages not shared between instances).
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
doc/configuration.txt | 60 +++++++++++++++++++++++++++++++++++++++++--
1 file changed, 58 insertions(+), 2 deletions(-)
diff --git a/doc/configuration.txt b/doc/configuration.txt
index e4e145af8..b3427a9f6 100644
--- a/doc/configuration.txt
+++ b/doc/configuration.txt
@@ -6876,6 +6876,7 @@ balance url_param <param> [check_post]
random
random(<draws>)
+ random(<draws>) peak-ewma [tau <time>] [default-rtt <time>]
A random number will be used as the key for the consistent
hashing function. This means that the servers' weights are
respected, dynamic weight changes immediately take effect, as
@@ -6923,6 +6924,59 @@ balance url_param <param> [check_post]
distribution closer to a uniform draw, at the expense of a
larger tree.
+ With the "peak-ewma" option, the drawn servers are compared
+ on their expected response time instead of their number of
+ streams. Each server gets a peak EWMA of its response time:
+ the time to the response headers ("Tr") in HTTP mode, the
+ connect time ("Tc") otherwise. The cost of a server is this
+ average multiplied by its number of served streams plus
+ one, divided by its weight, and the server with the lowest
+ cost is picked. The average jumps at once to any slower
+ response, and moves back down progressively when the server
+ answers faster again. When a server is not used, its
+ average decays towards zero, so that a server avoided
+ because it was slow is tried again after a while. A server
+ which fails to connect or to respond gets a penalty of
+ "tau", a request aborted by the client is not counted. This
+ way slow or degraded servers receive much less traffic than
+ when only the number of streams is compared. A server which
+ quickly answers with errors (e.g. 503) looks fast though,
+ and attracts the traffic as it does with "leastconn": use
+ "observe layer7" with "on-error" on the servers to take it
+ out (see "observe"). The optional parameters are :
+
+ tau <time> is the time constant of the average,
+ in milliseconds by default. It is the
+ time it takes to forget about a slow
+ response, and roughly the time a
+ failing server is avoided. Values
+ between 1s and 60s are reasonable:
+ shorter ones make the average follow
+ the noise, longer ones keep a server
+ away longer once it has recovered. The
+ default value is 10s.
+
+ default-rtt <time> is the response time assumed for a
+ server which has not answered yet,
+ in milliseconds by default. The first
+ response replaces it. The default
+ value is 10ms.
+
+ A slow server is only picked when all draws hit slow
+ servers, so with S slow servers out of N, this still
+ happens for about (S/N)^<draws> of the requests, provided
+ that the servers have about the same share of the ring
+ (see the weights above). With "peak-ewma", 3 draws are a
+ good trade-off: the cost of the algorithm stays low and
+ the slow servers are almost never picked. The response
+ times are measured with a resolution of one millisecond,
+ so this option is meant for servers answering in several
+ milliseconds; below one millisecond the choice mostly
+ depends on the number of streams. The averages are kept
+ per thread group and are not shared between HAProxy
+ instances. This option is ignored for backends in LOG
+ mode.
+
For backends in LOG mode, the number of draws is ignored and
a single random is picked since there is no notion of server
load. Random log balancing can be useful with large farms or
@@ -6971,8 +7025,8 @@ balance url_param <param> [check_post]
sticky server doesn't change until it becomes DOWN.
<arguments> is an optional list of arguments which may be needed by some
- algorithms. Right now, only "url_param", "uri" and "log-hash"
- support an optional argument.
+ algorithms. Right now, only "url_param", "uri", "random" and
+ "log-hash" support an optional argument.
The load balancing algorithm of a backend is set to "random" when no other
algorithm, mode nor option have been set. The algorithm may only be set once
@@ -6985,6 +7039,8 @@ balance url_param <param> [check_post]
TCP/HTTP Examples :
balance roundrobin
+ balance random(3) peak-ewma
+ balance random(2) peak-ewma tau 30s default-rtt 50ms
balance url_param userid
balance url_param session_id check_post 64
balance hdr(User-Agent)
--
2.56.0
From 6df27ecb059942b55f23e1be731ee90d1dd79b8f Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:28:18 +0100
Subject: [RFC PATCH 3/6] MEDIUM: backend: add the peak-ewma option to the
random algorithm
"balance random(<draws>)" compares <draws> random servers and picks the
one with the least served streams relative to its weight. With many
servers of different speeds this is not enough: a slow server with few
streams still wins against a fast one with a few more.
The new "peak-ewma" option compares instead the peak EWMA of the
response time of the servers multiplied by their number of served
streams plus one, relative to their weight, as Finagle and Linkerd do
with their power of two choices balancer:
balance random(<draws>) peak-ewma [tau <time>] [default-rtt <time>]
"tau" is the time constant of the peak EWMA (default 10s), "default-rtt"
the response time assumed for a server without any sample yet (default
10ms). The cost is capped so that multiplying it by a weight cannot
overflow. With the same cost, the existing tie-break on the request
rate applies.
The option is reset by any "balance" statement so that a backend using
another algorithm does not inherit it from the defaults section, and
"tau" and "default-rtt" are inherited from the defaults section with
the algorithm. "random" now rejects any other argument than
"peak-ewma", it silently ignored them before.
Tested on a Kubernetes test bed (OVH MKS, c3-8 nodes): 32 servers, 4 of
them answering in 50 ms and the others in 5 ms, 2 HAProxy instances
with 3 threads, h2load with 128 concurrent clients, 3 runs of 30 s, on
top of the patch drawing different servers and with weight 100. Share
of the requests sent to the slow servers, and throughput:
random(2) 4.0 % 15537 req/s
leastconn 2.0 % 18098 req/s
random(2) peak-ewma 1.63 % 18674 req/s
random(3) peak-ewma 0.40 % 20355 req/s
The possible regression is limited to backends using the option: the
other ones only test lbprm.pewma_tau in get_server_rnd() and at the end
of each stream. doc/internals/peak-ewma.txt has the details.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
include/haproxy/backend-t.h | 1 +
src/backend.c | 101 ++++++++++++++++++++++++++++++++++--
src/proxy.c | 1 +
3 files changed, 100 insertions(+), 3 deletions(-)
diff --git a/include/haproxy/backend-t.h b/include/haproxy/backend-t.h
index 4387bb308..ce13ea4ed 100644
--- a/include/haproxy/backend-t.h
+++ b/include/haproxy/backend-t.h
@@ -193,6 +193,7 @@ struct lbprm {
int wdiv; /* ratio between effective weight and user weight */
int hash_balance_factor; /* load balancing factor * 100, 0 if disabled */
unsigned int pewma_tau; /* peak EWMA time constant in us, 0 if disabled */
+ unsigned int pewma_rtt; /* peak EWMA of a server without sample, in us */
unsigned int lb_free_list_nb; /* Number of elements in the free list */
struct sample_expr *expr; /* sample expression for "balance (log-)hash" */
char *arg_str; /* name of the URL parameter/header/cookie used for hashing */
diff --git a/src/backend.c b/src/backend.c
index 8231d01c7..b47783232 100644
--- a/src/backend.c
+++ b/src/backend.c
@@ -40,6 +40,7 @@
#include <haproxy/lb_fwlc.h>
#include <haproxy/lb_fwrr.h>
#include <haproxy/lb_map.h>
+#include <haproxy/lb_pewma.h>
#include <haproxy/lb_ss.h>
#include <haproxy/log.h>
#include <haproxy/namespace.h>
@@ -568,6 +569,23 @@ struct server *get_server_expr(struct stream *s, const struct server *avoid)
return map_get_server_hash(px, hash);
}
+/* Returns the peak EWMA cost of <srv> for the backend <px>: its peak EWMA
+ * response time multiplied by the number of streams it would serve with one
+ * more. It is capped so that it may still be multiplied by a weight.
+ */
+static inline ullong pewma_cost(const struct proxy *px, const struct server *srv)
+{
+ uint lat = srv_pewma_get(srv, px->lbprm.pewma_tau);
+ ullong cost;
+
+ if (lat == 0)
+ lat = px->lbprm.pewma_rtt;
+ cost = (ullong)lat * (srv->served + 1);
+ if (cost > ULLONG_MAX / SRV_EWGHT_MAX)
+ cost = ULLONG_MAX / SRV_EWGHT_MAX;
+ return cost;
+}
+
/* random value */
struct server *get_server_rnd(struct stream *s, const struct server *avoid)
{
@@ -600,11 +618,20 @@ struct server *get_server_rnd(struct stream *s, const struct server *avoid)
}
/* compare the new server to the previous best choice and pick
- * the one with the least currently served requests.
+ * the one with the least currently served requests, or with
+ * the lowest peak EWMA cost.
*/
if (prev && prev != curr) {
- uint64_t wcurr = (uint64_t)curr->served * prev->cur_eweight;
- uint64_t wprev = (uint64_t)prev->served * curr->cur_eweight;
+ uint64_t wcurr, wprev;
+
+ if (px->lbprm.pewma_tau != 0) {
+ wcurr = pewma_cost(px, curr) * prev->cur_eweight;
+ wprev = pewma_cost(px, prev) * curr->cur_eweight;
+ }
+ else {
+ wcurr = (uint64_t)curr->served * prev->cur_eweight;
+ wprev = (uint64_t)prev->served * curr->cur_eweight;
+ }
if (wcurr > wprev)
curr = prev;
@@ -3163,6 +3190,11 @@ const char *backend_lb_algo_str(int algo) {
*/
int backend_parse_balance(const char **args, char **err, struct proxy *curproxy)
{
+ /* the peak EWMA is only enabled by "random ... peak-ewma", reset it
+ * so that another algorithm does not inherit it from the defaults.
+ */
+ curproxy->lbprm.pewma_tau = 0;
+
if (!*(args[0])) {
/* if no option is set, use random by default */
curproxy->lbprm.algo &= ~BE_LB_ALGO;
@@ -3211,6 +3243,69 @@ int backend_parse_balance(const char **args, char **err, struct proxy *curproxy)
return -1;
}
}
+
+ if (*args[1] && strcmp(args[1], "peak-ewma") != 0) {
+ memprintf(err, "%s only accepts the 'peak-ewma' option (got '%s').", args[0], args[1]);
+ return -1;
+ }
+
+ if (*args[1]) {
+ int arg = 2;
+
+ curproxy->lbprm.pewma_tau = 10000000; // 10s
+ curproxy->lbprm.pewma_rtt = 10000; // 10ms
+
+ while (*args[arg]) {
+ unsigned int val;
+ const char *res;
+
+ if (strcmp(args[arg], "tau") != 0 &&
+ strcmp(args[arg], "default-rtt") != 0) {
+ memprintf(err, "%s peak-ewma only accepts the 'tau' and 'default-rtt' parameters (got '%s').",
+ args[0], args[arg]);
+ return -1;
+ }
+
+ if (!*args[arg+1]) {
+ memprintf(err, "%s peak-ewma : '%s' expects a time as argument.", args[0], args[arg]);
+ return -1;
+ }
+
+ res = parse_time_err(args[arg+1], &val, TIME_UNIT_MS);
+ if (res == PARSE_TIME_OVER) {
+ memprintf(err, "%s peak-ewma : timer overflow in argument <%s> to <%s>, maximum value is 4294967 ms (~71 minutes).",
+ args[0], args[arg+1], args[arg]);
+ return -1;
+ }
+ else if (res == PARSE_TIME_UNDER) {
+ memprintf(err, "%s peak-ewma : timer underflow in argument <%s> to <%s>, minimum non-null value is 1 ms.",
+ args[0], args[arg+1], args[arg]);
+ return -1;
+ }
+ else if (res) {
+ memprintf(err, "%s peak-ewma : unexpected character '%c' in argument to <%s>.",
+ args[0], *res, args[arg]);
+ return -1;
+ }
+
+ if (val > UINT_MAX / 1000) {
+ memprintf(err, "%s peak-ewma : timer overflow in argument <%s> to <%s>, maximum value is 4294967 ms (~71 minutes).",
+ args[0], args[arg+1], args[arg]);
+ return -1;
+ }
+
+ if (strcmp(args[arg], "tau") == 0) {
+ if (val == 0) {
+ memprintf(err, "%s peak-ewma : 'tau' must not be null.", args[0]);
+ return -1;
+ }
+ curproxy->lbprm.pewma_tau = val * 1000;
+ }
+ else
+ curproxy->lbprm.pewma_rtt = val * 1000;
+ arg += 2;
+ }
+ }
}
else if (strcmp(args[0], "source") == 0) {
curproxy->lbprm.algo &= ~BE_LB_ALGO;
diff --git a/src/proxy.c b/src/proxy.c
index 6898b6bd8..2b5ab03b3 100644
--- a/src/proxy.c
+++ b/src/proxy.c
@@ -3595,6 +3595,7 @@ static int proxy_defproxy_cpy(struct proxy *curproxy, const struct proxy *defpro
curproxy->lbprm.algo = defproxy->lbprm.algo;
curproxy->lbprm.hash_balance_factor = defproxy->lbprm.hash_balance_factor;
curproxy->lbprm.pewma_tau = defproxy->lbprm.pewma_tau;
+ curproxy->lbprm.pewma_rtt = defproxy->lbprm.pewma_rtt;
curproxy->fullconn = defproxy->fullconn;
curproxy->conn_retries = defproxy->conn_retries;
curproxy->redispatch_after = defproxy->redispatch_after;
--
2.56.0
From 623d8aa1da2d29057b88afe625879f00dc3e1136 Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:19:05 +0100
Subject: [RFC PATCH 2/6] MINOR: stream: feed the peak EWMA of the servers
When the backend's load balancing uses a peak EWMA (lbprm.pewma_tau not
zero), stream_update_time_stats() now adds a sample to the peak EWMA of
the server which handled the stream: the response time (Tr) in HTTP
mode, the connect time (Tc) otherwise.
A server which failed to connect or to respond (SF_ERR_SRVTO or
SF_ERR_SRVCL without a response) gets a penalty sample equal to the time
constant, otherwise a server failing fast would look like the fastest
one and attract all the traffic. The penalty decays like any other
sample, so the server is tried again after a few time constants. A
stream aborted by the client counts as nothing, since it says nothing
about the server.
The timers are truncated to milliseconds, so a timer of t ms gives a
sample of t ms + 500 us, the middle of the range it stands for.
Otherwise a server answering in less than one millisecond would get a
sample of 1 us, and a single answer taking 1 ms would make it look 1000
times slower and keep it away for about one time constant. This
resolution is fine for servers answering in several milliseconds; below
one millisecond the peak EWMA does not tell the servers apart and the
choice mostly depends on their number of streams.
The time constant is inherited from the defaults section like the other
load balancing parameters. Nothing sets lbprm.pewma_tau yet, this comes
with the configuration keyword.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
include/haproxy/backend-t.h | 1 +
src/proxy.c | 1 +
src/stream.c | 30 ++++++++++++++++++++++++++++--
3 files changed, 30 insertions(+), 2 deletions(-)
diff --git a/include/haproxy/backend-t.h b/include/haproxy/backend-t.h
index 53c3f8748..4387bb308 100644
--- a/include/haproxy/backend-t.h
+++ b/include/haproxy/backend-t.h
@@ -192,6 +192,7 @@ struct lbprm {
int wmult; /* ratio between user weight and effective weight */
int wdiv; /* ratio between effective weight and user weight */
int hash_balance_factor; /* load balancing factor * 100, 0 if disabled */
+ unsigned int pewma_tau; /* peak EWMA time constant in us, 0 if disabled */
unsigned int lb_free_list_nb; /* Number of elements in the free list */
struct sample_expr *expr; /* sample expression for "balance (log-)hash" */
char *arg_str; /* name of the URL parameter/header/cookie used for hashing */
diff --git a/src/proxy.c b/src/proxy.c
index 2601d8b29..6898b6bd8 100644
--- a/src/proxy.c
+++ b/src/proxy.c
@@ -3594,6 +3594,7 @@ static int proxy_defproxy_cpy(struct proxy *curproxy, const struct proxy *defpro
if (curproxy->cap & PR_CAP_BE) {
curproxy->lbprm.algo = defproxy->lbprm.algo;
curproxy->lbprm.hash_balance_factor = defproxy->lbprm.hash_balance_factor;
+ curproxy->lbprm.pewma_tau = defproxy->lbprm.pewma_tau;
curproxy->fullconn = defproxy->fullconn;
curproxy->conn_retries = defproxy->conn_retries;
curproxy->redispatch_after = defproxy->redispatch_after;
diff --git a/src/stream.c b/src/stream.c
index dfa731623..a6658526f 100644
--- a/src/stream.c
+++ b/src/stream.c
@@ -40,6 +40,7 @@
#include <haproxy/http_rules.h>
#include <haproxy/htx.h>
#include <haproxy/istbuf.h>
+#include <haproxy/lb_pewma.h>
#include <haproxy/log.h>
#include <haproxy/pipe.h>
#include <haproxy/pool.h>
@@ -2863,6 +2864,8 @@ void stream_update_time_stats(struct stream *s)
int t_close;
struct server *srv;
unsigned int samples_window;
+ unsigned int pewma_tau;
+ int err;
t_request = 0;
t_queue = s->logs.t_queue;
@@ -2873,8 +2876,21 @@ void stream_update_time_stats(struct stream *s)
if (s->be->mode != PR_MODE_HTTP)
t_data = t_connect;
- if (t_connect < 0 || t_data < 0)
+ srv = objt_server(s->target);
+ pewma_tau = s->be->lbprm.pewma_tau;
+
+ if (t_connect < 0 || t_data < 0) {
+ /* the peak EWMA of a server which failed to connect or to
+ * respond gets a penalty, so that a server failing fast does
+ * not attract the traffic. A client abort counts as nothing.
+ */
+ if (pewma_tau != 0 && srv) {
+ err = s->flags & SF_ERR_MASK;
+ if (err == SF_ERR_SRVTO || err == SF_ERR_SRVCL)
+ srv_pewma_update(srv, pewma_tau, pewma_tau);
+ }
return;
+ }
if ((llong)(s->logs.request_ts - s->logs.accept_ts) >= 0)
t_request = ns_to_ms(s->logs.request_ts - s->logs.accept_ts);
@@ -2883,8 +2899,18 @@ void stream_update_time_stats(struct stream *s)
t_connect -= t_queue;
t_queue -= t_request;
- srv = objt_server(s->target);
if (srv) {
+ /* response time (Tr) in HTTP, connect time (Tc) otherwise.
+ * The timers are truncated to milliseconds, so a value of t ms
+ * means between t and t+1 ms: the middle of this range is
+ * taken (+500 us). Otherwise a server answering in less than
+ * one millisecond would get a sample of 1 us and a single
+ * answer of 1 ms would make it look 1000 times slower.
+ */
+ if (pewma_tau != 0)
+ srv_pewma_update(srv, (s->be->mode == PR_MODE_HTTP ?
+ t_data : t_connect) * 1000U + 500, pewma_tau);
+
if (s->sv_tgcounters)
samples_window = (((s->be->mode == PR_MODE_HTTP) ?
HA_ATOMIC_LOAD(&s->sv_tgcounters->p.http.cum_req) : HA_ATOMIC_LOAD(&s->sv_tgcounters->cum_lbconn)) > TIME_STATS_SAMPLES) ? TIME_STATS_SAMPLES : 0;
--
2.56.0
From ab3af4e1fcb0af0808e1401ed0e0b3b8e2024a4f Mon Sep 17 00:00:00 2001
From: Aleksandar Lazic <[email protected]>
Date: Fri, 30 Oct 2026 22:04:38 +0100
Subject: [RFC PATCH 1/6] MINOR: server: add a peak EWMA of the response time
The peak EWMA load balancing variant needs, per server, an estimate of
the response time that reacts at once to a slow server and recovers
progressively when it becomes fast again. This adds the state and the
functions to maintain it, without any user yet.
The peak EWMA is an exponentially weighted moving average whose weights
depend on the time elapsed between the samples, not on their number,
and which jumps to any sample above it. It only decays when it is read,
towards zero with a time constant, so that a server that was avoided
because it was slow is tried again after a while. This follows the
peak EWMA of Finagle, also used by Linkerd.
No floating point is used. A sample taken dt after the previous one
weighs dt / (dt + tau) instead of 1 - exp(-dt / tau), which has the same
limits for small and large dt. The decay v * exp(-dt / tau) needs a
closer approximation, since its tail decides when an avoided server is
tried again (v * tau / (tau + dt) would keep a penalized server away for
hours): the value is halved for each half-life tau * ln(2) elapsed and
linearly interpolated within the last one, which stays within 6% of the
exponential. The date is kept in nanoseconds, since with milliseconds
most samples of a busy server would see dt = 0 and never move the
average down.
The state is kept per thread group in struct srv_per_tgroup, next to the
other load balancing fields, so that the threads of a group only contend
on their own cache line. Each group thus has its own view of the server,
like separate load balancers. The functions take the server and use the
entry of the current thread group.
The value is updated with a CAS loop and its date stored after it; a
reader may briefly see the new value with the previous date, which is
fine for an estimate.
Co-Authored-By: Claude Opus 5.5 <[email protected]>
Signed-off-by: Aleksandar Lazic <[email protected]>
---
include/haproxy/lb_pewma.h | 139 +++++++++++++++++++++++++++++++++++++
include/haproxy/server-t.h | 2 +
2 files changed, 141 insertions(+)
create mode 100644 include/haproxy/lb_pewma.h
diff --git a/include/haproxy/lb_pewma.h b/include/haproxy/lb_pewma.h
new file mode 100644
index 000000000..b4d70a563
--- /dev/null
+++ b/include/haproxy/lb_pewma.h
@@ -0,0 +1,139 @@
+/*
+ * include/haproxy/lb_pewma.h
+ * Peak EWMA of the response time of the servers, for load balancing.
+ *
+ * Copyright (C) 2026 Aleksandar Lazic <[email protected]>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef _HAPROXY_LB_PEWMA_H
+#define _HAPROXY_LB_PEWMA_H
+
+#include <haproxy/api.h>
+#include <haproxy/clock.h>
+#include <haproxy/server-t.h>
+#include <haproxy/thread.h>
+
+/* The peak EWMA of a server is an exponentially weighted moving average of
+ * its response time whose weights depend on the time elapsed between the
+ * samples, not on their number, and which jumps to any sample above it (the
+ * "peak"). Without new samples it decays towards zero with the time constant
+ * <tau>, so that a server avoided because it was slow is tried again.
+ *
+ * The exponentials are approximated without floating point. A sample taken
+ * <dt> after the previous one weighs dt / (dt + tau) instead of
+ * 1 - exp(-dt / tau), which has the same limits for small and large <dt>.
+ * The decay v * exp(-dt / tau) needs a closer approximation, as its tail
+ * decides when an avoided server is tried again: the value is halved for
+ * each half-life tau * ln(2) elapsed, and linearly interpolated within the
+ * last one, which stays within 6% of the exponential.
+ *
+ * Each thread group keeps its own estimate in the server's per_tgrp entry,
+ * so that the threads of a group only contend on their own cache line; the
+ * functions below use the one of the current thread group. The value and its
+ * date are two fields: the value is updated with a CAS, the date is stored
+ * after it. A reader may see the new value with the previous date for a
+ * short time; this is fine for an estimate.
+ */
+
+/* Returns the microseconds elapsed since the last update of the peak EWMA
+ * <tg>, at most UINT_MAX. The date may come from another thread slightly
+ * ahead of the current one, in which case 0 is returned.
+ */
+static inline uint pewma_age(const struct srv_per_tgroup *tg)
+{
+ ullong last = HA_ATOMIC_LOAD(&tg->pewma_ns);
+ ullong age;
+
+ if (now_ns <= last)
+ return 0;
+ age = (now_ns - last) / 1000;
+ if (age > UINT_MAX)
+ return UINT_MAX;
+ return age;
+}
+
+/* Returns <val> decayed by <age> microseconds with the time constant <tau>
+ * (in microseconds), at least 1 so that it never reads as "no sample".
+ */
+static inline uint pewma_decay(uint val, uint age, uint tau)
+{
+ uint half;
+ uint n;
+
+ /* the half-life is tau * ln(2). There is no floating point here, so
+ * ln(2) = 0.6931... is written as the fraction 693 / 1000, which is
+ * precise enough for an estimate (0.02% off).
+ */
+ half = (ullong)tau * 693 / 1000;
+ if (half == 0)
+ return 1;
+ n = age / half;
+ if (n >= 32)
+ return 1;
+ val >>= n;
+ val -= (ullong)val * (age % half) / (2 * (ullong)half);
+ if (val == 0)
+ return 1;
+ return val;
+}
+
+/* Returns the peak EWMA of <srv> in microseconds, decayed with the time
+ * constant <tau> (in microseconds), or 0 if the server has no sample yet.
+ */
+static inline uint srv_pewma_get(const struct server *srv, uint tau)
+{
+ const struct srv_per_tgroup *tg = &srv->per_tgrp[tgid - 1];
+ uint val = HA_ATOMIC_LOAD(&tg->pewma);
+
+ if (val == 0)
+ return 0;
+ return pewma_decay(val, pewma_age(tg), tau);
+}
+
+/* Adds the response time <sample> (in microseconds) to the peak EWMA of
+ * <srv>, with the time constant <tau> (in microseconds). A sample above the
+ * average replaces it, a lower one moves it by dt / (dt + tau). The decay is
+ * only applied when reading, as the time between two samples already weighs
+ * the new one. This function is thread-safe.
+ */
+static inline void srv_pewma_update(struct server *srv, uint sample, uint tau)
+{
+ struct srv_per_tgroup *tg = &srv->per_tgrp[tgid - 1];
+ uint age = pewma_age(tg);
+ uint old, new;
+
+ if (sample == 0)
+ sample = 1;
+
+ old = HA_ATOMIC_LOAD(&tg->pewma);
+ do {
+ new = sample;
+ if (sample < old)
+ new = old - (ullong)(old - sample) * age / ((ullong)age + tau);
+ } while (!HA_ATOMIC_CAS(&tg->pewma, &old, new) && __ha_cpu_relax());
+
+ HA_ATOMIC_STORE(&tg->pewma_ns, now_ns);
+}
+
+#endif /* _HAPROXY_LB_PEWMA_H */
+
+/*
+ * Local variables:
+ * c-indent-level: 8
+ * c-basic-offset: 8
+ * End:
+ */
diff --git a/include/haproxy/server-t.h b/include/haproxy/server-t.h
index 40bfa910e..8d335af4d 100644
--- a/include/haproxy/server-t.h
+++ b/include/haproxy/server-t.h
@@ -305,6 +305,8 @@ struct srv_per_tgroup {
struct eb_root *lb_tree; /* For LB algos with split between thread groups, the tree to be used, for each group */
unsigned npos, lpos; /* next and last positions in the LB tree, protected by LB lock */
unsigned rweight; /* remainder of weight in the current LB tree */
+ unsigned int pewma; /* peak EWMA of the response time in us, 0 = no sample yet */
+ ullong pewma_ns; /* date of the last update of pewma (now_ns) */
} THREAD_ALIGNED();
/* Configure the protocol selection for websocket */
--
2.56.0
