Universally Unique Lexicographically Sortable Identifier (ULID): 128-Bit Specification, Monotonicity & B-Tree Optimization

1. Overview & Core Advantages

The Universally Unique Lexicographically Sortable Identifier (ULID) is a modern 128-bit identifier specification engineered to solve the database index degradation and readability shortcomings inherent in legacy UUIDv4 implementations. In horizontally distributed microservices and petabyte-scale relational and NoSQL databases, generating unique primary keys without a centralized coordinating counter is a mandatory architectural requirement.

While UUIDv4 provides 122 bits of randomness, its complete lack of chronological ordering induces severe B-Tree index fragmentation, explosive random disk I/O, and buffer pool thrashing. ULID directly overcomes this limitation by integrating a millisecond-precision 48-bit UNIX epoch timestamp with 80 bits of cryptographically secure pseudorandom randomness (CSPRNG), encoded in Crockford’s Base32.

Core Architectural Advantages

• 128-Bit Compatibility: Exact bit-parity with UUIDs (16 bytes binary), allowing drop-in compatibility with native database uuid or binary(16) column types.
• Lexicographically Sortable: Because the high-order bits contain the millisecond timestamp, alphabetical sorting corresponds exactly to chronological creation ordering.
• Crockford’s Base32 Encoding: Emits a compact 26-character string (01ARZ3NDEKTSV4RRFFQ69G5FAV) with no hyphens. Crockford Base32 excludes confusing visual characters (I, L, O, U) to prevent human transcription errors and offensive words.
• Strict Millisecond Monotonicity: Provides an incrementing sub-millisecond counter mechanism that guarantees strict sorting order even when generating thousands of IDs within the exact same millisecond.
• Zero Server Transmission: Computation is 100% client-side via the browser’s native window.crypto.getRandomValues() CSPRNG. Identifiers are never transmitted to or logged by external servers.

2. Theoretical Principles & Bit-Level Architecture

The 128-Bit Layout & Crockford Base32 Representation

A ULID consists of 128 bits structured into two fundamental components:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                      48-bit Timestamp                         |
|                    (milliseconds since epoch)                 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|       Timestamp (cont.)       |         80-bit Entropy        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Entropy (cont.)                        |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                        Entropy (cont.)                        |
|                                                               |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Crockford’s Base32 Alphabet

Crockford Base32 uses 32 ASCII characters:

0123456789ABCDEFGHJKMNPQRSTVWXYZ

• Excluded: I, L, O (to prevent confusion with numerals 1 and 0).
• Excluded: U (to mitigate the accidental generation of profane words).
• Decoder Aliasing: Robust decoders map lowercase characters to uppercase, and map 'i'/'l' $\to$ '1', and 'o' $\to$ '0'.

The Monotonicity Specification & Sub-Millisecond Ordering

In high-throughput microservices, a single instance may generate tens of thousands of records within a single millisecond. Under basic ULID generation, the 80-bit entropy would be regenerated randomly for each ID, meaning records created at timestamp $T_1$ might sort arbitrarily among themselves.

The Monotonic Factory Specification eliminates this ambiguity:

1. When generating a new ULID at timestamp $T_{\text{now}}$:
   • If $T_{\text{now}} > T_{\text{previous}}$, initialize the 80-bit entropy with fresh CSPRNG randomness.
   • If $T_{\text{now}} == T_{\text{previous}}$, keep the timestamp identical and increment the 80-bit entropy field by 1 ($E_{\text{new}} = E_{\text{previous}} + 1$).
2. This guarantees absolute lexicographical sort order identical to the exact sequence of generation calls within the same millisecond.
3. Overflow Protection: If the 80-bit integer ($2^{80} \approx 1.2 \times 10^{24}$) overflows within a single millisecond, the generator throws an overflow exception (statistically impossible under realistic physical workloads).

3. Step-by-Step Custom Configuration Guide

TypeScript Implementation with Monotonic Support

export class UlidGenerator {
  private static readonly ENCODING = '0123456789ABCDEFGHJKMNPQRSTVWXYZ';
  private static readonly ENCODING_LEN = 32;

  private lastTime = -1;
  private lastRandom = new Uint8Array(10); // 80 bits = 10 bytes

  /**
   * Generates a monotonically increasing ULID.
   */
  public generate(now: number = Date.now()): string {
    if (now <= this.lastTime) {
      // Same millisecond: increment entropy
      this.incrementEntropy();
    } else {
      // New millisecond: sample fresh CSPRNG entropy
      this.lastTime = now;
      crypto.getRandomValues(this.lastRandom);
    }

    return this.encodeTime(this.lastTime) + this.encodeRandom(this.lastRandom);
  }

  private encodeTime(time: number): string {
    let str = '';
    for (let len = 10; len > 0; len--) {
      const mod = time % UlidGenerator.ENCODING_LEN;
      str = UlidGenerator.ENCODING.charAt(mod) + str;
      time = Math.floor(time / UlidGenerator.ENCODING_LEN);
    }
    return str;
  }

  private encodeRandom(random: Uint8Array): string {
    // Convert 10 bytes (80 bits) to 16 Base32 characters (each 5 bits)
    let str = '';
    // Process 80 bits as 16 chunks of 5 bits each
    let buffer = 0;
    let bitsLeft = 0;

    for (const byte of random) {
      buffer = (buffer << 8) | byte;
      bitsLeft += 8;

      while (bitsLeft >= 5) {
        bitsLeft -= 5;
        const index = (buffer >> bitsLeft) & 0x1f;
        str += UlidGenerator.ENCODING.charAt(index);
      }
    }

    if (bitsLeft > 0) {
      const index = (buffer << (5 - bitsLeft)) & 0x1f;
      str += UlidGenerator.ENCODING.charAt(index);
    }

    return str;
  }

  private incrementEntropy(): void {
    for (let i = this.lastRandom.length - 1; i >= 0; i--) {
      if (this.lastRandom[i] < 255) {
        this.lastRandom[i]++;
        return;
      }
      this.lastRandom[i] = 0;
    }
    throw new Error('ULID Monotonic 80-bit entropy overflow within single millisecond.');
  }
}

// Execution
const factory = new UlidGenerator();
console.log(factory.generate()); // e.g. "01HZX8N2G9B4C5D6E7F8G9H0J1"

4. Production Architecture & Performance Analysis

Database Index Benchmarking: ULID vs. UUIDv4

In relational engines like PostgreSQL and MySQL (InnoDB), primary keys define the clustered index structure. A clustered index stores table data physically ordered on disk according to the key.

UUIDv4 Inserts (Unsorted Random Entropy):
Root --> [Page A] --> [Page B] --> [Page C]
Insertion of '9f8b...' requires writing into middle Page B -> PAGE SPLIT -> Disk Thrash!

ULID Inserts (K-Sortable Chronological Order):
Root --> [Page A] --> [Page B] --> [Page C] --> [APPEND to Page C Tail]
Zero page splits! Writes stream sequentially to the end of index leaf nodes.

Microservice Event Sourcing & Partition Key Sharding

In distributed event streaming architectures (such as Apache Kafka or AWS Kinesis), ULID acts as the ideal partition key and event ID:

interface DomainEvent<T> {
  eventId: string; // ULID
  aggregateId: string;
  timestampMs: number;
  payload: T;
}

function createDomainEvent<T>(aggregateId: string, payload: T): DomainEvent<T> {
  const eventId = factory.generate();
  return {
    eventId,
    aggregateId,
    timestampMs: extractUlidTimestamp(eventId),
    payload
  };
}

// Extracts milliseconds without storing redundant timestamp column
function extractUlidTimestamp(ulid: string): number {
  const timeStr = ulid.slice(0, 10);
  let timestamp = 0;
  for (let i = 0; i < timeStr.length; i++) {
    const char = timeStr[i];
    const val = UlidGenerator.ENCODING.indexOf(char);
    timestamp = timestamp * 32 + val;
  }
  return timestamp;
}

5. Frequently Asked Questions (FAQs)

Q1: Can ULIDs be decoded to reveal when a record was created?

Yes. The first 10 characters (48 bits) of a ULID represent a standard UNIX epoch timestamp with millisecond precision. Anyone who inspects a ULID can extract the exact millisecond it was generated. If the creation time of an entity is classified or sensitive commercial metadata, use UUIDv4 or encrypted tokenization instead.

Q2: How does ULID compare directly with UUIDv7?

Both ULID and UUIDv7 (formalized in RFC 9562 in 2024) solve the same fundamental problem: combining a 48-bit millisecond timestamp with randomness for database index efficiency. The primary difference is representation: UUIDv7 uses standard 36-character hexadecimal format with hyphens (018e38f9-b88d-71b3-a7c8-472d2424b918), whereas ULID uses 26-character Crockford Base32 (01HZX8N2G9B4C5D6E7F8G9H0J1). Both can be stored interchangeably as identical 16-byte raw binaries in database columns.

Q3: What is the probability of a ULID collision?

With 80 bits of cryptographic entropy per millisecond, the probability of collision is mathematically negligible. There are $2^{80} \approx 1.2 \times 10^{24}$ possible unique values per millisecond. Even if a globally distributed system generated 1 billion IDs within the exact same millisecond across decentralized servers, the probability of collision remains below $10^{-6}$. When monotonic factory generation is enabled on single nodes, collision probability is zero.

Q4: How should ULIDs be stored in PostgreSQL or MySQL?

For optimal performance and minimal storage footprint, store ULIDs as 16-byte binaries:

• In PostgreSQL: Use the native UUID type. ULID hex bytes map directly to 128-bit uuid fields.
• In MySQL / MariaDB: Store as BINARY(16). Avoid storing as VARCHAR(26), as binary storage halves memory consumption and accelerates index comparisons by orders of magnitude.

6. Client-Side Privacy & Security Notice

All ULID generation in this browser utility relies on client-side Web Crypto API (window.crypto.getRandomValues()). Generated identifiers are calculated in volatile browser memory and are never transmitted, logged, or cached on our infrastructure. Your generation pipeline is completely private and secure.