云備份系統(tǒng)中閃存輔助分段式布隆過濾器的研究.pdf

1、為了能夠在網(wǎng)絡(luò)帶寬較低或中等的區(qū)域?qū)崿F(xiàn)云備份應用,網(wǎng)絡(luò)上傳輸?shù)臄?shù)據(jù)量應越低越好,通過對備份數(shù)據(jù)使用重復數(shù)據(jù)刪除技術(shù),能夠顯著降低網(wǎng)絡(luò)傳輸數(shù)據(jù)量。重復數(shù)據(jù)刪除的方法很多,其中一個解決方案是將文件切分成比較小的片段,這需要使用到大布隆過濾器。在空間/時間效率方面,布隆過濾器相比其他數(shù)據(jù)結(jié)構(gòu)具有明顯的優(yōu)勢。但布隆過濾器在哈希函數(shù)個數(shù)增加或者它裝載的元素個數(shù)增加時,誤判率會有升高的趨勢。由于云備份系統(tǒng)重復數(shù)據(jù)刪除將產(chǎn)生大量指紋,若布隆過濾器的長

2、度較小則會產(chǎn)生較高的誤判率,長度增大則會增加內(nèi)存消耗。
　　針對如何降低內(nèi)存消耗,提高重復數(shù)據(jù)刪除的整體性能,本文提出了一種閃存輔助分段式的布隆過濾器(FASBF)方法,即在大規(guī)模云備份系統(tǒng)中將布隆過濾器部署在SSD上。由于SSD沒有機械磁頭,因此其讀速度很快;而分段式的布隆過濾器則可以方便劃分存儲空間。在本文的方法中,布隆過濾器全部保存在SSD中,只有部分保存在RAM中。保存在RAM中的部分布隆過濾器的大小決定了整個應用的RAM

3、空間消耗。當部分分段式布隆過濾器陣列(PSBFA)大小占整個分段式布隆過濾器陣列(FSBFA)大小的一半時,應用的內(nèi)存消耗就減少為原來的一半。本文使用三種方法優(yōu)化了重復數(shù)據(jù)刪除的數(shù)據(jù)檢索過程:首先布隆過濾器的長度可以充分大,其次可以使用更多的哈希函數(shù)來減少誤判率,最后由于布隆過濾器占用的內(nèi)存空間減少,內(nèi)存中可以緩存更多的指紋,這將極大地減少由誤判率導致的磁盤I/O開銷。為了最大化利用SSD,文件和數(shù)據(jù)塊的指紋哈希桶(在初始狀態(tài)時)部分被