Design a Distributed Unique ID Generator

This page is one interview loop in three rounds. All three rounds design the same system. Each round opens with the interviewer raising the scope, and the design from the round before has to evolve to meet it.

You can start at any round. Rounds 2 and 3 open with a "Where we left off" summary that catches you up.

Loop Opener: What Is a Unique ID?

You Already Use One: the Auto-Increment Column

You have written this table many times:

sqlCopy
CREATE TABLE orders (
  id          BIGINT AUTO_INCREMENT PRIMARY KEY,
  customer_id BIGINT NOT NULL,
  total_cents BIGINT NOT NULL
);

Every insert gets the next number: 1, 2, 3, and so on. That number is unique, it is small (8 bytes), and it is sorted by insert order. All three properties come from one fact: one machine hands out every number. It keeps a counter, and nobody else touches it.

Where IDs like this show up:

What Changes When Many Machines Hand Out IDs

Put the counter on two machines and let each count on its own. Both will hand out 42, and two orders now share one key. One of them may silently overwrite the other.

We have two ways out:

• Talk to each other on every ID. Ask one central counter, or agree by vote. Every ID now costs a network round trip, and if the counter is down, nobody can create anything.
• Make a collision impossible by construction. Build each ID from parts that no other machine can produce at the same moment, so no machine ever needs to ask anyone.

This loop is about the second way, and about everything that can quietly break it.

The Question the Whole Loop Answers

How do we guarantee that no two IDs are ever the same, without machines talking to each other on every request?

The answer gets sharper every round:

• Round 1: each machine owns a unique machine number, and the ID is built from time, machine number and a counter.
• Round 2: we prove the machine number stays unique even when a machine freezes, loses its lease, or has the wrong time.
• Round 3: regions, decades, public exposure, and whether we should run this service at all.

---

Round 1 · Mid-level · "IDs for One Product's Database"

~35 min · SDE II (L5) · 1 region, 3 AZs · ~10K IDs/s peak · 99.9%

R1.1 Establish Design Scope

The interviewer says: "Design a service that generates unique IDs." Before we draw anything, we ask questions, and we say out loud what each answer changes.

Out of scope for this round:

• Gapless sequences ("invoice 1001 must follow invoice 1000"). They need one central counter, and nobody asked for it.
• Generating IDs in more than one region. The product runs in one AWS region.
• IDs shown to the public. Order IDs stay inside the company for now.

R1.2 Functional Requirements, Derived Step by Step

We read the problem one phrase at a time and turn each phrase into a requirement:

Not yet: asking for many IDs in one call, reading the creation time back out of an ID, and serving many calling teams. The interviewer may bring these back.

Why Sorted IDs Matter to a Database

A primary key in MySQL's InnoDB engine is a B-tree: a tree of fixed-size pages (16 KB by default) with keys kept in sorted order. Where a new key lands depends on its value.

• Random keys land on a random page. That page must be read into memory if it isn't there already, and when it is full it splits in two. Across a big table, almost every insert touches a different page, so the cache holds little that is useful. MySQL's documentation puts the result at pages anywhere from 1/2 to 15/16 full.
• Time-ordered keys always land at the right-hand edge of the tree. The same few pages stay hot in memory, and pages end up about 15/16 full.

textCopy
Random keys                               Time-ordered keys
[ 12 | 40 | 77 ]  ← insert 51 here         [ ... | 97 | 98 ]  ← every insert goes
[ 03 | 29 | 88 ]  ← insert 15 here                              to the last page
[ 55 | 61 | 90 ]  ← insert 58 here
every page is touched, many split          one hot page, few splits

This is why "roughly sorted" is a real requirement and not a nice-to-have. The database that stores our IDs pays for random keys on every insert.

R1.3 Non-Functional Requirements: the Questions

Numbers come in R1.7. For now, the questions and why each matters:

• Availability. Every write in the product needs an ID first. If we are down, nobody can place an order.
• Latency. We sit on the write path of every request, so our time is added to every order.
• Uniqueness. This is the one promise we can never break. A duplicate ID can make one customer's order overwrite another's, silently.
• Scalability. If demand grows, adding generators should add capacity, without the generators having to talk to each other.

R1.4 The API

One endpoint, internal only:

httpCopy
POST /v1/ids HTTP/1.1
Host: idgen.internal
Content-Type: application/json

{}

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json

{ "id": "97301141913751557", "id_num": 97301141913751557 }

We return the ID twice: id as a string, and id_num as a number for callers whose JSON parser keeps 64-bit integers. The reason fits in one line: JavaScript stores every number as a 64-bit float, which is only exact up to $2^{53}$, and our IDs are bigger. Step 1.6 comes back to this.

Recap

• One call, one 64-bit ID, returned as a string and as a number.
• IDs must be unique forever, roughly time-sorted, and fit a BIGINT.
• About 10,000 per second at peak; gaps are fine.
• We sit on every write, so we must be fast and always up.
• No coordination on the request path, if we can help it.

Let's build it, starting with the simplest thing that works.

R1.5 Design Evolution: From One Counter to Snowflake

Every step below follows the same pattern: a problem, your turn to think, the answer, and what the answer costs us. The cost is always the next problem.

Step 1.0: The Baseline

The database's own auto-increment column, or one small service with a counter in one database.

Synthesizing vector architecture diagram...

What's good about it: IDs are unique, 8 bytes, and strictly increasing. For a single database, this is the right answer and you should say so.

What it costs us: every ID comes from one machine. If it is down, nothing gets an ID. And when other databases or services need IDs from the same sequence, each ID is a network round trip to that one machine.

Step 1.1: The Counter Is a Bottleneck and a Single Point of Failure

Primitive: Distributed Unique ID Generators

Step 1.2: 64 Bits, and Sorted by Time

The bit budget, proved. Each field's size sets a limit we must live with.

$$\text{Timestamp lifespan} = \frac{2^{41} - 1 \text{ ms}}{1{,}000 \times 86{,}400 \times 365.25 \text{ ms/year}} = \frac{2{,}199{,}023{,}255{,}551}{31{,}557{,}600{,}000} \approx 69.7 \text{ years}$$ $$\text{Machines} = 2^{10} = 1{,}024 \qquad \text{IDs per ms per machine} = 2^{12} = 4{,}096 \;(\text{so } 4{,}096{,}000 \text{ per second})$$

We pick the custom epoch 2026-01-01T00:00:00Z, which is 1767225600000 ms in Unix time. Why not the Unix epoch of 1970? Because 41 bits of milliseconds counted from 1970 run out in 2039: we would throw away 56 of our 69.7 years on a period before the service existed. Counting from our launch, the last timestamp is $2^{41} - 1$ ms after the epoch, which is 2095-09-07T15:47:35.551Z.

textCopy
 bit 63  62 ─────────────────────────── 22  21 ──────── 12  11 ────────── 0
┌─────┬──────────────────────────────────┬───────────────┬────────────────┐
│  0  │ timestamp: ms since 2026-01-01   │ machine (10)  │ sequence (12)  │
│ (1) │ (41 bits, lasts ~69.7 years)     │ 0 … 1,023     │ 0 … 4,095      │
└─────┴──────────────────────────────────┴───────────────┴────────────────┘
 id = (timestamp << 22) | (machine << 12) | sequence

A worked example. An order created at 2026-09-26T12:00:00.000Z on machine 37, the sixth ID in that millisecond (sequence 5):

textCopy
timestamp = 1790424000000 − 1767225600000 = 23198400000 ms since our epoch
id        = (23198400000 << 22) | (37 << 12) | 5
          = 97301141913751557
binary    = 0 | 00000010101100110101110110111111000000000 | 0000100101 | 000000000101
            sign        timestamp (41)                    machine=37    sequence=5

Twitter's original Snowflake used the same 41 + 10 + 12 split, with its own epoch in November 2010. Many systems copy it with their own epoch, Discord's for example starts in 2015.

Primitive: Distributed Unique ID Generators

Step 1.3: More Than One ID in the Same Millisecond

Step 1.4: Two Workers Got the Same Machine Number

The lease table:

The claim, as a DynamoDB UpdateItem request:

jsonCopy
{
  "TableName": "idgen-leases",
  "Key": { "machine_id": { "N": "37" } },
  "UpdateExpression": "SET holder = :me, lease_expiry = :expiry",
  "ConditionExpression": "attribute_not_exists(machine_id) OR lease_expiry < :now",
  "ExpressionAttributeValues": {
    ":me":     { "S": "i-0a1b2c3d4e5f67890" },
    ":now":    { "N": "1790424000000" },
    ":expiry": { "N": "1790424030000" }
  }
}

If the condition fails, DynamoDB returns ConditionalCheckFailedException and changes nothing; the worker tries the next number. Note that :now comes from the worker's own clock: DynamoDB conditions have no "current time" function. Round 2 cares about that detail.

Primitive: Distributed Locks & Leases · Drill: Distributed lock fencing token

Step 1.5: The Clock Went Backwards

Synthesizing vector architecture diagram...

The clock is read on every ID. Only one branch refuses to answer, and it's the one where answering could repeat an ID.

Go deeper: how chrony can step, and how to stop it. Verified against the chrony documentation and AWS's EC2 guide.

textCopy
# /etc/chrony.conf on each worker
server 169.254.169.123 prefer iburst minpoll 4 maxpoll 4
makestep 1.0 3

• The server line is the one AWS documents for the Amazon Time Sync Service; minpoll 4 maxpoll 4 polls every 16 seconds. Amazon Linux 2023 is already set up to use it.
• makestep 1.0 3 allows stepping, it does not prevent it: chrony steps the clock if it is off by more than 1.0 second, but only during its first 3 clock updates after it starts. After that it only slews (unless someone runs chronyc makestep by hand). Without any makestep line, chrony normally slews and doesn't step on its own.
• Before a worker takes traffic, its start-up script runs chronyc waitsync, which waits until chrony reports the clock is synchronized. So any start-up step happens before the first ID.
• Slewing is fast enough: by default chrony may slew up to 83,333 ppm (1/12, set by maxslewrate), so at that maximum rate a 40 ms error is gone in under half a second of slower running, with no backwards step.
• The Amazon Time Sync Service smears leap seconds over time instead of inserting a 61st second, so the clock never repeats a second at a leap second.

Drill: Snowflake clock backward skew

Step 1.6: The Web App Shows the Wrong Order

Round 1 Step Summary

The open cost from step 1.4, a lease can expire while its worker is still running, is where Round 2 begins.

R1.6 Architecture v1

Now the concepts get AWS names.

Synthesizing vector architecture diagram...

Follow the solid arrows: a request goes from a caller through the load balancer to one worker, and the worker answers from memory. Nothing on that path talks to anything else. The dotted arrows are off the request path: the lease table is touched once at start-up and then every 10 seconds, and the time service is polled by chrony in the background.

The pieces:

• Workers: three EC2 instances in an Auto Scaling group, one per AZ. Each is a c7g.medium (1 Graviton vCPU, 2 GiB). The worker is one small process holding four values in memory: its machine number, its lease expiry, last_ms and sequence.
• Internal Network Load Balancer (NLB): a layer-4 load balancer, which passes TCP connections through without parsing HTTP. It checks each worker's /healthz, which returns 503 when the worker is refusing to make IDs.
• Lease table: DynamoDB, on-demand capacity. One row per machine number.
• Time: chrony on each instance, synced to the Amazon Time Sync Service.

Trace 1: one ID request.

Synthesizing vector architecture diagram...

The only network hops are the caller to the NLB to the worker and back. The ID is a few integer operations in memory.

Trace 2: a worker starts and claims its machine number.

Synthesizing vector architecture diagram...

The worker makes no ID until it has a synced clock and a machine number. It starts its search at a random number, so workers starting together don't all fight over slot 0. With only three workers, the first or second try almost always succeeds. (The trace shows the unlucky case: it happened to start on the slot of the worker it is replacing, whose lease hasn't expired yet.)

R1.7 Numbers and Bit Budget

Traffic against capacity.

One worker's sequence could handle 410 times our peak. The real limit on a worker is how many HTTP requests one vCPU can serve. We plan on 20,000 requests per second per c7g.medium. That is a planning assumption, not a measured fact: we confirm it with a load test before launch.

So why three workers? Not for throughput. For availability. One worker per AZ means losing a worker, or a whole AZ, leaves two workers with 40,000 requests/s of capacity against a 10,000 peak. It also lets us deploy one worker at a time.

Availability budget. 99.9% over a 30.4-day month allows $43{,}830 \text{ min} \times 0.001 \approx 43.8$ minutes of downtime. With three independent workers behind an NLB, a single worker failure costs us nothing; the budget is really for mistakes, such as a bad deploy or the lease table being misconfigured.

Latency. Making the ID takes well under a microsecond. P99 under 5 ms is almost all network: caller to NLB to worker and back inside one region.

The timestamp's lifespan (from step 1.2): 69.7 years from 2026-01-01, ending 2095-09-07.

IDs per year and what they cost downstream. We store nothing. The callers store every ID, as a key.

$$2{,}000 \text{ IDs/s} \times 31{,}557{,}600 \text{ s/year} \approx 6.3 \times 10^{10} \text{ IDs/year}$$

"Per copy" matters: an ID is stored once in the primary key, again in every secondary index, and again in every table that refers to it.

Monthly cost (us-east-1 on-demand prices, 730 hours a month):

Say it plainly in the interview: this service is tiny. The hard part is not throughput or cost. It is keeping one promise, never twice, while machines crash and clocks lie.

R1.8 Trade-Offs

UUIDv7 (RFC 9562, 2024) puts a 48-bit Unix timestamp in milliseconds at the front of a 128-bit UUID and fills most of the rest with random bits. ULID is an older design with the same idea: 48 bits of milliseconds and 80 random bits, usually written as 26 characters. Both sort by time and need no coordination at all. Their only problem here is size: 16 bytes don't fit a BIGINT.

Why Snowflake fits this scope: it is the only option that is 64-bit, time-sorted and free of per-ID coordination. We pay for that with two things to run: the machine-number leases and clock discipline. At this scope, that price is small.

R1.9 Failure Modes

R1.10 Pillar Check

R1.11 Round 1 Rubric and Follow-Ups

What a strong mid-level (L5) answer shows

• Asks whether IDs must be strictly ordered and whether gaps are allowed, and explains that "roughly ordered, gaps OK" is what makes a coordination-free design possible.
• Explains why sorted keys matter to a B-tree.
• Walks from one counter to the Snowflake layout, and says why each rejected option fails a requirement.
• Proves the bit budget: 69.7 years, 1,024 machines, 4,096 IDs per ms.
• Knows machine numbers must be assigned dynamically, and that the clock can go backwards.
• Sends IDs as strings to JavaScript clients, and knows why.

Follow-up questions

1. "Why a custom epoch instead of the Unix epoch?" Answer: 41 bits of milliseconds last 69.7 years from whatever start we choose. From 1970 they would run out in 2039, and the 56 years before our launch would be wasted. From 2026-01-01 they last until 2095-09-07.

2. "Why not make the sequence bigger and the machine field smaller? We only have three workers." Answer: we could: 41 + 5 + 17 gives 32 machines and 131,072 IDs per ms. But we don't need more per-machine throughput (we use 10 of 4,096 per ms), and machine numbers get used faster than you'd think: every deploy starts new workers before the old ones stop, and crashed workers hold their numbers for 30 s. Round 2 will need many more machine numbers, not fewer.

3. "A worker restarts. Could it repeat IDs it made before the restart?" Answer: its memory, including last_ms, is gone, so step 1.5's check can't help. What protects it is the lease table. The new process must claim a machine number again, and it can only claim a number whose lease has expired by its own clock. A healthy worker renews every 10 s, so every ID made under that number was made before the stored expiry, and every ID the new process makes comes after it. The one gap in this argument is a worker that keeps making IDs after its lease expired, for example because it froze and woke up. Round 2 closes that gap and turns this argument into a rule.

Interview gotchas from this round's wrong answers

---

Round 2 · Senior · "Every Service in the Company Needs IDs"

~40 min · Senior SDE (L6) · 1 region, 3 AZs · 300K IDs/s peak · 99.99% · zero duplicates, even when a worker freezes

R2.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 2. If you're starting here, it's everything you need from Round 1.

Round 1 in 60 seconds. "We built an ID service for one product's orders database: about 10,000 IDs a second at peak, one region, three AZs, 99.9% availability. IDs are 64-bit Snowflake IDs: 1 sign bit, 41 bits of milliseconds since a custom epoch of 2026-01-01, 10 bits of machine number and 12 bits of sequence. That gives 69.7 years, 1,024 machines, and 4,096 IDs per millisecond per machine. Each worker leases its machine number from a DynamoDB table with a conditional write, renews every 10 seconds on a 30-second lease, remembers its last timestamp, waits out a clock step back of up to 5 ms and refuses beyond that. Clocks sync to the Amazon Time Sync Service with chrony. IDs go to JavaScript as strings. Three small workers behind an internal NLB, about $110 a month. Three costs are still open: a worker can outlive its lease, every ID costs a network hop, and we only have 1,024 machine numbers."

The layout

textCopy
┌─────┬──────────────────────────────────┬───────────────┬────────────────┐
│  0  │ timestamp: ms since 2026-01-01   │ machine (10)  │ sequence (12)  │
│ (1) │ (41 bits, until 2095-09-07)      │ 0 … 1,023     │ 0 … 4,095      │
└─────┴──────────────────────────────────┴───────────────┴────────────────┘

Architecture v1, compact

textCopy
 services ──► internal NLB ──► 3 workers (c7g.medium), one per AZ
                                  │ id = (ts << 22) | (machine << 12) | seq, all in memory
                                  │ last_ms check: wait ≤ 5 ms back, refuse beyond
                                  ├── off the request path: DynamoDB idgen-leases
                                  │     claim if free or expired; renew every 10 s; 30 s lease
                                  └── chrony ◄── Amazon Time Sync (169.254.169.123)

Round 1 step summary

Open costs: a worker can outlive its lease; every ID costs a network hop; 1,024 machine numbers.

R2.1 The Scope Raise

Interviewer: "Your service worked. Now every team in the company wants it. We're at 100,000 IDs a second on average and 300,000 at peak. The data ingestion pipelines want IDs in batches of up to 1,000. A few high-volume services say even one network hop per ID is too slow for them. Teams want to read the creation time out of an ID. You must survive losing a whole AZ. And one more thing: a duplicate ID is now a company-wide incident. Zero duplicates, even when a worker freezes."

A scope raise is not the end of scoping. Before we fix anything, we ask back, and we say what each answer changes, just as in R1.1.

Scope change

The "Not yet" list from R1.2 is now mandatory: batches, decoding an ID, and many calling teams. The zero-duplicates-under-pauses requirement changes the design most.

R2.2 What Breaks in the Round 1 Design

R2.3 New Requirements and API Additions

Batches

httpCopy
POST /v1/ids:batch HTTP/1.1
Host: idgen.internal
Content-Type: application/json

{ "count": 1000 }

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json

{ "ids": ["97301141913751557", "97301141913751558", "..."] }

count must be 1 to 1,000, or the answer is 400 Bad Request. A batch is made by one worker in one pass, so its IDs are in increasing order. A batch of 1,000 fits in one millisecond's sequence (4,096), unless other requests on the same worker used most of that millisecond, in which case it spills into the next.

Decode

httpCopy
GET /v1/ids/97301141913751557/decode HTTP/1.1
Host: idgen.internal

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json

{
  "id": "97301141913751557",
  "created_at": "2026-09-26T12:00:00.000Z",
  "machine": 37,
  "sequence": 5,
  "layout": "v1"
}

Decoding is just shifts and masks, so the client library does it locally and nobody needs a network call for it. We still publish the endpoint, for people and tools, and so there is one official answer. It becomes important if the layout ever changes (Round 3 changes it).

Caller identity and quotas. Every caller connects with mutual TLS using a certificate issued per service (by AWS Private CA), so each connection carries a known identity, checked once when the connection opens. Each caller has a quota in IDs per second. Over quota, the answer is 429 Too Many Requests with Retry-After.

The embedded library. For callers that can't pay a hop, we ship the generator as a library that runs inside their process. It must keep every promise a worker keeps:

• It leases its own machine number from the same lease table, with the same rules (step 2.2), under an IAM role allowed to touch only that table.
• Its host runs chrony against the Amazon Time Sync Service, and the library refuses to start until the clock is synchronized.
• It enforces the same clock and lease checks as the service, and publishes the same metrics.
• The owning team upgrades it within a fixed window when we release a fix.

R2.4 Design Evolution: Making "Never Twice" Hold Under Failure

Step 2.1: A Network Hop per ID Is Too Slow

Step 2.2: A Worker Froze for 40 Seconds

The lease table, with the epoch (the row just after B's claim)

The claim (worker B, clock reading 1790424131000, one second after A's expiry of 1790424130000):

jsonCopy
{
  "TableName": "idgen-leases",
  "Key": { "machine_id": { "N": "37" } },
  "UpdateExpression": "SET holder = :me, lease_expiry = :expiry, lease_epoch = if_not_exists(lease_epoch, :zero) + :one",
  "ConditionExpression": "attribute_not_exists(machine_id) OR lease_expiry < :now",
  "ExpressionAttributeValues": {
    ":me":     { "S": "i-0fedcba9876543210/pid-907/1790424129000" },
    ":now":    { "N": "1790424131000" },
    ":expiry": { "N": "1790424161000" },
    ":zero":   { "N": "0" },
    ":one":    { "N": "1" }
  },
  "ReturnValues": "ALL_NEW"
}

The renewal (worker A, just awake at clock reading 1790424145000, still believing it holds epoch 7):

jsonCopy
{
  "TableName": "idgen-leases",
  "Key": { "machine_id": { "N": "37" } },
  "UpdateExpression": "SET lease_expiry = :new_expiry",
  "ConditionExpression": "holder = :me AND lease_epoch = :my_epoch AND lease_expiry < :new_expiry",
  "ExpressionAttributeValues": {
    ":me":         { "S": "i-0a1b2c3d4e5f67890/pid-4121/1790424000000" },
    ":my_epoch":   { "N": "7" },
    ":new_expiry": { "N": "1790424175000" }
  }
}

After B's claim, the row says holder B and epoch 8, so A's renewal fails with ConditionalCheckFailedException. A drops number 37 and, if it's healthy, claims a different free number. These examples use Round 1's 30-second lease, which is what we have at this point; step 2.5 lengthens it to 5 minutes, and nothing in this argument changes.

Why renewals check both the holder and the epoch. The holder name includes the process and its start time, so a process that crashed and restarted on the same instance is a new holder, not the old one. The epoch alone would catch a stale renewal in normal operation, but epochs can repeat if the table is ever restored from an old backup (step 3.2 deals with that). Requiring both to match means a stale holder's renewal can only succeed on a row that still names it, which is exactly the case where nobody else has the number.

Primitive: Distributed Locks & Leases · Drill: Distributed lock fencing token

Step 2.3: We Ran Out of Machine Numbers

Go deeper: other real layouts make different choices. Instagram's IDs (generated inside PostgreSQL) use 41 bits of milliseconds, 13 bits of logical shard and 10 bits of sequence, favouring many shards. Sony's Sonyflake uses 39 bits of time in units of 10 ms (about 174 years), 16 bits of machine ID and 8 bits of sequence: 65,536 machines, but only 256 IDs per 10 ms per machine. Its newer version lets you choose the bit split and time unit.

Primitive: Distributed Unique ID Generators

Step 2.4: One Caller Is Hammering One Worker

Primitive: Distributed Rate Limiting

Step 2.5: The Lease Table Is Down

Step 2.6: A Team Sorted by ID and Got the Wrong Order

Primitive: Distributed Consensus: Raft & Paxos

Round 2 Step Summary

R2.5 Architecture v2

Synthesizing vector architecture diagram...

Two paths share one lease table. Service callers reach the fleet through the NLB; the six approved callers generate IDs in their own processes. Both paths follow the same rules, so an ID's machine field is unique no matter which path made it.

Trace: a pause and a wake-up, with the fence marked. Times are wall-clock seconds, and the lease here is 30 s to keep the numbers short (the same argument holds for 5 minutes).

textCopy
wall-clock time (s)   100      105   110   120   125   130   131        145
                       │        │     │     │     │     │     │          │
worker A (epoch 7)   renew ✓   ID ── freeze ──────────────────────────► wakes
                     expiry=130 ts=105 (renewals at 110, 120 never sent)   │
                                                                           ├─ delivers the ID with ts=105
                                  fence = 130 − 5 = 125 ──┐                 │   (105 < 125: fine, and B only
                                                          │                 │    makes ts > 130)
                                                          ▼                 ├─ next request: ts=145 ≥ 125 → refuse
worker B                                                        claim ✓     └─ renewal "epoch 7" fails → drops #37
                                                                epoch 8
                                                                last_ms=131, makes ts ≥ 131

A's IDs all sit below 125; B's all sit above 130. The five-second gap between them is the margin. Nothing in this picture depends on A and B having the same time: each compares its own clock with the one number in the table.

R2.6 Numbers and Cost

Traffic and volume

We use the average for the yearly volume: a year at peak rate would overstate it three times.

Per-worker ceiling against demand. One machine's sequence allows 4,096,000 IDs/s, more than 13 times the whole company's peak. Again, requests are the limit, not IDs. We plan on 50,000 requests per second per c7g.large (2 vCPUs), an assumption we confirm by load test, and we assume the worst case of one ID per request (batches only make it easier).

Fleet size for AZ loss

$$\text{workers needed at peak} = \frac{300{,}000}{50{,}000} = 6$$

Those 6 must still be there after losing an AZ, so the two surviving AZs must hold them. Four workers per AZ gives 12 in total. After losing an AZ: $8 \times 50{,}000 = 400{,}000$ requests/s of capacity against a 300,000 peak, or 75% busy. Without the AZ loss, peak runs at $300{,}000 / 600{,}000 = 50\%$. We add no workers during an AZ loss, which matters because start-up depends on the lease table (step 2.5).

Lease-table request rate

$$\text{holders} = 12 \text{ workers} + {\sim}200 \text{ embedded processes} = 212$$

$212 \times \tfrac{1}{10 \text{ s}} = 21.2 \text{ writes/s} \;\Rightarrow\; 21.2 \times 2{,}629{,}800 \text{ s/month} \approx 55.8 \text{ M writes/month}$

At $0.625 per million on-demand writes, that is about $35 a month. The lease table never sees a request per ID: the fence check is in memory.

Monthly cost (us-east-1, on-demand)

The whole fleet costs less per month than the extra storage a year of 16-byte keys would add to callers' databases. That comparison comes back in Round 3.

R2.7 Trade-Offs

R2.8 Failure Modes

Drill: WebSocket reconnect thundering herd

R2.9 Production Gotchas

R2.10 Pillar Check

Alarms and first actions

R2.11 Round 2 Rubric and Follow-Ups

What a senior (L6) answer adds over L5

• Treats "never twice" as something to prove, and proves it through a pause, a clock step and a lost lease.
• Knows exactly what a fencing token protects (the lease row) and what it doesn't (IDs already issued), and puts the fence where the IDs are.
• Chooses which clock measures what: wall clock inside the ID and for the fence, monotonic for timers.
• Does the bit-budget math before moving bits, and rations before migrating.
• Sizes the fleet for AZ loss without new workers, and ties lease length to how long the lease table might be down.
• Writes down the ordering guarantee instead of letting callers assume one.

Follow-up questions

1. "Why not just make the lease 1 hour and forget about renewals?" Answer: the fence keeps it safe at any length, so it's a question of cost. A dead holder's number would stay unusable for an hour. With 64 service numbers and deploys needing 24, a bad afternoon of crash loops could exhaust the service range. Five minutes covers realistic lease-table outages and keeps reuse quick.

2. "A worker's clock jumps forward by 10 minutes. What happens?" Answer: uniqueness holds; ordering doesn't, unless we guard it. Right after the jump, its IDs' timestamps are past its fence, so it refuses. But its next renewal succeeds: the renewal only checks the epoch and that the expiry moves forward, and "now + 5 min" by a fast clock is further forward. From then on it would issue IDs that are still unique (number 37 is still only its own) but carry timestamps 10 minutes in the future, so they sort after everything the rest of the fleet makes for the next 10 minutes. That's why each worker also refuses, and fails its health check, whenever chrony reports it unsynchronized or more than 5 ms from the reference time, and why the clock-offset alarm fires on forward jumps as well as backward ones.

3. "Could we skip the lease table and use the instance's private IP, since IPs are unique in a VPC at any moment?" Answer: unique among running instances, yes, but IPs are reused as soon as an instance terminates, and 10 bits can't hold a VPC's address range without hashing, which brings back collisions. The replacement instance with a reused IP could also produce IDs in the same milliseconds as the previous owner if clocks differ. The lease table gives us the rule "the new holder starts after the stored expiry", and nothing about IPs gives us that.

Interview gotchas from this round

---

Round 3 · Architect · "Global, Forever, and Safe to Expose"

~45 min · Principal (L7) · 5 regions · ~2M IDs/s peak · 99.999% for issuing IDs · no cross-region call on the request path

R3.0 Where We Left Off

This is what the candidate says aloud in the first 60 seconds of Round 3. If you're starting here, it's everything you need from Rounds 1 and 2.

Round 2 in 60 seconds. "We run the company's ID service in one region across three AZs: 100,000 IDs a second on average, 300,000 at peak, 99.99%. IDs are 64-bit Snowflake IDs: 41 bits of milliseconds since 2026-01-01, 10 bits of machine number, 12 bits of sequence, so 69.7 years, 1,024 machines and 4,096 IDs per millisecond per machine. Twelve workers, four per AZ, run behind an internal NLB, and six approved high-volume callers run the generator as a library in about 200 of their own processes. Everyone leases a machine number from one DynamoDB table: a 5-minute lease, renewed every 10 seconds, with an epoch so stale renewals fail. The key rule is the timestamp fence: a holder never issues an ID timestamped within 5 seconds of its lease expiry, and a new holder only starts after the stored expiry, so two holders of the same number can never produce the same ID, whatever pauses or clock skew happen. IDs are k-sorted, not strictly ordered. About $1,050 a month. Four costs are still open: it's one region; the timestamp runs out in 2095; IDs reveal volume and timing; and it's 64-bit only."

The layout (v1)

textCopy
┌─────┬──────────────────────────────────┬───────────────┬────────────────┐
│  0  │ timestamp: ms since 2026-01-01   │ machine (10)  │ sequence (12)  │
└─────┴──────────────────────────────────┴───────────────┴────────────────┘

Architecture v2, compact

textCopy
 most services ──(mTLS, batches, buffers)──► internal NLB ──► 12 × c7g.large (4 per AZ), numbers 0–63
 6 big callers: embedded library in ~200 processes, numbers 64–1,023
 everyone ──► DynamoDB idgen-leases: conditional claim (+1 epoch), renew every 10 s, 5 min lease
              fence: never issue ts ≥ expiry − 5 s; new holder starts after the stored expiry
 chrony on every host ◄── Amazon Time Sync; refuse if > 5 ms off or clock went back > 5 ms

Steps so far

Open costs: one region; the timestamp ends on 2095-09-07; IDs reveal volume and timing; 64-bit only.

R3.1 The Scope Raise

Interviewer: "We're going global: five regions, each creating records on its own, and we must survive losing a whole region. Peak is about 2 million IDs a second worldwide. Order IDs now appear in public URLs, and we've learned a competitor is estimating our daily order volume from them. We also acquired a company whose IDs are all UUIDv7. And the board wants this platform to outlive your 69-year timestamp without a flag day, meaning no single day when everything must switch at once."

Again, we ask back before we design:

Scope change

R3.2 What Breaks in the Round 2 Design

R3.3 New Requirements and API Additions

• Region-aware IDs. Every ID says which region made it, and a region registry assigns each region a number that is never reused.
• A public-facing ID that reveals nothing, used in URLs and anything a customer sees.
• A plan for mixed 64/128-bit IDs, and for the timestamp's end.
• A documented ordering guarantee across regions.
• Decode now returns the region and the layout version:

httpCopy
GET /v1/ids/683244571854022659/decode HTTP/1.1
Host: idgen.internal

httpCopy
HTTP/1.1 200 OK
Content-Type: application/json

{
  "id": "683244571854022659",
  "layout": "v2",
  "created_at": "2031-03-01T09:30:00.000Z",
  "region": "eu-west-1",
  "region_number": 2,
  "machine": 170,
  "sequence": 3
}

R3.4 Design Evolution: Regions, Decades and Exposure

Step 3.1: Five Regions Must Issue IDs Independently

The v2 layout, proved

$$\text{Regions} = 2^3 = 8 \qquad \text{Machines per region} = 2^9 = 512 \qquad \text{IDs per ms per machine} = 2^{10} = 1{,}024$$ $$\text{Machines worldwide} = 8 \times 512 = 4{,}096 \qquad \text{Timestamp: still 41 bits, still ends 2095-09-07}$$

textCopy
 bit 63  62 ──────────────────────── 22  21 ─ 19  18 ────── 10  9 ────── 0
┌─────┬───────────────────────────────┬────────┬─────────────┬───────────┐
│  0  │ timestamp: ms since 2026-01-01│ region │ machine (9) │ seq (10)  │
│ (1) │ (41 bits)                     │  (3)   │ 0 … 511     │ 0 … 1,023 │
└─────┴───────────────────────────────┴────────┴─────────────┴───────────┘
 id = (ts << 22) | (region << 19) | (machine << 10) | sequence

Example: an order in eu-west-1 (region 2), machine 170 (an embedded library in the order service), sequence 3, at 2031-03-01T09:30:00.000Z, which is 162898200000 ms after our epoch:

textCopy
id = (162898200000 << 22) | (2 << 19) | (170 << 10) | 3 = 683244571854022659

Changing the layout without a flag day: let the timestamp choose. Both layouts keep the timestamp in the same 41 bits, so any reader can find an ID's timestamp before knowing its layout. We pick a cutover time, T = 2028-01-01T00:00:00Z (63,072,000,000 ms after the epoch):

• An ID whose timestamp is before T is decoded as v1; at or after T, as v2.
• Every generator gets the v2 configuration months ahead. A generator without it refuses to issue any ID timestamped at or after T.
• In the weeks before T, each generator in us-east-1 also claims a v2 number from the new region-local lease table. It uses its v1 number for timestamps before T and its v2 number after.

Uniqueness across the switch follows from the same idea as the Round 2 fence: every v1 ID has a timestamp before T and every v2 ID has one at or after T, so they can't be equal. The only coordinated moment is a time written in a config file, not a day when everyone changes code.

Primitive: Distributed Unique ID Generators

Step 3.2: A Region Is Gone

Primitive: Cloud Disaster Recovery & Multi-Region Active-Active

Step 3.3: Which of These Two IDs Came First?

Step 3.4: A Competitor Counts Our Orders From Our Public IDs

Step 3.5: Two ID Formats, and the Timestamp Runs Out in 2095

UUIDv7 next to Snowflake

textCopy
UUIDv7 (RFC 9562), 128 bits
┌──────────────────────────────┬──────┬──────────┬────┬───────────────────────────────┐
│ unix_ts_ms (48)              │ ver  │ rand_a   │var │ rand_b (62)                   │
│ ms since 1970-01-01          │ 0111 │ (12)     │ 10 │                               │
└──────────────────────────────┴──────┴──────────┴────┴───────────────────────────────┘
Snowflake v2 (ours), 64 bits
┌───┬──────────────────────────┬────────┬───────────┬──────────┐
│ 0 │ ms since 2026-01-01 (41) │ region │ machine   │ sequence │
│   │                          │  (3)   │   (9)     │  (10)    │
└───┴──────────────────────────┴────────┴───────────┴──────────┘

RFC 9562 also lets an implementation use rand_a for extra timestamp precision or a counter, so IDs made by one process in the same millisecond stay in order; that trades random bits for ordering. It also defines version 8 for custom layouts, which is one way to carry a 64-bit ID inside a 128-bit column if a single column type is ever needed.

Primitive: Distributed Unique ID Generators

Step 3.6: Should We Even Run This Service?

R3.5 Global Architecture

Synthesizing vector architecture diagram...

Each region is complete on its own: its generators, its lease table and its callers never cross a region on the normal path. The region registry is the only thing shared, and it changes only when a region is added. The dotted cross-region arrow is used only when a region's own generators are down. Customers only ever see the public ID.

Trace 1: an order is created in eu-west-1 and shown publicly.

Synthesizing vector architecture diagram...

The internal ID is made in memory with no network call and never leaves the company. The public ID reveals nothing, so the competitor's decoder gets nothing.

Trace 2: eu-west-1's generator fleet fails. Its NLB health checks fail for all 24 workers. The client library in eu-west-1 services tries its local endpoint, gets connection errors, and moves to its configured backup, the us-east-1 endpoint, through Transit Gateway inter-region peering. Those IDs carry region number 0. Embedded libraries in eu-west-1 don't notice at all. When the eu-west-1 fleet is healthy again, clients move back after their next health probe. No machine number or lease moved anywhere.

R3.6 Numbers and Cost

Peak per region (a planning split)

Average is about a third of peak, as in Round 2: ≈ 667K IDs/s.

Fleet per region. We keep the planning figure of 50,000 requests/s per c7g.large and still assume one ID per request. We run the same shape everywhere, 24 workers, 8 per AZ, which is 1.2M requests/s of capacity per region. That covers the two cases we plan for, one at a time:

• Losing an AZ in the busiest region: $16 \times 50{,}000 = 800{,}000 \ge 600{,}000$ peak (75% busy).
• Absorbing another region's callers: the worst pair is us-east-1 taking eu-west-1's callers: $600\text{K} + 500\text{K} = 1.1\text{M} \le 1.2\text{M}$ (92% busy).

Smaller regions have more headroom than they need; one fleet shape everywhere keeps operations simple, and at $53 per worker per month the extra is cheap.

Per-machine headroom. Each machine can make 1,024 IDs per millisecond. A worker at its planned 50,000 requests/s averages 50 per millisecond, so the sequence only matters for batches: one batch of 1,000 fits in a millisecond, and two in the same millisecond spill into the next.

The v2 bit budget (step 3.1): 8 regions, 512 machines per region, 1,024 IDs per ms per machine, 41-bit timestamp ending 2095-09-07.

Downstream key storage: the biggest real cost is in the callers' databases.

$$667{,}000 \text{ IDs/s} \times 31{,}557{,}600 \text{ s/year} \approx 2.1 \times 10^{13} \text{ IDs/year}$$

If every ID were stored as a key about three times (primary key, one foreign key, one secondary index), 16-byte keys would add about $3 \times 168 \approx 505$ TB a year. At an illustrative $0.10 per GB-month (the Aurora standard storage price in us-east-1), each year of such data would cost about $50K more per month, every month it's kept, before any cross-region copies. (Aurora's price already covers its six copies across three AZs, and its replicas share that storage.) That is an upper bound, since not every ID becomes a stored key, but it's the right order of magnitude to compare with the fleet below.

Fleet and lease-table cost (us-east-1 prices; other regions cost somewhat more)

Cross-region traffic only flows during a fleet failure, over the company's existing Transit Gateway peering, so we don't count it here.

The public-ID mapping. Assume 30 million public orders a day, which is about $1.1 \times 10^{10}$ a year. Each needs a 16-byte public_id column and a unique-index entry holding that value and a pointer to the row (about 40 bytes), say 50 bytes with overhead:

$1.1 \times 10^{10} \times 50 \text{ B} \approx 550 \text{ GB/year} \;\Rightarrow\; \approx \$55/\text{month per year of data at } \$0.10/\text{GB-month}$

The encrypted option would cost almost nothing in dollars (one KMS key at $1 a month and a few KMS calls at start-up), but it carries the key-leak risk from step 3.4.

The lesson in one line: the generator costs about $9K a month; the size of the keys it hands out costs the company far more. That's why step 3.6 turns on key size, not on the service's bill.

R3.7 Trade-Offs

The opening question was: how do we guarantee no two IDs are ever the same, without machines talking to each other on every request? The answer is now: by construction (region, machine and time bits, fenced by leases), per region (no region ever asks another), and hidden from the public (customers see only an opaque ID). For most new systems, the answer is even simpler: 74 random bits, and a unique constraint as the safety net.

R3.8 Failure Modes

R3.9 Runbook and Incident Response

Golden signals, per region OPS 8 · REL 6

Duplicate-ID incident procedure OPS 10

1. Detect. Callers' unique constraints reject the second insert, and a daily Athena job over exported data counts any ID that appears twice.
2. Decode the duplicate. The ID itself says the time, region and machine number. That's the whole search space.
3. Find the holders. Every claim, renewal and release is logged with holder, epoch and expiry. List who held that machine number in that region around that time.
4. Contain. Quarantine the machine number (so nobody can claim it), stop the holders involved, and take their hosts out of service.
5. Assess. List the records created with IDs from that number in the window, find which ones collided, and fix them with the owning teams.
6. Learn. A blameless Correction of Error (COE). A duplicate means one of our invariants failed (a clock, a restore, a misconfigured region number, a library bypassing the fence), so the action items must close that path for good.

Clock-step procedure. If a host's clock was stepped: take it out of service (the worker has usually done so itself), confirm what stepped it from the chrony log and the instance's events, and replace the host rather than repair it. The replacement claims a fresh number and starts after that number's stored expiry. If many hosts in a region stepped at once, suspect the time source or a bad configuration push, and halt deploys in that region.

Go deeper: CLI playbook

Plain commands an on-call engineer runs, one at a time. Replace the IDs and ARNs with real ones.

textCopy
# 1. Who holds which machine number in a region right now
aws dynamodb scan --region eu-west-1 --table-name idgen-leases-v2 --projection-expression "machine_id, #h, lease_expiry, lease_epoch" --expression-attribute-names '{"#h": "holder"}'

# 2. One machine number's lease
aws dynamodb get-item --region eu-west-1 --table-name idgen-leases-v2 --key '{"machine_id": {"N": "170"}}'

# 3. Quarantine machine number 170: expiry far in the future (year 2100), new epoch, so nobody can claim or renew it
aws dynamodb update-item --region eu-west-1 --table-name idgen-leases-v2 --key '{"machine_id": {"N": "170"}}' --update-expression "SET #h = :q, lease_expiry = :far ADD lease_epoch :one" --expression-attribute-names '{"#h": "holder"}' --expression-attribute-values '{":q": {"S": "QUARANTINED"}, ":far": {"N": "4102444800000"}, ":one": {"N": "1"}}'

# 4. Clock status on every generator host in a region
aws ssm send-command --region eu-west-1 --document-name "AWS-RunShellScript" --targets "Key=tag:Service,Values=idgen" --parameters 'commands=["chronyc tracking"]'

# 5. Which workers the NLB considers healthy
aws elbv2 describe-target-health --region eu-west-1 --target-group-arn arn:aws:elasticloadbalancing:eu-west-1:111122223333:targetgroup/idgen-workers/0123456789abcdef

# 6. Take one worker out of the NLB
aws elbv2 deregister-targets --region eu-west-1 --target-group-arn arn:aws:elasticloadbalancing:eu-west-1:111122223333:targetgroup/idgen-workers/0123456789abcdef --targets Id=i-0a1b2c3d4e5f67890

# 7. Alarms currently firing for the generator
aws cloudwatch describe-alarms --region eu-west-1 --state-value ALARM --alarm-name-prefix idgen

# 8. Look for duplicate IDs in exported order data for an incident window
aws athena start-query-execution --region eu-west-1 --work-group primary --query-string "SELECT id, COUNT(*) AS n FROM orders_export WHERE created_at BETWEEN TIMESTAMP '2031-03-01 09:00:00' AND TIMESTAMP '2031-03-01 10:00:00' GROUP BY id HAVING COUNT(*) > 1"

4102444800000 is 2100-01-01T00:00:00Z in Unix milliseconds. Quarantine works because a claim needs lease_expiry < :now and a renewal needs its own holder name and epoch; this update changes both, so it defeats both. The current holder still stops at its own fence, so command 6 (or stopping the process) is what stops it immediately.

R3.10 Pillar Check

R3.11 Round 3 Rubric and Follow-Ups

What an architect (L7) answer adds over L6

• Sets a company-wide ID strategy: which format for which use, who may use the service, and what the ordering guarantee is.
• Uses bit budgets as a design tool: region bits make regions independent by construction, and the timestamp doubles as a layout version.
• Plans migrations with no flag day: the layout cutover by timestamp, and UUIDv7 for new data while old IDs stay valid forever.
• Treats IDs as information that leaks, and separates internal and public identity.
• Finds where the cost really is (key size in other teams' databases) and lets that drive the decision.
• Is willing to answer "do we even need this service?" with numbers, and to shrink their own system.

Follow-up questions

1. "We add a sixth, seventh and eighth region, and then a ninth. What happens?" Answer: three bits give eight region numbers, and retired numbers are never reused, so the ninth region can't get one. Options: the ninth region runs UUIDv7 only, which step 3.6 makes the default anyway; or we change the layout again, for example 41 + 4 + 8 + 10, with another timestamp cutover. We'd know years ahead, because the registry shows how many numbers are left.

2. "Why not encrypt the internal ID and skip storing public IDs? It's free." Answer: it's free in dollars. But one key then protects every public ID we've ever issued: if it leaks, anyone can decode all of them, and nothing can un-leak the old links. Rotating the key changes every public ID unless we version it. A random public ID has nothing to leak, and it costs about $55 a month per year of orders. Encryption is the right tool only when a table can't take a column.

3. "A team wants to generate Snowflake IDs in a browser app to create records offline." Answer: no. A browser can't hold a lease reliably, its clock is whatever the user set, and it would need a machine number per device. Browsers use UUIDv7 (or UUIDv4) generated locally, which is unique by chance, and the server can assign a Snowflake ID later if the table needs one.

---

Loop Closer: Interview Strategy for All Three Rounds

How to Run Each 60-Minute Round

For how to spend a single 45-minute round, see the 45-minute interview blueprint.

The Two Sentences That Matter Most

• Opening a round: "Before I design, let me ask a few scoping questions: must IDs be strictly ordered, and are gaps allowed?"
• When the scope is raised: "Here's what breaks in the current design, and here's the order I'll fix it in, starting with anything that could produce a duplicate."

Well-Architected Review Sheet

Interviewers rarely ask "which pillar is this?". They ask the pillar's question in plain words. Rehearse one sentence per row.

Rubric Across Levels