• / 22
  • 下載費用:30 金幣  

用于對于數據傳遞的單遍熵檢測的設備和方法.pdf

摘要
申請專利號:

CN201610447012.8

申請日:

2016.06.20

公開號:

CN106257402A

公開日:

2016.12.28

當前法律狀態:

實審

有效性:

審中

法律詳情: 實質審查的生效IPC(主分類):G06F 3/06申請日:20160620|||公開
IPC分類號: G06F3/06 主分類號: G06F3/06
申請人: HGST荷蘭公司
發明人: A.納拉西姆哈; A.辛格海; V.卡拉姆切蒂; K.斯坎達庫馬蘭
地址: 荷蘭阿姆斯特丹
優先權: 2015.06.19 US 14/744,947
專利代理機構: 北京市柳沈律師事務所 11105 代理人: 李芳華
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201610447012.8

授權公告號:

|||

法律狀態公告日:

2018.04.13|||2016.12.28

法律狀態類型:

實質審查的生效|||公開

摘要

本發明的實施例包括存儲單元和耦接到存儲單元的處理器。該處理器可操作以分組來自所述輸入數據流的多個數據子集,并計算與第一分組的數據子集對應的第一哈希值。另外,該處理器可操作以檢測所述第一哈希值和哈希表中存儲的第二哈希值之間的匹配,監視所述輸入數據流的哈希值匹配頻率,其中所述處理器可操作以響應于所述匹配的檢測來遞增計數器值,并基于所述計數器值相對于頻繁哈希值匹配閾值來確定用于所述輸入數據流的熵級別。該處理器能生成以下指令,當所述計數器值滿足或超出所述頻繁哈希值匹配閾值時,初始化數據壓縮操作的執行,或者當所述計數器值未能滿足所述頻繁哈希值匹配閾值時,避免所述數據壓縮操作的所述執行。

權利要求書

1.一種設備,包括:
存儲單元,被配置為存儲數據流;和
處理器,耦接到所述存儲單元,所述處理器被配置為檢測在單遍期間輸入數據流的熵,
所述處理器可操作地分組來自所述輸入數據流的多個數據子集,計算與第一分組的數據子
集對應的第一哈希值,檢測所述第一哈希值和哈希表中存儲的第二哈希值之間的匹配,監
視所述輸入數據流的哈希值匹配頻率,
其中所述處理器可操作以響應于所述匹配的檢測來遞增計數器值,并基于所述計數器
值相對于頻繁哈希值匹配閾值來確定用于所述輸入數據流的一部分的熵級別,并且生成以
下指令,當所述計數器值滿足或超出所述頻繁哈希值匹配閾值時,初始化數據壓縮操作的
執行,或者當所述計數器值未能滿足所述頻繁哈希值匹配閾值時,避免所述數據壓縮操作
的所述執行。
2.根據權利要求1的設備,其中初始化所述數據壓縮操作的所述執行的所述指令導致
包括所述輸入數據流的壓縮部分的輸出。
3.根據權利要求1的設備,其中避免所述數據壓縮操作的所述執行的所述指令導致包
括所述輸入數據流的未壓縮部分的輸出。
4.根據權利要求1的設備,其中所述處理器可操作以生成當所述計數器值未能滿足所
述頻繁哈希值匹配閾值時、停止所述數據壓縮操作的執行的指令。
5.根據權利要求1的設備,其中所述處理器可操作以計算用于所述多個數據子集的每
一數據子集的簽名,并且所述匹配表示與具有相同簽名的所述輸入數據流相關的至少兩個
分組的數據子集。
6.根據權利要求1的設備,其中所述處理器可操作以基于當前系統負荷調整所述頻繁
哈希值匹配閾值。
7.根據權利要求1的設備,其中所述處理器可操作以基于用戶偏好調整所述頻繁哈希
值匹配閾值。
8.一種檢測在單遍期間輸入數據流的熵的計算機實現的方法,所述方法包括:
接收輸入數據流;
分組來自所述輸入數據流的多個數據子集;
計算與第一分組的數據子集對應的第一哈希值;
檢測所述第一哈希值和哈希表中存儲的第二哈希值之間的匹配,并響應于所述匹配的
檢測來遞增計數器值;
監視所述輸入數據流的哈希值匹配頻率;
基于所述計數器值相對于頻繁哈希值匹配閾值,來確定用于所述輸入數據流的一部分
的熵級別;和
生成以下指令,當所述計數器值滿足或超出所述頻繁哈希值匹配閾值時,初始化數據
壓縮操作的執行,或者當所述計數器值未能滿足所述頻繁哈希值匹配閾值時,避免所述數
據壓縮操作的所述執行。
9.根據權利要求8的計算機實現的方法,其中初始化所述數據壓縮操作的所述執行的
所述指令導致包括所述輸入數據流的壓縮部分的輸出。
10.根據權利要求9的計算機實現的方法,其中避免所述數據壓縮操作的所述執行的所
述指令導致包括所述輸入數據流的未壓縮部分的輸出。
11.根據權利要求8的計算機實現的方法,其中所述生成步驟進一步包括生成當所述計
數器值未能滿足所述頻繁哈希值匹配閾值時、停止所述數據壓縮操作的執行的指令。
12.根據權利要求8的計算機實現的方法,其中所述分組進一步包括計算用于所述多個
數據子集的每一數據子集的簽名,并且所述匹配表示與具有相同簽名的所述輸入數據流相
關的至少兩個分組的數據子集。
13.根據權利要求8的計算機實現的方法,進一步包括:
基于當前系統負荷調整所述頻繁哈希值匹配閾值。
14.根據權利要求8的計算機實現的方法,進一步包括:
基于用戶偏好調整所述頻繁哈希值匹配閾值。
15.一種設備,包括:
存儲單元,配置為存儲數據流;和
處理器,耦接到所述存儲單元,所述處理器被配置為檢測在單遍期間輸入數據流的熵,
所述處理器可操作地計算來自所述輸入數據流的多個數據子集的每一數據子集的簽名,計
算與第一分組的數據子集對應的第一哈希值,檢測所述第一哈希值和哈希表中存儲的第二
哈希值之間的匹配,監視所述輸入數據流的哈希值匹配頻率,
其中所述處理器可操作以響應于所述匹配的檢測來遞增計數器值,并基于所述計數器
值相對于頻繁哈希值匹配閾值來確定用于所述輸入數據流的一部分的熵級別,并且生成以
下指令,當所述計數器值滿足或超出所述頻繁哈希值匹配閾值時,初始化數據縮減操作的
執行,或者當所述計數器值未能滿足所述頻繁哈希值匹配閾值時,避免所述數據縮減操作
的所述執行。
16.根據權利要求15的設備,其中初始化所述數據縮減操作的所述執行的所述指令導
致包括所述輸入數據流的壓縮部分的輸出。
17.根據權利要求15的設備,其中避免所述數據縮減操作的所述執行的所述指令導致
包括所述輸入數據流的未壓縮部分的輸出。
18.根據權利要求15的設備,其中所述數據縮減操作是數據消重操作。
19.根據權利要求15的設備,其中所述數據縮減操作是數據壓縮操作。
20.根據權利要求15的設備,其中所述處理器可操作以基于當前系統負荷調整所述頻
繁哈希值匹配閾值。
21.根據權利要求15的設備,其中所述處理器可操作以基于用戶偏好調整所述頻繁哈
希值匹配閾值。

說明書

用于對于數據傳遞的單遍熵檢測的設備和方法

相關申請的交叉引用

該申請涉及與該申請并發提交的具有代理人卷號HGST-H20151036US1的專利申
請:“APPARATUS AND METHOD FOR INLINE COMPRESSION AND DEDUPLICATION”,其在這里通
過引用被全部合并。

技術領域

本公開一般涉及數據縮減技術的領域。

背景技術

高性能非易失性儲存類別存儲子系統一般包括相對昂貴的組件。這樣,高度期望
使用數據縮減技術使得這樣的系統中的數據儲存最大化。數據縮減表示數據自壓縮和數據
消重(deduplication)的技術,以縮減向后端儲存系統寫入或從后端儲存系統讀取的信息
總量。數據縮減導致用戶(輸入)數據向能存儲的更緊湊表示的變換。數據縮減的優點包括
除了別的優點之外的、改進的儲存利用、增加的壽命(在全閃存儲存系統的上下文中)、和應
用加速。

數據壓縮表示尋找相同數據塊內的冗余度并然后按照縮減數據總體尺寸的方式
來編碼這些重復的序列的處理。數據消重表示即使個別塊具有不可壓縮的數據、仍為了找
到匹配序列而跨過多個塊匹配數據序列的處理。然而,傳統系統執行壓縮和數據消重作為
數據縮減處理中的分離步驟。這樣,這些傳統系統不將他們組合為單一步驟,并因此付出等
待時間(latency)和帶寬懲罰(penalties)。

此外,傳統數據縮減方案花費大量周期和功率以便執行壓縮功能。在任何給定應
用數據流中,總是存在數據塊的特定集合可以不呈現自壓縮屬性(properties)的高概率。
典型地,在壓縮階段的結束,傳統方案執行檢查以確保結果不大于原始塊。因此,因為在嘗
試壓縮數據時已利用了資源,所以這是相當遲的。

發明內容

因此,存在對于以下方案的需求,即創建在單遍(single pass)中執行數據壓縮和
消重兩者的統一數據路徑。本發明的實施例組合數據壓縮技術,并通過將它們與數據消重
方法合并來擴充它們。本發明的實施例的單遍本質(nature)允許系統等待時間的控制,并
幫助實現更高速度的線速率壓縮和消重(例如,按照能滿足用于給定FPGA的PCIe Gen3速
度、或其他速度需求或標準的方式)。

本發明的實施例利用較小的數據子集(諸如4千字節尺寸數據塊)用于壓縮,并且
能推翻(override)壓縮編碼副本格式,以區分自我參考的副本和參考參考塊的副本。應理
解的是,實施例不限于4千字節尺寸數據塊,并且能使用任何塊尺寸或塊尺寸的范圍(例如,
4kb、8kb、10kb、4kb–8kb塊尺寸范圍等)。實施例能創建以下存儲緩沖器結構,其具有多個并
行輸入緩沖器以保存參考數據塊。而且,實施例可包括并行哈希表查找方案,其中能與對于
輸入數據緩沖器中存儲的數據的哈希查找同時地、執行與參考數據塊緩沖器中存儲的數據
對應的搜索。

另外,為了增強數據縮減性能的目的,實施例能使用參考數據緩沖器的填充時間,
以計算和存儲參考數據的疊瓦(shingled)哈希函數值。實施例還能創建參考哈希表計算和
壓縮開始之間的互鎖。按照該方式,當壓縮開始時,能在參考哈希表、壓縮哈希表、或兩者中
執行搜索。本發明的實施例能使用試探法(heuristics)來確定當在哈希表的一個或多個中
檢測到哈希命中時使用哪個序列(如果存在任一個的話)。此外,本發明的實施例能修改用
于輸入數據流或來自輸入參考緩沖器的回溯引用(back-reference)解釋。

此外,本發明的實施例能早期檢測并預測塊的可壓縮性,以便使得浪費的努力最
小化并避免總體系統性能的損耗。這里描述的實施例能分析可壓縮性特性,以作出對于給
定數據塊執行數據縮減過程(諸如壓縮)的判斷。這樣,當給定不可壓縮的數據時,能按照使
得高性能數據縮減系統能節約功率和壓縮單元周期的方式,來執行低影響-高性能熵檢測
操作。

附圖說明

該說明書中合并的、并且形成其一部分的、并且其中相同附圖標記描繪相同元件
的附圖圖示了本公開的實施例,并且和該描述一起,用來解釋本公開的原理。

圖1A是描繪了根據本發明實施例的為了數據縮減的目的能夠并行執行雙壓縮和
消重過程的直列(inline)壓縮和消重系統的示范硬件配置的框圖。

圖1B是描繪了根據本發明實施例的用于執行直列壓縮和消重過程的存儲器中提
供的示范組件的框圖。

圖1C描繪了根據本發明實施例生成的示范壓縮數據成幀格式。

圖1D描繪了根據本發明實施例的示范組合參考哈希表和壓縮哈希表查找方案。

圖2A是根據本發明實施例的用于單遍熵檢測的示范處理的第一部分的流程圖。

圖2B是根據本發明實施例的用于單遍熵檢測的示范處理的第二部分的流程圖。

圖3A是根據本發明實施例的用于同時數據消重和壓縮的示范處理的流程圖。

圖3B是根據本發明實施例的用于執行哈希表查找過程的示范處理的流程圖。

具體實施方式

現在將對本發明的優選實施例進行詳細參考,其示例在附圖中進行了圖示。盡管
將結合優選實施例描述本發明,但是將理解的是,它們并不意欲將本發明限于這些實施例。
相反,本發明意欲覆蓋可在所附權利要求所限定的本發明的精神和范圍內包括的替換、修
改和等效。

此外,在本發明的實施例的以下詳細描述中,闡明許多特定細節,以便提供本發明
的透徹理解。然而,本領域技術人員將認識到,可在沒有這些特定細節的情況下實踐本發
明。在其他實例中,還沒有詳細描述公知方法、過程、組件、和電路,以便不會不必要地模糊
本發明的實施例的各方面。盡管為了清楚方法可被描繪為編號的步驟的序列,但是該編號
并非必須規定這些步驟的順序。

應當理解的是,一些步驟可被跳過、并行執行、或在沒有維持序列的嚴格順序的需
求的情況下執行。示出本發明的實施例的圖是半圖解的(semi-diagrammatic)并且不按照
比例繪制,并且特別是,一些維度是為了呈現的清楚,并在制圖的圖中被夸大示出。類似地,
盡管為了易于描述圖中的視圖一般示出類似方位,但是圖中的該描繪對于絕大部分是任意
的。一般,本發明能按照任何方位操作。

符號和術語:

然而,應注意的是所有這些和類似術語應與適當物理量關聯,并僅是向這些量應
用的便利標簽。除非特別闡明,否則如同根據以下討論清楚的那樣,理解貫穿本發明,利用
諸如“接收”或“選擇”或“生成”或“分組”或“監視”等的術語的討論表示計算機系統或類似
電子計算裝置的動作和處理,所述計算機系統或類似電子計算裝置操縱計算機系統的寄存
器和存儲器以及其他計算機可讀介質中的表示為物理(例如,電子)量的數據,并變換為計
算機系統存儲器或寄存器或其他這樣的信息儲存、傳送或顯示裝置中的類似表示為物理量
的其他數據。當組件在幾個實施例中出現時,相同附圖標記的使用意味著該組件是與原始
實施例中圖示的組件相同的組件。

示范直列壓縮和消重系統配置

圖1A是描繪了根據本發明實施例的為了數據縮減的目的能夠并行執行雙壓縮和
消重過程的直列壓縮和消重系統(例如,系統100)的示范硬件配置的框圖。按照該方式,系
統100能在單遍中執行數據縮減過程,使得將與諸如數據壓縮和數據消重的數據縮減過程
相關的操作組合為單一處理、單一處理路徑或單一步驟,由此降低一般系統等待時間和/或
帶寬懲罰。盡管圖1A中公開了特定組件,但是應理解這樣的組件是示范性的。即,本發明的
實施例將適當適于具有各種其他硬件組件或圖1A中闡明的組件的變型。理解圖1A中的硬件
組件能利用除了呈現的組件之外的組件操作,并且并非需要圖1A中描述的全部硬件組件來
實現本發明的目的。根據一些實施例,能組合圖1A中描繪的組件以實現本發明的目的。

系統100能被實現為能夠通過數據通信總線與其他電子裝置通信的電子裝置。例
如,總線106描繪這樣的數據通信總線。其上可實現本公開的實施例的示范系統100包括通
用目的計算系統環境。在其最基本配置中,系統100典型地包括至少一個處理單元101和存
儲儲存單元。例如,計算機可讀儲存介質104描繪這樣的存儲儲存單元。取決于裝置的精確
配置和類型,計算機可讀儲存介質104能夠是易失性(諸如RAM)、非易失性(諸如ROM、閃存)
或這兩者的一些組合。計算機可讀儲存介質104的部分,當運行時,促進存儲操作的有效運
行或對于多組線程的請求。

在一個實施例中,處理器101能夠是被配置為執行這里描述的直列壓縮和消重操
作的可編程電路。例如,處理器101能夠是FPGA控制器或閃存裝置控制器。作為選擇,在一個
實施例中,處理器101能夠可操作以運行直列壓縮和消重程序,所述程序被存儲在計算機可
讀儲存介質104中并被配置為執行這里描述的功能(見,例如下面討論的圖1B)。系統100還
可以包括可選圖形系統105,用于例如通過在可選顯示裝置102上顯示信息,而向計算機用
戶呈現信息。系統100還包括可選字母數字輸入/輸出裝置103。輸入/輸出裝置103能包括可
選光標控制或指引裝置、以及一個或多個信號通信接口(諸如網絡接口卡)。此外,接口模塊
115包括允許系統100通過電子通信網絡(例如,因特網、有線通信網、無線通信網或類似網
絡)與其它計算機系統通信的功能性。

另外,系統100還可以具有附加特征和功能性。例如,系統100還可以包括附加儲存
介質(可移除和/或不可移除),包括但不限于,磁或光盤或帶。計算機儲存介質包括按照用
于儲存諸如計算機可讀指令、數據結構、程序模塊或其它數據的信息的任何方法或技術實
現的易失性和非易失性、可移除和不可移除介質。

圖1B是描繪了根據本發明實施例的用于執行直列壓縮和消重過程的存儲器中提
供的示范組件的框圖。盡管圖1B中公開了特定組件,但是應理解的是,這樣的計算機儲存介
質組件是示范性的。即,本發明的實施例適當適于具有具有各種其他硬件組件或圖1B中闡
明的計算機儲存介質組件的變型。理解圖1B中的硬件組件能利用除了呈現的組件之外的其
它組件操作,并且并非需要圖1B中描述的全部計算機儲存介質組件來實現本發明的目的。
根據一些實施例,能組合圖1B中描繪的組件以實現本發明的目的。此外,理解的是,為了實
現本發明的目的的目標,圖1A中描述的一些硬件組件能與圖1B中描述的一些組件組合操
作。

如圖1B中描繪的,計算機可讀儲存介質104包括操作系統107。當系統100初始化
時,操作系統107被裝載到處理器101中。而且,當由處理器101運行時,操作系統107能被配
置以向系統100供應可編程接口。系統100還能包括無線通信機制。通過這些裝置,系統100
能通過諸如互聯網或內聯網(例如局域網)的通信網絡可通信地耦接到其它計算機系統。

此外,如圖1B中圖示的,計算機可讀儲存介質104包括指紋計算引擎110。指紋計算
引擎110包括為了執行驗證和/或查找過程的目的、使用字節序列生成指紋的功能性。在檢
測到數據流的接收時,緩沖器管理控制器112能向指紋計算引擎110傳遞信號,以在其接收
時處理數據輸入緩沖器112-1中存儲的數據。

能使用指紋計算引擎110所生成的指紋來表示較大文件,同時使用用于存儲這樣
的較大文件按照別的方式所需要的儲存空間的一部分。例如,較大文件能包括多頁內容或
多媒體文件。指紋計算引擎110能使用傳統計算機實現的過程,諸如哈希函數,以為了生成
指紋的目的而將數據流縮減為數據比特,從而能由系統100的組件(諸如簽名計算引擎113)
處理。哈希計算可按照與系統100的其它組件(諸如哈希表模塊111)如何計算哈希值的方式
一致的方式或按照不同的方式來執行。

按照該方式,指紋計算引擎110能被配置以生成與系統100原樣接收的數據流關聯
的進入數據的子集的指紋。例如,數據的子集能夠是4千字節增量的形式。在一個實施例中,
指紋計算引擎110能計算與系統100所接收的并在緩沖器管理控制器112所生成的數據輸入
緩沖器112-1中存儲的數據流關聯的4千字節的進入集合的指紋。

簽名計算引擎113包括計算系統100所接收的數據流的簽名的功能性。簽名能由簽
名計算引擎113基于各種傳統的基于哈希的簽名方案來計算,所述方案包括Merkle、
Spooky、CRC、MD5、SHA或類似方案。簽名計算引擎113能被配置為使用子塊簽名計算、基于拉
賓簽名的相似度檢測計算、和/或其它基于相似度的簽名計算,對系統100所接收的數據流
執行簽名計算。根據一個實施例,簽名計算引擎113能使用指紋計算引擎110所生成的指紋
數據以生成簽名。在一個實施例中,在接收到數據流時,緩沖器管理控制器112能被配置為
向簽名計算引擎113傳遞信號,以在其接收時處理數據緩沖器112-1中存儲的數據。

簽名計算引擎113能被配置為對于輸入數據流的各個部分偶爾計算用于數據子集
的多個簽名。按照該方式,簽名計算引擎113對于子集計算的簽名能被傳遞到系統100的其
它組件用于進一步處理,諸如參考塊標識模塊114。例如,簽名計算引擎113所計算的簽名能
包括允許它們相似或相同的數學屬性,如果對彼此相似或相同的塊計算它們的話。這樣,系
統100的組件(諸如參考塊標識模塊114)所選擇的參考塊能基于最好地表示系統100上駐留
的存儲器中存儲的多個相似簽名簇的計算的簽名。由此,系統100的組件能使用簽名計算引
擎113所計算的簽名,來執行參考塊標識過程。例如,參考塊標識模塊114能使用子塊簽名來
執行參考塊標識過程。

參考塊標識模塊114包括以下功能性,即,分析簽名計算引擎113所生成的多個不
同簽名簇,并選擇系統100的組件(諸如哈希表模塊111)能處理的參考塊。參考塊標識模塊
114能被配置為比較計算的簽名和系統100當前存儲的簽名簇,并對應地選擇最佳表示所計
算的簽名的參考塊。例如,參考塊標識模塊114能被配置為比較計算的簽名和緩沖器管理控
制器112所生成的緩沖器中當前存儲的簽名簇,并對應地選擇最佳表示所計算的簽名的參
考塊。

參考塊標識模塊114所選擇的參考塊能被存儲在緩沖器管理控制器112所生成的
緩沖器(諸如參考塊緩沖器112-3)中,用于由系統100的組件進一步處理。參考塊能夠是通
過各種方法已被發現與輸入數據相似的規則數據塊。例如,參考塊能夠是通過使用子塊簽
名、相似度檢測機制、應用暗示檢測方案或類似方案計算、已被發現與輸入數據相似的規則
數據塊。參考塊還可以是包括被發現具有較大重復因子的重復數據序列的純合成塊。根據
一個實施例,參考塊標識模塊114能被配置為使用先驗知識、內容相似度匹配、應用暗示、數
據圖案識別、或類似手段來標識參考塊。

此外,關于參考塊標識模塊114所標識的參考塊(諸如參考塊緩沖器112-3中存儲
的參考塊)的信息能被存儲在數據流的報頭部分中。例如,參考圖1C,參考塊標識模塊114所
標識的參考塊的參考塊標識符能被存儲在數據流116的報頭部分116a中。如圖1C中圖示的,
報頭數據116a能連同它們的相應壓縮的有效載荷數據部分(諸如壓縮有效載荷116b)一起
被包括在數據顆粒的集合中,諸如數據顆粒116-1、116-2和116-N。在一個實施例中,除了比
特向量117-2、顆粒計數117-3和/或報頭CRC數據117-4之外,報頭數據116a能存儲參考標識
符117-1。

參考圖1B,哈希表模塊111包括基于與系統100接收的數據流關聯的數據計算哈希
值并動態生成哈希表的功能性。在接收到數據流時,緩沖器管理控制器112能向哈希表模塊
111傳遞信號,以處理在每一緩沖器接收到數據時、在數據輸入緩沖器112-1和/或參考塊緩
沖器112-3中存儲的數據。哈希表模塊111包括計算能在生成的哈希表中存儲的、與系統100
所接收的數據流關聯的數據的子集(例如,數據的字節)的哈希值的功能性。例如,哈希表模
塊111能計算與系統100所接收的數據流關聯的數據的字節的哈希值。這樣,能按照加速重
復數據序列的搜索的方式,通過流行高性能壓縮方案來利用哈希表模塊111。例如,能通過
流行高性能壓縮方案來利用哈希表模塊111,所述方案包括Snappy、Lempel-Ziv(LZ)壓縮方
案、Gzip或類似方案。

數據的子集可以是預定的固定尺寸,并且為了執行消重過程的目的能被使用來表
示較大文件。這樣,哈希表模塊111能計算系統100接收的數據的每一字節的哈希值。按照該
方式,哈希表模塊111能與它們的接收和在緩沖器管理控制器112所生成的緩沖器中的存儲
同時地,計算數據的子集的哈希值。此外,可按照與系統100的其它組件(諸如指紋計算引擎
110)如何計算哈希值的方式一致的方式或按照不同的方式,來執行哈希計算。

根據一個實施例,哈希表模塊111包括基于參考塊標識模塊130所標識的參考數據
塊、動態生成參考哈希表的功能性。一旦由參考塊標識模塊114選擇,與參考塊對應的數據
塊就能被存儲在參考塊緩沖器(諸如參考塊緩沖器112-3)中。當正存儲參考塊時,哈希表模
塊111能被配置為計算與所述參考塊對應的疊瓦哈希值。按照該方式,哈希表模塊111能生
成能加速系統100所執行的壓縮和消重過程的性能的預先計算的哈希表。

例如,參考圖1B,當字節的集合由系統100所接收、并被存儲在系統100上駐留的數
據輸入緩沖器112-1中時,哈希表模塊111能將參考塊標識模塊114所確定和/或選擇的參考
塊的哈希值計算為對應于接收的字節的集合。當參考數據塊被存儲在緩沖器管理控制器
112動態生成的參考數據塊緩沖器112-3中時,哈希表模塊111計算這些哈希值。按照該方
式,緩沖器管理控制器112包括創建參考數據塊緩沖器的功能性,所述參考數據塊緩沖器能
并行系統100上駐留的數據輸入緩沖器(諸如數據輸入緩沖器112-1)的功能性。這樣,這些
計算的參考塊哈希值然后能所以被存儲在哈希表模塊111所生成的參考哈希表111-1中。

哈希表模塊111包括使用系統100所接收的和/或數據輸入緩沖器中存儲的數據
流、來動態生成壓縮哈希表的功能性。此外,哈希表模塊111包括修改和/或生成能用來隨后
解壓和/或重構系統100先前處理的數據流的編碼后數據的功能性。按照該方式,哈希表模
塊111能被配置來在壓縮操作期間在相似數據序列的標識時修改和/或編碼報頭數據。這
樣,哈希表模塊111能生成編碼后數據,該編碼后數據包括與哈希表模塊111先前標識的已
存儲數據對應的參考標識符。

例如,哈希表模塊111能生成和/或修改編碼后報頭數據,所述編碼后報頭數據包
括在哈希計算過程的完成時、由哈希表模塊111標識的未壓縮數據字節的數目,諸如標識的
文字的數目。按照該方式,哈希表模塊111生成的編碼后數據能提供關于解壓模塊如何能解
壓或解碼文字和/或副本元素的指令,所述元素對應于與經受解壓過程的數據流關聯的字
節集合。副本元素能包括要拷貝的字節(“長度”)和/或要拷貝的數據返回多遠(“偏移”)。

例如,在一個實施例中,哈希表模塊111生成和/或修改的報頭數據能包括標識的
文字的表示和對應文字數據序列。這樣,解壓模塊108能讀取提供關于模塊如何能解壓文字
序列的指令的、編碼后和/或修改后報頭信息。此外,解壓模塊108能被配置為基于例如
Snappy、LZ壓縮方案、Gzip或類似方案的各種壓縮方案來執行解壓過程。

根據一個實施例,假如至少一個參考塊被選擇并指定用于存儲在參考塊緩沖器
中,則哈希表模塊111能向系統100的組件發送信號,以使用參考哈希表和/或壓縮哈希表執
行哈希表查找和/或報頭修改過程,用于基于計算的哈希值的進一步處理。按照該方式,哈
希表模塊111能創建參考哈希表計算和解壓過程開始之間的互鎖。此外,哈希表模塊111對
于壓縮哈希表和參考哈希表執行的哈希計算過程能夠是相同的計算機實現的過程或功能
或者是不同的計算機實現的過程或功能。

表格I提供了能夠由本發明實施例修改的報頭格式或回溯引用編碼格式變型的示
范集合。

壓縮報頭
含義
00
文字,最大長度60字節
01
本地副本、3比特長度、11比特偏移
10
本地副本、6比特長度、12比特偏移
11
參考副本、12比特長度、12比特偏移

表格I

掃描和匹配引擎109包括執行哈希表查找過程和執行哈希值比較的功能性。掃描
和匹配引擎109包括以下功能性,即,發送和/或接收來自哈希表模塊111的信號,以執行用
于針對系統100當前存儲的參考數據塊比較所計算的數據子集的哈希值的計算機實現的查
找過程。

掃描和匹配引擎109能使用哈希表查找引擎來定位由哈希表模塊111生成的哈希
表中的計算的哈希值,并比較數據。例如,哈希表模塊111能生成參考哈希表111-1和壓縮哈
希表111-2并執行比較操作。這樣,掃描和匹配引擎109能被配置以在緩沖器管理控制器112
所生成的緩沖器(諸如參考塊緩沖器112-3)中針對系統100當前存儲的參考數據塊查找所
計算的字節的子集的哈希值。

按照該方式,掃描和匹配引擎109能在哈希表模塊111創建的參考哈希表和壓縮哈
希表兩者中執行并行或同時搜索。當執行這樣的查找過程時,掃描和匹配引擎109還能執行
用于針對存儲的參考數據塊和/或與哈希表模塊111先前標識的數據對應的壓縮哈希值,來
比較系統100所接收的字節的隨后集合的過程。

例如,參考圖1D,當通過參考塊標識模塊114標識參考塊118時,哈希表模塊111在
參考哈希表111-1中存儲與參考塊緩沖器中原樣存儲的參考塊118的一部分(例如,用于參
考塊數據子集118-1、118-2、118-3、118-4等的值)對應的所計算的哈希值條目。按照該方
式,系統100能使用參考數據緩沖器的填充時間,以計算和存儲與參考塊118對應的參考數
據的疊瓦哈希函數值,這增強了系統100所執行的壓縮和消重過程的性能。

此外,如圖1D中圖示的,系統100還能接收與進入數據流關聯的輸入數據塊120。這
樣,掃描和匹配引擎109能使用哈希表邏輯109-3,以使用增添數據的(populated)參考哈希
表111-1和壓縮哈希表111-2執行并行查找過程,以標識與接收的數據塊120類似的先前存
儲的數據序列。按照該方式,掃描和匹配引擎109能以每一字節為基礎使用數據和參考塊的
較小子集(例如,輸入數據塊數據子集120-1)來執行比較。

如果掃描和匹配引擎109檢測到參考哈希表111和/或壓縮哈希表111-2中的條目
與所計算的數據塊120的哈希值之間的匹配,則掃描和匹配引擎109能對應地向解壓模塊
108發送信號,以使用修改的壓縮報頭格式(諸如這里描述的回溯引用編碼格式變型)來解
壓參考塊緩沖器或數據輸入緩沖器中的數據的子集。因此,解壓的輸出能然后被存儲在緩
沖器管理控制器112所生成的緩沖器中,諸如數據輸出緩沖器112-2。

在一個實施例中,在解壓過程的執行期間,解壓模塊108能被配置以當掃描和匹配
引擎109檢測到參考哈希表111-1和/或壓縮哈希表111-2的任一個的匹配時、選擇多個不同
序列之一。例如,基于預定啟發,解壓模塊108能被配置以解壓數據作為文字、本地副本、和/
或參考副本。按照該方式,在解壓時,系統100能創建相似參考數據輸入緩沖器,使得能修改
解壓實現,以從輸入數據流或參考塊緩沖器解釋回溯引用。

這樣,解壓模塊108能被配置以處理掃描和匹配引擎109所使用的文字掃描邏輯
109-1和/或本地副本掃描邏輯109-2。能理解的是,本發明的實施例不限于使用單一參考
塊。實施例能被擴展到包括多個參考塊,具有對于現有數據路徑和幀結構的簡單變型。例
如,實施例能被擴展為并行執行的多個參考塊比較。此外,哈希表模塊111能被配置以生成
與不同參考塊集合的相應參考塊對應的多個參考哈希表。此外,能在哈希表模塊111所生成
的單一參考哈希表中存儲多個參考塊。

此外,系統100能被配置以早期檢測,并在數據縮減操作(諸如這里描述的那些)的
執行之前預測塊的可壓縮性,以便使得浪費的努力最小化并避免總體系統性能的損耗。例
如,解壓模塊108包括對系統100所接收的數據執行分組過程的功能性。這樣,解壓模塊108
能包括數據分組邏輯108-1,其允許解壓模塊108將經由數據輸入緩沖器112-1接收的進入
數據分組為能在單一實例中處理或操作的數據字節或“疊瓦”的子集。按照該方式,哈希表
模塊111能對于由解壓模塊108通過數據分組邏輯108-1所選擇的重疊數據疊瓦計算哈希
值。此外,哈希表模塊111對于重疊疊瓦所計算的哈希值能被用作存儲地址位置,其代表疊
瓦偏移值被存儲在數據結構(諸如壓縮哈希表111-2和/或系統100上駐留的存儲器)中的哪
里。

另外,掃描和匹配引擎109能使用哈希表模塊111來定位計算的疊瓦,并且當它們
被寫入到數據輸入緩沖器112-1時,并行地對數據塊執行比較操作。例如,使用壓縮哈希表
111-2,如果確定對于與進入數據集相關的疊瓦的計算的哈希值與壓縮哈希表111-2中存儲
的哈希值共享相同簽名,則掃描和匹配引擎109能檢測“哈希命中”的發生。按照該方式,當
兩個疊瓦具有簽名計算引擎113所計算的相同或相似簽名時,掃描和匹配引擎109能檢測哈
希命中的發生。

此外,掃描和匹配引擎109包括向解壓模塊108發送信號以遞增可壓縮性計數器
(例如哈希命中計數器111-3)的功能性。按照該方式,每當掃描和匹配引擎109檢測到哈希
命中的發生時,哈希命中計數器111-3能遞增。哈希命中計數器111-3允許系統100明了
(keep track of)在系統100所接收的進入數據集中頻繁出現的哈希值。因此,在數據傳遞
到數據輸入緩沖器112-1中的結束時,系統100能存儲用于整個數據集的計算的哈希的集
合。

另外,系統100能被配置以存儲頻繁哈希值匹配閾值,該閾值使得能夠較好確定哪
些數據塊將從具有對其執行的數據縮減過程(例如,數據消重過程、參考塊標識過程、數據
壓縮過程等)受益最多。按照該方式,系統100能按照以下方式配置,即,允許其使用預定閾
值和/或計算的可壓縮性計數,來自動解釋可壓縮性特性。例如,在系統100的任何數據縮減
過程的執行之前,其能首先參考預定閾值計數,并判斷是否執行、暫停和/或停止數據縮減
操作。

按照該方式,當閾值計數滿足或超出頻繁哈希值匹配閾值時,諸如解壓模塊108的
系統100的組件能生成命令系統100的組件初始化數據縮減操作(例如,數據消重過程、參考
塊標識過程、數據壓縮過程等)的執行的指令或指令集。因此,當該閾值計數未能滿足頻繁
哈希值匹配閾值時,系統100的組件能生成命令系統100的組件避免執行數據縮減操作的指
令或指令集。系統100的這樣的確定不僅能節約主機CPU周期,而且還能允許數據在系統中
移動,而不中斷其它驅動器,諸如主機驅動器。

例如,在一個實施例中,如果哈希命中計數器111-3的值低于預定閾值,則解壓模
塊108可確定當前分析下的數據塊呈現低可壓縮性特性,由此證明用于該數據流的至少一
部分的高熵級別。因此,響應于該確定,解壓模塊108能被配置以不執行任何解壓操作。按照
該方式,解壓模塊108能被配置以發送暫停和/或停止解壓操作的執行的指令。

然而,如果哈希命中計數器111-3的值等于或高于預定閾值,則解壓模塊108可確
定數據塊呈現高可壓縮性特性,由此證明用于該數據流的至少一部分的低熵級別。因此,響
應于該確定,解壓模塊108能被配置以發送初始化解壓操作的執行的指令。按照該方式,解
壓模塊108使用可壓縮性因子來確定對于與數據輸入緩沖器112-1中存儲的進入數據集相
關的字節的給定集合、是否向系統100的其他組件發布“壓縮”或“繞開壓縮”信號。

按照該方式,系統100能基于檢測的給定數據集的數據塊之間的相似度的頻率,來
測量與數據輸入緩沖器112-1中存儲的數據集相關的熵。根據一個實施例,掃描和匹配引擎
109能使用數據的直方圖表示,來計算哈希命中的頻率。因此,哈希命中計數器111-3能通過
硬件或軟件實現。

此外,系統100能被配置以基于系統負荷和/或用戶偏好來動態調整閾值。按照該
方式,為了在損害功率和等待時間的情況下增加壓縮比率的目的,用于壓縮的閾值能夠是
不嚴格的。類似地,為了實現較低平均等待時間,能使用較高閾值。

圖2A是根據本發明實施例的用于單遍熵檢測的示范處理的第一部分的流程圖。

在步驟205,輸入數據流由系統接收并存儲在數據輸入緩沖器中。在接收到該數據
流時,解壓模塊使用數據分組邏輯,以對在數據輸入流中發現的多個數據子集進行分組。這
些子集的尺寸能夠是預定的和固定尺寸的。

在步驟206,使用由指紋計算引擎對于該數據輸入緩沖器中存儲的數據生成的指
紋數據,簽名計算引擎計算在步驟205期間被原樣存儲的數據流中的的第一簽名。

在步驟207,哈希表模塊計算用于第一分組的數據子集的第一哈希值,并針對哈希
表中存儲的哈希值比較計算的哈希值,以檢測匹配。

在步驟208,哈希表模塊計算用于第二分組的數據子集的第二哈希值,并針對哈希
表中存儲的哈希值比較計算的哈希值,以檢測匹配。

在步驟209,哈希表模塊計算用于第n分組的數據子集的第n哈希值,并針對哈希表
中存儲的哈希值比較計算的哈希值,以檢測匹配。

在步驟210,解壓模塊監視哈希表模塊所檢測的匹配,并對于每一檢測的匹配對應
遞增計數器。

圖2B是根據本發明實施例的用于單遍熵檢測的示范處理的第二部分的流程圖。圖
2B中概括了操作210(見圖2A)的細節。

在步驟211,解壓模塊基于相對于預先確定的頻繁哈希值匹配閾值的計數器的值,
來確定對于輸入數據流的一部分的熵級別。

在步驟212,解壓模塊進行關于其是否檢測到已滿足或超出頻繁哈希值匹配閾值
的判定。如果解壓模塊檢測到已滿足或超出頻繁哈希值匹配閾值,則解壓模塊確定用于該
輸入數據流的至少一部分的高熵級別,并對應地將信號傳遞到系統組件以初始化數據縮減
操作的執行,如步驟213中詳述的那樣。如果解壓模塊檢測到還沒有滿足頻繁哈希值匹配閾
值,則解壓模塊確定用于該輸入數據流的一部分的低熵級別,并對應地將信號傳遞到系統
組件以暫停數據縮減操作的執行,如步驟214中詳述的那樣。

在步驟213,解壓模塊檢測到已滿足或超出頻繁哈希值匹配閾值,并所以解壓模塊
確定用于輸入數據流的一部分的高熵級別,并對應地將信號傳遞到系統組件,以初始化數
據縮減操作的執行。

在步驟214,解壓模塊檢測到還沒有滿足頻繁哈希值匹配閾值,并所以解壓模塊確
定用于輸入數據流的一部分的低熵級別,并對應地將信號傳遞到系統組件,以暫停數據縮
減操作的執行。

圖3A是根據本發明實施例的用于同時數據消重和壓縮的示范處理的流程圖。圖3A
中概括了操作213(見圖2B)的細節。

在步驟215,參考塊標識模塊比較在步驟206期間計算的簽名與系統當前存儲的簽
名的簇,并對應地選擇最佳表示所計算的簽名的參考塊。參考塊標識模塊所選擇的參考塊
被存儲在參考塊緩沖器中,用于由系統進一步處理。

在步驟216,因為參考塊在步驟215中被存儲,所以哈希表模塊計算與該參考塊對
應的疊瓦哈希值。

在步驟217,將步驟216期間計算的哈希值存儲在哈希表模塊所生成的參考哈希表
中,假設哈希值還沒有被存儲在參考哈希表中的話。

在步驟218,假設將至少一個參考塊存儲在參考塊緩沖器中,哈希表模塊向掃描和
匹配引擎發送信號,以使用參考哈希表和/或壓縮哈希表執行哈希表查找和/或報頭修改過
程,用于基于步驟207、208和/或209期間計算的哈希值的進一步處理。

圖3B是根據本發明實施例的用于執行哈希表查找過程的示范處理的流程圖。圖3B
中概括了操作218(見圖3A)的細節。

在步驟219,掃描和匹配引擎進行關于其是否檢測到計算的哈希值和參考哈希表
中排他存儲的條目之間的匹配的確定。如果掃描和匹配引擎確定檢測到匹配,則掃描和匹
配引擎以每一字節為基礎針對與匹配的條目關聯地在參考塊緩沖器中存儲的參考塊來比
較與哈希值關聯的數據子集,如步驟220中詳述的那樣。如果掃描和匹配引擎確定沒有檢測
到匹配,則掃描和匹配引擎進行關于其是否檢測到計算的哈希值和參考哈希表中排他存儲
的條目之間的匹配的確定,如步驟221中詳述的那樣。

在步驟220,掃描和匹配引擎確定檢測到匹配并所以,掃描和匹配引擎以每一字節
為基礎針對與匹配的條目關聯地在參考塊緩沖器中存儲的參考塊來比較與哈希值關聯的
數據子集,并對應地向解壓模塊發送信號,以使用用于參考副本的修改壓縮報頭格式(諸如
“11”)來解壓參考塊緩沖器中的數據子集。解壓的輸出被存儲在數據輸出緩沖器中。

在步驟221,掃描和匹配引擎確定沒有檢測到匹配并所以,掃描和匹配引擎進行關
于其是否檢測到計算的哈希值和壓縮哈希表中排他存儲的條目之間的匹配的確定。如果掃
描和匹配引擎確定檢測到匹配,則掃描和匹配引擎以每一字節為基礎針對數據輸入緩沖器
中當前存儲的數據來比較與哈希值關聯的數據子集,如步驟222中詳述的那樣。如果掃描和
匹配引擎確定沒有檢測到匹配,則掃描和匹配引擎進行關于其是否檢測到計算的哈希值和
參考哈希表與壓縮哈希表兩者中存儲的條目之間的匹配的確定,如步驟223中詳述的那樣。

在步驟222,掃描和匹配引擎確定檢測到匹配并所以,掃描和匹配引擎以每一字節
為基礎針對數據輸入緩沖器中當前存儲的數據來比較與哈希值關聯的數據子集,并對應地
向解壓模塊發送信號,以基于適當比特長度和偏移,使用用于本地副本的修改壓縮報頭格
式(諸如“01”或“10”)來解壓數據輸入緩沖器中的數據子集。解壓的輸出被存儲在數據輸出
緩沖器中。

在步驟223,掃描和匹配引擎確定沒有檢測到匹配并所以,掃描和匹配引擎進行關
于其是否檢測到計算的哈希值和參考哈希表與壓縮哈希表兩者中存儲的條目之間的匹配
的確定。如果掃描和匹配引擎確定檢測到匹配,則掃描和匹配引擎以每一字節為基礎針對
與數據輸入緩沖器中當前存儲的數據來比較與哈希值關聯的數據子集,并對應地向解壓模
塊發送信號,以基于預先確定的過程來解壓數據輸入緩沖器中的數據子集。

在步驟224,掃描和匹配引擎確定檢測到匹配并所以,掃描和匹配引擎以每一字節
為基礎針對數據輸入緩沖器中當前存儲的數據來比較與哈希值關聯的數據子集,并對應地
向解壓模塊發送信號,以基于預先確定的過程來解壓數據輸入緩沖器中的數據子集。根據
一個實施例,預先確定的過程能包括配置掃描和匹配引擎,以取決于副本的長度和/或與數
據流關聯的數據的某些知識,使得解壓過程的其選擇朝向本地匹配或參考匹配偏向。

在步驟225,掃描和匹配引擎確定沒有檢測到匹配,并所以,將計算的哈希值存儲
在哈希表模塊所生成的壓縮哈希表中。

在步驟226,掃描和匹配引擎將信號傳遞到解壓模塊,以使用用于文字序列的修改
壓縮報頭格式(諸如“00”)來解壓數據輸入緩沖器中存儲的數據子集。將解壓的輸出存儲在
數據輸出緩沖器中。

盡管這里已公開了某些優選實施例和方法,但是本領域技術人員根據前述公開將
清楚的是,可進行這樣的實施例和方法的變型和修改,而不脫離本發明的精神和范圍。

根據實施例,這里描述的技術能通過一個或多個特定目的計算裝置實現。所述特
定目的計算裝置可以是硬連線的以執行所述技術,或者可以包括被持久編程以執行所述技
術的諸如一個或多個特定用途集成電路(ASIC)或現場可編程門陣列(FPGA)的數字電子裝
置,或者可以包括被編程以執行依照固件、存儲器、其它儲存器、或組合中的程序指令的技
術的一個或多個通用目的硬件處理器。這樣的特定目的計算裝置還可以組合常規硬連線邏
輯、ASIC或FPGA與常規編程,以實現這些技術。所述特定目的計算裝置可以是數據庫服務
器、儲存裝置、桌面計算機系統、便攜式計算機系統、手持裝置、聯網裝置或合并硬連線和/
或程序邏輯以實現這些技術的任何其它裝置。

在本發明實施例的前述詳細描述中,已闡明了許多特定細節以便提供本發明的透
徹理解。然而,本領域技術人員將認識到,本發明能在沒有這些特定細節的情況下實踐。在
其它實例中,還沒有詳細描述公知方法、過程、組件、和電路,以便不會不必要地使得本發明
實施例的各方面模糊。盡管為了清楚能夠將方法描繪為編號步驟的序列,但是編號并非必
須規定這些步驟的順序。應理解的是,一些步驟可被跳過、并行執行、或在沒有維持序列的
嚴格順序的需求下執行。示出本發明實施例的圖是半圖解的并不按照比例繪制,并且特別
是,一些維度是為了呈現的清楚,并在附圖中被夸大示出。類似地,盡管為了易于描述圖中
的視圖一般示出類似方位,但是圖中的該描繪對于絕大部分是任意的。

關 鍵 詞:
用于 對于 數據 傳遞 單遍熵 檢測 設備 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:用于對于數據傳遞的單遍熵檢測的設備和方法.pdf
鏈接地址:http://www.rgyfuv.icu/p-6100716.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
山东11选5中奖结果走势图