Design a unique ID generator

Design a unique ID generator for 64-bit, time-sorted IDs. Start with one database sequence, let the numbers lead to Snowflake IDs, then stress it with clocks that go backwards, zombie workers, the bits budget and what an ID reveals, with interview prompts and code.

Foundation30 min core · 45 min full depth

Read first: Estimation Unique IDs
Scaling patterns: Multi-region and active-active
Building blocks: Unique IDs Consensus Indexes Partitioning Load balancing
Related: URL shortener News feed

“Design a service that hands out unique IDs to every other service in the company. They should be 64 bits and roughly sortable by time.”

This sounds like a ten minute question. The answer most people give has a duplicate-ID bug in it.

Once data lives on many machines, “auto-increment” stops being an answer. The standard answer is a Snowflake ID: a timestamp, a machine number and a counter, packed into 64 bits. Drawing that takes a minute. The hard part is what happens around it. What if a clock jumps backwards? What if two servers both believe they are worker 7? And how long do the bits last?

So this page starts with the simplest answer, a database counter, and lets the numbers lead us to Snowflake. Then it spends its depth on the two ways Snowflake can produce duplicates.

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains each part.

Each ID is 64 bits: time, place and a counter. 41 bits of milliseconds, 3 bits for the region, 7 for the server (the worker), and 12 for a counter within each millisecond. IDs sort by time, and no two servers can make the same one.
Each server gets its worker number from etcd, a small, strongly consistent store, when it starts. After that, it makes IDs from its own clock, with no calls to anyone.
The generator never reuses a millisecond. If the clock steps back a little, it keeps counting in its last millisecond. If the clock is more than a second behind, it refuses, and the caller tries another server.
Each worker number comes with a time limit. etcd records the latest millisecond each holder may use. A frozen server that wakes up can never make IDs past that mark, and its successor starts after it.
Callers keep a small buffer of IDs, about 100 ms worth, and refill it in batches. So the fleet stays small even at ten times the load.

Scope it

A few questions decide which kind of ID to use, and whether this service should exist at all.

Interviewerminute 0

We need unique IDs for everything: orders, posts, messages. Design the ID generator.

What they are testing

Whether you ask about bits, ordering and rate before choosing anything.

These four questions matter most:

How many bits may an ID have? 64, because it must fit a BIGINT column and a Java long. If 128 bits were allowed, every service could make its own UUIDv7 IDs, and there would be no service to build. Say this out loud.
Must IDs sort by time? Roughly: IDs made more than about a second apart sort in order. If order didn’t matter, we could avoid clocks entirely.
How many? 40 billion a day: 460,000 a second, and 1.9 million at peak.
Must numbers have no gaps? No. Unique and roughly ordered is enough. Gap-free numbering, like invoices, needs a very different, much slower design.

From these answers we make four promises:

Never a duplicate. Not after restarts, clock jumps, network splits or frozen servers. A duplicate key can lose someone’s order.
Always available. 99.999% of requests succeed, because every write in the company waits on an ID.
Fast. Under 2 ms for a network call, and about a microsecond from a client’s buffer.
Long-lived. The layout lasts at least 50 years.

We leave out gap-free invoice numbers, secret tokens (those need 128 random bits) and short, human-friendly codes.

Go deeperMore questions, and what each changes1 min

Question	We assume	If the answer were different
Several regions?	Yes, up to 8, each making IDs alone	One region: drop the region bits and give them to workers
Are IDs shown to users?	Yes, in URLs and APIs	Internal only: what an ID gives away matters much less
A few thousand a second?	No, 1.9 million at peak	One database sequence would be enough

The service also decodes IDs: it turns an ID back into its time, region and worker, for debugging. And within one worker, IDs always increase.

The numbers that decide it

Now we work out the numbers. Each one should rule something out, or set a bit width.

Assumptions

IDs a day, all services: 40 billion
Peak over average: 4×
IDs per call: 1
Timestamp bits: 41
Region bits: 3
Worker bits: 7
Sequence bits: 12

Rate460,000/s1.9M/s at peak

40 billion IDs a day ÷ 86,400 seconds ≈ 460,000 a second. Peaks are about four times that: 1.9 million a second.

So we no database call per ID. One Postgres sequence serves about 20,000 a second, a hundred times too few.

Per worker4.1M/sper worker

With 12 counter bits, one worker can make 4,096 IDs per millisecond.

So we the generator is never the limit. Network calls are, at about 100,000 a second per server.

Lifetime70 yearsof 41 bit timestamps

41 bits of milliseconds is 2⁴¹ ms ≈ 70 years. Counted from 1 January 2026, that lasts until 2095.

So we use 41 bits and our own starting date. Counted from 1970, the same bits run out in 2039.

Storage saved120 TBa year, per index

An 8-byte key instead of a 16-byte UUID saves 8 bytes per row, in every index that holds it, at 40 billion rows a day.

So we running a service is worth it. 64-bit IDs save that much over 128-bit UUIDs.

At one ID per call, the peak needs about 31 servers. That’s fine today. At ten times the load, it would need over 300, but 7 worker bits only allow 128. You can see this in the calculator: multiply the IDs a day by ten, then set IDs per call to 100, and the fleet drops to 8.

Change an assumption

IDs a day, all services40 billionPeak over average4×IDs per call1Timestamp bits41Region bits3Worker bits7Sequence bits12

IDs, average: 460,000/s
IDs, peak: 1,900,000/s; Far past one database sequence (about 20,000 round trips a second): no store on the per-ID path.
Most one worker can mint: 4,100,000/s; The sequence space per millisecond. It caps a server however fast its CPU is.
ID servers needed at peak: 31; Calls at 60% of 100,000 a second per server, or the sequence space, whichever needs more.
Worker IDs in use at peak, percent: 24; Plenty of spare worker IDs for restarts and deploys.
Years until the timestamp runs out: 70; Counted from our own epoch, 2026. Counted from the 1970 Unix epoch, 41 bits run out in 2039.
Bits over the 63 usable: 0; Zero means the layout fills a signed 64 bit integer with the sign bit left at 0. Negative means bits to spare.
Index bytes saved a year over 128 bit IDs: 120 TB; Per index that holds the ID, before replicas. This is why 64 bits is worth a service.
Call bandwidth at peak: 370 MB/s; About 200 bytes per call with headers. The network copes; the per-call CPU is what costs.

Build the design

We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs.

Step 1. One sequence in one database

The simplest ID generator is a counter in one database. Every service calls it, and it hands out the next number. The IDs are unique, they fit in 64 bits, and they sort by time, because the counter only goes up.

Unique ID generator · architecture

Stage 1: One sequence in one database

Color keyServiceDatabaseNew in this stageAsync or occasional

IDs per second: 1,900,000

Stage 1 of 6

One sequence in one database

Why this stage

Nothing yet.

This is the smallest design that hands out unique IDs.

What we add

An ID service that calls nextval on one Postgres sequence for every ID it returns.

What it costs

A database round trip per ID, about 20,000 a second at most, and one database that every write in the company waits on.

At 1.9M ids per second, Postgres is 9500% busy. Stage 2 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

The numbers break it at once. One database hands out about 20,000 numbers a second, and we need 1.9 million. It is also one machine that every write in the company depends on.

Step 2. Leased ranges

The usual fix is to stop asking for one number at a time. Each ID server takes a range of 100,000 numbers from the database, and hands them out from memory. The database is now asked a few times a second, not 1.9 million times. This is the URL shortener’s answer.

Unique ID generator · architecture

Stage 2: Leased ranges

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 2 of 6

Leased ranges

Why this stage

The peak is 1.9 million IDs a second, about 100 times what one sequence serves, and one ID server answers about 100,000 calls a second.

What we add

A load balancer, a fleet of ID servers, and blocks of 100,000 IDs leased from the database and handed out from memory.

What it costs

IDs are unique but not time-ordered: two servers hand out numbers millions apart at the same moment.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

The cost is time order. Server A might be handing out 4,700,000 while B hands out 9,200,000. So an ID made on A now is smaller than one made on B an hour ago. The IDs are unique, but not in time order. If order didn’t matter, we could stop here. It does matter, so we need IDs that carry the time inside them.

Step 3. IDs built from the clock

The fix is to put the time inside the ID itself. Before we pick a layout, here are the five common ways to make unique IDs, side by side:

Approach	How it works	Bits	Sorts by time	Coordination	Problem
UUIDv4	122 random bits	128	No	None	Random index inserts; 16 bytes in every index
UUIDv7 (RFC 9562)	48 bits of ms, 74 random bits	128	Yes	None	Doesn’t fit `BIGINT`; 16 bytes everywhere
Database sequence	`nextval` on one database	64	Yes	A database call per ID	20,000 a second; one point of failure
Leased ranges	Each server takes blocks of 100,000 numbers	64	No, across servers	One call per block	No time order
Snowflake	Time + machine + counter	64	Within about a second	A worker number at start	Uniqueness now depends on clocks and worker numbers

We pick Snowflake, the layout Twitter published in 2010 (Twitter engineering).

From the top bit down, our 64 bits look like this:

Bits	Field	Width	Range	Why this width
63	Sign	1	Always 0	IDs stay positive in every language
62–22	Timestamp	41	ms since 2026-01-01, 70 years	Lasts until 2095
21–19	Region	3	0 to 7	Up to 8 regions make IDs with no coordination
18–12	Worker	7	0 to 127	Servers per region, with room for deploys
11–0	Sequence	12	0 to 4,095	4.1 million IDs a second per worker

The timestamp makes IDs sort by time. The region and worker bits keep servers apart. The sequence counts IDs within one millisecond on one worker. So two IDs can only be equal if the same worker uses the same millisecond and the same count twice. The rest of the design exists to stop exactly that.

Unique ID generator · architecture

Stage 3: Snowflake IDs from the clock

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 3 of 6

Snowflake IDs from the clock

Why this stage

A requirement, not load: IDs must sort roughly by creation time, and every region must mint IDs without a shared database.

What we add

IDs built from a timestamp, a worker ID and a sequence. etcd hands each server a worker ID on a lease.

The ticket database is gone.

What it costs

Uniqueness now rests on the clock never going backwards and on no worker ID ever being held twice.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

Snowflake.javasnowflake.pySnowflake.cssnowflake.gosnowflake.ts

// The layout, from the top bit down: 1 sign bit (always 0, so IDs stay positive in every
// language), 41 bits of milliseconds since our epoch, 3 region bits, 7 worker bits, 12 sequence bits.
final class Snowflake {
    static final long EPOCH = 1_767_225_600_000L;     // 2026-01-01T00:00:00Z: 41 bits last until 2095
    static final int SEQ_BITS = 12, WORKER_BITS = 7, REGION_BITS = 3;
    static final int TS_SHIFT = REGION_BITS + WORKER_BITS + SEQ_BITS;
    static final long SEQ_MASK = (1L << SEQ_BITS) - 1; // 4,096 IDs per millisecond per worker

    private final long node;           // region and worker, shifted once: fixed while we hold the lease
    private final LongSupplier clock;  // wall-clock ms, injected so tests can move time
    private long lastMs = -1;
    private long seq;

    Snowflake(int region, int worker, LongSupplier clock) {
        if (region < 0 || region >= 1 << REGION_BITS || worker < 0 || worker >= 1 << WORKER_BITS)
            throw new IllegalArgumentException("region or worker does not fit its bits");
        this.node = ((long) region << (WORKER_BITS + SEQ_BITS)) | ((long) worker << SEQ_BITS);
        this.clock = clock;
    }

    // synchronized: two threads must never read the same (ms, seq) pair. The critical section
    // is a few arithmetic operations, far from the bottleneck at 100,000 calls a second.
    synchronized long next() {
        long now = clock.getAsLong();
        if (now == lastMs) {
            seq = (seq + 1) & SEQ_MASK;
            if (seq == 0) {
                // 4,096 IDs in this millisecond already: spin until the next one starts.
                while ((now = clock.getAsLong()) <= lastMs) Thread.onSpinWait();
            }
        } else {
            seq = 0;
        }
        // FLAW: if NTP steps the clock back, now < lastMs and the else branch above reuses
        // (ms, seq) pairs this worker already issued. Duplicates. Stage 4 fixes it.
        lastMs = now;
        return ((now - EPOCH) << TS_SHIFT) | node | seq;
    }
}

Uniqueness now depends on two things: every live server must have its own worker number, and its clock must never reuse a millisecond. Step 4 handles both.

Go deeperWhy not a ticket server?1 min

A ticket server is the database sequence made sturdier. Flickr ran two MySQL servers: one gave out odd numbers and the other even numbers, each counting up by two. If one died, the other kept going alone. It is simple and it worked for years. But every ID still costs a database round trip, so it tops out at tens of thousands a second. And two servers drift apart, so IDs only roughly follow time. At 1.9 million a second, we would need a hundred of them, and then we are back to needing a scheme that keeps them apart, which is what Snowflake’s worker bits already do.

The lesson for the interview: each option is right somewhere. Name the number that rules it out here, instead of calling it wrong.

Step 4. Worker numbers from a lease

Each server needs a worker number that no other live server holds. When it starts, it claims one in etcd: “create key workers/007 for me, only if nobody has it”. The key is attached to a lease, a timer the server renews every second. If the server dies, the lease expires after 60 seconds, and the key disappears, so the number is free again.

etcd keeps one more key per worker, the mark: the latest millisecond any holder of that number may use. The mark is not attached to the lease, so it outlives the holder. The second deep dive shows why this one key is what makes the whole design safe.

/idgen/r1/workers/007  -> "idsvc-3f9c"       attached to the holder's lease, 60 s
/idgen/r1/marks/007    -> 1793196191204      not on the lease: must outlive the holder

The clock gets the same care. Every server keeps its clock in step with disciplined time sync. And the generator never reuses a millisecond, even if the clock moves back. The first stress test shows how.

Unique ID generator · architecture

Stage 4: Clocks that go backwards

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 4 of 6

Clocks that go backwards

Why this stage

A failure, not load: NTP steps a clock back, a leap second repeats, a paused server wakes up after its lease expired.

Each one repeats IDs.

What we add

Time sync that slews instead of stepping, a generator that never moves backwards, and a high-water mark in etcd that fences zombie workers.

What it costs

A server whose clock jumps back more than a second stops issuing until it catches up, and an etcd outage stops the fleet after 30 seconds.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

Asking for IDs

Services call the ID servers over gRPC, and can ask for up to 1,000 IDs at once:

service IdService {
  // count: 1 to 1,000. Returns exactly count IDs, increasing, all from one worker.
  rpc NextIds(NextIdsRequest) returns (NextIdsResponse);
}

If a server’s clock is unsafe, it answers UNAVAILABLE, and the caller retries another server at once. Follow a request, and a server starting up, through the design:

Unique ID generator · architecture

Trace a request: Get one ID

Color keyServiceDatabaseNew in this stageAsync or occasionalHop in motionHops doneResponse

Get one ID: step 1 of 3

Services to Load balancer

The order service calls NextIds(count: 1) on a gRPC connection it keeps open. The load balancer spreads calls over every healthy ID server; any server will do, because none holds state another one needs.

0.3 ms of a 2 ms budget

Services → Load balancer0.3 ms
Load balancer → ID servers0.2 ms
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

This is enough for a mid-level answer. The bit layout with a reason for each width, worker numbers from etcd, and a strong reason to prefer 64 bits. The stress tests are what make it a senior answer.

Go deeperWhy not just use UUIDs?1 min

A common worry is that UUIDs can collide. They practically can’t. A UUIDv4 has 122 random bits. At 40 billion a day, the chance of even one collision reaches one in a billion only after about 7 years.

The real reasons not to use UUIDv4 here are size and random inserts. UUIDv7 fixes random inserts, because it starts with the time. Only 64-bit IDs fix the size: half the bytes in every primary key, foreign key and index, about 120 TB a year per index at our volume. And they fit the BIGINT columns every existing table already has.

The price of Snowflake is a service to run, and two new ways to create duplicates: clocks and worker numbers. If 128 bits were allowed, UUIDv7 would avoid both and need no service.

Go deeperWhy etcd, and not a database table?1 min

Claiming a worker number needs one operation done exactly right: “create this key, but only if nobody has it”. If two servers ask at the same moment, exactly one must win, and both must agree on who won. This is called a compare-and-set.

etcd is built for this. It runs on several members that agree on every write using a method called Raft. A write counts only once most members have it, so losing one member loses nothing. Its leases expire on their own when a holder stops renewing them. ZooKeeper offers the same things with its short-lived nodes.

A plain database table can work too: a row per worker number, with an owner and an expiry time. But then we build the expiry, the renewals and the “only if free” check ourselves, and we must be sure the database never answers from a stale copy. etcd gives all of this already, which is why Kubernetes uses it for the same job.

Stress it

The design works when clocks and servers behave. Now we test it where they don’t: a clock that goes backwards, a server that freezes, the bits budget, and what an ID gives away. Only the bits budget adds a new piece, a small buffer in each caller.

A clock that goes backwards

Interviewerminute 18

NTP just moved this server’s clock back two seconds. What does your generator do?

What they are testing

Whether you find the duplicate bug when the clock steps back, and fix it without stopping the fleet.

The simple generator above is correct only while the clock behaves. Say the time service steps the clock back 50 ms. The next call resets the counter to 0, in a millisecond it already used. It then makes the same IDs again. Duplicates.

Clocks go backwards for ordinary reasons. The time service jumps the clock when it’s far off. A leap second can repeat 23:59:59. A virtual machine can resume with an old clock.

There are four ways to react when the clock is behind the last millisecond used:

Policy	What it does	Problem
Refuse on any step back	Fail until the clock catches up (Twitter’s original)	Even a 3 ms correction makes the server fail requests
Wait it out	Sleep until the clock passes the last millisecond	A two second step blocks every caller for two seconds
Monotonic clock from start	Time at boot plus a counter that never goes back	A restart forgets it, and can reuse IDs
Keep going, with a limit	Use the larger of clock and last ms; refuse past 1 s	IDs can be up to a second “early” while the clock catches up

We pick keep going, with a limit. The generator uses the larger of the clock and the last millisecond it used. So a small step back changes nothing: it keeps counting in that millisecond. When the counter fills up, it moves to the next millisecond instead of waiting. It refuses only when it would run more than a second ahead of the real clock, because that would break our ordering promise. A refusing server fails its health check, and rejoins when its clock catches up.

Snowflake.javasnowflake.pySnowflake.cssnowflake.gosnowflake.ts

// Thrown instead of an ID. The server fails its health check, and callers retry elsewhere.
final class ClockException extends RuntimeException {
    ClockException(String message) { super(message); }
}

// The same layout as stage 3, now safe when the clock moves backwards. The generator keeps its
// own time: never below what it already issued, never more than a second ahead of the wall
// clock, and never past the high-water mark this worker has durably reserved in etcd.
final class Snowflake {
    static final long EPOCH = 1_767_225_600_000L;     // 2026-01-01T00:00:00Z
    static final int SEQ_BITS = 12, WORKER_BITS = 7, REGION_BITS = 3;
    static final int TS_SHIFT = REGION_BITS + WORKER_BITS + SEQ_BITS;
    static final long SEQ_MASK = (1L << SEQ_BITS) - 1;
    static final long MAX_AHEAD_MS = 1_000;           // the ordering promise: k-sorted within about 1 s

    private final long node;
    private final LongSupplier clock;
    private long lastMs = -1;
    private long seq;
    private long highWaterMs = 0;   // raised by the worker lease (deep dive 2); 0 means "may not issue yet"

    Snowflake(int region, int worker, LongSupplier clock) {
        if (region < 0 || region >= 1 << REGION_BITS || worker < 0 || worker >= 1 << WORKER_BITS)
            throw new IllegalArgumentException("region or worker does not fit its bits");
        this.node = ((long) region << (WORKER_BITS + SEQ_BITS)) | ((long) worker << SEQ_BITS);
        this.clock = clock;
    }

    synchronized long next() {
        long now = clock.getAsLong();
        // A clock that stepped back changes nothing: keep counting on the last millisecond used.
        long ms = Math.max(now, lastMs);
        long s = 0;
        if (ms == lastMs) {
            s = (seq + 1) & SEQ_MASK;
            if (s == 0) ms++;   // this millisecond is full: borrow the next one instead of spinning
        }
        // Refuse rather than drift. Past a one second step back, or a sustained burst above
        // 4 million a second, the IDs would stop being k-sorted. Nothing is committed yet,
        // so a refusal leaves the state exactly as it was.
        if (ms - now > MAX_AHEAD_MS)
            throw new ClockException("clock is " + (ms - now) + " ms behind IDs already issued");
        // The fence: never use a timestamp this worker has not reserved in etcd. A zombie that
        // lost its lease cannot renew, runs out of reserved time, and stops by itself.
        if (ms > highWaterMs)
            throw new ClockException("no reserved time left: the worker lease was not renewed");
        lastMs = ms;
        seq = s;
        return ((ms - EPOCH) << TS_SHIFT) | node | s;
    }

    // Called once, before the first ID, with the mark an earlier holder of this worker ID left.
    // Every ID is then later than that mark, even if the clock steps back before the first call.
    synchronized void startAfter(long markMs) {
        lastMs = markMs;
        seq = SEQ_MASK;     // that millisecond counts as full, so the first ID uses markMs + 1
    }

    // Called only after the new mark is committed in etcd, so the generator never runs ahead
    // of what a later holder of this worker ID will wait for.
    synchronized void raiseHighWater(long ms) {
        highWaterMs = Math.max(highWaterMs, ms);
    }
}

NTP steps the clock back two seconds on one server

Scroll or pinch to zoom, drag to pan

Color key
Service

We also make steps rare. Servers use chrony with several time sources, jump the clock only at boot, and use smeared leap seconds, which slow the clock slightly for hours instead of repeating a second (Google’s leap smear). The generator won’t start until its clock is within 10 ms.

Two servers that both think they’re worker 7

A server freezes for a minute, its lease expires, and a new server takes worker 7. Then the frozen server wakes up, still believing it is worker 7.

A lease alone is not enough. Here is how it fails:

Server A holds worker 7 and renews its lease every second.
A freezes for 70 seconds: a long garbage collection pause, a frozen VM, or a network problem.
The lease expires after 60 seconds. Server B claims worker 7.
A wakes up, still believing it is worker 7, and makes IDs in the same milliseconds as B. Duplicates.

A server like A is called a zombie. Checking the lease before every ID doesn’t help, because the freeze can come between the check and the answer. The usual zombie fix, a “fencing token” that the database checks on every write, doesn’t work either. IDs go into hundreds of databases, and none of them can check a token.

The fix is to fence by time. Each holder records in etcd the latest millisecond it may use, the mark, and never makes IDs past it:

Every second, A renews its lease and raises the mark to its clock plus 30 seconds, but only if it still holds worker 7. It may only use time up to a mark that etcd has confirmed.
If A freezes, it can’t renew. It never makes IDs past its last confirmed mark, however long it was frozen and whatever its clock says.
B claims worker 7 first, and then reads the mark. From the moment B claims, A’s renewals fail, so the mark can’t move again. B starts every ID after the mark.

So all of A’s IDs are at or below the mark, and all of B’s are above it, even if A’s clock is wrong. B never compares clocks with A. It only compares with a number in etcd.

A zombie worker cannot collide with its successor

Scroll or pinch to zoom, drag to pan

Color key
Service

WorkerLease.javaworker_lease.pyWorkerLease.csworker_lease.goworker-lease.ts

// The coordination store: etcd here, ZooKeeper works the same way. Every call is
// linearizable, and that, not anyone's clock, is what makes a worker ID safe to hold.
interface Coordinator {
    long grantLease(long ttlMs);                                // expires unless kept alive
    boolean claim(String key, String holder, long leaseId);     // create key only if absent, on the lease
    long readMark(String markKey);                              // latest reserved timestamp, 0 if none
    // Keep the lease alive, then one transaction: write the mark only if the claim key is still
    // attached to this lease. Compare the lease, never the holder name: a replacement pod reuses
    // its predecessor's name, but a lease ID is never reused. The mark key is NOT on the lease:
    // it must outlive this holder for the next one to read.
    boolean renewAndMark(long leaseId, String key, String markKey, long markMs);
}

final class WorkerLease {
    static final long TTL_MS = 60_000;     // a dead server's worker ID frees up after a minute
    static final long RESERVE_MS = 30_000; // how far ahead a holder may issue. Shorter than the TTL,
                                           // so a successor with a synchronized clock never waits.
    static final int WORKERS = 128;        // 7 worker bits

    private final Coordinator coord;
    private final int region;
    private final String holder;
    private final LongSupplier clock;
    private long leaseId, lastMark;
    private int worker = -1;
    private Snowflake gen;

    WorkerLease(Coordinator coord, int region, String holder, LongSupplier clock) {
        this.coord = coord;
        this.region = region;
        this.holder = holder;
        this.clock = clock;
    }

    private String key(int w) { return String.format("/idgen/r%d/workers/%03d", region, w); }
    private String markKey(int w) { return String.format("/idgen/r%d/marks/%03d", region, w); }

    // Claim the lowest free worker ID, then make sure every ID we issue is later than any
    // timestamp an earlier holder could have used. Correct even if that holder is a zombie.
    Snowflake start() throws InterruptedException {
        leaseId = coord.grantLease(TTL_MS);
        for (int w = 0; w < WORKERS; w++) {
            if (!coord.claim(key(w), holder, leaseId)) continue;
            worker = w;
            // Read AFTER the claim: from now on no earlier holder can raise the mark.
            long mark = coord.readMark(markKey(w));
            // Usually no wait at all. A clock far behind the mark would only be refused later.
            while (clock.getAsLong() <= mark) Thread.sleep(Math.min(mark - clock.getAsLong() + 1, 1_000));
            lastMark = mark;
            gen = new Snowflake(region, w, clock);
            gen.startAfter(mark);   // a clock step before the first ID cannot reach back below it
            renewOnce();            // reserve our own time; until this commits the generator refuses
            return gen;
        }
        throw new IllegalStateException("all " + WORKERS + " worker IDs are taken");
    }

    // Every second: keep the lease alive and push the mark 30 seconds ahead. The generator may
    // use the new time only after the write commits. If renewals fail, nothing else is needed:
    // the generator stops by itself when it reaches the last committed mark.
    void renewOnce() {
        long mark = Math.max(lastMark, clock.getAsLong() + RESERVE_MS); // never lower a mark
        if (coord.renewAndMark(leaseId, key(worker), markKey(worker), mark)) {
            lastMark = mark;
            gen.raiseHighWater(mark);
        }
    }
}

Go deeperWhy 60 seconds and 30, and two more details1 min

The mark reaches at most 30 seconds ahead, and the lease lasts 60. So when a dead holder’s lease expires, the successor’s clock is already past the old mark, and it doesn’t have to wait. The 30 seconds is also how long the fleet keeps working if etcd goes down, which is far longer than etcd needs to pick a new leader.

Restarts get the same treatment. A restarted process is a new holder, so it starts above its worker’s mark. A clock that stepped back during the restart is harmless.

Two details keep the argument sound. The “do I still hold it?” check compares the claim key’s lease ID, never the server’s name. A replacement pod reuses its predecessor’s name, but never its lease. And the mark only ever rises, so a holder whose clock stepped back can’t pull it below IDs it already made.

Other ways to hand out worker numbers, like a config file or a Kubernetes pod number, can all end with two live servers holding one number. So every option needs the same time fence. The choice between them is about operations, not safety.

The bits budget, and running out of servers

Why 41, 3, 7 and 12 bits? And what happens at ten times the load?

There are 63 usable bits, because the top bit stays 0. Every bit moved doubles one field and halves another. 40 timestamp bits would last 35 years. 42 would last 139. A fourth region bit would halve the workers. Real layouts chose differently:

Layout	Time	Machine	Sequence	Lifetime
Twitter Snowflake	41 bits, ms, from 2010	10: 5 datacenter, 5 worker	12	About 70 years
Instagram	41 bits, ms	13: database shard	10	About 70 years
Sonyflake	39 bits, 10 ms units	16: machine	8	About 174 years
Ours	41 bits, ms, from 2026	10: 3 region, 7 worker	12	Until 2095

Now push the load to 19 million IDs a second. The generator could easily make them: 128 workers × 4.1 million is 520 million a second. The problem is calls. At one ID per call, we’d need over 300 servers, and 7 worker bits only allow 128.

The fix is a client buffer. Each service uses a small ID library. It keeps a queue of about 100 ms worth of that service’s own IDs, between 1 and 1,000, and refills in the background with one NextIds(count) call. At 19 million a second, the fleet needs about 8 servers.

Unique ID generator · architecture

Stage 5: Batches in the caller

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 5 of 6

Batches in the caller

Why this stage

At 10 times the load, 19 million calls a second would need over 300 ID servers, and 7 worker bits allow 128.

What we add

A client library in every service that buffers about 100 ms of IDs and refills in batches, so one call returns hundreds of IDs.

What it costs

A crashed service loses its buffer, which leaves gaps, and a buffered ID can be up to 100 ms older than its use.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

Go deeperFollow a buffered request, and why IDs help indexes3 min

Unique ID generator · architecture

Trace a request: ID from the buffer

Color keyServiceDatabaseNew in this stageAsync or occasionalHop in motionHops doneResponse

ID from the buffer: step 1 of 4

Services to ID buffer

The order service asks its in-process ID client. The ID comes off a local queue in about a microsecond, with no network at all.

0.001 ms of a 2 ms budget

Services → ID buffer0.001 ms
ID buffer → Load balancerasync
Load balancer → ID serversasync
Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Why only 100 ms? An ID’s timestamp is when it was made, not when it was used. A buffer holding a minute of IDs would break the one-second ordering promise. Sizing by time keeps the error at 100 ms at any rate. A quiet service holds one ID. A busy one holds a thousand.

What the library does when a refill fails. It retries another server at once, and keeps handing out what is left in the buffer meanwhile. If the buffer runs dry, the caller waits a few milliseconds for the retry rather than getting an error. Only when every server in the region has refused does it fail the call. A crash loses the buffered IDs, which is fine: we never promised no gaps.

Why sorted IDs help a database. With time-ordered keys, every insert goes to the rightmost page of the index, which is always in memory. With random keys, every insert goes to a random page. Take a 500 GB index and 64 GB of memory: about 87% of random inserts touch a page that isn’t in memory. 20,000 inserts a second then cost about 17,000 disk reads a second.

But some stores have the opposite problem. In stores split by key range (Spanner, Bigtable, CockroachDB), every new time-ordered key goes to the last range, so all writes land on one server. There, use a hash of the ID as the first part of the key.

Never split data by id mod N. That looks at the lowest bits, which are the counter. At quiet times, most milliseconds see one or two IDs per worker, so the counter is mostly 0 or 1, and most rows land on two shards. Split by a hash of the ID instead.

What an ID gives away

These IDs show up in public URLs. Is that a problem?

Anyone can shift a Snowflake ID right by 22 bits and read when it was made, in which region, on which worker. Public tools decode Discord and Twitter IDs this way. The counter even hints at volume. Someone who collects public IDs for a day can estimate how many orders you take.

The defenses, in order:

Check permissions on every read. Knowing an ID must never grant access.
Secrets get their own random token. A password reset link uses 128 random bits, never an ID.
Disguise IDs where volume matters. Scramble the 64-bit ID with a keyed, reversible shuffle before showing it, and unscramble it on the way in. The URL shortener shows how.

The cost of disguising: clients can’t sort by the public ID, and old public IDs live in emails forever, so the key needs a version number to ever be changed.

When things break

Interviewerminute 40

etcd loses quorum. What happens to every write in the company?

What they are testing

Whether no failure can ever produce a duplicate, even if that means refusing for a while.

No failure may produce a duplicate. If etcd goes down, nothing happens for 30 seconds, because each server can still use time up to its mark. After that, every ID server in the region refuses.

That sounds harsh, and it’s on purpose. The alternative, “keep going on the old worker number”, is exactly how zombies make duplicates. An outage is loud and short. A duplicate key is silent, and shows up weeks later as two customers sharing one order. So etcd runs five members across three data centres, and client buffers hide short blips.

Click any box to break it and see what users would notice:

Unique ID generator · architecture

Break it: what fails, who notices, what users see

Color keyServiceDatabaseNew in this stageAsync or occasional

Break

Failure: click any box to break it

etcd goes down

What breaks

Quorum is lost, so no claims and no renewals.

How we notice

Lease renewal errors and the reserved time left per server.

What users see

Nothing for 30 seconds.

Then every server reaches its mark and refuses, and writes everywhere stop.

What we do

Five etcd members across three zones.

A leader election takes seconds, well inside the 30 second reservation.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Each region runs its own ID fleet and its own etcd. The 3 region bits keep their IDs apart, so no request ever crosses regions. If one region’s fleet is unreachable, its clients use a neighbour’s. Those IDs carry the neighbour’s region bits, which is harmless: the field says where an ID was made, not where the data lives.

Unique ID generator · architecture

Stage 6: Every region on its own

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 6 of 6

Every region on its own

Why this stage

One region is one failure domain against a 99.999% target, and a call to another region costs about 70 ms.

What we add

An ID fleet and an etcd cluster in every region, told apart by 3 region bits.

Callers fail over to another region.

What it costs

Order across regions is only as good as clock agreement, and 3 bits cap the design at 8 regions.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

Go deeperEvery failure, and what users see2 min

Part	Failure	What users see	How we notice	What we do
ID server	Crash or long freeze	A few retried calls; buffers hide it	Health checks, about 5 s	Removed; its number frees in 60 s; a zombie stops at its mark
etcd	Quorum lost	Nothing for 30 s, then IDs in the region stop	Renewal errors, time left before mark	Five members in three zones; elections take seconds
Time sync	Step back, drift, bad source	Small: nothing. Over 1 s: that server refuses	Clock offset, lead over the real clock	Several sources, gentle corrections, smeared leap seconds
ID buffer	A service restarts	Nothing; some IDs never used	None needed	Buffers hold only 100 ms
Whole region	Unreachable	Buffers hide it; clients switch in seconds	External test requests	Every region makes IDs on its own

Losing etcd data is the dangerous case. Restoring etcd from a backup rolls the marks back. A new holder could then start below IDs already used. So the restore runbook stops every ID server first, then moves every mark well past the restore time.

The last line of defense is in the databases that store IDs. A unique constraint on every ID column turns a duplicate into a failed insert, with an alert, instead of an overwritten row.

Go deeperWhat the IDs promise1 min

Property	Promise	What it rests on
Uniqueness	Absolute	Claims in etcd, marks read after the claim, a generator that never goes back
Order from one worker	Always increasing	The larger of clock and last ms, plus the counter
Order across workers	Within about 1 s	Clocks within milliseconds, the 1 s limit, the 100 ms buffer
Cause before effect	Not promised	A reply can sort before the post it replies to
No gaps	Not promised	Crashes and buffers leave gaps

Snowflake IDs give a rough time order, not a global order of events. Two events a few milliseconds apart on different servers can come out either way. A true total order needs one counter that everyone asks, which is the bottleneck we started by ruling out.

Go deeperRunning it: alerts and drills2 min

Wake someone up when: fewer than 99.99% of ID requests succeed from the client’s view; any server has less than 10 seconds left before its mark, because that’s the countdown to a fleet-wide stop; a clock is more than 500 ms off; fewer than 25% of worker numbers are free; or any database in the company reports a duplicate ID.

Each calling service gets a quota, so a runaway loop can’t ask for a million IDs a second.

Watch the worker numbers. Each region has 128, and deploys briefly need extra: a new server claims a number before the old one releases its own. A rolling deploy of 40 servers can hold 80 numbers for a minute. If free numbers fall below a quarter, new servers can’t start, so the deploy tool waits for numbers to free up instead of failing halfway.

Test the dangerous paths on purpose. Once a week, a test server has its clock stepped back two seconds, and another is frozen for 90 seconds. Both must make zero duplicates. A safety mechanism that never runs tends to break silently.

Wrap up

The whole design

Here is everything we built, in the order we built it. Use the buttons to step through it.

Unique ID generator · architecture

The full design, stage by stage

Color keyServiceDatabaseNew in this stageAsync or occasional

Stage

IDs per second: 1,900,000

Stage 6 of 6

Every region on its own

Why this stage

One region is one failure domain against a 99.999% target, and a call to another region costs about 70 ms.

What we add

An ID fleet and an etcd cluster in every region, told apart by 3 region bits.

Callers fail over to another region.

What it costs

Order across regions is only as good as clock agreement, and 3 bits cap the design at 8 regions.

At 1.9M ids per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.The whole design. Step through it: one sequence, leased ranges, IDs from the clock, worker leases, client buffers, then every region.

The numbers behind the busy bars

What one machine can do

One Postgres sequence serves about 20,000 round trips a second.
One ID server answers about 100,000 small gRPC calls a second.
One worker mints at most 4,096 IDs a millisecond (12 sequence bits), about 4 million a second.

Stages 3 and 4: worker IDs run out

At these stages, the ID servers bar shows worker IDs in use, not CPU.
100% means all 128 worker IDs a region has (7 bits), with each server at 60% of 100,000 calls a second. Past 100%, there are no worker IDs left for more servers.

Later stages

Until stage 6, everything runs in one region.
From stage 5, a call carries about 100 IDs, so a server is limited by its sequence space, not by calls.
In stage 6, the busiest region carries 40% of all IDs.

The decisions, and what each one costs

Decision	We chose	We gave up	We’d choose differently if
ID format	Snowflake, 64 bits	A design with no service	128 bits were allowed (UUIDv7 in every service)
Bit layout	41 ms, 3 region, 7 worker, 12 sequence, from 2026	More regions or workers	Many small cells (more machine bits)
Clock going back	Keep going on the last ms, refuse past 1 s	Exact timestamps right after a step	Timestamps had to be exact
Worker numbers	etcd lease, plus a mark fenced by time	Surviving an etcd outage over 30 s	No etcd at all (IDs made inside each database)
Scale	Client buffers of 100 ms	A few hundred IDs per crash, 100 ms of order	Calls were cheap and rates low
Regions	Independent fleets, 3 region bits	More than 8 regions	One region (bits go to workers)
Public IDs	Scrambled where volume matters	Sorting by public ID	Nothing about volume mattered

How to spend 45 minutes

0 to 5. Bits, ordering and rate. Say that 128 bits would mean UUIDv7 and no service.
5 to 10. 1.9 million a second, 4.1 million per worker, 128 workers, 70 years from your own start date.
10 to 18. Build it: one sequence, then leased ranges, then the bit layout and etcd worker numbers. A mid-level answer can stop here.
18 to 30. The stress tests: the backwards clock, then the zombie. These are the two duplicate bugs the question exists to find.
30 to 40. The bits budget and buffers, then what IDs reveal.
40 to 45. etcd failing, then your own questions.

Never skip the backwards clock or the zombie worker.

Follow-up questions

Interviewer asksA server's clock jumps a day into the future. What breaks?

That server makes IDs dated tomorrow, which sort after everything for a day. When its clock is corrected, it refuses, which is right, but the IDs already made stay wrong. So the defenses come first: refuse to start unless the clock is close, use several time sources so one bad one is outvoted, and alert on any server more than 500 ms from its peers.

Interviewer asksTwitter shows tweets in ID order. Can a reply sort before the tweet it replies to?

Yes, if they were made within the ordering limit on two different workers. If the replying server’s clock is 5 ms behind, its ID can be smaller. IDs give rough time order, not cause and effect. When that matters, readers sort replies after their parent.

Go deeperMore follow-up questions1 min

What happens during a leap second? With smeared time, nothing: clocks run slightly slow for hours and never repeat a second. Without smearing, the clock repeats 23:59:59, and the generator runs a full second ahead, right at its limit, so a burst can tip it into refusing. That thin margin is why we use smeared time.

Could you avoid wall clocks entirely? Yes, by giving up time order: leased ranges need no clock. A hybrid logical clock keeps time order and adds cause and effect, but every caller must pass along the largest ID it has seen.

Design a unique ID generator

The answer in one minute

Scope it

The numbers that decide it

Build the design

Step 1. One sequence in one database

Stage 1: One sequence in one database

Why this stage

What we add

What it costs

Step 2. Leased ranges

Stage 2: Leased ranges

Why this stage

What we add

What it costs

Step 3. IDs built from the clock

Stage 3: Snowflake IDs from the clock

Why this stage

What we add

What it costs

Step 4. Worker numbers from a lease

Stage 4: Clocks that go backwards

Why this stage

What we add

What it costs

Asking for IDs

Trace a request: Get one ID

Stress it

A clock that goes backwards

Two servers that both think they’re worker 7

The bits budget, and running out of servers

Stage 5: Batches in the caller

Why this stage

What we add

What it costs

Trace a request: ID from the buffer

What an ID gives away

When things break

Break it: what fails, who notices, what users see

What breaks

How we notice

What users see

What we do

Stage 6: Every region on its own

Why this stage

What we add

What it costs

Wrap up

The whole design

The full design, stage by stage

Why this stage

What we add

What it costs

The decisions, and what each one costs

How to spend 45 minutes

Follow-up questions

Further reading

Keep reading

The designbeyondcode digest, every Saturday