第 1 章 緒論

1.1 研究背景

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

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

1.2 課題研究?jī)?nèi)容

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 基于局部性的索引技術(shù).................28

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

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

5.2 TLDM 架構(gòu) ................36

第 6 章 TLDM 在 Hadoop 平臺(tái)中的應(yīng)用

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

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

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

6.2 實(shí)驗(yàn)結(jié)果與分析

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

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

結(jié)論

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

參考文獻(xiàn)（略）