(57)【要約】  分散システムで実行している複数のプロセスのためにチェックポイントを作成する分散システム。分散システムは複数の計算ノードを含み、各々の計算ノードでオペレーティング・システムが実行している。各々の計算ノードで、ユーザ・レベルのチェックポイント・ライブラリが存在し、そのチェックポイント・ライブラリは、同じ計算ノードに存在するオペレーティング・システム及び他の計算ノードに対してトランスペアレントである。各々のチェックポイント・ライブラリは、分散システムをチェックポイントするため、ウインドウ型メッセージング・ロギング・プロトコルを使用する。分散システムの分散計算に参加するプロセスは、チェックポイント・ライブラリを使用してハードウェア・アドレスを再マッピングすることによって、分散システムで１つの計算ノードから他の計算ノードへ移行されてもよい。【選択図】図３【特許請求の範囲】
【請求項１】
複数の計算ノードを備える分散システムで実行している分散計算の複数のプロセスのためにチェックポイントを作成する方法であって、
各々のプロセスのプロセス間通信を一時停止するステップと、
各々の計算ノードに存在するチェックポイント・ライブラリを使用してチェックポイントを作成するステップと、
複数の計算ノード各々のために、
チェックポイント区間で修正されたメモリ領域の第１のリストを記憶するステップと、
メモリ領域の第２のリストを記憶するステップと、
チェックポイントを作成するステップが、（i）第１のリストを第２のリストとして記録するステップを備え、（ii）チェックポイント区間で修正されたメモリ領域のリストへの書き込みを防止するステップと、（iii）チェックポイントが完了するまで、計算ノードの各々で計算と並列に続行するステップと、
を備える方法。
【請求項２】
更に、各々のプロセスへチェックポイント・コマンドを送信することによって、チェックポイントの作成を開始するステップを備える、請求項１に記載の方法。
【請求項３】
複数のプロセスが複数の計算ノードによって状態され、
各々のプロセスのプロセス間通信を一時停止するステップがフリーズ期間に行われる、
請求項１に記載の方法。
【請求項４】
更に、フリーズ期間に全てのプロセスのローカル実行を一時停止するステップを備える、請求項３に記載の方法。
【請求項５】
更に、分散システムで複数の分散アプリケーションを実行するステップを備え、チェックポイントを作成するステップが、分散アプリケーションの信頼性を向上する、請求項１に記載の方法。
【請求項６】
更に、各々の計算ノードで分散アプリケーション及びチェックポイント・ライブラリを実行するステップを備え、チェックポイント・ライブラリが分散アプリケーションへリンクされ、チェックポイント・ライブラリが計算ノードのユーザ空間に存在する、請求項１に記載の方法。
【請求項７】
第１のリストが現在のコミット・リスト・バッファの中に記憶され、第２のリストが前のコミット・リスト・バッファの中に記憶される、請求項１に記載の方法。
【請求項８】
現在のコミット・リスト・バッファを記録するステップ及び複数のメモリ領域への書き込みを防止するステップの後で、各々の計算ノードのために、チェックポイントを作成するステップが計算ノードの各々で計算と並列に続行する、請求項７に記載の方法。
【請求項９】
分散システムで実行している複数のプロセスのためにチェックポイントを作成する分散システムであって、
各々の計算ノードでオペレーティング・システムが実行する複数の計算ノードと、
各々の計算ノードのユーザ空間に存在するチェックポイント・ライブラリであって、複数の計算ノードの中の対応する計算ノードのオペレーティング・システムにトランスペアレントであるチェックポイント・ライブラリと、
分散アプリケーション及びミドルウェアが各々の計算ノードに存在し、チェックポイント・ライブラリが、更に、分散アプリケーション及びミドルウェアにトランスペアレントであり、複数のプロセスの任意の１つが、複数の計算ノードの中で１つのノードから他のノードへ移行されること
を備える分散システム。
【請求項１０】
全てのプロセス間メッセージ、ダイナミック・メモリ割り付け、二次記憶アクセス、及び各々の計算ノードの信号処理が、同じ計算ノードに存在するチェックポイント・ライブラリを介して処理される、請求項９に記載の分散システム。
【請求項１１】
ウインドウ型ロギング・プロトコルがチェックポイント・ライブラリの中で実施される、請求項９に記載の分散システム。
【請求項１２】
相互接続ネットワークによって接続された複数の計算ノードを備え、複数の計算ノードが、送信プロセスを実行してローカル・メモリを備える送信ノード及び受信プロセスを実行してローカル・メモリを備える受信ノードを含む分散システムで実行している分散計算の複数のプロセスについてチェックポイントを作成するため、分散システムを動作させる方法であって、
各々のメッセージを相互接続ネットワークへ送信する前に、送信プロセスによって送信された複数のメッセージの各々を、送信ノードのローカル・メモリに記憶されたローカル・ログへコミットするステップと、
各々のメッセージを受信プロセスへ渡すように動作可能な受信ノードで実行しているチェックポイント・ライブラリによって各々のメッセージを受信するステップと、
各々のメッセージを受信プロセスへ渡す前に、送信ノードのローカル・ログから各々のメッセージをアンコミットするステップと
を備える方法。
【請求項１３】
ローカル・ログから各々のメッセージをアンコミットするステップが、各々のメッセージの成功した引き渡しを確認するため受信プロセスからの肯定応答を受信した後に起こる、請求項１２に記載の方法。
【請求項１４】
更に、分散システムのためにチェックポイントを作成するステップと、
最後の一貫したチェックポイントから分散計算をリスタートした後、チェックポイントを作成する前に、送信ノードのローカル・ログへコミットされたが続いてアンコミットされなかった各々のメッセージを再送信するステップと
を備える、請求項１２に記載の方法。
【請求項１５】
更に、チェックポイントを作成する前に、受信プロセスによって既に受信されて再送信されたメッセージを廃棄するステップと、
受信ノードによって廃棄されたメッセージを送信プロセスのローカル・ログからアンコミットするステップと
を備える、請求項１４に記載の方法。
【請求項１６】
複数のプロセスを含む第１の分散計算が分散システムで実行されるプリエンプティブ・スケジューリングの方法であって、
ウインドウ型メッセージング・ロギング・プロトコルを使用して第１の分散計算をチェックポイントするステップと、
分散システムによって受信されたプリエンプティブ要求信号に応答して第１の分散計算の実行を停止するステップと、
第１の分散計算の実行を停止した後、分散システムで第２の分散計算の実行を再開するか第２の分散計算を開始するステップと
を備える方法。
【請求項１７】
更に、第１の分散計算の実行を停止した後、分散システムの中で複数のプロセスの１つ以上を移行するステップを備える、請求項１６に記載の方法。
【請求項１８】
次の１つ、即ち分散システムへ結合されたスケジューリング・エンティティからのプリエンプションの要求、又は分散システムの中の計算ノードのユーザからの要求に応答して、プリエンプティブ要求信号が生成される、請求項１６に記載の方法。
【請求項１９】
プリエンプティブ要求信号がソフトウェア・アプリケーションによる指定に応答して生成され、分散システムの計算ノードで実行するチェックポイント・ライブラリについて、及び保存される必要がある状態の量が事前に定義された量よりも少ない分散計算の実行点で起こるチェックポイントについて、前記ソフトウェア・アプリケーションが所定の知識を有する、請求項１６に記載の方法。
【請求項２０】
第１の分散計算のチェックポインティングが複数のチェックポイント区間で周期的に行われ、
分散システムの中でリソースの故障が検出されたことに応答して、プリエンプティブ要求信号が生成され、
リソースの故障が検出されたチェックポイント区間の前の複数のチェックポイント区間の１つで、第１の分散計算のチェックポインティングが行われる、
請求項１６に記載の方法。
【請求項２１】
更に、第２の分散計算の実行を停止し、次に第１の分散計算の実行を再開するステップを備える、請求項１６に記載の方法。
【請求項２２】
第１の分散計算の実行を再開するステップが、スケジューリング・エンティティによる要求に応答する、請求項２１に記載の方法。
【請求項２３】
第１の分散計算のチェックポインティングが、第１の分散計算と同期しないでスケジューリング・エンティティから信号を送信することによって開始され、
分散計算のチェックポインティングが完了した後に、第１の分散計算の実行の停止が行われる、
請求項１６に記載の方法。
【請求項２４】
スケジューリング・エンティティから送信された信号が、真のオペレーティング・システム信号又はバンド外メッセージである、請求項２３に記載の方法。
【請求項２５】
複数の計算ノードを含む分散システムでチェックポイントを記憶する方法であって、複数の計算ノードの各々のために、
計算ノードにおける計算の間にチェックポイント区間で修正されたメモリ領域のリストを含む現在のコミット・リストを維持するステップと、
計算ノードにおける計算を一時停止するステップと、
計算ノードにおける計算を一時停止した後、計算ノードで現在のコミット・リストに含まれるメモリ領域のリストを前のコミット・リストへ移動するステップと、
現在のコミット・リストをクリアするステップと、
チェックポイント区間で修正されたメモリ領域のリストへの書き込みを防止するステップと、
メモリ領域のリストへの書き込みを防止した後、計算ノードで計算を再開してチェックポイントを記憶するステップと
を備える方法。
【請求項２６】
計算ノードで計算を一時停止するステップがプロセス間通信を一時停止するステップを備える、請求項２５に記載の方法。
【請求項２７】
チェックポイントを記憶するステップが、
前のコミット・リストにリストされたメモリ領域の各々をチェックポイント・ファイルへ記憶するステップと、
メモリ領域がチェックポイント・ファイルへ記憶された後、前のコミット・リストからメモリ領域を除去するステップと
を備える、請求項２５に記載の方法。
【請求項２８】
前のコミット・リストにリストされたメモリ領域を記憶するステップが、前のコミット・リストにリストされたメモリ領域を順次に全探索するステップを備える、請求項２７に記載の方法。
【請求項２９】
現在のコミット・リストに含まれるメモリ領域のリストを前のコミット・リストへ移動した後に、チェックポイント区間で修正されたメモリ領域のリストへの書き込み防止が行われる、請求項２５に記載の方法。
【請求項３０】
現在のコミット・リストに含まれるメモリ領域のリストを前のコミット・リストへ移動する前に、チェックポイント区間で修正されたメモリ領域のリストへの書き込み防止が行われる、請求項２５に記載の方法。
【請求項３１】
更に、計算を再開した後に不揮発性記憶装置へチェックポイントを記憶するステップを備える、請求項２５に記載の方法。
【請求項３２】
不揮発性記憶装置が、複数の計算ノードの各々からアクセスできる共有記憶ファシリティである、請求項３１に記載の方法。
【請求項３３】
チェックポイントを記憶するステップが、情報をチェックポイント・ファイルへ記憶するステップを備え、
更に、書き込み防止メモリ領域が前のコミット・リストにあれば、計算ノードの計算が計算ノードの書き込み防止メモリ領域にアクセスしようとする試みに応答して、
書き込み防止メモリ領域をチェックポイント・ファイルへ書き込むステップと、
書き込み防止メモリ領域を前のコミット・リストから除去するステップと
を備える、請求項３１に記載の方法。
【請求項３４】
更に、前のコミット・リストの書き込み防止メモリ領域にアクセスする試みの後で、書き込み防止メモリ領域を現在のコミット・リストへ付加するステップを備える、請求項３３に記載の方法。
【請求項３５】
チェックポイントを記憶するステップが、情報をチェックポイント・ファイルへ記憶するステップを備え、更に、計算ノードの計算が計算ノードの書き込み防止メモリ領域へアクセスしようとする試みに応答して、
チェックポイントの記憶及び計算ノードの計算を中断して、書き込み防止メモリ領域にアクセスする試みが、前のコミット・リストにリストされたメモリ領域を含むか否かを決定するステップと、
アクセスする試みが、前のコミット・リストにリストされたメモリ領域を含まない場合、現在のコミット・リストで修正されたものとして書き込み防止メモリ領域をマークするステップと、
アクセスする試みが、前のコミット・リストにリストされたメモリ領域を含む場合、リストされたメモリ領域をチェックポイント・ファイルへ書き込み、前のコミット・リストからメモリ領域を除去し、現在のコミット・リストで修正されたものとして書き込み防止メモリ領域をマークし、メモリ領域の書き込み防止を除去するステップと
を備える、請求項３１に記載の方法。
【請求項３６】
更に、メモリ領域の書き込み防止を除去した後、チェックポイントの記憶及び計算ノードの計算を再開するステップを備える、請求項３５に記載の方法。
【請求項３７】
書き込み防止メモリ領域が、計算ノードからアドレスできるメモリ領域である、請求項３５に記載の方法。
【請求項３８】
分散システムで分散計算を実行している多くのプロセスの１つとして参加しているプロセスを、分散システムの第１の計算ノードから第２の計算ノードへ移行する方法であって、
ウインドウ型メッセージング・ロギング・プロトコルを使用して分散計算をチェックポイントするステップと、
第１の計算ノードから第２の計算ノードへプロセスを移行するステップと
を備える方法。
【請求項３９】
チェックポインティングが、第１の計算ノードのユーザ・レベルでチェックポイント・ライブラリを実行し、ロギング・プロトコルを実施するためチェックポイント・ライブラリを介して第１の計算ノードで全てのプロセス間通信をリダイレクトするステップを備える、請求項３８に記載の方法。
【請求項４０】
移行するステップが、プロセスを意図した全ての通信を第２の計算ノードへリダイレクトするステップを備える、請求項３９に記載の方法。
【請求項４１】
全ての通信をリダイレクトするステップが、チェックポイント・ライブラリを使用して、第１の計算ノードの複数のハードウェア・アドレスを第２の計算ノードの対応するハードウェア・アドレスへマップするステップを備える、請求項４０に記載の方法。
【請求項４２】
プロセスを移行するステップが、第１の計算ノードでプロセスの実行を中断する第１の計算ノードの故障に応答して実行される、請求項３８に記載の方法。
【請求項４３】
プロセスを移行するステップが、分散計算を実質的に中断させることなく第１の計算ノードを含む１つ以上の計算ノードを分散システムから除去するため、システム管理者からの要求に応答して実行される、請求項３８に記載の方法。
【請求項４４】
１つ以上の計算ノードを除去するステップが、１つ以上の計算ノードへのメンテナンス又はアップグレードを許容するために行われる、請求項４３に記載の方法。
【請求項４５】
更に、分散システムで１つ以上の予備の計算ノードの集合をリザーブするステップを備え、第２の計算ノードが１つ以上の予備の計算ノードの集合の中に含まれる、請求項４３に記載の方法。
【請求項４６】
更に、プリエンプティブ・スケジューリング・アルゴリズムを実行するスケジューリング・エンティティを使用して分散システムのリソースを管理するステップと、
プロセスを移行する前に、第１の計算ノードを異なった分散計算に使用するため、分散計算の実行を停止するステップと、
プロセスを移行するステップが、インテリジェント・スケジューリング・エンティティからの要求に応答して実行されるステップと、
を備える、請求項３８に記載の方法。
【発明の詳細な説明】
【関連出願】
【０００１】
[0001]本願は、（Ｓｒｉｎｉｄｈｉ  ＶａｒａｄａｒａｊａｎによりＴＲＡＮＳＰＡＲＥＮＴ  ＣＨＥＣＫＰＯＩＮＴＩＮＧ  ＡＮＤ  ＭＩＧＲＡＴＩＯＮ  ＯＦ  ＰＡＲＡＬＬＥＬ  ＣＯＤＥＳ  ＯＶＥＲ  ＧＲＩＤ  ＩＮＦＲＡＳＴＲＵＣＴＵＲＥＳと題して）２００３年１１月１７日に出願された米国暫定出願第６０／５２０，２５４号の、３５Ｕ．Ｓ．Ｃ．ｓｅｃ．１１９（ｅ）の利益を主張する非暫定出願である。上記米国暫定出願は、その全体を参照として本明細書に組み込まれる。
【背景】
【０００２】
[0002]本開示は、一般的に、分散コンピューティング・システムに関し、更に具体的には、そのようなシステムで実行される分散計算のチェックポインティングを改善することに関する。
【０００３】
[0003]クラスタ・スーパーコンピューティングは、個々のコンピューティング・ノードを接続して、複雑な問題を解決することができるコンピューティング・リソースを提供する分散システムを作成する常套手段である。これらのノードは、個々のデスクトップ・コンピュータ、サーバ、プロセッサ、又は計算の個々のインスタンスをホストすることができる類似のマシンであってもよい。これらのノードは、非限定的に、プロセッサ、揮発性メモリ（ＲＡＭ）、磁気記憶ドライブ、メインボード、ネットワーク・インタフェース・カードなどを含むハードウェア・コンポーネントから組み立てられる。最近、ＨＰＣ（ハイ・パフォーマンス・コンピューティング）社会において、より従来の特別注文のスーパーコンピュータではなく、分散システムを利用する傾向が存在する。この動きは、高速ネットワーク・インターコネクト（例えば、Ｍｙｒｉｎｅｔ、Ｑｕａｄｒｉｃｓ、及びＩｎｆｉｎｉｂａｎｄ）の比較的最近の利用可能性によって大きく動機づけられる。高速ネットワーク・インターコネクトは、分散システムが、コストの何分の一かで、従来の特別注文スーパーコンピュータで観察される効率レベルと同様の効率レベルへ達することを可能にする。
【０００４】
[0004]このようなシステムは、依然として、システムの信頼性が比較的劣っているという大きな欠点を有する。例えば、平均の個々のコンピューティング・ノードＣが信頼性ｘを有すると仮定すると、ｘは、Ｃを構成するハードウェア・コンポーネントはいずれも、所与の１日では故障しない確率である。多くの場合、ｘは非常に高い確率、おそらく９９．９％となる。これは、通常の消費者には優れた信頼性を表し、消費者は、１つのコンポーネントについて、ほぼ一年に１回メンテナンスを実行することに問題を有しない。しかし、分散システムの中の１つのノードＣｉが故障する確率に関して、どのようにｘが機能するかを正確に検査するとき当惑が生じる。ｎ個のノードから成るグループの中で、ノードＣｉが故障する確率Ｐは、Ｐ＝ｎ（１−ｘ）＝ｎ（１−０．９９９）＝ｎ（０．００１）によって与えられる。
【０００５】
[0005]ｎが増加するにつれて、所与の一日に故障するノードの確率は直線的に増加する。実際、大きな分散システムでは異常なコンポーネント数ではない１０００にｎが達すると、１日当たり最少で１つのノードが故障することがほぼ確かである。この信頼性の欠如は、不完全なシステム・ソフトウェアによって追加のノード故障が生じるという事実によって更に悪化する。故障したノードを利用していた分散計算は、リスタートされなければならない。大きな分散システムを利用するＨＰＣアプリケーションの多くは、完了するのに数日、数週間、更には数ヶ月を必要とし、分散計算が何とか完了する前に、幾つかの試行の失敗が必要となる。その結果、故障に耐えることができない分散システムは、真に大規模なスーパーコンピューティングには使用できない。
【０００６】
[0006]分散計算の状態を保存して、故障が解消した後に、その状態から分散計算をリスタートさせることのできる方法が存在すれば、その方法と分散システムとの組み合わせは、従来のスーパーコンピュータの信頼性を有するコンピューティング・リソースをコストの何分の一かで実施する。そのような方法を提供する多くの試みが存在した。それらのほとんど全ては、２つの抽象的分類の１つに入る。即ち、チェックポイントをベースとしたプロトコル及びログをベースとしたプロトコルである。チェックポイントをベースとしたプロトコル及びログをベースとしたプロトコルの包括的概論は、Ｅ．Ｎ．（Ｍｏｏｔａｚ）  Ｅｌｎｏｚａｈｙ，Ｌｏｒｅｎｚｏ  Ａｌｖｉｓｉ，Ｙｉ−Ｍｉｎ  Ｗａｎｇ，ａｎｄ  Ｄａｖｉｄ  Ｂ．Ｊｏｈｎｓｏｎ．Ａ  Ｓｕｒｖｅｙ  ｏｆ  Ｒｏｌｌｂａｃｋ−Ｒｅｃｏｖｅｒｙ  Ｐｒｏｔｏｃｏｌｓ  ｉｎ  Ｍｅｓｓａｇｅ−Ｐａｓｓｉｎｇ  Ｓｙｓｔｅｍｓ．ＡＣＭ  Ｃｏｍｐｕｔ．Ｓｕｒｖ．，３４（３）：  ３７５−４０８，２００２から入手可能である。この文献は参照として本明細書に組み込まれる。
【０００７】
[0007]単一の非分散計算の状態を「チェックポイント」又は記録する要件は、単純であり周知されている。それは、計算を実現するソフトウェア・プロセスの状態（例えば、グローバルなデータ、スタック、ヒープ、マップド・メモリ、及びプロセッサ・コンテキスト）を、或る形式の永続記憶装置へ単純に記録することを含む。永続記憶装置へ保存されたこのデータは、「チェックポイント」として知られている。後の時点で、チェックポイントは安定した記憶装置から読み出され、プロセスによってロードされ、その後で、保存された状態の中の実行点から計算がトランスペアレントに再開する。長時間実行の計算を周期的にチェックポイントすることは、故障に対する耐久性を実現する。一度故障が解消すると、計算はその最も近時のチェックポイントからリスタート可能である。この方法を利用すれば、喪失される計算部分は、最も近時のチェックポイントと故障との間の区間で起こった計算部分だけである。
【０００８】
[0008]しかし、この同じ方法を分散計算に応用しようと試みるとき、困難は一層大きくなる。分散計算は、計算の幾つかのインスタンスが協力して働き、単一の問題を解決する計算である。計算又は「プロセス」の各々のインスタンスは、通常、個々のＯＳプロセス、又はＯＳプロセスの内部の実行スレッドとして実施される。別々のプロセスの間の協力は、交換されるメッセージの形式を取る。これらのメッセージは、相互接続ネットワークを介して交換されるか、共有メモリのアクセス及び修正を介して交換される。
【０００９】
[0009]分散計算のチェックポイントが使用可能であるためには、それがグローバルに一貫した状態を表さなければならない。グローバルに一貫した状態とは、計算の正常な実行過程の間に到達され得る状態である。分散計算をチェックポイントする困難性は、任意の所与の時点で、おそらく多くの「飛行中の」メッセージが、異なったプロセスの間に存在する事実にある。これは捕捉されなければならない状態を通信チャンネルが所有していることを意味する。
【００１０】
[0010]通信チャンネルの両端で２つのプロセス（Ｐｓ及びＰｒ）を含む分散計算を考える。Ｐｓは特定のメッセージｍを送信する前にチェックポイントされ、Ｐｒはｍを受信した後にチェックポイントされる。２つのチェックポイントの集団によって表されるグローバル状態は一貫していない。なぜなら、１つのプロセスは、他のプロセスが送信しなかったメッセージを受信しているからである。この現象は孤立メッセージと呼ばれ、分散計算のチェックポイントがグローバルに一貫している状態を確保するためには、或る協調レベルが個々のプロセスの間に存在しなければならないことを例証している。
【００１１】
[0011]分散計算をチェックポイントする従来の方法は、ほとんど全て、分散スナップショットの方法に基づいている。この方法は、例えば、Ｋ．Ｍａｎｉ  Ｃｈａｎｄｙ  ａｎｄ  Ｌｅｓｌｉｅ  Ｌａｍｐｏｒｔ．Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｎａｐｓｈｏｔｓ：  Ｄｅｔｅｒｍｉｎｉｎｇ  Ｇｌｏｂａｌ  Ｓｔａｔｅｓ  ｏｆ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ．ＡＣＭ  Ｔｒａｎｓ．Ｃｏｍｐｕｔ．Ｓｙｓｔ．，３（１）：  ６３−７５，１９８５で説明される。この文献は参照として本明細書に組み込まれる。この方法は、「マーカ」メッセージの使用によって調整を達成するグローバル状態検出メカニズムである。それは、分散システムの通信チャンネルが信頼できるＦＩＦＯキュー（先入れ先出し待ち行列）であり、１つのプロセスから他のプロセスへ送信された全てのメッセージが順序どおりに誤りなく受信されることを上記キューが保証するという基本仮定に依存している。そのような分散計算における１つのプロセスが、グローバル状態（これはチェックポイントとして記録され得る）を検出したいと望むとき、そのプロセスはその全ての通信チャンネルでマーカ・メッセージを送信し、そのローカル状態を即時に記録する。通信チャンネルの他の端にある各々のプロセスはマーカ・メッセージを受信し、そのローカル状態を記録する。次に、プロセスは、マーカが受信された通信チャンネルを除く各々の通信チャンネルでマーカ・メッセージを転送する。これらのマーカ・メッセージは、分散システムの全体へ伝播し、個々のプロセスのチェックポインティングを調整して、全ての個々のチェックポイントの集団が、グローバルに一貫した状態と等しくなるようにする。
【００１２】
[0012]この調整がどのようにして達成されるかを理解するため、２つのプロセス及びそれらを接続する１つの信頼できるＦＩＦＯ通信チャンネルを含む分散システムを再び考える。２つのプロセスの１つであるＰｓは、通信チャンネルを横切ってマーカ・メッセージを送信し、そのローカル状態を記録することによってチェックポイントを開始する。受信プロセスＰｒは、マーカ・メッセージを受信すると、直ちにそのローカル状態を保存する。Ｐｒは、Ｐｓがチェックポイントを取る前に送信された全てのメッセージを受信したことを保証する。更に、この保証は、Ｐｓがチェックポイントした後にＰｓによって送信されたメッセージをＰｒが受信する前に、Ｐｒ自身のチェックポイントが取られたことを保証する。結果として、２つのプロセスが、各々の状態を保存するとき、未だ受信されないメッセージは送信されず、未だ送信されないメッセージは受信されない。実際には、マーカ・メッセージはネットワークから全てのメッセージを「一気に消去する」か「排出し」、記録されなければならない分散計算の状態を個々のプロセスの状態に限定する。これはリスタートのとき非一貫性が生じるのを妨げる。
【００１３】
[0013]ＬＡＭ／ＭＰＩメッセージ・パッシング・ライブラリは、分散スナップショットを利用して、Ｂｅｒｋｅｌｅｙ  Ｌｉｎｕｘ  Ｃｈｅｃｋｐｏｉｎｔ  Ｒｅｓｔａｒｔ（ＢＬＣＲ）で取られた個々のプロセス・チェックポイントを調整する１つのよく知られた通信ミドルウェア実施方法である。ＢＬＣＲは、単一プロセス・カーネル・ベースのチェックポイント／リスタート・システムである。ＬＡＭ／ＭＰＩメッセージ・パッシング・ライブラリは、Ｇｒｅｇ  Ｂｕｒｎｓ，Ｒａｊａ  Ｄａｏｕｄ，ａｎｄ  Ｊａｍｅｓ  Ｖａｉｇｌ．ＬＡＭ：  Ａｎ  Ｏｐｅｎ  Ｃｌｕｓｔｅｒ  Ｅｎｖｉｒｏｎｍｅｎｔ  ｆｏｒ  ＭＰＩ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｓｕｐｅｒｃｏｍｐｕｔｉｎｇ  Ｓｙｍｐｏｓｉｕｍ，ｐａｇｅｓ  ３７９−３８６，１９９４及びＪｅｆｆｒｅｙ  Ｍ．Ｓｑｕｙｒｅｓ  ａｎｄ  Ａｎｄｒｅｗ  Ｌｕｍｓｄａｉｎｅ．Ａ  Ｃｏｍｐｏｎｅｎｔ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  ＬＡＭ／ＭＰＩ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ，１０ｔｈ  Ｅｕｒｏｐｅａｎ  ＰＶＭ／ＭＰＩ  Ｕｓｅｒｓ'  Ｇｒｏｕｐ  Ｍｅｅｔｉｎｇ，ｎｕｍｂｅｒ  ２８４０  ｉｎ  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，ｐａｇｅｓ  ３７９−３８７，Ｖｅｎｉｃｅ，Ｉｔａｌｙ，Ｓｅｐｔｅｍｂｅｒ／Ｏｃｔｏｂｅｒ  ２００３  （Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ）でさらに説明されている。これら文献の各々は、参照として本明細書に組み込まれる。ＢＬＣＲは、Ｊ．Ｄｕｅｌｌ，Ｐ．Ｈａｒｇｒｏｖｅ，ａｎｄ  Ｅ．Ｒｏｍａｎ．Ｔｈｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ  ｏｆ  Ｂｅｒｋｅｌｅｙ  Ｌａｂ'ｓ  Ｌｉｎｕｘ  Ｃｈｅｃｋｐｏｉｎｔ／Ｒｅｓｔａｒｔ，２００２で更に詳細に説明される。この文献は、参照として本明細書に組み込まれる。ＬＡＭライブラリが分散計算の状態を記録したいと望むとき、それはマーカ・パケットを利用して全てのメッセージをネットワークから排出し、全ての通信チャンネルを遮断し、ＯＳから状態を除去し、ＢＬＣＲを利用して、各々の個々のプロセスのローカル状態をチェックポイントする。上記のことは、更に、Ｓｒｉｒａｍ．Ｓａｎｋａｒａｎ，Ｊｅｆｆｒｅｙ  Ｍ．Ｓｑｕｙｒｅｓ，Ｂｒｉａｎ  Ｂａｒｒｅｔｔ，Ａｎｄｒｅｗ  Ｌｕｍｓｄａｉｎｅ，Ｊａｓｏｎ  Ｄｕｅｌｌ，Ｐａｕｌ  Ｈａｒｇｒｏｖｅ，ａｎｄ  Ｅｒｉｃ  Ｒｏｍａｎ．Ｔｈｅ  ＬＡＭ／ＭＰＩ  ｃｈｅｃｋｐｏｉｎｔ／ｒｅｓｔａｒｔ  ｆｒａｍｅｗｏｒｋ：  Ｓｙｓｔｅｍ−Ｉｎｉｔｉａｔｅｄ  Ｃｈｅｃｋｐｏｉｎｔｉｎｇ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ，ＬＡＣＳＩ  Ｓｙｍｐｏｓｉｕｍ，Ｓａｎｔｅ  Ｆｅ，Ｎｅｗ  Ｍｅｘｉｃｏ，ＵＳＡ，Ｏｃｔｏｂｅｒ  ２００３で説明されている。この文献は参照として本明細書に組み込まれる。次に、ＬＡＭライブラリは、全ての通信チャンネルを再び開いて計算を続行する。
【００１４】
[0014]したがって、分散スナップショット法に基づく分散チェックポイント／リスタートの現在の実施方法によって共有される幾つかの難点及び短所が存在する。大部分の現在の方法は、下記の欠点の１つ以上を有する。
１．現在の実施方法は全て遮断的である。グローバル状態の検出の間、及びそのグローバル状態を二次記憶装置へ記録する間、計算は進行することができない。この結果として、計算時間の喪失を生じ、次にこれは分散システムの効率性を低減する。
２．現在の実施方法はトランスペアレントでない。実施方法は、ユーザ・レベルのアプリケーション自身、チェックポインティング以外の一次目的を有する幾つかのミドルウェア、又はオペレーティング・システム（ＯＳ）での知識を必要とする。現在の実施方法は、分散システムの全てのレベルへ完全にトランスペアレントな独立型エンティティとして機能しない。
３．現在の実施方法は移行を許さない。分散システムの個々のノードが故障すると、ミドルウェア層への修正なしに、そのノードが実行していたプロセスを、異なった非故障ノードへ移行することはできない。その結果、故障ノードが手作業で修復されるか、オペレータによって置換されるまで、分散システムは計算を再開することができない。
４．現在の実施方法は、チェックポイントの真の非同期的誘導を許さない。多くの実施方法は、或る動作の間、例えば、通信に関連する多くの動作の間、チェックポイントが取られることを許さない。これらの実施方法は、保護された動作が終了するまで、チェックポイント動作を遅延させる必要がある。
【００１５】
[0015]本開示をより完全に理解するため、ここで下記の図面を参照する。図面において、同様の参照番号は図面の全体で類似のアイテムを参照する。本明細書で記述される例は具体的な実施形態を示し、そのような例は、限定として解釈されることを決して意図されない。
【詳細な説明】
【００１６】
[0016]下記の説明及び図面は、本明細書で説明されるシステム及び方法を当業者に実施させるのに十分な具体的実施形態を示す。他の実施形態は、構造的、論理的、プロセス的及び他の変更を組み込んでもよい。例は、可能な変形を類型化するだけである。個々のコンポーネント及び機能は、明白に要求されない限り任意選択的であり、動作の順序は変更されてもよい。幾つかの実施形態の一部分及び特徴は、他の実施形態の一部分及び特徴によって包含又は置換されてもよい。
【００１７】
[0017]本システム及び下記の方法の様々な実施形態を実施する要素は、幾つかの場合には、アーキテクチャ・レベルで説明される。多くの要素は、周知の構造を使用して構成されてもよい。本明細書の機能及びプロセスは、本明細書で説明される機能及びプロセスを当業者が実施できるように説明される。
【００１８】
[0018]下記で説明される処理は、分散処理プラットフォームによって実行されてもよい。更に、そのような処理及び機能は、特殊用途のハードウェアの形式又は汎用又はネットワーク・プロセッサによって実行されるソフトウェア又はファームウェアの形式で実施可能である。そのような処理で取り扱われたデータ、又はそのような処理の結果として作成されたデータは、当技術分野で通常行われるように、任意のタイプのメモリに記憶可能である。例として、そのようなデータは、一時的メモリ、例えば所与のコンピュータ・システム又はサブシステムのＲＡＭに記憶されてもよい。これに加えて、又は代替として、そのようなデータは、長期記憶デバイス、例えば、磁気ディスク、再書き込み可能光ディスクなどに記憶されてもよい。本明細書の開示のためには、コンピュータ読み取り可能メディアは任意の形態のデータ記憶メカニズムを含んでもよい。その中には、既存のメモリ・テクノロジ及びそのような構造及びそのようなデータを表すハードウェア又は回路が含まれる。
【００１９】
[0019]更に理解すべきは、本システム及び方法の手法は、多様なテクノロジを使用して実施されてもよいことである。例えば、本明細書で説明される方法は、プログラム可能マイクロプロセッサで実行しているソフトウェアで実施されるか、マイクロプロセッサの組み合わせ又は他の特殊設計アプリケーション特定集積回路、プログラム可能論理デバイス、又はこれらの様々な組み合わせを利用するハードウェアで実施されてもよい。特に、本明細書で説明される方法は、記憶メディア、例えば、搬送波、ディスク・ドライブ、又は他のコンピュータ読み取り可能メディアに存在する一連のコンピュータ実行可能命令によって実施されてもよい。
【００２０】
[0020]分散システムのノードの或るサブセットで実行している非インタラクティブ分散計算のグローバル状態をトランスペアレント及び非遮断的に検出して個々のプロセスの移行を可能にする本明細書の方法は、分散システムと組み合わせられて、特別注文のハードウェアから構築された伝統的スーパーコンピュータの信頼性に匹敵する信頼性を提供するコンピューティング・リソースを作成することができる。本明細書の開示は方法及び装置を提供するが、これらの方法及び装置は、分散チェックポイントの間、通信チャンネルの状態の一貫性を保証し、計算を遮断することなく、記録された状態をコミットし、個々のプロセスのローカル・チェックポインティングを調整するために使用されてもよく、分散システムは、計算効率の最小限の損失を要するだけで、手作業による介入又はシステムの休止なしに故障から回復するようにされる。開示は、分散計算の過程で個々のプロセスの移行が可能になるように、これらの方法を提供する。更に、実施形態はライブラリの形式を取ってもよく、レガシー・ソフトウェアの修正なしに、レガシーのアプリケーション、ミドルウェア、及びＯＳと上記ライブラリとを、（例えば、リンキングを介して）トランスペアレントに介在させることができる。
【００２１】
[0021]例示的な実施形態において、分散システムはｎ個のコンピュータを含み、各々のコンピュータは、ネットワークによって相互接続されたｐ個のプロセッサを所有する。非インタラクティブ分散計算は、２つからｎ個までのコンピュータにおいてスタートされ、各々のプロセッサは個々のプロセスをホストする。分散計算の過程中に、プロセスはメッセージの交換を介してインタラクトする。この通信は、実行しているユーザ・レベルのアプリケーションによって実施されてもよいが、最も大きな可能性としては、ユーザ・レベルのアプリケーションとリンクされるミドルウェア・ライブラリ（例えば、ＭＰＩＣＨ、ＭＶＡＰＩＣＨ、ＬＡＭ／ＭＰＩ）によって実施される。
【００２２】
[0022]図２で示されるように、「チェックポイント・ライブラリ」２０２は、プロセス（例えば、ユーザ・レベル分散アプリケーション２１０及びミドルウェア・ライブラリ２０８）の「下」及びオペレーティング・システム（ＯＳ）２０６の「上」にトランスペアレントに介在し、全てのプロセス間メッセージ、ダイナミック・メモリ割り付け、二次記憶アクセス、及び信号処理はチェックポイント・ライブラリ２０２を介して処理される。
【００２３】
[0023]チェックポイント・ライブラリの中で実施されたウインドウ型ロギング・プロトコルは、プロセスＰｓによって送信されたｉ個のメッセージの各々のメッセージｍｉを、送信のためにＯＳへ渡す前に、ローカル・ログへコミット（即ち、挿入）する。メッセージは、計算のために上のレイヤへ渡される前に、受信プロセスＰｒに介在されたチェックポイント・ライブラリによってログからアンコミット（即ち、除去）される。当業者は、本明細書の実施形態で説明されるロギング方法が、オンライン・プロトコル（即ち、プロトコルは将来の入力の知識を必要としない）として実施されることを認識する。しかし、他の実施形態においては、非オンライン・プロトコルを使用することができる。
【００２４】
[0024]本実施形態において、このアンコミットは、ｍｉの成功した引き渡しを確認するＰｒからＰｓへの第２の小さなメッセージｍｉａの形式を取ってもよい。故障及び続くリスタートの場合、各々のプロセスに介在するチェックポイント・ライブラリは、チェックポイントが取られたときログの中にコミットされた各々のｍｉを再送信又は「再生」する。チェックポイントの前にｍｉがＰｒによって既に受信されていれば、それは上のレイヤへ通知することなく廃棄され、Ｐｓのログからアンコミットされる。ｍｉが受信されていなければ、それは正常なメッセージとして処理される。ウインドウ型ロギング・プロトコルは、通信チャンネルの状態の非一貫性を妨げる。
【００２５】
[0025]留意すべきは、本実施形態が、ログの中のメッセージのみが再生される点で、従来のメッセージ・ロギングと顕著に異なることである。メッセージ・ログは、意図された受信者によって受信されていないメッセージだけを含む。受信者によって成功裏に受信され、そのように肯定応答された全てのメッセージは、メッセージ・ログからアンコミットされる。
【００２６】
[0026]実行の過程中に、全てのダイナミック・メモリ割り付け及び後続のメモリ修正は、フロント・バッファ及びバック・バッファから構成されるダブルバッファド・コミット・リストを使用して、チェックポイント・ライブラリによって記録されてもよい。アプリケーション・プロセスの状態が記録されるべきであるとき、フロント及びバックのバッファは交換され、全ての修正されたメモリ領域は修正から保護される。前のコミット・リストにリストされた修正済みメモリ領域の全てを、不揮発性記憶装置、例えば、共有二次記憶ファシリティ（図１を参照）へ記録するため、個別の実行スレッド（即ち、状態記録スレッド）が生成される。リストは順次に全探索され、その間に計算は同時に進行することができる。
【００２７】
[0027]留意すべきは、本実施形態において、ローカルの二次記憶装置１１４（図１を参照）は、チェックポイント・ファイルを不揮発性記憶装置へ書き込むことに関与しないことである。その代わりに、全てのチェックポイント・ファイルが共有二次記憶ファシリティ１１０へ記憶される。しかし、他の実施形態では、他の不揮発性記憶のアプローチが使用されてもよい。これはローカル二次記憶装置１１４が関与することを含む。
【００２８】
[0028]アプリケーション・プロセスが、前のコミット・リストにリストされたメモリ領域を修正しようと試みる場合、それは状態記録スレッドによって検出される。スレッドはその順序正しい全探索を中断し、問題の領域を記録し、計算が進行できるようにする。領域は現在のコミット・リストにリストされ、新しい修正が次のチェックポイントの中に確実に記録されるようにする。この非遮断、書き込み時コピー、順序外のローカル・チェックポイント・コミット方法は、グローバル同期動作からローカル動作へチェックポイントを縮小する。それは、二次記憶システムの書き込みアクセス・スピードによって拘束されるコミット動作ではなく、ＯＳメモリ保護メカニズムによって拘束されるコミット動作へ、コミット動作を変換する。
【００２９】
[0029]グローバルに一貫した状態を確保するように、分散計算のチェックポイントを調整する新規な方法を呈示するため、上記の２つの新規なメカニズムが例示的な実施形態に関して説明される。この新規な方法は、非遮断的であり、分散計算の全てのレベルでトランスペアレントであり、プロセスが任意のノードへ移行されるように実行される。
【００３０】
[0030]調整は、任意のプロセスから、分散計算を構成する全ての他のプロセスへ「チェックポイント・コマンド」をブロードキャストすることによって開始可能である。状態が記録される計算区間又は「エポック」を識別するため、数値ｉｄが使用されてもよい。こうして、個々のプロセス各々は、プロセス間通信を停止し、その状態をコミットし（エポックｉｄによってマークされる）、プロセス間通信の障壁に入る。障壁から出た後、新しい区間の一部分としてプロセス間通信が再開する。当業者によって認識されるように、障壁は分散計算に参加する異なったプロセスを同期させる方法であり、障壁に参加する他のプロセスが障壁に到達するまで、プロセスを保持するために使用される並列動作である。
【００３１】
[0031]上記で説明した方法は、個々のノードから構成された分散システムと組み合わせられて、従来の特別注文スーパーコンピュータと同じ信頼性を有するスーパーコンピューティング・リソースを提供する。それは、個々のプロセスが、故障した計算ノードから適正に機能している計算ノードへ移行することを可能にし、分散計算が、分散システムを構成する個々のノードのメカニカル又はソフトウェアの故障によって妨害されないで進行することを可能にする。それは、計算の停止、分散計算の幾つかのレベルの修正（例えば、ユーザ・アプリケーション、通信ミドルウェア、及びＯＳ）、及び故障した計算をリスタートするための手作業による介入を必要とする従来の方法と対比して、非遮断的かつ分散計算の全てのレベルへ完全にトランスペアレントであるような方法で、この信頼性を提供する。
【００３２】
[0032]１つの実施形態において、実行時システムは、分散システムの実行の信頼性を向上させ、そのダイナミック（動的）な制御を可能にする幾つかの重要なイネーブル技術を提供する。具体的には、本実施形態の主な特徴の幾つかは、次のとおりである。
１．送信者のコミット及び受信者のアンコミットを利用して、チェックポイントが取られるとき通信チャンネルの状態が一貫して維持される状態を保証するウインドウ型メッセージ・ロギング・メカニズム。
２．個別の実行スレッドで実行することができ、チェックポイントが安定記憶装置へ保存されている間、計算が妨げらないで進行することを可能にする非遮断的、順序外、書き込み時コピー・プロトコル。これは、グローバル同期動作からローカル一時停止へチェックポイント動作を縮小し、二次記憶システムのアクセス・スピードではなくＯＳのメモリ保護メカニズムにコミット段階の下限を置く。
３．ローカル・チェックポイントを調整してグローバル一貫性を保証する新規なグローバル状態検出方法。これは、計算の遮断を必要とせず、分散システムの全てのレベルまでトランスペアレントであるような方法で達成される。
【００３３】
[0033]実施形態は、下記の例示的分散コンピューティング・システムで示される。しかし、本明細書で説明されるシステム及び方法は、特定タイプの分散システムでの使用に限定されず、従来の特別注文スーパーコンピューティング環境で経験されたレベルへ信頼性を向上させることが望まれる分散コンピューティング環境又はアプリケーションへ、一般的に応用可能であることを理解すべきである。
【００３４】
[0034]本明細書で使用される「分散システム」という用語は、２つ以上のコンポーネント、コンピュータ、マシン、又は他のタイプのプロセッサを含む任意のシステムを含むことを意図される。分散システムの中の各々のコンピュータは、例えば、対称型マルチプロセッサ（ＳＭＰ）であってもよく、複数のプロセッサを含んでもよい。「分散計算」という用語は、計算タスクを達成するため協力して働いている２つ以上のプロセスから成る計算のインスタンスを含むことを意図している。本明細書で使用される「プロセス」という用語は、分散システムの中の１つ以上のコンピュータ又は他のタイプのプロセッサで実行する任意のタイプのプログラム、命令、コードなどを含むことを意図される。
【００３５】
[0035]分散計算を構成するプロセスは、相互接続ネットワーク上の明白なメッセージ交換、全てのプロセスによって共有されるメモリ領域のアクセス及び修正、又はこれらの幾つかの組み合わせによって協力してもよい。現在の実施形態において、全てのプロセスは個別のプロセッサの上で同時に実行し、各々のプロセスはＯＳプロセスとして示される。しかし、本明細書で説明されるシステム及び方法は、そのような環境に限定されず、計算のインスタンスが実現される方法（例えば、ユーザ・レベルのスレッド、カーネル・レベルのスレッド、及びＯＳプロセス）に関係なく利用されてもよい。
【００３６】
[0036]本明細書で使用される「ローカル・チェックポイント」という用語は、本明細書では、分散計算の実行に貢献する単一のプロセスの状態を十分に特徴付ける情報の集合の記録を意味するために使用される。「チェックポイント」という用語は、本明細書ではローカル・チェックポイントの集団的集合を意味するために使用され、この集団的集合は分散計算のグローバル一貫状態を表す。「チェックポイント区間」という用語は、２つのチェックポイント動作の間で起こる正常な計算及び通信の期間を意味する。「ヘッド・ノード」という用語は、分散システムの中にある特別のコンポーネントであって、実行のためにユーザによって分散計算をサブミットされ、中央モニタリング及びリソース管理ソフトウェアを実行するコンポーネントを意味する。「計算ノード」という用語は、ｎ個のプロセッサを含み（ここで、ｎ≧１）、したがってｎ個のプロセスをホストする分散システムの中の１つのノードを意味する。
【００３７】
[0037]分散計算が従来の分散システムで開始されるとき、個々のプロセスの実行は計算ノードのサブセットでスタートする。ハードウェア又はシステム・ソフトウェアの故障がそれらの計算ノードの１つで起こると、分散計算は停止する。大部分の従来の分散システムはチェックポインティング・メカニズムを提供せず、分散計算は初期の実行点からリスタートしなければならない。分散システムが分散スナップショットベースのメカニズムを利用して分散計算をチェックポイントする場合、故障したノードは、分散計算のリスタートに先立って、手作業の検査及びメンテナンスによって修復されなければならない。
【００３８】
[0038]計算ノードのモニタリング及びメンテナンスを自動化する複雑なシステム・ソフトウェアが存在する場合でも、ハードウェアの故障は、決して少なくないノード故障についてシステム管理者の手作業による介入を必要とする。分散計算は、それが本来実行していた計算ノードのサブセットで、最も近時のチェックポイントによって記録された実行状態から再開する。分散スナップショット・ベースのメカニズムによって取られたローカル・チェックポイントは、ＯＳ及びミドルウェアの中に維持された状態を捕捉することなく通信チャネルを一気に消去し、したがって移行を許さない。オープン通信チャンネルは、特定のネットワーク又はハードウェア・レベル・アドレス（例えば、ＩＰアドレス又はＩｎｆｉｎｉＢａｎｄ接続状態）へ結合されるソケット又は他の同等のシステム・レベル・インタフェースに依存する。
【００３９】
[0039]要件を更に調べると、大多数の従来の分散システムで使用される分散スナップショット・ベースのチェックポインティング・メカニズムには、顕著な欠点があることが明らかになる。大部分の分散システムは、実際に多数の分散計算を同時に実行し、各々の分散計算は計算ノードのサブセットを利用する。計算ノードの１つが故障すると、それが関与していた分散計算は停止し、サブセットの中の適正に機能していた残りの計算ノードはアイドルになる。分散スナップショット・ベースのチェックポインティング・システムにおいて、これらの計算ノードは、故障したノードが修復され、分散計算が初めに実行していた計算ノードのサブセットで分散計算が実行を再開するまで、アイドルのままでなければならない。サブセットの中で故障していないノードがアイドルのままである時間の量が、リソースを浪費し、分散システムの効率に悪影響を与える。
【００４０】
[0040]代替の方法としては、故障ノードが保守されているのを待っている間、非故障計算ノードを他の分散計算に参加させることである。残念ながら、現在では分裂した元のノードのサブセットが同時に利用可能となって、故障した分散計算を再開するために必要な時間の量に上限は存在しない。そのような環境において、故障した分散計算が完了する保証はない。対照的に、本実施形態は、分散システムの所与の時点において、全ての計算ノードを正確に利用する分散計算の組み合わせがないため、少数の計算ノードがアイドルになる高い確率を利用することができる。結果として、分散計算にアクティブに参加している計算ノードの１つが故障すれば、その計算ノードがホストしたプロセスをアイドルの「優先予備」計算ノードの１つへ移行することができる。更に、システム管理者が計算ノードの集合を明示的にリザーブして、優先予備ノードが常に利用可能であることを保証してもよい。そうすれば、分散計算は妨げられることなく続行することができる。分散システムが、計算ノードの全集合を消費する単一の分散計算の実行に使用される場合、フェイルオーバーを目的として少数のノードをリザーブすることが管理者に残される。この方法による効率の損失は、従来の分散システムの故障に起因する損失よりも、はるかに小さいことを示すことができる。
【００４１】
[0041]本実施形態は、チェックポイントの集団がグローバルに一貫し、ローカル・チェックポイントが移行可能になるような方法で、分散計算のグローバル状態を検出し、計算に参加している各々のプロセスのローカル・チェックポイントをトランスペアレントに獲得する方法を提供する。本実施形態は、ローカル・チェックポイントの過程中に計算を進行させる新規な順序外の書き込み時コピー・メカニズムを使用して、ローカル・チェックポイントを記録する。本実施形態は、分散計算がチェックポイントされ、下記の理由のいずれか又は全てのために、プロセスの幾つかのサブセットを移行させるように構成されてもよい。その理由とは、（１）ハードウェア故障、システム・ソフトウェア・エラー、又は計算ノード上で実行しているプロセスを中断する他の遊歴故障に起因して、計算ノードの故障が起こり、（２）システム管理者が、起こっている分散計算を中断させることなく、メンテナンス又はアップグレードのために分散システムから或る数の計算ノードを取り外すことを望み、（３）分散システムのリソースを管理し、プリエンプティブ・スケジューリング・アルゴリズムを利用しているインテリジェント・スケジューリング・エンティティが、分散実行を一時的に停止して、その計算ノードを他の計算に使用することを望み、又は（４）本実施形態の先進的知識を使用して書かれたアプリケーション・ソフトウェアが、保存される必要がある状態の量が最小になる実行点で（例えば、時間ステップの終わりで）、チェックポイントを指定する（例えば、ユーザ指令チェックポイント）ことである。
【００４２】
[0042]分散アプリケーションがプリエンプトされるとき、各々のインスタンスは、進行中の計算とは非同期の信号を送信される。この信号は、真のＯＳ信号であるか、バンド外メッセージであってもよい。信号を受信すると、チェックポイント動作が開始される。一度チェックポイント動作が完了すると、スケジューリング・エンティティ（プリエンプティブ・スケジューリング・アルゴリズムを実行している）はＯＳファシリティを使用して、分散計算を停止又は終了してもよい。次に、スケジューリング・エンティティは、アイドルにされた計算ノードの上で他の計算をインスタンス化することができる。
【００４３】
[0043]図１は、開示の第１の実施形態が実施されてもよい例示的分散計算システム１００を示す。システム１００は計算ノード１０４（Ｃ１、Ｃ２、．．．、Ｃｎとして示される）のグループを含む。計算ノード１０４は、相互接続ネットワーク１０２の或る形式を介してヘッド・ノード１０６（Ｈとして示される）へ接続され、或る中央リソース管理ソフトウェア１０８（図１ではリソース管理フレームワークとして示される）がヘッド・ノード１０６で実行していてもよい。典型的には、ヘッド・ノード１０６は計算ノードではない。しかし、他の実施形態において、計算ノードは、ヘッド・ノードとして働くように使用されてもよい。
【００４４】
[0044]相互接続ネットワーク１０２は、例えば、インターネットに基づいたネットワークであってもよい。１つ以上のプロセス１２０が、各々の計算ノード１０４の上で実行されてもよい。例えば、プロセスＰ１は計算ノードＣ１で実行し、プロセスＰｎは計算ノードＣｎで実行してもよい。各々のプロセス１２０は、例えば、計算ノード１０４に含まれる１つ以上のプロセッサ（例えば、ＩＮＴＥＬ  ＩＴＡＮＩＵＭマイクロプロセッサ）によって実行されてもよい。
【００４５】
[0045]システムの中の計算ノード１０４は、更に、共有二次記憶ファシリティ１１０（Ｓで示される）へ接続される。共有二次記憶ファシリティ１１０は、例えば、相互接続ネットワーク１０２で利用可能なＮＦＳファイル・システムであるか、より先進的な並列ファイル・システム、例えば、ＬＵＳＴＲＥシステムであってもよい。二次記憶ファシリティに関しては、移行ターゲットとなる計算ノード１０４から同じファイル・システムが見えなければならない。典型的な実施形態において、共有二次記憶ファシリティ１１０は、全ての計算ノード１０４からアクセス可能である。
【００４６】
[0046]各々の計算ノード１０４は、ローカル・メモリ１１２（例えば、ダイナミックＲＡＭ）を含んでもよい。ローカル・メモリ１１２は、例えば、ユーザ・レベル・アプリケーション、通信ミドルウェア、及びオペレーティング・システムを記憶するために使用されてもよく、またローカル二次記憶デバイス１１４（例えば、ハードドライブ）を含んでもよい。ローカル・メモリ１１２は、下記でより詳細に説明するように、本明細書で説明されるチェックポイント方法に関連したメッセージ、バッファ、及びログを記憶するために使用されてもよい。ヘッド・ノード１０６は、更に、ローカル・メモリ１１６及びローカル二次記憶装置１１８を含んでもよい。
【００４７】
[0047]計算ノードＣ１、Ｃ２、．．．、Ｃｎはコンピュータ、ワークステーション、又は他のタイプのプロセッサ、及びこれらの様々な組み合わせであってもよい。例示を目的として、システムで分散計算の要求がＨに到着し、計算ノードのアイドルのサブセットへディスパッチされるものと仮定する。本明細書で説明する新規な方法を使用しないシステムでは、要求を満足させる計算ノードの十分大きなアイドルのサブセットが存在しなければ、要求はリソース管理フレームワークによってＨの上でキュー（待ち行列）とされ、そのようなサブセットを発見できる後の時点で実行される。リソース管理フレームワークは、キューにされた要求を整理し直して、アイドルの計算ノードの数を最少にするように試みてもよいが、一度分散計算が開始されると、それは完了まで実行されなければならない。分散計算は、典型的に非インタラクティブであることを留意すべきである。
【００４８】
[0048]図２を参照すると、ユーザ・レベル・チェックポイント・ライブラリ２０２は、例えば、分散計算を実行するアプリケーション２１０へ静的又は実行時にリンクされる。ミドルウェア２０８も、同じようにアプリケーションへリンクされてもよい。本実施形態は、例えば、キー・システム・ライブラリ呼び出しと同じシグネチャを有する強力な別名のシンボルを提供することによって、ユーザ・レベル・アプリケーション及びミドルウェアとトランスペアレントに統合されてもよい。リンカ／ローダは、チェックポイント・ライブラリを介してシステムコールの実行フローをリダイレクトする。
【００４９】
[0049]図２は、チェックポイント・ライブラリ２０２が、従来の分散システムで見られるアプリケーション２１０／ミドルウェア２０８／ＯＳ２０６のスタックの中へ適合する方法を示す。ユーザ・レベル・チェックポイント・ライブラリ２０２は、ユーザ・レベル・アプリケーション２１０及びミドルウェア２０８から構成されるプロセスの中へトランスペアレントに介在させられ、例えば、リダイレクトされたシステムコールの使用を介して、ユーザ・レベル・アプリケーション及び使用中のミドルウェアの「下」及びＯＳの「上」に存在する。アプリケーション、ミドルウェア、又はＯＳのいずれにおいても、チェックポイント・ライブラリ２０２の存在の認知又は知識は要求されない。分散アプリケーション２１０、ミドルウェア・ライブラリ２０８、チェックポイント・ライブラリ２０２、及びオペレーティング・システム２０６は、例えば、ローカル・メモリ１１２に記憶されてもよい。
【００５０】
[0050]図２において、チェックポイント・ライブラリ２０２は、計算ノードＣｉの上で実行しているプロセスＰｉと関連づけて示される。他のチェックポイント・ライブラリ２０４は、計算ノードＣｊの上で実行しているプロセスＰｊと関連づけられてもよい。典型的な場合、チェックポイント・ライブラリ２０２及び２０４は、最初にロードされたとき、同じライブラリのコピーである。一般的に、各々の計算ノード１０４は、計算ノードに関連づけられたユーザ空間の中にチェックポイント・ライブラリを含む。
【００５１】
[0051]ウインドウ型ロギング・プロトコルは、通信チャンネル及び両端にある２つのプロセスの状態が、チェックポイントの間に一貫している状態を保証するために使用されてもよい。このアプローチは、従来の分散スナップショット・ベースのシステムを使用する人々によって行われる仮定を考えるとき明確ではない。分散スナップショット方法は、全ての通信チャンネルが信頼できるＦＩＦＯキューであることを仮定し、したがってチェックポインティングの前に、キューから状態を排出する。したがって、従来の方法は、ＯＳによって提供された信頼性のある通信フレームワークへ結合されたメッセージング状態を記録せず、メッセージング状態にはハードウェア特定アドレス及び現在の接続バッファが含まれ、したがって移行が妨げられる。
【００５２】
[0052]対照的に、本実施形態は、ＯＳによって提供される全ての通信チャンネルが本来的に信頼性を有しない（例えば、オーダーの引き渡し又は正確性を保証しない）という一般的な動作仮定を使用する。前述したように、アプリケーション又はミドルウェアによって呼び出された全ての通信動作は、チェックポイント・ライブラリへ向けられてもよい。これらの動作は、ＯＳによって提供された通信プリミティブを利用して実行される。ＯＳチャネルは信頼性を有しないと仮定されるから、本実施形態は、ウインドウ型メッセージ・ロギング・プロトコルの使用を介してメッセージの正しい引き渡しを保証する。
【００５３】
[0053]図３は、ウインドウ型メッセージ・ロギング・プロトコルによって使用される方法のフローチャートを提供する。送信者Ｐｓは、送信の前にローカル・ログへメッセージをコミットする。ローカル・ログは、例えば、ロギング・プロトコルを使用して各々の計算ノードのローカル・メモリ１１２に記憶されてもよい。
【００５４】
[0054]メッセージを受信すると、受信者Ｐｒは、短い肯定応答メッセージで返答し、成功した引き渡しをＰｒに通知する。Ｐｒによって取られたこのアクションは、Ｐｓのログからメッセージをアンコミットする。一意の単調に増加するシーケンス番号が各々のメッセージに関連づけられてもよく、間違ったシーケンスで受信されたメッセージはＰｒによって正しく整理し直されてもよい。シーケンス番号によって、更に、受信者は、メッセージが喪失されたこと（例えば、受信されたメッセージのシーケンス番号のギャップ）、及び重複メッセージの受信を検出することができる。重複メッセージは廃棄され（理由は、それらが既に受信されて処理されたことによる）、喪失メッセージは再送信を要求することによって処理されてもよい。送信者ログの中にリストされるメッセージは、「未解決」メッセージとして知られる。
【００５５】
[0055]ログに有限バッファの使用を許すため、任意の一時点で許される未解決メッセージの数に制限が置かれてもよい。この制限に到達すれば、最も古い未解決メッセージが肯定応答されるまで、Ｐｓはメッセージの送信を中止する。未解決であることを許されるシーケンス番号の範囲は、「送信ウインドウ」として知られ、メッセージが送信及び受信されるにつれて、送信ウインドウは、本質的に、アプリケーション及びミドルウェアが送信を要求するメッセージの全集合にわたってスライドする。
【００５６】
[0056]本実施形態は、上記の方法で通信を実施し、前述したように、ＯＳに対するＰｓのインタフェースでスタートしてＰｒの対応するインタフェースで終わる通信チャンネルが信頼性を有しないものと仮定する。そのような環境において、メッセージの喪失、順序外の引き渡し、又は重複がＯＳの故障にさえも起因するのか、相互接続ネットワークの故障に起因するのか、通信チャンネルのリモート端におけるノードのＯＳの故障に起因するのか、又はそのリモート端で実行しているプロセスの故障に起因するのかを決定することは、一般的に不可能であることに留意すべきである。したがって、本実施形態は、ＯＳの中の状態又は通信ファブリックを飛行中の状態をチェックポイントしない。更に、本実施形態は、従来のシステムが行うように、チェックポインティングの前に、ＯＳ及び通信ファブリックから、調整されたメッセージの「一気消去」を行うことに携わらない。むしろ、本実施形態のユーザ・レベル・ライブラリによって実施されたウインドウ型メッセージ・ロギングは、チェックポイント動作の間に起こるオペレーティング・システム及び相互通信ネットワークの中の状態の喪失を、信頼性を有しないチャネルの上の正規の通信フローで処理されるメッセージ喪失としてマスクする。
【００５７】
[0057]前述したように、通信チャンネルの両端におけるＰｓ及び受信者からのローカル・チェックポイントをグローバルに一貫したチェックポイントへ集団化する場合の妨害要因は、リスタート時に通信チャンネル状態の非一貫性が起こらないようにすることの固有の困難性である。従来の分散システムにおいて、ＰｓがメッセージｍをＰｒへ送信する間、チェックポイントするときに生じる非一貫性は次のとおりである。
１．メッセージｍは、Ｐｓによって取られたローカル・チェックポイントの前に送信されたが、Ｐｒによって取られたローカル・チェックポイントの後で受信された。
２．メッセージｍは、ローカル・チェックポイントがＰｓによって取られた後に送信されたが、Ｐｒによって取られたローカル・チェックポイントの前に受信された。
３．実施形態は、更に、ＰｒからＰｓへの二次肯定応答メッセージｍａを付加するので、Ｐｒがｍａを送信した後にチェックポイントし、Ｐｓが肯定応答を受信する前にチェックポイントするとき、第３の非一貫性の存在が考えられる。
【００５８】
[0058]本明細書で説明される新規なウインドウ型ロギング方法の使用は、上記の故障モードを回避させる。
【００５９】
[0059]第１の故障モードにおいて、Ｐｓは、ｍが送信された前の状態でリスタートされ、正規の実行フローの一部分としてｍを送信する。ｍが既に受信された状態でリスタートされたＰｒはｍを再び受信し、これは一貫性を有しないグローバル状態を生じる。ウインドウ型ロギング・プロトコルは、メッセージが重複していることをｍに関連づけられたシーケンス番号から認識し、それを廃棄することによって、そのような事象の発生を防止する。次に、受信者は、ｍａで返答することによって、Ｐｓのメッセージ・ログからｍをアンコミットする。
【００６０】
[0060]第２の故障モードにおいて、Ｐｓはｍを送信した後の状態でリスタートされ、Ｐｒはｍを受信する前の状態でリスタートされるとき、メッセージｍはＰｒによって決して受信されない。ウインドウ型ロギング・プロトコルは、メッセージの永久的喪失を防止する。ｍは決して受信されないので、Ｐｒは決してｍａを送信せず、Ｐｓのログからｍをアンコミットしない。一定の期間ｔが経過した後、ｍはＰｓで「タイムアウト」となり再送信される。ここで、Ｐｒはｍの第２の送信を受信し、ｍａで返答することによってＰｓのログからｍをアンコミットする。ｔの適切な値は、分散システムによって利用される特定の相互接続ネットワークのバンド幅及びレイテンシーに基づいて設定される。
【００６１】
[0061]第３の故障モードにおいて、Ｐｓがｍａを受信する前の状態でリスタートされ、ｍａが送信された後の状態でＰｒがリスタートされるとき、ｍは決してＰｓのログからアンコミットされない。そのような事象の発生は、ウインドウ型ロギング・プロトコルの使用を介して防止されてもよい。或る期間ｔが経過した後、ｍはＰｓで「タイムアウト」となり再送信される。ここで、Ｐｒはｍの第２の送信を受信し、それが重複していることをシーケンス番号から認識し、ｍａの第２のコピーを送信して、Ｐｓのログからそれをアンコミットする。
【００６２】
[0062]ウインドウ型メッセージ・ロギング・プロトコルは、従来の分散スナップショット・システムに勝る他の基本的利点を提供するために使用されてもよい。本実施形態は、個々のプロセスを異なった計算ノードへトランスペアレントに移行する能力を分散システムに提供する。前述したように、従来の分散スナップショット方法は、マーカ・メッセージを使用し、チェックポインティングの前に送信された全てのメッセージをネットワークから一気に消去することによって、非一貫性を防止する。このアプローチはグローバルに一貫したチェックポイントを生じるが、通信ミドルウェア又はＯＳによって維持される状態を捕捉しない。そのような状態には、特定のハードウェア・アドレスに結合されたオープン接続が含まれるが、それに限定されない。どのようなタイプのトランスペアレント分散スナップショット・システムにおいても、これはどのようなタイプの移行をも妨げる。なぜなら、リモート・プロセスは、それが実行していた元のノードのアドレスを使用して、移行されたプロセスと通信しようと試みるからである。幾つかの分散スナップショット・システムは、元のノードの上に小さな「回送」プロセスＰｆを残すことによって問題に取りかかろうと試みる。Ｐｆは、移行されるプロセスに意図された全てのトラフィックを元のノードで受信し、それを新しいロケーションへ回送する。しかし、このモデルはフォールトトレランスに対処しない。なぜなら、故障がＰｆの実行を妨げるからである。
【００６３】
[0063]分散スナップショット・ベースのシステムがフォールトトレランスの移行を提供するためには、通信ミドルウェア又はＯＳのいずれかを修正しなければならない。そのようなシステムの顕著な例は通信ミドルウェア（例えば、ＬＡＭ／ＭＰＩ）である。このミドルウェアは、分散スナップショット・プロトコルを実施してサードパーティーの単一プロセス・チェックポイント・システムと統合させる特別のコードを有する。このタイプの配列は望ましくない。なぜなら、それはユーザ・アプリケーションをメッセージング・パッシングＡＰＩの特別な実施方法へ結合して、一般的メッセージ・パッシング指定の最初の動機を挫折させるからである。ＯＳの修正は、一層実行不可能となる。なぜなら、多くの分散システムは汎用ＯＳを実行し、システム管理者による手作業による修正を必要とするからである。
【００６４】
[0064]移行を含むチェックポイント／リスタートの全ての様相は、独立型フレームワークによってトランスペアレントに処理され、ユーザ・アプリケーション、ミドルウェア、又はオペレーティング・システムの修正を必要としないことが一般的に望まれる。本明細書の開示は、前述したウインドウ型メッセージ・ロギング・プロトコルの利点として、そのようなトランスペアレントな移行の提供を可能にする。全てのプロセス間通信は、ロギング・プロトコルを実施するため、チェックポイント・ライブラリを介してリダイレクトされる。本実施形態は全ての通信を処理するので、移行を可能にするために必要な全てのことは、所与のプロセスに意図された全ての通信を、それが移行されたノードへリダイレクトすることである。この方法の実施を容易にするため、本実施形態はネットワーク・アドレスを仮想化する。これは、ＯＳ通信インタフェースに対する全てのアプリケーション及びミドルウェアの要求が、本実施形態によって提供されるアドレスで満足させられることを意味する。内部的には、これらのアドレスは計算ノードの実際のハードウェア・アドレスへマップされてもよい。移行が生じるとき、チェックポイント・ライブラリは、それに従ってマッピングを修正する。そのような方法で、本実施形態はトランスペアレントなサポートをプロセス移行に提供することができる。
【００６５】
[0065]プロセスをローカルでチェックポイントするため、この方法は、次のものを記録する。（１）プロセスのグローバル及び静的なデータ、（２）そのプロセッサ・コンテキスト（レジスタの内容）、（３）そのスタック、及び（４）全てのダイナミックに割り付けられたメモリ。最初の３つの成分は既知のサイズであり、それらの値を安定記憶装置へ単純に書き込むことによって記録可能である。
【００６６】
[0066]最後の成分であるダイナミックに割り付けられたメモリは、共通領域（例えば、ヒープ）から割り付けられたメモリ、又は領域の中で「マップ」されて単位サイズ（通常はオペレーティング・システムのページ）の倍数であるサイズを有するメモリであってもよい。各々のチェックポイントで全てのダイナミックに割り付けられたメモリ領域を単純に記録することは可能であるが、典型的な分散計算は、大量のメモリを利用し、各々のチェックポイントで相当量のディスク・アクセスを必要とする。より望ましいことは、最後のチェックポイント以降の区間で修正されたメモリ領域だけをチェックポイントして、「増分」チェックポイントの順序正しい集合を作成することである。これを達成するため、チェックポイント・ライブラリは、全ての割り付けの制御パスの中にトランスペアレントに介在させられてもよい。
【００６７】
[0067]ローカル・チェックポイントの一部分としてどのメモリ領域を記憶する必要があるかを決定するため、本実施形態は、例えば、参照として本明細書に組み込まれるＪａｍｅｓ  Ｓ．Ｐｌａｎｋ，Ｍｉｃａｈ  Ｂｅｃｋ，Ｇｅｒｒｙ  Ｋｉｎｇｓｌｅｙ，ａｎｄ  Ｋａｉ  Ｌｉ．Ｌｉｂｃｋｐｔ：  Ｔｒａｎｓｐａｒｅｎｔ  Ｃｈｅｃｋｐｏｉｎｔｉｎｇ  Ｕｎｄｅｒ  Ｕｎｉｘ．Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ，１９９４に見い出される方法と類似した増分変更検出方法、又は、例えば、他の従来の単一プロセス・チェックポインティング方法に類似した方法を利用する。
【００６８】
[0068]全てのダイナミックに割り付けられたメモリは書き込みを防止され、防止されたメモリを修正しようとするアプリケーション又はミドルウェアの試みは、セグメント違反を生じる。セグメント違反の信号通知をチェックポイント・ライブラリへリダイレクトするため、プロセスの信号処理が介在する。チェックポイント・ライブラリは、セグメント違反が、書き込みを防止されたメモリの修正に起因したか、又はアプリケーション又はミドルウェアによって起こされた実際のセグメント違反に起因したかを決定する。真のセグメント違反はシステム・エラー処理ルーチンへ渡される。違反が、書き込みを防止されたメモリの修正に起因したのであれば、修正を含むメモリ領域は、修正されたものとしてコミット・リストの中でマークされる。書き込みの防止は除去され、アプリケーションの正規の実行フローが進行し、領域への全ての将来の修正は次のチェックポイントまで無視される。コミット・リストの中の領域は、チェックポイント区間における修正回数に関係なく、修正が存在するときチェックポイントされる。
【００６９】
[0069]チェックポイントを取る時間が来ると、計算は一時停止され、コミット・リストが順次に全探索され、最後のチェックポイント以降の区間に修正されたメモリ領域の全てが記録される。計算の一時停止は、コミット・リストの中の領域が、不揮発性メモリへ記憶される間に変更されないようにする。この増分チェックポインティング・アプローチにおいて、本実施形態は、記録されなければならないダイナミックに割り付けられるメモリの最小量を決定する。マークされるメモリ領域のサイズは、例えば、ＯＳのメモリ保護メカニズムが動作する最小メモリ・サイズ領域の離散的倍数である。多くのＯＳでは、これは、例えば、ページである。メモリ領域サイズの粒度（例えば、１ページ又は倍数ページ）は、パフォーマンスを向上するために変更されてもよいことに留意すべきである。
【００７０】
[0070]増分チェックポイントは、例えば、一連のファイル又は増分変化の集合として単一のダブルバッファド・チェックポイント・ファイルへ記憶されてもよい。ダブルバッファド・ファイルの利点は、チェックポイント動作の途中での故障が、前のチェックポイントの崩壊を生じないことである。
【００７１】
[0071]各々のチェックポイントのために記録されるメモリ量が大きいことを増分チェックポインティングが要求し、時には全てのチェックポイントで全てのダイナミックに割り付けられたメモリが記憶されることを要求する場合を考えるとき、この計算の一時停止は問題になる。この病的な場合は、分散システムが頻繁に使用されて実行するＨＰＣアプリケーションでは一般的なものとなる可能性がある。例えば、行列を使用して大きな連立一次方程式を解くアプリケーションでは、行列は片（例えば、部分行列、列、及び行）へ分割され、各々のプロセスが１つの片の上で動作する。一般的な行列演算の多くは、行列の中の全ての項目の値を修正し、したがって全体の行列がチェックポイントされることを要求する。プロセッサの相対的スピード及び不揮発性記憶サブシステムへのアクセスを因数分解しながら、分散システムの中のプロセッサは、相当量のアイドル時間量を費やすことが可能で、チェックポイントが記憶装置へ書き込まれるために待機する。全てのノードがそのコミット・リストの中にリストされたメモリ領域の記憶を終了し、ローカル計算を再開するまで、分散計算は再開しないので、この遮断問題は悪化する。これらの制限は、従来のシステムのチェックポイント動作を、最も遅いプロセスによって下限が決定される事実上のグローバル同期へ変換する。
【００７２】
[0072]チェックポイントをコミットする動作を、グローバル同期動作から、不揮発性記憶システムのアクセス・スピードによって制限されない実行時間を有する非遮断ローカルオペレーションへと縮小するため、本実施形態は、図４のフローチャートで記述される新規な非遮断・書き込み時コピー・順序外・チェックポインティング・アプローチを使用する。前述したように、従来の単一プロセス・チェックポインティング・システムはコミット・リストを利用して、前のチェックポインティング区間でどのメモリ領域が修正されたかを追跡する。本実施形態は、第１のバッファが前のコミット・リストＬｐを含み、第２のバッファが現在のコミット・リストＬｃを含む新規なダブルバッファド・コミット・リストを利用する。チェックポイント区間では、全ての検出された修正がＬｃの中にリストされてもよい。チェックポイント動作が呼び出されるとき、メモリへのローカル・プロセスは短時間一時停止され、Ｌｃの内容はＬｐの内容と交換され、Ｌｐの中にリストされたメモリ領域は書き込みを防止される。
【００７３】
[0073]留意すべきこととして、下記で説明する実施形態は、メモリ保護の前に交換が起こるものとして説明するが、他の実施形態では、メモリ領域がＬｃに置かれている間にメモリ領域への書き込みを防止した後で交換を行うことができる。保護される領域を含むバッファは、ＬｃであろうとＬｐであろうと、フリーズ期間の何時の時点でバッファが交換されるかに依存する。交換が書き込み防止の前に起こる場合、下記の実施形態で説明するように、領域は防止段階の間にＬｐの中で発見される。書き込み防止はフリーズ期間から出る前に実行される。
【００７４】
[0074]図４は、現在のコミット・リストの内容を前のコミット・リストへ移動した後の現在のコミット・リストのクリアを示す。留意すべきこととして、コミット・リストのクリアは、後続のチェックポイントが確実に最小サイズになるように手助けする。
【００７５】
[0075]ダブルバッファ自身は、任意の適切なデータ構造、例えばリンク・リストを使用して実施されてもよい。交換は、２つのバッファが置かれたメモリ・アドレスを記憶し、バッファを「交換」したいとき２つのアドレスを単純に交換することによって迅速に実施される。第２の実行スレッドが生み出されて、Ｌｐの中にリストされた全てのメモリ領域の内容を記録することを開始し、アプリケーションはチェックポイント記憶動作とともにインタリーブされた計算を再開することができる（即ち、並列に起こる）。メモリ領域が記録された後、そのリスティングはＬｐから除去される。インタリーブされた計算がメモリ領域を修正しようと試みる場合、その修正は検出され、本実施形態はそのメモリ領域がＬｐの中にリストされた領域であるか否かを決定する。領域がＬｐの中にリストされていることを発見される場合、記録スレッドによるＬｐの全探索は中断され、二次記憶装置へのメモリ領域の順序外記録が実行される。これは、記録されるプロセスの中にあったチェックポイントが確実に一貫して残るようにする。メモリ領域はＬｃへ付加される。なぜなら、問題の修正は次のチェックポイントの中に記録される必要があるからである。領域への書き込みアクセスは回復され、アプリケーションの実行は進行を許容される。この方法によって、チェックポイントのグローバルな一貫性が保証され、同時にアプリケーションの実行とチェックポイントのＩ／Ｏ動作とのインタリーブが可能となる。留意すべきこととして、バッファを表すために使用されるデータ構造は無関係であり、一般的に、メモリ領域がリスト及び全探索される効率で差異が生じるだけである。
【００７６】
[0076]書き込みを防止される領域は、ダブルバッファ領域Ｌｐ／Ｌｃの中に発見されることに留意されたい。ダブルバッファは、それ自身書き込みを防止される必要はない。なぜなら、ダブルバッファはチェックポインティング・ライブラリによって割り付け及び維持されるからである。ウインドウ型メッセージ・ロギングのためにログを含むメモリ領域への書き込みは防止され、ダブルバッファの中にリストされる。
【００７７】
[0077]この新規なアプローチの利点は、アプリケーションの一時停止が、ここではローカル動作であり、チェックポイント段階は、もはやグローバル同期を必要としないことである。このアプローチの第２の基本的利点は、一時停止の持続時間が比較的短いことである。なぜなら、それは修正されたメモリ領域の実際の内容を記録する動作の持続時間ではなく、メモリ領域への書き込みを防止するために必要な時間を含むだけであるからである。修正されたメモリ領域の実際の内容を記録する動作の持続時間は、不揮発性記憶システムのアクセス・スピードによって下限が決定され、この下限は計算のスピードよりも幾つかの桁数だけ遅くなるからである。順序外・書き込み時コピー・メカニズムは、Ｌｐの中にリストされた領域が、記録される前に修正されることを防止する。書き込み防止は、例えばハードディスクへメモリ領域を実際に記録しないで、実際の「コミット」動作になる。
【００７８】
[0078]本明細書で説明される実施形態は、従来の分散チェックポインティング・システムを利用するときに生じる問題を回避する助けとして使用されてもよく、従来のシステムでは一般的に不可能な新規な非遮断的グローバル・チェックポイント調整方法を提供する。図５は、分散計算をチェックポイントするため本実施形態によって取られるステップを示す。例示を目的として、チェックポイントが規則的な区間で取られて計算が進行するものと仮定する。留意すべきは、本明細書で開示されるシステム及び方法がそのような使用パターンに限定されないこと、そしてチェックポインティング戦略が規則的にスケジュール化されるか、ユーザによって恣意的に指令されるか、又はこれらを組み合わせてもよいことである。
【００７９】
[0079]区間の１つが経過した後、或るプロセスＰｒｏｏｔが、分散計算に参加している全てのプロセスへチェックポイント・コマンドをブロードキャストすることによって、チェックポイント動作を開始する。Ｐｒｏｏｔは、計算に参加しているプロセスの任意の１つ（例えば、ユーザ指令チェックポイント）、又はヘッド・ノード１０６で実行される他のプロセス、例えばスケジューリング・エンティティ又はリソース管理フレームワーク・ソフトウェア（例えばＬＳＦ、ＰＢＳ  Ｐｒｏ、及びＳｕｎ  Ｇｒｉｄ  Ｅｎｇｉｎｅ）であってもよい。ブロードキャスト・コマンドは、現在のチェックポイント動作に関連づけられたエポック識別子を含む。
【００８０】
[0080]ブロードキャストを受信すると、各々のプロセスＰｉは「フリーズ」期間へ入る。フリーズ期間、全てのプロセス間通信及び計算は一時停止される。ウインドウ型メッセージ・ロギング・プロトコルは、フリーズの間に廃棄されたメッセージが喪失されないことを確実にする。フリーズの後、Ｐｉはダブルバッファド・コミット・リストを利用して、Ｌｐの中にリストされたメモリ領域への書き込みを防止する前に、Ｌｐ及びＬｃの内容を交換する。ここで、コミットされた前の区間からの状態をＰｉが考慮して、記憶実行スレッドを生成することを順序外書き込み時コピーが保証する。Ｐｉは、バンド外障壁へ入ることによってチェックポイント動作から出る。障壁動作は、通常のように迅速に起こるものと期待される。なぜなら、計算に関与する分散システムの全てのプロセスは、典型的には、相互接続ネットワーク・レイテンシーより多くは分離されないでブロードキャストされたチェックポイントを受信し、したがってネットワーク・レイテンシーによって通常制限される遅延だけ分離された障壁へ入るからである。
【００８１】
[0081]障壁を実施するため、各々のプロセスＰｉは、Ｐｉの状態がコミットされたことをバンド外で開始・プロセスＰｒｏｏｔに通知する。Ｐｒｏｏｔが、計算に含まれた各々のＰｉからコミット確認を受信すると、Ｐｒｏｏｔは区間が終了したことを宣言するバンド外ブロードキャストを送信する。このブロードキャストを受信すると、Ｐｉは障壁から出て、フリーズが解除され、Ｐｉはプロセス間通信及び計算を再開する。留意すべきは、本実施形態の正しい動作には、障壁は必要でないことである。障壁は、単に、分散計算に関与する全てのプロセスがチェックポイント・メッセージを受信及び処理したこと、特に全てのプロセスが同じエポックで動作していることを保証する。
【００８２】
[0082]「カレント・エポック」識別子は単調に増加する６４ビットの量であって、各々のプロセスは、上記量についてそれ自身のローカル・コピーを維持する（例えば、ローカル・メモリの中の値として）。各々のプロセスは、グローバル・チェックポイント動作から出た後でローカル計算及びプロセス間通信を再開する前に、このローカル・コピーを増分する。増分チェックポイント・ファイルは、このエポック識別子を使用して整理及び識別されてもよい。２つのプロセスがカレント・エポックについて異なった値を有してもよい唯一の時間は、グローバル・チェックポイント動作から出たプロセスが、グローバル・チェックポイント動作に依然として参加しているプロセスよりも大きいカレント・エポックを有するグローバル・チェックポイント動作の間である。
【００８３】
[0083]チェックポイント区間の任意の時点で、何らかの理由によって、分散計算の中の２つのプロセスが、異なったエポックで動作していれば、この事実は故障として検出される。この故障を検出するプロセスは例外をブロードキャストし、分散計算は最も近時の既知のグローバルに一貫したチェックポイントへ戻されてもよい。障壁の存在は、この故障モードの検出を加速するだけである。上記の実施形態の全体のチェックポイント段階は、単に緩やかに調整されてもよく、典型的には、修正されたメモリの実際の内容を二次記憶装置へコミットするために必要な時間の、ほんの一部分の時間だけ続いてもよい。
【００８４】
[0084]ここで、前述した実施形態に応用可能と思われるグローバル一貫性に関して、幾つかの概念を簡単に説明する。ｎ個のプロセスから成る分散計算を考える。システムのグローバル状態は、各々のプロセスＰｉの個々の状態と、通信チャンネルの状態との和集合として抽象的に定義可能である。この簡単な説明の目的のために、分散システムはメッセージ・パッシング・システムであると仮定される。しかし、留意すべきは、プロセス間の通信が共有メモリ・ロケーションの修正を介して促進される共有メモリ・システムにも、説明を応用できることである。そのようなシステムで実行している分散計算については、グローバル分散状態ＳＧは、より公式的には次のように定義可能である。
【数１】
2008502953.tif 000002
ここで、ＳｉはＰｉのローカル状態を表し、Ｃｉｊは２つのプロセスＰｉとＰｊとの間の通信チャンネルの状態を表す。Ｃｉｊは、更に、メッセージＭｉｊの集合へ縮小され得る。ここで、各々のメッセージｍはＰｉ又はＰｊによって送信されており、対応するプロセスによっては未だ受信されていない。ウインドウ型メッセージ・ロギング・メカニズムの使用によって、全てのメッセージｍは送信者のログへコミットされてもよく、既に受信されていれば、受信者の状態へ記憶されてもよい。これは、通信チャンネルＣｉｊの状態がローカル状態Ｓｉ及びＳｊの中に完全に含まれることを意味する。したがって、グローバル分散状態は、次式へ縮小される。
【数２】
2008502953.tif 000003
【００８５】
[0085]グローバル・チェックポイント動作における各々のプロセスＰｉの役割は、ローカル・チェックポイント動作を実行してＳｉを記録することに縮小された。ＳＧの一貫性を保証するため、状態Ｓｉはローカル・チェックポイント動作の間は変化しない。更に具体的には、グローバル・チェックポイント動作へ入ると、Ｐｉは、グローバル・チェックポイント動作が終了するまで、そのローカル状態又は他のプロセスＰｊの状態を変更しない。ローカル状態の変化の唯一の自己付加原因はローカル計算である。同様に、ＰｉがＰｊの状態を変更する唯一の方法はメッセージを送信することである。
【００８６】
[0086]これらの規準が与えられたとして、Ｐｉは、グローバル・チェックポイント・プロセスへ入るとローカル計算を停止し、全てのプロセス間通信が一時停止される「フリーズ期間」へ入ることを想起されたい。次に、Ｐｉはローカル・チェックポイント動作を実行し、緩やかに同期されたバンド外障壁動作へ入ることによって、グローバル・チェックポイント動作から出る。Ｐｉは、グローバル・チェックポイント動作に関与する間、如何なる時点でもそれ自身の状態を変更せず、又はＳｊを変更するメッセージをプロセスＰｊへ送信しない。Ｐｉは、緩やかに同期された障壁動作においてローカル計算を再開するが、依然としてプロセス間通信を控える。これは、Ｐｉが、グローバル・チェックポイント動作に依然として参加しているプロセスＰｊの状態を変更しないことを保証する。全てのプロセスが、緩やかに同期された障壁へ入り、続いて障壁が終了した後でのみ、Ｐｉはプロセス間通信を再開する。上記のアプローチの使用は、取られた全てのグローバル・チェックポイントのグローバル一貫性を提供する。
【００８７】
[0087]前述した実施形態は、リソース共有ポリシーを実施するとき、フレキシビリティを最大限に提供することのできるプリエンプティブ・スケジューリング・システムを実施するために使用されてもよい。プリエンプティブ・スケジューラは、好ましくは、ユーザ・レベルのトランスペアレントなウインドウ型メッセージ・ロギングに基づいたチェックポインティング・フレームワーク、例えば、前述したものを使用して、実行中のジョブの状態を記録すべきである。１つの計算が一時停止され、それに代わって他の計算がスタート又は再開させることをリソース共有ポリシーが指示するとき、前述した実施形態を使用して、実行中の計算を停止する前に、それをチェックポイントしてもよい。新しい計算又はチェックポイントから再開された計算であってもよい第２の計算が実行される。
【００８８】
[0088]トランスペアレントなウインドウ型メッセージ・ロギングに基づいた方法を使用することによって、個々のプロセスの移行が許容され、分散システムの中のプロセスの物理ロケーションに制限は置かれない。これは、スケジューラが、例えば、分散システムのトータル容量によってのみ制限されるリソース共有ポリシーに従って、計算をプリエンプト及び再開することを可能にする。プリエンプティブ・スケジューラは、更に、個々の計算の実行区間の長さを変更することによって、各々の計算の相対的優先順位を考慮してもよい。プリエンプティブ・スケジューラは、一般的に、プリエンプト及び再開されるプロセスの空間的位置付けを考慮する必要はない。もっとも、協力するプロセスによって使用される通信チャンネルのレイテンシーを最小限にするように、空間的位置付けを構成してもよいことに留意すべきである。
【００８９】
[0089]１つのアプローチの具体的な例は、下記のステップによって記述される。
【００９０】
[0090]分散システムの各々の計算ノードでモニタリング・プロセス又はデーモンを実行する。
【００９１】
[0091]ヘッド・ノード又は分散システムの計算ノードの１つでスケジューリング・プロセスを実行する。スケジューリング・プロセスによって、ユーザは分散システムで実行される分散計算をキューにすることができる。
【００９２】
[0092]ユーザ・レベル・チェックポインティング・ライブラリに対してアプリケーションをリンクする。ユーザ・レベル・チェックポインティング・ライブラリは、アプリケーション、通信ミドルウェア、及びオペレーティング・システムにトランスペアレントであり、また仮想からネットワーク／ハードウェア・アドレスへのマッピングを使用して、ネットワーク／ハードウェア・アドレスを仮想化する。
【００９３】
[0093]分散計算で利用される各々のノードに存在するデーモンへメッセージを送信することによって、分散計算を開始する。デーモンは、アプリケーションの実行を開始する新しいオペレーティング・システム・プロセスを開始する。或る計算期間の後、計算に参加する各々の計算ノードのモニタリング・デーモンへチェックポイント・メッセージをブロードキャストする。デーモンは、プロセス状態をチェックポイントするようにプロセスを誘導する。この誘導は、非限定的に、オペレーティング・システムの信号、共有メモリ・ロケーションへの修正、又はバンド外通信チャンネルの上を送信されるメッセージの形式を取ってもよい。
【００９４】
[0094]ローカル・チェックポイントの集合が、一貫したグローバル状態を生じること、及び一時停止されたプロセスが、システムの他のノードへ移行されることを保証するため、ウインドウ型メッセージ・ロギング・プロトコルを使用する方法でプロセスをチェックポイントする。
【００９５】
[0095]全てのデーモンが、成功したチェックポイントの通知をスケジューリング・プロセスへ戻した後、計算に参加する全ての計算ノードのモニタリング・デーモンへキル（ｋｉｌｌ）メッセージをブロードキャストする。各々のデーモンはメッセージを受信し、前述したような方法を使用して、停止するようにプロセスを誘導する。分散計算が停止した後、現在ではアイドルであるノードの集合で前に保存されたチェックポイントから、他の計算がスタートされるか再開されてもよい。計算を再開するとき、デーモンは、プロセス移行の結果として仮想からネットワーク／ハードウェア・アドレスへのマッピングで行われた変更を、再開されるプロセスに提供する。この情報は、非限定的に、フラットなテキスト・ファイル、共有メモリ・ロケーション、又は環境変数の形式で提供されてもよい。或る実行期間の後、この第２の計算自身は、前述した方法でプリエンプトされ、第１の計算又は第３の計算と取り替えられてもよい。
【００９６】
[0096]複数キューの計算が存在する場合、適当なリソース共有ポリシーを最良に近似しながら、最小限のアイドルＣＰＵ時間を最良に促進するノードのサブセットへ、再開された計算を移行する。順序正しい方法で計算を定期的にプリエンプト及び／又は移行することによって、分散システムは任意の数の分散計算を同時に実行し、タスクがキューへサブミットされて完了するまでの経過時間が、計算実行時間及びキューのタスク数によってのみ制限されるようにし、キューに入れられた順序によって影響されないようにする。
【００９７】
[0097]優先順位に基づくリソース使用が望まれる場合、各々のタスクがキューに入れられるとき、タスクに優先順位値を割り当てる。より高い優先順位のタスクがキューへ付加されるとき、実行中のタスクをプリエンプトする。最後に、プリエンプションの間の期間を調整し、より高い優先順位のタスクが計算サイクルの所望のパーセンテージと一致するようにする。
【００９８】
[0098]特定の例示的方法が、前述したプリエンプティブ・スケジューリング・ステップで説明されたが、前述したステップの多くが他の実施形態では配列をし直され、及び／又は省略されてもよいことを当業者は認識する。
【００９９】
[0099]前述した開示によって、非遮断的な方法、個々のプロセスの移行を可能にする方法、及びアプリケーション、使用されるミドルウェア、及びオペレーティング・システムにトランスペアレントな方法でチェックポイント／リスタート問題を処理するために使用される改善されたシステム及び方法を説明した。他の利点としては、下記の特徴の１つ以上が含まれる。
１．チェックポイントの間に、通信チャンネル及び両端おけるプロセスのグローバルな一貫性を保証するトランスペアレントで移行能力のある方法。
２．プロセスの状態を原子的に記憶する（即ち、状態の崩壊又は変化が生じない方法で記憶する）方法。この方法は、グローバルな同期動作からプロセスごとのローカル動作へ分散計算のチェックポイントを縮小する。
３．分散計算に参加する全てのプロセスのローカル・チェックポインティングを調整して、個々のチェックポイントの集団がグローバルに一貫した状態を表すようにし、該グローバル一貫状態を使用して、後の時点で計算を再開できるようにするトランスペアレントで非遮断的な方法。
４．チェックポイント状態を記憶する非遮断的方法であって、チェックポイント状態を不揮発性記憶装置へ記憶するプロセスの間にアプリケーションが計算を続行できるようにする方法。
【０１００】
[00100]具体的実施形態のこれまでの説明は、開示の一般的性質を十分明らかにしている。他者は、現在の知識を応用することによって、一般的コンセプトから逸脱することなく、様々な応用のために容易に開示を修正及び／又は適合化することができる。例えば、上記の開示は、チェックポイント・ライブラリをユーザ・レベル・ライブラリとして使用する文脈で呈示されたが、他の一定の実施形態では、チェックポイント・ライブラリをカーネル・モジュールとして実施することができる。したがって、そのような適合化及び修正は、開示された実施形態の同等物の意味及び範囲の中にある。本明細書で使用された語句又は用語は、説明を目的としており、これに限定することを意図しているものではない。
【図面の簡単な説明】
【０１０１】
【図１】開示の第１の実施形態に従った分散コンピューティング・システムを示す。
【図２】図１の分散コンピューティング・システムの計算ノードにおけるアプリケーション、ミドルウェア、及びオペレーティング・システムに関するレイヤ形成を示す。
【図３】第１の実施形態で使用されるウインドウ型メッセージ・ロギング・プロセスのフローチャートである。
【図４】チェックポイントを記憶するために第１の実施形態で使用される非遮断的方法のフローチャートである。
【図５】第１の実施形態で使用される分散チェックポイント調整方法のフローチャートである。
【図１】
2008502953.tif 000004
【図２】
2008502953.tif 000005
【図３】
2008502953.tif 000006
【図４】
2008502953.tif 000007
【図５】
2008502953.tif 000008