布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

引言

在介绍布隆过滤器之前我们首先引入几个场景。

场景一

在一个高并发的计数系统中，如果一个key没有计数，此时我们应该返回0，但是访问的key不存在，相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的key而导致的缓存被击穿？

有人说， 将这个key的值置为0存入缓存不就行了吗？确实，这是一个好的方案。大部分情况我们都是这样做的，当访问一个不存在的key的时候，设置一个带有过期时间的标志，然后放入缓存。不过这样做的缺点也很明显，浪费内存和无法抵御随机key攻击。

场景二

在一个黑名单系统中，我们需要设置很多黑名单内容。比如一个邮件系统，我们需要设置黑名单用户，当判断垃圾邮件的时候，要怎么去做。比如爬虫系统，我们要记录下来已经访问过的链接避免下次访问重复的链接。

在邮件很少或者用户很少的情况下，我们用普通数据库自带的查询就能完成。在数据量太多的时候，为了保证速度，通常情况下我们会将结果缓存到内存中，数据结构用hash表。这种查找的速度是o(1)，但是内存消耗也是惊人的。打个比方，假如我们要存10亿条数据，每条数据平均占据32个字节，那么需要的内存是64g，这已经是一个惊人的大小了。

一种解决思路

能不能有一种思路，查询的速度是o(1)，消耗内存特别小呢？前辈门早就想出了一个很好的解决方案。由于上面说的场景判断的结果只有两种状态（是或者不是，存在或者不存在），那么对于所存的数据完全可以用位来表示！数据本身则可以通过一个hash函数计算出一个key，这个key是一个位置，而这个key所对的值就是0或者1（因为只有两种状态），如下图：

布隆过滤器原理

上面的思路其实就是布隆过滤器的思想，只不过因为hash函数的限制，多个字符串很可能会hash成一个值。为了解决这个问题，布隆过滤器引入多个hash函数来降低误判率。

下图表示有三个hash函数，比如一个集合中有x，y，z三个元素，分别用三个hash函数映射到二进制序列的某些位上，假设我们判断w是否在集合中，同样用三个hash函数来映射，结果发现取得的结果不全为1，则表示w不在集合里面。

布隆过滤器处理流程

布隆过滤器应用很广泛，比如垃圾邮件过滤，爬虫的url过滤，防止缓存击穿等等。下面就来说说布隆过滤器的一个完整流程，相信读者看到这里应该能明白布隆过滤器是怎样工作的。

第一步：开辟空间

开辟一个长度为m的位数组（或者称二进制向量），这个不同的语言有不同的实现方式，甚至你可以用文件来实现。

第二步：寻找hash函数

获取几个hash函数，前辈们已经发明了很多运行良好的hash函数，比如bkdrhash，jshash，rshash等等。这些hash函数我们直接获取就可以了。

第三步：写入数据

将所需要判断的内容经过这些hash函数计算，得到几个值，比如用3个hash函数，得到值分别是1000，2000，3000。之后设置m位数组的第1000，2000，3000位的值位二进制1。

第四步：判断

接下来就可以判断一个新的内容是不是在我们的集合中。判断的流程和写入的流程是一致的。

误判问题

布隆过滤器虽然很高效（写入和判断都是o(1)，所需要的存储空间极小），但是缺点也非常明显，那就是会误判。当集素本纯衣合中的元素越来越多，二进制序列中的1的个数越来越多的时候，判断一个字符串是否在集合中就很容易误判，原本不在集合里面的字符串会被判断在集合里面。

数学推导

布隆过滤器原理十分简单，但是专升本考试成绩查询hash函数个数怎么去判断，误判率有多少？

假设二进制序列有m位，那么经过当一个字符串hash到某一位的概率为：

1m

也就是说当前位被反转为1的概率：

p(1)=1m

那么这一位没有被反转的概率为：

p(0)=1−1m

假设我们存入n各元素，使用k个hash函数，此时没有被翻转的概率为：

p(0)=(1−1m)nk

那什么情况下我们会误判呢，就是原本不应该被翻转的位，结果翻转了，也就是

p(误判)=1小龙虾专业−(1−1m)nk

由于只有k个hash函数同时误判了，整体才会被误判，最后误判的概率为

p(误判)=(1−(1−1m)nk)k

要使得误判率最低，那么我们需要求误判与m、n、k之间的关系，现在假设m和n固定，我们计算一下k。可以首先看看这个式子：

(1−1m)nk

由于我们的m很大，通常情况下我们会用2^32来作为m的值。上面的式子中含有一个重要极限

limx→∞(1+1x)x=e

因此误判率的式子可以写成

p(误判)=(1−(e)−nk/m)k

接下来令t=−n/m，两边同时取对数，求导，得到：

p′1p=ln(1−etk)+klnet(−etk)1−etk

让p′=0，则等式后面的为0，最后整理出来的结果是

(1−etk)ln(1−etk)=etklnetk

计算出来的k为ln2mn，约等于0.693mn，将k代入p(误判)，我们可以得到概率和m、n之间的关系，最后的结果

(1/2)ln2mn，约等于0.6185m/n

以上我们就得出了最佳hash函数个数以及误判率与mn之前的关系了。

下表是m与n比值在k个hash函数下面的误判率

m/nkk=1k=2k=3k=4k=5k=6k=7k=8
21.390.3930.400
32.080.2830.2370.253
42.770.2210.1550.1470.160
53.460.1810.1090.0920.0920.101
64.160.1540.08040.06090.05610.05780.0638
74.850.1330.06180.04230.03590.03470.0364
85.550.1180.04890.03060.0240.02170.02160.0229
96.240.1050.03970.02280.01660.01410.01330.01350.0145
106.930.09520.03290.01740.01180.009430.008440.008190.00846
117.620.08690.02760.01360.008640.00650.005520.005130.00509
128.320.080.02360.01080.006460.004590.003710.003290.00314
139.010.0740.02030.008750.004920.003320.002550.002170.00199
149.70.06890.01770.007180.003810.002440.001790.001460.00129
1510.40.06450.01560.005960.0030.001830.001280.0010.000852
1611.10.06060.01380.0050.002390.001390.0009350.0007020.000574
1711.80.05710.01230.004230.001930.001070.0006920.0004990.0衢州学院是几本00394
1812.50.0540.01110.003620.001580.0008390.0005190.000360.000275
1913.20.05130.009980.003120.00130.0006630.0003940.0002640.000194
2013.90.04880.009060.00270.001080.000530.0003030.0001960.00014
2114.60.04650.008250.002360.0009050.0004270.0002360.0001470.000101
2215.20.04440.007550.002070.0007640.0003470.0001850.0001127.46e-05
2315.90.04250.006940.001830.0006490.0002850.0001478.56e-055.55e-05
2416.60.04080.006390.001620.0005550.0002350.0001176.63e-054.17e-05
2517.30.03920.005910.001450.0004780.0001969.44e-055.18e-053.16e-05
26180.03770.005480.001290.0004130.0001647.66e-054.08e-052.42e-05
2718.70.03640.00510.001160.0003590.0001386.26e-053.24e-051.87e-05
2819.40.03510.004750.001050.0003140.0001175.15e-052.59e-051.46e-05
2920.10.03390.004440.0009490.0002769.96e-054.26e-052.09e-051.14e-05
3020.80.03280.004160.0008620.0002438.53e-053.55e-051.69e-059.01e-06
3121.50.03170.00390.0007850.0002157.33e-052.97e-051.38e-057.16e-06
3222.20.03080.003670.0007170.0001916.33e-052.5e-051.13e-055.73e-06

php+redis实现的布隆过滤器

由于redis实现了tbit和getbit操作，天然适合实现布隆过滤器，redis也有布隆过滤器插件。这里使用php+redis实现布隆过滤器。

首先定义一个hash函数集合类，这些hash函数不一定都用到，实际上32位hash值的用3个就可以了，具体的数量可以根据你的位序列总量和你需要存入的量决定，上面已经给出最佳值。

class bloomfilterhash{ /** * 由justin sobel编写的按位散列函数 */ public function jshash($string, $len = null) {  $hash = 1315423911;  $len || $len = strlen($string);  for ($i=0; $i<$len; $i++) {  $hash ^= (($hash << 5) + ord($string[$i]) + ($hash >> 2));  } return ($hash % 0xffffffff) & 0xffffffff; } /** * 该哈希算法基于at＆t贝尔实验室的peter j. weinberger的工作。 * aho thi和ulman编写的“编译器（原理，技术和工具）”一书建议使用采用此特定算法中的散列方法的散列函数。 */ public function pjwhash($string, $len = null) { $bitsinunsignedint = 4 * 8; //（unsigned int）（sizeof（unsigned int）* 8）;  $threequarters = 四个字的成语($bitsinunsignedint * 3) / 4;  $oneeighth = $bitsinunsignedint / 8;  $highbits = 0xffffffff << (int) ($bitsinunsignedint - $oneeighth);  $hash = 0;  $test = 0;  $len || $len = strlen($string);  for($i=0; $i<$len; $i++) { $hash = ($hash << (int) ($oneeighth)) + ord($string[$i]); } $test = $hash & $highbits; if ($test != 0) { $hash = (($hash ^ ($test >> (int)($threequarters))) & (~$highbits));  } return ($hash % 0xffffffff) & 0xffffffff; } /** * 类似于pjw hash功能，但针对32位处理器进行了调整。它是基于unix的系统上的widley使用哈希函数。 */ public function elfhash($string, $len = null) { $hash = 0; $len || $len = strlen($string);  for ($i=0; $i<$len; $i++) {   $hash = ($hash << 4) + ord($string[$i]); $x = $hash & 0xf0000000; if ($x != 0) { $hash ^= ($x >> 24);   }   $hash &= ~$x;  } return ($hash % 0xffffffff) & 0xffffffff; } /** * 这个哈希函数来自brian kernighan和dennis ritchie的书“the c programming language”。 * 它是一个简单的哈希函数，使用一组奇怪的可能种子，它们都构成了31 .... 31 ... 31等模式，它似乎与djb哈希函数非常相似。 */ public function bkdrhash($string, $len = null) {  $ed = 131; # 31 131 1313 13131 131313 etc..  $hash = 0;  $len || $len = strlen($string);  for ($i=0; $i<$len; $i++) {   $hash = (int) (($hash * $ed) + ord($string[$i]));  } return ($hash % 0xffffffff) & 0xffffffff; } /** * 这是在开源sdbm项目中使用的首选算法。 * 哈希函数似乎对许多不同的数据集具有良好的总体分布。它似乎适用于数据集中元素的msb存在高差异的情况。 */ public function sdbmhash($string, $len = null) { $hash = 0; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) (ord($string[$i]) + ($hash << 6) + ($hash << 16) - $hash); } return ($hash % 0xffffffff) & 0xffffffff; } /** * 由daniel j. bernstein教授制作的算法，首先在unet新闻组comp.lang.c上向世界展示。 * 它是有史以来发布的最有效的哈希函数之一。 */ public function djbhash($string, $len = null) { $hash = 5381; $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) (($hash << 5) + $hash) + ord($string[$i]); } return ($hash % 0xffffffff) & 0xffffffff; } /** * donald e. knuth在“计算机编程艺术第3卷”中提出的算法，主题是排序和搜索第6.4章。 */ public function dekhash($string, $len = null) { $len || $len = strlen($string); $hash = $len; for ($i=0; $i<$len; $i++) { $hash = (($hash << 5) ^ ($hash >> 27)) ^ ord($string[$i]); } return ($hash % 0xffffffff) & 0xffffffff; } /** * 参考 /d/file/titlepic/ */ public function fnvhash($string, $len = null) { $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619 $hash = 2166136261; //32位的offt $len || $len = strlen($string); for ($i=0; $i<$len; $i++) { $hash = (int) ($hash * $prime) % 0xffffffff; $hash ^= ord($string[$i]); } return ($hash % 0xffffffff) & 0xffffffff; }}

接着就是连接redis来进行操作

/** * 使用redis实现的布隆过滤器 */abstract class bloomfilterredis{ /** * 需要使用一个方法来定义bucket的名字 */ protected $bucket; protected $hashfunction; public function __construct($config, $id) { if (!$this->bucket || !$this->hashfunction) { throw new exception("需要定义bucket和hashfunction", 1); } $this->hash = new bloomfilterhash; $this->redis = new yourredis; //假设这里你已经连接好了 } /** * 添加到集合中 */ public function add($string) { $pipe = $this->redis->multi(); foreach ($this->hashfunction as $function) { $hash = $this->hash->$function($string); $pipe->tbit($this->bucket, $hash, 1); } return $pipe->exec(); } /** * 查询是否存在, 存在的一定会存在, 不存在有一定几率会误判 */ public function exists($string) { $pipe = $this->redis->multi(); $len = strlen($string); foreach ($this->hashfunction as $function) { $hash = $this->hash->$function($string, $len); $pipe = $pipe->getbit($this->bucket, $hash); } $res = $pipe->exec(); foreach ($res as $bit) { if ($bit == 0) { return fal; } } return true; }}

上面定义的是一个抽象类，如果要使用，可以根据具体的业务来使用。比如下面是一个过滤重复内容的过滤器。

/** * 重复内容过滤器 * 该布隆过滤器总位数为2^32位, 判断条数为2^30条. hash函数最优为3个.(能够容忍最多的hash函数个数) * 使用的三个hash函数为 * bkdr, sdbm, jshash * * 注意, 在存储的数据量到2^30条时候, 误判率会急剧增加, 因此需要定时判断过滤器中的位为1的的数量是否超过50%, 超过则需要清空. */class filterepeatedcomments extends bloomfilterredis{ /** * 表示判断重复内容的过滤器 * @var string */ protected $bucket = 'rptc'; protected $hashfunction = array('bkdrhash', 'sdbmhash', 'jshash');}

总结

以上所述是www.887551.com给大家介绍的布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法，希望对大家有所帮助！