面向大數據的高效布魯姆過濾器研究與應用.pdf

1、大數據正在成為繼云計算、物聯網、移動互聯網之后新的信息革命高潮。無論是從數據傳遞及共享、數據存儲，還是從數據檢索及分析，信息技術正面臨前所未有的挑戰(zhàn)。信息表示和查詢算法是進行數據傳遞及共享、數據存儲、數據檢索及分析時用到的關鍵技術之一。當數據膨脹時，借助簡潔的數據結構表示信息，并研究與之對應的高效查詢算法已成為提升和完成大規(guī)模數據管理的關鍵技術！作為信息表示和查詢算法之一的布魯姆過濾器(BF)是一種空間效率很高的隨機數據結構，具有計算復

2、雜度低、并行程度高等優(yōu)勢，已經廣泛應用于數據庫、分布式系統、網絡等場景中。
　　本論文針對大數據時代的應用場景，從命名數據網絡(NDN)路由器中名字快速查找、閃存中數據溫度識別、閃存鍵值存儲的索引結構、Hadoop-Join算法、多維屬性數據集查詢等五個方面展開BF研究，設計新的適應于不同環(huán)境與應用的高效BF，本文創(chuàng)新性研究成果主要體現在以下五個方面:
　　(1)設計了一種面向NDN中名字查找的哈希布魯姆過濾器
　　名

3、字查找算法是提高NDN中數據包轉發(fā)速率的關鍵技術之一。NDN使用類似URL層次化的命名機制，一個名字由沒有個數限制的詞元組成，每個詞元是一個可變長的字符串。這種命名特點使得名字查找比IP地址查找更加復雜、更加困難。為了實現快速名字查找，本文設計了一種面向NDN中名字查找的哈希布魯姆過濾器(HBF)。HBF由位于片內存儲器中的g個計數器布魯姆過濾器(CBF)、g個計數器和位于片外存儲器中的g個哈希表組成，每個哈希表與1個CBF和1個計數器

4、關聯。為了避免因部分CBF存入名字過多導致的HBF高誤判率，HBF通過二次哈希選擇算法將NDN路由器中FIB/CS/PIT表項完整信息均勻分散保存于g個CBF和g個哈希表中，同時也利于數據包轉發(fā)的并行處理。理論分析和實驗結果表明HBF利用片內存儲器中CBF的定位與過濾作用，大幅度減少片外存儲器的訪問開銷，提高數據包轉發(fā)速率，同時有效避免泛洪攻擊。
　　(2)設計了一種面向閃存的數據溫度感知布魯姆過濾器
　　考慮到閃存的讀寫不

5、對稱、異地更新等特點，冷熱數據識別算法就成為提高閃存性能和降低存儲成本的關鍵因素。為了提高冷熱數據識別精度，本文設計了一種面向閃存的數據溫度感知布魯姆過濾器(DTPBF)。DTPBF將閃存中一段時間內的數據訪問記錄劃分為n個周期，通過1個CBF與n個BF組合依據Round-robin方式記錄每個周期內的數據訪問頻度。每個周期內訪問頻度用不同溫度來表示，并將每個周期的溫度通過雙射函數映射成一個溫度，該溫度就代表該數據在這段時間內的訪問特性

6、。根據DTPBF提供的數據溫度，閃存就能將具有相同訪問特性或規(guī)律的數據保存于閃存中相同物理塊上，從而降低閃存寫入放大率、提高閃存寫性能、提高閃存壽命和可靠性;DTPBF也能識別偶爾變熱的數據，提高閃存中緩沖區(qū)命中率，有效降低混合存儲模式（硬盤+閃存）中數據遷移成本，提高系統效率。理論分析和實際實驗結果表明DTPBF具有較小的內存消耗和計算復雜度低等特點。
　　(3)設計了一種面向閃存鍵值存儲的矩陣索引布魯姆過濾器
　　索引結

7、構是提高閃存鍵值存儲插入和查詢性能的關鍵技術之一。閃存鍵值存儲中直接使用傳統B+樹建立索引容易導致其父節(jié)點直至樹根節(jié)點的級聯更新，致使系統性能嚴重下降。為了解決此類問題，本文設計了一種面向閃存鍵值存儲的矩陣索引布魯姆過濾器(MIBF)。MIBF由m×s的比特位矩陣表示的多個布魯姆過濾器組(MBFG)和一個附加布魯姆過濾器(ABF)組成，其核心思想是借鑒編碼器原理，將鍵值對的閃存頁地址被拆分為多組比特，每組比特采用MBFG中的一組布魯姆過

8、濾器(BF)來表示，同時將鍵值對的key與閃存頁地址組合值存入ABF中。根據key查詢value時，MBFG中的每組BF產生多個比特值，組合生成鍵值對的閃存頁地址，并通過ABF濾掉部分偽閃存頁地址，達到較精確地址定位，降低閃存訪問次數，提高系統性能。
　　(4)設計了一種面向Hadoop-Join算法高精度計數器布魯姆過濾器
　　Key-value存儲沒有傳統數據庫中的數據關系模型，未向用戶提供類似SQL連接操作語句，應用層

9、需要編程實現多個數據集的Join操作。Hadoop-Join算法是提高大規(guī)模分布式key-value多數據集綜合統計分析效率的關鍵技術。為了克服Hadoop計算環(huán)境中沒有索引支持而帶來Join操作性能下降的問題，本文設計了一種高精度計數器布魯姆過濾器(ACBF)過濾掉不參與Join操作的數據記錄，減少通信成本，提高Hadoop-Join算法性能。ACBF主要思想是充分利用CBF的空閑空間來降低假陽性誤判概率。ACBF將CBF中計數器向量

10、劃分為由偏移索引組織的多層結構，第一層次用于執(zhí)行集合成員查詢操作，而其它層用于表示插入和刪除的計數器。本文通過優(yōu)化ACBF第一層大小來最大程度地降低ACBF假陽性誤判概率，同時保持其標準CBF功能不受影響。仿真結果表明在相同內存開銷情況下，ACBF假陽性要明顯低于CBF;基于ACBF的Hadoop-Join算法有效過濾掉Shuffle過程中冗余數據記錄，大幅度減少網絡I/O和Reduce端的無效操作，進一步提高了Hadoop-Join算

11、法性能。
　　(5)設計一種面向多維屬性數據的高精度多維計數布魯姆過濾器
　　大數據時代，數據結構復雜，元素屬性多維化。在快速變化的海量數據中通過高精度的多維屬性數據的信息表示和查詢算法迅速地完成數據的價值“提純”，成為有效進行大數據處理過程中極具挑戰(zhàn)性的問題。在分析現有針對多維屬性數據表示的布魯姆過濾器特點的基礎上，本文設計了一種基于雙射函數的高精度多維計數布魯姆過濾器(AMD-CBF)查詢算法。AMD-CBF中元素表示和