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
• High-throughput value-only scans with scan_values (skips key materialization)
• Memory reclamation via hyaline scheme (seize crate)
• Lazy leaf coalescing for deleted entries
• Extremely high-performance inline variant MassTree15Inline, this is only usable on Copy types.

Status

v0.7.2 — Major performance enhancements. Core feature complete. Beats C++ Masstree on 7/8 benchmarks and Rust alternatives on 12/12 workloads (12T SMT). Passes Miri with strict-provenance flag. Concurrent data structures require extensive stress testing, the test suite is comprehensive (978 tests total) but edge cases may remain.

vs C++ Masstree (12T, 10s)

Results vary between runs and hardware configurations. The same benchmark (10 hot keys, 12 threads) consistently shows the largest improvement over C++, achieving 1.7x higher throughput under extreme contention. Possible factors:

• Hyaline memory reclamation — Unlike the C++ epoch-based reclamation (EBR), Hyaline (via seize crate) allows readers to avoid quiescent state registration
• Lazy coalescing — Empty leaves are queued for deferred cleanup rather than removed inline, avoiding lock-coupling issues during removes
• Sharded length counter — 16 cache-line-aligned shards for len() tracking (C++ doesn't track global count)

Note: The optimistic read protocol (version-based OCC) is the original Masstree design, not a divergence. One minor divergence: has_changed() uses > (LOCK_BIT | INSERTING_BIT) instead of C++'s > lock_bit, ignoring both bits 0-1. This is safe because version counters (VINSERT/VSPLIT) are the source of truth, INSERTING_BIT is only set while modifications are in-flight and not yet visible to readers. See src/nodeversion.rs:643-673 for the full safety argument.

The forward-sequential gap (rw3) narrowed from 57% to 81% but remains under investigation.

vs Rust Concurrent Maps (6T Physical, Rigorous)

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

This can be considered the current baseline.

Note: MassTree's insert() has upsert semantics, it updates existing keys and returns the old value. TreeIndex's insert() fails on existing keys, requiring a remove()+insert() fallback. Pure insert benchmarks (13, 14) use fresh keys only, providing a fairer comparison for insert-heavy workloads where TreeIndex performs better.

Single-thread latency: masstree15 achieves 836 µs median read latency vs tree_index 1.35 ms (1.61x faster).

Build time: masstree15 builds at 8.46 Mitem/s vs skipmap 6.17, tree_index 4.35, indexset 1.86 (1.37–4.6x faster).

vs Rust Concurrent Maps (12T SMT)

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

Wins 12/12. Deferred suffix retirement and pre-allocated suffix buffers improved insert throughput by 20–46%, flipping 14_pure_insert from a loss (0.75x in run151) to a win.

Single-thread latency (11): masstree15 achieves 829 µs median read latency vs tree_index 1.39 ms (1.67x faster).

Build time (12): masstree15 builds at 8.14 Mitem/s vs skipmap 6.29, tree_index 4.33, indexset 1.81 (1.29–4.5x faster).

SMT scaling highlights: High-contention workloads benefit most from hyperthreading, with masstree15 reaching 76.28 Mitem/s (4.27x vs alternatives). Insert-heavy workloads (13_insert_only_fair, 14_pure_insert) showed the largest gains from moving heap allocation and EBR retirement outside the leaf lock critical section.

Note: 06_single_hot_key regressed from 14.33 to 10.66 Mitem/s (-26%) compared to run151. With only one key contended across 12 threads, the increased leaf size (896→1152 bytes from inline suffix capacity doubling) likely worsens cache line sharing. masstree15 still leads all alternatives (next best: skipmap at 6.51).

High-Impact Workloads (12T SMT)

Source: runs/run154_high_impact_twig_optimization.txt 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, and deep trie traversal.

Wins 8/8 with margins from 1.32x to 3.03x.

Key insights:

• Long keys (128B): Unique prefixes test suffix handling; Masstree stores suffixes inline
• Variable keys (64-256B): Masstree takes &[u8] slices; others clone() Vec<u8>
• Multiple hot keys: OCC reads excel under localized contention (8 keys, 80% access)
• Mixed ops (70/20/10): seize-based reclamation handles concurrent deletes well
• Prefix queries: Native scan_prefix() vs range simulation (29x faster than tree_index)
• Deep trie: Shared prefix chunks force multi-layer descent; narrowest margin (1.32x)

Range Scans (6T Physical)

Source: runs/run161_range_scan.txt Config: Physical cores only, 100 samples, performance governor

Wins 15/15 vs TreeIndex with margins from 1.42x to 3.42x.

Range Scans (12T SMT)

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

Wins 15/15 vs TreeIndex. TreeIndex scales better on SMT for shared-prefix and suffix-differ workloads but Masstree maintains leadership with margins from 1.14x to 2.91x.

Install

[dependencies]
masstree = { version = "0.7.2", 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
• Integer keys only → congee (ART-based)
• Read-heavy with rare writes → RwLock<BTreeMap>

Type Aliases

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();

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

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

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