Design a Unique ID Generator

Why auto-increment dies under sharding, how Snowflake ids are laid out, and what clock skew does to a sortable id.

Syntaxid = ((ms - EPOCH) << 22n) | (nodeId << 12n) | sequence // 41 + 10 + 12 bits

Every row needs an identifier. On one database, an auto-increment column is the right answer and you should use it. Once the data is sharded it stops being an answer: each shard's counter starts at 1, so ids collide across shards, and a single shared counter puts a coordinated round trip in front of every insert.

The options

Scheme	Shape	Cost
Random UUID (v4)	128 bits, no coordination	Not sortable; random inserts scatter writes across a B-tree index
Snowflake	64 bits: 41 timestamp, 10 node, 12 sequence	Compact and sortable; needs a node id registry and a trustworthy clock
UUIDv7	48-bit millisecond prefix, then random	Sortable with no registry, but 128 bits and no per-node sequence
Segment allocation	Blocks of ids from a counter table	One round trip per block; the counter table is a dependency

Clock skew

A Snowflake id is unique only because a node never issues two ids for the same millisecond and sequence number. If the wall clock steps backwards — an NTP correction, a VM migration, an operator with a shell — the node re-enters a millisecond it has already spent and starts producing duplicates. Correct implementations refuse to issue ids until the clock catches up, which means the generator is unavailable for the duration. Choose that failure consciously; the alternative is duplicate primary keys you discover much later.

Sortable, to a point

Time-prefixed ids sort by creation time only to the resolution of the timestamp. Within one millisecond, ordering across nodes is arbitrary. They make excellent index keys and terrible evidence about which of two near-simultaneous events happened first.

Example

// Snowflake generator. Layout of the 64 bits:
//   1 unused sign bit | 41 bits milliseconds since a custom epoch
//   | 10 bits node id | 12 bits sequence
// 41 bits of milliseconds is about 69 years from the epoch; 10 bits is 1024
// nodes; 12 bits is 4096 ids per millisecond per node.
const EPOCH = 1704067200000n;          // 2024-01-01T00:00:00Z. Chosen once, forever.
const NODE_BITS = 10n;
const SEQ_BITS = 12n;
const MAX_NODE = (1n << NODE_BITS) - 1n;   // 1023
const MAX_SEQ = (1n << SEQ_BITS) - 1n;     // 4095
// `1n << 10n` is shorthand for 2n ** 10n: a left shift by k multiplies by 2^k.

export function createGenerator(nodeId) {
  const node = BigInt(nodeId);
  if (node < 0n || node > MAX_NODE) throw new RangeError(`nodeId must be 0..${MAX_NODE}`);

  let lastMs = -1n;
  let seq = 0n;

  return function nextId() {
    let ms = BigInt(Date.now());

    if (ms < lastMs) {
      // The wall clock moved backwards. Reusing a millisecond we have already
      // issued sequence numbers for would produce duplicate ids, so refuse.
      // Alert on this: it means NTP, virtualisation or a human, and it will not
      // fix itself quietly.
      throw new Error(`clock moved back ${lastMs - ms}ms; refusing to issue ids`);
    }

    if (ms === lastMs) {
      seq = (seq + 1n) & MAX_SEQ;
      if (seq === 0n) {
        // All 4096 slots in this millisecond are spent. Spin to the next one;
        // at this rate the wait is bounded by under a millisecond.
        while (BigInt(Date.now()) <= lastMs) { /* busy wait */ }
        ms = BigInt(Date.now());
      }
    } else {
      seq = 0n;
    }

    lastMs = ms;

    const id = ((ms - EPOCH) << (NODE_BITS + SEQ_BITS)) | (node << SEQ_BITS) | seq;
    // Shift the timestamp left by 22 bits (10 + 12) and OR the other fields in.
    // Return a string: this value does not fit in a JavaScript number.
    return id.toString();
  };
}

// The node id has to be unique and is the part people get wrong. Derive it from
// something the platform guarantees - a StatefulSet ordinal, a ZooKeeper or
// etcd lease, a row claimed at boot - never from a random number or a hash of
// the hostname, both of which collide.
export const nextId = createGenerator(Number(process.env.NODE_ORDINAL));

When to use it

Pick a primary key for a table that is about to be split across sixteen shards.
Replace auto-increment ids in an API where two regions both accept writes.
Give events a key that sorts by creation time so you can range-scan a day without a separate timestamp index.
Diagnose duplicate primary keys appearing after a host's clock was corrected.

More examples

UUIDv7, when you do not want a node registry

The pragmatic default for a service that is sharded but not generating millions of ids per second. Reach for it when assigning and policing unique node ids is more operational work than the 64 extra bits are worth - which is most of the time. The time prefix is what matters: inserts land at the right-hand edge of the index instead of scattering across it the way v4 does.

// UUIDv7 per RFC 9562 section 5.7 (published May 2024; it obsoletes RFC 4122,
// which had no time-ordered random UUID). Layout:
//   48 bits unix_ts_ms | 4-bit version (7) | 12 bits random
//   | 2-bit variant (0b10) | 62 bits random
// Node's crypto.randomUUID() produces v4 only, so build v7 by hand.
import { randomFillSync } from 'node:crypto';

export function uuidv7(now = Date.now()) {
  const b = Buffer.alloc(16);
  randomFillSync(b);                 // fill all 16 bytes with randomness first
  b.writeUIntBE(now, 0, 6);          // bytes 0-5: big-endian milliseconds
  b[6] = (b[6] & 0x0f) | 0x70;       // high nibble of byte 6 = version 7
  b[8] = (b[8] & 0x3f) | 0x80;       // top two bits of byte 8 = variant 0b10
  const h = b.toString('hex');
  return `${h.slice(0, 8)}-${h.slice(8, 12)}-${h.slice(12, 16)}-${h.slice(16, 20)}-${h.slice(20)}`;
}

// Store it as 16 bytes, not as 36 characters of text. In Postgres that is the
// uuid type; in MySQL, BINARY(16). CHAR(36) more than doubles the size of every
// index that contains it.
//   ALTER TABLE events ADD COLUMN id uuid PRIMARY KEY;

// What you give up against Snowflake: 128 bits instead of 64, and no sequence
// counter, so two ids minted in the same millisecond on the same host sort in
// random order. What you gain: no node id to assign, and no generator to
// operate.

Segment allocation from the database you already have

Use this when ids must stay compact and human-quotable, and when you would rather depend on the database you already run than on a new generator service and a node id scheme. Flickr's ticket servers and Instagram's sharded id scheme are both variants of it. The gap behaviour is the thing to confirm with whoever owns the numbering before you ship.

// Ticket-server style allocation: one row per sequence, bumped in blocks. One
// round trip buys a thousand ids, so the database is touched once per thousand
// inserts instead of once per insert, and ids stay small dense integers.
//
// CREATE TABLE id_segments (name text PRIMARY KEY, next bigint NOT NULL DEFAULT 1);
const BLOCK = 1000;
const pools = new Map();   // name -> { next, end }

export async function nextId(db, name) {
  let pool = pools.get(name);
  if (!pool || pool.next >= pool.end) {
    // A single atomic UPDATE. The row lock serialises concurrent allocators,
    // and RETURNING hands back the value after the increment, so this block is
    // [newNext - BLOCK, newNext).
    const { rows } = await db.query(
      `UPDATE id_segments SET next = next + $2 WHERE name = $1 RETURNING next`,
      [name, BLOCK],
    );
    if (rows.length === 0) throw new Error(`no id segment named ${name}`);
    const end = Number(rows[0].next);
    pool = { next: end - BLOCK, end };
    pools.set(name, pool);
  }
  return pool.next++;
}

// The trade-off: a process that restarts abandons the rest of its block, so the
// sequence has gaps. If gaps are unacceptable - an invoice number a regulator
// reads - you cannot cache blocks, and you are back to one round trip per id.
// Also note that a monotonic id leaks volume: a competitor who signs up twice a
// day can read your growth rate off the ids.

Choosing a primary key, with the index cost made explicit

Shows what you are actually buying with a sortable id: index locality on write, a free time range scan on read, and a debugging affordance where any id tells you when it was created. Reach for this argument when someone proposes switching a hot table from bigint to random UUID for convenience - the convenience is real, and so is the write amplification once the index stops fitting in memory.

// Why id choice is a storage decision, not a naming decision. In a clustered
// index (InnoDB's primary key, or any index on the key) rows are stored in key
// order, so where a new key lands determines what the disk does.
//
// Random v4 UUID: every insert lands in a different page. The working set is
// the whole index, pages split constantly, and the buffer pool thrashes once
// the index exceeds RAM.
//
//   CREATE TABLE events (id BINARY(16) PRIMARY KEY, body JSON);   -- v4: scattered
//
// Time-ordered id (Snowflake or v7): inserts land at the right-hand edge. The
// hot pages are the newest ones, which are the ones already in memory.
//
//   CREATE TABLE events (id BIGINT UNSIGNED PRIMARY KEY, body JSON);  -- Snowflake

// A time-ordered key also gives you range queries for free, because the
// timestamp is a prefix of the key:
const since = (BigInt(Date.parse('2026-03-01T00:00:00Z')) - EPOCH) << 22n;
const until = (BigInt(Date.parse('2026-04-01T00:00:00Z')) - EPOCH) << 22n;
// SELECT * FROM events WHERE id >= ? AND id < ?   -- a range scan, no date index
const params = [since.toString(), until.toString()];

// And recovering the timestamp from an id is pure arithmetic, which is useful
// in support tooling:
export function idToDate(id) {
  return new Date(Number((BigInt(id) >> 22n) + EPOCH));
}

Discussion

Be the first to comment on this lesson.

The options

Clock skew

Sortable, to a point

Example

When to use it

More examples

UUIDv7, when you do not want a node registry

Segment allocation from the database you already have

Choosing a primary key, with the index cost made explicit

Related

Discussion