重復(fù)數(shù)據(jù)刪除技術(shù)的核心理念就是：在存儲(chǔ)數(shù)據(jù)時(shí)檢查和比較已存在的數(shù)據(jù)，如果它們是相同的，那么就過濾掉這部分?jǐn)?shù)據(jù)的備份，然后通過指針引用已存在的數(shù)據(jù)。重復(fù)數(shù)據(jù)刪除目前是存儲(chǔ)領(lǐng)域一個(gè)比較熱門的研究課題，因?yàn)樗芙o整個(gè)存儲(chǔ)系統(tǒng)甚至是整個(gè)企業(yè)帶來很多明顯的好處。顯然，重復(fù)數(shù)據(jù)刪除可以從根本上減少存儲(chǔ)占用的空間和用戶的磁盤驅(qū)動(dòng)器數(shù)量，減輕人力、能源、電力資源等方面的開銷，從而大幅度的節(jié)約存儲(chǔ)成本。另外，重復(fù)數(shù)據(jù)刪除可以減少在網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)量，進(jìn)而降低能量消耗和網(wǎng)絡(luò)成本，并為數(shù)據(jù)復(fù)制大量節(jié)省網(wǎng)絡(luò)帶寬。

工業(yè)界產(chǎn)品往往注重強(qiáng)調(diào)處理重復(fù)數(shù)據(jù)刪除的時(shí)間，這樣的劃分可以將處理時(shí)機(jī)分為兩類：同步處理和異步處理，也成為在線處理和離線處理。

所謂同步方式，就是當(dāng)大量的備份數(shù)據(jù)流到達(dá)具備重復(fù)數(shù)據(jù)刪除功能的備份設(shè)備時(shí)，首先駐留在內(nèi)存里，然后重復(fù)數(shù)據(jù)刪除引擎對(duì)先到的備份數(shù)據(jù)進(jìn)行辨識(shí)，判斷是否存在已被保存過的數(shù)據(jù)塊。如果有，則寫入一個(gè)指針來代替實(shí)際數(shù)據(jù)塊的寫入過程;如果沒有，則直接寫入該新數(shù)據(jù)塊，從而完成數(shù)據(jù)備份過程。而異步方式則不同。它是當(dāng)備份服務(wù)器開始向備份設(shè)備傳輸備份數(shù)據(jù)流時(shí)，將整個(gè)備份數(shù)據(jù)量作為一個(gè)整體來傳送，然后再啟動(dòng)單獨(dú)的進(jìn)程開始讀取已寫入磁盤的數(shù)據(jù)塊，從這開始重復(fù)數(shù)據(jù)刪除處理過程。如果讀入的數(shù)據(jù)塊和已存儲(chǔ)的數(shù)據(jù)塊重復(fù)，則用指針替代該數(shù)據(jù)塊，如果沒有重復(fù)，則將該新數(shù)據(jù)塊留在磁盤上。也就是說，前者是在數(shù)據(jù)備份的同時(shí)對(duì)其實(shí)施操作，后者是在數(shù)據(jù)被寫入磁盤后才開始實(shí)施操作。如此一來，兩種方式在整個(gè)數(shù)據(jù)備份過程中所花的時(shí)間就有所差異。

雖然同步處理可以縮短數(shù)據(jù)備份的時(shí)間，但對(duì)CPU 及網(wǎng)絡(luò)資源的占用非常大，所以，用戶在實(shí)際的應(yīng)用中必須仔細(xì)地進(jìn)行調(diào)優(yōu)處理，保證重復(fù)數(shù)據(jù)刪除速度足夠快，從而不至于造成進(jìn)入備份設(shè)備的數(shù)據(jù)流擁塞。另外，同步重復(fù)數(shù)據(jù)刪除方式對(duì)于實(shí)施重復(fù)數(shù)據(jù)刪除的硬件平臺(tái)性能要求很高，對(duì)于數(shù)據(jù)一致性和整體系統(tǒng)的擴(kuò)展性也存在較高的要求。

與工業(yè)界不同，學(xué)術(shù)界在提到重復(fù)數(shù)據(jù)刪除時(shí)，更多的是去關(guān)注檢測(cè)重復(fù)數(shù)據(jù)的方法。粗略的劃分，可以將檢測(cè)方法分為兩類：基于相同數(shù)據(jù)的檢測(cè)和基于相似數(shù)據(jù)的檢測(cè)，也可以稱為精確去重和近似去重。

基于相同數(shù)據(jù)的檢測(cè)是指將存儲(chǔ)系統(tǒng)中的數(shù)據(jù)按照文件級(jí)別或者數(shù)據(jù)塊級(jí)別劃分后，利用文件或者數(shù)據(jù)塊的hash值來查找新來的數(shù)據(jù)與已存儲(chǔ)數(shù)據(jù)完全相同的文件或者數(shù)據(jù)塊。而基于相似數(shù)據(jù)檢測(cè)是指利用數(shù)據(jù)自身的相似性特點(diǎn)，通過相似性查找技術(shù)，挖掘出與新來數(shù)據(jù)相似的已存儲(chǔ)數(shù)據(jù)。在選定了相似得已存儲(chǔ)數(shù)據(jù)后，再進(jìn)行精確地重復(fù)比較，進(jìn)而減少存儲(chǔ)空間占用。

雖然重復(fù)數(shù)據(jù)刪除技術(shù)能夠縮小存儲(chǔ)占用空間,減少網(wǎng)絡(luò)傳輸帶寬,節(jié)省能源,但這項(xiàng)技術(shù)能夠應(yīng)用的前提是對(duì)原有系統(tǒng)的性能,可靠性等方面不會(huì)造成過大的影響。所以除了關(guān)注能夠如何檢測(cè)到重復(fù)數(shù)據(jù)之外,還需要關(guān)注對(duì)系統(tǒng)性能和可靠性方面的影響以及改進(jìn)技術(shù)。另外值得一提的是，重復(fù)數(shù)據(jù)刪除與編碼技術(shù)相結(jié)合，可以最小化壓縮相似數(shù)據(jù)，進(jìn)一步所見存儲(chǔ)空間和網(wǎng)絡(luò)帶寬的占用。

1. 基于相同數(shù)據(jù)的檢測(cè)

1.1 文件級(jí)別相同

文件級(jí)別的基于相同數(shù)據(jù)檢測(cè)重復(fù)是在文件粒度級(jí)別查找重復(fù)數(shù)據(jù)的方法。存儲(chǔ)系統(tǒng)中，通常是以文件作為一個(gè)信息集合的單位，所以重復(fù)數(shù)據(jù)刪除技術(shù)出現(xiàn)的初期想到基于文件比較重復(fù)數(shù)據(jù)。對(duì)于已經(jīng)存儲(chǔ)在存儲(chǔ)系統(tǒng)中的文件，會(huì)先計(jì)算出它們各自的hash 函數(shù)值(通常用MD5 或SHA-1)，并將這些hash 函數(shù)值組織成hash 函數(shù)值庫(kù), 單獨(dú)存儲(chǔ)起來。這里應(yīng)用重復(fù)數(shù)據(jù)刪除功能的前提是: 應(yīng)用本身會(huì)有很多重復(fù)的數(shù)據(jù)，否則由于多存儲(chǔ)了文件的hash 函數(shù)值，實(shí)際是浪費(fèi)了存儲(chǔ)空間。

當(dāng)有新的準(zhǔn)備存儲(chǔ)的文件到達(dá)存儲(chǔ)系統(tǒng)以后，會(huì)首先計(jì)算這些新文件的hash 函數(shù)值。將得到的hash 函數(shù)值與已經(jīng)存儲(chǔ)與hash 函數(shù)值庫(kù)中的值進(jìn)行比較。如果發(fā)現(xiàn)兩者有相同的hash 函數(shù)值，就判定為兩個(gè)相同的文件，只需要用指向已存儲(chǔ)文件的指針代替新的準(zhǔn)備存儲(chǔ)的文件即可。如果發(fā)現(xiàn)新的準(zhǔn)備存儲(chǔ)的文件hash 函數(shù)值不在hash 函數(shù)值庫(kù)中，則可以判定該文件沒有在存儲(chǔ)系統(tǒng)中，除了將文件存儲(chǔ)起來之外，還要更新hash 函數(shù)值庫(kù)，將新的文件hash 函數(shù)值添加進(jìn)去。文件級(jí)別的相同數(shù)據(jù)檢測(cè)過程如下圖所示：

圖 文件級(jí)別的基于相同數(shù)據(jù)檢測(cè)

經(jīng)典文獻(xiàn)

u Single instance storage in Windows 2000

Bolosky WJ, Corbin S, Goebel D, Douceur JR. In: Proc. of the 4th Usenix Windows System Symp. Berkeley: USENIX Association, 2000. 13?24.

Windows 2000的單一實(shí)例存儲(chǔ)(SIS)是作為支持遠(yuǎn)程安裝服務(wù)的一個(gè)組件。由于遠(yuǎn)程安裝中不同的machine image可能存在很多重復(fù)文件，所以Windows 2000可以用這項(xiàng)功能節(jié)省空間。

SIS 主要由兩部分實(shí)現(xiàn)：內(nèi)核級(jí)的文件系統(tǒng)過濾器，用于管理復(fù)制、修改和歸并文件;用戶級(jí)的數(shù)據(jù)檢測(cè)器，用于搜索需要?dú)w并的相同文件。如下所示。

圖 Windows SIS 實(shí)現(xiàn)原理圖

用戶態(tài)下的數(shù)據(jù)檢測(cè)器用每個(gè)文件的128位摘要進(jìn)行檢測(cè)，摘要的前64位代表文件的大小。事實(shí)上，用64位表征文件大小的開銷并不大，但它顯然不能區(qū)分相同大小的不同文件。摘要的后64位是用文件的一部分計(jì)算出的hash函數(shù)值。過濾器從文件中部截取兩個(gè)4KB的數(shù)據(jù)塊計(jì)算它們的hash函數(shù)值。如果文件小于或者等于8KB，則直接用全文件計(jì)算。用戶級(jí)檢測(cè)文件系統(tǒng)的變化，維護(hù)一個(gè)文件hash值的數(shù)據(jù)庫(kù)用來檢測(cè)重復(fù)文件，然后將檢測(cè)到的重復(fù)文件報(bào)告給過濾器。如果兩個(gè)文件的摘要相同，數(shù)據(jù)檢測(cè)器會(huì)進(jìn)行仔細(xì)的二進(jìn)制比較。

內(nèi)核態(tài)下SIS是位于NTFS文件系統(tǒng)之上的一層過濾器，負(fù)責(zé)管理數(shù)據(jù)檢測(cè)器檢測(cè)出的硬盤卷上的重復(fù)數(shù)據(jù)。發(fā)現(xiàn)重復(fù)的文件時(shí)，SIS過濾器首先將文件拷貝到SIS公共存儲(chǔ)區(qū)域中，接著將原文件位置用一個(gè)指向公共存儲(chǔ)區(qū)域的鏈接代替。當(dāng)用戶進(jìn)程試圖讀一個(gè)普通文件時(shí)，SIS過濾器將文件的去寫請(qǐng)求重定向到SIS公共存儲(chǔ)區(qū)域目錄。當(dāng)用戶進(jìn)程想寫一個(gè)文件時(shí)，SIS采用copy-on-close策略。Copy-on-close策略和我們熟悉的copy-on-write策略不同。復(fù)制操作不是在第一次寫操作的時(shí)候執(zhí)行，而是延遲到關(guān)于這個(gè)文件的所有更新操作都完成時(shí)才執(zhí)行，并且只有新的數(shù)據(jù)才會(huì)被拷貝到公共存儲(chǔ)空間。也就是說當(dāng)文件在公共存儲(chǔ)區(qū)域中有副本時(shí)，SIS的復(fù)制操作開銷其實(shí)很小，只有SIS鏈接和新的數(shù)據(jù)。通過對(duì)具有20個(gè)不同Windows NT映像的服務(wù)器進(jìn)行測(cè)試，結(jié)果表明共節(jié)省了58% 的存儲(chǔ)空間。

文件級(jí)別的相同數(shù)據(jù)檢測(cè)可以檢測(cè)出不同文件名的相同文件，也可以檢測(cè)出不同目錄下的相同文件，運(yùn)算快速，便于實(shí)現(xiàn)。但由于hash函數(shù)的雪崩性，兩個(gè)相似的文件即使只有一個(gè)字節(jié)不同，計(jì)算出來的hash函數(shù)值也會(huì)完全不同，因此文件之間依然會(huì)存在大量的重復(fù)數(shù)據(jù)。為了解決這個(gè)問題，研究者們提出了基于數(shù)據(jù)塊級(jí)別的重復(fù)數(shù)據(jù)檢測(cè)。