(57)【特許請求の範囲】
【請求項１】
単一の地理的に分散したファイルシステムを実行するように構成された計算装置を含むノードのクラスターであって、
第１のデータセンターと、
前記第１のデータセンターとは地理的に離れており、かつ、ワイド・エリア・ネットワーク上で前記第１のデータセンターと結合された第２のデータセンターと、
調整エンジンプロセスとを備え、
前記第１のデータセンターは、
それぞれクライアントファイルのデータブロックを格納するように構成された複数の第１のデータノードと、
それぞれ前記クラスターの名前空間の状態を更新するように構成された複数の第１の名前ノードとを有し、
前記第２のデータセンターは、
それぞれクライアントファイルのデータブロックを格納するように構成された複数の第２のデータノードと、
それぞれ前記クラスターの前記名前空間の前記状態を更新するように構成された複数の第２の名前ノードとを有し、
前記複数の第１及び第２の名前ノードは、前記複数の第１及び第２のデータノードに書き込まれたデータブロックに応答して、前記名前空間の前記状態を更新するように構成され、
前記調整エンジンプロセスは、前記複数の第１の名前ノード及び前記第２の名前ノードに広がり、前記名前空間の前記状態が前記クラスターの前記第１及び第２のデータセンターにわたって首尾一貫した状態に維持されるよう前記複数の第１及び第２の名前ノードによって格納される前記名前空間の前記状態に対する更新を調整するように構成される
クラスター。
【請求項２】
前記複数の第１の名前ノードのそれぞれは、前記第１のデータセンター内の１以上の他の前記第１の名前ノードもまた前記名前空間の前記状態を更新しているのと同時に、前記名前空間の前記状態を更新するように構成される
請求項１に記載のクラスター。
【請求項３】
前記複数の第２の名前ノードのそれぞれは、前記第２のデータセンター内の１以上の他の前記第２の名前ノードもまた前記名前空間の前記状態を更新しているのと同時に、前記名前空間の前記状態を更新するように構成される
請求項１に記載のクラスター。
【請求項４】
前記第１のデータセンター内の前記複数の第１の名前ノードは、前記第２のデータセンター内の前記複数の第２の名前ノードのいくつかもまた前記名前空間の前記状態を更新しているのと同時に、前記名前空間の前記状態を更新するように構成される
請求項１に記載のクラスター。
【請求項５】
前記第２のデータセンター内の前記複数の第２の名前ノードは、前記第１のデータセンター内の前記複数の第１の名前ノードのいくつかもまた前記名前空間の前記状態を更新しているのと同時に、前記名前空間の前記状態を更新するように構成される
請求項１に記載のクラスター。
【請求項６】
前記複数の第１のデータノードのそれぞれは、前記第１のデータセンター内の前記複数の第１の名前ノードとのみ通信するよう構成され、
前記複数の第２のデータノードのそれぞれは、前記第２のデータセンター内の前記複数の第２の名前ノードとのみ通信するよう構成される
請求項１に記載のクラスター。
【請求項７】
前記調整エンジンプロセスは、前記第１及び第２の複数の名前ノードから前記名前空間の前記状態を更新することについての提案を受信し、呼応して、前記複数の第１及び第２の名前ノードがそれぞれ格納している前記名前空間の状態を更新する順序を特定する順序付けられた同意のセットを生成するよう構成される
請求項１に記載のクラスター。
【請求項８】
前記複数の第１の名前ノード及び前記複数の第２の名前ノードは、前記調整エンジンプロセスから前記順序付けられた同意のセットが受信されるまで、前記名前空間の前記状態に対する更新を遅延させる
請求項７に記載のクラスター。
【請求項９】
前記調整エンジンプロセスは、前記第１及び第２の名前ノードのうちの１以上の障害、又は、前記第１及び第２のデータノードのうちの１以上の障害の際に、前記名前空間の前記状態を首尾一貫した状態に維持するように構成される
請求項１に記載のクラスター。
【請求項１０】
前記調整エンジンプロセスは、前記第１及び第２のデータセンターの障害の際に、前記名前空間の前記状態を首尾一貫した状態に維持するように構成される
請求項１に記載のクラスター。
【請求項１１】
前記単一の地理的に分散したファイルシステムは、ハドゥープ分散ファイルシステム（ＨＤＦＳ）の１バージョンを含む
請求項１に記載のクラスター。
【請求項１２】
前記第１のデータセンターのクライアントによって書かれたファイルの複数のデータブロックの少なくともいくつかのレプリカは、前記第２のデータセンター内の前記複数の第２のデータノードのうちの選択された１つに格納され、
前記第２のデータセンターによって書かれたクライアントのファイルの複数のデータブロックの少なくともいくつかのレプリカは、前記第１のデータセンター内の前記複数の第１のデータノードのうちの選択された１つに格納される
請求項１に記載のクラスター。
【請求項１３】
前記第１のデータセンターの前記複数の第１のデータノードのそれぞれは、選択された複数のデータブロックを、前記ワイド・エリア・ネットワーク上で、前記第２のデータセンターの前記複数の第２のデータノードのうちの選択された１つに対して非同期に送信するよう構成される
請求項１に記載のクラスター。
【請求項１４】
前記選択された複数のデータブロックは、前記選択された複数のデータブロックの所定数のレプリカが前記第１のデータセンター内の前記複数の第１のデータノードのうちの選択された１つに格納された後、前記第１のデータセンターから前記第２のデータセンターに送信される
請求項１３に記載のクラスター。
【請求項１５】
前記複数の第１の名前ノードのうちの少なくともいくつかは、前記複数の第２の名前ノードによる消費のために、前記複数の第１のデータノード内に格納されるすべてのデータブロックのリストを含むブロック報告を生成するよう構成され、
前記複数の第２の名前ノードのうちの少なくともいくつかは、前記複数の第１の名前ノードによる消費のために、前記複数の第２のデータノード内に格納されるすべてのデータブロックのリストを含むブロック報告を生成するよう構成される
請求項１に記載のクラスター。
【請求項１６】
生成された前記ブロック報告は、ブロック報告ファイルとして前記ファイルシステムに書き込まれ、
前記第１及び第２のデータセンター内の前記第１及び第２の名前ノードは、前記ファイルシステムから前記ブロック報告ファイルを周期的に読み出し、対応してそれぞれに格納される前記名前空間の状態を更新するよう構成される
請求項１５に記載のクラスター。
【請求項１７】
前記複数の第１の名前ノード及び前記複数の第１のデータノードは、前記第１のデータセンターのクライアントファイルのデータブロックの書き込みを、前記クライアントファイルの前記データブロックのいくつかが、前記ワイド・エリア・ネットワーク上で前記第２のデータセンターに送信される前に完了するように構成される
請求項１に記載のクラスター。
【請求項１８】
前記複数の第１の名前ノード及び前記複数の第１のデータノードは、クライアントファイルの複数のデータブロックが前記第１のデータセンター内で第１の所定のかつ選択可能な回数複製されることとなるように構成され、
前記複数の第２の名前ノード及び前記複数の第２のデータノードは、前記クライアントファイルの前記複数のデータブロックが前記第２のデータセンター内で第２の所定のかつ選択可能な回数複製されることとなるように構成される
請求項１に記載のクラスター。
【請求項１９】
前記第１の所定のかつ選択可能な回数は、前記第２の所定のかつ選択可能な回数と同じである
請求項１８に記載のクラスター。
【請求項２０】
前記第１の所定のかつ選択可能な回数は、前記第２の所定のかつ選択可能な回数とは異なる
請求項１８に記載のクラスター。
【請求項２１】
前記調整エンジンプロセスは、前記第１及び第２の複数の名前ノードのそれぞれの中で動作するよう構成される
請求項１に記載のクラスター。
【請求項２２】
メタデータ及びファイルシステムのデータは、第１及び第２のデータセンターにわたって複製される
請求項１に記載のクラスター。
【請求項２３】
ワイド・エリア・ネットワーク上に広がる単一の分散ファイルシステムと、複数の第１の名前ノード及び複数のクライアントファイルの複数のデータブロックを格納するように構成された複数の第１のデータノードを含む第１のデータセンター、並びに、地理的に離れ、かつ、複数の第２の名前ノード及び複数のクライアントファイルの複数のデータブロックを格納するように構成された複数の第２のデータノードを含む第２のデータセンターを含むクラスターとを確立すること、
前記複数の第１の名前ノードのそれぞれの中に、及び、前記複数の第２の名前ノードのそれぞれの中に、前記クラスターの名前空間の状態を格納すること、
前記複数の第１及び第２のデータノードに複数のデータブロックが書き込まれたことに応答して、前記複数の第１の名前ノード及び前記第２の名前ノードの中に格納される前記名前空間の状態を更新すること、及び、
前記複数の第１の名前ノード内に格納され、かつ、前記複数の第２の名前ノード内に格納される前記名前空間の前記状態に対する更新を、前記名前空間の前記状態が前記クラスターの前記第１及び第２のデータセンターにわたって首尾一貫した状態を維持するよう調整すること
を含むコンピュータに実装された方法。
【請求項２４】
前記複数の第１の名前ノード内に格納される前記名前空間の前記状態を更新することは、前記名前空間の前記状態を更新するよう構成された前記複数の第１の名前ノードのそれぞれを用いて、前記第１のデータセンター内の１以上の他の前記第１の名前ノードもまた前記名前空間の前記状態を更新する間に実行される
請求項２３に記載のコンピュータに実装された方法。
【請求項２５】
前記複数の第２の名前ノード内に格納される前記名前空間の前記状態を更新することは、前記名前空間の前記状態を更新するよう構成された前記複数の第２の名前ノードのそれぞれを用いて、前記第２のデータセンター内の１以上の他の前記第２の名前ノードもまた前記名前空間の前記状態を更新する間に実行される
請求項２３に記載のコンピュータに実装された方法。
【請求項２６】
前記複数の第１の名前ノードに格納される前記名前空間の前記状態を更新することは、前記複数の第２の名前ノード内に格納される前記名前空間の前記状態を更新している間に実行される
請求項２３に記載のコンピュータに実装された方法。
【請求項２７】
前記複数の第１のデータノードのそれぞれが前記第１のデータセンター内の前記複数の第１の名前ノードとのみ通信することを可能にすること、及び
前記複数の第２のデータノードのそれぞれが前記第２のデータセンター内の前記複数の第２の名前ノードとのみ通信することを可能にすること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項２８】
調整エンジンプロセスによって、前記名前空間の前記状態を更新することについての前記第１及び第２の複数の名前ノードからの提案を受信すること、及び、
呼応して、前記複数の第１及び第２の名前の度がそれぞれに格納している前記名前空間の状態を更新する順序を特定する順序付けられた同意のセットを生成すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項２９】
前記複数の第１及び第２の名前ノードが、前記調整エンジンプロセスから前記順序付けられた同意のセットが受信されるまで、前記名前空間の前記状態に対する更新を行うことを遅延させること
をさらに含む請求項２８に記載のコンピュータに実装された方法。
【請求項３０】
調整エンジンプロセスが、前記複数の第１及び第２の名前ノードのうちの１以上の障害又は前記複数の第１及び第２のデータノードのうちの１以上の障害の際に、前記名前空間の前記状態を首尾一貫した状態に維持すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３１】
調整エンジンプロセスが、前記第１及び第２のデータセンターの障害の際に、前記名前空間の前記状態を首尾一貫した状態に維持すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３２】
前記分散ファイルシステムは、ハドゥープ分散ファイルシステム（ＨＤＦＳ）の１バージョンを含む
請求項２３に記載のコンピュータに実装された方法。
【請求項３３】
前記第１のデータセンターのクライアントのファイルの複数のデータブロックの少なくともいくつかのレプリカを、前記第２のデータセンター内の前記複数の第２のデータノードのうちの選択された１つに格納すること、及び、
前記第２のデータセンターのクライアントのファイルの複数のデータブロックの少なくともいくつかのレプリカを、前記第１のデータセンター内の前記複数の第１のデータノードのうちの選択された１つに格納すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３４】
前記第１のデータセンターの前記複数の第１のデータノードのそれぞれにより、選択された複数のデータブロックを、前記ワイド・エリア・ネットワーク上で、前記第２のデータセンターの前記複数の第２のデータノードのうちの選択された１つに対して送信すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３５】
前記選択された複数のデータブロックを、前記選択された複数のデータブロックの所定数のレプリカが前記第１のデータセンター内の前記複数の第１のデータノードのうちの選択された１つに格納された後、前記第１のデータセンターから前記第２のデータセンターに送信すること
をさらに含む請求項３４に記載のコンピュータに実装された方法。
【請求項３６】
前記複数の第１の名前ノードのうちの少なくともいくつかにより、前記複数の第２の名前ノードによる消費のために、前記複数の第１のデータノード内に格納されるすべてのデータブロックのリストを含むブロック報告を生成すること、及び、
前記複数の第２の名前ノードのうちの少なくともいくつかにより、前記複数の第１の名前ノードによる消費のために、前記複数の第２のデータノード内に格納されるすべてのデータブロックのリストを含むブロック報告を生成すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３７】
生成された前記ブロック報告は、ブロック報告ファイルとして前記ファイルシステムに書き込むこと、及び、
前記第１及び第２のデータセンター内の前記第１及び第２の名前ノードのそれぞれにより、前記ファイルシステムから前記ブロック報告ファイルを周期的に読み出すこと
をさらに含む請求項３６に記載のコンピュータに実装された方法。
【請求項３８】
前記複数の第１の名前ノード及び前記複数の第１のデータノードが、前記第１のデータセンターのクライアントファイルのデータブロックの書き込みを、前記クライアントファイルの前記データブロックのいくつかを、前記ワイド・エリア・ネットワーク上で前記第２のデータセンターに対して送信する前に完了すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項３９】
前記複数の第１の名前ノード及び前記複数の第１のデータノードが、クライアントファイルの複数のデータブロックが前記第１のデータセンター内で第１の所定のかつ選択可能な回数複製されるようにすること、及び、
前記複数の第２の名前ノード及び前記複数の第２のデータノードは、前記クライアントファイルの前記複数のデータブロックが前記第２のデータセンター内で第２の所定のかつ選択可能な回数複製されるようにすること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項４０】
前記第１の所定のかつ選択可能な回数は、前記第２の所定のかつ選択可能な回数と同じである
請求項３９に記載のコンピュータに実装された方法。
【請求項４１】
前記第１の所定のかつ選択可能な回数は、前記第２の所定のかつ選択可能な回数とは異なる
請求項３９に記載のコンピュータに実装された方法。
【請求項４２】
前記第１及び第２の複数の名前ノードのそれぞれの中で調整エンジンプロセスを実行すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【請求項４３】
メタデータ及びファイルシステムのデータを、第１及び第２のデータセンターにわたって複製すること
をさらに含む請求項２３に記載のコンピュータに実装された方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、主題において、本願と同一出願人によるものであり、かつ本願と同時に係属中である２０１３年８月２９日出願の米国特許出願１４／０１３，９４８及び２０１３年９月３０日出願の米国特許出願１４／０４１，８９４に関連する。本願はまた、主題において、本願と同一出願人によるものであり、かつ本願と同時に係属中である２００８年２月１３日出願の米国特許出願１２／０６９，９８６に関連する。この米国特許出願１２／０６９，９８６は、既に米国特許８,３６４,６３３として登録されている２００６年１月１１日出願の米国特許出願１１／３２９，９９６の分割出願である。米国特許８,３６４,６３３は、２００５年１月１２日出願の米国仮出願６０／６４３，２５７、２００５年１月１２日出願の米国仮出願６０／６４３，２５８、２００５年１月１２日出願の米国仮出願６０／６４３，２６９の利益を主張している。この出願はまた、主題において、本願と同一出願人によるものであり、かつ本願と同時に係属中であり、さらに２０１２年１２月２８日出願の米国仮出願６１／７４６，８６７の利益を主張する２０１３年３月１５日出願の米国特許出願１２／８３５，８８８に関連し、また、主題において、本願と同一出願人によるものであり、かつ本願と同時に係属中であり、さらに２０１２年１２月２８日出願の米国仮出願６１／７４６，９４０の利益を主張する２０１３年３月１５日出願の米国特許出願１３／８３７，３６６に関連する。これらそれぞれの開示は、その全体において、参照することにより本書に組み込まれる。
【０００２】
本書に開示される実施の形態の分野は、分散ファイルシステムを含む。特に、実施の形態は、例えばインターネットを含むワイド・エリア・ネットワーク（ＷＡＮ）上で地理的に分散した名前ノード及びデータノードを用いる分散ファイルシステム（及び、それによって可能とされる機能）に関連する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｌａｍｐｏｒｔ，Ｌ．、「Ｔｈｅ  Ｐａｒｔ  Ｔｉｍｅ  Ｐａｄｉａｍｅｎｔ，ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍｓ  １６，２」、１９９８年５月、ｐ．１３３−１６９
【非特許文献２】Ｂｅｒｎｓｔｅｉｎ等、「Ｃｏｎｃｕｒｒｅｎｃｙ  Ｃｏｎｔｒｏｌ  ＆  Ｒｅｃｏｖｅｒｙ  ｉｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ」、Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ、１９８７年、６，７，８章
【図面の簡単な説明】
【０００４】
【図１】従来のＨＤＦＳ実装を示す図である。
【０００５】
【図２】分散ファイルシステムについて、一実施の形態によるコンセンサス名前ノードを更新することの側面を示す図である。
【０００６】
【図３】一実施の形態による、分散ファイルシステム内におけるブロックの複製と生成の方法の側面を説明する図である。
【０００７】
【図４】一実施の形態による、ブロックの複製のさらなる側面を説明する図である。
【０００８】
【図５】一実施の形態による、ブロックの複製のさらなる側面を説明する図である。
【０００９】
【図６】一実施の形態による、複数のコンセンサス名前ノードにわたってユニークとなるようにブロック識別子が生成され得る１つの方法を説明する図である。
【００１０】
【図７】一実施の形態による、クライアントファイルのデータブロックを格納するように構成された複数のデータノードを含む分散ファイルシステムを実行するコンピュータに実装された方法を示すフローチャートである。
【００１１】
【図８】一実施の形態による、ＷＡＮに広がる分散ファイルシステムの構成要素を示すブロック図である。
【００１２】
【図９】一実施の形態による方法を示すフローチャートである。
【発明を実施するための形態】
【００１３】
ハドゥープ分散ファイルシステム（ＨＤＦＳ）名前空間は、ファイルとディレクトリの階層である。ファイル及びディレクトリは、アイノード（アイノード）によって、名前ノード上に表現される。アイノードは、許可、修正及びアクセスの時刻、名前空間、及びディスク空間の割当量などの属性を記録する。ファイルの内容は、大きなデータブロック（典型的には１２８ＭＢ）に分割され、ファイルの各データブロックは、複数（典型的には３つ）のデータノードで独立して複製される。名前ノードは、ＨＤＦＳのメタデータサービスであり、名前空間の操作に対して責任を負っている。名前ノードは、名前空間ツリーと、データブロックへのブロックのマッピングとを維持する。すなわち、名前ノードは、ハドゥープクラスタ内でデータの位置を追跡し、それらにクライアントアクセスを適合させる。従来、各クラスタは単一の名前ノードを有する。各データノードは複数のアプリケーションタスクを同時に実行することができるので、クラスタは、クラスタごとに、数千のデータノードと、数万のＨＤＦＳクライアントとを持つことができる。アイノードと、名前システムのメタデータを定義するデータブロックのリストとは、イメージと呼ばれる。名前ノードは、ＲＡＭ内に名前空間の全体を保持する。イメージの永続的な記録は、チェックポイント、及び、そのチェックポイントが生成されてから実行された名前空間に対する更新を表すジャーナルとして、名前ノードのローカルなネイティブファイルシステム内に格納される。
【００１４】
分散システムは、ノードと呼ばれる様々な構成要素からなる。システムを無矛盾に保つために、ノード間に分散された様々なイベントを調整することが必要になり得る。すべてのノードにより無矛盾で学ばれなければならない特定のイベントを調整するための最も簡単な方法は、指定された単一のマスターを選び、他のノードがそのマスターからイベントを学べるよう、そのマスターにそのイベントを記録することである。簡単ではあるけれども、単一のマスターの障害がシステム全体の前進を麻痺させることから、このアプローチは信頼性に欠ける。この認識の下、図１に示すように、従来のＨＤＦＳ実装は、通常動作時にアクセスされるアクティブ名前ノード１０２と、アクティブ名前ノード１０２が障害となった場合にフェイルオーバーとして使用されるスタンバイ名前ノード１０４と呼ばれるバックアップとを使用する。
【００１５】
図１に示すように、従来のＨＤＦＳクラスタは、次のように動作する。ＨＤＦＳクライアントが、例えばファイル又はディレクトリを生成するためにリモート・プロシージャ・コール（ＲＰＣ）を発行したときのように、名前空間に対する更新が要求されたとき、アクティブ名前ノード１０２は、図１に示すように、
１．クライアントから要求（例えば、ＲＰＣ）を受信し、
２．そのメモリ状態に直ちに更新を適用し、
３．共有の永続的記憶装置１０６（１つ以上のハード・ドライブを含むネットワーク接続ストレージ（ＮＡＳ）のようなもの）にジャーナルとして更新を書き込み、成功の通知をクライアントに返す。
スタンバイ名前ノード１０４は、今や、自身の状態を更新することによりアクティブ名前ノード１０２との首尾一貫性を維持しなければならない。その目的のためにスタンバイ名前ノード１０４は、
４．トランザクション・ジャーナル１０６からジャーナル・トランザクションを読み出し、
５．自身の状態を更新する。
【００１６】
しかしながら、この方法は最適ではない解決法であると信じられている。例えば、このスキームでは、トランザクション・ジャーナル１０６自身が単一障害点となる。実際、トランザクション・ジャーナル１０６が破損すると、スタンバイ名前ノード１０４がアクティブ名前ノード１０２と同じ状態であることは仮定できなくなり、アクティブからスタンバイへのフェイルオーバーはもはや不可能となる。
【００１７】
さらに、クラスタごとにただ１つのアクティブ名前ノードをサポートするハドゥープ・ソリューションでは、スタンバイ・サーバは典型的には、上記したように、ネットワーク接続ストレージ（ＮＡＳ）装置を介して同期状態に維持される。もしアクティブ名前ノードが障害を起こし、スタンバイが引き継がなければならなくなったとして、もしアクティブ名前ノードに書き込まれた変更がまだＮＡＳに書き込まれていなかったとしたら、データ損失の可能性がある。フェイルオーバーの管理者エラーは、さらなるデータ損失を引き起こし得る。さらに、もしアクティブサーバがスタンバイサーバと通信できないけれども、クラスタ内の他のマシンとは通信できるようなネットワーク障害が起きたとしたら、そして、スタンバイサーバが誤ってアクティブサーバが死んだと思い込み、アクティブの役割を引き継ぐとしたら、２つのノードがそれぞれアクティブ名前ノードであると信じる「分離脳」として知られる病的なネットワーク状態が発生する。この状態は、データの破損を引き起こし得る。
【００１８】
例えば、ランポート．Ｌによって書かれ、全体として本書に取り込まれる「The Part-Time Parliament, ACM Transactions on Computer Systems 16, 2 (May 1998), 133-169」には、プロポーザ（メンバーシップに対する提案を行う処理）、アクセプタ（メンバーシップにより同意されるべきか否かを投票する処理）、及びラーナー（作成済みの同意を学ぶメンバーシップ内の処理）の役割が定義されている。一実施の形態によれば、上記役割のそれぞれに複数のノードが構成され得る。（図２の２０８で示されるような）調整エンジンは、高い可用性を実現するため、複数のアクセプタの助けを借りた複数のプロポーザによってエンジンに提出されたイベントの順序について、複数のラーナーが同意することを許可することができる。一実施の形態によれば、信頼性、可用性、及び拡張性を達成するため、複数のノードにおいて名前空間の状態を複製することによって、複数の同時にアクティブな名前ノードが、名前空間が複製されるノードの状態がそれらのノード間で首尾一貫した状態を維持することの要求とともに提供され得る。
【００１９】
名前ノード間のこの一貫性は、提案を受け付けて名前空間を更新し、提案をグローバルな更新の配列に整備し、その後にのみ、各名前ノードが更新を学び、同意された順序で個々の状態に適用することを許可する調整エンジンによって保証され得る。ここで、「一貫性」は、１９８７年にアディソン・ウェスリーによって発行され、全体として本書に取り込まれるバーンスタインらの「Concurrency Control & Recovery in Database Systems」の第６章、第７章、第８章に詳述されているように、ワンコピー・エクイバレンス(One-Copy Equivalence)を意味する。各名前ノードは、同じ状態からスタートし、同じ決定論的な更新を同じ決定論的な順序で適用するものであるから、それぞれの状態は一貫した状態に保たれる。
【００２０】
一実施の形態によれば、名前空間はそれゆえ、以下の点を条件として複数の名前ノード上で複製され得る。
ａ）各ノードがその名前空間のレプリカを修正することについて許可されている。
ｂ）ある名前空間のレプリカに対する更新は、名前レプリカが複数のノードにわたって互いに一貫性を保つよう、他のノード上の名前空間のレプリカに伝搬されなければならない。
Ｉ．ローカル・エリア・ネットワーク（ＬＡＮ）上の分散ファイルシステム
【００２１】
一実施の形態はそれゆえ、最も問題となる可用性にインパクトを与える単一障害点、すなわち１つの名前ノードを取り除く。慣習的には、もし１つの名前ノードが利用できなくなると、ハドゥープクラスタはダウンし、アクセスを復活させるために複雑なフェイルオーバーの手続き（以前のアクティブ名前ノードからスタンバイ名前ノードへ切り替えることなど）が必要となる。この潜在的な単一障害点を扱うため、一実施の形態は、複数のアクティブ名前ノードサーバ（以下では、コンセンサス・ノード又はＣノードなど様々な呼び方をする）に対し、それぞれが連続的に同期され、かつ、ＭａｐＲｅｄｕｃｅを用いるバッチ・アプリケーションやＨＢａｓｅを用いるリアルタイム・アプリケーションのためのアクセスを含むクライアントアクセスを同時に提供する仲間として振る舞うことを許可する。一実施の形態によれば、名前ノードが障害状態となったり、メンテナンス又はユーザによる他の理由のためにオフラインとなるとき、他の仲間のアクティブ生江ノードサーバは常に利用可能であり、このことは、ＨＤＦＳメタデータに対する読み出し又は書き込みのアクセスに中断がないことを意味する。このサーバがオンラインに戻るとすぐに、その名前ノードは、自動的に回復し、合間に発生した可能性のある名前空間に対するすべての新たな変更を通告され、クラスタ上の他のすべての名前ノードの名前空間を一致させるべくその名前空間を同期させる。この名前ノードは、他のノードが変化を学んだときと同じ決定論的な順序で変化を学ぶので、他のレプリカと調和した状態になるであろう。
【００２２】
図２は、分散ファイルシステムについて、ＬＡＮ環境における特定の実用性を見い出す一実施の形態によるコンセンサス・ノードを更新することの側面を示す図である。一実施の形態によれば、クラスタは、単一のアクティブ名前ノード及びスタンバイ名前ノードではなく、調整エンジン２０８によって調整される複数（好ましくは奇数。例えば、３，５，７・・・）の名前ノードを含み得る。上述したように、本明細書では、調整された名前ノードはコンセンサス・ノードと呼ばれ、以下ではＣノードと称する。図２に示すように、一実施の形態は、それぞれ調整エンジン２０８とつながれた３つのＣノード２０２，２０４，２０６を含み得る。一実施の形態によれば、調整エンジン２０８は、ネットワーク上で互いの連携を取るエージェントを有する各ノードにおけるエージェントとして構成され得る。しかしながら、参照及び描画の簡単のため、調整エンジン２０８は、図２及び図４においては、分離した単一の実体であるとして示されている。一実施の形態によれば、名前空間に対する更新は、名前ノード２０２，２０４，２０６のうちの１つのインスタンス上で発議され、調整エンジン２０８により首尾一貫した方法で、他のインスタンスに伝えられる。この方法では、クライアントは、名前ノードのすべてのインスタンスにわたって首尾一貫した名前空間にアクセスする。ここに開示される複製方法は、ＨＤＦＳのような分散ファイルシステムのための高い可用性を有するアクティブ−アクティブモデルを提供するものであり、その中においては、メタデータ要求（読み出し又は書き込み）は、複数の名前ノードのインスタンスの間で、負荷分散され得る。
【００２３】
調整エンジン２０８は、名前空間の更新のグローバルな順序を決定するように構成され得る。名前空間のすべてのインスタンスが同じ状態から開始し、すべてのノードが同じ決定論的な順序で更新を適用するように制御される（ただし、実施の形態によれば、同時である必要はない）ので、名前空間の複数のインスタンスの状態は、ノード間で首尾一貫した状態に維持される（又は、首尾一貫した状態とされる）。
【００２４】
一実施の形態によれば、図２に示すように、複数のＣノードレプリカ２０２，２０４，２０６に対する首尾一貫した更新は、次のように実行され得る。（１）に示すように、複数のＣノードのうちの１つ（この場合、Ｃノード２０２）が、名前空間を更新することについての要求をクライアントから受信する。そのような名前空間の更新は、図２ではＲＰＣ３として識別されるＲＰＣを含むことができる。同様に、この例では、Ｃノード２０４はＲＰＣ１を受信し、Ｃノード２０６はＲＰＣ２を受信する。これらのＲＰＣは、例えば、ファイルにデータブロックを追加すること、ファイルを生成すること、ディレクトリを生成することについての要求を含み得る。一実施の形態によれば、Ｃノード２０２がＲＰＣ３内に含まれるイベント（例えば、読み出し、書き出し、削除など）により自身の状態を直ちに更新し、Ｃノード２０４が受信されたＲＰＣ１内に含まれるイベントにより自身の状態を直ちに更新し、Ｃノード２０６が受信されたＲＰＣ２内に含まれるイベントにより自身の状態を直ちに更新し、その後、Ｃノード２０２，２０４，２０６のうちの他のものに対して更新された名前空間を伝えるのではなく、代わりに、各Ｃノードの名前空間レプリカに対するこれらの独立した更新は調整エンジン２０８に対して提案として伝えられ、調整エンジン２０８はその後、Ｃノード２０２，２０４，２０６に対して対応する同意を発行する。実際、一実施の形態によれば、Ｃノード２０２，２０４，２０６によって格納される名前空間レプリカを首尾一貫した状態に保つメカニズムは、調整エンジン２０８に対して提案を発行し、調整エンジン２０８から同意を受信することによるものである。すなわち、図２に示すように、Ｃノード２０２は、ＲＰＣ３の受信に応じて、（２）で示されるように、提案Ｐｒｏｐ３を調整エンジン２０８に対して発行することができる。同様に、Ｃノード２０４は、ＲＰＣ１の受信に応じて、（２）で示されるように、提案Ｐｒｏｐ１を調整エンジン２０８に対して発行することができ、Ｃノード２０６は、ＲＰＣ２の受信に応じて、（２）で示されるように、提案Ｐｒｏｐ２を調整エンジン２０８に対して発行することができる。調整エンジン２０８は、一実施の形態によれば、その後、（３）で示されるように、受信した提案を順序付け、（４）で示されるように、順序付けられた同意（この場合、ＡＲＧ３，ＡＧＲ１，ＡＧＲ２のように順序付けられる）をＣノード２０２，２０４，２０６にフィードバックする。Ｃノード２０２，２０４，２０６は、順序付けられた一連の同意ＡＲＧ３，ＡＧＲ１，ＡＧＲ２を受け取ると、その決定論的な順序でそれぞれのメモリ状態にこれらの同意を適用し、それによって、名前空間のレプリカがＣノード２０２，２０４，２０６にわたって首尾一貫した状態に保たれ得る。この方法では、Ｃノード２０２，２０４，２０６の状態は、一貫性を失うことなく、（５）に示すように非同期で更新され得る。これらの更新はその後、Ｃノード２０２，２０４，２０６に結合され又はアクセス可能とされる（しかし、２１０，２１２，２１４における破線によって示唆されるように必須ではない）それぞれのローカルな永続的記憶装置２１０，２１２，２１４内に、ジャーナルトランザクションとして保存されてもよい（必須ではない）。その後、Ｃノード２０２，２０４，２０６のクライアントに対し、更新の成功を知らせる通知が戻され得る。
【００２５】
したがって、一実施の形態によれば、Ｃノード２０２，２０４，２０６は、クライアントの要求をそれぞれの状態に直接的に適用するのではなく、順序付けのために、それらを提案として、調整エンジン２０８に向けてリダイレクトする。Ｃノードの更新はその後、順序付けられた同意のセットとして、調整エンジン２０８から発行される。このことは、クライアントがＣノード２０２，２０４，２０６のうちの１つを介して変化を要求したときにすべてのＣノード２０２，２０４，２０６が更新されること、及び、その更新がクラスタ内のすべてのＣノードに対して透明かつ矛盾なく適用されるであろうことを保証する。
【００２６】
例えば、もしクライアントがＣノード２０２を介してディレクトリを生成し、その後、Ｃノード２０４を介して生成したばかりのディレクトリの一覧表を作ろうとするならば、Ｃノード２０４は、「ファイルが見つからない」という例外を返すかもしれない。同様に、クライアントは、図３に関連して以下で詳述するように、あるデータノードから他のデータノードにデータが移行しつつある間、様々なデータノード上で同じブロックのレプリカが異なる長さを有するために、作成中であるファイルの最新のデータブロックを異なるバイト数で読み出すかもしれない。これは、「陳腐な読み出し」問題として知られる。
【００２７】
したがって、一実施の形態によれば、調整エンジン２０８の重要な役割は、すべてのＣノードからの名前空間の状態の修正提案を処理し、それらをグローバルに順序付けられた同意のシーケンスに変形することである。Ｃノードはその後、それらの状態に対する更新として、その順序付けられたシーケンスからの同意を適用し得る。一実施の形態によれば、同意は、ユニークな単調に増加する数として構成され得るグローバルシーケンス番号（ＧＳＮ）に従って順序付けられ得る。ＧＳＮは、さもなければ、当該技術分野における当業者が理解できるように構成されればよい。ＧＳＮはその後、名前空間の状態を更新し、複数のＣノードにわたってその名前空間の状態を首尾一貫した状態に保つことに関して、色々なＣノードの進歩を比較するために使用され得る。例えば、もしＣノード２０２が、Ｃノード２０４によってちょうど処理されたＧＳＮ２より小さいＧＳＮ１が付与された同意をちょうど処理したところであれば、Ｃノード２０２は、Ｃノード２０４より早い時期の名前空間の状態を持っている。
【００２８】
一実施の形態によれば、クライアントは、それぞれ操作とともに、クライアントが現在接続されているＣノード上で処理されている最新のＧＳＮについて学ぶ。その後、もしクライアントが他のＣノードに切り替わるとすれば、クライアントは、一実施の形態によれば、データアクセスコマンドを含むＲＰＣを発行する前に、初めに（必要であれば）Ｃノードがクライアントの知っている最新のＧＳＮ（すなわち、クライアントが以前にアクセスしていたＣノードから受信したＧＳＮ）に追いつくまで待機する。これにより、陳腐な読み出しの問題を回避することが可能になる。
【００２９】
一実施の形態によれば、名前空間の状態を更新する操作だけが調整エンジン２０８によって調整される必要がある。すなわち、ほとんど（以下で詳細を説明する一実施の形態によれば、すべてではない）の読み出し要求は、名前空間の状態を変えるものでないことから、クライアントが接続されている任意のＣノードによって直接的に提供される。一実施の形態によれば、調整エンジン２０８は、すべての与えられた瞬間においてＣノード２０２，２０４，２０６が同じ状態を有していることを保証するものではない。むしろ調整エンジン２０８は、すべてのＣノード２０２，２０４，２０６が、すべての更新について、すべての他のＣノード及びクライアントがこの情報を見ることができるよう、同じ順序で矛盾なく学習することを保証するものである。この方法では、調整エンジン２０８は、すべてのＣノード２０２，２０４，２０６に対して等しく供給されるグローバルに順序付けられた一連のイベントを生成するように構成される。
【００３０】
一実施の形態によれば、ローカルな永続記憶装置２１０，２１２，２１４に対するジャーナルの更新が実行され得る。しかしながら、Ｃノード２０２，２０４，２０６の一貫性はそのようなジャーナルの更新に依存するものではなく、かつ、それぞれの永続的記憶装置（もしあれば）は、一実施の形態によれば、Ｃノードに対してローカルであり、複数のＣノードにわたって共有されるものではない。同様に、Ｃノード２０２，２０４，２０６にわたって名前空間の状態の一貫性を維持することは、メモリやプロセッサリソースのような他のリソースを共有することに依存するものではない。
【００３１】
実施の形態によれば、好ましい（マスターである、又は、他の方法で区別される）Ｃノードは存在しない。実際、１以上のＣノードが故障した場合、又は、メンテナンス（又は他の任意の理由）のためにオフラインとなった場合、他のアクティブなＣノードサーバが、アクセスの中断なくクライアントにサービスを提供するために、いつも利用可能である。一実施の形態によれば、サーバがオンラインに復帰するとすぐに、以下で説明するように、そのサーバは自動的に他のＣノードサーバと再同期する。そのような再同期は、そのＣノードがダウンし又はオフラインとされて以来調整エンジン２０８によって発行されたすべての同意を学習することを含み得る。すべてのＣノードがアクティブであり、常に同期状態に維持され又は同期状態とされるとき、分離脳状態及びデータ損失はともに除去され、それによって、デフォルトで継続的なホットバックアップが提供される。フェイルオーバー及びリカバリが即座かつ自動的に実行され、手動の介在の必要性及び管理者エラーのリスクを除去する。さらに、Ｃノード２０２，２０４，２０６のいずれもが、受動的なスタンバイ名前ノードとして構成されることはない。実際、一実施の形態によれば、クラスタ内のすべてのＣノードサーバは、クライアント要求を同時にサポートするように構成される。したがってこのことは、クラスタが、付加の増加によって性能を犠牲にすることなく、追加的なＣノードサーバをサポートするために拡張されることを可能にする。一実施の形態によれば、受動的なスタンバイサーバは存在せず、アクティブな名前サーバが単一であることによる脆弱性及びボトルネックは完全に除去される。さらに、複数のＣノード２０２，２０４，２０６にわたってクライアント要求を分配することは、本質的に、すべての利用可能なＣノードに処理負荷及びトラフィックを分配する。すべてのクライアント要求が単一の名前ノードによってサービスされるアクティブ／スタンバイ名前ノードのパラダイムに比べ、Ｃノード２０２，２０４，２０６にわたるアクティブな負荷平衡を実行することも可能である。
【００３２】
図３は、一実施の形態による、分散ファイルシステム内におけるブロックの複製と生成の方法の側面を説明する図である。３５０において、図３は、ＨＤＦＳ内に格納されるファイルを示している。一実施の形態によれば、ストレージの単位はブロックと称されることができ、ブロックのサイズはかなり大きいものであり得る。例えば、ブロックサイズは、１２８ＭＢの物理ストレージであってもよい。他のブロックサイズも容易に実行され得る。ファイル３５０は、複数の１２８ＭＢのデータブロックを含むものとして、図３に示されている。ブロックサイズは、１２８ＭＢである必要はない。一実施の形態によれば、１ファイル内の各データブロックは、複数のデータノード上で複製され得る（すなわち、全く同じように格納され得る）。３０２，３０４，及び３０６にはそのようなデータノードが示されており、これらはＣノード２０２のような１以上のＣノードと結合するように構成される。一実施の形態によれば、各データノードは、クラスタ上の複数のＣノードのそれぞれと通信するように構成され得る。ファイルのデータブロックは、５つ又は７つのデータノードのような、より多くの数のデータノード上に格納され得る。複数のデータノード上に各データブロックを格納することは、冗長性を通じてデータの信頼性を提供する。
【００３３】
図２に示すように、クライアントはＣノード２０２に対してメッセージ（例えば、ＲＰＣ）を送り、それによって、ファイルを生成し、ファイルに対して１ブロックのデータを書き込むというクライアントの意図を示す。一実施の形態によれば、Ｃノード２０２はその後、この新たに生成されたファイルのデータブロックが複製されるであろう複数のデータノード３０２，３０４，及び３０６（この例示の実装では３つ）を選択することができ、そのことをクライアントに通知する。クライアントはその後、一実施の形態によれば、３つのデータノード３０２，３０４，及び３０６のうちの選択された１つに対し、データのストリーミング（若しくは送信）を開始することができる。そのようなストリーミングは、選択されたデータノード（例えばデータノード３０２）に対して、各データブロックの小さなチャンクを順番に送ることによって実行され得る。例えばクライアントは、ファイルの１つ目のデータブロックがデータノード３０２に対して成功裏に伝送されるまでの間、そのファイルの１つ目のデータブロックの６４ＫＢのチャンクのシリアルなストリームを、データノード３０２に対して送信することとしてもよい。クライアントと選択されたデータノード３０２との間のハンドシェイクは、各データブロックが、選択されたデータノード３０２によって成功裏に受信され、格納されることを確実にし得る。１つ目のデータノード３０２に対して送信されたデータチャンクはまた、クライアントのデータブロックが送信されるべき２つ目のデータノード３０４の指示を含み得る。一実施の形態によれば、ファイルのデータブロックのレプリカを受信すべきとしてＣノード２０２によって選択された３つ（又は、それ以上）のデータノードに対してクライアントが直接ファイルのデータブロックを送信することよりも、データブロックのチャンクを受信した１つ目のデータノード３０２がその後、ファイルのデータブロックのレプリカを受信すべき３つのデータノードのうちの次のもの（例えばデータノード３０４）に対して、自分自身で受信したデータチャンクを送信することとしてもよい。同様に、データノード３０４は、データノード３０２によって自身に対して送信されたデータチャンクを成功裏に受信した後、クライアントファイルの構成要素であるデータブロックのレプリカを受信すべきとしてノード２０２によって選択された３つのデータノードのうちの最後のものに対してデータチャンクを送信することとしてもよい。この方法では、Ｃノードによって選択された１つ目のデータノードがＣノードによって選択された２つ目のデータノードに対してデータチャンクを転送し、２つ目のデータノードが、そのファイルのデータブロックを受信すべきとしてＣノードによって選択された２つ目のデータノードに対して、受信したデータチャンクを転送する、というデータの経路が生成される（もし３つ以上のデータノードがそのファイルのブロックを受信すべきである場合、同様に続く）。
【００３４】
一実施の形態によれば、Ｃノードは、クライアントファイルの構成要素であるデータブロックの受信者であるとして自身が選択したデータノードが、実際に、そのデータブロックを受信し格納したことを当然のこととは思わない。その代わりに、一実施の形態によれば、データノード３０２，３０４，３０６は、クライアントファイルの１以上のデータブロックを一旦所有した場合、それがクライアントによって直接、又は、他のデータノードによって、のいずれであるとしても、図３に示すように、自身に送信されたデータデータブロックを今や格納していることをＣノード２０２に対して報告する。少なくともいくつか（一実施の形態によれば、それぞれ）のデータノードは、周期的に、「鼓動」メッセージをＣノードに対して発行し得る。この鼓動メッセージは、発行しているデータノードがまだアクティブであってよい健康状態にある（すなわち、クライアントからのデータアクセス要求に対してサービスを提供できる）ことを、Ｃノードに対して通知するように構成され得る。データノードは、一実施の形態によれば、Ｃノードに対する他のメッセージとして、クライアントファイルの一以上のデータブロックの成功した受信及び格納を報告してもよい。図３に図示した例示の状況では、データノード３０２，３０４，３０６はＣノード２０２に対し、クライアントファイルの１以上のデータブロックを自身が成功裏に受信し格納したことをＣノード２０２に対して報告してもよい。
【００３５】
データノードは、故障し得る。その障害が、データノードとＣノードの間の通信チャネルにおける中断、ファイルサーバの障害、下層の物理ストレージの障害（又は、他の任意の故障）のいずれによるものであるかを問わず、そのような障害は、データブロックが少なくとも故障したデータノードからは利用できないかもしれない、ということを意味する。図４に示した例では、データノード３０６が故障している。一実施の形態によれば、Ｃノード２０２，２０４，２０６は、データノード３０６のこの変化した状態を直ぐには知らされないかもしれない。代わりに、上述した鼓動メッセージの機構は、各データノードの現在に近い（最新の鼓動の時点）状態を知らされる状態にＣノードを維持するためのよい利点として使用され得る。すなわち、一実施の形態によれば、所定時限内に鼓動メッセージを受信すべきＣノードの障害は、Ｃノードによって、鼓動無送信データノードの障害として解釈される。所定時限は、例えば、任意の単一のデータノードからの鼓動メッセージの期待される間隔よりも大きな期間に設定され得る。
【００３６】
図４の例では、データノード３０６は、その最後の鼓動から所定時限内に鼓動メッセージ（図３の「ＨＢ」）を送信することに失敗しており、それ故、故障しており、その中に格納されるデータブロックは、少なくとも現時点でアクセス不能である、と看做され得る。同様に、これは、データノード３０２及び３０４のみが色々なファイルのデータブロックを格納していることを意味する。一実施の形態によれば、Ｃノードは、現時点でアクティブ、かつ、一実施の形態によれば、新たなデータブロックを受け入れ、及び／又は、データアクセス要求に対してサービスを提供する準備ができているデータノードのリスクを保持し得る。そのようなリストは、「アクティブ」リストと称され得る。図４のデータノード３０６のようにデータノードからの期待される鼓動メッセージの受信に障害が発生すると、そのデータノードは故障したものと看做され、Ｃノードは、アクティブリストからその故障したデータノードを削除し得る。一実施の形態によれば、アクティブリストは、クライアントからブロックを生成することについての要求を受信したＣノードが、生成されるファイルのデータブロックが格納されるであろう（例えば）３つのデータノードをそこから選択できるリストであり得る。データノード３０６が故障したとき、データノード３０６はアクティブリストから削除され得、それによって、少なくともＣノードの観点からは、すべての目的のために、そのデータノードは事実上存在しておらずかつ利用不能なものとされる。
【００３７】
クライアントファイルのデータブロックが、データノード３０６の障害に起因して複製不足となっているとき（例えば、所定数のデータノードより少ないデータノードに記憶されているとき）、Ｃノード２０２は、一実施の形態によれば、３つのデータノードのすべてがファイルの構成要素であるデータブロックのレプリカを格納することを確実にするため、クライアントファイルのデータブロックが複製され得る新たなデータノードを選択することができる。一実施の形態によれば、Ｃノード２０２は、アクティブリストを調べ、そのリストからクライアントファイルのデータブロックが複製されるであろう新たなデータノードを選択し、それによって、クライアントファイルのデータブロックのレプリカを格納している複数のデータノードの数を３つ（又は４、５など。ファイルに割り当てられた複製因子による）にまで引き上げる。図４に示す例では、Ｃノード２０２は、データブロックのレプリカもまた格納されるであろうデータノードとしてデータノード４０２を選択し、それによって、データブロックの複製不足を矯正する。一実施の形態によれば、Ｃノード２０２はまた、選択されたデータノード４０２に対して所有しているレプリカを送信するであろうデータノード３０４を選択することができる。図４の４０６に示すように、選択されたデータノード３０４はその後、新たに選択されたデータノード４０２に対し、ブロックのレプリカのデータのチャンクのストリーミングを開始し、又は、さもなければブロックレプリカの送信を開始する。新たに選択されたデータノード４０２は、ブロックレプリカを受信し、データノード４０６がＣノードに対して報告する時間が来ると、新たに受信したブロックのレプリカを今や格納しているということを報告し得る。Ｃノードは、この変化を反映させるために、名前空間を変更することができる。一実施の形態によれば、受信するデータノードは、Ｃノードによってランダムに選択され得る。他の実施の形態によれば、そのような選択は、所定の選択基準に従ってなされ得る。
【００３８】
一実施の形態によれば、Ｃノード２０２，２０４，２０６のそれぞれは、データノード３０２，３０４，３０６，４０２及び自身が周期的に鼓動を受信している他のすべての（潜在的には何千もの）データノードのそれぞれに「気づく」。データノードの障害が発生すると、１以上のＣノードは、送信データノードとして１つのデータノードを選択し、ブロックのレプリカの受信者として他のデータノードを選択することができ、それによって、ブロックが複製不足とならないことを確実にする。このことは、複数のＣノードが、故障したデータノードに以前まで格納されていたデータブロックを格納すべき複数の補充データノードを選択する結果となり得る。すると、そのような並行アクションは、ブロックが複製過剰となる結果となり得る（例えば、意図した３つ，４つ，５つ・・・以上のそのブロックのインスタンスが複製される）。そのような複製過剰はまた、図５に示すように、以前に故障した、又は、さもなければアクセス不能となったデータノードがオンラインに復帰するときにもまた、発生し得る。図５は、以前に故障した、又は、アクセス不能となったデータノード３０６が今や、もう一度動作可能となり、Ｃノード２０２，２０４，２０６に対してアクセス可能となったと仮定したものである。この状態では、クライアントファイルのブロックは今や、４つのデータノード、すなわち、元のノード３０２，３０４、新たに追加されたデータノード４０２、及び、動作しておらずかつアクセス可能なデータノード３０６、に存在している。クライアントファイルのデータブロックはそれ故、複製過剰となっている。データノード３のオンライン復帰状態は今や、すべてのＣノード２０２，２０４，２０６によって知られている（なぜならば、それらが生き返ったデータノード３０６から鼓動を受信したから）ことから、Ｃノード２０２，２０４，２０６のうちの１以上が独立してクライアントファイルのデータブロックのレプリカを削除するデータノードを選択するかもしれない、ということが考えられる。この独立した選択は、クライアントファイルのブロックレプリカが複製過剰状態から複製不足状態となり、最悪のケースでは、すべてのデータノードから削除されてしまう原因となり得る。
【００３９】
そのような事件を防ぐため、一実施の形態によれば、ブロック複製任務は、任意の所与の時点で選択された又は選抜された単一のＣノード、すなわちブロック複製器Ｃノードのために予約され得る。そのようなブロック複製任務は、一実施の形態によれば、ブロック複製を調整すること（すなわち、データノード間で複製されるべきブロックを指示すること）及びブロック削除を調整することを含み得る。ブロック生成の機能は、一実施の形態によれば、そのようなデータ損失又は複製過剰の固有リスクを持ち出さないので、クラスタの各Ｃノードに与えられ得る。したがって、すべてのＣノードは、一実施の形態によれば、ブロック管理任務を実行するように構成され得る。しかしながら、そのようなブロック管理任務は、一実施の形態によれば、単一の選択されたＣノードのために予約されたブロック複製及び削除任務と、クラスタの複数のＣノードのそれぞれに与えられ得るブロック生成任務とに分割され得る。図５にはこのことが示されており、図５では、Ｃノード２０２がブロック複製器機能４１０を有して構成されるただ１つのＣノードとして選択されており、それによって、Ｃノード２０２のみがデータブロックの複製及び／又はデータノードからの削除を実行可能とされる。対照的に、図５に示されるように、Ｃノード２０２，２０４，２０６のそれぞれは、それぞれブロック生成器機能４０８，４１２，及び４１４を実行するように構成されることができ、これによりＣノード２０２，２０４，２０６のいずれもが、それらに報告をしている選択したデータノード上に格納されるべき新たなブロックを生成し又は利用可能とすることが可能になる。
【００４０】
一実施の形態によれば、各データノードは、クラスタ内のすべてのＣノードに対して、すべての通信を送るように構成され得る。すなわち、アクティブであり作動しているデータノードのそれぞれは、独立して、クラスタの各Ｃノードに対し、鼓動、ブロック報告、及び受信された又は削除されたレプリカについてのメッセージを送信するように構成され得る。
【００４１】
ＨＤＦＳの現在の実装では、データノードは単一のアクティブな名前ノードを理解するのみである。このことは、データノードが、アクティブでない名前ノードから来る任意のデータノードコマンドを無視するであろうことを意味する。従来は、もしアクティブでない名前ノードが今やアクティブであると主張し、より高いｔｘＩＤでその状態を確認するならば、データノードは、フェイルオーバー手続きを実行し、新たなアクティブ名前ノードに切り替え、その新たなアクティブ名前ノードからのデータノードコマンドを受け付けるのみとなるであろう。
【００４２】
実施の形態によるＣノードクラスタにおけるこの動作方法に適応するため、ブロック複製任務を有するＣノード（すなわち、現在のブロック複製器）のみが、データノードに対し、その状態がアクティブであるとして報告をする。このことは、ブロック複製器のみがデータノードに対してブロックのレプリカを複製し、又は、削除することを命令する能力を有することを保証する。
【００４３】
アプリケーションは、ＨＤＦＳクライアントを介して、ＨＤＦＳにアクセスする。従来、ＨＤＦＳクライアントは、ファイルのメタデータを求めて単一のアクティブな名前ノードに接触し、その後、データノードからのデータに直接アクセスしていた。実際、ＨＤＦＳの現在の実装では、クライアントは常に、単一のアクティブな名前ノードと会話する。もし、高い可用性（ＨＡ）が可能であれば、アクティブな名前ノードは、スタンバイノードにフェイルオーバーし得る。これが発生するとき、ＨＤＦＳクライアントは、他のフェイルオーバーが発生するまで、新たにアクティブとなった（以前はスタンバイノードであった）名前ノードと通信を行う。フェイルオーバーは、色々な実装を有し得るプラグ接続可能なインターフェイス（例えば、フェイルオーバー・プロキシ・プロバイダ）によって取り扱われ得る。
【００４４】
しかしながら、実施の形態によれば、Ｃノードはいつでもすべてアクティブであり、クライアントに対して名前空間の情報を提供するために等しく使用され得る。一実施の形態によれば、ＨＤＦＳクライアントは、例えばＣノード・プロキシと呼ばれるプロキシ・インターフェイスを介してＣノードと通信するように構成され得る。一実施の形態によれば、Ｃノード・プロキシは、ランダムにＣノードを選択し、このランダムに選択されたＣノードに対してクライアントのＲＰＣ要求を送るための通信ソケットを開くよう構成され得る。クライアントはその後、通信タイムアウト又は障害が発生するまで、このＣノードのみに対してＲＰＣ要求を送る。通信タイムアウトは、設定可能であり得る。通信タイムアウトが発生するとき、クライアントは、（例えば、Ｃノード・プロキシによってランダムに選択された）他のＣノードに切り替え、この新たなＣノードに対する通信ソケットを開き、この新たにランダムに選択されたＣノードに対してのみＲＰＣ要求を送ることができる。負荷平衡の目的のため、例えば、この通信タイムアウトは、低い値に設定され得る。実際、もしクライアントがそのＲＰＣ要求を送るＣノードがビジーであれば、応答における遅延は通信タイムアウトの低い値より大きくなり得、それにより、クライアントがＣノード・プロキシを介して通信相手のＣノードを切り替えることのきっかけとなる。
【００４５】
実際、ＨＤＦＳクライアントによるＣノードのランダムな選択は、複製されたＣノードと通信する複数のクライアントの負荷平衡を可能にする。Ｃノード・プロキシがクライアントの通信相手となるＣノードをランダムに一旦選択したら、クライアントは、一実施の形態によれば、そのランダムに選択されたＣノードがタイムアウトし、又は、故障するまで、そのＣノードに「貼り付く」ことができる。この同じＣノードに対する「貼り付き」は、上で議論した陳腐な読み出しの機会を、フェイルオーバーのケースのみに減らす。Ｃノード・プロキシは、例えばＣノードが再起動しており、サービスのための準備が完全にはできていない（例えば、ダウンしている間に取り損なった同意を学習している）ときに発生するセーフモードにあるＣノードを選択しないように構成されることができる。
【００４６】
上で議論した陳腐な読み出しの問題が、１つの例を通じてさらに説明される。例えば、もしクライアントがＣノード１を介してディレクトリを作成し、その後、同じ又は他のクライアントがその生成されたばかりのディレクトリをＣノード２を介して列挙しようとし、Ｃノード２は、その学習プロセスが遅れており、そのディレクトリを生成するための同意をまだ受信又は処理していないために、ファイルが見つからないという例外を返すかもしれない。同様に、クライアントは、データが転送中である間、同じブロックのレプリカが異なるデータノード上で異なる長さを有するために構築中であるファイルの最後のブロックの色々な数バイトを読み出すかもしれない。
【００４７】
陳腐な読み出しの問題は、それ自身、以下の２つのケースで明らかになる。
１．同一のクライアントが（例えば障害、意図的な中断により、又は、負荷平衡の目的のために）、より古い名前空間状態を有する新たなＣノードに切り替わる。
２．あるクライアントが、他のクライアントによって見られる必要のある名前空間を修正する。
【００４８】
一実施の形態によれば、１つ目のケースは、プロキシ・インターフェイスであるＣノード・プロキシに、接続されているＣノードのＧＳＮに気付かせることによって回避され得る。それぞれの動作により、ＨＤＦＳクライアントは、Ｃノード上のＧＳＮについて学習する。クライアントが（例えば、Ｃノードの障害、タイムアウト、理由は何であれそのＣノードの故意のシャットダウンのために）他のＣノードに切り替わるとき、そのクライアントは、Ｃノード・プロキシを介して、自身が既に見ていたものより小さくないＧＳＮを有するＣノードを選ぶか、又は、その新たなＣノードが、クライアントが以前のＣノードから受信した最新のＧＳＮに追いつくまで待機するべきである。
【００４９】
２つ目のケースは、マップ・リデュースのジョブが開始するときに起きる。このケースでは、マップ・リデュースのクライアントはｊｏｂ．ｘｍｌのようなジョブ構成ファイルをＨＤＦＳ内に起き、それがその後、クラスタ上で実行されるすべてのタスクによって読み出される。もし、いくつかのタスクがそのジョブ構成ファイルについて学習していないＣノードに接続されるとしたら、そのタスクは失敗するであろう。従来、そのような束縛は、クライアント間の外部調整を必要とする。しかしながら、一実施の形態によれば、クライアント間の調整は、調整された読み出しによって置き換えられる。
【００５０】
一実施の形態によれば、調整された読み出しは、修正操作であるのと同じ態様で実施され得る。すなわち、Ｃノードは、ファイルを読み出すための提案を提出し、調整エンジン２０８から対応する同意が受信されたときにそれを実際に読み出す。したがって、一実施の形態によれば、読み出しの同意は、名前空間の修正の同意と同じグローバルなシーケンス内で実行されることができ、それにより、調整された読み出しが決して陳腐にならないことが保証される。一実施の形態によれば、調整された読み出しは、そうすることが調整エンジン２０８上の計算負荷を不必要に増大させ、クラスタの読み出し性能を低下させ得ることから、すべての読み出しのために使用される必要はない。したがって、一実施の形態によれば、ｊｏｂ．ｘｍｌのような選択されたファイルのみが、調整された読み出しにさらされることとしてよい。したがって、一実施の形態によれば、例えば設定パラメータとして、ファイル名のパターンのセットが定義されることができる。そのようなパターンは、クラスタのＣノードによって評価され得る。そのようなファイル名のパターンが定義されるとき、Ｃノードは、読み出されるべきファイル名をファイル名のパターンと照合し、もしその結果が肯定であれば、Ｃノードは、そのファイルに対して調整された読み出しを実行する。
【００５１】
もし、特定のＣノード上において、あるクライアントによってあるオブジェクトが一旦アクセスされたとすると、そのオブジェクトは、続くクライアントのために調整された読み出しを通じてアクセスされる必要はない。一実施の形態によれば、ファイルは、特定のＲＰＣ呼び出しを通じてアクセスされるものとして識別され得る。この方法では、もしそのような呼び出しを実行しているＣノードが、そのファイルがそう識別されていないと理解したら、そのＣノードは、調整エンジン２０８に対して提案を提出し、調整された読み出しを実行するために対応する同意が受信されるのを待機するかもしれない。この読み出しの同意は、そのようにアクセスされたものとしてそれらのファイルのレプリカを識別することのできるすべてのＣノードに到着する。識別されたファイルにアクセスすることについてのすべての後続のクライアントの呼び出しは、一実施の形態によれば、調整して読み出される必要はない。それ故、クラスタ内に３つのＣノードを有する場合の最悪のケースでは、ファイルごとに３つ以下の調整された読み出しがあり得、それによって、高い読み出し性能が維持される。
【００５２】
Ｃノードもまた、故障したり、メンテナンスのためにダウンさせられたりする。もし故障したＣノードがブロック複製器任務を授けられた（すなわち、ブロック複製器として選ばれた）唯一のＣノードであるとすると、クラスタは、データブロックを複製又は削除する能力なしで残され得る。一実施の形態によれば、それゆえ、４１０に示すようにブロック複製器機能を有するＣノードは、４１６に示すように、調整エンジン２０８に対して周期的なブロック複製器鼓動（ＢＲ  ＨＢ）を送るように構成され得る。調整エンジン２０８がブロック複製器任務４１０を含むように選択されたＣノードから周期的なＢＲ  ＨＢ４１６を受信する限り、そのＣノードは、そのようなブロック複製器任務を実行し続けることができる。しかしながら、ブロック複製器４１０として選択されたＣノードから１以上のＢＲ  ＨＢをタイムリーに受信することに調整エンジン２０８が失敗すると、ブロック複製器任務は、クラスタ内の複数のＣノードのうちの他の１つに割り当てられるであろう。すると、そのように選択されたＣノードはその後、調整エンジン２０８に対して周期的なＢＲ  ＨＢ（データノードによって発行される鼓動ＨＢとは区別されるもの）を発行することができ、調整エンジン２０８が１以上のＢＲ  ＨＢを受信することに失敗し、それに応じてＣノード選択プロセスが繰り返されるまで、その役割であり続けることができる。
【００５３】
一実施の形態によれば、クラスタ内のブロック複製器４１０がただ１つであることを保証するため、ブロック複製器４１０を含むＣノードは、調整エンジン２０８に対してブロック複製器提案を周期的に提出するように構成され得る。すると、調整エンジン２０８は、ブロック複製器提案の受領に応じて、そのＣノードをブロック複製器任務を実行するために選択又は選抜されたものとして確認することができ、そのことは、クラスタ内のすべてのＣノードに対するそのブロック複製器ミッションを確認する。もし、ＢＲ  ＨＢが設定可能な期間内にＣノードによって聞かれなければ、他のＣノードは、調整エンジン２０８によって、新たなブロック複製器Ｃノードを選抜するプロセスを始めることができる。
【００５４】
実際に、一実施の形態によれば、ブロック複製器提案は、ブロック複製器任務を有するＣノードが、ブロック複製器としてのそのミッションを、周期的なＢＲ  ＨＢを介して他のＣノードに確認させるための方法であり、ＢＲ  ＨＢが満了するときに新たなブロック複製器の選抜を実施するための方法である。一実施の形態によれば、ブロック複製器提案は、以下を含み得る。
・ｂｒＩＤ・・・ブロック複製器であると思われるＣノードのｉｄ
・ｂｒＡｇｅ・・・提案するＣノードのＧＳＮ
【００５５】
各Ｃノードは、自身が受信した最新のブロック複製器同意と、その同意が受信された時刻とを格納する＜ｌａｓｔＢＲＡ，ｌａｓｔＲｅｃｉｅｖｅｄ＞。
【００５６】
例えば、３つのＣノードｃｎ１，ｃｎ２，ｃｎ３があり、ｃｎ１が現在のブロック複製器Ｃノードであると考える。Ｃノードｃｎ１は、周期的に、ＢＲ  ＨＢとしてブロック複製器提案を提案する。この提案は、自身のノードｉｄであるｃｎ１と、提案の時点でｃｎ１によって観測された最新のＧＳＮに等しいブロック複製器の新たな年齢とからなる。調整エンジン２０８は、ブロック複製器提案を受信し、対応する同意を生成して、その同意をすべてのＣノードｃｎ１，ｃｎ２，ｃｎ３に配送する。現在のブロック複製器であるノードｃｎ１は、その同意を学習し、ブロック複製作業を開始する。Ｃノードｃｎ２及びｃｎ３は、現在のブロック複製器ではなく、＜ｌａｓｔＢＲＡ，ｌａｓｔＲｅｃｉｅｖｅｄ＞をただ記憶し、通常の（複製でない）動作を継続する。ｌａｓｔＲｅｃｉｅｖｅｄが設定された閾値を超えたとき、一実施の形態によれば、ｃｎ２及び／又はｃｎ３は、候補として自身を提案することによって、新たなブロック複製器の選抜を開始することができる。
【００５７】
一実施の形態によれば、一旦Ｃノードがブロック複製器鼓動ＢＲ  ＨＢが満了したことを検出すると、選抜プロセスは任意のＣノードによって開始され得る。開始するＣノードは、一実施の形態によれば、新たなブロック複製器として自身を提案することによって、選抜プロセスを開始することができる。その提案は、ノードＩｄと、その開始するＣノードがその時点で見た最新のＧＳＮとを含み得る。その提案は調整エンジン２０８に対して提出され、対応する同意が他のＣノードに到着すると、それらは、それに応じてブロック複製器任務に対するそれらのミッションを更新する。これが、選抜プロセスを開始したＣノードが新たなブロック複製器になる方法である。一実施の形態によれば、いくつかのＣノードが選抜を同時に開始するケースでは、最も高いＧＳＮで同意を提案したＣノードがブロック複製器となる。したがって、ブロック複製器任務を有するＣノードは、選抜プロセス中に何度か変更になり得る。しかし、最終的には、ただ１つのブロック複製器ｃｍのアクリル板ノードが存在し、すべてのＣノードは、そのＣノードがブロック複製器任務を持つことに同意するであろう。一実施の形態によれば、故障したＣノードは、もしそれが障害の後にオンラインに戻り、自身がブロック複製器であると未だに思い込んでいるとしても、決してブロックの複製又は削除の決定をしないように保証される。これは、ブロックを複製又は削除することの決定は、ＢＲ  ＨＢを処理する結果としての看做されるからである。すなわち、サービス状態に戻った後、Ｃノードは、複製の設定をするために次のブロック複製器鼓動ＢＲ  ＨＢを待機する。しかし、その鼓動同意は新たなブロック複製器の割り当てについての情報を含んでおり、新たにアクティブとなったＣノードは、その受領に応じて、それがもはやブロック複製器任務を有しないこと知るであろう。
【００５８】
任意のＣノードがブロックを生成することができ、又は、ブロックの生成を可能にされていることは、複数のデータノードに格納されているデータブロックのそれぞれが、全クラスタにわたってユニークに識別可能であることを必要とする。長いデータのブロック識別子（ＩＤ）をランダムに生成すること、及び、その後そうして生成されたデータブロックＩＤが真にユニークか否かをチェックすることは、ＨＤＦＳにおけるブロックＩＤ生成の現在の方法である。このアプローチは、新たなブロックＩＤが、調整エンジン２０８に対して提出されるブロックを生成することについての提案の前に生成されなければならず、しかし、そのＩＤが生成時点ではフリーであったとしても、対応する同意がＣノードに到着するときまでにそのＩＤが他のブロックに既に割り当てられていることがあり得ることから、複製されたＣノードにとって問題を含む。同意事典でのそのような衝突の調整は、可能ではあるけれども、処理に不必要な複雑さ、トラフィック、及び遅延を付加し、成功裏に行われたデータブロックの生成の結果としてのクライアントに対する応答を遅延させる。代わりに、一実施の形態によれば、図６に示すように、最小のブロックＩＤ番号（ＭＩＮＬＯＮＧ）から最大のブロックＩＤ番号（ＭＡＸＬＯＮＧ）までの範囲にわたる大きな範囲が定義され得る。この大きな範囲は、各データブロックＩＤが全クラスタにわたって、かつ、一実施の形態によればそれらの予想される寿命を過ぎてもユニークであることを確実にするために必要な程度に大きいものであり得る。例えば、ＭＩＮＬＯＮＧからＭＡＸＬＯＮＧまでの範囲は、例えば、１０２４ビット以上を含む数であり得る。その後は、ＣノードがユニークなデータブロックＩＤ番号を生成することを確実にするために、ＭＩＮＬＯＮＧからＭＡＸＬＯＮＧまでの範囲は、図６に６０２，６０４，及び６０６で示すように、論理的に３つのＣノードブロックＩＤの範囲に分割され得る。例えば、データブロックＩＤ範囲６０２は、ＭＩＮＬＯＮＧからＭＩＮＬＯＮＧ＋Ｘビットまでの範囲にわたり、ブロックＩＤ範囲６０４は、ＭＩＮＬＯＮＧ＋ＸからＭＩＮＬＯＮＧ＋２Ｘまでの範囲にわたり、ブロックＩＤ範囲６０６は、ＭＩＮＬＯＮＧ＋２ＸからＭＡＸＬＯＮＧまでの範囲にわたる。
＜連続的なブロックＩＤ生成器＞
【００５９】
一実施の形態によれば、ブロックＩＤの生成は連続的である。この場合、ブロック割り当てを始めるＣノードは、提案が調整エンジンに提出される前に予めブロックＩＤを生成しておく必要はない。代わりに、一実施の形態によれば、Ｃノードは、ブロック割り当てが到着するときに、独立して、自身のブロックＩＤカウンターを次の値にインクリメントすることができる。このプロセスは、すべてのＣノードがカウンターの同じ値からスタートし、すべての同意を同じ順序で適用することから決定論的であり、そのことは、任意の所与のＧＳＮにおいて、ブロックＩＤカウンターの次の値がすべてのＣノード上で同じになることを保証する。
【００６０】
新たなブロックを割り当てるアルゴリズムａｄｄＢｌｏｃｋ（）は、一実施の形態によれば、次のようなものである。
１．ＣｈｏｏｓｅＴａｒｇｅｔｓ（）が、複製ポリシーに従い、利用可能な生存中のデータノードの中において、ブロックレプリカのための見込み位置を適切に選択する。
２．まだブロックＩＤが定義されていない新たに割り当てられたブロック（位置）と、生成スタンプとが調整エンジンに提案として提出される。同意が到着すると、各Ｃノードは、そのブロックに次のブロックＩＤ及び次の生成スタンプを割り当て、その後、名前空間に対してそれを引き渡す。
【００６１】
位置は、それでもなお、予め選ばれるべきである。色々なＣノードが同意を独立に処理するとき、同じターゲットを決定論的に選ぶことはできないからである。
【００６２】
図７は、一実施の形態による、ファイルのデータブロックを格納するように構成された複数のデータノードを含む分散ファイルシステムを実行するコンピュータに実装された方法を示すフローチャートである。ブロックＢ７１に示されるように、この方法は、少なくとも３つ（又は、いくつかのより大きな奇数）の名前ノードを、複数のデータノードに結合させるステップを含む。複数の名前ノードのそれぞれは、一実施の形態によれば、クラスタの名前空間の状態を格納するように構成され得る。その後、ブロックＢ７２に示されるように、（例えば調整エンジン２０８が）（図２において２０２，２０４，２０６で示されるような）名前ノードから、ファイル及びディレクトリを生成又は削除すること、及び、（図３において３０２，３０４，及び３０６で示されるような）複数のデータノードの中の１以上に格納されるデータブロックを追加することにより名前空間の状態を変更することについての提案を受信するステップが実行され得る。本開示において「変更する」とは、該当する場合、新たなデータブロックを追加すること、データブロックを複製すること、クライアントファイルのデータブロックを削除することを含む。Ｂ７３に示されるように、コンピュータに実装された本方法はさらに、提案の受信に応答して、名前ノードが名前空間の状態を変更しようとする順序を特定する同意の順序付けられたセットを生成することを含む。一実施の形態によれば、それゆえ、名前ノードは、その名前ノードが（例えば調整エンジン２０８から）同意の順序付けられたセットを受信するまで、名前空間の状態に対する（例えばクライアントによって要求された）変更を行うことを遅延させる。
【００６３】
一実施の形態によれば、（例えば、既存のＣノードが故障したか、又は、さもなければシャットダウンされたケースのように）新たなＣノードがオンラインになったとき、その新たなＣノードは、上述したようにセーフモードで起動されることができる。セーフモードにあるその新たなＣノードはその後、データノードから登録と初めのデータブロックの報告とを受信し、その新たなＣノードが結合される複数のデータノードのそれぞれに格納されているデータブロックを識別する。一実施の形態によれば、Ｃノードがセーフモードにあるとき、それは名前空果の状態の修正についてのクライアントからの要求を受け付けない。すなわち、提案を提出する前に、その新たなＣノードは、自身がセーフモードにあるか否かをチェックし、もしその新たなＣノードが現在セーフモードで動作中であると決定した場合、セーフモード例外を投げる。十分な数のブロック報告が受信されるとき、一実施の形態によれば、その新たなＣノードは、セーフモードを離れ、クライアントからのデータ修正要求の受け付けを開始する。一実施の形態によれば、複数のＣノードは起動の際に自動的にセーフモードに入り、一旦それらが十分な数のブロックレプリカの報告を受信すると、自動的かつ非同期的にセーフモードを離れる。自動的なセーフモードからの離脱は、一実施の形態によれば、調整エンジン２０８を通じて調整されるものでない。なぜなら、（図２のＣノード２０２，２０４，及び２０６のような）複数のＣノードは、ブロック報告を異なるレートで処理し、それゆえ、異なる時刻にそれらがセーフモードから離脱する閾値に達し得るからである。対照的に、クラスタの管理者がセーフモードに入れとのコマンドを発行すると、すべてのＣノードが従う。この理由により、管理者が発行したセーフモードコマンドは、一実施の形態によれば、調整エンジン２０８を通じて調整される。
【００６４】
上述したように、Ｃノードは故障したり、メンテナンスのために意図的にダウンさせられたりする。一実施の形態によれば、残りの複製されたＣノードは、それらが調整エンジン２０８に対して、同意を生成するために十分なクォーラムを形成する限り、動作を継続するであろう。もしクォーラムが失われると、一実施の形態によれば、クラスタはフリーズし、クォーラムがリストアされるまで、名前空間に対する変更の要求を処理することを停止するであろう。
【００６５】
先に故障したＣノード、又は、故意にオフラインとされたＣノードがオンラインに戻るとき、それは自動的にその状態を他のＣノードに追いつかせる。一実施の形態によれば、調整エンジン２０８は、オンラインに戻ったＣノードに対して、オフラインであった間にそれが取り損ねたすべての同意を供給することができる。この期間の間、オンラインに戻ったＣノードは、そのＲＰＣサーバを介しさせない。したがって、クライアント及びデータノードは、（ＲＰＣは、それらが通信し得るモードであるため）それに接続できず、そのことは、戻ったＣノードが、要求するクライアントに対して潜在的に陳腐なデータを供給してしまうことを回避する。このプロセスは、データノードがオンラインに戻ったＣノードに接続する前に起こる。データノードの登録及び初期のブロック報告は、その報告がＣノードがまだ学習しておらず、もし報告されたとしたら捨てられてしまうブロックを含むことから、遅延させられなければならない。
【００６６】
もしＣノードが長期間にわたってオフラインであり、著しい数（設定可能な閾値であり得る）の同意を取り損ねていたとしたら、Ｃノードにとって、それがオフラインである間に取り損ねた同意の受信を待機し、取り損ねた同意のすべてのヒストリーを再生することは、実際的でなく、非現実的であり得る。このケースかつ一実施の形態によれば、ＣノードにアクティブなＣノードの１つからチェックポイントをダウンロードさせ、それを初期の名前空間としてロードさせ、そのチェックポイントから始まる同意を調整エンジン２０８から受信させ、そのチェックポイントが生成されたときからその提供された同意のヒストリーを再生させることがより効率的である。そうするために、オンラインに戻ったＣノードは、チェックポイントを回収するためのソースとしてアクティブなノードのうちの１つ（「ヘルパー」と呼ばれる）を選び、その選ばれたヘルパーＣノードに対してＲＰＣ呼び出し（例えばｓｔａｒｔＣｈｅｃｋｐｏｉｎｔ（））を送ることができる。ヘルパーＣノードはその後、調整エンジン２０８に対してスタートチェックポイント提案を発行し、他のすべてのＣノードがそれらのローカルなチェックポイントを同じＧＳＮに同期することを確実にする。スタートチェックポイント同意が到着するとき、ヘルパーＣノードは、その同意のＧＳＮを、特定のＧＳＮ（例えばｃｈｅｃｋｐｏｉｎｔＧＳＮ）に至るまでの現行である特別に識別されたチェックポイントとして記憶するであろう。このｃｈｅｃｋｐｏｉｎｔＧＳＮはその後、現れてくるＣノードがそのチェックポイントを一旦消費した後、その後を追って学習プロセスを開始する同意を決定する。
【００６７】
オンラインに戻ったＣノードによるチェックポイントの消費は、ＨＤＦＳの標準にあるように、イメージ及びジャーナルファイルをアップロードすることによって実行され得る。追いついた後には、Ｃノードはデータノードからブロック報告の受信を開始することができる。一旦セーフモードがオフになると、新たにオンラインに戻ったＣノードは、完全にクラスタに参加し、その標準の任務を回復させる。
【００６８】
一実施の形態によれば、新たなＣノードの起動又は既存のＣノードの再起動は、以下の主たる段階を含むことができる。
１．オンラインに戻ったＣノードが起動し、プロポーザとしてクラスタに参加する。ただし、段階３まで、ラーナー能力はミュートされた状態となる。
ａ．他のノードと関連するグローバルなヒストリーの中での自身の状態を検査する。
２．もしその状態が実質的に他のノードから遅れていたら、これは設定可能な閾値により決定されることであるが、それは、アクティブなヘルパーノードのうちの選択された１つからより最近のチェックポイントをダウンロードするであろう。選択されたヘルパーノードは、チェックポイントの生成の時点におけるヒストリーの状態に対応するｃｈｅｃｋｐｏｉｎｔＧＳＮを提供する。
３．そのチェックポイントがダウンロードされるとき、（必要であれば）オンラインに戻ったＣノードは、同意リカバリ提案（ＡＲＰ）と呼ばれるその最初の提案を調整エンジン２０８に対して提出し、ラーナーの役割を引き受ける。
ａ．オンラインに戻ったＣノードは、オフラインとなったときにそれが取り損ねた同意の学習を、ｃｈｅｃｋｐｏｉｎｔＧＳＮ＋１から開始することができる。
４．オンラインに戻ったＣノードが自身の最初のＡＲＰ同意に達するとき、追いつきプロセスは完了したと看做される。新たにオンラインに戻ったＣノードは今や、アクセプタの役割を引き受けることができ、完全に機能するクラスタの参加者となり、調整エンジン２０８からさらなる同意を受信し、調整エンジン２０８に対して提案を提出する。
５．そうするために、新たにオンラインに戻ったＣノードは、そのＲＰＣサーバを初期化し、データノードに対して自身を登録及びブロック報告のために利用可能とする。報告を処理し、セーフモードを離れた後、Ｃノードは、クラスタの他のＣノードと対等の立場でクライアントの要求の受け付けを開始できる。
【００６９】
上述したように、一実施の形態によれば、各Ｃノードは名前空間のイメージを格納し、そのＣノードに結合しているローカルかつ永続的（不揮発性）な記憶装置内においてそれらを更新する。ローカル記憶装置（もしあれば）は、Ｃノード間で共有されるようには構成されないことに注意が必要である。一実施の形態によれば、各Ｃノードは、そのローカルな永続的記憶装置内に、最新の名前空間のイメージのチェックポイントを含むそれ自身のローカルなイメージファイルと、その最新のチェックポイント以降に名前空間に対して適用されたトランザクションのジャーナルを構成するファイルを編集するローカルな編集ファイルとを保持することができる。一実施の形態によれば、クラスタをシャットダウンすることは、名前空間の進化の異なる瞬間においてＣノードをダウンさせる。すなわち、いくつかのＣノードは、調整エンジン２０８から受信された同意によって特定されるすべてのトランザクションを適用済みであるかもしれないが、いくつかの遅れているＣノードは、まだ、そのようなトランザクションのすべては適用していないかもしれない。したがって、シャットダウンの後、色々なＣノードの編集ファイルは等しいものとはならないかもしれない。それゆえ、クラスタが再起動するとき、遅れているＣノードは、現在の状態よりも古い状態で起動するかもしれない。しかしながら、調整エンジン２０８は、遅れているＣノードを、グローバルなシーケンスからそれが取りこぼしたイベントを供給することによって、強制的に現在の状態とするように構成され得る。
【００７０】
これは、いくつかのＣノードが調整エンジン２０８から受信される同意の処理を通じて名前空間の状態を更新するにあたり他より遅れているときの名目上のクラスタ操作と異なるものではないことに注意が必要である。そのような遅れているＣノードは、それでもなおクライアントから修正要求を受け入れ、調整エンジン２０８に対して提案を作成するかもしれない。結果としての提案は順序付けられ、グローバルなシーケンスの中の、そのＣノードが未だ処理しておらず、当然そうあるべき順番で名前空間の状態を更新するために適用されるであろうイベントの後ろに配置される。この方法では、遅れているＣノードは、新しい要求が処理される前に、「周知された状態」（すなわち、最も現在のＧＳＮまで）とされ、それによって、クラスタの複数のＣノードにわたる名前空間の状態の一貫性が維持される。一実施の形態によれば、起動の間における複数のＣノードの持続的な状態の不一致は、「綺麗な」シャットダウン手続きを実行することによって回避され得る。
【００７１】
一実施の形態によれば、綺麗なシャットダウン手続きは、クラスタがシャットダウンされる前にすべてのＣノードを強制的に共通の状態とするように提供される。綺麗なシャットダウンを実行することの結果として、複数のＣノードのそれぞれに結合された永続的なローカルメモリに格納される名前空間のローカルなイメージのすべてが同一となるであろう。そして、それに対する更新は、トランザクションの空のシーケンスによって表され得る。一実施の形態によれば、綺麗にシャットダウンし、名前空間のすべてのローカルなイメージを強制的に同一にするために、各Ｃノードは、調整エンジン２０８によって送られた残りの同意が今まで通りに処理される一方で名前空間を修正するためのクライアント要求を処理することを停止するセーフモードの動作に入るよう命令され得る。その後、名前空間を保存する動作が実行されることができ、それによって、名前空間のローカルなチェックポイントを生成し、ジャーナルを空にする。Ｃノードのプロセスをキルする前に、すべてのＣノードが（今や複数のＣノードにわたって同一である）名前空間の保存を完了し、その名前空間のそれぞれのローカルなチェックポイントを生成したことが保証され、それによって、すべてのＣノードが同じ名前空間を有して再起動させられる。その後、Ｃノードのプロセスがキルされ得る。綺麗なシャットダウンの後には、任意の後続の起動プロセスが、Ｃノードが綺麗にシャットダウンされなかったケースに比べて速く進められるであろう。複数のＣノードのいずれもが、（それらのすべてがシャットダウンに先立って同一状態に置かれたために）調整エンジン２０８からの編集及び取り損ねた更新を適用する必要がないからである。
ＩＩ  ワイド・エリア・ネットワーク（ＷＡＮ）上の分散ファイルシステム
【００７２】
図８は、一実施の形態による、ＷＡＮ環境内に特有の効用を見出す分散ファイルシステムを示す図である。図８はまた、複製状態マシンモデルに基づく、分散された名前ノードベースのファイルシステム（例えば、ＨＤＦＳのようなもの）のためにＷＡＮ上で利用可能な複製方法の側面を説明している。一実施の形態によれば、名前ノードは、地理的に異なる場所に分散されたデータセンターに位置している。そのようなデータセンターは、例えば、異なる大陸に配置され得る。以下では、そのような名前ノードは、名前ノードがＬＡＮを介して互いに結合されるケースにおけるコンセンサス・ノード（又はＣノード）と区別するため、ジオノードと呼ばれる。
【００７３】
一実施の形態によれば、ジオノードは、上で詳細に説明したＣノードの特別なケースであると看做され得る。実際、ジオノードは、単一のデータセンター内でＣノードが動作するケースであり得るような、ＬＡＮを通じて動作を実行するように構成されたＣノードに関して本書で説明した特徴、コンセプト、方法、及びアルゴリズムのいくつか又はすべてを取り入れることができる。以下で説明するのは、例えばインターネット及び／又はプライベート又は専有のＷＡＮを含むＷＡＮ上におけるＨＤＦＳクラスタにわたる分散ファイルシステムに対して利用可能な実施の形態である。
＜アーキテクチャの概要＞
【００７４】
図８は、一実施の形態による、ＷＡＮに広がる分散ファイルシステムの構成要素を示すブロック図である。その中に示されるように、一実施の形態による分散ファイルシステム８０２を実行している（例えば単一の）クラスタは、２つ以上のデータセンターを含み得る。すなわち、データセンターＡ（ＤＣＡ）８０４と、データセンターＢ（ＤＣＢ）８０６である。ＤＣＡ８０４及びＤＣＢ８０６は、互いに地理的に遠隔であり得る。例えば、ＤＣＡ８０４及びＤＣＢ８０６は、同一の国の異なる部分に位置してもよいし、異なる大陸、異なるタイムゾーンに分散されてもよいし、完全に独立した電力系統から電力を得ることとしてもよい。ＤＣＡ８０４及びＤＣＢ８０６は、例えばインターネット及び／又は他のプライベート及び／又は専有のネットワークを含み得るＷＡＮ８０８を介して互いにゆるく結合されていてもよい。ＤＣＡ８０４及びＤＣＢ８０６はまた、他の専用の高速接続を介して、結合されてもよい。図８には２つのデータセンター８０４，８０６のみが示されているけれども、実施の形態はより多くの数のデータセンターを含み得ること、及び、分散ファイルシステム８０２がすべてのそのようなデータセンターにわたって延在することが理解される。
【００７５】
示されるように、ＤＣＡ８０４は、複数のアクティブ（その反対としては、例えばスタンバイ又はフェイルオーバー）な名前ノードを含み得る。現在の文脈では、この名前ノードはジオノードとして表示され、図面では「ＧＮ」として参照される。この態様では、ＤＣＡ８０４は、参照番号８１０，８１２，及び８１４によって示されるジオノードを含み、ＤＣＢ８０６は、参照番号８１６，８１８，及び８２０によって示されるジオノードを含む。ジオノード８１０，８１２，８１４，８１６，８１８，及び８２０は、分散ファイルシステムの名前空間の状態を格納し、かつ、複数のジオノード及び複数のデータセンターにわたって首尾一貫した態様で、単一の名前空間を維持するように構成され得る。ジオノード間の調整と、複数のジオノードにわたる単一の名前空間の維持との側面は、分散調整エンジン（ＣＥ）プロセス８２２によって提供され得る。図８では、ＣＥプロセス８２２は、ＤＣＡ８０４、ＤＣＢ８０６、及びＷＡＮ８０８に広がる分離した論理的な実体であるような態様で示されている。一実施の形態によれば、しかしながら、上述した及び以下で述べるＣＥ８２２の機能性は、ジオノード８１０，８１２，８１４，８１６，８１８，及び８２０のそれぞれによって解放され得る。すなわち、ジオノード８１０，８１２，８１４，８１６，８１８，及び８２０のそれぞれは、それぞれの他の機能の中で、ＣＥ８２２の任務を実行するように構成され得る。
【００７６】
ＤＣＡ８０２は、図８では「ＤＮ」として参照される複数のデータノード８２４，８２６，８２８，８３０を有し得る。同様に、ＤＣＢ８０４は、図８では「ＤＮ」として参照される複数のデータノード８３２，８３４，８３６，８３８を有し得る。示されるように、データノード８２４，８２６，８２８，８３０のそれぞれは、ジオノード８１０，８１２，及び８１４のそれぞれと結合し、通信するように構成され得る。また、示されるように、データノード８３２，８３４，８３６，８３８のそれぞれは、ＤＣＢ８０６のジオノード８１０，８１２，及び８１４のそれぞれと結合し、通信するように構成され得る。一実施の形態によれば、ジオノードはデータノードと直接的には通信しない。実際、一実施の形態によれば、データノードは、ジオノードが受信した要求に対するデータノードの応答に対するコマンドを発行するとすぐに、ジオノードに対して要求を送信するように構成され得る。したがって、ジオノードはデータノードを制御するように言われ得るけれども、データノードは、一実施の形態によれば、そこからコマンドを受信するためにジオノードに対して要求を送らなければならない。ＤＣＡ８０４には、４つのデータノード８２４，８２６，８２８，８３０が示されている。同様に、ＤＣＢ８０６には、４つのデータノード８３２，８３４，８３６，８３８が示されている。しかしながら、データセンター８０４及び８０６は、それぞれが図８に示されるより多くの（例えば数千の）データノードを含み得ることが理解される。
【００７７】
３つのジオノード８１０，８１２，８１４がＤＣＡ８０２内に提供されるように示されるけれども、ＤＣＡ８０２内には、より多くの数のジオノードが提供され得る。同様に、３つのジオノード８１６，８１８，８２０がＤＣＢ８０６内に提供されるように示されるけれども、ＤＣＡ８０６内には、より多くの数のジオノードが提供され得る。一実施の形態によれば、データセンター内のジオノードの数は、奇数であるように選択され得る。
【００７８】
一実施の形態によれば、図８は、地理的に異なる位置に分離して配置されたデータセンターに広がる単一の分散ファイルシステムを実行するクラスタを示している。分散ファイルシステムは、例えば、ＨＤＦＳの側面を取り込むものである。一実施の形態によれば、同じデータセンター内のジオノード間における名前空間の調整は、ＬＡＮを用いるケースに関して上述した構造、方法、手続きを使用して実行され得る。例えば、複数のデータノードのそれぞれは、それら自身のデータセンター内のジオノードとのみ（データノード−名前ノード間のＲＰＣプロトコルを通じて）通信するように構成され得る。反対に、あるデータセンター内のジオノードは、それら自身のデータセンター内のデータノードのみを制御するように構成され得る。すなわち、一実施の形態によれば、データセンター８０４のデータノードはそれら自身のデータセンター８０４のジオノードと通信するのみであり、データセンター８０６のデータノードはそれら自身のデータセンター８０６のジオノードと通信するのみであり得る。両データセンター８０２，８０６のジオノードは、名前空間の状態を一貫した状態に保つように、調整エンジンプロセス８２２を通じて互いに調整を行う。以下で記述するようにかつ一実施の形態によれば、あるデータセンターのデータノードは、他の１つのデータセンター又は複数のデータセンターのデータノードと通信し得る。
【００７９】
一実施の形態によれば、ＣＥプロセス８２２は、名前空間の状態に対する同じ決定論的な更新が、すべてのジオノード上で同じ決定論的な順序で適用されることを保証するように構成され得る。この順序は、グローバルシーケンス番号（ＧＳＮ）によって定義される。したがって、一実施の形態によるＣＥプロセス８２２の重要な役割は、すべてのジオノードからの名前空間の状態に対する修正又はさもなければ更新についての提案を処理し、それらをグローバルに順序付けられた同意のシーケンスに変形することにある。ジオノードはその後、その順序付けられたシーケンスからの同意を、それらが格納している状態に対する更新として適用し得る。一実施の形態によれば、ＧＳＮは、ユニークかつ単調に増加する数として構成され得る。しかしながら、ＧＳＮは、当業者が理解できるような別の方法でも構成され得る。ＧＳＮはその後、名前空間の状態を更新し、かつ、複数のジオノードにわたって名前空間の状態を一貫した状態に保つこと（又は、順序付けられた同意のシーケンスの連続的な適用を通じて、複数のジオノードのそれぞれに格納される名前空間の状態を時間を超えて首尾一貫した状態とすること）における色々なジオノードの進行を比較するように構成される。例えば、もしジオノード８１０が、ジオノード８１２によってちょうど処理されたＧＳＮ２よりも小さいＧＳＮ１とナンバリングされた同意をちょうど処理したところであれば、ジオノード８１０は、ジオノード８１２が有するものよりも早い時期の名前空間の状態を有する。ジオノード８１０に格納される名前空間の状態は、ジオノード８１０がＧＳＮ２を処理するや否や、ジオノード８１２がその合間により高い番号の同意を処理していないことを条件として、ジオノード８１２によって格納されるものと一致するであろう。この方法では、ＣＥプロセス８２２によって生成された順序付けられた同意のセットの連続的な実行を通じて、各データセンターの各ジオノードに格納されている名前空間の状態が首尾一貫した状態とされ、その状態で維持される。
【００８０】
一実施の形態によれば、クライアントは、それぞれの操作の際、現在接続中のジオノードで処理された最新のＧＳＮについて学習する。その後、もしクライアントが他のジオノードに切り替えたとすると、一実施の形態によればそれは、書き込みのようなデータアクセスコマンドを含むＲＰＣを発行する前にまず、（必要であれば）新しいジオノードがクライアントの知っている最新のＧＳＮ（すなわち、クライアントが以前にアクセスしていたジオノードから受信したＧＳＮ）に追いつくまで待機するべきである。このことは、陳腐な読み出しの問題を回避するであろう。各ジオノードは同じ状態から開始しているので、この更新の順序付けられた適用は、同じＧＳＮで同意を処理した異なるノードで撮られたそれらのスナップショットが各データセンター内でも複数のデータセンターにわたっても同一であるという点で、レプリカの一貫性を暗示する。ジオノード８１０，８１２，８１４，８１６，８１８，８２０の間のすべてのメタデータは、ＣＥプロセス８２２が同意を配送する限り、即座に調整され得る。同様に、すべてのファイルシステムのデータもまた、クラスタの複数のデータセンター（図８に示される２つ）にわたって自動的に複製され得る。
【００８１】
ここでは、異なるデータセンターからのジオノード、データノード、ブロックレプリカ、クライアントなどを指すために、「外国」という用語が好ましく使用される。同じデータセンターの実体は、「自国」と称される。例えば、クライアントがＤＣＡ８０４にアクセスするとき、ＤＣＡ８０４は、ローカル又は自国のデータセンターであると看做され、一方、ＤＣＢ８０６は外国のデータセンターとして表示され得る。逆に、クライアントがＤＣＢ８０６にアクセスするならば、データセンター８０６がローカル又は自国のデータセンターであり、一方、ＤＣＡ８０４は外国のデータセンターとして表示される。
【００８２】
一実施の形態によれば、クライアントが新たなファイルを生成するとき、ＣＥプロセス８２２は、すべてのジオノード８１０，８１２，８１４，８１６，８１８，８２０がその新しいファイルについて知っており、それらがその新しいファイルのデータ（例えばデータブロック）にアクセスする前でさえも、同名の他のファイルが生成されることを防止することを確実にする。一実施の形態によれば、データブロックは、バックグランドかつ非同期の態様で、自国のデータセンター内で複製され、また、データセンター間でも複製される。この態様では、ジオノードは、新しいファイルとそのデータブロックについて、自国のクライアントのためにそのブロックの（データセンターに対して）ローカルなレプリカを提供できるようになる前に学習する。すなわち、ＤＣＡ８０４のクライアントは、ＣＥプロセス８２２に対して提出される新たな順序付けられた提案の基礎を構成する新たなファイルを作成することができる。順序付けられた同意が生成され、すべてのジオノードの状態は、自国のＤＣＡ８０４及び外国のＤＣＢ８０６の両方において更新される。その後、以下で詳述するように、データブロックはＤＣＡ８０４内の指定されたデータノードに転送され、その後、指定されたデータノードにより、完全な複製の状態に到達するまで、ジオノードが指定したＤＣＡ８０４内の他のデータノードに（あるデータノードから他のデータノードに順番に）渡される。完全な複製の状態は、例えば、データブロックのレプリカが所与のデータセンターの３つのデータノードに格納されているときに到達され得る。完全な複製の状態は、他にも、当業者が理解できるように定義され得る。以下で説明するように、完全な複製の状態に到達すると、データブロックは、非同期かつバックグランドで、１以上の遠隔のデータセンターのデータノードに対して転送される。
【００８３】
ＤＣＡ８０４のデータノード８２４，８２６，８２８，及び８３０及びＤＣＢ８０６のデータノード８３２，８３４，８３６，及び８３８は、クライアントファイルのデータブロックのレプリカを格納するように構成され得る。任意の単一のデータブロックのレプリカは、１つ（例えばＤＣＡ８０４）、２つ（例えばＤＣＡ８０４及びＤＣＢ８０６）、又は、より大きな数のデータセンターのデータノード上に格納され得る。ＷＡＮ８０８上での通信はリソースを大量に消費し、かつ、高価であり、待機時間、中断、及び帯域幅の規制量が変化しがちであるので、一実施の形態は、あるデータセンターのデータノードが他の（地理的に離れた、外国の）データセンターのジオノードと通信することのないように構成される。すなわち、上で予め示したように、データノード８２４，８２６，８２８，及び８３０はジオノード８１０，８１２，８１４とのみ通信し（例えばリクエストを発行し）、ＤＣＢ８０６のジオノード８１６，８１８，８２０とは通信しない。逆に、データノード８３２，８３４，８３６，及び８３８はそれら自身のデータセンターのジオノード８１６，８１８，及び８２０のみと通信し、（それらにとって）外国のＤＣＡ８０４のジオノード８１０，８１２，８１４とは通信しない。このことは、一実施の形態によれば、あるデータセンターのジオノードが外国のデータセンターのデータノードからブロック報告や鼓動を直接受信することはなく、外国のデータセンターのデータノードに対してコマンドを送信することもないことを暗示する。
【００８４】
しかしながら、一実施の形態によれば、あるデータセンター、例えばＤＣＡ８０４のデータノードは、ＷＡＮ８０８上で１つ以上の外国のデータセンター、例えばＤＣＢ８０６に対してデータブロックのレプリカをコピーし、それによって外国のブロック複製サービスを提供するように構成され得る。一実施の形態によれば、ＷＡＮ８０８上のネットワークトラフィックは、ＷＡＮ８０８上では任意の特定のデータブロックのただ１つのレプリカのみを送信し、さらなる複製は外国ＤＣ内でローカルに発生するように構成することにより、最小化され得る。例えば、あるデータブロックがＤＣＡ８０４内で完全に複製されるとき、そのようなデータブロックのレプリカはＷＡＮ８０８上でＤＣＢ８０６に送信され得る。ＤＣＢ８０６内でそのデータブロックを完全に複製するために要求され得る任意のさらなる複製は、その後に完全にＤＣＢ８０６内で発生する。
【００８５】
例えばＨＤＦＳマップ・リデュース・タスクのような分散ファイルシステムのクライアントは、それらがクライアントであるデータセンターのデータノードとともに計算環境を共有するように構成され得る。したがって、一実施の形態によれば、クライアントは利用可能な複数のデータセンターのうちの１つの中で実行するように構成され得る。クライアント・タスクは、それゆえ、アクセスされたデータセンターに対して自国であるジオノードと通信するために最適化され、自国のデータノードにアクセスするように構成される。しかしながら、一実施の形態によれば、クライアントはまた、他のデータセンターからのデータにアクセスするためにＷＡＮ８０８を横切って到達するように構成され得る。
【００８６】
実施の形態によれば、各ジオノードが一貫性を有するように維持され、システムが任意の１つ以上のジオノードの障害、又は、１つ以上のデータセンターの実際の障害に対して耐性を有しているという点で、好ましいジオノードというものは存在しない。逆に言うと、実施の形態によれば、システム内の各名前ノードがいつもアクティブであり、一貫した名前空間の状態を維持しているという点で、フェイルオーバー中、非アクティブ、又はスタンバイのジオノードは存在しない。さらに、ここに開示されるシステムは、複数のクラスタがそれらの間でいくつか又はすべてのデータを共有する（ミラーリングする）一方でそれぞれのデータセンターで独立して動作するマルチクラスタ・アーキテクチャとは対照的に、単一の分散ファイル（例えばＨＤＦＳ）クラスタとして現れ、行動し、操作されるように構成される。異なるデータセンターに属するＷＡＮクラスターの同一の部分は、等しい役割を有するように構成され得る。この方法では、データは、分散ファイルシステムの複数のデータセンターのうちの任意のものによって取り込まれ、又は、それを通じてアクセスされ得る。実施の形態によれば、データの生成及びアクセスのプロセスは、実質的にＬＡＮのスピードで（すなわち、多くのケースでＷＡＮのスピードより概して速く）実行するように構成され得る。例えば、もしジョブが複数のデータセンターのうちの１つで動作するならば、そのジョブは、概ねそれが他のデータセンター内には存在しないときと同じ時間内に完了すべきである。
【００８７】
実施の形態による分散ファイルシステムの構造は、それに障害又は災害に対する高度な耐性を与える。実際、任意のジオノードが故障し得、２つ以上のデータセンター上で複数のジオノードが同時に故障し得、例えばＷＡＮの分割に起因してデータセンター全体が故障し得、データノードが故障し得る（例えば、２つのデータノードの同時の障害及び／又は全ラックの障害）が、それらはすべて、クラスタの機能性及びデータに対する自由なアクセスを維持している間に発生する。
ファイルを生成し読み出すためのワークフロー
＜ファイルを生成すること＞
【００８８】
ＨＤＦＳでは慣習的に、クライアントがファイルを生成することを欲するとき、それはまず、ブロック追加(addBlock)又は機能的に類似するコマンドを伴う生成要求により名前ノードを呼び出す。生成呼び出し、特定された属性を有する新しいファイルに対応する名前空間内にエントリを生成する。ブロック追加呼び出しは、そのファイルのために新しい空のブロックを割り当て、ブロック複製ポリシーに従い、そのレプリカのために予想されるデータノードの位置を割り当てる。クライアントはその後、名前ノードにより指定された１つのデータノードから、名前ノードにより指定された次のデータノードまでの経路を形成し、それらにデータを書き込む。続いてデータノードは、新しいブロックレプリカを受信すると、それを名前ノードに報告する。
【００８９】
しかしながら、実施の形態によれば、名前空間が複数のジオノード上（ＷＡＮのケース）、又はＣノード上（ＬＡＮのケース）で複製されるとき、クライアント（図８における参照番号８４０）要求は、複数のジオノード又はＣノードのうちの１つによって送信され、受信される。ＷＡＮのケースでは、実施の形態によれば、クライアントは自国のジオノードを選択することができる（必須ではない）。クライアント要求を受信し、このインスタンスの中でプロポーザとして動作するジオノードは、クライアント要求に対応する提案を形成し、その提案をＣＥプロセス８２２に提出する。一旦この提案に対する同意が達成されると、ＣＥプロセス８２２は、すべて（すなわち、ＤＣＡ８０４及びＤＣＢ８０６のジオノードのすべて、並びに、分散ファイルクラスタ（例えばＨＤＦＳ）内の他の任意のデータセンターのジオノードのすべて）に対して、その同意を配送する。その同意はその後、ジオノードのローカルな名前空間のインスタンスに適用されることができ、したがって、すべてのジオノード上で首尾一貫して同じファイル又は同じブロックを生成する。プロポーザであるジオノードは、同意を処理した後、クライアントに対して応答する。
【００９０】
ブロックが生成されるとき、ジオノードは、ブロックのための予想される位置として自国のデータノードを選択する。例えば、クライアント８４０がファイルを生成するとき、名前空間へのエントリが生成され、提案／同意のプロセスを通じて、自国及び外国両方のすべてのジオノードの状態が更新される。この方法では、その名前を有する他のファイルは、如何なるデータセンター上でも生成され得ない。ジオノード８１０のようなジオノードはその後、そのデータブロック及びそのすべてのレプリカを格納するために、予想されるデータノードを指定する。一実施の形態によれば、クライアント８４０はその後、そのデータノードとのみ通信し、ジオノードとはもはや通信しない。クライアント８４０はその後、ジオノードによって指定された最初の予想されるデータノード（例えば８２４）にデータブロックを書き込み、自国のデータセンター内で完全な複製（ただし、「完全」な複製は定義されたものである）が達成されるまで、ある自国データノードからその経路内の次の予想される自国データノードへのレプリカの経路８２５を生成する。この経路は、ＷＡＮ８０８を通って転送されるデータブロックのレプリカが存在しないことから、ＬＡＮのスピードで占められ得る。一実装によれば、完全な複製は、データブロックのレプリカが、例えばＤＣＡ８０４のデータノード８２４，８２６，及び８２８のような３つの分離した自国データノード内に格納されるときに達成され得る。データブロックの位置をすべてのジオノード（自国及び外国の両方）に通知するため、自国のジオノードのうちの１つは、データノードがジオノードに対してレプリカの安全な受領を報告した後、ＣＥ提案／同意機能を介して外国レプリカ報告の提案を提出する。
【００９１】
一実施の形態によれば、例えばブロックが完全に複製されたときのようにジオノードがすべての自国のブロックレプリカについての情報を受信するとき、ジオノードは、外国レプリカ報告の提案をＣＥ８２２に対して生成する。この提案に対する同意が達成された後、その外国レプリカ報告は、新たなレプリカの存在及び位置をすべてのジオノード（自国及び外国の両方）に通知するために動作する。この段階では、自国及び外国の両方のジオノードが新たに生成されたファイルの存在と、そのブロックレプリカの位置を「知る」。しかしながら、ジオノードによって指定された自国のデータノードのみが実際にそのブロックレプリカを格納する。したがって、その名前空間は、ジオノードによって指定された自国のデータノードが名前空間に対する更新を生じさせたレプリカを格納する場合でさえも、更新され、複数のデータセンターにわたって首尾一貫した状態で残る。
【００９２】
その後、一実施の形態によれば、新たにレプリカを格納する複数の自国データノードのうちの１つから外国のデータノードへのレプリカの転送が、ＨＤＦＳデー転送プロトコルのための標準を通じてスケジュールされる。例えば、新たにレプリカを格納するデータノード８２８は、８３２のようなジオノードによって指定された外国の予想されるデータノードに対し、ＷＡＮ８０８を使用してブロックレプリカを転送するようスケジュールされ得る。この転送は、対象のレプリカが完全に複製された後（すなわち、（例えば）自国データノード３，４，５に複製された後）に実行され得ることに注意が必要である。クライアントの観点から見ると、ジオノードが指定した予想されるデータノードへのデータブロックの書き込みは、多くのケースで比較上ＷＡＮのスピードより速いＬＡＮのスピードで実行される。したがって、レプリカはこの段階で自国のデータセンター内に冗長性を持って格納されるが、この時点では、１以上の地理的に遠隔の（したがって災害に耐性を有する）データセンターには格納されていない。新たなレプリカを格納する複数の自国データノードのうちの１つがジオノードが指定した外国の予想されるデータノードに対してブロックレプリカを転送した後、そのブロックのコピーが外国のデータセンター上で非同期に生成される。この転送は、必然的にＷＡＮスピードで発生するが、完了及びクライアントの書き込みに対する最終的な応答を遅延させることなく、バックグランドで発生する。一実施の形態によれば、新たな受信されたレプリカはその後、（例えばＨＤＦＳ）複製プロトコルを介し、外国のデータセンターにおいてその内部複製ポリシーに従って、ローカルに複製されることができる。例えば、外国のジオノードによって指定され、８２９において８２８のような自国データノードからＷＡＮ上でブロックのコピーをちょうど受信したばかりの外国データノード８３２は、その後、そのブロックのための完全な複製がその外国データセンター内で達成されるまで、（図８の８３３で示されるような）経路のやり方で、８３４及び８３６のような外国のジオノードによって指定された他の外国データノードに対してデータブロックが複製され、データノードからＲＰＣ呼び出しを介して外国ジオノード８１６，８１８，８２０に対して報告されるようにすることができる。その外国ジオノードはその後、ＣＥ８２２を通す提案／同意プロセスを再び介し、少なくとも外国ＤＣＢ８０６内のレプリカの外国データノード内での位置について、自国ジオノードを更新する。
＜ファイルの読み出し＞
【００９３】
ＨＤＦＳのような分散ファイルシステムのクライアントがファイルを読み出す必要があるとき、それは、ゲットブロック位置（又は機能的に類似する）要求を名前ノードに対して送信する。その名前ノードは、要求されたデータブロックのレプリカを格納しているデータノードのリストを返送する。クライアントはその後、ネットワークトポロジーに関してクライアントに最も近い複数のデータノードのうちの１つからデータを読み出す。
【００９４】
一実施の形態によれば、図８に示されるＷＡＮクラスタ上で、ＤＣＡ８４０のクライアント８４０は、ＤＣＡ８０４の複数の自国ジオノードのうちの１つに対して、ゲットブロック位置（又は機能的に類似する）要求を送信する。クライアントがゲットブロック位置要求を送信した自国ジオノードは、その要求を受信し、要求内で識別されるブロックのレプリカを格納している複数の自国データノード内の位置のリストをクライアント８４０に対して返送する。そのようなリストは、一実施の形態によれば、自国のデータノードのみ、自国と外国の両方のデータノード、又は、外国のデータノードのみを含む。レプリカは、上で詳述したように、そのブロックがまだ書き込み中であるか、まだ自国内で複製されている最中であるか、又は、自国データセンター内では完全に複製されたがまだ外国データセンターに転送されていないケースでは、外国のデータノードのみに格納され得る。もし、ブロックレプリカが、そこからゲットブロック位置が要求されたデータセンターにとって自国であるデータノードに格納されているならば、クライアント８４０は、複数の自国データノードのうちの１つからブロックレプリカを読み出すことができる。さもなければ、クライアント８４０は、ＷＡＮ８０８上で外国レプリカを読み出すことができる。しかしながら、ＷＡＮ８０８上での読み出しは多くのリソースを使用する。したがって、性能の理由から、一実施の形態は、外国レプリカの読み出しを許可しないことを可能にすることができる。そのような場合、クライアント８４０は、要求したデータブロックのレプリカがその自国のデータセンター上に現れるまで待たされ、その後、今や自国のものとなったレプリカの読み出しを進めることができる。外国読み出しを許可する／許可しないというオプションは、一実施の形態によれば、設定パラメータとして利用可能とされ得る。
＜外国ブロックの管理＞
【００９５】
一実施の形態によれば、ブロックマネージャーが自国のファイルブロックの位置及び自国データノードについての情報を保持する。外国ブロックマネージャーは、外国のファイルブロックの位置及び外国データノードについての情報を保持するように用意され得る。以下の記述は、実施の形態が外国のブロックと外国のデータノードを保持する方法を詳述する。
＜外国ブロックの複製＞
【００９６】
上述したように、ファイルの新たなブロックは、ブロック追加又は機能的に類似した呼び出しを介して割り当てられ、複数のジオノードにわたって調整され得る。あるジオノードがクライアントからブロック追加要求を受信するとき、ブロック追加要求を受信するジオノードは、完全な複製のために要求される必要数（一実施の形態では、デフォルトで３つ）の自国レプリカを選択し、ＣＥプロセス８２２に対して対応するブロック追加提案を提出することができる。対応する同意がＣＥ８２２から到着するとき、ジオノードは、そのブロックに対して決定論的に、ブロックＩＤ、類似の識別子、及び生成スタンプを割り当てることができ、その後クライアントに対して、位置決めされたブロック(LocatedBlock)又は機能的に類似した通信を返送することができる。クライアントファイルの新たなブロックのための初期のターゲットは、一実施の形態によれば、クライアントがブロック追加要求を発行したデータセンターに対して自国のデータノードからのみ選択され得る。このことは、クライアントが、ＷＡＮを介する転送が完了するのを待つことなく書き込んでいるそのデータセンターから書き込み応答を受信するという点で、書き込み性能の最適化を可能にする。この方法では、クライアントは（例えば経路の更新のような）エラー処理を回避する。エラーは、より遅くより信頼性の低いＷＡＮリンク８０８に起因して、より起こりやすい。
【００９７】
したがって、一実施の形態によれば、レプリカはまず、データ経路手続きの元であるデータセンターに対して自国である複数のデータノードに格納される。転送が成功すると、クライアントは、データがファイルシステム内に格納されていることを無事に推測することができ、その後、次のブロック又は他の操作を進めることができる。他（すなわち、外国）のデータセンターは、それらのジオノードはそのファイルの存在に気づき、既に（それらにとっての）外国データセンター内において格納されるブロックレプリカの位置を知っているかもしれないが、この時点ではブロックの自国のレプリカを所有していない。
【００９８】
一実施の形態によれば、ジオノードはその後、経路内のデータノードがそれらのレプリカを報告するので待機する。報告されたレプリカの数が完全な複製（一実施の形態によれば、デフォルトで３つ）に到達すると、ジオノードは、外国レプリカ報告（ＦＲＲ：ForeignReplicaReport）提案を発行し、外国データセンターへの１つのレプリカの転送をスケジュールする。
＜外国レプリカの報告＞
【００９９】
一実施の形態によれば、外国レプリカ報告（ＦＲＲ）は、ジオノードに報告されたすべての自国内のブロックのレプリカと、レプリカが属するデータセンターの名前又は報告しているデータセンターの名前を含むように構成され得る。ＦＲＲは、一実施の形態によれば、あるデータセンター上に存在しているブロックレプリカが他のデータセンターのジオノードに報告され得る１つの可能な機構を構成する。ＦＲＲ提案／同意は、一実施の形態によれば、次の２つのケースで発行され得る。
１．自国のブロックレプリカの数がデータセンターのための完全な複製に到達するとき。
２．例えば、そのレプリカを格納しているデータノードのすべて（３つ又はしかしながら多く）が死に、又は、さもなければデータアクセス要求に対するサービスが利用不能になるときに発生し得るような、自国のブロックレプリカの数が０にまで減らされるという事態に至ったとき。
【０１００】
ジオノードは、外国レプリカ報告の同意を受信すると、まず外国レプリカがＦＲＲ内で報告されているか否かを決定する。否であれば、ＦＲＲは、自国データノード内のレプリカの記憶容量（そのジオノードが既に気づいているもの）を報告しており、ジオノードはそのＦＲＲを安全に無視する。しかしながら、もしＦＲＲの主題であるレプリカが実際に外国のものであれば、ジオノードは、データセンターに報告するための外国レプリカの現在のリストを、新たに報告されたリストによって置き換え得る。したがって、そのＦＲＲメカニズムは、ブロックの外国レプリカを追加及び／又は削除するように動作し得る。
【０１０１】
一実施の形態によれば、各データセンターは（一実施の形態では単一の）ブロック複製器を提供され得る。単一のブロック複製器は、ＬＡＮ実装においては、図４に４１０で示されている。ブロック複製器は、データセンター内の全クラスタのために、ブロックレプリカの複製及び削除に対する決定を下す。そのような決定は、過剰なレプリカが生成されないように、又は、さらに悪いことにはいくつかのブロックがすべてのレプリカを失わないように、片務的に行われるべきである。
【０１０２】
一実施の形態によれば、データセンター内において、ブロック複製器の機能を引き受けている唯一のジオノードは、ＦＲＲを発行するジオノードである。ＦＲＲの目的は、それ自身のデータセンター内におけるレプリカの位置を報告することであるので、ＦＲＲ報告は、一実施の形態によれば、自国のブロックレプリカの位置についてのみ報告するように構成され得る。
【０１０３】
性能面の理由から、ＦＲＲは、一実施の形態によれば、ブロックが自国内における完全な複製に到達したときに、ブロック複製器ジオノードによって発行され得る。１つの実装では、ＦＲＲ提案は、自国のデータノードが３つのレプリカの成功裏に記憶したことを報告したときに発行され得る。ただし、「自国内における完全な複製」の他の定義が考案され得る。一実施の形態によれば、ＦＲＲは、レプリカの数が０に減らされるまで発行されない。なぜならば、データセンターがブロックの少なくとも１つのレプリカを有している限り、そのデータセンターは自国内でレプリケーションを取り扱えるからである。しかしながら、データセンターが任意の特定のデータブロック又は複数のブロックのいかなる自国内のレプリカももはや持たないときには、そのデータセンターのブロック複製器ジオノードは、他のデータセンターがＷＡＮ８０８上で自国に対してレプリカを転送すべきであるということを示す（複数の）ブロックのためのＦＰＲを発行することができる。
【０１０４】
もし、データブロックの１つ又はいくつか（ただし、すべてではない）のレプリカがＤＣＡ８０４上で失われたとしても、他のデータセンターは、ＤＣＡ８０４上でブロックの完全複製がリストアされるまで、そのレプリカが完全複製に至らない状態となっていることについて知ることはないであろう。この時点（完全複製が達成された時点）で、ＤＣＡ８０４のブロック複製器ジオノードはＦＲＲを提出し、他のデータセンターはこれに対応して、それらの外国レプリカのリストを、ＦＲＲを発行するＤＣＡ８０４によって報告された実際の値に更新するであろう。その間、いくつかの外国読み出しが失われた（複数の）位置からの読み出しに失敗するかもしれないが、シームレスな態様で、他のレプリカに切り替わるであろう。
【０１０５】
一実施の形態によれば、所与のブロックの（所与のデータセンターにおいてブロックが完全に複製されたと看做されるために格納されるべきレプリカの数を定める）複製因子は、データセンターによって異なっていてよい。例えば、一実施の形態は、クラスターが、ＤＣＡ８０４では３つのレプリカを、ＤＣＢ８０６ではそのブロックのただ１つのレプリカのみを、それぞれ格納することを許可し、それにも関わらずそのブロックは、ＤＣＡ８０４上及びＤＣＡ８０６上で完全に複製されたと看做される。したがって、完全複製の通知は、個々のデータセンターに特有のものであり得る。これは、例えば単一の地理的に遠隔なレプリカで十分である重大でないデータにとって、有益であり得る。
＜外国レプリカの転送＞
【０１０６】
データセンター内のブロック複製器として指定されたジオノードは、一実施の形態によれば、ブロックを調査し、自国のレプリカを有しているが外国のそれを有していないそれを検出することについて、追加の責任を割り当てられ得る。この機能は、自国のレプリカを周期的にモニタリングすることに加えて外国の複製の分析も行うブロックモニターに割り当てられてもよい。
【０１０７】
自国のレプリカを有するが外国のレプリカを有しないブロックがブロック複製器として指定されたジオノードによって検出されるとき、ジオノードは、対象のレプリカを格納する自国のデータノードの１つを選択し、それに対して、他のデータセンター内のデータノードに対してそのレプリカを転送するよう指示する。ＷＡＮを介するレプリカの転送命令は、データノードと自国のジオノードとの間の鼓動通信を介して発行され得る。一旦このコマンドが受信されると、選択されたデータノードは、外国データセンター内の指定された外国データノードに対し、そのレプリカを転送する。
【０１０８】
実施の形態によれば、データノードは、ブロック複製器機能を有するものとして指定されたジオノードからのみ、データノードコマンドを受け付けるよう構成され得る。これは、各データセンターが、ブロック複製器としてデザインされたジオノードをただ１つだけ含むように構成され得ることのもう１つの理由である。
＜自国のブロック複製器＞
【０１０９】
ＬＡＮ環境では、複数のＣノードの各クラスタは、クラスタ全体のために選択的にブロックレプリカの複製と削除を行う責任を単独で割り当てられるブロック複製器として指定される唯一のＣノードを有する。Ｃノードと同様、複数のジオノードは、そのデータセンターに対して唯一である１つのブロック複製器ジオノードを選抜する。各ブロック複製器ジオノードは、ブロック複製器鼓動（ＢＲ  ＨＢ）を送信する。複数のジオノードは、外国のブロック複製器ジオノードからのＢＲ  ＨＢを無視するように構成され得、それ自体、それぞれのローカルなデータセンター内で内部的にのみ使用されるように構成される。ＬＡＮのブロック複製器Ｃノードに関して上述したように、もし現在の自国のブロック複製器ジオノードからのＢＲ  ＨＢがそのために許される期間内に発行されることに失敗した場合、データセンター内の他の複数のジオノードは、新たなブロック複製器Ｃノードを選ぶために使用される方法と同様の方法で、新たなブロック複製器ジオノードを選ぶことができる。
【０１１０】
一実施の形態によれば、異なるデータセンターのためのＢＲ  ＨＢは互いに独立しているので、それらの調整は、外国のＢＲ  ＨＢが無視される単一の状態マシン、又は、複数の状態マシン、すなわちデータセンターごとに１つの独立した状態マシンを用いて取り扱われ得る。後者のケースでは、複数の状態マシンは切り離されたメンバーシップによって特徴付けられ、それぞれが単一のデータセンター内の複数のジオノードを含む。
【０１１１】
ジオノードは、名前ノード及びＣノードに類似する態様で、クラスタのデータノードのリストを、それぞれの状態（生死又は退役）とともに、さらに、例えば進行中のデータ転送の数及びローカルディスクの利用量などのようなそれらのリソース利用率とともに保持するように構成され得る。
＜データノード登録を調整すること＞
【０１１２】
図８に示すような実施の形態によるＷＡＮクラスタにおいては、データノードは、一実施の形態によれば、自国のジオノードとのみ通信する（例えば、要求を発行する）ように構成され得る。特に、分散ファイルシステム上で登録している複数の新たなデータノードは、外国データセンター上のジオノードへ直接、それらの登録情報を送信するようには構成されない。一実施の形態によれば、調整されたデータノードの登録プロセスが提供され得る。それによれば、データノードが自国のジオノードに登録するとき、その自国のジオノードは、調整エンジン２０８に対してデータノード登録提案を提出し、対応する同意が到着した後に登録を処理する。
【０１１３】
ジオノードがこの対応するデータノード登録同意を受信するとき、そのことは、名前ノード又はＣノードによって実行される手続きと同様であり得る登録手続きを起動し得る。もし、登録するデータノードが自国のものであれば、さらなるアクションは必要ない。新たに登録する外国のデータノードを考慮するデータノード登録同意のために、ジオノードは追加的に、新たに登録する外国データノードの状態を退役に設定し、それを外国のものとしてマークする。ジオノードは、外国のデータノードとは直接的には通信しないからである。実際、一実施の形態によれば、外国のデータノードはいつも、ジオノードによって「退役」として見られる。ジオノードは、外国データノードと通信できず、外国データノードを制御できず、さもなければ外国データノードから直接情報を集めることができないからである。特に、実施の形態によれば、外国データノードは、ブロックのための経路のターゲットとして使用されない。この制約は、クライアントのデータアクセス操作のためにＬＡＮ状のスピードを維持する。ローカルなデータセンターのデータノード内に完全な数（例えば３）のレプリカが確認されるとすぐに、ブロックが完全に複製されたと看做されるからである。同様に、外国データノードは、ローカルなジオノードが、鼓動の満了間隔の間にそれらの鼓動を受信することに失敗したことに基づいて死んだと宣言されることはない。なぜならば、一実施の形態によれば、複数のデータノードはそれらのローカルなジオノードとのみ通信し、外国のジオノードに対しては鼓動を発行しないからである。この振る舞いは、例えばＨＤＦＳクラスタ上の退役したデータノードのそれと矛盾しない。
＜外国データノードの記述子＞
【０１１４】
登録されたデータノードは、外国又は自国のいずれであっても、データノード記述子によってジオノード内に表現され得る。外国データノードの記述子は、（通常の、ローカルの）データノード記述子の、以下に示す追加のフィールドを含む拡張である。
・自国のノードと区別するための外国データノードマーカー
・それ自身の（それにとって自国の）データセンター内で知られているものとしてのそのデータノードの状態は、生、死、又は退役として特徴付けられ得る。データノードの状態は、ジオノードにとって、（経路方式の複製のためではなく）外国ブロック複製のためにターゲットとなる外国データノードを選択するときを知るために重要である。死んだ、退役した、又は退役しつつあるノードは、複製のターゲットとして使用されるべきでないからである。これは、自国のジオノードに対して新たに登録する外国データノードの「退役」状態とは異なることに注意が必要である。
・外国データノードには、無限の鼓動満了間隔が設定される。外国のデータノードは、それら自身のデータセンターの外にあるジオノードと直接通信する（例えば、それに対して要求を発行する）ことを期待されず、また、そのように構成されていないからである。
【０１１５】
実施の形態によれば、ジオノードは、外国データノードが生きているか死んでいるか知ることができない。自国のジオノードのみが、データノードがその鼓動を送ることを停止したときに、検出可能であるからである。ＷＡＮクラスター上では、登録、鼓動満了、退役のイベントは、外国及び自国の両方を含むすべてのジオノードが、すべてのデータノードの最新の状態を追えることができるように調整される。
＜外国ブロックの報告＞
【０１１６】
ブロックの報告は、所有しているブロックレプリカの名前ノードを通知するためにデータノードによって送信される。例えば、クラスタが最初に起動するとき、ローカルのジオノードは、すべてのレプリカについてその格納場所を知らない。ローカルなジオノードに対し、クラスタ内の各レプリカのローカルなデータノード内における位置を通知するのが、ブロック報告である。ＬＡＮ環境では、データノードは、すべてのＣノードに対してそれらのブロックを報告する。
【０１１７】
しかしながら、ＷＡＮ環境では、外国データノードが他のデータセンターのジオノードに対してＷＡＮ８０８上でブロック報告の全体を送ることは、受け入れ難いほどに、リソースを激しく使用し、高価であり得る。それにも関わらず、ジオノードは、外国データノード上に格納されているレプリカの位置を知る必要がある。したがって、一実施の形態は、システムディレクトリ内に、複数のデータセンターにわたるすべてのジオノードにとって利用可能なファイルとして、ジオノードが分散ファイルシステム（例えばＨＤＦＳ）自身に対するブロック報告を書き込むことを提供する。ある実装は、ブロック報告のファイルパスが以下のネーミング規則に従って形成されることを必要とする。
【０１１８】
/consensus/blockReports/<blockPoolId>/<dcName>/<storageID>/br_<hash-report>
ここで、<hash-report>は、ブロック報告のハッシュ（例えばＭＤ５）を含む。
【０１１９】
一実施の形態によれば、ブロック複製器でないジオノードのみが、ファイルシステムに外国ブロック報告を書き込むように構成される。したがって、複数のブロック複製器でないジオノードが同じブロック報告を書き込むように構成され、その書き込みを試すかもしれない。しかしながら、そのようなブロック複製器でないジオノードのうちの１つのみが成功すべきである。パス名に報告の（例えばＭＤ５の）ハッシュを付加することは、ジオノードがいくつかの他のローカルなジオノードがすでにそのブロック報告を書き込んでいることを理解し、したがって書き込みの衝突を回避できる。成功裏に書き込んだ者はその後、ディレクトリから以前のすべてのブロック報告ファイルを削除するであろう。
【０１２０】
ブロック報告ファイルは、外国ブロック複製技術を用いて、データセンターをわたって複製される。一実施の形態によれば、ジオノードは、新たなブロック報告を求めて周期的にシステムディレクトリをポーリングするように構成され得る。一旦、そのファイルが読み出し可能になると、他のデータセンターのジオノードは、それを読み出し、その外国ブロック報告を処理する。通常動作の間、間欠的な外国ブロック報告は、ＬＡＮ環境においてＣノードを更新するためにデータノードがブロック報告を発行する方法と類似の方法で、ジオノードに、クラスター上の他のデータセンター内におけるブロック報告が位置している場所の最新の見解を提供する。
【０１２１】
ＷＡＮクラスターの全体が起動するとき、各データセンターのデータノードは、ブロック報告の生成と、それらの自国のジオノードに対する送信とを開始する。そしてジオノードは、それらの自国のブロック報告の受信を開始する。上記したように、一実施の形態によれば、所与のデータセンターにおいてデータブロックが一旦完全複製に到達すると、ブロック複製器でないジオノードがＦＲＲ提案を発行し、それによって、外国ジオノードが（自身にとって）外国のブロック報告についての情報を得ることが可能になる。
【０１２２】
実行中のＷＡＮクラスター上でただ１つのジオノードのみが再起動するケースでは、他のデータセンターからのＦＲＲがブロックのレプリカ数として送信されることはない。したがって、一実施の形態によれば、外国ブロック報告は、再起動するジオノードか外国レプリカが格納されている位置を学ぶことのできる唯一のメカニズムを構成し得る。ジオノードが上述したＦＲＲプロセスを用いて外国レプリカの位置を学習している間、クライアント要求ＧｅｔＢｌｏｃｋＬｏｃａｔｉｏｎｓ（）が失敗し得ることに注意が必要である。一実施の形態によれば、そのようなクライアント要求が提出されたデータセンターのジオノードにとって外国の位置が未だ知られていないとき、そのクライアント要求を他のデータセンター上のジオノードにフェイルオーバーするための規則が生成され得る。
＜ジオノードの起動＞
【０１２３】
一実施の形態によれば、ジオノードの起動シーケンスはＬＡＮ環境でのＣノードのそれをなぞるが、少し違いがある。単一の名前ノードクラスターをＷＡＮクラスターに変換するために、名前ノードの記憶装置ディレクトリが、ジオノードを実行するために準備されたすべてのノードに分配され得、その後、クラスターが起動される。或いは、名前ノードが動作しているときに単一のジオノードが起動されてもよい。追加のジオノードがその後、ローカルなＬＡＮクラスターを形成するように、空の状態の中に追加され得る。そしてさらに、１つ以上のデータセンター上でジオノードが追加され得る。一実施の形態によれば、クラスタに参加している各ジオノードはその後、Ｃノードに関して上で詳述したように、既存の複数のノードのうちの１つから名前空間のイメージをダウンロードし、ダウンロードされたチェックポイントの最新のＧＳＮから始めて現在最大のＧＳＮに至るまでの同意の学習を開始する。もし、再起動しているジオノードが名前空間のイメージをダウンロードする必要があるならば、一実施の形態は、その再起動しているジオノードが、もし利用可能であれば、自国の他のジオノードをヘルパーとして好ましく選択することを必要とする。このことは、ＷＡＮ８０８上での非効率な転送を回避する。
＜外国の状態の回復＞
【０１２４】
Ｃノードと比較すると、起動時の複数のジオノードは、それらの外国の状態を追加する追加のステップを実行するように構成され得る。そのような追加のステップは、外国データノード及び外国のブロックレプリカを追加する（について学ぶ）最終ステップを追加することを含む。
【０１２５】
データノードは、ここで詳述されるように、自国のジオノードを用い、自国のジオノードがデータノード登録提案を（複数のデータセンターにわたって全クラスターに論理的に広がっている）調整エンジン２０８に対して提出し、対応する同意が到着した後にその登録を処理するとすぐに登録されるように構成され得る。したがって、全クラスターが起動するときには、すべてのジオノードが、データノードの登録及び外国レプリカ報告の同意を通じて、外国データノード及び外国ブロックレプリカのそれぞれについて学習する。
【０１２６】
クラスターが起動しており、その中の単一のジオノードが再起動するとき、外国登録及び外国レプリカ報告は、すぐには利用可能とならないかもしれない。上で詳細に開示したように、より早い時期の外国レプリカの位置は、分散ファイルシステム（例えばＨＤＦＳ）内に永続的に格納され得る外国ブロック報告のファイルから回復され得る。しかしながら、これらのブロック報告ファイルが読み出される前に、ジオノードは、これらのレプリカが格納されている外国データノードについて学習する必要がある。
【０１２７】
一実施の形態によれば、ジオノードが再起動及び／又はクラスターに新規に参加するとき、そのジオノードは、失われた同意の学習を開始する前に、同意リカバリについての提案を発行することができる。このことは、そのジオノードが、自身を最新であると看做すことのできるＧＳＮに印をつけることを可能にする。実際、ＣＥ８２２は発行された提案に対応する同意を発行し、その同意はグローバルな順序付けられたシーケンス内に取り込まれる。この方法では、ジオノードが、自身の同意リカバリに対する同意の前に順序付けられたすべての同意に加えて自身の同意リカバリに対する同意を学習するとき、「追いつくこと」が完了したと看做され、格納された名前空間の状態は、現行のものでありかつ一貫していると看做され得る。この時点において、そのジオノード内に格納されている名前空間は、その後、ジオノードがＣＥ８２２によって発行される同意を消費することを通じて、現行の状態に留まり得る。一実施の形態によれば、複数のジオノードが外国ジオノードから同意リカバリに対する同意を受信するとき、それらは追加的にすべてのそれらの自国のデータノードに対して、登録のための印を付けることができる。この印は、自国データノードが次の鼓動で再登録を要求されるであろうことを意味する。このことは、新しいジオノードが、それが自身の同意リカバリに対する同意の後に受信するであろうデータノード登録の同意（複数のデータセンターにわたるすべてのジオノードによって受信されるもの）を介して、名前空間が最新であるときに外国データノードについて学習することを可能にする。
＜リースのリカバリ＞
＜リースの管理＞
【０１２８】
（例えばＨＤＦＳのような）分散ファイルシステムは、１つのクライアントのみを、特定のファイルに対するライターとして許容するように構成され得る。単一ライターセマンティックスを実施するため（及び、それによって、２つの異なるクライアントが同じファイルを開き、それに対して書き込み始めることを避けるため）、リースの概念が導入される。リースは、ファイルか生成され、追加のために開かれるときに生成され得る。リースは、ファイルと、そのファイルに現在書き込んでいる（１つの）クライアントとを識別する。リースは、ファイルが閉じられるとき、破壊され、又は、さもなければ満了したものとしてマークされる。まだ満了していないリースは、その存続期間の間、他のクライアントがそのファイルに書き込みアクセスを行うことを禁止する。
【０１２９】
一実施の形態によれば、リース・マネージャ・プロセスは、名前ノードのためにリースを保持するように構成される。もし、そのリースが割り当てられたクライアントがそのリースに関連するファイルを閉じる前に死んだら、そのリースは、ファイルシステム自体によって、ゴミとして集められて処分され得る。リースを処分する前に、ファイルシステムは、そのファイルが首尾一貫した状態か否かを確認し、もし否であれば、ファイルブロックのリカバリを実行することができる。
【０１３０】
一実施の形態によれば、リースのリカバリプロセスは、（元のリースフォルダが応答せず、誰も所定期間内にそのファイルを閉じないときなど）そのファイルのリースについてのハード限界が満了するとき、又は、ソフト限界（例えば１０分）が終了し、かつ、他のクライアントがそのファイルへの書き込みアクセスの権利を主張しているときに、名前ノードによって起動され得る。実施の形態によれば、リースのリカバリプロセスは、２つのステップを含み得る。実際に、名前ノードは、リース・リカバリを始めるために、必要に応じて後続のブロックレプリカのリカバリをスケジュールできるＩｎｔｅｒｎａｌＲｅｌｅａｓｅＬｅａｓｅ（）を呼び出すことができる。その後、名前ノードは、ブロックレプリカのリカバリを実行するために、ファイルの最新ブロックのための新たな生成スタンプを生成し、かつ、その新たな生成スタンプをリカバリＩＤとして用いてそのブロックのメタデータを他のレプリカに同期させるために第１のデータノードを選択することができる。その第１のデータノードはその後、ブロックの正しい長さを調整するために、他のデータノードと通信することができる。例えば、ブロックの正しい長さは、問題のブロック又はブロックの部分を格納しているすべてのデータノードに対して共通である最小の長さと同じ程度に選択され得る。そのような調整が一旦完了すると、第１のデータノードは、ＣｏｍｍｉｔＢｌｏｃｋＳｙｎｃｈｒｏｎｉｚａｔｉｏｎ（）呼び出しを用いて、ジオノードに対するリカバリの結果を確認することができる。ＣｏｍｍｉｔＢｌｏｃｋＳｙｎｃｈｒｏｎｉｚａｔｉｏｎ（）呼び出しは、新たな生成スタンプ、新たな長さ、及び新たなレプリカ位置を用いて、ファイルの最後のブロックを更新するように構成され得る。ファイルはその後、閉じられる。この最後のブロックは、それが死ぬ前にクライアントによって何らデータが書き込まれなければ、削除され得る。
＜ＬＡＮリース及びＣノード＞
【０１３１】
ＬＡＮ環境では、複数のＣノードのうちの任意の１つが、そのリース・マネージャがリースが満了したことを検出するときに、リース・リカバリを起動し得る。しかしながら、リースの対象であったファイル又はそのデータブロックに対する任意の変化は、すべてのＣノード上で首尾一貫した複製を提供するために調整されなければならない。
【０１３２】
一実施の形態によれば、ファイルの状態はＩｎｔｅｒｎａｌＲｅｌｅａｓｅＬｅａｓｅ（）内で分析され得るが、Ｃノードは、名前ノードとは異なる、その段階でファイルを修正しない。もし、分析されたファイルが既に閉じられていたら、Ｃノードは単に復帰する。しかしながら、一実施の形態によれば、もしそのファイルが既に閉じられていなければ、そのＩｎｔｅｒｎａｌＲｅｌｅａｓｅＬｅａｓｅ（）・プロセスは、ファイルの最後のブロックの状態に応じて、次の２つの提案のうちの１つを発行する。
１）もし、分析されたファイルのすべてのブロックが完全であれば、完了の提案(CompleteProposal)が発行され得、それにより、Ｃノードは、調整された態様でそのファイルを単に閉じることができる。
２）もし分析されたファイルのブロックが完全でなく、ブロック・レプリカ・リカバリが必要であれば、リカバリブロック提案(RecoverBlockProposal)が発行され得る。
【０１３３】
もし、リカバリが、（追加、開く、又はリースのリカバリ(RecoverLease)のような）同意を処理している間のリースのソフト限界の満了によって起動されるのならば、その同意を実行しているＣノードはその後、ブロック・リカバリを起動することができる。一実施の形態によれば、もしハード限界がリースのために満了するのであれば、ブロック複製器のみが、完了又はブロックのリカバリ(RecoverBlock)を提案するであろう。この方法では、複数のＣノードが同じファイルのリースのリカバリを開始する見込みが最小化される。もし、Ｃノードが提案を発行できるならば、ＳｈｏｕｌｄＲｅｌｅａｓｅＬｅａｓｅ（）手続きが定義され得る。
【０１３４】
完了の同意（すべての関係するデータノードが今やファイルの同じブロックを格納している）がＣノードに到着するとき、Ｃノードは、リース満了の対象であったファイルを閉じることができ、それによって、リース・リカバリが整然と完了する。複数のＣノードによって完了の提案が提案されるというイベントにおいては、その後、最初の時間内の完了の同意がそのファイルを閉じ、後続のものは、何もさらにする必要がない。
【０１３５】
ブロックのリカバリの提案(RecoverBlockProposal)に応答するブロックのリカバリ(RecoverBlock)に対する同意は、ＩｎｉｔｉａｌｉｚｅＢｌｏｃｋＲｅｃｏｖｅｒｙ（）を実行することができる。これは、
１）ユニークなリカバリＩＤである新たなＧＳＮを生成し、
２）ジャーナルにリースの再割り当てについての記録を書き込み、
３）最新のブロックの状態をリカバリ中(UNDER_RECOVERY)状態に変更し、
４）そのブロックをリカバリ対象(to-be-recovered)のキューに加える。
【０１３６】
すべてのＣノードが最新のブロックのためにブロック・レプリカ・リカバリをスケジュールできる一方で、唯一のブロック複製器として指定されたＣノードのみが実際に第１のデータノードにリカバリを実行するかを尋ねるであろう。ブロック複製器Ｃノードのみがデータノード・コマンドを用いてデータノードに返答できるからである。
【０１３７】
ブロック複製器として指定されているＣノードはその後、第１のデータノードを用いてブロックのリカバリをスケジュールすることができる。リカバリの最後の段階では、第１のデータノードは、ＣｏｍｍｉｔＢｌｏｃｋＳｙｎｃｈｒｏｎｉｚａｔｉｏｎ（）呼び出しを用いて、ブロック複製器であるＣノードに対してリカバリ結果を確認する。ＣｏｍｍｉｔＢｌｏｃｋＳｙｎｃｈｒｏｎｉｚａｔｉｏｎ（）はまた、それが最新のブロックを更新又は削除し、及び／又は、ファイルを閉じるのに有効であることから調整され、永続的な記録を維持するために記録を書き込むことを含む。ブロック複製器Ｃノードはその後、ブロック同期の委託提案(CommitBlockSynchronizationProposal)を提出し、対応する同意が到着し実行される第１のデータノードに対して応答する。同意の実行は、正常な名前ノードのＣｏｍｍｉｔＢｌｏｃｋＳｙｎｃｈｒｏｎｉｚａｔｉｏｎ（）動作を実行する。
＜ジオノード：ＷＡＮでのリース＞
【０１３８】
ジオノードは、一実施の形態によれば、外国レプリカをリカバリできないことを思い出してほしい。データノードが自国のジオノードに対してのみ報告を行うからである。ブロックは最初に、そのファイルの生成が始まるデータセンター内で生成される。書き込まれたファイルの完了したブロックのレプリカは、一実施の形態によれば、元のデータセンターで完全な複製に到達したことに応じてのみ、他のデータセンターに転送される。
【０１３９】
ＷＡＮ環境において、１つのファイルがデータセンターＡ（ＤＣＡ）上でクライアントによって生成され、そのクライアントがファイルを閉じる前に死んだとする。データセンターＢ（ＤＣＢ）では、ジオノードはそのファイル及びそのブロックについての情報を有するであろう。ＤＣＢはまた、そのファイルの完了したブロック（ＤＣＡ上で完全に複製されたブロック）の自国のブロックレプリカを含むことができる。しかしながら、ＤＣＢは、構築中のブロックのいかなるレプリカも含むべきではない。
【０１４０】
ＷＡＮのためのＳｈｏｕｌｄＲｅｌｅａｓｅＬｅａｓｅ（）は、ソフト期限満了及びハード期限満了の両方のケースにおいて、ＬＡＮのための場合と同様の方法で行動する。すなわち、リースのリカバリは、任意のデータセンター上のジオノードによって起動され得る。同様に、完了の同意は、ＬＡＮのケースで動作するのと同様に、ＷＡＮのケースでも動作するよう構成されることができ、ジオノードはそのファイルを閉じ得る。
【０１４１】
ブロックのリカバリ(RecoverBlock)に対する同意を実行している間、各ジオノードは、そのファイルの最新のブロックの外国及び自国における期待される位置をチェックする。その後、以下に示す更なる動作がリースの対象であるファイルのブロックの状態に応じて行われる。
１．もしそのファイルのブロックが外国位置のみを有しているならば、ジオノードは、ブロックのリカバリの初期化(InitializeBlockRecovery)を行わない。
２．もしそのブロックが自国位置のみを有しているならば、ジオノードは、リカバリがレプリカを有しているデータセンター上で実行されることを確実にするため、ブロックのリカバリの初期化(InitializeBlockRecovery)を行わなければならない。
３．もしそのブロックが外国と自国の位置の両方を有しているならば、ブロックのリカバリ(RecoverBlock)に対する提案を提出したＤＣ中のジオノードが、ブロックのリカバリの初期化(InitializeBlockRecovery)を行わなければならない。
４．もしそのブロックがレプリカを有していなければ、ブロックのリカバリの初期化(InitializeBlockRecovery)は、生きているデータノードの中からランダムに選ばれたものに対してスケジュールされる。これは、ブロックのリカバリ(RecoverBlock)に対する提案を提出したＤＣに属するジオノード上で実行される。
【０１４２】
したがって、複数のＤＣのうちの１つにおける１つのブロック複製器ジオノードのみが、ブロックのリカバリを開始するであろう。レプリカを回復することの命令は、第１の自国データノードに対して、しかし、外国自国を問わずすべての期待される位置に送信されるであろう。第１のデータノードは、レプリカを含むすべてのデータノードと話すことにより、ブロックの正しい長さを決定する。これは、異なる複数のＤＣ上のデータノード間での通信を引き起こすことができる。リカバリの後には、第１のデータノードはブロック複製器であるジオノードに対し、ブロック同期の委託(CommitBlockSynchronization)呼び出しを送ることができる。このジオノードはその後、ブロック同期の委託提案(CommitBlockSynchronizationProposal)を提出することができる。
【０１４３】
一実施の形態によれば、対応するブロック同期の委託(CommitBlockSynchronization)に対する同意は、レプリカのための新たなターゲットとして、外国及び自国の位置を含み得る。外国の位置は、現在のジオノードにより、外国レプリカ報告(ForeignReplicaReport)として取り扱われる。すなわち、それは新たに報告された位置を外国のものとして格納し、最新のブロックを強制的に完了させ、要求があればファイルを完成させる。
＜非対称のブロック複製＞
【０１４４】
ブロック複製は、一実施の形態によれば、クラスタ内のすべてのデータセンターにわたって同じである必要はない。実際、ファイルごとに選択可能な複製因子が提供され得、その複製因子は、ファイルが生成されるときにファイルごとに設定される。複製因子は、一実施の形態によれば、ＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）提案を用いて、より遅い時間にリセットされ得る。ファイルは、デフォルトの複製因子を用いて生成され得る。例えば、３というデフォルトの複製が設定され得る。代わりに、例えば２又は５のような、他の複製因子が設定されてもよい。ＷＡＮクラスターでは、そのようなセマンティックスは通常、複数のファイルが異なるデータセンター上で、ファイルの生成者ごとに特定される値に等しい複製因子という、同じ複製因子を有することを意味する。
【０１４５】
しかしながら、異なるデータセンター上では、複製を低減する又は増加させることを許可することが望ましい。例えば、あるデータセンターが主であると看做され、他のデータセンターが従であると看做されるとき、ある人は、例えばコストの制約又は好ましいサービス品質のために、従たるデータセンターにはより少ない数のレプリカを保持することを願うかもしれない。
【０１４６】
実際、ファイル生成呼び出しは、データセンターごとにデフォルトの複製因子を許可するように修正され得る。このケースでは、リーズナブルなデフォルトの振る舞いが、複製因子を現在のデータセンターのデフォルト値に設定するために存在し得る。例えば、ＤＣＡがデフォルトの複製ｒＡを有し、ＤＣＢがそのデフォルトをｒＢに設定したとする。また、ＤＣＡ上に位置しているクライアントが、複製因子ｒを有するファイルを、今、生成するものとする。すると、ＤＣＡは、そのファイルのためにその複製をｒに設定するであろう。一方、ＤＣＢは、その複製因子をそのデフォルトの複製ｒＢに設定するであろう。一実施の形態によれば、それ故、ファイル生成呼び出し内の単一の複製因子パラメータが元のＤＣ上のファイルのための複製値として取り扱われ得る一方、他のＤＣは、そのファイルの複製を設定するために、それらのデフォルトの複製因子を使用する。
【０１４７】
一実施の形態によれば、複製因子は、単一の複製値をパラメータとして許容するように構成され得るＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）呼び出しによって修正され得る。ＷＡＮクラスターでは、このパラメータは、クライアントの呼び出しが実行されたデータセンター上のファイルの新たな複製因子として取り扱われ得る。他のデータセンターは、対応する複製設定(SetReplication)に対する同意を、もしそれが外国のジオノードによって提案されたものであるならば、単に無視することができる。そのようなメカニズムを用いて、複製因子は、異なるデータセンター上で随意に設定され得る。複製因子は、データセンター独自の属性になることができ、それ故、一対一のメタデータの複製から除外され得る。
＜選択的なデータ複製＞
【０１４８】
一実施の形態によれば、選択的なデータ複製は、選択されたデータにつき、指定された１つのデータセンター又は指定された複数のデータセンターからのみ見ることができ、他のデータセンターからの複製又はアクセスを許可しないようにすることができる。実施の形態によれば、１以上の以下の代替案が実装され得る。
−  ディレクトリは、すべてのデータセンターから複製され、アクセス可能である。
−  ディレクトリは、すべてのデータセンターから複製され、読み出され得るが、所定のサイトでのみ書き込み可能である。
−  ディレクトリは、いくつかのデータセンター上で複製されるが、他のデータセンターへは決して複製されない。
−  ディレクトリは、１つのデータセンター上でのみ複製され、見ることができる。
【０１４９】
現在の複製アーキテクチャを思い出すと、それは、同じ単位の名前空間が複製のノード上で維持され得ることを仮定する。調整エンジンプロセス８２２は、さらに、複数のジオノードの間で、及び、データセンター間でのメタデータ及びファイルシステムのデータの複製が首尾一貫していることを保証する。したがって、言葉「選択的なデータの複製」は、名前空間にというよりも、地理的に分散したクラスター内に格納されるデータについて適用可能である。
【０１５０】
上で導入された非対称のブロック複製においては、データセンターに特有のファイル属性、すなわち複製が導入され得る。この文脈では、０という特別なケースの値が選択的なデータ複製において重要な役割を果たす。実際、もしファイルの複製因子属性がデータセンター（ＤＣＢ）に対して０に設定されるとすると、そのファイルのブロックは、ＤＣＢ上で決して複製されない。元々、現在のＨＤＦＳクラスターは、０複製でファイルを生成することを許可しない。しかしながら、実施の形態は、値０を許容するようにＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）を拡張する。そのＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）は、一実施の形態によれば、現在のデーンセンターに対してのみ、ファイルの複製因子属性を変更する。したがって、０という値は、そのデータセンターにおいて、０という複製値に関連付けられたファイルのブロックの複製を許容しないであろう。
【０１５１】
実施の形態によれば、ＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）は、ディレクトリに対して適用するために、同様に拡張され得る。もし、複製因子の属性がディレクトリ上に設定されるならば、サブツリーに属するすべてのファイルは、その複製因子属性が特定のサブ・ディレクトリ又は特定のファイルのために明示的に他の値にリセットされない限り、その複製因子属性を受け継ぐ。ディレクトリ上で複製因子属性を設定することはデフォルトの複製パラメータの拡張であると考えられることができ、その中では、複製因子属性がルート・ディレクトリ上で設定され得る。一実施の形態によれば、もし明示的に設定されなければ、ファイルの複製因子属性は、複製設定を有している最も近い親の複製因子属性によって決定され得る。
【０１５２】
異なるデータセンターにおけるファイルとディレクトリの選択的な可視性は、データセンターに特有の他の属性として定義され得るパーミッションによって制御され得る。ＳｅｔＰｅｒｍｉｓｓｉｏｎｓ（）及びＳｅｔＯｗｎｅｒ（）呼び出しは、ＳｅｔＲｅｐｌｉｃａｔｉｏｎ（）と同様、それらの入力値を他のデータセンターに伝播しない。一実装によれば、１つ又は１つのファイルに対してパーミッション０００を設定することは、そのデータセンター上でのそれぞれのオブジェクトへのアクセスを禁止し、そのようなファイルをデータセンター上で効果的に「不可視」とする。一実施の形態によれば、（クラスターの管理者を代表する）ルートのユーザは、所有者とパーミッションを変更する完全な権限を提供され得る。
＜ＷＡＮクラスター上での役割、災害耐性＞
【０１５３】
上述したように、分散型の調整システム内におけるＣノードは、プロポーザー、ラーナー、及びアクセプタという３つの主たる役割を引き受け得る。また、各ノードは、１つ以上のそのような役割を引き受けることができる。ＬＡＮ環境ではしばしば、すべてのＣノードが３つの役割のすべてを引き受ける。実際、各Ｃノードは、自身の状態をＬＡＮの複数のＣノードと同期した状態に保つため、ラーナーでなければならない。クライアント要求を処理するために、各Ｃノードはまた、プロポーザであるべきである。アクセプタの役割は、システムの信頼性、すなわち、同時に起こる複数の故障に対する回復力を最大化するために、可能な限り多くのＣノードに割り当てられ得る。そのような実装では、１以上のＣノードは、大多数のＣノードが起動して動作している状態である限り、提供されたサービスに実質的な影響を与えることなく故障し得る。
【０１５４】
一実施の形態によれば、２つ以上のデータセンターを有するＷＡＮクラスターはまた、個々のジオノードの故障に対する耐性を用意すべきである。加えて、複数のデータセンターのうちの１つが故障し、又は、何らかの理由で他の（複数の）データセンターから孤立した（すなわち、これらにアクセス不能となった）場合にもサービスが起動された状態を維持することが望まれる。これは、例えば複数のデータセンター間のＷＡＮクラスターチャンネルが故障するときに発生し得る。もし２つのデータセンターが互いに孤立した状態となったとして、それらの名前空間のインスタンスに対して首尾一貫した変更をすることができるよう、それらの両方は独立して動作するべきではない。しかしながら、それらのうちの一方は動作可能な状態を維持し、他方は、その動作しているデータセンターとの通信が回復したときに追いつくための能力を提供されるべきである。一実施の形態によれば、これは、あるデータセンターが他より多くのジオノードを有するであろうことを意味する奇数個のジオノードを実行することによって達成され得る。
【０１５５】
複数のデータセンターが対称的に設定されるときには、異なるアプローチが使用され得る。例えば、ＤＣＡ及びＤＣＢがそれぞれ３つのジオノードを実行していると仮定することができる。ＤＣＡからの複数のジオノードはアクセプタであり、そのうちの１つはタイブレイカーとして指定されている。これは、３つのジオノードが、もしそれらが指定されたタイブレイカーであるジオノードを含むのであれば、クォーラムを形成することを意味する。この構成では、ＤＣＢからの複数のジオノードがいずれも利用可能でないというイベントの際にさえ、ＤＣＡは動作は継続する。この構成では、ＤＣＡから分離されているＤＣＢは、クォーラムを失い、少なくともＤＣＡとの通信が回復するまで、麻痺させられる（すなわち、名前空間のそのインスタンスに対する変化を伴う任意のさらなる同意を処理しない）であろう。
【０１５６】
そのような構成は、もしデータセンターが周期的な作業量の変化を経験するのであれば、特に有益であり得る。例えば、ＤＣＡは、日中により高い処理負荷を有し、ＤＣＢは、夜間により比較的高い処理負荷を有すると仮定する。一実施の形態によれば、クォーラムは、日中にＤＣＡのジオノードに対してアクセプタの役割を割り当て、対応して、夜間にはアクセプタの役割をＤＣＢのジオノードに割り当てることによって、ローテーションされ得る。
【０１５７】
図９は、一実施の形態による、コンピュータに実装された方法のフローチャートである。示されるように、ブロックＢ９１は、ワイド・エリア・ネットワーク上で第１のデータセンターと、地理的に離れた第２のデータセンターとに広がる単一の分散ファイルシステム（計算装置）クラスターの確立を指令する。加えて、追加のデータセンター（図示せず）が、同じ分散ファイルシステムに含まれてもよく、かつ、その分散ファイルシステムによって管理されてもよい。図８に示すように、第１のデータセンター８０４は、複数の第１の名前ノード（ここでは、ジオノードとも呼ばれる）８１０，８１２，及び８１４（その他の第１の名前ノードは、図８には示されていない）と、８２４，８２６，８２８，及び８３０（その他の第１のデータノードは、図８には示されていない）に示されるようにそれぞれクライアントファイルのデータブロックを格納するように構成された複数の第１のデータノード（ここでは、データノードとも呼ばれる）とを含み得る。第２のデータセンターは、図８に８０６で示されるように、複数の第２の名前ノード８１６，８１８，及び８２０（その他の第２の名前ノードは、図８には示されていない）と、それぞれクライアントファイルのデータブロックを格納するように構成された複数の第２のデータノード８３２，８３４，８３６，及び８３８（その他の第２のデータノードは、図８には示されていない）とを含み得る。ブロックＢ９２は、複数の第１の名前ノードのそれぞれの中と、複数の第２の名前ノードのそれぞれの中とに、クラスター８０２の名前空間の状態を格納するように指令する。Ｂ９３に示されるように、第１の名前ノードに格納される名前空間の状態は、１以上の選択された第１のデータノードに書き込まれるデータブロックに応答して更新され得る。同様に、Ｂ９４は、第２の名前ノードに格納される名前空間の状態が１以上の選択された第２のデータノードに書き込まれるデータブロックに応答して更新され得ることを指令する。最後に、Ｂ９５に示されるように、第１の名前ノード（８１０，８１２，８１４・・・）に格納される名前空間の状態に対する更新と、第２の名前ノード（８１６，８１８，８２０・・・）に格納される名前空間の状態に対する更新とが、名前空間の状態を単一の分散ファイルシステムのクラスターの第１及び第２のデータセンター８０４，８０６にわたって首尾一貫した状態で維持すべく、（例えば、調整エンジンプロセス８２２によって）調整され得る。そのような更新は、本書で開示した順序付けられた同意のセットに従って実行され得る。すなわち、名前ノード（Ｃノード又はジオノード）内に格納される名前空間の状態は所与の時点では他の名前ノードに格納される名前空間の状態と異なっているかもしれないが、本書に開示されるグローバルに順序付けられた同意のシーケンスは、（第１及び第２の複数の名前ノードのそれぞれの中で実行されるように構成され得る）調整エンジンプロセス８２２によって管理されていることから、それが位置しているデータセンターにかかわりなく、複数の名前ノードのそれぞれが、順序付けられた同意のセットを順に実行することを通して、やがてはその格納している名前空間の状態を他の名前ノード内に格納されている名前空間の状態と同意した状態とすることを確実にする。
【０１５８】
第１の名前ノード８１０，８１２，８１４のそれぞれが（「予備」「非アクティブ」「スタンバイ」に対立するものとしての）「アクティブ」な名前ノードであるとき、他の第１の名前ノード８１０，８１２，８１４のうちの１以上は、第１のデータセンター８０４内で名前空間の状態を更新しているかもしれない。同時に、他の第２の名前ノード８１６，８１８，８２０のうちの１以上もまた、第２のデータセンター８０６内で名前空間の状態を更新しているかもしれない。
【０１５９】
さらなる実施の形態によれば、複数の第１の名前ノードのそれぞれは、第１のデータセンター内の他の１以上の第１の名前ノードが名前空間の状態を更新している間に、名前空間の状態を更新するように構成され得る。一実施の形態によれば、複数の第２の名前ノードのそれぞれは、第２のデータセンター内の他の１以上の第２の名前ノードが名前空間の状態を更新している間に、名前空間の状態を更新するように構成され得る。第１のデータセンター内の複数の第１の名前ノードのそれぞれはまた、第２のデータセンター内の複数の第２の名前ノードのいくつかが名前空間の状態を更新している間に、名前空間の状態を更新するように構成され得る。
【０１６０】
さらなる実施の形態によれば、複数の第１のデータノードのそれぞれは、第１のデータセンター内の複数の第１の名前ノードとのみ通信するように構成される。同様に、複数の第２のデータノードのそれぞれは、第２のデータセンター内の複数の第２の名前ノードとのみ通信するように構成される。調整エンジンプロセスは、第１及び第２の複数の名前ノードから、名前空間の状態を更新し、呼応して、複数の第１及び第２の名前ノードが名前空間の状態を更新しようとする順序を特定する順序付けられた同意のセットを生成することについての提案を受信するように構成され得る。実際、複数の第１の名前ノード及び複数の第２の名前ノードは、調整エンジンプロセスから順序付けられた同意のセットが受信されるまで、名前空間の状態に対する更新を遅延させるよう構成される。さらに、調整エンジンプロセス（図８では８２２）は、複数の第１及び第２の名前ノードのうちの１つ以上の障害、及び／又は、複数の第１及び第２のデータノードのうちの１つ以上の障害の際、名前空間の状態を首尾一貫した状態に維持するように構成され得る。
【０１６１】
例えば、（単一の、地理的に分散した）ファイルシステムは、ハドゥープ・分散ファイルシステムの１つのバージョンであり得、又は、ハドゥープ・分散ファイルシステムの１つのバージョンを含み得る。他の分散ファイルシステムは、実施の形態によれば、当業者が理解できるように工夫され、改造され得る。一実施の形態によれば、第１のデータセンターのクライアントのファイルの複数のデータブロックの少なくともいくつかのレプリカは、第２のデータセンター内の複数の第２のデータノードのうちの選択された１つ以上に格納され得る。第２のデータセンターのクライアントのファイルの複数のデータブロックの少なくともいくつかのレプリカは、第１のデータセンター内の複数の第１のデータノードのうちの選択された１つ以上に格納され得る。
【０１６２】
一実施の形態によれば、第１のデータセンター内の第１のデータノードのそれぞれは、ＷＡＮ上の第２のデータセンターの複数の第２のデータノードのうちの選択された１つに対し、選択されたデータブロックを非同期で送るよう構成され得る。選択されたデータブロックは、その選択されたデータブロックの所定数（例えば３個）のレプリカが、第１のデータセンター内の複数の第１のデータノードのうちの選択された１つに格納された後、第１のデータセンターから第２のデータセンターに送信され得る。
【０１６３】
一実施の形態によれば、複数の第１の名前ノードのうちの少なくともいくつか（一実施の形態によれば、ブロック複製器の責任が割り当てられた名前ノード以外のすべて）は、複数の第２の名前ノードによる消費のために、複数の第１のデータノードに格納されているすべてのデータブロックのリストを含む外国ブロック報告を生成するように構成され得る。同様に、複数の第２の名前ノードのうちの少なくともいくつか（一実施の形態によれば、ブロック複製器の責任が割り当てられた名前ノード以外のすべて）は、複数の第１の名前ノードによる消費のために、複数の第２のデータノードに格納されているすべてのデータブロックのリストを含む外国ブロック報告を生成するように構成され得る。生成された外国ブロック報告は、ブロック報告ファイルとしてファイルシステムに書き込まれ、第１及び第２のデータセンター内の第１及び第２の名前ノードのそれぞれはその後、ファイルシステムから周期的にそのブロック報告ファイルを読み出し、それぞれに格納している名前空間の状態を対応して更新することができる。
【０１６４】
複数の第１の名前ノード及び複数の第１のデータノードは、任意のデータブロックがワイド・エリア・ネットワーク上で第２のデータセンターに送信される前に、第１のデータセンターのクライアントファイルのデータブロックの書き込みを完了するように構成される。この方法では、これらのデータブロックのレプリカがＷＡＮのスピードで他のデータセンターに非同期で送信され得る一方で、クライアントの書き込みはＬＡＮのスピードで完結する。一実施の形態によれば、第１の名前ノード及び第１のデータノードは、クライアントファイルのデータブロックが第１のデータセンター内で第１の所定のかつ選択可能な回数複製されることとなるように構成され得る。同様に、第２の名前ノード及び第２のデータノードは、クライアントファイルのデータブロックが第２のデータセンター内で第２の所定のかつ選択可能な回数複製されることとなるように構成され得る。第１の所定のかつ選択可能な回数は、第２の所定のかつ選択可能な回数と同じであってもよいし、異なっていてもよい。
【０１６５】
本開示の一定の実施の形態を記述してきたけれども、これらの実施の形態は例として提示されたものに過ぎず、開示の範囲を限定することを意図したものではない。実際に、本書に開示された新規なコンピュータに実装された方法、装置、及びシステムは、様々な他の形態に具体化され得る。例えば、一実施の形態は、計算装置によって実行されたときに、その計算装置に本書で記述され又は示されたワイド・エリア・ネットワーク上での分散ファイルシステムを実行させることになる一連の命令を表すデータが格納された有形、固定、機械読み取り可能なメディアを含む。例えば、一連の命令はダウンロードし、その後、メモリー装置（例えば、図７に７０２で示したようなもの）、記憶装置（例えば、固定式又は回転式のメディア装置又は他のデータキャリア）上に格納されることができる。さらに、本書で記述した方法及びシステムの形態には、様々な省略、代用、変更が本開示の精神を離れることなく、なされ得る。添付の複数の請求項及びそれらの等価物は、本開示の範囲及び精神に含まれるそのような形態及び変形例をカバーすることを意図している。例えば、当業者は、様々な実施の形態において、実際の物理的及び論理的な構造が図示したものと異なり得ることを理解するであろう。実施の形態によれば、上記例で記述されたあるステップは削除され得るし、他のステップが追加され得る。また、上で開示された特定の実施の形態の特徴及び属性は、追加の実施の形態を構成するために異なる方法で結合され得、それらのすべては本開示の範囲に含まれる。本開示は、一定の好ましい実施の形態及び適用を提供するけれども、本書に規定したすべての特徴及び有利点を備えない実施の形態を含む当業者にとって明らかな他の実施の形態もまた、本開示の範囲内である。したがって、本開示の範囲は、添付の複数の請求項を参照することによってのみ定義されることを意図している。
【図１】
0006628730.tif 000002
【図２】
0006628730.tif 000003
【図３】
0006628730.tif 000004
【図４】
0006628730.tif 000005
【図５】
0006628730.tif 000006
【図６】
0006628730.tif 000007
【図７】
0006628730.tif 000008
【図８】
0006628730.tif 000009
【図９】
0006628730.tif 000010