Distributed Locks, Leases, and Fencing Tokens

A distributed lock can tell a client, “you may act now.” It cannot reach into every storage system later and stop that client from acting after its permission has expired. The client may pause, lose contact with the lock service, and resume with code that still believes it owns the lock. Meanwhile another client may have acquired the same lease and completed newer work. Both clients can be honest, and both can write.

This is the expiry race at the heart of distributed locking. Better release code does not remove it. A timeout does not revoke computation already in flight, and a process cannot reliably distinguish a slow network from a failed coordinator. The safety mechanism must therefore live at the destination of the side effect.

The central thesis is: a lease controls admission, while a fencing token lets the protected resource reject stale owners. Each successful acquisition receives a token greater than every token previously issued for that lock. Every protected mutation carries the token. The resource remembers the greatest token it has accepted and rejects lower tokens. If that final check is absent, the system has a best-effort mutex, not robust stale-owner exclusion.

Start with the Stale-Owner Problem #

Imagine worker A acquires a lease for report july, reads source data, and begins rendering a large file. Its runtime then pauses for garbage collection or its virtual machine is suspended. The lock service sees no renewal. After the lease expires, worker B acquires the same lock, renders a corrected report, and stores it. A eventually resumes and uploads its older result.

From the lock service’s perspective, behavior was correct: only one unexpired lease existed at a time. From the storage system’s perspective, B’s valid result was overwritten by A, whose local state was stale. The critical intervals were not simultaneous according to the lease service, yet the side effects overlapped in real execution because expiration did not terminate A.

Many events create the same shape:

• A stop-the-world pause lasts longer than the lease.
• A network partition isolates a client while the resource remains reachable by another path.
• A delayed request reaches the resource after ownership changed.
• An overloaded event loop misses renewals but continues executing queued work.
• A process loses a renewal response and cannot know whether renewal committed.
• An operator restores the coordinator from stale state while old clients still run.

The problem is not malicious behavior and not merely clock skew. It follows from asynchronous communication and independent failure. A client can check its lease immediately before a write, then pause between the check and the write. Asking the coordinator “do I still own it?” narrows a window but never makes the check and an external side effect atomic.

A local mutex avoids this specific gap because the runtime controls both thread admission and memory access within one failure domain. A distributed lock coordinates components it does not control. Its grant is evidence, not a physical barrier.

Understand What a Lease Actually Guarantees #

A lease is permission valid for a bounded interval according to a defined time authority. Unlike an indefinite lock, it eventually becomes available after a holder disappears. That improves liveness, but expiry introduces timing assumptions.

Suppose the coordinator grants a lease until its own time $E$. The client should not assume it can act until local wall time $E$, because clocks differ and messages consumed part of the interval. A conservative client computes a local validity window from the acquisition round trip and a bound on clock uncertainty, then stops initiating work before that window closes. Renewals extend permission only after the coordinator commits them.

Even with disciplined clocks, the lease alone does not make old operations safe. Timing bounds can justify that two well-behaved clients do not both believe they hold a valid lease under specified conditions. They cannot retract a request already buffered at a resource, and they do not constrain a client paused beyond the model’s bound. Safety should survive a late stale request rather than depend on every pause being shorter than the lease.

Lease duration is a liveness and efficiency tradeoff. Short leases recover quickly but renew frequently and are sensitive to pauses. Long leases reduce renewal pressure but delay takeover after a crash. This article does not prescribe a universal duration; the important contract is what happens after any duration expires.

Release is an optimization, not the sole route to progress. A release request must identify the exact lease instance so a delayed release from A cannot release B’s newer lease. Compare the lease ID or fencing token at the coordinator. If release is lost, expiry eventually permits reacquisition. If expiry is unsafe without a release, the object is not functioning as a lease.

Put Fencing at the Protected Resource #

On every successful acquisition, the lock service returns a monotonically increasing fencing token: 41, then 42, then 43. The protected resource maintains highestAccepted for the relevant resource or namespace. A mutation with token $t$ is allowed only if its ordering condition is satisfied. A common rule is:

followed atomically by advancing highestAccepted to $t$ and applying the mutation. Whether equal tokens are accepted depends on the operation. Allowing equality supports retries from the current owner when the operation is idempotent or separately deduplicated. Requiring strictly greater tokens supports one mutation per grant but rejects legitimate multi-step work under one lease. The API must state which model it uses.

After accepting token 42, the resource rejects token 41 forever for that fencing domain. A paused A can resume, but it cannot overwrite B at a resource that enforces this rule. The resource need not consult the lock service on every operation; it needs a durable monotonic high-water mark and an atomic compare-and-apply path.

Tokens must order grants, not clients. A random lease UUID uniquely identifies ownership but cannot tell the resource whether it is older than another UUID. Pairing a unique lease ID with a monotonic fence can serve both purposes: the ID deduplicates coordinator requests, while the fence orders generations.

The scope must match the invariant. If the lock is report/july, a global counter is safe but may be unnecessarily contended; a per-report counter is sufficient if it never resets while stale clients can exist. The resource stores the accepted token in the same scope. Comparing a token issued for one account against the high-water mark of another account has no useful meaning.

Fencing only works when the resource participates. Sending a token in a log field without rejecting stale values is observability, not enforcement. A filesystem API that has no conditional metadata check cannot be fenced directly. Put an enforcing service in front of it, publish through a database row with conditional update, write immutable versioned objects and atomically advance a fenced pointer, or choose a different coordination design.

Work Through a Paused Report Writer #

Return to report july. The lock service and report catalog support the following protocol:

1. A acquires report/july with lease ID a7 and fencing token 41.
2. A renders to immutable object reports/july/a7.tmp, then pauses.
3. A’s lease expires. B acquires lease ID b9, token 42.
4. B renders reports/july/b9.tmp and asks the catalog to publish it with token 42.
5. The catalog atomically sets the visible object to B’s path and records fence 42.
6. A resumes and asks to publish its path with token 41.
7. The catalog rejects A because 41 < 42; A deletes or expires its unused temporary object.

The catalog operation could use a transactional conditional update:

UPDATE report_catalog
SET visible_object = :object_key,
    accepted_fence = :fence,
    published_at = CURRENT_TIMESTAMP
WHERE report_id = :report_id
  AND accepted_fence <= :fence;

The application checks that exactly one row was updated. For multiple publishes under one lease, equality is allowed, and each request also carries an idempotency key or expected catalog version so reordered same-token requests cannot move the pointer backward. If exactly one publish is permitted per grant, the predicate can require accepted_fence < :fence.

Notice what is fenced: the small catalog pointer that makes an immutable object visible. Ordinary object storage may not offer a convenient numeric fence comparison, so immutable writes are harmless until the catalog publishes one. The protected transition and the high-water mark share one database transaction.

Deleting the previous object is a separate operation and should not be performed eagerly by the current lease holder. A delayed delete from an old owner could remove a newly referenced key if names are reused. Immutable unique keys plus asynchronous garbage collection avoid that hazard. The collector reads catalog reachability and applies its own retention safeguards.

If A had written directly to a fixed object key before consulting the catalog, fencing the pointer would be too late: the bytes behind B’s pointer could already be overwritten. The architecture must route every harmful mutation through a resource that compares the token, or make unfenced writes immutable and non-visible.

Require a Monotonic Grant Authority #

A fencing token is only as strong as its issuer. Successful acquisitions for one lock must form a single monotonic sequence. Two coordinator leaders must not independently issue token 42 to different clients, and a restored coordinator must not return to 17 after resources have accepted 900.

A common implementation stores lock state and the next token in a linearizable replicated state machine or a database transaction with compare-and-set semantics. Acquisition checks whether the current lease is absent or expired, advances the generation, records the new lease, and returns the generation as the fence. Renewal preserves the same token because it extends one ownership generation; reacquisition creates a greater token.

Quorum language alone is not a proof. A majority protocol needs a defined membership, leader term rules, durable logs, and protection against two disjoint configurations each believing they have authority. Dynamic membership changes must overlap safely. If the lock service uses a database, its isolation and failover behavior must preserve the atomic acquisition invariant. “Three nodes” says nothing about these details.

Coordinator availability and protected-resource availability are separate. During a partition, the lock service may refuse new grants because it lacks a quorum. That sacrifices availability to avoid conflicting token sequences. An existing client may still reach the resource; its token remains subject to the resource’s high-water mark and application policy. If the system instead allows each partition to issue grants, fencing tokens from those partitions need a shared ordering authority at the resource or they are incomparable and unsafe.

Persist token state across backup and restore. Restoring only the lock table from an old snapshot can reuse values lower than high-water marks already stored elsewhere, causing every new owner to be rejected or, worse, accepted by resources whose own state was also inconsistently restored. Recovery procedures must restore a consistent fencing epoch or allocate a new epoch ordered above all previous ones. A composite (epoch, counter) can work if epochs themselves come from a monotonic authority and compare lexicographically.

Design the Client Protocol Around the Fence #

The client should treat acquisition as returning a capability with four fields: lock scope, lease ID, fencing token, and conservative validity deadline. Protected APIs require the scope and token explicitly. Hiding the token in ambient thread-local state makes it easy for asynchronous work to lose or reuse the wrong capability.

Before expensive work, check whether enough lease time remains to make progress, but regard that as an efficiency check. Before every protected mutation, send the token. If the resource reports stale_fence, stop immediately, discard unpublished output, and do not retry under the same grant. Reacquiring produces a new generation and usually requires recomputing from current state.

Renew using a conditional operation on the exact lease ID and token. A renewal response that arrives after local uncertainty should not resurrect work the client already abandoned unless the protocol carefully defines that transition. It is often simpler for a client that considers its lease lost to stay lost, even if a late response says the coordinator extended it.

Cancellation and lease loss do not automatically undo side effects. Design work as prepare then fenced commit when possible. Computation and immutable staging happen before the protected transition; a small conditional operation publishes the result. For database mutations, include the fence in the same transaction as the domain update. For an external device or legacy API that cannot compare tokens, fencing cannot supply the guarantee directly.

Use explicit result types. Acquisition can return acquired, busy, or unavailable. A protected write can return applied, duplicate, stale_fence, or a transient resource error. Conflating stale ownership with network failure encourages dangerous retries. A stale result is definitive evidence that a newer generation reached that resource.

Know the Limits and Failure Modes #

Fencing does not make a multi-resource operation atomic. If a lease holder updates database X with token 42 and sends email through service Y, both must understand the generation for stale-owner safety, and even then they may not commit together. Use an outbox, idempotent workflow, or transaction protocol appropriate to the cross-resource invariant. A token checked by only one destination leaves the others exposed.

Tokens also do not repair non-idempotent same-owner retries. If token 42 increments a balance twice after a timeout, the fence sees the same current owner and may permit both calls. Add an operation ID, expected version, or domain-specific deduplication. Fencing orders ownership generations; idempotency distinguishes attempts within one generation.

Common failures include:

• Issuing random lock IDs without a monotonic fence.
• Generating counters independently on several coordinator nodes.
• Resetting counters after restore, reconfiguration, or integer overflow.
• Checking a token in application code, then performing an unconditional write in a separate step.
• Fencing metadata while allowing another path to mutate the protected object directly.
• Allowing old and new software versions to disagree about token scope or comparison.
• Treating a successful renewal request as committed before receiving an authoritative response.
• Assuming process termination or lease expiry cancels requests already in transit.

There is also a product tradeoff. Fencing rejects stale work, but the rejected computation may have consumed substantial resources. Shorter tasks, periodic validity checks, cooperative cancellation, and staged work reduce waste; none replaces final enforcement. If stale computations are frequent, investigate pauses, renewal latency, and lease duration rather than weakening the fence.

Sometimes an operation is naturally commutative or conditional on current state and needs no lock. An atomic insert-if-absent, compare-and-set version update, append-only record, or conflict-free merge can encode the invariant directly. Prefer the smallest primitive the resource can enforce. A distributed lease plus fencing is appropriate when work needs temporary coordination and stale generations can be ordered at commit.

Test and Operate the Safety Invariant #

The decisive test pauses an owner beyond expiry. Acquire token 41, block A immediately before publish, advance the coordinator clock or let the test lease expire, acquire token 42, publish B, then release A. Assert B remains visible and A receives stale_fence. Do not implement this test with hopeful sleeps; expose barriers and a fake coordinator clock so the interleaving is deterministic.

Repeat the scenario with a delayed network request rather than a paused thread. Deliver A’s token-41 mutation after token 42. Duplicate current-token requests to verify idempotency behavior. Reorder two same-token operations to check expected-version rules. Crash between writing immutable output and fenced publication, then verify recovery cleans staging without exposing it.

Test the authority under leader changes, coordinator partitions, renewal races, and membership transitions. Assert every successful new acquisition has a token greater than all prior successful acquisitions for the scope. Restore from backup in an isolated environment and prove the next epoch compares above tokens retained by protected resources. Exercise rolling upgrades where old and new clients coexist.

At each protected resource, record accepted fence, rejected stale fence, scope, operation type, and lease-service epoch with bounded-cardinality labels. Alert on any stale rejection because it proves an expiry race occurred; occasional rejection may be expected safety behavior, while a spike signals pauses, renewal failures, or misrouted delayed traffic. Monitor acquisition latency, renewal success, lease age, holder loss, coordinator quorum, clock health if leases depend on it, and token exhaustion.

Audit APIs to ensure no unfenced mutation path exists. Database permissions can force writes through stored procedures or services that compare the fence. Contract tests can reject clients that omit the token. Runbooks should explain that manually clearing a lock does not revoke the old process; operators must rely on a newer fence at the resource or stop the stale actor before using an unfenced destination.

The durable model is compact. Leases decide who may begin and let the system recover liveness after holders disappear. They cannot erase delayed work. Monotonic fencing tokens order ownership generations, and protected resources turn that order into safety by atomically rejecting stale mutations. The lock service grants authority, but the destination enforces it. Designing both halves together is what makes expiry survivable rather than merely convenient.