DEV Community

Devanshu Biswas
Devanshu Biswas

Posted on

ULID from scratch: 128 bits that sort by time, and why UUIDv4 never can

#node #webdev #programming #javascript

A UUIDv4 is 128 bits of pure randomness — globally unique, but with no order and no meaning. Insert a stream of them as primary keys and you fragment the database's B-tree, because each new row lands at a random spot in the index. A ULID carries the same 128-bit budget but spends it with intent: 48 bits of millisecond timestamp up front, 80 bits of randomness behind. Put the time first, big-endian and fixed-width, and sorting the IDs as plain strings sorts them by creation time. That's the one superpower UUIDv4 will never have — and you can build the whole thing in under 100 lines.

The shape: Crockford Base32, 26 characters 

const B32 = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"; // no I L O U
const TIME_LEN = 10;   // 48-bit ms timestamp   -> 10 chars
const RAND_LEN = 16;   // 80 bits of randomness -> 16 chars
const RAND_BYTES = 10; // 80 bits = 10 bytes
Enter fullscreen mode Exit fullscreen mode

Crockford's alphabet drops I L O U so nothing is mistaken for 1 or 0, or spells accidental words. 10 + 16 = 26 characters, 128 bits, same as a UUID but with no dashes.

Encode the timestamp — plain base conversion

A millisecond timestamp is at most 48 bits, and 2⁴⁸ sits comfortably below JavaScript's exact-integer ceiling of 2⁵³, so ordinary arithmetic is safe. Build the ten characters most-significant-first so the text stays big-endian:

function encodeTime(ms){
  let out = "";
  for (let i = TIME_LEN - 1; i >= 0; i--){
    const mod = ms % 32;              // low base-32 digit
    out = B32[mod] + out;             // prepend (big-endian)
    ms = (ms - mod) / 32;             // shift right by one digit
  }
  return out;                         // 10 chars, most-significant first
}
Enter fullscreen mode Exit fullscreen mode

The random half must be cryptographically strong (crypto.getRandomValues, never Math.random()) and kept as bytes — 2⁸⁰ is far past what a Number holds exactly, so it can never be one integer. Streaming 8-bit bytes into 5-bit Base32 characters is a small bit-buffer, and since 80 divides evenly by 5, exactly 16 characters fall out with no padding.

Monotonicity: same millisecond, still sortable

Here's the subtlety. Generate two ULIDs in the same millisecond with fresh random tails and their relative order is a coin toss. The monotonic factory fixes it by remembering the last value and, on a repeat millisecond, incrementing the random bytes by one — so the newer ID's tail is always strictly larger, and it always sorts after.

function monotonicFactory(){
  let lastTime = -1, lastRand = null;
  return function(ms = Date.now()){
    if (ms === lastTime){
      lastRand = incrementBytes(lastRand.slice()); // +1 on a copy
    } else {
      lastTime = ms;
      lastRand = randomBytes();                    // new ms -> new random
    }
    return encodeTime(lastTime) + encodeRandom(lastRand);
  };
}
Enter fullscreen mode Exit fullscreen mode

"Add one" to an 80-bit byte array is grade-school carrying: bump the last byte, or wrap 0xFF to 0 and carry left.

Decode is the mirror, and the sort is pure structure

Decoding runs the same steps backwards — normalise (O→0, I/L→1, upper-case), split off the first ten and last sixteen characters, then reverse each encoder. The timestamp is base-32 Horner's method:

function decodeTime(str){
  let ms = 0;
  for (const c of str) ms = ms * 32 + B32.indexOf(c); // base-32 Horner
  return ms;                                           // milliseconds
}
Enter fullscreen mode Exit fullscreen mode

The sort guarantee needs no comparator: the timestamp is first, big-endian, fixed-width, and the alphabet ascends in value — so byte-comparing two ULIDs compares their timestamps first, then their random tails, which is exactly chronological order. Break any one of those three properties and the guarantee evaporates.

ULID vs UUIDv4, in one line

Both are 128-bit IDs. UUIDv4 is random, unsortable, carries no time, and fragments an index on insert. ULID trades a little randomness for a timestamp and gets sortability, index locality, and a decodable creation moment — which is why it makes such a good time-ordered primary key. (One caveat: that timestamp is not a secret; anyone can decode it, so don't use a ULID where you wouldn't print a creation time.)

Generate a batch, burst several in the same millisecond to prove sortability, and decode any ULID back to the moment it was born, live at: https://dev48v.infy.uk/solve/day54-ulid-generator.html

Top comments (0)