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

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

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

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