foundationdb/recipes/leader_election/
mod.rs

1// Copyright 2024 foundationdb-rs developers
2//
3// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
4// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
5// http://opensource.org/licenses/MIT>, at your option. This file may not be
6// copied, modified, or distributed except according to those terms.
7
8//! Poll-based Dynamo-style leader leases with FoundationDB fencing.
9//!
10//! This recipe adapts the client-side timing model of the
11//! [Amazon DynamoDB lock client](https://aws.amazon.com/blogs/aws/new-amazon-dynamodb-lock-client/).
12//! A caller observes a durable owner record and uses elapsed time from its own
13//! monotonic clock to decide when that unchanged record is suspicious.
14//! FoundationDB's serializable transaction on one state key, not local time,
15//! resolves concurrent acquisition, renewal, reacquisition, and takeover.
16//! The protocol is Dynamo-inspired, not wire-compatible with the DynamoDB lock
17//! client.
18//!
19//! ## Durable state and local time
20//!
21//! Durable state contains an optional owner, a monotonically increasing
22//! revision, and the last persisted relative lease duration. It contains no
23//! wall-clock or monotonic-clock reading, last-renewed timestamp, deadline, or
24//! expiry. A released record retains its revision and duration, while a
25//! never-created record has revision zero and no duration.
26//!
27//! The recipe holds no time either. Each poll receives a
28//! [`PollInput`](crate::recipes::leader_election::PollInput): the exact owner
29//! record the caller last saw, plus the time elapsed since its anchor, measured
30//! by the caller on its own monotonic clock. A claimed leadership may renew
31//! only while that elapsed time is below the duration stored in its exact
32//! durable revision. A follower waits the duration stored in its exact
33//! observation, never this handle's configured duration. If the observed
34//! owner, revision, or duration changes, the result asks the caller to reset
35//! its observation timer; if it is unchanged, the caller keeps its anchor.
36//!
37//! Clocks are never persisted or compared across processes: whoever holds an
38//! anchor measures elapsed time on its own clock. Participants need clocks
39//! running at similar rates, not synchronized clocks. On process restart, use
40//! a fresh [`ParticipantId`](crate::recipes::leader_election::ParticipantId)
41//! and begin again with
42//! [`PollInput::Unknown`](crate::recipes::leader_election::PollInput::Unknown),
43//! so the new incarnation observes the durable state and waits anew before
44//! attempting takeover.
45//!
46//! [`LocalState`](crate::recipes::leader_election::LocalState) is an optional
47//! helper that holds the anchors of a local caller and builds its inputs. Use
48//! it unless you are a transport service relaying remote callers.
49//!
50//! ## Cutover from v0.11 durable state
51//!
52//! This release's durable state is intentionally incompatible with v0.11.
53//! v0.11 and new clients use different keys, so a mixed deployment is unsafe:
54//! each population can elect a leader without observing or fencing the other.
55//!
56//! Upgrade by a destructive cutover, not an in-place migration. Stop or
57//! quiesce every old participant and all protected work before starting the
58//! new deployment. Then allocate fresh subspaces or epochs for the new
59//! election, its [`RankedRegister`](crate::recipes::ranked_register::RankedRegister),
60//! and the protected sink or rank namespace. Only then start clients using
61//! this release. This recipe neither reads nor migrates v0.11 durable state.
62//!
63//! ## Poll lifecycle
64//!
65//! Call [`LeaderElection::poll`](crate::recipes::leader_election::LeaderElection::poll)
66//! inside the closure passed to [`Database::run`](crate::Database::run). The
67//! recommended loop with [`LocalState`](crate::recipes::leader_election::LocalState):
68//!
69//! 1. Read `now` from the caller's monotonic clock once, before `Database::run`.
70//! 2. Build `input = local.input(now)` and clone it into the closure, so every
71//!    retry attempt claims the same tuple and elapsed time.
72//! 3. Call `poll` inside the closure, with the protected work of a leader
73//!    outcome in the same transaction.
74//! 4. After `Database::run` succeeds, and only then, replace the state with
75//!    `local = local.adopt(now, clock.monotonic(), result.next())`.
76//!
77//! [`LocalState::adopt`](crate::recipes::leader_election::LocalState::adopt)
78//! applies the anchoring rules. Leadership is anchored at the reading taken
79//! before the attempt, so time spent reading, retrying, or committing only
80//! shortens local validity. A reset observation is anchored at the fresh
81//! post-success reading, so it starts timing only after its durable read is
82//! known to have committed. A preserved observation keeps its anchor. This
83//! prevents retries, cancellation, and unknown commits from authorizing work
84//! based on uncommitted caller-local state.
85//!
86//! The poll transaction reads and, for a leadership transition, writes the
87//! same durable key. FoundationDB conflict resolution serializes competing
88//! transitions. Local time only permits an attempted conditional takeover; it
89//! does not prove that the prior process stopped.
90//!
91//! ## Renewal cadence and fencing epochs
92//!
93//! Renew with substantial headroom before local expiry. A cadence around one
94//! third of a lease leaves more room than polling at half a lease for
95//! scheduling delay, transaction retries, and commit latency. Tune it to the
96//! application's latency budget. This is availability guidance, not a safety
97//! condition or a durable expiry.
98//!
99//! A successful acquisition, renewal, reacquisition, or takeover returns a
100//! fresh [`Rank`](crate::recipes::ranked_register::Rank). Each is a new fencing
101//! epoch, including renewal by the same participant. Once the newer rank is
102//! installed, protected work using an older rank, even from that same process,
103//! can be rejected. Leadership status alone never authorizes an unfenced
104//! external side effect.
105//!
106//! Ranks returned by this recipe are opaque durable revisions. Do not mix them
107//! with [`Rank::new`](crate::recipes::ranked_register::Rank::new) values in the
108//! same ranked register or rank space. A manually constructed rank can exceed
109//! every future election revision and permanently fence election-backed work.
110//!
111//! Correctness-sensitive FoundationDB work must use the rank with a
112//! [`RankedRegister`](crate::recipes::ranked_register::RankedRegister) in the
113//! same enclosing transaction. An external sink must atomically enforce the
114//! rank and reject older ranks. See the
115//! [`RankedRegister` composition example](crate::recipes::ranked_register#composing-with-leader-election)
116//! rather than treating a successful poll as sufficient authorization.
117//!
118//! ## Safety versus liveness
119//!
120//! Local expiry does not revoke durable ownership. It only prevents this caller
121//! from renewing with its local token and can lead a follower with an unchanged
122//! observation to attempt takeover. A failed or unavailable poll cannot renew
123//! leadership, so callers must stop protected work that depends on a stale
124//! local token. Fencing ranks, not timing alone, protect against a delayed or
125//! partitioned process.
126//!
127//! Do not rely on a background heartbeat that cannot interrupt, fence, or stop
128//! in-progress protected work. It can renew a lease, but the protected-work
129//! path must still stop when it cannot obtain and use a current fencing rank.
130//!
131//! ## Protocol walkthrough
132//!
133//! 1. Create a non-zero-duration
134//!    [`LeaderElection`](crate::recipes::leader_election::LeaderElection) and a
135//!    fresh [`ParticipantId`](crate::recipes::leader_election::ParticipantId)
136//!    for this process incarnation. Start with
137//!    [`LocalState::Unknown`](crate::recipes::leader_election::LocalState::Unknown).
138//! 2. Poll in a `Database::run` attempt. A released or never-created state
139//!    produces [`PollOutcome::Leader`](crate::recipes::leader_election::PollOutcome::Leader)
140//!    with [`PollTransition::Acquired`](crate::recipes::leader_election::PollTransition::Acquired).
141//!    After the outer transaction succeeds, adopt its
142//!    [`NextState::Leadership`](crate::recipes::leader_election::NextState::Leadership)
143//!    with [`LocalState::adopt`](crate::recipes::leader_election::LocalState::adopt).
144//! 3. A caller that sees another owner receives
145//!    [`PollOutcome::Follower`](crate::recipes::leader_election::PollOutcome::Follower).
146//!    Its next [`LocalState`](crate::recipes::leader_election::LocalState)
147//!    contains an [`Observation`](crate::recipes::leader_election::Observation)
148//!    of that exact owner, revision, duration, and local observation time.
149//!    Repeated polls preserve that time only while the durable record is
150//!    unchanged.
151//! 4. The current holder polls with its matching, locally unexpired
152//!    [`PollInput::Leadership`](crate::recipes::leader_election::PollInput::Leadership) and receives
153//!    [`PollTransition::Renewed`](crate::recipes::leader_election::PollTransition::Renewed)
154//!    with a new rank. An unchanged observation that has waited at least its
155//!    persisted duration permits
156//!    [`PollTransition::TookOver`](crate::recipes::leader_election::PollTransition::TookOver),
157//!    or [`PollTransition::Reacquired`](crate::recipes::leader_election::PollTransition::Reacquired)
158//!    when the observer is the same participant.
159//! 5. For every leader outcome, co-commit the protected FoundationDB work with
160//!    the returned [`Rank`](crate::recipes::ranked_register::Rank), including
161//!    [`RankedRegister::read`](crate::recipes::ranked_register::RankedRegister::read)
162//!    to install its fence. A later rank fences delayed work using every older
163//!    rank.
164//! 6. A holder may call
165//!    [`LeaderElection::resign`](crate::recipes::leader_election::LeaderElection::resign)
166//!    with its exact rank and lease duration. The conditional release preserves the
167//!    revision, so the next acquisition receives a strictly newer rank. A stale
168//!    resignation is rejected.
169//! 7. If the outer run retries, fails, is cancelled, or has an unknown commit,
170//!    do not adopt its `PollResult`. The next successful run rediscovers the
171//!    durable state. After restart, discard all local state, generate a fresh
172//!    participant ID, and follow the observation path again.
173//!
174//! ## Remote callers
175//!
176//! A transport service may relay polls for remote participants, which then
177//! hold their own anchors and send the tuple they saw plus their measured
178//! elapsed time:
179//!
180//! - Apply the same anchoring rules on the caller: a leader anchors before
181//!   sending its request, a reset observation after receiving the reply.
182//! - A remote leader must consider itself expired at its anchor plus the
183//!   lease duration, even while a request is still in flight.
184//! - A resend must re-measure elapsed time from the same anchor, never restart
185//!   it.
186//! - After an unknown commit result, the caller does not know whether it
187//!   leads. It may then observe itself as owner and wait a full lease before
188//!   [`PollTransition::Reacquired`](crate::recipes::leader_election::PollTransition::Reacquired);
189//!   this is expected.
190//! - [`NextState::Leadership`](crate::recipes::leader_election::NextState::Leadership)
191//!   carries the relaying handle's lease duration, which is the one persisted.
192//! - Honest elapsed reporting is a protocol precondition. The exact-tuple
193//!   check only rejects stale or mismatched callers: a caller, even an
194//!   authenticated one, that reports an inflated elapsed time for the exact
195//!   current tuple can take over early. The service must also authenticate
196//!   the participant, since the tuple check does not stop a caller
197//!   impersonating another participant. A service that does not trust its
198//!   callers must enforce timing itself, for example by anchoring on its own
199//!   clock instead of relaying the reported elapsed time.
200//!
201//! ## Caller responsibilities
202//!
203//! The caller owns scheduling, retry policy, transaction options, sleeping,
204//! randomization, background work, and caller-local state. This component does
205//! not call `Database::run`, retry, set transaction options, sleep, draw random
206//! values, start background work, or read wall-clock time.
207//!
208//! ## Further reading
209//!
210//! - [AWS Builders Library: Leader Election in Distributed Systems](https://aws.amazon.com/builders-library/leader-election-in-distributed-systems/)
211//! - [Martin Kleppmann: How to do distributed locking](https://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html)
212//! - Mike Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed
213//!   Systems" (OSDI 2006).
214//! - Gregory Chockler and Dahlia Malkhi, "Active Disk Paxos with Infinitely
215//!   Many Processes" (PODC 2002).
216//! - Salman Niazi, Mahmoud Ismail, Gautier Berthou, and Jim Dowling, "Leader
217//!   Election Using NewSQL Database Systems" (DAIS 2015, LNCS 9038).
218//! - [AWS Labs: Amazon DynamoDB Lock Client](https://github.com/awslabs/amazon-dynamodb-lock-client)
219//! - [Apache ZooKeeper Recipes, GUID note](https://zookeeper.apache.org/doc/r3.5.5/recipes.html)
220
221mod algorithm;
222mod errors;
223mod keys;
224mod types;
225
226pub use errors::{LeaderElectionError, Result};
227pub use types::{
228    ElectionState, Leadership, LocalState, NextState, Observation, ObservationTimer, ParticipantId,
229    PollInput, PollOutcome, PollResult, PollTransition, ResignOutcome,
230};
231
232use crate::{Transaction, recipes::ranked_register::Rank, tuple::Subspace};
233use std::ops::Deref;
234use std::time::Duration;
235
236/// A handle for one independently scoped leader lease.
237///
238/// `lease_duration` is this caller's non-zero desired duration. It is
239/// persisted on every successful acquisition, takeover, and renewal. Existing
240/// foreign records remain governed by their own persisted duration. The handle
241/// holds no caller-local state and performs no scheduling or retries.
242#[derive(Clone, Debug)]
243pub struct LeaderElection {
244    subspace: Subspace,
245    lease_duration: Duration,
246}
247
248impl LeaderElection {
249    /// Creates an election handle with the non-zero duration it will persist on
250    /// successful ownership changes.
251    ///
252    /// Constructing a handle does not read or initialize durable state.
253    #[cfg_attr(
254        feature = "trace",
255        tracing::instrument(level = "debug", skip(subspace))
256    )]
257    pub fn new(subspace: Subspace, lease_duration: Duration) -> Result<Self> {
258        if lease_duration.is_zero() {
259            return Err(LeaderElectionError::InvalidLeaseDuration);
260        }
261        Ok(Self {
262            subspace,
263            lease_duration,
264        })
265    }
266
267    /// Returns this handle's desired duration for its future owner records.
268    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
269    pub fn lease_duration(&self) -> Duration {
270        self.lease_duration
271    }
272
273    /// Polls the durable lease state in the caller's transaction.
274    ///
275    /// A released state is acquired immediately. An exact, locally unexpired
276    /// [`PollInput::Leadership`] renews ownership with a fresh revision. A
277    /// first or changed [`PollInput::Observation`] never steals; only an exact
278    /// unchanged observation may take over, or same-owner reacquire, after the
279    /// observed record's persisted duration. An expired or mismatched
280    /// leadership claim yields a follower result with a reset observation and
281    /// cannot renew directly.
282    ///
283    /// `input` carries elapsed time measured by the caller, see
284    /// [`LocalState::input`]. Measure it before the enclosing
285    /// `Database::run` and reuse it for every retry attempt, making renewal and
286    /// takeover decisions conservative relative to read and commit delay.
287    /// After the run succeeds, adopt [`PollResult::next`], for example with
288    /// [`LocalState::adopt`].
289    ///
290    /// Renew well before the local deadline represented by [`Leadership`],
291    /// leaving headroom for scheduling delay, retries, and commit latency.
292    /// This affects availability only; it is not a durable expiry or safety
293    /// condition.
294    #[cfg_attr(
295        feature = "trace",
296        tracing::instrument(
297            level = "debug",
298            skip(self, txn, participant, input),
299            fields(participant = participant.as_str())
300        )
301    )]
302    pub async fn poll<T>(
303        &self,
304        txn: &T,
305        participant: &ParticipantId,
306        input: &PollInput,
307    ) -> Result<PollResult>
308    where
309        T: Deref<Target = Transaction>,
310    {
311        algorithm::poll(txn, &self.subspace, self.lease_duration, participant, input).await
312    }
313
314    /// Reads durable state without making any liveness or leadership-validity claim.
315    ///
316    /// This is a snapshot only. It does not create a local observation, permit
317    /// renewal or takeover, or authorize protected work.
318    #[cfg_attr(
319        feature = "trace",
320        tracing::instrument(level = "debug", skip(self, txn))
321    )]
322    pub async fn state<T>(&self, txn: &T) -> Result<ElectionState>
323    where
324        T: Deref<Target = Transaction>,
325    {
326        algorithm::state(txn, &self.subspace).await
327    }
328
329    /// Releases ownership only when `participant`, `rank`, and `lease_duration`
330    /// still exactly match durable state.
331    ///
332    /// The revision and persisted duration remain, so a later acquisition has
333    /// a strictly newer fencing rank. A stale delayed resignation is rejected.
334    /// This conditional operation does not make a liveness claim and may be
335    /// used to relinquish an otherwise exact durable token after its local
336    /// renewal window has elapsed.
337    #[cfg_attr(
338        feature = "trace",
339        tracing::instrument(
340            level = "debug",
341            skip(self, txn, participant),
342            fields(
343                participant = participant.as_str(),
344                leadership_revision = rank.as_u64()
345            )
346        )
347    )]
348    pub async fn resign<T>(
349        &self,
350        txn: &T,
351        participant: &ParticipantId,
352        rank: Rank,
353        lease_duration: Duration,
354    ) -> Result<ResignOutcome>
355    where
356        T: Deref<Target = Transaction>,
357    {
358        algorithm::resign(txn, &self.subspace, participant, rank, lease_duration).await
359    }
360}