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

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

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

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

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

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

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

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

1.1 文件級別相同

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

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

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

經(jīng)典文獻

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的單一實例存儲(SIS)是作為支持遠程安裝服務的一個組件。由于遠程安裝中不同的machine image可能存在很多重復文件，所以Windows 2000可以用這項功能節(jié)省空間。

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

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

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

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

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