【CMU 15-445】05 缓冲池

Slides
Notes

Tips

这部分与操作系统和计组内容有共通之处，结合会更好理解。

1. 两种锁定义 - Locks vs. Latches

在讨论DBMS如何保护其内部元素时，我们需要区分锁 Locks 和latches。

Locks

• 保护数据库逻辑内容(例如，元组、表、数据库)不受其他事务的影响。
• 在事务持续时间内执行。
• 需要能够回滚更改。
  （笔者把它理解为逻辑的、抽象的、high-level的概念）

Latches

• 保护DBMS的内部数据结构的临界区不受其他线程的影响。
• 在操作持续时间内执行。
• 无需能够回滚更改。
  （笔者把他理解为具体的、low-level的概念，真正对资源进行加锁。类似 Mutex ）

2. 缓冲池 Buffer Pool

缓冲池 是(从磁盘读取的) pages 的内存缓存。DBMS总是想知道得更清楚，所以我们希望自己管理内存和分页，而不是交给操作系统OS。

它是组织为固定大小 pages 数组的内存区域。里面的每个数组条目称为一个 frame。当DBMS请求页时，会将一个完全相同的副本放入其中一个框架中。（frame，对于磁盘的 page来说：slot array；对于缓冲池来说：page）

由缓冲池维护的元数据：

• 页表 Page Table：内存中的hash表，跟踪当前内存中的页面。它将 page ids 映射到缓冲池中的 frame 位置。
• 脏标志 Dirty-flag：线程在修改 page 时设置此标志。这向存储管理器指示必须将该页写回磁盘。
• 引用计数 Pin Counter：跟踪当前正在访问该页面(读取或修改该页面)的线程数量。线程在访问页面之前必须递增计数器。如果页面的计数大于0，则不允许存储管理器将该页面从内存中踢出，否则页面可以被踢出内存。

优化方法：

• 多缓冲池 Multiple Buffer Pools：DBMS还可以有多个用于不同目的的缓冲池。这有助于减少 latch 争用并改进局部性；
• 预取 Pre-Fetching：DBMS还可以通过基于查询计划预取页面来进行优化。在按顺序访问页面时通常这样做；
• 扫描共享 Scan Sharing：查询游标可以连接到其他游标并一起扫描页面。

分配策略：

• 全局策略：DBM应如何为所有活动 txns 做出决策。
• 局部策略：将 frame 分配给特定的txns，而不考虑并发 txns 的行为。

3. 替换策略 Replacement Policies

替换策略是DBMS实现的一种算法，它决定在缓冲池需要空间时从缓冲池中换出哪些pages。

实现目标：

• 正确性 Correctness
• 准确度 Accuracy
• 速度
• 元数据开销

LRU 最近最少使用算法

学过 OS 的一定非常熟悉，没错就是那一套OS页面置换算法。只需要注意下面两点：

维护上次访问每个页面的时间戳。
DBMS选择踢出具有最旧时间戳的页面。

CLOCK 时钟算法

也是 OS 的算法，对LRU算法进行改进，属于LRU的近似算法，每页不需要单独的时间戳。

• 每个页面都有一个引用位 reference bit
• 当页面被访问时，设置为1

用“时钟指针”在环形缓冲区中组织页面：

• 扫描时检查 pages bit 是否设置为1
• 如果是，则设置为0，如果否，则踢出内存
• 时钟指针踢出之间的位置

额外一提：

LRU 和 clock 更换策略存在问题：

• LRU 和 clock 容易受到顺序泛洪 sequential flooding 的影响，在这种情况下，缓冲池的内容会因顺序扫描而被丢弃。
• LRU 页面 实际上可能很重要，因为它不跟踪 页面使用情况的元数据。

更好的解决方法：

• LRU-K：考虑最近K次引用的历史。（LRU是考虑最近的一次）
• 优先级提示 Priority hints：允许txns告诉缓冲池页面是否重要
• Localization：根据每个txn/查询 选择要逐出的页面。