Clocks: physical, Lamport, vector and hybrid
Why wall clocks cannot order events across machines, and how Lamport, vector and hybrid logical clocks, and TrueTime's uncertainty intervals, fix it.
30 min8 steps
By the end you can
- Bound the offset between two clocks from drift rate and sync interval, and explain why wall-clock order is unsafe
- Apply the Lamport clock rules and state what a Lamport timestamp does and does not tell you
- Use vector clocks to tell a happens-before relation from concurrency
- Choose between physical, Lamport, vector, hybrid logical and TrueTime-style clocks for a requirement
Every clock is wrong, differently
1 ppm
1 us / s
about 86 ms per day
Two clocks, T seconds
2 x ppm x T us
before sync error
NTP step
can go backwards
use a monotonic clock for durations
Loading question…
Last-writer-wins silently loses writes
Select last-writer-wins loses an update under skew in Script.
Lamport clocks capture happens-before
1. Local event
C = C + 1
2. Send
stamp with C
3. Receive
C = max(C, stamp) + 1
Select lamport clock in Script.
Loading question…
What a Lamport timestamp cannot tell you
Known
- b did not happen before a
Unknown
- a before b?
- or concurrent?
- Vector clocks can tell
Vector clocks detect concurrency
X = [2, 1, 0] vs Y = [3, 1, 1]
- All entries <= and one <
- X happened before Y
X = [2, 1, 0] vs Y = [1, 2, 0]
- Each ahead somewhere
- Concurrent: keep both
Select vector clock in Script.
Hybrid logical clocks
l
max physical time seen
c
counter for same l
Size
64 bits
CockroachDB uses it
Select hlc clock in Script.
TrueTime: admit the uncertainty, then wait it out
TT.now()
[earliest, latest], width 2e
Pick
s = latest
Wait
Hold writes until earliest passes s (about 2e)
Visible
Externally consistent commit
Loading question…
Check your mastery
ppm x seconds
microseconds
Receive event
also ticks
Lamport clock
Score 80% or more. Leader election leases depend on these drift bounds.
Mastery check
5 questions on fresh variants. One attempt each, no time limit. Score 80% or more to master the lesson.
Answer this step to continue.