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

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

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

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

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

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

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

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

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