Crate lsm_tree 

Embedded LSM-tree storage engine.

Provides keyed point reads, prefix and range scans, MVCC snapshots, block and file-descriptor caching, and a configurable compaction subsystem. No write-ahead log — durability is the caller’s responsibility (flush_active_memtable forces persistence when needed).

Highlights

• AMQ filter: BuRR (Bumped Ribbon Retrieval, Walzer & Dillinger 2022) for per-key and per-prefix membership checks. ~30% smaller filter blocks than a same-FPR Bloom filter, or ~10× tighter FPR at the same memory budget.
• Compression: pure-Rust zstd (incl. dictionary mode), LZ4, or none — per-table and per-level policy.
• Encryption at rest: AES-256-GCM block encryption with a caller-supplied key.
• Range tombstones: delete_range / delete_prefix (SST-encoded; the feature was added in disk format V4 and remains supported in the current V5 format — the V5 break extends the block header for per-block Reed- Solomon Page ECC, not the tombstone encoding).
• Merge operators: commutative-merge LSM operations with lazy resolution.
• K/V separation (BlobTree): large-value workloads with automatic GC.
• Pluggable Fs: standard, in-memory, io_uring, or custom backends.
• MVCC: snapshot reads at a chosen SeqNo, custom UserComparator.
• Concurrency: thread-safe BTreeMap-like API.

Keys: up to 65,535 bytes (u16 length field). Values: up to 4,294,967,295 bytes (u32 length field, 2³² − 1). Larger keys and values carry a proportional performance cost.

Quick start

use lsm_tree::{AbstractTree, Config, SequenceNumberCounter};

let folder = tempfile::tempdir().unwrap();
let seqno = SequenceNumberCounter::default();
let tree = Config::new(&folder, seqno.clone(), SequenceNumberCounter::default())
    .open()
    .unwrap();

tree.insert("key", "value", seqno.next());
let value = tree.get("key", lsm_tree::SeqNo::MAX).unwrap();
assert_eq!(value.map(|v| v.to_vec()), Some(b"value".to_vec()));

On-disk format

Current version: V6, the only one this engine reads or writes. Relative to V5, which the 5.x releases write, the version snapshot names each table’s level and run in its own record, and the BuRR filter and retrieval-locator sections use the packed solution layout; see FormatVersion for the full list.

The self-describing block types (Meta / Manifest / ManifestFooter) carry a block_flags byte whose ECC_PARITY bit marks a per-block Reed-Solomon parity trailer and whose KV_CHECKSUM_FOOTER bit marks a per-entry checksum footer. SST block types (Data / Index / Filter / RangeTombstone) keep the compact header WITHOUT that byte and derive parity / footer presence from the per-SST meta descriptors (descriptor#page_ecc, descriptor#kv_checksum). Any “byte-identical when off” guarantee in the feature docs is within the current format and payload-level (e.g. index entries when seqno_in_index = false), not a cross-version equivalence.

Earlier formats, V5 included, are not readable by this version and vice versa. A V5 manifest is refused by the manifest version gate with Error::InvalidVersion at Tree::open and at Config::repair, before any section is parsed. Older manifests usually fail earlier, at the manifest footer (see FormatVersion); the engine knows no earlier layout, so it cannot tell such a manifest from a damaged one, and Config::repair treats it as unreadable. A V5 store is converted by the separate offline converter; the engine carries no V5 decoder.

Re-exports

pub use storage_stats::ApproximateRangeStats;

pub use storage_stats::BlobReferenceStats;

pub use storage_stats::FilterMemory;

pub use storage_stats::LevelStats;

pub use storage_stats::RangeCardinality;

pub use storage_stats::SegmentStats;

pub use storage_stats::StorageStatistics;

pub use storage_stats::StorageStats;

pub use storage_stats::StorageStatus;

pub use encryption::EncryptionProvider;

pub use encryption::Aes256GcmProvider;

pub use recovery_progress::RecoveryPhase;

pub use recovery_progress::RecoveryProgress;

pub use recovery_progress::RecoveryProgressSnapshot;

pub use repair::RepairPolicy;

pub use repair::RepairReport;

pub use repair::WalReplayScope;

pub use cache::Cache;

pub use comparator::DefaultUserComparator;

pub use comparator::SharedComparator;

pub use comparator::UserComparator;

pub use compression::CompressionType;

pub use config::BlobLocalityRelocation;

pub use config::Config;

pub use config::KvSeparationOptions;

pub use config::TreeType;

pub use error::Error;

pub use error::FormatPart;

pub use error::Result;

pub use format_version::FormatVersion;

pub use iter_guard::IterGuard as Guard;

pub use key_domain::KeyDomains;

pub use memtable::Memtable;

pub use memtable::MemtableId;

pub use merge_operator::MergeOperator;

pub use prefix::PrefixExtractor;

pub use seqno::MAX_SEQNO;

pub use seqno::SequenceNumberCounter;

pub use seqno::SequenceNumberGenerator;

pub use seqno::SharedSequenceNumberGenerator;

pub use slice::Slice;

pub use value::SeqNo;

pub use value_type::ValueType;

pub use backpressure::WriteBufferBudget;

pub use backpressure::Backpressure;

pub use backpressure::BackpressureSignals;

pub use backpressure::BackpressureThresholds;

Modules

backpressure

Computed write-backpressure verdict (caller-honoured, see backpressure). Computed write-backpressure verdict.

compaction

Contains compaction strategies

config

Configuration

ecc

Shard-based Page ECC (XOR single-parity and Reed-Solomon).

encryption

Block-level encryption at rest. Block-level encryption at rest.

fs

Pluggable filesystem abstraction for I/O backends. Pluggable filesystem abstraction for I/O backends.

hash

Stable hash functions used across the filter and table subsystems.

heal_hints

Tree-wide queue of SSTs whose blocks were ECC-corrected on a read that was confirmed persistent (the on-disk bytes are still faulty after a cache-bypassing re-read).

inspect

Out-of-band inspection of a single SST file.

io

Local I/O trait surface mirroring std::io::{Read, Write, Seek}.

rate_limiter

Compaction I/O rate limiter.

recovery_progress

Live progress counters for long-running recovery (repair / salvage). Live progress counters for long-running recovery work.

repair

Disaster-recovery: rebuild a missing/corrupt manifest from on-disk SSTs. Last-resort MANIFEST reconstruction from the SST files on disk.

restrict_bound

Sidecar recording a tight-space-punched SST’s restriction lower bound.

resumable

A multi-get its caller drives, which never blocks, sleeps or waits.

runtime_config

Runtime-toggleable configuration (RuntimeConfig + atomic-swap handle). Runtime-toggleable configuration.

salvage

Block-granular SST salvage: recover the readable blocks of an SST whose whole-file verification fails, dropping the corrupted ones.

scrub

ECC patrol scrub: a proactive sweep over Page-ECC-protected SST blocks.

storage_stats

Read-only storage introspection: how much is stored, the average shape of a stored entry, and an estimate of how many more entries fit in a byte budget.

util

Utility functions

verify

Integrity verification for SST and blob files.

write_budget

A cumulative host-write budget for one physical medium.

Structs

AcceptedWrites

What a tree took in from its caller, before any encoding: the payload the bytes it writes are measured against.

BlobFile

A blob file stores large values and is part of the value log

BlobTree

A key-value-separated log-structured merge tree

Cache

Cache, in which blocks or blobs are cached in-memory after being retrieved from disk

CacheStats

A point-in-time snapshot of block-cache effectiveness and occupancy.

CapacityPool

The room compactions in progress hold on the volumes they write to, shared by every tree given the same pool.

CheckpointInfo

Summary of a checkpoint produced by AbstractTree::create_checkpoint.

ColumnarScan

Iterator over a tree-level projected columnar scan.

DefaultUserComparator

Default comparator using lexicographic byte ordering.

DescriptorTable

Caches file descriptors to tables and blob files

Memtable

The memtable serves as an intermediary, ephemeral, sorted storage for new items

Metrics

Runtime metrics

PinnedEntry

One entry of a pinned memtable, as a flush would write it.

PinnedFile

A file a PinnedVersion holds in place: a table, a blob file or a compression dictionary.

PinnedRangeTombstone

A range tombstone of a pinned memtable, deleting [start, end) below seqno.

PinnedVersion

A point-in-time view of a tree that keeps its files in place.

ProjectedField

One field of a Projection: its column id, its physical type and what its absence means.

ProjectedRow

The cells a ValueProjector writes for one row.

Projection

The columns a projected scan returns: intrinsic columns and value fields, in the order the scan yields them, and the projector that reads the fields out of row values.

SequenceNumberCounter

Thread-safe sequence number generator

Slice

An immutable byte slice that can be cloned without additional heap allocation

SystemClock

The system wall-clock, backed by std::time::SystemTime.

Tree

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

TreeClose

The signal of a tree being closed, returned by Tree::close and its counterparts.

WeakTree

A handle on a tree that does not keep it open, made by Tree::downgrade and its counterparts.

WriteBatch

Batch of write operations applied with a shared seqno.

ZstdDictionaries

Every dictionary a tree can decompress against, keyed by the id its tables already record.

ZstdDictionary

A zstd dictionary to compress small blocks against.

Enums

Absent

What a projected field reads as in a row that does not have it: a segment written without the column, a null cell, or a row value the ValueProjector finds no such field in.

AnyIngestion

Unified ingestion builder over AnyTree

AnyTree

May be a standard Tree or a BlobTree

CompressionType

Compression algorithm to use

Error

Represents errors that can occur in the LSM-tree

FormatPart

The part of a table whose on-disk format Error::UnsupportedFormat refers to.

FormatVersion

Block / SST disk format version.

PinnableSlice

A value reference that may share the decompressed block buffer.

ScanSinceEvent

A single change event emitted by Tree::scan_since_seqno.

ValueType

Value type (regular value or tombstone)

Constants

MAX_SEQNO

The maximum allowed sequence number value.

Traits

AbstractTree

Generic Tree API

Clock

A source of wall-clock time.

Guard

Guard to access key-value pairs

KeyDomains

Splits the key space into domains that no new table spans.

MergeOperator

A user-defined merge operator for commutative LSM operations.

PrefixExtractor

Extracts prefixes from keys for prefix bloom filter indexing.

SequenceNumberGenerator

Trait for custom sequence number generation.

UserComparator

Trait for custom user key comparison.

ValueProjector

Reads the projected fields out of a row value the engine cannot interpret: a value in a memtable or a row-oriented table, or the result of a merge.

Type Aliases

KvPair

KV-tuple (key + value)

MemtableId

Unique memtable ID

Result

Tree result

SeqNo

Sequence number - a monotonically increasing counter

SharedComparator

Shared reference to a UserComparator.

SharedSequenceNumberGenerator

A shared, cloneable sequence number generator.

UserKey

User defined key (byte array)

UserValue

User defined data (byte array)