[發明專利]為基于散列的消重進行子塊分割的方法和系統

有效

• 申請號: 201310275022.4
• 申請日: 2013-07-03
• 公開（公告）號: CN103530310A
• 公開（公告）日: 2014-01-22
• 發明（設計）人: L·阿羅諾維奇;M·海爾什
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國國際貿易促進委員會專利商標事務所 11038
• 代理人: 高青

技術領域

本發明總體上涉及計算機，更具體而言，涉及計算環境中用于基于散列的消重（deduplication）的改進的子塊分割。

背景技術

在當今社會，計算機系統是普遍存在的。計算機系統可以在工作場所、在家庭或者在學校找到。計算機系統可以包括數據存儲系統，或者說盤存儲系統，來處理和存儲數據。每天要必須處理大量的數據，而且當前的趨勢表明，在可以預見的將來，這些量將繼續增加。緩解這個問題的一種有效途徑是通過使用消重。通過定位重復的數據并且只存儲其第一次出現，作為消重系統的基礎的思想是利用大部分可用數據被一次又一次沒有任何變化地拷貝和轉發的事實。后續的拷貝被指向存儲的出現的指針所代替，如果數據事實上是重復的，那么這顯著降低了存儲需求。

發明內容

數據消重是指冗余數據的減少和/或消除。在數據消重中，可以是文件、數據流或者某種其它形式的數據的數據對象被分成一個或多個被稱為子塊的部分。在數據消重處理中，數據的復制拷貝被減少或消除，分別留下最少量的冗余拷貝或者數據的單個拷貝。利用消重處理提供了各種好處，諸如所需存儲容量的減少和增加的網絡帶寬。由于這些及其它好處，近年來，消重已經作為計算存儲系統中的一個高度重要的技術領域而顯現出來。

已經推薦了幾種消重方法，這些方法中的許多都使用散列技術。例如，在基于散列的消重操作中，數據消重涉及把數據分成可變或固定尺寸的子塊、計算每個子塊的散列值并且通過其散列值來匹配完全相同的子塊。

基于散列的消重系統應當能夠提供平均子塊尺寸，同時維持子塊尺寸的一致性，而不是經歷顯著變化的子塊尺寸。當前，基于散列的消重系統不能夠在維持子塊尺寸的一致性的同時提供平均子塊尺寸。因而，在處理子塊尺寸變化時出現困難，這使存儲與處理考慮復雜化。換句話說，人為最小和最大子塊尺寸使基于散列的消重系統中的子塊和子塊元數據的存儲和檢索復雜化。連同平均子塊尺寸的偏移一起，子塊尺寸的大而多樣的分布降低了元數據（索引和指針）和數據之間的平衡的效率。子塊邊界的再現性的破壞降低了消重系統關于數據序列中的數據的重新排序、插入、移動和刪除來識別完全相同的子塊的能力。

因此，需要避免關于子塊的人為最小和最大尺寸的基于散列的消重系統，這種人為最小和最大尺寸會降低關于找出有效子塊邊界的概率的效果以及降低關于平均子塊尺寸的偏移效果，從而打破可再現子塊邊界的基本屬性。因此，所說明的實施例設法提供定義的最小和最大子塊尺寸（為了數據的方便管理）和子塊尺寸圍繞可預測平均尺寸的緊密分布（為了存儲和處理資源消耗的可預測性），同時產生可再現和統計上顯著的子塊邊界（為了有效的子塊匹配和消重）。

相應地，并且鑒于以上所述，提供了用于在計算環境中為基于散列的消重進行改進的子塊分割的各種示例性方法、系統和計算機程序產品實施例。在一種實施例中，僅僅是作為例子，定義子塊的最小和最大尺寸。對于子塊的每個邊界開始位置，通過使用多個搜索標準來測試在搜索期間計算的各個散列值和/或一組基礎散列值的導出散列值，在該子塊的最小尺寸之后開始對后續子塊的邊界位置的搜索。如果所述散列值中的一個滿足多個搜索標準中的一個，則把該散列值的位置聲明為所述子塊的邊界結束位置。如果在滿足多個搜索標準中的一個之前到達子塊的最大尺寸，則把基于多個搜索標準中的另一個選擇的另外一個散列值的位置聲明為所述子塊的邊界結束位置。

除了以上示例性方法實施例，還提供了其它的示例性系統和計算機產品實施例并且提供了相關的優點。以上概述的提供是為了以簡化的形式提供以下在具體描述中進一步描述的概念的選擇。這個概述不是要識別所保護主題的關鍵特征或基本特征，也不是要用于幫助確定所保護主題的范圍。所保護的主題不限于解決背景技術中所提到的任何或全部缺點的實現。

附圖說明

為了很容易地理解本發明的優點，將參考在附圖中說明的具體實施例給出以上簡單描述過的本發明的更特定的描述。應當理解，這些圖繪出了本發明的實施例而且并不能因此就認為是限定其范圍，本發明將通過附圖的使用以附加的特殊性與細節進行描述，其中：

圖1是說明具有例子存儲設備的計算系統環境的框圖，其中可以實現本發明的各方面；

圖2是說明計算機系統中的數據存儲系統的硬件結構的框圖，其中可以實現本發明的各方面；

圖3是說明用于基于散列的消重的改進子塊分割的示例性方法的流程圖；

圖4是說明計算機系統中的示例性子塊定義的框圖，其中可以實現本發明的各方面；