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_refandscan_prefix - Memory reclamation via epoch-based deferred cleanup
- Lazy leaf coalescing for deleted entries
- Two node widths:
MassTree(WIDTH=24) andMassTree15(WIDTH=15)
§Status: v0.3.0 (Core Feature Complete)
All core operations implemented and tested. Not yet production-ready—concurrent data structures require extensive stress testing beyond what Miri and proptests provide.
| Feature | Status |
|---|---|
| Concurrent get | Lock-free, version-validated |
| Concurrent insert | Fine-grained leaf locking |
| Concurrent remove | Fine-grained locking + lazy coalescing |
| Range scans | scan, scan_ref, scan_prefix, iterator |
| Memory reclamation | Seize-based epoch reclamation |
Not yet implemented: Entry API, DoubleEndedIterator, Extend/FromIterator.
§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 - Pure insert-only workloads →
scc::TreeIndex - Integer keys only →
congee(ART-based) - Read-heavy with rare writes →
RwLock<BTreeMap>
§Variant Selection
| Variant | Best For |
|---|---|
MassTree15 | Range 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.
§Architecture Overview
┌─────────────────────────────────────────────────┐
│ MassTreeGeneric<S,L,A> │
│ │
│ root_ptr ──► Leaf or Internode (Layer 0 root) │
│ collector ─► seize::Collector (reclamation) │
│ count ─────► ShardedCounter (approx size) │
│ coalesce_queue ─► CoalesceQueue (lazy cleanup) │
└─────────────────────────────────────────────────┘
│
▼
┌───────────────────────────────────────────────────────────────┐
│ LAYER 0 │
│ │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │Internode │ │Internode │ │Internode │ │
│ └────┬─────┘ └────┬─────┘ └────┬─────┘ │
│ │ │ │ │
│ ┌────┴────┐ ┌────┴────┐ ┌────┴────┐ │
│ ▼ ▼ ▼ ▼ ▼ ▼ │
│ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │
│ │Leaf│◄─►│Leaf│◄─►│Leaf│◄─►│Leaf│◄─►│Leaf│◄─►│Leaf│ (B-link) │
│ └────┘ └─┬──┘ └────┘ └────┘ └────┘ └────┘ │
│ │ layer_ptr │
└─────────────┼─────────────────────────────────────────────────┘
│
▼
┌────────────────────────────────────────────────────────────────┐
│ LAYER 1 │
│ │
│ ┌──────────┐ │
│ │ Internode│ (sublayer root) │
│ └────┬─────┘ │
│ ┌────┴────┐ │
│ ▼ ▼ │
│ ┌────┐ ┌────┐ │
│ │Leaf│◄─►│Leaf│ │
│ └────┘ └────┘ │
└────────────────────────────────────────────────────────────────┘§Node Structure
┌─────────────────────────────────────────────────────────────────────────────┐
│ LEAF NODE (WIDTH=15 or 24) │
├─────────────────────────────────────────────────────────────────────────────┤
│ version: NodeVersion ─────────────────────────────────────────────────────┤
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ bits: u32 │ │
│ │ ├─ bit 0: LOCK_BIT (exclusive access) │ │
│ │ ├─ bit 1: INSERTING_BIT (insert in progress) │ │
│ │ ├─ bit 2: SPLITTING_BIT (split in progress) │ │
│ │ ├─ bits 3-8: VINSERT (insert version, 6 bits) │ │
│ │ ├─ bits 9-27: VSPLIT (split version, 19 bits) │ │
│ │ ├─ bit 28: RESERVED (unused) │ │
│ │ ├─ bit 29: DELETED_BIT (logically deleted) │ │
│ │ ├─ bit 30: ROOT_BIT (is layer root) │ │
│ │ └─ bit 31: ISLEAF_BIT (leaf vs internode) │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ permutation: AtomicPermuter15/24 ─────────────────────────────────────────┤
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ Encodes logical→physical slot mapping + size in single atomic │ │
│ │ WIDTH=15: u64 (4 bits × 15 slots + 4-bit size) │ │
│ │ WIDTH=24: u128 (5 bits × 24 slots + 4-bit size) │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ ikeys: [AtomicU64; WIDTH] ─────────────────────────────────────────────── │
│ keylenx: [AtomicU8; WIDTH] (suffix info: 0-8=inline, 64=suffix, 65=layer) │
│ values: [AtomicPtr<u8>; WIDTH] (Arc<V> or inline V or layer_ptr) │
│ suffix: SuffixBag (key bytes beyond 8-byte ikey prefix) │
│ prev/next: AtomicPtr<Self> (B-link chain for siblings) │
│ parent: AtomicPtr<Internode> (parent pointer for split propagation) │
└─────────────────────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────────────────────┐
│ INTERNODE (WIDTH=15 fixed) │
├─────────────────────────────────────────────────────────────────────────────┤
│ version: NodeVersion │
│ nkeys: u8 (0..=15 keys) │
│ ikeys: [AtomicU64; 15] (routing keys) │
│ children: [AtomicPtr<u8>; 16] (child pointers: leaf or internode) │
│ parent: AtomicPtr<Internode> (parent for propagation) │
└─────────────────────────────────────────────────────────────────────────────┘§Operation Flows
§GET (Lock-Free Read)
┌──────────────────────────────────────────────────────────────────────────────┐
│ GET OPERATION - LOCK-FREE WITH OCC │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ get_with_guard(key, guard) │
│ │ │
│ │ key = Key::new(bytes) ← Split into 8-byte ikey chunks │
│ │ layer = 0 ← Start at layer 0 │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────────────┐ │
│ │ LAYER LOOP (for multi-layer keys) │ │
│ │ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Load root │──── AtomicPtr::load(Acquire) from root_ptr │ │
│ │ │ for layer │ Layer 0: tree.root, Layer N: sublayer root │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────────────────────────────────────────────────────┐ │ │
│ │ │ INTERNODE DESCENT LOOP │ │ │
│ │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Check node │──── version.is_leaf()? │ │ │
│ │ │ │ type │ │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ┌────┴────┐ │ │ │
│ │ │ │ Leaf │ Internode │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ EXIT ┌──────────────┐ │ │ │
│ │ │ LOOP │ Read version │──── v = version.stable() │ │ │
│ │ │ │ (Acquire) │ Spins if DIRTY_MASK set │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Binary/linear│──── upper_bound_internode() │ │ │
│ │ │ │ search ikeys │ Find child pointer for ikey │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Prefetch │──── prefetch_read(grandchild) │ │ │
│ │ │ │ grandchild │ Hides memory latency │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Version │──── has_changed(v)? │ │ │
│ │ │ │ changed? │ │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ┌────┴────┐ │ │ │
│ │ │ │ Yes │ No │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ RETRY Descend to child │ │ │
│ │ │ from └───────────────────────────► LOOP │ │ │
│ │ │ root │ │ │
│ │ │ │ │ │
│ │ └──────────────────────────────────────────────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ (reached leaf) │ │
│ │ ┌──────────────────────────────────────────────────────────────┐ │ │
│ │ │ LEAF SEARCH WITH OCC │ │ │
│ │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ v1 = stable()│──── Wait for clean version (Acquire) │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Check B-link │──── Is ikey >= ikey_bound()? │ │ │
│ │ │ │ boundary │ Key might be in next sibling │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ┌────┴────┐ │ │ │
│ │ │ │ Yes │ No │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ Follow ┌──────────────┐ │ │ │
│ │ │ B-link │ Linear search│──── Scan permutation for ikey │ │ │
│ │ │ to next │ leaf slots │ O(WIDTH) with 4x unrolling │ │ │
│ │ │ sibling └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ┌────┴────┬──────────────┬─────────────┐ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ ▼ ▼ ▼ ▼ │ │ │
│ │ │ ┌────────┐ ┌────────┐ ┌──────────┐ ┌──────────┐ │ │ │
│ │ │ │ FOUND │ │ NOT │ │ LAYER │ │ VERSION │ │ │ │
│ │ │ │ value │ │ FOUND │ │ POINTER │ │ CHANGED │ │ │ │
│ │ │ └───┬────┘ └───┬────┘ └────┬─────┘ └────┬─────┘ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ ▼ ▼ ▼ ▼ │ │ │
│ │ │ ┌────────┐ ┌────────┐ ┌──────────┐ ┌──────────┐ │ │ │
│ │ │ │ Verify │ │ Return │ │key.shift()│ │ Follow │ │ │ │
│ │ │ │ !has_ │ │ None │ │layer += 1 │ │ B-link │ │ │ │
│ │ │ │changed │ │ │ │ CONTINUE │ │ or RETRY │ │ │ │
│ │ │ │ (v1) │ │ │ │ LAYER │ │ from root│ │ │ │
│ │ │ └───┬────┘ └────────┘ │ LOOP │ └──────────┘ │ │ │
│ │ │ │ └──────────┘ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌────────┐ │ │ │
│ │ │ │ Return │ │ │ │
│ │ │ │ &Value │──── Zero-copy reference into tree │ │ │
│ │ │ └────────┘ │ │ │
│ │ │ │ │ │
│ │ └──────────────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ └──────────────────────────────────────────────────────────────────────┘ │
│ │
│ COMPLEXITY: O(log n) with layer factor, O(WIDTH) per leaf │
│ MEMORY ORDERING: Acquire on version reads, compiler fence on validation │
│ RETRY POLICY: Bounded retries before falling back to from-root traversal │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§INSERT (Fine-Grained Locking)
┌──────────────────────────────────────────────────────────────────────────────┐
│ INSERT OPERATION - FINE-GRAINED LOCKING │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ insert_with_guard(key, value, guard) │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Alloc Arc<V> │──── S::output_to_raw(&value) - done ONCE │
│ │ or inline │ For Arc: heap allocation + refcount │
│ │ value_ptr │ For Inline: encode bits into pointer │
│ └──────┬───────┘ (Reused across all retries - no re-allocation) │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────────────┐ │
│ │ RETRY LOOP │ │
│ │ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Optimistic │──── Same traversal as GET (no locks) │ │
│ │ │ traversal │ reach_leaf_concurrent_generic() │ │
│ │ │ to leaf │ Prefetch, internode descent, B-link follow │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Lock leaf │──── version.lock() returns LockGuard │ │
│ │ │ │ CAS: set LOCK_BIT | INSERTING_BIT │ │
│ │ │ │ Spins on contention (backoff) │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Verify │──── check_membership(): │ │
│ │ │ membership │ 1. ikey >= ikey_bound? → follow B-link │ │
│ │ │ │ 2. prev != null && ikey < slot[0]? → retry │ │
│ │ │ │ 3. version changed during traversal? → retry │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ┌────┴────┐ │ │
│ │ │ Invalid │ Valid │ │
│ │ ▼ ▼ │ │
│ │ Unlock ┌──────────────┐ │ │
│ │ RETRY │ Search leaf │──── Linear scan for matching ikey │ │
│ │ LOOP │ for key │ Check suffix if keylenx indicates │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ┌────┴────────────────────────────┐ │ │
│ │ │ │ │ │
│ │ ▼ ▼ │ │
│ │ ┌──────────────────────┐ ┌──────────────────────┐ │ │
│ │ │ KEY EXISTS │ │ NEW KEY │ │ │
│ │ │ (UPDATE) │ │ (INSERT) │ │ │
│ │ ├──────────────────────┤ ├──────────────────────┤ │ │
│ │ │ │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Load old_ptr │ │ │ │ find_usable_ │ │ │ │
│ │ │ │ from slot │ │ │ │ slot() │ │ │ │
│ │ │ └──────┬───────┘ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ ▼ │ │ ┌────┴────┐ │ │ │
│ │ │ ┌──────────────┐ │ │ │ │ │ │ │
│ │ │ │ Store new_ptr│ │ │ ▼ ▼ │ │ │
│ │ │ │ (Release) │ │ │ ┌──────┐ ┌──────┐ │ │ │
│ │ │ └──────┬───────┘ │ │ │ HAS │ │ NO │ │ │ │
│ │ │ │ │ │ │ SLOT │ │ SLOT │ │ │ │
│ │ │ ▼ │ │ └──┬───┘ └──┬───┘ │ │ │
│ │ │ ┌──────────────┐ │ │ │ │ │ │ │
│ │ │ │ Retire old │ │ │ │ ▼ │ │ │
│ │ │ │ if NEEDS_ │ │ │ │ ┌────────┐ │ │ │
│ │ │ │ RETIREMENT │ │ │ │ │ SPLIT │ │ │ │
│ │ │ │ (Arc only) │ │ │ │ │ LEAF │ │ │ │
│ │ │ └──────┬───────┘ │ │ │ │(below) │ │ │ │
│ │ │ │ │ │ │ └────────┘ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ ▼ │ │ │
│ │ │ │ │ │ ┌──────────────────┐ │ │ │
│ │ │ │ │ │ │ SLOT-0 RULE: │ │ │ │
│ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ │ If slot==0 AND │ │ │ │
│ │ │ │ │ │ │ prev!=null AND │ │ │ │
│ │ │ │ │ │ │ ikey!=slot0_ikey │ │ │ │
│ │ │ │ │ │ │ → CANNOT use │ │ │ │
│ │ │ │ │ │ │ slot 0 │ │ │ │
│ │ │ │ │ │ │ (B-link bound) │ │ │ │
│ │ │ │ │ │ └────────┬─────────┘ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ │ │ │ ▼ │ │ │
│ │ │ │ │ │ ┌──────────────────┐ │ │ │
│ │ │ │ │ │ │ Install key: │ │ │ │
│ │ │ │ │ │ │ 1. ikeys[slot] │ │ │ │
│ │ │ │ │ │ │ 2. keylenx[slot] │ │ │ │
│ │ │ │ │ │ │ 3. suffix if >8B │ │ │ │
│ │ │ │ │ │ │ 4. values[slot] │ │ │ │
│ │ │ │ │ │ │ 5. CAS permuter │ │ │ │
│ │ │ │ │ │ │ (atomic pub) │ │ │ │
│ │ │ │ │ │ └────────┬─────────┘ │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ └─────────┼────────────┘ └──────────┼───────────┘ │ │
│ │ │ │ │ │
│ │ └─────────────┬────────────────────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ drop(guard) │──── Unlock via RAII │ │
│ │ │ │ Bumps VINSERT, clears dirty │ │
│ │ └──────┬───────┘ (Release ordering) │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Return │ │ │
│ │ │ Ok(old_value)│──── None for new, Some for update │ │
│ │ └──────────────┘ │ │
│ │ │ │
│ └──────────────────────────────────────────────────────────────────────┘ │
│ │
│ COMPLEXITY: O(log n) traversal + O(WIDTH) search + O(1) insert │
│ CONTENTION: Only leaf locked, other leaves/internodes unaffected │
│ MEMORY: Value allocated once, reused across retries │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§SPLIT (Hand-Over-Hand Propagation)
Leaf becomes full during insert
│
▼
┌──────────────────────────────────────────────────────────────────────────┐
│ PHASE 1: Create sibling │
│ │
│ ┌────────────┐ ┌────────────┐ │
│ │ Left Leaf │──── keys ───►│Right Leaf │ Allocate sibling │
│ │ (LOCKED) │ [mid..end] │ (NEW) │ Move upper half of keys │
│ └────────────┘ └────────────┘ │
│ │ │ │
│ │◄────────── B-link ────────┤ │
│ │ (installed) │ │
└─────────┼───────────────────────────┼────────────────────────────────────┘
│ │
▼ ▼
┌──────────────────────────────────────────────────────────────────────────┐
│ PHASE 2: Hand-over-hand parent locking │
│ │
│ ┌────────────┐ lock() ┌────────────┐ │
│ │ Left Leaf │─────────────►│ Parent │ │
│ │ (LOCKED) │ │ (LOCKED) │ │
│ └────────────┘ └─────┬──────┘ │
│ │ │ │
│ │ ┌───────────────────┴───────────────────┐ │
│ │ │ Install right sibling pointer │ │
│ │ │ in parent's children array │ │
│ │ └───────────────────────────────────────┘ │
│ │ │ │
│ unlock() Parent full? │
│ │ │
│ ┌──────────┴──────────┐ │
│ │ No │ Yes │
│ ▼ ▼ │
│ ┌────────────┐ ┌────────────────┐ │
│ │ unlock() │ │ Propagate up │ │
│ │ Done │ │ (split parent) │ │
│ └────────────┘ └────────────────┘ │
└──────────────────────────────────────────────────────────────────────────┘§REMOVE (Lazy Coalescing)
┌──────────────────────────────────────────────────────────────────────────────┐
│ REMOVE OPERATION - LAZY COALESCING │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ remove_with_guard(key, guard) │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────────────┐ │
│ │ RETRY LOOP │ │
│ │ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Optimistic │──── Same traversal as GET/INSERT │ │
│ │ │ traversal │ reach_leaf_concurrent_generic() │ │
│ │ │ to leaf │ May need to descend layers for long keys │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Lock leaf │──── version.lock() with INSERTING_BIT │ │
│ │ │ │ (Same lock as insert - mutual exclusion) │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Verify │──── check_membership() + search for key │ │
│ │ │ key exists │ Same B-link checks as insert │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ┌────┴────────────────────────────┐ │ │
│ │ │ │ │ │
│ │ ▼ ▼ │ │
│ │ ┌────────────────────┐ ┌────────────────────┐ │ │
│ │ │ KEY FOUND │ │ KEY NOT FOUND │ │ │
│ │ ├────────────────────┤ ├────────────────────┤ │ │
│ │ │ │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Get value_ptr│ │ │ │ Unlock leaf │ │ │ │
│ │ │ │ for return │ │ │ │ Return │ │ │ │
│ │ │ └──────┬───────┘ │ │ │ Ok(None) │ │ │ │
│ │ │ │ │ │ └──────────────┘ │ │ │
│ │ │ ▼ │ │ │ │ │
│ │ │ ┌──────────────┐ │ │ OR if layer_ptr: │ │ │
│ │ │ │ Update perm: │ │ │ Descend layer, │ │ │
│ │ │ │ │ │ │ retry in sublayer│ │ │
│ │ │ │ old_perm = │ │ │ │ │ │
│ │ │ │ perm.load() │ │ └────────────────────┘ │ │
│ │ │ │ │ │ │ │
│ │ │ │ new_perm = │ │ │ │
│ │ │ │ remove_at( │ │ │ │
│ │ │ │ position) │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ perm.CAS( │ │ │ │
│ │ │ │ old→new, │ │ │ │
│ │ │ │ Release) │ │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Retire value │ │ │ │
│ │ │ │ if NEEDS_ │──┼──── guard.defer_retire(value_ptr) │ │
│ │ │ │ RETIREMENT │ │ Value added to thread-local batch │ │
│ │ │ │ (Arc only) │ │ Reclaimed when all guards drop │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐ │ │ │
│ │ │ │ Leaf empty? │ │ │ │
│ │ │ │ (perm.size │ │ │ │
│ │ │ │ == 0) │ │ │ │
│ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ┌────┴────┐ │ │ │
│ │ │ │ Yes │ No │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ ┌────────┐ ┌────┐ │ │ │
│ │ │ │Schedule│ │Skip│ │ │ │
│ │ │ │coalesce│ │ │ │ │ │
│ │ │ └───┬────┘ └──┬─┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ ▼ │ │ │ │
│ │ │ ┌──────────┐ │ │ │ │
│ │ │ │coalesce_ │ │ │ │ │
│ │ │ │queue. │ │ │ │ │
│ │ │ │schedule( │ │ │ │ │
│ │ │ │ leaf_ptr,│ │ │ │ │
│ │ │ │ ikey, │ │ │ │ │
│ │ │ │ layer_ctx│ │ │ │ │
│ │ │ │) │ │ │ │ │
│ │ │ └────┬─────┘ │ │ │ │
│ │ │ │ │ │ │ │
│ │ │ └────┬───┘ │ │ │
│ │ │ │ │ │ │
│ │ │ ▼ │ │ │
│ │ │ ┌──────────────┐│ │ │
│ │ │ │ Unlock leaf ││ │ │
│ │ │ │ Return ││ │ │
│ │ │ │ Ok(Some(val))││ │ │
│ │ │ └──────────────┘│ │ │
│ │ │ │ │ │
│ │ └────────────────────┘ │ │
│ │ │ │
│ └──────────────────────────────────────────────────────────────────────┘ │
│ │
│ WHY LAZY COALESCING: │
│ ├─ Inline removal would require locking parent → deadlock risk │
│ ├─ Empty leaves can be reused by concurrent inserts │
│ ├─ Readers already handle deleted nodes via B-link retry │
│ └─ Cleanup batched for efficiency (process_coalesce_queue) │
│ │
└──────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────┐
│ COALESCE (Background Cleanup) │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ process_coalesce_queue() / tree.flush(&guard) │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Pop entry │──── CoalesceEntry { leaf_ptr, ikey_bound, layer_ctx } │
│ │ from queue │ │
│ └──────┬───────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ Empty │ Entry found │
│ ▼ ▼ │
│ DONE ┌──────────────┐ │
│ │ Lock leaf │ │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Still empty? │──── Concurrent insert may have reused it │
│ └──────┬───────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ No │ Yes │
│ ▼ ▼ │
│ Unlock ┌──────────────┐ │
│ Skip │ Check if │ │
│ │ sublayer root│ │
│ └──────┬───────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ Yes │ No (regular leaf) │
│ ▼ ▼ │
│ gc_layer() ┌──────────────┐ │
│ (special │ mark_deleted │──── Set DELETED_BIT │
│ cleanup) └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Unlink from │ │
│ │ B-link chain:│ │
│ │ │ │
│ │ prev.next = │ │
│ │ self.next │ │
│ │ │ │
│ │ next.prev = │ │
│ │ self.prev │ │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Remove from │──── NodeCleaner:: │
│ │ parent │ remove_leaf_from_ │
│ │ internode │ parent_for_coalesce() │
│ └──────┬───────┘ │
│ │ │
│ ▼ │
│ ┌──────────────┐ │
│ │ Retire leaf │──── guard.defer_retire() │
│ │ node via │ Safe: unreachable from │
│ │ seize │ tree after unlinking │
│ └──────────────┘ │
│ │
│ SAFETY: Leaf retirement is safe because: │
│ 1. Marked deleted → readers see DELETED_BIT, follow B-link │
│ 2. Unlinked from B-link chain → not reachable via sibling traversal │
│ 3. Removed from parent → not reachable via tree traversal │
│ 4. Epoch guard protects existing references until safe to free │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§RANGE SCAN (Iterator)
┌──────────────────────────────────────────────────────────────────────────────┐
│ RANGE SCAN - ZERO-COPY ITERATOR │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ scan_ref(start_bound, end_bound, callback, guard) │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────────────┐ │
│ │ INITIALIZATION │ │
│ │ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Find first │──── find_leaf_for_scan(start_bound) │ │
│ │ │ leaf │ Optimistic traversal to leftmost matching leaf │ │
│ │ │ │ Uses B-link if key > ikey_bound │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ │ ▼ │ │
│ │ ┌──────────────┐ │ │
│ │ │ Init state: │ │ │
│ │ │ │ │ │
│ │ │ • leaf_ptr │──── Current leaf being scanned │ │
│ │ │ • ki │──── Current slot index in permutation │ │
│ │ │ • perm │──── Cached permutation snapshot │ │
│ │ │ • version │──── Version at snapshot time │ │
│ │ │ • end_bound │──── Stop condition │ │
│ │ │ • layer_stack│──── For multi-layer key descent │ │
│ │ └──────┬───────┘ │ │
│ │ │ │ │
│ └─────────┼────────────────────────────────────────────────────────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────────────────────────────────────────────────────────┐ │
│ │ STATE MACHINE LOOP │ │
│ │ │ │
│ │ ┌─────────────────────────────────────────────────────────────┐ │ │
│ │ │ │ │ │
│ │ ▼ │ │ │
│ │ ┌─────────────┐ │ │ │
│ │ │ FIND_NEXT │◄────────────────────────────────────────────────┤ │ │
│ │ │ │ │ │ │
│ │ │ ki < size? │ │ │ │
│ │ └──────┬──────┘ │ │ │
│ │ │ │ │ │
│ │ YES │ NO │ │ │
│ │ ┌─────┴─────┐ │ │ │
│ │ │ │ │ │ │
│ │ ▼ ▼ │ │ │
│ │ ┌───────────────────┐ ┌───────────────────────────────────┐ │ │ │
│ │ │ READ SLOT │ │ EXHAUSTED │ │ │ │
│ │ │ perm[ki] → slot │ │ (ki >= size) │ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ ┌───────────────┐ │ │ ┌─────────────────────────────┐ │ │ │ │
│ │ │ │Version check: │ │ │ │ At top layer (stack empty)? │ │ │ │ │
│ │ │ │changed since │ │ │ └─────────────┬───────────────┘ │ │ │ │
│ │ │ │snapshot? │ │ │ YES │ NO │ │ │ │
│ │ │ └───────┬───────┘ │ │ ┌────────┴────────┐ │ │ │ │
│ │ │ YES │ NO │ │ │ │ │ │ │ │
│ │ │ ┌─────┴─────┐ │ │ ▼ ▼ │ │ │ │
│ │ │ │ │ │ │ ┌─────────┐ ┌───────────┐ │ │ │ │
│ │ │ ▼ ▼ │ │ │ Follow │ │ Pop layer │ │ │ │ │
│ │ │ ┌─────┐ ┌──────┐ │ │ │ B-link │ │ stack, │ │ │ │ │
│ │ │ │RETRY│ │ Check│ │ │ │ to next │ │ continue │ │ │ │ │
│ │ │ │ │ │ slot │ │ │ │ leaf │ │ parent │────┼───┤ │ │
│ │ │ │Re- │ │ type │ │ │ │ │ │ scan │ │ │ │ │
│ │ │ │read │ └──┬───┘ │ │ │ null? │ └───────────┘ │ │ │ │
│ │ │ │perm,│ │ │ │ │ → DONE │ │ │ │ │
│ │ │ │re- │ │ │ │ └─────────┘ │ │ │ │
│ │ │ │find │ │ │ │ │ │ │ │
│ │ │ │leaf │ │ │ └───────────────────────────────────┘ │ │ │
│ │ │ │if │ │ │ │ │ │
│ │ │ │split│ │ │ │ │ │
│ │ │ └──┬──┘ │ │ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │ ┌────┴─────────────────────┐ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │ ▼ ▼ │ │ │
│ │ │ │ ┌──────────────┐ ┌──────────────┐ │ │ │
│ │ │ │ │ VALUE SLOT │ │ LAYER PTR │ │ │ │
│ │ │ │ │ │ │ │ │ │ │
│ │ │ │ │ Has key+val │ │ Points to │ │ │ │
│ │ │ │ │ → go to EMIT │ │ sublayer │ │ │ │
│ │ │ │ └──────┬───────┘ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │ │ ▼ │ │ │
│ │ │ │ │ ┌──────────────┐ │ │ │
│ │ │ │ │ │ DOWN: │ │ │ │
│ │ │ │ │ │ Push context │ │ │ │
│ │ │ │ │ │ (leaf, ki+1) │ │ │ │
│ │ │ │ │ │ to stack, │ │ │ │
│ │ │ │ │ │ descend to │ │ │ │
│ │ │ │ │ │ sublayer │────────────────────┤ │ │
│ │ │ │ │ │ root │ │ │ │
│ │ │ │ │ └──────────────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ └────┼────────┼──────────────────────────────────────────────────┘ │ │
│ │ │ │ │ │
│ │ │ ▼ │ │
│ │ │ ┌────────────────────────────────────────────────────────┐ │ │
│ │ │ │ EMIT │ │ │
│ │ │ │ │ │ │
│ │ │ │ ┌──────────────┐ │ │ │
│ │ │ │ │ Build key │──── Reconstruct full key: │ │ │
│ │ │ │ │ from slot │ layer prefixes + ikey + suffix │ │ │
│ │ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ ▼ │ │ │
│ │ │ │ ┌──────────────┐ │ │ │
│ │ │ │ │ Check end_ │ │ │ │
│ │ │ │ │ bound: key │ │ │ │
│ │ │ │ │ > end? │ │ │ │
│ │ │ │ │ → DONE │ │ │ │
│ │ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ ▼ │ │ │
│ │ │ │ ┌──────────────┐ │ │ │
│ │ │ │ │ Load value │──── Zero-copy: return &V reference │ │ │
│ │ │ │ │ reference │ Arc: deref into Arc<V> │ │ │
│ │ │ │ │ │ Inline: decode from pointer bits │ │ │
│ │ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ ▼ │ │ │
│ │ │ │ ┌──────────────┐ │ │ │
│ │ │ │ │ callback( │ │ │ │
│ │ │ │ │ key, &value │ │ │ │
│ │ │ │ │ ) │ │ │ │
│ │ │ │ └──────┬───────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ ┌────┴────┐ │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │ true false │ │ │
│ │ │ │ │ │ │ │ │
│ │ │ │ ▼ ▼ │ │ │
│ │ │ │ ki += 1 DONE (early termination) │ │ │
│ │ │ │ │ │ │ │
│ │ │ │ └───────────────────────────────────────────────────┼───┘ │
│ │ │ │ │ │
│ │ │ └────────────────────────────────────────────────────────┘ │
│ │ │ │
│ │ └───────────────────────────────────────────────────────────────────┘
│ │ │
│ └──────────────────────────────────────────────────────────────────────────┘
│ │
│ GUARANTEES: │
│ ├─ Keys emitted in lexicographic order │
│ ├─ Each key emitted at most once (snapshot consistency) │
│ ├─ Concurrent inserts: may or may not be seen (depends on timing) │
│ ├─ Zero-copy: values are references, no cloning │
│ └─ Handles splits/deletes via version validation + B-link retry │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§Concurrency Model
┌──────────────────────────────────────────────────────────────────────────────┐
│ OPTIMISTIC CONCURRENCY CONTROL (OCC) │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────┐ ┌─────────────────────────────┐ │
│ │ READER (Lock-Free) │ │ WRITER (Fine-Grained) │ │
│ ├─────────────────────────────┤ ├─────────────────────────────┤ │
│ │ │ │ │ │
│ │ ┌───────────────────────┐ │ │ ┌───────────────────────┐ │ │
│ │ │ v1 = stable() │ │ │ │ guard = lock() │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ • Spin while dirty │ │ │ │ • CAS: 0 → LOCK|INS │ │ │
│ │ │ • Return clean version│ │ │ │ • Spin on failure │ │ │
│ │ │ • Acquire ordering │ │ │ │ • Acquire ordering │ │ │
│ │ └───────────┬───────────┘ │ │ └───────────┬───────────┘ │ │
│ │ │ │ │ │ │ │
│ │ ▼ │ │ ▼ │ │
│ │ ┌───────────────────────┐ │ │ ┌───────────────────────┐ │ │
│ │ │ Read node data │ │ │ │ Modify node data │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ • ikeys[slot] │ │ │ │ • ikeys[slot] = new │ │ │
│ │ │ • keylenx[slot] │ │ │ │ • values[slot] = ptr │ │ │
│ │ │ • values[slot] │ │ │ │ • permutation CAS │ │ │
│ │ │ • permutation │ │ │ │ • suffix bag update │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ NO LOCKS HELD │ │ │ │ EXCLUSIVE ACCESS │ │ │
│ │ └───────────┬───────────┘ │ │ └───────────┬───────────┘ │ │
│ │ │ │ │ │ │ │
│ │ ▼ │ │ ▼ │ │
│ │ ┌───────────────────────┐ │ │ ┌───────────────────────┐ │ │
│ │ │ has_changed(v1)? │ │ │ │ drop(guard) │ │ │
│ │ │ │ │ │ │ │ │ │
│ │ │ • Compiler fence │ │ │ │ • Bump VINSERT/VSPLIT │ │ │
│ │ │ • (v1 ^ cur) >= 512? │ │ │ │ • Clear LOCK|INS|SPLIT│ │ │
│ │ │ │ │ │ │ • Release ordering │ │ │
│ │ │ Yes → RETRY │ │ │ │ │ │ │
│ │ │ No → SUCCESS │ │ │ │ PANIC-SAFE (RAII) │ │ │
│ │ └───────────────────────┘ │ │ └───────────────────────┘ │ │
│ │ │ │ │ │
│ └─────────────────────────────┘ └─────────────────────────────┘ │
│ │
│ RACE SCENARIOS AND RESOLUTION: │
│ │
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ Scenario 1: Reader overlaps with writer │ │
│ │ │ │
│ │ Reader Writer │ │
│ │ ────── ────── │ │
│ │ v1 = stable() │ │
│ │ read ikey[3] lock() │ │
│ │ modify ikey[3] │ │
│ │ read value[3] unlock() ← version bumped │ │
│ │ has_changed(v1)? → YES → RETRY with fresh data │ │
│ │ │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ Scenario 2: Reader during split │ │
│ │ │ │
│ │ Reader Writer (splitting) │ │
│ │ ────── ───────────────── │ │
│ │ v1 = stable() │ │
│ │ mark_split() ← SPLITTING_BIT set │ │
│ │ search for key move keys to sibling │ │
│ │ key not found install B-link │ │
│ │ has_changed(v1)? → YES (VSPLIT bumped) │ │
│ │ → Follow B-link to find key in sibling │ │
│ │ │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
└──────────────────────────────────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────────────────────────────────┐
│ B-LINK HELP-ALONG PROTOCOL │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ When a split occurs, the B-link chain allows readers to find keys that │
│ have moved to a sibling, even before the parent is updated. │
│ │
│ BEFORE SPLIT: │
│ │
│ ┌────────────────────────────────────────────┐ │
│ │ Leaf A │ │
│ │ ikey_bound = MAX │ │
│ │ keys: [k1, k2, k3, k4, k5, k6, k7, k8] │ │
│ │ next → null │ │
│ └────────────────────────────────────────────┘ │
│ │
│ DURING/AFTER SPLIT: │
│ │
│ ┌───────────────────────┐ ┌───────────────────────┐ │
│ │ Leaf A │ │ Leaf B │ │
│ │ ikey_bound = k4 │ │ ikey_bound = MAX │ │
│ │ keys: [k1, k2, k3, k4]│────►│ keys: [k5, k6, k7, k8]│ │
│ │ next ────────────────────► │ prev → A │ │
│ └───────────────────────┘ └───────────────────────┘ │
│ │
│ READER LOOKING FOR k6: │
│ │
│ 1. Parent routes to Leaf A (old routing) │
│ 2. Reader arrives at Leaf A │
│ 3. v1 = stable() on Leaf A │
│ 4. Search for k6 in Leaf A → NOT FOUND │
│ 5. Check: k6 >= ikey_bound(k4)? → YES │
│ 6. Follow B-link: A.next → Leaf B │
│ 7. v2 = stable() on Leaf B │
│ 8. Search for k6 in Leaf B → FOUND │
│ 9. Validate !has_changed(v2) → SUCCESS │
│ │
│ KEY INSIGHT: Readers never block, they "help along" by following B-links. │
│ The tree is always consistent enough for readers to find their keys. │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§Memory Reclamation
┌──────────────────────────────────────────────────────────────────────────────┐
│ SEIZE EPOCH-BASED RECLAMATION │
├──────────────────────────────────────────────────────────────────────────────┤
│ │
│ Seize uses a hyaline-style epoch-based scheme with thread-local batching. │
│ │
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ EPOCH TIMELINE │ │
│ │ │ │
│ │ Time ──────────────────────────────────────────────────────────────► │ │
│ │ │ │
│ │ Thread 1: │ │
│ │ ┌────────────────────────────────────────────────────┐ │ │
│ │ │ guard = enter() drop(guard) │ │ │
│ │ │ │ │ │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ ┌───────┐ remove(k) ┌──────────────┐ │ │ │
│ │ │ │Epoch 5│──────────►│defer_retire()│ │ │ │
│ │ │ └───────┘ │ └──────────────┘ │ │ │
│ │ │ │ │ │ │ │
│ │ │ ▼ ▼ │ │ │
│ │ │ ┌──────────────────────────┐ │ │ │
│ │ │ │ Thread-local batch: │ │ │ │
│ │ │ │ [ptr1, ptr2, ptr3, ...] │ │ │ │
│ │ │ └──────────────────────────┘ │ │ │
│ │ │ │ │ │
│ │ └────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ │ Thread 2: │ │
│ │ ┌────────────────────────────────────────────────────┐ │ │
│ │ │ guard = enter() drop(guard) │ │ │
│ │ │ │ │ │ │ │
│ │ │ ▼ get(k) ▼ │ │ │
│ │ │ ┌───────┐ (may see old ┌───────────────┐ │ │ │
│ │ │ │Epoch 5│ value - SAFE) │Thread 2 exits │ │ │ │
│ │ │ └───────┘ │epoch 5 │ │ │ │
│ │ │ └───────────────┘ │ │ │
│ │ └────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ │ ─────────────────────────────────────────────────────────────────── │ │
│ │ │ │
│ │ Reclamation (when batch_size reached or all threads exit epoch): │ │
│ │ │ │
│ │ ┌────────────────────────────────────────────────────────────────┐ │ │
│ │ │ 1. Check: All threads left epoch 5? │ │ │
│ │ │ └─ YES: No thread can hold references from epoch 5 │ │ │
│ │ │ │ │ │
│ │ │ 2. For each ptr in epoch 5's retire list: │ │ │
│ │ │ └─ free(ptr) ← Safe to deallocate │ │ │
│ │ │ │ │ │
│ │ │ 3. Advance global epoch │ │ │
│ │ └────────────────────────────────────────────────────────────────┘ │ │
│ │ │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ SEIZE INTERNALS: │
│ │
│ ┌────────────────────────────────────────────────────────────────────────┐ │
│ │ │ │
│ │ Collector::batch_size = max(CPU_COUNT, 32) │ │
│ │ └─ Configurable via MassTree::with_allocator_batch_size() │ │
│ │ │ │
│ │ defer_retire(ptr): │ │
│ │ ├─ Add ptr to thread-local Vec │ │
│ │ ├─ If Vec.len() >= batch_size: │ │
│ │ │ └─ Trigger epoch advancement + reclamation │ │
│ │ └─ Cost: ~100-500ns (Vec append) │ │
│ │ │ │
│ │ Batch trigger (heavy operation): │ │
│ │ ├─ sys_membarrier() syscall (Linux) - expensive! │ │
│ │ ├─ Check all thread epochs │ │
│ │ ├─ Reclaim safe batches │ │
│ │ └─ Cost: ~1-5µs │ │
│ │ │ │
│ │ Guard reuse (critical for performance): │ │
│ │ ├─ guard.enter() → ~µs (first enter) │ │
│ │ ├─ Nested guards → FREE (counter increment) │ │
│ │ └─ ALWAYS reuse guards across operations! │ │
│ │ │ │
│ └────────────────────────────────────────────────────────────────────────┘ │
│ │
│ INLINE STORAGE OPTIMIZATION: │
│ │
│ MassTree15Inline<V: Copy> eliminates most retirement: │
│ ├─ Values stored inline (no Arc) │
│ ├─ Updates overwrite in-place (no old value to retire) │
│ ├─ Only node retirements remain (splits, coalesces) │
│ └─ Result: 77-179% faster on update-heavy workloads │
│ │
└──────────────────────────────────────────────────────────────────────────────┘§Module Organization
src/
├── lib.rs ← You are here (entry point, re-exports)
│
├── tree.rs ← Core tree: MassTreeGeneric struct
│ └── tree/ ← Tree implementation modules
│ ├── generic.rs ← Main impl block, guard, flush
│ │ ├── search.rs ← Key search within nodes
│ │ ├── insert.rs ← Insert path with slot allocation
│ │ ├── optimistic_reads.rs ← Lock-free get operations
│ │ ├── batch.rs ← Batch insert API
│ │ ├── layer.rs ← Multi-layer (sublayer) handling
│ │ └── split.rs ← Per-slot split helpers
│ ├── remove.rs ← Deletion with permutation update
│ ├── split.rs ← Hand-over-hand split propagation
│ │ ├── propagation.rs ← Core split loop
│ │ ├── propagation_context.rs ← RAII lock management
│ │ ├── parent_locking.rs ← Membership validation
│ │ └── root_creation.rs ← New root/layer-root
│ ├── coalesce.rs ← Lazy empty leaf cleanup
│ └── range.rs ← Range iteration module
│ └── range/
│ ├── api.rs ← scan, scan_ref, scan_prefix
│ ├── iterator.rs ← RangeIter implementation
│ ├── scan_state.rs ← State machine for scanning
│ ├── cursor_key.rs ← Key reconstruction
│ ├── helper.rs ← Scan utilities
│ └── find.rs ← Find first/last leaf in range
│
├── leaf15.rs ← WIDTH=15 leaf node
├── leaf24.rs ← WIDTH=24 leaf node
├── leaf_trait.rs ← LayerCapableLeaf trait
├── internode.rs ← Internal routing node
├── nodeversion.rs ← OCC primitive (lock + version)
│
├── slot.rs ← ValueSlot trait (Arc vs Inline)
├── value.rs ← LeafValue, LeafValueIndex
├── suffix.rs ← SuffixBag for keys > 8 bytes
├── permuter.rs ← WIDTH=15 permutation (u64)
├── permuter24.rs ← WIDTH=24 permutation (u128)
│
├── alloc15.rs ← SeizeAllocator15
├── alloc24.rs ← SeizeAllocator24
├── alloc_trait.rs ← NodeAllocatorGeneric trait
├── retirement.rs ← BatchedRetire, FlushOnDrop
│
├── key.rs ← Key<'a> with layer traversal
├── ksearch.rs ← Binary/linear search helpers
├── link.rs ← B-link chain utilities
├── prefetch.rs ← CPU prefetch hints
└── ordering.rs ← Memory ordering constants§Value Storage
MassTree<V>: Stores values asArc<V>. ReturnsArc<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 tologs/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
LeafNode15with WIDTH=15 leaves and WIDTH=15 internodes. - alloc24
- Node allocation for
LeafNode24(WIDTH=24). - alloc_
trait - Generic allocator trait for tree nodes.
- 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.
- 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::MassTreestorage 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§
- Alloc
Error - Error returned when memory allocation fails.
- Batched
Retire - Batched retirement utilities.
- Flush
OnDrop - Guard that flushes the retirement batch on drop.
Enums§
- Alloc
Kind - Kind of allocation that failed.
Functions§
- init_
tracing - No-op when tracing feature is disabled.
Type Aliases§
- Alloc
Result - Result type alias for fallible allocations.