#lsm #rocksdb #leveldb #database #lsmt #block-index #bloom-filter

lsm-tree

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

19 releases (6 stable)

new 1.0.5 May 24, 2024
0.8.0 May 13, 2024
0.6.3 Feb 27, 2024
0.2.3 Dec 25, 2023

#154 in Data structures

Download history 77/week @ 2024-02-01 82/week @ 2024-02-08 75/week @ 2024-02-15 259/week @ 2024-02-22 101/week @ 2024-02-29 119/week @ 2024-03-07 32/week @ 2024-03-14 6/week @ 2024-03-21 31/week @ 2024-03-28 14/week @ 2024-04-04 32/week @ 2024-04-11 26/week @ 2024-04-18 200/week @ 2024-04-25 161/week @ 2024-05-02 463/week @ 2024-05-09 896/week @ 2024-05-16

1,734 downloads per month
Used in 3 crates (via fjall)

MIT/Apache

400KB
9K SLoC

CI docs.rs Crates.io MSRV

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 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.

Feature flags

bloom

Uses bloom filters to reduce disk I/O for non-existing keys. Improves point read performance, but increases memory usage.

Disabled by default.

Stable disk format

The disk format is stable as of 1.0.0. 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

Footnotes

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

Dependencies

~3–13MB
~145K SLoC