Part 4 of 6 · 4 min read
Unreliable clocks
Each machine has its own clock, and they disagree.
Think of two shopkeepers whose wall clocks differ by a few minutes. Each says "I closed at 5:00." Whose 5:00 came first? Without a shared clock, no one can say.
The book describes two kinds of clock in a computer.
Time-of-day clock. It returns the date and time, for example the number of seconds since 1 January 1970 UTC. It is usually synchronised with a time server using NTP, so timestamps from different machines should roughly agree. But it may jump backward when the local clock is reset after getting too far ahead, and it ignores leap seconds. So it is unsuitable for measuring elapsed time.
Monotonic clock. It only moves forward, which suits measuring a duration, such as a timeout (Linux CLOCK_MONOTONIC, Java System.nanoTime()). Its absolute value is meaningless, since it may count from boot, so values from two machines must not be compared. NTP may speed it up or slow it by at most 0.05%, but cannot make it jump.
Time-of-day clock versus monotonic clock
A time-of-day clock tells the calendar time and can jump. A monotonic clock never goes back and is meant for measuring durations on one machine.
Example: to time a request, subtract two monotonic readings. To print a log timestamp, use the time-of-day clock.
How accurate are clocks? The book lists causes of error:
- Quartz drift. Google assumes 200 ppm (parts per million) for its servers. That is 6 ms of drift for a clock synchronised every 30 seconds, or about 17 seconds for one synchronised once a day.
- A clock far from the NTP server may be forced to reset.
- A firewall may silently block NTP, and nobody notices.
- NTP can only be as accurate as network delay: the book cites an experiment where about 35 ms was the best over the internet, with spikes near a second.
- Some NTP servers report times that are hours wrong. Clients ask several servers and ignore outliers.
- Leap seconds make a minute of 59 or 61 seconds, and have crashed large systems. One answer is smearing: spreading the extra second over a day.
Check the arithmetic: 200 ppm is 200 per million = 0.0002. Over 30 seconds that is 0.0002 × 30 = 0.006 s, or 6 ms. Over a day of 86,400 seconds it is 0.0002 × 86,400 = 17.28 s.
Ordering events by timestamp is dangerous. The book's example uses last write wins (LWW): the database keeps the write with the newest timestamp. Client A writes x = 1 on node 1 at timestamp 42.004 s. The write is copied to node 3. Client B then increments x to 2 on node 3 at timestamp 42.003 s, because node 3's clock runs a little behind. When node 2 receives both, it keeps x = 1 and drops B's later write. Skew was under 3 ms, yet the order came out wrong.
The problems of LWW, per the book:
- Writes can silently vanish: a node with a slow clock cannot overwrite values from a node with a fast clock until the skew passes.
- It cannot tell apart sequential writes from truly concurrent ones.
- Two nodes may make the same timestamp, so a tiebreaker is needed, which can also break causality.
A safer tool is a logical clock: a counter that records only the order of events, not the time of day. Version vectors (Level 4) are an example. Time-of-day and monotonic clocks are called physical clocks.
A reading is a range. A clock value of 10.4 seconds is better thought of as "between 10.3 and 10.5". Most systems do not tell the error. An exception is Google's TrueTime in Spanner, which returns [earliest, latest]. If two such intervals do not overlap, the order is certain. Spanner waits out the width of its uncertainty before committing, so that later transactions have later, non-overlapping times. Google uses GPS receivers or atomic clocks in each data centre, giving about 7 ms accuracy. The book says this is not yet found in mainstream databases outside Google.
A worked example. Clock A reads 100 ms ± 7 ms, so the true time lies in [93, 107]. Clock B reads 110 ms ± 7 ms: [103, 117]. The intervals overlap (103 to 107), so the order of the two events is unknown. If B read 120 ms ± 7 ms: [113, 127], no overlap with [93, 107], so B is certainly later.
Common mistake
Comparing time-of-day timestamps from two machines to decide which event came first, or using them to expire a lock set by another machine.
Check yourself:
- Which clock would you use for a timeout, and why?
- Why can last write wins lose a later write?