Clocks and Ordering: Lamport, Vector, and Hybrid Logical Clocks

TL;DR: Wall-clock time is not safe for ordering events across machines. NTP skew between cloud VMs is routinely 10 to 250 ms^[1], quartz oscillators drift up to 150 ppm^[2], and leap seconds have crashed production systems from Reddit to Cloudflare^[3][4]. Use Lamport timestamps when you need a cheap total order, vector clocks when you must detect concurrency, and Hybrid Logical Clocks (HLC) when you need causal ordering in a 64-bit timestamp compatible with wall-clock reasoning. TrueTime is a hardware advantage that originally bounded epsilon to "usually less than 7 ms" (Corbett et al., OSDI 2012) and, as of Google's 2023 update, to under 1 ms at p99^[5][6]; you cannot replicate it in software, but AWS ClockBound now brings similar sub-millisecond bounds to EC2. Any time you see ORDER BY created_at on data written by many nodes, be suspicious.

Learning Objectives#

After this module, you will be able to:

• Define happens-before and distinguish causal from concurrent events
• Use Lamport timestamps to build a total order consistent with causality
• Use vector clocks to detect concurrent updates
• Explain HLC: a logical counter pinned to physical time in 64 bits
• Describe TrueTime and how Spanner uses bounded uncertainty for external consistency
• Choose the right clock for a given system design

Intuition#

Imagine two photographers at a wedding, each with a wristwatch. Photographer A's watch runs 30 seconds fast. Photographer B's watch runs 20 seconds slow. Both stamp every photo with their watch time. Later, you try to arrange all photos in chronological order by timestamp. The result is wrong: some of A's "later" photos actually happened before B's "earlier" ones, and you cannot tell which from the timestamps alone.

Now imagine a corporate mailroom that stamps every incoming letter with a counter: letter 1, letter 2, letter 3. The counter does not know what time it is, but it guarantees that if letter 5 was a reply to letter 3, then 3 < 5. You cannot tell real-world time from the stamp, but you can tell causality. That is the trade-off between physical clocks (human-readable but unreliable across machines) and logical clocks (reliable ordering but no connection to wall time).

Distributed systems need ordering. Consistency models and consensus protocols assume you have it. This chapter teaches you where ordering actually comes from.

Theory#

Why wall-clock time fails#

Every computer has a quartz oscillator that drifts. Commodity motherboards drift up to 150 parts per million^[2:1], which accumulates to tens of seconds per day if uncorrected. NTP corrects drift by slewing or stepping the clock, but in cloud VMs the sync is routinely 10 to 250 ms off^[1:1]. During NTP outages, skew can reach multiple seconds.

Three failure modes make wall clocks dangerous for ordering:

Leap seconds. Between 1972 and 2016, the IERS inserted 27 leap seconds at irregular intervals (about every 21 months on average, but with gaps as long as 6 years). The most recent leap second was December 31, 2016; none have been inserted since, and the CGPM voted in November 2022 to phase out the practice by 2035 at the latest^[7]. Even with no new insertions, legacy leap-second bugs still haunt systems that handle historical timestamps or run on older code paths. On June 30, 2012, the Linux kernel's hrtimer/futex path deadlocked when the second was inserted, causing CPU saturation on servers running Reddit, Mozilla, Cassandra, and Hadoop^[4:1][8]. On January 1, 2017, Cloudflare's RRDNS (written in Go) computed a negative RTT when time.Now() ran backward across the leap second, panicking rand.Int63n with a negative argument and erroring approximately 0.2% of DNS queries at peak, with full resolution taking about 6 hours and 45 minutes^[3:1].

Non-monotonic jumps. POSIX CLOCK_REALTIME can jump in either direction (NTP step, admin action, leap second). Any code that computes elapsed = now - start without using a monotonic clock source is vulnerable.

VM pauses. Hypervisor steal time and live-migration freezes can pause a guest for hundreds of milliseconds. The guest's clock appears to jump forward on resume, but events during the pause have no timestamps at all.

Happens-before (Lamport 1978)#

Leslie Lamport sidestepped physical time entirely^[9]. His "happens-before" relation (written ->) captures the only ordering that matters for program correctness:

• Same-process rule: if a and b are events in the same process and a comes first, then a -> b.
• Message rule: if a is the send of a message and b is its receive, then a -> b.
• Transitivity: if a -> b and b -> c, then a -> c.

Events not related by -> are concurrent (written a || b). Concurrency does not mean "at the same instant." It means neither event could have influenced the other. This is the foundation of all logical clocks.

Events a -> b -> c form a causal chain; event d is concurrent with a (no message path connects them), even though d may have happened "at the same time" on a wall clock.

Lamport timestamps#

A Lamport timestamp is a scalar counter per process^[9:1]:

1. On a local event: C_P += 1
2. On sending a message: tag it with C_P (after increment)
3. On receiving a message with tag t: C_P = max(C_P, t) + 1

To break ties, extend the timestamp to (C_P, process_id) and compare lexicographically. The result is a total order consistent with causality: if a -> b, then LC(a) < LC(b).

The critical limitation: the converse does not hold. LC(a) < LC(b) does not imply a -> b. Two concurrent events get different Lamport timestamps, but you cannot tell them apart from causally ordered events. Lamport timestamps erase concurrency information.

Use Lamport timestamps when: you need a cheap total order for a log (like Raft's log index) and do not need to detect concurrent writes.

Vector clocks#

Vector clocks (Fidge 1988, Mattern 1989) strengthen the guarantee in both directions^[10][11]. Each process i maintains a vector VC_i of length N (one entry per process):

1. On a local event: VC_i[i] += 1
2. On sending: attach VC_i
3. On receiving VC_j: VC_i[k] = max(VC_i[k], VC_j[k]) for all k, then VC_i[i] += 1

Comparison: VC(a) < VC(b) iff every entry of a is less than or equal to the corresponding entry of b, and at least one is strictly less. If neither VC(a) <= VC(b) nor VC(b) <= VC(a), the events are concurrent.

This gives the exact characterization: a -> b if and only if VC(a) < VC(b)^[10:1].

The same event sequence timestamped with Lamport scalars and vector clocks. Lamport assigns 1 to both initial events, hiding their concurrency. Vector clocks [1,0,0] and [0,1,0] are incomparable, revealing that neither caused the other.

The cost: O(N) bytes per timestamp, where N is the number of writers. Amazon's original Dynamo paper (2007) used vector clocks per item^[12]. With thousands of mobile clients writing, vectors can grow impractically large, motivating the truncation scheme Dynamo employed.

Dotted version vectors#

Riak's classic vector-clock implementation (2009 to 2014) suffered "sibling explosion" as thousands of clients wrote with their own client IDs. Dotted version vectors (DVV), introduced by Preguica et al. (2010), solve this by keying the vector on servers, not clients^[13][14].

Each value is tagged with a single "dot" (server_id, counter) identifying which server event produced it. The surrounding context is a version vector over servers only. On a put-with-context, the DVV subsumes all siblings the client observed; only siblings concurrent with that context survive.

Riak KV adopted DVVs as its default in version 2.0, eliminating the sibling explosion that plagued earlier deployments^[15].

Use vector clocks or DVVs when: you have a multi-leader eventually-consistent store and must detect (not just resolve) concurrent writes. Use DVVs specifically when clients outnumber servers.

Hybrid Logical Clocks (HLC)#

HLC (Kulkarni et al. 2014) combines the best of both worlds: a 64-bit timestamp that tracks wall-clock time closely while preserving the Lamport causality guarantee^[16][17].

The state at node j is a pair (l_j, c_j) where l is the physical-time component and c is a logical counter:

• Local event: l_new = max(l_j, physical_time); if l_new == l_j, then c_j += 1, else c_j = 0.
• Receive from (l_m, c_m): l_new = max(l_j, l_m, physical_time); bump c_j to be strictly greater than both the local and incoming counters at the same l value.

In one common encoding, the timestamp fits in 64 bits: 48 bits for physical time (millisecond granularity), 16 bits for the logical counter^[16:1]. The result:

• Causality: if a -> b, then HLC(a) < HLC(b) (the Lamport property).
• Proximity to wall time: the physical component stays within NTP drift of real time, so HLC timestamps are human-interpretable and compatible with AS OF SYSTEM TIME queries^[18].
• Constant size: 64 bits regardless of cluster size, unlike vector clocks.

The limitation: like Lamport, HLC is one-way. HLC(a) < HLC(b) does not imply a -> b. You cannot detect concurrency with HLC alone.

CockroachDB, YugabyteDB, and MongoDB all use HLC-style clocks^{[1:2][18:1][19]}. MongoDB's SIGMOD 2019 paper describes their cluster-wide logical clock for causal consistency^[18:2].

An HLC at Node B advances its logical counter when its physical clock is behind the incoming message timestamp, preserving strict monotonicity without waiting for NTP to catch up.

TrueTime and bounded physical clocks#

Google's TrueTime is not a clock. It is an API that returns an interval [earliest, latest] with a guarantee that the true time is inside^[5:1]. Every Google datacenter hosts "time masters" (half GPS, half atomic clocks). Servers poll multiple masters, discard outliers via Marzullo's algorithm, and report uncertainty as epsilon.

In production, epsilon is typically 1 to 7 ms^[5:2]. This is orders of magnitude tighter than NTP (10 to 250 ms).

Spanner uses TrueTime for commit-wait: after assigning commit timestamp s, a transaction sleeps until TT.now().earliest > s before acknowledging^[5:3]. This guarantees that any later transaction anywhere in the world picks a strictly greater timestamp. The result is external consistency (strict serializability) without cross-datacenter coordination for reads.

The commit-wait cost is proportional to epsilon: roughly 2 * epsilon per write, or about 7 to 14 ms in practice^[5:4].

AWS now offers a similar capability. Amazon Time Sync Service (November 2023) provides under-100-microsecond accuracy over NTP and under-40-microsecond accuracy over PTP hardware clocks on EC2^[20]. ClockBound is the open-source daemon that exposes the uncertainty interval^[21]. YugabyteDB integrates with Amazon Time Sync to tighten its clock uncertainty^[22].

Real-World Example#

CockroachDB: HLC without atomic clocks.

CockroachDB is a distributed SQL database that achieves serializability on commodity hardware using HLC^[1:3]. The design illustrates how to live without TrueTime.

Each CockroachDB node maintains an HLC. Transactions get a provisional commit timestamp from the coordinator's HLC. The critical insight is the uncertainty interval: every read carries a window [ts, ts + max_offset] where max_offset defaults to 500 ms^[23]. If a read encounters a value with a timestamp inside this window, the system cannot tell whether the value was committed before or after the transaction started. CockroachDB resolves this with an uncertainty restart: it bumps the transaction's timestamp above the encountered value and retries^[1:4].

Nodes gossip pairwise clock offsets via RPC heartbeats. If a node's observed offset exceeds the configured tolerated offset threshold, it self-terminates rather than risk serving stale reads^[23:1][24].

The contrast with Spanner is instructive:

Spanner pays on writes (a short sleep). CockroachDB pays on reads (occasional restarts). Both achieve serializability. Only Spanner achieves external consistency, because only TrueTime bounds uncertainty tightly enough to make commit-wait cheap.

CockroachDB avoids commit-wait by restarting reads that hit the uncertainty window; Spanner avoids read restarts by waiting out its tight uncertainty interval on writes.

Trade-offs#

Common Pitfalls#

Exercise#

Your multi-region document-collaboration service uses LWW on edits and is silently losing user changes about once a week. Diagnose why. Propose three fixes: (1) vector clocks for conflict detection, (2) CRDTs for automatic merging (forward reference to CRDTs), (3) switching to HLC with consensus per document. Compare.

Key Takeaways#

• Wall-clock time is not safe for ordering in distributed systems. NTP skew of 10 to 250 ms between cloud VMs is routine.
• Lamport timestamps give a total order consistent with causality but cannot detect concurrency. Use them for logs, not conflict detection.
• Vector clocks detect concurrency exactly (a -> b iff VC(a) < VC(b)) but cost O(N) per timestamp. Dotted version vectors fix the explosion for client-heavy workloads.
• HLC is the modern default for distributed databases: 64 bits, causal, physical-like, and used by CockroachDB, YugabyteDB, and MongoDB.
• TrueTime bounds uncertainty to 1 to 7 ms with GPS and atomic clocks. Commit-wait converts that bound into external consistency. AWS ClockBound brings a similar API to commodity EC2.
• Any time you see ORDER BY created_at on data written by many nodes, ask: "What clock produced this timestamp, and what is its skew budget?"
• Last-write-wins is wrong by default. Use it only when losing a concurrent write is explicitly acceptable.

Further Reading#

• Time, Clocks, and the Ordering of Events in a Distributed System (Lamport 1978) - the founding paper; happens-before and logical clocks in 6 pages. Start here.
• Logical Physical Clocks and Consistent Snapshots (Kulkarni et al. 2014) - the HLC paper with pseudocode; dense but essential if you work on CockroachDB or YugabyteDB internals.
• Living Without Atomic Clocks (CockroachDB, 2022) - the canonical "HLC vs TrueTime" explainer; best single resource for understanding the uncertainty-restart trade-off.
• Spanner: Google's Globally Distributed Database (Corbett et al., OSDI 2012) - the original TrueTime + Paxos system paper; read Section 4 for commit-wait.
• Spanner, TrueTime and the CAP Theorem (Brewer, 2017) - Brewer explains why Spanner is "effectively CA" and how TrueTime enables it.
• There Is No Now (Sheehy, ACM Queue 2015) - a short, opinionated essay on why "now" is not a distributed-system concept; excellent for building intuition.
• How and why the leap second affected Cloudflare DNS (2017) - a tight post-mortem with Go code showing exactly how a non-monotonic clock causes a production outage.
• It's About Time: Microsecond-Accurate Clocks on Amazon EC2 (AWS, 2023) - AWS's TrueTime-style hardware with ClockBound; the path to tighter bounds without Google-grade infra.

Flashcards#

References#