原副标题：TiDB下层储存内部结构LSM树基本原理如是说
译者 | 天猫云开发人员-天猫仓储 张家存
随著信息量的减小，现代亲密关系型资料库愈来愈无法满足用户对海量储存的市场需求。对分布式系统亲密关系型资料库，他们介绍其下层储存内部结构是十分关键的。责任编辑将如是说下分布式系统亲密关系型资料库 TiDB 所选用的下层储存内部结构 LSM 树的基本原理。
1 LSM 树如是说
LSM 树（Log-Structured-Merge-Tree) 笔记内部结构分拆树由 Patrick O’Neil 等人在学术论文《The Log-Structured Merge Tree》(https://www.cs.umb.edu/~poneil/lsmtree.pdf) 中明确提出，它事实上并非一棵，而要 2 个或是数个相同层级的树或类似于树的内部结构的子集。
LSM 树的核心理念特征是借助次序写来提升写操控性，付出是会稍稍减少读操控性（读弱化），载入量减小（写弱化）和占用内部空间减小（内部空间弱化）。
LSM 树主要就被用作 NoSql 资料库中，如 HBase、RocksDB、LevelDB 等，著名的分布式系统亲密关系型资料库 TiDB 的 kv 储存发动机 TiKV 下层储存是用的下面所言的 RocksDB，也是用的 LSM 树。
2 LSM 树演算法约莫路子
LSM 树由三个或数个抽象化的内部结构共同组成。
这四节他们以三个抽象化的内部结构形成的单纯的单层 LSM 树总括，来单纯说下 LSM 树约莫路子，让我们对 LSM 树同时实现有位总体的重新认识。
原学术论文中的图
2.1 数据内部结构
单层 LSM 树有一个较小的层，该层完全驻留在内存中，作为 C0 树（或 C0 层），以及驻留在磁盘上的较大层，称为 C1 树。
尽管 C1 层驻留在磁盘上，但 C1 中经常引用的节点将保留在内存缓冲区中，因此 C1 经常引用的节点也可以被视为内存驻留节点。
2.2 载入
载入时，首先将记录行载入次序笔记文件 WAL 中，然后再将此记录行的索引项插入到内存驻留的 C0 树中，然后通过异步任务及时迁移到磁盘上的 C1 树中。
2.3 读取
任何搜索索引项将首先在 C0 中查找，在 C0 中未找到，然后再在 C1 中查找。
如果存在崩溃恢复，还需要读取恢复崩溃前未从磁盘中取出的索引项。
2.4 Compact 过程
将索引条目插入驻留在内存中的 C0 树的操作没有 I/O 成本，然而，与磁盘相比，容纳 C0 组件的内存容量成本较高，这对其大小施加了限制。达到一定大小后，他们就需要将数据迁移到下一层。
他们需要一种有效的方法将记录项迁移到驻留在成本较低的磁盘介质上的 C1 树中。为了同时实现这一点，当插入达到或接近每一层分配的最大值的阈值大小，将进行一个滚动分拆（Compact）过程，用作从 C0 树中删除一些连续的记录项，并将其分拆到 C1 中。
Compact 目前有两种策略，size-tiered 策略，leveled 策略，他们将在下面的内容里详细如是说这两种策略。
2.5 崩溃恢复
在 C0 树中的项迁移到驻留在磁盘上的 C1 树之前，存在一定的延迟（延迟），为了保证机器崩溃后 C0 树中的数据不丢失，在生成每个新的历史记录行时，首先将用作恢复此插入的笔记记录载入以常规方式创建的次序笔记文件 WAL 中，然后再载入 C0 中。
3 LSM 树的共同组成
LSM 树有三个关键共同组成部分，MemTable，Immutable MemTable，SSTable (Sorted String Table)，如下图。
这张经典图片来自 Flink PMC 的 Stefan Richter 在 Flink Forward 2018 演讲的 PPT
这几个共同组成部分分别对应 LSM 树的相同层级，相同层级间数据转移见下图。这节是如是说 LSM 树抽象的相同层的抽象化数据内部结构的某个具体同时实现方式。
3.1 MemTable
MemTable 是在内存中的数据内部结构，用作保存最近更新的数据，会按照 Key 有序地组织这些数据。LSM 树对具体如何组织有序地组织数据并没有明确的数据内部结构定义，例如你可以任意选择红黑树、跳表等数据内部结构来保证内存中 key 的有序。
3.2 Immutable MemTable
为了使内存数据持久化到磁盘时不阻塞数据的更新操作，在 MemTable 变为 SSTable 中间加了一个 Immutable MemTable。
当 MemTable 达到一定大小后，会转化成 Immutable MemTable，并加入到 Immutable MemTable 队列尾部，然后会有任务从 Immutable MemTable 队列头部取出 Immutable MemTable 并持久化磁盘里。
3.3 SSTable(Sorted String Table)
有序键值对子集，是 LSM 树组在磁盘中的数据内部结构。
其文件内部结构基本路子是先划分为数据块 (类似于于 mysql 中的页)，然后再为数据块建立索引，索引项放在文件末尾，并用布隆过滤器优化查找。
4 LSM 树的 Compact 策略
当某层信息量大小达到他们预设的阈值后，他们就会通过 Compact 策略将其转化到下一层。
在如是说 Compact 策略前，他们先想想如果让他们自己设计 Compact 策略，对以下几个问题，他们该如何选择。
对某一层的树，他们用单个文件还是数个文件进行同时实现？ 如果是数个文件，那同一层 SSTable 的 key 范围是有序还是重合？有序方便读，重合方便写。 每层 SSTable 的大小以及相同层之间文件大小是否相等。 每层 SSTable 的数量。如果同一层 key 范围是重合的，则数量越多，读的效率越低。相同的选择会造成相同的读写策略，基于以上 3 个问题，又带来了 3 个概念：
读弱化：读取数据时实际读取的信息量大于真正的信息量。例如在 LSM 树中可能需要在所有层级的树中查看当前 key 是否存在。 写弱化：载入数据时实际载入的信息量大于真正的信息量。例如在 LSM 树中载入时可能触发 Compact 操作，导致实际载入的信息量远大于数据的大小。 内部空间弱化：数据实际占用的磁盘内部空间比数据的真正大小更多。LSM 树中同一 key 在相同层级里或是同一层级的相同 SSTable 里可能会重复。相同的策略实际是围绕这三个概念之间做出权衡和取舍，他们主要就如是说两种基本策略：size-tiered 策略和 leveled 策略，这三个策略对以上 3 个概念做了相同的取舍。
4.1 size-tiered 策略
4.1.1 演算法
size-tiered 策略每层 SSTable 的大小相近。 当每一层 SSTable 的数量达到 N 后，则触发 Compact 操作分拆这些 SSTable，并将分拆后的结果载入到一个更大的 SStable。 新的更大的 SStable 将直接放到下一层 SStable 的队尾。所以同一层相同 SStable key 范围重合，查找时要从后向前扫描，且最坏情况下可能会扫描同一层所有 SStable ，这减小了读弱化的问题 (之所以说减小，是因为 LSM 树相同层之间也有读弱化问题)。4.1.2 总结由此可以看出 size-tiered 策略几个特征：
每层 SSTable 的数量相近。 当层数达到一定数量时，最下层的单个 SSTable 的大小会变得十分大。 不但相同层之间，哪怕同一层相同 SSTable 之间，key 也可能会出现重复。内部空间弱化比较严重。只有当该层的 SSTable 执行 compact 操作才会消除这些 key 的冗余记录。 读操作时，需要同时读取同一层所有 SSTable ，读放大严重。4.2 leveled 策略
4.2.1 演算法
leveled 策略和 size-tiered 策略相同的是，它限制 SSTable 文件的大小，每一层相同 SSTable 文件 key 范围不重叠且后面的最小 key 大于前一个文件的最大 key 当每一层 SSTable 的总大小达到阈值 N 后，则触发 Compact 操作。 首先会随机选择一个 SSTable 分拆到下层，由于下一层 key 是全局有序的，这就要求 leveled 策略 Compact 操作时需要当前 SSTable 和下一层里和当前 SSTable key 存在范围重叠的所有 SSTable 进行合并。最坏情况下可能下一层所有 SSTable 都参与分拆，这就减小了写弱化问题 (之所以说减小，是因为 LSM 树相同层之间 Compact 也有写弱化问题)。4.2.2 总结由此可以看出 leveled 策略几个特征：
不会出现十分大的 SSTable 文件。 每一层相同 SSTable 文件 key 范围不重叠。相对 size-tiered 策略读弱化更小。 Compact 操作时，需要同时和下一层 SSTable 一起分拆，写弱化严重。5 LSM 树的插入、修改、删除从 LSM 树的名字，Log-Structured-Merge-Tree 笔记内部结构分拆树中他们约莫就能知道 LSM 树的插入、修改、删除的方法了 —— 次序追加而非修改 (对磁盘操作而言)。
LSM 树的插入、修改、删除都是在 L0 层的树里插入、修改、删除一条记录，并记录记录项的时间戳，由于只需要取最新的内容即可，所以不需要操作后面层级的树。 历史的插入、修改、删除的记录会在每次 Compact 操作时被后面的记录覆盖。6 LSM 树的查找由于后面的操作会覆盖前面的操作，所以查找只需从 L0 层往下查，直到查到某个 key 的记录就可以了，之前的记录不需要再查了。 对 size-tiered 策略，同一层 SSTable 需要从后向前遍历，直到找到符合的索引项。 在查找过程中也会使用其他一些手段进行优化，例如增加缓存、布隆过滤器等。7 LSM 树和 B+ 树的比较不考虑写笔记等操作，插入、修改、删除一条记录 B+ 树需要先找到数据位置，可能需要多次磁盘 IO；LSM 树不需要磁盘 IO，单次插入耗时短，所以其载入的最大吞吐量是高于 B+ 树的。 LSM 树后面的 Compact 操作也会操作这条数据几次，总的载入量是大于 B+ 树的，但可以通过将 Compact 操作放到业务低峰时来减少这个劣势的影响。 查找时， LSM 树需要遍历所有层级的树，查找效率上要低于 B+ 树，但 LSM 树载入时节省的磁盘资源占用，可以一定程度上弥补读效率上的差距。8 总结LSM 树特征：次序载入、Compact 操作、读、写和内部空间弱化。
LSM 树适用场景：对写操作吞吐量要求很高、读操作吞吐量要就较高的场景，目前主要就在 NoSql 资料库中用的比较多。
END
聊聊企业开源的下层逻辑
这里有最新开源资讯、软件更新、技术干货等内容
点这里 ↓↓↓ 记得 关注✔ 标星⭐ 哦~
