區(qū)塊鏈應(yīng)用下的新型區(qū)塊鏈布隆過濾器
2021-10-12 08:50:08牛保寧
計算機(jī)與生活 2021年10期
樊 星，牛保寧
太原理工大學(xué) 信息與計算機(jī)學(xué)院，山西 晉中 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ū)塊鏈應(yīng)用——以太坊[2]已經(jīng)產(chǎn)生10 029 304 個區(qū)塊，數(shù)據(jù)總?cè)萘窟_(dá)到127.06 GB，同比分別增加47.42%和53.88%。與以比特幣和以太坊為代表的公有鏈相比，許可鏈Hyperledger Fabric[3]由于有參與節(jié)點(diǎn)準(zhǔn)入限制，其數(shù)據(jù)冗余度沒有公有鏈的嚴(yán)重，但是，數(shù)據(jù)量也在隨著業(yè)務(wù)量的增加和參與節(jié)點(diǎn)的增加而快速增加。如何提高鏈上數(shù)據(jù)查詢性能對區(qū)塊鏈的推廣和應(yīng)用提出了巨大挑戰(zhàn)[4]。
在對區(qū)塊鏈數(shù)據(jù)分析時，經(jīng)常需要進(jìn)行數(shù)據(jù)查找操作。布隆過濾器（bloom filter，BF）[5]是一個高效的集合查詢工具，在以哈希運(yùn)算為主的區(qū)塊鏈應(yīng)用中不可或缺。輕量級節(jié)點(diǎn)由于本地沒有保存區(qū)塊數(shù)據(jù)，需要依賴遠(yuǎn)程全節(jié)點(diǎn)。為了保護(hù)輕量級節(jié)點(diǎn)的數(shù)據(jù)隱私[6]，提出由輕量級節(jié)點(diǎn)自主選擇誤判率，將布隆過濾器發(fā)送給遠(yuǎn)程節(jié)點(diǎn)，遠(yuǎn)程節(jié)點(diǎn)將運(yùn)算后的布隆過濾器及滿足條件的結(jié)果一起返回給輕量級節(jié)點(diǎn)，從而避免在數(shù)據(jù)查詢過程中隱私泄露。而對于保存完整數(shù)據(jù)的全節(jié)點(diǎn)，在查詢存儲在本地LevelDB數(shù)據(jù)庫的區(qū)塊數(shù)據(jù)時，利用布隆過濾器可以快速過濾不相干的數(shù)據(jù)，減少不必要的I/O 開銷，提高系統(tǒng)讀取性能。
可以看出，作為支持區(qū)塊鏈上數(shù)據(jù)查詢的基本工具，提高布隆過濾器的性能對于提高鏈上數(shù)據(jù)查詢、分析性能至關(guān)重要。
1 相關(guān)工作
綜上所述，布隆過濾器本質(zhì)上是一種巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，相比于傳統(tǒng)的List、Set、Map 等數(shù)據(jù)結(jié)構(gòu)，它更高效、占用空間更少，廣泛應(yīng)用于區(qū)塊鏈數(shù)據(jù)查詢中。然而，構(gòu)造布隆過濾器需要大量的內(nèi)存訪問和哈希計算，這將成為區(qū)塊鏈數(shù)據(jù)查詢的性能瓶頸。迄今為止，提高布隆過濾器性能的研究主要集中在降低內(nèi)存訪問和減少哈希函數(shù)計算開銷上，并沒有特定針對區(qū)塊鏈應(yīng)用的布隆過濾器優(yōu)化研究。
降低訪存開銷主要通過限定布隆過濾器的長度和改變哈希函數(shù)。OMBF（one-memory bloom filter）[7]和Bloom-1[8]將元素的映射位限制在一個緩存行內(nèi)，保證一個元素映射的k位能在一個緩存行中完成讀取。OMASS（one memory access set separation）[9]通過將k次哈希函數(shù)變換為更復(fù)雜的運(yùn)算，減少在字選擇階段造成的額外的訪存次數(shù)。它們的共同問題是：訪存開銷的減少是以增加哈希函數(shù)計算復(fù)雜度為代價的。
減少哈希函數(shù)計算開銷主要是通過共享哈希函數(shù)計算。LHBF（less Hashing bloom filter）[10]利用兩個偽隨機(jī)哈希函數(shù)h1(x)和h2(x)作為種子函數(shù)，根據(jù)構(gòu)造公式gi=h1(x)+ih2(x)生成多個哈希函數(shù)。另一種思路是：利用O(lgk)個種子函數(shù)產(chǎn)生k個相互獨(dú)立的哈希函數(shù)[11]。然而，這些方案缺乏對合成哈希函數(shù)間獨(dú)立性的理論分析，且并未針對區(qū)塊鏈數(shù)據(jù)的特性進(jìn)行優(yōu)化，還存在提升的空間。此外，在對布隆過濾器位向量分段情況下，Bloom-1[8]、Parallel BF[12]通過同時訪問多個組實(shí)現(xiàn)并行計算。然而，這類并行優(yōu)化只適用于順序查找，并且多核CPU 固有的并行性使得程序需要進(jìn)行重寫，可行性差。
總之，現(xiàn)有的布隆過濾器并沒有充分利用區(qū)塊鏈數(shù)據(jù)特性及通用設(shè)備計算資源，存在很大的優(yōu)化空間。在現(xiàn)有研究的基礎(chǔ)上，本文提出一種新的適用于區(qū)塊鏈應(yīng)用的布隆過濾器，即區(qū)塊鏈布隆過濾器（blockchain bloom filter，BBF）。與原始布隆過濾器相比，它的內(nèi)存訪問次數(shù)和哈希計算開銷更低。在此基礎(chǔ)上，利用SIMD（single instruction multiple data）指令來對布隆過濾器的構(gòu)造和查詢過程進(jìn)行并行化，進(jìn)一步提高BBF 元素查找性能。
2 BBF 設(shè)計與理論分析
本章討論了BBF 的實(shí)現(xiàn)方法，并分析了它的假陽性概率。BBF 設(shè)計的最終目標(biāo)是提供一種新的適合區(qū)塊鏈數(shù)據(jù)特性的布隆過濾器。
2.1 新型BBF 架構(gòu)
布隆過濾器由一個n比特的位數(shù)組S={x0x1…xn-1}和k個彼此獨(dú)立的哈希函數(shù){h1,h2,…,hk}組成，位數(shù)組初始化為0。插入元素xs時，將元素xs通過k個哈希函數(shù)產(chǎn)生對應(yīng)的k個哈希值，以哈希值作為位數(shù)組中的下標(biāo)，將k個對應(yīng)位置“1”。在查詢過程中，將該元素通過k個哈希函數(shù)映射到對應(yīng)的比特位，如果存在映射位為“0”，則說明該元素一定不在集合內(nèi)。
通過布隆過濾器的預(yù)過濾操作，可以提高數(shù)據(jù)的查找效率，然而，傳統(tǒng)的布隆過濾器在一次數(shù)據(jù)查詢過程中可能存在多次訪存失敗的情況。這是因?yàn)樵趨^(qū)塊鏈應(yīng)用中，數(shù)以億計的數(shù)據(jù)信息和有限的內(nèi)存資源使得布隆過濾器需要選擇片外存儲方式。而區(qū)塊鏈數(shù)據(jù)以文件形式存儲，一個布隆過濾器中往往對應(yīng)數(shù)以萬計的元素，相應(yīng)的，其包含的位數(shù)增多，只能連續(xù)存儲在多個緩存行（cache-line）上。那么在最壞情況下，進(jìn)行一次區(qū)塊（交易）查詢就會造成k次訪存缺失，這對于查詢性能的影響是致命的。
為了降低布隆過濾器計算中產(chǎn)生的訪存缺失，本文提出一種具有新型布隆過濾器數(shù)據(jù)結(jié)構(gòu)的BBF。如圖1 所示，BBF 由r個連續(xù)的長度為lg的組（group）組成，r為2 的冪次方，每個組由k個長度為lw字（word）組成，即lg=k×lw，哈希函數(shù)與word一一對應(yīng)，滿足一個word可以被加載到一個通用寄存器的緩存行中，即lw=32(64)bit。一個BBF 有m位，滿足關(guān)系m=r×lg=r×k×lw。在元素插入及查詢過程中，將其映射到一個包含連續(xù)的k個word的group中，保證組（group）的長度小于緩存行。
Fig.1 BBF structure圖1 BBF 架構(gòu)
通過改進(jìn)布隆過濾器結(jié)構(gòu)，一個元素的映射空間限制在一個group中。而一個緩存行可以保存至少一個group，那么在查詢過程中，一次訪存操作就可以讀取到多個group。即使元素映射到的組不在緩存中，也只需要一次訪存操作即可讀取全部映射位，從而將訪存失敗次數(shù)限制到1 次。為了保證元素與組（group）對應(yīng)，還需要一個額外的組選擇函數(shù)。
由于BBF 結(jié)構(gòu)發(fā)生改變，可能造成假陽性的變化，為了簡化描述過程，下面對BBF 和BF 兩者的假陽性進(jìn)行分析，分別用pBBF和pBF表示。圖2 中描述了元素x1的插入過程，哈希函數(shù)均選擇布隆過濾器中常用的Murmurhash3[13]函數(shù)，k=4，lw=4 。對于BF，插入過程可以分為①哈希映射階段和②取模階段。而對于BBF，插入過程可以分為①組選擇階段，②哈希運(yùn)算階段和③取模階段。在哈希運(yùn)算階段，元素經(jīng)過k次哈希運(yùn)算；在取模階段，將k個哈希值做取模運(yùn)算，并將對應(yīng)位置“1”。
根據(jù)文獻(xiàn)[5]BF 假陽性為：
BBF 通過組映射函數(shù)將元素映射到一個選定的組中，然后通過k個哈希函數(shù)將組中k個word中的對應(yīng)位置“1”，其中哈希函數(shù)和word一一對應(yīng)。如圖2所示，假定元素x1映射到group1。
BBF 保證元素映射到任意group的概率相等，假陽性事件J表示元素xs不屬于集合S，但誤判屬于S的情況。BBF 中g(shù)roup中任意word未被置“1”的概率為1-1/lw。插入z(z∈[0,n])個元素后，該位仍未被置“1”的概率為(1-1/lw)z，由此可知該位被置1 的概率為1-(1-1/lw)z。用隨機(jī)變量Z 表示映射到group中的元素個數(shù)。則當(dāng)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ā)生概率服從二項(xiàng)分布，即Z～B(n,1/r)，由此可得：
由式（1）、式（2）可知，BBF 假陽性概率為：
對于給定元素集合，布隆過濾器位數(shù)越少，函數(shù)碰撞率越高，相應(yīng)的，假陽性概率也越高。通過式（1）、式（3）無法直觀比較兩者的假陽性差異，因此對它們的假陽性進(jìn)行了數(shù)值分析，n=104，k=4。定義填充率（fill factor，F(xiàn)）為F=n/m；負(fù)載因子L=a/m，其中a為向量中填充為“1”的位數(shù)。負(fù)載因子表示布隆過濾器中的元素被填充的程度，L越大則布隆過濾器中的元素越多，空間利用率越高。然而，過高的空間利用率可能會導(dǎo)致哈希函數(shù)的高碰撞率和高誤判率。
哈希表（HashMap）[14]與布隆過濾器類似，都是將當(dāng)前元素的關(guān)鍵字通過哈希函數(shù)映射到數(shù)組中的某個位置，當(dāng)兩個不同的元素通過哈希函數(shù)得到的存儲地址相同時，就會產(chǎn)生哈希碰撞。為了減少哈希函數(shù)的碰撞概率，當(dāng)哈希表的數(shù)組長度達(dá)到一個臨界值就會觸發(fā)擴(kuò)容，此時需要將所有元素重新進(jìn)行哈希運(yùn)算再放回到容器中，這是一個非常耗時的操作。可以看出，臨界值的選擇尤為重要，而這個臨界值由負(fù)載因子和當(dāng)前的容量大小共同決定。在理想情況下，節(jié)點(diǎn)出現(xiàn)的頻率在哈希桶中的概率服從泊松分布，實(shí)驗(yàn)表明選擇0.75 作為負(fù)載因子是哈希表對于空間和時間成本的一種折中。考慮到BBF構(gòu)建過程中存在哈希沖突，存在a≤k×n，因此L=a/m≤(k×n)/m。
從圖3（a）可以看出，隨著填充率F增加，BF和BBF（lw=32,64）假陽性概率變化趨勢一致。當(dāng)F∈[0.80,1.00]時，變化曲線趨于平緩。圖3（b）為F∈[0.02,0.20]時的pBF和pBBF變化情況。圖3（b）右（次）縱坐標(biāo)軸為BBF 與BF 的假陽性概率相對差異，定義為D=(pBBF-pBF)/pBF。當(dāng)F較小時，BBF 與BF 的假陽性差值變化較大。隨著填充率的增加，兩者之間的差異越來越小。當(dāng)lw從32 bit 增加到64 bit 時，兩者的差異D幾乎減半。當(dāng)F從0.02 增加到0.20 時，pBF和pBBF(lw=32) 的假陽性概率相對差異從2.98 降低到0.10。類似地，pBF和pBBF(lw=64)之間的假陽性概率相對差異從1.28 減少到0.05。綜上所述，可以得出結(jié)論：在相同的假陽性概率下，BBF 比BF 需要更多的比特位，這是因?yàn)樵氐挠成湮槐幌拗圃谝粋€范圍內(nèi)，所以哈希函數(shù)碰撞率隨之增加。因此，從降低BBF 假陽性概率的角度來看，lw應(yīng)該盡可能長。然而，實(shí)際情況中l(wèi)w受到緩存行的限制。
Fig.3 False positive ratio of BF and BBF(lw=32,64)圖3 BF 及BBF（lw=32,64）假陽性概率
雖然與BF 相比，BBF 假陽性概率更高，但可以通過增加更多的映射位來彌補(bǔ)這一缺陷。實(shí)驗(yàn)發(fā)現(xiàn)，當(dāng)pBF=pBBF(lw=32)=0.015 6 時，BF 和BBF 分別需要86 650 bit和100 000 bit。而當(dāng)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é)構(gòu)，雖然能夠節(jié)省訪存開銷次數(shù)，但是需要增加一次組選擇哈希函數(shù)計算，將元素映射到指定的group中，產(chǎn)生了額外的計算開銷，因此本節(jié)對BBF 中涉及的哈希計算進(jìn)行優(yōu)化。
布隆過濾器中的計算開銷主要來自兩方面：元素插入時哈希函數(shù)的計算和成員查詢的哈希計算過程。根據(jù)區(qū)塊鏈數(shù)據(jù)的特性，區(qū)塊（交易）哈希值是對原始數(shù)據(jù)經(jīng)過哈希函數(shù)運(yùn)算（SHA256）的結(jié)果，是區(qū)塊（交易）的唯一標(biāo)識符。而區(qū)塊鏈與布隆過濾器選取哈希函數(shù)的原則一致，都是要保證函數(shù)的隨機(jī)性、不可逆、低碰撞。傳統(tǒng)布隆過濾器采用Murmurhash3函數(shù)而不是SHA256 的原因主要是考慮到布隆過濾器需要頻繁的哈希運(yùn)算，雖然SHA256 能夠滿足以上三個特性，但由于其計算量大，因此沒有作為布隆過濾器中的通用哈希函數(shù)。而區(qū)塊鏈數(shù)據(jù)特性決定區(qū)塊鏈中的數(shù)據(jù)都是由SHA256 標(biāo)識，因此，本文提出將SHA256 視為種子函數(shù)，利用區(qū)塊鏈中的哈希值派生出k個哈希候選值而不是設(shè)計多個哈希函數(shù)，從而簡化哈希計算。
在設(shè)計使用一個哈希函數(shù)執(zhí)行布隆過濾器的研究中，如何使用一個哈希函數(shù)模擬出k個哈希函數(shù)并證明這k個哈希函數(shù)相互獨(dú)立是一個研究難點(diǎn)。而目前的文獻(xiàn)研究局限于使用一定數(shù)量的種子哈希函數(shù)去模擬出k個哈希函數(shù)的方法，并沒有從理論上證明模擬出來的哈希函數(shù)是相互獨(dú)立的[10,15]。布隆過濾器假陽性概率的分析過程都假設(shè)使用的k個哈希函數(shù)完全隨機(jī)，并且相互獨(dú)立。雖然這些方法有效降低了哈希計算量，但由于缺少哈希函數(shù)獨(dú)立性證明，使得這些方法不能保證布隆過濾器的實(shí)際假陽性概率與理論分析值一致。
本文提出的BBF 通過利用區(qū)塊鏈數(shù)據(jù)特性，可以將其視為單哈希布隆過濾器。為了消除對于單哈希布隆過濾器相比傳統(tǒng)布隆過濾器可能造成假陽性概率升高的顧慮，進(jìn)一步論證如下：
BBF 與BF 的實(shí)際假陽性概率差異可能并不如理論中那樣明顯。這是因?yàn)閷?shí)際中用到的哈希函數(shù)并非是理想狀況下完全隨機(jī)的哈希函數(shù)。所有關(guān)于布隆過濾器的理論分析都是基于以下兩個關(guān)于哈希函數(shù)的假設(shè)：（1）完全隨機(jī)。布隆過濾器中使用的所有哈希函數(shù)是完全隨機(jī)的，哈希函數(shù)可以將所有的數(shù)據(jù)元素均勻地映射到整個布隆過濾器范圍內(nèi)。（2）相互獨(dú)立。布隆過濾器中使用的所有哈希函數(shù)相互之間是獨(dú)立的。
然而，文獻(xiàn)[16]中測試了一些實(shí)際應(yīng)用中具有代表性的哈希函數(shù)的隨機(jī)性和獨(dú)立性，結(jié)果顯示實(shí)際中的哈希函數(shù)并不能達(dá)到理想狀態(tài)下完全隨機(jī)，特別是將哈希函數(shù)進(jìn)行組合之后發(fā)現(xiàn)，當(dāng)哈希函數(shù)組合中存在未能通過獨(dú)立性測試的哈希函數(shù)時，相應(yīng)的哈希函數(shù)組合就無法通過隨機(jī)性測試。也就是說，哈希函數(shù)之間存在某種弱相關(guān)性。這種弱相關(guān)性會導(dǎo)致BF 中的多哈希函數(shù)組合假陽性概率跟理論假陽性概率相差很大。
因此在應(yīng)用布隆過濾器時，哈希函數(shù)的選擇是非常困難的，尤其是對于比較大的k值。一個差的哈希函數(shù)組合選擇會導(dǎo)致實(shí)際假陽性概率跟理論假陽性概率差值很大[17]。對于一個隨機(jī)性好的哈希函數(shù)，盡管初始化種子不同會展現(xiàn)出比較好的獨(dú)立特性，但哈希函數(shù)的計算仍然會導(dǎo)致計算開銷成倍增加。相反，在單哈希布隆過濾器中，它只需要一個隨機(jī)性好的種子哈希函數(shù)。實(shí)際中需要的哈希函數(shù)越少，就越容易做出正確的選擇。另外，如果哈希函數(shù)間的相關(guān)性被消除，實(shí)際的假陽性概率會更接近于理論值。可以將BBF 視為一種單哈希布隆過濾器，選取滿足哈希函數(shù)隨機(jī)性和獨(dú)立性測試的SHA256 作為種子函數(shù)。
在組選擇階段，可以將組選擇哈希函數(shù)簡化為一次取模運(yùn)算j=xsmodr，j為BBF 中映射到的組號。元素映射到任意組后，將元素根據(jù)式（4）映射為k個候選元素，與word一一對應(yīng)，lk為原始位數(shù)。
嚴(yán)格來說，BBF 的哈希映射過程仍然有k個相互獨(dú)立的哈希函數(shù)參與，相應(yīng)地，一個元素對應(yīng)產(chǎn)生k個映射位。不同之處在于，這k個哈希函數(shù)是由k個按位與運(yùn)算（and）產(chǎn)生的。此外，當(dāng)m為2 的冪次方時，根據(jù)計算機(jī)指令集[18]可知，按位與運(yùn)算與取模運(yùn)算（modulo）等價，而后者的計算復(fù)雜度較前者高，因此可以通過限定m的取值，將取模運(yùn)算替換為按位與運(yùn)算（and），進(jìn)一步提高計算效率。
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 的構(gòu)建（查詢）過程可以細(xì)分為①組選擇階段，②哈希運(yùn)算階段和③位運(yùn)算階段。元素xs首先被映射到groupj，然后經(jīng)過k次按位與運(yùn)算后得到候選集。最后將候選集的k個元素分別映射到groupj的k個word中，并將對應(yīng)位置“1”。BBF 構(gòu)建過程為：
步驟1j=xs&(2r-1)，將元素xs映射到groupj；
步驟2將元素xs按照式（4）分為k段；
步驟3將候選集中的k個元素映射到對應(yīng)的word中，映射規(guī)則為，并將對應(yīng)位置“1”。
圖4 顯示了BBF（2.1 節(jié)中提到的訪存優(yōu)化）和BBF（訪存及哈希計算優(yōu)化）示意圖。與前一種方法相比，后一種方法不僅消除了哈希函數(shù)運(yùn)算過程，而且將取模操作改為低復(fù)雜度的位與運(yùn)算，完成一個元素插入只需要2k+1 次位與運(yùn)算，運(yùn)算復(fù)雜度大大降低。
為了定量分析哈希優(yōu)化的優(yōu)勢，下面以CPU（central processing unit）時鐘周期為度量方式，對BF和BBF 在執(zhí)行元素插入過程中的操作成本進(jìn)行比較，其中k=4，lk=32 B。時鐘周期是計算機(jī)中最基本的、最小的時間單位，它刻畫了同步動態(tài)隨機(jī)存取內(nèi)存（synchronous dynamic random-access memory，SDRAM）所能運(yùn)行的最高頻率，時鐘周期越低，則意味著工作頻率越高。在一個時鐘周期內(nèi)，CPU 僅完成一個最基本的動作。
在CPU 指令中，通常情況下，按位運(yùn)算需要3 個CPU 時鐘周期。在實(shí)驗(yàn)服務(wù)器上進(jìn)行性能測試表明，一次取模運(yùn)算平均需要6 個CPU 時鐘周期；選用Murmurhash3 作為哈希函數(shù)，每個字節(jié)平均需要23個CPU 時鐘周期。由表1 可知，對于一次元素插入操作，BBF 需要192 個時鐘周期，約為BF 計算量的5%。BBF 的性能較BF 有顯著提升，這是因?yàn)锽BF 的哈希計算量大大降低了。此外，由于普通哈希函數(shù)的計算時間成本隨著元素長度的增加而增加，觀察到隨著元素大小和哈希函數(shù)數(shù)目的增加，BBF 較BF 性能優(yōu)勢明顯。這一點(diǎn)在3.2節(jié)的實(shí)驗(yàn)中也得到了驗(yàn)證。
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 中元素插入和查詢效率，通過改變布隆過濾器結(jié)構(gòu)減少了訪存失敗的次數(shù)和哈希計算開銷。在成員查詢過程中，需要依序檢查元素對應(yīng)的k個映射位。如果所有的k位都設(shè)置為1，那么這個元素可能包含在集合中。考慮到元素在插入和查詢過程中k個候選元素彼此獨(dú)立，不存在相關(guān)性。如果能將它們并行化，就有可能進(jìn)一步改進(jìn)BBF。計算機(jī)硬件的進(jìn)步對軟件的編寫方式產(chǎn)生了巨大的影響，SIMD指令集[19]可以實(shí)現(xiàn)同時對p對數(shù)據(jù)流執(zhí)行算術(shù)運(yùn)算，即(c1,c2,…,cp)=(a1,a2,…,ap)+(b1,b2,…,bp)。
然而，BF 與SIMD 指令集并不適配，這是因?yàn)樵诓悸∵^濾器的查詢過程中，元素的映射位存在于整個布隆過濾器中，而SIMD 指令集可以同時處理加載到的連續(xù)位向量，提高數(shù)據(jù)處理效率。但是由于SIMD 一次讀入的數(shù)據(jù)有限，對于傳統(tǒng)的布隆過濾器，無法一次訪問全部映射位，從而無法充分利用SIMD 指令集的優(yōu)勢。而BBF 對BF 結(jié)構(gòu)的改變正好與SIMD 的特性相吻合，支持一次讀取k個待查詢比特位的并行處理。基于BBF 的結(jié)構(gòu)特性和運(yùn)行機(jī)制，SIMD 指令主要應(yīng)用在BBF 構(gòu)建和元素查詢兩方面，提高元素插入/查詢效率。在元素插入過程中顯式調(diào)用SIMD 指令，偽代碼見算法1。
算法1BBF 構(gòu)建算法
輸入:xs區(qū)塊鏈交易哈希值。
輸出:BBFo1。
相應(yīng)地，BBF在元素查詢階段的偽代碼見算法2。
算法2BBF 元素查詢算法
輸入:xs，BBFs（BBF 候選集合）。
輸出:BBFt目標(biāo)BBF。
3 實(shí)驗(yàn)與結(jié)果分析
為了優(yōu)化區(qū)塊鏈應(yīng)用中的布隆過濾器，本文提出三個改進(jìn)措施。本章對BBF 性能進(jìn)行了實(shí)驗(yàn)。
3.1 實(shí)驗(yàn)設(shè)置
實(shí)驗(yàn)環(huán)境為Intel?CoreTMi7-8700K CPU@3.70 GHz，32 GB內(nèi)存。每個核心有獨(dú)立的一級緩存（L1 D-Cache 32 KB，L1 I-Cache 32 KB）和二級緩存（256 KB）。6個核心共享三級緩存（12 MB），緩存行為64 B。實(shí)驗(yàn)使用AVX2 指令集，支持256 bit 整數(shù)算術(shù)運(yùn)算。Gcc編譯器支持AVX2 指令的程序設(shè)計。
實(shí)驗(yàn)選用存儲在LevelDB 數(shù)據(jù)庫中的比特幣數(shù)據(jù)集，lk=256。數(shù)據(jù)集1 為交易索引，表示為<‘t’+32-byte transaction hash，transaction index record>，共50 000 000 項(xiàng)；數(shù)據(jù)集2 為區(qū)塊索引，描述為<‘b’+32-byte block hash，block index record>，共50 000 項(xiàng)。在元素查詢性能實(shí)驗(yàn)中，正向查詢是指查找屬于集合的元素，負(fù)向查詢是指查找不屬于集合中的元素。布隆過濾器的位數(shù)組是緩存行對齊的，使用每秒百萬次搜索（MSPS）作為查詢速度評價指標(biāo)。實(shí)驗(yàn)采用BF[5]和OMBF[7]作為對比方法。BF 為標(biāo)準(zhǔn)布隆過濾器，OMBF 是一種最先進(jìn)的布隆過濾器方法，它通過減少緩存丟失來提高成員查詢性能。
3.2 性能評價
（1）假陽性概率。實(shí)驗(yàn)選取pBBF(lw=64)在兩個數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)。如圖5 所示，不同數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果與2.1 節(jié)中的理論分析變化趨勢一致，實(shí)驗(yàn)結(jié)果基本吻合，可以得出BBF 成員查詢方法具有良好的隨機(jī)性，參數(shù)設(shè)置符合預(yù)期，驗(yàn)證了2.1 節(jié)中對于BBF 的假陽性概率分析。同時，為后續(xù)實(shí)驗(yàn)中填充率的選擇設(shè)置起到指導(dǎo)作用。
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 指令又進(jìn)一步提高了BBF的查找性能。圖6為在不同數(shù)據(jù)集上布隆過濾器查找性能對比，n=105,m=106,F=0.1。
理論上來說，正向查詢相比負(fù)向查詢需要檢查更多的映射位，因此哈希運(yùn)算數(shù)也會增加，對于BF 和OMBF，圖6（a）中的正向查詢相比圖6（b）中的負(fù)向查詢性能有所降低。隨著哈希函數(shù)個數(shù)k的增加，BF 和OMBF 查詢速度呈下降趨勢。這主要是因?yàn)锽F 和OMBF 在查詢過程中使用串行位檢測。隨著k的增加，待檢測比特位也隨之增加，因此速度下降。而BBF 采取并行的位檢測方法，顯示出近似恒定的查詢速度。
OMBF 的性能優(yōu)勢在于降低成員查詢過程中的內(nèi)存訪問開銷，在本實(shí)驗(yàn)環(huán)境中，CPU 有足夠的緩存（32 GB），因此OMBF 的成員查詢速度較BF 相比，查詢性能優(yōu)勢并不明顯。從圖中可以看出，當(dāng)k=8 時，在正向查詢中，BBF 的成員查詢速度分別為BF 和OMBF 的4 倍、3 倍；在負(fù)向查詢中，BBF 的成員查詢速度是其他兩類布隆過濾器的2 倍，BBF 較其他兩類具有代表性的布隆過濾器BF 和OMBF，查詢性能更優(yōu)。
Fig.7 m vs.membership query performance of BF圖7 m vs.布隆過濾器元素查詢性能
圖7 為布隆過濾器位數(shù)m與布隆過濾器查找性能的變化關(guān)系圖，為了表明緩存與查找性能之間的關(guān)系，將L1、L2 和L3 三級緩存在圖中做了標(biāo)識。當(dāng)CPU 緩沖區(qū)足夠大時（m
4 結(jié)論
本文提出了一種針對區(qū)塊鏈應(yīng)用的新型布隆過濾器BBF。通過改進(jìn)布隆過濾器數(shù)據(jù)結(jié)構(gòu)減少訪存缺失次數(shù)，同時提出一種簡化的三階段哈希運(yùn)算。在此基礎(chǔ)上，運(yùn)用SIMD 指令實(shí)現(xiàn)元素插入及查找并行化。實(shí)驗(yàn)結(jié)果表明，BBF 僅需要11.98%額外的映射位，就能在假陽性概率不變的同時，較其他兩種廣泛應(yīng)用的布隆過濾器性能有顯著提升。
