Unique ID Generation (Distributed Systems)

must-know senior · part of Skills & Topics · Senior SWE Roadmap · related: Database Sharding & Replication · Consistent Hashing · question form: Design a Unique ID Generator

Why this is hard

On a single node, generating a unique ID is trivial: an auto-increment counter behind the DB’s own locking. The problem only gets interesting once multiple nodes — app servers, DB shards, regions — must each mint IDs independently, at high throughput, with no per-request coordination.

“No per-request coordination” is the load-bearing constraint. If every ID request has to round-trip to a central authority (“give me the next number”), that authority becomes the throughput ceiling for the entire system and a single point of failure just to hand out integers. Whatever scheme you pick has to let a node generate an ID using only information it already has locally.

At the same time, three properties are usually all wanted together, and they pull against each other:

• Uniqueness: no two nodes, ever, under any timing or network condition, produce the same ID.
• Rough time-ordering: IDs should trend upward with time, not just be unique. Two reasons this matters:
  • Product-level: chat messages, feed items, order history often sort/paginate by ID as a cheap proxy for recency instead of paying for a separate indexed created_at column.
  • Storage-level: relational DB primary keys are almost always backed by a B-tree. Inserting keys in monotonically increasing order appends cleanly at the right edge of the tree. Inserting keys in random order (a random UUID, say) forces the DB to find the right spot somewhere in the middle of already-written pages, causing constant page splits, more disk I/O, and worse cache locality — the “index locality” problem. Time-ordered IDs sidestep this.
• Small, cheap, fast to generate: ideally a fixed-width integer, generated by a local computation, not a network call.

Every approach below is a different point on the tradeoff between how strong a uniqueness guarantee you get, how much coordination it costs, how well it sorts, and how big the ID is.

UUID

A UUID (Universally Unique Identifier) is a 128-bit value, conventionally written as 32 hex digits in five dashed groups (xxxxxxxx-xxxx-Mxxx-Nxxx-xxxxxxxxxxxx). Collision probability is negligible by design — no coordination of any kind is needed, any node can generate one from purely local state.

flowchart TD
    subgraph V4["UUIDv4 — 128 bits, fully random"]
        direction LR
        A1["48 random bits"] --> A2["4-bit version = 0100"] --> A3["12 random bits"] --> A4["2-bit variant"] --> A5["62 random bits"]
    end
    subgraph V7["UUIDv7 — 128 bits, time-ordered prefix"]
        direction LR
        B1["48-bit Unix timestamp (ms)"] --> B2["4-bit version = 0111"] --> B3["12 bits: sub-ms counter / random"] --> B4["2-bit variant"] --> B5["62 random bits"]
    end

• UUIDv4 (random): the version most people mean by default “a UUID.” Every bit outside the 4-bit version and 2-bit variant fields is random. With 122 effectively-random bits, the birthday-paradox collision risk is astronomically low even at billions of IDs. The cost: fully random means not sortable, and it’s the worst case for B-tree index locality — every insert lands at a random point in the index, causing the page-split problem described above at scale.
• UUIDv7 (time-ordered, RFC 9562, standardized 2024): the modern answer to that exact problem. The high 48 bits are a Unix millisecond timestamp, so UUIDs generated later sort after UUIDs generated earlier — index-friendly, append-mostly inserts, same as an auto-increment column, while remaining fully randomly generated (no coordination) below the timestamp prefix. Postgres 18, MySQL, and most major UUID libraries now support v7 natively. If you’re choosing a UUID variant for a primary key today, v7 is the correct default — v4 mainly makes sense for exposed tokens where you specifically don’t want any information (like creation time) leakable from the ID.

General UUID tradeoffs versus the alternatives below: 128 bits is 16 raw bytes (or 36 characters as a string) — double an 8-byte bigint / Snowflake int64. At billions of rows, that’s real extra storage in the primary key, every secondary index that includes it, and every replica — and UUIDs are not pleasant to type or read compared to a short decimal ID.

Database auto-increment

The simplest possible scheme on a single database: an AUTO_INCREMENT/SERIAL column, strictly monotonic, trivially sortable, zero application logic. It falls over the moment there’s more than one writer minting IDs for the same logical table — which is exactly what sharding requires (see Database Sharding & Replication).

sequenceDiagram
    participant App
    participant ShardA as Shard A (own auto_increment)
    participant ShardB as Shard B (own auto_increment)

    App->>ShardA: INSERT order (id auto-assigned)
    ShardA-->>App: id = 1001
    App->>ShardB: INSERT order (id auto-assigned)
    ShardB-->>App: id = 1001
    Note over ShardA,ShardB: Both shards independently reached id 1001.<br/>Any merge — replication, analytics, a cross-shard<br/>join, using id as a cache key — now has a collision.

Each shard’s counter starts at 1 and climbs independently, with zero visibility into any other shard’s counter. Two orders on two different shards can both legitimately be “order #1001,” which breaks the moment you need to treat the ID as globally unique — merging data for analytics, using it as a cache key, exposing it in a URL, replicating cross-shard.

Workaround — increment by N with a per-shard offset (popularized by Flickr): configure shard k (of N total shards) with auto_increment_increment = N and auto_increment_offset = k. Shard 1 only ever emits IDs ≡ 1 (mod N): 1, N+1, 2N+1, … Shard 2 only ever emits ≡ 2 (mod N), and so on. No two shards can ever produce the same value, and no coordination is needed between shards at insert time — the non-collision is baked into which residue class each shard is statically assigned.

Limits of this workaround:

• N is baked into the scheme. Adding a new shard means either burning an unused residue class you provisioned in advance, or reconfiguring every existing shard’s offset — a live, risky, coordinated cutover.
• Loose ordering only. IDs are monotonic within a shard, but shard A’s 1001 and shard B’s 1002 say nothing about which was created first — you get a partition into interleaved ranges, not a real global clock.
• Every ID still costs a real DB write to the counter, unless you add block allocation on top: each app server requests a batch of, say, 1000 IDs from the DB at once and hands them out from memory locally, refilling before it runs out. This cuts DB round-trips by ~1000x; the cost is that any IDs left unused in a block when a server crashes are simply skipped — fine, since gaps are harmless and uniqueness/ordering are unaffected, but worth naming explicitly if asked.

Twitter Snowflake

The industry-standard answer: a 64-bit integer (fits a standard bigint, half the size of a UUID), generated entirely locally after a one-time startup configuration step, roughly time-ordered, unique across the whole fleet without a shared counter.

flowchart LR
    S["1 bit<br/>sign, always 0"] --> T["41 bits<br/>timestamp (ms since custom epoch)<br/>~69 years of range"] --> DC["5 bits<br/>datacenter ID (0-31)"] --> M["5 bits<br/>machine ID (0-31)"] --> SEQ["12 bits<br/>sequence (0-4095)<br/>resets every ms"]

Field by field:

• 1 sign bit, always 0 — keeps the value a positive signed 64-bit integer, since many languages/DBs handle unsigned 64-bit poorly.
• 41-bit timestamp: milliseconds since a custom epoch chosen for the system (Twitter’s is 1288834974657, i.e. Nov 4 2010), not Unix epoch 1970. 2^41 ms is about 69 years of usable range — picking a recent custom epoch instead of 1970 matters because it doesn’t burn decades of that budget before the system even launches.
• 10 bits of machine identity, conventionally split into 5 bits datacenter ID (0–31) and 5 bits machine/worker ID (0–31): up to 1,024 independent generator processes, each with a distinct identity.
• 12-bit sequence number: a per-machine, per-millisecond counter, 0–4095 — the same machine can mint up to 4,096 distinct IDs within the same millisecond before it has to wait for the clock to tick forward.

Throughput ceiling: 4,096 IDs/ms/machine × 1,000 ms/s = ~4.1M IDs/sec per machine; × up to 1,024 machines ≈ north of 4 billion IDs/sec system-wide, in theory — in practice bounded by however many generator processes you actually run.

Where coordination actually happens: assigning each generator process a unique (datacenter_id, machine_id) pair. This is done once, at process startup — via static config, or a coordination service like ZooKeeper handing out an unused worker ID on boot — never on the per-ID hot path. That’s the property that makes Snowflake genuinely “coordination-free” in the sense that matters for throughput: the request path that actually mints an ID touches nothing but local memory and the local clock.

Ordering: because the timestamp occupies the highest bits, IDs generated by the same machine are strictly increasing. Across different machines, ordering is only approximate — two machines minting in the same millisecond interleave in an order that isn’t necessarily their true wall-clock order, and clock skew between machines adds further slop. That’s fine for feed/timeline “recent-ish” sorting and, crucially, is still monotonic enough per-writer to give the same B-tree index-locality benefit as an auto-increment column.

Worked example: two IDs, same machine, same millisecond

Composition formula (bit positions from the layout above):

id = (timestamp << 22) | (datacenter_id << 17) | (machine_id << 12) | sequence

Take timestamp_since_epoch = 100 (ms), datacenter_id = 1, machine_id = 1, generating two IDs back to back within the same millisecond:

Step	timestamp	datacenter	machine	sequence	Computation	id
1st ID this ms	100	1	1	0	100×2²² + 1×2¹⁷ + 1×2¹² + 0	419,565,568
2nd ID this ms	100	1	1	1	100×2²² + 1×2¹⁷ + 1×2¹² + 1	419,565,569

Same timestamp, same machine identity, sequence bumped by one — the two IDs differ by exactly 1 and are still strictly increasing. The next millisecond, sequence resets to 0 and the timestamp component advances instead.

flowchart TD
    Start([generate_id called]) --> Now[now = current_time_ms]
    Now --> Cmp{now == last_timestamp?}
    Cmp -- same ms --> Inc[sequence = sequence + 1 mod 4096]
    Inc --> Overflow{sequence wrapped to 0?}
    Overflow -- yes, exhausted this ms --> Wait[busy-wait for next ms]
    Wait --> Now
    Overflow -- no --> Compose
    Cmp -- new ms --> Reset[sequence = 0]
    Reset --> Compose[id = timestamp shl 22 or dc shl 17 or machine shl 12 or sequence]
    Compose --> Store[last_timestamp = now]
    Store --> Done([return id])

If more than 4,096 IDs are requested by one machine within a single millisecond, the sequence counter wraps back to 0 — the generator has to busy-wait until the clock actually advances rather than reuse a sequence value, or it would collide with an ID it already handed out this millisecond.

Clock skew and rollback risk

Snowflake’s uniqueness guarantee depends on reading a monotonically-advancing system clock. If NTP steps the clock backward — a correction, a leap second, a misbehaving hypervisor — a machine could compute a now that’s less than its own last_timestamp, which risks generating an ID smaller than (or colliding with) one it already issued.

flowchart TD
    Now[now = current_time_ms] --> Check{now less than last_timestamp?}
    Check -- no, clock ok --> Proceed[compose id normally]
    Check -- yes, clock moved backward --> Policy{generator policy}
    Policy -- wait it out --> WaitOut[sleep until now >= last_timestamp,<br/>then proceed]
    Policy -- error out --> ErrorOut[reject request / raise alarm,<br/>refuse to generate]
    Policy -- logical clock bit --> Hybrid[bump a spare logical-epoch bit<br/>so id stays monotonic despite clock dip]

How real systems handle it:

• Wait it out: for small backward jumps, sleep until now catches back up past last_timestamp, then proceed — this is what Twitter’s reference implementation does. Simple, correct, but a generator can briefly stall.
• Error out: for a large backward jump (past some configured threshold), refuse to generate and raise an alarm instead of blocking indefinitely — a multi-hour clock misconfiguration shouldn’t turn into a multi-hour outage of silent hangs.
• Mitigate at the source: run NTP in slew mode (gradual correction) rather than step mode (instant jump) on any host doing ID generation, and alert on drift before it becomes an application-visible problem.
• Logical clock bit: some reimplementations steal a spare bit as a generation/epoch counter that increments whenever a backward jump is detected, so (logical_epoch, timestamp) stays monotonic even though raw wall-clock time briefly regressed. Not in Twitter’s original design, but a reasonable answer to “how would you make this bulletproof.”

Ticket server pattern

A dedicated, centralized service whose only job is handing out unique IDs — typically just a DB table with an auto-increment column, exposed as a tiny service (REPLACE INTO Tickets ...; SELECT LAST_INSERT_ID();). Flickr popularized this: their “ticket servers” were literally MySQL instances used for nothing but minting IDs.

Pros: trivially strict monotonic integer IDs, tiny (fits a bigint), dead simple to reason about, and — unlike the sharded-auto-increment workaround — the number of application shards is irrelevant, since IDs come from one place.

Cons: every single ID request in the system, from every service, round-trips to this one component. If it’s down, every write path anywhere that needs a fresh ID stalls — a large blast radius for something conceptually as simple as “hand out a number.” It’s also a hard throughput ceiling: bound by whatever one DB instance can do.

Making it HA:

flowchart TD
    C1[Client] --> LB{Load balancer / failover}
    C2[Client] --> LB
    LB --> T1[("Ticket Server A<br/>increment = 2, offset = 1<br/>emits 1, 3, 5, 7 ...")]
    LB --> T2[("Ticket Server B<br/>increment = 2, offset = 2<br/>emits 2, 4, 6, 8 ...")]

• Run two or more instances, each configured with a distinct auto_increment_increment/auto_increment_offset, so one only ever emits odd numbers and another only even — the same residue-class trick as sharded auto-increment, just applied at the ID-service tier instead of the business-data tier. Clients round-robin or failover between instances.
• Alternative: pre-allocate non-overlapping ID ranges to each instance via a coordination layer (ZooKeeper/etcd leases), refilling before exhaustion.
• Worth stating explicitly in an interview: push HA far enough on a ticket server and you’ve basically reinvented Snowflake, just with the machine-identity assignment done as a full DB write per instance instead of a one-time config value — a useful observation for showing you understand why Snowflake is designed the way it is, not just that it exists.

Comparison

Approach	Uniqueness	Sortable / time-ordered	Coordination needed	Size	Notes
UUIDv4	Probabilistic (collision astronomically unlikely)	No — fully random	None, ever	128 bits	Worst case for B-tree index locality
UUIDv7	Probabilistic	Yes, ms resolution	None, ever	128 bits	Modern default for new PKs needing UUIDs
DB auto-increment (single writer)	Strict	Strict	Every ID = a DB write	~64 bits	Doesn’t scale past one writer
Auto-increment + shard offset	Strict within scheme	Loose (per-shard monotonic only)	One-time, per-shard config	~64 bits	Shard count baked into the scheme
Snowflake	Strict per machine, effectively unique fleet-wide	Rough, ms resolution	One-time, at generator startup	64 bits	Industry-standard default
Ticket server	Strict	Strict	Every ID = a request to the service	~64 bits	Simple; SPOF/throughput ceiling unless made HA

Interview angles

• Be ready to derive the Snowflake bit layout live, including why each field is the size it is (why 41 bits of timestamp and a custom epoch instead of 1970, why sequence resets per millisecond, why datacenter/machine ID assignment is a one-time startup cost and not per-request).
• “Why not just use a UUID everywhere?” — index locality is the strongest technical argument against random UUIDs as primary keys, plus the raw size overhead at scale (2x an int64, compounded across every index and every replica). For non-PK uses — idempotency keys, trace/request IDs — UUIDs are fine and simpler, since they need zero shared infrastructure.
• “What happens when the clock on a Snowflake node jumps backward?” — have at least one concrete mitigation ready (wait-it-out with a threshold before erroring), not just “that would be bad.”
• This topic almost never appears alone — it shows up as “how do you generate order IDs / message IDs / event IDs at scale” inside nearly every HLD. Default answer: Snowflake, then justify a deviation (ticket server if you specifically need strict global sequencing for something like a display order that must never skip a number; UUID/v7 if the ID is never a hot-path DB primary key).
• Design a Unique ID Generator is the dedicated HLD prompt this expands into. The sharded-auto-increment failure mode is really a Database Sharding & Replication problem wearing an ID-generation hat — worth naming the connection if it comes up.

My Notes