07 — Design a Unique ID Generator in Distributed Systems

“Design a service that hands out unique IDs across a fleet. 64 bits. They must sort by creation time.”

Every row in every database needs a name that no other row has — an identifier, or ID.

On one machine you get that for free by counting: 1, 2, 3. One process owns the counter, so nobody can hand out the same number twice.

Across a fleet of machines, nobody owns the counter. You could elect one machine to own it, but then every write in the system waits on a network call to that machine. The whole design exists to avoid that call.

So the job — derived here from arithmetic rather than from recall — is to hand out identifiers that are:

• unique across the whole fleet,
• sorted in the order they were created,
• 64 bits wide,
• and produced without asking anyone.

The resulting design then gets taken apart at the two places it actually fails: the machine’s clock, and the way each machine learns its own number.

When you finish, you should be able to say out loud, without looking anything up:

• how many years 41 bits of milliseconds buys, and how you got there;
• exactly what happens on a machine when the clock is stepped backwards by 300 ms;
• why a 128-bit random identifier is a performance bug rather than a complaint about size;
• when to throw the whole design away and use UUIDv7 instead.

What goes in and what comes out. Nothing goes in. That is the entire point. The block below shows one call and what the returned integer contains when you take it apart again:

next_id()  ->  141264821508263936        a 64-bit integer

decoded, that integer is:
    epoch_ms   1737747358021             when it was created, to the millisecond
    node_id    37                        which generator made it
    sequence   0                         which one it was inside that millisecond

The input is empty because a network round trip to ask anyone for a number is exactly what the design exists to avoid.

The output is one integer that packs three fields into 64 bits, and reversing the packing recovers all three. The best-known scheme for doing that is Snowflake, named after the internal Twitter service that popularised it. This chapter derives it rather than quoting it.

The whole chapter is a bit budget. 64 bits is a fixed quantity. Every design decision spends some of it:

• how far into the future the format keeps working,
• how many machines may generate at once,
• how many identifiers one machine can produce inside a single millisecond,
• and the time-sortability that lets the identifier double as a database primary key.

There is no slack anywhere. Every choice is forced by arithmetic, which is exactly why interviewers keep asking the question.

1. Framing: what decision is actually on the table

The question is never “produce distinct numbers.” Distinctness is free — hash a random 128-bit value and you are done. The real question is which of four properties you are willing to give up.

Three terms the table below assumes

• A primary key is the column a database uses to identify a row uniquely. It is usually also the column the rows are physically ordered by on disk.
• A B-tree is the index structure almost every relational database uses for that ordering. The one property that matters here: inserting at the end of it is cheap, inserting into the middle of it is not.
• A cursor is a pagination technique. Instead of “give me rows 500 to 600,” you say “give me the 100 rows after this ID.” That only works if IDs increase over time.

The four properties, and what each one costs

Read the table as four wishes and their price tags. The last column is the one to pay attention to: each property is paid for out of the same 64 bits, so no two of them are independent.

Three of those cells are shorthand and need unpacking.

BIGINT is the standard SQL type for a 64-bit signed integer. An ID that fits one needs no schema change anywhere.

“JS-unsafe” means JavaScript cannot represent a 64-bit integer exactly. It stores every number as a floating-point double, which is exact only up to 2^53; above that, parsing an ID silently rounds it. So a 64-bit ID has to cross an API boundary as a string. That detail costs real teams real days and reappears in Failure modes.

A shard hint means that, because the high bits are a timestamp, the ID itself tells you which time-based partition a row lives in — you can route a lookup without consulting any index.

Say this in the first minute: “uniqueness is the easy part; the design is about buying time-ordering and 64-bit width without a network round trip, and those three constraints together are what make the answer a bit layout rather than an algorithm.”

Four candidates, three of them eliminated

There are four candidate designs. Each one wins or fails for a specific, statable reason — and the reason is the answer, not the name.

flowchart TD
    Q["Need a unique 64-bit,<br/>time-sortable ID"]
    Q --> A["Multi-master auto-increment<br/>step N, offset i"]
    Q --> B["UUIDv4<br/>122 random bits"]
    Q --> C["Ticket server<br/>one counter, everyone asks"]
    Q --> D["Snowflake<br/>time | node | sequence"]

    A --> A1["FAILS: resizing the fleet<br/>changes every future ID.<br/>Order across masters tracks<br/>issue rate, not time"]
    B --> B1["FAILS: 128 bits, and the<br/>high bits are random.<br/>Kills the B-tree PK"]
    C --> C1["FAILS: batching is required<br/>for throughput, and batching<br/>destroys the time order<br/>you asked for"]
    D --> D1["WINS: no round trip,<br/>64 bits, monotone per node.<br/>Cost: a clock you must trust"]

    style D fill:#2d6a4f,color:#fff
    style D1 fill:#2d6a4f,color:#fff
    style A1 fill:#9d0208,color:#fff
    style B1 fill:#9d0208,color:#fff
    style C1 fill:#9d0208,color:#fff

The colour key for this chapter carries a verdict, not a component’s role. Green is the option this chapter takes. Red is one it rejects. In High level architecture, orange marks the input you have to configure rather than assume (the clock), and blue marks the store you talk to at startup and never per identifier. That is not the key chapter 01 uses — ch 01 reads the same hex colours as roles, where green means “takes load off the request path,” and that reading is exactly wrong here: the whole argument of Library or service is that the library sits on the request path, in-process, and that is why it wins.

Now walk the four boxes. The question at the top is: you need a unique 64-bit, time-sortable ID.

Multi-master auto-increment. Every database server counts by N, each starting from a different offset i. With N = 3, server 1 emits 1, 4, 7 and server 2 emits 2, 5, 8. It fails twice over. Resizing the fleet changes N, and therefore changes every future ID. And the interleaving tracks how fast each master is issuing, not what time it is.

UUIDv4. 128 bits, 122 of them random. It fails on width, and on the randomness of its leading bits, which destroys the primary-key B-tree. That is Deep dive 1 why a uuid loses and where exactly, where the cost is turned into two reproducible numbers.

Ticket server. One shared counter that every machine asks for numbers. It fails because reaching the required throughput forces you to hand out numbers in blocks, and handing out blocks destroys the very time-ordering you asked for. That is Alternatives rejected.

Snowflake — time | node | sequence. This one wins: no round trip, 64 bits, and identifiers that increase monotonically on each machine. Its cost is a clock you have to trust, which is Deep dive 2 clock skew leap seconds and the rewind.

2. Requirements

Functional

• next_id() returns a 64-bit integer, unique across the entire fleet, forever.
• IDs are monotonically increasing with respect to creation time, to within the fleet’s clock skew. Monotonic means the sequence never goes down: an ID issued later is always numerically larger.
• An ID is decodable back into (timestamp, node, sequence), which is what makes a stray ID in a log debuggable.

Two clock terms you will need for the rest of the chapter, and they are not the same thing. Clock skew is the difference between two machines’ idea of the current time right now — machine A says 12:00:00.010, machine B says 12:00:00.000, that is 10 ms of skew. Clock drift is the rate at which one machine’s clock gains or loses time against true time — a clock that runs 1 second fast per day is drifting, and skew is what drift accumulates into.

Non-functional

Five numbers. The middle two are the ones that shape the design; the fourth quietly decides the whole architecture.

Three of those rows need unpacking.

p99 is the 99th percentile latency: the number that 99 of every 100 calls come in under. It is the tail, not the average, and it is what a caller actually experiences when things are busy.

Availability is the fraction of the time a component is actually answering rather than failing or unreachable. It is usually quoted as a run of nines: 99.9% is about 8.8 hours of unavailability a year, 99.99% about 52 minutes. The reason it is a requirement here rather than an aspiration is that availabilities multiply along a dependency chain. A generator that is up 99.9% of the time caps every write behind it at 99.9%, however good the database is — because a write cannot happen without an ID.

A fan-out write is one user action that produces many rows: one post inserted into the feeds of every follower. This is why the burst figure and the average figure look so different. Averaged over a second the system wants 30,000 IDs; but a single fan-out can ask for 100,000 identifiers inside one millisecond, and the generator has to survive that spike, not the average.

The availability line is the one to say out loud: an ID generator sits in front of every write in the system, so its availability multiplies into everything downstream. That single fact is why the answer is a library rather than a service — and Library or service is where that choice comes due.

3. Back-of-envelope

Running out of 64-bit identifiers is not a risk anyone faces, and establishing that reframes the whole problem from “will we have enough numbers?” to “how do we spend the bits?” Generic estimation technique is chapter 02; the four numbers below are the ones this design actually spends.

The block below is one chain, read top to bottom. It works out how many IDs a decade of traffic needs, then how many a 64-bit column holds, then divides one into the other. 86400 is seconds in a day; 365.25 is days in a year, averaged over leap years.

IDs per day at the mean rate
  30,000 * 86400                        =  2,592,000,000

IDs over a ten-year lifetime
  2,592,000,000 * 365.25 * 10           =  9,467,280,000,000

the positive half of a signed 64-bit column
  2^63                                  =  9,223,372,036,854,775,808

headroom, as a multiple of a decade of traffic
  9,223,372,036,854,775,808 / 9,467,280,000,000  =  974,000

Only the positive half of the range is usable, because a BIGINT is signed and negative IDs would sort before positive ones. That is why the third line is 2^63 and not 2^64.

You consume roughly one millionth of the positive 64-bit space in ten years, so exhaustion is never the constraint — the layout is.

To see how little of the space a plain counter would actually need, compare that decade of traffic (9,467,280,000,000) against the two nearest powers of two:

2^43                                    =  8,796,093,022,208
2^44                                    =  17,592,186,044,416

A decade of traffic sits between them, so 44 bits covers it. That is with a dense counter — one that issues every value in order with no gaps.

So a coordinated counter would need 44 of the 64 bits, and 64 - 44 = 20 bits are left over. Those 20 bits are what you spend to avoid ever asking another machine for a number. Say that framing out loud: twenty bits is the price of coordination-freedom, and Snowflake spends them on a node id and a counter that runs inside a single millisecond.

One warning that the rest of the chapter keeps returning to: it is the burst number that sizes the fleet, not the average throughput number, and 5c 12 bits of sequence is where that arithmetic is done.

4. API sketch

The generator can ship in exactly two shapes, and Library or service decides between them. One detail about reading an ID catches people out along the way.

As a library, in-process (the default) — meaning the generator is a piece of code linked into the application itself, so calling it is a function call rather than a network request:

gen = Snowflake(node_id=37)
gen.next_id()          -> 141264821508263936
Snowflake.decode(x)    -> {"epoch_ms": 1737747358021, "node_id": 37, "sequence": 0}

That literal 141264821508263936 is checked against the layout by an executable assertion in Working python, and it is worth saying why it has to be.

The fields are packed as elapsed << 22 | node << 12 | seq. << shifts a value left by that many bit positions, which in decimal terms multiplies it by 2^22 and 2^12; | then merges the three shifted fields into one integer, which works precisely because their bit ranges do not overlap. Data model the 64 bit layout derived does that arithmetic in full with this exact ID.

The consequence to internalise: the decimal digits of an ID tell you nothing about its fields. An ID whose printed form happens to end in “37” is not node 37. The test in Working python uses 141264821510144037 — same timestamp, ends in “37” — and it decodes to node 496, sequence 37. A plausible-looking constant in a document is exactly how a reader ends up with a mental model that contradicts the arithmetic one section later.

As a service, over the network, if you must — meaning a separate cluster of machines that hands out identifiers over RPC, a remote procedure call, which is a function call that crosses the network:

POST /v1/ids            {"count": 100}
  200 {"ids": [...], "node_id": 37, "epoch_ms": 1704067200000}
GET  /v1/health         -> 503 while the node's clock is unusable

Look at the second line, the one that returns 503. That health check is the operational half of the whole design: a node whose clock has moved backwards must fail its health check, so a load balancer stops sending it traffic, rather than quietly carrying on.

A load balancer is the machine that owns the service’s public address and forwards each incoming call to one of the identical nodes behind it. It polls each node’s health endpoint every few seconds and removes any node that answers badly. So “fail the health check” is the entire mechanism by which one sick node stops receiving work — no operator involved.

That mechanism is also why, in Deep dive 2 clock skew leap seconds and the rewind, a fault that hits one node degrades gracefully while a fault that hits all of them at once does not: a load balancer can route around one bad node, and cannot route around a thousand.

Bandwidth is a non-issue, and it is worth closing off explicitly so nobody spends interview time on it:

payload per call, 100 IDs * 8 bytes     =  800 bytes
calls/s at the 100,000 IDs/s peak
  100,000 / 100                         =  1,000
bytes/s
  1,000 * 800                           =  800,000      (~0.8 MB/s)

Against a 1 Gbps network card, that is under 1% of the link. The RPC is a latency tax and a new dependency, never a bandwidth problem — which is why the argument against the service form is about availability rather than about capacity.

5. Data model: the 64-bit layout, derived

The “data model” here is the bit budget, because there is nothing else — no tables, no records, no schema. Each of the four fields is derived from a requirement, changing one moves the others, and the reallocation table at the end proves the budget is zero-sum.

The diagram below is one 64-bit integer drawn as a row of bits, numbered from the left. Bit 63 is the most significant bit, bit 0 the least. The numbers 22 and 12 above the boxes are the bit positions where one field ends and the next begins — remember those two, because they are the shift amounts in every line of code later.

 63  62                                            22          12         0
+---+----------------------------------------------+-----------+----------+
| 0 |            timestamp: 41 bits of ms           | node: 10  | seq: 12  |
+---+----------------------------------------------+-----------+----------+
  |                                                       |          |
  sign bit, always 0                                   1,024      4,096
  so the value is positive in a signed BIGINT          nodes      per ms

The same thing as a plain tally, to check the budget closes:

sign         1
timestamp   41
node id     10
sequence    12

The fields add up exactly: 1 + 41 + 10 + 12 = 64. Read the layout from the left.

• Sign bit, 1 bit. Every signed integer type reserves its top bit to say whether the value is negative. Pinning it to 0 keeps every ID a positive number in a BIGINT column, so ordering by the ID never surprises anyone.
• Timestamp, 41 bits. A count of milliseconds since a chosen starting instant.
• Node id, 10 bits. Which generator produced this ID.
• Sequence, 12 bits. A counter distinguishing IDs made by the same generator inside the same millisecond.

The order is not arbitrary. The timestamp is the most significant field, so comparing two IDs as plain integers compares their timestamps first — which is the entire reason the IDs sort by time. Put the node id first instead and you would be sorting by machine.

How the three fields become one integer

Packing is elapsed << 22 | node << 12 | seq. Shifting left by n bits is multiplying by 2^n, and because the three fields occupy non-overlapping bit ranges, | (bitwise OR) just drops each one into its own slot. Here is that arithmetic done with the ID from Api sketch, for node 37 at sequence 0:

wall clock                        1,737,747,358,021 ms
epoch (2024-01-01)                1,704,067,200,000 ms
elapsed = 1,737,747,358,021 - 1,704,067,200,000
                                     33,680,158,021   fits in 41 bits

elapsed << 22 = 33,680,158,021 * 4,194,304
                              141,264,821,508,112,384
node    << 12 =            37 *     4,096  =  151,552
seq                                        =        0

OR them together (no overlap, so this is just addition)
  141,264,821,508,112,384 + 151,552 + 0
                            = 141,264,821,508,263,936

That last number is the literal printed in Api sketch, and Working python asserts it.

Unpacking runs the same arithmetic backwards, which is what decode does in Working python:

node    = (value >> 12) & 1023     shift the node field down, mask off the rest
seq     =  value        & 4095
elapsed =  value >> 22

& with 1023 keeps only the low 10 bits, because 1023 = 2^10 - 1 is ten 1-bits in a row. 4095 = 2^12 - 1 does the same for the 12-bit sequence.

Two things to take from that worked example.

First, the node and sequence values live entirely in the low 22 bits, so two IDs from the same millisecond differ by at most 2^22 - 1 = 4,194,303, while ticking to the next millisecond adds a full 2^22 = 4,194,304. That is exactly why the sort is by time first: no amount of node or sequence variation can reach into the next millisecond’s range.

Second, and this is the point Api sketch made: nothing about “37” is visible in the decimal digits of the result.

Now spend each field in turn.

5a. 41 bits of milliseconds

The timestamp field fixes the lifetime of the format, and the starting instant it counts from is a decision you can never take back.

The four lines below are one division chain. Start with how many distinct values 41 bits holds — that is 2^41 milliseconds. Divide by 1,000 to get seconds, by 86,400 to get days, by 365.25 to get years. Each line is the previous line with one more divisor, so the last number is the one that matters.

2^41                                    =  2,199,023,255,552
2^41 / 1000                             =  2,199,023,255.552
2^41 / 1000 / 86400                     =  25,451.66
2^41 / 1000 / 86400 / 365.25            =  69.68

41 bits of milliseconds is 69.68 years, and that number is the reason the epoch is a design decision rather than a default.

An epoch is the fixed instant the timestamp counts from. The field stores “milliseconds since the epoch,” so the epoch fixes both ends of the window: the moment the format starts working and the moment, 69.68 years later, when the field overflows.

The Unix epoch is the conventional one: midnight UTC on 1 January 1970. A Snowflake built on it opened its window in 1970, so 69.68 years later it closes in 2039 — meaning that if you ship today you ship a format with roughly 13 years left on it, and you have burned 56 years of range on time that had already happened before the service existed.

Set the epoch to the service’s own launch date instead and the full 69.68 years is ahead of you:

epoch 1970-01-01  ->  exhausts 2039-09
epoch 2024-01-01  ->  exhausts 2093-09

(Both of those are 1970 or 2024 plus 69.68 years, which is where the September lands.)

The epoch is a one-way door. Changing it later shifts every future timestamp by the size of the change. Move it earlier and new IDs collide with ranges already issued; move it later and new IDs sort before old ones. No migration fixes that short of rewriting every row in every table that stores one of these IDs. Pin the epoch as a compile-time constant, write it in the schema comment, and never touch it.

If 69.68 years is not enough, one more timestamp bit doubles the window, because each bit doubles the number of milliseconds the field can count:

2^42 / 1000 / 86400 / 365.25            =  139.4

But that bit has to come out of another field, because the total is fixed at 64. Taking it from the node field gives the 42/8/13 layout: 139 years, 256 nodes, and 8,192 IDs per millisecond per node. Say the reallocation out loud; it demonstrates that you understand the budget is zero-sum rather than that you memorized 41/10/12.

The table below is four ways to spend the same 63 non-sign bits. Read across a row and check that the three numbers move against each other — buying years costs you nodes or burst room, never nothing.

Every cell in that table is one exponent, and you can reproduce all of them: 2^39 / 1000 / 86400 / 365.25 = 17.42 years, 2^12 = 4,096, 2^13 = 8,192, 2^14 = 16,384 IDs per millisecond, and 2^8 = 256, 2^10 = 1,024, 2^12 = 4,096 nodes.

5b. 10 bits of node id

2^10                                    =  1,024

Ten bits give 1,024 distinct generators — the whole fleet gets 1,024 slots, and every generator must hold a different one, forever.

That single number decides whether the generator can be embedded as a library or has to be a separate service (Library or service). It is also the field people consistently under-budget, and the reason is a definitional trap: on a container platform like Kubernetes, a “generator” is a process, not a machine. One machine runs many processes, so a 200-machine fleet can easily need 800 slots. Deep dive 3 where the node id comes from does that arithmetic.

5c. 12 bits of sequence

The sequence field looks like a throughput field. It is not, and the burst requirement — not the mean rate — is what it actually sizes.

The three lines below are one multiplication chain. Start with how many values 12 bits holds, which is the number of IDs one node can issue inside one millisecond. Multiply by 1,000 milliseconds to get one node’s per-second ceiling. Multiply by 1,024 nodes to get the whole fleet’s.

2^12                                    =  4,096
2^12 * 1000                             =  4,096,000
4,096,000 * 1,024                       =  4,194,304,000

4,096 IDs per millisecond per node is 4.096 million per second per node, and 4.19 billion per second across a full 1,024-node fleet.

Compare that to the 100,000/s peak from Requirements: 4,194,304,000 / 100,000 = 41,943, so the fleet is roughly 42,000 times over-provisioned on throughput. When a number comes out that far off, it usually means you are measuring the wrong thing — and here you are. Sequence bits do not buy throughput. They buy tolerance for a burst inside a single millisecond.

That distinction is the whole point of the field. Averaged over a second, the system needs 100,000 IDs, and a single node covers that 40 times over. But a fan-out write asks for 100,000 IDs inside one millisecond, and one node only has 4,096 of them in that millisecond:

100,000 / 4,096                         =  24.4

So that burst needs 25 nodes participating. With fewer, the extra requests stall while the sequence counter waits for the clock to reach the next millisecond — 24 milliseconds of waiting if only one node handles the whole fan-out. Size the node count from the burst, not from the mean.

6. High-level architecture

Where the generator physically lives, and what it depends on, is a much shorter list than for most designs in this book.

In the diagram below, the solid arrows are things that happen and the dotted arrow is a background process. Notice what is not there: no arrow from the write path out to a network service to fetch an ID. The two boxes off to the side are touched at startup, not per identifier.

flowchart LR
    subgraph POD["Application pod"]
        APP["Write path"] --> LIB["Snowflake library<br/>in-process<br/>no network call"]
    end
    LIB --> DB[("Primary store<br/>ID is the PK")]
    ZK[("Coordination store<br/>ZooKeeper / etcd")] -->|"lease node_id<br/>once, at startup"| LIB
    LIB -->|"persist last_ms<br/>per node_id"| ZK
    NTP["NTP / chrony<br/>slew-only, leap-smeared"] -.->|"disciplines<br/>CLOCK_REALTIME"| LIB

    style LIB fill:#2d6a4f,color:#fff
    style ZK fill:#1d3557,color:#fff
    style NTP fill:#bc6c25,color:#fff

Walk the boxes one at a time.

The application pod. A pod is one running copy of the application — the unit a container platform such as Kubernetes schedules onto a machine. Inside it, the write path calls the Snowflake library directly. The library runs in-process and makes no network call, so it returns in well under a microsecond.

The primary store. The identifier the library returns goes straight in as the row’s primary key. Nothing else happens to it.

The coordination store (blue). ZooKeeper and etcd are small, strongly consistent key-value services used for exactly this kind of cluster bookkeeping. The library talks to one twice, and only twice. It leases a node_id once, at startup. And it persists last_ms for that node_id, so a restarted process cannot reuse a millisecond it has already spent — the cross-restart version of the rewind bug, covered in Deep dive 3 where the node id comes from.

The NTP client (orange). NTP is the Network Time Protocol, and its client daemon keeps the machine’s clock close to true time. It disciplines CLOCK_REALTIME, the operating system’s wall-clock time source — the one that can jump. The arrow is dotted because this runs continuously in the background, not on any request. It is drawn at all because it is not a default install: it must be configured slew-only and leap-smeared, two settings Deep dive 2 clock skew leap seconds and the rewind derives and defines.

Three claims are packed into that picture, and each becomes a deep dive below.

1. The generator is in-process. There is no ID service on the critical path, so ID generation cannot become unavailable independently of the caller that needs it (Library or service).
2. Coordination happens once, at startup, to lease a node id — never once per identifier. That is the difference between this design and a ticket server.
3. The clock is an input with a failure mode, which is why it is drawn as an arrow into the library rather than assumed (Deep dive 2 clock skew leap seconds and the rewind).

7. Deep dive 1: why a UUID loses, and where exactly

“UUIDs are bad for indexes” is folklore until it becomes two numbers you can reproduce — and getting there means first discarding the two objections people usually reach for.

A UUID is a universally unique identifier, a 128-bit value standardised so that independently generated ones do not collide. UUIDv4 is the all-random variant: 128 bits with 122 of them drawn at random (the other 6 are fixed version and variant markers).

Two objections to it are commonly given. Both are weak, and reaching for either one in an interview tells the interviewer you are quoting.

Weak objection 1: “it might collide.” It will not. The birthday bound is the standard estimate for how likely a random collision is — named after the fact that in a room of 23 people two probably share a birthday, far fewer than intuition suggests. Over n identifiers drawn from 122 random bits it is about n^2 / 2^123. At a trillion identifiers (n = 10^12) that works out to roughly 10^-13, one chance in ten trillion. Collision is not the argument; do not make it.

Weak objection 2: “it is too big.” 128 bits against 64 is twice the width of the column. On its own, nobody rejects a design over 8 extra bytes a row.

The real objection

The high-order bits are random, so every insert lands at a uniformly random position in the primary-key B-tree. That converts an append at the end of the index into a random write into the middle of it, and unlike the two weak objections, this cost is a number you can compute.

Three terms make the derivation readable:

• A leaf is a bottom-level page of the B-tree — the page that actually holds index entries.
• Fill factor is what fraction of a page’s usable bytes hold real entries rather than free space. A leaf at 90% fill has 10% of its usable bytes empty.
• The buffer pool is the database’s in-memory cache of pages. A page found there costs a memory reference; a page that is not costs a disk read, which is thousands of times slower.

The mechanism underneath — page splits, and what each extra index costs per write — is derived in The write cost of indexes quantified.

The two fill-factor constants below come from outside this track. Both are worth attributing precisely, because one of them is routinely confused with a differently-named quantity in the same engine:

• Ordered inserts always land on the rightmost leaf, which stays packed at roughly 90% full and stays resident in the buffer pool because every insert touches it again. The 90% is Postgres’s default B-tree leaf fill factor (fillfactor = 90 on a B-tree index), which is how full a leaf is left when nothing is splitting it. It is a different quantity from the heap-page fillfactor that sql 03’s HOT-update result drops to 85 — same word, different structure, opposite purpose: that one deliberately wastes space in a table page to buy in-page updates, this one is simply how much of an index leaf an appended key gets to use.
• Random inserts split full leaves in half, and a B-tree under uniformly random insertion converges to a steady-state occupancy of ln 2 = 0.69 — 69% full, with the other 31% permanently wasted. That is the classical result of Yao (1978), On random 2-3 trees, and it is a property of the split rule rather than of any engine’s settings, which is why no amount of Postgres tuning recovers it.

So: 90% for an ordered key, 69% for a random one. Now apply both to a one-billion-row table on 8 KB pages.

The first block works out how many index entries fit on one page, ignoring fill factor. 8192 is the page size. 24 is the Postgres page header, per-page bookkeeping. 16 is the “special space” a B-tree page reserves for its own pointers, which a plain table page does not have. What is left is usable bytes.

usable bytes per page
  8192 - 24 - 16                        =  8,152

index entry, bigint key   (8 header + 8 key + 4 line pointer)
  8 + 8 + 4                             =  20
index entry, uuid key     (8 header + 16 key + 4 line pointer)
  8 + 16 + 4                            =  28

entries per page
  8,152 / 20                            =  407
  8,152 / 28                            =  291

Each index entry carries an 8-byte header, the key itself, and a 4-byte line pointer — the small slot at the top of a page that says where inside the page the entry lives. So a bigint key costs 8 + 8 + 4 = 20 bytes and a UUID key costs 8 + 16 + 4 = 28. Divide those into the 8,152 usable bytes and you get 407 entries per page against 291.

The width penalty alone is therefore 407 / 291 = 1.399, call it 1.4x. Now add the fill factor, which is where the random key actually hurts.

Each half of the block below is the same three steps: multiply entries-per-page by the fill factor to get real entries per page, divide a billion rows by that to get the page count, then multiply by 8,192 bytes to get the index size.

bigint, appended in order, ~90% full
  407 * 0.90                            =  366
  1,000,000,000 / 366                   =  2,732,240
  2,732,240 * 8192                      =  22,382,510,080

uuidv4, inserted at random, ~69% full
  291 * 0.69                            =  200.8
  1,000,000,000 / 200.8                 =  4,980,080
  4,980,080 * 8192                      =  40,796,815,360

That is 22.4 GB against 40.8 GB — 40,796,815,360 / 22,382,510,080 = 1.82. The reason splits cleanly into two independent factors, and multiplying them back reproduces the ratio:

key width           407 / 291           =  1.399
fill factor         0.90 / 0.69         =  1.304
product             1.399 * 1.304       =  1.824

A random UUID makes the primary-key index 1.8x larger, and only 1.4x of that is the extra bytes — the rest is space you are paying for and cannot use.

From index size to an insert ceiling

Index size is the part you can see in a monitoring dashboard. The part that shows up as an incident is what a random key does to write throughput, and the argument runs in three steps.

Step 1: the index stops fitting in RAM. Take a 16 GB buffer pool. A 22.4 GB ordered index does not fit either, but the ordered key only ever touches its rightmost leaf, so the pages it needs are always resident. The 40.8 GB random index is touched everywhere, so what matters is what fraction of it is cached.

Step 2: the misses become random disk reads. 1 - 0.392 = 0.608, so about 61% of inserts must first read an 8 KB leaf page off the drive before they can write to it.

Step 3: the drive’s random-read rate becomes the insert ceiling. A solid-state drive doing 100 MB/s of random reads delivers a fixed number of 8 KB pages per second; divide by the fraction of inserts that need one.

fraction of the uuid index that fits in RAM
  16 / 40.8                             =  0.392

8 KB random reads at 100 MB/s NVMe
  100,000,000 / 8192                    =  12,207

sustainable inserts when 61% of them must first fault a leaf in
  12,207 / 0.61                         =  20,011

The random-key table tops out around 20,000 inserts per second, bounded by random read I/O, on a machine whose ordered-key ceiling is set by CPU instead — because ordered inserts touch the same hot rightmost page every time and never read from disk at all. That is the sentence to say, and it is what makes the objection reproducible rather than received wisdom.

Two secondary consequences are worth naming.

• A UUID cannot serve as a cursor. WHERE id > $last ORDER BY id LIMIT 100 is the cheapest pagination there is, and it requires that IDs order by time. With a random key you need a separate index on (created_at, id), which is another index to maintain and a second stream of random writes.
• Range-partitioning by ID becomes impossible. Range partitioning means storing rows in separate physical chunks by key range; with a time-ordered key those chunks are time buckets, which lets a query skip whole partitions and lets an archival job drop the oldest one. A random key forecloses both.

8. Deep dive 2: clock skew, leap seconds, and the rewind

Snowflake assumes something exact about clocks. The moment that assumption fails, something specific breaks — and there are three fixes with three different costs, one of which is what modern generators actually ship.

The assumption, stated precisely

Everything else in this section follows from one sentence, so read it twice.

Snowflake’s uniqueness proof is one line: the triple (timestamp_ms, node_id, sequence) is unique because node_id is unique per generator, and sequence is unique within a millisecond on that generator.

Notice what that proof does not require. It never mentions any other node’s clock.

So the assumption is narrower than people expect, and it is worth saying out loud in an interview: Snowflake’s correctness does not depend on clocks being synchronized across the fleet. It depends only on each node’s own clock being non-decreasing — never returning a value smaller than one it already returned.

Two consequences follow, and they are very different in severity.

Consequence 1: skew between nodes costs sort accuracy, not uniqueness. NTP typically holds machines within about 10 ms of each other inside a datacenter. So two IDs created on different nodes less than 10 ms apart may sort in the wrong order relative to each other. For a sort key that is bounded, harmless fuzz.

It stops being harmless only if you need an order that respects causality — the guarantee that if event A caused event B then A sorts first, regardless of what any clock says. Snowflake cannot give you that. Two tools that can:

• A hybrid logical clock: a physical timestamp paired with a logical counter that is bumped whenever a message arrives from a machine whose clock is ahead, so causally later events always get larger values.
• Spanner-style commit-wait: a transaction deliberately waits out the clock’s own stated uncertainty interval before committing, so no two commits can be ordered wrongly.

Consequence 2: a single node’s clock going backwards costs uniqueness itself. That one is neither bounded nor harmless, and it is the rest of this section.

What breaks when a clock goes backwards

Here is the failure in full, step by step, because it is the one this whole chapter exists to prevent.

Call the last millisecond the generator issued from last_ms. A rewind is the wall clock returning a value smaller than last_ms.

1. At time T, the node issues IDs at last_ms = 1000, with sequence values 0, 1, 2, 3.
2. NTP steps the clock back 300 ms. The clock now reads 700.
3. The generator sees 700 != 1000, concludes the millisecond changed, and resets the sequence to 0.
4. It issues at (700, node, 0), (700, node, 1), and so on — but it already issued exactly those triples 300 ms ago, on the way up.

The result is a duplicate primary key, generated silently, on one node. The two colliding writes can be minutes or hours apart in wall-clock terms, because the collision only shows up when both rows reach the same table. By the time a unique-constraint violation surfaces in the database, nothing tells you which of the two writes is the imposter.

Note the shape of the failure: the guard has to be per-node and local. No amount of cross-fleet clock synchronization helps, because the assumption that broke was about one machine’s own clock, not about agreement between machines.

Where the rewind comes from

Five sources, in descending order of how often each actually happens. Read the magnitude column first — it is what decides whether a fix that waits is safe or a fix that refuses is required.

Two words in that first row carry the whole distinction, and they come back in every fix below.

• To step a clock is to jump it instantly to the correct value. A step can move the clock backwards.
• To slew a clock is to speed it up or slow it down slightly until it drifts into agreement. A slew never moves the clock backwards; it only makes it advance faster or slower than real time.

A leap second is an extra second inserted into UTC to keep it aligned with the earth’s rotation. The naive way an operating system applies one is to repeat or rewind a second — a one-second step, by another name.

The leap-second row is the dangerous one, and it is dangerous for a structural reason. Every other cause is uncorrelated across nodes: one machine’s NTP steps, or one VM migrates, and the rest of the fleet is fine. A per-node “refuse to serve” then degrades gracefully behind a load balancer, which routes to a healthy node and nobody notices.

A leap second fires on all 1,024 nodes at the same instant. There is no healthy node to route to, so the identical guard turns a correctness fix into a fleet-wide outage.

The two real fixes

There are exactly two safe responses to a detected rewind, and each is right in a different size range.

Fix 1 — refuse to issue. If now < last_ms, raise an error, fail the health check, and let the caller retry against another node. This is what the original Snowflake implementation did.

cost = one node unavailable for the duration of the rewind
       300 ms NTP step  ->  300 ms of errors from that node
       1 s leap second  ->  1 s of errors from every node at once

It is unambiguously safe: no duplicate can be issued because no ID is issued. It converts a correctness problem into an availability problem, which is the right trade for a primary key.

Fix 2 — wait it out. Sleep until the wall clock catches up to last_ms, then proceed.

cost = one request's latency inflated by the rewind
       2 ms slew artifact  ->  2 ms of extra p99, invisible
       1 s leap second     ->  a 1 s hang, indistinguishable from a hang

Equally safe, and better for small rewinds because a 2 ms latency bump beats a 2 ms error burst. Worse for large ones, because an unbounded sleep is a hang that no timeout budget expects.

The answer is to ship both, separated by a threshold. Wait out anything below a few milliseconds, because that band is slew artifact and clock-source jitter, and turning it into errors is self-harm. Refuse anything above it, because a rewind larger than the wait budget is a real event a human needs to see. The generator in Working python implements exactly that, with max_wait_ms as the boundary.

The trap inside the wait branch

max_wait_ms has to bound the whole call, not one reading of the drift. This is the subtle part, so take it slowly.

The tempting implementation samples the drift once, decides it is inside the budget, and then loops:

drift = last_ms - now
if drift > max_wait_ms: refuse
while now < last_ms:              # <-- no budget inside this loop
    sleep
    now = clock()

That is correct against a clock that rewinds once and then behaves. It is not correct against a clock that is still retreating while you sleep. On every iteration, the drift measured at that moment is small, so a per-sample test would pass every time — and the loop above does not even re-test. Either way the call blocks indefinitely, and the total rewind absorbed is unbounded.

Concretely: with max_wait_ms = 5.0 and a clock walking back 4 ms on every read, the call is still blocked after six seconds, having absorbed 212 ms of rewind against a 5 ms budget. That is the unbounded hang the refuse branch existed to prevent, reached through the wait branch instead.

The fix is a single monotonic deadline: compute one deadline before the loop starts and re-check it inside the loop. The monotonic clock is a separate operating-system time source that only ever moves forward and is never adjusted by NTP — which makes it immune to the exact fault being handled here. Use the wall clock to decide what to wait for, and the monotonic clock to decide how long. Working python tests this with a clock that retreats on every read.

The same trap in the exhaustion loop

The rule applies to every loop that waits on the wall clock, not just the rewind one.

The generator has a second such loop. When the 4,096 sequence values for the current millisecond are spent, it waits for the clock to reach the next millisecond. Its exit condition is now > last_ms.

A frozen clock never satisfies that condition either. And a frozen clock is not exotic — it is two rows of the failure table above: the suspended VM and the failing TSC. Left unbounded, the loop lets exactly 4,096 identifiers out and then blocks call 4,097 for ever, while holding the mutex, so every other thread in the process stops with it.

A clock that does not advance is the same fault as one that retreats. Both leave the generator inside a (timestamp, node) pair it has already spent. So the exhaustion loop takes the same monotonic deadline and raises the same ClockMovedBackwards, and Working python asserts that the 4,097th call on a stopped clock raises rather than blocks.

One more thing to say out loud, because it is the cleanest argument for the fix below: MonotonicSnowflake is immune to all of this by construction. It never uses the wall clock as a loop exit condition, so it has no loop to be stuck in. On the same frozen clock it issues 50,000 unique, sorted identifiers in tens of milliseconds, by borrowing from the sequence space. A deadline is the right guard for a generator that reads the wall clock for control flow; not reading it for control flow at all is better.

The third fix, which is what modern generators actually do

There is a fix that neither errors nor blocks, and two lines of it are the easiest to leave out.

The idea is to stop reading the wall clock directly and instead run the generator on a logical clock: an internal last_ms that tracks the wall clock upward, never follows it downward, and borrows from the sequence space when it has to run ahead.

Read the pseudocode below one line at a time. max(last_ms, wall_clock_now) is the whole trick — if the wall clock has gone backwards, last_ms wins and the timestamp simply does not move. All four lines are load-bearing, and the two marked with arrows are the ones people leave out:

ts = max(last_ms, wall_clock_now)
if ts == last_ms:
    seq += 1
    if seq overflowed: ts += 1; seq = 0
else:
    seq = 0                     # <-- without this, seq never resets per ms
last_ms = ts                    # <-- without this, the logical clock is dead

Here is what each omission does.

Drop else: seq = 0. The sequence field stops being a per-millisecond counter and becomes a global one. The generator now exhausts 4,096 IDs in total rather than 4,096 per millisecond, and every overflow after that shoves ts another millisecond into the future — so the embedded timestamps drift steadily away from real time.

Drop last_ms = ts. Then there is no logical clock at all. ts == last_ms is never true, so seq is pinned at 0, and on a frozen wall clock the generator hands out one identical ID forever.

Working python implements this as MonotonicSnowflake and has an executable test for each of those two failure shapes, because pseudocode that is never run is pseudocode that is never checked.

What this fix buys and what it costs.

It never blocks and never duplicates, which is why modern generators use it.

The cost is worth stating plainly: during and after a rewind, the timestamp embedded in the ID runs ahead of real time by up to the size of the rewind. Decoding an ID therefore gives you an upper bound on its creation time, not its creation time.

For an identifier used as a sort key, that is entirely fine — the ordering is still correct, just shifted. For an identifier used as an audit timestamp it is not, and an ID was never a safe place to keep an audit timestamp in the first place.

Configure the clock, not just the code

The code-level guards above are the last line of defence. Three configuration settings prevent most rewinds from ever reaching them.

• Slew, never step. Run chronyd with maxslewrate bounded, or ntpd -x, so the daemon corrects offsets by adjusting the clock’s rate rather than jumping it. A slewed clock is always monotone; a stepped clock is not.
• Leap smear. Google’s and AWS’s public NTP endpoints spread the leap second across 24 hours instead of applying it at once. Spreading one second over 86,400 seconds is 1 / 86400 = 0.0000116 of rate adjustment — about 1.16 parts in 100,000, far too small for anything to notice. Because the correction is a slew, the clock never moves backwards and never repeats a value. A fully smeared fleet cannot have a leap-second rewind at all, which converts the single worst correlated failure in the table above into a non-event.
• Never mix smeared and unsmeared NTP sources in one fleet. Halfway through a smear the two families of servers are up to 0.5 s apart. That is harmless for uniqueness, which is a per-node property, and it is terrible for anything that compares timestamps across nodes.

9. Deep dive 3: where the node id comes from

The second assumption — that every generator has a different node id — has to be enforced somewhere, and violating it, not the clock, is what actually takes systems down.

There are 1,024 slots. Every duplicate assignment creates two generators that will silently produce the same identifiers, because the uniqueness proof in Deep dive 2 clock skew leap seconds and the rewind rests on node_id being distinct. This is the most common real-world Snowflake outage, and it is almost never the clock.

Five ways to hand out node ids, worst first. The last column is the one to read: every scheme except the last has a specific, ordinary event that breaks it.

Four terms in that table are worth defining.

• An autoscaler is the component that starts and stops copies of an application in response to load. It is what makes “someone will clone the config” a certainty rather than a risk: the autoscaler clones it, thousands of times, with no human involved.
• A /22 is a block of IP addresses sharing their first 22 bits. The remaining bits vary, so it holds 2^(32 - 22) = 2^10 = 1,024 addresses — exactly the size of the node-id field. That is why taking the last 10 bits of the IP works perfectly inside one /22 and collides the moment you have two of them.
• A StatefulSet is the Kubernetes object that gives each copy of an application a stable numbered name like pod-7. A Deployment, the more common object, gives its copies random names instead, so there is no ordinal to use.
• A lease is a claim on a resource that expires unless renewed. In ZooKeeper it is an ephemeral znode: a small node in a tree-shaped key-value store, deleted automatically the moment the client’s session ends.

The ephemeral-lease trap deserves its own walkthrough, because it is the one that survives code review:

1. Node 37 crashes.
2. Its ZooKeeper session ends, so the ephemeral znode is deleted and slot 37 is free. That is what “ephemeral” means, and it is normally the feature.
3. A new pod starts and takes slot 37. Its clock happens to read 200 ms behind the dead node’s last-issued timestamp.
4. It issues identifiers in a millisecond range that slot 37 has already used. Silent duplicates.

The fix is to persist last_issued_ms alongside each node id, and refuse to serve on startup until now > last_issued_ms. That is the same guard as Deep dive 2 clock skew leap seconds and the rewind, applied across process restarts rather than within one process.

Does 1,024 fit your fleet?

This is where the layout choice from Data model the 64 bit layout derived comes due, and the arithmetic is unforgiving.

With an in-process library, a “node” is a process, not a machine. Then add deployments. A blue-green deploy is a release strategy that brings the whole new version up alongside the old one and switches traffic over once it is healthy. For the length of that window, both generations are running and both hold node-id leases — so your peak slot usage is twice your steady-state pod count:

400 pods, blue-green deploy holds two generations briefly
  400 * 2                               =  800
safe ceiling before the 1,024 slots are exhausted
  1,024 / 2                             =  512

With 10 bits and a blue-green rollout you can run 512 pods, not 1,024. A single bad rollout that leaves zombie pods still holding leases eats into what is left, and enough of them exhaust the space entirely.

If your fleet already runs 400 pods with growth ahead of it, take the 41/12/10 layout instead: 4,096 nodes at 1,024 IDs per millisecond per node. That is still 1,024 * 1,000 = 1,024,000 IDs per second per node, about 10 times the fleet’s whole peak.

Against that ceiling, the burst headroom the library form buys is enormous. Every pod has its own 4,096-per-millisecond sequence space, so they add up:

400 pods * 4,096 per ms                 =  1,638,400

1.6 million IDs inside a single millisecond, against a 100,000 burst requirement — 16x over. Embedding the generator turns the node-id field into your burst capacity, which is why the layout question and the library-versus-service question are the same question.

10. Library or service

Between the two deployment shapes from Api sketch, one is the default, and exactly two conditions flip it.

Seven rows below. The first two favour the library so heavily that the argument is essentially over; the last two are the only ones that favour the service.

Two rows need unpacking.

The batching row. At one round trip of 0.5 ms per call, a single caller making one call at a time and waiting for the answer cannot exceed 1 / 0.0005 = 2,000 identifiers a second — it spends every millisecond of the second waiting on two round trips. Any higher rate from one caller forces you to request identifiers in batches, which means holding unused IDs and issuing them out of time order.

The polyglot row. A polyglot fleet is one written in several programming languages. It matters here because the library form means reimplementing the rewind guard, the deadline, and the sequence-exhaustion loop once per language — and the bugs will differ per language.

Default to the library, and name the two conditions that flip the decision: a polyglot fleet, where you would be maintaining five subtly different implementations of the rewind guard, or a fleet large enough that one node id per process does not fit the field. If you do take the service form, batch — and then read Alternatives rejected, because batching is precisely what kills the ticket server.

11. Working Python

Here is the whole design as running code, so that every claim above is executable rather than asserted.

Two generators. Snowflake implements the wait-or-refuse threshold from Deep dive 2 clock skew leap seconds and the rewind. MonotonicSnowflake implements The third fix which is what modern generators actually do rather than describing it.

What the assertions cover. The bit layout. Monotonicity within and across milliseconds. The literal identifier printed in Api sketch. And both halves of the rewind threshold — the refuse half and the wait half. Those two have to be tested separately, because a generator constructed with max_wait_ms = 0.0 puts every possible rewind above the budget, so such a test exercises the refuse path twice and the wait path never. A third timing assertion covers the sequence-exhaustion half of the same rule: the 4,097th call against a stopped clock must raise rather than block.

One term before you read it. The generator holds a mutex — a lock that lets only one thread at a time run the code inside it. It needs one because _last_ms and _seq are a single piece of state that must be read and updated together; two threads interleaving there would both see the same sequence value and issue the same ID.

next_id runs four blocks in order: the rewind guard (if now < self._last_ms), the same-millisecond branch that bumps the sequence, the different-millisecond branch that resets it to 0, and the packing expression at the end that shifts the three fields into place.

"""Snowflake-style 64-bit ID generator: 1 | 41 | 10 | 12."""
import threading
import time

CUSTOM_EPOCH_MS = 1704067200000          # 2024-01-01T00:00:00Z

TIMESTAMP_BITS = 41
NODE_BITS = 10
SEQUENCE_BITS = 12
assert 1 + TIMESTAMP_BITS + NODE_BITS + SEQUENCE_BITS == 64

MAX_NODE = (1 << NODE_BITS) - 1          # 1023
MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1  # 4095
NODE_SHIFT = SEQUENCE_BITS               # 12
TIMESTAMP_SHIFT = SEQUENCE_BITS + NODE_BITS   # 22


class ClockMovedBackwards(RuntimeError):
    """The wall clock is behind a millisecond we have already issued from.

    Continuing would reissue sequence values inside a (ts, node) pair that
    is already spent -- a silent duplicate primary key.
    """


class Snowflake:
    def __init__(self, node_id, epoch_ms=CUSTOM_EPOCH_MS,
                 max_wait_ms=5.0, clock=None, sleep=None):
        if not 0 <= node_id <= MAX_NODE:
            raise ValueError(f"node_id must be in [0, {MAX_NODE}]")
        self.node_id = node_id
        self.epoch_ms = epoch_ms
        self.max_wait_ms = max_wait_ms          # wait below this, refuse above
        self._clock = clock or (lambda: int(time.time() * 1000))
        self._sleep = sleep or time.sleep
        self._lock = threading.Lock()
        self._last_ms = -1
        self._seq = 0

    def next_id(self):
        with self._lock:
            now = self._clock()

            # ---- the clock-rewind guard --------------------------------
            if now < self._last_ms:
                drift = self._last_ms - now
                if drift > self.max_wait_ms:
                    # A rewind bigger than the wait budget is a real event:
                    # an NTP step, a leap second, a migrated VM. Refuse and
                    # fail the health check so traffic moves to another node.
                    raise ClockMovedBackwards(
                        f"clock went back {drift} ms on node {self.node_id}")
                # Below the budget this is slew jitter. Wait it out: a few
                # milliseconds of latency beats a few milliseconds of 5xx.
                #
                # `max_wait_ms` has to bound the CALL, not one sample of the
                # drift. A clock that keeps retreating while we sleep passes
                # the drift test on every iteration and blocks forever, which
                # is exactly the unbounded hang section 8 refuses. One
                # monotonic deadline, checked every time round the loop.
                deadline = time.monotonic() + self.max_wait_ms / 1000.0
                while now < self._last_ms:
                    remaining = deadline - time.monotonic()
                    if remaining <= 0:
                        raise ClockMovedBackwards(
                            f"clock still {self._last_ms - now} ms behind "
                            f"after waiting {self.max_wait_ms} ms on node "
                            f"{self.node_id}")
                    self._sleep(min((self._last_ms - now) / 1000.0, remaining))
                    now = self._clock()

            if now == self._last_ms:
                self._seq = (self._seq + 1) & MAX_SEQUENCE
                if self._seq == 0:                  # 4,096 spent in this ms
                    now = self._wait_next_ms()
            else:
                self._seq = 0

            self._last_ms = now
            elapsed = now - self.epoch_ms
            if not 0 <= elapsed < (1 << TIMESTAMP_BITS):
                raise OverflowError("timestamp outside the 41-bit window")
            return ((elapsed << TIMESTAMP_SHIFT)
                    | (self.node_id << NODE_SHIFT)
                    | self._seq)

    def _wait_next_ms(self):
        """Sleep to the next millisecond. Do NOT busy-spin.

        The mutex is held here and must be: `_last_ms` and `_seq` are one
        piece of state and releasing it mid-update lets a second thread
        reissue this millisecond. But a spin loop under a held lock is the
        worst of both -- every other thread in the process is blocked on the
        lock AND descheduled by the spinner burning its core, for up to a
        full millisecond. Yielding costs one context switch and gives the
        core back. If a thread genuinely cannot afford to wait, the fix is a
        generator per thread with its own node id (section 13), not a spin.

        And this loop needs the same monotonic deadline the rewind guard
        above needs, for the same reason. A clock that does not ADVANCE is
        the same fault as one that RETREATS: both leave the generator inside
        a (timestamp, node) pair it has already spent, and both make the
        exit condition something the wall clock may never satisfy. A frozen
        clock -- a suspended VM, a failing TSC, both rows of section 14's
        table -- lets exactly 4,096 IDs out and then blocks call 4,097 for
        ever, HOLDING THE MUTEX, which stops every thread in the process. A
        healthy clock leaves this loop inside one millisecond, so bound the
        wait at that and refuse past it.
        """
        now = self._clock()
        deadline = time.monotonic() + max(self.max_wait_ms, 1.0) / 1000.0
        while now <= self._last_ms:
            if time.monotonic() >= deadline:
                raise ClockMovedBackwards(
                    f"clock stuck at {now} ms on node {self.node_id}: the "
                    f"sequence for this millisecond is spent and the clock "
                    f"has not advanced")
            self._sleep(0.0002)          # 200 us, well inside the 1 ms wait
            now = self._clock()
        return now

    @staticmethod
    def decode(value, epoch_ms=CUSTOM_EPOCH_MS):
        return {
            "epoch_ms": (value >> TIMESTAMP_SHIFT) + epoch_ms,
            "node_id": (value >> NODE_SHIFT) & MAX_NODE,
            "sequence": value & MAX_SEQUENCE,
        }


class MonotonicSnowflake(Snowflake):
    """Section 8's third fix, implemented rather than described.

    A logical clock that tracks the wall clock upward and never follows it
    down. It never blocks and never duplicates; the price is that the
    embedded timestamp is an upper bound on creation time, not the time.
    """

    def next_id(self):
        with self._lock:
            ts = max(self._last_ms, self._clock())
            if ts == self._last_ms:
                self._seq = (self._seq + 1) & MAX_SEQUENCE
                if self._seq == 0:              # borrow from the next ms
                    ts += 1
            else:
                self._seq = 0                   # the line the pseudocode lost
            self._last_ms = ts                  # ...and so is this one
            elapsed = ts - self.epoch_ms
            if not 0 <= elapsed < (1 << TIMESTAMP_BITS):
                raise OverflowError("timestamp outside the 41-bit window")
            return ((elapsed << TIMESTAMP_SHIFT)
                    | (self.node_id << NODE_SHIFT)
                    | self._seq)

Two implementation details in that code are worth pausing on before the tests.

_wait_next_ms sleeps rather than spins, and its docstring says why: the mutex is held throughout, so a busy-spin blocks every other thread in the process and burns the core they would otherwise run on, for up to a full millisecond.

Both waiting loops take their deadline from time.monotonic(), never from the wall clock they are waiting on. That is the Deep dive 2 clock skew leap seconds and the rewind rule in code: the thing that decides how long you wait must be immune to the fault you are waiting out.

Now the assertions that hold the design to its claims.

The key to all of them is scripted_clock: a clock that returns a prepared list of times instead of reading the machine’s. Passing one into the constructor lets a test make the clock jump backwards, stop, or retreat on every read. That reproducibility is the only way to test any of this at all — you cannot wait around for an NTP step.

def scripted_clock(values):
    """A clock that returns `values` in order, then ticks forward by 1 ms."""
    it = iter(values)
    state = [0]

    def clock():
        try:
            state[0] = next(it)
        except StopIteration:
            state[0] += 1
        return state[0]

    return clock


# --- bit layout -------------------------------------------------------
assert MAX_NODE == 1023 and MAX_SEQUENCE == 4095
assert (1 << TIMESTAMP_BITS) - 1 == 2_199_023_255_551
assert TIMESTAMP_SHIFT == 22 and NODE_SHIFT == 12

g = Snowflake(node_id=1023, clock=lambda: CUSTOM_EPOCH_MS + 1)
one = g.next_id()
assert one < (1 << 63), "must stay positive in a signed BIGINT"
assert Snowflake.decode(one)["node_id"] == 1023
assert Snowflake.decode(one)["epoch_ms"] == CUSTOM_EPOCH_MS + 1

# --- monotonicity inside one millisecond ------------------------------
g = Snowflake(node_id=7, clock=scripted_clock([CUSTOM_EPOCH_MS] * 5))
ids = [g.next_id() for _ in range(5)]
assert ids == sorted(ids) and len(set(ids)) == 5
assert [Snowflake.decode(i)["sequence"] for i in ids] == [0, 1, 2, 3, 4]

# --- monotonicity across milliseconds ---------------------------------
g = Snowflake(node_id=7, clock=scripted_clock(
    [CUSTOM_EPOCH_MS, CUSTOM_EPOCH_MS, CUSTOM_EPOCH_MS + 1]))
ids = [g.next_id() for _ in range(3)]
assert ids == sorted(ids) and len(set(ids)) == 3

# --- the literal printed in section 4 ---------------------------------
# 141264821508263936, and nothing else, decodes to node 37 at sequence 0.
g = Snowflake(node_id=37, clock=lambda: 1_737_747_358_021)
first = g.next_id()
assert first == 141264821508263936
assert Snowflake.decode(first) == {"epoch_ms": 1_737_747_358_021,
                                   "node_id": 37, "sequence": 0}
# The plausible-looking constant that ends in "37" is a different ID.
assert Snowflake.decode(141264821510144037) == {"epoch_ms": 1_737_747_358_021,
                                                "node_id": 496, "sequence": 37}

# --- a large rewind is REFUSED ----------------------------------------
g = Snowflake(node_id=7, max_wait_ms=5.0, clock=scripted_clock(
    [CUSTOM_EPOCH_MS + 1000, CUSTOM_EPOCH_MS + 400]))
g.next_id()
try:
    g.next_id()
    raise AssertionError("a 600 ms rewind must not be silently absorbed")
except ClockMovedBackwards:
    pass

# --- a small rewind is WAITED OUT, and then succeeds -------------------
# max_wait_ms must be > 0 here. At max_wait_ms = 0.0 every rewind is
# larger than the budget, so such a test exercises the refuse path twice
# and the wait path never.
g = Snowflake(node_id=7, max_wait_ms=5.0, clock=scripted_clock(
    [CUSTOM_EPOCH_MS + 1000, CUSTOM_EPOCH_MS + 998, CUSTOM_EPOCH_MS + 1000]))
one, two = g.next_id(), g.next_id()
assert two > one                              # no error, and still monotone
assert Snowflake.decode(two)["epoch_ms"] == CUSTOM_EPOCH_MS + 1000
assert Snowflake.decode(two)["sequence"] == 1

# --- max_wait_ms bounds the CALL, not one sample of the drift ----------
# A clock retreating 4 ms per read passes the `drift > max_wait_ms` test
# every single time, so without a deadline this loop never returns: it
# stays blocked past 6 seconds, having absorbed 212 ms of rewind against
# a 5 ms budget.
state = {"ms": CUSTOM_EPOCH_MS + 1_000_000, "reads": 0}


def retreating_clock():
    state["reads"] += 1
    if state["reads"] > 1:
        state["ms"] -= 4
    return state["ms"]


g = Snowflake(node_id=7, max_wait_ms=5.0, clock=retreating_clock)
g.next_id()
started = time.monotonic()
try:
    g.next_id()
    raise AssertionError("a clock that keeps retreating must not block forever")
except ClockMovedBackwards:
    pass
waited_ms = (time.monotonic() - started) * 1000
assert waited_ms < 50, waited_ms          # 5 ms budget, generous slack

# --- sequence exhaustion yields the CPU, it does not spin --------------
naps = []
ticks = iter([CUSTOM_EPOCH_MS + 9] * 3 + [CUSTOM_EPOCH_MS + 10] * 4)
g = Snowflake(node_id=7, clock=lambda: next(ticks), sleep=naps.append)
g._last_ms, g._seq = CUSTOM_EPOCH_MS + 9, MAX_SEQUENCE - 1
assert Snowflake.decode(g.next_id())["sequence"] == MAX_SEQUENCE  # last one
rolled = g.next_id()                                   # must roll to the ms
assert Snowflake.decode(rolled)["epoch_ms"] == CUSTOM_EPOCH_MS + 10
assert Snowflake.decode(rolled)["sequence"] == 0
assert naps, "the exhaustion path must sleep, not busy-spin under the lock"
assert all(0 < s <= 0.001 for s in naps), naps

# --- a clock that does not ADVANCE must refuse, not block --------------
# The rewind guard bounds its wait; the exhaustion path has to as well,
# because a frozen clock never satisfies `now > _last_ms` either. Exactly
# 4,096 IDs fit in one millisecond, so a stopped clock -- a suspended VM,
# a failing TSC -- issues 4,096 and then reaches `_wait_next_ms`. Without
# the deadline there, call 4,097 never returns AND it is holding the
# mutex, so every other thread in the process stops with it.
g = Snowflake(node_id=1, clock=lambda: CUSTOM_EPOCH_MS + 5)
frozen_ids = [g.next_id() for _ in range(MAX_SEQUENCE + 1)]   # 4,096
assert len(set(frozen_ids)) == 4096 and frozen_ids == sorted(frozen_ids)
started = time.monotonic()
try:
    g.next_id()                                   # the 4,097th
    raise AssertionError("a frozen clock must raise, not block for ever")
except ClockMovedBackwards:
    pass
assert (time.monotonic() - started) * 1000 < 100  # 1 ms budget, wide slack

# MonotonicSnowflake is immune to the same input by construction: it never
# reads the wall clock for an exit condition, so there is no loop to be
# stuck in. Same frozen clock, 50,000 IDs, no error and no duplicate.
m = MonotonicSnowflake(node_id=1, clock=lambda: CUSTOM_EPOCH_MS + 5)
immune = [m.next_id() for _ in range(50_000)]
assert len(set(immune)) == 50_000 and immune == sorted(immune)

# --- section 8's third fix: implemented, and both ways it breaks -------
def third_fix(n, clock, reset_seq, assign_last):
    """Section 8's pseudocode, with each of the two easy-to-omit lines
    switchable, so 'broken as written' is a number rather than a claim."""
    last_ms, seq, out = -1, 0, []
    for _ in range(n):
        ts = max(last_ms, clock())
        if ts == last_ms:
            seq = (seq + 1) & MAX_SEQUENCE
            if seq == 0:
                ts += 1
        elif reset_seq:
            seq = 0
        if assign_last:
            last_ms = ts
        out.append((ts, 9, seq))
    return out


# (a) `last_ms` never assigned: ts == last_ms is never true, so seq is
#     pinned at 0 and a frozen clock reissues one identical ID forever.
frozen = lambda: CUSTOM_EPOCH_MS + 77
assert len(set(third_fix(5, frozen, reset_seq=True, assign_last=False))) == 1

# (b) no `else: seq = 0`: the sequence stops being per-millisecond and
#     becomes a global counter, spent after 4,096 IDs in total.
two_per_ms = iter([CUSTOM_EPOCH_MS + i // 2 for i in range(9_000)])
no_reset = third_fix(9_000, lambda: next(two_per_ms),
                     reset_seq=False, assign_last=True)
assert max(s for _, _, s in no_reset) == MAX_SEQUENCE   # on 2 IDs/ms

# (c) both lines present -- which is what MonotonicSnowflake implements.
two_per_ms = iter([CUSTOM_EPOCH_MS + i // 2 for i in range(9_000)])
m = MonotonicSnowflake(node_id=9, clock=lambda: next(two_per_ms))
seqs = [Snowflake.decode(m.next_id())["sequence"] for _ in range(9_000)]
assert max(seqs) == 1                                   # resets every ms

# It never blocks and never duplicates, even on a frozen clock: it borrows
# from the sequence space and runs ahead of real time.
m = MonotonicSnowflake(node_id=9, clock=frozen)
ids = [m.next_id() for _ in range(10_000)]              # 2.4x the seq space
assert len(set(ids)) == 10_000 and ids == sorted(ids)
assert Snowflake.decode(ids[0])["epoch_ms"] == CUSTOM_EPOCH_MS + 77
assert Snowflake.decode(ids[-1])["epoch_ms"] == CUSTOM_EPOCH_MS + 79
assert max(Snowflake.decode(i)["sequence"] for i in ids) == MAX_SEQUENCE

# ...and it absorbs a rewind with no error and no duplicate.
back = iter([CUSTOM_EPOCH_MS + 1000, CUSTOM_EPOCH_MS + 400,
             CUSTOM_EPOCH_MS + 401])
m = MonotonicSnowflake(node_id=9, clock=lambda: next(back))
a, b, c = m.next_id(), m.next_id(), m.next_id()
assert a < b < c
assert Snowflake.decode(b)["epoch_ms"] == CUSTOM_EPOCH_MS + 1000  # ahead
assert Snowflake.decode(b)["sequence"] == 1

# --- two nodes never collide even at the same millisecond -------------
a = Snowflake(node_id=1, clock=lambda: CUSTOM_EPOCH_MS + 99)
b = Snowflake(node_id=2, clock=lambda: CUSTOM_EPOCH_MS + 99)
assert a.next_id() != b.next_id()

The last assert is the uniqueness proof in three lines: identical timestamps, identical sequence, different node field.

12. UUIDv7 and ULID: the modern answer, priced

The modern alternative deserves honest pricing: four costs, one very large benefit, and a rule for choosing between it and Snowflake.

RFC 9562, the 2024 standard from the Internet Engineering Task Force that supersedes the older UUID specification, defines UUIDv7: a UUID whose leading bits are a timestamp rather than random. It is what you should reach for whenever the 64-bit constraint is not real.

Its layout is below. Compare it against the Snowflake layout in Data model the 64 bit layout derived as you read: the timestamp is still first, for exactly the same reason, but there is no node field and the rest is random rather than a counter.

UUIDv7, 128 bits
  48 bits  Unix milliseconds, big-endian, at the front
   4 bits  version = 7
  12 bits  rand_a, or a sub-millisecond counter for monotonicity
   2 bits  variant
  62 bits  rand_b

The version and variant fields are fixed bit patterns that let any reader identify which UUID scheme a value belongs to. rand_a and rand_b are the two random regions; rand_a can optionally be repurposed as a sub-millisecond counter, which is how the monotonic variants work.

ULID, the Universally Unique Lexicographically Sortable Identifier, is the same idea in a different skin: 48 bits of milliseconds plus 80 bits of randomness. What is different is how it is written down. It is rendered in Crockford base32, an alphabet of 32 characters chosen to avoid the ones humans confuse — I, L, O and U are excluded. Each character carries 5 bits, and 26 * 5 = 130 bits of encoding space holds the 128. So a ULID is 26 characters that sort correctly as plain text, which is its actual selling point: you can ORDER BY the string form directly.

Unlike Snowflake’s 41 bits, the timestamp field here is not a constraint at all. Same division chain as 5a 41 bits of milliseconds — milliseconds, then seconds, then days, then years:

2^48                                    =  281,474,976,710,656
2^48 / 1000 / 86400 / 365.25            =  8,920

8,920 years. There is no epoch decision, no exhaustion planning, and no format migration in anyone’s career.

What it costs relative to Snowflake

There are four costs and they are worth taking one at a time.

Cost 1: the key doubles. 128 bits instead of 64.

But this is the cheap half of UUIDv4’s penalty, not the expensive half. Because the high bits are time-ordered, inserts append rather than scatter, so leaves fill to 90% again. You get the 1.304 fill-factor factor from Deep dive 1 why a uuid loses and where exactly back and pay only the 1.399 width factor. The block below is the same three steps as Deep dive 1 why a uuid loses and where exactly: 291 entries per page for a 16-byte key, times 90% fill, into a billion rows, times 8,192 bytes.

uuidv7, 16-byte key, inserted in order, ~90% full
  291 * 0.90                            =  262
  1,000,000,000 / 262                   =  3,816,794
  3,816,794 * 8192                      =  31,267,176,448

31.3 GB against 22.4 GB for a bigint and 40.8 GB for UUIDv4. UUIDv7 recovers the fill factor and pays only the key width: 31.3 / 22.4 = 1.40.

Cost 2: uniqueness becomes probabilistic rather than proven.

Snowflake’s uniqueness is a proof: distinct node ids and a per-millisecond counter make collisions impossible. UUIDv7’s is a probability, and it rests on entropy — randomness measured in bits, so 74 bits of entropy means one of 2^74 equally likely values. The 74 comes from the 12 bits of rand_a plus the 62 of rand_b, and it is refreshed every millisecond because the timestamp prefix changes.

Price it. Take a sustained 10 million IDs per second, which is 10,000 per millisecond and about 100 times the peak this system is sized for. The reasoning is the birthday bound again: two IDs collide only if they share a millisecond and draw the same 74 random bits, so count the pairs within a millisecond and divide the number of possible values by it.

2^74                                             =  18,889,465,931,478,580,854,784
colliding pairs per ms, 10,000 * 9,999 / 2       =  49,995,000
milliseconds between expected collisions
  18,889,465,931,478,580,854,784 / 49,995,000    =  377,827,101,339,705
milliseconds in a year, 365.25 * 86400 * 1000    =  31,557,600,000
years between expected collisions
  377,827,101,339,705 / 31,557,600,000           =  11,972

The middle line is n * (n - 1) / 2, the number of distinct pairs among 10,000 IDs — each pair is one chance to collide.

One expected collision every 12,000 years at 100x your peak load. That is not a real risk. Say the number and move on rather than hand-waving about “probably fine.”

Cost 3: no node id. You lose the ability to look at an ID and know which process made it, which is a genuine debugging loss and the reason to log the generator identity separately.

Cost 4: monotonicity within a millisecond is not free. Two UUIDv7s created in the same millisecond share a timestamp prefix, so their order is decided by the random bits — which means they sort randomly relative to each other. Snowflake’s sequence counter gives you that ordering for free; here you have to implement one of RFC 9562’s monotonic variants, which use rand_a as a counter inside the millisecond.

This matters most for cursors. WHERE id > $last ORDER BY id LIMIT 100 assumes a total order that does not change between pages. If two IDs in the same millisecond straddle a page boundary and their relative order is arbitrary, you get duplicated and skipped rows — a bug that looks like a data problem and is actually an ordering problem.

What it buys

Set against those four costs is one benefit large enough to usually settle the argument.

Every problem in Deep dive 3 where the node id comes from disappears. No node ids, no ZooKeeper, no lease, no /22 subnet constraint, no 512-pod ceiling, no silent-duplicates-from-a-cloned-config outage. That is the entire operational surface of Snowflake, deleted, in exchange for 8 bytes per row.

The decision rule to say out loud: take UUIDv7 unless something downstream genuinely requires 64 bits. Things that genuinely require it: an existing BIGINT schema you are not migrating, a wire protocol with a fixed 8-byte field, a system where the ID is packed into a composite key with a hard width. Things that do not: “128 bits feels wasteful,” and “we might need to know the node.”

The table below puts all four schemes side by side. Snowflake and UUIDv7 agree on every row that matters to a user; the only rows where they differ are “Bits”, “Coordination at startup”, “PK index at 1B rows”, and “Exhausts” — and only the second of those has any operational weight.

The last row means what it says: because a plain counter is dense, subtracting two identifiers issued a day apart tells an outsider exactly how many rows you wrote that day. Interviewer pushback covers what to do about that.

13. Bottlenecks and scaling

What actually runs out in this design is never the thing people expect.

There is no throughput bottleneck. One node covers 4.096 million IDs/s against a 100,000/s peak, so every interesting limit is somewhere else.

Six limits below. The first three are bit-budget limits, fixed at design time; the last three are runtime limits you hit on a bad day.

The lock-contention row is the one that bites at high rates in practice. A single mutex-protected generator serializes every write path in the process, because only one thread at a time can be inside it — the shifting and masking take nanoseconds, but the queue to get in does not.

At 4 million IDs/s the contention on that lock is the cost, not the arithmetic inside it. That is the argument for a lock-free implementation built on CAS — compare-and-swap, a single CPU instruction that writes a value only if the location still holds the value you last read. Threads that lose the race retry instead of queueing, so no thread is ever descheduled waiting for another. It is also an argument for UUIDv7, where the only shared state is the current millisecond.

The scaling patterns from chapter 01 barely apply here, and it is worth saying why: this is the rare component with no state to shard, no cache to warm, and no replica that can fall behind. The only shared resource in the whole design is the node-id namespace.

14. Failure modes

Below is every way the design breaks in production, with the trace, the signal that reveals it, and the guard.

Note the pattern before you read the rows. The first two are the two assumptions this chapter has been stating all along — one node id per generator, and a clock that never goes backwards. Everything below them is a consequence of one of those two.

The last row is not distributed-systems theory and it costs teams real days, so it is worth the arithmetic.

JavaScript stores every number as a double-precision float. A double has 53 bits of mantissa, so it represents integers exactly only up to 2^53 = 9,007,199,254,740,992 — about 9.0 quadrillion. A Snowflake ID like 141,264,821,508,263,936 is roughly 15 times larger than that, so JSON.parse rounds it to the nearest representable value with no error and no warning.

A 64-bit ID does not survive JSON.parse. Two IDs that differ in their low bits can round to the same number, which is how “two records merged” gets reported as a data bug. Serialize identifiers as strings at every API boundary. It costs nothing, and it is invisible until a customer finds it.

15. Alternatives rejected

Five designs a reasonable person would propose instead — what each is genuinely good at, the specific reason it loses here, and the condition under which to revisit it.

Multi-master auto-increment (auto_increment_increment = N, auto_increment_offset = i). Good: zero new infrastructure, and each master is genuinely independent.

Rejected for two reasons. First, the stride N is baked into every ID ever issued, so changing it when you add a master either collides with existing IDs or leaves permanent gaps — the fleet size becomes immutable. Second, the ordering is wrong in a subtle way: master A at offset 1 and master B at offset 2 interleave by issue count, not by time. If A takes twice B’s traffic, A’s IDs run ahead, and comparing two IDs tells you about relative write volume rather than about time. Revisit only for a fixed two-node fleet with no ordering requirement.

UUIDv4. Good: zero coordination, zero clock dependency, available in every standard library, and genuinely collision-free in practice.

Rejected on the index: 1.8x the primary-key size at one billion rows, and an insert ceiling near 20,000/s bounded by random reads. Both are derived in Deep dive 1 why a uuid loses and where exactly.

But it is the correct choice for any identifier that is never a clustered key — a clustered key being the one the rows are physically ordered by on disk. If nothing sorts by the identifier, none of §7’s costs apply. An idempotency token (a value a client sends so a retried request is not applied twice), a request id, and a trace id are all exactly that: identifiers that are looked up but never sorted by.

Ticket server (one row, REPLACE INTO ... auto_increment, everyone asks). Good: dense IDs with no gaps, trivially understood, and the dense-counter property is genuinely useful — chapter 08 needs exactly that and uses it.

Rejected here for a specific reason people miss: past what one row can commit per second you must batch, and batching destroys the property you wanted. Derive the threshold rather than asserting it, because it is the whole argument.

Every ID is one update of one row. Updates of a single row are strictly serial — the second waits for the first to release the row lock — so the ceiling is one second divided by the time that row spends locked. The lock is held for the update itself plus the commit that follows it. Take the components What one row can actually do prices, minus the synchronous replica acknowledgement a ticket server does not need:

row update plus its WAL record            40   us
group commit fsync                       200   us
lock hold, us                                     =    240
one row's ceiling, IDs/s
  1,000,000 / 240                                 =  4,167
IDs per allocation needed at the 100,000/s peak
  100,000 / 4,167                                 =     24

The WAL, or write-ahead log, is the durable record a database writes before applying the change itself; the fsync is the system call that forces that record onto the disk, and it is the expensive part. 1,000,000 in the fourth line is microseconds in a second.

One row does about 4,000 IDs a second, so a 100,000/s peak forces blocks of roughly 24 — and that is what destroys the ordering. Here is why, concretely. Node A is handed block [1000, 1999]; node B is handed [2000, 2999]. Node B emits 2000 at 09:00. Node A, which has been quiet, emits 1500 at 11:00. The later ID is the smaller number, so the IDs no longer order by time at all.

Two footnotes on that number, both of which people get wrong.

It is a server ceiling, not a client one. It is a different number from the per-caller 1 / 0.0005 = 2,000 in Library or service, which is set by round-trip latency and does not bind on its own. Fifty concurrent callers clear 100,000/s without a single one of them batching — and every one of those calls still lands on the same row, so the 4,167 ceiling binds anyway.

Check which side of the threshold you are on before rejecting the design. chapter 08 runs exactly this allocator at 1,000 writes/s, which is 1,000 / 4,167 = 24% of one row’s ceiling, and needs no batching at all.

Add the single point of failure — every write in the system queued behind that one fsync — and a 0.5 ms round trip on the write path, and at this system’s rate the ticket server loses on three axes at once.

Database-native UUID v7 / gen_random_uuid() server-side. Good: no client library at all, and no way for one language’s implementation to drift from another’s.

Rejected because the ID is then unavailable until after the round trip. The application cannot construct the object graph, log the id, or emit an event carrying it before the write commits — and if the write times out, it has no way to ask “did my row get created?” Generating the ID client-side is what lets a write be idempotent and retryable.

A hybrid logical clock. Good: it is the correct answer if you need an order consistent with causality — if one event caused another, the first sorts earlier, no matter what any wall clock says — rather than with approximate wall time.

Rejected because nothing in this design reads an identifier as a statement about what happened before what. The IDs are a sort key and a primary key, not a happened-before relation. Revisit the moment you find yourself comparing IDs across nodes to decide which of two writes won.

16. Interviewer pushback

Eight questions this design attracts, each answered the way you would say it out loud, with a note on what the question is really testing. Every number in them is derived above; what is new is the phrasing and the order the numbers come out in.

“Why not just use a UUID?” Testing: whether the objection is memorized or derived. Not because of collisions — the birthday bound at a trillion IDs is around ten to the minus thirteen, so that argument is wrong. The problem is that the high bits are random, so every insert lands at a uniformly random leaf of the primary-key B-tree. That does two things. It converges the fill factor to about 69% instead of the 90% an appended key holds, and combined with the wider key that makes the index 1.8x larger at a billion rows, 40.8 GB against 22.4. And it turns writes into random reads: with a 16 GB buffer pool only 39% of that index is resident, so 61% of inserts must fault a leaf in first, and at 8 KB pages against 100 MB/s of random NVMe that is about 12,200 page reads per second, capping inserts near 20,000 per second. The ordered key never reads from disk at all because it keeps hitting the same rightmost page. If the ID is not a clustered key, UUIDv4 is fine and I would use it.

“Where does 41 bits come from?” Testing: whether the layout is a budget or a recipe. From the lifetime requirement, backwards. Two to the 41 is 2.199 trillion milliseconds, which over 1000, then 86,400, then 365.25 is 69.68 years. That is the whole reason the epoch matters: with the Unix epoch the window closes in 2039, so you would ship a format with 13 years on it. Setting the epoch to launch date buys the full 69.68, out to 2093, and it is a one-way door because changing it later shifts every future timestamp into ranges already issued. If I needed 139 years I would take 42 bits and pay for it out of the node field: 42/8/13 gives 139 years, 256 nodes, and 8,192 IDs per millisecond.

“You have 12 sequence bits. Is that enough?” Testing: whether you know what the field is for. It is 4,096 per millisecond per node, so 4.096 million per second per node and 4.19 billion per second across 1,024 nodes. Against a 100,000 per second peak that is 42,000x over, so it is obviously enough for throughput — but throughput is not what the field buys. It buys burst tolerance inside one millisecond. A fan-out write that needs 100,000 IDs in the same millisecond needs 24.4 nodes’ worth of sequence space, so it needs at least 25 generators participating or it stalls for 24 milliseconds. That is why I size the generator count from the burst shape and not from the mean rate, and it is the main argument for embedding the generator in every app pod: 400 pods is 1.6 million IDs per millisecond.

“NTP steps the clock back 300 milliseconds. What happens?” Testing: the failure that actually happens. Without a guard, the node re-enters a millisecond it already used, the sequence counter restarts at zero, and it silently reissues IDs it already handed out — a duplicate primary key that surfaces hours later with no way to tell which write is the imposter. Two fixes and I would ship both with a threshold. Below a few milliseconds, wait it out: that band is slew jitter, and a two-millisecond latency bump beats a two-millisecond error burst. Above it, refuse to issue and fail the health check, which converts a correctness problem into an availability problem, which is the right trade for a primary key. The detail I would insist on is that the wait budget has to be a deadline on the call rather than a test on one reading of the drift — against a clock that is still retreating while you sleep, a per-sample test passes every time and the “bounded wait” becomes an unbounded hang, which is the failure the refuse branch existed to prevent. The important structural point is that a 300 ms NTP step is uncorrelated across nodes so a load balancer routes around it, but a leap second fires on all 1,024 nodes at the same instant and the same guard becomes a fleet-wide outage. So the real fix is upstream: slew-only NTP and a leap-smeared time source, which spreads the second over 24 hours at about 1.16 parts in 100,000 and makes a rewind impossible.

“Do all your nodes need synchronized clocks?” Testing: whether you understand the uniqueness proof. No, and this is the part that surprises people. Uniqueness rests on the tuple of timestamp, node id, and sequence, and the node id is unique per generator, so the proof never mentions any other node’s clock. Each node only needs its own clock to be non-decreasing. What cross-node skew costs is sort accuracy: with about 10 milliseconds of intra-datacenter offset, two IDs created within 10 milliseconds on different nodes may sort in the wrong order. If I needed an order that respects causality rather than approximate wall time, Snowflake would be the wrong tool and I would want a hybrid logical clock or a commit-wait protocol.

“How does a node learn its node id?” Testing: whether you know where the real outages come from. This is the failure mode, not the clock. Static config is the worst option because cloning a config file produces two generators with the same id and duplicates that look like application bugs. Deriving it from the last 10 bits of the private IP is free and correct only inside a single slash-22, because 32 minus 10 is 22 and a slash-22 holds exactly 1,024 addresses. The right answer is a lease from ZooKeeper or etcd keyed by stable identity, with one addition people forget: persist the last issued millisecond next to the lease and refuse to serve on startup until the wall clock passes it. Otherwise a crashed node’s slot gets relet to a pod with a slower clock, which is the cross-restart version of the rewind bug.

“Would you use UUIDv7 instead?” Testing: whether the answer is current. Yes, unless something downstream genuinely requires 64 bits. UUIDv7 puts 48 bits of Unix milliseconds at the front, which is 8,920 years, so there is no epoch decision and no exhaustion plan. The index cost is honest: 16-byte keys inserted in order fill at 90%, so a billion rows is 31.3 GB against 22.4 for a bigint — 1.4x, entirely the key width, with none of UUIDv4’s fill-factor penalty. Uniqueness becomes probabilistic on 74 bits of per-millisecond entropy, which at 10,000 IDs per millisecond is one expected collision every 12,000 years. What I get for that 8 bytes is the deletion of the entire node-id problem: no leases, no coordination store, no subnet constraint, no silent-duplicate-from-a-cloned-config incident. Things that would keep me on Snowflake: an existing BIGINT schema I am not migrating, or a wire format with a fixed 8-byte field.

“Your IDs are sequential. Does that leak anything?” Testing: whether you think about the ID as data. Snowflake leaks less than a plain auto-increment but it does leak. A plain counter leaks total volume directly: subtract two IDs a day apart and you have the day’s row count. Snowflake leaks per-node rate the same way, since two IDs from the same node in the same millisecond differ by their sequence values. And every Snowflake ID discloses its creation time to the millisecond, which is sometimes exactly what you want and sometimes a privacy issue. If the ID is user-visible and the enumeration matters, do what chapter 08 does: keep the dense ordered value internally and expose a bijective permutation of it externally, so the external token is unguessable while the storage key stays sequential.

Cheat sheet

Every result in this chapter, compressed to one line each, in the order it was derived.

Next: 08 — URL Shortener — where the ID generator becomes a dependency, and the base-62 length falls out of the ten-year volume.