System Design

Unique ID Generator

Design a distributed unique ID generation service like Twitter Snowflake.

Functional requirements

• Generate globally unique numeric IDs on demand for hundreds of internal services (e.g., tweets, messages, orders).
• IDs must be roughly sortable by creation time (k-sortable): IDs generated later should compare greater than IDs generated earlier, within a small tolerance window.
• IDs must fit in a 64-bit integer so they can be stored in a BIGINT column and serialized efficiently.
• Callers can obtain IDs either via a network call to the ID service or via an embedded client library: the design must pick one (or support both) and justify it.
• Given an ID, it must be possible to extract its approximate creation timestamp without a lookup.

Non-functional requirements

• Uniqueness is a hard invariant: two IDs must never collide, even across datacenter failover, process restarts, or clock anomalies; prefer refusing to issue an ID over issuing a duplicate.
• ID generation latency must be sub-millisecond at p99 (generation itself; network hop excluded if a service model is chosen).
• The generator must have no single point of failure: loss of any node, or an entire datacenter, must not halt ID issuance globally.
• No coordination on the hot path: generating an ID must not require a synchronous call to a central database or consensus system per ID.
• Ordering guarantee is explicitly best-effort across nodes (rough time-ordering), but must be strictly monotonic per generator node.

Scaling & constraints

• Peak demand: 10 million IDs generated per second across the fleet at global peak; average is ~1 million/sec.
• The fleet spans 5 datacenters, each running up to 1,024 generator instances (VMs/containers that autoscale and restart frequently).
• A single hot service (e.g., messaging) can burst to 500,000 IDs/sec from one datacenter for several minutes.
• The ID scheme must remain valid for at least 50 years from epoch without exhausting the 64-bit space.
• Server clocks are NTP-synchronized with typical drift under 10 ms, but backwards jumps of up to a few seconds have been observed after NTP corrections and VM live-migrations.
• Traffic grows ~40% year over year.

Out of scope

• Cryptographic unguessability of IDs (assume IDs may be enumerable; that's acceptable).
• Human-readable or vanity IDs (URL slugs, short codes).
• Authentication/authorization of callers and billing/quota enforcement.
• Storage or indexing of the objects the IDs identify.