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

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

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

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

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

10、標- 3 -</p><p>　　1.5全篇論文的主要內容- 3 -</p><p>　　2 重復數據刪除技術- 4 -</p><p>　　2.1重復數據刪除的流程- 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對于數據塊進行Hash值計算- 7 -</p><p>　

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

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

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

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

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

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

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

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

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

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

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

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

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

25、<p>　　Rsync算法也有一定的缺陷:首先, Rsync使用固定分塊的方法，這種分塊方法對數據變化非常敏感，因為當文件內部數據有部分變化時，緊接著的一系列文件塊會跟著相應地改變。其次，其中對于數據相似性檢測的方法與文件目錄結構有關，所以倘若目錄結構有所改變，但相應文件內容未做修改，其也會當作新文件處理，產生多余的網絡流量。</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算法來實現變長分塊，該方法對文件數據變化不敏感，是一種基于內容的分塊方法，同時使用SHA-1（安全散列算法）值作為指示符，向服務器進行塊存儲校驗，以判斷數據塊是否已存儲，若已存在則不用發(fā)送數據塊，以此達到了減小傳輸帶寬的目的。</p

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

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

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

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

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

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

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

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

35、FSP）、可變分塊檢測技術（content-defined chunking，CDC）和滑動塊檢測技術，并給出了在變化的數據類型上使用這些方法所獲得的益處。</p><p>　　2.2.1 相同文件檢測技術</p><p>　　相同文件檢測技術(WFD)是在文件級別的粒度下查找重復數據的方法。該方法是通過對整個文件進行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值進行比較，對于較大的數據集，需要比較的范圍大，時間消耗也多；（2）即使不同文件內部存在很多相同的數據，也不能被檢測并實現冗余消除。</p><p>　　2.2.2 基于內容算法的檢測技術</p><p>　　基于內容識別的重復檢測技術的基本原理是對記錄的數據格式進行比對。在備份數據時,該技術會讀取數據并從中提取出每組備份集以及備份集中數據對象的元數據,存入到

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

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

40、代表的數據塊，否則存儲新的數據塊。</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ā)現，固定分塊檢測技術已應用在很多領域，并具有如下兩個特征：（1）縮減存儲空間：針對數據歸檔的網絡存儲系統(tǒng)Venti應用該技術減少了大約30%的存儲空間。（2）減少網絡傳輸的數據量：虛擬機優(yōu)化系統(tǒng)通過該技術加速了在低寬帶網絡上的數據傳輸并改進了內存的性能。</p><p>　　此外，固定分塊檢測技術還可以

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

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

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

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

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

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

48、前進。而且對于在先前的已經被劃分的塊和最近被檢測到冗余之前的這個碎片，需要被記錄并且存儲；（4）如果求和校驗值或Hash值不能匹配，則滑動窗口繼續(xù)向前。如果滑動窗口已經行駛了一個塊大小的距離，但是仍然無法匹配到任何已經被存儲的塊，則需要對這個塊進行求和校驗和S</p><p><b>　　．．．文件．．．</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>　　根據滑動塊技術的特性，我們可知該技術的特點是對于插入問題和刪除問題處理高效，并能始終檢測到更多的冗余數據。（1）插入問題：如果一小部分字節(jié)被插入到一個對象中，只有周圍的塊會改變，接下來的塊將仍然會被識別出來并被該算法匹配，并且一個長度等于插入的字節(jié)數的碎片會被產生出來。（2）刪除問題：刪除一小部分字節(jié)也會產生一個長度等于塊大小減去被刪除部分字節(jié)長度的碎片，其它的塊不受影響。但該技術也存在一個不足：在插入和

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

74、量，提高傳輸數據速度，例如飛康的MicroScan軟件就采用了該技術。</p><p>　　4.2 重復數據刪除技術的實踐例證</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)都流動著非常重要的數據，因此，數據備份是一件及其重要的工作。</p><p>　　根據每個應用系統(tǒng)的不同要求，有的需要每天備份，保留最少7天的數據；有的需要每天備份，保留一年的數據；有的需要分別保留最近12個月、最近四周和最近7天的數據。</p><p>　　隨著人民銀行業(yè)務信息系統(tǒng)的不斷升級和完善，數據保護問題面臨著越來越大的挑戰(zhàn)。各業(yè)務系統(tǒng)的數據采用分散的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

91、08,6(24):40-41.</p><p>　　[5] 范濤.網絡存儲技術的研究與應用[J].福建電腦,2008,(6):90-93.</p><p>　　[6] 佟樂.重復數據刪除的前世今生[J].福建電腦，2007,(4):92-93.</p><p>　　[7] 蔡盛鑫.一種基于重復數據刪除的備份系統(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] 敖莉,舒繼武,李明強.重復數據刪除技術[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存儲的網絡容災技術

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

97、/p><p><b>　　文獻綜述</b></p><p>　　題　 目: 　 重復數據刪除中的可變分塊算法 </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>　　在存儲備份過程存在大量內容相同的數據，將這些內容相同的數據刪除，只保留其中一份。這種技術稱為重復數刪除技術。重復數據刪除技術的宗旨就是為企業(yè)用戶提供重復數據的備份解決方案，增加有效存儲空間

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

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

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

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

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

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

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

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