计算机存储设计理论：从分级存储到LSM树

计算机存储设计理论：从分级存储到LSM树

计算机存储系统的设计是一个复杂而精妙的过程，涉及到多个层次的存储设备和多种优化策略。从寄存器到硬盘，从高速缓存到Page Cache，每一种设计都有其独特的原理和应用场景。本文将从计算机存储分级设计开始，逐步深入探讨IO局部性原理、Page Cache的工作机制，以及顺序IO的优势。最后，我们将详细介绍几种常见的存储引擎，包括哈希表、B树、B+树和LSM树，帮助读者全面理解计算机存储系统的原理和实现方式。

计算机存储分级设计

计算机的存储器设计采用了一种分层次的结构。从CPU内部的寄存器，到高速缓存（L1、L2、L3），再到主存（内存）和硬盘（SSD或HDD），这些存储器的速度逐级递减，而容量逐级递增，价格也越来越低。

在现代计算机中，存储系统可以分为以下几个层次：

• CPU内部存储：包括寄存器、高速缓存L1、L2和L3，这些存储器速度最快，但容量最小。
• 内存：也称为主存，速度比CPU内部存储慢，但容量更大。
• 硬盘：包括SSD和HDD，速度最慢，但容量最大，价格也最低。

IO局部性原理

局部性原理（Principle of Locality）是计算机存储系统设计中的一个重要概念，它指出在程序执行过程中，倾向于访问某些局部特定的数据或指令，而不是随机地访问整个内存空间。局部性原理通常分为两种类型：

• 时间局部性（Temporal Locality）：如果一个数据被访问，那么在近期内它很可能会被再次访问。例如，在一个循环中反复使用的变量。
• 空间局部性（Spatial Locality）：如果一个数据项被访问，那么在其附近的数据项也很可能会被访问。例如，顺序执行的指令和顺序访问的数组元素。

Page Cache

Page Cache是操作系统中用于提高I/O性能的重要组件。在Linux系统中，Page Cache位于系统调用的read/write和底层的硬盘读写之间，利用局部性原理来优化数据访问效率。

工作机制

1. 读取优化：

• 当一个数据页被从硬盘读取到内存时，它被存储在Page Cache中。如果这个数据页在近期内被再次访问（时间局部性），那么可以直接从Page Cache中读取，而无需再次访问硬盘。
• 操作系统通常会预读取一些附近的数据页（空间局部性），并将它们也存储在Page Cache中，以便后续的访问。

2. 写入策略：

• 写回（write-back）策略：数据首先被写入Page Cache，然后在适当的时机被写入硬盘。这种策略可以显著提高写入性能，但需要处理数据一致性问题。
• 写穿（write-through）策略：数据同时被写入Page Cache和硬盘。这种策略保证了数据的持久性，但写入性能较低。

Linux默认使用write-back策略，即文件操作的写只写到Page Cache就返回。Page Cache中被修改的内存页称之为脏页（Dirty Page），脏页在特定的时候被一个叫做pdflush(Page Dirty Flush)的内核线程写入硬盘，写入的时机和条件如下：

1. 当空闲内存低于一个特定的阈值时
2. 当脏页在内存中驻留时间超过一个特定的阈值时
3. 用户进程调用sync、fsync、fdatasync系统调用时

顺序IO

顺序I/O（Sequential I/O）是一种数据访问模式，其中数据按照连续的顺序进行读取或写入。这与随机I/O（Random I/O）形成对比，随机I/O是指数据的访问位置在存储设备上是随机分布的。

顺序I/O的性能之所以高，主要是因为它能够最大化利用存储设备的局部性原理，并且减少了寻道时间和旋转延迟：

1. 局部性原理：在顺序I/O中，数据是连续读取或写入的，Page Cache可以将文件的连续数据块缓存在内存中，以提供快速的连续读取。此外Page Cache可以将内存中缓存的连续数据，比如按页大小批次刷新到硬盘。这样可以减少频繁的硬盘写入操作。
2. 减少寻道时间和旋转延迟：寻道操作指磁头移动到硬盘的正确轨道的过程，旋转延迟指磁头等待硬盘旋转到正确位置的时间。在顺序I/O中，由于数据是连续存储的，因此可以大大减少寻道时间和旋转延迟，从而提高I/O性能。

存储引擎

存储引擎是存储系统的发动机，决定了存储系统的性能和功能。存储引擎主要负责数据如何读写，包括读多写少和写多读少场景，读取操作又分为随机读取和顺序扫描。目前常见的存储引擎使用的存储数据结构主要有：

1. 哈希表（Hash Table）：支持随机读取，但不支持顺序扫描，对应键值 (Key-Value) 存储系统
2. B 树（Balance Tree）：适用于那些需要快速查找、插入和删除关键字的场景，如文件系统、数据库等。
3. B+树（Balance+ Tree）：支持随机读取和顺序扫描，读多写少场景，用于那些需要高效进行范围查询和顺序访问的场景，如数据库、索引等
4. LSM树（Log-Structured Merge Tree）：支持随机读取

Hash Table

在MySQL中，可以使用B+Tree或HashTable作为索引。由于哈希映射关系，哈希表在查找单条数据时，能保证O(1)的时间复杂度。但哈希表在范围查询和排序遍历时，只能进行全表扫描并依次判断是否满足条件，这样就会让性能影响非常大，所以不是特殊场景(譬如 Memory 引擎)不会选择 HashTable 当做底层存储结构。

B Tree

相较于HashTable查找的平均时间复杂度比O(1)稍慢的是O(logn)，这类数据结构有平衡二叉树(AVL Tree)、红黑树(RB Tree)、B树(B Tree)、**B+树(B+ Tree)**等。此类型结构天然就支持排序、范围查找操作。

以平衡二叉树为例，一般情况下查询性能非常好，但平衡二叉树单个节点只能保存一个数据，因此当覆盖大量数据时，平衡二叉树的树高度很高。这意味着当需要通过遍历获取存储在硬盘上的数据时，需要更多次的I/O操作。硬盘读取时间远远超过数据在内存中比较的时间，这将导致程序大部分时间会阻塞在硬盘 I/O 上。

为了降低树的高度，减少I/O操作，可以选择多叉树。B树是一种多叉树，每个节点都存放着索引和数据，相比与平衡二叉树，每个节点能够容纳更多的键值数据，减少树的高度和硬盘访问次数。

B+ Tree

B+树是B树的一种变种，它与B树的区别是：叶子节点保存了完整的索引和数据，而非叶子节点只保存索引值。因此查询索引数据，必须要遍历到叶子节点才能取到，因此查询时间固定为O(logn)。另外一点是，B+tree的叶子节点会有一个指针指向下一个叶子节点，这让所有的叶子节点用单链表的方式连通了起来，这样对于范围查询来说非常方便，能够最大程度的利用pagecache和预读机制。

相较于B Tree，B+ Tree的高度会更矮，范围查询的时间也会稳定一些。但是，B+树在写多场景的性能并不理想。这主要原因是：B+树在插入和删除操作时，可能需要进行节点的分裂和合并，以保持树的平衡。这会导致更新硬盘上多个数据页和Page Cache页缓存数据失效，这些操作伴随大量的随机I/O，限制B+树的写入效率。

LSM Tree

RocksDB的核心数据结构被称为日志结构合并树（Log Structured Merge Tree，LSM Tree），LSM树是一种专为写密集型工作负载设计的数据结构。

LSM树主要分为四个部分：

1. MemTable：在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据（这里key有序主要是为了后面方便合并数据，相同的key如果有序则可以使用归并的思想，加快合并效率）。
2. Immutable MemTable：将MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。
3. WAL（Write-Ahead Log）：因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过预写式日志（Write-ahead logging，WAL）的方式来保证数据的可靠性。WAL是一个只允许追加（Append Only）的文件，包含一组更改记录序列。每个记录包含键值对、记录类型（Put / Merge / Delete）和校验和（checksum）。与MemTable不同，在WAL中，记录不按key有序，而是按照请求到来的顺序被追加到WAL中。
4. SSTable（Sorted String Table）：一种拥有持久化、有序且不可变的键值存储结构，它的key和value都是任意的字节数组，并且提供了按指定key查找和指定范围的key区间迭代遍历的功能。

LSM 数据写入流程

LSM写入流程如下：

1. 首先记录到WAL log文件中；
2. 接着记录到MemTable中；
3. 当MemTable达到一定阈值后关闭该MemTable，变成ImmuMemTable(只读)；然后打开新的MemTable处理写操作，将ImmuMemTable写入到磁盘中，形成一个SSTable。

这种设计虽然大大提高了写性能，但同时也会带来一些问题：

1. 空间放大（Space Amplification）：占用的硬盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个key，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的（例如对同一个key的add、del、update操作只需要关注最后的结果）。
2. 读放大（Read Amplification）：实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在，不存在继续从SSTable中寻找。

LSM 数据读取流程

LSM读取流程如下：

1. 首先从MemTable中尝试读取，如果读取到数据，则停止读取过程，立即返回。
2. 如果MemTable中数据未读到，则尝试从ImmuMemTable读取数据，如果读取到，则停止读取，返回给用户。
3. 如果ImmuMemTable中数据未读到，则尝试从SSTables中读取数据（此处省去繁琐的具体SSTable中读取数据的逻辑，因为涉及到数据时按照大小分级组织还是按照分层关系组织），最后将读取的数据返回给用户。

在极端情况下，如果我们要搜索的数据根本就不存在。那这种情况下，我们需要读取完所有的数据才能返回给上层用户，搜索的数据不存在。当数据量较大时，这种查找过程效率极低。往往在工程上实现时，会采用布隆过滤器来加速读取，查找每个SSTable时，首先会根据布隆过滤器来拦截一次，如果布隆过滤器检测当前的查找的数据不存在，那么查找的数据就一定不存在当前的SSTable中，加快读取效率。不过布隆过滤器存在误判情况，所以在实际使用时，需要合理的设置布隆过滤器的几个关键参数。

合并机制

LSM树引入了合并（Compaction）机制，可以降低空间放大和读放大，但代价是更高的写放大（Write Amplification），即实际写入操作数量大于真正的写入操作数量。在合并操作中，每个被合并的SSTable中的数据都需要被读取出来，然后写入到新的SSTable中。因此，一个数据项可能会被多次写入到硬盘中。

写放大会增加硬盘I/O，尤其是在业务高峰期，从而降低系统的性能。因此LSM树提供了不同合并策略在空间、读和写放大之间进行权衡，这种策略主要包括：

• 分层合并(Tiered Compaction)：按照key的范围分裂成多个小文件SSTable，旧数据被移动到单独的层级
• 大小层分级合并(Leveled Compaction)：较新的和较小的SSTable文件被连续合并到较旧的、较大的文件SSTable中

总结

从上面的读写流程，LSM的核心设计思想（要解决的问题）如下：

1. 首先LSM是为了解决大量写的场景，写操作无非是add、update、delete，要想加快写的速度，选择了追加写（假设数据已经组织成了：[op, key, value]形式）。
2. 对于同一个key来说，我们只关心最终的value，中间的op过程是无效的，这种情况被称为空间放大，解决办法是进行合并压缩数据。
3. 合并压缩的过程中又引入了新的问题：（1）合并的过程中阻塞了写入和读取（2）每次合并需要读取整个文件，比较耗时。
4. 针对合并过程阻塞读写，解决方案是将原先单个文件存储转为采用多个小文件分段存储数据，这样的话每次当一个文件写入的数据达到一定条件后就关闭，不再修改，然后重新打开一个新文件进行写入数据不就好了。然后合并的时候对前面关闭的一些文件进行定期压缩。这样我们的第一个问题就得到解决了。压缩过程不会阻塞读写过程。具体的压缩逻辑大致如下：
   1. 依次按照文件关闭先后顺序倒序读取多个文件内容到内存
   2. 内存中保留最新的数据（越后写入的数据越新）即可
   3. 最后合并的数据写入到新文件中
5. 针对压缩比较慢的问题，利用多路归并的思想，保证每个文件的写入是有序的。这里可以选择一定的数据结构来在内存中排序如：AVL，红黑树，跳表等
6. 数据在内存中如果断电了，数据就丢失了，为了保证数据的持久性，又引入了WAL，所有操作先写redo log，挂掉重启从redo log中恢复
7. 合并压缩的策略选择

可以看到每个问题LSM tree都抽象了一些模块来解决：

1. 内存数据(MemTable)：内存数据主要缓存我们写入进来的数据，因为是内存数据所以称为MemTable。一般选择跳表或者红黑树等有序数据结构实现。
2. 磁盘数据文件(SSTable)：磁盘数据文件，保存我们所有的用户数据，数据有序存储，所以又称为SSTable(Sorted String Table)。
3. 磁盘日志文件(WAL log)：预写日志文件，主要用来程序异常退出重启时恢复数据，保证数据可靠性，WAL全程write ahead log。