jonnifyfsharp

Dive C4.10.2

Priority is a sort; fairness is a ring

Ordering is one line of F#. Fairness across groups is the line you have to build.

List.sortBy answers which job is most urgent. It does not answer whose job is served next — and if three owners each fill the queue, serving by urgency or by age alone drains one and starves the others. Fairness has to be constructed, and the construction is small: a ring of lanes and a rotation that moves the served lane to the back. That ring is the echo_fs bus's fair-lane rota, and it is four lines. Each result below was produced by dotnet fsi (9.0.303).

Serve the ring, watch it stay fair Module hub
C4.10.2 · part 1

Sorting — the urgent first

List.sortBy orders by a projected key; List.sortByDescending reverses it. Both are stable — equal keys keep their input order. For a queue served oldest-first, sorting is not even needed: a Set of branded ids is already in mint order, and Set.minElement reads the oldest in O(log n).

let jobs = [ ("J3", 3); ("J1", 1); ("J2", 2) ]
jobs |> List.sortBy snd
// val it: (string * int) list = [("J1", 1); ("J2", 2); ("J3", 3)]
jobs |> List.sortByDescending snd
// val it: (string * int) list = [("J3", 3); ("J2", 2); ("J1", 1)]

let pending = Set.ofList ["JOB003"; "JOB001"; "JOB002"]
Set.minElement pending   // val it: string = "JOB001"

Efficiency. List.sortBy is an O(n log n) merge sort (C4.03), stable, and it computes the key once per element rather than on every comparison. Set.minElement is O(log n) — when the order you want is already the structure's order, you read the front instead of sorting at all.

C4.10.2 · part 2

Fairness — the rotating ring

Sorting answers which job; it does not answer whose. The construction for fairness is a ring of lanes — one lane per group — and a rotation: take the head, then move it to the tail, so the next serve lands on a different lane. rotate advances the ring; next returns the lane to serve and the already-rotated ring in one step.

let next (ring: 'a list) =
    match ring with
    | [] -> None
    | head :: tail -> Some(head, tail @ [ head ])

let serve n ring0 =
    [1..n]
    |> List.fold (fun (out, r) _ ->
        match next r with
        | Some (lane, r') -> out @ [lane], r'
        | None -> out, r) ([], ring0)
    |> fst

serve 6 ["ada"; "kit"; "jo"]
// val it: string list = ["ada"; "kit"; "jo"; "ada"; "kit"; "jo"]

Six serves over three lanes give each lane exactly two turns, in order. The fairness is not a weight and not a hash — it is the rotation. The bus calls this lane a job's Group, and the ring holds only the lanes that currently have work.

Serve the ring, watch it stay fair

Choose how many times to serve a three-lane ring of owners. The ring rotates one step per serve, so the order served cycles through the lanes; the bars below count how many turns each lane got. With every serve count, the counts stay within one of each other — that is fairness, constructed by the rotation.

next over a 3-lane ring · ada · kit · jo

6
the ring · head served, then moved to the tail ada kit jo turns served ada 0 kit 0 jo 0 order served ada · kit · jo · ada · kit · jo 
let served = serve 6 ["ada"; "kit"; "jo"]
// ["ada"; "kit"; "jo"; "ada"; "kit"; "jo"]
6 serves over 3 lanes · each lane gets 2 turns — fairness from the rotation, not a weight

However many serves you ask for, the lane counts never spread by more than one. The ring does not weigh who deserves more; it guarantees no one is skipped while another is served twice.

EchoMQ in F#

Status — echo_fs is an in-memory model. The EchoMQ protocol — the Lua transitions executing on a Valkey wire — is not implemented (there is no Lua and no Valkey client in the code); that is the coming-soon transport (EchoMQ.Connector). This block shows how the model uses the structure, not a running bus.

The ring in the interactive is the bus's fair-lane rota, ported verbatim. A lane is a per-group pending set; the ring holds the serviceable lanes; every claim rotates it one step before serving. The whole rotation is two functions in echo_fs/EchoMQ/Lanes.fs:

// echo_fs/EchoMQ/Lanes.fs — verbatim
let rotate (ring: 'a list) : 'a list =
    match ring with
    | [] -> []
    | head :: tail -> tail @ [ head ]

let next (ring: 'a list) : ('a * 'a list) option =
    match ring with
    | [] -> None
    | head :: tail -> Some(head, tail @ [ head ])

The module's own comment names the property: fairness between identities is constructed, never hashed. rotate is the LMOVE LEFT RIGHT the Valkey bus uses to advance the rota — head off the front, onto the back. next packages the serve: it returns the lane to run and the ring already advanced, so the caller cannot forget to rotate. A job's lane is its Group: string option field (echo_fs/EchoMQ/Job.fs); a job with no group rides the default lane.

The ring rotation is pure and built today. The grouped, Valkey-backed store is coming soon — the LMOVE runs server-side over the lane lists, but the fairness contract is exactly the rotation shown here.

The F# idiom

List.sortBy for ordering; pattern-matching head :: tail and tail @ [head] for the rotation.

The bus's use

Lanes.next serves the head lane and advances the ring, so fairness across groups is built into the act of claiming.

Where this leads

Deduplication decided whether a job is admitted; priority decided whose job is served next. The last recipe is about time — how the bus spreads work across a window so a burst of failures does not become a storm, and how a pause holds a backlog without spending it. That is windowing.

↑ C4.10 · Practical recipes ← C4.10.1 · Deduplication C4.10.3 · Windowing →

References

Sources

Related in this course