In this lab, you are asked to implement a Buffer Manager. We are working our way up the stack of the DB architecture!
See previous labs.
See previous labs.
In this lab, you are asked to implement a Buffer Manager. You are strongly encouraged to review your notes from class and re-read the textbook (Cow book, especially Ch. 9.4).
In this lab you are asked to complete BufferManagerImpl, an implementation of the BufferManager interface. Your implementation must respect the requirement that the size of the buffer pool never exceeds a specified size. Therefore, it must implement a replacement policy that determines which page to evict when the buffer pool is full.
Note: the unit test for this lab uses the idea of “mock objects.” In particular, BufferManagerTest has a MockDiskManager that mimics the behavior of a real disk manager for the purpose of testing your buffer manager (which must make calls to a disk manager to read/write pages). In fact, the mock disk manager even writes mock pages! In a future lab, I will provide a real disk manager and your buffer manager will eventually read/write your slotted pages to/from disk.
You are expected to modify these files:
BufferManagerImpl.javaYou are expected to read, use, but not modify the remaining files.
Here is a suggested sequence of tasks. You are free to choose a different order provided that you complete all of them.
Task 0 Read the javadoc comments in BufferManager. This is the interface that your BufferManagerImpl is expected to implement.
Tasks 1-10 In BufferManagerImpl, implement the 10 methods in the order listed. The unit tests in BufferManagerTest roughly follow this order, so each time you implement a method you should be able to pass additional tests. In your initial implementation, pretend that the buffer pool has unlimited order (i.e., you never need to evict a page). With this approach, you should be able to pass every test except those with the word “evict” in them.
Task 11 Now it’s time to face reality: your Buffer Pool has finite order. Its order is measured in terms of the number of pages it can hold in its buffer pool and this number is specified by the numPages parameter that is passed into the constructor. Therefore, once the pool is full, the next request to pin a page will force an eviction according to your replacement policy. I suggest you start by implementing a dead simple eviction strategy: find the first page that is a candidate for replacement and evict it. With this strategy you should be able to pass the remaining tests in BufferManagerTest.
Task 12 Implement a more intelligent and efficient eviction strategy. You have some flexibility here and I encourage you to have some fun with this. There are some interesting data structure challenges here… you know, the kind of stuff that engineers like to ask about in interviews for tech jobs :-).
During the next code review, your grade will be a function of the level of difficulty of what you attempt and the quality of your resulting solution. Very roughly, here are my guidelines:
pinPage or page eviction will require time roughly linear in the size of the buffer pool.Regardless of which option you choose, you must include a comment in your code that explains your implementation. My suggestion is that you write a method called evictPage and put the documentation in the javadoc for that method.
The milestone for this lab will be to complete the above tasks and pass the tests described above. In addition, please include a javadoc description of your eviction strategy.
Upload your files to Gradescope.