Design a Unique ID Generator

EasyCore Building BlocksSnowflake IDsClock SkewCoordinationSharding

Problem

Many services in a large system need IDs for new records such as orders, messages, and posts. Design a generator that produces IDs that are globally unique across all data centers, fit in 64 bits so they work as database primary keys, and are roughly ordered by creation time so that newer records sort after older ones. The system must issue up to 1 million IDs per second across the fleet, and ID generation must keep working when a single machine or data center fails.

  • Must IDs be strictly increasing, or is rough time order (within a few milliseconds) enough?
  • Is 64 bits a hard limit, or could we use 128-bit IDs?
  • Can IDs be exposed to users, and is it a problem if they reveal creation time or volume?
  • How many data centers and generator machines do we expect over the next 10 years?
  • Is generation done in a separate service, or can it be a library inside each application?
  • What is the latency budget per ID?

Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.

  • Return a new ID that is unique across every data center and machine.
  • IDs are 64-bit integers.
  • IDs sort roughly by creation time.
  • Allow extracting the creation timestamp from an ID for debugging and partition pruning.
  • Support requesting a batch of IDs in one call.

Items in bold are existing requirements. The rest are suggestions. Confirm with the interviewer whether they are relevant first.

  • Generate up to 1 million IDs per second across the fleet.
  • Stay available when a machine or an entire data center fails.
  • Generate an ID in under 1 ms, with no network call on the hot path when used as a library.
  • Last at least 50 years before the ID space runs out.
  • Never issue a duplicate, even after restarts or clock adjustments.

Each generator instance builds IDs locally from three parts: a millisecond timestamp, a worker ID unique to that instance, and a per-millisecond sequence number. Worker IDs are leased from a coordination service at startup, which is the only time coordination is needed. Because no two instances share a worker ID and each instance never reuses a (timestamp, sequence) pair, IDs are unique without any per-ID communication.

Loading diagram...

Startup. When a process starts, the generator library connects to the coordination service and claims a free worker ID under a session lease. It also records the last timestamp it used (if any) so it never issues IDs for a time it has already used.

Generate an ID. The application calls nextId(). The library reads the current time in milliseconds since a custom epoch. If the time equals the last timestamp, it increments the sequence; if the sequence overflows, it waits for the next millisecond. If the time moved forward, it resets the sequence to zero. It then packs timestamp, worker ID, and sequence into one 64-bit integer.

Clock moves backward. If NTP steps the clock backward by a few milliseconds, the library waits until the clock catches up to the last timestamp. For a larger jump it refuses to issue IDs and raises an alert, since waiting seconds would stall callers.

Shutdown or crash. The worker ID lease expires when the session ends, and the ID is not handed to another process until a grace period has passed, which prevents two live processes from sharing it.

The bit layout that makes IDs unique and time ordered.

Diagram

Loading diagram...

Data Model

  • id = (timestampMs - EPOCH) << 22 | workerId << 12 | sequence

Scalability

41 bits of milliseconds cover about 69 years from the custom epoch. 10 bits allow 1,024 concurrent workers, and 12 bits allow 4,096 IDs per millisecond per worker, which is over 4 million per second per worker. The fleet target of 1 million per second needs only a handful of workers.

Tradeoffs

The bit split is tunable: a system with few machines but very bursty traffic can move bits from the worker field to the sequence. Keeping the sign bit zero means IDs stay positive in languages without unsigned integers, such as Java.

Code that runs inside each application process and produces IDs without network calls.

  • A small library per language (Java, Go, Python), or a sidecar process that exposes a local socket.

API

  • nextId() -> int64
  • nextIds(n) -> int64[] for batch inserts.
  • timestampOf(id) -> time for debugging.

Scalability

Generation is a few arithmetic operations under a lock, so a single instance easily produces hundreds of thousands of IDs per second. Adding application instances adds generation capacity linearly, limited only by the 1,024 worker IDs.

Tradeoffs

Generating locally avoids a network round trip per ID and removes a central point of failure. The cost is that every language needs a correct implementation, which is why the ID service exists for clients that cannot embed the library.

Assigns each running generator a unique worker ID.

  • ZooKeeper or etcd, using ephemeral nodes or leases with a TTL.

Data Model

  • Key /idgen/workers/<workerId> with value { host, pid, leasedAt }, held by a lease that the process renews every few seconds.

Scalability

The coordinator is touched only at startup and for lease renewals, so a three or five node cluster handles thousands of workers. Each data center has its own range of worker IDs (the 5 bit data center field), so a data center can keep assigning IDs from its own range even if it loses contact with the others.

Tradeoffs

Hardcoding worker IDs in config is simpler but breaks with autoscaling and container rescheduling, and a copy-paste mistake silently causes duplicates. Deriving the ID from the IP address can collide after the hash is reduced to 10 bits. A lease-based registry costs a dependency at startup but makes duplicate worker IDs impossible while leases are honored.

Protects uniqueness and ordering when system clocks drift or jump.

  • NTP or chrony configured to slew (gradually adjust) rather than step the clock.
  • Monotonic time source combined with a persisted last-used timestamp.

Scalability

Clock checks are in-process comparisons and add no measurable cost.

Tradeoffs

Ordering is only as good as clock agreement across machines, typically a few milliseconds, so IDs from different workers are roughly but not strictly ordered. Strict global ordering would require a central sequencer, which caps throughput and becomes a single point of failure. Rough ordering is enough for sorting feeds and for B-tree index locality, which is why it is the requirement.

A thin network service for clients that cannot embed the library, such as legacy systems or languages without an implementation.

  • A small gRPC or HTTP service that wraps the generator library, deployed in every data center.

API

  • GET /ids?count=n returns { ids: [...] }, with count capped at 1,000.

Scalability

Each instance holds its own worker ID, so instances scale horizontally behind a load balancer. Clients request IDs in batches and keep a small local buffer, which amortizes the network round trip.

Tradeoffs

Random UUIDv4 values need no service at all but use 128 bits and are randomly ordered, which fragments database indexes and breaks the 64-bit requirement. UUIDv7 fixes ordering but is still 128 bits. A single database auto-increment counter is strictly ordered but is a bottleneck and a single point of failure. Leasing ranges of IDs from a database (for example 1,000 at a time) is a reasonable fallback when dense IDs matter more than time ordering. The service exists only as a compatibility layer, so most traffic stays on the local library path.

Related questions