CASE STUDY
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.
EVIDENCE INSTRUMENT / PROJECT-SPECIFIC
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.
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.
MOTIVATION
Relational database internals represent the pinnacle of systems engineering: memory management, multi-threaded synchronization, query compilation, and transactional correctness must operate in perfect unison.
Building BusTub across all four core pillars demonstrates end-to-end mastery of low-level C++ systems programming, lock-free and latch-crabbing concurrency protocols, and formal verification using AddressSanitizer and UndefinedBehaviorSanitizer.
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?
OBJECTIVE
- 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.
ARCHITECTURE
VISUAL METAPHOR — MULTI-LAYER RELATIONAL DATABASE ENGINE ARCHITECTURE
ARCHITECTURE — DATA PATH
ARCHITECTURE DIAGRAM — THE DOCUMENTED LAYERS, NOT A MEASUREMENT
- 01
STORAGE & BUFFER POOL (P1)
Page-level memory hierarchy & disk scheduling
- LRU-K backward K-distance frame eviction (O(1) lookup)
- Asynchronous DiskScheduler with worker queue & std::promise/future
- Dirty-page persistence & pin-count reference management
- 02
CONCURRENT B+ TREE INDEX (P2)
Dynamic multi-level balanced index & latch crabbing
- Dynamic split on overflow (>= M) & coalesce/redistribute on underflow
- Optimistic read/write latch crabbing with early safe-ancestor release
- Thread-safe forward iterators across leaf pages
- 03
VOLCANO QUERY EXECUTION (P3)
Streaming pull-based operator pipeline
- Init() / Next() iterators: SeqScan, IndexScan, Insert, Update, Delete
- In-memory HashJoin, NestedLoopJoin, Aggregation, and TopN executors
- Filter predicate evaluation & tuple reconstruction
- 04
RULE-BASED QUERY OPTIMIZER (P3)
Logical-to-physical AST transformation
- NLJAsHashJoin: rewrites equi-joins to O(N) hash join pipelines
- SortLimitAsTopN: fuses Sort + Limit into bounded-heap O(N log K) TopN
- Predicate pushdown into B+ Tree IndexScan executors
- 05
MULTI-GRANULARITY 2PL & DEADLOCK (P4)
Hierarchical concurrency control & transaction recovery
- 5 Lock Modes (IS, IX, S, SIX, X) with compatibility matrix enforcement
- Strict 2PL state transitions: GROWING -> SHRINKING with prioritized upgrades
- Background Waits-For graph DFS cycle detection aborting youngest txns
DATA FLOW
PIPELINE — 7 STAGES, IN ORDER
- 01SQL statements are parsed, bound to catalog schemas, and compiled into abstract syntax tree (AST) query plans.
- 02The Rule-Based Optimizer inspects the plan tree, fusing sort-limits into TopN and rewriting nested-loop equi-joins into HashJoins.
- 03The Volcano execution engine pulls tuples on-demand via root.Next(), cascading calls down to scan and join iterators.
- 04Executors interact with the Lock Manager to acquire hierarchical table and row locks according to transaction isolation levels.
- 05IndexScan navigates concurrent B+ Tree pages using latch-crabbing protocols, resolving RID pointers into page identifiers.
- 06The Buffer Pool Manager fetches target 4 KB disk pages into memory frames, dispatching asynchronous I/O requests via DiskScheduler.
- 07Dirty pages and transactional commits are persisted to disk upon transaction commit, releasing all acquired locks.
METHODS
- Deterministic Backward K-Distance Tracking — separates sequential scan pollution from recurring analytical workloads.
- Optimistic Latch Crabbing — acquires parent and child page latches, immediately releasing safe ancestors to eliminate root bottlenecking.
- Bounded-Heap Top-N Selection — maintains a max-heap of size K during table scans, eliminating O(N log N) full sorting.
- In-Memory Hash Join — single-pass hash table build on right child followed by streaming probe on left child.
- Waits-For Graph Cycle Detection — periodic background daemon runs deterministic DFS to locate deadlock cycles and selects the youngest transaction (highest txn_id) as victim.
RISK / VALIDATION
- Root-level latch contention mitigated via optimistic read/write crabbing and fine-grained page-level latching.
- Deadlock avoidance and thread starvation eliminated through FIFO queue ordering, exclusive upgrading_ slots, and autonomous cycle-detection.
- Memory corruption and dangling frame references prevented via RAII page guards and automated sanitizers (ASan, UBSan).
EXPERIMENTS
Buffer Pool Under High Concurrency
COMPLETEDCan the Buffer Pool Manager handle intense multi-threaded page thrashing without race conditions or memory leaks?
11 / 11 test suites passed including ContentionTest and DeadlockTest with 0 sanitizer defects.
B+ Tree Concurrent Insert/Delete Stress
COMPLETEDDo optimistic latch-crabbing read/write traversals prevent race conditions during concurrent node splits and coalesces?
6 / 6 concurrent stress tests (InsertTest1/2, DeleteTest1/2, MixTest1/2) passed in 2.58 seconds with zero deadlocks.
End-to-End SQL Logic Test Suite
COMPLETEDDoes the Volcano execution engine and query optimizer correctly process multi-way joins, aggregations, and window functions?
21 / 21 SQLLogicTest suites passed cleanly (p3.01-seqscan through p3.20-window-function).
Deadlock Detection & Isolation Verification
COMPLETEDDoes the Waits-For DFS detector break circular dependency cycles while maintaining Strict 2PL invariants across isolation levels?
11 / 11 concurrency test suites passed, verifying correct victim aborts and repeatable read guarantees.
RESULTS
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
All 56 automated test suites across all four project milestones passed with 100% verification.
The engine operates with zero memory leaks, zero buffer overflows, and zero data races under AddressSanitizer and UndefinedBehaviorSanitizer.
Achieved seamless integration between disk scheduling, latch-crabbing B+ Tree indexing, cost/rule-based plan optimization, and multi-granularity Two-Phase Locking.
LIMITATIONS
- Currently uses fixed 4 KB disk pages without variable-length compressed columnar storage.
- Deadlock detection runs periodically rather than synchronously at lock timeout.
- Academic integrity compliance prohibits publishing full implementation source code publicly; read-only verification repository is available to engineering hiring teams upon request.
CURRENT STATUS
100% VERIFIED · 56/56 SUITES
Multi-threaded disk-backed relational database engine in modern C++20. CMU 15-445/645 compliant.
EVIDENCE
LAST VERIFIED 2026-11-01 — GoogleTest + SQLLogicTest + Clang-14 ASan/UBSan: 56/56 Passed · BASELINE 0ce5626 · VIEW THE RUN →
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 →INTERACTIVE LAB
AUTOMATED VERIFICATION TELEMETRY — CTEST & ADDRESSSANITIZER
56 / 56 SUITES PASSED · 0 DEFECTS
