#Design a Unique ID Generator (Twitter Snowflake Scale)

#1. Problem Statement & Clarifications

A distributed unique ID generator produces globally unique, roughly time-ordered 64-bit IDs without requiring coordination between nodes. This is a foundational building block — every distributed system needs unique identifiers for database records, events, messages, and transactions. The challenge is generating IDs that are unique, sortable, compact, and fast at massive scale.

#Functional Requirements

Generate unique IDs — Globally unique across all datacenters and servers, no collisions ever
Time-sortable — IDs are roughly ordered by generation time (newer ID > older ID)
64-bit integer — Fits in a standard BIGINT; no strings/UUIDs
High throughput — Generate 10K+ IDs/sec per node, 1M+ IDs/sec globally
No coordination — Each node generates IDs independently (no distributed locks)

#Non-Functional Requirements

Requirement	Target
Latency	< 1ms per ID generation (local operation)
Throughput	10K IDs/sec per node; 1M+ globally
Uniqueness	Zero collisions across all nodes forever
Sortability	IDs generated later are numerically larger (within ~1ms precision)
Availability	99.999% — ID generation must never block
Size	64-bit integer (fits in DB BIGINT, language `long`)

#Out of Scope

Human-readable IDs (slugs, usernames)
Cryptographically secure random IDs
Sequential / gap-free IDs (auto-increment replacement)
UUID generation (128-bit; too large)

#Assumptions

System has up to 32 datacenters and 1024 machines total
Clock accuracy within ~10ms (NTP synchronized)
IDs don't need to be sequential, just roughly time-ordered
Average ID generation rate: 100K/sec globally, bursts to 1M/sec

#2. Back-of-Envelope Estimation

#Traffic Estimates

Average ID generation:  100K IDs/sec globally
Peak (10x burst):       1M IDs/sec
Nodes:                  1024 machines across 32 datacenters
Per-node avg:           ~100 IDs/sec (uneven; some nodes much higher)
Per-node peak:          10K IDs/sec (burst on hot services)

#Storage Estimates

ID size:                8 bytes (64-bit integer)
IDs/day:                100K × 86400 = 8.64B IDs/day
Storage for IDs alone:  8.64B × 8B = 69GB/day (trivial; IDs are stored
                        alongside records, not in a separate ID store)

#Bit Budget (64-bit layout)

Total bits:             64
Sign bit:               1 (always 0, keeps IDs positive)
Timestamp:              41 bits → 2^41ms = 69.7 years from epoch
Datacenter ID:          5 bits → 2^5 = 32 datacenters
Machine ID:             5 bits → 2^5 = 32 machines per datacenter
Sequence:               12 bits → 2^12 = 4096 IDs per millisecond per machine
                                 = 4.096M IDs/sec per machine (headroom)

#Capacity Analysis

Max IDs/ms/machine:     4,096 (12-bit sequence)
Max IDs/sec/machine:    4,096,000
Max IDs/sec/cluster:    4,096,000 × 1,024 machines = 4.19B IDs/sec
Lifetime:               69.7 years from custom epoch
                        (custom epoch = Jan 1, 2025 → expires ~2094)

#3. API Design

#Generate Single ID

GET /api/v1/id/generate

Response 200:
{
  "id": 7109812942348288001,
  "id_hex": "62B5D2E400001001",
  "timestamp": 1716984000123,
  "datacenter_id": 5,
  "machine_id": 12,
  "sequence": 1
}

#Generate Batch IDs

POST /api/v1/id/generate/batch
{
  "count": 100
}

Response 200:
{
  "ids": [7109812942348288001, 7109812942348288002, ...],
  "count": 100,
  "generated_at": "2025-05-29T12:00:00.123Z"
}

#Parse ID (Debug/Introspection)

GET /api/v1/id/parse/7109812942348288001

Response 200:
{
  "id": 7109812942348288001,
  "timestamp_ms": 1716984000123,
  "timestamp_iso": "2025-05-29T12:00:00.123Z",
  "datacenter_id": 5,
  "machine_id": 12,
  "sequence": 1
}

#Health / Status

GET /api/v1/id/status

Response 200:
{
  "datacenter_id": 5,
  "machine_id": 12,
  "ids_generated_total": 1234567890,
  "ids_generated_last_sec": 342,
  "clock_status": "synchronized",
  "uptime_seconds": 864000
}

#4. Data Model

#ID Bit Layout (Snowflake Structure)

┌─────┬──────────────────────────────────────┬─────┬─────┬────────────┐
│Sign │           Timestamp (ms)             │ DC  │Mach │  Sequence  │
│ 1b  │              41 bits                 │ 5b  │ 5b  │   12 bits  │
└─────┴──────────────────────────────────────┴─────┴─────┴────────────┘
  0      [custom epoch offset in ms]          [0-31][0-31]  [0-4095]

Example ID: 7109812942348288001
Binary: 0 | 11000101011010111010010111001000000000001 | 00101 | 01100 | 000000000001

Decoded:
  Timestamp: 1716984000123 ms since custom epoch (2025-01-01)
  Datacenter: 5
  Machine: 12
  Sequence: 1

#Machine Registration (PostgreSQL or ZooKeeper — control plane only)

CREATE TABLE machine_registry (
  datacenter_id   SMALLINT NOT NULL,
  machine_id      SMALLINT NOT NULL,
  hostname        VARCHAR(255) NOT NULL,
  ip_address      INET NOT NULL,
  registered_at   TIMESTAMP DEFAULT NOW(),
  last_heartbeat  TIMESTAMP DEFAULT NOW(),
  is_active       BOOLEAN DEFAULT true,
  PRIMARY KEY (datacenter_id, machine_id)
);

CREATE INDEX idx_machine_heartbeat ON machine_registry(last_heartbeat)
  WHERE is_active = true;

#No Hot-Path Data Store

The ID generator has NO hot-path database dependency.
- ID generation is purely in-memory (bitwise operations)
- Machine registration is a one-time startup operation
- No reads or writes to any external store during ID generation
- This is what makes it fast (< 1μs per ID)

#Access Patterns

Query	Store	Frequency
Generate ID	In-memory (no store)	Every request (hot path)
Register machine on startup	PostgreSQL / ZooKeeper	Once per boot
Heartbeat update	PostgreSQL	Every 30 seconds
Parse/decode ID	In-memory bit manipulation	Debug only

#5. High-Level Design (HLD) & Scale Evolution

#Stage 1: MVP / Single Server (1K IDs/sec)

Architecture: Auto-increment counter in application memory. Single server.
ID format: Simple 64-bit counter starting from 1.
Bottleneck: Not distributed; single point of failure; IDs not time-sortable.

#Stage 2: Growth Scale (100K IDs/sec, 10 nodes)

Key Changes:
- Snowflake-style 64-bit IDs with timestamp + machine_id + sequence.
- Machine ID assignment via config file or ZooKeeper.
- NTP synchronization for clock accuracy.
Bottleneck: Clock skew between machines; machine ID management.

#Stage 3: Twitter Snowflake Scale (1M+ IDs/sec, 1024 nodes)

#Architecture Diagram

┌──────────────────────────────────────────────────────────────┐
│                    Datacenter 1 (dc_id=0)                     │
│                                                                │
│  ┌─────────────┐ ┌─────────────┐ ┌─────────────┐             │
│  │ App Server 1 │ │ App Server 2 │ │ App Server N │             │
│  │ (machine=0)  │ │ (machine=1)  │ │ (machine=31) │             │
│  │              │ │              │ │              │             │
│  │ ┌──────────┐ │ │ ┌──────────┐ │ │ ┌──────────┐ │             │
│  │ │ ID Gen   │ │ │ │ ID Gen   │ │ │ │ ID Gen   │ │             │
│  │ │ Library  │ │ │ │ Library  │ │ │ │ Library  │ │             │
│  │ │ (in-proc)│ │ │ │ (in-proc)│ │ │ │ (in-proc)│ │             │
│  │ └──────────┘ │ │ └──────────┘ │ │ └──────────┘ │             │
│  └──────────────┘ └──────────────┘ └──────────────┘             │
│                         │                                       │
│              ┌──────────▼──────────┐                            │
│              │  Machine Registry    │                            │
│              │  (ZooKeeper / etcd)  │                            │
│              └─────────────────────┘                            │
└──────────────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────────────┐
│                    Datacenter 2 (dc_id=1)                     │
│              (Same structure, different dc_id)                 │
└──────────────────────────────────────────────────────────────┘
                    ... up to 32 datacenters

#Component Breakdown

Component	Responsibility	Tech Choice
ID Generator Library	In-process ID generation; bit manipulation; sequence management	Go / Java / Rust library
Machine Registry	Assign unique (dc_id, machine_id) pairs; prevent duplicates	ZooKeeper / etcd / PostgreSQL
NTP Service	Clock synchronization across all machines	ntpd / chrony
Monitoring Agent	Track ID generation rate, clock drift, sequence overflow	Prometheus + Grafana

#Data Flow

ID Generation (The Hot Path — entirely in-process):

Application calls idgen.next_id()
  → 1. Get current timestamp in milliseconds
  → 2. If same millisecond as last ID:
        sequence++ (up to 4095)
        If sequence overflows → wait until next millisecond
  → 3. If new millisecond:
        sequence = 0
  → 4. Assemble 64-bit ID:
        id = (timestamp << 22) | (dc_id << 17) | (machine_id << 12) | sequence
  → 5. Return id (zero network calls, < 1μs)

Machine Registration (Startup only):

App server boots → ID Gen Library init
  → 1. Read dc_id from environment/config
  → 2. Request machine_id from ZooKeeper (ephemeral node)
     OR read from config file (static assignment)
  → 3. Verify uniqueness: no other active node has same (dc_id, machine_id)
  → 4. Start heartbeat (every 30s)
  → 5. Ready to generate IDs

#6. Deep Dive — Core Components

#Snowflake ID Generator — Detailed Design

Why 64-bit Snowflake over alternatives?

Approach	Size	Sortable	Coordination	IDs/sec/node	Drawbacks
UUID v4 (random)	128-bit	No	None	Unlimited	Too large for DB index; not sortable
UUID v7 (time)	128-bit	Yes	None	Unlimited	128-bit wastes space; string format
DB auto-increment	64-bit	Yes	Per-DB	~10K	Single DB bottleneck; coordination required
DB ticket server	64-bit	Yes	Per-ticket-server	~50K	Still centralized; SPOF
Snowflake	64-bit	Yes	None (runtime)	4M	Machine ID assignment needed at boot

Chosen: Snowflake — Best balance of size, sortability, throughput, and independence.

#Clock Management — Detailed Design

The Clock Skew Problem:

If server clock goes BACKWARD (NTP adjustment, leap second):
  → Same timestamp reused → potential duplicate IDs!

Mitigation:
  1. Track last_timestamp in memory
  2. If current_time < last_timestamp → clock went backward
  3. Wait until clock catches up (spin-wait)
  4. If backward > 5ms → alert + refuse to generate (prevent long stalls)
  5. Use monotonic clock where possible (clock_gettime(MONOTONIC))

NTP Best Practices:

- Use multiple NTP servers (pool.ntp.org + internal stratum 1)
- Chrony preferred over ntpd (faster convergence, slew not step)
- Max allowed drift: 10ms (beyond this → alert)
- Leap second handling: Google's leap smear (spread over 24h)

#Machine ID Assignment — Detailed Design

Three strategies:

Strategy	Pros	Cons
Static config	Simplest; no dependency	Manual management; error-prone
ZooKeeper ephemeral nodes	Auto-release on crash; no duplicates	ZK dependency at startup
Database lease	No ZK needed; familiar	Must renew lease; DB as dependency

Chosen: ZooKeeper ephemeral nodes (for large deployments)

On startup:
  1. Try to create /id-gen/dc/{dc_id}/machine/{0..31} (ephemeral)
  2. First available slot → that's your machine_id
  3. Node crash → ephemeral node auto-deleted → slot freed
  4. Heartbeat: ZK session keepalive handles this automatically

#Scaling Strategy

Component	Strategy
ID generation	Pure in-process; scales with app servers (no bottleneck)
Machine registry	ZooKeeper 3-node quorum; only used at boot
Multi-datacenter	Each DC gets unique dc_id (5 bits = 32 DCs)
Beyond 1024 machines	Expand bit layout (steal from timestamp or sequence)

#Caching Strategy

N/A — ID generation is entirely in-memory.
No caching needed. No external data dependencies on hot path.
The generator IS the cache: it holds only:
  - last_timestamp (8 bytes)
  - sequence counter (2 bytes)
  - dc_id + machine_id (2 bytes)
Total state: 12 bytes in memory.

#Consistency Models

Data	Model	Rationale
Generated IDs	Globally unique (no consistency needed)	Each node generates from its own bit-space; no overlap possible
Machine registry	Strongly consistent (ZooKeeper)	Must prevent duplicate (dc_id, machine_id) assignments
Clock	Eventually consistent (NTP)	~10ms drift acceptable; IDs from different nodes not strictly ordered
Time ordering	Roughly ordered (within ~10ms)	IDs from same node are strictly ordered; cross-node within NTP drift

#7. Low-Level Design — Core Functionality

#Key Algorithms

1. Snowflake ID Generator

import time
import threading

class SnowflakeGenerator:
    # Bit allocation
    TIMESTAMP_BITS = 41
    DC_BITS = 5
    MACHINE_BITS = 5
    SEQUENCE_BITS = 12

    MAX_SEQUENCE = (1 << SEQUENCE_BITS) - 1       # 4095
    MAX_MACHINE = (1 << MACHINE_BITS) - 1          # 31
    MAX_DC = (1 << DC_BITS) - 1                    # 31

    # Bit shifts
    TIMESTAMP_SHIFT = DC_BITS + MACHINE_BITS + SEQUENCE_BITS  # 22
    DC_SHIFT = MACHINE_BITS + SEQUENCE_BITS                    # 17
    MACHINE_SHIFT = SEQUENCE_BITS                               # 12

    # Custom epoch: Jan 1, 2025 00:00:00 UTC
    EPOCH = 1735689600000  # ms

    def __init__(self, datacenter_id, machine_id):
        assert 0 <= datacenter_id <= self.MAX_DC
        assert 0 <= machine_id <= self.MAX_MACHINE
        self.dc_id = datacenter_id
        self.machine_id = machine_id
        self.sequence = 0
        self.last_timestamp = -1
        self.lock = threading.Lock()

    def _current_millis(self):
        return int(time.time() * 1000)

    def _wait_next_millis(self, last_ts):
        """Spin-wait until clock advances to next millisecond."""
        ts = self._current_millis()
        while ts <= last_ts:
            ts = self._current_millis()
        return ts

    def next_id(self):
        with self.lock:
            timestamp = self._current_millis()

            # Clock went backward — critical error
            if timestamp < self.last_timestamp:
                drift = self.last_timestamp - timestamp
                if drift > 5:  # > 5ms backward
                    raise ClockDriftError(f"Clock moved back {drift}ms")
                # Small drift: wait it out
                timestamp = self._wait_next_millis(self.last_timestamp)

            if timestamp == self.last_timestamp:
                # Same millisecond: increment sequence
                self.sequence = (self.sequence + 1) & self.MAX_SEQUENCE
                if self.sequence == 0:
                    # Sequence overflow: wait for next millisecond
                    timestamp = self._wait_next_millis(self.last_timestamp)
            else:
                # New millisecond: reset sequence
                self.sequence = 0

            self.last_timestamp = timestamp
            ts_offset = timestamp - self.EPOCH

            # Assemble 64-bit ID
            id = ((ts_offset << self.TIMESTAMP_SHIFT) |
                  (self.dc_id << self.DC_SHIFT) |
                  (self.machine_id << self.MACHINE_SHIFT) |
                  self.sequence)

            return id

2. ID Parser (Decode)

def parse_snowflake_id(id_value):
    """Decode a Snowflake ID into its components."""
    EPOCH = 1735689600000

    sequence = id_value & 0xFFF                    # last 12 bits
    machine_id = (id_value >> 12) & 0x1F           # next 5 bits
    dc_id = (id_value >> 17) & 0x1F                # next 5 bits
    timestamp = (id_value >> 22) + EPOCH            # remaining 41 bits

    return {
        "timestamp_ms": timestamp,
        "timestamp_iso": datetime.fromtimestamp(timestamp/1000).isoformat(),
        "datacenter_id": dc_id,
        "machine_id": machine_id,
        "sequence": sequence
    }

3. Machine ID Auto-Assignment (ZooKeeper)

def acquire_machine_id(zk_client, datacenter_id):
    """Acquire a unique machine_id via ZooKeeper ephemeral node."""
    for machine_id in range(32):  # 0-31
        path = f"/id-gen/dc/{datacenter_id}/machine/{machine_id}"
        try:
            # Create ephemeral node — auto-deleted on disconnect
            zk_client.create(path, ephemeral=True,
                           value=socket.gethostname().encode())
            return machine_id  # successfully claimed
        except NodeExistsError:
            continue  # slot taken, try next

    raise NoAvailableSlots(f"All 32 machine IDs taken in DC {datacenter_id}")

#Design Patterns Used

Pattern	Where	Why
Embedded Library	ID gen as in-process library, not a service	Zero network latency; no SPOF; highest throughput
Bit Packing	64-bit ID with timestamp + DC + machine + seq	Compact; sortable; self-describing
Lease-based Assignment	ZK ephemeral nodes for machine IDs	Auto-release on crash; no manual cleanup
Monotonic Counter	Sequence number within same millisecond	Guarantees uniqueness within same ms on same machine

#8. Failure Handling & Edge Cases

#What Happens When X Fails?

Failure	Impact	Mitigation
Clock goes backward	Potential duplicate IDs	Detect and spin-wait for small drift (< 5ms); error for large drift
NTP outage	Clock drift increases over time	Local oscillator holds; alert if drift > 10ms; continue generating
ZooKeeper down	Can't register NEW nodes	Running nodes unaffected (machine_id already assigned); new boots fail
Machine crashes	Ephemeral ZK node deleted; machine_id freed	New process acquires same or different slot; no duplicate risk
Sequence overflow	> 4096 IDs in 1ms on one machine	Wait for next millisecond (< 1ms delay); alert on sustained overflow
Datacenter failure	All IDs from that DC stop	Other DCs unaffected; IDs are globally unique across DCs

#Edge Cases

Leap seconds → Use Google leap smear; OR ignore (1s gap is acceptable)
VM migration → machine_id may change; ZK ephemeral node re-created on new host
Container rescheduling → Same as VM migration; use pod UID or container ID for ZK node
Bit layout exhaustion (> 32 DCs) → Reconfigure bit allocation (steal from sequence: 11-bit seq = 2048/ms still plenty)
Timestamp overflow (year 2094) → 41 bits from 2025 epoch expires in 69 years; plan migration to 128-bit or new epoch
Dual-write during failover → Impossible by design: each (dc_id, machine_id) pair is exclusive

#9. Monitoring & Observability

#Key Metrics

Metric	Target	Alert Threshold
IDs generated/sec	Varies by service	> 4000/ms (approaching sequence overflow)
Clock drift from NTP	< 10ms	> 50ms
Sequence overflow events	0	> 10/min
Clock backward events	0	> 1/hour
ZK session health	Connected	Disconnected > 30s
Machine ID conflicts	0	> 0 (critical)

#Alerting Strategy

P0 (Page immediately): Machine ID conflict detected (two nodes with same ID), clock drift > 100ms
P1 (15 min response): Sustained sequence overflow (> 4096 IDs/ms), ZK disconnection > 5 min, clock backward events
P2 (Next business day): Clock drift > 10ms, ZK latency spike, ID generation rate anomaly

#SLAs / SLOs

ID Generation Latency:  P99 < 1ms (typically < 1μs)
Uniqueness:             100% (zero collisions, by design)
Availability:           99.999% (in-process; no external dependency on hot path)
Sortability:            Monotonic within same machine; ±10ms across machines

#10. Trade-off Summary

Decision	Chose	Over	Because
ID format	64-bit Snowflake	UUID (128-bit)	Half the size; DB-friendly BIGINT; time-sortable
Architecture	In-process library	Standalone ID service	Zero latency; no network dependency; no SPOF
Timestamp precision	Milliseconds	Microseconds	41 bits covers 69 years; μs would need more bits
Coordination	Startup-only (ZK)	Runtime coordination	Hot path has zero external dependencies
Clock drift handling	Spin-wait + error	Accept duplicates	Correctness over availability for ID uniqueness
Sequence overflow	Wait for next ms	Pre-allocate ranges	Simpler; overflow rare (4096 IDs/ms is high)
Bit allocation	41-5-5-12	Custom split	Proven by Twitter; good balance for most deployments
Custom epoch	Jan 1, 2025	Unix epoch (1970)	Saves 55 years of timestamp space; extends lifetime to 2094

#11. Extensions & Follow-ups

#What Would You Add With More Time?

UUID v7 Compatibility — Optional 128-bit mode for systems requiring UUID format
Multi-Tenant ID Spaces — Embed tenant ID in the bit layout for multi-tenant SaaS
ID Reservation — Pre-allocate ID ranges for batch operations (e.g., bulk import)
Encryption — Optionally encrypt IDs to hide timestamp/machine info from external users
Metrics Dashboard — Real-time visualization of ID generation rates across all nodes
Backward-Compatible Migration — Tool to migrate from auto-increment to Snowflake IDs

#How Would This Change at 100x Scale?

100K machines: Expand machine bits (steal from timestamp or use 128-bit format); or use hierarchical ID (region → cluster → machine)
100M IDs/sec globally: Already supported (4M/sec/machine × 1024 machines = 4B/sec capacity)
Multi-region with strict ordering: Use hybrid logical clocks (HLC) instead of physical timestamps; ensures causality
Regulatory requirements: Embed region code in ID for data residency compliance

#12. Cross-References

Topic	Connection
URL Shortener (#1)	Key Gen Service is a Snowflake-like ID generator
Key-Value Store (#3)	KV stores use unique IDs for internal coordination
Pastebin (#25)	Pre-generated key ranges solve the same uniqueness problem

#Building Blocks Used

PostgreSQL — Machine registry (control plane only; not on hot path)
Redis — Alternative to ZK for machine ID leasing (SETNX with TTL)

#Concepts Used

Consistency Models — Strong consistency for machine ID assignment; eventual for clock sync
Sharding — ID bit layout is a form of static partitioning (dc_id + machine_id = shard key)