第 6 章 数据库存储层
6.1 存储层的基本设计要素
在存储基础中，我已经介绍了关于硬盘的一些基础知识，这些知识应该能够帮助读者理解接下来要讨论的数据库的存储层设计。
在这篇文章中，我会简单地设计一个数据库存储数据的物理结构，并简述这种设计背后的一些考量。这种物理结构的设计和前文5.4中提到过的 FAT32 文件系统的结构会有一些相似之处，如果对本文有不能理解的地方，可以回到上一篇文章去回顾一下 FAT32 的结构。
6.1.1 数据库系统对数据存储的需求
从前文介绍的内容中可以看出，相对来说，硬盘的顺序读写的性能通常是随机读写的好几十倍，从这个硬件特性出发，我们涉及存储的核心目标就是，多用顺序读写，少用随机读写，如果一定要随机读写的，最好是能积少成多，尽可能凑成顺序读写。
对应到数据库对硬盘的需求上，一般的数据库对硬盘的读写有2种不同的需求，对应的也有不同的设计方案。
6.1.1.1 顺序读写，立刻刷盘
这种需求常见于数据库系统中存在的各种日志，例如维护事务状态的日志、记录对硬盘进行过的变更的WAL日志等，这一类存储需求的特点是始终都是顺序写入和顺序读取，对缓存几乎没有什么需求，希望写入的数据能立刻落盘。
6.1.1.2 随机读写，异步刷盘
这种需求常见于数据库中各种实际上的使用场景，例如，在插入 B+ 树时，新的 B+ 树的节点的物理位置通常没法和之前的邻居紧挨在一起，这也导致在遍历 B+ 树时实际上可能需要进行随机读取才能读取到下一个节点。
此外，用户在更新原有的数据时，很可能是在原有的地方进行修改，这也导致了用户修改数据的请求很可能是一种随机写入。
尽管这类需求对硬盘的要求比较苛刻，大部分都是随机读写，但数据库对这一类读写操作的即刻落盘要求不高，通常来说，数据库系统只是要求进行的操作在内存中立即可见，也就是说我们仅仅需要修改缓存，并可以在事后进行异步落盘，这也为优化提供了空间。
对以上两类不同的读写需求，对应着完全不同的方案。读者也能发现，对于顺序写入，立刻刷盘这种需求来说，我们能做的优化和设计其实并不多，这是一种相对来说简单的读写场景。本文重点来讨论针对随机读写，异步刷盘的场景如何对数据库的存储层进行设计。
6.1.2 存储层设计的考虑要素
6.1.2.1 Data locality
正如5.3 所展现地，我们的硬盘喜欢读取连续的数据，而非零散的数据。尽管实际上要面对的是随机的读写请求，我们在设计存储层的时候，也要创造机会，从实际上的业务语义出发，通过预留空间等方式，让经常可能被一起读写的数据尽可能相邻。
6.1.2.2 空间分配和回收
由于数据是零散的，如何高效分配和回收空间是存储层必须考虑的一个问题。例如，在数据库的使用过程中，用户删除了数据，或者是数据库以前产生的快照已经不再使用，这部分的空间要怎么回收呢？
如果回收不够及时，就会造成空间浪费，同时，由于已经不使用的数据长期占着存储空间，很可能会影响数据局部性。
图 6.1: 不再使用的数据造成数据碎片影响数据局部性
数据库工作的环境是相对高压力的，需要一种高效、尽可能并行化的方法来管理空间的分配和回收，尽可能避免出现单点瓶颈。
6.1.2.3 Overflow和变长数据
另一个很重要的考虑是超长数据和变长数据的存储。超长数据很可能本身的大小超过了一个最小单元能够存储的大小（类比 FAT32 文件系统中一个簇无法存下的数据），这类超长数据的管理是十分复杂的，在 FAT32 中，就使用了链表来管理这部分超长的数据，在回收空间时回需要额外的工作。
另一种很难处理的数据类型是变长数据，变长数据虽然现在能够在一个数据单元中存下，但由于变长的特性，可能之后就无法在这么小的空间里存下了。支持变长数据的好处是能够节省一些磁盘空间，不必在创建记录的时候就把所有空间都分配完毕，但日后的管理成本也是巨大的。
可以看到，数据库存储层的设计还是面临很多问题需要考量的。
6.2 一个简单的存储层设计
在前文，对存储层设计需要考虑的方面进行了简单的介绍。在这一节，尝试着从零开始设计一个简单的数据库存储层，并介绍设计背后的各种考虑。
6.2.1 寻址与分页
首先应该意识到，不论我们的存储层设计如何，我们都需要一个方式来表示数据存储的位置，也就是数据的地址。
理论上来说，我们可以使用从文件起始位置到数据开始位置的 offset 作为地址，但是这种方式对硬盘并不友好。如前文5.3所述，硬盘本身就是有读取放大的，因此，基本可以认为，一次性读取的数据一定要大于 4K，否则会造成很大的读取放大，也不会对性能有什么帮助，对新的 SSD 来说，一次性读取的数据可以更大，可以采用激进的64K等方案。
图 6.2: 分页示意
既然有了最小读取大小的限制，这就必然要求我们对地址空间进行分页了，分页的大小，以 MySQL 为例，设置在 16KB。
6.2.2 页内空间管理
在明确了使用分页的方式来方便寻址之后，我们需要意识到，一个页的大小（16KB或者更大）对于存储单纯的一条数据来说可能还是太大了。有没有办法，更好地来管理空间，提高空间的利用率呢？
这就涉及到业内空间的管理方式了，在这里，我们使用常见的方式，在页的底部存放与页的信息相关的重要数据，并且让分配给用户的空间从页的顶部开始向下增长，下面是空间管理的示意图。
图 6.3: 页内空间管理示意图
需要指出的是，这种地址管理方式存在一个潜在的缺陷，有一定改进的空间：
在这种地址管理方式中，数据的起始位置由 页号+在页内的偏移 共同确定。这种方式中，如果需要对页的数据进行部分的空间回收，就不能移动其他项所在的地址，因为这会导致在其他地方记录的数据地址不准确。
一个可能的改进是，我们可以不使用页内偏移，而是给数据项一个编号，每次读取数据时，把整个页读出，随后找到编号相符的数据项即可。
图 6.4: 不同地址表示方式造成的空间碎片
6.2.3 Extent
分页制能够避免读写放大造成的硬盘性能浪费，但一个页通常只有 16KB，其实是相对较小的，存几条用户数据就不够用了。为了保证 Data locality，也就是尽可能使会被一起使用的数据在硬盘上的位置相邻，这里我们还需要引入另一个概念——Extent。Extent 的实质是利用空间预分配这一手段，来为后续可能的邻居留出空间，以此来促进数据局部性。
每个 Extent 由可以配置数量的 Page 组成，通常一个 Extent 包括 1000-2000 个 Page。
除了保证数据局部性之外，Extent 这一设计还有一个比较重要的作用，有利于提高空间分配算法的并发度，每个 Extent 都会维护一个自己所包含的 Page 的空闲情况，当用户需要分配一个空间时，系统会快速索引出一个能够满足需求的 Extent ，随后，用户的请求会被分配到具体的 Extent 去执行，从而避免了所有的用户请求都在等同一个地方分配空间的问题。
图 6.5: Extent和空间分配算法
6.2.4 Copy On Write 优化
最后，来提空间分配之外的一个优化手段。
前文提到，变长数据的处理是相对复杂的，那么怎么简化这个过程呢？
可以使用名为 CoW 的方案来简化相关过程，在这个方案中，每个数据项的长度在被创建时就是固定的，事后不可以再被修改。
需要注意的是，我们这么设计并没有断绝了数据项在日后扩展长度的可能，如果需要一个空间更大的数据项时，可以先分配一个更长的空间，复制原数据项的信息到新的空间中，这样就能够扩展数据项的长度。这样一来，我们实际上把数据变长变成了分配空间-回收空间的过程，简化了管理。
这种做法经常被称为Copy On Write，或 CoW，写时复制。这种做法在一些文件系统中也有涉及，例如 btrfs 默认使用的就是 CoW 机制。此外，由于 SSD 这类硬件的特性，写入和擦除操作是分离的，通常 SSD 的固件会避免原地擦除后重新写入数据，因为这种操作会对同一个闪存块造成过度损耗。SSD 的主控会从已经擦除的块中选择一个磨损较小的，将原先的数据复制出来并写入进去，也就是说，SSD 这类硬件在底层天然执行的就是 Copy On Write 机制。
6.3 缓存池
前文6.2介绍了数据库的一个基本物理存储结构。在这个部分之上，缓存池是一个极其重要的部分。本文来对缓存池的作用和原理做一些简单介绍。
6.3.1 预读和重复利用
缓存池顾名思义的第一个作用就是将可能要用到的数据先缓存起来，这样当用户需要使用这部分数据的时候就可以直接从内存中拿到，而不用再回到硬盘挨个读取。
以前文中提到的存储结构为例，缓存池在读取文件的时候，可以将整个Page 的数据全部读取出来，避免多次重复读取。
另外，已经使用完毕的数据也可以保留在缓存池中一段时间，避免重复读取硬盘。
图 6.6: 缓存池与页中数据
6.3.2 异步刷盘
缓存池还负责异步刷盘的管理。如前所述，我们的硬盘喜欢顺序写入操作，对于随机写入操作，实际上，所有的写入动作也是直接进入缓存池的，也就是说，所有对数据的写入操作默认都是在内存中进行的。当缓存池满，需要淘汰数据，或者按照一定的策略需要触发刷盘时，缓存池需要给出目前还没有刷盘的数据列表，并负责对这些数据进行刷盘。
6.3.3 并发控制
最后一个很重要但很少有人提及的点是，缓存池在绝大多数的数据库系统中都负责 Latch 的管理。在数据库系统中，通常有 2 种不同的锁，第一种被称为 Lock ， 第二种被称为 Latch 。 其中，Lock 更多是对外的概念，例如，对某一行数据的一个锁，这种锁是具有业务意义的，Lock 依附于事务存在，甚至可能存在死锁等复杂场景，需要长时间保有。
而，Latch 是数据库内部的锁，Latch 负责进行最基本的数据库组件的并发管理，并不关心事务等概念，每个 Latch 的生命周期也很短，不会有持续时间和事务一样长久的 Latch 出现。举例来说，在 B+ 树的插入时，需要对 B+ 树的节点加锁，这时加的锁就是 Latch 而不是 Lock。
分清 Latch 和 Lock 是十分重要的，数据库对外展现的所有和锁有关的概念，例如“行锁”，都是 Lock 实现的概念，而 Latch 是用来保证数据库自身在并发状况下正确性的锁，对外不能观测到，所有的 Lock 的实现都应该不依赖 Latch 进行，否则就意味着长事务等会直接拖慢数据库自身的运行速度。
如何理解利用缓存池来实现 Latch 呢？举例来说，在我们的设计中，缓存池会保证每一个页中的数据项都是全局唯一的，用户通过地址取数据项时，总是会返回缓存池中的同一个对象，用户对数据项加锁时，其他要读写这个数据项的线程也能感受到。
通过这种保证，数据库在数据项这一最小的数据单元上就实现了并发控制，上层的其他内容，例如 B+ 树的节点，底层都绑定了一个数据项，通过对数据项加锁，我们实际上可以实现对 B+ 树节点的锁。
可以指出，Latch 和 Lock 尽管在概念上区别很大，但在实现上并不一定有很大的区别，举例来说，大部分数据库的 Latch 都是直接依赖操作系统提供的多线程同步工具(信号量、mutex 等)来进行的。Lock 的实现多种多样，但也可以通过简单的 mutex 来进行。
6.3.4 缓存池的设计
缓存池的设计，有两个需要注意的点，一个是保证缓存池的正确性，不要淘汰掉不应该淘汰的数据，另一个则是讨论如何高效地淘汰数据
6.3.4.1 正确性
有一些数据，在缓存满时也是不能淘汰的。这一类数据简单来说就是还有人在使用的数据，具体来说，就是还有线程持有对这个数据的 Latch 的数据，缓存池在实现时应该充分考虑这种情况，避免淘汰使用中的数据引起程序错误。
那么，缓存池如何知道一个数据是否还有人在使用呢？我们认为，我们可以设计一种缓存池数据的使用协议，并保证所有的使用方都需要遵守这个协议，只要遵守了这个协议，缓存池就能保证其行为的正确性。
6.3.4.2 使用协议
接下来，我们来设计这样一个基本的协议，首先来分析几种数据在缓存池中的不同场景，按照是否有使用方、是否有数据变更，可以分为以下三种场景：
- 没有使用方，没有数据变更
对于这种情况，缓存池可以直接淘汰数据，不需要做任何额外的操作
- 没有使用方，有数据变更（与磁盘上的数据有差异）
对于这种情况，缓存池可以淘汰数据，但必须在淘汰数据前把数据落盘，不然下次读取数据的时候就会读到脏数据
- 有使用方
对于这种情况，不论有没有数据变更，缓存池都不能淘汰数据
我们要设计的“协议”，其实就是规范使用方调用缓存池的方式，让缓存池能够知道，有没有使用方、有没有数据变更。
因此，协议可以这么设计：
obtain()在使用数据前，使用方必须调用obtain()方法，这个方法会给缓存池内部维护的数据引用计数 +1，缓存池确保在引用计数清零前不能淘汰数据release()当使用完成后，使用方必须调用release()方法，这个方法与obtain()做的事情相反commit()当使用方修改数据后，必须调用commit()让缓存池知道数据已经被修改
只要遵守了上述协议，缓存池就能够正确发挥作用。
6.3.4.3 缓存池的淘汰策略
接下来，讨论缓存池的不同淘汰策略。
6.3.4.3.1 FIFO
FIFO 是指先入先出的淘汰策略，这种策略极其简单，你可以把缓存池视为一个队列，新加入缓存池的数据项位于队首，而第一个加入缓存池的数据项位于队尾，当缓存池满时，队尾就会第一个被淘汰出去。
FIFO 是一种极其简单的淘汰策略，在一些情况下也确实好用，但是在数据库场景下有一些不足，这里讨论这些问题：
- 短期热点问题：FIFO 可能会导致一些短期内频繁使用的数据被淘汰。比如，某一数据项短时间内被多次访问，但因为其入队列的时间较早，可能会被淘汰，导致未来再次访问时又需要从磁盘读取。
- 不适应复杂的访问模式：数据库中的数据访问模式非常复杂，有的数据可能周期性地被访问，而有的数据长时间没有被访问后可能很快就会被再次访问。FIFO 策略并不考虑这些模式，可能导致频繁的磁盘IO。
为了解决上述问题，我们需要考虑我们实际应用场景的数据访问模式，例如，如果存在短期热点的场景，通常使用 LFU (Least Frequently Used) 策略，来保证经常访问的数据不会被缓存池淘汰，而如果是顺序扫描数据的场景，可以使用 LRU (Least Recently Used) 策略来保证长时间没有访问到的数据会被缓存池淘汰，而最近访问过的不会。
6.3.4.3.2 LRU (Least Recently Used)
LRU 是基于数据的历史访问记录来决定哪些数据被淘汰的策略。它会淘汰最长时间未被访问的数据。例如，某项数据一直被读取，那么它就不会被淘汰，这比 FIFO 要好得多。
具体来说，当一个数据项被访问时，LRU 会将其移动到缓存池的最前端，当需要淘汰数据时，LRU 会选择最后端的数据进行淘汰，因为它是最长时间未被访问的。
通过上面的描述，读者可以大概猜到，LRU 可以使用链表来实现，每次某数据被访问时，就把它移动到链表头部，每次需要淘汰数据时，就从链表尾部开始淘汰。
LRU 虽然对 FIFO 做了改进，但是依然不善于应对周期性的读取模式。
6.3.4.3.3 LFU (Least Frequently Used)
LFU 基于数据的访问频率来决定哪些数据被淘汰。它会淘汰访问频率最低的数据。
基于 LFU 的缓存池维护了一个频率计数器，每当数据项被访问时，其对应的频率计数器增加，当需要淘汰数据时，LFU 选择频率最低的数据进行淘汰。
LFU 能够很好地处理长期的访问模式。即使一个数据项在短期内没有被访问，但只要它的长期访问频率足够高，它仍然可以保留在缓存中，也就是说，对于有明确访问热点的工作负载，LFU可以提供非常好的性能。
LFU 的最大问题是，实现起来比较复杂，计算淘汰元素时需要耗费较多的 CPU 时间，对于要求性能的缓存池来说，有时候并不合适。
总结来说，选择哪种缓存淘汰策略应根据具体的应用场景和工作负载来决定。在某些情况下，可能需要结合 LRU 和 LFU 的特点，使用如 LRU-K 或 SLRU 等混合策略来达到最佳效果。
6.3.4.3.4 时钟算法
接下来，介绍一种工程上常用的 LFU 近似算法。
时钟算法通过维护一个循环链表（形象地称为“时钟”）来模拟最近使用情况，每个节点代表一个缓存页，并且每个节点有一个使用位（通常称为“时钟指针”）。下面是时钟算法的基本流程：
- 初始化：创建一个循环链表，链表中的每个节点代表一个被缓存的数据，每个节点都有一个使用位（标志位），初始化时，所有节点的使用位都设置为0。
- 访问页面：当访问一个页面时，如果该页面已在缓存中（即在循环链表中），则将该页面对应节点的使用位设置为1（表示该页面最近被使用过）。
- 替换页面：当需要载入一个新页面而缓存已满时，时钟算法会查看当前时钟指针指向的节点：
- 如果该节点的使用位为1，则将它设置为0（表示该页面不再是最近使用），然后时钟指针向下移动到下一个节点。
- 如果该节点的使用位为0，则将当前页替换为新的页面，并将新页面的使用位设置为1，同时保留时钟指针位置。
这个过程像一个时钟一样不断循环，因此得名“时钟算法”。
时钟算法通过“使用位”的概念赋予了经常被使用的数据逃过一劫的机会，同时，通过指针旋转的动作避免了将最近刚加入缓存池的数据淘汰出缓存，可以认为是一种近似的 LFU 算法