SD System Design In Depth
0%
From-Scratch Build

Lease-Based Leader Election with Fencing Tokens

A lease store that issues monotonic fencing tokens, clients that renew and step down early using a clock-drift safety margin, and a storage layer that rejects stale tokens, so a leader that was paused by GC cannot corrupt data. All time is injected, so every scenario is deterministic.

~30 min Intermediate Lessons: Leader election, Distributed locks and leases, Redis Redlock and fencing tokens, Clocks and ordering, Consensus, Distributed systems foundations
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript, TypeScript, or C++20 (WebAssembly) against an in-browser Node.js v22, Bun v1.1 & Clang/WASI runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

The problem

Many systems need exactly one node to do something: run the scheduler, own a shard, accept writes for a partition, or be the active NameNode. Nodes crash and networks partition, so "exactly one" has to recover on its own. The standard tool is a lease: a lock that expires unless it is renewed. When the leader dies, the lease runs out and someone else takes over.

Leases alone are not safe. A leader can check that it holds the lease and then freeze: a GC pause, a VM migration, a swapped-out page, a slow disk. By the time it runs again the lease has expired, a successor is active, and the old leader sends its write anyway. The fix (Chubby's "sequencers", popularised by Kleppmann's critique of Redlock) is a fencing token: a number that increases with every change of ownership and that the protected resource checks.

Where it shows up: Kubernetes controller-manager/scheduler (coordination.k8s.io/Lease), HDFS NameNode HA (quorum journal epochs), Kafka controller epochs, etcd and ZooKeeper election recipes, Google Chubby, and any cron or singleton worker that must not run twice.

Design

text
LeaseClient A ──acquire/renew──►  LeaseStore  (authority on ownership, issues tokens 1,2,3...)
  LeaseClient B ──acquire/renew──►
        │ write(token, ...)
        ▼
  FencedStorage  (remembers highest token seen, rejects anything lower)

lease.js exports:

  • LeaseStore: acquire(holder, ttl), renew(holder, token, ttl), release(holder, token). A new owner always receives token + 1, including the same node coming back after its own lease expired, because someone else may have held the lease in between. Tokens never go down, even after a release.
  • LeaseClient: a candidate state machine driven by tick(). Its local check isLeader() makes no network call.
  • FencedStorage: write(token, k, v) and fence(token). A token equal to the highest seen is accepted (the same leader keeps writing); a lower one throws StaleTokenError.
  • ManualClock, DriftingClock (injectable clocks with rate drift and offset) and mulberry32 (a seeded PRNG).

Invariants and the timing argument

  1. Token monotonicity: each ownership change in the store gets exactly the next integer.
  2. Storage safety: once storage has seen token n, no write with a token below n ever lands. This holds whatever the clocks do. It is the real safety net.
  3. Belief safety: at most one client has isLeader() === true at any real instant, provided relative clock drift stays within maxDriftRate. The client:
    • starts its countdown when it sends the request, not when the reply arrives. The store started the TTL later than that, so network delay only shortens the client's view.
    • acts only for safeWindow = ttl * (1 - maxDriftRate) - safetyMargin on its own clock. If that clock runs slow by rate r, the window lasts safeWindow / (1 - r) real ms, which is at most ttl whenever r ≤ maxDriftRate.
    • renews after renewFraction (1/3) of the window, so it survives a couple of lost renewals.
  4. Clock offset does not matter: only durations on a monotonic clock are used, never wall-clock timestamps compared across machines. DriftingClock in the demo runs B's clock 42 s ahead to show this.

The seeded chaos test runs 3 clients with random drift inside the bound and random pauses of up to 1 s, and asserts invariant 3 at every step. If you set maxDriftRate and the margin to 0, the same test fails, so the margin is doing real work.

Election barrier

Storage can only reject token 1 after it has seen token 2. If the new leader has not written yet, a zombie write with token 1 still gets in (the test shows this). The fix is for the new leader to call storage.fence(token) as its first act, the way HDFS makes a new NameNode bump the epoch on a quorum of JournalNodes before it writes.

Complexity

All operations are O(1) time and space. Memory is O(ownership changes) only because history and events are kept for inspection. Failover takes at most ttl (plus one tick), or one tick after a voluntary resign().

Failure modes & trade-offs

  • TTL length: a short TTL gives fast failover but false failovers under GC or network jitter. A long TTL means longer unavailability when the leader really dies. Kubernetes defaults to 15 s lease / 10 s renew deadline / 2 s retry.
  • Drift beyond the bound breaks belief safety, as the demo's -20% case shows. Storage safety still holds, which is why fencing is not optional.
  • Resources that cannot check tokens (a third-party API, an email being sent) cannot be fenced. You need idempotency keys or a design that accepts at-least-once effects.
  • The lease store must itself be consistent. A token counter backed by one replicated Raft log (etcd) or ZAB (ZooKeeper) is fine. A single Redis without replication is a single point of failure. Redlock across independent Redis nodes does not produce monotonic tokens at all.
  • Store restarts must never reuse tokens. Persist the counter, or derive it from a replicated revision number.

How production systems do it

  • etcd: LeaseGrant / LeaseKeepAlive with a server-side TTL. The concurrency.Election recipe writes a key attached to the lease, and the key's create revision (globally monotonic) works as the fencing token. Transactions can compare mod_revision so a write only applies if leadership has not changed.
  • ZooKeeper: ephemeral sequential znodes tied to the session timeout. The lowest sequence number leads. The zxid or znode version serves as the token.
  • Chubby: lock holders obtain a sequencer (lock name, mode, generation) and pass it to servers, which verify it. There is also a lock-delay for clients that do not check sequencers.
  • Kubernetes client-go leaderelection: a Lease object updated with optimistic concurrency (resourceVersion) and a leaseTransitions counter. The docs say it relies on bounded clock skew and does not fence the controlled resources.
  • HDFS QJM: each new active NameNode obtains a higher epoch. JournalNodes reject edits from lower epochs. This is textbook storage-side fencing.
  • Raft (etcd, CockroachDB, TiKV): terms act as fencing tokens for log replication. Leader leases on top allow local reads, and they depend on the same bounded-drift argument used here.

Extension exercises

  1. Put the LeaseStore behind a simulated network with delay and loss, and check that sending time, not receive time, is what keeps isLeader() safe.
  2. Make FencedStorage a replicated store: a write succeeds only if a majority of replicas accept its token. Then partition one replica.
  3. Implement etcd-style compare-and-swap writes (if leaderKey.createRevision == myToken) instead of a highest-seen check, and compare the two.
  4. Add a lease-delay mode like Chubby's: after an expiry, the store refuses new owners for an extra period, which protects resources that cannot check tokens.
  5. Measure false failovers against TTL and renewFraction under a GC-pause distribution (for example, lognormal), and plot availability against failover time.