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:
- Read
nowfrom the caller’s monotonic clock once, beforeDatabase::run. - Build
input = local.input(now)and clone it into the closure, so every retry attempt claims the same tuple and elapsed time. - Call
pollinside the closure, with the protected work of a leader outcome in the same transaction. - After
Database::runsucceeds, and only then, replace the state withlocal = 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
- Create a non-zero-duration
LeaderElectionand a freshParticipantIdfor this process incarnation. Start withLocalState::Unknown. - Poll in a
Database::runattempt. A released or never-created state producesPollOutcome::LeaderwithPollTransition::Acquired. After the outer transaction succeeds, adopt itsNextState::LeadershipwithLocalState::adopt. - A caller that sees another owner receives
PollOutcome::Follower. Its nextLocalStatecontains anObservationof that exact owner, revision, duration, and local observation time. Repeated polls preserve that time only while the durable record is unchanged. - The current holder polls with its matching, locally unexpired
PollInput::Leadershipand receivesPollTransition::Renewedwith a new rank. An unchanged observation that has waited at least its persisted duration permitsPollTransition::TookOver, orPollTransition::Reacquiredwhen the observer is the same participant. - For every leader outcome, co-commit the protected FoundationDB work with
the returned
Rank, includingRankedRegister::readto install its fence. A later rank fences delayed work using every older rank. - A holder may call
LeaderElection::resignwith 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. - 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::Leadershipcarries 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
- 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§
- Election
State - A read-only snapshot of durable state for diagnostics and observability.
- Leader
Election - 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.
- Participant
Id - Identifies one caller process incarnation participating in an election.
- Poll
Result - The result prepared by
super::LeaderElection::poll.
Enums§
- Leader
Election Error - Leader-election-specific errors.
- Local
State - Optional caller-owned helper holding the local anchors between polls.
- Next
State - The clock-free state a caller carries to its next poll.
- Observation
Timer - Whether a follower’s observation timer restarts or keeps running.
- Poll
Input - What the polling caller claims about the durable state, with the time elapsed since its anchor measured on the caller’s own monotonic clock.
- Poll
Outcome - The role and fencing rank prepared by one poll transaction attempt.
- Poll
Transition - The state-machine transition classified by one poll attempt.
- Resign
Outcome - Result of a conditional resignation attempt.
Type Aliases§
- Result
- Result type for
super::LeaderElectionoperations.