Distributed Unique ID Generator (Snowflake)#

Problem statement (interviewer prompt)

Design a distributed ID generator that produces globally unique, roughly time-sortable 64-bit IDs at 10k+ IDs/sec/node across hundreds of nodes - without a central coordinator on the hot path and without duplicates after process restarts.

flowchart LR
  C([Client / Service])
  S[ID Server]
  T[Wall clock ms]
  M[Machine ID]
  N[Sequence per ms]
  C --> S
  T --> S
  M --> S
  N --> S
  S -->|64-bit ID| C

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C client;
    class S,T,M,N service;

ID = [1 sign | 41 ms timestamp | 10 machine | 12 sequence] = 64 bits, sortable, decentralized.

flowchart TB
  subgraph Clients[ID Consumers]
    APP[App services]
    DB[Database row keys]
    LOG[Trace IDs]
  end

  subgraph Layout[64-bit Snowflake Layout]
    BIT1[bit 63: sign 0]
    BIT2[bits 62-22<br/>41-bit timestamp ms<br/>since custom epoch ~69 yr]
    BIT3([bits 21-12<br/>10-bit worker / dc id<br/>1024 nodes])
    BIT4[bits 11-0<br/>12-bit sequence per ms<br/>4096 IDs/ms/node]
  end

  subgraph Server[ID Generator Node]
    CLK[Monotonic clock]
    SEQ[Atomic seq counter]
    WID([Worker ID<br/>assigned at boot])
    REG[(Coordination<br/>ZooKeeper / etcd)]
  end

  subgraph Failures
    CB[Clock skew /<br/>backwards jump]
    EX[Seq exhaustion within 1 ms]
    REASSIGN([Node restart -<br/>reassign worker ID])
  end

  subgraph Variants
    UU[UUIDv4<br/>random, 128-bit, not sortable]
    UU7[UUIDv7 / ULID<br/>time-sortable]
    TSID[KSUID, TSID]
    SF[Snowflake clones<br/>Sonyflake, Discord]
    DB1[DB autoinc / sequence]
    SEG[Range allocator<br/>Twitter ID2 / Leaf]
  end

  APP --> Server
  DB --> Server
  LOG --> Server
  Server --> Layout
  REG --> WID
  CLK --> Server
  SEQ --> Server
  CB -.->|wait or NTP-fence| Server
  EX -.->|busy-wait next ms| Server
  REASSIGN --> REG
  Server --> Variants

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class APP,BIT1,BIT2,BIT4,CLK,SEQ,CB,EX,TSID,SEG service;
    class DB,REG,UU,UU7,SF,DB1 datastore;
    class BIT3,WID,REASSIGN compute;
    class LOG obs;

Properties of a good ID#

Uniqueness across cluster.
Roughly time-sortable (helps B-tree locality, log ordering).
64-bit fits Long; 128-bit safer for huge scale.
No central bottleneck.

Snowflake details#

Custom epoch (e.g., 2010-11-04) extends 41-bit ms range to ~69 years.
Per-node sequence rolls per ms; if >4096 IDs needed in one ms, wait for next ms.
Worker ID must be globally unique → ZooKeeper sequential node or Kubernetes pod index.
Clock-backwards: refuse to issue, wait until clock catches up, alert.

Alternatives#

Scheme	Sortable	Coordination	Length	Note
Snowflake	yes	once on boot	64	Twitter, Discord
UUIDv4	no	none	128	Random
UUIDv7 / ULID	yes	none	128	Modern default
KSUID	yes	none	160	Segment
DB sequence	yes	central	64	bottleneck
Range allocator	yes	periodic	64	Leaf-segment (Meituan)

Failure scenarios#

Clock drift / NTP step → buffer & wait.
Two nodes share worker ID → duplicates. Mitigate via ZK ephemeral node + heartbeat.
After power loss, persist last seq + ts to avoid reissue.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	LSM vs B-Tree engines	WAL, memtable, SSTables, compaction	storage-engines-lsm-btree
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Requirements#

Globally unique 64-bit IDs.
Roughly time-sortable.
10k+ IDs/s per node, 1M+ aggregate cluster.
No single point of failure.

Snowflake math#

4096 IDs/ms × 1000 ms × 1024 workers = 4.2 billion IDs/sec theoretical.
41-bit ms gives 2^41 / (365864001000) ≈ 69.7 years from custom epoch.

API#

GET /v1/id              -> 64-bit integer
POST /v1/ids?count=100  -> batch

Operational concerns#

Worker ID assignment: ZooKeeper sequential ephemeral nodes; release on shutdown.
Clock: chrony with hard sync; disable step (use slew).
Monitoring: emitted IDs/ms, sequence saturation, clock-skew events.

Trade-offs#

Snowflake: short, ordered, needs coord for worker ID.
UUIDv4: zero coord, 128-bit storage cost, hurts index locality (random inserts in B-trees).
UUIDv7 / ULID: best of both for modern systems.
DB sequence: simplest, but central; OK up to ~10k inserts/s.
Range allocator (Leaf-segment): claim block of 1k IDs at a time → 1k× fewer ZK trips.

Refs#

Twitter Snowflake (2010 blog), Discord "How Discord Stores Billions of Messages", Meituan Leaf paper, Instagram Engineering "Sharding & IDs", RFC 9562 (UUIDv7).

FAQ#

UUID vs Snowflake: which should I use?#

UUIDs are simple but 128 bits and not time-sortable. Snowflake gives 64-bit roughly time-ordered IDs ideal for primary keys and pagination, at the cost of clock dependency.

How does Twitter Snowflake work?#

A 64-bit ID packs a 41-bit millisecond timestamp, a 10-bit machine ID, and a 12-bit per-millisecond sequence, giving 4096 IDs per node per ms without coordination.

How do you handle clock skew in a Snowflake generator?#

Refuse to issue IDs if the wall clock moves backward, wait for the clock to catch up, or fall back to a logical counter until the clock recovers.

Why are time-sortable IDs useful?#

They cluster recent writes on disk for cache locality, give cheap chronological pagination without a separate sort key, and avoid index hot spots from purely random keys.

What is the difference between ULID, KSUID, and Snowflake?#

All three encode a timestamp prefix plus random bits. ULID is 128-bit base32, KSUID is 160-bit, Snowflake is 64-bit. Pick by ID width budget and sortability needs.

Distributed Transactions: coordinating ID generation across nodes requires understanding distributed consistency
Consistent Hashing: hash-based partitioning determines which node generates IDs in a Snowflake cluster
Database Sharding: shard IDs are often embedded in generated unique IDs to route requests correctly