CMU15445Lab1缓冲池管理器

缓冲池管理器

  • 可扩展哈希表

  • LRU-K淘汰算法

  • 缓冲池

可扩展哈希 extendible hashing

是一种动态哈希方法，其中目录和桶被用于哈希数据。可扩展哈希是一个有力的灵活的方法，其中哈希函数也经历动态的改变。

  • 目录 directories

    目录在指针中存储桶的地址，每个目录被分配一个id，每次目录扩张时，id可能会发生变化

  • 桶 buckets

    被用于哈希真实数据

基本结构

image-20230822154859503

  • 目录: 这个容器存储指向桶的指针。每个目录给定一个唯一的id，当扩张发生时id可能随之改变。哈希函数返回这个目录的id，这个id被用来指向合适的桶。

  • 桶: 它们存储哈希键。目录指向桶。如果局部深度小于全局深度时，一个桶可能包含不止一个指针指向它。

  • 全局深度：它跟目录相关联。它们表示哈希函数使用的比特位数目去分类这些键。全局深度=目录id的比特位数。
  • 局部深度：和全局深度类似，除了局部深度是跟桶关联，而不是跟目录。当桶溢出发生时，局部深度根据全局深度去决定执行的行为。局部深度通常小于等于全局深度。
  • 桶分裂：当桶的元素超过了特定的大小，那么桶分裂成两个部分。
  • 目录扩容：当桶溢出时，产生目录扩容。当溢出桶的局部深度等于全局深度时，目录扩容被执行。

基本工作流程

  • step1 分析数据元素

    数据元素可能以各种形式存在，比如整型字符串浮点数等，这里我们只考虑整型这类元素 比如49

  • step2 转换成二进制形式

    考虑ASCII码的对应整数，转化成二进制形式，比如49，他的二进制形式为110001

  • step3 检查目录的全局深度

    假设全局深度为3

  • step4 识别目录

    考虑在二进制下最低全局深度位去匹配目录id，如果二进制是110001，取他最后三位为001

  • step5 导航

    访问目录id=001指向的桶

  • step6 插入和溢出检查

    插入元素并检查桶是否溢出，如果遇到溢出转向步骤7和8，否则转到步骤9

  • step7 处理数据插入过程中的溢出情况

    很多情况下，当在桶里插入数据时，可能发生桶溢出，我们要采取以下流程去避免误操作数据，首先要检查局部深度是否小于或等于全局深度

    • case1 如果溢出桶的本地深度等于全局深度，那么需要执行目录扩张和桶分裂，全局深度和局部深度的值增加1，并指定合适的指针
    • case2 如果本地深度小于全局深度，仅仅发生桶分裂，将局部深度增加1即可，指定合适的指针

  • step8 分裂桶的元素重新哈希

    元素根据目录的全局深度进行重新哈希

  • step9 元素被成功哈希

具体例子

  1. 16,4,6,22,24,10,31,7,9,20,26 共11个元素将要被哈希

  2. 假设桶大小为3

  3. 哈希函数：全局深度为X，则哈希函数返回X的最低位

实际操作：

  1. 首先，计算每个给定数值的二进制形式。
  • 16- 10000
  • 4- 00100
  • 6- 00110
  • 22- 10110
  • 24- 11000
  • 10- 01010
  • 31- 11111
  • 7- 00111
  • 9- 01001
  • 20- 10100
  • 26- 11010

  1. 全局深度和局部深度初始化为1，如图所示：

    image-20230822161828264

  2. 插入16 16是10000，全局深度是1，所以映射到id=0的目录

    image-20230822162628674

  3. 插入4和6 一样

    image-20230822163136751

  4. 插入22 末尾也是零，但是桶大小为3，已经溢出了，根据step7-case1指导，局部深度=全局深度，桶分裂且目录扩张，分裂之后重新哈希分裂溢出桶中的数值，现在全局深度为2,16、4、6、22被重新哈希为最低2位 [ 16(10000),4(100),6(110),22(10110) ]

    image-20230822163426433

    注意，未溢出的桶存在没有触及的。但是，因为目录的数量已经翻倍，我们现在有2个目录01和11指向了同一个桶。这是因为桶的局部深度保持为1。并且，任何局部深度小于全局深度的桶会被不止一个目录指向。

  5. 插入 24 and 10: 24(11000) 和 10 (1010)基于目录id 00和10可以被哈希。此处，我们没有遇到溢出的情况。

    image-20230822163630854

  6. 插入 31,7,9,所有这些元素[ 31(11111), 7(111), 9(1001) ] 在最低2位要么01，要么11。因此，我们映射到01和11对应的桶。我们没有遇到任何溢出的情况

    image-20230822163717413

  7. 插入20 插入元素20 (10100) 时再一次遇到了溢出问题。

    20插入的桶被00所指向。正如Step 7-Case 1提示的那样，因为桶的局部深度=全局深度，目录扩张和桶分裂发生了。在溢出桶中的元素在新的全局深度下重新哈希。现在，新的哈希表如下

    image-20230822164041381

  8. 插入26，桶发生了溢出，并且按照Step 7-Case 2的指示，因此桶的局部深度小于全局深度（2<3），目录不会翻倍，仅仅是桶分裂和元素重新哈希。最后，哈希给定数值列表的结果已经获得。

image-20230822164136004

易错点

  • vector初始时没扩容
  • 插入的时候，直接根据哈希的id判断是否重复。这是错误的❎。因为没有扩容之前，1和3最低1位映射的结果都是1，所以这里直接替换了，而没有新增。我们期望的是插入3的时候扩容加分类，实现新增，而不是替换。
  • find(key, value)如果找到是把数据存到value中，注意这里的value是个入参。
  • remove的时候，要把扩容的点指向共同的桶，比如001和101扩容到三位时，需要同时指向01这个目录id下面，因为在没有分裂之前，存在旧数据未正确哈希。
  • 并发原则：读的时候加锁，写的时候加锁。

LRU-K

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

工作原理

相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。详细实现如下：

(1). 数据第一次被访问，加入到访问历史列表；

(2). 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；

(3). 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；

(4). 缓存数据队列中被再次访问后，重新排序；

(5). 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即：淘汰“倒数第K次访问离现在最久”的数据。

实际应用中LRU-2是综合各种因素后最优的选择，LRU-3或者更大的K值命中率会高，但适应性差

实现方法

历史队列

  • 历史队列中的数据为第一次访问时的数据，只要未达到k次访问频率，位置一直保持不变
  • 实现的数据结构为双向链表+哈希表
  • 淘汰策略为FIFO

缓存队列

  • 大于等于k次的访问频率，需要根据最近的访问时间切换元素在队列中的位置，类似LRU
  • 实现数据结构 双向链表+哈希表
  • 淘汰策略 LRU

缓冲池

BufferPoolManagerInstance 实现将使用前面步骤中创建的 ExtendibleHashTable 和 LRUKReplacer 类。 它将为将 page_id 映射到 frame_id 的表使用 ExtendibleHashTable。 它还将使用 LRUKReplacer 来跟踪访问 Page 对象的时间，以便它可以决定在必须释放框架以腾出空间从磁盘复制新物理页面时驱逐哪个对象。

  1. 执行引擎需要#2号页，找缓冲池去要。
  2. 缓冲池说，我们没有，我要去从磁盘读。
  3. 从磁盘读入数据到缓冲池。
    1. 缓冲池有足够空间，直接放入。
    2. 缓冲池空间不够，替换算法，选择一个页淘汰。
      i.没脏。直接替换。
      ii．脏了。先写入磁盘，再替换。
  4. 然后再把#2号页给执行引擎。

易错点

  • new和fetch时，从替换器中驱逐页后没有在page_table中将对应的page_id驱逐