Hybrid Logical Clocks and TrueTime: Ordering Writes With Skewed Clocks

The idea: timestamps from clocks that disagree

A distributed database wants one timestamp per write, so that "the newest version" means the same thing on every node. The obvious choice is the node's wall clock. But wall clocks are never exactly right: even with NTP they are a few milliseconds apart, and sometimes much more. Two fixes are used in practice. A hybrid logical clock (HLC) mixes the wall clock with a Lamport-style counter, so causally related writes are always in order. Google Spanner's TrueTime measures how wrong the clock may be, and makes each commit wait that long.

On the canvas	Meaning
N1, N2, N3 and their panels	three nodes; N2's clock is 6 ms fast, N3's 5 ms slow; pt is what the node's wall clock reads now, below it the clock state of the chosen mode
true time t (the ruler)	the real time of each event, in ms from 100; no node can see it
dots	one event per column, in true-time order (not to scale): orange write, blue send, green receive, light green "visible" after commit wait; above a dot its timestamp
yellow bar	a TrueTime commit wait
store	every version of x with its timestamp; a read returns the highest one

Clock skew breaks last-write-wins

Each node's clock reads pt = t + offset, where t is true time. On the page N2 is 6 ms ahead. In Demo 1: clock skew breaks last-write-wins, N2 writes x=1 at true time 100, stamped 106. It then tells N1, and N1 writes x=2 at true time 104, stamped 104. N1's write came later and N1 had seen x=1, yet its timestamp is smaller. A store that keeps the highest timestamp (last write wins, as Cassandra does) returns x=1 and the newer write is lost. The message is odd too: sent at 107, received at 103.

The hybrid logical clock

An HLC timestamp is a pair (l, c). l is the largest wall-clock time the node has seen, its own or in a message. c is a counter that orders events while l stays the same. Pairs compare by l, then by c. The rules (Kulkarni et al., 2014):

local event or send:            receive a message (lm, cm):
  l' = l                          l' = l
  l  = max(l', pt)                l  = max(l', lm, pt)
  c  = (l == l') ? c + 1 : 0      c  = max(c, cm) + 1   if l == l' == lm
                                       c + 1            if l == l' only
                                       cm + 1           if l == lm only
                                       0                otherwise (pt won)

The receive rule is the Lamport rule on the pair: the receiver moves to at least the message's timestamp and then one past it. So if e happened before f, HLC(e) < HLC(f). In Demo 2: an HLC keeps the order N1's clock reads 103 when the message (107,0) arrives; it takes l = 107 from the message and c = 1, and its write becomes (107,2), above N2's (106,0).

Unlike a pure Lamport clock, l is a real time. It is never behind the node's wall clock, and never ahead of the fastest clock in the cluster. Once the local clock passes l, the counter goes back to 0 (Demo 3: HLC counter, then the wall clock catches up: (107,2), (107,3), then 5 ms later (111,0)). A timestamp fits in 64 bits, and you can still ask "what did the data look like at 10:15?". Demo 4: HLC across three nodes carries l = 107 from N2 through N1 to slow N3, whose own clock reads only 102.

CockroachDB stamps every transaction with an HLC. Its Now() is the send rule, and Update() moves the clock up to a timestamp it receives (every RPC carries one). It also needs a bound on skew: --max-offset, 500 ms by default. A node whose clock is further off than that from the others shuts itself down. Reads use the bound as an uncertainty interval: a value with a timestamp a little above the read's may have been written before the read in real time, so the read restarts at a higher timestamp. YugabyteDB and MongoDB use HLCs too.

Note what an HLC does not promise. Two writes with no message between them are concurrent, and they are ordered by the clocks, skew and all. If N2 writes and then, with no message, N1 writes 1 ms later, N2's write still wins. Try it with Write on N2, then Write on N1.

TrueTime: an interval, not a point

Spanner's TrueTime uses GPS receivers and atomic clocks in every data centre to keep the uncertainty small and known. TT.now() returns an interval [earliest, latest] that is guaranteed to contain true time. Its half-width ε is usually 1 to 7 ms; the page uses ε = 7 ms, so every node's offset (+0, +6, −5) is inside it.

A read-write transaction picks its commit timestamp s = TT.now().latest, a time that has surely not passed yet anywhere. Then comes commit wait: the transaction is not visible, and its locks are held, until TT.now().earliest > s, which takes about 2ε. After that, true time is past s for certain.

Why it works: T1 becomes visible at a true time after s1. A transaction T2 that starts after that, on any node, has an interval that contains its true time, so s2 = latest ≥ true time > s1. This is external consistency (strict serializability): commit timestamps follow real time, even when no message links the two transactions. In Demo 5: TrueTime commit wait, N2 commits with s = 113 and waits 15 ms; N3, whose clock is slow, then commits with s = 121. In Demo 6: TrueTime without commit wait, N2's write is visible at once while 113 is still in the future, and N3's later commit gets s = 106: the older value wins.

HLC vs TrueTime

	Hybrid logical clock	TrueTime
hardware	ordinary servers with NTP	GPS and atomic clocks in each data centre
timestamp	(l, c) from the clock and messages	s = TT.now().latest
order it guarantees	causal: if e → f then ts(e) < ts(f)	real time: if T1 finishes before T2 starts, s1 < s2
cost per write	none	commit wait of about 2ε
skew handling	max offset bound, uncertainty restarts on reads	ε is measured and waited out
used by	CockroachDB, YugabyteDB, MongoDB	Spanner

These timestamps then become MVCC version numbers: a snapshot read at time T sees every version with a timestamp ≤ T. See MVCC and isolation levels for what that buys, and Lamport clocks and vector clocks for the purely logical versions.

To see why a single number cannot detect concurrent writes while a vector can, compare the two on Lamport clocks vs vector clocks.

What the page leaves out

Clocks here are off by a fixed amount and never drift, every action takes exactly 1 ms and messages 2 ms. The page skips CockroachDB's uncertainty restarts and read refresh, its clock-offset monitoring between nodes, Spanner's Paxos groups, two-phase commit across groups (the coordinator waits for the largest s), read-only transactions at TT.now().latest and safe time, how ε is computed from the time masters and the drift rate (it grows between polls), and Spanner's later work to shrink ε.

References

Kulkarni, Demirbas et al.: Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases (2014)

Corbett et al.: Spanner, Google's Globally-Distributed Database (OSDI 2012), TrueTime and commit wait

Cockroach Labs: Living Without Atomic Clocks

CockroachDB source: pkg/util/hlc/hlc.go (Now, Update, max offset)