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

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

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

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

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

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

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

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

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