CS 334: Buffer Manager

Introduction

In this assignment, you will have to implement a prototype of a buffer manager for a database system. I'm supplying a number of files already complete; here is the Java documentation for all of that code, as well as for the code that you will complete.

The code for the underlying Disk Space Manager will be given to you via the class DBFile. Read carefully the API for the DBFile class, since you will be using this in building your buffer manager. Similarly, read carefully the API for BufferManager, since this is the class you will actually create.

Getting Started

Start by grabbing this zip file and extract to a directory that you have created. The project contains the following files, among others:

BufferManager.java: Framework code for you to use as a starting point. You will certainly need to add your own private variables and methods, but your public API should be precisely as specified.
BMTester.java: Buffer manager test program. BMTester carries out a series of tests of the BufferManager class. We'll run these programs against your code to see if you're getting the right output. But I'm only supplying a couple of tests, and I'm not supplying the correct output; we'll run more tests than these.

The Buffer Manager Interface

You will have to implement a buffer manager that uses the clock replacement policy. The buffer manager interface that you will implement allows a program from higher levels of the database system to:

Allocate and deallocate pages on disk.
Bring a disk page to the buffer pool and pin it.
Unpin a page in the buffer pool.

The list of the specific methods that you need to implement are contained in BufferManager.java.

Design Overview and Implementation Details

The buffer pool is a collection of frames (page-sized sequences of main memory bytes) that is managed by the Buffer Manager. It should be stored as an array bufferPool[] of Page objects. In addition, you should maintain an array frameTable[] of descriptors, one per frame. Each descriptor is a is an object that contains a page id, a filename, a pin count, and a dirty bit.

A simple hash table should be used to figure out what frame a given disk page occupies. Use a Java HashMap to do this. Python would call this a dictionary.

When a page is requested for pinning, the buffer manager should do the following: Check the buffer pool (by using the HashMap) to see if it contains the requested page. If the page is not in the pool, it should be brought in as follows:

Choose a frame for replacement, using the Clock replacement policy.
If the frame chosen for replacement is dirty, flush it (i.e., write out the page that it contains to disk, using the DBFile appropriately).
Read the requested page (again, by using DBFile) into the frame chosen for replacement; the pin count and dirty bit for the frame should be initialized to 0 and false, respectively.
Delete the entry for the old page from the Buffer Manager's HashMap and insert an entry for the new page. Also, update the entry for this frame in the frameTable array to reflect these changes.
Pin the requested page by incrementing the pin_count in the descriptor for this frame and return a pointer to the page to the requester.

Error Reporting in the Code

Throw exceptions appropriately. The API describes what exceptions should be thrown when something goes wrong.

The Clock Replacement Policy

There are many ways of deciding which page to replace when a free frame is needed. Commonly used policies in operating systems are FIFO, MRU and LRU. Even though LRU is a commonly used policy, it required maintaining usage information every time a page is accessed. Instead, many database systems use the Clock algorithm which approximates LRU behavior, with bookkeeping only required at the time a page is to be replaced.

Clock Replacement Diagram

The above figure illustrates the execution of the clock algorithm. Conceptually, all the frames in the buffer pool are arranged in a circle around the face of a clock. Associated with each frame is a referenced bit. Each time a page in the buffer pool is unpinned, the referenced bit of the corresponding frame is set to true. Whenever we need to choose a frame for replacement, the current frame pointer, or the "clock hand" (an integer whose value is between 0 and poolSize-1), is advanced, using modular arithmetic so that it does not go past poolSize-1. This corresponds to the clock hand moving around the face of the clock in a clockwise fashion. For each frame that the clock hand goes past that is unpinned, the referenced bit is examined and then cleared. If the bit had been set, the corresponding frame has been referenced "recently" and is not replaced. On the other hand, if the referenced bit is false, the page is selected for replacement. If the selected buffer frame is dirty (i.e. it has been modified), the page currently occupying the frame is written to disk.

Note that when a frame is needed, the clock hand is advanced before the frame is considered for replacement. Otherwise, the frame most recently used will always be the first one checked, which is silly. You should initialize your clockhand appropriately so that frame 0 is the very first frame that your buffer pool uses.

Multiple parts

Part 1: Get the first test only (i.e., test1) to run correctly.

Part 2: Get the second test (i.e., test2) to run correctly.

Part 3: Get all the methods in BufferManager.java implemented, and test them. Make sure to test all of the methods, test edge cases, and test very carefully to see if your replacement policy is working precisely as it should; we will attempt to do so when grading.

Handing in Your Code

If you are working in a team, only one of you should submit the code. We will be grading anonymously, so leave your names off the file. If you need to make sure to grant credit to someone else, do so in a file called credits.txt; we will not look at this file until after we are done grading anonymously.

Zip up all of your code, and submit it via Moodle.

Good luck, have fun, and ask questions!