Najeeb Said

Personal project · 2025 – 2026

PithDB / PithKV

From-scratch storage engine in Rust exploring B-tree page indexing, write-ahead logging, and crash-safe mmap key-value storage.

WAL
4KB pager
B-tree
Rust·Storage engines·mmap·WAL

Problem

Understanding database storage engine internals below query execution—page layouts, write-ahead log fsync semantics, and crash recovery—requires implementing storage primitives directly.

Approach

Built PithDB from scratch in safe Rust: SQL parser/VM, 4KB page cache, cursor abstraction, byte-level B-tree (leaf splits and parent separator fixups), and a WAL with commit-gated replay recovery.

Exposed configurable workload durability modes (Fast, Batch, Paranoid) after benchmarking the three-order-of-magnitude latency delta between buffered writes and fsync calls.

Pivoted to PithKV, a Bitcask mmap key-value store. Implemented CRC32 record checksums, tombstone deletions, dual-slot shadow paging for directory commits, and atomic compaction via temporary files and directory fsync.

Technical Decisions

  1. Safe Rust storage engine implementation

    Eliminated unsafe Rust in PithDB and restricted unsafe calls in PithKV to raw mmap memory bindings, relying on compiler guarantees for memory safety.

  2. Tiered durability modes (Fast, Batch, Paranoid)

    Exposed explicit durability tiers to callers, allowing applications to trade fsync latency for write throughput based on workload requirements.

  3. Dual-slot CRC shadow paging for directory commits

    Committed key-value directory metadata across two checksummed slots with an active-slot flip, ensuring atomic recovery even if power fails mid-write.

  4. Compaction via atomic rename and parent directory fsync

    Compacted append logs into temporary files, executed atomic renames, and issued fsync calls on parent directories to ensure metadata durability.

  5. Adversarial corruption testing

    Built test suites that inject bit corruptions into CRC headers and execute concurrent operations to verify recovery logic.

Key Achievements

  • Built PithDB B-tree DBMS with 4KB pager and WAL crash recovery in safe Rust.
  • Rebuilt engine into PithKV mmap key-value store featuring dual-slot CRC shadow paging.
  • Exposed configurable durability tiers (Fast, Batch, Paranoid) addressing fsync latency overhead.
  • Implemented atomic log compaction with temporary files and parent directory fsync.
  • Authored test suite verifying crash recovery under simulated data corruption and concurrent thread access.

Outcome

Two storage engines operating with verified crash recovery protocols—WAL replay and dual-slot CRC shadow paging—validated against automated corruption testing.