Buffer Pools
1 Locks vs. Latches
在讨论 DBMS 如何保护其内部元素时，我们需要区分 lock 和 latches。
锁 lock
- 保护数据库逻辑内容（例如，元组、表、数据库）免受其他事务的影响。
- 在交易期间持有。
- 需要能够回滚更改。
锁存器 latches 类似操作系统的mutex
- 保护 DBMS 内部数据结构的关键部分免受其他线程的影响。
- 在操作期间保持。
- 不需要能够回滚更改。
2 缓冲池 Buffer Pool
BPM的总体架构
与虚拟内存的设计思想一致，BPM核心的便是将内存中的地址映射到磁盘中的地址（再次通过增加一个中间层解决了问题），向上提供所有数据都装入内存的幻象，数据单位为页。为了区分内存中的页和磁盘中的页，我们做一个定义：
- frame：buffer中的一页
- page：磁盘中的一页
BPM结构如下图所示：
其中包含两个数据结构：
- Buffer Pool：里面包含了一些frame，而这些frame中保存的就是对应page的内容
- Page Table：保存的是 page id -> frame id的映射。
实际运行的流程如下：
上层任务向BPM请求一个page
BPM查询对应的page是否在buffer pool中，即Page Table中包不包含page id
- 如果包含，那么返回对应的frame地址，并将frame 的pin count加1（代表这个frame的引用多了一次）
- 如果不包含，BPM需要将Page读如Buffer Pool中的frame中，再返回对应的frame地址（这其中可能包含置换）
结束
缓冲池是从磁盘读取的页面的内存缓存。 DBMS 总是知道得更好，所以我们想自己管理内存和页面。
它是组织为固定大小页面数组的内存区域。每个数组条目称为一个框架。当DBMS 请求一个页面，一个精确的副本被放置在这些框架之一。
缓冲池维护的元数据：
- 页表：内存中的哈希表，用于跟踪当前内存中的页面。它映射
页 id 到缓冲池中的帧位置。 - 脏标志：线程在修改页面时设置此标志。这向存储管理员表明
页必须写回磁盘。 - Pin 计数器（引用计数）：这会跟踪当前访问该页面的线程数（无论是阅读
或修改它）。线程必须在访问页面之前增加计数器。如果一个页面的计数
大于零，则不允许存储管理器从内存中驱逐该页面。
优化：
- 多个缓冲池：DBMS 也可以有多个缓冲池用于不同的目的。这个
有助于减少闩锁争用并改善局部性 - 预取：DBMS 还可以根据查询计划通过预取页面进行优化。通常
按顺序访问页面时完成。 - 扫描共享：查询光标可以附加到其他光标并一起扫描页面。
分配政策：
- 全局策略：DBMS 应如何为所有活动的 txns 做出决策。
- 本地策略：将帧分配给特定的 txn，而不考虑并发 txns 的行为。
3 更换政策
替换策略是 DBMS 实现的一种算法，它决定当需要空间时从缓冲池中驱逐将哪些页面。
实施目标：
- 正确性
- 准确性
- 速度
- 元数据开销
Least Recently Used 最近最少使用 (LRU)
- 维护每个页面上次访问时间的时间戳。
- DBMS 选择驱逐具有最早时间戳的页面。
CLOCK
LRU 的近似值，不需要每页单独的时间戳。
- 每个页面都有一个引用位
- 访问页面时，设置为 1
使用“时钟指针”在循环缓冲区中组织页面
- 扫描时检查页面位是否设置为 1
- 如果是，则设置为零，如果不是，则驱逐
- 时钟指针会记住驱逐之间的位置
备选方案
LRU 和时钟替换策略的问题：
- LRU 和 Clock 容易受到顺序泛滥的影响，其中缓冲池的内容被丢弃
由于顺序扫描。 - 由于不跟踪页面使用方式的元数据，LRU 页面可能实际上很重要。
更好的解决方案：
- LRU-K：考虑最近 K 个引用的历史记录，不看最老的时间戳，而是看这些时间戳的间隔，间隔最长的会被丢弃
- 优先级提示：允许 txns 告诉缓冲池页面是否重要
- 本地化：基于每个交易/查询选择要驱逐的页面
Transactions (事务）可以缩写为 TXNS