(57)【特許請求の範囲】
【請求項１】
デジタルシーケンスを含むデータを管理する方法であって、
コンピュータシステムが関数を用いて前記デジタルシーケンスに対して確率的に固有の識別子を生成するステップと、
前記コンピュータシステムが前記確率的に固有の識別子を、他のデジタルシーケンスと対応する、記憶装置に記憶された他の識別子のリストと比較するステップと、
前記確率的に固有の識別子が前記リストに予め無い場合、コンピュータシステムが前記デジタルシーケンスを複数のより短いデジタルシーケンスに分割するステップと、
前記コンピュータシステムが関数を用いて前記複数のより短いデジタルシーケンスの各々に対して確率的に固有の識別子を生成するステップと、
前記コンピュータシステムが前記複数のより短いデジタルシーケンスに対応する前記確率的に固有の識別子を前記リストと比較するステップと、
前記より短いデジタルシーケンスに対応する前記確率的に固有の識別子が前記リストに予め無い場合、前記コンピュータシステムが前記より短いデジタルシーケンスおよび前記対応する確率的に固有の識別子を前記リストに加えるステップと、
前記より短いデジタルシーケンスに対応する前記確率的に固有の識別子が前記リストに予めある場合、前記コンピュータシステムが前記より短いデジタルシーケンスおよび前記対応する確率的に固有の識別子を前記リストから取り除くか、またはスクリーニングするステップと
を備える方法。
【請求項２】
前記コンピュータシステムが前記デジタルシーケンスを複数のより短いデジタルシーケンスに分割するステップと、
前記コンピュータシステムが前記複数のより短いデジタルシーケンスの各々に対応する同様の複数の確率的に固有の識別子を生成するステップと、を更に備える、請求項１記載の方法。
【請求項３】
前記分割ステップが、個々に可変長を有する前記より短いデジタルシーケンスを生成する、請求項１記載の方法。
【請求項４】
前記分割ステップが、前記デジタルシーケンスのコンテンツに基づいている、請求項１記載の方法。
【請求項５】
前記分割ステップが、前記デジタルシーケンスを記述しているメタデータに基づいている、請求項１記載の方法。
【請求項６】
前記分割ステップが、実質的に不変長を有する前記より短いデジタルシーケンスを生成する、請求項１記載の方法。
【請求項７】
前記同様の複数の確率的に固有の識別子を生成する前記ステップが、
前記コンピュータシステムが前記より短いデジタルシーケンスに対して個々にハッシュ関数を実行して、前記同様の複数の確率的に固有の識別子を生成するステップを備える、請求項１記載の方法。
【請求項８】
前記コンピュータシステムが少なくとも前記確率的に固有の識別子の一部を前記比較ステップ用の前記リストのロケーションへのインジケータとして利用するステップを更に備える、請求項１記載の方法。
【請求項９】
データ記憶システムであって、
データに含まれるデジタルシーケンスの一部と、前記デジタルシーケンスの前記一部の各々に対して対応する確率的に固有の識別子を維持する、少なくとも１つのリストを記憶するための記憶装置と、
前記記憶装置に接続され、少なくとも１つの新しいデジタルシーケンスを受信し、関数を用いて前記デジタルシーケンスに対して確率的に固有の識別子を生成し、前記確率的に固有の識別子を、他のデジタルシーケンスと対応する、記憶装置に記憶された他の識別子のリストと比較し、前記確率的に固有の識別子が前記リストに予め無い場合、前記新しいデジタルシーケンスを複数のより短いデジタルシーケンスに分割し、関数を用いて前記より短いデジタルシーケンスの各々に対して確率的に固有の識別子を生成するコントローラであって、前記複数のより短いデジタルシーケンスの各々に対する前記確率的に固有の識別子のうちの任意の１つが前記リストで現在維持されているかどうかを判断し、前記少なくとも１つのリストに維持されていると判断されなかった前記確率的に固有の識別子のうちの任意の１つと、該任意の一つの確率的に固有の識別子と対応するより短いデジタルシーケンスとを前記少なくとも１つのリストに加える前記コントローラと、
を備える、データ記憶システム。
【請求項１０】
前記少なくとも１つのリストが複数のリストを備える、請求項９記載のデータ記憶システム。
【請求項１１】
前記複数のリストが、それぞれ前記確率的に固有の識別子の一部を含む、請求項１０記載のデータ記憶システム。
【請求項１２】
前記複数のリストのうちの少なくとも１つが、前記少なくとも１つのリストの他から物理的に移される、請求項１０記載のデータ記憶システム。
【請求項１３】
前記複数のリストが、前記確率的に固有の識別子に基づいて分割される、請求項１０記載のデータ記憶システム。
【請求項１４】
前記複数のリストはネットワークによって結合する、請求項１２記載のデータ記憶システム。
【請求項１５】
前記少なくとも１つのリストが、前記少なくとも１つの分割メカニズムから物理的に移される、請求項９記載のデータ記憶システム。
【請求項１６】
前記リストが物理的分散データベースを備える、請求項９記載のデータ記憶システム。
【請求項１７】
前記コントローラおよび前記記憶装置が、ネットワークによって結合される、請求項９記載のデータ記憶システム。
【請求項１８】
前記ネットワークがインターネットのような公衆網を備える、請求項１７記載のデータ記憶システム。
【請求項１９】
前記コントローラおよび前記記憶装置が、物理的に分散される、請求項１８記載のデータ記憶システム。
【請求項２０】
前記確率的に固有の識別子がハッシュ関数によって生成される、請求項９記載のデータ記憶システム。
【請求項２１】
前記ハッシュ関数が、業界標準ダイジェストアルゴリズムを備える、請求項２０記載のデータ記憶システム。
【請求項２２】
前記ハッシュ関数が、MD4、MD5 SHAまたはSHA-1アルゴリズムのうちの１つを備える、請求項２１記載のデータ記憶システム。
【請求項２３】
前記確率的に固有の識別子がチェックサムによって生成される、請求項２０記載のデータ記憶システム。
【請求項２４】
前記デジタルシーケンスは可変長である、請求項９記載のデータ記憶システム。
【請求項２５】
前記デジタルシーケンスは不変長である、請求項９記載のデータ記憶システム。
【請求項２６】
前記コントローラが、前記複数の前記より短いデジタルシーケンスに対する前記確率的に固有の識別子の少なくとも一部を、前記リスト分割に関連があるロケーターとして利用するのに有効である、請求項１５記載のデータ記憶システム。
【請求項２７】
前記デジタルシーケンスがデータファイルを備える、請求項９記載のデータ記憶システム。
【請求項２８】
前記デジタルシーケンスがデータストリームを備える、請求項９記載のデータ記憶システム。
【請求項２９】
前記デジタルシーケンスが実行可能ファイルを備える、請求項９記載のデータ記憶システム。
【請求項３０】
前記デジタルシーケンスがデータベースレコードを備える、請求項９記載のデータ記憶システム。
【請求項３１】
前記デジタルシーケンスがデータベースインデックスを備える、請求項９記載のデータ記憶システム。
【請求項３２】
前記デジタルシーケンスがディジタル装置画像を備える、請求項９記載のデータ記憶システム。
【請求項３３】
前記デジタルシーケンスがネットワークパケットを備える、請求項９記載のデータ記憶システム。
【請求項３４】
前記デジタルシーケンスがデジタル化されたアナログ信号を備える、請求項９記載のデータ記憶システム。
【請求項３５】
デジタルシーケンスを含むデータを管理するためのコンピュータープログラムであって、
コンピュータに関数を用いてデジタルシーケンスの確率的に固有の識別子の生成を行わせるよう構成されたコンピュータ可読プログラムコードと、
前記コンピュータに、前記確率的に固有の識別子と他のデジタルシーケンスに対応する他の識別子のリストの比較を行わせるよう構成されたコンピュータ可読プログラムコードと、
前記確率的に固有の識別子が前記リストに予め無い場合、前記コンピュータに、前記デジタルシーケンスを複数のより短いデジタルシーケンスに分割させるように構成されたコンピュータ可読プログラムコードと、
前記コンピュータに、関数を用いて前記より短いデジタルシーケンスの各々に対して確率的に固有の識別子を生成させて、各より短いデジタルシーケンスが各確率的に固有の識別子と関連付けされるように構成されたコンピュータ可読プログラムコードと、
前記コンピュータに、前記確率的に固有の識別子を前記リストと比較させるよう構成されたコンピュータ可読プログラムコードと、
前記確率的に固有の識別子が前記リストに予め無かった場合、前記コンピュータに前記確率的に固有の識別子と、該確率的に固有の識別子と対応するより短いデジタルシーケンスとの前記リストへの追加を行わせるよう構成されたコンピュータ可読プログラムコードと
を備える、コンピュータープログラム。
【請求項３６】
前記コンピュータに生成を行わせるよう構成された前記コンピュータ可読プログラムコードは、
コンピュータに前記デジタルシーケンスのハッシュ関数を実行させて前記確率的に固有の識別子を生成させるよう構成されたコンピュータ可読プログラムコードを含む、
請求項３５記載のコンピュータープログラム。
【請求項３７】
コンピュータにハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコードは、業界標準ダイジェストアルゴリズムによって実行される、請求項３６記載のコンピュータープログラム。
【請求項３８】
コンピュータにハッシュ関数を実行させるよう構成された前記コンピュータ可読プログラムコードは、MD4、MD5、SHAまたはSHA-1アルゴリズムのうちの１つによって実行される、請求項３７記載のコンピュータープログラム。
【請求項３９】
コンピュータに生成を行わせるよう構成された前記コンピュータ可読プログラムコードは、
コンピュータに前記デジタルシーケンスのチェックサムの生成を行わせて前記確率的に固有の識別子を生成させるよう構成されたコンピュータ可読プログラムコードを含む、請求項３５記載のコンピュータープログラム。
【請求項４０】
コンピュータに前記デジタルシーケンスの前記確率的に固有の識別子を含むディレクトリリストの作成を行わせるよう構成されたコンピュータ可読プログラムコードを更に備える、請求項３５記載のコンピュータープログラム。
【請求項４１】
コンピュータに分割を行わせるよう構成された前記コンピュータ可読プログラムコードが、個々に可変長を有する前記より短いデジタルシーケンスを生成する、請求項３５記載のコンピュータープログラム。
【請求項４２】
コンピュータに分割を行わせるよう構成された前記コンピュータ可読プログラムコードが、実質的に不変長を有する前記より短いデジタルシーケンスを生成する、請求項３５記載のコンピュータープログラム。
【請求項４３】
コンピュータに前記同様の複数の確率的に固有の識別子の生成を行わせるよう構成された前記コンピュータ可読プログラムコードが、
コンピュータに前記より短いデジタルシーケンスのハッシュ関数を個々に実行させて前記同様の複数の確率的に固有の識別子を生成させるよう構成されたコンピュータ可読プログラムコードを含む、請求項３５記載のコンピュータープログラム。
【請求項４４】
コンピュータに前記複数のより短いデジタルシーケンスおよび前記対応する同様の複数の確率的に固有の識別子の前記リストへの追加を行わせるよう構成されたコンピュータ可読プログラムコードを更に備える、請求項３５記載のコンピュータープログラム。
【請求項４５】
コンピュータに、少なくとも前記確率的に固有の識別子の一部を前記比較ステップ用の前記リストのロケーションテーブルへのインデックスとして利用させるよう構成されたコンピュータ可読プログラムコードを更に備える、請求項３５記載のコンピュータープログラム。
【請求項４６】
前記記憶装置が、前記各より短いデジタルシーケンスと各前記確率的に固有の識別子との間の対応を確立して、各より短いデジタルシーケンスが各確率的に固有の識別子と関連付けされるようにするステップを備える請求項１に記載の方法。
【請求項４７】
前記識別子および前記対応する前記より短いデジタルシーケンスが少なくとも一つのデータリストで維持される、請求項４６記載の方法。
【請求項４８】
少なくとも一部の前記識別子が、前記少なくとも一つのデータリスト内の前記対応する前記より短いデジタルシーケンスのロケーションへのポインタとして利用できる、請求項４６記載の方法。
【請求項４９】
前記より短いデジタルシーケンスが少なくとも一部のデータファイルを備え、前記識別子が前記少なくとも一部の前記データファイルのコンテンツに固有に関連している、請求項４６記載の方法。
【請求項５０】
前記より短いデジタルシーケンスが少なくとも一部のデータストリームを備え、前記識別子が前記少なくとも一部の前記データストリームのコンテンツに固有に関連している、請求項４６記載の方法。
【請求項５１】
前記少なくとも一部の前記デジタルシーケンスが少なくとも一部の実行可能ファイルを備え、前記識別子が前記少なくとも一部の前記実行可能ファイルのコンテンツに固有に関連している、請求項４６記載の方法。
【請求項５２】
前記関数実行ステップが、
前記より短いデジタルシーケンスのハッシュ関数を実行して前記確率的に固有の識別子を生成するステップによって実行される、請求項４６記載の方法。
【請求項５３】
前記ハッシュ関数を実行するステップが、業界標準ダイジェストアルゴリズムによって実行される、請求項５２記載の方法。
【請求項５４】
前記ハッシュ関数を実行するステップが、MD4、MD5、SHAまたはSHA-1アルゴリズムのうちの１つによって実行される、請求項５３記載の方法。
【請求項５５】
コンピュータに、前記複数のより短いデジタルシーケンスの各々と各前記確率的に固有の識別子との間での対応の確立を行わせて、各より短いデジタルシーケンスが各確率的に固有の識別子と関連付けられるよう構成されたコンピュータ可読プログラムコードを備える、請求項３５に記載のコンピュータープログラム。
【請求項５６】
前記識別子および前記対応する前記より短いデジタルシーケンスが少なくとも一つのデータリストで維持される、請求項５５記載のコンピュータープログラム。
【請求項５７】
少なくとも一部の前記識別子が、前記少なくとも一つのデータリスト内の前記対応する前記より短いデジタルシーケンスのロケーションへのポインタとして利用できる、請求項５６記載のコンピュータープログラム。
【請求項５８】
前記より短いデジタルシーケンスが少なくとも一部のデータファイルを備え、前記識別子が前記少なくとも一部の前記データファイルのコンテンツに固有に関連している、請求項５５記載のコンピュータープログラム。
【請求項５９】
前記より短いデジタルシーケンスが少なくとも一部のデータストリームを備え、前記識別子が前記少なくとも一部の前記データストリームのコンテンツに固有に関連している、請求項５５記載のコンピュータープログラム。
【請求項６０】
前記より短いデジタルシーケンスが少なくとも一部の実行可能ファイルを備え、前記識別子が前記少なくとも一部の前記実行可能ファイルのコンテンツに固有に関連している、請求項５５記載のコンピュータープログラム。
【請求項６１】
コンピュータに関数を実行させるよう構成された前記コンピュータ可読プログラムコードが、
コンピュータに、前記より短いデジタルシーケンスに対してハッシュ関数を実行させて前記確率的に固有の識別子を生成させるよう構成されたコンピュータ可読プログラムコードによって実行される、請求項５５記載のコンピュータープログラム。
【請求項６２】
コンピュータにハッシュ関数を実行させるよう構成されたコンピュータ可読プログラムコードが、業界標準ダイジェストアルゴリズムによって実行される、請求項６１記載のコンピュータープログラム。
【請求項６３】
コンピュータにハッシュ関数を実行させるよう構成されたコンピュータ可読プログラムコードが、MD4、MD5、SHAまたはSHA-1アルゴリズムのうちの１つによって実行される、請求項６２記載のコンピュータープログラム。
【発明の詳細な説明】
【０００１】
【著作権に関する通知／許可】
この特許文献の開示の一部は、著作権保護の対象となる材料を含んでよい。著作権所有者は、米国登録商標特許庁の特許ファイルまたはレコードに記載されているような特許の開示の特許文献が誰によってファクシミリ再生されても異論はないが、それ以外においては、いかなるものに対しても全ての著作権の権利を確保する。以下の通知はソフトウェア、データおよび該当する場合には図面を含む以下の説明に適用される。Copyright（著作権あり）2000, Undoo Technologies
【０００２】
【発明の背景】
本発明は、一般に、ハッシュファイルシステムおよび共通性ファクタリングシステムの分野に関する。より詳細には、本発明は、分散形コンピュータデータ環境およびそれに対する特定のアプリケーションにおいて電子ファイル間の対応を判断するシステムおよび方法に関する。
【０００３】
経済的、政治的および社会的なパワーは、データによってますます管理されている。トランザクションおよび豊かさは、データによって表される。政治的なパワーは、データに基づいて分析され修正される。人間の相互作用および関係は、データ交換によって定義される。したがって、データの効率的な配布、記憶および管理が、人間社会においてますます不可欠な役割を演ずることが予想される。
【０００４】
コンピュータプログラム、データベース、ファイルなどの形式の、管理が不可欠なデータの量は、急激に増加している。コンピュータ処理力が増加するにつれて、オペレーティングシステムおよびアプリケーションソフトウェアはより大きくなっていく。さらに、マルチメディアファイルおよび大容量データベースといったより大きなデータセットにアクセスしたいという要望は、管理されるデータ量を増大させる。このますます大きくなるデータロードを、コンピューティング装置間で移動させ、アクセス可能なやり方で格納することは不可欠である。データの指数増加レートは通信帯域および記憶容量の改良を追い越すことが予想され、従来の方法を用いたデータ管理をより切迫したものにしている。
【０００５】
多くのファクタは釣り合いをとられる必要があり、また、従来のデータ記憶システムにおいてはしばしば譲歩される必要がある。データ量が極めて大きいことから、記憶されるビットあたりのコストを減らすことに対するプレッシャは絶えることがない。また、データ管理システムは、現在のニーズだけでなく将来のニーズを予想してもスケーラブルである必要がある。
【０００６】
記憶システムは、ユーザーが任意の特定の時間に必要とする容量だけを購入することができるように、インクリメンタルにスケーラブルであることが望ましい。データユーザーが、データの脱落、損傷および入手不可に対してますます許容しなくなるのにつれて、高い信頼性および高い可用性も考慮される。
【０００７】
残念ながら、従来のデータ管理アーキテクチャはこれらのファクタに譲歩しなければならず、そのため、どのアーキテクチャも費用効率の高さ、信頼性、高可用性、スケーラブルな解決を提供できない。
【０００８】
従来のRAID（独立した複数のディスクからなる冗長配列）システムは、ハードディスクといった多重記憶装置の異なる位置に同一データを（したがって冗長に）格納する方法である。データを多重ディスクに入れることによって、入/出力（「Ｉ／Ｏ」）操作はバランスの取れた状態でオーバーラップでき、性能を改善する。多重ディスクの使用が平均故障間隔（「MTBF」）を増大させることから、冗長なデータ格納もまた故障の許容範囲を増加させる。RAIDシステムは実際のデータ管理の複雑さを隠すようハードウェアまたはソフトウェアコントローラに依存しており、そのためRAIDシステムはオペレーティングシステムに一つの論理的ハードディスクとして現れる。しかしながら、RAIDシステムは、ケーブル接続およびコントローラの物理的な限界のために基準化するのが難しい。また、RAIDシステムの可用性はコントローラ自体の機能性にかなり左右されており、そのため、コントローラが故障すると、コントローラの背後に格納されるデータが利用できなくなる。さらに、RAIDシステムは一般的なハードウェアよりむしろ専門的なハードウェアを必要とし、したがって高価な解決策である傾向がある。
【０００９】
NAS（ネットワーク接続ストレージ）は、アプリケーションサーバに接続されるのではなく、それ自身のネットワークアドレスによって設定されるハードディスクストレージを指す。ファイルリクエストは、NASファイルサーバにマップされる。NASは、RAIDに基づいたハードウェアかソフトウェアを用いたトランスペアレントな入出力動作を提供してよい。NASはまた、故障の許容範囲をさらに改善するために、一つ以上の他のNASデバイスに対してデータのミラーリングを自動化してもよい。NASデバイスをネットワークに加えることができるので、それらのデバイスはネットワークが利用できる記憶領域の全容量の基準化を可能にする。しかしながら、NASデバイスは、RAIDアプリケーションにおいて従来のRAIDコントローラの能力に制約される。また、NASシステムはミラーリングおよびノードにわたるパリティーを不可能にし、よって限定された解決策である。
【００１０】
データストレージ問題に加えて、データトランスポートは、広域ネットワーク（「WAN」）およびインターネットワーキング技術の改良によって、急速に発展している。インターネットは、例えば、ほとんどいたる所にあるアクセスによってグローバルにネットワーク化された環境を作りあげた。迅速なネットワークインフラの改善にもかかわらず、トランスポートを必要とするデータ量の増加割合は、有効帯域の改良を追い越すであろうと予想される。
【００１１】
理念的に、従来のデータ管理方法はハードウェアデバイスおよびデータの操作および移動のために発展したインフラと一致していない。たとえば、コンピュータは特徴として容易にプログラムされ、仮想的に無制限な様々な機能を実行する汎用機である。しかしながら、コンピュータには、大きな割合で、マシンの特殊目的にあわせるために汎用的性質を限定されている、固定され且つゆっくり変更されるデータセットがロードされている。演算速度、周辺装置性能およびデータ記憶容量の進歩は、商品のコンピュータで最も劇的である。しかしながら、多くのデータストレージの解決策は、基本となる記憶領域コントローラによって広げられるのではなく、むしろ制限されるのでこれらの進歩を利用することができない。同様に、インターネットはフォールト・トレラントの複数パス相互接続ネットワークとして発展してきた。しかしながら、ネットワークリソースは、ノードが接続しているネットワークのフォールト・トレラントにもかかわらずノード障害がリソースを利用不可にするといった特定のネットワークノードで従来実現される。ニーズは、高可用性、高信頼性、非常にスケーラブルなデータストレージの解決に対して継続して存在している。
【００１２】
【発明の概要】
特定であるか、異なっているかまたは変化する長さの桁のハッシュおよび／または文字列に基づいて編成されたコンピュータファイルシステムのシステムおよび方法が本願に開示されており、システムからデータブロック（またはデータブロックの一部）の冗長コピーを除去するかまたはスクリーニングすることが可能である。また、業界標準メッセージダイジェスト4（「MD4」）、MD5、安全なハッシュアルゴリズム（「SHA」）またはSHA-1アルゴリズムといったチェックサム生成プログラム、エンジンまたはアルゴリズムによって生成されてよいコンピュータファイルシステムのシステムおよび方法も本願に開示されている。さらに、ハッシュが、チェックサムプログラム、エンジン、アルゴリズム、或いは非線形の確率的な数値計算用アルゴリズムまたは他のデータ/数字シーケンスの入力テキストから疑似ランダム値を生成するあらゆる業界標準技術に基づく不定元サイズのデータブロックの確率的に固有のハッシュ値を生成する他の手段によって生成されてよい、コンピュータファイルシステムのシステムおよび方法も本願に開示されている。
【００１３】
本発明のシステムおよび方法は、本願で開示される特定のアプリケーションにおいて、データの冗長を自動的に考慮から除外するのに利用されてよく、潜在的に非常に多量の考慮されていない記憶領域のサイズをいくつかのオーダーで頻繁に減らすことを可能にする。この事については、本発明のシステムおよび方法は、特定のハードウェアまたはソフトウェアの特徴に関係なく、全てのコンピュータが、単純、効率的かつ安全にデータを共有し、データの読み込み、書き込み、または参照を達成するユニークで有利な手段を提供するのを可能にする。本発明のシステムおよび方法は、ネットワーク化されたコンピュータまたはコンピュータシステムに関して特に効果的であるが、相当する結果を有する絶縁データストレージに適用されてもよい。
【００１４】
本発明のハッシュファイルシステムは、従来のストレージアーキテクチャを悩ませている多くの問題を有利に解決する。例えば、本発明のシステムおよび方法は、複製およびわずかに異なるコピーによって必然的に発生する無駄なシステムリソースすべてと共に莫大なディレクトリおよびファイルの集合を管理する必要性を除外する。複製ファイルのメンテナンスおよびストレージは、従来の会社および個人のコンピュータシステムを悩ませ、一般に、人にとって骨の折れる「ディスクスペースのクリーンアップ」への関与を必要とする。本発明のハッシュファイルシステムは、コピーに使われるディスクスペースを除去し、部分コピーに使われるディスクスペースをほとんど完全に除去することによって、効果的にこの問題を取り除く。たとえば、従来のコンピュータシステムでは、ギガバイトのディレクトリ構造の新しいロケーションへのコピーには、更なるギガバイトのストレージが要求される。特定のアプリケーションにおいて、本発明のハッシュファイルシステムは、このオペレーションで使われるディスクスペースを最高10万倍以上減らす。
【００１５】
現在、幾つかのファイルシステムはコピーを削除するメカニズムを有するが、どれも、短い時間でこのオペレーションを達成する（専門用語では、システムが基準化されている場合であっても、 O(l)（「一定時間のオーダーの」）時間でシステムがコピーをファクタリングすることを意味する）ことができない。これは、O(N**2)、O(N)またはO(log(N))時間を必要とする他のシステムとは対照的に一定の時間の単位を意味しており、この時間はファクタリングされるストレージの量と関連がある。変化する時間においてストレージをファクタリングすることは、ストレージの量が少ない場合には、かろうじてシステムにとって満足のいくようなものであるが、システムが大きなサイズに増大するにつれて、最も効率的な可変ファクタリングシステムでさえ維持しきれなくなる。本発明のハッシュファイルシステムは、ストレージを今までに決して試みられなかったスケールでファクタリングするように設計されていて、第１のインプリメンテーションにおいて、かなり大きなサイズに拡大する能力を用いて、200万ペタビットのストレージをファクタリングすることができる。既存のファイルシステムは、このようなスケールでデータを管理することはできない。
【００１６】
さらに、本発明のハッシュファイルシステムは、安価な、グロ―バルコンピュータシステムデータ保護およびバックアップを提供するのに利用されてよい。コンピュータファイルシステムは各バックアップ処理の間に全ストレージの２，３パーセント以上を変更することがほとんどないので、そのファクタリング機能は非常に効率的に典型的なバックアップデータセット上で作用する。さらに、本発明のハッシュファイルシステムは、効率的なメッセージ通信（電子メール）システムに基準として使用できる。電子メールシステムは、基本的には、著作者がメッセージを書き、それを受け側のリストに送信するデータコピーメカニズムである。電子メールシステムは、データを1つの位置から別の位置にコピーすることによって、この「送信」オペレーションを効果的に実現する。著作者は一般に本人が送信するメッセージのコピーを保持し、受け側は彼ら自身のコピーをそれぞれ保持する。これらのコピーは、これもまた保持される応答にしばしば添付される（すなわちコピーのコピー）。本発明の共通性ファクタリングの特徴はこの総非効率性を取り除くことができ、その一方で、電子メールユーザーがこのよく知られているコピー指向パラダイムを維持するのを明らかに可能にする。
【００１７】
上述したように、コンピュータシステムの大部分のデータはまず変更されないので、本発明のハッシュファイルシステムはシステム全体の完全なスナップショットの再生を可能にし、例えばスナップショットが存在するあらゆる時間あらゆる日の間保持することができ、または、システムニーズによるが分単位（またはそれ以下）のインターバルでとられたスナップショットによって連続的に保持することもできる。さらに、従来のコンピュータシステムはファイル（すなわちデジタルエキップメントコーポレーションのVAX（登録商標） VMS（登録商標）ファイルシステム）の限定されたバージョニングをしばしば提供することから、本発明のハッシュファイルシステムはまたこの事に関して重要な利点を提供する。従来のシステムでのバージョニングは、良い面および悪い面の両方を提示している。前者においては、それはアクシデントを防ぐ手助けをしているが、後者においては、それは消費するディスクスペースを減らすために正規のパージを要求する。本発明のハッシュファイルシステムは、特別なスペースをほとんど用いずに同一のコピーまたは編集コピーをファクタリングすることによって、オーバーヘッドがほとんどない状態でファイルのバージョニングを提供する。たとえば、典型的なドキュメントの100リビジョンを保存することは、通常、オリジナルファイルのスペースの約100倍のスペースを必要とする。本願で開示されているハッシュファイルシステムを用いることによって、それらのリビジョンは、オリジナルのスペースの３倍のみのスペースを必要とするであろう（ドキュメントのサイズ、編集の程度およびタイプ、および外的要素に依存する）。
【００１８】
本発明のハッシュファイルシステムの更なる他の潜在的アプリケーションは、ウェブサービングを含む。この事に関しては、共通性ファクタリング（ハッシュ）方法はまた全てのハッシュファイルシステムサーバ上に均一分散を生じることから、ハッシュファイルシステムは、効率的にウェブコンテンツを分散するのに使用できる。この均一な分散は、大きなアレーのサーバが、均一に分散されたロードを有する巨大なウェブサーバファームとして機能するのを可能にする。他のアプリケーションでは、本発明のハッシュファイルシステムは、データ自体の代わりにデータのプロキシ（ハッシュ）を送信することによってネットワークトラフィックを減らすのに使用できることから、ネットワークアクセラレータとして使用できる。現在のネットワークトラフィックの大きな割合は、ロケーション間で動いている重複データである。データのプロキシ送信は、効果的なローカルキャッシュメカニズムが機能するのを可能にし、おそらくはインターネット上のトラフィックをいくつかのオーダーで減らすのを可能にする。
【００１９】
特に本願で開示されるように、本発明のハッシュファイルシステムおよび方法は、一般的なポインタとして160ビットのハッシュサムを用いて実現されてよい。これは、中央権限から割り当てられるポインタを用いる従来のファイルシステムとは異なっている（すなわち、Unixでは、32ビットの「iノード」がロックステップオペレーションでのカーネルのファイルシステムによって割り当てられ、固有性を確保する）。本発明のハッシュファイルシステムでは、これらの160ビットのハッシュサムは、ハッシュアルゴリズムによって中央権限なしで（すなわちロッキングなし、 同期なしで）割り当てられる。
【００２０】
既知のハッシュアルゴリズムは、均一に値域にまたがる確率的に固有の数を生成する。ハッシュ関数SHA-1の場合、その範囲は 0〜10e48である。このハッシュ演算は、格納されるデータのコンテンツだけを調べることによって行なわれ、したがって、完全なアイソレーション、非同期、およびインタロックなしで実行できる。
【００２１】
ハッシュは、システムのあらゆるコンポーネントによって確認可能なオペレーションであり、それらのコンポーネントの全域にわたって信頼されるオペレーションの必要性を取り除く。したがって、本願で開示された本発明のハッシュファイルシステムおよび方法は、従来の大規模な分散ファイルシステム（すなわち信頼される包含中央権限）の重要なボトルネックを取り除くよう機能する。それは同時読取り書込みオペレーションに対して無制限である大規模な分散ファイルシステムの構造を可能にし、非コヒーレンスの危険および特定の従来のボトルネックの制限なしで機能できる。
【００２２】
本発明の前記および他の特徴と目的およびそれを達成する方法は以下の説明でより明らかになり、本発明は添付の図と以下の好適な実施例の説明を参照することによって最も理解されるであろう。
【００２３】
【代表的な実施例の説明】
本願に開示されているように本発明のハッシュファイルシステムおよび方法の特定のインプリメンテーションにおいて、そのアプリケーションは、商品のコンピューティング装置およびインターネットといったインターネットワーク技術の強力な性質の急速な進歩に影響を及ぼす高可用性かつ高信頼性のデータ記憶システムを目的とする。本願に特に開示されているのは、一つ以上のデータブロック（ファイル、ディレクトリ、ドライブ画像、ソフトウェアアプリケーション、デジタル音声およびリッチ媒体コンテンツを含むがこれに限定されるものではない）と、そのデータブロックに対する一つ以上の記号の対応を管理するハッシュファイルシステムであって、記号は、数、ハッシュ、チェックサム、2進シーケンス、又はデータブロック自体から導き出され、統計学的に、確率的に、さもなければ効果的にそのデータブロックに特有である他の識別子であってよい。システムは、限定されることなく、以下を含むあらゆるコンピュータシステムに機能する：パーソナルコンピュータ；スーパーコンピュータ；分散型または非分散型ネットワーク；IDE、SCSIまたは他のディスクバスを用いた記憶領域ネットワーク（「SAN」）；ネットワーク接続ストレージ（「NAS」）またはデータを格納しておよび／または処理することができる他のシステム。
【００２４】
本願で開示されるハッシュファイルシステムの特定のインプリメンテーションにおいて、記号は、エンジン、プログラム、又はMD4、MD5、SHA、SHA-1またはそれらの導出物を含むが、それに限定されないアルゴリズムを生成する一つ以上のハッシュまたはチェックサムを用いて導き出されてよい。さらに、記号は、エンジン、プログラム、又はMD4、MD5、SHA、SHA-1を含むが、それに限定されないアルゴリズムを生成するハッシュまたはチェックサム、或いはデータコンテンツに基づいた確率的に固有の識別子を生成する他の方法、を用いて導き出された可変長または不変長の記号の一部を備えてよい。本願で開示される特定のインプリメンテーションにおいて、ファイルシーク或いはデータを検索するか又はデータの存在/可用性をチェックするルックアップは、記号の全部分または記号の少量の部分を見ることによって加速可能であり、記号の一部は、データの存在/可用性を見つけるか、検索するか、或いはチェックするためのルーティング情報を示しているか、そうでなければ提供している。
【００２５】
さらに、ハッシュファイルシステムのシステムおよび方法が本願で開示されており、記号は、システム内での冗長コピーの識別を可能にし、および／またはファイリングおよびストレージシステムに提示されるデータのために冗長なシステム内でのコピーの識別を可能にする。記号は、データの完全性の損失なしで、システム内のデータおよび／またはデータの一部の冗長コピー或いはシステムに提示されるデータおよび／またはデータの一部の冗長コピーの除去またはスクリーニングを可能にし、システムの有効ストレージ上にデータが均等に分散されるよう備えることができる。本願に開示されているように本発明のシステムおよび方法は、中心操作点、処理バランス、および／または全てのコンピュータ、スーパーコンピュータ、またはシステムに接続されたデータを格納および／または処理することができる他のデバイスにわたっている入出力（「Ｉ／Ｏ」）ロードを必要としない。本願で提供されるデータおよび／またはデータの一部の冗長コピーのスクリーニングは、システム内の他のデータ、システムに提示されるその後のデータまたはシステムによって格納されるその後のデータをスクリーニングするインテリジェント境界の作成、反復作成または保存を可能にする。
【００２６】
本発明は、インターネットのような公衆通信回線を使っている企業コンピューティングシステムのような分散コンピューティング環境に関して、図示され説明される。しかしながら、本発明の重要な特徴は、特定のアプリケーションのニーズに合うよう上方および下方に容易に基準化されるということである。したがって、相反するものに対して指示がない限り、本発明は従来のLANシステムのような小さなネットワーク環境と同様に相当に大きくかつ複雑なネットワーク環境にも適用できる。
【００２７】
図1に関して、本発明はネットワーク10上の新規のデータ記憶システムとともに利用できる。この図において、典型的なインターネットワーク環境10は、多重広域ネットワーク（「WAN」）14とローカルエリアネットワーク（「LAN」）16間の論理および物理接続によって形成されるグロ―バルインターネットワークを備えるインターネットを含んでよい。インターネットバックボーン12は、データトラフィックのバルクを運ぶメインラインおよびルーターを表す。バックボーン12は、例えばGTE、MCI、Sprint、UUNetおよびAmerica Onlineといった主要なインターネットサービスプロバイダ（「ISP」）によって管理されるシステムの最大ネットワークによって形成される。単独接続ラインはインターネットバックボーン12へのWAN 14およびLAN 16の接続を好都合に図示するのに用いられているが、現実には、複数パスでルート可能な物理接続が多重WAN 14とLAN 16間に存在することは理解されるべきである。これは、単一または多重故障ポイントに直面した際にインターネットワーク10を強力にする。
【００２８】
コンピュータ内の周辺デバイス間に実現される内部データ経路からネットワークコネクションを区別することは重要である。「ネットワーク」は汎用のシステムを備え、通常、ノード18で作動するプロセス間の論理接続を可能にする物理接続を切り替える。ネットワークによって実現される物理接続は、一般的に、ネットワークを使っているプロセス間で確立される論理接続から独立している。このように、ファイル転送、メール転送などに及ぶ異種のプロセスセットが、同じ物理的なネットワークを使うことができる。逆に言えば、ネットワークは、ネットワークを用いて論理的に接続されているプロセスには見えない異質の物理的なネットワーク技術のセットから形成可能である。ネットワークによって実現されるプロセス間の論理接続が物理接続から独立しているので、インターネットワークは長距離にわたる仮想的に無制限のノード数に容易に基準化される。
【００２９】
対照的に、システムバス、周辺コンポーネント相互接続（「PCI」）バス、インテリジェントドライブエレクトロニクス（「IDE」）バス、小型コンピューターシステムインターフェース（「SCSI」）バスなどといった内部データ経路は、コンピュータシステム内で特殊目的接続を実現する物理接続を画成する。これらの接続は、プロセス間の論理接続に対してフィジカルデバイス間の物理接続を実現する。これらの物理接続は、コンポーネント、該接続に結合できる限定された数のデバイス、および該接続を介して接続できる条件付きフォーマットのデバイス間の限られた距離によって特徴づけられている。
【００３０】
本発明の特定のインプリメンテーションで、記憶装置はノード18に配置されてよい。あらゆるノード18のストレージが、一つのハードディスクを備えてよく、或いは一つの論理ボリュームとして構成される多重ハードディスクを有する従来のRAIDデバイスのような管理された記憶システムを備えてもよい。重要なこととして、本発明は、ノード内で行なうのとは対照的に、ノードの全域にわたって冗長オペレーションを管理するので、任意のノード内のストレージの特定の構成はあまり重要ではない。
【００３１】
オプションとして、ノード18のうちの1つ以上が、分散型かつ共同的なやり方でノード18にわたってデータストレージを管理するストレージ割付け管理（「SAM」）プロセスを実現してもよい。SAMプロセスは、全体として、システムを集中制御しないか或いはほとんどしないように機能するのが望ましい。SAMプロセスは、ノード18全域にわたってデータ分布を提供し、RAID記憶サブシステムで見つけられるパラダイムと同様の方法で、ネットワークノード18全域にわたって故障を許容するやり方でリカバリを実現する。
【００３２】
しかしながら、SAMプロセスは、一つのノード内または一つのコンピュータ内ではなくノードの全域にわたって機能するので、該プロセスは従来のRAIDシステムよりも大きな故障許容とストレージ効率レベルを可能にする。たとえば、SAMプロセスは、ネットワークノード18、LAN 16またはWAN 14が利用できなくなった場合でさえも回復可能である。さらに、一部のインターネットバックボーン12が故障または輻輳によって利用できなくなった場合でさえも、SAMプロセスはアクセス可能なままであるノード18で分配されるデータを用いて回復可能である。このように、本発明はインターネットワークの強力な性質に影響を及ぼし、先例のない可用性、信頼性、障害の許容範囲および堅固性を提供する。
【００３３】
図2に関して、本発明が実現される典型的なネットワークコンピューティング環境のより詳細な概念図が表される。先行図のインターネットワーク10（またはこの図でのインターネット118）は、スーパーコンピュータ即ちデータセンター104からハンドヘルド即ちペンベースのデバイス114の範囲に及ぶ、異質のコンピューティング装置およびメカニズム102のセットの相互接続ネットワーク100を可能にする。このようなデバイスは異なるデータストレージのニーズを有しているが、それらはネットワーク100を介してデータを検索する能力を共有しており、それら自身のリソース内のデータに作用する。IBM互換機デバイス108、マッキントッシュデバイス110およびラップトップコンピューター112といったパーソナルコンピュータまたはワークステーションクラスデバイスと同様にメインフレームコンピュータ（例えばVAXステーション106およびIBM AS/400ステーション116）を含む異種のコンピューティング装置102は、インターネットワーク10およびネットワーク100を介して容易に相互接続する。図示されてはいないが、移動式および他のワイヤレスデバイスをインターネットワーク10に結合してもよい。
【００３４】
インターネットベースのネットワーク120は一組の論理接続を備えており、その幾つかはインターネット118を介して複数の内部ネットワーク122間に作られる。概念的に、インターネットベースのネットワーク120はWAN 14（図1）と同種であり、それは地理的に遠いノード間での論理接続を可能にしている。インターネットベースのネットワーク120は、インターネット118、または専用回線、Fibre Channelなどを含む他の公共および私用のWAN技術を用いて実現されてもよい。
【００３５】
同様に、内部ネットワーク122は概念的にLAN 16（図1）と同種であり、 それはWAN 14よりも限られた距離にわたっての論理接続を可能にしている。内部ネットワーク122は、 Ethernet、Fiber Distributed Data Interface（「FDDI」）、Token Ring、AppleTalk、Fibre Channel、などを含むさまざまなLAN技術を用いて実現されてもよい。
【００３６】
各内部ネットワーク122は、独立したノード（RAIN）エレメント124の一つ以上の冗長配列を接続し、RAINノード18（図1）を実現する。各RAINエレメント124は、プロセッサ、メモリおよび一つ以上の大容量記憶装置（例えばハードディスク）を備える。RAINエレメント124はまた、従来のIDE またはSCSIコントローラであってよく、RAIDコントローラのような管理コントローラであってもよいハードディスクコントローラを含む。RAINエレメント124は、物理的に分散してよく、冷却および電力といったリソースを共有している一つ以上のラックで同じ位置に配置されてもよい。各ノード18（図1）は他のノード18から独立しており、1つのノード18の故障または不稼働が他のノード18の可用性に影響を及ぼさず、1つのノード18に格納されているデータは他のノード18に格納されているデータから復元可能である。
【００３７】
特定の典型的なインプリメンテーションにおいて、RAINエレメント124は、PCIバスを支持するマザーボードおよび従来のATまたはATXケースに収容される256メガバイトのランダムアクセスメモリー（「RAM」）上に取り付けられるインテルベースのマイクロプロセッサーのような商品コンポーネントを用いたコンピュータを備えてもよい。SCSIまたはIDEコントローラは、マザーボード上でおよび／またはPCIバスに接続された拡張カードによって実現されてよい。コントローラがマザーボード上のみで実現される場合、PCI拡張バスがオプションとして使われてもよい。特定のインプリメンテーションにおいて、マザーボードは、各RAINエレメント124が最高4つ以上のEIDEハードディスクを含むよう、2つのマスタリングEIDEチャネルおよび2つの付加マスタリングEIDEチャネルを実現するのに用いられるPCI拡張カードを実現できる。特定のインプリメンテーションにおいて、各ハードディスクは、RAINエレメントにつき320ギガバイト以上の総記憶容量の80ギガバイトハードディスクを備えてよい。RAINエレメント124内のハードディスク容量および構成は、特定のアプリケーションのニーズを満たすよう容易に増大または低減できる。外被もまた、電源および冷却デバイス（図示せず）といった支持メカニズムを収容する。
【００３８】
各RAINエレメント124は、オペレーティングシステムを実行する。特定のインプリメンテーションにおいて、UNIXまたはLinuxのようなUnixバリアントオペレーティングシステムが、使われてよい。しかしながら、 DOS、マイクロソフトウインドウズ、アップルマッキントッシュOS、OS/2、マイクロソフトウインドウズNTなどを含む他のオペレーティングシステムを、パフォーマンスにおける予測可能な変更を行なうことで同等に置換え可能であることが企図される。選択されたオペレーティングシステムは、アプリケーションソフトウェアおよびプロセスを実行するプラットホームを形成し、ハードディスクコントローラを介して大容量記憶域にアクセスするファイルシステムを実現する。様々なアプリケーションソフトウェアおよびプロセスが各RAINエレメント124上で実現され、適切なネットワークプロトコル（例えばユーザーデータグラムプロトコル（「UDP」）、伝送制御プロトコル（TCP）、インターネットプロトコル（IP）など）を用いたネットワークインターフェースを介して、ネットワークの接続性を提供できる。
【００３９】
図3に関しては、ロジックフローチャートが、本発明のハッシュファイルシステムにコンピュータファイルをエントリするステップを表すために示されており、ファイルのハッシュ値が、セットまたはデータベースに予め維持されるファイルのハッシュ値と照合される。
【００４０】
プロセス200は、コンピューターファイルデータ202（例えば「ファイルA」）を本発明のハッシュファイルシステム（「HF」）に入力することから始まり、ハッシュ関数がステップ204で実行される。次いで、ファイルAのハッシュを表すデータ206が判断ステップ208でハッシュファイル値を含むセットのコンテンツと比較される。データ206が既にセットにある場合、ファイルのハッシュ値はステップ210でディレクトリリストに加えられる。ハッシュ値を含み、データに対応しているセット212のコンテンツは、判断ステップ208の比較演算のために既存のハッシュ値214の形で提供される。一方、ファイルAのハッシュ値がその時点でセットに存在しない場合、ファイルは、ステップ216で（以下でより完全に説明されるように）ハッシュピースに分割される。
【００４１】
図4に関しては、更なるロジックフローチャートが、デジタルシーケンス（例えばファイルまたは他のデータシーケンス）をブレークアップしてハッシュピースにするプロセス300でのステップを表すために提供される。このプロセス300は、多数のデータピースと同様にそれに対応している確率的に固有のハッシュ値を各ピースに対して最終的に生成することになる。
【００４２】
ファイルデータ302は、システムの他のピースとの共通性あるいは後にステップ304で共通していることが明らかになるピースの可能性に基づいたピースに分割される。ファイルデータ302に関するステップ304のオペレーションの結果は、代表的な例において、A1〜A5と名づけられた4つのファイルピース306を生成する。
【００４３】
ファイルピース306の各々は、次いで、A1〜A5のピース306の各々に確率的に固有の数が割り当てられるよう、個々のハッシュ関数オペレーションを通して各々を配置することによってステップ308で操作される。ステップ308のオペレーションの結果、ピース306（A1〜A5）の各々は、関連づけられた、確率的に固有のハッシュ値310（それぞれA1ハッシュ〜A5ハッシュとして示される）を有することになる。ステップ304のファイル分割プロセスは、ここで開示されている固有の「スティッキービット」オペレーションとともに、更に詳細に以下で説明される。
【００４４】
更に図5に関しては、別のロジックフローチャートが、ファイルの各ピース306のハッシュ値310を、セット212で維持されている既存のハッシュ値214と比較するプロセス400を表すために示される。特に、ステップ402で、ファイルの各ピース306のハッシュ値310は既存のハッシュ値214および新しいハッシュ値408と比較され、対応する新しいデータピース406がセット212に加えられる。このように、データベースセット212に予め存在していないハッシュ値408が、それらに関連づけられたデータピース406と共に加えられる。プロセス400はまた、全てのファイルピースに対する一つのハッシュ値が様々なピース306のハッシュ値310と同値であることを示しているレコード404を生成することになる。
【００４５】
更に図6は、ファイルハッシュまたはディレクトリリストハッシュ値を既存のディレクトリリストハッシュ値と比較し、新しいファイルまたはディレクトリリストハッシュ値をデータベースディレクトリリストに加えるプロセス500を図示している別のロジックフローチャートを示す。プロセス500は、ファイル名、ファイルメタデータ（例えば日付、時間、ファイルの長さ、ファイルタイプ等）およびディレクトリの各項目のファイルのハッシュ値の累積リストを備える記憶データ502上で機能する。ステップ504で、ハッシュ関数はディレクトリリストのコンテンツに実行される。判断ステップ506は、ディレクトリリストのハッシュ値が既存のハッシュ値214のセット212であるかどうかを判断するよう機能する。判断が肯定である場合、プロセス500は、別のファイルハッシュまたはディレクトリリストハッシュをディレクトリリストに加えるために戻る。これに対して、ディレクトリリストのハッシュ値がデータベースセット212にすでにない場合、ディレクトリリストのハッシュ値およびデータはステップ508でデータベースセット212に加えられる。
【００４６】
更に図7に関しては、代表的なコンピュータファイル（すなわち「ファイルA」）のピース306とそれらに対応するハッシュ値310の比較600が、典型的なファイルの特定ピースの編集の前後双方で示される。この例では、レコード404はファイルA1〜A5のピースの各々のハッシュ値310と同様にファイルAのハッシュ値を含む。ファイルAの代表的な編集は、306AのファイルピースのピースA2（A2-bによって表される）のデータの変化と共にハッシュ値310Aのハッシュ値A2-bの対応する変化を生成可能である。編集されたファイルピースは、ファイルAの修正ハッシュ値およびピースA2-bの修正ハッシュ値を含む更新済みレコード404Aを生成する。
【００４７】
更に図8に関しては、本発明のシステムおよび方法によって導き出される複合データ（例えば複合データ702および704）は明示的に表されるデータ706と実質的に同じものであるが、「レシピ」すなわち式によって作成されるという事実を図示している概念図700が示される。図示される例において、このレシピは、対応するハッシュ708によって表されるデータの連結またはハッシュによって表されるデータを用いた関数の結果を含む。データブロック706は示されるように可変長数量であってよく、ハッシュ値708はそれに関連づけられたデータブロックから導き出される。既に述べたように、ハッシュ値708は対応するデータピースの確率的に固有のＩＤであるが、全く固有のＩＤがその代わりに使われるか、或いは確率的に固有のＩＤと混在させることもできる。複合データ702、704はまた、多くのレベルが深い他の複合データを参照でき、一方、複合データのハッシュ値708はレシピが生成するデータの値またはレシピ自体のハッシュ値から導き出されることが可能であることもまた注目されるべきである。
【００４８】
更に図9に関しては、本発明のハッシュファイルシステムおよび方法がデータ802を編成し、それらが表すデータへのポインタとしてハッシュ値806を使用することによって冗長シーケンスの再利用を最適化するのにどのように利用できるかを別の概念図800で示していて、データ802は、明確なバイトシーケンス808（原子データ）か或いはシーケンスのグループ（コンポジット）804として表されてよい。
【００４９】
図800は、レシピおよびあらゆるレベルで再利用されるデータの強大な共通性を図示する。本発明のハッシュファイルシステムの基本構成は、本質的に、ハッシュ値806が従来のポインターの代わりに使われる「ツリー」または「ブッシュ」である。ハッシュ値806はレシピで使われて、データまたはそれ自体がレシピでありえる別のハッシュ値を示している。したがって、本質において、レシピは他のレシピを示し、他のレシピはさらに他のレシピを示し、最終的に幾つかの特定データを示し、その特定データ自体は更に多くのデータを示す他のレシピを示してよく、最後にはデータだけにかかる。
【００５０】
更に図10に関しては、典型的な160ビットのハッシュ値902のハッシュファイルシステムアドレス変換機能の実例となる簡略図900が示される。ハッシュ値902は図示されるように前部904および後部906を備えるデータ構造を含み、図900は対応するデータを含むシステムにおいて特定のノードのロケーションに行くためにハッシュ値902の使用を可能にするよう用いられる特定の「1のうちの0」オペレーションを図示する。
【００５１】
図900は、ハッシュ値902のデータ構造の前部904がストライプ識別（「ID」）908へのハッシュ・プレフィックスを示すのにどのように用いられることができるか、また、次に、ストライプIDをIPアドレスにマップし、IDクラスをIPアドレス910にマップするのにどのように利用されるかを図示する。この例では、「S2」はインデックスノード37 912のストライプ2を示す。ノード37のインデックスストライプ912は、次いで、リファレンス番号914によって示されるデータノード73のストライプ88を示す。次いで、オペレーションにおいて、ハッシュ値902自体がシステムのどのノードが関連したデータを含むのかを示すのに使用でき、ハッシュ値902の別の部分はどのデータストライプがその特定のノードにあるのかを示すのに使用でき、ハッシュ値902の更に別の部分はそのストライプ内のどこにデータが存在するのかを示すのに使用できる。この３ステッププロセスを通して、ハッシュ値902によって表されるデータがシステムに既に存在するかどうかを迅速に判断することができる。
【００５２】
更に図11に関しては、本発明のシステムおよび方法で使用されるインデックスストライプ分割機能1000の簡略的な典型図が示される。この図において、典型的な機能1000は、ストライプ1002（S2）を1つのストライプが充分にいっぱいになるように2つのストライプ1004（S2）と1006（S7）に効果的に分割するのに使用可能であることが示されている。この例では、奇数のエントリはストライプ1006（S7）に動かされ、一方偶数のエントリはストライプ1004に残る。この機能1000は、システム全体のサイズが大きくなり複雑さが増すにつれて、ストライプエントリをどう処理することができるかを示す1つの例である。
【００５３】
更に図12に関しては、本発明のシステムおよび方法の全体機能の簡略図1100は、例えば、第１日に多数のプログラムおよびドキュメントファイル1102Aおよび1104Aを有する代表的な家庭用コンピュータのデータのバックアップに用いられているのを示しており、プログラムファイル1102Bは第２日に同じものを残し、一方、ドキュメントファイル1104Bのうちの1つは第２日で編集され（Y.doc）、第３のドキュメントファイル（Z.doc）が加えられる。
【００５４】
図1100は、コンピュータファイルシステムがピースに分けられ、次いでピースからオリジナルデータを復元するためにグロ―バルデータ保護回路（「gDPN」）上に一連のレシピとしてリストされることができる方法の詳細を示す。この非常に小さいコンピュータシステムは、「スナップショット」の形で「第１日」で、次いでその後「第２日」で示される。「第１日」上で「プログラムファイルH5」および「マイドキュメントH6」が数字1106で図示され、前者はレシピ1108によって表されており、第１の実行可能ファイルはハッシュ値H1 1114で表され、第２の実行可能ファイルはハッシュ値H2 1112で表されている。ドキュメントファイルはハッシュ値H6 1110によって表され、第１のドキュメントはハッシュ値H3 1118で表され、第２のドキュメントファイルはハッシュ値H4 1116によって表されている。その後、「第２日」で数字1120によって示される「プログラムファイルH5」および「マイドキュメントH10」は、「プログラムファイルH5」は変更されていないが、「マイドキュメントH10」は変更されたことを示している。数字1122によって示されるH10は、「X.doc」が依然としてハッシュ値H3 1118で表されていることを示し、一方「Y.doc」は今では数字1124においてハッシュ値H8で表されていることを示している。新しいドキュメントファイル「Z.doc」は、数字1126においてハッシュ値H9で表される。
【００５５】
この例では、第２日で幾つかのファイルが変更され、他は変更されていないことがわかる。変更されたファイルにおいて、それらのうちの幾つかのピースは変更されておらず、他のピースは変更されている。本発明のハッシュファイルシステムの使用を通して、コンピュータシステムの「スナップショット」が第１日で作成可能であり（次に存在できるようコンピュータファイルの再生に必要なレシピを生成する）、次いで第２日で以前の日のレシピの幾つかの再使用、他のレシピの再定式化、ならびに新規のレシピの追加によって、その時点でのシステムが記述される。このように、コンピュータシステムは第１日または第２日双方のいかなる時ならびにいかなる後続日でもその全体において再現可能である。
【００５６】
更に図13に関しては、多数の「スティッキーバイト」1204によってマークされる特定のドキュメントファイルの様々なピースの比較1200が、編集前（第１日 1202A）および編集後（第２日 1202B）の双方で示されており、それによってピースのうちの一つが変更され、他のピースは同じままである。
【００５７】
たとえば、第１日に、ファイル1202Aは、可変長ピース1206（1.1）、1208（1.2）、1210（2.1）、1212（2.）、1214（2.3）および1216（3.1）を備える。第２日では、ピース1206、1208、1210、1214および1216は同じままであり（したがって同じハッシュ値を有する）、一方、ピース1212は編集されてピース1212Aを生成する（したがって異なるハッシュ値を有する）。
【００５８】
データ・スティッキーバイト（または「スティッキーポイント」）は、共通ブロック要素がコンピュータ間で通信する必要なく複数の関連したおよび無関連のコンピュータで見つかるようコンピュータファイルをサブ分割するユニークな完全自動化の方法である。スティッキーポイントを見つける手段は、本質的に完全に数学的であり、ファイルのデータコンテンツに関係なく均等かつ適切に実行される。本発明のハッシュファイルシステムでは、全てのデータオブジェクトはインデックスを付けられ、格納され、例えば（限定されるものではないが）MD4、MD5、SHAまたはSHA-1といった業界標準チェックサムを用いて検索されてよい。オペレーションにおいて、2つのファイルが同じチェックサムを有する場合、それらが同一ファイルであることは非常に可能性が高いと考えられ得る。本願で開示されているシステムおよび方法を用いると、データスティッキーポイントは、標準的な数理分布およびターゲットサイズが僅かな割合である標準偏差で生成できる。
【００５９】
データスティッキーポイントは、統計学的には稀なnバイトの配列である。この場合、現在のマイクロプロセッサー技術でのインプリメンテーションにおいて容易であるという理由から、例においては32バイトが使われている。
【００６０】
32ビットのローリングハッシュは、ファイル「f」に対して生成可能である：//f[i]はファイル「f」のi番目のバイトである。
//scrambleは各々が32ビット長の整数の256エントリアレーである。
//これらの整数は均一に範囲にまたがるよう一般的に選択される。
int t=8//後置0のターゲットナンバである。
int hash = 0;
int sticky bits;
for(int i=O; i<filesize; i++）
hash = hash >> 1 |scramble[f[i]];
//ファイルの各バイトで、ハッシュはファイルのローリングハッシュを表す。
sticky bits = (hash - 1)^hash;
//sticks bitsは変数であり、「ハッシュ」の後置0の数に対応するハッシュの数のうちの一つを有する。
number of bits = count ones(stick-bits);
if(number of bits > t)
output sticky point(i);
}
【００６１】
スティッキーポイントは、バイナリーで表されるハッシュを有するターゲットナンバとして後置ゼロの数を少なくとも有するローリングハッシュになるよう画成される。統計学的にいうと、このアルゴリズムは、2^tで間隔をあけられるポイントを見つけ、ここでtは後置ゼロのターゲットナンバである。この例において、t=8の場合、アルゴリズムは平均で2^8=256バイト離れているスティッキーポイントを見つける。
【００６２】
32ビットのローリングハッシュは、fファイルに対して生成でき、ここで：
f[i] はファイルfのi番目のバイトであり、
scramble は、各々がnビット長のランダムエレメントの256エントリアレーである：
int t=8//後置ゼロのターゲットナンバ
int target distance = 256; //2の8乗
int hash = 0;
int sticky bits;
int distance = 0;
int last point = 0;
for(int i=O; i<filesize; i++) [
hash = hash >> 1| scramble[f[i]];
//ファイルの各バイトでハッシュはファイルのローリングハッシュを表す。
sticky bits = (hash - 1)^hash;
//sticks bitsは変数であり、「ハッシュ」の後置0の数に対応する数のうちの一つを有する。
number of bits = count ones(stick bits);
distance = i-last point;
if(number of bits * distance/target distance >t)
last point =i;
output sticky point(i);
}
}
【００６３】
本発明のハッシュファイルシステムを実現するのに利用されるハッシュ関数は適度に複雑な計算を必要とするが、それは現在のコンピュータシステムの能力の範囲内で充分である。ハッシュ関数は本質的に確率に基づいているので、2つの異なるデータオブジェクトが偶然同一のハッシュ値を有した場合、どんなハッシュ関数でもあるいは誤った結果を生じるかもしれない。しかしながら、本願で開示されているシステムおよび方法は、衝突の確率を信頼のおける使用のために許容できるレベル（すなわち10の24乗に1回の機会）であり、従来のコンピュータハードウェアオペレーションで容認されているエラー率よりはるかに少ないレベルまで低減する、よく知られかつ調査されたハッシュ関数を用いてこの問題を軽減する。
【００６４】
本願で用いられるように、用語「インターネットインフラ」は様々なハードウェアおよびソフトウェアメカニズムを含んでいるが、該用語は、主に、一つのネットワークノードから別のネットワークノードにデータパケットを移動させる機能を有するルーター、ルーターソフトウェアおよびこれらのルーター間の物理リンクを指す。また、本願で用いられるように、「デジタルシーケンス」はコンピュータプログラムファイル、コンピュータアプリケーション、データファイル、ネットワークパケット、マルチメディア（オーディオおよびビデオを含む）といったストリーミングデータ、テレメトリーデータ、およびデジタルまたは数字シーケンスによって表されることができる他のあらゆるデータフォームを含むことができるが、これに限定されるものではない。本発明のハッシュファイルシステムおよび方法によって生成される確率的に固有の識別子はまた、URLとしてネットワークアプリケーションで使われてもよい。
【００６５】
本発明のシステムおよび方法の特定のインプリメンテーションおよびアプリケーションに関連して本発明の原理を以上で説明してきたが、前述の説明は例としてのみ成されており、本発明の範囲を限定するものではないことは明白に理解されたであろう。特に、前述の開示内容の教示が他の変形実施例を当業者に示唆していることは理解されたであろう。このような変形実施例は、それ自体が既に知られており、本願で既に説明された特徴の代わりにまたはそれに加えて使用可能な他の特徴を含んでもよい。特許請求の範囲は本出願において特定の特徴の組合せに対して明確に述べているが、本願における開示の範囲はまた、特許請求の範囲と同一の発明に関連があるにせよ、また本発明が直面したものと同じ技術的な問題の全てを軽減するにせよ、当業者には明らかな明示的または暗示的に開示されている特徴のあらゆる新規な特徴または組合わせ、またはそれを一般化した例または変形実施例を含むことを理解されたい。出願人は、これによって本出願のまたはそこから導き出される更なる出願の全ての手続き中に、前記の特徴および／または前記の特徴の組合せを新しい特許請求の範囲に発展させる権利を確保する。
【図面の簡単な説明】
【図１】  本発明のシステムおよび方法が実現可能な代表的なネットワーク化されたコンピュータ環境のハイレベル図である。
【図２】  本発明のシステムおよび方法を利用するのに可能な操作環境のより詳細な概念図であり、あらゆる数のコンピュータまたはデータセンターで維持されるファイルが、例えば地理的に多様なロケーションに位置する多数の独立ノードの冗長配列（「RAIN」）ラックへのインターネット接続を通して分散型コンピュータシステムに格納されてよい。
【図３】  本発明のハッシュファイルシステムにコンピュータファイルを入力するステップを表すロジックフローチャートであり、ファイルのハッシュ値は、セットまたはデータベースに予め維持されているファイルのハッシュ値と照合される。
【図４】  ファイルまたは他のデータシーケンスをハッシュピースにブレークアップするステップを表す更なるロジックフローチャートであり、多数のデータピースとそれに対応している確率的に固有のハッシュ値を各ピースに対して生成することになる。
【図５】  ファイルの各ピースのハッシュ値と、セット（またはデータベース）の既存のハッシュ値との比較を表す別のロジックフローチャートであり、レコードの生成物は、全てのファイルに対する一つのハッシュ値と様々なピースのハッシュ値が同等であることを示しており、新しいデータピースおよびそれに対応する新しいハッシュ値がセットに加えられる。
【図６】  ファイルハッシュまたはディレクトリリストハッシュ値と既存のディレクトリリストハッシュ値とを比較し、新しいファイルまたはディレクトリリストハッシュ値をセットディレクトリリストに加えるステップを図示する別のロジックフローチャートである。
【図７】  典型的なファイルの特定ピースの編集の前後双方における、代表的なコンピュータファイルのピースとそれらに対応しているハッシュ値との比較である。
【図８】  本発明のシステムおよび方法によって導出可能な複合データは、明示的に表示されるデータと効果的に同一であるが、代わりに、「レシピ」（例えばその対応するハッシュによって表されるデータの連結、またはハッシュによって表されるデータを用いた関数の結果）によって生成されてもよいという事実の概念図である。
【図９】  本発明のハッシュファイルシステムおよび方法がデータを編成し、それらが表すデータへのポインタとしてハッシュ値を使用することによって冗長シーケンスの再利用を最適化するのにどのように利用できるかを表す別の概念図であり、データは、明確なバイトシーケンス（原子データ）か或いはシーケンスのグループ（コンポジット）として表されてよい。
【図１０】  典型的な160ビットのハッシュ値のハッシュファイルシステムアドレス変換機能の実例となる簡略図である。
【図１１】  本発明のシステムおよび方法で使用されるインデックスストライプ分割機能の簡略的な典型図である。
【図１２】  本発明のシステムおよび方法の全体機能の簡略図であり、第１日に多数のプログラムおよびドキュメントファイルを有する代表的な家庭用コンピュータのデータのバックアップに用いられているのを示しており、ドキュメントファイルのうちの1つが第２日で編集され、第３のドキュメントファイルが加えられる。
【図１３】  編集前および編集後の双方における、多数の「スティッキーバイト」によってマークされる特定のドキュメントファイルの様々なピースの比較であって、それによってピースのうちの一つが変更され、他のピースは同じままである、図を示す。
【図１】
0004846156.tif 000002
【図２】
0004846156.tif 000003
【図３】
0004846156.tif 000004
【図４】
0004846156.tif 000005
【図５】
0004846156.tif 000006
【図６】
0004846156.tif 000007
【図７】
0004846156.tif 000008
【図８】
0004846156.tif 000009
【図９】
0004846156.tif 000010
【図１０】
0004846156.tif 000011
【図１１】
0004846156.tif 000012
【図１２】
0004846156.tif 000013
【図１３】
0004846156.tif 000014