Clock Skew & Time Ordering in Distributed Systems

Every deduplication mechanism eventually asks a question about time: has this key expired, is this lease still held, did this event happen before that one? This page is part of Distributed Coordination & Locking Strategies, and it covers what happens when the clocks answering those questions disagree — which they always do, by an amount you either measured or merely hoped for.

Clock skew is not an exotic failure. It is the ambient condition of every fleet larger than one machine. The engineering task is not to eliminate it but to make every time-dependent decision either tolerant of it or independent of it.

---

Problem framing

A wall clock is a shared fiction maintained by a synchronisation daemon against a reference server, and it can move backwards. NTP in step mode will jump a clock to correct a large offset. A virtual machine resumed from suspend sees time discontinuously advance. A leap second can be smeared over 24 hours by one cloud provider and stepped by another, so two hosts in the same fleet disagree for a day.

Deduplication is unusually sensitive to this because it makes irreversible decisions from time-derived state. If a TTL is evaluated against a clock that has jumped forward, a key expires early and a duplicate charge executes. If a lease is evaluated against a clock that has jumped backwards, a lock is held long past its intended lifetime and a stuck worker blocks a queue. Neither failure announces itself; both surface later as a reconciliation discrepancy.

The unsafe window is exactly the skew. Everything on this page is about shrinking it, bounding it, or removing the dependency on it.

---

Guarantee model

Time-based coordination gives you a best-effort, skew-bounded guarantee: correct provided the maximum offset between any two participating clocks stays below the margin you built in. That is a real guarantee, but it is conditional, and the condition is not enforced by anything in the system — it is an assumption about your infrastructure that fails silently.

Three ordering models are available, and they trade cost against strength:

• Wall-clock ordering — compare now() values from different hosts. Provides no ordering guarantee at all under skew. Acceptable only for human-facing audit fields and coarse expiry with a generous margin.
• Logical ordering (Lamport / vector clocks) — provides a correct causal order with no clock dependency, but the timestamps are meaningless to humans and cannot drive a TTL.
• Hybrid logical clocks — a physical component plus a logical counter. Preserves causality unconditionally and stays within a bounded distance of real time, so a single value can both order events and approximate expiry.

Under partition, all three degrade the same way: two sides make independent decisions and reconcile later. Under skew, only the last two survive. This is why the strongest deduplication designs use an atomic conditional write to decide and a clock only to expire — the decision is causal, the expiry is approximate, and the approximation is padded.

---

Measuring your actual skew budget

Guessing is the failure mode. Every fleet should export its clock offset as a first-class metric, because the number varies by an order of magnitude between environments and changes when infrastructure changes.

# chrony: offset from the selected reference, in seconds (System time line)
chronyc tracking | awk '/System time/ {print $4}'

# Export it for Prometheus via node_exporter's textfile collector
cat > /var/lib/node_exporter/textfile/clock.prom <<EOF
# HELP node_clock_offset_seconds Offset of the system clock from its NTP reference.
# TYPE node_clock_offset_seconds gauge
node_clock_offset_seconds $(chronyc tracking | awk '/System time/ {print $4}')
EOF

# The number that matters: the widest disagreement between ANY two hosts, not the average.
max(node_clock_offset_seconds) - min(node_clock_offset_seconds)

Typical measured bounds, which you should confirm rather than adopt:

Run chronyd in slew mode (makestep disabled, or restricted to boot) on every host that participates in deduplication. Slewing corrects an offset by speeding or slowing the clock rather than jumping it, which keeps time monotonic at the cost of taking longer to converge. A stepped clock is the single most common cause of the failure in the diagram above.

---

Removing the dependency: monotonic clocks and fencing tokens

Two techniques cover most of the risk. The first removes wall clocks from duration measurement. The second removes correctness from time entirely.

Monotonic clocks for durations

A wall clock answers “what time is it”; a monotonic clock answers “how long since”. Only the second question is meaningful for a timeout, and only the monotonic clock is guaranteed never to go backwards.

// WRONG — a clock step between the two calls silently changes the measured duration.
start := time.Now()
doWork()
if time.Now().Sub(start) > lease { /* may be true or false for the wrong reason */ }

// RIGHT — Go's time.Since reads the monotonic component embedded in time.Now(),
// which is immune to NTP steps. Never round-trip a Time through Unix seconds
// (or through JSON) if you intend to measure a duration with it: that strips
// the monotonic reading and leaves only the wall clock.
start := time.Now()
doWork()
if time.Since(start) > lease { renewOrAbort() }

import time
# time.time() is the wall clock and can jump. time.monotonic() cannot.
start = time.monotonic()
do_work()
if time.monotonic() - start > lease_seconds:
    renew_or_abort()

Fencing tokens for correctness

Monotonic clocks fix measurement, not authority. A worker can hold a lease, get descheduled for 90 seconds by a garbage-collection pause or a hypervisor freeze, wake up believing it still holds the lock, and write. Its lease expired while it was frozen; another worker already took over. No amount of clock hygiene prevents this, because the frozen worker’s clocks were correct — it simply did not run.

A fencing token makes the late write harmless. The lock service hands out a strictly increasing integer with every grant, and the protected resource refuses any write carrying a token lower than the highest it has already accepted.

-- The resource enforces the fence. No timestamps appear anywhere in this check.
UPDATE account_balances
   SET balance = balance - $1,
       fence_token = $2
 WHERE account_id = $3
   AND fence_token < $2;     -- a stale holder's write matches zero rows

The fence is what makes a lease safe rather than merely usually correct, and it is the piece most Redlock-style deployments omit. Redlock versus single-instance Redis locks works through why the replication protocol alone does not close this gap.

---

Implementation variants

Variant A — padded TTL with slewed clocks

The cheapest option: keep wall-clock TTLs, but pad every one by the measured maximum skew plus a safety factor, and forbid clock steps.

MEASURED_MAX_SKEW_MS = 50      # from your own fleet metric, 99.9th percentile
SAFETY_FACTOR = 3

def safe_ttl_ms(intended_ms: int) -> int:
    return intended_ms + MEASURED_MAX_SKEW_MS * SAFETY_FACTOR

Correct while the assumption holds; wrong, silently, the day someone adds a region with an independent NTP hierarchy. Pair it with an alert on the fleet-wide offset spread so the assumption is monitored rather than assumed.

Variant B — server-side expiry only

Never compute expiry on the application host. Let the single deduplication store own the clock, so there is only one clock and skew becomes definitionally zero.

# Redis evaluates the TTL against its own clock; the app never compares timestamps.
SET idem:acct7:charge:01HXYZ '{"state":"pending"}' NX PX 86400000

-- PostgreSQL: now() is the server's clock, identical for every connected client.
INSERT INTO idempotency_keys (scoped_key, state, expires_at)
VALUES ($1, 'pending', now() + interval '24 hours')
ON CONFLICT (scoped_key) DO NOTHING;

This is the strongest option available without new machinery, and it is why Redis-based deduplication is more skew-resistant than it first appears. Its limit is that a replicated store has more than one clock again, which is exactly where fencing tokens re-enter.

Variant C — hybrid logical clocks

When events must be ordered across stores — a deduplication log replicated between regions, say — an HLC gives a single 64-bit value that respects causality and stays close to real time.

type HLC struct {
    mu       sync.Mutex
    physical int64  // milliseconds
    logical  uint16 // tie-break counter within one millisecond
}

// Now stamps a locally generated event.
func (c *HLC) Now() (int64, uint16) {
    c.mu.Lock(); defer c.mu.Unlock()
    wall := time.Now().UnixMilli()
    if wall > c.physical { c.physical, c.logical = wall, 0 } else { c.logical++ }
    return c.physical, c.logical
}

// Update merges a timestamp received from a peer, preserving happens-before.
func (c *HLC) Update(pPhys int64, pLog uint16) (int64, uint16) {
    c.mu.Lock(); defer c.mu.Unlock()
    wall := time.Now().UnixMilli()
    switch {
    case wall > c.physical && wall > pPhys:
        c.physical, c.logical = wall, 0
    case pPhys > c.physical:
        c.physical, c.logical = pPhys, pLog+1
    case c.physical == pPhys:
        if pLog > c.logical { c.logical = pLog }
        c.logical++
    default:
        c.logical++
    }
    return c.physical, c.logical
}

A steadily growing logical counter is a direct signal that physical clocks are lagging behind message propagation — which makes it a useful skew alarm in its own right.

---

Edge cases and failure scenarios

---

Operational concerns

TTL management. Every TTL that is evaluated off-store needs three numbers written down: the intended lifetime, the measured skew bound, and the padding factor. A 24-hour idempotency key with a 50 ms skew bound needs no meaningful padding — the ratio is 1 in 1.7 million. A 30-second lock lease with the same bound needs 0.5% padding at 3x, which is trivial. The danger zone is short leases in high-skew environments: a 2-second lease with a 300 ms bound is 45% padding, at which point the lease is no longer doing what you think.

Index strategy. Fencing tokens are a single bigint column on the protected row, updated in the same statement as the guarded write, so they add no index at all. A dedicated sequence per resource (CREATE SEQUENCE fence_<resource>) is cheaper than a global one and avoids cross-resource contention on the sequence cache.

Storage budgeting. Hybrid logical clocks add 8 bytes of physical time plus 2 bytes of counter per event. On a deduplication log ingesting 5,000 events per second with 7-day retention, that is roughly 30 GB of timestamps alone — worth knowing before enabling it globally rather than on the cross-region path that actually needs it.

Alert thresholds. Page when the fleet-wide offset spread exceeds 100 ms, because that is the point at which short leases stop being safe. Warn on any system_clock_step_total increment outside the first minute after boot. Alert on any non-zero lock_fence_rejected_total rate above baseline, since a rising fence-rejection rate means workers are being frozen or partitioned more often — a capacity or noisy-neighbour signal, not merely a locking one. And treat a monotonically climbing HLC logical counter as a skew alarm, because it means physical time is advancing more slowly than causality.

Testing. Skew bugs never appear in a single-host test. Validate them by running the deduplication suite with one container’s clock deliberately offset — libfaketime or a privileged container running date -s — and asserting that no duplicate side effect occurs at offsets of ±1 s, ±60 s, and ±1 h. This belongs in CI, not in a runbook.

---

FAQ

How much clock skew should I budget for?

Measure it rather than assume it. A healthy chrony fleet inside one cloud region typically holds within 1 to 5 milliseconds of reference, cross-region within 50 milliseconds, and a VM that has just been live-migrated or resumed from suspend can be seconds out. Budget the 99.9th percentile of your own measured offset spread, not the median, and add a 3x safety factor to any TTL that depends on it.

Can I use timestamps to decide which duplicate request came first?

No. Two requests stamped by different hosts carry incomparable times — the later-stamped one may genuinely have arrived first. Use an atomic conditional write at a single store to decide the winner, exactly as preventing race conditions in microservices describes, and use timestamps only for expiry and for human-readable audit fields.

What is a fencing token and why does a lock need one?

A fencing token is a monotonically increasing integer handed out with each lock grant. The protected resource records the highest token it has seen and rejects any write carrying a lower one. This makes a lock safe even when a paused holder wakes after its lease expired: its token is now stale, so the write is refused rather than corrupting state. Without a fence, a lease is a performance optimisation wearing a correctness costume.

Does a hybrid logical clock remove the need for NTP?

No. An HLC guarantees causal ordering regardless of skew, but its physical component still tracks wall time so timestamps stay human-meaningful and TTLs remain approximately right. Poor NTP discipline makes the logical counter grow without bound, which is a symptom worth alerting on rather than a condition the HLC repairs.

Should idempotency key TTLs use the application clock or the database clock?

The database clock, always, when there is a single authoritative store. Writing expires_at = now() + interval '24 hours' in SQL, or letting Redis own the PX argument, collapses every participating clock into one and removes the whole class of failure. The application clock only becomes unavoidable when expiry must be computed before the store is reachable, which is rare and worth designing away. Choosing TTL values for idempotency keys covers the sizing side of the same decision.

---

Related

• Distributed Coordination & Locking Strategies — the parent section covering locks, consensus and race-condition prevention across services.
• Using Fencing Tokens to Survive Lock Expiry — the full implementation: token issuance, storage-side enforcement, and migration on a live table.
• Hybrid Logical Clocks for Deduplication Ordering — building and propagating an HLC across a replicated deduplication log.
• Measuring and Bounding NTP Clock Skew in Production — the metrics, chrony configuration and alerts that turn the skew budget into a monitored number.
• Lock Timeout & Lease Management — sibling area on lease lifetimes, heartbeat renewal and stale-lock recovery.
• Injecting Clock Skew to Validate TTL Safety — the chaos experiment that proves these defences work before production does it for you.