尽管 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 策略，对于以下几个问题，我们该如何选择。

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

不同的策略实际就是围绕这三个概念之间做出权衡和取舍，我们主要介绍两种基本策略：size-tiered 策略和 leveled 策略，这两个策略对于以上 3 个概念做了不同的取舍。

4.1 size-tiered 策略

4.1.1 算法

由此可以看出 size-tiered 策略几个特点：

4.2.1 算法

由此可以看出 leveled 策略几个特点：

从 LSM 树的名字，Log-Structured-Merge-Tree 日志结构合并树中我们大概就能知道 LSM 树的插入、修改、删除的方法了 —— 顺序追加而非修改 (对磁盘操作而言)。

LSM 树特点：顺序写入、Compact 操作、读、写和空间放大。

LSM 树适用场景：对于写操作吞吐量要求很高、读操作吞吐量要就较高的场景，目前主要在 NoSql 数据库中用的比较多。

END

聊聊企业开源的底层逻辑

这里有最新开源资讯、软件更新、技术干货等内容

点这里 ↓↓↓ 记得 关注✔ 标星⭐ 哦~返回搜狐，查看更多