A relational database storage engine built from scratch in Java. Implements the full storage stack of a DBMS — from raw disk I/O up through indexed record access — with ACID transactions, write-ahead logging, and concurrent multi-transaction support.
Built as a semester-long course project in database implementation (Yeshiva University).
PetiteDB is a layered storage engine. Each layer builds directly on the one below it, mirroring the architecture of production databases like PostgreSQL and MySQL.
┌─────────────────────────────────────────────────────────┐
│ Index Module StaticHashIndex (per-bucket heap) │
├─────────────────────────────────────────────────────────┤
│ Metadata Module System catalog (stored in heap) │
├─────────────────────────────────────────────────────────┤
│ Record Module Slotted-page heap files │
├─────────────────────────────────────────────────────────┤
│ Query Module Scan / UpdateScan / Datum │
├─────────────────────────────────────────────────────────┤
│ Transaction ACID: concurrency + recovery │
│ ├── Concurrency S/X lock table, FIFO ordering │
│ └── Recovery WAL-based UNDO recovery │
├─────────────────────────────────────────────────────────┤
│ Buffer Pool Pin/unpin, Naive & CLOCK eviction │
├─────────────────────────────────────────────────────────┤
│ Log Manager Append-only WAL, reverse iterator │
├─────────────────────────────────────────────────────────┤
│ File Manager Block I/O via FileChannel/ByteBuffer│
└─────────────────────────────────────────────────────────┘
Reads and writes fixed-size blocks to disk using java.nio.channels.FileChannel and ByteBuffer. Maintains an open-channel cache via ConcurrentHashMap. Handles both fresh-database initialization and resuming from existing state via a DBConfiguration singleton.
Append-only write-ahead log. Records are written right-to-left within each page, which makes reverse iteration (needed for UNDO recovery) O(1) per record without any separate index. An LSN counter enables selective flushes — the flush(lsn) call is a no-op if the record is already on disk.
Fixed-size pool of in-memory pages. Supports two eviction policies:
- Naive — evicts the first unpinned buffer found
- CLOCK — approximates LRU by rotating a "clock hand" across the pool
Pinning is blocking: if no buffer is available, the caller waits (via wait()/notifyAll()) up to a configurable timeout before throwing BufferAbortException.
Each transaction gets its own ConcurrencyMgr and RecoveryMgr. Enforces the following protocol:
- Acquires a shared lock before any read
- Acquires an exclusive lock before any write
- Writes a before-image log record before modifying a buffer (WAL)
- On commit: flushes modified buffers, writes a COMMIT record, flushes the log, then releases all locks
- On rollback: scans the log backwards and undoes all changes made by the transaction
Global LockTable singleton backed by a ConcurrentHashMap<BlockId, LockInfo>. Locking is per-block with fine-grained synchronization on each LockInfo object, so transactions operating on different blocks don't contend with each other. FIFO ordering is enforced: a pending exclusive lock request blocks subsequent shared lock requests, preventing writer starvation.
UNDO-only WAL recovery. On startup, the recovery process scans the log in reverse, identifies uncommitted transactions (those without a COMMIT or ROLLBACK record before a CHECKPOINT), and applies the before-image values to restore the database to a consistent state. Writes a CHECKPOINT record after completing recovery.
Typed log records are supported for all data types: SETINT, SETBOOLEAN, SETDOUBLE, SETSTRING, SETBYTES.
Heap-organized files using slotted-page layout. Each slot begins with a boolean in-use flag. RecordPage manages read/write access within a single block. TableScan iterates across all blocks in a file, crossing block boundaries transparently. Supports int, varchar, boolean, double, and varbinary field types.
System catalog stored in two heap tables (tblcat and fldcat) that are themselves managed by the record module. On fresh startup, the catalog tables are bootstrapped. On restart, layouts are reconstructed by scanning the catalog tables — no hardcoded schema at the application layer.
Static hash index with a configurable bucket count (default: 100). Each bucket is a separate heap-organized file. Supports equality search (beforeFirst / next), insert, delete, and deleteAll. Type safety is enforced at insert/delete time by comparing the datum's SQL type against the indexed column's schema type.
- Layered architecture — each module has a clean interface (
FileMgrBase,LogMgrBase, etc.) that the layer above depends on, making each module independently testable - No third-party storage libraries — all disk I/O, page layout, and concurrency primitives implemented from first principles using the Java standard library
- Thread-safe buffer pool — blocking
pin()with configurable timeout;unpin()wakes all waiters vianotifyAll() - FIFO lock ordering — prevents write starvation without requiring a full deadlock detection cycle
- WAL before buffer modification — correct ordering maintained throughout the transaction module
- Reverse log iteration — records written right-to-left in pages; the log iterator reads them back in reverse with no extra data structure
src/
├── main/java/edu/yu/dbimpl/
│ ├── file/ # FileMgr, Page, BlockId
│ ├── log/ # LogMgr (WAL with reverse iterator)
│ ├── buffer/ # BufferMgr (Naive + CLOCK eviction)
│ ├── tx/
│ │ ├── Tx.java # Full ACID transaction
│ │ ├── concurrency/ # LockTable (S/X, FIFO)
│ │ └── recovery/ # WAL UNDO recovery
│ ├── record/ # RecordPage, TableScan, Schema, Layout
│ ├── metadata/ # TableMgr (system catalog)
│ ├── query/ # Datum, Scan, UpdateScan
│ ├── index/ # StaticHashIndex
│ ├── config/ # DBConfiguration singleton
│ └── demo/ # Demo programs for each module
└── test/java/edu/yu/dbimpl/
├── file/ # FileMgr correctness tests
├── log/ # LogMgr correctness tests
├── buffer/ # Buffer pool tests
├── tx/ # Transaction commit/rollback/recovery + concurrency tests
├── record/ # RecordPage, TableScan, schema tests + concurrency + perf
├── metadata/ # TableMgr tests
└── index/ # Hash index correctness, edge cases, and perf tests
Prerequisites: Java 17+, Maven 3.8+
# Build and run all tests
mvn test
# Build without running tests
mvn compile
# Run a specific test class
mvn test -Dtest=BufferTest
# Run the buffer module demo
mvn exec:java -Dexec.mainClass="edu.yu.dbimpl.demo.SampleBufferModuleDemo"Demo programs exist for each module under edu.yu.dbimpl.demo:
SampleFileModuleDemoSampleLogModuleDemoSampleBufferModuleDemoSampleTxModuleDemoSampleRecordModuleDemoSampleMetadataModuleDemoSampleIndexModuleDemo
| Dependency | Version | Purpose |
|---|---|---|
| Java | 17 | Language and NIO |
| JUnit Jupiter | 5.8.1 | Unit and integration testing |
| Log4j2 | 2.24.3 | Structured logging |
The architecture follows the layered design described in Database Design and Implementation by Edward Sciore. All implementations are original.