bplus_store

Status: beta — core APIs are stable; internal storage traits may still change. License: MIT OR Apache-2.0

Embedded, copy-on-write B+-tree key-value store in Rust. Synchronous, zero-network. Multi-writer with optimistic commits (CAS). Snapshot readers via epoch-based reclamation.

Why

An embedded key-value store in the same design space as LMDB, BoltDB, and redb — crash-safe COW B+ trees with snapshot isolation. Where it differs:

• Multi-writer OCC: LMDB and BoltDB serialise all writes behind a single writer lock. bplus_store lets multiple writers proceed in parallel and resolves conflicts at commit time via CAS on a 128-bit metadata word. Under low-to-moderate contention this gives near-linear write throughput scaling.
• No WAL: crash safety comes from COW page immutability + A/B metadata slot alternation with CRC validation. No write-ahead log to tune, compact, or replay.
• Bounded page cache: PagedNodeStorage keeps decoded NodeViews in a bounded CLOCK-Pro cache (via quick_cache). Pages are immutable while live (COW guarantee), so cached entries never go stale. The cache is bounded to a configurable number of pages (default 16,384 ≈ 64 MB), and CLOCK-Pro provides scan resistance — range scans over cold leaves won't evict hot root/internal nodes.
• Epoch-based snapshot readers: readers pin an epoch and walk a consistent snapshot without holding any locks. Writers retire old pages; a reclaimer frees them only after all pinned readers have advanced.
• Layered storage traits: PageStorage (raw page I/O) and NodeStorage (encoded node I/O) are separate traits, making the node encoding strategy pluggable without touching the page layer.

Features

• Copy-on-write page mutation via NodeView over [u8; 4096] pages
• Multiple concurrent writers (optimistic concurrency; CAS on metadata)
• Batched write transactions (stage → commit → reclaim)
• Bounded page cache (CLOCK-Pro) with COW-coherent eviction via epoch GC
• Cursor-based range iteration (parent-stack traversal, no sibling pointers)
• Physical fullness handling: large values trigger page splits before reaching max keys
• Pluggable node encoding via NodeStorage trait; raw page I/O via PageStorage trait
• Multi-tree support: one database directory, many named trees (create, rename, drop, list)
• Manifest-based crash recovery with CRC-framed catalog log
• Superblock and metadata page CRC validation
• Exclusive file locking to prevent multi-process corruption
• Built-in order-preserving codecs for u64, i64, String, Vec<u8>
• Typed Tree<K, V> API with KeyCodec / ValueCodec traits
• Thread-safe handles via Arc-based storage ownership (no unsafe in the public API)

Quick start

[dependencies]
bplus_store = "0.7.1"

Build & test

cargo build
cargo test --tests
cargo run --example bytes_api
cargo run --example typed_api
cargo bench

Bytes-level API

use bplus_store::api::Db;

let dir = tempfile::tempdir()?;
let db = Db::open(dir.path())?;
let tree = db.create_tree::<Vec<u8>, Vec<u8>>("data", 64)?;

tree.put(&b"alpha".to_vec(), &b"1".to_vec())?;
tree.put(&b"beta".to_vec(), &b"2".to_vec())?;

let val = tree.get(&b"alpha".to_vec())?;
assert_eq!(val.as_deref(), Some(&b"1"[..]));

tree.delete(&b"alpha".to_vec())?;

Typed API

use bplus_store::api::Db;

let dir = tempfile::tempdir()?;
let db = Db::open(dir.path())?;
let tree = db.create_tree::<u64, String>("users", 64)?;

tree.put(&42, &"answer".to_string())?;
assert_eq!(tree.get(&42)?.as_deref(), Some("answer"));

Batched write transaction

let tree = db.create_tree::<u64, String>("events", 64)?;

let mut txn = tree.txn();
txn.insert(&1, &"first".to_string());
txn.insert(&2, &"second".to_string());
txn.commit()?;  // atomic CAS; retries internally on conflict

API surface

Db

• Db::open(dir) — opens or creates a database
• db.create_tree::<K, V>(name, order) — creates a named tree
• db.open_tree::<K, V>(name) — opens an existing tree
• db.tree::<K, V>(name, order) — open-or-create
• db.rename_tree(old, new) — rename a tree (recorded in manifest)
• db.drop_tree(name) — remove a tree from the catalog
• db.list_trees() — returns all tree names
• db.close() — checkpoints the freelist and drops the database
• db.format_version() — on-disk format version from the superblock

Tree<K, V>

• tree.put(&key, &value) — insert or replace
• tree.get(&key) — lookup, returns Option<V>
• tree.contains_key(&key) — check existence without decoding the value
• tree.delete(&key) — remove
• tree.txn() — start a batched WriteTxn
• tree.range(&start, &end) — forward range scan [start, end)
• tree.range_from(&start) — forward range scan from start to end of tree
• tree.len() / tree.is_empty()
• tree.height() — current tree height (1 = single leaf)

WriteTxn<K, V>

• txn.insert(&key, &value) — stage an insert
• txn.delete(&key) — stage a delete
• txn.commit() — atomically apply all staged operations

delete returns an error if the key is not found. commit returns Err(ApiError::TxnAborted) if the retry budget is exhausted.

Multi-writer semantics (OCC)

Writers run in parallel: each captures the committed 128-bit metadata word, applies its writes on a staged COW tree, and commits via compare_exchange on a single AtomicU128 packing (root_id, height, txn_id). If another writer published first, the transaction rebases from the latest root and retries (bounded). Readers never block writers, and the monotonic txn_id doubles as an ABA guard (no old-pointer retirement needed). Full protocol in ARCHITECTURE.md.

Durability and fsync

Each commit: (1) CAS-publish the new 128-bit metadata word (visible to in-process readers immediately); (2) write the new metadata to the inactive A/B slot; (3) fdatasync() once, flushing both the COW node pages and the metadata page.

Crash safety comes from A/B metadata-slot alternation + CRC32, no WAL: a commit writes slot = txn_id % 2, leaving the previous slot intact, and recovery picks the slot with the highest txn_id and a valid CRC. A crash before fdatasync (or a torn write) simply rolls back to the prior commit — the only cost is possibly leaking a few unreachable pages (wasted space, never data loss). The sync_data() fd-flush behaviour and the O_DIRECT trade-off are covered in ARCHITECTURE.md.

Epoch-based reclamation

Readers pin an epoch while walking a snapshot; writers tag retired pages with the current epoch at commit; a reclaimer frees a page only once every reader older than its retire-epoch has unpinned. No locks on the read path, no use-after-free. Pin/GC details in ARCHITECTURE.md.

On-disk layout

<dir>/
  data.db            # all pages: superblock, tree nodes, metadata slots
  manifest.log       # append-only CRC-framed catalog log
  freelist.snapshot   # optional; written on graceful shutdown
  db.lock            # exclusive flock held while the database is open

Recovery path

database::open acquires an exclusive file lock (db.lock), validates the superblock (page 0, including CRC-32C), replays the CRC-framed manifest to rebuild the in-memory catalog, then reconciles each tree's catalog entry against its on-disk A/B metadata pages (source of truth for root_id, height, size after a crash). If a freelist snapshot exists, freed page IDs are restored so they can be reused.

Key components

• Superblock (page 0): magic, format version, generation counter, CRC-32C.
• Manifest: append-only, CRC-framed log of tree-lifecycle records (CreateTree, RenameTree, DeleteTree, Checkpoint); truncated trailing records are skipped, CRC mismatches reported as corruption.
• Catalog: in-memory TreeId -> TreeMeta, rebuilt from the manifest.
• Per-tree metadata: CRC-validated A/B pages holding (root_node_id, height, size, txn_id); commit writes the inactive slot.
• File lock: exclusive flock on db.lock.

Architecture

For a detailed description of the architecture, design decisions, and trade-offs, see ARCHITECTURE.md.

src/
  api.rs, api/                  # Db, Tree<K,V>, WriteTxn, ApiError
  codec.rs, codec/              # KeyCodec/ValueCodec traits, bincode codecs, kv (API codecs)
  database.rs, database/        # Database, catalog, manifest (reader/writer), metadata, superblock
  bplustree/                    # BPlusTree core: search, insert, delete, commit, transaction
  storage.rs, storage/          # PageStorage, NodeStorage, FilePageStorage, PagedNodeStorage,
                                #   EpochManager, MetadataManager, page cache
  page.rs, page/                # Slotted page layouts (leaf, internal)
  keyfmt.rs, keyfmt/            # Key encoding formats (raw, prefix-compressed)
  layout.rs                     # PAGE_SIZE constant
examples/
  bytes_api.rs                  # Vec<u8> key/value CRUD
  typed_api.rs                  # u64/String with batched transaction
  concurrent_web_store.rs       # Multi-threaded HTTP fetch + concurrent tree writes
  example.rs                    # async HTTP fetch + store
benches/
  bench_insert.rs               # Criterion benchmarks

Layers (bottom → top)

page (4 KB slotted pages) → storage (PageStorage raw I/O · NodeStorage encoded I/O · PagedNodeStorage decoded-node cache) → database (Database<S>: superblock, manifest, catalog, tree lifecycle) → bplustree (BPlusTree: search / insert / delete / CAS-commit, WriteTransaction for batched commits) → api (Db hands out Arc-shared, synchronous Tree<K, V> handles). Each layer is written up in ARCHITECTURE.md.

Design trade-offs

The core choices — explained in depth in ARCHITECTURE.md:

• COW — every write clones only the touched pages (leaf + ancestors) and publishes a new root by CAS; readers see a consistent epoch-pinned snapshot and never block. Same approach as LMDB / BoltDB / redb.
• No sibling pointers — next/prev links would cascade-invalidate under COW (a copied leaf's new page ID breaks its sibling's pointer). Range scans instead use a cursor over a root-to-leaf (node_id, index) stack (BPlusTreeIter); O(log n) per leaf transition, cheap since height is 3–5 and parent pages stay hot.
• Batched OCC writes — WriteTransaction buffers ops and replays against the current root, retrying on CAS conflict (a future sort-by-key/bulk-load path would cut COW copies).
• Physical fullness — large values can fill a 4 KB page before the tree order is reached, splitting at the page level; entries are capped at MAX_ENTRY_PAYLOAD (2038 bytes) so two always fit per page and splits produce valid halves.

Where this design fits

• Embedded databases (the LMDB/redb/BoltDB niche) where the store is linked as a library, not accessed over a network.
• Read-heavy workloads where readers must never block and always see consistent snapshots.
• Crash safety without a WAL: COW gives atomic commits for free since old pages survive until the new root is published.
• Low-to-moderate write contention: OCC retries are cheap when conflicts are rare.

Where it struggles

• Write-heavy workloads with high contention: OCC retries discard and redo all speculative work.
• Large sequential bulk loads: COW copies O(height) pages per insert; a bulk-load path would amortise this.
• Values larger than ~2 KB: entries must fit within MAX_ENTRY_PAYLOAD (2038 bytes). Overflow pages or external value storage are not yet implemented.

Gotchas

• Order-preserving keys: if your codec doesn't preserve lexicographic order, scans will be wrong.
• Commit conflicts: normal under load. WriteTxn retries automatically up to a budget.
• Entry size limit: key + value must fit within 2038 bytes (MAX_ENTRY_PAYLOAD). Entries exceeding this limit are rejected with TreeError::EntryTooLarge.

Roadmap

• Prefix-compressed key block format (PrefixRestarts) — Keys are currently stored verbatim in each slot. When keys share long common prefixes, this wastes significant page space. Prefix compression stores the shared prefix once and only the differing suffix per key, with periodic restart points for random access within the block. This increases key density per page and reduces I/O for prefix-heavy workloads.

• Bulk-load path for large initial imports — Inserting N keys one-by-one through the tree incurs O(height) COW copies per key. A bulk-load path sorts all keys upfront, fills leaves left-to-right, and builds internal nodes bottom-up. Orders of magnitude faster for initial data ingestion compared to incremental inserts.

• Overflow pages for values exceeding MAX_ENTRY_PAYLOAD — Currently key + value must fit within 2038 bytes. Overflow pages would store large values across multiple linked pages, removing this size constraint. This is standard in production B-trees (SQLite, LMDB).

• Fuzz testing (cargo-fuzz) — Use coverage-guided fuzzing to generate random sequences of inserts, deletes, splits, and merges, then verify tree invariants hold after each operation. Catches edge cases in the slotted page layout and codec encode/decode roundtrips that hand-written tests are unlikely to cover.

• Configurable page size — Currently hardcoded to 4 KB. Some workloads benefit from larger pages (16 KB, 64 KB) for fewer tree levels and better sequential throughput; smaller pages reduce write amplification under update-heavy workloads. The superblock already records the page size (page_size); what remains is making PAGE_SIZE a runtime value rather than a compile-time const and threading it through the page layer.

• Deferred value compaction on delete — The slotted leaf page currently compacts the value arena on every delete. Under COW this is just in-memory byte shuffling, but batched deletes pay the cost repeatedly. Deferring compaction until the page needs the space (e.g. before an insert that doesn't fit, or before a merge) would avoid redundant repacking within a single transaction.

• Node merge / rebalancing on delete — Deletes currently remove entries and compact within a leaf, but underfull nodes are not merged with (or rebalanced against) a sibling. Under delete-heavy workloads this leaves the tree with underfilled pages — extra height and wasted space — and deviates from the classic B+tree minimum-occupancy invariant. Implementing merge-on-underflow (borrow from a sibling, or merge two underfull nodes and drop the separator key from the parent) restores occupancy and keeps the tree compact.

• Sharded epoch pinning — EpochManager::pin()/unpin() currently acquire a central Mutex<HashMap<ThreadId, Epoch>> on every read operation. Under high reader concurrency this serialises the pin/unpin brackets even though the tree walk itself is lock-free. Replace with per-thread atomic slots (a Vec<AtomicU64> indexed by a thread-claimed slot) so that pin is a single atomic store and oldest_active() is a lock-free scan. This is the approach used by crossbeam-epoch and similar libraries.

License

Dual-licensed under MIT or Apache-2.0. You may choose either license.

Contact

Paris Mesidis — pmesidis@gmail.com