A K.I.S.S. implementation of log-structured merge trees (LSM-trees/LSMTs) in Rust.

This crate only provides a primitive LSM-tree, not a full storage engine. For example, it does not ship with a write-ahead log. You probably want to use https://github.com/fjall-rs/fjall instead.

This is the most feature-rich LSM-tree implementation in Rust! It features:

• Thread-safe BTreeMap-like API
• 100% safe & stable Rust
• Block-based tables with compression support
• Range & prefix searching with forward and reverse iteration
• Size-tiered, (concurrent) Leveled and FIFO compaction
• Multi-threaded flushing (immutable/sealed memtables)
• Partitioned block index to reduce memory footprint and keep startup time short [1]
• Block caching to keep hot data in memory
• Bloom filters to increase point lookup performance (bloom feature, disabled by default)
• Snapshots (MVCC)
• Key-value separation (optional) [2]
• Single deletion tombstones ("weak" deletion)

Keys are limited to 65536 bytes, values are limited to 2^32 bytes. As is normal with any kind of storage engine, larger keys and values have a bigger performance impact.

Allows using LZ4 compression, powered by lz4_flex.

Disabled by default.

Allows using DEFLATE/zlib compression, powered by miniz_oxide.

Disabled by default.

Uses bloom filters to reduce superfluous disk I/O during point reads, improving performance, but also increasing memory usage.

Disabled by default.

Uses bytes as the underlying Slice type.

Disabled by default.

The disk format is stable as of 1.0.0.

2.0.0 uses a new disk format and needs a manual format migration.

Future breaking changes will result in a major version bump and a migration path.

All source code is licensed under MIT OR Apache-2.0.

All contributions are to be licensed as MIT OR Apache-2.0.

cargo bench --features bloom --features lz4 --features miniz

[1] https://rocksdb.org/blog/2017/05/12/partitioned-index-filter.html

[2] https://github.com/facebook/rocksdb/wiki/BlobDB