Distributed locks and leader leases: expiry, fencing tokens and what a lock cannot promise

What it is

A distributed lock is a lease: a client acquires the exclusive right to a name for a bounded time and must renew it before expiry. The Kubernetes documentation (cited) describes Lease objects in the coordination.k8s.io API group used for node heartbeats and leader election of control-plane components. Redis documents Redlock (cited) as a proposed multi-instance locking algorithm, invites analysis of it, and in its consistency disclaimer says that fencing tokens should be implemented and that Redis does not use a monotonic clock for key expiry.

Kleppmann's analysis (cited) makes the central point: a client can pause (garbage collection, page faults, CPU contention, a delayed packet) after acquiring the lease, the lease expires, a second client acquires it, and the first client resumes and writes as if it still held the lock. No lock service can prevent this on its own. The fix is a fencing token, a number that increases every time the lock is granted, sent with every write to the protected resource, which rejects any write carrying a token lower than one it has already seen. ZooKeeper's zxid or znode version can serve as such a token; Kleppmann notes that Redlock has no facility for generating one.

Why it matters

Kleppmann distinguishes locks for efficiency (avoid doing the same expensive work twice; an occasional duplicate is harmless) from locks for correctness (a duplicate corrupts data or double-charges). Teams often deploy the first kind and rely on it as the second.

How to apply

• Decide which kind of lock you need. For efficiency, a single lock store with a TTL and an owner token on release is enough.
• For correctness, obtain a monotonically increasing token from the lock service (a consensus store's revision, a database sequence updated in the same transaction) and make the resource check it: a fence column with a conditional UPDATE ... SET fence = $held WHERE fence <= $held (zero rows updated means the lease was lost), or a storage API with conditional writes.
• Set the renewal interval well below the lease duration and stop work immediately when a renewal fails; do not "finish the current item first".
• Release only with the token you hold, so an expired holder cannot release the successor's lease.
• Prefer making the work idempotent over locking it; a lock then only reduces wasted effort.

Pitfalls

Lease durations are wall-clock assumptions about how long a process may pause, and pauses have no upper bound. A lock that protects a resource without a token check is a hint, not a guarantee. A singleton cron runner with "only one instance runs" enforced by a lock still needs idempotent jobs.