随笔分类
Buffer Replacement Policy
Buffer 池中页面的置换策略
通常关注于:
-
正确性
确保要移除的 page正在被读取
-
精确性
确保要移除的页面是在未来不太会被用到的那些 pages,以此来减少磁盘寻道的数量
-
速度
当我们在访问 page table时会持有 latch,我们并不希望运行哪种算法来找到要被移除的 page,因为这耗时可能会多余实际访问 page
-
元数据的开销
我们并不想要去拥有大量元数据带来的开销,也不想去跟踪所有这些额外数据
如:跟踪单个 page的元数据本身大于该 page,这显然是我们不想看到的结果
LRU
Least Recently Used,最近最少使用算法
跟踪页面最近一次被访问的时间戳,即 最老时间戳的 page理应被置换出去
可以通过维护一个单独的数据结构:如 Queue(FIFO,根据 page的时间戳进行排序)
- 这就避免了为了找到应被置换出去的 page而线性遍历 buffer pool所带来的开销
Clock便是 LRU的近似算法实现
Clock
LRU的近似算法(并非是去移除最老的时间戳的页面,而是移除某一时间范围内的 reference bit == 1的 page)实现
不去跟踪 page最近被访问的时间戳,相反,唯一需要跟踪的信息就是 每个 page的标志位 (reference bit)
通过此标志位可以得知,自从上一次检查该 page后,此 page是否有被访问
因此,我们要将 page组织为一个环形的 buffer,就像是一个时钟那样
- 核心:在某个时间段内,即一圈时钟,如果某 page的标志位没发生变化,便可以从 buffer pool中移除该 page
- 通过一个能够旋转的指针,其能够去检查 page的标志位是被设置成 1 还是 0,如果被设置为了 0,即意味着子上一次检查后该 page就没在被访问,so 可以将该 page从 buffer pool中移除
shortcoming
事实上,LRU和 Clock都对 Sequtial Flooding(顺序扫描)敏感
有些查询,会去执行一个按顺序进行的、可以读取每一页的扫描
此时,在 LRU和 Clock中 实际上保存的是最近使用的 page
对于 Sequtial Flooding,可能仅用于单个点的查询,为此将其它 page移除,显然是不正确的,即 最近使用的页面实际上是最不需要的页面
LRU-K
用于解决 LRU "缓存污染"
k:需要对于单个 page对于缓存数据的访问进行计数的次数
核心思路:将最近使用过 1次扩展为最近使用过 k次,也就是说没有达到 k次访问的数据并不会被缓存起来,访问记录不能无限记录(达到指定时间间隔会将 page的访问次数置为 0,再去 + 1),当达到 k次访问时,将数据索引从历史队列移到缓存队列中
- 使用历史记录来预测下一次访问该页面的时间,以来帮助我们更好地判断哪儿个page应该被移除
Buffer Policy:Localization
使用多个缓冲池,让每个查询本地化
跟踪每个查询来选择要删除的 page,对于某个处查询而言,这便是最近最少使用的 page,因此可将其移除
这样可以最小化每个查询对 buffer pool带来的污染
Buffer Policy:Priority Hints
使用优先级提示
DBMS知道查询期间每个页面的上下文,它可以为缓冲池提供关于页面是否重要的 hints
dirty pages
每个 page上都对应一个 dirty bit,便是该 page读进内存后是否有被修改过
对于 dirty page,是不能被置换出去的,即不能被丢弃 (drop)
-
如果 page是 dirty的话,在我们可以将该空间重新用于新的 page之前,我们必须将其安全地写回磁盘:这是一种比较缓慢的方式
这种方式就需要两次 磁盘 I/O了
-
比较快的置换 page:快速找到 buffer池中不是 dirty的 pages,将其置换出去,然后将一个新的 frame放在 buffer pool的这个位置
事实上,快速置换以及 dirty pages的 refresh之间的权衡,是很难做得到的
为了解决必须要将 page写出以便在 buffer池中释放可用空间的问题,引入了 后台写入
Background Writing
后台写入
在 DBMS中有一个定时任务的线程,其定期去扫描 buffer池中的 dirty pages,将其写回磁盘上,将对应的 pages设置为 clean状态,即可以被置换出去的状态
- 在 dirty pages写回到磁盘之前,必须要确保对应修改的日志操作已经先写回到磁盘中去了