Leader Election Distributed Locks and Leases

Published by Programming Line in System Design and Distributed Systems. Last updated .

Purpose and Outcome

Leader election, distributed locks, and leases solve a narrow but critical coordination problem: deciding which process may perform an exclusive action at a moment in time. In system design, this appears when one scheduler should enqueue jobs, one replica should accept writes, one compactor should rewrite storage files, or one worker should own a shard. The goal is not to make distributed systems magically synchronous. The goal is to make ownership explicit, bounded, observable through a coordination service, and safe when machines crash or networks delay messages.

A leader is a process selected from a group to make decisions for a term, epoch, or lease interval. A distributed lock is an exclusive claim on a named resource, such as billing-daily-close. A lease is a lock with an expiration time. The expiration is important because it lets the system recover if the holder dies, but it also creates the hardest design constraint: an old holder may keep running after its lease has expired if it was paused or partitioned. Correct designs therefore combine leases with renewal rules and, for external side effects, fencing tokens.

Mechanism Internals

Most robust implementations use a small coordination system rather than every application node negotiating directly with every other node. ZooKeeper, etcd, and Consul are common examples. Internally, these systems replicate metadata with consensus, so a successful lock or election operation is committed to a quorum before clients rely on it. The coordination state is small: keys, sessions, versions, leases, and monotonic counters. The application state remains elsewhere.

A typical lock acquisition writes a key only if it does not already exist. In etcd terms this is a transaction: compare that the key version is zero, then put the owner value attached to a lease. In ZooKeeper, contenders create ephemeral sequential znodes and the contender with the lowest sequence number becomes leader. The session or lease ties ownership to liveness as observed by the coordinator. If the client disconnects long enough, the coordinator expires the session and deletes or invalidates the ownership record.

Leader election adds ordering. Candidates need to know not only who currently leads, but also whether a newer leadership term has superseded an older one. A monotonically increasing epoch, revision, or fencing token provides that ordering. A storage service receiving writes from leaders can reject commands whose token is lower than the latest token it has accepted. Without this, a paused former leader can wake up and corrupt state even though the lock service has already elected a replacement.

API Anatomy

A practical coordination API has five parts. The resource name identifies what is protected. The owner identity records which process believes it owns the resource. The lease ttl sets how long the coordinator will preserve ownership without renewal. The renewal loop extends the lease before expiration. The fencing token is a monotonically increasing number returned on acquisition and included in downstream writes.

from dataclasses import dataclass

@dataclass(frozen=True)
class LeasePolicy:
    ttl_seconds: int
    renew_every_seconds: int
    pause_budget_seconds: int

policy = LeasePolicy(ttl_seconds=30, renew_every_seconds=10, pause_budget_seconds=12)

assert policy.renew_every_seconds * 2 + policy.pause_budget_seconds <= policy.ttl_seconds
print("lease policy leaves renewal margin")

This simple check captures a real design rule. If a process renews every ten seconds, and the platform can pause it for twelve seconds, a thirty-second TTL leaves enough time for one missed renewal and a late retry. If the assertion fails, the system may revoke leadership while the application still believes it is leader.

Example 1: Single Scheduled Job

Suppose five API instances all run the same minute-based scheduler, but only one should enqueue invoices. Each instance attempts to acquire the invoice-scheduler lease. One succeeds; the others watch the key and retry after it is released or expired. The leader renews the lease while it enqueues work. The expected behavior is duplicate prevention for scheduler decisions, not necessarily exactly-once invoice processing. Downstream jobs should still be idempotent because the leader can crash after enqueueing some messages and before recording completion.

A safe scheduler loop reads: acquire lease, receive token 41, enqueue jobs with idempotency keys such as invoice:customer:date, renew during long batches, then release. If the leader crashes, token 42 may be issued to another instance after TTL expiry. The queue accepts each invoice key once. The lease selects one scheduler; idempotency handles retries and crash boundaries.

Example 2: Shard Ownership

Now consider a stream processor with 128 shards and 12 workers. A single global leader would become a bottleneck, so the design uses one lease per shard: stream/shard-000 through stream/shard-127. Workers acquire multiple leases and process only the shards they own. This spreads coordination and allows partial failover. If one worker dies, only its shards are reassigned.

The expected output is stable ownership with bounded imbalance. A worker might own shards 0, 9, and 27, while another owns 1, 5, and 80. When worker A stops renewing, its leases expire and other workers claim those shard keys. The stream offsets should be committed with the shard lease token so stale owners cannot overwrite a newer offset.

Example 3: Fenced Writes

The most important example is a paused leader. Process A acquires a lock and receives token 7. It starts a write to shared storage, then experiences a long stop-the-world pause. Its lease expires. Process B acquires the same lock and receives token 8. B writes new data. A later resumes and sends its delayed write. If storage does not check tokens, A can overwrite B. If storage stores the highest accepted token per resource, it rejects A because 7 is older than 8.

class FencedRegister:
    def __init__(self):
        self.value = None
        self.highest_token = 0

    def write(self, token, value):
        if token < self.highest_token:
            return "rejected stale token"
        self.highest_token = token
        self.value = value
        return "accepted"

register = FencedRegister()
print(register.write(7, "leader-a-started"))
print(register.write(8, "leader-b-committed"))
print(register.write(7, "leader-a-resumed"))
print(register.value)

The deterministic output is accepted, accepted, rejected stale token, and leader-b-committed. The lease service alone cannot prevent the delayed message. The downstream resource must participate by enforcing the fencing token.

Design Choices and Trade-offs

Short TTLs reduce failover time but increase false failovers during garbage collection, CPU starvation, coordinator hiccups, or network jitter. Long TTLs reduce accidental revocation but delay recovery after real crashes. Renewal frequency should be comfortably shorter than TTL, but too-frequent renewal creates load on the coordinator and noisy incident signals.

Leader election granularity also matters. A single leader is simple and useful for schema migrations, cluster-wide scheduling, or metadata decisions. Per-resource leases scale better for shard processing and distributed workers, but they require rebalancing logic and can cause thundering herds when many leases expire at once. Sequential-node elections are easy to reason about because the lowest sequence wins; compare-and-put locks are compact and fit key-value coordinators. Both require clients to handle session loss as loss of authority, not as a warning to inspect later.

Fairness is usually less important than safety. Many systems do not guarantee first-come-first-served lock acquisition because retries, watches, and session expirations race. If fairness matters, use a queue-like election pattern such as sequential contenders watching only their predecessor. That avoids waking every candidate on each change and gives deterministic ordering.

Failure Modes and Troubleshooting

Symptom: two workers appear to process the same shard. Cause: the old worker continued after losing its lease, or the protected storage did not enforce fencing. Diagnostic steps: compare coordinator lease revision history, worker logs for renewal failures, and downstream writes for token values. Correction: make lease loss stop the worker immediately, include fencing tokens in offset commits, and reject stale tokens at the storage boundary.

Symptom: leadership changes every few minutes under load. Cause: TTL is too close to observed pauses or renewal requests are starved behind application work. Diagnostic steps: measure renewal latency, process pauses, coordinator request latency, and clock-independent lease expiry events. Correction: increase TTL margin, renew from a lightweight dedicated task, reduce coordinator overload, and treat renewal failure as a controlled step-down.

Symptom: no candidate becomes leader after an outage. Cause: clients are waiting on stale watches, using expired sessions, or retrying with the same failed connection. Diagnostic steps: inspect session state, connection errors, and whether the lock key still has an attached live lease. Correction: recreate the session, re-list current contenders after reconnect, and implement retry with jitter.

Security, Performance, and Reliability

Coordination keys should be protected by least-privilege access. A worker that only owns stream shards should not be able to delete the database migration leader key. Store owner identities for debugging, but avoid secrets in lock values because they are often visible to operators and logs.

The coordinator is on the critical path for acquisition and renewal, not for every unit of business work. Keep lock values small, avoid high-cardinality churn when a local queue would work, and do not use a consensus-backed coordinator as a general message broker. Reliability depends on making lease loss explicit in the application state machine: candidate, leader, stepping_down, and follower are safer than a Boolean is_leader.

Hands-on Lab

Prerequisites: Python 3 and a terminal. This lab simulates lease acquisition, expiry, and fenced writes without requiring a real coordination service. It demonstrates the invariant you must preserve when later using etcd, ZooKeeper, or Consul: newer ownership tokens supersede older ones.

  1. Create a file named lease_lab.py with the code below.
  2. Run python lease_lab.py.
  3. Verify that the stale write is rejected and the final value belongs to the second leader.
  4. Change the stale write token from 1 to 3 and rerun. Observe that the simulated storage accepts it because it now appears newer.
  5. Cleanup by deleting lease_lab.py when finished.
class Coordinator:
    def __init__(self):
        self.token = 0
        self.owner = None

    def acquire(self, owner):
        self.token += 1
        self.owner = owner
        return self.token

class Storage:
    def __init__(self):
        self.highest_token = 0
        self.value = "empty"

    def write(self, token, value):
        if token < self.highest_token:
            return "reject"
        self.highest_token = token
        self.value = value
        return "ok"

coordinator = Coordinator()
storage = Storage()

a_token = coordinator.acquire("worker-a")
print("A", a_token, storage.write(a_token, "from A"))
b_token = coordinator.acquire("worker-b")
print("B", b_token, storage.write(b_token, "from B"))
print("A late", a_token, storage.write(a_token, "late A"))
print("final", storage.value)

Expected output is A 1 ok, B 2 ok, A late 1 reject, and final from B. The coordinator chooses ownership order; storage enforces that order. Real systems need both halves.

Assessment Exercises

  1. A leader renews every 5 seconds, the lease TTL is 12 seconds, and garbage collection sometimes pauses the process for 9 seconds. Explain whether this is safe and what measurements would change your answer.
  2. Design shard ownership for 1,000 partitions and 40 workers. Which data goes in the coordination service, and which data stays in the stream or database?
  3. A team says it does not need fencing because its lock service is strongly consistent. Describe the paused-leader scenario that still breaks the system.
  4. Choose a TTL and renewal interval for a nightly compaction leader where 30 seconds of failover delay is acceptable but duplicate compaction is expensive. Defend the trade-off.
  5. Given logs showing token 15 and token 16 both writing the same object, list the checks needed to determine whether this was a bug or expected retry behavior.

Summary

Leader election decides who may act; distributed locks name the exclusive resource; leases bound ownership in time; fencing tokens make old owners harmless after leadership changes. The central system-design lesson is that coordination is only complete when both the coordinator and the protected resource participate. Tune TTLs for real pauses and network behavior, keep coordination state small, use per-resource leases when scale requires it, and make loss of leadership a first-class application transition.