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而不移动时钟手。

1）顺序扫描性能 - LRU

LRU 总体上表现良好，但在一组页面 S（其中 $|S| >$ 缓冲池大小）被多次重复访问时，性能会受到影响。这种访问模式称为顺序淹没，经常在数据库工作负载中出现，比如在表中扫描每个记录。

为了突显这一点，请考虑一个使用 LRU 的 3 帧缓冲池，具有以下访问模式：

A B C D A B C D A B C D A B C D

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

另一个常用的替换策略是 MRU（最近最常使用）。与淘汰最近最少使用的未固定页不同，MRU 策略淘汰最近最常使用的未固定页，根据页面的固定计数最后一次减少的时间来衡量。

1）Sequential Scanning Performance - MRU

起初使用这种策略可能会显得违反直觉，但考虑一个使用 MRU 的 3 帧缓冲池的访问模式：

A B C D A B C D A B C D A B C D

显然，在发生顺序淹没访问模式时，MRU 在页面命中率方面远远优于 LRU。

6、练习题

1）判断真假

a. 缓冲池中的每个帧都是一个磁盘页面的大小。

真。帧的大小被定义为磁盘页面的大小。

b. 缓冲管理器代码（而不是文件/索引管理代码）负责设置页面的脏位。

假。页面的请求者（文件/索引管理代码）设置脏页。

c. 脏位用于跟踪页面的受欢迎程度。

假。脏位用于跟踪页面在写回磁盘之前是否已被修改。引用计数用于跟踪受欢迎程度。

d. 使用LRU策略时，引用位用于在替换页面之前为页面提供“第二次机会”留在内存中。

假。引用位不用于LRU策略。它们用于时钟策略。

e. 对文件进行顺序扫描时，当文件小于缓冲池时，使用MRU或LRU将具有相同的命中率（从空缓冲池开始）。

真。由于我们可以将所有页面放入内存，因此在顺序扫描期间我们不需要驱逐页面。

f. 页面的引用计数只能由缓冲管理器递减。

假。引用计数由请求页面的人递减，表示他们已经使用完毕。

2）LRU、MRU、Clock相关问题

对于以下问题，我们有一个初始为空的缓冲池，其中有4个缓冲帧。对于访问模式：

A B D D E A E C A B C A E

a. LRU的命中率是多少？

b. 当LRU完成时，缓冲池中有哪些页面？

c. MRU的命中率是多少？

d. 当MRU完成时，缓冲池中有哪些页面？

e. Clock的命中率是多少？

f. 当Clock完成时，缓冲池中有哪些页面？

详细的访问模式如下图所示。在 LRU 和 MRU 中，行数对应于缓冲帧的数量，每列对应于一个单独的访问，其中字符表示缺失，星号表示命中。

a. 7/13

b. A, C, B, E

c. 7/13

d. E, B, D, C

e. 6/13

f. C, A, B, E

以上，DBS note4：Buffer Management

祝好。