system-design

Time, Clocks, and Ordering

“Which happened first?” is a much harder question than it sounds, and using timestamps to answer it silently corrupts data.

Prerequisites: The 8 Fallacies, Failure Modes Time to read: ~22 minutes

The problem

Two servers write to the same record:

Server A: sets name = "Bilal"   at its clock time 10:00:00.100
Server B: sets name = "Ayesha"  at its clock time 10:00:00.050

Last-write-wins says “Bilal” — it has the later timestamp.

🚨 But server B’s clock might be 200 ms ahead of server A’s. In real time, B’s write happened after A’s. You just silently discarded the newer value, and nothing anywhere logged an error.

Clocks on different machines disagree, and the disagreement is usually larger than the intervals you’re trying to order.

Two kinds of clock

Every machine has both, and confusing them causes real bugs.

Time-of-day clock (wall clock)

System.currentTimeMillis(), time.time(), NOW(). Returns seconds since the Unix epoch, synchronized by NTP.

✅ Meaningful across machines. Comparable to human time. Good for display and for logging.

❌ 🚨 It can jump backwards. NTP corrects drift by stepping the clock, which may move it back. Leap seconds. Someone changes the timezone. A VM resumes from a snapshot.

What this breaks:

start = time.time()
do_work()
elapsed = time.time() - start      # ← can be NEGATIVE if NTP stepped backwards

Monotonic clock

System.nanoTime(), time.monotonic(), CLOCK_MONOTONIC. Counts from an arbitrary point (usually boot) and only ever increases.

✅ Never goes backwards. Correct for measuring elapsed time, timeouts, and rate limiting. ❌ Meaningless across machines — the epoch is arbitrary and different everywhere.

🚨 The rule: monotonic for durations, wall clock for timestamps. Using the wall clock to measure a timeout means an NTP correction can make a 5-second timeout fire immediately or never. Using a monotonic clock to record when something happened is meaningless to anyone else.

This distinction is a small, specific thing that separates people who’ve been burned from people who haven’t.

How wrong are clocks, really?

Situation	Typical skew
Well-configured NTP, same datacenter	0.1–10 ms
NTP over the internet	10–100 ms
A VM after live migration	Can jump by seconds
A misconfigured or failed NTP client	Unbounded — minutes, hours, or years
Google Spanner with atomic clocks (TrueTime)	< 7 ms, and bounded with certainty

🚨 The important word is “typical.” Under normal conditions skew is small; when NTP fails — and it does, silently — skew is unbounded. A machine whose NTP daemon died six months ago can be minutes off, and nothing will tell you.

📐 The practical consequence: if two events are more than a second apart, wall-clock ordering is probably right. If they’re milliseconds apart — which is exactly the case in a write conflict — it’s a coin flip.

Why last-write-wins loses data

LWW is the most common conflict resolution strategy because it’s the simplest: keep the value with the highest timestamp, discard the rest.

⚖️ And it silently discards writes. Not “resolves conflicts” — discards data, with no error, no log, and no way to detect it afterwards.

Real time:
  t=0     Client A reads balance = 100
  t=10ms  Client B reads balance = 100
  t=20ms  Client A writes 150  (its clock says 10:00:00.020)
  t=30ms  Client B writes 200  (its clock says 10:00:00.015 — 15ms behind)

LWW keeps A's write (higher timestamp). B's write vanishes.
The user who set 200 sees 150 and has no idea why.

When LWW is acceptable: the data is a cache, a counter where approximate is fine, or genuinely last-writer-should-win semantics (a user’s own profile setting, where they’re the only writer).

When it’s not: anything where losing a write is a bug. Which is most things.

The alternatives — which is what the rest of this chapter and Conflict Resolution are about — are logical clocks and CRDTs.

Logical clocks: ordering without time

🚨 The key insight, and it’s genuinely elegant:

For most purposes you don’t need to know when something happened. You need to know what happened before what.

And causality can be tracked without any clock at all.

Lamport timestamps

Each node keeps a counter.

Rules:
Increment your counter before each event.
Send your counter with every message.
On receiving a message: counter = max(own, received) + 1

Node A:  1 ──2──────→ send(2)
                        ↓
Node B:       1 ────→ receive → max(1,2)+1 = 3 ──→ 4

Guarantee: if event a causally happened before b, then L(a) < L(b).

🚨 But not the converse. L(a) < L(b) does not mean a happened before b — they might be concurrent. Lamport timestamps give you a total order that’s consistent with causality, but they can’t tell you whether two events were actually related.

Vector clocks

Fix that by tracking a counter per node.

Node A:  [A:1, B:0, C:0]
Node B:  [A:0, B:1, C:0]

Now comparison is informative:

Comparison	Meaning
Every element of V1 ≤ V2, and at least one is strictly less	V1 happened before V2
Every element of V1 ≥ V2	V2 happened before V1
Some elements greater, some less	🚨 Genuinely concurrent — a real conflict

V1 = [A:2, B:1, C:0]
V2 = [A:1, B:3, C:0]
A: 2 > 1 but B: 1 < 3  →  concurrent. Neither caused the other.

This is the crucial capability: vector clocks can detect a genuine conflict, rather than silently picking a winner. You can then resolve it properly — merge, or ask the user, or apply domain logic.

⚖️ The cost: the vector grows with the number of nodes that have ever written, so metadata grows over time and needs pruning. This is why Dynamo used them and why many systems since have preferred CRDTs. → Conflict Resolution

Version vectors and hybrid clocks

Version vectors are the same idea applied to replicas of a data item — used by Riak and Dynamo.

Hybrid Logical Clocks (HLC) combine both: a physical timestamp with a logical counter for tie-breaking. You get roughly-wall-clock-meaningful values that also respect causality, in constant space. Used by CockroachDB and YugabyteDB, and increasingly the modern answer.

Google Spanner and TrueTime

The most interesting engineering response to this problem.

The idea: instead of pretending clocks are exact, measure the uncertainty and expose it. TrueTime returns an interval, not a point:

TT.now() → [earliest, latest]     typically ~7 ms wide, guaranteed to contain the true time

Achieved with GPS receivers and atomic clocks in every datacenter.

🚨 Then the clever part — “commit wait”: before committing a transaction, Spanner waits out the uncertainty window.

Transaction commits at time T
Spanner waits until TT.now().earliest > T
Now every subsequent transaction is guaranteed a later timestamp — everywhere, globally.

📐 It costs a few milliseconds of deliberate waiting per commit. In exchange you get external consistency (linearizability) across a globally distributed database — the strongest guarantee available, at planetary scale.

🎙️ The lesson worth stating: “Spanner doesn’t make clocks accurate — it makes the error bound *known, and then waits it out. That’s the difference between hoping your clocks agree and being able to reason about it.”*

Where this bites in practice

Ordering events in logs. Merging logs from 50 servers by timestamp gives you an order that’s subtly wrong — you’ll see a response logged before its request. Use trace IDs and spans, not timestamps, to reconstruct causality. → Distributed Tracing

Cache expiry. A TTL computed on one machine and evaluated on another with a skewed clock expires early or late.

Token and certificate expiry. 🚨 A JWT issued by a server whose clock is 5 minutes fast is rejected as “not yet valid” by every other server. This is a common, baffling production bug, and it’s why libraries have a configurable clock-skew tolerance (usually 30–60 seconds).

Distributed locks with TTLs. The lock expires according to whose clock? Skew means two holders. → Distributed Locking

Rate limiting. Window boundaries computed from a skewed clock let a client exceed the limit.

Scheduled jobs. “Run at 2 a.m.” — on which machine’s clock? → Background Jobs

Snowflake IDs. They embed a timestamp; a backwards clock jump means reissuing IDs already used. → Unique ID Generation

Practical rules

Never use wall-clock timestamps to order events across machines. Use logical clocks, sequence numbers, or a single authoritative sequencer.
Use monotonic clocks for durations, wall clocks for timestamps. Never the reverse.
Always store UTC, convert for display, and use TIMESTAMPTZ. → Relational Modeling
Assume clock skew of tens of milliseconds, and tolerate more. Build in leeway (JWT libraries default to 30–60 seconds for good reason).
Monitor clock skew as a metric. NTP fails silently; you want to know.
Have a single source of ordering where order matters — a database sequence, a Kafka partition offset, a leader.
Prefer detecting conflicts to silently resolving them. Vector clocks over LWW when losing a write is a bug.

🎙️ “I wouldn’t order these events by timestamp — clocks across machines disagree by more than the intervals we care about. I’d use the Kafka partition offset as the ordering authority, since it gives a single sequence per key.”

⚖️ Trade-offs

Approach	Gain	Cost
Wall-clock LWW	Trivial; no metadata	Silently loses writes; depends on clock accuracy
Lamport timestamps	Total order consistent with causality; tiny	Can’t distinguish concurrent from ordered
Vector clocks	Detects genuine conflicts	Metadata grows with node count; needs pruning
Hybrid logical clocks	Causality + roughly-real timestamps, constant size	More complex; still needs reasonable NTP
TrueTime (Spanner)	Global external consistency	Special hardware; a few ms of commit wait
Single sequencer (leader / Kafka partition)	Simple, exact ordering	Throughput ceiling; a coordination point

In the real world

Cassandra uses LWW by default with client-supplied timestamps, which means clock skew between clients silently loses writes. This is a documented, known hazard and a reason to configure NTP carefully and to prefer server-side timestamps or conflict-free structures where it matters.
The 2012 leap second caused widespread outages — Linux kernels livelocked, Java applications spun, and Reddit, Mozilla, and others went down. The industry response was leap smearing (spreading the extra second over a day), now standard at Google, AWS, and elsewhere.
CockroachDB uses hybrid logical clocks and enforces a maximum clock offset: a node whose clock drifts beyond the configured bound shuts itself down rather than risk correctness violations. That’s the right instinct — fail loudly rather than corrupt silently.

🚨 Interview traps

Ordering distributed events by timestamp. The most common mistake in this area.
Proposing last-write-wins without acknowledging it discards data.
Using the wall clock to measure elapsed time or implement timeouts.
Not knowing why vector clocks exist — the answer is detecting concurrency, not ordering it.
Ignoring clock skew in token expiry, locks, or rate-limit windows.
Assuming NTP guarantees accuracy. It fails silently and skew is unbounded when it does.

🎙️ Soundbites

“I wouldn’t order these by timestamp — clocks disagree by more than the intervals we’re comparing. I’d use a sequence number from a single authority, or the Kafka partition offset.”
“Last-write-wins doesn’t resolve conflicts, it discards data — silently, with no error. If losing a write is a bug here, we need vector clocks to detect the conflict, or a CRDT.”
“Monotonic clock for the timeout, wall clock for the audit log. An NTP correction stepping the wall clock backwards would make a duration calculation go negative.”
“Spanner’s insight is that you can’t make clocks exact, but you can make the error *bounded and known — then wait it out before committing. That’s what buys global external consistency.”*
“I’d allow 60 seconds of clock skew tolerance on token validation. Otherwise a server whose clock runs a few minutes fast issues tokens that everyone else rejects as not-yet-valid.”

🛠️ Try it

1. Break a duration calculation. Measure elapsed time with time.time() in a loop, then step your system clock backwards by 10 seconds. Watch it produce a negative duration. Switch to time.monotonic() and watch it stay correct.

2. Implement vector clocks. Three simulated nodes exchanging messages, each maintaining a vector. Then create a genuine conflict (two concurrent writes) and confirm your comparison function reports concurrent rather than picking a winner. That detection is the entire point, and implementing it once makes the concept permanent.

3. Measure real skew. Across a few machines:

ntpq -p                    # offset column, in milliseconds
chronyc tracking           # if using chrony

Then compare against a public time server and see how far off each machine actually is.

4. Cause the JWT skew bug. Issue a token on a machine whose clock is 5 minutes fast, validate it on a normal machine. It’s rejected as nbf (not before) in the future. Then set a leeway and watch it work.

Check yourself

1. Why can't you use timestamps to order events across machines?

Because clocks on different machines disagree, typically by milliseconds to tens of milliseconds under healthy NTP, and by unbounded amounts when NTP fails silently — which it does. The events you usually want to order (concurrent writes to the same record) are separated by *less* time than the typical skew, so timestamp comparison is effectively a coin flip. Worse, the wall clock can jump backwards when NTP steps it, so timestamps aren't even monotonic on a single machine. Order by a single authority instead: a database sequence, a Kafka partition offset, a leader's assigned sequence number, or logical clocks.

2. What's the difference between a monotonic and a wall-clock time source, and when do you use each?

A wall clock reports time since the Unix epoch and is synchronized by NTP — meaningful across machines and to humans, but it can jump forwards or backwards when corrected. A monotonic clock counts from an arbitrary origin and never decreases — meaningless across machines, but reliable for measuring intervals. **Use monotonic for anything measuring a duration**: timeouts, rate-limit windows, latency measurement, retry backoff. **Use wall clock for anything recorded or compared across machines**: log timestamps, `created_at` columns, token expiry. Using the wall clock for a timeout means an NTP step can make it fire immediately or never.

3. What do vector clocks give you that Lamport timestamps don't?

The ability to **detect concurrency**. Lamport timestamps guarantee that if *a* causally preceded *b* then *L(a) < L(b)*, but the converse doesn't hold — a smaller timestamp doesn't mean it happened first, so you can't tell whether two events were causally related or genuinely concurrent. Vector clocks track a counter per node, so comparing two vectors gives three possible answers: V1 before V2, V2 before V1, or **concurrent** (some elements greater, some less). That third answer is a real conflict you can then resolve deliberately — merge the values, apply domain logic, or ask the user — rather than silently discarding one. The cost is metadata that grows with the number of writers.

4. Why is last-write-wins dangerous, and when is it acceptable?

It's dangerous because it doesn't *resolve* conflicts — it discards one of them, silently, with no error and no audit trail, and the decision is based on clocks that disagree. A user's write can vanish because another server's clock was 20 ms ahead, and neither the user nor your monitoring will ever know. It's acceptable when the data is a cache (regenerable), when values are idempotent or approximate (a view counter), when there's genuinely only one legitimate writer (a user editing their own setting), or when the business explicitly accepts the loss. Otherwise use vector clocks to detect conflicts, or a CRDT that merges deterministically.

5. How does Spanner achieve globally consistent ordering, and what does it cost?

TrueTime returns a time *interval* — `[earliest, latest]` — guaranteed to contain the true time, with a width of a few milliseconds achieved using GPS receivers and atomic clocks in every datacenter. Spanner then applies **commit wait**: after assigning a transaction timestamp T, it deliberately waits until `TT.now().earliest > T` before making the commit visible. This guarantees any transaction starting afterwards — anywhere on Earth — receives a strictly later timestamp, giving external consistency (linearizability) globally. The cost is roughly the uncertainty width (a few milliseconds) of deliberate waiting on every commit, plus specialized hardware. The generalizable insight is that you can't eliminate clock error, but bounding it *with certainty* lets you reason about it.