commonware_storage/qmdb/store/
mod.rs

1//! Traits for interacting with stores whose state is derived from an append-only log of
2//! state-changing operations.
3//!
4//! # Pruning
5//!
6//! A log based store maintains a location before which all operations are inactive, called the
7//! _inactivity floor_. These operations can be cleaned from storage by calling [PrunableStore::prune].
8
9use crate::{
10    mmr::{Location, Proof},
11    qmdb::Error,
12};
13use commonware_codec::CodecShared;
14use commonware_cryptography::Digest;
15use core::future::Future;
16use std::num::NonZeroU64;
17
18mod batch;
19pub mod db;
20#[cfg(test)]
21pub use batch::tests as batch_tests;
22
23/// Sealed trait for store state types.
24mod private {
25    pub trait Sealed {}
26}
27
28/// Trait for valid store state types.
29pub trait State: private::Sealed + Sized + Send + Sync {}
30
31/// Marker type for a store in a "durable" state (no uncommitted operations).
32#[derive(Clone, Copy, Debug)]
33pub struct Durable;
34
35impl private::Sealed for Durable {}
36impl State for Durable {}
37
38/// Marker type for a store in a "non-durable" state (may contain uncommitted operations).
39#[derive(Clone, Debug, Default)]
40pub struct NonDurable {
41    /// The number of _steps_ to raise the inactivity floor. Each step involves moving exactly one
42    /// active operation to tip.
43    pub(crate) steps: u64,
44}
45
46impl private::Sealed for NonDurable {}
47impl State for NonDurable {}
48
49/// A trait for a store based on an append-only log of operations.
50pub trait LogStore: Send + Sync {
51    type Value: CodecShared + Clone;
52
53    /// Returns true if there are no active keys in the database.
54    fn is_empty(&self) -> bool;
55
56    /// Return [start, end) where `start` and `end - 1` are the Locations of the oldest and newest
57    /// retained operations respectively.
58    fn bounds(&self) -> std::ops::Range<Location>;
59
60    /// Return the Location of the next operation appended to this db.
61    fn size(&self) -> Location {
62        self.bounds().end
63    }
64
65    /// Return the inactivity floor location. This is the location before which all operations are
66    /// known to be inactive. Operations before this point can be safely pruned.
67    fn inactivity_floor_loc(&self) -> Location;
68
69    /// Get the metadata associated with the last commit.
70    fn get_metadata(&self) -> impl Future<Output = Result<Option<Self::Value>, Error>> + Send;
71}
72
73/// A trait for stores that can be pruned.
74pub trait PrunableStore: LogStore {
75    /// Prune historical operations prior to `loc`.
76    fn prune(&mut self, loc: Location) -> impl Future<Output = Result<(), Error>> + Send;
77}
78
79/// A trait for stores that support authentication through merkleization and inclusion proofs.
80pub trait MerkleizedStore: LogStore {
81    /// The digest type used for authentication.
82    type Digest: Digest;
83
84    /// The operation type stored in the log.
85    type Operation;
86
87    /// Returns the root digest of the authenticated store.
88    fn root(&self) -> Self::Digest;
89
90    /// Generate and return:
91    ///  1. a proof of all operations applied to the store in the range starting at (and including)
92    ///     location `start_loc`, and ending at the first of either:
93    ///     - the last operation performed, or
94    ///     - the operation `max_ops` from the start.
95    ///  2. the operations corresponding to the leaves in this range.
96    ///
97    /// # Errors
98    ///
99    /// Returns [crate::mmr::Error::LocationOverflow] if `start_loc` > [crate::mmr::MAX_LOCATION].
100    /// Returns [crate::mmr::Error::RangeOutOfBounds] if `start_loc` >= `op_count`.
101    #[allow(clippy::type_complexity)]
102    fn proof(
103        &self,
104        start_loc: Location,
105        max_ops: NonZeroU64,
106    ) -> impl Future<Output = Result<(Proof<Self::Digest>, Vec<Self::Operation>), Error>> + Send
107    {
108        self.historical_proof(self.bounds().end, start_loc, max_ops)
109    }
110
111    /// Generate and return:
112    ///  1. a proof of all operations applied to the store in the range starting at (and including)
113    ///     location `start_loc`, and ending at the first of either:
114    ///     - the last operation performed, or
115    ///     - the operation `max_ops` from the start.
116    ///  2. the operations corresponding to the leaves in this range.
117    ///
118    /// for the store when it had `historical_size` operations.
119    ///
120    /// # Errors
121    ///
122    /// Returns [crate::mmr::Error::LocationOverflow] if `start_loc` > [crate::mmr::MAX_LOCATION].
123    /// Returns [crate::mmr::Error::RangeOutOfBounds] if `start_loc` >= `op_count`.
124    #[allow(clippy::type_complexity)]
125    fn historical_proof(
126        &self,
127        historical_size: Location,
128        start_loc: Location,
129        max_ops: NonZeroU64,
130    ) -> impl Future<Output = Result<(Proof<Self::Digest>, Vec<Self::Operation>), Error>> + Send;
131}
132
133#[cfg(test)]
134pub(crate) mod tests {
135    use super::{LogStore, MerkleizedStore, PrunableStore};
136    use crate::mmr::Location;
137    use commonware_utils::NZU64;
138
139    pub fn assert_send<T: Send>(_: T) {}
140
141    #[allow(dead_code)]
142    pub fn assert_log_store<T: LogStore>(db: &T) {
143        assert_send(db.get_metadata());
144    }
145
146    #[allow(dead_code)]
147    pub fn assert_prunable_store<T: PrunableStore>(db: &mut T, loc: Location) {
148        assert_send(db.prune(loc));
149    }
150
151    #[allow(dead_code)]
152    pub fn assert_merkleized_store<T: MerkleizedStore>(db: &T, loc: Location) {
153        assert_send(db.proof(loc, NZU64!(1)));
154    }
155}
commonware_storage/qmdb/store/mod.rs

commonware_storage/qmdb/store/
mod.rs
