jonnify·redis /redis-patterns/flow-control/fairness

R6.02 · Flow Control & Scale — module hub

Fairness under load — serve every lane in turn.

Fairness under load is keeping every producer's work moving when one floods the queue. A single first-in, first-out line lets one heavy producer starve the rest, so EchoMQ drains a set of lanes by a rotation that serves each in turn, and a weight tilts the share without letting any lane take all of it.

Grounding: echo/apps/echo_mq · EchoMQ.Lanes.claim/3 (the ring rotated one step by LMOVE, then the rotated lane served) · wclaim/3 + weight/4 (the gweight hash, K = min(weight, depth, glimit headroom)) · the keys emq:{q}:ring and emq:{q}:g:<group>:pending. Consumer: codemojex.

One ring, served in turn. Select a lane to read where it stands in the rota. Three lanes hold wildly different backlogs; each is served once per turn of the ring, so the heavy lane never starves the light ones.
LMOVE rotates the ring one step per claim A1000 B10 C200 each lane served once per turn — depth does not buy a bigger share
readout · Select a lane. The ring holds the serviceable lanes; LMOVE rotates it one step before each claim, so A (1000), B (10) and C (200) are each served once per turn. A deep backlog fills its own lane deeper — it never wins a larger share of the rota.
§1

The starvation problem

one FIFO line

A queue is the simplest shared resource: one line, drained first-come-first-served. That line is fair only while the producers are evenly matched. Put one producer that submits a thousand jobs beside one that submits ten, and the small producer waits behind the whole flood — the line is fair to jobs and unfair to producers. This is starvation: the order is correct, and the outcome is not.

The fix is to stop treating the queue as one line. A queue is a set of lanes, each a per-group pending set named by a branded id (emq:{q}:g:<group>:pending). Work is admitted into the lane of its group, so the heavy producer fills its own lane and the small producer keeps its own. The line is no longer shared; the machine is shared, and the question becomes how to drain many lanes fairly.

This module is the retarget of priority. An earlier approach reached for a numeric per-job priority — a composite score that sorts the line so urgent work jumps ahead. EchoMQ retired that by design: there is no numeric per-job priority. Fairness comes from the rotation and the weight, not from a number stamped on each job, because mint order plus the rota already give a fair line.

A single line is fair to jobs, not to producers: one flood starves the rest. The unit of fairness is the lane — one pending set per producer, named by a branded id — and the machine is drained across the lanes.

§2

The rota — service by rotation

claim/3 · the ring LMOVE

EchoMQ drains the lanes with a ring. emq:{q}:ring is a list holding exactly the lanes that can be served right now — nonempty, unpaused, and below their concurrency limit. Every claim rotates the ring one step before it serves, so the lane at the head changes on every claim. Fairness between identities is constructed by the rotation, never hashed and never sorted.

The rotation is one Valkey operation:

LMOVE emq:{cm}:ring emq:{cm}:ring LEFT RIGHT   # pop the head, push it to the tail — one atomic step

LMOVE pops the head of the ring and pushes it to the tail in one atomic move, then the claim serves the head of that rotated lane. The next claim lands on the next lane, and the one after on the one after — round and round, so a thousand-job lane and a ten-job lane are each served once per turn of the ring. A lane that empties or hits its ceiling drops out of the ring with LREM; it rejoins with RPUSH the moment it is serviceable again.

EchoMQ.Lanes.claim/3 is that move: rotate the ring one step, serve the head of the rotated lane, lease the job on the server clock, and return the job beside its group. No producer can jump the rota by submitting more — more work fills its lane deeper, and the lane is still served once per turn.

Notes on ValkeyLMOVE src dst LEFT RIGHT with the same key for source and destination is a single atomic rotate: the head moves to the tail and nothing else can interleave, so the rota step and the read are consistent. Every lane key carries the per-queue {q} hash tag, so the ring and the lanes co-locate on one slot and a multi-key claim is slot-legal — valkey.io/commands/lmove.

The ring holds the serviceable lanes; one LMOVE rotates it a step per claim, and the rotated lane's head is served. Fairness is built by the rotation, so backlog depth never buys a larger share.

§3

The weighted share

wclaim/3 · weight/4 · gweight

Equal rotation is the floor. Sometimes one lane should be served more than the others — a paid tenant, a latency-sensitive class — without ever being served all of the machine. That is a weight, not a priority.

A weight is a throughput share, an integer of one or more, set per lane with EchoMQ.Lanes.weight/4. It rides the emq:{q}:gweight hash, the same shape as the concurrency keys, and it never parks a lane (a parked lane is the operator's pause/3, not a weight of zero). EchoMQ.Lanes.wclaim/3 is the weighted rotation: it rotates the ring one step exactly as claim/3 does, then serves the rotated lane K heads in one turn instead of one, where:

K = min(weight, the lane's pending depth, the glimit headroom)

The three clamps each guard something. The weight is the share. The lane's pending depth means the turn never serves more than the lane holds. The glimit headroom — the room left under the lane's concurrency ceiling — means the weighted multi-pop can never push gactive past glimit; a weight is a throughput share but the limit is a concurrency ceiling, and the share bends to the ceiling. A higher-weight lane is served proportionally more over a window, never all of it, because the rotation still visits every other lane in turn.

One turn of the weighted ring. Select a lane to read how many heads it is served this turn. Three lanes carry different weights; each is served K = min(weight, depth, headroom) heads in its turn — more share, never the whole machine.
K heads served this turn — one row per lane A · w1 K=1 B · w3 K=3 C · w5 K=2 depth clamps C: weight 5, but only 2 jobs to serve
readout · Select a lane. A (weight 1) is served 1 head per turn — equal rotation. B (weight 3) is served 3, three times A's share. C (weight 5) holds only 2 jobs, so K clamps to its depth and 2 are served — the weight is a ceiling on the share, not a promise to fabricate work.

So fairness has two dials. The rotation gives every lane an equal turn; the weight tilts how much each lane gets per turn. Neither is a number on a job.

A weight is a per-lane throughput share, w ≥ 1, set with weight/4 on the gweight hash. wclaim/3 serves the rotated lane K = min(weight, depth, headroom) heads per turn — more share, never the whole machine, and never a per-job number.

§4

Applied in EchoMQ

echo/apps/echo_mq

The rota is the shipped fairness. EchoMQ.Lanes.claim/3 is how every consumer takes work, and the inline @gclaim Lua is the rotate-then-serve: one LMOVE rotates the ring, ZPOPMIN takes the head of the rotated lane, HINCRBY counts the attempt as the fencing token, and the server clock (TIME) sets the lease. wclaim/3 deepens the same one-step rotation to the lane's fair share.

EchoMQ.Lanes · echo/apps/echo_mq — the @gclaim script: rotate the ring, serve the rotated laneverbatim
local g = redis.call('LMOVE', KEYS[1], KEYS[1], 'LEFT', 'RIGHT')   ← rotate the ring one step
if not g then return {} end
local lane = ARGV[1] .. 'g:' .. g .. ':pending'          ← the rotated lane
local popped = redis.call('ZPOPMIN', lane)                  ← serve its head (mint order)
if #popped == 0 then
  redis.call('LREM', KEYS[1], 0, g)                          ← empty lane: drop from 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 architecture is the bus's fair-lanes property, stated in the manuscript:

bcs.3.md · B3 · the fair-lanes property

“A queue is not one line; it is a set of lanes, each named by a branded id, drained fairly. Lanes.claim is how every consumer takes work, and it spreads claims across lanes so no one lane starves the rest — the fair-lanes property. Group-aware pause and resume act on a lane without touching the queue, so one tenant can be held while the others run. Work that should ride a lane and is enqueued ungrouped is never claimed; the lane is the unit of fairness and of control.”

the pattern

Fairness under load: serve every producer in turn so a flood from one cannot starve the rest, and let a weight tilt the share without handing any one producer the whole machine.

its EchoMQ application

The emq:{q}:ring rotated one step per claim by LMOVE; EchoMQ.Lanes.claim/3 serves the rotated lane's head, and wclaim/3 serves a higher-weight lane K = min(weight, depth, headroom) heads per turn. There is no numeric per-job priority — “served more” is a property of the identity, not the work.

A consumer makes it concrete. In codemojex (echo/apps/codemojex), a Telegram emoji-guessing game on the same stack, Codemojex.Guesses.submit/3 enqueues each guess on the player's lane — the lane is named by the player's branded PLR id, so the queue emq:{cm}:g:<PLR…>:pending holds one lane per player. The scoring consumer, Codemojex.ScoreWorker, drains through Lanes.claim with the player id arriving as the lane group, so the bus rotates service across players and one keyboard masher cannot starve the field.

The deeper enforcement — the consumer loop that holds the rota under sustained load, the per-group ceiling that caps how much of the machine any one lane holds — is the queue's scaling layer, taught in the EchoMQ course rather than here.

Notes on ValkeyA lane is a sorted set keyed by mint order: ZPOPMIN takes the lowest-scored member, which is the oldest job, so within a lane the order is first-in, first-out while across lanes the rotation orders service — valkey.io/commands/zpopmin.

§5

When to use / when to avoid

the decision

Reach for fair lanes when:

  • Many producers share one queue and one of them can run hot — fan-in from many tenants, many users, or many rooms.
  • A flood from one source must not delay the rest, and the order within each source must still be honoured.
  • Some classes deserve a larger share of throughput than others, but none should ever take the whole machine — a weight per lane.

Avoid it when:

  • There is only one producer, or the producers are evenly matched — a plain line is simpler and equally fair.
  • The constraint is total concurrency, not fairness between producers — that is the per-group ceiling (limit/4, glimit/gactive), a sibling primitive, not the rota.
  • Strict global ordering across all producers is required — the rota deliberately interleaves lanes, so a job from a busy lane can be served after a later job from a quiet one.

Fair lanes solve fairness between producers; a concurrency ceiling solves how many run at once. They compose — the ring sets whose turn, the ceiling sets how much — and neither is a per-job priority number.

built ready to read
§6

References

sources · related

Sources

  • Valkey — LMOVE — atomically pop one end of a list and push the other; the ring's one-step rotation.
  • Valkey — RPUSH — append a lane to the tail of the ring when it becomes serviceable again.
  • Valkey — LREM — drop a lane from the ring when it empties or reaches its concurrency ceiling.
  • Valkey — ZPOPMIN — take the head (lowest score, the mint-ordered place) of a lane.
  • Valkey — Cluster specification — the {q} hash tag pins every key of a queue to one of 16384 slots, so a multi-key rotation is slot-legal.

Related in this course