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:
- A human intervenes. Workable for a weekly batch job, unacceptable for a database primary.
- 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.
- 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:
| Part | Meaning |
|---|---|
| Grantor | The party that issues authority (a lock service, a quorum of replicas, a metadata server) |
| Holder | The party that receives authority (a client, a would-be leader, a cache) |
| Term | A 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
| Concept | Duration | What expiry means | Typical system |
|---|---|---|---|
| Lock (no TTL) | Unbounded | Never expires; must be released or manually broken | flock, database row locks within a transaction |
| Lock with TTL | Fixed TTL per acquisition | Lock disappears after TTL | Redis SET key val NX PX 30000 |
| Lease | Renewable term | Authority lapses unless renewed | etcd lease, Chubby master lease |
| Session | Renewable, many objects attached | All ephemeral state (locks, ephemeral nodes) owned by the session vanishes on expiry | ZooKeeper 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 state | Condition | Allowed actions |
|---|---|---|
| Valid | now < local deadline − margin | Exercise authority, serve cached reads |
| Uncertain | local deadline − margin ≤ now, renewal not confirmed | No new writes, no cached reads, keep trying to renew |
| Lost | Grantor says expired, or grace period over | Drop 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:
- A candidate wins an election (or acquires a lock key in etcd/ZooKeeper/Consul).
- The quorum promises: "we won't elect anyone else for D seconds."
- The leader acts only while its local lease timer says it is valid.
- 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
| Cause | Typical pause | Notes |
|---|---|---|
| Stop-the-world GC | ms to tens of seconds | Large 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 time | ms to seconds | The guest OS has no idea it was paused |
| Host or container CPU throttling | ms to seconds | cgroup CPU quotas can starve a process within each period |
| Swapping / major page faults | ms to seconds | Touching a swapped-out page blocks the thread |
SIGSTOP, debugger attach, laptop sleep | Unbounded | Including "someone ran kill -STOP while debugging production" |
| Synchronous disk I/O on a degraded volume | Seconds to minutes | fsync on a struggling network disk can block for a very long time |
| Kernel or hypervisor bugs | Unbounded | Rare, 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:
| Step | Event | Storage max_token | Result |
|---|---|---|---|
| 1 | Initial | 32 | — |
| 2 | A acquires, gets 33 (doesn't write yet) | 32 | — |
| 3 | A pauses; lease 33 expires | 32 | — |
| 4 | B acquires, gets 34 | 32 | — |
| 5 | B writes with 34 | 32 → 34 | Accepted |
| 6 | A writes with 33 | 34 | Rejected (33 < 34) |
| 7 | B writes again with 34 | 34 | Accepted (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, updatemax_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.
| System | Natural fencing value |
|---|---|
| ZooKeeper | zxid of the lock znode creation, or the znode's cversion / sequential node number |
| etcd | The key's mod_revision or create_revision (cluster-wide monotonic revision) |
| Raft-based services | The leader's term, possibly combined with log index |
| Chubby | The sequencer: lock name, mode, and lock generation number |
| Kafka | Controller epoch; partition leader epoch; producer epoch for transactional producers |
| HDFS QJM | Writer epoch number promised by a quorum of JournalNodes |
| Your own DB | A 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:
- The resource natively supports conditional writes. Use them.
- SQL:
UPDATE ... WHERE fence_token <= $tokenin one statement. - DynamoDB: a
ConditionExpressionon 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
TxnwithCompare(CreateRevision(key), "=", rev)).
- SQL:
- A proxy in front of the resource that tracks
max_tokenand drops stale requests. Works if every path to the resource goes through the proxy. - 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
zxidare 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 style | Enforced by | Needs cooperation of resource? | Failure mode if misconfigured |
|---|---|---|---|
| Token per write | Resource (conditional write) | Yes | Stale writes accepted |
| Epoch on replication RPCs | Quorum of replicas | Yes (built into protocol) | None if protocol is correct |
| STONITH | Power controller | No | Both nodes alive → split brain, or both dead → outage |
| Storage reservation | Storage array | Partially | Old 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:
- Majority quorums for election. Only one side of a partition can have a majority, so only one side can elect.
- 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.
- Fencing at every resource. Covers the uncommon cases — pauses, clock anomalies, bugs in step 2.
- 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:
| Approach | How | Cost per read | Depends on clocks? |
|---|---|---|---|
| Log read | Append the read as a log entry, serve when committed | Full replication round + disk write | No |
| ReadIndex | Record commit index, confirm leadership with a heartbeat round to a majority, wait until applied, serve | One network round trip (batchable) | No |
| Lease read | If a majority acked a heartbeat within the last election timeout (minus drift margin), serve locally | Zero network round trips | Yes |
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:
- 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.
- 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:
nextTokenmust 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.Writemust 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 duration | Recovery time after crash | Renewal traffic | Sensitivity to pauses | Typical use |
|---|---|---|---|---|
| 1–3 s | Fast | High | Very high — normal GC can expire you | Low-latency leader leases with tuned runtimes |
| 10–30 s | Moderate | Moderate | Moderate | Most service locks, ZooKeeper/etcd sessions |
| Minutes | Slow | Low | Low | Batch 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
| System | Lease mechanism | Fencing mechanism |
|---|---|---|
| Chubby | Master lease from replicas; client session leases with KeepAlive and grace period | Sequencers (lock name + mode + generation); lock-delay for servers that can't check sequencers |
| ZooKeeper | Session timeout negotiated with the ensemble; ephemeral nodes vanish on expiry | zxid (epoch in high bits); znode version/sequence numbers usable as tokens |
| etcd | First-class leases with TTL and keep-alive; keys attached to leases | Cluster-wide revision; Txn compares |
| Consul | Sessions with TTL / health-check binding; lock-delay | ModifyIndex / LockIndex values |
| Raft | Leader lease via heartbeat majority (optional, for reads) | Term numbers on every RPC |
| Spanner | Paxos leader leases (10 s default per the paper) | Paxos ballot/term; TrueTime-bounded disjointness of leases |
| Kafka | Controller and partition leadership managed by the controller quorum | Controller epoch, leader epoch, producer epoch |
| HDFS HA (QJM) | Active NameNode chosen via ZooKeeper failover controller | Epoch promised by a JournalNode quorum |
| CockroachDB | Range 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"]
| Situation | Recommendation |
|---|---|
| Avoid duplicate cron runs; duplicate work is merely wasteful | TTL lock is fine; no fencing needed |
| Single writer to a database table | Lease + fencing column checked in the UPDATE |
| Leader of a replicated log | Consensus protocol with terms/epochs (Raft, ZAB, Paxos) — don't roll your own |
| Low-latency linearizable reads from a leader | Lease reads, only with conservative drift bound and tuned pause behaviour; otherwise ReadIndex |
| Cache with strong consistency | Server-granted leases + invalidation (Chubby-style), bounded by lease expiry |
| Shared block device | STONITH or storage-level fencing; tokens can't help |
Key Takeaways
- A lease converts "is the holder dead?" (undecidable) into "has the holder renewed in time?" (decidable locally). It gives liveness.
- Leases are measured as durations on monotonic clocks, with the holder starting its timer before sending and subtracting a drift and safety margin.
- Process pauses make holder-side checks insufficient: a holder can be stopped between checking and acting.
- Fencing tokens — monotonic numbers from replicated state, checked atomically by the resource — give safety regardless of timing.
- Epochs/terms are fencing applied to replication protocols, enforced by quorums.
- Raft lease reads trade a clock assumption for zero-round-trip reads; ReadIndex is the clock-free alternative.
- 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