· 9 min read

Bounded Clock Drift and Linearizable Lease Reads in Multi-AZ Raft

Distributed Storage

A linearizable key-value cluster must never return stale data after a leader partition heals. Standard Raft solves this via ReadIndex: the leader records its commit index and broadcasts a heartbeat round to confirm it still holds a quorum before serving reads. Across availability zones with 1.8 ms RTT, that round-trip doubles read latency.

The Cost of Quorum ReadIndex

On read-heavy metadata workloads (95% reads, 5% writes), forcing a quorum heartbeat on every lookup saturates RPC codecs long before CPU or disk limits are reached. Leader leases eliminate that RPC round-trip by proving via time bounds that no follower can start an election while the lease remains valid.

Deriving Safe Lease Bounds

Suppose the configured election timeout is E and the maximum bound on monotonic clock drift ratio across hosts is ε (typically well below 500 ppm with Chrony/PTP). If a majority of nodes acknowledged a heartbeat sent at local monotonic timestamp t_send, no new term can elect a leader before:

Lease Validity Window t_now < t_send + (E / (1 + ε)) - safety_margin

Crucially, followers must also wait until their own election timer expires relative to the last received AppendEntries before voting for a candidate, preserving mutual exclusion even if the old leader hits a GC or hypervisor pause.

Monotonic Clocks vs Wall Clocks

Never evaluate lease expiration with CLOCK_REALTIME. NTP step adjustments or leap second smearing can shift wall time backward and revive an expired lease. Always read CLOCK_MONOTONIC_RAW (or CLOCK_MONOTONIC on modern kernels where slew rates are bounded).

go — lease.go
type LeaseTracker struct {
    mu            sync.RWMutex
    electionTick  time.Duration
    maxDriftRatio float64
    validUntil    time.Time // monotonic component preserved by time.Time
}

func (l *LeaseTracker) ExtendFromQuorum(sentAt time.Time) {
    // Divide by (1 + maxDrift) and subtract 15ms safety margin
    usable := time.Duration(float64(l.electionTick) / (1.0 + l.maxDriftRatio))
    deadline := sentAt.Add(usable - 15*time.Millisecond)

    l.mu.Lock()
    if deadline.After(l.validUntil) {
        l.validUntil = deadline
    }
    l.mu.Unlock()
}

func (l *LeaseTracker) CanServeLocalRead() bool {
    l.mu.RLock()
    ok := time.Now().Before(l.validUntil)
    l.mu.RUnlock()
    return ok
}

Handling Leader Pause & Step-Down

If a VM experiences live migration freeze longer than E, the lease expires naturally before resumption because Go's time.Now() monotonic counter advances while frozen—Wait: verify your hypervisor clock source! Under KVM kvm-clock, monotonic time advances across pauses, ensuring the frozen leader immediately falls back to ReadIndex upon unfreezing.