[發明專利]利用了數據段的相似度的高效數據存儲

有效

• 申請號: 201210299545.8
• 申請日: 2007-04-11
• 公開（公告）號: CN102999543A
• 公開（公告）日: 2013-03-27
• 發明（設計）人: K.李;M.B.朱;U.馬赫什沃里;Z.楊
• 申請（專利權）人: EMC公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 湯春龍;劉春元

發明背景

一種高效地存儲數據的方法是防止對于在備份之間保持不變的數據的冗余拷貝。這種高效的存儲是通過把來自各數據源的數據流分成段(segment)并且把所述段以及所述段的標識符的索引存儲在存儲設備上來實現的。在后續的備份操作期間，再次對所述數據流進行分段，并且在所述索引中查找所述段以便確定某一數據段先前是否已被存儲過。如果找到完全相同的段，則不再存儲該數據段；否則就存儲所述新的數據段和新的索引標識符。遺憾的是，隨著將要備份的數據量的增加，所述段的數目(如果所述段的尺寸近似的話)以及所述索引條目的數目也會增加。所述段和索引條目的數目的增加會導致存取性能的降低：對于寫入，必須把到來的段索引與所述索引中的所有條目進行比較；以及對于讀取，必須從較大數目的段當中檢索與某一文件相關聯的段。如果增大所述段的尺寸，則會減少所述段的數目，從而所述索引條目的數目也會減少，性能也可以得到保持；然而，由于出現較長的完全相同的段的幾率沒有那么高，因此存儲效率會降低。如果可以在不犧牲存儲效率的情況下保持存取性能，則將是有益的。

附圖簡述

在下面的詳細描述和附圖中公開了本發明的各種實施例。

圖1是示出利用數據段的相似度進行高效存儲的系統的一個實施例的方框圖。

圖2是示出利用數據段的相似度進行高效存儲的處理的一個實施例的方框圖。

圖3是示出寫入期間的內容存儲過程的一個實施例的流程圖。

圖4是示出用于生成邏輯段以及計算概要特征集合的過程的一個實施例的流程圖。

圖5是示出讀取期間的內容存儲過程的一個實施例的流程圖。

圖6是示出寫入期間的段存儲過程的一個實施例的流程圖。

圖7是示出相似度確定過程的一個實施例的流程圖。

圖8是示出針對讀取的段存儲過程的一個實施例的流程圖。

詳細描述

可以按照多種方式來實施本發明，其中包括把本發明實施為一種過程、設備、系統、物質構成、計算機可讀介質(比如計算機可讀存儲介質)或者計算機網絡(其中通過光學或電子通信鏈路來發送程序指令)。在本說明書中，這些實施方式或者本發明所能采取的任何其他形式都可以被稱作技術。諸如被描述為被配置成執行任務的處理器或存儲器之類的組件包括通用組件或專用組件，其中所述通用組件在給定時間被臨時配置成執行所述任務，而所述專用組件是為了執行所述任務而被制造的。一般來說，在本發明的范圍內可以改變所公開的過程的各步驟的順序。

在下面連同附圖一起提供對本發明的一個或多個實施例的詳細描述，所述附圖示出本發明的原理。下面將結合所述實施例來描述本發明，但是本發明不限于任何實施例。本發明的范圍僅僅由權利要求書來限定，并且本發明包含許多替換方案、修改和等效方案。為了提供對于本發明的透徹理解，在下面的描述中闡述了許多具體細節。提供這些細節是出于舉例的目的，并且可以在沒有一些或全部所述具體細節的情況下根據權利要求書來實踐本發明。為了清楚起見沒有描述本發明的相關技術領域內已知的技術材料，以免不必要地模糊本發明。

公開了利用數據段的相似度來進行高效的存儲。確定一個新段與一個先前存儲的段相似，其中所述先前存儲的段包括來自某一輸入數據流中的任何位置的一個先前存儲的段。至少部分地基于增量來存儲所述新段的表示。存儲增量會提高存儲效率，尤其是在其中各段與先前存儲的段相比可能具有小的改變的情況下，這是因為與存儲新段相比，存儲小的增量更為高效。通過把第一段的概要特征集合與第二段的概要特征集合進行比較來確定相似度。在一些實施例中，所述第一段是從某一輸入數據流到達的段，而所述第二段是來自某一輸入數據流的先前已被存儲在備份存儲系統中的任何段。在一些實施例中，所述第一段與第一輸入數據流相關聯，而所述第二段與第二輸入數據流相關聯。在一些實施例中，所述相似度包括第一段與第二段之間的逐字節相似性的度量。通過以下操作來確定概要特征集合：選擇第一段的多個固定長度或可變長度的子段；對于每一個子段，通過對于每一個子段應用一組函數來計算多個值；以及從對于所有所述子段所計算的所有所述值當中選擇第一值子集。在一些實施例中，所述第一值子集被用于確定所述第一段與第二段之間的相似度。