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

Download history 88/week @ 2024-08-19 118/week @ 2024-08-26 102/week @ 2024-09-02 131/week @ 2024-09-09 434/week @ 2024-09-16 503/week @ 2024-09-23 233/week @ 2024-09-30 458/week @ 2024-10-07 431/week @ 2024-10-14 205/week @ 2024-10-21 590/week @ 2024-10-28 221/week @ 2024-11-04 517/week @ 2024-11-11 182/week @ 2024-11-18 304/week @ 2024-11-25 324/week @ 2024-12-02

1,344 downloads per month
Used in 4 crates (via fjall)

MIT/Apache

505KB
11K SLoC

CI docs.rs Crates.io MSRV dependency status

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

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

Dependencies

~4–12MB
~159K SLoC