數(shù)據(jù)備份系統(tǒng)中冗余數(shù)據(jù)的高性能消除技術(shù)研究.pdf

1、隨著近些年電子信息和數(shù)據(jù)的爆炸性增長(zhǎng)，數(shù)據(jù)去重和差量壓縮作為有效檢測(cè)和消除大規(guī)模備份系統(tǒng)中冗余數(shù)據(jù)的關(guān)鍵技術(shù)，獲得了越來(lái)越多的關(guān)注。相對(duì)于傳統(tǒng)的哈弗曼編碼和字典編碼的壓縮技術(shù)而言，數(shù)據(jù)去重和差量壓縮具有更好的可擴(kuò)展性，更加適應(yīng)現(xiàn)在存儲(chǔ)系統(tǒng)規(guī)模的增長(zhǎng)，可有效地幫助存儲(chǔ)系統(tǒng)節(jié)省存儲(chǔ)空間和提高網(wǎng)絡(luò)帶寬利用率。但是數(shù)據(jù)去重和差量壓縮面對(duì)現(xiàn)在非結(jié)構(gòu)化數(shù)據(jù)的持續(xù)增長(zhǎng)，仍然面臨著諸多的問(wèn)題和挑戰(zhàn)。比如數(shù)據(jù)規(guī)模增長(zhǎng)帶來(lái)的重復(fù)數(shù)據(jù)和相似數(shù)據(jù)查找的磁盤索引

2、瓶頸問(wèn)題、數(shù)據(jù)去重和差量壓縮帶來(lái)的計(jì)算延遲與日益增長(zhǎng)的存儲(chǔ)和網(wǎng)絡(luò)帶寬的矛盾等。所以如何高效地壓縮在存儲(chǔ)系統(tǒng)中的海量數(shù)據(jù)，是現(xiàn)在數(shù)據(jù)去重和差量壓縮研究的迫切需求和研究熱點(diǎn)。
　　隨著數(shù)據(jù)去重的規(guī)模從TB向PB級(jí)擴(kuò)展，指紋的存儲(chǔ)索引管理逐步從內(nèi)存走向磁盤，這導(dǎo)致了指紋查找速度越來(lái)越慢。針對(duì)這一問(wèn)題，提出一種近乎精確的數(shù)據(jù)去重索引算法SiLo，能夠有效挖掘和利用備份數(shù)據(jù)流中的相似性和局部性來(lái)達(dá)到很高的數(shù)據(jù)去重索引性能。具體而言，SiLo

3、通過(guò)對(duì)備份數(shù)據(jù)流分成多個(gè)相似性單元并提取其相似性特征存放在內(nèi)存中建立索引，通過(guò)挖掘這種備份數(shù)據(jù)流的相似性來(lái)大大減少去重索引的內(nèi)存開(kāi)銷，通過(guò)對(duì)相似性數(shù)據(jù)的查找匹配再進(jìn)一步進(jìn)行具體的數(shù)據(jù)塊指紋匹配；另外SiLo對(duì)多個(gè)連續(xù)的相似性單元組裝成一個(gè)局部性單元，然后挖掘這種相似性單元的局部性來(lái)補(bǔ)充前面的基于相似性的重復(fù)數(shù)據(jù)檢測(cè)。實(shí)驗(yàn)測(cè)試表明：SiLo通過(guò)有效地聯(lián)合挖掘備份數(shù)據(jù)流的相似性和局部性，僅僅使用了目前主流的Extreme Binning去重

4、系統(tǒng)1/10和ChunkStash去重系統(tǒng)1/25的指紋索引內(nèi)存開(kāi)銷，同時(shí)獲得了大于99％的冗余識(shí)別率和較高的指紋索引吞吐率。
　　現(xiàn)有主流的數(shù)據(jù)去重技術(shù)采用了基于Rabin的分塊算法、基于SHA-1的指紋算法，這使得數(shù)據(jù)去重技術(shù)在壓縮存儲(chǔ)空間的同時(shí)，不可避免地帶來(lái)了計(jì)算開(kāi)銷和時(shí)延。針對(duì)這個(gè)問(wèn)題，提出一套加速數(shù)據(jù)去重的流水線和并行計(jì)算的解決方案P-Dedupe，來(lái)降低數(shù)據(jù)去重中的計(jì)算延遲。P-Dedupe通過(guò)有效利用現(xiàn)在多核計(jì)算機(jī)

5、系統(tǒng)的閑置計(jì)算資源，流水化數(shù)據(jù)去重的功能任務(wù)（即數(shù)據(jù)分塊、指紋計(jì)算、指紋索引以及存儲(chǔ)管理），并且集中并行化計(jì)算密集型的功能單元（即數(shù)據(jù)分塊和指紋計(jì)算），最終達(dá)到降低計(jì)算時(shí)延的效果。其流水線去重子任務(wù)和并行哈希計(jì)算的理念符合多核和眾核處理器行業(yè)的發(fā)展趨勢(shì)。實(shí)驗(yàn)測(cè)試表明：P-Dedupe通過(guò)有效地并行數(shù)據(jù)去重任務(wù)和哈希計(jì)算，獲得了2～4倍的數(shù)據(jù)去重系統(tǒng)吞吐率的提升。
　　如何在數(shù)據(jù)去重系統(tǒng)中最大化地、高效率地檢測(cè)和消除冗余數(shù)據(jù)，一直是

6、數(shù)據(jù)去重研究的熱點(diǎn)之一。針對(duì)這一問(wèn)題，提出一種數(shù)據(jù)去重感知的相似數(shù)據(jù)檢測(cè)和差量壓縮算法DARE，利用現(xiàn)有的數(shù)據(jù)去重系統(tǒng)中的冗余數(shù)據(jù)信息來(lái)檢測(cè)非重復(fù)但是相似的數(shù)據(jù)并進(jìn)行差量壓縮，進(jìn)一步檢測(cè)并且消除數(shù)據(jù)去重系統(tǒng)中的數(shù)據(jù)冗余，同時(shí)有效地減少在相似數(shù)據(jù)檢測(cè)的計(jì)算和索引開(kāi)銷。具體而言，DARE首先利用重復(fù)數(shù)據(jù)的局部性來(lái)查找相似數(shù)據(jù)，即嘗試對(duì)兩個(gè)重復(fù)數(shù)據(jù)相鄰的非重復(fù)數(shù)據(jù)塊進(jìn)行差量壓縮從而判定其是否相似，然后對(duì)剩下的非重復(fù)非相似數(shù)據(jù)來(lái)計(jì)算超級(jí)特征值從

7、而進(jìn)一步補(bǔ)充查找相似數(shù)據(jù)并且進(jìn)行差量壓縮。實(shí)驗(yàn)數(shù)據(jù)表明：DARE僅僅使用了傳統(tǒng)的超級(jí)特征值方法的1/4的計(jì)算開(kāi)銷和1/2的索引開(kāi)銷，而且多檢測(cè)到了2～10％的冗余數(shù)據(jù)并獲得了更高的系統(tǒng)吞吐率。
　　差量壓縮是一項(xiàng)有效消除相似文件和相似數(shù)據(jù)塊中的冗余數(shù)據(jù)的經(jīng)典壓縮技術(shù)，但差量編碼速率慢成為其應(yīng)用和推廣的潛在瓶頸。針對(duì)這一問(wèn)題，提出一種新穎的基于數(shù)據(jù)去重啟發(fā)的差量編碼算法Ddelta，通過(guò)有效地結(jié)合數(shù)據(jù)去重技術(shù)中的基于內(nèi)容分塊算法來(lái)簡(jiǎn)

8、化和加速相似數(shù)據(jù)的差量計(jì)算（即重復(fù)內(nèi)容匹配）。Ddelta的具體內(nèi)容包括：提出一種基于Gear哈希的分塊算法并與基于Spooky哈希的指紋算法結(jié)合，加速了差量計(jì)算過(guò)程中的重復(fù)字符串查找的過(guò)程；針對(duì)基于內(nèi)容分塊算法導(dǎo)致的數(shù)據(jù)壓縮率下降的問(wèn)題，挖掘冗余數(shù)據(jù)的局部性，即在重復(fù)數(shù)據(jù)相鄰區(qū)域貪心檢測(cè)出更多重復(fù)的字節(jié)內(nèi)容，從而保證了Ddelta差量壓縮的效果。實(shí)驗(yàn)測(cè)試顯示：相比較于傳統(tǒng)的差量壓縮算法Xdelta和Zdelta，Ddelta獲得了2.