Preface
This experiment has two tasks ： Clock replacement algorithm and buffer pool manager , They correspond to each other ClockReplacer and BufferPoolManager class ,BufferPoolManager Will use ClockReplacer Select the page to be swapped out , And pass DiskManager Write the swapped out page to the database file . The following describes the implementation process of these two classes .
Code implementation
If you clone directly Bustub Warehouse , Get is fall 2021 Experimental code , about fall 2019, Can be commit Switch to 5972018: Fix typo in type.cpp(#66). But this introduces a pit , It's the need to put build_support/gtest_CMakeLists.txt.in Is changed to ：
cmake_minimum_required(VERSION 3.8)
project(googletest-download NONE)
include(ExternalProject)
ExternalProject_Add(googletest
GIT_REPOSITORY [email protected]:google/googletest.git
GIT_TAG main
SOURCE_DIR "${CMAKE_BINARY_DIR}/googletest-src"
BINARY_DIR "${CMAKE_BINARY_DIR}/googletest-build"
CONFIGURE_COMMAND ""
BUILD_COMMAND ""
INSTALL_COMMAND ""
TEST_COMMAND ""
)
The main changes here are GIT_TAG by main, because googletest The warehouse seems to be master The branch was renamed main 了 .
ClockReplacer class
The project homepage introduces the implementation of this class ：
The size of the
ClockReplaceris the same as buffer pool since it contains placeholders for all of the frames in theBufferPoolManager. However, not all the frames are considered as in theClockReplacer. TheClockReplaceris initialized to have no frame in it. Then, only the newly unpinned ones will be considered in theClockReplacer. Adding a frame to or removing a frame from a replacer is implemented by changing a reference bit of a frame. The clock hand initially points to the placeholder of frame 0. For each frame, you need to track two things: 1. Is this frame currently in theClockReplacer? 2. Has this frame recently been unpinned (ref flag)?In some scenarios, the two are the same. For example, when you unpin a page, both of the above are true. However, the frame stays in the
ClockReplaceruntil it is pinned or victimized, but its ref flag is modified by the clock hand.
A simple translation , Namely ClockReplacer Class maintains a frame Set , The collection size is consistent with the buffer pool size . Due to some frame Being accessed by another thread , these frame Of pin count （ Equal to the number of threads accessing the frame ） Will be greater than the 0, Now these frame It is not allowed to be replaced , To put it another way , That's all. frame be not in ClockReplacer In the set of maintenance . For those that can be replaced frame, It must meet two conditions ：
pin countby 0, That is, the frame is inClockReplacerin . Once the... Of a framepin countGreater than zero , Will be removedClockReplacer（ callClockReplacer::Pin）reference bitbyfalse, That is, the frame has not been accessed recently . aboutpin countJust become 0 And be joinedClockReplacerIn terms of frames , Because it has just been visited , So itsreference bitbytrue（ callClockReplacer::Unpin）
As for the process of clock replacement algorithm , In fact, it is from... In order frame Select a process that meets the above exchange conditions from the set . In order to maintain the position of the clock pointer and ensure thread safety , You need to add a clock pointer member clock_hand_ And a read-write lock mutex_, Frame set frames_ Each element of the represents whether the frame is in ClockReplacer And reference bit：
/**
* ClockReplacer implements the clock replacement policy, which approximates the Least Recently Used policy.
*/
class ClockReplacer : public Replacer {
public:
/**
* Create a new ClockReplacer.
* @param num_pages the maximum number of pages the ClockReplacer will be required to store
*/
explicit ClockReplacer(size_t num_pages);
/**
* Destroys the ClockReplacer.
*/
~ClockReplacer() override;
bool Victim(frame_id_t *frame_id) override;
void Pin(frame_id_t frame_id) override;
void Unpin(frame_id_t frame_id) override;
size_t Size() override;
private:
frame_id_t clock_hand_ = 0;
std::vector<std::tuple<bool, bool>> frames_;
std::shared_mutex mutex_;
};
Each method is defined as follows , It uses std::lock_guard To ensure that the code is abnormally safe ：
ClockReplacer::ClockReplacer(size_t num_pages) {
for (size_t i = 0; i < num_pages; ++i) {
frames_.push_back(std::make_tuple(false, false));
}
}
ClockReplacer::~ClockReplacer() = default;
bool ClockReplacer::Victim(frame_id_t *frame_id) {
if (Size() == 0) {
return false;
}
std::lock_guard<std::shared_mutex> lock(mutex_);
while (true) {
auto &[contains, ref] = frames_[clock_hand_];
if (contains) {
if (ref) {
ref = false;
} else {
*frame_id = clock_hand_;
contains = false;
return true;
}
}
clock_hand_ = (clock_hand_ + 1) % frames_.size();
}
}
void ClockReplacer::Pin(frame_id_t frame_id) {
assert(static_cast<size_t>(frame_id) < frames_.size());
std::lock_guard<std::shared_mutex> lock(mutex_);
auto &[contains, ref] = frames_[frame_id];
contains = false;
ref = false;
}
void ClockReplacer::Unpin(frame_id_t frame_id) {
assert(static_cast<size_t>(frame_id) < frames_.size());
std::lock_guard<std::shared_mutex> lock(mutex_);
auto &[contains, ref] = frames_[frame_id];
contains = true;
ref = true;
}
size_t ClockReplacer::Size() {
std::shared_lock<std::shared_mutex> lock(mutex_);
size_t size = 0;
for (auto &[contains, ref] : frames_) {
size += contains;
}
return size;
}
Enter the command at the terminal ：
mkdir build
cd build
cmake ..
make clock_replacer_test
./test/clock_replacer_test
The test results are as follows ：
BufferPoolManager class
Here, the mutex lock is replaced by a read-write lock , To protect page_table_、pages_ and free_list_, At the same time, an auxiliary function is introduced GetVictimFrameId()：
class BufferPoolManager {
// Omitted code
protected:
/**
* select a victim frame from the free list or replacer.
* @return the frame id, INVALID_PAGE_ID if the victim could not be found
*/
frame_id_t GetVictimFrameId();
/** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
std::shared_mutex latch_;
};
BufferPoolManager Class requires us to implement five functions ：
FetchPageImpl(page_id)NewPageImpl(page_id)UnpinPageImpl(page_id, is_dirty)FlushPageImpl(page_id)DeletePageImpl(page_id)FlushAllPagesImpl()
The following functions will be implemented one by one .
FetchPageImpl(page_id)
This function implements the main functions of the buffer pool ： Provide the specified to the upper layer page. The buffer pool manager starts with page_table_ Search for page_id Does the key exist ：
- If it exists, it is based on
page_idCorrespondingframe_idFrom buffer poolpages_Take outpage - If it doesn't exist, go through
GetVictimFrameId()Function to select the frame to be swapped out , This function starts withfree_list_Find the empty bit of buffer pool in , If you can't find a vacant seat, you have to rely on the previous section to realizeClockReplacerSelect the wronged leader who has been replaced
The specific code is as follows ：
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
// 1. Search the page table for the requested page (P).
std::lock_guard<std::shared_mutex> lock(latch_);
Page *page;
// 1.1 If P exists, pin it and return it immediately.
auto it = page_table_.find(page_id);
if (it != page_table_.end()) {
page = &pages_[it->second];
if (page->pin_count_++ == 0) {
replacer_->Pin(it->second);
}
return page;
}
// 1.2 If P does not exist, find a replacement page (R) from either the free list or the replacer.
// Note that pages are always found from the free list first.
frame_id_t frame_id = GetVictimFrameId();
if (frame_id == INVALID_PAGE_ID) {
return nullptr;
}
// 2. If R is dirty, write it back to the disk.
page = &pages_[frame_id];
if (page->IsDirty()) {
disk_manager_->WritePage(page->page_id_, page->data_);
}
// 3. Delete R from the page table and insert P.
page_table_.erase(page->GetPageId());
page_table_[page_id] = frame_id;
// 4. Update P's metadata, read in the page content from disk, and then return a pointer to P.
disk_manager_->ReadPage(page_id, page->data_);
page->update(page_id, 1, false);
replacer_->Pin(frame_id);
return page;
}
frame_id_t BufferPoolManager::GetVictimFrameId() {
frame_id_t frame_id;
if (!free_list_.empty()) {
frame_id = free_list_.front();
free_list_.pop_front();
} else {
if (!replacer_->Victim(&frame_id)) {
return INVALID_PAGE_ID;
}
}
return frame_id;
}
The above code also uses a Page::update Auxiliary function , Used to update the page Metadata ：
/**
* update the meta data of page
* @param page_id the page id
* @param pin_count the pin count
* @param is_dirty is page dirty
* @param reset_memory whether to reset the memory of page
*/
void update(page_id_t page_id, int pin_count, bool is_dirty, bool reset_memory = false) {
page_id_ = page_id;
pin_count_ = pin_count;
is_dirty_ = is_dirty;
if (reset_memory) {
ResetMemory();
}
}
NewPageImpl(page_id)
This function inserts a new page into the buffer pool , If all the pages in the buffer pool are being accessed by threads , Insert the failure , Otherwise, it depends on GetVictimFrameId() Calculate the insertion position ：
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
// 0. Make sure you call DiskManager::AllocatePage!
std::lock_guard<std::shared_mutex> lock(latch_);
// 1. If all the pages in the buffer pool are pinned, return nullptr.
if (free_list_.empty() && replacer_->Size() == 0) {
*page_id = INVALID_PAGE_ID;
return nullptr;
}
// 2. Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
frame_id_t frame_id = GetVictimFrameId();
if (frame_id == INVALID_PAGE_ID) {
*page_id = INVALID_PAGE_ID;
return nullptr;
}
// 3. Update P's metadata, zero out memory and add P to the page table.
Page *page = &pages_[frame_id];
if (page->IsDirty()) {
disk_manager_->WritePage(page->page_id_, page->data_);
}
*page_id = disk_manager_->AllocatePage();
page_table_.erase(page->GetPageId());
page_table_[*page_id] = frame_id;
// Need to put dirty bit Set to false Can pass IsDirty The test case
page->update(*page_id, 1, true, true);
// 4. Set the page ID output parameter. Return a pointer to P.
return page;
}
DeletePageImpl(page_id)
This function deletes a... From the buffer pool and database files page, And its page_id Set to INVALID_PAGE_ID：
bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
// 0. Make sure you call DiskManager::DeallocatePage!
std::lock_guard<std::shared_mutex> lock(latch_);
// 1. search the page table for the requested page (P).
// If P does not exist, return true.
auto it = page_table_.find(page_id);
if (it == page_table_.end()) {
return true;
}
// 2. If P exists, but has a non-zero pin-count, return false. Someone is using the page.
Page &page = pages_[it->second];
if (page.pin_count_ > 0) {
return false;
}
// 3. Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
disk_manager_->DeallocatePage(page_id);
page_table_.erase(page_id);
page.update(INVALID_PAGE_ID, 0, false, true);
free_list_.push_back(it->second);
return true;
}
UnpinPageImpl(page_id, is_dirty)
This function is used to reduce the number of references to a page pin count, When pin_count by 0 You need to add it to ClockReplacer in ：
bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
std::lock_guard<std::shared_mutex> lock(latch_);
auto it = page_table_.find(page_id);
if (it == page_table_.end()) {
return false;
}
Page &page = pages_[it->second];
if (page.pin_count_ <= 0) {
return false;
}
// add page to replacer when the pin count is 0
page.is_dirty_ |= is_dirty;
if (--page.pin_count_ == 0) {
replacer_->Unpin(it->second);
}
return true;
}
FlushPageImpl(page_id)
If the buffer pool page Has been modified , You need to write it to disk to keep it synchronized ：
bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
// Make sure you call DiskManager::WritePage!
std::shared_lock<std::shared_mutex> lock(latch_);
auto it = page_table_.find(page_id);
if (it == page_table_.end()) {
return false;
}
// write page to disk if it's dirty
Page &page = pages_[it->second];
if (page.IsDirty()) {
disk_manager_->WritePage(page_id, pages_[it->second].data_);
page.is_dirty_ = false;
}
return true;
}
FlushAllPagesImpl()
This function will buffer all page Write to disk ：
void BufferPoolManager::FlushAllPagesImpl() {
// You can do it!
std::lock_guard<std::shared_mutex> lock(latch_);
for (size_t i = 0; i < pool_size_; ++i) {
Page &page = pages_[i];
if (page.page_id_ != INVALID_PAGE_ID && page.IsDirty()) {
disk_manager_->WritePage(i, page.data_);
page.is_dirty_ = false;
}
}
}
test
Input instructions at the terminal ：
cd build
make buffer_pool_manager_test
./test/buffer_pool_manager_test
The test results are as follows ：
summary
This experiment examines students' understanding of concurrency and STL The degree of mastery , Because the implementation steps are listed in the comments （ What's the trouble You can do it! notes ）, So the code can be written smoothly , above ~~
CMU15445 (Fall 2019) And Project#1 - Buffer Pool More related articles in detail
- Protocol Buffer Technical details ( language norm )
Protocol Buffer Technical details ( language norm ) This series of Blog The main body of the content mainly comes from Protocol Buffer Official documents of , And the code sample is extracted from a company internal project currently under development Demo. The purpose of this ...
- Protocol Buffer Technical details ( Data encoding )
Protocol Buffer Technical details ( Data encoding ) I've published three articles about Protocol Buffer Technology blog , The first one introduces Protocol Buffer The language standard of , The latter two are based on C++ and J ...
- Protocol Buffer Technical details (Java example )
Protocol Buffer Technical details (Java example ) This article Blog And the last one (C++ example ) Basically the same , It's just for our team Java The engineer , After all, the front end of our project is based on Android Developed , And we develop ...
- Protocol Buffer Technical details (C++ example )
Protocol Buffer Technical details (C++ example ) This article Blog Still with Google The official documents of , The code example is completely taken from the one we are developing Demo project , Through previous attempts , I feel this kind of combination is quite ...
- CMU-15445 LAB1:Extendible Hash Table, LRU, BUFFER POOL MANAGER
summary A new pit has been opened recently ,CMU Of 15445, This is a course on database . I follow Yes. 2018 Course of , because 2018 In, the government stopped opening the experimental source code to the outside world , So I used 2017 The experiment of , But it's not a big problem , Basic content ...
- iOS Study ——iOS project Project and Targets Configuration details
Recently began to learn complete iOS Project development process and ideas , In the actual project development process , We usually need version control and management of project code and data , It's commonly used SVN perhaps Github Code version control and project management . We iOS Project development ...
- shared pool Detailed explanation
Shared pool shared pool The concept of user submitted commands : analysis . The process of executing the parsing of user commands is quite complex , It should consider various possible exceptions, such as SQL The object involved in the statement does not exist . The submitted user does not have permission and so on, but also needs to test ...
- Project Server 2010 Configuration details
At the request of the company , Project management needs to be strengthened . Arrange for me to learn from Microsoft Project How to manage the project , And build such a project management tool on the company server . It can be accessed through the browser . I use a single computer Project Pr ...
- thorough Golang And sync.Pool Detailed explanation
We usually use golang To build applications in high concurrency scenarios , But because of golang The built-in GC The mechanism will affect the performance of the application , In order to reduce the GC,golang Provides a mechanism for object reuse , That is to say sync.Pool Object pool . sync.Pool ...
- [Project] SpellCorrect Source details
The Project The original application scenario is to intelligently correct an incorrect product name in the e-commerce website , such as iphoae The error correction is iphone. The following version simplifies it , Project source code address see my github:https:// ...
Random recommendation
- ul li Set up a row , And remove it li Dot before
Results the preview :http://hovertree.com/texiao/css/ How to use CSS Make a horizontal menu Give Way ul li Horizontal arrangement and dot processing Let's create an unordered list , To build the structure of the menu . The code is : <ul& ...
- Android When the project is deployed , happen AndroidRuntime：android.view.InflateException: Binary XML file line #168: Error inflating class error
This mistake also made me tangled for a day , The projects written at that time were running normally on the Android virtual machine , So when I deploy to Android phones , When you click the login button to jump to the main user interface, you will directly end the operation and return to the login interface . at that time , I went through my code , and ...
- ubuntu15.10 perhaps 16.04 perhaps ElementryOS Next use Dotnet Core
Here we won't talk about installation , The lack of libicu52 Its installation . Use after installation dotnet restore perhaps build Will fail , One is the compilation of newspapers dll Not suitable for the current system , Second, compile to ubuntu16.04 Some... Will be generated under the folder ...
- HDU 5319 Painter ( simulation )
The question : A painter draws a picture , Yes 3 A pen of different colors ,R.G.B.R as '\',B as '/',G Look at the overlap of the two ( I.e. fork ). What I give is a matrix , There's only... In the matrix 4 Symbols , except 3 There are three colors and '.', Means not painted . Ask the minimum cost ...
- CVTE Embedded Software Engineer Two sides
Last night, I received a two-sided notice , Excited - The next day ahead of schedule 20 Minutes to the designated place , Then take a bus to CVTE headquarters , It seems that not many people brush off the written test . As soon as we got off the bus, we were taken to the company cinema , Listen to the concert . ha-ha , That's interesting , There is a beautiful ...
- 《 I and Android A story that has to be told -1- Stick up your mind 》
The product needs to iterate , The same with people , Self renewal , To make progress , Enter new fields , Stick up your mind . By the way, record the potholes on the new road
- oracle SQL Statement to get the data of this week, this month and this year
-- From Monday to Sunday in China Abroad is from Sunday to Saturday select to_char(sysdate-1,'D') from dual;-- Take the domestic day of the week Take out the week abroad by subtracting one -- Take the data of this week ,)+) an ...
- html Style sheets
<html><body><table border="1"> <tr height="20px"> &l ...
- C# Connect sqlserver windows and sqlserver Two connection strings for authentication
//sql server Authentication Connection string private string ConnstrSqlServer = "server= Server name ;uid= Login name ;pwd= The login password ;datab ...
- JS Ajax The asynchronous request sends more list data []
Still struggling to write code , I won't go into details here , Throw the question directly : As shown in the figure : front end ajax When requesting to send data to the back end , to key Added [] There are many reasons that cannot be found , It says resolvent : For the time being, record it like this , Easy to find next time , Okay ...
![[untitled]](/img/96/7f26614bbdcce71006e38ee34ab216.jpg)
