基于雙布魯姆過濾器的數(shù)據(jù)排重算法及其應(yīng)用.pdf

1、隨著近年來數(shù)據(jù)總量呈現(xiàn)出的爆炸增長(zhǎng)趨勢(shì)，數(shù)據(jù)備份系統(tǒng)存儲(chǔ)的數(shù)據(jù)越來越多。經(jīng)研究發(fā)現(xiàn)，在備份、歸檔等集中存儲(chǔ)系統(tǒng)中存在大量冗余數(shù)據(jù)，有的甚至占到存儲(chǔ)空間的60％，導(dǎo)致存儲(chǔ)成本過高，數(shù)據(jù)訪問性能下降。數(shù)據(jù)排重是減少數(shù)據(jù)冗余、節(jié)省存儲(chǔ)空間的有效手段?，F(xiàn)有排重算法中，文件級(jí)排重盡管排重開銷小，但排重粒度過粗，難以取得存儲(chǔ)空間的高效利用;數(shù)據(jù)塊級(jí)排重算法能實(shí)現(xiàn)高效存儲(chǔ)，但其附帶的存儲(chǔ)開銷過高，排重的時(shí)間開銷大。本文研究分層排重結(jié)構(gòu)，應(yīng)用雙布魯姆過

2、濾器實(shí)現(xiàn)數(shù)據(jù)排重，優(yōu)化數(shù)據(jù)排重性能，主要工作如下:
　　 1.針對(duì)數(shù)據(jù)重復(fù)有文件級(jí)的重復(fù)和數(shù)據(jù)塊級(jí)的重復(fù)之分，提出一種基于雙布魯姆過濾器的數(shù)據(jù)排重算法。該算法使用兩個(gè)布魯姆過濾器構(gòu)成二級(jí)排重結(jié)構(gòu)，將排重過程分解成文件排重和數(shù)據(jù)塊排重兩部分。算法首先進(jìn)入第一級(jí)進(jìn)行文件排重，然后將第一級(jí)排重判定為不重復(fù)的文件分割成塊進(jìn)行第二級(jí)數(shù)據(jù)塊排重。利用這種分層排重結(jié)構(gòu)，通過第一級(jí)將重復(fù)文件直接過濾掉，不進(jìn)入第二級(jí)排重，減少了數(shù)據(jù)塊排重的工作量

3、;通過第二級(jí)進(jìn)入不重復(fù)文件內(nèi)部進(jìn)行數(shù)據(jù)塊排重，獲得了數(shù)據(jù)塊級(jí)的排重粒度。
　　 2.本文將上述算法應(yīng)用于文檔備份系統(tǒng)中，實(shí)現(xiàn)對(duì)文檔的排重，由于算法采用布魯姆過濾器對(duì)數(shù)據(jù)進(jìn)行壓縮表達(dá)，存在誤判可能，即假陽性誤判問題。本文設(shè)計(jì)通過查詢?cè)獢?shù)據(jù)（保存數(shù)據(jù)相關(guān)信息）來為誤判糾錯(cuò)。當(dāng)布魯姆過濾器判斷數(shù)據(jù)為重復(fù)時(shí)，首先將元數(shù)據(jù)預(yù)讀到內(nèi)存中，在內(nèi)存中匹配元數(shù)據(jù)信息，若沒有找到，再讀取保存元數(shù)據(jù)的文件—索引文件查詢?cè)獢?shù)據(jù)。通過內(nèi)存、索引文件兩級(jí)元

4、數(shù)據(jù)查詢，杜絕了假陽性誤判的情況。
　　 3.由于為假陽性誤判糾錯(cuò)需要對(duì)元數(shù)據(jù)進(jìn)行大量訪問，增加了排重時(shí)間開銷，本文設(shè)計(jì)將索引文件緩存，保證元數(shù)據(jù)操作的高效，以此提高排重效率。但系統(tǒng)的句柄數(shù)限制了同時(shí)緩存的索引文件數(shù)目，若索引文件過多，則不能同時(shí)緩存全部索引文件，需要進(jìn)行更多的磁盤IO，此時(shí)排重開銷與耗時(shí)都急劇升高，針對(duì)這種情況，采用動(dòng)態(tài)哈希算法來分配元數(shù)據(jù)地址，將元數(shù)據(jù)保存在少數(shù)幾個(gè)索引文件內(nèi)，從而克服了句柄限制問題。