Buffer Pool

这个project是要在存储管理器中实现一个buffer pool，即缓冲池。缓冲池其实就是一块大的内存区域主内存，负责与磁盘之间来回移动物理页。它使得DBMS支持大于系统可用内存的数据库。缓冲池的操作对系统中的其他部分应该是透明的。例如，系统使用唯一标识符page_id_t想缓冲池请求页面的时候，系统不知道该页面是否位于已经在内存中，或者是需要从磁盘检索。

实现的时候需要保证线程安全。多个线程可以同时访问内部数据结构，并且必须确保关键部分收到latch的保护。

LRU-K 更换策略

这个组件负责跟踪缓冲池的页面使用情况。LRUKReplacer的最大大小与缓冲池的大小相同，但并非 replacer 中的所有帧都被视为可驱逐。LRUKReplacer的大小由可驱逐帧的数量表示。

LRU-K 算法移出其后向 k 距离为replacer中所有帧的最大值的帧。向后 k 距离的计算方法是当前时间戳与第 k 次访问的时间戳之间的时间差。历史访问次数少于 k 次的帧将为其后 k 距离指定 +inf。 当多个帧具有 +inf 向后 k 距离时，实施普通的LRU。

Evict(frame_id_t* frame_id) -> bool

驱逐具有最大向后 k 距离的帧。将帧 ID 存储在 output 参数中并返回 True。如果没有可驱逐的帧，则返回 False。

1. 获取latch，判断如果当前大小为0，则返回false。
2. 构建tuple(id, kthTimestamp, mostRecentTimestamp)来存储节点信息，然后创建一个vector<tuple>，遍历node_store_中的所有节点，把每个节点的信息用tuple的形式放进vector中。vector为空则返回false。
3. 实现一个临时的cmp排序函数，对vector中元素进行排序std::sort(vec.begin(), vec.end(), cmp)，排在第一个的元素就是需要被驱逐的节点。清除节点历史、置为不可驱逐、replacer大小减1、赋值frame_id。

1
2
3
4
5
6

  auto cmp = [](const std::tuple<frame_id_t, size_t, size_t> &a, const std::tuple<frame_id_t, size_t, size_t> &b) {
    if (std::get<1>(a) != std::get<1>(b)) {
      return std::get<1>(a) > std::get<1>(b);
    }
    return std::get<2>(a) < std::get<2>(b);
  };

RecordAccess(frame_id_t frame_id)

记录在当前时间戳访问给定的帧 ID。应在 BufferPoolManager 中固定页面后调用此方法。

1. 获取latch，frame_id不超过replacer_size_，否则throw exception。
2. 当前时间戳加1，先在node_store_找frame_id，找到了就直接把当前时间戳添加到该帧的访问历史中，否则新建一个节点，添加访问历史，并把新节点emplace到node_store_中。

Remove(frame_id_t frame_id)

清除与该帧关联的所有访问历史记录。仅当在 BufferPoolManager 中删除页面时，才应调用此方法。

1. 获取latch，frame_id不超过replacer_size_，否则throw exception。
2. 在node_store_找该帧，若没找到或者找到了但不可驱逐，直接return。
3. 拿到该帧，清除访问历史，置为不可驱逐，replacer当前大小减1。

SetEvictable(frame_id_t frame_id, bool set_evictable)

该方法控制帧是否可驱逐。它还控制 LRUKReplacer 的大小。在实现 BufferPoolManager 时当页面的 pin count 达到 0 时，其对应的帧被标记为 evictable 并且 replacer 的大小会增加。

1. 获取latch，frame_id不超过replacer_size_，否则throw exception。
2. 在node_store_找该帧，若没找到，直接return。
3. 找到该帧之后，判断若是由unevictable变为evictable，则replacer当前大小加1，反之replacer当前大小减1。设置该帧可驱逐与否。

Disk Scheduler

该组件负责调度DiskManager上的读写操作。BufferPoolManager 可以使用磁盘调度程序disk scheduler对磁盘请求进行排队，磁盘调度程序将维护一个后台工作线程，负责处理调度的请求。

磁盘调度程序将利用共享队列来调度和处理磁盘请求。一个线程将向队列添加一个请求，磁盘调度程序的后台工作人员将处理排队的请求。项目已提供了一个Channel类 src/include/common/channel.h 以促进线程之间安全共享数据。

Schedule(DiskRequest r)

安排DiskManager执行的请求。 DiskRequest结构指定请求是否为读/写、数据应写入/从何处以及操作的页 ID。 DiskRequest还包含一个std::promise一旦处理请求，其值应设置为 true。

1. 将请求添加到共享队列中

1

request_queue_.Put(std::make_optional<DiskRequest>(std::move(r)));

StartWorkerThread()

此方法负责获取排队的请求并将它们分派到DiskManager。请记住在DiskRequest的回调中设置值，以向请求发出者发出请求已完成的信号。在调用 DiskScheduler的析构函数之前，该值不应返回。

1. 循环查看是否有请求，有请求就调用DiskManager的ReadPage或WritePage方法，然后执行回调设置值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void DiskScheduler::StartWorkerThread() {
  std::optional<DiskRequest> request;
  // 是否循环看request.has_value()
  while ((request = request_queue_.Get(), request.has_value())) {
    if (request->is_write_) {
      disk_manager_->WritePage(request->page_id_, request->data_);
    } else {
      disk_manager_->ReadPage(request->page_id_, request->data_);
    }
    request->callback_.set_value(true);
  }
}

Disk Manager

磁盘管理器类Disk Manager从磁盘读取页面数据并将其写入磁盘。您的磁盘调度程序在处理读取或写入请求时将使用磁盘管理器的ReadPage()和WritePage()。

Buffer Pool Manager

BufferPoolManager负责使用DiskScheduler从磁盘获取数据库页面并将其存储在内存中。当明确指示执行此操作或需要逐出页面以为新页面腾出空间时， BufferPoolManager还可以安排将脏页面写入磁盘。

实验文档中强调，这里需要理解的是：系统里所有内存的页面都是由Page对象表示，BufferPoolManager也不需要了解页面的内容，但是作为开发人员，你需要认识到Page对象只是bufferpool中内存的容器。也就是说，每个Page对象都包含了一块内存空间，用来存放从磁盘读取的物理页面的内容。当数据在磁盘上来回移动时， BufferPoolManager将重用相同的Page对象来存储数据。这意味着在系统的整个生命周期中，同一个Page对象可能包含不同的物理页。 Page对象的标识符(page_id)跟踪它包含的物理页。

NewPage(page_id_t* page_id)

当您想要在NewPage()中创建新页面时， AllocatePage私有方法为BufferPoolManager提供唯一的新页面 id。

1. 获取latch，若free_list_不空，则取出free_list_的第一个元素（也可以不是第一个）作为frame_id，然后pop掉。否则，用LRUKReplacer的Evict方法获取一个frame_id，若驱逐失败，直接返回nullptr，驱逐成功则先从page_table_中erase掉该frame_id对应的page。
2. 通过pages数组和frame_id获取该页面，如果该页是脏页，需要先写回磁盘，了解promise和future的使用方法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  page = pages_ + frame_id;
  if (page->IsDirty()) {
    // use promise and future to implement the communication between threads
    auto promise = disk_scheduler_->CreatePromise();
    auto future = promise.get_future();
    disk_scheduler_->Schedule({true, page->GetData(), page->GetPageId(), std::move(promise)});
    // wait till promise is fulfilled
    future.get();
    page->is_dirty_ = false;
  }

3. 用AllocatePage()分配一个页面id，执行一系列初始化，返回页面。

1
2
3
4
5
6
7

  page->page_id_ = AllocatePage();
  page->ResetMemory();
  page->pin_count_ = 1;
  page_table_[page->page_id_] = frame_id;
  replacer_->SetEvictable(frame_id, false);
  replacer_->RecordAccess(frame_id);
  *page_id = page->page_id_;

FetchPage(page_id_t page_id)

对于FetchPage ，如果空闲列表中没有可用页面且所有其他页面当前均已固定，则应返回 nullptr。

1. 获取latch，如果page_id等于INVALID_PAGE_ID，返回nullptr。
2. 如果在page_table_中找到了该page_id，则取出对应的frame_id，然后用pages数组得到page。replacer_记录它的访问、置为不可驱逐、pin加一。返回该page。
3. 若是没有找到，则要通过free_list_或者驱逐来获得一个frame_id，同理NewPage()的时候也要先执行写回磁盘。
4. 修改page_table_，同理NewPage()执行一系列初始化，然后利用disk_scheduler_修改从磁盘读取物理页面，存入page后返回。

UnpinPage(page_id_t page_id, bool is_dirty)

对于UnpinPage ， is_dirty 参数跟踪页面在固定时是否被修改。

1. 获取latch，如果page_table_中没找到，返回false。
2. 拿到page，若是pin_count_以及为0，返回false。
3. pin_count_减1，若减完之后为0，置为可驱逐，然后注意is_dirty_设置为is_dirty || page->is_dirty_。

FlushPage(page_id_t page_id)

FlushPage应该刷新页面，无论其 pin 状态如何。

1. 获取latch，page_id不合法或者没在page_table_中没找到，返回false。
2. 拿到page，用disk_scheduler_写回磁盘。is_dirty_置为false。

DeletePage(page_id_t page_id)

DeallocatePage()方法是一个空操作，它模拟释放磁盘上的页面，您应该在DeletePage()实现中调用它。

1. 获取latch，若page_id不合法，返回false。若是在page_table_中没找到，先执行DeallocatePage(page_id)，返回true。
2. 拿到page，如果pin_count_不为0，返回false。
3. 执行一系列删除相关操作后DeallocatePage(page_id)。

1
2
3
4
5
6
7
8

  page_table_.erase(page_id);
  replacer_->Remove(frame_id);
  free_list_.emplace_back(frame_id);
  page->ResetMemory();
  page->page_id_ = INVALID_PAGE_ID;
  page->is_dirty_ = false;
  page->pin_count_ = 0;
  DeallocatePage(page_id);

FlushAllPages()

写回所有页面到磁盘