The problem with clocks is that while they seem simple and easy to use, they have a surprising number of pitfalls. A day may not have exactly 86,400 seconds, time-of-day clocks may move backward in time, and the time according to one node’s clock may be quite different from another node’s clock.
Earlier in this topic we discussed networks dropping and arbitrarily delaying packets. Even though networks are well behaved most of the time, software must be designed on the assumption that the network will occasionally be faulty, and the software must handle such faults gracefully. The same is true with clocks: although they work quite well most of the time, robust software needs to be prepared to deal with incorrect clocks.
Part of the problem is that incorrect clocks easily go unnoticed. If a machine’s CPU is defective or its network is misconfigured, it most likely won’t work at all, so the issue will quickly be spotted and fixed. On the other hand, if its quartz clock is defective or its NTP client is misconfigured, most things will seem to work fine, even though its clock gradually drifts further and further away from reality. If a piece of software is relying on an accurately synchronized clock, the result is more likely to be silent and subtle data loss than a dramatic crash.
Thus, if you use software that requires synchronized clocks, it is essential that you carefully monitor the clock offsets between all the machines in your cluster. Any node whose clock drifts too far from the others should be declared dead and removed. Such monitoring ensures that you notice the faulty clocks before they can cause too much damage.
Timestamps for ordering events
Let’s consider one particular situation in which it is tempting, but dangerous, to rely on clocks: ordering of events across multiple nodes. For example, if two clients write to a distributed database, who got there first? Which write is the more recent one?
Figure 9-3 illustrates a dangerous use of time-of-day clocks in a database with multi-leader replication (the example is similar to Figure 6-8). Client A writes x = 1 on node 1; the write is replicated to node 3; client B increments x on node 3 (we now have x = 2); and finally, both writes are replicated to node 2. As this figure shows, when a write is replicated to other nodes, it is tagged with a timestamp according to the time-of-day clock on the node where the write originated. The clock synchronization is very good in this example; the skew between node 1 and node 3 is less than 3 ms, which is probably better than you can expect in practice.
Since the increment builds upon the earlier write of x = 1, we might expect that the write of x = 2 should have the greater timestamp of the two. Unfortunately, that is not what happens in Figure 9-3. The write x = 1 has a timestamp of 42.004 seconds, but the write x = 2 has a timestamp of 42.003 seconds. In other words, the write by client B is causally later than the write by client A, but B’s write has an earlier timestamp.
Diagram illustrating a conflict in multi-leader replication where client B's write occurs after client A's but receives an earlier timestamp due to node clock differences.
Figure 9-3. Relying on timestamps for ordering events can cause problems when time-of-day clocks are not perfectly synchronized.
As discussed in “Dealing with Conflicting Writes”, one way of resolving conflicts between concurrently written values on different nodes is last write wins (LWW), which means keeping the write with the greatest timestamp for a given key and discarding all writes with older timestamps. In Figure 9-3, when node 2 receives these two events, it will incorrectly conclude that x = 1 is the more recent value and drop the write x = 2, so the increment is lost.
This problem can be prevented by ensuring that when a value is overwritten, the new value always has a higher timestamp than the overwritten value, even if that timestamp is ahead of the writer’s local clock. However, that incurs the cost of an additional read to find the greatest existing timestamp. Some systems, including Cassandra and ScyllaDB, are designed to avoid this additional round trip and simply use the client clock’s timestamp along with a LWW policy. This approach has some serious problems:
-
Database writes can mysteriously disappear. A node with a lagging clock is unable to overwrite values previously written by a node with a faster clock until the clock skew between the nodes has elapsed. This scenario can cause arbitrary amounts of data to be silently dropped without any error being reported to the application.
-
LWW cannot distinguish between writes that occurred sequentially in quick succession (in Figure 9-3, client B’s increment definitely occurs after client A’s write) and writes that were truly concurrent (neither writer was aware of the other). Additional causality tracking mechanisms, such as version vectors, are needed in order to prevent violations of causality (see “Detecting Concurrent Writes”).
-
Two nodes could independently generate writes with the same timestamp, especially when the clock has only millisecond resolution. An additional tiebreaker value (which can simply be a large random number) is required to resolve such conflicts, but this approach can also lead to violations of causality.
Thus, even though it is tempting to resolve conflicts by keeping the most “recent” value and discarding others, it is important to be aware that the definition of “recent” depends on a local time-of-day clock, which may well be incorrect. Even with tightly NTP-synchronized clocks, you could send a packet at timestamp 100 ms (according to the sender’s clock) and have it arrive at timestamp 99 ms (according to the recipient’s clock)—so it appears as though the packet arrived before it was sent, which is impossible.
Could NTP synchronization be made accurate enough that such incorrect orderings cannot occur? Probably not, because NTP’s synchronization accuracy is itself limited by the network round-trip time, in addition to other sources of error such as quartz drift. To guarantee a correct ordering, you would need the clock error to be significantly lower than the network delay, which is not possible.
So-called logical clocks, which are based on incrementing counters rather than an oscillating quartz crystal, are a safer alternative for ordering events (see “Detecting Concurrent Writes”). Logical clocks do not measure the time of day or the number of seconds elapsed, only the relative ordering of events (whether one event happened before or after another). In contrast, time-of-day and monotonic clocks, which measure actual elapsed time, are known as physical clocks. We’ll look at logical clocks in more detail in “ID Generators and Logical Clocks”.
Clock readings with a confidence interval
You may be able to read a machine’s time-of-day clock with microsecond or even nanosecond resolution. But even if you can get such a fine-grained measurement, that doesn’t mean the value is actually accurate to such precision. In fact, it most likely is not. As mentioned previously, the drift in an imprecise quartz clock can easily be several milliseconds, even if you synchronize with an NTP server on the local network every minute. With an NTP server on the public internet, the best possible accuracy is probably to the tens of milliseconds, and the error may easily spike to over 100 ms with network congestion.
Thus, it doesn’t make sense to think of a clock reading as a point in time. It is more like a range of times, within a confidence interval—for example, a system may be 95% confident that the time now is between 10.3 and 10.5 seconds past the minute, but it doesn’t know any more precisely than that. If we know only the time +/– 100 ms, the microsecond digits in the timestamp are essentially meaningless.
The uncertainty bound can be calculated based on your time source. If you have a GPS receiver or atomic clock directly attached to your computer, the expected error range is determined by the device and, in the case of GPS, by the quality of the signal from the satellites. If you’re getting the time from a server, the uncertainty is based on the expected quartz drift since your last sync with the server, plus the NTP server’s uncertainty, plus the network round-trip time to the server (to a first approximation, and assuming you trust the server).
Unfortunately, most systems don’t expose this uncertainty; for example, when you call clock_gettime, the return value doesn’t tell you the expected error of the timestamp, so you don’t know whether its confidence interval is five milliseconds or five years.
There are exceptions. The TrueTime API in Google Spanner and Amazon ClockBound explicitly report the confidence interval on the local clock. When you ask it for the current time, you get back two values: [earliest, latest], which are the earliest possible and the latest possible timestamp. Based on its uncertainty calculations, the clock knows that the actual current time is somewhere within that interval. The width of the interval depends, among other factors, on how long it has been since the local quartz clock was last synchronized with a more accurate clock source.
Synchronized clocks for global snapshots
In “Snapshot Isolation and Repeatable Read” we discussed multiversion concurrency control (MVCC), which is a very useful feature in databases that need to support both small, fast read/write transactions and large, long-running read-only transactions (e.g., for backups or analytics). It allows read-only transactions to see a snapshot of the database, a consistent state at a particular point in time, without locking and interfering with read/write transactions.
Generally, MVCC requires a monotonically increasing transaction ID. If a write happened later than the snapshot (i.e., the write has a greater transaction ID than the snapshot), that write is invisible to the snapshot transaction. On a single-node database, a simple counter is sufficient for generating transaction IDs.
However, when a database is distributed across many machines, potentially in multiple datacenters, a global, monotonically increasing transaction ID (across all shards) is difficult to generate, because it requires coordination. The transaction ID must reflect causality: if transaction B reads or overwrites a value that was previously written by transaction A, then B must have a higher transaction ID than A—otherwise, the snapshot would not be consistent. With lots of small, rapid transactions, creating transaction IDs in a distributed system becomes an untenable bottleneck. (We will discuss such ID generators in “ID Generators and Logical Clocks”.)
Can we use the timestamps from synchronized time-of-day clocks as transaction IDs? If we could get the synchronization good enough, they would have the right properties because later transactions have a higher timestamp. The problem is the uncertainty about clock accuracy.
Spanner implements snapshot isolation across datacenters in this way. It uses the clock’s confidence interval as reported by the TrueTime API and is based on the following observation: if you have two confidence intervals, each consisting of an earliest and latest possible timestamp (A = [Aearliest, Alatest] and B = [Bearliest, Blatest]), and those two intervals do not overlap (i.e., Aearliest < Alatest < Bearliest < Blatest), then B definitely happened after A—there can be no doubt. Only if the intervals overlap are we unsure in which order A and B happened.
To ensure that transaction timestamps reflect causality, Spanner deliberately waits for the length of the confidence interval before committing a read/write transaction. By doing so, it ensures that any transaction that may read the data is at a sufficiently later time that their confidence intervals do not overlap. To keep the wait time as short as possible, Spanner needs to keep the clock uncertainty as small as possible; for this purpose, Google deploys a GPS receiver or atomic clock in each datacenter, allowing clocks to be synchronized to within about 7 ms.
The atomic clocks and GPS receivers are not strictly necessary in Spanner. The important thing is to have a confidence interval—accurate clock sources only help keep that interval small. Other systems are beginning to adopt similar approaches—for example, YugabyteDB can leverage ClockBound when running on AWS, and several other systems now also rely on clock synchronization to various degrees.