encoding.ulid
Sortable unique identifiers: ULID text and binary forms, a thread safe monotonic generator, and range bounds for queries.
import encoding.ulid
A ULID is a 128 bit identifier made of a 48 bit timestamp in milliseconds and 80 random bits, written as 26 characters of Crockford base32. It is the sortable alternative to a random UUID: the text sorts in the order the ids were made, so a database index stays compact and a range of time is a range of ids. This package follows the ULID specification and is written in Salam.
The text uses the digits and the letters without I, L, O and U. The largest id is 7ZZZZZZZZZZZZZZZZZZZZZZZZZ, because 130 bits are used to hold 128. Parsing accepts lowercase, reads I and L as 1 and O as 0, and refuses U and anything above that largest id.
| Piece | What it is |
|---|---|
ULID | The value: time plus two 40 bit halves of the randomness. Compare with Compare, Equal and Less. |
New, NewString, NewBatch | Ids from the default generator. Strictly increasing in one process, safe from any number of threads. |
Generator | The monotonic generator of the specification, one lock around the last id. NewGeneratorWith takes your clock and entropy. |
Parse, String | Text in and out. Bytes and FromBytes give the 16 bytes, also the bytes of a UUID. |
FromParts | A time and 10 given bytes: no randomness, for exact tests. |
MinAt, MaxAt | The first and the last id of a millisecond, the bounds of a range query. |
Make, print and read back
New gives the next id of the default generator and String writes the 26 characters. NewAt makes an id for a time you choose. Every id is a value: copy it, compare it, keep it in a struct.
import encoding.ulid
func main:
id := ulid.New()
text := ulid.String(id)
println "length:", text.Len()
back := ulid.Parse(text)
println "round trip:", back.ok and ulid.Equal(back.id, id)
println "close to now:", ulid.Time(id) - ulid.Now() < 5000
stamp := ulid.NewAt(1469918176385)
println ulid.String(stamp.id).Len(), ulid.Time(stamp.id)
endParsing and the rules of the text
Parse follows the specification: lowercase and the aliases I, L and O are accepted, U is not, and the first character may not be above 7 because the value would not fit in 128 bits. ParseStrict wants exactly what String writes. Errors are codes, with ErrorText for a message.
import encoding.ulid
func show(text: str):
r := ulid.Parse(text)
if r.ok:
println text, "->", ulid.Time(r.id), ulid.String(r.id)
else:
println text, "->", ulid.ErrorText(r.err)
end
end
func main:
show("01ARYZ6S41TSV4RRFFQ69G5FAV")
show("01aryz6s41tsv4rrffq69g5fav")
show("O1ARYZ6S41TSV4RRFFQ69G5FAV")
show("7ZZZZZZZZZZZZZZZZZZZZZZZZZ")
show("80000000000000000000000000")
show("01ARYZ6S41TSV4RRFFQ69G5FAU")
show("01ARYZ6S41")
println ulid.ParseStrict("01aryz6s41tsv4rrffq69g5fav").ok
println ulid.ParseStrict("01ARYZ6S41TSV4RRFFQ69G5FAV").ok
endOrder and range queries
Text order is time order, so ids sort by a plain string sort. To select the ids of a time window ask for everything between MinAt(start) and MaxAt(end); in SQL that is a BETWEEN on the id column.
import encoding.ulid
func main:
mut ids := Vector {} as Vector<ulid.ULID>
defer ids.free()
mut mark := 1700000000000 as i64
repeat 4:
ids.push(ulid.MinAt(mark))
mark += 1500
end
repeat ids.Len() in i:
println ulid.String(ids.get(i))
end
low := ulid.MinAt(1700000001000)
high := ulid.MaxAt(1700000003000)
println "range:", ulid.String(low), ulid.String(high)
repeat ids.Len() in i:
inside := ulid.Compare(ids.get(i), low) >= 0 and ulid.Compare(ids.get(i), high) <= 0
println i, inside
end
endThe monotonic generator
Two ids made in the same millisecond must still sort in the order they were made. A Generator does what the specification says: in a new millisecond it draws fresh randomness, in the same one it adds 1 to the last random part, and when the clock moves back it keeps the last timestamp. If the 80 bits ever overflow, the timestamp moves one millisecond ahead instead of failing. The example uses a fake clock and a fixed entropy function so every character is known.
import encoding.ulid
mut now_ms := 1000 as i64
mut chunk := 7 as i64
func clock(): i64:
ret now_ms
end
func source(): i64:
ret chunk
end
func main:
g := ulid.NewGeneratorWith((): ret clock() end, (): ret source() end)
defer ulid.Free(g)
repeat 3:
println ulid.String(ulid.Next(g).id)
end
now_ms = 1001
chunk = 9
println ulid.String(ulid.Next(g).id)
now_ms = 900
last := ulid.Next(g)
println "clock went back:", ulid.Time(last.id), ulid.String(last.id)
println ulid.String(ulid.Increment(last.id).id)
endMany threads
The default generator and every Generator guard their state with a mutex, so threads share one without duplicates and without going out of order: every thread sees its own ids increase, and all ids together are distinct. NewBatch takes the lock once for n ids. The cost is one lock and one clock read per id.
import encoding.ulid
import pool
import mem
const WORKERS := 8
const EACH := 500
func main:
out := mem.AllocateZeroed((WORKERS * EACH * 3 * 8) as u64) as i64*
shared := ulid.Default()
pool.ParallelFor(WORKERS as i64, 4 as i64, (task: i64):
repeat EACH in k:
id := ulid.New()
slot := ((task * EACH + k) * 3) as int
out[slot] = id.time
out[slot + 1] = id.hi
out[slot + 2] = id.lo
end
end)
mut seen := HashMap {} as HashMap<str, bool>
defer seen.free()
repeat WORKERS * EACH in n:
id := ulid.ULID { time = out[n * 3], hi = out[n * 3 + 1], lo = out[n * 3 + 2] }
seen.put(ulid.String(id), true)
end
println "ids:", WORKERS * EACH, "distinct:", seen.size()
println ulid.Last(shared).ok
mem.Free(out as void*)
endWhen the random source fails
The built in source reads the operating system random generator through crypto.RandomBytes, which stops the program if the system cannot give random bytes: a weak id is never made. A source of your own, passed to NewGeneratorWith, can fail politely by returning a negative number. Next then returns ERR_ENTROPY and leaves the generator untouched, so the next call can succeed.
import encoding.ulid
mut failing := true
func clock(): i64:
ret 5000
end
func source(): i64:
if failing:
ret -1
end
ret 123456
end
func main:
g := ulid.NewGeneratorWith((): ret clock() end, (): ret source() end)
defer ulid.Free(g)
r := ulid.Next(g)
println r.ok, r.err == ulid.ERR_ENTROPY, ulid.ErrorText(r.err)
println "state untouched:", ulid.Last(g).ok
failing = false
ok := ulid.Next(g)
println ok.ok, ulid.String(ok.id)
endBytes, UUIDs and fixed ids
Bytes gives 16 bytes, big endian, the same size as a UUID, and FromBytes reads them back; the package does not depend on a UUID type, only on the bytes. FromParts builds an id from a time and 10 bytes you pick, which is how tests get exact answers. Free the byte vectors.
import encoding.ulid
import str
func hex(data: Vector<u8>): str:
digits := "0123456789abcdef"
mut out := ""
repeat data.Len() in i:
code := data.get(i) as int
out = out + str.Substr(digits, code / 16, 1) + str.Substr(digits, code % 16, 1)
end
ret out
end
func main:
r := ulid.Parse("01ARYZ6S41TSV4RRFFQ69G5FAV")
raw := ulid.ToUUIDBytes(r.id)
defer raw.free()
println raw.Len(), hex(raw)
back := ulid.FromUUIDBytes(raw)
println back.ok, ulid.String(back.id)
mut seed := Vector {} as Vector<u8>
defer seed.free()
repeat 10 in i:
seed.push((i * 3) as u8)
end
made := ulid.FromParts(1469918176385, seed)
println ulid.String(made.id)
part := ulid.Entropy(made.id)
defer part.free()
println hex(part)
endWhat people get wrong:
- Expecting
NewAtto be ordered inside one millisecond. It keeps no state; use aGenerator. - Treating the time as secret. The first 10 characters are the creation time, readable by anyone who sees the id.
- Comparing text with lowercase or aliases without
Parse:01arzand01ARZare the same id but different strings. - Forgetting to
Freea generator or to free the vectors ofBytes,EntropyandBatch. - Comparing ids made by different generators or machines for strict order: clocks differ, so only ids of one generator are strictly ordered.
Types
ULID
struct ULID| Name | Type | Description |
|---|---|---|
time | i64 = 0 | The timestamp in milliseconds since the Unix epoch. |
hi | i64 = 0 | The upper 40 bits of the 80 random bits. |
lo | i64 = 0 | The lower 40 bits of the 80 random bits. |
import encoding.ulid
func main:
r := ulid.Parse("01ARYZ6S41TSV4RRFFQ69G5FAV")
mut raw := ulid.Bytes(r.id)
defer raw.free()
println raw.Len(), raw.get(0), raw.get(15)
back := ulid.FromBytes(raw)
println back.ok, ulid.Equal(back.id, r.id)
mut wire := ulid.ToUUIDBytes(r.id)
defer wire.free()
println wire.Len(), ulid.Equal(ulid.FromUUIDBytes(wire).id, r.id)
mut tail := ulid.Entropy(r.id)
defer tail.free()
println tail.Len(), r.id.hi, r.id.lo
mut short := Vector {} as Vector<u8>
defer short.free()
short.push(1 as u8)
println ulid.FromBytes(short).err == ulid.ERR_BYTES
endResult
struct Resultok, the id and an err code.| Name | Type | Description |
|---|---|---|
ok | bool = false | True when the operation worked. |
id | ULID | The id; the zero id when ok is false. |
err | int = 0 | One of the error codes, OK on success. |
import encoding.ulid
func main:
r := ulid.Parse("01arYz6s41TsV4RrffQ69g5fav")
println r.ok, ulid.Time(r.id), ulid.String(r.id)
bad := ulid.Parse("01ARYZ6S41TSV4RRFFQ69G5FAU")
println bad.ok, bad.err == ulid.ERR_CHAR
println ulid.ParseStrict("01arYz6s41TsV4RrffQ69g5fav").ok
println ulid.IsValid("7ZZZZZZZZZZZZZZZZZZZZZZZZZ"), ulid.IsValid("8ZZZZZZZZZZZZZZZZZZZZZZZZZ")
endGenerator
struct Generator| Name | Type | Description |
|---|---|---|
state | i64* | The shared last timestamp and random parts, behind the lock. |
mu | sync.Mutex | The lock that guards the state. |
clock | func(): i64 | The function that returns the current time in milliseconds. |
entropy | func(): i64 | The function that returns 40 random bits, or a negative number when it fails. |
import encoding.ulid
mut tick := 100 as i64
func clock(): i64:
ret tick
end
func source(): i64:
ret 1
end
func main:
g := ulid.NewGeneratorWith((): ret clock() end, (): ret source() end)
defer ulid.Free(g)
first := ulid.Next(g)
second := ulid.Next(g)
println ulid.String(first.id)
println ulid.String(second.id)
println ulid.Less(first.id, second.id)
forced := ulid.NextAt(g, 50)
println ulid.Time(forced.id), ulid.Less(second.id, forced.id)
endConstants and variables
MAX_TIME
const MAX_TIME: i64 = 281474976710655import encoding.ulid
func main:
each code in [ulid.OK, ulid.ERR_LENGTH, ulid.ERR_CHAR, ulid.ERR_OVERFLOW, ulid.ERR_TIME, ulid.ERR_ENTROPY, ulid.ERR_BYTES, 99]:
println code, ulid.ErrorText(code)
end
r := ulid.Parse("short")
println r.ok, r.err, ulid.IsZero(r.id)
println ulid.MAX_TIME
top := ulid.MaxAt(ulid.MAX_TIME)
println top.time, top.hi, top.lo
endOK
const OK: i32 = 0The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_LENGTH
const ERR_LENGTH: i32 = 1The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_CHAR
const ERR_CHAR: i32 = 2The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_OVERFLOW
const ERR_OVERFLOW: i32 = 3The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_TIME
const ERR_TIME: i32 = 4The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_ENTROPY
const ERR_ENTROPY: i32 = 5The example for this item is shown with the ones above: encoding-ulid-Errors.salam
ERR_BYTES
const ERR_BYTES: i32 = 6The example for this item is shown with the ones above: encoding-ulid-Errors.salam
Functions
FromParts
func FromParts(ms: i64, entropy: Vector<u8>): Resultimport encoding.ulid
func main:
mut seed := Vector {} as Vector<u8>
defer seed.free()
repeat 10 in i:
seed.push((i + 1) as u8)
end
r := ulid.FromParts(1469918176385, seed)
println r.ok, ulid.String(r.id)
println ulid.FromParts(-1, seed).ok, ulid.FromParts(ulid.MAX_TIME + 1, seed).ok
println ulid.String(ulid.FromParts(ulid.MAX_TIME, seed).id)
endFromBytes
func FromBytes(b: Vector<u8>): ResultThe example for this item is shown with the ones above: encoding-ulid-Bytes.salam
FromUUIDBytes
func FromUUIDBytes(b: Vector<u8>): ResultThe example for this item is shown with the ones above: encoding-ulid-Bytes.salam
String
func String(id: ULID): strimport encoding.ulid
func main:
a := ulid.New()
b := ulid.NewString()
println ulid.String(a).Len(), b.Len()
println ulid.Less(a, ulid.Parse(b).id)
at := ulid.NewAt(1469918176385)
println at.ok, ulid.Time(at.id), at.id.time
println ulid.NewAt(ulid.MAX_TIME + 1).err == ulid.ERR_TIME
println ulid.Now() > 1700000000000
last := ulid.Last(ulid.Default())
println last.ok, ulid.Less(a, last.id)
fresh := ulid.NewGenerator()
defer ulid.Free(fresh)
println ulid.Last(fresh).err == ulid.ERR_TIME
endBytes
func Bytes(id: ULID): Vector<u8>The example for this item is shown with the ones above: encoding-ulid-Bytes.salam
ToUUIDBytes
func ToUUIDBytes(id: ULID): Vector<u8>The example for this item is shown with the ones above: encoding-ulid-Bytes.salam
Entropy
func Entropy(id: ULID): Vector<u8>The example for this item is shown with the ones above: encoding-ulid-Bytes.salam
Time
func Time(id: ULID): i64The example for this item is shown with the ones above: encoding-ulid-New.salam
Compare
func Compare(a: ULID, b: ULID): intimport encoding.ulid
func main:
early := ulid.MinAt(1000)
late := ulid.MaxAt(1000)
println ulid.Compare(early, late), ulid.Compare(late, early), ulid.Compare(early, early)
println ulid.String(early)
println ulid.String(late)
println ulid.IsZero(ulid.MinAt(0)), ulid.IsZero(early)
step := ulid.Increment(early)
println ulid.String(step.id)
println ulid.Increment(late).ok
endEqual
func Equal(a: ULID, b: ULID): boolThe example for this item is shown with the ones above: encoding-ulid-Bytes.salam
Less
func Less(a: ULID, b: ULID): boolThe example for this item is shown with the ones above: encoding-ulid-Next.salam
IsZero
func IsZero(id: ULID): boolThe example for this item is shown with the ones above: encoding-ulid-Compare.salam
MinAt
func MinAt(ms: i64): ULIDThe example for this item is shown with the ones above: encoding-ulid-Compare.salam
MaxAt
func MaxAt(ms: i64): ULIDThe example for this item is shown with the ones above: encoding-ulid-Compare.salam
Increment
func Increment(id: ULID): ResultThe example for this item is shown with the ones above: encoding-ulid-Compare.salam
Parse
func Parse(s: str): ResultThe example for this item is shown with the ones above: encoding-ulid-Parse.salam
ParseStrict
func ParseStrict(s: str): ResultThe example for this item is shown with the ones above: encoding-ulid-Parse.salam
ParseOr
func ParseOr(s: str, fallback: ULID): ULIDThe example for this item is shown with the ones above: encoding-ulid-Parse.salam
IsValid
func IsValid(s: str): boolThe example for this item is shown with the ones above: encoding-ulid-Parse.salam
NewGenerator
func NewGenerator(): GeneratorThe example for this item is shown with the ones above: encoding-ulid-New.salam
NewGeneratorWith
func NewGeneratorWith(clock: func(): i64, entropy: func(): i64): GeneratorThe example for this item is shown with the ones above: encoding-ulid-Next.salam
Next
func Next(g: Generator): ResultThe example for this item is shown with the ones above: encoding-ulid-Next.salam
NextAt
func NextAt(g: Generator, ms: i64): ResultThe example for this item is shown with the ones above: encoding-ulid-Next.salam
Batch
func Batch(g: Generator, n: int): Vector<ULID>import encoding.ulid
func main:
ids := ulid.NewBatch(5)
defer ids.free()
mut increasing := ids.Len() == 5
repeat ids.Len() - 1 in i:
if not ulid.Less(ids.get(i), ids.get(i + 1)):
increasing = false
end
end
println ids.Len(), increasing
endLast
func Last(g: Generator): ResultThe example for this item is shown with the ones above: encoding-ulid-New.salam
Free
func Free(g: Generator)The example for this item is shown with the ones above: encoding-ulid-Next.salam
Default
func Default(): GeneratorThe example for this item is shown with the ones above: encoding-ulid-New.salam
New
func New(): ULIDThe example for this item is shown with the ones above: encoding-ulid-New.salam
NewString
func NewString(): strThe example for this item is shown with the ones above: encoding-ulid-New.salam
NewAt
func NewAt(ms: i64): ResultThe example for this item is shown with the ones above: encoding-ulid-New.salam
NewBatch
func NewBatch(n: int): Vector<ULID>The example for this item is shown with the ones above: encoding-ulid-Batch.salam
ErrorText
func ErrorText(code: int): strThe example for this item is shown with the ones above: encoding-ulid-Errors.salam
Now
func Now(): i64The example for this item is shown with the ones above: encoding-ulid-New.salam