Distributed systems
Part 6 of 6 · Time, Clocks & OrderingDistributed ID Generation - Snowflake, UUIDv4 vs UUIDv7, ULID, KSUID & Sequences
ID schemes compared (sequences, hi-lo, Flickr ticket servers, Snowflake, Instagram, UUIDv4, UUIDv7/RFC 9562, ULID, KSUID); runnable Snowflake with sequence overflow and clock-rollback handling; runnable UUIDv7 with monotonic counter plus B-tree right-edge locality vs UUIDv4; ordering vs locality vs coordination; hot-partition twist; JS 2^53 pitfall.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Why are UUIDv4 primary keys hard on a B-tree?
Answer
Random keys hit random leaves: more splits, a larger cache working set, and more write amplification.
L2
Walk through a Snowflake ID.
Answer
1 sign bit, 41 bits of milliseconds since a custom epoch, 10 bits of worker, 12 bits of sequence. 4096 IDs per millisecond per worker.
L3
What do you do when the clock moves backwards?
Answer
Wait if the gap is within the small policy, otherwise refuse and alert. Never reset the sequence on a timestamp you might reuse.
L4
How do UUIDv7 and ULID differ?
Answer
Both lead with 48 bits of milliseconds. UUIDv7 is RFC 9562 and fits UUID columns. ULID is a community spec with a 26-character Crockford base32 form.
L5
When is a database sequence still the right call?
Answer
A single database, compact strictly increasing IDs, and you already accept that database as the bottleneck. Hi-lo or cached blocks cut contention.
L6
What did the locality demo measure?
Answer
10,000 inserts. UUIDv7 appended at the right edge 100.0 percent of the time. UUIDv4 did so 0.1 percent of the time. The UUIDv7 generator used a seeded PRNG.
L7
What fails if two workers share an ID?
Answer
They can mint the same Snowflake in the same millisecond. Lease worker IDs, and do not copy a worker ID into a recycled container.
Failure modes
A large NTP step would reuse a millisecond
The example refuses a 2000 ms rollback instead of issuing IDs. A 3 ms rollback waits until last_ms.
Sequence overflow stalls the millisecond
After 4096 IDs the next ID is forced into the following millisecond with sequence 0.
A monotonic key is the shard key
All inserts land on the newest range. Spread writes with a hash or a random prefix instead.
Misconceptions
UUIDv7 is random like UUIDv4.
The high 48 bits are Unix time in milliseconds, so new IDs sort after old ones and cluster on the right edge of a B-tree.
Right-edge locality is always good.
It helps one B-tree and hotspots a range-partitioned store.
A 64-bit ID is safe in JSON numbers.
JavaScript cannot represent every integer above 2^53 - 1. Send strings.
Interviewer traps
Recommending UUIDv4 as a clustered primary key on a write-heavy table.
Show the right-edge contrast and offer UUIDv7, ULID, or Snowflake.
Ignoring clock rollback in a Snowflake design.
Wait for a few milliseconds, refuse a large jump, and persist last_ms across restarts.
Design scenario
Same prompt for every reader.
Requirements
IDs are unique without a database round trip on every insert. New rows should not scatter across a single B-tree. The shard key must not be the hottest range.
Traffic / scale
Example Snowflake worker 37, with a burst of 4096 IDs in one millisecond.
Latency
Minting is local unless you call a ticket server or a sequence. Overflow waits one millisecond.
Consistency
Uniqueness requires a unique worker ID or enough random bits. Ordering is k-sorted, not a single global sequence.
Availability
A central ticket service is a dependency on every insert. Local Snowflake or UUIDv7 is not.
Failure assumptions
- NTP can step the clock backwards.
- A worker ID can be copied onto a second process.
- Clients may be JavaScript and will parse JSON numbers.
Constraints
- Do not use UUIDv4 as the clustered primary key.
- Do not use the raw Snowflake ID as a range-partition key.
Prompt
Design IDs for a URL shortener that also stores rows in a B-tree and may later shard by key range.
API
What string or integer do you return to the client, and in what encoding?
Data
Which bits are time, worker, and sequence, and what is the epoch?
Architecture
Where are worker IDs leased, and what is the shard key if it is not the ID?
Where the next insert lands
Prefer
Time in the high bits for one B-tree
UUIDv7, ULID, and Snowflake append near the right edge, so the hot leaf stays in cache.
- The seeded demo inserts UUIDv7 at the right edge 100 percent of the time.
- UUIDv4 in the same demo lands on the right edge 0.1 percent of the time.
- Lexical order of the UUIDv7 samples matches creation order.
Alternative
The same monotonic ID as a range key
Every new write goes to the newest partition. Bigtable and HBase schema guides warn against monotonically increasing row keys.
- A clustered B-tree wants the right edge.
- A range-partitioned store wants the writes spread out.
- UUIDv4 spreads them and scatters the single-node index.
From the clock to a Snowflake ID
Wait out a few milliseconds of rollback. Refuse a large jump. Overflow the 12-bit sequence into the next millisecond.
- 1
Read now and compare with last_ms
If the clock moved backwards more than the example 5 ms policy, refuse. A 3 ms step waits until last_ms. - 2
Bump the sequence inside the millisecond
4096 IDs use the 12-bit sequence. The next ID waits for the following millisecond and starts at sequence 0. - 3
Pack time, worker, and sequence
Shift the milliseconds since the custom epoch by 22, the worker by 12, and OR the sequence. - 4
Do not recycle the worker
Two processes with the same worker ID and the same millisecond can emit the same ID. A copied container config is the classic bug.
Overview
Almost every system needs unique IDs, and the choice quietly decides three things: ordering (can I sort by ID to get creation order?), index locality (do new rows land at the end of the B-tree or randomly all over it?), and coordination (does generating an ID need a network call?). Random UUIDv4 needs no coordination but scatters inserts. Database sequences are compact and ordered but centralize. Time-ordered schemes (Snowflake, UUIDv7, ULID, KSUID) sit in between and inherit every clock problem from this cluster, especially the clock moving backwards.
The options at a glance
| Scheme | Size | Layout | Sortable by time | Coordination | Notes |
|---|---|---|---|---|---|
| DB auto-increment / sequence | 8 bytes | Counter | Yes (per sequence) | Central database | Simple; leaks volume; single point of contention |
| Hi-lo / sequence blocks | 8 bytes | Fetch a block of N ids, hand out locally | Roughly | One call per block | Hibernate hi/lo, pooled optimizers; gaps on restart |
| Ticket servers (Flickr 2010) | 8 bytes | Two MySQL servers, odd/even via auto-increment offset | Roughly | Small dedicated service | Cheap and boring; still a service to run |
| Snowflake (Twitter 2010) | 8 bytes | 41-bit ms time, 10-bit worker, 12-bit sequence | Yes (k-sorted) | Assign worker ids once | 4096 ids per ms per worker; depends on clocks |
| Instagram-style (2012) | 8 bytes | 41-bit ms time, 13-bit logical shard, 10-bit sequence, in PostgreSQL | Yes | Shard owns sequence | Generated inside the database per shard |
| UUIDv4 | 16 bytes | 122 random bits | No | None | Great uniqueness, poor B-tree locality |
| UUIDv7 (RFC 9562, 2024) | 16 bytes | 48-bit Unix ms, version, 74 random/counter bits | Yes | None | Standard UUID type, time-ordered |
| ULID | 16 bytes (26 chars Crockford base32) | 48-bit ms + 80 random bits | Yes | None | Monotonic variant increments within a ms |
| KSUID (Segment) | 20 bytes (27 chars base62) | 32-bit seconds since a custom epoch + 128 random bits | Yes (second resolution) | None | Larger, very low collision risk |
How a Snowflake-style generator works
Decisions
- 1
Step 1: read clock now_ms
- nextStep 2: now_ms < last_ms (clock went backwards)?
- ?
Step 2: now_ms < last_ms (clock went backwards)?
- yes, a few msStep 3a: wait until last_ms
- yes, large jumpStep 3b: refuse, alert, drain this worker
- noStep 4: now_ms == last_ms?
- 3
Step 3a: wait until last_ms
- nextStep 4: now_ms == last_ms?
- 4
Step 3b: refuse, alert, drain this worker
- ?
Step 4: now_ms == last_ms?
- yesStep 5a: sequence += 1
- no, new msStep 5b: sequence = 0
- 6
Step 5a: sequence += 1
- nextStep 6: sequence overflowed 4095?
- ?
Step 6: sequence overflowed 4095?
- yesStep 7: wait for next millisecond, sequence = 0
- noStep 8: id = time << 22 | worker << 12 | sequence
- 8
Step 7: wait for next millisecond, sequence = 0
- nextStep 8: id = time << 22 | worker << 12 | sequence
- 9
Step 8: id = time << 22 | worker << 12 | sequence
- 10
Step 5b: sequence = 0
- nextStep 8: id = time << 22 | worker << 12 | sequence
Lesson map
Distributed ID Generation - Snowflake, UUIDv4 vs UUIDv7, ULID, KSUID & Sequences
ID schemes compared (sequences, hi-lo, Flickr ticket servers, Snowflake, Instagram, UUIDv4, UUIDv7/RFC 9562, ULID, KSUID); runnable Snowflake with sequence overflow and clock-rollback handling; runnable UUIDv7 with monotonic counter plus B-tree right-edge locality vs UUIDv4; ordering vs locality vs coordination; hot-partition twist; JS 2^53 pitfall.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB n["Step 1: read clock now_ms"] b["Step 2: now_ms < last_ms (clock went backwards)?"] wait["Step 3a: wait until last_ms"] ref["Step 3b: refuse, alert, drain this worker"] s["Step 4: now_ms == last_ms?"] inc["Step 5a: sequence += 1"] ov["Step 6: sequence overflowed 4095?"] next["Step 7: wait for next millisecond, sequence = 0"] pack["Step 8: id = time << 22 worker << 12 sequence"] zero["Step 5b: sequence = 0"] n -->|continues| b b -->|yes, a few ms| wait b -->|yes, large jump| ref b -->|no| s wait -->|continues| s s -->|yes| inc inc -->|continues| ov ov -->|yes| next ov -->|no| pack s -->|no, new ms| zero next -->|continues| pack zero -->|continues| pack
Snowflake with clock-rollback handling (runnable)
# A Snowflake-style 64-bit ID generator with an injectable clock so we can test
# sequence overflow and clock rollback. Layout (Twitter's original):
# 1 sign bit | 41 bits ms since custom epoch | 10 bits worker id | 12 bits sequence
EPOCH_MS = 1_288_834_974_657 # Twitter's published Snowflake epoch (Nov 2010)
WORKER_BITS, SEQ_BITS = 10, 12
MAX_SEQ = (1 << SEQ_BITS) - 1 # 4095 IDs per ms per worker
MAX_BACKWARD_WAIT_MS = 5 # tolerate tiny rollbacks by waiting (example policy)
class ClockMovedBackwards(Exception):
pass
class Snowflake:
def __init__(self, worker_id: int, clock):
assert 0 <= worker_id < (1 << WORKER_BITS)
self.worker, self.clock = worker_id, clock
self.last_ms, self.seq = -1, 0
def next_id(self) -> int:
now = self.clock.ms()
if now < self.last_ms:
behind = self.last_ms - now
if behind > MAX_BACKWARD_WAIT_MS:
# Refuse rather than risk duplicate IDs; alert, and let the LB route elsewhere.
raise ClockMovedBackwards(f"clock moved back {behind} ms; refusing to issue IDs")
self.clock.wait_until(self.last_ms) # small rollback: just wait it out
now = self.clock.ms()
if now == self.last_ms:
self.seq = (self.seq + 1) & MAX_SEQ
if self.seq == 0: # 4096 IDs used this ms: wait for next ms
self.clock.wait_until(self.last_ms + 1)
now = self.clock.ms()
else:
self.seq = 0
self.last_ms = now
return ((now - EPOCH_MS) << (WORKER_BITS + SEQ_BITS)) | (self.worker << SEQ_BITS) | self.seq
def decode(i: int):
return {"ms": (i >> 22) + EPOCH_MS, "worker": (i >> 12) & 0x3FF, "seq": i & MAX_SEQ}
class FakeClock:
def __init__(self, ms): self.t = ms
def ms(self): return self.t
def wait_until(self, target): self.t = max(self.t, target) # pretend we slept
clk = FakeClock(1_759_850_000_000) # an example instant in Oct 2025
gen = Snowflake(worker_id=37, clock=clk)
ids = [gen.next_id() for _ in range(3)]
print("ids :", ids)
print("decoded :", decode(ids[0]), decode(ids[2]))
print("sorted by time == sorted numerically:", ids == sorted(ids))
for _ in range(MAX_SEQ + 1 - len(ids)): # use up the rest of this millisecond (4096 total)
gen.next_id()
spill = gen.next_id()
print("after 4096 in one ms, next id lands in ms +1:", decode(spill)["ms"] - decode(ids[0])["ms"], "seq", decode(spill)["seq"])
clk.t -= 3 # NTP stepped back 3 ms: tolerated by waiting
print("3 ms rollback ->", decode(gen.next_id()))
clk.t -= 2_000 # 2 s rollback: refuse
try:
gen.next_id()
except ClockMovedBackwards as e:
print("2 s rollback ->", e)
years = (1 << 41) / 1000 / 86400 / 365.25
print(f"41-bit ms timestamp lasts ~{years:.1f} years from the custom epoch")Output:
ids : [1975580204856397824, 1975580204856397825, 1975580204856397826]
decoded : {'ms': 1759850000000, 'worker': 37, 'seq': 0} {'ms': 1759850000000, 'worker': 37, 'seq': 2}
sorted by time == sorted numerically: True
after 4096 in one ms, next id lands in ms +1: 1 seq 0
3 ms rollback -> {'ms': 1759850000001, 'worker': 37, 'seq': 1}
2 s rollback -> clock moved back 2000 ms; refusing to issue IDs
41-bit ms timestamp lasts ~69.7 years from the custom epochDesign notes: worker ids must be unique, so assign them from configuration, a coordination service (ZooKeeper/etcd lease), or a database row, and make sure two processes can never run with the same id (a recycled container with a copied config is the classic duplicate-ID bug). Persisting last_ms across restarts protects against a restart combined with a backwards clock.
UUIDv7 and index locality (runnable)
// UUIDv7 (RFC 9562): 48-bit Unix ms timestamp | ver(4)=7 | rand_a(12) | var(2)=10 | rand_b(62).
// We use rand_a as a 12-bit counter within the same millisecond (RFC 9562 "Method 1",
// fixed-length dedicated counter) so IDs from one generator are strictly increasing.
// A SEEDED PRNG keeps this demo's output reproducible; production code must use
// crypto.getRandomValues (or your platform's CSPRNG).
let seed = 42;
function prngByte(): number { // xorshift32, demo only
seed ^= seed << 13; seed >>>= 0; seed ^= seed >>> 17; seed ^= seed << 5; seed >>>= 0;
return seed & 0xff;
}
let lastMs = -1;
let counter = 0;
function uuidv7(ms: number): string {
if (ms === lastMs) counter++; else { counter = prngByte() & 0x3f; lastMs = ms; } // random start, room to grow
const b = new Uint8Array(16);
for (let i = 0; i < 6; i++) b[i] = Math.floor(ms / 2 ** (8 * (5 - i))) & 0xff; // big-endian ms
b[6] = 0x70 | ((counter >> 8) & 0x0f); // version 7 + high 4 bits of counter
b[7] = counter & 0xff;
for (let i = 8; i < 16; i++) b[i] = prngByte();
b[8] = (b[8]! & 0x3f) | 0x80; // RFC variant bits 10xx
const h = [...b].map((x) => x.toString(16).padStart(2, "0")).join("");
return `${h.slice(0, 8)}-${h.slice(8, 12)}-${h.slice(12, 16)}-${h.slice(16, 20)}-${h.slice(20)}`;
}
function uuidv4(): string {
const b = new Uint8Array(16);
for (let i = 0; i < 16; i++) b[i] = prngByte();
b[6] = (b[6]! & 0x0f) | 0x40; b[8] = (b[8]! & 0x3f) | 0x80;
const h = [...b].map((x) => x.toString(16).padStart(2, "0")).join("");
return `${h.slice(0, 8)}-${h.slice(8, 12)}-${h.slice(12, 16)}-${h.slice(16, 20)}-${h.slice(20)}`;
}
const tsOf = (u: string): number => parseInt(u.replace(/-/g, "").slice(0, 12), 16);
const base = Date.UTC(2026, 9, 7, 17, 0, 0); // 2026-10-07T17:00:00Z (example instant)
const v7 = [uuidv7(base), uuidv7(base), uuidv7(base + 1), uuidv7(base + 2)];
console.log("UUIDv7 samples:");
for (const u of v7) console.log(" ", u, "->", new Date(tsOf(u)).toISOString());
console.log("lexicographic order == creation order:", JSON.stringify(v7) === JSON.stringify([...v7].sort()));
// Index locality: insert 10,000 keys into a sorted array (a stand-in for a B-tree leaf chain)
// and count how often the new key lands at the right edge (cheap append) vs in the middle.
function rightEdgeShare(gen: (i: number) => string): number {
const keys: string[] = [];
let appends = 0;
for (let i = 0; i < 10_000; i++) {
const k = gen(i);
let lo = 0, hi = keys.length;
while (lo < hi) { const mid = (lo + hi) >> 1; if (keys[mid]! < k) lo = mid + 1; else hi = mid; }
if (lo === keys.length) appends++;
keys.splice(lo, 0, k);
}
return appends / 10_000;
}
console.log(`right-edge inserts UUIDv7: ${(100 * rightEdgeShare((i) => uuidv7(base + 10 + Math.floor(i / 8)))).toFixed(1)}%`);
console.log(`right-edge inserts UUIDv4: ${(100 * rightEdgeShare(() => uuidv4())).toFixed(1)}%`);Output:
UUIDv7 samples:
01a1174e-c280-7028-ac03-c0c4b6d8ae93 -> 2026-10-07T17:00:00.000Z
01a1174e-c280-7029-b7da-3364e0a9d9d0 -> 2026-10-07T17:00:00.000Z
01a1174e-c281-7014-a352-6903e46a68bf -> 2026-10-07T17:00:00.001Z
01a1174e-c282-7024-8f7d-2df2daf8ee51 -> 2026-10-07T17:00:00.002Z
lexicographic order == creation order: true
right-edge inserts UUIDv7: 100.0%
right-edge inserts UUIDv4: 0.1%ExpectedUUIDv7 samples: 01a1174e-c280-7028-ac03-c0c4b6d8ae93 -> 2026-10-07T17:00:00.000Z 01a1174e-c280-7029-b7da-3364e0a9d9d0 -> 2026-10-07T17:00:00.000Z 01a1174e-c281-7014-a352-6903e46a68bf -> 2026-10-07T17:00:00.001Z 01a1174e-c282-7024-8f7d-2df2daf8ee51 -> 2026-10-07T17:00:00.002Z lexicographic order == creation order: true right-edge inserts UUIDv7: 100.0% right-edge inserts UUIDv4: 0.1%
Press Run. Snippets must be self-contained — no network, files, or native modules.
The locality result is the reason teams are moving primary keys from UUIDv4 to UUIDv7. In a B-tree (InnoDB clustered primary keys, PostgreSQL indexes), random keys land on random leaf pages: more page splits, more dirty pages to flush, a working set as large as the whole index, and more WAL from full-page writes. Time-ordered keys append near the right edge, so the hot part of the index stays in cache. PostgreSQL 18 ships a built-in uuidv7() function; most languages have libraries.
Ordering vs index locality vs coordination
| You care most about | Prefer | Avoid |
|---|---|---|
| Zero coordination, opaque ids | UUIDv4 (or v7 if you also want locality) | Central sequences |
| Insert performance on B-tree primary keys | UUIDv7, ULID, Snowflake, sequences | UUIDv4 as clustered key |
| Compact 64-bit keys | Snowflake-style, sequences, hi-lo | 128-bit UUIDs where storage really matters |
| Not leaking business volume or creation time | UUIDv4, or encrypt/obfuscate public ids | Sequences and time-ordered ids exposed in URLs |
| Strict global order | A single sequence or consensus log | Any per-node scheme (only k-sorted) |
| Spreading writes across shards | Hash of id as shard key, or random prefix | Time-ordered id as the partition key in Bigtable/DynamoDB-style stores (hot latest partition) |
That last row is the twist: the same right-edge locality that helps a single B-tree creates a hot spot when the ID is the range-partition key of a distributed store, because all new writes go to the newest range. Bigtable and HBase schema guides warn against monotonically increasing row keys for this reason.
Clock rollback and other failure modes
- NTP step backwards: wait out small rollbacks, refuse large ones (as above). Some implementations borrow the next sequence bits instead of waiting; never silently reuse a timestamp with a reset sequence.
- Duplicate worker id: two generators produce identical ids at the same millisecond. Lease worker ids, or include a random component.
- Sequence exhaustion: more than 4096 ids per millisecond per worker; either wait (adds latency) or add workers.
- Epoch exhaustion: 41 bits of milliseconds last about 69 years from the custom epoch; choose the epoch deliberately.
- Leap seconds and smearing: a smeared clock still never goes backwards, which is one reason fleets smear.
- JavaScript precision: 64-bit ids exceed
Number.MAX_SAFE_INTEGER(2^53 - 1). Send them as strings in JSON (Twitter's API addedid_strfor this reason).
What happens if you choose otherwise
- UUIDv4 as a clustered primary key on a write-heavy table: insert throughput drops and buffer pool churn rises as the table grows; switching to time-ordered keys later is a migration.
- Auto-increment ids in public URLs: competitors can estimate your volume and attackers can enumerate resources (pair with authorization checks regardless).
- Snowflake without rollback handling: duplicate ids after an NTP step, discovered as unique-constraint violations or, worse, overwritten rows.
- A central ticket service for a global system: every insert pays a network hop; batch with hi-lo blocks to amortize.
Interview Q&A
Why are UUIDv4 primary keys slow in MySQL InnoDB or PostgreSQL B-trees?
Answer
Random keys insert into random leaf pages, causing page splits, poor cache locality and more write amplification. Time-ordered ids like UUIDv7 or Snowflake append near the right edge of the index.
Walk me through a Snowflake id.
Answer
1 unused sign bit, 41 bits of milliseconds since a custom epoch, 10 bits of worker id (often split into datacenter and worker), 12 bits of sequence within the millisecond, so 4096 ids per millisecond per worker, roughly sortable by time.
How should a Snowflake generator handle the clock going backwards?
Answer
Detect now < last timestamp; wait if the gap is tiny, otherwise refuse to issue ids and alert, so duplicates are impossible. Persist the last timestamp across restarts.
UUIDv7 vs ULID?
Answer
Both put a 48-bit millisecond timestamp first and randomness after. UUIDv7 is an IETF standard (RFC 9562) that fits UUID columns and tooling; ULID is a community spec with a shorter, URL-friendly base32 text form. Byte-wise they are similarly sortable.
When would you still use a database sequence?
Answer
Single-database systems, where you want compact, strictly increasing ids and the database is already the bottleneck you accept. Use hi-lo or cached sequences to reduce contention.
Why is a time-ordered ID a hot partition key?
Answer
Range partitions split the keyspace. Every new ID is larger than the last, so every insert hits the newest range. That is the same right edge that helps a single B-tree.
What is the JavaScript integer pitfall?
Answer
A 64-bit Snowflake exceeds Number.MAX_SAFE_INTEGER, 2^53 - 1. JSON numbers round it. Send the ID as a string. Twitter's API added id_str for this reason.
How long does the 41-bit millisecond timestamp last?
Answer
About 69.7 years from the custom epoch in the snippet. Twitter's published epoch is November 2010. Pick the epoch on purpose.
Check yourself
Pick a table you know. Say whether its primary key is a sequence, UUIDv4, or a time-ordered ID. Then say whether that same value is a range-partition key. If both answers are time-ordered, name the hotspot.
Elsewhere in the library
These pages stay as they are. This lesson only points at them: URL Shortener Scale-up HLD - ID Generation, Caching, Sharding & Analytics, Database Sharding & Partitioning — Keys, Hotspots & Rebalancing, Partition Keys — Ordering Guarantees vs Parallel Throughput.
Go Deeper
- RFC 9562: Universally Unique IDentifiers (UUIDs), including UUIDv7
- Twitter Engineering: Announcing Snowflake (2010)
- Twitter Snowflake source (archived)
- Instagram Engineering: Sharding & IDs at Instagram
- Flickr: Ticket Servers, Distributed Unique Primary Keys on the Cheap
- ULID specification
- Segment KSUID
- Google Cloud Bigtable: schema design, row keys to avoid