Design a unique ID generator

Every order, payment, chat message and post needs a name the moment it is created, before it is written anywhere. On one database an auto-increment column does the job. Spread the data over hundreds of shards in three regions, mint two million IDs a second at the stroke of midnight on the first day of a festival sale, and the obvious answers break: one shared counter becomes the bottleneck and the single point of failure, random UUIDs double the size of every key and scatter inserts across your indexes, and timestamps on their own collide. In this problem you design the ID generator that every team in a large product shares: 64-bit IDs that are unique without any coordination per ID, sort roughly by time, arrive in well under a millisecond, and keep coming when almost everything else is broken.

Understand the problem

An ID generator looks like a one-line function. Most of the interview is about the three questions hiding behind it: what “unique” costs, what “ordered” means, and which clock you trust. Pin down the shape of the ID before you draw boxes, because here the bit layout is the design.

Functional requirements

1. Services should be able to get a new ID, or a batch of IDs, in one call. The order service asks for one ID per order; a bulk import asks for 10,000. Every ID is unique across all services, regions and time.
2. Services should be able to sort and page by ID. An ID minted later should almost always be larger, so “newest first” is ORDER BY id DESC and a feed cursor is just the last ID you saw.
3. Services should be able to read the creation time back out of an ID, and build the smallest ID for a given moment, so “orders placed on Diwali” becomes a range scan on the primary key.
4. Operators should be able to add and remove generators freely — autoscaling, rolling deploys, a new region — without editing config by hand and without ever risking a duplicate.

Non-functional requirements

• Uniqueness is absolute. Zero duplicates, ever, in any region. A duplicate order ID can merge two customers’ orders or make an upsert silently overwrite a payment. It is a correctness bug, not a quality metric.
• Fits a signed 64-bit integer. bigint in PostgreSQL and MySQL and long in Java are signed, so the top bit stays 0 and you have 63 usable bits. That is half the size of a UUID in every primary key, index and foreign key.
• Roughly time-ordered (k-sorted). IDs from one generator strictly increase. IDs from different generators are in time order unless they were minted closer together than the clock skew between the machines: target 10 ms, hard bound 1 s. Strict global order is not required.
• High throughput. About 2M IDs/s at peak across the fleet (derived below). One generator must manage millions a second, so it is never the bottleneck.
• Low latency. Minting in memory takes well under a microsecond; over the network, p99 under 1 ms within a zone.
• Very high availability. 99.999% for “give me an ID”, about 5 minutes a year, because when IDs stop, every write in the company stops.
• Long life. The layout must last at least 50 years without a migration.
• Regional independence. A region cut off from the others keeps minting IDs that can never clash with theirs.

Out of scope

• A strict total order across the whole fleet. It needs one sequencer for every ID; it comes back as a follow-up.
• Secrets. Session tokens, password-reset links and API keys need at least 128 bits from a cryptographically secure random generator. Our IDs are guessable by design.
• Gapless numbering. An invoice series that must have no holes needs a transactional counter per series. Ordinary database sequences cannot promise it either: PostgreSQL never rolls back a value once handed out.
• Short, human-friendly codes such as booking references. Also a follow-up.

The set-up

Plan the approach

Agree on the ID’s shape first: 64 bits, time first. Then build the simplest generator that meets each functional requirement, ending with a regional ID service whose pods lease worker numbers. Spend most of your time in the deep dives: choosing the scheme, budgeting the bits, worker numbers, clocks, library versus service, and what IDs do to databases and to privacy.

Core entities

• ID. A signed 64-bit integer: 1 sign bit (always 0), 41 bits of milliseconds since a custom epoch, 3 bits of region, 7 bits of worker and 12 bits of sequence.
• Layout. The epoch (2026-01-01 00:00 UTC), the field widths and a version number. Every generator and every decoder shares it; changing it is a migration.
• Generator. One process that mints IDs. It holds its region and worker number, the last timestamp it used and its sequence counter, all in memory.
• Worker lease. A record in the registry: region, worker number, owning pod and valid_until, the last millisecond the owner may stamp into an ID.

{
  "key": "/idgen/r1/w37",
  "owner": "id-svc-7f2c9",
  "valid_until_ms": 25850400123,
  "revision": 81723
}

API

The service speaks gRPC; it is shown as HTTP for readability.

POST /v1/ids:next
Content-Type: application/json

{ "count": 3, "caller": "order-service" }

{
  "ids": ["108421920055775237", "108421920055775238", "108421920055775239"],
  "layout_version": 1
}

IDs travel as strings in JSON. JavaScript numbers are exact only up to 2⁵³, and every ID minted more than about 25 days after the epoch is bigger than that, so a browser would silently round it to a neighbouring ID. Discord’s API returns its 64-bit IDs as strings for the same reason. caller is only for metrics and quotas; it never changes the ID.

GET /v1/ids/108421920055775237

{
  "id": "108421920055775237",
  "created_at": "2026-10-27T04:30:00.123Z",
  "region": 1,
  "worker": 37,
  "sequence": 5
}

The same functions live in a small client library, so services decode IDs locally without a call:

id, err := idgen.Next(ctx)        // one ID
ids, err := idgen.NextN(ctx, 500) // a batch
t := idgen.Time(id)               // 2026-10-27 04:30:00.123 UTC
lo := idgen.MinIDAt(t)            // smallest possible ID minted at that millisecond

Back-of-envelope estimates

These numbers decide the bit layout and the size of the fleet. (For the method, see back-of-envelope estimation.)

Volume. Assume 30B chat messages, 8B posts, likes and comments, and 2B orders, payments and other records a day: 40B IDs a day. 40B ÷ 86,400 s ≈ 463k IDs/s on average. Midnight at a festival sale or the last over of a cricket final pushes about 4× that: 463k × 4 ≈ 1.85M, so plan for 2M IDs/s.

Time bits. 41 bits of milliseconds is 2⁴¹ ms ≈ 2.2 × 10¹² ms ≈ 69.7 years. From an epoch of 1 January 2026, that runs out in September 2095. Counting from the Unix epoch instead would waste 56 of those years before the first ID.

Sequence bits. 12 bits is 2¹² = 4,096 IDs per millisecond per generator, or 4.1M IDs/s. In theory one generator could mint the whole peak.

Generators. Three regions run active-active, and two must carry everything if one fails: 2M ÷ 2 = 1M IDs/s per region. Callers average 2 IDs per call, so 500k calls/s. Budget 50k gRPC calls/s per pod at about half CPU: 500k ÷ 50k = 10 pods, doubled for a lost zone and rolling deploys = 20 pods per region. That uses 20 of the 2⁷ = 128 worker numbers each region gets, leaving room for deploy surges and for crashed pods whose leases have not yet run out.

Load per generator. 1M ÷ 20 = 50k IDs/s, or 50 per millisecond: about 1.2% of the 4,096 a millisecond allows. The sequence has plenty of headroom.

Storage. 40B a day × 365 ≈ 14.6 trillion IDs a year. Each 64-bit ID saves 8 bytes over a 128-bit UUID wherever it is stored: 14.6T × 8 B ≈ 117 TB a year for every copy — the primary key, each index that contains it, each foreign key and each replica.

Registry load. 60 pods renewing a lease every 30 s is 2 writes a second. The registry is idle.

High-level design

Build the design one requirement at a time. By the end it works in every region, but nothing has yet been hardened against bad clocks or zombie pods.

Services should be able to get a new ID, or a batch

Start with the idea that makes everything else possible: an ID does not have to come from a shared counter if it is built from parts that are already unique. A generator knows the time, knows its own number, and can count. Put the time in the high bits, the generator’s number in the middle and a counter in the low bits, and two generators can only collide if they share a number — which the rest of the design makes impossible.

Put the generator behind a small ID service in each region: stateless pods, each with its own worker number, called over gRPC by the order, chat and post services. For now, worker numbers come from a config file.

The generator itself is a few lines. Here it is in Go:

// 1 sign bit (0) | 41 bits ms since epoch | 3 region | 7 worker | 12 sequence
type Generator struct {
	mu     sync.Mutex
	node   int64 // region<<7 | worker: 10 bits, unique among live generators
	lastMs int64 // timestamp of the last ID, ms since epochMs
	seq    int64
}

func (g *Generator) Next() (int64, error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	now := time.Now().UnixMilli() - epochMs
	if now < g.lastMs {
		return 0, ErrClockMovedBack // improved in the deep dive on clocks
	}
	if now == g.lastMs {
		g.seq = (g.seq + 1) & 0xFFF // 12 bits
		if g.seq == 0 {             // 4,096 IDs already used this millisecond
			for now <= g.lastMs {
				now = time.Now().UnixMilli() - epochMs // spin to the next one
			}
		}
	} else {
		g.seq = 0
	}
	g.lastMs = now
	return now<<22 | g.node<<12 | g.seq, nil
}

Three details matter. The lock is held for about 100 nanoseconds and never across I/O. The sequence restarts at 0 every millisecond, and when all 4,096 values are used the generator waits for the next millisecond — exactly what the original Snowflake IdWorker does. And if the clock reads earlier than the last ID, the generator refuses rather than risk a duplicate; the deep dive on clocks does better. A batch, NextN(500), runs the same logic 500 times under one lock: about 50 µs and one round trip.

Services should be able to sort and page by ID

Because time sits in the high bits, comparing two IDs as plain numbers compares their creation times. The promise is precise:

• Per generator: strictly increasing. Each ID is larger than the one before, always.
• Across generators: k-sorted. Two IDs from different machines are in time order unless they were minted closer together than the clock skew between those machines.

Twitter’s Snowflake README promised a bound of 1 s and aimed for tens of milliseconds; with a healthy time service, a few milliseconds is realistic within a region.

For a feed, a chat history or an order list, k-sorting is all you need: two messages sent 3 ms apart by different people have no meaningful order anyway. ORDER BY id DESC LIMIT 20 gives newest first, and the last ID on a page is a stable cursor for the next — see offset vs keyset pagination.

Why not a strict global order? One sequencer stamping every ID is a throughput ceiling, a single point of failure and, from other regions, a round trip of tens of milliseconds per ID. Where order really matters, it matters within one chat or one account, and a counter per entity is cheap (see the follow-ups).

Services should be able to read the creation time back out of an ID

Decoding is shifts and masks — no lookups and no calls — which is why it lives in the client library.

Three uses pay for this:

• Debugging. An ID in a log line says when and where it was made: region 1, worker 37, 10:00:00.123.
• Time-range queries on the primary key. “Orders created on 27 October” is WHERE id >= MinIDAt(start) AND id < MinIDAt(end), an index range scan with no separate created_at index.
• Archiving. A table range-partitioned by ID is in effect partitioned by month, so dropping old data means dropping old partitions (see table partitioning).

One caution: the timestamp is the generator’s clock at minting time, not the business time of the event. Keep a real created_at column where business time matters — for example, a record made on a phone offline and synced hours later.

Operators should be able to add and remove generators freely

A config file of worker numbers works for five long-lived servers. It fails with pods that autoscale, restart and reschedule: someone copies a config, or a new pod inherits a number from one that is not quite dead, and two generators mint identical IDs. Move the assignment into a registry — a small etcd cluster in each region (see ZooKeeper and etcd) — and have every pod lease a worker number at start-up:

1. List the worker keys for its region and pick a number whose lease has expired.
2. Claim it with a compare-and-swap that fails if another pod got there first.
3. Renew the lease every 30 s for as long as it runs, and release it on a clean shutdown.

Twitter’s Snowflake did the same with ZooKeeper, choosing worker numbers at start-up. The registry is off the hot path: a pod touches it at start-up and twice a minute, never per ID.

Add the region to the ID as well — 3 bits for up to 8 regions — and each region needs only its own registry. Worker 37 in Mumbai and worker 37 in Hyderabad differ in their region bits, so their IDs cannot collide, and nothing ever crosses regions (see multi-region and active-active).

You now have a working design: unique, sortable, decodable IDs from a stateless service, with worker numbers assigned automatically. The deep dives are about what breaks it — a paused pod, a clock that jumps back, a database that hates your keys — and whether this is even the right scheme.

Deep dives

Which ID scheme should we use?

There are six serious families. The right one depends on how many bits you can afford, whether you need time order, and how much coordination you can tolerate per ID.

Bad: one database’s auto-increment. Compact, strictly ordered and already there. But every ID now needs a write to one primary, so the whole company’s insert rate is capped by one machine, and while it fails over nothing gets created — a textbook single point of failure. Two primaries can split the space with a step and an offset — MySQL’s auto_increment_increment = 2 with offsets 1 and 2 gives one server the odd numbers and the other the even ones — which removes the single point of failure but not the write per ID, and time order is lost between the two.

Good: Flickr-style ticket servers. Flickr made the central counter cheap: a dedicated MySQL server with a one-row table per sequence, bumped with REPLACE INTO Tickets64 (stub) VALUES ('a') and read back with SELECT LAST_INSERT_ID(). Two such servers split odd and even numbers, and clients round-robin between them; it ran in production from 2006. You gain simplicity and compact IDs. You pay a network round trip and a database write per ID, and the halves drift apart — Flickr reported a few hundred thousand more odd IDs than even — so IDs are not in time order across servers.

Good: segment (range) allocation. Take the ticket server’s write off the hot path. Each app server reserves a whole block — 1,000 or 10,000 IDs — with one UPDATE … SET max_id = max_id + step, then hands them out from memory. PostgreSQL’s sequence CACHE option is the same idea inside one database: each session preallocates values, unused ones become holes when the session ends, and values from different sessions interleave. With double buffering, a server fetches its next block in the background when the current one is 80% used, so callers never wait on the database.

You gain 64-bit IDs, one database write per thousand IDs and a design anyone can debug. You pay with gaps after every crash, no time order across servers, and a database that must answer at least every few seconds.

Good: random UUIDv4. 122 random bits, generated anywhere with no coordination at all. Collisions are not the problem: at 14.6 trillion IDs a year, ten years is n ≈ 1.46 × 10¹⁵ IDs, and the birthday bound puts the chance of even one duplicate at about n² ÷ 2¹²³ = (1.46 × 10¹⁵)² ÷ 1.06 × 10³⁷ ≈ 2 × 10⁻⁷. The problems are size — 128 bits, 36 characters as text — and randomness: each insert lands on a random leaf of the primary-key B-tree. RFC 9562 puts the difference in index locality between random and time-ordered keys at an order of magnitude or more.

Great, if you can afford 128 bits: UUIDv7 or ULID. Both put a 48-bit Unix millisecond timestamp first and fill the rest with randomness: UUIDv7 keeps 74 random bits after its version and variant bits, and ULID has 80 random bits and a 26-character Crockford base32 text form. They sort by time and need no worker numbers at all, and UUIDv7 is a 2024 IETF standard with growing database support. The cost is 16 bytes everywhere and a timestamp anyone can read.

Great for our requirements: Snowflake-style 64-bit IDs. Time, generator and sequence in 63 bits. Twitter built Snowflake in 2010 to replace MySQL auto-increment with something uncoordinated, roughly sortable and no wider than 64 bits, after rejecting ticket servers (no ordering without a resync routine), UUIDs (128 bits) and ZooKeeper sequential nodes (too slow, and coordination would lower availability). You pay with worker-number management and a dependence on clocks — the next three deep dives.

A last variant hides the generator inside the database. Instagram, sharding PostgreSQL, wanted Snowflake’s properties without new moving parts. Each of several thousand logical shards is a PostgreSQL schema, and every sharded table’s ID column defaults to a small PL/pgSQL function: 41 bits of milliseconds since a custom epoch, 13 bits of logical shard ID and 10 bits of a per-table sequence modulo 1,024 — up to 1,024 IDs per shard per millisecond. The shard is inside the ID, so any service can route a row from its ID alone. Two details are worth noticing if you copy it. 41 + 13 + 10 = 64, so the time field includes the sign bit: in a signed bigint the IDs turn negative once 2⁴⁰ ms ≈ 34.8 years have passed, around 2046 for that epoch. And the sequence wraps instead of waiting, so a 1,025th insert into one table on one shard in the same millisecond reuses an ID; the primary key turns that rare case into a failed insert rather than silent corruption.

How do we spend 63 bits?

Every Snowflake-style layout divides the same 63 bits between three fields, and each field buys exactly one thing:

• Time bits × tick size = lifetime. 41 bits of 1 ms ≈ 69.7 years; 39 bits of 10 ms ≈ 174 years.
• Generator bits = how many generators may run at once. 10 bits = 1,024.
• Sequence bits ÷ tick = peak rate per generator. 12 bits per 1 ms = 4,096,000 IDs/s.

Read the figure as a set of trades:

• Sonyflake stretches the tick to 10 ms and gives 16 bits to the machine — by default the low 16 bits of its private IP address — so it lasts 174 years and allows 65,536 machines. Each one manages only 2⁸ = 256 IDs per 10 ms, 25,600 a second; its README suggests running several instances per host if you need more.
• A library in every pod needs thousands of generator numbers. Moving 3 bits from sequence to node gives 8,192 generators at 512 IDs per millisecond each — still 512k a second, far more than any single pod needs.
• Our regional service needs few generators but wants them grouped by region, so the 10 node bits split into 3 for region and 7 for worker.

Discord, which gives every object a Snowflake-style ID, uses a 42-bit timestamp from a 2015 epoch, 5-bit worker and 5-bit process fields and a 12-bit increment: all 64 bits, which works because its systems treat IDs as unsigned numbers or strings. Four smaller choices matter as much as the widths:

• Pick a recent custom epoch. Twitter’s starts in November 2010, Discord’s on 1 January 2015, ours on 1 January 2026. Counting from 1970 would burn 56 of your 69.7 years before you mint anything.
• Time always goes first, or IDs do not sort by time. Whether the generator or the sequence comes next only changes the order within one millisecond.
• Never shard by id % N. The sequence restarts at 0 every millisecond, so a quiet entity — a few new restaurants a second — gets sequence 0 on almost every ID, and its low bits are nearly all zero. id % 64 would send almost every row to shard 0. Hash the whole ID, or put the shard inside the ID as Instagram does (see database sharding).
• Version the layout. Keep the epoch and widths in shared config with a version number, so a later change can switch cleanly at a cut-over moment (see the follow-ups).

How do we hand out worker numbers without duplicates?

Two live generators with the same region and worker number mint identical IDs whenever they use the same millisecond — and because both restart their sequence at 0 every millisecond, that happens in the very first busy millisecond. Nothing downstream notices until an insert fails on the primary key or, worse, an upsert quietly overwrites someone else’s payment. Worker numbers are where this design is won or lost.

Bad: static config, hostnames or IP addresses. Fine for five servers that never move. In Kubernetes, pods are created and destroyed all day, and a copied config or a recycled hostname gives two pods the same number. Deriving the number from an IP address, as Sonyflake does by default, is unique only while addresses are — and a cluster hands a dead pod’s address to a new one quickly.

Good: leases in ZooKeeper or etcd, with a gap before reuse. Each pod claims a number with an ephemeral node or a key attached to a lease, renews it, and loses it when it stops renewing. That handles crashes cleanly. It does not handle zombies: a pod that is paused — a long garbage-collection pause, a frozen VM, a network partition that cuts it off from etcd but not from its callers — still believes it owns number 37 after its lease has expired and been granted to another pod.

Leaving a gap before a number is reused (a quarantine) shrinks the window, but a pause can always outlast any gap you choose.

Great: time-fenced leases. Make the ID’s own timestamp the fence. Alongside the owner, the registry stores valid_until: the last millisecond the current owner may stamp into an ID.

1. The owner never mints at or after valid_until. It checks the timestamp it is about to embed — not the time at which it last checked — so a pause anywhere in the call cannot smuggle a late timestamp into an ID. Renewal moves valid_until forward by compare-and-swap, and only while the pod still owns the key.
2. A new owner never mints at or before the old valid_until. When a pod claims number 37, it reads the previous valid_until and uses it as the floor for its own timestamps.

Now every ID from the old owner carries a timestamp below valid_until, and every ID from the new owner a timestamp above it. They cannot overlap, however long the zombie sleeps and whatever its clock says. Uniqueness rests on the registry’s compare-and-swap, not on timing; clocks only decide how soon a new owner can start. It is the fencing-token idea from distributed locking — worked through in design a distributed lock — except the token travels inside every ID.

Choose the lease length for availability, not tidiness. A pod that cannot renew before valid_until must stop minting, so an etcd outage longer than the lease becomes an ID outage. With 10-minute leases renewed every 30 s, etcd can be down for about 9 minutes before any pod is affected. The cost is that a crashed pod’s number stays locked for up to 10 minutes; with 128 numbers per region and 20 pods, even an hour of crash loops will not run the pool dry. A clean shutdown writes its last used timestamp as valid_until and frees the number immediately.

What happens when the clock goes backwards?

Wall clocks are not monotonic. A time daemon that finds the clock 25 ms fast may step it back. A VM resumed after a live migration may jump and then be corrected. A leap second can repeat a second on systems that do not smear it over the day. If the generator trusts the clock, it re-enters milliseconds it has already used, restarts the sequence at 0 and re-issues IDs it has already handed out. (The wider topic is clocks, ordering and conflict resolution.)

Bad: trust the wall clock. Duplicates for every millisecond that comes round again, usually with no error anywhere.

Good: refuse until the clock catches up. Snowflake’s original code throws an error while the clock is behind its last timestamp, and its README recommends running the time daemon in a mode that never moves the clock backwards. Sleep through small gaps (a few milliseconds) and fail fast on big ones, letting the health check take the pod out of rotation so callers retry another pod. You pay a stall, or a lost pod, per jump — but never a duplicate.

Great: a clock that never goes back, with limits. Let the generator keep its own clock, max(wall clock, last timestamp). When the wall clock falls behind, keep stamping the last millisecond and keep counting; when the sequence fills, borrow the next millisecond. RFC 9562 describes the same two moves for UUIDv7 generators: reuse the previous timestamp and increment the counter, or run the timestamp ahead of real time. Bound the borrowing: if the generator would be more than 1 s ahead of its wall clock, stop and alert, because that machine’s clock is badly wrong.

func (g *Generator) Next() (int64, error) {
	g.mu.Lock()
	defer g.mu.Unlock()
	wall := time.Now().UnixMilli() - epochMs
	now := max(wall, g.lastMs) // the generator's clock never goes back
	seq := int64(0)
	if now == g.lastMs {
		seq = (g.seq + 1) & 0xFFF
		if seq == 0 {
			now++ // sequence full: borrow the next millisecond
		}
	}
	if now-wall > maxLeadMs { // e.g. 1,000 ms ahead of the wall clock
		return 0, ErrClockBehind // fail loudly; the health check pulls this pod
	}
	if now >= g.validUntilMs {
		return 0, ErrLeaseExpired // the time fence from the worker-number deep dive
	}
	g.lastMs, g.seq = now, seq
	return now<<22 | g.node<<12 | seq, nil
}

Restarts are the subtle case. A generator keeps its last timestamp in memory and loses it when the process restarts. If the clock was stepped back 25 ms just before, a fresh process would happily mint those 25 ms again. The time fence already covers this: a restarted process takes a fresh lease, sets its last timestamp to the previous valid_until for that number, and waits until the wall clock passes it (failing if that would take more than a second). RFC 9562 recommends the same pattern for UUID generators with stable storage — periodically store a timestamp larger than any used so far, and start above it after a reboot.

Watch the clocks. Configure the time daemon to slew (speed up or slow down gradually) rather than step, except at boot. Export each pod’s offset from the time service, count backward jumps and borrowed milliseconds, and keep a pod out of rotation at start-up until its offset is under 5 ms. A bad clock should be an alert, not a mystery.

Should the generator be a library or a service?

The generator is a few dozen lines of code. The real question is where those lines run.

Good: a library in every application process. No network hop: an ID costs about 100 ns, and ID generation cannot be down while the application is up. But every process is now a generator with its own worker number. 3,000 application pods across the company is three times what 10 node bits allow, so you must move bits out of the sequence (the 41/13/9 layout), and every deploy re-leases thousands of numbers. Every host’s clock, and every language’s implementation, becomes your problem.

Good: a central ID service. A few dozen pods per region mint for everyone. Worker numbers stay few, clocks are watched in one place, and anything with a gRPC client can call it (see REST vs GraphQL vs gRPC). You pay about 0.3 ms per call and a new tier that must itself reach 99.999% — see availability and the nines.

Great: a regional service, with a smart client. Run the ID service in every region and zone, and give callers a thin client that:

• Spreads calls across pods with client-side load balancing, and retries on another pod after a 2 ms timeout. Retrying is always safe: an ID that was minted but never delivered is just a gap, never a duplicate.
• Buffers where volume is high. A chat server can keep 32 IDs in memory and refill when half empty, so most messages get an ID with no call at all. The price is that an ID records when it was minted, not when it was used — at 1,000 messages a second, 32 IDs last 32 ms, well inside the k-sort bound.
• Decodes locally, so Time(id) and MinIDAt(t) never need the service.

That keeps 20 generators per region, a fraction of a millisecond per call, and no database anywhere near ID minting.

What do our IDs do to the database?

An ID is written once and then lives in indexes for years, so its shape matters more there than anywhere else.

In a B-tree, increasing keys are cheap. PostgreSQL and MySQL keep primary keys in B-trees (see database indexes). When each new key is the largest so far, every insert goes to the rightmost leaf: one hot page in memory, pages filled almost full, and the old part of the index can stay on disk. Snowflake-style IDs from 60 generators are not perfectly sequential, but they land in a narrow band at the right edge and behave almost the same. UUIDv4 keys land on random leaves, so every leaf must be cached and pages split all over the index, half empty. That is the main reason not to use UUIDv4 as a clustered key — more in indexes in practice.

In a range-partitioned store, increasing keys are a hot spot. Spanner, Bigtable, HBase and similar systems split a table into key ranges and give each range to a server. A key that always increases sends every insert to the last range — Spanner’s schema guide makes avoiding it its first best practice — and that one server takes all 1M writes a second while the rest sit idle. Splitting the range does not help: the new last range is just as hot.

• Bad: ignore it. The table’s write capacity becomes one server’s.
• Good: lead the key with something else. Store messages under (chat_id, message_id) rather than message_id alone. Writes spread across chats, and each chat’s history is still one time-ordered range — usually the right data model anyway.
• Good: a hash prefix. Store (hash(id) % 64, id) as the key. Writes spread over 64 ranges; you pay with time-range scans that must read all 64 prefixes and merge them. Spanner also offers bit-reversed sequences, which reverse an integer’s bits so that consecutive values land far apart.
• Great, for these stores: a random key. If nothing scans by ID range, UUIDv4 spreads perfectly — Spanner’s own recommendation — and you can keep the Snowflake ID as an ordinary column for sorting.

Hash-partitioned stores such as Cassandra and DynamoDB hash the partition key anyway, so Snowflake IDs spread well as partition keys there, and inside a partition a time-ordered clustering key is exactly what you want (compare design a key-value store).

How do we stop IDs from leaking information?

Anything inside an ID is visible to whoever sees it. Ours contain a millisecond timestamp, a region and a worker number, and a sequence.

An order number that counts up tells a competitor your daily orders; a Snowflake ID in a profile URL tells anyone when the account was created, to the millisecond. Three rules:

• Use a separate public ID where it matters. Order pages, invoices and shareable links get their own identifier — random, or a short human-friendly code — mapped to the internal ID by a unique index. You pay with one more column and one more lookup.
• Or encrypt the ID. A keyed 64-bit block cipher, a form of format-preserving encryption, turns each ID into an unrelated-looking 64-bit number and back, with no lookup table. You pay with key management: rotating the key changes every public ID ever shown.
• Never use IDs as secrets. RFC 9562 says plainly that UUIDs must not be used as security capabilities, and ours are far easier to guess. Check authorisation on every read: GET /orders/:id must verify the order belongs to the caller, whatever the ID looks like.

The final design

The hot path is an application, a service and one ID pod’s memory; the registry and the time service sit beside it, not on it.

Follow one order through the system:

1. Lease. When an ID service pod starts, it claims a free worker number in its region’s etcd with compare-and-swap, takes the previous valid_until as its floor, and gets a lease that runs 10 minutes ahead.
2. Clock check. It reads its offset from the time service and reports ready only when the offset is under 5 ms and its wall clock has passed the floor.
3. Request. A shopper places an order; the request reaches the order service.
4. Mint. The order service’s client takes an ID from its small buffer or calls NextIds on a nearby pod. The pod mints from memory — its own clock, region and worker bits, sequence — and checks the time fence. A slow pod costs a 2 ms timeout and a retry elsewhere.
5. Store. The order row is inserted with the ID as its bigint primary key, an append at the right edge of the B-tree. Range-partitioned stores get a better leading key or a hash prefix.
6. Renew and observe. Every 30 s the pod renews its lease, moving valid_until forward; if it cannot, it stops minting before the lease runs out. Clock offset, backward jumps, borrowed milliseconds and lease failures feed metrics with alerts.
7. Respond. The app receives the order ID as a string, and the order page shows a separate public order code.

Check it against the requirements. Uniqueness rests on region bits, leases fenced by timestamp, and a sequence that never repeats within a millisecond. IDs are 63 bits and k-sorted to within clock skew. Twenty pods per region carry 1M IDs/s at about 1% of their sequence capacity. Nothing on the hot path touches etcd, the time service, another region or any database except the caller’s own, so ID minting survives almost anything short of losing every pod in a region.

What interviewers look for by level

Follow-up questions

What if IDs must be strictly increasing across the whole system?

First ask what for. Strict order almost always matters within something — one chat, one account’s ledger, one partition of a log — and a counter per entity gives it: a next_seq column bumped in the same transaction as the insert, or a partition leader assigning offsets. A truly global order needs a single sequencer: one leader, replicated with a consensus protocol so it survives failover (see consensus and leader election), which records “reserved up to N + 10,000” in its log and then hands out values one at a time from memory. You pay with a throughput ceiling of one machine, a pause on every leader election, and a cross-region round trip of tens of milliseconds for every region that is not the leader’s.

What if we must generate IDs offline on mobile devices?

Phones cannot lease worker numbers, and their clocks can be hours or years wrong. Let the device create a UUIDv4 — or a UUIDv7 if it needs local ordering — as a client ID for each record made offline. On sync, the server assigns the canonical Snowflake ID and keeps the client ID under a unique index, so a retried sync is recognised instead of duplicated; the client ID doubles as an idempotency key. Never order server-side data by a device’s timestamp; keep it as a separate “created on device” field.

What if we run out of worker numbers?

Find where they went first: leaked leases, crash-looping pods, or a team quietly embedding the library. Then trade bits: 2 bits taken from the sequence buy 4× the generators at a quarter of the per-generator rate, which our service at 1.2% sequence use can easily afford. Do it with a new layout version and a cut-over time, keeping the time field where it is: old and new IDs still sort together, and a decoder tells layouts apart by comparing an ID with the first one after the cut-over. If you genuinely need tens of thousands of independent generators — every pod, every device — the honest answer is 128-bit UUIDv7, which needs no worker numbers at all.

What if IDs must be short and human-friendly, like a booking code?

Use a separate code, not the 64-bit ID, which is 18 digits long. Eight characters of Crockford base32 — digits and letters without I, L, O and U, case-insensitive — give 32⁸ ≈ 1.1 trillion codes. Draw them at random from a secure generator and insert under a unique constraint: with 100 million live codes, a new one clashes 10⁸ ÷ 1.1 × 10¹² ≈ 0.009% of the time, so one retry is plenty. Add a check character so a mistyped code is rejected before any database lookup, and if codes only need to be unique among active bookings, recycle them after the trip. Random codes also reveal nothing about volume.

What if JavaScript clients lose precision above 2⁵³?

They will. A JavaScript Number is a 64-bit float, exact only up to 2⁵³ − 1 ≈ 9.0 × 10¹⁵. With 22 bits below the timestamp, every ID minted after the first 2³¹ ms ≈ 24.9 days of the epoch is larger, so JSON.parse silently rounds it to a different ID — and the user opens the wrong order. Send IDs as strings in every API, as Discord does, parse them as BigInt if the client must do arithmetic, and add a test that round-trips a real ID through your JSON layer.

How to say it in the interview

“I’ll design a shared ID generator: 64-bit IDs, unique across three regions with no coordination per ID, roughly sorted by time, about two million a second at peak, and available whenever anything else is.

I’d use a Snowflake-style layout. The sign bit stays zero, then 41 bits of milliseconds since a 2026 epoch — about 69.7 years — then 3 bits of region, 7 bits of worker, and a 12-bit sequence, so one generator can mint 4,096 IDs per millisecond. Time first means IDs sort by creation time, which keeps B-tree inserts at the right edge and makes ‘newest first’ a primary-key scan. Across generators they’re k-sorted to within clock skew. That’s fine for feeds and pagination; a strict global order would need a single sequencer, so I’d only add order per entity, where it matters.

The generators run as a small ID service in each region, about 20 pods, using roughly one percent of their sequence capacity. Each pod leases a worker number from etcd with compare-and-swap, and the lease carries a valid-until timestamp: the old owner never stamps an ID at or after it, and the new owner never at or before it. So even a paused zombie can’t create a duplicate, and etcd is never on the hot path.

For clocks, the generator never lets its own clock go backwards: it uses the larger of the wall clock and its last timestamp, borrows at most a second ahead, and otherwise fails and takes itself out of rotation. Time sync slews rather than steps.

Around the edges: IDs go to clients as strings because of JavaScript’s 2⁵³ limit; range-partitioned stores get a hash prefix or a better leading key; and anything public, like order numbers, gets a separate opaque ID, because ours reveal creation time and are never secrets.”

Concepts used in this design

• Back-of-envelope estimation — deriving 2M IDs/s, the pod count and the bit budget.
• Single point of failure — why one auto-increment database cannot mint every ID.
• Availability and the nines — what 99.999% allows, and why the hot path has no dependencies.
• Clocks, ordering and conflict resolution — clock skew, k-sorting and clocks that never run backwards.
• Consensus and leader election — what a strict global sequencer would really cost.
• ZooKeeper and etcd — leases and compare-and-swap for worker numbers.
• Distributed locking — leases, zombies and fencing tokens.
• Design a distributed lock — fencing applied end to end.
• Database indexes — why increasing keys make cheap B-tree inserts.
• Indexes in practice — UUIDv4 versus UUIDv7 as a primary key.
• Database sharding — why per-shard auto-increment collides, and routing by ID.
• Table partitioning — partitioning by ID range as partitioning by time.
• Offset vs keyset pagination — IDs as stable cursors.
• Idempotency — client-made IDs that make offline sync and retries safe.
• Multi-region and active-active — region bits and regions that never need to talk.
• REST vs GraphQL vs gRPC — the transport for the ID service.

References and further reading

1. Announcing Snowflake (Twitter Engineering, 2010)blog.x.comWhy Twitter needed uncoordinated, roughly sortable 64-bit IDs; ticket servers, UUIDs and ZooKeeper sequential nodes considered and rejected; worker numbers chosen at start-up through ZooKeeper.
2. Snowflake README and IdWorker source (snowflake-2010 tag)github.comThe 41-bit time, 10-bit machine and 12-bit sequence layout, 10k IDs/s per process, the k-sorted promise, refusing IDs when the clock goes backwards, and waiting for the next millisecond when the sequence is full.
3. Sharding & IDs at Instagram (Instagram Engineering, archived copy)web.archive.orgIDs minted inside PostgreSQL per logical shard: 41 bits of milliseconds, 13 bits of shard and a 10-bit sequence, with the PL/pgSQL function that builds them.
4. Ticket Servers: Distributed Unique Primary Keys on the Cheap (Flickr, 2010)code.flickr.netREPLACE INTO plus LAST_INSERT_ID on two MySQL servers that split the ID space into odd and even numbers.
5. RFC 9562: Universally Unique IDentifiers (UUIDs)rfc-editor.orgUUIDv4 and UUIDv7 layouts, monotonic counters, handling clock rollback, restarting above a stored timestamp, index locality, and the rule that UUIDs must not be used as security capabilities.
6. ULID specificationgithub.comA 48-bit millisecond timestamp plus 80 random bits, a 26-character Crockford base32 form, and monotonic generation within one millisecond.
7. Sonyflake READMEgithub.comA Snowflake variant with 39 bits of 10 ms ticks, an 8-bit sequence and a 16-bit machine ID taken from the private IP: 174 years and 65,536 machines, fewer IDs per machine.
8. Discord API reference: Snowflakesdiscord.comA production Snowflake layout with worker and process fields, ID-based pagination, and IDs always returned as strings in JSON.
9. Spanner: schema design best practicescloud.google.comWhy monotonically increasing keys hot-spot a range-partitioned database, and the fixes: UUIDv4, bit-reversed sequences, reordering key columns and hash prefixes.
10. PostgreSQL documentation: CREATE SEQUENCEpostgresql.orgSequence caching hands each session a block of values; unused values become holes, values from different sessions interleave, and sequences are never gapless.