这是华科的第一篇 OSDI 论文，发布时间是 2018 年。
主要研究 Persistent memory 上高性能的 hashing table。
在 Pmem 上放各种数据结构是近年来学术界的热点，很多研究都是基于 B 族树，这篇 paper 的研究点是 hash table 数据结构在 Pmem 上的高性能方案。

背景

Pmem 特点：

在延迟和吞吐量上接近 DRAM；
具备持久化的能力；
可以按照字节寻址；

Pmem 的特点问题使得可能的问题：

• 部分写
• 乱序写

当把 hash table 放到 pmem上，存在以下几个挑战：

• 一致性保证需要高开销

1. 由于上面的两个原因，指令可能被乱序，所以不得不使用 cache line flush 和memory fence，这将引入高的开销；
2. CPU 的原子写 unit 一般是 8B， 如果写入超过了这个大小，就需要使用其他昂贵的技术来确保程序崩溃后数据不被破坏，例如 WAL，COW 技术。

• Pmem 的读写延迟是非对称的，写延迟高于读延迟，并且并发写延迟更高；

• 传统 hash table 的 resize 性能不好
  需要分配新的内存（一般2倍），然后将 item 重新 hash 一遍，时间开销是 O(N) 复杂度，N 是 item 的数量。Resize 触发 N 个插入操作，会导致 大量的 cache line flush 和 memory fence。

hash 结构

hash 最大的差别是冲突的解决。

当 hash table 中有两个或者多个 key 被映射到同一个位置时，就出现了碰撞冲突。
碰撞冲突一般有两种方法，分别为：

• chained hashing
  chained hashing 是使用链表，将冲突的 key 串起来，当前工程上采用这种方法。
• open addressing
  open addressing 采用其他的策略，来重新选择一个位置，直到可以放置没有冲突为止。

image.png

BCH

cuckoo hash 基本思想是使用2个hash函数来处理碰撞，从而每个key都对应到2个位置。

插入操作如下：

1. 对key值hash，生成两个hash key值，hashk1和 hashk2, 如果对应的两个位置上有一个为空，那么直接把key插入即可。

2. 否则，任选一个位置，把key值插入，把已经在那个位置的key值踢出来。

3. 被踢出来的key值，需要重新插入，直到没有key被踢出为止。

PCM-frendly hash table(PFHT)

作为 BCH 的变种，PFHT 修改 BCH，每次插入一个新的元素的时候，只能 evict 一个 item，可以降低写的次数，但是空间利用率低（load factor 小）。
如果不能放进去，就放到一个新的地方存着。

path hash

扩展了 2-choice hash，path 用来存放冲突的 item。

image.png

level hashing 设计

image.png

level hashing 是一种新的开放式寻址结构，它具有BCH，PFHT和路径哈希的所有优点，包括高效内存访问，写优化和高性能，同时通过以下主要设计决策来避免它们的缺点。

Write-optimized Hash Table Structure

① Multiple slots per bucket
② Two hash locations for each key
③ Sharing-based two-level structure
④ At most one movement for each successful insertion

根据 facebook 和 baidu 的 key-value 数据库 workload 特点，得知 key 一般小于 cache line，大部分的 key 长度是小于 32B的，所以一个 key 可以放到 cache line 里面，通过 CLFLUSH + MFENSE 做到原子下刷。

作者设计的 Level hashing 借鉴了 2-choice 和 BCH 以及其 path hash 的做法。
对于每个 key， 设计两个不相关的 hash 函数，来计算可以放的 bucket。然后每个桶，有多个 slot，用来存放有冲突的 key 和 value。
Level hashing 有两层，在插入时：

• 首先计算两个 hash 值，先查找上层的两个桶，是否有空余的 slot，如果有，插入即可，反之，进入下一步：
• 在下层中继续查找对应的两个桶是否有空余的 slot，插入即可，反之，进入下一步：
• 重新从上层开始，尝试移动每一个桶里面的 item，能否移动到其他位置，如果有，移动后，插入即可，依次类推；

一致性保证

为了实现 log-free 原子写入，作者在每个 bucket 的首部为每个 kv 保留了一个 token 标记位，0 表示相应的 slot 未被占用，1 表示相应的 slot 被占用；

insert

其数据的 insert 采用，先写 kv，然后更新相应的 token标记位，只有当 token 标记位 update 成功，需要注意的是这里 token 由于比较小，可以保证原子更新（一般是 64 bytes 的原子更新）。

image.png

总结说来，对于 insert不需要移动的场景，先写 kv， 然后更新 token。
序列是：
如果在一个 cache line：

set bit
pflush key
pflush value
pflush token

如果不在一个 cache line：

pflush key
pflush value
mfense
set bit
pflush token

插入的时候如果要移动一个 item：

• 先移动一个 item 写入到新的地方
• 在旧的地方写入 item；
• 更新 token；
  可能出现一个 key 出现在两个地方，但是内容是一致的，所以不存在数据风险。

update

对于 update，不能原地更新，可能造成 partial write；

• 上面的插入可以能在同一个 key 出现多次的情况，如果有多份数据，先删除一个 item，转到下一步；
• 找个一个空闲的 slot，写入新的 key-value；

• 更新旧的 key-value 的 token 为 0，更新新的 key-value 的 token 为 1，这个操作可以原子的更新；

  
  
  image.png

如果找不到空闲的地方，不得不采用 log 的方式，备份旧的数据。

delete

delete 最简单，原子的设置 token 为 0 即可。

rehash

首先创建一个新的 level，叫做 interim level，从下一层 rehash item 到 interim level。
对于每一个 item，先写 kv，再 set token 为1，最后 set old token 为0，如果 crash 发生，可能造成 duplicate item。
但是不会有数据风险。
再 recover 过程中，先查找是否有重复的 item，如果有先删除即可。

rehash

改善 resize 之后的 load factor

在 resize 之后，可能导致上层的空间利用率不高。原因是：

1. 在 resize 之前，一般是上层空间满了，下层并没有满。（原因是下层是存放冲突的地方）
2. 在 resize 之后，将下层的 1/3 元素重新 hash 到 更大的一堆 bucket 里，使得上层的桶很稀疏；

一个做法是：
当插入的时候，上下层都插不进去：

• 先尝试移动一个 item 到同层的桶里面；
• 可以从下层选择一个 item ，搬到上层放置，然后在这里放入新的 item；

改善 resize 之后的搜索性能

resize 之后可能查找性能有额外的开销，原因是：

• resize 之前，2/3 的数据在 top level，resize 之后，2/3 的数据成了 second level，所以查找有 2/3 的概率需要找到第二层。
  解决办法是：
• 如果第二层数据量大于第一层数据量，就从第二层开始查找；

并发 level hashing

多线程冲突来自于访问同一个 slot，只需要加 slot 级别的锁，就可以避免了。

总结

• 低的一致性开销
  提出了在插入，更新，删除，resize 操作都可以 log-free 且保证一致性安全；
• 写优化
  提出了一个 2-level hash table 结构，可以确保在最坏情况，O(1) 复杂度下完成搜索，删除，更新操作。对于插入，在大部分场景下，最多查找 4 个bucket 就可以成功，以及很少的场景需要移动 item。
• 低开销的 resize
  为了改善 resize 的性能，提出了一个 原地 hash 的方案，通过添加一级 hash 结构，使得只需要 rehash 1/3 的item，大大的降低了 resize 的写入开销；
• 实验结果表明其在性能和负载因子上表现都很出色。

想法

update 的时候，如果同一个桶里面没有空余的 slot，那么需要采用 log 的方式。其实可以做的方法是预留一个 slot，专门用来做 update，不过这样可能降低 load factor。