データ・クラスタを使用する冗長性の少ないデータを格納する方法
本明細書は、冗長性の少ない形式でデータを格納するための方法および装置を記載する。バイナリ・ラージ・オブジェクト（ＢＬＯＢ）は、分割方法に従ってサブブロックに分割され、サブブロックはサブブロック・クラスタに格納される。各ＢＬＯＢは、クラスタ内のサブブロックの隣接シーケンスを識別するサブブロックのスパンのリストとして表示される。記憶装置の冗長性は低減することができる。何故なら、２つの異なるＢＬＯＢのスパンは同じサブブロックを参照することができるからである。サブブロック・ハッシュをサブブロック・クラスタ番号にマッピングするためにインデックスを使用することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ・システムにおいて記憶空間が少なくてすむ形式でデータを格納する方法および装置に関する。
【背景技術】
【０００２】
従来のコンピュータ記憶システムは、通常、ファイル・システム内に名前付きファイルとしてバイトのシーケンスを格納している。多くのファイルは相互に非常に似ている場合があり、データの大部分１３０、１３２を共有している場合がある（図１３）のに、これらのシステムはこの冗長性を除去することができない。それどころか、これらのシステムは、同じデータの多数のコピー１３０、１３２を保持しながら各ファイル１４０、１４２を別々に格納していることもある（図１４）。
【０００３】
従来のファイル・システムの中には、個々のファイルを圧縮するために、（ＧＺｉｐのような）従来の損失を起こさないテキスト圧縮アルゴリズムを組み込んでいるものがあるが、これは「鍵穴」冗長除去技術と見なすことができる。何故なら、この技術は、ファイル・システムを全体として分析するのではなく、ある時点で１つのファイルの冗長性を分析するからである。これらの従来のテキスト圧縮アルゴリズムは、ファイル・システムの異なる部分の２つの類似しているファイル１３０、１３２のような遠く離れているデータ１５０、１５２間の類似性を見つけることができない場合がある（図１５）。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
そこで、データのその反復シーケンスのいくつかを識別し、格納しているこの反復データのコピーの数を低減することができる形式でデータを表示する方法および装置が求められている。
【課題を解決するための手段】
【０００５】
データの反復シーケンスのコピーの数を低減するような方法で、いくつかの異なるバイナリ・ラージ・オブジェクト（ＢＬＯＢ）１０、１２を表示するために、２つ以上のＢＬＯＢ表示により各反復シーケンスを参照することができる表示を使用することができる。図１６は、このことを達成することができる１つの方法を示す。この実施形態の場合には、各ＢＬＯＢ１６０、１６２はサブブロックと呼ばれる部分Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇに分割され、サブブロックの複製１６４、１６６は識別され、１回だけ格納される。このフレームワークにおいては、下記の問題が解決される。すなわち、ＢＬＯＢをサブ分割する方法、結果として得られるサブブロックを格納する方法、およびサブブロックの複製を識別するための方法。
【０００６】
本発明のある態様によれば、格納するデータの各ＢＬＯＢ１０、１２は、分割方法によりサブブロックＡ〜Ｊに分割される（図１）。種々の分割方法を使用することができるが、特に、データを固定長のサブブロック６０〜６５に分割する固定長分割方法を使用することもできるし（図６）、またはデータ自身により定めた位置で（図１）、データを可変長のサブブロックＥ、Ｆ、Ｇ、Ａ、Ｂ、Ｃ、Ｄに分割する可変長分割方法を使用することもできる（図１０）。本発明者と同じ発明者であるＷｉｌｌｉａｍｓの米国特許第５，９９０，８１０号に、この後者の方法の一例が開示されている。この米国特許は、参照により本明細書に組み込まれ、図３７に示す。
【０００７】
サブブロックは、冗長除去の単位になり、ある実施形態の場合には、システムは、せいぜい一度だけ一意の各サブブロックを格納する。他の実施形態の場合には、一意の各サブブロックのコピーの数は低減するが、２以上の場合がある。
【０００８】
例示的実施形態の場合には、ＢＬＯＢのサブブロックは、サブブロック・クラスタ２０、２２、２４と呼ばれるグループ内に格納される（図２）。各ＢＬＯＢは、それぞれが１つのクラスタ２０、２２、２４内のサブブロックの隣接シーケンスを識別するレコード（「スパン・レコード」）３０、３１、３２の順序付きリスト（またはツリー）により表示することができる（図３および図４）。ＢＬＯＢ１０は、スパン３０、３１、３２のリストにより識別されたシーケンスの連結として表示することができ（図３および図４）、各スパンが参照したサブブロック内のサブブロック・コンテンツを検索するスパンのＢＬＯＢのリストを順次チェックすることにより、記憶装置から検索することができる。
【０００９】
例示的実施形態においては、クラスタ２０、２２、２４は、２つ以上のＢＬＯＢ ＸおよびＹからのサブブロックを含むこともできるし（図４）、ＢＬＯＢのサブブロックは、２つ以上のクラスタ内に常駐することもできる（図３）。例示的実施形態において、ＢＬＯＢのサブブロックを１つまたは複数のクラスタ内に順次格納することができる（図２）。これによりＢＬＯＢ検索の効率が改善される。何故なら、ＢＬＯＢ内のサブブロックの全シーケンスを、１回の順次読出動作でディスクから読み出すことができるからである。このことは、各サブブロックを探してランダム・アクセス・ディスク・シークを行うよりも遥かに効率的である。
【００１０】
例示的実施形態においては、同じまたは異なるＢＬＯＢ内の異なるスパンは、同じサブブロックを含む（図４）。これにより冗長性を低減することができる。何故なら、同じサブブロックを含むＢＬＯＢは、（クラスタ内の）同じサブブロックを指すスパンにより表示することができるからである。
【００１１】
本発明のさらに他の態様によれば、各クラスタは、クラスタが使用するスペースの大きさを低減するためにデータ圧縮方法により圧縮される。これを行う最も簡単な方法は、全クラスタを圧縮することである。いくつかの実施形態（特に大きなクラスタを使用する実施形態の場合には）においては、全クラスタ（またはサブブロックを読み出す前のクラスタの少なくとも一部）を圧縮解除しなくても、クラスタ内のサブブロックにアクセスすることができるように、クラスタの各部分（例えば、個々のサブブロックまたはサブブロックの一続きの部分）を圧縮することが望ましい場合がある。
【００１２】
本発明のさらに他の態様によれば、各クラスタ内のサブブロックのディレクトリ７０が各クラスタに対して生成され、（通常は開始のところの）クラスタ内に格納されるか（図７）、または別々に８０、８２（図８）内に格納される。ディレクトリは、例えば、サブブロックの前に各サブブロックのメタデータを格納することにより、クラスタ全体に分配することもできる（図９）。ディレクトリは、そのハッシュ、長さ、サブブロック識別子、およびクラスタ内のその位置のような、各サブブロックに対する種々のメタデータを含むことができる。
【００１３】
本発明のさらに他の態様によれば、２つ以上のＢＬＯＢが共有するサブブロックが識別される。例示的実施形態においては、サブブロックのコンテンツまたはサブブロック・ハッシュ（サブブロックのコンテンツのハッシュ）をクラスタ５２、５４、５６にマッピングする（または関連付ける）サブブロック・インデックス５０が維持される。格納動作中、格納される各サブブロックが、サブブロック・インデックス内で参照される。存在する場合には、サブブロックは再度格納されない。サブブロックが存在しない場合には、サブブロックはクラスタ内に格納され、それに対するエントリがサブブロック・インデックスに追加される。いずれの場合も、新しいサブブロックがスパン５８により参照される。
【００１４】
本発明のある態様によれば、特定のサブブロックが記憶装置内にすでに存在していることをインデックスが示す場合には、一致するサブブロックのクラスタがアクセスされ、クラスタ内の一致するサブブロックの後のサブブロックが、格納するＢＬＯＢ内の一致するサブブロックの後のサブブロックと比較される（図１０）。この比較はインデックスにアクセスしないで行うことができ、実際には、サブブロックを含んでいるクラスタが、サブブロック・ハッシュを含むサブブロック・ディレクトリを有している限り、実際のサブブロック・コンテンツ・データにアクセスしないで行うことができる。
用語
欠落サブブロック：記憶装置内に存在していないサブブロック
ＢＬＯＢ（バイナリ・ラージ・オブジェクト）：データのゼロまたはそれ以上のバイト（またはビット）の有限シーケンス。その名前にも関わらず、ＢＬＯＢは必ずしも大きくはない。ＢＬＯＢは、数ビットまたはバイトのように小さいものであってもよいし、またはギガバイトのように大きいものであってもよい。
【００１５】
ＢＬＯＢレコード：特定のＢＬＯＢについての情報を記録している記憶装置内に維持されているレコード。また、ＢＬＯＢレコードは、ＢＬＯＢコンテンツを定義するスパンのリスト（またはツリー）を含むこともできるし、または参照することもできる。
【００１６】
ＢＬＯＢテーブル：ＢＬＯＢ識別子（例えば、制限なしに、ＢＬＯＢハッシュ）をＢＬＯＢレコードに関連付けるデータ構造
クラスタ：「サブブロック・クラスタ」の短縮語。関連するサブブロックのグループ。クラスタは、クラスタ内のサブブロックについての情報を提供する関連サブブロック・ディレクトリを有することができる。
【００１７】
クラスタ・サブブロック・ディレクトリ：クラスタ内のサブブロックについての情報を提供するメタデータの集合体。サブブロックのメタデータは、サブブロックの長さ、ハッシュ、識別子および基準カウントを含むことができる（しかし、含むことができるものはこれらに限定されない）。
【００１８】
隣接する：物事の順序付きグループ内の２つの物事が隣り合っている場合には、隣接するという。Ｎの物事が正確にＮ−１の隣り合った１対の物事を含んでいる場合には（すなわち、Ｎの物事が１つの連続している一続きの部分として表される場合には）、物事の順序付きグループ内のＮという物事は隣接している。
【００１９】
隣接サブブロック：隣り合っている場合には、あるコンテキスト（例えば、ＢＬＯＢまたはクラスタ）において、２つのサブブロックは隣接している。Ｎという物事が正確にＮ−１の隣り合った１対のサブブロックを含んでいる場合には（すなわち、サブブロックが１つの連続している一続きの部分となっている場合には）、あるコンテキストにおいてＮのサブブロックは隣接している。
【００２０】
ディレクトリ：クラスタ・サブブロック・ディレクトリ参照
ディスク：コンピュータが使用するランダム・アクセス記憶媒体。通常、ディスクという用語は、磁化したデータを保持している金属の回転円盤（ハードディスク）を意味する。本明細書においては、ディスクという用語は、メモリよりかなり遅いランダム・アクセス記憶媒体を意味するようにもっと広義に解釈することができる。
【００２１】
固定長分割方法：データを固定長サブブロックに分割するデータを分割するための方法。例えば、固定長分割方法は、ＢＬＯＢを５１２バイトのサブブロックに分割することができる。
【００２２】
ハッシュ：ハッシュ・アルゴリズムが生成したバイト（またはビット）の固定長シーケンス。サブブロックのハッシュは、サブブロックを索引し、比較するためのサブブロックを表すものとして使用することができる。
【００２３】
ハッシュ・アルゴリズム：バイト（またはビット）の有限シーケンスを受け入れ、入力シーケンスに高度に依存するバイト（またはビット）の有限シーケンスを生成するアルゴリズム。通常、ハッシュ・アルゴリズムは、特定の固定長の出力を生成する。ハッシュ・アルゴリズムは、シーケンスを直接比較しなくても、データの２つのシーケンスが同じであるか否かをチェックするための試験に使用することができる。実際に暗号化ハッシュを使用すれば、そのハッシュが同じである場合、２つのサブブロックが同じであると結論することができる。ハッシュ・アルゴリズムは、ＢＬＯＢ識別子を生成し、サブブロックを比較し、ハッシュ・テーブル・キーを生成するために、例示的実施形態において使用することができる。
【００２４】
サブブロックのハッシュ：サブブロック・ハッシュ参照
インデックス：サブブロック・インデックス参照
インデックス・バケット：ハッシュ・テーブルを使用してサブブロック・インデックスを実施する実施形態の場合には、ハッシュ・テーブルを、それぞれが空であるかエントリを含み、それぞれが一定数のエントリ・スロットを含むバケットのアレイとして構成することができる。インデックス・バケットの１つの目的は、ハッシュ・テーブルを、ランダム・アクセス・ディスク動作の回数を低減するために、グループとしてディスクから読み出し、ディスクに書き込むことができる部分に構成することである。
インデックス・エントリ：サブブロック・インデックス内のレコード。ある実施形態の場合には、インデックス・レコードは、インデックス・キーおよびインデックス値を含む。ある実施形態の場合には、インデックス・レコードは、インデックス・キーの一部およびインデックス値を含む。ある実施形態の場合には、インデックス・レコードはインデックス値だけを含む。ある実施形態の場合には、インデックス・レコードは値を含まないで、キーの一部または全部を含む。
【００２５】
インデックス・キー：サブブロックについての情報を検索するために、サブブロック・インデックスに提供されるサブブロックについての情報。ある実施形態の場合には、この情報はインデックス・エントリの位置を発見し、読み出すことにより検索される。
【００２６】
インデックス値：サブブロック（またはその一例がそのハッシュであるサブブロックの派生物）をインデックスで参照した場合に、インデックスによりサブブロックについて生成された情報。ある実施形態の場合には、この値は、ディスク上のサブブロックの位置からなる。他の実施形態の場合には、インデックスの唯一の目的がキーの有無を記録することである場合には、値が存在しない場合がある。ある実施形態の場合には、この値は単にクラスタ数からなる。
【００２７】
サブブロックの長さ：サブブロック・コンテンツ内のバイト（またはビット）数
線形探索：１つずつ集合体内のオブジェクトをチェックすることによる、およびチェックする次のオブジェクトの選択が前のチェックの結果により影響を受けない場合の、オブジェクトの集合体内の１つのオブジェクトに対する探索方法。
スパンのリスト：スパンの順序付きリスト。このようなリストは、ＢＬＯＢのコンテンツを表示するために使用することができる。
【００２８】
一致する一続きの部分：（例えば、格納しているＢＬＯＢ内に存在してもよい）サブブロックの他のシーケンスと一致する（クラスタ内の）サブブロックのシーケンス。ある実施形態の場合には、サブブロックのシーケンスは隣接している。
【００２９】
メモリ：通常、ランダム・アクセス・メモリ（ＲＡＭ）を参照するコンピュータが使用するランダム・アクセス記憶媒体。本明細書においては、この用語は、「ディスク」よりかなり速いランダム・アクセス記憶媒体を意味するようにもっと広義に解釈することができる。
【００３０】
分割方法：ＢＬＯＢ内の各バイト（またはビット）が、正確に１つのサブブロック内に入るように、ＢＬＯＢを１つまたは複数のサブブロックに分割するための方法。
【００３１】
存在サブブロック：記憶装置内に存在するサブブロック。
【００３２】
低冗長：バイト（またはビット）の同一シーケンスのコピー数の任意のタイプのデータ表示での低減である。
【００３３】
低冗長記憶装置：データのその表示の際に、自身が格納している一組のデータ内の複製データのいくつかを除去する記憶システム。
【００３４】
サブブロックへの参照：サブブロックを識別する１つのデータ。例えば、制限なしで、参照は、コンテンツまたは格納位置によりサブブロックを識別することができる。
【００３５】
基準計数：あるエンティティがもはや必要なくなった時を判定するための方法。この方法は、エンティティに対して存在する参照の数を記録するカウンタを維持するステップを含む。基準カウントがゼロになった場合には、エンティティを削除することができる。ある実施形態の場合には、ＢＬＯＢおよび／またはサブブロックは基準カウントを有する。
【００３６】
スパン：クラスタ内のサブブロックのシーケンス。ある実施形態の場合には、このシーケンスは隣接している。
【００３７】
スパン・レコード：クラスタ内のスパンを識別するレコード。ある実施形態の場合には、スパン・レコードは、クラスタ番号フィールド、開始サブブロック識別子フィールド、および（サブブロックまたはバイトの）スパン長フィールドを含む。
【００３８】
記憶装置：低冗長記憶装置参照。
【００３９】
サブブロック：索引、比較および／または冗長除去のための単位として識別されたバイト（またはビット）のシーケンス。ＢＬＯＢはサブブロックに分割することができる。
【００４０】
サブブロック・クラスタ：一緒に格納している１つまたは複数のサブブロックのグループ。「クラスタ」とも呼ばれる。
【００４１】
サブブロック・コンテンツ：サブブロックのメタデータとは異なるサブブロックの実際のデータ。
【００４２】
サブブロック・ディレクトリ：クラスタ・サブブロック・ディレクトリ参照。
【００４３】
サブブロック満了日：サブブロックをユーザが必要としないことを保証された場合に、最も初期の日付を定義するサブブロックと関連する１つのメタデータ。
【００４４】
サブブロック・ハッシュ：サブブロックへのハッシュ・アルゴリズムの適用結果。サブブロックのハッシュは、例えば、サブブロックを索引および／または比較するために、サブブロックを表すものとして使用することができる。
【００４５】
サブブロック識別子：サブブロックに関連する１つのメタデータ。識別子はクラスタ内のサブブロックに対して一意のものであり、それ故、そのクラスタ内のサブブロックを一義的に識別するために使用することができる。ある実施形態の場合には、異なるクラスタ内のサブブロックは、同じ識別子を有することができる。
【００４６】
サブブロック・インデックス：サブブロックの位置（例えば、制限なしで、クラスタ番号（およびまた、おそらくサブブロック識別子））に、サブブロックのハッシュ（またはサブブロック自身）をマッピングする（または他の方法で関連付ける）データ構造。
【００４７】
サブブロック・メタデータ：サブブロックについての情報。サブブロックのメタデータは、（制限なしに）サブブロックの長さ、サブブロックのハッシュ、サブブロックの識別子、サブブロックの満期日付、およびサブブロックの基準カウントを含むことができる。
【００４８】
サブブロック・レコード：１つのサブブロックに対するメタデータを含むクラスタ・サブブロック・ディレクトリ内のレコード。
【００４９】
サブブロック基準カウント：サブブロックに対する参照の現在数を記録する１つのサブブロック・メタデータ。ある実施形態の場合には、これはサブブロックを含むスパンを定義するスパン・レコードの数である。
【００５０】
サブブロック一連番号：サブブロック識別子の形式。例えば、一連番号システムを使用するある実施形態の場合には、特定のクラスタに到着するサブブロックには、第１のサブブロックに対して１から始まり増大する一連番号が割り当てられる。ある実施形態の場合には、サブブロックを削除した場合には、一連番号は再使用されない。これらの実施形態の場合には、一連番号は、クラスタ内のサブブロックを一意に識別する方法を提供する。
【００５１】
ユーザ：記憶装置内にＢＬＯＢを格納し、検索する１つのソフトウェア。
【００５２】
可変長分割方法：ＢＬＯＢを可変長サブブロックに分割する分割方法。好ましい実施形態の場合には、可変長分割方法は、データをデータのコンテンツが決定する境界のところで分割する。例えば、制限なしに、分割方法は、前のいくつかのバイトが、特定の所定の一定値にハッシュするＢＬＯＢ内の各位置のところのサブブロック境界を定義することができる。
【００５３】
仮想ブロック装置：オペレーティング・システムが提供する固定長記憶ブロックのアレイからなる装置。仮想装置は、物理デバイスに直接対応することができ、または（例えば、ＲＡＩＤを使用して）１つまたは複数の物理デバイスから構成することができる。
【００５４】
全キー：小さな派生キーの元として使用されるキー。データ構造が成長し、派生キーが必要になるので、全キーの増大する部分を、派生キーを形成するのに使用することができる。
【００５５】
本明細書全体および添付の特許請求の範囲を通して、別段の指示がない限り、「備える」および「含む」という用語、および「備えている」および「含んでいる」という派生語は、「包含」および「除外しないこと」を意味する用語であると理解されたい。例えば、このような用語を記載の整数または整数のグループを参照するために使用した場合には、このような用語は、任意の他の整数または整数のグループの除外を意味しない。
【００５６】
本明細書の添付の特許請求の範囲は、本明細書に記載する本発明の広義の記述であり、参照により本明細書に組み込まれる。
【００５７】
本明細書での任意の従来技術への参照は、このような従来技術が共通の一般的知識の一部を形成しているという容認でもなければ、任意の形式の示唆でもないし、またそのように解釈すべきでもない。
【００５８】
添付の図面を参照しながら、以下に本発明の特定の実施形態についてさらに詳細に説明する。これらの実施形態は、説明のためのものであって、本発明の範囲を制限するためのものではない。他の実施形態の示唆および記述を本発明の範囲内に含めることができるが、これらのものは添付の図面には示していないし、または別の方法で本発明の機能を図面には示してあるが本明細書には記述していない。
【発明を実施するための最良の形態】
【００５９】
図５は、本発明の典型的な実施形態の要素の概観である。この実施形態は、ＢＬＯＢレコード５１、５３と、スパン・リスト５８と、クラスタ５２、５４、５６と、サブブロック・インデックス５０とを含む。図３８は、典型的なコンピュータ・ハードウェア上でのこれらの要素の配置を示す。すべてのデータ構造はディスク３８０上に常駐している。インデックス３８１も、いくつかのＢＬＯＢレコード３８２およびクラスタ３８３のいくつかの作業コピーを格納しているいくつかのキャッシュと一緒にメモリ内に保持されている。
６．１ ハッシュ関数の概観
すべての実施形態においてはハッシュ関数を使用していないが、ハッシュ関数は、多くの実施形態でいくつかの利点を提供する。下記の説明は、本発明の種々の実施形態に関連して使用することができる例示としてのハッシュ関数の概観である。
【００６０】
ハッシュ関数は、ビットの可変長入力ブロックを受け入れ、入力ブロックをベースとするビットの出力ブロックを生成する。大部分のハッシュ関数は、出力ブロックが特定の長さ（例えば、１６ビット）になることを保証し、入力ブロックの無限集合と出力ブロックの有限集合との間でランダムではあるが、決定論的マッピングを提供するようにする。ランダムさの特性により、「ハッシュ」と呼ばれるこれらの出力を、入力ブロックの容易に操作した表示として動作させることができる。
【００６１】
ハッシュ関数は少なくとも４つのクラスの強度を有する。
【００６２】
狭いハッシュ関数：狭いハッシュ関数は、最も弱いクラスのハッシュ関数であり、出力値の全スペースを妥当な時間内に探索することができるような、非常に狭い（例えば、１６ビット）出力値を生成する。例えば、８ビットのハッシュ関数は、任意のデータ・ブロックを０〜２５５の範囲内のハッシュにマッピングする。１６ビットのハッシュ関数は、０〜６５５３５の範囲内のハッシュにマッピングする。特定のハッシュ値の場合には、単に探索する値が表れるまで、ランダム・ブロックを生成し、これらのブロックを狭いハッシュ関数に提供することにより、対応するブロックを発見することができる。狭いハッシュ関数は、一組のデータ値を少数のグループに任意に（しかし決定論的に）分類するために、通常、使用される。それ故、狭いハッシュ関数は、ハッシュ・テーブル・データ構造を構成し、ノイズの多い通信チャネルを通して送信したデータのエラーを検出するのに役に立つ。このクラスの例としては、ＣＲＣ−１６、ＣＲＣ−３２、フレッチャ・チェックサム、ＩＰチェックサム等がある。
【００６３】
広いハッシュ関数：広いハッシュ関数は、その出力値がかなり広いということを除けば、狭いハッシュ関数に類似している。ある点においては、この定量的違いは、定性的違いを意味する。広いハッシュ関数の場合には、出力値が非常に広い（例えば、１２８ビット）ので、同じハッシュ値を有する任意の２つのランダムに選択したブロックの確率は無視することができる（例えば、１０３８のうちの約１）。この特性により、これらの広いハッシュを、これらが計算されたデータのブロックの「ＩＤ（ｉｄｅｎｔｉｔｙ）」として使用することができる。例えば、エンティティＥ１がデータのブロックを有し、エンティティＥ２にブロックの広いハッシュを送った場合で、エンティティＥ２が同じハッシュを有するブロックを有している場合には、ブロックが実際に異なる先験的確率は無視することができる。唯一の問題は、広いハッシュ関数が非反転できるように設計されていないことである。それ故、（例えば）２１２８値のスペースは、狭いハッシュ関数のところで説明した方法で探索するにはあまりに広すぎるが、ハッシュ関数を分析し、特定のハッシュに対応するブロックを計算するのは容易である。それ故、Ｅ１が本当に異なるブロックである場合には、Ｅ１は、Ｅ２がＥ１が１つのブロックを有すると思い込ませることができる。このクラスの例としては、任意の１２８ビットのＣＲＣアルゴリズムがある。
【００６４】
弱一方向ハッシュ関数：弱一方向ハッシュ関数は、「ＩＤ」を提供するのに十分広いばかりでなく、特定のハッシュ値が与えられた場合、そのハッシュ値に対応するブロックを発見するのが極度に難しい暗号保証を提供する。このクラスの例としては、６４ビットＤＥＳハッシュがある。
【００６５】
強一方向ハッシュ関数：強一方向ハッシュ関数は、同じハッシュ値を有する任意の２つの異なるブロックを発見するのが難しい暗号保証を提供する追加特性を有することを除けば、弱一方向ハッシュ関数と同じものである。この場合、ハッシュ値は指定されない。このクラスの例としては、ＭＤ５およびＳＨＡ−１がある。
【００６６】
これら４つのクラスのハッシュは、選択が行われるある範囲のハッシュ強度を提供する。予想されるように、ハッシュ関数の速度は、強度が増大するにつれて低減し、トレードオフを提供し、異なる用途の場合には異なる強度が適切な強度になる。しかし、違いは非常に小さいので、最もタイムクリティカルな用途以外では、強一方向ハッシュ関数を使用することができる。
【００６７】
暗号ハッシュという用語は、多くの場合、弱一方向ハッシュ関数のクラスおよび強一方向ハッシュ関数のクラス両方を含む暗号強度を提供するハッシュを指すために使用される。
【００６８】
本発明の例示的実施形態は、少なくとも２つの役割でハッシュ関数を使用することができる。
【００６９】
１．サブブロック境界を決定するために。
【００７０】
２．サブブロックＩＤを生成するために。
【００７１】
用途に従って、上記４つのクラスのうちの任意のクラスからのハッシュ関数をいずれかの役割で使用することができる。しかし、サブブロック境界の決定にはＩＤおよび暗号強度が必要ないので、最も弱いクラス以外からのクラスからのハッシュ関数を使用するのは非効率である。同様に、ＩＤの必要性、絶えず存在する破壊行為の脅威、および強一方向ハッシュ関数（弱一方向ハッシュ関数と比較した場合）に対する低性能というペナルティは、強一方向ハッシュ関数より弱いいかなるものもサブブロックＩＤの計算に使用すべきではないことを示唆している。
【００７２】
ＩＤを生成するために強一方向ハッシュ関数以下の何かを使用する際につきもののセキュリティの危険は、任意のこのような弱ハッシュ関数を使用する本発明を組み込む記憶システムを考慮することにより説明することができる。このようなシステムにおいては、侵入者は、修正したサブブロックが、ターゲット・システム内にすでに存在することを侵入者が知っている他のサブブロックと同じハッシュを有するように、（ターゲット・システムにより操作される）サブブロックを修正することができる。そうすると、ターゲット・システムがそれを新しいものと置き換えないで、既存のサブブロックを保持する結果になる恐れがある。（例えば）ターゲット・システムがネットワーク上で検索したセキュリティ・パッチを正しく適用するのを防止するために、このような弱点を使用することができる。
【００７３】
それ故、敵意を持つ人間に曝されないシステムでサブブロックを計算するのに、広いハッシュ関数を安全に使用することができるが、弱一方向ハッシュ関数が、これらのシステムでは非セキュアとなる恐れがある。
【００７４】
ここで、ブロックまたはサブブロックのハッシュを実際に使用することができる方法について説明する。
６．２ 暗号ハッシュの使用
暗号ハッシュ（およびここでは強一方向ハッシュ関数）の理論特性は、特に興味のある実際の特性を生成する。このようなハッシュはかなり広いので、２つのランダムに選択したサブブロックが、同じハッシュを有する確率は事実上ゼロであり（１２８ビット・ハッシュの場合には、１０３８のうちの約１であり）、同じハッシュを有する２つのサブブロックを発見するのは計算上不可能であるので、スパイがそのようなことを行うことができないことを事実上保証している。これらの特性の密接な関係は、実際の見地から見ると、特定の暗号ハッシュ・アルゴリズムに対するハッシュ値の有限集合は、有限の可変長サブブロックの無限集合に対して１対１の関係になる。これは、同じ値にハッシュする２つのサブブロックを発見するのは実際上不可能であるので、実際には、理論上不可能な特性であることは明らかである。
【００７５】
この特性は、（同一であることのために）比較の目的で、計算されたサブブロックの代わりに、暗号ハッシュを安全に使用することができることを意味する。大部分の暗号ハッシュは約１２８ビットの長さしかないので、ハッシュは、サブブロック自身のコンテンツを直接比較しなくても、サブブロックを比較するための非常に効率的な方法を提供する。
【００７６】
本発明の例示的実施形態で暗号ハッシュが使用されるいくつかの方法は下記の通りである。
【００７７】
サブブロックの比較：暗号ハッシュＨは、２つのサブブロックＡ、Ｂのコンテンツを比較しなくても、またはアクセスしなくても、２つのサブブロックＡ、Ｂを比較２８０するために使用することができる（図２８）。
【００７８】
サブブロックのインデックス：サブブロックＡ、Ｂ、Ｃ、Ｄの集合体を索引するために、そのキーがサブブロック２９２、２９４、２９６、２９８のハッシュであるインデックス２９０を構成することができる（図２９）。
ＢＬＯＢチェック：ＢＬＯＢ３００のサブブロック３０２への分割、および再構成したＢＬＯＢ３０４へのサブブロックの以降の再組立を確実にエラーのないものにするために、暗号ハッシュを使用することができる。このことは、元のＢＬＯＢのハッシュ３０６を再構成したＢＬＯＢのハッシュ３０８と比較３０９することにより行うことができる（図３０）。
６．３ 安全ネットとしてのハッシュの使用
本発明の実施形態は、これらの実施形態を組み込む記憶システムをさらに複雑にする場合がある。このように複雑になると、潜在的にエラーが検出されない機会が多くなる。
【００７９】
複雑さの主な機構は、ＢＬＯＢのサブブロックへの分割であり、このようなサブブロックの以降の再組立である。ＢＬＯＢをサブブロックに分割することにより、記憶システムが、サブブロックを間違って追加したり、削除したり、再配置したり、置換したり、複製したり、または何らかの他の方法で偶然のエラーのより大きなリスクに曝されたりする恐れがでてくる。
【００８０】
このリスクは、サブブロックに分割される前にＢＬＯＢのハッシュ（好適には暗号ハッシュであることが好ましい）を計算し、このハッシュを全体としてＢＬＯＢに関連するエンティティと一緒に格納し、次に、格納しているハッシュを、再構成したブロックの計算したハッシュと比較することにより、低減または除去することができる。このようなチェックは、本発明を使用することによるエラーが検出されないリスクを事実上取り除く非常に強力な安全ネットを提供する（図３０）。
【００８１】
ＢＬＯＢをチェックするもう１つの方法は、そのサブブロックのハッシュの連結をハッシュし、記憶装置からＢＬＯＢを検索した場合の値をチェックする方法である。この方法は、全体的に見てハッシュしなければならないデータが少なくてすみ、このような実施形態をより効率的にすることができるという利点を有する。
６．４ クラスタ内へのサブブロックの格納
クラスタ内にサブブロックを格納することができる方法は多数ある。「サブブロックのコンテンツ」という用語は、実際のサブブロックを形成するバイトのシーケンスを意味する。例示的実施形態においては、クラスタ７４内のサブブロック７２は、メタデータの介入なしで背中合わせに格納される（図７）。クラスタがそれ自身のディレクトリを持たない実施形態の場合には、背中合わせのサブブロック・コンテンツは、クラスタが含んでいなければならないすべてのものであってもよい。
【００８２】
背中合わせにサブブロックを格納する利点は、サブブロックの隣接する一続きの部分を１つのシーケンシャルな動作としてクラスタから読み出すことができることであり、次に、最初に、メタデータを除去しなくても、メモリ内に保持し、１つのシーケンシャルな動作として書き出すことができることである。
【００８３】
サブブロックをクラスタに分割する方法を決定するために多数の方法を使用することができる。１つの方法は、少なくともＳ個のサブブロックを有するまでクラスタにサブブロックを書き込む方法である。ここで、Ｓは所定の定数である。もう１つの方法は、少なくともＭメガバイトを含むまで、クラスタにサブブロックを書き込む方法である。ここで、Ｍは所定の定数である。
６．５ クラスタ・サブブロック・ディレクトリ
クラスタは、クラスタ内のサブブロックについての情報を提供し、クラスタ内のサブブロックの位置を迅速に発見することができるサブブロック・ディレクトリを有することができる。
【００８４】
クラスタは、ディレクトリ７０を有している場合には、ディレクトリをクラスタの始めの部分（図７）またはクラスタの終わりの部分に置くことができる。もう１つの例は、サブブロック・コンテンツ９２とディレクトリ９０エントリをインタリーブする例である（図９）。最後に、ディレクトリ８０、８２は別々に格納することができる（図８）。
【００８５】
１つの簡単なオプションは、クラスタ内のサブブロック数上に上部限界Ｌを置き、クラスタ内のサブブロック数が何であれ、カウントにＬディレクトリ・エントリのアレイを加えたものとしてディレクトリを表す方法である。これにより固定長ディレクトリ８０、８２が出来上がり、クラスタのディレクトリを、残りのクラスタのコンテンツ８４、８６（すなわち、サブブロックのコンテンツ）とは別々に１つのアレイを格納することができる（図８）。
６．６ クラスタ・サブブロック・ディレクトリ内のサブブロック・メタデータ
クラスタのサブブロック・ディレクトリは、各サブブロックの長さを格納することができる。通常、各サブブロックの長さの単位はバイトである。サブブロックの長さを格納した場合には、クラスタのサブブロックのコンテンツを、境界がサブブロック間にあることを決定するために、分割方法を呼び出さなくても、サブブロックに分割することができる。
【００８６】
クラスタのディレクトリは、各サブブロックのハッシュを格納することができる。例えば、ディレクトリは、クラスタ内の各サブブロックの１２８ビットのＭＤ５または１６０ビットのＳＨＡ−１を格納することができる。各サブブロックのハッシュを格納することは役に立つ。何故なら、格納中、システムが、サブブロックＸのコンテンツをサブブロックＹのコンテンツと比較しなくても、新しく到着したサブブロックＹがクラスタ内で発見されたことを確認することができるからである。代わりに、システムは、サブブロックＹのハッシュを計算し、それを（そのクラスタのディレクトリ内で発見することができる）サブブロックＸのハッシュと比較する。それ故、格納しているＢＬＯＢ内のサブブロックを、記憶装置内のサブブロックのコンテンツを読み出さなくても、インデックスおよびクラスタ・ディレクトリだけを使用して、記憶装置内に存在しているか否かを試験することができる。
【００８７】
また、クラスタのディレクトリは、各サブブロックに対するサブブロック識別子を格納することもできる。サブブロックの識別子は、クラスタ内の一組のサブブロック内で一意のものである。サブブロック識別子を実施する１つの簡単な方法は、固定幅（例えば、１６ビット）を選択し、各クラスタ内の一連番号カウンタを割り当て、ゼロから開始し、次の整数を各サブブロックにその一連番号識別子として割り当てる方法である。カウンタが最大値に達した場合には、クラスタを新データに対して単に閉鎖することができる。別の方法としては、サブブロックをクラスタから削除した場合には、未使用の識別子を再度割り当てることができる。これはサブブロック識別子を実施する多くの方法のうちの１つの方法である。
【００８８】
一連番号をサブブロック識別子として使用した場合には、その連続性をＢＬＯＢ内のサブブロックの１つの一続きの部分から格納したクラスタ内のサブブロック２７６〜２７８の一続きの部分の始まりおよび終わりを示すために使用することができる。ある実施形態の場合には、このことは各格納している一続きの部分２７２、２７４の終わりのところの一連番号をスキップ（廃棄）することにより行うことができる（図２７）。一連番号を使用しない場合には、クラスタ内のサブブロックの一続きの部分の（元のＢＬＯＢ内のサブブロックの一続きの部分に対する）終わりを示すために、各サブブロックのメタデータに、ブール値を追加することができる。
６．７ クラスタの圧縮
システム内に圧縮（例えば、制限なしに、ＧＺｉＰ）を組み込むことができる方法は多数ある。１つの簡単な方法は、ディスクに書き込む前に、各クラスタに対して１つのシーケンシャルな動作として圧縮を行う方法である。もう１つの方法は、各サブブロックを個々に圧縮する方法である。もう１つの方法は、隣接する一連番号と一緒にサブブロックの各一続きの部分を圧縮する方法である。
【００８９】
クラスタは、圧縮した形式でディスク上に格納することができる。また、これらのクラスタは、圧縮した形式でメモリに格納することもできる。
６．８ スパン・サブブロック−一続きの部分の識別
各スパンは、特定のクラスタ内のサブブロックの一続きの部分を識別する。例示的実施形態の場合には、スパンは、サブブロックの一続きの部分を含むクラスタを識別する情報を含む。サブブロックの一続きの部分を識別するための広い範囲の可能性がある。そのため、一続きの部分内の最初および最後のサブブロックを識別することができ、または最初（または最後）のサブブロックを識別することができ、長さを提供することができる。長さはバイト単位またはサブブロック単位で測定することができる。
【００９０】
例示的実施形態のサブブロックを識別するために、スパンは、サブブロックのハッシュ（この場合、クラスタは（サブブロックのディレクトリを使用して（１つ有している場合））サブブロックを探索しなければならないが）、クラスタ（例えば、「第３のサブブロック」）内のサブブロックの位置、またはサブブロック識別子を使用することができる。
【００９１】
ハッシュの幅は比較的広い。クラスタ内に（例えば）１０００のサブブロックが存在する場合には、サブブロック識別子は、約１０ビットの幅を有していればよいのだが、典型的なハッシュは１２８ビットの幅を有する。そのクラスタ内の（サブブロック単位で測定した）位置を使用すると、スペースをもっと効率的に使用することができるが、（サブブロックを含んでいるＢＬＯＢを記憶装置から削除した場合に起こるかもしれないように）サブブロックをクラスタから削除した場合、故障が起こる。これを避けるために、例示的実施形態の場合には、（クラスタ内で一意の）クラスタ内の各サブブロックに一意の識別子を割り当てることができる。この識別子は、クラスタのディレクトリ内に各サブブロックのメタデータと一緒に格納することができる。このような識別子は、（ビット単位で）十分狭いものであってもよいが、サブブロックがクラスタ内でシフトしても、サブブロックをはっきりと識別する。
【００９２】
もう１つのアプローチは、そのハッシュでサブブロックを参照する方法であるが、同じクラスタ内で他のすべてのサブブロックからそのサブブロックを区別するために必要なものである。スパン・レコード内の短い固定長フィールドは、記録するハッシュのバイト数を記録するために使用することができる。この方法を使用すれば、サブブロック識別子を使用する必要がなくなるし、スパン・レコードに長いハッシュによる負担がかからなくなる。この方法を使用すれば、スパン・レコードは可変長を有することができる。この方法の１つの潜在的な問題は、クラスタに追加されるサブブロックが、既存の参照を曖昧にする恐れがあることである。この問題は、このような曖昧な参照がいつでも曖昧な参照を満たす第１のサブブロックを参照するように注意することにより解決することができる。
【００９３】
もう１つの方法は、サブブロックの一連番号を使用するが、これらの一連番号をスパンにより直接参照されるサブブロックだけに割り当てる方法である。実際には、スパンの第１のサブブロックは非常に少ないので、遥かに少ない数の一連番号を格納するだけですむ。
６．９ 部分サブブロックの一致
ＢＬＯＢ１７０の格納中、１つまたは複数の一致するサブブロックＢ、Ｃの一続きの部分をクラスタ１７４内で発見した場合には、一致しているサブブロックの一続きの部分のどちらかの側面上の一致していないサブブロックのある部分が、格納しているＢＬＯＢ内の対応するサブブロックの対応部分と一致する可能性がある。図１７は、格納中のＢＬＯＢ１７０および比較しているクラスタ１７４を示す。インデックスを使用して、サブブロックＢＣの一致する一続きの部分を発見した。各側面上のサブブロックは一致しない。ＡはＥと一致しないし、ＤはＦと一致しない。それ故、一致する一続きの部分はちょうど２つのサブブロックの長さである。しかし、ＢＣの一致を発見した場合、周囲のサブブロックをもっと精密なレベルで比較することができる。
【００９４】
サブブロックＡの終わりとサブブロックＥの終わりと比較すれば、これらのサブブロックが、同じ（例えば）１２３バイトの接尾部を共有していることが分かる。同様に、サブブロックＤの始まりをサブブロックＦの始まりと比較すると、これらのサブブロックが、同じ（例えば）１０４５バイトの接頭部を共有していることが分かる。これらを部分サブブロックの一致と呼ぶ。
【００９５】
部分サブブロックの一致を発見した場合には、多数の方法を使用することができる。図１８は、スパン内の最初のサブブロックの始まりのところ、およびスパン内の最後のサブブロックの終わりのところで無視すべきバイト数を記録する余分なフィールド「開始スキップ」１８０および「終了スキップ」１８２を含むように、スパン・レコード構造を増大することができる方法を示す。もう１つの方法は、サブブロックのどちらかの終わりを延長するために、バイト数を記録する２つのフィールド「開始エクステンド」および「終了エクステンド」を使用する方法である。ある実施形態は、上記各フィールドの一方または両方の使用を選択することができる。
【００９６】
サブブロックの一続きの部分内のバイトのある範囲を参照するもう１つの方法は、「終了スキップ」フィールドを、スパン内のバイトの全数である長さで置換する方法である。
６．１０ フラグメンテーションの低減
格納しているＢＬＯＢがすでに格納済みの多くのサブブロックを含んでいるが、多くの異なるクラスタ全体に散乱している場合には、ＢＬＯＢは、ディスク全体を指すスパンのリストの表示で終わる。要するに多数に分割される。
【００９７】
一致しないサブブロックの長い一続きの部分内の１つのサブブロックが一致する場合には、ある特に不都合な形のフラグメンテーションが起こる。図１９は、ＢＬＯＢ１ １９０が記憶装置内にすでに格納されていて、ＢＬＯＢ２ １９２を格納中であり、１つの一致するサブブロックＣが、ＢＬＯＢ２内のサブブロックＦ〜Ｍの他の方法で一致しない一続きの部分内に位置するこの一例を示す。結果としては、一致するサブブロックに対する１つのスパン・レコード１９４がスパン・リスト１９６内に生成される。このタイプのフラグメンテーションは、ＢＬＯＢ２の検索時間を長くする傾向がある。何故なら、ランダム・ディスク・アクセスを、第１のクラスタ１９８および第２のクラスタ１９９に対して行わなければならないからである。
【００９８】
ある種の実施形態は、孤立している一致サブブロックを一致していないとして処理し、これらのサブブロックを次に格納することにより、このタイプの１つの一致サブブロック・フラグメンテーションを避けることができる。図２０は、余分のスペースを使用するが、ＢＬＯＢ２ ２０２のフラグメンテーションを低減することにより、サブブロックＣの孤立している一致を格納させるのを無視する方法を示す。この方法は、一致するサブブロックの予め定義したしきい値Ｔより短いすべての一致する一続きの部分を無視することにより一般化することができる。ある実施形態の場合には、１より大きいＴの任意の値はフラグメンテーションを低減する傾向がある。値２も役に立つ。
６．１１ ＢＬＯＢテーブル
ＢＬＯＢを格納する記憶システムは、そのユーザがＢＬＯＢを検索することができるように、ＢＬＯＢを参照することができるようにするある方法を提供するものでなければならない。
【００９９】
１つの方法は、ＢＬＯＢのハッシュ１１０を識別子として使用する方法である（図１１）。それ故、ユーザは、ＢＬＯＢを記憶システムに提出し、ＢＬＯＢのハッシュ（例えば、ＭＤ５ハッシュ）を書き留める。ＢＬＯＢを検索するために、ハッシュを記憶システムに提出し、システムはＢＬＯＢを返送する。
【０１００】
もう１つの方法は、任意の名前を各ＢＬＯＢに割り当てる方法である。従来のファイル・システムはこの方法を使用する。
【０１０１】
どんなネーミング・スキームを採用しようとも実施しなければならない。このような実行は、本質的には、ＢＬＯＢ１１２名前空間から（スパンのリスト１１６を含む（または参照する）ＢＬＯＢレコード１１４自身へのマッピングからなる（図１１）。このマッピングは、デジタル探索ツリー、Ｂツリーおよびハッシュ・テーブルのようなすべてのタイプの従来のデータ構造を使用して行うことができる。
６．１２ スパンのリストおよびツリー
ＢＬＯＢテーブル１１２が参照する各ＢＬＯＢレコード１１４は、ＢＬＯＢの任意のメタデータを含み、スパン・レコード１１６の順序付きシーケンスを含んでいるかまたはポイントする（図１１）。各スパン・レコードは、クラスタ内のサブブロックの（隣接する）一続きの部分を識別する。
【０１０２】
スパンの順序付きリスト内にスパンを維持すると、全ＢＬＯＢをシーケンシャルに効率的に検索することができるが、格納しているＢＬＯＢ上でランダム・アクセス読出しを行うために線形探索（またはスパン・レコードをランダムにアクセスできる場合には、二分探索）を必要とする。ランダム・アクセス読出しをスピードアップするために、ＢＬＯＢのスパンをツリー構造に編成することができる。図２６は、３つの分岐を含むツリーの一例である（が、任意の分岐を使用することができる）。各非葉ノードは、その子ノードが表すブロックの連結であるバイトの有限個のブロックを表す。各ノードは、その子ノードが表すブロックの長さである３つの長さを含む。各葉ノードは、クラスタ内の１つまたは複数のサブブロックのシーケンスを識別するスパン２６０からなる。このようなツリーが表す格納しているＢＬＯＢのバイトＪ〜Ｋのランダム・アクセス読出しは、バイトＪ〜Ｋを含むスパンを発見するためにツリーを下方に移動し、次にクラスタからサブブロック・コンテンツ・バイトを検索することにより行うことができる。
６．１３ サブブロック・インデックス
サブブロック・インデックス（図５）を使用すれば、記憶装置内のすべてのクラスタの線形探索を行わなくても、記憶装置内に特定のサブブロックがすでに存在するか否かを判定することができる。また、インデックスは、一致するサブブロックの位置を発見する際に役に立つ情報を提供することができる。
【０１０３】
インデックス５０は、それぞれがインデックス・キーをインデックス値に結合しているエントリの組織した集合体として表示することができる。エントリは、エントリ・レコード（それぞれがキー・フィールドおよび値フィールドからなる）として、インデックス内に明示的に、または（例えば、インデックスが、キー上に葉ノード内に値を含むバイナリ・デジタル探索ツリーとして組織されている場合には）暗黙的に格納することができる。
【０１０４】
インデックス・キーは、サブブロックのコンテンツであっても、サブブロックのコンテンツのハッシュであっても、またはサブブロックのコンテンツのハッシュの単なる一部であってもよい。サブブロックのコンテンツのハッシュの一部（例えば、全１６バイトではなく、ＭＤ５ハッシュの最初の８バイト）だけを格納すると、時に起こる衝突を犠牲にして、インデックスのサイズを小さくすることができる。２つ以上のサブブロックが同じ部分ハッシュを有している場合には、インデックスは、両方のエントリを格納し、検索することができるものでなければならない。
【０１０５】
インデックス値は、記憶装置内のサブブロックの位置を発見する際に役に立つ情報でなければならない。ある極端な実施形態の場合には、この値は、クラスタ番号およびクラスタ内の特定のサブブロック（例えば、識別子、サブブロック一連番号またはサブブロック・ハッシュ）を識別する情報からなる正確な参照を提供することができる。極端な他の実施形態の場合には、インデックス値をクラスタ番号だけから構成することができる。サブブロックのクラスタ番号が分かると、存在する場合には、クラスタ内のサブブロックを発見するためにクラスタ・ディレクトリを探索することができる。インデックス内のスペースをさらに制約するために、インデックス値を、探索するのに２つ以上のクラスタを必要とするクラスタ番号の一部（例えば、クラスタ番号の最後の２つのビット）だけで構成することができる。
【０１０６】
選択の優れた組合わせは、インデックス・キーをサブブロック・ハッシュの頂部の８バイトとし、インデックス値をサブブロックを含むクラスタの数とする方法である。各クラスタに対するディレクトリが存在する限り、これらの選択は、インデックスのサイズを小さいままに維持し、依然として記憶装置の任意のサブブロックに高速でアクセスすることができる。
【０１０７】
インデックスは、デジタル探索ツリー、バイナリ・ツリー、およびハッシュ・テーブルを含む種々のデータ構造により行うことができる。
６．１４ インデックスの格納
インデックスは、メモリ内またはディスク上に格納することができる。インデックスのサイズの低減は、インデックスがメモリ内に保持されている場合には重要な問題である。実験の結果、ある実施形態の場合には、インデックスがメモリ内に保持されている場合には、システムの動作が遥かに速くなることが分かっている。クラスタ内の目標のサブブロックの位置を識別する情報を格納しなくてすむならば、インデックスのサイズをかなり低減することができる。それ故、典型的な実施形態の場合には、インデックス内にクラスタ番号だけを格納する。
６．１５ サブブロック・インデックスのためのハッシュ・テーブルの使用
サブブロック・インデックスは、低冗長記憶システムの速度を判定する際に非常に重要なものであるので、このデータ構造を最高速でアクセスできるように設計するのは重要なことである。ハッシュ・テーブルは、０（１）時間内にアクセスを提供するので、ハッシュ・テーブルは、サブブロック・インデックスに対して非常に優れたデータ構造を提供する。しかし、このハッシュ速度アクセスは、かなり高いものにつく。以下のいくつかの節は、サブブロック・インデックスが提起する課題について説明する。
６．１６ ハッシュ・テーブルの衝突
この節においては、ハッシュ・テーブルの衝突について説明するが、インデックスがハッシュ・テーブルを使用して実施される場合にだけ適用される。
【０１０８】
衝突は、２つのキー２１０、２１２が、同じ位置（スロット）２１６にハッシュ２１４した場合に、ハッシュ・テーブル内で起こる（図２１）。この状況を解決する１つの方法は、第２のエントリを単に廃棄するという方法である。ある場合には、これは正しい選択である場合がある。しかし、ハッシュ・テーブルが損失を許容するものでない場合には、このオプションを使用することはできないので、この「オーバーフロー」状況を処理するために種々様々な技術のうちの１つを使用することができる。
【０１０９】
衝突を処理するために昔から使用されてきた１つの技術は、「オーバーフロー」領域２２０と呼ぶ別の記憶領域を有する方法である。各ハッシュ・テーブル・スロットは、オーバーフロー・フィールド２２２を含む。スロット内で衝突が起きた場合には、オーバーフロー・エントリ２２４は、オーバーフロー領域内に格納され、エントリへのポインタがスロット２２２内に置かれる（図２２）。オーバーフロー領域によりエントリはまた相互にポイントすることができ２２６、各オーバーフロー・スロットは、エントリのリストをポイントすることができる（図２２）。（ハッシュ・テーブルがメモリ内に位置していて、メモリ・ヒープの形をしている場合のように）別々のオーバーフロー領域を使用できる場合には、この技術はうまく動作する。しかし、ハッシュ・テーブルがディスク上に位置している場合には、オーバーフロー領域内にオーバーフロー・エントリを置くと、通常、非常に遅い少なくとも１回のランダム・アクセス・シークを行うステップが関連してくる。
【０１１０】
衝突へのもっとうまいアプローチは、衝突しているエントリを、ハッシュ・テーブル自身内に格納する方法である。昔からのアプローチの場合には、衝突が起こると、第２のハッシュ関数により第２の項目キーがハッシュされ、結果として得られたスロットがチェックされる。スロットが空である場合には、エントリをそこに格納することができる。もしスロットが空でない場合には、第３のハッシュ関数を呼び出すことができ、空のスロットが発見されるまでこの手順が反復して行われる。全テーブルが満杯である場合には、テーブルを分割してからでなければ、新しいエントリを追加することはできない。一般に、ハッシュ関数Ｈ（Ｋ，Ｘ）は、Ｋがハッシュするキーであり、Ｘが、衝突しているエントリに対するハッシュ・テーブル内の連続している候補の位置を発見するために増大することができる正の整数である場合に定義することができる。キーＫを探索するために、キーを含むスロットを発見するまで、または（テーブル内のハッシュ・オーバーフロー・チェーンの終わりを示す）空のスロットに遭遇するまで、Ｘ＝１，２，．．．に対してスロットＨ（Ｋ，Ｘ）がチェックされる。
【０１１１】
このアプローチの問題は、ハッシュ・テーブルが大きなもので、ディスク上に位置している場合には、衝突チェーンの後で、非常に時間がかかる一連のランダム・アクセス・シークをディスク上で行わなければならないことである。このことはＨ（Ｋ，Ｘ）＝Ｈ（Ｋ，Ｘ−１）＋１と定義することにより、すなわち、（テーブルの終わりのところを囲んでいる）次の隣接スロット２３０（図２３）に溢れることにより避けることができる。この技術の場合には、アクセスは局部的なままである。アクセスした第１のスロットを読み出した場合には、次のＳスロットも小さなＳに対して読み出され、ディスク動作は、（例えば、１２バイトの代わりに１Ｋを読み出すように）余分な時間はかからないし、オーバーフロー・スロットも提供する。新しいエントリが追加されると、複数のスロットを１つのグループとしてディスクに書戻すことができる。衝突チェーンがＳ個のスロットを超えて跨ることが希になるように（およびそれにより追加のディスク・アクセスが必要になるように）（おそらく動的に）値Ｓが調整される。
６．１７ ハッシュ・テーブル・バケット
インデックスがディスク上に格納されている場合には、インデックスへのランダム・アクセス読出しおよび書込みは時間がかかるものになる場合がある。それ故、あるスロットから他のスロットに溢れるチャンスがある場合には、２つ以上のスロットを一度に読出しおよび書込みするのは理にかなっている。そうするための１つの方法は、テーブルをバケット２４０に分割し（図２４）、エントリのかわりにバケットを読み出し、書き込む方法である。例えば、１０２４のスロットのテーブルを、それぞれが１６のスロットを含む６４のバケットのテーブルで置き換えることができる。エントリを探索するために、バケットを読み出して、バケット内で線形探索を行うことができ（またはバケット内のキーがソートされる場合、二分探索をおそらく行うことができる）。時々であるがバケットが満杯になっている場合がある。その場合には、オーバーフローは次のバケットに移動する。テーブルがあまり大きく成長できない限りは、オーバーフロー・チェーンはあまり長くすべきではない。
６．１８ ハッシュ・テーブルの成長
ハッシュ・テーブルを使用した場合の１つの問題は、満杯になった場合、拡張するはっきりした方法がないことである。
【０１１２】
この問題に対する１つのアプローチは、テーブルがけっして満杯にならないようにすることである。このことは、最初に、特定の用途の場合にけっして満杯にならないほど大きなハッシュ・テーブルを生成することにより行うことができる。しかし、ある用途の場合には、予めハッシュ・テーブル上の負荷を予測することができない場合があり、そのため他の解決方法を発見しなければならない。
【０１１３】
１つのアプローチは、新しいもっと大きなハッシュ・テーブルを生成し、旧テーブル内のすべてのエントリを新テーブルに転送することによりハッシュ・テーブルを廃棄する方法である。転送中に両方のテーブルを保持するための十分なメモリが存在する限り、このアプローチは完全に実行可能な方法である。
【０１１４】
もう１つのアプローチは、満杯になったらいつでもハッシュ・テーブルのサイズを２倍にし、第１の（旧）２５０の半体内のエントリの（約）半体を、第２の（新）２５１の半体に転送する方法である。図２５は、その方法を示す。最初のハッシュ・テーブルが２Ｋのエントリを有している場合には、全キーの下のＫビットを、テーブルを索引するために使用することができる。テーブルが満杯になったら２倍に増大することができる。この新テーブルは、全キー２５４のＫ＋１の最も低いビットをキーとして使用する。現在使用しているキーの余分なビット（ビットＫ）は、２倍にしたテーブルの旧テーブルおよび新テーブルの半体を区別する。全キーの左側の残りは未使用のままである。あとは、そのビットＫが１である２倍にしたテーブルの旧半体内のエントリを新半体内の対応する位置に移動するだけでよい。実際には、オーバーフローがあるので、これより少し複雑になる。最初に、オーバーフローは、エントリがテーブルの旧半体内の「自然の」位置に位置していなくて、それ故、すべてのエントリを単に移動すると、ビットＫセットがいくつかのエントリを正しくない位置に移動する。このことは、再ハッシュが必要なことを意味する。第二に、旧半体内のエントリを除去すると、いくつかのオーバーフロー・チェーンが切断する場合があり、いくつかのエントリにアクセスできなくなる恐れがある。それ故、エントリを移動した場合、そのエントリのオーバーフロー・チェーンをギャップを埋めるためにもとに戻してやらなければならない。
６．１９ サブブロック・インデックス部分キーの格納
インデックスのサイズを小さくする１つの方法は、各インデックス・エントリ内にインデックスのキーのコピーを格納しない方法である。例えば、インデックス・キーが、（サブブロックの）１２８ビットのＭＤ５ハッシュである場合には、インデックスのサイズを小さくする１つの方法は、インデックスのエントリ内のキーの一部だけを記録する方法である。
【０１１５】
例えば、インデックスがハッシュ・テーブル１２０として実施される場合には、各ハッシュ・テーブル・エントリ１２２は、通常、クラスタ番号１２４およびサブブロック・ハッシュ１２６のコピーを含む（図１２）。これにより、インデックスのハッシュ・テーブル内の同じ位置に２つのサブブロックがハッシュされた場合には、２つのエントリを区別することができる。しかし、ハッシュが１２８ビット幅を有していて、各ハッシュの６４ビットだけを格納する場合には、エントリは、依然として区別することができるが、スペースの半分を使用することになる。
【０１１６】
極端な場合、ハッシュ・テーブルは、任意のキーの任意の部分を含んでいない。代わりに、各サブブロック・ハッシュは、ハッシュ・テーブル内のある位置にハッシュし、その位置で発見したすべてのクラスタを探索しなければならない。これは、依然として記憶装置内のすべてのクラスタの線形探索より遥かに優れている。
【０１１７】
最善のアプローチは、ハッシュのある部分は格納するが、すべてのハッシュは格納しない方法である。このことは、希な場合ではあるが、ハッシュ・テーブル内に２つ以上の一致するエントリが存在する場合があり、一組の一致するエントリに参照したすべてのクラスタを探索しなければならないことを意味する。エントリ内のハッシュの一部だけを格納すれば、いくつかのクラスタをチェックしなくてもすみ、しかも依然として完全なハッシュよりかなり少ないスペースしか使用しない十分な違いを提供する。
６．２０ ＢＬＯＢの削除
ある用途の場合には、ＢＬＯＢを削除し、またＢＬＯＢを格納しなければならない場合がある。ＢＬＯＢの削除を行わなければならない場合がある。何故なら、ＢＬＯＢのスパン内で参照したすべてのサブブロックを単に削除する（次に、ＢＬＯＢのスパンおよびＢＬＯＢレコードを削除する）明らかなアプローチは、このような行為は、他の（削除していない）ＢＬＯＢの一部でもあるサブブロックを削除する恐れがあるために失敗するからである。もっと高度なアプローチが望ましい。
【０１１８】
ＢＬＯＢを削除するためのあるアプローチは、記憶装置内の各サブブロックに余分なメタデータを追加する方法である。基準カウント。サブブロックの基準カウントは、サブブロックを含む（ＢＬＯＢ内の）スパンの数を格納する。基準カウント・アプローチの場合には、サブブロックを含む新しいスパンが生成されると（すなわち、ＢＬＯＢ格納中に）サブブロックの基準カウントが増大し、このようなスパンが削除されると（すなわち、ＢＬＯＢ削除中に）この基準カウントが低減する。その基準カウントがゼロになった場合には、サブブロックを削除することができる。
【０１１９】
基準カウント・アプローチを使用すれば、記憶システムは、ＢＬＯＢを削除することができる。しかし、ユーザはこの機能を必要としない。基準カウントの他の方法は、満了システムである。このシステムの場合、各ＢＬＯＢおよび各サブブロックは満了日を有する。ＢＬＯＢを格納した場合、ユーザは満了日を提供し、ＢＬＯＢが追加され、スパンの新しいリストが生成される。追加プロセスの一部として、スパン・リストが参照したサブブロックは、その前の満了日の最大値に設定したその満了日を有し、それらを新しく参照しているＢＬＯＢの日付を有する。ＢＬＯＢおよびサブブロックに満了日を表示すると、背景プロセスは、満了したＢＬＯＢおよびサブブロックを自由に削除することができる。
６．２１ 既存のファイル・システムを使用する実施形態
本発明の実施形態は、既存のファイル・システムの頂部上で実施することができる。図３１は、その構成方法を示す。
【０１２０】
このような実施形態の場合、各クラスタは、１つのクラスタ・ファイル３４０内に格納することができる。クラスタに番号が付けられている場合には、各クラスタの名前は、クラスタ番号を含むことができる。クラスタ・ファイルは、１つのディレクトリ３４２またはディレクトリのツリー３４４内に格納することができる（図３４）。クラスタはそのファイル上でランダム・アクセス読出しおよび書込みを行うことにより直接修正することもできるし、またはクラスタ・ファイルをメモリ内の完全な読み出し、それを修正し、およびシーケンシャルなＩＯ動作を使用して、全ファイルをディスクに書き戻すことにより修正することができる。
【０１２１】
もう１つの実施形態は、既存のファイル・システムを使用することができるが、１つのファイルしか使用しない。クラスタは、メモリ内に保持しているクラスタインデックス３３２を使用することにより、隣接して位置する１つのファイル３３０内に格納することができる（図３３）。
【０１２２】
固定長クラスタ・ディレクトリを使用する場合には、クラスタ・ディレクトリの一組全体を、ディレクトリを格納している１つのファイル内にアレイとして格納することができ、ファイルにランダム・アクセスを行って特定のディレクトリにランダム・アクセスすることができるようにする。
【０１２３】
各ＢＬＯＢは、その名前がＢＬＯＢのハッシュの名前であるファイル内に格納することができる。ＢＬＯＢファイルは、ＢＬＯＢディレクトリ内、またはディレクトリ（おそらくＢＬＯＢハッシュの連続しているバイトにより構成されているデジタル探索ツリー）内に格納することができる。各ＢＬＯＢファイルは、ＢＬＯＢを表すスパンのリストを含むことができる。ファイル・システムのファイル毎のスペース・オーバーヘッドを避けるために、複数のＢＬＯＢを１つの「ＢＬＯＢ」ファイル内に格納することができる。
６．２２ 仮想ブロック装置を使用する実施形態
本発明の実施形態は、既存のオペレーティング・システム３２２が提供する仮想ブロック装置を使用して実施することができる（図３２）。クラスタは、メモリ内に保持しているクラスタインデックスを使用することにより、隣接して位置する仮想ブロック装置内に格納することができる。
６．２３ データを格納しない実施形態
すでに説明した実施形態のいずれかと同じではあるが、任意のＢＬＯＢデータを実際に格納しない実施形態を生成することができる（図３５）。このような実施形態の場合には、すべての記憶構造およびメタデータを構成することができるが、ＢＬＯＢ／サブブロック・コンテンツは格納されない。この実施形態のような実施形態は、前に遭遇したＢＬＯＢ１に関連してＢＬＯＢ２を分析しなければならない用途の際に役に立つが、その場合、ＢＬＯＢを実際には格納してはならない。
【０１２４】
例えば、セキュリティ環境においては、ＢＬＯＢコンテンツ自身を格納しないで、前に遭遇したＢＬＯＢに関連してＢＬＯＢを分析するためにＢＬＯＢメタデータを使用する方が有利な場合がある。記憶構造および既存のＢＬＯＢを表すメタデータを使用することにより、記憶装置は、前に遭遇したＢＬＯＢにアクセスしなくても、前に遭遇したＢＬＯＢの本体に関連して文書を分析することができる。例えば、このことはセキュアなゲートウェイに適用することができる。
６．２４ 範囲に関する注
当業者であれば、本発明は、上記の特定の用途に限定されないことを理解することができるだろう。また、本発明は、本明細書に記載し図面に示した特定の要素および／または機能に関してその好ましい実施形態に限定されない。本発明の原理から逸脱することなしに、種々の修正を行うことができることを理解することができるだろう。それ故、本発明は、本発明の範囲内に入るすべてのこのような修正を含むものと解釈すべきである。
【図面の簡単な説明】
【０１２５】
【図１】ＢＬＯＢのサブブロックへの分割である。
【図２】クラスタ内のＢＬＯＢのサブブロックの記憶装置である。
【図３】ＢＬＯＢを、クラスタ内のサブブロックの一続きの部分を識別するスパンの順序付きリストとして表す方法である。
【図４】データの共通シーケンス（サブブロックＡ〜ＣおよびＧ〜Ｊ）を含む２つの異なるＢＬＯＢを、各反復サブブロックを２回以上格納しないですむ方法で表す方法である。
【図５】サブブロックを含むクラスタの数に各サブブロックのハッシュをマッピングするインデックスを示す。
【図６】ＢＬＯＢを固定長サブブロックに分割する分割方法である。
【図７】クラスタの開始のところにサブブロック・ディレクトリを含むサブブロックのクラスタである。
【図８】クラスタのディレクトリをクラスタ自身とは別々に格納する方法である。
【図９】クラスタ・サブブロック・ディレクトリのエントリをクラスタ全体に分配する方法である。
【図１０】（格納しているＢＬＯＢの）サブブロックＡがクラスタ＃１内にすでに存在することを発見した後で、ＢＬＯＢ内の以降のサブブロック（Ｂ、ＣおよびＤ）をそのクラスタ内でＡの後のサブブロック（この場合は、Ｂ、ＣおよびＤ）と比較することができ、それによりサブブロック・インデックス内のＢ、ＣおよびＤを参照しなくてもすむＢＬＯＢを格納する態様を示す。
【図１１】それぞれが、ＢＬＯＢ内のサブブロックを識別するスパンの順序付きリストを含む（または参照する）ＢＬＯＢレコードにＢＬＯＢハッシュをマッピングするＢＬＯＢテーブルである。
【図１２】サブブロック・インデックス・ハッシュ・テーブルであり、テーブルのエントリである。
【図１３】（従来技術）データの同じサブ・シーケンスの２つの例を含む２つのファイルである。さらに、ファイルＡは、それ自身の中に同一のファイルを有する。
【図１４】（従来技術）従来の記憶システムのその共通データを識別しようとしないファイルの格納方法である。
【図１５】（従来技術）従来のデータ圧縮が各ＢＬＯＢのサイズを小さくするが、ＢＬＯＢ間のデータの共通シーケンスを識別しないことを示す。
【図１６】データの同じシーケンスを含む２つのＢＬＯＢの表示が、データのこれらのシーケンスを参照し、そのためシーケンスを１回格納するだけですむ方法である。
【図１７】任意の部分一致があるか否かをチェックするために、一致する一続きの部分の各端部のところのサブブロックを直接比較する方法である。
【図１８】一続きの部分の両端のところに部分サブブロックを含むサブブロックの一続きの部分を表すために（それぞれがバイト・カウントを保持する）２つの追加フィールド「開始スキップ」および「終了スキップ」で、スパン・レコードを増大する方法である。
【図１９】ＢＬＯＢを格納した場合に、孤立している一致サブブロック（Ｃ）がＢＬＯＢの表示で分割を行う方法である。
【図２０】記憶装置で孤立サブブロック（Ｃ）を２回格納することを選択することにより分割を避ける方法である。
【図２１】２つのキーが、テーブル内の同じ位置にハッシュするハッシュ・テーブル衝突を示す。
【図２２】外部オーバーフロー・リストを含むハッシュ・テーブルである。
【図２３】オーバーフロー・エントリが次の空のスロットに格納されるテーブル内オーバーフローである。
【図２４】それぞれが一定数のエントリ・スロットを含むバケットのアレイとして構成されたハッシュ・テーブルである。
【図２５】全キーの余分なビットを使用してハッシュ・テーブルのサイズを２倍にする方法である。
【図２６】３つの分岐を含むスパンのツリーである。スパンをツリーに編成することにより、ＢＬＯＢ内のランダム・アクセスが高速になる。図面の番号は、各子ノードが表すブロックの長さである。
【図２７】元のＢＬＯＢ内で隣接しているサブブロックの一続きの部分を識別するためのクラスタ内のサブブロックの一連番号の意図的なスキップである。
【図２８】２つのサブブロックＡおよびＢを直接比較しないで、これらのサブブロックＡおよびＢを比較する暗号ハッシュ関数Ｈの使用方法である。代わりに、そのハッシュＨ（Ａ）およびＨ（Ｂ）が比較される。
【図２９】サブブロックＡ、Ｂ、ＣおよびＤを索引し、そのキーが、サブブロック自身ではなく、（ハッシュ関数Ｈを使用する）サブブロックのハッシュであるサブブロック・インデックスである。
【図３０】サブブロックに分割され、低冗長記憶装置に格納されたにも関わらず、ＢＬＯＢがその統合性を保持していることをチェックするための暗号ハッシュ関数Ｈの使用方法である。元のＢＬＯＢのハッシュは、格納しているＢＬＯＢと一緒に格納され、検索したＢＬＯＢのハッシュと比較される。
【図３１】既存のファイル・システム（の頂部上）を使用して低冗長記憶システムが実施される実施形態である。
【図３２】既存のオペレーティング・システムが提供する仮想ブロック装置（の頂部上）を使用して低冗長記憶システムを実施する実施形態である。
【図３３】１つのブロック装置またはファイル・システム内の１つのファイル内に、長さが変化するクラスタを格納する方法である。クラスタ・インデックスは、その番号によりクラスタを迅速に発見するために使用することができる。
【図３４】既存のファイル・システム内のファイルの対応する集合体内へのクラスタの集合体の格納方法である。この例の場合には、ディレクトリ・ツリーは、クラスタ番号上の小数デジタル探索ツリーを形成する。
【図３５】ＢＬＯＢを格納するために必要な構造およびメタデータを生成したが、データ自身を格納していない実施形態である。
【図３６】元のスパン（サブブロックＦＧＨ）と同じデータを指しているが、記憶装置の異なる部分（この場合は、異なるクラスタ）内に位置する別のスパンにより増大したスパン（スパンのリスト内の２番目）である。
【図３７】制約Ｆを使用するサブブロックへのブロックｂの分割、およびハッシュ関数Ｈを使用するサブブロックのハッシュの計算を示す。
【図３８】典型的なコンピュータ・ハードウェア上での低冗長記憶システムの配置方法である。すべてのデータ構造は、ディスク上に常駐している。また、インデックスも、いくつかのＢＬＯＢレコードおよびクラスタの作業コピーを格納しているいくつかのキャッシュと一緒にメモリ内に保持される。
【技術分野】
【０００１】
本発明は、コンピュータ・システムにおいて記憶空間が少なくてすむ形式でデータを格納する方法および装置に関する。
【背景技術】
【０００２】
従来のコンピュータ記憶システムは、通常、ファイル・システム内に名前付きファイルとしてバイトのシーケンスを格納している。多くのファイルは相互に非常に似ている場合があり、データの大部分１３０、１３２を共有している場合がある（図１３）のに、これらのシステムはこの冗長性を除去することができない。それどころか、これらのシステムは、同じデータの多数のコピー１３０、１３２を保持しながら各ファイル１４０、１４２を別々に格納していることもある（図１４）。
【０００３】
従来のファイル・システムの中には、個々のファイルを圧縮するために、（ＧＺｉｐのような）従来の損失を起こさないテキスト圧縮アルゴリズムを組み込んでいるものがあるが、これは「鍵穴」冗長除去技術と見なすことができる。何故なら、この技術は、ファイル・システムを全体として分析するのではなく、ある時点で１つのファイルの冗長性を分析するからである。これらの従来のテキスト圧縮アルゴリズムは、ファイル・システムの異なる部分の２つの類似しているファイル１３０、１３２のような遠く離れているデータ１５０、１５２間の類似性を見つけることができない場合がある（図１５）。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
そこで、データのその反復シーケンスのいくつかを識別し、格納しているこの反復データのコピーの数を低減することができる形式でデータを表示する方法および装置が求められている。
【課題を解決するための手段】
【０００５】
データの反復シーケンスのコピーの数を低減するような方法で、いくつかの異なるバイナリ・ラージ・オブジェクト（ＢＬＯＢ）１０、１２を表示するために、２つ以上のＢＬＯＢ表示により各反復シーケンスを参照することができる表示を使用することができる。図１６は、このことを達成することができる１つの方法を示す。この実施形態の場合には、各ＢＬＯＢ１６０、１６２はサブブロックと呼ばれる部分Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇに分割され、サブブロックの複製１６４、１６６は識別され、１回だけ格納される。このフレームワークにおいては、下記の問題が解決される。すなわち、ＢＬＯＢをサブ分割する方法、結果として得られるサブブロックを格納する方法、およびサブブロックの複製を識別するための方法。
【０００６】
本発明のある態様によれば、格納するデータの各ＢＬＯＢ１０、１２は、分割方法によりサブブロックＡ〜Ｊに分割される（図１）。種々の分割方法を使用することができるが、特に、データを固定長のサブブロック６０〜６５に分割する固定長分割方法を使用することもできるし（図６）、またはデータ自身により定めた位置で（図１）、データを可変長のサブブロックＥ、Ｆ、Ｇ、Ａ、Ｂ、Ｃ、Ｄに分割する可変長分割方法を使用することもできる（図１０）。本発明者と同じ発明者であるＷｉｌｌｉａｍｓの米国特許第５，９９０，８１０号に、この後者の方法の一例が開示されている。この米国特許は、参照により本明細書に組み込まれ、図３７に示す。
【０００７】
サブブロックは、冗長除去の単位になり、ある実施形態の場合には、システムは、せいぜい一度だけ一意の各サブブロックを格納する。他の実施形態の場合には、一意の各サブブロックのコピーの数は低減するが、２以上の場合がある。
【０００８】
例示的実施形態の場合には、ＢＬＯＢのサブブロックは、サブブロック・クラスタ２０、２２、２４と呼ばれるグループ内に格納される（図２）。各ＢＬＯＢは、それぞれが１つのクラスタ２０、２２、２４内のサブブロックの隣接シーケンスを識別するレコード（「スパン・レコード」）３０、３１、３２の順序付きリスト（またはツリー）により表示することができる（図３および図４）。ＢＬＯＢ１０は、スパン３０、３１、３２のリストにより識別されたシーケンスの連結として表示することができ（図３および図４）、各スパンが参照したサブブロック内のサブブロック・コンテンツを検索するスパンのＢＬＯＢのリストを順次チェックすることにより、記憶装置から検索することができる。
【０００９】
例示的実施形態においては、クラスタ２０、２２、２４は、２つ以上のＢＬＯＢ ＸおよびＹからのサブブロックを含むこともできるし（図４）、ＢＬＯＢのサブブロックは、２つ以上のクラスタ内に常駐することもできる（図３）。例示的実施形態において、ＢＬＯＢのサブブロックを１つまたは複数のクラスタ内に順次格納することができる（図２）。これによりＢＬＯＢ検索の効率が改善される。何故なら、ＢＬＯＢ内のサブブロックの全シーケンスを、１回の順次読出動作でディスクから読み出すことができるからである。このことは、各サブブロックを探してランダム・アクセス・ディスク・シークを行うよりも遥かに効率的である。
【００１０】
例示的実施形態においては、同じまたは異なるＢＬＯＢ内の異なるスパンは、同じサブブロックを含む（図４）。これにより冗長性を低減することができる。何故なら、同じサブブロックを含むＢＬＯＢは、（クラスタ内の）同じサブブロックを指すスパンにより表示することができるからである。
【００１１】
本発明のさらに他の態様によれば、各クラスタは、クラスタが使用するスペースの大きさを低減するためにデータ圧縮方法により圧縮される。これを行う最も簡単な方法は、全クラスタを圧縮することである。いくつかの実施形態（特に大きなクラスタを使用する実施形態の場合には）においては、全クラスタ（またはサブブロックを読み出す前のクラスタの少なくとも一部）を圧縮解除しなくても、クラスタ内のサブブロックにアクセスすることができるように、クラスタの各部分（例えば、個々のサブブロックまたはサブブロックの一続きの部分）を圧縮することが望ましい場合がある。
【００１２】
本発明のさらに他の態様によれば、各クラスタ内のサブブロックのディレクトリ７０が各クラスタに対して生成され、（通常は開始のところの）クラスタ内に格納されるか（図７）、または別々に８０、８２（図８）内に格納される。ディレクトリは、例えば、サブブロックの前に各サブブロックのメタデータを格納することにより、クラスタ全体に分配することもできる（図９）。ディレクトリは、そのハッシュ、長さ、サブブロック識別子、およびクラスタ内のその位置のような、各サブブロックに対する種々のメタデータを含むことができる。
【００１３】
本発明のさらに他の態様によれば、２つ以上のＢＬＯＢが共有するサブブロックが識別される。例示的実施形態においては、サブブロックのコンテンツまたはサブブロック・ハッシュ（サブブロックのコンテンツのハッシュ）をクラスタ５２、５４、５６にマッピングする（または関連付ける）サブブロック・インデックス５０が維持される。格納動作中、格納される各サブブロックが、サブブロック・インデックス内で参照される。存在する場合には、サブブロックは再度格納されない。サブブロックが存在しない場合には、サブブロックはクラスタ内に格納され、それに対するエントリがサブブロック・インデックスに追加される。いずれの場合も、新しいサブブロックがスパン５８により参照される。
【００１４】
本発明のある態様によれば、特定のサブブロックが記憶装置内にすでに存在していることをインデックスが示す場合には、一致するサブブロックのクラスタがアクセスされ、クラスタ内の一致するサブブロックの後のサブブロックが、格納するＢＬＯＢ内の一致するサブブロックの後のサブブロックと比較される（図１０）。この比較はインデックスにアクセスしないで行うことができ、実際には、サブブロックを含んでいるクラスタが、サブブロック・ハッシュを含むサブブロック・ディレクトリを有している限り、実際のサブブロック・コンテンツ・データにアクセスしないで行うことができる。
用語
欠落サブブロック：記憶装置内に存在していないサブブロック
ＢＬＯＢ（バイナリ・ラージ・オブジェクト）：データのゼロまたはそれ以上のバイト（またはビット）の有限シーケンス。その名前にも関わらず、ＢＬＯＢは必ずしも大きくはない。ＢＬＯＢは、数ビットまたはバイトのように小さいものであってもよいし、またはギガバイトのように大きいものであってもよい。
【００１５】
ＢＬＯＢレコード：特定のＢＬＯＢについての情報を記録している記憶装置内に維持されているレコード。また、ＢＬＯＢレコードは、ＢＬＯＢコンテンツを定義するスパンのリスト（またはツリー）を含むこともできるし、または参照することもできる。
【００１６】
ＢＬＯＢテーブル：ＢＬＯＢ識別子（例えば、制限なしに、ＢＬＯＢハッシュ）をＢＬＯＢレコードに関連付けるデータ構造
クラスタ：「サブブロック・クラスタ」の短縮語。関連するサブブロックのグループ。クラスタは、クラスタ内のサブブロックについての情報を提供する関連サブブロック・ディレクトリを有することができる。
【００１７】
クラスタ・サブブロック・ディレクトリ：クラスタ内のサブブロックについての情報を提供するメタデータの集合体。サブブロックのメタデータは、サブブロックの長さ、ハッシュ、識別子および基準カウントを含むことができる（しかし、含むことができるものはこれらに限定されない）。
【００１８】
隣接する：物事の順序付きグループ内の２つの物事が隣り合っている場合には、隣接するという。Ｎの物事が正確にＮ−１の隣り合った１対の物事を含んでいる場合には（すなわち、Ｎの物事が１つの連続している一続きの部分として表される場合には）、物事の順序付きグループ内のＮという物事は隣接している。
【００１９】
隣接サブブロック：隣り合っている場合には、あるコンテキスト（例えば、ＢＬＯＢまたはクラスタ）において、２つのサブブロックは隣接している。Ｎという物事が正確にＮ−１の隣り合った１対のサブブロックを含んでいる場合には（すなわち、サブブロックが１つの連続している一続きの部分となっている場合には）、あるコンテキストにおいてＮのサブブロックは隣接している。
【００２０】
ディレクトリ：クラスタ・サブブロック・ディレクトリ参照
ディスク：コンピュータが使用するランダム・アクセス記憶媒体。通常、ディスクという用語は、磁化したデータを保持している金属の回転円盤（ハードディスク）を意味する。本明細書においては、ディスクという用語は、メモリよりかなり遅いランダム・アクセス記憶媒体を意味するようにもっと広義に解釈することができる。
【００２１】
固定長分割方法：データを固定長サブブロックに分割するデータを分割するための方法。例えば、固定長分割方法は、ＢＬＯＢを５１２バイトのサブブロックに分割することができる。
【００２２】
ハッシュ：ハッシュ・アルゴリズムが生成したバイト（またはビット）の固定長シーケンス。サブブロックのハッシュは、サブブロックを索引し、比較するためのサブブロックを表すものとして使用することができる。
【００２３】
ハッシュ・アルゴリズム：バイト（またはビット）の有限シーケンスを受け入れ、入力シーケンスに高度に依存するバイト（またはビット）の有限シーケンスを生成するアルゴリズム。通常、ハッシュ・アルゴリズムは、特定の固定長の出力を生成する。ハッシュ・アルゴリズムは、シーケンスを直接比較しなくても、データの２つのシーケンスが同じであるか否かをチェックするための試験に使用することができる。実際に暗号化ハッシュを使用すれば、そのハッシュが同じである場合、２つのサブブロックが同じであると結論することができる。ハッシュ・アルゴリズムは、ＢＬＯＢ識別子を生成し、サブブロックを比較し、ハッシュ・テーブル・キーを生成するために、例示的実施形態において使用することができる。
【００２４】
サブブロックのハッシュ：サブブロック・ハッシュ参照
インデックス：サブブロック・インデックス参照
インデックス・バケット：ハッシュ・テーブルを使用してサブブロック・インデックスを実施する実施形態の場合には、ハッシュ・テーブルを、それぞれが空であるかエントリを含み、それぞれが一定数のエントリ・スロットを含むバケットのアレイとして構成することができる。インデックス・バケットの１つの目的は、ハッシュ・テーブルを、ランダム・アクセス・ディスク動作の回数を低減するために、グループとしてディスクから読み出し、ディスクに書き込むことができる部分に構成することである。
インデックス・エントリ：サブブロック・インデックス内のレコード。ある実施形態の場合には、インデックス・レコードは、インデックス・キーおよびインデックス値を含む。ある実施形態の場合には、インデックス・レコードは、インデックス・キーの一部およびインデックス値を含む。ある実施形態の場合には、インデックス・レコードはインデックス値だけを含む。ある実施形態の場合には、インデックス・レコードは値を含まないで、キーの一部または全部を含む。
【００２５】
インデックス・キー：サブブロックについての情報を検索するために、サブブロック・インデックスに提供されるサブブロックについての情報。ある実施形態の場合には、この情報はインデックス・エントリの位置を発見し、読み出すことにより検索される。
【００２６】
インデックス値：サブブロック（またはその一例がそのハッシュであるサブブロックの派生物）をインデックスで参照した場合に、インデックスによりサブブロックについて生成された情報。ある実施形態の場合には、この値は、ディスク上のサブブロックの位置からなる。他の実施形態の場合には、インデックスの唯一の目的がキーの有無を記録することである場合には、値が存在しない場合がある。ある実施形態の場合には、この値は単にクラスタ数からなる。
【００２７】
サブブロックの長さ：サブブロック・コンテンツ内のバイト（またはビット）数
線形探索：１つずつ集合体内のオブジェクトをチェックすることによる、およびチェックする次のオブジェクトの選択が前のチェックの結果により影響を受けない場合の、オブジェクトの集合体内の１つのオブジェクトに対する探索方法。
スパンのリスト：スパンの順序付きリスト。このようなリストは、ＢＬＯＢのコンテンツを表示するために使用することができる。
【００２８】
一致する一続きの部分：（例えば、格納しているＢＬＯＢ内に存在してもよい）サブブロックの他のシーケンスと一致する（クラスタ内の）サブブロックのシーケンス。ある実施形態の場合には、サブブロックのシーケンスは隣接している。
【００２９】
メモリ：通常、ランダム・アクセス・メモリ（ＲＡＭ）を参照するコンピュータが使用するランダム・アクセス記憶媒体。本明細書においては、この用語は、「ディスク」よりかなり速いランダム・アクセス記憶媒体を意味するようにもっと広義に解釈することができる。
【００３０】
分割方法：ＢＬＯＢ内の各バイト（またはビット）が、正確に１つのサブブロック内に入るように、ＢＬＯＢを１つまたは複数のサブブロックに分割するための方法。
【００３１】
存在サブブロック：記憶装置内に存在するサブブロック。
【００３２】
低冗長：バイト（またはビット）の同一シーケンスのコピー数の任意のタイプのデータ表示での低減である。
【００３３】
低冗長記憶装置：データのその表示の際に、自身が格納している一組のデータ内の複製データのいくつかを除去する記憶システム。
【００３４】
サブブロックへの参照：サブブロックを識別する１つのデータ。例えば、制限なしで、参照は、コンテンツまたは格納位置によりサブブロックを識別することができる。
【００３５】
基準計数：あるエンティティがもはや必要なくなった時を判定するための方法。この方法は、エンティティに対して存在する参照の数を記録するカウンタを維持するステップを含む。基準カウントがゼロになった場合には、エンティティを削除することができる。ある実施形態の場合には、ＢＬＯＢおよび／またはサブブロックは基準カウントを有する。
【００３６】
スパン：クラスタ内のサブブロックのシーケンス。ある実施形態の場合には、このシーケンスは隣接している。
【００３７】
スパン・レコード：クラスタ内のスパンを識別するレコード。ある実施形態の場合には、スパン・レコードは、クラスタ番号フィールド、開始サブブロック識別子フィールド、および（サブブロックまたはバイトの）スパン長フィールドを含む。
【００３８】
記憶装置：低冗長記憶装置参照。
【００３９】
サブブロック：索引、比較および／または冗長除去のための単位として識別されたバイト（またはビット）のシーケンス。ＢＬＯＢはサブブロックに分割することができる。
【００４０】
サブブロック・クラスタ：一緒に格納している１つまたは複数のサブブロックのグループ。「クラスタ」とも呼ばれる。
【００４１】
サブブロック・コンテンツ：サブブロックのメタデータとは異なるサブブロックの実際のデータ。
【００４２】
サブブロック・ディレクトリ：クラスタ・サブブロック・ディレクトリ参照。
【００４３】
サブブロック満了日：サブブロックをユーザが必要としないことを保証された場合に、最も初期の日付を定義するサブブロックと関連する１つのメタデータ。
【００４４】
サブブロック・ハッシュ：サブブロックへのハッシュ・アルゴリズムの適用結果。サブブロックのハッシュは、例えば、サブブロックを索引および／または比較するために、サブブロックを表すものとして使用することができる。
【００４５】
サブブロック識別子：サブブロックに関連する１つのメタデータ。識別子はクラスタ内のサブブロックに対して一意のものであり、それ故、そのクラスタ内のサブブロックを一義的に識別するために使用することができる。ある実施形態の場合には、異なるクラスタ内のサブブロックは、同じ識別子を有することができる。
【００４６】
サブブロック・インデックス：サブブロックの位置（例えば、制限なしで、クラスタ番号（およびまた、おそらくサブブロック識別子））に、サブブロックのハッシュ（またはサブブロック自身）をマッピングする（または他の方法で関連付ける）データ構造。
【００４７】
サブブロック・メタデータ：サブブロックについての情報。サブブロックのメタデータは、（制限なしに）サブブロックの長さ、サブブロックのハッシュ、サブブロックの識別子、サブブロックの満期日付、およびサブブロックの基準カウントを含むことができる。
【００４８】
サブブロック・レコード：１つのサブブロックに対するメタデータを含むクラスタ・サブブロック・ディレクトリ内のレコード。
【００４９】
サブブロック基準カウント：サブブロックに対する参照の現在数を記録する１つのサブブロック・メタデータ。ある実施形態の場合には、これはサブブロックを含むスパンを定義するスパン・レコードの数である。
【００５０】
サブブロック一連番号：サブブロック識別子の形式。例えば、一連番号システムを使用するある実施形態の場合には、特定のクラスタに到着するサブブロックには、第１のサブブロックに対して１から始まり増大する一連番号が割り当てられる。ある実施形態の場合には、サブブロックを削除した場合には、一連番号は再使用されない。これらの実施形態の場合には、一連番号は、クラスタ内のサブブロックを一意に識別する方法を提供する。
【００５１】
ユーザ：記憶装置内にＢＬＯＢを格納し、検索する１つのソフトウェア。
【００５２】
可変長分割方法：ＢＬＯＢを可変長サブブロックに分割する分割方法。好ましい実施形態の場合には、可変長分割方法は、データをデータのコンテンツが決定する境界のところで分割する。例えば、制限なしに、分割方法は、前のいくつかのバイトが、特定の所定の一定値にハッシュするＢＬＯＢ内の各位置のところのサブブロック境界を定義することができる。
【００５３】
仮想ブロック装置：オペレーティング・システムが提供する固定長記憶ブロックのアレイからなる装置。仮想装置は、物理デバイスに直接対応することができ、または（例えば、ＲＡＩＤを使用して）１つまたは複数の物理デバイスから構成することができる。
【００５４】
全キー：小さな派生キーの元として使用されるキー。データ構造が成長し、派生キーが必要になるので、全キーの増大する部分を、派生キーを形成するのに使用することができる。
【００５５】
本明細書全体および添付の特許請求の範囲を通して、別段の指示がない限り、「備える」および「含む」という用語、および「備えている」および「含んでいる」という派生語は、「包含」および「除外しないこと」を意味する用語であると理解されたい。例えば、このような用語を記載の整数または整数のグループを参照するために使用した場合には、このような用語は、任意の他の整数または整数のグループの除外を意味しない。
【００５６】
本明細書の添付の特許請求の範囲は、本明細書に記載する本発明の広義の記述であり、参照により本明細書に組み込まれる。
【００５７】
本明細書での任意の従来技術への参照は、このような従来技術が共通の一般的知識の一部を形成しているという容認でもなければ、任意の形式の示唆でもないし、またそのように解釈すべきでもない。
【００５８】
添付の図面を参照しながら、以下に本発明の特定の実施形態についてさらに詳細に説明する。これらの実施形態は、説明のためのものであって、本発明の範囲を制限するためのものではない。他の実施形態の示唆および記述を本発明の範囲内に含めることができるが、これらのものは添付の図面には示していないし、または別の方法で本発明の機能を図面には示してあるが本明細書には記述していない。
【発明を実施するための最良の形態】
【００５９】
図５は、本発明の典型的な実施形態の要素の概観である。この実施形態は、ＢＬＯＢレコード５１、５３と、スパン・リスト５８と、クラスタ５２、５４、５６と、サブブロック・インデックス５０とを含む。図３８は、典型的なコンピュータ・ハードウェア上でのこれらの要素の配置を示す。すべてのデータ構造はディスク３８０上に常駐している。インデックス３８１も、いくつかのＢＬＯＢレコード３８２およびクラスタ３８３のいくつかの作業コピーを格納しているいくつかのキャッシュと一緒にメモリ内に保持されている。
６．１ ハッシュ関数の概観
すべての実施形態においてはハッシュ関数を使用していないが、ハッシュ関数は、多くの実施形態でいくつかの利点を提供する。下記の説明は、本発明の種々の実施形態に関連して使用することができる例示としてのハッシュ関数の概観である。
【００６０】
ハッシュ関数は、ビットの可変長入力ブロックを受け入れ、入力ブロックをベースとするビットの出力ブロックを生成する。大部分のハッシュ関数は、出力ブロックが特定の長さ（例えば、１６ビット）になることを保証し、入力ブロックの無限集合と出力ブロックの有限集合との間でランダムではあるが、決定論的マッピングを提供するようにする。ランダムさの特性により、「ハッシュ」と呼ばれるこれらの出力を、入力ブロックの容易に操作した表示として動作させることができる。
【００６１】
ハッシュ関数は少なくとも４つのクラスの強度を有する。
【００６２】
狭いハッシュ関数：狭いハッシュ関数は、最も弱いクラスのハッシュ関数であり、出力値の全スペースを妥当な時間内に探索することができるような、非常に狭い（例えば、１６ビット）出力値を生成する。例えば、８ビットのハッシュ関数は、任意のデータ・ブロックを０〜２５５の範囲内のハッシュにマッピングする。１６ビットのハッシュ関数は、０〜６５５３５の範囲内のハッシュにマッピングする。特定のハッシュ値の場合には、単に探索する値が表れるまで、ランダム・ブロックを生成し、これらのブロックを狭いハッシュ関数に提供することにより、対応するブロックを発見することができる。狭いハッシュ関数は、一組のデータ値を少数のグループに任意に（しかし決定論的に）分類するために、通常、使用される。それ故、狭いハッシュ関数は、ハッシュ・テーブル・データ構造を構成し、ノイズの多い通信チャネルを通して送信したデータのエラーを検出するのに役に立つ。このクラスの例としては、ＣＲＣ−１６、ＣＲＣ−３２、フレッチャ・チェックサム、ＩＰチェックサム等がある。
【００６３】
広いハッシュ関数：広いハッシュ関数は、その出力値がかなり広いということを除けば、狭いハッシュ関数に類似している。ある点においては、この定量的違いは、定性的違いを意味する。広いハッシュ関数の場合には、出力値が非常に広い（例えば、１２８ビット）ので、同じハッシュ値を有する任意の２つのランダムに選択したブロックの確率は無視することができる（例えば、１０３８のうちの約１）。この特性により、これらの広いハッシュを、これらが計算されたデータのブロックの「ＩＤ（ｉｄｅｎｔｉｔｙ）」として使用することができる。例えば、エンティティＥ１がデータのブロックを有し、エンティティＥ２にブロックの広いハッシュを送った場合で、エンティティＥ２が同じハッシュを有するブロックを有している場合には、ブロックが実際に異なる先験的確率は無視することができる。唯一の問題は、広いハッシュ関数が非反転できるように設計されていないことである。それ故、（例えば）２１２８値のスペースは、狭いハッシュ関数のところで説明した方法で探索するにはあまりに広すぎるが、ハッシュ関数を分析し、特定のハッシュに対応するブロックを計算するのは容易である。それ故、Ｅ１が本当に異なるブロックである場合には、Ｅ１は、Ｅ２がＥ１が１つのブロックを有すると思い込ませることができる。このクラスの例としては、任意の１２８ビットのＣＲＣアルゴリズムがある。
【００６４】
弱一方向ハッシュ関数：弱一方向ハッシュ関数は、「ＩＤ」を提供するのに十分広いばかりでなく、特定のハッシュ値が与えられた場合、そのハッシュ値に対応するブロックを発見するのが極度に難しい暗号保証を提供する。このクラスの例としては、６４ビットＤＥＳハッシュがある。
【００６５】
強一方向ハッシュ関数：強一方向ハッシュ関数は、同じハッシュ値を有する任意の２つの異なるブロックを発見するのが難しい暗号保証を提供する追加特性を有することを除けば、弱一方向ハッシュ関数と同じものである。この場合、ハッシュ値は指定されない。このクラスの例としては、ＭＤ５およびＳＨＡ−１がある。
【００６６】
これら４つのクラスのハッシュは、選択が行われるある範囲のハッシュ強度を提供する。予想されるように、ハッシュ関数の速度は、強度が増大するにつれて低減し、トレードオフを提供し、異なる用途の場合には異なる強度が適切な強度になる。しかし、違いは非常に小さいので、最もタイムクリティカルな用途以外では、強一方向ハッシュ関数を使用することができる。
【００６７】
暗号ハッシュという用語は、多くの場合、弱一方向ハッシュ関数のクラスおよび強一方向ハッシュ関数のクラス両方を含む暗号強度を提供するハッシュを指すために使用される。
【００６８】
本発明の例示的実施形態は、少なくとも２つの役割でハッシュ関数を使用することができる。
【００６９】
１．サブブロック境界を決定するために。
【００７０】
２．サブブロックＩＤを生成するために。
【００７１】
用途に従って、上記４つのクラスのうちの任意のクラスからのハッシュ関数をいずれかの役割で使用することができる。しかし、サブブロック境界の決定にはＩＤおよび暗号強度が必要ないので、最も弱いクラス以外からのクラスからのハッシュ関数を使用するのは非効率である。同様に、ＩＤの必要性、絶えず存在する破壊行為の脅威、および強一方向ハッシュ関数（弱一方向ハッシュ関数と比較した場合）に対する低性能というペナルティは、強一方向ハッシュ関数より弱いいかなるものもサブブロックＩＤの計算に使用すべきではないことを示唆している。
【００７２】
ＩＤを生成するために強一方向ハッシュ関数以下の何かを使用する際につきもののセキュリティの危険は、任意のこのような弱ハッシュ関数を使用する本発明を組み込む記憶システムを考慮することにより説明することができる。このようなシステムにおいては、侵入者は、修正したサブブロックが、ターゲット・システム内にすでに存在することを侵入者が知っている他のサブブロックと同じハッシュを有するように、（ターゲット・システムにより操作される）サブブロックを修正することができる。そうすると、ターゲット・システムがそれを新しいものと置き換えないで、既存のサブブロックを保持する結果になる恐れがある。（例えば）ターゲット・システムがネットワーク上で検索したセキュリティ・パッチを正しく適用するのを防止するために、このような弱点を使用することができる。
【００７３】
それ故、敵意を持つ人間に曝されないシステムでサブブロックを計算するのに、広いハッシュ関数を安全に使用することができるが、弱一方向ハッシュ関数が、これらのシステムでは非セキュアとなる恐れがある。
【００７４】
ここで、ブロックまたはサブブロックのハッシュを実際に使用することができる方法について説明する。
６．２ 暗号ハッシュの使用
暗号ハッシュ（およびここでは強一方向ハッシュ関数）の理論特性は、特に興味のある実際の特性を生成する。このようなハッシュはかなり広いので、２つのランダムに選択したサブブロックが、同じハッシュを有する確率は事実上ゼロであり（１２８ビット・ハッシュの場合には、１０３８のうちの約１であり）、同じハッシュを有する２つのサブブロックを発見するのは計算上不可能であるので、スパイがそのようなことを行うことができないことを事実上保証している。これらの特性の密接な関係は、実際の見地から見ると、特定の暗号ハッシュ・アルゴリズムに対するハッシュ値の有限集合は、有限の可変長サブブロックの無限集合に対して１対１の関係になる。これは、同じ値にハッシュする２つのサブブロックを発見するのは実際上不可能であるので、実際には、理論上不可能な特性であることは明らかである。
【００７５】
この特性は、（同一であることのために）比較の目的で、計算されたサブブロックの代わりに、暗号ハッシュを安全に使用することができることを意味する。大部分の暗号ハッシュは約１２８ビットの長さしかないので、ハッシュは、サブブロック自身のコンテンツを直接比較しなくても、サブブロックを比較するための非常に効率的な方法を提供する。
【００７６】
本発明の例示的実施形態で暗号ハッシュが使用されるいくつかの方法は下記の通りである。
【００７７】
サブブロックの比較：暗号ハッシュＨは、２つのサブブロックＡ、Ｂのコンテンツを比較しなくても、またはアクセスしなくても、２つのサブブロックＡ、Ｂを比較２８０するために使用することができる（図２８）。
【００７８】
サブブロックのインデックス：サブブロックＡ、Ｂ、Ｃ、Ｄの集合体を索引するために、そのキーがサブブロック２９２、２９４、２９６、２９８のハッシュであるインデックス２９０を構成することができる（図２９）。
ＢＬＯＢチェック：ＢＬＯＢ３００のサブブロック３０２への分割、および再構成したＢＬＯＢ３０４へのサブブロックの以降の再組立を確実にエラーのないものにするために、暗号ハッシュを使用することができる。このことは、元のＢＬＯＢのハッシュ３０６を再構成したＢＬＯＢのハッシュ３０８と比較３０９することにより行うことができる（図３０）。
６．３ 安全ネットとしてのハッシュの使用
本発明の実施形態は、これらの実施形態を組み込む記憶システムをさらに複雑にする場合がある。このように複雑になると、潜在的にエラーが検出されない機会が多くなる。
【００７９】
複雑さの主な機構は、ＢＬＯＢのサブブロックへの分割であり、このようなサブブロックの以降の再組立である。ＢＬＯＢをサブブロックに分割することにより、記憶システムが、サブブロックを間違って追加したり、削除したり、再配置したり、置換したり、複製したり、または何らかの他の方法で偶然のエラーのより大きなリスクに曝されたりする恐れがでてくる。
【００８０】
このリスクは、サブブロックに分割される前にＢＬＯＢのハッシュ（好適には暗号ハッシュであることが好ましい）を計算し、このハッシュを全体としてＢＬＯＢに関連するエンティティと一緒に格納し、次に、格納しているハッシュを、再構成したブロックの計算したハッシュと比較することにより、低減または除去することができる。このようなチェックは、本発明を使用することによるエラーが検出されないリスクを事実上取り除く非常に強力な安全ネットを提供する（図３０）。
【００８１】
ＢＬＯＢをチェックするもう１つの方法は、そのサブブロックのハッシュの連結をハッシュし、記憶装置からＢＬＯＢを検索した場合の値をチェックする方法である。この方法は、全体的に見てハッシュしなければならないデータが少なくてすみ、このような実施形態をより効率的にすることができるという利点を有する。
６．４ クラスタ内へのサブブロックの格納
クラスタ内にサブブロックを格納することができる方法は多数ある。「サブブロックのコンテンツ」という用語は、実際のサブブロックを形成するバイトのシーケンスを意味する。例示的実施形態においては、クラスタ７４内のサブブロック７２は、メタデータの介入なしで背中合わせに格納される（図７）。クラスタがそれ自身のディレクトリを持たない実施形態の場合には、背中合わせのサブブロック・コンテンツは、クラスタが含んでいなければならないすべてのものであってもよい。
【００８２】
背中合わせにサブブロックを格納する利点は、サブブロックの隣接する一続きの部分を１つのシーケンシャルな動作としてクラスタから読み出すことができることであり、次に、最初に、メタデータを除去しなくても、メモリ内に保持し、１つのシーケンシャルな動作として書き出すことができることである。
【００８３】
サブブロックをクラスタに分割する方法を決定するために多数の方法を使用することができる。１つの方法は、少なくともＳ個のサブブロックを有するまでクラスタにサブブロックを書き込む方法である。ここで、Ｓは所定の定数である。もう１つの方法は、少なくともＭメガバイトを含むまで、クラスタにサブブロックを書き込む方法である。ここで、Ｍは所定の定数である。
６．５ クラスタ・サブブロック・ディレクトリ
クラスタは、クラスタ内のサブブロックについての情報を提供し、クラスタ内のサブブロックの位置を迅速に発見することができるサブブロック・ディレクトリを有することができる。
【００８４】
クラスタは、ディレクトリ７０を有している場合には、ディレクトリをクラスタの始めの部分（図７）またはクラスタの終わりの部分に置くことができる。もう１つの例は、サブブロック・コンテンツ９２とディレクトリ９０エントリをインタリーブする例である（図９）。最後に、ディレクトリ８０、８２は別々に格納することができる（図８）。
【００８５】
１つの簡単なオプションは、クラスタ内のサブブロック数上に上部限界Ｌを置き、クラスタ内のサブブロック数が何であれ、カウントにＬディレクトリ・エントリのアレイを加えたものとしてディレクトリを表す方法である。これにより固定長ディレクトリ８０、８２が出来上がり、クラスタのディレクトリを、残りのクラスタのコンテンツ８４、８６（すなわち、サブブロックのコンテンツ）とは別々に１つのアレイを格納することができる（図８）。
６．６ クラスタ・サブブロック・ディレクトリ内のサブブロック・メタデータ
クラスタのサブブロック・ディレクトリは、各サブブロックの長さを格納することができる。通常、各サブブロックの長さの単位はバイトである。サブブロックの長さを格納した場合には、クラスタのサブブロックのコンテンツを、境界がサブブロック間にあることを決定するために、分割方法を呼び出さなくても、サブブロックに分割することができる。
【００８６】
クラスタのディレクトリは、各サブブロックのハッシュを格納することができる。例えば、ディレクトリは、クラスタ内の各サブブロックの１２８ビットのＭＤ５または１６０ビットのＳＨＡ−１を格納することができる。各サブブロックのハッシュを格納することは役に立つ。何故なら、格納中、システムが、サブブロックＸのコンテンツをサブブロックＹのコンテンツと比較しなくても、新しく到着したサブブロックＹがクラスタ内で発見されたことを確認することができるからである。代わりに、システムは、サブブロックＹのハッシュを計算し、それを（そのクラスタのディレクトリ内で発見することができる）サブブロックＸのハッシュと比較する。それ故、格納しているＢＬＯＢ内のサブブロックを、記憶装置内のサブブロックのコンテンツを読み出さなくても、インデックスおよびクラスタ・ディレクトリだけを使用して、記憶装置内に存在しているか否かを試験することができる。
【００８７】
また、クラスタのディレクトリは、各サブブロックに対するサブブロック識別子を格納することもできる。サブブロックの識別子は、クラスタ内の一組のサブブロック内で一意のものである。サブブロック識別子を実施する１つの簡単な方法は、固定幅（例えば、１６ビット）を選択し、各クラスタ内の一連番号カウンタを割り当て、ゼロから開始し、次の整数を各サブブロックにその一連番号識別子として割り当てる方法である。カウンタが最大値に達した場合には、クラスタを新データに対して単に閉鎖することができる。別の方法としては、サブブロックをクラスタから削除した場合には、未使用の識別子を再度割り当てることができる。これはサブブロック識別子を実施する多くの方法のうちの１つの方法である。
【００８８】
一連番号をサブブロック識別子として使用した場合には、その連続性をＢＬＯＢ内のサブブロックの１つの一続きの部分から格納したクラスタ内のサブブロック２７６〜２７８の一続きの部分の始まりおよび終わりを示すために使用することができる。ある実施形態の場合には、このことは各格納している一続きの部分２７２、２７４の終わりのところの一連番号をスキップ（廃棄）することにより行うことができる（図２７）。一連番号を使用しない場合には、クラスタ内のサブブロックの一続きの部分の（元のＢＬＯＢ内のサブブロックの一続きの部分に対する）終わりを示すために、各サブブロックのメタデータに、ブール値を追加することができる。
６．７ クラスタの圧縮
システム内に圧縮（例えば、制限なしに、ＧＺｉＰ）を組み込むことができる方法は多数ある。１つの簡単な方法は、ディスクに書き込む前に、各クラスタに対して１つのシーケンシャルな動作として圧縮を行う方法である。もう１つの方法は、各サブブロックを個々に圧縮する方法である。もう１つの方法は、隣接する一連番号と一緒にサブブロックの各一続きの部分を圧縮する方法である。
【００８９】
クラスタは、圧縮した形式でディスク上に格納することができる。また、これらのクラスタは、圧縮した形式でメモリに格納することもできる。
６．８ スパン・サブブロック−一続きの部分の識別
各スパンは、特定のクラスタ内のサブブロックの一続きの部分を識別する。例示的実施形態の場合には、スパンは、サブブロックの一続きの部分を含むクラスタを識別する情報を含む。サブブロックの一続きの部分を識別するための広い範囲の可能性がある。そのため、一続きの部分内の最初および最後のサブブロックを識別することができ、または最初（または最後）のサブブロックを識別することができ、長さを提供することができる。長さはバイト単位またはサブブロック単位で測定することができる。
【００９０】
例示的実施形態のサブブロックを識別するために、スパンは、サブブロックのハッシュ（この場合、クラスタは（サブブロックのディレクトリを使用して（１つ有している場合））サブブロックを探索しなければならないが）、クラスタ（例えば、「第３のサブブロック」）内のサブブロックの位置、またはサブブロック識別子を使用することができる。
【００９１】
ハッシュの幅は比較的広い。クラスタ内に（例えば）１０００のサブブロックが存在する場合には、サブブロック識別子は、約１０ビットの幅を有していればよいのだが、典型的なハッシュは１２８ビットの幅を有する。そのクラスタ内の（サブブロック単位で測定した）位置を使用すると、スペースをもっと効率的に使用することができるが、（サブブロックを含んでいるＢＬＯＢを記憶装置から削除した場合に起こるかもしれないように）サブブロックをクラスタから削除した場合、故障が起こる。これを避けるために、例示的実施形態の場合には、（クラスタ内で一意の）クラスタ内の各サブブロックに一意の識別子を割り当てることができる。この識別子は、クラスタのディレクトリ内に各サブブロックのメタデータと一緒に格納することができる。このような識別子は、（ビット単位で）十分狭いものであってもよいが、サブブロックがクラスタ内でシフトしても、サブブロックをはっきりと識別する。
【００９２】
もう１つのアプローチは、そのハッシュでサブブロックを参照する方法であるが、同じクラスタ内で他のすべてのサブブロックからそのサブブロックを区別するために必要なものである。スパン・レコード内の短い固定長フィールドは、記録するハッシュのバイト数を記録するために使用することができる。この方法を使用すれば、サブブロック識別子を使用する必要がなくなるし、スパン・レコードに長いハッシュによる負担がかからなくなる。この方法を使用すれば、スパン・レコードは可変長を有することができる。この方法の１つの潜在的な問題は、クラスタに追加されるサブブロックが、既存の参照を曖昧にする恐れがあることである。この問題は、このような曖昧な参照がいつでも曖昧な参照を満たす第１のサブブロックを参照するように注意することにより解決することができる。
【００９３】
もう１つの方法は、サブブロックの一連番号を使用するが、これらの一連番号をスパンにより直接参照されるサブブロックだけに割り当てる方法である。実際には、スパンの第１のサブブロックは非常に少ないので、遥かに少ない数の一連番号を格納するだけですむ。
６．９ 部分サブブロックの一致
ＢＬＯＢ１７０の格納中、１つまたは複数の一致するサブブロックＢ、Ｃの一続きの部分をクラスタ１７４内で発見した場合には、一致しているサブブロックの一続きの部分のどちらかの側面上の一致していないサブブロックのある部分が、格納しているＢＬＯＢ内の対応するサブブロックの対応部分と一致する可能性がある。図１７は、格納中のＢＬＯＢ１７０および比較しているクラスタ１７４を示す。インデックスを使用して、サブブロックＢＣの一致する一続きの部分を発見した。各側面上のサブブロックは一致しない。ＡはＥと一致しないし、ＤはＦと一致しない。それ故、一致する一続きの部分はちょうど２つのサブブロックの長さである。しかし、ＢＣの一致を発見した場合、周囲のサブブロックをもっと精密なレベルで比較することができる。
【００９４】
サブブロックＡの終わりとサブブロックＥの終わりと比較すれば、これらのサブブロックが、同じ（例えば）１２３バイトの接尾部を共有していることが分かる。同様に、サブブロックＤの始まりをサブブロックＦの始まりと比較すると、これらのサブブロックが、同じ（例えば）１０４５バイトの接頭部を共有していることが分かる。これらを部分サブブロックの一致と呼ぶ。
【００９５】
部分サブブロックの一致を発見した場合には、多数の方法を使用することができる。図１８は、スパン内の最初のサブブロックの始まりのところ、およびスパン内の最後のサブブロックの終わりのところで無視すべきバイト数を記録する余分なフィールド「開始スキップ」１８０および「終了スキップ」１８２を含むように、スパン・レコード構造を増大することができる方法を示す。もう１つの方法は、サブブロックのどちらかの終わりを延長するために、バイト数を記録する２つのフィールド「開始エクステンド」および「終了エクステンド」を使用する方法である。ある実施形態は、上記各フィールドの一方または両方の使用を選択することができる。
【００９６】
サブブロックの一続きの部分内のバイトのある範囲を参照するもう１つの方法は、「終了スキップ」フィールドを、スパン内のバイトの全数である長さで置換する方法である。
６．１０ フラグメンテーションの低減
格納しているＢＬＯＢがすでに格納済みの多くのサブブロックを含んでいるが、多くの異なるクラスタ全体に散乱している場合には、ＢＬＯＢは、ディスク全体を指すスパンのリストの表示で終わる。要するに多数に分割される。
【００９７】
一致しないサブブロックの長い一続きの部分内の１つのサブブロックが一致する場合には、ある特に不都合な形のフラグメンテーションが起こる。図１９は、ＢＬＯＢ１ １９０が記憶装置内にすでに格納されていて、ＢＬＯＢ２ １９２を格納中であり、１つの一致するサブブロックＣが、ＢＬＯＢ２内のサブブロックＦ〜Ｍの他の方法で一致しない一続きの部分内に位置するこの一例を示す。結果としては、一致するサブブロックに対する１つのスパン・レコード１９４がスパン・リスト１９６内に生成される。このタイプのフラグメンテーションは、ＢＬＯＢ２の検索時間を長くする傾向がある。何故なら、ランダム・ディスク・アクセスを、第１のクラスタ１９８および第２のクラスタ１９９に対して行わなければならないからである。
【００９８】
ある種の実施形態は、孤立している一致サブブロックを一致していないとして処理し、これらのサブブロックを次に格納することにより、このタイプの１つの一致サブブロック・フラグメンテーションを避けることができる。図２０は、余分のスペースを使用するが、ＢＬＯＢ２ ２０２のフラグメンテーションを低減することにより、サブブロックＣの孤立している一致を格納させるのを無視する方法を示す。この方法は、一致するサブブロックの予め定義したしきい値Ｔより短いすべての一致する一続きの部分を無視することにより一般化することができる。ある実施形態の場合には、１より大きいＴの任意の値はフラグメンテーションを低減する傾向がある。値２も役に立つ。
６．１１ ＢＬＯＢテーブル
ＢＬＯＢを格納する記憶システムは、そのユーザがＢＬＯＢを検索することができるように、ＢＬＯＢを参照することができるようにするある方法を提供するものでなければならない。
【００９９】
１つの方法は、ＢＬＯＢのハッシュ１１０を識別子として使用する方法である（図１１）。それ故、ユーザは、ＢＬＯＢを記憶システムに提出し、ＢＬＯＢのハッシュ（例えば、ＭＤ５ハッシュ）を書き留める。ＢＬＯＢを検索するために、ハッシュを記憶システムに提出し、システムはＢＬＯＢを返送する。
【０１００】
もう１つの方法は、任意の名前を各ＢＬＯＢに割り当てる方法である。従来のファイル・システムはこの方法を使用する。
【０１０１】
どんなネーミング・スキームを採用しようとも実施しなければならない。このような実行は、本質的には、ＢＬＯＢ１１２名前空間から（スパンのリスト１１６を含む（または参照する）ＢＬＯＢレコード１１４自身へのマッピングからなる（図１１）。このマッピングは、デジタル探索ツリー、Ｂツリーおよびハッシュ・テーブルのようなすべてのタイプの従来のデータ構造を使用して行うことができる。
６．１２ スパンのリストおよびツリー
ＢＬＯＢテーブル１１２が参照する各ＢＬＯＢレコード１１４は、ＢＬＯＢの任意のメタデータを含み、スパン・レコード１１６の順序付きシーケンスを含んでいるかまたはポイントする（図１１）。各スパン・レコードは、クラスタ内のサブブロックの（隣接する）一続きの部分を識別する。
【０１０２】
スパンの順序付きリスト内にスパンを維持すると、全ＢＬＯＢをシーケンシャルに効率的に検索することができるが、格納しているＢＬＯＢ上でランダム・アクセス読出しを行うために線形探索（またはスパン・レコードをランダムにアクセスできる場合には、二分探索）を必要とする。ランダム・アクセス読出しをスピードアップするために、ＢＬＯＢのスパンをツリー構造に編成することができる。図２６は、３つの分岐を含むツリーの一例である（が、任意の分岐を使用することができる）。各非葉ノードは、その子ノードが表すブロックの連結であるバイトの有限個のブロックを表す。各ノードは、その子ノードが表すブロックの長さである３つの長さを含む。各葉ノードは、クラスタ内の１つまたは複数のサブブロックのシーケンスを識別するスパン２６０からなる。このようなツリーが表す格納しているＢＬＯＢのバイトＪ〜Ｋのランダム・アクセス読出しは、バイトＪ〜Ｋを含むスパンを発見するためにツリーを下方に移動し、次にクラスタからサブブロック・コンテンツ・バイトを検索することにより行うことができる。
６．１３ サブブロック・インデックス
サブブロック・インデックス（図５）を使用すれば、記憶装置内のすべてのクラスタの線形探索を行わなくても、記憶装置内に特定のサブブロックがすでに存在するか否かを判定することができる。また、インデックスは、一致するサブブロックの位置を発見する際に役に立つ情報を提供することができる。
【０１０３】
インデックス５０は、それぞれがインデックス・キーをインデックス値に結合しているエントリの組織した集合体として表示することができる。エントリは、エントリ・レコード（それぞれがキー・フィールドおよび値フィールドからなる）として、インデックス内に明示的に、または（例えば、インデックスが、キー上に葉ノード内に値を含むバイナリ・デジタル探索ツリーとして組織されている場合には）暗黙的に格納することができる。
【０１０４】
インデックス・キーは、サブブロックのコンテンツであっても、サブブロックのコンテンツのハッシュであっても、またはサブブロックのコンテンツのハッシュの単なる一部であってもよい。サブブロックのコンテンツのハッシュの一部（例えば、全１６バイトではなく、ＭＤ５ハッシュの最初の８バイト）だけを格納すると、時に起こる衝突を犠牲にして、インデックスのサイズを小さくすることができる。２つ以上のサブブロックが同じ部分ハッシュを有している場合には、インデックスは、両方のエントリを格納し、検索することができるものでなければならない。
【０１０５】
インデックス値は、記憶装置内のサブブロックの位置を発見する際に役に立つ情報でなければならない。ある極端な実施形態の場合には、この値は、クラスタ番号およびクラスタ内の特定のサブブロック（例えば、識別子、サブブロック一連番号またはサブブロック・ハッシュ）を識別する情報からなる正確な参照を提供することができる。極端な他の実施形態の場合には、インデックス値をクラスタ番号だけから構成することができる。サブブロックのクラスタ番号が分かると、存在する場合には、クラスタ内のサブブロックを発見するためにクラスタ・ディレクトリを探索することができる。インデックス内のスペースをさらに制約するために、インデックス値を、探索するのに２つ以上のクラスタを必要とするクラスタ番号の一部（例えば、クラスタ番号の最後の２つのビット）だけで構成することができる。
【０１０６】
選択の優れた組合わせは、インデックス・キーをサブブロック・ハッシュの頂部の８バイトとし、インデックス値をサブブロックを含むクラスタの数とする方法である。各クラスタに対するディレクトリが存在する限り、これらの選択は、インデックスのサイズを小さいままに維持し、依然として記憶装置の任意のサブブロックに高速でアクセスすることができる。
【０１０７】
インデックスは、デジタル探索ツリー、バイナリ・ツリー、およびハッシュ・テーブルを含む種々のデータ構造により行うことができる。
６．１４ インデックスの格納
インデックスは、メモリ内またはディスク上に格納することができる。インデックスのサイズの低減は、インデックスがメモリ内に保持されている場合には重要な問題である。実験の結果、ある実施形態の場合には、インデックスがメモリ内に保持されている場合には、システムの動作が遥かに速くなることが分かっている。クラスタ内の目標のサブブロックの位置を識別する情報を格納しなくてすむならば、インデックスのサイズをかなり低減することができる。それ故、典型的な実施形態の場合には、インデックス内にクラスタ番号だけを格納する。
６．１５ サブブロック・インデックスのためのハッシュ・テーブルの使用
サブブロック・インデックスは、低冗長記憶システムの速度を判定する際に非常に重要なものであるので、このデータ構造を最高速でアクセスできるように設計するのは重要なことである。ハッシュ・テーブルは、０（１）時間内にアクセスを提供するので、ハッシュ・テーブルは、サブブロック・インデックスに対して非常に優れたデータ構造を提供する。しかし、このハッシュ速度アクセスは、かなり高いものにつく。以下のいくつかの節は、サブブロック・インデックスが提起する課題について説明する。
６．１６ ハッシュ・テーブルの衝突
この節においては、ハッシュ・テーブルの衝突について説明するが、インデックスがハッシュ・テーブルを使用して実施される場合にだけ適用される。
【０１０８】
衝突は、２つのキー２１０、２１２が、同じ位置（スロット）２１６にハッシュ２１４した場合に、ハッシュ・テーブル内で起こる（図２１）。この状況を解決する１つの方法は、第２のエントリを単に廃棄するという方法である。ある場合には、これは正しい選択である場合がある。しかし、ハッシュ・テーブルが損失を許容するものでない場合には、このオプションを使用することはできないので、この「オーバーフロー」状況を処理するために種々様々な技術のうちの１つを使用することができる。
【０１０９】
衝突を処理するために昔から使用されてきた１つの技術は、「オーバーフロー」領域２２０と呼ぶ別の記憶領域を有する方法である。各ハッシュ・テーブル・スロットは、オーバーフロー・フィールド２２２を含む。スロット内で衝突が起きた場合には、オーバーフロー・エントリ２２４は、オーバーフロー領域内に格納され、エントリへのポインタがスロット２２２内に置かれる（図２２）。オーバーフロー領域によりエントリはまた相互にポイントすることができ２２６、各オーバーフロー・スロットは、エントリのリストをポイントすることができる（図２２）。（ハッシュ・テーブルがメモリ内に位置していて、メモリ・ヒープの形をしている場合のように）別々のオーバーフロー領域を使用できる場合には、この技術はうまく動作する。しかし、ハッシュ・テーブルがディスク上に位置している場合には、オーバーフロー領域内にオーバーフロー・エントリを置くと、通常、非常に遅い少なくとも１回のランダム・アクセス・シークを行うステップが関連してくる。
【０１１０】
衝突へのもっとうまいアプローチは、衝突しているエントリを、ハッシュ・テーブル自身内に格納する方法である。昔からのアプローチの場合には、衝突が起こると、第２のハッシュ関数により第２の項目キーがハッシュされ、結果として得られたスロットがチェックされる。スロットが空である場合には、エントリをそこに格納することができる。もしスロットが空でない場合には、第３のハッシュ関数を呼び出すことができ、空のスロットが発見されるまでこの手順が反復して行われる。全テーブルが満杯である場合には、テーブルを分割してからでなければ、新しいエントリを追加することはできない。一般に、ハッシュ関数Ｈ（Ｋ，Ｘ）は、Ｋがハッシュするキーであり、Ｘが、衝突しているエントリに対するハッシュ・テーブル内の連続している候補の位置を発見するために増大することができる正の整数である場合に定義することができる。キーＫを探索するために、キーを含むスロットを発見するまで、または（テーブル内のハッシュ・オーバーフロー・チェーンの終わりを示す）空のスロットに遭遇するまで、Ｘ＝１，２，．．．に対してスロットＨ（Ｋ，Ｘ）がチェックされる。
【０１１１】
このアプローチの問題は、ハッシュ・テーブルが大きなもので、ディスク上に位置している場合には、衝突チェーンの後で、非常に時間がかかる一連のランダム・アクセス・シークをディスク上で行わなければならないことである。このことはＨ（Ｋ，Ｘ）＝Ｈ（Ｋ，Ｘ−１）＋１と定義することにより、すなわち、（テーブルの終わりのところを囲んでいる）次の隣接スロット２３０（図２３）に溢れることにより避けることができる。この技術の場合には、アクセスは局部的なままである。アクセスした第１のスロットを読み出した場合には、次のＳスロットも小さなＳに対して読み出され、ディスク動作は、（例えば、１２バイトの代わりに１Ｋを読み出すように）余分な時間はかからないし、オーバーフロー・スロットも提供する。新しいエントリが追加されると、複数のスロットを１つのグループとしてディスクに書戻すことができる。衝突チェーンがＳ個のスロットを超えて跨ることが希になるように（およびそれにより追加のディスク・アクセスが必要になるように）（おそらく動的に）値Ｓが調整される。
６．１７ ハッシュ・テーブル・バケット
インデックスがディスク上に格納されている場合には、インデックスへのランダム・アクセス読出しおよび書込みは時間がかかるものになる場合がある。それ故、あるスロットから他のスロットに溢れるチャンスがある場合には、２つ以上のスロットを一度に読出しおよび書込みするのは理にかなっている。そうするための１つの方法は、テーブルをバケット２４０に分割し（図２４）、エントリのかわりにバケットを読み出し、書き込む方法である。例えば、１０２４のスロットのテーブルを、それぞれが１６のスロットを含む６４のバケットのテーブルで置き換えることができる。エントリを探索するために、バケットを読み出して、バケット内で線形探索を行うことができ（またはバケット内のキーがソートされる場合、二分探索をおそらく行うことができる）。時々であるがバケットが満杯になっている場合がある。その場合には、オーバーフローは次のバケットに移動する。テーブルがあまり大きく成長できない限りは、オーバーフロー・チェーンはあまり長くすべきではない。
６．１８ ハッシュ・テーブルの成長
ハッシュ・テーブルを使用した場合の１つの問題は、満杯になった場合、拡張するはっきりした方法がないことである。
【０１１２】
この問題に対する１つのアプローチは、テーブルがけっして満杯にならないようにすることである。このことは、最初に、特定の用途の場合にけっして満杯にならないほど大きなハッシュ・テーブルを生成することにより行うことができる。しかし、ある用途の場合には、予めハッシュ・テーブル上の負荷を予測することができない場合があり、そのため他の解決方法を発見しなければならない。
【０１１３】
１つのアプローチは、新しいもっと大きなハッシュ・テーブルを生成し、旧テーブル内のすべてのエントリを新テーブルに転送することによりハッシュ・テーブルを廃棄する方法である。転送中に両方のテーブルを保持するための十分なメモリが存在する限り、このアプローチは完全に実行可能な方法である。
【０１１４】
もう１つのアプローチは、満杯になったらいつでもハッシュ・テーブルのサイズを２倍にし、第１の（旧）２５０の半体内のエントリの（約）半体を、第２の（新）２５１の半体に転送する方法である。図２５は、その方法を示す。最初のハッシュ・テーブルが２Ｋのエントリを有している場合には、全キーの下のＫビットを、テーブルを索引するために使用することができる。テーブルが満杯になったら２倍に増大することができる。この新テーブルは、全キー２５４のＫ＋１の最も低いビットをキーとして使用する。現在使用しているキーの余分なビット（ビットＫ）は、２倍にしたテーブルの旧テーブルおよび新テーブルの半体を区別する。全キーの左側の残りは未使用のままである。あとは、そのビットＫが１である２倍にしたテーブルの旧半体内のエントリを新半体内の対応する位置に移動するだけでよい。実際には、オーバーフローがあるので、これより少し複雑になる。最初に、オーバーフローは、エントリがテーブルの旧半体内の「自然の」位置に位置していなくて、それ故、すべてのエントリを単に移動すると、ビットＫセットがいくつかのエントリを正しくない位置に移動する。このことは、再ハッシュが必要なことを意味する。第二に、旧半体内のエントリを除去すると、いくつかのオーバーフロー・チェーンが切断する場合があり、いくつかのエントリにアクセスできなくなる恐れがある。それ故、エントリを移動した場合、そのエントリのオーバーフロー・チェーンをギャップを埋めるためにもとに戻してやらなければならない。
６．１９ サブブロック・インデックス部分キーの格納
インデックスのサイズを小さくする１つの方法は、各インデックス・エントリ内にインデックスのキーのコピーを格納しない方法である。例えば、インデックス・キーが、（サブブロックの）１２８ビットのＭＤ５ハッシュである場合には、インデックスのサイズを小さくする１つの方法は、インデックスのエントリ内のキーの一部だけを記録する方法である。
【０１１５】
例えば、インデックスがハッシュ・テーブル１２０として実施される場合には、各ハッシュ・テーブル・エントリ１２２は、通常、クラスタ番号１２４およびサブブロック・ハッシュ１２６のコピーを含む（図１２）。これにより、インデックスのハッシュ・テーブル内の同じ位置に２つのサブブロックがハッシュされた場合には、２つのエントリを区別することができる。しかし、ハッシュが１２８ビット幅を有していて、各ハッシュの６４ビットだけを格納する場合には、エントリは、依然として区別することができるが、スペースの半分を使用することになる。
【０１１６】
極端な場合、ハッシュ・テーブルは、任意のキーの任意の部分を含んでいない。代わりに、各サブブロック・ハッシュは、ハッシュ・テーブル内のある位置にハッシュし、その位置で発見したすべてのクラスタを探索しなければならない。これは、依然として記憶装置内のすべてのクラスタの線形探索より遥かに優れている。
【０１１７】
最善のアプローチは、ハッシュのある部分は格納するが、すべてのハッシュは格納しない方法である。このことは、希な場合ではあるが、ハッシュ・テーブル内に２つ以上の一致するエントリが存在する場合があり、一組の一致するエントリに参照したすべてのクラスタを探索しなければならないことを意味する。エントリ内のハッシュの一部だけを格納すれば、いくつかのクラスタをチェックしなくてもすみ、しかも依然として完全なハッシュよりかなり少ないスペースしか使用しない十分な違いを提供する。
６．２０ ＢＬＯＢの削除
ある用途の場合には、ＢＬＯＢを削除し、またＢＬＯＢを格納しなければならない場合がある。ＢＬＯＢの削除を行わなければならない場合がある。何故なら、ＢＬＯＢのスパン内で参照したすべてのサブブロックを単に削除する（次に、ＢＬＯＢのスパンおよびＢＬＯＢレコードを削除する）明らかなアプローチは、このような行為は、他の（削除していない）ＢＬＯＢの一部でもあるサブブロックを削除する恐れがあるために失敗するからである。もっと高度なアプローチが望ましい。
【０１１８】
ＢＬＯＢを削除するためのあるアプローチは、記憶装置内の各サブブロックに余分なメタデータを追加する方法である。基準カウント。サブブロックの基準カウントは、サブブロックを含む（ＢＬＯＢ内の）スパンの数を格納する。基準カウント・アプローチの場合には、サブブロックを含む新しいスパンが生成されると（すなわち、ＢＬＯＢ格納中に）サブブロックの基準カウントが増大し、このようなスパンが削除されると（すなわち、ＢＬＯＢ削除中に）この基準カウントが低減する。その基準カウントがゼロになった場合には、サブブロックを削除することができる。
【０１１９】
基準カウント・アプローチを使用すれば、記憶システムは、ＢＬＯＢを削除することができる。しかし、ユーザはこの機能を必要としない。基準カウントの他の方法は、満了システムである。このシステムの場合、各ＢＬＯＢおよび各サブブロックは満了日を有する。ＢＬＯＢを格納した場合、ユーザは満了日を提供し、ＢＬＯＢが追加され、スパンの新しいリストが生成される。追加プロセスの一部として、スパン・リストが参照したサブブロックは、その前の満了日の最大値に設定したその満了日を有し、それらを新しく参照しているＢＬＯＢの日付を有する。ＢＬＯＢおよびサブブロックに満了日を表示すると、背景プロセスは、満了したＢＬＯＢおよびサブブロックを自由に削除することができる。
６．２１ 既存のファイル・システムを使用する実施形態
本発明の実施形態は、既存のファイル・システムの頂部上で実施することができる。図３１は、その構成方法を示す。
【０１２０】
このような実施形態の場合、各クラスタは、１つのクラスタ・ファイル３４０内に格納することができる。クラスタに番号が付けられている場合には、各クラスタの名前は、クラスタ番号を含むことができる。クラスタ・ファイルは、１つのディレクトリ３４２またはディレクトリのツリー３４４内に格納することができる（図３４）。クラスタはそのファイル上でランダム・アクセス読出しおよび書込みを行うことにより直接修正することもできるし、またはクラスタ・ファイルをメモリ内の完全な読み出し、それを修正し、およびシーケンシャルなＩＯ動作を使用して、全ファイルをディスクに書き戻すことにより修正することができる。
【０１２１】
もう１つの実施形態は、既存のファイル・システムを使用することができるが、１つのファイルしか使用しない。クラスタは、メモリ内に保持しているクラスタインデックス３３２を使用することにより、隣接して位置する１つのファイル３３０内に格納することができる（図３３）。
【０１２２】
固定長クラスタ・ディレクトリを使用する場合には、クラスタ・ディレクトリの一組全体を、ディレクトリを格納している１つのファイル内にアレイとして格納することができ、ファイルにランダム・アクセスを行って特定のディレクトリにランダム・アクセスすることができるようにする。
【０１２３】
各ＢＬＯＢは、その名前がＢＬＯＢのハッシュの名前であるファイル内に格納することができる。ＢＬＯＢファイルは、ＢＬＯＢディレクトリ内、またはディレクトリ（おそらくＢＬＯＢハッシュの連続しているバイトにより構成されているデジタル探索ツリー）内に格納することができる。各ＢＬＯＢファイルは、ＢＬＯＢを表すスパンのリストを含むことができる。ファイル・システムのファイル毎のスペース・オーバーヘッドを避けるために、複数のＢＬＯＢを１つの「ＢＬＯＢ」ファイル内に格納することができる。
６．２２ 仮想ブロック装置を使用する実施形態
本発明の実施形態は、既存のオペレーティング・システム３２２が提供する仮想ブロック装置を使用して実施することができる（図３２）。クラスタは、メモリ内に保持しているクラスタインデックスを使用することにより、隣接して位置する仮想ブロック装置内に格納することができる。
６．２３ データを格納しない実施形態
すでに説明した実施形態のいずれかと同じではあるが、任意のＢＬＯＢデータを実際に格納しない実施形態を生成することができる（図３５）。このような実施形態の場合には、すべての記憶構造およびメタデータを構成することができるが、ＢＬＯＢ／サブブロック・コンテンツは格納されない。この実施形態のような実施形態は、前に遭遇したＢＬＯＢ１に関連してＢＬＯＢ２を分析しなければならない用途の際に役に立つが、その場合、ＢＬＯＢを実際には格納してはならない。
【０１２４】
例えば、セキュリティ環境においては、ＢＬＯＢコンテンツ自身を格納しないで、前に遭遇したＢＬＯＢに関連してＢＬＯＢを分析するためにＢＬＯＢメタデータを使用する方が有利な場合がある。記憶構造および既存のＢＬＯＢを表すメタデータを使用することにより、記憶装置は、前に遭遇したＢＬＯＢにアクセスしなくても、前に遭遇したＢＬＯＢの本体に関連して文書を分析することができる。例えば、このことはセキュアなゲートウェイに適用することができる。
６．２４ 範囲に関する注
当業者であれば、本発明は、上記の特定の用途に限定されないことを理解することができるだろう。また、本発明は、本明細書に記載し図面に示した特定の要素および／または機能に関してその好ましい実施形態に限定されない。本発明の原理から逸脱することなしに、種々の修正を行うことができることを理解することができるだろう。それ故、本発明は、本発明の範囲内に入るすべてのこのような修正を含むものと解釈すべきである。
【図面の簡単な説明】
【０１２５】
【図１】ＢＬＯＢのサブブロックへの分割である。
【図２】クラスタ内のＢＬＯＢのサブブロックの記憶装置である。
【図３】ＢＬＯＢを、クラスタ内のサブブロックの一続きの部分を識別するスパンの順序付きリストとして表す方法である。
【図４】データの共通シーケンス（サブブロックＡ〜ＣおよびＧ〜Ｊ）を含む２つの異なるＢＬＯＢを、各反復サブブロックを２回以上格納しないですむ方法で表す方法である。
【図５】サブブロックを含むクラスタの数に各サブブロックのハッシュをマッピングするインデックスを示す。
【図６】ＢＬＯＢを固定長サブブロックに分割する分割方法である。
【図７】クラスタの開始のところにサブブロック・ディレクトリを含むサブブロックのクラスタである。
【図８】クラスタのディレクトリをクラスタ自身とは別々に格納する方法である。
【図９】クラスタ・サブブロック・ディレクトリのエントリをクラスタ全体に分配する方法である。
【図１０】（格納しているＢＬＯＢの）サブブロックＡがクラスタ＃１内にすでに存在することを発見した後で、ＢＬＯＢ内の以降のサブブロック（Ｂ、ＣおよびＤ）をそのクラスタ内でＡの後のサブブロック（この場合は、Ｂ、ＣおよびＤ）と比較することができ、それによりサブブロック・インデックス内のＢ、ＣおよびＤを参照しなくてもすむＢＬＯＢを格納する態様を示す。
【図１１】それぞれが、ＢＬＯＢ内のサブブロックを識別するスパンの順序付きリストを含む（または参照する）ＢＬＯＢレコードにＢＬＯＢハッシュをマッピングするＢＬＯＢテーブルである。
【図１２】サブブロック・インデックス・ハッシュ・テーブルであり、テーブルのエントリである。
【図１３】（従来技術）データの同じサブ・シーケンスの２つの例を含む２つのファイルである。さらに、ファイルＡは、それ自身の中に同一のファイルを有する。
【図１４】（従来技術）従来の記憶システムのその共通データを識別しようとしないファイルの格納方法である。
【図１５】（従来技術）従来のデータ圧縮が各ＢＬＯＢのサイズを小さくするが、ＢＬＯＢ間のデータの共通シーケンスを識別しないことを示す。
【図１６】データの同じシーケンスを含む２つのＢＬＯＢの表示が、データのこれらのシーケンスを参照し、そのためシーケンスを１回格納するだけですむ方法である。
【図１７】任意の部分一致があるか否かをチェックするために、一致する一続きの部分の各端部のところのサブブロックを直接比較する方法である。
【図１８】一続きの部分の両端のところに部分サブブロックを含むサブブロックの一続きの部分を表すために（それぞれがバイト・カウントを保持する）２つの追加フィールド「開始スキップ」および「終了スキップ」で、スパン・レコードを増大する方法である。
【図１９】ＢＬＯＢを格納した場合に、孤立している一致サブブロック（Ｃ）がＢＬＯＢの表示で分割を行う方法である。
【図２０】記憶装置で孤立サブブロック（Ｃ）を２回格納することを選択することにより分割を避ける方法である。
【図２１】２つのキーが、テーブル内の同じ位置にハッシュするハッシュ・テーブル衝突を示す。
【図２２】外部オーバーフロー・リストを含むハッシュ・テーブルである。
【図２３】オーバーフロー・エントリが次の空のスロットに格納されるテーブル内オーバーフローである。
【図２４】それぞれが一定数のエントリ・スロットを含むバケットのアレイとして構成されたハッシュ・テーブルである。
【図２５】全キーの余分なビットを使用してハッシュ・テーブルのサイズを２倍にする方法である。
【図２６】３つの分岐を含むスパンのツリーである。スパンをツリーに編成することにより、ＢＬＯＢ内のランダム・アクセスが高速になる。図面の番号は、各子ノードが表すブロックの長さである。
【図２７】元のＢＬＯＢ内で隣接しているサブブロックの一続きの部分を識別するためのクラスタ内のサブブロックの一連番号の意図的なスキップである。
【図２８】２つのサブブロックＡおよびＢを直接比較しないで、これらのサブブロックＡおよびＢを比較する暗号ハッシュ関数Ｈの使用方法である。代わりに、そのハッシュＨ（Ａ）およびＨ（Ｂ）が比較される。
【図２９】サブブロックＡ、Ｂ、ＣおよびＤを索引し、そのキーが、サブブロック自身ではなく、（ハッシュ関数Ｈを使用する）サブブロックのハッシュであるサブブロック・インデックスである。
【図３０】サブブロックに分割され、低冗長記憶装置に格納されたにも関わらず、ＢＬＯＢがその統合性を保持していることをチェックするための暗号ハッシュ関数Ｈの使用方法である。元のＢＬＯＢのハッシュは、格納しているＢＬＯＢと一緒に格納され、検索したＢＬＯＢのハッシュと比較される。
【図３１】既存のファイル・システム（の頂部上）を使用して低冗長記憶システムが実施される実施形態である。
【図３２】既存のオペレーティング・システムが提供する仮想ブロック装置（の頂部上）を使用して低冗長記憶システムを実施する実施形態である。
【図３３】１つのブロック装置またはファイル・システム内の１つのファイル内に、長さが変化するクラスタを格納する方法である。クラスタ・インデックスは、その番号によりクラスタを迅速に発見するために使用することができる。
【図３４】既存のファイル・システム内のファイルの対応する集合体内へのクラスタの集合体の格納方法である。この例の場合には、ディレクトリ・ツリーは、クラスタ番号上の小数デジタル探索ツリーを形成する。
【図３５】ＢＬＯＢを格納するために必要な構造およびメタデータを生成したが、データ自身を格納していない実施形態である。
【図３６】元のスパン（サブブロックＦＧＨ）と同じデータを指しているが、記憶装置の異なる部分（この場合は、異なるクラスタ）内に位置する別のスパンにより増大したスパン（スパンのリスト内の２番目）である。
【図３７】制約Ｆを使用するサブブロックへのブロックｂの分割、およびハッシュ関数Ｈを使用するサブブロックのハッシュの計算を示す。
【図３８】典型的なコンピュータ・ハードウェア上での低冗長記憶システムの配置方法である。すべてのデータ構造は、ディスク上に常駐している。また、インデックスも、いくつかのＢＬＯＢレコードおよびクラスタの作業コピーを格納しているいくつかのキャッシュと一緒にメモリ内に保持される。
【特許請求の範囲】
【請求項１】
ＢＬＯＢを複数のサブブロックに分割するステップと、
前記サブブロックを複数のクラスタ内に格納するステップと、
前記ＢＬＯＢの表示を複数のスパンとして生成するステップであって、各スパンがクラスタ内のサブブロックのシーケンスを識別し、少なくとも１つのサブブロックが２つ以上のスパンにより参照されるステップとを含むＢＬＯＢを格納する方法。
【請求項２】
各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別する、請求項１に記載の方法。
【請求項３】
前記複数のスパンが順序付きリストである、請求項１に記載の方法。
【請求項４】
前記複数のスパンがスパンのツリーである、請求項１に記載の方法。
【請求項５】
２つ以上のサブブロックが、介入メタデータを使用しないでクラスタ内にバイトの隣接シーケンスとして格納される、請求項１に記載の方法。
【請求項６】
前記サブブロックが、いくつかのサブブロック・メタデータとインタリーブしている、請求項１に記載の方法。
【請求項７】
各スパンが、クラスタ識別子、クラスタ・アドレス、サブブロック識別子、クラスタ内のサブブロック位置、長さのうちの少なくとも１つを使用して、クラスタ内の隣接サブブロックのシーケンスを識別する、請求項１に記載の方法。
【請求項８】
前記長さがサブブロック数である、請求項７に記載の方法。
【請求項９】
前記長さがバイト数である、請求項７に記載の方法。
【請求項１０】
上部境界が、各クラスタ内のサブブロック数上に置かれる、請求項１に記載の方法。
【請求項１１】
上部境界が、各クラスタ内のバイト数上に置かれる、請求項１に記載の方法。
【請求項１２】
前記データが、前記一組のデータｂをｂ内の少なくとも１つの位置ｋ｜ｋ＋１のところで複数のサブブロックに分割することにより分割され、ｂ［ｋ−Ａ＋１．．．ｋ＋Ｂ］が所定の制約を満たし、ＡおよびＢが自然数である、請求項１に記載の方法。
【請求項１３】
前記データを格納する前記データ構造が生成されるが、前記データ自身は格納されない、請求項１に記載の方法。
【請求項１４】
データを複数のサブブロックに分割するステップと、
前記サブブロックを複数のクラスタに格納するステップと、
前記一組のデータの表示を複数のスパンとして生成するステップであって、各スパンがクラスタ内のサブブロックのシーケンスを識別し、少なくとも１つのサブブロックが２つ以上のスパンにより参照されるステップとを含む一組のデータを格納する方法。
【請求項１５】
前記データがデータ・ファイルである、請求項１４に記載の方法。
【請求項１６】
スパンのグループにより参照された前記サブブロックから前記一組のデータを再構成するステップをさらに含む、請求項１４に記載の方法。
【請求項１７】
前記データが、前記一組のデータｂをｂ内の少なくとも１つの位置ｋ｜ｋ＋１のところで複数のサブブロックに分割することにより分割され、ｂ［ｋ−Ａ＋１．．．ｋ＋Ｂ］が、所定の制約を満たし、ＡおよびＢが自然数である、請求項１４に記載の方法。
【請求項１８】
各クラスタが、サブブロックのディレクトリを有し、前記ディレクトリが、各サブブロックの長さ、各サブブロックのハッシュ、前記クラスタ内の各サブブロックの位置、各サブブロックに対する識別子のうちの少なくとも１つを含む、請求項１に記載の方法。
【請求項１９】
前記クラスタ・ディレクトリが、前記クラスタ内に格納される、請求項１８に記載の方法。
【請求項２０】
前記クラスタ・ディレクトリが、前記クラスタとは別々に格納される、請求項１８に記載の方法。
【請求項２１】
前記クラスタ・ディレクトリが、前記クラスタが含むサブブロック数が何であれ固定長である、請求項１８に記載の方法。
【請求項２２】
前記クラスタ・ディレクトリが固定長であり、クラスタ・ディレクトリの固定長アレイ内に前記クラスタとは別々に格納される、請求項１８に記載の方法。
【請求項２３】
前記クラスタが、前記クラスタ内のサブブロックの隣接する一続きの部分間の境界を記録する、請求項１８に記載の方法。
【請求項２４】
クラスタ内のサブブロック間の境界が、順序付き識別子を使用することにより、および境界のところでサブブロックに隣接していない識別子を割り当てることにより識別される、請求項１８に記載の方法。
【請求項２５】
圧縮アルゴリズムを使用して少なくとも１つのクラスタを圧縮するステップをさらに含む、請求項１に記載の方法。
【請求項２６】
圧縮アルゴリズムを使用して少なくとも１つのサブブロックを圧縮するステップをさらに含む、請求項１に記載の方法。
【請求項２７】
少なくとも２つの隣接サブブロックが、圧縮アルゴリズムを使用することにより圧縮される、請求項１に記載の方法。
【請求項２８】
少なくとも１つのサブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持するステップをさらに含む、請求項１に記載の方法。
【請求項２９】
少なくとも１つのサブブロックのハッシュを、前記サブブロックを含む前記クラスタにマッピングするインデックスを維持するステップをさらに含む、請求項１に記載の方法。
【請求項３０】
前記インデックスが、前記サブブロックを含む前記クラスタ内の各サブブロックの位置を含む、請求項２８または２９に記載の方法。
【請求項３１】
前記インデックスが、そのキーがサブブロック・ハッシュであるデジタル探索ツリーとして実施される、請求項２８または２９に記載の方法。
【請求項３２】
前記インデックスが、Ｂツリーとして実施される、請求項２８に記載の方法。
【請求項３３】
各ＢＬＯＢ内の各Ｔ番目のサブブロックだけが索引され、Ｔが所定の正の整数である、請求項２８に記載の方法。
【請求項３４】
各ＢＬＯＢ内の各Ｔ番目のサブブロックだけが索引され、Ｔが所定の正の整数である、請求項２９に記載の方法。
【請求項３５】
前記インデックスが、１つまたは複数のハッシュ・テーブルとして実施される、請求項２８に記載の方法。
【請求項３６】
サブブロックに対するハッシュ・テーブル・エントリが、前記サブブロックの前記ハッシュの全部または一部を含む、請求項３５に記載の方法。
【請求項３７】
前記ハッシュ・テーブルがバケットを含む、請求項３５に記載の方法。
【請求項３８】
各スパンが、前記クラスタ内の１つまたは複数のバイトの有限シーケンスを参照する、請求項１に記載の方法。
【請求項３９】
各スパンが、ｘバイトだけ低減する前記スパンの範囲を示す少なくとも１つのスキップ値ｘを含む、請求項１に記載の方法。
【請求項４０】
各スパンが、ｘバイトだけ増大する前記スパンの範囲を示す少なくとも１つの拡張値ｘを含む、請求項１に記載の方法。
【請求項４１】
クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックするステップを含む、請求項２８に記載の方法。
【請求項４２】
格納するサブブロックのハッシュを、クラスタ内の前記サブブロックのうちの少なくとも１つの前記ハッシュと比較することにより、サブブロックの複製をチェックするステップであって、インデックスが格納するサブブロックを示すステップを含む、請求項２９に記載の方法。
【請求項４３】
スパンが、前記サブブロックの前記ハッシュの一部または全部を使用してサブブロックを識別する、請求項１に記載の方法。
【請求項４４】
Ｔの現在のサブブロック以下の少なくとも１つの隣接する一続きの部分が、サブブロックの記憶装置内で複製され、Ｔがサブブロックの所定のしきい値である、請求項１に記載の方法。
【請求項４５】
Ｔが２である、請求項４４に記載の方法。
【請求項４６】
１つまたは複数のサブブロックの少なくとも１つの隣接する一続きの部分が、サブブロックの前記記憶装置内で複製される、請求項１に記載の方法。
【請求項４７】
少なくとも１つのスパンＸが、スパンＸにより参照されたデータのコピーを参照する別のスパンにより増大する、請求項１に記載の方法。
【請求項４８】
前記インデックスをクラスタ内のサブブロックＸの位置の発見に使用した場合に、格納中の前記サブブロックによりサブブロックの最も長い一致する一続きの部分を発見するために、前記クラスタがサブブロックＸから順方向に探索される、請求項２８に記載の方法。
【請求項４９】
前記インデックスをクラスタ内のサブブロックＸの位置の発見に使用した場合に、格納中の前記サブブロックによりサブブロックの最も長い一致する一続きの部分を発見するために、前記クラスタがサブブロックＸから順方向に探索される、請求項２９に記載の方法。
【請求項５０】
ＢＬＯＢを２つ以上のサブブロックに分割するためのデータ処理手段と、
１つまたは複数のクラスタ内に前記サブブロックを格納するためのデータ記憶手段と、
前記ＢＬＯＢをスパンの順序付きリストまたはスパンのツリーとして表示するための手段とを備え、
各スパンがクラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるデータのＢＬＯＢを格納するデータ処理装置。
【請求項５１】
前記処理手段が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項４３に記載のデータ処理装置。
【請求項５２】
前記処理手段が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項４４に記載のデータ処理装置。
【請求項５３】
データのＢＬＯＢを格納するためのプログラマブル・デバイスを指示するために使用することができる、コンピュータ・プログラムを表すデータで符号化したコンピュータ可読メモリであって、
前記ＢＬＯＢを２つ以上のサブブロックに分割するために、前記コンピュータ可読メモリを動作するための処理手段と、
１つまたは複数のクラスタ内に前記サブブロックを格納するために、前記コンピュータ可読メモリにより使用することができるデータ記憶手段と、
前記ＢＬＯＢをスパンの順序付きリストまたはスパンのツリーとして表示するための手段とを備え、各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるコンピュータ可読メモリ。
【請求項５４】
前記処理手段が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項５３に記載のコンピュータ可読メモリ。
【請求項５５】
前記処理手段が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項５４に記載のコンピュータ可読メモリ。
【請求項５６】
プログラマブル・デバイスに、
前記ＢＬＯＢを複数のサブブロックに分割する第１の機能と、
前記サブブロックを複数のクラスタに格納する第２の機能と、
前記ＢＬＯＢを関連するスパンのグループとして表示する第３の機能と
を実行させるために、データのＢＬＯＢを格納するためのコンピュータ・プログラム・コード手段を備えるコンピュータ・プログラム要素であって、
各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるコンピュータ・プログラム要素。
【請求項５７】
第４の機能が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項５６に記載のコンピュータ・プログラム要素。
【請求項５８】
第５の機能が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項５７に記載のコンピュータ・プログラム要素。
【請求項１】
ＢＬＯＢを複数のサブブロックに分割するステップと、
前記サブブロックを複数のクラスタ内に格納するステップと、
前記ＢＬＯＢの表示を複数のスパンとして生成するステップであって、各スパンがクラスタ内のサブブロックのシーケンスを識別し、少なくとも１つのサブブロックが２つ以上のスパンにより参照されるステップとを含むＢＬＯＢを格納する方法。
【請求項２】
各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別する、請求項１に記載の方法。
【請求項３】
前記複数のスパンが順序付きリストである、請求項１に記載の方法。
【請求項４】
前記複数のスパンがスパンのツリーである、請求項１に記載の方法。
【請求項５】
２つ以上のサブブロックが、介入メタデータを使用しないでクラスタ内にバイトの隣接シーケンスとして格納される、請求項１に記載の方法。
【請求項６】
前記サブブロックが、いくつかのサブブロック・メタデータとインタリーブしている、請求項１に記載の方法。
【請求項７】
各スパンが、クラスタ識別子、クラスタ・アドレス、サブブロック識別子、クラスタ内のサブブロック位置、長さのうちの少なくとも１つを使用して、クラスタ内の隣接サブブロックのシーケンスを識別する、請求項１に記載の方法。
【請求項８】
前記長さがサブブロック数である、請求項７に記載の方法。
【請求項９】
前記長さがバイト数である、請求項７に記載の方法。
【請求項１０】
上部境界が、各クラスタ内のサブブロック数上に置かれる、請求項１に記載の方法。
【請求項１１】
上部境界が、各クラスタ内のバイト数上に置かれる、請求項１に記載の方法。
【請求項１２】
前記データが、前記一組のデータｂをｂ内の少なくとも１つの位置ｋ｜ｋ＋１のところで複数のサブブロックに分割することにより分割され、ｂ［ｋ−Ａ＋１．．．ｋ＋Ｂ］が所定の制約を満たし、ＡおよびＢが自然数である、請求項１に記載の方法。
【請求項１３】
前記データを格納する前記データ構造が生成されるが、前記データ自身は格納されない、請求項１に記載の方法。
【請求項１４】
データを複数のサブブロックに分割するステップと、
前記サブブロックを複数のクラスタに格納するステップと、
前記一組のデータの表示を複数のスパンとして生成するステップであって、各スパンがクラスタ内のサブブロックのシーケンスを識別し、少なくとも１つのサブブロックが２つ以上のスパンにより参照されるステップとを含む一組のデータを格納する方法。
【請求項１５】
前記データがデータ・ファイルである、請求項１４に記載の方法。
【請求項１６】
スパンのグループにより参照された前記サブブロックから前記一組のデータを再構成するステップをさらに含む、請求項１４に記載の方法。
【請求項１７】
前記データが、前記一組のデータｂをｂ内の少なくとも１つの位置ｋ｜ｋ＋１のところで複数のサブブロックに分割することにより分割され、ｂ［ｋ−Ａ＋１．．．ｋ＋Ｂ］が、所定の制約を満たし、ＡおよびＢが自然数である、請求項１４に記載の方法。
【請求項１８】
各クラスタが、サブブロックのディレクトリを有し、前記ディレクトリが、各サブブロックの長さ、各サブブロックのハッシュ、前記クラスタ内の各サブブロックの位置、各サブブロックに対する識別子のうちの少なくとも１つを含む、請求項１に記載の方法。
【請求項１９】
前記クラスタ・ディレクトリが、前記クラスタ内に格納される、請求項１８に記載の方法。
【請求項２０】
前記クラスタ・ディレクトリが、前記クラスタとは別々に格納される、請求項１８に記載の方法。
【請求項２１】
前記クラスタ・ディレクトリが、前記クラスタが含むサブブロック数が何であれ固定長である、請求項１８に記載の方法。
【請求項２２】
前記クラスタ・ディレクトリが固定長であり、クラスタ・ディレクトリの固定長アレイ内に前記クラスタとは別々に格納される、請求項１８に記載の方法。
【請求項２３】
前記クラスタが、前記クラスタ内のサブブロックの隣接する一続きの部分間の境界を記録する、請求項１８に記載の方法。
【請求項２４】
クラスタ内のサブブロック間の境界が、順序付き識別子を使用することにより、および境界のところでサブブロックに隣接していない識別子を割り当てることにより識別される、請求項１８に記載の方法。
【請求項２５】
圧縮アルゴリズムを使用して少なくとも１つのクラスタを圧縮するステップをさらに含む、請求項１に記載の方法。
【請求項２６】
圧縮アルゴリズムを使用して少なくとも１つのサブブロックを圧縮するステップをさらに含む、請求項１に記載の方法。
【請求項２７】
少なくとも２つの隣接サブブロックが、圧縮アルゴリズムを使用することにより圧縮される、請求項１に記載の方法。
【請求項２８】
少なくとも１つのサブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持するステップをさらに含む、請求項１に記載の方法。
【請求項２９】
少なくとも１つのサブブロックのハッシュを、前記サブブロックを含む前記クラスタにマッピングするインデックスを維持するステップをさらに含む、請求項１に記載の方法。
【請求項３０】
前記インデックスが、前記サブブロックを含む前記クラスタ内の各サブブロックの位置を含む、請求項２８または２９に記載の方法。
【請求項３１】
前記インデックスが、そのキーがサブブロック・ハッシュであるデジタル探索ツリーとして実施される、請求項２８または２９に記載の方法。
【請求項３２】
前記インデックスが、Ｂツリーとして実施される、請求項２８に記載の方法。
【請求項３３】
各ＢＬＯＢ内の各Ｔ番目のサブブロックだけが索引され、Ｔが所定の正の整数である、請求項２８に記載の方法。
【請求項３４】
各ＢＬＯＢ内の各Ｔ番目のサブブロックだけが索引され、Ｔが所定の正の整数である、請求項２９に記載の方法。
【請求項３５】
前記インデックスが、１つまたは複数のハッシュ・テーブルとして実施される、請求項２８に記載の方法。
【請求項３６】
サブブロックに対するハッシュ・テーブル・エントリが、前記サブブロックの前記ハッシュの全部または一部を含む、請求項３５に記載の方法。
【請求項３７】
前記ハッシュ・テーブルがバケットを含む、請求項３５に記載の方法。
【請求項３８】
各スパンが、前記クラスタ内の１つまたは複数のバイトの有限シーケンスを参照する、請求項１に記載の方法。
【請求項３９】
各スパンが、ｘバイトだけ低減する前記スパンの範囲を示す少なくとも１つのスキップ値ｘを含む、請求項１に記載の方法。
【請求項４０】
各スパンが、ｘバイトだけ増大する前記スパンの範囲を示す少なくとも１つの拡張値ｘを含む、請求項１に記載の方法。
【請求項４１】
クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックするステップを含む、請求項２８に記載の方法。
【請求項４２】
格納するサブブロックのハッシュを、クラスタ内の前記サブブロックのうちの少なくとも１つの前記ハッシュと比較することにより、サブブロックの複製をチェックするステップであって、インデックスが格納するサブブロックを示すステップを含む、請求項２９に記載の方法。
【請求項４３】
スパンが、前記サブブロックの前記ハッシュの一部または全部を使用してサブブロックを識別する、請求項１に記載の方法。
【請求項４４】
Ｔの現在のサブブロック以下の少なくとも１つの隣接する一続きの部分が、サブブロックの記憶装置内で複製され、Ｔがサブブロックの所定のしきい値である、請求項１に記載の方法。
【請求項４５】
Ｔが２である、請求項４４に記載の方法。
【請求項４６】
１つまたは複数のサブブロックの少なくとも１つの隣接する一続きの部分が、サブブロックの前記記憶装置内で複製される、請求項１に記載の方法。
【請求項４７】
少なくとも１つのスパンＸが、スパンＸにより参照されたデータのコピーを参照する別のスパンにより増大する、請求項１に記載の方法。
【請求項４８】
前記インデックスをクラスタ内のサブブロックＸの位置の発見に使用した場合に、格納中の前記サブブロックによりサブブロックの最も長い一致する一続きの部分を発見するために、前記クラスタがサブブロックＸから順方向に探索される、請求項２８に記載の方法。
【請求項４９】
前記インデックスをクラスタ内のサブブロックＸの位置の発見に使用した場合に、格納中の前記サブブロックによりサブブロックの最も長い一致する一続きの部分を発見するために、前記クラスタがサブブロックＸから順方向に探索される、請求項２９に記載の方法。
【請求項５０】
ＢＬＯＢを２つ以上のサブブロックに分割するためのデータ処理手段と、
１つまたは複数のクラスタ内に前記サブブロックを格納するためのデータ記憶手段と、
前記ＢＬＯＢをスパンの順序付きリストまたはスパンのツリーとして表示するための手段とを備え、
各スパンがクラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるデータのＢＬＯＢを格納するデータ処理装置。
【請求項５１】
前記処理手段が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項４３に記載のデータ処理装置。
【請求項５２】
前記処理手段が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項４４に記載のデータ処理装置。
【請求項５３】
データのＢＬＯＢを格納するためのプログラマブル・デバイスを指示するために使用することができる、コンピュータ・プログラムを表すデータで符号化したコンピュータ可読メモリであって、
前記ＢＬＯＢを２つ以上のサブブロックに分割するために、前記コンピュータ可読メモリを動作するための処理手段と、
１つまたは複数のクラスタ内に前記サブブロックを格納するために、前記コンピュータ可読メモリにより使用することができるデータ記憶手段と、
前記ＢＬＯＢをスパンの順序付きリストまたはスパンのツリーとして表示するための手段とを備え、各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるコンピュータ可読メモリ。
【請求項５４】
前記処理手段が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項５３に記載のコンピュータ可読メモリ。
【請求項５５】
前記処理手段が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項５４に記載のコンピュータ可読メモリ。
【請求項５６】
プログラマブル・デバイスに、
前記ＢＬＯＢを複数のサブブロックに分割する第１の機能と、
前記サブブロックを複数のクラスタに格納する第２の機能と、
前記ＢＬＯＢを関連するスパンのグループとして表示する第３の機能と
を実行させるために、データのＢＬＯＢを格納するためのコンピュータ・プログラム・コード手段を備えるコンピュータ・プログラム要素であって、
各スパンが、クラスタ内の１つまたは複数の隣接サブブロックのシーケンスを識別し、少なくとも１つのサブブロックが、２つ以上のスパンにより参照されるコンピュータ・プログラム要素。
【請求項５７】
第４の機能が、各サブブロックを前記サブブロックを含む前記クラスタにマッピングするインデックスを維持する、請求項５６に記載のコンピュータ・プログラム要素。
【請求項５８】
第５の機能が、クラスタにサブブロックを追加する前に、前記インデックスをチェックすることによりサブブロックの複製をチェックする、請求項５７に記載のコンピュータ・プログラム要素。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図３５】
【図３６】
【図３７】
【図３８】
【公表番号】特表２００８−５３７２０９（Ｐ２００８−５３７２０９Ａ）
【公表日】平成２０年９月１１日（２００８．９．１１）
【国際特許分類】
【出願番号】特願２００８−５０００１１（Ｐ２００８−５０００１１）
【出願日】平成１８年３月１０日（２００６．３．１０）
【国際出願番号】ＰＣＴ／ＡＵ２００６／０００３２６
【国際公開番号】ＷＯ２００６／０９４３６５
【国際公開日】平成１８年９月１４日（２００６．９．１４）
【出願人】（５０７３０４８４５）ロックソフト リミテッド (3)
【公表日】平成２０年９月１１日（２００８．９．１１）
【国際特許分類】
【出願日】平成１８年３月１０日（２００６．３．１０）
【国際出願番号】ＰＣＴ／ＡＵ２００６／０００３２６
【国際公開番号】ＷＯ２００６／０９４３６５
【国際公開日】平成１８年９月１４日（２００６．９．１４）
【出願人】（５０７３０４８４５）ロックソフト リミテッド (3)
[ Back to top ]