A-A+

Split-Order Hash基本原理

2016年12月26日 编程 评论 2 条 阅读 1,617 次
摘要:

之前阅读论文并实现了一个可扩展的哈希表,已经在生产环境使用。这里简单描述一下思路和一些经验教训,详细的实现可以参见论文。

之前阅读论文并实现了一个可扩展的哈希表,已经在生产环境使用。这里简单描述一下思路,详细的实现可以参见论文。

 

哈希的常规实现方式是开辟一个长度为N的大数组,新插入一个元素时,先根据元素hash值模除N,将元素节点插入这个桶,桶上有元素,一般可以拉链解决冲突。当元素越来越多,每个桶上链表就会比较长,查找操作耗时增加。此时哈希表要扩展。扩展时,哈希表长度从N扩展到2N,就需要将原来第0个桶上的元素挑出来,转移到第N个桶上。例如,N=16,hash=0/16/32/48的元素都在0号桶,当扩展到2N=32时,hash=16/48的元素要移动到16号桶上。移动元素时,给两个桶加锁,然后操作两个桶的链表。

这里简介一种不需要加桶锁的算法,Split Order Hash。

先假设我们已经有了一个抽象数据类型ResizableArray,另外算法不关心内存回收。

假设一开始size=4,如左侧图示。hash值为0,4,8,12的key都会落在bucket 0上。如果要把size扩展到8,那么,其中4和12要转移到bucket 4上。如果bucket 0上的元素就是按照前一部分属于bucket 0,后一部分属于bucket 4,那么扩展就容易的多,可以直接把bucket 4指向分界点即可,如红色所示。那么,如何在扩展前就将数据按照适合分裂的顺序排好(注意,将来可能还要扩展到16,32…,因该顺序要支持递归分裂)?我们发现,bucket 0和bucket 4的元素有着天然的区分,如果哈希值是x..x000就会落在bucket 0,如果最低位是x..x100就会落在bucekt 4(其中x为0或1的任意值)。

注意到这个现象之后,我们将哈希值位翻转,即可保证想要的顺序,即000x..x < 001x..x。该顺序也满足递归分裂的要求。位翻转后的顺序即定义为split-order。

split-order hash

一些经验教训:

  1. 实际实现时,也可以考虑用分位点的思路来写代码,道理是一样的。
  2. 扩展时,并不是每次都要真的将size加倍,比如,size=64可以扩展为size=80,那么bucket 81~127视为不需要填充即可。
  3. 所有的桶节点都可以串起来。
  4. 填充桶(桶节点串到链表):需要先设置bucket_node的next指针,然后用CAS原子地串到链表,在CAS成功之前,桶不能被视为有效,等CAS成功之后才能对外生效。所以正在被填充的桶生效时机不能依赖next指针是否为空来判断。
  5. 桶可以惰性填。
  6. 注意避免false sharing。
  7. 计算负载因子时,需要维护一个原子计数器。原子加1在多线程环境下成本很高(要走核间通信),可以考虑用概率算法,维护一个不精确的负载因子(我这边实测概率算法效果很好)。
  8. lock free的程序编写和调试都比较麻烦,要仔细思考各种可能的并发场景,并尽量减少状态。

 

2 条留言  访客:0 条  博主:0 条

  1. 乒乓狂魔

    不需要split-order,你使用split-order就是为了把桶中数据进行分类,直接将桶中元素的hash&旧容量即可实现分类,结果等于0的在地位置的桶(即当前桶,如上述0桶)下,非0的在高位置的桶(地位置桶+旧容量,如上述4桶)下

    • LoopJump

      旧桶中元素有一部分要移动到新桶。哪些元素要移动,这个问题是trivial的。Split-Order要解决的是如何在不加桶锁的前提下原子地移动一个元素,这是一个lock free的hash扩展算法。
      另外,如果容量不是2的幂次,直接按位与也是有问题的吧。

给我留言