高性能重復(fù)數(shù)據(jù)檢測與刪除技術(shù)研究.pdf

1、信息技術(shù)的不斷突破和發(fā)展推動全球進(jìn)入大數(shù)據(jù)時代。近年來,數(shù)據(jù)去重作為提高硬盤存儲系統(tǒng)空間效率和降低數(shù)據(jù)維護(hù)成本的關(guān)鍵技術(shù)成為存儲學(xué)術(shù)界和工業(yè)界的研究熱點。數(shù)據(jù)去重是在數(shù)據(jù)集或數(shù)據(jù)流中發(fā)現(xiàn)和消除重復(fù)內(nèi)容以提高數(shù)據(jù)的存儲和/或傳輸效率的過程。一般來說,發(fā)現(xiàn)和消除重復(fù)數(shù)據(jù)的粒度可以是文件、字節(jié)串、定長分塊或變長分塊。研究如何高效地界定、檢測和刪除重復(fù)數(shù)據(jù)對構(gòu)建高性能去重存儲系統(tǒng)十分重要。
　　可變長度分塊技術(shù)能夠有效偵測到相似文件之間的

2、重復(fù)內(nèi)容,文件級去重技術(shù)則能夠在更大粒度上發(fā)現(xiàn)和消除重復(fù)內(nèi)容,從而降低塊級去重的計算和查找復(fù)雜度。針對當(dāng)前同時在文件級和變長塊級消除冗余的數(shù)據(jù)去重方法,提出基于多核并行的流水化的兩級指紋計算方法PDF。通過分解指紋計算的主要任務(wù),PDF使用多個數(shù)據(jù)緩存消除計算任務(wù)間的數(shù)據(jù)依賴和緩存競爭,并采用流水調(diào)度方式將各計算任務(wù)部署到不同的處理器核,從而實現(xiàn)在單次內(nèi)容掃描中同時生成數(shù)據(jù)的文件級和塊級指紋。實驗結(jié)果表明,PDF可達(dá)到比傳統(tǒng)多線程方法更

3、高的指紋計算性能。
　　基于滑動窗口模型的重復(fù)元素檢測是統(tǒng)計和分析流式數(shù)據(jù)的重要技術(shù)手段,緩存滑動窗口內(nèi)動態(tài)更新的元素序列需要消耗大量內(nèi)存且具有較高的重復(fù)元素查詢復(fù)雜度?，F(xiàn)有支持重復(fù)元素檢測的快速索引方法存在內(nèi)存效率低和不可擴(kuò)展等問題,因此提出可在滑動窗口模型下對流式數(shù)據(jù)進(jìn)行重復(fù)元素快速檢測的分離計數(shù)型布隆過濾器陣列(Detached Counting Bloom filter Array,DCBA)。DCBA由一組同構(gòu)的分離計數(shù)

4、型布隆過濾器(Detached Counting Bloom Filter,DCBF)構(gòu)成,其中的布隆過濾器用于描述滑動窗口內(nèi)元素的成員資格,而計數(shù)器組(計時器組)用于記錄元素的時間戳。DCBA以循環(huán)先入先出隊列的方式工作,位于隊尾的DCBF處于填充狀態(tài)以容納新元素,位于隊首的DCBF處于衰減狀態(tài)以淘汰舊元素,中間滿載的DCBF相對穩(wěn)定且其計時器組可被轉(zhuǎn)儲到硬盤以節(jié)約內(nèi)存資源。DCBA的大部分DCBF組件都具有穩(wěn)定性,因此其可被高效同步

5、到多個節(jié)點用于共享信息或增強(qiáng)可靠性,也可進(jìn)一步將其擴(kuò)展部署到多個節(jié)點以在分析大數(shù)據(jù)流時描述超大容量滑動窗口。數(shù)學(xué)分析和實驗數(shù)據(jù)表明,DCBA的內(nèi)存空間效率和可擴(kuò)展性明顯優(yōu)于已有解決方案。
　　存儲系統(tǒng)中的數(shù)據(jù)集通常具有較強(qiáng)的可擴(kuò)展性,采用固定容量的快速索引方法描述可擴(kuò)展數(shù)據(jù)集合有兩個明顯缺點。首先,若集合元素的實際數(shù)量超過索引的設(shè)計容量,則需要較大的時間和空間開銷重建整個索引;其次,若集合基數(shù)需要很長的時間才能增長到索引的設(shè)計容量

6、,則索引機(jī)制需要長期占據(jù)不必要的內(nèi)存資源,降低了內(nèi)存空間利用率。因此,提出動態(tài)布隆過濾器陣列(Dynamic Bloom filter Array,DBA)用于描述存儲系統(tǒng)中的可擴(kuò)展數(shù)據(jù)集并支持重復(fù)元素快速檢測。DBA以布隆過濾器為基本組件,具有較高的內(nèi)存空間效率,其可根據(jù)數(shù)據(jù)集合規(guī)模的增長按需創(chuàng)建新的布隆過濾器以擴(kuò)展索引容量。DBA采用優(yōu)化的內(nèi)存數(shù)據(jù)結(jié)構(gòu)以增強(qiáng)索引單元的訪問并行度和提高查詢效率。通過局部調(diào)整布隆過濾器成員的設(shè)計容量或誤

7、判率閾值,DBA可有效控制整體查詢準(zhǔn)確度。如果將集合劃分為不相交的子集并分別采用不同的布隆過濾器作為索引,則DBA可根據(jù)查詢結(jié)果直接定位疑似重復(fù)元素所對應(yīng)的子集。針對去重存儲系統(tǒng)批量回收空間的特點,DBA采用懶惰更新策略支持元素刪除。
　　構(gòu)建可擴(kuò)展的高性能去重存儲系統(tǒng)面臨兩大挑戰(zhàn)。首先,大數(shù)據(jù)集的全量索引可能溢出可用內(nèi)存空間,從而導(dǎo)致查找重復(fù)數(shù)據(jù)對象時的硬盤訪問瓶頸。其次,去重存儲系統(tǒng)擴(kuò)展到多個節(jié)點時必須有效消除節(jié)點間的重復(fù)內(nèi)容

8、,以免形成孤島效應(yīng)。已有去重方法在部分或同時解決上述問題時無法完全消除存儲系統(tǒng)中的重復(fù)數(shù)據(jù),因此提出面向備份存儲系統(tǒng)的可擴(kuò)展的高性能精確去重方法 MAD2以同時在文件級和塊級檢測和消除重復(fù)數(shù)據(jù)。MAD2采用四種技術(shù)提高去重性能和實現(xiàn)可擴(kuò)展性。首先,MAD2創(chuàng)建哈希桶矩陣(HBM)作為存儲數(shù)據(jù)指紋的全量索引,HBM的各行可用于保存指紋序列的局部性。其次,MAD2采用動態(tài)布隆過濾器陣列(DBA)作為常駐內(nèi)存的快速索引,用以加速重復(fù)指紋的檢測