实现一个简单的高性能布隆过滤器

title: 实现一个简单的高性能布隆过滤器 date: 2019-03-17 12:26:00 tags:

Bloom Filter
数据结构与算法

布隆过滤器是什么

它是一个数据结构，而且一般传统的科班的算法书不会讲到。它可以用来判断某个元素是否在集合内，具有执行速度快和内存占用小的特点。

布隆过滤器高效的插入和查询代价就是：Bloom Filter是一个基于概率的数据结构：它只能告诉我们一个元素的以下两种查询结果：

绝对不在集合内
可能在集合内

针对第二点，也就说可能会有false positive。朴素的布隆过滤器一般是不支持删除操作的，但是也有针对具体应用而产生支持删除操作的布隆过滤器。这个延伸问题我不打算涉及，感兴趣可以查找下相关论文。

布隆过滤器的简单原理以及实现

基本原理

布隆过滤器的一个基础的数据结构就是一个Bit Vector 。其原理非常简单，这个bit 数组是带有下标索引的，一个索引对应一个bit状态，实际就是0或1。一般状态1就是元素存在的标识，状态0就是元素不存在的标识。

00000000000100010100101010101010101010101010100101010000001111100111

以上的文本示例就是一个长度为N的比特向量，当然初始状态但是是全为0，但一旦向布隆过滤器插入一个元素的时候，需要对这个元素进行多次hash运算，一次运算的结果为bit vector的一个下标索引，然后把这个索引对应的bit状态设置为1，当多次Hash运算计算下标完成并设置为1，这样元素就算插入完成了。查询的时候也是把元素进行多次hash运算，然后检查对应索引上的bit状态是否为1，如果多次运算后的bit为1就是可能存在，如果其中有一个bit为0，就是绝对不存在。

以上就是布隆过滤器的最基本原理了。是不是很简单？但是要对其进行分析就需要一定难度了，其中需要你懂些基本的数学知识，比如如果你要设计一个布隆过滤器，以下几个方面需要你来取舍：

长度为m的比特向量，这个长度需要多长？m需要多大？也就是说需要几个bit？
进行多次hash运算，这个多次是需要不同的k个Hash函数的，那么这k个Hash函数怎么选择？ MD5，SHA256还是其他？这个K的最优值又是什么？
已知当前比特向量已经插入n个元素了，那么过滤器判断的误报率(false positive)又是怎样的？毕竟是概率性数据结构。

如果以上三个要点实现过滤器的设计者没有考虑清楚，很可能他设计出来的过滤器根本不可用，误报率上升到一定程度就没有意义了。

Hash函数的选择

布隆过滤器里的Hash函数最好是要选择彼此独立的, 而且是要离散均匀分布的。也就是说Hash函数的结果要等可能（等概率）的落在一个[a, b]区间任的一点（点是非连续的，离散的），如果概率不等，那么在某个bit下标区间内误报的概率就会上升。当然最后，Hash函数还要尽可能的快，虽然是Hash函数时间复杂度都是常数级别，最好是降低下常数吧。

所以适合于做布隆过滤器的Hash函数有：

murmur系列Hash函数
Fowler–Noll–Vo系列Hash函数

当然还有其他的。如果你仔细分析，你会发现以上两个系列的Hash函数都不是为密码学设计的，一般来说不是以密码学为目的设计的Hash函数速度会更快。所以MD5， SHA-1， SHA-2这些算法就不太合适用来做布隆过滤器的Hash函数。

如果你有所怀疑的话，那么可以参考一下这个PR，当把布隆过滤器的实现从MD5切换到murmur时，极大的提高了性能。

当然，也有其他布隆过滤器采用为密码学设计的Hash算法的，这里暂时先不去研究为什么了。

比特向量已经设计为多大？

布隆过滤器的一个优良特性就是可以调整过滤器的误报率。拥有一个大的比特向量的过滤器会拥有比一个相对较小的过滤器有着更低的误报率。

误报率会近似于以下公式：

a1ac93f3gy1g15t747vd0j203p01q3ya

所以你只需要先确定可能插入的数据集的容量大小n, 然后再调整k和m来为你的场景配置过滤器。

所以根据以上公式，你不得不带出来另一个问题，就是K的取值是多少？也就是说，几个Hash函数才合适？

布隆过滤器使用的Hash函数越多运行速度就会越慢。但是如果Hash函数过少，又会遇到误报率高的问题。所以这个问题上需要认真考虑权衡。

在创建布隆过滤器的时候需要确定k的值，也就是说你需要提前规划n的变动范围。而一旦你这样做了，你依然需要确定m（比特向量长度）和 k (Hash函数的个数）的值。

似乎这是一个十分困难的优化问题，但幸运的是，对于给定的m和n，有一个函数可以帮我们确定最优的k值(公式来自于wiki):

a1ac93f3gy1g15tqjkxm7j209701tglf

当然，有篇论文叫做Building a better bloom filter（Adam Kirsch）已经证明了，其中布隆过滤器只需要2个Hash函数就可以模拟k个Hash函数，并且不会降低精准度。论文中指出以下公式：

Gi(x) = H1(x) +iH2(x).

H1，H2分别是两个互相独立并且离散均匀分布的两个Hash函数，其中 0 <= i <= k - 1 。

当然对于比特向量的索引下标就是最终Hash的结果对向量大小取模就可以了：

index = [hash-value] mod [size of vector]

所以，可以通过以下4个步骤来确定过滤器的大小：

1.确定n的变动范围
2.选定m的值
3.通过公式计算k的最优值（k可以用2个Hash函数的线性组合代替）
4.通过m，n，k计算误报率，如果误报率不在你接受的限度，那么你需要重回步骤2，否则就结束

基本实现

如果用C++模拟比特向量，可以用std::vector\<bool>来模拟，一般来说别担心bool在vector里面每个元素是占sizeof(bool)个字节。反而这很可能是被优化了，在bool向量中，bool可能被优化成只占一个Bit 。当然这具体看实现（implementation defined），一般来说占用空间是被优化掉了。

过滤器的add方法:

// m = size of bit vector
// Gi(x)= H1(x) + i * H2(x)
// index = Gi(x) mod m
uint64_t indexHash(uint8_t i, uint64_t hashA, uint64_t hashB, uint64_t m)
{
    return (hashA + i * hashB) % m;
}

// you need to serialize an object to bytes array
void addObject(const std::vector<uint8_t>& data)
{
    // you need to choose HashA and HashB
    hash_a = HashA(data.data(),data.size());
    hash_b = HashB(data.data(),data.size());

    for(int i = 0; i <= k - 1; ++i)
    {
        uint64_t index = indexHash(i, hash_a, hash_b, bit_vector.size()); 
        bit_vector[index] = true;
    }
}

过滤器的contains方法：

// you need to serialize an object to bytes array
bool maybe_contains(const std::vector<uint8_t>& data)
{
    hash_a = HashA(data.data(),data.size());
    hash_b = HashB(data.data(),data.size());

    for(int i = 0; i <= k - 1; ++i)
    {
        uint64_t index = indexHash(i, hash_a, hash_b, bit_vector.size()); 
        if(!bit_vector[index]) return false;
    }

    return true;
}

以上实现的过滤，查找在亿级对象数据量中判断某对象是否存在基本平均响应在纳秒时间。

一般来说，如果不是出什么特别的差错，在大部分场景下误报率几乎可以忍受。

EOF

AlexiaChen / AlexiaChen.github.io