Understanding lease-based leader election#

2024-03-15

Both Paxos and Raft support "leader leases" — an optimization where the leader can serve reads locally (without a round-trip to a majority) for a bounded period. Getting this right is surprisingly tricky.

The basic idea#

A leader holds a lease with a time bound T. During the lease:

• The leader can respond to read requests without asking followers.
• No other node can become leader.

If the leader crashes, the lease expires after T; a new leader can be elected after that.

The clock-skew problem#

Leases require bounded clock skew between nodes. Otherwise:

• Node A thinks its lease expires at T=1000.
• Node B thinks A's lease already expired at T=950 (B's clock is faster).
• B elects itself, serves writes. Meanwhile, A is still doing reads.
• Split brain.

Practical mitigations#

• Use monotonic clocks (CLOCK_MONOTONIC), not wall clock.
• Guard band: renew leases at T - guard_band, treat lease as expired at T - guard_band from consumer side. Typical: 500 ms guard band with 10 s lease.
• NTP hygiene: keep all nodes on the same time source with tight maxpoll.
• Hardware TSC-based clocks in datacenters (Spanner does this with TrueTime).

etcd's approach#

etcd doesn't use leader leases for reads by default; it does "linearizable reads" via ReadIndex (leader proposes an empty read barrier, waits for commit, then serves reads). This is safer but adds a round-trip.

etcd v3.4+ has an opt-in LeaseRead mode that uses leader leases with a conservative 1-second guard.

CockroachDB's approach#

CockroachDB uses per-range leases with a hybrid logical clock (HLC). Lease renewal is piggybacked on Raft heartbeats. The HLC compensates for small skew, but the system is still designed to fail closed under large skew.

Reference#

• Chandra, Griesemer, Redstone, Paxos Made Live — the "master leases" section.
• The etcd docs on linearizable-read and serializable-read.
• Corbett et al., Spanner: Google's Globally-Distributed Database (OSDI 2012).