DB Buffer Manager

A compact C++ implementation of a database buffer manager. The project demonstrates how a storage engine keeps frequently used pages in memory, tracks page pins, writes dirty pages back to storage, and chooses replacement victims with the Clock second-chance algorithm.

This repository is intentionally small, documented, and testable. It is suitable for learning database internals and extending into a more complete storage manager.

Quick Start

git clone https://github.com/macyxiangA/db-buffer-manager.git
cd db-buffer-manager
cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure

Run the example:

./build/basic_usage

What It Does

Database systems do not read every record directly from disk for every operation. They move fixed-size pages between persistent storage and an in-memory buffer pool. This project implements that middle layer:

• BufMgr owns a fixed number of memory frames.
• File exposes page-level storage operations.
• BufHashTbl maps (file, pageNo) to the frame holding that page.
• BufDesc tracks frame metadata: page identity, pin count, dirty bit, validity, and Clock reference bit.

When a caller requests a page, the buffer manager returns an in-memory Page*. The caller pins the page while using it and unpins it when done. Dirty pages are written back before eviction or during flush.

Features

• Fixed-size buffer pool with page descriptors.
• Clock second-chance replacement policy.
• Pin count protection for pages currently in use.
• Dirty page tracking and write-back on flush, eviction, and destruction.
• Hash table lookup for constant-time page-to-frame resolution.
• Minimal page-oriented File abstraction for tests and examples.
• CMake build, automated tests, and GitHub Actions CI.

Architecture

Client code
   |
   v
BufMgr
   |-- BufDesc[]      frame metadata
   |-- Page[]         in-memory buffer pool
   |-- BufHashTbl     (File*, pageNo) -> frameNo
   |
   v
File
   |
   v
Page storage

Repository Layout

.
|-- buf.C                    buffer manager, frame metadata, and hash table implementation
|-- include/                 public headers
|-- src/file.cpp             lightweight page storage used by tests and examples
|-- tests/test_buf.cpp       behavior tests for replacement, flushing, and pin safety
|-- examples/basic_usage.cpp minimal usage example
|-- .github/workflows/       CI configuration

Core Operations

Operation	Purpose
readPage(file, pageNo, page)	Pin and return a page, loading it into the pool if needed.
unPinPage(file, pageNo, dirty)	Release a page and optionally mark it dirty.
allocPage(file, pageNo, page)	Allocate a new page and pin it in the buffer pool.
disposePage(file, pageNo)	Remove an unpinned page from both buffer and file storage.
flushFile(file)	Write all dirty unpinned pages for a file and remove them from the pool.

Build

Requirements:

• CMake 3.16+
• A C++17 compiler

cmake -S . -B build
cmake --build build

Test

ctest --test-dir build --output-on-failure

The tests cover:

• dirty page flush behavior,
• replacement refusal when every frame is pinned,
• Clock replacement with dirty victim write-back,
• dispose safety for pinned pages.

Example

File file("demo");
BufMgr bufferManager(8);

int pageNo = -1;
Page* page = nullptr;

bufferManager.allocPage(&file, pageNo, page);
page->data[0] = 'A';
bufferManager.unPinPage(&file, pageNo, true);
bufferManager.flushFile(&file);

Design Notes

The implementation uses Clock replacement instead of exact LRU because Clock approximates recency with lower bookkeeping overhead. Each frame has a refbit. Referenced frames get a second chance; unpinned frames with a cleared reference bit can be evicted. Pinned frames are never evicted because active callers may still be reading or modifying them.

The included File class is intentionally lightweight and in-memory so the buffer manager can be tested without depending on platform-specific disk behavior. The buffer manager boundary is the important part: replacing File with a disk-backed implementation does not change the buffer replacement, pinning, or dirty-page logic.

Correctness Invariants

• A frame with pinCnt > 0 is never selected as an eviction victim.
• Dirty pages are written before eviction or file flush.
• The hash table and frame descriptor state are updated together.
• Failed new-page allocation is rolled back when the buffer pool has no replaceable frame.
• Disposing a pinned page is rejected.

Roadmap

• Add a disk-backed File implementation.
• Add configurable page sizes.
• Add optional metrics for hit rate, eviction count, and flush latency.
• Add thread-safety with latches around shared metadata.
• Add benchmarks comparing Clock, LRU, and MRU behavior.

License

This project is released under the MIT License.