37 releases (23 stable)
2.4.0 | Nov 15, 2024 |
---|---|
2.1.1 | Oct 8, 2024 |
1.5.0 | Aug 5, 2024 |
1.4.0 | Jul 19, 2024 |
0.2.3 | Dec 25, 2023 |
#145 in Data structures
1,344 downloads per month
Used in 4 crates
(via fjall)
505KB
11K
SLoC
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.
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 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.
Feature flags
lz4
Allows using LZ4
compression, powered by lz4_flex
.
Disabled by default.
miniz
Allows using DEFLATE/zlib
compression, powered by miniz_oxide
.
Disabled by default.
bloom
Uses bloom filters to reduce superfluous disk I/O during point reads, improving performance, but also increasing memory usage.
Disabled by default.
Stable disk format
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.
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 --features lz4 --features miniz
Footnotes
[1] https://rocksdb.org/blog/2017/05/12/partitioned-index-filter.html
Dependencies
~4–12MB
~159K SLoC