triggerdotdev · 1stvamp · Jul 23, 2026 · Jul 23, 2026 · Jul 23, 2026 · Jul 23, 2026
diff --git a/docs/superpowers/plans/2026-07-23-fair-queueing-ck-spike.md b/docs/superpowers/plans/2026-07-23-fair-queueing-ck-spike.md
@@ -0,0 +1,69 @@
+# Per-concurrency-key fairness spike Implementation Plan
+
+> **For agentic workers:** REQUIRED SUB-SKILL: superpowers:subagent-driven-development or executing-plans. Steps use checkbox syntax.
+
+**Goal:** Rank baseline (age-order) vs SFQ/DRR/stride/CoDel on per-concurrency-key fairness by driving the real CK-dequeue Lua and controlling `ckIndex` scores.
+
+**Architecture:** Enqueue runs across many concurrency keys under one base queue via the real `RunQueue`. For candidates, rewrite the `ckIndex` ZSET scores before each dequeue round so the unmodified `dequeueMessagesFromCkQueueTracked` Lua serves keys in the discipline's order; baseline leaves scores untouched (production). Reuse the base-queue spike's workload and metrics.
+
+**Tech Stack:** TypeScript, vitest, `@internal/testcontainers`, `@internal/run-engine` (RunQueue, keyProducer), `@internal/redis`.
+
+## Global Constraints
+
+- All code under `internal-packages/run-engine/src/run-queue/fairness-spike-ck/`. Reuse `../fairness-spike/harness/{workload,metrics}.ts` and disciplines where they transfer. Throwaway; delete before merge.
+- Fairness group = concurrency key. One org/project/env, one base queue, many CKs.
+- No production Lua edits. The `ckIndex` rescore sweep is the only affordance; discipline state advances via an `onServiced(concurrencyKey)` hook.
+- Determinism: seeded workload; logical clock owned by the driver.
+- Verify: `cd internal-packages/run-engine && pnpm run test ./src/run-queue/fairness-spike-ck/<file> --run`.
+- Commit with `but` on `chore/fair-queueing-ck-spike` (stacked on `chore/fair-queueing-spike`).
+
+---
+
+### Task 1: ckReader — read ckIndex members + head scores
+
+**Files:** Create `fairness-spike-ck/ckReader.ts`; Test `fairness-spike-ck/tests/ckReader.test.ts`.
+
+**Produces:** `type ActiveCk = { ckQueue: string; concurrencyKey: string; headScore: number }`; `class CkReader { constructor(redis, keys); readActiveCks(baseQueue): Promise<ActiveCk[]> }`. Reads `ZRANGE ckIndexKey WITHSCORES` for the base queue; member is the prefixless CK-queue name; `concurrencyKey` from `descriptorFromQueue(keyPrefix+member)`.
+
+- [ ] Write `redisTest`: enqueue 2 runs with concurrencyKeys "ck1","ck2" under one base queue via real RunQueue; assert readActiveCks returns both with numeric headScores. First discover the exact ckIndex member format by dumping `ZRANGE ckIndexKey 0 -1` (grep enqueueMessageCkTracked Lua for the `ZADD ckIndexKey` member).
+- [ ] Implement; run; commit.
+
+### Task 2: ckRescorer — write discipline order into ckIndex
+
+**Files:** Create `fairness-spike-ck/ckRescorer.ts`; Test `tests/ckRescorer.test.ts`.
+
+**Produces:** `async function rescoreCkIndex(redis, keys, baseQueue, order: string[] /* ckQueues, highest priority first */, now: number)`. Assigns scores `now - (order.length - i)` so the highest-priority CK gets the smallest (oldest) score, all `<= now`, order-preserving. ZADD each member.
+
+- [ ] Write `redisTest`: enqueue CKs, rescore with a chosen order, assert `ZRANGEBYSCORE ckIndexKey -inf now` returns that order.
+- [ ] Implement; run; commit.
+
+### Task 3: CK disciplines
+
+**Files:** Create `fairness-spike-ck/disciplines.ts`; Test `tests/disciplines.test.ts`.
+
+**Produces:** a `CkDiscipline` interface `{ name; order(active: ActiveCk[]): string[] /* ckQueues, best first */; onServiced(concurrencyKey): void; reset() }` with `Sfq`, `Drr`, `Stride` keyed by concurrency key, plus `Codel` wrapper and `Baseline` (order = by headScore asc, i.e. no rescore needed). Reuse the monotonic-floor SFQ/stride and DRR logic from the base-queue spike (import or copy the core, keyed by concurrencyKey).
+
+- [ ] Unit tests mirroring the base-queue spike (under-served key first; 3:1 weight ratio if weights used; CoDel hoist/revert).
+- [ ] Implement; run; commit.
+
+### Task 4: ckDriver — enqueue, rescore, real dequeue, hold, ack
+
+**Files:** Create `fairness-spike-ck/harness/ckDriver.ts`; Test `tests/ckDriver.smoke.test.ts`; fidelity test `tests/fidelity.test.ts`.
+
+**Produces:** `runCkScenario(config): Promise<RunMetrics>` reusing `../fairness-spike/harness/metrics.ts`. Loop per instant: release holds (ack), enqueue arrivals (with concurrencyKey), for candidate: compute discipline order over active CKs and `rescoreCkIndex`; call `testDequeueFromMasterQueue`; record per-key events; `onServiced`; hold. Baseline skips the rescore.
+
+- [ ] Fidelity test: baseline path per-key dequeue counts equal a direct `testDequeueFromMasterQueue`-only run (no rescore) — confirms the harness matches production age-order.
+- [ ] Smoke: balanced CKs drain fully and no key starves under a fair discipline.
+- [ ] Implement; run; commit.
+
+### Task 5: scenarios + bench + FINDINGS
+
+**Files:** Create `fairness-spike-ck/harness/ckScenarios.ts`, `ckFairnessSpike.bench.test.ts`, `FINDINGS.md`.
+
+- [ ] Scenarios ckSkew / ckBalanced / ckTrickle, multi-seed (3), five selectors; write results JSON; print table.
+- [ ] Run the matrix; sanity-check baseline starves under ckSkew and at least one candidate fixes it (or record if not).
+- [ ] Write FINDINGS with proof/disproof per discipline at the CK grain and whether the base-queue ranking carried over. Commit.
+
+## Self-Review
+
+Covers the spec: ckReader (T1), rescorer (T2), disciplines incl. baseline (T3), driver + fidelity anchor (T4), scenarios/bench/findings (T5). Grain = concurrency key throughout. Reuses workload/metrics from the base-queue spike. The rescore affordance and onServiced seam are Global Constraints.
diff --git a/docs/superpowers/specs/2026-07-23-fair-queueing-ck-spike-design.md b/docs/superpowers/specs/2026-07-23-fair-queueing-ck-spike-design.md
@@ -0,0 +1,90 @@
+# Per-concurrency-key fairness spike: design
+
+## What this is
+
+The follow-on to the base-queue-grain fair-queueing spike. That spike found the
+#2617 gap lives below the `RunQueueSelectionStrategy` interface, in the
+CK-dequeue Lua: `dequeueMessagesFromCkQueueTracked` picks concurrency-key queues
+from `ckIndexKey` oldest-head-first, so a concurrency key with a big backlog
+starves other keys under the same base queue. This spike proves or disproves
+whether the same disciplines (SFQ, DRR, stride, CoDel) fix that at the real seam.
+
+Throwaway. Ships nothing. Delete before any merge to main.
+
+## Goal
+
+Rank five selectors on per-concurrency-key fairness under contention: the
+production baseline (age-order) plus SFQ, DRR, stride, and a CoDel wrapper.
+Relative ranking only, on the same axes the base-queue spike used: contention
+share (arrival-aware) and per-key wait, over multiple seeds.
+
+## Grain
+
+The fairness group is the concurrency key. One environment, one base queue, many
+concurrency keys. A "heavy" key has a large backlog; "light" keys have little.
+The question: does the heavy key starve the light keys, and does each discipline
+fix it?
+
+## Approach: rescore ckIndex, drive the real Lua
+
+The per-CK pick is `ZRANGEBYSCORE ckIndexKey -inf now` inside
+`dequeueMessagesFromCkQueueTracked` (`index.ts`), i.e. lowest score first, and
+the score is the CK-queue's head-message timestamp. So the discipline is
+expressed by controlling that score:
+
+- baseline: leave the scores as the Lua maintains them (head timestamp). This is
+  production behaviour, unmodified.
+- candidate: before each dequeue round, rewrite each active CK-queue's `ckIndex`
+  score to encode the discipline's priority (virtual clock / deficit / pass),
+  mapped into a `<= now` range preserving order so the Lua treats the
+  highest-priority key as the oldest and serves it first.
+
+Enqueue and acknowledge go through the real `RunQueue` (real `ckIndex`, per-CK
+queues, per-CK and env concurrency, atomic Lua). The only spike affordance is the
+rescore sweep before candidate dequeues, plus the `onServiced` hook that advances
+discipline state per served key. In production that advance would live inside the
+enqueue/dequeue Lua that maintains `ckIndex`.
+
+Fidelity anchor: a test asserts the baseline path (no rescore) produces the same
+per-key dequeue sequence as calling the real Lua directly, so the harness is a
+faithful stand-in for production age-ordering.
+
+## Components
+
+Reuse from the base-queue spike (`../fairness-spike/`): `harness/workload.ts`
+(tenant becomes concurrency-key generator), `harness/metrics.ts` (contention
+share + wait, unchanged), and the selector disciplines' core logic where it
+transfers. New, under `internal-packages/run-engine/src/run-queue/fairness-spike-ck/`:
+
+- `ckReader.ts`: reads `ckIndexKey` members and each key's head score for a base
+  queue.
+- `ckRescorer.ts`: given a discipline priority per concurrency key, rewrites the
+  `ckIndex` scores into a `<= now` order-preserving range.
+- `strategies/`: sfq/drr/stride/codel keyed by concurrency key (thin adapters
+  over the base-queue spike's disciplines, or shared directly).
+- `harness/ckDriver.ts`: enqueues runs across concurrency keys, loops
+  rescore -> real dequeue -> hold -> ack, records per-key events.
+- `ckFairnessSpike.bench.test.ts`: the selector-by-scenario matrix, multi-seed.
+- `FINDINGS.md`: the writeup.
+
+## Scenarios (seeded, multi-seed)
+
+- ckSkew: one heavy concurrency key (large backlog) vs many light keys, equal
+  weight. The direct #2617 reproduction.
+- ckBalanced: equal keys (sanity).
+- ckTrickle: a bulk key plus keys whose runs trickle in (poisson), to exercise
+  wait and the CoDel wrapper honestly.
+
+## Out of scope
+
+- Per-CK concurrency-limit multiplication (the other half of #2617) is a limit
+  problem, not a dequeue-ordering problem; not addressed here.
+- No changes to production Lua. The rescore sweep stands in for the production
+  ckIndex-scoring change.
+- Single shard, single environment, single base queue.
+
+## Deliverable
+
+The multi-seed ranking table plus `FINDINGS.md` with a proof/disproof verdict per
+discipline at the concurrency-key grain, and whether the base-queue spike's
+ranking carried over to the real seam.
diff --git a/internal-packages/run-engine/src/run-queue/fairness-spike-ck/FINDINGS.md b/internal-packages/run-engine/src/run-queue/fairness-spike-ck/FINDINGS.md
@@ -0,0 +1,122 @@
+# Per-concurrency-key fairness spike: findings
+
+Throwaway spike. Ships nothing; delete before any merge to main.
+
+Bottom line: the base-queue spike's direction carries over to the real seam. At
+the concurrency-key grain the production baseline (serve the oldest-head CK
+first) starves keys that arrive behind a big backlog, and virtual-time (SFQ) and
+stride fix it: they cut the starved key's wait from ~1300ms to ~20ms by making
+the backlog key wait its turn. DRR does the same. A CoDel wrapper on the baseline
+makes it worse. This was measured by driving the real
+`dequeueMessagesFromCkQueueTracked` Lua and only rewriting `ckIndex` scores to
+express each discipline. That is enough to say the ordering fix is worth a design
+spike, but NOT that a production implementation is proven (see the fidelity
+caveat: the spike serves one key per Lua call, and production dequeues in
+batches).
+
+## What was driven, and the two things to know before reading numbers
+
+Runs enqueue across many concurrency keys under one base queue via the real
+`RunQueue`. The per-CK pick is `ZRANGEBYSCORE ckIndexKey -inf now` in the CK Lua
+(lowest score first, score = head timestamp). Candidates rewrite those scores
+each round to encode discipline order; the baseline leaves them (production age
+order). Enqueue, dequeue, concurrency gating and ack all run through the real
+code.
+
+Two caveats a review forced, both load-bearing:
+
+1. Lead with wait, not contention share. The contention-share metric is
+   volume-confounded for low-volume keys (a key with 15 runs cannot take a third
+   of a long window even when served instantly), so on these scenarios it lands
+   around 0.7 to 0.9 for a discipline that has in fact eliminated the starvation.
+   The per-key wait is the clean signal.
+2. The scenarios must give keys genuinely different head ages. An earlier version
+   enqueued every run at one timestamp; with tied `ckIndex` scores the real Lua
+   falls back to a lexicographic member-name tie-break, so the "baseline starves
+   the heavy key's rivals" result was actually "Redis sorts by name" and the
+   heavy key only won because "heavy" sorts before "light". Fixed: the backlog
+   key fires at once (persistently old head) and the other keys arrive via
+   poisson (distinct, later heads), so the baseline now exercises real age order.
+
+## Results
+
+`contWorstS/W` mean over 3 seeds (min..max), and the worst-served key's mean wait
+(seed-a, logical ms). Read the wait column as the headline.
+
+| scenario   | discipline | contWorstS/W        | worst-key wait | backlog-key wait |
+| ---------- | ---------- | ------------------- | -------------- | ---------------- |
+| ckSkew     | baseline   | 0.187 (0.186..0.188)| 1321           | 872              |
+| ckSkew     | sfq        | 0.723 (0.655..0.769)| 16             | 1150             |
+| ckSkew     | drr        | 0.608 (0.556..0.648)| 21             | 1149             |
+| ckTrickle  | baseline   | 0.279 (0.254..0.291)| 1339           | 872              |
+| ckTrickle  | sfq        | 0.909 (0.891..0.918)| 24             | 1237             |
+| ckTrickle  | drr        | 0.790 (0.769..0.818)| 30             | 1236             |
+
+Full matrix (contWorstS/W mean over 3 seeds):
+
+| scenario   | baseline            | sfq                 | drr                 | stride | codel(sfq) | codel(baseline)     |
+| ---------- | ------------------- | ------------------- | ------------------- | ------ | ---------- | ------------------- |
+| ckSkew     | 0.187               | 0.723               | 0.608               | 0.723  | 0.723      | 0.104 (0.000..0.157)|
+| ckBalanced | 0.515 (0.444..0.600)| 0.611 (0.462..0.800)| 0.730 (0.615..0.909)| 0.611  | 0.611      | 0.464               |
+| ckTrickle  | 0.279               | 0.909               | 0.790               | 0.909  | 0.909      | 0.018 (0.000..0.055)|
+
+## Verdict per discipline (at the concurrency-key grain)
+
+- SFQ / stride: fix the starvation. Contention share improves (skew 0.187 to
+  0.723, trickle 0.279 to 0.909) and the starved key's wait collapses (skew 1321
+  to 16, trickle 1339 to 24) because the backlog key now waits its turn (its wait
+  rises 872 to ~1150 to 1237). Identical to each other on every scenario.
+  Recommended discipline for the fix.
+- DRR: fixes the wait just as well (skew 21, trickle 30) and its contention share
+  tracks SFQ within noise (sometimes a little lower, sometimes higher, e.g.
+  balanced 0.730 vs 0.611). Fine.
+- CoDel(sfq): no harm, matches SFQ to the decimal. Adds nothing on top of a fair
+  base.
+- CoDel(baseline): harmful. Hoisting stale keys on top of the age-order baseline
+  drove ckSkew to 0.104 (below baseline's 0.187) and ckTrickle to 0.018 (below
+  0.279). A staleness monitor is not a substitute for a fair base.
+- Baseline (production age order): starves keys that queue behind a backlog
+  (ckSkew 0.187, worst key waits 1321ms; ckTrickle 0.279, 1339ms). It is roughly
+  fair when keys are symmetric (ckBalanced 0.515, though seed-variant 0.444 to
+  0.600). This is the #2617 dynamic at the seam where it lives.
+
+## Fidelity caveat (the reason this is not "proven for production")
+
+The driver dequeues one key per Lua call (`maxCount = 1`) and rescores `ckIndex`
+before each call. Production dequeues in batches (`maxCount` default 10). Inside a
+batched CK-dequeue call the Lua re-scores each served key back to its head
+timestamp as it goes, so a once-per-round rescore would only steer the FIRST pick
+of a batch; the rest would follow head-timestamp order again. So this spike
+demonstrates the ordering fix only in a one-key-per-call regime, which is not how
+production dequeues. A real fix has to advance per-key discipline state inside the
+Lua on every serve (and hold that state in Redis, not process memory). This spike
+does not exercise that batch path, so the correct claim is "the ordering fix is
+worth a design spike", not "a production fix is viable".
+
+## Other caveats
+
+- Contention share is volume-confounded (see above); the wait column is the
+  trustworthy signal, and the contention numbers should be read as directional.
+- The DRR contention-share gap is NOT the base-queue spike's batch-drain artifact
+  (that harness batched; this one serves one key per call and advances DRR's
+  deficit every serve). The cause of DRR's slightly lower share here is not
+  established; its wait result is as good as SFQ's.
+- Per-CK concurrency gating never binds in these runs (no per-CK limit is set, so
+  it collapses to the env limit), so the spike says nothing about the per-CK
+  concurrency-limit-multiplication half of #2617, which is out of scope.
+- A rescore discipline advances its floor/ring state on the final no-op drain
+  round of an instant (order() is called before the empty dequeue). It is
+  self-correcting and does not corrupt the event-based metrics, but it is a minor
+  infidelity to a production per-serve advance.
+- Equal weights only; single shard, single base queue, single sequential
+  consumer; simulated holds on a logical clock; 3 seeds.
+
+## Recommended direction
+
+Score `ckIndex` by a fair discipline (SFQ/stride virtual time, or DRR) instead of
+by head timestamp. Both spikes agree on the discipline and this one shows the
+ordering fix works through the real dequeue path at `maxCount = 1`. The design
+spike past this needs to: advance per-key virtual-time state inside the batched
+CK-dequeue Lua (the `maxCount > 1` path this spike did not exercise), hold that
+state in Redis for the multi-consumer case, and address the per-CK
+concurrency-limit multiplication that is the other half of #2617.