Buffer Pool的目标

负责数据在disk和memory之间的传输。此数据的传输其实在在有page directory的情况下，可以直接交由OS负责（通过filesystem的读写接口或者通过mmap等系统调用实现内存映射）

上述的方案是可行的，且有部分数据库系统确实采用上述的方式来进行数据的传输。但是此种方式性能会比较差，这是由于数据库系统和操作系统/文件系统是隔离的，OS与FS在缺少信息的情况下无法采用高级的算法来改进数据库系统的性能。

基于上述原因，商用的数据库系统都设计了自己的buffer pool来负责数据在内存和存储设备上的传输。Buffer Pool的总体设计目标是：

1. 优化空间局部性，使得磁盘是尽可能的顺序读/写
2. 时间控制：尽量减少硬盘读写等待，这需要控制page的读入时机和evict时机

当使用了buffer pool时，除PostgresQL，大部分数据库系统在使用文件系统接口时都会使用O_DIRECT标记来跳过文件系统的page cache。原因是：

1. 如果同时存在buffer pool+page cache，在内存中就存在冗余的page copy
2. 不同的OS采用不同的套题啊策略，在不同的OS上会有不同的性能表现

数据库系统利用query execution plan的语义完成：

1. 淘汰
2. 分配
3. 预取

Buffer Pool通用概念

图1: buffer pool结构

如图1所示，buffer pool是数据库系统向OS申请的一块内存空间，数据库系统将这个空间以frame为单位进行划分管理。frame对应文件中的page，其大小是相等的。数据库将通过系统调用，将数据从存储设备拷贝到frame中，其直接拷贝而不会进行例如解压缩等操作，也就是说，frame中的字节和存储设备上的字节是完全一样的。

数据库系统通过一个page table来映射page id（数据库通常会为每个page分配一个全局唯一的id）到buffer pool中的frame位置。当然，如果没有在page table中找到需要的page，说名page miss。page table中的每一个entry，通常包含的信息有：

1. page id与frame array的映射
2. dirty flag：表示此page是否在数据库系统中被修改
3. pin/reference counter：表示当前数据库系统中需要此page的thread/query的数量

lock vs latch

在数据库系统中，lock与latch有不同的含义。

lock是用于在事务中保护数据库中的逻辑数据，操作的对象例如数据库对象，relation对象，在事务commit或者rollback后才会释放。定义了事务对数据库中资源的访问模型。

latch是low level的操作原语，用于对数据库系统内存中数据的一致性保护。保证并发的安全性。Latch是对内存数据结构提供互斥访问的一种机制，轻量级的，忙等的，不入队的。

Buffer Pool通用优化技术

在Buffer Pool中可以根据数据库内核中的一些统计信息、query语句的执行计划来对buffer pool的行为进行优化，使得Buffer Pool能有更好的性能。在这个优化的过程中一般要考虑全局最优和局部最优的一个折衷。局部最优是指根据一个事务的上下文，对buffer pool进行frame调度，使得buffer pool对当前事务的性能最优。但是局部最优并不一定是全局最优的，全局最优是指buffer pool调度frame使得对所有事务的总体性能最优。

常有的优化技术有：

1. 多个buffer pool
2. pre-fetching
3. 共享磁盘IO
4. buffer pool bypass

多个buffer pool

如字面意思，在数据库系统中不是指维持一个buffer pool，而是维护多个buffer pool。每个buffer pool可以跟一个database或者page相关联，或者根据workloads的不同，使用不同的buffer pool。每个buffer pool可以根据其独自的情况使用不同的管理策略，这样的优点是：

1. 局部性提高
2. 减少了latch竞争（当有多个buffer pool时，有多个page table，多线程可以访问不同的page table，进而减少了latch竞争）

在多个buffer pool的情形下，数据库系统将page映射到某个buffer pool的方式有两种：

1. 建立一个buffer pool划分对象的id到buffer pool的映射表
2. hash（MySQL实现方式）

pre-fetch

1. 空间局部性预取，减少随机IO（OS亦能完成）
2. 根据query的execution plan，预取其需要的page（OS无法完成）

共享磁盘IO

1. scan sharing1：buffer pool将多个query的读写请求batch起来，如果是读取相同的page，则可以共享IO的结果；另一方面可以重组IO顺序，可以减少磁头移动的时间。
2. scan sharing2：当query A的读取请求和已经在执行的query B的读取请求近似时，可以将A的cursor绑定到B的cursor，这样就共享了当前正在进行的磁盘IO，当B的IO结束后，数据库系统再将A还没有执行的IO继续执行，完成A的全部IO请求。（只有DB2和MSSQL支持，ORACAL只支持数据库完全一致IO情况下的cursor sharing）。另外关系模型的无序性导致一些查询可以从这个机制中获得额外的优化，例如limit 100。

buffer pool bypass

此技术原理为，不将获取到的page数据存储到buffer pool中。因为有些query是查询大量数据但是只使用一次，如果放到buffer pool中会导致buffer pool被污染。也就是说当前query的局部性导致buffer pool的全局性受到大影响。

另外对当前query可以创建一个临时的buffer，当query执行结束后就删除这个临时buffer pool，适合于一些sorting，join等操作。

Buffer置换策略

置换策略的目标：

1. 正确性
2. 准确性
3. 快速（latch持有时间短）
4. 额外的数据结构少

CLOCK LRU

图2: CLOCK LRU

不需要为每一个page维护一个timestamp，为每个page维护一个reference bit。当page被访问时，reference bit置1。page以circular buffer 的形式组织，用一个clock hand指向一个page；当需要淘汰时，如果reference bit是0则淘汰当前page，如果是reference bit是1则置0，移动clock hand到下一个frame。

CLOCK LRU的缺点是不能应对sequential flooding的情形。

LRU-K

ref：//www.greatytc.com/p/c4e4d55706ff

LRU-K中的K代表最近使用的次数，因此LRU可以认为是LRU-1。LRU-K的主要目的是为了解决LRU算法“缓存污染”的问题，亦即上述sequential flooding，其核心思想是将“最近使用过1次”的判断标准扩展为“最近使用过K次”。

相比LRU，LRU-K需要多维护一个队列，用于记录所有缓存数据被访问的历史。只有当数据的访问次数达到K次的时候，才将数据放入缓存。当需要淘汰数据时，LRU-K会淘汰第K次访问时间距当前时间最大的数据。

LOCALIZATION

数据库系统根据每一个query或者事务的统计信息，在buffer pool中淘汰选择的page。

PRIORITY HINTS

给page分配优先级，置换时考虑优先级。

Dirty Pages处理

在淘汰一个page时，如果一个page不是dirty page，则可以直接将此page从内存中移除，因为此page在内存中和disk中是一致的。如果此page是dirty page就需要将此page的数据更新到磁盘中。此时有两种解决方法：

1. 置换时写出。性能肯定很差，因为系统要等待磁盘IO完成
2. 后台写出。使用一个后台线程来周期性将dirtypage更新到磁盘上。需要注意dirty page写出时必须保证日志已经更新。

NOTE

数据库中其他缓存：

1. sorting + join buffers
2. query cache
3. maintanance buffers
4. log buffers
5. dictionary buffers

参考：

CMU 15-445/645 05
《Database System Concepts 7th editon》