如何实现一个Buffer Pool Manager。
Buffer Pool
Organization
内存区域组织为一个固定页大小（等同数据库页面大小）的数组，其中每个元素称为帧（frame）。
当上层请求访问一个页面时，从磁盘读取该页面后，将在这些frame中保留一个该页面的副本。
如果对副本做出修改，则称其为脏页（dirty page），脏页回写磁盘往往不是立刻执行的。
Meta-Data
页表：负责跟踪当前内存中的页面，主要维护page ID与frame的映射关系，通常实现为线程安全的固定大小哈希表。
如图所示，应当使用latch来确保写入页表时线程安全。
其他元数据：
- Dirty Flag：标记脏页；
- Pin/Reference Counter：统计多少工作线程正在访问该页面；
- Access Tracking Infomation：上次/近几次访问该页面的时间，可以通过该信息在内存不够用时驱逐页面。
～有关latch与lock：～
为了和数据库中锁（lock）的概念用作区分，使用latch来称呼buffer pool中用到的闩锁。latch更接近操作系统中的互斥锁，用于保护切实的数据结构，且无需保证回滚；而lock则是在数据库并行事务时对逻辑数据的保护，需要能够支持回滚。
～有关page table与page directory～
二者在数据库运行期间都存在于内存中。page directory是page id和数据库文件中page磁盘物理位置的映射关系，其所有变更必须落盘确保重启后能够恢复；page table维护的是page id和内存中页面副本之间的映射关系，无需落盘。
why not use mmap
mmap
mmap 将文件内容映射到进程虚拟地址空间，建立“虚拟页 → 文件偏移”的映射关系，实际物理页由操作系统按需从磁盘加载到 page cache。
mmap使用懒加载，具体而言，mmap首先给予用户可用的起始和终止虚拟内存地址，当用户通过虚拟内存访问某页面时，首先发现虚拟页没有映射到物理页，触发缺页中断（page fault），内存检查该页是否已经在page cache中，如果不在则从磁盘读取并建立映射。
假设继续这样操作，直到物理内存已满，无法加载新的页面，触发页面置换。操作系统将中断发起请求的线程，执行页面置换算法淘汰部分页面并加载新页。
problems of mmap
假设我们使用mmap进行内存管理，会存在哪些问题：
- 事务安全：当一次事务中涉及多个页面的修改，按照事务逻辑，其中一个页面发生错误则所有修改回滚。在os中，由于os将自己决定刷新脏页的时机，可能是任何时机，因此可能在事务执行过程中将修改后脏页刷盘，导致其他页面发生错误时无法正确进行回滚；
- I/O停顿：由于数据库不知道内存中到底存在哪些页面，因此会导致查询不可预知的停顿；
- 错误处理：mmap 错误以信号形式暴露（SIGBUS/SIGSEGV），不利于数据库进行细粒度错误恢复；
- 性能问题：操作系统使用mutex维护自己的页表，但性能表现并不好。（为啥不好）
solutions
可以通过一些系统调用解决上面说到的问题：
- madvise：可以向操作系统提供页面访问模式提示（如顺序访问、随机访问、即将访问）；
- mlock：锁定页在物理内存，防止被 swap out；
- msync：可强制将指定映射页写回磁盘。
Buffer Replacement Policies
Least-Recently Used (LRU)
记录每个页面上次被访问的时间，当需要淘汰页面时，选择上次被访问时间距今最久的一个。
我们可以通过按照访问时间排序，以便在淘汰页面时降低检索时间。
但这要求为每个页面访问维护一个时间戳。
Clock
LRU的近似算法，但无需为每个页面维护上次访问时间戳：
- 为每个page保留一个比特位，该比特位用于表示自上次扫描后，页面是否被访问过；
- 当页面被访问时，该比特位设为1；
Clock算法以环形缓冲区组织页面，并在运行时按序对各个页面进行扫描：
- 当指针扫描到某页面时，检查其比特位是否被设为1：
- 如果是，则将其设为0，扫描下一个页面；
- 如果不是，淘汰该页面。
极端情况：假设多轮循环扫描都无法淘汰任何页面，可以考虑返回内存不足的错误，因为这表明当前内存中页面都在被积极使用。
Problem of LRU & Clock：Sequential Flooding
LRU + Clock算法容易受到顺序泛洪（sequential flooding）的影响：
- sequential flooding：顺序扫描查询将大量只访问一次的页面加载进入内存（例如nested join）从而导致真正的热点页被淘汰。
LRU和Clock这种基于最近访问的淘汰策略，容易受到访问模式污染，有时真正的热点页面可能并非最近访问的页面。
LRU-K
为每个页面保留最近K次访问时间，定义Backward K-distance = current timestamp - kth last access timestemp，并淘汰Backward K-distance最大的页面。
MySQL Approximate LRU-K
数据结构：LRU链表，但存在两个Head节点，从而将LRU链表分割为两部分，一个为Old List，一个为Young List。
- 新页面初次访问时，总是插入Old List的头部；
- 如果Old List中的页面被再次访问，则插入Young List的头部。
本质上是近似了LRU-2，对每个页面记录其上次访问时间，并标记当前位于Old List / Young List。
Adaptive Replacement Cache (ARC)
核心思想：ARC将缓存中的页面分为最近访问和最常访问两类，并且自动根据访问模式动态调整两类比例。
ARC维护四个队列：
- 实际缓存：
- T1-Recent：页面刚进入缓存，只命中一次。
- T2-Frequent：命中次数$\ge$两次。
- 幽灵缓存：只存页面ID，不存实际数据
- B1：T1中被淘汰的历史记录。
- B2：T2中被淘汰的历史记录。
ARC工作流程
页面访问请求到达：
- case1：命中T1或T2，将页面移动到T2，表示被多次访问。
- case2：命中B1，说明最近被访问页面被淘汰的太多，因此需要扩大T1容量，缩减T2容量。
- case3：命中B2，说明最近高频页被淘汰的太多，因此需要扩大T2容量，缩减T1容量。
上述T1和T2的容量动态调整通过ARC的自适应参数p实现，在ARC内部维护一个目标大小参数p，表示这是T1的目标大小，系统运行过程中根据B1和B2的运行状况增减参数p。
当需要页面置换时，将根据目标大小参数和T1的实际大小来决定
- case1：$|T1| > p$，说明最近访问队列超标，优先从T1的LRU淘汰。
- case2：$|T1| \le p$，说明最常访问队列超标，优先从T2的LERU淘汰。
Localization
核心思想：不要让一个查询弄脏整个buffer pool，而是让每个查询只影响到自己的一小块缓存。
实际上pg是这样的做法，为每个顺序扫描查询（例如nested join）分配一个小的环形缓冲区，而非整个buffer pool。当该环形缓冲区满，新的数据页将覆盖该小环中的旧页，而不影响全区属于其他查询的缓存。
Priority Hints
给予替换策略一定提示，告知某page是否重要。
Dirty Pages
关于脏页处理：
- 若buffer pool中某页面是干净的，则可以直接drop掉；
- 若为脏页，则必须落盘后才能drop掉该页面。
此时需要在快速页面淘汰和脏页落盘之间进行权衡。
Backgroud Writing：令工作线程定期查看buffer pool，找到其中的脏页并刷入磁盘，写入完成后可以标记页面为clean，在下次置换时能够快速drop。
Disk I/O Scheduling
DBMS维护内部队列来跟踪整个系统的读写请求，请求的优先级将基于一些因素计算决定：
- 顺序/随机磁盘读写；
- 关键任务/后台任务；
- 。。。
OS Page Cache
OS Page Cache 是由操作系统维护的文件数据缓存，对所有进程共享，用于缓存从磁盘读取的文件页面。
当 DBMS 通过 read() 发起文件读取请求时：
内核首先在 page cache 中查找目标页
若命中，则直接从 page cache 拷贝到用户态缓冲区
若未命中，则触发磁盘 IO，将数据读入 page cache
再通过 copy_to_user 复制到用户态返回
从上述过程，可以看到read系统调用下发后，将产生两次文件的拷贝。
因此大多数DBMS选择使用直接I/O，从而跳过OS的page cache，避免冗余副本以及受到OS缓存区淘汰策略的影响。
冷知识：pg依赖于OS的page cache。
Problems of fsync
fsync 依赖操作系统与存储设备的正确写回语义，但存在若干问题：
设备写缓存问题：某些设备会将数据写入设备缓存后立即报告成功，若未开启 write-through / barrier，断电可能丢失数据。
写回错误传播复杂：写回错误可能只在首次 fsync 时报告，后续 fsync 不一定再次报告同一错误，
Buffer Pool Optimizations
Multiple Buffer Pools
允许系统中存在多个而非唯一Buffer Pool，例如每个database/每个page一个buffer pool。
此时内存分配仅在各个buffer pool之间进行分配，能够降低临界区争用，并提升内存局部性。
那么如何决定某个页面归属哪一个buffer pool：
- 使用object id，维护从object id至buffer pool的映射；
- 使用hash，将page id散列到不同的buffer pool。
Pre-Fetching
基于query plan识别出未来需要访问的页面，并预先读取到内存。
例如：顺序扫描，在加载page0的同时可以加载page1，page2…，因为这都是未来需要的页面。
Scan Sharing
Scan Sharing 是一种顺序扫描优化技术，允许多个对同一对象进行全表扫描的查询共享一次物理扫描过程，从而减少重复 I/O 与缓冲池污染。
例如，Q1对table A执行聚合求和计算，从page0开始扫描，到达page3的时候，由于内存页满，page0被替换为page3。
此时，另一个线程发起Q2查询，对table A进行聚合均值计算，同样也需要全量扫描table A。如果Q2仍然从page0开始，那么在我们的例子中随着Q1向下读取、替换，Q2又会不断将置换出的页面重新读回内存，造成重复IO。
scan sharing就是当系统察觉到Q1和Q2实际上要访问的是完全相同的页面，因此允许Q1和Q2共享扫描流，在我们的例子中就是Q2加入Q1当前的扫描位置：
一直到最后一页page5，Q1扫描完毕，Q2将再次回到page0扫描最开始跳过的三个页面：
Buffer Pool Bypass
顺序扫描算子可绕过全局 buffer pool，将读取页面仅保存在查询私有内存中，读取后即丢弃，避免污染共享缓存。
该策略适用于：
大范围顺序扫描
磁盘连续页面读取
临时数据处理（排序、join中间结果）
Informix 中称为 Light Scan。