圖 文件級(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è)。

huanghui