布隆过滤器(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/n k k=1 k=2 k=3 k=4 k=5 k=6 k=7 k=8
2 1.39 0.393 0.400      
3 2.08 0.283 0.237 0.253     
4 2.77 0.221 0.155 0.147 0.160    
5 3.46 0.181 0.109 0.092 0.092 0.101   
6 4.16 0.154 0.0804 0.0609 0.0561 0.0578 0.0638  
7 4.85 0.133 0.0618 0.0423 0.0359 0.0347 0.0364  
8 5.55 0.118 0.0489 0.0306 0.024 0.0217 0.0216 0.0229 
9 6.24 0.105 0.0397 0.0228 0.0166 0.0141 0.0133 0.0135 0.0145
10 6.93 0.0952 0.0329 0.0174 0.0118 0.00943 0.00844 0.00819 0.00846
11 7.62 0.0869 0.0276 0.0136 0.00864 0.0065 0.00552 0.00513 0.00509
12 8.32 0.08 0.0236 0.0108 0.00646 0.00459 0.00371 0.00329 0.00314
13 9.01 0.074 0.0203 0.00875 0.00492 0.00332 0.00255 0.00217 0.00199
14 9.7 0.0689 0.0177 0.00718 0.00381 0.00244 0.00179 0.00146 0.00129
15 10.4 0.0645 0.0156 0.00596 0.003 0.00183 0.00128 0.001 0.000852
16 11.1 0.0606 0.0138 0.005 0.00239 0.00139 0.000935 0.000702 0.000574
17 11.8 0.0571 0.0123 0.00423 0.00193 0.00107 0.000692 0.000499 0.000394
18 12.5 0.054 0.0111 0.00362 0.00158 0.000839 0.000519 0.00036 0.000275
19 13.2 0.0513 0.00998 0.00312 0.0013 0.000663 0.000394 0.000264 0.000194
20 13.9 0.0488 0.00906 0.0027 0.00108 0.00053 0.000303 0.000196 0.00014
21 14.6 0.0465 0.00825 0.00236 0.000905 0.000427 0.000236 0.000147 0.000101
22 15.2 0.0444 0.00755 0.00207 0.000764 0.000347 0.000185 0.000112 7.46e-05
23 15.9 0.0425 0.00694 0.00183 0.000649 0.000285 0.000147 8.56e-05 5.55e-05
24 16.6 0.0408 0.00639 0.00162 0.000555 0.000235 0.000117 6.63e-05 4.17e-05
25 17.3 0.0392 0.00591 0.00145 0.000478 0.000196 9.44e-05 5.18e-05 3.16e-05
26 18 0.0377 0.00548 0.00129 0.000413 0.000164 7.66e-05 4.08e-05 2.42e-05
27 18.7 0.0364 0.0051 0.00116 0.000359 0.000138 6.26e-05 3.24e-05 1.87e-05
28 19.4 0.0351 0.00475 0.00105 0.000314 0.000117 5.15e-05 2.59e-05 1.46e-05
29 20.1 0.0339 0.00444 0.000949 0.000276 9.96e-05 4.26e-05 2.09e-05 1.14e-05
30 20.8 0.0328 0.00416 0.000862 0.000243 8.53e-05 3.55e-05 1.69e-05 9.01e-06
31 21.5 0.0317 0.0039 0.000785 0.000215 7.33e-05 2.97e-05 1.38e-05 7.16e-06
32 22.2 0.0308 0.00367 0.000717 0.000191 6.33e-05 2.5e-05 1.13e-05 5.73e-06

php+Redis实现的布隆过滤器

由于Redis实现了setbit和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 Sethi和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)
 {
  $seed = 131; # 31 131 1313 13131 131313 etc..
  $hash = 0;
  $len || $len = strlen($string);
  for ($i=0; $i<$len; $i++) {
   $hash = (int) (($hash * $seed) + 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教授制作的算法,首先在usenet新闻组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;
 }

 /**
 * 参考 http://www.isthe.com/chongo/tech/comp/fnv/
 */
 public function FNVHash($string, $len = null)
 {
 $prime = 16777619; //32位的prime 2^24 + 2^8 + 0x93 = 16777619
 $hash = 2166136261; //32位的offset
 $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->setBit($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 false;
 }
 }
 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');
}

总结

以上所述是小编给大家介绍的布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法,希望对大家有所帮助!

时间: 2019-12-07

Python+Redis实现布隆过滤器

布隆过滤器是什么 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 布隆过滤器的基本思想 通过一种叫作散列表(又叫哈希表,Hash table)的数据结构.它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点.这样一来,我们只要看看这个点是不是1就可以知道集合中有没

Redis 中的布隆过滤器的实现

什么是『布隆过滤器』 布隆过滤器是一个神奇的数据结构,可以用来判断一个元素是否在一个集合中.很常用的一个功能是用来去重.在爬虫中常见的一个需求:目标网站 URL 千千万,怎么判断某个 URL 爬虫是否宠幸过?简单点可以爬虫每采集过一个 URL,就把这个 URL 存入数据库中,每次一个新的 URL 过来就到数据库查询下是否访问过. select id from table where url = 'https://jaychen.cc' 但是随着爬虫爬过的 URL 越来越多,每次请求前都要访问数据

Redis实现布隆过滤器的方法及原理

布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难. 本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器. 应用场景 1.50亿个电话号码,现有10万个电话号码,如何判断这10万个是否已经存在在50亿个之中?(可能方案:数据库,set, hyperloglog) 2.新闻客户端看新闻时,它会不

Java实现布隆过滤器的方法步骤

前言 记得前段时间的文章么?redis使用位图法记录在线用户的状态,还是需要自己实现一个IM在线用户状态的记录,今天来讲讲另一方案,布隆过滤器 布隆过滤器的作用是加快判定一个元素是否在集合中出现的方法.因为其主要是过滤掉了大部分元素间的精确匹配,故称为过滤器. 布隆过滤器 在日常生活工作,我们会经常遇到这的场景,从一个Excel里面检索一个信息在不在Excel表中,还记得被CTRL+F支配的恐惧么,不扯了,软件开发中,一般会使用散列表来实现,Hash Table也叫哈希表,哈希表的优点是快速准确

python实现布隆过滤器及原理解析

在学习redis过程中提到一个缓存击穿的问题, 书中参考的解决方案之一是使用布隆过滤器, 那么就有必要来了解一下什么是布隆过滤器.在参考了许多博客之后, 写个总结记录一下. 一.布隆过滤器简介 什么是布隆过滤器? 本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 "某样东西一定不存在或者可能存在". 相比于传统的 Set.Map 等数据结构,它更高效

布隆过滤器(Bloom Filter)的Java实现方法

布隆过滤器原理很简单:就是把一个字符串哈希成一个整数key,然后选取一个很长的比特序列,开始都是0,在key把此位置的0变为1:下次进来一个字符串,哈希之后的值key,如果在此比特位上的值也是1,那么就说明这个字符串存在了. 如果按照上面的做法,那就和哈希算法没有什么区别了,哈希算法还有重复的呢. 布隆过滤器是将一个字符串哈希成多个key,我还是按照书上的说吧. 先建立一个16亿二进制常量,然后将这16亿个二进制位全部置0.对于每个字符串,用8个不同的随机产生器(F1,F2,.....,F8)产

布隆过滤器的概述及Python实现方法

布隆过滤器 布隆过滤器是一种概率空间高效的数据结构.它与hashmap非常相似,用于检索一个元素是否在一个集合中.它在检索元素是否存在时,能很好地取舍空间使用率与误报比例.正是由于这个特性,它被称作概率性数据结构(probabilistic data structure). 空间效率 我们来仔细地看看它的空间效率.如果你想在集合中存储一系列的元素,有很多种不同的做法.你可以把数据存储在hashmap,随后在hashmap中检索元素是否存在,hashmap的插入和查询的效率都非常高.但是,由于ha

C++ 数据结构之布隆过滤器

布隆过滤器 一.历史背景知识 布隆过滤器(Bloom Filter)是1970年由布隆提出的.它实际上是一个很长的二进制向量和一系列随机映射函数.布隆过滤器可以用于检索一个元素是否在一个集合中.它的优点是空间效率和查询时间都远超过一般的算法,缺点是有一定的误识别率和删除错误.而这个缺点是不可避免的.但是绝对不会出现识别错误的情况出现(即假反例False negatives,如果某个元素确实没有在该集合中,那么Bloom Filter 是不会报告该元素存在集合中的,所以不会漏报) 在 FBI,一个

JAVA实现较完善的布隆过滤器的示例代码

布隆过滤器是可以用于判断一个元素是不是在一个集合里,并且相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势.布隆过滤器存储空间和插入/查询时间都是常数.但是它也是拥有一定的缺点:布隆过滤器是有一定的误识别率以及删除困难的.本文中给出的布隆过滤器的实现,基本满足了日常使用所需要的功能. 0 0 0 0 0 0 0 0 0 0 先简单来说一下布隆过滤器.其实现方法就是:利用内存中一个长度为M的位数组B并初始化里面的所有位都为0,如下面的表格所示: 然后我们根据H个不同的散列函数,对传进来