Loading...
High availability: Greater than 99.99% uptime. An ID outage cascades into a write outage across the entire platform.
Low latency: Sub-millisecond ID generation via local computation only, no network calls, no disk I/O, no consensus rounds.
Horizontal scalability: Adding generator nodes increases throughput linearly without redesign.
No single point of failure: Failure of any single node reduces capacity but does not halt ID generation.
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
The bit budget is the real capacity constraint (not storage, not bandwidth). Every bit allocated to one field is stolen from another. 41 timestamp bits at millisecond resolution cover 2 to the power of 41 milliseconds, which is roughly 69.7 years from a custom epoch. 10 worker bits allow 1,024 nodes. 12 sequence bits allow 4,096 IDs per millisecond per node. That is 4,096 times 1,024 times 1,000 which equals roughly 4.19 billion IDs per second system-wide. At 10K IDs per second baseline, we are using 0.00024% of capacity.
Baseline: 10,000 IDs per second. Peak: 100,000 IDs per second. Per node: 4,096 IDs per millisecond equals 4.096 million IDs per second theoretical max. With 10 nodes: 40.96 million IDs per second, 400x headroom over peak.
The generator stores nothing persistently on the hot path. Its only persistent state is the worker ID registry in ZooKeeper: at most 1,024 entries totaling under 100 KB. Each node holds exactly three values in memory: last timestamp, worker ID, and current sequence.
41 bits at millisecond resolution equals roughly 69.7 years. With a custom epoch starting January 1, 2020, IDs remain valid until roughly 2089.
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
Generate single ID: POST /ids
Returns a single unique ID. No request body needed; the generator uses its own clock, worker ID, and sequence counter.
json
{
"id": "7089463626481090561"
}
Generate batch IDs: POST /ids/batch
Request body specifies count. Returns an array of IDs generated in sequence.
json
// Request
{ "count": 100 }
// Response
{ "ids": ["7089463626481090561", "7089463626481090562", ...] }
The coordination store holds worker-to-node mappings. Each entry is an ephemeral node with a lease:
/id-generator/workers/42
├── node_instance_id: "i-0a1b2c3d4e5f"
├── lease_expires_at: 1709654400000
└── fencing_token: 17
worker_id (0-1023): The 10-bit identifier embedded in every ID this node generates. The key in the coordination store.
node_instance_id: The cloud instance ID or hostname. Used for debugging: identifying which physical machine holds which worker ID.
lease_expires_at: Timestamp when the lease expires if not renewed. Ephemeral znodes in ZooKeeper auto-delete on session loss, but explicit TTL tracking provides an additional safety layer.
fencing_token: Monotonically increasing integer. Each new lease grant increments this value. Used to detect stale nodes that lost their lease but have not yet realized it.
A small config entry stores the epoch and bit layout version:
/id-generator/config
├── epoch: 1577836800000 (Jan 1, 2020 UTC)
└── layout_version: 1 (41/10/12 bit split)
All nodes read this on startup to ensure consistent ID generation. Changing the epoch or bit layout requires a coordinated rollout.
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
The architecture has two distinct operational phases, and understanding this separation is the key insight.
Startup phase (coordinator-dependent): A new node boots, contacts the coordination store (ZooKeeper or etcd), acquires a unique worker ID with a lease, and loads the epoch and bit layout configuration. This is the only moment the node depends on an external system.
Runtime phase (fully independent): Once a node has its worker ID, it generates IDs using only local computation: read the system clock, manage a per-millisecond sequence counter, compose the bits, return the ID. No network calls, no disk writes, no consensus rounds. The hot path touches no external systems.
Client Services: Any service needing unique IDs (tweet ingestion, order processing, event logging). Clients call the ID generator via HTTP or gRPC through a load balancer.
Load Balancer: Routes requests to healthy generator nodes. Health checks monitor clock drift and lease status. Any node can serve any request; there is no affinity or routing logic.
ID Generator Nodes: Stateless at runtime; each holds a worker ID, a clock reference, and a sequence counter in memory. Horizontally scalable; add nodes to increase throughput.
Coordination Store (ZooKeeper/etcd): Manages the worker ID registry. Accessed only at startup and during lease renewal. A 3-node or 5-node cluster provides fault tolerance.
NTP/Time Sync: Keeps node clocks aligned. Not on the hot path but critical for correctness. Clocks that drift apart cause ordering violations; clocks that jump backward cause duplicate IDs.
These components form clear boundaries: each has a single responsibility (generation, coordination, routing, time sync) and communicates through well-defined interfaces.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
The entire design rests on one insight: if you divide a 64-bit integer into non-overlapping fields, and each node controls a unique subset of one field, then all nodes can generate IDs independently without any runtime coordination.
Bit position: 63 | 62 .............. 22 | 21 ...... 12 | 11 ...... 0
Field: Sign | Timestamp (41) | Worker (10) | Seq (12)
Example: 0 | 1709654400123 | 42 | 7
Sign bit (bit 63): Always 0. Keeps the ID positive in languages that use signed 64-bit integers.
Timestamp (bits 22-62, 41 bits): Milliseconds since the custom epoch (January 1, 2020). 41 bits cover 69.7 years. This field occupies the highest bits, so IDs are naturally sorted by time, a later timestamp always produces a larger ID.
Worker ID (bits 12-21, 10 bits): Uniquely identifies the generator node. Range 0-1023. Assigned once at startup by the coordination store. This field is what eliminates runtime coordination, no two live nodes share a worker ID, so no two nodes can produce the same bit pattern.
Sequence (bits 0-11, 12 bits): Per-millisecond counter, range 0-4095. Resets to 0 when the timestamp advances. Allows each node to generate 4,096 unique IDs within the same millisecond.
Key Insight
GATE: The bit layout eliminates runtime coordination entirely. Timestamp comes from the local clock (no network call). Worker ID was assigned at startup (no runtime lookup). Sequence is a local counter (no shared state). Bitwise OR of these independently-maintained values produces a globally unique result because each field occupies non-overlapping bit positions. This is why the hot path has zero external dependencies.
The sequence counter is the mechanism that allows multiple IDs within the same millisecond from the same node:
if current_ms == last_ms:
sequence = (sequence + 1) & 0xFFF # mask to 12 bits
if sequence == 0:
# overflow: spin-wait for next ms
current_ms = wait_next_ms(last_ms)
else:
sequence = 0
last_ms = current_ms
The mask & 0xFFF (4095) ensures the sequence never exceeds 12 bits. When it wraps to 0, that signals overflow, the node has used all 4,096 slots for this millisecond and must wait.
Fencing token prevents split-brain: when Node A loses its ZooKeeper session, Node B claims the worker ID with a higher token
The coordination store prevents the most dangerous failure mode: two nodes generating IDs with the same worker ID. The mechanism uses leases with fencing tokens:
Lease acquisition: Node creates ephemeral znode under /id-generator/workers/. ZooKeeper assigns a unique path and returns a fencing token.
Lease renewal: Session heartbeats keep the ephemeral znode alive; no explicit renewal needed.
Lease loss: If the node loses its session (partition, GC pause, crash), the znode is deleted after session timeout. The node MUST stop generating the moment it detects session loss.
Fencing token: Each lease grant increments a monotonic counter. Node B claims worker ID 42 with token 18 after Node A's session expires. Node A's stale token 17 is rejected on renewal, preventing the "zombie node" problem.
Common Pitfall
10 worker bits means 1,024 nodes maximum. If you need 4,096 nodes, steal 2 bits from the timestamp field (reducing from 41 to 39 bits, cutting time span from 69.7 years to 17.4 years) or from the sequence field (reducing from 12 to 10 bits, cutting per-ms throughput from 4,096 to 1,024 IDs). Every bit reallocation has a cascading capacity consequence, there are no free bits in a 64-bit budget.
Multiple threads on the same node must not produce duplicate IDs. The solution is a single atomic compare-and-swap (CAS) on the combined (last_timestamp, sequence) state: lock-free, no mutex, no blocking. Under contention, losing threads retry immediately. At 4,096 IDs per millisecond, contention is rare on modern hardware.
Timestamp occupies the highest bits, so IDs from different milliseconds are perfectly ordered regardless of which node generated them. Within the same millisecond, IDs from different workers are interleaved, "roughly sorted," sufficient for feed ordering, event logs, and cursor-based pagination.
Ticket server requires a database write per ID, creating a bottleneck. Snowflake uses local computation with zero external calls.
Ticket server: A MySQL table with AUTO_INCREMENT. Simple, strictly sequential, easy to implement. But every ID is a database write. At 100K IDs per second, you need a database capable of 100K writes per second, or you shard across multiple ticket databases with different auto-increment steps (database 1 generates odd IDs, database 2 generates even). Sharding adds complexity: you need a routing layer, and IDs are no longer globally sequential (only sequential within each shard). If a shard fails, half the ID space is unavailable.
Snowflake: Zero runtime coordination. Each node generates IDs independently using local clock and counter. Throughput scales linearly with nodes. The trade-off: IDs are only roughly sorted (not strictly sequential), and the system depends on synchronized clocks. Clock problems cause uniqueness violations that are harder to detect than a database failure.
When to choose which: Ticket server for systems under 10K IDs per second that need strict sequential ordering (like invoice numbers). Snowflake for systems needing high throughput, decentralized generation, and time-based sorting.
64 bits is a zero-sum budget. Every bit given to one field is taken from another.
More timestamp bits: Extends the time span. Moving from 41 to 43 bits extends from 69.7 years to 278.9 years. Cost: 2 fewer bits for workers or sequence. Useful for systems that must run for decades without format changes.
More worker bits: Supports more nodes. Moving from 10 to 13 bits increases from 1,024 to 8,192 nodes. Cost: 3 fewer bits for timestamp or sequence. Useful for microservice architectures with thousands of independently-deployed services.
More sequence bits: Higher burst capacity. Moving from 12 to 14 bits increases per-millisecond throughput from 4,096 to 16,384 IDs per node. Cost: 2 fewer bits for timestamp or workers. Useful for systems with extreme burst patterns (flash sales, viral events).
Key Insight
Bit allocation is a zero-sum game within 64 bits. Twitter chose 41/10/12 for roughly 70 years, 1K nodes, and 4K IDs per millisecond per node. Discord uses 42/10/12 with a different epoch. Instagram uses 41/13/10, more shards, lower per-shard throughput. Each company optimized for their specific scale profile.
Halt on rollback: Preserves uniqueness absolutely. The node stops generating until the clock recovers. During the halt, availability drops for that node, but load balancers redirect traffic to other nodes.
Continue with offset: Maintains availability by generating IDs with an adjusted timestamp. Risks subtle ordering violations and, in worst case, ID collisions if the offset calculation is wrong. Debugging is extremely difficult because the IDs look valid.
The industry consensus favors halting. A brief availability drop on one node (with traffic redirected to others) is far less costly than silent uniqueness violations that corrupt data across the system.