[ATC '20] Lock-free Concurrent Level Hashing for Persistent Memory

发表于 更新于

这是一篇论文阅读笔记。

clevel 是一个面向 NVM 的单机键值存储引擎。它主要解决使用哈希表结构时难以避免的阻塞问题，测试显示它比已有的系统最多快 4.2 倍。

研究背景和动机

基于哈希表的键值存储引擎都面临一个共同的问题：哈希碰撞。这个碰撞一般是通过让哈希表中一个 hash 值对应多个键来解决的。具体来说，在哈希表索引中，一个 hash 值对应一个桶（bucket），每个桶中包含固定数目的槽（slot），每个槽能容纳一个键值对的索引。一般不用拉链 hash 解决这个问题，因为多级间接查找效率太差。

在上述策略下，如果在插入键值对的时候发现对应的 bucket 装不下了，那么就必须给哈希表扩容。这个过程称为 rehash，顾名思义，就是扩大哈希表的容量，然后用新的哈希函数计算每个键值对在新哈希表中的位置，重新插入至新表中。可以看到 rehash 是一个代价极大的行为，并且如果在 rehash 的过程中做增删改查等操作，其正确性是没有保证的。为此，已有的工作

  • 通过各种手段减少 rehash 影响的键值对数量；
  • 在 rehash 时加锁，阻塞可能受影响的增删改查操作。

后者完全就是一个权宜之计，加锁会提升延迟，同时也会给操作延迟带来不确定性。因此，作者设计了 clevel hashing，把 rehash 变成了无锁的操作。

clevel 的设计

前身 level hasing

作者团队在 OSDI ‘18 上发表了一篇 *Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory*，提出了一个叫 level hashing 的东西，本文可以看做是它的续作。level hashing 也是一个哈希表，它的结构如下所示：

level hashing 包含两个核心设计：

  • 哈希表包含两层，其中上层的 bucket 数量始终是下层的 2 倍。rehash 时，将旧的上层变为新的下层，然后把旧的下层中的键值对 rehash 到新的上层中去。
  • 利用两个固定、独立的哈希函数 $H_1$ 和 $H_2$，为每个键值对在每一层选取两个候选的 bucket。

注意哈希表中只存储指向实际键值对的指针和一个用来加速比对的 tag（利用 x86_64 指针未被使用的高 16 位）。当然，level hashing 还包含其他的设计，但它们并没有继承到 clevel 中，所以就略去了。

clevel 的结构

clevel hashing 的意思是 concurrent level hashing，意思是在 level hashing 的基础上加入了并行支持。事实上 level hashing 不能很好地处理键值引擎的并发操作，这一点留到后面讨论。回到正题，clevel 在它的前身的基础上，把第一个核心设计做了一点改进：

  • 哈希表包含若干层，其中每一层的 bucket 数量都是其下一层的 2 倍，各层之间通过一个链表连接；使用一个全局 context 结构保存当前的最顶层和最底层；
  • rehash 时，建立一个新的最顶层，大小为旧的最顶层的 2 倍，然后把旧的最底层中的键值对 rehash 到新的最顶层中去，最后利用 CoW + CAS 更新全局 context。

另外，为了防止 rehash 阻塞其他操作，clevel 将工作线程和 rehash 线程分开：一部分线程专门负责 rehash，另一部分专门响应用户请求。要注意的一点是，虽然文中没有明确提出，但是 rehash 线程的数目必须是固定的，否则会影响错误恢复。

无锁 rehash

首先通过 CAS 和 CoW + CAS 追加新的最顶层，然后更新全局 context。然后对旧的最底层中的每个键值对实施 rehash：首先利用 CAS 将其插入最顶层的一个可用位置中，然后删除其在最底层中的指针。rehash 可以由多个线程并行完成，每个线程负责独立的一部分，例如可以通过一个模函数将不同的 bucket 分给各个线程。

但是注意，由于 rehash 和其他键值引擎操作是并行的，因此可能出现两个问题：

  • 假阴性（False negative）查询：由于 rehash 会移动和删除指向键值对的指针，一个查询请求可能查不到本应存在的键值对；
  • 重复插入：由于插入操作包含一次查询（用来去重），而查询可能返回假阴性结果，键值引擎内可能存储了多个重复的键。

这两个问题都是 level hashing 遗留下来的，不过后面 clevel 会把它们解决掉。

另外，我在思考无锁 rehash 的正确性的时候想到，如果 rehash 过程中有一个工作线程发起另一个 rehash 请求，则这个新的请求会被阻塞到当前 rehash 结束，所以实际上 rehash 并不是完全无阻塞的（回顾一下，多个 rehash 线程是为了并行处理同一个 rehash，而不是多个）。但是，两个独立的哈希函数的存在使得上一次 rehash 还没结束就出现这种情况的概率非常低。这里，两个哈希函数可以说是起到了 power-of-two-choice 的作用，这个既简单又有效的策略已经见过很多次了，比如 FAST ‘19 的那篇 DistCache。

无锁增删改查

  • 查询：由最底层开始逐层向上查找；为了解决假阴性问题，如果出现阴性结果，那么要检查全局 context 是否发生变化，如果变化了就再查一次。
  • 插入：由最底层开始逐层向上寻找空位插入。但是这带来两个问题：第一个是并行的请求可能插入相同的键值对，第二个是把数据插入到最底层可能因为 rehash 而导致丢失数据。对于第二个问题，我们在 rehash 时不插入到最后一层；如果已经插入到了最后一层，然后发现 rehash 开始了，那就重新执行一遍插入操作，把它转化为键重复的问题。最后，尽管我们没法避免出现重复的键，但每个键值对本身都是正确的，因此查询到的也一定是一致的结果；剩下的就是在更新和删除操作时处理这些重复的键。
  • 更新：由最底层开始逐层向上查找，如果出现多次命中，只保留位于最高层的那一个。为了防止 rehash 导致更新失败，rehash 线程需要记录它当前做到了哪一步（即正在处理哪个 bucket）；如果更新操作前后，被更新的 slot 正好被 rehash 线程经过，那么就重来一遍。
  • 删除：和更新类似，也要处理键重复和 rehash 的问题。

我认为更新操作还是有问题的，至少是表述上。为了防止出问题，应该是在执行 rehash 之前先更新“做到了哪一步”。那么比如现在 rehash 刚好处理到要更新的 slot 所在的 bucket，工作线程就应该等到这个键值对被搬到最顶层，然后再去最顶层更新数据。

性能表现

正好上篇写的 FlatStore 也是单机 NVM 键值引擎，不过没和 FlatStore 做对比，可能因为没开源吧。

性能总体上优于已有成果，许多指标和 SOSP ‘19 的 P-CLHT 基本持平，优势主要有两个：

  • 因为 P-CLHT 插入要加锁，插入快了一倍以上；另外也支持 P-CLHT 不支持的更新操作；
  • 可扩展性优于 P-CLHT，并发数高的时候性能优势比较明显。

我的一些想法

挺有意思的一篇文章，整个系统无锁，感觉把一些东西做到了极致。

如果一定要问有什么点可以改进，全文最让人感觉不适的点就是 rehash 线程需要一直记录它做到了哪一步。照作者的意思，为了错误恢复，应该每 rehash 一个 bucket 就记录一次？这会导致相当多的 clflush 和 mfence，可能会比较耗 NVM。

当然一个直观的解法就是每隔几个 bucket 记录一次。不过如果这样不行，那可以再想想别的办法。