btree_store

btree_store is a high-performance, persistent, embedded key-value storage engine written in Rust. It implements a robust Copy-On-Write (COW) B-Tree architecture to ensure data integrity, crash safety, and efficient concurrent access.

Features

ACID Compliance: Atomic commits using COW and double-buffered meta pages.
Crash Safety: A dedicated .pending log recovery mechanism reclaims leaked pages from interrupted transactions.
Buckets: Logical namespaces for data separation within a single database file.
Zero-Allocation Iterators: High-performance iterators returning (&[u8], &[u8]) with internal buffer reuse to minimize GC pressure and memory overhead.
Efficient Concurrency: Granular locking using parking_lot and sharded node caching.
Data Integrity: Full CRC32C checksum validation for every page (nodes, meta, and free lists).
Zero External Dependencies: Core engine built using native Rust standard library for a lightweight footprint.

Architecture

Store (src/store.rs): Low-level page management, sharded LRU caching, and positional I/O.
Node (src/node.rs): B-Tree node serialization, splitting, compacting, and checksumming.
Tree (src/lib.rs): Core B+ Tree algorithms including COW insertion, deletion with root collapse optimization, and search.
Bucket (src/lib.rs): High-level API for user-facing key-value operations.

Usage

Add this to your Cargo.toml:

[dependencies]
btree-store = "0.1.0"

Basic Example

use btree_store::BTree;

fn main() -> Result<(), btree_store::Error> {
    // Open or create the database
    let db = BTree::open("data.db")?;

    // Create or retrieve a bucket
    let bucket = db.new_bucket("users")?;

    // Insert data
    bucket.put(b"id:100", b"Alice")?;
    
    // Retrieve data
    if let Some(val) = bucket.get(b"id:100").ok() {
        println!("Found user: {:?}", String::from_utf8_lossy(&val));
    }

    // Commit changes to disk
    db.commit()?;

    // Iterate efficiently
    let mut iter = bucket.iter()?;
    while let Some((k, v)) = iter.next() {
        println!("Key: {:?}, Value: {:?}", k, v);
    }

    Ok(())
}

Performance Design

The engine is optimized for high-throughput scenarios:

Cursor-based path traversal avoids redundant tree searches.
RAII CommitContext ensures zero-leak automatic rollbacks on failure.
Transmute-based lifetime extension in iterators allows returning direct references to internal buffers under a read lock, achieving C-like performance in Rust.

Testing

The project includes a comprehensive suite of integration tests:

smo_stress_test: Structural Modification Operations under heavy load.
crash_safety_tests: Verifies data integrity across simulated crashes.
concurrency_tests: Parallel readers and writers.
leak_safety_tests: Ensures no pages are lost during failed operations.

Run tests with:

cargo test

License

This project is licensed under the MIT License - see the LICENSE file for details.

btree-store 0.1.0