![](https://csdnimg.cn/release/download_crawler_static/87210283/bg4.jpg)
写操 作. 数据首先写入磁盘, 作为数据库恢复的 Redo-Log; 然后写入内
存中的 MemTable, MemTable 由跳表实现, 维护数据的有 序性. 数 据的写入
到 此 结 束 . 当 MemTable 写 满 后 , 转 变 成 不 可 写 入 只 可 读 取 的 MemTable
(Immutable MemTable); 再 将 Immutable MemTable 写入 磁 盘 中 的 L
0
层 , 格
式变为 SSTable, 这一过程称为 Minor Compaction; 当 L
0
层数据达到阈值时,
与 L
1
层进行合并, 这一过程称为 Major Compaction; 磁盘中的每一层数据到
达阈值后均向下进行 Major Compaction.
在 LSM-tree 架构中, 存在 3 种类型的写停顿. 插入停顿: 如果 MemTable
在 Immutable MemTable 刷盘完成前被填满, 所有写入 LSM-tree 的操作都会
停止. 刷盘停顿: 如果 L
0
层有许多的 SSTable 并且达到了大小限制, 则会阻止
刷盘. 合并停顿: 太多的等待执行合并的任务阻塞了前台的操作, 导致写停顿.
L
0
层的每个 SSTable 文件内部的键值对是有序的, 但文件之间是无序的甚
至会有交集 ; L
1
层及以上每 一 层 的 数 据 都是全局有序的, 并且保 证 每 一 层 的
SSTable 文件之间是没有交集的.
执行一次 Major Compaction, 首先确定 L
i
层参加 Compaction 的 SSTable
(被称为 Victim SSTable)和 L
i+1
层中与 Victim SSTable 范围有交集的 SSTable
(被称 为 Overlap SSTable)作为 Compaction 的初 始 输 入. 落 入 这个扩 大 后 的
范围的 L
i
层的其他 SSTable 被反向选择, 从而确定了全部输入. 将之前选择的
所有 SSTable 使用外部归并排序的方式写回到 L
i+1
层. 由于 L
0
层是未排序的,
并且 L
0
层中的每一个 SSTable 的 key 范围都很大, 所以几乎会选择 L
0
层和 L
1
层中的所有 SSTable 来进行排序, 导致了全量的写放大.
读 操 作 . 读 数 据 首 先 查 询 MemTable, 然 后 查 询 Immutable MemTable,
最后是 L
0
层到 L
n
层中的 SSTable. 由于 L
0
层没有维护全局有序性, 在 L
0
层可
能会查询多个文件.
1.3 LSM-tree 研究现状
现有的基于 LSM-tree 架构的提升包括: 减少写放大、提高内存管理水平、
支持自动优化、用混合存储优化 LSM-tree 架构等. 在这些工作中, 随机写性
能是一个被共同关注的点, 因为受 Compaction 影响, 随机写会导致写停顿和
写放大. 下面讨论工作中最相关的 3 类: 减少写放大, 处理写停顿和使用 NVM.