[ASPLOS '20] FlatStore: An Efficient Log-Structured Key-Value Storage Engine for Persistent Memory

发表于 更新于

这是一篇论文阅读笔记。

FlatStore 是一个面向 NVM 的单机键值存储引擎，适用于小规模键值对和写密集的应用场景。它使用 batching 的思想，降低刷写次数从而降低延迟。测试结果显示 FlatStore 比已有的系统快 2.5 ~ 6.3 倍。

研究背景和动机

当前，键值引擎上的实际工作负载具有两个特点：

  1. 大部分键值对的尺寸很小，例如 Facebook ETC Pool 中有 70% 的数据不大于 300B；
  2. 写密集。传统的负载通常是读密集型的，但如今大量实际应用会不断更新已有数据。

一个传统的面向 NVM 的键值存储引擎在面对一次 Put 操作时可能对 NVM 产生多次更新，包括键值对本身、存储键值对所用空间的分配器的元数据，以及用于索引的数据结构。为了操作保序，每次更新之后可能还需要执行 clflush 和 mfence 这类缓存刷写和访存屏障指令。Intel 的 Optane DC PMM 设备的内部写粒度是 256B，然而缓存行刷写粒度则是 64B，这就导致浪费 NVM 带宽。

作者还在实测中观察到两个现象：

  1. NVM 的随机访存性能在线程数较少时低于顺序访存性能，但在线程数增多（$\geq 20$）时二者没有显著区别；
  2. 当刷写一个缓存行到 NVM 中后，如果立即再次写入并刷写同一个缓存行，那么后一个操作会非常缓慢，大概要花费 800ns，是平均值的 4 ~ 8 倍。这件事情原因不明，但其确实存在。

基于这些观察，作者设计了 FlatStore 来改进键值引擎的性能。

FlatStore 的设计

FlatStore 基于单机，CPU 的多个核可以分别处理请求，客户端根据键的哈希值决定将请求发送到哪一个核心上。

日志式写入

FlatStore 采用日志式（Log-structured）的设计，比较好地解决了上面讲到的两个问题：

  1. 每次更新（Put）操作都导致一系列的 NVM 刷写。如果采用 Log-structured 的设计，多次请求就可以方便地被 batch 在一起，只 flush 一次；同时也能比较好地匹配 NVM 自身的内部访问粒度。
  2. Log-structured 天生避免了原地写导致的问题。

FlatStore 在 NVM 中维护一个写日志，将索引结构维护在 DRAM 中。这个写日志是 per-core 的，避免了不同的核心之间的同步开销。至于 DRAM 中的索引结构则可以套用任何已有的解决方案，如果希望单点快速查询可以维护一个哈希表，如果希望支持范围查询那就维护一棵 B+ 树。索引结构可以在 FlatStore 重启时从 NVM 中的日志恢复，也可以周期性地持久化到 NVM 里面来加快恢复。

日志项的设计在此值得一提。FlatStore 使用了一个经典的、类似 inode 的解决方案。每个日志项先用 3 字节存储元数据，用 8 字节存键（Key）；然后，如果值（Value）不大于 256B，就把值直接内联在日志项里面，否则用 5 字节存储值的地址，值的内容本身则存储在 NVM 中另外的一段空间中，由一个分配器管理。

虽然值指针只有 5 个字节，但因为值大于 256B，如果我们保证值存储的位置是 256B 对齐的，那么它的地址的后 8 位就都是 0，可以省掉。也就是说值指针实际上是 6 个字节，这足以索引 128TB 的 NVM 空间，是够用的。同时，虽然键的大小只有 8 个字节，但可以很容易地把它也改为一个指针，从而支持更大尺寸的键。

此外，日志项在存储时是缓存行对齐的，也就是说不同的项不会占用同一个缓存行，这就避免了之前提到的刷写同一缓存行时缓慢的问题。

批处理

上一小节提到多个请求可以被 batch 到一起。由于 CPU 的多个核心都在执行请求，所以一个最简单的方式是每个核分别 batch 自己的请求。但是这样每个核心必须凑够一个 batch 才会去完成请求，会显著提升请求延迟。

对此，FlatStore 提出一个简单的解决方案，称为 Horizontal Batching（HB），就是当一个核心收到请求时，首先把它放到一个公开的请求池中，然后尝试取得一个全局锁。拿到锁的核心从其他所有核心的请求池中收集请求，全都拿到自己这里 batch 起来，执行完毕后发送一个完成消息，并且释放全局锁。其他核心收到完成消息后返回给客户端。但是这种情况下同一时间只有同一个核心在工作，其他核心都在等待，浪费资源。

最终的解决方案也很简单。某个核心如果拿不到全局锁，那它就先去轮询客户端发来的下一次请求，然后执行一次新的 HB 流程。具体可以看下面的图(d)：三个核在处理请求，C3 拿到了全局锁；C1 和 C2 并不等待 C3 发来的完成信息，而是重新开始 HB，去轮询新请求，然后试图拿锁；这回由 C2 得到了锁，C1 就又去轮询新的请求。拿到锁的核心在收集完其他核心的请求后就立即释放锁，而不是一直持有到完成这些请求。这样一来，多个核心就比较有效率地被利用起来，同时每个核心每次也都能 batch 到一定数量的请求。这就被叫做 Pipelined HB。

当然如果很多 CPU 核心争抢一个全局锁，反而会降低效率；对此作者提出可以将核心分组，每组核心争用单独的一个全局锁。分组方式见仁见智，作者根据他们的经验提出“将来自同一个 socket 的核心分在一组”能带来最优性能。

性能表现

略去。总而言之是全面优于已有成果（Level-Hashing、CCEH、FAST&FAIR、FPTree），有不错的性能线性性。相较于朴素的 HB 策略，Pipelined HB 表现出了明显的性能优势。此外，日志空间回收效果也不错，没有严重影响前台的处理性能。

我的一些想法

  1. 文章中作者对 Intel Optane DC PMM 刷写同一缓存行的延迟的测试感觉非常重要，这相当于是给简单地进行数据原地更新的系统判了死刑，要想取得较高性能也许必须去搞 COW；
  2. 文章中 Log-structure 的设计还是相对传统，Log Entry 的设计也很像 inode，分配器的设计也包含了一些 trick 在里面；总而言之这部分的性能优势还是来源于工程实现，理论层面没有突破；
  3. Pipelined HB 部分，如果每个 HB 分组只有一个全局锁，那么其他核心还是必须得等到全局锁被释放，然后才能去轮询下一个新请求，否则这些核心在执行新的 HB 流程时可能锁还没被释放。如果每个 HB 分组有多个全局锁，事情就会变得极度复杂，各个核心之间还必须协调用哪个锁，这种情况是不太可能出现的；
  4. 一直以来都有把键值引擎用到分布式文件系统中的尝试，主要是用来管理元数据；但是 FlatStore 的设计中并不包含任何容错，感觉也许是没有办法推广到分布式元数据服务中。