區(qū)塊鏈應用下的新型區(qū)塊鏈布隆過濾器

樊 星，牛保寧

太原理工大學 信息與計算機學院，山西 晉中 030600

隨著區(qū)塊鏈的廣泛使用，其產(chǎn)生的區(qū)塊數(shù)據(jù)也在急劇增加。截至2020年5月8日，比特幣[1]已經(jīng)產(chǎn)生629 473個區(qū)塊，存儲容量為257.28 GB，同比分別增加8.9%和22.4%。支持智能合約的區(qū)塊鏈應用——以太坊[2]已經(jīng)產(chǎn)生10 029 304 個區(qū)塊，數(shù)據(jù)總容量達到127.06 GB，同比分別增加47.42%和53.88%。與以比特幣和以太坊為代表的公有鏈相比，許可鏈Hyperledger Fabric[3]由于有參與節(jié)點準入限制，其數(shù)據(jù)冗余度沒有公有鏈的嚴重，但是，數(shù)據(jù)量也在隨著業(yè)務量的增加和參與節(jié)點的增加而快速增加。如何提高鏈上數(shù)據(jù)查詢性能對區(qū)塊鏈的推廣和應用提出了巨大挑戰(zhàn)[4]。

在對區(qū)塊鏈數(shù)據(jù)分析時，經(jīng)常需要進行數(shù)據(jù)查找操作。布隆過濾器（bloom filter，BF）[5]是一個高效的集合查詢工具，在以哈希運算為主的區(qū)塊鏈應用中不可或缺。輕量級節(jié)點由于本地沒有保存區(qū)塊數(shù)據(jù)，需要依賴遠程全節(jié)點。為了保護輕量級節(jié)點的數(shù)據(jù)隱私[6]，提出由輕量級節(jié)點自主選擇誤判率，將布隆過濾器發(fā)送給遠程節(jié)點，遠程節(jié)點將運算后的布隆過濾器及滿足條件的結果一起返回給輕量級節(jié)點，從而避免在數(shù)據(jù)查詢過程中隱私泄露。而對于保存完整數(shù)據(jù)的全節(jié)點，在查詢存儲在本地LevelDB數(shù)據(jù)庫的區(qū)塊數(shù)據(jù)時，利用布隆過濾器可以快速過濾不相干的數(shù)據(jù)，減少不必要的I/O 開銷，提高系統(tǒng)讀取性能。

可以看出，作為支持區(qū)塊鏈上數(shù)據(jù)查詢的基本工具，提高布隆過濾器的性能對于提高鏈上數(shù)據(jù)查詢、分析性能至關重要。

1 相關工作

綜上所述，布隆過濾器本質(zhì)上是一種巧妙的概率型數(shù)據(jù)結構，相比于傳統(tǒng)的List、Set、Map 等數(shù)據(jù)結構，它更高效、占用空間更少，廣泛應用于區(qū)塊鏈數(shù)據(jù)查詢中。然而，構造布隆過濾器需要大量的內(nèi)存訪問和哈希計算，這將成為區(qū)塊鏈數(shù)據(jù)查詢的性能瓶頸。迄今為止，提高布隆過濾器性能的研究主要集中在降低內(nèi)存訪問和減少哈希函數(shù)計算開銷上，并沒有特定針對區(qū)塊鏈應用的布隆過濾器優(yōu)化研究。

降低訪存開銷主要通過限定布隆過濾器的長度和改變哈希函數(shù)。OMBF（one-memory bloom filter）[7]和Bloom-1[8]將元素的映射位限制在一個緩存行內(nèi)，保證一個元素映射的k位能在一個緩存行中完成讀取。OMASS（one memory access set separation）[9]通過將k次哈希函數(shù)變換為更復雜的運算，減少在字選擇階段造成的額外的訪存次數(shù)。它們的共同問題是：訪存開銷的減少是以增加哈希函數(shù)計算復雜度為代價的。

減少哈希函數(shù)計算開銷主要是通過共享哈希函數(shù)計算。LHBF（less Hashing bloom filter）[10]利用兩個偽隨機哈希函數(shù)h1(x)和h2(x)作為種子函數(shù)，根據(jù)構造公式gi=h1(x)+ih2(x)生成多個哈希函數(shù)。另一種思路是：利用O(lgk)個種子函數(shù)產(chǎn)生k個相互獨立的哈希函數(shù)[11]。然而，這些方案缺乏對合成哈希函數(shù)間獨立性的理論分析，且并未針對區(qū)塊鏈數(shù)據(jù)的特性進行優(yōu)化，還存在提升的空間。此外，在對布隆過濾器位向量分段情況下，Bloom-1[8]、Parallel BF[12]通過同時訪問多個組實現(xiàn)并行計算。然而，這類并行優(yōu)化只適用于順序查找，并且多核CPU 固有的并行性使得程序需要進行重寫，可行性差。

總之，現(xiàn)有的布隆過濾器并沒有充分利用區(qū)塊鏈數(shù)據(jù)特性及通用設備計算資源，存在很大的優(yōu)化空間。在現(xiàn)有研究的基礎上，本文提出一種新的適用于區(qū)塊鏈應用的布隆過濾器，即區(qū)塊鏈布隆過濾器（blockchain bloom filter，BBF）。與原始布隆過濾器相比，它的內(nèi)存訪問次數(shù)和哈希計算開銷更低。在此基礎上，利用SIMD（single instruction multiple data）指令來對布隆過濾器的構造和查詢過程進行并行化，進一步提高BBF 元素查找性能。

2 BBF 設計與理論分析

本章討論了BBF 的實現(xiàn)方法，并分析了它的假陽性概率。BBF 設計的最終目標是提供一種新的適合區(qū)塊鏈數(shù)據(jù)特性的布隆過濾器。

2.1 新型BBF 架構

布隆過濾器由一個n比特的位數(shù)組S={x0x1…xn-1}和k個彼此獨立的哈希函數(shù){h1,h2,…,hk}組成，位數(shù)組初始化為0。插入元素xs時，將元素xs通過k個哈希函數(shù)產(chǎn)生對應的k個哈希值，以哈希值作為位數(shù)組中的下標，將k個對應位置“1”。在查詢過程中，將該元素通過k個哈希函數(shù)映射到對應的比特位，如果存在映射位為“0”，則說明該元素一定不在集合內(nèi)。

通過布隆過濾器的預過濾操作，可以提高數(shù)據(jù)的查找效率，然而，傳統(tǒng)的布隆過濾器在一次數(shù)據(jù)查詢過程中可能存在多次訪存失敗的情況。這是因為在區(qū)塊鏈應用中，數(shù)以億計的數(shù)據(jù)信息和有限的內(nèi)存資源使得布隆過濾器需要選擇片外存儲方式。而區(qū)塊鏈數(shù)據(jù)以文件形式存儲，一個布隆過濾器中往往對應數(shù)以萬計的元素，相應的，其包含的位數(shù)增多，只能連續(xù)存儲在多個緩存行（cache-line）上。那么在最壞情況下，進行一次區(qū)塊（交易）查詢就會造成k次訪存缺失，這對于查詢性能的影響是致命的。

為了降低布隆過濾器計算中產(chǎn)生的訪存缺失，本文提出一種具有新型布隆過濾器數(shù)據(jù)結構的BBF。如圖1 所示，BBF 由r個連續(xù)的長度為lg的組（group）組成，r為2 的冪次方，每個組由k個長度為lw字（word）組成，即lg=k×lw，哈希函數(shù)與word一一對應，滿足一個word可以被加載到一個通用寄存器的緩存行中，即lw=32(64)bit。一個BBF 有m位，滿足關系m=r×lg=r×k×lw。在元素插入及查詢過程中，將其映射到一個包含連續(xù)的k個word的group中，保證組（group）的長度小于緩存行。

Fig.1 BBF structure圖1 BBF 架構

通過改進布隆過濾器結構，一個元素的映射空間限制在一個group中。而一個緩存行可以保存至少一個group，那么在查詢過程中，一次訪存操作就可以讀取到多個group。即使元素映射到的組不在緩存中，也只需要一次訪存操作即可讀取全部映射位，從而將訪存失敗次數(shù)限制到1 次。為了保證元素與組（group）對應，還需要一個額外的組選擇函數(shù)。

由于BBF 結構發(fā)生改變，可能造成假陽性的變化，為了簡化描述過程，下面對BBF 和BF 兩者的假陽性進行分析，分別用pBBF和pBF表示。圖2 中描述了元素x1的插入過程，哈希函數(shù)均選擇布隆過濾器中常用的Murmurhash3[13]函數(shù)，k=4，lw=4 。對于BF，插入過程可以分為①哈希映射階段和②取模階段。而對于BBF，插入過程可以分為①組選擇階段，②哈希運算階段和③取模階段。在哈希運算階段，元素經(jīng)過k次哈希運算；在取模階段，將k個哈希值做取模運算，并將對應位置“1”。

根據(jù)文獻[5]BF 假陽性為：

BBF 通過組映射函數(shù)將元素映射到一個選定的組中，然后通過k個哈希函數(shù)將組中k個word中的對應位置“1”，其中哈希函數(shù)和word一一對應。如圖2所示，假定元素x1映射到group1。

BBF 保證元素映射到任意group的概率相等，假陽性事件J表示元素xs不屬于集合S，但誤判屬于S的情況。BBF 中group中任意word未被置“1”的概率為1-1/lw。插入z(z∈[0,n])個元素后，該位仍未被置“1”的概率為(1-1/lw)z，由此可知該位被置1 的概率為1-(1-1/lw)z。用隨機變量Z 表示映射到group中的元素個數(shù)。則當Z=z時事件J發(fā)生的概率為Pr{J|Z=z}=(1-(1-1/lw)z)k。

Fig.2 Schematic view of BF vs.BBF(minimize cache misses)圖2 BF vs.BBF（減少訪存開銷）示意圖

Z=z事件發(fā)生概率服從二項分布，即Z～B(n,1/r)，由此可得：

由式（1）、式（2）可知，BBF 假陽性概率為：

對于給定元素集合，布隆過濾器位數(shù)越少，函數(shù)碰撞率越高，相應的，假陽性概率也越高。通過式（1）、式（3）無法直觀比較兩者的假陽性差異，因此對它們的假陽性進行了數(shù)值分析，n=104，k=4。定義填充率（fill factor，F(xiàn)）為F=n/m；負載因子L=a/m，其中a為向量中填充為“1”的位數(shù)。負載因子表示布隆過濾器中的元素被填充的程度，L越大則布隆過濾器中的元素越多，空間利用率越高。然而，過高的空間利用率可能會導致哈希函數(shù)的高碰撞率和高誤判率。

哈希表（HashMap）[14]與布隆過濾器類似，都是將當前元素的關鍵字通過哈希函數(shù)映射到數(shù)組中的某個位置，當兩個不同的元素通過哈希函數(shù)得到的存儲地址相同時，就會產(chǎn)生哈希碰撞。為了減少哈希函數(shù)的碰撞概率，當哈希表的數(shù)組長度達到一個臨界值就會觸發(fā)擴容，此時需要將所有元素重新進行哈希運算再放回到容器中，這是一個非常耗時的操作?？梢钥闯?，臨界值的選擇尤為重要，而這個臨界值由負載因子和當前的容量大小共同決定。在理想情況下，節(jié)點出現(xiàn)的頻率在哈希桶中的概率服從泊松分布，實驗表明選擇0.75 作為負載因子是哈希表對于空間和時間成本的一種折中?？紤]到BBF構建過程中存在哈希沖突，存在a≤k×n，因此L=a/m≤(k×n)/m。

從圖3（a）可以看出，隨著填充率F增加，BF和BBF（lw=32,64）假陽性概率變化趨勢一致。當F∈[0.80,1.00]時，變化曲線趨于平緩。圖3（b）為F∈[0.02,0.20]時的pBF和pBBF變化情況。圖3（b）右（次）縱坐標軸為BBF 與BF 的假陽性概率相對差異，定義為D=(pBBF-pBF)/pBF。當F較小時，BBF 與BF 的假陽性差值變化較大。隨著填充率的增加，兩者之間的差異越來越小。當lw從32 bit 增加到64 bit 時，兩者的差異D幾乎減半。當F從0.02 增加到0.20 時，pBF和pBBF(lw=32) 的假陽性概率相對差異從2.98 降低到0.10。類似地，pBF和pBBF(lw=64)之間的假陽性概率相對差異從1.28 減少到0.05。綜上所述，可以得出結論：在相同的假陽性概率下，BBF 比BF 需要更多的比特位，這是因為元素的映射位被限制在一個范圍內(nèi)，所以哈希函數(shù)碰撞率隨之增加。因此，從降低BBF 假陽性概率的角度來看，lw應該盡可能長。然而，實際情況中l(wèi)w受到緩存行的限制。

Fig.3 False positive ratio of BF and BBF(lw=32,64)圖3 BF 及BBF（lw=32,64）假陽性概率

雖然與BF 相比，BBF 假陽性概率更高，但可以通過增加更多的映射位來彌補這一缺陷。實驗發(fā)現(xiàn)，當pBF=pBBF(lw=32)=0.015 6 時，BF 和BBF 分別需要86 650 bit和100 000 bit。而當pBF=pBBF(lw=64)=0.013 7時，BF 和BBF 需要89 299 和100 000 bit。換句話說，為了保持與BF 相同的假陽性率，BBF(lw=32)和BBF(lw=64)分別需要比BF 多出15.40%和11.98%的映射位?？紤]到布隆過濾器的空間效率特性，與區(qū)塊鏈的數(shù)據(jù)量相比，它額外需要的比特位數(shù)可以忽略不計，因此該方案是可行的。

2.2 哈希計算優(yōu)化

通過改變布隆過濾器的映射結構，雖然能夠節(jié)省訪存開銷次數(shù)，但是需要增加一次組選擇哈希函數(shù)計算，將元素映射到指定的group中，產(chǎn)生了額外的計算開銷，因此本節(jié)對BBF 中涉及的哈希計算進行優(yōu)化。

布隆過濾器中的計算開銷主要來自兩方面：元素插入時哈希函數(shù)的計算和成員查詢的哈希計算過程。根據(jù)區(qū)塊鏈數(shù)據(jù)的特性，區(qū)塊（交易）哈希值是對原始數(shù)據(jù)經(jīng)過哈希函數(shù)運算（SHA256）的結果，是區(qū)塊（交易）的唯一標識符。而區(qū)塊鏈與布隆過濾器選取哈希函數(shù)的原則一致，都是要保證函數(shù)的隨機性、不可逆、低碰撞。傳統(tǒng)布隆過濾器采用Murmurhash3函數(shù)而不是SHA256 的原因主要是考慮到布隆過濾器需要頻繁的哈希運算，雖然SHA256 能夠滿足以上三個特性，但由于其計算量大，因此沒有作為布隆過濾器中的通用哈希函數(shù)。而區(qū)塊鏈數(shù)據(jù)特性決定區(qū)塊鏈中的數(shù)據(jù)都是由SHA256 標識，因此，本文提出將SHA256 視為種子函數(shù)，利用區(qū)塊鏈中的哈希值派生出k個哈希候選值而不是設計多個哈希函數(shù)，從而簡化哈希計算。

在設計使用一個哈希函數(shù)執(zhí)行布隆過濾器的研究中，如何使用一個哈希函數(shù)模擬出k個哈希函數(shù)并證明這k個哈希函數(shù)相互獨立是一個研究難點。而目前的文獻研究局限于使用一定數(shù)量的種子哈希函數(shù)去模擬出k個哈希函數(shù)的方法，并沒有從理論上證明模擬出來的哈希函數(shù)是相互獨立的[10,15]。布隆過濾器假陽性概率的分析過程都假設使用的k個哈希函數(shù)完全隨機，并且相互獨立。雖然這些方法有效降低了哈希計算量，但由于缺少哈希函數(shù)獨立性證明，使得這些方法不能保證布隆過濾器的實際假陽性概率與理論分析值一致。

本文提出的BBF 通過利用區(qū)塊鏈數(shù)據(jù)特性，可以將其視為單哈希布隆過濾器。為了消除對于單哈希布隆過濾器相比傳統(tǒng)布隆過濾器可能造成假陽性概率升高的顧慮，進一步論證如下：

BBF 與BF 的實際假陽性概率差異可能并不如理論中那樣明顯。這是因為實際中用到的哈希函數(shù)并非是理想狀況下完全隨機的哈希函數(shù)。所有關于布隆過濾器的理論分析都是基于以下兩個關于哈希函數(shù)的假設：（1）完全隨機。布隆過濾器中使用的所有哈希函數(shù)是完全隨機的，哈希函數(shù)可以將所有的數(shù)據(jù)元素均勻地映射到整個布隆過濾器范圍內(nèi)。（2）相互獨立。布隆過濾器中使用的所有哈希函數(shù)相互之間是獨立的。

然而，文獻[16]中測試了一些實際應用中具有代表性的哈希函數(shù)的隨機性和獨立性，結果顯示實際中的哈希函數(shù)并不能達到理想狀態(tài)下完全隨機，特別是將哈希函數(shù)進行組合之后發(fā)現(xiàn)，當哈希函數(shù)組合中存在未能通過獨立性測試的哈希函數(shù)時，相應的哈希函數(shù)組合就無法通過隨機性測試。也就是說，哈希函數(shù)之間存在某種弱相關性。這種弱相關性會導致BF 中的多哈希函數(shù)組合假陽性概率跟理論假陽性概率相差很大。

因此在應用布隆過濾器時，哈希函數(shù)的選擇是非常困難的，尤其是對于比較大的k值。一個差的哈希函數(shù)組合選擇會導致實際假陽性概率跟理論假陽性概率差值很大[17]。對于一個隨機性好的哈希函數(shù)，盡管初始化種子不同會展現(xiàn)出比較好的獨立特性，但哈希函數(shù)的計算仍然會導致計算開銷成倍增加。相反，在單哈希布隆過濾器中，它只需要一個隨機性好的種子哈希函數(shù)。實際中需要的哈希函數(shù)越少，就越容易做出正確的選擇。另外，如果哈希函數(shù)間的相關性被消除，實際的假陽性概率會更接近于理論值?？梢詫BF 視為一種單哈希布隆過濾器，選取滿足哈希函數(shù)隨機性和獨立性測試的SHA256 作為種子函數(shù)。

在組選擇階段，可以將組選擇哈希函數(shù)簡化為一次取模運算j=xsmodr，j為BBF 中映射到的組號。元素映射到任意組后，將元素根據(jù)式（4）映射為k個候選元素，與word一一對應，lk為原始位數(shù)。

嚴格來說，BBF 的哈希映射過程仍然有k個相互獨立的哈希函數(shù)參與，相應地，一個元素對應產(chǎn)生k個映射位。不同之處在于，這k個哈希函數(shù)是由k個按位與運算（and）產(chǎn)生的。此外，當m為2 的冪次方時，根據(jù)計算機指令集[18]可知，按位與運算與取模運算（modulo）等價，而后者的計算復雜度較前者高，因此可以通過限定m的取值，將取模運算替換為按位與運算（and），進一步提高計算效率。

Fig.4 Schematic view of BBF(cache efficiency optimization)vs.BBF(cache efficiency and Hash computation optimization)圖4 BBF（訪存優(yōu)化）vs.BBF（訪存及哈希計算優(yōu)化）示意圖

至此，BBF 的構建（查詢）過程可以細分為①組選擇階段，②哈希運算階段和③位運算階段。元素xs首先被映射到groupj，然后經(jīng)過k次按位與運算后得到候選集。最后將候選集的k個元素分別映射到groupj的k個word中，并將對應位置“1”。BBF 構建過程為：

步驟1j=xs&(2r-1)，將元素xs映射到groupj；

步驟2將元素xs按照式（4）分為k段；

步驟3將候選集中的k個元素映射到對應的word中，映射規(guī)則為，并將對應位置“1”。

圖4 顯示了BBF（2.1 節(jié)中提到的訪存優(yōu)化）和BBF（訪存及哈希計算優(yōu)化）示意圖。與前一種方法相比，后一種方法不僅消除了哈希函數(shù)運算過程，而且將取模操作改為低復雜度的位與運算，完成一個元素插入只需要2k+1 次位與運算，運算復雜度大大降低。

為了定量分析哈希優(yōu)化的優(yōu)勢，下面以CPU（central processing unit）時鐘周期為度量方式，對BF和BBF 在執(zhí)行元素插入過程中的操作成本進行比較，其中k=4，lk=32 B。時鐘周期是計算機中最基本的、最小的時間單位，它刻畫了同步動態(tài)隨機存取內(nèi)存（synchronous dynamic random-access memory，SDRAM）所能運行的最高頻率，時鐘周期越低，則意味著工作頻率越高。在一個時鐘周期內(nèi)，CPU 僅完成一個最基本的動作。

在CPU 指令中，通常情況下，按位運算需要3 個CPU 時鐘周期。在實驗服務器上進行性能測試表明，一次取模運算平均需要6 個CPU 時鐘周期；選用Murmurhash3 作為哈希函數(shù)，每個字節(jié)平均需要23個CPU 時鐘周期。由表1 可知，對于一次元素插入操作，BBF 需要192 個時鐘周期，約為BF 計算量的5%。BBF 的性能較BF 有顯著提升，這是因為BBF 的哈希計算量大大降低了。此外，由于普通哈希函數(shù)的計算時間成本隨著元素長度的增加而增加，觀察到隨著元素大小和哈希函數(shù)數(shù)目的增加，BBF 較BF 性能優(yōu)勢明顯。這一點在3.2節(jié)的實驗中也得到了驗證。

Table 1 CPU clock cycles comparison on element insertion between BF and BBF表1 BF 及BBF 元素插入所需CPU 時鐘周期

2.3 利用通用CPU 的SIMD 指令集優(yōu)化BBF

為了加快BBF 中元素插入和查詢效率，通過改變布隆過濾器結構減少了訪存失敗的次數(shù)和哈希計算開銷。在成員查詢過程中，需要依序檢查元素對應的k個映射位。如果所有的k位都設置為1，那么這個元素可能包含在集合中。考慮到元素在插入和查詢過程中k個候選元素彼此獨立，不存在相關性。如果能將它們并行化，就有可能進一步改進BBF。計算機硬件的進步對軟件的編寫方式產(chǎn)生了巨大的影響，SIMD指令集[19]可以實現(xiàn)同時對p對數(shù)據(jù)流執(zhí)行算術運算，即(c1,c2,…,cp)=(a1,a2,…,ap)+(b1,b2,…,bp)。

然而，BF 與SIMD 指令集并不適配，這是因為在布隆過濾器的查詢過程中，元素的映射位存在于整個布隆過濾器中，而SIMD 指令集可以同時處理加載到的連續(xù)位向量，提高數(shù)據(jù)處理效率。但是由于SIMD 一次讀入的數(shù)據(jù)有限，對于傳統(tǒng)的布隆過濾器，無法一次訪問全部映射位，從而無法充分利用SIMD 指令集的優(yōu)勢。而BBF 對BF 結構的改變正好與SIMD 的特性相吻合，支持一次讀取k個待查詢比特位的并行處理。基于BBF 的結構特性和運行機制，SIMD 指令主要應用在BBF 構建和元素查詢兩方面，提高元素插入/查詢效率。在元素插入過程中顯式調(diào)用SIMD 指令，偽代碼見算法1。

算法1BBF 構建算法

輸入:xs區(qū)塊鏈交易哈希值。

輸出:BBFo1。

相應地，BBF在元素查詢階段的偽代碼見算法2。

算法2BBF 元素查詢算法

輸入:xs，BBFs（BBF 候選集合）。

輸出:BBFt目標BBF。

3 實驗與結果分析

為了優(yōu)化區(qū)塊鏈應用中的布隆過濾器，本文提出三個改進措施。本章對BBF 性能進行了實驗。

3.1 實驗設置

實驗環(huán)境為Intel?CoreTMi7-8700K CPU@3.70 GHz，32 GB內(nèi)存。每個核心有獨立的一級緩存（L1 D-Cache 32 KB，L1 I-Cache 32 KB）和二級緩存（256 KB）。6個核心共享三級緩存（12 MB），緩存行為64 B。實驗使用AVX2 指令集，支持256 bit 整數(shù)算術運算。Gcc編譯器支持AVX2 指令的程序設計。

實驗選用存儲在LevelDB 數(shù)據(jù)庫中的比特幣數(shù)據(jù)集，lk=256。數(shù)據(jù)集1 為交易索引，表示為<‘t’+32-byte transaction hash，transaction index record>，共50 000 000 項；數(shù)據(jù)集2 為區(qū)塊索引，描述為<‘b’+32-byte block hash，block index record>，共50 000 項。在元素查詢性能實驗中，正向查詢是指查找屬于集合的元素，負向查詢是指查找不屬于集合中的元素。布隆過濾器的位數(shù)組是緩存行對齊的，使用每秒百萬次搜索（MSPS）作為查詢速度評價指標。實驗采用BF[5]和OMBF[7]作為對比方法。BF 為標準布隆過濾器，OMBF 是一種最先進的布隆過濾器方法，它通過減少緩存丟失來提高成員查詢性能。

3.2 性能評價

（1）假陽性概率。實驗選取pBBF(lw=64)在兩個數(shù)據(jù)集上分別進行實驗。如圖5 所示，不同數(shù)據(jù)集上的實驗結果與2.1 節(jié)中的理論分析變化趨勢一致，實驗結果基本吻合，可以得出BBF 成員查詢方法具有良好的隨機性，參數(shù)設置符合預期，驗證了2.1 節(jié)中對于BBF 的假陽性概率分析。同時，為后續(xù)實驗中填充率的選擇設置起到指導作用。

Fig.5 False positive ratio comparison between theory and measured results of BBF圖5 BBF 假陽性概率理論值與測試值分析

Fig.6 k vs.membership query performance圖6 k vs.元素查詢性能

（2）搜索代價。最小化緩存缺失和減少哈希操作有助于降低成員插入和搜索代價。而SIMD 指令又進一步提高了BBF的查找性能。圖6為在不同數(shù)據(jù)集上布隆過濾器查找性能對比，n=105,m=106,F=0.1。

理論上來說，正向查詢相比負向查詢需要檢查更多的映射位，因此哈希運算數(shù)也會增加，對于BF 和OMBF，圖6（a）中的正向查詢相比圖6（b）中的負向查詢性能有所降低。隨著哈希函數(shù)個數(shù)k的增加，BF 和OMBF 查詢速度呈下降趨勢。這主要是因為BF 和OMBF 在查詢過程中使用串行位檢測。隨著k的增加，待檢測比特位也隨之增加，因此速度下降。而BBF 采取并行的位檢測方法，顯示出近似恒定的查詢速度。

OMBF 的性能優(yōu)勢在于降低成員查詢過程中的內(nèi)存訪問開銷，在本實驗環(huán)境中，CPU 有足夠的緩存（32 GB），因此OMBF 的成員查詢速度較BF 相比，查詢性能優(yōu)勢并不明顯。從圖中可以看出，當k=8 時，在正向查詢中，BBF 的成員查詢速度分別為BF 和OMBF 的4 倍、3 倍；在負向查詢中，BBF 的成員查詢速度是其他兩類布隆過濾器的2 倍，BBF 較其他兩類具有代表性的布隆過濾器BF 和OMBF，查詢性能更優(yōu)。

Fig.7 m vs.membership query performance of BF圖7 m vs.布隆過濾器元素查詢性能

圖7 為布隆過濾器位數(shù)m與布隆過濾器查找性能的變化關系圖，為了表明緩存與查找性能之間的關系，將L1、L2 和L3 三級緩存在圖中做了標識。當CPU 緩沖區(qū)足夠大時（mL3-Cache 時，三者的成員查詢性能均明顯降低。由于OMBF 在BF的基礎上對查詢過程中的內(nèi)存訪問開銷做了優(yōu)化，較BF 查詢性能更優(yōu)。而BBF 在設計中優(yōu)化了訪存效率，因此無論片上緩存是否足以容納位向量，它的成員查詢速度都明顯優(yōu)于BF 和OMBF。

4 結論

本文提出了一種針對區(qū)塊鏈應用的新型布隆過濾器BBF。通過改進布隆過濾器數(shù)據(jù)結構減少訪存缺失次數(shù)，同時提出一種簡化的三階段哈希運算。在此基礎上，運用SIMD 指令實現(xiàn)元素插入及查找并行化。實驗結果表明，BBF 僅需要11.98%額外的映射位，就能在假陽性概率不變的同時，較其他兩種廣泛應用的布隆過濾器性能有顯著提升。