How to design a distributed unique-ID generator

Uniqueness is free; the design spends a fixed 64-bit budget to buy time-ordering without a network round trip, so the answer is a bit layout, not an algorithm. This is Snowflake.

The job

• One next_id() -> 64-bit integer: unique fleet-wide, sorted by creation time, produced with no coordination (no round trip to ask for a number).
• Monotonic: an ID issued later is numerically larger. Decodable back to (timestamp, node, sequence) for debugging.
• Exhaustion is never the constraint: a decade of mean traffic ≈ 9.5 T IDs vs 2^63 ≈ 9.2 × 10^18 usable (positive half only). The layout is the problem.

The 64-bit layout

 63  62                                    22        12       0
+---+--------------------------------------+---------+--------+
| 0 |        timestamp: 41 bits (ms)       | node:10 | seq:12 |
+---+--------------------------------------+---------+--------+
 sign=0        1 + 41 + 10 + 12 = 64      1,024      4,096
 (positive)                               nodes      per ms

• Timestamp is the most significant field, so integer comparison sorts by time first. Node first would sort by machine.
• Pack: elapsed << 22 | node << 12 | seq. Unpack: mask with 1023 (node), 4095 (seq).
• Decimal digits tell you nothing: an ID ending in “37” can decode to node 496.

Sizing each field

• Budget is zero-sum: more timestamp bits cost node or sequence bits. Alt layouts: 42/8/13 (long life, small fleet), 41/12/10 (many pods), 39/10/14 (extreme burst).
• Sequence sizes from burst, not mean. One node = 4.096 M IDs/s vs 100,000/s peak (42,000x over). But a 100,000-ID fan-out in one ms needs 100,000 / 4,096 ≈ 25 nodes; fewer stall waiting for the next ms.
• Epoch is a one-way door: changing it later collides or reorders every future ID. Pin as a compile-time constant.

Two assumptions carry the design

• One node id per generator, and each node’s own clock never goes backwards. Uniqueness proof: (ts, node, seq) is unique because node is unique and seq is unique within a ms. It never mentions any other node’s clock.
• Skew (difference between two clocks now, ~10 ms in a DC) costs only sort accuracy. A single clock going backwards (a rewind) costs uniqueness — reissues a spent (ts, node) = silent duplicate PK.
• A frozen clock is the same fault: it leaves you inside a (ts, node) pair already spent.

Clock rewind: the fixes

• Sources: NTP step (>128 ms offset), VM migration, leap second (hits all nodes at once), operator error, bad hardware. Step = instant jump (can go back); slew = gradual rate change (never back).
• Fix 1 — refuse (now < last_ms): raise, fail health check, reroute. Safe; turns correctness into availability. Best for large rewinds.
• Fix 2 — wait it out: sleep until the clock catches up. Best for small rewinds. Split by a max_wait_ms threshold: wait below, refuse above.
• Trap: a clock still retreating while you sleep passes a per-sample drift test forever. Bound the whole call with ONE monotonic-clock deadline (immune to NTP). Same deadline guards the sequence-exhaustion loop.
• Fix 3 — logical clock (MonotonicSnowflake): ts = max(last_ms, wall_now); never blocks, never duplicates. Cost: embedded timestamp becomes an upper bound on creation time, not the time.

ts = max(last_ms, wall_now)
if ts == last_ms:
    seq += 1
    if seq overflowed: ts += 1; seq = 0
else:
    seq = 0        # drop this: seq becomes a global counter
last_ms = ts       # drop this: no logical clock, seq pinned at 0

• Also configure the clock: slew-only NTP (ntpd -x), leap-smear (spreads the leap second over 24h, so no leap rewind), never mix smeared and unsmeared sources.

Node id and library-vs-service

• Assign via a persistent lease keyed by stable identity (hostname), storing last_issued_ms; refuse startup until now > last_issued_ms. Static config gets cloned; last-10-IP-bits only unique inside a /22 (1,024 addrs); ephemeral leases get reused by a pod with a slower clock.
• 1,024 slots don’t stretch far: blue-green deploy doubles peak usage, so safe ceiling ≈ 512 pods. Go 41/12/10 or UUIDv7 if larger.
• Ship as a library, in-process (sub-µs, cannot fail independently of the caller). Switch to a service only for a polyglot fleet or a fleet too big for the node field — and then you must batch, which reorders time (that is what kills the ticket server).

Gotchas and the modern answer

• Serialize 64-bit IDs as strings at every API boundary. JS numbers are doubles, exact only to 2^53; a Snowflake ID (~15x larger) silently rounds under JSON.parse.
• UUIDv4 loses on the index: random high bits scatter inserts across the B-tree, dropping fill to ln 2 ≈ 69% (Yao 1978) vs 90% for appends — ~1.8x index size, insert ceiling ~20,000/s. Fine only for non-clustered keys (idempotency/request/trace ids).
• Prefer UUIDv7 / ULID (RFC 9562, 48-bit ms timestamp first) unless something downstream truly needs 64 bits: deletes the entire node-id/coordination problem for 8 bytes a row, pays only the 1.4x key-width cost, lasts ~8,920 years. Loses the node id (log generator identity separately); needs a monotonic variant for same-ms ordering.
• Ticket server / multi-master rejected: batching reorders time; changing the stride N collides every future ID.