Dive C4.07.2

Base62

A 64-bit integer, written in eleven characters — and written so the alphabetical order is the numeric order.

The Snowflake integer travels on the wire as a string. EchoMQ encodes it in Base62 over the alphabet 0-9 A-Z a-z, fixed at eleven characters. Two facts make the encoding earn its place. The alphabet is in ascending code-point order, and the form is fixed-width and big-endian — so a plain lexicographic sort of the strings agrees exactly with a numeric sort of the integers. That is the property the pending set leans on: mint order is id order, with no second index. This dive quotes echo_fs/EchoMQ/Base62.fs verbatim and proves the order property; every value was produced by dotnet fsi.

See order preserved Module hub

C4.07.2 · part 1

The encoding — base-62 with a fixed width

encode is the schoolbook base conversion: repeatedly take the integer modulo 62, prepend the alphabet character at that index, and divide by 62 — then left-pad to eleven characters. decode is its inverse: fold the string, each step multiplying the accumulator by 62 and adding the character's index. The module is quoted verbatim from echo_fs/EchoMQ/Base62.fs.

module Base62 =
    [<Literal>]
    let Alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

    /// The fixed transport width: 11 chars cover the full 64-bit range.
    [<Literal>]
    let Width = 11

    /// Encode a non-negative 64-bit integer to a fixed-width-11 Base62 string.
    let encode (n: int64) : string =
        if n < 0L then
            invalidArg (nameof n) "Base62.encode requires a non-negative integer"
        let sb = System.Text.StringBuilder()
        let mutable v = n
        if v = 0L then
            sb.Append(Alphabet.[0]) |> ignore
        while v > 0L do
            let r = int (v % 62L)
            sb.Insert(0, Alphabet.[r]) |> ignore
            v <- v / 62L
        sb.ToString().PadLeft(Width, '0')

    /// Decode a Base62 string back to its 64-bit integer.
    let decode (s: string) : int64 =
        let mutable acc = 0L
        for ch in s do
            let idx = Alphabet.IndexOf(ch)
            if idx < 0 then
                invalidArg (nameof s) (sprintf "Base62.decode: invalid character %c" ch)
            acc <- acc * 62L + int64 idx
        acc

Alphabet: 62 characters in ascending code-point order: 0–9 (indices 0–9), then A–Z (10–35), then a–z (36–61). The index is the digit value.
Width = 11: eleven base-62 digits cover the full 64-bit range (62¹¹ > 2⁶⁴). Fixing the width is what keeps the strings comparable.
PadLeft('0'): '0' is the alphabet's first character, so left-padding with it adds leading "zeros" without disturbing the big-endian order.
invalidArg: encode rejects a negative integer; decode rejects a character outside the alphabet. Both fail loudly rather than producing a wrong value.

C4.07.2 · part 2

Small values, exactly

The boundaries make the alphabet visible: 35 is the last digit-or-uppercase (Z), 36 is the first lowercase (a), 61 is the last single digit (z), and 62 rolls into a second column. Every encoding below was produced by dotnet fsi and round-trips through decode.

// Base62.encode, verified in FSI — note the width-11 left-pad
Base62.encode 0L      // val it : string = "00000000000"
Base62.encode 10L     // val it : string = "0000000000A"   (index 10)
Base62.encode 35L     // val it : string = "0000000000Z"   (last upper)
Base62.encode 36L     // val it : string = "0000000000a"   (first lower)
Base62.encode 61L     // val it : string = "0000000000z"   (last single digit)
Base62.encode 62L     // val it : string = "00000000010"   (rolls to a second column)
Base62.encode 3844L   // val it : string = "00000000100"   (62 * 62)
Base62.decode "00000000010"   // val it : int64 = 62L

Drop the PadLeft and the order breaks: "10" (62) would sort before "z" (61) because a shorter string compares first. The fixed width is not cosmetic — it is what the ordering depends on.

Encode, decode, and watch the order hold

Pick a value. The readout shows Base62.encode of it and the round trip back through decode, computed in this page's JavaScript with the same alphabet. The table below holds three real Snowflakes — two minted in the same millisecond (sequences 0 and 1) and one a millisecond later — and marks the selected one. Read the integers top to bottom and the strings top to bottom: the two orders are the same.

Integer order = string order · select a value

Base62.encode 55264149504028672 = "0456qLH4via" · decode back = 55264149504028672 · round trip exact.

The wire form and the integer agree on order. A store can keep the string and still serve oldest-first, or keep the integer and hand out the string — neither needs a separate sort key.

C4.07.2 · part 3

Why the order holds

Fixed width means both strings have the same length, so comparison is character by character from the left. Big-endian means the most significant digit is leftmost. An ascending alphabet means a larger digit is a larger character. Put together: at the first position where two encodings differ, the one with the larger integer has the larger character — which is exactly lexicographic order. The check below confirms it for the three real ids.

// the three real ids, encoded (FSI)
let a = Snowflake.compose 1717243200000L 7L 0L
let b = Snowflake.compose 1717243200000L 7L 1L
let c = Snowflake.compose 1717243200001L 7L 0L
Base62.encode a   // "0456qLH4via"
Base62.encode b   // "0456qLH4vib"
Base62.encode c   // "0456qLHMWqe"

// integer order and ordinal string order agree
(a < b && b < c)
&& (System.String.CompareOrdinal(Base62.encode a, Base62.encode b) < 0)
&& (System.String.CompareOrdinal(Base62.encode b, Base62.encode c) < 0)
// val it : bool = true

Base62 gives

An eleven-character, url-safe string whose lexicographic order matches the integer's numeric order.

The next dive adds

A three-letter namespace in front, and a total isValid a key builder enforces — C4.07.3.

EchoMQ in F#

A job id travels as the Base62 string, but the bus compares ids as the integer underneath — and because the encoding preserves order, the two agree. So EchoMQ can hold the pending set as the width-11 strings and still serve the oldest job first by reading the smallest string, with no separate sort column.

The F# EchoMQ encodes ids today — Base62 is built and tested (Base62Tests covers the round trip and the order property). The Valkey transport EchoMQ.Connector lands next.

The cost model on .NET

Encode and decode are O(11) — a bounded loop over at most eleven digits. The single allocation is the StringBuilder; Alphabet.[r] indexes a literal string and Alphabet.IndexOf(ch) scans 62 characters. The integer never leaves an int64 until the final ToString(). The Elixir course (E4.07) builds the same base62 over the same alphabet; the cost is dominated by the one string allocation on both runtimes.

↑ C4.07 · Identifiers ← C4.07.1 · The Snowflake C4.07.3 · Branded ids →

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.

References

Sources

Microsoft — F# documentation — strings, mutable bindings, and the for / while loops.
FSharp.Core API reference — int64 conversion and the operators used here.
Microsoft — .NET documentation — StringBuilder, String.PadLeft, and String.CompareOrdinal.
The F# Software Foundation — F# on the .NET runtime.

Related in this course

Elixir — The Snowflake bigint — the same integer and base62 step on the BEAM.
C4.07.1 — The Snowflake — the integer this dive encodes.
C4.07.3 — Branded ids — the namespace prefix and the validity gate.
C4.07 — Identifiers — the module hub.