CMU::15-445/645::Buffer Pools 笔记

缓冲池和内存管理

img

介绍

DBMS 负责管理其内存并从磁盘上来回移动数据。由于在大多数情况下，数据不能直接在磁盘上操作，任何数据库都必须能够有效地将其磁盘上以文件形式表示的数据移动到内存中，以便能够使用。DBMS 面临的一个障碍是尽量减少移动数据的速度问题。理想情况下，数据应该"看起来"是已经在内存中了。

img

从空间控制和时间控制的角度来思考这个问题。

空间控制是指页面在磁盘上的物理写入位置，目标是使经常一起使用的页面在磁盘上尽可能地保持物理上的接近。

时间控制是指何时将页面读入内存，何时将其写入磁盘，目的是尽量减少从磁盘上读取数据的停顿次数。

Locks vs. Latches

Locks: Locks 是一个更高层次的逻辑元语，它保护数据库的内容（如 Tuple 、表、数据库）不受其他事务的影响。事务将在整个持续时间内持有一个 Locks。数据库系统可以在运行查询时向用户披露哪些 Locks 正在被持有。Locks 需要能够回滚。概念上接近于操作系统中的 Latches。

Latches: Latches 是一种底层的保护元语，DBMS 将其用于内部数据结构的关键部分（例如，哈希表，内存区域）。Latches 只在所进行的操作的时间内保持。Latches 不需要支持回滚。概念上接近与操作系统的 Mutex。

缓冲池

缓冲池是一个从磁盘上读取页面的内存缓存。它本质上是在数据库内部分配的一个大的内存区域，用来存储从磁盘获取的页面。

缓冲池的内存区域被组织成一个固定大小的页面阵列。每个数组条目被称为一个帧。当 DBMS 请求一个页面时，一个精确的副本被放置到缓冲池的一个帧中。然后，当一个页面被请求时，数据库系统可以首先搜索缓冲池。如果没有找到该页，那么系统就会从磁盘上获取该页的副本。

img

缓冲池元数据

缓冲池必须维护某些元数据，以便有效和正确地使用。首先，页表是一个内存中的哈希表，用于跟踪当前内存中的页面。它将页面 ID 映射到缓冲池中的帧位置。由于缓冲池中的页面顺序不一定反映磁盘上的顺序，这个额外的中介层允许识别缓冲池中的页面位置。请注意，页面表不能与页面目录混淆，后者是从页面 ID 到数据库文件中的页面位置的映射。

页面表还维护着每个页面的额外元数据，一个脏页标志和一个固定/引用计数器。

每当一个线程修改一个页面时，就会设置脏页标记。这表明存储管理程序必须将该页写回磁盘。

固定/引用计数器跟踪当前访问该页的线程数量（无论是读取还是修改）。一个线程在访问该页之前必须递增该计数器。如果一个页面的计数大于零，那么存储管理器就不允许将该页面从内存中替换出去。

内存分配策略

数据库中的内存是根据两个策略分配给缓冲池的。

全局策略处理 DBMS 应该做出的决定，以有利于正在执行的整个工作负载。 它考虑所有活动的事务，以找到分配内存的最佳决策。

另一个选择是局部策略，它做出的决定将使单个查询或事务运行得更快，即使它对整个工作负载不利。对整个工作负载有利。局部策略将帧分配给特定的事务，而不考虑并发事务的行为。并发事务的行为。但是需要考虑共享页面。

大多数系统使用全局策略和局部策略的组合。

缓冲池优化

多个缓冲池

DBMS 可以为不同的目的维护多个缓冲池（即每个数据库缓冲池、每个页面类型的缓冲池）。然后，每个缓冲池可以采用为其内部存储的数据定制的本地策略。这种方法可以帮助减少锁的竞争，并提高定位性。

将所需页面映射到缓冲池的两种方法是对象 ID 和散列。

对象 ID 涉及到扩展记录 ID，以包括关于每个缓冲池管理的数据库对象的元数据。然后通过对象标识符，可以维护对象到特定缓冲池的映射。

另一种方法是散列，DBMS 对页面 ID 进行散列，以选择访问哪个缓冲池。

预取

DBMS 也可以通过基于查询计划的预取页面来进行优化。然后，当第一组页面被处理时，第二组可以被预取到缓冲池中。这种方法是 DBMS 在连续访问许多页面时常用的。

扫描共享

查询游标可以重复使用从存储或操作计算中获取的数据。这允许多个查询附加到一个扫描表的游标上。如果一个查询开始扫描，如果已经有一个在做这个，那么 DBMS 会跟踪第二个查询与第一个查询的连接位置，这样它就可以在到达数据结构的末端时完成扫描。第二个查询还可以复用第一个查询的结果或者中间结果。

缓冲池旁路

顺序扫描操作不将获取的页面存储在缓冲池中来避免开销。如果操作需要读取磁盘上连续的大序列页面，这就很好用，在后面不需要用到这些原始数据，可以在内存中计算完成后就可以丢掉。缓冲池旁路也可用于临时数据（排序、连接）。

操作系统页面缓存

大多数磁盘操作是通过操作系统的 API 进行的。除非被明确告知，操作系统会维护自己的文件系统缓存。

大多数 DBMS 使用 direct I/O 来绕过操作系统的缓存，以避免页面的冗余拷贝和不得不管理不同的驱逐策略。

缓冲替换策略

当 DBMS 需要释放一个帧来为一个新的页面腾出空间时，它必须决定从缓冲池中驱逐哪个页面。

替换策略是 DBMS 实现的一种当它需要空间时决定从缓冲池中驱逐哪些页面的算法。

替换策略的实现目标是提高正确性、准确性、速度和元数据的开销。

最近使用最少（LRU）

最近最少使用的替换策略保留了每个页面最后被访问的时间戳。这个时间戳可以存储在一个单独的数据结构中，比如一个队列，以便进行排序和提高效率。该 DBMS 会选择驱逐具有最古老时间戳的页面。此外，页面被保存在排序的顺序中，以减少排序驱逐的时间。

时钟算法

CLOCK 策略是 LRU 的一个近似值，不需要每页有单独的时间戳。在 CLOCK 策略中，每个页面被赋予一个引用位。当一个页面被访问时，设置为 1。

为了直观地了解这一点，可以将页面组织在一个带有"时钟指针"的圆形缓冲区中。当扫到一个页面，参考位如果是 1，则设置为 0，如果不是，则驱逐它。通过这种方式，时钟指针通过驱逐操作记住了位置。

然而，LRU 和 CLOCK 很容易受到顺序泛滥的影响，即缓冲池的内容由于顺序扫描而被破坏。由于顺序扫描会读取每一页，所以读取的页面的时间戳可能并不反映我们真正想要的页面。换句话说，最近使用的页面实际上可能是最不需要的页面。

有三种解决方案可以解决 LRU 和 CLOCK 策略的缺点。

一种解决方案是 LRU-K，它以时间戳的形式跟踪最后 K 个引用的历史，并计算出后续访问的间隔时间。这个历史记录被用来预测一个页面下次被访问的时间。

另一个优化是局部化每个查询。通过持续跟踪被查询读取过的页面，DBMS 在每个事务/查询的基础上选择哪些页面要被驱逐。这使得每次查询对缓冲池的污染最小化。

最后，优先级提示允许事务在查询执行过程中根据每个页面的上下文告诉缓冲池页面是否重要。

脏页

有两种方法来处理有脏位的页面。最快的方法是丢弃缓冲池中任何不脏的页面。一个较慢的方法是将脏页写回磁盘，以确保其变化被持久化。

这两种方法说明了快速驱逐与脏写页之间的权衡，脏写页在未来不会被再次读取。

避免不必要地写页面的问题的一种方法是后台写入。通过后台写入，DBMS 可以周期性地走过页表并将脏页写入磁盘。当一个脏页被安全地写入时，DBMS 可以驱逐该页或者直接取消脏页标志。

其他内存池

DBMS 需要内存来处理 Tuple 和索引以外的事情。这些其他的内存池可能并不总是由磁盘支持，这取决于实现。

  • Sorting + Join Buffers
  • Query Caches
  • Maintenance Buffers
  • Log Buffers
  • Dictionary Caches