proxy: snapshot in-flight counts before sorting (least_conn selection O(n)) #124
No Assignees
Notifications
Due Date
No due date set.
Dependencies
No dependencies set.
Reference: unkin/artifactapi#124
Reference in New Issue
Block a user
Delete Branch "benvin/leastconn-snapshot-opt"
Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?
Why
least_connmirror selection (baseURLAttemptOrder) scaled super-linearly. After rotating the pool by the round-robin cursor itsort.SliceStabled with a comparator that calledinflightCounteron every comparison — and each call did aremoteName+"\x00"+urlconcat plus async.MapLoadOrStorewith a speculativenew(atomic.Int64). So each selection cost O(n·log n) map lookups + allocations, all on the cache-miss/upstream path.How
Snapshot each mirror's in-flight count once, then sort the snapshot — O(n) map loads, zero comparator allocations.
inflightCount(name, url) int64: plainsync.MapLoad, returns 0 when the gauge is absent (noLoadOrStore, no speculative allocation).least_connbranch builds a{url, count}snapshot via oneinflightCountper rotated URL,sort.SliceStablebycountascending, then extracts the URLs.beginAttempt/endAttemptkeep the create-on-writeinflightCounterpath — they legitimately need to create the gauge.Numbers (
BenchmarkBaseURLAttemptOrder_LeastConn, Ryzen 7 4700U, best of 3)Allocs are now constant regardless of pool size; pool-8 is ~4.8x faster with ~16x fewer allocations.
Behavior
Unchanged: least-loaded first, RR rotation as the stable tie-break,
round_robinand single-URL paths untouched. Pure internal optimization — no API/schema/DB change. Added a multi-mirror tie-break test asserting all-equal load yields the RR rotation;make test(-race) green, vet/fmt clean.least_conn mirror selection stable-sorted the RR-rotated pool with a comparator that called inflightCounter on every comparison. Each call did a remoteName+"\x00"+url concat plus a sync.Map LoadOrStore with a speculative new(atomic.Int64), so selection cost O(n log n) map lookups and allocations per request on the cache-miss path. Snapshot each mirror's in-flight count exactly once, then sort the snapshot by plain int, making selection O(n) map loads with zero comparator allocations: - Add read-only inflightCount(name, url) int64: plain sync.Map Load, returns 0 when the counter is absent (no LoadOrStore, no speculative allocation). - least_conn branch builds a {url, count} snapshot via one inflightCount per rotated URL, sort.SliceStable by count ascending, then extracts the URLs. - beginAttempt/endAttempt keep the create-on-write inflightCounter path; they legitimately need to create the gauge. Behavior is unchanged: least-loaded first, RR rotation as the stable tie-break, round_robin and single-URL paths untouched. Added a multi-mirror tie-break test asserting all-equal load yields the RR rotation.