Unique ID Generator: requirements, rejected options and the Snowflake layout

The prompt: "Design a unique identifier generator for a distributed system."

Attempt this for 45 minutes on paper before reading. It is small, sharp, and produces one of the best trade-off discussions in the course.

This lesson covers the problem and the standard answer. It starts with why unique identifiers stop being free the moment you shard, and the five questions that shape the design. It then takes the four approaches that occur to everyone and rejects each for a specific, nameable reason — rejecting them properly is half the answer. It ends with the Snowflake layout. The next lesson covers what breaks it: clocks, machine identifiers, and the follow-ups.

Why this is a problem at all

On one database, unique identifiers are free: an auto-incrementing column. The database holds a counter, hands out 1, 2, 3, and guarantees no two rows share a value.

Sharding removes that guarantee (Sharding, and what it takes away). Sixteen shards each with their own auto-increment column will each produce the identifier 1,000, and now three different orders share it. Every system that shards eventually needs this, which is why it is asked so often despite looking trivial.

The five questions

1. How many identifiers per second? The number decides the design outright.

• Hundreds per second: a single database sequence is fine, and saying so is the correct answer.
• Tens of thousands: you need something distributed.
• Millions: you need the Snowflake bit layout (later in this lesson) and probably several generator nodes.

Ask for a peak, not an average, and ask about bursts — identifier generation spikes with whatever produces the entities.

2. Must they be numeric? A 64-bit integer stores in 8 bytes, sorts natively, indexes efficiently, and fits a BIGINT column. A string identifier costs more space in every index and every foreign key. If the answer is "they must be numeric", the design space narrows immediately.

3. Must they be sortable by time? This is the question candidates most often skip and interviewers most often care about. Time-sortable identifiers give you:

• "Most recent first" ordering with no separate timestamp index.
• Efficient inserts into a B-tree index, because new keys append at the right edge rather than landing randomly (the UUID discussion below explains why that matters so much).
• Cursor pagination for free.

4. Must they be unguessable? Sortable and unguessable are in direct tension. If identifiers increase over time, anyone with one identifier can guess neighbouring ones — which leaks how many orders you processed last night and enables enumeration of other users' resources. If the identifier is exposed in a URL, ask this explicitly.

5. How many bits, and how many datacentres and machines? 64 bits is the usual target because it fits a machine integer. The machine and datacentre counts decide how many bits must be spent identifying the generator.

The requirements we will design against

State them back:

• Globally unique, with no duplicates ever.
• Numeric, 64 bits.
• Roughly sortable by creation time.
• At least 10,000 identifiers per second, with bursts far above that.
• Generated without a network call, so it never becomes a shared bottleneck.
• Multi-datacentre.

That last requirement — no network call — is the one that rules out most simple answers, and it is worth calling out. If every entity creation must first ask a central service for an identifier, that service is now in the critical path of every write in the company.

The obvious options: database auto-increment

Four approaches occur to everyone. Each fails for a specific, nameable reason.

One database owns a counter and hands out the next value on every insert.

• Correct? Yes, on one database.
• Why it fails: it is a single point of failure — that database down means no new entities anywhere. It is a bottleneck: every entity creation in the system is a write to one row, capping you at a few thousand per second. And it does not survive sharding, which is what brought you here.

Multi-master with offsets

Two databases: one produces odd numbers, one even. Generalised, k servers use step k with different starting offsets.

• Why it fails: the step is baked into the configuration, so adding a server means reconfiguring every existing one and reasoning carefully about overlaps. Identifiers are not time-sortable across servers — server 1 might be at 1,000,001 while server 2 is at 3,000,002 with no relationship to when they were issued. And each server is still a single point of failure for its own stream.

UUID version 4

A 128-bit value with 122 random bits, generated locally with no coordination at all.

• What is genuinely good: no coordination, no single point of failure, no configuration, and collisions are negligible — with 122 random bits you would need on the order of 10^18 identifiers before a collision becomes likely.
• Why it still fails the requirements: it is 128 bits, twice the target, and it is not sortable by time — consecutive identifiers are unrelated.

The third problem is the one worth spelling out, because it is the answer to "so what if it's random?":

Random identifiers are hostile to B-tree indexes. A B-tree keeps keys in sorted order. With a time-ordered key, every insert lands at the right-hand edge, touching the same few pages, which stay in memory — insert cost is close to nothing. With a random key, each insert lands on a random page, so the database must read that page from disk if it is not cached, modify it, and write it back. Once the index exceeds memory, insert throughput falls sharply and the index fragments as pages split.

The storage cost compounds too. 16 bytes rather than 8 is +8 bytes on the primary key, plus 8 bytes in every secondary index and every foreign key referencing it. On a table of one billion rows with three secondary indexes, that is roughly 32 GB of extra storage before you count page overhead.

(UUID version 1 embeds a timestamp, but with the time fields ordered so that the value does not sort chronologically as a byte string, so it does not solve the index problem either. UUID version 7, in Follow-ups, does.)

A ticket server

A single dedicated service holding a counter, handing out identifiers over the network.

• What is good: identifiers are small, numeric, and increasing; clients need no configuration.
• Why it fails: it is still a single point of failure, now with a network hop in the critical path of every write. Running two for redundancy reintroduces the offset problem. This design has been used successfully in production — the well-known example is Flickr's ticket servers — with the honest caveat that they accepted the single point of failure and managed it.

One rescue worth naming: hand out ranges rather than single values. A server asks for a block of 10,000 identifiers, then allocates from it locally with no network call for the next 10,000. That reduces the coordination rate by four orders of magnitude and turns the ticket server from a per-write dependency into a per-block one. It is a genuinely good design, and its cost is gaps in the sequence when a server restarts with a partly used block.

The Snowflake approach: the 64-bit layout

The standard answer: build the identifier out of fields, so that uniqueness comes from partitioning the number space rather than from coordination. The design is widely known as Snowflake, after the scheme Twitter published.

The identifier is these fields concatenated, most significant first, and the ordering of the fields is the whole trick: the timestamp occupies the high bits, so numeric order is chronological order.

Why each field is that width

Sign bit (1). Many languages have no unsigned 64-bit integer, and a negative identifier breaks sorting and looks wrong everywhere. Spending one bit avoids all of it.

Timestamp (41 bits). 2^41 milliseconds = 2.2 × 10^12 ms ≈ 69.7 years. Measured from a custom epoch — the date the system was deployed — rather than 1970, so the full 69 years is ahead of you rather than half spent. Milliseconds rather than seconds because the sequence field must not overflow within one tick.

Datacentre (5) and machine (5) bits. 2^5 = 32 datacentres × 32 machines = 1,024 generator nodes. The split is a convention, not a rule: a system with one datacentre and many machines should spend all 10 bits on the machine identifier for 1,024 machines. Say that out loud — it shows you understand the layout is a budget rather than a formula.

Sequence (12 bits). 2^12 = 4,096 identifiers per millisecond per node.

The rate it supports

4,096 per millisecond × 1,000 ms = 4.096 million identifiers per second per node

× 1,024 nodes = ~4.2 billion per second cluster-wide

Against a requirement of 10,000 per second, that is five orders of magnitude of headroom on a single node. This is the arithmetic to state, because it converts "Snowflake is fast" into a comparison with the requirement.

What happens on overflow

If a node generates more than 4,096 identifiers in one millisecond, the sequence wraps. The correct behaviour is to wait until the next millisecond and continue — a delay of under a millisecond, invisible to callers. Silently wrapping would issue duplicates, so this branch must exist. Interviewers ask about it.

Why this satisfies the requirements

• Unique: two identifiers can only collide if they share a timestamp, a datacentre, a machine, and a sequence number — impossible, given each machine's sequence is local and monotonic within a millisecond.
• No coordination: every node generates locally with no network call. Nothing is in the critical path.
• Time-sortable: the timestamp is in the high bits, so sorting identifiers sorts by creation time — to within a millisecond, and within one millisecond ordering is by node and sequence rather than by true arrival order. That "roughly sortable" caveat is worth stating; it is not a total order over real time.
• 64 bits: fits a BIGINT, sorts natively, keeps B-tree inserts at the right edge.