Timestamp Ordering Protocol

Every computer has a clock. It ticks away constantly, tracking the passage of real-world seconds, milliseconds, and nanoseconds. When a database needs unique, monotonically increasing timestamps, the system clock presents an obvious solution: just ask the operating system what time it is.

This approach is intuitive—the clock is already there, already incrementing, already providing a universally understood ordering. When transaction T₁ starts at 10:00:00.000 and T₂ starts at 10:00:00.001, the timestamps directly reflect real-world causality.

But as we'll discover, using system clocks for database timestamps introduces subtle challenges that can undermine correctness. Understanding these challenges—and how to address them—is essential for building reliable timestamp-based systems.

Before using system clocks for timestamps, we need to understand how computers track time. This involves multiple layers of hardware and software working together.

Hardware Timekeeping:

At the lowest level, computers use hardware oscillators to generate periodic signals:

1. Real-Time Clock (RTC): A battery-backed chip that maintains time even when powered off. Typically uses a 32.768 kHz crystal oscillator. Drifts several seconds per day.

2. High-Precision Event Timer (HPET): Modern motherboard timer providing nanosecond-resolution timing for the operating system.

3. Time Stamp Counter (TSC): A register in modern CPUs that increments with each clock cycle. Provides the finest granularity (sub-nanosecond) but requires calibration.

Software Time Management:

The operating system uses hardware timers to maintain:

• System Time: Wall-clock time since a reference epoch (e.g., January 1, 1970 for Unix)
• Monotonic Time: A counter that never goes backward, regardless of clock adjustments
• High-Resolution Timers: APIs for nanosecond-precision time queries

For timestamps to provide unique, ordered identifiers, the clock's resolution must be fine enough that no two transactions receive the same timestamp. This imposes strict requirements on clock precision.

Key Terminology:

• Resolution: The smallest time unit the clock can distinguish (e.g., 1 microsecond)
• Precision: The consistency of measurements—how much variation occurs when measuring the same interval
• Accuracy: How close the clock is to true physical time (matters for wall clocks)

The Uniqueness Challenge:

Consider a database handling 100,000 transactions per second. With millisecond-resolution timestamps:

• Each millisecond: 100 transactions on average
• Problem: Multiple transactions get the same timestamp

With microsecond resolution:

• Each microsecond: 0.1 transactions on average
• Most microseconds have 0 or 1 transaction—much better!

Throughput vs Resolution Requirements:

Let's calculate the minimum required resolution for given transaction rates:

Modern hardware easily provides microsecond resolution. Nanosecond resolution is available but less consistent across platforms. For transactions exceeding hardware clock resolution, we need tie-breaking mechanisms.

When two transactions request timestamps within the same clock tick—or when clock resolution is insufficient—we face timestamp collisions. Since timestamps must be unique by definition, we need systematic strategies to resolve these conflicts.

Strategy 1: Wait for Clock Advance

The simplest approach: if the current clock value equals the last assigned timestamp, wait until it changes.

last_timestamp = 0

function get_timestamp():
    current = system_clock()
    while current <= last_timestamp:
        current = system_clock()  // busy-wait or sleep
    last_timestamp = current
    return current

Pros: Guarantees uniqueness with pure clock values Cons: Limits throughput to clock resolution; can cause contention

Strategy 2: Sub-Clock Counter Extension

Append a secondary counter that increments within each clock tick:

last_clock = 0
sub_counter = 0

function get_timestamp():
    current_clock = system_clock()
    if current_clock == last_clock:
        sub_counter = sub_counter + 1
    else:
        last_clock = current_clock
        sub_counter = 0
    return (current_clock, sub_counter)  // composite timestamp

Pros: Higher throughput; no waiting Cons: Timestamps become composite values; need handling if counter overflows

Strategy 3: Hybrid Logical Clocks (HLC)

A sophisticated approach combining physical time with logical components:

1. Physical Component (pt): Maximum of local clock and highest pt seen from other nodes
2. Logical Component (l): Counter reset when pt advances; incremented within same pt

HLC timestamps look like (physical_time, logical_counter) and provide:

• Comparable ordering with real time (approximately)
• Guaranteed uniqueness
• Causality tracking: if A happens-before B, HLC(A) < HLC(B)

This approach is used by CockroachDB, MongoDB, and other distributed databases.

Computer clocks are imperfect—they drift relative to true physical time. A clock that runs 1 part per million (ppm) fast will gain about 86 milliseconds per day. This drift creates challenges for timestamp ordering.

Sources of Clock Drift:

1. Crystal Oscillator Variation: Temperature changes, aging, manufacturing tolerances cause frequency shifts
2. Frequency Scaling: Modern CPUs adjust clock speeds for power management, affecting timing
3. Virtualization: Virtual machines may have less accurate timekeeping than bare metal
4. Initial Synchronization Delay: Clocks may be significantly off until NTP corrects them after boot

Network Time Protocol (NTP):

NTP corrects clock drift by synchronizing with reference time servers. Key characteristics:

• Typical accuracy: 1-50 milliseconds over the internet
• LAN accuracy: sub-millisecond possible with local NTP servers
• Correction methods: gradual frequency adjustment (slewing) or instant jump (stepping)

The Stepping Problem:

When NTP determines the clock is significantly off (typically > 128ms), it may step the clock—instantly changing the time. If the clock moves backward:

• Timestamps assigned before the step may be larger than timestamps after
• Violates monotonicity—a fundamental timestamp property
• Can cause serious consistency issues in timestamp ordering

Most production systems configure NTP to only slew (never step) after initial synchronization, accepting temporary drift in exchange for monotonicity.

When multiple database nodes each assign timestamps using their local clocks, the challenges multiply. Different nodes have different clocks, and keeping them perfectly synchronized is physically impossible.

The Fundamental Problem:

Imagine two database nodes, A and B:

• Node A's clock runs 5ms fast relative to true time
• Node B's clock runs 3ms slow relative to true time
• Total skew: 8ms between A and B

User 1 sends transaction T₁ to Node A at true time t=100ms:

• Node A sees clock time 105ms, assigns TS(T₁) = 105

User 2 sends transaction T₂ to Node B at true time t=101ms (1ms later):

• Node B sees clock time 98ms, assigns TS(T₂) = 98

Result: T₂ (actually later) has a smaller timestamp than T₁.

If T₁ and T₂ both access the same data, the timestamp ordering is inverted from real causality.

Why This Matters:

Consider a scenario where:

1. User reads their bank balance ($1000) from Node A at TS=105
2. User initiates withdrawal ($500) on Node B at TS=98

The read appears to have happened "after" the withdrawal in timestamp order, even though it happened before. If the system uses timestamps strictly, the withdrawal might see stale data or the read might miss the withdrawal—both are incorrect.

Approaches to Distributed Timestamps:

1. Centralized Timestamp Server: A single node assigns all timestamps

   • Simple but creates bottleneck and single point of failure

2. Clock Synchronization Bounds: Characterize maximum clock skew and build protocols around it

   • Google Spanner's TrueTime: knows uncertainty bounds, waits them out

3. Logical Timestamps: Use vector clocks or Lamport clocks instead of physical time

   • Guaranteed correct ordering based on causality, not time

4. Hybrid Logical Clocks: Combine physical and logical components

   • Best of both worlds: approximate real-time with correctness guarantees

Let's examine concrete implementation patterns used by real database systems to leverage system clocks while mitigating their limitations.

Key Implementation Details:

1. Composite Timestamp Structure: High bits for clock time, low bits for counter
2. Lock Protection: Ensures atomicity across concurrent threads
3. Counter Overflow Handling: Waits for clock advance rather than wrapping
4. Backward Clock Handling: Increments from last timestamp instead of using "past" value
5. Thread Safety: Critical for multi-threaded database engines

This pattern provides:

• Uniqueness: Counter ensures no collisions within same microsecond
• Monotonicity: Never returns a smaller value than previously
• Approximate real-time: High bits correlate with wall clock
• Bounded waiting: Only waits when counter overflows (rare)

System clock timestamps are appropriate in specific scenarios. Understanding these helps make informed architectural decisions.

We've thoroughly examined system clock-based timestamp generation. Let's consolidate the essential insights:

What's Next:

System clocks are one approach to timestamp generation. An alternative avoids clock complexity entirely: logical counters provide guaranteed uniqueness and monotonicity without any dependency on physical time. We'll explore this elegant alternative next.