4.3 Unique ID Generation

## Requirements for Distributed Unique IDs

Every system needs to identify things.

Orders need order IDs.

Messages need message IDs. Users need user IDs.

Events need event IDs. On a single database server, this is trivial: use an auto-incrementing integer. The database hands out 1, 2, 3, 4, and never repeats.

In a distributed system with multiple servers, multiple databases, and multiple data centers, auto-incrementing breaks down.

If server A hands out ID 5 and server B also hands out ID 5 at the same millisecond, you have a collision.

Two different orders share the same ID. Data gets overwritten or corrupted.

Distributed unique ID generation solves this, and it comes with a specific set of requirements that shape every design decision.

Uniqueness is non-negotiable. Two different objects must never receive the same ID, regardless of which server generated them, what time it was, or how many IDs are being generated per second.

Scalability means the ID generation system must keep up with the rate at which your application creates objects. A messaging platform generating 100,000 messages per second needs an ID generator that can produce 100,000 unique IDs per second without becoming a bottleneck.

Performance means ID generation must be fast. If generating an ID takes 50ms, every create operation in your system is at least 50ms slower. Ideally, ID generation takes microseconds, not milliseconds.

Sortability is often desirable. If IDs are roughly ordered by creation time, you can use the ID itself to sort records chronologically without needing a separate timestamp column. Database indexes on sortable IDs are also more efficient because sequential inserts are friendlier to B+ tree structures than random inserts.

Size matters for storage and network transfer. A 128-bit ID takes twice the storage of a 64-bit ID. Across billions of records, that difference adds up. Shorter IDs also fit more naturally into URLs and are easier for humans to work with when debugging.

No coordination is the ideal. If every server can generate IDs independently without talking to a central authority or to each other, the system is simpler, faster, and more resilient. Coordination introduces a potential bottleneck and a single point of failure.

Not every system needs all of these properties.

An internal logging system might not care about sortability.

A URL shortener might prioritize compact size above everything else. The design decisions you make depend on which requirements matter most for your specific use case.

Explore Grokking the System Design Interview for complete preparation.

## UUID/GUID: Versions and Trade-offs

UUID (Universally Unique Identifier) is the most widely used approach for generating unique IDs without coordination.

A UUID is a 128-bit value, typically represented as a 36-character string like `550e8400-e29b-41d4-a716-446655440000`.

The probability of two randomly generated UUIDs colliding is astronomically small. You would need to generate about 2.7 quintillion (2.7 × 10^18) UUIDs to have a 50% chance of a single collision.

For all practical purposes, UUID collisions do not happen.

UUIDs come in several versions, each generating the ID using a different method.

UUID v1 combines the current timestamp with the machine's MAC address. This guarantees uniqueness (the timestamp \+ MAC combination is unique) and produces time-ordered IDs. The downside is that the MAC address leaks information about which machine generated the ID, which can be a privacy or security concern.

UUID v4 is purely random. 122 of the 128 bits are randomly generated. No timestamp, no machine identifier. This is the most commonly used version because it is simple, requires no coordination, and reveals nothing about the generating machine. The trade-off is that UUIDs v4 are not sortable. Two UUIDs generated one second apart have no relationship to each other in sort order.

UUID v7 (standardized in 2022\) embeds a Unix timestamp in the most significant bits, followed by random bits. This produces IDs that are both globally unique and roughly time-ordered. UUID v7 is the modern answer for systems that need both the simplicity of UUIDs and the sortability of timestamp-based IDs. It is gaining adoption rapidly as the preferred UUID version for database primary keys.

**UUID Trade-offs**

The biggest advantage of UUIDs is that they require zero coordination.

Any server, anywhere in the world, can generate a UUID independently with virtually no risk of collision.

No central authority, no network calls, no shared state.

The biggest disadvantage is size. A UUID is 128 bits (16 bytes).

A 64-bit integer is 8 bytes.

For a table with a billion rows, the primary key index alone is 16 GB with UUIDs versus 8 GB with 64-bit integers.

UUIDs also perform poorly as clustered index keys in databases (particularly UUID v4) because random values cause fragmented index pages.

Every insert goes to a random position in the B+ tree, forcing the database to do random I/O instead of sequential appends.

UUID v7 mitigates the index fragmentation problem because its time-ordered nature means new IDs are always larger than previous ones, so inserts append to the end of the index rather than scattering randomly.

## Auto-Incrementing IDs in Distributed Systems

Auto-incrementing integers (1, 2, 3, 4...) are the default primary key strategy for single-database applications. They are compact (8 bytes for a 64-bit integer), naturally sortable, and human-readable.

But in a distributed system, they introduce a coordination problem.

**Why Auto-Increment Breaks**

If you have three database shards each generating their own auto-incrementing IDs, shard A generates 1, 2, 3 while shard B also generates 1, 2, 3\. You now have two different orders with ID 1\.

Merging data across shards becomes impossible without ID conflicts.

**Offset-Based Approach**

A simple fix is to assign each shard a different starting offset and increment.

Shard A generates 1, 4, 7, 10\.

Shard B generates 2, 5, 8, 11\.

Shard C generates 3, 6, 9, 12\.

Each shard increments by the total number of shards (3 in this case), starting from its shard number.

This works, but it has a critical limitation: adding a new shard requires changing the increment for all existing shards and potentially renumbering existing IDs.

If you go from 3 shards to 4, the entire numbering scheme changes.

This makes the approach fragile in environments where the number of shards changes over time.

**Centralized Sequence Generator**

Another approach is a single service that generates sequential IDs for the entire system. Every server requests IDs from this central service.

The service maintains a counter and hands out the next number on each request.

This preserves the simplicity and sortability of auto-incrementing IDs, but the central service is a single point of failure and a potential throughput bottleneck.

If it goes down, no IDs can be generated and the entire system's write path stops. Batching helps: instead of requesting one ID at a time, each application server requests a block of 1,000 IDs, uses them locally, and requests a new block when the current one runs out.

This reduces the frequency of calls to the central service and allows the application to continue generating IDs even if the central service is briefly unavailable.

## Twitter Snowflake ID Generator

Snowflake is the ID generation system Twitter designed to solve the distributed uniqueness problem with a compact, sortable, 64-bit ID.

It has become one of the most influential ID generation designs and is referenced in nearly every system design discussion about unique IDs.

**How Snowflake Works**

A Snowflake ID is a 64-bit integer divided into four sections.

Bit 0 (1 bit): Reserved, always 0 (ensures the ID is a positive integer in signed 64-bit representations).

Bits 1-41 (41 bits): Timestamp in milliseconds since a custom epoch (not the Unix epoch, but a chosen reference point like the date the system launched). 41 bits of millisecond timestamps give you roughly 69 years of unique values before rolling over.

Bits 42-51 (10 bits): Machine ID (also called datacenter ID \+ worker ID). This identifies which machine generated the ID. 10 bits support up to 1,024 unique machines.

Bits 52-63 (12 bits): Sequence number. A counter that increments for every ID generated within the same millisecond on the same machine. 12 bits allow 4,096 IDs per millisecond per machine. If more than 4,096 IDs are needed in a single millisecond, the generator waits until the next millisecond.

**Why Snowflake Is Elegant**

Snowflake IDs are 64-bit integers, half the size of UUIDs. They fit natively in most programming languages and database columns.

They are time-sortable because the timestamp occupies the most significant bits, so sorting by ID is equivalent to sorting by creation time.

They require no coordination between machines because each machine uses its own machine ID and local sequence counter.

And they are fast: generating an ID is a local operation involving reading the clock, incrementing a counter, and assembling the bits.

The maximum throughput per machine is 4,096 IDs per millisecond, which is roughly 4 million IDs per second per machine.

Across 1,024 machines, the system can generate over 4 billion IDs per second. That is sufficient for virtually any application.

**Snowflake Considerations**

#### Clock Dependency

Snowflake depends on the system clock being monotonically increasing.

If the clock moves backward (due to NTP adjustments, leap seconds, or clock drift), the generator could produce duplicate IDs (same timestamp \+ same machine ID \+ same sequence).

Production implementations typically detect clock regression and either wait for the clock to catch up or refuse to generate IDs until the issue is resolved.

#### Machine ID Assignment

Each machine needs a unique machine ID.

In small deployments, this can be assigned manually or through configuration.

In larger deployments, machine IDs are assigned through a coordination service like ZooKeeper, which introduces a dependency at startup (but not during ID generation).

#### Custom Epoch

By choosing a recent epoch instead of the Unix epoch (1970), you maximize the useful range of the 41 timestamp bits.

Twitter chose their launch date. You should choose a date close to your system's launch.

This extends the 69-year window into the future rather than wasting bits on decades before your system existed.

## Database Ticket Servers

Flickr introduced the ticket server approach in 2010 to generate unique, sequential 64-bit IDs using MySQL's auto-increment feature in a distributed context.

**How Ticket Servers Work**

You run one or more dedicated MySQL instances whose only job is generating IDs. Each instance has a table with an auto-increment column.

To get a new ID, a service inserts a row and reads back the generated ID.

The service does not store anything meaningful in the table.

The table exists solely to produce sequential numbers.

For redundancy, you run two ticket servers with different offsets.

Server A generates odd numbers (1, 3, 5, 7...) and server B generates even numbers (2, 4, 6, 8...).

If server A goes down, server B continues generating IDs.

You lose strict sequential ordering (IDs jump from 5 to 8 instead of 5, 6, 7, 8), but uniqueness is preserved.

**Trade-offs**

Ticket servers produce compact, naturally ordered 64-bit integers. They are simple to understand and implement.

The downside is that they introduce a network dependency: every ID generation requires a round trip to the ticket server.

Batching (requesting 1,000 IDs at a time) reduces this overhead but introduces gaps in the sequence when a batch is not fully used.

Ticket servers are also a potential bottleneck and single point of failure (mitigated by running multiple servers with offsets). They work well for moderate-scale systems (thousands of IDs per second) but are outperformed by Snowflake-style generators for high-throughput systems (millions of IDs per second).

## ULID and Other Sortable ID Schemes

The desire for IDs that are both globally unique and chronologically sortable has produced several alternatives to UUIDs and Snowflake.

**ULID (Universally Unique Lexicographically Sortable Identifier)**

ULID is a 128-bit identifier (same size as a UUID) that is designed to be sortable. It consists of a 48-bit Unix timestamp in milliseconds (giving \~8,900 years of range) followed by 80 bits of randomness.

When encoded, a ULID looks like `01ARZ3NDEKTSV4RRFFQ69G5FAV`, a 26-character Crockford Base32 string.

ULIDs are lexicographically sortable as strings, meaning you can sort them alphabetically and they sort chronologically. This is a significant advantage over UUID v4, which requires parsing the binary representation to extract any time information.

ULIDs generated within the same millisecond are distinguishable by their random portion.

Some implementations monotonically increment the random portion within the same millisecond (instead of generating a new random value) to guarantee strict ordering even within a single millisecond.

**Other Sortable ID Schemes**

KSUID (K-Sortable Unique Identifier) is a 160-bit ID consisting of a 32-bit timestamp (seconds, not milliseconds) and 128 bits of randomness. KSUIDs are larger than ULIDs but have more randomness, which further reduces collision probability. They are popular in API contexts where larger IDs are acceptable.

Nano ID generates compact, URL-friendly random IDs of configurable length. It is not time-sorted but is useful when you need short, random strings (like `V1StGXR8_Z5jdHi6B-myT`) for tokens, session IDs, or short-lived references.

TSID (Time-Sorted Unique Identifier) is inspired by Snowflake but uses fewer bits for the machine ID and more for the timestamp and sequence, optimizing for systems with fewer machines but higher throughput requirements per machine.

## Sequencer as a Building Block

In system design interviews and in production systems, the ID generator often appears not as a standalone topic but as a building block embedded within a larger design.

Understanding when and how to plug in the right ID generation strategy makes your designs more complete.

**Where Sequencers Appear in System Design**

URL shorteners need compact, unique IDs that map to long URLs. A Snowflake ID or a ticket server generates a numeric ID, which is then encoded in Base62 (a-z, A-Z, 0-9) to produce a short string like `a3Bx9K`. The ID generator is the core building block that determines the short URL's format and collision safety.

Message ordering in chat systems requires IDs that are globally unique and sortable within a conversation. Snowflake IDs or ULIDs work well because messages can be sorted by ID to reconstruct chronological order without a separate sort key.

Event sourcing systems assign a monotonically increasing ID to each event in a stream. The sequence number determines the order of events and is critical for replaying events correctly. Within a single partition, Kafka offsets serve this role. Across partitions or across systems, a Snowflake-style generator provides globally ordered event IDs.

Database sharding uses IDs that encode the shard information. Some systems embed the shard key in the ID itself, so that a service can determine which shard holds a record by examining the ID without querying a routing table. A Snowflake-style ID where the machine ID bits represent the shard achieves this.

Distributed tracing assigns a unique trace ID to each request as it enters the system. This trace ID propagates through all services and appears in logs and traces for correlation. A 128-bit random ID (UUID v4) or a 64-bit Snowflake ID both work. The trace ID does not need to be sortable, but it must be globally unique and fast to generate at the edge.

**Choosing the Right Scheme**

The decision comes down to your priorities.

Need strict sequential ordering with no gaps? Use a centralized ticket server with batching.

Need time-sorted 64-bit IDs at massive scale with no coordination? Use Snowflake.

Need sortable 128-bit IDs that work without machine ID assignment? Use UUID v7 or ULID.

Need IDs with zero coordination and do not care about sorting? Use UUID v4.

Need compact IDs for URLs or human-readable contexts? Generate a numeric ID (Snowflake or ticket server) and encode it in Base62.

**Beginner Mistake to Avoid**

New engineers sometimes default to UUID v4 for everything without considering the consequences.

UUID v4 works for many cases, but its randomness causes B+ tree index fragmentation in databases, leading to slower writes as the table grows.

If your IDs are primary keys in a database with millions of rows and high write throughput, time-sorted IDs (UUID v7, ULID, or Snowflake) perform significantly better because inserts always go to the end of the index instead of random positions.

Choosing the right ID scheme early avoids painful migrations later.

Interview-Style Question

> Q: You are designing a distributed messaging system like Slack. Each message needs a unique ID. Messages within a channel must be sortable by creation time. The system handles 500,000 messages per second across 200 servers. Which ID generation strategy would you use?

> A: Snowflake-style IDs. The requirements are time-sortability (messages must be orderable by creation time within a channel), high throughput (500,000 per second), compactness (64-bit IDs are more storage-efficient than 128-bit for a high-volume system), and no coordination (200 servers generating IDs independently). Assign each server a unique 10-bit machine ID from a coordination service (ZooKeeper or etcd) at startup. Each server generates IDs locally using its machine ID, the current timestamp, and a per-millisecond sequence counter. At 500,000 messages per second across 200 servers, each server handles about 2,500 messages per second, far below the 4,096-per-millisecond limit of a 12-bit sequence counter. UUIDs would also be unique but would double the storage cost for message IDs across billions of messages. Ticket servers could not handle 500,000 requests per second without massive batching and redundancy. Snowflake gives you uniqueness, sortability, compactness, and throughput in a single 64-bit integer.

_Snowflake ID Layout_

### KEY TAKEAWAYS

* Distributed ID generation requires uniqueness, scalability, performance, and often sortability, without centralized coordination.

* UUID v4 is the simplest option with zero coordination but is not sortable and causes index fragmentation. UUID v7 adds sortability and is the modern standard for database primary keys. * Auto-incrementing IDs do not work natively in distributed systems. Offset-based approaches and centralized ticket servers are workarounds with their own limitations. * Snowflake IDs are compact (64-bit), time-sorted, and generated locally with no coordination. They are the best choice for high-throughput systems that need sortable IDs. * ULIDs provide sortable 128-bit IDs with a compact string encoding. They are a good alternative when you want UUID-like properties with chronological ordering. * Choose your ID scheme based on your priorities: strict ordering (ticket server), time-sorted compactness (Snowflake), sortable universality (UUID v7 or ULID), or zero-coordination simplicity (UUID v4). * The ID generator is a building block that appears inside larger designs: URL shorteners, chat systems, event sourcing, database sharding, and distributed tracing.