实验指导书

  1. 构建一个新的面向磁盘的存储管理器，这样的存储管理器假定数据库的主要存储位置在磁盘上。

  2. 在存储管理器中实现缓冲池。缓冲池负责将 pag 从主存到磁盘来回移动。允许 DBMS 支持大于系统可用内存量的数据库。缓冲池的操作对系统中的其他部分是透明的。例如，系统使用其唯一标识符 ( page_id_t)向缓冲池请求页面，但它不知道该页面是否已经在内存中，或者系统是否必须从磁盘中检索它。

  3. 实现需要是线程安全的。多个线程将同时访问内部数据结构，因此需要确保临界区受到 latches的保护。

  4. 需要在存储管理器中实现以下两个任务：

    （1）LRU 替换原则

    （2）缓冲池管理器

  5. 任务 1 - LRU 替换策略

    （1）该组件负责跟踪缓冲池中的页面使用情况。将在 src/include/buffer/lru_replacer.h 中实现一个新的子类 LRUReplacer  ，它相应的实现文件在 src/buffer/lru_replacer.cpp 。LRUReplacer 继承了抽象类 Replacer （src/include/buffer/replacer.h）。

    （2） LRUReplacer 的大小与 BufferPoolManager 相同，因为在 BufferPoolManager 中包含了所有 frames 的 placeholders 。 但是，并非所有 frames 都被视为 LRUReplacer. 将 LRUReplacer 被初始化为有没有 frames。然后，LRUReplacer 将只考虑新的没有划分的那些。

    （3）需要实现课程中讨论的 *LRU* 策略。您将需要实现以下方法：

  6. 任务 2 - 缓冲池管理器

  1. 测试

    // 别忘了删除测试中的 disabled

$ mkdir build
$ cd build
$ make lru_replacer_test
$ ./test/lru_replacer_test

$ mkdir build
$ cd build
$ make buffer_pool_manager_test
$ ./test/buffer_pool_manager_test

// 检查
$ cd build
$ make format
$ make check-lint
$ make check-clang-tidy

  2. 提交：

设计思路

  1. LRU（Least-Recently Used）的策略：
  2. LRU 的思路：
  3. Clock 策略：
  4. Clock 设计思路：

Coding

<aside> 💡 C++ ：std::scoped_lock 能够避免死锁的发生。它的构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作。能够保证线程安全。

</aside>

  1. 根据上面 LRU 的设计思路，我们可以定义出 LRUReplacer 的数据结构，如下。

    class LRUReplacer : public Replacer {
 private:
  // TODO(student): implement me!
	// 为了线程安全需要加的锁
  std::mutex latch;
	// 这个表示 LRUReplacer 的大小，Buffer Pool大小相同。
  size_t capacity;
	// 我们使用 双向链表 + 哈希表 的数据结构。
  std::list<frame_id_t> LRUList;
  // 使用 unordered_map（注意加头文件），从 frame_id 映射到 Node。 
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> LRUHash;
};

  2. 根据上面 Clock 的设计思路，我们可以定义出 ClockReplacer 的数据结构，如下。

    
class ClockReplacer : public Replacer {
 private:
  // TODO(student): implement me!
  // 对于每个 frame_id，都需要标记两个元素。isPin 表示当前 frame 是正在被引用。
  // ref 表示当前的 frame 最近是否被使用过。
  struct clockItem {
    bool isPin;
    bool ref;
  };
  // 为了线程安全需要加的锁
  std::mutex latch;
  // 这个表示 ClockReplacer 的大小，Buffer Pool大小相同。
  size_t victim_number;
  // clock 指针当前所指位置。
  size_t clockHand;
  // clockItem 数组，数组下表表示 frame_id。
  std::vector<clockItem> victimArray;
};

  3. Replacer ：追踪 page 使用情况的抽象类。类中不包含 page 的具体信息，只是为 Buffer Pool Manager 服务，提供了一个可以替换的 frame_id 。这个类包含了四个主要的函数。这里为了方便，将两个实现 LRUReplacer ClockReplacer 根据功能写在了一起，看的时候如果不舒服可以一次看一种实现方法。

    class Replacer {
 public:
  Replacer() = default;
  virtual ~Replacer() = default;

  /**
   * Remove the victim frame as defined by the replacement policy.
   * @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
   */
  virtual bool Victim(frame_id_t *frame_id) = 0;

  /**
   * Pins a frame, indicating that it should not be victimized until it is unpinned.
   * @param frame_id the id of the frame to pin
   */
  virtual void Pin(frame_id_t frame_id) = 0;

  /**
   * Unpins a frame, indicating that it can now be victimized.
   * @param frame_id the id of the frame to unpin
   */
  virtual void Unpin(frame_id_t frame_id) = 0;

  /** @return the number of elements in the replacer that can be victimized */
  virtual size_t Size() = 0;
};

    （1）Victim 函数：

    （2）Pin 函数：

    （3）Unpin 函数：

    （4）Size 函数：

    （5）构造函数：

  4. Buffer Pool Manager ：对缓冲池进行管理。其主要的数据结构是一个 page 数组，下标表示 frame_id 。还有一个哈希表，表示从 page_id 到 frame_id 的映射。为了各种需要，省略代码。