The vtime dequeue is a copy of dequeueMessagesFromCkQueueTracked, and main
added a TTL re-registration to that command while this branch was open. A copy
cannot pick up a change to its original, so the rebase left the vtime path
behind: it drops an expired run from the queue sorted sets and defers to a TTL
consumer that has no entry for it, because the entry is removed on first
dequeue. The run is then orphaned.
Only reachable with the flag on, so nothing shipped, but it would have gone out
with the feature. Same four lines as the base command, verbatim; the expired
branch is now identical between the two again.
Copies drifting like this is a known cost of the vtime scripts being copies,
kept deliberately so the flag-off path stays byte-identical to production. The
drift is worth a test that pins each copy against its original, which would
have caught this the day main merged.
Comments only, no behaviour change: the non-comment bytes of index.ts are
identical before and after.
The 22 "NEW:" markers went. They meant "added relative to the non-vtime script
this one was copied from", which was useful while the copies were being written
and says nothing once the branch merges. Several carried a sentence of history
with them ("previously only the vtime dequeue removed a ckVtime entry"), which
belongs in the commit that changed it.
The long blocks came down to the part a reader cannot get from the code or from
a test. The gate report had nine lines describing a bug that now has two tests,
the arrival cap option had fifteen including measurements, and pass 2 had
seventeen. What survives in each is the invariant a future change could break
without noticing, most of all that floor registration is for repair only and a
new enqueue-side path has to stack instead.
The registration block appears three times and so did eleven lines explaining
it. Now once, with the other two pointing at it, which also stops the copies
drifting apart in prose while staying identical in code.
Test headers lose their provenance (which review or audit prompted them) and
keep the invariant plus the reason each fixture is shaped the way it is. One of
them also asserted that Lua truncates numbers to integers on the way into
Redis. It does not, measured on the 7.2 container the suites run against, so
that claim is gone rather than reworded.
The rewind guard added alongside it was covered, but deleting the idle
correction underneath it outright left all 59 vtime tests green, so the
behaviour that correction exists for was still held up by a comment.
A variant registering from the gated batch has to come back at its parked tag
rather than at the floor, or draining under the gate hands it full credit. The
comment saying so shrinks to the part the test cannot state, which is why the
current score is the thing that tells an already-registered variant apart from
one this call just added.
The gated-candidate block registers its batch with one variadic ZADD NX and
then, if that added anything, walks every member of gatedPending applying its
parked idle tag. The ZADD reports how many members it added but not which ones,
so the correction lands on candidates it did not register.
That reaches an already-registered variant whenever the pass-1 scan is
truncated, since knownRegistered comes from that scan and it reads only
scanLimit entries. A queue with more variants than that pushes registered ones
into pass 2 as if they were new. Their idle entry also survives re-registration
(the enqueue path reads the parked tag but never deletes it, and it is reaped
only once the floor climbs past), so with floor < parked < live the XX write
overwrites the live tag with the older one. The variant's clock winds back and
it is served ahead of variants that are genuinely due, which is the opposite of
what the feature is for and exactly what NX exists to prevent everywhere else.
The current score is the discriminator: at the floor means the variant either
just registered here or has no credit to lose, and above the floor means it has
spent a turn and keeps its tag. Reading it first also skips the idle lookup for
the advanced ones, so the branch gets cheaper rather than dearer, and the
steady state is untouched because none of this runs unless something registered.
Reported by Devin on #4367.
A second mutation audit covered the paths the first one listed as untouched:
the enqueue and nack registration, the ack, dead-letter and TTL-expiry drains,
and the TypeScript plumbing between them. 14 of 25 mutations were caught, and
the 11 green ones collapse into three real holes.
The idle park was checked on the dequeue path and nowhere else, so ack,
dead-letter and TTL expiry could all stop parking a drained variant's tag, and
nack could stop restoring it, with every suite still green. Each test here
gives the variant credit first, drains it by one route, then asserts the tag
reaches the idle set and comes back on the next enqueue.
The dead-letter test also covers its caller. The old one drove the Lua
directly, so forcing that branch to the untracked command was green while the
same damage done inside the script was caught. Reaching the drain through the
public API needs the rollout shape, where a flag-off instance empties the
variant queue without collecting it.
The TTL enqueue command carries its own copy of the registration block and no
test enqueued a run with a TTL under the flag, so all three of its behaviours
were unverified. And no test configured a quantum, so the weight dimension had
no coverage at all; this adds one at 0.3.
A variant whose head is scheduled in the future reports 'notReady' so pass 1
declines to spend a window slot on it. That was added deliberately and its comment
calls it load-bearing, but deleting the report left all four vtime suites green:
the behaviour was defended by comment and by nothing else.
Found by mutating the production Lua one change at a time and rerunning the
suites, on the principle that a green run against a broken invariant is a hole.
Seven of eight mutations were caught, some by more than twenty assertions; this
was the one that walked through. It is the same shape as the concurrency-gate bug
fixed in the previous commit, which is the uncomfortable part: the guard for one
half of the problem had no test while the other half was actively broken.
The test mirrors the gated one. Enough future-headed variants to fill the pass-1
window, sorted ahead on tag, and a servable variant behind them that fair order
says to serve first and age order says to serve last. Verified in both directions:
it passes against the real script and fails against the mutation with
'expected old to be owed', which is precisely the silent fall back to age order.
A candidate parked at its per-key concurrency ceiling fell out of tryServe
returning nil, so pass 1 spent one of its window slots on a variant it could not
serve. A gated variant's tag also stops advancing, so it keeps sorting to the
front of ckVtime and is revisited first on every call. Enough of them and pass 1
serves nothing, ever, and the scheduler quietly runs on pass 2's age order
instead.
The original note on this said work conservation still held because pass 2 fills
the batch, and that was the reason it was left alone. It does not hold. Where the
gated variants are also the oldest, which is the ordinary case since a variant
that has been queued longest is likely to be both old and saturated, pass 2's own
window fills with the same variants and servable work behind them is reached by
neither pass. The test added here starts from that shape and serves nothing at all
before the fix, rather than serving in the wrong order.
So a gated candidate now reports 'notReady', exactly as a future-scheduled head
already did, and pass 1 reads past it without spending a slot. The read is bounded
by scanLimit, which is already the cap on how far pass 1 will look.
It is not free. On a fully gated call pass 1 now reads to scanLimit instead of
stopping at the window: measured 53 Redis operations before and 80 after, every
one of the 27 a SCARD, so roughly 10 usec. That is worth paying, because a fully
gated call serves nothing either way, while a partially gated one goes from
serving nothing to serving in fair order. A second test pins the op count against
scanLimit plus the pass-2 window so the read cannot start running away.
Reported by Devin on #4367.
The cap on how far above the floor a brand-new variant may register defaulted to
64 quanta, framed as a guard against one inflated tag propagating and as a bound
on transitional spread. A blind multi-model review flagged that a burst larger
than the cap piles up on the cap line, and chasing that turned up something worse
than the tie cohort they described.
While the floor rises about a quantum per call, the cap line at floor + 64q rises
with it, and clamped arrivals stack 8 to 40 per quantum instead of the intended
one. The serving front crosses that dense band slower than the floor climbs, so a
backlogged variant's tag eventually climbs into the band, ties with the crowd, and
key-name order decides who runs. Every finite cap therefore collides after O(cap)
calls of sustained minting and restores a milder form of the starvation the
arrival rule exists to prevent, in the hostile-tenant case specifically, with
smaller caps failing sooner.
Measured on Redis, 40 fresh keys per call over 300 calls at maxCount 5: a 2000-deep
backlog kept 92 of 1500 slots at cap 64 and 293 of 1500 effectively uncapped. A
discrete-event model of the same shape predicted 90 and 292 before the run.
So the default goes to 2^32, leaving the clamp as a pure sanity bound against a
corrupted tag rather than an operational limit. The reasoning and the numbers are
in the option's doc comment, because the tempting instinct on reading "cap" is to
lower it. A test pins the sustained-minting shape so it cannot drift back.
Also documents why pass-2 discovery and the gated-pending batch still register at
the floor while the enqueue paths stack. Two reviewers independently read that as
an inconsistent application of the rule, which means the invariant needed writing
down: those two sites only ever see established work that lost its tag, so "serve
next" is right and there is nothing to stack behind, and a tenant cannot mint into
them while the flag is on because a flag-on enqueue registers the variant first.
Floor registration is for repair. A new enqueue-side path must stack, or fresh keys
start entering at the floor again.
Two tests, both for holes the fresh-key work opened or exposed.
The first pins the fix itself: a persistent backlog against eight brand-new
concurrency keys per call, asserting it keeps pace with the flag-off arm and that
the floor actually moves. Before the fix that shape served the backlog 1 time in
600 against flag-off's 120, so the assertion is nowhere near the boundary.
The second covers the rank cap, which had quietly lost its only test. The idle set
has two bounds, the at-or-below-floor reap and the cap, and the reap was dead while
the floor sat pinned, so the existing test asserted a pinned floor to prove the cap
was doing the work. Unpinning the floor killed that premise: the test now asserts
the floor advances, which is the fix, and no longer says anything about the cap.
The cap still matters, because a park only ever writes a tag ABOVE the floor, so
anything parked faster than the floor climbs is out of the reap's reach. The new
test seeds the idle set directly, far clear of any floor the fixture can reach, so
the reap provably cannot be what trims it, and checks the survivors are the highest
tags rather than an arbitrary subset. Mutation-checked: raising the configured cap
while holding the assertions fixed fails it, so it is not vacuous.
A concurrency key seen for the first time registered at the virtual-time floor.
The floor only rises to the lowest tag present or the lowest tag pass 1 actually
served, so a variant registered at the floor and served at the floor leaves it
exactly where it was. A workload minting a previously-unseen key per run (a uuid,
a high-cardinality tenant id) therefore pinned the floor at the epoch forever,
and any variant that had ever been served sat one quantum above it and lost every
comparison to the next arrival. Being served once was a permanent penalty.
Measured before, 120 calls at maxCount 5 against 8 fresh keys per call: the
backlogged variant took 1 of 600 slots with the flag on, against 120 of 600 with
it off. After: 120 of 600, and the floor ends at 119 rather than 0.
A variant with a remembered idle tag is unchanged, since the parked tag already
carries its history. One with none now joins one quantum behind the highest tag on
record instead of at the floor, bounded at floor + arrivalCap (64 quanta by
default) so a queue with a long-running leader cannot exile newcomers.
Two details are load-bearing and came out of simulation rather than reasoning.
Strictly behind the maximum, not level with it: registering at the maximum leaves
an unbounded lex-ordered tie cohort under overload and a lex-late variant still
starves. And falling back to the idle set's maximum when ckVtime shows nothing
above the floor, because drained keys carry their credit out of ckVtime into the
idle set, which an earlier draft measured at 0 of 600 for a lex-late hog.
Every added call sits inside the branch that the ZADD NX actually inserts on, so
an enqueue onto a registered variant costs exactly what it did before: the hot
path is untouched by construction rather than by measurement. A registration pays
one or two more reads, and skips the idle read when ckVtime already proves credit.
Same root cause as the drain-and-re-register starvation fixed earlier on this
branch. That was variants RETURNING to a stuck floor and was patched by
remembering their tag; this is variants ARRIVING at one, which no amount of
remembering can fix because a new key has nothing to remember. Unpinning the floor
addresses both.
Seven tag assertions move, each because the rule they encode has changed rather
than because behaviour regressed; their names and rationale are updated with them.
The idle-cap test loses its floor-pinned premise entirely, so it now asserts the
floor advancing, which is the fix itself.
Reported by Devin on #4367.
The note ran to three sentences, advertised a server env var a user cannot set,
and described the pass-1 window degradation. .server-changes/README.md asks for a
one-line description of behaviour rather than implementation, and says that
needing a paragraph usually means you are describing the implementation.
Reported by Devin on #4367; this is its suggested wording.
The gated-registration path in the vtime dequeue was the one writer that touched
:ckVtime without also touching :ckVtimeFloor. Everything else keeps the pair
alive together: the enqueue and nack registrations EXPIRE both, and a serving
dequeue SETs the floor with its own TTL. That path runs on calls that serve
nothing, so the floor-persist block, which is guarded on having served, is
skipped.
A base queue whose variants are all sat at their per-key ceiling therefore
refreshes the tags on every poll while the floor's TTL runs down underneath them.
Once it expires the next registration reads GET ckVtimeFloorKey back as '0' and
starts a brand-new variant below every established tag, so it leads pass 1 until
it catches up. Same hole as the one the enqueue floor-TTL test was added to close,
reached by a different path.
Reported by Devin on #4367.
A concurrency-gated candidate cost two Redis calls: the SCARD that discovers it is
gated, and a ZADD NX to make sure it is in the fair order. For anything pass 1
selected the second is a guaranteed no-op, because pass 1 draws its candidates from
the ckVtime zset and being in that scan is what registration means. tryServe now
takes a knownRegistered flag, so a gated visit from pass 1 costs only the SCARD,
the same as the flag-off command.
Pass 2 candidates can genuinely be unregistered, and ones outside pass 1's scanned
prefix are indistinguishable from those, so both are collected and settled after
pass 2 by a single variadic ZADD NX. Its return value is the count it inserted, so
the idle-tag correction that stops a drained variant reclaiming full credit only
runs when something actually registered. In the steady state nothing does and the
whole batch costs that one call.
Measured on the fully-gated shape, saturated (generator co-located with Redis, 1M
invocations per arm, Redis CPU/wall 0.978-0.987, no state drift):
N=1000 flag-off 21.05 before 76.63 (+55.6) after 54.56 (+33.5) -22.1us, 40%
N=10000 flag-off 21.09 before 77.99 (+56.9) after 57.52 (+36.4) -20.5us, 36%
A batched ZMSCORE reads the same information and measured better, -24.9us and
-24.7us for 45% and 43%. It was rejected anyway: it would have been the first thing
in this file to require Redis 6.2, and about 3 to 4 usec is a fair price for not
raising the floor. The variadic ZADD NX is one call either way; it costs more
because thirty skiplist lookups on the write path are dearer than thirty reads.
Worth noting the saving per call removed is nearer 0.4 usec than the 0.33 usec
measured previously on small keys, because the call being removed is a write
against a zset holding thousands of members.
Fully gated is the worst case by construction: a dequeue that serves exits earlier.
Per-key concurrency limits are ordinary on ck queues, so it is worth having.
The idle lookup only matters on the call that actually registers a variant. ZADD
NX is a no-op on one that is already registered, and its tag is already correct,
so the ZSCORE preceding it was wasted on every enqueue after the first. Doing the
ZADD first and the ZSCORE only when it reports an insert takes the common path
from two ops to one. The per-registration EXPIRE of ckVtimeIdle went too: the
park sites are the only writers that put anything in that key and they set its
TTL themselves, so refreshing it on a call that may never write there was pure
cost.
Applies to all four registration sites: enqueue, enqueue-with-ttl, nack, and the
gated-variant branch in the vtime dequeue. Six redis.call per registration
becomes four in the common case, five or six on the rarer call that registers.
Measured on a saturated benchmark (generator co-located with Redis, 1M
invocations per arm, 3 interleaved cycles, Redis CPU/wall 0.97 on every arm, two
independent cost measures agreeing to 0.04 usec). Against the flag-off enqueue
script at 8.603 usec, the vtime path was 10.903 usec (+26.7%) and is now 10.177
usec (+18.3%), so this removes about 30% of the virtual-time enqueue overhead.
That +26.7% independently reproduces the 26/23/24% total-CPU overhead the
cardinality benchmark measured by a different method.
A probe isolating the block gives the model behind it: roughly 1.38 usec fixed
per EVALSHA plus 0.33 usec per redis.call, linear in call count for O(1)
commands on small keys.
Behaviour is unchanged. Final ckVtime tags are identical across already
registered, unregistered, idle above floor, idle below floor and missing floor
key, and the starvation suite that asserts exact tags still passes.
The at-or-below-floor reap on :ckVtimeIdle is worth nothing while the floor is
pinned, and a workload that keeps minting fresh concurrency keys pins it
indefinitely: each new key registers at the floor and is served at it, so
minServableTag never rises. A resource benchmark caught the set growing by the
drain count every round and never shrinking, passing ckIndex in size by round
50 and reaching 12000 entries (1.77MB) over 60 rounds, with only the 24h state
TTL bounding it. The mechanism was measured rather than inferred: a probe
sampling the floor found it at 0 on every round while the lowest parked tag was
1, so ZREMRANGEBYSCORE could never match.
Adds a rank cap, keeping the highest idleMaxEntries tags (default 10000,
configurable), which does not depend on the floor moving. Trimming the lowest
tags first drops the entries nearest the floor, whose remembered credit is worth
least. Verified against an explicit cap of 3000: the set rises to it and stays
flat there across 12000 drains with the floor still pinned at 0.
The new ARGV is inserted before the metrics gauge arg, which has to stay last
because the gauge fragment reads ARGV[#ARGV].
Also drops the node:test describe import from the new test file, which shadows
vitest's own under globals:true. That is a wider pattern in this directory and
is left alone elsewhere.
A concurrency-key variant whose message zset drained was removed from ckVtime,
throwing away the virtual-time tag it had accumulated. Its next enqueue
re-registered it at the floor, so it came back with full credit. A variant
holding a persistent backlog keeps advancing its tag instead, so it lost every
pass-1 slot to variants that drain and reset each call, and pass 2 could not
help once the batch was already full. Measured on a backlogged variant against
five trickle variants: 1 serve out of 600 with the flag on, against 120 with it
off, inverting the fairness the feature exists to provide.
A parked tag now survives the drain in a sibling :ckVtimeIdle zset, and every
registration path (enqueue, enqueue-with-ttl, nack, and the gated-variant
branch) starts the variant at max(floor, idleTag) rather than at the floor.
The out-of-band drains (ack, dead-letter, TTL expiry) park the tag too. Entries
at or below the floor confer nothing, so a single ZREMRANGEBYSCORE per serving
call reaps them and bounds the set.
Deriving the floor differently was tried first and rejected by measurement: any
variant with a tag that never advances, which includes any concurrency-gated
key, pins the minimum and defeats it.
Backlogged variant now lands on its round-robin share in every shape, including
with a pinned-low gated or future-headed variant present, and with more trickle
variants than batch slots. Op-count overhead goes from 587 to 641 against a
budget of 900. The flag-off Lua is still byte-identical: 7 vtime command
variants changed, the other 31 commands hash the same as HEAD.
Only the vtime dequeue removed a variant from :ckVtime. Ack, TTL expiry and the
dead-letter path all ZREM a drained variant from ckIndex and left its ckVtime
entry behind, with a tag that had stopped advancing, until some later scan
happened to visit and collect it. Ack is much the most common of the three: it is
what a cancellation of a still-queued run runs through.
The limitations note called this bounded and self-healing, and it is, but on two
weaker grounds than it claimed. The 24h state TTL is refreshed by every enqueue,
nack and serving dequeue, so on a queue that is never quiet for a full day it
never fires, leaving floor advance as the only collection route. And that route
can be held still by a workload that keeps minting concurrency keys, because each
fresh variant registers at the floor and its first serve records the floor as the
minimum servable tag. It is also not fairness-neutral: registration is NX, so a
REUSED key inherits the stale high tag and is deprioritised, which means a
cancel-drain remembers history that a serve-drain forgets.
Adds vtime variants of the three commands rather than editing them, so the
flag-off scripts stay byte-identical by construction (this is a pure addition to
the file). Ack and dead-letter take the key as one more KEYS slot from the call
site; the TTL sweep derives it in Lua, as it already derives ckIndexKey, because
it discovers the queues it touches inside the script.
Tests cover all three paths and fail without the fix. The old stranded-entry test
is kept rather than deleted, retargeted at the pre-fix command directly, since
GC-on-scan is still load-bearing for an older instance during a rolling deploy.
Reported by Devin on #4367.
tryServe marks a variant attempted before the per-key concurrency gate, and pass
2's discovery step skips anything attempted, so a variant that was both gated and
unregistered fell through every route: pass 1 could not see it without a ckVtime
entry, pass 2's attempt was a no-op behind the gate, and discovery then passed
over it. It stayed invisible to the fair pass on every call for as long as the
gate held, and only a serve would have registered it.
Unregistered only arises where a variant reached ckIndex without a vtime-aware
write, which is the rollout case discovery already exists to repair: a backlog
queued before the flag went on, an enqueue from an instance that still has it
off, or a ckVtime that expired while ckIndex lived. Registration is NX so an
already-registered variant keeps the tag it earned, and the state TTL is only
written when the ZADD actually registered something, which is the path that can
recreate a ckVtime key that expired out from under a live ckIndex.
Adds a regression test that fails without the branch, and a second op-count
budget covering the all-unservable scan. The existing budget only bounds the
servable shape (its fixture acks immediately so nothing is ever gated or
deferred), and its comment read as a general worst case, which it is not.
Reported by Devin on #4367.
Carries the fix from #4628 into the three CK scripts this branch adds, which do
not exist on main and so could not be covered there. A concurrency key of '*'
renders a variant name identical to the wildcard member the master queue uses for
the base queue, and the unguarded transition cleanup then removed the entry the
rebalance had just written, stranding every concurrency key on that queue.
The pre-existing scripts are fixed in #4628; this is the same one-line guard
applied to enqueueMessageCkVtimeTracked, enqueueMessageWithTtlCkVtimeTracked and
nackMessageCkVtimeTracked.
Pass 1 now steps over a variant whose head is scheduled in the future without
spending one of its window slots, so a retry storm across enough keys can no
longer fill the window with variants that cannot be served and freeze the
virtual-time floor. The variant stays registered and stays scanned, which is
what keeps it reachable; only the budget is spared. The scan is capped at twice
the window, so a wider block still degrades to pass 2's age order.
A dequeue that serves nothing now persists nothing. Both things that block would
write are re-derivable: minServableTag is only set inside a successful serve, and
discovery only runs once the batch is full, so the floor read-repair is recomputed
from ckVtime on the next call anyway.
Refits the two tests whose premise these change: the freeze test now pins the
residual beyond the scan cap, and the floor test pins that a zero-serve call
persists nothing while the repair still lands on the next serving call.
The scenario said a bounded first-serve delay was fine without asserting any
bound, so nothing stopped that delay growing. It now pins the measured values:
the light key is first served on step 9 with the flag on against 72 with it off,
and cardinality above the pass-1 window costs no throughput (drain 79 on, 81
off). The harness has no wall-clock wait and no randomness, so those figures are
exact; the assertions carry a little slack for tie-break churn only.
At the moment the flag is flipped, :ckVtime is empty and every already-queued
variant is unregistered. The first dequeue has an empty pass 1, so pass 2 serves
and registers up to actualMaxCount variants. From the next call on, pass 1 can
serve one message per registered variant and actualMaxCount is often small, so
pass 1 fills the batch off that cohort alone. Pass 2 was gated on
dequeuedCount < actualMaxCount, so it never ran again, and the rest of the
backlog stayed invisible until a registered variant fully drained or an enqueue
or nack happened to land on it. A key that gets no further work has no other
route into the fair order. Same reachability shape 1a6d1a5 fixed for
registered-but-unservable variants, applied to the unregistered cohort. It also
covers a mixed deploy, where an instance with the flag still off enqueues
through the non-vtime command, and a :ckVtime that expired while ckIndex lived.
Pass 2 now always runs. When the batch is already full it registers the variants
pass 1 could not see, at the floor, instead of serving them, so the next call's
pass 1 leads with them. Serving is still capped at actualMaxCount, so no serve
happens that the old gate would have refused, and the fairness scenarios are
byte-identical: ckSkew, ckTrickle, ckSybil, ckBalanced, ckManyKeys, ckHeavyIdle
and ckStalledNewcomer all report the same numbers as before.
Op cost is one extra fixed op per call. The pass-1 window read doubles as a free
membership set, so nothing is registered twice, and the registrations are
collected into a single variadic ZADD NX rather than one call each. Measured on
the op-count budget test: 11.62 ops per dequeue over the flag-off path, against
10.90 before. The budget comment now counts 8 fixed ops rather than 7.
Devin's suggestion of reserving a batch slot for pass 2 does not fix it. Pass 2
walks ckIndex in age order, so its one reserved slot always lands on a variant
that is already registered and never reaches the cohort that is not. Measured
against the new tests: identical to no fix at all, 12, 16 and 12 calls.
Reported by Devin on #4367.
Reverts the de-registration added earlier on this branch. Dropping a variant from
ckVtime when it had work but nothing ready stranded it: pass 1 is the only reader
of ckVtime, and pass 2 is skipped whenever pass 1 fills the batch, so on a queue
busy enough to keep filling it the variant was never looked at again. A blind
review measured one sitting unserved for over two thousand calls after its head
became ready, and every nack backoff produces exactly that shape, so a single
steady key could hold up another key's retries indefinitely. That is worse than
the floor pinning it was meant to address.
The floor advance from servable variants handles both cases on its own, so the
de-registration bought nothing. It now also only takes its bound from pass 1.
Pass 2 picks candidates by message age, so its tag implies nothing about the
entries it skipped, and letting it move the floor stepped over registered
variants that were servable and simply never visited, confiscating their credit
on the next serve.
Adds the regression test the earlier tests were missing. They proved the variant
was evicted but never that it came back, which is the half that was broken.
The floor only tracked the lowest tag on record, so any registered variant that
could not be served held it there: one sitting at its own concurrency ceiling, or
one whose head is not ready yet. The keys actually being served advanced past it,
and since new keys register at the floor, a later arrival started underneath the
incumbents and took the fair pass until it caught up.
The floor now also rises to the lowest tag that was servable on the call. Pass 1
walks candidates in ascending tag order, so that is a safe lower bound. The repair
from the lowest tag on record stays, because both routes only ever raise it and it
still recovers a floor that was lost while ckVtime survived.
Also adds the fairness scenario the suite was missing. None of the six scenarios
nacked or used future-scored messages, so a stalled variant never existed and this
class of bug could not show up. In the window after it lands the latecomer now
takes 5 of 20 serves, against 12 of 20 without the fix.
A concurrency-key variant that has queued work but nothing ready yet, which is
what every nack with a retry backoff produces, stayed registered in ckVtime
holding its old low tag. The floor is the lowest stored tag, so it froze there
while the keys actually being served advanced. New keys register at the floor,
so a key that arrived later started well below the established ones and won
every pass-1 slot until it caught up, which is the starvation the feature is
meant to remove.
The dequeue path now de-registers a variant when it has work but none of it is
ready, alongside the existing GC for variants with no work at all. It stays in
ckIndex, so pass 2 still serves it in age order once its head is ready, and it
rejoins the fair order at the current floor on its next enqueue, nack or serve.
Idle keys no longer hoard priority credit either.
Measured with a control against a treatment on the real dequeue path: with one
future-headed variant present the floor stayed at 0 while served keys reached
25, and a newcomer took 20 of the next 20 serves. With the fix the same run
matches the control, newcomer 5 of 20.
Reported by Devin on #4367.
Keeps the change to the scheduler code, the CI tests, and the server-changes
note. The benchmark harnesses, e2e project, results, plans, and design
references were only ever local validation aids and don't belong in the repo.
Adds a resource/cardinality arm to the CK virtual-time benchmark: a plan, a
runnable harness (drives a real RunQueue against a dedicated Redis, flag OFF
vs ON, and reads server-side INFO memory/cpu, MEMORY USAGE and OBJECT
ENCODING; inert without CK_BENCH_REDIS_URL), and results from a local homelab.
Findings: the :ckVtime ZSET is essentially a second copy of :ckIndex (~150
bytes per key), so memory is linear in cardinality (about +1.3MB for a 10k-key
queue) and TTL-reclaimed; Redis CPU overhead is small and does not scale with
cardinality (+5 to +12 percent on an identical workload, per-script cost flat
at ~25 usec/call) because the dequeue window is fixed and the ZSET ops are
O(log N); and ckVtime membership tracks ckIndex exactly under sustained churn.
Ignore the generated micro-benchmark output (bench-results/) and the
standalone e2e harness run artifacts (node_modules, e2e-results, manifests,
.env, lockfiles) so benchmark runs do not dirty the tree.
Real flag OFF-vs-ON A/B from a local homelab with a production-like
multi-cluster topology (not production, no prod data or traffic). Micro
arm: a light key behind a backlog goes from first-served at step 480 to
step 4, wait p95 down ~70%, contention fairness 0.34 to 1.0, with the
balanced and lone-key cases unchanged and drain steps identical
(work-conserving). End-to-end arm across three worker clusters: the
victim tenant start latency drops ~38% mean while the flood tenant is
unchanged. Relative numbers only; single box, not prod scale.
Enumerate runs from a trigger-time id manifest instead of runs.list (the
list API can return empty on self-hosted, where it is ClickHouse-backed),
add waitdrain and preflight helpers, pin the CLI and SDK to a matching
version, and document the deploy invocation that actually works on
self-hosted: no --self-hosted or --local-build, and --network host so the
in-build indexer step can reach the instance API.
A prod-like A/B benchmark for the concurrency-key virtual-time scheduling
change. Includes a method doc (hypotheses, scenarios, metrics, results
template), a queue-level micro-benchmark that drives RunQueue with the flag
off vs on under identical load (reuses the fairness test harness; inert in CI
unless CK_BENCH_REDIS_URL is set), and a deployable end-to-end noisy-neighbor
trigger project. All numbers are relative (same box, same load) so the
scheduler is isolated from absolute throughput.
Reframe the retained findings/research headers so they no longer say
'delete before merge' (the spike harness is archived and ships nothing; the
findings ship as a design reference), and replace the placeholder
.server-changes/2026-XX-XX filename with the real dated file. Addresses CodeRabbit
notes on the design docs.
check-broken-links parses every .md under docs/ as MDX and can't parse the plain-
markdown plan (code/angle brackets), failing CI. These are engine design docs, not
user documentation, so relocate docs/superpowers/{plans,references} (plan,
findings, research, diagrams) to internal-packages/run-engine/design/ and fix the
internal path references. Also run oxfmt on runEngine.server.ts (missed after the
review fix wave), fixing code-quality.
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.
Captures the whole-branch review findings deliberately not code-fixed (bounded /
self-healing / pre-existing): ckVtime tombstone drift on ack/TTL/DLQ/rollback
paths and its 24h-TTL / key-delete mitigation; the pre-existing member-name
tie-break among equal tags; future-scheduled variants occupying the pass-1 window
under retry storms; and the rollout/rollback sequence.
Three-model blind review (no Critical). Fixes:
- Refresh ckVtimeFloor TTL on enqueue/nack, not just dequeue: a dequeue-quiescent
but enqueue-active base queue could expire the floor key while ckVtime survived,
making a new variant register at 0 and jump the backlog (fairness inversion).
- tostring() the vtime tag advance so a fractional quantum/weight is not truncated
to an integer by Redis's Lua-number ZADD conversion (silent tag freeze).
- Validate the env config: enable flag now uses BoolEnv (so =true/1/yes work, not
only '1'); quantum/windowMultiplier/stateTtlSeconds are int().positive() (a 0 TTL
errored SET ... EX 0 and stopped all CK dequeues; a 0 multiplier caused a full
ZRANGE scan). Constructor clamps as defense-in-depth.
- Tests: floor-not-lost regression (H1), large-N (>window) sharding no-starvation,
tightened ckBalanced no-harm bound, corrected op-count budget (EXISTS = 7 fixed).
- Softened a dangling plan-doc path in a comment.
Old Lua command bodies remain byte-identical (edits are in the ...Vtime... commands
+ env/wiring/tests only).
Task 10 (final). Adds the .server-changes note (ships dark, off by default), fixes
three stale/misleading test comments (keyProducer var naming; the un-seeded test 4
comment; the flag-off KEYS-scan comment now correctly credits redisTest flushall),
and applies format. No production logic changed.
Task 9. Threads the ckVirtualTimeScheduling option from RunEngineOptions.queue into
the RunQueue constructor, and exposes RUN_ENGINE_CK_VTIME_SCHEDULING_ENABLED (+
quantum, window multiplier, state TTL) env vars in the webapp. Off by default at
both layers (env default '0' -> undefined -> today's dequeue path). No behaviour
change until explicitly enabled.
Task 8. Flag-off test: with ckVirtualTimeScheduling absent, a mixed
enqueue/dequeue/nack/ack sequence creates zero *ckVtime* keys and serves in strict
head-timestamp (age) order, i.e. today's behaviour. createQueue extended to accept
null for an absent option. The whole run-queue suite (16 files, 146 tests) is green
with the feature code present and the flag off, proving byte-identical behaviour.
Task 7. New ckVtimeConcurrency.test.ts: two concurrent consumer instances on one
base queue serve every message exactly once (no double-serve, no lost message),
ckVtime drains empty and the floor never rewinds; concurrent enqueue-during-dequeue
never rewinds a tag; and a per-dequeue op-count budget (<= off + 50*(6+2*maxCount))
pins the vtime overhead. Verifies the atomic-single-Lua correctness story.
Task 6. New ckVtimeFairness.test.ts drives the real batched Lua (maxCount=10) with
flag-ON-vs-OFF ratio assertions over 5 ported spike scenarios, closing the spike's
maxCount=1 fidelity gap. ckSkew/ckTrickle: starved-key wait ON <= 0.3x OFF;
ckSybil (the case per-key caps cannot fix): light wait ON <= 0.7x OFF + first serve
within 3 steps; ckBalanced no-harm; ckHeavyIdle equal drain steps (work
conservation). Uses envConcurrencyLimit 1 to force serialization so the ON/OFF
contrast is non-vacuous (one-msg-per-variant-per-call would otherwise hide order at
limit 4). Reviewer traced each OFF baseline through the real Lua to confirm the
assertions genuinely discriminate.
Task 5. Adds nackMessageCkVtimeTracked: the existing tracked nack script verbatim
plus a slow-path ZADD ckVtime NX at the floor after the CK-index rebalance, so a
variant a nack revives from GC rejoins the fair order. Old nack script unchanged;
flag-off byte-identical. Test 13 covers nack re-registration; test 14 is a 200-op
closure-invariant property test (ckIndex subset of ckVtime). Also disables the
background master-queue consumers + worker in this file's createQueue helper
(matching the RunQueue test convention) so the tests verify the Lua invariant
under controlled ops instead of racing a background consumer (was a ~36% flake).
Task 4. Adds enqueueMessageCkVtimeTracked / enqueueMessageWithTtlCkVtimeTracked:
the existing tracked enqueue scripts verbatim plus a slow-path ZADD ckVtime NX at
the current floor (never rewinds an advanced tag), so a brand-new key is in the
fair order from its first enqueue (the sybil fix). Fast path does not register.
Old enqueue scripts unchanged; flag-off byte-identical. Tests 10/12 cover
registration-at-floor and fast-path purity; test 4 un-seeded.
Task 3 (core). Adds dequeueMessagesFromCkQueueVtimeTracked: a new flag-selected
Lua command that orders concurrency-key variants by SFQ virtual time. Pass 1 takes
candidates from a new :ckVtime ZSET by lowest tag, runs today's per-candidate serve
body verbatim (per-key gate, TTL/normal/stale branches, counters, ckIndex
rebalance), advances the served variant's tag within the batch, and GCs empty
variants from ckVtime too. Pass 2 fills in today's age order (window clamped to
>= maxCount*3) so the command is a strict superset of today: work-conserving and
mixed-deploy safe. Monotonic floor in :ckVtimeFloor; new variants enter at the
floor. The old tracked/untracked scripts are byte-identical and only run when the
flag is off. 10 behaviour tests incl. a discriminating vtime-beats-age-order case.
Task 2. Adds the off-by-default ckVirtualTimeScheduling option (enabled, quantum,
scanWindowMultiplier, stateTtlSeconds) to RunQueueOptions and resolves it into
private constructor fields for later tasks to read. No behaviour wired yet.
Task 1 of the CK virtual-time (SFQ) scheduling plan. Adds ckVtimeKeyFromQueue and
ckVtimeFloorKeyFromQueue (reusing the same base-queue normalisation as
ckIndexKeyFromQueue, so :ck:* and :ck:<value> map to one base key), the
RunQueueKeyProducer interface signatures, and byte-exact key tests. No runtime
behaviour yet.
Wes Mason