"分散ファイルシステムと、マップリデュースシステムと、を含み、各マップ機能が前記分散ファイルシステムに書き込みを行い、各リデュース機能が前記分散ファイルシステムから入力を読み込む、マップリデュース互換可能なシャッフル機能。前記分散ファイルシステムが、生のブロック記憶を一緒にまとめ、コンテナおよびトランザクションログに記憶機構を提供する、複数の記憶プールと、データの複製、再配置、およびトランザクション的な更新のいずれかのために構成された複数のコンテナと、複数のファイルサーバ内で特定のコンテナを配置するように構成され、コンテナの複製どうしの優先度は、コンテナのコンテンツのトランザクション的な更新を構成するように定められる、コンテナ位置データベースと、をさらに含む、請求項1に記載のシャッフル機能。データ移動の制御、ミラーの生成、および制御とポリシー情報の保持、のいずれかを容易にするように構成された複数のボリュームをさらに含む、請求項1に記載のシャッフル機能。ディレクトリ、コンテナ位置マップ、および圧縮されたファイル内のオフセットマップ、のいずれかに関するデータへのキーに関連するように構成された複数のキー値記憶をさらに含む、請求項1に記載のシャッフル機能。複数のコンテナのそれぞれがどこに配置されているかについての情報を維持するように構成されたコンテナ位置データベースCLDBと、各クラスタノードが1つ以上の記憶プールを含み、各記憶プールがゼロ個以上のコンテナを含む、複数のクラスタノードと、前記コンテナ内でデータを構成するための複数のiノードと、を含む、マップリデュース互換可能な分散ファイルシステム。前記コンテナが、各複製チェーンに関するマスタとして指定された1つのコンテナと共に他のクラスタノードに複製される、請求項5に記載の分散ファイルシステム。前記CLDBが複数の余分なサーバによって維持され、CLDB内のデータ自体が、よく知られているコンテナ内のiノードとして記憶されている、請求項5に記載の分散ファイルシステム。CLDBノードが、前記コンテナのすべてに関する情報を少なくとも含むデータベースを維持するように構成され、前記コンテナのすべてに関する前記情報が、コンテナの複製を有するノード、および各コンテナに関する複製チェーンの順番である、請求項7に記載の分散ファイルシステム。前記CLDBが、各コンテナに関するすべてのトランザクションを制御するマスタノードに該コンテナを割り当てる、前記CLDBが、複製を保持するノードのチェーンを指定する、前記複製の1つが故障するかマスタCLDBノードから分離された場合、それは複製チェーンから取り除かれる、マスタが故障するか分離された場合、新しいマスタが指定される、複製チェーンから取り除かれた後で復帰した任意のノードは、ノードが復帰したときにチェーンがまだ別の複製チェーンを必要とする場合には、複製チェーンの最後に再挿入される、第1の所定の期間内にノードが復帰した場合、問題となっているコンテナを複製する新しいノードが指定されることはなく、チェーンはなお複製チェーンを必要とする、第2の、より長い所定の期間内にノードが故障した場合、CLDBはチェーン内に位置を占める他のノードを指定することができる、のいずれかに従うポリシー制約に前記CLDBが合致するように、コンテナ内のデータの複製としてノードを割り当てるように前記CLDBが構成される、請求項5に記載の分散ファイルシステム。コンテナマスタがトランザクション的に複製チェーンの更新を制御するように構成される、請求項9に記載の分散ファイルシステム。すべてのiノードデータ構造および間接データB木が、トランザクションを失ったコンテナ複製の更新を容易にするバージョン番号を有する、請求項5に記載の分散ファイルシステム。データが分散ファイルシステム内の、ディスク全体、フラッシュメモリシステム、それらのいずれかのパーティション、および従来のファイルシステムに記憶された個々のファイル、のいずれかを表すブロック装置を含む複数のブロックアドレス可能なデータ記憶装置上に記憶され、各データ記憶装置が、比較的小さい、固定サイズのブロックのデータのランダムな読み書きをサポートする、請求項5に記載の分散ファイルシステム。前記各記憶プールが、前記記憶プール内のいくつかのよく知られた位置に複製されるスーパーブロック内にそれぞれが記憶された、複数のビットマップ空間、複数のログ空間、およびコンテナディスクオフセットへのCIDのマップを含み、前記ビットマップ空間は、前記記憶プールに関する複数のブロック割り当てビットマップへのポインタを含み、前記ログ空間は、前記記憶プールに関するトランザクションログを記憶するために用いられる前記記憶プールの部分へのポインタを含み、ディスクオフセットへのコンテナIDCIDの前記マップは、前記記憶プール内のディスクオフセットを発見するようにコンテナIDを検索する機構を含む、請求項5に記載の分散ファイルシステム。各FIDが特定のコンテナ内のiノードを参照し、各FIDがコンテナID、iノード番号、およびiノードが異なる目的で再使用されてもFIDのコンテンツを一意的にするように選ばれた整数を含む、複数のファイル識別子FIDをさらに含む、請求項5に記載の分散ファイルシステム。各iノードが、所有者、許可、親FID、オブジェクトのタイプ、およびサイズを含む各オブジェクトの種々の特徴を記述する属性を含むコンポジットデータ構造をさらに含み、オブジェクトのタイプはローカルファイル、チャンクファイル、ディレクトリ、キー値記憶、シンボリックリンク、またはボリュームマウントポイントのいずれかを含み、前記iノードはさらに、オブジェクト内のデータのバイトの最初の組を含むディスクブロックへのポインタを含み、前記ポインタのそれぞれは、前記ポインタと共に記憶された関連するコピーオンライトビットを含み、前記iノードはさらに、間接的なデータへの参照を含み、該参照は、ローカルファイルの場合には、B木に関するコピーオンライトビットと共にオブジェクトデータを含む該B木へのポインタを含むことができ、チャンクファイルの場合には、ファイルのコンテンツを含む他のコンテナ内のローカルファイルを参照するFIDを含むFIDマップと呼ばれるローカルファイルへのポインタを含み、前記iノードはiノードから参照される任意の構造に関する最新のバージョン番号のキャッシュをさらに含み、前記バージョン番号は複製およびミラーリングにおいて用いられるように構成される、請求項5に記載の分散ファイルシステム。前記チャンクファイルが、多くのコンテナ内に記憶されたチャンクからなるファイルを含み、各チャンクはローカルファイルおよび、これらのローカルファイルへの参照の列へとつながるチャンクファイルiノードからの参照として表される、請求項15に記載の分散ファイルシステム。前記シンボリックリンクが、ファイルの名前を含み任意の分散ファイルシステムオブジェクトを指示可能なローカルファイルとして記憶される、請求項15に記載の分散ファイルシステム。ボリュームマウントが、マウントされるボリュームの名前を含むローカルファイルとして記憶される、請求項15に記載の分散ファイルシステム。前記分散ファイルシステムが読み書きアクセスファイルシステムとして構成され、ランダムな更新および読み込みが、クラスタ内の任意のノードから、および/または、クラスタ内の他の装置への自由なアクセスを有する任意の装置から起こる、請求項5に記載の分散ファイルシステム。前記分散型ファイルシステムがステートレスなアクセスのために構成される、請求項5に記載の分散ファイルシステム。少なくとも1つのNFSゲートウェイをさらに含み、前記分散型ファイルシステムがNFSネットワークプロトコルを介してのアクセスのために構成される、請求項20に記載の分散ファイルシステム。複数のNFSゲートウェイと、調整サーバによって前記NFSゲートウェイが、どの前記NFSゲートウェイがどのIPアドレスをホスティングするかを協調的に決定する、前記調整サーバと、をさらに含む、請求項21に記載の分散ファイルシステム。すべてのNFSサーバが分散ファイルシステム内のすべてのファイルにアクセス可能な、請求項22に記載の分散ファイルシステム。分散ファイルシステムを介してアクセスされるすべてのファイル名が、共通のプレフィックスで始まり、その後にクラスタ名および前記クラスタ内のファイル名が続き、前記NFSゲートウェイは、各アクセス可能なクラスタに対応するバーチャルファイルを、前記共通のプレフィックスに関連づけられたトップレベルバーチャルディレクトリに表示させるように構成される、請求項22に記載の分散ファイルシステム。上記システムのいずれも、マップリデュースシステムによって課せられた必要なファイル生成速度をなおもサポートするトランザクション的な更新およびクラスタワイドなスナップショットを可能にする完全に分散的な複製ファイルシステムを提供することができない。マップリデュースプログラムはそのようなファイルシステムを用いて実行されうるが、マップリデュース計算に関連するロードのいくつかをファイルシステムから外して二次記憶システムに移動させることによってのみ実行されうる。ファイル更新がサポートされる故障耐性はこれらのシステムにおいても、商品レベルの設備における大規模動作を許容するには十分ではない。トランザクション的な読み書き更新動作にチャンクファイルの複製および膨大なファイル生成速度を提供する分散ファイルシステムは、マップリデュース計算クラスタに関して大きな技術的利点を提示する。本明細書で開示されたファイルシステムは、初めてこのことを可能にする多くの技術的革新性を有し、したがって、マップリデュース互換可能な分散ファイルシステムがどのように形成されうるかの例を提供する。このファイルシステムは、それぞれが次のレイヤーが形成される基礎を提供する連続したコンポーネントレイヤーからなる。それらは以下を含む。記憶プールとも呼ばれるプリミティブ記憶レイヤー。記憶プールは生のrawブロック記憶を接合しknit、コンテナおよびトランザクションログに関する記憶機構を提供する。記憶プールは個々のファイルサーバによって操作される。データ複製、再配置、およびトランザクション的な更新の基本的原理を提供するコンテナ。すべてのファイルサーバの中からコンテナを発見することを可能にし、コンテナのコンテンツのトランザクション的な更新を体系化する目的でコンテナの複製の中の優先度を定義する、コンテナ配置データベース。データの配置の制御、スナップショットおよびミラーの生成の制御、および様々な制御およびポリシー情報の保持を容易にする、ボリューム。ディレクトリ、コンテナ位置マップ、および圧縮されたファイル内のオフセットマップなどの多くの目的のためにキーをデータに関連づけることを可能にする、キー値記憶。本明細書で開示された分散ファイルシステムは、トランザクション的な読み書き更新動作にチャンクファイルの複製および膨大なファイル生成速度を提供し、マップリデュース計算クラスタに関して大きな技術的利点を提供する。主題のファイルシステムは、初めてこのことを可能にする多くの技術的革新性を有し、したがって、マップリデュース互換可能な分散ファイルシステムがどのように形成されうるかの例を提供する。図2は、シャッフル203が分散ファイルシステム内に含まれ、入力および出力が本発明による分散ファイルシステム内にあるかないかのいずれかである、マップリデュース処理の概略を示すブロック概略図である。このファイルシステムは、それぞれが次のレイヤーが形成される基礎を提供する連続したコンポーネントレイヤーからなる。それらは以下にさらに詳細に記載され、以下のものを含む。記憶プールとも呼ばれるプリミティブ記憶レイヤー。記憶プールは生のrawブロック記憶を接合しknit、コンテナおよびトランザクションログに関する記憶機構を提供する。記憶プールは個々のファイルサーバによって操作される。データ複製、再配置、およびトランザクション的な更新の基本的原理を提供するコンテナ。すべてのファイルサーバの中からコンテナを発見することを可能にし、コンテナのコンテンツのトランザクション的な更新を体系化する目的でコンテナの複製の中の優先度を定義する、コンテナ配置データベース。データの配置の制御、スナップショットおよびミラーの生成の制御、および様々な制御およびポリシー情報の保持を容易にする、ボリューム。ディレクトリ、コンテナ位置マップ、および圧縮されたファイル内のオフセットマップなどの多くの目的のためのデータにキーを関連づけることを可能にする、キー値記憶。加えて、これらの基本的なコンポーネントの実装を容易にする他のデータ構造がある。これらの追加のデータ構造は、本明細書に開示された分散ファイルシステムの基本的なコンポーネントおよび能力について以下に記載する際に、話題になるので説明する。コンテナ位置データベース図3は、コンテナ位置データベースCLDB301およびクラスタノード302、304を有する分散ファイルシステム203の構造を示すブロック概略図である。各クラスタノードは1つ以上の記憶プール303、305を含む。各記憶プールは0以上のコンテナ309、312を含んでもよい。データはiノード、例えば306、308、310、311を用いてコンテナ内に構成される。コンテナは各複製チェーンごとに、マスタとして指定された1つのコンテナ、例えばコンテナ306によって他のクラスタノードに複製される。CLDBは各コンテナがどこに位置するかについての情報を保持する。CLDBはいくつかの重複するサーバに保持され、CLDB内のデータ自身が、よく知られているコンテナ内のiノードとして記憶される。本明細書に記載された分散ファイルシステムにおけるクラスタ内のノードの断片は、コンテナ位置データベースCLDBを記憶するように指定される。小さいクラスタにおける故障耐性のためには、少なくとも3つのそのようなノードが指定されるのが通常である。より大きいクラスタに関しては、5つのノードが通常指定される。CLDBノードはシステム内のすべてのコンテナに関する少なくとも以下の情報を含むデータベースを維持するように働く。-コンテナの複製を有するノード。-そのコンテナの1つの複製が各ノード上で利用可能であるコンテナのバージョン。-各コンテナの複製チェーンの順序づけ。さらに、CLDBノードはそのうち1つをマスタとして働くように指定する。このトランザクション的なマスタは、コンテナ位置データベース自身を保持する特別なコンテナに関する複製チェーンのヘッドとして設定される。コンテナ位置データベースへのすべての更新は、以下に詳細に述べる通常のコンテナ複製機構を用いて調整される。CLDBマスタの指定は調整サービスに基づくリーダ選択を用いて行われる。一実施形態では、調整サービスはApacheZookeeperを使用し、それ自身はPaxosの簡潔にされた形態を使用し、ノードの故障またはネットワークパーティションの存在を一貫して保証する。ApacheZookeeperは、トランザクションがそのコンポーネントノードの大多数において行われ、その結果として限られた更新頻度でのみ取り扱えばよいことを、確実に保証する。分散ファイルシステムはマスタCLDBノードを確実に指名するようにZookeeperのみを用いるため、これは限定ではない。したがって、CLDB自身は大多数よりは少ないコピーただ1つのコピーであることさえもあると共に実行され、最も新しいものをだれが有するかを識別するためには外部の選抜されたプロバイダに頼るしかない。CLDBはコンテナが移動する際に、ノードが故障した際に、または周期的なブロックの変更報告の結果としてのみ更新される。この結果は、非常に大きなクラスタに対してさえも、比較的小さい更新頻度をもたらす。コンテナ位置が無期限にキャッシュされうるため、CLDBのクエリ頻度はなおさら小さい。期限切れの情報が用いられるといつも、コンテナ位置情報におけるキャッシュの整合性エラーが検出され、明示的なキャッシュ一貫性プロトコルは要求されない。コンテナバージョン情報はノードがクラスタを再結合する場合にのみ要求され、したがって、ファイルサーバがキャッシュする必要があるもののすべては、コンテナの現実の位置である。CLDBが非常に低い更新頻度およびクエリ頻度を有することに加えて、CLDB自身が、例えばHadoopネームノードと比較して、非常に小さい。Hadoopネームノードは、対照的に、各ファイルのすべてのブロックに関するブロック位置と同様に、すべてのファイルに関するメタデータおよびブロック数を監視しなければならない。ブロックは一般に200MB以下のサイズであるため、Hadoopネームノードによって監視されるべきアイテムの総数はかなり大きい。対照的に、本明細書で開示された分散ファイルシステムのコンテナはかなり大きく、平均で10から30GBの大きさであるため、位置情報はHadoopホームノードにおける位置情報よりも100から1000倍小さくなる。CLDBはさらなる保存へとつながるいかなるファイルメタデータも全く保持しない。さらに、コンテナ位置データが効率的にキャッシュされているため、CLDBは任意の可視的な異なる動作を行わずにページングされることができ、メインメモリに常駐する必要がない。これらの要因は、本明細書に記載の分散ファイルシステムを数百万以上のコンテナを保持する規模に成長させることを可能にする。このことは、ファイルの数にかかわらず、数十エクサバイトのデータを保持するクラスタが実用化されることを暗示する。ApacheHadoopは、対照的に、ネームノード全体がメモリに常駐しなければならないことによって数十万のファイルに限られ、全体のサイズは一般的に数ペタバイトに限られる。ファイル生成速度もまた、本明細書に記載の分散ファイルシステムは他のいかなるファイルシステムよりも概して非常に速い。10個のノードのスモールクラスタ上でさえも、本発明によるファイルシステムは、同じサイズのHadoopクラスタのほぼ100倍の速度でファイルを生成可能である。この比率により、クラスタサイズを1000個のノードに線形に拡大すると、本明細書に記載されたファイルシステムは、同じサイズのHadoopクラスタよりもほぼ4桁のオーダーで高い速度でファイルを生成可能である。複製およびデータ構造バージョニング分散ファイルシステムのコンテナは複製の単位である。コンテナ位置データベースCLDBは、コンテナ内でデータの複製として動作するようにポリシーの制約を合致させる必要がある程度に多くのノードを割り当てる。複製は、しかしながら、ノードに可能な限り多くの故障が重なってもなお存続しなければならない。このために用いられる1つの戦略は、CLDBに、各コンテナに関するすべてのトランザクションを制御するマスタノードにそのコンテナを割り当てさせることである。加えて、CLDBは複製を保持するノードのチェーンを指定する。複製の1つが故障するかマスタCLDBノードから分離された場合、それは複製チェーンから取り除かれる。マスタが故障するか分離された場合、新しいマスタが指定される。複製チェーンから取り外された後に復帰した任意のノードは、ノードが復帰する際にチェーンがなおも別の複製を必要とする場合、複製チェーンの最後に挿入される。ノードがすばやく復帰した場合、問題のコンテナを複製する新しいノードが指定されていることはおそらくないため、チェーンはなおも複製を必要とする。ノードが長時間にわたって故障していた場合、その間に、CLDBはチェーン内で代替となる他のノードを指定している可能性が高い。複製チェーンの更新は、トランザクションを制御するコンテナマスタによって、通常はトランザクション的に実行される。これはコンテナのすべての複製が最新のものであることを保証する。そのような更新はマスタ複製をローカルにロックして、他のすべてのレプリカが成功したか失敗したかを報告するまで待つことによって実行されうる。いずれの場合もロックは解除される。ノードが複製チェーンに復帰した場合には、しかしながら、不通だった間に発生したいかなるトランザクションも経験することはない。逆に、それらは、まだカレントであるかなりの量の古いデータを有していそうである。それらのノードは任意の長期間の間不通であったかもしれないため、そしてノードが復帰する保証が全くないため、ノードの復帰までトランザクションログを保持することは実行可能ではない。本明細書記載の分散ファイルシステムにおいて、ファイルシステムデータ自身は、すべてのトランザクションが再生または保持すらもされる必要なしに、コンテナ複製チェーン状態の再構築を可能にする最小セットの更新を見出すように試されうる。すべてのiノードデータ構造および間接データB木は、トランザクションを欠いたコンテナ複製を更新することを容易にするバージョン番号を有する。複製チェーンを最新のものにするように、複製マスタのコンテナiノードのスナップショットが、更新過程の最中に任意の他の変化を凍結するように生成される。スナップショットの最新のバージョンが、更新される複製チェーンの最新のバージョンと比較される。バージョンが同じ場合は、更新は不要である。更新が必要である場合、スナップショットiノードの各子childは、スナップショットに隠れた複製チェーン内にiノードまたはブロックを発見するように同一の方法で再帰的に試される。ひとたび複製チェーンがマスタスナップショットと共に最新のものにされると、スナップショット複製の過程全体が繰り返され、マスタレプリカ先書きログwrite-aheadlogが再生されて複製チェーンを完全に最新のものにすることができる。別の選択は、コンテナマスタの更新を一時的に凍結させ、変更されたブロックを新しい複製チェーンにコピーすることである。更新された複製チェーンは、すべてのレプリカの更新が複製プロセスの完了の際に一斉に現れるようなトランザクションのやり方で、利用可能となる。この更新過程もまた、変更されたブロックの現在のバージョンのみがコピーされているため、非常に古いレプリカチェーンの更新をずっと効率的なものにする。トランザクション的なスナップショットからなるこの複製は、ほとんどすべてのもっともらしい故障シナリオの下で、そして悪いやり方での極端な故障シナリオの下でさえも、動作が平常に継続することを可能にする。例えば、コンテナに3つの複製チェーンA、B、Cがあるとする。Cは利用不可能で、その後にAおよびBが更新を受信したとする。そのとき、AおよびBの両方が利用不可能となりCが復帰した場合、望めばシステムはなおも機能することができる。システムはCが古いことを知っており、Cを前の状態に逆行させることが受け入れ可能な場合、Cをリードオンリーモードで利用可能にすることができる。Cを現在のバージョンに指定することによって、逆行した状態に関与することさえも可能である。Cがそのように指定されておらずAまたはBがようやく復帰した場合でも、システムはAおよびBが最新のものであることを認識することができ、CをAおよびBと合致するように回復させ、複製チェーンを復旧させて正常の動作を続けることができる。そのような部分的な故障シナリオは従来のトランザクション的システムでは概して可能ではなかった。さらに、少なくとも1つの更新複製チェーンが動いている限り、データは一切失われない。これは、システムの複製の半数以上が利用不可能になると同時にリードオンリーモードになるので所定数の更新を必要とするシステムとは、対照的である。この例において、Cなどの期限切れの複製チェーンへの更新を回避するためのいくつかの機構が可能である。1つは、すべてのノードに、該ノードがコンテナ内の最新バージョンと共に有する変更されたコンテナのリストを、定期的にCLDBへ報告させることである。故障したノードが復帰し、特定のコンテナに関する複製チェーンとのコンタクトを再構築しようとする際に、それは問題のコンテナの位置および最新のバージョンを返すCLDBにコンタクトする。コンテナが期限切れであり、他のコピーがないためにコンテナの更新が不可能である場合、返すノードはこれを自覚し、リードオンリー基準に基づいてコンテナを提供することが可能である。すべての複製チェーン更新は完全にトランザクション的な方法で実行されるため、本明細書で記載されたシステムはハードマウントな動作を行い、すべての書き込みが成功するか成功までずっとハングすることを保証する。複製チェーン内のノードが書き込みの最中に故障した場合、書き込みは改訂された複製チェーンによって再開される。ひとたび複製チェーン内のすべてのノードが更新を適用した旨を報告すると、書き込みは成功する。書き込みが失敗するのは、更新されているコンテナの複製チェーンのいかなる部分も利用可能ではない場合のみである。実際に、その点において、書き込み中のオブジェクトはファイルシステム内にもはや存在しないのであるからである。更新コンテナの管理の何らかのチェーンが存在する限り、データは失われない。同様に、最小限の数の複製チェーンが任意の更新の進行のために必要である場合、故障が複数となる率はそう高くなく新しい複製チェーンが採用および更新されることがない限り、少なくとも1つのノードがコンテナの最新バージョンと共に動作している管理の連続したチェーンが存在することが保証されうる。利用可能でない複製チェーンの数が最小である期間、更新は抑制され、特定可能な数の故障が最新のバージョンを利用不可能にすることを妨げる。これらの故障シナリオの間、追加の複製チェーンがクラスタの残りから採用され、ウインドウに脆弱性がある時間は新しい複製チェーンにコンテナをコピーするために必要な時間に限定される。典型的なコンテナのサイズにおいて、そして1Gb/sイーサネットデータリンクが利用可能として、この時間は約1分である。10Gb/sデータリンクでは、この時間は数十秒に限定される。記憶プールおよびファイルサーバ分散ファイルシステムにおけるデータは最終的にブロックアドレッシング可能なデータ記憶に記憶される。このデータ記憶は、ディスクまたはフラッシュメモリシステム全体またはそれらのいずれかのパーティションを示すブロック装置であってもよい。これらのデータ記憶は、Linuxext3ファイルシステムなどの、従来のファイルシステム内に記憶された個々のファイルであってもよい。この最も低いレベルにおいては、重要なことのすべては、各データ記憶が比較的小さい、固定されたサイズのブロックのデータをランダムに読み書きすることをサポートすることである。本明細書に記載されたシステムにおいて、これらのブロックは通常は8キロバイトであるが、当業者はその他の理に適ったブロックサイズを選択可能であることを理解するであろう。選択されたサイズは、大きなデータ記憶をより少ないビットでアドレッシングすることを可能にするのに十分大きいが、平均的な予想されるファイルサイズの一部であるほど十分小さい。それらが実際にどのように記憶されているかにかかわらず、最も一般的な使用の場合には、ファイル記憶がハードディスク全体にわたる単一のパーティションを表すブロック装置からなることとなるから、これらのデータ記憶はファイルシステム内でディスクとみなされる。分散ファイルシステム内のディスクは、より高いレベルのブロックアドレッシング可能なオブジェクトを提供するように種々の方法で組み合わせられる。これらの組み合わせとして、連結、ミラーリング、およびストライピングが挙げられる。これらの組み合わせは、コンポジットオブジェクトへの更新およびアクセスがコンポーネントオブジェクトへの更新およびアクセスに変わっている点で異なる。2つのディスクの連結において、第1のコンポーネントディスクのサイズよりも小さいアドレスを有するブロックへのすべての更新およびアクセスは、すべての他の更新およびアクセスが第2のディスクに向けられる間に、第1のディスクにアドレッシングされる。ミラーリングにおいて、更新はすべてのコンポーネントディスクで行われ、アクセスはランダムに選ばれた任意のコンポーネントディスクで行われる。ストライピングにおいて、コンポーネントディスクはディスクの数を法moduloとした更新またはアクセスのブロックアドレスをとることによって選択され、コンポーネントのために用いられるアドレスはオリジナルのアドレスをコンポーネントディスクの数で割った商をとることによって導出される。任意のそのような組み合わせの結果は、それ自体でディスクと考えられうる。図4は、記憶プールが、ディスクパーティション、単一のファイル、またはディスク全体などのプリミティブ要素からどのように構成されるかを示すブロック概略図である。この場合にはコンポジット連結ディスク401が連結ディスク402およびストライピングされたディスク403の連結からなる。連結されたディスク402は単一のディスクパーティション404および単一のファイル405の連結からなる。ストライピングされたディスク403はディスク全体406および単一のパーティション407を範囲に含むパーティションからなり、場合によってはそれらの中の1つはディスク上にある。コンポジットディスク401へのすべての更新およびアクセスは、根底にあるプリミティブなデータ記憶404から407の1つへの更新またはアクセスへと結局は帰着する。図5は記憶プール501の構造を示すブロック概略図である。ビットマップ空間のリスト502、ログ空間のリスト503、コンテナディスクオフセットへのCIDのマップ504が、記憶プールの中のいくつかの周知の位置に複製されるスーパーブロック内に記憶される。ビットマップ空間のリストは、記憶プールに関する複数のブロック割り当てビットマップ505、506へのポインタを有する。ログ空間のリストは、記憶プールに関するトランザクションログ507、508を記憶するために用いられる記憶プールの一部へのポインタを含む。ディスクオフセットへのコンテナIDCIDのマップは、コンテナの仕様509、510が記憶プール内に見出されるコンテナに対してどこに位置するかを示すポインタ、およびスナップショット513のリンクされたリストを形成するコンテナIDを有する。したがって、記憶プールはコンポジットまたはプリミティブなディスクとして定義され、それは4つの主要なコンポーネントを有する。他の3つのコンポーネントの開始点へのオフセットを含むスーパーブロック。ディスク内のどのブロックが使用状態にあるかを示すブロック割り当てビットマップ。分散ファイルシステムにおいて、ブロック割り当てビットマップは、ビットマップデータを含む連続的なディスク領域へのポインタのリストとして記憶される。図5において、2つのビットマップ505および506が示されるが、実際には任意に多くのビットマップが使用される。記憶プールのコンテンツのACIDトランザクションを容易にするように使用されるトランザクションログ。分散ファイルシステムにおいて、トランザクションログは、実際のログデータを保持するディスク領域へのポインタのリスト503として記憶される。図5において、2つのログ空間507および508が示される。コンテナIDから記憶プール内の各コンテナの仕様へのマッピング504を含むコンテナマップ。2つのコンテナ仕様509および510が図5に示されるが、任意の数のコンテナが記憶プール内に存在してもよい。コンテナ仕様509のコンテンツの一部は、コンテナがコピーオンライト511としてマークされたかどうか、コンテナがディスク512上のどこに実際に位置するか、およびコンテナのスナップショット513のリストを示すためのビットを含む。コンテナに関する他のデータも同様に記憶されてよい。記憶プールは他のコンポーネントから記憶プールの詳細を隠すファイルサーバコンポーネントによって管理および変更される。ファイルサーバは、例えばコンテナ位置データベースなどの他のコンポーネントからの、あるいはファイルサーバによって管理されるコンテナへの更新またはアクセスのための要求を特定するクライアントプログラムからのメッセージを受け取る。コンテナ記憶プール内のバイトよりも高い抽象化レベルにおいて、分散ファイルシステムはコンテナと見なされるオブジェクトを有する。コンテナ内のすべての構造はiノードとして知られるデータ構造によって記述される。図6は、特定のコンテナにおいてiノード601と呼ばれるFIDファイル識別子606を示すブロック概略図である。iノードのすべての形態はある共通の構造を有する。この実施例におけるiノード601は、所有者、許可、親FID、オブジェクトのタイプ、およびサイズを含むオブジェクトの種々の特徴を記述する属性602を含むコンポジットデータ構造である。オブジェクトのタイプはローカルファイル、チャンクファイルchunkedfile、ディレクトリ、キー値記憶、シンボリックリンク、またはボリュームマウントポイント、そしてその他の可能性もありうる。iノードはまた、オブジェクト内の最初の64キロバイトのデータを含む8つのディスクブロックへのポインタ603も含む。これらのポインタのそれぞれはポインタ603と共に記憶された関連するコピーオンライトビットを有する。iノード601はまた、間接的なデータへの参照604も含む。ローカルファイルの場合には、この参照604は、B木に関するコピーオンライトビットと共にオブジェクトデータを含む該B木へのポインタであってもよい。チャンクファイルの場合には、参照604はFIDマップと呼ばれるローカルファイルを指してもよく、FIDマップは、ファイルのコンテンツを含む他のコンテナ内のローカルファイルを参照するFIDを含む。iノードのこの実施形態における参照はB木またはFIDマップのいずれかを参照することができるが、両方を参照することはない。両方の種類の参照が同時に用いられる他の実施形態が可能である。シンボリックリンクおよびボリュームマウントは、iノードの直接のデータブロック内の文字列データとして参照されるファイルまたはボリュームの名前を記憶する。チャンクファイルの内部構造は以下に記載される。iノード601はまた、iノードから参照される任意の構造に関する最新のバージョン番号のキャッシュ605も含む。このバージョン番号は複製およびミラーリングにおいて用いられる。iノード606への参照はFIDと呼ばれ、コンテナID、iノード番号、および、iノードが異なる目的のために再使用される場合であってもFIDのコンテンツを一意的にするように選ばれた整数から構成される。ローカルファイルとは、完全に単一のコンテナ内にバイトを含む分散ファイルシステムにおけるオブジェクトである。ローカルファイルはデータの最初の64kBに関するディスクブロックへの8つまでの直接参照を有するiノードによって表される。64kBよりも長いローカルファイルに関しては、B木リンクは、クラスタディスクリプタとして知られる値が64kBデータブロックのB木を指示する。B木に関するキーは、対応するクラスタディスクリプタの始まりに関するバイトオフセットである。それらのバイトオフセットの下位の16ビットは常にゼロであり、キーは実際には216で割ったバイトオフセットである。図7はローカルファイルを表すiノードの構成を示すブロック概略図である。ここで、iノード701は図3のCLDB301によって指示されたiノードと同じ、または図6の概略で示されたものと同じ全体的構造を有する。ただし、データポインタのすべてがディスクブロック702を指示することと、間接的な値がB木703を指示し、それがクラスタディスクリプタ704を指示することを除く。クラスタディスクリプタ704は64kBまでのデータを記憶する8つまでのディスクブロックへのポインタを含む。クラスタディスクリプタ内のデータを記憶するために必要とされるのと同じ数のディスクブロックのみが用いられる。クラスタディスクリプタが圧縮されたデータを含む場合、オリジナルデータは8kBブロックごとに個別に圧縮され、圧縮された表現representationはバイト単位でbyte-wise連結される。各連結された8kBブロックの始まりへのオフセットは、2バイト整数の配列として記憶される。単一のチャンクファイルに記憶されるデータは、チャンクファイルに関するiノードと同じコンテナ内にあるように制限される。チャンクファイルは多くのコンテナに記憶されたチャンクで構成されるファイルである。各チャンクはローカルファイルとして表され、チャンクファイルのiノードからの参照は、それらのローカルファイルへの参照の配列へとつながる。図8はチャンクファイルを含むファイルの構造を示すブロック概略図である。ここで、チャンクファイルに関するiノード801が示される。このiノードは、各ファイルレットfileletがどれだけのデータを含むかを特定するチャンクサイズ802を含む。ローカルファイルでは、チャンクサイズは0に設定され、チャンクファイルでは、チャンクサイズは64kかそれ以上の任意の所望の値に設定される。直接的なデータポインタは、以前にローカルファイルiノード801に関して見られたような、チャンクファイルiノードと同じコンテナ内のディスクブロック803への参照を有する。ファイルに関する間接的なポインタは、しかしながら、FIDマップ804と呼ばれるFIDの配列を含むローカルファイルを指示し、該FIDマップの要素はクラスタのどこかのいずれかのコンテナの中にあるチャンクファイルとみなされる。FIDマップの要素は図6に示されたようなFID806である。シンボリックリンクはファイルの名前を含むローカルファイルとして記憶される。通常、そのような名前は64kB未満の長さであり、したがってiノードの直接的なブロック内にのみ記憶される。シンボリックリンクは他のファイルシステム内に通常あるリンクを含むディレクトリに対して逆参照されることができる。本明細書の分散システムにおいて、シンボリックリンクは任意のファイルシステムオブジェクトを指示することができる。ボリュームマウントは、マウントされるボリュームの名前を含むローカルファイルとして記憶される。通常は、そのような名前は64kB未満の長さであり、したがってiノードの直接的なブロック内にのみ記憶される。ボリュームマウントはファイルシステムオブジェクトへの参照を解決するresolve際にディレクトリとして処理される。マウントされているボリュームは名前によって検索され、ボリュームのルートディレクトリは、それがボリュームマウントポイントにあるかのように処理される。図9はコンテナのコンテンツを定義するiノードファイルのコンテンツおよびレイアウトを示すブロック概略図である。iノードファイル自身のiノードは16個のリザーブされたiノードの1つである。iノードファイルはローカルファイルとして記憶される。コンテナ内のすべてのファイルはコンテナIDおよびiノードナンバによって定義される。ファイルのiノードナンバは、ファイルに関する256バイトのiノード構造を見出すようにiノードファイル内でオフセットを計算するように用いられる。iノードファイルのビットマップ領域に対応するiノードナンバは用いられない。iノードファイルは512キロバイト刻みで拡張される。図10はコンテナ複製からデータを読み込むクライアントを示すフローチャートである。図10において、FID=<CID,Inode,Uniquifier>、offset、およびlengthが入力される1000。コンテナ位置がキャッシュされているかどうか決定が行われる1001。キャッシュされているのならば、コンテナ複製ノードは抜き取られてリストから取り除かれ1003、要求がデータをホスティングするノードに送られる1004、図11参照。コンテナが発見されたならば1008、動作は成功する1009。発見されないのならば、利用可能であればより多くの位置がチェックされ1007、そうでないならばコンテナ位置がCLDBから検索される1002。CLDBから検索されたコンテナ位置は受信receiptにキャッシュされる。位置が空ならば1005、エラーであり1006、そうでなければ、コンテナ複製ノードは抜き取られてリストから取り除かれ1103、処理は上記のように続行する。同様に、コンテナ位置がキャッシュされていないならば1001、コンテナ位置はCLDBから検索されてキャッシュされる1002。位置が空ならば1005、エラーであり1006、コンテナ複製ノードは抜き取られてリストから取り除かれ1103、処理は上記のように続行する。図11はブロックを読み込むことによってサーバがファイルの領域をどのように読み込むかを示すフロー図である。領域内のバイトを含むブロックが読み込まれて、領域内の関心のある部分が結果へとコピーされる。図11において、FID=<CID,Inode,Uniquifier>、offset、およびlengthが入力される1100。オフセットは8kの境界で切り捨てられ、lengthがチェックされて0を超えるかどうか決定される1103。もし超えないのならば、処理は完了する1103。そうでなければ、ブロックは現在のオフセットにおいて読み込まれ1104、図12を参照、ブロックの一部が結果へとコピーされる1105。現在のオフセットはこのとき8kだけオフセットされており、lengthは8kだけ差し引かれ1106、処理が繰り返される。図12はサーバがファイルからどのようにブロックを読み込むかを示すフローチャートである。すべてのファイルはファイルの最初の64KBへの直接のアクセスを可能にする。後のブロックへのアクセスは別のフロー図で記載される。図12において、FID=<CID,Inode,Uniquifier>、offset、およびlengthが入力される1200。コンテナ位置はそのとき各記憶プールにおいて検索される1201。コンテナが発見されないならば1202、エラーであり、コンテナは存在しない1203。そうでなければ、iノードはiノードファイルから読み込られる1204。一意性識別子uniquifierが一致しないならば1205、エラーでありステイルstaleFIDである1206。そうでなければ、オフセットが検査されて64kBより小さいかどうか決定される。オフセットが64kBより小さくないならば、ファイルがローカルファイルかどうか決定が行われる1212。ローカルファイルならば、ファイルは読み込まれる1213、図13参照。そうでなければ、チャンクファイルが読み込まれる1214、図14参照。オフセットが64kBより小さいならば1207、直接のブロックナンバー[オフセット/8k]から読み込みが行われる1208。ブロックが発見されたならば1209、動作は成功してブロックは戻される1211。そうでなければ、動作は成功したとみなされるが、ゼロで満たされたブロックが戻される1210。図13はサーバがローカルファイルからどのようにブロックを読み込むかを示すフローチャートである。最初の64キロバイトの後のブロックは、正しいブロッククラスタのアドレスを見つけるようにオフセットによってキー付けされたkeyedB木内を探すことによって読み込まれる。各ブロッククラスタは8つの個別の8キロバイトブロックからなる。図13において、ローカルファイルブロックが読み込まれる1300。iノードB木1301が[offset/64k]に等しいキーによって検索され、ブロッククラスタディスクリプタを見つける。クラスタが見つからなければ1302、動作は成功したものとされ、ゼロで満たされたブロックが戻される1303。そうでなければ、ブロック番号[offset/64k]を8で割った余りによって識別されたブロックがブロッククラスタから読み込まれる1304。ブロックが見つかったならば1305、操作は成功し、ブロックが戻される1306。そうでなければ、操作は成功したものとされ、ゼロで満たされたブロックが戻される1307。図14はサーバがファイルチャンクからどのようにブロックを読み込むかを示すフロー図である。最初の64キロバイトの後のブロックが、ローカルファイル内に記憶されたFIDテーブルとして知られるFIDの列内からFIDを探すことによって読み込まれる。FIDテーブル内のFIDのインデックスは、ファイルチャンク内のチャンクのサイズで所望のブロックのオフセットを除算し、その答えより小さく一番近い整数で丸めることによって決定される。ローカルファイルからどのように読み込むかについての詳細は図13を参照のこと。各チャンクはchunk_sizeのバイト数を有する1つのファイルチャンクを含む。chunk_sizeパラメータはファイルチャンクのiノード内で定義される。チャンクからブロックを読み込むことは、ローカルファイルからブロックを読み込むための通常の方法に任せる。図14において、ファイルチャンクブロックが読み込まれ、iノードおよびブロックオフセットが与えられる1400。チャンクFIDは、offset/chunk_size以下であるかの指標fを用いてFIDマップ内で検索される1401、図13参照。チャンクが見つからなければ1402、動作は成功したものとされ、ゼロで満たされたブロックが戻される1403。そうでなければ、FIDによって指定されたブロックがオフセットモードのchunk_sizeにおいてローカルファイルから読み込まれ1404、図14参照、動作は成功したものとされ、所望のブロックが戻される1405。分散トランザクション第一級のマップリデュースシステムは、あるファイルが単なるコンテナよりも大きくなることを要求し、ファイルが単なるコンテナの複製チェーンによって表現されるノードの組よりも多数のノード上に広がることを要求するため、単なるコンテナ複製は分散ファイルシステムにとって不十分である。分散ファイルシステムにおけるファイルチャンクはこの要求を満足するために用いられるが、ファイルチャンク上の非常に細かいfullatomic更新または追加のサポートにはマルチコンテナトランザクションが必要である。最も単純な場合には、ファイルチャンクおよびオリジナルのiノードが協調的に更新されなければならない。より複雑な場合には、オリジナルのiノードおよび複数のファイルチャンクがともに更新されなければならない。分散マルチノードトランザクションには複数の手法が存在するが、すべての従来のシステムは分散的な設定において深刻な欠陥を有する。例えば、Zookeeperはすべてのトランザクションが単純なマスタを介して行われることを要求することによって、マスタを指定する一定数のquorumクラスタが常にあることを要求することによって、そしてすべての更新は一定数のノードによって受け入れられた2相コミットを用いてコミットすると要求することによって、トランザクションを取り扱う。時間をかけてトランザクション情報を管理する連続したチェーンがあるように、そして最新の情報を有しない一定数が生成されないように、一定数はクラスタ内のコンピュータの半分以上である。この手法は2つの問題を有する。第一に、一定数よりも少ないノードがまだ利用可能である場合に動作が不可能であり、第二に、すべての更新はマスタノードを介して行わなければならず、クラスタの引継ぎを妨害することなく1つ以上のマスタを有することは不可能である。これらのトレードオフはZookeeperにかなり良い信用を与えているが、利用可能なノードが一定数より少ない場合は更新の受け入れに関してZookeeperを拡張不可能で脆弱なものにする。従来の分散2相コミットシステムはまた、複数の故障に直面しての信頼できる動作の提供に問題がある。図15は3つのノード、トランザクションマスタ1501と、補助subsidiaryノード1502および1503の間の相互作用の最中に、回復不可能なトランザクションを示すフロー図である。正確にどのノードがマスタでどのノードが補助であるかはトランザクションごとに変更することができ、補助ノード上で実施された動作は、ここで述べたことの一般性に影響を及ぼすことなく、補助ノード自身を分散トランザクションに関与させることができる。第1のステップは補助ノードへの開始トランザクション1504をマスタが送信することである。この時点で、このトランザクションの保護を受けたデータへのすべての変更には、そのデータにロック1505を行うことを含む。結局は、マスタはトランザクションへのコミットまたはロールバックの開始を決め、補助ノードに準備コマンド1506を送信する。この例においてはこの時点で、すべての含まれるノードは、トランザクションがコミットに成功するかロールバックされるまで、すべてのロックを保つことを保証しなければならない。このシナリオでは、しかしながら、マスタから送信されたコミット1507はノードA1502に到達するが、ノード故障またはネットワーク分断のためにノードB1503への到達が阻止される。ノードBはトランザクションにコミットし、そのトランザクションのログを取り除く。マスタは、しかしながら、現時点で到達していないコミットが完了した旨のCからの確認を待たねばならない。ここでマスタが故障してノードCが復帰した場合、ノードCはマスタからのトランザクションの状態の発見1508が不可能であり、トランザクションをコミットするべきかアボートすべきかわからないため不安定な状態にとどまっている。それはトランザクションをアボートすることができず、マスタのみが持っている情報なしにトランザクションにコミットすることもできない。したがって、ノードCはこのトランザクションに関連するすべてのログおよびロックを、マスタが決して復帰しない場合には永久に、保持しなければならない。図16は故障によって影響を受けないトランザクションを示すフロー図である。図16において、マスタノード1601は補助ノードA1602上の参照を、補助ノードB1603上の新しいデータに書き込むことを意図している。動作の後に、関与するノードの一時的あるいは恒久的な故障または分断にかかわらず、A上の参照とB上のデータが存在すべきか、A上の参照とB上のデータのいずれも存在すべきでないか、のいずれかである。いくつかの実施例または状況において補助ノードAまたはBあるいはその両方は、一般性を失うことなくマスタノードと同じノードである。同様に、複数の補助ノードが、ノードの別の組にあるデータへの参照が存在するノードの組に分割可能である限り、ここに示された概略例は、ここに示されたよりも多くの補助ノードを含んでもよい。一般性を失うことなく、マスタ1601、ノードA1602、およびノードB1603がそれぞれ単一のノードである場合を記載する。当業者はこの限定的な記載を、より一般的な形態として解釈することができるであろう。このトランザクションが実施される方式は、マスタノード1601がデータ1604を補助ノードB1603に最初に書き込むことである。データは補助ノードB上のトランザクションログに書き込まれ、トランザクション1605は、補助ノードA上の参照が後で発見されない場合、書き込みの効果を逆転されるオーファナージorphanageに書き込まれる。トランザクションログへの更新およびオーファナージへの更新はアトミックに行われる。補助ノード1603はそれから参照1606を、マスタノードに新しく書き込まれたデータへ戻す。それからこの参照は、補助ノードA1602への送信1607となる。データがノードB上で生成された場合、1608においてバックグラウンドスレッドが開始されるか、クリーンアップイベントがスケジューリングされ、オリジナルの書き込みが行われたかなり後の時点で、ノードBにオーファナージを検査させる。オーファナージのエントリは1609においてノードBにノードAを検査させるか、またはノードAの複製の1つに、ノードB上に書き込まれたデータへの参照が存在するかどうか確認させる。参照が存在する場合は、動作は起こらない。参照が存在しない場合は、B上のトランザクション1605において生成されたオーファナージのエントリは、データ1604のオリジナルの書き込みの効果を反転させる動作を行う。ノードA上の参照が生成されない場合は、ノードB上の新しいデータはアクセス可能にはならず、したがって効果は、参照およびデータがアトミックに出現するか決して出現しないかとなる。妨害されているトランザクションの不変条件がなければ、故障はこの過程の任意の点で発生しうる。オリジナルの書き込み1604および1605の前の故障は、マスタノードが新しいデータへの参照を受信することを妨げ、ノードB上のデータのいかなる変更にもつながらず、したがっていかなる変更または参照も引き起こさない。書き込み1604または1605の後で、参照が1606に戻る前の故障は、参照がノードA上に挿入されることを阻止するが、オーファナージは結局はデータ書き込みを未成undoneにする。参照を受信した後でノードAへの送信1607の前のマスタノードの故障、または参照が持続する前のノードAの故障は、バックグラウンドスレッド1608によって結局は解決される。バックグラウンドスレッド1608がノードAの複製の1つにおいて参照を発見するので、参照が書き込まれた後のノードAの故障は処理される。ノードAおよびすべてのノードAの複製の故障によってすべての複製が失われた場合、データは消去される。バックグラウンドスレッドが起動される前にノードBが故障した場合、複製チェーンの他のノードが解決タスクを実行する。この形態のトランザクションが分散ファイルシステムに役立つ理由の1つは、何らかの部分的な更新が該ファイルシステムの状態にユーザから見える変化を起こすことがないように、該ファイルシステムへのすべての分散的な更新が、従属関係に応じてトポロジー的にソートされることができることである。多くの場合において、トランザクションに含まれるノードを、新しいデータへの新しい参照を含むいくつかのノードと、新しいデータを含む他のノードと、からなる二分された組に分割することは、このトポロジー的なソートの要請を自明に満足する。このトポロジー的なソートの基準は、例えば、相関的データベースの更新の一般的な場合には当てはまらない。なぜなら、従属関係が外部の意味的制約に基づいているために、常に明らかであるとは限らないからである。このことは、分散ファイルシステムの分散トランザクションは、ある意味では、従来型の2相コミットよりも弱いことを意味する。その一方で、この新規な形式の分散トランザクションを分散ファイルシステムが用いることを可能にするために必要な動作の組は、より限定されている。分散ボリュームスナップショット分散トランザクションの1つの特に重要な形態は、多数のコンテナにまたがるディレクトリおよびファイルを含むファイルシステムボリュームのスナップショットの生成である。これは従来のファイルシステムでは困難であり、通常は分散アップデートを避けることによって例えばAFS、あるいは集中型ロッキングプロトコルを用いることによって例えばGFS実装される。複製の欠如は、シングルポイントの故障が多く、大きなクラスタにおいて性能が低いシステムをもたらす。集中型ロッキングプロトコルは性能を限定し、特に高速度でのファイル生成に関して限定する。また、性能に深刻な影響を与えることなくアクティブなファイルシステム上で分散スナップショットを作成することを非常に困難にする。ここで開示された分散ファイルシステムにおいて、分散トランザクションおよびコンテナスナップショットは、性能に大きな影響を与えることなく、また、大規模分散データ構造のロッキングを必要とすることなく、分散スナップショットを実装するために用いられる。分散ファイルシステムが分散スナップショットを実装する方法は、ボリュームに関するすべてのデータおよびメタデータを、単一のネームコンテナおよびゼロ個以上のデータコンテナにまとめることである。加えて、システムはデータへのすべてのコンテナ間参照cross-containerreferenceを、データコンテナ内にデータのすべてを保ちながらネームコンテナへと分離する。このシステムは、当業者に知られている標準的な手法を用いて1つ以上のネームコンテナを用いるように一般化することができる。1つのデータコンテナから別のデータコンテナへのすべての参照がネームボリューム内のデータ構造によって仲介され、ボリュームスナップショットは、ネームコンテナのスナップショットを最初に生成し、次にデータコンテナのスナップショットを生成するように進行する。データコンテナに挿入されるデータ構造は、コンテナに名前をつけるデータ構造からデータコンテナへの参照を有するにすぎず、該参照はネームコンテナのスナップショットの前または後に生成されなければならない。参照がネームコンテナのスナップショット内に存在する場合、データはより早い時間に存在していなければならず、したがって、該ネームコンテナのスナップショットの後でとられたいかなるデータコンテナのスナップショットも、参照を未解決のままにさせないデータを有する。どのコンテナがスナップショット内に含まれるかに関する混乱を防止するため、コンテナ位置データベースは、スナップショットの生成の最中には、ボリュームに関する新しいコンテナの追加を阻止してもよい。代替として、ネームコンテナはデータコンテナへの必要な参照を含んでもよく、それは、ひとたびネームコンテナがスナップショットをとられると、スナップショットをとられる必要があるデータコンテナのセットがフリーズすることを意味する。図17は、ファイルチャンクに関する参照の構造を示すブロック概略図である。図17において、ファイルチャンクを記述するiノード1702を指示するディレクトリエントリ1701の最終状態がある。ファイルチャンクに関するiノード1702はFIDマップ1703を参照する。FIDマップ1703は、ファイルデータを実際に含むローカルファイル1704への参照を有する。ディレクトリエントリ1701およびFIDマップ1703はネームコンテナ1705内にある。iノード1702およびローカルファイル1704は1つ以上のデータコンテナ1706内にある。ネームコンテナスナップショット内のボリュームディレクトリルートまたはほかのサーチルートから推移的にアクセス可能なすべての参照が有効なターゲットを有しなければならない場合、ボリュームスナップショット全体における参照のインテグリティは保証される。分散システムにおける分散トランザクションは参照が持続する前に参照のターゲットが存在することを保証するので、起こりうる最悪のことは、ボリュームルートディレクトリからデータ構造体への直接または間接の参照が全くないために、トランジション的にアクセス不可能なデータ構造をスナップショットが含むことである。図17において、例えば、FIDマップ1703からローカルファイル1704への参照は、ローカルファイル1704がすでに存在する場合にのみ存在しうる。ネームコンテナのスナップショットはデータコンテナのスナップショットの前に生成されるため、参照はネームコンテナ内に存在しないか、そうでなければ、参照がネームコンテナのスナップショット内に存在してかつローカルファイルがデータコンテナのスナップショット内に存在する。同様に、ファイルチャンクiノード1702を生成する分散トランザクションは、FIDマップ1703が最初にネームコンテナ内に存在することを保証し、ファイルチャンクiノードへのディレクトリ参照1701を生成するトランザクションは、ファイルチャンクiノードがすでに存在する場合にのみディレクトリ参照1701が存在することを保証する。このことは、ファイルチャンクiノード1702へのディレクトリ参照1701が生成される前にFIDマップが存在することを推移的に示す。したがって、FIDマップ1703がネームコンテナのスナップショット内にない場合、ディレクトリ参照1701もまたネームコンテナのスナップショット内にはありえず、チャンクファイルiノード1702の存在による、参照のインテグリティに対するいかなる潜在的な妨害も、視野から隠される。当業者は本分散ファイルシステム内のすべての参照チェーンに関して、同様のロジックのチェーンを導き出すことができる。特に、ネームコンテナは多くの娘ネームコンテナを参照することができ、娘ネームコンテナが親ネームコンテナ内に見えるようにされる前に、娘ネームコンテナ内にメタデータが生成されるという同様の制約を伴う。これによって、単一ボリュームの内部の分散ディレクトリは、ネームコンテナの階層化を用いて構築され、該ネームコンテナはトランザクション的にも、分散においてスナップショットをとられている際にも、すべて整合がとれている。NFSゲートウェイ分散ファイルシステムは、トークンまたは他の状態に基づく機構をロックする必要なしに、読み書きアクセスを提供する。このことは、ランダムな更新および読み込みが、クラスタ内の任意のノードまたは、クラスタ内のコンピュータへの自由なアクセスを有する任意のコンピュータから起こることを意味する。分散ファイルシステムへのアクセスのステートレスな特性は、NFSなどのネットワークプロトコルを介した分散ファイルシステムへのアクセスを提供することがかなり容易であることを意味する。図18は、クラスタに関するNFSゲートウェイの動作を示すブロック概略図である。このシステムにおいて、NFSクライアント1801はランダムに選択されたバーチャルIPアドレス1802に接続する。各バーチャルIPアドレス1802はNFSゲートウェイ1803の1つによってホスティングされ、バーチャルIPアドレスへの接続が、NFSゲートウェイの1つへの接続を実際に行わせる。NFSゲートウェイは調整サーバ1804を用いて、どのゲートウェイがどのIPアドレスをホスティングするのかを協働的に決める。調整サービスはApacheZookeeperなどのシステムを用いる一実施形態において実装される。そのような調整サービスの使用は、単独のゲートウェイへの各バーチャルIPアドレスの信頼できる割り当てを可能にし、各ゲートウェイができる限り少ないバーチャルIPアドレスにサービスすることを確実にする。ファイルの生成、ファイルメタデータへのアクセス、またはファイル領域の読み込みまたは更新の要請に応じて、NFSゲートウェイはクラスタ1805によってホスティングされた分散ファイルシステムに同様の要請を行う。NFSゲートウェイはクラスタとは別のコンピュータ上で、またはクラスタの一部であるコンピュータ上でホスティングされることができる。すべてのNFSサーバは分散ファイルシステム内のすべてのファイルにアクセス可能であるため、NFSゲートウェイは完全にステートレスである。このことは、1つのNFSゲートウェイが故障した場合、そのゲートウェイによって使用されていたバーチャルIPアドレスが別のゲートウェイに再割り当て可能であり、動作は無駄なくリトライ可能であることを意味する。故障したゲートウェイの喪失が検出されバーチャルIPが再割り当てされる間の遅延以外は、NFSクライアントは故障の検出さえできない。NFSゲートウェイ内のロックを別のNFSゲートウェイに転送することが困難か高コストでありうるため、そのような故障寛容性はそのようなロックを維持するシステムを提供することを困難にしうる。そのようなシステムは分散ファイルシステムへの均一なNFSアクセスを提供しうる。分散ファイルシステムとNFSゲートウェイとの組み合わせの結果としていくつかの利点が生じる。1つの利点は、ファイル読み書き帯域幅の総計が、クラスタのサイズによって課せられていた制限を超えてNFSゲートウェイの数に対応可能となることである。ファイルの生成または削除の速度の総計も同様に対応する。別の利点は、クラスタ内のファイルに名前をつける際の慣習に関する。分散ファイルシステムAPIによってアクセスされるすべてのファイル名は、例えば、プレフィックス/mapr/から始まり、その後ろに、クラスタ名、スラッシュ、およびそのクラスタ内のファイルの名前が続く。NFSゲートウェイは、それらに対してアクセス可能なクラスタのすべてに関して知っているので、それらは各アクセス可能なクラスタに対応するバーチャルファイルを、トップレベル/maprバーチャルディレクトリに表示させることができる。各NFSゲートウェイは/maprファイルシステムの下のこれらのバーチャルクラスタディレクトリをエクスポートする。ディレクトリ/mapr上のローカルファイルシステム上のNFSファイルシステムがNFSクライアントによってマウントされる場合、NFSクライアントマシン上でローカルに実行されるプログラムは、クラスタの使用において実行されるHadoopプログラムと正確に同じパス名を用いることができる。このことは実質的に、従来のシーケンシャルな要素をマップリデュースに基づく要素と組み合わせるプログラムおよびスクリプトを簡易にする。本発明は好ましい実施形態を参照して本明細書に記載されるが、本発明の精神および範囲から逸脱することなく、他の応用例が本明細書に記載されたものと置換可能であることを当業者は容易に理解するであろう。したがって、本発明は以下に記載された特許請求の範囲にのみ制限されるべきである。"