CSE-4411(A)
Database Management Systems

York University
Fall 2009
Project #1
The Buffer Pool Manager
from Java Minibase
(University of Wisconsin)
  Introduction

For this project, you are to implement a simplified version of the Buffer Manager layer within Java Minibase, without support for concurrency control or recovery, with the LRU replacement strategy. You will be given the code for the lower layer, the Disk Space Manager.

Review the chapter on Disks and Files, to get an overview of buffer management. See the Javadoc Minibase documentation to understand how (java) Minibase is put together and its layers' APIs. Read the description of the DB class, the diskmgr package, in the javadoc, which you will call extensively in this assignment. You should also look over the code under diskmgr/ to learn how a package is declared and how Exceptions are handled in Minibase.

 
  The Buffer Manager Interface

The simplified Buffer Manager interface that you will implement in this assignment allows a client (a higher level program that calls the Buffer Manager) to allocate/de-allocate pages on disk, to bring a disk page into the buffer pool and pin it, and to unpin a page in the buffer pool.

The methods that you are to implement are described below:

    public class BufMgr {

      /**
       * Create the BufMgr object.
       * Allocate pages (frames) for the buffer pool in main memory and
       * make the buffer manage aware that the replacement policy is
       * specified by replacerArg (i.e. Clock, LRU, MRU etc.).
       *
       * @param numbufs number of buffers in the buffer pool.
       * @param replacerArg name of the buffer replacement policy.
       */

      public BufMgr(int numbufs, String replacerArg) {};


      /** 
       * Pin a page.
       * First check if this page is already in the buffer pool.  
       * If it is, increment the pin_count and return a pointer to this 
       * page.  If the pin_count was 0 before the call, the page was a 
       * replacement candidate, but is no longer a candidate.
       * If the page is not in the pool, choose a frame (from the 
       * set of replacement candidates) to hold this page, read the 
       * page (using the appropriate method from {\em diskmgr} package) and pin it.
       * Also, must write out the old page in chosen frame if it is dirty 
       * before reading new page.  (You can assume that emptyPage==false for
       * this assignment.)
       *
       * @param Page_Id_in_a_DB page number in the minibase.
       * @param page the pointer poit to the page.
       * @param emptyPage true (empty page); false (non-empty page)
       */

      public void pinPage(PageId pin_pgid, Page page, boolean emptyPage) {};


      /**
       * Unpin a page specified by a pageId.
       * This method should be called with dirty==true if the client has
       * modified the page.  If so, this call should set the dirty bit 
       * for this frame.  Further, if pin_count>0, this method should 
       * decrement it. If pin_count=0 before this call, throw an exception
       * to report error.  (For testing purposes, we ask you to throw
       * an exception named PageUnpinnedException in case of error.)
       *
       * @param globalPageId_in_a_DB page number in the minibase.
       * @param dirty the dirty bit of the frame
       */

      public void unpinPage(PageId PageId_in_a_DB, boolean dirty) {};


      /** 
       * Allocate new pages.
       * Call DB object to allocate a run of new pages and 
       * find a frame in the buffer pool for the first page
       * and pin it. (This call allows a client of the Buffer Manager
       * to allocate pages on disk.) If buffer is full, i.e., you 
       * can't find a frame for the first page, ask DB to deallocate 
       * all these pages, and return null.
       *
       * @param firstpage the address of the first page.
       * @param howmany total number of allocated new pages.
       *
       * @return the first page id of the new pages.  null, if error.
       */

      public PageId newPage(Page firstpage, int howmany) {};

            
      /**
       * This method should be called to delete a page that is on disk.
       * This routine must call the method in diskmgr package to 
       * deallocate the page. 
       *
       * @param globalPageId the page number in the data base.
       */

      public void freePage(PageId globalPageId) {};


      /**
       * Used to flush a particular page of the buffer pool to disk.
       * This method calls the write_page method of the diskmgr package.
       *
       * @param pageid the page number in the database.
       */

      public void flushPage(PageId pageid) {};

      /** Flushes all pages of the buffer pool to disk
       */

      public void flushAllPages() {};


      /** Gets the total number of buffers.
       *
       * @return total number of buffer frames.
       */

      public int getNumBuffers() {};


      /** Gets the total number of unpinned buffer frames.
       *
       * @return total number of unpinned buffer frames.
       */

      public int getNumUnpinnedBuffers() {};

    };
    

 
  Internal Design

The buffer pool is a collection of frames (page-sized sequence of main memory bytes) that is managed by the Buffer Manager. Conceptually, it should be stored as an array bufPool[numbuf] of Page objects. However, due to the limitation of Java language, it is not feasible to declare an array of Page objects, and later on write string (or other primitive values) to the defined Page directly. To circumvent this problem, Page is defined as an array of bytes. We deal with buffer pool at the byte array level. Therefore, when one implements the constructor for the BufMgr class, you should declare the buffer pool as bufpool[numbuf][page_size]. Note that the size of minibase pages is defined in the interface GlobalConst of the global package. Before jumping into coding, please be certain to understand how a Page object is defined and manipulated in Java Minibase.

In addition, one should maintain an array bufDescr[numbuf] of descriptors, one per frame. Each descriptor is a record with the following fields:

  • page_number,
  • pin_count, and
  • dirtybit.

The pin_count field is an integer, page_number is a PageId object, and dirtybit is a boolean. This describes the page that is stored in the corresponding frame. A page is identified by a page_number that is generated by the DB class when the page is allocated, and is unique over all pages in the database. The PageId type is defined as an integer type.

When a pin request is received, the BP manager needs an efficient way to determine whether the page is already in the buffer pool. To handle this, you should implement a simple hash table, or map. With an input of page_number, the hash table should return the frame_number that the page occupies (or "nil" if the page is not present). Of course, this hash table should be main-memory based. Yes, you may use available Java classes (java.utils) for this.

When a page is requested, the buffer manager should do the following:

  1. Check the buffer pool (by using the hash table) to see if it contains the requested page. If the page is not in the pool, it should be brought in as follows:
    1. Choose a frame for replacement, using the LRU replacement policy.
    2. If the frame chosen for replacement is dirty, flush it (i.e., write out the page that it contains to disk, using the appropriate DB class method).
    3. Read the requested page (again, by calling the DB class) into the frame chosen for replacement; the pin_count and dirtybit for the frame should be initialized to 0 and FALSE, respectively.
    4. Delete the entry for the old page from the Buffer Manager's hash table and insert an entry for the new page. Also, update the entry for this frame in the bufDescr array to reflect these changes.
  2. Pin the requested page by incrementing the pin_count in the descriptor for this frame, and return a pointer to the page to the requestor.

Recall that the LRU replacement policy is as follows. (It is the same as the textbook describes, so follow that.) Whenever a page is unpinned to a pin_count of zero, its associated frame is placed into a priority queue. (Really, a "plain" queue works for this. There is nothing "priority" about it.) When a frame is needed to bring in a page not already in the buffer pool, choose as follows: first, a free frame (a frame than currently holds no page) is chosen, if available; else, the frame at the front of the queue is selected, which contains the page that has been least recently used.

Note that you must use a queue data-structure (class) that allows you to remove efficiently a frame from it when that frame's page becomes pinned again. We need the buffer pool manager to be fast, and candidate frame selection is a core operation. So we need frame selection, and the management of the queue, to be fast. I shall be grading whether you implement this part reasonably.

 
  Where to Find Makefiles, Code, etc.

Please copy all the files from /cs/dept/course/2009-10/F/4411/bufmgr/src/, on red.cs.yorku.ca or any of the York PRISM machines, into a local directory of your own. You can do this easily, for instance, by saying

% cp -rp /cs/dept/course/2009-10/F/4411/bufmgr/src bufmgr

This makes a copy into a directory called bufmgr within your current directory. The contents are:

  • bufmgr/
    • You should keep all your code for bufmgr package in this directory. A sample Makefile is provided for compiling your project. You will have to set up any dependencies by editing this file. You can also design your own Makefile. Whatever you do, please make sure that the classpath is set to the one provided in the original Makefile.

      Here is a template file to get you started: BufMgr.java.

  • diskmgr/
    • You should look over the code for the diskmgr package before you implement your bufmgr package. Detailed descriptions of the files are not included, but the javadoc (java documentation) of the packages describes things well.

      This directory is just for your convenience and reference. The code in this directory is not linked when you compile your code! Rather the version (identical) in the JAR that contains all the Minibase base code is linked instead.

  • tests/
    • Makefile, TestDriver.java, BMTest.java: Buffer manager test driver program. Note that you use this Makefile to run the test suite on your bufmgr code.

You may find other useful information by reading the java documentation on other packages, such as the global package and the chainexception package.

 
  Error Protocol

Although the Throwable class in Java contains a snapshot of the execution stack of its thread at the time it was created and also a message string that gives more information about the error (exception), Minibase maintains a copy of its own stack, in order to have more control over the error handling.

The chainexception package handles the Minibase exception stack. Every exception created in the bufmgr package should extend the ChainException class. The exceptions are thrown according to the following rule:

  • Error caused by an exception caused by another layer:

    For example: (when try to pin page from diskmgr layer)

            try {
              SystemDefs.JavabaseBM.pinPage(pageId, page, true);
            }
            catch (Exception e) {
              throw new DiskMgrException(e, "DB.java: pinPage() failed");
            }
            

  • Error not caused by exceptions of others, but needs to be acknowledged.

    For example: (when try to unpin a page that is not pinned)

            if (pin\_count == 0) {
              throw new PageUnpinnedException (null, "BUFMGR: PAGE_NOT_PINNED.");
            }
            

Basically, the ChainException class keeps track of all the exceptions thrown accross the different layers. Any exceptions that you decide to throw in your bufmgr package should extend the ChainException class.

For testing purposes, we ask you to throw the following exceptions in case of error (use the exact same name, please):

  • BufferPoolExceededException: Throw a BufferPoolExceededException when try to pin a page to the buffer pool with no unpinned frame left.
  • PagePinnedException: Throw a PagePinnedException when try to free a page that is still pinned.
  • HashEntryNotFoundException: Throw a HashEntryNotFoundException when page specified by PageId is not found in the buffer pool.

Feel free to throw other new exceptions as you see fit. But make sure that you follow the error protocol when you catch an exception. Also, think carefully about what else you need to do in the catch phase. Sometimes you do need to undo certain previous operations when a failure happens.

 
  What to Turn In (and When)

You will use submit to submit your code, together with copies of the output produced by running the tests provided.

For documentation, you do not need to produce javadoc, and you do not need to comment extensively, line-by-line. You should comment your code though, commenting the methods, commenting the fields, and placing relevant comments in the code where things would not be clear otherwise.

For coding style, choose a reasonable indentation convention and be consistent. Name your variables with understandable names. And follow general good coding practise. I will not grade the style component with respect to specific style guidelines, but rather with respect to general good coding practise.

A portion of the project grade will be based on coding style. Namely, your code should be readable.

 
  More Information

See the FAQ (Frequently Asked Questions) for the buffer pool manager project for more information.

Read over the FAQ to start. There is already quite a bit covered in it. Not everything in the FAQ will make sense to you in the beginning. Don't worry about that. Each of those issues will become clear as your project proceeds. Refer back to the FAQ as needed.

Of course, send reasonable questions my way, as needed. Pertinent questions sent my way regarding the project will make their way into the FAQ. So check the FAQ online periodically for updates.

You may discuss the project with others in the class. The work you turn in has to be your own.

Parke Godfrey
With much thanks and credit to the many folks
at the University of Wisconsin
who built Minibase and designed these projects.