MiniDB

MiniDB is a lightweight, high-performance, single-file embeddable B+Tree storage engine written in modern C++20 with full ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) Write-Ahead Logging (WAL) crash durability.

---

Key Features

• Slotted Page Storage Engine: 4 KB fixed-size page architecture with 24-byte PageHeader, 32-byte NodeHeader, sorted 8-byte Slot array, and downward-growing payload heap with dynamic fragmentation compaction.
• Buffer Pool Manager: Configurable frame capacity with LRU eviction replacer, pin count tracking, dirty page flushing, and WAL ordering invariants.
• Physical WAL & CLRs: Dual-image physical page diff logging for kUpdate records, compensation log records (kClr) for single-pass rollback, sharp checkpointing, and torn tail detection via CRC32 checksums.
• ARIES 3-Pass Recovery Engine:
  1. Analysis Pass: Scans WAL forward building active transaction table.
  2. Idempotent Redo Pass: Replays physical updates driven strictly by page LSN comparison.
  3. Undo Pass: Reverses active uncommitted transactions using prev_lsn chains and generates CLRs.
• Crash Consistency Fuzzer: Automated multi-process fuzzer with POSIX fsync journal oracle testing against arbitrary process SIGKILL and simulated pwrite/fsync syscall failures.
• Zero External Dependencies: Standard C++20 library + POSIX system calls only (pread, pwrite, fsync, ftruncate).

---

Architecture Overview

 ┌─────────────────────────────────────────────────────────────┐
 │                         DB Facade                           │
 ├──────────────────────────────┬──────────────────────────────┤
 │         BTree Engine         │       RecoveryManager        │
 ├──────────────────────────────┴──────────────────────────────┤
 │                     BufferPoolManager                       │
 ├──────────────────────────────┬──────────────────────────────┤
 │          LogManager          │         DiskManager          │
 └──────────────────────────────┴──────────────────────────────┘

---

Building and Running

Prerequisites

• C++20 compatible compiler (clang++, g++, or Apple Clang)
• CMake 3.20+
• POSIX-compliant operating system (Linux, macOS)

Debug Build & Unit Tests

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build
./build/minidb_tests

Release Build & Benchmarks

cmake -S . -B build_release -DCMAKE_BUILD_TYPE=Release
cmake --build build_release
./build_release/bench_main --mode seq_insert --num-ops 100000

Running Crash Consistency Fuzzer

python3 scripts/crash_fuzz.py --iterations 100 --mode mixed --build-dir build

---

Performance Summary

Measured on GitHub Actions Ubuntu Server runner (AMD EPYC 7763, 100k ops, 100-byte payloads):

Benchmark Mode	Operations	Throughput (ops/sec)	Latency p50 (us)	Latency p99 (us)
Sequential Insert	100,000	52,442 ops/sec	6.42 us	90.29 us
Random Insert	100,000	58,640 ops/sec	6.11 us	88.88 us
Point Get	100,000	427,923 ops/sec	2.25 us	3.42 us
Range Scan (100 keys)	10,000	405,404 ops/sec	2.37 us	3.65 us
Recovery	1 open	433 ops/sec	2.20 ms	2.20 ms

See docs/BENCHMARKS.md for complete benchmark details and docs/COMPARISON.md for head-to-head comparisons against SQLite, LMDB, and RocksDB.

---

Design Trade-Offs & Limitations

1. Single-Threaded Execution Model: Transactions execute under global synchronization locks; concurrency control (2PL/MVCC) is omitted for storage layer simplicity.
2. Fixed Page Size: Fixed 4096-byte pages require keys and values to fit within a single slotted page (max entry payload: 3900 bytes). Large binary objects (LOBs) are not supported.
3. Sharp Checkpointing: DB::Checkpoint() flushes all dirty pages to disk during checkpointing rather than maintaining a fuzzy checkpoint dirty page table.

---

License

MIT License. See LICENSE for details.