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

1、信息技術(shù)的不斷突破和發(fā)展推動(dòng)全球進(jìn)入大數(shù)據(jù)時(shí)代。近年來(lái),數(shù)據(jù)去重作為提高硬盤(pán)存儲(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ǔ)和/或傳輸效率的過(guò)程。一般來(lái)說(shuō),發(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。通過(guò)分解指紋計(jì)算的主要任務(wù),PDF使用多個(gè)數(shù)據(jù)緩存消除計(jì)算任務(wù)間的數(shù)據(jù)依賴(lài)和緩存競(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ò)展等問(wèn)題,因此提出可在滑動(dòng)窗口模型下對(duì)流式數(shù)據(jù)進(jìn)行重復(fù)元素快速檢測(cè)的分離計(jì)數(shù)型布隆過(guò)濾器陣列(Detached Counting Bloom filter Array,DCBA)。DCBA由一組同構(gòu)的分離計(jì)數(shù)

4、型布隆過(guò)濾器(Detached Counting Bloom Filter,DCBF)構(gòu)成,其中的布隆過(guò)濾器用于描述滑動(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ǔ)到硬盤(pán)以節(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ù)量超過(guò)索引的設(shè)計(jì)容量,則需要較大的時(shí)間和空間開(kāi)銷(xiāo)重建整個(gè)索引;其次,若集合基數(shù)需要很長(zhǎng)的時(shí)間才能增長(zhǎng)到索引的設(shè)計(jì)容量

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

7、判率閾值,DBA可有效控制整體查詢準(zhǔn)確度。如果將集合劃分為不相交的子集并分別采用不同的布隆過(guò)濾器作為索引,則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í)的硬盤(pán)訪問(wèn)瓶頸。其次,去重存儲(chǔ)系統(tǒng)擴(kuò)展到多個(gè)節(jié)點(diǎn)時(shí)必須有效消除節(jié)點(diǎn)間的重復(fù)內(nèi)容

8、,以免形成孤島效應(yīng)。已有去重方法在部分或同時(shí)解決上述問(wèn)題時(shí)無(wú)法完全消除存儲(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)布隆過(guò)濾器陣列(DBA)作為常駐內(nèi)存的快速索引,用以加速重復(fù)指紋的檢測(cè)