《Write-Optimized and High-Performance Hashing Index Scheme for Persistent Memory》解读

原文地址Slides地址

这篇讲了针对NVMopen addressing hashtable,其中和一致性相关的内容感觉并不是特别多,没有看出特别多的针对NVM的优化出来。很多数据和load factor有关,毕竟对于open addressing hashtable而言,装载系数特别重要,chained hashing如果冲突太多,影响的是性能,open addressing的槽位如果都占满了,则必须通过rehash或者淘汰来解决。当然open addressing可能有其非常适用的场景。

下面只针对Paper 中讲设计细节的内容作解读。

数据结构

作者针对open addressinghashtable,提到了下面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个桶里面去找数据,也就是可能去对比16Slots。下面的描述中,都认为一个key可能有4个桶选择来存放。作者的paper中并没有测试level 更多的情况,可能是因为边际效益递减的原因。

D4: At Most One Movement for Each Successful Insertion

在插入时,允许做一次移动;首先会去找Top-level的那两个桶,如果这两个桶都满了,也就是8Slots都满了,那么会去看这8Slots能不能移动到它们另外一个可选的Top-level的桶(另外一个hash函数对应的桶,这里要再算两次hash)。如果到这里还是失败了,那就去尝试放到Bottom-level的两个桶中。这里Bottom-level的两个桶中同样会有8Slots。注意,这里并没有说Bottom-level的桶中的Slots会再移动到Top-level中,这个也是有可能的,但是属于作者后面提到的bottom-to-top(B2T)方案。

通过以上几个设计理念,作者给出的结果显示有效地提高了装载系数。其中,D3D4属于这篇paper里面相对有特色的方式。

In-place Resizing

Resizing更常用的叫法是RehashtrivialRehash方式一般需要把老的hashtable中所有的数据都移到到新的hashtable中,当然,这个过程中不一定会阻塞增删改查的流程。

对于level hashing 而言,简单来说, rehash就是增加一个新的TL层,来接受新的写入,原来的TL层变成新的BL层,原来的BL层作者称之为IL(interim level),因为经过rehash之后,这一层就会被删除。rehash的过程就是将IL中的元素向TLBL中移动。

作者认为这个移动出现rehashing failure的可能性不大,因为IL中元素的个数比较少。这是rehashing failure这种情况对于open addressinghashtable来说还是有存在的可能性的,这可能也是为什么实际使用的产品大多是使用chained hashing

针对这样的Resizing方案,作者提出了两个问题:

  • 装载系统变低。Rehash之后,新的BL层基本是满的,这样就会导致level hashing基本就变成单level了,这样会影响load factor
  • 查询性能变低。Rehash之后, 新的TL中的元素个数只是BL中的一半,对于存在元素的查询层数的期望从本来的4/3层变成了5/3层。

对于第1个问题,使用的是bottom-to-top(B2T),在出现位置满的时候,会尝试把BL中的元素移到TL中,如果不把keyhash值存放起来,在有冲突出现的时候,level hashingCPU消耗会增加得比较厉害。

对于第2个问题,作者引入了dynamic searching,简单来说就是根据元素个数来决定是先查找TL还是先查找BL,而不是无脑先查找TL

低成本的一致性保证

好,这一节讲到了NVM相关的了。作者的主要思路是如何通过设计来避免宕机之后带来的不一致状态,而且需要通过尽量不记日志的方式。首先一个相关的设计是Bucket内部的结构:

头部使用小于8 bytes的空间来记录,每一位(token)代表相应的Slots的空闲状态,这样头部的更新就可以原子地完成。作者并没有指明Slots是否是定长的,但从上下文来判断,应该是假设是定长的。

对于DeleteInsertResize,都是可以做到log-free的;对于Update,某些情况下是可以log-free的。

  • Delete只需要设置相应的token
  • Insert需要分情况:如果不需要移动元素,那么先写Slot内容,再设置token;如果需要移动元素,先在dest的位置增加,再在src的位置删除,再执行插入。那么这就会出现在dest的位置增加后,系统崩溃,恢复起来后,hashtable中有两个相同的key的情况,这对读并不影响,对delete来说,需要查找所有的Slots,把命中的都删除掉;对于update,需要先删除其中一个
  • Rehash和上面的Insert需要移动元素的情况是相同的,不同的是Rehash的过程如果导致了两个相同的key,是可以知道这个key的位置的,那么可以检查这个key是否有两个版本
  • Update在某些情况下是可以log-free的,这个情况具体是需要updatekey所在的Bucket中有空闲的Slot

小结

关于NVM上的hashtable,之前有一篇<NVC-Hashmap: A Persistent and Concurrent Hashmap For Non-Volatile Memories>,使用的是Split-Ordered Lists,感觉更实用一些。

我们实验室的第一篇OSDI,赞。