LSM 优化系列（六）-- 【ATC‘20】MatrixKV : NVM 的PMEM 在 LSM-tree的write stall和写放大上的优化

这篇论文大家可能不了解，但是"华为天才少女 年薪150w" 那个热搜女孩大家应该听过。这里分享的这一篇论文是ATC’20 存储技术相关的顶会今年收录的一篇，她是一作；去年她的一篇GearDB: A GC-free Key-Value Store on HM-SMR Drives with Gear Compaction 被FAST’19 收录，她也是一作。

她之前的相关论文并没有再搜，但从这两篇顶会以一作的身份来看，她本身的实力不言而喻。存储技术的顶会大家可以看看相关的官网数据，国内被录入的基本都是顶级互联网公司级的团队产出 以及 知名教授带领的C9 top学校团队。她以一作 贡献最大的身份被录入，这样的年薪是实至名归的（国内还是需要留住优秀人才的）。

当然，她所做的技术是数据库/存储相关的，同样是TOP级公司极为看重的核心技术，也才会有这样的优质待遇。

回到今天要讨论的论文 : MatrixKV:Reducing Write Stalls and Write Amplification 上。

ps：本篇并非论文翻译，下文的组织形态是比较简化的，感觉可能会有信息缺失的同学可以直接看论文。
该论文是基于 rocksdb 5.18.3 版本实现的，源代码MatrixKV-github

关于rocksdb compaction的一些基础知识可以参考这两篇。这是详解，会涉及到源码层级的分析。
1. SST文件详细格式源码解析
2. Compaction 完整实现过程 概览

LSM 问题背景

本篇论文关注的问题背景是LSM-tree 带来的 write-stall 以及 写放大问题。
都是针对LSM的老生常谈的问题，关于write-stall 直接参考SILK- Preventing Latency Spikes in Log-Structured Merge Key-Value Stores 中的Latency Spike 在LSM-tree中的体现即可。

其中Write-Stall的主体原因还是I/O资源的竞争，Higher-level compaction 与更高优先级的Flush和L0->L1 compaction的I/O资源进行竞争，导致更高优先级的internal 操作无法及时完成，最终体现在客户端的操作就是Write-stall或者高长尾延时。 而造成write-stall 的主体compaction就是 L0->L1 的compaction过程，这个过程L0重复的key最多，但却只有一个compaction 线程来做（传统LSM 在更高层中 sst文件之间以及之内不允许又重叠key），所以效率也很低，这就在大压力的场景下很大概率造成write-stall。

写放大问题简要概述一下，在PebblesDB Building Key-Value Stores using FLSM-Tree(Fragmented) 中的背景描述也有说。
如下图

L1->L2 compaction的过程中，选择一部分L1的sst文件，一部分L2的sst文件，compaction之后又写入到了L2；这样下一次 又调用的 L1->L2 的compaction 可能又会将之前的写入的sst文件的key-value读出来，重新合并排序，再次写入到L2。这样，很多key-value不断的被读写，而自己本身并没有发生变化。随着LSM 层数的增加，读写放大的比例会越来越大 WAM = AF *n（wam 是写放大的倍数，AF是写放大的系数，n是LSM的层数）。

这就是在Level compaction过程中出现的读写放大，带宽资源有限的情况下用户态吞吐会被严重限制。

MatrixKV 的出现背景 就是想要在Write stall 和 写放大上 进行一些优化，重心需要放在L0->L1的compaction速度慢问题之上。直接办法是变更存储介质（NVM-PMEM），只变更存储介质，仍然会有write-stall的问题，毕竟L0->L1 compaction速度提升不上来。这里我比较好奇的是论文中并没有提到subcompaction机制，rocksdb的subcompaction机制本身也是在L0->L1 compaction速度慢的情况下按照sst文件粒度拆分成多个compaction线程并发来做。

总之，只变更存储介质为更高性能的（NVM-PMEM）是不够的，论文中有Novel-LSM 的数据可以看到还是有大量write-stall。所以还需要变更L0->L1的数据结构，实现算法层的加速。至于，降低写放大，通过这个公式 WAM = AF *n，论文中直接将 Level层数减少，比如原来的6层，减少为4层，并增大每一层的容量（这个优化略显尴尬😅）。

NVM-PMEM性能
延时和吞吐 和内存DRAM处于一个量级，注意，是一个量级，实际还会差几倍。但是相比于NAND ssd 延时好2个量级，带宽也是有数倍的提升。

还有一种是DIMM-PMEM 持久内存，两者的主要差异是I/O传输使用的系统总线不同，NVME是走PCIe总线，DIMM 是内存总线，所以DIMM 性能相比于PCIe的性能好一些。后续我的博客会介绍一些SATA,SAS,PCIe,NVMe 这一些之间的区别。

问题背景和优化方向已经做了一个总的描述，优化的结果 是L0-L1 compaction过程中 如何利用好NVM-PMEM做好算法的设计，也就是MatrixKV的 设计核心MatrixComtainer。

MatrixKV 设计细节

整体架构介绍

MatrixKV 在LSM 整体设计中 用了组合存储，即DRAM，NVM-PMEM,SSD。
这里需要补充一点，减少Write-Stall 方法 在上文中的表述可以归纳为两方面：

1. 加速L0->L1 compaction的速度，也就是单位时间内完成compacion的数据总量越大越好
2. 减少L0->L1 compaction 与 Higher Level compaction的资源竞争问题

所以MatrixKV 除了设计了全新的L0->L1 compaction算法，还将L0->L1的compaction和Higher Level compactions 分布在不同的存储介质上，把Higher Level compactions 单独放在SSD 上， 这样就不会有I/O资源的竞争问题了。

整体MatrixKV的设计架构如下图

架构图中的基本组件及其作用如下：

• DRAM: 继续保存mem/imm
• NVM-PMEM: MatrixContainer 来保存L0的key-value数据存储 以及 L0->L1的compaction调度
• SSD：保存更高层的SST文件 以及 按照rocksdb原生compaction逻辑调度compaction

写入流程如下：

1. rocksdb原生逻辑，先更新DRAM中的memtable, memtable写满之后切换为immutable memtable
2. imm flush到处于 NVM-PMEM中的matrix containter，又Receiver 组件负责接受flush的k-v数据，并通过pmdk写入到NVM-PMEM之上
3. receiver 切换为compactor 调度 column compaction
4. column compaction结果最终会形成一个个SST文件落在SSD上的L1层，由后续compaction在更高层按照rocksdb的原生逻辑调度。

接下来详细看一下Matrix Container组件及其设计细节。

Matrix Container介绍

Matrix container 可以看作是一个新的数据管理结构。

主要有两个协调组件和一个k-v数据存储结构 以及 NVM-PMEM空间管理结构：

• Receiver，负责接受imm的数据，转化为一个RowTable 存储，并为这个RowTable分配一个唯一标识的递增编号
• Compactor，当Receiver存储的RowTable总大小达到了Matrix Container容量的阈值（比如60%），切换为Compactor，将多个RowTable 按列并结合L1的sst文件 触发Column Compaction。
• RowTable ，行表。每一行存储一个imm，使用的是pmdk 的 底层pmem相关接口写入到持久内存中。
• space-management ，为Receiver分配以page为粒度的存储空间，回收compaction完成compaction之后的空间。

Receiver

Receiver 主要用作保存来自memtable的数据，准确的说是immtable中的数据，这一个过程是imm从DRAM中调用flush操作完成的。每一个imm 会被Receiver序列化为一个单行的RowTable，RowTable会得到一个持续递增的编号标识自己，同时追加写入到Matrix Container。

当Receiver的中rowtable 的总大小达到了一定的阈值（用户态可以配置，比如60%），此时Compactor也是空的。当前的Receiver 会停止接受来自客户端的flush 并 切换成Compactor。同时，一个新的Receiver会被创建出来接受来自DRAM的imm flush。

这个过程并没有数据迁移，仅仅是两个组件的状态切换 并加上 一些打标签的过程。这个过程也有点像active memtale和 immutable memtable 之间的切换。

RowTable

Receiver接受到的一个imm k-v 序列化为一个RowTable，详细格式如下

可以看到rowtable中主要分为两个数据存储区域：Data, Metadata

• Data ： 有序存储key-value数据，value紧挨着key存储。（memtable有序，flush的key-value数据默认是有序的）
• Metadata：包含： 索引key、该key在Data区域的偏移地址 offset、该key 在Data区域的页面Page（逻辑页，代码中默认大小是256KB,这个大小也是NVM的基本配置单元）、还有一个pointer，用来加速Matrix Container中的读，指向前一个RowTable 大于当前key的key index。

通过如上图也可以看到RowTatable和SST文件的差异，除了Metadata中的block差异，其他方面还是比较相似的。

Compactor

compaction 主要是用来从L0 和 在SSD上的L1中的sst文件选择能够进行merge的key-value，并将完成合并的数据形成SST文件写到L1中。加速 column compaction的过程其实是通过NVM-PMEM的 一个特性：支持按照字节寻址的能力。也就是之前在SSD上以block(4K)为单位读取数据，而在NVM-PMEM中 最小的读取单元是(256B)，这大大减少了compaction的开销。

compactor会根据用户态的配置，将一列keys形成一个column，然后按列进行compaction。当然，compactor本身也会有column compaction的触发限制，没有达到限制并不会触发column compaction。

关于column compaction的细节后续会详细描述。

Space management

因为Matri Container 是通过pmdk直接操作NVM-PMEM，需要涉及到空间管理。毕竟人家PMEM只是一个存储设备，如何使用PMEM自己内部是不会感知的。

Matrix KV 维护了一个free list 链表 用来管理整个matrix container的空间。当column compactions完成之后会释放掉一部分空间，如果释放的空间包含一个page,这个空闲page会被添加到freelist。Receiver 为RowTable分配空间时会从free list取空闲页。

论文中的数据貌似有问题，8G的contianer 中一个page配置的是4Kb，竟然只用了2^11 个节点就能表示，这里我理解应该是2^20个，或者作者配置的是4M一个page。

比如 代码中默认一个page大小是256KB，则一个8G的container包含 2^15个节点，每一个链表节点区数据使用unsignint 4byte表示，再加上一个8bytes的指针，链表节点的元数据总共只需要12bytes存储。也就是2^14 个节点只需要384KB的存储空间。

Column Compaction介绍

主体过程就是拿着L1 sst文件的key range 和 matrix container中的compactor形成的column 按行匹配，满足匹配规则的就将维护的column 和 L1的sst文件进行匹配，最终形成新的sst文件。

触发column Compaction的要求是Receiver中拥有的RowTable的大小达到了一定量，比如60%，则切换为Compactor之后，comapctor直接就开始调度column compaction相关的逻辑了。实际的代码中维护了三个水位，类似与之前L0 compaction trigger，slow, stop三个大小。

uint64_t Level0_column_compaction_trigger_size = 7ul * 1024 * 1024 * 1024;  //7G trigger
uint64_t Level0_column_compaction_slowdown_size = 7ul * 1024 * 1024 * 1024 + 512ul * 1024 * 1024;  //7.5G slowdown
uint64_t Level0_column_compaction_stop_size = 8ul * 1024 * 1024 * 1024;   //8G stop

大家看代码的过程中相关的规范/可读性 其实可以忽略的，毕竟是学术界的论文demo

完整拆分后的形态如下：

整个column compaction的过程可以分为以下七个详细步骤：

1. MatrixKV 将key range 按照L1 层的SST文件进行切分。
   
   比如上图，L1上的几个SST文件，每个SST文件有smallest_key和largest_key。那么最终的划分的key_range间隔是
   [1,3], [3,8],[8,11], [11,12]… [33,36]，这一些key_range会被放在一个vector中{1,3,8,11,12,15,…36}

2. Column compaction 会选择第一个key_range 作为开始，如上图中的[1,3]

3. 接下来进入到了Matrix Container中的compactor，这里此时有多个RowTable，启用多线程并发读Rowtable，按列逐个匹配RowTable中的key，看该key是否在挑选的L1的第一个key_range [1,3]。这里启用的多线程数目经过测试，维持在8个，如果此时 compactor 中有16个RowTable，则每个线程负责读2个RowTable即可。

4. 匹配的过程中除了要求 RowTable的列上满足在L1挑选的key_range内，如L1的第一个range [1,3]比column中的第一列的某个key 4小，那么将维护的key_range的vector中的下一个range 添加进来，即[3,8]，并和[1,3]合并为[1,8]继续进行匹配。 当一个Column中的key的数量/满足RowTable的文件大小超过了阈值（默认2个），则形成一个Column boundary。

   这个boundary 按照列分割了整个compactor中的RowTable。

5. 基于RowTable中的key 边界构建一个逻辑层的Column.

6. 一个Column data 会拿着已经构建好的 key的boundary，也就是key_range和L1中有重叠key的SST文件进行Merge。
   Merge的过程也是将MatrixContainer以及L1中目标数据读取到内存中，进行归并排序

7. 最终的结果会按照SST文件的targe大小形成一个或者多个SST文件，后续的compaction会在SSD上启用原本rocksdb的逻辑进行。

需要注意的是第一个column compaction L1并没有sst文件可供划分key_range,这里是通过判断 已经选择的Column 大小是否超过了4个，超过了直接进行column compaction。直接从3步开始，并没有匹配L1 key_range的逻辑了。

对于Column Compaction的总结

1. column compaction的性能提升（加速L0->L1 compaction）的根源还是 利用了NVM-PMEM的按照字节寻址（256B）的能力，Matrix Container中的读写都是通过pmdk来直接操作PMEM的。而这样形态的compaction也是为了适配PMEM 本身的形态。
2. 另一个减少WriteStall 的方式则是通过对分离NVM和SSD，两种compaction的IO带宽互不影响。
3. 再补充一个论文中降低写放大的优化是通过降低LSM的层数，加大每一层的容量来做的。即WAM= n*AF，保持AF不变的情况下（本身并没有优化L1以上的compaction逻辑），所以降低层数能够直接降低写放大。

论文中没有直接对比Column Comapction和 rocksdb原生的subcompaction的逻辑，这是一个奇怪的地方。

读加速 Cross-row Hint Search

因为L0的存储结构相比于SST文件已经发生了变化，所以需要保证L0的读能力（RowTable中并没有像SST文件那样的filter block和index block）如果不做任何优化，那就相当于在每个 rowtable 几十万条key中做二分查找，每一层都得做，这代价显而易见无法接受。

不选择bloom filter的原因如下：

1. 会带来额外的开销在构建filter 上，这个构建过程需要每一个key参与
2. bloom filter对点查友好，但对range scan并不友好

只需要在每个RowTable中引入和key数量一样的一个指针（8bytes），再构建RowTable的过程即可完成指针的指向。
类似如下图：

1. 每个RowTable内是有序的，这个指针只需要指向前一个RowTable第一个不小于自己key的节点即可。比如，RowTable3中的7 指向RowTable2中从左向右的第一个不小于自己key的节点8，依次每个rowtable的节点都指向前一个不小于自己的节点。

2. 查找的过程就类似于跳表。每一层rowtable通过 pointer可以定位一个目标key的左右边界，不用对一整层rowtable的key进行查找。

   比如查找12
   a. 二分查找定位到12 在10和13之间，10和13各自的pointer向下查找
   b. 到了第RowTable2，可以确定的12左右边界是在8,13之间
   c. 依此继续向前，直到rowTable0

首先查找的肯定是最新的rowTable3， 因为数据是最新的。

MatrixKv 写入完整流程

如下图：

1. 写入逻辑先写 WAL , 设备掉电，能够保存Mem/imm中的数据，继续flush rowtable
2. 更新DRAM 中的mem，mem满了switch 为只读的imm，并创建一个新的mem
3. imm flush 到PMEM中，被Receiver序列化形成Matrix Container中的一个RowTable
4. Receiver中的RowTable总容量达到了阈值，切换为Compactor
5. Compactor 调度Rowtable和L1的 SST文件进行 column compaction
6. column compaction的合并过程还是在DRAM中进行，column compaction完成，更新column 的元信息（smallest_key, largest_key, keys_num）到MANIFEST中，方便掉电之后重放 Matrix Container中的 column compaction
7. column compaction的结果 会形成SST文件写入到SSD层的L1中，后续在SSD上按照原生rocksdb的逻辑调度更高层的compaction。
   
   相比于原生rocksdb的逻辑，主要不同的是3，4，5步。

MatrixKV 读取完整流程

读取的过程就是逐层读取了，如下图。

MatrixKV 性能

这个性能应该是db_bench的测试数据，总体体现的优势是在随机写场景大value下有较为明显的收益。
而且读性能并不弱于参与对比的其他rocksdb模型，当然这个随机写吞吐提升的数据还需要测试。

在长尾收益中，因为有效提升了L0->L1 compaction的效率，所以长尾收益看起来还是很明显的。相比于其他的LSM 优化：

• SILK 是本身做了Flush、L0->L1 compaction 以及 Higher Level compactions的优先级调度，保证Flush以及L0->L1的compaction被优先调度，它在长尾的优化效果中还是很明显的。而Matrix KV比它还好，这个数据需要测试。
• Pebblesdb 为了减少写放大，引入了类似于跳表节点的gurad，且允许 guard 内部的sst文件有重叠。间接增加了读放大，所以pebblesdb的长尾数据是合理。

看到长尾优化这里有这么明显，还是比较吃惊的，数据待测试中。

还有一组写放大的优化效果，这个数据是通过降低了LSM的层数，增大单层内的LSM空间（论文中给的是扁平化LSM tree的说法），优化效果看起来也比较直观。

总结

Matrixkv 通过与NVM-PMEM的结合， 在write stall 和 写放大上有一定的优化。

write stall 优化有两方面：

• 主要是通过NVM-PMEM的字节寻址能力，加速了Matirx Container上 的column compaction 来降低write stall。
• 引入DRAM --> NVM-PMEM --> SSD 的存储形态，将compaction的IO抢占分开，互不影响

读上的优化：
在L0 的Matrix Container中 引入了Cross-row hint search，比较有借鉴意义。通过forward pointer加速读性能（缩减每次Get的key 范围）。

写放大的优化：
扁平化LSM，降低层数，增加单层容量。

存在的问题是，Column compaction并没有直接和rocksdb原生的sub_compaction 性能进行对比，相比于原生rocksdb性能是否能在L0->L1 compaction的速度进一步提升有待测试。