Index Kubernetes exact-host routes so lookup no longer scans every host's regexp
perfloop-oss/skipper · Inefficient Algorithm
https://perfloop.ai/t/oss/case_wx05m9nbmj
Verdict
VERIFIED · settled 2026-11-11 · pull request opened as zalando/skipper#4401
What happened: The paired measurements met the required improvement.
Hypothesis
HTTP route lookup tests host regular expressions one candidate at a time after selecting a path. Kubernetes hosts sharing the same root path can therefore leave a large candidate list for each request. The submitter reports substantial proxy CPU cost and savings from an exact-host index, but those measurements and their production representativeness are unconfirmed here.
At accepted revision 2237f1e885a2efab21a524f8d96e8c87d58bbf69, `matchLeaves` in routing/matcher.go:468-476 returns the first candidate accepted by `matchLeaf`. Host checking calls `matchRegexps(l.hostRxs, req.Host)` at routing/matcher.go:448-450, whose loop executes the compiled regexps at 388-396. Compilation already occurs during construction at 100-118 and 216-250; the proposed removable work is repeated regexp execution, not repeated compilation. The accepted reverse-proxy HTTP request operation already reaches this exact `matchLeaves` definition through `RouteLookup.Do`, `matcher.match`, path-tree lookup and `leafRequestMatcher.Match` (routing/routing.go:477-479; routing/matcher.go:481-505, 361-385, 23-31). This seed concerns that definition, not the Kubernetes generator.
Kubernetes `createHostRx` emits the literal-host alternatives with optional trailing dot and numeric port (dataclients/kubernetes/hosts.go:11-25), including `^(h[.]example[.]org[.]?(:[0-9]+)?)$`. Ingress Prefix paths become `PathSubtree` (dataclients/kubernetes/ingressv1.go:43-62), and ingress routes retain the generated HostRegexps (93-96, 141-171). RouteGroups use the same generator for external and internal hosts (dataclients/kubernetes/routegroup.go:559-588, 634-642). Root subtree routes are grouped into the same `/` and `/**` leaf lists (routing/matcher.go:277-300), then stably sorted by weight and conditions (49-68, 262-275, 351-357). The submitted mechanism is linear host-regexp work as the number of hosts in such a list grows, up to the first full match. The submitter cites 15k-20k routes per Zalando cluster. The pinned documentation actually says more than 20,000 production ingress routes and many clusters above 15k (docs/kubernetes/migrate.md:35-41, 74-81); neither statement measures distinct hosts sharing this path or the request distribution.
The submitter describes a local proxy benchmark as using Zalando's production settings: OTel `always_on` through the OpenTracing bridge, Prometheus host metrics, `powerOfRandomNChoices` with five endpoints, passive health checks, and default `fifo`, `disableAccessLog` and `stateBagToTag` filters. They report that at 3,000 hosts the host-regexp scan accounts for approximately 69% of proxy CPU. They report that a prototype reduces sec/op by 77% with a canned backend and 67% with real `httptest` backends at 3,000 hosts, and by approximately 11% at 300 hosts, with allocations unchanged. They also report approximately 11-19% more route-table construction allocations, paid once per update. These are attributed reports to reproduce during the Case, not measurements established by this run or minimum gain thresholds. Production host cardinality, traffic mix, match positions and update cadence remain unmeasured.
Required tests cover port and trailing-dot equivalence, mixed indexed/non-indexed priority order, `Weight()` order, and East-West hosts. Preserve all matching semantics and the public API, including fallback for every non-indexable host condition and the unchanged path when a list has no indexable host. Add a benchmark with thousands of Kubernetes hosts sharing `PathSubtree("/")`. The smallest useful first check is an executable differential comparing selected routes against the current scan for literal-host alternatives and mixed fallback priorities; a changed route falsifies semantics preservation. Then reproduce the reported full-proxy configurations at 300 and 3,000 hosts with both backend types, recording sec/op, CPU attribution, request allocations and construction allocations per update. The existing routing/host_test.go:15-89 benchmark is a useful local mechanism probe, but its 10,000 host-only shunt routes are not evidence for the claimed full-proxy workload or the requested shared-subtree benchmark.
Current upstream draft https://github.com/zalando/skipper/pull/4282 overlaps in purpose. Its reviewed base is aeb015f841cbd1c9142b3af7355c982975142318 and head is 89e62c712c8713090276e878b963188304500b7b. It adds an opt-in `UseHostTree` host/path index using `HostAny` predicates that expose `MatchHosts`, and tries the host tree before the original path tree. The useful remaining difference is this submission's recognition of existing Kubernetes `Host` regexps and ordered merging within each leaf list while retaining the original full match. Draft https://github.com/zalando/skipper/pull/3296 at head 41449525673371da86692b7230f75cea0b852fda and its linked https://github.com/zalando/skipper/issues/3297 concern wildcard-host conversion and weighting, not the exact-literal index. Their discussions flag wildcard ordering and operational concerns; those do not establish an exclusion of this literal-only outcome. Both PRs are open drafts, not accepted replacement or migration decisions. The comparison uses current metadata, bodies, selected implementation patches and the linked issue discussion; it does not establish repository-wide absence of other work or maintainer approval.
Change to test: Preserve matching semantics and the public API while avoiding unrelated-host scans: when building leaf lists, map hosts to original leaf positions for leaves whose sole host condition is exactly the Kubernetes `^(lit[.]?(:[0-9]+)?|...)$` regexp form, with `lit` limited to `[A-Za-z0-9.-]` and dots encoded as `[.]`, and retain every other leaf in an ordered fallback list. At lookup, strip a numeric port and one trailing dot from the request host to derive the key, merge indexed and fallback candidates in original priority order, and run the existing full `matchLeaf` on each so the original regexp still decides; leaf lists with no indexable host retain the current path.
Where it lives
perfloop-oss/skipper · proxy/proxy.go
Evidence
Kubernetes sample route lookup · 20 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
571.5 |
503.1 |
−12% (−68.45) |
−100.7 to −32.2 |
gain > 0; gain > 0.05 × |baseline median|; arm medians separated |
PASSED |
B/op |
384 |
384 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
3 |
3 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kubernetes-host proxy requests (300/canned) · 20 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
55892 |
46151 |
−17.8% (−9964) |
−13055 to −5016 |
gain > 0; gain > 0.05 × |baseline median|; arm medians separated |
PASSED |
B/op |
31622 |
31622 |
0 |
−1 to +2 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
276 |
276 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kubernetes-host proxy requests (300/http) · 31 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
343733 |
304379 |
−12.4% (−42647) |
−55752 to −18969 |
gain > 0; gain > 0.05 × |baseline median|; arm medians separated |
PASSED |
B/op |
38924 |
38922 |
−2 |
−10 to +5 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
376 |
376 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kubernetes-host proxy requests (3000/canned) · 20 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
296764 |
54353 |
−81.8% (−242828) |
−262798 to −216872 |
gain > 0; gain > 0.05 × |baseline median|; arm medians separated |
PASSED |
B/op |
31617 |
31617 |
0 |
−1 to +1 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
276 |
276 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Kubernetes-host proxy requests (3000/http) · 20 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
673828 |
316047 |
−52.9% (−356627) |
−377577 to −311172 |
gain > 0; gain > 0.05 × |baseline median|; arm medians separated |
PASSED |
B/op |
38897 |
38894 |
−2 |
−6 to +5 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
376 |
376 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
First of four literal-host routes (root) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
194.4 |
219.7 |
+13.3% (+25.8) |
+8.8 to +41.5 |
loss ≤ stated 0.5 × |baseline median| |
PASSED |
B/op |
48 |
48 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
1 |
1 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
First of four literal-host routes (exact) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
242.3 |
268.2 |
+30.5 |
0 to +50.7 |
loss ≤ stated 0.6 × |baseline median| |
PASSED |
B/op |
96 |
96 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
2 |
2 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
First of four literal-host routes (subtree) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
460.3 |
499 |
+7.8% (+36.1) |
+14.2 to +92.6 |
loss ≤ stated 0.4 × |baseline median| |
PASSED |
B/op |
384 |
384 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
3 |
3 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Build 300 literal-host subtree routes · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
4761083 |
5075688 |
+339833 |
−272450 to +816827 |
loss ≤ stated 0.4 × |baseline median| |
PASSED |
B/op |
3355303 |
3471026 |
+3.4% (+115723) |
+115653 to +115760 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
39331 |
41163 |
+4.7% (+1832) |
+1832 to +1832 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Build 3000 literal-host subtree routes · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
37840579 |
40020079 |
+2737177 |
−331766 to +7540810 |
loss ≤ stated 0.4 × |baseline median| |
PASSED |
B/op |
33620486 |
34684073 |
+3.2% (+1063583) |
+1063171 to +1064050 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
399760 |
417824 |
+4.5% (+18064) |
+18063 to +18065 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Mixed host-list rejection (root) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
942 |
978.6 |
+36.7 |
−20 to +79 |
loss ≤ stated 0.5 × |baseline median| |
PASSED |
B/op |
48 |
48 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
1 |
1 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Mixed host-list rejection (exact) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
946 |
975.2 |
+35.2 |
−53.6 to +138.2 |
loss ≤ stated 0.35 × |baseline median| |
PASSED |
B/op |
48 |
48 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
1 |
1 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Mixed host-list rejection (subtree) · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
ns/op |
938.9 |
990.5 |
+54.4 |
−28.6 to +121.3 |
loss ≤ stated 0.5 × |baseline median| |
PASSED |
B/op |
48 |
48 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
allocs/op |
1 |
1 |
0 |
0 to 0 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Build and retain 3000 literal-host routes · 40 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
peak RSS KiB |
115122 |
115858 |
+768 |
−7360 to +5084 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Build one literal-host subtree route · 21 sample pairs
| metric | baseline | candidate | paired median change | confidence range | required | result |
|---|---|---|---|---|---|---|
B/op |
10928 |
10944 |
+0.1% (+16) |
+16 to +16 |
loss ≤ 0.05 × |baseline median| |
PASSED |
Checks: 6 of 6 passed. Verification: no defect found.
Timeline
2026-11-03· Case opened2026-11-03· PR opened2026-11-07· Case closed