重復(fù)數(shù)據(jù)刪除中的可變分塊算法【畢業(yè)論文+文獻(xiàn)綜述+開題報(bào)告+任務(wù)書】

1、<p>　　本科畢業(yè)設(shè)計(jì)(論文)</p><p><b>　　( 屆)</b></p><p>　　論文題目重復(fù)數(shù)據(jù)刪除中的可變分塊算法</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級 信息管理與信息系統(tǒng) </p

2、><p>　　學(xué)生姓名 學(xué)號 </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 日</p><p>　　重復(fù)數(shù)據(jù)刪除中的可變分塊算法</p><p>　　摘要：重復(fù)數(shù)

3、據(jù)刪除技術(shù)對縮減數(shù)據(jù)占用空間、提高存儲設(shè)備利用率、削減存儲成本、減輕網(wǎng)絡(luò)負(fù)載有十分重要的意義。本文針對這種現(xiàn)狀，分析了現(xiàn)在重復(fù)數(shù)據(jù)刪除技術(shù)的現(xiàn)狀，并著重分析了可變分塊算法。</p><p>　　本次畢業(yè)設(shè)計(jì)主要通過對可變分塊的重復(fù)數(shù)據(jù)刪除技術(shù)的基本定義、算法思想、應(yīng)用情況進(jìn)行研究，了解了現(xiàn)今數(shù)據(jù)存儲方面的現(xiàn)狀，同時(shí)了解了當(dāng)今重復(fù)數(shù)據(jù)刪除技術(shù)的主流方法和主要的優(yōu)缺點(diǎn)，分析得出了重復(fù)數(shù)據(jù)刪除技術(shù)在實(shí)際應(yīng)用方面的意義和

4、一些不足。</p><p>　　關(guān)鍵詞： 重復(fù)數(shù)據(jù)刪除；可變分塊；應(yīng)用</p><p>　　Variable-length Block Algorithm of Data De-duplication</p><p>　　Abstract: Data de-duplication technology is very important to reduce the

5、data footprint, improve the storage utilization, reduce storage costs and reduce the network load. This paper analyses the current status of the data de-duplication technology under the current situation and analyses the

6、 variable-length block algorithm.</p><p>　　The graduation design mainly through variable partition repeating data deleted the basic definition, algorithm technical ideas, application and study, understand th

7、e now data storage the status, and understand the current repeating data deleted the mainstream method and main technical advantages and disadvantages of repetition and analysis in practical application data deleted tech

8、nology of meaning and some shortage. </p><p>　　Key words: Data De-duplication; Variable block; Application</p><p><b>　　目錄</b></p><p>　　1 引言- 1 -</p><p>　　1

9、.1重復(fù)數(shù)據(jù)刪除技術(shù)的背景和意義- 1 -</p><p>　　1.2重復(fù)數(shù)據(jù)刪除的定義、分類- 1 -</p><p>　　1.3重復(fù)數(shù)據(jù)刪除技術(shù)的國內(nèi)外現(xiàn)狀- 2 -</p><p>　　1.3.1國外現(xiàn)狀- 2 -</p><p>　　1.3.2國內(nèi)狀況- 3 -</p><p>　　1.4主要任務(wù)和目

10、標(biāo)- 3 -</p><p>　　1.5全篇論文的主要內(nèi)容- 3 -</p><p>　　2 重復(fù)數(shù)據(jù)刪除技術(shù)- 4 -</p><p>　　2.1重復(fù)數(shù)據(jù)刪除的流程- 4 -</p><p>　　2.2檢測技術(shù)- 4 -</p><p>　　2.2.1相同文件檢測技術(shù)- 4 -</p>&l

11、t;p>　　2.2.2基于內(nèi)容算法的檢測技術(shù)- 5 -</p><p>　　2.2.3定長塊的切分- 5 -</p><p>　　2.2.4變長塊的切分- 6 -</p><p>　　2.2.5滑動塊檢測技術(shù)- 6 -</p><p>　　2.3對于數(shù)據(jù)塊進(jìn)行Hash值計(jì)算- 7 -</p><p>　

12、　2.4消除重復(fù)- 8 -</p><p>　　3 重復(fù)數(shù)據(jù)刪除中的可變分塊算法- 8 -</p><p>　　3.1文件分塊和記錄指紋- 8 -</p><p>　　3.2 計(jì)算數(shù)據(jù)塊Hash值- 9 -</p><p>　　3.3重復(fù)數(shù)據(jù)比較- 10 -</p><p>　　3.4數(shù)據(jù)存儲- 11 -&

13、lt;/p><p>　　3.5 新文件的指紋以及已分?jǐn)?shù)據(jù)塊Hash值的保存- 11 -</p><p>　　4 重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用- 12 -</p><p>　　4.1重復(fù)數(shù)據(jù)刪除的主要應(yīng)用特點(diǎn)- 12 -</p><p>　　4.1.1數(shù)據(jù)備份系統(tǒng)- 12 -</p><p>　　4.1.2歸檔存儲系統(tǒng)-

14、 13 -</p><p>　　4.1.3遠(yuǎn)程災(zāi)備系統(tǒng)- 13 -</p><p>　　4.2重復(fù)數(shù)據(jù)刪除技術(shù)的實(shí)踐例證- 13 -</p><p>　　4.3刪除備份數(shù)據(jù)重復(fù)部分- 14 -</p><p>　　4.4不能脫離存儲系統(tǒng)單獨(dú)使用- 14 -</p><p>　　4.5重復(fù)數(shù)據(jù)刪除技術(shù)的主要不足

15、- 14 -</p><p>　　5 總結(jié)與展望- 15 -</p><p>　　致 謝- 16 -</p><p>　　參考文獻(xiàn)- 16 -</p><p><b>　　1 引言</b></p><p>　　1.1 重復(fù)數(shù)據(jù)刪除技術(shù)的背景和意義</p><p>

16、;　　隨著數(shù)字圖書館、電子商務(wù)、科學(xué)計(jì)算、多媒體等應(yīng)用的不斷發(fā)展，數(shù)據(jù)從萬億字節(jié)(TB)急速增長到千萬億字節(jié)(PB)，甚至到一百億億字節(jié)(EB)。據(jù)IDC(國際數(shù)據(jù)公司)統(tǒng)計(jì)顯示，去年全球產(chǎn)生的數(shù)字信息量共計(jì)161 EB字節(jié)，世界上有足夠存儲185 EB字節(jié)的存儲設(shè)備，到2010年，世界上將有能夠存儲601 EB字節(jié)的設(shè)備。然而到2010年，全球所產(chǎn)生的數(shù)碼信息量將由現(xiàn)在的161 EB字節(jié)猛增到988 EB字節(jié)[1]。</p>

17、;<p>　　由于信息的海量增長，磁盤備份設(shè)備的容量已經(jīng)趨于飽和，在數(shù)據(jù)中心需要不停地增加硬盤來備份PB級別的數(shù)據(jù)，在這種情況下，在我們希望將備份數(shù)據(jù)保存一個(gè)月時(shí)，卻只能保存兩到三天，硬盤里的數(shù)據(jù)開始變得臃腫和龐大。當(dāng)對這些數(shù)據(jù)進(jìn)行仔細(xì)分析時(shí)，卻不難發(fā)現(xiàn)其中有太多的重復(fù)數(shù)據(jù)，因此重復(fù)數(shù)據(jù)刪除技術(shù)開始受到工業(yè)與學(xué)術(shù)界的關(guān)注[2]。</p><p>　　為了緩解存儲系統(tǒng)的空間增長問題、縮減數(shù)據(jù)占用空間、

18、降低成本、最大程度的利用已有資源，我們需要對重復(fù)數(shù)據(jù)刪除技術(shù)進(jìn)行研究。</p><p>　　一方面，利用重復(fù)數(shù)據(jù)刪除技術(shù)，可以對存儲空間的利用率進(jìn)行優(yōu)化。因傳統(tǒng)的數(shù)據(jù)壓縮技術(shù)主要根據(jù)一些固定的模式利用傳統(tǒng)的數(shù)據(jù)分析工具和技術(shù)來消除重復(fù)數(shù)據(jù)，不能有效地改善基于磁盤數(shù)據(jù)的成本效益[3]，所以我們需要通過探究重復(fù)數(shù)據(jù)的特性，利用相應(yīng)的重復(fù)數(shù)據(jù)刪除技術(shù)，以消除分布在存儲系統(tǒng)中的相同文件或者數(shù)據(jù)塊。</p>

19、<p>　　另一方面，利用重復(fù)數(shù)據(jù)刪除技術(shù)，可以減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，進(jìn)而降低能量消耗和網(wǎng)絡(luò)成本。由于重復(fù)數(shù)據(jù)刪除技術(shù)的目標(biāo)是消除分布在存儲系統(tǒng)中的相同及相似文件或者數(shù)據(jù)塊，因此能夠減少大量的磁盤消耗，并且為數(shù)據(jù)復(fù)制大大節(jié)省網(wǎng)絡(luò)帶寬。</p><p>　　1.2 重復(fù)數(shù)據(jù)刪除的定義、分類</p><p>　　一種數(shù)據(jù)縮減技術(shù)，通常用于基于磁盤的備份系統(tǒng)，旨在減少存儲系統(tǒng)中使

20、用的存儲容量,它的工作方式是在某個(gè)時(shí)間周期內(nèi)查找不同文件中不同位置的重復(fù)可變大小數(shù)據(jù)塊,這就是重復(fù)數(shù)據(jù)刪除技術(shù)的定義。重復(fù)數(shù)據(jù)刪除技術(shù)的宗旨就是為企業(yè)用戶提供重復(fù)數(shù)據(jù)的備份解決方案，增加有效存儲空間，提高存儲效率，使企業(yè)備份解決方案更加完善、高效。按照部署位置的不同，重復(fù)數(shù)據(jù)刪除可分為源端重復(fù)數(shù)據(jù)刪除和目標(biāo)端重復(fù)數(shù)據(jù)刪除。源端重復(fù)數(shù)據(jù)刪除是先刪除重復(fù)數(shù)據(jù)，再將數(shù)據(jù)傳到備份設(shè)備。目標(biāo)端重復(fù)數(shù)據(jù)刪除是先將數(shù)據(jù)傳到備份設(shè)備，存儲時(shí)再刪除重復(fù)數(shù)

21、據(jù)。按照檢查重復(fù)數(shù)據(jù)的算法不同，重復(fù)數(shù)據(jù)刪除可以分為對象/文件級和塊級的重復(fù)數(shù)據(jù)刪除。對象級的重復(fù)數(shù)據(jù)刪除保證文件不重復(fù)。塊級重復(fù)數(shù)據(jù)刪除則將文件分成數(shù)據(jù)塊進(jìn)行比較。根據(jù)切分?jǐn)?shù)據(jù)塊方法的不同，又可分為定長塊和變長塊的重復(fù)數(shù)據(jù)刪除技術(shù)。變長塊的重復(fù)數(shù)據(jù)刪除，數(shù)據(jù)塊的長度是變動的。定長塊的重復(fù)數(shù)據(jù)刪除，數(shù)據(jù)塊的長度是固定的。根據(jù)應(yīng)用場合的不同，可以分為通用型重復(fù)數(shù)據(jù)刪除系統(tǒng)和專用型重復(fù)數(shù)據(jù)刪除系統(tǒng)。通用型重復(fù)數(shù)據(jù)刪除系統(tǒng)是指廠商提供通用的重

22、復(fù)數(shù)據(jù)刪除產(chǎn)品，而不是和特定虛擬磁帶庫或備份設(shè)備相聯(lián)系</p><p>　　根據(jù)目前的研究現(xiàn)狀，我們可以分析得出，隨著重復(fù)數(shù)據(jù)刪除技術(shù)的研究與應(yīng)用，其理論將得到不斷地發(fā)展和完善，人們對重復(fù)數(shù)據(jù)刪除的認(rèn)識也會越來越清晰。但是，如何充分挖掘數(shù)據(jù)的內(nèi)在特性，將其應(yīng)用到已有的技術(shù)中，發(fā)揮各技術(shù)的優(yōu)勢，將是一個(gè)可深入探究的領(lǐng)域；從重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性研究角度，如何在吸收現(xiàn)有成果的同時(shí)，引入其他機(jī)制打破現(xiàn)有技術(shù)的局限性是

23、一個(gè)需要更深入研究的區(qū)域；從重復(fù)數(shù)據(jù)刪除技術(shù)的性能研究角度，如何融合各種現(xiàn)有技術(shù)，同時(shí)提供通用性、可擴(kuò)展性和自適應(yīng)性也是一個(gè)需要更深入研究的方面。</p><p>　　1.3 重復(fù)數(shù)據(jù)刪除技術(shù)的國內(nèi)外現(xiàn)狀</p><p>　　1.3.1 國外現(xiàn)狀</p><p>　　重復(fù)數(shù)據(jù)刪除作為一種文件間的無損壓縮技術(shù)，在數(shù)據(jù)備份領(lǐng)域，特別是數(shù)據(jù)災(zāi)難備份領(lǐng)域得到廣泛的運(yùn)用，

24、因?yàn)榭梢钥缥募嚎s，并且能達(dá)到較高的壓縮比，因此國外諸多的研究機(jī)構(gòu)都對它做了較為深入的研究，而且設(shè)計(jì)開發(fā)了較為成熟的系統(tǒng)，比如Rsync和LBFS等。</p><p>　　1.3.1.1 Rsync系統(tǒng)</p><p>　　Rsync[5]算法由A. Tridgell于1999年在他的博士論文中提出,它通過檢測、傳輸新舊文件的差異部分,可以實(shí)現(xiàn)快速、高效的文件同步。</p>

25、<p>　　Rsync算法也有一定的缺陷:首先, Rsync使用固定分塊的方法，這種分塊方法對數(shù)據(jù)變化非常敏感，因?yàn)楫?dāng)文件內(nèi)部數(shù)據(jù)有部分變化時(shí)，緊接著的一系列文件塊會跟著相應(yīng)地改變。其次，其中對于數(shù)據(jù)相似性檢測的方法與文件目錄結(jié)構(gòu)有關(guān)，所以倘若目錄結(jié)構(gòu)有所改變，但相應(yīng)文件內(nèi)容未做修改，其也會當(dāng)作新文件處理，產(chǎn)生多余的網(wǎng)絡(luò)流量。</p><p>　　1.3.1.2 LBFS系統(tǒng)</p>

26、<p>　　LBFS[6]是麻省理工學(xué)院于2001年由Athicha Muthitacharoen, Benjie Chen等人開發(fā)的一款文件系統(tǒng)，該系統(tǒng)使用Rabin fingerprint算法來實(shí)現(xiàn)變長分塊，該方法對文件數(shù)據(jù)變化不敏感，是一種基于內(nèi)容的分塊方法，同時(shí)使用SHA-1（安全散列算法）值作為指示符，向服務(wù)器進(jìn)行塊存儲校驗(yàn)，以判斷數(shù)據(jù)塊是否已存儲，若已存在則不用發(fā)送數(shù)據(jù)塊，以此達(dá)到了減小傳輸帶寬的目的。</p

27、><p>　　該系統(tǒng)作為一款文件系統(tǒng)提出，但是其中使用到了文件分塊處理，以及文件塊單一實(shí)例化存儲的思想，使得該系統(tǒng)在重復(fù)數(shù)據(jù)刪除技術(shù)中一直被作為經(jīng)典系統(tǒng)進(jìn)行引用研究。</p><p>　　1.3.2 國內(nèi)狀況</p><p>　　國內(nèi)有清華大學(xué)網(wǎng)絡(luò)存儲實(shí)驗(yàn)室和華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院兩家科研機(jī)構(gòu)對重復(fù)數(shù)據(jù)刪除領(lǐng)域進(jìn)行了深入的研究，并分別開發(fā)了ADMAD和FBB

28、M系統(tǒng)。</p><p>　　1.3.2.1 ADMAD系統(tǒng)</p><p>　　清華大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)存儲實(shí)驗(yàn)室與明尼蘇達(dá)大學(xué)共同合作開發(fā)了ADMAD[7]歸檔備份系統(tǒng)，使用不同等級I/O通道的元數(shù)據(jù)信息把文件分成有一定意義的文件塊，以此來削減文件間的重復(fù)數(shù)據(jù)，該系統(tǒng)同樣使用變長分塊的方式。</p><p>　　1.3.2.2 FBBM系統(tǒng)</p>

29、<p>　　FBBM[8]系統(tǒng)由華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院開發(fā)的一款文件備份系統(tǒng)，它把文件使用變長分塊算法，分成多個(gè)數(shù)據(jù)塊，然后使用描點(diǎn)分級的策略進(jìn)行重復(fù)數(shù)據(jù)塊的發(fā)現(xiàn)檢測，同時(shí)根據(jù)文件塊內(nèi)容建立一個(gè)哈希表，以此來實(shí)現(xiàn)文件塊存儲的唯一性，然后把唯一的數(shù)據(jù)塊存入一次性寫入的RAID設(shè)備中。</p><p>　　1.4 主要任務(wù)和目標(biāo)</p><p>　　為了緩解存儲系統(tǒng)的空

30、間增長問題、縮減數(shù)據(jù)占用空間、降低成本、最大程度的利用已有資源，我們需要對重復(fù)數(shù)據(jù)刪除技術(shù)進(jìn)行研究。重復(fù)數(shù)據(jù)刪除技術(shù)可以有效提高存儲設(shè)備的利用率，減少存儲容量。同時(shí)在重復(fù)數(shù)據(jù)刪除技術(shù)中存在一種可變分塊算法，這種算法允許某些數(shù)據(jù)片段進(jìn)行伸縮，而不影響后面的數(shù)據(jù)塊，有助于提高系統(tǒng)查找重復(fù)數(shù)據(jù)塊的能力，從而達(dá)到大幅節(jié)省空間的目的。同時(shí)這種算法對于數(shù)據(jù)的敏感性不高，所以對于數(shù)據(jù)的一些小的改變不會引起數(shù)據(jù)的大規(guī)模的改變。例如該算法對于插入問題和刪

31、除問題處理高效。無論是插入還是刪除一小部分字節(jié)，只會影響一到兩個(gè)塊，其余的塊保持不變。這種算法對于數(shù)據(jù)的重復(fù)冗余有著更多的清理和檢測。</p><p>　　本課題設(shè)計(jì)了算法的流程來實(shí)現(xiàn)數(shù)據(jù)塊的可變長切分，并將其應(yīng)用于重復(fù)數(shù)據(jù)刪除軟件中，檢驗(yàn)算法的性能。</p><p>　　1.5 全篇論文的主要內(nèi)容</p><p>　　論文主要分析了當(dāng)前重復(fù)數(shù)據(jù)刪除技術(shù)的主要方法

32、，及各自的優(yōu)缺點(diǎn)，同時(shí)主要分析了可變分塊算法的主要過程以及算法實(shí)現(xiàn)的思想。同時(shí)闡述了重復(fù)數(shù)據(jù)刪除技術(shù)在時(shí)下社會的的應(yīng)用及主要不足。論文最后是對于重復(fù)數(shù)據(jù)刪除技術(shù)進(jìn)行展望和總結(jié)。</p><p>　　2 重復(fù)數(shù)據(jù)刪除技術(shù)</p><p>　　國外經(jīng)過多年的發(fā)展，重復(fù)數(shù)據(jù)刪除技術(shù)己形成完整的運(yùn)作體系。鑒于一般過程達(dá)到共識，本章主要分析重復(fù)數(shù)據(jù)刪除主要運(yùn)用的關(guān)鍵技術(shù)。</p>&

33、lt;p>　　2.1 重復(fù)數(shù)據(jù)刪除的流程</p><p>　　重復(fù)數(shù)據(jù)刪除數(shù)據(jù)的流程如圖2-1所示：</p><p>　　分塊Hash計(jì)算HashKey比較</p><p>　　圖2-1 重復(fù)數(shù)據(jù)刪除數(shù)據(jù)的一般流程</p><p>　　如圖所示，需要先對于文件進(jìn)行分塊，然后對于分塊并進(jìn)行文件Hash值的計(jì)算，再比較所得的Hash值

34、，最后實(shí)現(xiàn)對于重復(fù)數(shù)據(jù)的刪除。</p><p><b>　　2.2 檢測技術(shù)</b></p><p>　　本節(jié)介紹了相同數(shù)據(jù)檢測的4種技術(shù)。從前面的討論我們可以看出，重復(fù)數(shù)據(jù)的存在形式中有很大一部分是完全相同的數(shù)據(jù)，文獻(xiàn)采用具有不同相關(guān)性的數(shù)據(jù)集評估了相同文件（whole file detection，WFD）、固定分塊（fixed-sized partition，

35、FSP）、可變分塊檢測技術(shù)（content-defined chunking，CDC）和滑動塊檢測技術(shù)，并給出了在變化的數(shù)據(jù)類型上使用這些方法所獲得的益處。</p><p>　　2.2.1 相同文件檢測技術(shù)</p><p>　　相同文件檢測技術(shù)(WFD)是在文件級別的粒度下查找重復(fù)數(shù)據(jù)的方法。該方法是通過對整個(gè)文件進(jìn)行Hash[9]計(jì)算，然后將該值和已存儲的Hash值進(jìn)行比較，如果檢測到

36、相同的值，則僅將文件用指針替換，不進(jìn)行實(shí)際的存儲，否則存儲新的文件。</p><p>　　通過研究表明，基于Hash算法的相同文件檢測技術(shù)具有以下兩方面的優(yōu)勢：（1）在普通硬件條件下計(jì)算速度很快，加州大學(xué)的研究表明[10]，SHA-1是83MB/S，而MD5是227MB/S；（2）可以檢測到所有完全相同的文件，節(jié)省存儲空間較大。</p><p>　　但是這種方法也有兩個(gè)主要的缺點(diǎn)：（1）因

37、該方法是對所有的文件Hash值進(jìn)行比較，對于較大的數(shù)據(jù)集，需要比較的范圍大，時(shí)間消耗也多；（2）即使不同文件內(nèi)部存在很多相同的數(shù)據(jù)，也不能被檢測并實(shí)現(xiàn)冗余消除。</p><p>　　2.2.2 基于內(nèi)容算法的檢測技術(shù)</p><p>　　基于內(nèi)容識別的重復(fù)檢測技術(shù)的基本原理是對記錄的數(shù)據(jù)格式進(jìn)行比對。在備份數(shù)據(jù)時(shí),該技術(shù)會讀取數(shù)據(jù)并從中提取出每組備份集以及備份集中數(shù)據(jù)對象的元數(shù)據(jù),存入到

38、內(nèi)嵌文件系統(tǒng)的數(shù)據(jù)庫內(nèi)。當(dāng)有新的數(shù)據(jù)進(jìn)入時(shí)則對新的元數(shù)據(jù)與數(shù)據(jù)庫中的元數(shù)據(jù)進(jìn)行版本比對?；趦?nèi)容的算法可以減少計(jì)算量，并可以利用元數(shù)據(jù)之間的聯(lián)系更快地查找重復(fù)數(shù)據(jù),但需要針對不同情況分別提取不同的元數(shù)據(jù)，實(shí)現(xiàn)起來比較復(fù)雜。</p><p>　　2.2.3 定長塊的切分</p><p>　　相同文件檢測技術(shù)不能用于文件內(nèi)部的重復(fù)數(shù)據(jù)查找，使得數(shù)據(jù)占用空間沒有充分縮減，因此研究者們將目光集中

39、于更細(xì)粒度——塊級別的重復(fù)數(shù)據(jù)檢測上來[11]。固定分塊檢測技術(shù)（FSP）是使用固定大小的分塊策略在存儲系統(tǒng)中識別相同數(shù)據(jù)的一種方法，如圖2-2所示，該方法分為三個(gè)步驟：（1）固定大小的分塊技術(shù)提供一個(gè)預(yù)先已經(jīng)定義好的塊的大?。ㄔ撝氮?dú)立于所存取的數(shù)據(jù)內(nèi)容），所有文件均按照這個(gè)固定的塊大小進(jìn)行劃分；（2）每個(gè)劃分好的數(shù)據(jù)塊均通過哈希算法（MD5或SHA1）得到一個(gè)指紋值；（3）將該值和已存儲的塊指紋值進(jìn)行比對，如果檢測到相同的值，則刪除其

40、代表的數(shù)據(jù)塊，否則存儲新的數(shù)據(jù)塊。</p><p><b>　　．．．文件．．．</b></p><p>　　SHA-1 HashSHA-1 Hash SHA-1 Hash</p><p><b>　　否</b></p><p><b>　　是</b></p>

41、;<p>　　圖2-2 固定分塊檢測技術(shù)</p><p>　　通過研究發(fā)現(xiàn)，固定分塊檢測技術(shù)已應(yīng)用在很多領(lǐng)域，并具有如下兩個(gè)特征：（1）縮減存儲空間：針對數(shù)據(jù)歸檔的網(wǎng)絡(luò)存儲系統(tǒng)Venti應(yīng)用該技術(shù)減少了大約30%的存儲空間。（2）減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量：虛擬機(jī)優(yōu)化系統(tǒng)通過該技術(shù)加速了在低寬帶網(wǎng)絡(luò)上的數(shù)據(jù)傳輸并改進(jìn)了內(nèi)存的性能。</p><p>　　此外，固定分塊檢測技術(shù)還可以

42、提供很高的處理速度，適合于在交互性的環(huán)境中應(yīng)用[12]。但是它也具有一定的局限性：在刪除重復(fù)數(shù)據(jù)時(shí)該技術(shù)對編輯和修改的序列很敏感，對于插入問題（在原來的數(shù)據(jù)流中某處插入少量新字節(jié)，其它部分不變）和刪除問題（在原來的數(shù)據(jù)流中某處刪除少量新字節(jié)，其它部分不變）處理十分低效，即該技術(shù)不能智能的根據(jù)文件自身內(nèi)容的變化和文件之間的關(guān)聯(lián)關(guān)系進(jìn)行調(diào)整與優(yōu)化，這也是基于固定分塊檢測技術(shù)的一個(gè)劣勢。</p><p>　　2.2.4

43、 變長塊的切分</p><p>　　為了彌補(bǔ)固定塊大小劃分技術(shù)的局限性，更加靈活的找到重復(fù)數(shù)據(jù)，研究者們提出了可變塊大小劃分的檢測技術(shù)。</p><p>　　這是一種基于內(nèi)容Content-Defined Chunking(CDC)技術(shù)的分塊方法，與固定分塊不同的是它的塊斷點(diǎn)不以一個(gè)預(yù)設(shè)值來確定，而是以其文件內(nèi)容進(jìn)行計(jì)算，當(dāng)滿足一定的標(biāo)準(zhǔn)之后方認(rèn)為其為塊斷點(diǎn)。在實(shí)現(xiàn)變長分塊前，我們先建立

44、一種弱Hash的機(jī)制，滿足兩個(gè)規(guī)則：（1）Hash值相同的時(shí)候內(nèi)容不一定相同，Hash值不同的時(shí)候內(nèi)容一定不同。（2）Hash的沖突盡可能的頻繁，這樣可以避免文件塊變得異常的大。我們使用這種Hash函數(shù)，對文件進(jìn)行計(jì)算，當(dāng)Hash值滿足一定條件，比如等于一個(gè)預(yù)定義值的時(shí)候我們便認(rèn)為此時(shí)該內(nèi)容所在的地方為一個(gè)塊斷點(diǎn)。</p><p>　　根據(jù)CDC算法的特性，我們可以發(fā)現(xiàn)基于CDC算法檢測技術(shù)的特點(diǎn)是：對于插入問題

45、和刪除問題處理高效。無論是插入還是刪除一小部分字節(jié)，只會影響一到兩個(gè)塊，其余的塊保持不變，即CDC方法在兩個(gè)相似對象（只相差幾個(gè)字節(jié)）之間可以檢測出更多的冗余。</p><p>　　但是CDC算法也存在一定的局限性，它劃分的粒度絕大部分取決于期望塊的設(shè)定，如果該值設(shè)置的較小，雖然粒度較細(xì)，重復(fù)數(shù)據(jù)查找較為精確，但是額外存儲每塊信息的開銷很大，相反，如果該值設(shè)置的較大，則粒度過粗，重復(fù)數(shù)據(jù)刪除的效果不好。所以，如何

46、權(quán)衡取舍是一個(gè)難點(diǎn)。</p><p>　　2.2.5 滑動塊檢測技術(shù)</p><p>　　可變分塊檢測技術(shù)對一個(gè)文件間小的隨機(jī)改變檢測效果不佳。針對這一問題，一些研究者將滑動塊技術(shù)引入到相同數(shù)據(jù)檢測中來，以期更好的檢測到變化的數(shù)據(jù)?；瑒訅K技術(shù)結(jié)合了固定塊大小檢測技術(shù)和可變塊大小檢測技術(shù)的優(yōu)點(diǎn)，塊大小固定，管理簡單。通過測試發(fā)現(xiàn)，對大的簇，CDC的重復(fù)數(shù)據(jù)檢測性能較好，而滑動塊技術(shù)對細(xì)粒度

47、匹配更適用。基于滑動塊技術(shù)的相同塊檢測過程有4步，如圖2-3所示：（1）一個(gè)文件用rsync求和校驗(yàn)（checksum）函數(shù)和固定塊大小的滑動窗口來計(jì)算文件對象的每個(gè)重疊塊的求和校驗(yàn)值；（2）對于每個(gè)塊，將計(jì)算出的求和校驗(yàn)值與先前存儲的值進(jìn)行比較；（3）如果匹配，則利用更嚴(yán)格的SHA-1算法對塊進(jìn)行Hash計(jì)算，并將SHA-1 Hash值與先前存儲的值進(jìn)行比較，從而進(jìn)行冗余檢測。如果檢測到數(shù)據(jù)冗余，將其記錄后，滑動窗口越過這個(gè)冗余塊繼續(xù)

48、前進(jìn)。而且對于在先前的已經(jīng)被劃分的塊和最近被檢測到冗余之前的這個(gè)碎片，需要被記錄并且存儲；（4）如果求和校驗(yàn)值或Hash值不能匹配，則滑動窗口繼續(xù)向前。如果滑動窗口已經(jīng)行駛了一個(gè)塊大小的距離，但是仍然無法匹配到任何已經(jīng)被存儲的塊，則需要對這個(gè)塊進(jìn)行求和校驗(yàn)和S</p><p><b>　　．．．文件．．．</b></p><p><b>　　校驗(yàn)</b

49、></p><p><b>　　校驗(yàn)</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p>　　圖2-3 滑動塊檢測技術(shù)</p&

50、gt;<p>　　根據(jù)滑動塊技術(shù)的特性，我們可知該技術(shù)的特點(diǎn)是對于插入問題和刪除問題處理高效，并能始終檢測到更多的冗余數(shù)據(jù)。（1）插入問題：如果一小部分字節(jié)被插入到一個(gè)對象中，只有周圍的塊會改變，接下來的塊將仍然會被識別出來并被該算法匹配，并且一個(gè)長度等于插入的字節(jié)數(shù)的碎片會被產(chǎn)生出來。（2）刪除問題：刪除一小部分字節(jié)也會產(chǎn)生一個(gè)長度等于塊大小減去被刪除部分字節(jié)長度的碎片，其它的塊不受影響。但該技術(shù)也存在一個(gè)不足：在插入和

51、刪除問題中都會引入碎片，如何能夠準(zhǔn)確識別改變的數(shù)據(jù)，不影響匹配數(shù)據(jù)塊，從而不產(chǎn)生額外的碎片將是一個(gè)研究的難點(diǎn)。</p><p>　　2.3 對于數(shù)據(jù)塊進(jìn)行Hash值計(jì)算</p><p>　　文件被切分成數(shù)據(jù)塊之后，需要對每個(gè)數(shù)據(jù)塊的內(nèi)容計(jì)算Hash值，保存下數(shù)據(jù)塊的各個(gè)Hash值，以便為以后的數(shù)據(jù)進(jìn)行比較。內(nèi)容不同，Hash值不同。內(nèi)容相同，Hash相同。對于數(shù)據(jù)塊進(jìn)行Hash值的計(jì)算，

52、使得數(shù)據(jù)塊的存在不同時(shí)，Hash值不同，使得數(shù)據(jù)重復(fù)檢測成為可能。</p><p><b>　　2.4 消除重復(fù)</b></p><p>　　首先對于保存的Hash值進(jìn)行檢索，根據(jù)Hash值的不同，判斷數(shù)據(jù)塊的重復(fù)性，對于數(shù)據(jù)進(jìn)行進(jìn)一步的刪除、修改、插入，使得重復(fù)數(shù)據(jù)得到刪除。使得數(shù)據(jù)能夠得到單一化存儲，同時(shí)將更新的文件進(jìn)一步保存和對其進(jìn)行指紋和數(shù)據(jù)塊的計(jì)算，保存下

53、新的Hash值和指紋。</p><p>　　3 重復(fù)數(shù)據(jù)刪除中的可變分塊算法</p><p>　　本算法可以分為文件分塊和記錄指紋，計(jì)算數(shù)據(jù)塊Hash值，重復(fù)數(shù)據(jù)比較，數(shù)據(jù)存儲四個(gè)部分，如圖3-1。本章將對于這四個(gè)部分進(jìn)行分別介紹。</p><p>　　圖3-1 重復(fù)數(shù)據(jù)刪除可變分塊算法模型</p><p>　　3.1 文件分塊和記錄指紋

54、</p><p>　　文件分塊是本算法的關(guān)鍵，是該算法體現(xiàn)文件可變分塊的具體體現(xiàn)。主要體現(xiàn)它與固定分塊的區(qū)別。</p><p>　　文件被分為大小可變的數(shù)據(jù)塊,數(shù)據(jù)塊的大小在一個(gè)規(guī)定的最小值和最大值之間?？勺兇笮〉臄?shù)據(jù)塊用一個(gè)滑動窗口來劃分，當(dāng)滑動窗口的Hash值與一個(gè)基準(zhǔn)值相匹配時(shí)就創(chuàng)建一個(gè)分塊，這樣數(shù)據(jù)塊的尺寸分布就可達(dá)到一個(gè)希望的情形。對于文件的分塊計(jì)算反而帶來便利。</p&g

55、t;<p>　　基準(zhǔn)值可以采用Rabin指紋(Rabin指紋生成算法由美國哈佛大學(xué)教授Rabin提出的算法)進(jìn)行計(jì)算，首先要定一個(gè)數(shù)據(jù)塊的最大值與最小值，使得數(shù)據(jù)塊不會太小或太大，有利于數(shù)據(jù)的比較。一般將這個(gè)范圍定于1k到8k之間。預(yù)先定義一個(gè)D與r（例如：可以定義D=32，r=0，這樣使得數(shù)據(jù)塊的平均大小在2k左右），在文件數(shù)據(jù)塊達(dá)到最小標(biāo)準(zhǔn)后，用一個(gè)固定大小滑動窗口在文件上滑動，并計(jì)算其滑動時(shí)的指紋的Hash值，當(dāng)該處

56、窗口內(nèi)的數(shù)據(jù)的Hash值在與k處滿足模D等于r時(shí)即為該文件的一個(gè)塊斷點(diǎn)，記錄下來這個(gè)塊斷點(diǎn)，或者當(dāng)文件達(dá)到8k是硬性定為一個(gè)斷點(diǎn)，這時(shí)的數(shù)據(jù)塊的大小為8k(即使不滿足指紋處Hash值模D等于r)。同時(shí)在文件大小不足1k時(shí)，將整個(gè)文件當(dāng)做一個(gè)數(shù)據(jù)塊，作為一個(gè)數(shù)據(jù)塊。然后窗口繼續(xù)滑動，重復(fù)上述動作，在每個(gè)分塊點(diǎn)的位置上記錄下來。在文件結(jié)束處，將剩余的數(shù)據(jù)塊作為一個(gè)數(shù)據(jù)塊，但是最后一個(gè)可能不滿足上述要求，文件被分為n塊，同時(shí)有n-1個(gè)指紋值。

57、將指紋值記錄下來。過程如圖3-2[13]：</p><p><b>　?。募?lt;/b></p><p>　　fingerprint是</p><p><b>　　否</b></p><p>　　圖3-2 文件分塊過程</p><p>　　3.2 計(jì)算數(shù)據(jù)塊Has

58、h值</p><p>　　在第一個(gè)部分中已經(jīng)將文件分為了各個(gè)數(shù)據(jù)塊，現(xiàn)在要將各個(gè)分好的數(shù)據(jù)塊進(jìn)行MD5運(yùn)算出其Hash值。記錄下每個(gè)分塊點(diǎn)的位置，以及每個(gè)數(shù)據(jù)塊的Hash值，保存下來，作為原文件的文件記錄。系統(tǒng)會通過分塊點(diǎn)和Hash值來判斷文件的異同。 </p><p>　　MD5為計(jì)算機(jī)安全領(lǐng)域廣泛使用的一種散列函數(shù)，用以提供消息的完整性保護(hù)。對MD5算法簡要的敘述可以為：MD5以51

59、2位分組來處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過了一系列的處理后，算法的輸出由四個(gè)32位分組組成，將這四個(gè)32位分組級聯(lián)后將生成一個(gè)128位散列值。MD5的典型應(yīng)用是對一段Message(字節(jié)串)產(chǎn)生fingerprint(指紋)，以防止被“篡改”。舉個(gè)例子，你將一段話寫在一個(gè)叫 readme.txt文件中，并對這個(gè)readme.txt產(chǎn)生一個(gè)MD5的值并記錄在案，然后你可以傳播這個(gè)文件給別人，別人如果修改了文件中

60、的任何內(nèi)容，你對這個(gè)文件重新計(jì)算MD5時(shí)就會發(fā)現(xiàn)兩個(gè)MD5值不相同。</p><p>　　3.3 重復(fù)數(shù)據(jù)比較</p><p>　　（1）將新文件的屬性信息與所有已備份文件的信息進(jìn)行比較,看是否有相同文件或名稱不同內(nèi)容相同的文件。如果有，則不需要實(shí)際的傳輸數(shù)據(jù)，只需更新文件信息庫內(nèi)容,將新文件信息索引指向已存的相同文件；</p><p>　?。?）如果沒有發(fā)現(xiàn)重復(fù)

61、文件，則用Rabin指紋算法來對新文件進(jìn)行掃描分塊，計(jì)算數(shù)據(jù)塊的Hash值，并與已有的文件指紋庫和相對應(yīng)的偏移位置進(jìn)行比較。標(biāo)記所有發(fā)生了變化的數(shù)據(jù)塊；</p><p>　　（3）如果變化的數(shù)據(jù)量小或者帶寬充足，則直接同步對應(yīng)的數(shù)據(jù)塊內(nèi)容即可，如圖3-3所示。</p><p>　　S1C1C2C3C4C5C6C7</p><p>　　S2C1C2

62、C3C8C5C6 C7</p><p>　　S3C1C2C3C8C9C10C6 C7</p><p>　　S4C1C11C8C9C10C6 C7</p><p>　　圖 3-3 直接同步數(shù)據(jù)塊</p><p>　　假設(shè)文件A在初始狀態(tài)( S1)生成了備份文件A′，當(dāng)文件A

63、發(fā)生插入修改( S2, S3) ,刪除修改后( S4) ，生成新備份文件A″：</p><p>　?。?）文件A′根據(jù)Rabin 指紋算法,生成6個(gè)指紋，文件被劃分為7個(gè)數(shù)據(jù)塊，指紋以{M1, M2, ?, M6}表示，數(shù)據(jù)塊以{C1, C2, C3, C4, C5, C6, C7}表示；</p><p>　?。?）發(fā)生插入修改,如S2所示,新插入的數(shù)據(jù)位于C4中，如果(C4 + 新插入的

64、數(shù)據(jù)塊)經(jīng)過Rabin指紋計(jì)算，為一個(gè)chunk (未產(chǎn)生新的指紋) ，僅需傳輸C8數(shù)據(jù)塊，在服務(wù)端更新版本庫和指紋庫，得到A″；</p><p>　　（3）插入修改,如S3所示,如果插入的數(shù)據(jù)導(dǎo)致原來一個(gè)chunk劃分為兩個(gè)chunk，僅需傳輸C9和C10 兩個(gè)數(shù)據(jù)塊，在服務(wù)端更新版本庫和指紋庫,得到A″；</p><p>　?。?）刪除修改,如S4所示，如果刪除的數(shù)據(jù)塊影響了一個(gè)指紋，

65、導(dǎo)致原來兩個(gè)chunk 合并為一個(gè)chunk，則僅需傳輸C11,在服務(wù)端更新版本庫和指紋庫后,得到A″。</p><p><b>　　3.4 數(shù)據(jù)存儲</b></p><p>　　對于存儲數(shù)據(jù)而言，需要記錄下更新文件以后的MD5的值，以及分塊點(diǎn)的位置，可以做成一個(gè)< fingerprint，MD5 >的二元組，那么在用戶下次再更新數(shù)據(jù)時(shí)就相當(dāng)方便。在下次

66、更新時(shí)就不用對原文進(jìn)行處理了，而在下一次更新時(shí)獲得方便的同時(shí)對于文件數(shù)據(jù)有一定的記錄作用。如圖3-4所示：</p><p>　　圖 3-4 重復(fù)數(shù)據(jù)檢測流程</p><p>　　在文件存儲方面主要是要保持文件以及分塊的單一性，保證重復(fù)數(shù)據(jù)的正確刪除，和對于數(shù)據(jù)的分塊信息的即使備份。方便在下一更新是對于更新文件進(jìn)行比較。</p><p>　　3.5 新文件的指紋以

67、及已分?jǐn)?shù)據(jù)塊Hash值的保存</p><p>　　對于新文件的保存主要分為以下幾步完成</p><p>　?。?）對于原文件和更新文件進(jìn)行各個(gè)分塊的Hash值對比，找出Hash值相同的部分，并記錄下下兩個(gè)文件相同的分塊的分塊點(diǎn)在什么位置；</p><p>　?。?）然后對于不同部分進(jìn)行同步，等到新的文件數(shù)據(jù)庫；</p><p>　　（3）對于

68、新的文件數(shù)據(jù)進(jìn)行分塊，記錄新的分塊點(diǎn)保存下來。</p><p>　　整個(gè)的流程如下圖3-5：</p><p>　　圖 3-5 文件指紋和已分?jǐn)?shù)據(jù)塊Hash值保存流程</p><p>　　4 重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用</p><p>　　在基礎(chǔ)架構(gòu)中的多個(gè)不同位置部署重復(fù)數(shù)據(jù)刪除技術(shù)，以解決存在大量冗余數(shù)據(jù)的問題。重復(fù)數(shù)據(jù)的作用包括以下幾方面

69、：（1）降低成本。重復(fù)數(shù)據(jù)刪除帶來了資源效率和成本節(jié)約，包括數(shù)據(jù)中心耗電量以及存儲容量、網(wǎng)絡(luò)帶寬和IT管理人員的減少。（2）提高備份和恢復(fù)級別。重復(fù)數(shù)據(jù)刪除可大大提高備份性能，從而可以在有限的備份時(shí)間窗口內(nèi)完成備份。重復(fù)數(shù)據(jù)刪除技術(shù)還可以充分利用隨機(jī)存取磁盤存儲，與順序存?。ù艓В┓椒ㄏ啾忍岣吡嘶謴?fù)性能。（3）改變磁盤相對于磁帶的經(jīng)濟(jì)性。重復(fù)數(shù)據(jù)刪除使基于磁盤的備份適用于更多的應(yīng)用程序。磁帶之所以仍在數(shù)據(jù)中心的數(shù)據(jù)備份存儲中扮演著重要角

70、色，是由于其經(jīng)濟(jì)性和易于歸檔特性。然而在與重復(fù)數(shù)據(jù)刪除配合使用時(shí)每GB成本將降低，從而使磁盤的成本等于甚至小于磁帶成本。（4）重復(fù)數(shù)據(jù)刪除降低了數(shù)據(jù)存儲在電源、冷卻和空間方面的需求，降低能源消耗，因而減少了二氧化碳排放，承擔(dān)起環(huán)保責(zé)任。</p><p>　　4.1 重復(fù)數(shù)據(jù)刪除的主要應(yīng)用特點(diǎn)</p><p>　　4.1.1 數(shù)據(jù)備份系統(tǒng)</p><p>　　重復(fù)

71、數(shù)據(jù)刪除技術(shù)為數(shù)據(jù)保護(hù)領(lǐng)域帶來革命性突破，有效地改善了磁盤數(shù)據(jù)保護(hù)的成本效益。因?yàn)樵趥鹘y(tǒng)數(shù)據(jù)保護(hù)中無法實(shí)現(xiàn)重復(fù)數(shù)據(jù)刪除，往往采用廉價(jià)的磁帶庫作為備份設(shè)備，而磁帶備份在備份窗口、恢復(fù)速度方面難以滿足用戶的需求?，F(xiàn)在，基于磁盤的數(shù)據(jù)保護(hù)方案如虛擬磁盤庫(VTL)被廣泛采用，并且在未來會繼續(xù)增長。備份到VTL或其他基于磁盤的備份已經(jīng)縮小了備份窗口，改善了備份和恢復(fù)能力，但由于數(shù)據(jù)量的不斷增加，人們所要備份的數(shù)據(jù)越來越多，面臨容量膨脹的壓力。重

72、復(fù)數(shù)據(jù)刪除技術(shù)的出現(xiàn)，為最小化存儲容量找到有效的方法。</p><p>　　4.1.2 歸檔存儲系統(tǒng)</p><p>　　重復(fù)數(shù)據(jù)刪除技術(shù)對歸檔存儲非常重要。由于參考數(shù)據(jù)的數(shù)量不斷增長，而法規(guī)遵從要求數(shù)據(jù)在線保留的時(shí)間更長，并且由于高性能需求需要采用磁盤進(jìn)行歸檔，因此，企業(yè)一旦真正開始進(jìn)行數(shù)據(jù)的存儲歸檔就面臨成本問題。理想的歸檔存儲系統(tǒng)應(yīng)能滿足長期保存歸檔數(shù)據(jù)的需求，并且總擁有成本也要低

73、于生產(chǎn)環(huán)境。重復(fù)數(shù)據(jù)刪除技術(shù)通過消除冗余實(shí)現(xiàn)高效率的歸檔存儲，從而實(shí)現(xiàn)最低的成本。目前，歸檔存儲系統(tǒng)的重復(fù)數(shù)據(jù)刪除技術(shù)主要是基于Hash的方法。</p><p>　　4.1.3 遠(yuǎn)程災(zāi)備系統(tǒng)</p><p>　　在遠(yuǎn)程災(zāi)備系統(tǒng)中，需要將大量的數(shù)據(jù)遷移到異地的系統(tǒng)中。隨著數(shù)據(jù)量的不斷增長，數(shù)據(jù)傳輸?shù)膲毫υ絹碓酱螅ㄟ^重復(fù)數(shù)據(jù)刪除技術(shù)在數(shù)據(jù)傳輸前檢測并刪除重復(fù)的數(shù)據(jù)，可以有效地減少傳輸?shù)臄?shù)據(jù)

74、量，提高傳輸數(shù)據(jù)速度，例如飛康的MicroScan軟件就采用了該技術(shù)。</p><p>　　4.2 重復(fù)數(shù)據(jù)刪除技術(shù)的實(shí)踐例證</p><p>　　在IT方面，中國人民銀行鄭州中心支行（簡稱鄭州支行）有十多個(gè)應(yīng)用系統(tǒng)為工作提供技術(shù)保障，包括賬戶系統(tǒng)、財(cái)務(wù)系統(tǒng)、報(bào)表系統(tǒng)、辦公自動化系統(tǒng)、會計(jì)核算系統(tǒng)、事后監(jiān)督系統(tǒng)、國庫會計(jì)核算系統(tǒng)、同城清算系統(tǒng)、公文傳輸系統(tǒng)、總行郵件系統(tǒng)、事后影響系統(tǒng)、綜

75、合管理平臺系統(tǒng)等等。每一個(gè)系統(tǒng)都流動著非常重要的數(shù)據(jù)，因此，數(shù)據(jù)備份是一件及其重要的工作。</p><p>　　根據(jù)每個(gè)應(yīng)用系統(tǒng)的不同要求，有的需要每天備份，保留最少7天的數(shù)據(jù)；有的需要每天備份，保留一年的數(shù)據(jù)；有的需要分別保留最近12個(gè)月、最近四周和最近7天的數(shù)據(jù)。</p><p>　　隨著人民銀行業(yè)務(wù)信息系統(tǒng)的不斷升級和完善，數(shù)據(jù)保護(hù)問題面臨著越來越大的挑戰(zhàn)。各業(yè)務(wù)系統(tǒng)的數(shù)據(jù)采用分散的

76、模式各自獨(dú)立保存，其數(shù)據(jù)備份方式一般采用磁盤、磁帶、光盤、移動介質(zhì)等方式，且大多在本地保存，很難滿足數(shù)據(jù)異地備份需要。</p><p>　　鄭州中支的數(shù)據(jù)總量相對較大，保存期復(fù)雜，因此，如果采用傳統(tǒng)的備份方式，無論數(shù)據(jù)總量和備份窗口都很成問題。隨后，鄭州中支把目光投向了重復(fù)數(shù)據(jù)刪除技術(shù)，并采用了EMC公司基于重復(fù)數(shù)據(jù)刪除技術(shù)的磁盤備份技術(shù)方案。</p><p>　　EMC Avamar重

77、復(fù)數(shù)據(jù)刪除解決方案的部署很簡單，地市中心支行不需要部署硬件，只要在業(yè)務(wù)系統(tǒng)服務(wù)器上安裝備份代理即可；在中心支行部署兩個(gè)Avamar節(jié)點(diǎn)，完成雙節(jié)點(diǎn)的冗余、互備、復(fù)制和負(fù)載均衡。而且，安裝備份代理沒有數(shù)量限制，只要備份服務(wù)器節(jié)點(diǎn)的數(shù)量不超出，就可以無限擴(kuò)展。鄭州中支的分支機(jī)構(gòu)眾多，應(yīng)用服務(wù)器的數(shù)量比較大，總共安裝了近100個(gè)備份代理。</p><p>　　在鄭州中支的應(yīng)用環(huán)境中，經(jīng)過測算，鄭州中支所有設(shè)備（包括地市

78、中支）初次完全備份下來的重復(fù)數(shù)據(jù)刪除率為3:1，之后的備份由于有基礎(chǔ)數(shù)據(jù)，重復(fù)數(shù)據(jù)刪除率大大提高，達(dá)到了300:1的水平。這樣，不僅節(jié)省了大量的備份空間，而且節(jié)省了廣域網(wǎng)帶寬，使異地備份和恢復(fù)成為可能。</p><p>　　4.3 刪除備份數(shù)據(jù)重復(fù)部分</p><p>　　重復(fù)數(shù)據(jù)刪除軟件技術(shù)是對備份數(shù)據(jù)內(nèi)容進(jìn)行比對、切分處理以后，將重復(fù)的內(nèi)容刪除掉的一種數(shù)據(jù)處理技術(shù)。而那些經(jīng)過軟件技術(shù)

79、處理以后，被判定為不重復(fù)的數(shù)據(jù)或者數(shù)據(jù)片段將被完整保存。它不是一種數(shù)據(jù)壓縮行為，而是根據(jù)備份系統(tǒng)保存數(shù)據(jù)和數(shù)據(jù)副本的特點(diǎn)，以及保存這些數(shù)據(jù)內(nèi)容對存儲空間的使用方式特點(diǎn)，利用重復(fù)數(shù)據(jù)軟件及功能實(shí)現(xiàn)的一種針對備份數(shù)據(jù)和副本的壓縮效果。所以沒有備份操作的信息系統(tǒng)以及那些數(shù)據(jù)量不大的信息系統(tǒng)是沒有必要使用這種軟件技術(shù)的。</p><p>　　4.4 不能脫離存儲系統(tǒng)單獨(dú)使用</p><p>　　

80、重復(fù)數(shù)據(jù)刪除技術(shù)的核心功能是處理數(shù)據(jù)，它自身并不能完成數(shù)據(jù)的長期存儲。它必須借助其它存儲技術(shù)的幫助，通過集成實(shí)現(xiàn)一體化的重復(fù)數(shù)據(jù)刪除備份系統(tǒng)存儲設(shè)備，才能使其在信息系統(tǒng)的備份系統(tǒng)當(dāng)中發(fā)揮完整的效用。從數(shù)據(jù)處理效率和軟件技術(shù)性能方面分析，為了滿足信息系統(tǒng)對備份系統(tǒng)數(shù)據(jù)吞吐能力的需求，通常情況下，重復(fù)數(shù)據(jù)刪除軟件技術(shù)主要與硬盤存儲技術(shù)進(jìn)行集成來實(shí)現(xiàn)其綜合應(yīng)用目的。</p><p>　　4.5 重復(fù)數(shù)據(jù)刪除技術(shù)的主要

81、不足</p><p>　　重復(fù)數(shù)據(jù)刪除作為存儲的一個(gè)新技術(shù)方向，有著廣泛的應(yīng)用前景，全面應(yīng)用于主存儲系統(tǒng)和歸檔存儲系統(tǒng)中。未來發(fā)展的方向?qū)⑹牵簭亩ㄩL分塊向智能變長分塊發(fā)展；從傳統(tǒng)Hash算法向速度更快、沖突更小的Hash算法發(fā)展；從靜態(tài)Hash檢索到動態(tài)分布式Hash檢索方向發(fā)展。</p><p>　　從目前的研究來看，我們可以得出如下結(jié)論：（1）近年來，隨著重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用，其理論

82、不斷得到發(fā)展和加強(qiáng)，人們對重復(fù)數(shù)據(jù)刪除的認(rèn)識也越來越清晰。但是，如何挖掘不同類型的數(shù)據(jù)特性，快速準(zhǔn)確的檢測到重復(fù)數(shù)據(jù)，高效結(jié)合已有的技術(shù)仍然存在著可探究的空間，因此也需要研究者進(jìn)行更深入的探索。（2）因重復(fù)數(shù)據(jù)檢測技術(shù)自身設(shè)計(jì)上均存在有一定的局限性，如何在融合各技術(shù)特征的同時(shí)，通過結(jié)合統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘領(lǐng)域的各種技術(shù)，對數(shù)據(jù)特性進(jìn)行充分的分析和挖掘，找到其規(guī)律性的認(rèn)識來彌補(bǔ)重復(fù)數(shù)據(jù)刪除技術(shù)上的不足，提高整體系統(tǒng)的性能，也是一個(gè)需要深入探究

83、的方面；（3）因新的壓縮理論或更有效的數(shù)學(xué)模型不斷出現(xiàn)，壓縮技術(shù)發(fā)展非常迅速，如何通過引進(jìn)壓縮算法開發(fā)新的技術(shù)與已有技術(shù)結(jié)合在一起，有效地優(yōu)化存儲空間也是一個(gè)需要研究的問題；（4）重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用盡管節(jié)約了存儲空間，但也降低了系統(tǒng)的可靠性。當(dāng)前研究表明，已有的可靠性技術(shù)是基于增加冗余數(shù)據(jù)的。雖然這樣的技術(shù)模型具有簡單高效的特點(diǎn)，但在存儲開銷和系統(tǒng)性能方面存在一定的局限性。因此如何針對不同的數(shù)據(jù)類型，設(shè)計(jì)有效的度量方式，適度的增加冗

84、余數(shù)據(jù)來高效的提高系統(tǒng)的可靠性或</p><p><b>　　5 總結(jié)與展望</b></p><p>　　通過重復(fù)數(shù)據(jù)刪除中的可變分塊算法的編寫大致了解了現(xiàn)今數(shù)據(jù)存儲方面的現(xiàn)狀，同時(shí)了解了當(dāng)今重復(fù)數(shù)據(jù)刪除技術(shù)的主流方法和主要的優(yōu)缺點(diǎn)！ </p><p>　　近年來，隨著重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用，其理論不斷得到發(fā)展和加強(qiáng)，人們對重復(fù)數(shù)據(jù)刪除的認(rèn)識

85、也越來越清晰。但是，如何挖掘不同類型的數(shù)據(jù)特性，快速準(zhǔn)確的檢測到重復(fù)數(shù)據(jù)，高效結(jié)合已有的技術(shù)仍然存在著可探究的空間，因此也需要研究者進(jìn)行更深入的探索。</p><p>　　因重復(fù)數(shù)據(jù)檢測技術(shù)自身設(shè)計(jì)上均存在一定的局限性，如何在融合各技術(shù)特征的同時(shí)，通過結(jié)合統(tǒng)計(jì)學(xué)和數(shù)據(jù)挖掘領(lǐng)域的各種技術(shù)，對數(shù)據(jù)特性進(jìn)行充分的分析和挖掘，找到其規(guī)律性的認(rèn)識來彌補(bǔ)重復(fù)數(shù)據(jù)刪除技術(shù)上的不足，提高整體系統(tǒng)的性能，也是一個(gè)需要深入探究的方面

86、。</p><p>　　重復(fù)數(shù)據(jù)刪除技術(shù)的應(yīng)用盡管節(jié)約了存儲空間，但也降低了系統(tǒng)的可靠性。當(dāng)前研究表明，已有的可靠性技術(shù)是基于增加冗余數(shù)據(jù)的。雖然這樣的技術(shù)模型具有簡單高效的特點(diǎn)，但在存儲開銷和系統(tǒng)性能方面存在一定的局限性。</p><p>　　面對當(dāng)今社會信息的爆炸式的增長，重復(fù)數(shù)據(jù)刪除算法技術(shù)越來越成為主流的技術(shù)方法。同時(shí)重復(fù)數(shù)據(jù)刪除中的可變分塊算法在對于插入問題和刪除問題處理高效性必

87、然會使其成為重復(fù)數(shù)據(jù)中的主流算法。同時(shí)CDC算法也存在一定的局限性，它劃分的粒度絕大部分取決于期望塊的設(shè)定，如果該值設(shè)置的較小，雖然粒度較細(xì)，重復(fù)數(shù)據(jù)查找較為精確，但是額外存儲每塊信息的開銷很大，相反，如果該值設(shè)置的較大，則粒度過粗，重復(fù)數(shù)據(jù)刪除的效果不好的缺點(diǎn)也局限了其適用范圍，所以在以后的發(fā)展過程中必然要注意這方面的改進(jìn)。</p><p>　　由于Hash算法不關(guān)心數(shù)據(jù)塊的內(nèi)容，因此已經(jīng)壓縮的數(shù)據(jù)，比如Zip

88、，JPEG,GIF以及各種媒體數(shù)據(jù)對這種算法技術(shù)的重復(fù)數(shù)據(jù)刪除技術(shù)來說是極大的困難。因此，基于Hash算法的重復(fù)數(shù)據(jù)刪除軟件要么在自身核心技術(shù)方面取得突破，要么打破技術(shù)壁壘與內(nèi)容已知軟件技術(shù)實(shí)現(xiàn)合作，取長補(bǔ)短才能更有發(fā)展前途。</p><p>　　所以面對這些問題，重復(fù)數(shù)據(jù)刪除算法如何融合各種現(xiàn)有技術(shù)的同時(shí)，提供通用性、可擴(kuò)展性和自適應(yīng)性是重中之重。同時(shí)也要減小重復(fù)數(shù)據(jù)在檢測和刪除過程中的系統(tǒng)開銷。</p&

89、gt;<p><b>　　參考文獻(xiàn)</b></p><p>　　[1]程菊生.重復(fù)數(shù)據(jù)刪除技術(shù)的研究[J].華賽科技,2008,4:8-11. </p><p>　　[2] Douglis,F.,Iyengar,A.Application-Specific delta encoding via resemblance detection[C].In Us

90、enix Annual Technical Conference,San Antonio,Texas:USENIX Association,2003:113-126.</p><p>　　[3] 劉俊輝.HASH消息摘要算法實(shí)現(xiàn)及改進(jìn)[J].福建電腦,2007,(4):92-93.</p><p>　　[4] 顏軍.重復(fù)數(shù)據(jù)刪除帶來集群架構(gòu)革命[J].計(jì)算機(jī)世界·技術(shù)與應(yīng)用,20

91、08,6(24):40-41.</p><p>　　[5] 范濤.網(wǎng)絡(luò)存儲技術(shù)的研究與應(yīng)用[J].福建電腦,2008,(6):90-93.</p><p>　　[6] 佟樂.重復(fù)數(shù)據(jù)刪除的前世今生[J].福建電腦，2007,(4):92-93.</p><p>　　[7] 蔡盛鑫.一種基于重復(fù)數(shù)據(jù)刪除的備份系統(tǒng)[D].北京郵電大學(xué)碩士論文，2006.</p&g

92、t;<p>　　[8] J. McKnight,T.Asaro,B.Babineau.Digital Archiving:End-User Survey and Market Forecast [J].The Enterprise Strategy Group,2006:30-35.</p><p>　　[9] Athicha Muthitacharoen,Benjie Chen,David Maz

93、i´eres.A Low-Bandwidth Network File System[C].In Proceedings of the Symposium on Operating Systems Principles (SOSP'01).Chateau Lake Louise,Banff,Canada: ACM Association,2001:174-187.</p><p>　　[10]S

94、AVAGE S,WETHERALL D,KARLINA,etal.Network support for IPtraceback[J].ACM/IEEE Transactions on Networking,2001,9(3):226-237.</p><p>　　[11] 敖莉,舒繼武,李明強(qiáng).重復(fù)數(shù)據(jù)刪除技術(shù)[J].軟件學(xué)報(bào),2010,5(21):916-929. </p><p

95、>　　[12] RICHARD S W 著.范偉華,胥光輝,張清,等譯.TCP/IP 詳解一卷 1:協(xié)議[M].北京:機(jī)械工業(yè)出版社,2000.</p><p>　　[13] Pearl J.Data Mining with Graphical Models[D]. Standford University,2000.</p><p>　　[14] 李立松.基于IP存儲的網(wǎng)絡(luò)容災(zāi)技術(shù)

96、研究與系統(tǒng)實(shí)現(xiàn)[D].中國優(yōu)秀博碩士學(xué)位論文全文數(shù)據(jù)庫(碩士),2005。</p><p>　　本科畢業(yè)設(shè)計(jì)(論文)</p><p><b>　　任 務(wù) 書</b></p><p><b>　　（2011屆）</b></p><p><b>　　畢業(yè)論文（設(shè)計(jì)）</b><

97、/p><p><b>　　文獻(xiàn)綜述</b></p><p>　　題　 目: 　 重復(fù)數(shù)據(jù)刪除中的可變分塊算法 </p><p>　　學(xué) 　院:　　 商學(xué)院 　　 </p><p>　　?！　I(yè):　　 信息管理與信息系統(tǒng)　　 </p><

98、p>　　班　　級:　　　 　　 </p><p>　　學(xué)　 號:　　 　　 　　 </p><p>　　姓　 名:　　　 　 </p><p>　　指導(dǎo)教師:　　　 　　

99、 </p><p><b>　　教　務(wù)　處　制</b></p><p><b>　　一、前言部分</b></p><p>　　在存儲備份過程存在大量內(nèi)容相同的數(shù)據(jù)，將這些內(nèi)容相同的數(shù)據(jù)刪除，只保留其中一份。這種技術(shù)稱為重復(fù)數(shù)刪除技術(shù)。重復(fù)數(shù)據(jù)刪除技術(shù)的宗旨就是為企業(yè)用戶提供重復(fù)數(shù)據(jù)的備份解決方案，增加有效存儲空間

100、，提高存儲效率，使企業(yè)備份解決方案更加完善、高效。按照部署位置的不同，重復(fù)數(shù)據(jù)刪除可分為源端重復(fù)數(shù)據(jù)刪除和目標(biāo)端重復(fù)數(shù)據(jù)刪除。源端重復(fù)數(shù)據(jù)刪除是先刪除重復(fù)數(shù)據(jù)，再將數(shù)據(jù)傳到備份設(shè)備。目標(biāo)端重復(fù)數(shù)據(jù)刪除是先將數(shù)據(jù)傳到備份設(shè)備，存儲時(shí)再刪除重復(fù)數(shù)據(jù)。按照檢查重復(fù)數(shù)據(jù)的算法不同，重復(fù)數(shù)據(jù)刪除可以分為對象/文件級和塊級的重復(fù)數(shù)據(jù)刪除。對象級的重復(fù)數(shù)據(jù)刪除保證文件不重復(fù)。塊級重復(fù)數(shù)據(jù)刪除則將文件分成數(shù)據(jù)塊進(jìn)行比較。根據(jù)切分?jǐn)?shù)據(jù)塊方法的不同，又可分

101、為定長塊和變長塊的重復(fù)數(shù)據(jù)刪除技術(shù)。變長塊的重復(fù)數(shù)據(jù)刪除，數(shù)據(jù)塊的長度是變動的。定長塊的重復(fù)數(shù)據(jù)刪除，數(shù)據(jù)塊的長度是固定的。根據(jù)應(yīng)用場合的不同，可以分為通用型重復(fù)數(shù)據(jù)刪除系統(tǒng)和專用型重復(fù)數(shù)據(jù)刪除系統(tǒng)。通用型重復(fù)數(shù)據(jù)刪除系統(tǒng)是指廠商提供通用的重復(fù)數(shù)據(jù)刪除產(chǎn)品，而不是和特定虛擬磁帶庫或備份設(shè)備相聯(lián)系。專用型重復(fù)數(shù)據(jù)刪除系統(tǒng)是和特定虛擬磁帶或備份設(shè)備相聯(lián)系，一般采取目標(biāo)端重復(fù)</p><p>　　根據(jù)目前的研究現(xiàn)狀，我

102、們可以分析得出，隨著重復(fù)數(shù)據(jù)刪除技術(shù)的研究與應(yīng)用，其理論得到不斷發(fā)展和完善，人們對重復(fù)數(shù)據(jù)刪除的認(rèn)識也越來越清晰。但是，如何充分挖掘數(shù)據(jù)的內(nèi)在特性，將其應(yīng)用到已有的技術(shù)中，發(fā)揮各技術(shù)的優(yōu)勢，彌補(bǔ)其中的不足是一個(gè)可深入探究的領(lǐng)域；從重復(fù)數(shù)據(jù)刪除技術(shù)的可靠性研究角度，如何在吸收現(xiàn)有成果的同時(shí)，引入其他機(jī)制打破現(xiàn)有技術(shù)的局限性是一個(gè)需要更深入研究的方面；從重復(fù)數(shù)據(jù)刪除技術(shù)的性能研究角度，如何融合各種現(xiàn)有技術(shù)的同時(shí)，提供通用性、可擴(kuò)展性和自適應(yīng)

103、性也是一個(gè)需要更深入研究的方面。</p><p><b>　　二、主題部分</b></p><p>　　1．重復(fù)數(shù)據(jù)刪除中的可變分塊算法原理</p><p>　　在關(guān)于重復(fù)數(shù)據(jù)刪除中的可變分塊算法的實(shí)現(xiàn)上，本文運(yùn)用VC2005中的MFC，在MFC中可以擁有很好界面操作，同時(shí)C++在各個(gè)系統(tǒng)有很好的兼容性。</p><p>

104、;　　在算法設(shè)計(jì)方面，我在文件分塊方面，采用rabinhash算法對于文件分塊（同時(shí)對于數(shù)據(jù)塊有1kbit到8kbit的限制）時(shí)的31bit的數(shù)據(jù)進(jìn)行加密，讓后對于所得的hash值進(jìn)行32的模值運(yùn)算，得到模值為0的hash值的指紋為分塊指紋，記錄下分塊的位置，同時(shí)對于每一個(gè)分塊的數(shù)據(jù)塊進(jìn)行MD5算法求hash值，保存分快點(diǎn)位置和對應(yīng)的MD5的值。當(dāng)更新文件到來時(shí)，對于更新文件采取相同的算法然后比較兩個(gè)文件的hash值對于不同hash值的

105、數(shù)據(jù)塊采用基于CDC的算法。對于文件進(jìn)行更新。在對于更新的文件在對于其進(jìn)行指紋和MD5運(yùn)算計(jì)算hash值，然后跟新指紋庫和hash值庫，保存下來。</p><p>　　rabinhash算法滿足兩個(gè)規(guī)則：（1）hash值相同的時(shí)候內(nèi)容不一定相同，hash值不同的時(shí)候內(nèi)容一定不同。（2）hash的沖突盡可能的頻繁，這樣可以避免文件塊變得異常的大。同時(shí)這個(gè)算法扥到一個(gè)9到10位的10進(jìn)制hash值方便下一步計(jì)算。這樣

106、在于文件的指紋計(jì)算上有很大的優(yōu)勢，它對于時(shí)間復(fù)雜度上有很大的優(yōu)越性，同時(shí)在文件相同時(shí)的判斷是準(zhǔn)確的，雖然在不同上會出現(xiàn)誤差，但在文件指紋計(jì)算上不是很重要，所以rabinhash在文件分塊上有很大的優(yōu)勢。</p><p>　　在文件分塊方面，本算法通過對于大于1024大小的數(shù)據(jù)塊進(jìn)行最后32位的rabinhash的計(jì)算，同時(shí)對于得到的hash值進(jìn)行模32的計(jì)算，得到模值為0的為分塊點(diǎn)，若不為0，則以31為窗口進(jìn)行滑

107、動，然后再進(jìn)行hash計(jì)算重復(fù)上述過程。記錄下各個(gè)分塊點(diǎn)。</p><p><b>　　2．重復(fù)數(shù)據(jù)的檢查</b></p><p>　　2.1相同文件檢測技術(shù)</p><p>　　相同文件檢測技術(shù)(WFD)是在文件級別的粒度下查找重復(fù)數(shù)據(jù)的方法。如圖2所示，該方法是通過對整個(gè)文件進(jìn)行hash[2]計(jì)算，然后將該值和已存儲的hash值進(jìn)行比較，如