Crate ferntree 

Ferntree: A Concurrent In-Memory B+ Tree

This crate provides a fast, concurrent B+ tree implementation featuring optimistic lock coupling, a technique that enables high-throughput concurrent access with minimal blocking.

Design overview

The implementation is based on research from:

• LeanStore - Optimistic lock coupling for B-trees
• Umbra - High-performance database engine techniques

Key concepts

Optimistic Lock Coupling: Instead of holding locks while traversing the tree, readers acquire “optimistic” access (no locks) and validate at the end that no concurrent modifications occurred. If validation fails, the operation retries. This allows readers to proceed without blocking writers, and vice versa.

Hybrid Latches: Each node is protected by a latch::HybridLatch that supports three access modes:

• Optimistic: Version-based read access with no blocking. Must be validated before trusting any read data.
• Shared: Traditional blocking read lock for guaranteed consistent reads.
• Exclusive: Blocking write lock for modifications.

Fence Keys: Each node stores lower_fence and upper_fence keys that define the key range the node is responsible for. These enable efficient range checks and help detect when a node has been split or merged during optimistic traversal.

Sample Keys: Each node stores a sample_key that can be used to relocate the node in the tree after an optimistic validation failure. This avoids restarting from the root.

Tree structure

                   ┌─────────────────┐
                   │   Root Latch    │  <- Protects the root pointer
                   │  (HybridLatch)  │
                   └────────┬────────┘
                            │
                            ▼
                   ┌─────────────────┐
                   │  Internal Node  │  <- Contains keys and child pointers
                   │   keys: [K]     │
                   │   edges: [ptr]  │
                   │   upper_edge    │
                   └────────┬────────┘
                            │
             ┌──────────────┼──────────────┐
             ▼              ▼              ▼
       ┌──────────┐  ┌──────────┐  ┌──────────┐
       │   Leaf   │  │   Leaf   │  │   Leaf   │  <- Store actual key-value pairs
       │ keys:[K] │  │ keys:[K] │  │ keys:[K] │
       │ vals:[V] │  │ vals:[V] │  │ vals:[V] │
       └──────────┘  └──────────┘  └──────────┘

Basic usage

use ferntree::Tree;

let tree = Tree::new();

// Insert key-value pairs
tree.insert("key1", "value1");
tree.insert("key2", "value2");

// Lookup values (requires a closure due to optimistic access)
let value = tree.lookup(&"key1", |v| v.to_string());
assert_eq!(value, Some("value1".to_string()));

// Remove entries
tree.remove(&"key1");

Concurrent usage

The tree is designed for high-concurrency workloads. Wrap it in an Arc to share across threads:

Multi-threaded inserts

use ferntree::Tree;
use std::sync::Arc;
use std::thread;

let tree = Arc::new(Tree::<i32, i32>::new());

// Spawn multiple writer threads
let handles: Vec<_> = (0..4).map(|t| {
    let tree = Arc::clone(&tree);
    thread::spawn(move || {
        for i in 0..1000 {
            tree.insert(t * 1000 + i, i);
        }
    })
}).collect();

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

assert_eq!(tree.len(), 4000);

Concurrent readers and writers

use ferntree::Tree;
use std::sync::Arc;
use std::thread;

let tree = Arc::new(Tree::<i32, i32>::new());

// Pre-populate some data
for i in 0..100 {
    tree.insert(i, i * 10);
}

let tree_writer = Arc::clone(&tree);
let tree_reader = Arc::clone(&tree);

// Writer thread adds new entries
let writer = thread::spawn(move || {
    for i in 100..200 {
        tree_writer.insert(i, i * 10);
    }
});

// Reader thread performs lookups concurrently
let reader = thread::spawn(move || {
    let mut found = 0;
    for i in 0..100 {
        if tree_reader.lookup(&i, |v| *v).is_some() {
            found += 1;
        }
    }
    found
});

writer.join().unwrap();
let found = reader.join().unwrap();
assert_eq!(found, 100); // Reader sees consistent data

Iterator usage

use ferntree::Tree;
use std::sync::Arc;
use std::thread;

let tree = Arc::new(Tree::<i32, i32>::new());

for i in 0..100 {
    tree.insert(i, i);
}

// Iterators acquire locks on leaf nodes, ensuring consistent reads
let tree_iter = Arc::clone(&tree);
let handle = thread::spawn(move || {
    let mut iter = tree_iter.raw_iter();
    iter.seek_to_first();

    let mut count = 0;
    while iter.next().is_some() {
        count += 1;
    }
    count
});

// Concurrent modifications are safe
tree.insert(100, 100);

let count = handle.join().unwrap();
// Iterator sees a consistent snapshot
assert!(count >= 100);

Thread safety

Send and Sync bounds

Tree<K, V> implements Send and Sync when both K and V implement Send + Sync. This means the tree can be safely shared across threads and accessed concurrently.

use ferntree::Tree;

fn assert_send_sync<T: Send + Sync>() {}

// Tree is Send + Sync for thread-safe key/value types
assert_send_sync::<Tree<String, i32>>();
assert_send_sync::<Tree<i32, Vec<u8>>>();

Operation atomicity

Individual operations (insert, remove, lookup) are atomic at the key level:

• Atomic reads: lookup() always returns a consistent value for a key
• Atomic writes: insert() and remove() complete atomically
• No cross-key transactions: Multiple operations are NOT transactional; if you need to update multiple keys atomically, you must use external synchronization

Retry semantics

The tree uses optimistic concurrency control internally:

• Operations may retry automatically if concurrent modifications are detected
• Users don’t need to handle retries - this is managed internally
• Important: Closures passed to lookup() may be called multiple times if retries occur. Avoid side effects in lookup closures:

use ferntree::Tree;

let tree = Tree::<i32, i32>::new();
tree.insert(1, 42);

// Good: Pure closure that just extracts data
let value = tree.lookup(&1, |v| *v);

// Avoid: Side effects in lookup closure (may execute multiple times)
// let mut counter = 0;
// tree.lookup(&1, |v| { counter += 1; *v }); // counter may be > 1

Memory safety

The tree uses epoch-based memory reclamation via crossbeam_epoch to ensure safe concurrent access:

• Safe concurrent reads: Readers never see freed memory, even during concurrent modifications
• Deferred deallocation: Nodes removed from the tree are not immediately freed; they remain valid until all concurrent readers have finished
• No use-after-free: The epoch system guarantees that memory is only reclaimed when it’s safe to do so

This means you can safely perform concurrent reads and writes without worrying about memory safety - the tree handles all synchronization internally.

Re-exports

pub use optimistic::OptimisticRead;

Modules

alloc

Allocation tracking for memory leak detection.

atomic_slot

Per-type atomic storage for optimistic-read fields

error

Error Types for the Concurrent B+ Tree

iter

Iterator Module for the Concurrent B+ Tree

latch

Hybrid Latch Implementation

optimistic

Optimistic value reads

Macros

impl_optimistic_read_boxed

Implement OptimisticRead for a non-Copy type via BoxedSlot indirection.

Structs

GenericTree

A concurrent B+ tree with configurable node capacities.

Type Aliases

Tree

A B+ tree with default node capacities (64 keys per internal node, 64 entries per leaf).