Expand description
Log-structured merge tree with background flush.
use subms_lsm_tree::LsmTree;
let dir = std::env::temp_dir().join("subms-lsm-doctest");
let mut lsm = LsmTree::open(&dir, 16_000)?;
lsm.put("AAPL", b"150.10")?;
assert_eq!(lsm.get("AAPL")?.as_deref(), Some(&b"150.10"[..])); // stored key: a hit
assert_eq!(lsm.get("ZZZZ")?, None); // absent: bloom-accelerated missWrites land in an in-memory active memtable. When it exceeds
flush_threshold_bytes the tree rotates: the full memtable is frozen and
a fresh one is installed so the triggering write returns immediately. By
default (FlushMode::Background) a background thread turns each frozen
memtable into an SSTable (with a bloom-filter trailer) off the write path,
so put never pays the O(memtable) flush cost - only the swap. Reads check
active, then the frozen memtables still awaiting flush (newest first),
then SSTables newest-to-oldest; with BloomMode::On each SSTable consults
its bloom filter before scanning, so misses short-circuit in a few hash
probes. First hit wins, tombstones included.
FlushMode::Sync flushes inline on the calling thread instead - thread-free
and deterministic (for single-threaded / wasm targets or deterministic
replay), at the cost of a periodic write-latency spike on the write that
triggers a flush.
Durability: a frozen memtable queued for flush is not on disk until the
worker writes it, so a hard crash loses the queued + active memtables unless
the wal feature is recording them for replay - the same no-durability-
without-WAL profile as before, just with a slightly wider in-memory window.
LsmTree::flush forces everything pending to disk and blocks until it is.
If the background worker ever stops - a write error is retried, but a panic
is terminal - the tree stops accepting flushes: put, delete, flush and
compact return an error from that point rather than parking on a queue
nothing will drain. Reads keep serving whatever is already in memory and on
disk.
Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-lsm-tree
Re-exports§
pub use features::block_cache_integration::Block;pub use features::block_cache_integration::BlockCache;pub use features::block_cache_integration::BlockKey;pub use features::block_cache_integration::LruBlockCache;pub use features::leveled_compaction::LeveledCompactionPlanner;pub use features::leveled_compaction::LeveledManifest;pub use features::leveled_compaction::LeveledRun;pub use features::lz4::Lz4BlockCompressor;pub use features::snapshot::Snapshot;pub use features::snapshot::SnapshotManager;pub use features::snapshot::SnapshotManifest;pub use features::tiered_compaction::TieredCompactionPlanner;pub use features::tiered_compaction::TieredManifest;pub use features::tiered_compaction::TieredRun;pub use features::wal::WriteAheadLog;pub use features::zstd::ZstdBlockCompressor;
Modules§
- features
- Opt-in feature catalog. Each submodule is gated by its own Cargo feature flag and adds a specific capability to the base LSM tree without bloating the core build.
- recipe
SubMsRecipeimpl for the LSM tree perf workload. Behind theharnessfeature.