marksql is a DBMS prototype in C++20. The codebase is already structured around the classic pieces of a database storage stack, even though several behaviors are still incomplete. This README is meant to be a fast architectural refresher so you can come back later and remember how the pieces are intended to fit together.
The current implementation is centered on a paged storage model:
DiskLayer/handles page-sized reads, writes, and page-id allocation against a database file.MemoryManagementLayer/provides an in-memory buffer pool plus an LRU replacement policy.RecordLayer/interprets raw page bytes as a slotted heap page that can store variable-length tuples.TableLayer/provides a table-heap abstraction over linked heap pages.Models/contains the low-level structs and page wrappers used across the stack.Tests/exercises each layer independently.
The project is not yet a full database. There is no SQL layer, parser, planner, executor, schema system, WAL, or transaction manager. Right now the code is mostly about learning and validating the storage-engine path from disk page -> buffer frame -> heap page -> tuple.
The intended flow is:
DiskManagerowns a database file and treats it as an array of fixed-size pages.BufferPoolManagercaches those pages in RAM asPageobjects.LRUReplacerdecides which unpinned frame can be evicted when the buffer pool is full.HeapPageinterprets a page's rawchar[4096]payload as a slotted page storing tuples.TableHeapwalks one or more heap pages and exposes table-style operations such as insert, read, delete, and edit byRID.
If you want one mental model for the codebase, it is this:
TableHeap is the public storage abstraction, HeapPage is the record format, BufferPoolManager is the RAM cache, and DiskManager is the persistence boundary.
Shared data structures used by multiple layers.
Page: an in-memory page frame with metadata:page_id_data_[PAGE_SIZE]- dirty bit
- pin count
RID:(page_id, slot_id)address of a tuple.Slot: slot-directory entry(offset, length)for one tuple.HeapPageHeader: compact header placed at the start of a heap page:- number of slots
- start of slot directory / free-space metadata
- end of free space
Tuple.h: currently not the tuple type used by the heap-page code. The real tuple payload type inHeapPageis currentlyusing Tuple = std::vector<char>;.
Contains DiskManager, the lowest layer that talks to the filesystem.
Responsibilities:
- Open or create the backing file.
- Read exactly one page with
pread. - Write exactly one page with
pwrite. - Hand out monotonically increasing page ids via
allocatePage().
Important design point:
DiskManagerdoes not know anything about records, slots, or tables.- It only understands page ids and byte offsets.
Contains the in-memory cache and replacement policy.
Owns:
- A fixed-size array of
Pageframes (BUFFER_POOL_CAPACITY = 1000). - A page table mapping
page_id -> frame index. - A free-list of never-used frames.
- An
LRUReplacerfor choosing eviction victims among unpinned frames. fetchPage(page_id)- Returns a cached page if already resident.
- Otherwise loads it from disk into a free frame or an evicted frame.
- Pins the page while it is in active use.
unpinPage(page_id, is_dirty)- Decrements pin count.
- Marks the page dirty if requested.
- Makes it eligible for eviction once the pin count reaches zero.
newPage(...)- Allocates a fresh page id through
DiskManager. - Reserves a frame for it.
- Returns a pinned, dirty page ready to be initialized by upper layers.
- Allocates a fresh page id through
flushPage(page_id)- Forces the current in-memory bytes to disk.
deletePage(page_id)- Removes an unpinned page from the buffer pool and frees its frame for reuse.
Replacer: abstract base class.LRUReplacer: linked-list + hash-map implementation of least-recently-used eviction among unpinned frames.pin(frame_id)removes a frame from the eviction set.unpin(frame_id)adds or moves a frame to the back of the LRU list.victim(...)evicts the least recently used unpinned frame.- The header lives at the beginning of the page.
- The slot directory grows forward from the front.
- Tuple bytes are copied into the page from the back downward.
- Free space is the gap between those two regions.
- Check whether there is enough free space for tuple bytes plus one
Slot. - Copy the tuple bytes near the end of free space.
- Append a slot entry containing offset and length.
- Advance
free_space_start. - Move
free_space_endbackward. insertTuplegetTupleapplyDeletechangeTupleexists but is still effectively unfinished in the implementationsetNextPage/setPrevPageand getters exist at the object level- a
DiskManager* - a
BufferPoolManager* first_page_id_insertTuple- Starts from
first_page_id_ - Fetches a page through the buffer pool
- Wraps it as a
HeapPage - Tries to insert the tuple
- Returns an
RIDwith(page_id, slot_id)
- Starts from
getTuple- Walks pages until it finds the target page id and reads the slot
applyDelete- Walks pages until it finds the target page id and marks the slot deleted
editTuple- Intended to update in place when possible, or delete-and-reinsert when not
TableHeapchooses a target page, starting atfirst_page_id_.- It asks
BufferPoolManagerfor that page. BufferPoolManagereither:- returns the cached frame, or
- loads the page from disk through
DiskManager, or - evicts an unpinned frame and reuses it.
TableHeapconstructs aHeapPageview over the page's raw bytes.HeapPage::insertTuplecopies the tuple bytes and appends a slot entry.TableHeapreturns the resultingRID.TableHeapfetches candidate pages through the buffer pool.- Each page is interpreted as a
HeapPage. - Once the target
page_idis found, the slot directory is used to reconstruct the tuple bytes. BufferPoolManagerasksLRUReplacerfor a victim frame.- If the victim page is dirty, it is written back via
DiskManager. - The old page id is removed from the page table.
- The frame is reused for the requested page.
- Fixed-size page abstraction.
- Disk-backed page read/write.
- Buffer pool with pin/unpin semantics.
- LRU-based eviction of unpinned frames.
- Slotted heap-page insert and fetch.
- Basic table-heap wrapper and tests for the main happy paths.
HeapPage::changeTupleis a stub, but tests already describe the intended behavior.TableHeap::editTupleis written around the idea of in-place update or reinsertion, but it currently depends on the unfinishedHeapPage::changeTuple.- Heap-page linked-list metadata is not persisted inside the page bytes yet.
TableHeap::insertTupleallocates a new page id iffetchPagereturnsnullptr, but it does not fully initialize and link a new heap page into a durable page chain.- Pin/unpin discipline is not consistently enforced across all table-layer operations, so long-running usage could keep pages pinned longer than intended.
- Deletion currently zeroes the slot length, but there is no space reclamation or compaction.
- The
Tupleclass inModels/Tuple.hdoes not match theTuplealias used byHeapPageandTableHeap. main.cppis not yet a real entry point for the storage engine; most meaningful validation lives inTests/.TableLayer/TableHeap.hand.cppRecordLayer/HeapPage.hand.cppMemoryManagementLayer/BufferPoolManager.hand.cppMemoryManagementLayer/Replacer/LRUReplacer.hand.cppDiskLayer/DiskManager.hand.cppModels/Page.hTests/HeapPageTests.cpp,Tests/BpmTests.cpp, andTests/TableHeapTests.cpptestDMtestPagetestReplacertestBPMtestHeapPagetestTableHeap- disk pages at the bottom
- a buffer pool in the middle
- slotted heap pages on top of raw page bytes
- a table-heap API on top of heap pages
Main behaviors:
Defines the replacement-policy interface and the current implementation:
Conceptually:
Contains HeapPage, which overlays structure onto a raw page buffer.
The page layout is a slotted-page design:
That means inserts work like this:
Current HeapPage operations:
Important caveat:
The current next/prev page ids are stored as member fields on HeapPage, not serialized into the underlying page bytes. So page links behave like transient wrapper state rather than durable page metadata right now.
Contains TableHeap, the highest-level storage abstraction currently present.
TableHeap owns:
The constructor allocates the first table page immediately.
Main behaviors:
Conceptually this is the start of a heap-file implementation: a table is a linked sequence of slotted pages, and each tuple is addressed by RID.
When a tuple is inserted through TableHeap:
When reading a tuple by RID:
When the buffer pool is full:
This is the part worth rereading before making changes later, because it explains what is architectural intent versus what is already solid.
If you want the fastest re-entry path into the project, read files in this order:
That order mirrors the logical abstraction stack from highest-level storage API down to disk.
The project uses CMake and GoogleTest.
Typical flow:
cmake -S . -B build
cmake --build build
ctest --test-dir buildDefined test executables include:
Sanitizers are enabled in the CMake configuration for the main library, which is useful while iterating on low-level page and memory logic.
marksql is currently a storage-engine skeleton:
The architecture is already recognizable as a miniature database storage stack. The remaining work is mostly about making the table/page linkage durable, finishing tuple update behavior, tightening lifecycle rules around pinning and flushing, and then building more database functionality above this foundation.