Buffer Pool

Conception

Buffer vs. Disk file

  • 一般而言，frame 大小 = page 大小
  • buffer 由若干 frame 组成，file 由若干 page 组成

Lock vs. Latch

  • Lock 为概念上的锁，Latch 更具体，比如锁和锁眼

Page Table vs. Page Directory

  • Page Table 是 page id 到 buffer pool frames 的 map
  • Page Directory 是 page id 到 page locations 的 map

DBMS Buffer vs. OS Buffer

  • DBMS 经常能预测访问模式，可以使用更专门的缓冲区替换策略。且 DBMS 需要强制写回磁盘的能力。
  • OS 不能保证写顺序

Buffer Pool Optimizations

Multiple Buffer Pools

  • 每个数据库一个缓冲池
  • 每个页类型一个缓冲池，如存储索引的页，存储元素的页

Pre-Fetching

  • 全表扫描时提前读取

Scan Sharing

  • 两个请求共享结果

Buffer Pool Bypass

  • 数据不进内存池，连续读一大片且不需要再用的数据

Buffer Replacement Policies

OPT算法

  • 称为 Belady’s 算法，最佳的页面置换算法

  • 每次置换以后永远用不到的页面，如果没有则淘汰最久以后再用到的页面

  • 只存在理论意义，可以作为算法性能上界作为对比

LRU

  • 所有 frame 按照最近一次访问时间排列成一个链表，基于时间局部性，越是最近访问的在未来被访问的概率越高
  • 优点：在重复访问同一个页面上效果较好，选择frame的复杂度只有 O(1)
  • 缺点：缓存污染、维护 LRU 链表代价高、不满足时间局部性则性能差、没有考虑访问频率

LRU-K

  • 若某个 frame 的访问次数达到了K次以上，则尽量不置换
  • 维护两个 LRU 链表（1个是访问K次以上的，1个访问次数小于K），优先置换小于 K 次的链表。

2Q

  • 与 LRU-2 类似，区别在于访问1次的队列采用FIFO

Second-Chance FIFO

  • 给每个 frame 两次置换机会
  • 所有 frame 组成 FIFO 链表，每个 frame 附加一个 bit 位，初始为 0。当 FO 页第一次被选中置换时置为 1，并移到 FI 端。只有 bit 位为 1 的 FO 端的页才被选中置换

CLOCK

  • 避免每次访问都需要调整链表

  • 引入环形Second Chance FIFO，引入一个current指针指向当前指向的frame，给每个frame添加一个referenced位，初始为1

    1. current 指向 frame 的 pin-count>0，则 current++
    2. current 指向 frame 的 referenced 位若为 1，则置 0，current++
    3. current 指向 frame 的 referenced 位若为 0，且 pin-count 为 0，则替换该 frame，current++

  • 若访问命中时，不会改变current指针

Priority Hints

给优先级提示，比如某个根节点