YouDieInADream

Nope.

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

发布于 2020-07-29 | 标签: Paper 、 存储 、 LSM | 26分钟 | 6680字数 | 浏览量::
  • 该篇文章来自于 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_i 到 Li+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_0 到 L1L_1 的数据。利用 NVM 字节寻址的特性以及我们设计的 RowTable 可以实现开销更小的压缩。合并特定的键范围从 L0L_0 到 L1L_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_0 到 L1L_1 的一种细粒度压缩方式。因此减少了 L0L_0 到 L1L_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 对，直到取到的键值对数目位于压缩的阈值下界和上届之间时 （即 12AF∗Ssst\frac{1}{2} AF*S_{sst} 到 AF∗SsstAF*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=N∗AFWA=N*AF，其中 N 为 LSM-trees 的层级数。因此 Matrix 的另一个设计思路就是通过减小 LSM-tree 的深度来减小写放大。MatrixKV 通过固定比例增加每一层的大小限制，使相邻层的 AF 保持不变来减少 LSM-tree 的层数。
  • 但是这样单层扩大带来了两个负面影响：
    • 扩大后的 L0L_0 与 L1L_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_0 到 L1L_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_0 到 L1L_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 来保证原有的读性能
# Paper # 存储 # LSM
TinyKV 学习笔记 上一篇
Series Six of Basic of Persistence - Log-structured File System 下一篇
已运行:
浏览数: 次 | 访客数: 人
Powered by Gridea
0%