H2DB - Rust Database Storage Manager

H2DB is a Rust implementation of the core storage manager components from CMU 15-445 Database Systems Project 1. This project implements a thread-safe, disk-oriented storage manager with buffer pool management, LRU-K page replacement, and asynchronous disk I/O scheduling.

Overview

This project implements the fundamental components of a database storage manager:

• Buffer Pool Manager: Manages pages in memory and coordinates with disk I/O
• LRU-K Replacement Policy: LRU-K page eviction algorithm
• Disk Scheduler: Asynchronous disk I/O request processing
• Page Management: Thread-safe page operations using RwLock guards

The implementation is built with Rust's safety guarantees and leverages async/await for high-performance I/O operations.

Architecture

Task 1: LRU-K Replacement Policy (src/buffer/lru_k_replacer.rs)

The LRU-K replacer tracks page access patterns and makes eviction decisions:

• Backward K-Distance: Evicts frames with the largest backward k-distance
• Access History: Maintains timestamp history for up to K recent accesses
• Eviction Strategy: Frames with <K accesses get +∞ distance; ties broken by earliest timestamp
• Thread-Safe: Uses internal synchronization for concurrent access

Key Methods:

• evict() - Selects frame for eviction based on LRU-K algorithm
• record_access(frame_id, access_type) - Records page access with timestamp
• set_evictable(frame_id, evictable) - Controls frame eviction eligibility
• remove(frame_id) - Removes frame from tracking
• size() - Returns number of evictable frames

Task 2: Disk Scheduler (src/storage/disk/disk_scheduler.rs)

Asynchronous disk I/O scheduler with background worker thread:

• Request Queue: Thread-safe unbounded channel for disk requests
• Background Processing: Dedicated tokio task processes requests concurrently
• Promise/Future Pattern: Uses oneshot channels for request completion signaling
• Read/Write Operations: Handles both page reads and writes through DiskManager

Key Methods:

• schedule(disk_request) - Queues a disk I/O request
• _poll_requests() - Background worker that processes queued requests
• _process_disk_requests() - Executes individual read/write operations

Task 3: Buffer Pool Manager (src/buffer/buffer_pool_manager.rs)

Central component managing page lifecycle in memory:

• Page Table: Maps page IDs to frame IDs for fast lookup
• Free Frame Management: Tracks available frames for new pages
• Pin/Unpin Mechanism: Reference counting prevents premature page eviction
• Dirty Page Tracking: Ensures modified pages are written to disk
• Integration: Coordinates LRU-K replacer and disk scheduler

Key Methods:

• get_page_read(page_id) - Fetches page with read lock
• get_page_write(page_id) - Fetches page with write lock
• unpin_page(page_id, is_dirty) - Releases page reference
• new_page() - Allocates a new page
• delete_page(page_id) - Removes page from buffer pool
• flush_page(page_id) - Forces page write to disk

Dependencies

• tokio (1.46.1): Async runtime for I/O operations
• thiserror (2.0.12): Error handling macros
• async-trait (0.1): Async trait support
• rstest (0.26.1): Advanced testing framework

Building and Testing

Build the Project

cargo build

Run All Tests

cargo test

Run Specific Component Tests

# LRU-K Replacer tests
cargo test lru_k_replacer

# Disk Scheduler tests  
cargo test disk_scheduler

# Buffer Pool Manager tests
cargo test buffer_pool_manager

Run with Debug Output

cargo test -- --nocapture

Configuration

Key configuration constants (can be modified in respective files):

• H2DB_PAGE_SIZE: 4096 bytes (standard page size)
• DEFAULT_DB_IO_SIZE: 16 (I/O operation batch size)
• DEFAULT_DB_PATH: "./tmp/h2db" (default database directory)

Future Enhancements

• DiskManager with concurrent Reads/Write support for improved performance
• Persistent disk manager with disk based file management integration

License

This project is an educational implementation based on CMU 15-445 coursework and is intended for learning purposes.

---

Note: This implementation demonstrates core database storage concepts in Rust while maintaining the essential functionality described in the CMU 15-445 Project 1 specification.