2. Buffer Pools

【学习笔记 3】数据库中的 buffer pool - 简书 (jianshu.com)

CMU 15445 学习笔记——Buffer Pool - 知乎 (zhihu.com)

• 这段内存完全是由数据库控制而不是操作系统
• 类似于数据库的内存

2.1. Lock 和 Latch

• lock 更高级，保护高级内容 from other transaction。

• 事务运行时持有 lock

• 要求能够回滚 changes

• 可以暴露给开发人员

• latch 是更底层的概念，来保护数据结构和内存

• 不需要能够回滚 changes

• 有点类似 mutex（互斥锁）

2.2. page table 和 page directory

• page directory
  • page id 到数据库文件中的 page location 的映射
  • 所有 changes 必须持久化
• page table
  • page id 到 buffer pool frames 中 page copy 的银蛇
  • 内存中的数据，不需要在磁盘中保存

2.3. buffer pool optimization

2.3.1. Multiple Buffer Pool

• 有多个 buffer pool
• 在每个 buffer pool 有局部策略
• 比如对每个表都有一个 buffer pool
• 可以一定程度缓解多线程争抢 latch 的场景

Approach Methods：

2.3.1.1. Object Id

2.3.1.2. Hashing

2.3.2. pre-fetching

• 为了最小化磁盘 IO 的影响

• pre-fetching 的方法

  • Sequential Scans
  • Index Scans

2.3.3. scan sharing

• 复用某次查询的数据，用于其他的查询
  • 不是 caching，caching 指的是完全相同的查询
  • 但是 scan sharing 只在乎是否取了同一个 page，而不是查询

2.3.4. buffer pool bypass

• 为了避免从 page table（hash 表）中查询的开销。
• 给每个查询线程分配一个本地内存作为该线程的缓存

2.4. replace policy

• lRU（Least Recently Used）
  • 单独维护一个 queue，根据 page 的修改顺序排列
  • 实现
    • 每个 page 带一个时间戳
    • clock：每个 page 带一个标志位（reference bit）
      • 代表我们上次 check 后，该 page 是否被访问
      • page 在一个环形队列（like a clock）
      • 不是严格的 LRU
      • 其实它的基本假设是：如果一个 page 在一段时间内不被使用，那么它大概率也不会再被使用，即可移除

• 问题：sequential flooding。

2.4.1. 解决 sequential flooding

LRU-K

• 记录每页的 K 次历史记录

• 不是看哪个 page 的时间戳最老，而是看时间戳之间的间隔

localization

• 从本地的角度移除最少使用的 page，而不是全局的角度

priority hints

dirty page

• 每个 page 有一个 dirty bit
  • 告诉我们自从上次 page 被放入后，是否被修改
• 要么每次 drop 掉不 dirty 的 page，但这些 page 可能会被用到
• 要么每次写出一个 dirty page 到磁盘（产生一次 IO），再将其替换之（又产生一次 IO）
• 数据库一般有一个定时任务线程，负责定时写出 dirty page，然后将其置为 clean

project 说明在 13：40(2 封私信) CMU 15-445 18 Buffer Pools 04 - 知乎 (zhihu.com)