第 1 章 緒論

1.1 研究背景

網(wǎng)絡信息技術等計算機新興科技不但促進了國民經(jīng)濟各個領域的蓬勃發(fā)展，同時也推進了相應軟硬件系統(tǒng)全面步入信息化、智能化時代。隨著這些技術逐漸融入到社會生活中的各個角落里，大數(shù)據(jù)時代在全球數(shù)字化浪潮帶來的海量信息數(shù)據(jù)逐漸推動下也越來越清晰地步入全球的視野。據(jù) IDC 研究指出[1]，2006 年個人用戶數(shù)據(jù)已經(jīng)進入 TB 級的時代，從 2006 年到 2010 年，數(shù)據(jù)每年以 57%的速度持續(xù)增長，2011 年，全球的數(shù)據(jù)量已經(jīng)進入以 ZB 為單位的時代，全世界使用的數(shù)據(jù)總量超過1.8ZB。IDC調查稱，2020年全球數(shù)據(jù)總量甚至將會超過40ZB，大數(shù)據(jù)時代越來越清晰，同時其數(shù)據(jù)種類多(Variety)，數(shù)據(jù)量大(Volume)，價值密度低(Value)，處理速度快(Velocity)的四大特性也逐漸被大家所熟知[2]。

...............

1.2 課題研究內(nèi)容

當前各企業(yè)廠商和研究機構為了能節(jié)省磁盤等硬件成本開銷同時又能提高存儲空間的利用率提出了重復數(shù)據(jù)刪除技術的概念。重復刪除技術實質上是一種有效的數(shù)據(jù)壓縮技術，用來刪除存儲系統(tǒng)中存在的大量冗余數(shù)據(jù)，以降低磁盤 I/O開銷，提高系統(tǒng)資源利用率。目前國內(nèi)外很多研究組織和企業(yè)都在對其進行研究，并且取得了非常明顯的成果，LBFS[7]是一種由麻省理工學院開發(fā)的網(wǎng)絡文件系統(tǒng)，其目標在于降低數(shù)據(jù)傳輸對帶寬的占用，在傳輸之前判斷數(shù)據(jù)塊是否已經(jīng)在于目標服務器上，如果已經(jīng)存在則無需重復發(fā)送數(shù)據(jù)塊。此外，LBFS 使用 SHA1 值的前 64 位作數(shù)據(jù)塊指紋索引，是有一定指紋沖突的可能；Venti 系統(tǒng)[8]是美國貝爾實驗室設計和研發(fā)的用于數(shù)據(jù)歸檔的網(wǎng)絡存儲系統(tǒng)，但它綁定到 Plan9 操作系統(tǒng)上，因此不能用于諸如 Linux，Windows 等系統(tǒng)環(huán)境中，Venti 以固定大小的數(shù)據(jù)塊作為存儲基本單位，并且計算每個數(shù)據(jù)塊的 SHA1 值作為塊數(shù)據(jù)指紋，最后利用速度比較塊的哈希運算檢測判斷重復數(shù)據(jù)。

...............

第 2 章 重復數(shù)據(jù)檢測方法

2.1 重復數(shù)據(jù)去重原理

重復數(shù)據(jù)刪除（DataDeduplication）是一種單一對象存儲或智能數(shù)據(jù)壓縮技術，它利用哈希值來判斷內(nèi)容相同的數(shù)據(jù)，對那些相同內(nèi)容的數(shù)據(jù)只存儲其唯一一份對象，對這個對象的其他重復數(shù)據(jù)使用指向唯一副本的指針來代替[8]，通過此種方式消除重復冗余的數(shù)據(jù)、提高存儲空間使用率，圖 2.1 具體展示了這一原理。而學術界給出了重復數(shù)據(jù)刪除技術的精確定義，基于數(shù)據(jù)自身冗余度來檢測數(shù)據(jù)流中存在的相同數(shù)據(jù)，然后只存儲和傳輸唯一的數(shù)據(jù)對象，最終使用指向唯一數(shù)據(jù)對象副本的指針替換其中的重復副本[9]。

...............

2.2 重復數(shù)據(jù)檢測方法

對于重復數(shù)據(jù)檢測技術來講，按照不同的標準，可以分為不同的處理方式。最為廣泛的分類方式是以檢測的粒度大小劃分，再有是根據(jù)去重操作發(fā)生的時機來劃分用于評價重復數(shù)據(jù)刪除技術優(yōu)劣的指標有兩個，一個是重復數(shù)據(jù)刪除率，另外一個是執(zhí)行性能。想要取得相對更高的重復數(shù)據(jù)刪除率則需要以犧牲一定執(zhí)行性能為代價，操作的粒度越精細，檢測的重復數(shù)據(jù)就越多，能節(jié)省的存儲空間就越大。

...............

第 3 章 數(shù)據(jù)指紋計算................14

3.1 單向散列函數(shù)..................14

3.2 MD5 哈希函數(shù)................16

第 4 章 指紋索引策略................27

4.1 數(shù)據(jù)去重的指紋索引研究................27

4.2 基于局部性的索引技術.................28

第 5 章 基于 SHA3 算法和兩級索引的雙端去重檢測框架.................36

5.1 TLDM 方法原理 .................36

5.2 TLDM 架構 ................36

第 6 章 TLDM 在 Hadoop 平臺中的應用

6.1 實驗環(huán)境和數(shù)據(jù)集

本文使用三臺機器搭建的 Hadoop 集群環(huán)境，每個節(jié)點的操作系統(tǒng)都是Ubuntu12.04，三個節(jié)點中有一個同時運行 NameNode 和 DataNode 進程，其余兩個節(jié)點只存在 DataNode 進程，每臺機器的配置如表 6.1 所示。本文采用 Rabin 指紋算法對每一個待處理的文件進行按內(nèi)容分塊，且設定數(shù)據(jù)塊的平均大小為 4KB。除此之外，設定數(shù)據(jù)塊大小最小為 2K，最大為 64KB，。對于重復的文件無需再次上傳，而在對非重復 SSH 文件進行分塊之前，先確定文件的大小，對于小于 2K 的小文件不做分塊處理，而是將整個文件作為一個塊處理，這樣可以減少對這些小文件進行數(shù)據(jù)分塊過程的時間開銷。而對于文件指紋以及數(shù)據(jù)塊指紋的計算都采用 SHA3 哈希算法。

...............

6.2 實驗結果與分析

在比較數(shù)據(jù)集所需的存儲空間時，使用三種方法：無去重措施、在線 EB 檢測，本文的客戶-服務端雙重檢測，分別用 No-Dedup、EB-Dedup 和 CS-Dedup 表示。圖 6.2 和圖 6.3 所示為采用不同方法時，Dataset I 和 Dataset II 所占的存儲空間比較�？梢钥闯觯翰捎萌我庖环N去重處理后，數(shù)據(jù)集所占的存儲空間明顯減少，尤其在數(shù)據(jù)量增大時，存儲空間利用率大大提高；而且 CS-Dedup 相比EB-Dedup 能夠節(jié)省更多的存儲空間，因為 CS-Dedup 相當于在 EB-Dedup 之上又做了一次服務端的全局查重。不過圖 6.3 中 CS-Dedup 相比 EB-Dedup 去重率提高不大，其原因是數(shù)據(jù)集中大多數(shù)重復數(shù)據(jù)通過 EB 即可得到確認，即能在客戶端檢測到大部分的重復數(shù)據(jù)，，只有少數(shù)副本需要通過服務端的全局確認。

...............

結論

無論是在個人 PC 機、備份、歸檔系統(tǒng)還是在分布式文件系統(tǒng)里，都存在一定量的數(shù)據(jù)是重復存儲的，而加之當前信息飛速發(fā)展帶來數(shù)據(jù)規(guī)模的急劇增大，如何充分利用系統(tǒng)的存儲資源，去除這些重復數(shù)據(jù)愈加顯得重要和迫切。本文的目的是通過研究國內(nèi)外重復數(shù)據(jù)去重領域研究現(xiàn)狀，結合以往相關經(jīng)典算法并提出一種擴展性強、去重率高的客戶-服務端雙端去重框架-TLDM。首先，本文分析了當前大數(shù)據(jù)環(huán)境下給數(shù)據(jù)存儲帶來的一系列問題，重點講到了云存儲環(huán)境重復數(shù)據(jù)冗余存儲的客觀現(xiàn)狀以及因此給企業(yè)和個人帶來的各種問題。其中闡述了國內(nèi)外重復數(shù)據(jù)刪除技術的主要方法，包括基于內(nèi)容識別的傳統(tǒng)去重方法和當代基于塊粒度的數(shù)據(jù)去重方法。并在后續(xù)內(nèi)容中對基于去重粒度的文件級、靜態(tài)分塊和按內(nèi)容分塊方法進行了重點敘述，這其中又對基于文件內(nèi)容的分塊技術進行更加細致的講解，該講解中涉及到了兩項重要技術，一個是滑動窗口的概念，另一個是 Rabin 指紋分塊方法。

參考文獻（略）