[發明專利]一種基于局部性優化的重復數據檢測方法

有效

• 申請號: 201710555589.5
• 申請日: 2017-07-07
• 公開（公告）號: CN107391034B
• 公開（公告）日: 2019-05-10
• 發明（設計）人: 王樺;周可;張攀峰
• 申請（專利權）人: 華中科技大學
• 主分類號: G06F3/06
• 分類號: G06F3/06
• 代理公司: 武漢臻誠專利代理事務所(普通合伙) 42233
• 代理人: 宋業斌

本發明公開了一種基于局部性優化的重復數據檢測方法，屬于計算機存儲技術領域，解決現有重復數據檢測方法中檢測效率低下的問題，以適應因存儲數據規模擴大，而導致重復數據檢測效率降低的現狀。本發明包括布隆過濾器檢測、哈希桶寫緩存檢測、哈希桶讀緩存檢測、哈希桶地址表檢測步驟。本發明主要針對局部性較強的數據集類型，通過挖掘數據集中的局部性，提高數據預取的效率，降低磁盤訪問開銷，提升數據去重的吞吐率。對于數據集中可能的重復數據，本發明首先利用布隆過濾器對數據塊的重復性進行預判，接下來根據不同的條件分別對緩存區的熱區及冷區及磁盤進行三級重復數據的檢測，充分利用重復數據中的局部性，提升重復數據的檢測效能。

技術領域

本發明屬于計算機存儲技術領域，更具體地，涉及一種基于局部性優化的重復數據檢測方法。

背景技術

隨著信息技術迅猛發展，信息已成為我們賴以生存的寶貴資源，成為了推動生產力快速發展的最大動力。信息技術的大量應用也伴隨著海量的數據的產生，越來越多有價值的數據需要進行存儲。那么，如何有效提高現有存儲介質的存儲效率，滿足不斷增長的存儲需求，已經成為存儲研究領域急迫解決的問題之一。同時，IDC公司調研報告顯示現存約75％的數據為冗余信息，即僅有25％的數據具有唯一性。在此背景下，數據去重作為在較大空間范圍內檢測和消除冗余信息的一種新型技術成為近幾年學術界和工業界的研究熱點，并正被愈加廣泛地應用到各種信息存儲系統。

重復指紋的檢測是實現數據去重的重要技術手段。在現有的數據去重技術中，重復數據的檢測主要是使用指紋檢測的方式，即通過提取數據塊的指紋(哈希值)，再通過檢測指紋的重復性來識別某個數據塊是否為重復數據塊。在基本重復指紋檢測方法中，通常采用單一的哈希表或B樹等數據結構來實現重復指紋段的識別。

然而，上述指紋檢測法存在的一個不可忽略的問題是，其檢測性能較為低下，無法針對大數據集實現有效的重復數據檢測，從而影響到數據去重的整體效能。

發明內容

針對現有技術的以上缺陷或改進需求，本發明提供了一種基于局部性優化的重復數據檢測方法，其目的在于，解決現有基于指紋檢測的重復數據檢測方法存在的檢測性能較為低下，無法針對大數據集實現有效的重復數據檢測的技術問題。

為實現上述目的，按照本發明的一個方面，提供了一種基于局部性優化的重復數據檢測方法，包括以下步驟：

(1)獲取指紋列表文件，從該指紋列表文件中獲取部分指紋并存儲在緩存中，從緩存中提取一個指紋；

(2)在布隆過濾器中查詢是否可能記錄有提取到的該指紋，如果可能記錄有，則轉入步驟(4)，否則轉入步驟(3)；

(3)將該指紋插入到布隆過濾器及哈希桶寫緩存(Buffer)中，并從緩存中提取下一個指紋，并返回步驟(2)；

(4)判斷哈希桶讀緩存的熱區中是否記錄有該指紋，如果有則從緩存中提取下一個指紋，并返回步驟(2)，否則轉入步驟(5)；

(5)判斷哈希桶寫緩存的熱桶中是否記錄有該指紋，如果有則從緩存中提取下一個指紋，并返回步驟(2)，否則轉入步驟(6)；

(6)根據指紋查找哈希桶地址表，以判斷能否獲取到對應的哈希桶ID，如果獲取不到則認定該指紋為新指紋，從緩存中提取下一個指紋，并返回步驟(2)，如果能獲取到則轉入步驟(7)；

(7)根據獲取的哈希桶ID遍歷哈希桶讀緩存的冷區中的所有哈希桶，以判斷是否有與該哈希桶ID對應的哈希桶，如果有對應的哈希桶，則在該哈希桶中查找該指紋，從緩存中提取下一個指紋，并返回步驟(2)，否則將該哈希桶ID對應的哈希桶從磁盤中插入到哈希桶讀緩存的熱區中的首個哈希桶中，并在插入后的哈希桶中查找該指紋，如果查找到則說明該指紋是現有指紋，如果查找不到則說明該指紋是新指紋，然后從緩存中提取下一個指紋，并返回步驟(2)。

優選地，布隆過濾器是在初始化階段創建，且有