[發明專利]用于計算滾動散列的技術

有效

• 申請號: 201580064889.2
• 申請日: 2015-11-25
• 公開（公告）號: CN107004015B
• 公開（公告）日: 2021-01-29
• 發明（設計）人: J·D·吉爾福德;V·戈帕爾;G·B·塔克
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/23;G06F16/174;H03M7/30
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 王英;劉瑜

用于計算滾動散列的技術包括計算設備，其具有包括第一多個隨機值條目的第一散列表以及包括第二多個隨機值條目的第二散列表。所述計算設備從數據緩沖區取回數據塊，并且基于所述數據塊、先前生成的散列、所述第一散列表、以及所述第二散列表而生成散列。所述計算設備還確定所生成的散列是否與預先定義的觸發相匹配，并且響應于確定所述所生成的散列與所述觸發相匹配而記錄數據邊界。

與相關美國專利申請的交叉引用

本申請要求于2014年12月27日提交的、標題為“TECHNOLOGIES FOR COMPUTINGROLLING HASHES”的序列號為14/583,669的美國實用新型專利申請的優先權。

背景技術

數據去重涉及找到數據文件中的相似性(例如，副本)并且基于所識別的那些相似性來壓縮或者以其他方式減少所使用的存儲器。例如，替代將重復的數據存儲在存儲器的各個單元處，可以存儲該數據的單個副本并且可以用對該單個副本的引用來代替重復的實例。應當理解的是，所述引用常常比數據的重復的副本顯著地需要較少的存儲器來存儲。

與識別重復本身相關聯的算法傾向于是數據去重的較計算密集的方面，并且常常是在計算設備的通用處理器(例如，主處理器)上執行的。由此，這些算法的速度和質量是最重要的。用于識別數據重復一些算法，或者更加具體地，用于識別數據“分塊”的自然邊界一些算法包括滾動散列或指紋，其中具有固定大小的一組連續的字節的散列基于滾動基礎而被計算。簡單的算法可以涉及在每個單元處計算連續字節的散列，然而較復雜的算法(例如，Rabin Karp指紋)通過遞增地加上數據緩沖區中的下一字節的貢獻并且減去不再位于散列窗口內的字節的貢獻來嘗試降低計算開銷。

附圖說明

在附圖中作為示例而非限制示出了在本文中所描述的概念。為了說明的簡單和清楚，在圖中所示出的元件不一定是按比例繪制的。在適當地考慮的情況下，可以在附圖間重復附圖標記以指示對應的或類似的元素。

圖1是用于計算滾動散列的計算設備的至少一個實施例的簡化框圖；

圖2是圖1的計算設備的環境的至少一個實施例的簡化框圖；

圖3-4是可以由圖1的計算設備執行的、用于計算滾動散列的方法的至少一個實施例的簡化流程圖。

具體實施方式

盡管本公開的概念容易受到各種修改和可替代的形式的影響，但其具體的實施例已經作為示例在附圖中被示出并且將在本文中詳細地描述。然而，應當理解的是，沒有打算將本公開的概念限制至所公開的特定的形式，而相反，目的是覆蓋與本公開和所附權利要求相一致的所有修改、等同物、和替代物。

在說明書中對“一個實施例”、“實施例”、“說明性實施例”等的引用指示所描述的實施例可以包括特定的特征、結構、或特性，但每個實施例可以或可以不一定包括該特定的特征、結構、或特性。此外，這樣的短語不一定指的是同一實施例。此外，當結合實施例來描述特定的特征、結構、或特性時，所主張的是結合其他實施例(無論其是否進行了明確地描述)實現這樣的特征、結構、或特性也在本領域技術人員的知識范圍內。額外地，應當理解的是，以“至少一個A、B和C”的形式包括在列表中的項目可以意味著(A)；(B)；(C)；(A和B)；(B和C)；(A和C)；或者(A、B和C)。類似地，以“A、B或C中的至少一個”的形式列出的項目可以意味著(A)；(B)；(C)；(A和B)；(B和C)；(A和C)；或者(A、B和C)。

在一些情況下，可以以硬件、固件、軟件或其任何組合來實現所公開的實施例。還可以將所公開的實施例實現為由一個或多個瞬時性或者非瞬時性機器可讀(例如，計算機可讀)存儲介質所實行或存儲在其上的指令，所述指令可以由一個或多個處理器來讀取或執行。機器可讀存儲介質可以被實施為用于以能夠由機器讀取的形式存儲或發送信息的任何存儲設備、機制、或其他物理結構(例如，易失性或非易失性存儲器、媒體盤、或其他介質設備)。