Hybrid Logical Clocks: Making Last-Write-Wins Mean the Later Write

Most conflict-resolution code I have read starts the same way: stamp each write with time.Now(), and on a tie, keep the newest timestamp. Last-write-wins. It survives the demo. It loses data the first time two replicas take writes a few milliseconds apart with clocks that disagree.

The trap is subtle. "Last write" sounds like it means "the event that happened later." With a wall clock, it means "the event from the node with the higher clock reading." Those are different sentences, and the gap between them is exactly the node-to-node clock skew. NTP on commodity hardware leaves clocks tens of milliseconds apart on a good day, and minutes apart on a bad one. So last-write-wins quietly rewards whichever machine is running fast, regardless of causal order.

I went down this path right after writing up why a CRDT merge function converges. That post fixed the problem at the data-structure layer: make the merge commutative, associative, and idempotent, and the clock stops mattering. This post fixes the same problem one layer down, at the timestamp itself. If I can make the timestamp respect causality, plain last-write-wins becomes correct again — and I get to keep a single comparable value instead of carrying per-element metadata.

That timestamp exists. It is the Hybrid Logical Clock, formalized in the 2014 paper Logical Physical Clocks and Consistent Snapshotting in Globally Distributed Databases by Kulkarni, Demirbas, and colleagues. It is also the quiet default inside modern distributed SQL: CockroachDB, YugabyteDB, and MongoDB all run HLC rather than Google's GPS-and-atomic-clock TrueTime. Worth a fresh look, since one of the co-authors now works on clocks at MongoDB Research and the design keeps showing up in production write-ups.

Where wall-clock last-write-wins drops the later write

Here is the concrete interleaving. Node A's physical clock reads 1000 ms. Node B's reads 995 ms — five milliseconds behind, well inside normal NTP error.

A user writes x = 1 on node A. A stamps it 1000. The write replicates to B. B's application logic reacts and writes x = 2, a strict causal successor: it only exists because A's write arrived. B stamps it with its own clock: 995.

Now both writes meet at a merge. Last-write-wins compares 1000 against 995 and keeps x = 1. The causally later write — the one that happened after and because of the first — loses, because B's quartz crystal runs slightly slow. No error, no log line. The value is just wrong, and stays wrong.

The picture below traces that interleaving and what HLC does to it.

​

What the counter actually buys

An HLC timestamp is a pair: (l, c). The l component tracks physical time — it stays close to the wall clock. The c component is a small integer counter that breaks ties when physical time cannot. Comparison is lexicographic: compare l first, then c.

Two rules govern how the pair moves. On a local event, take the larger of the stored l and the current physical clock. If l did not move (physical time has not advanced past it), bump the counter. If l did move, reset the counter to zero. On receiving a remote timestamp, take the largest of the stored l, the remote l, and the current physical clock, then set the counter so the result is strictly greater than both inputs.

That receive rule is the whole game. When B processes A's (1000, 0) while its own clock reads 995, it adopts l = 1000 — the maximum — and sets c = 1. B's follow-up write becomes (1000, 1), which sorts strictly after A's (1000, 0). The causal successor wins, even though B's hardware clock never reached 1000. The counter carried the order the wall clock could not.

The non-obvious worry is the counter running away. If a busy messaging loop keeps pushing l ahead of physical time, does c grow without bound? The paper's naive version does drift unboundedly. The HLC algorithm does not, and the reason is mechanical: every time physical time advances past l, the counter resets to zero. The authors prove c stays bounded — under the minimal assumption that a node's physical clock ticks at least once between two of its own events, c < N·(ε + 1), where ε is the clock skew bound and N the node count. In their experiments the counter mostly stayed in single digits. With 16 bits it has room up to 65,536; you would need that many events inside a single physical tick to overflow it, which does not happen in practice.

That bound is what makes the compact encoding safe. The paper packs the whole thing into 64 bits: 48 bits for l and 16 for c. CockroachDB uses the same shape. One int64, one comparison, and you have a timestamp that is monotonic per node and consistent with causality across nodes.

The implementation, in one file

Here is a self-contained Go version. The physical clock is injected as a function so the skew is reproducible instead of dependent on the host.

package main

import (
	"fmt"
	"sync"
)

// Clock is a Hybrid Logical Clock. wall is the physical-time component in
// milliseconds; counter breaks ties when wall does not move.
type Clock struct {
	mu      sync.Mutex
	wall    int64
	counter int64
	now     func() int64 // injectable physical clock, in ms
}

func New(now func() int64) *Clock { return &Clock{now: now} }

// Local stamps a local event and returns the new timestamp.
func (c *Clock) Local() (int64, int64) {
	c.mu.Lock()
	defer c.mu.Unlock()
	prev := c.wall
	c.wall = max64(prev, c.now())
	if c.wall == prev {
		c.counter++
	} else {
		c.counter = 0
	}
	return c.wall, c.counter
}

// Receive merges a remote timestamp into this clock and returns the new one.
func (c *Clock) Receive(rWall, rCounter int64) (int64, int64) {
	c.mu.Lock()
	defer c.mu.Unlock()
	prev := c.wall
	c.wall = max64(prev, rWall, c.now())
	switch {
	case c.wall == prev && c.wall == rWall:
		c.counter = max64(c.counter, rCounter) + 1
	case c.wall == prev:
		c.counter++
	case c.wall == rWall:
		c.counter = rCounter + 1
	default:
		c.counter = 0
	}
	return c.wall, c.counter
}

// Pack folds the timestamp into one int64: 48 bits wall, 16 bits counter.
func Pack(wall, counter int64) int64 { return wall<<16 | (counter & 0xFFFF) }

func max64(xs ...int64) int64 {
	m := xs[0]
	for _, x := range xs[1:] {
		if x> m {
			m = x
		}
	}
	return m
}

func main() {
	// Two nodes. Node B's physical clock is stuck 5 ms behind A's.
	clockA := int64(1000)
	clockB := int64(995)
	a := New(func() int64 { return clockA })
	b := New(func() int64 { return clockB })

	// A stamps a write, then sends it to B.
	wA, cA := a.Local()

	// B receives A's write. Its slow wall clock must not lose the ordering.
	wB, cB := b.Receive(wA, cA)
	if Pack(wB, cB) <= Pack(wA, cA) {
		panic("causality lost: B's stamp is not after A's")
	}

	// B stamps a follow-up event without its physical clock advancing.
	w2, c2 := b.Local()
	if Pack(w2, c2) <= Pack(wB, cB) {
		panic("monotonicity lost: counter did not advance")
	}
	if c2 != cB+1 {
		panic("counter should have incremented by exactly one")
	}

	fmt.Printf("A:(%d,%d)  B<-A:(%d,%d)  B next:(%d,%d)\n", wA, cA, wB, cB, w2, c2)
}

Run it with go run hlc.go. It prints:

A few lines carry the weight. In Receive, the case c.wall == rWall branch is the skew fix: B's physical clock reads 995, so max64(0, 1000, 995) is 1000, which equals the remote l but not B's old l, so the counter becomes rCounter + 1 = 1. That single increment is what makes B's stamp sort after A's. The four-way switch looks fussy, but each branch answers one question — did l come from the local clock, the remote stamp, both, or neither — and sets the counter to stay strictly ahead of whatever it adopted. Pack is the encoding from the paper; shifting wall left by 16 and oring in the masked counter gives one comparable int64.

I keep the comparison out of the clock type on purpose. The clock's only job is to produce monotonic, causal stamps; deciding which write wins is the merge layer's job, and it is just Pack(a) < Pack(b).

For tests, I drive the same logic three ways: a regression test pinning the exact skew interleaving above, a monotonicity test that stamps events while the wall clock is frozen and checks the counter both climbs and resets when the clock advances, and a seeded fuzz that runs five thousand random local-or-receive steps across three skewed nodes and asserts each node's stamps stay strictly increasing. The fuzz is the one that earns its keep — a hand-written case never hits the interleaving you forgot.

What HLC does not give you

HLC orders events. It does not detect that two events were concurrent. This is the same limitation Lamport clocks have, and it matters more than it first looks. If two nodes write independently with no message between them, HLC still produces two comparable timestamps and last-write-wins still discards one. The order it imposes is arbitrary for genuinely concurrent writes — it just happens to be consistent and monotonic, so every replica discards the same one. You get convergence, not conflict awareness. To actually detect "these two writes conflict, surface both," you need version vectors or a CRDT — which is the whole reason the merge-function approach and HLC solve different halves of the problem.

HLC also does not make clock skew go away. It bounds and masks skew up to ε; beyond that, ordering breaks. This is where the production cost lives. CockroachDB runs HLC with a static maximum clock offset, 500 ms by default, and a reading transaction carries an uncertainty interval of [ts, ts + max_offset]. If a read sees a value stamped inside that window, the database cannot prove the value is in the past rather than a skew artifact, so it restarts the transaction at a higher timestamp. That restart is real latency, paid to convert "probably ordered" into "provably ordered." Tighten the offset and you cut the uncertainty window but raise the risk of crossing it; CockroachDB's own guidance treats the 500 ms default as a safety margin, not a target.

And when skew exceeds the bound, HLC does not paper over it — the system protects itself instead. A CockroachDB node that detects its clock drifting more than 80% of the max offset (400 ms at the default) versus a majority of peers shuts itself down rather than serve possibly-misordered reads. That is the honest shape of the trade: HLC buys you correct ordering on commodity NTP as long as the clocks stay within the bound, and the fallback for breaching it is a dead node, not silent corruption. MongoDB, which uses HLC for cluster-time and causal consistency, leans the other way — more transaction restarts and longer causal-read waits instead of self-shutdown.

When to reach for it

Reach for an HLC when you need a single monotonic, causally-consistent timestamp and you cannot afford per-key metadata: multiversion stores, snapshot reads, last-write-wins registers where you want the later write to actually win, and ordering events across services that already exchange messages. It is O(1) per event, it rides on the NTP you already run, and it drops into anywhere you currently call time.Now().

Skip it when last-write really is the intent and a single writer owns the key — a plain wall clock is fine and cheaper to reason about. Skip it when you need to detect concurrent updates rather than silently order them; that is version-vector or CRDT territory. And do not treat it as a substitute for synchronized clocks: HLC bounds skew's damage, it does not eliminate skew, and the uncertainty-restart cost scales with how far apart your clocks drift.

Actionable takeaways:

• Replace wall-clock timestamps in last-write-wins with an HLC pair (l, c); compare lexicographically so the causally later write wins under skew.
• Inject the physical clock behind an interface so you can pin skew and write a deterministic regression plus a seeded fuzz.
• Pack l and c into one 64-bit value (48 bits / 16 bits) — the proven counter bound makes 16 bits safe.
• Budget for the uncertainty cost: tighter clock-offset bounds mean fewer restarts but less headroom before a node has to fence itself off.

Use it for monotonic causal timestamps on commodity NTP. Avoid it when you need concurrency detection, when a single writer makes plain wall-clock last-write-wins correct, or when you are tempted to read it as a clock-synchronization fix it was never meant to be.