无锁哈希表

2013-07-15

前段时间看到酷壳中一篇无锁哈希表的 文章,以及伯乐在线上面一篇 文章,正好研究一下这个主题。

伯乐在线上那篇号称“世界上最简单的无锁哈希表”,用开地址+线性探查实现的哈希表,然后对数据元素用原子操作,看完基本上没什么价值。原因很简单:不支持扩容。而正如酷壳上那篇文章说的,扩容才是难点。“HashMap主要有插入、删除、查找以及ReHash四种基本操作。一个典型的HashMap实现,会用到一个数组,数组的每项元素为一个节点的链表。对于此链表,我们可以利用上文提到的操作方法,执行插入、删除以及查找操作,但对于ReHash操作则比较困难。”

按常规思路,扩容时涉及了将结点从旧链中移除,将结点插入到新链,需要三次指针操作,而这三次指针操作必须同时完成,才能保证移动操作的原子性。显然这跟把冰箱门打开,把大象放进去,再把冰箱门关上一样不靠谱。因为CAS操作每次只能保证一个变量的值被原子性地验证并更新,无法满足同时验证并更新三个指针的需求。

关于无锁哈希表看过另一个实现,是用哈希树的方式,每一层32个孩子,这样就可以用字节长度做一个32位的位图,通过这个位图来保护访问的原子性。不过酷壳上的这篇比较巧妙,巧妙地避免了扩容时的节点移动操作,通过引入哨兵结点,做成了顺序插入。具体的原理就不说了,可以看原文,下面只说说我在实现过程中遇到的一些细节。

按位翻转

遇到的第一个问题就是二进制位反转。太久不玩这种底层的代码,不太顺了。第一次取出全部奇数位,跟偶数位交换位置,然后两位一组取出,交换,接着四位一组取出交换,依次做下去就可以将整个数据按位交换了。有一点类型面试题中,按单词交换"hello world"变成"world hello"的做法,先单词反转,再整句反转。

func bitReverse(v uint32) (ret uint32) {
    mask := []uint32{
        0x55555555, //...010101010101
        0xaaaaaaaa, //...101010101010
        0x33333333, //...001100110011
        0xcccccccc, //...110011001100
        0x0f0f0f0f, //...00001111
        0xf0f0f0f0, //...11110000
        0x00ff00ff, //...0000000011111111
        0xff00ff00, //...1111111100000000
        0x0000ffff,
        0xffff0000,
    }
    ret = v
    for i := uint32(0); i < 5; i++ {
        tmp1 := ret & mask[2*i]
        tmp1 = tmp1 << (1 << i)
        tmp2 := ret & mask[2*i+1]
        tmp2 = tmp2 >> (1 << i)
        ret = tmp1 | tmp2
    }
    return
}

Go中的CompareAndSwapPointer函数就是个坑

接着是链表中的CAS操作。不得不吐糟一下Go提供的这个api真的很误导。atomic.CompareAndSwapPointer是做不出来原子地给指针赋值的,被坑惨了。因为它的第一个参数是unsafe.Pointer,而(unsafe.Pointer)(&p)编译会报错。做完类型转换得到的是一个“左值”,左值是没法取地址的。而如果先tmp := unsafe.Pointer(p),再&tmp,这么做是无用的,改的是临时变量tmp而不是原始的p。

想取到p的地址了当参数传给CompareAndSwapPointer都是做不到的。于是我就想绕过这个,弄一个*unsafe.Pointer的东西出来,假设叫pp,再传pp给CompareAndSwapPointer。这个也搞不定...

最后我算是明白了,unsafe.CompareAndSwapPointer这个函数完全是个鸡肋,用它根本没法完成原子性的给某个非unsafe.Pointer的指针赋值(有点绕,我的意思是说它没法给*node这种其它非unsafe.Pointer类型指针赋值)。解决方式是用atomic.CompareAndSwapUintptr这个函数。利用unsafe.Pointer可以向指针转化,以及uintptr刚好是一个指针大小。

atomic.CompareAndSwapUintptr((*uintptr)(unsafe.Pointer(&prev.next)),
        uintptr(unsafe.Pointer(next)),
        uintptr(unsafe.Pointer(p)))

递归初始化bucket

插入操作中,先判断hash & mask之后的插入位置,如果该位置未初始化,会先进行初始化再插入。初始化某个bucket是递归进行的,先递归地初始化它的父结点位置,再初始化它。其实初始化就是插入一个哨兵结点。这个是有点巧妙的地方,如果不自己动手写的话很难注意到这种细节。最后都变成调用listInsert的操作了,只要按无锁链表做就够了。无锁链表还是相对比较简单的。

我开始在想,要不要做成递归初始化这样子啊?直接在开始时就把所有哨兵结点都分配好不就行了?直到后面写rehash才明白其中的精妙:rehash其实就是新插入一些哨兵结点,说白了就是在做递归的初始化bucket的操作。所以rehash和这里本质上是同一个操作。

我还是将rehash说细点吧。在这个实现中,没有结点的移动,没有将结点从旧表中删除,再插入到新表的过程。只有插入一个哨兵将分裂后桶中的点隔开成两部分。结点插入时插入操作,扩容也是插入操作,只不过一个是插入普通节点,一个是插入哨兵结点。

关于一个线程在做扩容过程中,另一个线程做了插入,如何保持一致性的问题,那篇文章中没有细说。我实现的做法是,先更新哈希表中的桶数组,但是不更新哈希表的当前mask位数bits。然后去做扩容操作,也就是插入哨兵结点啦,这时在其它线程中看哈希表状态跟旧表没两样,而扩容线程看它差不多是个新表了。两个表共用的同一个结点的链表,插入都是链表插入,可以保证原子性。扩容完后将mask位数更新成新表位数就完成了。So easy!

好啦,无图无真相,没 代码我说个JB。

数据结构hash无锁CAS