System Design · Lesson 7 of 18
Unique ID Generator
UUIDs, Snowflake, ticket servers, clock skew and monotonic ordering at scale.
- Advanced
- 50 min read
- 6 objectives
Before this lessonLesson 6: Low-Level Design: Classes, APIs and Concurrency
What you will learn
- Pin down id requirements: uniqueness scope, ordering, size, throughput and exposure
- Compare UUIDv4, UUIDv7, ULID, auto-increment, step increments, ticket servers, range allocation and Snowflake
- Build a Snowflake generator that handles clock regression and sequence overflow
- Assign worker ids safely with leases, self-fencing and cooldowns
- Explain how random keys fragment B-tree indexes, and when sequential keys become hot spots
- Keep internal ids private: enumeration, leakage and encrypted public ids
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
Nearly every system in this course needs a way to name new things: order ids, message ids, tweet ids, short-URL codes, file ids, payment ids. On one machine this is a solved problem, an auto-increment column. Across a hundred app servers in three datacenters, handing out billions of ids a day with no collisions, no central bottleneck and no extra network hop turns into a real distributed-systems question. That is why interviewers like it: the prompt is tiny, but a good answer touches clocks, consensus, storage engines, index structure and security.
The lesson follows the same shape as a full case study. We pin the requirements down with numbers, do the maths, lay out eight candidate schemes in one comparison table, pick Snowflake for the stated constraints, and then build it properly: bit layout, a runnable generator that handles clock regression and sequence overflow, worker-id leases, decoding, and the failure cases that turn a neat diagram into duplicate primary keys at 3 a.m.
Step 1 — Clarify the requirements
"Generate unique ids" hides at least five independent questions. Candidates who jump straight to "Snowflake: 41 bits of time, 10 bits of machine, 12 bits of sequence" without asking any of them usually get stopped with a constraint that makes Snowflake the wrong answer, such as "the ids appear in public URLs" or "clients generate ids offline".
Questions to ask, and why each one matters
- Unique within what? One table, one service, the whole company, or globally including mobile clients? The wider the scope, the more bits of randomness or coordination you need.
- Do ids need to be sortable by creation time? If "newest first" feeds, cursor pagination or time-range scans run on the id, you need time-ordered ids. If not, random ids are simpler.
- Strictly or roughly ordered? Strict global ordering (id A < id B means A was created first, across every machine) needs a single sequencer. Rough ordering (within a few milliseconds) is what distributed schemes actually give you. Almost everyone needs only the rough version, but you have to ask.
- How big can the id be? 64 bits fits a SQL
BIGINT, a Javalong, a Redis integer and a Kafka key without thinking. 128 bits (UUID) doubles index size and is awkward in some languages and in JavaScript, where numbers above 253 lose precision. - Throughput per node and in total? 100 ids/s and 500,000 ids/s have different answers.
- Is coordination on the hot path allowed? A network round trip per id adds latency and a dependency. The usual requirement is that minting an id is a local, in-memory operation.
- Are ids exposed to users? Public ids leak information (creation time, volume, machine) and invite enumeration. That can rule out any sequential scheme for the public-facing identifier.
Functional requirements for our design
next_id()returns a new 64-bit integer that no other call anywhere in the fleet has ever returned or will ever return.next_ids(n)returns a batch, for bulk inserts.decode(id)returns creation time, datacenter and worker, for debugging and for time-range queries on the primary key.
Out of scope (say it out loud)
Human-friendly codes (order numbers read over the phone), strictly gapless sequences (invoice numbers some tax authorities require, which need a single serialised counter and are a separate small system), and short public codes for a URL shortener, which get their own treatment in the URL shortener lesson. We will still cover the key-generation service those designs use, because it is one of the candidates.
Non-functional requirements
- Uniqueness: absolute. A duplicate primary key is data loss or data corruption, not a latency blip. This one outranks every other requirement.
- Size: 64 bits, positive (so it survives signed
longtypes), which leaves 63 usable bits. - Sortability: k-sortable, meaning ids created more than a few milliseconds apart sort in creation order. Ids minted in the same millisecond on different machines may be in either order.
- Throughput: at least 10,000 ids/s per node sustained, bursts to 100,000 ids/s per node, around 300,000 ids/s across the fleet at peak.
- Latency: p99 under 1 ms, which in practice means no network call per id.
- Availability: id generation must keep working when any single dependency (the coordination service, one datacenter, the network between datacenters) is down. If ids stop, every write in the company stops.
- No coordination per id: machines agree once, at startup, on who they are, and then mint independently.
- Longevity: the scheme must not run out for at least 50 years.
Step 2 — Back-of-the-envelope estimation
Put numbers on the load, then check that 64 bits can carry it. This step is what justifies the bit budget later: every bit you give to one field is taken from another.
import math
# --- Demand: every write in the company needs an id ---
writes_per_day = {"orders": 5_000_000, "messages": 2_000_000_000,
"posts": 50_000_000, "events": 3_000_000_000}
total_day = sum(writes_per_day.values())
avg = total_day / 86_400
peak = avg * 5
print(f"ids/day: {total_day:,} avg: {avg:,.0f}/s peak (5x): {peak:,.0f}/s")
# --- Supply per generator node with a 12-bit sequence ---
per_ms = 2 ** 12
per_node_s = per_ms * 1000
print(f"one node: {per_ms} ids/ms = {per_node_s:,} ids/s ceiling")
print(f"nodes needed for raw throughput: {math.ceil(peak / per_node_s)}")
# --- How long does a 41-bit millisecond clock last? ---
ms_41 = 2 ** 41
years = ms_41 / 1000 / 86_400 / 365.25
print(f"41-bit ms timestamp lasts {years:.1f} years from the custom epoch")
# --- Lifetime id count: do we fit in 63 usable bits? ---
ten_years = total_day * 365 * 10
print(f"ids in 10 years: {ten_years:.2e} (2^63 = {2**63:.2e})")
# --- Storage: bigint vs UUID as primary key, 10B rows, PK + 3 secondary indexes ---
rows = 10_000_000_000
copies = 1 + 3 # clustered PK + every secondary index stores the PK
for name, size in (("BIGINT", 8), ("UUID binary", 16), ("UUID as text", 36)):
gb = rows * size * copies / 1e9
print(f"{name:13s} {size:2d} B/key -> {gb:,.0f} GB of key bytes")ids/day: 5,055,000,000 avg: 58,507/s peak (5x): 292,535/s one node: 4096 ids/ms = 4,096,000 ids/s ceiling nodes needed for raw throughput: 1 41-bit ms timestamp lasts 69.7 years from the custom epoch ids in 10 years: 1.85e+13 (2^63 = 9.22e+18) BIGINT 8 B/key -> 320 GB of key bytes UUID binary 16 B/key -> 640 GB of key bytes UUID as text 36 B/key -> 1,440 GB of key bytes
What the numbers decide
- Throughput is not the hard part. A 12-bit sequence gives one node a ceiling of 4 million ids/s, more than ten times the whole fleet's peak. So we can spend bits on other things (datacenter, worker) without worrying about running dry. When a candidate proposes 16 or more sequence bits "for safety", ask what those bits cost in worker ids or lifetime.
- 63 bits holds the id count easily. Ten years of every write in the company is about 1013 ids, against a space of about 1019. The constraint is not the count of ids, it is how we structure the bits so that machines never overlap without talking to each other.
- A 41-bit millisecond timestamp lasts about 70 years from a custom epoch. If you count from 1970 instead, you have already used about 56 of those years. That is why every Snowflake-style scheme picks its own epoch, usually the year the system launched.
- Key size is multiplied by every index. In InnoDB and most B-tree engines, every secondary index stores the primary key. On a 10-billion-row table with three secondary indexes, switching from
BIGINTto binary UUIDs costs about 320 GB more of key bytes, and storing UUIDs as 36-character strings (a common mistake) costs over a terabyte more. Those bytes live in the buffer pool, so they turn directly into cache misses.
Step 3 — The interface: library or service?
Before comparing schemes, decide where the generator runs. There are two shapes, and the choice affects latency, failure isolation and how worker ids get assigned.
## Option A: an in-process library (preferred for Snowflake-style ids)
gen = IdGenerator.start(datacenter=3, registry="etcd://idgen") # acquires a worker lease
order_id = gen.next_id() # ~100 ns, no I/O
batch = gen.next_ids(500) # for bulk inserts
info = IdGenerator.decode(order_id) # {created_at, datacenter, worker, seq}
## Option B: a network service (needed for ticket servers / key generation)
POST /v1/ids?count=100
Headers: X-Client: order-service
-> 200 { "ids": ["228666743193993216", ...] } # strings: JavaScript loses
# precision above 2^53
-> 503 + Retry-After # generator refuses while its clock is behind or its
# worker lease is lost; never returns a risky id
GET /v1/ids/{id}/decode
-> 200 { "created_at": "2025-09-23T00:00:00.000Z",
"datacenter": 3, "worker": 1, "sequence": 0 }
## gRPC variant used internally
rpc NextIds(NextIdsRequest{count}) returns (NextIdsResponse{repeated fixed64 ids})Decisions worth defending
- Library by default. A library has no network hop and no extra service to keep up. Its cost is that every app process needs its own worker id, so a fleet of 3,000 pods needs 3,000 worker ids and a registry to hand them out. We will size the worker field for that.
- Service when processes are too many or too short-lived. Serverless functions and batch jobs that live for seconds cannot each hold a worker lease. Put a small generator service in front of them and let clients fetch ids in batches of 100 to amortise the round trip.
- Return ids as strings over JSON. A 64-bit id such as 228666743193993216 is above JavaScript's safe integer limit (253 - 1), and
JSON.parsesilently rounds it. Twitter hit this and added anid_strfield next to every numeric id. Use strings in public APIs and integers inside. - Fail closed. The generator returns an error rather than an id it is not sure about. A 503 costs one retry; a duplicate id costs a data-repair project.
Step 4 — The candidates, compared
There are eight schemes worth knowing. The interviewer expects you to name several, discard most of them for a specific reason, and pick one for the stated constraints. Here they all are against our requirements.
| Scheme | Size | Time-sortable | Coordination | Throughput limit | Main weakness |
|---|---|---|---|---|---|
| UUIDv4 (random) | 128 bits | No | None | Unlimited | Random inserts fragment B-tree indexes; 2x the storage of a bigint |
| UUIDv7 (time + random) | 128 bits | Yes (ms) | None | Unlimited | Still 128 bits; leaks creation time |
| ULID | 128 bits, 26 chars | Yes (ms) | None | Unlimited | Same as UUIDv7, not a standard UUID type in databases |
| DB auto-increment, one primary | 64 bits | Yes, strictly | Every id, one server | That primary's write rate | Single point of failure and bottleneck; cannot shard |
| Multi-master step increments | 64 bits | Only per server | Setup only | N x one primary | Adding a server means re-numbering all offsets |
| Ticket server (Flickr style) | 64 bits | Roughly | Every id, network hop | Ticket server's write rate | Extra hop per id; ticket servers must stay up |
| Range allocation / key generation service | 64 bits or short code | No (only within a range) | Once per block | Very high | Ids not time-ordered across servers; gaps when a node dies |
| Snowflake | 64 bits | Yes (k-sortable) | Worker id at startup only | 4,096 per ms per worker | Depends on clocks; worker ids must be managed |
Now the reasoning behind each row, because the table is only useful if you can defend it.
UUIDv4: 122 random bits
Generate 16 random bytes, set 4 bits to the version and 2 bits to the variant, and you have a UUIDv4. No coordination, no clocks, no configuration, works on a phone that is offline. The question everyone asks is whether collisions are a real risk. The birthday bound answers it:
import math
def p_collision(n: float, bits: int) -> float:
"""Birthday bound: P(any collision) ~ 1 - exp(-n^2 / 2N)."""
space = 2.0 ** bits
return -math.expm1(-(n * n) / (2 * space))
# UUIDv4 has 122 random bits (6 are fixed version/variant bits).
for n in (1e9, 1e12, 1e15, 2.7e18):
print(f"UUIDv4, {n:.1e} ids -> P(collision) = {p_collision(n, 122):.2e}")
# Contrast: a 7-char base62 random short code (~41.7 bits).
bits_7 = 7 * math.log2(62)
print(f"\n7-char base62 = {62**7:,} codes = {bits_7:.1f} bits")
for n in (100_000, 1_000_000, 100_000_000):
print(f" {n:>11,} codes issued -> P(at least one clash) = {p_collision(n, bits_7):.3f}")
# Truncating a hash has the same maths: 6 base64 chars of MD5 = 36 bits.
n_half = math.sqrt(2 * 2**36 * math.log(2))
print(f"\nMD5 cut to 6 base64 chars: 50% clash chance after only {n_half:,.0f} urls")UUIDv4, 1.0e+09 ids -> P(collision) = 9.40e-20
UUIDv4, 1.0e+12 ids -> P(collision) = 9.40e-14
UUIDv4, 1.0e+15 ids -> P(collision) = 9.40e-08
UUIDv4, 2.7e+18 ids -> P(collision) = 4.96e-01
7-char base62 = 3,521,614,606,208 codes = 41.7 bits
100,000 codes issued -> P(at least one clash) = 0.001
1,000,000 codes issued -> P(at least one clash) = 0.132
100,000,000 codes issued -> P(at least one clash) = 1.000
MD5 cut to 6 base64 chars: 50% clash chance after only 308,651 urls
At a trillion ids the chance of any collision is about 10-13, far below the chance of a disk silently corrupting the row. You reach coin-flip odds only around 2.7 × 1018 ids. Collisions are not the problem with UUIDv4, provided the random source is a real CSPRNG. Most real UUID collisions come from bugs: a PRNG seeded with the same value in forked processes, a cloned VM image, or a library that fell back to a weak generator.
The same maths shows why short random codes and truncated hashes are a different story. A 7-character base62 code has about 41.7 bits, and the chance of at least one clash hits 13% after only a million codes. Cutting an MD5 hash down to six base64 characters (36 bits) gives even odds of a clash after about 300,000 URLs. That is why a URL shortener that hashes the long URL must check for a clash and retry, and it has two more problems: the same long URL always hashes to the same code (two users shortening the same link get the same code, which breaks per-user analytics and deletion), and small differences in URL encoding produce different codes for the same page. Salting the hash with a counter or user id fixes the first and brings back the need for coordination. This path usually ends at a key generation service, below.
The real costs of UUIDv4 are storage (16 bytes against 8, multiplied by every index) and, more importantly, randomness in the index. We will measure that in Step 10. Use UUIDv4 when ids are generated in many places you do not control (clients, partners, offline devices), when the table is small, or as an opaque public token next to a sortable internal key.
UUIDv7 and ULID: time first, then randomness
UUIDv7 (standardised in RFC 9562, 2024) puts a 48-bit Unix millisecond timestamp in the high bits and fills the rest with random bits. ULID, which came earlier, does the same thing and encodes the result as 26 characters of Crockford base32, which leaves out I, L, O and U so ids are not misread. Both sort in creation order, both need no coordination, and both keep 74 to 80 random bits per millisecond, so collisions within one millisecond are still negligible.
import random, uuid
rng = random.Random(7) # seeded so the output is reproducible; use os.urandom in production
def uuid4_like() -> uuid.UUID:
b = bytearray(rng.getrandbits(128).to_bytes(16, "big"))
b[6] = (b[6] & 0x0F) | 0x40 # version 4
b[8] = (b[8] & 0x3F) | 0x80 # RFC 9562 variant
return uuid.UUID(bytes=bytes(b))
def uuid7(unix_ms: int) -> uuid.UUID:
"""RFC 9562: 48-bit ms timestamp | ver(4) | 12 rand | var(2) | 62 rand."""
rand_a = rng.getrandbits(12)
rand_b = rng.getrandbits(62)
v = (unix_ms << 80) | (0x7 << 76) | (rand_a << 64) | (0b10 << 62) | rand_b
return uuid.UUID(int=v)
CROCKFORD = "0123456789ABCDEFGHJKMNPQRSTVWXYZ" # no I, L, O, U
def ulid(unix_ms: int) -> str:
"""48-bit ms timestamp + 80 random bits, Crockford base32, 26 chars."""
v = (unix_ms << 80) | rng.getrandbits(80)
return "".join(CROCKFORD[(v >> (5 * i)) & 31] for i in reversed(range(26)))
t0 = 1_758_585_600_000 # 2025-09-23 00:00:00 UTC in ms
stamps = [t0, t0 + 1, t0 + 2, t0 + 1000]
v4 = [uuid4_like() for _ in stamps]
v7 = [uuid7(t) for t in stamps]
ul = [ulid(t) for t in stamps]
print("UUIDv4 (creation order):")
for u in v4: print(" ", u)
print(" sorted == creation order?", sorted(v4) == v4)
print("UUIDv7 (creation order):")
for u in v7: print(" ", u)
print(" sorted == creation order?", sorted(v7) == v7)
print("ULID (creation order):")
for u in ul: print(" ", u)
print(" sorted == creation order?", sorted(ul) == ul)
print("v7 timestamp recovered:", v7[3].int >> 80 == t0 + 1000)UUIDv4 (creation order): 6513270e-269e-4d37-b2a7-4de452e6b438 d23f0824-128b-4f33-8c5c-7fd0a6a3a450 9531985d-5d9d-49f8-9818-e811892f902b 36f675cc-81e7-4ef5-a8e2-5d940ed90475 sorted == creation order? False UUIDv7 (creation order): 019973de-b800-7099-9bc0-d9d61600a35a 019973de-b801-76b0-8f67-05c911e20b8f 019973de-b802-7173-9b2b-52898d116ece 019973de-bbe8-70f2-a430-64b3d3ac94af sorted == creation order? True ULID (creation order): 01K5SXXE0074KF530GBMFV2Z13 01K5SXXE01JMZT17VPPPGQ1CSR 01K5SXXE02JEYGZNHGY7S9T3D9 01K5SXXEZ81JRPB36T2JAYC2QN sorted == creation order? True v7 timestamp recovered: True
Notice that the four v7 ids, spread over one second, share their first 9 hex digits. That shared prefix is exactly what makes inserts land on the same index page. UUIDv7 is now the right default when 128 bits is acceptable, and PostgreSQL 18 ships a native uuidv7() function. It fails our requirements only because we asked for 64 bits: an interviewer who allows 128 bits will accept "UUIDv7, done" if you explain why it beats v4. Both leak creation time to the millisecond, so they are not opaque public ids either.
One subtlety: within a single millisecond, random bits mean two ids from the same process are not guaranteed to be in order. RFC 9562 allows implementations to use part of the random field as a counter that increases within the millisecond (the ULID spec calls this "monotonic mode"). If you rely on ids to order events from one producer, use that mode.
Database auto-increment on one primary
Perfect on one box: unique, strictly ordered, 64 bits, no gaps (apart from rollbacks). It breaks on everything else. Every insert in the company funnels through one primary, a failover to an asynchronous replica that missed the last few writes hands out ids that were already used (and MySQL before 8.0 recomputed the counter from MAX(id) on every restart, so ids of deleted rows could come back), and the moment you shard the table each shard has its own counter, so ids collide across shards. Fine for a prototype and for low-volume admin tables; not a distributed answer.
Multi-master with step increments
Run N database servers and give each an offset and a step: with N = 2, server 1 hands out 1, 3, 5... and server 2 hands out 2, 4, 6... (MySQL's auto_increment_increment and auto_increment_offset). Each server is independent, so throughput scales with N and losing one server does not stop the others.
The weaknesses: ids are ordered per server but not across servers (server 1 may be at 9,001 while server 2 is at 4,002, so a newer row can have a smaller id); and you cannot add a server without re-planning every offset. Going from 2 to 3 servers means choosing a new step, making sure the new sequences start above everything already issued, and changing every server at the same moment. Candidates often propose this and do not notice the resize problem until asked.
Ticket server (the Flickr approach)
Flickr ran a dedicated MySQL database whose only job was to hand out ids. The trick is a one-row table and a statement that replaces the row, bumping its auto-increment value:
CREATE TABLE tickets64 (
id BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
stub CHAR(1) NOT NULL DEFAULT '',
PRIMARY KEY (id),
UNIQUE KEY stub (stub) -- only ever one row, so the table stays tiny
) ENGINE=InnoDB;
-- Each id request: replace the single row, which advances the counter.
REPLACE INTO tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID(); -- per-connection, so concurrent callers do not race
-- High availability: two ticket servers, odd and even, behind a round-robin.
-- Server A: auto_increment_increment = 2, auto_increment_offset = 1
-- Server B: auto_increment_increment = 2, auto_increment_offset = 2It is simple, gives 64-bit numeric ids that are roughly time-ordered, and is easy to reason about. The costs are a network round trip per id (or per batch), a dependency that every write in the company now has, and a throughput ceiling of what one MySQL row can take (a few thousand to tens of thousands of updates per second, limited by the row lock and the redo log fsync). With the odd/even pair, the two servers drift apart, so ordering is only rough. It is a sensible answer at medium scale and a good one to name, but it violates "no coordination per id".
Range allocation and the key generation service
Instead of asking a central counter for every id, ask it for a block of ids and hand them out from memory. One database row per id type holds the highest id allocated so far; an app server runs UPDATE ... SET max_id = max_id + 1000 and owns the next thousand. The central store sees one write per thousand ids. Meituan's Leaf segment mode and many in-house "sequence services" work this way. The refinement that matters is double buffering: fetch the next block in the background when the current one is 80% used, so a caller never waits on the database.
import threading
class CounterTable:
"""The allocator's durable state: one row per business key.
Real version: UPDATE id_alloc SET max_id = max_id + step WHERE biz = ?;
SELECT max_id FROM id_alloc WHERE biz = ?; (one transaction)"""
def __init__(self):
self.max_id = {"order": 0}
self.round_trips = 0
def grab(self, biz: str, step: int) -> tuple[int, int]:
self.round_trips += 1
self.max_id[biz] += step
hi = self.max_id[biz]
return hi - step + 1, hi # inclusive range [lo, hi]
class SegmentAllocator:
"""Hands out ids from an in-memory range; fetches the NEXT range in the
background once the current one is 80% used, so callers never wait on the DB."""
def __init__(self, db: CounterTable, biz: str, step: int, prefetch_at: float = 0.8):
self.db, self.biz, self.step, self.prefetch_at = db, biz, step, prefetch_at
self.lock = threading.Lock()
self.cur_lo, self.cur_hi = db.grab(biz, step)
self.next_seg = None
self.nxt = self.cur_lo
self.stalls = 0
def _maybe_prefetch(self):
used = (self.nxt - self.cur_lo) / self.step
if self.next_seg is None and used >= self.prefetch_at:
self.next_seg = self.db.grab(self.biz, self.step) # async in real life
def next_id(self) -> int:
with self.lock:
if self.nxt > self.cur_hi:
if self.next_seg is None: # prefetch lost the race: stall on DB
self.stalls += 1
self.next_seg = self.db.grab(self.biz, self.step)
self.cur_lo, self.cur_hi = self.next_seg
self.next_seg, self.nxt = None, self.cur_lo
v = self.nxt
self.nxt += 1
self._maybe_prefetch()
return v
db = CounterTable()
app1 = SegmentAllocator(db, "order", step=1000)
app2 = SegmentAllocator(db, "order", step=1000)
a = [app1.next_id() for _ in range(2500)]
b = [app2.next_id() for _ in range(10)]
print("app1 first/last:", a[0], a[-1], "| app2 first:", b[0])
print("db round trips for 2,510 ids:", db.round_trips, "| stalls:", app1.stalls + app2.stalls)
print("unique:", len(set(a + b)) == len(a) + len(b))
# app1 crashes now: the rest of its current segment and its prefetched one are lost.
wasted = (app1.cur_hi - app1.nxt + 1) + (app1.step if app1.next_seg else 0)
print("ids burned if app1 crashes now:", wasted, "-> gaps, never duplicates")app1 first/last: 1 3500 | app2 first: 1001 db round trips for 2,510 ids: 4 | stalls: 0 unique: True ids burned if app1 crashes now: 500 -> gaps, never duplicates
Two properties to call out. Ids are unique but not time-ordered across servers: app2's id 1001 was issued after app1's id 3500. And a crash burns the unused part of the block, which leaves gaps but never duplicates, because the counter row only ever moves forward. Gaps are fine for primary keys; they are not fine for invoice numbers.
The key generation service (KGS) used for short-URL codes is the same idea applied to random strings. Offline, the KGS generates random 6- or 7-character codes, removes duplicates, and stores them in a key database. Serving a code is then a lookup, not a computation, and there is no collision check on the hot path. The details interviewers probe:
- Two tables, unused and used. When the KGS gives a batch of codes to an app server, it moves them to the used table in the same transaction. Two app servers can then never receive the same code, even if they ask at the same instant, provided the move is atomic (
DELETE ... RETURNING, orSELECT ... FOR UPDATE SKIP LOCKEDin PostgreSQL). - In-memory batches. The KGS keeps a few thousand codes in memory and marks them used as soon as they are loaded. If it crashes, those codes are lost. With billions of codes available, losing a few thousand is an acceptable price for never handing one out twice.
- Key database size. 3.5 trillion possible 7-character base62 codes is far more than you need; pre-generate, say, 10 billion at 7 bytes each and the key database is about 70 GB, small enough for one replicated database.
- Single point of failure. Run a standby KGS with the same key database. Because app servers hold a local batch, a KGS failover of a few seconds is invisible to users.
- App-server caches. Each app server holds its own batch of codes. If it dies, its batch is wasted, which is the same trade-off again.
The KGS is the right answer when ids must be short and must not reveal order. For internal 64-bit primary keys it is a lot of machinery compared with the next option.
Snowflake: time, machine and sequence packed into 64 bits
Twitter published Snowflake in 2010 when it moved tweets off MySQL auto-increment. The idea is to split the 64 bits into fields so that uniqueness comes from structure, not from coordination: no two machines share a worker id, and no single machine reuses a (millisecond, sequence) pair. Machines agree once, at startup, on their worker id and never talk about ids again. It meets every one of our requirements, so it is our design. The rest of the lesson builds it.
Step 5 — The Snowflake bit layout
63 62 22 21 17 16 12 11 0
+---+-------------------------------------------+-------+-------+--------------+
| 0 | timestamp: ms since custom epoch (41) | dc(5) | wk(5) | sequence(12) |
+---+-------------------------------------------+-------+-------+--------------+
| | | | |
| | | | +-- 4,096 ids per ms per worker
| | | +------------- 32 workers per datacenter
| | +--------------------- 32 datacenters
| +------------------------------------------------- 2^41 ms = 69.7 years
+----------------------------------------------------------------------- sign bit, always 0
id = (ms - EPOCH) << 22 | dc << 17 | worker << 12 | sequenceWhy each field is where it is
- Sign bit fixed at 0. Java, Go
int64, PostgreSQLBIGINTand most JSON parsers treat 64-bit integers as signed. A negative id sorts before every older id and breaksORDER BY id. - Timestamp in the high bits. This is what makes ids sort by time: comparing two ids compares their timestamps first. Anything placed above the timestamp would take over the sort order (put the datacenter first and every id from dc 5 sorts after every id from dc 4, whatever its age).
- 41 bits of milliseconds. About 70 years from a custom epoch. Using seconds would free 10 bits but leave only one-second ordering and force a much larger sequence field. Using microseconds would last only 25 days in 41 bits.
- 10 bits of machine identity, split 5 + 5. 1,024 concurrent generators. The split into datacenter and worker lets each datacenter assign its own worker ids with no cross-datacenter coordination (Step 9).
- 12 bits of sequence at the bottom. Distinguishes ids minted by one worker in the same millisecond. At 4,096 per ms it is ten times our fleet peak per node.
Re-budgeting the bits
The 41/5/5/12 split is Twitter's, not a law. Change it when your constraints differ, and say which trade you are making:
- Thousands of short-lived pods. Kubernetes restarts can churn through worker ids faster than cooldowns release them. Take bits from the sequence: 41 + 13 worker bits (8,192 workers) + 9 sequence bits (512 ids per ms per worker, still 512,000/s per pod).
- Longer lifetime. Sony's Sonyflake uses 39 bits of 10 ms units (174 years), 8 sequence bits and 16 machine bits taken from the private IP address. The price is 10 ms ordering resolution and only 25,600 ids/s per machine.
- One datacenter. Drop the datacenter field and give all 10 bits to workers.
- Need to route by id. Instagram put a 13-bit logical shard id in the machine field and generated ids inside PostgreSQL, so the id itself says which shard holds the row.
Step 6 — High-level design
embedded generator, worker 0"] P2["Chat service pod
embedded generator, worker 1"] P3["ID service
for short-lived clients, worker 2"] FN["Serverless jobs"] -->|"NextIds(100)"| P3 E3[("etcd cluster, dc 3
/idgen/dc3/worker/N leases")] N3["NTP / chrony
slew only, local stratum 1"] P1 -.->|"lease + keepalive"| E3 P2 -.->|"lease + keepalive"| E3 P3 -.->|"lease + keepalive"| E3 N3 -.-> P1 N3 -.-> P2 N3 -.-> P3 end subgraph DC5["Datacenter 5 (dc bits = 00101)"] P4["Order service pod
embedded generator, worker 0"] E5[("etcd cluster, dc 5")] P4 -.-> E5 end P1 --> DB[("Orders DB
BIGINT primary key")] P4 --> DB CFG["Deploy config
datacenter id per region"] -.-> P1 CFG -.-> P4
The hot path is the solid arrow from pod to database: minting is an in-memory operation. The dotted arrows are the control plane, used at startup and for lease keepalives every few seconds. Worker 0 exists in both datacenters and cannot collide, because the datacenter bits differ.
What each component owns
- Embedded generator (in every long-lived service process). Owns the clock check, the sequence counter and the bit packing. Holds a worker lease and stops minting the moment it cannot prove the lease is still valid.
- Per-datacenter etcd or ZooKeeper. Owns worker-id assignment: which process holds worker N in this datacenter, and until when. It is off the hot path: if it is down, generators that already hold leases keep minting until their leases run out, and only new processes cannot start.
- Deploy config. Owns the datacenter id. It is set per region in configuration and never assigned dynamically, because two datacenters claiming the same id would duplicate everything.
- NTP (chrony). Owns keeping clocks close to true time. It is configured to slew (speed up or slow down the clock gradually) rather than step (jump), so the clock never moves backwards under normal operation.
- ID service (optional). The same generator behind an RPC for clients that cannot hold a lease: serverless functions, cron jobs, other languages.
Step 7 — Walk one generator's life end to end
Uniqueness depends on two local checks made on every id: the lease is still valid, and the clock has not gone backwards. Both are done under the same lock that protects the sequence counter.
The order of operations, and why
- Claim the worker id with a compare-and-create. In etcd, a transaction "create key
/idgen/dc3/worker/0only if it does not exist, attached to my lease". Scan 0 to 31 and take the first free slot. In ZooKeeper, create an ephemeral sequential node and use its sequence number modulo the slot count, after checking that the slot is not held. Either way the claim is atomic, so two pods cannot win the same slot. - Wait out the previous owner's time. If the process persisted its last timestamp (or the registry stores the last timestamp each worker used), wait until the local clock is past it before minting. This protects against a restart onto a machine whose clock is behind.
- Check the lease on every id, locally. The generator knows when its lease expires. It stops minting a safety margin (1 s here) before expiry, so a pod that is partitioned from etcd stops before anyone else could take its slot.
- Check the clock on every id. Compare now against the last timestamp used. Wait if slightly behind, refuse if far behind (Step 8).
- Fail readiness when minting fails. The load balancer stops sending traffic to a pod that cannot mint, and the orchestrator restarts it. A pod that returns 503s is fine; a pod that returns duplicates is not.
Step 8 — Low-level design: the generator, in full
Here is a complete generator with the lease registry simulated in memory and the clock injected, so we can move time backwards and forwards on purpose. In production the registry is etcd or ZooKeeper, the clock is time.time_ns() // 1_000_000 and sleeping is real.
import threading
from typing import Callable
# ---------------- bit layout (1 + 41 + 5 + 5 + 12 = 64) ----------------
EPOCH_MS = 1_704_067_200_000 # 2024-01-01T00:00:00Z, our custom epoch
TS_BITS, DC_BITS, WORKER_BITS, SEQ_BITS = 41, 5, 5, 12
MAX_DC = (1 << DC_BITS) - 1 # 31
MAX_WORKER = (1 << WORKER_BITS) - 1 # 31
MAX_SEQ = (1 << SEQ_BITS) - 1 # 4095
WORKER_SHIFT = SEQ_BITS # 12
DC_SHIFT = SEQ_BITS + WORKER_BITS # 17
TS_SHIFT = SEQ_BITS + WORKER_BITS + DC_BITS # 22
class ClockMovedBackwards(Exception): pass
class LeaseLost(Exception): pass
class NoFreeWorkerId(Exception): pass
class LeaseRegistry:
"""Stand-in for etcd / ZooKeeper. In production: an etcd lease with TTL,
or a ZooKeeper ephemeral sequential node under /idgen/dc-3/."""
def __init__(self, clock: Callable[[], int], ttl_ms: int, cooldown_ms: int):
self.clock, self.ttl, self.cooldown = clock, ttl_ms, cooldown_ms
self.slots: dict[tuple[int, int], tuple[str, int]] = {} # (dc, w) -> (owner, expires)
def acquire(self, dc: int, owner: str) -> tuple[int, int]:
now = self.clock()
for w in range(MAX_WORKER + 1):
held = self.slots.get((dc, w))
# Free only if the old lease expired AND the cooldown has passed:
# the old holder may still be minting with a clock that runs behind.
if held is None or now >= held[1] + self.cooldown:
self.slots[(dc, w)] = (owner, now + self.ttl)
return w, now + self.ttl
raise NoFreeWorkerId(f"dc {dc} has no free worker id")
def renew(self, dc: int, w: int, owner: str) -> int | None:
now = self.clock()
held = self.slots.get((dc, w))
if held is None or held[0] != owner or now >= held[1]:
return None # too late: someone may own it now
self.slots[(dc, w)] = (owner, now + self.ttl)
return now + self.ttl
class Snowflake:
def __init__(self, dc: int, worker: int, lease_expires_ms: int,
clock: Callable[[], int], sleep_ms: Callable[[int], None],
max_backwards_wait_ms: int = 10, lease_margin_ms: int = 1_000):
if not (0 <= dc <= MAX_DC and 0 <= worker <= MAX_WORKER):
raise ValueError("dc / worker id out of range")
self.dc, self.worker = dc, worker
self.clock, self.sleep_ms = clock, sleep_ms
self.max_back = max_backwards_wait_ms
self.lease_expires, self.margin = lease_expires_ms, lease_margin_ms
self.last_ms, self.seq = -1, 0
self.lock = threading.Lock() # many request threads, one sequence
self.waits = 0 # metric: how often we stalled
def on_lease_renewed(self, expires_ms: int) -> None:
self.lease_expires = expires_ms
def _wait_until(self, target_ms: int) -> int:
now = self.clock()
while now < target_ms:
self.waits += 1
self.sleep_ms(target_ms - now)
now = self.clock()
return now
def next_id(self) -> int:
with self.lock:
now = self.clock()
# 1. Refuse to mint on a lease we might no longer own.
if now >= self.lease_expires - self.margin:
raise LeaseLost(f"worker {self.dc}/{self.worker} lease expiring")
# 2. Clock went backwards (NTP step, VM pause, manual change).
if now < self.last_ms:
drift = self.last_ms - now
if drift > self.max_back:
raise ClockMovedBackwards(f"clock is {drift} ms behind last id")
now = self._wait_until(self.last_ms) # small blip: just wait it out
# 3. Same millisecond: bump the sequence; on overflow wait for the next ms.
if now == self.last_ms:
self.seq = (self.seq + 1) & MAX_SEQ
if self.seq == 0:
now = self._wait_until(self.last_ms + 1)
else:
self.seq = 0
self.last_ms = now
ts = now - EPOCH_MS
if ts >= (1 << TS_BITS):
raise OverflowError("epoch exhausted: 69 years are up")
return (ts << TS_SHIFT) | (self.dc << DC_SHIFT) | (self.worker << WORKER_SHIFT) | self.seq
def decode(i: int) -> tuple[int, int, int, int]:
return ((i >> TS_SHIFT) + EPOCH_MS, (i >> DC_SHIFT) & MAX_DC,
(i >> WORKER_SHIFT) & MAX_WORKER, i & MAX_SEQ)
# ---------------- demo with a controllable clock ----------------
class FakeClock:
def __init__(self, ms): self.ms = ms
def now(self): return self.ms
def sleep(self, d): self.ms += d # sleeping moves time forward
clk = FakeClock(1_758_585_600_000) # 2025-09-23T00:00:00Z
reg = LeaseRegistry(clk.now, ttl_ms=10_000, cooldown_ms=5_000)
w_a, exp_a = reg.acquire(dc=3, owner="pod-a")
w_b, exp_b = reg.acquire(dc=3, owner="pod-b")
gen_a = Snowflake(3, w_a, exp_a, clk.now, clk.sleep)
gen_b = Snowflake(3, w_b, exp_b, clk.now, clk.sleep)
print("worker ids:", w_a, w_b)
ids = [gen_a.next_id() for _ in range(3)] + [gen_b.next_id()]
for i in ids:
print(i, decode(i))
# Sequence overflow: 4097 ids inside one frozen millisecond.
start = clk.ms
burst = [gen_a.next_id() for _ in range(4097)]
print("burst: last decoded", decode(burst[-1])[1:], "moved", clk.ms - start, "ms, waits", gen_a.waits)
# Small backwards step (NTP correction of 4 ms): absorbed by waiting.
clk.ms -= 4
x = gen_a.next_id()
print("after -4 ms blip: ok, waits now", gen_a.waits)
# Large backwards step (2 s): refuse rather than risk duplicates.
clk.ms -= 2_000
try:
gen_a.next_id()
except ClockMovedBackwards as e:
print("ClockMovedBackwards:", e)
clk.ms += 2_000
# Pod A freezes (GC pause / network partition) and never renews.
clk.ms += 9_500
try:
gen_a.next_id()
except LeaseLost as e:
print("LeaseLost:", e)
# A replacement pod starts right away. Slot 0 is expired but still cooling down.
w_c, _ = reg.acquire(dc=3, owner="pod-c")
print("pod-c got worker id", w_c, "(not 0: cooldown protects against pod-a's stale clock)")
# Uniqueness + per-worker monotonicity under interleaving.
clk.ms += 1
reg.renew(3, w_b, "pod-b")
gen_b.on_lease_renewed(clk.ms + 10_000)
mixed = []
for n in range(50_000):
mixed.append(gen_b.next_id())
if n % 7 == 0: clk.ms += 1
print("50,000 ids unique:", len(set(mixed)) == len(mixed), "| strictly increasing:",
all(a < b for a, b in zip(mixed, mixed[1:])))worker ids: 0 1 228666743193993216 (1758585600000, 3, 0, 0) 228666743193993217 (1758585600000, 3, 0, 1) 228666743193993218 (1758585600000, 3, 0, 2) 228666743193997312 (1758585600000, 3, 1, 0) burst: last decoded (3, 0, 3) moved 1 ms, waits 1 after -4 ms blip: ok, waits now 2 ClockMovedBackwards: clock is 2000 ms behind last id LeaseLost: worker 3/0 lease expiring pod-c got worker id 2 (not 0: cooldown protects against pod-a's stale clock) 50,000 ids unique: True | strictly increasing: True
The details an interviewer is listening for
- One lock around read-clock, compare, bump, pack. Without it, two threads can read the same millisecond and the same sequence value and return the same id. The critical section is a handful of integer operations, so the lock is not a bottleneck: a single thread can do several million per second. Lock-free versions use one atomic compare-and-swap on a 64-bit word holding (last_ms, seq).
- Sequence overflow waits for the next millisecond. The 4,097th id in one millisecond waited 1 ms and came back with seq 0 in the next millisecond. An older version of this code in many blog posts "borrows" the next millisecond by adding 1 to the timestamp without waiting; that works until the clock catches up and the same (ms, seq) pair is issued a second time.
- Small backwards jumps are waited out, large ones are refused. A 4 ms step back cost a 4 ms stall. A 2-second step back raised an error, because stalling every request for 2 seconds is worse than failing fast and letting the load balancer route around this pod.
- The lease is checked locally with a margin. The frozen pod refused to mint at 9.5 s into a 10 s lease. It does not need to reach etcd to know it must stop, which is what makes this safe during a partition.
- The cooldown keeps a new pod off a slot that was just released. pod-c got worker 2, not worker 0. Step 9 explains the duplicate this prevents.
- Starting the sequence at 0 every millisecond has a side effect. At low traffic almost every id ends in sequence 0, so
id % 16is almost always the same value. If anyone shards or partitions byid % N, all rows go to one shard. Hash the id before taking the modulus, or start each millisecond's sequence at a small random value.
Decoding an id
Because the fields sit at fixed positions, any id can be taken apart with shifts and masks. This is useful for debugging ("which pod minted this broken order?") and, more importantly, for turning time ranges into primary-key ranges: all orders created on a given day lie between two ids you can compute, so the query uses the primary-key index and needs no separate created_at index.
from datetime import datetime, timezone
EPOCH_MS = 1_704_067_200_000
TS_SHIFT, DC_SHIFT, WORKER_SHIFT = 22, 17, 12
def explain(i: int) -> dict:
ms = (i >> TS_SHIFT) + EPOCH_MS
return {
"created": datetime.fromtimestamp(ms / 1000, timezone.utc).isoformat(timespec="milliseconds"),
"datacenter": (i >> DC_SHIFT) & 0x1F,
"worker": (i >> WORKER_SHIFT) & 0x1F,
"sequence": i & 0xFFF,
"binary": f"{i:064b}",
}
def min_id_at(dt: datetime) -> int:
"""Smallest possible id minted at or after dt. Lets you turn a time range
into a primary-key range: WHERE id >= min_id_at(a) AND id < min_id_at(b)."""
ms = int(dt.timestamp() * 1000)
return (ms - EPOCH_MS) << TS_SHIFT
sample = 228666743193997312
for k, v in explain(sample).items():
print(f"{k:>10}: {v}")
b = explain(sample)["binary"]
print(" layout :", b[0], b[1:42], b[42:47], b[47:52], b[52:])
print(" ", "s", "timestamp (41 bits)".ljust(41), "dc".ljust(5), "wkr".ljust(5), "seq (12)")
day_start = datetime(2025, 9, 23, tzinfo=timezone.utc)
day_end = datetime(2025, 9, 24, tzinfo=timezone.utc)
print(f"\nSELECT * FROM orders WHERE id >= {min_id_at(day_start)} AND id < {min_id_at(day_end)};")
print("ids per ms of timestamp:", 1 << TS_SHIFT, "(so a 1-day range spans",
f"{(min_id_at(day_end) - min_id_at(day_start)):,} id values)") created: 2025-09-23T00:00:00.000+00:00
datacenter: 3
worker: 1
sequence: 0
binary: 0000001100101100011000110011000100000000000001100001000000000000
layout : 0 00000110010110001100011001100010000000000 00011 00001 000000000000
s timestamp (41 bits) dc wkr seq (12)
SELECT * FROM orders WHERE id >= 228666743193600000 AND id < 229029131059200000;
ids per ms of timestamp: 4194304 (so a 1-day range spans 362,387,865,600,000 id values)
Keep a created_at column anyway if the business needs the exact time of an event. The id timestamp is the time the id was minted, which can be seconds before the row was committed, and it comes from a clock that might have been slightly wrong.
Step 9 — Clocks, worker ids and datacenter bits
Clock skew and NTP
Snowflake trusts each machine's wall clock, and wall clocks misbehave in several distinct ways. Know them by name:
- NTP step. If the clock is far off (by default more than 128 ms for ntpd), NTP may step it, jumping it backwards or forwards at once. Configure chrony with
makesteplimited to the first few updates after boot, so later corrections are always slewed, which adjusts the rate gradually and never moves the clock backwards. - Leap seconds. A clock that repeats 23:59:59 goes back one second. Google and AWS "smear" leap seconds over many hours instead, which slews rather than steps. Use a smeared time source, or accept a one-second refusal window.
- VM pauses and live migration. A paused VM resumes with its clock behind, then NTP corrects it, sometimes with a step.
- Drift between machines. With decent NTP, machines in one datacenter agree to within about a millisecond; across datacenters to within a few milliseconds. This drift does not break uniqueness (worker bits separate machines), but it limits ordering: an id minted on a machine whose clock is 3 ms ahead sorts after ids minted up to 3 ms later elsewhere. That is the "roughly" in "roughly sorted".
- A human runs
date -s. It happens. The backwards check catches it.
What to do when the clock goes backwards, from gentlest to strictest:
- Wait if the gap is small (a few ms). The code above does this.
- Refuse and alert if it is large. Return an error, fail readiness, and page someone if it repeats.
- Keep going on a logical clock. Some implementations keep issuing ids from
last_ms, advancing it on sequence overflow, until the wall clock catches up. This keeps availability, at the cost of ids whose timestamps run ahead of real time for a while. It is safe for uniqueness because the generator never reuses a (last_ms, seq) pair it has issued, but only for the life of the process. - Persist
last_msto local disk every few seconds (writing "now + 5 s" as a promise not to go below it). On restart, wait until the clock passes the stored value. This closes the gap that option 3 leaves open across restarts.
A wrong answer candidates often give: "use a monotonic clock". A monotonic clock (CLOCK_MONOTONIC) never goes backwards within one boot, but it counts from an arbitrary point (usually boot time), so it is not comparable across machines or restarts. You can use it to measure elapsed time since a trusted wall-clock reading at startup, which is a reasonable hardening, but it does not replace the wall clock.
Worker-id assignment, and the danger of reuse
Uniqueness depends on this invariant: at no moment do two live processes mint with the same (datacenter, worker) pair. Static configuration (worker id in a config file, or derived from the hostname) satisfies it on a fixed fleet and breaks as soon as autoscaling, blue-green deploys or a copy-pasted config arrive. Deriving it from the last bits of an IP address (Sonyflake's default) breaks when IPs are reused across a large network. Leases are the robust answer:
- etcd: grant a lease with a TTL of about 10 s, create
/idgen/dc3/worker/Nin a transaction that fails if the key exists, and send keepalives every 3 s. When the process dies, keepalives stop and the key disappears after the TTL. - ZooKeeper: an ephemeral node under
/idgen/dc3/, tied to the session; the node vanishes when the session times out. - Plain SQL: a table of
(worker_id, owner, expires_at)updated withUPDATE ... WHERE worker_id = ? AND (owner = ? OR expires_at < now() - cooldown)androwcount = 1as the success test. Works fine at this scale if you already have a reliable database.
The subtle failure is reuse too soon. Picture this sequence:
- Pod A holds worker 7 and has minted ids up to wall time 12:00:05.000.
- Pod A is partitioned from etcd (or stalls in a long garbage-collection pause). Its lease expires at 12:00:06. If A does not check its own lease, it keeps minting.
- At 12:00:06 pod B takes worker 7. B's clock happens to be 400 ms behind A's.
- B mints (12:00:05.700, worker 7, seq 0). A minted exactly that triple 300 ms ago. Duplicate id.
Two defences close this, and you need both. First, the old holder fences itself: it stops minting a margin before its own lease expiry, measured on a monotonic clock, so a partitioned pod stops on its own. Second, a released slot cools down before reuse, for longer than the maximum clock skew plus the lease margin (the registry above uses 5 s). A third belt-and-braces option is to store each worker's last-used timestamp in the registry, and have a new owner wait until its clock passes it. Note that a long pause is still dangerous for a process that checks its lease, reads the clock, and then freezes for 30 seconds before returning the id. The id is still unique, because it carries the old timestamp and the slot was fenced; what breaks is only ordering, which is acceptable.
Datacenter bits
Giving each datacenter its own 5-bit id means worker-id assignment is local to each datacenter: dc 3's etcd never talks to dc 5's. A cross-region partition therefore cannot affect id generation at all, which is exactly the availability requirement. The datacenter id must come from deploy configuration, reviewed like a schema change, because the failure mode of two regions sharing one (a new region copied from an old one's config) is duplicate ids across the whole company. Add a startup check: the generator refuses to start if its datacenter id does not match the region its metadata service reports.
If you have only one or two regions, the 5 dc bits are wasted. Fold them into the worker field and run one registry per region with worker ranges assigned per region (dc 3 uses 0 to 511, dc 5 uses 512 to 1023).
Step 10 — Why time order matters: index locality
"Sortable ids are nice for pagination" is true but not the main reason. The main reason is what random keys do to a B-tree. InnoDB stores rows in primary-key order (a clustered index), and PostgreSQL's primary-key index is a B-tree as well. Inserting a new key means finding the leaf page it belongs in. With time-ordered keys that is always the rightmost page, which is already in memory. With random keys it is any page in the index, which is usually not in memory once the index is larger than the buffer pool. The simulation below inserts 200,000 keys into leaf pages of 100 keys each, splitting a full page in half as B-trees do:
import bisect, random
PAGE_CAPACITY = 100 # keys per leaf page (a 16 KB InnoDB page holds a few hundred)
def build_leaves(keys):
"""Insert keys one by one into B-tree leaf pages. Like InnoDB, a full page
splits 50/50 -- except when the insert lands at the far right end of the
rightmost page, where it just starts a fresh page (an 'append split')."""
firsts, pages = [], [] # first key of each page, and the pages
splits = touched_old_pages = 0
for k in keys:
if not pages:
firsts.append(k); pages.append([k]); continue
p = max(0, bisect.bisect_right(firsts, k) - 1)
page = pages[p]
if p != len(pages) - 1:
touched_old_pages += 1 # writing into the middle of the index
if len(page) < PAGE_CAPACITY:
bisect.insort(page, k)
elif p == len(pages) - 1 and k > page[-1]:
firsts.append(k); pages.append([k]) # append: no data moves
else:
splits += 1
bisect.insort(page, k)
half = len(page) // 2
new = page[half:]; del page[half:]
pages.insert(p + 1, new); firsts.insert(p + 1, new[0])
firsts[p] = pages[p][0]
fill = sum(map(len, pages)) / (len(pages) * PAGE_CAPACITY)
return len(pages), splits, fill, touched_old_pages
N = 200_000
rng = random.Random(42)
sequential = list(range(N)) # Snowflake / UUIDv7 / auto-increment
random_keys = [rng.getrandbits(122) for _ in range(N)] # UUIDv4
for name, keys in (("time-ordered", sequential), ("random UUIDv4", random_keys)):
pages, splits, fill, mid = build_leaves(keys)
print(f"{name:14s} pages={pages:5d} 50/50 splits={splits:5d} "
f"avg fill={fill:5.1%} inserts into non-tail pages={mid:,}")time-ordered pages= 2000 50/50 splits= 0 avg fill=100.0% inserts into non-tail pages=0 random UUIDv4 pages= 2862 50/50 splits= 2860 avg fill=69.9% inserts into non-tail pages=199,393
Read the three numbers:
- Fill factor. Random keys leave pages about 70% full on average, the long-known result for random B-tree inserts, so the same data needs about 43% more pages, on disk and in cache. Time-ordered keys fill each page almost completely, because InnoDB and PostgreSQL both detect inserts at the right edge and start a new page instead of splitting it in half (PostgreSQL deliberately leaves 10% free on those pages by default).
- Page splits. 2,860 splits against zero. Each split allocates a page, moves half the rows, updates the parent and writes all of it to the redo log and replicas.
- Where writes land. Almost every random insert touched an old page somewhere in the middle of the index. On a 500 GB table with a 64 GB buffer pool, most of those are a disk read before the write can happen. This is the familiar story of a UUIDv4-keyed table whose insert rate drops as it grows, while an identical table with sequential keys stays flat.
The same locality helps reads: "latest 20 orders" reads a handful of adjacent pages, and time-range scans on the id are sequential I/O. That is what k-sortable buys: ids created close together in time are stored close together.
Step 11 — Security: ids are not secrets
Every structured id leaks something. Decide which ids are allowed to leave your network.
- Enumeration. If
/invoices/1041works, someone will try/invoices/1042. With Snowflake ids they cannot guess the next id exactly, but they can narrow it: the timestamp is known to the millisecond, worker and datacenter are small ranges, and the sequence is usually 0. Walking a few thousand candidates per second is cheap. The fix is authorisation, checking on every request that the caller may see that object. Unguessable ids are defence in depth on top of that, never a replacement. Accessing another user's object by changing an id in the URL (insecure direct object reference) is one of the most common API vulnerabilities in the OWASP API Security Top 10. - Business intelligence leakage. Sequential ids tell a competitor how many orders you took this week: sign up on Monday, again on Friday, subtract. In the Second World War the Allies estimated German tank production from the serial numbers on captured tanks (the "German tank problem"), and it works just as well on order numbers. Snowflake ids leak creation time and, through the worker bits, roughly how many generators you run.
- Timing and correlation. An account id that encodes its creation millisecond can link a user's accounts or reveal when they signed up.
Three ways to expose ids safely, from simplest to most flexible:
- A separate random public id. Keep the Snowflake id as the internal primary key and add a unique
public_idcolumn holding a UUIDv4 or a random base62 string. Costs one extra unique index and a lookup on every public request. - Encrypt the id. A keyed permutation of 64-bit integers (a small block cipher over 64 bits, or a Feistel network) maps every internal id to exactly one public id and back, with no lookup table:
import hmac, hashlib
SECRET = b"rotate-me-and-keep-me-in-a-kms" # demo key; never hard-code a real one
MASK32 = 0xFFFFFFFF
ALPHABET = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
def _round(half: int, r: int) -> int:
msg = r.to_bytes(1, "big") + half.to_bytes(4, "big")
return int.from_bytes(hmac.new(SECRET, msg, hashlib.sha256).digest()[:4], "big")
def encrypt64(x: int, rounds: int = 4) -> int:
"""Feistel network: a keyed bijection on 64-bit integers. Every internal id maps
to exactly one public id and back, so no lookup table and no collisions."""
left, right = x >> 32, x & MASK32
for r in range(rounds):
left, right = right, left ^ _round(right, r)
return (left << 32) | right
def decrypt64(y: int, rounds: int = 4) -> int:
left, right = y >> 32, y & MASK32
for r in reversed(range(rounds)):
left, right = right ^ _round(left, r), left
return (left << 32) | right
def base62(n: int) -> str:
out = ""
while True:
n, rem = divmod(n, 62)
out = ALPHABET[rem] + out
if n == 0:
return out
internal = [228666743193993216, 228666743193993217, 228666743193993218]
for i in internal:
pub = encrypt64(i)
assert decrypt64(pub) == i
print(f"internal {i} -> public {base62(pub):>11} (plain base62 {base62(i)})")internal 228666743193993216 -> public 4TWIIa6wNwO (plain base62 GtIMFG0PfE) internal 228666743193993217 -> public H4hG7PghLyS (plain base62 GtIMFG0PfF) internal 228666743193993218 -> public 8qcMGYz6OKL (plain base62 GtIMFG0PfG)
Consecutive internal ids produce unrelated public ids, and the server decrypts on the way in. Rotating the key changes every public URL, so treat the key like a schema: version it, and prefix public ids with the key version. Do not invent your own cipher for real use; use a vetted construction for small blocks (for example a format-preserving encryption mode) and treat the demo as the idea only.
- Signed tokens for ids that should expire or be scoped (share links, password-reset links): include the id, an expiry and an HMAC signature. That is a capability, not an identifier, and it belongs in the API design discussion.
Step 12 — Failure modes
| What fails | What happens | Mechanism |
|---|---|---|
| Clock steps back a few ms | A short stall on that pod | Wait until the clock passes last_ms |
| Clock steps back seconds | That pod returns 503 and leaves the pool | Refuse beyond a threshold, fail readiness, alert; chrony configured to slew only |
| Process restarts on a machine whose clock is behind | Would reuse (ms, worker, seq) triples | Persisted last_ms or registry-stored last timestamp; wait at startup |
| etcd or ZooKeeper down | Running pods keep minting; new pods cannot start | Leases outlive short outages; alert; keep TTL long enough to ride out a leader election |
| Pod partitioned from etcd | Pod stops minting before its lease expires | Local lease check with a safety margin (self-fencing) |
| Worker id reused too soon | Duplicate ids if clocks disagree | Cooldown longer than max skew plus margin before a slot is reusable |
| Two regions configured with the same dc id | Duplicates across the whole company | dc id in reviewed config; startup check against cloud metadata |
| All 1,024 worker slots in use | New pods cannot start | Alert at 70% utilisation; re-budget bits (13 worker, 9 sequence); fall back to the ID service |
| Burst above 4,096 ids/ms on one pod | Callers wait up to 1 ms | Normal behaviour; a sustained rate means batch through next_ids(n) or add pods |
| VM image cloned with the generator state | Two processes share state | Worker id always acquired at runtime, never baked into an image |
| Epoch runs out | OverflowError around the year 2093 | Documented epoch; alert decades ahead; migration plan to a new layout |
| Duplicate id reaches the database anyway | Insert fails on the primary-key constraint | The constraint is the last line of defence: never disable it, and alert on duplicate-key errors on id columns |
Step 13 — Observability
- Clock health: NTP offset per host (alert above 50 ms), count of backwards-clock events, and time spent waiting for the clock. A rising wait count is the earliest sign of a bad time source.
- Sequence pressure: the fraction of milliseconds that hit sequence overflow, per pod. Near zero is normal; a steady non-zero value means one pod is doing the work of several.
- Lease health: keepalive latency and failures, lease time remaining, and
LeaseLostevents. - Slot utilisation: worker ids in use per datacenter against the maximum, including those in cooldown.
- Correctness canary: a background job that samples recently inserted ids, decodes them, and checks that the decoded time is within a few seconds of
created_atand that the dc and worker match a registered pod. It catches misconfiguration long before a collision does. - Duplicate-key errors on id columns, as their own alert. They should be zero forever.
The trade-off summary — how to close
- Snowflake over UUIDv4 because we need 64-bit, time-ordered keys: half the index size, no page-split storm and time-range queries for free. We pay with a dependency on clocks and a worker-id registry.
- Snowflake over a ticket server because we ruled out a network hop per id. The ticket server gives stricter ordering and no clock dependency; it is a fine answer if the interviewer relaxes the latency requirement.
- UUIDv7 if 128 bits is allowed. It gives most of Snowflake's benefits with no registry at all. Say this: it shows you know the current state of the art.
- A key generation service for short public codes, because short random codes collide quickly and must not reveal order.
- Rough ordering, not strict. Ids are ordered to within clock skew (about a millisecond inside a datacenter, a few across). Anything that needs a strict total order across machines needs a single sequencer or a consensus log, and we say so rather than pretending.
- Fail closed. Every uncertain situation (clock behind, lease unknown, slot exhausted) produces an error rather than a possibly duplicate id, with the primary-key constraint as the final safety net.
- Internal ids are not public ids. Snowflake ids stay inside; the outside world sees an encrypted or separate random id, and authorisation is checked on every request anyway.
These ids appear throughout the rest of the course: as order ids in the food delivery capstone, as tweet ids in the news feed, as message ids that give a per-conversation order in chat, and next, as the source of short codes in the URL shortener.
// Write your solution here
// Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
