Leader Election & Distributed Locks: Bully, Leases and Redlock

Why you need one. A scheduler that runs a job twice sends two emails; two writers on a primary-secondary database corrupt data. Some work must be done by exactly one node at a time, and when that node dies another must take over.

Bully algorithm. Every node has an id; the highest live id wins. A node that notices the leader is gone sends ELECTION to all higher ids. If none answers, it declares itself leader (COORDINATOR). If a higher node answers, it takes over the election. Simple and deterministic, but chatty (O(n^2) messages worst case) and unsafe in a partition - each side may elect its own leader.

Leases. Safer than 'am I leader?' is 'do I hold a lease until time T?'. A leader renews a short lease (say 10 s) every few seconds. If it dies, the lease expires and another node can take it. A leader that cannot renew must stop acting, because it may already have been replaced.

Fencing tokens. A paused leader (a long garbage-collection pause) can wake up after its lease expired and still write. Defend with a monotonically increasing fencing token issued with each lease; the storage layer rejects any write carrying a token lower than one it has already seen. This, not clock accuracy, is what makes a lock safe.

A simple Redis lock. SET lock:job <unique-id> NX PX 30000 takes the lock only if absent and gives it an expiry; release by deleting it only if the stored id still matches yours (compare-and-delete in a Lua script), so you never delete someone else's lock.

Redlock. To survive a single Redis failing, acquire the same lock on a majority of N independent Redis instances (e.g. 3 of 5) within a time budget much shorter than the lease; the lock's valid time is the lease minus the time spent acquiring. If a majority cannot be had, release everything and retry after a random delay.

Redlock's honest limits. It depends on bounded clock drift and bounded pauses, which real systems do not promise. For correctness-critical work, use a consensus system (etcd, ZooKeeper) and fencing tokens; use Redlock for efficiency locks, where a rare double-run is merely wasteful.

Choose. If duplicates are harmless, a lease with a short TTL is enough. If duplicates corrupt data, you need consensus plus fencing. Often the best answer is making the work idempotent so that running twice is safe.