Design a Unique ID Generator

Dozens of services across several data centres create records all day: orders, messages, payments, log events. Each record needs an ID that is unique across the whole company, fits in a signed 64-bit integer (so it works as a database primary key and in every language), and sorts roughly by creation time so that newest-first queries and time-range scans are cheap.

The busiest services need hundreds of thousands of IDs per second, and an ID must be available in well under a millisecond. Database auto-increment cannot keep up across shards, and random UUIDs are too wide and do not sort.

In 45 minutes, pin down what "unique" and "time-ordered" must mean, compare approaches, design the bit layout, and explain how you assign machine identities and survive clocks that drift or jump.

Sketch on the HLD board, write your answer in the Design doc, and size it with the Estimator. Start the mock interview from the timer for a 45-minute run.

Design Path · Core Building Blocks · problem 7 of 70

Ask before you design. Try answering each yourself, then compare.

1. Must IDs be strictly increasing across the whole company?
   Typical answer

   No. Roughly time-ordered (k-sorted, within a few milliseconds) is enough; strictly increasing is only required within one generator.

2. Must they fit in 64 bits?
   Typical answer

   Yes, a signed 64-bit integer, so the top bit stays 0.

3. Peak rate?
   Typical answer

   Around 300,000 IDs per second across the company, with single services bursting to 50,000.

4. Can there be gaps in the sequence?
   Typical answer

   Yes. Gaps are fine; duplicates are never acceptable.

5. How long must the scheme last?
   Typical answer

   At least 50 years from a custom epoch.

6. Is it a problem if IDs reveal creation time and volume?
   Typical answer

   Acceptable for internal IDs. Public-facing IDs can be obfuscated separately.

7. How many machines will generate IDs?
   Typical answer

   A few hundred today, at most about 1,000 at once.

Requirements

Functional

• Return a new 64-bit ID on request, unique across all generators and data centres.
• IDs are k-sorted by creation time (to within clock skew, a few ms).
• Support batch requests (e.g. 1,000 IDs at once) for bulk loaders.
• Decode an ID into its timestamp and generator for debugging.

Non-functional

• p99 under 1 ms per ID; under 1 microsecond when generated in-process.
• Peak 300k IDs/s company-wide, scaling by adding generators.
• Zero duplicates, even across clock adjustments and machine restarts.
• 99.99% availability with no single coordinator on the request path.

Out of scope

• Globally strict ordering across all generators.
• Human-friendly short codes for URLs (a separate encoding layer).

Back-of-the-envelope estimates

• Rate: 5 B IDs a day ≈ 58,000 per second on average, ~300,000 at peak.
• Bit budget: 41 bits of milliseconds cover 2⁴¹ ms ≈ 69.7 years from a custom epoch. 10 bits allow 1,024 generators. 12 bits give 4,096 IDs per millisecond per generator, i.e. ~4.1 M per second each.
• Headroom: one generator alone could cover 13× the company-wide peak, so the number of generators is decided by availability and locality, not throughput.
• State: each generator holds only its worker ID, last timestamp and sequence: a few bytes, nothing to store.

Throughput is easy; the driving constraints are the 64-bit budget, unique worker IDs, and clock behaviour.

API

// in-process library (preferred)
ids.next() -> int64
ids.nextBatch(n) -> int64[]

// network service for languages without the library
GET /v1/ids?count=100 -> {ids: [...]}
GET /v1/ids/{id}/decode -> {timestamp, workerId, sequence}

Embedding the generator as a library avoids a network hop per ID; the network service exists for callers that cannot embed it and hands out batches to amortise the round trip.

Data model

The ID layout is the data model: 0 | 41-bit ms since 2024-01-01 | 10-bit worker | 12-bit sequence. The worker field can be split into 3 bits of data centre and 7 bits of machine if each region assigns its own numbers.

The only stored state is the worker ID lease table in a strongly consistent coordination store: worker_leases(worker_id PK, holder, expires_at, last_seen_ms). A consensus-backed store fits because this table is tiny and correctness (no two holders) matters far more than speed. Recording last_seen_ms lets a restarted generator refuse to issue IDs older than its predecessor's last timestamp.

High-level design

Callers usually embed the generator library; others call the ID service through an internal load balancer, and each generator instance answers locally from memory.

Startup: a generator asks the coordination store for a free worker ID and takes a lease on it (say 30 seconds, renewed every 10). It reads the last timestamp recorded for that worker and waits until its own clock is past it. It refuses to serve until its clock is synchronised with the time source.

Generating: on each request the generator reads the current millisecond. If it is a new millisecond, the sequence resets to 0; if it is the same one, the sequence increments; if 4,096 IDs have already been used, it spins until the next millisecond. It then packs timestamp, worker and sequence into one 64-bit integer. No network call, disk write or lock across machines is involved, so this takes well under a microsecond.

Generators publish clock offset and sequence exhaustion metrics to a monitor, and the caller writes the ID as the primary key of its own database row.

Open the HLD board and press Reference to see the architecture diagram.

Deep dives

Comparing the options

Auto-increment per database gives short, ordered IDs but becomes a write bottleneck and breaks under sharding; using different offsets per shard (shard k issues k, k+N, ...) works but makes adding shards painful. Random UUIDv4 needs no coordination but is 128 bits and random, which scatters inserts across B-tree pages. Time-ordered UUIDs (v7) fix ordering but are still 128 bits. A central counter that leases blocks of 10,000 IDs is simple and compact but IDs from different servers interleave poorly in time. A timestamp + worker + sequence layout meets all constraints at once, at the cost of depending on clocks and unique worker IDs.

Assigning worker IDs safely

A duplicate worker ID is the only way this scheme produces duplicate IDs, so assignment must be airtight. Static config breaks with autoscaling. Instead, generators take a lease on a worker ID from a consensus store. The danger is a generator that pauses (a long GC or a VM freeze), loses its lease, and resumes issuing IDs while a new holder has the same number. Defend by checking the lease's local expiry before every batch and stopping if it might have lapsed, keeping a safety margin between lease expiry and reassignment, and reusing a freed ID only after a quarantine period longer than any plausible pause.

Surviving clock problems

Clocks drift and NTP corrects them, sometimes by stepping backwards. If the clock goes back, a generator could reissue a timestamp it already used. Rules: always remember the last timestamp issued; for small backward steps (a few ms), keep using the last timestamp and the sequence until real time catches up; for large ones, refuse to serve and alert, letting callers fail over to another generator. Configure time sync to slew (gradually speed up or slow down) rather than step, and smear leap seconds. After a restart, wait until the clock passes the last persisted timestamp for that worker.

What ordering actually means

IDs from one generator are strictly increasing. Across generators, ordering is only as good as clock agreement: with 2 ms of skew, an ID created later on one machine can sort before one created earlier on another. That is enough for newest-first feeds and time-bucketed storage, but not for causality, so a system that needs "B happened after A" must carry that explicitly. Within one millisecond, lower worker IDs always sort first, which slightly biases order but is harmless. If an ID is exposed publicly, competitors can estimate volume from it; encrypting it with a keyed permutation hides that while keeping uniqueness.

Failure modes

• If the coordination store is down, running generators keep serving on their existing leases; only new generators cannot start.
• If a generator's clock jumps backwards by more than a few ms, it stops serving and alerts; the load balancer or library fails over to another worker.
• If a generator is paused past its lease and resumes, the pre-issue lease check makes it stop before it can duplicate a reassigned worker ID.
• If a burst exceeds 4,096 IDs in a millisecond on one worker, it waits for the next millisecond, adding under 1 ms of latency rather than failing.

Core algorithm in code

import threading, time

EPOCH_MS = 1_704_067_200_000          # 2024-01-01 UTC, our custom epoch
WORKER_BITS, SEQ_BITS = 10, 12
MAX_WORKER, MAX_SEQ = (1 << WORKER_BITS) - 1, (1 << SEQ_BITS) - 1


class ClockMovedBack(Exception):
    pass


class IdGenerator:
    """64-bit ids: 1 sign bit (0) | 41 bits ms since epoch | 10 bits worker | 12 bits sequence."""
    def __init__(self, worker_id, clock=lambda: int(time.time() * 1000), max_backstep_ms=5):
        if not 0 <= worker_id <= MAX_WORKER:
            raise ValueError("worker id out of range")
        self.worker, self.clock, self.max_back = worker_id, clock, max_backstep_ms
        self.last_ms, self.seq = -1, 0
        self.lock = threading.Lock()

    def next_id(self):
        with self.lock:
            now = self.clock()
            if now < self.last_ms:
                if self.last_ms - now > self.max_back:
                    raise ClockMovedBack("clock went back %d ms" % (self.last_ms - now))
                now = self.last_ms                    # small step back: keep using the last ms
            if now == self.last_ms:
                self.seq = (self.seq + 1) & MAX_SEQ
                if self.seq == 0:                     # 4096 ids used this ms: wait for the next one
                    while now <= self.last_ms:
                        now = self.clock()
            else:
                self.seq = 0
            self.last_ms = now
            return ((now - EPOCH_MS) << (WORKER_BITS + SEQ_BITS)) | (self.worker << SEQ_BITS) | self.seq


def decode(i):
    return {"ms": (i >> 22) + EPOCH_MS, "worker": (i >> 12) & MAX_WORKER, "seq": i & MAX_SEQ}


gen = IdGenerator(worker_id=17)
ids = [gen.next_id() for _ in range(200_000)]
print("sample id:", ids[0], decode(ids[0]))
print("200k ids unique:", len(set(ids)) == len(ids), "| strictly increasing:", all(a < b for a, b in zip(ids, ids[1:])))
print("fits in signed 64-bit:", max(ids) < 2 ** 63)
print("timestamp space lasts %.1f years" % ((1 << 41) / 1000 / 3600 / 24 / 365.25))

fake = [1_800_000_000_000]
g2 = IdGenerator(worker_id=3, clock=lambda: fake[0])
a = g2.next_id(); fake[0] -= 2; b = g2.next_id()
print("2 ms clock step back tolerated, still ordered:", a < b)
fake[0] -= 50
try:
    g2.next_id()
except ClockMovedBack as e:
    print("50 ms step back refused:", e)

Trade-offs

• Embedding the generator as a library removes a network hop but spreads worker ID leases across thousands of processes.
• More worker bits support more generators but shrink the sequence or timestamp space.
• Refusing to serve on a large clock jump preserves uniqueness but reduces availability; callers must retry on another generator.
• Time-prefixed IDs sort well and help B-tree locality but concentrate inserts on the newest index page and leak creation time.

What a strong answer shows

• Compares at least three approaches against 64-bit size, ordering and throughput.
• Produces a concrete bit layout and checks its lifetime and per-ms capacity.
• Explains how worker IDs are assigned and protected against duplicates.
• Handles backward clock jumps and restarts explicitly.
• Is precise about the ordering guarantee (per generator strict, global approximate).

Mistakes to avoid

• Proposing UUIDv4 without noticing it violates the 64-bit and ordering requirements.
• Using a single central counter service on every request, creating a bottleneck and single point of failure.
• Hard-coding worker IDs in config files in an autoscaling fleet.
• Ignoring the clock moving backwards.
• Claiming IDs are globally strictly increasing.

Follow-ups to expect

• How would you make IDs non-guessable for public URLs? (Apply a keyed reversible permutation such as a small Feistel cipher, then base62-encode.)
• What changes if you need 10 million IDs per second on one service? (More workers per service, or fewer timestamp bits with coarser time units.)
• How would you shard a database by these IDs? (Hash the ID, or use the worker bits; time prefix alone would create hot shards.)
• What happens in 69 years? (Migrate to a new epoch with a version bit, or move to 128-bit IDs well beforehand.)

Practice next