企业官网建设流程全解析

回顾Lec3-5，我们解决的问题：How the DBMS represents the database in files on disk?

我们从物理结构出发，分析了页如何在磁盘内组织，数据如何在页内组织，如何表示一条记录（tuple），如何高效管理变长记录，如何压缩以榨取更多价值

这个lec我们将解决这个新的问题：How the DBMS manages its memory and move data back-and-forth from disk

解决这个问题的过程中，我们将着眼于两个问题：

一个在lec3-5中提出的旧问题，如何尽可能减少磁盘 I/O

一个新的问题，如何防止OS捣乱

buffer pool服务于这两个目标

lec3-5中我们只是管理了disk上的文件，但是没有解决”如何高效的把数据从磁盘搬到内存“这个问题：

每次查询都从磁盘读？太慢！

把所有数据都放内存？内存不够大！

所以 Lec 6 要解决：如何用有限的内存，缓存热点数据，最小化磁盘 I/O

从DBMS的视角来看，整个database看起来好像都在内存中，尽管实际上database所占用的空间可能超过系统中可用的内存。然而DBMS不需要关心数据是怎么被取到内存中来的，也不需要关心数据如何被管理

因此，我们需要从两个方向来优化：空间与时间

空间上，尽可能让那些经常一起使用的页面在磁盘上尽可能靠近

时间上，控制页面什么时候被写入内存，什么时候被写回磁盘，以尽可能减少必须从磁盘读取数据而造成的停顿

Buffer Pool Manager

Buffer Pool 是位于内存和磁盘之间的、以页面为单位的内存缓存。它本质上是数据库内部申请的一大片内存区域，用来临时存储页面。

Buffer Pool 的基础实现如图，frame array是实际存储 page 的内存区域，左边的pagetable存page id到frame id的映射

与此同时，我们需要有替换策略，当frame array满的时候，我们需要选择驱逐哪个frame

DBMS 还维护一个 page directory，页面目录，它是从 page id 到数据库文件中页面物理位置的映射。Page directory 存储在磁盘上以保证持久化，但通常会被缓存在内存中，以降低页面访问延迟。

功能上来讲，DBMS需要这块buffer pool来完成很多工作，具体来说包括：

• Tuple Storage and Indexes，元组存储和索引

• Sorting and Join Buffers，排序和连接缓冲区

• Query and Dictionary Caches，查询缓存和字典缓存

• Maintenance and Log Buffers，维护缓冲区和日志缓冲区

page table 与 page directory

page directory是从 page id 到物理数据库文件中页面位置的映射。所有修改都必须被记录到磁盘上，这样 DBMS 在重启时才能找到它们。

page table是从 page id 到缓冲池 frame中某个页面副本的映射。这是一个内存中的数据结构，不需要存储在磁盘上。

metadata

缓冲池拥有的元数据存放在pagetable中，主要包括dirty flag和pin counter

dirty flag会在线程修改页面时被set。这向storage manager表明，在该页面被驱逐之前，必须先将它写回磁盘

pin counter会跟踪当前正在访问该页面的线程数量，无论是读还是写，线程在访问页面之前必须先增加这个计数器，使用完毕后减少计数器

如果pin count 大于 0，那么 storage manager 不允许把这个页面从内存中驱逐出去

并发

我们需要区分DBMS中的lock和latch

latch 保护的是DBMS 内部数据结构的物理一致性

lock 保护的是数据库逻辑数据的事务隔离性

latch就是我们OS里学到的，保护临界区域的那种“锁”，用来保护内存DBMS数据结构别被并发破坏掉，是DBMS内部用的。

而lock是在更宏观的角度，用来保护DBMS本身事务的锁，用来保护数据库的逻辑对象（例如tuple, table, index record等）

很自然的，当我们更新一条记录的时候，两者都会用到，首先为了事务隔离，需要使用lock，具体修改时，为了安全修改内存的page，需要使用latch

OS与DBMS

学习这个lec的时候，总是有点混淆OS和DBMS各自负责的内容，理了很久终于是理清楚了。

首先，DBMS做为运行在OS上的软件，看起来DBMS做的事情就是把自己在管理的那些文件拉出来，又围绕着这些文件做了一层新的文件系统和内存管理。为什么要这么做？因为对于DBMS来说，OS做的这些事情是“不可控的”，这会让DBMS没有“安全感”。

但是具体来说，DBMS并不是完全接管OS的职能，而是，DBMS通过一些特定的方式“绕过”OS的一些机制，但是底层仍然需要OS的系统调用来访问硬件

为什么OS做事，DBMS不放心

因为OS提供的file system和memory management是通用的，用以服务所有的应用程序，但是DBMS有特殊的需求，而OS不知道这些需求：

1. OS不知道哪些数据更重要，在OS眼里，他只知道这是一个文件，一块内存，一次读写请求，无法根据数据库语义做优化

2. OS 的页面替换策略不适合数据库，OS经常用LRU类似的策略来管理page cache，但是数据库经常会遇到顺序扫描（例如SELECT * FROM huge_table;），这回一次性读取几百万的page，对于OS来说，他会把这些page全读进内存，把之前内存的热点数据都挤出去，而这些进入内存的page又只用一次。对于DBMS来说，它知道这些page只会用一次，所以可以用其他特殊的策略

3. OS不知道事务的存在，DBMS有事务的概念，而OS不知道，如果OS的page cache觉得内存紧张，把脏页刷回磁盘，会破坏事务的原子性和持久性

4. OS会引入不可控的延迟，如果DBMS使用mmap把数据库文件映射到内存，当其访问一个内存不存在的page时：首先触发page fault，然后OS阻塞进程，在磁盘读取page，唤醒进程。这个过程对于DBMS是黑盒的，DBMS不知道这些事情，而它希望可以主动控制自己什么时候读取哪些page

5. OS的文件系统不够灵活，它是给通用程序用的，但是DBMS需要固定大小的page，page之间有逻辑关系，自己能够按照某些方法快速定位某个page，并且按照自己的方式组织page。如果完全依赖OS的文件系统，DBMS就是去了上述的控制能力

DBMS怎么绕过OS

DBMS使用OS提供的最底层接口，但是绕过OS的高层抽象（文件系统缓存、虚拟内存），自己来管理文件布局和内存

绕过OS的page cache

DBMS使用O_DIRECT标志打开文件：

int fd = open("database.db", O_RDWR | O_DIRECT);

这样OS就不会缓存数据库文件的内容，DBMS自己来管理buffer pool，自己实现缓存逻辑，自己管理内存分配

绕过OS的虚拟内存

不用mmap，例如：

void* buffer_pool = malloc(BUFFER_POOL_SIZE); //自己控制读哪个page read(fd, buffer_pool + offset, PAGE_SIZE);

DBMS就知道哪些page在内存里，主动控制IO，而且可以实现自己的替换策略

自己管理文件布局

详见上一篇：Lec3-5的内容

DBMS是在OS的文件系统之上又构建了自己的“文件系统”，对OS来说，这只是几个大文件，而对DBMS来说，这就是一个包含了page directory、heap file、B+Tree、log 的复杂结构

DBMS没有绕过文件系统，仍然使用open,read,write,但是在文件内容的组织上完全自主

fsync problem

我们先回顾一下磁盘的两个系统调用

1. fwrite(): 写入操作系统的缓冲区，这个调用会把数据复制到OS的page cache，然后返回。数据没有到磁盘。只是从DBMS的内存到了OS的内存

2. fsync(): 强制刷盘，OS会把Page cache中的脏页真正写入磁盘，磁盘控制器确认写入完成以后返回。这个时候数据才真的在磁盘上

问题1：DBMS调用fwrite，会发生什么？

很明显，数据只是被写入操作系统的 Page Cache，并没有真正到达磁盘

问题 2：DBMS 调用 fsync，会发生什么？

操作系统把 Page Cache 中的脏页真正写入磁盘，并等待磁盘控制器确认写入完成后才返回

问题 3：如果 fsync 失败（返回 EIO 错误），会发生什么？

Linux中，第一次fsync调用发生磁盘故障，无法写入，返回EIO错误，但是，Linux 把Page Cache中的脏页标记为"干净"。

对于Linux来说，他认为：我是OS，我只负责管理硬件。如果硬件出错了，我告诉你错误（EIO），你应该自己决定怎么处理。如果你重试 fsync，我假设你已经知道第一次失败了，并且已经采取了适当的措施（比如换一个磁盘）。所以我把脏页标记为干净，避免无限重试

所以如果这个时候DBMS没有正确处理错误，再次调用fsync，Linux检查Page cache，发现所有页面都是干净的（没有dirty page），于是认为没有脏页需要刷盘，fsync立即返回成功

DBMS认为，第二次fsync成功了，数据已经在磁盘上了，于是告诉客户端commit成功，认为数据已经持久化。然而，数据根本没有写到磁盘！

很多应用程序，包括早期的数据库，不知道这个行为，天真的重试fsync，导致数据丢失了。

那么正确的处理方法应该是什么？

1. 第一次失败就直接panic，数据库立即停止服务，防止数据损坏，PostgreSQL就是这么做的

2. 重新打开文件，这会让OS重新建立Page Cache，清除之前的标记

3. 使用O_DIRECT，写入时就会绕过Page Cache

Buffer Replacement Policies

LRU

同OS的LRU，需要维护每个页面上次被访问的时间戳

CLOCK

同OS的CLOCK，每个页面拥有一个引用位，被访问时置1，需要替换页面时，需要一个时钟指针开始扫描，如果引用位为1，则置0；如果为0，替换掉该页面

LRU和CLOCK替换策略存在最大的问题，就是前文提到的，发生顺序扫描时，快速读取大量页面，缓冲池被填满，拥有更早时间戳的页面被替换。这样的顺序扫描叫做sequential flooding，顺序泛洪，是指由于顺序扫描导致缓冲池内容被污染

所以我们需要思考，如果有一个页面在一段时间内被频繁访问，即使最近没有被访问，我们也不希望驱逐它

LRU-K

注意：在课程Lec6中所讲解的算法，是MYSQL对于LRU-2的一种近似实现，并不是LRU-K算法。真正的LRU-K算法是在课程的project1-task1中要求我们去实现的

这里我们先讲LRU-K算法：

K表示，判断一个frame/page是否要换出的时候，要看它“倒数第K次访问”的时间。

LRU-1：只看最近一次访问时间，也就是普通 LRU

LRU-2：看倒数第 2 次访问时间

LRU-3：看倒数第 3 次访问时间

我们定义一个值：backward k-distance = 当前时间戳 - 第k次访问的时间戳

我们来举一个例子：假设k=2，当前时间是100，某些frame的访问历史如下：

frame 1: [10] frame 2: [20, 80] frame 3: [30, 60, 90] frame 4: [5]

只保留最近k次访问：

frame 1: [10] // 访问次数不足 2 frame 2: [20, 80] // 倒数第 2 次访问是 20 frame 3: [60, 90] // 倒数第 2 次访问是 60 frame 4: [5] // 访问次数不足 2

计算backward k-distance

frame 1: backward 2-distance = +inf frame 2: backward 2-distance = 100 - 20 = 80 frame 3: backward 2-distance = 100 - 60 = 40 frame 4: backward 2-distance = +inf

根据算法规则，优先淘汰 backward k-distance 最大的，如果访问不足k，距离视为+inf，如果多个都是+inf，淘汰它们中“最早被访问”的那个

这里就应该淘汰frame4，他是最早被访问的+inf

这样的设计正好避免了，遇到顺序泛洪时，会把热点页面淘汰的问题。一般情况下，k值为2

MYSQL对于LRU-2的一种近似实现

接下来我们再来讲课程中MYSQL的实现，SQL 对 LRU-2 的一种近似实现是使用两个链表（new list和old list），并且只从 old list，旧链表中驱逐页面

每当一个页面被访问时：

• 如果它已经在 old list 中，就把它放到 young queue，年轻队列的开头；

• 否则，就把它放到 old list 的开头。

例子如下：

可以看到，第一次访问page1的时候，放入Old List队头，第二次访问page1，移至New list对头，New list队尾的内容同步移动到Old list队头

为什么说近似了LRU-2的思想，因为访问不足2次的页面都会在old list里面，优先被淘汰，而访问次数≥2的页面在new list里，会得到保护

Localization

DBMS 在每个查询的基础上选择要驱逐哪些页面。这最小化了每个查询对 buffer pool 的污染

核心思想就是：Per-query（按查询）替换，不是全局决定替换哪些页面，而是每个查询只能"弄脏"自己分配到的那部分 buffer pool。

照样来一个例子：

这里有个buffer pool有10个frame，其中100-105是热点数据，有很多小查询频繁访问他们

Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: 空闲 Frame 7: 空闲 Frame 8: 空闲 Frame 9: 空闲

而现在来了一个大查询，执行一个全表扫描，假设需要读取从200-1199共1000个页面，但是这些页面又只会读一次，读完就不需要了。那么对于Localization策略，我们给这个大查询分配一个小的buffer pool，我们把frame6-9给他

Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: Page 200 Frame 7: Page 201 Frame 8: Page 202 Frame 9: Page 203

此时frame已满，下一个page204进来的时候，查询只能覆盖自己的这四个frame，frame6变成Page 204，一直循环直到最后

Buffer Pool (10 frames): Frame 0: Page 100 (用户索引) Frame 1: Page 101 (用户表热点数据) Frame 2: Page 102 (订单索引) Frame 3: Page 103 (产品目录) Frame 4: Page 104 (库存表) Frame 5: Page 105 (价格表) Frame 6: Page 1196 Frame 7: Page 1197 Frame 8: Page 1198 Frame 9: Page 1199

前面的热点数据完全不被影响。当查询结束之后，frame6-9的内容就会被标记为可被替换

Priority Hints

让 DBMS 根据查询的上下文信息，给页面打上"重要性标签"，替换时优先驱逐不重要的页面。

不同于 Localization，Priority Hints 是给页面分等级。例如还是上面的情景，我们把frame0-5的部分全部标上priority为High，并且给那些小的查询的优先级全部标为high，遇到顺序扫描的时候，访问的页面全部标记为low，加载新页面的时候，有限替换 priority=low的页面

实现方式：DBMS根据查询特征自动推断/用户指定/动态调整学习

优化Buffer Pool的性能

Multiple Buffer Pools

单个Buffer pool会遇到一个情况，当多个线程都在buffer pool的时候，会产生锁竞争，大量时间会浪费在等锁上，因此，我们可以创建多个独立的buffer pool。

每个buffer pool都可以采用局部策略，这些策略针对其内部存储的数据进行定制

映射方式：

1. Object ID，对象 ID

2. Hashing，哈希

Object ID的方法会扩展 record ID，使其包含一个对象标识符。可以通过这些 object ID 维护从对象到特定缓冲池的映射

另一种方法是 hashing。DBMS 对 page ID 进行哈希，以选择要访问哪个缓冲池

Pre-fetching

预测未来访问，例如我们进行大查询时，如果如果访问了 Page N，下一个大概率访问 Page N+1，因此当访问 Page N 时，后台线程自动预取 Page N+1, N+2, N+3

Scan Sharing

这允许多个查询附着到一个扫描表的单一游标，如果一个查询开始扫描，而此时已经存在另一个活跃扫描，那么 DBMS 会把第二个查询的游标附着到已有游标上

DBMS 会跟踪第二个查询是从哪里加入第一个查询的，这样当它到达数据结构末尾时，就可以完成扫描

但是，当需要按 I/O 付费时，这种方式非常浪费且成本很高

Buffer Pool Bypass

即上文提到的，使用O_DIRECT绕过OS的page cache

这样可以避免双重缓存，但是会让所有的IO都变成真实的磁盘操作

一般适用于大小OLTP的数据库，且内存足够大，不依赖OS

总结

那么到这里，我们已经解答了两个完整的问题：

1. How the DBMS represents the database in files on disk?

2. How the DBMS manages its memory and move data back-and-forth from disk?

到此为止，我们已经基本解决了storage的问题，后面的Lec7-10是storage的自然延申：有了buffer pool，我们如何用它高效的找到数据了

所以到这里关于存储的内容就告一段落啦！