How to design a distributed unique-ID generator

How does a fleet of machines hand out identifiers that never collide, all fit in 64 bits, and still sort by the moment they were created, without any machine stopping to ask another for a number?

In this lesson, we’ll answer that by deriving the ID from its 64-bit budget outward. By the end you’ll be able to lay out the bits, say what each field costs the others, and defend the design against the two things that actually break it in production: the machine’s clock and the way each machine learns its own number.

On one machine, a unique ID is free: one process owns a counter and hands out 1, 2, 3. No number goes out twice. Across a fleet, no single process 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, and avoiding that call is the whole point.

So the job is an identifier that is:

• unique across the whole fleet,
• sorted in the order it was created,
• 64 bits wide,
• and produced without coordination.

Two things can break it, and each gets a deep dive below: the machine’s clock, and the way each machine learns its own number.

Input and output. Nothing goes in: a network round trip to ask for a number is exactly what the design avoids. The output is one integer that packs three fields into 64 bits; reversing the packing recovers all three:

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 best-known scheme for this is Snowflake, named after the internal Twitter service that popularised it. We’ll derive it here instead of quoting it.

64 bits is a fixed budget, and every property is paid out of it: how far into the future the format works, how many machines may generate at once, how many IDs one machine can produce inside a millisecond, and the time-sortability that lets the ID double as a database primary key. There is no slack.

What the design actually trades off

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 properties you keep when they compete for the same 64 bits.

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 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.

Each property below is paid for out of the same 64 bits, so no two are independent.

Three of those cells need unpacking.

BIGINT is the standard SQL type for a 64-bit signed integer; an ID that fits one needs no schema change anywhere. 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, so you can route a lookup without consulting any index. And a 64-bit ID has to cross an API boundary as a string, because JavaScript stores every number as a floating-point double that is exact only up to 2^53; above that, parsing an ID silently rounds it. That detail costs real teams real days and reappears in the failure table.

So uniqueness is the easy part. The design is about buying time-ordering and 64-bit width without a network round trip, and those constraints are what make the answer a bit layout, not an algorithm.

Four candidates, three eliminated

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 tracks issue rate,<br/>not time"]
    B --> B1["FAILS: 128 bits, and the<br/>high bits are random.<br/>Kills the B-tree PK"]
    C --> C1["FAILS: throughput forces<br/>batching, 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

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

UUIDv4. 128 bits, 122 random. It fails on width and on the randomness of its leading bits, which destroys the primary-key B-tree. The full cost is in the UUID deep dive below.

Ticket server. One shared counter every machine asks for numbers. Reaching the required throughput forces you to hand out numbers in blocks, and blocks destroy the time-ordering you asked for. Detailed in the alternatives section.

Snowflake: time | node | sequence. No round trip, 64 bits, and IDs that increase monotonically on each machine. Its cost is a clock you have to trust.

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, and they are not the same. Clock skew is the difference between two machines’ idea of the current time right now: A says 12:00:00.010, 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; skew is what drift accumulates into.

Non-functional

p99 is the 99th-percentile latency: the number 99 of every 100 calls come in under, the tail, not the average. Availability is the fraction of time a component is actually answering. It is a hard requirement here because 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. That is why burst and mean differ so much. Averaged over a second the system wants 30,000 IDs, but a single fan-out can ask for 100,000 IDs inside one millisecond, and the generator has to survive that spike, not the average.

The key point: an ID generator sits in front of every write, so its availability multiplies into everything downstream. That is why the answer is a library, not a service, a choice that comes due later.

Back-of-envelope

Running out of 64-bit IDs is not a real risk, which reframes the problem from “will we have enough numbers?” to “how do we spend the bits?” (General estimation technique is in the estimation chapter.)

A decade of mean traffic is about 30,000 * 86400 * 365.25 * 10 ≈ 9.5 trillion IDs. The usable range of a signed 64-bit column is its positive half, 2^63 ≈ 9.2 * 10^18, only the positive half, because negative IDs would sort before positive ones. That is roughly a million times more than a decade needs.

You consume about one millionth of the space in ten years, so exhaustion is never the constraint; the layout is.

A dense counter (every value in order, no gaps) would need 44 bits to cover a decade, since 2^43 ≈ 8.8 trillion and 2^44 ≈ 17.6 trillion straddle it. That leaves 64 - 44 = 20 bits. Those twenty bits are the price of coordination-freedom, and Snowflake spends them on a node id and a counter that runs inside a single millisecond. And it is the burst number, not the mean, that sizes the fleet. The arithmetic for that is in the sequence section.

Data model: the 64-bit layout

There is no schema here: the data model is the bit budget. Each field is derived from a requirement, and changing one moves the others.

The layout is one 64-bit integer, bit 63 most significant, bit 0 least. The numbers 22 and 12 are where one field ends and the next begins; 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 fields add up exactly: 1 + 41 + 10 + 12 = 64.

• Sign bit, 1 bit. Pinned to 0 so every ID is a positive number in a BIGINT column, and 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 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 multiplies by 2^n, and because the three fields occupy non-overlapping bit ranges, | (bitwise OR) drops each into its own slot. For the example ID, node 37 at sequence 0: elapsed is 1,737,747,358,021 - 1,704,067,200,000 = 33,680,158,021 ms since the 2024 epoch; shifting that left by 22 and OR-ing in the node and sequence gives exactly 141,264,821,508,263,936. Unpacking runs it backwards, masking with 1023 = 2^10 - 1 for the node and 4095 = 2^12 - 1 for the sequence.

Two things follow. First, the node and sequence live entirely in the low 22 bits, so two IDs from the same millisecond differ by at most 2^22 - 1, while ticking to the next millisecond adds a full 2^22. That is why no amount of node or sequence variation can reach into the next millisecond’s range, and why the sort is by time first. Second (and this catches people), the decimal digits of an ID tell you nothing about its fields. The value 141264821510144037 ends in “37” but decodes to node 496, sequence 37, not node 37.

41 bits of milliseconds

2^41 milliseconds is about 69.68 years (2^41 / 1000 / 86400 / 365.25). That number is why the epoch is a design decision, not a default.

An epoch is the fixed instant the timestamp counts from, so it fixes both ends of the window: when the format starts working and when, 69.68 years later, the field overflows. The Unix epoch (midnight UTC, 1 January 1970) closes its window in 2039. Ship today on it and you have about 13 years left, having burned 56 years on time that had already passed. Set the epoch to the service’s launch date instead and the full window is ahead of you:

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

The epoch is a one-way door. Changing it later shifts every future timestamp: 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 that stores one. Pin it as a compile-time constant and never touch it.

More timestamp bits buy more years, but each bit has to come out of another field, because the total is fixed. That is what makes the budget zero-sum, not a memorized 41/10/12:

10 bits of node id

Ten bits give 2^10 = 1,024 distinct generators, and every generator must hold a different one, forever. That single number decides whether the generator can be a library or has to be a service. It is also the field people under-budget, because of a trap: on a container platform like Kubernetes a “generator” is a process, not a machine, and one machine runs many processes, so a 200-machine fleet can easily need 800 slots. The node-id deep dive returns to this.

12 bits of sequence

The sequence field looks like a throughput field, but it is not. 2^12 = 4,096 IDs per millisecond per node is 4.096 million per second per node, and across a full 1,024-node fleet 4.19 billion per second. Against the 100,000/s peak, the fleet is roughly 42,000x over-provisioned on throughput. When a number comes out that far off you are measuring the wrong thing: sequence bits do not buy throughput, they buy tolerance for a burst inside a single millisecond.

Averaged over a second, one node covers the 100,000/s peak forty times over. But a fan-out asks for 100,000 IDs inside one millisecond, and one node has only 4,096 of them in that millisecond: 100,000 / 4,096 ≈ 25, 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. Size the node count from the burst, not from the mean.

High-level architecture

Where the generator lives is a shorter list than for most designs. Solid arrows are per-call; the dotted arrow is a background process. What is absent matters just as much: no arrow runs from the write path out to a network service to fetch an ID.

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

    style LIB fill:#2d6a4f,color:#fff

The application pod. A pod is one running copy of the application, the unit 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 returned identifier goes straight in as the row’s primary key.

The coordination store. ZooKeeper and etcd are small, strongly consistent key-value services for 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 already spent, the cross-restart version of the rewind bug.

The NTP client. NTP (Network Time Protocol) keeps the machine’s clock close to true time by disciplining CLOCK_REALTIME, the wall-clock source that can jump. It runs continuously in the background, and it is drawn because it is not a default install: it must be configured slew-only and leap-smeared, two settings the clock deep dive defines.

Three claims are packed into that picture. The generator is in-process, so ID generation cannot become unavailable independently of the caller. Coordination happens once, at startup, to lease a node id, never once per identifier, which is the difference from a ticket server. And the clock is an input with a failure mode, which is why it is drawn as an arrow into the library, not assumed.

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

“UUIDs are bad for indexes” is folklore until you can reproduce the cost as a number. Getting there means first discarding the two objections people usually reach for.

A UUID is a 128-bit value standardised so independently generated ones do not collide. UUIDv4 is the all-random variant: 128 bits, 122 of them random.

Weak objection 1: “it might collide.” It will not. The birthday bound (a room of 23 people probably shares a birthday) estimates a random collision over n IDs from 122 bits at about n^2 / 2^123, at a trillion IDs, roughly one chance in ten trillion. Collision is not the argument.

Weak objection 2: “it is too big.” Twice the width, 8 extra bytes a row. Nobody rejects a design over that alone.

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 turns an append at the end of the index into a random write into the middle of it, and this cost is a number you can compute.

Two facts drive it. Ordered inserts always land on the rightmost leaf, which stays packed at roughly 90% full (Postgres’s default B-tree leaf fill factor) and stays resident in the buffer pool (the database’s in-memory cache of pages) because every insert touches it again. Random inserts split full leaves in half, and a B-tree under uniformly random insertion converges to a steady-state occupancy of ln 2 ≈ 69%, the classical result of Yao (1978), On random 2-3 trees; that is a property of the split rule, so no engine tuning recovers it. The mechanism underneath (page splits) is derived in the database internals chapter.

Applied to a one-billion-row table on 8 KB pages: a bigint index is about 22.4 GB, a UUIDv4 index about 40.8 GB, a factor of 1.8x, which factors cleanly into a 1.4x key-width penalty (a 16-byte key packs fewer entries per page than an 8-byte one) times a 1.3x fill-factor penalty (90% vs 69%).

Index size is what you see on a dashboard. What shows up as an incident is write throughput, in three steps. The 40.8 GB random index does not fit a 16 GB buffer pool and is touched everywhere, so only about 16 / 40.8 ≈ 39% of it stays cached; the other 61% of inserts must first read an 8 KB leaf off disk before writing. An NVMe drive doing 100 MB/s of random reads delivers about 100,000,000 / 8192 ≈ 12,200 pages/s, and dividing by that 61% caps inserts near 20,000/s, bounded by random read I/O, on a machine whose ordered-key ceiling is set by CPU instead, because ordered inserts hit the same hot rightmost page and never read from disk. That is what makes the objection reproducible, not received wisdom.

Two secondary consequences: a UUID cannot serve as a cursor (WHERE id > $last ORDER BY id LIMIT 100 requires time-ordered IDs), and range-partitioning by ID becomes impossible, so a query can no longer skip whole time buckets and an archival job can no longer drop the oldest one.

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

Snowflake assumes something exact about clocks. When that assumption fails, something specific breaks, and there are three fixes with three different costs.

The assumption, stated precisely

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 never mentions: any other node’s clock.

So the assumption is narrower than people expect. 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, very different in severity:

• Skew between nodes costs sort accuracy, not uniqueness. NTP typically holds machines within about 10 ms 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: if event A caused event B, A must sort first, whatever the clocks say. Snowflake cannot give you that; a hybrid logical clock (a physical timestamp paired with a logical counter bumped on messages from ahead-of-you machines) or Spanner-style commit-wait (a transaction waits out the clock’s stated uncertainty before committing) can.

• 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

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, sequence 0, 1, 2, 3.
2. NTP steps the clock back 300 ms. It 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), 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 apart in wall-clock terms, because the collision only surfaces when both rows reach the same table, and by then nothing tells you which write is the imposter. Note the shape: the guard has to be per-node and local, because the assumption that broke was about one machine’s own clock, not agreement between machines.

Where the rewind comes from

Two words carry the distinction, and they come back in every fix. To step a clock is to jump it instantly to the correct value, a step can move it backwards. To slew a clock is to speed it up or slow it down slightly until it drifts into agreement, a slew never moves it backwards. A leap second is an extra second inserted into UTC to track the earth’s rotation; the naive way to apply one is a one-second step.

The leap-second row is the dangerous one, for a structural reason. Every other cause is uncorrelated across nodes: one machine’s NTP steps and the rest of the fleet is fine, so a per-node “refuse to serve” degrades gracefully behind a load balancer that routes to a healthy node. 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, each 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 did. It is unambiguously safe: no ID is issued, so none can duplicate. It converts a correctness problem into an availability problem, which is the right trade for a primary key. The cost is one node unavailable for the duration of the rewind (300 ms of errors for a 300 ms step; 1 s from every node at once for a leap second).

• Fix 2: wait it out. Sleep until the wall clock catches up to last_ms, then proceed. Equally safe, and better for small rewinds, a 2 ms latency bump beats a 2 ms error burst. Worse for large ones, because an unbounded sleep is a hang no timeout budget expects.

Ship both, separated by a threshold. Wait out anything below a few milliseconds (that band is slew artifact and turning it into errors is self-harm), refuse anything above it (a larger rewind is a real event a human needs to see). The code below uses 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. The tempting implementation samples the drift once, decides it is inside the budget, and loops. That is correct against a clock that rewinds once and behaves, but not 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 passes every time, and the call blocks indefinitely. 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, 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 and re-check it inside. The monotonic clock is a separate OS time source that only ever moves forward and is never adjusted by NTP, which makes it immune to the exact fault being handled. Use the wall clock to decide what to wait for, and the monotonic clock to decide how long.

The same trap in the exhaustion loop

The rule applies to every loop that waits on the wall clock. The generator has a second one: when the 4,096 sequence values for the current millisecond are spent, it waits for the clock to reach the next millisecond, with exit condition now > last_ms. A frozen clock never satisfies that either, and a frozen clock is two rows of the table above (the suspended VM, the failing TSC). Left unbounded, the loop lets exactly 4,096 IDs out and then blocks call 4,097 forever 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.

The third fix, which is what modern generators do

There is a fix that neither errors nor blocks. Stop reading the wall clock directly and 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.

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

Drop else: seq = 0 and the sequence becomes a global counter: the generator exhausts 4,096 IDs in total, not per millisecond, and every overflow after that shoves ts another millisecond into the future, so the timestamps drift away from real time. Drop last_ms = ts and there is no logical clock at all: ts == last_ms is never true, seq is pinned at 0, and on a frozen clock the generator hands out one identical ID forever.

What it buys and costs. It never blocks and never duplicates, which is why modern generators use it. The cost: during and after a rewind, the embedded timestamp runs ahead of real time by up to the size of the rewind, so decoding an ID gives you an upper bound on its creation time, not the time. For a sort key that is fine. For an audit timestamp it is not, and an ID was never a safe place to keep one anyway.

Configure the clock, not just the code

The code guards are the last line of defence. Three 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 instead of jumping it. A slewed clock is always monotone.
• Leap smear. Google’s and AWS’s public NTP endpoints spread the leap second across 24 hours, a rate adjustment of about 1.16 parts in 100,000, too small for anything to notice. Because it is a slew, the clock never moves backwards. A fully smeared fleet cannot have a leap-second rewind at all, which turns the single worst correlated failure into a non-event.
• Never mix smeared and unsmeared sources in one fleet. Halfway through a smear the two families are up to 0.5 s apart, harmless for uniqueness, terrible for comparing timestamps across nodes.

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. Every duplicate assignment creates two generators that silently produce the same identifiers.

Four terms: an autoscaler starts and stops copies of an application in response to load. It is what makes “someone will clone the config” a certainty, not a risk. A /22 is a block of IP addresses sharing their first 22 bits, so it holds 2^(32-22) = 1,024 addresses, exactly the size of the node-id field, which is why the IP trick works inside one /22 and collides across two. A StatefulSet is the Kubernetes object that gives each copy a stable numbered name; the more common Deployment gives random names. A lease is a claim that expires unless renewed; in ZooKeeper it is an ephemeral znode, deleted automatically the moment the client’s session ends.

The ephemeral-lease trap survives code review:

1. Node 37 crashes; its session ends, so the znode is deleted and slot 37 is free. That is what “ephemeral” means, and it is normally the feature.
2. A new pod takes slot 37. Its clock reads 200 ms behind the dead node’s last-issued timestamp.
3. It issues in a millisecond range slot 37 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, the same guard as the clock deep dive, applied across process restarts.

Does 1,024 fit your fleet?

With an in-process library a “node” is a process, not a machine. Add deployments: a blue-green deploy brings the whole new version up alongside the old and switches once it is healthy, so for the length of that window both generations hold leases and peak slot usage is twice steady-state. 400 pods * 2 = 800, and the safe ceiling is 1,024 / 2 = 512. With 10 bits and a blue-green rollout you can run 512 pods, not 1,024, and zombie pods still holding leases eat into that.

A fleet already at 400 pods with growth ahead should take the 41/12/10 layout: 4,096 nodes at 1,024 IDs per millisecond per node, still about 1 million IDs/s per node. And embedding the generator turns the node-id field into burst capacity: 400 pods * 4,096 per ms = 1.6 million IDs in a single millisecond against a 100,000 burst requirement, 16x over. That is why the layout question and the library-versus-service question are the same question.

Library or service

The generator can ship in two shapes. As a library, in-process, calling it is a function call: gen.next_id(). As a service, over RPC (a remote procedure call, a function call that crosses the network), a separate cluster hands out IDs and a node whose clock has moved backwards fails its health check so a load balancer (the machine that owns the public address and forwards each call to a healthy node) stops sending it traffic.

Two rows unpack. Batching: at 0.5 ms per round trip, one caller making one call at a time cannot exceed 1 / 0.0005 = 2,000 IDs/s, so a higher rate forces requesting IDs in batches, which means holding unused IDs and issuing them out of time order. Polyglot (a fleet in several languages): the library form means reimplementing the rewind guard, the deadline, and the exhaustion loop once per language, and the bugs will differ per language.

Default to the library. Two conditions flip it: a polyglot fleet, or a fleet large enough that one node id per process does not fit the field. If you take the service form, batch, and batching is precisely what kills the ticket server.

Working Python

The whole design as running code, so every claim above is executable. Snowflake implements the wait-or-refuse threshold; MonotonicSnowflake implements the logical-clock fix.

The generator holds a mutex (a lock that lets only one thread at a time run the code inside it) because _last_ms and _seq are one piece of state that must be read and updated together; two threads interleaving there would issue the same ID. Both waiting loops take their deadline from time.monotonic(), never from the wall clock they are waiting on: the thing that decides how long you wait must be immune to the fault you are waiting out. And the exhaustion path sleeps instead of busy-spinning, because the mutex is held throughout, a spin would block every other thread and burn the core they would run on.

"""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 already issued from;
    continuing would reissue a (ts, node) pair -- a silent duplicate PK."""


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 budget is a real event: an
                    # NTP step, a leap second, a migrated VM. Refuse, so the
                    # health check fails and 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. The
                # deadline bounds the CALL: a clock still retreating while we
                # sleep passes the per-sample drift test every iteration and
                # would block forever without one monotonic deadline.
                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 {self.max_wait_ms} ms on node {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, under the same monotonic deadline
        as the rewind guard: a frozen clock (a suspended VM, a failing TSC)
        never satisfies `now > _last_ms` and would block call 4,097 forever
        while holding the mutex. A healthy clock leaves this loop inside one
        millisecond, so bound the wait at that and refuse past it. Sleep,
        never spin -- the lock is held."""
        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}: this "
                    f"ms's sequence is spent and the clock 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):
    """The logical-clock fix: a clock that tracks the wall clock upward and
    never follows it down. Never blocks, 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)

The assertions below hold the design to its claims. The key to all of them is scripted_clock: a clock that returns a prepared list of times, so a test can make the clock jump backwards, stop, or retreat on every read. You cannot wait around for a real NTP step. Both halves of the rewind threshold have to be tested separately, because a generator built with max_wait_ms = 0.0 puts every rewind above the budget and would exercise the refuse path twice and the wait path never.

def scripted_clock(values):
    """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 and the literal ID from the intro ---------------------
assert MAX_NODE == 1023 and MAX_SEQUENCE == 4095
assert TIMESTAMP_SHIFT == 22 and NODE_SHIFT == 12

g = Snowflake(node_id=37, clock=lambda: 1_737_747_358_021)
first = g.next_id()
assert first == 141264821508263936
assert first < (1 << 63)                       # positive in a signed BIGINT
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)["node_id"] == 496

# --- monotonic within and 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

# --- a large rewind is REFUSED, a small one is WAITED OUT -------------
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

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 and Snowflake.decode(two)["sequence"] == 1

# --- a clock that does not ADVANCE must refuse, not block ------------
# Exactly 4,096 IDs fit in one ms; a frozen clock issues them, then the
# 4,097th call must raise rather than block forever holding the mutex.
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
try:
    g.next_id()
    raise AssertionError("a frozen clock must raise, not block for ever")
except ClockMovedBackwards:
    pass

# 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 hang.
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)

# --- 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()

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

UUIDv7 and ULID: the modern answer

The modern alternative deletes Snowflake’s entire operational surface in exchange for 8 bytes a row, and it is what you should reach for whenever the 64-bit constraint is not real.

RFC 9562 (2024) defines UUIDv7: a UUID whose leading bits are a timestamp, not random. The timestamp is still first, for exactly the same sorting reason as Snowflake, but there is no node field and the rest is random:

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

version and variant are fixed bit patterns that let any reader identify the scheme; rand_a can optionally be a sub-millisecond counter, which is how the monotonic variants work. ULID is the same idea in a different skin (48 bits of milliseconds plus 80 random) rendered in Crockford base32 (an alphabet that excludes the confusable I, L, O, U), so a ULID is 26 characters that sort correctly as plain text and you can ORDER BY the string form directly.

The 48-bit timestamp is about 8,920 years (2^48 / 1000 / 86400 / 365.25), so there is no epoch decision, no exhaustion planning, and no format migration in anyone’s career.

Four costs, relative to Snowflake.

1. The key doubles, 128 bits instead of 64, but only the cheap half of UUIDv4’s penalty. Because the high bits are time-ordered, inserts append and leaves fill to 90% again, so a billion rows is about 31.3 GB, which is 31.3 / 22.4 = 1.4x a bigint, entirely the key width, with none of UUIDv4’s fill-factor penalty.
2. Uniqueness becomes probabilistic, not proven, resting on 74 bits of per-millisecond entropy (12 bits of rand_a plus 62 of rand_b, refreshed each millisecond). By the birthday bound, even at 10,000 IDs per millisecond (about 100x this system’s peak) that is one expected collision every 12,000 years. Not a real risk.
3. No node id, so you cannot tell from an ID which process made it, a genuine debugging loss, and the reason to log the generator identity separately.
4. Monotonicity within a millisecond is not free. Two UUIDv7s in the same millisecond share a timestamp prefix, so their relative order is decided by the random bits and is arbitrary. Snowflake’s sequence gives that ordering for free; here you must use one of RFC 9562’s monotonic variants. It matters most for cursors: if two same-millisecond IDs straddle a page boundary with arbitrary order, WHERE id > $last ORDER BY id duplicates and skips rows.

The one benefit that usually settles it: every problem in the node-id deep dive disappears, no node ids, no ZooKeeper, no lease, no /22 constraint, no 512-pod ceiling, no silent-duplicate-from-a-cloned-config outage.

Decision rule: take UUIDv7 unless something downstream genuinely requires 64 bits, an existing BIGINT schema you are not migrating, or a wire protocol with a fixed 8-byte field. “128 bits feels wasteful” and “we might want the node id” do not count.

The last row: because a plain counter is dense, subtracting two IDs issued a day apart tells an outsider exactly how many rows you wrote that day. Snowflake leaks per-node rate the same way and discloses each creation time to the millisecond. If the ID is user-visible and enumeration matters, keep the dense ordered value internally and expose a bijective permutation of it externally, as the URL shortener chapter does.

Bottlenecks and scaling

What runs out is rarely what 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 elsewhere.

The lock-contention row is the one that bites at high rates. A single mutex-protected generator serializes every write path in the process. 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 argues for a lock-free implementation built on CAS (compare-and-swap, a single CPU instruction that writes only if the location still holds the value you last read), where threads that lose the race retry instead of queueing, and for UUIDv7, whose only shared state is the current millisecond.

The scaling patterns from the scaling chapter barely apply, because 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.

Failure modes

Every way the design breaks in production. The first two rows are the two assumptions (one node id per generator, and a clock that never goes backwards) and everything below is a consequence of one of them.

The last row is not distributed-systems theory, and it costs teams real days. JavaScript stores every number as a double, exact only up to 2^53 ≈ 9.0 quadrillion; a Snowflake ID is roughly 15x larger, so JSON.parse rounds it with no error and no warning, and 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 is invisible until a customer finds it.

Alternatives, and when to revisit them

Multi-master auto-increment (auto_increment_increment = N, auto_increment_offset = i). Zero new infrastructure, each master independent. Rejected twice over: the stride N is baked into every ID ever issued, so changing it collides or leaves permanent gaps and the fleet size becomes immutable; and masters interleave by issue count, not time, so comparing two IDs tells you about relative write volume, not time. Revisit only for a fixed two-node fleet with no ordering requirement.

UUIDv4. Zero coordination, zero clock dependency, in every standard library. Rejected on the index: 1.8x the primary-key size and an insert ceiling near 20,000/s, both derived above. But it is the correct choice for any identifier that is never a clustered key, the column rows are physically ordered by on disk. 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 looked up but never sorted by, so none of the index costs apply.

Ticket server (one row, everyone asks). Dense, gapless IDs; genuinely useful where a dense counter is wanted: the URL shortener chapter uses exactly this at 1,000 writes/s and needs no batching. Rejected here for a specific reason: past what one row can commit per second you must batch, and batching destroys the ordering. Every ID is one update of one row, and updates of a single row are strictly serial, the second waits for the first to release the row lock. The lock is held for the update plus the commit fsync (the system call that forces the write-ahead log onto disk, the expensive part), roughly 240 µs, so one row does about 4,000 IDs/s. A 100,000/s peak then forces blocks of about 24, and blocks reorder time: node A holding [1000, 1999] can emit 1500 two hours after node B emits 2000, so the later ID is the smaller number. (Full pricing of one row’s commit is in the digital wallet chapter.)

Database-native gen_random_uuid() server-side. No client library, no cross-language drift. Rejected because the ID is 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 cannot ask “did my row get created?” Generating the ID client-side is what lets a write be idempotent and retryable.

A hybrid logical clock. The correct answer if you need an order consistent with causality, not approximate wall time. Rejected because nothing here reads an ID 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.

Conclusion

• Uniqueness is the easy part. The design exists to buy time-ordering and 64-bit width without a network round trip, which forces the answer to be a bit layout: 1 sign + 41 timestamp + 10 node + 12 sequence.
• The 41-bit timestamp lasts 69.68 years, so the epoch is a one-way door, set it to launch date (out to 2093), pin it as a constant, and never change it.
• Sequence bits buy burst tolerance, not throughput: 4,096 per millisecond per node, sized from the fan-out spike, not the mean rate.
• Two assumptions carry the whole design: one node id per generator, and each node’s own clock never going backwards. Violating the first (a cloned config) is the more common outage; violating the second silently duplicates a primary key.
• The clock fixes are wait-below-a-threshold, refuse-above-it, and a monotonic deadline on every loop that waits on the wall clock, plus slew-only, leap-smeared NTP so most rewinds never happen. MonotonicSnowflake sidesteps the loops entirely by running on a logical clock.
• Prefer UUIDv7 unless something downstream genuinely requires 64 bits: it deletes the entire node-id and coordination problem for 8 bytes a row, and pays only the 1.4x key-width index cost, not UUIDv4’s 1.8x.
• Whatever the scheme, serialize 64-bit IDs as strings at every API boundary, because JSON.parse rounds anything above 2^53.

One line to remember: uniqueness is free; the design spends 64 bits to buy time-ordering without a round trip, and it lives or dies on one node id per generator and a clock that never goes backwards.

Further reading

• RFC 9562, Universally Unique IDentifiers (UUIDs) (IETF, 2024): defines UUIDv7 and the monotonic variants.
• Twitter Snowflake: the original announcement and the archived twitter-archive/snowflake source, for the exact bit layout and the refuse-on-rewind behaviour.
• The ULID specification (ulid/spec): the 48-bit-time + 80-bit-random layout and Crockford base32 encoding.
• A. C. Yao, On random 2-3 trees, Acta Informatica 9 (1978): the ln 2 ≈ 69% steady-state occupancy of a randomly-inserted B-tree.
• PostgreSQL documentation, B-tree indexes and fillfactor: the 90% default leaf fill and how page splits work.
• Corbett et al., Spanner: Google’s Globally-Distributed Database (OSDI 2012): TrueTime and commit-wait, for when you need causal ordering.

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