Design a Distributed Unique ID Generator

Prompt

Generate unique IDs across many servers: never a duplicate, thousands per second per node, ideally roughly time-sortable, no single point of failure, and small enough (~64 bits) to fit a BIGINT primary key.

Requirements

Unique across all nodes forever; high throughput (thousands–millions/s); low latency (ideally generated locally, no network hop); roughly time-sortable (helps index locality and cursor pagination); compact (64-bit); highly available (the ID service can't be the thing that takes the site down).

The candidates

Snowflake — the bit layout

Pack three things into 64 bits so the ID is unique and time-ordered:

 0 | 41 bits: ms since custom epoch | 10 bits: machine id | 12 bits: sequence
sign        ~69 years                  1024 nodes            4096 ids / ms / node

• The timestamp is the high bits, so numeric order ≈ time order (k-sortable).
• 12-bit sequence ⇒ 4,096 IDs per millisecond per node = ~4M/s/node; across 1,024 nodes that's billions/s with no coordination on the hot path.

class Snowflake {
  private seq = 0;
  private lastMs = -1;
  constructor(private machineId: number, private epoch = 1700000000000) {}

  next(): bigint {
    let now = Date.now();
    if (now < this.lastMs) throw new Error("Clock moved backwards — refuse to issue");
    if (now === this.lastMs) {
      this.seq = (this.seq + 1) & 0xfff;            // 12-bit sequence
      if (this.seq === 0) now = this.waitNextMs(this.lastMs); // overflow → next ms
    } else {
      this.seq = 0;
    }
    this.lastMs = now;
    return (BigInt(now - this.epoch) << 22n)
         | (BigInt(this.machineId) << 12n)
         | BigInt(this.seq);
  }
  private waitNextMs(prev: number) { let t = Date.now(); while (t <= prev) t = Date.now(); return t; }
}

The genuinely hard part — clocks

The high bits are a wall-clock timestamp, so time going backwards breaks uniqueness:

• Clock skew / NTP corrections: machines drift and NTP can step the clock back. If now < lastMs, you must not reissue IDs. Options: refuse (fail fast), wait until the clock catches up, or keep a logical clock that only moves forward. Naming this trade-off is the SDE-3 signal.
• Machine-id assignment: each node needs a unique 10-bit id. Lease it from ZooKeeper/etcd, derive it from a Kubernetes StatefulSet ordinal, or hand it out at deploy time — and reclaim it when a node dies so autoscaling doesn't collide.
• Sequence overflow: more than 4,096 IDs in one millisecond ⇒ spin until the next ms.

Variants & trade-offs

• k-sortable, not strictly monotonic: two nodes in the same ms produce IDs that sort by machine id, not true issue order. Usually fine; say so if strict ordering matters.
• ULID / KSUID (128-bit, lexicographically sortable strings) when you want a sortable string id instead of a 64-bit int.
• Instagram's scheme: DB sharding with a per-shard sequence baked into a stored procedure — IDs encode the shard, which helps routing.

Design drills