Event Ordering, Logical Clocks, TrueTime, and Hybrid Logical Clock in Distributed Systems

Linearizability is crucial for systems such as distributed databases; after a write, subsequent reads must see the new value, otherwise anomalies like reading an outdated balance in a bank transfer can occur.

A simplified example: after executing set a = 10 at time t , every read a after t must return 10, not a previous value.

To guarantee that a read observes the latest write, we rely on the "happened‑before" relation: if event a occurs before event b , we denote it as a → b . Within a single process this ordering is trivial, but in a distributed system events may reside in different processes that communicate with each other, making the ordering non‑trivial.

Using physical timestamps alone is unreliable because each machine’s clock can drift; even with NTP synchronization there remains error, so system time cannot be directly used to decide event order.

Logic Clock

Lamport introduced Logical Clocks in the 1970s to establish a total order of events. Each event a has a logical timestamp C(a) . If two events occur in the same process and a → b , then C(a) < C(b) . For events across processes, the sender attaches its clock value to the message; the receiver updates its clock to be greater than the received value (typically C(received) + 1 ), ensuring C(b) > C(a) for related events.

Vector clocks extend this idea but still lack a real‑time component, making it impossible to query events by actual wall‑clock time.

True Time

Google Spanner solves the distributed‑time problem by combining GPS and atomic clocks to create a hardware‑based TrueTime service with millisecond‑level accuracy. The TrueTime API provides three methods:

Method

Return

TT.now()

TTinterval: [earliest, latest]

TT.after(t)

true if

t

has definitely passed

TT.before(t)

true if

t

has definitely not arrived

Spanner obtains a narrow time interval [t‑ε, t+ε] . If the earliest time of event b is later than the latest time of event a , then b is guaranteed to occur after a . This introduces a short commit‑wait (≈2ε) but provides global ordering with high performance.

Hybrid Logical Clock (HLC)

When hardware TrueTime is unavailable, CockroachDB adopts a software‑based Hybrid Logical Clock, which combines a physical clock l.j and a logical counter c.j . The physical component is read from the system clock; the logical component resolves ordering when physical clocks are equal or experience drift.

HLC algorithm (node j ):

Initialization:

l.j = 0, c.j = 0

When sending or processing a local event:

l'.j = l.j; // compare with current system time pt l.j = max(l'.j, pt.j); if (l.j == l'.j) { c.j = c.j + 1; } else { c.j = 0; } // Timestamp = (l.j, c.j)

When receiving a message from node m :

l'.j = l.j; l.j = max(l'.j, l.m, pt.j); if (l.j == l'.j && l.j == l.m) { c.j = max(c.j, c.m) + 1; } else if (l.j == l'.j) { c.j = c.j + 1; } else if (l.j == l.m) { c.j = c.m + 1; } else { c.j = 0; } // Timestamp = (l.j, c.j)

HLC works well as long as NTP remains reasonably accurate; severe NTP failures can cause large drift, at which point CockroachDB logs warnings or discards out‑of‑bounds messages.

Timestamp Oracle (TSO)

For smaller clusters without global requirements, a centralized Timestamp Oracle can provide a single source of time, as used in Google Percolator. Benefits include simple ordering and high throughput (10⁵+ QPS). Drawbacks are network latency, single‑point‑of‑failure concerns, and the need for fault‑tolerance mechanisms such as Zookeeper or etcd.

In practice, many database products start with a TSO and may later adopt TrueTime or HLC if global synchronization becomes necessary.

Conclusion

Time‑based ordering is fundamental in distributed systems, but achieving a globally consistent and accurate notion of time is challenging; solving this problem simplifies the design of linearizable systems, though additional considerations arise when supporting distributed transactions.