How Hybrid Logical Clocks Power Distributed Transactions

Clock Solutions in Distributed Databases

Why a clock is required

Distributed transactions must be ordered across all nodes to preserve ACID properties. In a single‑node DB a log sequence number (LSN) or a physical timestamp is sufficient, but in a cluster each replica maintains its own clock, so a global order cannot be inferred without additional mechanisms. The order is also needed for Multi‑Version Concurrency Control (MVCC) visibility rules and for version garbage‑collection.

Clock designs for distributed systems

Centralized clock – a single service (e.g., TiDB’s Timestamp Oracle, Postgres‑XL’s GTM) issues timestamps to all participants. Guarantees a total order but creates a single point of failure and a performance bottleneck.

Pure logical clocks – each node keeps a monotonically increasing counter (Lamport clock) and propagates it with every message. Provides a "happen‑before" partial order without any physical time.

Hybrid Logical Clock (HLC) – combines a physical component (synchronised via NTP or atomic clocks) with a logical counter. The physical part gives a coarse global ordering; the logical part resolves ties and absorbs clock skew.

Typical deployments:

TiDB – central timestamp service.

Postgres‑XL – GTM central clock.

Oracle – logical SCN timestamps.

CockroachDB – HLC derived from Google Spanner.

Google Spanner – TrueTime, an atomic‑clock based service.

Logical clock mechanics (Lamport)

Each node maintains a counter c. On a local event c = c + 1. When a message with timestamp t is received, the node sets c = max(c, t) + 1. This guarantees that if event A causally precedes event B, then c_A < c_B. The ordering is partial: unrelated transactions may have incomparable timestamps.

Hybrid Logical Clock (HLC) algorithm

An HLC timestamp is a pair (physical, logical). When a new transaction is started on node i:

now = physical_time()
if now > last_physical:
    physical = now
    logical = 0
else:
    logical = logical + 1

When a message with timestamp (p, l) is received, the node updates:

now = physical_time()
physical = max(now, p)
if physical == p:
    logical = max(logical, l) + 1
else:
    logical = max(logical, 0)

This preserves causality while allowing each node to generate timestamps locally.

Comparison of clock families

Centralized clocks give a total order but suffer from single‑point‑of‑failure and scalability limits.

Pure logical clocks avoid a central service but can only order causally related events; unrelated transactions remain unordered.

HLC removes the central node, provides total order for transactions that share data (causal ordering), and allows independent progress for disjoint transactions.

TrueTime (Spanner) offers globally bounded timestamps using atomic clocks, eliminating logical ambiguity at the cost of specialized hardware and added commit latency.

Distributed Transaction Management

Two‑Phase Commit (2PC)

2PC guarantees atomicity across nodes. Phase 1 (prepare) asks every participant to lock required resources and confirm that it can commit. If all participants reply positively, Phase 2 (commit) is issued; otherwise the transaction is aborted. 2PC protects consistency but can block if a participant crashes after the prepare phase.

Other transaction coordination techniques

Optimistic Concurrency Control (OCC) / Multi‑Version OCC (MVOCC) – conflicts are detected at commit time. FoundationDB uses MVOCC; it allows high throughput when contention is low because no locks are held during execution.

Deterministic transactions – the complete transaction logic is known beforehand, enabling pre‑ordering without locks. FaunaDB is a representative system.

Non‑deterministic (interactive) transactions – typical e‑commerce workloads where each statement is issued after the previous one returns. These cannot be pre‑ordered and rely on traditional locking or OCC.

Integrating HLC with 2PC

Attach an HLC timestamp to the prepare and commit messages. The prepare phase carries the timestamp of the transaction’s logical start; the commit phase carries the timestamp after all participants have agreed. Because HLC preserves causality, the commit order of overlapping transactions is well‑defined without a central clock.

HLC representation and throughput characteristics

An HLC is stored in 64 bytes:

5 bytes reserved for future compatibility.

43 bytes for the physical component (millisecond‑precision Unix epoch). At this size the physical field can represent ~279 years of time.

16 bytes for the logical counter, allowing up to 2^16 = 65 536 increments per millisecond.

With millisecond precision a single node can theoretically issue >30 million transactions per second (30 M TPS) because each millisecond can host 65 k distinct timestamps. In practice network latency and CPU limits reduce the achievable rate.

Impact of clock skew on HLC throughput

If two nodes differ by Δ ms, the logical part must absorb the gap. A 5 ms skew can reduce the effective TPS by a factor of 100 because the logical counter must span the extra milliseconds before it overflows. Mitigation strategies:

Enforce a maximum allowable skew (e.g., 100 ms). Nodes exceeding the bound are excluded from the cluster.

Allow the logical counter to overflow into the physical component, effectively extending the logical range and tolerating larger skews.

Summary of trade‑offs

Centralized clock : total order, simple to reason about, but single‑point‑of‑failure and scalability bottleneck.

Pure logical clock : no central service, scales horizontally, but only provides causal ordering.

Hybrid Logical Clock : combines the best of both – causal ordering with low‑latency local timestamp generation, suitable for high‑throughput distributed databases.

TrueTime : strongest consistency guarantees (global linearizability) at the cost of specialized hardware and added commit latency.