原题目：Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory

文章概况：这篇文章主要研究 Persistent memory 上高性能的 hashing 索引技术

这篇文章是来自华中科技大学，好像实现了零突破。上交 IPADS 实验室今年有两篇。强~

1. Motivation

Persistent Memory （例如 Intel 公司基于 3DXpoint 技术的 Optane DC Persistent Memory 设备 ）在 latency 和 throughput 的性能表现上都接近 DRAM，而且同时具备了 Persistent 和 byte-addressable 的能力，因此备受学术界和工业界的关注。当前 PM 上索引数据结构的研究大多集中在 B族 tree 上，这篇文章主要研究基于 PM 的高性能 hashing 索引技术，因为相比传统在 DRAM 中的 hash table ，基于 PM 的 hash table 会存在几个问题：

（1）PM 上的 hash table 都是持久化的，那么意味着需要保证数据写入的 consistency，也就是写入的原子性，传统写入大多使用 log 或者 COW 技术，性能表现一般

（2）PM 设备的 write 相比 read，在 latency 上会差很多，而且，并发的 write 性能不好，在并发上去之后 latency 显著上升，在上一篇文章【ATC 2018】Closing Performance Gap Between DRAM&NVM 有贴出一些测试数据（Notes，1,2 这两点涉及很多 PM 设备偏底层的知识，没怎么看懂，感兴趣的可以看看论文原文）

（3）传统 hash table 的 resizing hash table 性能很差，因为 resizing hash table，需要创建一个新的 2 倍大小的 table，然后在将旧的 hash table 的数据复制过去

2. Innovation

1. 巧妙的提出了一种分层（Level Hashing）的 hash table 方案，可以实现 Cost-efficient In-place Resizing Scheme，大大减小了 resizing hash table 的开销
2. 通过一个 Log free 技术实现了原子的 write，实现了 Low-overhead Consistency Guarantee Scheme

3. Implement

3.1 Level Hashing Design

当 hash table 中有两个或者多个 key 被映射到同一个位置时，就出现了碰撞冲突，教科书的碰撞冲突一般有两种方法，分别为：开放定址（open addressing）和开链（separate chaining）。开放定址的方法，通过一定的策略重新选一个位置，直到没有冲突，缺点就是解决一个冲突，但是会引入一些冲突；开链方法，会将冲突的的 value 用链表组织起来，但是局部性比较差，一般工程实现都是用的开链 [3]。更多 hash table 的细节和描述，可以参考文献 [3]，写得不错。

作者设计的 Level hashing 为了保证较好的局部性，借鉴了 Cuckoo hashing [2] 的做法，每个 hash key，会通过两个 hash 函数计算， 而且每个 hash 桶都有多个 slot，用于存放冲突的 key 的 value，而且如图 Figure 1. (a)，Level hashing 有两层，分为 top level 和 bottom level，其插入的过程大致如下：

（1）首先在 top level 在找空的位置，通过 hash1(key) 确定 hash 桶位置，如果有空的 slot，则放入，没有则用 hash2(key) 确定 hash 桶位置，如果有空的 slot，则放入，否则进入下一步， （2）在 bottom level 中找空的 slot，bottom level 的容量是 top level 的一半，其放置的过程和 top level 一致，还是通过 hash1 和 hash2 两个函数依次计算查找，这也是 Level hash design 的核心创新点之一

（上图中（a）为逻辑视图，（b）为物理视图，也就是具体工程实现，一般都是数组实现的）

（3）如果上面两步都没有找到，则进入 hash resizing，将 hash table 的容量扩大到两倍。其 resizing 的过程下面将详细描述。

3.2. Cost-efficient In-place Resizing

这里以增大空间为例。hash table 初始状态为（a），开始 resizing 之后，首先分配一个 2N 的空间，作为 top level，原来的 top level 作为 bottom level，原来的 bottom 作为过渡层，如图（b），然后将过渡层的 value 重新 hash 到新的 hash table 中，完成之后就删除回收过渡层，如图（c）。通过分层的 hash 设计，不难发现在 resizing 的时候，平均仅有 1/3 的 hash table 元素需要移动，相比传统的 hash table 设计，确实很有新意。

3.3. Low-overhead Consistency Guarantee

为了实现 log-free 原子写入，作者在每个 bucket 的首部为每个 kv 保留了一个 token 标记位，0 表示相应的 slot 未被占用，1 表示相应的 slot 被占用（如下图）；其数据的 update 采用的类似 delta update （append only write ）的思路，先写 kv，然后更新相应的 token标记位，只有当 token 标记位 update 成功，需要注意的是这里 token 由于比较小，可以保证原子更新（一般是 64 bytes 的原子更新）。

4. Summary

level hahsing 通过 level，使得在读写性能 O（1）的情况下，表现出了非常好的 resizing 性能，可以减少 2/3 的数据移动；通过 token 的设计实现了 log-free 的 delta update，降低了保证 PM 设备数据原子写入的开销，最后实验结果表明其在性能和负载因子上表现都很出色，详细数据参考原文，这里就不贴图了。

鸣谢

非常感谢上交 IPADS 实验室关于 OSDI 2018 的全方位解读，详细参见文献 [4]，感兴趣的可以通过 IPADS 实验室的这几篇文章快速搜寻自己感兴趣的研究主题，因为毕竟对非学术背景出身的同学，其实在万千论文中找出有价值的论文是一件痛苦和吃力的事情。这篇文章也只是在文献 [4] 的引导下，看了这篇论文，写了这篇笔记，实际上不用看论文原文，文献 [5] 已经描述得非常清晰了。所以再此特意表示感谢，以后会持续关注和学习。

Notes

限于作者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流；部分参考已经在正文和参考文献列表中注明，但仍有可能有遗漏的地方，有任何侵权或者不明确的地方，欢迎指出，必定及时更正或者删除；文章仅供于学习交流，转载注明出处。

参考文献

[1]. Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory.

[2]. Fan B, Andersen D G, Kaminsky M. MemC3: compact and concurrent MemCache with dumber caching and smarter hashing[C]// Usenix Conference on Networked Systems Design and Implementation. 2013:371-384.

[3]. 聊一聊哈希表. http://legendtkl.com/2017/07/23/about-hash-table/

[4]. 卡尔斯巴德中的OSDI'18—SJTU-IPADS的集体见闻（三、四）. https://mp.weixin.qq.com/s/0fyNk4kuakZlIgnSuw8NYg