Struct BlobTree 

pub struct BlobTree { /* private fields */ }

A key-value-separated log-structured merge tree

This tree is a composite structure, consisting of an index tree (LSM-tree) and a log-structured value log to reduce write amplification.

Closed like a Tree: once the TreeClose of close fires, the tree writes nothing into its directory, its blob folder included.

Implementations

impl BlobTree

pub fn downgrade(&self) -> WeakTree

A handle that does not keep the tree open; see WeakTree.

pub fn close(self) -> TreeClose

Gives up this handle and returns the signal of the tree being closed; see Tree::close. A blob file an iterator or a snapshot still holds keeps the tree open, as a table does.

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

Iterate change events with seqno >= target_seqno, resolving KV-separated values.

Same change-data-capture contract as Tree::scan_since_seqno, but a blob-indirected value is resolved from its blob file into a ScanSinceEvent::Insert carrying the real value, so a downstream consumer can replicate without access to the source’s blob files. Block-skip, seqno ordering, and tombstone handling are identical to the standard-tree path (the same shared aggregation backs both).

Panics

Panics if the internal version-history lock is poisoned.

Errors

Returns Err if reading the index, a data block, or a referenced blob fails.

pub fn start_multi_get<K: Into<UserKey>>( &self, keys: impl IntoIterator<Item = K>, seqno: SeqNo, ) -> Result<Step>

Starts a multi-get of keys at seqno that its caller drives, as Tree::start_multi_get does; a value kept in the value log is read by a job the read hands out.

Errors

Returns crate::Error::SnapshotBelowRetention when seqno is below what the tree retains.

pub fn scan_since_seqno_in_range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, target_seqno: SeqNo, range: R, ) -> Result<impl Iterator<Item = ScanSinceEvent> + use<K, R>>

Range-scoped variant of Self::scan_since_seqno, with the same contract as Tree::scan_since_seqno_in_range: point events only for keys inside range, range deletions when their span overlaps it, and index SSTs outside the bounds skipped unread.

Panics

Panics if the internal version-history lock is poisoned.

Errors

Same as Self::scan_since_seqno.

pub fn insert_cells<K: Into<UserKey>>( &self, key: K, fields: &[Field<'_>], seqno: SeqNo, ) -> Result<(u64, u64)>

Writes key as a row of fields at seqno.

Each Field names its column and physical type, and both are stored with the row, so a stored row always reads with the layout it was written with. A column id is a field id of the columnar format (from FIRST_FIELD_COLUMN up to, not including, RESERVED_COLUMNS), so a columnar table can store the field as that column. The row keeps its fields in ascending column order, whatever order they are given in. Plain reads of the key return the fields in that order, framed as the columnar format frames a row’s value sub-columns (a variable-width field as a little-endian u32 length and its bytes, a fixed-width one as its bytes), with every Cell::Ref replaced by its object. A Cell::Value at or above its column’s threshold (KvSeparationOptions::cell_separation_threshold, else the tree’s separation threshold) is stored in a blob file when the row is flushed.

A Cell::Ref keeps an object the key already holds without rewriting it, which is how a metadata-only update leaves a large field in place. Take the references from the key’s latest version and write this row above it.

Returns the added item’s size and the new memtable size, as AbstractTree::insert does.

Errors

Returns crate::Error::BlobRef if a reference was read from another key or tree, two fields name one object, or a reference is stale (its object was moved or let go of since the read: read the key again); crate::Error::CellRow if a column is not a field id, two fields share a column or a fixed-width field is not its type’s width; and an error if the row has more than u16::MAX fields or a cell exceeds u32::MAX bytes. Nothing is written then.

Examples

let tree = Config::new(folder.path(), SequenceNumberCounter::default(), SequenceNumberCounter::default())
    .with_kv_separation(Some(KvSeparationOptions::default()))
    .open()?;
// Given out of order, stored and read in column order.
tree.insert_cells("doc", &[Field::bytes(4, b"body"), Field::bytes(3, b"draft")], 0)?;
let value = tree.get("doc", 1)?.expect("written");
assert_eq!(&*value, b"\x05\0\0\0draft\x04\0\0\0body");

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

The fields of key as of seqno, references included as references: the read a metadata-only update starts from. No blob object is read.

Returns None when the key is absent at seqno. References to write back must come from the key’s latest version; a reference read at an older seqno may name an object a newer version already let go of.

Errors

Returns crate::Error::SnapshotBelowRetention when seqno is below what the tree retains, and crate::Error::BlobRef when the key’s version at seqno was not written as cells.

Examples

let body = vec![b'x'; 1_000];
tree.insert_cells("doc", &[Field::bytes(3, b"draft"), Field::bytes(4, &body)], 0)?;
tree.flush_active_memtable(0)?;

// Change the status, keep the body where it is.
let row = tree.get_cells("doc", 1)?.expect("written");
let mut fields = row.fields()?;
assert!(matches!(fields[1].cell, Cell::Ref(_)));
fields[0].cell = Cell::Value(b"final");
tree.insert_cells("doc", &fields, 1)?;

pub fn range_cells<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: SeqNo, ) -> Result<Box<dyn DoubleEndedIterator<Item = Result<RowCells>> + Send + 'static>>

The rows written as cells in range as of seqno, in key order, each with its references as references, as Self::get_cells reads one.

A key whose version at seqno is stored whole rather than as cells is passed over: read it with a plain range read. Every row comes from one read, which keeps its objects readable and its references writable as RowCells describes, for as long as any of its rows is held.

Errors

Returns crate::Error::SnapshotBelowRetention when seqno is below what the tree retains; the iterator yields an error for a row it cannot read.

Examples

let body = vec![b'x'; 1_000];
for key in ["a", "b"] {
    tree.insert_cells(key, &[Field::bytes(3, b"draft"), Field::bytes(4, &body)], 0)?;
}
tree.insert("plain", "value", 0);
tree.flush_active_memtable(0)?;

// Publish every draft, keeping each body where it is.
let rows: Vec<_> = tree.range_cells::<&str, _>(.., 1)?.collect::<lsm_tree::Result<_>>()?;
assert_eq!(rows.len(), 2);
for row in &rows {
    let mut fields = row.fields()?;
    fields[0].cell = Cell::Value(b"final");
    tree.insert_cells(row.key().clone(), &fields, 1)?;
}

pub fn columnar_scan<R: RangeBounds<UserKey>>( &self, projection: impl Into<Projection>, predicate: Option<&ColumnRangePredicate>, seqno: SeqNo, range: R, ) -> Result<ColumnarScan>

Runs a projected columnar scan across the tree, as Tree::columnar_scan does, reading each row’s declared fields as late as it can.

The rows are decided first on their keys, seqnos and value types; only the rows the scan returns have their fields read. A field of a row written as cells is read out of the row (or, in a columnar table, out of the field’s own column), and its object is read from its blob file only when the field is projected: a projection of compact fields reads no blob at all. A row stored whole has its fields read through the projection’s ValueProjector, its value read from the value log first when it is kept there. When the predicate runs on a projected field, that field is read first and the objects of the other fields are read only for the rows it keeps.

A field is projected as a declared field, with its type and what its absence means; the intrinsic key, seqno and value-type columns may be projected by id. A field holds its value, not how the tree stores it, so a row’s value type reads as a value.

Errors

Returns crate::Error::Projection when a value column is projected by id alone or the predicate runs on one no field declares, and otherwise as Tree::columnar_scan, and, lazily, when a field is stored under another type than declared or an object cannot be read.

Examples

use lsm_tree::blob_tree::field_row::{Field, TypeTag};
use lsm_tree::{Absent, ProjectedField, Projection};
let body = vec![b'x'; 1_000];
tree.insert_cells("doc", &[Field::bytes(3, b"draft"), Field::bytes(4, &body)], 0)?;
tree.flush_active_memtable(0)?;

// The status alone: the body stays in its blob file, unread.
let status = Projection::new().field(ProjectedField::new(3, TypeTag::Bytes, Absent::Null)?);
let mut batches = tree.columnar_scan(status, None, SeqNo::MAX, ..)?;
let batch = batches.next().expect("one batch")?;
assert_eq!(batch.row_count, 1);

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

where F: FnOnce(&mut RuntimeConfig),

Updates the live RuntimeConfig, as Tree::update_runtime_config does for the index tree.

The blob files share the snapshot: a change of blob_compression applies to the next blob file written, and every earlier one keeps the codec it recorded.

Errors

Same as Tree::update_runtime_config, including a blob compression that names a dictionary the tree does not hold.

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

Snapshot of the current runtime config, shared by the index and the blob files.

pub fn register_zstd_dictionary(&self, dict: Arc<ZstdDictionary>) -> Result<()>

Stores dict in the tree, as Tree::register_zstd_dictionary does. The step before a blob compression that names it: an update naming a dictionary the tree does not hold is refused.

Errors

Same as Tree::register_zstd_dictionary.

Trait Implementations

impl AbstractTree for BlobTree

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 pin(&self) -> PinnedVersion

Pins the tree’s current state for a point-in-time copy that costs no file I/O: seals the active memtable and returns a PinnedVersion holding the sealed memtables, tables, blob files and dictionaries as they are now.

fn acknowledge_repair_report(&self, id: u128) -> Result<bool>

Stops the tree owing the repair report with this RepairReport::id, installing a version that no longer carries it: no later Config::open_or_repair hands it out.

fn table_file_cache_size(&self) -> usize

Returns the number of cached table file descriptors.

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

Makes every flush installed before this call durable, under FlushDurability::Deferred: the tables and blob files those flushes wrote are synced, then their folders, then the manifest is written. Once it returns Ok a caller may drop its own log up to the writes those flushes held; under SyncMode::Barrier after sync_devices as well. A no-op when nothing is pending, and under FlushDurability::Synced every flush is durable when it returns.

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 run count, the strategy’s pending-compaction bytes and the unflushed memtable bytes, against the configured RuntimeConfig::backpressure thresholds.

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 metrics(&self) -> &Arc<Metrics>

Returns the metrics structure.

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 tombstone_count(&self) -> u64

Returns the approximate number of tombstones in the tree.

fn weak_tombstone_count(&self) -> u64

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

fn weak_tombstone_reclaimable_count(&self) -> u64

Returns the approximate number of values reclaimable once weak tombstones can be GC’d.

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

Drops all tables and clears all memtables atomically.

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

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

fn clear_active_memtable(&self)

Clears the active memtable atomically.

fn l0_run_count(&self) -> usize

Returns the number of disjoint runs in L0.

fn blob_file_count(&self) -> usize

Returns the number of blob files currently in the tree.

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

Returns the size of a value if it exists.

fn stale_blob_bytes(&self) -> u64

Returns the disk space used by stale blobs.

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 filter_memory(&self) -> FilterMemory

The serialised and the resident bytes of the tree’s filters, and how they stand against a FilterAdvisor budget.

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 get_flush_lock(&self) -> MutexGuard<'_, ()>

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

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

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

fn compact( &self, strategy: Arc<dyn CompactionStrategy>, gc_watermark: 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 get_highest_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number.

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 is_empty( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<bool>

Returns true if the tree is empty.

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 len( &self, seqno: SeqNo, index: Option<(Arc<Memtable>, SeqNo)>, ) -> Result<usize>

Scans the entire tree, returning the number of items.

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 oldest_retained_seqno(&self) -> SeqNo

Returns the retention floor: the lower bound of the readable snapshot window.

fn retention_floor(&self) -> SeqNo

Returns the persisted retention floor: the highest snapshot seqno the tree refuses, now and after a reopen. It always equals oldest_retained_seqno.

fn lower_retention_floor(&self, floor: SeqNo) -> Result<()>

Lowers the persisted retention floor to floor, so snapshots above it are served again, now and after a reopen.

fn compaction_rate_limiter(&self) -> Arc<RateLimiter>

Returns the limiter that throttles this tree’s compactions: the one supplied through Config::compaction_rate_limiter, which other trees may share, or the tree’s own built from Config::compaction_rate_limit.

fn write_rate_limiter(&self) -> Arc<RateLimiter>

The limiter writes are paced with under backpressure slowdown: shared with other trees if one was supplied through Config::write_rate_limiter, else the tree’s own. Retune it live with RateLimiter::set_rate; 0 turns byte pacing off.

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 get<K: AsRef<[u8]>>(&self, key: K, seqno: SeqNo) -> Result<Option<UserValue>>

Retrieves an item from the tree.

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 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 write_backpressure_for( &self, strategy: &dyn CompactionStrategy, bytes: u64, ) -> Backpressure

The verdict for one write of bytes: write_backpressure, except that a slowdown on a tree with a write rate limit (see Config::write_rate_limit) debits bytes from the tree’s write limiter and suggests waiting until they, and every byte debited before them, are paid off at its rate. Writes honouring it are then bounded by the rate in bytes per second, large and small alike, however many writers share the limiter. Outside the slowdown tier nothing is debited.

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_active_memtable(&self, gc_watermark: SeqNo) -> Result<()>

Seals the active memtable and flushes it, with every memtable sealed before it, to tables: the durability barrier for a caller that keeps its own journal of the writes.

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

Makes durable everything this tree synced on each device it lies on: the tree folder’s, that of every level’s tables, that of the dictionaries folder and, with KV separation, that of the blobs folder.

fn flush( &self, _lock: &MutexGuard<'_, ()>, gc_watermark: 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 flush_to_tables( &self, stream: impl Iterator<Item = Result<InternalValue>>, ) -> Result<Option<(Vec<Table>, Option<Vec<BlobFile>>, WritePin)>>

Synchronously flushes a memtable to a table.

fn tree_type(&self) -> TreeType

Returns the tree type.

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 get_pinned<K: AsRef<[u8]>>( &self, key: K, seqno: SeqNo, ) -> Result<Option<PinnableSlice>>

Retrieves an item from the tree as a PinnableSlice.

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 BlobTree

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl From<BlobTree> for AnyTree

fn from(tree: BlobTree) -> Self

Converts to this type from the input type.

impl TryInto<BlobTree> for AnyTree

type Error = &'static str

The type returned in the event of a conversion error.

fn try_into(self) -> Result<BlobTree, Self::Error>

Performs the conversion.