Lib.rs

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.

cargo add lsm-tree

About

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 LZ4 compression
• Range & prefix searching with forward and reverse iteration
• Size-tiered, (concurrent) Levelled 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)

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.

Stable disk format

The disk format will be stable from 1.0.0 (oh, the dreaded 1.0.0...) onwards. As of 0.7.0 the disk format is generally stabilized, but will have one final breaking change going into 1.0.0.

License

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

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

Development

Run benchmarks

cargo bench --features bloom

Footnotes

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