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

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

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

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

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

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

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

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

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

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

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

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