Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index

Summary

Bf-Tree is a modern read-write-optimized concurrent larger-than-memory range index in Rust from MSR. Design Details You can find the Bf-Tree research paper here. You can find more design docs here. User Guide Rust Bf-Tree is written in Rust, and is available as a Rust crate. You can add Bf-Tree to your Cargo.toml like this: [ dependencies ] bf-tree = " 0.1.0 " An example use of Bf-Tree: use bf_tree :: BfTree ; use bf_tree :: LeafReadResult ; let mut config = bf_tree :: Config :: default ( ) ; config . cb_min_record_size ( 4 ) ; let tree = BfTree :: with_config ( config , None ) . unwrap ( ) ; tree . insert ( b"key" , b"value" ) ; let mut buffer = [ 0u8 ; 1024 ] ; let read_size = tree . read ( b"key" , & mut buffer ) ; assert_eq ! ( read_size , LeafReadResult :: Found ( 5 ) ) ; assert_eq ! ( & buffer [ .. 5 ] , b"value" ) ; PRs are accepted and preferred over feature requests. Feel free to reach out if you have any design questions. Developer Guide Building Prerequisite Bf-Tree supports Linux, Windows, and macOS, although only a recently version of Linux is rigorously tested. Bf-Tree is written in Rust, which you can install here. Please install pre-commit hooks to ensure that your code is formatted and linted in the same way as the rest of the project; the coding style will be enforced in CI, these hooks act as a pre-filter. # If on Ubuntu sudo apt update && sudo apt install pre-commit pre-commit install Build cargo build --release Testing Unit Tests cargo test Shuttle Tests Concurrent systems are nondeterministic, and subject to exponential amount of different thread interleaving. We use shuttle to deterministically and systematically explore different thread interleaving to uncover the bugs caused by subtle multithread interactions. cargo test --features " shuttle " --release shuttle_bf_tree_concurrent_operations (Takes about 5 minute to run) Fuzz Tests Fuzz testing is a bug finding technique that generates random inputs to the system and test for crash. Bf-Tree e...