LSM 日志合并树¶
1 LSM 结构¶
LSM 是一种分层结构，L0-N 层存在硬盘中，每一层（除了 L0 层）都是排好序的数据。 - WAL：在更新 Memtable 前会先写 WAL 日志，只有 flush 到 L0 层后，日志文件才被删除。 - Memtable 和 Immutable Memtable 在内存中，当 Memtable 数据达到阈值时，状态改变，成为 Immutable Memtable。 - L0 层 是特殊的 SSTable 层，Immutable Memtable 数据直接以 append 方式写入，这导致 L0 层可能存在多个相同的 key，且只能保证这一层中单个 SSTable 内数据有序。 - L1-n 每一层也是由多个 SSTable 组成，但 每一个 SSTable 都是有序的。
1.1 MemTable¶
MemTable 是在内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据，LSM 树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如 Hbase 使跳跃表来保证内存中 key 的有序。
因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过 WAL(Write-ahead logging，预写式日志) 的方式来保证数据的可靠性。
当 Memtable 数据写入到了 L1 层 SSTable 中后先前的 WAL 日志就可以删除掉。
1.2 Immutable MemTable¶
当 MemTable 达到一定大小后，会转化成 Immutable MemTable。Immutable MemTable 是将 MemTable 转变为 SSTable 的一种中间状态。写操作由新的 MemTable 处理，在转存过程中不阻塞数据更新操作。
1.3 SSTable (Sorted String Table)¶
有序键值对集合，是 LSM 树组在磁盘中的数据结构。为了加快 SSTable 的读取，可以通过建立 key 的索引以及布隆过滤器来加快 key 的查找。
2 更新¶
LSM 树会将所有的数据 插入、修改、删除 等操作 只更新 Memtable 和 WAL，不会涉及到硬盘操作，只有当 Memtable 达到一定的数据量后，转换为 Immutable Memtable ，再追加写入到 L0 层 SSTable 中。这与 B+ 树不同，B+ 树数据的更新会直接在原数据所在处修改对应的值，但是 LSM 树的数据更新是日志式的，当一条数据更新是直接 append 一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将 Immutable MemTable flush 到持久化存储即可，而不用去修改之前的 SSTable 中的 key，保证了顺序写。
因此当 MemTable 达到一定大小 flush 到持久化存储变成 SSTable 后，在 L0 层中 SSTable 中可能存在相同的 Key 或者在 L1-n 层中可能存在相同 Key 的记录，当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能，但同时也会带来一些问题：
1）冗余存储，对于某个 key，实际上除了最新的那条记录外，其他的记录都是冗余无用的，但是仍然占用了存储空间。因此需要进行 Compact 操作 (合并多个 SSTable) 来清除冗余的记录。 2）读取时需要从最新的倒着查询，直到找到某个 key 的记录。最坏情况需要查询完所有的 SSTable，这里可以通过前面提到的索引/布隆过滤器来优化查找速度。
3 删除¶
删除引入了一个 墓碑 概念；删除操作直接往 Memtable 插入（不存在）或更新（存在）墓碑标记（即删除标记）。当合并发生时，才能去清理那一层 SSTable 中的被标记成墓碑的数据。
4 查询¶
因为 LSM 树中一个 key 可以在多个 Ln 层存在，但最新的数据永远在上一层，所以当查询时需要在每一层查找，找到了就返回，极端情况可能在最底层才能查到数据。如果查询的数据不存在，就需要查询所有 Ln 层，并且最终返回查询无数据的结果，可以通过 布隆过滤器 + 建立稀疏索引 来优化查询 操作。从这可以看出，LSM 树查询效率不高。
5 合并¶
- LSM 树合并操作可以 清除那些重复的数据和被标记成墓碑的数据，从而释放了部分放大的空间。
- 通常 L0 层触发合并时，会选择 L0 层所有数据进行合并（因为 L0 层是无序的）
- 合并操作在 L0-n 层上进行，不同层可以并发合并，合并时选择 Li-1 层部分 SSTable 和 Li 层中有交集的部分进行合并。
6 放大问题¶
- 读放大：读取数据时实际读取的数据量大于真正的数据量。例如在 LSM 树中需要先在 MemTable 查看当前 key 是否存在，不存在继续从 SSTable 中寻找。
- 写放大：写入数据时实际写入的数据量大于真正的数据量。例如在 LSM 树中写入时可能触发 Compact 操作，导致实际写入的数据量远大于该 key 的数据量。
- 空间放大：数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个 key 来说，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的。
7 时间复杂度¶
LSMTree 的增、删、改、查四种基本操作的时间复杂度分析如下所示：
| 操作 | 平均代价 | 最坏情况代价 |
|---|---|---|
| 插入 | 1 | 1 |
| 删除 | 1 | 1 |
| 修改 | 1 | 1 |
| 查找 | lgN | lgN |