proj1_Buffer Pool

LRU-K,Disk_Scheduler,Buffer_Pool_Manager

发表于 2024/06/25

作者 alioth

15 分钟阅读

Proj1:buffer_pool

概览

缓存池负责在内存和磁盘之间来回移动物理页，它使得数据库管理系统能够支持比系统可用内存更大的数据库。

LRU-K

后向K距离(Backward K-Distance): 后向K距离是衡量某个数据帧在缓存中被保留理由的一个重要指标。这个距离的计算方法是，找出当前时间戳与该数据帧第K次之前访问的时间戳之间的差。简单地说，这个距离衡量了自从该数据帧最后一次成为第K次访问以来已过去的时间长度。
淘汰机制: 在LRU-K算法中，使用后向K距离来决定哪个数据帧应当从缓存中淘汰：如果一个数据帧的访问历史少于K次，那么它的后向K距离被认为是无限大+inf。这意味着这个数据帧相对来说是“新”的或者“不够重要的”，因为它还没被足够频繁地访问。当多个数据帧有相同的无限大后向K距离时，算法会淘汰那个整体上最早访问过的数据帧，即所有数据帧中记录的最早访问时间最早的那个。
淘汰流程的逻辑: 计算每个数据帧的后向K距离：通过当前时间戳与第K次之前访问的时间戳之间的差分。比较后向K距离：找到拥有最大后向K距离的数据帧（这代表它相对于其他数据帧而言，在很长时间内不太可能被访问）。如果有多个数据帧的后向K距离是+inf（表示它们被访问的次数少于K次），那么这些数据帧被视为候选淘汰对象。
淘汰数据帧：: 在所有候选淘汰对象中，淘汰那个整体上最早访问过的数据帧，确保缓存中保留的数据帧是最近被频繁访问的。

ToDo

LRU-K replacement policy
Disk scheduler
Buffer pool manager
上述部分的类的API需要自己完成，不要修改任何类中定义的函数名。
不要删除类中的数据成员，可以添加数据成员和辅助函数
实现是要求线程安全的

Task1 LRU-K Replacement Policy

这个部分负责跟踪缓存池中页的使用，需要实现的类:LURKReplacer位于src/include/buffer/lru_k_replacer.h，需要实现的文件位于:src/buffer/lru_k_replacer.cpp。

LURKReplacer是一个单独的类，不和其他的Replacer类相关联。不要实现LRU或clock replacement policy。

LRU-K算法会驱逐替换器中所有帧里反向k距离最大的那个帧。反向k距离的计算方式是当前时间戳与第k次先前访问的时间戳之间的时间差。对于历史访问次数少于k次的帧，其反向k距离被赋予+inf（无穷大）。当多个帧的反向k距离为+inf时，替换器会驱逐具有最早总体时间戳的帧（即，其最近一次记录的访问是所有帧中总体上最近一次访问的帧）。

LRUKReplacer的最大size等于buffer_pool的size，因为它包含了BufferPoolManager中所有帧的占位符。不过在任何给定时刻，不是所有的replacer中的帧都视为可以被驱逐的。LRUKReplacer的大小由可驱逐帧的数量表示。LURKReplacer初始化时没有帧，因此，只有当有帧被标记为evictable，replacer的size才会增加。

TODO: src/include/buffer/lru_k_replacer.h&src/buffer/lru_k_replacer.cpp

Evict(frame_id_t* frame_id): evict一个在replacer中用LURK算法从所有evictable的帧中得到的帧，将这个帧的id存在输出参数里并且返回True，如果没有evictable的帧则返回false
RecordAccess(frame_id_t frame_id): 记录当前时间戳被访问的frame id，这个方法应该在一个页被固定在bufferPoolManager后被调用。
Remove(frame_id_t frame_id): 清楚一条特定帧的访问记录，此方法仅应在BufferPoolManager中页面被删除时调用。
SetEvictable(frame_id_t frame_id, bool set_evictable):此方法控制一个帧是否可被驱逐。它还控制LRUKReplacer的大小。在实现BufferPoolManager时，你会知道何时调用此函数。具体来说，当一个页面的固定计数达到0时，其对应的帧被标记为可驱逐，并且替换器的大小增加。
Size(): 此方法返回当前在LRUKReplacer中的evictable帧的数量。

LRU

用到了一个哈希表和一个双向链表实现，双向链表有一头一尾，分别用来代表最早和最晚access过的节点。

双向链表用到的函数:

  
void addNode(DoubleNode* newNode) {}      // 加入一个节点到头部
void moveNodeToTail(DoubleNode* node) {}  // 将指定节点移动到尾部
DoubleNode *removeHead() {}               // 删除头节点(最近最少使用节点)

LRU_Cache用到的函数:

  
int get(int key) {}                       // access 指定节点
void put (int key, int value) {}          // put 指定节点

LRU-K

用到了一个history_list和一个buffer_list来分别记录access次数小于k的和access次数大于等于k的节点。所以我们现在需要两个双向链表，并且它们的总容量等于buffer_pool的大小，有两种策略，一种是还是用一个双向链表，不过中间用一个mid指针分隔history和buffer；第二种策略就是用两个链表实例。

让我们来设计一下现在的LRUK:

  
  class LRUKNode {
  public:
    size_t fid_;          // 类似于键
    size_t access_times;      // 命中缓存的次数
    bool is_evictable;

    LRUKNode *next;
    LRUKNode *prev;
  }

  class Double_list {
  public:
    LRUKNode *head;
    LRUKNode *tail;
    size_t evictable_num; // evictable 节点数
    size_t node_num;      // 总节点数
  public:
    void addNode(DoubleNode* newNode) {}      // 加入一个节点到头部
    void moveNodeToTail(DoubleNode* node) {}  // 将指定节点移动到尾部
    DoubleNode *removeHead() {}               // 删除头节点(最近最少使用节点)
  }

  class LRUK_Cache {
  public:
    size_t replacer_size_;  // 整个缓存池的容量
    size_t curr_size_{0};     // evictable 节点数量
    size_t node_num;          // 全部节点的数量
    size_t k_;
    Double_list history_list; // 两个双向链表
    Double_list buffer_list;
    std::unordered_map<size_t, LRUKNode*> his_node_store_;
    std::unordered_map<size_t, LRUKNode*> buf_node_store_;
  public:
    bool Evict(frame_id_t *frame_id) -> bool;
    void RecordAccess(frame_id_t frame_id);
    void SetEvictable(frame_id_t frame_id, bool set_evictable);
    void Remove(frame_id_t frame_id);
    size_t Size() -> size_t;
  }

具体方法的实现

Evict

判断LRUK_Cache的evictable_num是否为0，是的话继续执行，否则返回false。
先看history里有没有evictable的节点，有的话就对history_list做evict，否则对buffer_list做。
记录被evict的节点的frame_id，释放这个节点的内存，整个LRUK_Cache的evictable_num-1。
返回true

  
auto LRUKReplacer::Evict(frame_id_t *frame_id) -> bool { 
  if (curr_size_ == 0)
      return false;
  LRUKNode* node;
  if (his_list.evictable_num != 0) {
      node = his_list.remove();
  } else {
      node = buf_list.remove();
  }
  if (!node)
      return false;
  *frame_id = node->get_fid();
  if (his_node_store_.find(node->get_fid()) != his_node_store_.end()) {
      his_node_store_.erase(node->get_fid());
  } else if (buf_node_store_.find(node->get_fid()) != buf_node_store_.end()) {
      buf_node_store_.erase(node->get_fid());
  }
  delete node;
  curr_size_--;
  node_num--;
  return true;
}

RecordAccess

在history_list找到了：(FIFO)
1. access_time+1 == k那么就要把这个节点移动到buffer_list里了。buffer_list的node_num++，如果这个节点还是evictable的话那buffer_list的evictable_num++。history_list的node_num和evictable_num也都要做相应的处理
2. access_time+1 < k那就access_time++。
在buffer_list里找到了：(LRU)
1. 移动到尾部
对于新的frame：
1. buffer_pool.size > node_num -> 直接插入到history_list中,LRUKCache.node_num++, his_list.node_num++。
2. buffer_pool.size == node_num && evictable_num != 0 -> 做Evict然后做addNode。

  
void LRUKReplacer::RecordAccess(frame_id_t frame_id/*, [[maybe_unused]] AccessType access_type*/) {
  LRUKNode* node;
  if (his_node_store_.find(frame_id) != his_node_store_.end()) {
    // 如果在历史列表找到了，access_times++
    node = his_node_store_[frame_id];
    size_t times = node->get_access_times();
    if (times + 1 >= k_) {
      node->set_access_times(times+1);
      LRUKNode *tmp = node;
        
      // 这里的顺序翻一下就全错了!!!
      his_list.remove_node(node);
      buf_list.add_node(tmp);
        
      buf_node_store_[frame_id] = tmp;
        
      his_node_store_.erase(frame_id);

    } else {
      node->set_access_times(times + 1);
    }
  } else if (buf_node_store_.find(frame_id) != buf_node_store_.end()) {
    // 如果在缓冲列表找到了，移动到尾部
    node = buf_node_store_[frame_id];
    buf_list.move_node_to_tail(node); // 同上
  } else {
    // 如果是新帧，创建并加入历史列表
    node = new LRUKNode(frame_id);
    node->set_access_times(1);
    his_node_store_[frame_id] = node;
    if (replacer_size_ > node_num) {
      his_list.add_node(node);
      node_num++;
    } else if (replacer_size_ == node_num && curr_size_ != 0) {
      frame_id_t id;
      Evict(&id);
      his_list.add_node(node);
    }
  }
}

SetEvictable

先在history_list里找，如果发现节点的Evictable状态发生了变化那么就对LRUK_Cache和history_list的evictable_num做处理。
buffer_list同理。

  
void LRUKReplacer::SetEvictable(frame_id_t frame_id, bool set_evictable) {
  if (his_node_store_.find(frame_id) != his_node_store_.end()) {
    LRUKNode* node = his_node_store_[frame_id];
    if (node->is_evictable() != set_evictable) { // 如果状态发生了变化
      node->set_evictable(set_evictable);
      curr_size_ += set_evictable ? 1 : -1;
      if (set_evictable) {
        his_list.evictable_num++;
      } else {
        his_list.evictable_num--;
      }
    }
} else if (buf_node_store_.find(frame_id) != buf_node_store_.end()) {
    LRUKNode* node = buf_node_store_[frame_id];
    if (node->is_evictable() != set_evictable) { // 如果状态发生了变化
      node->set_evictable(set_evictable);
      curr_size_ += set_evictable ? 1 : -1;
      if (set_evictable) {
          buf_list.evictable_num++;
      } else {
          buf_list.evictable_num--;
      }
    }
  }
}

Task2 Disk Scheduler

这个组件负责在磁盘管理器上调度读写操作。

磁盘调度器可以被其他组件（在这种情况下，是任务3中的缓冲池管理器）用来排队磁盘请求，这些请求由一个DiskRequest结构体表示（已经在src/include/storage/disk/disk_scheduler.h中定义）。磁盘调度器将维护一个后台工作线程，负责处理已调度的请求。

磁盘调度器将使用一个共享队列来安排和处理DiskRequests。一个线程将请求添加到队列中，而磁盘调度器的后台工作线程将处理队列中的请求。我们已经在src/include/common/channel.h中提供了一个Channel类，以促进线程间数据的安全共享，但如果你认为有必要，也可以自由使用你自己的实现。

DiskScheduler的构造函数和析构函数已经实现，负责创建和加入后台工作线程。

TODO(only): /include/storage/disk/disk_scheduler.h src/storage/disk/disk_scheduler.cpp

Schedule(DiskRequest r): 安排一个请求给磁盘管理器执行。DiskRequest结构体指定了请求是用于读取还是写入，数据应该写入何处或从何处读取，以及操作的页ID。DiskRequest还包括一个std::promise，一旦请求被处理，其值应该被设置为true。
StartWorkerThread(): 后台工作线程处理已调度请求的启动方法。工作线程在1DiskScheduler构造函数中创建，并调用此方法。该方法负责获取队列中的请求并将其分派给DiskManager。请记住在DiskRequest的回调上设置值，以向请求发起者发出请求已完成信号。此方法不应返回，直到DiskScheduler的析构函数被调用。

helper function in src/include/storage/disk/disk_manager.h

DiskManager::ReadPage()
DiskManager::WritePage()

csdiy, cmu15445

database

本文由作者按照 CC BY 4.0 进行授权

Proj1:buffer_pool

概览

Task1 LRU-K Replacement Policy

Task2 Disk Scheduler

热门标签