王鵬

【摘要】 介紹布隆過(guò)濾器（Bloom Filter）的相關(guān)算法原理和使用說(shuō)明，并闡述其在BSS領(lǐng)域中應(yīng)用。通過(guò)與Redis緩存技術(shù)相結(jié)合，利用布隆過(guò)濾器（Boom Filter）的高效匹配、低存儲(chǔ)等優(yōu)勢(shì)，提高BSS中排重效率，減少BSS對(duì)硬件擴(kuò)容的需求。同時(shí)，闡述BSS排重中關(guān)于位數(shù)組的劃分，以及針對(duì)布隆過(guò)濾器（Bloom Filter）對(duì)數(shù)據(jù)存在一定誤判率的不足，并提出相應(yīng)的應(yīng)對(duì)措施。

【關(guān)鍵詞】 布隆過(guò)濾器 排重 哈希算法 BSS Redis

一、引 言

判斷一個(gè)元素已經(jīng)存在某個(gè)集合里，一般的做法是：將集合中所有的元素保存起來(lái)，然后通過(guò)比較的方式來(lái)確定是否為重復(fù)元素。例如，常用于存儲(chǔ)集合元素的數(shù)據(jù)結(jié)構(gòu)有：鏈表、樹(shù)、哈希表（hash table）等。但是，隨著數(shù)據(jù)量的不斷增長(zhǎng)，所需的存儲(chǔ)空間呈線性增長(zhǎng)，檢索的效率面臨著嚴(yán)峻的考驗(yàn)。在BSS系統(tǒng)中，需要從檢索效率、空間存儲(chǔ)以及準(zhǔn)確性等多個(gè)方面考慮排重機(jī)制，從而保障系統(tǒng)性能及穩(wěn)定性。在眾多的排重技術(shù)中，布隆過(guò)濾器（Bloom Filter）是其中最優(yōu)秀的排重技術(shù)之一。它的主要優(yōu)勢(shì)在于：快速的檢索以及極低的存儲(chǔ)需求，主要缺點(diǎn)在于：存在一定的誤判率，需要從應(yīng)用角度，設(shè)計(jì)適中的位數(shù)組以及多重哈希判斷來(lái)降低誤判率。同時(shí)，針對(duì)誤判元素進(jìn)行特殊處理，以滿足系統(tǒng)需要。

二、Bloom Filter概述

布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

布隆過(guò)濾器（Bloom Filter）是一種空間效率極高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，采用位向量的方式表示一個(gè)集合，并結(jié)合哈希（hash）函數(shù)映射到集合中。布隆過(guò)濾器（Bloom Filter）的這種高效算法有一定的代價(jià)：判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能把不屬于這個(gè)集合的元素誤認(rèn)為屬于這個(gè)集合。因此，布隆過(guò)濾器（Bloom Filter）不適合“零誤判”的應(yīng)用場(chǎng)合。而是在能夠容忍低誤判率的應(yīng)用場(chǎng)合下，布隆過(guò)濾器（Bloom Filter）通過(guò)極低的誤判，節(jié)省極大的存儲(chǔ)空間。

三、Bloom Filter原理布隆過(guò)濾器（Bloom Filter）是一個(gè)包含N位的位數(shù)組，每一位初始為0（如圖1）。

二位數(shù)組集合N={x1，x2，x3，… …，xn}存放N個(gè)位元素，布隆過(guò)濾器（Bloom Filter）使用K個(gè)相互獨(dú)立的哈希（hash）函數(shù)，將待處理的數(shù)據(jù)分別壓縮成K個(gè)散列值，然后采用取模算法，將K個(gè)散列值分別映射到集合{1，2，3，…，n}的范圍內(nèi)。即（圖二）對(duì)于一個(gè)待處理數(shù)據(jù)x1，x2，通過(guò)3個(gè)獨(dú)立的哈希（hash）函數(shù)fk（h）分別計(jì)算出相應(yīng)的散列值fk（x），并將計(jì)算出來(lái)的3個(gè)散列值fk（x）對(duì)N進(jìn)行取模運(yùn)算得到位數(shù)組下標(biāo)，對(duì)相應(yīng)下標(biāo)的位進(jìn)行置1操作。當(dāng)在檢索一個(gè)元素時(shí)，同樣需要經(jīng)過(guò)K個(gè)哈希（hash）函數(shù)計(jì)算出來(lái)的位數(shù)組下標(biāo)，并挨個(gè)確認(rèn)是否置為1。如果全為1，則被檢索的元素可能已經(jīng)存在；如果K個(gè)里面有任何一個(gè)不為1，則被檢索的元素一定不存在當(dāng)前集合中。

在布隆過(guò)濾器中，由于無(wú)論哈希（hash）函數(shù)設(shè)計(jì)的多么精密，都會(huì)有沖突現(xiàn)象，即2個(gè)不同的元素通過(guò)同一個(gè)哈希（hash）函數(shù)的處理結(jié)果可能映射到同一個(gè)位置。所以，為了減少?zèng)_突發(fā)生的概率，布隆過(guò)濾器（Bloom Filter）通過(guò)K個(gè)獨(dú)立的哈希（hash）函數(shù)來(lái)進(jìn)行映射操作，但是無(wú)法百分百避免。如果在不考慮位數(shù)組大小的前提下，隨著K值增長(zhǎng)（即獨(dú)立哈希（hash）函數(shù)的增多），沖突的概率會(huì)不斷降低，即誤判率會(huì)不斷降低。但是，隨著K值增大，也會(huì)引起大量哈希（hash）計(jì)算占用過(guò)高的CPU計(jì)算，導(dǎo)致整體的效率降低。

四、Bloom Filter排重應(yīng)用

在BSS系統(tǒng)中傳統(tǒng)的排重算法，是將原數(shù)據(jù)X（待排重元素）作為自變量，通過(guò)特定的哈希（hash）函數(shù)映射成相應(yīng)的散列值。表達(dá)為：f（x）=H（X）。將計(jì)算出來(lái)的f（x），到存儲(chǔ)哈希表（hash table）的文件（或數(shù)據(jù)庫(kù)）中查找，如果匹配上則認(rèn)為可能是重復(fù)數(shù)據(jù)，然后進(jìn)行下一步完全排重判斷；如果匹配不上，認(rèn)為不是重復(fù)數(shù)據(jù)，則將此數(shù)據(jù)寫入存儲(chǔ)哈希表（hash table）的文件（或數(shù)據(jù)庫(kù)）中供后續(xù)數(shù)據(jù)排重使用。傳統(tǒng)的排重中，為了能夠快速的查找到散列值，將計(jì)算后的散列值按照一定的規(guī)則進(jìn)行分片，例如：按照時(shí)間、地域等多個(gè)維度進(jìn)行分片。同時(shí)，按照訪問(wèn)的熱度，將熱數(shù)據(jù)放到內(nèi)存中，提高匹配效率。雖然，以上多種優(yōu)化措施在一定程度上提高了目前的排重效率，能夠有效的處理日常的話單排重。但是，隨著用戶的不斷發(fā)展，歷史排重文件所占的空間不斷增加，在普通存儲(chǔ)設(shè)備上即使采用高效的哈希（hash）算法也很難提高效率。例如，采取目前MD5（Message-Digest Algorithm 5）算法將待排重?cái)?shù)據(jù)計(jì)算成一個(gè)128bit大小的大整數(shù)，100億數(shù)據(jù)量大約需要占用約149GB空間。由于需要完全匹配排重，所以需要將原數(shù)據(jù)也一同保留下來(lái)，以便在發(fā)生哈希（hash）沖突時(shí)，使用原數(shù)據(jù)進(jìn)行完全比對(duì)。單條原數(shù)據(jù)的空間本身占用就比較大，那么100億記錄的空間占用會(huì)更大。

采用布隆過(guò)濾器（Bloom Filter）來(lái)代替目前傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)，在效率和空間上都有所改變。但是，在使用布隆過(guò)濾器（Bloom Filter）時(shí)，需要考慮多個(gè)因素：（1）考慮如何分配大小最優(yōu)的位數(shù)組以及最優(yōu)的K值（獨(dú)立哈希函數(shù)的個(gè)數(shù)）；（2）考慮位數(shù)組集合存儲(chǔ)問(wèn)題，以便最快的檢索；（3）解決由于布隆過(guò)濾器（Bloom Filter）自身的誤判率問(wèn)題，以便完全匹配重復(fù)數(shù)據(jù)。

使用布隆過(guò)濾器（Bloom Filter）在分配位數(shù)組大小以及K值（獨(dú)立哈希函數(shù)的個(gè)數(shù)）時(shí)，都會(huì)影響到最終的誤判率以及排重的處理效率。假設(shè)位數(shù)組的大小為N，獨(dú)立的哈希函數(shù)個(gè)數(shù)為K，那么在已經(jīng)插入x個(gè)元素后的誤判率為： 。其中當(dāng)K=1時(shí)， x/N與誤判率f（x）的關(guān)系：隨著N的不斷增加，誤判率不斷降低。N的大小設(shè)定，需要取決于待排重總量的大小。所以，一定要對(duì)當(dāng)前需要排重的數(shù)據(jù)量有一個(gè)初步的預(yù)估，從而計(jì)算出合理的N值。當(dāng)x/N=1時(shí)，K值與誤判率f（x）的關(guān)系：隨著K值的不斷增加，誤判率不斷降低。 K值的大小設(shè)定，需要考慮對(duì)CPU消耗影響，過(guò)高的K值會(huì)影響應(yīng)用的整體效率。

在確定位數(shù)組大小后，需要考慮存儲(chǔ)方式，可以通過(guò)多種存儲(chǔ)方式存儲(chǔ)，例如：一塊連續(xù)的私有內(nèi)存、鏈表以及容器等存儲(chǔ)方式。如果對(duì)于少量的數(shù)據(jù)，應(yīng)用可以通過(guò)分配私有內(nèi)存的方式，分配一定大小的連續(xù)內(nèi)存空間，即可滿足；如果對(duì)于大量數(shù)據(jù)，例如100億數(shù)據(jù)量，當(dāng)x/N=1時(shí)大約就需要1.16GB容量。這個(gè)數(shù)量級(jí)的操作，放到私有內(nèi)存有重多限制，例如：內(nèi)存分配問(wèn)題、數(shù)據(jù)共享問(wèn)題、應(yīng)用啟動(dòng)加載問(wèn)題等。大量數(shù)據(jù)可以考慮以共享內(nèi)存的形式存放位數(shù)組。但是，需要考慮數(shù)據(jù)的持久性、容災(zāi)備份、并發(fā)訪問(wèn)以及快速查找等因素。尤其考慮到位數(shù)組的特殊性：以比特位（bit）的形式存儲(chǔ)。結(jié)合當(dāng)前開(kāi)源的產(chǎn)品：內(nèi)存庫(kù)、緩存以及消息中間件，最終選取了Redis。Redis不僅具備事務(wù)、磁盤持久化、復(fù)制等功能，最主要的是提供BitMap這種可以直接用于位操作的數(shù)據(jù)類型。將需要排重的數(shù)據(jù)信息通過(guò)布隆過(guò)濾器（Bloom Filter）生成相應(yīng)位數(shù)組的位置下標(biāo)，然后使用BitMap中的setbit（置位）/getbit（獲取位）進(jìn)行相應(yīng)的寫/讀操作。

在BSS的話單排重中，由于整個(gè)月的話單都需要排重，而且單省整月的話單量大約在270億條左右。如果只用一個(gè)BitMap來(lái)存放整月的數(shù)據(jù)，則會(huì)帶來(lái)效率的下降。從系統(tǒng)的業(yè)務(wù)角度出發(fā)，將數(shù)據(jù)按照話單開(kāi)始日期進(jìn)行分片，BitMap從而也按照開(kāi)始日期進(jìn)行存儲(chǔ)，不同的BitMap存放不同開(kāi)始時(shí)間的話單排重信息。即，每月可以拆成30個(gè)BitMap。但是，即使拆成30個(gè)BitMap，還有有新的問(wèn)題：并發(fā)處理話單時(shí)，多個(gè)應(yīng)用程序同時(shí)處理同一個(gè)用戶的同一條記錄，存在競(jìng)爭(zhēng)的關(guān)系。為了解決這個(gè)問(wèn)題，可以采取多種方案，例如：在進(jìn)行事物操作時(shí)加鎖，避免并發(fā)帶來(lái)的數(shù)據(jù)異常；或者，將話單記錄按照用戶進(jìn)行劃分，同一個(gè)用戶在一個(gè)應(yīng)用進(jìn)程下處理。如果，按照用戶進(jìn)行劃分后，原來(lái)的30個(gè)BitMap可以根據(jù)用戶的不同再次分解。即，按照日期加進(jìn)程的方式進(jìn)行劃分BitMap。這樣一個(gè)BitMap存儲(chǔ)的數(shù)據(jù)量會(huì)變得較低，有利于檢索效率的提升。

布隆過(guò)濾器（Bloom Filter）由于存在一定的誤判率，但是BSS的排重對(duì)重單是零容忍。針對(duì)誤判用戶再采取完全匹配的方式到文件系統(tǒng)（或數(shù)據(jù)庫(kù)）進(jìn)行檢索匹配，判斷是否重復(fù)數(shù)據(jù)。由于檢索文件系統(tǒng)（或數(shù)據(jù)庫(kù)）效率比Redis差了很多倍，所以盡可能通過(guò)適當(dāng)增加BitMap的大小以及最優(yōu)的K值，來(lái)保障最小的誤判率。從而使絕大多數(shù)話單記錄通過(guò)操作Redis里的BitMap實(shí)現(xiàn)排重，只有少部分的誤判記錄查詢文件系統(tǒng)（或數(shù)據(jù)庫(kù)）。

五、結(jié)論

布隆過(guò)濾器（Bloom Filter）優(yōu)點(diǎn)在于：檢索效率快、存儲(chǔ)空間占用低；缺點(diǎn)在于：無(wú)法刪除、存在誤判。利用存儲(chǔ)空間低的優(yōu)勢(shì)，可以部署在低配置的主機(jī)實(shí)現(xiàn)大量數(shù)據(jù)的排重操作。同時(shí)，可以與目前開(kāi)源的多種工具相結(jié)合使用，比如：與Redis+Hadoop相結(jié)合，實(shí)現(xiàn)大數(shù)據(jù)的快速排重。

參 考 文 獻(xiàn)

[1] 劉威；郭淵博；黃鵬 基于Bloom filter的多模式匹配引擎評(píng)論推薦[期刊論文]-電子學(xué)報(bào) 2010（05）.

[2]A.Broder；M.Mitzenmacher Network applications of bloom filters：A survey 2005（04）