六虎

TiDB 底层存储结构 LSM 树原理介绍

作者：

写代码像蔡徐抻

在

作者：京东物流 刘家存

随着数据量的增大，传统联系型数据库越来越不能满意关于海量数据存储的需求。关于分布式联系型数据库，咱们了解其底层存储结构是非常重要的。本文将介绍下分布式联系型数据库 TiDB 所选用的底层存储结构 LSM 树的原理。

1 LSM 树介绍

LSM 树（Log-Structured-Merge-Tree) 日志结构兼并树由 Patrick O’Neil 等人在论文《The Log-Structured Merge Tree》(www.cs.umb.edu/~poneil/lsm…

LSM 树的中心特色是利用次序写来提高写性能，代价就是会略微下降读性能（读扩大），写入量增大（写扩大）和占用空间增大（空间扩大）。

LSM 树主要被用于 NoSql 数据库中，如 HBase、RocksDB、LevelDB 等，闻名的分布式联系型数据库 TiDB 的 kv 存储引擎 TiKV 底层存储就是用的上面所说的 RocksDB，也就是用的 LSM 树。

2 LSM 树算法大概思路

LSM 树由两个或多个树状的结构组成。
这一节咱们以两个树状的结构构成的简略的双层 LSM 树举例，来简略说下 LSM 树大概思路，让咱们对 LSM 树完成有个整体的知道。

TiDB 底层存储结构 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)，如下图。

TiDB 底层存储结构 LSM 树原理介绍

这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT

这几个组成部分别离对应 LSM 树的不同层次，不同层级间数据转移见下图。这节就是介绍 LSM 树抽象的不同层的树状数据结构的某个详细完成方法。

TiDB 底层存储结构 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 战略

TiDB 底层存储结构 LSM 树原理介绍

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 战略

TiDB 底层存储结构 LSM 树原理介绍

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 数据库顶用的比较多。

更多文章