最近这段时间在看 Buffer Manager 相关的一些资料，从基本的原理出发再到最近一两年这个方向上的实践与科研，还是有不少想法产生的。于是准备写一些博客稍作整理，还望路过的高手不吝赐教。这篇博客主要介绍缓存管理器的基本原理。

disclaim：本文着重参考了 CMU 15445 Lecture 5。

早期关系型数据库底层存储通常使用 B 树类数据结构，这类数据结构通过提高节点扇出，可以把树高降低，从而减少查找时磁盘访问的次数。因为磁盘访问速度和内存相比实在太过于感人，因此可以利用访问磁盘的时空局部性把一些节点缓存在内存中，进一步减少磁盘访问。

如果有删改，则内部节点可能会 split/merge、叶子节点上的数据会被修改，那么就需要及时地把内存中的数据写回到磁盘进行持久化，虽然通常的会先写 WAL 作为灾难恢复的手段，但无论如何缓存更新总是要写回的。

同时，内存容量有限，在加载新的节点前，如果内存容量紧张，或许还需要把一些暂时不用的节点缓存给释放掉。

一个可行的方案是仰赖操作系统本身的 Page Cache，然而，正如 CMU 的 Andy Pavlo 老师指出的那样，数据库系统本身总是比操作系统更了解自己使用各种资源的模式的，利用好这份知识可以为更多的优化打开大门。这也是为什么 Andy 十分反对使用 mmap 来代替缓存管理器的原因。

为了服务上述目的，基于 B 树类数据结构的传统关系型数据库通常都会引入一个缓存管理器。

缓存管理器的原理并不复杂。

B 树节点的大小通常以虚拟内存的页的大小为单位（典型大小是 4KB），缓存管理器也会尊重这一设定。

作为文件的缓存，在缓存管理器眼中，保存数据的文件不过是固定长度的页（page）在磁盘中一字排开。每一页按顺序分配一个逻辑上的 page id，这样就可以通过 page id 与页大小算出偏移量来访问这一页的数据。

缓存管理器内部会分配一定数量的框（frame）用来存放从磁盘缓存的页——显然框的大小和页的大小是相等的，不然放不下嘛。框在内存中也是一字排开的，同样也会按顺序编上 frame id 的编号，目的和 page id 相同，都是为了通过 id 获取偏移量。而框内的数据就是数据库内部存储层之上的各个部件访问磁盘的代理。

既然是代理，上层的逻辑只会知道通过 page id 索取页，毕竟 page 来来往往，在缓存管理器中只是过客罢了。因此缓存管理器会维护一个从 page id 到 frame id 的映射，通常是一个 hash map。当有页需要加载到缓存管理器时，从尚未使用的框中找一个作为容器，然后把页的数据加载到框内，同时更新映射表。这样当上层逻辑想访问这一页的数据时，缓存管理器就可以知道对应的框，从而节约了一次磁盘访问。

框的数量受限于内存空间，故而需要某种释放的机制来给新的页访问提供框。

根据是否有数据修改，框可以分为干净与脏脏两种状态。干净的框内数据和磁盘中页的数据一致，因此可以直接释放回收这个框；而对于脏脏的框，则需要把改动写回到磁盘中生效。每个框会附加一个元信息，表示是否有写入导致的脏脏，这样就可以在释放时知道是否要写回。

此外，有一些页在内存中地址可能正在被引用，这些页是不能被写回的。这种避免写回的设定被称为 pin，上层逻辑根据需求可以要求 pin 住一页数据，这时缓存管理器就不能擅自释放这一页。在实现上，框通常还会再附加一个 pin 计数器作为元信息，只释放计数器为 0 的页。

具体释放哪一页，这个决策就属于仁者见仁了。尊崇时间局部性原理，采用 LRU 机制，优先释放长时间不用到的页。LRU 具体的实现方式有很多，可以放弃一些严谨的顺序换取更高的效率，CLOCK 机制就是一例。但后面我们会提到，LRU 并不总是好的。

就是这样。

一些细节

原理是简单的，然而在缓存管理器的实现和使用上，有一些细节还是挺重要的。

取决于编码方式，数据库需要首先知道它想要的数据在哪一页上。数据库文件的前几页就是索引这个数据的元信息，包括表中各列数据的类型，总共的行的数量等等，不过最重要的还是 B 树的根节点，从根节点往下，到每个子节点的引用都是其 page id，这样在游览 B 树时，就可以透过引用知道下一个应该被加载的页。

具体到一页内，各行数据按顺序逐一排布。若各行长度相等，就可以简单地从行号算出在页内的偏移量；若存在变长的列，则通常会把这一列单独拎出来，在页内从后往前堆积，而原来的位置上就可以简单存一个偏移量。这样直到从前往后写的行与这个从后往前的堆积撞车，就表示此页已满，要继续添加请再新建一页。对于一页放不下的特别宽的列，就只能额外申请页来存放，原来的位置存放到外部页的引用即可。

数据库中一页数据可能被多个请求并发访问，这当然是要做并发控制的。数据库领域在物理实现上的锁通常被称为 latch，区别于逻辑上用来确保 ACID 中的 I 的 lock。页上的计数器可以用 CPU 提供的原子操作实现，而读取和写入则需要通过读写锁这类机制，为写提供排他性的访问。缓存管理器本身也需要做并发控制，加载新页时对框的分配这里，加锁或者采用无锁队列等手段，通常是必不可少的。

页数据读取与写回时，由于缓存管理器已经站好了缓存的岗，因此操作系统的缓存机制就可以解散了，打开文件的系统调用上可以添加 O_DIRECT 的标志绕过。

改动发生需要写回页前，最好先写 WAL，确保即使写入丢失也可以从 WAL 中恢复。这套机制在一篇文章中断然讲不清楚，就当是一个提醒吧。

使用时的优化

前文提到，数据库本身比操作系统更了解自己对磁盘的访问模式，因此一些优化手段可以更好地利用这份知识。

预取

根据执行计划，数据库可以提前知道哪些页需要被访问，那么在使用前就可以预取到缓存管理器。

扫描共享

如果有两个查询在时空上有重合，那么可以让后来的查询先跟着前一个查询读取，等前一个查询读完，再回过头来补上前面漏下未读到的数据。

绕过

大规模的扫表的一个现象是，刚刚读入的页往往会马上变得无用，如果扫表过程中的页加载到缓存管理器中，会用大量无用的页驱逐掉原来的所有缓存。因此，对于特定的读取模式，上层逻辑可以选择绕过缓存管理器。

以上就是对缓存管理器原理的介绍，下一篇文章我会对 DuckDB 的缓存管理器的实现做分析。