[發明專利]一種云存儲中重復數據刪除的檢索算法

在審

• 申請號: 201610411080.9
• 申請日: 2016-06-12
• 公開（公告）號: CN106611035A
• 公開（公告）日: 2017-05-03
• 發明（設計）人: 范勇;胡成華
• 申請（專利權）人: 四川用聯信息技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

計算機存儲、云存儲中重復數據的刪除及檢索

背景技術

隨著信息技術和網絡技術的發展，大數據與海量數據已經成為數據中心的主要業務，而重復數據刪除與壓縮是可以節約大量數據存儲的技術。只有備份還不夠；重復數據刪除與壓縮即將成為主存儲的必備功能。重復數據刪除是一種壓縮技術，通過識別重復內容，進行去重，并在對應的存儲位置留下指針來最小化數據量；這個指針通過給定大小的數據模式進行哈希創建。目前只有少數主存儲陣列提供重復數據刪除作為產品的附加功能；對于租用云空間的用戶來說，大量重復數據充斥在云空間內，不僅對檢索造成麻煩，還浪費了寶貴的云資源，產生額外開銷，據報道，只有不到5％的磁盤陣列真正支持在線重復數據刪除與壓縮，通過數據去重節約的空間十分可觀。要進行重復數據的刪除，首先要檢索出新寫入文件在整個存儲系統中與哪一個文件相似，從而輸出相似度，已決定是否進行精細對比，這種做法對系統的開銷極大，同時隨著存儲空間內文件的增加，運算將越來越耗時，不利于大量文件的周轉，而且，僅僅用相似度作為判斷依據是有缺陷的，因為相似度還會受到抽樣方法和抽樣大小的影響。為解決這種需求，本發明提出一種云存儲中重復數據刪除的檢索算法，解決了抽樣對相似度的影響。

發明內容

針對重復數據在云空間中，對檢索造成麻煩，還浪費了寶貴的云資源，產生額外開銷以及為了解決抽樣對相似度的影響，本發明提出了一種云存儲中重復數據刪除的檢索算法。

本發明為了實現上述目的所采用的技術方案：對存儲空間內的文件進行分塊，并隨機抽取部分數據塊作為樣本，對樣本數據進行哈希，提取指紋特征，計算不同文件樣本之間的相似度，相似度結合抽樣大小，建立系統文件之間重復率函數，通過重復率設定的閾值來判斷文件之間的重復情況，選取對比文件，對其余文件冗余的數據塊進行刪除處理，建立索引并進行存儲，在提取文件時候依據索引和對比文件，重構出數據。

本發明的有益效果：本發明對系統開銷較小，運行時間短，并且維持較高的重復刪除率。更適用于大量數據存儲和云存儲環境下使用。

具體實施方式

為了使本發明的目的、技術方案及優點更加清楚，以下是本發明技術方案的具體計算步驟過程：

步驟1.指紋數據值得是文件分塊后，對每一個文件塊哈希，對應的哈希值即為指紋。

步驟2.計算不同文件樣本之間的相似度，其具體求解過程如下：

設在存儲空間中有文件P將他們按照字長分為n個文件塊，對每一個文件塊進行哈希，輸出哈希值的集合A_P，A_P＝(a_P1，a_P2，…，a_Pn)；同理，對于文件Q則有：A_Q＝(a_Q1，a_Q2，…，a_Qn)

如果：A_Pi＝a_Qi，表示兩個文件塊相同，那么在文件P/Q中，具有相同塊的數量可以表示為：∑_imin(A_Pi，a_Qi)兩個文件的總塊數為：∑_imax(A_Pi，a_Qi)，那么令r表示兩個文件之間的相似度，則：

但是，如果這樣去判定，在大數據環境和云存儲環境下，明顯是不可行的，因為計算量太大，引起的系統開銷大，而且耗時長。

所以在相似度的計算上，本發明采用抽樣處理：在文件P哈希值的集合A_P＝(a_P1，a_P2，…，a_Pn)，隨機抽取u個樣本放入集合U中U_P＝(a_P1，a_P2，…，a_Pu)，1<u<n，對文件Q做同樣處理，可以得到樣本的相似度為：

步驟3.相似度結合抽樣大小，建立系統文件之間重復率函數，其具體求解過程如下：

由于抽樣計算，系統的運算時間和占用率都大為縮小，但是r并不能準確表示表示文件Q，P之間的相似性。由此，文件P在分為n個文件塊，哈希后得到n個哈希值，也就是n個文件指紋，設m表示冗余塊，k是從n個文件指紋中抽取出來的樣品文件指紋數，當從文件塊中抽取一定數目的哈希時，有概率(c)抽取到冗余塊，那么抽取到冗余數據塊的概率符合離散型隨機變量分布規律，故抽取到冗余塊的期望(E)為：