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    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug"))]
39    pub fn new(process_id: u32, sequence: u32) -> Self {
40        Self(((sequence as u64) << 32) | process_id as u64)
41    }
42
43    /// Returns the process ID component of this rank
44    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
45    pub fn process_id(&self) -> u32 {
46        self.0 as u32
47    }
48
49    /// Returns the sequence number component of this rank
50    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
51    pub fn sequence(&self) -> u32 {
52        (self.0 >> 32) as u32
53    }
54
55    /// Returns the raw `u64` representation
56    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
57    pub fn as_u64(&self) -> u64 {
58        self.0
59    }
60}
61
62impl From<u64> for Rank {
63    fn from(value: u64) -> Self {
64        Self(value)
65    }
66}
67
68impl fmt::Display for Rank {
69    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70        write!(
71            f,
72            "Rank(seq={}, pid={})",
73            self.sequence(),
74            self.process_id()
75        )
76    }
77}
78
79/// Logical state of the ranked register
80///
81/// Tracks the maximum read and write ranks alongside the current value. The
82/// implementation stores metadata and value chunks separately.
83/// Private fields enforce invariants through the algorithm module.
84#[derive(Debug, Clone, PartialEq, Eq, Default)]
85pub struct RegisterState {
86    pub(crate) max_read_rank: Rank,
87    pub(crate) max_write_rank: Rank,
88    pub(crate) value: Option<Vec<u8>>,
89}
90
91impl RegisterState {
92    /// Returns the highest rank that has performed a read
93    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
94    pub fn max_read_rank(&self) -> Rank {
95        self.max_read_rank
96    }
97
98    /// Returns the highest rank that has successfully written
99    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
100    pub fn max_write_rank(&self) -> Rank {
101        self.max_write_rank
102    }
103
104    /// Returns the current value, if any
105    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
106    pub fn value(&self) -> Option<&[u8]> {
107        self.value.as_deref()
108    }
109}
110
111/// Result of a ranked read operation
112///
113/// Contains the write rank and value at the time of the read.
114/// The read also installs a fence at the given rank, preventing
115/// lower-ranked writes from succeeding.
116#[derive(Debug, Clone, PartialEq, Eq)]
117pub struct ReadResult {
118    pub(crate) write_rank: Rank,
119    pub(crate) value: Option<Vec<u8>>,
120}
121
122impl ReadResult {
123    /// Returns the rank of the last successful write
124    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
125    pub fn write_rank(&self) -> Rank {
126        self.write_rank
127    }
128
129    /// Returns a reference to the current value, if any
130    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
131    pub fn value(&self) -> Option<&[u8]> {
132        self.value.as_deref()
133    }
134
135    /// Consumes self and returns the value
136    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
137    pub fn into_value(self) -> Option<Vec<u8>> {
138        self.value
139    }
140}
141
142/// Result of a ranked write operation
143#[must_use = "a committed write result controls whether co-staged application writes are valid"]
144#[derive(Debug, Clone, Copy, PartialEq, Eq)]
145pub enum WriteResult {
146    /// The write was accepted (rank was high enough)
147    Committed,
148    /// The write was rejected (rank too low)
149    Aborted,
150}
151
152impl WriteResult {
153    /// Returns `true` if the write was committed
154    #[cfg_attr(feature = "trace", tracing::instrument(level = "debug", skip(self)))]
155    pub fn is_committed(&self) -> bool {
156        matches!(self, WriteResult::Committed)
157    }
158}