Distributed ID generation

The problem: who counts?

On one Postgres server, IDs are easy: bigserial counts 1, 2, 3. With 256 logical shards, each shard's counter starts at 1 and they collide. Keeping one central counter brings back a single machine that every insert depends on.

What we usually want from an ID:

• Unique, across every shard and server, forever.
• Generated without coordination, or with very little, so it's fast and never blocks.
• Roughly sortable by time, so recent rows sit together in an index and "newest first" is cheap.
• Small: 64 bits fits a bigint and most languages; 128 bits is twice the index.
• Sometimes unguessable, so IDs don't reveal how many rows exist or let anyone list them.

No scheme gives all of these. Here are the common ones.

Ticket servers and blocks

The simplest fix keeps a counter, but takes it off the hot path. A ticket server is a tiny database whose only job is to return the next number. Two of them, one handing out odd numbers and one even, survive the loss of either.

Cheaper still, each app server reserves a block of IDs at once and hands them out from memory:

-- reserve IDs 1,000 at a time; the app uses next - 1000 up to next - 1
UPDATE id_blocks SET next = next + 1000 WHERE name = 'links' RETURNING next;

One round trip per thousand IDs. A crash wastes the rest of a block (gaps are fine), and IDs from different servers interleave, so order is only rough.

UUIDs

A UUID is 128 bits, generated anywhere with no coordination. Version 4 is entirely random, which makes it unique and unguessable, but as a primary key every insert lands at a random place in the B-tree, touching a different page each time and keeping the whole index hot in memory. UUIDv7, standardised in 2024, puts a 48-bit millisecond timestamp first and fills the rest with random bits. New IDs sort after old ones, so inserts go to the right-hand edge of the index, like an auto-increment key.

Snowflake: 64 bits, no coordination

Twitter's Snowflake packs three fields into one 64-bit integer:

| 1 unused | 41 bits: ms since a custom epoch | 10 bits: machine | 12 bits: sequence |

• 41 bits of milliseconds last about 69 years from the chosen epoch.
• 10 bits of machine number allow 1,024 generators, each assigned a unique number at deploy time.
• 12 bits of sequence allow 4,096 IDs per machine per millisecond.

Each machine generates IDs alone, and because the timestamp comes first, IDs sort by time across machines (within the clocks' disagreement). A generator in TypeScript:

const EPOCH = 1735689600000n; // 2025-01-01 UTC, Snip's own epoch
const MAX_SEQ = 4095n;

export class Snowflake {
  private last = -1n;
  private seq = 0n;

  constructor(private machine: bigint) {
    if (machine < 0n || machine > 1023n) throw new Error("machine must be 0–1023");
  }

  next(): bigint {
    let now = BigInt(Date.now());
    if (now < this.last) {
      // The clock went backwards. Issuing IDs now could repeat old ones, so refuse.
      throw new Error(`clock moved back ${this.last - now} ms`);
    }
    if (now === this.last) {
      this.seq = (this.seq + 1n) & MAX_SEQ;
      if (this.seq === 0n) {
        // 4,096 IDs used this millisecond: wait for the next one.
        while (now <= this.last) now = BigInt(Date.now());
      }
    } else {
      this.seq = 0n;
    }
    this.last = now;
    return ((now - EPOCH) << 22n) | (this.machine << 12n) | this.seq;
  }
}

Two things can go wrong, and both are handled above: the clock moving backwards (refuse, rather than risk a duplicate) and running out of sequence numbers within one millisecond (wait). Machine numbers must also never be reused by two running generators at once, which is a deployment problem, not a code one.

Snip's short codes

Snip's codes face one more constraint: people type and share them, so they must be short. A Snowflake ID in base62 (digits plus upper and lower case letters) is 11 characters, longer than Snip wants. And a counter in base62 is short but guessable: anyone could walk through x7Kp, x7Kq, x7Kr and find every link, including private ones.

So Snip draws random codes and lets the database catch the rare collision:

• 62⁷ is about 3.5 trillion seven-character codes. Today Snip expects 600 million links over five years, so a new random code collides with an existing one about 0.02% of the time.
• At a hundred times the traffic, 60 billion links, that rises to about 1.7%. Snip moves to eight characters (about 218 trillion), back to 0.03%.
• The code is the shard key (05.01 Sharding: range, hash, directory), so its uniqueness is checked by the one shard that owns it: insert, and on a primary key conflict, draw again.

INSERT INTO links (code, long_url, owner_id) VALUES ($1, $2, $3)
ON CONFLICT (code) DO NOTHING
RETURNING code; -- no row back means the code was taken: draw another and retry

Snip's other IDs, such as click events, use Snowflake-style 64-bit IDs, where size and time order matter and nobody types them.

Recap

Interview questions