spike: fair queueing for the run queue — caps vs scheduling (#2617)#4353
Conversation
The plan of record ships concurrency caps (per-task total, per-key limit) and leaves the fair-selection scoring untouched, the opposite lever from the earlier spike's SFQ recommendation. Adds the reconciliation design and the queueing-theory research grounding it (WFQ/SFQ wait bounds, concurrency-cap fairness limits, CoDel scope, real multi-tenant systems, Little's law).
Runs the plan's concurrency caps (per-key limit via the real per-queue gate, total cap via a driver group gate) head-to-head with SFQ/DRR through the real CK-dequeue Lua. Per-key caps fix a starved key's wait when one key floods (eligibility-aware dequeue) but fail when a tenant shards its backlog across many keys (the sybil split), and are not work-conserving; a total cap only lowers the ceiling and worsens cross-key wait; scheduling fixes every case including sybil and stays work-conserving. Adds a makespan work-conservation metric.
Blind two-model review (a third stalled). Folds in: consistent relative-ranking register instead of proven/disproven; reframes the total cap as a capacity- confounded cross-task knob, not a cross-key fairness failure; leads the sybil result with the mechanism (unbounded per-key sum) plus the real Lua's 3-wide scan window (ZRANGEBYSCORE ... LIMIT 0, maxCount*3), which governs why per-key caps work with one heavy key and give no wait improvement once a tenant shards (sybil bumped to 20 attacker keys, now flat vs baseline). Adds the shipped combined total+per-key config and a fully-layered total+per-key+sfq treatment. Marks the caps-first sequencing as interpretation, not measured. Corrects the makespan doc (last dequeue, arrival-confounded off ckHeavyIdle), defines worstWait, notes the contention-share seed spread, and comments the speculative order() coupling.
Measures the claim the caps bench left argued-not-measured: the per-task total cap's real purpose is cross-TASK isolation, not cross-key. Two keyless tasks share one env; capping the heavy task (its real per-queue concurrency gate, which for a keyless task equals its total cap) cuts the light task's wait 475 to 2 under the production FairQueueSelectionStrategy, versus failing at the cross-key grain. Still not work-conserving (makespan 2039 to 3039); SFQ protects the light task too and stays work-conserving. Adds a perQueueCap hook to the base-queue driver.
|
Important Review skippedAuto reviews are disabled on base/target branches other than the default branch. Please check the settings in the CodeRabbit UI or the ⚙️ Run configurationConfiguration used: Repository UI Review profile: CHILL Plan: Pro Plus Run ID: You can disable this status message by setting the Use the checkbox below for a quick retry:
✨ Finishing Touches🧪 Generate unit tests (beta)
Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out. Comment |
|
Throwaway spike (ships nothing, delete before merge). Reconciles the earlier fair-queueing spikes with the multi-tenant fairness plan of record, which ships concurrency caps and leaves the fair-selection scoring alone.
Measured on the real CK-dequeue Lua (3 seeds, blind two-model reviewed):
Reconciliation: caps and scheduling are orthogonal knobs (Parekh-Gallager needs both). Shipping the caps first is defensible; the general fix also orders ckIndex by virtual time; the end state layers them (Kubernetes APF). Findings in CAPS_FINDINGS.md, queueing-theory research in RESEARCH.md, under internal-packages/run-engine/src/run-queue/fairness-spike-ck/.
Stacked on the earlier fair-queueing spike branches.
This is part 3 of 3 in a stack made with GitButler: