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

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

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

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

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

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

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

huanghui