ChameleonDB: a Key-value Store for Optane Persistent Memory

• 该篇文章来自于 EuroSys2021 - ChameleonDB: a Key-value Store for Optane Persistent Memory

Abstract

• Optane DC PM 的出现使得利用其高带宽和低延迟构建持久性 KV 存储成为了热点。Optane Pmem 本质上是一种具有两个不同属性的混合存储设备，这是Optane Pmem面临的一个主要挑战。
  • 一方面，是一个高速的字节寻址的设备，类似于 DRAM
  • 另一方面，对 Optane 的写操作以 256bytes 进行，更像一个块设备。
• 现有的基于持久性内存的 KV 存储设计没有考虑到后面的因素，导致出现了较高的写放大以及受限的读写吞吐量。与此同时，直接重用原有的为块设备设计的 KV 存储，如 LSM，也将因为字节寻址的特性而导致更高的读延迟。
• 本文中我们提出了 ChameleonDB，一个考虑且利用了 PM 的两个特性的基于混和 内存/存储 场景的设计。使用 LSM Tree 以低写放大率有效地接受写入，且使用了一个 DRAM 中的 HASH 表来 bypass LSM 的多层结构从而快速读。与此同时，ChameleonDB 可能选择在后台维护LSM多级结构，以在系统崩溃后实现较短的恢复时间。ChameleonDB 的混合结构被设计成能够吸收写负载的突发写入，从而避免长尾延迟。

Introduction

• 现有的 KV 存储设计在 PM 场景中面临主要三个挑战：

Challenge 1: Optane Pmem is a Block Device

• 在 PM 发布之前就有大量研究人员提出了该设备场景下的 KV 存储。这些设计都假设 PM 是一个稍微慢一点且持久的 DRAM，相应地，这样的设计通常构建一个持久化哈希表或持久化树来索引存储日志中的 KV 项。当新的KV项目按照到达顺序批量写入日志时，索引上的相应更新(通常)在非连续的内存位置单独进行(由哈希函数或树结构确定)。
  • HASH:
    • Level hashing
    • CCEH
  • tree-structured
    • WB+ Tree
    • FAST&FAIR
• 不幸的是，这些前面的假设和最终商业 PM 相关性能特性的研究表现不一致。
• 据报道，Optane Pmem的写单元大小为256B，为了理解这种性能特征的含义，我们将特定大小的数据写入与256B单元大小对齐的随机选择的地址。在实验中，我们将写大小从8B改变为128KB，并使用不同的线程数，以便能够达到内存的峰值带宽。测试结果如下所示，当写大小小于 256B 时，写吞吐量比256B及其以上的写吞吐量要小很多，更有意思的是，256B 的吞吐量几乎是 128B 的两倍，128B 又几乎是 64B 的两倍，这强有力地证明了设备 256B 访问单元的特性。任何非连续的小于该大小的写入都要进行一个 RMW 读后写的操作来生成一个 256B 的写，从而导致写入放大和并减少了有效的内存带宽。
  
• 这样的特性造成之前基于假设的 KV 存储的设计遭受了写性能的损失，原则上类似于对其他块设备(如机械硬盘和 SSD)的小写操作。特别的是，利用持久性的 HASH 表以及树结构的 KV 存储，在 key 插入、rehash、rebalance等过程中每个对索引的更新都是小写操作，比如 16bytes，远小于 256byte，此时写的放大高达 16。由于没有充分考虑设备的写单元，这些设计无法提供高写性能。

Challenge 2: Optane Pmem is of High Speed

• 有大量的工作都是在解决基于块设备的 KV 存储中的小写问题，如 LevelDB/RocksDB/Cassandra/LSM-trie/PebblesDB 都是学术界以及工业界中的例子。他们聚合了最近的更新操作并批量顺序写这些数据到磁盘，根据 key 比较的结果或者hash函数的结果。由于维护一个大的已排序列表的开销太大，所以要维护多个和指数级长的已排序列表。每个列表位于其单独的 level，从 L0 开始是最短的列表，每个 k+1 层 level 都有着 k 层的 r 倍容量。r 的值在不同的 KV 存储中不同，例如 LevelDB/RocksDB r=10，LSM-trie r=8，在 KV 项被写入到存储之后，初始在 L0，然后向下移动直到最后一层。
• LSM 树结构有两种主要的压缩方案，它们对写放大和读性能有不同的影响。leveling 和 size-tiering。
  • leveling: 在相邻两层的 KV 项被归并排序然后重新插入到更下面的一层。随着下层的 Key 的个数达到了上层的很多倍之后，每个压缩的写入放大倍数可以大到10(以LevelDB为例)。
  • size-tiering: 每一层包含多个具有重叠的键范围的子 levels，在子 Level 之间进行键的归并排序操作，结果将被写入到更低一层的新的子 level 中。这样的话，该压缩的写入放大总是为 1。确实该策略可以显著减少额外的写操作，但也会显著增加子 level 的个数，然后增加了在存储中查询一个 Key 的开销。
    
• 而基于 LSM 的设计似乎是在Optane Pmem上部署的一个很好的候选方案，它为块设备设计了内置的多级结构，不幸的是，它与Optane的高读性能不兼容。因为它的多层设计，读一个 Key 需要检索很多层，从 L0 开始，直到这个 Key 被找到或者找到最后一层都没找到这个 Key。我们的目标是每次搜索 Key 只有一个磁盘读取，在 DRAM 中为每个 KV 项所在的块维护了 BloomFilter，从而在从该层读取磁盘上的数据之前先判断是否该 Key 存在于这个 Block 中。相比于毫秒级别的磁盘访问时间，对于 filter 的纳秒级的操作几乎可以忽略。只要实际只发生一次磁盘读取，这样的设计就能在磁盘上的 KV 项上实现最好的读取延迟。然而，当存储设备是Optane Pmem 时，情况就大不相同了，它的读延迟本身是纳秒级的，只有 DRAM 读延迟的3倍左右。
  
• 为了理解 Optane 高速访问的影响，我们选择构建了一个基于 HASH 的 KV 存储， 7 层 LSM-trie，分别在 SATA SSD、PCIe SSD 和 Optane PMem 上。在不同的层级上读取 Key 并报告其读延迟，如下图所示。 从表中读取项的时间(在图中表示为“Table read”)是高度一致的，无论键驻留在哪个级别，因为只需要读取一次磁盘(或Pmem)。如图2(a)和2(b)所示，当存储在 SSD 上运行时，花费在过滤器(在图中表示为“Filter Check”)上的时间只占很小的一部分。因此，在 Bloom flters 帮助下的磁盘上的 KV 存储，使用多层次结构不会损害读性能。然而如图 c 所示，当 Optane Pmem 使用的时候，花费在过滤器上的时间就变得很长，相比于 Pmem 的读取时间。KV 对在较低的层级时，它不断增加，最终成为不可接受的。这个观察结果表明，多级结构成为实现稳定的的低读延迟的主要障碍。同时，同样的结构对于允许批写以适应块设备也是必不可少的

Challenge 3: Optane Pmem is Non-volatile

• 为了避免前面提到的挑战，研究者已经提出了当 Pmem 仅用于存储KV项作为存储日志时，将索引结构移动到 DRAM 上。因为 KV 项批量写到日志中没有任何写放大，然后所有的索引的读和更新都发生在 DRAM 上，这样的设计提供了高吞吐和低延迟。（索引位于 DRAM 上）
  • ASPLOS’20 FlatStore
  • FAST'19 uDepot
  • SOSP'19 KVell
• 然而，让整个索引或者绝大部分索引都在易失的内存中就一定程度上消除了 Optane Pmem 作为持久性内存的优势，Pmem 本身就是承诺快速故障恢复的介质。对于一个存储了几十亿的 KV 对的 KV 存储，DRAM 中的索引可能占据的空间超过 100GB，而且有限的 DRAM 空间本身就是被多种系统和应用共享，一旦索引数据在丢失，从存储日志中重建这么大的索引是会花费特别长的时间的。与此同时，快速的恢复和重启是很重要的，特别是在虚拟化的环境中，一个 KV 存储可能宿主在虚拟机或者容器中，这些虚拟机容器本身的启动时间就只有几秒甚至不到秒的级别。所以把最近的对于索引结构的更新周期性地保存在 PMem 中，并使Pmem上的索引有组织并可以很快使用 对于 LSM Tree 的设计是非常有用的。
• （目标：利用 PMem 进行快速故障恢复，减少 DRAM 消耗，主要是快速构建索引）

Summary

• in-DRAM index
  

Solution

• 虽然现有的KV存储设计不能同时实现Optane Pmem上期望的多个目标(高写吞吐量、低读延迟、高动态工作负载下良好的读尾延迟、小DRAM占用空间、快速恢复和重启)，但我们提出了一个KV存储设计，名为ChameleonDB，可以在一个系统中实现这个目标。为了证明 ChameleonDB 的实力，下图中和基于 HASH 位于 Pmem 的索引存储以及基于 HASH 位于 DRAM 的索引存储进行了相应的四个性能维度的对比。和写吞吐高度相关的写放大，读延迟，内存占用，恢复时间。
  • PmemLSM 对应传统的带有 Bloom 过滤器的 LSM 树状 KV 存储设计，它有很长的读延迟。（因为 LSM 和布隆过滤器）
  • DRAM_HASH 对应内存中维护索引，PMem 中维护日志，会有比较大的内存占用和很长的恢复时间。（因为内存 HASH 表内存占用，索引重建开销大）
  • Pmem-Hash 对应了持久的 HASH 表设计，会有比较大的写放大，相应地导致较低的写吞吐。（因为 HASH 操作均为小写，基于 PMem 的特性，存在写放大）
  • 相反，ChameleonDB 在四个维度都表现得很好。
    

Contribution

• 我们分析了现有的在 PMem 上构建的 KV 存储设计的缺点，证明了他们中还没有方案可以同时实现低读延迟、低 DRAM 消耗、快速重启以及高吞吐。特别的，我们揭示了在Optane Pmem上部署基于LSM 的 KV 存储的困境，据我们所知，这尚未在开放文献中进行讨论。
• 我们提出了 ChameleonDB，一个新的为 PMem 设计的 KV 存储，一定程度上讲，该设计是一个混合设计。利用了其中一个存储(pmems-hash、pmems-lsm 和 dram-hash)的各自优势来解决其他存储可能存在的问题。特别的，使用了一个多层的结构来高效地持久化索引上的更新操作，使用了一个内存中的 HASH 表来加速小规模的最近更新的索引的读操作，然后使用了在 Pmem 上的哈希表来遍历存储中的大部分 Key，它还提供了一种操作模式，用于减少长读尾延迟。
• 我们实现了 ChameleonDB 并进行了测试对比，和其他几种结构的最先进的方案进行了对比。实验表明 ChameleonDB 成功地同时实现了前面提到的目标，且和其他存储相比要在一个或者多个维度上表现得更好。

Design

• 整体结构

  • KV 分离
  • HASH 分区
  • DRAM-NVM 混合索引
    

• ChameleonDB 是一个 Value 存储在存储日志上的 KV 存储，同时 keys（或者他们的 hash 值）以及对应值的地址信息被存储在相应的持久性索引中，如下图所示。
  

• KV 项根据请求到达顺序被批量写入到 Value Log 中，持久性索引是一个有多个 shards 的高度并行的结构，每个 shard 有自己的多层结构以及自己的 compaction 操作。Keys 根据相应的 hash 值分布在这些 shards
  

A Multi-shard Structure

• ChameleonDB 的索引被组织成多个 shard 的结构，每一个 shard 覆盖了相等范围的 HASH key space。一个 shard 是一个多层的类 LSM 的结构，如下图所示。
• 每一个 Level 会有很多个子 levels，被称之为 tables，每一个又被组织成固定大小的 hashtable，使用线性探测的方法来解决 HASH 冲突。和其他基于 LSM 的 KV 存储一样，每个 shard 有一个内存中的 Memtable 来聚合 KV 项。当 Memtable 满了之后，即负载因子达到了阈值，这时候执行刷回，从 DRAM 到 PMem，最终在 Pmem 上组织成持久的不可变的 L0 level 上的 Tables。每一层能够容纳的最大的 Table 数量是由层级之间的比例系数 r 来确定的，除了最后一层只包含一个 Table。下图所示的例子中的 r 为 4，因此在有四个 Memtables 被 flush 到 Level0 之后然后变满，从而触发 Compaction
  
• Leveling 和 Size-Tiering 两种策略各有优缺，ChameleonDB在不同的LSM级别上使用这两种压缩方案来提供低写放大和低读延迟。在每一个 shard，size_tiering 主要用于压缩上层，就是在 PMem 上的除了最后一层以外的层次，leveling compaction 用于压缩最底层。这种混合压缩策略在 SIGMOD’18 的 Dostoevsky 中也有应用被称之为 lazy leveling，在写放大和读延迟之间达到平衡，并且比单独使用两种方案中的任何一种性能更好
• 基于 LSM 的 KV 存储的 Compaction 的策略通常都是在两个相邻的层次之间进行的。以如下所示的图中的例子来说，L0 满了触发到 L1 的 compaction，然后级联 compaction 触发到 L2 的 compaction。
• 在 ChameleonDB 中，我们引入了 Direct Compaction 算法通过允许在多个 levels 之间进行 compaction 而减少了压缩开销。为了完成如下图 a 所示的 compaction，Direct Compaction 首先触发了一个包含 L0,L1,L2 的 compaction，如图 b 所示。同样地，最后一层的 compaction 会在 L0 满且上层 level 都有 r-1 个 tables 的时候执行。在 shard 执行了最后一层的 compaction 之后，shard 上层的所有表都被清除因为其数据项已经被移动到了最后一层。
  
• 随着单个 shard 中每个 table 的大小（包括内存中的 Memtable）超过了 256B（PMem 的访问单元），需要按照 256B 大小进行对齐，flushing/compacting table 可以完整利用 PMem 的写带宽，解决了前面描述的第一个挑战。在此之后，每一次 flush memtable 之后，ChameleonDB 持久化 LSM 数据结构的修改，故障恢复只需要重启恢复没有持久化的 Memtable 数据，从而解决挑战三。

The Auxiliary Bypass Index (ABI) in a Shard

• 因为每一个 shard 是一个多层的结构，一个 get 操作因为需要一层一层检查 tables 直到找到目标的 Key 或者到达最后一层，会有比较严重的读延迟，如下图 a 所示。因为 ChameleonDB 在上层使用了 size-tiering 的压缩策略来减小写放大，levels（以及子 level）的数量已经显著增加，而在 LSM 中使用的比较多的布隆过滤器，没办法为这种较长的读延迟提供高效的解决方案，因为检查 filters 本身就会占据 PMem 读延迟的大约 50%，这就是我们为什么需要一个新的解决方案来减小读延迟，也就是 ChameleonDB 辅助旁路索引 Auxiliary Bypass Index（ABI）
• 每个 shard 有自己的 ABI，本质是一个内存中的 HASH 表，索引了所有的上层 Keys，通过使用 ABI，在查询 Keys 的时候最多查询三个表，一个 Memtable，一个 ABI，一个最后一层的 table，如图 b 所示。
  
• ABI 包含且只包含存在于上层的 KV 项，当 Keys 被持久化到 L0 的时候，也需要被插入到 ABI 中，在数据项被合并到最后一层的时候，相应地需要从 ABI 中移除对应的索引。为了实现这样的效果，ChameleonDB 在执行 MemTable 到 L0 的刷回的时候把数据项添加到 ABI，在最后一层的 Compaction 执行之后删除 ABI 中所有的数据项，因为在最后一层的 Compaction 之后所有的上层数据都会被清除。PinK 也尝试着把上层以一个多层的 LSM 结构给固定住，而 ABI 将上层的 keys 组织成一个 hash table，在 DRAM 中以 O(1) 的时间复杂度进行访问。
  
• 除了减小尾延迟以外，ABI 也能有助于加速最后一层的 Compaction，ABI 包含一个 shard 的上层的所有数据项，Direct Compaction 是把上层所有的 tables 给压缩到最后一层的 table，不再需要把所有的持久化的上层 Tables 读取出来然后压缩到最后一层，而是直接合并已经存在于 DRAM 中的数据项到最后一层，如下图所示，从而减小最后一层 Compaction 的开销。通过使用 ABI，我们避免了检查多个 levels，从而解决上述挑战2
  
• 直接合并 ABI 和 Last Level，这里的前提是 ABI 的数据和 Upper Level 的数据一致，也就是说都是存储的 索引

Trade Restart Time for the Put Performance

• ChameleonDB shards 的多层结构帮忙减少了重启时间，因为只有 Memtable 需要在重启过程中恢复数据，同时 Memtables 只包含了非常小比例的数据，比如对于一个 4 层结构，且系数为 4 的存储大概只包含了 1/256。然而，维护一个多层 LSM 结构消耗了读带宽、CPU 时钟周期、以及写带宽，因为 Compaction 操作需要与 put 请求一起不断进行，这会降低 put 性能。对于传统的 LSM 设计，比如 LevelDB\RocksDB，多层的结构不得不总是被维护，否则，读延迟会大打折扣，因为越来越多的memtable被刷新到0，而没有被压缩就会产生很多级别，导致遍历次数变多。除此以外，DRAM 的消耗也会快速增加，因为 Memtable 变得越来越大来容纳更多的 KV 项。相反，ChameleonDB 的结构中，上层通常用于快速恢复，提供了一个不用妥协读延迟和 DRAM 消耗来维护多层结构的机遇。（加 HASH 索引）
• 在系统特别稳定以及系统很少故障的场景中，ChameleonDB 可以通过暂时暂停多级结构的维护来换取更高的 put 性能，而无需在密集的 put 工作负载期间进行上层压缩，从而降低系统崩溃时重启时间延长的风险。这样的策略我们称之为 Write-Intensive Mode
• 在 Write-Intensive Mode 下，Memtables 当满了的时候不再被刷回到 L0，L0 到 L1 的压缩不会被触发，同样地，所有的压缩到其他高层也不会进行。只有当 ABI 已满时，才会触发清除 ABI 的最后一级压缩，如果这时候一个系统故障发生了，重启时间可能会很长因为 ABI 中所有的项必须从存储日志中恢复。实验表明该模式下的重启时间仍然比 DRAM-Hash 要小，DRAM-HASH 的整个索引都需要在重启过程中重建。此外，ChameleonDB 重启时间的长短可以将 Write-Intensive Mode 作为一个用户选项来进行控制。
• 简而言之，Write-Intensive Mode 就是不使用上层的索引，停止维护多级结构，ABI 满了则进行合并

Handling Put Bursts

• 读操作尾延迟通常用来测量 QoS，后台压缩任务对于尾延迟有比较高的影响因为该操作消耗 Optane Pmem 读写带宽，在一个 Put 操作爆发期间，读操作的尾延迟可能显著增加，因为后台压缩任务被触发。
• 为了提供更好的服务质量，我们在 ChameleonDB 中引入了一个动态的 Get-Protect Mode 来监控读操作的尾延迟并调整 Compaction 的时机。具体而言，就是一个读操作尾延迟到达一个阈值的时候，ChameleonDB 挂起所有的上层 Compactions，包括 flush 操作，延缓最后一层压缩的执行。挂起上层压缩的影响就是重启时间可能因为不止要恢复 Memtable 还有 ABI 来扫描整个 Log 从而变得很长，和 WriteIntensive Mode 类似，当 ABI 满了之后，所有的数据项需要被压缩到最后一层，假设 DRAM 空间被限制了，且不能容纳一个二级 ABI。然而，最后一层的压缩需要读取最后一层的数据并和 ABI 中的数据进行合并，并写回 Optane Pmem，该操作的开销可能非常大，且显著影响尾延迟，因此 Get-Protect Mode 下只是将 ABI 中的内容 dump 到 Pmem 上作为一个新的级别，而没有进行合并。这将增加get 请求检查的 levels 的数量。然而，根据我们的实验结果，这种副作用相对于最后一级压缩的成本是适度的。此外，我们限制了可以转储到 Optane Pmem 的 ABI 的数量(默认为一个)。Dumped 的 tables 将在 put burst subsides 之后被合并到最后一层。当尾延迟低于预先设定的阈值时，将取消 Get-Protect Mode。
• 简而言之，Get-Protect Mode 就是挂起 Compaction，ABI 满了则 dump 到 PMem

Implementation Details

Randomized Load Factors

• 哈希表通常用作一种可扩展的结构，其大小随插入的项而变化。一旦一个表被认为是满的，它将被展开，其中的项目将被重新散列到新的位置。重新散列是一个耗时的过程。因此，在ChameleonDB的一个分片中，我们为上层的键使用一个固定大小的散列表，以避免频繁地进行重散列，因为散列表的大小变化很大。
• ChameleonDB的分片中的每个表(或子层)也是一个散列表。它通过线性探测来解决碰撞问题。确定此类哈希表是否已满的常用方法是在插入新项时探测它的次数。但是，使用探测计数来确定表是否已满可能会与 ChameleonDB 中的压缩操作发生冲突。例如，由于插入了一个探测数大于阈值的项，一个级别中的4个表中的项可能无法插入到比它大4倍的新表中。另一方面，允许无限的探测时间也不是一个可接受的选择，因为在最坏的情况下，一个 get 请求可能需要扫描整个表，导致太长的 get 延迟。
• 在ChameleonDB中，我们限制了MemTable的加载因子，从而控制所有持久性表的加载因子(因为它们的所有项都来自MemTable)。例如，当我们将MemTable的负载因子限制为不超过75%时，表的四个槽中就有一个是空的。当MemTable的负载因子达到预定义的阈值时，认为它已经满了。当到达一个空槽时，对哈希表的扫描就会停止，因此降低负载因子来增加表中的空槽可以改善获取延迟，但代价是降低空间效率和更频繁的压缩。对所有分片使用统一的负载因子阈值将导致压缩突发，因为插入通常会均匀地分布到 shards 上。在压缩爆发期间，所有shards 都需要进行上层压缩，甚至更糟的是，最后一级压缩的KV存储会经历一个显著的性能退化期。为了缓解压缩突发，ChameleonDB为 shards 使用随机加载因子，从而错开不同 shards 的压缩时间。

DRAM footprint

• 使用ABI改善获取延迟的一个主要问题是它的 DRAM 占用。众所周知，每个分片中的级别大小呈指数级增长。尽管ABI包含了所有上层的条目，但它只占总指数的中等比例(例如，1/r ，层次之间的比率为 r )。

Write Amplifcation

• ChameleonDB中的写放大(不包括对存储日志的写)与级别数(表示为l)、级间比r和负载因子(表示为f)有关。写哈希表的写放大为1/f。例如，一个负载因子为75%、大小为1MB的哈希表只有0.75MB的用户数据，因此写入这个表的写入放大倍数是1/0.75。由于ChameleonDB使用大小分层(size-tiering)来进行中层压缩，使用水平分层(leveling )来进行最后一级压缩，ChameleonDB的写入放大倍数为(l−1 + r)/f。

KV items in the storage log

• 存储日志中的每个条目都有{key, value_size, value}的形式，其中，key 和 value_size 的大小固定在8个字节，而 value 的大小(也就是 value_size)是可变的。日志项首先在DRAM中缓冲以形成批处理。然后，当批处理的大小达到预定义的阈值(例如，4KB)时，将批处理附加到日志的尾部。

Evaluation

• 为了观察和理解 ChameleonDB 在真实系统中的性能行为，并了解它是否实现了所有的设计目标(高写吞吐量、低读延迟、响应请求峰值对读尾延迟的影响，以及快速恢复和重新启动)，我们在英特尔Optane持久性存储器(Pmem)上开发了 ChameleonDB 原型。

Setup

• ChameleonDB以它的App Direct模式运行，通过调用Persistent的开源库中的函数，通过load和store指令访问内存，通过调用 PMDK 中开源库的函数。
• 所有实验都在两台服务器上进行8核Intel Xeon Silver 4215处理器，64GB DRAM和两个128GB Optane Pmem。两个Optane Pmem内存条连接到同一个插座，并以交错模式运行。在我们的实验中，KV存储运行在处理器上，本地访问Optane Pmem，以获得更高的访问效率。
  
• 对比对象：
  • DRAM-HASH：DRAM 中维护 HASH 索引（robin-hood hash table）
  • Pmem-HASH：PMem 中的持久性 HASH 索引 CCEH
  • Pmem-LSM-F：带布隆过滤器且位于 PMem 的 LSM
  • Pmem-LSM-NF：不带布隆过滤器且位于 PMem 的 LSM
  • Pmem-LSM-PinK：除了最后一层以外所有层驻留在 DRAM 上的 LSM，且不使用布隆过滤器（该对照组是最公平的对照组，资源开销相近）
• 写性能：
  • PMem-hash 最差，因为在 Optane 上进行了大量的随机写，与 256B 不匹配，写放大严峻
  • ChameleonDB, Pmem-LSM-NF, and Pmem-LSM-PinK 性能相近，比 Pmem-LSM-F 好很多，这三个方案性能优势相近，因为写入都是大而顺序的，且都没有布隆过滤器的开销。其中 ChameleonDB 和 Pmem-LSM-PinK 在 Compaction 期间使用了一些 DRAM 读代替 PMem 读。三个方案的性能差距较小。因为在 compaction 中发挥了 Pmem 顺序读的优势，与更昂贵的 CPU 使用和哈希操作期间随机 dram 访问 KV 项和压缩相比，读的性能影响大大降低。DRAM-HASH 占用内存更多，恢复更慢，大规模数据场景瓶颈就越明显。
    
• 延迟除 PMem-HASH 以外是比较接近的。
  
• 读方面，Pmem-LSM-NF 最差，DRAM-HASH 最高，其次为本文的方案。ChameleonDB 比 PinK 好是因为 PinK 在 DRAM 维护了多层结构 LSM 需要进行多次检查（level by level）。
  
• 延迟和吞吐的比较结果一致。
  
  
  
  
  

Related Work

Persistent Hashing

• PFHT：是一种布谷鸟哈希变体，它通过在一次写操作中最多允许一次 displacement 来优化以减少在服务写请求期间的内存写操作
• Level Hashing：应用两级散列方案，以便每个键可以有三个桶作为插入的候选桶，这有助于提高负载因子，来代替双重哈希
• CCEH：CCEH是一种可扩展的散列，它使用线性探测策略，因此成功的插入只需要一次内存写操作
• 这些工作设计的写优化的 HASH 都是试图减少 PM 上的写入，但是现阶段在 Optane 上的就地更新会有严峻写放大，ChameleonDB 则聚合了数据。

Key-value stores for Persistent Memory

• SLM-DB：使用一个全局 B+tree 作为索引，数据追加写日志。因为全局索引所以只能存在 PM 上，但又造成小写。而本文的方案使用 HASH 表，占用更小，可以放在内存中
• FlatStore：维护一个易失的全局索引，数据丢 PM，故障恢复时间长。本文只需要恢复一小部分。
• 准确理解存储设备的性能特征对于在设备上进行有效的KV-store设计至关重要。
• HiKV 假设了延迟方面 PM 写比 DRAM 差，读相近，但其实最近研究发现 PM 写延迟更接近 DRAM，读延迟更差。本文的设计通过只在 DRAM 中进行小的写操作和使用基于 DRAM 哈希表的旁路索引减少读操作来适应这些真正的性能特征。
• Bullet 使用交叉引用日志(CRLs)技术将持久内存写移出关键路径，解决了优化的持久内存和 DRAM 常驻 KV 存储之间的性能差距。本文则是使用不同的方式来消除这个性能 gap，使用内存哈希表来减少对 Optane Pmem 的访问，然后批量执行小写。
• NoveLSM 和 MatrixKV 则主要是利用 PM 来提升写性能，NoveLSM 维护更大的 Memtable 在 PM 上来直接在 PM 上执行小写，MatrixKV 则是把 L0 放在 PM 上来优化 compaction 使其更细粒度。但是本文的方案比这两个方案都要好，因为适配了 256B 访问单元避免了小写，使用了共享数据结构来减少 LSM 的层级数，从而细粒度压缩并减小放大，同时使用了 size-tiering 和 leveling compactions 来减小写放大并保证低延迟。

Key-Value Stores for Fast SSD

• KVell：利用无共享结构和异步 I/O 解决方案来充分利用磁盘 I/O 带宽，避免 CPU 瓶颈，从而提升性能
• Zhang et al.：提出了 FPGA 加速 compaction 的 LSM KV 存储来减小 CPU 瓶颈
• PinK：消除了上层的 BF 并使用基于 FPGA 的 SSD 消除了 compaction 过程中的 CPU 的开销