Winnowing指紋串匹配的重復(fù)數(shù)據(jù)刪除算法

　　目前數(shù)據(jù)激增問題使數(shù)據(jù)中心處理的數(shù)據(jù)量呈現(xiàn)爆炸式增長(zhǎng)，數(shù)據(jù)存儲(chǔ)、備份和恢復(fù)所需的時(shí)間和容量也隨之增大，給存儲(chǔ)系統(tǒng)帶來了沉重的負(fù)擔(dān)。由于數(shù)據(jù)來源不同，許多數(shù)據(jù)被反復(fù)存儲(chǔ)，造成了大量的數(shù)據(jù)冗余，尤其在備份系統(tǒng)中更加突出。重復(fù)數(shù)據(jù)刪除技術(shù)的出現(xiàn)引起了研究者的關(guān)注，它不僅能夠減少存儲(chǔ)和處理的數(shù)據(jù)量，節(jié)約數(shù)據(jù)的管理和存儲(chǔ)成本，同時(shí)提高了網(wǎng)絡(luò)通信的速度，成為降低數(shù)據(jù)中心冗余數(shù)據(jù)量的有效手段。

　　為了在存儲(chǔ)系統(tǒng)中充分利用重復(fù)數(shù)據(jù)刪除技術(shù)，減少數(shù)據(jù)的最終積累量，縮短消除冗余數(shù)據(jù)的時(shí)間，許多經(jīng)典的重復(fù)數(shù)據(jù)刪除算法被提出。EB（ Extreme Binning）算法。利用文件相似性，使用最小塊簽名作為文件的特征，只在內(nèi)存中保存文件的代表塊ID，有效減小了內(nèi)存占用。然而，最小塊ID作為主索引，一方面重刪率相對(duì)較低，另一方面數(shù)據(jù)分塊算法影響最小塊簽名，不同的分塊算法所產(chǎn)生的最小塊可能不同，從而影響重刪的準(zhǔn)確性。Bloom filter算法利用K個(gè)Hash函數(shù)將數(shù)據(jù)塊MD5值映射到m位的向量y中，減少頻繁的I/O操作，但存在假正例（ False Positives）誤識(shí)別率，并且無法從Bloom Filter榘合中刪除元素，在需要數(shù)據(jù)修改的場(chǎng)景下不能使用。張滬寅等提出了用戶感知的重復(fù)數(shù)據(jù)刪除算法，根據(jù)用戶相關(guān)度，以用戶為單位，減少了數(shù)據(jù)空間局部性，但對(duì)于非人為產(chǎn)生的數(shù)據(jù)，其相似性計(jì)算準(zhǔn)確度較低。

　　以上算法在數(shù)據(jù)分塊時(shí)均采用了可變長(zhǎng)度分塊（ Content-Defined Chunking，CDC）算法，相對(duì)于以文件為粒度，數(shù)據(jù)塊級(jí)粒度能夠檢測(cè)到文件內(nèi)部的重復(fù)數(shù)據(jù)，因此，目前大多數(shù)重復(fù)數(shù)據(jù)刪除算法均采用數(shù)據(jù)塊為粒度。