Skip to content
Katabench
Try free
8 min read The Katabench team

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.

Text
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-0411

The 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.

The holder cannot check its way out

Checking the lease right before the write looks like the obvious repair:

C#
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.

Move the decision to 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:

SQL
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:

Text
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-0412

Same pause, same late write: with fence <= $2 in the UPDATE, token 1 changed 0 rows and the alias stayed on build-0412.

The check that counts runs at the resource

  1. 0.0 s publisher-a acquires the lease, token 1, then pauses
  2. 2.0 s lease service expires the lease while publisher-a is frozen
  3. 2.2 s publisher-b acquires the lease, token 2, publishes build-0412 accepted, fence is now 2
  4. 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 lease decides who should write. The token lets the resource refuse whoever should have stopped.

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.

Where the token comes from

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:

SQL
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.

What the storage layer has to do

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.

Resources that cannot check

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.

Testing a fence without sleeping

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

More like this: C# unit testing exercises →

Get new katas and .NET tips in your inbox

A short note when fresh kata land, plus the C# and performance tricks behind the grading. No spam, unsubscribe anytime.