缓冲池
Project #1 Buffer Pool Manager¶
Buffer Pool Manager 的常见中文翻译有 “缓冲池”、“内存池” 等。
磁盘数据库需要处理庞大的数据（通常是内存的很多倍），因此任意时刻只能有一部分数据在内存中。而 Buffer Pool Manager 就是负责管理这些内存的。
值得一提的是，Andy 在课上花了很多的时间介绍了操作系统的 mmap（虚拟内存） 技术，并且强调绝对不要在数据库设计中使用 mmap。在我看来有以下几点理由：
- 事务安全：操作系统会在任意时刻将虚拟内存的页面出页，一旦出页就会把脏页刷回磁盘，但是 DBMS 的事务执行失败时会涉及到回滚，那么本该回滚的数据被刷回了磁盘就非常棘手。
- 性能问题：DBMS 自己管理内存可以对数据页进行更加精细的管控，举个例子，针对 DBMS 的应用场景，可以使用更优秀的页面置换算法，为不同的页面、不同的操作类型规定停留在缓冲池的时间长短。而如果使用 mmap ，一方面其他程序的也会挤占 DBMS 可用的内存大小，另一方面，mmap 的页面置换算法通常实现为 LRU，并不适合 DBMS 的场景，从而导致性能问题（后面会介绍一个 LRU 的例子）。
-
IO 开销。mmap 什么时候把内存写回磁盘？mmap 很可能在一次写页面的请求中将这个页面多次出页刷回磁盘，造成额外的IO开销。另外，mmap 到底开多少个线程来 IO 数据？如果 DBMS 使用了 mmap 作为缓冲池，就面临着和其他进程抢 mmap IO 线程 的问题。
-
错误处理，mmap 是有可能失败的，如果 DBMS 使用了 mmap 作为缓冲池，就不得不处理
SIGBUS信号。
Andy 在课上还说了一句印象深刻的话：
如果我死了，并且我的墓碑上只能写一句话，我会写“永远不要在 DBMS 中使用 mmap”。
虽然一部分冷门的 DMBS 使用了 mmap，但绝大多数 DBMS 自己管理缓冲池。
我们定义页面为数据在内存和磁盘之间 IO 的基本单位，一个文件由若干个页面组成。在 Postgres 中默认页面大小为 8KB，MySQL 的默认页面大小为 16KB。
缓冲池实际就是一个数组，数组中每个位置可容纳一个页面。
接下来介绍缓冲池的三个重要部分：
页面置换¶
后端请求一个页面有三种情况：
- 页面在缓冲池中，此时直接返回缓冲池中对应的地址。
- 页面不在缓冲池中，但此时缓冲池拥有空闲的空间（空闲是指缓冲池数组中某个没有实际页面数据的位置），则在这个位置读入请求页面，然后返回对应的地址。
- 页面不在缓冲池中，此时缓冲池已满，那么我们需要置换一个页面，被置换出去的页面如果脏了就需要写回磁盘。然后，在这个位置上，我们读入页面数据，最后返回对应的地址。
本节讨论的是第三种情况所使用的页面置换算法，操作系统的页面置换算法有 LRU、FIFO、LFU 等，其中最常见的就是 LRU。
LRU 算法虽然通用，但在 DBMS 中存在一些问题，例如，一次全表扫描会将缓冲池的所有页面都替换出去，进而导致缓冲池中都是全表扫描的页面，原先的热点页面都没了，这是不可接受的。通常称这个问题为页面污染，也就是不正确的页面污染了缓冲池。
针对 LRU 的缺陷，大多数 DBMS 都对其进行改进。普通的 LRU 仅仅考虑上次命中页面的时间，而没有考虑页面命中了多少次，就会出现
Project 1 选用的页面置换算法为 LRU-K，LRU-K 额外记录了每个页面（在缓冲池期间）命中的次数。根据次数是否达到了 K 次，将页面分为两个表，其中大于等于 K 次的部分称为热点表，热点表按照 LRU 维护，不足 K 次的部分称为普通表，普通表按照 FIFO 进行维护。在置换页面时，优先从普通表中选择。
- 普通的 LRU 实际就是 LRU-1 的特化，由于此时 K 为 \(1\)，相当于只有热点表，而没有普通表。
- MySQL 中采用的是一种类似 LRU-2 的特化方案，除了考虑次数以外，MySQL 还会考虑页面在缓冲池中待了多长时间，只有超过一定阈值的页面才能从普通表升级到热点表。
- Postgres 采用的页面置换算法是 clock sweep 算法，该算法同样记录页面命中的次数，同时维护一个指针，这个指针就像钟表的指针一样不停的转动，来寻找第一个命中次数为 \(0\) 的页面，将其置换。如果一个页面次数不为 \(0\)，则其次数减少 \(1\)，然后指针向后移动继续寻找。
IO 调度¶
缓冲池需要只在必要时才进行 IO 的调度，具体来说，对于后端的页面请求，我们需要保证在后端释放页面之前页面处于“钉住”(Pinned)，被钉住的页面是无论如何都不能被置换的。
什么时候才必须执行 IO？
- 被置换的页面是脏页面。我们知道被置换的页面一定是没有被后端钉住的页面，但这个页面曾经可能被后端改写过，因而成为脏页面。所以在被置换出去前，必须将脏页面数据写回磁盘。
- 新读入页面时，需要从磁盘将页面读到缓冲池中。
显然，对于情况 1，我们会向 IO 调度发起一次写数据的请求，对于情况 2 则是发起一次读数据的请求。IO 调度就是负责接收 IO 请求，和文件进行读写交互的部分。
在 IO 调度的优化方面，为了吃满磁盘 IO 的性能，IO 调度需要支持并发的处理 IO 请求。在并发编程时，需要考虑读写数据的一致性，保证多线程 IO 调度和单线程 IO 调度拥有一致的结果。
此外，大多数 DBMS 会在磁盘 IO 负载较低时，在后台自动将缓冲池的脏页面写回，提高页面置换的速度。
缓冲池设计¶
回顾一下后端请求页面的三种情况：
- 页面在缓冲池中，此时直接返回缓冲池中对应的地址。
- 页面不在缓冲池中，但此时缓冲池拥有空闲的空间（空闲是指缓冲池数组中某个没有实际页面数据的位置），则在这个位置读入请求页面，然后返回对应的地址。
- 页面不在缓冲池中，此时缓冲池已满，那么我们需要置换一个页面，被置换出去的页面如果脏了就需要写回磁盘。然后，在这个位置上，我们读入页面数据，最后返回对应的地址。
我们需要知道某个页面是否在缓冲池中，显然，缓冲池还需要维护一个哈希表，建立页面编号到已有缓冲池的映射。对于后端的页面请求，查找哈希表就能得到页面是否在缓冲池中。
除了哈希表之外，缓冲池还拥有一个巨大的页面数组，在初始化时所有的位置都是空闲位置，再加上刚刚提到的页面置换以及 IO 调度的组件，缓冲池就设计完成了。
缓冲池最终需要保证交付给后端可用的页面（内存空间），允许后端对页面进行读写。
实现过程记录¶
大概花了两个星期实现了缓冲池以及优化，最终在课程的 bench-mark 中取得了排名第 1 的成绩，系统基本的功能是非常简单的，只要能梳理出缓冲池的实现即可实现最简单的单线程版本。
我大概用了 \(2\) 天的时间完成缓冲池的基础版本，随后的时间都花在了优化、重构、调试上。
在我对缓冲池的实现以及优化过程中，有比较重要的几个节点：
- 第一个单线程可用的基础版本，花了 \(2\) 天实现，在排行榜中排大概200多位。
- 对单线程版本进行重构，思考每个组件是否有更优的实现（从数据结构、C++ 开销、更简洁的逻辑等角度），这个版本耗费 \(2\) 天，最终在保持单线程不变的情况下，性能排名达到 \(70\) 位左右（是的，即使只用单线程，仍然能达到这个排名）
- 在确保单线程程序优化的差不多的时，我开始将缓冲池改为多线程，这个版本耗费了大概 \(10\) 天左右，不断的重构、优化、调试确实非常麻烦，经过几次迭代，排名持续上涨，最后终于冲上了排行榜的第 \(1\)。
附上排名（截图于2024.05.30）
优化建议¶
基于本课程的 Collaboration Policy，我不会在本文公布源码以及我具体做了哪些优化，仅仅给出想要对缓冲池优化的建议，以及前期的准备。
-
首先，请考虑官方给出的优化建议，在此，我附上简短的翻译：
- 考虑读取页面的类型，即：默认、扫描、概率分布、索引四种类型的请求。
- 允许并发的进行 IO 调度，并保证数据的一致性。
- 允许并发在缓冲池中的读取页面。
- 不要使用投机取巧的办法。例如，试图突破缓冲池大小的限制，将所有数据都读到缓冲池中。（这一条更像是一种禁止规则）
- 在必要时使用无锁队列以及自己的
std::promise实现。
-
如果你不会
C++并发编程，请参阅 《C++并发编程实战（第2版）》，这本书内容量很大。请带着自己的思考去读（同时进行必要的实验），更重要的是带着“优化性能”的目的去读。 - 针对并发性能的提升，无非就是逐步减小锁的粒度，换取更高的并发量。因此，请务必问自己一些问题：
- 哪些地方必须加锁？证明？
- 哪些地方没必要加锁？
- 哪些地方不加锁会发生冲突？
- 冲突能否解决？如果能解决，代价是什么？
- \(\cdots\cdots\)
为什么会想优化到排名第 \(1\) ？并非刻意的攀比，只是想将所学的并发编程应用于实际的场景。在完成第一个单线程版本之后，我知道还可以用多线程进一步优化，所以我列了一些 TODO，每一个 TODO 对应一个优化方式，我做的也仅仅是（按照性能提升的优先级）完成了这些 TODO 而已。
在优化的过程中免不了碰到高并发环境下的问题，而并发调试是非常痛苦的（尤其是在这个缓冲池的 bench 中，当吞吐量高到一定程度之后，甚至连打日志都会影响 bug 的复现），中间一度想过放弃，最终还是坚持下来了，同时积累了一些并发编程调试的经验。事实上，这种逐步提高性能带给我的反馈是很足的，这也是我能坚持下去的原因。
创建日期: 2024-06-01