Distributed locks: leases, fencing tokens and when not to use one

Key points

• Every practical distributed lock is a lease: it expires so a crashed holder cannot block everyone, which means a slow holder can lose it without knowing.
• Decide first whether the lock is for efficiency, where a rare overlap only wastes work, or for correctness, where an overlap corrupts data. The two need different tools.
• A fencing token is a number that grows with every grant. The storage remembers the highest token it has seen and rejects writes that carry an older one.
• Redlock’s safety depends on timing assumptions; Kleppmann argues that is unsafe for correctness, antirez argues the assumptions are reasonable. Both agree long pauses need something like fencing.
• ZooKeeper, etcd and Chubby tie locks to sessions on a consensus-replicated store and expose numbers that can serve as fencing tokens.
• Often the best lock is none: an idempotency key, a version check on the row, or one owner per partition removes the race instead of guarding it.

Why a lock across machines is hard

Inside one process, a mutex works because the operating system knows when the holder dies and every thread shares one clock and one memory. Across machines none of that holds. The lock service and the client talk over a network, and each side only knows what the last message said. Three things break the simple picture.

• Process pauses. A garbage collection pause, a page fault under memory pressure, a VM being migrated or a container being throttled can stop a process at any instruction, for longer than anyone planned. When it resumes, it carries on as if no time had passed.
• Clock drift and jumps. Each machine has its own clock. Clocks drift, and wall clocks can jump when NTP corrects them or an operator sets the time. A lock that expires by wall-clock time can expire early or late.
• Network delays. A request sent while the lock was held can arrive after the lock has passed to someone else. The Chubby paper describes exactly this: a process holding lock L sends request R and fails; another process takes L and acts; then R arrives and is applied without the protection of L.

The lock service cannot wait forever for a silent client, or one crash would block everyone. So it gives the lock out for a bounded time, and the client cannot be sure it still holds the lock at the moment its write lands. Everything below is a way of living with that gap. The same problem sits under linearizability in consistency models and the CAP theorem: a lock is only as good as the agreement behind it.

Efficiency locks and correctness locks

Martin Kleppmann’s 2016 article “How to do distributed locking” starts with the question that decides the rest: what happens if the lock fails and two processes both think they hold it?

• Efficiency lock: the lock stops work being done twice. If it fails, a report is generated twice or an email goes out twice. That is a cost, not a disaster.
• Correctness lock: the lock protects data. If it fails, two writers interleave and a file is corrupted, a balance is wrong or an order is lost. Kleppmann calls two nodes believing they hold the same lock “a serious bug” in this case.

For efficiency, his advice is a single Redis instance and a note in the code that the lock is approximate. For correctness, he recommends a consensus system such as ZooKeeper, or a database with real transactions, plus fencing tokens on every access to the resource. Most arguments about locks are two people talking about different kinds.

Leases: locks that expire

A lease is a lock with a time to live. The holder gets the lock for a fixed period and must renew it before it runs out; if it crashes or loses contact, the lease expires and someone else can take it. That is the liveness half of the deal. Redis keys with an expiry, ZooKeeper sessions, etcd leases and Chubby’s KeepAlives are all leases.

The cost is the safety half. Picking the length is a trade-off: short leases recover quickly from a dead holder but expire under a healthy holder that hit a long pause; long leases tolerate pauses but leave the resource stuck for longer when a holder dies. Renewing in a background thread helps, but a pause stops the renewal thread too.

Checking the lease before each write does not close the gap. Kleppmann’s point is that a pause can happen at any instruction, including between the check and the write. Chubby added a mitigation for servers that cannot do better, called lock-delay: if a holder fails rather than releasing normally, the lock server refuses to hand the lock to anyone else for a period the client chooses, bounded at one minute in the paper. The paper calls it imperfect. It narrows the window; it does not remove it.

Fencing tokens: let the resource say no

The fix is to stop trusting the client’s belief that it holds the lock and let the protected resource check. Every time the lock service grants the lock, it also returns a number that is larger than any it gave before. The client sends that number with every write. The storage keeps the highest number it has accepted and rejects any write that carries a smaller one.

Kleppmann’s example: client 1 gets token 33 and pauses; its lease expires; client 2 gets token 34 and writes; client 1 wakes up and writes with token 33, and the storage rejects it because it has already seen 34. The simulation below runs that sequence with a fake clock, so it is deterministic.

class LockService:                   # grants leases; each grant gets a larger token
    def __init__(self):
        self.token, self.holder, self.expires = 32, None, 0.0
    def acquire(self, client, now, ttl=10.0):
        if self.holder and now < self.expires:
            return None              # a live lease is held by someone else
        self.token += 1
        self.holder, self.expires = client, now + ttl
        return self.token

class Storage:                       # the resource checks tokens, not the lock
    def __init__(self):
        self.max_token, self.value = 0, ''
    def write(self, client, token, value):
        if token < self.max_token:
            return f'{client}: REJECTED token {token} (already saw {self.max_token})'
        self.max_token, self.value = token, value
        return f'{client}: ok with token {token}, value is now {value!r}'

locks, disk = LockService(), Storage()
t1 = locks.acquire('client-1', now=0.0)   # token 33; then client 1 pauses (GC, swap, VM move)
t2 = locks.acquire('client-2', now=15.0)  # the lease ran out at t=10, so client 2 gets 34
print(disk.write('client-2', t2, 'B'))
print(disk.write('client-1', t1, 'A'))    # client 1 wakes up, still thinks it holds the lock
print('final value:', disk.value)

client-2: ok with token 34, value is now 'B'
client-1: REJECTED token 33 (already saw 34)
final value: B

Without the check in Storage.write, the final value would be A: the stale client’s write lands last and overwrites the newer one. Three details matter in a real system:

• The check and the write must be one atomic step on the storage side. In SQL that is a conditional update such as UPDATE files SET body = :body, fence = :token WHERE id = :id AND fence <= :token, followed by a check that one row changed.
• The token must come from the lock service and grow with every grant, across failovers. A random value identifies a holder; it does not say which holder is newer.
• Every resource the lock protects must check the token. A side effect that cannot check one, such as an email or a call to a third-party API, is not protected by the lock at all, and needs an idempotency key instead.

Chubby built the same idea in 2006 and called it a sequencer: an opaque string with the lock’s name, the mode it was taken in and a lock generation number. The holder passes it to servers such as file servers, which check it is still valid and reject the request if not.

Redis locks and the Redlock debate

The Redis documentation describes the single-instance lock as SET resource_name my_random_value NX PX 30000: set the key only if it does not exist (NX), with an expiry of 30,000 milliseconds (PX). The value must be unique per client and per request, because release must delete the key only if it still holds that value. A plain DEL could remove a lock that expired and was taken by another client in the meantime. The docs give a short Lua script that compares and deletes, and note that Redis 8.4 added a DELEX command with an IFEQ condition that does the same.

The docs are candid about the limits. A single instance is a single point of failure. Adding a replica does not fix it, because Redis replication is asynchronous: a client can take the lock on the primary, the primary can crash before the key reaches the replica, the replica is promoted, and a second client takes the same lock. The page also notes that Redis does not use a monotonic clock for key expiry, so a wall-clock jump can let two processes hold a lock.

Redlock is the docs’ answer for a lock that survives node failures. The client uses N independent Redis primaries, five in the example. It records the time, tries to set the same key and random value on all of them with a short per-node timeout, and holds the lock only if it reached a majority and the elapsed time is less than the lock’s validity time. The remaining validity is the original time minus the time spent acquiring.

Kleppmann’s critique has two parts. First, Redlock produces no fencing token, so it cannot stop a client that paused after acquiring. Second, its safety rests on timing: bounded network delay, bounded pauses and clocks that do not jump. He gives two failure scenarios, a clock jump on one Redis node and a client pause during acquisition, in which two clients both believe they hold the lock, and concludes that Redlock assumes a synchronous system model that real machines and networks do not provide. Consensus algorithms such as Paxos, Raft and Zab, by contrast, stay safe without timing assumptions.

Salvatore Sanfilippo (antirez), who created Redis, replied in “Is Redlock safe?”. He argues that if the storage can do the check-and-set that fencing needs, it can do the same with Redlock’s large random value: set the resource’s state to that value and write only while it still matches. He argues that Redlock needs processes to measure elapsed time at roughly the same rate, not synchronized clocks, and that the algorithm checks the elapsed time after acquiring a majority, which catches delays during acquisition. He agrees that Redis should use a monotonic clock, and he concedes that a pause after that final check affects every lock with automatic release, not only Redlock.

Where that leaves you: both sides agree that a lock with automatic expiry cannot, on its own, protect a resource from a holder that pauses after acquiring, and that the resource needs to check something. They disagree on how much to trust timing in practice. The Redis docs now point readers to both articles and advise implementing fencing tokens if correctness matters. For efficiency locks, a single instance with SET NX PX is simple and fine. For correctness, put the check in the resource, whichever lock you use.

Lock services on consensus: ZooKeeper, etcd and Chubby

These systems replicate their state with a consensus protocol, so a granted lock survives the failure of a minority of servers, and they tie locks to a client session rather than to a key’s expiry time.

• ZooKeeper. The lock recipe has each client create an ephemeral, sequential child node under a lock node. The client with the lowest sequence number holds the lock. Every other client watches only the node just below its own, so a release wakes one waiter instead of all of them, which the docs call avoiding the herd effect. Ephemeral nodes are deleted when the session that created them ends, and session expiry is decided by the cluster when it stops hearing from the client within the session timeout. Kleppmann suggests the zxid or the node’s version as a fencing token.
• etcd. The concurrency API’s Lock call takes a lease ID and returns a key that exists as long as the caller holds the lock; if the lease expires or is revoked, the lock is released. The docs say the key can be used in transactions so that updates to etcd happen only while the lock is held. Every key records a create_revision and mod_revision from a 64-bit, cluster-wide revision counter that only grows, which makes the lock key’s revision a natural fencing token for resources outside etcd.
• Chubby. Mike Burrows’ 2006 paper describes Google’s lock service: a small cell of replicas running Paxos, a file-system-like namespace, advisory reader-writer locks and sessions kept alive by KeepAlive calls. It was built for coarse-grained locks held for hours or days, such as electing a primary, not for locks taken per request. The paper adds sequencers for fencing and lock-delay for servers that cannot check them, and suggests that applications needing fine-grained locks run their own lock servers with a monotonically increasing acquisition counter.

A session expiry is still a lease expiry. A paused ZooKeeper or etcd client can lose its session and keep acting, exactly like a paused Redis client. What these systems add is a consensus-backed record of who holds the lock and an ordering number that comes with it. Use that number.

Database locks: advisory locks and SELECT ... FOR UPDATE

If the data you are protecting lives in PostgreSQL, the database you already run is often the best lock service. PostgreSQL offers two tools.

• Advisory locks are locks on an application-chosen number, one 64-bit key or two 32-bit keys. The server does not attach any meaning to them. Session-level locks, pg_advisory_lock and pg_try_advisory_lock, are held until released or until the session ends, stack if taken twice, and do not honor transactions: a lock taken inside a transaction that rolls back stays held. Transaction-level locks, pg_advisory_xact_lock and pg_try_advisory_xact_lock, are released at commit or rollback and have no unlock call.
• Row locks: `SELECT ... FOR UPDATE` locks the selected rows until the transaction ends, blocking other writers and lockers of those rows but not plain reads. NOWAIT makes the statement fail instead of waiting; SKIP LOCKED skips rows that are already locked, which the docs say gives an inconsistent view and suits queue-like tables with many consumers.

-- Only one worker runs the nightly rollup. 4201 is a key the app reserves for this job.
BEGIN;
SELECT pg_try_advisory_xact_lock(4201) AS got_lock;
-- got_lock is false: another session holds it, so ROLLBACK and skip this run.
-- got_lock is true: do the work inside this same transaction.
INSERT INTO daily_rollup (day, orders)
SELECT current_date - 1, count(*) FROM orders
WHERE created_at >= current_date - 1 AND created_at < current_date;
COMMIT;  -- the advisory lock is released here; there is no unlock call

-- Row locks instead of a named lock: each worker claims one pending job.
BEGIN;
SELECT id FROM jobs WHERE status = 'pending'
ORDER BY id LIMIT 1
FOR UPDATE SKIP LOCKED;
UPDATE jobs SET status = 'running' WHERE id = :claimed_id;
COMMIT;

The strength here is that the lock and the data share one transaction. If the connection drops, the transaction rolls back and the lock goes with it, so a paused worker cannot commit stale work after losing the lock. That stops being true as soon as the work leaves the database: a worker that holds an advisory lock while it writes to object storage or calls an API is back to the lease problem, and needs fencing or idempotency for those effects.

Three practical notes. Prefer the transaction-level functions; session-level locks outlive rollbacks and must be unlocked as many times as they were taken. Behind a connection pooler that hands out a connection per transaction, a session-level lock stays with a pooled connection, not with your request. And advisory locks share a memory pool with ordinary locks; the docs warn that exhausting it stops the server granting any locks, and show how a LIMIT in the same query can take locks on rows you did not mean to.

Comparing lock implementations

When not to use a lock

A lock tries to stop two actors from running at once. Often it is simpler to let them run and make the second one harmless. Three patterns do that.

• Idempotency. Give each operation a unique key and record it with the result, so a repeat returns the first result instead of acting again. This is the usual answer for jobs that might run twice and for side effects that cannot check a token. Idempotency and job queues covers the patterns.
• Optimistic concurrency. Read a row with its version, then write with WHERE id = :id AND version = :seen, setting version = version + 1. If no row changed, someone else won; reload and retry. A fencing token is the same check with the number coming from a lock service instead of the row. Conditional writes in key-value stores work the same way.
• A single writer per partition. Route every write for a key to one owner, so there is never a second writer to exclude. Partitioned logs and sharded services work this way, and consistent hashing and sharding shows how keys find their owner. Ownership still moves when a node fails, so the handoff needs an epoch number that the storage checks, which is a fencing token by another name.

A reasonable order of preference: remove the race with a single writer or a unique constraint; if you cannot, make the write conditional or idempotent; if you still need mutual exclusion, take a lock from the database that holds the data; and reach for a separate lock service, with fencing, when the resource lives somewhere else.

BYD Tech builds web apps and their backends: the code lives in the client’s GitHub from day one, the founders are on the calls, and AI-assisted work is reviewed by an engineer.