Module leader_election

Source
Expand description

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.

The recipe holds no time either. Each poll receives a PollInput: the exact owner record the caller last saw, plus the time elapsed since its anchor, measured by the caller on its own monotonic clock. A claimed leadership may renew only while that elapsed time 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 result asks the caller to reset its observation timer; if it is unchanged, the caller keeps its anchor.

Clocks are never persisted or compared across processes: whoever holds an anchor measures elapsed time on its own clock. Participants need clocks running at similar rates, not synchronized clocks. On process restart, use a fresh ParticipantId and begin again with PollInput::Unknown, so the new incarnation observes the durable state and waits anew before attempting takeover.

LocalState is an optional helper that holds the anchors of a local caller and builds its inputs. Use it unless you are a transport service relaying remote callers.

§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. The recommended loop with LocalState:

  1. Read now from the caller’s monotonic clock once, before Database::run.
  2. Build input = local.input(now) and clone it into the closure, so every retry attempt claims the same tuple and elapsed time.
  3. Call poll inside the closure, with the protected work of a leader outcome in the same transaction.
  4. After Database::run succeeds, and only then, replace the state with local = local.adopt(now, clock.monotonic(), result.next()).

LocalState::adopt applies the anchoring rules. Leadership is anchored at the reading taken before the attempt, so time spent reading, retrying, or committing only shortens local validity. A reset observation is anchored at the fresh post-success reading, so it starts timing only after its durable read is known to have committed. A preserved observation keeps its anchor. 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 NextState::Leadership with LocalState::adopt.
  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 PollInput::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 rank and lease duration. 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.

§Remote callers

A transport service may relay polls for remote participants, which then hold their own anchors and send the tuple they saw plus their measured elapsed time:

  • Apply the same anchoring rules on the caller: a leader anchors before sending its request, a reset observation after receiving the reply.
  • A remote leader must consider itself expired at its anchor plus the lease duration, even while a request is still in flight.
  • A resend must re-measure elapsed time from the same anchor, never restart it.
  • After an unknown commit result, the caller does not know whether it leads. It may then observe itself as owner and wait a full lease before PollTransition::Reacquired; this is expected.
  • NextState::Leadership carries the relaying handle’s lease duration, which is the one persisted.
  • Honest elapsed reporting is a protocol precondition. The exact-tuple check only rejects stale or mismatched callers: a caller, even an authenticated one, that reports an inflated elapsed time for the exact current tuple can take over early. The service must also authenticate the participant, since the tuple check does not stop a caller impersonating another participant. A service that does not trust its callers must enforce timing itself, for example by anchoring on its own clock instead of relaying the reported elapsed time.

§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

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
Optional caller-owned helper holding the local anchors between polls.
NextState
The clock-free state a caller carries to its next poll.
ObservationTimer
Whether a follower’s observation timer restarts or keeps running.
PollInput
What the polling caller claims about the durable state, with the time elapsed since its anchor measured on the caller’s own monotonic clock.
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.