HybridTime introduces a hybrid between physical and logical clocks that can be used to implement globally consistent database snapshots. HybridTime is one implementation of the general concept of Hybrid Logical Clocks that combine the logical clock semantics of Lamport and Vector clocks with a physical representation of time such as Spanner’s TrueTime.

HybridTime follows similar update semantics as Lamport and Vector Clocks, where each node in the system updates their internal clock in response to events received. It differs in that HybridTime values are not purely logical — they include a physical time component that allows values to be associated with a physical point-in-time.

TrueTime’s key innovation is that timestamps assigned by the system serve a dual purpose: they are used to achieve external consistency, but they also have a physical meaning. This is in contrast to Lamport Clocks and Vector Clocks, in which timestamps are purely logical. HybridTime provides similar similar semantics to TrueTime by providing meaningful physical timestamps with bounded errors, but also leverages logical clocks to aid with consistency and correctness calculations.

Assumptions

HybridTime makes a few assumptions about the environment where it runs.

First, it assumes that nodes in the system have a reasonably accurate physical clock. This can be represented as a function \( PC_i(e) \) that returns a timestamp for process \( i \) for event \( e \).

Second, it assumes that the physical clocks on each system are periodically synchronized using a reference clock system. This can be represented by the function \( PC_{ref}(e) \) which returns the timestamp recorded by the reference process for an event \( e \). In addition, we assume that the reference synchronization system returns an error bound denoted by \( E_i(e) \) which returns the numeric error \( \epsilon \) of the process \( i \) at the time event \( e \) occurred.

We can formally codify these assumptions:

$$ \begin{aligned} \text{Assumption 1:} && \forall i,e : | PC_{ref}(e) - PC_i(e) | \leq E_i(e) && \text{(1)} \end{aligned} $$

Meaning that the physical timestamp returned by each server’s physical clock is within \( E_i(e) \) of the reference time. This assumption is plausible since most NTP deployments do provide a maximum error with regard to a master daemon, the time reference.

$$ \begin{aligned} \text{Assumption 2:} && \forall i,e : e \to f \Rightarrow PC_i(e) \leq PC_i(f) && \text{(2)} \end{aligned} $$

Meaning that the timestamp returned by a physical clock is always monotonically increasing. That is, when a server’s physical clock is queried for the current time, it never outputs a value that is less than a previous result.

These assumptions may seem like a large hurdle to overcome, but they actually are already implemented by the NTP system. In certain cases, NTP may skip time forward or backward, but such cases are extreme and easily detected by monitoring the NTP daemon status. Servers may choose to decommission themselves or fail-stop upon detection of such an event.

The HybridTime Clock Algorithm

A timestamp in the HybridTime protocol is represented as a pair \( ( \text{physical}, \text{logical} ) \), where \( \text{physical} \) represents the current physical time and \( \text{logical} \) is a logical sequence counter.

With this representation in hand, the full HybridTime algorithm can be represented with the following pseudo-code, reproduced from tech report HybridTime - Accessible Global Consistency with High Clock Uncertainty:

type Timestamp of {int physical, int logical}

int last physical = 0
int next logical = 0

PhysicalClock pc

function NOW : Timestamp
  Timestamp now;
  int cur physical = pc.now().physical;
  if cur physical ≥ last physical then
    now.physical = cur physical;
    now.logical = 0
    last physical = cur physical;
    next logical = 1;
  else
    now.physical = last physical;
    now.logical = next logical;
    next logical++;
  end if
  return now;
end function

function UPDATE(Timestamp in) : void
  int Timestamp now = Now();
  if now.physical > in.physical then
    return;
  end if
  last physical = in.physical;
  next logical = in.logical + 1;
end function

The first function, NOW, is used to obtain timestamps from the HybridTime clock. As we noted, this timestamp consists of two components, the current physical time as measured by the local clock, and a logical time defined by a sequence number. The physical component is defined as the larger of the value of the physical clock or the last known physical value. The logical timestamp is the next value in the sequence or 0. This determination is made depending on if the last time a measurement was taken, we selected the logical or physical timestamps as a record of time.

The second function, UPDATE, increases the local representation of time in response to receiving an incoming event with a timestamp. For any incoming timestamp if the incoming value’s physical component is lower that the one obtained through NOW() then no action is required. On the other hand, if the incoming value’s physical component is equal to the one obtained through NOW() then we set next logical to be the maximum of the current logical value and the incoming logical value, plus one, as in Lamport Clocks. Finally, if the physical component of the incoming value is higher than the one obtained through Now() we set last physical to it and next logical to be the incoming timestamp’s logical component plus one.

If you are familiar with the Lamport Clock algorithm, you will notice many similarities between the two algorithms. In fact, this algorithm actually implements a Lamport Clock, with the additional advantage that generated timestamps have physical meaning and are accurate representations of physical time within a bounded error term.

When reflecting on the simple concept of time, made much more difficult when measured across distributed systems, it’s amazing how far a simple concept like Lamport Clocks can be extended to solving real-world problems. HybridTime, like Vector Clocks, extend the ideas given by Lamport to provide consistent snapshots of data across multiple servers and are widely used techniques in modern databases.

Resources