masstree

A high-performance concurrent ordered map for Rust.

The Problem

Rust has dashmap for concurrent hash maps (millions of downloads/month), but no high-perm concurrent ordered map crates. The current options are (to my knowledge):

MassTree fills this gap with a cache-efficient B+tree that scales.

Benchmark Highlights

Two benchmark suites: lock_comparison (vs Mutex/RwLock<BTreeMap>) and concurrent_maps (vs crossbeam-skiplist).

Benchmark Caveats (Why The Gap Can Look Huge)

• Most read-throughput numbers use MassTree::get_ref(..., &guard) (no Arc clone) with a guard pinned once per thread, this is a best-case for Masstree’s design.
• Mutex<BTreeMap> / RwLock<BTreeMap> benchmarks take a lock per operation (as you would with a shared map), and use the standard library locks (not parking_lot).
• crossbeam-skiplist::SkipMap does not expose a reusable epoch guard in its high-level API, many operations pin/unpin internally per call. For a closer “same guard model” comparison, use crossbeam_skiplist::base::SkipList with an explicitly pinned guard.
• Current node allocation tracking (SeizeAllocator) uses a mutex on allocatio/deallocation, most read-heavy benchmarks don’t allocate nodes (and many “write” mixes are updates), so this overhead won’t show up unless you benchmark split-heavy growth.
• Concurrent-write results should be treated as being "WRONG" until remaining write-correctness bug (missing keys under contention) is fixed.

Where MassTree Does Well

Concurrent read throughput (32 threads):

Long keys with deep shared prefixes (16 common bytes), concurrent reads at 16 threads:

Single-threaded lookups scale better with key length:

Where MassTree Is Slower

Short keys (≤16B), single-threaded lookups:

The trie structure adds overhead for keys that fit in a single 8-byte slice. This is inherent to the algorithm—each lookup must traverse the trie even for short keys.

Mixed read/write workloads with Zipfian distribution:

Write-heavy hot spots expose layer creation overhead for long keys.

Concurrent Scaling Comparison

Read scaling from 1 to 32 threads:

MassTree's optimistic reads avoid lock acquisition entirely—readers never block each other.

Summary

This should be possible, after it is properly implemented with all features and rigorously stress tested for correctness and subtle concurrency issues (there's currently one that's getting actively worked on and is blocking concurrent writes, but I have concrete plan in mind to fix it). I WOULDN'T RECOMMEND USING THIS CRATE FOR ANYTHING CURRENTLY.

Status: Alpha

Not production ready at all. Core functionality works; APIs may change.

305 tests passing (unit, integration, property, loom, shuttle)

Quick Start

use masstree::MassTree;
use std::sync::Arc;
use std::thread;

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

let handles: Vec<_> = (0..8).map(|i| {
    let tree = Arc::clone(&tree);
    thread::spawn(move || {
        let guard = tree.guard();

        // Insert (fine-grained locking, not serialized)
        tree.insert_with_guard(b"user:1000", i, &guard).unwrap();

        // Read (lock-free, returns &V)
        if let Some(value) = tree.get_ref(b"user:1000", &guard) {
            println!("Got: {}", *value);
        }
    })
}).collect();

for h in handles { h.join().unwrap(); }

Use mimalloc for Best Performance

MassTree's allocation pattern benefits significantly from mimalloc:

#[global_allocator]
static GLOBAL: mimalloc::MiMalloc = mimalloc::MiMalloc;

Single-threaded improvement: 17% faster. The gap widens under contention.

How It Works

MassTree implements the Masstree algorithm (Mao, Kohler, Morris — EUROSYS 2012):

Trie of B+trees: Keys are split into 8-byte slices. Each slice navigates a B+tree layer. Longer keys chain through layers.

Key: "hello world!"

Layer 0: "hello wo" → B+tree lookup
                ↓
Layer 1: "rld!\0\0\0\0" → B+tree lookup → Value

Optimistic concurrency: Readers check version numbers before and after reading. If a concurrent write occurred, they retry. No locks acquired for reads.

Fine-grained writes: Writers lock only the target leaf node. CAS fast-path for simple inserts avoids locking entirely when possible.

B-link trees: Split operations use sibling pointers for lock-free traversal, allowing reads to proceed during structural modifications.

Memory Reclamation: The NodeAllocator trait abstracts memory management, designed for integration with seize's hyaline-based reclamation scheme.

Limitations

1. No deletion — keys cannot be removed (planned)
2. No range scans — ordered iteration not yet implemented (planned)
3. Arena reclamation — nodes freed only when tree drops
4. Key length — max 256 bytes, longer keys panic
5. Long key insert cost — multi-layer creation adds overhead vs skip lists

Running Benchmarks

# Recommended: use mimalloc
cargo bench --bench concurrent_maps --features mimalloc
cargo bench --bench lock_comparison --features mimalloc

# Compare against standard allocator
cargo bench --bench concurrent_maps

# Run tests
cargo test

# Miri (requires nightly)
cargo +nightly miri test

Contributing

This project needs help with:

• Permutation Freeze - Currently working this. Please check the open issues.
• Deletion + memory reclamation — integrate seize for safe concurrent deletes
• Range scans — ordered iteration like BTreeMap::range()
• Benchmarking — more workloads, different hardware, methodology validation
• Stress testing — adversarial concurrent patterns

References

• Masstree: A Cache-Friendly Mashup of Tries and B-Trees (EUROSYS 2012)
• C++ Reference Implementation
• seize — Hyaline Memory Reclamation

Disclaimer

Independent Rust implementation of the Masstree algorithm. Not affiliated with or endorsed by the original authors.

License

MIT