//! Rebuild snapshot indexes and activity bitmaps from the operations log. use super::{Error, cache::Cache}; use crate::{ index::{ Cursor, Unordered as Index, partitioned::{PartitionRange, Partitioned}, }, journal::{ authenticated::{Chunk, ChunkHasher, LeafSink}, contiguous::Contiguous, }, merkle::{self, Family, Location, hasher::Hasher as MerkleHasher}, qmdb::operation::{Committable, Operation}, translator::Translator, }; use commonware_codec::Encode; use commonware_runtime::{AbortOnDrop, ReadOptions, Spawner}; use commonware_utils::{ bitmap::{Atomic, BitMap}, channel::mpsc, prefetch::Lookahead, }; use core::{convert::Infallible, num::NonZeroUsize, ops::Range}; use futures::{StreamExt as _, pin_mut}; use std::{collections::VecDeque, sync::Arc}; /// Builds the database's snapshot by replaying the log starting at the inactivity floor. Assumes /// the log is not pruned beyond the inactivity floor. The callback is invoked for each replayed /// operation, indicating activity status updates. The first argument of the callback is the /// activity status of the operation, and the second argument is the location of the operation it /// inactivates (if any). Returns the number of active keys in the db. /// /// `init_buffer` sizes the replay read buffer (in bytes). `cache_size` bounds a /// `(location -> key)` cache that lets collision resolution resolve candidates from memory /// instead of re-reading the log; `None` disables it. pub(crate) async fn build_snapshot_from_log( inactivity_floor_loc: crate::merkle::Location, reader: &C, snapshot: &mut I, init_buffer: NonZeroUsize, cache_size: Option, mut callback: Fn, ) -> Result> where F: crate::merkle::Family, C: Contiguous>, I: Index>, Fn: FnMut(bool, Option>), { let bounds = reader.bounds(); // Init reads every operation once, so the replayed pages are not kept in the OS page cache: // the init cache, not the OS cache, decides which probes hit. let stream = reader .replay( *inactivity_floor_loc..bounds.end, init_buffer, ReadOptions::DONT_CACHE, ) .await?; pin_mut!(stream); let last_commit_loc = bounds.end.saturating_sub(1); // Memoize `(location -> key)` for replayed update ops so collision resolution in // `find_update_op` resolves candidates from memory instead of re-reading (and re-decoding) the // log. let mut cache = cache_size.map(Cache::<>::Key>::new); let mut active_keys: usize = 0; while let Some(batch) = stream.next().await { for (loc, op) in batch? { if let Some(key) = op.key() { if op.is_delete() { let old_loc = delete_key(snapshot, reader, key, cache.as_mut()).await?; callback(false, old_loc); if old_loc.is_some() { active_keys -= 1; } } else if op.is_update() { let new_loc = crate::merkle::Location::new(loc); let old_loc = update_key(snapshot, reader, key, new_loc, cache.as_mut()).await?; callback(true, old_loc); if old_loc.is_none() { active_keys += 1; } // This update op is now a `find_update_op` candidate for later ops of its // key. if let Some(cache) = cache.as_mut() { cache.put(loc, op.into_key().expect("operation without key")); } } } else if op.is_commit() { callback(loc == last_commit_loc, None); } } } Ok(active_keys) } /// Delete `key` from the snapshot if it exists, using a stable log reader, and return the /// previously associated location. pub(super) async fn delete_key( snapshot: &mut I, reader: &R, key: &>::Key, cache: Option<&mut Cache<>::Key>>, ) -> Result>, Error> where F: Family, I: Index>, R: Contiguous, R::Item: Operation, { // If the translated key is in the snapshot, get a cursor to look for the key. let Some(cursor) = snapshot.get_mut(key.as_ref()) else { return Ok(None); }; delete_at_cursor::(cursor, reader, key, cache).await } /// Delete `key` at `cursor` (obtained from a `get_mut` lookup of `key`), returning its location if /// it was present among the cursor's conflicts. When supplied, the matched location is removed /// from `cache` with the snapshot deletion. async fn delete_at_cursor( mut cursor: C, reader: &R, key: &>::Key, mut cache: Option<&mut Cache<>::Key>>, ) -> Result>, Error> where F: Family, C: Cursor>, R: Contiguous, R::Item: Operation, { // Find the matching key among all conflicts, then delete it. let Some(loc) = find_update_op::(reader, &mut cursor, key, cache.as_deref_mut()).await? else { return Ok(None); }; // Cache entries mirror current snapshot locations, so invalidate the matched location with // the authoritative deletion. cursor.delete(); if let Some(cache) = cache { cache.remove(*loc); } Ok(Some(loc)) } /// Update `key` in the snapshot using a stable log reader, returning its old location if present. pub(super) async fn update_key( snapshot: &mut I, reader: &R, key: &>::Key, new_loc: Location, cache: Option<&mut Cache<>::Key>>, ) -> Result>, Error> where F: Family, I: Index>, R: Contiguous, R::Item: Operation, { // If the translated key is not in the snapshot, insert the new location. Otherwise, get a // cursor to look for the key. let Some(cursor) = snapshot.get_mut_or_insert(key.as_ref(), new_loc) else { return Ok(None); }; update_at_cursor::(cursor, reader, key, new_loc, cache).await } /// Update `key` to `new_loc` at `cursor` (obtained from a `get_mut_or_insert` lookup of `key`), /// returning its old location if it was present among the cursor's conflicts; otherwise `new_loc` /// is inserted at the cursor. When supplied, the matched old location is removed from `cache` with /// the snapshot update. async fn update_at_cursor( mut cursor: C, reader: &R, key: &>::Key, new_loc: Location, mut cache: Option<&mut Cache<>::Key>>, ) -> Result>, Error> where F: Family, C: Cursor>, R: Contiguous, R::Item: Operation, { // Find the matching key among all conflicts, then update its location. if let Some(loc) = find_update_op::(reader, &mut cursor, key, cache.as_deref_mut()).await? { // Removing the superseded cache entry with the snapshot update lets the caller reuse its // slot for `new_loc` instead of evicting another entry. assert!(new_loc > loc); cursor.update(new_loc); if let Some(cache) = cache { cache.remove(*loc); } return Ok(Some(loc)); } // The key wasn't in the snapshot, so add it to the cursor. cursor.insert(new_loc); Ok(None) } /// Find and return the location of the update operation for `key`, if it exists. The cursor is /// positioned at the matching location, and can be used to update or delete the key. async fn find_update_op( reader: &R, cursor: &mut impl Cursor>, key: &>::Key, mut cache: Option<&mut Cache<>::Key>>, ) -> Result>, Error> where F: Family, R: Contiguous, R::Item: Operation, { while let Some(&loc) = cursor.next() { // Consult the cache first; on a miss, read the log and populate. let matches = if let Some(k) = cache.as_deref().and_then(|c| c.get(*loc)) { *k == *key } else { let op = reader.read(*loc).await?; let k = op.key().expect("operation without key"); let matches = *k == *key; // Every caller immediately mutates a match. Admitting it here could evict another // cached location before the caller invalidates this one. if !matches && let Some(cache) = cache.as_deref_mut() { cache.put(*loc, op.into_key().expect("operation without key")); } matches }; if matches { return Ok(Some(loc)); } } Ok(None) } /// Bounded depth (in batches) of each per-worker channel during a parallel build. Backpressure keeps /// the replay from running arbitrarily far ahead of a slow worker. const SNAPSHOT_CHANNEL_DEPTH: usize = 4; /// A batch of keyed operations routed to a snapshot-build worker: each entry is the op's key, its /// location, and whether it is a delete. type RoutedBatch = Vec<(K, u64, bool)>; /// Parameters shared by the inline replay and decode chunks of one parallel build. #[derive(Clone, Copy)] struct SnapshotRouting { /// Number of insert workers routed to. workers: usize, /// Maps a key to its index partition. partition_of: fn(&[u8]) -> usize, /// Partitions per worker range: worker = `partition_of(key) / range_size`. range_size: usize, /// Replay read-buffer size in bytes. init_buffer: NonZeroUsize, } /// Number of operations the snapshot replay batches per worker-channel send during a parallel /// build. Build throughput is mostly insensitive to this value, so it is a constant rather than /// configuration. Small in tests so ordinary logs exercise batch boundaries. #[cfg(not(test))] const SNAPSHOT_ROUTE_BATCH: usize = 4096; #[cfg(test)] const SNAPSHOT_ROUTE_BATCH: usize = 3; /// Operations ahead of its insert at which a parallel-build worker hints an operation's partition /// entries. The partition's header is hinted twice as far ahead. One in tests, so the hints reach /// their steady state within a [SNAPSHOT_ROUTE_BATCH]. #[cfg(not(test))] const PREFETCH_DISTANCE: usize = 16; #[cfg(test)] const PREFETCH_DISTANCE: usize = 1; /// Operations per decode chunk in a parallel build. Decoding the replay stream is the build's /// serial bottleneck at large sizes, so contiguous chunks of this many locations are decoded (and /// partition-routed) on concurrent tasks while the coordinator forwards finished chunks in position /// order. Together with the decoder count, this bounds the queued operations. Each decoder also /// reserves one batch per worker. Small in tests so ordinary logs exercise chunk boundaries. #[cfg(not(test))] const SNAPSHOT_DECODE_CHUNK: u64 = 1 << 17; #[cfg(test)] const SNAPSHOT_DECODE_CHUNK: u64 = 64; /// What a parallel build's decode task does with each operation of its chunk besides routing it. trait ChunkVisitor: Send + 'static { /// The chunk's result, passed on in position order once the chunk is routed. type Output: Send + 'static; /// See the chunk's next operation, in position order. fn visit(&mut self, item: &Item); /// The chunk's result, once every operation in it has been visited. fn finish(self) -> Result>; } impl ChunkVisitor for () { type Output = (); fn visit(&mut self, _: &Item) {} fn finish(self) -> Result<(), merkle::Error> { Ok(()) } } impl + 'static, Item: Encode> ChunkVisitor for ChunkHasher { type Output = Chunk; fn visit(&mut self, item: &Item) { Self::push(self, item); } fn finish(self) -> Result> { Self::finish(self) } } /// The operations a parallel build decodes, and what its decode tasks do with them besides routing /// those at or after the floor. They do nothing more, or hash them for the journal's Merkle /// structure. trait Scan: Send + Sync { type Visitor: ChunkVisitor; /// The chunks to decode, in position order, for a build from `floor` to `end`. fn chunks(&self, floor: u64, end: u64) -> impl Iterator> + Send + 'static; /// The visitor of `chunk`, one of [Self::chunks], that its decode task calls. fn visitor(&self, chunk: Range) -> Self::Visitor; /// Pass a routed chunk's result on. Returns false to stop the build. fn send( &self, output: >::Output, ) -> impl Future + Send; } /// A build that only routes, decoding from the floor. struct IndexOnly; impl Scan for IndexOnly { type Visitor = (); fn chunks(&self, floor: u64, end: u64) -> impl Iterator> + Send + 'static { (floor..end) .step_by(usize::try_from(SNAPSHOT_DECODE_CHUNK).expect("chunk size fits usize")) .map(move |start| start..(start + SNAPSHOT_DECODE_CHUNK).min(end)) } fn visitor(&self, _: Range) {} async fn send(&self, _: ()) -> bool { true } } /// A build that also hashes every operation from the journal's boundary, in the journal's chunks. impl + 'static, Item: Encode> Scan for LeafSink { type Visitor = ChunkHasher; // Starts at the journal's pruning boundary, which initialization keeps at or before the floor. fn chunks(&self, _: u64, _: u64) -> impl Iterator> + Send + 'static { Self::chunks(self) } fn visitor(&self, chunk: Range) -> ChunkHasher { self.chunk_hasher(chunk) } async fn send(&self, chunk: Chunk) -> bool { Self::send(self, chunk).await } } /// Replay `range` and send each worker's keyed operations at or after `floor` in log order, in /// batches of at most [SNAPSHOT_ROUTE_BATCH] operations. `visitor` sees every replayed operation, /// including those before `floor`. /// /// Stop if `send` returns false. The caller owns the receiving tasks and observes their errors when /// joining them. async fn route_snapshot( log: &C, range: Range, floor: u64, routing: SnapshotRouting, visitor: &mut T, mut send: impl FnMut(usize, RoutedBatch<>::Key>) -> Fut + Send, ) -> Result<(), Error> where F: Family, C: Contiguous>, T: ChunkVisitor, Fut: Future + Send, { // Init reads every operation once, so the replayed pages are not kept in the OS page cache: // the init cache, not the OS cache, decides which probes hit. let stream = log .replay(range, routing.init_buffer, ReadOptions::DONT_CACHE) .await?; pin_mut!(stream); let mut batches: Vec> = (0..routing.workers) .map(|_| Vec::with_capacity(SNAPSHOT_ROUTE_BATCH)) .collect(); while let Some(batch) = stream.next().await { for (loc, op) in batch? { visitor.visit(&op); if loc < floor { continue; } let is_delete = op.is_delete(); let Some(key) = op.into_key() else { continue }; let w = (routing.partition_of)(key.as_ref()) / routing.range_size; batches[w].push((key, loc, is_delete)); if batches[w].len() >= SNAPSHOT_ROUTE_BATCH { let routed = std::mem::replace(&mut batches[w], Vec::with_capacity(SNAPSHOT_ROUTE_BATCH)); if !send(w, routed).await { return Ok(()); } } } } // Flush remaining batches before the caller closes the channels. for (w, batch) in batches.into_iter().enumerate() { if !batch.is_empty() && !send(w, batch).await { break; } } Ok(()) } /// Build one parallel-init worker's partial snapshot: apply the routed operations (streamed in log /// order over `rx`) to `index`, resolving translated-key collisions with the worker's own log /// `reader` and `(location -> key)` cache. Sets the bits of the range's active locations in the /// shared `active` bitmap (indexed over `activity`, the replayed region) and returns the populated /// worker index along with the range's active-key count. async fn build_snapshot_worker( log: Arc, mut rx: mpsc::Receiver>::Key>>, mut index: R, activity: Range, active: Arc, cache_size: Option, ) -> Result<(R, usize), Error> where F: Family, C: Contiguous>, R: PartitionRange>, { let mut cache = cache_size.map(Cache::<>::Key>::new); // Ops are software pipelined so the cache misses of their partition lookups and cache inserts // overlap. Before op `k` is applied, the loop hints the header of op `k + 2 * D` and the // entries and cache set of op `k + D` (`D = PREFETCH_DISTANCE`), so each op's loads are // issued in three steps: // // applying op: k-2D .......... k-D ........... k // header of op k: hinted -------> read by prefetch_entries // entries of op k: hinted -------> read by the insert // cache set of op k: hinted -------> scanned by put // // The header holds the entries' addresses, so their hint can only be issued once it has // landed. while let Some(batch) = rx.recv().await { let mut ops = batch.into_iter(); let mut headers = Lookahead::new(2 * PREFETCH_DISTANCE); let mut entries = Lookahead::new(PREFETCH_DISTANCE); loop { for (key, _, _) in headers.advance(ops.as_slice()) { index.prefetch_header(key.as_ref()); } for (key, loc, is_delete) in entries.advance(ops.as_slice()) { index.prefetch_entries(key.as_ref()); if !is_delete && let Some(cache) = &cache { cache.prefetch(*loc); } } let Some((key, loc, is_delete)) = ops.next() else { break; }; if is_delete { if let Some(cursor) = index.get_mut(key.as_ref()) { delete_at_cursor::(cursor, &*log, &key, cache.as_mut()).await?; } } else { let new_loc = Location::new(loc); if let Some(cursor) = index.get_mut_or_insert(key.as_ref(), new_loc) { update_at_cursor::(cursor, &*log, &key, new_loc, cache.as_mut()) .await?; } // This update op is now a `find_update_op` candidate for later ops of its key. // `key` is owned by this batch and unused after the update, so move it in. if let Some(cache) = cache.as_mut() { cache.put(loc, key); } } } } // Reconstruct this range's share of the activity bitmap (in parallel with the other workers) // and count the active keys. Locations are partitioned across workers, so every bit has a // single writer. let mut active_keys = 0; index.for_each_value(|loc| { active.set(**loc - activity.start); active_keys += 1; }); Ok((index, active_keys)) } /// Build a snapshot serially on the calling task via [build_snapshot_from_log], collecting each /// replayed location's activity status into a [BitMap]. Returns the number of active keys and the /// activity bitmap (see [Rebuild::build_snapshot]). async fn build_snapshot_serial( inactivity_floor_loc: Location, reader: &C, snapshot: &mut I, init_buffer: NonZeroUsize, cache_size: Option, ) -> Result<(usize, BitMap), Error> where F: Family, C: Contiguous>, I: Index>, { // Track per-op transitions locally: push each op's status and clear the bit of any location it // supersedes. The state after the last op is each location's final status. let mut activity = BitMap::new(); let floor = *inactivity_floor_loc; let active_keys = build_snapshot_from_log( inactivity_floor_loc, reader, snapshot, init_buffer, cache_size, |is_active, old_loc| { activity.push(is_active); if let Some(loc) = old_loc { activity.set(*loc - floor, false); } }, ) .await?; Ok((active_keys, activity)) } /// Worker counts, partition ranges, and cache allocation for a parallel snapshot build. pub struct ParallelPlan { /// Total partitions to distribute. partitions: usize, /// Concurrent decode tasks. Zero means the coordinator decodes inline. decoders: usize, /// Insert workers, each owning a nonempty partition range. workers: usize, /// Maximum partitions per worker. Partition `p` routes to worker `p / range_size`. range_size: usize, /// Cache entries per worker. `None` disables caching, including when the share rounds to zero. per_worker_cache: Option, } impl ParallelPlan { /// Plan the worker allocation, or return `None` to build serially. fn new( partitions: usize, init_concurrency: NonZeroUsize, cache_size: Option, ) -> Option { let concurrency = init_concurrency.get(); // Split the budget between decode tasks and insert workers. Inserts cost more CPU than // decoding. Across widths on both journal types, throughput peaks near two decoders per // five tasks. let (decoders, workers) = if concurrency <= 3 { // Two decoders need a budget of at least four, since a lone decoder starves the // workers. Below that, the coordinator decodes inline and takes one slot. (0, concurrency - 1) } else { // Spawned decoders leave the coordinator only forwarding, so it takes no slot. // Divide before multiplying to preserve the ratio without overflowing large budgets. let share = concurrency / 5 * 2 + concurrency % 5 * 2 / 5; let decoders = share.max(2).min(concurrency / 2); (decoders, concurrency - decoders) }; let workers = workers.min(partitions); if workers == 0 { return None; } let range_size = partitions.div_ceil(workers); // `range_size` rounds up, so the last ranges could start at or past `partitions`. Reduce // `workers` to the number of non-empty ranges: every spawned worker then owns at least one // partition and routing (`partition / range_size`) stays in `[0, workers)`. let workers = partitions.div_ceil(range_size); let per_worker_cache = cache_size.and_then(|n| NonZeroUsize::new(n.get() / workers)); Some(Self { partitions, decoders, workers, range_size, per_worker_cache, }) } /// Like [Self::new], but for a build whose decode tasks also hash the journal's operations. /// Hashing costs more than routing, so all `init_concurrency` tasks decode, beside the insert /// workers [Self::new] plans. fn hashing( partitions: usize, init_concurrency: NonZeroUsize, cache_size: Option, ) -> Option { let plan = Self::new(partitions, init_concurrency, cache_size)?; Some(Self { decoders: init_concurrency.get(), ..plan }) } /// Each worker's starting partition and partition count, in worker order. fn ranges(&self) -> impl ExactSizeIterator + '_ { (0..self.workers).map(|worker| { let lo = worker * self.range_size; let len = self.range_size.min(self.partitions - lo); (lo, len) }) } } /// Build a snapshot by decoding the log replay in contiguous chunks on concurrent decode tasks /// and routing each keyed operation to the parallel insert worker owning its partition range /// (see [Partitioned]). Returns the number of active keys and the activity bitmap (see /// [Rebuild::build_snapshot]). async fn build_snapshot_parallel( snapshot: &mut I, plan: ParallelPlan, context: E, inactivity_floor_loc: Location, log: &Arc, init_buffer: NonZeroUsize, scan: S, ) -> Result<(usize, BitMap), Error> where F: Family, E: Spawner, C: Contiguous> + 'static, I: Partitioned + Index>, S: Scan, { let floor = *inactivity_floor_loc; let end = log.bounds().end; // All workers share one atomic bitmap to track the activity bits. let active = Arc::new(Atomic::zeroes(end - floor)); // Spawn one worker per contiguous partition range, each owning its own reader and cache. let mut senders = Vec::with_capacity(plan.workers); let mut handles = Vec::with_capacity(plan.workers); let per_worker_cache = plan.per_worker_cache; for (w, (lo, range_len)) in plan.ranges().enumerate() { let (tx, rx) = mpsc::channel(SNAPSHOT_CHANNEL_DEPTH); senders.push(tx); let log = log.clone(); // This worker owns the contiguous partition range [lo, lo + range_len). It allocates // only that many slots, so per-worker memory is the range, not the full partition set. let worker_index = snapshot.new_range(lo, range_len); let active = active.clone(); let handle = context .child("snapshot_worker") .with_attribute("worker", w) .dedicated() .spawn(move |_| { build_snapshot_worker::( log, rx, worker_index, floor..end, active, per_worker_cache, ) }); handles.push(handle.abort_on_drop()); } // Route each replayed op to the worker owning its partition, forwarding decoded chunks in // position order to preserve the per-worker op order the insert path relies on. Routing runs in // an inner future so a failure here still drains the workers below rather than leaving them // running detached. // // A closed worker channel means that worker terminated early (e.g. returned an `Error` while // resolving a collision). Routing stops on the first such send failure and the join below // surfaces that worker's error, rather than panicking on the send. let mut pending = VecDeque::new(); let routing = SnapshotRouting { workers: plan.workers, partition_of: I::partition_of, range_size: plan.range_size, init_buffer, }; let routing_result: Result<(), Error> = async { // With no decode tasks, decode and route on this task over one continuous replay to avoid // per-chunk buffered-reader overhead (measured 265s vs 369s on a 1.66B-op log). if plan.decoders == 0 { let senders = &senders; return route_snapshot::( &**log, floor..end, floor, routing, &mut (), |w, batch| async move { senders[w].send(batch).await.is_ok() }, ) .await; } let mut chunks = scan.chunks(floor, end); let mut spawn_next = |pending: &mut VecDeque<_>| { let Some(chunk) = chunks.next() else { return false; }; let log = log.clone(); let mut visitor = scan.visitor(chunk.clone()); // Each chunk's channel holds the whole chunk (full sub-batches plus a final partial // per worker), so every decoder can finish regardless of which chunk is being // forwarded. let capacity = (chunk.end - chunk.start) as usize / SNAPSHOT_ROUTE_BATCH + plan.workers; let (tx, rx) = mpsc::channel(capacity); let handle = context .child("snapshot_decoder") .dedicated() .spawn(move |_| async move { let tx = &tx; route_snapshot::( &*log, chunk, floor, routing, &mut visitor, |w, batch| async move { tx.send((w, batch)).await.is_ok() }, ) .await?; Ok::<_, Error>(visitor.finish()?) }); pending.push_back((rx, handle.abort_on_drop())); true }; // Start decoding ahead of forwarding, with at most `plan.decoders` chunks in flight. for _ in 0..plan.decoders { if !spawn_next(&mut pending) { break; } } // Workers need operations in log order even when later chunks finish decoding first. // Reuse each decoder slot only after forwarding its chunk and joining its task. while let Some((rx, _)) = pending.front_mut() { while let Some((w, batch)) = rx.recv().await { if senders[w].send(batch).await.is_err() { return Ok(()); } } let (_, decoder) = pending.pop_front().expect("front exists"); let output = decoder.join().await??; spawn_next(&mut pending); if !scan.send(output).await { return Ok(()); } } Ok(()) } .await; // Close the channels so each worker's stream terminates and it returns its index. drop(senders); // Abort and join any decode chunks still in flight, so no decoder outlives a failed init. while let Some((rx, decoder)) = pending.pop_front() { drop(rx); decoder.abort().await; } // Join workers before surfacing any replay failure, so none outlive a failed init. let joined = AbortOnDrop::join_all::>(handles).await; routing_result?; let joined = joined?; // Install each worker's partition range into the snapshot and fold its active-key count in. let mut total_items = 0; for (worker_index, worker_keys) in joined { snapshot.install_range(worker_index); total_items += worker_keys; } // The join reclaimed exclusive ownership of the shared bitmap, so it can be read back. let mut active = Arc::into_inner(active) .expect("workers were joined") .into_bitmap(); // The last operation is the final commit (a log always ends with one), which stays active. // An empty log has none. if let Some(last_commit) = end.checked_sub(1) && last_commit >= floor { active.set(last_commit - floor, true); } Ok((total_items, active)) } /// Configures snapshot rebuilding during QMDB initialization. /// /// This trait is sealed to the index types provided by this crate. #[expect( private_bounds, reason = "the Rebuild supertrait is private so only QMDB can call build_snapshot" )] pub trait SnapshotBuild: Index> + Rebuild + Sized + 'static { } /// Replays the log into an index owned by initialization. Implementations must drop all log /// clones before returning, including on error. pub(super) trait Rebuild: Index> + Sized { /// Replay `log` from `inactivity_floor_loc`, populating `self`. Returns the number of active /// keys and the activity status of every replayed location, in location order: a location's /// bit is set iff it holds the current operation of an active key or is the last commit. /// /// `init_buffer` sizes the replay read buffer (in bytes), and `cache_size` bounds each /// build's `(location -> key)` cache in entries (`None` disables it). fn build_snapshot( &mut self, _context: E, inactivity_floor_loc: Location, log: &Arc, _init_concurrency: NonZeroUsize, init_buffer: NonZeroUsize, cache_size: Option, ) -> impl Future>> + Send where E: Spawner, C: Contiguous> + 'static, { async move { build_snapshot_serial(inactivity_floor_loc, &**log, self, init_buffer, cache_size).await } } /// The plan of a build whose decode tasks also hash the journal's operations. Index types /// that never spawn decode tasks declare [Infallible]. type HashingPlan: Send + 'static; /// The plan of a build at this concurrency and cache size whose decode tasks hash the /// journal's operations as they decode them, or `None` if this index builds without them. fn hashing_plan( &self, _init_concurrency: NonZeroUsize, _cache_size: Option, ) -> Option { None } /// Like [Self::build_snapshot], but follows `plan`, whose decode tasks also hash every chunk /// of `leaves` and send them to it in order. fn build_snapshot_hashing( &mut self, context: E, inactivity_floor_loc: Location, log: &Arc, plan: Self::HashingPlan, init_buffer: NonZeroUsize, leaves: LeafSink, ) -> impl Future>> + Send where E: Spawner, C: Contiguous + Encode> + 'static, H: MerkleHasher + 'static; } impl SnapshotBuild for crate::index::unordered::Index> {} impl SnapshotBuild for crate::index::ordered::Index> {} impl SnapshotBuild for crate::index::partitioned::unordered::Index, P> { } impl SnapshotBuild for crate::index::partitioned::ordered::Index, P> { } impl Rebuild for crate::index::unordered::Index> { type HashingPlan = Infallible; async fn build_snapshot_hashing( &mut self, _context: E, _inactivity_floor_loc: Location, _log: &Arc, plan: Infallible, _init_buffer: NonZeroUsize, _leaves: LeafSink, ) -> Result<(usize, BitMap), Error> where E: Spawner, C: Contiguous + Encode> + 'static, H: MerkleHasher + 'static, { match plan {} } } impl Rebuild for crate::index::ordered::Index> { type HashingPlan = Infallible; async fn build_snapshot_hashing( &mut self, _context: E, _inactivity_floor_loc: Location, _log: &Arc, plan: Infallible, _init_buffer: NonZeroUsize, _leaves: LeafSink, ) -> Result<(usize, BitMap), Error> where E: Spawner, C: Contiguous + Encode> + 'static, H: MerkleHasher + 'static, { match plan {} } } impl>> Rebuild for I { type HashingPlan = ParallelPlan; async fn build_snapshot( &mut self, context: E, inactivity_floor_loc: Location, log: &Arc, init_concurrency: NonZeroUsize, init_buffer: NonZeroUsize, cache_size: Option, ) -> Result<(usize, BitMap), Error> where E: Spawner, C: Contiguous> + 'static, { let Some(plan) = ParallelPlan::new(self.partition_count(), init_concurrency, cache_size) else { return build_snapshot_serial( inactivity_floor_loc, &**log, self, init_buffer, cache_size, ) .await; }; build_snapshot_parallel( self, plan, context, inactivity_floor_loc, log, init_buffer, IndexOnly, ) .await } fn hashing_plan( &self, init_concurrency: NonZeroUsize, cache_size: Option, ) -> Option { ParallelPlan::hashing(self.partition_count(), init_concurrency, cache_size) } async fn build_snapshot_hashing( &mut self, context: E, inactivity_floor_loc: Location, log: &Arc, plan: ParallelPlan, init_buffer: NonZeroUsize, leaves: LeafSink, ) -> Result<(usize, BitMap), Error> where E: Spawner, C: Contiguous + Encode> + 'static, H: MerkleHasher + 'static, { build_snapshot_parallel( self, plan, context, inactivity_floor_loc, log, init_buffer, leaves, ) .await } } #[cfg(test)] mod tests { use super::*; #[test] fn test_parallel_plan_budget_and_ranges() { for partitions in 0..=128 { for budget in 1..=64 { let plan = ParallelPlan::new(partitions, NonZeroUsize::new(budget).unwrap(), None); assert_eq!(plan.is_none(), partitions == 0 || budget == 1); let Some(plan) = plan else { continue; }; assert!((1..=partitions).contains(&plan.workers)); if budget <= 3 { assert_eq!(plan.decoders, 0); assert!(plan.workers < budget); } else { assert!(plan.decoders >= 2); assert!(plan.decoders + plan.workers <= budget); } let ranges = plan.ranges(); assert_eq!(ranges.len(), plan.workers); let mut end = 0; for (worker, (lo, len)) in ranges.enumerate() { assert_eq!(lo, end); assert!((1..=plan.range_size).contains(&len)); end = lo + len; assert!(end <= partitions); for partition in lo..end { assert_eq!(partition / plan.range_size, worker); } } assert_eq!(end, partitions); } } } #[test] fn test_hashing_plan_decodes_on_the_whole_budget() { for partitions in 0..=64 { for budget in 1..=64 { let budget = NonZeroUsize::new(budget).unwrap(); let plan = ParallelPlan::new(partitions, budget, None); let hashing = ParallelPlan::hashing(partitions, budget, None); assert_eq!(hashing.is_none(), plan.is_none()); let (Some(plan), Some(hashing)) = (plan, hashing) else { continue; }; assert_eq!(hashing.decoders, budget.get()); assert_eq!(hashing.workers, plan.workers); assert!(hashing.workers < budget.get()); } } } #[test] fn test_parallel_plan_cache_split() { // Uneven ranges can reduce the worker count, so split the cache among the final workers. for partitions in 1..=64 { for budget in 2..=32 { for cache_size in [0, 1, 3, 8, 64] { let plan = ParallelPlan::new( partitions, NonZeroUsize::new(budget).unwrap(), NonZeroUsize::new(cache_size), ) .unwrap(); let share = plan.per_worker_cache.map_or(0, NonZeroUsize::get); assert_eq!(plan.per_worker_cache.is_none(), cache_size < plan.workers); let allocated = share * plan.workers; assert!(allocated <= cache_size); assert!(cache_size - allocated < plan.workers); } } } } }