关于tidb: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 策略，对于以下几个问题，咱们该如何抉择。

1. 对于某一层的树，咱们用单个文件还是多个文件进行实现？
2. 如果是多个文件，那同一层 SSTable 的 key 范畴是有序还是重合？有序不便读，重合不便写。
3. 每层 SSTable 的大小以及不同层之间文件大小是否相等。
4. 每层 SSTable 的数量。如果同一层 key 范畴是重合的，则数量越多，读的效率越低。

不同的抉择会造成不同的读写策略，基于以上 3 个问题，又带来了 3 个概念：

1. 读放大：读取数据时理论读取的数据量大于真正的数据量。例如在 LSM 树中可能须要在所有档次的树中查看以后 key 是否存在。
2. 写放大：写入数据时理论写入的数据量大于真正的数据量。例如在 LSM 树中写入时可能触发 Compact 操作，导致理论写入的数据量远大于数据的大小。
3. 空间放大：数据理论占用的磁盘空间比数据的真正大小更多。LSM 树中同一 key 在不同档次里或者同一档次的不同 SSTable 里可能会反复。

不同的策略理论就是围绕这三个概念之间做出衡量和取舍，咱们次要介绍两种根本策略：size-tiered 策略和 leveled 策略，这两个策略对于以上 3 个概念做了不同的取舍。

[]()4.1 size-tiered 策略

[]()4.1.1 算法

1. size-tiered 策略每层 SSTable 的大小相近。
2. 当每一层 SSTable 的数量达到 N 后，则触发 Compact 操作合并这些 SSTable，并将合并后的后果写入到一个更大的 SStable。
3. 新的更大的 SStable 将间接放到下一层 SStable 的队尾。所以同一层不同 SStable key 范畴重合，查找时要从后向前扫描，且最坏状况下可能会扫描同一层所有 SStable，这增大了读放大的问题 (之所以说增大，是因为 LSM 树不同层之间也有读放大问题)。

[]()4.1.2 总结

由此能够看出 size-tiered 策略几个特点：

1. 每层 SSTable 的数量相近。
2. 当层数达到肯定数量时，最底层的单个 SSTable 的大小会变得十分大。
3. 岂但不同层之间，哪怕同一层不同 SSTable 之间，key 也可能会呈现反复。空间放大比较严重。只有当该层的 SSTable 执行 compact 操作才会打消这些 key 的冗余记录。
4. 读操作时，须要同时读取同一层所有 SSTable，读放大重大。

4.2 leveled 策略

4.2.1 算法

1. leveled 策略和 size-tiered 策略不同的是，它限度 SSTable 文件的大小，每一层不同 SSTable 文件 key 范畴不重叠且前面的最小 key 大于前一个文件的最大 key
2. 当每一层 SSTable 的总大小达到阈值 N 后，则触发 Compact 操作。
3. 首先会随机抉择一个 SSTable 合并到上层，因为下一层 key 是全局有序的，这就要求 leveled 策略 Compact 操作时须要以后 SSTable 和下一层里和以后 SSTable key 存在范畴重叠的所有 SSTable 进行合并。最坏状况下可能下一层所有 SSTable 都参加合并，这就增大了写放大问题 (之所以说增大，是因为 LSM 树不同层之间 Compact 也有写放大问题)。

4.2.2 总结

由此能够看出 leveled 策略几个特点：

1. 不会呈现十分大的 SSTable 文件。
2. 每一层不同 SSTable 文件 key 范畴不重叠。绝对于 size-tiered 策略读放大更小。
3. Compact 操作时，须要同时和下一层 SSTable 一起合并，写放大重大。

5 LSM 树的插入、批改、删除

从 LSM 树的名字，Log-Structured-Merge-Tree 日志构造合并树中咱们大略就能晓得 LSM 树的插入、批改、删除的办法了——程序追加而非批改 (对磁盘操作而言)。

1. LSM 树的插入、批改、删除都是在 L0 层的树里插入、批改、删除一条记录，并记录记录项的工夫戳，因为只须要取最新的内容即可，所以不须要操作前面档次的树。
2. 历史的插入、批改、删除的记录会在每次 Compact 操作时被前面的记录笼罩。

6 LSM 树的查找

1. 因为前面的操作会笼罩后面的操作，所以查找只需从 L0 层往下查，直到查到某个 key 的记录就能够了，之前的记录不须要再查了。
2. 对于 size-tiered 策略，同一层 SSTable 须要从后向前遍历，直到找到合乎的索引项。
3. 在查找过程中也会应用其余一些伎俩进行优化，例如减少缓存、布隆过滤器等。

7 LSM 树和 B+ 树的比拟

1. 不思考写日志等操作，插入、批改、删除一条记录 B+ 树须要先找到数据地位，可能须要屡次磁盘 IO；LSM 树不须要磁盘 IO，单次插入耗时短，所以其写入的最大吞吐量是高于 B+ 树的。
2. LSM 树前面的 Compact 操作也会操作这条数据几次，总的写入量是大于 B+ 树的，但能够通过将 Compact 操作放到业务低峰时来升高这个劣势的影响。
3. 查找时，LSM 树须要遍历所有档次的树，查找效率上要低于 B+ 树，但 LSM 树写入时节俭的磁盘资源占用，能够肯定水平上补救读效率上的差距。

[]()8 总结

LSM 树特点：程序写入、Compact 操作、读、写和空间放大。
LSM 树实用场景：对于写操作吞吐量要求很高、读操作吞吐量要就较高的场景，目前次要在 NoSql 数据库中用的比拟多。