Understanding Timestamps in Distributed Transactions: TSO, TrueTime, Lamport Clock, and HLC

Why Timestamps Are Needed

Since the invention of MVCC, most modern databases abandoned two‑phase locking for concurrency control, and distributed databases typically adopt MVCC, which naturally introduces version numbers or timestamps to determine visibility of data.

Linearizability

Linearizable (or external) consistency requires that the order of operations observed by external clients matches physical time, providing a strong guarantee that every read sees the latest committed write.

TrueTime

Google Spanner uses TrueTime, a combination of atomic clocks and GPS, to provide decentralized timestamps with a bounded uncertainty ε (≈7 ms). Transactions wait for 2ε before committing to ensure a globally consistent order.

Lamport Clock and Hybrid Logical Clock (HLC)

Lamport clocks assign monotonically increasing integers to capture causal order. HLC augments this by embedding a physical time component in the high bits and a logical counter in the low bits, allowing both causality and approximate physical ordering.

T1: w(C1)
T1: commit
T2: r(C2)   (not visible! assuming T2.snapshot_ts < T1.commit_ts)

Limited‑Error HLC in CockroachDB

CockroachDB limits clock skew to 250 ms using semi‑synchronized clocks. When a read’s snapshot timestamp falls within the uncertainty window [snapshot_ts, snapshot_ts + max_clock_shift] , the transaction is restarted with a new timestamp.

Combining TSO and HLC (TiDB Async Commit)

TiDB’s async commit reduces latency by making the primary‑key commit asynchronous while still obtaining a commit timestamp from the TSO. The design introduces a prewrite_ts to preserve ordering of commit timestamps across nodes.

T1: begin   T2: begin   T3: begin   (concurrently)
T1: w(C1)
T1: commit   (commit_ts = 105)
T2: w(C2)
T2: commit   (commit_ts = 103)
T3: r(C1)   (not found)
T3: r(C2)   (found)
T3: commit

Async Commit Done Right

By fetching a prewrite_ts from the TSO and propagating it to TiKV during the prewrite phase, TiKV can raise its local max timestamp, ensuring that subsequent commit timestamps respect the correct order and thus satisfy linearizability.

Summary

Only TSO and TrueTime can guarantee full linearizability.

Logical‑clock schemes (Lamport, HLC) provide only session/causal consistency.

CockroachDB’s HLC offers row‑level linearizability but not multi‑row transactions.

TiDB async commit preserves external consistency when prewrite timestamps are used; without them, linearizability may be violated.

References

https://en.wikipedia.org/wiki/Lamport_timestamp

https://www.slideshare.net/josemariafuster1/spanner-osdi2012-39872703

https://jepsen.io/analyses/cockroachdb-beta-20160829

https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

https://sergeiturukin.com/2017/06/29/eventual-consistency.html

https://github.com/tikv/sig-transaction/blob/master/design/async-commit/initial-design.md

https://github.com/tikv/tikv/issues/8589