關于布隆過濾器在BSS中應用

王鵬

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

【關鍵詞】 布隆過濾器 排重 哈希算法 BSS Redis

一、引 言

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

二、Bloom Filter概述

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

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

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

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

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

四、Bloom Filter排重應用

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

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

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

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

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

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

五、結論

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

參 考 文 獻

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

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