ID Generator Cheat Sheet

Key concepts, trade-offs, and quick-reference notes for your interview prep.

Snowflake Layout: 1 + 41 + 10 + 12

1 sign bit (zero: IDs stay positive int64 everywhere) + 41 bits of ms since a custom epoch + 10 bits worker ID + 12 bits sequence. Each field buys a guarantee: timestamp buys k-sortability, worker bits buy coordination-free uniqueness across

2^{10} = 1{,}024

machines, sequence buys burst:

2^{12} = 4{,}096

IDs/ms/worker. Ceilings: 4.096M IDs/sec per worker at the bit level, 4.2B/sec cluster-wide, 69.7 years of clock. The split is a dial: Sonyflake trades burst for 65K workers and 174 years; Instagram embeds 13 shard bits in PostgreSQL.

💡 Say what each field BUYS, not just the widths. The layout is the design.

UUID vs Snowflake: The Locality Tax

UUIDv4: zero infrastructure, but 16 bytes/key and random B-tree inserts: every insert lands on a random index page, the working set becomes the whole index, and throughput collapses ~10x past RAM (Percona). No time signal. UUIDv7 (2024): 48-bit ms prefix fixes locality, still 128 bits: the right default when you control neither end. Snowflake: 8 bytes, k-sortable, extractable timestamp: costs worker-ID assignment and clock discipline. Collisions are NEVER the argument against UUIDv4 (

2^{122}

): performance and semantics are.

💡 Rightmost-page appends vs random-page inserts is the whole B-tree story. Know UUIDv7 exists.

Clock-Backward Policy Ladder

NTP steps the clock backward and the worker sees a used millisecond: generating now means duplicates, the one unforgivable failure. The ladder: small step -> spin-wait until wall clock passes last-used timestamp; large step -> refuse and page (down is an incident, duplicating is a catastrophe); optional grace -> borrow from sequence at the last timestamp until it overflows (a tiny hybrid logical clock). Prevention: slew-only NTP on generator hosts, monotonic-clock regression detection, persist last timestamp so restarts wait instead of replaying a millisecond.

💡 Availability vs safety: always choose safety. A paused generator fails loudly; a duplicating one corrupts quietly.

Worker IDs: Leases with Fencing

Two machines sharing worker ID 7 = duplicates every overlapping ms. Assignment options: ZooKeeper/etcd ephemeral lease per ID (TTL ~10s, renew every 3s) with the fencing deadline: stop generating at TTL minus safety margin, BEFORE the lease can expire under you (the GC-pause double-worker scenario). StatefulSet ordinals: pod-N = worker N; the orchestrator guarantees single ownership for free. Never: hardcoded config (copy-paste duplicates) or MAC/IP derivation (clones, DHCP). Pool math: 1,024 IDs is a hard cap: monitor pool usage or autoscaling silently blocks.

💡 The fencing deadline is the answer to "what if the ZooKeeper session expires during a GC pause?"

What K-Sortability Buys

Numerically sorted IDs come out ~creation-ordered (exact per worker, ms-fuzzy across workers: the "k"). Buys: B-tree append locality (hot rightmost page, no split storms), cursor pagination (the ID is the cursor: no OFFSET, no created_at index), cross-shard merge-sort (timeline assembly by ID), range archival (a month = an ID range), and extractable timestamps (shift right 22 bits + epoch = creation time, from the ID alone). Does NOT buy causality: ID order is not a logical clock across services.

💡 Enumerate the five buys. "Sortable" as a checkbox wastes the topic's best material.

Real Ceiling: RPC, Not Bits

Bit ceiling: 4,096/ms = 4.096M IDs/sec/worker. Practical ceiling as a gRPC service: 100-200K IDs/sec/worker: RPC overhead dominates, 20-40x below the bits. Fixes: batching (one RPC returns a reserved run of 500 IDs: round trip amortized) and library embedding (generator linked into the app process, each instance its own worker: zero network, but spends worker IDs faster and pushes clock discipline to every host). Platform need of 10M IDs/sec = 50 service workers with batching, or ~0 extra infra as a library.

💡 Candidates quote the bit ceiling; the network is the real one. Batching is the standard answer.

Sequence Overflow: Spin to Next Millisecond

ID 4,097 in one ms: the budget is spent. Correct behavior: spin-wait to the next ms, reset sequence to 0: at most 1ms, invisible unless sustained. Sustained saturation makes the generator a hard rate limiter: monitor sequence saturation ratio (fraction of ms hitting 4,095); above ~10% sustained, add workers or push batching before callers feel latency. Guard the fleet from one bad citizen: per-caller rate limits and batch-only APIs above a threshold stop a tight-loop client from saturating a worker while the rest idle.

💡 Saturation ratio is the leading indicator; p99 latency is the lagging one.

Ticket Servers and Range Allocation

Flickr's pattern, generalized: a central allocator grants ranges ("IDs N to N+10,000") and workers mint locally: coordination cost drops from per-ID to per-range. Trade table vs Snowflake: ranges give dense sequences and zero clock discipline (no NTP anywhere); Snowflake gives time-ordering and no central dependency. Ranges strand IDs on crash (gaps: usually fine) and survive allocator outages on unspent ranges (Flickr ran odd/even dual ticket servers). Our URL shortener's 62^7 counter blocks ARE this pattern. Combine them: lease WORKER IDS by range, mint Snowflake locally.

💡 One pattern, three topics: URL-shortener counters, ticket servers, worker-ID leases. Amortize coordination with ranges.

Custom Epoch: The Irreversible Parameter

2^{41}

ms = 69.7 years: from your custom epoch, not 1970 (Unix epoch wastes 50+ years and overflows in the 2030s). Twitter: 2010-11-04; Discord: 2015-01-01. The epoch is a decode contract: every analytics pipeline and debugger that extracts timestamps depends on it, and it cannot be rotated in place: mixed-epoch IDs interleave wrongly forever. Extensions, in order: spend fewer sequence/worker bits (Sonyflake: 174 years), version the ID space OUTSIDE the 64 bits, or a coordinated cutover to a higher base. Never let a test epoch reach production.

💡 Bit budgets flex, worker schemes migrate: the epoch is forever. Derive 69.7 years on the whiteboard.

Monitoring an ID Generator

#10

Clock skew per worker vs fleet median: page past 100ms; skew bounds both duplicate risk and the k in k-sortable. Backward-step events: any occurrence logs loudly; sustained = NTP misconfigured (step mode instead of slew). Sequence saturation ratio per worker. Worker-ID pool usage: near 1,024 blocks autoscaling. Lease renewal latency: approaching the fencing deadline means workers about to park. And the duplicate canary: SETNX every Nth generated ID into Redis; any conflict is a sev-1 that says the impossible happened. Latency itself: p99 <1ms in-process, <5ms via RPC.

💡 The duplicate canary converts "cannot happen" into "we would know in seconds if it did."