面向大數(shù)據(jù)的高效布魯姆過濾器研究與應(yīng)用.pdf

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

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

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

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

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

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

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

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

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

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

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