Design a Unique Distributed ID Generator (Snowflake-Style)

A Distributed ID Generator generates unique, monotonically increasing identifiers across hundreds of distributed database shards and microservices without central lock contention.

Functional Requirements

1. Global Uniqueness: Every generated ID must be globally unique across all servers and datacenters.
2. Time-Ordered (Roughly Monotonic): IDs generated at time T_2 > T_1 must have numerical values ID_2 > ID_1, allowing sorting directly by ID.
3. Compact Size: Fits in a standard 64-bit integer (BIGINT in SQL / int64 in Go/Java) to conserve index RAM and storage.

Non-Functional Requirements

• Massive Throughput: Must generate > 100,000 IDs/sec per individual worker node in local CPU memory with zero network roundtrips.
• Zero Central Coordination: Generation must not depend on a central database lock or coordinator for each individual ID.
• High Availability: If network partitions occur between datacenters, local nodes continue generating valid unique IDs without interruption.

A common junior developer mistake is using 128-bit random UUIDv4 (f47ac10b-58cc-4372-a567-0e02b2c3d479) for database primary keys.

The Physics of B+ Tree Index Degradation:

1. Random Insertion Page Splits: Relational databases (PostgreSQL, MySQL InnoDB) store rows physically ordered by primary key in a clustered B+ Tree. Because UUIDv4 is completely random, new records insert randomly throughout the tree, causing frequent B+ Tree page splits, excessive write amplification, and random disk I/O.
2. Memory Bloat: 128-bit UUID strings (36 characters) consume more than double the RAM and disk of a 64-bit integer. Index caches fill up rapidly, dropping buffer pool hit ratios.
3. Snowflake Solution: Because Snowflake IDs are roughly monotonically increasing based on timestamp, new database rows append sequentially to the rightmost leaf of the B+ Tree, completely eliminating page splits and achieving maximum write IOPS.

Twitter Snowflake divides a 64-bit signed integer into 4 distinct binary bit fields:

code
Copy
+---+-------------------------------------------+--------------+--------------+
| 1 | 41 Bits: Timestamp (Milliseconds)         | 10 Bits: Node| 12 Bits: Seq |
+---+-------------------------------------------+--------------+--------------+
  |                        |                            |              |
Unused (0)          Epoch Offset (ms)               Worker ID       Sequence
(Sign Bit)       (Supports ~69.7 Years)          (0 - 1023)    (0 - 4095/ms)

Bit Breakdown & Math:

• 1 Bit (Sign Bit): Always 0 to ensure the generated 64-bit number is a positive integer in Java, Go, and SQL BIGINT.
• 41 Bits (Timestamp): Milliseconds elapsed since a custom epoch (e.g., 2026-01-01T00:00:00Z = 1767225600000 ms):

2^{41} = 2,199,023,255,552 ms ≈ 69.73 Years of Lifetime

• 10 Bits (Machine / Worker ID): Uniquely identifies up to 2^{10} = 1,024 worker nodes (often divided into 5-bit Datacenter ID = 32 datacenters, and 5-bit Worker ID = 32 nodes per DC).
• 12 Bits (Sequence Counter): Increments for each ID generated within the same millisecond on the same node:

2^{12} = 4,096 unique IDs per millisecond per node

Maximum Cluster Throughput:

Throughput = 1,024 nodes × 4,096 IDs/ms × 1,000 ms/sec = 4.19 Billion IDs/second!

Here is a production-grade implementation of a Snowflake generator using 64-bit BigInt:

typescript
Copy
export class SnowflakeIdGenerator {
  private readonly epoch: bigint = 1767225600000n; // Custom Epoch (Jan 1, 2026)
  private readonly workerIdBits: bigint = 10n;
  private readonly sequenceBits: bigint = 12n;

  private readonly maxWorkerId: bigint = (1n << this.workerIdBits) - 1n; // 1023
  private readonly maxSequence: bigint = (1n << this.sequenceBits) - 1n; // 4095

  private readonly timestampShift: bigint = this.workerIdBits + this.sequenceBits; // 22
  private readonly workerIdShift: bigint = this.sequenceBits; // 12

  private workerId: bigint;
  private sequence: bigint = 0n;
  private lastTimestamp: bigint = -1n;

  constructor(workerId: number) {
    if (workerId < 0 || BigInt(workerId) > this.maxWorkerId) {
      throw new Error(`Worker ID must be between 0 and ${this.maxWorkerId}`);
    }
    this.workerId = BigInt(workerId);
  }

  public nextId(): bigint {
    let now = BigInt(Date.now());

    if (now < this.lastTimestamp) {
      const offset = this.lastTimestamp - now;
      if (offset <= 5n) {
        // Clock drift small: wait until clock catches up
        while (now < this.lastTimestamp) {
          now = BigInt(Date.now());
        }
      } else {
        throw new Error(`NTP Clock moved backwards by ${offset}ms! Refusing to generate ID.`);
      }
    }

    if (now === this.lastTimestamp) {
      this.sequence = (this.sequence + 1n) & this.maxSequence;
      if (this.sequence === 0n) {
        // Sequence exhausted for current ms; wait for next ms
        while (now <= this.lastTimestamp) {
          now = BigInt(Date.now());
        }
      }
    } else {
      this.sequence = 0n;
    }

    this.lastTimestamp = now;

    return (
      ((now - this.epoch) << this.timestampShift) |
      (this.workerId << this.workerIdShift) |
      this.sequence
    );
  }
}

1. Handling NTP Clock Drift & Backward Jumps

Server clocks periodically synchronize via Network Time Protocol (NTP). If an NTP synchronization steps the local clock backwards (T_{now} < T_{last}), naive generators could generate duplicate IDs.

• Mitigation Strategies:
  • Slight Drift (< 5 ms): Pause execution in a tight spin-lock loop until the clock catches up to lastTimestamp.
  • Large Drift (> 5 ms): Refuse generation and trigger an automated alert, or switch to a reserved secondary worker_id offset.
  • Monotonic Clocks: Use monotonic OS clock APIs (CLOCK_MONOTONIC_RAW) that never step backwards.

2. Machine Worker ID Assignment

How do worker nodes get assigned their 10-bit ID (0-1023)?

• Dynamic ZooKeeper / Consul Registration: On boot, the container creates an ephemeral sequential znode in ZooKeeper (e.g., /workers/id_042) to claim worker ID 42. When the container dies, the lease expires and is reclaimed.

3. Alternative: UUIDv7 (The Modern RFC 9562 Standard)

• Combines 48-bit millisecond timestamp + 74-bit random entropy.
• Time-ordered like Snowflake, but 128-bit long. Snowflake remains the preferred choice when 64-bit integer performance is critical.