Topic 13B.5
Time, Clocks & Ordering: Lamport, Vector Clocks, HLC
In one line
Machines' clocks disagree, so 'which happened first?' can't be answered with timestamps alone. Logical clocks capture cause and effect; vector clocks detect concurrent conflicting writes; hybrid clocks combine both with real time.
Think of it like this
Two people editing the same shared shopping list on phones with slightly wrong clocks. Phone A says 'added milk at 10:00:05', phone B says 'removed milk at 10:00:03'. Which came first? The wall clocks can't be trusted to decide.
Key ideas
- 01
PHYSICAL CLOCKS drift and are corrected by NTP, sometimes jumping backwards. Differences of milliseconds (or seconds on bad days) are normal between machines. So 'last write wins by timestamp' can silently drop the newer write. Google's Spanner uses GPS and atomic clocks with a known uncertainty window (TrueTime) and waits it out; most systems can't.
- 02
LAMPORT CLOCKS: each process keeps a counter, increments it on every event, sends it with messages, and on receive sets
counter = max(local, received) + 1. If A caused B, thenL(A) < L(B). They give a consistent total order, but can't tell whether two events were concurrent. - 03
VECTOR CLOCKS: each node keeps a counter per node. Comparing two vectors tells you whether one happened before the other or they're CONCURRENT (neither dominates), which is exactly a conflict needing resolution. Dynamo-style stores (Riak, the original Dynamo) used them to keep 'sibling' versions for the application to merge. CRDTs (conflict-free replicated data types) go further by designing data types that always merge automatically (collaborative editing, counters).
- 04
HYBRID LOGICAL CLOCKS (HLC) combine physical time with a logical counter: close to wall-clock time for humans, but never going backwards and preserving causality. CockroachDB and YugabyteDB use them for transaction ordering. Practical rule: use the database's ordering (sequence numbers, versions) or logical clocks for correctness; use wall-clock timestamps only for display and approximate ordering.
Code & diagrams
Explain without notes
Why is 'last write wins' based on wall-clock timestamps risky?
Practice
Two users edit the same profile field offline on different devices and then sync. How can the system detect and handle the conflict?
Trade-offs
- ↔
Lamport clocks are tiny but can't detect concurrency; vector clocks detect it but grow with the number of writers; HLCs track real time with causality but still need bounded clock skew.
Run it in production
You've designed it. Now build, operate, and break the same idea hands-on in the DevOps courses:
Completion checklist
I can explain why physical clocks can't order distributed events
I can describe Lamport vs vector clocks and when conflicts arise