//! Batch mutation API for Immutable QMDBs. use super::Db; use crate::{ Context, journal::{authenticated, contiguous::Mutable}, merkle::{Family, Location, Proof}, qmdb::{ Error, any::batch::lookup_sorted, chain::{self, Bounds, Commitment, Compatible}, immutable::operation::Operation, operation::Key, value::ValueEncoding, }, translator::Translator, }; use commonware_codec::EncodeShared; use commonware_cryptography::{Digest, Hasher}; use commonware_parallel::Strategy; use commonware_utils::iter::zip_eq; use core::borrow::Borrow; use std::{ collections::BTreeMap, iter, sync::{Arc, Weak}, }; type DiffVec = Vec<(K, DiffEntry)>; /// The value a batch set for a key and the location of that set operation. #[derive(Clone)] pub(crate) struct DiffEntry { pub(crate) value: V, pub(crate) loc: Location, } /// Look up `key` in `diff`, ignoring an entry below the inactivity `floor`. /// /// A reopened database indexes only operations at or above its floor, so batch reads skip /// entries below the floor to answer alike on every database at the same commitment. fn lookup_active<'a, K: Ord, F: Family, V>( diff: &'a [(K, DiffEntry)], key: &K, floor: Location, ) -> Option<&'a DiffEntry> { lookup_sorted(diff, key).filter(|entry| entry.loc >= floor) } /// Result of merkleizing a batch. type MerkleizeResult = Result>, Error>; /// A speculative batch of operations whose root digest has not yet been computed, in contrast /// to [`MerkleizedBatch`]. /// /// Consuming [`UnmerkleizedBatch::merkleize`] produces a merkleized batch. /// Methods that need the DB (e.g. [`get`](Self::get)) accept it as a parameter. #[allow(clippy::type_complexity)] pub struct UnmerkleizedBatch where F: Family, K: Key, V: ValueEncoding, H: Hasher, { /// Metadata for this batch's commit. metadata: Option, /// Application-declared floor, inherited when this batch is created. inactivity_floor: Location, /// Authenticated journal batch for computing the speculative Merkle root. journal_batch: authenticated::UnmerkleizedBatch, S>, /// Pending mutations. mutations: BTreeMap, /// Parent batch in the chain. `None` for batches created directly from the DB. parent: Option>>, /// The state immediately before this batch's operations. /// This batch's i-th operation lands at location `base.size + i`. base: Commitment, } /// Merkleized authenticated-journal batch wrapping an [`Operation`] payload. type JournalBatch = Arc, S>>; /// A speculative batch of operations whose root digest has been computed, in contrast to /// [`UnmerkleizedBatch`]. Reads through it return [`crate::qmdb::Error::StaleRead`] once the /// database is at no state of its chain, for example after a sibling or one of its descendants /// is applied (see [`crate::qmdb::chain`]). #[derive(Clone)] pub struct MerkleizedBatch { /// Authenticated journal batch (Merkle state + local items). pub(super) journal_batch: JournalBatch, /// This batch's local key-level changes only (not accumulated from ancestors). /// Sorted by key with no duplicates; queried via `lookup_sorted` (binary search). pub(super) diff: Arc>, /// The parent batch in the chain, if any. pub(super) parent: Option>, /// Arc refs to the diffs of the reachable ancestors, collected during `merkleize()`. Reads /// consult them (see `read_diffs`), and `apply_batch` applies the unapplied ones. 1:1 with /// `bounds.ancestors` (same length, same ordering). pub(super) ancestor_diffs: Vec>>, /// Position and floor bounds for this batch chain. pub(super) bounds: chain::Bounds, } impl UnmerkleizedBatch where F: Family, K: Key, V: ValueEncoding, H: Hasher, Operation: EncodeShared, { /// Set the metadata recorded in this batch's commit. Defaults to `None` and is not inherited by /// child batches. pub fn with_metadata(mut self, metadata: impl Into>) -> Self { self.metadata = metadata.into(); self } /// Set the inactivity floor recorded in this batch's commit. Defaults to the database or parent /// batch's floor when the batch is created. /// /// The floor must be at least the parent batch's (or database's) floor and at most this /// batch's commit location. Merkleizing the batch checks both bounds. pub const fn with_inactivity_floor(mut self, floor: Location) -> Self { self.inactivity_floor = floor; self } /// The database boundary for this batch chain. /// /// A batch created from the database uses its base. A child inherits its parent's `db`. fn db(&self) -> Commitment { self.parent .as_ref() .map_or(self.base, |parent| parent.bounds.db) } /// The inactivity floor this batch builds on: its parent's, or `db`'s for a batch with no /// parent. fn floor(&self, db: &Db) -> Location where E: Context, C: Mutable>, C::Item: EncodeShared, T: Translator, { self.parent.as_ref().map_or_else( || db.inactivity_floor(), |parent| parent.bounds.inactivity_floor, ) } /// Check that `db` is at a state of this batch's chain and return the [`Compatible`] /// witness that database reads require. #[allow(clippy::type_complexity)] fn compatible<'a, E, C, T>( &self, db: &'a Db, ) -> Result>, Error> where E: Context, C: Mutable>, C::Item: EncodeShared, T: Translator, { self.parent.as_ref().map_or_else( || self.base.compatible(db, db.commitment()), |parent| parent.bounds.compatible(db, db.commitment()), ) } /// Set a key to a value. /// /// The key must not already be set in the database history or in any ancestor batch. pub fn set(mut self, key: K, value: V::Value) -> Self { self.mutations.insert(key, value); self } /// Read through: mutations -> ancestor diffs -> database. /// /// Only operations at or above the inactivity floor this batch builds on are read, so every /// database at the same commitment answers alike, however far it has pruned. /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain. pub async fn get( &self, key: &K, db: &Db, ) -> Result, Error> where E: Context, C: Mutable>, C::Item: EncodeShared, T: Translator, { let db = self.compatible(db)?; // Check this batch's pending mutations. if let Some(value) = self.mutations.get(key) { return Ok(Some(value.clone())); } let floor = self.floor(&*db); if let Some(parent) = self.parent.as_ref() { for diff in parent.read_diffs(db.bounds().end) { if let Some(entry) = lookup_active(diff, key, floor) { return Ok(Some(entry.value.clone())); } } } // Fall through to base DB. db.get_from(key, floor).await } /// Batch read multiple keys. /// /// Returns results in the same order as the input keys, matching [`Self::get`] for each key. /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain. pub async fn get_many( &self, keys: &[impl Borrow + Sync], db: &Db, ) -> Result>, Error> where E: Context, C: Mutable>, C::Item: EncodeShared, T: Translator, { let db = self.compatible(db)?; if keys.is_empty() { return Ok(Vec::new()); } let floor = self.floor(&*db); let mut results: Vec> = Vec::with_capacity(keys.len()); let mut db_indices = Vec::new(); let mut db_keys = Vec::new(); for (i, key) in keys.iter().enumerate() { let key = key.borrow(); // Check local mutations. if let Some(value) = self.mutations.get(key) { results.push(Some(value.clone())); continue; } // Check the parent's retained diff chain. if let Some(entry) = self.parent.as_ref().and_then(|parent| { parent .read_diffs(db.bounds().end) .find_map(|diff| lookup_active(diff, key, floor)) }) { results.push(Some(entry.value.clone())); continue; } // Need DB fallthrough. db_indices.push(i); db_keys.push(key); results.push(None); } if !db_keys.is_empty() { let db_results = db.get_many_from(&db_keys, floor).await?; for (slot, value) in zip_eq(db_indices, db_results) { results[slot] = value; } } Ok(results) } /// Resolve mutations into operations and return a merkleized batch. /// /// The commit records the batch's inactivity floor (see [`Self::with_inactivity_floor`]), which /// declares every operation before it inactive. /// /// # Errors /// /// - Returns [`Error::StaleBatch`] if `db` is not at a state of this batch's chain or an /// unapplied ancestor was dropped. /// - Returns [`Error::FloorRegressed`] if `inactivity_floor` is below the floor this batch /// builds on, and [`Error::FloorBeyondCommit`] if it is past the commit location. #[tracing::instrument(name = "qmdb.immutable.batch.merkleize", level = "info", skip_all)] pub async fn merkleize( mut self, db: &Db, ) -> MerkleizeResult where E: Context, C: Mutable>, C::Item: EncodeShared, T: Translator, { let metadata = self.metadata.take(); let inactivity_floor = self.inactivity_floor; let base = self.base.size; let live_ancestors: Vec<_> = chain::parent_and_ancestors(self.parent.as_ref(), |parent| parent.ancestors()) .collect(); let boundary = chain::effective_boundary( self.db(), live_ancestors.last().map(|oldest| oldest.bounds.base), ); // Compute the batch chain bounds. let mut ancestor_diffs = Vec::new(); let mut ancestors = Vec::new(); for batch in &live_ancestors { ancestor_diffs.push(Arc::clone(&batch.diff)); ancestors.push(batch.commitment()); } let db = chain::merkleizable(db, db.commitment(), boundary, ancestors.iter().copied())?; let start_floor = self.floor(&*db); // Build operations: one Set per key, then Commit. `self.mutations` is a BTreeMap, so // iteration yields keys in sorted order, which `diff` relies on for binary search. let mut ops: Vec> = Vec::with_capacity(self.mutations.len() + 1); let mut diff: DiffVec = Vec::with_capacity(self.mutations.len()); for (key, value) in self.mutations { let loc = base + ops.len() as u64; ops.push(Operation::Set(key.clone(), value.clone())); diff.push((key, DiffEntry { value, loc })); } ops.push(Operation::Commit(metadata, inactivity_floor)); let total_size = base + ops.len() as u64; chain::validate_merkleize_floor::(start_floor, inactivity_floor, total_size - 1)?; let inactive_peaks = F::inactive_peaks(total_size, inactivity_floor); // Leaf and node hashing dominate merkleization, so run them as one job through the // strategy (see `Journal::merkleize`). let (journal, root) = db .journal .merkleize(self.journal_batch, ops, inactive_peaks) .await?; // Hold ancestor batches until the journal has captured their operations and nodes. drop(live_ancestors); Ok(Arc::new(MerkleizedBatch { journal_batch: journal, diff: Arc::new(diff), parent: self.parent.as_ref().map(Arc::downgrade), ancestor_diffs, bounds: chain::Bounds { base: self.base, db: boundary, tip: Commitment { size: total_size, root, }, ancestors, inactivity_floor, }, })) } } impl MerkleizedBatch where Operation: EncodeShared, { /// Return the speculative root. pub const fn root(&self) -> D { self.bounds.tip.root } /// Return the [`Bounds`] of the batch. pub const fn bounds(&self) -> &Bounds { &self.bounds } /// Return the operations this batch appends to the log and the location of the first. #[allow(clippy::type_complexity)] pub fn operations(&self) -> (Location, Arc>>) { ( self.bounds.base.size, Arc::clone(self.journal_batch.items()), ) } /// Inclusion proof for the operations returned by [`Self::operations`], anchored at /// this batch's tip. The pair verifies against [`Self::root`] via /// [`crate::qmdb::ProofExt::verify`]. Together with [`Self::pinned_nodes`] they verify via /// [`crate::qmdb::ProofExt::verify_with_pinned_nodes`]. /// /// Nodes appended by unapplied ancestors come from the records this batch retained when it /// was merkleized. Nodes below the chain are read from `db`'s /// [Merkle store][crate::merkle::mem::Mem], which retains them at least until this batch's /// changes are flushed (by a commit or sync after apply). /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain, /// [`crate::merkle::Error::ElementPruned`] if a required node has been pruned, and /// [`crate::merkle::Error::Empty`] if the batch has no operations (such as a batch from /// [`Db::to_batch`]). pub fn proof( &self, db: &Db, ) -> Result, Error> where E: Context, C: Mutable>, H: Hasher, T: Translator, { let db = self.bounds.compatible(db, db.commitment())?; let inactive_peaks = F::inactive_peaks(self.bounds.tip.size, self.bounds.inactivity_floor); db.journal .speculative_proof(&self.journal_batch, inactive_peaks) .map_err(Into::into) } /// The Merkle frontier at the first operation returned by [`Self::operations`] /// ([`Family::nodes_to_pin`]), which lets a consumer holding only this batch's base rebuild /// compact state and replay the operations. The operations, [`Self::proof`], and pinned /// nodes verify against [`Self::root`] via [`crate::qmdb::ProofExt::verify_with_pinned_nodes`]. /// /// Nodes appended by unapplied ancestors come from the records this batch retained when it /// was merkleized. Nodes below the chain are read from `db`'s /// [Merkle store][crate::merkle::mem::Mem], which retains them at least until this batch's /// changes are flushed (by a commit or sync after apply). /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain, and /// [`crate::merkle::Error::ElementPruned`] if a required node has been pruned. pub fn pinned_nodes( &self, db: &Db, ) -> Result, Error> where E: Context, C: Mutable>, H: Hasher, T: Translator, { let db = self.bounds.compatible(db, db.commitment())?; db.journal .speculative_pinned_nodes(&self.journal_batch) .map_err(Into::into) } /// Yield this batch's diff, then the ancestor diffs a read consults before a compatible /// database at `db_size` operations: each reachable or unapplied ancestor's, newest first. /// /// The walk ends at the first ancestor that is both unreachable and applied. The database /// holds that ancestor's writes and every older layer's. A reachable applied ancestor stays in /// the walk so its writes resolve from memory. The batch keeps every retained diff, because a /// bounded initialization can make those layers unapplied again. fn read_diffs( &self, db_size: Location, ) -> impl Iterator)]> { let mut reachable = iter::once_with(|| self.ancestors()).flatten(); iter::once(self.diff.as_slice()).chain( self.ancestor_diffs .iter() .zip(&self.bounds.ancestors) .take_while(move |(_, state)| reachable.next().is_some() || state.size > db_size) .map(|(diff, _)| diff.as_slice()), ) } /// Iterate over ancestor batches (parent first, then grandparent, etc.). pub(super) fn ancestors(&self) -> impl Iterator> + use { chain::ancestors(self.parent.clone(), |batch| batch.parent.as_ref()) } /// The [`Commitment`] this batch commits to. pub(super) const fn commitment(&self) -> Commitment { self.bounds.tip } /// Read through: local diff -> ancestor diffs -> database. /// /// Only operations at or above this batch's inactivity floor are read, so every database at /// the same commitment answers alike, however far it has pruned. /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain. pub async fn get( &self, key: &K, db: &Db, ) -> Result, Error> where E: Context, C: Mutable>, C::Item: EncodeShared, H: Hasher, T: Translator, { let db = self.bounds.compatible(db, db.commitment())?; let floor = self.bounds.inactivity_floor; for diff in self.read_diffs(db.bounds().end) { if let Some(entry) = lookup_active(diff, key, floor) { return Ok(Some(entry.value.clone())); } } db.get_from(key, floor).await } /// Batch read multiple keys. /// /// Returns results in the same order as the input keys, matching [`Self::get`] for each key. /// /// # Errors /// /// Returns [`Error::StaleRead`] if `db` is not at a state of this batch's chain. pub async fn get_many( &self, keys: &[impl Borrow + Sync], db: &Db, ) -> Result>, Error> where E: Context, C: Mutable>, C::Item: EncodeShared, H: Hasher, T: Translator, { let db = self.bounds.compatible(db, db.commitment())?; if keys.is_empty() { return Ok(Vec::new()); } let floor = self.bounds.inactivity_floor; let mut results: Vec> = Vec::with_capacity(keys.len()); let mut db_indices = Vec::new(); let mut db_keys = Vec::new(); for (i, key) in keys.iter().enumerate() { let key = key.borrow(); if let Some(entry) = self .read_diffs(db.bounds().end) .find_map(|diff| lookup_active(diff, key, floor)) { results.push(Some(entry.value.clone())); continue; } // Need DB fallthrough. db_indices.push(i); db_keys.push(key); results.push(None); } if !db_keys.is_empty() { let db_results = db.get_many_from(&db_keys, floor).await?; for (slot, value) in zip_eq(db_indices, db_results) { results[slot] = value; } } Ok(results) } /// Create a new speculative batch of operations with this batch as its parent. /// /// Every unapplied ancestor in the chain must be held until the child (or any descendant) is /// merkleized. Otherwise, `merkleize` returns [`Error::StaleBatch`]. /// /// A child can be created from a stale parent. While the database is at none of the chain's /// states, the child's reads return [`Error::StaleRead`], and merkleizing it returns /// [`Error::StaleBatch`]. pub fn new_batch(self: &Arc) -> UnmerkleizedBatch where H: Hasher, { UnmerkleizedBatch { journal_batch: self.journal_batch.new_batch::(), mutations: BTreeMap::new(), parent: Some(Arc::clone(self)), metadata: None, inactivity_floor: self.bounds.inactivity_floor, base: self.commitment(), } } } impl Db where F: Family, E: Context, K: Key, V: ValueEncoding, C: Mutable>, C::Item: EncodeShared, H: Hasher, T: Translator, S: Strategy, { /// Create a new speculative batch of operations with this database as its parent. pub fn new_batch(&self) -> UnmerkleizedBatch { UnmerkleizedBatch { journal_batch: self.journal.new_batch(), mutations: BTreeMap::new(), parent: None, metadata: None, inactivity_floor: self.inactivity_floor_loc, base: self.commitment(), } } /// Create an initial [`MerkleizedBatch`] from the DB's current state. pub fn to_batch(&self) -> Arc> { Arc::new(MerkleizedBatch { journal_batch: self.journal.to_merkleized_batch(), diff: Arc::new(Vec::new()), parent: None, ancestor_diffs: Vec::new(), bounds: chain::Bounds::from_db(self.commitment(), self.inactivity_floor_loc), }) } } impl crate::qmdb::sync::MerkleizedBatch for MerkleizedBatch where Operation: EncodeShared, { type Family = F; type Digest = D; fn root(&self) -> D { self.root() } fn target(&self) -> crate::qmdb::sync::Target { crate::qmdb::sync::Target { root: self.root(), range: commonware_utils::non_empty_range!( self.bounds.inactivity_floor, self.bounds.tip.size ), } } }