確定用於去重複的段邊界的製作方法
2023-05-08 05:01:16
確定用於去重複的段邊界的製作方法
【專利摘要】接收散列的序列。每個散列對應於有待去重複的數據的數據組塊。確定數據組塊的先前存儲的副本的位置，所述位置是基於散列來確定的。基於位置來確定數據組塊的序列中的斷點，所述斷點形成數據組塊段的邊界。
【專利說明】確定用於去重複的段邊界
【背景技術】
[0001]管理員力求高效管理文件伺服器和文件伺服器資源，同時保持網絡受保護以防未經授權的用戶而仍對經授權的用戶來說可訪問。將文件存儲在伺服器上而不是本地存儲在用戶的計算機上的實踐已經造成相同數據存儲在相同系統中的多個位置處以及甚至在相同伺服器中的多個位置處。
[0002]去重複(deduplicat1n)是用於消除冗餘數據、改善存儲利用率和減小網絡業務量的技術。基於存儲的數據去重複檢查大容量的數據並標識相同的整個文件或文件的章節，然後減少相同數據的實例的數目。例如，電子郵件系統可以包含相同的一兆字節文件附件的100個實例。每當電子郵件系統被備份時，都存儲附件的100個實例中的每一個，這要求100兆字節的存儲空間。利用數據去重複，僅存儲附件的一個實例，因此節省99兆字節的存儲空間。
【專利附圖】
【附圖說明】
[0003]為了詳細描述本發明的示例性實施例，現在將對附圖做出參考，在附圖中:
圖1A圖示了用於確定段邊界的系統；
圖1B圖示了用於確定段邊界的系統；
圖2圖示了用於確定段邊界的方法；
圖3圖示了用於確定段邊界的存儲設備；
圖4A和4B示出了確定段邊界的圖。
[0004]標記法和命名法
如本文所使用的，術語「組塊」是指數據流的連續子集。
[0005]如本文所使用的，術語「段」是指連續組塊的群組。每個段具有兩個邊界，一個在它的開始處並且一個在它的結尾處。
[0006]如本文所使用的，術語「散列」是指使用散列函數創建的組塊的標識。
[0007]如本文所使用的，術語「塊」是指與其它文件或數據流交錯的文件或數據流的劃分。例如，交錯數據可以包括la，2a，3a，lb，2b，lc，3b，2c，其中Ia是基礎流一的第一塊，Ib是基礎流一的第二塊，2a是基礎流二的第一塊等等。在一些情況下，塊在長度上可以不同。
[0008]如本文所使用的，術語「去重複」是指在存儲系統中或在存儲節點處邏輯存儲組塊、段或數據的其它劃分以使得在該系統或節點處存在每個唯一組塊的僅一個物理副本(或者，在一些情況下，幾個副本)的動作。例如，針對初始為空的存儲節點去重複ABC、DBC和EBF (其中每個字母表示唯一組塊)導致B的僅一個物理副本但是三個邏輯副本。具體地，如果針對存儲位置去重複組塊並且組塊先前未被存儲在存儲位置處，則將組塊物理存儲在存儲位置處。然而，如果針對存儲位置去重複組塊並且組塊已經被存儲在存儲位置處，則不再次在存儲位置處物理存儲組塊。在又一示例中，如果針對存儲位置去重複多個組塊並且組塊中的僅一些已經被存儲在存儲位置處，則在去重複期間在存儲位置處存儲僅先前未被存儲在存儲位置處的組塊。
【具體實施方式】
[0009]以下討論涉及本發明的各種實施例。儘管這些實施例中的一個或多個可以是優選的，但是所公開的實施例不應當被解釋為或以其它方式用作限制包括權利要求在內的本公開的範圍。此外，本領域技術人員將理解，以下描述具有寬泛的應用，並且任何實施例的討論僅僅意在例證該實施例，而不旨在暗示包括權利要求在內的本公開的範圍受限於該實施例。
[0010]在基於組塊的去重複期間，唯一的數據組塊每一個都被物理存儲一次，不論可能存在多少它們的邏輯副本。所接收的後續組塊可以與所存儲的組塊比較，並且如果比較得到匹配，則匹配的組塊不再次被物理存儲。取而代之，匹配的組塊可以被指向組塊的單個物理副本的引用替代。訪問引用的過程可以被重定向到所存儲的組塊的單個物理實例。以該方式使用引用導致存儲節約。因為可以遍及系統多次出現相同組塊，所以必須被存儲在系統中或通過網絡傳送的數據量減少。然而，交錯數據難以高效地去重複。
[0011]圖1A圖示了用於智能分段的系統100。交錯數據是指通過交錯來自不同基礎源的數據而從不同基礎源產生的數據流。例如，四個基礎數據源A，B，C和D 180可以被交錯以產生流adcccbadaaaadcb,其中a表示來自源A的數據塊，b表示來自源B的數據塊,c表示來自源C的數據塊，並且d表示來自源D的數據塊。
[0012]在不理解用於對流進行交錯的格式的情況下，恢復基礎源流是困難的。因為不同的備份代理由以不同方式交錯數據的不同公司做出，並且因為交錯的方法隨時間改變，所以產生可去交錯所有交錯數據的系統可能不是划算的。因此，對於系統而言能夠直接處置交錯數據可以是有用的。
[0013]在去重複期間，可以在前端上或者在客戶端199上實時創建組塊的散列，所述前端與一個或多個去重複後端通信。例如，與可以是去重複後端節點116、120、122的一個或多個後端通信的前端118。在各種實施例中，前端和後端還包括其它計算設備或系統。數據組塊是使用可基於大小或邏輯文件邊界的組塊化算法產生的數據流的連續子集。每個數據組塊可以被輸入到可用密碼寫的散列函數；例如MD5或SHA1。在圖1A的示例中，組塊I1,I2,13 I4分別導致散列A613F……,32B11……,4C23D……和35DFA……。在至少一些實施例中，每個組塊可以近似是4千字節左右，並且每個散列可以近似是16到20位元組。
[0014]取代為了去重複目的而比較組塊，可以比較組塊的散列。具體地，如果使用相同的散列化算法，則相同組塊將產生相同的散列。因此，如果兩個組塊的散列相等，並且已經存儲了一個組塊，則另一組塊無需被再次物理存儲；這節省了存儲空間。同樣，如果散列相等，則基礎組塊自身可以被比較以核實重複，或者可以假設重複。此外，系統100可以包括一個或多個後端節點116、120、122。在至少一個實施方式中，不同後端節點116、120、122通常不存儲相同組塊。這樣，節省了存儲空間，因為相同組塊未被存儲在後端節點116、120、122之間，但是段(組塊的群組)必須被路由到正確的後端節點116、120、122以被有效地去重複。
[0015]比較組塊的散列可以被執行得比比較組塊自身更加高效，特別是在使用索引和過濾器時。為了有助於比較過程，可以使用索引105和/或過濾器107來確定哪些組塊被存儲在後端節點116、120、122上的哪些存儲位置106中。在至少一個實施方式中，索引105和/或過濾器107可以駐留在後端節點116、120、122上。在其它實施方式中，索引105和/或過濾器107可以以任何組合分布在前端節點118和/或後端節點116、120、122當中。此夕卜，每個後端節點116、120、122可以具有分離的索引105和/或過濾器107，因為不同數據被存儲在每個後端節點116、120、122上。
[0016]在一些實施方式中，索引105包括將存儲在該後端節點上的組塊的散列(可能間接地)映射到包含那些組塊的存儲位置的數據結構。該數據結構可以是散列表。對於非稀疏索引，針對每一個所存儲的組塊創建條目。對於稀疏索引，針對存儲在該後端節點上的組塊的散列的僅有限一小部分創建條目。在至少一個實施例中，稀疏索引平均僅對每64個組塊中的一個編索引。
[0017]在至少一個實施例中，過濾器107可以存在和被實現為布隆(Bloom)過濾器。布隆過濾器是用於近似集合成員資格的空間高效數據結構。也就是說，它表示集合，但是所表示的集合可以包含未被顯式插入的元素。過濾器107可以表示存儲在該後端節點處的組塊集合的散列集合。在該實施方式中後端節點可以因此通過確定給定組塊的散列是否是其過濾器107的成員來快速確定給定組塊是否可能已經存儲在該後端節點處。
[0018]在至少一個實施例中，並非在每組塊基礎上確定要針對哪個後端節點去重複組塊(即，要將組塊路由到哪個後端節點)。而是，一次一段(組塊的連續群組)確定路由。數據組塊的輸入流可以被分成段，使得每個數據組塊確切地屬於一個段。圖1A圖示了組塊I1和I2包括段130，並且組塊I3和I4包括段132。在其它示例中，段可以包含數千個組塊。段可以包括在交錯流中鄰近的組塊的群組。段的邊界為斷點。如所圖示的，段130與段132之間的斷點處於12和I3之間。如圖2的方法中詳述的，可以基於先前存儲的組塊的位置確定流中的合適斷點。在各種實施例中，由前端節點118、後端節點116、120、122、或前端節點118和後端節點116、120、122 二者確定斷點。
[0019]儘管圖1A僅示出一個前端118，但是系統可以包含多個前端，每一個前端實現類似的功能性。僅示出其中的一個的客戶端199可以在長時間段內與相同的前端118通信。在一個實施方式中，前端118和後端節點116、120、122的功能性被組合在單個節點中。
[0020]圖1B圖示了系統100的硬體視圖。在至少一個實施例中，系統100的組件可以分布在一個或多個網絡114之上。具體地，用戶可以與⑶I 110交互並通過網絡114從管理控制臺發射命令和其它信息以供前端節點118和後端節點116處理。顯示器104可以是計算機監視器，並且用戶可以經由鍵盤112和指點設備或計算機滑鼠(未示出)操縱GUI。網絡114可以包括諸如交換機之類的網絡元件，並在至少一個實施例中可以是網際網路。在至少一個實施例中，前端節點118包括執行散列化算法的處理器102。在另一實施例中，系統100包括多個前端節點。後端節點116包括可訪問索引105和/或過濾器107的處理器108，並且處理器108可以耦合到存儲位置106。系統100的硬體組件的許多配置和組合是可能的。在另一實施例中，系統100包括多個後端節點。
[0021]在至少一個實施例中，一個或多個客戶端199通過所調度的命令而被周期性地備份。虛擬帶庫(「VLT」)或網絡文件系統(「NFS」)協議可以被用作用於備份客戶端199的協議。
[0022]圖2圖示了在202處開始且在210處結束的智能分段的方法200。在204處，接收散列的序列。例如，序列可以由前端節點118從針對去重複而調度的交錯數據的順序組塊生成。交錯數據的順序組塊可以已經通過對從客戶端199接收的交錯數據進行組塊化以供去重複而產生在前端節點118上。組塊化過程將交錯數據分成數據組塊的序列。散列的序列可以進而通過對每個數據組塊進行散列化而生成。
[0023]可替換地，組塊化和散列化可以由客戶端199執行，並且可以僅將散列發送到前端節點118。其它變型是可能的。
[0024]如上所述，交錯數據可以源自不同的源或流。例如，不同的線程可以將數據復用到單個文件中從而導致交錯數據。每個散列對應於組塊。在至少一個實施例中，所接收的散列的量對應於具有總計平均段長度的三倍的長度的組塊。儘管使用交錯數據作為示例討論了系統，但是在至少一個示例中，非交錯數據也被類似地處置。
[0025]在206處，確定數據組塊的先前存儲的副本的位置。在至少一個示例中，針對位置信息而對後端116、120、122做出查詢,並且位置可以作為查詢的結果而接收。在一個實施方式中，前端節點118可以向後端節點116、120、122廣播散列的序列，所述後端節點116、120,122中的每一個然後可以確定其位置106中的哪些包含對應於所發送的散列的數據組塊的副本並向前端節點118發送回所得到的位置信息。在一個節點實施方式中，該確定可以直接進行而無需節點之間的任何通信。
[0026]對於每個數據組塊，可以確定哪些位置已經包含該數據組塊的副本。該確定可以利用試探法。在一些實施方式中，該確定可以僅針對數據組塊的子集而進行。
[0027]位置可以與後端節點的群組或集群或者特定後端節點一樣通用，或者位置可以與組塊容器(例如，存儲組塊的文件或盤部分)或具體後端節點上的其它特定位置一樣專用。確定位置可以包括在諸如完整組塊索引或稀疏索引之類的索引105或諸如布隆過濾器之類的集合或過濾器107中搜索散列中的一個或多個。所確定的位置可以是後端節點116、120,122的群組、特定的後端節點116、120、122、組塊容器、儲存器或存儲節點。例如，每個後端節點可以向前端節點118返回組塊容器標識號碼的集合的列表，每個集合關於對應的散列/數據組塊，並且組塊容器標識號碼標識其中存儲該數據組塊的副本的被存儲在該後端節點處的組塊容器。這些列表可以在前端節點118上被組合成單個列表，該單個列錶針對每個數據組塊給出標識包含該數據組塊的副本的組塊容器的組塊容器ID/後端號碼對。
[0028]在另一實施例中，所返回的信息僅標識該後端節點具有哪些數據組塊的副本。同樣，信息可以被組合以產生針對每個數據組塊給出包含該數據組塊的副本的後端節點的集合的列表。
[0029]在僅具有單個節點的又一實施例中，所確定的信息可以只由組塊容器ID的集合的列表構成，因為不存在在不同後端節點之間進行區分的需要。如本領域技術人員所意識到的那樣，存在可以傳達位置信息的許多不同方式。
[0030]在208處，至少部分地基於確定的位置確定組塊的序列中的斷點。該斷點可以用於形成數據組塊段的邊界。例如，如果尚未產生段，則第一段可以被生成為從序列的開始的數據組塊到恰在所確定的斷點之前的數據組塊。可替換地，如果已經生成了一些段，則所生成的下一段可以由處於所生成的最後一段的結尾與新確定的斷點之間的數據組塊構成。
[0031]圖2的每次迭代(202到210)可以確定新的斷點並從而確定新的段。每次附加迭代可以重用先前迭代的工作或信息中的一些。例如，未被先前迭代形成到段中的數據組塊的散列及其確定的位置可以被下一迭代再次考慮以便可能包括在所確定的下一段中。將數據組塊的序列分成段的過程被稱為分段。
[0032]確定斷點可以包括部分地基於哪些數據組塊在所確定的相同位置中具有副本來確定數據組塊的序列中的區域並且然後基於該區域來確定數據組塊的序列中的斷點。例如，數據組塊的序列中的區域可以被確定成使得具有每個區域的所確定的位置的數據組塊的至少90%在單個位置中具有先前存儲的副本。也就是說，對於每個區域，存在其中具有所確定的位置的數據組塊的至少90%具有先前存儲的副本的位置。接下來，可以基於區域來確定數據組塊的序列中的斷點。
[0033]對應於相同或類似位置的散列和組塊可以被成組。例如，前端節點118可以將對應於一個位置的散列和對應數據組塊成組為段，並可以將對應於不同位置的鄰近散列和對應數據組塊成組為另一段。這樣，確定斷點處於這兩個段之間。
[0034]前端節點118可以針對後端節點之一，作為整體去重複新形成的段。也就是說，可以僅針對被包含在後端節點之一中的數據而不針對被包含在其它後端節點中的數據去重複該段。這與例如針對一個後端節點去重複段的第一半並且針對另一後端節點去重複該段的第二半形成對照。在至少一個實施例中，被包含在後端節點中的數據可以在附接到後端節點的儲存器中，在後端節點的控制之下，或者是後端節點的首要責任而不是在物理上作為其一部分。
[0035]可以僅針對被包含在多個節點之一中的數據去重複段。在一個實施例中，所選取的後端節點116、120或122標識將針對其去重複段的存儲位置106。
[0036]以上描述的系統可以被實現在具有足以處置置於計算機上的必要工作負載的處理能力、存儲器資源和吞吐量能力的任何特定機器或計算機上。圖3圖示了適於實現本文所公開的一個或多個示例的特定計算機系統380。計算機系統380包括與存儲器設備通信的一個或多個硬體處理器382 (其可以被稱為中央處理器單元或CPU)，所述存儲器設備包括計算機可讀存儲設備388和輸入/輸出(I/O) 390設備。該一個或多個處理器可以被實現為一個或多個CPU晶片。
[0037]在各種實施例中，計算機可讀存儲設備388包括諸如易失性存儲器(例如RAM)、非易失性儲存器(例如快閃記憶體、硬碟驅動器、CD ROM等)或其組合之類的非暫時性存儲設備。計算機可讀存儲設備388可以包括存儲由(一個或多個)處理器382執行的軟體或指令384的計算機或機器可讀介質。本文所描述的一個或多個動作在指令384的執行期間由(一個或多個)處理器382執行。
[0038]圖4A圖示了確定區域的集合的一種方式的示例。這裡，示出了 25個組塊的序列。在各種示例中，可以一次處理數千個組塊。對於每個組塊，在該組塊上方示出其確定的位置。例如，尚未確定組塊號碼I在任何位置106中具有副本。在至少一個示例中，它可以表示尚未被存儲的新數據。可替換地，用於確定組塊位置的試探法可能已經在這種情況下犯了錯誤。相比之下，已經確定組塊號碼2在位置5中。組塊號碼3也不具有確定的位置，但已經確定組塊號碼4到6在位置I中具有副本。注意，已經確定一些組塊在多個位置中；例如，已經確定組塊號碼9和10在位置I和2 二者中具有副本。
[0039]以下示出組塊是許多區域，Rl到R6。例如，區域Rl包括組塊I到3，並且區域R2包括組塊3到18。這些區域(R1-R6)是已經通過下述操作來確定的:找到最大連續子序列，使得每個子序列具有關聯的位置並且該子序列中的每個數據組塊要麼使該位置作為它的確定的位置之一要麼不具有確定的位置。例如，區域Rl的關聯位置為5;它的組塊之一(#2)使5作為它的確定的位置之一併且其它兩個組塊(# I和3)不具有確定的位置。類似地，R2的關聯位置為1，R3和R6的關聯位置為2，R4的關聯位置為4，並且R5的關聯位置為3。
[0040]這些區域中的每一個都是最大的，因為它不能夠在不違反示例區域生成規則的情況下在任一方向上被擴展甚至一個組塊。例如，組塊4不能夠被添加到區域R1，因為它具有確定的位置並且其確定的位置中沒有一個為5。每個區域表示駐留在一個位置中的一長條數據；因此，區域中部處的斷點將很可能導致去重複的損失。因為新的數據(例如沒有位置的數據組塊)能夠被存儲在任何地方而沒有創建中間重複的風險，所以新的數據有效地像通配符一樣操作，允許它作為任何區域的一部分，由此擴展該區域。
[0041]存在確定區域的許多方式。例如，區域無需最大，但可能被要求以具有確定的位置的數據組塊結束。在另一示例中，為了應對噪聲，可以允許區域併入有具有不包括區域的主要位置的確定的位置的少量數據組塊。例如，在圖4A中，如所示的，可能允許區域R2存在，即便確定了組塊13位於位置5中。在另一示例中，可以存在對區域可以併入有多少這樣的組塊的限制；該限制可以是絕對的(例如不大於五個組塊)或者相對的(例如具有確定的位置的數據組塊中不大於10%可能具有除關聯位置外的確定的位置)。
[0042]在另一示例中，可以以不同方式處置新的數據組塊。取代將它們的位置視作能夠屬於任何區域的通配符，而是可以將它們視為位於具有確定的位置的左側最接近的組塊的確定的位置和具有確定的位置的右側最接近的組塊的確定的位置二者中。如果具有確定的位置的最接近組塊太過遙遠(例如超過離開距離的閾值)，則可以忽略其確定的位置。因此，太過遠離舊組塊的新數據組塊可以被視為不具有位置，並且因此，要麼不可併入到區域中要麼僅可併入到特殊區域中。在至少一個示例中，這樣的特殊原因可以是僅包含遠離舊數據組塊的類似的新數據組塊的一個。在另一示例中，新數據組塊可以被視為在具有確定的位置的最接近的數據組塊的確定的位置中。在圖4A的情況下，可以將組塊11視作其在位置1&2中，可以將組塊13視作其在位置I中，並且可以將組塊12視作取決於平局決勝規則而在位置1&2中、在I中或者這二者。
[0043]因為「打斷」(即，確定邊界)區域中部很可能導致重複，所以如果可能的話應當避免它。而且，較大區域而不是較小區域中部處的打斷和更接近於區域中部的打斷將很可能導致更多的重複。這樣，這些情景也應當被最小化。通過將區域考慮在內，可以基於區域來確定高效的斷點。高效的斷點導致所存儲的數據的更少重複。
[0044]存在確定邊界的許多方式。一個示例涉及專注於保持最大區域，例如選擇最大區域並且縮短與其重疊的其它區域的部分。縮短在這裡意味著使較小區域恰好足夠小以使得它不與最大區域重疊；如果較小區域被完全包含在最大區域中，這可能要求整個移除較小區域。在圖4A的情況下，最大區域為R2。可以將Rl縮短到組塊1-2，並且可以丟棄R3，因為它完全與R2重疊。可以將R4縮短到組塊19-25。可以選擇其餘的下一最大區域並且重複過程，直到沒有其餘的區域重疊。對於圖4A的該過程的結果被示出在圖4B中。
[0045]潛在斷點可以恰好處於圖4B中的三個所得到的區域(Rl』、R2』和R4』 )中的每一個的第一組塊之前和最後組塊之後。在一個示例中，選取處於所要求的最小段大小和所要求的最大段大小之間的最早的這樣的斷點。如果沒有這樣的斷點存在，則要麼可以選取最大段大小，要麼可以應用不將確定的組塊位置考慮在內的備用分段方案。如果為了圖4A的示例的目的，假設最小段大小8和最大段大小23，則將選取組塊18與19之間的斷點。第一生成段然後可以由組塊I到18構成。組塊19可以形成第二段的開始。注意，這將位置I中的數據一起置於單個段中，以及將位置4中的數據置於不同的單個段中。
[0046]該實施方式的許多變型是可能的。例如，取代縮短區域，規則可以包括丟棄閾值大小以下的最大區域並且按照所得到的潛在斷點的關聯區域有多大來對所得到的潛在斷點進行優先化排序。只有在較高優先級斷點落在最小和最大段大小要求之外時，才可能使用較低優先級斷點。
[0047]在至少一個示例中，兩個潛在斷點被不屬於任何區域的新數據分離。在這樣的情況下，可以確定斷點在兩個潛在斷點之間的任何地方而不影響哪些區域被打斷。在各種示例中，不同規則將允許在區域之間的中部處或在區域端之一處的斷點的選擇。
[0048]以上討論旨在說明本發明的原理和各種實施例。一旦以上公開內容被完全領會，大量變型和修改對本領域技術人員來說將變得顯而易見。意圖在於，隨附的權利要求應被解釋成涵蓋所有這樣的變型和修改。
【權利要求】
1.一種非暫時性計算機可讀存儲設備，包括可執行指令，所述可執行指令在被執行時使一個或多個處理器: 接收散列的序列，有待去重複的數據被分成數據組塊的序列，散列的序列中的每個散列包括對應數據組塊的散列； 確定所述數據組塊的先前存儲的副本的位置，所述位置是基於所述散列來確定的；以及 部分地基於確定的位置來確定數據組塊的序列中的斷點，所述斷點形成數據組塊段的邊界。
2.權利要求1的設備，其中指令還使一個或多個處理器作為整體去重複段。
3.權利要求1的設備，其中指令還使一個或多個處理器僅針對被包含在多個節點之一中的數據去重複段。
4.權利要求1的設備，其中所述位置是通過在索引、稀疏索引、集合或布隆過濾器中搜索所述散列中的一個或多個來確定的。
5.權利要求1的設備，其中確定斷點使一個或多個處理器: 部分地基於哪些數據組塊在相同位置中具有副本來確定數據組塊的序列中的區域； 基於所述區域來確定數據組塊的序列中的斷點。
6.權利要求5的設備，其中對於每個區域，存在其中具有確定的位置的數據組塊的至少90%具有先前存儲的副本的位置。
7.一種方法，包括: 由處理器接收散列的序列，有待去重複的數據被分成數據組塊的序列，散列的序列中的每個散列包括對應數據組塊的散列； 確定數據組塊的先前存儲的副本的位置；以及 部分地基於確定的位置來確定數據組塊的序列中的斷點，所述斷點形成數據組塊段的邊界。
8.權利要求7的方法，還包括作為整體去重複段。
9.權利要求7的方法，其中確定的位置是組塊容器、儲存器或存儲節點。
10.權利要求7的方法，其中所述位置是通過在索引、稀疏索引、集合或布隆過濾器中查找所述散列中的一個或多個來確定的。
11.權利要求7的方法，其中確定斷點包括: 部分地基於哪些數據組塊在相同的確定的位置中具有副本來確定數據組塊的序列中的區域； 基於所述區域來確定數據組塊的序列中的斷點。
12.權利要求11的方法，其中對於每個區域，存在其中具有確定的位置的數據組塊的至少90%具有先前存儲的副本的位置。
13.權利要求11的方法，其中確定位置包括查詢位置信息。
14.一種設備，包括: 一個或多個處理器； 耦合到處理器的存儲器； 所述一個或多個處理器執行下述操作: 接收散列的序列，有待去重複的數據被分成數據組塊的序列，散列的序列中的每個散列包括對應數據組塊的散列； 確定數據組塊的先前存儲的副本的位置，所述位置是基於所述散列來確定的；以及 基於所述位置來確定數據組塊的序列中的斷點，所述斷點形成數據組塊段的邊界。
15.權利要求14的設備，其中確定斷點包括: 部分地基於哪些數據組塊在相同的位置中具有副本來確定數據組塊的序列中的區域； 基於所述區域來確定數據組塊的序列中的斷點。
【文檔編號】G06F9/06GK104246720SQ201280072861
【公開日】2014年12月24日 申請日期:2012年5月1日 優先權日:2012年5月1日
【發明者】埃什希 K., M. 法爾金德 D., D. 利利布裡奇 M. 申請人:惠普發展公司，有限責任合夥企業