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.

Status

Current Version: v0.9.1

Significantly reduced duplicate code through trait based abstractions, while improving performance further. All standard data structure features are implemented and streamlined, on top the specialized features like range scans and prefix queries. From latency analysis, it seems to have a surprisingly strong tail latency profile for a concurrent ordered map. The cache-line aligned layout design and aggressive prefetching seems to have paid off, on top of masstree's original excellent architecture.

The next issues to work on are the memory profile and memcomparable mappings for general key types, before 1.0.

vs Rust Concurrent Maps (12T SMT)

Source: runs/run199_read_write.txt (masstree), runs/run184_read_write_reworked.txt (competitors) Config: 12 threads on 6 physical cores (SMT/hyperthreading), 200 samples.

High-Impact Workloads (12T SMT)

Source: runs/run200_high_impact.txt (masstree), runs/run188_high_impact.txt (competitors) Config: 12 threads on 6 physical cores (SMT), 200 samples

Benchmarks targeting Masstree's architectural advantages: long keys, variable-length keys, hot key patterns, mixed operations, prefix queries, deep trie traversal, and mixed prefix workloads.

Range Scans (6T Physical)

Source: runs/run191_range_scan.txt Config: Physical cores only, 200 samples, performance governor

Range Scans (12T SMT)

Source: runs/run191_range_scan.txt Config: 12 threads on 6 physical cores (SMT), 200 samples

Tail Latency (pbench, Per-Operation)

Source: runs/run202_tail_latency.txt Config: 200k samples per benchmark, sample_size=1 (unbatched), TSC timer (10 ns precision)

Point Lookups

Inserts

Mixed Read/Write (8T)

Range Scans (8T, 50-key scan)

Install

[dependencies]
masstree = { version = "0.9.1", 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, RangeBound};

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

// Insert (returns None for new keys, Some(old) for existing)
tree.insert_with_guard(b"hello", 123, &guard);
tree.insert_with_guard(b"world", 456, &guard);

// Point lookup (returns copy for inline storage)
assert_eq!(tree.get_with_guard(b"hello", &guard), Some(123));

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

// Range scan
tree.scan(
    RangeBound::Included(b"a"),
    RangeBound::Excluded(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);
tree.insert(b"key2", 200);

assert_eq!(tree.get(b"key1"), Some(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);
}

// 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
• Integer keys only → congee (ART-based)
• Read-heavy with rare writes → RwLock<BTreeMap>

Which Tree Type Should I Use?

MassTree<V> (Default, True-Inline)

• Values stored directly in leaf nodes (zero allocation per insert)
• Returns V by copy: get_with_guard() → Option<V>
• Use scan() for range iteration

MassTree15<V> (Box-Based)

• Values stored as Box<V> raw pointers (heap allocation per insert)
• Returns ValuePtr<V>: a zero-cost Copy pointer with Deref to &V
• Supports get_ref() → Option<&V> for zero-copy access
• Use scan_ref() for zero-copy range iteration

MassTree<V> is the recommended default for Copy types like u64, i32, f64, pointers, etc. Use MassTree15<V> explicitly when you need to store non-Copy types like String.

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

// Default: inline storage for Copy types (recommended)
let tree: MassTree<u64> = MassTree::new();

// Box-based storage for non-Copy types
let tree_box: MassTree15<String> = MassTree15::new();

// Explicit inline storage (same as MassTree)
let inline: MassTree15Inline<u64> = MassTree15Inline::new();

Examples

The examples/ directory contains comprehensive usage examples:

cargo run --example basic_usage --features mimalloc --release      # Core API walkthrough
cargo run --example rayon_parallel --features mimalloc --release   # Parallel processing with Rayon
cargo run --example tokio_async --features mimalloc --release      # Async integration with Tokio
cargo run --example url_cache --features mimalloc --release        # Real-world URL cache
cargo run --example session_store --features mimalloc --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

CHANGELOG

0.9.1: Route based re-traversal for sublayer GC. Fixes UAF from duplicate queue entries and stale pointers in deeply nested chains. The correctness fix and proper GC path leads to substantial performance improvements.