学习 RocksDB 知道源码那么写的，但是也要从顶端看到为什么要有这些东西，组里的一位很牛的上古程序员在很久以前给我们科普过 Bedtime Stories for children (Storage Engines)，这里主要对大佬的科普内容整理主要便于自己温习。

存储引擎

存储引擎是管理数据集的系统，最简单的存储引擎对外暴露 write read scan 即可。本质上 read/write 就是描述 keys 和 values 的单映射关系，拍脑袋想到的就是用 hashmap，这样读写时间基本是 O(1)。但考虑到空间成本和 scan 的需要，也可以用一个有序数组，虽然比 hashmap 的性能差一点，但是有序性和局部性都更好，这样通过二分读取性能是 O(lgn)，而写入性能就很一般。

局部性：当 OS 执行一次操作，会带来一些 overhead，而在大部分设计中，连续执行相同操作 or 访问相邻内容时，有一些机制或优化能够平摊单次操作的开销，以提升性能。这就是为什么需要考虑空间局部性的原因。对于 read/scan 当然局部性越高越好，但局部性过高，比如有序数组，对于 write 也是灾难。插入一个 key 需要搬运很多数据，降低了写入性能。

所以有序数组这个结构并不算多好，那如果考虑写入可以使用二叉平衡树，这样 write 性能就不错 O(lgn)，read 性能时间理论上是 O(lgn)，但因为损失了局部性带来的隐含新能优化，所以也不算多好，scan 就是 O(nlgn)，同样损失了局部性优化。

key value 分离：value 较小的时候会影响 scan 性能，但是大 value 性能不错，减少了写放大，因为修改数据无需移动。

基于这个思想我们想到了 B+ Tree，可以实现 1.有序性 2.部分局部性，通过配置 leaf node 实现插入和读取的平衡。

底层存储层的特点：开销一定比内存大，哪怕是 SSD 连续写入也快于随机写入，对数据局部性要求高，最好的程序设计让 IOBW 打到瓶颈而不是很高的 IOPS 缺只有很少的 IOBW。所以不能用同构镜像来让内存和盘的数据结构一样。

根据两种存储层的特点区别，使用 WAL 作为异构镜像解决方案，内存随便使用什么结构都可以，磁盘上用局部性好的结构。这样写的时候同时写内存结构和 WAL，启动的时候从 WAL 里恢复数据到内存中。WAL 里一般可以用 Record 作为单位，每次写完一条记录做一次 fsync 确保 flush。

但是这样 WAL 会记录很多无效操作，比如多次修改过一个 value，肯定希望最终只存一份，这就引入了 GC。简单实现下的 WAL 有一个标记已经失效的指针，比如 B+ tree 里每个叶子结点有一个小 WAL，最终需要刷到一个完整的 WAL 里，WAL 记录里各个值的修改结果，定期的 GC 可以帮助回收空间。

但是这个 WAL + B+ Tree 的实现下有一个问题，假设每个叶子结点都的 WAL 我们成为脏页，可能一个脏页写满了数据，另一个脏页远没到触发 compact 到统一 WAL 的阈值，这个时候强行 compact 就会引发写放大。

到这里就实现了一个简陋的 B+Tree 存储引擎了，底层文件使用多个 WAL 文件：1.攒批脏 leaf WAL 2.compaction 获得空间，但引起了多余的写放大

B+Tree 引擎

读性能：定位需要 lgn 性能较快，leaf node 的缓存如果存在就可以直接读，不然要从磁盘加载，所以小范围 scan 性能较好，大范围因为局部性肯定受影响。

读缓存：能否命中缓存对读至关重要，假设缓存算法是 LRU，而用户全 key 随机模式，命中率就很低了。因此如果可以设计接口以提供一定的模式匹配应该是重要的优化手段。而且 update 和 delete 的不同语义也会给写带来一定的读，从而击穿缓存。

写性能：定位需要写入的叶子节点同样是 lgn，append 到 WAL 文件，顺序 IO 速度也能得到保证，更新到叶节点之前有概率先加载到内存 leaf node，另外写到叶子结点 innodb 有 double write buffer 解决写部分宕机的问题。

写放大：当趋于纯随机写的时候，每个叶节点的修改数据量都较小，而因为多个叶子节点同时访问修改，导致 compact 变的频繁，假设一个叶子节点存 4MB 数据，但是只修改了 4KB 的数据就要 compact 这里就会带来写放大问题，而且原数据量大小也会影响到写放大。只有在攒批的 key 范围较窄，缩减到部分叶子的 ranges 时，才能达到优秀的 batch 效果，即单热点。

B+Tree 的另一个问题是散 IO、小 IO 问题。

当 meta 数据修改频繁，即 compact 频繁，那么锁竞争很激烈，导致 CPU 上下文切换频繁，同样降低性能。

问题总结：1.写放大 2.IO小而散 3.meta数据修改频繁

LSM Tree 引擎

前面讨论的都是 B+ Tree，现在换一个口味，学习 LSM Tree。这种类型是多个范围重叠的一维线性数组，而之前 B+ Tree 每一个脏页之间的 range 是独立不重叠的。

局部性：数组（文件）个数决定，设想 range(2, 15) 的数据只分布在两个文件和分布在多个文件肯定是不一样的局部性。

key 重排：因为多个文件会重叠 key range，因此需要做多路归并，对于相同的 key 选择最后写入的 key。

Read 性能：和文件数量有关，文件数量多，有可能查到最后一个文件，在每个文件中的查询依赖二分搜索。但是 LSM 结构会带来读放大问题，毕竟 key range 重叠。

Bloom Filter：因为文件生成后不会改变，可以给每个文件生成对应的 bloom filter，因为自身特性，只会假阳，因此过滤器有不代表真的存在，但是没有就可以跳过这个文件了，这个是主要的优化读放大的手段。

Scan 性能：需要在每个数组找到这个 range，然后进行多路归并，因此复杂度也和文件数量 K 相关。

查询和 B+ Tree 的区别：因为 B+ Tree 叶节点小，可以整叶读写，直接全读进内存二分即可，但是 LSM 里一个文件比较大，一般按照 block 读取，而且直接在磁盘上二分更不可能，这带来了太多的单点读 IO。

block 满足了局部性的要求，又控制了读放大，是磁盘读取的基本单位，当然也可以作为压缩的基本单位。其中 block cache 可以用 LRU 实现。

compaction：减少数组消除重复的 key 有助于增加读性能，每次第一次写入的数组文件是固定大小的，取决于 writebuffer，这个文件称为 L0 文件。而从小往大 compact 有助于快速减少文件数量。当然 compaction 也有写放大，而且放大比为 3 时，相当于（1 write + 2 read + 2 write）:1=5倍 的 IO overhead（假设被 compaction 的文件不在内存里）。

不同的 compaction 策略会生成不同的形状图：

1. 等大逢 T 进 1（universal compaction），假设 T = 2，当有 2 个同等大小（level）的文件，就合并为下一个 level。

   代价估算：数组个数需要折中，越多写放大越小，但是读越差，反之同理。

   优化：执行 compact 顺带执行更小层的文件，以减少写放大。

   目标：需要形状稳定，读取才能稳定

   解决：动态推算最大层的期望大小，再反推较小层；对 L0（文件小而多不稳定） 使用不同策略以维持主体形状稳定；L0 使用周期触发 compaction，即写入 K 个文件就触发一次。

2. Level compaction：提升 read 性能，因为会更积极地触发 compaction，而不是类似 size tiered 方案找到 size 相似的文件才开始 compact。基本原理是把大部分数据 merge 到一个不重叠的数组文件中，利用逐层攒批加入并行优化把写放大降低到可以接受的程度。

对比 B+ Tree：B+ 的问题主要来源 leaf node 只覆盖一个小 range，因此攒批能力差，小 range 在全值域下占比很低，而 LSM 采用全 key range，在这 3 个问题上做的更好。

LSM Tree 解决：1. IO 小散 » 顺序大 IO 2.元数据修改频繁 » 元数据改动少 3.写放大 -> 较低（通过攒批大）

带来的问题：读放大（B+ tree < level compaction < universal compaction），多路合并可能出现 CPU bound 问题，周期性带来的 background IO 写带宽。

优化：

1. 工程优化，比如锁、内存等

2. SSD 的特点，因此局部性可以不用过于在意，比如 value 分离后带来的值分散存储问题

3. compaction 的平衡问题（稳定的形状）
4. 为特定数据模型应用特定的模型，比如时序数据库使用 append 写入等优化