引言

在介紹布隆過(guò)濾器之前我們首先引入幾個(gè)場(chǎng)景。

場(chǎng)景一

在一個(gè)高并發(fā)的計(jì)數(shù)系統(tǒng)中，如果一個(gè)key沒(méi)有計(jì)數(shù)，此時(shí)我們應(yīng)該返回0，但是訪問(wèn)的key不存在，相當(dāng)于每次訪問(wèn)緩存都不起作用了。那么如何避免頻繁訪問(wèn)數(shù)量為0的key而導(dǎo)致的緩存被擊穿？

有人說(shuō)， 將這個(gè)key的值置為0存入緩存不就行了嗎？確實(shí)，這是一個(gè)好的方案。大部分情況我們都是這樣做的，當(dāng)訪問(wèn)一個(gè)不存在的key的時(shí)候，設(shè)置一個(gè)帶有過(guò)期時(shí)間的標(biāo)志，然后放入緩存。不過(guò)這樣做的缺點(diǎn)也很明顯，浪費(fèi)內(nèi)存和無(wú)法抵御隨機(jī)key攻擊。

場(chǎng)景二

在一個(gè)黑名單系統(tǒng)中，我們需要設(shè)置很多黑名單內(nèi)容。比如一個(gè)郵件系統(tǒng)，我們需要設(shè)置黑名單用戶，當(dāng)判斷垃圾郵件的時(shí)候，要怎么去做。比如爬蟲系統(tǒng)，我們要記錄下來(lái)已經(jīng)訪問(wèn)過(guò)的鏈接避免下次訪問(wèn)重復(fù)的鏈接。

在郵件很少或者用戶很少的情況下，我們用普通數(shù)據(jù)庫(kù)自帶的查詢就能完成。在數(shù)據(jù)量太多的時(shí)候，為了保證速度，通常情況下我們會(huì)將結(jié)果緩存到內(nèi)存中，數(shù)據(jù)結(jié)構(gòu)用hash表。這種查找的速度是O(1)，但是內(nèi)存消耗也是驚人的。打個(gè)比方，假如我們要存10億條數(shù)據(jù)，每條數(shù)據(jù)平均占據(jù)32個(gè)字節(jié)，那么需要的內(nèi)存是64G，這已經(jīng)是一個(gè)驚人的大小了。

一種解決思路

能不能有一種思路，查詢的速度是O(1)，消耗內(nèi)存特別小呢？前輩門早就想出了一個(gè)很好的解決方案。由于上面說(shuō)的場(chǎng)景判斷的結(jié)果只有兩種狀態(tài)（是或者不是，存在或者不存在），那么對(duì)于所存的數(shù)據(jù)完全可以用位來(lái)表示！數(shù)據(jù)本身則可以通過(guò)一個(gè)hash函數(shù)計(jì)算出一個(gè)key，這個(gè)key是一個(gè)位置，而這個(gè)key所對(duì)的值就是0或者1（因?yàn)橹挥袃煞N狀態(tài)），如下圖：

布隆過(guò)濾器原理

上面的思路其實(shí)就是布隆過(guò)濾器的思想，只不過(guò)因?yàn)閔ash函數(shù)的限制，多個(gè)字符串很可能會(huì)hash成一個(gè)值。為了解決這個(gè)問(wèn)題，布隆過(guò)濾器引入多個(gè)hash函數(shù)來(lái)降低誤判率。

下圖表示有三個(gè)hash函數(shù)，比如一個(gè)集合中有x，y，z三個(gè)元素，分別用三個(gè)hash函數(shù)映射到二進(jìn)制序列的某些位上，假設(shè)我們判斷w是否在集合中，同樣用三個(gè)hash函數(shù)來(lái)映射，結(jié)果發(fā)現(xiàn)取得的結(jié)果不全為1，則表示w不在集合里面。

布隆過(guò)濾器處理流程

布隆過(guò)濾器應(yīng)用很廣泛，比如垃圾郵件過(guò)濾，爬蟲的url過(guò)濾，防止緩存擊穿等等。下面就來(lái)說(shuō)說(shuō)布隆過(guò)濾器的一個(gè)完整流程，相信讀者看到這里應(yīng)該能明白布隆過(guò)濾器是怎樣工作的。

第一步：開辟空間

開辟一個(gè)長(zhǎng)度為m的位數(shù)組（或者稱二進(jìn)制向量），這個(gè)不同的語(yǔ)言有不同的實(shí)現(xiàn)方式，甚至你可以用文件來(lái)實(shí)現(xiàn)。

第二步：尋找hash函數(shù)

獲取幾個(gè)hash函數(shù)，前輩們已經(jīng)發(fā)明了很多運(yùn)行良好的hash函數(shù)，比如BKDRHash，JSHash，RSHash等等。這些hash函數(shù)我們直接獲取就可以了。

第三步：寫入數(shù)據(jù)

將所需要判斷的內(nèi)容經(jīng)過(guò)這些hash函數(shù)計(jì)算，得到幾個(gè)值，比如用3個(gè)hash函數(shù)，得到值分別是1000，2000，3000。之后設(shè)置m位數(shù)組的第1000，2000，3000位的值位二進(jìn)制1。

第四步：判斷

接下來(lái)就可以判斷一個(gè)新的內(nèi)容是不是在我們的集合中。判斷的流程和寫入的流程是一致的。

誤判問(wèn)題

布隆過(guò)濾器雖然很高效（寫入和判斷都是O(1)，所需要的存儲(chǔ)空間極小），但是缺點(diǎn)也非常明顯，那就是會(huì)誤判。當(dāng)集合中的元素越來(lái)越多，二進(jìn)制序列中的1的個(gè)數(shù)越來(lái)越多的時(shí)候，判斷一個(gè)字符串是否在集合中就很容易誤判，原本不在集合里面的字符串會(huì)被判斷在集合里面。

數(shù)學(xué)推導(dǎo)

布隆過(guò)濾器原理十分簡(jiǎn)單，但是hash函數(shù)個(gè)數(shù)怎么去判斷，誤判率有多少？

假設(shè)二進(jìn)制序列有m位，那么經(jīng)過(guò)當(dāng)一個(gè)字符串hash到某一位的概率為：

1m

也就是說(shuō)當(dāng)前位被反轉(zhuǎn)為1的概率：

p(1)=1m

那么這一位沒(méi)有被反轉(zhuǎn)的概率為：

p(0)=1−1m

假設(shè)我們存入n各元素，使用k個(gè)hash函數(shù)，此時(shí)沒(méi)有被翻轉(zhuǎn)的概率為：

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

那什么情況下我們會(huì)誤判呢，就是原本不應(yīng)該被翻轉(zhuǎn)的位，結(jié)果翻轉(zhuǎn)了，也就是

p(誤判)=1−(1−1m)nk

由于只有k個(gè)hash函數(shù)同時(shí)誤判了，整體才會(huì)被誤判，最后誤判的概率為

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

要使得誤判率最低，那么我們需要求誤判與m、n、k之間的關(guān)系，現(xiàn)在假設(shè)m和n固定，我們計(jì)算一下k?？梢允紫瓤纯催@個(gè)式子：

(1−1m)nk

由于我們的m很大，通常情況下我們會(huì)用2^32來(lái)作為m的值。上面的式子中含有一個(gè)重要極限

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

因此誤判率的式子可以寫成

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

接下來(lái)令t=−n/m，兩邊同時(shí)取對(duì)數(shù)，求導(dǎo)，得到：

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

讓p′=0，則等式后面的為0，最后整理出來(lái)的結(jié)果是

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

計(jì)算出來(lái)的k為ln2mn，約等于0.693mn，將k代入p(誤判)，我們可以得到概率和m、n之間的關(guān)系，最后的結(jié)果

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

以上我們就得出了最佳hash函數(shù)個(gè)數(shù)以及誤判率與mn之前的關(guān)系了。

下表是m與n比值在k個(gè)hash函數(shù)下面的誤判率

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實(shí)現(xiàn)的布隆過(guò)濾器

由于Redis實(shí)現(xiàn)了setbit和getbit操作，天然適合實(shí)現(xiàn)布隆過(guò)濾器，redis也有布隆過(guò)濾器插件。這里使用php+redis實(shí)現(xiàn)布隆過(guò)濾器。

首先定義一個(gè)hash函數(shù)集合類，這些hash函數(shù)不一定都用到，實(shí)際上32位hash值的用3個(gè)就可以了，具體的數(shù)量可以根據(jù)你的位序列總量和你需要存入的量決定，上面已經(jīng)給出最佳值。

class BloomFilterHash
{
 /**
 * 由Justin Sobel編寫的按位散列函數(shù)
 */
 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貝爾實(shí)驗(yàn)室的Peter J. Weinberger的工作。
 * Aho Sethi和Ulman編寫的“編譯器（原理，技術(shù)和工具）”一書建議使用采用此特定算法中的散列方法的散列函數(shù)。
 */
 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功能，但針對(duì)32位處理器進(jìn)行了調(diào)整。它是基于UNIX的系統(tǒng)上的widley使用哈希函數(shù)。
 */
 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;
 }

 /**
 * 這個(gè)哈希函數(shù)來(lái)自Brian Kernighan和Dennis Ritchie的書“The C Programming Language”。
 * 它是一個(gè)簡(jiǎn)單的哈希函數(shù)，使用一組奇怪的可能種子，它們都構(gòu)成了31 .... 31 ... 31等模式，它似乎與DJB哈希函數(shù)非常相似。
 */
 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項(xiàng)目中使用的首選算法。
 * 哈希函數(shù)似乎對(duì)許多不同的數(shù)據(jù)集具有良好的總體分布。它似乎適用于數(shù)據(jù)集中元素的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上向世界展示。
 * 它是有史以來(lái)發(fā)布的最有效的哈希函數(shù)之一。
 */
 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在“計(jì)算機(jī)編程藝術(shù)第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來(lái)進(jìn)行操作

/**
 * 使用redis實(shí)現(xiàn)的布隆過(guò)濾器
 */
abstract class BloomFilterRedis
{
 /**
 * 需要使用一個(gè)方法來(lái)定義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; //假設(shè)這里你已經(jīng)連接好了
 }

 /**
 * 添加到集合中
 */
 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();
 }

 /**
 * 查詢是否存在, 存在的一定會(huì)存在, 不存在有一定幾率會(huì)誤判
 */
 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;
 }

}

上面定義的是一個(gè)抽象類，如果要使用，可以根據(jù)具體的業(yè)務(wù)來(lái)使用。比如下面是一個(gè)過(guò)濾重復(fù)內(nèi)容的過(guò)濾器。

/**
 * 重復(fù)內(nèi)容過(guò)濾器
 * 該布隆過(guò)濾器總位數(shù)為2^32位, 判斷條數(shù)為2^30條. hash函數(shù)最優(yōu)為3個(gè).(能夠容忍最多的hash函數(shù)個(gè)數(shù))
 * 使用的三個(gè)hash函數(shù)為
 * BKDR, SDBM, JSHash
 *
 * 注意, 在存儲(chǔ)的數(shù)據(jù)量到2^30條時(shí)候, 誤判率會(huì)急劇增加, 因此需要定時(shí)判斷過(guò)濾器中的位為1的的數(shù)量是否超過(guò)50%, 超過(guò)則需要清空.
 */
class FilteRepeatedComments extends BloomFilterRedis
{
 /**
 * 表示判斷重復(fù)內(nèi)容的過(guò)濾器
 * @var string
 */
 protected $bucket = 'rptc';

 protected $hashFunction = array('BKDRHash', 'SDBMHash', 'JSHash');
}

總結(jié)

以上所述是小編給大家介紹的布隆過(guò)濾器(bloom filter)及php和redis實(shí)現(xiàn)布隆過(guò)濾器的方法，希望對(duì)大家有所幫助！

最新評(píng)論