docs: virtual-time fair scheduling plan for the run queue (#2617)#4356
docs: virtual-time fair scheduling plan for the run queue (#2617)#43561stvamp wants to merge 1 commit into
Conversation
Implementation and testing plan for the recommended run-queue multi-tenant fairness fix: score the concurrency-key dequeue by SFQ virtual time, layered under the concurrency caps. Keeps the three spike findings and the queueing-theory research as references; the throwaway spike harness/bench code is archived on the remote branch chore/fair-queueing-spike and is not carried onto main. The plan adds a parallel :ckVtime ZSET + floor (leaving ckIndex's timestamp domain intact and mixed-deploy-safe), a flag-selected two-pass dequeue command (vtime order then age-order fallback, so it never serves less than today), and a 19-test suite that exercises the real batched maxCount>1 path the spikes could not.
|
WalkthroughAdds reference documentation for queue fairness research and spike findings. Adds a detailed plan for feature-flagged virtual-time scheduling across concurrency-key variants, including Redis state, two-pass Lua dequeue behavior, registration and cleanup invariants, option wiring, fairness and correctness tests, rollout handling, and verification steps. 🚥 Pre-merge checks | ✅ 4 | ❌ 1❌ Failed checks (1 warning)
✅ Passed checks (4 passed)
✨ 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 |
There was a problem hiding this comment.
Actionable comments posted: 6
ℹ️ Review info
⚙️ Run configuration
Configuration used: Repository UI
Review profile: CHILL
Plan: Pro Plus
Run ID: 652606c6-d0ed-4180-8cf2-21ad00b211a7
📒 Files selected for processing (6)
docs/superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.mddocs/superpowers/references/README.mddocs/superpowers/references/run-queue-fairness-base-queue-findings.mddocs/superpowers/references/run-queue-fairness-caps-vs-scheduling-findings.mddocs/superpowers/references/run-queue-fairness-ck-findings.mddocs/superpowers/references/run-queue-fairness-research.md
📜 Review details
⚠️ CI failures not shown inline (2)
GitHub Actions: 📚 Docs Checks / check-broken-links: docs: virtual-time fair scheduling plan for the run queue (#2617)
Conclusion: failure
##[group]Run npx mintlify@4.0.393 broken-links
�[36;1mnpx mintlify@4.0.393 broken-links�[0m
shell: /usr/bin/bash -e {0}
##[endgroup]
Checking for broken links...
Error: Syntax error - Unable to parse superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.md - 639:4: Unexpected character `=` (U+003D) before name, expected a character that can start a name, such as a letter, `$`, or `_`
##[error]Process completed with exit code 1.
GitHub Actions: 📚 Docs Checks / 0_check-broken-links.txt: docs: virtual-time fair scheduling plan for the run queue (#2617)
Conclusion: failure
##[group]Run npx mintlify@4.0.393 broken-links
�[36;1mnpx mintlify@4.0.393 broken-links�[0m
shell: /usr/bin/bash -e {0}
##[endgroup]
Checking for broken links...
Error: Syntax error - Unable to parse superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.md - 639:4: Unexpected character `=` (U+003D) before name, expected a character that can start a name, such as a letter, `$`, or `_`
##[error]Process completed with exit code 1.
🧰 Additional context used
🪛 GitHub Actions: 📚 Docs Checks / 0_check-broken-links.txt
docs/superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.md
[error] 639-639: Mintlify broken-links check failed. Syntax error: Unable to parse markdown at line 639:4. Unexpected character '=' (U+003D) before name; expected a character that can start a name (e.g., a letter, '$', or '_').
🪛 GitHub Actions: 📚 Docs Checks / check-broken-links
docs/superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.md
[error] 639-639: mintlify broken-links failed: Syntax error - Unable to parse file. 639:4: Unexpected character '=' (U+003D) before name; expected a character that can start a name (e.g., a letter, '$', or '_').
🪛 LanguageTool
docs/superpowers/references/run-queue-fairness-research.md
[grammar] ~44-~44: Ensure spelling is correct
Context: ...cuts light tenant L's wait to near-zero iff BOTH: 1. Slot availability: sum of cap...
(QB_NEW_EN_ORTHOGRAPHY_ERROR_IDS_1)
[style] ~90-~90: The double modal “needs bounded” is nonstandard (only accepted in certain dialects). Consider “to be bounded”.
Context: ...n one tenant could use all K) and needs bounded, pre-known tenant cardinality. ## Prod...
(NEEDS_FIXED)
docs/superpowers/references/run-queue-fairness-ck-findings.md
[style] ~9-~9: Consider using a shorter alternative to avoid wordiness.
Context: ...e same. A CoDel wrapper on the baseline makes it worse. This was measured by driving the real ...
(MADE_IT_JJR)
[grammar] ~85-~85: Ensure spelling is correct
Context: ...e key per Lua call (maxCount = 1) and rescores ckIndex before each call. Production ...
(QB_NEW_EN_ORTHOGRAPHY_ERROR_IDS_1)
docs/superpowers/plans/2026-07-23-ck-virtual-time-scheduling-plan.md
[style] ~28-~28: ‘exact same’ might be wordy. Consider a shorter alternative.
Context: ...lag off is byte-identical to today: the exact same Lua scripts run and no new Redis keys a...
(EN_WORDINESS_PREMIUM_EXACT_SAME)
[style] ~92-~92: Consider an alternative for the overused word “exactly”.
Context: ...ker variants have older heads (which is exactly where today's age-ordered *3 window f...
(EXACTLY_PRECISELY)
[locale-violation] ~356-~356: In American English, ‘afterward’ is the preferred variant. ‘Afterwards’ is more commonly used in British English and other dialects.
Context: ...erved in that first call and its tag afterwards is floor + quantum, not 1. 5. "no s...
(AFTERWARDS_US)
[grammar] ~699-~699: Use a hyphen to join words.
Context: ...same SHA) holds by construction: the off path calls the same command names wh...
(QB_NEW_EN_HYPHEN)
🔇 Additional comments (4)
docs/superpowers/references/README.md (1)
1-44: LGTM!docs/superpowers/references/run-queue-fairness-research.md (1)
1-134: LGTM!docs/superpowers/references/run-queue-fairness-base-queue-findings.md (1)
1-169: LGTM!docs/superpowers/references/run-queue-fairness-ck-findings.md (1)
1-123: LGTM!
| ckVirtualTimeScheduling?: { | ||
| enabled: boolean; | ||
| /** Virtual-time advance per serve (dimensionless). Default 1. */ | ||
| quantum?: number; | ||
| /** Pass-1 candidate window = actualMaxCount * this. Default 3. */ | ||
| scanWindowMultiplier?: number; | ||
| /** EXPIRE applied to ckVtime/ckVtimeFloor on every write. Default 86400. */ | ||
| stateTtlSeconds?: number; |
There was a problem hiding this comment.
🎯 Functional Correctness | 🟠 Major | ⚡ Quick win
Validate vtime configuration before passing it to Lua.
Reject non-positive quantum, stateTtlSeconds, and scanWindowMultiplier values (and require an integer multiplier). For example, a zero multiplier makes both candidate windows empty, contradicting the work-conservation guarantee. Apply the validation in the option resolution and environment schema.
Also applies to: 718-721
| -- Register this variant in the virtual-time index at the floor. NX means an | ||
| -- already-advanced tag is never rewound. | ||
| local vfloor = redis.call('GET', ckVtimeFloorKey) or '0' | ||
| redis.call('ZADD', ckVtimeKey, 'NX', vfloor, queueName) | ||
| redis.call('EXPIRE', ckVtimeKey, stateTtl) | ||
| ``` |
There was a problem hiding this comment.
🗄️ Data Integrity & Integration | 🟠 Major | ⚡ Quick win
Refresh and repair the floor before registering a variant.
This block refreshes ckVtime but not ckVtimeFloor. If the floor expires while tags remain, GET falls back to 0, so a new variant can be registered behind existing tags, violating the monotonic-floor guarantee. Recompute the floor from the stored minimum tag and refresh both keys atomically; apply the same logic to the nack variant.
| <= 0.7 x flag OFF (spike: 1765 -> 1009), AND light key's first serve | ||
| happens within the first 3 steps (reachability at the floor), AND | ||
| contention-window share: over the steps where >= 2 keys have queued | ||
| backlog, light's served fraction >= 0.5 x its fair share 1/21 (directional, | ||
| per the spike's confounding caveat; wait is the headline). | ||
| - ckBalanced (no-harm check): 4 symmetric keys x 25. Assert: max per-key | ||
| mean wait with flag ON <= 1.25 x flag OFF (fair order must not make the |
There was a problem hiding this comment.
🎯 Functional Correctness | 🟠 Major | ⚡ Quick win
Escape the comparison operators in the Markdown assertions.
The Mintlify parser treats the leading <= tokens as markup; this is the reported docs-check failure at Line 639 and the same pattern appears at Line 645. Write them as <= or wrap the expressions in inline code.
🧰 Tools
🪛 GitHub Actions: 📚 Docs Checks / 0_check-broken-links.txt
[error] 639-639: Mintlify broken-links check failed. Syntax error: Unable to parse markdown at line 639:4. Unexpected character '=' (U+003D) before name; expected a character that can start a name (e.g., a letter, '$', or '_').
🪛 GitHub Actions: 📚 Docs Checks / check-broken-links
[error] 639-639: mintlify broken-links failed: Syntax error - Unable to parse file. 639:4: Unexpected character '=' (U+003D) before name; expected a character that can start a name (e.g., a letter, '$', or '_').
Source: Pipeline failures
| 15. "two consumers, one base queue, no corruption": one `RunQueue` for | ||
| enqueues, two more instances (same Redis, same key prefix, flag on) each | ||
| running a dequeue loop with `maxCount: 5` concurrently | ||
| (`Promise.all` of two loops, acking with a short hold). 6 keys x 30 | ||
| messages. Assert: every message served exactly once across both | ||
| consumers (union of served IDs has no duplicates and equals the enqueued | ||
| set); after drain, `ckVtime` is empty and floor equals the max it ever | ||
| reached; sample the floor between iterations and assert it never | ||
| decreased. The correctness argument is that every mutation happens | ||
| inside one Lua script and Redis serialises scripts; this test is the | ||
| check that the scripts do not assume cross-call state. |
There was a problem hiding this comment.
🎯 Functional Correctness | 🟠 Major | ⚡ Quick win
Relax the final floor assertion after GC.
The script persists floor before serving the batch, then can advance tags and remove all entries. Therefore the final floor need not equal the maximum tag ever observed; requiring that at Line 668 can fail by design. Assert monotonicity and emptiness, or explicitly change the Lua to advance/persist the floor after every serve.
| 17. "op-count budget": using a second plain Redis client, `CONFIG RESETSTAT`, | ||
| run 50 identical dequeue calls flag OFF, snapshot | ||
| `INFO commandstats` total calls; repeat flag ON with identical data. | ||
| Assert `on_total <= off_total + 50 * (6 + 2 * maxCount)` (per call the | ||
| vtime path adds at worst: GET floor, ZRANGE min, ZRANGE window, SET | ||
| floor, EXPIRE, the pass-2 ZRANGEBYSCORE, plus per serve one ZSCORE and | ||
| one ZADD). This pins the per-dequeue overhead the way the caps plan pins | ||
| the fairQueue snapshot cost. |
There was a problem hiding this comment.
🎯 Functional Correctness | 🟡 Minor | ⚡ Quick win
Include vtime GC operations in the command budget.
The planned dequeue adds ZREM ckVtimeKey when a variant becomes empty, but the budget only allows two new commands per serve. Final-message serves therefore exceed the stated bound. Add allowance for vtime removals (and any other per-candidate vtime commands) or make the test data avoid GC.
| Bottom line: the plan-of-record's concurrency CAPS and the earlier spike's fair | ||
| SCHEDULING are different knobs, and the data on the real CK-dequeue Lua lines up | ||
| with the queueing theory (see `RESEARCH.md`). A per-key cap cuts a starved key's |
There was a problem hiding this comment.
📐 Maintainability & Code Quality | 🟡 Minor | ⚡ Quick win
Use the actual research filename.
RESEARCH.md does not match the added reference run-queue-fairness-research.md; update this citation so readers can locate the supporting document.
Implementation and testing plan for the recommended multi-tenant fairness fix in the RunQueue: score the per-base-queue concurrency-key dequeue by SFQ virtual time instead of head timestamp, inside the real batched CK-dequeue Lua, layered under the per-key and total concurrency caps. Caps bound occupancy; the fair order bounds wait under contention (the Kubernetes-APF shape).
Contents (docs only, no engine code yet):
Provenance: three throwaway spikes drove the real dequeue Lua on testcontainers Redis. The spike harness/bench code is archived on the branch chore/fair-queueing-spike (never merged); only the findings, research, and plan are carried here.
Draft: opening for design review of the approach before implementation.