Time, ordering and IDs
On one machine, "which happened first?" and "give me a unique number" are trivial. Across many machines they aren't: every server's clock is slightly wrong in its own way, messages arrive late and out of order, and two servers can hand out the same ID. This module explains why, what logical clocks do instead of trusting time, and how to generate IDs that are unique, compact and sortable at any scale.
1. The idea
- Wall-clock time (time of day) comes from each machine's quartz clock, corrected by NTP from time servers. Clocks drift, and corrections can make them jump forwards or backwards. Different machines are typically a few milliseconds apart; a misconfigured one can be off by seconds or more.
- Monotonic time only ever moves forwards and is meant for measuring durations on one machine (timeouts, latency). Use it for "how long did this take?", never for "what time is it?".
- Clock skew is the difference between two machines' clocks. Any design that compares timestamps from different machines must assume skew.
- Happened-before: event A happened before B if they're on the same machine in that order, or A is sending a message that B receives, or there's a chain of these. Otherwise the events are concurrent: neither could have influenced the other, whatever the clocks say.
2. How it works
When clocks decide, skew decides
Last-write-wins (Module 16) keeps the version with the latest timestamp. If the machine that wrote first has a clock that's ahead, its older write "wins" and the newer one vanishes. Try the skew in section 3.
Lamport clocks: order without trusting time
Leslie Lamport's 1978 idea: each process keeps a counter. Increment it for every event; attach it to every message; on receiving a message, set your counter to max(yours, received) + 1. If A happened before B, A's number is smaller. Press Play.
- Lamport clocks give a total order consistent with causality (ties broken by process ID), but a smaller number doesn't prove one event caused the other.
- Vector clocks keep one counter per process. Comparing two vectors tells you whether one event happened before the other or they were concurrent, which is exactly what you need to detect conflicting writes (Dynamo-style stores and CRDT systems use them or relatives).
- Hybrid logical clocks (HLC) combine a physical timestamp with a logical counter: close to real time, but never going backwards and always respecting causality. CockroachDB and others use them.
- TrueTime (Google Spanner) uses GPS receivers and atomic clocks to give every timestamp an uncertainty interval. Spanner waits out the uncertainty before committing, so commit timestamps match real-time order: externally consistent transactions worldwide.
Unique IDs at scale
A single database's auto-increment counter is simple but becomes a bottleneck and a single point of failure once you shard, and it leaks how many orders you have. The alternatives:
| Scheme | Size | Sortable by time? | Coordination | Notes |
|---|---|---|---|---|
| Auto-increment | 8 bytes | Yes | One database | Simple; guessable; hard across shards (use ranges or steps per shard) |
| UUIDv4 | 16 bytes | No | None | 122 random bits; random inserts scatter across a B-tree index and slow writes |
| UUIDv7 | 16 bytes | Yes (to the millisecond) | None | 48-bit Unix millisecond timestamp, then random bits (RFC 9562, 2024); index-friendly. PostgreSQL 18 has uuidv7() |
| ULID | 16 bytes (26 characters) | Yes | None | 48-bit time + 80 random bits, Crockford base32 text; similar to UUIDv7 |
| Snowflake-style | 8 bytes | Yes | A unique worker ID per generator | 41-bit milliseconds + 10-bit worker + 12-bit sequence: 4,096 IDs per millisecond per worker. Popularised by Twitter; Discord and others use variants |
3. Try it yourself
Clock skew vs last-write-wins
User 1 writes through server A, then 20 ms later user 2 writes through server B. The store keeps the write with the larger timestamp. Change how far server A's clock is ahead of B's.
Generate IDs
Each click generates five IDs in a row, about a millisecond apart (Snowflake makes some in the same millisecond). Notice which schemes keep their creation order when sorted as text.
4. Choosing an ID scheme
Sortable IDs help databases
Time-ordered IDs (UUIDv7, ULID, Snowflake) insert at the "end" of a B-tree index, like auto-increment, so indexes stay compact. Random UUIDv4s cause page splits all over the index.
Sortable IDs leak a little
Anyone holding the ID can read its creation time. Usually fine; for sensitive cases use random IDs, or keep internal IDs private and expose opaque ones.
8 bytes vs 16
Snowflake-style IDs fit in a 64-bit integer, which is smaller in every index and foreign key. They need a unique worker ID per generator, assigned by config or a coordinator.
Never trust clocks for correctness
Use timestamps for display and rough ordering. For "which write wins" or "is this lock still mine", use versions, sequence numbers, consensus or fencing tokens (Module 21).
5. In real systems
- Clock sync: servers run an NTP client (chrony is common). Clouds offer local time sources (Amazon Time Sync Service, Google's NTP, Azure's host time) that keep instances closely aligned, and some support hardware timestamping. Skew becomes small, never zero.
- Leap seconds are handled by "smearing" (spreading the extra second over hours) at Google, AWS and others, so clocks never show 23:59:60. Code that assumes every minute has 60 seconds survives.
- Databases: PostgreSQL 18 generates UUIDv7 natively; Spanner uses TrueTime; CockroachDB uses hybrid logical clocks; Cassandra uses client or coordinator timestamps for last-write-wins, which is why clock sync matters there.
- Messages and events: Kafka orders by offset within a partition, not by timestamp. Chat systems order by a per-conversation sequence number, not by device clocks.
- Discord's message IDs are Snowflake-style, which is why the message ID alone tells you when a message was sent.
In an interview, choose IDs early: "posts get Snowflake-style 64-bit IDs, generated in the service, so they're unique across shards, sortable by time, and the cursor for pagination is just the last ID." And whenever ordering matters across machines, say what provides it: one partition, a sequence number, or consensus, not wall clocks.
The technologies up close
posts get Snowflake-style IDs (or UUIDv7) generated in the service; ordering within a chat comes from a per-conversation sequence number; we never decide which write wins by comparing two machines' clocks.Mention HLC or TrueTime only when the design uses a distributed SQL database.
Clock sync: NTP, chrony and PTP
The default · always on, never perfectEvery server's clock drifts (a quartz crystal gains or loses milliseconds a day), so a daemon keeps adjusting it against better clocks. Sync makes skew small; nothing makes it zero.
How it works
- NTP asks time servers, measures the round trip, and assumes the delay is symmetric to estimate the offset. Over the internet that's accurate to milliseconds; inside a data centre, well under a millisecond.
- chrony is the usual NTP client on Linux today: it converges quickly and slews the clock (speeds it up or slows it down slightly) rather than jumping it.
- PTP (Precision Time Protocol) uses hardware timestamps in network cards and switches to reach microseconds or better.
- Two clocks per machine: the wall clock (can jump backwards after a sync) and a monotonic clock (only moves forward). Measure durations and timeouts with the monotonic one.
Status today (checked October 2026)
Clouds provide local time sources: Amazon Time Sync Service (with microsecond-level accuracy through a PTP hardware clock on supported instances, and the open-source ClockBound daemon that reports an error bound), Google's internal NTP, and Azure's host time. Leap seconds are smeared over hours, and international timekeeping bodies have agreed to stop adding them by 2035.
Use it when
- Every machine: timestamps in logs, certificates, token expiry, TTLs
Skip it when
- Ordering events across machines by timestamp alone
In the interview
Clocks are NTP-synced, so timestamps are good for display and rough ordering, but I won't rely on them to decide which write wins.
- Measuring a timeout with the wall clock: an NTP step makes it fire early or never.
- "Clocks are synced, so last-write-wins is safe".
Snowflake-style 64-bit IDs
The default for sortable IDs at scaleA 64-bit integer built from a timestamp, a machine number and a counter, so every server can mint unique IDs on its own and they sort roughly by creation time.
How it works
Twitter's original layout: 1 sign bit (unused) + 41 bits of milliseconds since a custom epoch (about 69 years) + 10 bits of machine ID (1,024 generators) + 12 bits of sequence (4,096 IDs per millisecond per machine, about 4 million a second). Discord, Instagram and others use variations: Instagram, for example, put a shard number in the middle so the ID says where the row lives.
- Machine IDs must be unique: assign them from configuration, ZooKeeper/etcd leases, or the pod's ordinal. Two generators with the same ID will collide.
- Clock going backwards: the generator must refuse or wait until time catches up, or it can reissue IDs.
- Fits in a BIGINT, indexes compactly, and works as a pagination cursor.
Status today
The pattern is widespread (Twitter, Discord, Instagram, Mastodon, many in-house services); libraries exist for every language. Sony's Sonyflake and similar variants trade sequence bits for longer lifetimes.
Use it when
- High-volume entities (posts, messages, events) that need time order and compact keys
- IDs minted on many servers without coordination
Skip it when
- Public IDs that shouldn't reveal creation time or volume
- Small systems: a database sequence is simpler
In the interview
Messages get Snowflake IDs: time-ordered, unique across shards without coordination, and the last ID is the pagination cursor.
- Reusing machine IDs after autoscaling or restarts.
- Ignoring clock rollback in the generator.
UUIDv4, UUIDv7 and ULID
The default for 128-bit IDs128-bit identifiers anyone can generate with no coordination. Version 4 is pure randomness; version 7 and ULID put a millisecond timestamp first, so new IDs sort after old ones.
How it works
| Kind | Layout | Sorts by time? | Text form |
|---|---|---|---|
| UUIDv4 | 122 random bits (+ 6 version/variant bits) | No | 36 chars with dashes |
| UUIDv7 (RFC 9562, 2024) | 48-bit Unix ms timestamp + 74 random bits (+ 6 version/variant bits) | Yes, by millisecond | 36 chars with dashes |
| ULID | 48-bit ms timestamp + 80 random bits | Yes | 26 chars, Crockford base32 |
- Why order matters for databases: B-tree indexes like inserts at the end. Random UUIDv4 keys land on random pages, so the working set is the whole index: more page splits, more cache misses, slower inserts as the table grows. UUIDv7 and ULID append like a sequence does.
- Collisions: with 74+ random bits per millisecond, collisions are not a practical concern.
- Storage: store as a 16-byte binary/UUID type, not 36-character text.
Status today (checked October 2026)
RFC 9562 (May 2024) standardised UUIDv6, v7 and v8 and replaced RFC 4122. PostgreSQL 18 generates UUIDv7 natively with uuidv7(); most languages have libraries.
Use it when
- IDs created on clients or in many services
- Primary keys where you'd rather not expose a counter: prefer v7 over v4
Skip it when
- Tight storage or index budgets at huge scale: a 64-bit Snowflake ID is half the size
In the interview
Primary keys are UUIDv7: generated anywhere, no coordination, and they insert at the end of the index like a sequence.
- UUIDv4 as the clustered primary key of a huge, write-heavy table (InnoDB especially).
- UUIDs stored as text.
Vector clocks
Rare · detecting concurrent writesA list of counters, one per node, attached to each version of a value. Comparing two lists tells you whether one version came after the other, or whether they were written concurrently and conflict.
How it works
- Node A writes:
[A:1]. B reads that and writes:[A:1, B:1], which is later because every counter is ≥. If C also wrote from[A:1], giving[A:1, C:1], neither dominates the other: a conflict the system keeps as two siblings for the application (or a merge rule) to resolve. - Lamport clocks (one number) give an order but can't tell "later" from "concurrent"; vector clocks can, at the cost of one entry per writer.
- Lists grow with the number of writers, so real systems prune or use dotted version vectors.
Status today
Amazon's 2007 Dynamo paper made them famous; Riak used them (later dotted version vectors). Most modern stores chose simpler options: last-write-wins with timestamps (Cassandra, DynamoDB) or CRDTs (Module 19, D19).
Use it when
- Multi-leader or leaderless stores where concurrent edits must be detected, not silently overwritten
Skip it when
- Single-leader databases: the leader already orders writes
In the interview
If we allow writes in both regions, I need to detect conflicts: version vectors per item, or a CRDT for counters and sets.
- Claiming vector clocks give a total order: they deliberately don't.
Hybrid logical clocks (HLC)
Situational · ordering in distributed SQLA timestamp that is close to real time but also respects cause and effect: a physical time part plus a small logical counter. If event B happened because of event A, B's HLC is always larger, even if B's machine clock is a little behind.
How it works
- Each node keeps
(wall, logical). On a local event or send: take the max of its own value and the physical clock; bump the counter if the wall part didn't move. On receive: take the max of local, physical and the message's timestamp. - Timestamps fit in 64 bits and stay within the clock-skew bound of real time, so they're readable and can be used for snapshots "as of" a time.
- HLC doesn't remove uncertainty: databases still need a maximum clock offset, and transactions may restart when they see a value inside the uncertainty window.
Status today
Proposed by Kulkarni et al. (2014). Used by CockroachDB (nodes whose clocks drift beyond the configured maximum offset shut themselves down rather than risk anomalies), YugabyteDB and MongoDB's cluster time.
Use it when
- Distributed databases needing consistent snapshots without special hardware
Skip it when
- Application code: you get it inside the database, you don't build it
In the interview
CockroachDB orders transactions with hybrid logical clocks, so it needs NTP within its maximum offset, not atomic clocks.
- Assuming HLC makes clock sync unnecessary.
TrueTime and commit wait
Rare · Spanner's clockGoogle's clock API that returns an interval [earliest, latest] guaranteed to contain the true time, backed by GPS receivers and atomic clocks in every data centre. Spanner uses it to give globally consistent (externally consistent) transactions.
How it works
- Commit wait: a transaction takes a timestamp at the top of the interval, then waits until
earliesthas passed that timestamp before making the commit visible. After that, every machine anywhere agrees the commit is in the past, so a later transaction always gets a larger timestamp. - The wait is about twice the uncertainty. The 2012 Spanner paper reported uncertainty of roughly 1–7 ms; smaller uncertainty means shorter waits, which is why the hardware matters.
Status today (checked October 2026)
Available through Cloud Spanner. AWS's ClockBound exposes similar error-bounded time on EC2, and newer distributed databases use bounded clocks the same way.
Use it when
- Global transactions with strict ordering, when on Google Cloud (Spanner)
Skip it when
- Anything you'd build yourself: it's a property of the database
In the interview
Spanner gives external consistency across regions by waiting out TrueTime's uncertainty at commit, a few milliseconds.
- "Spanner beats CAP": it chooses consistency; it's just engineered so partitions are rare.
6. Remember it
How this hook works: what "Clocks lie, counters don't" means
What the slogan means, phrase by phrase
- "Clocks lie"
- Every machine's clock is off by some skew, drifts, and can jump backwards when corrected. Comparing timestamps across machines can give the wrong order.
- "counters don't"
- A counter incremented on each event and carried in messages (Lamport clock), a per-key sequence number, or a partition offset gives an order that respects cause and effect.
- (for IDs)
- Time-first IDs are sortable and index-friendly; uniqueness comes from the random bits or the worker-and-sequence bits, not the timestamp.
Why this picture fits: it's the friends with cheap watches. "Replying to message 41" is a counter; it's right even when every watch is wrong.
The story → the concept
| Friends and watches | Distributed system |
|---|---|
| Each friend's watch | A server's wall clock |
| Watches a minute fast or slow | Clock skew |
| Resetting a watch backwards | An NTP correction |
| "This answers message 41" | A Lamport clock or sequence number |
| Two messages that don't reply to each other | Concurrent events |
| Numbering your messages "Asha-1, Asha-2…" | Snowflake's worker ID plus sequence |
Watch it on an example
- A collaborative to-do app stamps each edit with the device's clock and keeps the latest.
- A phone with its clock 3 minutes fast edits an item; a laptop edits it again a minute later. The phone's older edit wins, and the laptop's change disappears.
- Switch to per-item version numbers (or a CRDT): each edit says which version it was based on, and concurrent edits are detected and merged.
- Timestamps stay, but only for showing "edited 2 minutes ago".
The trap it saves you from
Last-write-wins and lease expiry based on clocks from different machines: both fail silently when skew is larger than you assumed.
It still works when…
You read logs from many servers: sort by timestamp to get a rough picture, but trust trace IDs and parent-child links (Module 25) for what actually caused what.
7. Common mistakes
/orders/1042 tells competitors your volume and invites guessing other customers' orders. Check authorization, and consider opaque public IDs.8. Design exercise (25 minutes)
- Design an ID scheme for a global chat app with 50 data centres: requirements (unique, sortable, compact), the bit layout, and how worker IDs are assigned.
- Capacity check: with 12 sequence bits per millisecond, how many IDs a second can one worker produce? What happens if it needs more?
- Order chat messages: phones' clocks disagree. Describe how the server assigns order, and what the client shows while a message is unconfirmed.
- Vector clocks on paper: two replicas each update the same key once while partitioned. Write their vector clocks and show how a reader detects the conflict.
- Write it down: the ID comparison table, and "clocks lie, counters don't".
9. Self-check quiz
Which clock should measure how long a request took?
A process has Lamport clock 2 and receives a message stamped 4. What's its clock after receiving?
Which ID is time-sortable, needs no coordination and is index-friendly?
Two events on different servers with no message between them are…
Why is UUIDv7 a better primary key than UUIDv4 for a large, write-heavy table?
In a Snowflake ID with 12 sequence bits, how many IDs can one machine mint per millisecond?
10. Go deeper
| Resource | Time | Why |
|---|---|---|
| Time, Clocks, and the Ordering of Events in a Distributed System (Leslie Lamport, 1978) | 45 min | The founding paper: happened-before and logical clocks, short and readable. |
| RFC 9562: UUIDs, section 5.7 | 15 min | The UUIDv7 layout and why it was added. |
| Spanner: Google's Globally Distributed Database | 1 h | TrueTime and commit wait: using bounded clock uncertainty for global consistency. |
| Logical Physical Clocks (the hybrid logical clocks paper) | 45 min | How HLCs combine physical and logical time. |
| Twitter Snowflake (archived) | 10 min | The original ID generator and its bit layout. |