DBS note4：Buffer Management

1、介绍

2、缓冲池

3、处理页面请求

4、LRU替换和时钟策略

1）顺序扫描性能 - LRU

5、最近最常使用替换策略（MRU Replacement）

1）Sequential Scanning Performance - MRU

6、练习题

1）判断真假

2）LRU、MRU、Clock相关问题

1、介绍

我们前面简略讨论了 DBMS 的最低级别如何管理磁盘空间，以及基于页面的数据库系统中如何管理文件和索引。现在，我们将探讨 DBMS 中这两个级别之间的接口 - 缓冲区管理器（the buffer manager）。

缓冲区管理器负责管理内存中的页面，并处理文件和索引管理器的页面请求。请记住，内存空间是有限的，因此我们无法负担得起将所有页面存储在缓冲池中。缓冲区管理器负责淘汰策略，即在空间填满时选择淘汰哪些页面。当页面从内存中淘汰或新页面读入内存时，缓冲区管理器会与磁盘空间管理器通信，执行所需的磁盘操作。

2、缓冲池

内存通过将空间划分为页面可以放置的帧而转化为缓冲池。一个缓冲帧可以容纳与一个页面相同量的数据（因此一个页面完美地适应一个帧）。为了有效跟踪帧，缓冲区管理器在内存中为元数据表分配了额外的空间。

该表追踪了4个信息：

1. 与内存地址唯一关联的 “框架ID”
2. 用于确定框架当前包含哪个页面的 “页面ID”
3. 用于验证页面是否已被修改的 “脏位”
4. 用于跟踪当前使用页面的请求者数量的“Pin计数”

3、处理页面请求

当从缓冲管理器请求页面并且页面已经存在于内存中时，页面的引用计数会递增，并返回页面的内存地址。

如果页面不在缓冲池中且仍有空间，将找到下一个空框架，并将页面读入该框架。页面的引用计数设置为1，并返回页面的内存地址。在页面不存在且没有空框架的情况下，必须使用替换策略确定要驱逐的页面。

替换策略的选择在很大程度上取决于页面访问模式，并通过计算页面命中次数选择最优策略。页面命中是指可以在内存中找到请求的页面而无需访问磁盘。每个页面未命中会产生额外的IO成本，因此良好的淘汰策略对性能至关重要。访问模式的命中率定义为#页面命中次数 / (#页面命中次数 + #页面未命中次数)，或更简单地说，#页面命中次数 / #页面访问次数。

此外，如果被驱逐的页面的脏位被设置，则将页面写入磁盘以确保更新被持久化。如果在内存中对页面进行更新，则将脏位设置为1。一旦页面被写回磁盘，脏位就被设置为0。

一旦请求者完成其工作负载，它负责通知缓冲管理器减少其先前使用的页面的引用计数。

4、LRU替换和时钟策略

一个常用的替换策略是 LRU（最近最少使用）。当需要将新页面读入已满的缓冲池时，将淘汰最近最少使用、引用计数为 0 且 "Last Used" 列具有最低值的未固定页面。为了追踪页面的使用情况，在元数据表中添加了一个 "Last Used" 列，用于记录页面引用计数减少的最新时间。LRU 是一个有效的策略选择，因为它会保留常被访问的页面在内存中，由于它们经常被访问，因此很可能是最近使用的。

实现 LRU 通常可能成本较高。时钟策略提供了一种替代实现，它使用元数据表中的一个 ref bit（最近被引用）列和一个时钟手变量来高效地近似 LRU。使用 ref bit 可以降低空间和时间成本。只需每个框架一个比特，而不是多个比特来存储 Last Used 值。在时间方面，缓冲管理器只需跟随clock hand。在 LRU 中，缓冲管理器必须花费时间搜索 Last Used 列中的最小值。

时钟策略算法将元数据表视为帧的循环列表。它在开始时将时钟手设置为第一个未固定的帧，并在将每个页面最初读入帧时将其相应行的ref bit设置为1。该策略在尝试淘汰时的工作方式如下：

1. 遍历表中的帧，跳过固定的页面，并在到达末尾时绕回到帧0，直到找到第一个未固定且ref bit = 0的帧。

2. 在每次迭代期间，如果当前帧的ref bit = 1，则将ref bit设置为0并将时钟手移动到下一个帧。

3. 在到达ref bit = 0的帧时，淘汰现有页面（如果dirty bit被设置，则将其写入磁盘；然后将dirty bit设置为0），读取新页面，将帧的ref bit设置为1，并将时钟手移动到下一个帧。

如果访问当前在缓冲池中的页面，则时钟策略将页面的ref bit设置为1而不移动时钟手。