Module P-3·26 min read

Auto-increment vs UUIDv4 vs UUIDv7/ULID vs Snowflake — why random keys shred B-tree page locality, and what a monotonic public ID leaks.

JJS

Written by Jatin Jain Saraf · Senior Software Engineer

Module P-3 — Primary Keys and Distributed ID Generation

Q: A team migrates a 500-million-row Postgres table's primary key from `bigint` identity to UUIDv4. Insert latency looks unchanged, but over the following weeks WAL volume roughly triples, replica lag becomes routine, and the primary key index grows to nearly double the size its row count justifies. What is the dominant mechanism?

Random keys scatter inserts across every leaf, so the set of pages being written becomes the whole index rather than a few right-edge pages: most inserts now miss the buffer pool, splits happen mid-tree and leave pages half-full, and with `full_page_writes` on, each first touch of a page after a checkpoint drags a full 8 KB page image into the WAL to record a small row. — This is the module's central mechanism, and it is Module F-2's access-pattern claim in reverse: same insert, same complexity class, different physical pattern. Full-page writes are what make the WAL figure so much larger than key width alone predicts — a ~100-byte row can cost an 8 KB page image whenever it touches a page not yet modified this checkpoint cycle. The index growth is mid-tree splits settling at roughly 50–70% fill, where ascending keys pack leaves close to full thanks to Postgres's special handling of rightmost splits. Option B is the near-miss: the width increase is real and does contribute, but eight extra bytes per entry cannot triple WAL volume, and it explains none of the fill-factor loss. Option A misplaces the cost — UUID generation is cheap and happens outside the database. Option C describes a mechanism that does not exist; a `REINDEX` does compact the index, but the bloat returns because the insert pattern causing it has not changed.

Q: A sharded service generates Snowflake IDs on every node. After an NTP correction steps one node's wall clock back by ~400 ms, that node starts rejecting writes with a "clock regression" error. An engineer proposes deleting the check so writes continue. What happens, and why is the check there?

The timestamp is the high-order component and uniqueness depends on it never moving backwards. Across the rewound window the node re-issues (timestamp, machine ID, sequence) triples it has already used, producing duplicate primary keys. Halting is the deliberate trade: a brief write outage on that node, chosen because duplicate keys spread through logs, caches, and downstream systems are effectively impossible to clean up. — Snowflake's uniqueness argument is that the triple of timestamp, machine ID, and sequence is never repeated, and that rests entirely on the wall clock being monotonic — which NTP step corrections do not guarantee. Rewind 400 ms and the generator walks back over sequence space it has already issued. The module names the trade explicitly: refusing to mint IDs makes the node briefly unavailable for writes, which is recoverable, whereas duplicate keys referencing two different entities are not. Option A inverts the design — the sequence is 12 bits and resets whenever the millisecond changes, so it provides uniqueness *within* a millisecond, not across a rewind. Option C names a genuine and serious Snowflake failure mode, since the module calls machine-ID assignment a real coordination problem, but it is a different one and would not correlate with a clock step. Option D misreads the range: 41 bits of milliseconds is roughly 69 years, and overflow would not present as a backwards step.

Q: A competitor publishes an accurate estimate of a company's monthly order volume, derived from the IDs in two invoice URLs a month apart. Separately, a scraper has been walking `/invoices/{id}` by decrementing the number. Which response addresses both, and what does it cost?

Keep the `bigint` identity column as the internal primary key — preserving right-edge insert locality, 8-byte foreign keys, and cheap joins — and add an opaque randomly generated external identifier with a unique index as the only value ever exposed in URLs, APIs, and webhooks. It costs a second random-insert unique index, an extra lookup or covering index on the read path, and standing discipline that the internal ID is never serialised. — The module's answer is two keys: a narrow sequential internal key for physical locality and cheap references, and an opaque external key for everything the outside world touches. It closes the volume leak and the enumeration path together, and the module insists on naming its costs — the extra unique index is itself a random-insert index with the scatter properties the module spent two sections on, plus the extra lookup, the serialisation discipline, and harder support debugging. Option D is the trap the module argues against throughout: it fixes the disclosure by adopting the one key choice with no case left for it on a growing table, reintroducing scattered inserts, WAL amplification, and index bloat. UUIDv7 is the defensible version of that idea, at the cost of a readable creation time. Option B is a genuine near-miss and genuinely necessary — correct authorisation is the real fix for enumeration (Module A-13) and rate limiting raises the attacker's cost (Module P-18) — but neither touches the volume leak, since two legitimately obtained IDs still differ by the row count. Option A obscures the absolute number while leaving the growth rate inferable from the delta, and a bounded random step still permits enumeration with modest extra effort.

What this module covers: The primary key is a physical layout decision disguised as a naming one, and it becomes near-irreversible once a table is large. This module covers the four real candidates — auto-increment, UUIDv4, UUIDv7/ULID, and Snowflake — with the cost of each named; the mechanism by which a random key turns the whole index into the write working set, including mid-tree page splits and WAL full-page-write amplification; the arithmetic of 16 bytes versus 36 and where it multiplies; Snowflake's bit layout and the clock regression that breaks it; and the volume leak a monotonic public ID hands to anyone holding two of them.

The Key Is Where Access Pattern Beats Storage Medium, in Reverse

Module F-2 ended on a claim: access pattern beats storage medium by a wider margin than people expect. Module P-2 uses it constructively — LSM-trees turn random writes into sequential ones and pay in read amplification. This module runs it backwards. A random primary key is one line in a CREATE TABLE that converts a sequential write pattern into a random one, deliberately, forever. Nobody frames it that way; they choose it because crypto.randomUUID() needs no round trip and lets the client mint the key before the row exists. Those benefits are real. The bill arrives at a size where you can no longer change your mind.

The pager symptom is slow and recognisable. Insert throughput slides over months rather than falling off a cliff. WAL volume grows out of proportion to the data written, so replication lag (Module P-5) and backup windows both stretch. The buffer cache hit ratio on one index degrades while everything else looks fine. The index reaches roughly double the size its row count justifies; a REINDEX reclaims most of it, and it comes back. No query is slow enough to surface in pg_stat_statements.

Analogy: a warehouse worker putting away arriving stock. With sequential keys every box goes onto the end of the last row — the worker stays in one aisle all shift, and the shelf they are filling is already open in front of them. With random keys each box's slot is drawn from a hat spanning ten acres: they drive the length of the building for every box, no aisle stays warm, and a shelf that turns out to be full means dragging in an empty one and moving half the existing boxes across before the new box fits.

The Four Candidates, and What Each One Costs

	Size	Ordering	Coordination	Leaks	Its cost
Auto-increment / identity	8 bytes	Total, monotonic	One authority per table	Volume; enumerable	No client-side generation; right-edge contention; range allocation across shards
UUIDv4	16 bytes	None	None	Nothing	Destroys insert locality — the next two sections
UUIDv7 / ULID	16 bytes	k-sortable by millisecond	None	Creation time, to the millisecond	Not a total order; same-millisecond ties can invert between nodes
Snowflake (64-bit)	8 bytes	k-sortable	Machine-ID assignment at startup	Creation time; per-node rate	A backwards clock issues duplicate keys; you operate an ID service

Auto-increment is the default and the default is usually right: an 8-byte key, perfect right-edge locality, the cheapest index entries available, comparison in one machine instruction. Three costs, all real.

It is a coordination point. The ID does not exist until the database says so, so you cannot assemble a graph of related rows in memory and insert it in one shot, cannot let an offline client create records, and cannot build an outbox row referencing its entity before the insert (Module A-3). Across shards it is worse: two shards handing out ID 1 is a merge you cannot perform, so you allocate disjoint ranges or per-node offset-and-step — coordination you must maintain, which quietly caps how many shards you can add (Module P-6).

It has a hot spot. Every insert targets the same rightmost index page. At normal concurrency that is the point; at extreme insert concurrency it becomes contention — the honest counter-argument to "sequential is always better."

It reports your size to anyone who can read it — the last section.

Against that is the one thing a server-side sequence cannot do: a client-generated key makes a retry idempotent. A retried request carries the same ID, and INSERT ... ON CONFLICT DO NOTHING turns a duplicate submission into a no-op. With a sequence you need a separate idempotency key and somewhere to store it (Module P-16). That is a genuine win for UUID-shaped keys, to be weighed rather than dismissed.

How One Random Column Makes the Whole Index the Write Working Set

Module F-13 gave the structure — a B-tree with values in sorted order at the leaves. Module F-2 gave the unit — Postgres reads and writes 8 KB pages. The mechanism falls out with no further machinery.

With a monotonically increasing key, every insert belongs at the right edge. The leaf you need is the one you needed last time: already in shared_buffers, already dirty, and it absorbs many rows before it fills. The set of pages being written is a handful of pages, however large the table.

With a random key, the target leaf is drawn uniformly from every leaf in the index. The set of pages being written is the entire index. Same row, same size, same complexity class — but the physical pattern went from "one page repeatedly" to "any page unpredictably," the transition F-2 says costs most. Three costs follow, and they compound.

Buffer-pool miss rate. Take a 500-million-row table whose primary key index is roughly 20 GB, on a machine with shared_buffers near 8 GB shared with everything else. A randomly chosen leaf is resident perhaps 40% of the time, so most inserts begin with an ~50 µs NVMe page read before any writing happens — and each read evicts something, so the rest of the workload's hit ratio degrades too. With a sequential key that read happens approximately never. The ratio is the point, not the digits.

Page splits everywhere instead of nowhere. Postgres treats a split at the rightmost page specially, leaving the left side nearly full because it can see inserts are ascending and nothing will arrive to fill the gap. Ascending keys therefore pack leaves close to full. Random keys cause ordinary mid-tree splits, each leaving two half-empty pages, and the index settles at a steady-state fill of roughly 50–70%. That is the bloat — not dead tuples, just permanently half-used pages — and a bigger index means more pages competing for the buffer pool, feeding back into the miss rate.

WAL amplification, the large one. With full_page_writes on — the default, and what protects you from torn pages on a crash — the first modification of a page after a checkpoint writes the whole 8 KB page image into the WAL, not just the delta. Sequential inserts touch few distinct pages between checkpoints, so those images are rare and amortised over many rows. Random inserts touch a different page nearly every time, so a large fraction of inserts drags an 8 KB image into the WAL to record a ~100-byte row. That is one to two orders of magnitude more WAL for the same data, and WAL is not a local cost: it streams to every replica, fills your archive, and gets replayed by a restore.

None of this is special to the primary key — an index on (tenant_id, created_at) where tenant_id is a v4 UUID scatters identically.

Why this matters in production: no tool that hunts for slow queries will find this, because no query is slow — the insert still returns in single-digit milliseconds. What changed is the rate at which the system absorbs inserts and the WAL bytes each one costs. You find it by measuring those, not on a latency dashboard. And you find it at 400 GB, when changing the key means rewriting the table and every index referencing it, online, under traffic (Module O-4).

Sixteen Bytes or Thirty-Six, and Where That Multiplies

Separately from locality there is a plain storage cost, and it hides the most common unforced error: storing a UUID as text.

Postgres's uuid type is 16 bytes, fixed. The canonical 36-character string form in text or varchar(36) costs 36 bytes plus a length header — 37 to 40 with alignment. That is ~21 wasted bytes per occurrence, roughly 10 GB per copy on 500 million rows, and it makes every comparison a variable-length string comparison while admitting 'A1B2…' and 'a1b2…' as distinct values. Use the native type and render the string at the API boundary; the cost is less readable psql output and an explicit cast whenever you compare to a literal.

Where "per copy" multiplies needs precision, because the folklore is wrong for Postgres. A Postgres secondary index does not implicitly carry the primary key — entries hold the indexed columns plus a 6-byte tuple pointer. The multiplier is the copies you wrote yourself: the PK's own index, every foreign key column in every child table, the index on each of those, and every composite index containing the key. In a normalised schema that is easily five to ten copies, and 21 wasted bytes each becomes tens of gigabytes competing for the same buffer pool.

In MySQL/InnoDB the folklore is correct, and worse. InnoDB clusters the table on the primary key, so the row data is the PK index leaf and every secondary index entry stores the full PK as its row pointer. A wide PK inflates every secondary index directly, and a random PK scatters the rows themselves rather than merely an index.

Time-Ordered IDs Put the Writes Back at the Right Edge

UUIDv7 and ULID keep coordination-free generation and give back the locality. Both put a millisecond timestamp in the high-order bits and fill the rest with randomness. UUIDv7 (standardised in RFC 9562, which superseded RFC 4122) uses a 48-bit big-endian Unix millisecond timestamp, then version and variant bits, then random bits. ULID uses the same 48-bit prefix plus 80 random bits, with a 26-character Crockford base32 encoding that sorts lexicographically as text.

Because the timestamp is the most significant component, new IDs sort near each other and near the end of the index. Inserts return to a small set of right-edge pages: the miss rate collapses, splits become rightmost splits with high fill, and the full-page-write amplification largely disappears. You keep client-side generation, idempotent retries, and shard-independent writes, and pay 16 bytes instead of 8.

The cost beyond those 16 bytes: the value now carries a creation timestamp you are probably exposing. Anyone holding a UUIDv7 knows when that row was created, to the millisecond. Harmless for an order ID; a real disclosure for a password-reset token or a private message — and one people do not expect from something that looks like a random UUID.

Snowflake: Coordination-Free IDs in 64 Bits, and the Clock You Must Trust

Snowflake gets both properties into a bigint. The widely-copied layout:

Bits	Field	Consequence
1	Unused sign bit	Value stays positive in a signed 64-bit integer
41	Milliseconds since a custom epoch	~69 years of range from your chosen epoch
10	Machine ID	1,024 concurrent generators
12	Per-millisecond sequence	4,096 IDs/ms/node, so ~4M IDs/s/node

Time-ordered, so right-edge locality. And coordination-free on the hot path: no network call per ID, because the machine ID makes each node's output disjoint by construction. That is what makes Snowflake attractive across shards.

The coordination did not vanish, it moved to startup. Machine IDs must be unique, and assigning them is a real distributed-systems problem — a lease from etcd or ZooKeeper (Module A-2), a StatefulSet pod ordinal, or static config you must never copy-paste wrong. But the failure mode that gets people is the clock.

typescript

let lastMs = -1;
let sequence = 0;

export function nextId(machineId: number): bigint {
  const now = Date.now();

  // THE line that matters. The timestamp is the high-order component, so
  // uniqueness rests entirely on time never moving backwards. An NTP step
  // correction can rewind the wall clock — and a rewound clock re-issues
  // (timestamp, machineId, sequence) triples already in the database.
  if (now < lastMs) throw new Error(`clock regression: ${lastMs - now}ms`);

  sequence = now === lastMs ? (sequence + 1) & 0xfff : 0;   // 12 bits, 4096/ms
  lastMs = now;

  return (BigInt(now - EPOCH_MS) << 22n) | (BigInt(machineId) << 12n) | BigInt(sequence);
}

Halting during a regression is the standard behaviour, and note the cost: a clock correction becomes a write outage on that node for the duration of the skew. Brief unavailability is the deliberate choice, because duplicate keys are not really cleanable — by the time you notice, two entities have been referenced by one ID in logs, caches, and downstream systems. A monotonic clock measures elapsed time but does not supply the wall-clock component Snowflake encodes, so the check stays. The second cost: you now own an ID-generation concern, and a machine-ID misconfiguration is silent until it is catastrophic.

k-Sortability Is What Makes Cursor Pagination Cheap

Module F-8 specified (created_at DESC, id DESC) as a matched composite so a cursor has a stable tiebreaker. A time-ordered ID collapses that to one column.

sql

-- Time-ordered PK: cursor and sort key are the same column, and the primary
-- key index alone serves this as a short scan at the right edge.
SELECT * FROM orders WHERE id < $1 ORDER BY id DESC LIMIT 20;

-- Random v4 PK: `id` carries no time, so the cursor needs a separate column,
-- its own composite index, and row-comparison semantics that are easy to
-- get subtly wrong.
SELECT * FROM orders WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC LIMIT 20;

Two more payoffs. Recent-rows range queries become right-edge scans — "everything from the last hour" is a bounded key range hitting pages still hot from the inserts that created them. And archival gets simpler: dropping last year's data becomes a partition drop on an ID range (Module P-6) rather than the mass delete that generates the bloat F-13 described.

Two costs. All of this works by making creation time inferable from the key. And k-sortable is not sorted: two IDs minted in the same millisecond on different nodes have no defined relative order, so never use ID order as a business ordering for events that must be sequenced correctly — that needs Module A-1's machinery.

A Monotonic Public ID Is a Free Volume Report

Two facts about an exposed sequential ID.

It leaks volume. Place one order in January and one in February, note the IDs, subtract. You now know that company's monthly order count, accurate to whatever gaps the sequence left — the German tank problem with the guesswork removed. A competitor or a counterparty in due diligence can do it from two receipts, and what it gives away is the growth rate, not just the absolute scale.

It enables enumeration. /invoices/10432 implies /invoices/10431 exists. If authorisation has one gap on one endpoint, sequential IDs turn that gap from "an attacker reads the record they were handed" into "an attacker walks the table" (Module A-13). Correct authorisation is the actual fix and rate limiting raises the cost of the walk (Module P-18) — but a guessable identifier is what makes the failure total rather than local.

The standard answer keeps both properties by using two keys:

sql

CREATE TABLE invoices (
  -- Internal: never leaves the database. 8 bytes, right-edge insert locality,
  -- cheap joins, and what every foreign key in the schema references.
  id          bigint PRIMARY KEY GENERATED BY DEFAULT AS IDENTITY,

  -- External: the only identifier URLs, APIs, emails, and webhooks ever see.
  -- Opaque, unguessable, no volume signal, no creation timestamp.
  public_id   text NOT NULL DEFAULT ('inv_' || encode(gen_random_bytes(16), 'hex')),

  customer_id bigint NOT NULL REFERENCES customers(id),
  total_cents bigint NOT NULL CHECK (total_cents >= 0),
  created_at  timestamptz NOT NULL DEFAULT now(),

  CONSTRAINT invoices_public_id_key UNIQUE (public_id)
);

Its costs, because this gets recommended as though it were free. A second unique index on a random value — a random-insert index with exactly the scatter properties described above; bounded, since it is smaller and not the clustering key, but the same mechanism and not zero. An extra lookup on the read path, since every request arrives with a public_id that must resolve to an id. Discipline forever, because the internal ID must never appear in a URL, response, webhook, export, or error message — and invariants that depend on nobody forgetting are the ones that break. And harder support debugging, since the ID a customer quotes is not the one in your logs unless you log both.

The prefixed form (inv_, cus_) costs a few bytes and buys a lot: a misrouted identifier fails legibly instead of resolving to the wrong entity. If a second column is unwelcome, UUIDv7 as the sole key is a defensible middle — unguessable, no volume signal — at the cost of 16 bytes everywhere and a readable creation time.

Where This Shows Up in Your Stack

PostgreSQL: use uuid, never text; gen_random_uuid() is v4, so v7 comes from your application or an extension — check rather than assume. Prefer GENERATED ... AS IDENTITY over serial. Measure the real thing with WAL bytes per inserted row (pg_current_wal_lsn() around a fixed batch) and index fill via pgstattuple.
Node.js: crypto.randomUUID() is v4, which makes the worst primary key the easiest one to reach for. And a 64-bit Snowflake ID exceeds Number.MAX_SAFE_INTEGER (2^53−1), so JSON.parse silently rounds it — two distinct IDs can become the same number in a browser. Serialise 64-bit IDs as strings at the boundary, or use BigInt end to end.
Redis: INCR works as an ID allocator if used hi/lo — each instance claims a block of 1,000 and hands them out locally, so Redis is on the path once per thousand IDs. The cost is that Redis becomes durability-critical: an instance restarting from a stale snapshot replays a counter it already issued (Module P-12).
MySQL/InnoDB: the clustered index makes everything here worse. If you inherit a char(36) UUID key, converting it to binary(16) is a measurable win before you even address ordering.

Summary

The primary key is a physical layout decision that becomes near-irreversible with size — changing it on a 400 GB table rewrites the table and every index referencing it (Module O-4).
A random v4 key makes the entire index the write working set. Sequential inserts touch a handful of right-edge pages; random inserts touch any page — F-2's access-pattern penalty applied to your own schema.
Three compounding costs follow: buffer-pool misses on most inserts, mid-tree splits leaving the index at ~50–70% fill, and WAL full-page-write amplification of one to two orders of magnitude. None of it appears on a latency dashboard, because no query is slow.
Store UUIDs as 16-byte uuid, not 36-byte text. In Postgres the multiplier is the copies you wrote — FK columns and composite indexes; in InnoDB every secondary index carries the PK, so it is direct and larger.
Auto-increment is the cheapest key and costs three things: no client-side generation, right-edge contention at extreme concurrency, and a volume leak. Client-generated keys buy idempotent retries in return (Module P-16).
UUIDv7/ULID restore right-edge locality via a 48-bit millisecond prefix, costing 16 bytes and a readable creation time. Being k-sortable makes cursor pagination a single-column right-edge scan (Module F-8) and archival a partition drop (Module P-6).
Snowflake (41-bit timestamp | 10-bit machine ID | 12-bit sequence) buys coordination-free 8-byte keys. Machine-ID assignment is still coordination, and a backwards clock must halt issuance — a brief write outage chosen over duplicate keys you cannot clean up.
A monotonic public ID reports your volume and growth rate to anyone holding two of them, and makes one authorisation gap total rather than local. The answer is an internal identity PK plus an opaque external ID, costing an extra unique index, an extra lookup, and permanent discipline.

The next module, Connection Pooling and the Database Bottleneck, moves from what a row is keyed by to how a request reaches the database at all. The connection is the resource Module F-13's one-slow-query cascade actually exhausted, and P-4 sizes it properly — including the serverless case where every invocation arrives holding its own connection and the pool stops being a pool.

Knowledge Check

A team migrates a 500-million-row Postgres table's primary key from bigint identity to UUIDv4. Insert latency looks unchanged, but over the following weeks WAL volume roughly triples, replica lag becomes routine, and the primary key index grows to nearly double the size its row count justifies. What is the dominant mechanism?

A sharded service generates Snowflake IDs on every node. After an NTP correction steps one node's wall clock back by ~400 ms, that node starts rejecting writes with a "clock regression" error. An engineer proposes deleting the check so writes continue. What happens, and why is the check there?

A competitor publishes an accurate estimate of a company's monthly order volume, derived from the IDs in two invoice URLs a month apart. Separately, a scraper has been walking /invoices/{id} by decrementing the number. Which response addresses both, and what does it cost?

Test your knowledge with more question sets

Sign in to keep reading

The rest of this module is free — sign in with Google to unlock it and track your progress.

PreviousModule P-2: Storage Engines: B-Trees vs LSM-Trees Next Module P-4: Connection Pooling and the Database Bottleneck

Discussion

Join the discussion

Loading comments...