[發明專利]一種基于統一采樣的快速相似數據檢測方法

有效

• 申請號: 201910243356.0
• 申請日: 2019-03-28
• 公開（公告）號: CN110083743B
• 公開（公告）日: 2021-11-16
• 發明（設計）人: 夏文;王軒
• 申請（專利權）人: 哈爾濱工業大學（深圳）
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京集佳知識產權代理有限公司 11227
• 代理人: 王學強

本發明提供了一種基于統一采樣的快速相似數據檢測方法，包括以下步驟：A、基于滑動窗口算法快速計算哈希集合；B、對計算得出的哈希集合進行快速統一采樣；C基于采樣后的哈希集合，再提取相似性特征值和超級特征值用于相似性匹配查找。本發明的有益效果是：在保持原有的相似性檢測效率的前提下，通過快速滑動哈希計算，以及通過統一采樣方法大幅度地減少了需要線性變換的指紋數量，從而簡化了后面的提取特征值和超級特征值的計算，最終大幅度提升相似數據檢測速度，以實現面向大規模存儲系統的快速高效的相似數據檢測效果。

技術領域

本發明涉及相似數據檢測方法，尤其涉及一種基于統一采樣的快速相似數據檢測方法。

背景技術

近年來，隨著計算機技術和網絡的發展普及，全球的數據信息存儲量呈爆炸式增長的趨勢。雖然存儲設備的售價一直在不停地下降，但也遠遠趕不上數據擴張增長的速度。數據消冗(或稱冗余數據消除)作為一種通過大規模地有效地消除冗余數據的技術，成為了近年來存儲系統研究的熱點。冗余數據消除不僅能夠大量地節省了存儲空間以及提高存儲系統性能，而且通過避免冗余數據傳輸而節省了網絡帶寬。冗余數據消除技術的興起源于存儲市場中的大量數據備份和歸檔的需求，而需求帶動了研發與產品化，IBM、HP、EMC、NEC、Microsoft這些存儲大公司都瞄準了數據消冗市場，開發出了一系列的數據消冗產品。一般而言，通過有效地檢測并消除存儲系統中的冗余數據，可以實現數倍甚至是數十倍地節省存儲空間的效果。

面向存儲系統的數據消冗技術包括數據去重和差量壓縮，其中差量壓縮主要負責處理相似數據消冗。比如兩個數據塊A1和A2僅幾個字節不同的情況，差量壓縮技術通過計算數據塊A1和A2的差量，實現節省存儲空間的目的。具體而言，差量壓縮是一項高效的數據壓縮技術，它能夠根據引用數據塊A_r對其相似數據塊A_i進行高度壓縮。數據塊的相似度越高，則壓縮效率越高。如公式所示，把A_r和A_i輸入Delta算法器，Delta算法器會輸出一個差量數據△_r,i代表文件A_i的壓縮版本。如需要解壓數據A_i，則讀取差量數據和引用數據塊A_r即可以計算得出數據A_i。

但是把差量壓縮技術結合到存儲系統中不那么簡單，主要的挑戰是需要先確定對哪些數據進行差量壓縮，即如何查找相似的數據。現有的相似數據查找方法具有計算速度慢，可擴展性差等缺點，現在常用的相似性特征值提取方法計算帶寬只有幾十MB/s，這嚴重限制了差量壓縮算法的推廣和發展。

原始的方案基于全局掃描數據塊的特征值(假設數據塊的長度為N)，具體采用基于滑動窗口的技術，針對每個窗口算法Rabin哈希值，這樣就產生了N個Rabin值，同時對著N個Rabin值進行M次線性變換，獲得M維Rabin值，然后對這M維的數據進行特征值提取(一般來說是提取最大值)，這樣就獲得了M個特征值，然后對這M個特征值進行組合就獲得了超級特征值。

如下公式給出了具體計算案例：

SuperFearture_k＝Rabin(Feature₁,Feature₂,...) (4)

這里Feature_i指的就是相似性特征值，SuperFeature_k指的是超級特征值，Rabin(W_j)表示滑動窗口W_j的Rabin指紋，m_i和a_i表示預定的隨機數；在這里數據塊的長度為N，所以該數據塊有N個滑動窗口，相似性特征值Feature就是在這N個滑動窗口的Rabin指紋中取哈希最大值。不同預定值m_i和a_i就會產生不同相似性特征值。