Skip to content

Distributed Leases and Fencing Tokens

A backend service may run ten replicas while only one should reconcile a tenant, rebuild an index, or perform a scheduled transition at a time. A mutex protects threads in one process; it does not coordinate replicas. A distributed lock can coordinate acquisition, but it cannot forcibly stop a process that pauses, loses its network connection, and later resumes.

That distinction is the hard part of distributed coordination. The lock service decides who may start work. The protected resource must still reject work from an owner whose authority has expired.

This chapter focuses on leases, owner identities, fencing tokens, database coordination, Redis locks, and leader election. The cache chapter covers hot-key single-flight; the notification-service design covers queue delivery and worker ownership.

1. Define the invariant before choosing a lock

A lock is a coordination rule that grants exclusive access to a named resource. A lease is an ownership grant with an expiry. A client normally renews the lease while it is working; if it stops renewing, another client may take over. Leader election chooses one coordinator from several candidates, commonly by using a lease or a compare-and-swap record.

Two properties matter:

Property Question Typical mechanism
Safety Can two owners make conflicting changes that the resource accepts? Transactional constraints, row locks, or resource-enforced fencing
Liveness Can another healthy owner eventually take over after a crash or partition? Lease expiry, bounded waits, retries, and recovery

A lease improves liveness because a crashed process does not hold ownership forever. Expiry alone does not prove safety. A process can be paused by a long garbage-collection pause, VM suspension, scheduler starvation, or a network partition. The lease service can expire its record, but it cannot retract a request that the old process already sent.

Start by asking whether a lock is needed at all. If the invariant is “one row per external identifier,” use a unique constraint. If it is “decrement inventory only when enough stock remains,” use one conditional update. If a short database transaction can serialize the operation, use the database. A distributed lock adds another failure boundary and should not replace an invariant the data store can enforce directly.

2. Why expiry creates a stale-owner race

Consider a scheduled reconciliation worker:

  1. Worker A acquires a 30-second lease and starts processing.
  2. A is paused for 45 seconds. Its process has not crashed; it simply stops making progress.
  3. The lease expires. Worker B acquires the same resource and begins reconciliation.
  4. A resumes with its old in-memory state and sends a write.

The lock service sees B as the current owner. A may not know that its lease expired. Cancelling A is useful, but cancellation is cooperative and cannot undo an already-issued database statement or HTTP request.

A random owner token solves a narrower problem. It lets the lock service distinguish A's lease from B's, so A cannot accidentally delete or renew B's lock. It does not stop A from writing to the protected resource.

A fencing token is different: it is a monotonically increasing generation issued on each successful acquisition. A might receive 41 and B later receive 42. Every state-changing request carries its generation. The resource remembers the highest generation it has accepted and rejects older generations.

The token is useful only if the resource enforces it. A lock service that issues token 42 but a storage API that ignores the token has not fenced worker A.

There is one subtle timing detail. A high-water mark rejects token 41 after the resource has observed token 42. If the new owner must be protected immediately at acquisition, install the new generation at the resource before allowing the new owner to start, or make the protected operation validate current ownership atomically with the coordination record. When both records live in one database, a short transaction can do this. Across independent systems, use a resource-native fencing/version check or accept that the lock is only best-effort coordination.

Fencing tokens should be strictly increasing for the resource, not timestamps or random UUIDs. The generator must preserve monotonicity across failover. An asynchronously replicated counter can lose an acknowledged increment during promotion; if that happens, a new owner may receive a token that is not newer than one already observed. Choose a coordination store and durability policy that match the safety requirement.

3. Choose the smallest coordination primitive that works

Database constraints and row locks

For an invariant stored in one relational database, prefer a unique constraint, conditional update, or serializable transaction. PostgreSQL's row locks are appropriate when a short transaction must inspect and change known rows together. Keep the transaction short: do not hold it while calling an HTTP provider, publishing to a broker, waiting for a human, or performing long CPU work.

An application-level lock key can be useful when the resource is not represented by one row. PostgreSQL advisory locks provide this mechanism. Use a transaction-level lock when the protected work is database-only:

BEGIN;

-- All participants must use the same stable key mapping.
SELECT pg_advisory_xact_lock(42001, 17);

-- Perform a short database-only operation.

COMMIT;

The transaction-level lock is released automatically at commit or rollback. Use pg_try_advisory_xact_lock when waiting is not acceptable and the caller should skip or retry later. Advisory locks are cooperative: PostgreSQL does not know the business meaning of the key, so every code path must follow the same convention.

Session-level advisory locks have a different lifetime. They remain attached to the database session until explicitly released or the session ends. That is hazardous when a connection is returned to a pool, and session locks are not compatible with assumptions made by transaction pooling. See the connection-pooling chapter before using session-scoped database state.

Redis leases

A common Redis pattern creates a key only if it does not exist and gives it a TTL, using a unique owner value. Release and renewal must compare that value before changing the key. A plain delete can remove a replacement owner's lock after the original lease expires. The cache chapter shows the compare-and-delete pattern; Redis 8.4 also documents a conditional delete command.

Understand the failure model before treating Redis as a correctness authority. Redis documents a failover race in which a primary accepts a lock, crashes before asynchronously replicating it, and a promoted replica grants the same lock to another client. Redis proposes Redlock using independent masters, while its own consistency notes still recommend fencing tokens for long-running work and warn about wall-clock shifts. Martin Kleppmann's analysis questions Redlock's timing assumptions; Redis links a counter-analysis as well.

A Redis lease is often reasonable for reducing duplicate work when duplicate execution is harmless or independently idempotent. Do not make it the only protection for a payment, inventory reservation, or irreversible external action unless the resource also enforces a fencing or version check.

Consensus-backed coordination and platform leases

A coordination store such as etcd offers lock and election APIs tied to leases. Its lock API returns a key that exists while the caller owns the lock; transactions can use that key to guard updates made in etcd. This is stronger than inventing a lock protocol from ordinary key reads and writes, but an external database or API still needs its own protection against stale commands.

Kubernetes uses Lease objects for node heartbeats and leader election. Competing candidates update a shared object using optimistic concurrency, so only one update against a given resource version succeeds. The lease identifies the current leader and supports takeover when renewals stop. It does not make arbitrary work in an old process disappear. If a leader writes to another system, that system still needs a generation check, idempotency, or reconciliation strategy.

Requirement Starting point Important boundary
Enforce a data invariant Constraint or conditional update Keep the check and mutation in one transaction
Serialize short work in one database Row lock or transaction advisory lock Do not hold it across network calls
Suppress duplicate refresh work Redis lease or per-process single-flight Duplicate work must be safe; protect the stored value separately
Coordinate a cluster leader etcd or a platform Lease API Fence side effects outside the coordination store
Distribute durable work A queue with acknowledgements and idempotent consumers A queue is not a general-purpose mutex

4. A PostgreSQL lease with a fencing generation

A lease row can hold the current owner, expiry, and generation. Keep the row after release so the generation is not reset:

CREATE TABLE coordination_lease (
    resource_key  text PRIMARY KEY,
    owner_id      uuid,
    lease_until   timestamptz NOT NULL DEFAULT '-infinity'::timestamptz,
    fencing_token bigint NOT NULL DEFAULT 0 CHECK (fencing_token >= 0)
);

Acquire with one atomic upsert. The first owner receives token 1; a later owner increments the existing generation only after the previous lease has expired:

INSERT INTO coordination_lease
    (resource_key, owner_id, lease_until, fencing_token)
VALUES
    ($1, $2, clock_timestamp() + $3::interval, 1)
ON CONFLICT (resource_key) DO UPDATE
SET owner_id = EXCLUDED.owner_id,
    lease_until = clock_timestamp() + $3::interval,
    fencing_token = coordination_lease.fencing_token + 1
WHERE coordination_lease.lease_until <= clock_timestamp()
RETURNING fencing_token, lease_until;

If the statement returns no row, another owner still has an unexpired lease. Do not turn that result into an unbounded wait; apply a bounded retry or let another worker take a different item. The unique key and row conflict serialize competing acquisitions for the same resource.

Renew only while the same owner and generation still hold an unexpired lease:

UPDATE coordination_lease
SET lease_until = clock_timestamp() + $4::interval
WHERE resource_key = $1
  AND owner_id = $2
  AND fencing_token = $3
  AND lease_until > clock_timestamp()
RETURNING lease_until;

A renewal that returns no row means ownership is lost or uncertain. Do not revive an expired lease with the old token; reacquisition must produce a new generation. Release conditionally and preserve the row:

UPDATE coordination_lease
SET owner_id = NULL,
    lease_until = '-infinity'::timestamptz
WHERE resource_key = $1
  AND owner_id = $2
  AND fencing_token = $3;

For a database resource in the same PostgreSQL instance, validate the current lease and perform the protected write in one short transaction. Locking the lease row prevents a new acquisition from passing the current owner while that transaction is in progress:

BEGIN;

SELECT 1
FROM coordination_lease
WHERE resource_key = $1
  AND owner_id = $2
  AND fencing_token = $3
  AND lease_until > clock_timestamp()
FOR UPDATE;

-- Require exactly one row. Otherwise ROLLBACK and stop.
UPDATE rebuild_state
SET state = $4,
    last_fencing_token = GREATEST(last_fencing_token, $3)
WHERE resource_key = $1
  AND last_fencing_token <= $3;

COMMIT;

The application must treat a missing lease row, a mismatched owner/token, an expired lease, or a rejected resource update as loss of authority. The transaction should contain only the database work needed for that state change. A long transaction can delay takeover; use bounded lock and statement timeouts and monitor idle transactions.

For a separate storage service, the resource should persist its own highest accepted generation and reject lower tokens on every write. A conditional update might require last_fencing_token <= incoming_token, then advance the high-water mark. Allowing equality permits several operations from the same lease generation; use a separate resource version if operations within one generation also need ordering. Register the new generation with the resource before the new owner starts when the protocol requires immediate fencing. If the resource cannot validate a token or version, a distributed lock alone cannot guarantee that a stale owner will not perform an external side effect.

The runnable PostgreSQL 18 smoke test at interview-handbook/examples/sql/distributed-coordination.sql exercises acquisition, renewal, release, generation changes, and stale-owner rejection. It is a database-level example, not a substitute for a multi-node failover test.

5. Leader election is the same problem at a larger boundary

A leader is a lease holder with a coordination responsibility: schedule work, refresh metadata, or coordinate a partition. Followers observe the leader record and attempt takeover when it expires. The system needs a clear policy for what happens when renewal fails: the leader stops starting new work, signals cancellation to owned tasks, and reports that leadership is uncertain.

That still does not revoke commands already sent. Include a leader epoch in writes to downstream systems, or make the work idempotent and reconcilable. If the leader performs a batch of external operations, record progress durably and make replay safe. Do not rely on a local boolean such as is_leader as the only authorization check.

6. Production controls and failure tests

Treat the lease as a bounded coordination protocol, not a magic timer:

  • Use the coordination store's clock for expiry decisions rather than comparing client wall clocks. PostgreSQL's clock_timestamp() changes during a transaction, unlike now(), which is fixed at transaction start. It is still a wall clock, not a monotonic safety proof; the resource-enforced generation is the safety backstop when expiry timing is imperfect.
  • Choose a TTL and renewal cadence from measured pauses, network latency, failover objectives, and work duration. A 30-second lease renewed every 10 seconds is only an example, not a universal setting.
  • On renewal timeout, assume ownership is uncertain. Stop starting new side effects, cancel cooperative work, and let the resource reject stale generations.
  • Keep owner identity, resource key, and fencing generation in structured logs.
  • Measure acquisition success and wait time, renewal failures, lease expiry, time spent holding ownership, leader transitions, and stale-token rejections.
  • Preserve idempotency keys and durable progress for operations that may be retried after a crash. A lock does not make an external API call exactly once.
  • Test process pauses beyond the TTL, delayed packets, lock-store failover, owner restart, failed renewal, and a stale write after a new generation has been installed. Assert that the resource rejects the stale write.

The SQL example validates database transitions; production still needs fault-injection against the deployed coordination store and protected resource.

7. Interview questions

1. Why is a lease not sufficient for mutual exclusion?

Expiry lets another client take over, but it cannot stop the old process from resuming. Safety must be enforced where the protected state changes, usually with a transaction, version check, or fencing token.

2. What is the difference between an owner token and a fencing token?

An owner token is a unique identity used to prove that a release or renewal belongs to the current lock holder. A fencing token is a monotonically increasing generation that lets the resource reject work from an older owner. One does not replace the other.

3. Why must the resource validate the fencing token?

The coordinator cannot retract a request already in flight. The resource is the final authority over its own state and must remember the newest generation it has accepted. If the resource ignores the token, the token provides no protection.

4. When would you choose a PostgreSQL advisory lock?

Use a transaction-level advisory lock when several code paths must serialize a short database-only operation that does not map neatly to one row. Prefer constraints or row locks when they express the invariant directly. Do not keep a transaction or session lock while performing network work.

5. Is a Redis lock safe after failover?

It depends on the required failure model. Asynchronous replication can promote a replica that never received the original lock, allowing another client to acquire it. Redlock uses independent masters and has a published debate about its timing assumptions. For correctness-critical writes, require resource-side fencing rather than relying on lock acquisition alone.

6. What changes when the lock is used for leader election?

The leader needs a lease-renewal and step-down policy, but followers can take over while old work is still running. Carry a monotonically increasing leader epoch into downstream writes, or make work idempotent and reconcilable.

7. How do you know whether to use a lock or a unique constraint?

Write the invariant first. If the database can enforce it with a unique constraint, conditional update, or transaction, use that. Add distributed coordination only when the operation spans a resource or ownership boundary that those mechanisms cannot cover.

References