Cella

             .__  .__          
  ____  ____ |  | |  | _____   
_/ ___\/ __ \|  | |  | \__  \  
\  \__\  ___/|  |_|  |__/ __ \_
 \___  >___  >____/____(____  /
     \/    \/               \/

A crash-recoverable, single-writer, page-oriented B-tree key-value storage engine in Rust.

This project focuses on storage-layer fundamentals rather than SQL semantics. It implements durable set/get/delete/scan operations on a persistent B-tree, with write-ahead logging (WAL), recovery, page reuse, and a professional CLI for interactive and scripted usage.

Highlights

• 4KB fixed-size page model (Page { id, data: [u8; 4096] })
• Persistent B-tree with multi-level splits and recursive traversal
• Delete support with leaf/internal rebalancing (borrow/merge)
• Leaf sibling chain for range scans
• WAL-based crash recovery (redo-style page replay on startup)
• Manual checkpoint (fsync + WAL truncate)
• Free-list page reuse with chained overflow freelist pages
• Structural invariants verification (verify_tree)
• CLI with subcommands, JSON output, REPL, benchmark tools, and DOT graph export

Architecture Overview

The engine is intentionally page-centric:

• Data file pages: B-tree internal/leaf nodes, freelist metadata, overflow pages
• WAL file: append-only records that log page images before data-page writes
• Recovery: on open, WAL records are replayed to data pages, then WAL is truncated

Core modules:

• src/storage/page.rs: page header/layout, slot directory, cell operations
• src/storage/disk.rs: page file I/O, allocation, sync operations
• src/storage/btree.rs: B-tree logic, rebalancing, verification, stats, DOT dump
• src/storage/wal.rs: WAL record append/read/truncate
• src/storage/freelist.rs: persistent free-list with overflow chaining
• src/main.rs: CLI + REPL

Data Structure Notes

• Page size is fixed at 4096 bytes.
• Slotted-page layout supports variable-size cells.
• Leaf cells encode key/value bytes.
• Internal cells encode route entries (min_key -> child_page_id).
• Leaf pages maintain next_leaf pointers for ordered scans.

Durability Model

Write path:

1. Append page image to WAL and sync WAL record.
2. Write page to data file.

Startup path:

1. Read all WAL records.
2. Replay page payloads to target page IDs.
3. Truncate WAL.

Checkpoint path:

1. Sync data file.
2. Truncate WAL.

CLI Usage

Run REPL (default command when no subcommand is provided):

cargo run -- --db kv.db repl

One-shot commands:

cargo run -- --db kv.db set user:1 alice
cargo run -- --db kv.db get user:1
cargo run -- --db kv.db del user:1
cargo run -- --db kv.db scan --start user:1 --limit 20
cargo run -- --db kv.db verify
cargo run -- --db kv.db checkpoint
cargo run -- --db kv.db stats

JSON output (automation-friendly):

cargo run -- --db kv.db --json stats

Benchmark commands:

cargo run -- --db kv.db bench 20000
cargo run -- --db kv.db benchmix 50000

DOT graph export:

cargo run -- --db kv.db dumpdot --out tree.dot
dot -Tpng tree.dot -o tree.png

REPL Commands

• SET <key> <value>
• GET <key>
• DEL <key>
• SCAN [start_key] [limit]
• CHECKPOINT
• VERIFY
• STATS
• BENCH [n]
• BENCHMIX [n]
• DUMPDOT [path]
• HELP
• EXIT

The REPL includes line editing, history, and typo-aware command suggestions.

Build and Test

cargo build
cargo test

Project Scope

This repository targets storage-engine internals, not SQL features. It is a single-writer engine focused on correctness, durability, and observability.

Not in scope (currently):

• SQL parser/planner/executor
• multi-writer concurrency control
• networked replication
• background compaction/checkpoint workers

Validation Strategy

The test suite covers:

• page layout invariants
• disk read/write and allocation behavior
• WAL append/truncate and recovery replay
• multi-level tree growth and lookups
• delete behavior with rebalance and collapse
• freelist overflow chaining and reuse
• crash-recovery scenarios

Roadmap Ideas

• Prometheus metrics endpoint + Grafana dashboard
• background checkpointing and batched WAL sync policy
• expanded randomized/fuzz crash testing in CI
• deeper page inspection/debug commands

License

MIT License