Leases

Deep dive

How it works

In: Acquire(client, term d) and Renew requests · Out: a grant with a fencing token, or a refusal while another holder's lease is live · State: grantor: holder, expiry (its own monotonic clock) and the last token; holder: its local expiry and token · Cost: O(1) per grant or renew, one round trip

Holder H, grantor G, term d, max drift rate ρ, small safety margin ε.

1. H records t0 = monotonic_now() before sending Acquire.
2. G, if the lease is free or expired (by G's own monotonic clock), increments a fencing token, grants for d, and records expires = now_G + d·(1+ρ) + ε.
3. H, on the grant, considers itself owner until t0 + d·(1−ρ) − ε. Network delay only shortens H's view, never lengthens it.
4. H renews well before expiry (e.g. at d/3 remaining); renewals keep the same token.
5. Every write H makes to shared storage carries the token; storage remembers the highest token seen and rejects lower ones.
6. If H can't renew, it must stop acting at its expiry; G will reassign after its (later) expiry.

H:  t0 ──Acquire──►                       H believes:  [t0 ........ t0+d(1-ρ)-ε]
G:         grant at tG (token 34) ──►     G believes:  [tG .............. tG+d(1+ρ)+ε]
                                          G's interval always ends after H's
storage: write(token 34) ok; later write(token 33) from a paused old holder → rejected

Code

use std::time::{Duration, Instant};

pub struct Grant { pub token: u64, pub term: Duration }

pub struct LeaseServer {
    holder: Option<(u64, Instant)>, // (client, expiry on the server's monotonic clock)
    token: u64,
    drift: f64,                     // e.g. 1e-4 = 100 ppm, generous for quartz
    margin: Duration,
}

impl LeaseServer {
    pub fn new(drift: f64, margin: Duration) -> Self { LeaseServer { holder: None, token: 0, drift, margin } }

    /// Acquire or renew. Renewal by the current holder keeps its token.
    pub fn acquire(&mut self, client: u64, term: Duration, now: Instant) -> Option<Grant> {
        match self.holder {
            Some((h, exp)) if h != client && now < exp => return None, // held by someone else
            Some((h, exp)) if h == client && now < exp => {}            // renewal
            _ => self.token += 1,                                       // new owner: new epoch
        }
        let exp = now + term.mul_f64(1.0 + self.drift) + self.margin;  // server waits longer
        self.holder = Some((client, exp));
        Some(Grant { token: self.token, term })
    }

    pub fn release(&mut self, client: u64) {
        if matches!(self.holder, Some((h, _)) if h == client) { self.holder = None; }
    }
}

pub struct LeaseHolder { pub token: u64, valid_until: Option<Instant>, term: Duration, drift: f64, margin: Duration }

impl LeaseHolder {
    pub fn new(drift: f64, margin: Duration) -> Self {
        LeaseHolder { token: 0, valid_until: None, term: Duration::ZERO, drift, margin }
    }
    /// `sent_at` must be captured BEFORE the request went out.
    pub fn on_grant(&mut self, sent_at: Instant, g: Grant) {
        self.token = g.token;
        self.term = g.term;
        // Holder assumes a shorter lease; saturates to sent_at if margin > term.
        let held = g.term.mul_f64(1.0 - self.drift).saturating_sub(self.margin);
        self.valid_until = Some(sent_at + held);
    }
    pub fn is_valid(&self, now: Instant) -> bool { self.valid_until.map_or(false, |v| now < v) }
    pub fn should_renew(&self, now: Instant) -> bool {
        self.valid_until.map_or(true, |v| v.saturating_duration_since(now) < self.term / 3)
    }
}

/// The resource enforces ordering: a paused ex-holder's late write is rejected.
#[derive(Default)]
pub struct FencedStore { max_token: u64, pub data: Vec<u8> }

impl FencedStore {
    pub fn write(&mut self, token: u64, data: &[u8]) -> Result<(), u64> {
        if token < self.max_token { return Err(self.max_token); }
        self.max_token = token;
        self.data = data.to_vec();
        Ok(())
    }
}

is_valid must be checked right before each externally visible action, and the action must still carry the token, because the process can pause between the check and the I/O.

Complexity and constants

• Acquire: 1 RTT (plus a consensus write if the grantor is replicated, as it should be).
• Renew traffic: one RPC per holder every ~d/3; 10,000 sessions with 12 s terms ≈ 2,500 renewals/s.
• Unavailability on holder failure: up to d·(1+ρ) + ε + detection; Kubernetes defaults ⇒ order of 15-20 s.
• Drift margin: 100 ppm on a 10 s lease = 1 ms; the network RTT and GC pauses dominate, not drift.

Efficiency

• Cost: one round trip to acquire (plus a consensus write if the grantor is replicated), then one small RPC per holder every d/3: 10,000 sessions with 12 s terms are about 2,500 renewals/s. After a holder fails, the resource is unavailable for up to d·(1+ρ) + ε plus detection, order of 15-20 s with Kubernetes defaults. Drift margin is tiny (100 ppm on 10 s = 1 ms). Bound: network latency, pauses and renewal load on the grantor.
• Levers:
  • one session or lease shared by many locks — renewals per client stay at one stream, not one per lock (Chubby sessions, etcd leases) — clients holding many resources
  • longer term — fewer renewals but slower failover (arithmetic above) — stable holders
  • renew at d/3 on a dedicated thread — survives one or two lost renewals without losing the lease (above) — every deployment
  • leader lease for reads — local reads at the leader with no quorum round per read (Spanner, CockroachDB) — read-heavy replicated stores
  • batch renewals into one keepalive stream — fewer RPCs at the grantor (order of) — thousands of sessions
• Naive → standard → state of the art:
  • lock with no expiry, released by hand · blocks forever when the holder crashes
  • lease with a term, fencing token on writes · 1 RTT to acquire, 1 renewal per d/3
  • shared session leases and leader leases for reads · renewals per client, not per lock; reads without a quorum round

Implementation notes

• Use CLOCK_MONOTONIC/Instant for every duration; never compare wall clocks between machines.
• CLOCK_MONOTONIC on Linux stops during system suspend (CLOCK_BOOTTIME doesn't); a suspended holder would think less time passed. Use BOOTTIME where suspend is possible.
• The grantor itself must be fault-tolerant: store lease state in a Raft/Paxos group (etcd leases, Chubby). A new grantor leader must wait out the maximum outstanding lease term before granting.
• Leader leases for reads: a Raft/Paxos leader serves reads locally while its lease, granted by a majority, is valid. Followers promise not to vote for another leader until the lease runs out (Spanner, CockroachDB range leases).
• Renew asynchronously on a dedicated thread with its own timeouts, so a slow request path doesn't starve renewals.
• On losing a lease, fail fast: stop serving, abort in-flight work, and exit if unsure.

Pitfalls

• Starting the holder's timer when the response arrives instead of before the request: the holder overestimates its lease by the RTT.
• GC pause / VM stall between "lease valid?" and the write: the classic split-brain. Only fencing tokens at the resource fix it.
• Using a lease in a store that doesn't check tokens (e.g. a plain distributed lock around writes to S3) gives no safety, just probable mutual exclusion.
• Renew interval too close to the term: one slow renewal loses the lease and triggers failover storms.
• Assuming lease expiry implies the old holder has stopped: it implies only that it should have.

Variants and alternatives

In production

Google Chubby (sessions + KeepAlive, 12 s default lease), Spanner Paxos leader leases (10 s), etcd leases (Kubernetes leader election, distributed locks), CockroachDB range leases, HDFS NameNode client leases for file writers, Kafka controller epochs as fencing tokens.

Implementations

Sources

• Cary G. Gray, David R. Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency, SOSP 1989. paper
• Mike Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI 2006. paper
• James C. Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI 2012. paper
• Martin Kleppmann, Designing Data-Intensive Applications, O'Reilly 2017 (ch. 8, fencing tokens). book
• Droms, Dynamic Host Configuration Protocol, RFC 2131, 1997. RFC