On this page

Leases & Fencing

A lock that never expires is a liability: if its holder crashes, nobody can ever take it again. A lock that does expire is a different kind of liability: the holder may still believe it owns the lock after the system has handed it to someone else. Every coordination system you will ever use — ZooKeeper, etcd, Consul, Chubby, Kafka's controller, HDFS NameNode HA, CockroachDB range leases — lives between these two failure modes.

The two tools that make the space navigable are:

  • Leases — authority that is granted for a bounded amount of time, so that a crashed holder's authority evaporates on its own.
  • Fencing — a mechanism, usually a monotonically increasing number, that lets the resource being protected reject a holder whose lease has already been superseded, regardless of what that holder believes.

Leases give you liveness (the system recovers from crashed holders without a human). Fencing gives you safety (a stale holder cannot corrupt state). You almost always need both. This page builds both from first principles, works through the timing math, and shows how real systems combine them.

If you have not yet read them, Distributed Locking covers Redis/Redlock/ZooKeeper lock recipes and Kleppmann's critique, and Leader Election covers how a leader is chosen. This page is about the time dimension of the authority that those mechanisms hand out, and about what the protected resource must do to stay safe.


Why Leases Exist

The crashed-holder problem

Imagine a plain mutual-exclusion service. Client A asks for lock L, the service records "A holds L", and A goes off to work. Now A's machine loses power. From the service's point of view nothing has happened: no release message ever arrives. Without some rule for revoking A's ownership, L is held forever.

There are only three ways out:

  1. A human intervenes. Workable for a weekly batch job, unacceptable for a database primary.
  2. The service detects that A is dead and revokes. But in an asynchronous network the service cannot distinguish "A is dead" from "A is slow" or "the path to A is broken" (see Failure Detectors and FLP Impossibility). Any detector will sometimes be wrong.
  3. The authority was only ever granted for a bounded time. A must keep renewing. If renewals stop arriving — for whatever reason — the authority lapses when the time runs out.

Option 3 is a lease. It replaces the impossible question "is A dead?" with the answerable question "has A renewed within the last T seconds?". Both sides can reason about the second question independently, using only their own clocks, without exchanging any further messages. That independence is the whole trick.

A bit of history

The term comes from Cary Gray and David Cheriton's 1989 SOSP paper "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency". Their problem was cache consistency in a distributed file system: a server grants a client the right to cache a file; before the file can be written, every cached copy must be invalidated. If a caching client is unreachable, the writer would block forever. With leases, the writer waits at most until the unreachable client's lease expires. They also analysed the trade-off that still governs lease design today: short leases mean fast recovery but more renewal traffic; long leases mean less traffic but longer unavailability after a failure.

Google's Chubby lock service (Mike Burrows, OSDI 2006) made leases the backbone of an entire coordination service: the master holds a master lease from the replicas, each client holds a session lease from the master, and cached data is protected by those sessions. Chubby also introduced sequencers — what everyone now calls fencing tokens. Almost every coordination service since (ZooKeeper sessions, etcd leases, Consul sessions) is a variation on that design.


First Principles

What exactly is a lease?

A lease is a promise with three parts:

PartMeaning
GrantorThe party that issues authority (a lock service, a quorum of replicas, a metadata server)
HolderThe party that receives authority (a client, a would-be leader, a cache)
TermA duration D during which the grantor promises not to grant conflicting authority to anyone else

The grantor's promise is: "for D seconds from when I granted this, I will not give conflicting authority to anyone else." The holder's obligation is: "I will stop exercising this authority before D seconds have elapsed, unless I have renewed."

Notice the asymmetry. The grantor's obligation is easy to keep — it just refuses conflicting requests until its timer fires. The holder's obligation is the hard one, because the holder must notice that its time is up, and a process that is paused, swapped out, or stuck in a 30-second garbage collection does not notice anything.

Leases are about duration, not timestamps

A naive implementation sends an absolute expiry: "your lease expires at 14:00:10.000". That is only safe if the two machines' wall clocks agree, and Clock Synchronization explains at length why they do not. NTP corrections can step a clock backwards or forwards; a VM restored from a snapshot can be minutes off.

Robust lease protocols therefore transmit a duration and have each side measure that duration with its own monotonic clock (CLOCK_MONOTONIC on Linux, time.monotonic() in Python, the monotonic reading Go embeds in time.Time, performance.now() / process.hrtime in Node). The assumption is no longer "our clocks agree" but the much weaker:

Bounded drift: each node's clock advances at a rate within some factor (1 ± ρ) of real time.

Quartz oscillators typically drift on the order of tens of parts per million. That is tiny — 50 ppm is 0.5 ms over a 10-second lease — but lease protocols are designed with a much larger safety margin because the real threat is not oscillator drift. It is the holder not running at all for a while.

The three clocks in a lease protocol

sequenceDiagram
    participant H as Holder
    participant G as Grantor
    Note over H: t0 = holder monotonic time when request is SENT
    H->>G: Acquire lease, duration D
    Note over G: t1 = grantor monotonic time when request is RECEIVED
    G-->>H: Granted, token 34, duration D
    Note over G: Grantor refuses conflicting grants until t1 + D + guard
    Note over H: Holder treats lease valid only until t0 + D x (1 - rho) - margin

The key rule is that the holder starts its timer before sending the request, and the grantor starts its timer after receiving it. Because the send happens before the receive in real time, the holder's window always closes earlier in real time than the grantor's — as long as neither clock runs too fast or too slow relative to the other. The drift factor and margin absorb the residual uncertainty.

Worked example: the timing math

Let's put numbers on it.

  • Lease duration D = 10 s
  • Drift bound ρ = 0.001 (0.1%, very generous compared to quartz, covering VM clock weirdness)
  • Network delay for the request: anywhere between 0 and 200 ms
  • Holder safety margin m = 1 s (time budget for the last in-flight operation)

Holder side. Holder records t0 = 1000.000 (monotonic seconds), sends request. It treats the lease as valid until:

Grantor side. The request arrives 200 ms later in real time. Grantor records t1 on its own clock and refuses conflicting grants until t1 + D + guard. With guard = 0 and the grantor's clock running 0.1% slow in the worst case, the grantor's window ends no sooner than ~10.190 s of real time after the holder sent the request (0.2 s network + ~9.99 s).

Gap. The holder stops at ~8.99 s of real time after sending; the grantor will not re-grant before ~10.19 s. The 1.2 s gap is the safety buffer. Even with zero network delay the gap is ~1 s, the margin.

Now the bad case: the holder's process is frozen for 12 seconds after checking "is my lease still valid?" and before performing the write. No arithmetic on the holder's side can protect against that, because the holder isn't executing. The rest of this page is about that case.

Leases vs. locks vs. sessions

ConceptDurationWhat expiry meansTypical system
Lock (no TTL)UnboundedNever expires; must be released or manually brokenflock, database row locks within a transaction
Lock with TTLFixed TTL per acquisitionLock disappears after TTLRedis SET key val NX PX 30000
LeaseRenewable termAuthority lapses unless renewedetcd lease, Chubby master lease
SessionRenewable, many objects attachedAll ephemeral state (locks, ephemeral nodes) owned by the session vanishes on expiryZooKeeper session, Consul session, Chubby session

A session is really one lease with many things hanging off it. That design is efficient — one keep-alive stream per client rather than per lock — but it means a single missed heartbeat window releases everything the client holds at once.


Core Mechanics

Acquisition, renewal and expiry

A practical lease protocol has four operations: grant, renew (keep-alive), release (voluntary revoke), and expire (implicit revoke).

stateDiagram-v2
    [*] --> Free
    Free --> Held: "grant(holder, D) — token++"
    Held --> Held: "renew before expiry"
    Held --> Free: "release()"
    Held --> Expired: "no renew within D"
    Expired --> Free: "guard period elapsed"
    Free --> [*]

Renewal policy matters more than people think:

  • Renew early. Renew at roughly D/3 (etcd's Go client keep-alive loop, for example, sends keep-alives well before the TTL runs out). That gives two more chances before expiry if a renewal is lost.
  • Bound the renewal call itself. A renewal RPC that hangs for longer than the remaining lease is worse than useless — it keeps the holder hoping. Give it a deadline of at most the remaining validity minus margin.
  • On renewal failure, assume the worst. If you cannot confirm renewal before your local deadline, stop acting as holder at the local deadline. Do not "assume it probably succeeded".
  • Renewal does not reset the token. A renewed lease keeps the same fencing token; only a new grant (after expiry or release) increments it.

What the holder must do when the lease is uncertain

Chubby's paper describes a useful intermediate state: when a client's session lease times out locally, the client library does not immediately declare the session dead. It enters a jeopardy state, disables its cache, and waits a grace period (45 s by default in the paper) to see if it can reach a (possibly new) master. If it can, the session survives; if not, the application is told the session is lost. During jeopardy the client must not trust anything the lease protected.

This generalises:

Holder stateConditionAllowed actions
Validnow < local deadline − marginExercise authority, serve cached reads
Uncertainlocal deadline − margin ≤ now, renewal not confirmedNo new writes, no cached reads, keep trying to renew
LostGrantor says expired, or grace period overDrop all state derived from the lease, re-acquire from scratch

Lease-based leadership

A leader election (see Leader Election) chooses who leads. A leader lease bounds how long the leader may act without re-confirming. The usual shape:

  1. A candidate wins an election (or acquires a lock key in etcd/ZooKeeper/Consul).
  2. The quorum promises: "we won't elect anyone else for D seconds."
  3. The leader acts only while its local lease timer says it is valid.
  4. The leader renews by heartbeating; if heartbeats stop getting quorum acks, its lease runs out on its own.

Google Spanner uses exactly this pattern for Paxos group leaders: the paper describes timed leader leases, 10 seconds by default, renewed implicitly on successful writes. Chubby's master holds a master lease from its replicas for the same reason. CockroachDB attaches a range lease to each range; one variant ties leases to a node-liveness record with an epoch, so incrementing a node's liveness epoch invalidates every lease that node held at once.

flowchart LR
    subgraph Quorum["Replica quorum"]
        R1["Replica 1"]
        R2["Replica 2"]
        R3["Replica 3"]
    end
    L["Leader (lease until T)"] -->|"heartbeat / renew"| R1
    L -->|"heartbeat / renew"| R2
    L -->|"heartbeat / renew"| R3
    R1 -->|"ack: won't vote for others until T"| L
    R2 -->|"ack"| L
    C["Clients"] -->|"reads + writes"| L
    L -->|"writes with epoch / token"| S[("Storage")]

Lease-based caching

The original use case is still common. A server grants clients a lease on cached data; while the lease is valid, the server must either (a) notify the client before changing the data and wait for an ack, or (b) wait for the lease to expire. Either way, the client's cache is never stale while the lease is valid.

Chubby combines both: on a write, the master sends invalidations to every client caching that file and blocks the write until each has acknowledged or its lease has expired. The result is a consistent cache with a hard upper bound on how long a dead client can delay a writer.

Modern examples of the same idea:

  • DNS TTLs are a degenerate lease without invalidation — you get bounded staleness, but no consistency.
  • CDN surrogate caching with purge APIs is closer to Gray & Cheriton: TTL as a backstop, invalidation for speed.
  • Facebook's memcache leases (from the 2013 NSDI paper "Scaling Memcache at Facebook") use a different meaning of "lease": a token handed out on a cache miss to prevent stale sets and thundering herds. Same word, related idea — a time-bounded right to write the key.

See Cache Invalidation for the broader caching picture.


The Process-Pause Hazard

Everything so far assumes the holder is running. The central difficulty of leases is that a process can stop running at any instruction, for an unbounded time, without knowing it stopped.

What pauses processes in practice

CauseTypical pauseNotes
Stop-the-world GCms to tens of secondsLarge JVM heaps with older collectors are the classic offender; modern low-pause collectors (ZGC, Shenandoah) shrink but do not eliminate pauses
VM live migration / steal timems to secondsThe guest OS has no idea it was paused
Host or container CPU throttlingms to secondscgroup CPU quotas can starve a process within each period
Swapping / major page faultsms to secondsTouching a swapped-out page blocks the thread
SIGSTOP, debugger attach, laptop sleepUnboundedIncluding "someone ran kill -STOP while debugging production"
Synchronous disk I/O on a degraded volumeSeconds to minutesfsync on a struggling network disk can block for a very long time
Kernel or hypervisor bugsUnboundedRare, real

A pause can happen between any two instructions, including between "check my lease" and "write to storage". This is a time-of-check-to-time-of-use (TOCTOU) race, and no amount of checking on the holder side closes it.

Worked timeline: how a correct-looking lease still corrupts data

sequenceDiagram
    participant A as Client A
    participant LS as Lease Service
    participant B as Client B
    participant S as Storage
    A->>LS: acquire lease on file F
    LS-->>A: granted, 10s
    Note over A: checks lease — valid, 9.5s left
    Note over A: GC pause starts — 15 seconds
    Note over LS: lease of A expires at t=10s
    B->>LS: acquire lease on file F
    LS-->>B: granted, 10s
    B->>S: write F = version from B
    S-->>B: ok
    Note over A: GC pause ends at t=15s, A still thinks it holds F
    A->>S: write F = version from A
    S-->>A: ok — B's write is silently overwritten

Nothing in this diagram is a bug in the lease service. The lease service was correct: A's lease had expired. Client A was correct too, by its own lights: it checked the lease and it was valid. The corruption happens because storage accepted a write from a holder whose authority had lapsed, and storage had no way to know.

This is the scenario Martin Kleppmann used in 2016 to critique Redlock (summarised in Distributed Locking). The conclusion generalises beyond Redis: a lease alone cannot provide mutual exclusion for side effects on an external resource. It can only tell holders when they should stop. To guarantee they do stop, the resource itself has to participate.

Why safety margins help but cannot solve it

You can make the holder more conservative: bigger margin, check the lease immediately before every write, bound every operation's duration. These reduce the window; they never close it, because the window is "the gap between the last check and the side effect taking effect at the resource", and a pause, a slow network, or a delayed packet can stretch that gap arbitrarily.

flowchart LR
    A["Check lease valid"] --> B["Build request"]
    B --> C["Send over network"]
    C --> D["Request sits in a queue / retransmit"]
    D --> E["Storage applies write"]
    style A fill:#2f9e44,color:#fff
    style E fill:#c92a2a,color:#fff

Every arrow is a place where time can pass. Even a request that left the holder while the lease was valid can arrive after it expired — a TCP retransmission or a congested switch is enough. Margins shrink the probability; fencing removes it.


Fencing Tokens and Epochs

The idea

Every time the grantor issues a new grant (not a renewal), it attaches a number strictly greater than any it has issued before: the fencing token (also called an epoch, generation, term, or sequencer). The holder sends the token with every operation on the protected resource. The resource remembers the highest token it has seen and rejects any operation carrying a smaller one.

That's it. The protection no longer depends on the holder's sense of time at all. A paused holder wakes up with an old token; the resource has already seen a newer token from the new holder; the stale write bounces.

Worked timeline with fencing

sequenceDiagram
    participant A as Client A
    participant LS as Lease Service
    participant B as Client B
    participant S as Storage
    A->>LS: acquire lease on F
    LS-->>A: granted, token 33
    Note over A: GC pause — 15 seconds
    Note over LS: lease 33 expires
    B->>LS: acquire lease on F
    LS-->>B: granted, token 34
    B->>S: write F, token 34
    Note over S: max seen 33 → 34, accept
    S-->>B: ok
    Note over A: wakes up, still holds token 33
    A->>S: write F, token 33
    Note over S: 33 is less than 34, reject
    S-->>A: rejected — stale token
    Note over A: A learns it lost the lease and stops

Walk through the storage state:

StepEventStorage max_tokenResult
1Initial32—
2A acquires, gets 33 (doesn't write yet)32—
3A pauses; lease 33 expires32—
4B acquires, gets 3432—
5B writes with 3432 → 34Accepted
6A writes with 3334Rejected (33 < 34)
7B writes again with 3434Accepted (equal is fine — same holder)

Two subtleties:

  • Equal tokens are accepted. The current holder writes many times with the same token. The rule is token >= max_seen, update max_seen = token.
  • What if A had written before B? Suppose A wakes up just before B's first write: A writes with 33 (accepted, 33 ≥ 32), then B writes with 34 (accepted). That is fine: at the moment A wrote, no newer holder had touched storage. The order of authority as observed by the resource is consistent with the order of grants. Fencing does not guarantee that a stale holder never writes; it guarantees that once a newer holder has written, no older holder ever will again. That is precisely the property you need for linearizable handover.

Where the token comes from

The token must be monotonic across grantor failovers, which means it must come from replicated, durable state — not a counter in one process's memory.

SystemNatural fencing value
ZooKeeperzxid of the lock znode creation, or the znode's cversion / sequential node number
etcdThe key's mod_revision or create_revision (cluster-wide monotonic revision)
Raft-based servicesThe leader's term, possibly combined with log index
ChubbyThe sequencer: lock name, mode, and lock generation number
KafkaController epoch; partition leader epoch; producer epoch for transactional producers
HDFS QJMWriter epoch number promised by a quorum of JournalNodes
Your own DBA BIGINT column incremented in the same transaction that records the grant

etcd's revision is a convenient choice: every write in the cluster increments the global revision, so the revision at which you created your lock key is unique and strictly greater than any earlier lock's.

Storage-side enforcement

Fencing only works if the resource checks the token, and checks it atomically with the write. Options, from most to least robust:

  1. The resource natively supports conditional writes. Use them.
    • SQL: UPDATE ... WHERE fence_token <= $token in one statement.
    • DynamoDB: a ConditionExpression on a token attribute.
    • Object stores with conditional writes (e.g. S3 and GCS support preconditions on object generation/ETag) can be used for compare-and-swap on a manifest object.
    • etcd/ZooKeeper themselves: a transaction that checks the lock key still exists at your revision before writing (etcd Txn with Compare(CreateRevision(key), "=", rev)).
  2. A proxy in front of the resource that tracks max_token and drops stale requests. Works if every path to the resource goes through the proxy.
  3. The resource is a log or replicated store that already uses epochs — e.g. writes to Kafka by a transactional producer, where the broker rejects a zombie producer with an old epoch (ProducerFencedException).

If the resource cannot check tokens at all — a legacy FTP server, an external payment API that has no idempotency or precondition support — fencing is impossible and you must fall back to making the operation itself safe to duplicate: idempotency keys (see Idempotency) or exactly-once processing patterns (see Exactly-Once Semantics).

Checking the token in application code is not fencing

SELECT max_token → compare in your service → UPDATE is a race: two writers can both read the old max and both write. The check and the write must be one atomic operation at the resource (one SQL statement, a conditional put, or a transaction with appropriate isolation).

Epochs in replication: fencing a whole node

Fencing tokens protect individual writes. Epoch numbers apply the same idea to an entire replica or leader role.

  • Raft terms. Every RPC carries the sender's term. A node receiving a message with a higher term steps down and updates its own; a message with a lower term is rejected. An old leader that was partitioned away cannot get anything committed, because no majority will accept its stale term. See Raft Full Walkthrough.
  • HDFS Quorum Journal Manager. When a NameNode becomes active, it asks a majority of JournalNodes to promise a new epoch higher than any they've seen. JournalNodes then reject edits from any writer with a lower epoch. Even if the old active NameNode keeps running, its edits cannot reach a quorum — the "fencing" is enforced by the shared storage.
  • Kafka. The controller epoch rejects a zombie controller's commands; partition leader epochs let followers detect log divergence after an unclean leadership change.
  • ZooKeeper's ZAB. The high 32 bits of each zxid are the epoch, so proposals from an old leader are distinguishable and discarded. See ZAB Protocol.

Epoch fencing works because it is checked by a quorum: a deposed leader may keep running and may even believe it is leader, but it cannot assemble a majority that accepts its epoch.

Heavier fencing: STONITH and resource-level isolation

When the protected resource cannot check tokens — a shared SAN volume, a floating IP — clusters fence at a lower level:

  • STONITH ("shoot the other node in the head"): power off the old holder via an IPMI/iLO/PDU before the new holder takes over. Pacemaker clusters use this. Brutal but definitive.
  • Storage-level fencing: SCSI persistent reservations, revoking the old node's access at the storage array.
  • Network fencing: revoke the old node's security-group or switch-port access.
  • Cloud API fencing: detach the volume from the old instance before attaching it to the new one (and verify the detach completed).

HDFS NameNode HA historically offered sshfence (log in and kill the process) and arbitrary shell fencing methods, before QJM made epoch-based storage fencing the norm.

Fencing styleEnforced byNeeds cooperation of resource?Failure mode if misconfigured
Token per writeResource (conditional write)YesStale writes accepted
Epoch on replication RPCsQuorum of replicasYes (built into protocol)None if protocol is correct
STONITHPower controllerNoBoth nodes alive → split brain, or both dead → outage
Storage reservationStorage arrayPartiallyOld node retains access

Split-Brain Prevention

Split brain is two nodes simultaneously acting as the single authority. Leader Election covers how elections can produce it; leases and fencing are the two layers that stop it from causing damage.

flowchart TB
    P["Network partition"] --> Old["Old leader (minority side)"]
    P --> New["New leader elected (majority side)"]
    Old --> Q1{"Lease still valid locally?"}
    Q1 -->|"no"| Stop["Steps down by itself"]
    Q1 -->|"yes, briefly"| W["Tries to write"]
    W --> Q2{"Resource checks epoch / token?"}
    Q2 -->|"yes"| Rej["Rejected — stale epoch"]
    Q2 -->|"no"| Corrupt["Split-brain write — data corruption"]
    style Corrupt fill:#c92a2a,color:#fff
    style Rej fill:#2f9e44,color:#fff
    style Stop fill:#2f9e44,color:#fff

The layered defence:

  1. Majority quorums for election. Only one side of a partition can have a majority, so only one side can elect.
  2. Leader leases with a margin. The new leader cannot be elected until the old leader's lease has expired from the quorum's point of view, and the old leader stops acting before then from its own point of view. In the common case this alone prevents overlap.
  3. Fencing at every resource. Covers the uncommon cases — pauses, clock anomalies, bugs in step 2.
  4. Observability. Alert on any rejected-stale-token event. In a healthy system they're rare; a burst of them means a pause or partition happened and the safety net caught it.

The order matters

Lease timing is an optimisation that keeps the stale holder from even trying. Fencing is the guarantee. Systems that implement only leases are correct only as long as their timing assumptions hold. Systems that implement fencing are correct even when they don't — they just get slower.


Lease-Based Reads in Raft

A Raft leader can serve writes safely because every write goes through log replication, which a deposed leader cannot complete. Reads are trickier: a leader that has been partitioned away might still believe it's leader and serve a stale value — a stale read, violating linearizability (see Consistency Models).

Diego Ongaro's Raft dissertation (§6.4) describes three ways to serve linearizable reads:

ApproachHowCost per readDepends on clocks?
Log readAppend the read as a log entry, serve when committedFull replication round + disk writeNo
ReadIndexRecord commit index, confirm leadership with a heartbeat round to a majority, wait until applied, serveOne network round trip (batchable)No
Lease readIf a majority acked a heartbeat within the last election timeout (minus drift margin), serve locallyZero network round tripsYes

The lease read works like this. Followers will not start an election until they have gone a full election timeout without hearing from the leader. So if the leader sent a heartbeat at time t and a majority acknowledged it, no other leader can exist until at least t + election_timeout — measured on the followers' clocks. Adjusting for drift, the leader treats itself as holding a lease until:

where tsend is when the leader sent the heartbeat (again: start the timer before sending). Within that window, a local read is linearizable.

sequenceDiagram
    participant C as Client
    participant L as Leader
    participant F1 as Follower 1
    participant F2 as Follower 2
    Note over L: t_send = 100.000
    L->>F1: heartbeat, term 7
    L->>F2: heartbeat, term 7
    F1-->>L: ack
    F2-->>L: ack
    Note over L: majority acked, lease valid until 100.000 + timeout x (1 - rho)
    C->>L: read x
    Note over L: now within lease, serve from local state
    L-->>C: x = 42

Two important caveats:

  1. The lease read depends on bounded clock drift and on the leader not pausing between "check lease" and "serve read". A paused leader that wakes up might serve a read from before a newer leader's write. Unlike writes, reads have no resource to fence them — the leader is the resource. This is why lease reads are an opt-in optimisation in most implementations.
  2. A new leader must not serve lease reads until it has committed an entry in its own term, otherwise it may not know the latest commit index.

Real systems: etcd's Raft library offers both ReadOnlySafe (ReadIndex, the default) and ReadOnlyLeaseBased. TiKV uses leader-lease reads to serve most reads without a round trip. CockroachDB serves reads from the leaseholder of a range, and the range-lease mechanism is designed so only one node can believe it holds a valid lease at any moment (with clock-uncertainty handling built in).


Implementation

A lease service and a fencing-aware store (Go)

The following is a self-contained, runnable Go program. It models a lease service, a store that enforces fencing tokens, and a client that renews its lease — then reproduces the GC-pause scenario and shows the store rejecting the stale write.

// leases.go — run with: go run leases.go
package main

import (
	"errors"
	"fmt"
	"sync"
	"time"
)

// ---------- Lease service (grantor) ----------

type Lease struct {
	Holder  string
	Token   uint64        // fencing token, increments on every NEW grant
	TTL     time.Duration // duration the grantor promises exclusivity
	granted time.Time     // grantor-local monotonic time of grant/renewal
}

type LeaseService struct {
	mu        sync.Mutex
	current   *Lease
	nextToken uint64 // in production: durable, replicated (etcd revision, Raft term, DB sequence)
	guard     time.Duration
}

var ErrHeld = errors.New("lease held by another holder")
var ErrNotHolder = errors.New("not the current holder or lease expired")

func NewLeaseService(guard time.Duration) *LeaseService {
	return &LeaseService{nextToken: 33, guard: guard}
}

func (s *LeaseService) expired(now time.Time) bool {
	// Grantor's view: lease ends TTL + guard after it was granted/renewed.
	return s.current == nil || now.Sub(s.current.granted) > s.current.TTL+s.guard
}

func (s *LeaseService) Acquire(holder string, ttl time.Duration) (Lease, error) {
	s.mu.Lock()
	defer s.mu.Unlock()
	now := time.Now() // time.Now carries a monotonic reading; Sub uses it
	if !s.expired(now) && s.current.Holder != holder {
		return Lease{}, ErrHeld
	}
	if s.current != nil && s.current.Holder == holder && !s.expired(now) {
		s.current.granted = now // re-acquire by same holder == renewal, same token
		return *s.current, nil
	}
	s.nextToken++
	s.current = &Lease{Holder: holder, Token: s.nextToken, TTL: ttl, granted: now}
	return *s.current, nil
}

func (s *LeaseService) Renew(holder string, token uint64) error {
	s.mu.Lock()
	defer s.mu.Unlock()
	now := time.Now()
	if s.expired(now) || s.current.Holder != holder || s.current.Token != token {
		return ErrNotHolder
	}
	s.current.granted = now
	return nil
}

// ---------- Fencing-aware storage (the protected resource) ----------

type Store struct {
	mu       sync.Mutex
	maxToken uint64
	data     map[string]string
}

var ErrStaleToken = errors.New("stale fencing token")

// Write is atomic: the token check and the write happen under one lock,
// the same way a single conditional SQL UPDATE would.
func (st *Store) Write(token uint64, key, val string) error {
	st.mu.Lock()
	defer st.mu.Unlock()
	if token < st.maxToken {
		return fmt.Errorf("%w: got %d, max seen %d", ErrStaleToken, token, st.maxToken)
	}
	st.maxToken = token
	st.data[key] = val
	return nil
}

// ---------- Holder (client) ----------

type Holder struct {
	name    string
	svc     *LeaseService
	lease   Lease
	validTo time.Time // holder-local deadline, computed conservatively
}

const drift = 0.001              // assume clocks may run 0.1% off
const margin = 50 * time.Millisecond

func (h *Holder) Acquire(ttl time.Duration) error {
	sent := time.Now() // start the timer BEFORE the request leaves
	l, err := h.svc.Acquire(h.name, ttl)
	if err != nil {
		return err
	}
	h.lease = l
	h.validTo = sent.Add(time.Duration(float64(ttl)*(1-drift)) - margin)
	return nil
}

func (h *Holder) Renew() error {
	sent := time.Now()
	if err := h.svc.Renew(h.name, h.lease.Token); err != nil {
		h.validTo = time.Time{} // lost: stop acting immediately
		return err
	}
	h.validTo = sent.Add(time.Duration(float64(h.lease.TTL)*(1-drift)) - margin)
	return nil
}

func (h *Holder) Valid() bool { return time.Now().Before(h.validTo) }

func main() {
	svc := NewLeaseService(20 * time.Millisecond)
	store := &Store{data: map[string]string{}, maxToken: 32}
	ttl := 200 * time.Millisecond

	a := &Holder{name: "A", svc: svc}
	b := &Holder{name: "B", svc: svc}

	must(a.Acquire(ttl))
	fmt.Printf("A acquired token %d, valid=%v\n", a.lease.Token, a.Valid())

	// A checks its lease... and then is paused (GC, VM steal, SIGSTOP).
	if a.Valid() {
		time.Sleep(400 * time.Millisecond) // the pause: longer than the TTL

		// Meanwhile B acquires once A's lease has expired at the grantor.
		// (In this single-process demo B acquires after the pause; the ordering
		// at the store is what matters.)
		must(b.Acquire(ttl))
		fmt.Printf("B acquired token %d\n", b.lease.Token)
		must(store.Write(b.lease.Token, "file-F", "written by B"))
		fmt.Println("B wrote file-F")

		// A wakes up and performs the write it decided to do before the pause.
		err := store.Write(a.lease.Token, "file-F", "written by A")
		fmt.Println("A write result:", err)
	}

	fmt.Println("final file-F =", store.data["file-F"])

	// Self-check: the stale write must have been rejected.
	if store.data["file-F"] != "written by B" {
		panic("fencing failed: stale holder overwrote newer holder")
	}
	if err := store.Write(a.lease.Token, "file-F", "x"); !errors.Is(err, ErrStaleToken) {
		panic("expected stale token error")
	}
	fmt.Println("self-check passed")
}

func must(err error) {
	if err != nil {
		panic(err)
	}
}

Expected output:

A acquired token 34, valid=true
B acquired token 35
B wrote file-F
A write result: stale fencing token: got 34, max seen 35
final file-F = written by B
self-check passed

What to change for production:

  • nextToken must be durable and replicated. If the lease service restarts and hands out token 34 again, fencing is broken. Use etcd revisions, a Raft term, or a database sequence.
  • Store.Write must be enforced by the real storage system atomically — see the SQL below.
  • The holder should run renewals on a background loop at roughly TTL/3, with each renewal RPC bounded by a deadline shorter than the remaining validity.

Fencing in SQL

A single conditional statement is atomic in every mainstream relational database:

-- Table that the leaseholder writes to
CREATE TABLE job_state (
    job_id      TEXT PRIMARY KEY,
    payload     JSONB NOT NULL,
    fence_token BIGINT NOT NULL DEFAULT 0
);

-- Write guarded by the fencing token. Returns 0 rows if the token is stale.
UPDATE job_state
SET    payload = $2,
       fence_token = $3
WHERE  job_id = $1
  AND  fence_token <= $3;

The application treats "0 rows updated" as "I have lost my lease": it stops work, discards local state derived from the lease, and re-acquires.

etcd: the lease and the token come from the same place

With etcd, a lock is a key attached to a lease; the key's CreateRevision is a ready-made fencing token, and an etcd transaction can check it atomically before writing to etcd itself:

// Using go.etcd.io/etcd/client/v3 and its concurrency package.
sess, err := concurrency.NewSession(cli, concurrency.WithTTL(10)) // lease + keep-alive loop
if err != nil { return err }
defer sess.Close()

mu := concurrency.NewMutex(sess, "/locks/job-42")
if err := mu.Lock(ctx); err != nil { return err }

fence := mu.Header().Revision // cluster revision at acquisition: monotonic, usable as a token

// Writes to etcd itself: guard with a transaction that checks we still own the lock key.
// IsOwner() compares the lock key's CreateRevision with the one recorded at Lock().
_, err = cli.Txn(ctx).
	If(mu.IsOwner()).
	Then(clientv3.OpPut("/jobs/42/state", "running")).
	Commit()

// Writes to an EXTERNAL store: pass `fence` along and enforce it there,
// e.g. with the SQL UPDATE ... WHERE fence_token <= $fence shown above.

concurrency.Session exposes Done(), a channel that closes when the lease is lost; production code should select on it and abort work promptly.


Failure Modes and Edge Cases

Clock steps and wall-clock leases

If a lease implementation measures time with the wall clock, an NTP step backwards makes a holder's lease appear longer; a step forwards on the grantor makes it expire early. Both have caused real bugs across the industry. Always use a monotonic clock for durations. Note that monotonic clocks can still behave oddly across VM suspend/resume and live migration, which is one more reason fencing is the backstop.

Lease service failover

When the grantor fails over to a new replica, the new grantor must honour leases granted by the old one. Approaches:

  • Replicate lease state (etcd, ZooKeeper, Chubby): the new leader knows every lease. etcd, on leader change, extends existing leases' remaining TTLs so holders aren't spuriously expired by the election time itself.
  • Wait out the maximum lease duration before granting anything: simple, costs availability. Chubby's new master, as described in the paper, conservatively assumes the old master's leases might still be in force and extends client leases during failover.

Expiry storms

A grantor that pauses (or a network blip that delays every keep-alive) can expire thousands of sessions at once, triggering mass re-acquisition, cache rebuilds and leader re-elections. Mitigations: renew early (TTL/3), extend leases on grantor failover, and avoid TTLs so short that a routine pause causes mass expiry.

Choosing the lease duration

Lease durationRecovery time after crashRenewal trafficSensitivity to pausesTypical use
1–3 sFastHighVery high — normal GC can expire youLow-latency leader leases with tuned runtimes
10–30 sModerateModerateModerateMost service locks, ZooKeeper/etcd sessions
MinutesSlowLowLowBatch job ownership, cron singleton

Rules of thumb:

  • The lease must be comfortably longer than the p99.9 pause you observe (GC logs, scheduler latency), or you will lose leases during normal operation.
  • Recovery time after a holder crash ≈ lease duration + guard + time to re-elect/re-acquire.
  • Renewal interval ≈ duration / 3.

When the resource cannot fence

If the side effect is "send an email", "call a partner's API", or "charge a card", there is nothing to fence. Then:

  • Make the operation idempotent with a stable key (see Idempotency) so that a duplicate from a stale holder is harmless.
  • Or route the side effect through a component that can fence — write an outbox row guarded by the token, and let a separate dispatcher send it (see the outbox pattern in Exactly-Once Semantics).

Real Systems at a Glance

SystemLease mechanismFencing mechanism
ChubbyMaster lease from replicas; client session leases with KeepAlive and grace periodSequencers (lock name + mode + generation); lock-delay for servers that can't check sequencers
ZooKeeperSession timeout negotiated with the ensemble; ephemeral nodes vanish on expiryzxid (epoch in high bits); znode version/sequence numbers usable as tokens
etcdFirst-class leases with TTL and keep-alive; keys attached to leasesCluster-wide revision; Txn compares
ConsulSessions with TTL / health-check binding; lock-delayModifyIndex / LockIndex values
RaftLeader lease via heartbeat majority (optional, for reads)Term numbers on every RPC
SpannerPaxos leader leases (10 s default per the paper)Paxos ballot/term; TrueTime-bounded disjointness of leases
KafkaController and partition leadership managed by the controller quorumController epoch, leader epoch, producer epoch
HDFS HA (QJM)Active NameNode chosen via ZooKeeper failover controllerEpoch promised by a JournalNode quorum
CockroachDBRange leases (including epoch-based leases tied to node liveness)Lease sequence/epoch checked on proposals

Chubby's lock-delay deserves a mention as a pragmatic fallback: when a lock holder's session expires (as opposed to releasing cleanly), Chubby refuses to grant the lock to anyone else for a configurable delay (up to a minute, per the paper). It doesn't make stale writes impossible, but it gives in-flight requests from the old holder time to drain for servers that cannot check sequencers.

War Story (illustrative)

A team ran a "singleton" report generator: each instance tried to acquire a Redis lock with a 30-second TTL, and the winner rebuilt a large summary table. A heap-heavy JVM instance occasionally hit a 40-second full GC. After one such pause, it woke up and resumed writing its half-built table while the new lock holder was writing its own. Customers saw totals that matched neither run. The fix was not a longer TTL (the next pause could always be longer). They added a generation column, obtained a monotonically increasing number when acquiring the lock (from a database sequence rather than Redis), and made every write UPDATE ... WHERE generation <= $mine. Stale writers started getting zero-row updates and aborting; the lock TTL went back to being a liveness setting rather than a correctness one.


Decision Guidance

flowchart TD
    Q0{"Do you need exclusive authority over something?"} -->|"no"| N["Use idempotent ops or CRDTs instead"]
    Q0 -->|"yes"| Q1{"Is it efficiency only (dup work OK)?"}
    Q1 -->|"yes"| E["Lease / TTL lock is enough — e.g. Redis SET NX PX"]
    Q1 -->|"no, correctness matters"| Q2{"Can the resource check a token atomically?"}
    Q2 -->|"yes"| F["Lease from a consensus store + fencing token at the resource"]
    Q2 -->|"no"| Q3{"Can you make the side effect idempotent?"}
    Q3 -->|"yes"| I["Lease + idempotency keys / outbox"]
    Q3 -->|"no"| S["Hard isolation — STONITH, storage reservation, or redesign"]
SituationRecommendation
Avoid duplicate cron runs; duplicate work is merely wastefulTTL lock is fine; no fencing needed
Single writer to a database tableLease + fencing column checked in the UPDATE
Leader of a replicated logConsensus protocol with terms/epochs (Raft, ZAB, Paxos) — don't roll your own
Low-latency linearizable reads from a leaderLease reads, only with conservative drift bound and tuned pause behaviour; otherwise ReadIndex
Cache with strong consistencyServer-granted leases + invalidation (Chubby-style), bounded by lease expiry
Shared block deviceSTONITH or storage-level fencing; tokens can't help

Key Takeaways

  1. A lease converts "is the holder dead?" (undecidable) into "has the holder renewed in time?" (decidable locally). It gives liveness.
  2. Leases are measured as durations on monotonic clocks, with the holder starting its timer before sending and subtracting a drift and safety margin.
  3. Process pauses make holder-side checks insufficient: a holder can be stopped between checking and acting.
  4. Fencing tokens — monotonic numbers from replicated state, checked atomically by the resource — give safety regardless of timing.
  5. Epochs/terms are fencing applied to replication protocols, enforced by quorums.
  6. Raft lease reads trade a clock assumption for zero-round-trip reads; ReadIndex is the clock-free alternative.
  7. If the resource can't fence, make the side effect idempotent or isolate the old holder physically.

Interview Questions

1. Why can't a client simply check that its lease is still valid before every write?

Because the check and the write are not atomic. The client may be paused (GC, VM migration, swapping) or its request may be delayed in the network between the check and the moment the write takes effect at the resource. The lease can expire in that gap and be granted to someone else. Only a check performed by the resource, atomically with the write — a fencing token — closes the gap.

2. Your lease service hands out a 10 s lease. How should the holder compute its local expiry, and why?

Start the timer before sending the acquire request, on a monotonic clock, and treat the lease as valid until t_send + D × (1 − ρ) − margin, where ρ is the assumed maximum relative clock drift and the margin covers the longest operation you'll start near the end. Starting before sending guarantees the holder's window ends before the grantor's (which starts on receipt); the drift factor covers clocks running at different rates; the margin covers in-flight work.

3. Where should the fencing token come from? What breaks if it's an in-memory counter?

From durable, replicated state that is monotonic across failovers: etcd revision, ZooKeeper zxid or znode sequence, a Raft term, or a database sequence. If it's an in-memory counter in the lock server, a restart can reset it and re-issue a token the resource has already seen, so a new holder's writes may be rejected or — worse — a stale holder's token may again look current.

4. Explain how Raft lease reads work and what assumption they add over ReadIndex.

The leader records when it sends a heartbeat; once a majority acks, no follower in that majority will start an election until an election timeout has passed on its own clock. So the leader can serve reads locally until t_send + election_timeout × (1 − ρ). ReadIndex needs a round trip per read (or batch) but no clock assumption. Lease reads add the assumptions of bounded drift and that the leader isn't paused between checking the lease and serving the read.

5. A resource cannot check tokens (an external payment API). How do you prevent a stale lock holder from double-charging?

Use an idempotency key derived from the business operation (not the attempt), so the payment provider deduplicates. Or record the intent in a store that can fence (an outbox row written with a token-guarded statement) and have a single dispatcher perform the call with an idempotency key. Lease timing alone cannot prevent the duplicate.

6. Compare Chubby's sequencers and lock-delay.

A sequencer is a fencing token (lock name, mode, generation) that the server receiving a request can verify against Chubby or compare to the highest seen. It provides safety but requires the server to participate. Lock-delay is a fallback for servers that can't check sequencers: after a holder's session is lost uncleanly, Chubby refuses to re-grant the lock for a period so the old holder's in-flight requests can drain. It reduces risk but provides no guarantee.

7. How do HDFS JournalNodes prevent a deposed NameNode from corrupting the edit log?

A new active NameNode obtains a promise of a new, higher epoch from a majority of JournalNodes. Each JournalNode then rejects writes from any writer with a lower epoch. The old NameNode may still be running, but it can't get a quorum of JournalNodes to accept its edits, so it can't commit anything. Fencing is enforced by the shared storage quorum.

8. You see occasional "stale fencing token" rejections in production. Is that a bug?

Not necessarily — it's the safety mechanism working. It means some former holder (after a pause, a partition, or a slow renewal) tried to act after losing its lease. Investigate frequency: a rare event is expected; a rising rate suggests lease TTL too short for observed pauses, renewal problems, or overloaded lease service. Make sure the client handles the rejection by stepping down rather than retrying.


Further Reading

  • Cary G. Gray and David R. Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency, SOSP 1989
  • Mike Burrows, The Chubby Lock Service for Loosely-Coupled Distributed Systems, OSDI 2006
  • Martin Kleppmann, How to do distributed locking (2016), and Designing Data-Intensive Applications, chapter 8
  • Diego Ongaro, Consensus: Bridging Theory and Practice (PhD dissertation, 2014), §6.4 on read-only queries
  • James C. Corbett et al., Spanner: Google's Globally-Distributed Database, OSDI 2012
  • Related pages: Distributed Locking, Leader Election, Clock Synchronization, Failure Detectors, Raft Full Walkthrough