MSST’20 NovKV

References

Abstract

• 基于 LSM 的键值存储(lsm -store)在许多存储系统中扮演着重要的角色。然而，LSM 存储会遭受压缩操作的高写放大。最近提出的键值分离的 LSM 存储减少了影响，但是值部分的垃圾收集开销仍然很高。在本文中，我们发现现有的键值分离方法必须通过查询 LSM 树来检查键值项的有效性，并在垃圾收集时通过将键值项插入 LSM 树来更新值句柄。有效性检查和值句柄更新给 LSM 树带来了很大的开销。

• 为此，我们提出了一种有效的方法，通过消除 LSM 树的查询和插入来减少垃圾收集的昂贵开销。该方法包含三个关键技术：协作压缩 collaborative compaction、高效垃圾收集和选择性句柄更新。

• 我们在LevelDB之上实现这种方法，并将其命名为 NovKV。评估表明，NovKV 在随机写入和随机读取方面的性能分别比 wisckey 高出 1.98 倍和 1.85 倍。

Introduction

• 本文把 KV 分离方案中 key 和 value 的部分分别称之为 KStore 和 VStore。KV 分离的方案的开销主要是来源于 GC 操作需要检查 KStore 数据的有效性，从而删除掉过期的数据，对于有效的数据，拷贝移动到新位置，然后更新 KStore 中的指针信息。

• 本文旨在利用 KStore 和 VStore 之间的依赖来减少 GC 开销。我们观察到，KStore 中的压缩将无效值与有效值区分开来，所以我们把这个信息传递给 VStore，从而避免 GC 中的有效性检查，为了支持有效性信息的传递，在 VStore 中引入了 VTable 和 SVTable 设计，以便附加在 KStore 中已识别的无效键

• 本文还提出了延迟指针更新的操作直到需要读的时候，所以可以减少指针更新的开销。

• 基于上述两个点，提出了新的 KV 分离的 LSM 树，NovKV，从而减少了有效性检查的开销和指针更新的开销。

Contributions

• Collaborative Compaction：收集 Compaction 过程中的丢弃的 keys，然后把这些 keys 追加到两个新设计的表中

• Efficient Garbage Collection：垃圾回收的过程中就不检查 KStore 了，而是用可搜索的 SVTable 来避免 value 指针更新和快速的读取

• Selective Handle Updating：不会激进地把所有的有效值的新指针插回到 KStore，相反，NovKV 将保留这个指针，在一个客户端需要在 SVTable 中查找该值的时候才更新 KStore

Background and Motivation

• WiscKey 引入了 KV 分离，HashKV 在此基础上把 value 以哈希分区的形式来组织，HashKV 还把 vLog 分成了几个段组，然后把键值对映射到对应的段组。HashKV 的 GC 首先选择一个有最多写入的段组，然后顺序扫描该段组的 KV 项来做 GC，不需要查询 LSM 树，然后把所有的有效 KV 写回到段组，最后更新 LSM 树中的指针。
• HashKV 如何避免有效性检查的呢？使用了一个临时的内存哈希表来存储有效的键和值的位置，由于 KV 项按其写入顺序顺序存储在段组中，并且特定键值的所有版本必须散列到同一段组中，因此在扫描完成后，散列表将保存有效 KV 项的所有最新版本。因此，HashKV 可以将所有有效的 KV 项写回到段组中。

动机

• 即便 KV 分离减小了 Compaction 开销，但是 GC 还是引入了查询和插入的开销，即需要检查数据的有效性，然后把有效的 KV 项追加到 vLog 的头部，最后再把新的指针写回到 LSM 树，这些 GC 引入的查询和插入操作回合前端请求竞争可用的资源，导致性能降级。

• WiscKey 是分开独立运行 KStore 和 VStore 的 Compaction 和 GC 的，两个操作之间没有任何的协同。但其实在 KStore 中有一些有用的信息可以拿来促进 VStore 的 GC。我们发现键只有在 KStore 的 Compaction 过程中才会被丢弃，基于这些发现，我们记录了这些丢弃的键然后避免了在 GC 过程中查询 KStore

• 然后 VStore GC 可能会插入有效的数据指针到 KStore 很多次，但是大部分的 KV 数据在 GC 之后是不会被读取的，因此，许多 KV 数据的指针是在被反复插入的，即便他们没被读取，更糟糕的是，这种激进的插入方法增加了 Compaction 的频率因此增加了 Compaction 开销，所以我们只有在这些值被读取的时候插入到 KStore

Design

Architecture

• 图 1 描绘了 NovKV 的架构，由 KStore 和 VStore 组成，VStore 中又包含了 VTable 和 VMap，SVMap。
• value handle 对应的由 文件号，epoch，文件偏移，以及 item size 组成。epoch 表示一个表被重写的次数，也表示了一个 value handle 在 table 中是否是有效的
• VManifest 记录了 VStore 中的元数据来进行故障恢复，VRecovery 记录了最后一个 Memtable flush point

• 写请求首先编码 KV 成一个固定长度的字符串，VItem，如图 2 所示，然后追加到当前 VTable 的末尾，然后把对应的 value 句柄插入到 Memtable 中，当 VTables 达到限制，创建一个新的 VTable，然后把新的 VTable 插入到 VMap 中管理
• 数据首先以 VItem 的形式写到了 VTable，然后有 VMap 来管理 VTables；VMap 维护的是 fileno 和 Table 的映射

• 读请求首先查询 KStore 获取 value 句柄，然后使用句柄的文件号来检查是否该 value 文件存在于 VMap 中，如果存在就去直接通过句柄读取 VTable 中的值，不存在则表明对应的 VTable 已经垃圾回收了，然后现在是 SVTable。所以这时候需要从 SVMap 中取出 SVTable，如果对应 value 句柄的 epoch 和 SVTable 的 epoch 匹配的话，NovKV 就直接读取 SVTable 中 handle 所指向的值，不匹配，则表明该 SVTable 在这个句柄被插入到 KStore 之后被重写了，意味着这是一个无效的 value handle，因此，NovKV 在这个 SVTable 的 SSTable 部分中搜索 KV 项，SSTable 的搜索流程和 LevelDB 一致
• VTable 执行了 GC 之后变成 SVTable，SVMap 一样管理 fileno 和 Table 的映射，可能还包含了 Table 的 epoch 信息
• epoch 不一致是因为 SVTable 可能做了 GC，epoch 有所增加，但是索引中还是之前的 epoch

VTable

• VTable 由对应的 vLog 和几个 DropBlocks 组成
• vLog 包含了编码的 VItems 数据，然后通过 value handle 中包含的 offset 和 size 信息来定位 vLog 中的 value
• DropBlock 包含了一组 DropKeys 和一个 DFooter，DFooter 存储的是 DropBlock 和 VTable 的元数据信息
• Magic：检查文件完整性的魔数
• DOffset and DSize：DropBlock 的偏移量和大小
• ValueSize：记录了 vLog 的大小
• Total and Valid Keys：DFooter 记录了总键的个数以及当前 VTable 中有效 Key 的个数，有效 Key 的个数等于总 Key 的个数减去所有丢弃的 Key 数

• 为了避免在垃圾收集之前对 DFooter 进行额外的读取，NovKV 将最后一个 DFooter 保存在内存中，同时将计算的有效率(等于有效键/总键)保存在内存中

• 当当前 VTable 达到其大小阈值时，NovKV 将一个无效的 DFooter 附加到 vLog 部分的末尾，以指示以下 DropBlocks 的开始，我们称之为 finish。NovKV 创建一个新的 VTable 作为新的当前 VTable，并将这个 VTable 插入到 VMap 中。新创建的 VTable 未完成，只包含 vLog 部分。在 KStore 压缩过程中，NovKV 收集 KStore 删除的键，将这些键构建为 DropBlock，然后将 DropBlock 附加到 VTable 的末尾

SVTable

• 与 VTable 类似，SVTable 由一个 SSTable 部分和若干个 DropBlocks 组成，如图 3 所示。如上所述，NovKV 可能需要在 SVTable 中按键搜索值。因此，SVTable 用一个嵌入的 SSTable 替换 VTable 中的 vLog 部分。DFooter 保持与 VTable 相同，除了 ValueSize 在这里表示 SSTable 大小。

• 注意，一旦 NovKV 需要从 SVTable 中搜索值，我们可以确认这个键和值必须存在于 SSTable 中。因此，SSTable 中的 bloom 过滤器是不需要的

• 除了支持快速搜索之外，SVTable 比无序的 VTable 对缓存更友好，因为 SVTable 中的值是按键排序的。因此，在 SVTable 中通过值句柄直接读取的速度比在 VTable 中直接读取的速度快

KStore - 协同 Compaction

• LSM 树因为异地更新的原因可能会保存数据的多个版本，也就带来了两个问题：读操作需要读取正确的版本，无效的数据项需要被更新或者删除，所以需要决定一个数据项在 LSM 树中是否为有效的。LSM 维护了一个自增的序列号和一个快照列表，然后在 Compaction 期间丢弃 keys

• 在 KStore Compaction 之前，NovKV 首先创建一个 map，对应存储了 file number 和一组 keys 的映射，然后 NovKV 从 SSTable 上读取一个项，像传统的 Compaction 一样检查它的有效性，如果该数据项无效，NovKV 解码对应的 value 获取对应的文件号，然后将该 DropKey 插入到对应 map 中 file number 关联的数组里，Compaction 完成之后，NovKV 把这些 DropKeys 写到相应的 VTable 和 SVTable 中，然后触发一个 VStore 的 GC，如果已经有一个正在运行的 GC，则跳过触发。
• 本质就是在 Compaction 过程中按照每个文件分别记录了失效的 Keys，组成了每个文件的 DropKeys

VStore：高效的 GC

• 本方案中减少 GC 过程中的检查数据有效性和指针更新的开销，在 VStore 中持久化了前面从 KStore 中分离出来的有效性信息，然后使用 SVTable 来减少更新的指针的开销。

• 如下图所示，VTable 或者 SVTable 的无效数据项达到了阈值后，将执行垃圾回收的策略然后构建新的 SVTables
• 首先 NovKV 收集所有的已经完成的 VTables 和 SVTables 对应的有效率是否低于阈值 gc_threshold
• 然后按照数据的有效率降序排列，然后选择一组有效率最低的 VTables 和 SSTables，如果有效率为 0 将直接从 map 中删除并被直接回收
• 然后 NovKV 一个个地来处理剩下的 VTables 和 SVTables

GC 的流程

• NovKV 首先反向地从 DropBlocks 中读取 DropKeys，通过缓存的 DFooter 来读取对应的 DOffset 和 DSize，然后 NovKV 读取出最后一个 DropBlock 和前面的 DFooter

• NovKV 解码 DropBlock 然后插入到一个 hashset 中，读取 DropBlock 之后检查前面的 DFooter
• 如果 DFooter 是有效的，继续读取前一个 DropBlock，该 Block 由该有效的 DFooter 索引
• 否则结束读取

• VTable GC：对应的流程如下图所示
• NovKV 首先创建一个 SVTable，对应的 epoch 为 1，来存储有效的键值对，然后从 vLog 部分的开始段读取一个固定长度的内容，从内存中解码出一个 VItem，检查这个 Key 是否存在于 DropKeys
• 如果不存在，说明该键值对为有效的 KV 对，然后把这个键值对插入到新的 SVTable
• 否则直接丢弃该键值对
• 处理完一个 VItem 之后接着处理下一个 VItem，直到没有下一个
• 因为 VItem 在 VTable 中是乱序的，所以 SVTable 使用了一个 Memtable 来在构建过程中装有效键值对，当 VTable GC 完成后，再结束这个 SVTable，即把对应的 Memtable 构建成一个 SSTable 然后刷回磁盘，最后再追加写入一个无效的 DFooter 来作为 SSTable 部分的末尾
• 然后 NovKV 删除 VMap 中过期的数据，并把新创建的 SVTable 插入到 SVMap，主要该步骤需要一个锁来保护该步骤
• 有一个特殊情况需要处理：
• KStore 可能会在 GC 的期间发生很多次 Compaction，然后丢弃掉一些键到老旧的 VTables 中，这些 VTable 可能又参加了此次 GC
• 所以在删除旧的 VTable 之前，需要检查是否有新的 DropKeys 追加到了该旧的 VTable 中
• 这一次垃圾收集不读取这些新的 DropKey，所以 NovKV 将这些 dropkey 复制到新创建的 SVTable 中。最后，NovKV 删除这个过时的 VTable。

• SVTable GC：
• 和前面步骤是类似的。首先从 SVTable 中收集 DropKeys，然后创建对应的迭代器来读取键值对，后续过程一样
• 最后，NovKV 打开一个新创建的 SVTable，使用新的 SVTable 替换掉老的 SVTable，也需要锁来保护
• 新创建的 SVTable 的 epoch 等于过时的 SVTable 的 epoch 加1

Selective Handle Updating

• 该方案不会在 GC 中立即插入新的键值对句柄到 KStore 中，所以 value handle 中的 fileno 仍然是有效的，即便执行了 GC，GC 不会改变文件号，为了方便在垃圾收集值文件中搜索值，NovKV在 SVTable 中使用了嵌入的 SSTable。但是，这会给读进程带来额外的 SSTable 搜索开销。因此，NovKV 提出了一种机制来更新过时的值句柄

• 当 NovKV 在 SVTable 中搜索一个值时，NovKV 也获得 SVTable中 的值句柄，并将这个新的值句柄插入到 KStore 中的 MemTable 中，以修复无效的值句柄。

• 一个完全的内存写的成本非常低，这使得在读过程中更新句柄成为可能。这样，NovKV 就可以直接从 SVTable 中读取值，而无需下次搜索
• 本质就是读操作拿到了地址信息之后才会更新索引 LSM 中的 KP 信息。

故障恢复

• 为了从崩溃中恢复，NovKV 使用一个清单文件来记录所有有效的数据文件(包括 VTables、SVTables 和当前 VTable)，并使用一个恢复文件来记录恢复点

• 当从崩溃中恢复时，NovKV 首先读取清单文件并重新构建 VMap、SVMap 和当前 VTable 指针。然后，NovKV 读取恢复文件，从 VTables 中读取前一个恢复点之后的所有 KV 项，并将所有这些键和值句柄重新插入到 KStore

• 正如III-A中所描述的，在返回写结果之前，NovKV 中传入的 KV 项首先被附加到当前的 VTable 中，这确保了写操作只有在 KV 项被成功持久化的情况下才能成功返回。因此，在写入过程中程序崩溃不会丢失任何数据。

• 由于租户使用 DropKeys 来丢弃过时的 KV 项，而不是查询 KStore，如果 KStore 已经丢弃的密钥丢失，将会留下一些过时的 KV 项，永远不会被丢弃。

• 因此，NovKV 在 KStore 压缩过程中写入 dropkey。如果在 dropkey 被持久化之前发生崩溃，KStore 压缩也是未完成的，在故障恢复后将被清理。因此，这些 dropkey 可以在下一次压缩中再次收集。此外，只有当本次垃圾收集运行中的所有文件都被成功收集，并且清单文件的新版本被成功持久化时，VMap 和 SVMap 中相应的文件指针才会被替换。因此，在压缩和垃圾收集期间程序崩溃也不会丢失任何数据或破坏一致性

Evaluation

• 小 KV 的时候，NovKV 要远好于 WiscKey，随着 value 的增加，与 WiscKey 之间的差距减小，表明：WiscKey 垃圾收集期间的插入与面向用户的插入竞争 KStore 的写空间。因此，由于避免了插入，NovKV 可以实现比 WiscKey 更高的吞吐量
• 还是没解释为什么 value 变大之后，与 NovKV 类似

• 读没什么差距，测试两次，第一次可能会更新指针，第二次就完全不需要了
• 更新指针开销比较小，所以第一次和 WiscKey 差不多
• 在第二次读的时候，本方案好很多说明 WiscKey 中的 GC 对 KStore 的性能产生了影响
• value 比较小的时候，NovKV 效果更好，因为这时候读取操作中读取 VStore 中更大的 value 占据了读操作的大部分开销，KStore 的影响就没那么大了，但是 NovKV 使用了有序的结构，是缓存更友好的

写放大

• 在 wisckey 的垃圾收集中大量插入 KStore 会导致比 NovKV 更多的 KStore 压缩。相比之下，NovKV 在垃圾收集期间不插入值句柄，因此 NovKV 中压缩的写量几乎保持相同。因此，wisckey 需要比 NovKV 做更多的数据重排，这导致了更高的写放大。

• NovKV 使用了一个贪心的 valid_rate 方法，使得 NovKC 的 GC 开销小于 WiscKey，使得 NovKV 可以比 WiscKey 执行更多的 GC

GC 的影响

• 有无 GC 对于 NovKV 影响比较小，WiscKey 受影响比较大

• 因为 NovKV 相比于 WiscKey 有一些额外的操作，所以在没有 GC 的时候表现不如 WiscKey