buffer pool Manager：如何管理内存并比OS做的更好？

HTAP：既做OLTP，⼜做OLAP的数据库系统。你们会有前端OLTP数据库，以及后端⼤型数据仓库。这些有时候被称为Data silo(数据孤岛，即相互独⽴的数据存储区)，因为你们可以对其中⼀个数据库实例进⾏⼀系列更新操作，不管它是不是单个节点都没关系，因为它是⼀个单个逻辑数据库。然后你就可以进⾏某种被称为ETL的操作（ETL是将业务系统的数据经过抽取、清洗转换之 后加载到数据仓库的过程），将处理后的数据 传⼊后端数据仓库

今天我们想去讲的内容就是，我们该如何将磁盘中的数据库⽂件或page放到内存中，以便我们 以对它们进⾏操作。

我们没办法在不将它们先放⼊内存的情况下对这些数据进⾏读写，这是冯诺依曼架构。现在也推出了⼀些新的硬件，我们可以将这些处理逻辑推送到磁盘上，但现在，我们可以将它抛之脑后

今天我们要讨论的东⻄就是如何去构建⼀个Buffer池管理器。然后，我们会去讨论，当我们需要释放内存空间时，我们该如何使⽤不同的策略来决定我们想让 哪些pages写出到磁盘上。然后会讨论我们可以通过哪些额外的优化来最⼩化这种影响。然后，我们会结束讨论数据库系统中其他两个需要⽤到内存的部分，Ok

概述

So，现在我们想试着弄清楚如何将这些page放回磁盘中，从而：

• ⽀持大小超出内存容量的数据库
• 最⼩化磁盘速度缓慢的影响

基本策略是缓存，做一个 由 DBMS 管理，而非OS，我们想绕过OS的FS缓存。这被称为我们的 buffer pool

buffer pool 组成

1. frame：缓冲池被划分为一个个固定大小的块
2. 间接层映射：PT，缓冲池中的页顺序和磁盘中的并不一致
   • 一个哈希表，每一项都需要一个 latch 锁保护
3. 元数据：跟踪缓冲池的状态，例如：
   • Dirty Flag
   • Pin count：使用该页的线程数量/查询该页的数量
   • Access Tracking Information（日志）：写完日志后，再修改磁盘页

向 buffer pool 请求 page

DBMS发出page请求时，先看看buffer pool中有没有，没有就从磁盘中拷贝一份到pool中，然后返回指针

• 在使用某个PTE时，需要获取锁

lock 和 latch 的区别

• lock：保护逻辑内容，比如说：tuple，表以及数据库。事务会在运⾏的时候去持有这个lock
• latch：保护数据库系统的底层内容，比如说我们映射表每一项的锁

在操作系统中，此处的Latch就像是它⾥⾯的 Mutex。实际上，我们会在我们的数据库系统中使⽤mutex来保护其中的关键内容

page directory & page table 的区别

• 页目录：找磁盘上的page，必须持久化
  • 崩溃恢复、支持庞大的数据库系统
• 页表：内部映射，映射页号和物理地址。临时的，无需持久化

构建 buffer pool：分配内存

基本策略分为全局策略和局部策略，全局策略可能对于某个查询来讲很糟糕，局部策略可能会拖慢整个系统的效率。大多数系统尝试着结合二者

DBMS 知道接下来要接触什么，这是它比OS做的更好的根本原因

优化1：多 buffer pool

每个池子都有自己的映射表，不同的池子中使用不同的局部策略

• 为每个池子中的查询带来更好的性能：不同的缓存策略、page 大小
• 减少锁竞争：更细粒度的锁

定位 page

1. 在需要定位page时，可以添加额外的元数据：Object Id，然后把这个id映射到特定的buffer pool

   

2. hash slot number/record id

   

优化2：Pre-fetching

我们想去最⼩化系统中的停顿：

• 线程切换：没有page时不得不使得线程停顿、读取磁盘并切换到其他线程，有数据时再切换回来
• 最大化磁盘顺序I/O，减小多次随机I/O带来的影响

控制预取的时机

有时候会预取到错误的page，而这在一些情形下是完全可以避免的——我们知道这些页的结构

只需要一些额外的元数据即可（但做起来也不是非常容易）

优化3：扫描/查询共享

也被称为同步扫描 synchronized scans，可以复用某个查询从磁盘上读取到的数据。

• 这是 buffer manager 的工作，非常底层的存储层
• 这些查询可以不同，而结果共享的查询必须相同，二者是不同的

实现方式：将多个查询附加到一个查询结果的游标上。第二个查询只需要知道自己是否和第一个查询有共同的数据，然后将游标附加到上面即可。同时需要跟踪第二个查询的游标，在扫描第一个查询的结果后，仍需查看还有那些数据是自己尚未扫描过的。

• 要正确⽀持它是件⾮常难的事，它让查询做的事情变得很复杂

由于关系模型是无序的，可以从任意地方开始执行，所以可以将下一个查询的游标附加到第一个查询的游标上，然后再回过头来查看还有什么数据是自己还没有读取的。

优化4：Buffer Pool bypass/light scan

查询 buffer pool 的页表是有代价的，我们需要获取锁。我们想绕过这个代价，同时想避免污染缓存。

具体的实现方式是，为这个查询线程分配一小块内存，如果查询的页不再内存中则读取到本地内存，然后在查询结束后丢弃掉这些本地内存。

• 对于大块连续存储在磁盘的数据效果很好；可被用于计算临时数据
• 在informix中，这被称为light scan

替换策略

所有的磁盘操作都是通过最底层的OS API来做的，而FS会维护一个文件缓存，我们不想二次缓存，也不信任OS的管理能力，于是我们使用的都是这些API的 direct I/O 模式

PostgreSQL是主流数据库系统中唯⼀⼀个依赖OS page cache 的

替换时我们关心：

• 正确性：如果说某个数据我们并没有真正地使⽤完，那么我们不想将它写出或移除
• 准确度：为我们要去确保我们所移除的page是在未来不太会被⽤到的那些page
• 磁盘寻道的数量减⾄最少

我们的策略需要尽可能地：

• 更少的元数据：跟踪页的使用，以决定替换哪个页
• 更快的策略：我们不想花费大量时间在策略执行上

⾼端数据库拥有⾮常复杂的替换策略

LRU

一种简单的替换策略：LRU。

• 实现1：跟踪⼀个page最后⼀次被访问时的时间戳
  • 需要扫描，效率低
• 实现2：维护一个队列，淘汰队头
  • 在被使用时查找到他再插入队尾，查找需要扫描，效率低

Clock

另一个策略叫：Clock，一种近似LRU的算法，它不会精确移除最久未被访问的page，而是近似

• 每个page有一个reference bit，它标记自从上一次访问这个page，它是否被访问过
• 有⼀个能够旋转的指针，它能够去检查这个标志位是被设置为1还是0
  • 若为0即未被访问过，移除
  • 否则继续递增指针
    • 如果所有的page都已经被修改了，那么我们就选择frame_id最⼩的那个page进⾏移除
    • 如果所有page的状态都是pinned（加了锁），那么你就没法释放任何page，那么你就得移除page id最⼩的那个page

问题：sequential flooding

也即我们的缓存会被污染，同时这些扫描的page都是最新的

三种解决策略：

1. LRU-K：记录每个缓存项最近被访问的K次时间戳，根据访问历史选择那些最近K次中访问频率最低或最近最久未被访问的项进行替换
   • 适应性强，更好的预测能力
2. 多个 buffer pool
3. priority hints（优先级提示）：确保某些高优先级的页被固定在内存中
   • 比如说 index page 中的非叶节点

dirty page

在page上有⼀个dirty bit

替换时可以先把脏页写回进行替换，并复⽤它的空间。但这需要两次磁盘I/O来读取一个页：

• ⼀次I/O是⽤来写出dirty page，另⼀个I/O则是读取我想要的那个page
  所以在替换脏页，与淘汰其他页之间的权衡非常难做

必须⽴即将page写出，在数据库系统中有⼀条执⾏定时写出任务的线程。另外，在写出 dirty pages 之前，请确保先将操作⽇志写出到磁盘

我必须做些额外的保护措施，以确保我以正确的顺序写⼊数据。这是mmap所⽆法做到的事