Design: a unique ID generator

The prompt

"Design a unique ID generator" looks like a one-liner (use a UUID) until the interviewer adds constraints: 64 bits, sortable by time, very fast, and no single machine that everything depends on.

1. Requirements

• Unique, everywhere, forever.
• 64 bits, so they fit a bigint column and are cheap to index.
• Roughly time-ordered ("k-sorted"): IDs made later are usually larger, so new rows land at the end of a B-tree index (04.02 Indexes and B-trees) and IDs sort by time without a separate column.
• Fast and available: 500,000 a second, under a millisecond, no single point of failure.
• Not required: being unguessable (these aren't Snip's short codes) or strictly sequential.

2. Options

 1 bit  | 41 bits                       | 10 bits        | 12 bits
 unused | milliseconds since 2025-01-01 | worker number  | sequence within the millisecond

 41 bits of milliseconds ≈ 69 years · 1,024 workers · 4,096 IDs per worker per millisecond

One worker can make about 4 million IDs a second, so 500,000 a second needs a handful. The real limits are the 1,024 worker numbers and the clock.

3. High-level design

4. Deep dives

CREATE TABLE worker_ids (id int PRIMARY KEY, holder text, expires_at timestamptz NOT NULL DEFAULT '-infinity');
INSERT INTO worker_ids (id) SELECT g FROM generate_series(0, 1023) g;

export async function claimWorkerId(db: pg.Pool, holder: string, leaseSeconds = 30): Promise<number | null> {
  const { rows } = await db.query(
    `UPDATE worker_ids SET holder = $1, expires_at = now() + make_interval(secs => $2)
     WHERE id = (SELECT id FROM worker_ids WHERE expires_at < now()
                 ORDER BY id LIMIT 1 FOR UPDATE SKIP LOCKED)
     RETURNING id`,
    [holder, leaseSeconds],
  );
  return rows[0]?.id ?? null;
}

export async function renewWorkerId(db: pg.Pool, id: number, holder: string, leaseSeconds = 30) {
  const { rowCount } = await db.query(
    `UPDATE worker_ids SET expires_at = now() + make_interval(secs => $3)
     WHERE id = $1 AND holder = $2 AND expires_at > now()`,
    [id, holder, leaseSeconds],
  );
  return rowCount === 1; // false: the lease is gone, so stop generating IDs at once
}

Tested on Postgres 16 with 2-second leases: 20 processes claiming at the same moment got 20 different numbers. Renewal by the holder succeeded and by any other name failed. After the lease ran out, the old holder's renewal failed, and a new process claimed the freed number. The lease time comes from the database's clock, so the processes' own clocks don't decide who holds what.

Library or service? A library has no network hop and no new service to run; it needs the lease table and disciplined clocks on every machine. A central ID service (a few instances, each with its own worker number) suits clients in many languages, at the cost of a call per ID or per block of IDs. Snip uses the library.

5. Wrap-up

What breaks first: worker numbers, if thousands of short-lived processes each hold one (10 bits is 1,024); widen the worker field and narrow the sequence. Then ordering across machines: IDs are only roughly ordered, since two machines' clocks differ by a few milliseconds, so never use them to decide which of two events happened first (08.05 Clocks and ordering).

Recap

Interview questions