Buffer Manager Project
Buffer Pool Project to Manage files/pages/records!
Project Scope:
- Build a Buffer Manager that controls what pages go into the Buffer
Buffer Manager
-
A database buffer pool is an Array of fixed-sized memory buffers called frames that are used to hold database pages that have been read from the disk into memory.
-
The database page in memory is an exact copy of the corresponding page on disk when its first read into the buffer pool
-
Once a page has been read from the disk to the buffer pool, the DBMS software (MySQL, SQLite3, etc) can update/make changes to the page, causing the copy in the buffer pool to be different from the copy on the disk. Such pages are termed dirty.
-
Only a limited number of database pages fit in the memory at any given time, so the buffer manager is used to control which pages are in the buffer
-
When the buffer manager recieves a requested page, it first checks if the page is in one of the frames in the pool, if so then it returns a pointer to the page. If not, the buffer must free a frame (possibily write the freed page to the disk if it’s dirty) and then it reads in the requested page from the disk into the frame that was just freed!
Structure of the Buffer Manager
- Buffer Hash Table
- Clock Algorithm
- Buffer Pool Array
- Buffer Description Table
- Buffer Stats
Here is the Header File of the Buffer Manager, we will implement the methods for this!
class BufMgr
{
private:
FrameId clockHand; // Current Page the Clock is pointing to
std::uint32_t numBufs; // Number of Buffer Frames
BufHashTbl *hashTable; // Maps
BufDesc *bufDescTable; // Describes each Frame in the Buffer Pool
BufStats bufStats;
void advanceClock();
void allocBuf(FrameId & frame);
public:
Page* bufPool; // Here is the Buffer Pool!!!!, which is an array
BufMgr(std::uint32_t bufs); // Constructor
~BufMgr(); // deconstructor
void readPage(File* file, const PageId PageNo, Page*& page);
void unPinPage(File* file, const PageId PageNo, const bool dirty);
void allocPage(File* file, PageId &PageNo, Page*& page);
void flushFile(const File* file);
void disposePage(File* file, const PageId PageNo);
void printSelf();
BufStats &getBufStats() // Getter Method!!!!!!!!!!!!!
{
return bufStats;
}
void clearBufStats()
{
bufStats.clear(); // Clear the Stats: .clear() is a function for array
}
};
Clock Replacement Algorithm
-
The Buffer Pool contains numBufs frames, numbered 0 to numBufs-1, conceptually all the frames in the buffer pool are arranged in a circular list.
-
In the Circular Pool Buffer, each frame is associated with a bit termed the refbit, each time a page in the Buffer Pool is accessed, the refbit of the corresponding frame is set to True. T
-
The Clock is advanced using modular arithmetic so that it does not go past numBufs-1 in a clockwise fashion
Buffer Pool
-
Buffer Pool consists of an Array of numBufs Frames, each the size of a database Page
-
Along with this Buffer Pool Array, the BufMgr also cojtains an array of numBufs instances of the BufDesc class that is used to describe the state of each frame in the buffer!
BufHashTbl Class
The Hash Table is used to keep track of the pages that are currently resident in the pool.
HashTable is Maping the File and Page numbers to the Buffer Pool Frames, the HashTable is made up of HashBuckets that contains the follwing:
- File* : Pointer to a file object
- PageID : Page number within a file
- FrameID : Frame number of a page in the Buffer Pool
- hashBucket* : Pointer to next bucket in the chain
The header file for the Buffer Hash table is shown below.
bufHashTbl.h
#pragma once
#include "file.h"
namespace badgerdb {
struct hashBucket {
File *file;
PageId pageNo;
FrameId frameNo;
hashBucket* next;
};
class BufHashTbl
{
private:
int HTSIZE;
hashBucket** ht;
int hash(const File* file, const PageId pageNo);
public:
BufHashTbl(const int htSize);
~BufHashTbl();
void insert(const File* file, const PageId pageNo, const FrameId frameNo);
void lookup(const File* file, const PageId pageNo, FrameId &frameNo);
void remove(const File* file, const PageId pageNo);
};
}
Buffer Description Class
The Buffer Description Class is used to keep track of the state of each frame in the Buffer Pool, each attribute (besides BufMgr Class) is private.
Describes each frame in the buffer pool such as:
- pinCnt: Number of times this page has been pinned
- dirty: If records have been changed then true
- valid: true is page is valid (actually in use)
- refbit: true if this buffer frame has been referenced recently (used by the clock algorithm)
Methods it can call:
- Clear(): initializes buffer frame and sets everything up
- Set(File* filePtr, PageId pageNum): This sets the frame!
- Print(): Prints values of the member variables
- BufDesc(): Constructor
Buffer Description Class
class BufDesc {
public:
friend class BufMgr;
private:
File* file;
PageId pageNo;
FrameId frameNo;
int pinCnt;
bool dirty;
bool valid;
bool refbit;
void Clear();
void Set(File* filePtr, PageId pageNum);
void Print();
BufDesc();
};
Buffer Stats Class
- Used to describe the stats of the Buffer like the number of accesses, diskreads, and diskwrites
struct BufStats
{
int accesses;
int diskreads;
int diskwrites;
void clear()
{
accesses = diskreads = diskwrites = 0;
}
BufStats()
{
std::cout << "Number of Accesses: " accesses << std::endl;
std::cout << "Number of Diskreaads: " diskreads << std::endl;
std::cout << "Number of Diskwrites: " diskwrites << std::endl;
}
};
Buffer Manager Class
Here is were we actually implement methods, recall are Buffer Manager Class which is shown below in the code.
We have shown the BufHashTbl, BufDesc, and BufStats. We will now implement the different methods that the Buffer Manager can perform:
Method to Implement:
- BufMgr [x]
- ~BufMgr [x]
- advanceClock [x]
- allocBuf [x]
- readPage [x]
- unPinPage [x]
- allocPage [x]
- flushFile []
- disposePage []
- printSelf [x]
class BufMgr
{
private:
FrameId clockHand;
std::uint32_t numBufs;
BufHashTbl *hashTable;
BufDesc *bufDescTable;
BufStats bufStats;
void advanceClock();
void allocBuf(FrameId & frame);
public:
Page* bufPool;
BufMgr(std::uint32_t bufs);
~BufMgr();
void readPage(File* file, const PageId PageNo, Page*& page);
void unPinPage(File* file, const PageId PageNo, const bool dirty);
void allocPage(File* file, PageId &PageNo, Page*& page);
void flushFile(const File* file);
void disposePage(File* file, const PageId PageNo);
void printSelf();
BufStats &getBufStats()
{
return bufStats;
}
void clearBufStats()
{
bufStats.clear();
}
};
Constructor
The Constructor sets up the Buffer Manager and this method is given to us
- Sets up Buffer Pool as an array of Pages
- Creates Buffer Description Table to descibe each frame in the buffer
- Creates Hash Table for our Buffer to map file and page numbers
BufMgr::BufMgr(std::uint32_t bufs) : numBufs(bufs) {
bufPool = new Page[bufs];
bufDescTable = new BufDesc[bufs];
for (FrameId i = 0; i < bufs; i++) {
bufDescTable[i].frameNo = i;
bufDescTable[i].valid = false;
}
int htsize = ((((int) (bufs * 1.2))*2)/2)+1;
hashTable = new BufHashTbl(htsize);
clockHand = bufs - 1;
}
Deconstructor
In order to remove everything from our Buffer, we must first write each frame in the buffer pool to the disk and then deleted (deallocate) any memory used.
-
Check to see if the page in the Buffer Pool is dirty
-
If the page is dirty, we have to write to the disk
-
Deallocate Our Memory
BufMgr::~BufMgr() {
for(int i = 0; i < numBufs; i++ ){
if(bufDescTable[i].dirty == true){
File* thisFile = bufDescTable[i].file;
PageId thisPageNo = bufDescTable[i].pageNo;
Page thisPage = bufPool[thisPageNo];
bufStats.accesses++;
thisFile ->writePage(thisPage);
bufStats.diskwrites++:
bufDescTable[i].dirty = false;
hashTable -> remove(thisFile, thisPageNo);
bufDescTable[i].Clear();
}
}
delete [] bufPool;
delete [] bufDescTable;
delete hashTable;
}
void advanceClock()
- The purpose of this method is to advance the clock hand to the next frame in the Buffer Pool
clockHand represents the current frame in the Buffer Pool
void BufMgr::advanceClock()
{
clockHand = (clockHand +1 ) % numBufs;
}
void allocBuf(FrameId& frame)
- Allocates a free frame using the first part of the Clock Algorithm
The Allocate Buffer method follows the first clock algorithm, while we iterate over the Buffer Description Table
-
Check if the frame is Valid, if true continue Else, we will return the frame to use
-
We then check if the refbit == false, we continue Else, if true, we reset the refbit to false and advance the clock this frame has been used lately
-
We then Check if the pinCnt == 0, if so we continue Else, we Advance the Clock
-
We check if dirty == false (check if the page is dirty) If false we return the frame If true (frame is dirty), we must do the following: a. Write the Page to Disk b. Remove from hashTable c. Reset BufDescTable Frame (.Clear()) d. Return Frame
Throws Exception if all the buffer frames are pinned
void BufMgr::allocBuf(FrameId & frame)
int count = 0;
bool allocated = false;
while(count < numBufs * 2) {
if(bufDescTable[clockHand].valid == true) {
if(bufDescTable[clockHand].refbit == false) {
if(bufDescTable[clockHand].pinCnt == 0) {
if(bufDescTable[clockHand].dirty == false){
allocated = true;
frame = clockHand;
break;
}
else {
bufDescTable[clockHand].file->writePage(bufPool[clockHand]);
bufStats.accesses++;
hashTable->remove(bufDescTable[clockHand].file, bufDescTable[clockHand].pageNo);
bufDescTable[clockHand].Clear();
allocated = true;
frame = clockHand;
bufStats.diskwrites++;
break;
}
}
else {
advanceClock();
count++;
}
}
else {
bufDescTable[clockHand].refbit= false;
advanceClock();
count++;
}
}
else{
allocated = true;
frame = clockHand;
break;
}
}
if(allocated == false) {
throw BufferExceededException();
}
}
readPage(File* file, const PageId PageNo, Page*& page)
Reads the given page from the file into a frame and returns the pointer to page.
Checks if the page is already in the buffer pool by invoking the lookup() method, which may throw the HashNotFoundException when the page is not in the buffer pool. There are two cases to be handled depending on the outcome of the lookup() call:
-
Case 1: Page is not in the buffer pool, so we must call allocBuf() to allocate a buffer frame and then we call the method file->readPage() to read the page from the disk into the buffer pool frame that we just allocated. Next, insert the page into the hashtable. Finally, invoke Set() on the frame to set it up properly. Return a pointer to the frame containing the page via the page parameter.
-
Case 2: Page is in the buffer pool. In this case set the appropriate refbit, increment the pinCnt for the page, and then return a pointer to the frame containing the page via the page parameter.
void BufMgr::readPage(File* file, const PageId pageNo, Page*& page)
{
FrameId frameNo;
try {
hashTable->lookup(file, pageNo, frameNo);
bufDescTable[frameNo].refbit = true;
bufDescTable[frameNo].pinCnt++;
page = &bufPool[frameNo]; // Return Page pointer to page to use
}
catch(HashNotFoundException e)
{
allocBuf(frameNo); // Free a Frame
bufStats.diskreads++;
bufPool[frameNo] = file->readPage(pageNo);
bufDescTable[frameNo].Set(file, pageNo);
page = &bufPool[frameNo];
hashTable->insert(file, pageNo, frameNo);
}
}
void unPinPage(File* file, const PageId PageNo, const bool dirty);
Purpose: Unpin a page from memory since it is no longer required for it to remain in memory.
Steps:
Decrements the pinCnt of the frame containing (file, PageNo) and, if dirty == true; sets the dirty bit.
Throws PAGENOTPINNED if the pin count is already 0.
Does nothing if page is not found in the hash table lookup.
void BufMgr::unPinPage(File* file, const PageId pageNo, const bool dirty)
{
FrameId frameNo = 0;
hashTable->lookup(file, pageNo, frameNo);
if (dirty == true){
bufDescTable[frameNo].dirty = dirty;
}
if (bufDescTable[frameNo].pinCnt == 0)
{
throw PageNotPinnedException(file->filename(), pageNo, frameNo);
}
else {
bufDescTable[frameNo].pinCnt--;
}
}
void allocPage(File* file, PageId &PageNo, Page*& page);
The first step in this method is to to allocate an empty page in the specified file by in-voking the file->allocatePage() method, this method will return a newly allocated page. Then allocBuf() is called to obtain a buffer pool frame. Next, an entry is inserted into the hash table and Set() is invoked on the frame to set it up properly. The method returns both the page number of the newly allocated page to the caller via the pageNo parameter and a pointer to the buffer frame allocated for the page via the page parameter.
void BufMgr::allocPage(File* file, PageId &pageNo, Page*& page)
{
Page emptyPage = file -> allocatePage();
pageNo = emptyPage.page_number();
FrameId frame;
allocBuf(frame);
bufPool[frame] = emptyPage;
bufStats.accesses++;
page = &bufPool[frame];
hashTable -> insert(file, pageNo, frame); // insert into hashTable
bufDescTable[frame].Set(file, pageNo); // Set Up on the Buffer Description Table
}
void flushFile(const File* file);
Should scan bufTable for pages belonging to the file. For each page encountered it should: a. If the page is dirty, call file->writePage() to flush the page to disk and then set the dirty bit for the page to false b. Remove the page from the hashtable (whether the page is clean or dirty) c. Invoke the Clear() method of BufDesc for the page frame.
Throws PagePinnedException if some page of the file is pinned. Throws BadBuffer- Exception if an invalid page belonging to the file is encountered.
void BufMgr::flushFile(const File* file)
{
for(FrameId i = 0; i < numBufs; ++i){
if (bufDescTable[i].file == file){
PageId pageNo = bufDescTable[i].pageNo;
if(bufDescTable[i].pinCnt != 0){
throw PagePinnedException(file -> filename(), pageNo, i);
}
if(bufDescTable[i].valid == false){
throw BadBufferException(i, bufDescTable[i].dirty, bufDescTable[i].valid, bufDescTable[i].refbit);
}
if (bufDescTable[i].dirty == true){
Page page = bufPool[i];
bufStats.accesses++;
bufDescTable[i].file -> writePage(page);
bufStats.diskwrites++;
bufDescTable[i].dirty = false;
hashTable -> remove(file, pageNo);
bufDescTable[i].Clear();
}
}
}
}
void disposePage(File* file, const PageId PageNo);
This method deletes a particular page from file. Before deleting the page from file, it makes sure that if the page to be deleted is allocated a frame in the buffer pool, that frame is freed and correspondingly entry from hash table is also removed.
void BufMgr::disposePage(File* file, const PageId pageNo) {
FrameId frameNo = 0;
hashTable->lookup(file, pageNo, frameNo);
bufDescTable[frameNo].Clear();
hashTable->remove(file, pageNo);
file->deletePage(pageNo);
}
void printSelf();
Method that prints the Buffer
- Given to us
void BufMgr::printSelf(void)
{
BufDesc* tmpbuf;
int validFrames = 0;
for (std::uint32_t i = 0; i < numBufs; i++)
{
tmpbuf = &(bufDescTable[i]);
std::cout << "FrameNo:" << i << " ";
tmpbuf->Print();
if (tmpbuf->valid == true)
validFrames++;
}
std::cout << "Total Number of Valid Frames:" << validFrames << "\n";
}
Practicing using the Database, Files, and Pages
Here is a main file demonstrating using the Database Pages and Files and writing records !!
#include <iostream>
#include <stdlib.h>
//#include <stdio.h>
#include <cstring>
#include <memory>
#include "page.h"
#include "buffer.h"
#include "file_iterator.h"
#include "page_iterator.h"
#include "exceptions/file_not_found_exception.h"
#include "exceptions/invalid_page_exception.h"
#include "exceptions/page_not_pinned_exception.h"
#include "exceptions/page_pinned_exception.h"
#include "exceptions/buffer_exceeded_exception.h"
using namespace badgerdb;
int main()
{
const std::string& filename = "test.db";
std::cout << "Creating a Database named test.db " << std::endl;
// Clean up from any previous runs that crashed.
try {
File::remove(filename);
}
catch(FileNotFoundException){}
{
// Create a new database file.
File new_file = File::create(filename);
// Allocate some pages and put data on them.
PageId third_page_number;
PageId fourth_page_number;
// Loop through and create new page()
for (int i = 0; i < 5; ++i) {
Page new_page = new_file.allocatePage();
if (i == 3) {
// Keep track of the identifier for the third page so we can read it later!
third_page_number = new_page.page_number();
}
if (i == 4){
// Keep Track of the identifier for the fourth page so we can read it later!!
fourth_page_number = new_page.page_number(); // Testing
}
// Insert "Record into each page"
new_page.insertRecord("hello!");
// Write the page back to the file (with the new data).
new_file.writePage(new_page);
}
// Iterate through all pages in the file.
for (FileIterator iter = new_file.begin(); iter != new_file.end(); ++iter) {
// Iterate through all records on the page.
for (PageIterator page_iter = (*iter).begin(); page_iter != (*iter).end(); ++page_iter) {
std::cout << "Found record: " << *page_iter << " on page " << (*iter).page_number() << "\n";
}
}
// Retrieve the third page and add another record to it.
Page third_page = new_file.readPage(third_page_number);
const RecordId& rid = third_page.insertRecord("world!");
new_file.writePage(third_page);
std::cout << std::endl;
// Retrieve the record we just added to the third page.
std::cout << "Third page has a new record: " << third_page.getRecord(rid) << "\n\n";
// REtrive the 4th page and add another rtecord to it
Page fourth_page = new_file.readPage(fourth_page_number);
const RecordId& rid2 = fourth_page.insertRecord("Here is the 4th page!!!");
new_file.writePage(fourth_page);
// Retrieve 4th page
std::cout << "Fourth page has a new record: " << fourth_page.getRecord(rid2) << "\n\n";
}
// new_file goes out of scope here, so file is automatically closed.
// Delete the file since we're done with it.
File::remove(filename);
}
Example Output:
Creating a Database named test.db
Found record: hello! on page 1
Found record: hello! on page 2
Found record: hello! on page 3
Found record: hello! on page 4
Found record: hello! on page 5
Third page has a new record: world!
Fourth page has a new record: Here is the 4th page!!!
Main File to Test out the Database and the Buffer Manager (Main.cpp)
-
Driver File, shows you how to use the File and Page classes and contains simple test cases for the Buffer Manager.
-
Run test of the Buffer Manager
Test 1
void test1()
{
//Allocating pages in a file...
for (i = 0; i < num; i++)
{
bufMgr->allocPage(file1ptr, pid[i], page);
sprintf((char*)tmpbuf, "test.1 Page %d %7.1f", pid[i], (float)pid[i]);
rid[i] = page->insertRecord(tmpbuf);
bufMgr->unPinPage(file1ptr, pid[i], true);
}
//Reading pages back...
for (i = 0; i < num; i++)
{
bufMgr->readPage(file1ptr, pid[i], page);
sprintf((char*)&tmpbuf, "test.1 Page %d %7.1f", pid[i], (float)pid[i]);
if(strncmp(page->getRecord(rid[i]).c_str(), tmpbuf, strlen(tmpbuf)) != 0)
{
PRINT_ERROR("ERROR :: CONTENTS DID NOT MATCH");
}
bufMgr->unPinPage(file1ptr, pid[i], false);
}
std::cout<< "Test 1 passed" << "\n";
}
Test 2
void test2()
{
//Writing and reading back multiple files
//The page number and the value should match
for (i = 0; i < num/3; i++)
{
bufMgr->allocPage(file2ptr, pageno2, page2);
sprintf((char*)tmpbuf, "test.2 Page %d %7.1f", pageno2, (float)pageno2);
rid2 = page2->insertRecord(tmpbuf);
bufMgr->allocPage(file3ptr, pageno3, page3);
sprintf((char*)tmpbuf, "test.3 Page %d %7.1f", pageno3, (float)pageno3);
rid3 = page3->insertRecord(tmpbuf);
bufMgr->readPage(file2ptr, pageno2, page2);
sprintf((char*)&tmpbuf, "test.2 Page %d %7.1f", pageno2, (float)pageno2);
if(strncmp(page2->getRecord(rid2).c_str(), tmpbuf, strlen(tmpbuf)) != 0)
{
PRINT_ERROR("ERROR :: CONTENTS DID NOT MATCH");
}
bufMgr->readPage(file3ptr, pageno3, page3);
sprintf((char*)&tmpbuf, "test.3 Page %d %7.1f", pageno3, (float)pageno3);
if(strncmp(page3->getRecord(rid3).c_str(), tmpbuf, strlen(tmpbuf)) != 0)
{
PRINT_ERROR("ERROR :: CONTENTS DID NOT MATCH");
}
bufMgr->unPinPage(file1ptr, pageno1, false);
}
for (i = 0; i < num/3; i++) {
bufMgr->unPinPage(file2ptr, i+1, true);
bufMgr->unPinPage(file2ptr, i+1, true);
bufMgr->unPinPage(file3ptr, i+1, true);
bufMgr->unPinPage(file3ptr, i+1, true);
}
std::cout << "Test 2 passed" << "\n";
}
Test 3
void test3()
{
try
{
bufMgr->readPage(file4ptr, 1, page);
PRINT_ERROR("ERROR :: File4 should not exist. Exception should have been thrown before execution reaches this point.");
}
catch(InvalidPageException &e)
{
}
std::cout << "Test 3 passed" << "\n";
}
Test 4
void test4()
{
bufMgr->allocPage(file4ptr, i, page);
bufMgr->unPinPage(file4ptr, i, true);
try
{
bufMgr->unPinPage(file4ptr, i, false);
PRINT_ERROR("ERROR :: Page is already unpinned. Exception should have been thrown before execution reaches this point.");
}
catch(PageNotPinnedException &e)
{
}
std::cout << "Test 4 passed" << "\n";
std::cout << "Get Buffer Stats at END: " << std::endl;
bufMgr->getBufStats();
std::cout << "_______________________ " << std::endl;
}
Test 5
void test5()
{
std::cout << "TEST NUMBER 5!!!!! " << std::endl;
for (i = 0; i < num; i++) {
bufMgr->allocPage(file5ptr, pid[i], page);
sprintf((char*)tmpbuf, "test.5 Page %d %7.1f", pid[i], (float)pid[i]);
rid[i] = page->insertRecord(tmpbuf);
}
PageId tmp;
try
{
bufMgr->allocPage(file5ptr, tmp, page);
PRINT_ERROR("ERROR :: No more frames left for allocation. Exception should have been thrown before execution reaches this point.");
}
catch(BufferExceededException &e)
{
}
std::cout << "Test 5 passed" << "\n";
for (i = 1; i <= num; i++)
bufMgr->unPinPage(file5ptr, i, true);
}
Test 6
void test6()
{
//flushing file with pages still pinned. Should generate an error
for (i = 1; i <= num; i++) {
bufMgr->readPage(file1ptr, i, page);
}
try
{
bufMgr->flushFile(file1ptr);
PRINT_ERROR("ERROR :: Pages pinned for file being flushed. Exception should have been thrown before execution reaches this point.");
}
catch(PagePinnedException &e)
{
}
std::cout << "Test 6 passed" << "\n";
for (i = 1; i <= num; i++)
bufMgr->unPinPage(file1ptr, i, true);
bufMgr->flushFile(file1ptr);
}
How to Set up Buffer Manager as a Program
-
Includes all the files including the buffer.cpp that we did above
-
File Organization/Structure and Set Up
Makefile
- Mmakefile is used to make what to do, most often the makefile tells make how to compile and link a program.
- Included in the file above
CC=g++
# change to c++14 if you are using an older version
CPPFLAGS=-std=c++17 -g
all:
cd src;\
$(CC) $(CPPFLAGS) *.cpp exceptions/*.cpp -I. -Wall -o badgerdb_main
clean:
cd src;\
rm -f badgerdb_main test.?
Run the Program
run make in the terminal
make
Then run the executable
./src/badgerdb_main
Output
Creating a Database named test.db
Found record: hello! on page 1
Found record: hello! on page 2
Found record: hello! on page 3
Found record: hello! on page 4
Found record: hello! on page 5
Third page has a new record: world!