Buffer Pool

这个lab三个部分，先实现一个extendible hashtable，然后实现一个lru-k替换器，最后利用这两个东西实现一个buffer pool manager。

Extendible Hashtable

此处放一个很好的介绍：

Extendible Hashing (Dynamic approach to DBMS) - GeeksforGeeks

基本介绍

哈希表，初始长度为0，每次增长长度都增长到原来的一倍，也就是表的长度是2^n。表的每个位置放一个指针，指向对应的bucket（一个list的封装）。

这个n就是表的global_depth，同时每个bucket又有一个local_depth，这个local_depth代表的是该桶实际所在的depth，例如global_depth是2，一个桶的local_depth是1，index是3，则这个bucket的实际深度只有2^1=2，也就是实际位置并不在index 3而在index 1，index 3和index 1指向的是同一个bucket。而当这个桶放满之后，就需要重新分配数据，增加local_depth到2，然后index3放一个桶，index1放一个，现在这两个桶的实际深度和表深度一致了。

此外这个depth还代表着所要取的hash值的位数。还是以刚刚的为例，global_depth决定往哪个index插入：一个key进来计算（hash值%global_depth）得到3，也就是要插入index 3 这个位置的桶（现在这个桶实际上是index 1上的桶，local_depth是1，但是无所谓，还是要插在这里）。那local_depth有什么用？这里有一个约束：多个key放在一个桶中时，其hash值%local_depth得到的是相同的，所以当这个bucket满的时候，local_depth增加，我们也要根据新的local_depth分配它们是去到哪个桶，来保证约束的不变。

相关操作

查找：

  • key计算hash值再%global_depth 得到对应的index，再找到对应bucket的指针。
  • 找到指针指向的bucket，遍历查找key，找到返回对应值和true，找不到返回false。

删除：

删除不需要缩小表，也不需要回收bucket，所以实际上和查找一样简单

  • key计算hash值再%global_depth 得到对应的index，再找到对应bucket的指针。
  • 找到对应bucket，遍历查找，找到就删除并返回true，找不到返回false。

插入：

插入比较复杂，主要是需要涉及重新分配bucket中的key和重新设置bucket指针。

  • key计算hash值再%global_depth 得到对应的index，再找到对应bucket的指针。

  • 找到对应bucket，遍历查找，找到的话，更新value，直接返回即可

    • 没找到->需要进行插入 ：如果bucket没满，很简单，直接push_back()，就可以返回了

      • Bucket 满了->需要先重分配bucket里面的值，然后重新分配bucket指针，然后再重新插入。

        • 先检查满的这个bucket的local_depth和global_depth，如果相等的话，我们在进行分配前，需要先增加global_depth的值，将表扩大一倍（复制一份原来的表，附在原来表后面，这样就是对应的）。

        • 如果local_depth小于global_depth，那么不需要增加表。

        • 分裂bucket和重新分配内容

          • 增加当前bucket的local_depth
          • 新构造一个bucket
          • 对于老bucket中的元素，用新的local_depth%hash值，如果和老hash值相同，则还放在老bucket中，如果不同，放入新bucket。

        • 现在需要重新设置bucket指针。

          • 新local_depth值对应的index需要放新bucket，老local_depth对应的index处需要放老bucket

          •   // 我觉得这块蛮妙的
  auto n = 1 << (global_depth_ - newdepth);
  for (int i = 1; i < n; i++) {
    auto index1 = (i << newdepth) + oldindex;
    auto index2 = (i << newdepth) + newindex;
    dir_[index1] = bucket;
    dir_[index2] = newbucket;
  }

      • 现在分配完毕，重新尝试插入，但是这次插入也不一定能成功完成（有可能重新分配bucket内值的时候，还是全部分配到了一个bucket中去），所以我们需要一个循环。

LRU-K Replacement Policy

外部调用时，会传入对应的frame_id，replacer需要记录并在必要时驱除。

理解

The LRU-K algorithm evicts a frame whose backward k-distance is maximum of all frames in the replacer. Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access. A frame with less than k historical accesses is given +inf as its backward k-distance. When multipe frames have +inf backward k-distance, the replacer evicts the frame with the earliest timestamp.

一定不要贸然的开始work，先search、理解、理论设计，完善之后再去coding

这里说的很清楚了，LRU-K算法所要驱除的page是具有最大backward k-distance的page，计算方式是计算倒数第k次访问和当前时间戳的差值，或者访问次数没有达到K次，就为inf（第一次理解竟然可以理解成计算平均值？我真佩服当时的自己）。

实际上是有paper的

img

paper的意思是说，有一个访问操作的序列，backward k-distance也就是每个操作倒数第k次的访问或者不足则为inf。我们设计的时候，可以不维护这个操作队列，扫描的过程耗时比较多，但是总之搞明白什么是这个backward k-distance是很重要的。

我们要驱除的页面也就是backward k-distance最大的页面，但是需要注意的是，对于不足k次访问的页面，backward k-distance都是inf，这样的话该驱除哪个？要求是驱除 the frame with the earliest timestamp.

replacer实际上是一个frame_id的维护器，维护0-replacer_size个frame_id 用于分配和回收。

设计

  • 一个访问次数不足k次的队列，根据页面的最早timestamp维护，当访问次数达到k次，则放入另一个队列
  • 一个访问次数达到k次的队列，根据页面的最早timestamp维护，当又有访问时更新位置
  • 每个frame，需要将最后一个访问记录的时间戳当做其时间戳；需要维护最后的k次访问的list，当有新的访问时，访问记录插入在开头，当访问记录达到k次时，删除最后一个访问记录，同时将新的最后一个设置为其时间戳，并更新其在满足k次访问的队列中的位置；需要记录其是否可以被evict，当不可以时，需要将其从两个队列中移除，可以驱逐时才加入。（封装成一个结构体）
  • 一个hashtable，方便找到对应的frame

实现

需要维护一个全局的timestamp，从0开始，每当发生一个Recordaccess，递增timestamp

RecordAccess: 传入frame_id

  • 对于该frame_id，从hashtable中查找对应的frame
    • 没找到：
      • 创建一个新的frame，evictable为false；timestamp设置为当前timestamp；list插入当前的timestamp
    • 找到：
      • 如果frame中的list的size还没达到k，只需要将当前timestamp 头插进去
        • 检查evictable，如果为true，需要处理队列
          • 如果当前list已经达到k，则需要从不足k次的队列中删除并插入到满足k次的队列的合理位置。
          • 如果list没达到k，则无需更改。
      • 如果frame中的list已经达到k个元素，则头插当前timestamp，尾删除最后一个，并设置其timestamp为当前timestamp
        • 检查evictable，如果为true，需要查找满足k次访问的list，并更新其位置。
  • 最后还得++一下current_timestamp

对于更快速的找到和遍历list中的值，cppreference中有如下说明：

Adding, removing and moving the elements within the list or across several lists does not invalidate the iterators or references. An iterator is invalidated only when the corresponding element is deleted.

迭代器在元素插入删除时不受影响，除非删除对应的元素，所以我们完全可以维护一个迭代器在frame中，方便我们快速的找到对应的元素。

SetEvictable:

  • 对于该frame_id，从hashtable中查找对应的frame
  • 没找到直接返回
  • 找到：
    • 设置frame对应的evitable为true或者false
      • 从true到false的话，从对应的队列中删除。
      • 从false到true的话，放入对应的队列。

Remove:

  • 查找
  • 检查frame是否evitable
    • false：报错
    • true：从对应队列中删除，从hashtable中删除。

Evict:

  • 检查less_k_list_，如果size不为0，则删除list的头节点
  • less_k_list为空时才检查k_list，也是删除list头节点。

Buffer Pool Manager Instance

理解

Buffer pool的组成大概包含：frame、page、disk_manager，首先需要明白这些东西的含义是什么

  • frame：LRU-K中所用的就是frame_id，它代表的是buff_pool实际管理的内存页，所以它的大小也就是buffer pool的size
  • page：实际存储数据的内存页，buffer pool实际管理size个存储内存的内存页，也就是frame，page可以理解成一页内存，存在frame上
    • Page_id：从0开始递增，用来标识数据页，当数据页被写入磁盘之后，还可以使用原来的page_id找到；当分配一个新的数据页的时候，需要递增当前的page_id来标识新的页。它需要和frame_id做区分，frame_id是标识buffer pool维护的，用于缓存的内存页，所以它的取值也就是从0到buffer pool的size，但是page_id则是代表实际的一页数据，它可以无限递增（因为可以存在磁盘上），所以page_id从0到无限递增。
    • 总结：buffer pool维护size个frame（实际上是内存条上的size个page块）用于缓存page。page的概念是虚的，标识实际的一页内存，它会存在内存，也可能存在磁盘。
  • disk_manager：用于管理实际磁盘存储的page，这里使用读和写的两个接口

现在再回过头看一下主要的几个api

  • FetchPgImp(page_id)：也就是要找到page_id对应的数据页，则如果已经在buffer pool的frame中，返回对应的frame。如果不在，从磁盘上读取，从buffer pool中找一个frame存数据，返回这个frame。
  • UnpinPgImp(page_id, is_dirty)：告诉buffer pool不再使用这个frame和是否对frame做了修改
  • FlushPgImp(page_id)：将page_id对应的数据页对应的frame的更改刷新到磁盘去。
  • NewPgImp(*page_id)：申请一个新的数据页，则需要分配新的page_id，并找一个frame承载，同时返回frame。
  • DeletePgImp(page_id)：删除一个数据页，所以要从buffer pool中的frame中删除，还要从磁盘上释放（在没有被pin时）。
  • FlushAllPagesImpl()：将frame中的所有page刷新到磁盘中去。

最后做几点说明

  • lru_replacer用于记录frame的访问和在必要时evict
  • page没有pin的操作，这是因为当new或者fetch一个page是会自动pin。pin对应着在lru中设置不可驱逐，但是unpin只有在pin值为0时才设置lru为可驱逐。

实现

实现上，感觉无需详细说明流程了，理解了之后实现并不难，因为不是很考虑算法的部分。在此记录几点关键。

  • UnpinPgImp的is_dirty不能直接设置给page，它只代表某个进程是否对其进行修改，所以直接设置的话，可能将其他进程的true覆盖成false。
  • buffer_pool维护一个free_list，代表没有使用的frame。当需要一个frame的时候，先在free_list中查找，找不到才需要lru-k驱逐。驱逐时还需要注意将脏页写回磁盘。