Back

CMU 15-445 Project 1: Buffer Pool Manager

实现一个缓冲池,以在磁盘与内存之间移动物理页面

buffer pool 负责将物理页在内存与磁盘之间来回移动,它允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如,系统使用其唯一标识符 page_id 向 buffer pool 请求一个页面,但系统不需要知道该页面是否已在内存中,由 buffer pool 负责在被请求的页面不在内存中时从磁盘检索该页面,并完成可能的内存页面替换。

图片 1
图片 1

LRU Replacer

该组件负责跟踪缓冲池中的页面使用情况。

在内存中且未在被使用(被 Unpin)的 Page 对应的 frame 的 id 会进入 LRUReplacer,等待在内存已满且需要从磁盘中交换页面时被淘汰。LRU 替换策略要求我们能根据最近的被使用时间来选择淘汰目标,一个简单的想法就是使用一个链表记录每一个元素,新加入的在链表头,那么链表尾的自然就是最近最少被使用的。Pin 操作需要在其中检索并删除元素,则又需要一个哈希表记录每个元素在链表中的位置。此外,还需要一个锁来保证线程安全。

class LRUReplacer : public Replacer {
    ···
private:
    size_t num_pages_;
    std::mutex latch_;
    std::list<frame_id_t> lru_list_;
    std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> lru_map_;
};

下面的实现就非常简单了,注意几点:

  • 每个函数都要加锁,可以使用 std::lock_guard,类似 golang 中的 defer
  • 在实现 Unpin 时确保链表的长度不超过 LRUReplacer 的容量,已满时先从链表末尾删除再将新的加入链表头。不要忘了操作哈希表。

Buffer Pool Manager

BufferPoolManager 负责从 DiskManager 获取数据库的物理页面并将它们存储在内存中。BufferPoolManage 还可以在被要求或者需要时淘汰一个页以便为新页腾出空间时,将脏页写入磁盘。

系统中的所有内存页面均由 Page 对象表示,BufferPoolManager 类维护了一个存放 Page 类型对象的数组。Page 对象只是缓冲池中用于存储内存页面的容器,因此并不特定于唯一页面。也就是说,每个 Page 对象都包含一块内存(data_),被认为是存放 “DiskManager 从磁盘读取到的物理页面内容” 的位置,project 2将会调用 Page::GetData 方法获取指向 data_ 的指针,再使用 reinterpret_cast 将其转换为其他类型的指针。BufferPoolManager 将在把物理页面从内存来回移动到磁盘时重用相同的 Page 对象来存储不同页面的数据。这意味着在系统的整个生命周期中,相同的 Page 对象可能包含不同的物理页面。Page 对象的标识符(page_id)跟踪其当前包含的物理页面。如果 Page 对象不再包含物理页面,则必须将其 page_id 设置为INVALID_PAGE_ID。

每个 Page 对象还维护一个计数器(pin_count),以表示正在使用该页面的线程数,类似引用计数。BufferPoolManager 不允许淘汰 pinned page。每个Page对象还跟踪它的脏标记(is_dirty)。页面在被淘汰之前必须要判断是否是脏页,脏页的内容要被写回磁盘,然后才能重用该对象。

BufferPoolManager实现将使用 Task 1 中实现的 LRUReplacer 类。它将使用 LRUReplacer 来跟踪页对象何时被访问过,以便在必须释放一个帧以为从磁盘复制新的物理页腾出空间时,它可以决定淘汰哪个页对象。

先来看一下 Buffer Pool Manager 以及 Page 的结构,frame_id 是用来访问 pages_ 数组的下标,page table 用于存储 page_id -> frame_id 的映射,这样就可以用 page_id 找到对应的 Page 对象。free_list 表示未含有实际内存页面的 Page 对象的 frame_id。

class BufferPoolManager {
    ···
    /** Number of pages in the buffer pool. */
    size_t pool_size_;
    /** Array of buffer pool pages. */
    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. */
    Replacer *replacer_;
    /** List of free pages. */
    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_;
};

class Page {
    ···
private:
    /** The actual data that is stored within a page. */
    char data_[PAGE_SIZE]{};
    /** The ID of this page. */
    page_id_t page_id_ = INVALID_PAGE_ID;
    /** The pin count of this page. */
    int pin_count_ = 0;
    /** True if the page is dirty, i.e. it is different from its corresponding
     * page on disk. */
    bool is_dirty_ = false;
    /** Page latch. */
    ReaderWriterLatch rwlatch_;
};

图片 2
图片 2

翻译完这一大段话,话不多说直接来实现,每个函数的注释提示都比较详细了。

先说几点:

  • 不要忘了加锁 bpm 的 latch。
  • NewPage 和 FetchPage 返回前要自增 pin count,这是因为这两个方法被调用是因为某个线程想要使用该页面。
  • 每个 Page 对象都有一个 rwlatch,但是不要滥用。在修改元数据的时候不需要加锁,只有在将页面写入磁盘、从磁盘读取页面时候需要加锁。这个锁是留给 Project 2 的。

Helper method

FetchPage 和 NewPage 都需要找到一个 replacement page,这里的代码可以复用。先在 free list 中找,再尝试让 replacer 去选取一个 Vitctim Page,这是因为 free list 中都是没有内容的 Page,一定不需要被写入磁盘。

bool BufferPoolManager::FindVictimPage(frame_id_t *frame_id) {
    if (!free_list_.empty()) {
        *frame_id = free_list_.front();
        free_list_.pop_front();
        return true;
    }

    if (replacer_->Victim(frame_id)) {
        return true;
    }

    frame_id = nullptr;
    return false;
}

FetchPageImpl

一个进程需要使用一个页面,bpm需要根据指定的 page_id 返回存放对应物理页面的 Page。

  1. 先在 page table 中找 page_id 是否存在对应的 frame_id。
    • 如果存在,就直接返回对应的 Page。返回前需要自增 pin_count 并调用 replacer_->Pin。
    • 如果不存在,就从 free list 或 replacer 中寻找一个 replacement page,若找不到,返回 nullptr。
  2. 如果 replacement page 是脏页,将其写入磁盘并重置 is_dirty。
  3. 修改 page table 以及 Page 对象的元数据,从磁盘中读取 page_id 对应的物理页面。不要忘了调用 replacer_->Pin,以及 pin count置为1。
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
    std::lock_guard<std::mutex> lock_(this->latch_);

    std::unordered_map<page_id_t, frame_id_t>::iterator it =
        page_table_.find(page_id);

    frame_id_t frame_id;
    if (it != page_table_.end()) {
        frame_id = it->second;
        Page *page = &pages_[frame_id];
        page->pin_count_++;

        replacer_->Pin(frame_id);
        return page;
    }

    if (!FindVictimPage(&frame_id)) {
        return nullptr;
    }

    Page *page = &pages_[frame_id];
    page->WLatch();
    if (page->IsDirty()) {
        disk_manager_->WritePage(page->GetPageId(), page->GetData());
        page->is_dirty_ = false;
    }

    page_table_.erase(page->GetPageId());
    page_table_[page_id] = frame_id;

    disk_manager_->ReadPage(page_id, page->GetData());

    page->page_id_ = page_id;
    page->pin_count_ = 1;
    replacer_->Pin(frame_id);
    page->WUnlatch();

    return page;
}

UnpinPageImpl

一个进程不再使用这个页面之后,将会调用 UnpinPage。Buffer Pool Manager 需要更新其对应的 pin count,is dirty。

  1. 尝试在页表中搜索 page_id。如果没有则需要返回 true。我也不知道为啥,感觉有点奇怪。
  2. 如果该 page 的 pin count <= 0,返回 false。
  3. 当函数入参 is_dirty 为真时置 page 的 is_dirty 为真。如果入参不为真,不要把原来 page 的标志搞没了。
  4. pin_count 自减,如果降为0,表示没有任何线程在使用该 page 了,调用 replacer 的 Unpin。

FlushPageImpl

将一个页面写入磁盘,这里不需要判断 is dirty 和 pin count。

在页表中搜索该页。若不存在,返回 false;若存在,调用 disk_manager 的 WritePage 方法将页面写回磁盘。需要对该页加读锁。

NewPageImpl

新建一个页面,并返回该页的 page_id 和 Page 对象。

  1. 先循环判断是否缓冲池中的所有 Page 都为 pinned,如果是则返回 nullptr。新建的页面要先写入缓冲池中的一个 Page,被 pin 过的 Page 不能被淘汰。
  2. 从 free list 或 replacer 中寻找一个 replacement page,若无法找到则返回。这里复用之前的 help method FindVictimPage。
  3. 如果该 replacement page 是脏的,将其写回磁盘。使用 DiskManager::AllocatePage 方法获得一个新的 page_id 赋给这个 Page 对象,修改 page table。不要忘了调用 ResetMemory 以及置 pin_count = 1。
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
    std::lock_guard<std::mutex> lock_(this->latch_);
    bool all_pinned = true;
    for (size_t i = 0; i < pool_size_; ++i) {
        auto page = &pages_[i];
        if (page->GetPinCount() > 0) {
            continue;
        }

        all_pinned = false;
        break;
    }

    if (all_pinned) {
        return nullptr;
    }

    frame_id_t frame_id;
    if (!FindVictimPage(&frame_id)) {
        return nullptr;
    }

    *page_id = disk_manager_->AllocatePage();
    Page *page = &pages_[frame_id];
    page->WLatch();
    if (page->IsDirty()) {
        disk_manager_->WritePage(page->GetPageId(), page->GetData());
        page->is_dirty_ = false;
    }

    page_table_.erase(page->GetPageId());
    page->page_id_ = *page_id;
    page->is_dirty_ = false;
    page->pin_count_ = 1;

    page->ResetMemory();
    page_table_[*page_id] = frame_id;
    page->WUnlatch();
    return page;
}

DeletePageImpl

删除一个页面。

  1. 在页表中搜索该页,如果不存在则返回 true。
  2. 如果该页的 pin count 大于 0,返回false。这代表有线程正在使用该页。
  3. 调用 DiskManager::DeallocatePage 从磁盘删除该页,从页表删除该页对应的项,调用 ResetMemory 清空该 Page 对象的数据,置 page_id 为 INVALID_PAGE_ID,将该页加入 free list。

FlushAllPagesImpl

将所有页面写回磁盘,这个没啥好说的。

测试结果

图片 3
图片 3

值得一提的是这个 2020 的 autograder 似乎用不了了。googletest 把它的 github 上的分支从 master 改成了 main,但测试构建脚本还是会从 master 分支去拉东西,然后就会失败。

Built with Hugo
Theme Stack designed by Jimmy