Design a Unique ID Generator in Distributed Systems

1. The problemCopy Anchor Link

Generate IDs that are globally unique across many servers, fast, with no central bottleneck.

On ONE server it's trivial: a database auto_increment column (the DB hands out 1, 2, 3, …; its transaction handling stops two simultaneous requests from getting the same number). At scale it breaks:

  server 1:  1, 2, 3, ...        two servers counting independently
  server 2:  1, 2, 3, ...   →    collide on the very first ID

And funnelling every write through one counting server = a bottleneck + a SPOF (single point of failure). That's the whole puzzle.

Where it's used: primary keys for tweets/orders/messages, URL-shortener IDs (chapter 8 imports this one), tracing IDs — any write-heavy distributed system.

2. Requirements (extract these from the interviewer)Copy Anchor Link

The book's clarified list:

Two terms to know cold:

• Why 64-bit numeric: fits a standard bigint column; small on the wire; keeps B-tree indexes fast (the tree structure databases use for primary keys — it stays cheap when new keys land at the end, i.e. keys increase).
• K-sortable: roughly ordered by creation time — newer IDs are usually bigger, occasional slight out-of-order is fine. "Roughly" matters: perfect global ordering needs coordination; rough ordering is free.

3. The four approaches (walk them in this order, reject with reasons)Copy Anchor Link

3.1 Multi-master replication — auto_increment by kCopy Anchor Link

Keep DB auto_increment, but each of the k servers increments by k, starting at a different offset → disjoint slices of the number line:

Rejected because:

• Not time-ordered across servers — a busy server races ahead on the number line while an idle one lags, so ID order ≠ creation order
• Adding/removing a server changes k → every server must be reconfigured — complex and error-prone
• OK only for small, static clusters

3.2 UUIDCopy Anchor Link

UUID (Universally Unique Identifier): a 128-bit identifier, standardized by RFC 4122, generated locally from randomness — format 550e8400-e29b-41d4-a716-446655440000. Collision odds are astronomically small (treated as impossible in practice).

Pros: dead simple; no network call; no coordination of any kind.

Rejected for THESE requirements:

• 128 bits (need 64), alphanumeric (need numeric)
• Not time-sortable → random keys thrash B-tree indexes (inserts land all over the tree instead of at the end)

Modern bonus point (post-book, say it): UUIDv7 is a standardized time-ordered UUID — the best choice when 128 bits is acceptable. ULID is similar (128-bit, sortable, compact Base32 string). Knowing when the 64-bit-numeric constraint actually matters vs "just use UUIDv7" is the judgment interviewers probe.

3.3 Ticket serverCopy Anchor Link

One central service (a DB with auto_increment) that everyone calls for the next number. Popularized by Flickr.

Pros: unique, numeric, roughly sequential; very simple.

Rejected because:

• The central server is a SPOF
• Making it redundant (multiple ticket servers) reintroduces the synchronization problems of 3.1
• Every single ID costs a network round trip → caps throughput, adds latency to every write in the company

3.4 Twitter Snowflake — the answerCopy Anchor Link

Divide and conquer: build uniqueness INTO the ID by packing three facts into 64 bits — WHEN it was made, WHERE it was made, WHICH one it was within that instant. Every node generates independently: no network call, no runtime coordination.

Why each field is shaped that way:

• Timestamp in the MOST significant (leftmost) bits → sorting IDs numerically sorts them by time. That's where k-sortability comes from, free.
• Custom epoch = the zero-point the clock counts from. Not Unix's 1970-01-01 but e.g. your launch date → your 41 bits (~69 years of ms) run out ~2090 instead of ~2039.
• DC + machine bits are assigned once at startup (config, a coordination service, or derived from the pod's IP). The ONLY coordination in the design — and it's at boot, not per ID. Two live machines must never share a pair.
• Sequence = tiebreaker for same-millisecond IDs on one machine, behind a local mutex:

  same ms again?        sequence++          (up to 4096 per ms)
  sequence exhausted?   spin-wait until the clock ticks to the next ms
  new ms?               sequence = 0

Uniqueness by construction: a collision needs same ms AND same DC AND same machine AND same sequence — the counter makes that impossible on a correctly configured machine.

Capacity math: 4,096 IDs/ms/machine ≈ 4M+/sec/machine × 1,024 machines. The 10k/sec requirement is nothing.

4. Wrap-up issues (where seniors score)Copy Anchor Link

4.1 Clock synchronizationCopy Anchor Link

The design assumes machines roughly agree on time. Reality:

• All nodes run NTP (Network Time Protocol — daemons that keep server clocks accurate to within a few ms of true time).
• Skew between machines (A's clock ≠ B's clock): harmless for uniqueness — each machine's IDs carry its own machine bits, so cross-machine collisions can't happen. Only effect: slight cross-machine ordering fuzz (hence k-sortable, not sortable).
• The dangerous case — one clock stepping BACKWARDS (e.g. an NTP correction): the machine could revisit a (timestamp, sequence) pair it already issued → duplicates. Defenses:
  1. remember the last timestamp issued; if now < last, refuse or wait — never reissue a past timestamp
  2. configure NTP to smear (slow the clock gradually) instead of stepping

4.2 Section-length (bit-budget) tuningCopy Anchor Link

41/5/5/12 is a default, not a law:

Saying "the split is a tunable budget" shows understanding, not memorization.

4.3 High availabilityCopy Anchor Link

Everything depends on the generator → it must be always-on. Good news: the design is naturally HA — every node is independent, run many, clients fail over to any other. Remaining operational risks are the coordinated parts:

• machine-ID assignment — two nodes sharing an ID = collisions
• clock health — see 4.1

Common deployment: a sidecar — the generator runs next to the application process, called over a zero-latency local interface, worker ID derived statelessly (e.g. from pod IP) to avoid a ZooKeeper dependency.

5. Interview scriptCopy Anchor Link

  1. clarify      unique? numeric? 64-bit? time-sortable? IDs/sec (10k)?
  2. single box   auto_increment — then break it: 2 servers → instant collision
  3. multi-master increment by k → not time-ordered, resizing reconfigures all
  4. UUID         local & simple → 128 bits, random order thrashes B-trees
                  (+ "UUIDv7 fixes ordering" — modern bonus)                ← unprompted
  5. ticket srv   central counter → SPOF + network hop per ID
  6. snowflake    time + place + count in 64 bits; DRAW the bit layout
  7. deep dive    custom epoch (~69 yrs), sequence spin-wait, boot-time machine ID
  8. wrap-up      NTP + clock-backwards defense, bit tuning, HA / sidecar   ← unprompted

6. The lines that earn the mostCopy Anchor Link

1. "The timestamp sits in the most significant bits, so numeric order IS time order — sortability costs nothing."
2. "The only coordination is machine-ID assignment at boot — generation itself is a local counter behind a mutex. No network, no bottleneck."
3. "Skew between machines can't cause duplicates — machine bits differ. A clock stepping backwards on one machine can — so I track the last timestamp issued and refuse to go back, and I smear NTP corrections."
4. "The 41/5/5/12 split is a tunable bit budget, not a constant."
5. "If 64-bit numeric weren't a requirement, UUIDv7 gets the same time-ordering as a ratified standard with zero infrastructure."

7. Numbers to rememberCopy Anchor Link

8. Common follow-upsCopy Anchor Link

9. When NOT to go deepCopy Anchor Link

In a product design interview ("design Twitter / URL shortener"), one sentence and move on:

"IDs come from a Snowflake-style generator — 64-bit, time-sortable, generated locally on each node, so there's no central bottleneck."

Go deep only when the question IS the generator (this chapter), or when the interviewer pushes on ID collisions / ordering in another design.

10. Glossary (A–Z, one line each)Copy Anchor Link