Open on desktop
Antimetal's interactive diagrams require a larger screen. Open this page on your laptop or desktop to continue.
Unique ID Generator
§1Step 2 — High-Level Design
Design a distributed ID generation system. Compare UUID, Snowflake, and ULID approaches.
Connect the API server to a load balancer that will distribute ID generation requests across the worker pool. Round-robin across healthy workers is the right default.
A load balancer sits between the API server and the ID generator worker pool, distributing requests with round-robin or least-connections routing and performing health checks on each worker.
At scale, a single generator is a ceiling on throughput and a single point of failure. The load balancer turns a fleet of independent workers into a single logical endpoint — clients don't need to know how many workers exist.
Round-robin can't guarantee perfectly even distribution if workers have different response times. Least-connections routing is more accurate under variable load, but adds state to the load balancer.
Twitter's Snowflake service ran behind HAProxy. Discord routes ID generation through their internal load balancing layer. Instagram's ID system uses a DNS-based round-robin approach for the initial request routing.
A well-tuned L4 load balancer handles 1M+ RPS with sub-millisecond overhead. At our 10K RPS target, the load balancer consumes less than 1% of its capacity.
Add three worker services implementing the Snowflake algorithm. Each worker is assigned a unique machine ID (0–1023) at startup and generates 64-bit IDs using only bitwise operations — no database, no coordination at runtime.
Snowflake workers implement a 64-bit ID format: 1 sign bit (always 0) + 41-bit millisecond timestamp + 10-bit worker ID + 12-bit per-millisecond sequence. Generation is pure in-memory bitwise ops — no I/O, no locks across workers.
UUID v4 is random — you lose time-ordering, which destroys index locality on inserts (B-tree pages scatter randomly). Auto-increment requires a single authoritative database. Snowflake IDs are time-ordered (newer = higher), globally unique, and generated at the edge without coordination.
Snowflake IDs encode approximate creation time — an attacker can infer when an object was created from its ID. If privacy matters, add a reversible shuffle layer on top (Instagram's ID system did this). Also: worker IDs must be unique — collision produces silent data corruption.
Twitter Snowflake (open-sourced 2010), Discord's snowflakes (same format, different epoch), Instagram IDs (Postgres-based with Snowflake bit layout), TikTok video IDs, Shopify order IDs — all Snowflake variants.
One worker: 4,096 IDs/ms = 4,096,000 IDs/sec. Three workers: 12M IDs/sec peak. At 10K RPS target, you're using 0.08% of capacity. Even at Twitter's peak of 150K tweets/second, three workers handle it comfortably.
Add a ZooKeeper or etcd node to act as the worker ID coordination service. Each Snowflake worker claims a unique worker ID lease on startup. Without this, two workers could be assigned the same ID — silently producing duplicate IDs.
A service registry (ZooKeeper, etcd, Consul) provides distributed coordination via leases. Each worker acquires a worker ID lease on startup using an atomic compare-and-swap operation — guaranteed exclusive across the cluster.
Worker ID collision is the worst failure mode: two workers silently generating IDs with the same worker ID will produce colliding IDs that are impossible to detect until a uniqueness constraint fails in your database — potentially hours later.
ZooKeeper adds a startup dependency — workers can't start if the registry is unreachable. Mitigate with fallback to a pre-configured static worker ID (written to local disk after first successful lease claim) so restarts don't require the registry.
Twitter's Snowflake service used ZooKeeper for worker ID assignment. Discord uses an environment-variable-based approach for simplicity (manually assigned in deployment config). Sonyflake (Go implementation) uses the machine's IP address as the worker ID.
The registry is consulted only at startup/shutdown — at runtime, zero requests go to it. Even with 1,024 workers starting simultaneously, a healthy etcd cluster handles this trivially.
Add a monitoring node to track clock skew, ID generation rate per worker, sequence overflow events, and worker health. Clock skew is the only failure mode that can cause silent ID collisions — monitoring must alert on it immediately.
Monitoring collects: (1) IDs generated per second per worker, (2) sequence overflow events (clock waiting), (3) system clock offset vs NTP, (4) worker ID assignment events (lease claims/releases), (5) per-worker p99 generation latency.
Clock skew is silent. A worker generating IDs with a backward clock won't error — it will happily produce IDs that collide with IDs it issued in the future. Without monitoring, you only discover this when a duplicate key exception surfaces in your primary database.
Monitoring adds a small network overhead per metric emission. Use async, non-blocking metrics emission (UDP to StatsD, or background goroutine pushing to Prometheus) so the hot path (ID generation) is never blocked by the metrics path.
Twitter monitored Snowflake workers for clock skew and sequence overflow. Discord's ID system monitors generation rate to detect worker failures early. Cloudflare monitors their ID systems for drift as part of their SLO stack.
Metrics emission at 10K IDs/sec generates roughly 10 data points/sec per worker — negligible load. Clock drift alerts fire within seconds of drift exceeding a threshold (typically 1ms for Snowflake systems).
At high ID generation volume, distribute requests across multiple ID generator nodes behind a load balancer.
A load balancer distributes ID generation requests across multiple generator nodes, each with a unique machine ID.
A single generator node can produce ~500K IDs/second. At high traffic with billions of IDs/day, you need multiple nodes.
Machine IDs must be unique and stable. Use node index assignment or coordinate via ZooKeeper for dynamic scaling.
Twitter's Snowflake runs multiple generator nodes, each with a unique datacenter+machine ID combination.
Each Snowflake-style node generates 4K IDs/ms (4M/second). Two nodes = 8M IDs/second.
At peak, pre-generate batches of IDs into a Redis queue so generators can serve from cache without compute overhead.
A Redis cache holds pre-generated ID batches. Clients pop IDs from the list rather than triggering generation per-request.
At peak, even fast ID generation has compute overhead. Pre-batch generation smooths CPU usage and cuts P99 latency 10x.
IDs in the batch may be skipped if the server crashes mid-batch (gaps in the sequence). This is usually acceptable.
Instagram's ID system pre-allocates ranges. Flickr used MySQL auto-increment with batching for their ID service.
A Redis list handles millions of pops/second. Pre-generating 10K IDs every 10ms gives headroom for 1M ID requests/second.
§2Step 3 — Deep Dive
A load balancer sits between the API server and the ID generator worker pool, distributing requests with round-robin or least-connections routing and performing health checks on each worker.
| Approach | Throughput | Sortable? | Coordination needed? | Best for | Cost | Ops burden |
|---|---|---|---|---|---|---|
| Snowflake (timestamp+worker+seq) | 4K IDs/ms/node | Yes (time-ordered) | No (worker ID pre-assigned) | Twitter, Discord, Uber ✓ | Low | Medium |
| UUID v4 (random) | Unlimited | No | No | Simple, global uniqueness, not sortable | Low | Low |
| UUID v7 (time-ordered) | Unlimited | Yes | No | Modern replacement for v4 | Low | Low |
| Database auto-increment | DB throughput limited | Yes | Yes (central DB) | Single-node, small scale | Low | Low |
| ULID | Unlimited | Yes | No | URL-safe, Snowflake alternative | Low | Low |
Distributed ID generation — Snowflake is the industry standard.
import time
import threading
# Snowflake layout (64 bits total):
# [1 sign][41 timestamp ms][10 worker ID][12 sequence]
EPOCH = 1704067200000 # 2024-01-01 00:00:00 UTC in ms
WORKER_BITS = 10
SEQ_BITS = 12
MAX_SEQ = (1 << SEQ_BITS) - 1 # 4095
class SnowflakeGenerator:
def __init__(self, worker_id: int):
assert 0 <= worker_id < (1 << WORKER_BITS)
self.worker_id = worker_id
self.sequence = 0
self.last_ms = -1
self.lock = threading.Lock()
def next_id(self) -> int:
with self.lock:
now = int(time.time() * 1000) - EPOCH
if now == self.last_ms:
self.sequence = (self.sequence + 1) & MAX_SEQ
if self.sequence == 0:
# Sequence exhausted — wait for next millisecond
while now <= self.last_ms:
now = int(time.time() * 1000) - EPOCH
else:
self.sequence = 0
self.last_ms = now
return (now << (WORKER_BITS + SEQ_BITS)) | (self.worker_id << SEQ_BITS) | self.sequence
gen = SnowflakeGenerator(worker_id=3)
print(gen.next_id()) # e.g. 7264823049182208003 (time-sortable)| Component | Why Add It | Tradeoff |
|---|---|---|
| Load Balancer | At scale, a single generator is a ceiling on throughput and a single point of failure. | Round-robin can't guarantee perfectly even distribution if workers have different response times. |
| ID Generator Workers | UUID v4 is random — you lose time-ordering, which destroys index locality on inserts (B-tree pages scatter randomly). | Snowflake IDs encode approximate creation time — an attacker can infer when an object was created from its ID. |
| Service Registry | Worker ID collision is the worst failure mode: two workers silently generating IDs with the same worker ID will produce colliding IDs that are impossible to detect until a uniqueness constraint fails in your database — potentially hours later. | ZooKeeper adds a startup dependency — workers can't start if the registry is unreachable. |
| Monitoring | Clock skew is silent. | Monitoring adds a small network overhead per metric emission. |
| Load Balancer | A single generator node can produce ~500K IDs/second. | Machine IDs must be unique and stable. |
| Cache for ID Batching | At peak, even fast ID generation has compute overhead. | IDs in the batch may be skipped if the server crashes mid-batch (gaps in the sequence). |
Design decision tradeoffs
A worker's system clock drifts backward by 50ms. The Snowflake algorithm panics: the same timestamp + sequence could collide with IDs already issued. Worker must refuse requests until the clock catches up, or wait for the skew to resolve.
Two workers are assigned the same worker ID — every ID they generate will collide. Without a coordination service, this happens silently. With ZooKeeper, worker ID leases prevent this: no two workers can hold the same ID lease simultaneously.
One of three worker nodes crashes mid-traffic. The load balancer detects the unhealthy instance via health checks and stops routing to it. The remaining two workers absorb the full 10K RPS — each has 4M IDs/sec headroom, so capacity is not a concern.
A single worker receives 4,097 ID requests in the same millisecond. The 12-bit sequence field (max 4,096) overflows. Proper implementation must wait until the next millisecond tick before issuing the next ID — adding up to 1ms of latency for burst requests.
The 41-bit timestamp field stores milliseconds since a custom epoch (e.g. 2010-01-01). It exhausts in ~69 years. Twitter's Snowflake will overflow in 2079. Systems should document their epoch and plan an ID format migration well in advance — same problem as Y2K, but you get to see it coming.
§3Step 4 — Wrap Up
| Decision | Choice | Why |
|---|---|---|
| Load Balancer | A load balancer sits between the API server and the ID generator worker pool, distributing requests with round-robin or least-connections routing and performing health checks on each worker. | At scale, a single generator is a ceiling on throughput and a single point of failure. |
| ID Generator Workers | Snowflake workers implement a 64-bit ID format: 1 sign bit (always 0) + 41-bit millisecond timestamp + 10-bit worker ID + 12-bit per-millisecond sequence. | UUID v4 is random — you lose time-ordering, which destroys index locality on inserts (B-tree pages scatter randomly). |
| Service Registry | A service registry (ZooKeeper, etcd, Consul) provides distributed coordination via leases. | Worker ID collision is the worst failure mode: two workers silently generating IDs with the same worker ID will produce colliding IDs that are impossible to detect until a uniqueness constraint fails in your database — potentially hours later. |
| Monitoring | Monitoring collects: (1) IDs generated per second per worker, (2) sequence overflow events (clock waiting), (3) system clock offset vs NTP, (4) worker ID assignment events (lease claims/releases), (5) per-worker p99 generation latency. | Clock skew is silent. |
| Load Balancer | A load balancer distributes ID generation requests across multiple generator nodes, each with a unique machine ID. | A single generator node can produce ~500K IDs/second. |
| Cache for ID Batching | A Redis cache holds pre-generated ID batches. | At peak, even fast ID generation has compute overhead. |
Key design decisions