foundationdb/recipes/ranked_register/
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//! # Ranked Register for FoundationDB
9//!
10//! A shared memory abstraction that encapsulates Paxos ballots, based on
11//! Chockler & Malkhi's "Active Disk Paxos with infinitely many processes"
12//! (PODC 2002). A ranked register is a mutable register with conflict detection
13//! via ranks, supporting unbounded processes with finite storage.
14//!
15//! Sections 4.2 and 4.3 of the paper use one logical ranked register. Section
16//! 5.1 implements it from one read-modify-write object, while Section 5.2 uses
17//! `n` registers as replicas to emulate one fault-tolerant logical register.
18//! This implementation is the single logical cell because FoundationDB already
19//! supplies replication and transactions. Multiple child-subspace registers are
20//! application sharding, not a replication requirement from the paper.
21//!
22//! ## Operations
23//!
24//! | Operation | Who | Effect |
25//! |-----------|-----|--------|
26//! | [`read(rank)`](crate::recipes::ranked_register::RankedRegister::read) | Leader | Raises max_read_rank only for a higher rank, returns current value |
27//! | [`write(rank, value)`](crate::recipes::ranked_register::RankedRegister::write) | Leader | Commits only if rank is high enough |
28//! | [`value()`](crate::recipes::ranked_register::RankedRegister::value) | Followers | Plain read, no fence installed |
29//!
30//! ## Addressing, schema, and capacity
31//!
32//! One [`RankedRegister`](crate::recipes::ranked_register::RankedRegister) owns
33//! one [`Subspace`](crate::tuple::Subspace). Its internal `"state"` key stores
34//! a versioned metadata tuple, while raw value bytes are stored in sequential
35//! `"value"/<u64 index>` child keys. For a keyed collection, derive a child
36//! subspace from each logical key before constructing the register:
37//!
38//! ```rust
39//! use foundationdb::{recipes::ranked_register::RankedRegister, tuple::Subspace};
40//!
41//! let registers = Subspace::all().subspace(&"document-registers");
42//! let document_id = "document-42";
43//! let register = RankedRegister::new(registers.subspace(&(document_id,)));
44//! # let _ = register;
45//! ```
46//!
47//! Each value chunk is raw bytes and may be exactly
48//! [`MAX_VALUE_CHUNK_BYTES`](crate::recipes::ranked_register::MAX_VALUE_CHUNK_BYTES)
49//! bytes. [`RankedRegister::new`](crate::recipes::ranked_register::RankedRegister::new)
50//! imposes no recipe aggregate limit, although
51//! FoundationDB transaction limits remain the backend boundary. Use
52//! [`RankedRegister::with_max_value_bytes`](crate::recipes::ranked_register::RankedRegister::with_max_value_bytes)
53//! to impose a local aggregate limit
54//! on one handle. That limit is never stored in FoundationDB, so all handles
55//! that write through the same subspace should use compatible limits.
56//!
57//! This schema is intentionally incompatible with ranked-register state from
58//! v0.11 and earlier. It does not decode the former unversioned tuple layout.
59//! Start with a fresh subspace, or clear an existing register subspace before
60//! using this version.
61//!
62//! Ranked reads and writes for one register contend on that single key and are
63//! serialized by FoundationDB conflicts. Use separate child subspaces to shard
64//! independently updated logical items.
65//!
66//! ## Rank domains
67//!
68//! A register rank space has one authority. Do not mix
69//! [`Rank::new`](crate::recipes::ranked_register::Rank::new) values with
70//! leader-election ranks or values issued by another rank allocator in the
71//! same register. A rank from a different domain can permanently fence valid
72//! future writes from the intended authority.
73//!
74//! Although the primitive stores one optional value, a successful ranked write
75//! can fence additional application-key writes staged in the same transaction.
76//! Stage those writes only when
77//! [`WriteResult::Committed`](crate::recipes::ranked_register::WriteResult::Committed)
78//! is returned. One rank can commit only once per register because each write
79//! requires a rank strictly greater than the stored maximum write rank.
80//!
81//! ## Composing with Leader Election
82//!
83//! The ranked register is designed to work with the leader election recipe.
84//! Every successful leader poll returns a fencing rank derived from the durable
85//! revision, providing automatic fencing against stale leaders. This includes
86//! same-owner renewal: installing the new rank fences delayed work using the
87//! prior rank from that same process.
88//!
89//! ```rust,no_run
90//! # #[cfg(feature = "recipes-leader-election")]
91//! # mod leader_election_example {
92//! # async fn example(db: &foundationdb::Database) -> Result<(), foundationdb::FdbBindingError> {
93//! use std::time::Duration;
94//!
95//! use foundationdb::{
96//!     env::{Clock, Environment},
97//!     options::TransactionOption,
98//!     recipes::{
99//!         leader_election::{LeaderElection, LocalState, ParticipantId, PollOutcome},
100//!         ranked_register::{RankedRegister, WriteResult},
101//!     },
102//!     tuple::Subspace,
103//!     FdbBindingError,
104//! };
105//!
106//! let election = LeaderElection::new(
107//!     Subspace::all().subspace(&"my-election"),
108//!     Duration::from_secs(10),
109//! )?;
110//! let register = RankedRegister::new(Subspace::all().subspace(&"my-state"));
111//! let participant = ParticipantId::new("process-incarnation")?;
112//! let mut local_state = LocalState::unknown();
113//! let env = Environment::default();
114//!
115//! // The application owns retries, options, scheduling, and local observation.
116//! // Measure elapsed time once, before the run, and reuse it on every retry.
117//! let now = env.clock().monotonic();
118//! let input = local_state.input(now);
119//! let result = db.run(|txn, _maybe_committed| {
120//!     let election = election.clone();
121//!     let register = register.clone();
122//!     let participant = participant.clone();
123//!     let input = input.clone();
124//!     async move {
125//!         txn.set_option(TransactionOption::AutomaticIdempotency)?;
126//!         let poll = election.poll(&txn, &participant, &input).await?;
127//!         if let PollOutcome::Leader { rank, .. } = poll.outcome() {
128//!             register
129//!                 .read(&txn, *rank)
130//!                 .await
131//!                 .map_err(|error| FdbBindingError::new_custom_error(Box::new(error)))?;
132//!             let write_result = register
133//!                 .write(&txn, *rank, b"new_value")
134//!                 .await
135//!                 .map_err(|error| FdbBindingError::new_custom_error(Box::new(error)))?;
136//!             if write_result == WriteResult::Committed {
137//!                 txn.set(b"application-key", b"new_value");
138//!             }
139//!         }
140//!         Ok::<_, FdbBindingError>(poll)
141//!     }
142//! }).await?;
143//! // Adopt this only after db.run succeeded.
144//! local_state = local_state.adopt(now, env.clock().monotonic(), result.next());
145//! # let _ = local_state;
146//! # Ok(())
147//! # }
148//! # }
149//! ```
150//!
151//! ### Why This Works
152//!
153//! - Durable leader-election revisions increase monotonically
154//! - A renewal is a new fencing epoch, even for the same leader
155//! - `read(rank)` installs a fence at that fencing rank
156//! - Any write with a lower fencing rank is automatically rejected
157//! - `value()` is safe for followers, it never installs a fence
158
159mod algorithm;
160mod errors;
161mod keys;
162mod types;
163
164pub use errors::{RankedRegisterError, Result};
165pub use types::{Rank, ReadResult, RegisterState, WriteResult};
166
167use crate::{Transaction, tuple::Subspace};
168use std::ops::Deref;
169
170/// Maximum size of one raw register-value chunk.
171///
172/// This is FoundationDB's exact 100,000-byte value limit.
173pub const MAX_VALUE_CHUNK_BYTES: usize = 100_000;
174
175/// A ranked register backed by FoundationDB
176///
177/// Provides a mutable register with conflict detection via ranks.
178/// No initialization is needed — an absent key represents the bottom state
179/// (zero ranks, no value).
180///
181/// # Thread Safety
182///
183/// `RankedRegister` is [`Clone`], [`Send`], and [`Sync`]. It holds only a
184/// [`Subspace`] and can be safely shared across tasks.
185#[derive(Clone, Debug)]
186pub struct RankedRegister {
187    subspace: Subspace,
188    max_value_bytes: Option<usize>,
189}
190
191impl RankedRegister {
192    /// Create a new ranked register instance
193    ///
194    /// The subspace isolates this register from other data in the database.
195    /// No initialization step is required — the register starts in the
196    /// bottom state (zero ranks, no value) until the first write.
197    #[cfg_attr(
198        feature = "trace",
199        tracing::instrument(level = "debug", skip(subspace))
200    )]
201    pub fn new(subspace: Subspace) -> Self {
202        Self {
203            subspace,
204            max_value_bytes: None,
205        }
206    }
207
208    /// Create a ranked register with a local aggregate value-size limit.
209    ///
210    /// The limit applies only to writes through this handle. It is not durable
211    /// state, so use compatible limits for all writers of the same subspace.
212    #[cfg_attr(
213        feature = "trace",
214        tracing::instrument(level = "debug", skip(subspace))
215    )]
216    pub fn with_max_value_bytes(subspace: Subspace, limit: usize) -> Self {
217        Self {
218            subspace,
219            max_value_bytes: Some(limit),
220        }
221    }
222
223    /// Returns a reference to the underlying subspace
224    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
225    pub fn subspace(&self) -> &Subspace {
226        &self.subspace
227    }
228
229    /// Perform a ranked read
230    ///
231    /// Raises `max_read_rank` only when the given rank is higher, installing a
232    /// fence that prevents lower-ranked writes. A superseded rank returns the
233    /// current write rank and value without changing the installed fence.
234    ///
235    /// Used by the leader before writing to ensure consistency.
236    #[cfg_attr(
237        feature = "trace",
238        tracing::instrument(level = "debug", skip(self, txn))
239    )]
240    pub async fn read<T>(&self, txn: &T, rank: Rank) -> Result<ReadResult>
241    where
242        T: Deref<Target = Transaction>,
243    {
244        algorithm::read(txn, &self.subspace, rank).await
245    }
246
247    /// Perform a ranked write
248    ///
249    /// Commits the value only if:
250    /// - `rank >= max_read_rank` (no higher fence)
251    /// - `rank > max_write_rank` (no equal-or-higher write)
252    ///
253    /// Returns [`WriteResult::Committed`] or [`WriteResult::Aborted`].
254    /// Returns [`RankedRegisterError::ValueTooLarge`] when this handle has a
255    /// configured limit and `value` exceeds it.
256    #[cfg_attr(
257        feature = "trace",
258        tracing::instrument(level = "debug", skip(self, txn, value))
259    )]
260    pub async fn write<T>(&self, txn: &T, rank: Rank, value: &[u8]) -> Result<WriteResult>
261    where
262        T: Deref<Target = Transaction>,
263    {
264        algorithm::write(txn, &self.subspace, rank, value, self.max_value_bytes).await
265    }
266
267    /// Read the current value without updating ranks
268    ///
269    /// Safe for followers and observers: it installs no durable fence. Its
270    /// normal non-snapshot FoundationDB read still adds a conflict range for
271    /// this register key, so it can conflict with a concurrent leader write.
272    #[cfg_attr(
273        feature = "trace",
274        tracing::instrument(level = "debug", skip(self, txn))
275    )]
276    pub async fn value<T>(&self, txn: &T) -> Result<Option<Vec<u8>>>
277    where
278        T: Deref<Target = Transaction>,
279    {
280        algorithm::value(txn, &self.subspace).await
281    }
282}