Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Distributed
Unique ID Generator.

Design a globally distributed unique ID generation service (similar to Twitter Snowflake). Generated IDs must be 64-bit integers, globally unique, roughly time-sortable, and generated at high scale without cross-node network coordination.
Start the journey5 stages
Loading diagram…
Design a Distributed Unique ID Generator architecture sketch diagram
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Design a globally distributed unique ID generation service (similar to Twitter Snowflake). Generated IDs must be 64-bit integers, globally unique, roughly time-sortable, and generated at high scale without cross-node network coordination.

From patterns to decisions.

Design a globally distributed unique ID generation service (similar to Twitter Snowflake). Generated IDs must be 64-bit integers, globally unique, roughly time-sortable, and generated at high scale without cross-node network coordination.

01
SYSTEM-DESIGN · STAGE 01L4 · FUNDAMENTALS

UUID v4 is 128-bit and.

UUID v4 is 128-bit and non-sequential, causing B-tree fragmentation, page splits, and cache misses in database indexes. Centralized DB auto-increment introduces a single write bottleneck and single point of failure.

ChoiceWhat it buysWhat it costs
UUID v4fully distributed, zero coordination, but 128-bit non-sequential degrades DB indexing.
Centralized DB counter (Ticket Server)simple and sequential, but single point of failure and latency bottleneck.
Snowflake 64-bit scheme64-bit, time-sortable, decentralized, but depends on system clock stability.
02
SYSTEM-DESIGN · STAGE 02L5 · APPLIED DESIGN

Twitter Snowflake 64-bit structure.

Twitter Snowflake 64-bit structure: 1 sign bit + 41 timestamp bits + 10 machine/datacenter bits + 12 sequence bits.

Step 1

1. 1 unused sign bit (always 0 to keep integer positive).

2. 41 timestamp bits

milliseconds since custom epoch. 2^41 ms ≈ 69.7 years of IDs.

3. 10 node ID bits

5 bits datacenter ID (32 datacenters) + 5 bits worker ID (32 workers per DC) = 1,024 generator nodes.

4. 12 sequence bits

supports up to 2^12 = 4,096 IDs per millisecond per node.

5. Algorithm

read current timestamp. If same millisecond as last ID, increment sequence. If sequence overflows 4095, busy-wait until next millisecond. If new millisecond, reset sequence to 0.

Alternative 1

Ticket Server with multi-master offsets: Node A generates odd IDs, Node B generates even IDs. Simple, but does not scale dynamically and doesn't time-sort cleanly.

Alternative 2

ULID (Universally Unique Lexicographically Sortable Identifier): 128-bit time-sortable alternative, useful when 64-bit constraint is relaxed.

// Twitter Snowflake 64-bit ID Generator
// 1 bit unused | 41 bits timestamp (millis) | 10 bits machine/node ID | 12 bits sequence counter
export class SnowflakeIdGenerator {
  private static readonly EPOCH = 1609459200000n; // Custom Epoch: 2021-01-01
  private static readonly NODE_ID_BITS = 10n;
  private static readonly SEQUENCE_BITS = 12n;
  private static readonly MAX_SEQUENCE = (1n << 12n) - 1n;

  private sequence = 0n;
  private lastTimestamp = -1n;

  constructor(private readonly nodeId: bigint) {
    if (nodeId < 0n || nodeId > 1023n) throw new Error("Node ID must be between 0 and 1023");
  }

  public nextId(): bigint {
    let timestamp = BigInt(Date.now());
    if (timestamp < this.lastTimestamp) {
      throw new Error("Clock moved backwards! Rejecting generation.");
    }

    if (timestamp === this.lastTimestamp) {
      this.sequence = (this.sequence + 1n) & SnowflakeIdGenerator.MAX_SEQUENCE;
      if (this.sequence === 0n) {
        // Spin until next millisecond
        while (timestamp <= this.lastTimestamp) {
          timestamp = BigInt(Date.now());
        }
      }
    } else {
      this.sequence = 0n;
    }

    this.lastTimestamp = timestamp;
    return (
      ((timestamp - SnowflakeIdGenerator.EPOCH) << 22n) |
      (this.nodeId << 12n) |
      this.sequence
    );
  }
}
03
SYSTEM-DESIGN · STAGE 03L6 · SCALE & TRADE-OFFS

Trade-Off Analysis.

Key architectural decisions and failure handling for Design a Distributed Unique ID Generator.

ChoiceWhat it buysWhat it costs
Custom epochStarting timestamp at application launch year (e.g., 2026) gives 69 years of runtime from now. Unix epoch would overflow 41 bits in 2039.
Static worker ID assignment vs ZooKeeper/etcdStatic config is simple but prone to human config error (duplicate worker IDs). Zookeeper/etcd ephemeral nodes assign unique worker IDs automatically on startup.

What to Focus On

  • Primary Objective: Architect a globally unique, 64-bit monotonically roughly increasing ID generation engine capable of serving 100,000+ IDs/second per instance with sub-millisecond response times, zero cross-datacenter locking, and strict ordering guarantees for distributed storage engines.
  • Key Decision Levers:
    1. ID Bit-Allocation Scheme: 64-bit Twitter Snowflake vs 128-bit UUID (v4 / v7) vs Centralized Ticket Server vs Database Auto-Increment.
    2. Clock Drift & Rollback Handling: NTP Backward Drift Protection (Refuse & Halt vs Spin Wait vs Reserve Next Millisecond Sequence).
    3. Worker Node Coordination: Static Configuration vs Consensus Lease (ZooKeeper / Consul / etcd) vs K8s StatefulSet Ordinals.
    4. High-Concurrency Sequence Exhaustion: Sequence bit overflow within a single millisecond (wait for next millisecond vs expand sequence pool).
  • What You Should Be Able to Explain:
    • Why standard random UUIDv4 causes devastating B-Tree index fragmentation and cache page eviction in relational and document databases.
    • How Twitter Snowflake packs timestamp, datacenter/worker ID, and sequence into a single 64-bit signed integer.
    • How to handle NTP time jumps when the server clock jumps backward by 5 milliseconds.
    • Why a centralized MySQL auto-increment ticket server (Flickr pattern) creates a single point of failure and cross-region latency bottleneck.

Structured Trade-Off Matrix

Strategy Optimizes For Storage / Footprint Throughput Capacity Downside / Trade-off When to Choose
Twitter Snowflake (Recommended) 64-bit integer, B-Tree locality, high throughput 64 bits (8 bytes) 4,096,000 IDs/sec/worker Requires unique worker ID coordination & clock drift handling High-throughput distributed databases, primary keys
UUIDv7 (Time-Ordered) No worker coordination, client-side generation 128 bits (16 bytes) Unlimited distributed 2x storage footprint vs 64-bit int; larger index sizes Ephemeral serverless containers, microservices
UUIDv4 (Completely Random) Pure randomness, zero coordination 128 bits (16 bytes) Unlimited distributed Total lack of ordering; severe B-tree page splits Non-indexed correlation IDs, idempotency tokens
Flickr Ticket Server (DB Auto-inc) Simple implementation, strictly consecutive IDs 64 bits (8 bytes) Limited by DB write IOPS (~5k-10k/sec) Centralized DB bottleneck; cross-region roundtrip latency Low-throughput legacy monolithic stacks

Explicit Decision Rationale: Why Snowflake is the Production Standard

  1. 64-Bit Compatibility: Fits natively inside an int64 / BIGINT column. Highly compact, fits in CPU registers, and cuts secondary index memory footprint in half compared to 128-bit UUIDs.
  2. K-Sortable Chronological Locality: Because the high 41 bits represent the millisecond timestamp, IDs naturally sort chronologically. New inserts append cleanly to the right-most leaf page of a B+Tree, eliminating random page splits.
  3. Zero Network Hop during Generation: Generation occurs completely in-memory on the local worker node using atomic bitwise shifting (timestamp << 22 | workerId << 12 | sequence), yielding sub-microsecond latencies.

Architectural Decisions & Scaling Concerns

  • Clock Rollback (NTP Drift): If currentTimestamp < lastTimestamp:
    • If drift is <5 ms< 5\text{ ms}, spin-wait (Thread.sleep(drift)) until clock catches up.
    • If drift is ≥5 ms\ge 5\text{ ms}, reject ID generation, fire high-priority alert, or switch to backup worker ID reserved for clock skew emergencies.
  • Sequence Saturation: If more than 4,096 requests hit a single node within the exact same millisecond, sequence overflows. The node loops in a busy-wait until System.currentTimeMillis() ticks to the next millisecond, resetting sequence to 0.

Hidden Assumptions & Common Traps

  • Hidden Assumption 1 — Custom Epoch: Never use the default UNIX epoch (1970). A 41-bit timestamp from 1970 runs out in 2039. A custom epoch starting today lasts until 2095.
  • Hidden Assumption 2 — Signed Integer Representation: Java and some languages do not support unsigned 64-bit integers. If the most significant bit (MSB) is 1, the number is interpreted as negative. Always reserve bit 63 as 0.
  • Common Trap — Reusing Worker IDs Across Pod Restarts: If two pods share worker ID 7 at the same millisecond, ID collisions occur. Always use etcd leases or K8s StatefulSet ordinals.

Example Bitmask Calculation & API Output

{
  "id": "178239014589235200",
  "binary": "000000100111100100010111000101110001011100_00010_00101_000000000001",
  "decoded": {
    "timestampMs": 1740816000123,
    "dateTimeIso": "2026-03-01T08:00:00.123Z",
    "datacenterId": 2,
    "workerId": 5,
    "sequence": 1
  }
}
04
SYSTEM-DESIGN · STAGE 04L6 · SCALE & TRADE-OFFS

Failure Modes & Recovery.

Key architectural decisions and failure handling for Design a Distributed Unique ID Generator.

Clock skew / rollback

If system clock jumps backward, the generator will produce duplicate timestamps and therefore duplicate IDs!

Defense 1 (Wait)

If clock rollback is small (< 5 ms), spin-wait until the clock catches up to lastTimestamp.

Defense 2 (Reject)

If clock rollback is significant, reject requests and raise an alert; refuse to generate IDs until operator verifies or clock catches up.

Defense 3 (Clock-sequence bits)

Reserve 2 bits for clock sequence counter; increment clock sequence when rollback is detected to maintain uniqueness.

05
SYSTEM-DESIGN · STAGE 05L7 · STAFF / PRINCIPAL

Sequence saturation handling.

Sequence saturation handling.

ChoiceWhat it buysWhat it costs
Blocking on sequence overflowintroduces microsecond latency jitter on burst, but guarantees strict uniqueness without allocating extra bits.

Step 1

1. When sequence reaches 4,095, block and yield CPU until timestamp advances to the next millisecond.

2. Horizontal scale

add more generator worker nodes to distribute the load across more 10-bit machine namespaces.

Theory & Tips and Tricks

Practical heuristics & interview traps

  • 01Interview anchor: Allocate 64 bits with 41 timestamp bits from a custom epoch (69 years), 10 worker bits (1,024 nodes via ZooKeeper/etcd leases), and 12 sequence bits (4,096 IDs/ms). Protect against NTP clock drift by spin-waiting if under 5 ms and rejecting if clock moves backward.
  • 02Trade-off tip: Custom epoch: Starting timestamp at application launch year (e.g., 2026) gives 69 years of runtime from now. Unix epoch would overflow 41 bits in 2039.
  • 03Trade-off tip: Static worker ID assignment vs ZooKeeper/etcd: Static config is simple but prone to human config error (duplicate worker IDs). Zookeeper/etcd ephemeral nodes assign unique worker IDs automatically on startup.
  • 04Watch out for: Clock skew / rollback: If system clock jumps backward, the generator will produce duplicate timestamps and therefore duplicate IDs!
  • 05Watch out for: Defense 1 (Wait): If clock rollback is small (< 5 ms), spin-wait until the clock catches up to lastTimestamp.
Behavioral Progression · Design Unique Id Generator

Design Unique Id Generator — Normal → Load / Fault → Recovery

Send Request
1. Normal Request Ingress
Traffic: 1x baseline · Latency (p99): 4 ms
Process State
2. Core Execution & State Lookup
Traffic: 1x baseline · Latency (p99): 9 ms
Inject 10x Spike
3. Scale Spike / Failure Injection
Traffic: 10x burst · Latency (p99): 185 ms

Allocate 64 bits with 41 timestamp bits from a custom epoch (69 years), 10 worker bits (1,024 nodes via ZooKeeper/etcd leases), and 12 sequence bits (4,096 IDs/ms). Protect against NTP clock drift by spin-waiting if under 5 ms and rejecting if clock moves backward.

Synthesis / One connected design

Putting Design a Distributed Unique ID Generator Together

Allocate 64 bits with 41 timestamp bits from a custom epoch (69 years), 10 worker bits (1,024 nodes via ZooKeeper/etcd leases), and 12 sequence bits (4,096 IDs/ms). Protect against NTP clock drift by spin-waiting if under 5 ms and rejecting if clock moves backward.

A candidate architecture, not a universal answer

Putting Design a Distributed Unique ID Generator Together

Step 1
Step 2
Step 3
Step 4
  1. 1. 1 unused sign bit (always 0 to keep integer positive).
  2. 2. 41 timestamp bits: milliseconds since custom epoch. 2^41 ms ≈ 69.7 years of IDs.
  3. 3. 10 node ID bits: 5 bits datacenter ID (32 datacenters) + 5 bits worker ID (32 workers per DC) = 1,024 generator nodes.
  4. 4. 12 sequence bits: supports up to 2^12 = 4,096 IDs per millisecond per node.
Resilient end-to-end architecture ready for production spikes.
Interview Readiness Check

Resilient end-to-end architecture ready for production spikes.

Walk through bottlenecks, back-of-the-envelope math, and failure recovery.

Practice / Explain the consequences

Make the trade-off yourself.

Practice Check

Test your understanding

Question 1 of 3

Why is selecting a low-cardinality column like 'country_code' as a primary database shard key considered a dangerous architectural pitfall?

Key takeaway

Design a Distributed Unique ID Generator

Allocate 64 bits with 41 timestamp bits from a custom epoch (69 years), 10 worker bits (1,024 nodes via ZooKeeper/etcd leases), and 12 sequence bits (4,096 IDs/ms). Protect against NTP clock drift by spin-waiting if under 5 ms and rejecting if clock moves backward.