MiniDB++

A relational database engine built from scratch in C++20. MiniDB++ brings persistent storage, indexing, SQL execution, transactions, and crash recovery together in one end-to-end systems project. It is designed for learning and engineering exploration, not as a production-ready database.

Explore: Architecture · Build & run · SQL demo · Recovery · Testing · Limitations

Highlights

• Storage: versioned 4 KiB pages, variable-length slotted-page tuples, stable page/slot record IDs, and validated free-page reuse.
• Indexes & SQL: persistent page-native B+ tree primary indexes and a hand-written SQL lexer, parser, semantic binder, and executor.
• Buffer management: bounded LRU-K cache, move-only RAII page guards, and WAL-aware dirty-page eviction.
• Transactions: autocommit and explicit BEGIN / COMMIT / ROLLBACK, concurrent readers, and one exclusive writer.
• Durability & recovery: CRC32C segmented WAL, full-page/byte-range/adaptive update records, persistent PageLSNs, restartable CLR-based UNDO, and ownership-scoped non-truncating rollback.
• Checkpoints: sharp and opt-in fuzzy checkpoints with dirty-page/live-transaction tracking and retention-aware WAL reclamation.
• Verification: 103 CTest targets on the v1.0.0 release, including crash injection, randomized models, format compatibility, and focused sanitizer checks.

Architecture

flowchart TB
    Client[CLI client] --> Wire[Versioned TCP protocol]
    Wire --> Engine[SqlEngine]
    Engine --> SQL[Parser / semantic binding / executor]
    Engine --> Txn[TransactionManager]
    SQL --> Relational[Catalog / Table]
    Relational --> Storage[TupleStore + B+ tree]
    Storage --> Allocator[PageAllocator]
    Allocator --> Pool[BufferPoolManager + LRU-K]
    Pool --> Disk[DiskManager]
    Disk --> Database[(database.db)]

    Txn --> Recovery[RecoveryCoordinator]
    Recovery --> Log[LogManager]
    Log --> WAL[(segmented WAL)]
    Recovery --> Pool
    Checkpoint[CheckpointManager] --> Pool
    Checkpoint --> Log

Loading

Persistent structures reference pages by PageId; transient buffer frames have a separate FrameId. The active relational path uses the bounded buffer pool. The legacy Pager and fixed-row RecordStore remain for historical and educational regression tests.

Quick start

Requirements are CMake 3.20 or newer, a C++20 compiler, and a POSIX platform for the TCP and crash-injection tests.

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --parallel
ctest --test-dir build --output-on-failure

Start a database server (default address 127.0.0.1:7432):

./build/minidb_server demo.db

In another terminal, start the interactive client:

./build/minidb_client

Both programs accept --host and --port. The client also supports one-shot execution with --execute SQL and access-path counters with --stats. Run either executable with invalid arguments to see its concise usage line.

Demo

With the server running, these one-shot requests exercise the implemented SQL path:

./build/minidb_client --execute \
  "CREATE TABLE users (id UINT32 PRIMARY KEY, username VARCHAR(64) NOT NULL, score INT64, active BOOLEAN NOT NULL);"
./build/minidb_client --execute \
  "INSERT INTO users VALUES (1, 'alice', 10, TRUE);"
./build/minidb_client --execute \
  "INSERT INTO users VALUES (2, 'bob', 20, FALSE);"
./build/minidb_client --execute \
  "UPDATE users SET score = 25, active = TRUE WHERE id = 2;"
./build/minidb_client --execute \
  "SELECT id, username, score FROM users WHERE id >= 1 AND active = TRUE;"
./build/minidb_client --execute \
  "DELETE FROM users WHERE id = 1;"

The SELECT response is rendered as a small text table:

id | username | score
---+----------+------
1  | alice    | 10
2  | bob      | 25
2 rows

SQL scope

Statement	Current support
CREATE TABLE	Columns, nullability, and one UINT32 PRIMARY KEY
INSERT	One VALUES row, with or without an explicit column list
SELECT	* or named projections, optional WHERE
UPDATE	Literal assignments with optional WHERE
DELETE	Optional WHERE
BEGIN [TRANSACTION] [READ ONLY|READ WRITE], COMMIT, ROLLBACK	Session transactions; BEGIN defaults to READ WRITE

The type system contains UINT32, INT64, BOOLEAN, and VARCHAR(1..4000), plus NULL for nullable columns. WHERE supports =, !=, <>, <, <=, >, >=, parentheses, NOT, AND, and OR, with SQL three-valued logic. A suitable primary-key equality predicate uses the persistent B+ tree; other predicates use a heap scan.

The current grammar intentionally excludes joins, aggregation and GROUP BY, ORDER BY, LIMIT/OFFSET, aliases, subqueries, set operations, secondary indexes, schema alteration, and query optimization.

Autocommit remains the default. To group mutations atomically, send these as separate requests on one connection:

BEGIN;
INSERT INTO users VALUES (3, 'carol', 30, TRUE);
UPDATE users SET username = 'caroline' WHERE id = 3;
COMMIT;

Use ROLLBACK to discard the whole transaction. Disconnect also rolls it back. BEGIN READ ONLY retains shared database access; multiple readers can overlap. A READ WRITE transaction retains exclusive access through durable completion. See transactions.md and concurrency.

Storage engine

Every database file begins with a versioned metadata page, followed by fixed 4096-byte pages. PageAllocator allocates or reuses validated free pages. Variable-length tuple bytes live in slotted pages; a RecordId combines a page ID and stable slot ID, so in-page compaction can move bytes without invalidating an index entry. TupleStore links those pages into a persistent heap. A page-native B+ tree maps UINT32 primary keys to RIDs and maintains its own stable metadata-page identity as roots change.

The exact layouts and invariants are documented in storage-format.md, slotted-pages.md, and bplus-tree-storage.md.

Buffer pool

The active engine has a fixed number of in-memory frames—128 by default—and uses LRU-K with K = 2 by default. A PageId identifies persistent storage; a FrameId identifies only a resident cache frame. Fetching pins a frame, and the move-only ReadPageGuard and WritePageGuard release that pin through RAII. Write guards carry dirty-page intent. Only unpinned frames are evictable, and a dirty victim is written after the WAL rule is satisfied. See buffer-pool.md.

WAL and crash recovery

MiniDB++ supports implicit statement transactions and explicit multi-statement transactions. Physical WAL supports complete 4096-byte page images, an opt-in byte-range before/after encoding, and opt-in per-record adaptive selection, with transaction chains, LSNs, and CRC32C validation. Full-page logging remains the default. The buffer pool may write an uncommitted dirty page (STEAL) and need not force committed pages at commit (NO-FORCE), so startup recovery redoes committed winners and undoes losers. Recovery supports interleaved transaction chains and independent restartable UNDO; production SQL still permits only one writer. Persistent PageLSNs let recovery skip committed updates already represented by an equal or newer disk page; legacy WAL records remain always-redo. Physical compensation log records make completed loser-UNDO work durable across a crash during recovery; CLRs are REDO-able and never themselves undone.

The observable commit rule is:

durable COMMIT    -> recover the transaction as committed
no durable COMMIT -> recover the transaction as aborted

Autocommit mutations and explicit COMMIT return success only after COMMIT is fsynced. Statements inside BEGIN remain uncommitted until explicit COMMIT. The physical logging design does not claim ARIES or crash-safe operation without the WAL sidecars.

Recovery is tested by real subprocess termination with _exit, bypassing normal destructors. Directed cases include crashes before and after COMMIT fsync, dirty STEAL before commit, NO-FORCE winners, repeated crashes during REDO or UNDO, checkpoint publication boundaries, legacy-WAL migration, segment rotation, and reclamation. See wal.md, wal-byte-range.md, wal-adaptive.md, page-lsn.md, and recovery.md.

Checkpoints and segmented WAL

Sharp checkpoints flush the bounded pool; opt-in fuzzy checkpoints instead persist a Dirty Page Table and live transaction table at safe statement boundaries while dirty pages remain resident. Both publish through the same double-slot recovery pointer. Segmented WAL reclaims only history older than the selected mode's recovery floor. See checkpoints.md, fuzzy-checkpoints.md, and wal-segments.md.

Benchmarks

The benchmark runner emits versioned JSON with configuration, latency distributions, storage/WAL counters, and environment metadata. One deterministic Release measurement on a single development machine showed the recovery scan boundary effect:

Recovery mode	Elapsed	WAL scanned
Full historical scan	~204.97 ms	33.70 MiB
Checkpoint-aware scan	~2.13 ms	~331 KiB

These are reproducible experiment results, not universal performance claims or a comparison with another database. The suite also includes controlled LRU-K, storage, SQL, TCP, WAL, transaction, checkpoint, and segment-lifecycle workloads. See benchmarking.md and benchmarks/README.md.

Testing

Configure and run the complete suite with warnings enabled:

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release \
  -DCMAKE_CXX_FLAGS="-Wall -Wextra -Wpedantic"
cmake --build build --parallel
ctest --test-dir build --output-on-failure

The suite covers byte-level format validation, deterministic state models, randomized differential tests, malformed and fuzz-like inputs, real reopen boundaries, TCP integration, and subprocess crash recovery. The current clean Release verification runs 103 CTest targets. Focused AddressSanitizer and UndefinedBehaviorSanitizer builds are also used during release verification. For incremental verification profiles, see the development workflow.

Documentation

• Storage architecture
• Database storage formats
• Buffer pool and LRU-K
• Checkpoint-authorized frame WAL dependency retirement
• Write-ahead log
• Physical byte-range WAL experiment
• Adaptive physical WAL update encoding
• Persistent PageLSN and selective REDO
• Crash recovery
• Multi-transaction recovery substrate
• Explicit transactions
• Concurrent readers and database access
• Compensation records and restartable UNDO
• Sharp checkpoints
• Fuzzy checkpoints, DPT, and recLSN
• Segmented WAL lifecycle
• Benchmarking
• Wire protocol
• Server and client
• SQL parsing and execution

Current limitations

• Writers exclude all database readers/writers for their entire transaction.
• There are no multiple writers, fine-grained locks, MVCC, isolation-level selection, or savepoints.
• Long transactions retain original page images in memory until completion.
• Byte-range/adaptive WAL adds diff CPU cost; adaptive bounds each update to the smaller existing physical encoding, while full-page logging remains the default.
• Checkpoints are synchronous; fuzzy mode is opt-in and requires a safe statement boundary.
• There is no point-in-time recovery or WAL archive.
• Query planning, joins, aggregation, and secondary indexes are not implemented.
• The TCP endpoint has no TLS, authentication, or authorization; it is intended for local development and protocol experimentation.

Development

The project uses C++20 and CMake. Keep normal builds warning-clean under -Wall -Wextra -Wpedantic, preserve documented persistent and wire formats, and add focused tests for behavioral or format changes. Generated builds, database files, WAL sidecars, and benchmark JSON are intentionally ignored.

License

MiniDB++ is available under the MIT License.