CMU15-445 Lecture #05: Buffer Pools[译]
介绍(Introduction)
DBMS 负责管理其内存并从磁盘来回移动数据。因为在大多数情况下，数据不能直接在磁盘上操作，任何数据库都必须能够有效地将以文件形式表示的数据从磁盘移到内存中，以便能够使用这些数据。图 1 显示了这种互动的图示。理想情况下，从执行引擎的角度来看，它应该 “看起来 “像是所有的数据都在内存中。它不应该担心数据是如何被获取到内存中的。
另一种思考这个问题的方式是在空间和时间控制方面。
空间控制 是指页面写在磁盘上的哪个位置位置。空间控制的目的是使经常一起使用的页面在磁盘上 尽可能地靠近。
时间控制 是指何时将页面读入内存，何时将其写入磁盘。时间控制的目的是尽量 减少从磁盘上读取数据的停顿次数。
Locks vs. Latches
在讨论 DBMS 如何保护其内部元素时，我们需要对 locks 和 latches 进行区分。
Locks: 是一种用于保护数据库中的内容（例如元组、表、数据库）免受其他事务的干扰的高级别的逻辑原语。事务将在其整个持续时间内持有锁定。数据库系统可以在查询运行时向用户公开正在持有的锁定。锁定需要能够回滚更改。
Latches: 是 DBMS 在其内部数据结构（例如哈希表、内存区域）的关键部分使用的低级保护原语。 Latch 仅在进行操作的持续时间内被持有。Latch 不需要能够回滚更改。
缓冲池(Buffer Pool)
缓冲池是从磁盘读取的页面的内存缓存，本质上是在数据库内部分配的一个大型内存区域，用于存储从磁盘中获取的页面。
缓冲池的内存区域被组织成一个固定大小页面的数组，每个数组条目称为一 帧。 当 DBMS 请求页面时，它会从磁盘复制一个页面到缓冲池的其中一个帧中。当一个页面被请求时，数据库系统可以首先搜索缓冲池。仅当未找到页面时，系统才会从磁盘获取页面的副本。脏页会被缓冲，不会立即写回。请参见图 2 以了解缓冲池的内存组织图。
缓冲池元数据
缓冲池必须维护某些元数据，以便能够高效、正确地使用。
首先，页表是一个内存中的哈希表，用于跟踪当前在内存中的页面。它将页面 ID 映射到缓冲池中的帧位置。由于缓冲池中页面的顺序不一定反映在磁盘上的顺序，这个额外的间接层允许标识池中页面的位置。
注意：页表不应与页面目录混淆，页面目录是从页面 ID 映射到数据库文件中的页面位置的映射。所有对页面目录的更改都必须记录在磁盘上，以便数据库管理系统在重启时可以找到。
页表还会针对每一页维护额外的元数据，包括脏位标记和引用计数器。
每当一个线程修改一个页面时，它会设置dirty-flag，这表明存储管理器必须将页面写回磁盘。
引用计数器跟踪当前正在访问该页面的线程数（无论是读取还是修改）。线程在访问页面之前必须增加计数器。如果页面的引用计数大于零，则存储管理器不允许将该页面从内存中逐出。固定页面不会防止其他事务同时访问该页面。
内存分配策略
数据库为缓冲池的内存分配根据两种策略进行。
全局策略涉及到 DBMS 为整个工作负载做出的决策，考虑所有活动事务以找到最优的内存分配决策。
而另一种是本地策略，其决策会使单个查询或事务运行更快，即使这对整个工作负载不利。本地策略为特定事务分配缓冲区帧，而不考虑并发事务的行为。
大多数系统使用全局和本地视图的组合。
缓冲池优化(Buffer Pool Optimizations)
有许多方法可以优化缓冲池，以使其适应应用程序的工作负载。
多个缓冲池
DBMS 可以为不同的目的维护多个缓冲池（例如每个数据库缓冲池、每个页面类型缓冲池）。然后，每个缓冲池可以采用适用于其存储的数据的本地策略。这种方法有助于减少锁争用并提高局部性。
将所需页面映射到缓冲池的两种方法是对象标识符和哈希。
Object IDs（对象标识符）是将记录 ID 扩展为具有对象标识符的过程。通过对象标识符，可以维护从对象到特定缓冲池的映射关系。
另一种方法是 哈希，其中 DBMS 将页面 ID 哈希以选择要访问的缓冲池。
预取
DBMS 还可以通过基于查询计划预取页面进行优化。在处理第一组页面时，第二组页面可以被预取到缓冲池中。当访问许多页面时，DBMS 通常会使用这种方法进行顺序访问。缓冲池管理器还可以预取树状索引数据结构中的叶子页面。
扫描共享（同步扫描）
查询下标可以重用从存储中检索到的数据或操作计算得到的数据。这允许多个查询附加到扫描表的单个下标上。如果一个查询开始扫描并且已经有一个查询在执行此操作，则数据库管理系统将第二个查询的下标附加到现有的下标上。数据库管理系统会跟踪第二个查询加入到第一个查询的位置，以便在达到数据结构的末尾时完成扫描。
缓冲池绕过
顺序扫描运算符不会将已获取的页面存储在缓冲池中，以避免开销。相反，内存是针对正在运行的查询本地化的。如果运算符需要读取在磁盘上连续的大量页面，则此方法效果良好。缓冲池绕过也可用于临时数据（如排序、连接）。
OS 页面缓存(OS Page Cache)
大多数磁盘操作都通过 OS API 进行。除非显式指定，否则操作系统会维护自己的文件系统缓存。
大多数 DBMS 使用直接 I/O 以绕过操作系统缓存，以避免页面的冗余拷贝和管理不同的驱逐策略。
Postgres是使用操作系统页面缓存的数据库系统的一个例子。
缓冲区更换策略(Buffer Replacement Policies)
当 DBMS 需要释放一个帧以为新页腾出空间时，它必须决定从缓冲池中驱逐哪一页。
替换策略是一个算法，DBMS 实现该算法来决定从缓冲池中驱逐哪些页面以腾出空间。
替换策略的实现目标包括改进正确性、准确性、速度和元数据开销。
LRU
最近最少使用（Least Recently Used，LRU）替换策略维护了每个页面最后一次访问的时间戳。数据库管理系统选择驱逐具有最老时间戳的页面。该时间戳可以存储在单独的数据结构（例如队列）中，以便进行排序，并通过减少驱逐时的排序时间来提高效率。
CLOCK
CLOCK 策略是 LRU 的一种近似，无需每个页面单独使用时间戳。在 CLOCK 策略中，每个页面都被赋予一个参考位。当页面被访问时，参考位被设置为 1。为了可视化这一过程，将页面组织成一个循环缓冲区，并配有一个“时钟指针”。在扫描期间，检查页面的参考位是否被设置为 1。如果是，则将其设置为 0；如果不是，则将其驱逐。通过这种方式，时钟指针在驱逐之间记住了位置。
Alternatives
LRU 和 CLOCK 替换策略存在多个问题。
其中，LRU 和 CLOCK 容易受到 顺序洪泛攻击，即由于顺序扫描而导致缓冲池的内容被破坏。由于顺序扫描快速读取许多页面，缓冲池被填满，并且其他查询的页面被驱逐，因为它们具有更早的时间戳。在这种情况下，最近的时间戳不准确地反映了我们实际想要驱逐的页面。
有三种 LRU 和 CLOCK 策略缺陷的解决方案。
1. LRU-K，它跟踪最后 K 次引用的历史记录作为时间戳，并计算相邻访问之间的间隔。使用此历史记录来预测下一次访问页面的时间。
2. 每个查询的本地化。DBMS 基于每个事务/查询选择要驱逐的页面。这最小化了每个查询对缓冲池的污染。
3. 优先级提示允许事务基于查询执行期间每个页面的上下文告诉缓冲池页面的重要性。
脏页
处理具有脏位的页面有两种方法。最快的选项是放弃缓冲池中未被修改的任何页面。较慢的方法是将脏页写回磁盘，以确保其更改得以持久化。这两种方法说明了快速驱逐与写入不会再次被读取的脏页之间的权衡。
避免不必要地写出页面的问题之一是通过后台写入。通过后台写入，数据库管理系统(DBMS)可以定期遍历页面表，并将脏页写回磁盘。当脏页被安全地写入后，DBMS 可以将页面驱逐或仅取消脏标志。
避免不必要地编写页面的问题的一种方法是后台写入（background writing）。通过后台写入，DBMS 可以定期遍历页面表，并将脏页面写入磁盘。当脏页面安全地写入后，DBMS 可以将页面驱逐（evict）出内存，或者只是取消脏标志（dirty flag）。
其他内存池(Other Memory Pools)
DBMS 需要内存来存储元组和索引之外的其他内容。这些其他的内存池根据实现可能并不总是由磁盘支持。
其中包括：
- 排序和连接缓冲区
- 查询缓存
- 维护缓冲区
- 日志缓冲区
- 字典缓存。