这篇讲了针对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
只需要设置相应的token
Insert
需要分情况:如果不需要移动元素,那么先写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
,赞。