Fencing tokens: why a lease can't stop a paused writer
A fencing token does what a lease cannot: with the check in the write, a paused holder changed 0 rows. Without it, that holder overwrote a newer index build.
This log comes from a small program we ran against PostgreSQL. Two publishers compete for a lease that lets one of them point a search alias at the newest index build. The pause is a timer standing in for whatever really stops a process.
t= 0.1s publisher-a acquired lease, token 1, ttl 2s
t= 0.1s publisher-a paused
t= 2.3s publisher-a lease expired while paused
t= 2.3s publisher-b acquired lease, token 2, ttl 2s
t= 2.3s publisher-b set products -> build-0412
t= 3.1s publisher-a resumed, believes it holds the lease
t= 3.1s publisher-a set products -> build-0411 (1 row)
t= 3.1s alias now: build-0411The lease service never granted two live leases, and production search is now serving the older build with no error anywhere. The lock protected the right to start working, and the damage happened at the moment of finishing.
Checking the lease right before the write looks like the obvious repair:
var lease = await locks.AcquireAsync("index-publisher", TimeSpan.FromSeconds(30));
var build = await BuildIndexAsync(cancellationToken);
if (lease.ExpiresAt > timeProvider.GetUtcNow())
{
// A pause can begin here, after the check and before the write.
await search.SetAliasAsync("products", build, cancellationToken);
}That narrows the window and leaves it open. Martin Kleppmann's
analysis of distributed locking
lists what can stop a process at any instruction: stop-the-world garbage collection, a page fault
waiting on disk, CPU contention, a stray SIGSTOP. The request can also leave on time and then wait
in the network, which no check inside the client can see. Renewing more often and shortening the TTL
change the odds without changing the outcome, since any pause longer than the remaining lease has
the same result.
etcd's documentation says "the lock APIs cannot be used as mutual exclusion mechanism by themselves", because owning a lease cannot guarantee the owner still holds the lock of the resource.
A fencing token is a number from the lock service that goes up every time the lock changes hands. The holder sends it with every write. The resource remembers the highest token it has accepted and refuses anything lower. Google's Chubby paper describes the same idea as a sequencer: the holder passes it to servers such as file servers, and the recipient "is expected to test whether the sequencer is still valid" and reject the request if not.
The whole mechanism can be one SQL statement. The fence goes in the row it guards:
CREATE TABLE index_alias (
alias text PRIMARY KEY,
target text NOT NULL,
fence bigint NOT NULL
);
UPDATE index_alias
SET target = $1, fence = $2
WHERE alias = 'products'
AND fence <= $2;One affected row means accepted. Zero means a newer holder got there first, and the caller should stop rather than retry. The same scenario with that statement in place:
t= 0.0s publisher-a acquired lease, token 1, ttl 2s
t= 0.0s publisher-a paused
t= 2.2s publisher-b acquired lease, token 2, ttl 2s
t= 2.2s publisher-b publish build-0412 with token 2: accepted
t= 3.0s publisher-a resumed, believes it holds the lease
t= 3.0s publisher-a publish build-0411 with token 1: rejected
t= 3.0s alias now: build-0412Same pause, same late write: with
fence <= $2in theUPDATE, token 1 changed 0 rows and the alias stayed on build-0412.
The check that counts runs at the resource
- 0.0 s publisher-a acquires the lease, token 1, then pauses
- 2.0 s lease service expires the lease while publisher-a is frozen
- 2.2 s publisher-b acquires the lease, token 2, publishes build-0412 accepted, fence is now 2
- 3.0 s publisher-a resumes and publishes build-0411 with token 1 rejected, 1 is below 2
Lease only, no check at the resource
products -> build-0411
The older build wins because it arrived last.
Lease plus fencing token
products -> build-0412
The stale writer changes nothing, however late it arrives.
The comparison is <= rather than < so the current holder can write more than once with the same
token. Nothing here depends on how long the pause lasted or whether any clock was accurate, which is
the property a TTL alone can never give you.
The number must never repeat or go backwards, including across a failure of the lock service. For a single lease row in PostgreSQL, acquisition can bump it in one statement:
INSERT INTO leases AS l (name, holder, token, expires_at)
VALUES ('index-publisher', $1, 1, now() + $2)
ON CONFLICT (name) DO UPDATE
SET holder = excluded.holder,
token = l.token + 1,
expires_at = excluded.expires_at
WHERE l.expires_at <= now()
RETURNING token;A live lease makes the WHERE false, so RETURNING yields nothing and the caller knows it lost.
Durability here is the database's, including what a failover does to it.
Coordination services expose the same thing as a built-in. etcd's documentation treats its revision
number as the fencing token, and Kleppmann points to ZooKeeper's zxid or znode version. A plain
counter on an asynchronously replicated store is the trap, because a failover can lose the latest
increments and hand out a number that was already used. His post also notes that Redlock has no
facility for generating tokens: its random value is not monotonic, and a counter on one node dies
with that node.
A token only helps if the receiving end does its part, and most of the mistakes are here.
Compare and write in one atomic step. We raced two writers with adjacent tokens for 2,000 rounds
on a table of the same shape. Running SELECT fence and then UPDATE as separate statements let the lower token
win 790 rounds. The single UPDATE above let it win 0. In READ COMMITTED, a waiting UPDATE
re-evaluates its WHERE clause
against the updated row once the lock is released, so the second writer sees the new fence.
Store the fence with the data. If the high-water mark is kept in memory or in a separate store, a crash or a partial write can leave data and fence disagreeing. In the same row or the same transaction they cannot.
Survive storage failover. If the store fails over to a replica that was behind, it may have lost both the write from token 2 and the record of having seen it, and token 1 becomes acceptable again. Replication lag and failover sets how much can vanish.
Leave no second path. A fence on the application's UPDATE does nothing for the admin script or
batch importer writing the same table with its own credentials. Every write path has to cross the
check, which argues for enforcing it as close to the storage as you can.
Keep the fence through deletes. If deleting the row deletes the fence, a stale holder's insert recreates the row and is accepted. Keep a tombstone, or keep the fence in a separate per-resource row that outlives the data.
Scope it to one resource. A token from lease A means nothing to resource B. One lease can guard several resources, but each must track its own high-water mark, and a job that writes to two of them can still finish on one and be rejected on the other, so the sequence needs a recovery plan.
Plenty of targets have no place to put a number: a payment provider, an email gateway, a third-party API. You have three partial answers. Put a small service in front that holds the fence and is the only route to the target. Make the operation idempotent with a key tied to the work, so the second attempt is harmless, as in idempotency in API design. Or wait. Chubby's lock-delay stops anyone else from claiming a lock for a period after its holder disappears, up to one minute, and the paper calls this "imperfect" while noting that it protects servers that cannot check sequencers from everyday delays.
Nothing above needs a real pause to test. Give the lease explicit times or a fake clock, as TimeProvider testing shows, and assert on the sequence: acquire, expire, reacquire, then write with the old token and expect a refusal. A test that sleeps for the TTL is slow, and on a loaded machine it can pass or fail on timing alone.
The worker in this post held valid credentials and a stale view, and nothing at the target stopped it. A System Design challenge in the Recover a Data Platform series starts from that situation, and a unit testing exercise has you write the suite for a lease allocator using integer times, where your tests have to catch hidden mutants.
Practice what you just read
- Open in the editor: Test Fenced Lease Ownership
Test writing Hard Free, no account needed
Test Fenced Lease Ownership
Exercise expiry, renewal, ownership transfer, and stale-token rejection in a lease that must never reuse authority.
- Open the Pro kata: Fence the Retired Writer
System Design Studio Hard Katabench Pro
Fence the Retired Writer
An old process wakes after cutover and overwrites recovered data. Enforce shared ownership epochs at the target.
More like this: C# unit testing exercises →