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//! ## Operations
16//!
17//! | Operation | Who | Effect |
18//! |-----------|-----|--------|
19//! | [`read(rank)`](RankedRegister::read) | Leader | Updates max_read_rank (installs fence), returns current value |
20//! | [`write(rank, value)`](RankedRegister::write) | Leader | Commits only if rank is high enough |
21//! | [`value()`](RankedRegister::value) | Followers | Plain read, no fence installed |
22//!
23//! ## Composing with Leader Election
24//!
25//! The ranked register is designed to work with the leader election recipe.
26//! The leader election's ballot serves as the rank for register operations,
27//! providing automatic fencing against stale leaders.
28//!
29//! ```rust,no_run
30//! # fn example() {
31//! use foundationdb::recipes::leader_election::LeaderElection;
32//! use foundationdb::recipes::ranked_register::{RankedRegister, Rank};
33//! use foundationdb::tuple::Subspace;
34//!
35//! let election = LeaderElection::new(Subspace::all().subspace(&"my-election"));
36//! let register = RankedRegister::new(Subspace::all().subspace(&"my-state"));
37//!
38//! // In the leader's main loop:
39//! // db.run(|txn, _| async move {
40//! //     let result = election.run_election_cycle(&txn, process_id, priority, now).await?;
41//! //     match result {
42//! //         ElectionResult::Leader(state) => {
43//! //             let rank = Rank::from(state.ballot);
44//! //             // Read current state (installs fence at this ballot)
45//! //             let current = register.read(&txn, rank).await?;
46//! //             // Mutate and write back
47//! //             register.write(&txn, rank, b"new_value").await?;
48//! //         }
49//! //         ElectionResult::Follower(_) => {
50//! //             // Safe read — doesn't interfere with leader's writes
51//! //             let current = register.value(&txn).await?;
52//! //         }
53//! //     }
54//! //     Ok(())
55//! // }).await?;
56//! # }
57//! ```
58//!
59//! ### Why This Works
60//!
61//! - Leader election's ballot is monotonically increasing
62//! - A deposed leader has a lower ballot than the new leader
63//! - `read(rank)` installs a fence at the ballot value
64//! - Any write with a lower rank is automatically rejected
65//! - `value()` is safe for followers — it never installs a fence
66
67mod algorithm;
68mod errors;
69mod keys;
70mod types;
71
72pub use errors::{RankedRegisterError, Result};
73pub use types::{Rank, ReadResult, RegisterState, WriteResult};
74
75use crate::{tuple::Subspace, Transaction};
76use std::ops::Deref;
77
78/// A ranked register backed by FoundationDB
79///
80/// Provides a mutable register with conflict detection via ranks.
81/// No initialization is needed — an absent key represents the bottom state
82/// (zero ranks, no value).
83///
84/// # Thread Safety
85///
86/// `RankedRegister` is [`Clone`], [`Send`], and [`Sync`]. It holds only a
87/// [`Subspace`] and can be safely shared across tasks.
88#[derive(Clone, Debug)]
89pub struct RankedRegister {
90    subspace: Subspace,
91}
92
93impl RankedRegister {
94    /// Create a new ranked register instance
95    ///
96    /// The subspace isolates this register from other data in the database.
97    /// No initialization step is required — the register starts in the
98    /// bottom state (zero ranks, no value) until the first write.
99    pub fn new(subspace: Subspace) -> Self {
100        Self { subspace }
101    }
102
103    /// Returns a reference to the underlying subspace
104    pub fn subspace(&self) -> &Subspace {
105        &self.subspace
106    }
107
108    /// Perform a ranked read
109    ///
110    /// Updates `max_read_rank` if the given rank is higher, installing a fence
111    /// that prevents lower-ranked writes. Returns the current write rank and value.
112    ///
113    /// Used by the leader before writing to ensure consistency.
114    pub async fn read<T>(&self, txn: &T, rank: Rank) -> Result<ReadResult>
115    where
116        T: Deref<Target = Transaction>,
117    {
118        algorithm::read(txn, &self.subspace, rank).await
119    }
120
121    /// Perform a ranked write
122    ///
123    /// Commits the value only if:
124    /// - `rank >= max_read_rank` (no higher fence)
125    /// - `rank > max_write_rank` (no equal-or-higher write)
126    ///
127    /// Returns [`WriteResult::Committed`] or [`WriteResult::Aborted`].
128    pub async fn write<T>(&self, txn: &T, rank: Rank, value: &[u8]) -> Result<WriteResult>
129    where
130        T: Deref<Target = Transaction>,
131    {
132        algorithm::write(txn, &self.subspace, rank, value).await
133    }
134
135    /// Read the current value without updating ranks
136    ///
137    /// Safe for followers and observers — does not install a fence,
138    /// so it won't interfere with the leader's writes.
139    pub async fn value<T>(&self, txn: &T) -> Result<Option<Vec<u8>>>
140    where
141        T: Deref<Target = Transaction>,
142    {
143        algorithm::value(txn, &self.subspace).await
144    }
145}
foundationdb/recipes/ranked_register/mod.rs

foundationdb/recipes/ranked_register/
mod.rs
