这篇讲了针对NVM的open addressing hashtable，其中和一致性相关的内容感觉并不是特别多，没有看出特别多的针对NVM的优化出来。很多数据和load factor有关，毕竟对于open addressing hashtable而言，装载系数特别重要，chained hashing如果冲突太多，影响的是性能，open addressing的槽位如果都占满了，则必须通过rehash或者淘汰来解决。当然open addressing可能有其非常适用的场景。
下面只针对Paper 中讲设计细节的内容作解读。
数据结构
作者针对open addressing的hashtable，提到了下面4个设计理念：
D1: Multiple Slots Per Bucket
对于一个桶，有多个Slots可以来存储数据，这样读取一个桶的数据的时候，对CPU cache更友好，减少访存的次数，后面的解释都针对1个Bucket有4个Slots。
D2: Two Hash Locations For Each Key
对于第一个key，会通过两个不同的hash函数计算出hash值，这样可能匹配到两个不同的桶。插入的时候会选择比较空一些（空Slots更多一些的）的那个桶。
D3: Sharing-based Two-level Structure
level hashing的核心理念，后面的rehash也是基于这个设计的。从下图中可以看到分为 TL(top level)和BL(bottom level)，优先会去装载TL。
一个key可能会对应到两个hash值，可能对应上图中TL层的两个不同的桶，同时会有 BL层两个不同的桶，对于某一个特定的key，可能属于的位置是没有level之前的4倍。所以，一次查找操作最坏的情况下需要去4个桶里面去找数据，也就是可能去对比16个Slots。下面的描述中，都认为一个key可能有4个桶选择来存放。作者的paper中并没有测试level 更多的情况，可能是因为边际效益递减的原因。
D4: At Most One Movement for Each Successful Insertion
在插入时，允许做一次移动；首先会去找Top-level的那两个桶，如果这两个桶都满了，也就是8个Slots都满了，那么会去看这8个Slots能不能移动到它们另外一个可选的Top-level的桶（另外一个hash函数对应的桶，这里要再算两次hash）。如果到这里还是失败了，那就去尝试放到Bottom-level的两个桶中。这里Bottom-level的两个桶中同样会有8个Slots。注意，这里并没有说Bottom-level的桶中的Slots会再移动到Top-level中，这个也是有可能的，但是属于作者后面提到的bottom-to-top(B2T)方案。
通过以上几个设计理念，作者给出的结果显示有效地提高了装载系数。其中，D3和D4属于这篇paper里面相对有特色的方式。
In-place Resizing
Resizing更常用的叫法是Rehash，trivial 的Rehash方式一般需要把老的hashtable中所有的数据都移到到新的hashtable中，当然，这个过程中不一定会阻塞增删改查的流程。
对于level hashing 而言，简单来说， rehash就是增加一个新的TL层，来接受新的写入，原来的TL层变成新的BL层，原来的BL层作者称之为IL(interim level)，因为经过rehash之后，这一层就会被删除。rehash的过程就是将IL中的元素向TL和BL中移动。
作者认为这个移动出现rehashing failure的可能性不大，因为IL中元素的个数比较少。这是rehashing failure这种情况对于open addressing的hashtable来说还是有存在的可能性的，这可能也是为什么实际使用的产品大多是使用chained hashing。
针对这样的Resizing方案，作者提出了两个问题：
- 装载系统变低。
Rehash之后，新的BL层基本是满的，这样就会导致level hashing基本就变成单level了，这样会影响load factor。 - 查询性能变低。
Rehash之后， 新的TL中的元素个数只是BL中的一半，对于存在元素的查询层数的期望从本来的4/3层变成了5/3层。
对于第1个问题，使用的是bottom-to-top(B2T)，在出现位置满的时候，会尝试把BL中的元素移到TL中，如果不把key的hash值存放起来，在有冲突出现的时候，level hashing的CPU消耗会增加得比较厉害。
对于第2个问题，作者引入了dynamic searching，简单来说就是根据元素个数来决定是先查找TL还是先查找BL，而不是无脑先查找TL。
低成本的一致性保证
好，这一节讲到了NVM相关的了。作者的主要思路是如何通过设计来避免宕机之后带来的不一致状态，而且需要通过尽量不记日志的方式。首先一个相关的设计是Bucket内部的结构：
头部使用小于8 bytes的空间来记录，每一位(token)代表相应的Slots的空闲状态，这样头部的更新就可以原子地完成。作者并没有指明Slots是否是定长的，但从上下文来判断，应该是假设是定长的。
对于Delete、Insert和Resize，都是可以做到log-free的；对于Update，某些情况下是可以log-free的。
Delete只需要设置相应的tokenInsert需要分情况：如果不需要移动元素，那么先写Slot内容，再设置token；如果需要移动元素，先在dest的位置增加，再在src的位置删除，再执行插入。那么这就会出现在dest的位置增加后，系统崩溃，恢复起来后，hashtable中有两个相同的key的情况，这对读并不影响，对delete来说，需要查找所有的Slots，把命中的都删除掉；对于update，需要先删除其中一个Rehash和上面的Insert需要移动元素的情况是相同的，不同的是Rehash的过程如果导致了两个相同的key，是可以知道这个key的位置的，那么可以检查这个key是否有两个版本Update在某些情况下是可以log-free的，这个情况具体是需要update的key所在的Bucket中有空闲的Slot
小结
关于NVM上的hashtable，之前有一篇<NVC-Hashmap: A Persistent and Concurrent Hashmap For Non-Volatile Memories>，使用的是Split-Ordered Lists，感觉更实用一些。
我们实验室的第一篇OSDI，赞。