foundationdb/recipes/ranked_register/
types.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//! Core data structures for the ranked register
9//!
10//! Implements the ranked register abstraction from Chockler & Malkhi's
11//! "Active Disk Paxos with infinitely many processes" (PODC 2002).
12
13use std::fmt;
14
15/// A rank value for ordering register operations
16///
17/// Encodes both a process identifier and a sequence number into a single `u64`.
18/// The high 32 bits hold the sequence number, and the low 32 bits hold the
19/// process ID. This ensures that ranks from the same process are ordered by
20/// sequence, and ties between different processes are broken by process ID.
21///
22/// # Encoding
23///
24/// ```text
25/// |--- sequence (32 bits) ---|--- process_id (32 bits) ---|
26/// ```
27#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
28pub struct Rank(u64);
29
30impl Rank {
31    /// The zero rank, representing the bottom/uninitialized state
32    pub const ZERO: Rank = Rank(0);
33
34    /// Create a new rank from a process ID and sequence number
35    ///
36    /// The sequence occupies the high 32 bits and the process ID the low 32 bits,
37    /// so ranks are ordered primarily by sequence, then by process ID.
38    pub fn new(process_id: u32, sequence: u32) -> Self {
39        Self((sequence as u64) << 32 | process_id as u64)
40    }
41
42    /// Returns the process ID component of this rank
43    pub fn process_id(&self) -> u32 {
44        self.0 as u32
45    }
46
47    /// Returns the sequence number component of this rank
48    pub fn sequence(&self) -> u32 {
49        (self.0 >> 32) as u32
50    }
51
52    /// Returns the raw `u64` representation
53    pub fn as_u64(&self) -> u64 {
54        self.0
55    }
56}
57
58impl From<u64> for Rank {
59    fn from(value: u64) -> Self {
60        Self(value)
61    }
62}
63
64impl fmt::Display for Rank {
65    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
66        write!(
67            f,
68            "Rank(seq={}, pid={})",
69            self.sequence(),
70            self.process_id()
71        )
72    }
73}
74
75/// Internal state of the ranked register as stored in FoundationDB
76///
77/// Tracks the maximum read and write ranks alongside the current value.
78/// Private fields enforce invariants through the algorithm module.
79#[derive(Debug, Clone, PartialEq, Eq, Default)]
80pub struct RegisterState {
81    pub(crate) max_read_rank: Rank,
82    pub(crate) max_write_rank: Rank,
83    pub(crate) value: Option<Vec<u8>>,
84}
85
86impl RegisterState {
87    /// Returns the highest rank that has performed a read
88    pub fn max_read_rank(&self) -> Rank {
89        self.max_read_rank
90    }
91
92    /// Returns the highest rank that has successfully written
93    pub fn max_write_rank(&self) -> Rank {
94        self.max_write_rank
95    }
96
97    /// Returns the current value, if any
98    pub fn value(&self) -> Option<&[u8]> {
99        self.value.as_deref()
100    }
101}
102
103/// Result of a ranked read operation
104///
105/// Contains the write rank and value at the time of the read.
106/// The read also installs a fence at the given rank, preventing
107/// lower-ranked writes from succeeding.
108#[derive(Debug, Clone, PartialEq, Eq)]
109pub struct ReadResult {
110    pub(crate) write_rank: Rank,
111    pub(crate) value: Option<Vec<u8>>,
112}
113
114impl ReadResult {
115    /// Returns the rank of the last successful write
116    pub fn write_rank(&self) -> Rank {
117        self.write_rank
118    }
119
120    /// Returns a reference to the current value, if any
121    pub fn value(&self) -> Option<&[u8]> {
122        self.value.as_deref()
123    }
124
125    /// Consumes self and returns the value
126    pub fn into_value(self) -> Option<Vec<u8>> {
127        self.value
128    }
129}
130
131/// Result of a ranked write operation
132#[derive(Debug, Clone, Copy, PartialEq, Eq)]
133pub enum WriteResult {
134    /// The write was accepted (rank was high enough)
135    Committed,
136    /// The write was rejected (rank too low)
137    Aborted,
138}
139
140impl WriteResult {
141    /// Returns `true` if the write was committed
142    pub fn is_committed(&self) -> bool {
143        matches!(self, WriteResult::Committed)
144    }
145}
foundationdb/recipes/ranked_register/types.rs

foundationdb/recipes/ranked_register/
types.rs
