基于位標識的可擦寫高效過濾器算法與實現(xiàn)

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

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

0 引言

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

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

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

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

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

Table 4 Comparison of memory space of different numbers of strings表4 不同數目字符串內存空間比較

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

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

1 相關工作

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

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

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

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

2 基本原理

2.1 前綴樹結構

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

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

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

Fig.2 An example of an improved dynamic tree structure圖2 改進的動態(tài)構建樹結構示例

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

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

Fig.3 An example of the structure of erasable filter based on bit identification圖3 基于位標識的可擦寫過濾器結構示例

2.2 構建流程

基于位標識的可擦寫過濾器構建流程如圖4 所示，具體步驟如下：

Fig.4 Construction flow chart圖4 構建流程

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

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

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

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

Step5：結束。

3 實現(xiàn)過程

3.1 索引過程

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

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

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

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

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

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

Step5：結束。

3.2 刪除過程

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

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

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

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

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

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

Step5：結束。

4 實驗對比與分析

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

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

4.2 數據測試分析

4.2.1 時間性能測試分析

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

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

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

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

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

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

4.2.2 空間性能測試分析

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

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

Fig.9 Comparison of memory space of different numbers of strings圖9 不同數目字符串內存空間比較

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

5 結語

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