谈谈关系数据库的设计与实现(2)——缓存池

pedrogao大约 15 分钟

缓存池

减少磁盘和内存之间的数据 IO 次数是数据库提升查询效率的主要途径之一，也是数据设计的主要目标。

为了达到这个目标，数据库需要在内存中保留尽可能多的数据页，最大限度地提高在内存中处理数据查询的机会，减少磁盘访问次数。

但不可能将所有页都保存在内存中，我们需要一个管理内存与磁盘数据的中介组件——缓存池。

磁盘上保存的数据实则是缓存池数据的副本。缓存池中的基本单位是页(对应操作系统 IO 的基本单位也是页)，每一页在磁盘上都有一个副本，磁盘上的副本可能是老数据(脏页)，负责分配缓存池的组件被称为缓存管理器(buffer_manager)。

淘汰策略

相较于磁盘而言，内存是非常有限的，数据库不可能将所有数据页装在内存中，只能尽可能的将热点数据存储在缓冲池中，因此一旦缓存池满了，那么就需要淘汰一部分数据页将其刷到磁盘中，再从磁盘读取新的页。

常见的淘汰算法有 FIFO、 LRUopen in new window 和 LFUopen in new window 等。数据库可以实现多种淘汰算法，在不同场景中选择合适的淘汰策略，这里我们来详细介绍 LRU 算法。

LRU(Least recently used)，全称最近最少使用算法，是目前最常见的页面置换算法。LRU 算法会选择最近最少使用的页淘汰，缓存管理器会将其从缓存池中淘汰，并刷到磁盘中，然后从磁盘上读取新的数据页。

LRU 的核心点在于最近、最少两个字，选择合适的数据结构就能解决这个问题。这里，笔者选择了最常见的双向链表+哈希表法，原理也很简单：

新增(新访问)页将其保存在链表头部，并写入哈希表供快速查询；
待页慢需要淘汰时，从链表尾部得到淘汰页，并从哈希表中删除。由于每次访问或者新增页时，都会将页保存在链表头部，那么链表尾部自然就成为了最近最少使用的页，当缓存池满了需要淘汰时，直接将链表尾部页淘汰即可。

bustub 中的 LRUReplacer 定义如下：

class LRUReplacer : public Replacer {
 public:
  // ...
  // 淘汰一个页，并将淘汰页的 frame_id 返回
  bool Victim(frame_id_t *frame_id) override;
  // 从 LRU 淘汰策略中删除一个页，不受淘汰约束
  void Pin(frame_id_t frame_id) override;
  // 将一个页加入 LRU 淘汰策略
  void Unpin(frame_id_t frame_id) override;
  // 当前 LRU 中有多少页
  size_t Size() override;

 private:
  size_t num_pages;  // 最大页数量
  std::list<frame_id_t> list_; // 双向链表
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> _map; // 哈希表
  std::mutex mu;  // 锁
};

LRUReplacer 实现并不困难，也不复杂，不过需要注意以下两点：

LRUReplacer 需要保证并发安全，故每个函数操作都需加锁；
缓存管理器会调用 Unpin 方法向 LRUReplacer 中加入需要被淘汰的页，也会调用 Pin 方法删除页，一经删除后，该页不再受 LRU 约束。 LRUReplacer 中的三个核心方法伪代码如下：

void LRUReplacer::Unpin(frame_id_t frame_id) {
  lock(); // 加锁
  // 如果超过了最大数量，或者已经包含了 frame_id，则直接返回
  if (size >= num_pages || _map.contains(frame_id)) {
    return;
  }
  // 将 frame_id 加入到 LRU 中
  front = list_.push_front(frame_id);
  _map[frame_id] = front;
}

void LRUReplacer::Pin(frame_id_t frame_id) {
  lock(); // 加锁
  if (!_map.contains(frame_id)) {
    return;  // 没有则直接返回
  }
  it = _map[frame_id];
  // 删除这个节点
  _list.erase(it);
  _map.erase(frame_id);
}

bool LRUReplacer::Victim(frame_id_t *frame_id) {
  lock(); // 加锁
  if (_map.empty()) {
    return false;
  }
  // 删除尾部
  *frame_id = _list.pop_back();
  _map.erase(*frame_id);
  return true;
}

缓存管理器

缓存管理器负责协同内存、磁盘之间的数据交换，且数据基本单位是页。缓存管理器负责将新数据页刷新到磁盘中，也会从磁盘中读取数据页到内存。如下图 2 所示：

图 2 缓存管理器内存、磁盘

缓存管理器是内存、磁盘之间的数据通道，元数据、表数据、索引数据都会通过缓存管理器来管理，对应 bustub 中的 BufferPoolManager 类。定义如下：

class BufferPoolManager {
 public:
  // ...
  // 获取所有数据页
  Page *GetPages() { return pages_; }
  // 缓存池大小
  size_t GetPoolSize() { return pool_size_; }

 protected:
  // 通过 page_id 获取对应页 
  Page *FetchPageImpl(page_id_t page_id);
  // Unpin 一个页，is_dirty 表示是否脏页
  bool UnpinPageImpl(page_id_t page_id, bool is_dirty);
  // 将页刷到磁盘
  bool FlushPageImpl(page_id_t page_id);
  // 新建一个页
  Page *NewPageImpl(page_id_t *page_id);
  // 从缓存中删除一个页
  bool DeletePageImpl(page_id_t page_id);
  // 将缓存中所有页到刷到磁盘
  void FlushAllPagesImpl();

  // 缓存池大小
  size_t pool_size_;
  // 缓存池中的页
  Page *pages_;
  // 磁盘管理器
  DiskManager *disk_manager_ __attribute__((__unused__));
  // 日志管理器，暂不关注
  LogManager *log_manager_ __attribute__((__unused__));
  // 页表，page_id => frame_id
  std::unordered_map<page_id_t, frame_id_t> page_table_;
  // 置换器，如 LRUReplacer
  Replacer *replacer_;
  // 空闲页列表
  std::list<frame_id_t> free_list_;
  // 锁
  std::mutex latch_;
};

BufferPoolManager 中由 pages_ 负责缓存数据页，其本质为一个 Page 数组，数组中的每一项被称为帧(frame)，每一项对应的数组序号称为 frame_id；
page_table_ 负责维护 frame_id 与 page_id 之间的关系，pages_ 数组是有限的，frame_id 是数据页在内存中的标识，而 page_id 是数据页在磁盘上的标识；
free_list_ 是空闲页列表，表示当前缓存池还有多少帧是空闲的，可以用于缓存页数据；
BufferPoolManager 上的操作也需要保证并发安全，因此锁(latch_) 也是必须的。这里需要额外说明的是，数据存储在磁盘上被称为页，但是被加载到内存 pages_ 后，又给它取了一个新名字，叫做帧，由 frame_id 来表示，当然其数据本身还是由 Page 来表示，因此后面还是会统一称作页。frame_id 是页在内存中暂时的 id 而已，当页被淘汰，就会有新页来继续使用这个 frame_id。

BufferPoolManager 的意义在于，任何内存与磁盘之间的交互都需要通过它来进行，无论是获取数据页(FetchPage)，删除数据页(DeletePage)，新建数据页(NewPage)，刷数据页(FlushPage)都被它垄断，这样就能最大程度的利用缓存，提高访问性能。

BufferPoolManager 的主要作用点在于操作数据页，有如下几个核心方法：

获取数据页(FetchPage)；
删除数据页(DeletePage)；
新建数据页(NewPage)；
将数据页刷至磁盘(FlushPage)。以 FetchPage 方法为例，以 page_id 为参数调用 FetchPage 来获取对应的数据页，如果缓存中已有该页，则 Pin 该页(避免被 LRU 淘汰)并增加 pin_count 直接返回；如缓存中没有，则判断空闲列表是否有空闲页，如有直接获取空闲页，若无则淘汰一个页并且拿到该页；如果该页是脏页，则刷至磁盘，最后重置页数据，并从磁盘中读取新页。流程图如下图 3：

图 3 FetchPage 流程图

FetchPage 伪代码实现如下：

Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
  lock(); // 加锁，保证线程安全
  page = page_table_.find(page_id);
  if (page) {
    // 缓存中已有 page
    replacer.Pin(page.frame_id); // Pin frame，frame 不会再淘汰
    page.pin_count_++; // pin_count += 1
    return page; // 返回 page
  }
  // 缓存中没有 page，未找到 Page
  frame_id_t free_frame_id;
  if (!free_list_.empty()) {
    // 从空闲列表中获取
    free_frame_id = free_list_.pop_front(); 
  } else {
    // 如果 free_list 中没有则淘汰一个页
    replacer_.Victim(&free_frame_id);
  }
  // 得到空闲页
  page = pages_[free_frame_id];
  // 如果 free_frame_id 的页是脏的，则刷至磁盘
  if (page.IsDirty()) {
    disk_manager.WritePage(page);
    page.is_dirty_ = false;
  }
  // 更新 page_table_
  page_table_[page_id] = free_frame_id;
  // 更新 P 的元数据
  page.reset();
  // 从磁盘中读取 page_id 对应的页数据到 page
  disk_manager_.ReadPage(page_id, page);
  return page;
}

其它方法，这里就不再赘述了，感兴趣的可以点击这里open in new window 查看其说明。这里贴出笔者实现的伪代码：

bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
  lock(); // 加锁
  page = page_table_.find(page_id); // 寻找 page
  if (not page) {
    return false;  // 未找到，返回 false
  }
  if (page.pin_count_ < 0) { // 如果 pin_count < 0，返回 false
    return false;
  }
  if (page.pin_count_ > 0) { // 如果 > 0，则 -1
    page->pin_count_--;
  }
  if (page.pin_count_ == 0) { // 如果 == 0，则证明无人使用该页，加入到 replacer 中
    replacer_.Unpin(frame_id); // Unpin 后，该页可能会被替换
  }
  if (is_dirty) {
    page.is_dirty_ = is_dirty; // 是否脏页，即是否更改了该页数据
  }
  return true;
}

bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
  lock(); // 加锁
  page = page_table_.find(page_id); // 寻找数据页
  if (not page) {
    return false;
  }
  if (page.IsDirty()) { // 是否脏页
    disk_manager_.WritePage(page); // 脏页记得写回磁盘
    page.is_dirty_ = false;
  }
  return true;
}

Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
  lock();
  *page_id = disk_manager_.AllocatePage(); // 分配新的 page_id
  // 寻找新的 frame_id
  frame_id_t free_frame_id;
  if (!free_list_.empty()) {
    free_frame_id = free_list_.pop_front(); // 从空闲列表中拿到
  } else {
    // 如果 free_list 中没有则淘汰一个页
    replacer_.Victim(&free_frame_id);
  }
  page = pages_[free_frame_id];
  // 如果 free_frame_id 的页是脏的，则刷至磁盘
  if (page.IsDirty()) {
    // 写到 page
    disk_manager_.WritePage(page);
    page.is_dirty_ = false;
  }
  page_table_[*page_id] = free_frame_id;  // 更新 page_table
  // 重置 P 的元数据
  page.reset()
  return pages_[free_frame_id];
}

bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
  lock();
  page = page_table_.find(page_id);
  if (not page) {
    return true; // 不存在，直接返回
  }
  if (page.pin_count_ > 0) {
    return false; // 注意：pin_count > 0 证明有人正在使用，不能删除
  }
  if (page.IsDirty()) {
    disk_manager_.WritePage(page);
    page.is_dirty_ = false;
  }
  // 元数据重置
  page->reset();
  // 删除
  page_table_.erase(page_id); // 从 page_table 中删除
  free_list_.push_back(frame_id); // 加入到空闲列表
  disk_manager_->DeallocatePage(page_id); // 释放该页，并刷回磁盘
  return true;
}

void BufferPoolManager::FlushAllPagesImpl() {
  lock();
  for page in pages_ { // 刷每一页
    FlushPage(page);
  }
}

额外说明：

UnpinPage 需要注意 pin_count，pin_count 不可能为负，当有人拿到数据页，就会 pin_count += 1，一旦 pin_count 为 0，就证明无人使用该页，那么该页就应该被加入到 replacer 中，可以被淘汰；
FlushPage 和 FlushAllPages 需要注意脏页，若是脏页，则必须刷回磁盘；
NewPage 与 FetchPage 类似，都需要检查空闲列表，如果没有空闲页，那么则需要淘汰一个页；
DeletePage 时也需要注意脏页，另外如果 pin_count > 0，那么证明有人正在使用该页，不能删除。从伪代码中，我们可以发现 FetchPage 和 UnpinPage 实则为一对反操作，FetchPage 会增加页的 pin_count，而 UnpinPage 会减少 pin_count，并且页最后能否被删除取决于 pin_count 是否为 0，所以请切记：一旦你调用了 FetchPage 获取了数据页，操作完成后，不再使用，一定记得 UnpinPage，否则页永远不能删除，缓存的淘汰策略就名存实亡了。

参考资料

Buffer Poolsopen in new window
Database System Concepts 10.8
PROJECT #1 - BUFFER POOLopen in new window

谈谈关系数据库的设计与实现(2)——缓存池

# 缓存池

# 淘汰策略

# 缓存管理器

# 参考资料

缓存池

淘汰策略

缓存管理器

参考资料