R6.02.1 · Fairness under load — dive

Starvation under load — one line is not enough.

A single first-in, first-out line is fair to jobs and unfair to producers: when one floods the queue, the rest wait behind the whole flood. EchoMQ splits the line into lanes, one per producer, and drains them with a ring rotated one step per claim — so every lane is served in turn, whatever its backlog.

Grounding: echo/apps/echo_mq · EchoMQ.Lanes.claim/3 and the inline @gclaim Lua (the LMOVE rotate-then-serve) · the keys emq:{q}:ring and emq:{q}:g:<group>:pending.

One line, or one lane each. Select an arrangement to read what happens to the small producer. Producer A sends a flood; producer B sends a few — watch where B's work ends up.

readout · Select an arrangement. In one FIFO line, B's job sits behind A's entire flood and is served arbitrarily late — starvation. With a lane each, A's flood fills A's lane and B keeps its own, and the rota serves one head from each lane per turn, so B is served promptly whatever A sent.

§1

Why one line starves

FIFO couples order and share

Take a queue drained strictly first-come-first-served and two producers. Producer A submits a thousand jobs in a burst; producer B submits ten a moment later. In one line, B's ten sit behind A's thousand. B is not served until A is drained — its work is correct in its place and arbitrarily late. The line honoured arrival order perfectly, and it starved the small producer.

The cause is that a single line couples two things that should be separate: the order within a producer and the share between producers. First-in, first-out is the right rule for the first — a producer's own jobs should run in the order it sent them. It is the wrong rule for the second — a producer's share of the machine should not be proportional to how much it dumped on the queue. Couple them and the heaviest producer wins the machine.

Adding workers does not fix it. Ten workers drain A's thousand ten times faster, and B still waits for all thousand to clear the head of the line before its first job is even visible. The starvation is in the ordering, not the throughput — more workers drain the same unfair order faster.

A single line is fair to jobs and unfair to producers, because it couples order with share. The remedy is not more workers — it is to stop sharing the line.

§2

The lane is the unit

enqueue/5 · one set per producer

The fix is to split the line by producer. A queue is a set of lanes, each a per-group pending set named by a branded id (emq:{q}:g:<group>:pending). A's thousand jobs land in A's lane; B's ten land in B's. Within a lane, order is still first-in, first-out — a lane is a sorted set keyed by mint order, and the head is the oldest job. Across lanes, the line is no longer shared, so the question is no longer “who is first” but “whose turn is it”.

A lane is created by admission. EchoMQ.Lanes.enqueue/5 writes the job row with its group, adds the job to the group's lane, and — if the lane is serviceable and not already present — appends the group to the ring. Work that should ride a lane but is enqueued with no group is never claimed: the lane is the unit of fairness and of control, and ungrouped work has no lane to be served from.

Notes on ValkeyA lane is a sorted set; the head is read with ZPOPMIN (the lowest score). EchoMQ scores a job by its mint order, so the oldest job in a lane is always its head — first-in, first-out holds within a lane while the rotation orders service across lanes — valkey.io/commands/zpopmin.

The unit of fairness is the lane: one pending set per producer, named by a branded id, FIFO inside. The machine is shared across lanes, not the line.

§3

The rota guarantee

the @gclaim LMOVE

The ring is the rota. emq:{q}:ring is a list holding exactly the serviceable lanes — nonempty, unpaused, below their concurrency ceiling. A claim rotates the ring one step, then serves the head of the lane it landed on. The rotation is one atomic Valkey move:

LMOVE emq:{cm}:ring emq:{cm}:ring LEFT RIGHT   # the head moves to the tail; the claim serves it

The next claim rotates again and serves the next lane. Over one full turn of the ring, every serviceable lane is served exactly once — A's lane and B's lane each get one head per turn, whether A holds a thousand jobs or ten. A deep backlog fills its lane deeper; it never wins a larger share of the rota.

EchoMQ.Lanes.claim/3 is that operation, and its inline @gclaim Lua is the rotate-then-serve in full:

EchoMQ.Lanes · echo/apps/echo_mq — the @gclaim script: rotate the ring, serve the rotated lane's headverbatim

local g = redis.call('LMOVE', KEYS[1], KEYS[1], 'LEFT', 'RIGHT')   ← rotate one step
if not g then return {} end
local lane = ARGV[1] .. 'g:' .. g .. ':pending'          ← the lane the rota landed on
local popped = redis.call('ZPOPMIN', lane)                  ← its head = the oldest job
if #popped == 0 then
  redis.call('LREM', KEYS[1], 0, g)                          ← empty lane: leaves the ring
  return {}
end
local id = popped[1]
local jk = ARGV[1] .. 'job:' .. id
local att = redis.call('HINCRBY', jk, 'attempts', 1)         ← attempts = the fencing token
redis.call('HSET', jk, 'state', 'active')
local t = redis.call('TIME')                                ← the server clock leases the job
local now = t[1] * 1000 + math.floor(t[2] / 1000)
redis.call('ZADD', KEYS[2], now + tonumber(ARGV[2]), id)

The rota over three claims. Select a claim to read which lane it lands on after the rotation. The ring is [A, B, C]; each claim rotates one step then serves the head — the lanes are served in turn whatever their depth.

readout · Select a claim. The ring is [A, B, C]. Claim 1 rotates and serves A; claim 2 serves B; claim 3 serves C. Each lane is served one head per turn — A's thousand and B's ten get the same single turn, so depth never buys a larger share.

The guarantee is structural: fairness is constructed by the rotation, not bought with a priority number, not approximated by a hash. EchoMQ has no numeric per-job priority — the rota plus mint order already give a fair line, and a lane that should be served more carries a weight, the subject of the next dive.

the pattern

A single FIFO line lets one flood starve the rest. Split the line into one set per producer and serve the sets in turn — order within a producer preserved, share between producers equalised.

its EchoMQ application

The emq:{q}:ring rotated one step per claim by LMOVE, with EchoMQ.Lanes.claim/3 serving the head of the rotated lane — every lane served in turn, FIFO within, and no lane able to buy a bigger share by being deeper.

A consumer makes the guarantee concrete. In codemojex (echo/apps/codemojex), Codemojex.Guesses.submit/3 enqueues each guess on the player's lane — named by the player's PLR id — and Codemojex.ScoreWorker drains through Lanes.claim with the player id arriving as the lane group, so a player who mashes the keyboard fills only their own lane and the rota keeps serving every other player in turn.

/echomq/queue

References

sources · related

Sources

Valkey — LMOVE — the atomic pop-and-push that rotates the ring one step.
Valkey — ZPOPMIN — pop the lowest-scored member — the oldest job in a lane.
Valkey — LREM — remove a lane from the ring when it empties.
Valkey — Data types — the ring is a list and a lane a sorted set; the rota is list rotation.

Related in this course

R6.02 · Fairness under loadthe module hub
R6.02.2 · The weighted shareweights, the multi-pop, priority retired
R6.02.3 · Lanes vs separate queuesone queue with lanes against N queues
/echomq/queuethe rota wired at the claim point
/bcs/busPart B3, the fair-lanes architecture