Using Fencing Tokens to Survive Lock Expiry

A lease says “you hold this lock for 30 seconds”. It cannot say “you will still be running in 30 seconds”, and that gap is where distributed locks corrupt data. A fencing token closes it by making the resource — not the lock service, and certainly not the client — the final authority on which writer is current. This runbook implements the mechanism described in clock skew & time ordering in distributed systems.

Prerequisites. A working distributed lock — see distributed lock acquisition patterns — and write access to the schema of the resource it protects.

Step 1 — Issue a monotonic token with every grant

The token must increase strictly across grants, and it must come from the same operation that grants the lock.

Where a trustworthy token comes from Three token sources. An etcd revision and a ZooKeeper transaction id are both produced by a consensus log, so a new leader already holds them and they never regress. A Redis counter increments on one shard only, so an asynchronous failover can reissue a value that was already handed out. etcd revision from the Raft log never regresses ZooKeeper zxid from the atomic broadcast never regresses Redis INCR one shard, async replication can reissue a used value 
-- acquire_with_fence.lua
-- KEYS[1] = lock key   KEYS[2] = fence counter (same hash tag as KEYS[1])
-- ARGV[1] = holder id  ARGV[2] = lease ms
-- Returns: token (integer) on success, 0 if the lock is held
if redis.call('SET', KEYS[1], ARGV[1], 'NX', 'PX', tonumber(ARGV[2])) then
  return redis.call('INCR', KEYS[2])          -- monotonic within this shard
end
return 0
// etcd: the revision of the successful Put is already strictly monotonic
// across the whole cluster, produced by Raft rather than by a counter.
resp, err := cli.Txn(ctx).
    If(clientv3.Compare(clientv3.CreateRevision(lockKey), "=", 0)).
    Then(clientv3.OpPut(lockKey, holderID, clientv3.WithLease(leaseID))).
    Commit()
if err != nil || !resp.Succeeded { return 0, ErrLockHeld }
token := resp.Header.Revision            // the fencing token — no counter needed

etcd and ZooKeeper give you this for free: etcd’s Revision and ZooKeeper’s zxid are strictly monotonic by construction because they come out of a consensus log. Redis’s INCR is monotonic on one shard but can regress across an asynchronous failover, which is the reason Redlock alone is not sufficient for a safety-critical fence.

Step 2 — Carry the token to the write

@dataclass(frozen=True)
class Lease:
    resource: str
    holder: str
    token: int          # never optional — a Lease without a token is not a lease

def with_lock(resource: str, fn):
    lease = lock_service.acquire(resource, lease_ms=30_000)
    try:
        return fn(lease)            # fn MUST thread lease.token into every write
    finally:
        lock_service.release(lease)

Make the token a required parameter on every function the lock protects. A signature that accepts an optional token is one refactor away from a call site that forgets it, and the failure is silent until the day a worker pauses.

Step 3 — Enforce at the resource

Client-side check versus resource-side fence Two panels. On the left, a frozen worker checks its own token against its own cached lease, concludes it still holds the lock, and writes successfully, corrupting the balance. On the right, the same worker sends its write with token thirty-three to the database, whose row already records token thirty-four, so the WHERE clause matches zero rows and nothing changes. Client-side check — useless frozen worker, token 33 if (myLease.valid()) { write() } it checks its OWN cached lease which is exactly what is wrong write succeeds balance corrupted, no error Resource-side fence — correct UPDATE … WHERE fence_token < 33 row already records token 34 the database compares, not the client no clock is consulted anywhere 0 rows updated stale write rejected, state intact 
-- The fence lives in the WHERE clause of the write itself. One statement,
-- no read-then-write, no clock.
UPDATE account_balances
   SET balance     = balance - :amount,
       fence_token = :token
 WHERE account_id  = :account
   AND fence_token < :token
RETURNING balance;
-- Zero rows returned = a newer holder has already written. Abort, do not retry.
def debit(conn, account: str, amount: int, lease: Lease) -> int:
    row = conn.execute(DEBIT_SQL,
                       {"amount": amount, "token": lease.token, "account": account}
                       ).fetchone()
    if row is None:
        metrics.inc("lock_fence_rejected_total")
        raise StaleLeaseError(f"token {lease.token} superseded on {account}")
    return row.balance

For DynamoDB the same idea is a condition expression:

table.update_item(
    Key={"pk": account},
    UpdateExpression="SET balance = balance - :amt, fence_token = :tok",
    ConditionExpression="attribute_not_exists(fence_token) OR fence_token < :tok",
    ExpressionAttributeValues={":amt": amount, ":tok": token},
)

And for an S3-style object store, use a conditional write on an ETag, or encode the token in the object key so a stale writer simply produces a version nobody reads.

Step 4 — Migrate an existing table

-- 1. Add the column, nullable, with no default rewrite.
ALTER TABLE account_balances ADD COLUMN fence_token bigint;

-- 2. Backfill in bounded batches so no long lock is taken.
UPDATE account_balances SET fence_token = 0
 WHERE fence_token IS NULL AND account_id IN (
   SELECT account_id FROM account_balances WHERE fence_token IS NULL LIMIT 10000);

-- 3. Once backfilled, make it mandatory.
ALTER TABLE account_balances ALTER COLUMN fence_token SET NOT NULL;
ALTER TABLE account_balances ALTER COLUMN fence_token SET DEFAULT 0;

During step 2, writers must tolerate NULL:

-- Transitional predicate: accepts rows not yet backfilled.
WHERE account_id = :account AND (fence_token IS NULL OR fence_token < :token)

Remove the IS NULL branch as soon as the backfill completes. Leaving it means any row that somehow loses its token becomes permanently unfenced.

Step 5 — Prove it

def test_frozen_worker_cannot_write(db, lock_service):
    account = "acct_fence_probe"
    lease_a = lock_service.acquire(account, lease_ms=1_000)     # token N

    time.sleep(1.5)                                             # lease A expires
    lease_b = lock_service.acquire(account, lease_ms=30_000)    # token N+1
    debit(db, account, 100, lease_b)                            # B writes first

    with pytest.raises(StaleLeaseError):
        debit(db, account, 100, lease_a)                        # A wakes and tries

    assert db.scalar("SELECT balance FROM account_balances WHERE account_id=:a",
                     a=account) == INITIAL - 100                # exactly one debit
# The real-world version: freeze a worker with SIGSTOP past its lease.
kill -STOP "$(pgrep -f settlement-worker)"
sleep 45                                    # lease (30 s) expires; a peer takes over
kill -CONT "$(pgrep -f settlement-worker)"
sleep 5

psql -c "SELECT account_id, balance, fence_token FROM account_balances
          WHERE account_id = 'acct_fence_probe'"
# expect: exactly one debit applied, fence_token equal to the newer holder's token
grep -c 'lock_fence_rejected' worker.log    # expect: at least 1

A non-zero lock_fence_rejected_total in production is good news. It means workers really do freeze past their leases and the fence is catching it — which also means that before you added the fence, those were silent corruptions.

Failure scenarios and debugging

Failure Scenario Remediation Steps Observability Hooks
Token checked in application code before the write rather than in the write’s WHERE clause Move the comparison into the same statement as the update. A separate read-then-write reintroduces the race the fence exists to remove. lock_fence_rejected_total flat at zero while lease_expired_while_held_total is non-zero — the fence is not firing
Redis-issued tokens regress after a failover, so a new holder receives a token lower than one already written Move token issuance to etcd or ZooKeeper, whose revisions come from consensus. If Redis must stay, persist the counter’s high-water mark and restore it on promotion. lock_token_regression_total from a monitor comparing issued tokens against the last observed maximum; page on any value
One resource protected by two lock services (a migration left both running), each with its own counter Never run two token sources for one resource. Migrate by having the new service seed its counter above the old one’s maximum, then decommissioning the old path. lock_service label on the fence-rejection counter; two distinct values for one resource is the signature
Backfill left some rows NULL, and the transitional IS NULL predicate was never removed, so those rows stay unfenced forever Complete the backfill, set NOT NULL, and remove the transitional branch in the same release. SELECT count(*) FROM account_balances WHERE fence_token IS NULL as a gauge; must be zero
Fence added to the balance table but not to an audit or projection table written by the same handler Fence every table the lock protects, or write them all in one transaction so the fenced statement gates the whole unit. A schema audit listing tables written under each lock and whether they carry fence_token
Enforcing the fence in three storage types Three enforcement forms. In SQL the fence is a where clause comparing the stored token to the presented one. In DynamoDB it is a condition expression on the same comparison. In an object store there is no conditional write, so the token is encoded into the object key and a stale writer simply produces a version nobody reads. SQL AND fence_token < :tok 0 rows = superseded DynamoDB ConditionExpression check failure = superseded object store key contains the token stale write lands where nobody reads

SRE / observability checklist

  1. lock_fence_rejected_total — Counter of writes rejected by the fence, labelled by resource. Non-zero proves the fence is earning its place; a sudden rise means workers are freezing more often.
  2. lock_token_regression_total — Counter from a monitor comparing each issued token against the last observed maximum. Any value is a correctness emergency.
  3. lease_expired_while_held_total — Counter from the lock client noticing its lease expired mid-work. Correlate with lock_fence_rejected_total; the two should track each other.
  4. gc_pause_seconds (JVM) or go_gc_pause_seconds — Histogram p99. A p99 approaching the lease duration predicts fence rejections before they happen.
  5. fence_token_null_rows — Gauge of unfenced rows during a migration. Must reach zero and stay there.
  6. fence_token in the write’s structured log — So a rejected write can be traced back to the lease that issued it and the pause that stranded it.