In “Unreliable Clocks” we discussed time-of-day clocks and monotonic clocks. Both are physical clocks: hardware devices that measure the passing of time (seconds, milliseconds, microseconds, etc.).
In distributed systems it is common to also use another kind of clock, called a logical clock. In contrast to a physical clock, a logical clock is an algorithm that counts the events that have occurred. A timestamp from a logical clock therefore doesn’t tell you what time it is, but you can compare two timestamps from a logical clock to tell which one is earlier and which one is later.
The general requirements for a logical clock are as follows:
-
Its timestamps are compact (a few bytes in size) and unique.
-
You can compare any two timestamps and determine which one is earlier (i.e., they are totally ordered).
-
The order of timestamps is consistent with causality. That is, if operation A happened before operation B, then A’s timestamp is less than B’s timestamp. (We discussed causality previously in “The happens-before relation and concurrency”.)
A single-node ID generator meets these requirements, but the distributed ID generators we just discussed do not meet the causal ordering requirement.
Lamport timestamps
Fortunately, a simple method for generating logical timestamps is consistent with causality, and you can use it as a distributed ID generator. It is called a Lamport clock, proposed in 1978 by Leslie Lamport, in what is now one of the most-cited papers in the field of distributed systems.
Although Lamport clocks provide a total ordering, they do not provide linearizability—that is, they are not a way of ensuring that a value is up-to-date. They are merely a way of assigning IDs to events such that if event A happened before event B, then A’s ID is less than B’s ID.
Figure 10-9 shows how a Lamport clock would work in the chat example from Figure 10-8. Each node has a unique identifier, which in Figure 10-9 is the name Aaliyah, Bryce, or Caleb, but which in practice could be a random UUID or something similar. Each node also keeps a count of the operations it has processed. A Lamport timestamp is then simply a pair of (counter, node ID). Two nodes may sometimes have the same counter value, but by including the node ID in the timestamp, each timestamp is made unique.
Diagram illustrating how Lamport timestamps work in a chat scenario, showing message exchanges between nodes labeled "Aaliyah," "Bryce," and "Caleb" with unique identifiers and counters.
Figure 10-9. Lamport timestamps provide a total ordering consistent with causality.
Every time a node generates a timestamp, it increments its counter value and uses the new value. Every time a node sees a timestamp from another node, if the counter value in that timestamp is greater than its local counter value, it increases its local counter to match the value in the timestamp.
In Figure 10-9, Aaliyah had not yet seen Caleb’s message when she posted her own, and vice versa. Assuming both users start with an initial counter value of 0, both therefore increment their local counter and attach the new counter value of 1 to their message. When Bryce receives those messages, he increases his local counter value to 1. Finally, Bryce sends a reply to Aaliyah’s message, incrementing his local counter and attaching the new value of 2 to the message.
To compare two Lamport timestamps, we first compare their counter value—for example, (2, “Bryce”) is greater than (1, “Aaliyah”) and also greater than (1, “Caleb”). If two timestamps have the same counter value, we then compare their node IDs, using the usual lexicographic string comparison. Thus, the timestamp order in this example is (1, “Aaliyah”) < (1, “Caleb”) < (2, “Bryce”).
Hybrid logical clocks
Lamport timestamps are good at capturing the order in which things happened, but they have some limitations:
-
Since they have no direct relation to physical time, you can’t use them to find, say, all the messages that were posted on a particular date; you would need to store the physical time separately.
-
If two nodes never communicate, one node’s counter increments will never be reflected in the other one’s counter. As a result, events generated around the same time on different nodes could have wildly different counter values.
A hybrid logical clock combines the advantages of physical time-of-day clocks with the ordering guarantees of Lamport clocks. Like a physical clock, it counts seconds or microseconds. Like a Lamport clock, when one node sees a timestamp from another node that is greater than its local clock value, it moves its own local value forward to match the other node’s timestamp. As a result, if one node’s clock is running fast, the other nodes will similarly move their clocks forward when they communicate.
Every time a timestamp from a hybrid logical clock is generated, it is also incremented, which ensures that the clock moves forward monotonically even if the underlying physical clock jumps backward—for example, because of NTP adjustments. Thus, the hybrid logical clock might be slightly ahead of the underlying physical clock. Details of the algorithm ensure that this discrepancy remains as small as possible.
As a result, you can treat a timestamp from a hybrid logical clock almost like a timestamp from a conventional time-of-day clock, with the added property that its ordering is consistent with the happens-before relation. It doesn’t depend on any special hardware and requires only roughly synchronized clocks. Hybrid logical clocks are used by CockroachDB, for example.
Lamport/hybrid logical clocks versus vector clocks
In “Multiversion concurrency control” we discussed how snapshot isolation is often implemented: essentially, by giving each transaction a transaction ID, and allowing each transaction to see writes made by transactions with a lower ID but making writes by transactions with higher IDs invisible. Lamport clocks and hybrid logical clocks are a good way of generating these transaction IDs because they ensure that the snapshot is consistent with causality.
When multiple timestamps are generated concurrently, these algorithms order them arbitrarily. This means that when you look at two timestamps, you generally can’t tell whether they were generated concurrently or one happened before the other. (In Figure 10-9, you actually can tell that Aaliyah and Caleb’s messages must have been concurrent, because they have the same counter value; however, when the counter values are different, you can’t tell whether they were concurrent.)
If you want to be able to determine when records were created concurrently, you need a different algorithm, such as a vector clock. Vector clocks keep a counter for each node and store all the counter values with each write. If write A has a higher counter value than B for one node, and write B has a higher counter value than A for another node, then A and B must be concurrent (see “Detecting Concurrent Writes”). The downside is that the timestamps from a vector clock take up much more space than the other timestamps we have discussed—potentially one integer for every node in the system.