jonnify·redis /redis-patterns/time-delay-priority/priority-scores/fifo-within-tier

R4.03.2 · Priority with composite scores — dive 2

FIFO within a tier.

Two jobs of the same priority share the same high bits. The low bits — an arrival counter — break the tie in arrival order, so a tier serves first-in-first-out.

Grounding: echo/apps/echo_mq/lib/echo_mq/lanes.ex · echo/apps/codemojex/lib/codemojex/notifier.ex — EchoMQ writes lane sets at score 0; the time-ordered branded id is the tie-break, no counter. The order theorem.

Three tier-1 jobs — counter versus priority-only. Hover a slot to read its counter and pop position; toggle to "priority only" to see the tie that loses arrival order.
tier 1 — three jobs, ordered by arrival counter
readout · Three priority-1 jobs. With the counter they pop in arrival order; with priority only they tie. Hover a slot.

Static order — with counter: zeta, beta, alpha (counters 1, 2, 3, by arrival) · priority only: all tie at score 1, the set falls back to member order, losing arrival.

§1

The tie a single field leaves

lexicographic-sorted-sets.md.txt

Score a job by its priority alone and every job in a tier gets the identical score. A sorted set keeps equal-score members in lexicographic order of the member, which for an arbitrary job is its id — not its arrival order. So a priority-only score loses arrival order inside a tier: two jobs added in sequence can come out in id order, which is arbitrary unless the id itself sorts by time.

ZADD scored:jobs 1 "job:zeta"    # arrived first
ZADD scored:jobs 1 "job:alpha"   # arrived second
# Equal scores → ordered by member: alpha before zeta — arrival order lost

A priority-only score ties every job in a tier; the set falls back to member order, which for an arbitrary id is not arrival order — the FIFO a queue user expects is gone.

§2

The counter breaks the tie

lexicographic-sorted-sets.md.txt · INCR

The composite-score pattern fills the low 32 bits with an arrival counter — the value of an atomic INCR on a per-queue counter key, taken inside the same operation that scores the job:

counter = INCR pc                    # the new value, atomically, one larger each add
score   = priority × 0x100000000 + counter

INCR returns the new value after incrementing, atomically. Each add reads a fresh counter, one larger than the last. So within a tier the first add gets the smaller counter, the second a larger one, and so on. The low bits now carry arrival order, and because they sit below the tier bits they break the tie without disturbing it. Three jobs of priority 1, added in order, take counters 1, 2, 3; their composite scores rise in the same order; the set keeps them head-first by arrival.

An INCR arrival counter in the low bits rises by one per add, so same-tier jobs sort by arrival, head first: strict FIFO within the tier, with no second structure.

§3

Why a counter, not a timestamp

lexicographic-sorted-sets.md.txt · ordering

A timestamp could order arrivals too, but it ties when two jobs arrive in the same millisecond. The INCR counter never ties: it rises by exactly one per add, atomically, regardless of clock resolution. Two jobs added in the same millisecond still get two different counters, so the within-tier order is total and deterministic. The counter is a logical clock for arrivals, immune to wall-clock collisions.

timestamp
Ties on same-millisecond arrivals; needs a tie-break of its own.
INCR counter
Rises by exactly one per add, atomically — total and collision-free.

A wall-clock timestamp ties on same-millisecond arrivals; the INCR counter is a logical clock that never ties, so the within-tier order is total.

§4

In EchoMQ: the id is the counter

echo_mq/lanes.ex · codemojex/notifier.ex

EchoMQ needs no arrival counter, because the branded JOB id is already a logical clock. A lane set is written at score 0 — ZADD <lane> 0 <job-id> — so the set orders purely by member; and the branded id is a 14-character name carrying a 63-bit snowflake (ts | node | seq), so its text sorts as the mint instant. Two jobs minted in the same millisecond still differ in the seq field, so the order is total without a side counter. EchoMQ.Lanes names this the order theorem: "mint order is the order theorem." The same FIFO the composite score buys with a low-bit counter, EchoMQ gets for free from the id it already carries.

The consumer is codemojex. Codemojex.Notifier.notify/3 enqueues each notification on EchoMQ.Lanes.enqueue(conn, "cm.notify", chat_id, job_id, payload) — a fair lane per chat — so within one chat's lane the notifications come out in mint order, FIFO, with no counter and no second index.

# Codemojex.Notifier.notify/3 (notifier.ex) — a fair lane keyed by chat id, verbatim
def notify(chat_id, text, opts \\ []) do
  job_id = EchoData.BrandedId.generate!("NOT")
  payload = Jason.encode!(%{chat: chat_id, text: text, opts: Map.new(opts), id: job_id, attempt: 1})
  case Lanes.enqueue(Bus.conn(), NotificationWorker.queue(), to_string(chat_id), job_id, payload) do
    ...
  end
end

Notes on ValkeyA sorted set orders equal-score members lexicographically by member — so a score-0 set ordered by a time-ordered branded id is FIFO by mint, no counter needed — valkey.io/topics/sorted-sets.

the application · codemojex · the order theorem

The id is the tie-break

Where the textbook adds an INCR counter to make a tier FIFO, EchoMQ writes its lane sets at score 0 and lets the time-ordered branded id be the tie-break — same within-tier FIFO, no counter key. The order theorem and the fair lanes in depth are the Queue pillar of the EchoMQ course.

the pattern

An equal-score tie falls back to arbitrary member order, so the pattern packs an INCR arrival counter into the low bits to make the tier FIFO.

its EchoMQ application

EchoMQ writes lane sets at score 0 and lets the time-ordered branded id be the tie-break: same within-tier FIFO, no counter key, no second structure — the order theorem.

Both reach FIFO within a tier: the pattern with a low-bit INCR counter, EchoMQ with a score-0 set and a time-ordered id.

§5

Recap — the low bits order arrivals

next → R4.03.3

A priority-only score ties same-tier jobs; an INCR arrival counter in the low bits breaks the tie in arrival order, making the tier FIFO. EchoMQ reaches the same order with a score-0 set and a time-ordered id — no counter. The next dive walks the consume: one ZPOPMIN reads the smallest score, and the lane rotation that serves the same head by weight.

§6

References

sources · related

Sources

  • Redis — INCR — the atomic increment behind the arrival counter; returns the new value, one larger each call.
  • Redis — ZADD — score a member; the write that places a job in its tier and arrival slot, and the score-0 write EchoMQ uses.
  • Redis — Sorted sets — equal-score members fall back to member order, the tie the counter — or a time-ordered id — removes.
  • Valkey — Sorted sets — the engine's own reference for the member ordering EchoMQ's score-0 lane sets rely on.

Related in this course