A Beginner’s Guide to Clocks, Causality, and Ordering in Distributed Systems
Why does something as simple as reading the time become a hard problem for distributed systems?
On a single computer, every event can be measured against one clock, so the order of the events is never in doubt. However, a distributed system, where work is spread across many independent machines, lacks a shared reference. Each machine can read time from its own hardware clock, but those clocks do not stay aligned. Network Time Protocol (NTP) tries to bring the clocks together, but it cannot eliminate the problem.
This becomes a real problem whenever correctness depends on the order in which things happened. If events on different machines are ordered by comparing timestamps, a small difference in the wrong direction can change the result. For example:
An update that happened later can be discarded in favor of an earlier one, because clock differences gave the earlier write the larger timestamp, and the newer data disappears with no error raised.
Logs gathered from several machines can place an effect before its cause, which makes tracing a problem much harder.
An operation that depends on a correct order, such as granting access only after the change that authorized it, can act on stale information.
In this article, we look at these ideas in detail:
Why a machine’s own clock is a poor basis for ordering events, and how close synchronization can realistically get
What it means for one event to have happened before another, and why some pairs of events have no defined order
Logical clocks and vector clocks, and what each one can and cannot determine
Why the order of events matters in practice, for replication, auditing, and debugging
Hybrid logical clocks and the problem they were designed to solve
How a globally distributed database such as Google Spanner approaches ordering at scale
