ID Generation — Unique ≠ Ordered ≠ Linearizable
every scheme hands out unique IDs · they differ in ordering guarantees, fault tolerance, and how far away the answer comes from
① Single node
Autoincrement counter
unique + total order + linearizable
one fetch-and-add on one counter
SPOF · cross-region RTT · bottleneck
Timestamp oracle (single leader)
one counter, replicated for fault tolerance
persist a batch of IDs, hand them out in
sequence — crash skips IDs, never repeats
not shardable · every region asks one node
linearizable ✓ · fault-tolerant only via replication
② Distributed generators
Sharded counters
unique; order lost across shards
IDs 16 and 17 — which came first?
Preallocated blocks
node A takes 1–1000, node B takes 1001–2000
a later write can still get a smaller ID
a crash wastes the rest of the block
Random UUID v4
128 bits, generated locally — zero calls
collisions vanishingly unlikely
order is random — comparing IDs tells nothing
Wall-clock + sequence
UUIDv7 / ULID / Snowflake: time + shard + seq
≈ real-time order, compact, no round trip
clock skew / NTP jumps can invert order
→ almost certainly not linearizable
③ Logical clocks
Lamport clock
timestamp = (counter, nodeID)
counter := max(local, seen) + 1
total order that respects causality
no wall-clock meaning · not linearizable
Hybrid logical clock (HLC)
physical time + Lamport-style bump
monotonic even across NTP adjustments
≈ wall-clock meaning + causal order
needs only roughly synced clocks
Vector clocks
one counter per node in every timestamp
tells “concurrent” from “later”
size grows with the number of nodes
causal order ✓ · linearizable recency ✗
Ordering is not deciding
To enforce a constraint — a lock, a unique username, the last seat on a flight — the winner must know its timestamp is the lowest.
That requires hearing from every node that might have stamped a request; one unreachable node halts the decision.
Fault-tolerant decision-making therefore needs consensus (next section): single-node counters are linearizable but fragile,
logical clocks are robust but not linearizable.