System Design Fundamentals

Unique ID generation

An Instagram-scale upload lands in three regions at once. Each write needs an ID that is unique everywhere, roughly ordered by time for feeds and indexes, and mintable at high QPS (queries per second), without one database sequence becoming a .

Auto-increment fails when many shards write at once. Random scatters primary keys across the index. A packs time, location, and a so each writer can mint locally and still stay roughly sortable.

Minting journey

Read wall-clock ms

Timestamp fills the high bits so IDs sort roughly by creation time.

Lease a unique generator ID so two pods never mint the same space.

Same millisecond: increment; if the counter fills, wait for the next ms.

Combine the bits into one 64-bit time-ordered unique ID.

Try it: mint IDs across workers

Compare Snowflake (time + worker + sequence), UUID-style opaque ids, and a central sequence. The interview question is rarely “which hash?” — it is where uniqueness, ordering, and write load live.

Mode: snowflake
Worker id: 7
Sequence: 0
Next id: 362387865628672

Recent ids (newest first)

order

Uniqueness

collision

Snowflake needs unique worker ids and a sequence that resets per millisecond. UUID leans on randomness. DB seq is unique by construction.

Ordering

indexes

Time-ordered ids improve locality for recent-range scans. Opaque UUIDs scatter B-tree inserts unless you add a created_at column.

Hotspot

allocator

A single sequence table or auto-increment becomes a create-path bottleneck long before storage does.

Mint IDs with Snowflake bits, compare to UUID randomness and a central DB sequence, and watch sortable order versus collision risk.

Snowflake. Roughly time-sortable and allocatable on many workers if worker ids stay unique.

Central sequence. Simplest ordering story, worst hotspot under create-heavy traffic.

What actually happens when many regions write

The three-region upload above is the default for any multi-writer system. You need IDs that stay unique across workers and regions, stay roughly ordered for timelines and partitions, and keep minting under load. That is a coordination problem: uniqueness, time-ordering, throughput, and multi-region safety, all at once.

Naive move. One database SERIAL / autoincrement primary works on a single primary. Multi-region primaries cannot share one counter without coordination or collisions. Counterexample: two regional primaries each mint id=1_000_041. Random avoids that collision but scatters every insert across the B-tree (the on-disk index tree) until page splits dominate write I/O.

What breaks. A central sequence is a and a hotspot. Random keys destroy locality. Time-ordered schemes without unique or handling collide after restarts and NTP (network time sync) steps.

Other options still show up in interviews: and add sortability at 128 bits with familiar libraries. batch-allocate ranges when you can afford a small central tier. The rest of this page focuses on the packed 64-bit path, because that is the usual high-QPS multi-datacenter answer.

How to choose an ID scheme

Before diving into bit layouts, three questions usually decide which scheme fits. Use them as a quick filter, then confirm with the comparison table further down.

1. Do indexes need time locality? Feeds, shards, and clustered primary keys usually want roughly monotonic IDs. Random is a poor clustered key even though it is unique.

2. Can you lease unique worker IDs under autoscaling? uniqueness hinges on every live generator holding a distinct . If you cannot lease them safely, prefer a library-backed 128-bit scheme or a .

3. Is 64-bit packing required? If not, or may be simpler with existing libraries, at the cost of larger keys.

When each approach fits

DB sequence: single-region monolith, low write QPS, dense consecutive integers preferred.
UUIDv4: client-generated or offline minting when sort order does not matter.
ULID / UUIDv7: time-sortable keys with libraries when 64-bit packing is optional.
Ticket servers: sequential-ish ranges with batch allocation and a small coordination tier.
Snowflake-style 64-bit: high QPS feeds, sharded stores, multi-DC compact sortable IDs.

Rule of thumb

Default interview answer for high-QPS multi-DC writes: Snowflake-style 64-bit IDs with leased worker IDs and explicit handling. Use UUIDv4 for opaque external IDs when sort order does not matter. In simple terms: pick the scheme that is unique, useful as a key, and free of a single minting bottleneck.

From problem to Snowflake mechanism

Once you choose a packed time-ordered ID, here is the classic interview layout and the mint path that keeps the uniqueness invariant.

Classic layout (64 bits total; often 1 unused sign bit so IDs stay positive as signed integers):

1 unused

41 timestamp ms

5 datacenter

5 worker

12 sequence

64-bit time-ordered ID

plaintext

[1 unused] | [41 timestamp ms] | [5 datacenter] | [5 worker] | [12 sequence]

Timestamp: ms since custom epoch
  2^41 ms ≈ 69.7 years of IDs

Datacenter + worker: 10 bits → 1024 unique generators
  e.g. 32 DCs × 32 workers each

Sequence: 12 bits → 4096 IDs per worker per millisecond
  Per worker: 4096 × 1000 = ~4.1M IDs/sec
  1024 workers: theoretical ~4.2B IDs/sec cluster-wide

Same ms on one worker: increment sequence.
Sequence full: wait for next millisecond.

Request new ID

Read wall-clock ms

ms < last issued?

Yes: skew

Wait / refuse / logical bump

Re-read clock

No: proceed

Same ms as last?

next decision

Same ms as last?

Yes

Increment sequence

Sequence exhausted?

wait next ms if full

Reset sequence to 0

Pack timestamp | DC | worker | sequence

Emit unique ID

Correctness invariant

No two live generators share the same (datacenter, worker) identity for overlapping ID lifetimes. For a given worker, emitted (timestamp, ) pairs never reuse a previously issued pair: wall time may step back, but the logical mint clock must not. Rough time-order is not causal consistency or a global total order.

Numbers to know, and how options compare

The bit layout above is only useful if you can quote the rates and spot when a hot worker or a random key will hurt. Keep these numbers handy, then use the table to place Snowflake against the alternatives.

plaintext

Classic layout: 1 unused | 41 ms | 5 DC | 5 worker | 12 sequence

2^41 ms ≈ 69.7 years from custom epoch
10 machine bits → 1_024 concurrent generators
12 sequence bits → 4_096 IDs / worker / ms
  → ~4.1M IDs/sec per worker
  → ~4.2B IDs/sec theoretical across 1_024 workers

Hot worker at 6_000 IDs in one ms:
  sequence exhausts at 4_096 → must wait next ms (or add workers)
  p99 mint latency spikes under burst even though average QPS looks fine

UUIDv4 as clustered PK at 50K inserts/sec:
  random page touches → more splits / dirty pages than time-ordered 64-bit keys

Approach	Unique	Time-ordered	Scale / multi-DC	Main risk
DB sequence	Yes (one primary)	Yes	Weak: single writer hotspot	SPOF; hard across shards
UUIDv4	Yes (probabilistic)	No	Excellent: fully local	Index fragmentation; 128-bit keys
ULID / UUIDv7	Yes	Yes (ms + entropy)	Excellent: local	Larger than 64-bit; clock skew still matters
Ticket servers	Yes	Roughly	Batch helps; still centralish	Availability of ticket tier; range waste
Time-ordered 64-bit	Yes (with unique worker IDs)	Yes (by design)	Excellent: local mint	Clock skew; worker ID collisions

Clock skew and worker-ID leasing

The comparison table lists and worker collisions as the main Snowflake risks. Here is how to handle both in production without inventing a second central minting service.

Clock skew responses

Time-ordered IDs depend on a non-decreasing clock. NTP steps, VM pause, or bad sync can move wall time backward and risk reusing a (timestamp, worker, ) tuple.

Wait

Suppose a worker last emitted an ID at logical millisecond 10,000 and its clock returns 9,998. Reusing the older timestamp with a reset sequence can recreate an earlier ID. A bounded-wait policy pauses until physical time exceeds the last emitted time, then resumes. Waiting protects uniqueness but consumes request latency and throughput; expose that wait as a metric instead of treating it as an invisible clock correction.

Refuse

If skew exceeds a threshold (for example >5s), fail the request and alert rather than risk silent duplicates.

Logical bump

A logical-time policy uses at least the previous emitted timestamp and continues its per-millisecond sequence when physical time falls behind. Once that timestamp’s sequence capacity is exhausted, it must wait, advance logical time under a documented policy, or reject work. Arbitrarily advancing the timestamp can move IDs far ahead of real time and affects range queries. Persist or safely reconstruct the high-water mark across restarts; an in-memory variable protects only one process lifetime.

On restart, a worker must know that its next timestamp/sequence pair cannot repeat any pair it previously issued. Persisting a high-water mark, reserving future timestamp intervals durably, or assigning a safely distinct worker identity are possible approaches with different costs. Persisting after every issued ID can create a new write bottleneck, while infrequent persistence leaves a reuse window. Document what happens after a crash between reservation and issuance.

Multi-region assignment

Uniqueness hinges on every live generator holding a distinct (datacenter, worker) pair for the lifetime of IDs that might still be in flight.

Static / config map

Deploy with fixed worker IDs. Simple, but fragile under autoscaling unless the orchestrator guarantees uniqueness.

Lease from a registry

On boot, claim a free worker ID with a TTL lease (etcd / ZooKeeper-style / SQL row). Renew while healthy; release on shutdown.

Region bits in DC field

Carve the 5–10 machine bits by region so two regions never collide even if local worker pools are independently assigned.

Never reuse hot IDs

After a crash, wait out the lease TTL (or a safety window greater than max clock skew) before reassigning the same worker ID.

Lease sketch and index locality

A worker identifier must belong exclusively to one active generator for the interval in which timestamp/sequence pairs could overlap. A coordination-store lease helps allocate identifiers, but lease expiry alone does not stop a paused old process from resuming and minting. The generator must stop before its authority expires under explicit clock/pause assumptions, or use an identity-generation scheme that cannot collide with a replacement. Do not present a TTL formula based only on in-flight request duration as a complete proof.

Time-prefixed IDs often improve B-tree locality by concentrating recent inserts, but can also create a hot rightmost page or a hot range partition. Random IDs spread that load while increasing scattered index writes. The best choice depends on the database’s physical index and partitioning strategy, not only the visual order of identifiers.

plaintext

lease(worker_id=417, ttl=30s)
heartbeat every 10s

If heartbeat fails and TTL expires:
  coordinator may reassign worker_id=417

Safe restart rule:
  do not mint again with old lease token
  until the old lease is confirmed dead

Watch / runbook

Alert on clock-skew refusals, lease acquire failures, sequence-wait duration, and duplicate-key rate on the ID primary. Persist last-issued timestamp across restarts when possible (see Numbers to know above for burst rates).

Failure timeline, and what still breaks after the fix

Putting leasing and skew handling together, here is how a collision still happens when both fail at once, followed by the residual failure modes and the trade-offs you accept by choosing Snowflake.

Timeline: clock rollback + reused worker ID

t=0      Worker W17 leases worker_id=42; mints IDs at wall ms T=1_700_000_100
t=1      Last issued: (T, seq=200); lease heartbeat fails; pod OOM-killed
t=2      NTP / VM restore: wall clock jumps back to T-40ms
t=3      New pod claims worker_id=42 before old lease TTL ends (bad coordinator)
t=4      New W17 mints (T-20ms, seq=0) … up through (T, seq=200)
t=5      Collision: same (timestamp, worker, sequence) as IDs already in DB
Outcome  Unique-ID invariant broken; upserts overwrite or PK inserts fail

Counterexample to "Snowflake cannot collide": uniqueness is only as strong as exclusivity and a non-decreasing logical clock across restarts.

Failure modes and traps

Duplicate worker IDs: two pods share one ID and collide in the same millisecond.
Clock rollback after restart: forgotten last sequence plus a step-back reissues IDs.
Sequence exhaustion: one hot worker above 4096 IDs/ms must wait or add workers.
Epoch or bit-budget mistakes: wrong epoch, signed overflow, or claiming perfect global order.
Trap: calling UUIDv4 fine for primary keys without discussing B-tree locality.
Trap: treating ticket servers as infinitely available, or equating time order with causality.

Still fails when…

A paused generator resumes after losing its lease; identifier reassignment is unsafe unless stale generators are prevented from minting overlapping timestamp/sequence pairs.
Logical clock bumping under long skew exhausts the sequence and stalls minting.
batch ranges but become a soft when the coordination tier dies.
Concurrent workers are treated as a global total order; / still need skew handling.

Trade-offs

64-bit packed IDs are compact but sensitive to clocks and worker-ID leasing ops.
UUIDv4 is easy and fully local, but hurts clustered indexes and range scans.
ULID / UUIDv7 add sortability at 128-bit size without custom bit packing.
Skipping leasing or skew handling buys simplicity and risks collisions or a minting SPOF.

Choosing and explaining unique ID generation

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

Call out uniqueness, rough time order, QPS, multi-DC, and no SPOF before naming a scheme.

Propose a time-ordered 64-bit layout with bit budget and IDs/sec math.

Cover clock skew mitigations and how worker IDs stay unique under churn.

When it belongs

Post, order, or message IDs must be minted across many writers.

Primary keys should help range scans or timeline sort without a second created_at index.

Autoincrement or a central sequence becomes a hotspot.

How it fails

Two workers share an ID after bad lease handling.

Clock steps backward after restart and reissues IDs.

Single ticket server or DB sequence dies and ID minting stops.

Trade-offs to weigh

64-bit packed IDs are compact but clock- and worker-ID sensitive.

UUIDv4 is easy and local but hurts clustered indexes.

ULID/UUIDv7 add sortability at 128-bit size.

Common misunderstandings

Claiming global total order from millisecond timestamps.

Ignoring worker ID assignment in autoscaling environments.

Using UUIDv4 as a clustered PK without discussing write amplification.

Going deeper

Production deep dive: uniqueness under clocks and churn

A sortable 64-bit ID is a protocol: bit layout, epoch, time source, worker assignment, overflow behavior, and rollback policy must remain stable for every producer and decoder.

What must stay true

No active process may emit the same (timestamp, worker, sequence) tuple as any current or previous lease holder.

How the pieces fit

Worker lease

ID + fencing epoch

Clock check

now ≥ last timestamp

Sequence

0…4095 per ms

Pack 64 bits

41 + 10 + 12

Persist high-water

survive restart

Timestamp bits

2^41 ms ≈ 69.7 years from a custom epoch.

Worker bits

2^10 = 1,024 simultaneously leased workers.

Sequence bits

4,096 IDs/ms/worker; ≈ 4.19B/s theoretical fleet peak.

Worker-ID fencing

Allocate worker IDs with renewable leases and monotonically increasing fencing epochs. A generator must stop before lease expiry; the coordinator must not reassign the ID until the old lease is impossible to use, and downstream telemetry should include the fencing epoch for duplicate diagnosis.

Clock rollback sequence

If last_ms=10,005 and wall clock returns 10,002, do not reset sequence. Wait for small rollback within a bound; for a larger rollback, quarantine the worker, use a persisted logical high-water timestamp, or obtain a new fenced worker ID. Alert because hidden drift can exhaust the future-time buffer.

Sequence overflow

After 4,096 IDs in one millisecond, block until the next millisecond, borrow preallocated sequence space, or reject with backpressure. Wrapping to zero creates a duplicate immediately; silently moving the timestamp into the future can compound later rollback.

UUIDv7 and ULID

UUIDv7 places Unix-millisecond time before random bits and uses the standardized UUID shape. ULID uses 48 time bits plus 80 randomness bits and a compact sortable encoding. Both avoid a central worker allocator; monotonic generation within one millisecond still needs careful library behavior.

Information leakage

Sortable IDs reveal creation time; a visible worker field can expose topology, and sequence values can reveal traffic. Use opaque public IDs or encrypt/map internal IDs when enumeration, customer-volume inference, or regional placement is sensitive.

Worked example: Complete bit-allocation calculation

1Reserve the sign bit so IDs stay positive in signed 64-bit stores. Allocate 41 timestamp + 10 worker + 12 sequence = 63 payload bits.
2Lifetime: 2^41 milliseconds ÷ 1,000 ÷ 60 ÷ 60 ÷ 24 ÷ 365.25 ≈ 69.7 years.
3Per-worker peak: 2^12 × 1,000 = 4.096M IDs/s; across 1,024 workers the mathematical ceiling is ≈4.19B IDs/s.

The real safe rate is lower because the generator must reserve time for clock checks, lease renewal, restarts, and burst backpressure.

Generator failure matrix

Scenario	Consequence	How to contain it
Old and new owner share worker 17	Identical timestamp/sequence pairs collide.	Lease fencing, delayed reassignment, and fail-closed renewal.
Clock moves backward 3 seconds	Previously used timestamp range repeats.	Wait/quarantine or continue from persisted logical high-water time.
Public IDs expose sequence	Competitor infers tenant volume.	Map internal sortable ID to opaque public identifier.

What to watch in production

Monitor rollback milliseconds, sequence-exhaustion waits, lease-renewal margin, duplicate detection, and IDs generated in future time.
Persist last emitted timestamp across graceful restart and test abrupt restart with an artificially rolled-back clock.
Version the bit layout; never reinterpret old IDs after changing epoch or field widths.

A scenario to reason through

A worker emits at timestamp 50,000, restarts with its clock at 49,800, and receives the same worker ID. What prevents duplicates?

One solid approach

A persisted high-water timestamp and fenced lease. The process waits or logically stays above 50,000 and starts sequence safely; if state is unavailable, it must receive a new worker identity or fail closed.

Wrap-up

You have seen the multi-region failure, the Snowflake mechanism, and the operational signals. Use these exercises to check the ideas stuck, then follow the references for the primary sources.

Exercises

You need 2M IDs/sec cluster-wide with 12-bit sequences. How many workers must be live, and what happens if one worker briefly hits 5K IDs in a single millisecond?
A worker lease lasts 15s, clock skew can reach 8s, and requests may remain in flight for 5s. Explain why those numbers alone do not prove worker_id=42 is safe to reuse after a process pause. What stops the old generator from resuming?
Product wants sortable feed keys but already stores UUIDv4. Choose UUIDv7 vs Snowflake-style 64-bit, and name one migration risk for each.

Topic-specific references

Twitter Engineering: Snowflake: ID generation at high scale (bit layout and sequence semantics).
RFC 9562: Universally Unique IDentifiers (UUIDv7 time-ordered layout).
Instagram Engineering: Sharding & IDs at Instagram (early multi-DC ID allocation lessons).

Key takeaway

Prefer local, time-ordered generators when uniqueness and index locality both matter. Pack timestamp + location + sequence into 64 bits, keep worker IDs leased uniquely, and treat clock skew as a first-class failure mode.

Practice and further reading

Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.

Focus for this lesson: Choose UUIDv7, ULID, database sequences, or Snowflake-style IDs with bit capacity, worker fencing, clock rollback, overflow, ordering, and leakage trade-offs.

Explain the decision

What happens to a Snowflake generator when its clock moves backward?

Read the reasoning

Pause until caught up, use a logical/epoch mechanism, or fence/reassign the worker; never emit duplicate time/worker/sequence tuples.

Apply it to a production scenario

Two hosts receive the same worker ID after an orchestrator race. What protects uniqueness?

Read one approach

Lease worker IDs with epochs, persist generator state, reject stale epochs, and monitor duplicate-risk conditions before serving.

Work through the numbers

Twelve sequence bits per millisecond allow how many IDs/s per worker?

Read the worked calculation

4,096/ms, about 4.096 million/s; behavior at overflow must wait or advance safely.

Reason through a failure

What is the ID invariant?

Read the recovery reasoning

No two accepted generators can emit the same namespace/time-or-logical/worker/sequence combination, including after restart or rollback.

Sources and further study

Continue with Proximity Search.

Unique ID generation

Try it: mint IDs across workers

Recent ids (newest first)

Uniqueness

Ordering

Hotspot

What actually happens when many regions write

How to choose an ID scheme

Rule of thumb

From problem to Snowflake mechanism

Correctness invariant

Numbers to know, and how options compare

Clock skew and worker-ID leasing

Clock skew responses

Multi-region worker ID assignment

Lease sketch and index locality

Failure timeline, and what still breaks after the fix

Timeline: clock rollback + reused worker ID

Failure modes and traps

Choosing and explaining unique ID generation

Explain the core idea

When it belongs

How it fails

Trade-offs to weigh

Common misunderstandings

Production deep dive: uniqueness under clocks and churn

How the pieces fit

Worker-ID fencing

Clock rollback sequence

Sequence overflow

UUIDv7 and ULID

Information leakage

Worked example: Complete bit-allocation calculation

Generator failure matrix

What to watch in production

A scenario to reason through

Wrap-up

Exercises

Topic-specific references

Key takeaway

Practice and further reading

Explain the decision

Apply it to a production scenario

Work through the numbers

Reason through a failure

Sources and further study

Multi-region assignment