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

有效

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

1.一種基于局部性優化的重復數據檢測方法，其特征在于，包括以下步驟：

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

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

(3)將該指紋插入到布隆過濾器及哈希桶寫緩存中，并從緩存中提取下一個指紋，并返回步驟(2)；其中將該指紋插入到布隆過濾器及哈希桶寫緩存中具體為：(a)計算k個獨立哈希函數的值hash_i(X)，并將對位向量中偏移量為hash_i(X)的比特位單元置1，其中k為哈希函數個數，1≤i≤k；(b)輪流檢測哈希桶寫緩存中的兩條哈希桶列表，判斷某條列表中是否有未滿的桶，當發現未滿桶時，將指紋存入首個未滿桶，此時該哈希桶被稱為熱桶，并將該指紋和該哈希桶的哈希桶ID寫入哈希桶地址表中；如果發現某條列表中所有哈希桶都已裝滿，則將該列表鎖定，并將該列表中的所有哈希桶寫入磁盤中，寫完成后對該列表進行清空和解鎖的操作，其中對列表進行清空操作就是將該列表中的所有哈希桶清空，并為每個哈希桶分配新的哈希桶ID；如果兩條列表中所有桶都已經裝滿，則指紋插入操作必須等待某條列表寫入完成并清空后再執行插入操作；

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

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

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

(7)根據獲取的哈希桶ID遍歷哈希桶讀緩存的冷區中的所有哈希桶，以判斷是否有與該哈希桶ID對應的哈希桶，如果有對應的哈希桶，則在該哈希桶中查找該指紋，從緩存中提取下一個指紋，并返回步驟(2)，否則將該哈希桶ID對應的哈希桶從磁盤中插入到哈希桶讀緩存的熱區中的首個哈希桶中，并在插入后的哈希桶中查找該指紋，如果查找到則說明該指紋是現有指紋，如果查找不到則說明該指紋是新指紋，然后從緩存中提取下一個指紋，并返回步驟(2)；其中哈希桶讀緩存在邏輯上由兩部分構成，前面多個節點為熱區部分，而后邊到尾節點之間的部分為冷區。

2.根據權利要求1所述的重復數據檢測方法，其特征在于，布隆過濾器是在初始化階段創建，且有

布隆過濾器的最佳位向量大小m等于：

m＝log₂e×log₂(1/ε)×C

哈希函數個數為：

其中C表示重復數據塊索引容量，ε表示布隆過濾器的誤判率。

3.根據權利要求1所述的重復數據檢測方法，其特征在于，步驟(2)中判斷布隆過濾器中是否可能記錄有提取到的指紋X具體為，如果對于哈希函數hash_i(X)，有hash₁(X)&hash₂(X)...&hash_k(X)＝0，則表明布隆過濾器中沒有記錄過該指紋X，該指紋X為新指紋，否則表示可能記錄過該指紋X，其中1≤i≤k，k表示哈希函數的數量。

4.根據權利要求1所述的重復數據檢測方法，其特征在于，

哈希桶是用于放置指紋的容器，其取值是192至512條指紋/桶；

哈希桶寫緩存是在初始化階段通過在內存中申請空閑的內存空間來實現的，其取值等于4至128個哈希桶；

哈希桶寫緩存中設置有第一列表和第二列表，每個列表上的節點都由哈希桶構成。

5.根據權利要求1所述的重復數據檢測方法，其特征在于，步驟(4)中，哈希桶讀緩存是在初始化階段在內存中設置的緩存空間，其是由多個哈希桶構成的鏈表所組成，哈希桶讀緩存的大小為1024-2048個哈希桶。

6.一種基于局部性優化的重復數據檢測系統，其特征在于，包括：

第一模塊，用于獲取指紋列表文件，從該指紋列表文件中獲取部分指紋并存儲在緩存中，從緩存中提取一個指紋；

第二模塊，用于在布隆過濾器中查詢是否可能記錄有提取到的該指紋，如果可能記錄有，則轉入第四模塊，否則轉入第三模塊；

第三模塊，用于將該指紋插入到布隆過濾器及哈希桶寫緩存中，并從緩存中提取下一個指紋，并返回第二模塊；其中將該指紋插入到布隆過濾器及哈希桶寫緩存中具體為：(a)計算k個獨立哈希函數的值hash_i(X)，并將對位向量中偏移量為hash_i(X)的比特位單元置1，其中k為哈希函數個數，1≤i≤k；(b)輪流檢測哈希桶寫緩存中的兩條哈希桶列表，判斷某條列表中是否有未滿的桶，當發現未滿桶時，將指紋存入首個未滿桶，此時該哈希桶被稱為熱桶，并將該指紋和該哈希桶的哈希桶ID寫入哈希桶地址表中；如果發現某條列表中所有哈希桶都已裝滿，則將該列表鎖定，并將該列表中的所有哈希桶寫入磁盤中，寫完成后對該列表進行清空和解鎖的操作，其中對列表進行清空操作就是將該列表中的所有哈希桶清空，并為每個哈希桶分配新的哈希桶ID；如果兩條列表中所有桶都已經裝滿，則指紋插入操作必須等待某條列表寫入完成并清空后再執行插入操作；

第四模塊，用于判斷哈希桶讀緩存的熱區中是否記錄有該指紋，如果有則從緩存中提取下一個指紋，并返回第二模塊，否則轉入第五模塊；

第五模塊，用于判斷哈希桶寫緩存的熱桶中是否記錄有該指紋，如果有則從緩存中提取下一個指紋，并返回第二模塊，否則轉入第六模塊；

第六模塊，用于根據指紋查找哈希桶地址表，以判斷能否獲取到對應的哈希桶ID，如果獲取不到則認定該指紋為新指紋，從緩存中提取下一個指紋，并返回第二模塊，如果能獲取到則轉入第七模塊；

第七模塊，用于根據獲取的哈希桶ID遍歷哈希桶讀緩存的冷區中的所有哈希桶，以判斷是否有與該哈希桶ID對應的哈希桶，如果有對應的哈希桶，則在該哈希桶中查找該指紋，從緩存中提取下一個指紋，并返回第二模塊，否則將該哈希桶ID對應的哈希桶從磁盤中插入到哈希桶讀緩存的熱區中的首個哈希桶中，并在插入后的哈希桶中查找該指紋，如果查找到則說明該指紋是現有指紋，如果查找不到則說明該指紋是新指紋，然后從緩存中提取下一個指紋，并返回第二模塊；其中哈希桶讀緩存在邏輯上由兩部分構成，前面多個節點為熱區部分，而后邊到尾節點之間的部分為冷區。