MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM

  • 该篇文章来自于 ATC2020 上非易失主题下的论文 MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM
  • 由于很久没看论文了,前段时间也看了论文作者的一些分享,特别优秀的学姐,恰好对相关方向比较感兴趣,好像还和 PingCAP 合作。故拜读了这篇 Paper
  • 本文主要结合了 NVM,然后针对 LSM 优化领域中少有的对写停顿的优化进行了分析与设计,基于 RocksDB 进行了实现,且已开源,使用了最新的器件 Optane 进行了测试。

Abstract

  • 现有的基于 LSM-tree 的 KV 存储性能表现欠佳,且性能常常无法预测,主要原因就是其严峻的 写放大和写停顿 的问题(Write Stalls)。实验结果表明:
    • 写停顿主要源于 L0-L1 层之间的大量数据的压缩过程
    • 写放大会随着 LSM-trees 的深度增加而不断增大
  • 利用 NVM 基于 LSM-trees 提出了一种 KV 存储的设计 MatrixKV(包含了多级存储:DRAM-NVM-SSD),设计原则表现为:
    • 让 L0-L1 层之间的压缩开销更小从而减少写停顿
    • 减小 LSM-tree 的深度来减小写放大
  • 核心思想主要表现为以下四点:
    • 利用自己提出的 matrix container 在 NVM 上管理 L0 层
    • 设计了新的 column compaction 引用到了 L0-L1 的压缩中来减少压缩数据的量
    • 增加每一层的宽度来减少 LSM-tree 的深度
    • 引入了 cross-row hint search 来改善读性能
  • 和 RocksDB 以及 KVS NoveLSM 对比, 99th 尾延迟降低了 5x 和 1.9x,随机写吞吐量提升了 3.6x 和 2.6x

Introduction

  • 为什么引入 NVM?:考虑到随机写操作在流行的 OLTP 工作负载中很常见,不管是突发的还是持续的随机写都是用户很关注的问题,DRAM-SSD 这种存储结构形式就是想利用快速的 DRAM 和持久的 SSD 来提供高性能的数据库访问操作,但是如 cell size、功耗、成本以及 DIMM 槽数量的限制使得不能只通过提升 DRAM 大小来提升性能。因此,在混合存储系统中使用 NVM 成为了现代存储系统的一个新方向。
  • 原有的 LSM-tree 存在的问题:在 DRAM-SSD 的存储结构的基础上使用 RocksDB 进行测试,观察实验结果并分析原因:
    • 写入停顿会导致应用程序吞吐量周期性地降至几乎为零,从而导致性能的剧烈波动和长尾延迟。写停顿的主要原因是每次 L0-L1 压缩处理的数据量大,合并时会合并 L0 和 L1 的所有数据,但是 L0 无序,合并过程占用较多的 CPU 资源和 SSD 带宽,从而导致写停顿和较高的尾延迟。
    • 写入放大(WA) 降低了系统性能和存储设备的耐久性。

关键技术

  • Matrix container:Matrix Container 通过在 NVM 上使用一个 receiver 和一个 compactor 来管理无序的 L0。Receiver 维护来自 DRAM 刷回的 MemTable,一行一个 MemTable。Compactor 选择并合并 L0 中的数据子集合到 L1。(选择具有相同键范围的数据),每次压缩一列。
  • Column compaction:列压缩是 L0 和 L1 之间的细粒度压缩,每次压缩一个小的键范围,因为处理的数据量有限,并迅速释放 NVM 中存放的列从而继续接受来自 DRAM 刷回的数据,从而减小写停顿。
  • Reducing LSM-tree depth:增大每一层 LSM-tree 的容量来减少层数
  • Cross-row hint search:为每个键提供一个指针,用于对 Matrix Containier 中的所有键进行逻辑排序,从而加速搜索过程

Background and Motivation

Background

  • NVM 的出现:存储介质的发展,PCM、memristors、3D Xpoint、STT-MRAM 等存储介质的发展使得 NVM 成为新的选择。字节寻址、持久化、快速,接近 DRAM 的性能,类似于磁盘的持久性,比 DRAM 更低成本获得更大的容量,比 SSD 更低的读写延迟以及更高的带宽。研究表明 NVM 作为存储设备,使用 PCIe 总线时,只实现了边际的性能改进,浪费了 NVM 的介质带来的高性能,所以很多都将 NVM 作为单级内存使用。最常用的是 DRAM-NVM-SSD 三级存储:
    • NVM 有望在未来几年与大容量 SSD 共存
    • 与 DRAM 相比,NVM 仍然有 5 倍的低带宽和 3 倍的高读取延迟
    • 混合系统平衡了 TCO(the total cost of ownership) 和系统性能。
  • 现有 LSM-trees 机制
    • 几个关键点:L0 层无序是为了保证刷回操作的快速执行,磁盘组件上需要进行压缩来减小读操作和扫描的开销。
    • 压缩过程大致如下:
      • LiL_i 层的一个 SSTable 和 Li+1L_{i+1} 层的多个 SSTables (具有重叠键范围的)被选作需要压缩的数据
      • LiL_i 中也在该键范围内的 SSTable 会被反选
      • 前面两步选择的 SSTable 将被加载到内存进行归并排序
      • 新生成的 SSTables 被写回到 Li+1L_{i+1}
    • 因为 L0L_0 层无序,每一个 SSTable 都有比较宽的键范围,就会来回执行上述步骤中的前两步,就很有可能导致两层中的所有的 SSTable 都被选中用于压缩,导致一个 all-to-all 压缩。
    • 读请求的处理,首先查询内存组件中的 MemTable,继续查询磁盘组件的各个层次,但是因为 L0L_0 层无序,即键的范围是重叠的,所以可能该层数据检索时遍历了所有 SSTables
      20200728211222
  • 现有的 LSM-trees 优化方案:减小写放大、提升内存管理、支持自动调优、使用混合存储结构优化 LSM-tree.其中随机写是最受关注的,因为受压缩的影响较大。对比对象 PebblesDB,SILK,NoveLSM
    • 减小写放大:PebblesDB,Lwc-tree,WiscKey,LSM-trie,VTtree,TRIAD。然而,几乎所有这些工作都忽略了性能差异和写停顿。
    • 减少写停顿:SILK 引入了一个I/O调度器,通过将刷新和压缩延迟到低负载时期、对刷新和较低级别的压缩进行优先级排序以及抢占压缩,可以减轻写暂停对客户端写的影响。Blsm 提出了一个新的合并调度程序,称为“spring and gear”,以协调多级别的压缩。但该方案只是限制了最大写处理延迟,忽略了排队延迟。KVell 使磁盘上的 KV 无序,以减少 CPU 计算成本,从而减轻基于 NVMe SSD 的 KV 存储的写停顿,这不适用于具有一般 SSD 的系统。
    • 引入 NVM 到 LSM 中:SLM-DB,MyNVM,NoveLSM,NVMRocks。

Challenges and Motivations

  • 主要表现为两方面:写停顿和写放大。
  • 测试结果表明:系统性能经历高峰和低谷,而吞吐量的低谷表现为写停顿。显著的波动表明性能不可预测和不稳定
    20200728173136

Write Stalls

  • RocksDB 中主要有三种可能的停顿:
    • Insert stall:在完成后台刷回之前,如果 Memtable 被填满,所有的插入操作将停顿。
    • Flush stall:L0L_0 层有太多的 SSTables 并达到了大小限制,从内存刷回到 L0L_0 的操作将停顿
    • Compaction stalls:前面操作有太多待定的压缩数据块
  • 所有这些停顿都会对写性能产生级联影响,并导致写停顿。
  • 通过记录不同 level 的 flush 和 compaction 周期来测试这三种类型的停顿。L0L_0-L1L_1 压缩的周期与观察到的写停顿近似匹配,如图 2 所示,图中的每一个短红线表示一次 L0L_0-L1L_1 压缩,红线的长度表示压缩的延迟,纵轴对应此次压缩过程中处理的数量。压缩的数据量平均大小为 3.10 GB,大量压缩数据会导致大量的读合并写,占用 CPU 周期和 SSD 带宽,从而阻塞前台请求,使L0-L1压缩成为写停顿的主要原因。
    20200728220734
  • 写停顿不仅导致系统吞吐量低,而且还导致了高写延迟,从而导致长尾延迟问题。CDF 累积分布函数如图所示,76% 的写请求延迟低于 48 微秒,但是尾延迟达到了 1ms,高延迟会显著降低用户体验的质量,特别是对于延迟关键型应用程序
    20200728220948

Write Amplification

  • 系统吞吐量随着数据集大小的增加而降低。写放大(WA)定义为写入存储设备的数据量与用户写入的数据量之间的比率。由于相邻 Level 的大小从低到高以放大倍数(AF = 10)呈指数增长,所以从 LiL_iLi+1L_{i+1} 的压缩可能会导致平均 AF 倍的写放大,数据集的增长会增加 LSM 树的深度,也会增加总体 WA。增加的 WA 消耗更多的存储带宽,与刷新操作竞争,并最终降低应用程序吞吐量。因此,系统吞吐量随着 LSM 树深度的增加而降低。

NoveLSM

  • 设计思想主要表现为:
    • 采用 NVM 替代 DRAM,从而增加可以存储的 Memtable 和 Immutable Memtable 的容量
    • 允许 NVM 上的 Memtable 被直接更新从而减少压缩
  • 然而,这些设计选择只是推迟了写停顿,当数据集大小达到了 NVM Memtable 的容量,还是会产生 flush stall,(这里有个疑问,为啥是 flush stall,不应该是 insert stall 吗?)NVM 中扩大的 memtable 被刷新到 L0L_0,并显著增加了 L0L_0 - L1L_1 压缩中的数据量,导致更严重的写停顿。
    20200728221723
  • 使用 8GB 的 NVM 和 80GB 的数据集测试了 NoveLSM,测试结果如图所示:相比于 RocksDB 整体 load 时间下降了 1.7 倍,但是写停顿的周期变得更长,主要是因为 L0L_0 - L1L_1 压缩中的数据量较大,如图所示超过了 15GB,和图二中 RocksDB 的数据量对比 4.86x。当 L0L_0 - L1L_1 压缩开始就会产生写停顿,在压缩开始之前可能还要等待更高级别或者更高优先级的压缩完成,如图中的灰色短线所示,压缩完成后性能再次提升。显然,NoveLSM 加剧了写停顿。
    20200729101711

Summary

  • 从上述分析中我们不难看出造成写停顿的主要原因是 L0L_0 - L1L_1 压缩过程中的数据量太大,造成写放大系数较大的原因是 LSM-trees 的深度较大。正是两者的共同作用使得系统吞吐量较低并增大了尾延迟。
  • NoveLSM 试图解决这些问题时却加剧了写停顿,基于以上挑战,我们提出了 MatrixKV,致力于通过巧妙地使用 NVM 来提供一个稳定的低延迟的 KV 存储。

MatrixKV Design

  • 四个关键技术:
    • the matrix container in NVMs to manage the L0 of LSM-trees
    • column compactions for L0 and L1
    • reducing LSM-tree levels
    • the cross-row hint search
      20200729103236

Matrix Container

  • NoverLSM 使用 NVM 来增大 MemTable 的大小,但是因为有了更大的 L0 层加剧了写停顿,并未解决瓶颈。因此为了减少写停顿,需要遵循的基本原则就是减少 L0L_0 - L1L_1 单次压缩过程中的数据量或粒度。基于这样的原则,MatrixKV 从 SSD 上将 L0 层提升到了 NVM,并重新组织 L0 到 matrix container 中,想要充分利用 NVM 的字节寻址和快速的随机访问。matrix container 是在 NVM 上的 L0 的数据管理结构,如图所示,主要由 Receiver 和 Compactor 组成。
    20200729104017

Receiver

  • Receiver 接收从 DRAM 刷回的 MemTables,每一个 Memtable 被序列化成 Receiver 中一个单独的行,称为 RowTable。在 Matrix Container 中 RowTable 按行排列,有对应的序列编号,从 0 到 n,Receiver 初始容量为一个 RowTable,当 Receiver 的大小达到阈值时,比如 Matrix Container 的百分之六十,并且 Compactor 为空的时候,Receiver 将停止接受 flush 的 MemTables 并转变为 Compactor。与此同时,会创建一个新的 Receiver 用于接受 Flushed Memtables,在整个逻辑转换过程中不会发生任何数据迁移。
  • RowTable:由数据和元数据组成,为了构造 RowTable,我们必须首先序列化来自 Immutable Memtable 的 KV 对并进行排序,然后存储到到对应的数据区。然后使用一个有序的数组为所有 KV 对构建元数据,包含对应的页号,在页内的偏移,一个前置指针 pnp_n
    • 在 RowTable 中查找 KV,首先进行二分查找找到对应的目标 Key 和对应的页号、偏移量。
    • 每个元素的 forward pointer 是用于 cross-row hint 搜索的,从而提升读性能。后面章节会讨论。
    • 和传统的 LSM-trees 中的 SSTable 进行对比,SSTable 是以块为单位进行组织的,RowTable 是以 NVM 页为单位进行组织的,除此以外就是元数据的组织方式上略有不同,因此构建 SSTable 和 RowTable 的开销时接近的。
      20200729105502
  • Compactor:用于以较细的粒度选择和合并 SSD 中从 L0L_0L1L_1 的数据。利用 NVM 字节寻址的特性以及我们设计的 RowTable 可以实现开销更小的压缩。合并特定的键范围从 L0L_0L1L_1 上的 SSTables 子集,而不需要合并所有 L0L_0 和所有 L1L_1。我们称之为 Column Compaction
    • 在 Compactor 中,KV 对由逻辑上的列来组织管理,一列就是一个具有一定数量的 Key 的子集,也就是 Column Compaction 的基本单元。具体而言,来自不同 RowTables 的 KV 键值对在一个列对应的键范围内形成了一个逻辑上的列。
    • 这些位于一列里的 KV 对的数量即为一个列的大小,因此一个列的大小不是固定的,但是会有一个由 Column Compaction 控制的阈值大小。
  • Space Management:在一个列的数据被压缩之后,对应的占据的 NVM 的空间将会被释放。我们使用了页算法来管理这些空闲的空间。由于列压缩会旋转键范围,因此每个行表最多只分段一个页面。列压缩后完全释放的 NVM 页面将作为一组页面大小的单元添加到空闲列表中。为了在 Receiver 中存储传入的 RowTable,我们应用空闲列表中的空闲页面。
    • 8GB 的 matrix container 包含 2112^{11} 个 4K 大小的页,每一个页由页号(无符号整数)标识,为每个列表元素添加 8 字节的指针,每个页面的元数据大小即为 12 字节。因此 NVM 上空闲列表最多占据 24KB。

Column Compaction

  • 该压缩过程是指 L0L_0L1L_1 的一种细粒度压缩方式。因此减少了 L0L_0L1L_1 压缩过程中的数据量,从而减少写停顿。该压缩过程大致如下:
    • MatrixKV 将 L1L_1 的键空间分隔为多个连续的键范围:因为 L1L_1 的 SSTables 有序,每一个 SSTable 都有对应的最小和最大键,所有的 SSTables 的最小键和最大键形成一个有序的键列表,每两个相邻的键代表一个键范围,就能得到多个连续的键范围。
    • Column Compaction 从上述步骤的第一个键范围开始,即选择一个 L1L_1 中的键范围作为要压缩的键范围。
    • 在 Compactor 中,对应压缩键范围的 KV 对被并发地从多个 Rows 中选出来。假设由 N 个 RowTables,K 个线程用于并行地取对应范围的键,那么每个线程负责 N/K 个RowTables,我们为了保证足够的并发访问,用 8 个线程去 NVM 上操作。
    • 如果取到的数据个数没有达到压缩的阈值下界,那么将会加入第二个键范围,对应的 K 个线程将继续在 N 个 Row 中寻找对应的 KV 对,直到取到的键值对数目位于压缩的阈值下界和上届之间时 (即 12AFSsst\frac{1}{2} AF*S_{sst}AFSsstAF*S_{sst} 之间)。这两个边界值保证了 Column Compaction 合理的开销
    • 上述步骤选择出的 KV 对在 Compactor 中形成一个逻辑的列
    • 列中的数据和对应的具有重叠键范围的 L1L_1 层的 SSTables 在内存中进行合并
    • 最终,合并后的 SSTables 被写回 L1L_1
    • Column Compaction 继续执行,选择下一个键范围,下一列。Column Compaction 选择键范围将形成一个环,旋转一直执行,从而保证平衡。
  • 如图所示:首先选择了 0-3 的 SSTable 范围,然后搜索 RowTable 元数据找到对应的键,个数低于下界,即不足以执行一次压缩,那么继续选择一个键范围,比如 3-5,那么合并之后就是 0-5,如果还是未到下界,继续扩大,再选择 5-8,此时达到阈值 10,最终选择 0-8。此时就形成了逻辑上的一列。
    20200729113636

Reducing LSM-tree Depth

  • 传统的 LSM-trees 对应的 AF 一般为 10,其深度会随着数据量的增长而不断增大,写放大系数对应的可以表示为 WA=NAFWA=N*AF,其中 N 为 LSM-trees 的层级数。因此 Matrix 的另一个设计思路就是通过减小 LSM-tree 的深度来减小写放大。MatrixKV 通过固定比例增加每一层的大小限制,使相邻层的 AF 保持不变来减少 LSM-tree 的层数。
  • 但是这样单层扩大带来了两个负面影响:
    • 扩大后的 L0L_0L1L_1 有更多的重叠键范围,那么压缩过程中的数据量将增大,不会增加压缩的开销但是会延长写停顿的时间。
    • 遍历更大的 L0L_0 会降低查询操作的效率。
  • 通过使用 Column Compaction 能够较好地解决第一个负面影响,因为该压缩方式不会受到每一层的数据容量的影响
  • Matrix 提出了 cross-row hint search 来改善增大单层容量操作带来的查询开销
  • 在 MatrixKV 的 L0L_0,每一个 RowTable 是有序的,不同的 RowTables 的键范围可能重叠。为每一个 table 构建布隆过滤器是减小查询开销的一个可能的方案,然而会引入构建布隆过滤器的开销而且不支持 range scan。为了提供更好的读和 scan 性能,我们构建了 cross-row hint searches
  • Constructing cross-row hints:在 RowTable 的结构中我们为每一个元数据元素添加了前置指针。RowTable i 中的 key x,对应的前置指针指向了 RowTable i-1 的 key y,y 是第一个不小于 x 的 key。这些前向指针提供了在不同行中对所有键进行逻辑排序的提示,类似于分层级联。因为每个前置指针只记录上一个行表的数组索引,所以只占据 4bytes,因此开销很低。(疑问:存储开销是很低,但是具体为每一个元素维护指针不是应该还挺耗时的吗?
  • Search process in the matrix container:一个查询操作从最近最新的 RowTable i 开始,如果目标 key 不在对应的键范围内,则相应地去检索 RowTable i-1。在 RowTable 内部执行二分查找。使用前向指针,我们可以缩小在前面的 RowTables 中的搜索范围。因此查询和 scan 操作将无须遍历所有的 tables。该方式通过显著减少查询操作对应的 table 和元素的数量来提升了整体的读效率。
  • 如图所示,假设我们检索 k=12 的 key,首先二分查找 RowTable 3,得到一个范围 10-23,然后根据前置指针 hint 找到 RowTable 2 中的 13-30,因为不包含 12,此时需要把 13 之前的 8 给纳入进来,变成 8-13-30。再进行二分查找,没找到对应的 key,8-13, 移动到 RowTable 1, 9-10-13,二分查找 10-13,无对应的 key,继续看 RowTable 0,11-12-14,二分查找找到了 12.
    20200729143209

Implementation

  • MatrixKV 通过使用 PMDK 库来访问 NVMs,使用 POSIX API 来访问 SSDs。
  • Write
    • 来自用户的写请求首先插入了一个 WAL 日志到 NVMs 以保证崩溃一致性
    • 数据在 DRAM 中被批量处理,形成 MemTable 和 Immutable Memtable
    • Change)Immutable Memtable 被刷入到 NVM 并以 RowTable 的形式保存在 matrix container 的 receiver 中
    • Change)当 RowTables 的数量到达了大小限制,例如 matrix container 的百分之六十,且 compactor 为空,receiver 将变成 compactor
    • Change)Compactor 中的数据将和 SSTable 数据以 Column Compaction 的形式进行压缩,同时新的 receiver 将继续接受刷回的 Memtables
    • SSDs 上的压缩还是和原有的 RocksDB 保持一致
  • Read:同 RocksDB 的读操作处理方式大致相同,顺序变为 DRAM > NVM > SSD。在 NVMs 中,cross-row hint 搜索有助于更快地在 L0 的不同 RowTables 之间进行搜索。通过在不同的存储设备中并发地搜索,可以进一步提高读取性能。
  • Consistency:NVM 中的数据结构必须避免由系统故障引起的不一致性。在 MatrixKV 中,对 NVM 的写或更新操作只发生在两个阶段,flush 和 column compaction。
    • 对于 flush 操作,如果在写 RowTable 的过程中发生了错误,MatrixKV 可以重新处理被记录在 WAL 中的事务
    • 对于 Column Compaction 操作,为了实现一致性和可靠性的低开销,Matrix 采用了 RocksDB 的版本机制,使用一个 mainfest 文件记录数据库的状态,compaction 的操作会被持久化到 mainfest 文件中,作为一个版本的变化。如果系统发生了故障,则使用版本号恢复到最近的一个一致的状态。MatrixKV 会添加 RowTables 的状态到 mainfest 文件中,例如第一个 key 对应的偏移,key 的数量,文件的大小,元数据的大小等。MatrixKV 使用延迟删除来保证在一个一致的新版本完成之前,由于列压缩而失效的陈旧列不会被删除。

Evaluation

测试环境

  • 硬件:
    • 2 Genuine Intel(R) 2.20GHz 24-core processors
    • 32 GB of memory
    • 800 GB Intel SSDSC2BB800G7 SSD
    • 256 GB NVMs of two 128 GB Intel Optane DC PMM
  • 软件:
    • The kernel version is 64-bit Linux 4.13.9
    • OS:Fedora 27

对照组

  • RocksDB (including RocksDB-SSD and RocksDB-L0-NVM(8G) )
  • NoveLSM 8GB NVM
  • MatrixKV 8 GB L0, SSD L1 8GB
  • PebblesDB DRAM-NVM
  • SILK DRAM-NVM

其他配置

  • RocksDB:64 MB MemTables/SSTables, 256 MB L1 size, and AF of 10. The default key-value sizes are 16 bytes and 4 KB

负载

  • db_bench: the micro-benchmark released with RocksDB.
  • YCSB macro-benchmarks

测试结果

db_bench 写性能

随机写
  • RocksDB-SSD 和 RocksDB-L0-NVM 之间的对比表明:通过将 L0 放置在 NVM 上带来了大约 65% 的提升
  • Matrix 相比 RocksDB-L0-NVM 和 NoveLSM 吞吐量在所有的 value 大小都有提升,相比于 RocksDB-L0-NVM 提升了大约 1.86x 到 3.61x,相比于 NoveLSM 提升了 1.72x 到 2.61x
顺序写
  • 因为顺序写不会导致压缩,所以四种存储的顺序写吞吐量都要比随机写的吞吐量要高。
  • RocksDB-SSD 性能更好是因为其他三种存储引擎都使用了 NVM,就多了一次 NVM 到 SSD 上的数据迁移开销
  • MatrixKV 优于 NoveLSM 是因为 缩小的 RowTable 的开销比在 NoveLSM 上的大的跳表更新的开销小。

db_bench 读性能

  • 因为 NVM 中只保存了数据量百分之十的数据,所以化石 SSD 的读性能占据了更大的比重。四种方案总体表现接近,MatrixKV 优化之后并没有造成读性能降级甚至在顺序读上有一定的提升:因为 cross-row hint 搜索减少了大 L0 的检索开销,还拥有更小的层数,进一步使得查询的开销变小。
20200729152527

YCSB

  • MatrixKV 在写密集的负载下提升效果明显
  • MatrixKV 在读密集的负载下保持了平均水平
  • MatrixKV 和 NoveLSM 在负载 D 下表现得最好是因为 latest 的分布,使得在 NVM 中就能命中很多数据
    20200729160723

Tail latency

  • 通过减少写停顿和写放大,MatrixKV 极大降低了尾延迟并提升了用户服务质量。
    20200729161421

性能分析

写停顿

  • MatrixKV 使用了更少的时间处理对应的负载,因为随机写吞吐量更高
  • RocksDB 和 NoveLSM 都有严重的由于 L0L_0L1L_1 之间的压缩造成的写停顿问题
  • MatrixKV 相比之下实现了最稳定的性能
    20200729161643

写放大

  • MatrixKV 的写放大系数更小
    20200729162000

MatrixKV Enabling Techniques

  • Column compaction 的效率对比
    20200729162104

  • Overall compaction efficiency

    • MatrixKV 压缩次数最少,因为树的层级降低
    • MatrixKV 中的所有压缩处理的数据量相近,因为我们减少了 L0-L1 上的压缩数据量,而没有增加其他级别上的压缩数据量。
    • NoveLSM and RocksDB-L0-NVM 比 RocksDB-SSD 压缩次数少的原因是
      • NoveLSM 使用了比较大的 Memtable 来处理写请求,吸收了一部分的 update 请求
      • RocksDB-L0-NVM 在 NVM 上存放了 8GB L0 数据,存储了更多的数据
    • NoveLSM 和 RocksDB 大量的压缩数据来自于 L0-L1 压缩。
      20200729162249
  • Reducing LSM-tree depth:RocsksDB 和 MatrixKV 随着单层容量的增加都减小了写放大,但是对性能的影响有所不同,RocksDB 随着单层的增大性能反而降低,因为增大了 L0L_0L1L_1 压缩的数据量。MatrixKV 使用了独立的压缩策略不受大小变化的影响才得以实现更高的性能。
    20200729162919

Extended Comparisons on NVMs

  • MatrixKV 不仅仅是因为 NVM 的引入使得性能变得很好,还有设计思路和方案的加持。故和其他使用了 NVM 的方案进行了对比:
  • 通过对比发现,MatrixKV 的方案是很适合 NVM 的,相比于其他如 PebblesDB 把 NVM 作为块设备的方案。
    20200729163601

Conclusion

  • 提出了基于 LSM-trees 的稳定的、低延迟的 KV 存储方案
    • 使用了多级存储结构 DRAM-NVM-SSD
    • 在 NVM 上设计实现了 matrix container 来管理 L0L_0 层,并采用适当的粒度进行 Column Compaction 来减小写停顿
    • 通过增大每一层的容量来减小树的高度,从而减小写放大
    • 使用 cross-hint search 来保证原有的读性能