masstree

A high-performance concurrent ordered map for Rust. It stores keys as &[u8] and supports variable-length keys by building a trie of B+trees, based on the Masstree paper

Disclaimer: This is an independent implementation. It is not endorsed by, affiliated with, or connected to the original Masstree authors or their institutions.

Features

• Ordered map for byte keys (lexicographic ordering)
• Lock-free reads with version validation
• Concurrent inserts and deletes with fine-grained leaf locking
• Zero-copy range scans with scan_ref and scan_prefix
• Memory reclamation via hyaline scheme (seize crate)
• Lazy leaf coalescing for deleted entries
• Two node widths: MassTree (WIDTH=24) and MassTree15 (WIDTH=15)

Status

v0.3.0 — Core feature complete. It has been heavily tested but I am not sure about whether it should be usd in actual projects. Such low-level cncurrent data structures usually need a lot of stress testing and have a lot of edge cases that are not easily noticeable. The unsafe code passes miri with strict-provenance flag, but that doesn't really ensure correctness.

Tests: 755 tests (466 unit + 88 ported from C++ reference + integration). Miri strict provenance clean.

Not yet implemented: Entry API, DoubleEndedIterator, Extend/FromIterator.

Install

[dependencies]
masstree = { version = "0.3", features = ["mimalloc"] }

MSRV is Rust 1.92+ (Edition 2024).

The mimalloc feature sets the global allocator. If your project already uses a custom allocator, omit this feature.

Quick Start

use masstree::MassTree;

let tree: MassTree<u64> = MassTree::new();
let guard = tree.guard();

// Insert
tree.insert_with_guard(b"hello", 123, &guard).unwrap();
tree.insert_with_guard(b"world", 456, &guard).unwrap();

// Point lookup
assert_eq!(tree.get_ref(b"hello", &guard), Some(&123));

// Remove
tree.remove_with_guard(b"hello", &guard).unwrap();
assert_eq!(tree.get_ref(b"hello", &guard), None);

// Range scan (zero-copy)
tree.scan_ref(b"a"..b"z", |key, value| {
    println!("{:?} -> {}", key, value);
    true // continue scanning
}, &guard);

// Prefix scan
tree.scan_prefix(b"wor", |key, value| {
    println!("{:?} -> {}", key, value);
    true
}, &guard);

Ergonomic APIs

For simpler use cases, auto-guard versions create guards internally:

use masstree::MassTree;

let tree: MassTree<u64> = MassTree::new();

// Auto-guard versions (simpler but slightly more overhead per call)
tree.insert(b"key1", 100).unwrap();
tree.insert(b"key2", 200).unwrap();

assert_eq!(tree.get(b"key1"), Some(std::sync::Arc::new(100)));
assert_eq!(tree.len(), 2);
assert!(!tree.is_empty());

tree.remove(b"key1").unwrap();

Range Iteration

use masstree::{MassTree, RangeBound};

let tree: MassTree<u64> = MassTree::new();
let guard = tree.guard();

// Populate
for i in 0..100u64 {
    tree.insert_with_guard(&i.to_be_bytes(), i, &guard).unwrap();
}

// Iterator-based range scan
for entry in tree.range(RangeBound::Included(b""), RangeBound::Unbounded, &guard) {
    println!("{:?} -> {:?}", entry.key(), entry.value());
}

// Full iteration
for entry in tree.iter(&guard) {
    println!("{:?}", entry.key());
}

When to Use

May work well for:

• Long keys with shared prefixes (URLs, file paths, UUIDs)
• Range scans over ordered data
• Mixed read/write workloads
• High-contention scenarios (the trie structure helps here)

Consider alternatives for:

• Unordered point lookups → dashmap
• Pure insert-only workloads → scc::TreeIndex
• Integer keys only → congee (ART-based)
• Read-heavy with rare writes → RwLock<BTreeMap>

Variant Selection

Two variants are provided with different performance characteristics:

MassTree15 tends to perform better in our benchmarks due to cheaper u64 atomics and better cache utilization. Consider it for most workloads unless you have uniform random-access patterns.

use masstree::{MassTree, MassTree15, MassTree24Inline, MassTree15Inline};

// Default: WIDTH=24, Arc-based storage
let tree: MassTree<u64> = MassTree::new();

// WIDTH=15, Arc-based storage (recommended for most workloads)
let tree15: MassTree15<u64> = MassTree15::new();

// Inline storage for Copy types (no Arc overhead)
let inline: MassTree24Inline<u64> = MassTree24Inline::new();
let inline15: MassTree15Inline<u64> = MassTree15Inline::new();

Benchmarks

6 physical cores, mimalloc allocator, Divan framework with 200 samples per benchmark. Your mileage may vary.

vs Rust Competitors (6 threads, median throughput)

MassTree15 wins all benchmark categories. The high-contention advantage reflects per-node versioning design.

vs C++ Reference (6 threads, mean throughput)

Rust wins 6/8 benchmarks. Trails on sequential patterns (-4% to -40%) where C++ has prefetching advantages.

Note: This implementation diverges from C++ in several ways (notably hyaline-based memory reclamation via seize). Direct comparison is imperfect.

vs RwLock<BTreeMap> (6 threads)

The main question: when does a complex lock-free structure beat a simple RwLock<BTreeMap>?

Mixed read/write workloads (where MassTree is designed to help):

MassTree's lock-free reads and per-node versioning help when writers need to make progress. The 2-5x advantage shows up when there's actual contention.

Pure read workloads (where RwLock naturally wins):

For read-only workloads, RwLock has minimal overhead (one atomic to acquire) while MassTree pays for version validation on every access. Range scans are particularly lopsided because RwLock holds the lock for the entire scan. This is expected - lock-free structures pay complexity costs that only matter under contention.

How It Works

Masstree splits keys into 8-byte chunks, creating a trie where each node is a B+tree:

Key: "users/alice/profile" (19 bytes)
     └─ Layer 0: "users/al" (8 bytes)
        └─ Layer 1: "ice/prof" (8 bytes)
           └─ Layer 2: "ile" (3 bytes)

Keys with shared prefixes share upper layers, making lookups efficient for hierarchical data.

Examples

The examples/ directory contains comprehensive usage examples:

cargo run --example basic_usage --release      # Core API walkthrough
cargo run --example rayon_parallel --release   # Parallel processing with Rayon
cargo run --example tokio_async --release      # Async integration with Tokio
cargo run --example url_cache --release        # Real-world URL cache
cargo run --example session_store --release    # Concurrent session store

Rayon Integration

MassTree works seamlessly with Rayon for parallel bulk operations:

use masstree::MassTree15Inline;
use rayon::prelude::*;
use std::sync::Arc;

let tree: Arc<MassTree15Inline<u64>> = Arc::new(MassTree15Inline::new());

// Parallel bulk insert (~10M ops/sec)
(0..1_000_000).into_par_iter().for_each(|i| {
    let key = format!("key/{i:08}");
    let guard = tree.guard();
    let _ = tree.insert_with_guard(key.as_bytes(), i, &guard);
});

// Parallel lookups (~45M ops/sec)
let sum: u64 = (0..1_000_000).into_par_iter()
    .map(|i| {
        let key = format!("key/{i:08}");
        let guard = tree.guard();
        tree.get_with_guard(key.as_bytes(), &guard).unwrap_or(0)
    })
    .sum();

Tokio Integration

MassTree is thread-safe but guards cannot be held across .await points:

use masstree::MassTree15;
use std::sync::Arc;

let tree: Arc<MassTree15<String>> = Arc::new(MassTree15::new());

// Spawn async tasks that share the tree
let handle = tokio::spawn({
    let tree = Arc::clone(&tree);
    async move {
        // Guard must be scoped - cannot be held across await!
        {
            let guard = tree.guard();
            let _ = tree.insert_with_guard(b"key", "value".to_string(), &guard);
        } // guard dropped here

        tokio::time::sleep(Duration::from_millis(10)).await;

        // Create new guard after await
        let guard = tree.guard();
        tree.get_with_guard(b"key", &guard)
    }
});

// For CPU-intensive operations, use spawn_blocking
let tree_clone = Arc::clone(&tree);
tokio::task::spawn_blocking(move || {
    let guard = tree_clone.guard();
    for entry in tree_clone.iter(&guard) {
        // Process entries...
    }
}).await;

Crate Features

• mimalloc — Use mimalloc as global allocator (recommended)
• tracing — Enable structured logging to logs/masstree.jsonl

License

MIT. See LICENSE.

References

• Masstree Paper (EuroSys 2012)
• C++ Reference Implementation

AI Assist Disclaimer

It should be obvious that such a high number of tests, benchmarks and docs could not be written by hand this fast. Even though the full design and implementation was written by hand, there's still a a significant amount of AI generated code. I have gone through most of the docs,tests and benches to ensure correctness and also added the 'prompt' for the agent I used to analyze C++ codebase.

Apart from writing the above mentioned things, it was also used to write prototype ideas to optimize the implementation (most of which (like 80-90%) didn't work out well, and I had to just revert or remove them entirely, this can be seen if you go through the commits). The CAS insert fast path and a direct port of leaf coalescing was something that the model (Opus 4.5) was pushing aggressively, even though it was fundamentally unsound for masstree and leads to EXTREMELY subtle data races and synchronization issues and transient stress test failures.

In this commit, I am adding AI generated ASCII diagrams to provide top level overviews of the modules, core algorithms, operations and types.