The theory of distributed systems promoted the use of logical clocks by introducing the idea of causality tracking as an abstraction for reasoning about concurrency between events in the system. In practice, a lot of systems continue to operate using physical time, which presents difficulties due to clock synchronization drift. In an effort to bridge the gap between physical and logical time, HybridTime combines both logical and physical times in one system.

Hybrid Logical Clocks (HLC) are extensions of the previous causality and time keeping systems that capture the causality relationship like logical clocks, but that can also substituted for physical clocks by maintaining its logical value always close to NTP. With these semantics, HLC can be used in lieu of a physical clock source like NTP for database reads, and it can simultaneously be used as a logical clock to identify consistent global snapshots.

Happens Before

The paper Logical Physical Clocks and Consistent Snapshots in Globally Distributed Database provides one of the best definitions I’ve found for the Happens Before relation we covered in Lamport Clocks. The authors begin by defining what they mean by events in a distributed system.

A distibuted system consists of a set of nodes whose number may change over time. Each node can perform three types of actions, a send action, a receive action, and a local action. The goal of a timestamping algorithm is to assign a timestamp to each event.

We can then use the relation “happened before” \( hb \) to capture the causal relationship between events in the system.

The HLC Algorithm

The goal of HLC is to provide a logical time that is close enough to physical time that it can act as a physical time replacement. We can codify this goal as a rule: for any event \( e \), \( l.e \gt pt.e \). The algorithm for achieving this builds off of Lamport Clocks, but records both the physical time and the logical time at each event. In pseudo-code the algorithm is expressed as:

l.j := 0, c.j := 0

Send or local event:
  l'.j := l.j;
  l.j := max(l'.j, pt.j);
  if (l.j = l'.j) then
    c.j := c.j + 1
  else
    c.j := 0
  return timestamp with l.j, c.j


Receive event of message m:
  l'.j := l.j;
  l.j := max(l'.j, l.m, pt.j);
  if (l.j == l'.j == l.m) then
    c.j := max(c.j, c.m) + 1
  else if (l.j == l'.j) then
    c.j := c.j + 1
  else if (l.j == l.m) then
    c.j := c.m + 1
  else
    c.j := 0
  return timestampe with l.j, c.j

Initially, l and c are set to 0. When a new send event f is created, l.j is set to max(l.e, pt.j, where e is the previous event that happened on a node j. This ensures that the logical clock value for an event at a node (l.j) is always greater than the physical clock value for hat node (pt.j). It is possible, however, that l.e is equal to l.f. That is, the previous event e has a logical timestamp equal to that of the new event f. In these cases, we use c as a means of capturing causality.

One of the key differences between this algorithm and Lamport Clocks is splitting the timestamp into two parts: l.j and c.j. The first part, l.j is used as a logical clock that records the maximum physical time stored so far, whereas c.j is used for capturing causality updates only when l values are equal stored so far, whereas c.j is used for capturing causality updates only when l values are equal.

Resources

Hybrid Logical Clocks are used in modern databases to maintain causality across nodes. For example, mongoDB uses hybrid timestamp to maintain versions in its MVCC storage and CockroachDB use hybrid timestamp to maintain causality with distributed transactions.

The HLC algorithm can be expressed fairly succinctly in code. There are implementations in JavaScript, Go and Java readily available.