IDs, Time and Ordering · System Design · aiiolarHandbooks / System Design / Chapter 12
IDs, Time and Ordering
7 pages · ~5 min✓ Reviewed
Builds on Distributed Transactions and Consensus. Next up: Observability and Operations.
System DesignPage 1IDs and Clocks: The Mental Model
1. What a Distributed ID Needs
- Unique across every node: the one hard rule
- k-sortable: roughly time-ordered
- Compact: fewer bytes in every index
- No coordination: any node mints IDs alone
3. Happens-Before
a → b if same process and a is earliera → b if a is a send and b its receive- No path either way: concurrent
4. Key Order and the B-tree
System DesignPage 2ID Schemes: Auto-increment, UUIDs, Snowflake, Ticket Servers
1. Auto-increment and UUIDs
- Auto-increment: 8-byte, sorted, tiny index
- Single writer is a bottleneck; it leaks row counts
- Multi-master needs offset/step: node 1 gives 1,3,5; node 2 gives 2,4,6
System DesignPage 3Clock Skew, NTP and Why Wall Clocks Lie
1. Skew vs Drift
- Skew = offset between two nodes' clocks
- Drift = rate a clock gains or loses time
- Quartz drifts roughly tens of ppm
2. NTP and Monotonic Clocks
- NTP accuracy: ~ms on a LAN, tens of ms over the internet
- NTP can step the clock backward: wall time is not monotonic
System DesignPage 4Logical Clocks: Lamport, Vector, Hybrid
1. Lamport Clock
- 1Local eventc = c + 1
- 2Sendattach c
- 3Receivec = max(local, received) + 1
System DesignPage 5Ordering Guarantees in Partitioned Systems
1. Order Per Partition
- Kafka orders only within a partition
- Partition key (
user_id) keeps related events together - No order guarantee across partitions
- Producerkey = user_id
- Partitionone per key
- Consumerdedupe on event ID
- Total order needs one partition, a sequencer, or consensus (Raft/Paxos)
System DesignPage 6Cheat Sheet: Choosing IDs and Clocks
System DesignPage 7Check yourself
Two events have Lamport timestamps L(a)=3 and L(b)=5. Did a happen before b?
- Unknown: a → b implies L(a) < L(b), not the reverse
- They may be concurrent; only vector clocks can tell
NTP steps a Snowflake worker's clock back 5 ms. What can go wrong?
- It reuses timestamps it already issued, with the sequence reset to 0: duplicate IDs
- Fix: keep
last_timestamp; wait or refuse until time catches up
Vector clocks are A=[2,1] and B=[1,2]. How are the two events related?
| Time-ordered | right edge | fast, cache-friendly |
| Random | anywhere | page splits, cache misses |
RememberTimestamps say when; only happens-before says what caused what. Concurrent events have no true order.
| UUID v4 | 16 bytes, 122 random bits | no, fragments clustered index | none, collisions negligible |
| UUID v7 | 48-bit Unix-ms prefix + random | yes | none |
2. Snowflake (64 bits)
- 1 bitsign
- 41 bitsms timestamp, ~69 years from custom epoch
- 10 bitsworker ID
- 12 bitssequence, 4096 IDs per ms per worker
- Timestamp comes first, so IDs sort by time
- Each worker needs a unique worker ID
3. Ticket Server (Flickr)
sqlREPLACE INTO Tickets64 (stub) VALUES ('a');
SELECT LAST_INSERT_ID(); a dedicated DB hands out the next ID
- Run two servers with odd/even steps
- Clients cache a block of IDs: no round trip per ID
Rememberv4 is unsorted. Auto-increment needs one writer. v7 is sorted and coordination-free.
| Clock | Use for | Example |
|---|
| Monotonic | durations, timeouts | CLOCK_MONOTONIC, System.nanoTime |
| Wall | timestamps only | System.currentTimeMillis |
3. What Breaks
- Last-write-wins on wall clocks silently drops writes
- The node with the fast clock always wins
- Snowflake and UUIDv7 break on a backward jump
- Clock goes backnow < last_timestamp
- Refuseissue no IDs
- Wait it outuntil caught up
- Bump sequencekeep last_timestamp
RememberNever compare raw wall clocks across nodes to order events. Use monotonic for elapsed time.
- a → b implies L(a) < L(b)
- Converse is false: L(a) < L(b) proves nothing
- Equal or ordered stamps cannot show causality or concurrency
2. Vector Clock
- One counter per node, compared element-wise
- Neither vector dominates → events are concurrent (a conflict)
- Cost grows with the number of nodes
- Dynamo-style stores keep sibling versions, then merge or let the client resolve
3. Hybrid Logical Clock
- HLC = (physical time l, logical counter c)
- Stays close to wall time, yet causal
- Used by CockroachDB and MongoDB
- Bounded max-offset check rejects clocks too far ahead
RememberLamport gives order, not concurrency. Only vector clocks detect concurrent events.
event ID or sequence number3. Spanner TrueTime
- Returns a bounded interval [
earliest, latest] - Commit-wait: wait out the uncertainty before commit
- Result: external consistency
RememberOrder holds per key. Global order costs throughput and latency.
- Snowflake worker ID: assign via ZooKeeper, etcd or config
- Sorting by ID gives only approximate time order across workers (ms-level skew)
- Sequential IDs as public identifiers without authorization checks: enumeration risk
- Cross-node ordering by raw wall-clock comparison
- Using the wall clock to measure a duration
Rule of thumbWall clock for timestamps, monotonic clock for durations, logical clocks for order.