R4.03.1 · Priority with composite scores — dive 1

Packing two keys in one score.

A priority queue needs two orderings at once. The composite-score pattern packs both into one number — priority × 0x100000000 + counter — the tier in the high bits, the arrival in the low.

Grounding: echo/apps/echo_mq/lib/echo_mq/lanes.ex · EchoMQ.Lanes.weight/4 — the real bus keeps the two orderings but splits them off the score: tier → lane weight, arrival → mint order.

The composite score — tier × 0x100000000 + counter. Set a priority and a counter; hover a field to read its bit-range. Raise the priority by one and the score jumps a full 2^32.

priority 2

counter 7

readout · Set the sliders; hover a field to read its bit-range.

§1

Two orderings, one score

lexicographic-sorted-sets.md.txt

A sorted set offers one ordering axis — the score. A priority queue needs two. Jobs in a higher-priority tier must come out before jobs in a lower tier, and within one tier the earliest-arriving job must come out first. A single number has to express both.

The move is positional. Reserve the high bits of the score for the tier and the low bits for the arrival order. Then the score compares tier-first automatically: any difference in the high bits dominates any difference in the low bits, because the high bits are worth more. Comparing two composite scores compares their tiers first and, only when the tiers are equal, their arrival counters.

A sorted set offers one ordering axis; a priority queue needs two, so the score reserves its high bits for the tier and its low bits for the arrival order, and the high bits dominate.

§2

The formula

lexicographic-sorted-sets.md.txt · Numeric rankings

The composite score is computed positionally: priority × 0x100000000 + counter. 0x100000000 is 2³² — 4294967296. Multiplying the priority by it shifts the tier left thirty-two binary places, leaving the low thirty-two bits at zero. The arrival counter — an atomic INCR on a per-queue counter key, taken when the job is added — then fills those low bits. The result is one number whose top half is the tier and whose bottom half is the position within the tier.

ZADD scored:jobs 4294967297 "job-A"   # priority 1, counter 1 → 1·2^32 + 1
ZADD scored:jobs 8589934594 "job-B"   # priority 2, counter 2 → 2·2^32 + 2

high 32 bits: The tier, priority × 0x100000000 — the band the job sits in.
low 32 bits: The arrival counter, INCR on a per-queue key — the position within the band.
one double: 53 bits of integer precision carry both fields exactly, so the score never rounds.

The score is priority × 0x100000000 + counter: the tier shifted into the high thirty-two bits, the arrival counter in the low — one double carries both exactly.

§3

The tier dominates the counter

lexicographic-sorted-sets.md.txt · bucketing

Because the tier sits in the high bits, any change in the tier outweighs every value the counter can take. Two jobs in tier 1, however far apart their counters, both score below any job in tier 2 — the smallest tier-2 score is 2 × 2³², larger than the largest tier-1 score, which is 1 × 2³² − 1 + 2³². The high bits set the band; the low bits position within it.

The hero figure shows it directly: raise the priority slider by one and the score jumps by a full 0x100000000, dwarfing any counter move. The interactive below pits two jobs against each other — one a step higher in tier, the other far ahead on the counter — and reports which composite score is smaller and therefore pops first.

Tier beats counter — which job pops first. Select a comparison; the readout names the smaller score and the winner.

Static verdicts — case A: tier 1 (counter 999) scores 4295968295, below tier 2 (counter 1) at 8589934593, so the tier-1 job pops first · case B: same tier, the smaller counter scores smaller and pops first.

The tier in the high bits outweighs every counter value: raise the priority and the score jumps a whole 2³², so tier order always wins over arrival order.

§4

In EchoMQ: the number moves to the lane

echo_mq/lanes.ex · weight/4

The real EchoMQ bus does not pack precedence into a job's score. EchoMQ.Lanes says so in the source: "there is no numeric per-job priority (retired by design); ‘served more’ is a property of the identity, not the work." EchoMQ keeps the two orderings the composite score combines, but separates them across two structures instead of two bit-ranges of one number.

The arrival order — the low bits in the textbook — is the branded JOB id itself. A lane set is written at score 0 (ZADD <lane> 0 <job-id>), so the set orders purely by member, and the typed, time-ordered id makes that member order the mint order. The high-bit tier becomes the lane's weight: EchoMQ.Lanes.weight/4 writes a gweight hash (group → weight), and EchoMQ.Lanes.wclaim/3 serves a higher-weight lane a larger share per rotation. The bit-packing trick is unnecessary because the precedence never lives in the job's number.

# EchoMQ.Lanes.weight/4 (lanes.ex) — the "high bits" become a lane weight, verbatim
def weight(conn, queue, group, w) when is_integer(w) and w >= 1 do
  _ = lane_key!(queue, group)
  keys = [Keyspace.queue_key(queue, "gweight")]
  case Connector.eval(conn, @gweight, keys, [group, Integer.to_string(w)]) do
    {:ok, 1} -> :ok
    other -> other
  end
end

Notes on ValkeyA sorted set compares members by score, then lexicographically within an equal score — the exact two-level order the composite score exploits, and the order EchoMQ's score-0 lane sets fall back to entirely — valkey.io/topics/sorted-sets.

the application · precedence on the identity

Two structures, not two bit-ranges

The composite score is one number doing two jobs. EchoMQ does the same two jobs with two structures: a score-0 lane set for arrival order (the branded id is the tie-break) and a gweight hash for tier precedence. The lane ring, the weighted rotation, and the order theorem are the Queue pillar of the EchoMQ course.

the pattern

Pack two fields into one ordering key: the tier in the high 32 bits, the arrival counter in the low 32, read with one ZPOPMIN.

its EchoMQ application

EchoMQ splits the two apart: arrival is the branded id's mint order (a score-0 set), and the tier becomes the lane's gweight. The precedence moves from the bits of a number onto the lane.

The composite score packs tier and arrival into one number; EchoMQ keeps both orderings but moves them off the score — onto a lane weight and a time-ordered id.

§5

Recap — one number, two fields

next → R4.03.2

The composite score reserves its high bits for the tier and its low bits for the arrival order, so one number orders by tier then arrival. EchoMQ reaches the same goal with two structures — a lane weight and a score-0 mint-ordered set. The next dive takes the low bits apart: the arrival counter that makes a tier FIFO, and the time-ordered id EchoMQ uses instead.

§6

References

sources · related

Sources

Redis — ZADD — add a member with its score; the write that scores a prioritized job by its composite number.
Redis — Sorted sets — score-then-member ordering, the axis the composite score occupies.
Redis — INCR — the atomic increment that produces the arrival counter folded into the low bits.
Valkey — Sorted sets — the engine's own reference for the score-then-member order behind both encodings.

Related in this course

R4.03 · Priority with composite scoresthe module hub
R4.03.2 · FIFO within a tierthe counter, and EchoMQ's score-0 mint order
R4.03.3 · ZPOPMINthe smallest-score pop that reads this score
R4.01.1 · The score is the fire-timethe sibling score
R4 · Time, Delay & Prioritythe chapter
/echomq · Queuethe lane ring and fair-share weight