CMU15445-lecture6
第六课：缓冲池
1 介绍
DBMS负责管理其内存并在磁盘上来回移动数据。由于在大多数情况下，数据无法直接在磁盘中进行操作，因此任何数据库必须能够有效地将表示为文件的数据从磁盘移动到内存中，以便可以使用。交互的示意图如图一所示。理想情况下，从执行引擎的角度来看，它应该“看起来”好像所有数据都在内存中。它不必担心如何将数据提取到内存中。
思考这个问题的另一种方式是从空间和时间控制的角度来考虑。
空间控制是指页面在磁盘上物理写入的位置。空间控制的目标是使经常一起使用的页面在磁盘上尽可能物理地靠近。
时间控制是指何时将页面读入内存以及何时将其写入磁盘。时间控制旨在最大限度地减少因必须从磁盘读取数据而导致的停顿数量。
2 Locks vs. Latchs
在讨论DBMS如何保护其内部元素时，我们需要区分locks和latchs
Locks：锁是一种更高级别的逻辑原语，可保护数据库的内容（例如元组、表、数据库）免受其他事务的影响。事务将在其整个持续时间内保持锁定。数据库系统可以向用户公开在运行查询时持有哪些锁。需要能够回滚更改。
Latchs：latch是一种低级保护原语，DBMS用于其内部数据结构（例如哈希表、内存区域）中的关键部分。Latchs仅在执行操作期间被保持。不需要能够回滚更改。
3 缓冲池
缓冲池是从磁盘读取的页面的内存缓存。它本质上是在数据库内部分配的一个大内存区域，用于存储从磁盘获取的页面。
缓冲池的内存区域组织为固定大小页面的数组。每个数组条目称为一个帧。当DBMS请求一页时，会将其从磁盘复制到缓冲池的其中一个帧。当一个页面被请求时，数据库系统能先查找缓冲池。只有这个页面没有找到时，系统才会从磁盘中获取这个页面的一个copy。脏页被缓冲并且不会立即写回。缓冲池的内存组织图见图 2。
缓冲池元数据
缓冲池必须维护某些元数据才能有效且正确地使用。
首先，页表是内存中的哈希表，用于跟踪当前内存中的页面。它将页面 ID 映射到缓冲池中的帧位置。由于缓冲池中页面的顺序不一定反映磁盘上的顺序，因此这个额外的间接层允许识别池中的页面位置。
注意：不要将页表与页目录混淆，页目录是从页 id 到数据库文件中页位置的映射。对页目录的所有更改都必须记录在磁盘上，以便 DBMS 在重新启动时能够找到。
页表还维护每页的附加元数据、脏标志和引脚/引用计数器。
每当线程修改页面时，都会设置脏标志。这向存储管理器表明该页必须写回磁盘。
引脚/引用计数器跟踪当前正在访问该页面（读取或修改它）的线程数。线程在访问页面之前必须增加计数器。如果页面的引脚计数大于零，则不允许存储管理器从内存中逐出该页面。固定不会阻止其他事务同时访问该页面。
内存分配策略
数据库中的内存根据两种策略分配给缓冲池。
全局策略涉及 DBMS 应该做出的决策，以使正在执行的整个工作负载受益。它考虑所有活动事务以找到分配内存的最佳决策。
另一种选择是本地策略，它做出的决策将使单个查询或事务运行得更快，即使这对整个工作负载不利。本地策略将帧分配给特定事务，而不考虑并发事务的行为。
大多数系统结合使用全局视图和局部视图。
4 缓冲池优化
有多种方法可以优化缓冲池以适应应用程序的工作负载。
多缓冲池
DBMS 可以出于不同目的维护多个缓冲池（即每个数据库缓冲池、每个页面类型缓冲池）。然后，每个缓冲池都可以采用针对存储在其中的数据量身定制的本地策略。此方法有助于减少锁存争用并提高局部性。
将所需页面映射到缓冲池的两种方法是对象 ID 和散列。
对象 ID 涉及扩展记录 ID 以具有对象标识符。然后通过对象标识符，可以维护从对象到特定缓冲池的映射。
另一种方法是散列，其中 DBMS 对页面 id 进行散列以选择要访问的缓冲池。
预获取
DBMS 还可以通过基于查询计划预取页面来进行优化。然后，在处理第一组页面时，可以将第二组页面预取到缓冲池中。DBMS 在顺序访问多个页面时通常使用此方法。缓冲池管理器还可以预取树索引数据结构中的叶页。
扫描共享（同步扫描）
查询游标可以重用从存储或运算符计算中检索的数据。这允许多个查询附加到扫描表的单个游标。如果一个查询开始扫描并且已经有一个查询在执行此操作，则 DBMS 会将第二个查询的游标附加到现有游标。DBMS 跟踪第二个查询与第一个查询的连接位置，以便在到达数据结构末尾时完成扫描。
旁路缓冲池
顺序扫描操作符不会将获取的页面存储在缓冲池中以避免开销。相反，内存对于正在运行的查询来说是本地的。如果操作员需要读取磁盘上连续的大量页面，则此方法非常有效。缓冲池旁路还可以用于临时数据（排序、连接）。
5 缓存替换策略
当DBMS需要释放帧以为新页面腾出空间时，它必须决定从缓冲池里移除哪个页面。
替换策略是 DBMS 实现的一种算法，用于在需要空间时决定从缓冲池中逐出哪些页。
替换策略的实施目标是提高正确性、准确性、速度和元数据开销。
最近最少使用（LRU）
最近最少使用的替换策略维护每个页面上次访问时间的时间戳。 DBMS 选择逐出具有最早时间戳的页面。该时间戳可以存储在单独的数据结构中，例如队列，以允许排序并通过减少驱逐时的排序时间来提高效率。
CLOCK
CLOCK 策略是 LRU 的近似，不需要每页单独的时间戳。在CLOCK策略中，每个页面都被赋予一个参考位。当访问页面时，设置为1。
为了形象化这一点，请使用“时钟指针”将页面组织在循环缓冲区中。扫描时检查页面的位是否设置为 1。如果是，则设置为零，如果否，则将其逐出。通过这种方式，时钟指针可以记住驱逐之间的位置。
备选方案
LRU 和 CLOCK 替换策略存在许多问题。
也就是说，LRU 和 CLOCK 容易受到顺序泛洪的影响，其中缓冲池的内容由于顺序扫描而被损坏。由于顺序扫描会快速读取许多页面，因此缓冲池会被填满，并且来自其他查询的页面会被逐出，因为它们将具有较早的时间戳。在这种情况下，最新的时间戳并不能准确反映我们实际想要驱逐的页面。
针对LRU和CLOCK策略的缺点，存在三种解决方案。
一种解决方案是 LRU-K，它将最后 K 个引用的历史记录作为时间戳进行跟踪，并计算后续访问之间的间隔。该历史记录用于预测下次访问页面的时间。
另一个优化是每个查询的本地化。 DBMS 根据每个事务/查询选择要驱逐的页面。这可以最大限度地减少每个查询对缓冲池的污染。
最后，优先级提示允许事务在查询执行期间根据每个页面的上下文告诉缓冲池页面是否重要。
脏页
有两种方法可以处理含有脏位的页面。最快的选择是删除缓冲池中任何未脏的页面。较慢的方法是将脏页写回磁盘以确保其更改被持久化。
这两种方法说明了快速驱逐与将来不会再次读取的脏写页面之间的权衡。
避免不必要地写出页面问题的一种方法是后台写入。通过后台写入，DBMS 可以定期遍历页表并将脏页写入磁盘。当脏页被安全写入时，DBMS 可以逐出该页或只是取消设置脏标志。
6 其他内存池
DBMS 需要内存来存储元组和索引以外的内容。这些其他内存池可能并不总是由磁盘支持，具体取决于实现。
- 排序+连接缓冲区
- 查询缓存
- 维护缓冲器
- 日志缓冲区
- 字典缓存
7 操作系统页面缓存
大多数磁盘操作都是通过操作系统 API 进行的。除非另有明确说明，否则操作系统维护自己的文件系统缓存。
大多数 DBMS 使用直接 I/O 来绕过操作系统的缓存，以避免页面的冗余副本以及必须管理不同的逐出策略。
Postgres 是使用操作系统页面缓存的数据库系统的示例。
8 磁盘IO调度
DBMS 维护内部队列来跟踪来自整个系统的页面读/写请求。任务的优先级是根据以下几个因素确定的：
- 顺序IO和随机IO
- 关键路径任务与后台任务
- 表、索引、日志、临时数据
- 事务信息
- 基于用户的SLA