雷 蒙，肖文超，高佳寧，廖雪花

（1.四川師范大學(xué)計算機(jī)科學(xué)學(xué)院；2.四川師范大學(xué)物理與電子工程學(xué)院，四川成都 610101）

0 引言

傳統(tǒng)應(yīng)用開發(fā)會直接從數(shù)據(jù)庫讀取數(shù)據(jù)，大數(shù)據(jù)環(huán)境下，高并發(fā)請求頻繁地訪問磁盤操作數(shù)據(jù)［1］，會導(dǎo)致系統(tǒng)卡頓等嚴(yán)重問題，成為整個應(yīng)用系統(tǒng)的性能瓶頸。為緩解數(shù)據(jù)庫訪問壓力，減少頻繁地讀寫操作，通常會選擇在業(yè)務(wù)與數(shù)據(jù)庫之間加入一層緩存。

高并發(fā)場景下，若某個無效key 被高并發(fā)訪問且沒有命中，出于對容錯性的考慮，會去數(shù)據(jù)庫中獲取，導(dǎo)致數(shù)據(jù)庫執(zhí)行了大量不必要的查詢操作，從而帶給數(shù)據(jù)庫巨大沖擊與壓力。解決此類緩存擊穿問題的傳統(tǒng)思路為利用HashTable［2］，但需要耗費(fèi)大量資源，成本太高。目前流行的解決方式是采用布隆過濾器（Bloom Filter，BF）［3-4］。通常對于數(shù)據(jù)庫中數(shù)據(jù)的key 值，可以將其預(yù)先存儲在布隆過濾器中，然后在布隆過濾器中進(jìn)行過濾。如果發(fā)現(xiàn)布隆過濾器中沒有，就去緩存服務(wù)（如redis）中查詢，如果緩存服務(wù)（如redis）中也沒有數(shù)據(jù)，就再去數(shù)據(jù)庫查詢，這樣可以避免不存在的數(shù)據(jù)信息也到存儲庫中進(jìn)行查詢的情況。

Table 1 Test environment configuration表1 測試環(huán)境配置

Table 2 Comparison of construction（insertion）time of different numbers of strings表2 不同數(shù)目字符串構(gòu)建（插入）時間比較

Table 3 Comparison of index time of different numbers of strings表3 不同數(shù)目字符串索引時間比較

Table 4 Comparison of memory space of different numbers of strings表4 不同數(shù)目字符串內(nèi)存空間比較

布隆過濾器可以高效查詢元素是否在指定集合中，目前已廣泛應(yīng)用于元素查詢［5-7］。利用布隆過濾器可以快速過濾不相干的數(shù)據(jù)，減少不必要的I/O 開銷，提高系統(tǒng)讀取性能。布隆過濾器在識別郵件黑名單、過濾重復(fù)資源的效率上有一定優(yōu)勢，同時因其在同等數(shù)量級下占用內(nèi)存小、查找效率高而得以廣泛應(yīng)用。

本文提出一種新型的基于位標(biāo)識的可擦寫高效過濾器算法，采用改進(jìn)后的前綴樹［8-9］作為基本結(jié)構(gòu)，將傳統(tǒng)樹結(jié)構(gòu)中的字符改進(jìn)為位（bit）數(shù)組存儲，并動態(tài)構(gòu)建過濾器。相較于傳統(tǒng)的布隆過濾器，在保證查詢效率以及占用盡可能少的內(nèi)存空間基礎(chǔ)上，具備了可擦寫特性，由于前綴樹自身結(jié)構(gòu)支持刪除操作，因此改進(jìn)后的布隆過濾器可以便捷地完成刪除操作從而實現(xiàn)0 誤判率，能夠更好地應(yīng)用于高并發(fā)場景下的系統(tǒng)開發(fā)。

1 相關(guān)工作

布隆過濾器自巴頓布隆于1970 年提出以來［10-11］，被廣泛應(yīng)用于各種計算機(jī)系統(tǒng)以表示龐大數(shù)據(jù)并提高查找效率［12］。布隆過濾器是一種通過多個哈希函數(shù)的映射對參數(shù)存儲空間進(jìn)行壓縮的數(shù)據(jù)結(jié)構(gòu)［13］，由于其自身結(jié)構(gòu)特性，布隆過濾器存在無法刪除及假陽性等缺陷，大量研究工作者提出了一些改進(jìn)方案并將其應(yīng)用于各類應(yīng)用系統(tǒng)。

王乾等［14］提出將布隆過濾器改為雙向量的結(jié)構(gòu)使其適合硬件，實現(xiàn)并行過濾，降低了查找延遲，提高了端口吞吐率。為了支持元素的刪除，F(xiàn)an 等［15］提出計數(shù)布隆過濾器（Counting Bloom filter，CBF），其本質(zhì)上是一個計數(shù)數(shù)組，每個計數(shù)器大小為d位，與傳統(tǒng)布隆過濾器相比，會產(chǎn)生d倍的存儲開銷，并且在判斷集合成員時需要同時判斷k個哈希地址對應(yīng)計數(shù)器的值；Fan 等［16］提出支持刪除操作的布谷鳥過濾器（Cuckoo filter，CF），其本質(zhì)上是由m個桶組成的數(shù)組，每個桶包含b個基本存儲單元，每個存儲單元被稱為槽。王飛越［17］采用“兩種選擇的力量”策略改進(jìn)布谷鳥布隆過濾器并將其應(yīng)用于實際；Yu 等［18］提出一種基于單哈希函數(shù)的新型布隆過濾器，提高了布隆過濾器的查詢效率，假陽性與傳統(tǒng)布隆過濾器近似相同；耿宏等［19］提出一種動態(tài)布隆計數(shù)樹（DBCT）型數(shù)據(jù)結(jié)構(gòu)存儲元素集合，通過對每個字節(jié)增加計數(shù)器記錄對應(yīng)字節(jié)被置位的次數(shù)以完成刪除操作。雖然這些研究工作在對布隆過濾器進(jìn)行一定改進(jìn)后都滿足了特定需求，但整體上存在以下幾點問題：

（1）誤算率（假陽性）問題。隨著布隆過濾器中元素數(shù)量的增加，誤算率隨之增加，難以消除。

（2）刪除問題。由于布隆過濾器中的每位都被多個元素共享，因此不支持刪除操作。改進(jìn)版的計數(shù)型布隆過濾器雖然可以提供刪除功能，但代價是將原有空間增大d倍（計數(shù)器占用空間）且在某種程度上降低了系統(tǒng)性能。

2 基本原理

2.1 前綴樹結(jié)構(gòu)

前綴樹又稱單詞查找樹，它是由鏈接結(jié)點組成的數(shù)據(jù)結(jié)構(gòu)，這些鏈接可能為空，也可能指向其他結(jié)點［20］。傳統(tǒng)單詞查找樹的每個結(jié)點都有R 條鏈接，其中R 為字母表大小，結(jié)構(gòu)如圖1 所示。單詞查找樹的構(gòu)建效率及查詢效率均為O（k），k為字符串長度，與單詞查找樹中存儲的元素總數(shù)無關(guān)，因此，其查詢效率通常比二叉搜索樹及哈希樹更快。此外，根據(jù)其自身結(jié)構(gòu)特性，單詞查找樹可通過將某節(jié)點設(shè)置為空（null）來完成刪除操作，以及在查詢時不存在誤判率。因此，本文提出選用前綴樹結(jié)構(gòu)對傳統(tǒng)布隆過濾器進(jìn)行改進(jìn)研究。

Fig.1 An example of the traditional R-direction word search tree structure圖1 傳統(tǒng)R向單詞查找樹結(jié)構(gòu)示例

由于傳統(tǒng)R 向單詞查找樹的很多結(jié)點都為空結(jié)點，稀疏現(xiàn)象嚴(yán)重，因此其空間利用率較低［13］，屬于典型的“空間換時間”策略。為了避免R 向單詞查找樹在空間上的過度消耗，本文算法采用改進(jìn)的前綴樹，即動態(tài)構(gòu)建有效結(jié)點，避免大量無效空節(jié)點占用內(nèi)存，降低了內(nèi)存空間消耗，改進(jìn)的動態(tài)構(gòu)建樹結(jié)構(gòu)如圖2所示。

Fig.2 An example of an improved dynamic tree structure圖2 改進(jìn)的動態(tài)構(gòu)建樹結(jié)構(gòu)示例

對比傳統(tǒng)R 向單詞查找樹中每個非空鏈接隱式地表示其對應(yīng)字符，改進(jìn)后的動態(tài)單詞查找樹是顯式地保存在每個結(jié)點中。

通過對常用的前綴樹進(jìn)行結(jié)構(gòu)分析，本文設(shè)計了一種新型的基于位標(biāo)識的動態(tài)前綴樹結(jié)構(gòu)，并將其用于實現(xiàn)可擦寫的高效過濾器算法中，解決傳統(tǒng)布隆過濾器難以刪除的問題及避免出現(xiàn)誤判率的情況。基于位標(biāo)識的可擦寫過濾器基本結(jié)構(gòu)如圖3 所示，將傳統(tǒng)結(jié)點中存儲的字符用一系列二進(jìn)制向量即位（bit）數(shù)組代替。使用占用空間更小的比特位標(biāo)識字符，能夠有效減少空間占用率。假設(shè)存儲1 億個char 類型（占2 字節(jié)）的字符，大約需占用1.8GB存儲空間，而存儲1 億個位數(shù)據(jù)只需大約119MB，即約為0.11GB，所占空間是其1/16 倍。由此可見，選用位數(shù)組優(yōu)化可以極大降低存儲空間，更適用于系統(tǒng)應(yīng)用。

Fig.3 An example of the structure of erasable filter based on bit identification圖3 基于位標(biāo)識的可擦寫過濾器結(jié)構(gòu)示例

2.2 構(gòu)建流程

基于位標(biāo)識的可擦寫過濾器構(gòu)建流程如圖4 所示，具體步驟如下：

Fig.4 Construction flow chart圖4 構(gòu)建流程

Step1：獲取字符串Key 的第i個字符，判斷子結(jié)點是否為空，從根結(jié)點開始：若當(dāng)前結(jié)點的子結(jié)點為空，執(zhí)行Step2；若當(dāng)前結(jié)點的子結(jié)點不為空，執(zhí)行Step3。

Step2：創(chuàng)建新的子結(jié)點children（key：位數(shù)組；TrieNode：樹結(jié)點），將第i個字符存儲到節(jié)點對應(yīng)的位數(shù)組中，即將位數(shù)組中下標(biāo)為該字符的二進(jìn)制位設(shè)置為1。

Step3：判斷當(dāng)前結(jié)點的子節(jié)點記錄中是否存在第i個字符對應(yīng)的TrieNode 節(jié)點，且Key［i］非字符串的最后一位：若存在，則向下構(gòu)建樹，獲取第（i+1）個字符：Key［i+1］，執(zhí)行Step1；若不存在，創(chuàng)建TrieNode 節(jié)點，將其存入children中Key［i］對應(yīng)的位置中，執(zhí)行Step4。

Step4：判斷當(dāng)前字符是否為字符串最后一位：若是，則將當(dāng)前節(jié)點結(jié)束標(biāo)記置為1，執(zhí)行Step5；若否，則向下構(gòu)建樹，獲取第（i+1）個字符：Key［i+1］，執(zhí)行Step1。

Step5：結(jié)束。

3 實現(xiàn)過程

3.1 索引過程

基于位標(biāo)識的可擦寫過濾器索引元素流程如圖5 所示，具體步驟如下：

Step1：獲取字符串Key 的第i 位元素，從根結(jié)點（root）開始：若當(dāng)前結(jié)點的子節(jié)點為空（null），則返回false，表示未命中；否則，執(zhí)行Step2。

Fig.5 Index flow chart圖5 索引流程

Step2：判斷子節(jié)點是否存在以字符Key［i］值為下標(biāo)的位數(shù)組：若存在，執(zhí)行Step3；若不存在，返回false，表示未命中。

Step3：判斷當(dāng)前Key［i］是否為字符串最后一位元素：若是，執(zhí)行Step4；否則，繼續(xù)索引Key［i+1］位元素，執(zhí)行Step1。

Step4：判斷當(dāng)前節(jié)點的結(jié)束標(biāo)記是否為1：若是，表示字符串存在，返回true；否則，未命中，返回false。

Step5：結(jié)束。

3.2 刪除過程

本文設(shè)計的基于位標(biāo)識的過濾器存儲結(jié)構(gòu)本質(zhì)上是前綴樹Trie，因此具有可擦寫特性，可以很便捷地支持元素的刪除功能。由于應(yīng)用場景不同，可擦除過濾器算法在刪除元素時，只需將元素（字符串key）對應(yīng)結(jié)點中的位數(shù)組全部置為0 即可。在刪除過程中，若遇到某個結(jié)點含有其余子結(jié)點，則無須繼續(xù)進(jìn)行操作；若該結(jié)點的所有鏈接均為空，即：對應(yīng)結(jié)點的位數(shù)組中沒有置位1 的位數(shù)，則可將其從數(shù)據(jù)結(jié)構(gòu)中刪除；若刪除該結(jié)點后，其父結(jié)點無任何鏈接，此時應(yīng)繼續(xù)將父結(jié)點刪除。刪除流程如圖6 所示，具體步驟如下：

Syep1：獲取字符串Key的第i個字符元素。

Step2：判斷子節(jié)點（key：位數(shù)組；TrieNode：樹節(jié)點）是否存在以字符Key［i］值為下標(biāo)的位數(shù)組對應(yīng)的TrieNode：若存在，執(zhí)行Step3；若不存在，執(zhí)行Step5。

Fig.6 Example of deletion process圖6 刪除流程示例

Step3：判斷當(dāng)前元素Key［i］是否為字符串最后一位：若為最后一位，執(zhí)行Step4；若不為最后一位，繼續(xù)讀取下一字符元素，執(zhí)行Step2。

Step4：判斷當(dāng)前子節(jié)點是否為空：若為空，將第i 個元素對應(yīng)的位數(shù)組置為0，刪除其對應(yīng)的樹節(jié)點TrieNode；若不為空，執(zhí)行Step5。

Step5：結(jié)束。

4 實驗對比與分析

4.1 環(huán)境配置說明

測試環(huán)境配置如表1所示。

4.2 數(shù)據(jù)測試分析

4.2.1 時間性能測試分析

（1）不同數(shù)目字符串（定長）構(gòu)建時間比較。使用定長的字符串，測試不同數(shù)目（萬級）字符串構(gòu)建傳統(tǒng)前綴樹及可擦寫高效過濾器的時間性能。字符串定長為5 時的具體測試數(shù)據(jù)如表2所示。

可以看出，隨著字符串?dāng)?shù)據(jù)10（萬）、20（萬）、40（萬）、60（萬）……遞增，基于位標(biāo)識的可擦寫過濾器能夠快速響應(yīng)，正確處理數(shù)據(jù)并完成構(gòu)建；而傳統(tǒng)的前綴樹方式消耗的構(gòu)建時間更多，且當(dāng)數(shù)據(jù)量增加至200（萬）及以上時，由于內(nèi)存溢出問題，系統(tǒng)無法正常響應(yīng)，完成構(gòu)建。圖7 直觀地反映了兩種方式下不同數(shù)目字符串的構(gòu)建時間情況。由此可知，本文提出的基于位標(biāo)識的可擦寫高效過濾器是可行的。

（2）不同數(shù)目字符串（定長）索引時間比較。使用定長的字符串，測試不同數(shù)目（萬級）字符串索引時間。字符串定長為5的具體測試數(shù)據(jù)如表3所示。

Fig.7 Comparison of the construction（insertion）time of different numbers of strings圖7 不同數(shù)目字符串構(gòu)建（插入）時間比較

由表3 可以看出，隨著字符串?dāng)?shù)據(jù)10（萬）、20（萬）、40（萬）、60（萬）……遞增，基于位標(biāo)識的可擦寫過濾器與傳統(tǒng)前綴樹方式在索引時間上的差異并不顯著，兩者的索引差值僅占很小一部分，性能相當(dāng)。圖8 直觀地反映了測試環(huán)境下兩種方式的索引時間情況。由此可知，本文提出的新型的基于位標(biāo)識的可擦寫過濾器可應(yīng)用于高并發(fā)場景下。

Fig.8 Comparison of indexing time of different numbers of strings圖8 不同數(shù)目字符串索引時間比較

4.2.2 空間性能測試分析

使用定長的字符串，測試不同數(shù)目（萬級）字符串構(gòu)建后傳統(tǒng)前綴樹與可擦寫過濾器的內(nèi)存空間使用情況。字符串定長為5時的具體測試數(shù)據(jù)如表4所示。

表4 給出了存儲10 萬～800 萬定長字符串時兩種算法的內(nèi)存空間使用情況?？梢钥闯?，新型的基于位的可擦寫高效過濾器的內(nèi)存空間使用最少。為進(jìn)一步分析這兩種結(jié)構(gòu)的空間性能，繪制圖9，用來顯示字符串?dāng)?shù)目從10 萬增至800 萬時傳統(tǒng)R 向前綴樹與基于位的可擦寫過濾器的空間差值變化情況。

Fig.9 Comparison of memory space of different numbers of strings圖9 不同數(shù)目字符串內(nèi)存空間比較

從圖9 可知，隨著字符串?dāng)?shù)量的增加，傳統(tǒng)R 向前綴樹與基于位的可擦寫過濾器之間的內(nèi)存使用差值不斷增加。當(dāng)測試數(shù)目增至100 萬時，傳統(tǒng)R 向前綴樹所使用的空間比基于位的可擦寫過濾器多了大約1.9GB，當(dāng)數(shù)目增至200 萬及以上時，系統(tǒng)內(nèi)存溢出。由此可知，本文提出的新型基于位的可擦寫過濾器較傳統(tǒng)前綴樹在內(nèi)存使用上有極大優(yōu)勢，更適用于高并發(fā)場景下的系統(tǒng)應(yīng)用。

5 結(jié)語

本文提出新型的基于位標(biāo)識的可擦寫高效過濾器算法，利用前綴樹自身結(jié)構(gòu)支持元素刪除的特性，解決傳統(tǒng)布隆過濾器中元素刪除困難問題及實現(xiàn)0 誤判率，并通過改進(jìn)傳統(tǒng)的前綴樹存儲結(jié)構(gòu)，將字符替換為占用空間更少的位（bit）數(shù)組，動態(tài)構(gòu)建樹結(jié)構(gòu)，減少大量無效的空節(jié)點，在保持索引時間復(fù)雜度的前提下，極大降低了內(nèi)存空間消耗，更適用于高并發(fā)下的系統(tǒng)開發(fā)。