1. 介绍
以 LevelDB 和 RocksDB 为代表的 LSM-tree key-value 存储，在生产环境中被广泛的应用。其优点：（1）通过将随机小写转变成顺序写，提高了写入的性能；（2）顺序的key-value存储，可以支持高效的 range scans。缺点也很明显，就是 I/O 放大：（1）read 放大（amplifications）： 坏情况从内存，到盘中 level 逐级 read，直到 read 到数据；（2）write 放大：反复的 Compaction；其中write放大的问题尤其显著，很多文献测试表明甚至可以到50X。由于历史原因，在顺序写和随机写相差 100X 甚至 1000X 的 HDD 时代，LSM-tree 的收益是明显的，反之在顺序写和随机写相差不大的 SDD 时代，尤其是 NVME SSD 和 Persistent Memory（3D-Xpoint技术）设备的出现，远远缩小了顺序写和随机写的差距（< 10X），所以大量研究开始思考对 LSM-tree 进行优化了。这里将向大家介绍fast 2019上一篇基于Persistent Memory的优化key-value存储，与前段时间知乎讨论的sqlite4基于LSM-tree的尝试不同[2]，作者通过B+-Tree作为索引，消除了LSM-Tree的多层结构，而且充分利用了Persisitent Memory空间、性能、字节选址的特性，实现了一种Single-Level Merge DB，大大优化read/write的性能，并且减少了write放大。
2. SLM-DB
2.1. Architecture
Single-Level Merge DB（SLM-DB）整体架构如下图，左边为Disk，存放sst files，和通常的LSM-tree实现不同，其只有1个level，那么自然这个level上的sst file之间的key range是有重叠的；右边为Persistent Memory，主要包含：
- memtable（mutable&immutable）：包含了mutable和immutable两种类型的memtable，都是Persistent Memory的数据结构，实现还是Skiplist，放在Persistent Memory相比Memory，可以不需要WAL，因为Persistent Memory本身就是就保证了持久性
- Global B+tree：记录了key的索引结构，索引了value所在的sst file和offset
下面首先看看基本的put/get/Scan流程：
Put
- key-value insert Persistent MemTable中（并不需要写WAL）
- 如果MemTable达到一定的大小，转换成Immutable MemTable
- 如果Immutable MemTable个数到达一定数量，那么flush到disk中，且将相应key的索引结构更新的Global B+-tree中
Get
- 从Persistent MemTable查
- 从Immutable MemTable查
- 从Global B+-Tree查
Scan（RangeQuery）
- 查询MemTable相应的range
- 产需Immutable MemTable相应的range
- 通过B+-Tree查询Disk上相应range的数据，B+-Tree的索引多range查询不是问题，但是因为从Disk中读数据会是问题，因为SLM-DB只有1个level，这个level上面的sst file的key-range是重叠的，那么意味着RangeQuery查询的数据坏情况会落在所有的sst files上面，Scan的放大会很严重，而且写入如果是随机的，那么大概率数据会散落在sst files上面，如下图RangeQuery(5, 12)：
从上面的基本流程不难看出，SLM-DB的write和read流程都非常的简单，（1）write没有WAL，直接落Persistent Memory就可以返回了；（2）单个key-vlaue的read坏也是从Global B+-tree的索引中就能定位数据，不会存在类似LevelDB/RocksDB的逐层read导致的放大很严重；（3）Scan性能会相对差一些，因为LevelDB/RocksDB除了level 0，其他level的sst file的key range是不相交的，所以Scan的时候read哪些sst file是非常明确和数量可控的。
2.2. Persistent MemTable
持久性MemTable是还是使用的SkipList，如下图，是一个典型的SkipList结构，上半部分为索引，底层为数据的索引，既然Persistent Memtable，那么首要需要解决的问题就是Insert原子性的问题，显然写WAL开销太大了，Persistent Memory具有字节寻址的能力，所以其一般都就有atomic 8-byte write的能力，可以利用这个特性实现原子的update，其步骤如下：
假定已知key（待插入的key）, value（待插入的value）, prevNode（待插入node的前项节点，例如下图中的3）
- 创建一个node，如下图，也就是node 4
- 将node 4的next指向下一个节点5
- 原子的修改preNode，也就是node 3的next指针指向node 4
其中第3步为关键，在Persistent Memory中，和Memory一样，指针也是8个字节，所以这一步的原子性，保证了整个node 4插入的原子性，不过需要注意insert仅仅保证了原子性，但是并不支持并发。
还需要额外说明的是Skiplist的索引部分修改不会有一致性保证，因为SkipList的索引部分可以在failure之后恢复
2.3. Compaction
Why Compaction ?
- 回收空间
- 提升range query的性能：因为只有一层，那么每层之间的key是由交集的，如果没有Compaction，那么range query需要查询遍历非常多的文件才行。上面在介绍SLM-DB的Scan操作已经分析过。
How to Compaction ?
SLM-DB使用的是Selective compaction，其基本的流程是：
- 根据一定的策略选择将一些sst files标记为candidate sst files
- 当candidate sst files的数量到达一定的阈值之后，会通过归并排序对这些sst file做合并，生成新的sst file，删除相应的candidate sst files
这里关键是选择的策略，论文中也介绍了几种选择策略，这里以Live-key ratio selection为例介绍，非常简单，所谓的Live-key，就是有效的key，SLM-DB会统计每个sst file的 live-key ratio，并且会设定一个threshold，一旦某个sst file的有效key ratio低于这个threshold，那么就会将其选入Candidate sst file。还有一些其他的选择策略，感兴趣的可以参考论文。
3. 总结
后根据实验结果，发现get/put的性能基本符合预期，会远好于LevelDB，Scan的性能稍差于LevelDB（如上图）；写放大从实验来看，也表现不错，不过这一点可能跟实验的数据规模和场景有关，这一点还不太好确定，感兴趣的可以深入研究。
Notes
限于作者水平，难免在理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献列表中注明，但仍有可能有疏漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章供于学习交流，转载注明出处
参考
[1]. Kaiyrakhmet O, Lee S, Nam B, et al. SLM-DB: Single-Level Key-Value Store with Persistent Memory[C]//17th {USENIX} Conference on File and Storage Technologies ({FAST} 19). 2019: 191-205.
[2]. 如何看待sqlite作者放弃sqlite4的开发，说使用LSM Tree是一种失败？. https://www.zhihu.com/question/67858225.
