BUILD / PRODUCT OVERVIEW
DATABASE SYSTEMS ARCHITECTURE • STORAGE, INDEXING, OPTIMIZER & CONCURRENCY
BUSTUB RELATIONAL DATABASE ENGINE
Multi-Threaded Relational Database Storage & Execution Engine (CMU 15-445/645)
Engineered a disk-backed, multi-threaded relational database management system (RDBMS) in modern C++ from the ground up. Designed to operate under strict memory-safety and high-concurrency constraints, the engine implements custom page-level buffer management, latch-crabbing B+ Tree indexing, a Volcano-model physical query execution pipeline with rule-based cost optimization, and multi-granularity Two-Phase Locking (2PL) with autonomous cycle-detection deadlock resolution.
100%
TEST PASS RATE
TEST-SUITE
56 / 56 TEST SUITES VERIFIED ACROSS P1-P4
GoogleTest & SQLLogicTest under Clang-14 on WSL2
0 LEAKS
MEMORY & THREAD SAFETY
TEST-SUITE
ADDRESSSANILIZER & UNDEFINEDBEHAVIORSANITIZER
ASan detect_leaks=1, strict_init_order=1 clean exit
4 PILLARS
ENGINE SUBSYSTEMS
TEST-SUITE
STORAGE · INDEX · OPTIMIZER · CONCURRENCY
Full-stack relational database architecture
5 MODES
LOCK HIERARCHY
TEST-SUITE
IS · IX · S · SIX · X + DFS DEADLOCK DETECTOR
Multi-granularity 2PL with Waits-For cycle detection
SYSTEM INSTRUMENT / BUSTUB
VISUAL METAPHOR — MULTI-LAYER RELATIONAL DATABASE ENGINE ARCHITECTURE
INSTRUMENT / 4-PILLAR RELATIONAL DATABASE SUBSYSTEMS
ARCHITECTURAL INVARIANTS & CONCURRENCY PROTOCOLS
The full relational stack: from raw 4096-byte disk blocks up through the LRU-K frame cache, concurrent latch-crabbing B+ Tree, Volcano iterator execution engine, and multi-granularity Two-Phase Locking (2PL) with background DFS cycle detection.
THE BUILD AT A GLANCE
WHAT IT IS, WHAT IT SOLVES, HOW IT IS BUILT — THE FULL EVIDENCE CHAIN LIVES IN THE CASE STUDY
THE PROBLEM
Bridging the semantic gap between raw, page-oriented block storage (4 KB disk pages) and low-latency, multi-threaded transactional SQL queries without corrupting memory, leaking page frames, or deadlocking worker threads.
Designing high-concurrency index structures where concurrent splits and merges do not introduce root-level latch contention or thread starvation.
Transforming unoptimized declarative relational plans into sub-quadratic physical operator trees that execute streaming iterators without materialization overhead.
Guaranteeing ACID serializability and isolation invariants across concurrent transactions while preventing and resolving distributed lock dependency cycles.
WHAT IT DOES
- Engineer a thread-safe Buffer Pool Manager with LRU-K frame eviction and asynchronous disk I/O scheduling.
- Construct an optimistic Latch-Crabbing B+ Tree supporting concurrent point lookups, range scans, splits, and merges.
- Build a Volcano-style iterator execution engine with rule-based optimizations (NLJ -> HashJoin, Sort + Limit -> TopN, filter pushdown).
- Implement a Multi-Granularity Lock Manager (IS, IX, S, SIX, X) with Strict 2PL and a background DFS waits-for cycle detector.
- Validate the complete stack against 56 automated test suites with 0 leaks or errors under ASan/UBSan.
RESEARCH QUESTION
Can a disk-backed database engine sustain high concurrent read-write transaction throughput while enforcing strict 2PL serializability, zero sanitizer defects, and deterministic deadlock resolution?
ARCHITECTURE
ARCHITECTURE — DATA PATH
ARCHITECTURE DIAGRAM — THE DOCUMENTED LAYERS, NOT A MEASUREMENT
- 01
STORAGE & BUFFER POOL (P1)
Page-level memory hierarchy & disk scheduling
- 02
CONCURRENT B+ TREE INDEX (P2)
Dynamic multi-level balanced index & latch crabbing
- 03
VOLCANO QUERY EXECUTION (P3)
Streaming pull-based operator pipeline
- 04
RULE-BASED QUERY OPTIMIZER (P3)
Logical-to-physical AST transformation
- 05
MULTI-GRANULARITY 2PL & DEADLOCK (P4)
Hierarchical concurrency control & transaction recovery
TECHNOLOGY
KEY EVIDENCE
WORK_PROOF.md Dossier
Complete milestone commit hashes, terminal test logs, and sanitizer proofs.
OPEN THE SOURCE →Buffer Pool Manager Telemetry
11/11 tests passed in 39.41s across LRUKReplacer, DiskScheduler, and BufferPoolManager.
OPEN THE SOURCE →Concurrent B+ Tree Telemetry
6/6 concurrent stress tests passed in 2.58s with multi-threaded latch crabbing.
OPEN THE SOURCE →Volcano Query Engine Telemetry
21/21 SQLLogicTest suites passed including multi-way hash joins and window functions.
OPEN THE SOURCE →Concurrency & Deadlock Telemetry
11/11 tests passed verifying table/row locks, 2PL phase transitions, and DFS cycle aborts.
OPEN THE SOURCE →Sanitizer Verification Log
Clean ASan & UBSan execution across all unit tests and stress benchmarks.
OPEN THE SOURCE →CURRENT STATE
100% VERIFIED · 56/56 SUITES
Multi-threaded disk-backed relational database engine in modern C++20. CMU 15-445/645 compliant.
LAST VERIFIED 2026-11-01 — GoogleTest + SQLLogicTest + Clang-14 ASan/UBSan: 56/56 Passed · BASELINE 0ce5626 · VIEW THE RUN →
GO DEEPER
THE FULL EVIDENCE CHAIN
Problem, hypothesis, architecture, methodology, experiments, results — and the failures and limitations beside them. The case study is the full write-up for this build.