(57)【特許請求の範囲】
【請求項１】
装置であって、
データストリームを格納するためのメモリユニットと、
前記メモリユニットに結合されるプロセッサであって、前記プロセッサは、単一パスでの圧縮操作及び重複排除操作を実行するよう構成され、前記プロセッサは、データストリームからのデータのサブセットを用いて、前記データのサブセットに対応する参照データブロックを生成し、前記データのサブセットに対して演算処理された第１のハッシュ値を、前記参照データブロックに対して演算処理された第２のハッシュ値と比較し、別々のハッシュテーブルのうちの１つにおける前記第１のハッシュ値と前記第２のハッシュ値との間の検出されたマッチングに対応して、前記データのサブセットに対応するヘッダデータを少なくとも修正することによって、前記データのサブセットの圧縮及び重複排除された表現を生成するよう動作可能である、プロセッサとを備え、
前記第１のハッシュ値及び前記第２のハッシュ値は、別々のハッシュテーブルに格納される、装置。
【請求項２】
前記プロセッサは、前記別々のハッシュテーブルを用いて、並列に前記第１のハッシュ値と前記第２のハッシュ値を比較するよう動作可能である、請求項１に記載の装置。
【請求項３】
前記別々のハッシュテーブルは、参照ハッシュテーブルと圧縮ハッシュテーブルとを備える、請求項１に記載の装置。
【請求項４】
前記プロセッサは、前記第１のハッシュ値と前記第２のハッシュ値との間のマッチングの検出に対応して、前記参照データブロックを用いて前記データのサブセットの圧縮された表現を生成するよう動作可能であり、前記第２のハッシュ値は、前記参照テーブルに格納される、請求項３に記載の装置。
【請求項５】
前記プロセッサは、前記参照データブロックを前記メモリユニットに常駐するメモリバッファに格納すると、復元プロシージャを開始することによりインターロックを生じるよう動作可能である、請求項４に記載の装置。
【請求項６】
前記プロセッサは、ヒューリスティックに基づいて、後方参照符号化フォーマットを用いて前記ヘッダデータを修正するよう動作可能である、請求項１に記載の装置。
【請求項７】
前記第１のハッシュ値及び前記第２のハッシュ値は、同じ関数を用いて演算処理される、請求項１に記載の装置。
【請求項８】
単一のパスの間に入力データストリームに関するデータ整理操作を実行するコンピュータで実装される方法であって、
データストリームからデータのサブセットを受信することと、
前記データのサブセットに対応する参照データブロックを選択することであって、前記参照データブロックはメモリバッファに格納されることと、
前記データのサブセットに対して演算処理された第１のハッシュ値を、前記参照データブロックに対して演算処理された第２のハッシュ値と比較することであって、前記第１のハッシュ値及び前記第２のハッシュ値は、別々のハッシュテーブルに格納されることと、
前記別々のハッシュテーブルのうちの１つにおける前記第１のハッシュ値と前記第２のハッシュ値との間の検出されたマッチングに対応して、前記データのサブセットに対応するヘッダデータを少なくとも修正することによって、前記データのサブセットの圧縮表現を生成することと、を含む方法。
【請求項９】
前記比較することは更に、前記別々のハッシュテーブルを用いて、並列に前記第１のハッシュ値と前記第２のハッシュ値を比較することを含む、請求項８に記載の方法。
【請求項１０】
前記別々のハッシュテーブルは、参照ハッシュテーブルと圧縮ハッシュテーブルとを備える、請求項８に記載の方法。
【請求項１１】
前記生成することは更に、前記第１のハッシュ値と前記第２のハッシュ値との間のマッチングの検出に対応して、前記参照データブロックを用いて前記圧縮表現を生成することを含み、前記第２のハッシュ値は、前記参照ハッシュテーブルに格納される、請求項１０に記載の方法。
【請求項１２】
更に、
前記参照データブロックを前記メモリバッファに格納すると、復元プロシージャを開始することによりインターロックを生じることを含む、請求項８に記載の方法。
【請求項１３】
前記修正することは更に、ヒューリスティックに基づいて、後方参照符号化フォーマットを用いて前記ヘッダデータを修正することを含む、請求項８に記載の方法。
【請求項１４】
前記第１のハッシュ値及び前記第２のハッシュ値は、同じ関数を用いて演算処理される、請求項８に記載の方法。
【請求項１５】
装置であって、
メモリバッファを格納するためのメモリユニットと、
プロセッサであって、前記メモリユニットに結合され、
データストリームからデータのサブセットを受信し、
前記データのサブセットをデータ入力メモリバッファ内に格納し、
前記データのサブセットのための署名を演算処理し、
前記演算処理された署名を用いて参照データブロックを選択することであって、前記参照データブロックは前記メモリユニットに常駐するメモリバッファに格納され、
前記データのサブセットに対して演算処理された第１のハッシュ値を、前記参照データブロックに対して演算処理された第２のハッシュ値と比較し、前記第１のハッシュ値及び前記第２のハッシュ値は、別々のハッシュテーブルに格納され、
前記別々のハッシュテーブルのうちの１つにおける前記第１のハッシュ値と前記第２のハッシュ値との間の検出されたマッチングに対応して、前記データのサブセットに対応するヘッダデータを修正することによって、前記データのサブセットの圧縮表現を生成するよう構成されるプロセッサと、を備える、装置。
【請求項１６】
前記プロセッサは、前記別々のハッシュテーブルを用いて、並列に前記第１のハッシュ値と前記第２のハッシュ値を比較するよう動作可能である、請求項１５に記載の装置。
【請求項１７】
前記別々のハッシュテーブルは、参照ハッシュテーブルと圧縮ハッシュテーブルとを備える、請求項１５に記載の装置。
【請求項１８】
前記プロセッサは、前記第１のハッシュ値と前記第２のハッシュ値との間のマッチングの検出に対応して、前記参照データブロックを用いて前記圧縮表現を生成するよう動作可能であり、前記第２のハッシュ値は、前記参照ハッシュテーブルに格納される、請求項１７に記載の装置。
【請求項１９】
前記プロセッサは、前記参照データブロックを前記メモリバッファに格納すると、復元プロシージャを開始することによりインターロックを生じるよう動作可能である、請求項１８に記載の装置。
【請求項２０】
前記プロセッサは、ヒューリスティックに基づいて、後方参照符号化フォーマットを用いて前記ヘッダデータを修正するよう動作可能である、請求項１５に記載の装置。
【請求項２１】
前記第１のハッシュ値及び前記第２のハッシュ値は、同じ関数を用いて演算処理される、請求項１５に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、本出願と同時に出願され、代理人整理番号ＨＧＳＴ−Ｈ２０１５１０５５ＵＳ１を有する特許出願「データ転送に関する単一パスエントロピー検出のための装置及び方法」に関し、そのすべてを引用して本明細書中に組み込む。
【０００２】
本発明は、概してデータ整理技術の分野に関する。
【背景技術】
【０００３】
高性能な、不揮発性記憶クラスメモリサブシステムは一般に、比較的高価なコンポーネントから成っている。従って、データ整理技法を用いて、かかるシステムにおけるデータ記憶を最大化することが高く望まれている。データ整理とは、バックエンド記憶システムに書き込まれるか、それから読み出される情報の総容量を削減するためのデータ自己圧縮及びデータ重複排除技法を指している。データ整理は、結果として、格納することができる、よりコンパクトな表現にまでユーザ（入力）データを変換させる。データ整理の利点は、記憶装置使用率の向上、寿命の向上（全フラッシュ記憶システムとの関連）、及び、数ある利点の中でもアプリケーションの高速化を含んでいる。
【０００４】
データ圧縮とは、同じデータブロック内部の冗長性を探し、次いで、データの全体のサイズを低減するような方法で、これらの繰り返されたシーケンスを符号化する処理を指している。データ重複排除とは、個々のブロックが非圧縮性データを有している場合でさえも、マッチしたシーケンスを見つけるために、多数のブロックにわたってデータシーケンスをマッチングさせる処理を指している。しかし、従来のシステムは、圧縮及びデータ重複排除を、データ整理処理において別々のステップとして実行している。従って、これら従来のシステムは、それらを単一のステップに結合しなかったため、待ち時間及び帯域幅を犠牲にしている。
【０００５】
更に、従来のデータ整理の解決法は、圧縮機能を実行するために、多くのサイクル及びパワーを費やしている。何らかの所定のアプリケーションデータフローにおいて、データブロックの特定のセットが、自己圧縮特性を呈示しない場合がある可能性は、常に高い。通常、圧縮段階の終わりにおいて、従来の解決法は、チェックを実行して結果が元のブロックよりも大きくないことを保証している。従って、データを圧縮しようとする時に、既にリソースが利用されたものとしては、これはかなり遅いものである。
【発明の概要】
【課題を解決するための手段】
【０００６】
従って、単一パスでデータ圧縮及び重複排除の両方を実行する統一されたデータパスを作成する解決法に対するニーズが存在している。本発明の実施形態は、データ圧縮技術を組み合わせ、それらをデータ重複排除方法に統合することによってそれらを拡張している。本発明の実施形態の単一パスの特性により、システム待ち時間の制御が可能となり、高速（例えば、所定のＦＰＧＡに対するＰＣＩｅ  Ｇｅｎ３速度、又は他の速度要件又は規格を満たし得る態様）でラインレート圧縮及び重複排除を達成することに役立つ。
【０００７】
本発明の実施形態は、圧縮のために、４キロバイトサイズのデータブロック等の、より小さなデータのサブセットを利用し、圧縮符号化コピーフォーマットをオーバーライドして、参照ブロック参照化コピーから自己参照コピーを区別できる。実施形態は、４キロバイトサイズのデータブロックに限定されず、何れかのブロックサイズ又はブロックサイズの範囲（例えば、４ｋｂ、８ｋｂ、１０ｋｂ、４ｋｂ−８ｋｂブロックサイズ範囲、等）が用いられてもよいことは、正しく理解すべきである。実施形態は、参照データブロックを保持するよう多数の並列入力バッファを有するメモリバッファ構造を作成できる。また、実施形態は、参照データブロックバッファに格納されているデータに対応する検索が、入力データバッファに格納されているデータに対して実行されるハッシュルックアップと同時に実行することができる並列ハッシュテーブルルックアップ方式を含んでもよい。
【０００８】
加えて、実施形態は、データ整理パフォーマンスを強化する目的のために、参照データバッファの充填時間を用いて、参照データのシングル（瓦）形ハッシュ関数値を演算処理し、格納できる。実施形態はまた、参照ハッシュテーブル演算処理と圧縮の開始との間にインターロックを生じることもできる。このように、圧縮が開始する場合、参照ハッシュテーブル、圧縮ハッシュテーブルのどちらか一方、又は両方において、検索を実行することができる。本発明の実施形態は、ヒューリスティックを用いて、ハッシュヒットがハッシュテーブルの１つ以上で検出された場合、どのシーケンスを用いるか（もしあれば）を決定できる。その上、本発明の実施形態は、入力データストリームに対するか、入力参照バッファからのどちらか一方の後方参照解釈を修正できる。
【０００９】
更に、本発明の実施形態は、無駄な努力を最小限にし、システム全体のパフォーマンスにおけるロスを避けるために、ブロックの圧縮性を早期に検出し、予測できる。本明細書中で説明する実施形態は、圧縮特性を分析して、所定のデータブロックに対して、圧縮等のデータ整理プロシージャを実行する決定を行う。従って、非圧縮性データが与えられた場合、高性能データ整理システムに、パワー及び圧縮単位サイクルを節約することを可能にする方法で、負担の少ない、高性能なエントロピー検出操作を実行することができる。
【００１０】
本明細書に組み込まれ、その一部を形成し、同様の符号が同様の要素を表す添付図面は、本開示の実施形態を示し、説明と共に、開示の原理を説明する役割を果たす。
【図面の簡単な説明】
【００１１】
【図１Ａ】図１Ａは、本発明の実施形態によるデータ整理の目的のために、同時に二重の圧縮及び重複排除プロシージャを実行可能なインライン圧縮及び重複排除システムの例示のハードウェア構成を表すブロック図である。
【図１Ｂ】図１Ｂは、本発明の実施形態によるインライン圧縮及び重複排除プロシージャを実行するためのメモリ内に設けられる例示のコンポーネントを表すブロック図である。
【図１Ｃ】図１Ｃは、本発明の実施形態によって生成される例示の圧縮データフレーミングフォーマットを表す。
【図１Ｄ】図１Ｄは、本発明の実施形態による例示の組み合わされた参照ハッシュテーブル及び圧縮ハッシュテーブルルックアップ方式を表す。
【図２Ａ】図２Ａは、本発明の実施形態による単一パスエントロピー検出のための例示的な処理の第１の部分のフローチャートである。
【図２Ｂ】図２Ｂは、本発明の実施形態による単一パスエントロピー検出のための例示的な処理の第２の部分のフローチャートである。
【図３Ａ】図３Ａは、本発明の実施形態による同時データ重複排除及び圧縮のための例示的な処理のフローチャートである。
【図３Ｂ】図３Ｂは、本発明の実施形態によるハッシュテーブルルックアッププロシージャを実行するための例示的な処理のフローチャートである。
【発明を実施するための形態】
【００１２】
ここで、実施例が添付図面に示されている本発明の好ましい実施形態を、詳細に参照する。発明を、好ましい実施形態と共に説明するが、それらは発明をこれらの実施形態に限定する意図はないことは理解されよう。反対に、発明は、添付特許請求の範囲によって定義されるような発明の趣旨及び適用範囲内に含まれてもよい代替、改良、及び均等物をカバーすることを意図している。
【００１３】
更に、以下の本発明の実施形態の詳細な説明において、本発明の完全な理解を提供するために、数多くの特定の詳細を説明する。しかし、本発明は、これらの特定の詳細がなくても実施されてもよいことは、当業者によって認識されるであろう。他の例では、周知の方法、プロシージャ、コンポーネント、及び回路は、本発明の実施形態の態様を不必要に不明瞭にしないように、詳細に説明されてはいない。方法は、明確にするために番号の付いたステップのシーケンスとして示されているが、番号付けは、必ずしもステップの順序を定めるものではない。
【００１４】
ステップの内のいくつかは、省略され、同時に実行され、又は、シーケンスの順序を厳格に維持する必要なく実行されてもよいことは、言うまでもない。発明の実施形態を示す図面は、半図解式であり、正確な縮尺で描かれてはおらず、特に、寸法のいくつかは、描写を明確にするためであり、図中で誇張して示されている。同様に、説明を容易にするための図中の視点は、概して、類似する向きを示しているが、図中におけるこの描写は、多くの部分に対して任意である。一般に、発明は、どのような向きでも操作することができる。
【００１５】
注釈及び命名法
しかし、これら及び類似の用語のすべては、適切な物理的数量に関するものであり、これらの数量に適用される単に便利な表示であることは念頭に置かれたい。以下の検討により特に明記のない限り、本発明を通じて、「受信」又は「選択」又は「生成」又は「グループ化」又は「監視」等の用語を用いる検討は、コンピュータシステムのレジスタ及びメモリ及び他のコンピュータ読取可能媒体内部の物理的（例えば、電子的）数量として表されるデータを、コンピュータシステムメモリ又はレジスタ又は他のかかる情報記憶、転送、又は表示装置内部の物理的数量として同様に表される他のデータに操作し、変換するコンピュータシステム、又は類似の電子演算システムの動作及び処理を指すことを、正しく理解されたい。１つのコンポーネントがいくつかの実施形態に出現する場合、同じ符号の使用は、コンポーネントが元の実施形態において図示されたものと同じコンポーネントであることを意味する。
【００１６】
例示的なインライン圧縮及び重複排除システム構成
図１Ａは、本発明の実施形態によるデータ整理の目的のために、同時に二重の圧縮及び重複排除プロシージャを実行可能なインライン圧縮及び重複排除システム（例えば、システム１００）の例示のハードウェア構成を表すブロック図である。このように、システム１００は、データ圧縮及びデータ重複排除等のデータ整理操作に関する操作が、単一の処理、単一の処理経路、又は、単一のステップで結合され、それによって、一般のシステム待ち時間及び／又は帯域幅の犠牲を低減するように、単一パスでのデータ整理プロシージャを実行できる。特定のコンポーネントを図１Ａに開示するが、かかるコンポーネントが例示であることは、正しく理解されたい。すなわち、本発明の実施形態は、種々の他のハードウェアコンポーネント又は図１Ａに挙げた種々のコンポーネントを有することに良好に適している。図１Ａのハードウェアコンポーネントは、提示したそれらのもの以外のコンポーネントと共に動作でき、図１Ａで説明するハードウェアコンポーネントのすべてが本発明の目標を達成するために必要ではないことは、正しく理解されたい。いくつかの実施形態によれば、図１Ａ内部に示すコンポーネントは、本発明の目標を達成するよう組み合わせることができる。
【００１７】
システム１００は、データ通信バスを通じて他の電子デバイスと通信することができる電子デバイスとして実装することができる。例えば、バス１０６は、かかるデータ通信バスを表している。本開示の実施形態が実装されてもよい例示のシステム１００は、汎用演算システム環境を含んでいる。その最も基本的な構成において、システム１００は通常、少なくとも１つの処理ユニット１０１及びメモリ記憶ユニットを含む。例えば、コンピュータ読取可能記憶媒体１０４は、かかるメモリ記憶ユニットを表している。装置の正確な構成及び種類に応じて、コンピュータ読取可能記憶媒体１０４は、揮発性（ＲＡＭ等）、不揮発性（ＲＯＭ、フラッシュメモリ等）、又はその２つのいくつかの組み合わせであってもよい。コンピュータ読取可能記憶媒体１０４の一部は、実行時、メモリ操作又はスレッドのグループに対するリクエストの効率的な実行を容易にする。
【００１８】
一実施形態において、プロセッサ１０１は、本明細書中で説明するインライン圧縮及び重複排除操作を実行するよう構成されるプログラマブル回路であってもよい。例えば、プロセッサ１０１は、ＦＰＧＡコントローラ又はフラッシュメモリ装置コントローラであってもよい。代替として、一実施形態において、プロセッサ１０１は、コンピュータ読取可能記憶媒体１０４内に格納されるインライン圧縮及び重複排除プログラムを実行するよう動作可能で、本明細書中で説明する機能（例えば、以下に検討する図１Ｂを参照）を実行するよう構成されてもよい。システム１００はまた、任意の表示装置１０２に情報を表示することによる等の、情報をコンピュータユーザに提示するための任意のグラフィックスシステム１０５も備えてもよい。システム１００はまた、任意の英数字入出力装置１０３も備えている。入出力装置１０３は、任意のカーソル制御又は指示装置と、ネットワークインターフェースカード等の１つ以上の信号通信インターフェースとを含むことができる。更に、インターフェースモジュール１１５は、システム１００が電子通信ネットワーク（例えば、インターネット、有線通信ネットワーク、無線通信ネットワーク、又は類似のネットワーク）を介して他のコンピュータシステムと通信することを可能にする機能を含んでいる。
【００１９】
加えて、システム１００は、追加の特徴及び機能を有していてもよい。例えば、システム１００は、磁気又は光学ディスク又はテープを含むが、これらに限定されない（取り外し可能な、及び／又は、取り外しできない）追加の記憶媒体を含んでもよい。コンピュータ記憶媒体は、コンピュータ読取可能命令、データ構造、プログラムモジュール、又は他のデータ等の情報を格納するための何らかの方法又は技術で実装される揮発性及び不揮発性の、取り外し可能な、及び、取り外しできない媒体を含む。
【００２０】
図１Ｂは、本発明の実施形態によるインライン圧縮及び重複排除プロシージャを実行するためのメモリ内に設けられる例示のコンポーネントを表すブロック図である。特定のコンポーネントを図１Ｂに開示するが、かかるコンピュータ記憶媒体コンポーネントが例示であることは、正しく理解されたい。すなわち、本発明の実施形態は、種々の他のコンポーネント又は図１Ｂに挙げた種々のコンピュータ記憶媒体コンポーネントを有することに良好に適している。図１Ｂのコンポーネントは、提示したそれらのもの以外のコンポーネントと共に動作でき、図１Ｂで説明するコンピュータ記憶媒体コンポーネントのすべてが本発明の目標を達成するために必要ではないことは、正しく理解されたい。いくつかの実施形態によれば、図１Ｂ内部に示すコンポーネントは、本発明の目標を達成するよう組み合わせることができる。更に、図１Ａで説明したいくつかのハードウェアコンポーネントは、本発明の目標を達成する目的のために、図１Ｂで説明するいくつかのコンポーネントとの組み合わせで動作できる。
【００２１】
図１Ｂに表すように、コンピュータ読取可能記憶媒体１０４は、オペレーティングシステム１０７を含んでいる。オペレーティングシステム１０７は、システム１００が初期化される場合にプロセッサ１０１にロードされる。また、プロセッサ１０１による実行時に、オペレーティングシステム１０７は、プログラマティックインターフェイスをシステム１００に供給するよう構成することができる。システム１００は、無線通信機構も含むことができる。かかる装置により、システム１００は、インターネット又はローカルエリアネットワーク等のイントラネット等の通信ネットワークを通じて他のコンピュータシステムに通信可能に結合することができる。
【００２２】
更に、図１Ｂに示すように、コンピュータ読取可能記憶媒体１０４は、フィンガープリント演算処理エンジン１１０を含んでいる。フィンガープリント演算処理エンジン１１０は、認証及び／又はルックアッププロシージャを実行する目的のために、バイト列を用いるフィンガープリントを生成する機能を含んでいる。テータストリームの受信の検出時に、バッファ管理コントローラ１１２は、信号をフィンガープリント演算処理エンジン１１０に伝えて、その受信時にデータ入力バッファ１１２−１に格納されているデータを処理することができる。
【００２３】
フィンガープリント演算処理エンジン１１０によって生成されるフィンガープリントは、記憶領域のごく一部を用いながら、より大きいファイルを表すために用いることができ、その他の場合は、かかるより大きいファイルを格納するために必要とされてもよい。例えば、大きいファイルは、コンテンツのページ又はマルチメディアファイルを含むことができる。フィンガープリント演算処理エンジン１１０は、署名演算処理エンジン１１３等のシステム１００のコンポーネントによって処理できるようにフィンガープリントを生成する目的のために、ハッシュ関数等の従来のコンピュータで実装されるプロシージャを用いてデータストリームをデータのビットにまで削減する。ハッシュ演算処理は、ハッシュテーブルモジュール１１１等のシステム１００の他のコンポーネントがどのようにハッシュ値を演算処理するかに一致する方法で、又は異なる方法で実行されてもよい。
【００２４】
このように、フィンガープリント演算処理エンジン１１０は、データストリームがシステム１００によって受信されている間に、データストリームに関連する受信データのサブセットのためのフィンガープリントを生成するよう構成することができる。例えば、データのサブセットは、４キロバイト単位の形態であってもよい。一実施形態において、フィンガープリント演算処理エンジン１１０は、システム１００によって受信されるデータストリームに関連し、バッファ管理コントローラ１１２によって生成されるデータ入力バッファ１１２−１内部に格納される４キロバイトの受信セットのためのフィンガープリントを演算処理できる。
【００２５】
署名演算処理エンジン１１３は、システム１００によって受信されたデータストリームのための署名を演算処理する機能を含んでいる。署名は、Ｍｅｒｋｌｅ、Ｓｐｏｏｋｙ、ＣＲＣ、ＭＤ５、ＳＨＡ、又は同様の方式を含む種々の従来のハッシュベースの署名方式に基づいて、署名演算処理エンジン１１３によって演算処理できる。署名演算処理エンジン１１３は、システム１００によって受信されたデータストリームに関するサブブロック署名演算処理、ラビン署名ベースの類似性検出演算処理、及び／又は、他の類似性ベースの署名演算処理を用いて署名演算処理を実行するよう構成することができる。一実施形態によれば、署名演算処理エンジン１１３は、フィンガープリント演算処理エンジン１１０によって生成されるフィンガープリントデータを用いて署名を生成できる。一実施形態において、テータストリームの受信時に、バッファ管理コントローラ１１２は、信号を署名演算処理エンジン１１３に伝えて、その受信時にデータ入力バッファ１１２−１に格納されているデータを処理するよう構成することができる。
【００２６】
署名演算処理エンジン１１３は、入力データストリームの様々な部分のために、データのサブセットのための多数の署名を同時に演算処理するよう構成することができる。このように、サブセットのために署名演算処理エンジン１１３によって演算処理された署名は、更なる処理のために、参照ブロック識別モジュール１１４等の、システム１００の他のコンポーネントに通信することができる。例えば、署名演算処理エンジン１１３によって演算処理された署名は、互いに類似した、又は、同じブロックに関して演算処理される場合と類似または同じであることを可能にする数学的特性を含むことができる。従って、参照ブロック識別モジュール１１４等のシステム１００のコンポーネントによって選択される参照ブロックは、システム１００に常駐するメモリに格納される複数の類似の署名クラスタを最良に表す、演算処理された署名に基づくことができる。従って、システム１００のコンポーネントは、署名演算処理エンジン１１３によって演算処理された署名を用いて、参照ブロック識別プロシージャを実行できる。例えば、参照ブロック識別モジュール１１４は、サブブロック署名を用いて参照ブロック識別プロシージャを実行できる。
【００２７】
参照ブロック識別モジュール１１４は、署名演算処理エンジン１１３によって生成される複数の異なる署名クラスタを解析し、ハッシュテーブルモジュール１１１等のシステム１００のコンポーネントによって処理することができる参照ブロックを選択する機能を含んでいる。参照ブロック識別モジュール１１４は、演算処理された署名を、システム１００によって現在のところ格納されている署名のクラスタと比較し、演算処理された署名を最良に表している参照ブロックをそれに応じて選択するよう構成することができる。例えば、参照ブロック識別モジュール１１４は、演算処理された署名を、バッファ管理コントローラ１１２によって生成されるバッファに現在のところ格納されている署名のクラスタと比較し、演算処理された署名を最良に表している参照ブロックをそれに応じて選択するよう構成することができる。
【００２８】
参照ブロック識別モジュール１１４によって選択された参照ブロックは、システム１００のコンポーネントによって更に処理するため、参照ブロックバッファ１１２−３等の、バッファ管理コントローラ１１２によって生成されるバッファ内に格納することができる。参照ブロックは、様々な方法によって入力データと類似していると判明された正規のデータブロックであってもよい。例えば、参照ブロックは、サブブロック署名、類似性検出機構、アプリケーションヒント検出方式、又は類似の方式を用いて演算処理されることによって入力データと類似していると判明された正規のデータブロックであってもよい。参照ブロックは、また、より大きい繰返し因数を有していると判明された、繰り返されるデータシーケンスを含む純粋な合成ブロックであってもよい。一実施形態によれば、参照ブロック識別モジュール１１４は、アプリオリな知識、コンテンツ類似性マッチング、アプリケーションヒント、データパターン認識、又は類似の手段を用いて参照ブロックを識別するよう構成することができる。
【００２９】
更に、参照ブロックバッファ１１２−３内に格納される参照ブロック等の、参照ブロック識別モジュール１１４によって識別される参照ブロックに関する情報は、データストリームのヘッダ部分内に格納することができる。例えば、図１Ｃを参照すると、参照ブロック識別モジュール１１４によって識別される参照ブロックのための参照ブロック識別子は、データストリーム１１６のヘッダ部分１１６ａ内に格納することができる。図１Ｃに示すように、ヘッダデータ１１６ａは、データ粒子１１６−１、１１６−２、及び１１６−Ｎ等の１セットのデータ粒子内に、圧縮ペイロード１１６ｂ等のそれらそれぞれの圧縮されたペイロードデータ部分と共に含まれてもよい。一実施形態において、ヘッダデータ１１６ａは、参照識別子１１７−１を、ビットベクトル１１７−２、粒子数１１７−３、及び／又は、ヘッダＣＲＣデータ１１７−４に加えて格納できる。
【００３０】
図１Ｂを参照すると、ハッシュテーブルモジュール１１１は、システム１００によって受信されたデータストリームに関連するデータに基づいて、ハッシュ値を演算処理し、ハッシュテーブルを動的に生成する機能を含んでいる。テータストリームの受信時に、バッファ管理コントローラ１１２は、信号をハッシュテーブルモジュール１１１に伝えて、各バッファがデータを受信した時にデータ入力バッファ１１２−１及び／又は参照ブロックバッファ１１２−３に格納されたデータを処理することができる。ハッシュテーブルモジュール１１１は、生成されたハッシュテーブル内に格納することができる、システム１００によって受信されたデータストリームに関するデータのバイト等のデータのサブセットに対するハッシュ値を演算処理する機能を含んでいる。例えば、ハッシュテーブルモジュール１１１は、システム１００によって受信されたデータストリームに関するデータのバイトに対するハッシュ値を演算処理できる。従って、ハッシュテーブルモジュール１１１は、繰り返されたデータシーケンスの検索を加速する方法で、普及している高速圧縮方式によって利用されてもよい。例えば、ハッシュテーブルモジュール１１１は、Ｓｎａｐｐｙ、Ｌｅｍｐｅｌ−Ｚｉｖ（ＬＺ）圧縮方式、Ｇｚｉｐ又は他の方式を含む普及している高速圧縮方式によって利用されてもよい。
【００３１】
データのサブセットは、所定の固定サイズであってもよく、重複排除プロシージャを実行する目的のためにより大きいファイルを表すよう用いることができる。従って、ハッシュテーブルモジュール１１１は、システム１００によって受信されたデータの各バイトに対するハッシュ値を演算処理できる。このように、ハッシュテーブルモジュール１１１は、データのサブセットに対するハッシュ値を、それらの受信及びバッファ管理コントローラ１１２によって生成されるバッファ内の格納と同時に演算処理できる。更に、ハッシュ演算処理は、フィンガープリント演算処理エンジン１１０等のシステム１００の他のコンポーネントがどのようにハッシュ値を演算処理するかに一致する方法で、又は異なる方法で実行されてもよい。
【００３２】
一実施形態によれば、ハッシュテーブルモジュール１１１は、参照ブロック識別モジュール１１４によって識別される参照データブロックに基づいて参照ハッシュテーブルを動的に生成する機能を含んでいる。一旦、参照ブロック識別モジュール１１４によって選択されると、参照ブロックに対応するデータブロックは、参照ブロックバッファ１１２−３等の参照ブロックバッファ内に格納することができる。参照ブロックが格納されている間に、ハッシュテーブルモジュール１１１は、参照ブロックに対応するシングル（瓦）形ハッシュ値を演算処理するよう構成することができる。このように、ハッシュテーブルモジュール１１１は、システム１００によって実行される圧縮及び重複排除プロシージャの性能を加速できる予め演算処理されたハッシュテーブルを生成できる。
【００３３】
例えば、図１Ｂを参照すると、１セットのバイトがシステム１００によって受信され、システム１００に常駐するデータ入力バッファ１１２−１内に格納される場合、ハッシュテーブルモジュール１１１は、受信された１セットのバイトに対応するような、参照ブロック識別モジュール１１４によって決定され、及び／又は、選択される参照ブロックに対するハッシュ値を演算処理できる。ハッシュテーブルモジュール１１１は、参照データブロックが、バッファ管理コントローラ１１２によって動的に生成された参照データブロックバッファ１１２−３内に格納されているものとして、これらのハッシュ値を演算処理する。このように、バッファ管理コントローラ１１２は、データ入力バッファ１１２−１等の、システム１００に常駐するデータ入力バッファの機能と並列にできる参照データブロックバッファを生成する機能を含んでいる。従って、これらの演算処理された参照ブロックハッシュ値は、その後、ハッシュテーブルモジュール１１１によって生成される参照ハッシュテーブル１１１−１内に格納することができる。
【００３４】
ハッシュテーブルモジュール１１１は、システム１００によって受信され、及び／又は、データ入力バッファ内に格納されるデータストリームを用いて圧縮ハッシュテーブルを動的に生成する機能を含んでいる。更に、ハッシュテーブルモジュール１１１は、システム１００によって前もって処理されたデータストリームを、その後に復元及び／又は再構築するよう用いることができる、符号化データを修正及び／又は生成する機能を含んでいる。このように、ハッシュテーブルモジュール１１１は、圧縮操作中に類似のデータシーケンスを識別すると、ヘッダデータを修正及び／又は符号化するよう構成することができる。従って、ハッシュテーブルモジュール１１１は、ハッシュテーブルモジュール１１１によって前もって識別された格納データに対応する参照識別子を含む符号化データ生成できる。
【００３５】
例えば、ハッシュテーブルモジュール１１１は、ハッシュ演算処理プロシージャの完了時に、識別されたリテラルの数等の、ハッシュテーブルモジュール１１１によって識別される非圧縮データバイトの数を含む符号化ヘッダデータを生成及び／又は修正できる。このように、ハッシュテーブルモジュール１１１によって生成される符号化データは、復元モジュールが復元プロシージャにかけられるデータストリームに関連する１セットのバイトに対応するリテラル及び／又はコピー要素を復元又は複合できる方法に関する命令を提供できる。コピー要素は、コピーされるバイト（「長さ」）、及び／又は、コピーされるデータがどの程度後ろにあるか（「オフセット」）を含むことができる。
【００３６】
例えば、一実施形態において、ハッシュテーブルモジュール１１１によって生成及び／又は修正されるヘッダデータは、識別されたリテラルの表現及び対応するリテラルデータシーケンスを含むことができる。従って、復元モジュール１０８は、モジュールがリテラルシーケンスを復元する方法に関する命令を提供する符号化及び／又は修正されたヘッダ情報を読み取ることができる。更に、復元モジュール１０８は、Ｓｎａｐｐｙ、ＬＺ圧縮方式、Ｇｚｉｐ、又は類似の方式等の種々の圧縮方式に基づいて、復元プロシージャを実行するよう構成することができる。
【００３７】
一実施形態によれば、少なくとも１つの参照ブロックが参照ブロックバッファ内への格納のために選択され、指定されることを条件に、ハッシュテーブルモジュール１１１は、信号をシステム１００のコンポーネントに送信して、演算処理されたハッシュ値に基づいて更に処理するために、参照ハッシュテーブル及び／又は圧縮ハッシュテーブルを用いてハッシュテーブルルックアップ及び／又はヘッダ修正プロシージャを実行できる。このように、ハッシュテーブルモジュール１１１は、参照ハッシュテーブル演算処理と復元プロシージャの開始との間にインターロックを作成できる。更に、圧縮ハッシュテーブル及び参照ハッシュテーブルのためにハッシュテーブルモジュール１１１によって実行されるハッシュ演算処理プロシージャは、コンピュータで実装される同じプロシージャ又は機能、又はコンピュータで実装される異なるプロシージャ又は機能であってもよい。
【００３８】
表１は、例示的な１セットのヘッダフォーマット又は本発明の実施形態によって修正可能な後方参照符号化フォーマット修正を提供する。
【００３９】
【表１】
0006370838.tif 000002
【００４０】
スキャン及びマッチエンジン１０９は、ハッシュテーブルルックアッププロシージャを実行し、ハッシュ値比較を実行する機能を含んでいる。スキャン及びマッチエンジン１０９は、信号をハッシュテーブルモジュール１１１から送信及び／又は受信して、データのサブセットに対する演算処理したハッシュ値をシステム１００によって現在格納されている参照データブロックと比較するためのコンピュータで実装されるルックアッププロシージャを実行する機能を含んでいる。
【００４１】
スキャン及びマッチエンジン１０９は、ハッシュテーブルルックアップロジックを用いて、ハッシュテーブルモジュール１１１によって生成されたハッシュテーブル内の演算処理されたハッシュ値を探し出し、データを比較できる。例えば、ハッシュテーブルモジュール１１１は、参照ハッシュテーブル１１１−１及び圧縮ハッシュテーブル１１１−２を生成し、比較操作を実行できる。従って、スキャン及びマッチエンジン１０９は、バイトのサブセットに対する演算処理したハッシュ値を、参照ブロックバッファ１１２−３等のバッファ管理コントローラ１１２によって生成されるバッファ内にシステム１００によって現在格納されている参照データブロックに対してルックアップするよう構成することができる。
【００４２】
このように、スキャン及びマッチエンジン１０９は、ハッシュテーブルモジュール１１１によって作成される参照ハッシュテーブル及び圧縮ハッシュテーブル内の両方において並行又は同時検索を実行できる。かかるルックアッププロシージャを実行する場合、スキャン及びマッチエンジン１０９は、システム１００によって受信されるバイトの後続のセットを、ハッシュテーブルモジュール１１１によって前もって識別されたデータに対応する格納されている参照データブロック及び／又は圧縮ハッシュ値と比較するためのプロシージャも実行できる。
【００４３】
例えば、図１Ｄを参照すると、参照ブロック１１８が参照ブロック識別モジュール１１４によって識別される場合、ハッシュテーブルモジュール１１１は、参照ブロック１１８の一部に対応する演算処理されたハッシュ値エントリ（例えば、参照ブロックデータサブセット１１８−１、１１８−２、１１８−３、１１８−４、等に対する値）を、それが参照ブロックバッファに格納されるように、参照ハッシュテーブル１１１−１内に格納する。このように、システム１００は、参照データバッファの充填時間を用いて、参照ブロック１１８に対応する参照データのシングル形ハッシュ関数値を演算処理し、格納でき、システム１００によって実行される圧縮及び重複排除プロシージャのパフォーマンスを向上させている。
【００４４】
その上、図１Ｄに示すように、システム１００は、受信データストリームに関連する入力データブロック１２０も受信できる。従って、スキャン及びマッチエンジン１０９は、登録された参照ハッシュテーブル１１１−１及び圧縮ハッシュテーブル１１１−２を用いる並列ルックアッププロシージャを実行するよう、ハッシュテーブルロジック１０９−３を用いて、類似の受信したデータブロック１２０である前もって格納されたデータのシーケンスを識別できる。このように、スキャン及びマッチエンジン１０９は、データのより小さなサブセット（例えば、入力データブロックデータサブセット１２０−１）及びバイト単位での参照ブロックを用いて比較を実行できる。
【００４５】
仮にスキャン及びマッチエンジン１０９が、参照ハッシュテーブル１１１−１及び／又は圧縮ハッシュテーブル１１１−２内のエントリとデータブロック１２０に対する演算処理されたハッシュ値との間のマッチングを検出すると、スキャン及びマッチエンジン１０９は次いで、それに応じて信号を復元モジュール１０８に送信して、本明細書中で説明する後方参照符号化フォーマット修正等の修正された圧縮ヘッダフォーマットを用いて参照ブロックバッファ又はデータ入力バッファ内のデータのサブセットを復元できる。従って、復元された出力は、次いで、データ出力バッファ１１２−２等のバッファ管理コントローラ１１２によって生成されたバッファ内に格納することができる。
【００４６】
一実施形態において、復元プロシージャの実行中、復元モジュール１０８は、スキャン及びマッチエンジン１０９が参照ハッシュテーブル１１１−１及び／又は圧縮ハッシュテーブル１１１−２のどちらかとのマッチングを検出した場合、複数の異なるシーケンスのうちの１つを選択するよう構成することができる。例えば、所定のヒューリスティックに基づき、復元モジュール１０８は、リテラル、ローカルコピー、及び／又は参照コピーのようなデータを復元するよう構成することができる。このように、復元に関して、システム１００は、復元の実装が、入力データストリームから、又は、参照ブロックバッファからのどちらかの後方参照を解釈するよう修正することができるように、類似の参照データ入力バッファを作成できる。
【００４７】
従って、復元モジュール１０８は、スキャン及びマッチエンジン１０９によって用いられるリテラルスキャンロジック１０９−１及び／又はローカルコピースキャンロジック１０９−２を処理するよう構成することができる。本発明の実施形態が、単一の参照ブロックを用いることに限定されないことは、正しく理解され得る。実施形態は、既存のデータパス及びフレーム構造に対する簡単な改良により、多数の参照ブロックを包含するよう拡張することができる。例えば、実施形態は、並列に実行される多数の参照ブロック比較にまで拡張することができる。更に、ハッシュテーブルモジュール１１１は、１セットの異なる参照ブロックのそれぞれの参照ブロックに対応する多数の参照ハッシュテーブルを生成するよう構成することができる。その上、多数の参照ブロックは、ハッシュテーブルモジュール１１１によって生成される単一の参照ハッシュテーブル内に格納することができる。
【００４８】
更に、システム１００は、無駄な努力を最小限にし、システム全体のパフォーマンスにおけるロスを避けるために、本明細書中で説明するもの等のデータ整理操作の実行前に、ブロックの圧縮性を早期に検出し、予測するよう構成することができる。例えば、復元モジュール１０８は、システム１００によって受信されるデータに関するグループ化プロシージャを実行する機能を含んでいる。従って、復元モジュール１０８は、復元モジュール１０８が、データ入力バッファ１１２−１を介して受信される受信データを、単一のインスタンスで処理又は操作できるデータバイトのサブセット又は「シングル（瓦）」にグループ化することを可能にするデータグループ化ロジック１０８−１を含むことができる。このように、ハッシュテーブルモジュール１１１は、データグループ化ロジック１０８−１を介して復元モジュール１０８によって選択される部分的に重なり合うデータシングルに関するハッシュ値を演算処理できる。その上、重なり合うシングルに対するハッシュテーブルモジュール１１１によって演算処理されるハッシュ値は、シングルオフセット値が、圧縮ハッシュテーブル１１１−２等のデータ構造及び／又はシステム１００に常駐するメモリ内に格納されている場所を表すメモリアドレス位置として用いることができる。
【００４９】
加えて、スキャン及びマッチエンジン１０９は、ハッシュテーブルモジュール１１１を用いて演算処理されたシングルを特定し、同時に、データブロックに関して、それらがデータ入力バッファ１１２−１に書き込まれる間に比較操作を実行できる。例えば、圧縮ハッシュテーブル１１１−２を用いて、スキャン及びマッチエンジン１０９は、受信データセットに関係するシングルに対する演算処理されたハッシュ値が、圧縮ハッシュテーブル１１１−２内に格納されたハッシュ値と同じ署名を共有していると判断した場合に、「ハッシュヒット」の発生を検出できる。このように、スキャン及びマッチエンジン１０９は、２つのシングルが署名演算処理エンジン１１３によって演算処理された同じ又は類似の署名を有する場合、ハッシュヒットの発生を検出できる。
【００５０】
更に、スキャン及びマッチエンジン１０９は、信号を復元モジュール１０８に送信して、ハッシュヒットカウンタ１１１−３等の圧縮性カウンタをインクリメントする機能を含んでいる。このように、ハッシュヒットカウンタ１１１−３は、スキャン及びマッチエンジン１０９がハッシュヒットの発生を検出する度に、インクリメントすることができる。ハッシュヒットカウンタ１１１−３は、システム１００が、システム１００によって受信される受信データセット内に頻繁に現れるハッシュ値を常時監視することを可能にする。従って、データ入力バッファ１１２−１へのデータ転送の終了時に、システム１００は、データセット全体に対する１セットの演算処理されたハッシュを格納できる。
【００５１】
加えて、システム１００は、どのデータブロックがそこで実行されるデータ整理プロシージャ（例えば、データ重複排除プロシージャ、参照ブロック識別プロシージャ、データ圧縮プロシージャ、等）を有することから最良に恩恵を受けるのかを、良好に判断することが可能となる高頻度ハッシュ値マッチ閾値を格納するよう構成することができる。このように、システム１００は、所定の閾値及び／又は演算処理された圧縮性カウントを用いて圧縮特性を自動的に解釈することを可能にする方法で構成することができる。例えば、システム１００による何らかのデータ整理プロシージャの実行前に、それは、所定の閾値カウントを先ず参照し、データ整理操作を実行、中止、及び／又は一時停止するか否かを決定できる。
【００５２】
このように、復元モジュール１０８等のシステム１００のコンポーネントは、閾値カウントが高頻度ハッシュ値マッチ閾値に達するか、又はそれを超えた場合、システム１００のコンポーネントにデータ整理操作（例えば、データ重複排除プロシージャ、参照ブロック識別プロシージャ、データ圧縮プロシージャ、等）の実行を初期化するよう命令する命令又は命令のセットを生成できる。従って、システム１００のコンポーネントは、閾値カウントが高頻度ハッシュ値マッチ閾値に達していない場合、システム１００のコンポーネントにデータ整理操作の実行を控えるよう命令する命令又は命令のセットを生成できる。システム１００によるかかる判断は、ホストＣＰＵのサイクルを軽減できるだけではなく、データが、ホストドライバ等の他のドライバに割込をかけることなく、システムを介して移動することも可能にできる。
【００５３】
例えば、一実施形態において、ハッシュヒットカウンタ１１１−３の値が所定の閾値未満である場合は、復元モジュール１０８は、現在解析中のデータブロックが低い圧縮特性を呈し、それによって、データストリームの少なくとも一部に対する高いエントロピーレベル示すことを判断してもよい。従って、この判断に応じて、復元モジュール１０８は、何の復元操作も行わないよう構成することができる。このように、復元モジュール１０８は、復元操作の実行を中止及び／又は一時停止する命令を送信するよう構成することができる。
【００５４】
しかし、ハッシュヒットカウンタ１１１−３の値が所定の閾値以上である場合は、復元モジュール１０８は、データブロックが高い圧縮特性を呈し、それによって、データストリームの少なくとも一部に対する低いエントロピーレベル示すことを判断してもよい。従って、この判断に応じて、復元モジュール１０８は、復元操作の実行を初期化する命令を送信するよう構成することができる。このように、復元モジュール１０８は、圧縮係数を用いて、「圧縮」又は「バイパス圧縮」信号を、データ入力バッファ１１２−１内に格納される受信データセットに関する所定セットのバイトのために、システム１００の他のコンポーネントに発行するか否かを判断する。
【００５５】
このように、システム１００は、所定のデータセットのデータブロック間の検出された類似性の頻度に基づいて、データ入力バッファ１１２−１内に格納されるデータセットに関するエントロピーを測定できる。一実施形態によれば、スキャン及びマッチエンジン１０９は、データのヒストグラム表現を用いてハッシュヒットの頻度を演算処理できる。加えて、ハッシュヒットカウンタ１１１−３は、ハードウェア又はソフトウェアにより実装することができる。
【００５６】
更に、システム１００は、システム負荷及び／又はユーザの基本設定に基づいて閾値を動的に調整するよう構成することもできる。このように、圧縮のための閾値は、パワー及び待ち時間を犠牲にして圧縮率を向上させる目的のために緩和することができる。同様に、より短い平均待ち時間を達成するために、より高い閾値が用いられてもよい。
【００５７】
図２Ａは、本発明の実施形態による単一パスエントロピー検出のための例示的な処理の第１の部分のフローチャートである。
【００５８】
ステップ２０５において、入力データストリームが、システムによって受信され、データ入力バッファ内に格納される。データストリームを受信すると、復元モジュールは、データグループ化ロジックを用いて、データ入力ストリーム内で見つかったデータの複数のサブセットをグループ化する。サブセットのサイズは、所定であり、固定サイズであってもよい。
【００５９】
ステップ２０６において、データ入力バッファに格納されたデータに対してフィンガープリント演算処理エンジンによって生成されたフィンガープリントデータを用いて、署名演算処理エンジンが、ステップ２０５中に格納されたようなデータストリーム内のデータの第１のグループ化サブセットのための第１の署名を演算処理する。
【００６０】
ステップ２０７において、ハッシュテーブルモジュールは、データの第１のグループ化サブセットに対する第１のハッシュ値を演算処理し、演算処理されたハッシュ値をハッシュテーブルに格納されているハッシュ値と比較してマッチングを検出する。
【００６１】
ステップ２０８において、ハッシュテーブルモジュールは、データの第２のグループ化サブセットに対する第２のハッシュ値を演算処理し、演算処理されたハッシュ値をハッシュテーブルに格納されているハッシュ値と比較してマッチングを検出する。
【００６２】
ステップ２０９において、ハッシュテーブルモジュールは、データの第ｎのグループ化サブセットに対する第ｎのハッシュ値を演算処理し、演算処理されたハッシュ値をハッシュテーブルに格納されているハッシュ値と比較してマッチングを検出する。
【００６３】
ステップ２１０において、復元モジュールが、ハッシュテーブルモジュールによって検出されたマッチングを監視し、それに応じて、検出された各マッチングのためのカウンタをインクリメントする。
【００６４】
図２Ｂは、本発明の実施形態による単一パスエントロピー検出のための例示的な処理の第２の部分のフローチャートである。操作２１０（図２Ａ参照）の詳細は、図２Ｂにおいて略述する。
【００６５】
ステップ２１１において、復元モジュールが、所定の高頻度ハッシュ値マッチ閾値に対するカウンタの値に基づいて、入力データストリームの一部に対するエントロピーレベルを決定する。
【００６６】
ステップ２１２において、高頻度ハッシュ値マッチ閾値が達せられたか、超えたかを検出することに関して、復元モジュールによって決定が行われる。復元モジュールが、高頻度ハッシュ値マッチ閾値が達せられたか、超えたことを検出した場合は、復元モジュールは、入力データストリームの一部に対して高いエントロピーレベルを決定し、それに応じて、信号をシステムコンポーネントに伝えて、ステップ２１３で詳述するように、データ整理操作の実行を初期化する。復元モジュールが、高頻度ハッシュ値マッチ閾値が達せられていないと検出した場合は、復元モジュールは、入力データストリームの一部に対して低いエントロピーレベルを決定し、それに応じて、信号をシステムコンポーネントに伝えて、ステップ２１４で詳述するように、データ整理操作の実行を中止する。
【００６７】
ステップ２１３において、復元モジュールは、高頻度ハッシュ値マッチ閾値が達せられたか、超えたことを検出し、従って、復元モジュールは、入力データストリームの一部に対して高いエントロピーレベルを決定し、それに応じて、信号をシステムコンポーネントに伝えて、データ整理操作の実行を初期化する。
【００６８】
ステップ２１４において、復元モジュールは、高頻度ハッシュ値マッチ閾値が達せられていないと検出し、従って、復元モジュールは、入力データストリームの一部に対して低いエントロピーレベルを決定し、それに応じて、信号をシステムコンポーネントに伝えて、データ整理操作の実行を中止する。
【００６９】
図３Ａは、本発明の実施形態による同時データ重複排除及び圧縮のための例示的な処理のフローチャートである。操作２１３（図２Ｂ参照）の詳細は、図３Ａにおいて略述する。
【００７０】
ステップ２１５において、参照ブロック識別モジュールは、ステップ２０６中に演算処理された署名を、システムによって現在格納されている署名のクラスタと比較し、それに応じて、演算処理された署名を最良に表している参照ブロックを選択する。参照ブロック識別モジュールによって選択された参照ブロックは、システムによる更なる処理のために参照ブロックバッファ内に格納される。
【００７１】
ステップ２１６において、参照ブロックがステップ２１５において格納されている間に、ハッシュテーブルモジュールが、参照ブロックに対応するシングル形ハッシュ値を演算処理する。
【００７２】
ステップ２１７において、ステップ２１６中に演算処理されたハッシュ値は、ハッシュ値が参照ハッシュテーブル内にまだ格納されていないことを条件に、ハッシュテーブルモジュールによって生成される参照ハッシュテーブル内に格納される。
【００７３】
ステップ２１８において、少なくとも１つの参照ブロックが参照ブロックバッファ内に格納されていることを条件に、ハッシュテーブルモジュールは、信号をスキャン及びマッチエンジンに送信して、ステップ２０７、２０８、及び／又は２０９の間に演算処理されたハッシュ値に基づいて更に処理するために、参照ハッシュテーブル及び／又は圧縮ハッシュテーブルを用いてハッシュテーブルルックアップ及び／又はヘッダ修正プロシージャを実行する。
【００７４】
図３Ｂは、本発明の実施形態によるハッシュテーブルルックアッププロシージャを実行するための例示的な処理のフローチャートである。操作２１８（図３Ａ参照）の詳細は、図３Ｂにおいて略述する。
【００７５】
ステップ２１９において、演算処理されたハッシュ値と参照ハッシュテーブル内に排他的に格納されるエントリとの間のマッチングを検出したかどうかに関する決定が、スキャン及びマッチエンジンによって行われる。スキャン及びマッチエンジンが、マッチングが検出されたことを判断した場合、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、ステップ２２０で詳述するように、バイト単位でマッチングしたエントリに関連する参照ブロックバッファに格納される参照ブロックと比較する。スキャン及びマッチエンジンが、何のマッチングも検出されなかったことを判断した場合、演算処理されたハッシュ値と圧縮ハッシュテーブル内に排他的に格納されるエントリとの間のマッチングを検出したかどうかに関する決定が、スキャン及びマッチエンジンによって行われる。
【００７６】
ステップ２２０において、スキャン及びマッチエンジンは、マッチングが検出されたことを判断し、従って、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、バイト単位でマッチングしたエントリに関連する参照ブロックバッファに格納される参照ブロックと比較し、それに応じて、信号を復元モジュールに送信して、「１１」等の参照コピーのための修正された圧縮ヘッダフォーマットを用いて参照ブロックバッファ内のデータのサブセットを復元する。復元された出力は、データ出力バッファ内に格納される。
【００７７】
ステップ２２１において、スキャン及びマッチエンジンが、何のマッチングも検出されなかったことを判断し、従って、演算処理されたハッシュ値と圧縮ハッシュテーブル内に排他的に格納されるエントリとの間のマッチングを検出したかどうかに関する決定が、スキャン及びマッチエンジンによって行われる。スキャン及びマッチエンジンが、マッチングが検出されたことを判断した場合、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、ステップ２２２で詳述するように、バイト単位でデータ入力バッファ内に現在格納されているデータと比較する。スキャン及びマッチエンジンが、何のマッチングも検出されなかったことを判断した場合、ステップ２２３で詳述するように、演算処理されたハッシュ値と、参照ハッシュテーブル及び圧縮ハッシュテーブル内の両方に格納されるエントリとの間のマッチングを検出したかどうかに関する決定が、スキャン及びマッチエンジンによって行われる。
【００７８】
ステップ２２２において、スキャン及びマッチエンジンは、マッチングが検出されたことを判断し、従って、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、バイト単位でデータ入力バッファ内に現在格納されているデータと比較し、それに応じて、信号を復元モジュールに送信して、適切なビット長及びオフセットに基づいて、「０１」又は「１０」等のローカルコピーのための修正された圧縮ヘッダフォーマットを用いてデータ入力バッファ内のデータのサブセットを復元する。復元された出力は、データ出力バッファ内に格納される。
【００７９】
ステップ２２３において、スキャン及びマッチエンジンが、何のマッチングも検出されなかったことを判断し、従って、演算処理されたハッシュ値と、参照ハッシュテーブル及び圧縮ハッシュテーブル内の両方に格納されるエントリとの間のマッチングを検出したかどうかに関する決定が、スキャン及びマッチエンジンによって行われる。スキャン及びマッチエンジンが、マッチングが検出されたことを判断した場合、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、バイト単位でデータ入力バッファ内に現在格納されているデータと比較し、それに応じて、信号を復元モジュールに送信して、所定のプロシージャに基づいて、データ入力バッファ内のデータのサブセットを復元する。
【００８０】
ステップ２２４において、スキャン及びマッチエンジンが、マッチングが検出されたことを判断し、従って、スキャン及びマッチエンジンは、ハッシュ値に関連するデータのサブセットを、バイト単位でデータ入力バッファ内に現在格納されているデータと比較し、それに応じて、信号を復元モジュールに送信して、所定のプロシージャに基づいて、データ入力バッファ内のデータのサブセットを復元する。一実施形態によれば、所定のプロシージャは、コピーの長さ、及び／又は、データストリームに関連するデータの他のいくつかの知識に応じて、復元プロシージャのその選択を、ローカルマッチ又は参照マッチに向かってバイアスをかけるよう、スキャン及びマッチエンジンを構成することを含むことができる。
【００８１】
ステップ２２５において、スキャン及びマッチエンジンが、何のマッチングも検出されなかったことを判断し、従って、演算処理されたハッシュ値が、ハッシュテーブルモジュールによって生成される圧縮ハッシュテーブル内に格納される。
【００８２】
ステップ２２６において、スキャン及びマッチエンジンは、信号を復元モジュールに伝えて、「００」等のリテラルシーケンスのための修正された圧縮ヘッダフォーマットを用いてデータ入力バッファに格納されるデータのサブセットを復元する。復元された出力は、データ出力バッファ内に格納される。
【００８３】
ある特定の好ましい実施形態及び方法を本明細書中で開示してきたが、当業者にとって、前述の開示から、かかる実施形態及び方法の変更及び改良が、発明の精神及び適用範囲から逸脱することなく行われてもよいことは、明白である。
【００８４】
実施形態によれば、本明細書中で説明する技法は、１つ以上の特殊用途演算装置によって実装することができる。特殊用途演算装置は、技法を実行するハードワイヤードであってもよく、又は、技法を実行するよう永続的にプログラミングされた１つ以上の特定用途向け集積回路（ＡＳＩＣ）又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のデジタル電子装置を含んでもよく、又は、ファームウェア、メモリ、他の記憶装置、又はその組み合わせにおけるプログラム命令に従って技法を実行するようプログラミングされた１つ以上の汎用ハードウェアプロセッサを含んでもよい。かかる特殊用途演算装置は、技法を達成するよう、カスタムプログラミングを有するカスタムハードワイヤードロジック、ＡＳＩＣ、又はＦＰＧＡを組み合わせてもよい。特殊用途演算装置は、データベースサーバ、ストレージ装置、デスクトップコンピュータシステム、可搬型コンピュータシステム、携帯装置、ネットワーキング装置、又は、技法を実装するようハードワイヤード及び／又はプログラムロジックを組み込んだ何らか他の装置であってもよい。
【００８５】
本発明の実施形態の前述の詳細な説明において、本発明の完全な理解を提供するために、数多くの特定の詳細を説明してきた。しかし、本発明は、これらの特定の詳細がなくても実施可能であることは、当業者によって認識されるであろう。他の例では、周知の方法、プロシージャ、コンポーネント、及び回路は、本発明の実施形態の態様を不必要に不明瞭にしないように、詳細に説明されてはいない。方法は、明確にするために番号の付いたステップのシーケンスとして示すことが可能であるが、番号付けは、必ずしもステップの順序を定めるものではない。ステップの内のいくつかは、省略され、同時に実行され、又は、シーケンスの順序を厳格に維持する必要なく実行されてもよいことは、言うまでもない。発明の実施形態を示す図面は、半図解式であり、正確な縮尺で描かれてはおらず、特に、寸法のいくつかは、描写を明確にするためであり、図中で誇張して示されている。同様に、説明を容易にするための図中の視点は、概して、類似する向きを示しているが、図中におけるこの描写は、多くの部分に対して任意である。
【符号の説明】
【００８６】
１００  システム
１０１  プロセッサ
１０２  表示装置
１０３  入出力装置
１０４  コンピュータ読取可能記憶媒体
１０５  グラフィックスシステム
１０６  バス
１０７  オペレーティングシステム
１０８  復元モジュール
１０８−１  データグループ化ロジック
１０９  スキャン及びマッチエンジン
１０９−１  リテラルスキャンロジック
１０９−２  ローカルコピースキャンロジック
１０９−３  ハッシュテーブルルックアップロジック
１１０  フィンガープリント演算処理エンジン
１１１  ハッシュテーブルモジュール
１１１−１  参照ハッシュテーブル
１１１−２  圧縮ハッシュテーブル
１１１−３  ハッシュヒットカウンタ
１１２  バッファ管理コントローラ
１１２−１  データ入力バッファ
１１２−２  データ出力バッファ
１１２−３  参照ブロックバッファ
１１３  署名演算処理エンジン
１１４  参照ブロック識別モジュール
１１５  インターフェースモジュール
１１６  データストリーム
１１６−１、１１６−２、１１６−Ｎ  データ粒子
１１６ａ  ヘッダデータ
１１６ｂ  圧縮ペイロード
１１７−１  参照識別子
１１７−２  ビットベクトル
１１７−３  粒子数
１１７−４  ヘッダＣＲＣデータ
１１８  参照ブロック
１１８−１、１１８−２、１１８−３、１１８−４  参照ブロックデータサブセット
１２０  入力データブロック
【図１Ａ】
0006370838.tif 000003
【図１Ｂ】
0006370838.tif 000004
【図１Ｃ】
0006370838.tif 000005
【図１Ｄ】
0006370838.tif 000006
【図２Ａ】
0006370838.tif 000007
【図２Ｂ】
0006370838.tif 000008
【図３Ａ】
0006370838.tif 000009
【図３Ｂ】
0006370838.tif 000010