Fencing Tokens and the Arithmetic of Lease Expiry

A failover that promotes a standby while the old primary is still running produces two nodes that both believe they are primary. The network partition that caused the failover is usually asymmetric: the standby cannot reach the old primary, but the old primary may still be reachable by some clients, and it may still be executing writes. Stopping this requires more than a decision to promote. It requires a mechanism that makes the old primary’s writes ineffective, and the two standard mechanisms — lease expiry and fencing tokens — have different timing properties and different failure modes.

The split-brain window

The window exists because failure detection is a local observation. Node B concludes that node A is dead because B’s probes to A time out. That conclusion is about the path from B to A, not about A’s liveness. A can be running, healthy, and serving clients whose path to A is intact. This is the classic distinction between a failure and a suspicion of failure, and every consensus system is built around the fact that suspicion is all a node can have.

The danger is not that both nodes accept writes for a long time. It is that both accept writes for a short time, because a short overlap is enough to diverge. Two writes to the same record, one on each side, produce two versions with no ordering between them. When the partition heals, one must be discarded — and the client whose write was acknowledged and then discarded has been lied to. Conflict resolution for two-region writes describes what to do with the divergence, but the point of fencing is to prevent the divergence rather than reconcile it.

Leases bound how long a stale primary may act

A lease is a time-bounded grant. The old primary holds a lease on the primary role, valid until a known expiry time. The new primary may take over only after that expiry has certainly passed. The correctness argument is a timing one: if the lease duration is L, the old primary’s clock advances at most at some rate, and the grant is made at a time known to both sides, then after L plus a margin the old primary must stop acting, regardless of whether it has heard anything.

The margin has to cover clock drift. If the lease is measured on the old primary’s clock and the drift rate is bounded by ρ, then a lease of nominal duration L may appear to the old primary to last as long as L / (1 - ρ) in real time. A drift bound of 100 parts per million — generous for a disciplined clock, plausible for an undisciplined one — extends a 10-second lease by about 1 millisecond. Small, but it must be in the arithmetic rather than assumed away.

The margin must also cover the delay in delivering the grant. The new primary cannot know the exact instant the old primary received its lease; it only knows when the lease was issued. So the wait is:

wait = L + (max delivery delay) + (clock drift allowance)

Every term is a bound, not an estimate. If the delivery delay is unbounded, the wait is unbounded and the mechanism does not work. This is why leases are only sound in systems with bounded message delay or with an explicit acknowledgment that the lease was received: an unacknowledged lease grant is a lease whose start time is unknown.

Why the wait is not optional

The temptation is to skip the wait when the old primary appears unreachable. That is precisely the case in which the wait matters. The new primary cannot distinguish “old primary is down” from “old primary is up but the path to it is broken”, and the second case is the one where skipping the wait causes two writers.

A system that promotes immediately on suspicion has a split-brain window equal to the time until the old primary learns it has lost the role — which may be never, if it is partitioned and its clients are not. A system that waits out the lease has a window of zero, at the cost of extending the failover time by the lease duration. The lease duration is therefore a direct trade against the recovery time objective, and it belongs in the failover time budget as an explicit term rather than a constant buried in configuration.

Shortening the lease reduces the wait and increases the chance of spurious expiry: a lease that expires during a brief pause (a long garbage collection cycle, a hypervisor stall, a scheduling delay) causes the holder to lose the role while it is still healthy. The holder must then stop acting immediately when it notices the expiry, and any operation it performs between the expiry instant and the moment it notices is unsynchronized. That is the reason a lease holder must check the clock before each write, not just periodically.

Fencing tokens make stale writes rejectable

The second mechanism does not depend on time at all. Each time a node is granted the primary role, it receives a token from a monotonically increasing sequence. Every write the primary sends to the storage layer carries the token. The storage layer remembers the highest token it has seen and rejects any write carrying a lower one.

grant 1 -> primary A, token 33
partition
grant 2 -> primary B, token 34
B writes with token 34        -> accepted, storage high-water mark = 34
A writes with token 33        -> rejected (33 < 34)

The old primary’s write is refused by the resource it is trying to modify, so the divergence never happens. No clock, no lease duration, no waiting for expiry. The old primary discovers it is stale on its next write, and it can then step down.

The requirement is that the token check happens at the resource being modified, or at a layer that the write cannot bypass. A token checked by a proxy in front of the storage is useless if the old primary can reach the storage by another path — which is exactly the situation in a partition where routing has changed. The check must be at the last point before the write becomes durable.

Fencing is stronger than leases and cheaper in latency, and it has a cost of its own: the storage layer must implement the check, which means the storage layer must know about roles and tokens. Many storage systems do not, and adding the check to an existing system is a change to the data path rather than a configuration. Where the storage layer cannot be changed, the token can be checked by a component that every write must traverse and that cannot be bypassed — a load balancer that terminates the connection, for example, with the backend reachable only through it. That works if the network enforces the path, which is a stronger assumption than it sounds.

Combined use and the common mistake

Leases and fencing are complementary. Fencing protects against a stale writer that is still able to reach storage; leases protect against a stale reader that is still serving results, and bound the time a client’s cached view of leadership remains valid. A system with fencing but no lease can have a stale primary that serves reads from its own state and only learns it is stale when it attempts a write. A system with leases but no fencing is protected only up to the accuracy of its clock bounds and the boundedness of its message delays.

The common mistake is applying the token at the wrong granularity. A token that guards writes to the primary record but not to the index, the cache invalidation stream, or the outbox table leaves those paths open. A stale primary that cannot write the record but can still enqueue an outbox event has effectively written, because the event will be applied downstream. Every path by which a write becomes visible must be guarded, and enumerating those paths is the actual work of fencing a system.

A second mistake is a token sequence that can go backwards. If tokens are stored per-region and generated locally, two regions can issue the same number, and the storage layer’s high-water comparison then rejects the legitimate new primary. The sequence must be issued by a single authority — the consensus group that grants the role — and it must be durable, because a restart that resets the counter reissues tokens that have already been used.

What a client sees during the transition

Clients are the third party in this protocol and the one most often neglected. A client that has a connection to the old primary may keep sending writes after the new primary is active. Fencing makes those writes fail, but the client’s retry logic may then send the same write to the new primary, where it may or may not be a duplicate.

The standard mitigation is an idempotency key attached to the client’s request, stored with the write and checked by the new primary. Without it, a retried write after a failover can apply twice — a double charge, a double shipment, a duplicated record. With it, the retry is recognized and the original result returned. The key must be generated by the client before the first attempt, not by the server, or the retry carries a different key and the duplicate is invisible.

A client that caches the primary’s address has a similar problem: after the failover, the cached address points at a node that is now fenced, and every write fails until the client re-resolves. DNS failover and the resolver caching bound covers how long that can last. The design consequence is that write failures during a transition should be retryable errors with a clear indication to re-resolve, not generic 500s that a client library treats as transient without changing its target.

Where the guarantees stop

Neither mechanism protects against a storage layer that loses its high-water mark. If the record of the highest token is itself lost in a failure — a cache-only implementation, or a store restored from a backup taken before the last grant — then the stale primary’s writes become acceptable again. The high-water mark must be as durable as the data it guards, and it must be replicated with the same consistency as the data.

Neither protects against a token that is reused after a full system rebuild. If the entire cluster is destroyed and restored from backup, the token sequence may restart below values that clients and storage have seen. The recovery procedure must establish a new epoch, either by seeding the sequence above any previously issued value or by changing a deployment identifier that is part of the token comparison. This is the same problem as a Raft term being reused, and it is solved the same way: make the epoch part of the identity, not a side effect of a counter.

The residual risk after both mechanisms is a storage layer that accepts a write from a fenced primary through a path nobody thought to guard. That is not a timing problem and no amount of waiting fixes it. It is an enumeration problem, and the only reliable way to close it is to make the guard mandatory at the storage interface rather than optional at each caller.