[發明專利]基于位置敏感哈希的刪冗存儲系統元數據管理方法有效

申請號：	201010294016.X	申請日：	2010-09-27
公開（公告）號：	CN101963982A	公開（公告）日：	2011-02-02
發明（設計）人：	余宏亮;孫競	申請（專利權）人：	清華大學
主分類號：	G06F17/30	分類號：	G06F17/30
代理公司：	北京路浩知識產權代理有限公司 11002	代理人：	王瑩
地址：	100084 北京市海***	國省代碼：	北京;11
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	基于位置敏感存儲系統數據管理方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明涉及計算機數據存儲技術領域，具體涉及一種基于位置敏感哈希的刪冗存儲系統元數據管理方法。

背景技術

隨著數字信息量的爆炸式增長，數據占用空間越來越大；在過去的10年里，很多行業提供的存儲系統容量從數十GB發展到數百TB，甚至數PB，足足翻了10,000多倍。隨著數據的指數級增長，企業面臨的快速備份和恢復的時間點越來越多，管理保存數據的成本及數據中心空間和電源的耗費也變得越來越昂貴。研究發現，應用系統所保存的數據，高達60％是冗余的，而且隨著時間的推移越來越嚴重，人們可能要花費超過10倍的存儲空間和管理成本。

為了緩解存儲系統的空間增長問題，縮減數據占用空間，降低成本、最大程度的利用已有資源，冗余數據刪除技術(簡稱刪冗技術)就應運而生了。一方面，利用冗余數據刪除技術，可以對存儲空間的利用率進行優化。因傳統的數據壓縮技術主要根據一些固定的模式利用傳統的數據分析工具和技術來消除重復數據，不能有效地改善基于磁盤數據的成本效益，所以需要通過探究重復數據的特性，利用相應的冗余數據刪除技術，以消除分布在存儲系統中的相同文件或者數據塊。另一方面，利用冗余數據刪除技術，可以減少在網絡中傳輸的數據量，進而降低能量消耗和網絡成本。由于冗余數據刪除技術的目標是消除分布在存儲系統中的相同及相似文件或者數據塊，因此能夠減少大量的磁盤消耗，并且為數據復制大大節省網絡帶寬。

刪冗技術可以廣泛用于從虛擬機存儲、文件服務器、郵件服務器、磁盤備份、社區網絡(Social?Networking?Services，SNS)等諸多應用領域。傳統上刪冗技術不作為主存儲系統(Primary?Storage?System)使用，但近年來，隨著云存儲等技術的發展，以刪冗技術構建主存儲系統成為了一個重要的技術課題，以刪冗技術構建的主存儲系統簡稱為刪冗存儲系統。

在構建主存儲刪冗系統(Primary?Storage?Dedulication?System)(即刪冗存儲系統)的時候，主要有兩個重要的技術挑戰：(1)由于刪冗而產生大量的計算開銷如何消除；(2)相對普通存儲系統，刪冗存儲系統中，元數據的數量激增，而在進行數據寫操作的時候，需要查找所要寫的數據是否在系統中已經存在，這種查找的開銷極大。

發明內容

(一)要解決的技術問題

本發明要解決的技術問題是：如何提供一種基于位置敏感哈希的刪冗存儲系統元數據管理方法，使其顯著提高刪冗存儲系統中元數據查找的速度，從而提高整個刪冗存儲系統的存取吞吐率。

(二)技術方案

為解決上述技術問題，本發明提供了基于位置敏感哈希的刪冗存儲系統元數據管理方法，所述方法的寫數據操作包括以下步驟：

S101、將文件分塊，計算每個數據塊的數字指紋，生成文件數字指紋集合；

S102、將所述文件數字指紋集合映射到一個固定大小的存儲結構中進行歸一化處理，得到固定長度的輸入向量；

S103、根據所述輸入向量計算所述文件數字指紋集合的位置敏感哈希函數值；

S104、根據所述位置敏感哈希函數值查找相似文件的元數據集合的地址，根據該地址將所述相似文件的元數據集合讀入內存，然后查找存在于所述文件數字指紋集合中而在所述相似文件的元數據集合中沒有保存的數字指紋；所述相似文件是包含有一定數量相同數據塊的文件；

S105、根據步驟S104得到的所述元數據集合中沒有保存的數字指紋對應的數據塊生成相應的元數據，將所述相應的元數據合并到所述相似文件的元數據集合中。

在步驟S102中，使用bloom?filter進行歸一化處理，歸一化后，bloom?filter的輸出具有相同長度，所述輸出為位置敏感哈希函數的所述輸入向量。

所有文件數字指紋集合使用相同的位置敏感哈希函數來計算位置敏感哈希函數值，所述位置敏感哈希函數使用確定大小的隨機變量組成的向量與所述輸入向量進行點積，求得位置敏感哈希函數值。