Dive C4.11.3 · part 3 of 3 · the payoff

Backoff as dynamic programming

A retry delay is a recurrence solved once per attempt. The bus already computes it — and never asks the wire to.

The two styles done, the chapter lands on a recurrence the bus computes in production. EchoMQ.Backoff — the retry-delay vocabulary of echo_fs, the F# port of echo/apps/echo_mq — turns a policy and an attempt count into a literal delay in milliseconds. Its Exponential case is exactly the shape this module teaches: base · 2^(attempts-1), clamped to a ceiling. Tabulate it over attempts 1..N and the whole retry schedule is a delay curve — a one-dimensional DP table the bus never has to keep, because the wire takes the literal and the host computes the curve. This dive first works edit distance as the textbook two-dimensional Array2D DP, so the arc closes on a named classic, then plots the real backoff curve from its recurrence. Every value was verified in dotnet fsi against EchoMQ.Tests/BackoffTests.fs.

Plot the backoff curve Module hub

C4.11.3 · part 1

Edit distance — the classic two-dimensional DP

The textbook two-dimensional DP is edit distance: the fewest single-character edits — insert, delete, or substitute — that turn one string into another. Indexed by two positions at once, it fills an Array2D. Cell d[i, j] is the distance between the first i characters of one string and the first j of the other; each cell is built from its three neighbours up and to the left. Put to work, it powers a "did you mean" suggestion: the closest catalog title to a misspelled query.

// fewest single-character edits from `a` to `b`, an Array2D filled top-left to bottom-right
let editDistance (a: string) (b: string) =
    let m, n = a.Length, b.Length
    let d = Array2D.zeroCreate (m + 1) (n + 1)
    for i in 0 .. m do d[i, 0] <- i      // base: delete i chars
    for j in 0 .. n do d[0, j] <- j      // base: insert j chars
    for i in 1 .. m do
        for j in 1 .. n do
            let cost = if a[i - 1] = b[j - 1] then 0 else 1
            d[i, j] <- List.min [ d[i - 1, j] + 1; d[i, j - 1] + 1; d[i - 1, j - 1] + cost ]
    d[m, n]
// val editDistance: a: string -> b: string -> int

editDistance "kitten" "sitting"   // val it: int = 3
editDistance "reciepe" "recipe"    // val it: int = 1  — one deletion of the extra e

Array2D: F#'s rectangular array, indexed d[i, j]; allocated with Array2D.zeroCreate and accessed O(1).
d[i, j]: the edit distance between the first i and first j characters; built from the cell above, the cell left, and the diagonal.
cost: 0 when the two current characters match, 1 when they differ (a substitution); the diagonal step pays it.
List.min: picks the cheapest of the three predecessor moves — delete, insert, or substitute — the optimal-substructure choice.

editDistance "reciepe" "recipe" is 1: a single deletion of the extra e turns the misspelling into the catalog title. That one-edit distance is what a "did you mean" search ranks suggestions by.

C4.11.3 · part 2

The backoff recurrence, verbatim

The chapter's payoff is shorter than the bridge: a recurrence the bus already runs. EchoMQ.Backoff is, quoted whole from echo_fs/EchoMQ/Backoff.fs, a discriminated union of policies and a pure function from a policy and an attempt count to a delay. The module's own documentation states the design — "a pure function from a policy and an attempt count to a literal delay in milliseconds. The wire takes the literal and never computes a curve, so the retry cadence is a value the caller can compute, table, and test without a server."

// echo_fs/EchoMQ/Backoff.fs — quoted verbatim
type Policy =
    | Fixed of ms: int
    | Exponential of baseMs: int * capMs: int
    | Jitter of inner: Policy

let rec delayMsWith (rng: System.Random) (policy: Policy) (attempts: int) : int =
    match policy with
    | Fixed ms -> ms
    | Exponential (baseMs, capMs) ->
        let shift = attempts - 1
        if shift >= 62 then capMs
        else int (min (int64 baseMs * (1L <<< shift)) (int64 capMs))
    | Jitter inner ->
        let bound = delayMsWith rng inner attempts
        if bound <= 0 then 0 else rng.Next(bound + 1)

let delayMs (policy: Policy) (attempts: int) : int =
    delayMsWith System.Random.Shared policy attempts
// val delayMs: policy: Policy -> attempts: int -> int

The Exponential case is the recurrence: 1L <<< shift is 2^shift where shift = attempts - 1, so the unclamped delay is base · 2^(n-1); min … capMs clamps it to the ceiling; and the shift >= 62 guard stops the int64 shift from overflowing. A subproblem — the delay at attempt n — is computed once; the schedule is the table.

Plot the backoff curve

Move base and cap and the figure plots delayMs (Exponential(base, cap)) n over attempts 1..10 — the real recurrence, computed by the same base · 2^(n-1) clamp as Backoff.fs. Each point is a tabulated cell; the dashed line is the cap. The static figure below shows Exponential(100, 10000), the policy in the tests.

delayMs (Exponential(base, cap)) n · attempts 1..10

base (ms) 100

cap (ms) 10000

policy: Exponential(100, 10000)

attempts to reach the cap: 8

Every point is a subproblem solved once by the recurrence. The curve doubles until it meets the cap, then flattens — and the bus stores none of it: the host fills the table and hands the wire one literal delay.

EchoMQ in F# — the recurrence above the wire

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.

This is the direct hit. Where memoisation and tabulation taught the technique on a track and a credit target, EchoMQ.Backoff is the technique in the bus itself: a recurrence solved once per attempt, the answer read back as a literal. Because the host computes the curve, the wire stays simple — it takes a number, not a policy — and the cadence is testable without a server, which is why the tests assert exact values rather than approximations.

echo_fs/EchoMQ.Tests/BackoffTests.fs · the curve, asserted

// quoted from echo_fs/EchoMQ.Tests/BackoffTests.fs
[<Fact>]
let ``exponential climbs then holds at the cap`` () =
    let p = Backoff.Exponential(100, 10000)
    Assert.Equal<int>(100, Backoff.delayMs p 1)
    Assert.Equal<int>(400, Backoff.delayMs p 3)
    Assert.Equal<int>(10000, Backoff.delayMs p 20)

The curve for that policy over attempts 1..8 is [100; 200; 400; 800; 1600; 3200; 6400; 10000] — climbing by doubling, then clamped at the 10000 ms cap from the eighth attempt on. The plotter above computes exactly these values; so does dotnet fsi.

The F# EchoMQ computes the backoff curve today — built and tested. The Valkey transport EchoMQ.Connector lands next; when it does, the consumer still computes the curve host-side and the bus still takes the literal, so the design does not move.

dynamic programming

Solve a recurrence once per subproblem; read the answer back from the table.

EchoMQ.Backoff

The recurrence is base · 2^(n-1) clamped; the table is the delay curve; the host fills it above the wire.

The chapter's last idea is the bus's design stated as an algorithm: a pure recurrence, tabulated host-side, with the wire handed a literal it never has to compute.

Where this leads

That closes the module: memoisation top-down, tabulation bottom-up, and a recurrence the bus computes in production. The chapter's final module assembles the pieces it has built — Store and the single-writer Broker — into the in-memory EchoMQ core, a mini echo_fs.

↑ C4.11 · Dynamic programming C4.11.1 · Memoization ← C4.11.2 · Tabulation

References

Sources

Microsoft — F# documentation — discriminated unions, recursion, and pattern matching.
FSharp.Core API reference — Array2D and the core list operators.
Microsoft — .NET documentation — System.Random and the integer types behind the shift.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — F4.11 · Dynamic programming — the E4 sibling this module reflects, the same arc in Elixir.
C4.11 — Dynamic programming — the module hub.
C4.07 — Identifiers, Snowflake & branded ids — the branded id the same echo_fs bus mints.
C4 — Algorithms & Data Structures — the chapter.