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

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

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

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

4、一些不足。</p><p>　　關鍵詞： 重復數(shù)據(jù)刪除；可變分塊；應用</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重復數(shù)據(jù)刪除技術的背景和意義- 1 -</p><p>　　1.2重復數(shù)據(jù)刪除的定義、分類- 1 -</p><p>　　1.3重復數(shù)據(jù)刪除技術的國內外現(xiàn)狀- 2 -</p><p>　　1.3.1國外現(xiàn)狀- 2 -</p><p>　　1.3.2國內狀況- 3 -</p><p>　　1.4主要任務和目

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

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

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

13、lt;/p><p>　　3.5 新文件的指紋以及已分數(shù)據(jù)塊Hash值的保存- 11 -</p><p>　　4 重復數(shù)據(jù)刪除技術的應用- 12 -</p><p>　　4.1重復數(shù)據(jù)刪除的主要應用特點- 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遠程災備系統(tǒng)- 13 -</p><p>　　4.2重復數(shù)據(jù)刪除技術的實踐例證- 13 -</p><p>　　4.3刪除備份數(shù)據(jù)重復部分- 14 -</p><p>　　4.4不能脫離存儲系統(tǒng)單獨使用- 14 -</p><p>　　4.5重復數(shù)據(jù)刪除技術的主要不足

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

40、代表的數(shù)據(jù)塊，否則存儲新的數(shù)據(jù)塊。</p><p><b>　?。募?lt;/b></p><p>　　SHA-1 HashSHA-1 Hash SHA-1 Hash</p><p><b>　　否</b></p><p><b>　　是</b></p>

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

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

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

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

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

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

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

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

49、></p><p><b>　　校驗</b></p><p><b>　　否</b></p><p><b>　　是</b></p><p><b>　　否</b></p><p>　　圖2-3 滑動塊檢測技術</p&

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

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

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

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

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

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

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

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

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

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

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

61、文件，則用Rabin指紋算法來對新文件進行掃描分塊，計算數(shù)據(jù)塊的Hash值，并與已有的文件指紋庫和相對應的偏移位置進行比較。標記所有發(fā)生了變化的數(shù)據(jù)塊；</p><p>　?。?）如果變化的數(shù)據(jù)量小或者帶寬充足，則直接同步對應的數(shù)據(jù)塊內容即可，如圖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>　　假設文件A在初始狀態(tài)( S1)生成了備份文件A′，當文件A

63、發(fā)生插入修改( S2, S3) ,刪除修改后( S4) ，生成新備份文件A″：</p><p>　　（1）文件A′根據(jù)Rabin 指紋算法,生成6個指紋，文件被劃分為7個數(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指紋計算，為一個chunk (未產(chǎn)生新的指紋) ，僅需傳輸C8數(shù)據(jù)塊，在服務端更新版本庫和指紋庫，得到A″；</p><p>　?。?）插入修改,如S3所示,如果插入的數(shù)據(jù)導致原來一個chunk劃分為兩個chunk，僅需傳輸C9和C10 兩個數(shù)據(jù)塊，在服務端更新版本庫和指紋庫,得到A″；</p><p>　?。?）刪除修改,如S4所示，如果刪除的數(shù)據(jù)塊影響了一個指紋，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

89、gt;<p><b>　　參考文獻</b></p><p>　　[1]程菊生.重復數(shù)據(jù)刪除技術的研究[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消息摘要算法實現(xiàn)及改進[J].福建電腦,2007,(4):92-93.</p><p>　　[4] 顏軍.重復數(shù)據(jù)刪除帶來集群架構革命[J].計算機世界·技術與應用,20

91、08,6(24):40-41.</p><p>　　[5] 范濤.網(wǎng)絡存儲技術的研究與應用[J].福建電腦,2008,(6):90-93.</p><p>　　[6] 佟樂.重復數(shù)據(jù)刪除的前世今生[J].福建電腦，2007,(4):92-93.</p><p>　　[7] 蔡盛鑫.一種基于重復數(shù)據(jù)刪除的備份系統(tǒng)[D].北京郵電大學碩士論文，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] 敖莉,舒繼武,李明強.重復數(shù)據(jù)刪除技術[J].軟件學報,2010,5(21):916-929. </p><p

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

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

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

98、p>　　班　　級:　　　 　　 </p><p>　　學　 號:　　 　　 　　 </p><p>　　姓　 名:　　　 　 </p><p>　　指導教師:　　　 　　

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

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

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

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

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

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

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

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

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