masstree

A concurrent ordered map for Rust, based on the Masstree algorithm (trie of B+trees).

Status: Alpha

Not production ready. Use for evaluation and feedback only.

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

Why This Crate?

Rust lacks a popular concurrent ordered map. The ecosystem:

Skip lists have poor cache locality. B+trees allocate nodes in blocks, improving cache utilization. MassTree brings cache-efficient concurrent ordered maps to Rust.

Quick Start

Concurrent API (recommended)

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

// MassTree is Send + Sync when V: Send + Sync
let tree = Arc::new(MassTree::<u64>::new());

// Spawn concurrent readers and writers
let handles: Vec<_> = (0..4).map(|i| {
    let tree = Arc::clone(&tree);
    thread::spawn(move || {
        let guard = tree.guard();

        // Insert with guard (fine-grained locking)
        let _ = tree.insert_with_guard(b"key", i, &guard);

        // Get with guard (lock-free, version-validated)
        tree.get_with_guard(b"key", &guard)
    })
}).collect();

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

Single-threaded API

use masstree::MassTree;

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

// insert() requires &mut self - not for concurrent use
let _ = tree.insert(b"alice", 100)?;
let _ = tree.insert(b"bob", 200)?;

// get() returns Arc<V>
assert_eq!(*tree.get(b"alice").unwrap(), 100);
# Ok::<(), masstree::tree::InsertError>(())

Note: Keys must be 0-256 bytes. Longer keys will panic.

Performance

Benchmarks vs BTreeMap (single-threaded, cargo bench --bench comparison):

Where BTreeMap wins:

Concurrent Scaling

Tested against DashMap (note: different data structure category):

MassTree scales well for reads. High write contention favors DashMap's sharded design.

Architecture

MassTree implements the Masstree algorithm:

• Trie of B+trees: Keys split into 8-byte chunks, each navigating a B+tree layer
• Optimistic reads: Version validation, retry on concurrent modification
• Fine-grained locking: Per-leaf locks for writes, CAS for simple inserts
• B-link structure: Lock-free traversal during splits

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

Value Storage

Two modes:

// Default: Arc<V> for any value type
let tree: MassTree<MyStruct> = MassTree::new();

// Index mode: Copy types (planned optimization)
let index: MassTreeIndex<u64> = MassTreeIndex::new();

Arc<V> enables safe concurrent reads without guard lifetimes. The trade-off is atomic refcount overhead on access.

Known Limitations

1. Memory grows monotonically - Split nodes stay allocated until tree drop
2. No range scans - Ordered iteration not yet implemented
3. No deletion - Keys cannot be removed
4. Update overhead - Arc swap is slower than in-place mutation
5. Limited stress testing - Verified up to 8 threads
6. Key length limit - Keys > 256 bytes will panic (not a Result error)

Roadmap

• v0.1.0 (current): Core concurrent get/insert
• v0.2.0: Range scans, deletion, seize retirement
• v0.3.0: Performance optimization, stress testing
• v1.0.0: Production ready

Contributing

Feedback and bug reports welcome! This is an alpha release—expect rough edges.

# Run tests
cargo test

# Run benchmarks
cargo bench --bench comparison

# Run with Miri (requires nightly)
cargo +nightly miri test

References

• Masstree Paper (EUROSYS 2012)
• C++ Implementation
• seize (memory reclamation)

Disclaimer

This is an independent Rust implementation of the Masstree data structure. It is not affiliated with, endorsed by, or connected to the original authors (Eddie Kohler, Yandong Mao, Robert Morris) or their institutions.

License

MIT