Crate masstree

Crate masstree 

Source
Expand description

§MassTree

A high-performance concurrent ordered map for Rust. Stores keys as &[u8] and supports variable-length keys by building a trie of B+trees.

§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 epoch-based deferred cleanup
  • Lazy leaf coalescing for deleted entries
  • Two node widths: MassTree (WIDTH=24) and MassTree15 (WIDTH=15)

§Variant Selection

VariantBest For
MassTree15Range scans, writes, shared-prefix keys, contention
MassTree (WIDTH=24)Random-access reads, single-threaded point ops

MassTree15 tends to perform better due to cheaper u64 atomics and better cache utilization. Consider it for most workloads.

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

§Performance Notes

On mixed read/write workloads (90% read, 10% write) at 6 threads, MassTree15 achieves 2-5x higher throughput than RwLock<BTreeMap> due to lock-free reads and per-node versioning. The advantage increases under contention.

For pure read workloads, RwLock<BTreeMap> is competitive or faster—lock-free structures pay complexity costs that only matter when there’s actual contention.

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

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

// Remove
tree.remove_with_guard(b"hello", &guard).unwrap();

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

§Thread Safety

MassTree<V> is Send + Sync when V: Send + Sync. Concurrent access requires using the guard-based API. The guard ties operations to an epoch for safe memory reclamation.

use masstree::MassTree;

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

// Concurrent get (lock-free)
let value = tree.get_with_guard(b"key", &guard);

// Concurrent insert (fine-grained locking)
let old = tree.insert_with_guard(b"key", 42, &guard);

§Key Constraints

  • Keys must be 0-256 bytes. Longer keys will panic.
  • Keys are byte slices (&[u8]), not generic types.

§How It Works

Keys are split into 8-byte slices, 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.

§Value Storage

  • MassTree<V>: Stores values as Arc<V>. Returns Arc<V> on get.
  • MassTreeIndex<V: Copy>: Convenience wrapper that copies values.

§Feature Flags

  • mimalloc: Uses mimalloc as the global allocator (recommended).
  • tracing: Enables structured logging to logs/masstree.jsonl.

Re-exports§

pub use leaf_trait::TreeInternode;
pub use leaf_trait::TreeLeafNode;
pub use leaf_trait::TreePermutation;
pub use alloc_trait::NodeAllocatorGeneric;
pub use permuter::AtomicPermuter;
pub use permuter::AtomicPermuter15;
pub use permuter::Permuter;
pub use permuter::Permuter15;
pub use permuter24::AtomicPermuter24;
pub use permuter24::Permuter24;
pub use permuter24::WIDTH_24;
pub use leaf15::LeafNode15;
pub use leaf15::WIDTH_15;
pub use leaf24::LeafNode24;
pub use leaf24::MODSTATE_DELETED_LAYER;
pub use leaf24::MODSTATE_INSERT;
pub use leaf24::MODSTATE_REMOVE;
pub use leaf24::WIDTH_24 as LEAF24_WIDTH;
pub use alloc15::SeizeAllocator15;
pub use alloc15::SeizeAllocator15TrueInline;
pub use alloc24::SeizeAllocator24;
pub use inline::bits::InlineBits;
pub use inline::leaf15_true::LeafNode15TrueInline;
pub use slot::true_inline::TrueInlineSlot;
pub use value::InsertTarget;
pub use value::LeafValue;
pub use value::LeafValueIndex;
pub use value::SplitPoint;
pub use link::Linker;
pub use ref_value_slot::RefValueSlot;
pub use slot::ValueSlot;
pub use suffix::InlineSuffixBag;
pub use suffix::PermutationProvider;
pub use suffix::SuffixBag;
pub use tree::InsertError;
pub use tree::RemoveError;
pub use tree::KeysIter;
pub use tree::RangeBound;
pub use tree::RangeIter;
pub use tree::ScanEntry;
pub use tree::ValuesIter;
pub use tree::MassTree;
pub use tree::MassTree15;
pub use tree::MassTree15Inline;
pub use tree::MassTree24;
pub use tree::MassTree24Inline;
pub use tree::MassTreeGeneric;
pub use tree::MassTreeIndex;
pub use tree::BatchEntry;
pub use tree::BatchInsertResult;
pub use tree::batch;

Modules§

alloc15
Node allocation for LeafNode15 with WIDTH=15 leaves and WIDTH=15 internodes.
alloc24
Node allocation for LeafNode24 (WIDTH=24).
alloc_trait
Generic allocator trait for tree nodes.
hints
Branch prediction hints for performance-critical paths.
inline
True-inline value storage for leaf nodes.
internode
Filepath: src/internode.rs
key
Filepath: src/key.rs
ksearch
Key search algorithms for MassTree.
leaf15
Filepath: src/leaf15.rs
leaf24
Filepath: src/leaf24.rs
leaf_trait
Traits for abstracting over leaf node WIDTH variants.
link
Pointer marking utilities for concurrent split operations.
node_pool
Thread-local node pools using size-class buckets.
nodeversion
Filepath: src/nodeversion.rs
ordering
Standard memory orderings for concurrent node access.
permuter
Filepath: src/permuter.rs
permuter24
24-slot permutation using u128 storage.
prefetch
Software prefetching utilities for cache optimization.
ref_value_slot
Marker trait for value slots that support reference returns.
slot
Value slot abstraction for crate::MassTree storage modes.
suffix
Filepath: src/suffix.rs
tree
Filepath: src/tree.rs MassTree - A high-performance concurrent trie of B+trees.
value
Value types for leaf node storage.

Structs§

AllocError
Error returned when memory allocation fails.
BatchedRetire
Batched retirement utilities.
FlushOnDrop
Guard that flushes the retirement batch on drop.

Enums§

AllocKind
Kind of allocation that failed.

Functions§

init_tracing
No-op when tracing feature is disabled.

Type Aliases§

AllocResult
Result type alias for fallible allocations.