Module leader_election

Leader election recipe for distributed consensus Poll-based Dynamo-style leader leases with FoundationDB fencing.

This recipe adapts the client-side timing model of the Amazon DynamoDB lock client. A caller observes a durable owner record and uses elapsed time from its own monotonic clock to decide when that unchanged record is suspicious. FoundationDB’s serializable transaction on one state key, not local time, resolves concurrent acquisition, renewal, reacquisition, and takeover. The protocol is Dynamo-inspired, not wire-compatible with the DynamoDB lock client.

Durable state and local time

Durable state contains an optional owner, a monotonically increasing revision, and the last persisted relative lease duration. It contains no wall-clock or monotonic-clock reading, last-renewed timestamp, deadline, or expiry. A released record retains its revision and duration, while a never-created record has revision zero and no duration.

Leadership and Observation are caller-local state. A leadership token may renew only while elapsed time on that caller’s clock is below the duration stored in its exact durable revision. A follower waits the duration stored in its exact observation, never this handle’s configured duration. If the observed owner, revision, or duration changes, the caller starts a new observation window. If it is unchanged, the original observation time is retained.

Clocks are never persisted or compared across processes. They only measure elapsed time for the caller that recorded them. On process restart, use a fresh ParticipantId and begin again with LocalState::Unknown, so the new incarnation observes the durable state and waits anew before attempting takeover.

Cutover from v0.11 durable state

This release’s durable state is intentionally incompatible with v0.11. v0.11 and new clients use different keys, so a mixed deployment is unsafe: each population can elect a leader without observing or fencing the other.

Upgrade by a destructive cutover, not an in-place migration. Stop or quiesce every old participant and all protected work before starting the new deployment. Then allocate fresh subspaces or epochs for the new election, its RankedRegister, and the protected sink or rank namespace. Only then start clients using this release. This recipe neither reads nor migrates v0.11 durable state.

Poll lifecycle

Call LeaderElection::poll inside the closure passed to Database::run. Read attempt_started_at from the caller’s monotonic clock immediately before each poll call, including every retry attempt. It controls renewal and takeover eligibility and stamps new leadership, so time spent reading, retrying, or committing only shortens local validity.

A returned PollResult is only prepared state. Adopt it with PollResult::into_next_state after the outer Database::run succeeds. Use a fresh adopted_at reading then: it starts timing for a new or reset observation only after its durable read is known to have committed. An unchanged observation and a new leadership token retain their original attempt-local times. This prevents retries, cancellation, and unknown commits from authorizing work based on uncommitted caller-local state.

The poll transaction reads and, for a leadership transition, writes the same durable key. FoundationDB conflict resolution serializes competing transitions. Local time only permits an attempted conditional takeover; it does not prove that the prior process stopped.

Renewal cadence and fencing epochs

Renew with substantial headroom before local expiry. A cadence around one third of a lease leaves more room than polling at half a lease for scheduling delay, transaction retries, and commit latency. Tune it to the application’s latency budget. This is availability guidance, not a safety condition or a durable expiry.

A successful acquisition, renewal, reacquisition, or takeover returns a fresh Rank. Each is a new fencing epoch, including renewal by the same participant. Once the newer rank is installed, protected work using an older rank, even from that same process, can be rejected. Leadership status alone never authorizes an unfenced external side effect.

Ranks returned by this recipe are opaque durable revisions. Do not mix them with Rank::new values in the same ranked register or rank space. A manually constructed rank can exceed every future election revision and permanently fence election-backed work.

Correctness-sensitive FoundationDB work must use the rank with a RankedRegister in the same enclosing transaction. An external sink must atomically enforce the rank and reject older ranks. See the RankedRegister composition example rather than treating a successful poll as sufficient authorization.

Safety versus liveness

Local expiry does not revoke durable ownership. It only prevents this caller from renewing with its local token and can lead a follower with an unchanged observation to attempt takeover. A failed or unavailable poll cannot renew leadership, so callers must stop protected work that depends on a stale local token. Fencing ranks, not timing alone, protect against a delayed or partitioned process.

Do not rely on a background heartbeat that cannot interrupt, fence, or stop in-progress protected work. It can renew a lease, but the protected-work path must still stop when it cannot obtain and use a current fencing rank.

Protocol walkthrough

1. Create a non-zero-duration LeaderElection and a fresh ParticipantId for this process incarnation. Start with LocalState::Unknown.
2. Poll in a Database::run attempt. A released or never-created state produces PollOutcome::Leader with PollTransition::Acquired. After the outer transaction succeeds, adopt its Leadership through PollResult::into_next_state.
3. A caller that sees another owner receives PollOutcome::Follower. Its next LocalState contains an Observation of that exact owner, revision, duration, and local observation time. Repeated polls preserve that time only while the durable record is unchanged.
4. The current holder polls with its matching, locally unexpired Leadership and receives PollTransition::Renewed with a new rank. An unchanged observation that has waited at least its persisted duration permits PollTransition::TookOver, or PollTransition::Reacquired when the observer is the same participant.
5. For every leader outcome, co-commit the protected FoundationDB work with the returned Rank, including RankedRegister::read to install its fence. A later rank fences delayed work using every older rank.
6. A holder may call LeaderElection::resign with its exact leadership token. The conditional release preserves the revision, so the next acquisition receives a strictly newer rank. A stale resignation is rejected.
7. If the outer run retries, fails, is cancelled, or has an unknown commit, do not adopt its PollResult. The next successful run rediscovers the durable state. After restart, discard all local state, generate a fresh participant ID, and follow the observation path again.

Caller responsibilities

The caller owns scheduling, retry policy, transaction options, sleeping, randomization, background work, and caller-local state. This component does not call Database::run, retry, set transaction options, sleep, draw random values, start background work, or read wall-clock time.

Further reading

• AWS Builders Library: Leader Election in Distributed Systems
• Martin Kleppmann: How to do distributed locking
• Mike Burrows, “The Chubby Lock Service for Loosely-Coupled Distributed Systems” (OSDI 2006).
• Gregory Chockler and Dahlia Malkhi, “Active Disk Paxos with Infinitely Many Processes” (PODC 2002).
• Salman Niazi, Mahmoud Ismail, Gautier Berthou, and Jim Dowling, “Leader Election Using NewSQL Database Systems” (DAIS 2015, LNCS 9038).
• AWS Labs: Amazon DynamoDB Lock Client
• Apache ZooKeeper Recipes, GUID note

Structs

• ElectionState
  A read-only snapshot of durable state for diagnostics and observability.
• LeaderElection
  A handle for one independently scoped leader lease.
• Leadership
  The exact durable owner record a caller may attempt to renew before local expiry.
• Observation
  An exact durable owner record adopted after a successful outer transaction.
• ParticipantId
  Identifies one caller process incarnation participating in an election.
• PollResult
  The result prepared by super::LeaderElection::poll.

Enums

• LeaderElectionError
  Leader-election-specific errors.
• LocalState
  Caller-owned state carried between successful outer transactions.
• PollOutcome
  The role and fencing rank prepared by one poll transaction attempt.
• PollTransition
  The state-machine transition classified by one poll attempt.
• ResignOutcome
  Result of a conditional resignation attempt.

Type Aliases

• Result
  Result type for super::LeaderElection operations.