Design a Unique ID Generator.

Every system needs IDs, and the first instinct is the database's auto-increment column. It works until you have more than one database, or more than one data centre, or a million writes a second. "Design a unique ID generator" asks what you do then. The answer most interviewers expect fits in a single 64-bit integer, and the interesting part is not the layout but the two things it depends on: a clock you can trust and a worker number nobody else is using.

Functional requirements#

Non-functional requirements#

Two ways to expose it, and the embedded library is the default.

# 1 · embedded library: no network hop
ids = SnowflakeGenerator(worker_id=lease.worker_id)
order_id = ids.next()                  # 64-bit int, e.g. 240044212224069649

# 2 · a small ID service, for languages or jobs that can't embed the library
POST /v1/ids?count=100
→ 200 { "ids": ["240044212224069649", "240044212224069650", ...] }

IDs go over JSON as strings. JavaScript numbers are exact only up to 2^53 − 1, and a Snowflake ID passes that within weeks of its epoch, so a browser parsing it as a number would silently round it.

%% title: Snowflake-style IDs, generated inside each service
flowchart TD
  OS["Order service instance<br/>ID library · worker 17"]:::core
  CS["Chat service instance<br/>ID library · worker 18"]:::core
  E@{ icon: "tech:etcd", label: "etcd<br/>worker-ID leases" }
  T@{ icon: "sd:clock", label: "NTP time sources" }
  DB@{ icon: "sd:database", label: "Databases<br/>B-tree index on id" }
  API@{ icon: "sd:api", label: "ID service<br/>(batch endpoint)" }
  B@{ icon: "sd:browser", label: "Web clients<br/>IDs as strings" }
  OS -->|"lease worker 17, renew every 10 s"| E
  CS --> E
  API --> E
  T -.->|"clock sync"| OS
  T -.-> CS
  OS -->|"insert id"| DB
  CS --> DB
  OS -->|"JSON: id as string"| B
  class E,DB store
  class T,API service
  class B client

• The library in every service instance builds IDs from its clock, its worker ID and a per-millisecond counter. No network call per ID.
• etcd (or ZooKeeper) hands out worker IDs as leases. An instance must hold a live lease to generate; that is what keeps two instances from using the same worker number.
• NTP keeps clocks close so IDs from different instances are ordered to within a few milliseconds.
• The ID service is the same library behind an endpoint, for callers that can't embed it. Callers fetch IDs in batches so the extra hop is rare.

Deep dive 1: Building an ID, and the 4,097th request in a millisecond#

import time

EPOCH_MS = 1735689600000          # custom epoch: 2025-01-01T00:00:00Z
WORKER_BITS, SEQ_BITS = 10, 12
MAX_SEQ = (1 << SEQ_BITS) - 1     # 4,095

class SnowflakeGenerator:
    def __init__(self, worker_id: int):
        assert 0 <= worker_id < (1 << WORKER_BITS)
        self.worker_id, self.last_ms, self.seq = worker_id, -1, 0

    def next(self) -> int:
        now = int(time.time() * 1000)
        if now < self.last_ms:                       # clock went backwards: deep dive 2
            now = self._wait_until(self.last_ms)
        if now == self.last_ms:
            self.seq = (self.seq + 1) & MAX_SEQ
            if self.seq == 0:                        # 4,096 used this ms: wait for the next ms
                now = self._wait_until(self.last_ms + 1)
        else:
            self.seq = 0
        self.last_ms = now
        return ((now - EPOCH_MS) << (WORKER_BITS + SEQ_BITS)) | (self.worker_id << SEQ_BITS) | self.seq

    def _wait_until(self, target_ms: int) -> int:
        while (now := int(time.time() * 1000)) < target_ms:
            time.sleep(0.0001)
        return now

• Timestamp first makes IDs sort by time, so new rows append at the end of the index.
• The sequence separates IDs generated in the same millisecond by the same worker. The 4,097th request in a millisecond waits for the next millisecond (at most 1 ms), so it is a throughput ceiling of ~4.1M a second per generator, never a duplicate.
• A custom epoch (2025-01-01 here, not 1970) spends the 69 years from when the system starts. (The code is a sketch: a real generator also guards next() with a lock if threads share it.)
• Order across workers is only as good as clock sync: two IDs made 1 ms apart on different hosts can come out in either order. That is "roughly time-ordered", which is what the interviewer agreed to.

Deep dive 2: The two ways to get a duplicate#

• Leases, fencing tokens and the zombie that wakes up: Week 5 · Day 5: Leader Election and Coordination
• Why time-ordered keys create hot partitions: Week 1 · Day 1: Partitioning Deep-Dive and Week 1 · Day 4: Hot Keys and Skew
• Clock skew and ordering events by time: Week 3 · Day 5: Audit Log System
• IDs as idempotency keys: Week 2 · Day 2: Idempotency in Practice
• Range allocation in practice (short codes from leased blocks): Week 1 Capstone: URL Shortener at Scale
• Powers of two and capacity math: Week 0 · Part 3: Back-of-the-Envelope Estimation