Winnowing指紋串匹配的重復數據刪除算法
大?。?/span>0.95 MB 人氣： 2018-04-17 需要積分：1
標簽：指紋(23218)
目前數據激增問題使數據中心處理的數據量呈現爆炸式增長，數據存儲、備份和恢復所需的時間和容量也隨之增大，給存儲系統帶來了沉重的負擔。由于數據來源不同，許多數據被反復存儲，造成了大量的數據冗余，尤其在備份系統中更加突出。重復數據刪除技術的出現引起了研究者的關注，它不僅能夠減少存儲和處理的數據量，節約數據的管理和存儲成本，同時提高了網絡通信的速度，成為降低數據中心冗余數據量的有效手段。
為了在存儲系統中充分利用重復數據刪除技術，減少數據的最終積累量，縮短消除冗余數據的時間，許多經典的重復數據刪除算法被提出。EB（ Extreme Binning）算法。利用文件相似性，使用最小塊簽名作為文件的特征，只在內存中保存文件的代表塊ID，有效減小了內存占用。然而，最小塊ID作為主索引，一方面重刪率相對較低，另一方面數據分塊算法影響最小塊簽名，不同的分塊算法所產生的最小塊可能不同，從而影響重刪的準確性。Bloom filter算法利用K個Hash函數將數據塊MD5值映射到m位的向量y中，減少頻繁的I/O操作，但存在假正例（ False Positives）誤識別率，并且無法從Bloom Filter榘合中刪除元素，在需要數據修改的場景下不能使用。張滬寅等提出了用戶感知的重復數據刪除算法，根據用戶相關度，以用戶為單位，減少了數據空間局部性，但對于非人為產生的數據，其相似性計算準確度較低。
以上算法在數據分塊時均采用了可變長度分塊（ Content-Defined Chunking，CDC）算法，相對于以文件為粒度，數據塊級粒度能夠檢測到文件內部的重復數據，因此，目前大多數重復數據刪除算法均采用數據塊為粒度。
非常好我支持^.^
(0) 0%
不好我反對
(0) 0%