Concept Simulators / Copies and agreement
Clocks and ordering
Why timestamps lie, and how Lamport and vector clocks count causes instead.
On the roadmap:Advanced · step 2: Consistency models
Settings
What happens
A slow clock reads less than the real time and a fast one reads more. Real clocks drift apart by milliseconds, and sometimes by much more.
Events
6
Cause stamped after effect
0 of 11
Concurrent pairs
4
Selected
none
Clocks agree with causes here. Move a slider to give a machine a clock that is slow or fast, or click two events on the diagram to compare them. 4 pairs are concurrent.
Who did what, and when (click two events to compare)
Left to right is real time. The label under each event is its Lamport number.
In plain words
Clocks on different machines never agree exactly, so the time stamped on two events does not tell you which came first. Logical clocks give up on time and count causes instead. A Lamport clock gives every event a number that is bigger than that of anything that could have caused it. A vector clock goes further and can tell whether two events were related at all.
Why it matters
Distributed systems have to decide what happened before what: which write is newer, whether two edits conflict, whether a message arrived in order. Trusting timestamps from different machines gives wrong answers in a way that is rare and hard to debug. Here you can skew a clock and watch an effect appear before its cause.
How real systems do it
The simulation is a simplified model. Here is what production systems add or do.
- Leslie Lamport's 1978 paper Time, Clocks, and the Ordering of Events in a Distributed System introduced the happened-before relation and logical clocks. The idea underlies almost every later consensus and replication protocol.
- Amazon's Dynamo used vector clocks to detect conflicting updates to the same key and return both versions to the application. Riak did the same, and later versions of it moved to dotted version vectors to keep them small.
- Google Spanner takes the opposite approach: it keeps physical clocks tightly bounded with GPS receivers and atomic clocks (TrueTime) and waits out the uncertainty before committing, so timestamps can be trusted.
- Hybrid logical clocks combine a physical timestamp with a counter, giving times close to real time that still respect causes. CockroachDB and several other databases use them.
Study: Clocks and ordering
Once you have played with it, learn the same idea from people who build these systems. Watch first for the picture, then read for the detail.
11 minNetwork Time Protocol (NTP) - Computerphile
Computerphile · 209K views
