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}