Struct Tree 

pub struct Tree(/* private fields */);

A log-structured merge tree (LSM-tree/LSMT)

Implementations

impl Tree

pub fn scan_since_seqno( &self, target_seqno: SeqNo, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<>>

Iterate change events with seqno >= target_seqno.

Returns every change committed at or after target_seqno as a stream of ScanSinceEvents in increasing seqno order. This is the canonical change-data-capture primitive: a downstream consumer (replica, Kafka connector, Debezium-style pipeline) replays the events in order to reconstruct the source’s history. Superseded versions are not collapsed (a key written three times after the target yields three events).

Block-skip

On SSTs written with the seqno_bounds section (seqno_in_index), data blocks whose bounds cannot overlap the target window are skipped without being read; SSTs without the section are read and filtered per entry, so mixed trees are handled transparently.

KV-separation

Standard trees never store blob-indirected values. On the inner tree of a KV-separated (blob) tree this returns an Err for indirected entries: blob resolution into ScanSinceEvent::Insert is provided by the blob-tree scan path, which owns the blob files.

Corruption resilience

The per-block seqno-bounds used for skipping live in the optional seqno_bounds SST section, a Block covered by XXH3-128 (+ optional Page ECC) and verified when it is loaded at open, plus a decode that rejects non-ascending offsets and inverted bounds, so a corrupted bound is caught rather than trusted. Even in the impossible case of a fault bypassing those checks, a bad bound can only cause a missed record, never a wrong one. Callers who want defense against that hypothetical can use Self::scan_since_seqno_full_scan, which reads every block (slower, no skip).

Panics

Panics if the internal version-history lock is poisoned.

Errors

Returns Err if reading the index or a data block fails, or if an entry is a KV-separated value (see above).

pub fn scan_since_seqno_full_scan( &self, target_seqno: SeqNo, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<>>

Paranoid variant of Self::scan_since_seqno that disables the per-block seqno-bounds skip: every data block is read and filtered per entry, even on seqno-indexed SSTs.

When to use

The fast Self::scan_since_seqno trusts each block’s recorded [seqno_min, seqno_max] to skip blocks that cannot hold a qualifying record. Those bounds live in the seqno_bounds SST section, a Block covered by XXH3-128 (and optional Page ECC) and verified at open, so on-disk corruption is caught, not silently trusted. This method exists for callers who want defense even against a fault that somehow bypassed those checks: a corrupted seqno_max can only ever cause a missed record (never a wrong one), and a full scan cannot miss. It is slower (no skip), so prefer Self::scan_since_seqno unless you specifically need this guarantee.

Panics

Panics if the internal version-history lock is poisoned.

Errors

Same as Self::scan_since_seqno.

pub fn update_runtime_config<F>(&self, mutator: F) -> Result<()>

where F: FnOnce(&mut RuntimeConfig),

Update the live crate::runtime_config::RuntimeConfig.

Mutator runs on a clone of the current snapshot; the new snapshot is then atomically swapped in. Subsequent calls to Self::runtime_config observe the new snapshot.

Current scope

This API ships the snapshot + atomic-swap mechanism. No write path in the current tree consults runtime_config yet — that wiring lands with the V5-batch format features (manifest hardening, per-KV protection, scan-since-seqno) which extend RuntimeConfig with their own fields and read it at block write / manifest commit / compaction boundaries.

Designed semantics (effective once wired by V5 features)

• Subsequent write paths load the new snapshot lockless on their next operation.
• Existing on-disk data remains in its original format and reads transparently — every block / manifest is self-describing via its own header.
• Compaction acts as the live-migration mechanism: source blocks are rewritten per the current snapshot over subsequent cycles, so all data converges to the current settings without stop-the-world coordination.

Concurrency

Reader atomicity: concurrent readers observe either the old or the new snapshot, never a torn intermediate state.

Writer semantics: last-writer-wins. Two update calls racing from the same starting snapshot will have the second store overwrite the first — the first writer’s mutation is lost. There is no CAS / RCU merge. Callers that need lost-update avoidance (e.g. two threads concurrently toggling different fields) MUST serialize their update_runtime_config calls, typically via a Mutex around the call site.

Errors

Returns crate::Error::PageEccUnsupported when the mutator leaves page_ecc = true on a binary built without the page_ecc cargo feature. The live snapshot stays at its pre-mutation value on error.

pub fn runtime_config(&self) -> Arc<RuntimeConfig>

Snapshot of the current runtime config. Cheap atomic load — safe to call on hot paths.

pub fn heal_hints(&self) -> Arc<HealHints>

Shared handle to this tree’s ECC heal-hint queue.

A read that recovers a block from Page-ECC parity records the owning SST here (when the on-disk fault is confirmed persistent). Pass the handle to compaction::EccHeal and run that strategy via Tree::compact — leader-only in a clustered deployment — to rewrite the flagged SSTs clean. Check HealHints::is_empty to skip the pass when nothing is queued.

Examples

use lsm_tree::{AbstractTree, AnyTree, Config, SequenceNumberCounter, compaction::EccHeal};
use std::sync::Arc;
let AnyTree::Standard(tree) = Config::new(
    "/tmp/db",
    SequenceNumberCounter::default(),
    SequenceNumberCounter::default(),
)
.open()?
else {
    return Ok(());
};

// Opt into rewrite scheduling; reads that recover a block from parity now
// flag its SST for healing.
tree.update_runtime_config(|c| c.auto_heal = true)?;

// Drain the queue, rewriting each flagged SST clean (leader-only in a
// clustered deployment).
let hints = tree.heal_hints();
while !hints.is_empty() {
    tree.compact(Arc::new(EccHeal::new(tree.heal_hints(), u64::MAX)), 0)?;
}

Trait Implementations

impl AbstractTree for Tree

fn tombstone_count(&self) -> u64

Returns the number of tombstones in the tree.

fn weak_tombstone_count(&self) -> u64

Returns the number of weak tombstones (single deletes) in the tree.

fn weak_tombstone_reclaimable_count(&self) -> u64

Returns the number of value entries that become reclaimable once weak tombstones can be GC’d.

fn table_file_cache_size(&self) -> usize

Returns the number of cached table file descriptors.

fn blob_file_count(&self) -> usize

Returns the number of blob files currently in the tree.

fn create_checkpoint(&self, target_path: &Path) -> Result<CheckpointInfo>

Creates a hard-linked checkpoint of the tree’s on-disk state in target_path for point-in-time recovery (PITR) backup.

fn storage_stats(&self) -> Result<StorageStats>

Returns a read-only snapshot of the tree’s on-disk storage footprint: total used bytes, entry count, the average shape of a stored entry (average key / value bytes), and an estimate of how many more average-shaped entries fit in a byte budget (see StorageStats::estimated_remaining_entries).

fn write_admission(&self) -> Result<()>

Storage admission gate: Ok(()) if a write may proceed, or Error::StorageFull if the tree is over budget and should be treated as read-only.

fn write_backpressure(&self, strategy: &dyn CompactionStrategy) -> Backpressure

Computed write-backpressure verdict from the live L0 table count and the strategy’s pending-compaction bytes, against the configured RuntimeConfig::backpressure thresholds.

fn get_flush_lock(&self) -> MutexGuard<'_, ()>

Acquires the flush lock which is required to call Tree::flush.

fn metrics(&self) -> &Arc<Metrics>

Returns the metrics structure.

fn cache_stats(&self) -> CacheStats

A point-in-time CacheStats snapshot of block-cache effectiveness (cumulative hit / miss counts and rate) and occupancy (current size against capacity).

fn version_free_list_len(&self) -> usize

Gets the length of the version free list.

fn prefix<K: AsRef<[u8]>>( &self, prefix: K, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator over a prefixed set of items.

fn range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator over a range of items.

fn range_seekable<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn SeekableGuardIter + 'static>

Returns a range iterator that can reposition (seek) in place without reopening its per-SST readers.

fn batch_range_scan<K: AsRef<[u8]>, R: RangeBounds<K> + 'static, I: IntoIterator<Item = R>>( &self, intervals: I, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn Iterator<Item = IterGuardImpl> + Send + 'static>

where I::IntoIter: Send + 'static,

Scans a sequence of disjoint, ascending key sub-intervals, reusing one set of per-SST readers across all of them.

fn drop_range<K: AsRef<[u8]>, R: RangeBounds<K>>(&self, range: R) -> Result<()>

Drops tables that are fully contained in a given range.

fn clear(&self) -> Result<()>

Drops all tables and clears all memtables atomically.

fn l0_run_count(&self) -> usize

Returns the number of disjoint runs in L0.

fn size_of<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<Option<u32>>

Returns the size of a value if it exists.

fn filter_size(&self) -> u64

Gets the space usage of all filters in the tree.

fn pinned_filter_size(&self) -> usize

Gets the memory usage of all pinned filters in the tree.

fn pinned_block_index_size(&self) -> usize

Gets the memory usage of all pinned index blocks in the tree.

fn sealed_memtable_count(&self) -> usize

Returns the number of sealed memtables.

fn register_tables( &self, tables: &[Table], blob_files: Option<&[BlobFile]>, frag_map: Option<FragmentationMap>, sealed_memtables_to_delete: &[MemtableId], gc_watermark: SeqNo, ) -> Result<()>

Atomically registers flushed tables into the tree, removing their associated sealed memtables.

fn clear_active_memtable(&self)

Clears the active memtable atomically.

fn compact( &self, strategy: Arc<dyn CompactionStrategy>, seqno_threshold: SeqNo, ) -> Result<CompactionResult>

Performs compaction on the tree’s levels, blocking the caller until it’s done.

fn get_next_table_id(&self) -> TableId

Returns the next table’s ID.

fn tree_config(&self) -> &Config

Returns the tree config.

fn active_memtable(&self) -> Arc<Memtable>

Returns the active memtable.

fn rotate_memtable(&self) -> Option<Arc<Memtable>>

Seals the active memtable.

fn table_count(&self) -> usize

Returns the number of tables currently in the tree.

fn level_table_count(&self, idx: usize) -> Option<usize>

Returns the number of tables in levels[idx].

fn approximate_len(&self) -> usize

Approximates the number of items in the tree.

fn disk_space(&self) -> u64

Returns the disk space usage.

fn approximate_range_stats<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, ) -> Result<ApproximateRangeStats>

Estimates the on-disk bytes and entry count contained in range at seqno, WITHOUT reading any data block.

fn approximate_range_cardinality<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, ) -> Result<RangeCardinality>

Estimates the row cardinality and selectivity of range at seqno, WITHOUT reading any data block.

fn get_highest_memtable_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number of the active memtable.

fn get_highest_persisted_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number that is flushed to disk.

fn get<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<Option<UserValue>>

Retrieves an item from the tree.

fn get_pinned<K: AsRef<[u8]>>( &self, key: K, seqno: SeqNo, ) -> Result<Option<PinnableSlice>>

Retrieves an item from the tree as a PinnableSlice.

fn multi_get<K: AsRef<[u8]>>( &self, keys: impl IntoIterator<Item = K>, seqno: SeqNo, ) -> Result<Vec<Option<UserValue>>>

Reads multiple keys from the tree.

fn apply_batch(&self, batch: WriteBatch, seqno: SeqNo) -> Result<(u64, u64)>

Applies a WriteBatch with the given sequence number.

fn insert<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, value: V, seqno: SeqNo, ) -> (u64, u64)

Inserts a key-value pair into the tree.

fn merge<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, operand: V, seqno: SeqNo, ) -> (u64, u64)

Writes a merge operand for a key.

fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u64, u64)

Removes an item from the tree.

fn remove_range<K: Into<UserKey>>(&self, start: K, end: K, seqno: SeqNo) -> u64

Deletes all keys in the range [start, end) by inserting a range tombstone.

fn level_segment_stats(&self) -> Result<Vec<LevelStats>>

Per-LSM-level and per-segment size + entry-count stats, for tiering and erasure-coding placement decisions (which level / segment is large enough to demote, EC-encode, or migrate).

fn compaction_debt(&self, strategy: &dyn CompactionStrategy) -> u64

Estimated bytes pending compaction under strategy: on-disk data above its level’s target that must eventually be rewritten downward (a RocksDB estimate-pending-compaction-bytes analog), a compaction-debt signal for a scheduler / tiering consumer.

fn is_read_only(&self) -> bool

true when the admission gate is currently closed (see write_admission). Convenience for callers that want a boolean rather than a Result. Always false unless admission control is enabled and the tree is over budget.

fn verify_checksum(&self) -> BlockVerifyReport

where Self: Sized,

Proactively verifies every block’s XXH3 checksum across every SST in the tree’s current version — a scrubber for catching bit rot before it surfaces as a user-visible read failure (cron / scrub jobs).

fn verify_checksum_with(&self, options: &VerifyOptions) -> BlockVerifyReport

where Self: Sized,

Like Self::verify_checksum but with configurable parallelism and I/O throttle (see VerifyOptions).

fn flush( &self, _lock: &MutexGuard<'_, ()>, seqno_threshold: SeqNo, ) -> Result<Option<u64>>

Synchronously flushes pending sealed memtables to tables.

fn iter( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Box<dyn DoubleEndedIterator<Item = IterGuardImpl> + Send + 'static>

Returns an iterator that scans through the entire tree.

fn major_compact( &self, target_size: u64, seqno_threshold: SeqNo, ) -> Result<CompactionResult>

Performs major compaction, blocking the caller until it’s done.

fn stale_blob_bytes(&self) -> u64

Returns the disk space used by stale blobs.

fn flush_to_tables( &self, stream: impl Iterator<Item = Result<InternalValue>>, ) -> Result<Option<(Vec<Table>, Option<Vec<BlobFile>>)>>

Synchronously flushes a memtable to a table.

fn get_highest_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number.

fn tree_type(&self) -> TreeType

Returns the tree type.

fn len( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<usize>

Scans the entire tree, returning the number of items.

fn is_empty( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<bool>

Returns true if the tree is empty.

fn first_key_value( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Option<IterGuardImpl>

Returns the first key-value pair in the tree. The key in this pair is the minimum key in the tree.

fn last_key_value( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Option<IterGuardImpl>

Returns the last key-value pair in the tree. The key in this pair is the maximum key in the tree.

fn contains_key<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<bool>

Returns true if the tree contains the specified key.

fn contains_prefix<K: AsRef<[u8]>>( &self, prefix: K, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<bool>

Returns true if the tree contains any key with the given prefix.

fn try_insert<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, value: V, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated insert: consults write_admission first and declines with Error::StorageFull when the tree is over budget, otherwise inserts and returns the same (added_bytes, memtable_size) tuple. This is the write entry a space-aware caller uses so over-budget writes are refused up front rather than failing a flush later; bare insert stays infallible for callers that do not opt into admission control.

fn try_merge<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, operand: V, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated merge. See try_insert.

fn try_remove<K: Into<UserKey>>( &self, key: K, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated remove. See try_insert.

fn try_remove_weak<K: Into<UserKey>>( &self, key: K, seqno: SeqNo, ) -> Result<(u64, u64)>

Admission-gated remove_weak. See try_insert.

fn try_remove_range<K: Into<UserKey>>( &self, start: K, end: K, seqno: SeqNo, ) -> Result<u64>

Admission-gated remove_range. See try_insert.

fn remove_prefix<K: AsRef<[u8]>>(&self, prefix: K, seqno: SeqNo) -> u64

Deletes all keys with the given prefix by inserting a range tombstone.

impl Clone for Tree

fn clone(&self) -> Tree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Deref for Tree

type Target = TreeInner

The resulting type after dereferencing.

fn deref(&self) -> &Self::Target

Dereferences the value.

impl From<Tree> for AnyTree

fn from(v: Tree) -> AnyTree

Converts to this type from the input type.

impl TryInto<Tree> for AnyTree

type Error = &'static str

The type returned in the event of a conversion error.

fn try_into(self) -> Result<Tree, <Self as TryInto<Tree>>::Error>

Performs the conversion.