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

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

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

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

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

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

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

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

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