Cheat Sheet

Requirements

2^64 = 1.8446744 * 10^19
365 * 10^9 events/year
2^64 / (365 * 10^9) ~= 50.54 million years     -> 64 bits is plenty

The size limit is the binding constraint. Without it, UUIDs solve everything.

The seven approaches

Each row fixes the previous row's failure and reveals a new one. That progression is the answer.

The approaches in detail

UUID — 128-bit hex, ~10^38 combinations, v4 pseudorandom. Zero coordination (its one great strength). Fails: too big · non-numeric · probabilistic not deterministic · not sortable · random keys destroy B-tree locality.

Database auto-increment — central counter. SPOF in front of every write. Increment-by-m fix breaks: m=3, A emits 1,4,7 · C emits 3,6,9 · B dies, m=2 · A's next = 7+2 = 9 = duplicate. Same trap as hash % m: any scheme depending on node count breaks on membership change.

Range handler — central service hands out blocks (e.g. 300,001–400,000); servers assign locally, request a new block when exhausted. Range status in replicated storage + failover server. Key idea: amortize coordination — once per 100k IDs, not per ID. Cost: gaps when a server dies holding a range. Smaller ranges = fewer lost IDs, more handler traffic.

UNIX timestamps — 24 * 60 * 60 * 1000 = 86.4M IDs/day, 10x short. Same-millisecond requests collide.

Twitter Snowflake

 1 bit      41 bits            10 bits       12 bits
[sign=0]  [timestamp ms]      [worker]     [sequence]
           ~69 years           1,024        4,096/ms
                    1 + 41 + 10 + 12 = 64

Time to depletion = 2^41 / (365*24*60*60*1000) ~= 69 years
Throughput = 4,096/ms * 1,000 * 1,024 workers ~= 4.2 billion/sec theoretical

Default epoch 1288834974657 (Nov 4, 2010) — set a custom epoch at launch or you burn years of budget.

Worked decode:

timestamp field   = 352,721,356,343
+ Twitter epoch   = 1,288,834,974,657
= 1,641,556,331,000 ms  ->  Jan 07 2022 11:52:11 UTC

Weakness: the 41-bit range drains on the wall clock regardless of usage, and ordering is only as good as the clocks. Clock error can reach 17 sec/day; an NTP correction backwards can reissue a millisecond → duplicates or broken causality. Defence: refuse to generate while now < last timestamp; use NTP slew, not step. Sequence overflow: block until the next millisecond, don't reuse.

Logical clocks

Lamport — counter per process; increment before local events; send with messages; on receive max(local, received) + 1.

a caused b   =>  L(a) < L(b)          (holds)
L(a) < L(b)  =>  a caused b           (does NOT hold)

Gives a partial order; total order by tie-breaking on node ID. Cannot detect concurrency.

Vector clocks — counter per node; captures full causal history.

 1 bit    53 bits          10 bits
[sign]  [vector clock]    [worker]        pattern: [vector-clock][worker-id]

A1 -> [1,0,0][A]    C1 -> [0,0,1][C]    B1 (saw A1) -> [1,1,0][B]

Every counter in X <= Y   -> X happened before Y
Each has one the other lacks -> CONCURRENT

Fails: O(n) in cluster size — blows a fixed 64-bit budget when n is large or every client is a node.

TrueTime

Returns an interval [earliest, latest], guaranteeing real time lies inside. GPS receivers + atomic clocks, epsilon typically < 7 ms, daemon runs Marzullo's algorithm to intersect readings.

Epsilon grows at 200 us/sec between syncs -> +6 ms over 30 sec
Order is certain only if intervals are DISJOINT:
  A_earliest < A_latest < B_earliest < B_latest  =>  B after A

 41 bits        4 bits        10 bits     8 bits
[earliest T] [uncertainty]   [worker]   [sequence]
                 epsilon      1,024        256

Cost: GPS and atomic clocks in every data center — costly and operationally complex. Overlapping intervals report unknown rather than guessing.

Six design lessons

• Duplicate IDs cause critical errors (duplicate payments).
• UUIDs are probabilistic; deterministic uniqueness needs consensus, which is slower.
• Large keys slow database updates — keep IDs compact.
• Random bits prevent guessing business metrics (subtract two order IDs = weekly volume).
• Counters need persistent storage → bottlenecks and SPOFs.
• Monotonic IDs create hotspots in distributed databases — every insert hits the top shard.

Quick decision cues

• No size constraint → UUID (zero coordination, done)
• Compact + unique, ordering irrelevant → range handler
• Compact + unique + roughly sortable → Snowflake (the practical default)
• Provable causality, small cluster → vector clocks
• Strict external consistency, Google budget → TrueTime
• IDs externally visible → add random bits (conflicts with sortability)
• Hot shard on inserts → the sortable ID is the cause; hash for partitioning
• Need >4,096 IDs/ms on one worker → more workers, not more sequence bits

Work the Interview Walkthrough for the full design and the Concept Drills for rapid-fire practice.