Fencing Tokens: Why a Lock Is Advisory Until the Resource Checks It

A lock service can tell a client that it holds a lock. It cannot make the client hold the lock, and it cannot stop a client that believed it held the lock from issuing a request to the resource the lock was meant to protect. Between the service’s decision and the resource’s observation of that decision there is a network, a scheduler, and a client process, and any of them can delay the observation past the point where the decision was reversed. The lock is therefore a suggestion unless the resource itself enforces the ordering.

The window that leases cannot close

Consider a client holding a lock with a lease. The client pauses: garbage collection, a hypervisor descheduling it, a page fault on a swapped-out heap. The lease expires while the client is not running. The service grants the lock to a second client, which acquires it, reads the current state of the resource, and begins writing. The first client wakes, still believing it holds the lock, and writes to the same resource based on a state it read before the pause.

Nothing in the lease mechanism prevents the second write. The lease bounded how long the first client’s belief was supposed to remain valid, but the client was not running to observe its own deadline, and the service’s expiry is not visible to the resource. The resource receives two writes and has no way to tell which one came from the current holder, because both requests look alike: same endpoint, same credentials, same payload shape.

Reducing the lease duration does not fix this. It shortens the window but does not eliminate it, and every pause longer than the lease recreates it. Making the client check its deadline before each write does not fix it either, because the check and the write are separated by an interval in which the client can be descheduled again. The only place the check can be made reliable is at the resource, in the same atomic step as the write, and that requires the resource to know something about the grant that the client cannot forge or replay.

The token as a version of the grant

The mechanism is to attach a value to each grant that is monotonically increasing across grants of the same lock, and to require every request from the holder to carry it. The service assigns the value at the moment it grants the lock, from a counter that only ever increases. The first holder receives 31, the next 32, the next 33. The resource keeps the highest value it has accepted, and it rejects any request carrying a value below or equal to that maximum.

The first client in the scenario above holds 31. The second holds 32 and writes first, moving the resource’s accepted maximum to 32. When the first client wakes and writes with 31, the resource compares 31 against 32 and refuses. The stale write does not land, and the invariant that only one client’s writes are applied at a time is preserved by the resource rather than by the lock service. This is what Chubby calls a sequencer: an opaque byte string that the lock service generates and that the client must pass to the resource, whose cooperation is required for the guarantee.

// The resource, not the lock service, enforces the order. The check and the
// mutation happen under one lock, so a rejected token cannot race a write.
type Guarded struct {
	mu       sync.Mutex
	accepted uint64
	data     []byte
}

func (g *Guarded) Write(token uint64, p []byte) error {
	g.mu.Lock()
	defer g.mu.Unlock()
	if token <= g.accepted {
		return ErrStaleToken // the grant this token came from is superseded
	}
	g.accepted = token
	g.data = append(g.data[:0], p...)
	return nil
}

The token need not encode anything. It need not be a timestamp, need not be verifiable by the resource, and need not be secret. Its only requirements are that it increases across successive grants and that a client cannot obtain a higher one without the service granting it. A counter held by the service satisfies both. A timestamp would fail the first requirement if the service’s clock stepped backwards, which is one reason tokens are counters rather than times.

Where the check has to live

The token is only useful if the resource performs the comparison atomically with the mutation. A resource that validates the token, then performs a write in a separate step, has reintroduced the window: two requests can both validate against the same accepted maximum before either updates it. The comparison and the update must be one operation, which in a single-process resource means a mutex or a compare-and-swap around both, and in a database means the token check must be part of the same transaction or the same conditional update as the write.

For a storage system that supports conditional writes, the natural encoding is to store the accepted token alongside the data and make every write conditional on the stored token being below the presented one. That makes the check a property of the data rather than of a separate authorization layer, and it survives restarts of the resource because the accepted maximum is durable. A resource that keeps the maximum only in memory resets it on restart, and a client holding an old token can then write successfully after the restart, which is the same failure the token was meant to prevent.

There is a subtlety about scope. A single counter per lock protects one resource. A resource shared by several locks needs either one counter per resource or a counter that is global across all grants, and the latter serializes grants that need not be serialized. The usual arrangement is one lock per resource, with the token’s scope matching the lock’s scope, so that a token is only ever compared against tokens for the same protected object.

The cost is cooperation from the resource

The token requires every writer to the resource to participate. A storage system that accepts writes from an authenticated client without a token cannot be protected by one, and adding the check means changing every write path, every client, and every stored record. That is the reason fencing is often described as advisory: the lock service can issue tokens all day, but a resource that ignores them is unprotected, and no amount of correctness in the lock service changes that.

The cost also shows up in the protocol’s shape. Every write must carry the token, which means the token has to be threaded through whatever layer issues writes, including retries and queued work. A retry that reuses an old token after the grant has changed is rejected, which is the intended behaviour, but a system that batches writes and sends them later must decide what to do with a batch whose token has been superseded: discard it, re-acquire, and recompute, which may duplicate work. Idempotency keys and per-batch tokens are the usual answers.

There is a related cost in observability. A resource that rejects stale tokens is doing its job, and the rejection looks like an error in the client’s logs. Distinguishing “the lock was superseded while I was paused” from “the lock service is broken” requires the rejection to carry enough information for the client to re-read the grant state, which is a small protocol of its own.

Tokens and the queue

A queue-based lock has a natural token already: the sequence number of the ticket that made the client the holder. The client that created the lowest node has a number lower than every other waiter’s, and the next holder’s number is higher. Using that number as the token gives the ordering for free, with one caveat: sequence numbers are assigned per path, so two different locks have interleaved numbers, and a token from one lock is meaningless for the other. The token’s scope must be the lock path, and the resource must be protected by exactly one lock path.

The other caveat is reuse. If a queue path is deleted and recreated, the counter may restart, and a token from the old incarnation can exceed a token from the new one. Services that persist sequence counters across path deletion avoid this; services that reset them require the resource to be reset as well, or require the lock path to include a generation identifier that changes when the path is recreated. The generation is the same idea as the version number in conditional writes, applied to the lock itself rather than to the data.

What remains outside the token

The token orders writes to one resource. It does not order the client’s reads, and a stale client can still read the resource and make decisions based on a state that has moved on. It does not protect side effects outside the resource, such as messages sent to a queue or files written to a shared volume, unless those systems also check a token. And it does not help when the client’s write is not a single request but a sequence of requests that must be applied as a unit; the unit needs the token checked once, at its start, and the resource must hold the guard for the duration.

The general shape is that the lock service orders grants and the resource orders effects, and the token is the object that carries the first ordering into the second. A system that has only the first is coordinating intentions, not actions, and the gap between intention and action is where the interesting failures live.