(57)【要約】共通シーケンスといったデジタルシーケンスでブレークポイントを決める「スティッキーバイト」くくり出しを用いてデータシーケンスを組織化しないで決めるシステムおよび方法を確認できる。スティッキーバイトくくり出しは、最適な共通性に近いところを通常もたらす、データセットをピースに分割する効率的な方法を提供する。これは、ローリングハッシュ合計、および本願で開示されている典型的な実施例における、決定論的にデータシーケンスに部をセットする閾値関数を用いることによって、達成される。ローリングハッシュおよび閾値関数は、最小限度の計算を必要とするようできている。この低オーバーヘッドは、くくり出しエンジン、またはデータセットにわたって後続の同期を選択する他のアプリケーションに提示するためにデータシーケンスを迅速に分割することを可能にする。【特許請求の範囲】
【請求項１】
デジタルシーケンスを分割する方法であって、
少なくとも前記デジタルシーケンスの一部にハッシュ関数を実行するステップと、
前記ハッシュ関数によって生成されたハッシュ値を第１の予め決められた数パターンに対してモニタするステップと、
前記第１の予め決められた数パターンが発生した場合、前記デジタルシーケンスにブレークポイントをマークするステップと、
を備える方法。
【請求項２】
前記ハッシュ関数を実行するステップは、ローリングハッシュ関数手段によって実行される、請求項１記載の方法。
【請求項３】
前記第１の予め決められた数パターンは、ビットパターンである、請求項１記載の方法。
【請求項４】
前記ハッシュ関数を実行するステップは、構造上効率的なｎビットハッシュ関数手段によって実行される、請求項１記載の方法。
【請求項５】
前記構造上効率的なｎビットハッシュ関数は、３２ビットハッシュ関数を備える、請求項４記載の方法。
【請求項６】
前記第１の予め決められた数パターンは、連続ビットシーケンスを備える、請求項１記載の方法。
【請求項７】
前記連続ビットシーケンスは複数の末端ビットを備える、請求項６記載の方法。
【請求項８】
前記複数の末端ビットは１１ビットを備える、請求項７記載の方法。
【請求項９】
前記１１ビットは「０」である、請求項７記載の方法。
【請求項１０】
前記ハッシュ値をモニタする前記ステップに対して閾値制限を決めるステップと、
前記閾値制限が達成された場合、前記モニタステップに対して少なくとも第２の予め決められた数パターンを確立するステップと、
前記第２の予め決められた数パターンが発生した場合、代わりに前記デジタルシーケンスに前記ブレークポイントをマークするステップと、
を更に備える、請求項１記載の方法。
【請求項１１】
前記第２の予め決められた数パターンは、ビットパターンである、請求項１０記載の方法。
【請求項１２】
前記第２の予め決められた数パターンは、前記第１の予め決められた数パターンのサブセットである、請求項１１記載の方法。
【請求項１３】
前記第１の予め決められた数パターンは連続した１１ビットシーケンスを備え、前記第２の予め決められた数パターンは前記１１ビットのうちの１０を備える、請求項１２記載の方法。
【請求項１４】
前記第１の予め決められた数パターンは１１の連続した「０」を備え、前記第２の予め決められた数パターンは１０の連続した「０」を備える、請求項１３記載の方法。
【請求項１５】
前記ハッシュ値をモニタする前記ステップに対して閾値制限を決めるステップと、
前記デジタルシーケンスに前記ブレークポイントをマークする確率を上げるステップと、
を更に備える、請求項１記載の方法。
【請求項１６】
前記デジタルシーケンスに前記ブレークポイントをマークする確率を上げる前記ステップは、少なくとも所望のチャンクサイズの関数である、請求項１５記載の方法。
【請求項１７】
前記デジタルシーケンスに前記ブレークポイントをマークする確率を上げる前記ステップは、少なくとも前記デジタルシーケンスの現在の部分の長さの関数である、請求項１５記載の方法。
【請求項１８】
前記デジタルシーケンスに前記ブレークポイントをマークする確率を上げる前記ステップは、
前記ハッシュ値をモニタする前記ステップに第２の予め決められた数パターンを利用するステップと、
前記第２の予め決められた数パターンが発生した場合、代わりに前記ブレークポイントをマークするステップと、
によって実行される、請求項１５記載の方法。
【請求項１９】
第１のデジタルシーケンスで第１のブレークポイントを決める方法であって、
前記第１のデジタルシーケンスのサブセットグループを決めるステップと、
ハッシュ値で第１の予め決められた数パターンを得るまで、前記第１のデジタルシーケンスの開始位置から始まっている前記第１のデジタルシーケンスの前記サブセットグループにハッシュ関数を実行するステップと、
前記ハッシュ値で前記第１の予め決められた数パターンを得た場合に、前記第１のブレークポイントをマークするステップと、
を備える方法。
【請求項２０】
前記数パターンはビットパターンを備える、請求項１９記載の方法。
【請求項２１】
前記ハッシュ関数を実行するステップは、ローリングハッシュ関数手段によって実行される、請求項１９記載の方法。
【請求項２２】
前記ハッシュ値で前記第１の予め決められた数パターンを再び得るまで、前記第１のブレークポイントから前記第１のデジタルシーケンスのサブセットグループにハッシュ関数を更に実行するステップと、
前記ハッシュ値で前記第１の予め決められた数パターンを再び得た場合に、前記第１のデジタルシーケンスに別のブレークポイントをマークするステップと、
を更に備える、請求項１９記載の方法。
【請求項２３】
前記ハッシュ関数を更に実行するステップは、ローリングハッシュ関数手段によって実行される、請求項２２記載の方法。
【請求項２４】
前記ハッシュ値で第２の予め決められた数パターンを決めるステップと、
確立された閾値制限を達成するまで、前記第１のデジタルシーケンスの前記サブセットグループに前記ハッシュ関数を実行するステップを継続するステップと、
前記ハッシュ値で前記第２の予め決められた数パターンを得た場合、代わりに前記第１のブレークポイントをマークするステップと、
を更に備える、請求項１９記載の方法。
【請求項２５】
前記ハッシュ値で前記第１の予め決められた数パターンを得るまで、第２のデジタルシーケンスの開始位置から始まっている前記サブセットグループにハッシュ関数を実行するステップと、
前記ハッシュ値で前記第１の予め決められた数パターンを得た場合に、前記第２のデジタルシーケンスに第２のブレークポイントをマークするステップと、
前記第１のブレークポイントで予め決められたハッシュ値を前記第２のブレークポイントで予め決められたハッシュ値と比較するステップと、
前記開始位置から前記第１のブレークポイントまでの前記第１のデジタルシーケンスの対応部分を、前記開始位置から前記第２のブレークポイントまでの前記第２のデジタルシーケンスの対応部分と同等視するステップと、
を更に備える、請求項１９記載の方法。
【請求項２６】
コンピュータープログラム製品であって、前記コンピュータープログラム製品は、
デジタルシーケンスが分割されるよう中に含まれるコンピュータ可読コードを有するコンピュータ可使用媒体を備え、前記コンピュータ可使用媒体が、
コンピュータに、少なくとも一部の前記デジタルシーケンスに対してハッシュ関数を実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
コンピュータに、第１の予め決められた数パターンに対する前記ハッシュ関数によって生成されるハッシュ値のモニタを行わせるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記第１の予め決められた数パターンが発生した場合に、コンピュータに、前記デジタルシーケンスへのブレークポイントのマークを行わせるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を備える、コンピュータープログラム製品。
【請求項２７】
コンピュータに前記ハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコード・デバイスは、ローリングハッシュ関数手段によって実行される、請求項２６記載のコンピュータープログラム製品。
【請求項２８】
前記第１の予め決められた数パターンはビットパターンである、請求項２６記載のコンピュータープログラム製品。
【請求項２９】
コンピュータに前記ハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコード・デバイスは、構造上効率的なｎビットハッシュ関数手段によって実行される、請求項２６記載のコンピュータープログラム製品。
【請求項３０】
前記構造上効率的なｎビットハッシュ関数は、３２ビットハッシュ関数を備える、請求項２９記載のコンピュータープログラム製品。
【請求項３１】
前記第１の予め決められた数パターンは、連続ビットシーケンスを備える、請求項２６記載のコンピュータープログラム製品。
【請求項３２】
前記連続ビットシーケンスは複数の末端ビットを備える、請求項３１記載のコンピュータープログラム製品。
【請求項３３】
前記複数の末端ビットは１１ビットを備える、請求項３２記載のコンピュータープログラム製品。
【請求項３４】
前記１１ビットは「０」である、請求項３２記載のコンピュータープログラム製品。
【請求項３５】
コンピュータに、前記ハッシュ値をモニタする前記ステップに対して閾値制限を決めるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記閾値制限が達成された場合に、コンピュータに、前記モニタステップに対して少なくとも第２の予め決められた数パターンを確立するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記第２の予め決められた数パターンが発生した場合に、コンピュータに、代わりに前記デジタルシーケンスに前記ブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を更に備える、請求項２６記載のコンピュータープログラム製品。
【請求項３６】
前記第２の予め決められた数パターンはビットパターンである、請求項３５記載のコンピュータープログラム製品。
【請求項３７】
前記第２の予め決められた数パターンは、前記第１の予め決められた数パターンのサブセットである、請求項３６記載のコンピュータープログラム製品。
【請求項３８】
前記第１の予め決められた数パターンは連続した１１ビットシーケンスを備え、前記第２の予め決められた数パターンは前記１１ビットのうちの１０を備える、請求項３７記載のコンピュータープログラム製品。
【請求項３９】
前記第１の予め決められた数パターンは１１の連続した「０」を備え、前記第２の予め決められた数パターンは１０の「０」を備える、請求項３８記載のコンピュータープログラム製品。
【請求項４０】
コンピュータに、前記ハッシュ値をモニタする前記ステップに対して閾値制限を決めるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
コンピュータに、前記デジタルシーケンスに前記ブレークポイントをマークする確率を上げるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を更に備える、請求項２６記載のコンピュータープログラム製品。
【請求項４１】
コンピュータに、前記デジタルシーケンスに前記ブレークポイントをマークする前記確率を上げるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスは、少なくとも所望のチャンクサイズの関数である、請求項４０記載のコンピュータープログラム製品。
【請求項４２】
コンピュータに、前記デジタルシーケンスに前記ブレークポイントをマークする前記確率を上げるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスは、少なくとも前記デジタルシーケンスの現在の部分の長さの関数である、請求項４０記載のコンピュータープログラム製品。
【請求項４３】
コンピュータに、前記デジタルシーケンスに前記ブレークポイントをマークする前記確率を上げるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスは、
コンピュータに、前記ハッシュ値をモニタする前記ステップに第２の予め決められた数パターンを利用するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記第２の予め決められた数パターンが発生した場合に、コンピュータに、代わりに前記ブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
によって実行される、請求項４０記載のコンピュータープログラム製品。
【請求項４４】
コンピュータープログラム製品であって、前記コンピュータープログラム製品は、
第１のデジタルシーケンスで第１のブレークポイントが決定されるよう中に含まれるコンピュータ可読コードを有するコンピュータ可使用媒体を備え、前記コンピュータ可使用媒体が、
コンピュータに、前記第１のデジタルシーケンスのサブセットグループを決めるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
ハッシュ値で第１の予め決められた数パターンを得るまで、コンピュータに、前記第１のデジタルシーケンスの開始位置から始まっている前記第１のデジタルシーケンスの前記サブセットグループにハッシュ関数を実行するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記ハッシュ値で前記第１の予め決められた数パターンを得た場合に、コンピュータに、前記第１のブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を備える、コンピュータープログラム製品。
【請求項４５】
前記数パターンはビットパターンを備える、請求項４４記載のコンピュータープログラム製品。
【請求項４６】
コンピュータに前記ハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコード・デバイスは、ローリングハッシュ関数手段によって実行される、請求項４４記載のコンピュータープログラム製品。
【請求項４７】
前記ハッシュ値で前記第１の予め決められた数パターンを再び得るまで、コンピュータに、前記第１のブレークポイントから前記第１のデジタルシーケンスのサブセットグループにハッシュ関数を更に実行するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記ハッシュ値で前記第１の予め決められた数パターンを再び得た場合に、コンピュータに、前記第１のデジタルシーケンスに別のブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を更に備える、請求項４４記載のコンピュータープログラム製品。
【請求項４８】
コンピュータに前記ハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコード・デバイスは、ローリングハッシュ関数手段によって実行される、請求項４７記載のコンピュータープログラム製品。
【請求項４９】
コンピュータに、前記ハッシュ値で第２の予め決められた数パターンを決めるステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
確立された閾値制限を達成するまで、コンピュータに、前記第１のデジタルシーケンスの前記サブセットグループに前記ハッシュ関数を実行するステップを継続するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記ハッシュ値で前記第２の予め決められた数パターンを得た場合、コンピュータに、代わりに前記第１のブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を更に備える、請求項４４記載のコンピュータープログラム製品。
【請求項５０】
前記ハッシュ値で前記第１の予め決められた数パターンを得るまで、コンピュータに、第２のデジタルシーケンスの開始位置から始まっている前記サブセットグループにハッシュ関数を実行するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
前記ハッシュ値で前記第１の予め決められた数パターンを得た場合に、コンピュータに、前記第２のデジタルシーケンスに第２のブレークポイントをマークするステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
コンピュータに、前記第１のブレークポイントで予め決められたハッシュ値を前記第２のブレークポイントで予め決められたハッシュ値と比較するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
コンピュータに、前記開始位置から前記第１のブレークポイントまでの前記第１のデジタルシーケンスの対応部分を、前記開始位置から前記第２のブレークポイントまでの前記第２のデジタルシーケンスの対応部分と同等視するステップを実行させるよう構成されたコンピュータ可読プログラムコード・デバイスと、
を更に備える、請求項４４記載のコンピュータープログラム製品。
【請求項５１】
前記デジタルシーケンスに前記ブレークポイントをマークする前記確率を上げるステップは、前記シーケンスの一部のコンテンツ部分の関数である、請求項１５記載の方法。
【請求項５２】
前記ハッシュ関数は、可能な出力値の範囲を均一にカバーしない優先ハッシュ合計を生じるよう選択される、請求項１記載の方法。
【請求項５３】
前記ハッシュ関数は、その実行中にダイナミックに選択されるか或いは変更される、請求項１記載の方法。
【請求項５４】
前記ハッシュ関数は、該ハッシュ関数への入力値として現在のロケーションの相対値または絶対値を含む、請求項１記載の方法。
【発明の詳細な説明】
【０００１】
【著作権に関する通知／許可】
この特許文献の開示の一部は、著作権保護の対象となる材料を含んでよい。著作権所有者は、米国登録商標特許庁の特許ファイルまたはレコードに記載されているような特許の開示の特許文献が誰によってファクシミリ再生されても異論はないが、それ以外においては、いかなるものに対しても全ての著作権の権利を確保する。以下の通知はソフトウェア、データおよび該当する場合には図面を含む以下の説明に適用される。Ｃｏｐｙｒｉｇｈｔ ２０００， Ｕｎｄｏｏ Ｔｅｃｈｎｏｌｏｇｉｅｓ
【０００２】
【発明の背景】
本発明は、一般的に、デジタルシーケンスのブレークポイントを求める「スティッキーバイト」のくくり出しを用いて、データシーケンスを組織化しないで決定するシステムおよび方法の分野に関する。より詳細には、本発明は、最適に近い共通性を一般的に生ずる、データセットをピースに分割する効率的かつ有効な方法に関する。
【０００３】
現代のコンピュータシステムは、総計すると何十億桁ものバイトになる莫大な量のデータを保持している。信じられないことに、この量は年ごとに４倍になる傾向があり、コンピュータ大容量記憶アーキテクチャの最もみごとな進歩でさえも追いつくことができない。
【０００４】
大部分のコンピュータ大容量記憶システムで保持されるデータは、以下の興味深い特徴を有すると見られている：１）それはほとんど全くランダムでなく、事実上非常に冗長である；２）このデータに特有のシーケンスの数は、実際にデータが占める記憶空間のなかで非常に低い割合となる。３）かなりの量の労力がこの量のデータの管理を試みるのに必要とされ、その多くが冗長の除去（すなわち複製ファイル、ファイルの古いバージョン、パージログ、アーカイブ処理等）の識別に関係している。４）大量の資本的資源が、不必要なコピーを作成し、それらコピーを局所型媒体に保存することなどに捧げられる。
【０００５】
冗長コピーくくり出しシステムは、別な方法では何桁も必要とされる記憶量の数を減らすであろう。しかしながら、大容量データをそれらの共通のシーケンスにくくり出すシステムでは、シーケンスを求める方法を使用しなければならない。１つのデータシーケンスを別のシーケンスと比較することを試みる従来の方法は、一般的に、計算の極度な複雑性を被ることになり、したがって、これらの方法は比較的小さいデータセットをくくり出すことにのみ使用可能である。より大きなデータセットのくくり出しは、一般的に、任意の固定サイズを用いるといった単純な方法を用いて成されるだけである。これらの方法は、多くの環境下で十分なくくり出しができず、大きいデータセットの効率的なくくり出しは、コンピュータ科学分野において今まで長きにわたり持続的に厄介な問題であった。
【０００６】
【発明の概要】
共通シーケンスを識別できるように、デジタルシーケンスのブレークポイントを求める「スティッキーバイト」のくくり出しを用いて、データシーケンスを組織化しないで決定するシステムおよび方法が、本願に開示されている。スティッキーバイトのくくり出しは、最適に近い共通性を一般的に生ずる、データセットをピースに分割する効率的な方法を提供する。本願で開示されるように、これは、ハッシュ値の定期的なリセット、或いは好適な実施例においてはローリングハッシュ合計、を有するハッシュ関数を用いることによって実現されてよい。さらに、本願で開示されている特に典型的な実施例において、閾値関数は、デジタルまたは数のシーケンス（例えばデータのシーケンス）に区分を決定的に設定するのに利用される。ローリングハッシュおよび閾値関数の双方は、最小限の計算が必要とされるようできている。この低オーバーヘッドは、くくり出しエンジンまたは全データセットにわたる後続の同期を好む他のアプリケーションに対する表現のデータシーケンスを速やかに分割することを可能にする。
【０００７】
本願で開示されるシステムおよび方法の重要な利点の内の一つは、計算が良好に機能するための（従来のくくり出しているシステムのような）通信も比較も必要としないことである。これは分散環境において特に当てはまり、従来のシステムが１つのシーケンスを別のシーケンスと比較するのに通信を必要とするのに対して、本発明のシステムおよび方法は、次に考えられるシーケンスだけを用いて隔離状態で実行可能である。
【０００８】
オペレーションにおいて、コンピュータ間の通信の必要がなく、またファイルのデータコンテンツに関係なく、多重関連および無関連のコンピュータシステム上で共通要素を見つけることができるように、本発明のシステムおよび方法は、数のシーケンス（例えばファイルのバイト）を分割する完全自動手段を提供する。概括的にいえば、共通シーケンスを、それらシーケンスを見つけるオペレーションにおける検索、比較、通信、または他の処理要素との調整の必要なく見つけることができるように、数要素のシーケンス（すなわちバイトシーケンス）を分割する完全自動手段を含むデータ処理システムに関するシステムおよび方法が、本願に開示されている。本発明のシステムおよび方法は、パーティション間で共通性を最適化するのに求められるタイプおよびサイズのシーケンスを生ずる分布を有する数シーケンスを分割する「スティッキーバイト」ポイントを生成する。
【０００９】
添付の図と共に取り入れられた好適な実施例の以下の説明を参照することによって、本発明の上述ならびに他の特徴および目的、またそれらを達成する方法がより明瞭になり、本発明は最大限理解されるであろう。
【００１０】
【代表的な実施例の説明】
本発明は、インターネットのような公衆通信回線を使っている企業コンピューティングシステムのような分散コンピューティング環境に関して、図示され説明される。しかしながら、本発明の重要な特徴は、特定のアプリケーションのニーズに合うよう上方および下方に容易に基準化されるということである。したがって、相反するものに対して指示がない限り、本発明は従来のＬＡＮシステムのような小さなネットワーク環境と同様に相当に大きくかつ複雑なネットワーク環境にも適用できる。
【００１１】
図１に関して、本発明はネットワーク１０上の新規のデータ記憶システムとともに利用できる。この図において、典型的なインターネットワーク環境１０は、多重広域ネットワーク（「ＷＡＮ」）１４とローカルエリアネットワーク（「ＬＡＮ」）１６間の論理および物理接続によって形成されるグロ―バルインターネットワークを備えるインターネットを含んでよい。インターネットバックボーン１２は、データトラフィックのバルクを運ぶメインラインおよびルーターを表す。バックボーン１２は、例えばＧＴＥ、ＭＣＩ、Ｓｐｒｉｎｔ、ＵＵＮｅｔおよびＡｍｅｒｉｃａ Ｏｎｌｉｎｅといった主要なインターネットサービスプロバイダ（「ＩＳＰ」）によって管理されるシステムの最大ネットワークによって形成される。単独接続ラインはインターネットバックボーン１２へのＷＡＮ １４およびＬＡＮ １６の接続を好都合に図示するのに用いられているが、現実には、複数パスでルート可能な物理接続が多重ＷＡＮ １４とＬＡＮ １６間に存在することは理解されるべきである。これは、単一または多重故障ポイントに直面した際にインターネットワーク１０を強力にする。
【００１２】
「ネットワーク」は汎用のシステムを備え、通常、ノード１８で作動するプロセス間の論理接続を可能にする物理接続を切り替える。ネットワークによって実現される物理接続は、一般的に、ネットワークを使っているプロセス間で確立される論理接続から独立している。このように、ファイル転送、メール転送などに及ぶ異種のプロセスセットが、同じ物理的なネットワークを使うことができる。逆に言えば、ネットワークは、ネットワークを用いて論理的に接続されているプロセスには見えない異質の物理的なネットワーク技術のセットから形成可能である。ネットワークによって実現されるプロセス間の論理接続が物理接続から独立しているので、インターネットワークは長距離にわたる仮想的に無制限のノード数に容易に基準化される。
【００１３】
対照的に、システムバス、周辺コンポーネント相互接続（「ＰＣＩ」）バス、インテリジェントドライブエレクトロニクス（「ＩＤＥ」）バス、小型コンピューターシステムインターフェース（「ＳＣＳＩ」）バスなどといった内部データ経路は、コンピュータシステム内で特殊目的接続を実現する物理接続を画成する。これらの接続は、プロセス間の論理接続に対してフィジカルデバイス間の物理接続を実現する。これらの物理接続は、コンポーネント、該接続に結合できる限定された数のデバイス、および該接続を介して接続できる条件付きフォーマットのデバイス間の限られた距離によって特徴づけられている。
【００１４】
本発明の特定のインプリメンテーションで、記憶装置はノード１８に配置されてよい。あらゆるノード１８のストレージが、一つのハードディスクを備えてよく、或いは一つの論理ボリュームとして構成される多重ハードディスクを有する従来のＲＡＩＤデバイスのような管理された記憶システムを備えてもよい。重要なこととして、本発明は、ノード内で行なうのとは対照的に、ノードの全域にわたって冗長オペレーションを管理するので、任意のノード内のストレージの特定の構成はあまり重要ではない。
【００１５】
オプションとして、ノード１８のうちの１つ以上が、分散型かつ共同的なやり方でノード１８にわたってデータストレージを管理するストレージ割付け管理（「ＳＡＭ」）プロセスを実現してもよい。ＳＡＭプロセスは、全体として、システムを集中制御しないか或いはほとんどしないように機能するのが望ましい。ＳＡＭプロセスは、ノード１８全域にわたってデータ分布を提供し、ＲＡＩＤ記憶サブシステムで見つけられるパラダイムと同様の方法で、ネットワークノード１８全域にわたって故障を許容するやり方でリカバリを実現する。
【００１６】
しかしながら、ＳＡＭプロセスは、一つのノード内または一つのコンピュータ内ではなくノードの全域にわたって機能するので、該プロセスは従来のＲＡＩＤシステムよりも大きな故障許容とストレージ効率レベルを可能にする。たとえば、ＳＡＭプロセスは、ネットワークノード１８、ＬＡＮ １６またはＷＡＮ １４が利用できなくなった場合でさえも回復可能である。さらに、一部のインターネットバックボーン１２が故障または輻輳によって利用できなくなった場合でさえも、ＳＡＭプロセスはアクセス可能なままであるノード１８で分配されるデータを用いて回復可能である。このように、本発明はインターネットワークの強力な性質に影響を及ぼし、先例のない可用性、信頼性、障害の許容範囲および堅固性を提供する。
【００１７】
図２に関して、本発明が実現される典型的なネットワークコンピューティング環境のより詳細な概念図が表される。先行図のインターネットワーク１０（またはこの図でのインターネット１１８）は、スーパーコンピュータ即ちデータセンター１０４からハンドヘルド即ちペンベースのデバイス１１４の範囲に及ぶ、異質のコンピューティング装置およびメカニズム１０２のセットの相互接続ネットワーク１００を可能にする。このようなデバイスは異なるデータストレージのニーズを有しているが、それらはネットワーク１００を介してデータを検索する能力を共有しており、それら自身のリソース内のデータに作用する。ＩＢＭ互換機デバイス１０８、マッキントッシュデバイス１１０およびラップトップコンピューター１１２といったパーソナルコンピュータまたはワークステーションクラスデバイスと同様にメインフレームコンピュータ（例えばＶＡＸステーション１０６およびＩＢＭ ＡＳ／４００ステーション１１６）を含む異種のコンピューティング装置１０２は、インターネットワーク１０およびネットワーク１００を介して容易に相互接続する。図示されてはいないが、移動式および他のワイヤレスデバイスをインターネットワーク１０に結合してもよい。
【００１８】
インターネットベースのネットワーク１２０は一組の論理接続を備えており、その幾つかはインターネット１１８を介して複数の内部ネットワーク１２２間に作られる。概念的に、インターネットベースのネットワーク１２０はＷＡＮ １４（図１）と同種であり、それは地理的に遠いノード間での論理接続を可能にしている。インターネットベースのネットワーク１２０は、インターネット１１８、または専用回線、Ｆｉｂｒｅ Ｃｈａｎｎｅｌなどを含む他の公共および私用のＷＡＮ技術を用いて実現されてもよい。
【００１９】
同様に、内部ネットワーク１２２は概念的にＬＡＮ １６（図１）と同種であり、それはＷＡＮ １４よりも限られたスタンスにわたって論理接続を可能にしている。内部ネットワーク１２２は、 Ｅｔｈｅｒｎｅｔ、Ｆｉｂｅｒ Ｄｉｓｔｒｉｂｕｔｅｄ Ｄａｔａ Ｉｎｔｅｒｆａｃｅ（「ＦＤＤＩ」）、Ｔｏｋｅｎ Ｒｉｎｇ、ＡｐｐｌｅＴａｌｋ、Ｆｉｂｒｅ Ｃｈａｎｎｅｌ、などを含むさまざまなＬＡＮ技術を用いて実現されてもよい。
【００２０】
各内部ネットワーク１２２は、独立したノード（ＲＡＩＮ）エレメント１２４の一つ以上の冗長配列を接続し、ＲＡＩＮノード１８（図１）を実現する。各ＲＡＩＮエレメント１２４は、プロセッサ、メモリおよび一つ以上の大容量記憶装置（例えばハードディスク）を備える。ＲＡＩＮエレメント１２４はまた、従来のＩＤＥ またはＳＣＳＩコントローラであってよく、ＲＡＩＤコントローラのような管理コントローラであってもよいハードディスクコントローラを含む。ＲＡＩＮエレメント１２４は、物理的に分散してよく、冷却および電力といったリソースを共有している一つ以上のラックで同じ位置に配置されてもよい。各ノード１８（図１）は他のノード１８から独立しており、１つのノード１８の故障または不稼働が他のノード１８の可用性に影響を及ぼさず、１つのノード１８に格納されているデータは他のノード１８に格納されているデータから復元可能である。
【００２１】
特定の典型的なインプリメンテーションにおいて、ＲＡＩＮエレメント１２４は、ＰＣＩバスを支持するマザーボードおよび従来のＡＴまたはＡＴＸケースに収容される２５６メガバイトのランダムアクセスメモリー（「ＲＡＭ」）上に取り付けられるインテルベースのマイクロプロセッサーのような商品コンポーネントを用いたコンピュータを備えてもよい。ＳＣＳＩまたはＩＤＥコントローラは、マザーボード上でおよび／またはＰＣＩバスに接続された拡張カードによって実現されてよい。コントローラがマザーボード上のみで実現される場合、ＰＣＩ拡張バスがオプションとして使われてもよい。特定のインプリメンテーションにおいて、マザーボードは、各ＲＡＩＮエレメント１２４が最高４つ以上のＥＩＤＥハードディスクを含むよう、２つのマスタリングＥＩＤＥチャネルおよび２つの付加マスタリングＥＩＤＥチャネルを実現するのに用いられるＰＣＩ拡張カードを実現できる。特定のインプリメンテーションにおいて、各ハードディスクは、ＲＡＩＮエレメントにつき３２０ギガバイト以上の総記憶容量の８０ギガバイトハードディスクを備えてよい。ＲＡＩＮエレメント１２４内のハードディスク容量および構成は、特定のアプリケーションのニーズを満たすよう容易に増大または低減できる。外被もまた、電源および冷却デバイス（図示せず）といった支持メカニズムを収容する。
【００２２】
各ＲＡＩＮエレメント１２４は、オペレーティングシステムを実行する。特定のインプリメンテーションにおいて、ＵＮＩＸまたはＬｉｎｕｘのようなＵｎｉｘバリアントオペレーティングシステムが、使われてよい。しかしながら、 ＤＯＳ、マイクロソフトウインドウズ、アップルマッキントッシュＯＳ、ＯＳ／２、マイクロソフトウインドウズＮＴなどを含む他のオペレーティングシステムを、パフォーマンスにおける予測可能な変更を行なうことで同等に置換え可能であることが企図される。選択されたオペレーティングシステムは、アプリケーションソフトウェアおよびプロセスを実行するプラットホームを形成し、ハードディスクコントローラを介して大容量記憶域にアクセスするファイルシステムを実現する。様々なアプリケーションソフトウェアおよびプロセスが各ＲＡＩＮエレメント１２４上で実現され、適切なネットワークプロトコル（例えばユーザーデータグラムプロトコル（「ＵＤＰ」）、伝送制御プロトコル（ＴＣＰ）、インターネットプロトコル（ＩＰ）など）を用いたネットワークインターフェースを介して、ネットワークの接続性を提供できる。
【００２３】
図３に関しては、ロジックフローチャートが、本発明のハッシュファイルシステムにコンピュータファイルをエントリするステップを表すために示されており、ファイルのハッシュ値が、セットまたはデータベースに予め維持されるファイルのハッシュ値と照合される。いかなるデジタルシーケンスもまた、全く同様に本発明のハッシュファイルシステムに入力できるが、入力されるデジタルシーケンスがコンピュータファイルから成る本例は教訓的である。
【００２４】
プロセス２００は、コンピューターファイルデータ２０２（例えば「ファイルＡ」）を本発明のハッシュファイルシステム（「ＨＦ」）に入力することから始まり、ハッシュ関数がステップ２０４で実行される。次いで、ファイルＡのハッシュを表すデータ２０６が判断ステップ２０８でハッシュファイル値を含むセットのコンテンツと比較される。データ２０６が既にセットにある場合、ファイルのハッシュ値はステップ２１０でハッシュレシピに加えられる。このハッシュレシピは、データ、並びにシステムに入力されたコンピューターファイルデータのクラスに従って、ファイル、ディレクトリ、ボリュームまたは全体システムを復元するのに必要な関連する構成から成る。ハッシュ値を含み、データに対応しているセット２１２のコンテンツは、判断ステップ２０８の比較演算のために既存のハッシュ値２１４の形で提供される。一方、ファイルＡのハッシュ値がその時点でセットに存在しない場合、ファイルは、ステップ２１６で（以下でより完全に説明されるように）ハッシュピースに分割される。
【００２５】
図４に関しては、更なるロジックフローチャートが、デジタルシーケンス（例えばファイルまたは他のデータシーケンス）をブレークアップしてハッシュピースにするプロセス３００でのステップを表すために提供される。このプロセス３００は、多数のデータピースと同様にそれに対応している確率的に固有のハッシュ値を各ピースに対して最終的に生成することになる。
【００２６】
ファイルデータ３０２は、システムの他のピースとの共通性あるいは後にステップ３０４で共通していることが明らかになるピースの可能性に基づいたピースに分割される。ファイルデータ３０２に関するステップ３０４のオペレーションの結果は、代表的な例において、Ａ１〜Ａ５と名づけられた４つのファイルピース３０６を生成する。
【００２７】
ファイルピース３０６の各々は、次いで、Ａ１〜Ａ５のピース３０６の各々に確率的に固有の数が割り当てられるよう、個々のハッシュ関数オペレーションを通して各々を配置することによってステップ３０８で操作される。ステップ３０８のオペレーションの結果、ピース３０６（Ａ１〜Ａ５）の各々は、関連づけられた、確率的に固有のハッシュ値３１０（それぞれＡ１ハッシュ〜Ａ５ハッシュとして示される）を有することになる。ステップ３０４のファイル分割プロセスは、ここで開示されている固有の「スティッキーバイト」オペレーションとともに、更に詳細に以下で説明される。
【００２８】
更に図５に関しては、別のロジックフローチャートが、ファイルの各ピース３０６のハッシュ値３１０を、セット２１２で維持されている既存のハッシュ値２１４と比較するプロセス４００を表すために示される。特に、ステップ４０２で、ファイルの各ピース３０６のハッシュ値３１０は既存のハッシュ値２１４および新しいハッシュ値４０８と比較され、対応する新しいデータピース４０６がセット２１２に加えられる。このように、セット２１２に予め存在していないハッシュ値４０８が、それらに関連づけられたデータピース４０６と共に加えられる。プロセス４００はまた、全てのファイルピースに対する一つのハッシュ値が様々なピース３０６のハッシュ値３１０と同値であることを示しているレコード４０４を生成することになる。
【００２９】
更に図６は、ファイルハッシュまたはディレクトリリストハッシュ値を既存のディレクトリリストハッシュ値と比較し、新しいファイルまたはディレクトリリストハッシュ値をセットディレクトリリストに加えるプロセス５００を図示している別のロジックフローチャートを示す。プロセス５００は、ファイル名、ファイルメタデータ（例えば日付、時間、ファイルの長さ、ファイルタイプ等）およびディレクトリの各項目のファイルのハッシュ値の累積リストを備える記憶データ５０２上で機能する。ステップ５０４で、ハッシュ関数はディレクトリリストのコンテンツに実行される。判断ステップ５０６は、ディレクトリリストのハッシュ値が既存のハッシュ値２１４のセット２１２であるかどうかを判断するよう機能する。判断が肯定である場合、プロセス５００は、別のファイルハッシュまたはディレクトリリストハッシュをディレクトリリストに加えるために戻る。これに対して、ディレクトリリストのハッシュ値がセット２１２にすでにない場合、ディレクトリリストのハッシュ値およびデータはステップ５０８でセット２１２に加えられる。
【００３０】
更に図７に関しては、代表的なコンピュータファイル（すなわち「ファイルＡ」）のピース３０６とそれらに対応するハッシュ値３１０の比較６００が、典型的なファイルの特定ピースの編集の前後双方で示される。この例では、レコード４０４はファイルＡ１〜Ａ５のピースの各々のハッシュ値３１０と同様にファイルＡのハッシュ値を含む。ファイルＡの代表的な編集または変更は、３０６ＡのファイルピースのピースＡ２（Ａ２−ｂによって表される）のデータの変化と共にハッシュ値３１０Ａのハッシュ値Ａ２−ｂの対応する変化を生成可能である。編集されたファイルピースは、ファイルＡの修正ハッシュ値およびピースＡ２−ｂの修正ハッシュ値を含む更新済みレコード４０４Ａを生成する。
【００３１】
更に図８に関しては、本発明のシステムおよび方法によって導き出される複合データ（例えば複合データ７０２および７０４）は明示的に表されるデータ７０６と実質的に同じものであるが、「レシピ」すなわち式によって作成されるという事実を図示している概念図７００が示される。図示される例において、このレシピは、対応するハッシュ７０８によって表されるデータの連結またはハッシュによって表されるデータを用いた関数の結果を含む。データブロック７０６は示されるように可変長数量であってよく、ハッシュ値７０８はそれに関連づけられたデータブロックから導き出される。既に述べたように、ハッシュ値７０８は対応するデータピースの確率的に固有のＩＤであるが、全く固有のＩＤがその代わりに使われるか、或いは確率的に固有のＩＤと混在させることもできる。複合データ７０２、７０４はまた、多くのレベルが深い他の複合データを参照でき、一方、複合データのハッシュ値７０８はレシピが生成するデータの値またはレシピ自体のハッシュ値から導き出されることが可能であることもまた注目されるべきである。
【００３２】
更に図９に関しては、ハッシュファイルシステムおよび方法がデータ８０２を編成し、それらが表すデータへのポインタとしてハッシュ値８０６を使用することによって冗長シーケンスの再利用を最適化するのにどのように利用できるかを別の概念図８００で示していて、データ８０２は、明確なバイトシーケンス８０８（原子データ）か或いはシーケンスのグループ（コンポジット）８０４として表されてよい。
【００３３】
図８００は、レシピおよびあらゆるレベルで再利用されるデータの強大な共通性を図示する。本発明のハッシュファイルシステムの基本構成は、本質的に、ハッシュ値８０６が従来のポインタの代わりに使われる「ツリー」または「ブッシュ」である。ハッシュ値８０６はレシピで使われて、データまたはそれ自体がレシピでありえる別のハッシュ値を示している。したがって、本質において、レシピは他のレシピを示し、他のレシピはさらに他のレシピを示し、最終的に幾つかの特定データを示し、その特定データ自体は更に多くのデータを示す他のレシピを示してよく、最後にはデータだけにかかる。
【００３４】
更に図１０に関しては、典型的な１６０ビットのハッシュ値９０２のハッシュファイルシステムアドレス変換機能の実例となる簡略図９００が示される。ハッシュ値９０２は図示されるように前部９０４および後部９０６を備えるデータ構造を含み、図９００は対応するデータを含むシステムにおいて特定のノードのロケーションに行くためにハッシュ値９０２の使用を可能にするよう用いられる特定の「０（１）」オペレーションを図示する。
【００３５】
図９００は、ハッシュ値９０２のデータ構造の前部９０４がストライプ識別（「ＩＤ」）９０８へのハッシュ・プレフィックスを示すのにどのように用いられることができるか、また、次に、ストライプＩＤをＩＰアドレスにマップし、ＩＤクラスをＩＰアドレス９１０にマップするのにどのように利用されるかを図示する。この例では、「Ｓ２」はインデックスノード３７ ９１２のストライプ２を示す。ノード３７のインデックス・ストライプ９１２は、次いで、リファレンス番号９１４によって示されるデータノード７３のストライプ８８を示す。次いで、オペレーションにおいて、ハッシュ値９０２自体がシステムのどのノードが関連したデータを含むのかを示すのに使用でき、ハッシュ値９０２の別の部分はどのデータストライプがその特定のノードにあるのかを示すのに使用でき、ハッシュ値９０２の更に別の部分はそのストライプ内のどこにデータが存在するのかを示すのに使用できる。この３ステッププロセスを通して、ハッシュ値９０２によって表されるデータがシステムに既に存在するかどうかを迅速に判断することができる。
【００３６】
更に図１１に関しては、本発明のシステムおよび方法で使用されるインデックス・ストライプ分割機能１０００の簡略的な典型図が示される。この図において、典型的な機能１０００は、ストライプ１００２（Ｓ２）を１つのストライプが充分にいっぱいになるように２つのストライプ１００４（Ｓ２）と１００６（Ｓ７）に効果的に分割するのに使用可能であることが示されている。この例では、奇数のエントリはストライプ１００６（Ｓ７）に動かされ、一方偶数のエントリはストライプ１００４に残る。この機能１０００は、システム全体のサイズが大きくなり複雑さが増すにつれて、ストライプエントリをどう処理することができるかを示す１つの例である。
【００３７】
更に図１２に関しては、本発明のシステムおよび方法の全体機能の簡略図１１００は、例えば、Ｄａｙ１に多数のプログラムおよびドキュメントファイル１１０２Ａおよび１１０４Ａを有する代表的な家庭用コンピュータのデータのバックアップに用いられているのを示しており、プログラムファイル１１０２ＢはＤａｙ２に同じものを残し、一方、ドキュメントファイル１１０４Ｂのうちの１つはＤａｙ２で編集され（Ｙ．ｄｏｃ）、第３のドキュメントファイル（Ｚ．ｄｏｃ）が加えられる。
【００３８】
図１１００は、コンピュータファイルシステムがピースに分けられ、次いでピースからオリジナルデータを復元するためにグロ―バルデータ保護回路（「ｇＤＰＮ」）上に一連のレシピとしてリストされることができる方法の詳細を示す。この非常に小さいコンピュータシステムは、「スナップショット」の形で「Ｄａｙ１」で、次いでその後「Ｄａｙ２」で示される。「Ｄａｙ１」上で「ｐｒｏｇｒａｍ ｆｉｌｅｓ Ｈ５」および「ｍｙ ｄｏｃｕｍｅｎｔｓ Ｈ６」が数字１１０６で図示され、前者はレシピ１１０８によって表されており、第１の実行可能ファイルはハッシュ値Ｈ１ １１１４で表され、第２の実行可能ファイルはハッシュ値Ｈ２ １１１２で表されている。ドキュメントファイルはハッシュ値Ｈ６ １１１０によって表され、第１のドキュメントはハッシュ値Ｈ３ １１１８で表され、第２のドキュメントファイルはハッシュ値Ｈ４ １１１６によって表されている。その後、「Ｄａｙ２」で数字１１２０によって示される「ｐｒｏｇｒａｍ ｆｉｌｅｓ Ｈ５」および「ｍｙ ｄｏｃｕｍｅｎｔｓ Ｈ１０」は、「ｐｒｏｇｒａｍ ｆｉｌｅｓ Ｈ５」は変更されていないが、「ｍｙ ｄｏｃｕｍｅｎｔ Ｈ１０」は変更されたことを示している。数字１１２２によって示されるＨ１０は、「Ｘ．ｄｏｃ」が依然としてハッシュ値Ｈ３ １１１８で表されていることを示し、一方「Ｙ．ｄｏｃ」は今では数字１１２４においてハッシュ値Ｈ８で表されていることを示している。新しいドキュメントファイル「Ｚ．ｄｏｃ」は、数字１１２６においてハッシュ値Ｈ９で表される。
【００３９】
この例では、Ｄａｙ２で幾つかのファイルが変更され、他は変更されていないことがわかる。変更されたファイルにおいて、それらのうちの幾つかのピースは変更されておらず、他のピースは変更されている。本発明のハッシュファイルシステムの使用を通して、コンピュータシステムの「スナップショット」がＤａｙ１で作成可能であり（次に存在できるようコンピュータファイルの再生に必要なレシピを生成する）、次いでＤａｙ２で以前の日のレシピの幾つかの再使用、他のレシピの再定式化、ならびに新規のレシピの追加によって、その時点でのシステムが記述される。このように、コンピュータシステムを共に構成するファイルは、スナップショットがとられたＤａｙ１およびＤａｙ２のいかなる時点でもその全体において、並びにいかなる後続日にとられたスナップショットからでも、再現可能である。したがって、本発明のハッシュファイルシステムに委ねられたコンピュータファイルのいかなるバージョンも、初めに委ねられた後であればいつでも、システムから検索できる。
【００４０】
更に図１３に関しては、多数の「スティッキーバイト」１２０４によってマークされる特定のドキュメントファイルの様々なピースの比較１２００が、編集前（Ｄａｙ１ １２０２Ａ）および編集後（Ｄａｙ２ １２０２Ｂ）の双方で示されており、それによってピースのうちの一つが変更され、他のピースは同じままである。
【００４１】
たとえば、Ｄａｙ１に、ファイル１２０２Ａは、可変長ピース１２０６（１．１）、１２０８（１．２）、１２１０（２．１）、１２１２（２．）、１２１４（２．３）および１２１６（３．１）を備える。Ｄａｙ２では、ピース１２０６、１２０８、１２１０、１２１４および１２１６は同じままであり（したがって同じハッシュ値を有する）、一方、ピース１２１２は編集されてピース１２１２Ａを生成する（したがって異なるハッシュ値を有する）。
【００４２】
更に図１４を参照すると、本発明のインプリメンテーションで使用できる代表的なスティッキーバイト（またはスティッキーポイント）くくり出しプロセス１３００が示されている。プロセス１３００は、ステップ１３０２でハッシュ値を「０」にセットして、プロセスを初期化することから始まる。
【００４３】
入力コンピュータファイルのコンテンツを備えるデータオブジェクト１３０４は、入力ファイルソースからのキャラクタを読みとるステップ１３０６で実行される。ステップ１３０８において、ステップ１３０６で読みとられたキャラクタは、３２ビット値のアレイ（このサイズのアレイは、例として記載されているだけである）にインデックスを付けるために利用される。その後、ステップ１３１０で、ステップ１３０８で見つかったインデックスを付けられた３２ビット値は、現在の３２ビットハッシュ値に排他的ＯＲ化（「ＸＯＲ化」）される。
【００４４】
判断ステップ１３１２で、予め決められたパターンが見つかった場合（例えば、最下位ビット「０」の選択された数）、スティッキーバイトはその時点でステップ１３１４において入力ファイルに配置される。一方、予め決められたパターンが判断ステップ１３１２で見つからなかった場合、判断ステップ１３１６において、入力ファイルでの予め決められたキャラクタの閾値数（以下でより完全に説明するように、プロセス１３００のローリングハッシュ関数によって操作されている）を超えたかどうかによって判断が下される。予め決められた閾値数を超えた場合、判断ステップ１３１２で検索される予め決められたパターン（例えば最下位ビット「０」のより小さい選択数）の幾つかのサブセット数が見つかったかどうかを確かめるために、プロセス１３００は判断ステップ１３１８に進む。そうであった場合、スティッキーバイトはステップ１３１４に置かれる。
【００４５】
あるいは、判断ステップ１３１６において予め決められた閾値を超えなかった場合、プロセス１３００は、既存の３２ビットハッシュ値を１ビットポジションにわたってシフトさせる（「右」か「左」に）ステップ１３２０に進む。判断ステップ１３２２において、プロセス１３００が作用するさらに別のキャラクタが存在する場合、入力ファイルソースの次のキャラクタはステップ１３０６で読みとられる。判断ステップ１３１８で予め決められたパターンのサブセットが見つからなかった場合、あるいは、ステップ１３１４でスティッキーバイトが配置された場合、上述したように、プロセスはステップ１３２０に進む。
【００４６】
データ・スティッキーバイト（または「スティッキーポイント」）は、共通ブロック要素がコンピュータ間で通信する必要なく複数の関連したおよび無関連のコンピュータで見つかるようコンピュータファイルをサブ分割するユニークな完全自動化の方法である。スティッキーポイントを見つける手段は、本質的に完全に数学的であり、ファイルのデータコンテンツに関係なく均等かつ適切に実行される。ハッシュファイルシステムの使用を通して、全てのデータオブジェクトはインデックスを付けられ、格納され、例えば、限定されるものではないが、ＭＤ４、ＭＤ５、ＳＨＡまたはＳＨＡ−１といった業界標準チェックサムを用いて検索されてよい。オペレーションにおいて、２つのファイルが同じチェックサムを有する場合、それらが同一ファイルであることは非常に可能性が高いと考えられ得る。本願で開示されているシステムおよび方法を用いると、データスティッキーポイントは、標準的な数理分布およびターゲットサイズが僅かな割合である標準偏差で生成できる。
【００４７】
データスティッキーポイントは、統計学的には稀なｎバイトの配列である。この場合、現在の３２ビットオリエンテッドマイクロプロセッサ技術でのインプリメンテーションにおいて容易であるという理由から、例においては３２ビットが使われている。ハッシュファイルシステムを実行するために利用されるハッシュ関数は適度に複雑な計算を必要とするが、それは現代コンピュータシステムの機能の範囲内では問題ない。ハッシュ関数は本質的に確率的であり、いかなるハッシュ関数でも２つの異なるデータオブジェクトに対して同じ結果をもたらすことができる。しかしながら、本願に開示されているシステムおよび方法は、従来のコンピュータハードウェアオペレーションでは容認されているエラー率よりはるかに低い、信頼できる使用のために許容できるレベル（すなわち何兆分の１の可能性）まで衝突の確率を減らす、周知でありかつ研究されたハッシュ関数を用いて、この問題を緩和している。
【００４８】
本発明のスティッキーバイトくくり出しシステムをより完全に説明するために、以下の定義を付随させる。
【００４９】
ローリングハッシュ
ローリングハッシュ関数は、標準ハッシュ関数の本質的な性質を維持しているが、その入力値の限られたメモリを有するようにデザインされている。具体的には、ハッシュ関数は以下の特性を有する：
１．固定長または可変長ウィンドウ（シーケンスの長さ）を有する；
２．同一のデータウィンドウを与えられた同一値を生じる；
すなわち、決定性がある。理想的には、生成されたハッシュ合計は、正当な値の全ての範囲に均一にまたがっている；
３．そのハッシュ合計は、ウィンドウの前か或いは後のデータに影響されない。
【００５０】
本発明の特定のインプリメンテーションで、３２ビットローリングハッシュ関数が使われてよい。その一般的なオペレーションは、以下の通りである： １）既存の３２ビットハッシュ値を１ビットにわたって（左か右に）シフトさせる； ２）入力ファイルソースからのキャラクタを読みとる； ３）そのキャラクタを用いて、３２ビット値のアレイにインデックスを付ける；および ４）インデックス付き３２ビット値を現在の３２ビットハッシュにＸＯＲ化する。次いで、オペレーションを繰り返す。
【００５１】
ローリングハッシュ値は次いで３２ビット値のままであり、全ての３２ビットがＸＯＲ演算の影響を受ける。シフト段階において、ビットのうちの一つが、残りの３１ビットから離れてローリングハッシュ「ウィンドウ」から移動し、残された３１ビットは１つの場所にわたって移動するが、それ以外に変化はない。この結果、ウィンドウは１つのユニットにわたって移動する。
【００５２】
少数のビットのみが、例えば最下位「０」の幾つかの数といった多くのアプリケーションで一般に使われるので、更なる計算の労力が、「スティッキーバイト」の決定において要求されはしないが、６４ビット（または他のサイズ）のローリングハッシュが使われてよい点に留意する必要がある。 利用される関数が適切に分散された数を生じると仮定した場合、３２のビット数に対して、ゼロの最大数はもちろん３２であり、平均して４０億のキャラクタ毎に一回のみ発生する。４０億キャラクタはおよそ４ギガバイトのデータであり、大きな「チャンク」である。６４ビットハッシュ値を用いることは更に大きなチャンクサイズを生成する際の助けになるが、本願に開示されている本発明の特定のインプリメンテーションは約２Ｋのチャンクサイズを使用しているので、３２ビットローリングハッシュの全範囲を必要とすることはほとんどない。
【００５３】
以下のＣ言語例について考えてみる。ここで、「ｆ」はバイトアレイであり、「ｉ」はそのアレイへのインデックスであり、「ｈａｓｈ」は計算されるハッシュ合計である。単純なローリングハッシュは以下のように書くことができる：
2004514968.tif 000002
【００５４】
このハッシュは、大きくランダム化された整数値を生成する、入力バイト値（０〜２５５）によってインデックス付けされる第２のアレイ「スクランブル」を含むことによって、改善可能である：
2004514968.tif 000003
【００５５】
このローリングハッシュ関数の例は、３２ビット値の範囲にわたってかなり均一な数をもたらす。
【００５６】
閾値関数
閾値関数は、或る値が任意のレベルより上か下かを求める計算を実行する。
このアクションは不連続な結果を生じ、一部の値は閾値の上に、また他の値は閾値の下になる。閾値関数は、オプションとして、その入力値に対して或る変換を実行することもできる。例として：
2004514968.tif 000004
あるいは：
2004514968.tif 000005
【００５７】
スティッキーバイトのくくり出しに関する本発明のシステムおよび方法は、有利にデータセットを共通性を助長するシーケンスに分割する。続いての例は、現代の３２ビットマイクロプロセッサで特に適切に実行できる閾値関数と共に３２ビットローリングハッシュを利用した、好適なインプリメンテーションの実例である。
【００５８】
３２ビットのローリングハッシュは、分割される入力シーケンスとしてバイトアレイ「ｆ」を用いて生成される。ここで：
１．ｆ［ｉ］ は、「ｆ」に含まれるバイトシーケンスのｉ番目のバイトである；
２．「スクランブル」は、生成されたハッシュ合計でビットが「かき回される」ように選択された３２ビット整数の２５６要素アレイである。これらの整数は、それらの複合型排他的論理和（「ＸＯＲ」）がゼロに等しくなる（該整数が複合型の１と０ビットのバイナリ同等を有することを意味する）特徴を有するように、一般的に選択される；
３．「＾」オペレータは、排他的論理和関数である；
４．ｌｅｎｇｔｈ＿ｏｆ＿ｂｙｔｅ＿ｓｅｑｕｅｎｃｅ は、分割されるシーケンスの長さである；
５．関数「ｏｕｔｐｕｔ＿ｓｔｉｃｋｙ＿ｐｏｉｎｔ」は、分割要素インデックスと共に呼び出される；
６．「閾値」は、所望の長さのシーケンスが生成されるよう選択される値である。すなわち、値が大きくなればなるほど、より長いシーケンスが生成される。
【００５９】
例１：
2004514968.tif 000006
／／ シーケンス「ｆ」の各バイトに対して、「ｈａｓｈ」はファイルのローリングハッシュを表す；
2004514968.tif 000007
／／ ｓｔｉｃｋｙ＿ｂｉｔｓは、より大きな値がより低い頻度で生成されるという特徴を有する非均一な値である；
2004514968.tif 000008
／／ この計算は、現在のバイトをパーティションの最後と考える必要があるかどうかを判断する；
2004514968.tif 000009
／／ 「ｌａｓｔ＿ｓｔｉｃｋｙ＿ｐｏｉｎｔ」は、既存のパーティションの長さを閾値計算の要素として求めるのに（オプションとして）用いられる前のパーティションのインデックスを覚えている；
2004514968.tif 000010
【００６０】
本発明のシステムおよび方法は、値のシーケンスを通して順次に進み、ローリングハッシュ合計値を計算する。インデックス「ｉ」におけるそのハッシュ合計値は、インデックスｉ−３１〜ｉにおけるバイトにのみ依存している。３１未満のｉの場合、ハッシュ合計は０〜ｉの間のバイトに対する値を反映する。広範なバイト値を用いる「ｆ」の入力テキストおよび適切に選択されたランダム化値のセットが「スクランブル」に存在すると仮定した場合、ハッシュ合計は適切に分散された値域を生じ、所望の３２ビット数範囲に広くかつ均一にまたがる。一部のバイトシーケンスが適切に分散された数を生じない点に留意する必要があるが、この動作を有するバイトシーケンスは典型的な入力テキストに関しては一般的でない。
【００６１】
「ｓｔｉｃｋｙ＿ｂｉｔｓ」値は、現在のハッシュ合計を使って計算される。この値は、非常に非均一な分散を有するよう、また３２ビット値の全範囲にまたがる数を生成するようにできていて、以下の表１で示されるように、より大きな値はそれらの大きさに反比例して生成される：
【表１】
2004514968.tif 000011
【００６２】
更なる変更なしで、この特定の例は、平均の９５％となる、標準偏差を含むシーケンスの長さを有する統計プロパティを実証する。これを補正するために、「ｓｔｉｃｋｙ＿ｂｉｔｓ」値は、現在のシーケンスの長さと組み合わされ、より均一に間隔をあけられたパーティションを生成することができる。この点に関しては、「ｓｔｉｃｋｙ＿ｗｅｉｇｈｔｉｎｇ」は、「ｓｔｉｃｋｙ＿ｂｉｔｓ」値の重み対現在のパーティションの長さを調節するのに用いられるファクタである：
2004514968.tif 000012
【００６３】
例２：
2004514968.tif 000013
／／ シーケンス「ｆ」の各バイトに対して、「ｈａｓｈ」はファイルのローリングハッシュを表す；
2004514968.tif 000014
／／ ｓｔｉｃｋｙ＿ｂｉｔｓは、より大きな値がより低い頻度で生成されるという特徴を有する非均一な値である；
2004514968.tif 000015
／／ この計算は、現在のバイトをパーティションの最後と考える必要があるかどうかを判断する；
2004514968.tif 000016
／／ 「ｌａｓｔ＿ｓｔｉｃｋｙ＿ｐｏｉｎｔ」は、既存のパーティションの長さを閾値計算の要素として求めるのにオプションとして用いられる前のパーティションのインデックスを覚えている；
2004514968.tif 000017
【００６４】
本発明のシステムおよび方法のこの特定の実施例において、調整は、より一貫したパーティションサイズを作り出すために成されてきた。これは、潜在的なパーティションサイズが増加するのにつれて、閾値への「圧力」を本質的に増大させてパーティションを作成することによって、達成される。これを達成する様々な方法が際限なくあるが、前述の例は一つの実例を示すことを意図している点に留意されたい。
【００６５】
理解されるように、本願で開示されているデータシーケンスを組織化しないで決定する本発明のシステムおよび方法は、現代のコンピュータプロセッサを用いて大容積のデータをそれらの共通シーケンスにくくり出す、効率的かつ容易な達成手段を提供する。従来のくくり出し技術と異なり、それは、共通性を確立するために、シーケンス比較、コミュニケーションまたは前のアクションの履歴記録を必要としない。 更に、本発明のシステムおよび方法は、分割されるデータのタイプの影響を本質的に受けず、テキストファイル、バイナリファイル、セット画像、オーディオおよびビデオクリップ、静止画像等に一貫して実行する。
【００６６】
本願に開示されているスティッキーバイトくくり出し技術はまた、共通性がシーケンス内の可変ロケーションにある場合でも、その共通性を識別するのに役立つパーティションを有利に作成する；例えば、特定のドキュメントファイルの２つのバージョン間の差が小さなものだけだったにしても、スティッキーバイトくくり出しは、キャラクタの挿入または削除にもかかわらず、くくり出されたドキュメント間に高い共通性をもたらす。更に、本発明のシステムおよび方法は、「スライドする」か又は絶対位置を変更するデータで、共通性を識別するのに役立つパーティションまたはブレークポイントを生成する。
【００６７】
本質において、本発明のシステムおよび方法は、共通データシーケンスを迅速かつ効率的に見つける方法における問題点を効果的に解決する。更に、それは、前述の分割方式に基づく情報を格納するようにできているシステムに高い可能性で存在しているデータシーケンスの別のコード化を検索するのに使用することができる。本発明のスティッキーバイトくくり出し技術は、典型的なコンピュータファイルシステムで共通シーケンスを検索する場合に特に適切に機能し、最も有名な圧縮アルゴリズムをも含み、多くが基本ファイルサイズ低減技術として共通性くくり出しを利用する幾つかのテスト組合せに対して非常に高い圧縮比をもたらす。
【００６８】
本願で用いられるように、用語「インターネットインフラ」は様々なハードウェアおよびソフトウェアメカニズムを含んでいるが、該用語は、主に、一つのネットワークノードから別のネットワークノードにデータパケットを移動させる機能を有するルーター、ルーターソフトウェアおよびこれらのルーター間の物理リンクを指す。また、本願で用いられるように、「デジタルシーケンス」はコンピュータプログラムファイル、コンピュータアプリケーション、データファイル、ネットワークパケット、マルチメディア（オーディオおよびビデオを含む）といったストリーミングデータ、テレメトリーデータ、およびデジタルまたは数字シーケンスによって表されることができる他のあらゆるデータフォームを含むことができるが、これに限定されるものではない。
【００６９】
特定の例示的なスティッキーバイトくくり出し技術およびコンピュータシステムに関連して本発明の原理を以上で説明してきたが、前述の説明は例としてのみ成されており、本発明の範囲を限定するものではないことは明白に理解されたであろう。特に、前述の開示内容の教示が他の変形実施例を当業者に示唆していることは理解されたであろう。このような変形実施例は、それ自体が既に知られており、本願で既に説明された特徴の代わりにまたはそれに加えて使用可能な他の特徴を含んでもよい。特許請求の範囲は本出願において特定の特徴の組合せに対して明確に述べているが、本願における開示の範囲はまた、特許請求の範囲と同一の発明に関連があるにせよ、また本発明が直面したものと同じ技術的な問題の全てを軽減するにせよ、当業者には明らかな明示的または暗示的に開示されている特徴のあらゆる新規な特徴または組合わせ、またはそれを一般化した例または変形実施例を含むことを理解されたい。出願人は、これによって本出願のまたはそこから導き出される更なる出願の全ての手続き中に、前記の特徴および／または前記の特徴の組合せを新しい特許請求の範囲に発展させる権利を確保する。
【図面の簡単な説明】
【図１】
本発明のシステムおよび方法を実施可能な代表的なネットワーク化されたコンピュータ環境の高レベル図解である。
【図２】
本発明のシステムおよび方法のユーティライゼーションに対して可能な操作環境のより詳細な概念図であり、ここで、任意の数のコンピュータまたはデータセンターで維持されるファイルは、インターネット接続を介した、例えば地理的に多様なロケーションに位置する多くの独立ノードの冗長アレイ（「ＲＡＩＮ」）ラックに対する分散型コンピュータシステムに格納されてよい。
【図３】
本発明のハッシュファイルシステムにコンピュータファイルをエントリするステップを表すロジックフローチャートであり、ここで、ファイルのハッシュ値は、セット（データベース）で予め維持されるファイルのハッシュ値とチェックされる。
【図４】
ファイルまたは他のデータシーケンスをハッシュされたピースにブレークアップするステップを表す更なるロジックフローチャートであり、多くのデータピースを生成させるのに加えて、各ピースに対して確率的に固有のハッシュ値を対応させる。
【図５】
ファイルの各ピースのハッシュ値とセットまたはデータベースの既存のハッシュ値との比較を表す別のロジックフローチャートであり、レコードの生成は、全ファイルピースに対して単一のハッシュ値と様々なピースのハッシュ値との等価を示し、そこで、新しいデータピースおよびそれに対応する新しいハッシュ値がセットに加えられる。
【図６】
ファイルハッシュまたはディレクトリリストハッシュ値を既存のディレクトリリストハッシュ値と比較して、新しいファイルまたはディレクトリリストハッシュ値をセットディレクトリリストに加えるステップを示す、更に別のロジックフローチャートである。
【図７】
典型的なファイルの特定のピースの編集の前後に、代表的なコンピュータファイルのピースをそれに対応するハッシュ値と比較している。
【図８】
本発明のシステムおよび方法によって導き出されることができる複合データが明示的に表されるデータと事実上同一ではあるが、「レシピ」（例えばその対応しているハッシュによって表されるデータの連結またはハッシュによって表されるデータを用いた関数の結果）によって、その代わりに作成されてもよいという事実の概念図である。
【図９】
本発明のハッシュファイルシステムおよび方法が、ハッシュ値をそれらが表すデータへのポインターとして使用することによって、冗長シーケンスの再利用を最適化するためにデータを編成するのにどのように利用可能であるかを表す別の概念図であり、ここで、データは、明確なバイトシーケンス（原子データ）またはシーケンスのグループ（複合物）として表されてよい。
【図１０】
典型的な１６０ビットハッシュ値のハッシュファイルシステムアドレス変換関数を示す簡略図である。
【図１１】
本発明のシステムおよび方法で用いられるインデックス・ストライプ分割関数の典型的な簡略図である。
【図１２】
Ｄａｙ １に多くのプログラムおよびドキュメントファイルを有している典型的な家庭用コンピュータのデータのバックアップに用いられる本発明のシステムおよび方法の全体的な機能を示す簡略図であり、ドキュメントファイルの一つが第３のドキュメントファイルを加えると共にＤａｙ ２で編集される。
【図１３】
多くの「スティッキーバイト」によってマークされる特定のドキュメントファイルの様々なピースの編集の前後両方での比較を示し、ピースのうちの一方はそれによって変更され、他方のピースは同じままである。
【図１４】
本発明による典型的なスティッキーバイトくくり出しプロセスの代表的なフローチャートである。
【図１】
2004514968.tif 000018
【図２】
2004514968.tif 000019
【図３】
2004514968.tif 000020
【図４】
2004514968.tif 000021
【図５】
2004514968.tif 000022
【図６】
2004514968.tif 000023
【図７】
2004514968.tif 000024
【図８】
2004514968.tif 000025
【図９】
2004514968.tif 000026
【図１０】
2004514968.tif 000027
【図１１】
2004514968.tif 000028
【図１２】
2004514968.tif 000029
【図１３】
2004514968.tif 000030
【図１４】
2004514968.tif 000031
【国際公開パンフレット】
2004514968.tif 000032
2004514968.tif 000033
2004514968.tif 000034
2004514968.tif 000035
2004514968.tif 000036
2004514968.tif 000037
2004514968.tif 000038
2004514968.tif 000039
2004514968.tif 000040
2004514968.tif 000041
2004514968.tif 000042
2004514968.tif 000043
2004514968.tif 000044
2004514968.tif 000045
2004514968.tif 000046
2004514968.tif 000047
2004514968.tif 000048
2004514968.tif 000049
2004514968.tif 000050
2004514968.tif 000051
2004514968.tif 000052
2004514968.tif 000053
2004514968.tif 000054
2004514968.tif 000055
2004514968.tif 000056
2004514968.tif 000057
2004514968.tif 000058
2004514968.tif 000059
2004514968.tif 000060
2004514968.tif 000061
2004514968.tif 000062
2004514968.tif 000063
2004514968.tif 000064
2004514968.tif 000065
2004514968.tif 000066
2004514968.tif 000067
2004514968.tif 000068
2004514968.tif 000069
2004514968.tif 000070
2004514968.tif 000071
2004514968.tif 000072
2004514968.tif 000073
2004514968.tif 000074
2004514968.tif 000075
2004514968.tif 000076
2004514968.tif 000077
2004514968.tif 000078
2004514968.tif 000079
【国際調査報告】
2004514968.tif 000080
2004514968.tif 000081