# bf-tree: a concurrent range index that outgrew memory

> Bf-Tree is an MIT licensed Rust crate from Microsoft Research implementing a read-write-optimized concurrent range index whose data set is larger than memory, with CPR-style consistent snapshots for recovery. Its test story is unusually strong, using the shuttle scheduler to explore thread interleavings deterministically and fuzzing to catch crashes.

**microsoft/bf-tree** — Bf-Tree is a modern read-write-optimized concurrent larger-than-memory range index in Rust from MS Research.

- Repository: https://github.com/microsoft/bf-tree
- Stars: 1,077 · Forks: 49
- Language: Rust
- License: MIT
- Published: 2026-10-19 · Updated: 2026-10-19 · Language: en
- Canonical page: https://hysenlabs.com/projects/microsoft-bf-tree

## What larger-than-memory changes

Bf-Tree is described as a modern read-write-optimized concurrent larger-than-memory range index in Rust from MSR, and the phrase doing the most work in that sentence is larger-than-memory.

A range index that fits in memory does not need to be a research project. A B-tree in a process with a lock around it is fast, simple, and well understood. The difficulty starts when the indexed data is larger than the RAM of the machine, and the design has to deal with what that implies.

Concretely, an index larger than memory means the interesting parts are not on disk. A write has to be durable somewhere, a read has to find data that may have been evicted, and a restart has to reconstruct state without scanning everything. The tree needs a write-ahead log so that committed writes survive a crash, and it needs a cache, and the cache has to be reconstructible from the log and from what is on disk.

The Cargo.toml confirms the write-ahead log is a first-class part of the API, since recovery options include an optional wal configuration for a recovered tree. The io-uring dependency on Linux points at asynchronous I/O for the same reason. A structure that is bigger than memory is defined by how it moves bytes to and from storage, and that is where most of the engineering goes.

The project is a research artefact from Microsoft Research with the research paper published at VLDB 2024 and additional design documents in the doc/ directory of the repository. The two together are the real documentation, and they are where the guarantees and the design rationale live.

## The Rust API is small and the crate is on crates.io

The user guide is short, and the API surface reflects that this is a library rather than a framework.

Adding it to a project is a single command:

```bash
$ cargo add bf_tree
```

Which adds the dependency to Cargo.toml:

```toml
[dependencies]
bf-tree = "0.5.5"
```

The crate name and the dependency name differ, with the package being bf-tree and the import path being bf_tree, which is a small trap worth knowing before you write your first import.

The example shows the whole shape of the API. A Config is created and adjusted, the tree is built from it, and then you insert and read:

```rust
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");
```

Two design points in that snippet. The read returns a LeafReadResult rather than a plain length, so the caller can distinguish a found value from a miss or an error, which matters when a miss may be a cache miss rather than an absent key. And reads write into a caller-provided buffer, so the allocation policy is the caller's, which is how you avoid a per-read heap allocation in a hot path.

The Config object carries the tunables, and the second argument to with_config is the cache buffer pointer, where None means the tree allocates one. The version in Cargo.toml is 0.5.6 on edition 2021, and the crate is published on crates.io.

## CPR snapshots give the tree a recovery story

The snapshot support is the feature that makes Bf-Tree usable as a system component rather than a research artefact, and the CPR naming is worth explaining through the documented behaviour.

Bf-Tree supports CPR-style consistent snapshots. A snapshot captures a consistent prefix of all in-flight transactions to a file, and a tree can later be reconstructed from such a snapshot file.

That is a different guarantee from a filesystem-level copy or a checkpoint of the in-memory state. The snapshot is a point in the logical transaction history, so the recovered tree contains exactly the writes that had committed, with no torn transactions and no need to replay an arbitrary amount of the log.

To enable it you call use_snapshot(true) on the Config before creating the tree, and then call BfTree::cpr_snapshot with the destination path to take a snapshot at any point. Snapshots can be taken concurrently with ongoing reads and writes, though only one snapshot may be in progress at a time.

Recovery goes through BfTree::new_from_cpr_snapshot. The snapshot file embeds most of the configuration, including the record sizes, the leaf page size and the cache-only flag, so the caller only has to specify the recovery-time options:

```rust
let tree = BfTree::new_from_cpr_snapshot(
    "snapshot.bftree",
    /* use_snapshot */ true,
    /* buffer_ptr */ None,
    /* buffer_size */ None,
    /* wal */ None,
).unwrap();
```

The buffer_size option has a documented constraint that is easy to trip over. It is an optional override of the cache size stored in the snapshot, and if it is smaller than the original, recovery may fail because cached pages from the snapshot must fit in memory.

There is also a coordination function, are_all_threads_in_next_snapshot_version, which reports whether all active threads have transitioned to the next snapshot version, meaning all threads are operating in v + 1. That is useful for coordinating external systems that need to wait until the snapshot's data is fully consistent, without waiting for the whole snapshot to finish. It returns false if no snapshot is ongoing.

One operational note is stated plainly: the path passed to cpr_snapshot must be different from the path used by any concurrent recovery. The design document is at doc/snapshot-recovery.md.

## Shuttle testing is how this project finds concurrency bugs

The testing section is the most distinctive part of the developer guide, and it reflects the fact that the hard failures in this kind of structure are intermittent.

The reasoning is stated first. Concurrent systems are nondeterministic, and subject to an exponential amount of different thread interleaving. The project uses shuttle to deterministically and systematically explore different thread interleavings to uncover bugs caused by subtle multithread interactions.

The shuttle tests are feature-gated so they do not run by default:

```bash
# Core Bf-tree concurrent operations (~5 minutes)
cargo test --features "shuttle" --release shuttle_bf_tree_concurrent_operations

# CPR snapshot with disk-backed storage (fast, < 1s)
cargo test --features "shuttle" --release shuttle_cpr_snapshot_disk

# CPR snapshot with cache-only (in-memory) storage
cargo test --features "shuttle" --release shuttle_cpr_snapshot_cache_only
```

And a failing schedule is automatically written out, so it can be replayed deterministically:

```bash
cargo test --features "shuttle" --release shuttle_replay -- --nocapture
```

That replay step is what makes shuttle practical rather than a curiosity. A bug found in a concurrent test is otherwise gone, because the interleaving that produced it will not happen again. Writing the schedule to target/schedule000.txt on failure and replaying it means a flaky test becomes a reproducible one.

Alongside that sits fuzzing. Fuzz testing is described as a bug-finding technique that generates random inputs and tests for a crash, and Bf-Tree uses it to generate random operation sequences such as insert, read and scan, checking that no operation sequence crashes the system or leads to inconsistent state. The details are in the fuzz/ folder.

The ordinary tests are the usual cargo test, and the dev dependencies show the rest of the toolkit: proptest for property-based testing, rstest for fixtures, tempfile for temporary files, and shuttle itself. Shuttle 0.7.1 is a dev dependency, and the shuttle feature in Cargo.toml is an empty feature list, which is how the gated tests are switched on without pulling the library into a normal build.

## Platform support, benchmarking, and the build environment

The platform story is stated with a caveat that is worth taking seriously.

Bf-Tree supports Linux, Windows and macOS, although only a recent version of Linux is rigorously tested. That is a deliberate asymmetry, and it makes sense given the dependency set: io-uring on Linux, windows-sys with the threading and Windows programming features on Windows, and libc on Linux.

The developer prerequisites are Rust itself, installed through rustup, and pre-commit hooks. The hooks are explained with a reason rather than as a formality: they ensure your code is formatted and linted in the same way as the rest of the project, and the coding style will be enforced in CI, so the hooks act as a pre-filter.

```bash
# If on Ubuntu
sudo apt update && sudo apt install pre-commit
pre-commit install
```

The build itself is cargo build --release, and the tests are cargo test.

The benchmarking setup is more elaborate, and the flags tell you what the authors cared about. The basic run is a filter on the benchmark name plus a mimalloc setting:

```bash
cd benchmark
env SHUMAI_FILTER="inmemory" MIMALLOC_LARGE_OS_PAGES=1 cargo run --bin bftree --release
```

MIMALLOC_LARGE_OS_PAGES is the mimalloc allocator using large operating system pages, which matters for a structure that is defined by its memory access patterns. The advanced run adds metrics collection, NUMA node binding and huge page reservation:

```bash
env MIMALLOC_SHOW_STATS=1 MIMALLOC_LARGE_OS_PAGES=1 MIMALLOC_RESERVE_HUGE_OS_PAGES_AT=0 numactl --membind=0 --cpunodebind=0 cargo bench --features "metrics-rt" micro
```

The metrics-rt feature is the runtime metrics feature, and the Cargo.toml comment explains its design: release metrics are saved in static crate-level thread-local storage and each thread can only access its own copy, so the overhead is low.

The repository also ships Nix tooling, with a default.nix, a shell.nix and a nix/ directory, plus a rust-toolchain.toml pinning the toolchain, so a reproducible environment is available for CI and for benchmarking.

## Where Bf-Tree is the wrong tool

The first wrong case is the most common one. If your data fits in memory, a larger-than-memory index is a downgrade. A concurrent B-tree in memory with a lock, or even a well-tuned single-threaded one, will be faster, use less code, and be far easier to reason about. The complexity of Bf-Tree buys you the ability to exceed RAM, and if you do not need that, you are paying for insurance you do not use.

The second is that this is a research codebase, and it is honest about it. It comes from Microsoft Research, the README points at a research paper and a doc/ directory of design documents, there are no GitHub releases, and the crate version is 0.5.6, which in a 0.x line means the API is explicitly not stable. The project does say that pull requests are accepted and preferred over feature requests, and that design questions can be raised, which is the sign of a project that wants outside input. But there is no compatibility promise, no long-term support window, and no patch commitment.

The third is the operational surface. A structure with a write-ahead log, a cache, a snapshot format and a recovery path is a system with operational procedures attached. Someone has to decide where the log goes, how large the cache should be, how often snapshots are taken, and what happens when recovery fails because the cache is too small for the snapshot. If you are looking for a library to call and forget, this is not that.

The fourth is a specific constraint worth calling out. The buffer_size override on recovery must not be smaller than the original, because the cached pages in the snapshot have to fit in memory, and recovery may fail otherwise. That is a sharp edge in an operation you would run in the middle of an incident, and it is exactly the kind of thing to test before you need it.

## Conclusion

bf-tree is a good pick for a Rust system that needs a concurrent range index over more data than fits in memory and wants read and write performance rather than a simpler design, because the CPR snapshot support gives it a real recovery story and the shuttle based test suite is what a concurrent structure like this needs to be trusted; it is the wrong pick for a workload that fits comfortably in memory, where a B-tree plus a lock is simpler and faster, and before you adopt it you should read the design documents in doc/ and the VLDB 2024 paper, since the API and its guarantees are only fully explained there.

## FAQ

### What is bf-tree and what problem does it solve?

It is a modern read-write-optimized concurrent larger-than-memory range index written in Rust at Microsoft Research. Larger than memory means the indexed data set does not fit in RAM, which requires a write-ahead log, a cache and a recovery path rather than a plain in-memory B-tree.

### How do I add bf-tree to a Rust project?

Run cargo add bf_tree, which adds the dependency to Cargo.toml as bf-tree = "0.5.5". The package is named bf-tree and the import path is bf_tree, so the two differ.

### How do snapshots and recovery work in bf-tree?

Enable them with use_snapshot(true) on the Config before creating the tree, then call BfTree::cpr_snapshot with a destination path to capture a consistent prefix of in-flight transactions. Recover with BfTree::new_from_cpr_snapshot, specifying only the recovery-time options, since the snapshot file embeds the record sizes, leaf page size and cache-only flag.

### How does bf-tree test for concurrency bugs?

It uses shuttle to deterministically explore thread interleavings, run under a shuttle cargo feature, with separate tests for the core concurrent operations and for CPR snapshots on disk-backed and cache-only storage. A failing schedule is written to target/schedule000.txt and can be replayed with the shuttle_replay test.

### Which platforms does bf-tree support?

Linux, Windows and macOS, although the documentation says only a recent version of Linux is rigorously tested. The build is cargo build --release, and the crate requires Rust plus pre-commit hooks so that formatting and linting match what CI enforces.

## Sources

- [Issues](https://github.com/microsoft/bf-tree/issues)
- [License: MIT](https://github.com/microsoft/bf-tree/blob/main/LICENSE)
- [microsoft/bf-tree on GitHub](https://github.com/microsoft/bf-tree)
- [README](https://github.com/microsoft/bf-tree/blob/main/README.md)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/microsoft-bf-tree