ULID (original) (raw)

ULID, which stands for "Universally unique Lexicographically sortable IDentifier", is an alternative to UUID. The specification and the reference implementation in JavaScript are available from https://github.com/ulid . The ULID specification was published in 2016. In 2021 an Internet Draft proposed UUIDv7 , a time-based sortable unique identifier format influenced by earlier work, including ULID.

Why use ULID

The author of the spec/reference implementation explains the motivation behind it thus:

UUID can be suboptimal for many uses-cases because:

It isn't the most character efficient way of encoding 128 bits of randomness
UUID v1/v2 is impractical in many environments, as it requires access to a unique, stable MAC address
UUID v3/v5 requires a unique seed and produces randomly distributed IDs, which can cause fragmentation in many data structures
UUID v4 provides no other information than randomness which can cause fragmentation in many data structures

Instead, herein is proposed ULID:

128-bit compatibility with UUID
1.21e+24 unique ULIDs per millisecond
Lexicographically sortable!
Canonically encoded as a 26 character string, as opposed to the 36 character UUID
Uses Crockford's base32 for better efficiency and readability (5 bits per character)
Case insensitive
No special characters (URL safe)

Why not use ULID

Timing based UUIDs (type 1) or ULIDs can leak (surprise!) timing information. If you can see them then you can infer the rate at which some resource is being created. For example the rate at which a service is creating users or business transactions. This can be valuable competitive information you don't want to share with the world.

— programd on Hacker News

Implementation

The follow module has been tested in Tcl 8.5-8.6 and Jim Tcl 0.73. A version of this module with the Critcl code removed is included in Jimlib.

Download with wiki-reaper: wiki-reaper 48827 0 > ulid-0.1.2.tm

Code

A ULID generator with optional Critcl acceleration.

The default RNG is [::tcl::mathfunc::rand] in pure Tcl and the libc function

rand() when using Critcl. You can replace the default RNG by setting

::ulid::defaultRng to a script that returns a number between 0 and 31.

Copyright (c) 2017 dbohdan.

License: MIT.

namespace eval ::ulid { variable version 0.1.2 variable base32 [split 0123456789ABCDEFGHJKMNPQRSTVWXYZ {}] if {![info exists useCritcl]} { variable useCritcl 0 if {![catch { package require critcl 3 }]} { set useCritcl [::critcl::compiling] } } }

$t is the time in milliseconds.

proc ::ulid::encode-time {t len} { if {($t < 0) || ($t > 0xffffffffffff)} { error "expected unsigned integer representable in 48 bits but got
"$t"" }

set result {}
for {set i 0} {$i < $len} {incr i} {
    set m [expr {$t % 32}]
    set result [lindex <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo>:</mo><mo>:</mo><mi>u</mi><mi>l</mi><mi>i</mi><mi>d</mi><mo>:</mo><mo>:</mo><mi>b</mi><mi>a</mi><mi>s</mi><mi>e</mi><mn>32</mn></mrow><annotation encoding="application/x-tex">::ulid::base32 </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mrel">::</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">u</span><span class="mord mathnormal" style="margin-right:0.01968em;">l</span><span class="mord mathnormal">i</span><span class="mord mathnormal">d</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">::</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal">ba</span><span class="mord mathnormal">se</span><span class="mord">32</span></span></span></span>m]$result
    set t [expr {($t - $m) / 32}]
}

return $result

}

proc ::ulid::gen-random {rng len} { set result {} for {set i 0} {$i < $len} {incr i} { append result [lindex ::ulid::base32[∗::ulid::base32 [{*}::ulid::base32[∗rng]] } return $result }

proc ::ulid::rng {} { return [expr {int(32 * rand())}] }

if {$::ulid::useCritcl} { ::critcl::ccode "#define ULID_BASE32 "[join $::ulid::base32 {}]"" ::critcl::cinit { Tcl_Time t; Tcl_GetTime(&t); srand((unsigned int)(t.sec ^ t.usec)); } {} critcl::cproc ulid::rng-accel {} int { return rand() % 32; } critcl::ccommand ulid::ulid-accel {cdata interp objc objv} { Tcl_Obj* result; char s[27]; int i, m; Tcl_WideInt t;

    if (objc != 3) {
        Tcl_WrongNumArgs(interp, 1, objv, "t rng");
        return TCL_ERROR;
    }
    if ((Tcl_GetWideIntFromObj(interp, objv[1], &t) != TCL_OK) ||
        (t < 0) || (t > 0xffffffffffff)) {
        Tcl_SetObjResult(interp,
                         Tcl_NewStringObj("expected unsigned integer "
                                          "representable in 48 bits", -1));
        return TCL_ERROR;
    }

    for (i = 9; i >= 0; i--) {
        m = t % 32;
        s[i] = ULID_BASE32[m];
        t = (t - m) / 32;
    }
    for (i = 10; i < 26; i++) {
        int random;
        int rc = Tcl_EvalObjEx(interp, objv[2], 0);
        if (rc != TCL_OK) {
            return rc;
        }
        rc = Tcl_GetIntFromObj(interp, Tcl_GetObjResult(interp), &random);
        if (rc != TCL_OK) {
            return rc;
        }
        if ((random < 0) || (random > 31)) {
            Tcl_SetObjResult(interp,
                             Tcl_NewStringObj("expected random integer "
                                              "between 0 and 31", -1));
            return TCL_ERROR;
        }
        s[i] = ULID_BASE32[random % 32];
    }
    s[26] = '\0';

    Tcl_SetObjResult(interp, Tcl_NewStringObj(s, -1));
    return TCL_OK;
}
ulid::ulid-accel 0 ::ulid::rng

}

proc ::ulid::ulid {{t {}} {rng {}}} { if {$t eq {}} { set t [expr {[clock milliseconds]}] } if {$rng eq {}} { if {[info exists ::ulid::defaultRng]} { set rng $::ulid::defaultRng } elseif {$::ulid::useCritcl} { set rng ::ulid::rng-accel } else { set rng ::ulid::rng } } if {$::ulid::useCritcl} { return [ulid-accel tt trng] } else { return [encode-time t10][gen−randomt 10][gen-random t10][gen−randomrng 16] } }

proc ::ulid::test {} { if {$::ulid::useCritcl} { for {set i 0} {$i < [clock seconds]} {incr i 100001} { set accel [string range [::ulid::ulid $i] 0 9] set ::ulid::useCritcl 0 set pure [string range [::ulid::ulid $i] 0 9] set ::ulid::useCritcl 1 if {$accel ne $pure} { error "Critcl ULID time "$accel" doesn't equal
pure Tcl ULID time "$pure" for t $i" } }

    set ::ulid::useCritcl 0
    catch {::ulid::ulid nope}
    catch {::ulid::ulid 0 error}
    set ::ulid::useCritcl 1

    puts -nonewline "with Critcl:\n    "
}

puts [time ::ulid::ulid 10000]
catch {::ulid::ulid nope}
catch {::ulid::ulid 0 error}

if {$::ulid::useCritcl} {
    puts -nonewline "without Critcl:\n    "
    set ::ulid::useCritcl 0
    puts [time ::ulid::ulid 10000]
    set ::ulid::useCritcl 1
}

}

if {[info exists argv0] && ([file tail [info script]] eq [file tail $argv0])} { if {$argv eq {--test}} { ::ulid::test } else { set n [expr {$argv eq {} ? 1 : $argv}] if {![string is integer -strict $n]} { puts "usage: $argv0 [--test | n]" exit 1 } for {set i 0} {$i < $n} {incr i} { puts [::ulid::ulid] } } }

Use example

% source ulid.tcl % ::ulid::ulid 01BJ3J678K844ZTW53YPNB5K54 % ::ulid::ulid 0xffffffffffff 7ZZZZZZZZZT103WW4FN24H45Y7

Performance benchmark

$ tclsh ulid.tcl --test with Critcl: 9.0863 microseconds per iteration without Critcl: 38.7804 microseconds per iteration