代写CMPT 454、代做Buffer Pool、代写C++编程语言、代做C++

日期：2019-06-10 09:54

CMPT 454 Project Milestone 1: Buffer Pool

Total marks: Total marks: 100

Overall percentage: Overall percentage: 16%

Due:: Jun 11 (23:59)

In this project milestone, you are going to implement a buffer manager discussed in the class. You should use C++11 to Qnish this

project. If you use more recent C++ standards (e.g., C++17), make sure to update the required standard in CMakeLists.txt. See

Tutorial 2 for a quick overview of C++11 features. If your code (as a result of using more recent C++ standards) requires a speciQc

version of GCC/Clang, please document it in your submission and make corresponding changes in your CMakeLists.txt Qle. You are

not allowed to use external libraries other than standard C++ library. All code must run on a Linux machine. We will grade your code

on a Linux machine.

Note: It is very important that you are familiar with the provided codebase to be able to Qnish the required tasks (described later).

Make sure you understand the following two sections before attempting the problems in Section 3. Also check out Tutorial 1 for

basic information on project architecture and building and working on the project code.

1. Setting up the Base Code

We have prepared the basic code skeleton for you to start with. Assuming you have set up your repo as in Project Milestone 0,

issue the following commands to get it in your code repo:

$ git fetch --all

$ git merge base/master --allow-unrelated-histories

1.1 Code Structure

Now you should see a new yase_internal.h header Qle and a BufferManager directory in which there are multiple header (.h)

and source (.cc) Qles:

buffer_manager.{h,cc}: buffer manager implementation, including page frame management, replacement algorithm.

table.{h,cc}: user-visible table abstraction. The test progam uses structures deQned and implemented in these Qles to

manipulate data.

file.{h,cc}: implements storage Qles that hold data for tables. Each table corresponds to a Qle.

page.{h,cc}: data and directory page abstractions.

1.2 Building the Code

Dependencies: Dependencies: The code depends on the glog, g_ags, gtest libraries for logging, handling command-line parameters and testing,

and CMake for conQguring and building. You will need to have these libraries installed in your system (or build your own). If you are

using CSIL server, then all these packages should have already been installed. Each Linux distribution has its own package

manager so you will need to Qnd out yourself. Below are guidelines for Arch Linux and Ubuntu.

For Arch Linux users: The following command will get you all set directly: $sudo pacman -S cmake gtest gflags googleglog.

Proceed to the "Building the code" section.

For Ubuntu users: To install these libraries in your own Ubuntu system, issue the following commands:

$ sudo apt-get install cmake

$ sudo apt-get install libgoogle-glog-dev libgflags-dev libgtest-dev // Note the 'dev' suffix

To use gtest on Ubuntu, you need to do some extra work to build gtest by yourself as the gtest packages in Ubuntu only give source

code stored under /usr/src/gtest. To do so, follow the steps below:

$ mkdir ~/gtest && cd ~/gtest // Create a gtest folder in your own directory

$ cd gtest

$ cmake -DCMAKE_BUILD_TYPE=Release -DBUILD_SHARED_LIBS=on /usr/src/gtest // Build a shared library

$ make -jN // Replace N with the number of threads you'd like to use for compiling

Then issue sudo make install if you are using your own machine. If you are using CSIL machine, you may skip this step, and

change your top-level CMakeLists.txt to include the library install path using -L/home/[username]/gtest when linking with

gtest (i.e., tell the compiler where to Qnd libgtest.so). This can be done by adding the following to the top-level CMakeLists.txt:

link_directories("/home/[username]/gtest"). Finally, in some environments you may need to also add -lpthread to your

CMakeLists.txt (e.g., by adding a new line link_libraries("-lpthread -pthread").

Building the code: Building the code:Once you have all the dependencies set up, use the following commands to build the project:

$ mkdir build && cd build // Create a separate directory to build the project

$ cmake -DCMAKE_BUILD_TYPE=[Debug/Release/RelWithDebInfo] ..

$ make -jN

2. YASE Architecture

We design YASE to be a row-store that is capable of storing Qxed-length records (size can be speciQed by the user) using slotted

pages. Free and occupied pages are tracked by directory pages. Each table is backed by a single Qle that stores both directory and

data pages.

Supported operations: Supported operations: Insert, delete, read, and update a record. The BufferManager/table.{h,cc} Qles deQne these uservisible

interfaces. The insert operation will return the record ID (RID) of the inserted record, the other operations require an RID as

the input and returns true if the operation succeeded. RID and page ID are deQned in yase_internal.h.

Table and Space Management: Table and Space Management: Each table is backed by a Qle (represented by the File structure deQned in file.{h,cc}). We

use directory pages to manage pages in the table. Upon initialization, the user speciQes the maximum amount of data that can be

stored by the table (see Table's constructor in table.h). Since the maximum size of a Qle is known, the number of directory

pages is also Qxed. In each Qle, we store all directory pages in the beginning of the Qle, and each directory entry includes two Qelds:

free_slots and allocated, which represents the number of free slots in the corresponding data page and whether the data

page was allocated.

Data Page: Data Page: Data pages follow the bit array design where at the end of the page is a header area that includes (1) record count and

(2) a bit array (one bit per slot to indicate whether the slot is vacant). Data records are stored one after another starting from the

beginning of the page. To delete a record, we simply reset the slot's bit in the bit array to 0 and decrement record count, then

increment the free_slots Qeld in the corresponding directory page.

Page, File, Record IDs: Page, File, Record IDs: RIDs are 8-byte integers subdivided into three parts (Qle ID, page ID and slot ID) occupying different parts

of the 8-byte (64 bits). The Qle ID indicates which Qle (table) this record belongs to; the page ID indicates which page inside the Qle

stores the record; the slot ID indicates the slot in the page storing the record. File IDs are 16-bit integers, while both page and slot

IDs are 24-bit long. Detailed deQnitions for PageID and RID can be found in yase_internal.h. An important note is that page IDs

are local to Qles, i.e., page IDs run from 0 to maximum for each different Qle ID. Similarly, slot IDs are page-local, running from 0 to

maximum for each different page.

3. Tasks

There are three tasks in this project milestone. Storage-level functionality (insert/delete/read/update) are already provided in the

base code. You will need to Qnish the missing buffer pool functionality based on the given code. Since the code is missing in

functionality, buffer_manager_test will not pass until you correctly implement the required components.

3.1. Task 1 - Buffer Pool Structure [40 marks]

The buffer pool is deQned by the BufferManager class in buffer_manager.h. First, Qnish the constructor function to initialize

the buffer pool with an array of page frames (described by the Page structure). Detailed steps are provided in the code. Also Qnish

the destructor function to free the page frames allocated upon class destruction.

Next, follow the approach discussed in class (slide 5 of Storage Management - Part 2), set up a PageID - Page Frame mapping.

Note that PageIDs are local to each Qle. Your buffer manager should support multiple tables. That is, you should setup another

FileID - File object mapping in order to be able to process pages belonging to different table.

Hint: For both mappings, you may use std::map or std::unorderd_map. An example is included in the code at lines 83-87 of

buffer_manager.h

Next, implement the PinPage and UnpinPage functions that pins and unpins a page with a given page ID. PinPage is used by the

Table and File classes to load a page in the buffer pool in order to modify (e.g., insert record) it. PinPage's signature is Page

*PinPage(PageID page_id, bool new_page = false);. The return value (Page *)is a page frame that contains a page

backed by storage.

The UnpinPage function is as simple as just decrementing the pin count in the Page structure provided.

Check the buffer_manager.{h,cc} for details. You are free to modify the buffer manager code (including removing/replacing

variable/function deQnitions), but you are not allowed to change the insert/delete/read/update interfaces exported by table.h.

3.2. Task 2 - LRU Replacement Algorithm [40 marks]

Your PinPage function should use LRU to evict a page when needed. You are free to use different approaches to implement LRU.

One way is to follow the approach that is discussed in class, by using a queue of unpinned pages. A page frame (i.e., Page*) is

added to the tail of the queue when its pin count is zero. The head page on the queue will be the candidate for eviction. When

eviting a page, make sure to properly _ush the page back back using File::FlushPage.

3.3. Task 3 - Testing Your Code [20 marks]

Under the Tests directory a new test program (buffer_manager_test.cc) is given to get you started on testing your code. You

task here is to add one more test case that covers more than one table. You may follow the similar structure and operations of the

existing test, but modify it to use two different tables.

We will test your code using more complex cases so you are encouraged to use this code as a starting point and vary as many

parameters as possible to test your code.

4. Submission

You need to do two things to submit your solution:

Add a CONTRIBUTIONS Qle that documents each group member's contribution to your solution. If you are doing the project

alone, you may just indicate this in the CONTRIBUTIONS Qle.

Check in (commit and push!) your code and the CONTRIBUTIONS Qle to your project repo by the deadline.

There is no need to submit anything to CourSys (grades will be posted there, though). Make sure you are familiar with the course

policies. Especially, we do not accept late submissions or submissions by means other than speciQed here. You can get partial

marks for coding style if your code does not compile. You can (and should) also continue to work on your solutions throughout the

semester to possibly get bonus marks in the end of the semester. Sample solutions will not be provided for course project.