hash-ring-points

How evenly do nginx, HAProxy and Envoy spread keys with consistent hashing, and how much of it comes down to the number of ring points each server gets?

Cloudflare got back 100 TB of RAM partly by cutting 90% of the points on its rings, because 100,000 points per server was far more than the spread needed. This repo measures the other end of the same curve: the defaults that give each server too few points.

Companion to the DevOps Daily article Cloudflare freed 100 TB of RAM from its hash rings. Your proxy may have the opposite problem.

Run it

You need Node 20.18.1 or newer, and nginx and haproxy on your PATH (the recorded runs used nginx 1.22.1 and HAProxy 2.6.12 from Debian 12, arm64).

npm install
node scripts/simulate.mjs                           # ideal rings, exact shares
node scripts/measure.mjs --variant nginx            # 1,000,000 keys through nginx
node scripts/measure.mjs --variant haproxy-default
node scripts/measure.mjs --variant nginx --down 9042 --keys 200000
node scripts/remap.mjs --down 9042
node scripts/predict.mjs                            # ports vs measured runs, key by key
node scripts/report.mjs

Each measure.mjs run starts 100 backends (one nginx listening on ports 9001-9100, each answering with its own port), starts the proxy under test, sends the keys, and writes data/<variant>.json plus the backend for every key in data/mappings/ (not committed). A run fails if any request fails or comes from a backend that should not answer, if a key lands on a different backend when it is sent again, or if nginx logs an upstream error (see below).

Variants: nginx, haproxy-default, haproxy-weight-10, haproxy-weight-100, envoy-default, envoy-ring-16000, envoy-maglev, and nginx-keepalive-64 (the failure reproduction).

The scripts

• scripts/simulate.mjs builds ideal rings with k random points per server for 100 servers and computes each server's exact share, with no requests and no sampling. It checks Cloudflare's formula CV = sqrt((N-1)/(N*k+1)) (reporting the root mean square of the per-ring CVs), the same rings with HAProxy's nearest-point rule, and where a removed server's share goes.
• scripts/measure.mjs runs one proxy for real and records which backend served each key.
• scripts/remap.mjs compares a normal run with a run where one backend is marked down in the config.
• scripts/lib/rings.mjs ports each proxy's ring, point placement and key lookup, from the source listed in data/sources.txt.
• scripts/predict.mjs predicts the backend for every key with those ports and compares with each measured run.
• scripts/haproxy-ring.mjs computes each HAProxy server's share of the hash space under the nearest-point rule and under a next-point rule, on the same points.
• scripts/envoy-ring.mjs computes Envoy's ring sizes, spread, and where a removed host's keys go, from the port.
• scripts/test-xxh64.mjs checks the XXH64 port against reference values.
• scripts/reproduce-keepalive-failure.sh and scripts/analyze-keepalive-failure.mjs reproduce and analyse the thrown-away run (below).
• scripts/report.mjs prints the table below.

Results (100 backends, 1,000,000 keys)

Proxy and setting	Points per server	Busiest server	Quietest server	CV
nginx hash ... consistent	160	1.211x mean	0.835x	7.6%
HAProxy hash-type consistent, weight 1	16	1.417x	0.630x	16.0%
HAProxy, weight 10	160	1.128x	0.867x	5.7%
HAProxy, weight 100	1600	1.048x	0.956x	1.9%
Envoy RING_HASH defaults (computed)	11	2.025x	0.319x	30.5%
Envoy minimum_ring_size: 16000 (computed)	160	1.223x	0.805x	8.2%

The nginx and HAProxy ports agreed with the real proxies on all 4.8 million key lookups across the eight clean runs, four with 1,000,000 keys and four one-backend-down runs with 200,000 (data/predict.txt). The ports cover equal weights and at most one backend down; other cases throw instead of guessing.

Raw output: data/runs.txt, data/report.txt, data/predict.txt, data/simulate.txt, data/haproxy-ring.txt, data/envoy-ring.txt.

Envoy on a Raspberry Pi

The Envoy rows are computed from the port, not measured. The official arm64 Envoy build uses tcmalloc, which expects a 48-bit virtual address space, and this Raspberry Pi kernel has 39 bits, so Envoy aborts at startup (data/envoy-pi-startup.txt). On a machine where Envoy starts, measure.mjs --variant envoy-default measures it the same way as the others (set ENVOY_BIN or put the binary at bin/envoy), and predict.mjs then compares it with the port key by key.

The run we threw away

The first nginx run looked clean: 1,000,000 requests, 0 errors. The comparison with the one-backend-down run said otherwise: 291 keys that were never on the down backend had changed server (data/discarded-run/original-*.txt). Its nginx log had already been overwritten by a re-run, so scripts/reproduce-keepalive-failure.sh runs the same config again (nginx-keepalive-64) and keeps the evidence in data/discarded-run/ and data/nginx-keepalive-64-nginx-error.log (see data/discarded-run/window.txt for how the kernel log was bounded to the run).

With keepalive 64 per worker for 100 backends, and the default upstream keepalive_requests of 1,000, nginx kept closing and opening upstream connections, which filled the machine's conntrack table (65,536 entries, nf_conntrack: table full, dropping packet). With the table full, connects timed out (our reading: new connections were dropped), the nginx worker marked those backends unavailable for fail_timeout (10 s), and served their keys from the next point on the ring. The client still got a 200. In the reproduction, 6,172 of 1,000,000 keys went to a different backend than the ring says, 5,595 of them to the next live server on the ring.

The config now keeps upstream connections open (keepalive 512, keepalive_requests 1000000), and measure.mjs fails a run if nginx logs any upstream error. The recorded nginx runs are the re-runs, which match the port on every key.

License

MIT