# Buffer Pools

上节中提到，DBMS 的磁盘管理模块主要解决两个问题：

1. 如何使用磁盘文件来表示数据库的数据（元数据、索引、数据表等）
2. （本节）如何管理数据在内存与磁盘之间的移动

本节将讨论第二个问题。管理数据在内存与磁盘之间的移动又分为两个方面：空间控制（Spatial Control）和时间控制（Temporal Control）

#### Spatial Control

空间控制策略通过决定将 pages 写到磁盘的哪个位置，使得常常一起使用的 pages 能离得更近，从而提高 I/O 效率。

#### Temporal Control

时间控制策略通过决定何时将 pages 读入内存，写回磁盘，使得读写的次数最小，从而提高 I/O 效率。

整个 big picture 如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUJRryGLyHUdcOnhD0%2FScreen%20Shot%202019-02-24%20at%207.43.51%20PM.jpg?alt=media\&token=5ca91d06-1e09-43be-afd2-5a52918ad9c9)

本节的提纲如下：

* Buffer Pool Manager
* Replacement Policies
* Allocation Policies
* Other Memory Pools

## Buffer Pool Manager

DBMS 启动时会从 OS 申请一片内存区域，即 Buffer Pool，并将这块区域划分成大小相同的 pages，为了与 disk pages 区别，通常称为 frames，当 DBMS 请求一个 disk page 时，它首先需要被复制到 Buffer Pool 的一个 frame 中，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUL8f0p1WjNRGMIHPo%2FScreen%20Shot%202019-02-24%20at%207.51.24%20PM.jpg?alt=media\&token=01bd6968-510b-4625-bfdd-18dbcc44bb0c)

同时 DBMS 会维护一个 page table，负责记录每个 page 在内存中的位置，以及是否被写过（Dirty Flag），是否被引用或引用计数（Pin/Reference Counter）等元信息，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUL_hS_6EBXlhpQYor%2FScreen%20Shot%202019-02-24%20at%207.53.21%20PM.jpg?alt=media\&token=f26dd21a-fc01-4a36-a42e-68eab4d85e2c)

当 page table 中的某 page 被引用时，会记录引用数（pin/reference），表示该 page 正在被使用，空间不够时不应该被移除；当被请求的 page 不在 page table 中时，DBMS 会先申请一个 latch（lock 的别名），表示该 entry 被占用，然后从 disk 中读取相关 page 到 buffer pool，释放 latch。以上两种过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUP5rlT7qWNo8qYSuD%2FScreen%20Shot%202019-02-24%20at%208.08.44%20PM.jpg?alt=media\&token=f492f425-12b9-47bc-af9a-b4e2430e12bf)

### Multiple Buffer Pools

为了减少并发控制的开销以及利用数据的 locality，DBMS 可能在不同维度上维护多个 Buffer Pools：

* 多个 Buffer Pools 实例，相同的 page hash 到相同的实例上
* 每个 Database 分配一个 Buffer Pool
* 每种 Page 类型一个 Buffer Pool

### Prefetching

DBMS 可以通过查询计划来预取 pages，如：

* Sequential Scans
* Index Scans

![Sequential Scans](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUSLzxnuEQMtJzuytG%2FScreen%20Shot%202019-02-24%20at%208.22.53%20PM.jpg?alt=media\&token=cf9600a4-fb0f-461f-a3d4-8f2cd98dd4e9)

![Index Scans](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZUa28zEosfmp4uFA77%2F-LZUSUIOuhnXVYFlFaxA%2FScreen%20Shot%202019-02-24%20at%208.23.30%20PM.jpg?alt=media\&token=b991109e-99cb-45a0-a574-806b001ae3ac)

### Scan Sharing

Scan Sharing 技术主要用在多个查询存在数据共用的情况。当两个查询 A, B 先后发生，B 发现自己有一部分数据与 A 共用，于是先共用 A 的 cursor，等 A 扫完后，再扫描自己还需要的其它数据。

### Buffer Pool Bypass

当遇到大数据量的 Sequential Scan 时，如果将所需 pages 顺序存入 Buffer Pool，将造成后者的污染，因为这些 pages 通常只使用一次，而它们的进入将导致一些可能在未来更需要的 pages 被移除。因此一些 DBMS 做了相应的优化，在这种查询出现时，为它单独分配一块局部内存，将其对 Buffer Pool 的影响隔离。

### OS Page Cache

大部分 disk operations 都是通过系统调用完成，通常系统会维护自身的数据缓存，这会导致一份数据分别在操作系统和 DMBS 中被缓存两次。大多数 DBMS 都会使用 (O\_DIRECT) 来告诉 OS 不要缓存这些数据，除了 Postgres。

## Buffer Replacement Policies

当 Buffer Pool 空间不足时，读入新的 pages 必然需要 DBMS 从已经在 Buffer Pool 中的 pages 选择一些移除，这个选择就由 Buffer Replacement Policies 负责完成。它的主要目标是：

* Correctness：操作过程中要保证脏数据同步到 disk
* Accuracy：尽量选择不常用的 pages 移除
* Speed：决策要迅速，每次移除 pages 都需要申请 latch，使用太久将使得并发度下降
* Meta-data overhead：决策所使用的元信息占用的量不能太大

### LRU

维护每个 page 上一次被访问的时间戳，每次移除时间戳最早的 page。

### Clock

Clock 是 LRU 的近似策略，它不需要每个 page 上次被访问的时间戳，而是为每个 page 保存一个 reference bit

* 每当 page 被访问时，reference bit 设置为 1
* 每当需要移除 page 时，从上次访问的位置开始，按顺序轮询每个 page 的 reference bit，若该 bit 为 1，则重置为 0；若该 bit 为 0，则移除该 page

### LRU 与 Clock 的问题

二者都容易被 sequential flooding 现象影响，从而导致最近被访问的 page 实际上却是最不可能需要的 page。为了解决这个问题，又提出了 LRU-K 策略。

### LRU-K

LRU-K 保存每个 page 的最后 K 次访问时间戳，利用这些时间戳来估计它们下次被访问的时间，通常 K 取 1 就能获得很好的效果。

### Localization

DBMS 针对每个查询做出移除 pages 的限制，使得这种影响被控制在较小的范围内，类似 API 的 rate limit。

### Priority Hints

有时候 DBMS 知道每个 page 在查询执行过程中的上下文信息，因此它可以根据这些信息判断一个 page 是否重要。

### Dirty Pages

移除一个 dirty page 的成本要高于移除一般 page，因为前者需要写 disk，后者可以直接 drop，因此 DBMS 在移除 page 的时候也需要考虑到这部分的影响。除了直接在 Replacement Policies 中考虑，有的 DBMS 使用 Background Writing 的方式来处理。它们定期扫描 page table，发现 dirty page 就写入 disk，在 Replacement 发生时就无需考虑脏数据带来的问题。

## Allocation Policies

Allocation Policies 指 DBMS 如何为不同的查询分配内存，可以分为 Global Policies 和 Local Policies。前者指同时考虑所有查询来分配内存，后者指为单个查询分配内存时不考虑其它查询的情况。

## Other Memory Pools

除了存储 tuples 和 indexes，DBMS 还需要 Memory Pools 来存储其它数据，如：

* Sorting + Join Buffers
* Query Caches
* Maintenance Buffers
* Log Buffers
* Dictionary Caches

## 参考：

[slides](https://15445.courses.cs.cmu.edu/fall2018/slides/05-bufferpool.pdf), [video](https://www.youtube.com/watch?v=_vRG1ksPlXs\&list=PLSE8ODhjZXja3hgmuwhf89qboV1kOxMx7\&index=5)