CMU15-445 PROJECT #1 - BUFFER POOL(实验代码,已满分)

实验说明:https://15445.courses.cs.cmu.edu/fall2020/project1

我的完整实验代码见github:https://github.com/nefu-ljw/database-cmu15445-fall2020(已通过gradescope所有测试点)

参考:https://blog.csdn.net/FEATHER2016/article/details/121248062

TASK #1 - LRU REPLACEMENT POLICY

说明

LRUReplacer的大小与缓冲池相同,因为它包含BufferPoolManager中所有帧的占位符。

LRUReplacer被初始化为没有frame。在LRUReplacer中只会考虑新取消固定的frame。

实现课程中讨论的LRU策略,即实现以下函数:

  1. Victim(T*): Replacer跟踪与所有元素相比最近最少访问的对象并删除,将其页号存储在输出参数中并返回True,为空则返回False。
  2. Pin(T):在将page固定到BufferPoolManager中的frame后,应调用此方法。它应该从LRUReplacer中删除包含固定page的frame。
  3. Unpin(T):当page的pin_count变为0时应调用此方法。此方法应将包含未固定page的frame添加到LRUReplacer。
  4. Size():此方法返回当前在LRUReplacer中的frame数量。

实现细节由您决定。您可以使用内置的STL容器。您可以假设不会耗尽内存,但必须确保操作是线程安全的。

代码

(1)src/include/buffer/lru_replacer.h,在BufferPoolManager类中添加成员变量:

class LRUReplacer : public Replacer {
 //...省略代码...
 private:
  // TODO(student): implement me!
  std::mutex mut;                                                           // 信号量
  std::list<frame_id_t> LRUlist;                                            // 双向链表,存放frame_id_t
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> LRUhash;  // 哈希表,frame_id_t->链表迭代器
  size_t max_size;                                                          // 最大容量
};

(2)src/buffer/lru_replacer.cpp,补充函数实现:

/**
 * 使用LRU策略删除一个victim frame,这个函数能得到frame_id
 * @param[out] frame_id id of frame that was removed, nullptr if no victim was found
 * @return true if a victim frame was found, false otherwise
 */
bool LRUReplacer::Victim(frame_id_t *frame_id) {
  // C++17 std::scoped_lock
  // 它能够避免死锁发生,其构造函数能够自动进行上锁操作,析构函数会对互斥量进行解锁操作,保证线程安全。
  std::scoped_lock lock{mut};
  if (LRUlist.empty()) {
    return false;
  }
  // list<int>a,那么a.back()取出的是int类型
  *frame_id = LRUlist.back();  // 取出最后一个给frame_id(对传入的参数进行修改)
  LRUhash.erase(*frame_id);    // 哈希表中删除其映射关系
  // 以上均要加*,才能改变函数外调用时传入的参数
  LRUlist.pop_back();  // 链表中删除最后一个
  return true;
}

/**
 * 固定一个frame, 表明它不应该成为victim(即在replacer中移除该frame_id)
 * @param frame_id the id of the frame to pin
 */
void LRUReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock lock{mut};
  // 哈希表中找不到该frame_id
  if (LRUhash.count(frame_id) == 0) {
    return;
  }
  auto iter = LRUhash[frame_id];
  LRUlist.erase(iter);
  LRUhash.erase(frame_id);
}

/**
 * 取消固定一个frame, 表明它可以成为victim(即将该frame_id添加到replacer)
 * @param frame_id the id of the frame to unpin
 */
void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock lock{mut};
  // 哈希表中已有该frame_id,直接退出,避免重复添加到replacer
  if (LRUhash.count(frame_id) != 0) {
    return;
  }
  // 已达最大容量,无法添加到replacer
  if (LRUlist.size() == max_size) {
    return;
  }
  // 正常添加到replacer
  LRUlist.push_front(frame_id);  // 注意是添加到首部还是尾部呢?
  // 首部是最近被使用,尾部是最久未被使用
  LRUhash.emplace(frame_id, LRUlist.begin());
}

/** @return replacer中能够victim的数量 */
size_t LRUReplacer::Size() { return LRUlist.size(); }

TASK #2 - BUFFER POOL MANAGER

说明

您需要在系统中实现BufferPoolManager。BufferPoolManager负责从DiskManager读取数据库页并将它们存储在内存中。BufferPoolManager也可以在明确指示这样做或当它需要驱逐页面为新页面腾出空间时,将脏页面写入磁盘。

为了确保您的实现与系统的其余部分一起正常工作,我们将为您提供一些已经填充的功能。您也不需要实现实际将数据读取和写入磁盘的代码(这在我们的实现中称为DiskManager)。我们将为您提供该功能。

系统中的所有内存页面都由Page对象表示。在BufferPoolManager并不需要了解这些页面的内容。但作为系统开发人员,了解Page对象只是缓冲池中内存的容器,因此并不特定于唯一页面,这一点很重要。也就是说,每个Page对象都包含一块内存,DiskManager将使用该内存块来复制它从磁盘读取的物理页的内容。当它来回移动到磁盘时,BufferPoolManager将重用相同的Page对象来存储数据。这意味着在系统的整个生命周期中,同一个Page对象可能包含不同的物理页面。该Page对象的标识符(page_id)会跟踪它包含的物理页面;如果Page对象不包含物理页,则其page_id必须设置为INVALID_PAGE_ID。

每个Page对象还为“固定”该页面的线程数维护一个计数器。您的BufferPoolManager不允许释放被固定的页面,并且跟踪每个Page对象是否脏。您的工作是在取消固定页面之前记录页面是否被修改。您的BufferPoolManager必须先将脏页的内容写回磁盘,然后才能重用该对象。

您的BufferPoolManager实现将使用您在本作业的前面步骤中创建的LRUReplacer类。使用LRUReplacer来跟踪何时访问Page对象,以便可以决定在必须释放frame以腾出空间来从磁盘复制新物理页时驱逐哪个对象。

您需要在源文件 src/buffer/buffer_pool_manager.cpp 中实现以下定义的函数:

  • FetchPageImpl(page_id)
  • NewPageImpl(page_id)
  • UnpinPageImpl(page_id, is_dirty)
  • FlushPageImpl(page_id)
  • DeletePageImpl(page_id)
  • FlushAllPagesImpl()

代码

(1)src/include/buffer/buffer_pool_manager.h,添加两个函数声明(FindVictimPage、UpdatePage):

/**
 * 主要数据结构是一个page数组(pages_),frame_id作为其下标。
 * 还有一个哈希表(page_table_),表示从page_id到frame_id的映射。
 * BufferPoolManager reads disk pages to and from its internal buffer pool.
 */
class BufferPoolManager {
 protected:
  //...省略代码...
  bool FindVictimPage(frame_id_t *frame_id);
  void UpdatePage(Page *page, page_id_t page_id, frame_id_t frame_id);

  /** Number of pages in the buffer pool. */
  size_t pool_size_;
  /** Array of buffer pool pages. 大小为pool_size_,下标为[0,pool_size_) */
  Page *pages_;
  /** Pointer to the disk manager. */
  DiskManager *disk_manager_ __attribute__((__unused__));
  /** Pointer to the log manager. */
  LogManager *log_manager_ __attribute__((__unused__));
  /** Page table for keeping track of buffer pool pages. */
  std::unordered_map<page_id_t, frame_id_t> page_table_;
  /** Replacer to find unpinned pages for replacement. 大小为pool_size_*/
  Replacer *replacer_;
  /** List of free pages. 最开始,所有页都在free_list中*/
  std::list<frame_id_t> free_list_;
  /** This latch protects shared data structures. We recommend updating this comment to describe what it protects. */
  std::mutex latch_;
};

对BufferPoolManager类中成员变量的理解:

  • pages就是缓冲区当前存的pool_size个page,可以用frame_id作为下标取出缓冲区的单个page
  • page_id表示由diskmanager分配得到的page编号,目前是id自增策略,它的大小完全有可能超过pool_size
  • frame_id表示缓冲区中的每页占的位置,它的范围只能是[0,pool_size)
  • page_table表示现在放入缓冲区的page_id与对应占的位置frame_id,若page_id在页表中即表示page在缓冲区中

(2)src/buffer/buffer_pool_manager.cpp,补充函数实现:

/*
将脏页写入磁盘,更新page元数据(data, is_dirty, page_id)和page table
(自己补充的函数)
*/
void BufferPoolManager::UpdatePage(Page *page, page_id_t page_id, frame_id_t frame_id) {
// 1 如果是脏页,一定要写回磁盘
if (page->IsDirty()) {
disk_manager_->WritePage(page->page_id_, page->data_);
}
page_table_.erase(page->page_id_);  // 删除页表中原page_id和其对应frame_id
// 2 重置page的元数据,包括data和dirty状态
page->ResetMemory();
page->is_dirty_ = false;
// 3 根据传入的参数更新page id和page table
page->page_id_ = page_id;
page_table_.emplace(page_id, frame_id);  // 更新页表为新的page_id和其对应frame_id
}
/*
从free_list或replacer中得到*frame_id;返回bool类型
(自己补充的函数)
*/
bool BufferPoolManager::FindVictimPage(frame_id_t *frame_id) {
// 1 缓冲池还有freepages(缓冲池未满),即free_list非空,直接从free_list取出一个
// 注意,在此函数中从free_list首部取出frame_id,在DeletePage函数中从free_list尾部添加frame_id
if (!free_list_.empty()) {
*frame_id = free_list_.front();
free_list_.pop_front();
return true;
}
// 2 缓冲池已满,根据LRU策略计算是否有victim frame_id
return replacer_->Victim(frame_id);
}
/**
* Fetch the requested page from the buffer pool.
* 如果页表中存在page_id(说明该page在缓冲池中),并且pin_count++。
* 如果页表不存在page_id(说明该page在磁盘中),则找缓冲池victim page,将其替换为磁盘中读取的page,pin_count置1。
* @param page_id id of page to be fetched
* @return the requested page
*/
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
// 1.     Search the page table for the requested page (P).
// 1.1    If P exists, pin it and return it immediately.
// 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.
// 2.     If R is dirty, write it back to the disk.
// 3.     Delete R from the page table and insert P.
// 4.     Update P's metadata, read in the page content from disk, and then return a pointer to P.
std::scoped_lock lock{latch_};
auto iter = page_table_.find(page_id);
// 1 该page在页表中存在(说明该page在缓冲池中)
if (iter != page_table_.end()) {
frame_id_t frame_id = iter->second;  // iter是pair类型,其second是page_id对应的frame_id
Page *page = &pages_[frame_id];      // 由frame_id得到page
replacer_->Pin(frame_id);            // pin it
page->pin_count_++;                  // 更新pin_count
return page;
}
// 2 该page在页表中不存在(说明该page不在缓冲池中,而在磁盘中)
frame_id_t frame_id = -1;
// 2.1 没有找到victim page
if (!FindVictimPage(&frame_id)) {
return nullptr;
}
// 2.2 找到victim page,将其data替换为磁盘中该page的内容
Page *page = &pages_[frame_id];
UpdatePage(page, page_id, frame_id);  // data置为空,dirty页写入磁盘,然后dirty状态置false
disk_manager_->ReadPage(page_id, page->data_);  // 注意,从磁盘文件database file中page_id的位置读取内容到新page->data
replacer_->Pin(frame_id);                       // pin it
page->pin_count_ = 1;                           // pin_count置1
return page;
}
/**
* Unpin the target page from the buffer pool. 取消固定pin_count>0的在缓冲池中的page
* @param page_id id of page to be unpinned
* @param is_dirty true if the page should be marked as dirty, false otherwise
* @return false if the page pin count is <= 0 before this call, true otherwise
*/
bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
std::scoped_lock lock{latch_};
auto iter = page_table_.find(page_id);
// 1 该page在页表中不存在
if (iter == page_table_.end()) {
return false;
}
// 2 该page在页表中存在
frame_id_t frame_id = iter->second;  // iter是pair类型,其second是page_id对应的frame_id
Page *page = &pages_[frame_id];      // 由frame_id得到page
// 2.1 pin_count <= 0
if (page->GetPinCount() <= 0) {
return false;
}
// 2.2 pin_count > 0
// 只有pin_count>0才能进行pin_count--,如果pin_count<=0之前就直接返回了
page->pin_count_--;  // 这里特别注意,只有pin_count减到0的时候才让replacer进行unpin
if (page->pin_count_ == 0) {
replacer_->Unpin(frame_id);
}
// page->is_dirty_ = is_dirty;
if (is_dirty) {
page->is_dirty_ = true;  // 这个地方要看它is_dirty到底是怎么置的
}
return true;
}
/**
* Flushes the target page to disk. 将page写入磁盘;不考虑pin_count
* @param page_id id of page to be flushed, cannot be INVALID_PAGE_ID
* @return false if the page could not be found in the page table, true otherwise
*/
bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
// Make sure you call DiskManager::WritePage!
std::scoped_lock lock{latch_};
if (page_id == INVALID_PAGE_ID) {
return false;
}
auto iter = page_table_.find(page_id);
// 1 该page在页表中不存在
if (iter == page_table_.end()) {
return false;
}
// 2 该page在页表中存在
frame_id_t frame_id = iter->second;  // iter是pair类型,其second是page_id对应的frame_id
Page *page = &pages_[frame_id];      // 由frame_id得到page
// 不管dirty状态如何,都写入磁盘
disk_manager_->WritePage(page->page_id_, page->data_);
page->is_dirty_ = false;  // 注意这句话!刷新到磁盘后,dirty要重置false
// 注意,不能调用UpdatePage,因为那个函数里面还进行了元数据的重置
// UpdatePage(page, page_id, frame_id);
return true;
}
/**
* Creates a new page in the buffer pool. 相当于从磁盘中移动一个新建的空page到缓冲池某个位置
* @param[out] page_id id of created page
* @return nullptr if no new pages could be created, otherwise pointer to new page
*/
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
// 0.   Make sure you call DiskManager::AllocatePage!
// 1.   If all the pages in the buffer pool are pinned, return nullptr.
// 2.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
// 3.   Update P's metadata, zero out memory and add P to the page table.
// 4.   Set the page ID output parameter. Return a pointer to P.
std::scoped_lock lock{latch_};
frame_id_t frame_id = -1;
// 1 无法得到victim frame_id
if (!FindVictimPage(&frame_id)) {
return nullptr;
}
// 2 得到victim frame_id(从free_list或replacer中得到)
*page_id = disk_manager_->AllocatePage();  // 分配一个新的page_id(修改了外部参数*page_id)
Page *page = &pages_[frame_id];            // 由frame_id得到page
// pages_[frame_id]就是首地址偏移frame_id,左边的*page表示是一个指针指向那个地址,所以右边加&
UpdatePage(page, *page_id, frame_id);
page->pin_count_ = 1;  // 这里特别注意!每个新建page的pin_count初始为1
return page;
}
/**
* Deletes a page from the buffer pool.
* @param page_id id of page to be deleted
* @return false if the page exists but could not be deleted, true if the page didn't exist or deletion succeeded
*/
bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
// 0.   Make sure you call DiskManager::DeallocatePage!
// 1.   Search the page table for the requested page (P).
// 1.   If P does not exist, return true.
// 2.   If P exists, but has a non-zero pin-count, return false. Someone is using the page.
// 3.   Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.
std::scoped_lock lock{latch_};
auto iter = page_table_.find(page_id);
// 1 该page在页表中不存在
if (iter == page_table_.end()) {
return true;
}
// 2 该page在页表中存在
frame_id_t frame_id = iter->second;  // iter是pair类型,其second是page_id对应的frame_id
Page *page = &pages_[frame_id];      // 由frame_id得到page
if (page->GetPinCount() > 0) {
return false;
}
disk_manager_->DeallocatePage(page_id);
UpdatePage(page, INVALID_PAGE_ID, frame_id);
page->pin_count_ = 0;            // 删除page后,pin_count置0
free_list_.push_back(frame_id);  // 加到尾部
return true;
}
/**
* Flushes all the pages in the buffer pool to disk.
*/
void BufferPoolManager::FlushAllPagesImpl() {
// You can do it!
std::scoped_lock lock{latch_};
for (size_t i = 0; i < pool_size_; i++) {
FlushPageImpl(i);
}
}

注意pin_count的变化:

| 操作 | pin_count变化 |
| ---------- | ------------------------------------------------------------ |
| NewPage | pin_count置1 |
| FetchPage | pin_count++(若page在缓冲池) 或者 pin_count置1(若page不在缓冲池) |
| UnpinPage | pin_count--(此函数在NewPage或FetchPage后使用才能起到"取消固定"的作用) |
| DeletePage | pin_count置0 |

最后,提交zip文件,进行打包:

zip project1.zip \
src/include/buffer/lru_replacer.h \
src/buffer/lru_replacer.cpp \
src/include/buffer/buffer_pool_manager.h \
src/buffer/buffer_pool_manager.cpp