cuckoo filter 简介

    介绍个小东西， cuckoo filter （布谷鸟过滤器）。可以用作替代bloom filter。
    
    介绍这个东东前先简单介绍一下 cuckoo hash。 cuckoo hash 是一种hash表， 在最坏情况下查找也是常数时间， 它主要是在 hash 冲突时处理方法比较特殊。传统hash表在发生hash冲突的时候， 通过把冲突的item挂在一张链表上解决（当然还有其它方式， 这里不讨论）， 在查询时需要遍历这个链表。 这样最坏情况下查询时间其实是不确定的。而cuckoo hash。 把一个hash表分成相等的两份， 采用两个hash函数记作h1(.), h2(.)。 这样任何一个key 通过h1和h2可以计算得到2个bucket。这个key就一定存在这两个bucket中。 查找的时候， 至多查找两次。插入数据时， 看这两个bucket是否为空， 如果任何一个空闲， 插入就好了， 如果都不空闲， 则挑一个bucket， 把当前值插入到这个bucket中， 把bucket中原来的值踢出来。 把被踢出来的值， 插入这个被踢出值的另外一个bucket中。 如果那个bucket空闲则插入结束， 否则踢出原有值， 反复这个过程。因为算法如同布谷鸟下蛋一样， 找个巢就下蛋， 如果巢里已经有蛋了， 就把原有的蛋从巢里踢出去， 所以叫做cuckoo hash。下面这个图从维基百科上拷贝过来的， 说明了这个插入过程。

k	h(k)	h'(k)
20	9	1
50	6	4
53	9	4
75	9	6
100	1	9
67	1	6
105	6	9
3	3	0
36	3	3
39	6	3

1. table for h(k)
	20	50	53	75	100	67	105	3	36	39
0
1					100	67	67	67	67	100
2
3								3	3	36
4
5
6		50	50	50	50	50	105	105	105	50
7
8
9	20	20	20	20	20	20	53	53	53	75
10

2. table for h'(k)
	20	50	53	75	100	67	105	3	36	39
0										3
1							20	20	20	20
2
3									36	39
4			53	53	53	53	50	50	50	53
5
6				75	75	75	75	75	75	67
7
8
9						100	100	100	100	105
10

    cuckoo hash 适合大并发的读， 少量的写的应用场景。 而且空间利用率可以做到很高。 如果你有足够的空间， 以至于hash 冲突基本不发生， 这东西对你没用。

    下面介绍 cuckoo filter。不清楚 bloom filter的同学请先补一下bloom filter知识。cuckoo filter里不会存储原信息， 只存储指纹信息， 那么在一个iterm被挤出， 需要重新找位置的时候， 怎么计算这个iterm的另外一个位置呢（没有原来的key， 知道两个hash函数也没法计算）？cuckoo 采用只需要指纹信息就能找到第二个bucket的方式， 技巧在这里：
    i1= HASH(x),
    i2= i1 ⊕HASH(x′s fingerprint)
    其中 ⊕ 是异或运算。所以：
    j = i ⊕HASH(fingerprint)
    也就是说， 知道了当前的bucket（i）， 知道指纹信息， 就可以计算出另外一个bucket（j）。
    要从cuckoo filter里删除一个元素， 只需要从cuckoo hash里查到这个元素匹配的指纹， 从表中删除即可。这是因为即便有两个元素， 他们的指纹信息相同， 并且计算得到的i1也相同（从而i2必然也相同）， 按照刚才的方式删除也是安全的。当另外的元素来查找的时候， 仍然能够查到。
    这里有一点要注意， 如果要支持删除， 当插入重复数据的时候， 每次都需要存储一次指纹信息。这很容易造成插入的失败， 所以要限制重复数据的插入， 如果不支持删除则无此问题。
    原文里提到为了提高hash表的占用率（occupancy）， 在一个bucket下存储多个指纹是非常有效的， 当然这要增加查找时候的比较次数同时增加指纹的长度来保持false postive的比率（可以这样理解， 一个bucket存放更多的指纹， 可以降低hash表本身的大小， hash表减小， 其实降低了区分度， 增加指纹长度， 又提高了区分度）。他们测试的平衡点是每个bucket存4个指纹。
    关于指纹信息， 稍微提一下， 大家不要一下子想到128位md5. 存储是需要成本的， 所以这里的指纹可能就是一个12bits。 指纹位数的确定和影响， 请见原文。
    当一个cuckoo hash表中元素达到一定量的时候， 插入就很容易失败， 这时需要扩展hash表来容纳更多元素。 但是对于bloom filter来说， 可以一直插入元素， 不过这时 false postive的比率会很高（基本就失去作用了）， 如果要保持这个合理的比率 bloom filter也需要扩展。

    原文可以通过 cuckoo filter:better than bloom 搜索到, 请希望了解更多细节的同学自行查看原文。