PinK: High-speed In-storage Key-value Store with Bounded Tails

  • 该篇文章来自于 ATC2020 Best Paper PinK: High-speed In-storage Key-value Store with Bounded Tails
  • 论文其实是基于一种新的 KV 存储形式 KV-SSD 开展研究的,KV-SSD 近年来常被提及,未来可能作为一种新型存储器件在键值存储系统中使用。
  • 本文的工作主要实现了基于 LSM-Tree 的 KV-SSD,和基于哈希的 KV-SSD 进行了对比。

Abstract

  • KV 存储的实现主要有 LSM-tree 和 HASH 两种,但相关学术研究和工业应用中 LSM Tree 因为支持更多的操作以及更好的写性能,相比于 HASH 更受欢迎。但是,在资源有限的 KV-SSD 环境下,LSM-tree 很难实现,故 KV-SSD 的环境下常常使用 HASH 实现。
  • 我们提出了 PinK,一种基于 LSM-tree 实现的 KV-SSD,相比于基于 HASH 实现的 KV-SSD,99th 尾延迟降低了 73%,平均读延迟增加了 42% 但吞吐量提升了 37%。
  • 在资源受限的环境下提升 LSM-tree 的性能的核心思想是 避免使用 BloomFilter,使用少量的 DRAM 来 keep/pin LSM-tree 的顶层数据。

Introduction & Background

KV Store

  • 应用广泛

现有的优化方案

  • Algorithm:
    • ATC19 Best Paper - SILK:通过调度 compaction 和带宽分配来集中优化 write 长尾延迟
    • SIGMOD18 - Dostoevsky:控制 merge 频率在 tiering、leveling 和 lazying leveling 几种不同策略下转换以适应不同的workload
    • SIGMOD17 - Monkey:对每一层的布隆过滤根据数据规模的大小分配不同的内存空间,从而最小化所有层布隆过滤的假阳率。
  • System:
    • VLDB10 - FlashStore:内存维护 HashTable 索引,使用签名代替 Key,CuckooHash 解决冲突,KV 以日志结构形式存储,使用 Flash Memory 作为非易失缓存
    • FAST16 - WiscKey:KV 分离,Key 存 LSM-Tree,Value 存 Log
    • Eurosys14 - LOCS:
  • Architecture:
    • VLDB16 - Bluecache:基于闪存的分布式KV Store系统,使用了 FPGA

NAND Flash-based SSD

  • SSD 的具体结构请参考其他博文。eg.
  • 一个比较关键的点,也是本文涉及到的点:FTL 中维护了由 LBA 索引的映射表,对应地指向响应的 flash page。映射表保存在 SSD 控制器 DRAM 中,DRAM 大小通常为 SSD 容量的 0.1%。映射表需要持久化,所以会使用到 SSD 内置的电容来防止突然的断电故障。

KV-SSD

  • 近年来学术和工业界都在考虑将 KV 存储的相关功能从软件层面转移到硬件存储设备层面。
  • 为什么要引入 KV-SSD?传统的 KV 存储不能完全发挥新型存储器件的性能,如很多支持 NVMe 的设备,结合之前 SOSP19 的一篇论文 [2],发现 KV Store 的 bound 已经从磁盘转移到了 CPU,故考虑引入 KV-SSD 来降低 KV 存储对 host 侧的 CPU 和 DRAM 的高占用率,同时减小 I/O 延迟并提高吞吐量。
  • KV SSD 支持的接口对应的规范:全球网络存储工业协会发布的 https://www.snia.org/tech_activities/standards/curr_standards/kvsapi
  • 设计实现 KV-SSD 的两大挑战:有限的 DRAM 资源和有限的 CPU 资源

工业界

  • Samsung KV-SSD:直接处理 KV 请求,参考文献 [1]。通过简化软件存储堆栈和合并冗余,KV-SSD 提供了更好的可伸缩性和性能,从而降低了总体 CPU 使用量并将内存释放给用户应用程序。

学术界

  • ASPLOS19 LightStore: Software-defined Network-attached Key-value Drives:使用 LSM-Tree 实现协议转换,并实现了和数据中心网络直连
  • KAML: A Flexible, High-Performance Key-Value SSD 实现了内部事务处理、更细粒度的锁和和缓存层
  • Towards Building a High-performance, Scale-in Keyvalue Storage System.
  • NVMKV: A Scalable and Lightweight Flash Aware Key-value Store
  • Bluecache: A Scalable Distributed Flash-based Key-value Store

HASH-Based KV-SSD

  • SSD DRAM 中维护一个 hashtable, hashtable 有很多个 buckets,每个 bucket 对应的保存了元数据(key 和指向 value 的指针)。假设 Key 为 32B,Value 为 1KB,假设 4TB 的 SSD 中的 bucket 数量为 2322^{32},即 4TB 全部用于存 1KB 的 Value,那么实际对应需要 DRAM 大小为 36B232=144GB36B * 2^{32}=144 GB 才能装下对应的 HashTable,但是按照之前的 0.1% 的计算逻辑来看,最多提供 4GB DRAM。显然是不够的。
  • 为了降低 DRAM 使用率,可以使用哈希签名来代替 KEY,实际的 KEY 和 Value 一起存储在 flash 中,即便是使用 16bit 的签名还是需要 24GB 的 DRAM,且可能产生签名冲突。所以只能保存部分热数据索引到 DRAM 中,剩余部分需要保存在 flash 中,但是引入了额外的 flash 读取开销。

现在的 KV-SSD 存在的问题

  • 从现如今的 KV-SSD 表现出来的效果来看,在尾延迟和吞吐量方面表现都是 inconsistent (注:至于这个 incosistent 怎么理解,可以看后文的具体描述,大胆猜测一下应该是类似于 unpredictable 的意思
  • 现在的 KV-SSD 主要都是基于 HASH 实现的,因为 HASH 实现起来相对容易,但是也就带来了一些局限。基于 HASH 实现的 KV-SSD 主要是在对应的磁盘控制器(DRAM)中维护了一个 HashTable,相应的操作本质就是查表以及对表的管理,但是由于 KV-SSD 的 DRAM 容量有限,数据量大的时候肯定会有部分数据需要放在 Flash 上,简单快速的 DRAM 内查表工作就可能退化成开销较大的访问 FLASH 的查表,同时还需要实现比较复杂的空间管理机制(何时访问 FLASH 进行空间置换,诸如此类)。如果产生了 HASH 冲突,可能就需要访问很多次 FLASH,导致长尾延迟以及吞吐量的下降。
  • 光纸上谈兵不行,做个实验:4TB KV-SSD prototype (KV-PM983),KV pools 从 1GB 到 3TB,平均大小 Key-32B,Value-1KB,3TB 的池对应就可以有 30 亿个 KV。负载 KVBench 10 分钟随机 GET(期间无 GC)。对比测试,对照了使用 4TB Block SSD 和 FIO 测试。
20200807105934
  • 实验结论:在基于哈希的 KV-SSD 实现中,随着存储的 KV 对总数的增加,性能和尾延迟会变得更差,还不如 Block SSD 稳定。(分别测试了 CDF 累积分布函数和吞吐量)
  • incosistent 的性能表现可能是因为低效的 HASH 冲突解决策略引起的。可以考虑使用最坏情况下常数级的查询的哈希冲突解决策略,如 Cuckoo Hash, Hopscotch 等,来避免长尾延迟,但是这种好处是以降低写入速度和/或频繁重复哈希为代价的。且 HASH 不支持 range query。
  • 性能随着容量的增加显著下降的原因主要是 DRAM 容量的限制导致索引数据太大,不得不频繁访问 Flash

解决方案

  • 从 DRAM 资源有限的角度来考虑,LSM-tree 提供了更好的性能。
  • 在 KV-SSD 中比较常用的 LSM-tree 实现为 LightStore [ [3]] 和 iLSM-SSD [4]
  • 考虑使用 LSM-tree 替代 HASH,因为 LSM-tree 需要使用的 DRAM 更小,对范围查询的支持也较好。但是实验显示,使用了常见的 LSM-Tree 实现的 KV-SSD 并没有表现出预期的效果,在有些场景下甚至比 HASH 性能还差。
  • 测试结果,如图所示。
    • 没有 BloomFilter,LSM-tree KV-SSD 显示出了比 BlockSSD 更高的延迟。
    • 使用 BloomFilter 会显著降低读的层级数,平均进行一次 flash 上的 page read 就可以读取到数据,读延迟比不带 BloomFilter 更好,但是尾延迟更严重(因为概率性的数据结构导致大约有 1.4% 的读操作会需要超过一次的 flash lookup)。
    • YCSB-C 的负载下,吞吐量的表现上,带 BloomFilter 的 LSM-tree KV-SSD 不到 Block-SSD 的一半(因为为了获取KV索引来为GET()服务, Monkey 需要两次 flash 读取)。
    • YCSB-Load 负载下,吞吐量严重下降,主要是因为 GC 产生了影响。我们发现为 GC 移动有效页面涉及到 LSM 树维护的 KV 索引的级联更新。
    • CPU 的开销,重建 BloomFilter 的开销占据了很大的比重。
      20200807160924
通用的 LSM-tree 方案存在的问题
  • 尾延迟: 虽然很多 LSM-tree 实现都使用了 BloomFilter 来改善平均读延迟,但因为 BloomFilter 是概率型数据结构,对于最差的情况下的尾延迟还是没有办法改善,就会出现和 HASH KV-SSD 一样的长尾延迟的情况。
  • 严峻的写放大: LSM-tree 本身的问题(压缩会导致 GC,GC 导致更多的 I/O,加剧写放大),应用在 KV-SSD 中可能还会加剧 FTL 的 GC 开销。
  • CPU 占用率高: 这个也是 LSM-tree 本身存在的问题,现在用于 KV-SSD,本身存储设备的处理性能就有限,LSM-Tree 的 filter rebuild 以及 KV 对的压缩排序都需要花费大量的时钟周期,很容易导致 KV-SSD 的控制器处理单元过载,从而显著影响 I/O 性能
本文的方案
  • Pink:核心思想为 level pinning,即通过将 top levels 的键值索引 pin 到 DRAM 中来代替 BloomFilter (注:看着是不是很懵,可能直接看设计部分好点,但就暂时理解为 DRAM 里放了个索引来代替了布隆过滤器吧)
  • 因为没了 BloomFilter,使用了 DRAM 内的索引,带来了两个直接的好处:延迟变得 predictable;减少了资源占用。
  • 其他优点主要体现在:
    • 压缩过程减小了对 flash 的 I/O,因为 DRAM 索引排序不需要 I/O 操作,且该索引由内置的电容来保证持久性;
    • 可以批量延迟更新 DRAM 中的 LSM-tree 索引,从而减小 GC I/O 次数;
    • 添加硬件比较器来参与 sort 操作,而无需 CPU 介入,减小 CPU 开销。
  • 注:这儿可能看着还比较抽象,等着看下文的详细设计部分吧

Design

Data Structure

20200807170301
  • DRAM:a skiplist 和 level lists (由 SSD 电容保护)
    • skiplist:类似于 write buffer,通常配置的很大以便充分利用 NAND channels 的并行性来向 Flash 刷入数据。对应包含数据 <key size, key, value size, value>
    • level lists: 每一层被组织成为了具有确定大小指针对组成的数组,第一个指针指向 meta segment 在 flash 中的物理位置,第二个指针指向对应 meta segment 的开始 key。所以 meta segment 的起始 key 被单独存储在了 DRAM 中,
  • FLASH:meta segments 和 data segments
    • skiplists 满了之后,元数据和数据分离,刷入到 Flash,元数据包含指向对应数据的指针,数据段中存储了 KEY 以及 Key Size 便于 GC。元数据段大小被固定为 flash page size,但数据段可以是任意大小
    • meta segment: 由一组 <key, pointer> 组成,按 key 排序,加上一个 header,key 大小可变 16B-128B,,为了利用二分查找,所以维护了 <key, pointer> 的起始位置在 header 中。
      20200807163318
  • 和 HASH 相比,PinK 需要使用的 DRAM 更少

Improving I/O Speed with Level Pinning

  • 缓解读延迟:最差的情况下,PinK 需要 O(h1)O(h-1) 的 flash 查询,为了防止这种情况, PinK 采用了 Level pinning 来代替布隆过滤器,简单粗暴地可以理解如果 LSM-tree 有 h 层,PinK 直接把 top-k 层对应的 meta segments 给放在 DRAM 中。对于读操作,首先看 DRAM 中的 top-k 层有没有该 Key,没有再访问 flash。此时最糟糕的情况下的复杂度降低为 O(hk1)O(h-k-1)
  • Level-pinning 内存需求:假设 4TB SSD,共 5 层,可以根据 SSD 中 DRAM 的大小来考虑实际需要缓存多少层 meta segement。
  • 减少压缩 I/O:因为 meta segment 被缓存在内存中,所以可以直接更新,且不用刷回,因为有电容保护。

理解

20200807163318
  • 图 5 表示了压缩后的数据布局。假设 L1 被固定到了 DRAM,在 L0 刷回之前,首先从 L1 中找到相应的 meta segments(读次数 - 1)。即图示中的 Page 0,然后进行归并排序,从而得到两个有序的 meta segments,这两个 meta segments 再相应地刷到 L1(写 - 2)(即图5 中的 Page 3 和 4)。相应地更新 level lists。然后发现 L1 层满了,那么需要刷回到 L2,这时候读取 L1 和 L2 的各自两个 meta segments(读 - 2)(即图 5 中的 Page 1~4,其中 Page 1 和 2 来自 L2,Page 3 和 4 来自 L1),归并排序后然后写到 L2,得到对应的 Page 5~7。
  • 因为 L1 被固定在 DRAM 上,所以省略了对 L1 的三次 flash 读和两次 flash 写
    20200925110938

Optimizing Search Path

  • 假设 L1L_{1} 层有 N 个 entries,层级之间容量比为 T,因此 Lh1L_{h-1}NTh2N * T ^{h-2}。计算最坏的时间复杂度为 O(h2log(T))O(h^2 * log(T)). 带 BloomFilter 的 LSM-tree 实现对应的复杂度可能更小,因为能够跳过一些不必要的二分查找。
  • 为了减小查询的开销,PinK 使用了两个技术:
    • 一个是减少字符串比较的开销,通过使用 key 的前缀,level list 的每个条目都有两个指针,每个指针指向一个 meta segment 和一个 start key string,我们还包含了前缀(即 start key 的前四个字节)。二分查找时,首先比较前缀,只有匹配了才会匹配整个字符串。
    • 通过借用分级级联技术来减少 level list 的搜索范围。level list 的每一个 entry 都会再有一个 4-byte 指针,称之为范围指针,该指针指向下一层的最大的起始 key 但是小于或等于当前 entry 的 key 的位置。例如,在 L1L_1 中找到了一个 entry eL1ie_{L_1}^i,如果该 entry 指向的 meta segment 不包含匹配的 KV index,那么将会寻找下一层,eL1ie_{L_1}^i 将成为 L2L_2 层搜索的下界, 而 eL1i+1e_{L_1}^{i+1} 对应的 range pointer 将成为搜索的上界,从而缩小搜索的范围。复杂度变为 O(logT)O(logT),因此平均时间复杂度降低为 O(hlog(T))O(h * log(T))
      20200807210308

Speeding up Compaction

  • 虽然减少了压缩对应的 I/O 次数,但是在压缩过程中的排序操作仍然需要计算资源的开销。考虑使用 HW accelerator(硬件加速)来缓解主机端的压力。HW 加速器放置在闪存和主机数据总线之间,可以很容易地合并两个位于闪存的 level,因为两个 level 的 meta segment 能够从 flash 中以速度较快的流的形式进行传输。该加速器写合并后的 meta segments 时不需要 CPU 的介入。硬件加速器的引入不仅减小了计算的开销,同时提高了 I/O 总线的利用率,因为不再需要以前那样的 等待合并的以及合并后的数据传输。
  • 如图所示工作流程,PinK 软件首先请求加速器来执行压缩,并提供两个 level 的 meta segments 地址以及合并后写回的 mete segements 地址。flash request generator 会进行调度等待多个读请求以便充分利用 flash 带宽,由于不同 flash 通道的数据包是交错的,我们需要为每个 level 使用每个通道的 reorder buffer 来序列化 meta segment。序列化之后送入 compaction engine,本质是个比较器进行归并排序,将比较后的更小的数据以输出流的形式,使用了小的 write buffer,最终输出到写回地址中,当两个 key 相等的时候,上层对应的数据因为最新将取代另外的数据。操作完成后,将使用了的 meta segments 页号返回,从而由上层决定回收哪些未使用的空间。
  • 对于 pinned levels 的合并是有一个类似的机制,只是使用了 DMA 代替 flash request generator,以及交互的不是 flash 而是 DRAM。
    20200808111314

Optimizing Garbage Collection

  • 压缩会产生两种垃圾数据:
    • 一种是老旧的 meta segment,当执行压缩时,PinK 写新的 meta segments 数据来替代老旧的数据,如下图所示的 pages 0,1,2。
    • 另一种是过期的 KV 对象,该对象被更新了或者被客户端删除了都变成过期对象,过期对象的索引在压缩过程中会被直接丢弃,所以将没有 meta segments 指向。但是数据部分仍然存储在 data segments 中。
      20200808113340
  • 为了擦除老旧的数据,PinK 将在空间接近枯竭的时候触发 GC,选择一个 flash block,将其中的有效数据拷贝到空闲空间,然后擦除整个块。因为冷热分离的原因,meta segment 通常和 data segment 位于不同的块,PinK 通常针对不同块类型采用不同的 GC 策略。

GC for Meta Segment

  • 读取页对应的起始键,然后查询 level list 中是否有 entry 指向该键,如果没有则说明是老旧的 segment,直接跳过,如果有则需要将该页迁移到空闲页,然后对该 entry 的更新也将定位到新的页。清理 meta segment 的开销较小,因为只涉及到有效页的拷贝以及 DRAM 中对 level list 的更新。

GC for Data Segment

  • 从选出来的块中扫描一个 data segments,需要将 value 对应的键提取出来,利用 key 才能查询到 level lists 并找到 meta segments,才能检查该 value 的有效性,如果一个 meta segment 没有被 pin 到 DRAM 中,就必须从 flash 中去读,从而可以收集到很多的有效 values。
  • 最简单的方法就是 WiscKey 的垃圾回收思想,收集有效的然后拷贝,然后整块擦除,对应 value 的 meta segment 也需要更新并刷回,从而指向新的位置。如果被 pin 到 DRAM 里了,则不需要写 flash。这种方法会造成会多对 flash 上的元数据更新,其次就是对于一些很久以前写的数据,压缩之后,很有可能一个 meta segment 中包含的对象不在同一个 value segement 或者 block 中,即可能只有很少的 value 被拷贝,但是却要更新对应的 meta segment。
  • 所以 PinK 采用了延迟写的方式,把有效的 KV 再写到 L0,然后擦除整块。垃圾数据静待回收,但是对原有有效数据的访问将被更高 level 处理,即不进行元数据的更新,全部交给 GC,虽然增加了 compaction 开销,但是减少了 mete segment 的更新,因为有效的 KV 对应的元数据被重新整合到了一个 meta segment 中。
  • GC 过程中会把有的数据放在 L0 层会一定程度上地影响读延迟。

Durability and Scalability Issues

Durability with Limited Capacitor

  • 前面我们默认了使用 SSD 里的电容来保证 SSD DRAM 里的数据不丢,但其实很多 SSD 没有足够的电容来保证 DRAM 里的所有元数据,此时就会有持久性的问题。可以通过将 DRAM 中的数据结构写入 flash 中来解决。L0 的数据可以在处理请求之前写入日志,即写前日志;在执行压缩之后,level list 和 pinned levels 会变成脏数据,需要被持久化到 flash。
  • 无论是写前日志还是脏数据刷回,在 HASH-KV-SSD 中一样需要处理,但是在 LSM-tree-KV-SSD 中可能刷回操作的开销更小,因为写性能 LSM-tree 更好。

DRAM Scalability

  • 我们一开始就假设了 SSD 的 DRAM 容量会随着 flash 的容量的增加而增加,但是 DRAM 的容量增长速度比 flash 要慢,所以可能就没把所有的 levels 给 pin 在 DRAM 中,即只能 pin 部分 levels,相应地也就会增加最坏情况下的查询开销,但即便是最坏情况下,也比使用 HASH 的 KV-SSD 或者使用通用 LSM-tree 的 KV-SSD 表现要好。
  • 另外可以考虑减小树的高度,即让除了最后一层以外的上层结构都放在 DRAM 中,虽然会因为压缩开销的增大一定程度上牺牲写性能,但是能在最坏的情况下将查询复杂度限制在 O(1)O(1)

Evaluation

  • 器件:FPGA-based SSD platform with quad-core ARM Cortex-A53 (Xilinx ZCU102)。即使用 FPGA 做硬件加速
  • 负载:YCSB
  • 对比:HASH-KV-SSD, LightStore-KV-SSD, W/O HW PinK

分析

  • 吞吐量显然 PinK 更高,以及 HW 的引入相应地带来了提升。对于有很多写操作的工作负载,PinK 的这些好处是显而易见的,对于读比较多的,就没什么提升。纯粹的 LSM-tree 相比于 HASH 在写敏感负载下表现更差,反而在读上表现更好。
    20200808143557
  • PinK 大幅减小了 flash 的读次数,压缩对应的 I/O 次数也比原始的 LSM-tree 小了很多
    20200808143609
  • 延迟测试情况
    20200808144531
  • 查询优化效果,ALL 是指既包含 range 指针又包含前缀匹配。效果比未优化的 PinK 肯定好很多,但比起 LSM-tree 其实只有尾延迟有一些改善。
    20200808144726
  • 垃圾回收:优化之后效果比 PinK 好很多,甚至比 HASH 还要好
    20200808145136
  • 写延迟和高度的关系:PinK 的读延迟更稳定
    20200808145333

Conclusion

  • PinK: 基于 LSM-tree 的 KV-SSD
    • pinning top level indices 改善了读延迟
    • 使用 HW accelerate 显著减少了压缩的 I/O 次数
  • 未来考虑在 RocksDB 这种通用的 KVS 中贯彻 pinned levels 思想,但可能需要借助 Persistent Memory 来保证主机端的持久性。

References