Hybrid logical clocks and TrueTime

Logical clocks respect cause and effect, but they know nothing about real time. Physical clocks know real time, but they ignore cause and effect, and they drift. Hybrid logical clocks (HLC) combine the two. TrueTime takes a different route. It makes the clock's uncertainty explicit, and it waits that uncertainty out before it commits.

The big idea

HLC gives each timestamp two parts. The first part stays close to real time. The second part keeps causality, because it moves forward whenever a message arrives from a node that is ahead.

TrueTime gives up on exact time. It returns a range that is guaranteed to contain the true time. Then it makes sure no answer depends on the part of the range you can't see.

Walking through it

HLC. Each node follows a few update rules. A local event or send, with physical time pt, does this:

l_new = max(l, pt)
c     = (l_new == l) ? c + 1 : 0
l     = l_new

On receiving a message with (l_m, c_m), the node takes the largest of its own l, the message's l_m and pt. It sets c to keep the order moving forward. The result fits in 64 bits, stays close to physical time, and respects happens-before like a Lamport clock.

CockroachDB uses HLCs to timestamp transactions. It also enforces a configured maximum clock offset between nodes, which is hundreds of milliseconds by default. When a transaction reads a value whose timestamp falls inside its uncertainty window, it can't tell which came first. It bumps its timestamp and retries the read. A node whose clock drifts too far shuts itself down rather than risk a consistency violation. The trade is commodity clocks, paid for with occasional retries.

TrueTime. Google's Spanner took the opposite approach. Each data center has time masters with GPS receivers and atomic clocks. The TrueTime API returns an interval, not one value:

TT.now() = [earliest, latest]     width = 2ε
guarantee: the true absolute time is inside the interval

The 2012 Spanner paper reports ε typically between about 1 and 7 ms.

To give transactions timestamps that match real-time order, Spanner uses commit-wait:

1. When a transaction is ready to commit, it picks s = TT.now().latest.
2. It waits until TT.now().earliest > s.
3. Only then does it make the writes visible and reply to the client.

Once the wait is over, the true time is past s for every node. Any later transaction gets a larger timestamp, with no coordination between the two.

Work the numbers. With ε = 4 ms, the interval is 8 ms wide, so commit-wait is about 8 ms. Spanner overlaps that wait with replication, which often takes longer anyway, so the wait is frequently hidden. Halve ε and you halve the wait.

Common mistakes

• Thinking HLC removes uncertainty. It bounds the drift and relies on a maximum offset. Nodes outside that bound must stop.
• Ignoring the cost of commit-wait. Tighter clocks are what keep it short. Without them, every commit pays for a wide window.
• Assuming TrueTime is available everywhere. It depends on dedicated time hardware in each data center.

Check yourself

1. Spanner's ε is 4 ms. About how long is commit-wait? About 8 ms, because the uncertainty interval is 2ε wide.
2. What does the counter c in an HLC do? It breaks ties when the physical part doesn't advance, so causality is still respected.

Key takeaways

• HLC timestamps stay close to real time and still respect cause and effect.
• CockroachDB pairs HLCs with a maximum offset, and retries reads inside the uncertainty window.
• TrueTime makes the uncertainty explicit, and commit-wait waits it out.
• Tighter clocks directly lower commit latency.

Further learning

Living without atomic clocks (CockroachDB) explains the uncertainty-window design in plain terms.

Logical Physical Clocks and Consistent Snapshots (Kulkarni et al.) is the original HLC paper.

Next, return to the clocks and ordering overview to see how these ideas connect to consensus.