System Design Case Study

How does Twitter generate 100K+ unique time-sorted IDs/sec without coordination?

?? Design a distributed ID generator: 100K+ IDs/sec, 64-bit, time-sortable, 1000+ nodes, zero collisions
Concepts Involved
Partitioning Consistency Clock Sync Fault Tolerance Sharding

Problem Statement

How does a distributed ID generation system produce 100K+ unique, time-sortable 64-bit IDs per second across 1000+ nodes with zero coordination between them and guaranteed zero collisions?

Core challenge: Need IDs that are globally unique (no central coordinator), time-sortable (newer IDs > older IDs for timeline ordering), compact (64-bit, fits in a long), and generated at 100K+/sec per node without any cross-node communication.
100K+
IDs generated / sec
64-bit
compact, fits in long
1000+
nodes, no coordination
Zero
collisions guaranteed

Architecture

LAYER 1: ID STRUCTURE · 64-bit Snowflake Layout 0 1 bit sign 41 bits · timestamp (ms since custom epoch) 2^41 ms · 69.7 years before overflow MSB position ? IDs naturally sort by creation time 10 bits · node_id 2^10 = 1024 unique nodes assigned at deploy via ZooKeeper 12 bits · sequence 2^12 = 4096 IDs/ms/node resets to 0 each millisecond 1/64 41/64 (64%) 10/64 (16%) 12/64 (19%) LAYER 2: GENERATION · Independent Nodes (No Cross-Node Communication) Node 1 (ID=001) generates IDs locally seq: 0, 1, 2 ... 4095 local clock + atomic counter 4096 IDs/ms capacity Node 2 (ID=002) generates IDs locally seq: 0, 1, 2 ... 4095 local clock + atomic counter 4096 IDs/ms capacity Node N (ID=999) generates IDs locally seq: 0, 1, 2 ... 4095 local clock + atomic counter 4096 IDs/ms capacity ZooKeeper assigns node_ids at deploy time only one-time coordination no runtime calls ? zero network calls during ID generation ? deploy-time only LAYER 3: GUARANTEES · Uniqueness + Clock Skew + Comparison Same ms + Same node ? sequence # differs (0,1,2...4095) unique by local seq counter Same ms + Diff node ? node_id bits differ (001 vs 002) unique by node assignment Diff ms (any node) ? timestamp bits differ unique by time (MSB) Clock Skew Handling NTP backward jump detected ? REFUSE generation wait until clock catches up to last seen ms prevents duplicate timestamps across restarts Comparison: Snowflake vs UUID vs Auto-Inc vs ULID Snowflake: 64-bit, sortable, no coord, needs node_id mgmt UUID v4: 128-bit, NOT sortable, no coord, poor index locality Auto-Inc: sortable, SPOF | ULID: 128-bit, sortable, no coord 4096 IDs/ms/node = 4M/sec | 69 years before overflow | time-sortable (timestamp in MSB) | no coordination during generation 1024 nodes · 4M IDs/sec = 4B IDs/sec total cluster capacity | Custom epoch extends usable lifetime | Compact 8-byte fits in DB BIGINT
Bit layout: 1 bit sign + 41 bits timestamp (ms since custom epoch, ~69 years) + 10 bits node ID (1024 machines) + 12 bits sequence (4096 IDs/ms/node). Total capacity: 4M IDs/sec/node. Time-sortable because timestamp is the most significant bits.
Zero coordination: Each node has a unique node_id (assigned at deploy via ZooKeeper/config). Within the same millisecond, sequence counter increments locally. Different nodes can never collide because their node_id bits differ. No network calls needed during ID generation.
Anti-patterns: UUID v4 (128-bit random) · not sortable, wastes space, poor index locality. Auto-increment DB · single point of failure, not distributed. Timestamp-only · collisions within same ms. No clock monotonicity check · NTP jumps cause duplicate timestamps.
Clock skew handling: If system clock moves backward (NTP adjustment), the generator refuses to generate IDs until clock catches up · prevents duplicate timestamps. Some implementations use logical clocks or wait. Critical for correctness guarantee.
ID Strategy Comparison Snowflake (64-bit) ? Time-sortable ? Compact (8 bytes) ? No coordination ? Needs node_id mgmt UUID v4 (128-bit) ? Not sortable ? 16 bytes (2· larger) ? No coordination ? Poor index locality Auto-Increment DB ? Sortable, sequential ? Compact ? Single point of failure ? Not distributed ULID (128-bit) ? Time-sortable ? 16 bytes ? No coordination Lexicographically sortable

Interview Cheat Sheet

1. 64-bit layout · 41 timestamp + 10 node_id + 12 sequence = time-sortable, unique, compact
2. No coordination · node_id assigned once, all generation is local (no network calls)
3. Time-sortable · timestamp in MSB means IDs naturally sort by creation time
4. Capacity · 4096 IDs/ms/node = 4M/sec/node, 1024 nodes = 4B IDs/sec total
5. Clock skew · refuse generation on backward clock jump, wait for catch-up
6. Trade-offs vs UUID · smaller (64 vs 128 bit), sortable, but requires node_id management