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.
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.
| Choice | What it buys | What it costs |
|---|---|---|
| UUID v4 | fully 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 scheme | 64-bit, time-sortable, decentralized, but depends on system clock stability. |
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
);
}
}
Trade-Off Analysis.
Key architectural decisions and failure handling for Design a Distributed Unique ID Generator.
| Choice | What it buys | What it costs |
|---|---|---|
| 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. | |
| 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. |
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:
- ID Bit-Allocation Scheme: 64-bit Twitter Snowflake vs 128-bit UUID (v4 / v7) vs Centralized Ticket Server vs Database Auto-Increment.
- Clock Drift & Rollback Handling: NTP Backward Drift Protection (Refuse & Halt vs Spin Wait vs Reserve Next Millisecond Sequence).
- Worker Node Coordination: Static Configuration vs Consensus Lease (ZooKeeper / Consul / etcd) vs K8s StatefulSet Ordinals.
- 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
- 64-Bit Compatibility: Fits natively inside an
int64/BIGINTcolumn. Highly compact, fits in CPU registers, and cuts secondary index memory footprint in half compared to 128-bit UUIDs. - 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.
- 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 , spin-wait (
Thread.sleep(drift)) until clock catches up. - If drift is , reject ID generation, fire high-priority alert, or switch to backup worker ID reserved for clock skew emergencies.
- If drift is , spin-wait (
- 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
}
}
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.
Sequence saturation handling.
Sequence saturation handling.
| Choice | What it buys | What it costs |
|---|---|---|
| Blocking on sequence overflow | introduces 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.
Design Unique Id Generator — Normal → Load / Fault → Recovery
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.
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.
Putting Design a Distributed Unique ID Generator Together
- 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.
Interview Readiness Check
Resilient end-to-end architecture ready for production spikes.
Walk through bottlenecks, back-of-the-envelope math, and failure recovery.
Make the trade-off yourself.
Practice Check
Test your understanding
Why is selecting a low-cardinality column like 'country_code' as a primary database shard key considered a dangerous architectural pitfall?
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.
