(57)【要約】  分散システム（１）は、メモリ（１０２）を有し、分散プロセスを実行し、チェックポインティングを行い、各プロセス用チェックポイントデータを生成する複数のノード（１００）と、複数の将来障害リカバリ用予備ノードをプロセス毎に選択するノード選択部（２０６）と、障害発生前にチェックポイントデータを予備ノードに割り当て、予備ノードに送信し、各予備ノードにチェックポイントデータをメモリに格納させる割り当て部（２０８）と、少なくとも一つのチェックポイントがリカバリに適切との判断時、チェックポイントを一つ選択し、選択チェックポイントをアクティブにして、予備ノード上で一プロセスを実行し、またはリカバリに適切なチェックポイントが一つもないと判断時、メモリ格納の現存チェックポイントデータを、複数分割部分に分割するリカバリ部（２１２）と、チェックポイントデータの複数分割部分は、全体として完全なチェックポイントデータに統合され、予備ノードから新ノードに複数分割部分はそれぞれ送信され、新ノード上で送信された複数分割部分は完全なデータに統合されアクティブ化されプロセスを実行する。
2013516665.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおいて、複数の前記ノードは、分散プロセスを実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納し、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択し、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させ、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断し、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリでき、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセスの複数の前記予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノードで、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる障害リカバリ方法。
【請求項２】
請求項１に記載の障害リカバリ方法において、
前記複数予備ノードを選択する際、
残りのノードより少ないプロセスを実行している一つのノードを優先して選択する第１の方法、残りのノードより大きいメモリ容量を有する一つのノードを優先して選択する第２の方法、および、ランダムに一つのノードを選択する第３の方法を含む複数の方法の中から選択した方法で、前記将来の障害リカバリ用の複数予備ノードを選択する障害リカバリ方法。
【請求項３】
請求項１または２に記載の障害リカバリ方法において、
前記各プロセスに障害が発生する前に、前記プロセス毎にｋ個の予備ノードを選択し、
前記ネットワークを介して選択されたｋ個の予備ノードに対し、前記チェックポイントデータをマルチキャストし、
前記ｋ個の予備ノードの各々の前記メモリに前記チェックポイントデータを格納し、
前記障害プロセスの検出に呼応して、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の前記ｋ個の予備ノードの各々におれる前記チェックポイントデータを、１／ｋ分割部分に複数に分割し、ｋ個の予備ノードの各々のチェックポイントデータの１／ｋ分割部分は、全体として前記障害プロセス用の完全なチェックポイントデータに統合され、前記チェックポイントデータの前記１／ｋ分割部分を前記ネットワークを介して前記新ノードに前記ｋ個の予備ノードからそれぞれ送信する障害リカバリ方法。
【請求項４】
請求項３に記載の障害リカバリ方法において、
プロセス毎に、前記ｋが他のプロセスと異なる場合、前記予備ノードの前記メモリ内に格納されるチェックポイントデータの数の閾値は、上限が［（Ｎｃｋｐｔ＋ｍ）／Ｎｓｅｌｅｃｔ］であり、ここで、前記Ｎｃｋｐｔは各プロセス用のチェックポイントデータの総数であり、前記ｍは、前記ｎ個のノードで実行しているプロセスの数であり、前記Ｎｓｅｌｅｃｔは、前記予備ノードの総数である障害リカバリ方法。
【請求項５】
請求項３または４に記載の障害リカバリ方法において、
各プロセスのｋが同じ場合、異なるプロセスからのチェックポイントデータの数は、上限が［（ｋ＋１）×ｍ／ｎ］以下である障害リカバリ方法。
【請求項６】
請求項３乃至５いずれかに記載の障害リカバリ方法において、
さらに、前記予備ノードの各々から前記新ノードに、分割された１／ｋチェックポイントデータを送信し、前記分割された１／ｋデータは互いに異なり、
前記障害プロセスをリカバリするために、前記新ノードにおいて送信されたチェックポイントデータを再編成し、
前記障害プロセス用のメモリコンテキストを準備し、
そして、リカバリされたプロセスをアクティブにする障害リカバリ方法。
【請求項７】
請求項１乃至５いずれかに記載の障害リカバリ方法において、
さらに、リカバリに適した少なくとも一つのチェックポイントデータがあると判断されたとき、前記チェックポイントデータから適切なリカバリポイントを見つけ、
そして、前記障害プロセス用のメモリコンテキストを準備し、
前記リカバリポイントから再スタートすることによって、新たにリカバリされたプロセスを実行するのに適した前記予備ノード内でリカバリすべきプロセスを最終的にアクティブにする障害リカバリ方法。
【請求項８】
請求項１乃至７いずれかに記載の障害リカバリ方法において、
前記チェックポインティングは、インクリメンタルまたは確率的なチェックポイント、あるいは、それらの組み合わせである障害リカバリ方法。
【請求項９】
請求項１乃至８いずれかに記載の障害リカバリ方法において、
複数の前記分割部分の再編成は、
新しい事前に割り当てられたノードを追加する、または、前記新しい事前に割り当てられたノードに、事前に割り当てられたノード内のデータを移動することを含み、各プロセスのチェックポイントの第１の数と、システムの最も初期に定義を満たす各事前に割り当てられたノード内のチェックポイントデータの第２の数とを保証する障害リカバリ方法。
【請求項１０】
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードと、複数の前記ノードは、分散プロセスを実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納するチェックポインティング部と、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる割り当て部と、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の各予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノード上で、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える分散システム。
【請求項１１】
分散システムにおける障害リカバリのための管理装置であって、前記分散システムは、ネットワークを介して互いに接続される複数のノードを含み、複数の前記ノードの各々はメモリを有し、複数の前記ノードは分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリに格納させる事前割り当て部と、
障害が発生した障害プロセスを検出する検出部と、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにするリカバリ部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記チェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させ、前記新ノードに、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える管理装置。
【請求項１２】
ノードを実現するコンピュータによって実行可能な記録媒体に記録されたコンピュータプログラムであって、複数の前記ノードは、分散システム内で、ネットワークを介して互いに接続され、複数の前記ノードの各々は、メモリを有し、複数の前記ノードは、分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記コンピュータに、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択する手順、
複数のノードに対して指示して、前記チェックポイントデータを前記選択された複数の予備ノードに事前に割り当てさせる手順、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された複数の予備ノードに送信させ、前記選択された複数の予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる手順、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する手順、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順、
前記障害プロセス用の各前記予備ノードに対して指示して、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の複数の前記予備ノードに対して指示して、それぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させる手順、
前記新ノードに対して指示して、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順を実行させるためのコンピュータプログラム。
【請求項１３】
分散システムにおけるノードであって、
複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
複数の前記プロセスに対しチェックポインティングを行い、プロセス毎にチェックポイントデータを生成するチェックポインティング部と、
前記チェックポイントデータを格納するメモリと、
前記管理装置から指定された前記動作しているプロセスの将来の障害リカバリ用の複数の予備ノードに前記チェックポイントデータをマルチキャストし、前記指定された複数の予備ノードに、前記受信したチェックポイントデータを前記メモリにそれぞれ格納させるマルチキャスト部と、を備えるノード。
【請求項１４】
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、動作しているノード用の予備として機能し、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
前記プロセスを実行している他のノードからチェックポイントデータを前記ネットワークを介して受信する受信部と、
受信したチェックポイントデータを格納するメモリと、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
プロセスが障害を起し、かつ前記管理装置が、前記メモリに格納された前記チェックポイントデータが前記障害をリカバリするのに適していると判断したとき、前記管理装置の制御に従って、前記メモリに格納された前記チェックポイントデータをアクティブにし、前記処理部にプロセスを実行させ、その結果、障害プロセスをリカバリできるアクティブ化部と、
プロセスが障害を起し、かつ前記管理装置が、リカバリに適しているチェックポイントが一つもないと判断したとき、前記管理装置の制御に従って、前記メモリ内の現存するチェックポイントデータを、障害プロセス用に、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
前記チェックポイントデータの複数の前記分割部分のうち一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信する送信部と、を備えるノード。
【請求項１５】
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
将来の障害リカバリ用に予め準備された複数の予備ノードのそれぞれからチェックポイントデータの分割部分を受信し、プロセスをリカバリするためのチェックポイントデータを確保する受信部と、前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
プロセスが障害を起こしたとき、前記管理装置の制御に従い、受信した前記チェックポイントデータの複数の前記分割部分を、前記障害プロセス用の前記完全なチェックポイントデータに再編成し、アクティブにして、前記処理部にプロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備えるノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、障害リカバリのための方法、分散システム、およびコンピュータプログラムに関し、特に、複数プロセスのチェックポインティングおよびリカバリを行う障害リカバリのための方法、分散システム、およびコンピュータプログラムに関する。
【背景技術】
【０００２】
分散システムにおいて障害に耐えるために、しばしば使用される技術の一つは、機能不全になったプロセス／ジョブ（これ以降、単にプロセスと言い、チェックポインティングを行うことができるプログラム、タスク、ジョブ、および、どれでも実行しているユニットを意味する）を、他の健全なマシン／ノード（これ以降、簡単にノードのみ）に移動することである。プロセスマイグレーションは、あるノードから他のノードに動作中のプロセスを移動できる（非特許文献１）。機能不全になったハードウェアにおけるプロセスは抽出できないため、マイグレーションによって単にプロセスを移動することでは、ハードウェアの障害に耐えることができない。したがって、プロセスマイグレーションは、障害耐性に対する効果は限定され、同様な技術、チェックポインティング／リカバリが出現する（非特許文献２）。
【０００３】
分散システムにおける既存のチェックポインティング／リカバリ技術は、おおまかに２つのクラス、ディスクベースとディスクレスに分類できる。非特許文献２において、ディスクベースのチェックポインティング／リカバリのメカニズムについて調査されている。クラスタなどの分散パラレルコンピュータシステムでは、ディスクベースのチェックポインティング／リカバリは、非特許文献３および非特許文献４などの分散方法で実施される。ディスクアクセスからの遅延を排除するために、ディスクレスチェックポインティングが開発され、はじめに非特許文献５で提示され、そして、それは非特許文献６で達成された。クラスタシステムでディスクレスチェックポインティング／リカバリを使用する例は非特許文献７に記載されている。
【０００４】
インクリメンタルチェックポインティング（非特許文献８に記載された）と確率的なチェックポインティング（非特許文献９に記載された）は、チェックポインティング時間とデータ伝送コストを効果的に削減できる。最終的に、マルチキャストはこの発明にも関わるが、通信の発信元と目的地が典型的なマスタ／スレーブの関係であるので、この発明におけるマルチキャストは、グループ通信のものよりはるかに簡単である。
【０００５】
現在、分散システムに存在するチェックポインティング／リカバリ技術がどういうものであろうと、健全に継続してプロセスを実行する新たに選択されたノードに、プロセスのチェックポイントデータを転送しなければならない。データ転送を説明するために２つの例をここに示す。非特許文献３および非特許文献４には、隣接しているノード内のデータ断片から計算されたパリティ付きで、分散したノードに、チェックポイントデータ全体が別々に保存される。したがって、各ノードには、データの断片およびデータ断片のパリティが格納される。永続的な障害がノードで起こるとき、データ断片が、その隣接ノードに再帰的に移され、そして、隣接ノードでは、データ断片およびパリティが、隣接ノード内の元のデータ断片を計算するのに使用される。
【０００６】
これらのノードは、平行して、チェックポインティング／リカバリを操作するが、各データ断片のパリティ計算を連続して実行しなければならない。したがって、リカバリ時間は、一つのプロセスのチェックポイントデータ全体の転送時間とパリティの計算時間に等しい。ここで、ディスク操作は含まれず、この再構築時間は通常非常に短いので、メモリ内のプログラム実行コンテキストを再構築する時間は、無視できる。
【０００７】
非特許文献６において、データ転送とパリティ計算による時間遅延は、非特許文献３および非特許文献４と同じであり、違いは、単に非特許文献６のシステムがディスクレスということである。非特許文献７では、各プロセスのデータはローカルメモリに格納され、そして、パリティはデータのすべてから計算される。もし、障害がノードで起こった場合、残っているデータとパリティは新たに選択されたノードに移されるだろう。
【０００８】
特許文献１（特開２００９−１２９４０９号公報）において、すべてのコンピュータが、ビジネスコンピュータと、アイドルコンピュータに分類されるとしている。ビジネスコンピュータはプログラムを実行し、アイドルコンピュータは、リカバリ用データを格納するだけである。特許文献１（特開２００９−１２９４０９号公報）には、プロセスのチェックポイントファイルがユニキャストによって一つのコンピュータに、または、マルチキャストによって全てのコンピュータに、格納されることが記載されている。しかし、特許文献１（特開２００９−１２９４０９号公報）には、いつ、どれくらいの他のコンピュータにマルチキャストを使用するのかに関する情報がない。特許文献１（特開２００９−１２９４０９号公報）では、チェックポイントは、特定のコンピュータに格納できるだけで、チェックポイントデータは、複数の小片に分けて、新しく選択されたコンピュータに再編成することはできない。リカバリコストは大幅には削減できない。
【０００９】
特許文献２（特開平１０−２７５１３３号公報）は、チェックポイントおよびリカバリ情報がどのように収集され、格納され、処理され、そして記録されるかが紹介している。チェックポイントデータのただ一つのコピーがあり、リカバリは決定論的方法である。リカバリコストもまた大幅には削減されない。
特許文献３（特開平０８−３１４８７５号公報）には、共有メモリ分散システムのための方法が示されている。この方法は、平均チェックポイント／リカバリコストが大幅に削減されることと、この発明のチェックポイントデータが複数の小片に切断され、再統合できることを保証するだけなので、この特許が提案する方法は、上述した方法とは異なる。言い換えれば、これはランダム化された方法である。
【００１０】
リカバリ時間は、一つのプロセスのデータの転送時間に、パリティの計算時間を少なくとも加算したものである。パリティの計算時間は、短くすべきと論争されているにも関わらず、データ転送速度が遅く、かつコンピューティングパワーが通常デスクトップより弱い、ワイヤレスおよびモバイル分散コンピューティングにおいては、この計算時間は実に長過ぎる。
【００１１】
大規模分散システム、グリッドシステム、クラウドシステム、およびＰ２Ｐ（Peer to Peer）システム、ならびに、ワイヤレスおよびモバイル分散システムなどにおいて、ネットワーク帯域と待ち時間が悪化した場合、リカバリ時間はかなり長くなる。既存の技術では、この問題は解決できない。なぜなら、チェックポイントデータをすべて新しいノードに移すということなしには、障害プロセスを論理的にリカバリできないからである。付加的なパリティ計算はさらにリカバリィ時間を遅らせる。ｔＤはディスクアクセス時間を示し、ｔＮはネットワークのデータ伝送時間を示し、ｔＰはパリティ計算時間を示すとき、リカバリ時間ｔＲは、ｔＲ＝ｔＤ＋ｔＮ＋ｔＰとして表すことができる。ディスクレスのチェックポインティング／リカバリに関しては、ｔＲ＝ｔＮ＋ｔＰである。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００９−１２９４０９号公報
【特許文献２】特開平１０−２７５１３３号公報
【特許文献３】特開平０８−３１４８７５号公報
【非特許文献】
【００１３】
【非特許文献１】D. S. Milojicic et al., and four others, "Process Migration", ACM Computing Surveys, (U.S.A.), Association for Computing Machinery, September 2000, Vol. 32, No. 3, p. 241-299.
【非特許文献２】E. N. (Mootaz) Elnozahy et al., and three others, "A Survey of Rollback-Recovery Protocols in Message-Passing Systems", ACM Computing Surveys (CSUR), (U.S.A.), Association for Computing Machinery, September 2002, Vol. 34., No. 3, p. 375-408.
【非特許文献３】H. Nakamura et al., and five others, "Skewed Checkpointing for Tolerating Multi-Node Failures", Proceedings of the 23rd IEEE (Institute of Electrical and Electronics Engineers, Inc.) International Symposium on Reliable Distributed Systems (SRDS'04), (U.S.A.), 2004, IEEE Computer Society, p. 116-125.
【非特許文献４】M. Kondo et al., and five others, "Evaluation of Checkpointing Mechanism on SCore Cluster System", IEICE (Institute of Electronics, Information and Communication Engineers) Transactions on Information and Systems E series D, (Great Britain), Institute of Electronics, Information and Communication Engineers, January 2003, Vol. E86-D, No.1, p. 2553-2562.
【非特許文献５】J. S. Plank et al., and one other, "Faster Checkpointing with N+1 Parity", Proceedings of the 24th International Symposium, Fault-Tolerant Computing, (U.S.A.), University of Tennessee, 1994, p. 288-297.
【非特許文献６】J. S. Plank et al., and two others, "Diskless Checkpointing", IEEE Transactions on Parallel and Distributed Systems, (U.S.A.), IEEE Press, October 1998, Vol. 9, No. 10, p. 972-986.
【非特許文献７】W. Gao et al., and two others, "A Faster Checkpointing and Recovery Algorithm with a Hierarchical Storage Approach", Proceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region (HPCASIA'05), (U.S.A.), IEEE Computer Society, 2005, p. 398.
【非特許文献８】S. Agarwal et al., and three others, "Adaptive Incremental Checkpointing for Massively Parallel Systems", Proceedings of the 18th annual International Conference on Supercomputing (ICS), (U.S.A.), Association for Computing Machinery, 2004, p. 277-286.
【非特許文献９】E. N. Elnozahy, "How Safe Is Probabilistic Checkpointing?", Proceedings of the 28th Annual International Symposium on Fault-Tolerant Computing (FTCS), (U.S.A.), IEEE Computer Society, 1998, p.358-363.
【発明の概要】
【００１４】
本発明の目的の一例は、チェックポインティングまたはリカバリが大規模分散システムで使用されるとき、ネットワーク伝送遅延、ディスクリードまたはライト遅延を改善できる障害リカバリのための方法、システム、およびコンピュータプログラムを提供することにある。
【００１５】
一つの実施形態において、ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおいて、複数の前記ノードは、分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納し、前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択し、前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させ、前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断し、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリでき、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセスの複数の前記予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノードで、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる障害リカバリ方法が提供される。
【００１６】
別の実施形態において、ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードと、複数の前記ノードは、分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納するチェックポインティング部と、前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、前記チェックポイントデータを前記選択された予備ノードに割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる割り当て部と、前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、前記障害プロセスをリカバリするのに適しているかを判断する判断部と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の各予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部と、前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノード上で、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含む分散システムが提供される。
【００１７】
別の実施形態において、分散システムにおける障害リカバリのための管理装置であって、前記分散システムは、ネットワークを介して互いに接続される複数のノードを含み、複数の前記ノードの各々はメモリを有し、複数の前記ノードは分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリに格納させる事前割り当て部と、障害が発生した障害プロセスを検出する検出部と、障害プロセスが検出されたとき、複数の前記予備ノードにおいて、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する判断部と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにするリカバリ部と、前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記チェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させ、前記新ノードに、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含む管理装置が提供される。
【００１８】
別の実施形態において、ノードを実現するコンピュータによって実行可能な記録媒体に記録されたコンピュータプログラムであって、複数の前記ノードは、分散システム内で、ネットワークを介して互いに接続され、複数の前記ノードの各々は、メモリを有し、複数の前記ノードは、分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記コンピュータに、前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択する手順、複数のノードに対して指示して、前記チェックポイントデータを前記選択された複数の予備ノードに事前に割り当てさせ、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された複数の予備ノードに送信させ、前記選択された複数の予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる手順、前記プロセスで障害が起きたとき、複数の前記予備ノードにおいて、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する手順、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順、前記障害プロセス用の各前記予備ノードに対して指示して、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の複数の前記予備ノードに対して指示して、それぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させる手順、前記新ノードに対して指示して、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順を実行させるためのコンピュータプログラムが提供される。
【００１９】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、複数の前記プロセスに対しチェックポインティングを行い、プロセス毎にチェックポイントデータを生成するチェックポインティング部と、前記チェックポイントデータを格納するメモリと、前記管理装置から指定された前記動作しているプロセスの将来の障害リカバリ用の複数の予備ノードに前記チェックポイントデータをマルチキャストし、前記指定された複数の予備ノードに、前記受信したチェックポイントデータを前記メモリにそれぞれ格納させるマルチキャスト部と、を備えるノードが提供される。
【００２０】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、動作しているノード用の予備として機能し、前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、前記プロセスを実行している他のノードからチェックポイントデータを前記ネットワークを介して受信する受信部と、受信したチェックポイントデータを格納するメモリと、前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、プロセスが障害を起し、かつ前記管理装置が、前記メモリに格納された前記チェックポイントデータが前記障害をリカバリするのに適していると判断したとき、前記管理装置の制御に従って、前記メモリに格納された前記チェックポイントデータをアクティブにし、前記処理部にプロセスを実行させ、その結果、障害プロセスをリカバリできるアクティブ化部と、プロセスが障害を起し、かつ前記管理装置が、リカバリに適しているチェックポイントが一つもないと判断したとき、前記管理装置の制御に従って、前記メモリ内の現存するチェックポイントデータを、障害プロセス用に、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、前記チェックポイントデータの複数の前記分割部分のうち一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信する送信部と、を備えるノードが提供される。
【００２１】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、将来の障害リカバリ用に予め準備された複数の予備ノードのそれぞれからチェックポイントデータの分割部分を受信し、プロセスをリカバリするためのチェックポイントデータを確保する受信部と、前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、プロセスが障害を起こしたとき、前記管理装置の制御に従い、受信した前記チェックポイントデータの複数の前記分割部分を、前記障害プロセス用の前記完全なチェックポイントデータに再編成し、アクティブにして、前記処理部にプロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含むノードが提供される。
【００２２】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。
【００２３】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。
【００２４】
また、本発明の方法およびコンピュータプログラムには複数の手順を順番に記載してあるが、その記載の順番は複数の手順を実行する順番を限定するものではない。このため、本発明の方法およびコンピュータプログラムを実施するときには、その複数の手順の順番は内容的に支障のない範囲で変更することができる。
【００２５】
さらに、本発明の方法およびコンピュータプログラムの複数の手順は個々に相違するタイミングで実行されることに限定されない。このため、ある手順の実行中に他の手順が発生すること、ある手順の実行タイミングと他の手順の実行タイミングとの一部ないし全部が重複していること、等でもよい。
【図面の簡単な説明】
【００２６】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。
【図１】本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図２】図１に示す分散システムのネットワーク構成を示すブロック図である。
【図３】図１に示す分散システムの管理装置のリカバリ部の構成を示すブロック図である。
【図４】本発明の実施の形態に係る分散システムの動作を示すフローチャートである。
【図５】本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図６】本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図７】本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図８】本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図９】本発明の実施の形態に係る分散システムの動作を説明するための図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施の形態について、図面を用いて説明する。多くの変形態様が本発明の技術を用いて達成できること、そして、本発明が説明のために図示された実施形態に限定されないことは、当業者は認識しうるだろう。
【００２８】
ここで、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２９】
図１から図９を参照して、以下に本発明の実施の形態に係る分散システムを説明する。
図１は、本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【００３０】
ここで、以下の説明を容易にするために、いくつかの定義を追加する。本実施形態では、ｎ個のノードにおいて実行されるｍ個のプロセスがある。プロセス毎に事前に選択されたノードの数は、ｎより小さいｋｉで示される。ここで、ｉは、実行しているプロセスの数を示し、ｉ＝１，２，・・・，ｍである。事前に選択されるべき適切なノードのセットは、Ｋｉであり、必ずｋｉ以上である。もし、事前に選択されたノードの一つがリカバリに適している場合、それを「ヒット」と呼ぶ。もし、事前に選択されたノードがどれもリカバリに適していない場合、それを「ミス」と呼ぶ。ヒット率は、Ｐｈと示される。メカニズムは、必ずチェックポインティングとリカバリの２要素である。
【００３１】
図１において、本発明の実施の形態に係る分散システムは、複数のノード１００と、管理装置２００と、を備え、ネットワーク３を介して互いに接続される。
【００３２】
管理装置２００と複数のノード１００は、複数のコンピュータである。管理装置２００と複数のノード１００は、メモリ（図示されない）に組み込まれた、対応するコンピュータプログラムを実行することにより、管理装置２００と複数のノード１００の様々な機能を実現する。ここで、図面において、本発明の主旨に本質的な関連のない要素の構成は、図示されていない。
【００３３】
また、分散システム１の各構成要素は、任意のコンピュータの、ＣＰＵ（Central Processing Unit）、メモリ、メモリにロードされ、本図の構成要素を実現するプログラム、そのプログラムを可能するハードディスクスなどの記憶ユニット、ネットワークに接続用インタフェース等を中心に含む、ハードウェアとソフトウェアの任意の組み合わせによって実現される。そして、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。以下説明する各図は、ハードウェア単位の構成ではなく、機能単位のブロックを示している。
【００３４】
本発明の実施の形態に係る分散システム１は、大規模分散システムにおける障害耐性をサポートするソフトウェアを含む。特に、本実施形態において、システムは、グリッドコンピューティングシステム、Ｐ２Ｐコンピューティングシステム、クラウドコンピューティングシステム、ならびに、ワイヤレスおよびモバイルコンピューティングシステム等を含む。
【００３５】
図２は、図１に示す分散システム１のネットワーク構成を示すブロック図である。
図２に示すように、分散システム１は、「ｎ１１」、「ｎ１２」、および「ｎ１３」、・・・と示される第１ノードと、「ｎ２１」、「ｎ２２」、および「ｎ２３」、・・・と示される第２ノードと、「ｎ３１」、・・・と示される第３ノードと、を含む複数のノード１００を含む。ノードの数は、図２に示す構成に限定されない。ここでは、単に構成の一例を示している。
【００３６】
本実施形態において、第１ノードｎ１１、ｎ１２、・・・は、管理装置２００の制御に従って、複数のプロセスを実行する。これらのプロセスは、管理装置２００によって監視され、障害が検出される。
【００３７】
第２ノードｎ２１、ｎ２２、・・・は、管理装置２００によって選択され、プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードの役割を果たす。複数の予備ノードｎ２１、ｎ２２、・・・は、複数のノード１００が実行するプロセス毎に準備される。管理装置２００は、将来の障害リカバリ用の予備ノードｎ２１、２２を選択する。この動作の詳細については後述する。
【００３８】
第３ノードｎ３１は、障害プロセスに適したチェックポイントデータがなかった場合に、管理装置２００によってリカバリ用に選択される。第３ノードｎ３１の選択については後述する。
【００３９】
図１を参照すると、第１ノードｎ１１は、メモリ１０２、処理部１０４、インタフェース部（Ｉ／Ｆ）１０６、チェックポインティング部１０８、マルチキャスト部１１０、および制御部１１２を有する。第２ノードｎ１２は、第１ノードｎ１１と同じ構成要素に加え、伝送部１２０を有する。管理装置２００は、リソース管理データデータベース２０２、ノード制御部２０４、ノード選択部２０６、事前割り当て部２０８、障害検出部２１０、リカバリ部２１２、およびネットワーク３のインタフェースとして機能するインタフェース部（不図示）を含む。
【００４０】
図３は、図１に示すリカバリ制御部２１２の詳細なブロック図である。
図３に示すように、リカバリ制御部２１２は、判断部２３０と、チェックポイント選択部２３２、新ノード選択部２４０、分割指定部２４２、および再編成部２４４を含む。
【００４１】
図１に示すように、本発明の実施の形態に係る分散システム１は、ネットワーク３を介して互いに接続される複数のノード１００を含み、各ノード１００は、メモリ１０２を有し、複数のノード１００（図１では、「ｎ１１」と示す）は、分散プロセスを実行し、複数のプロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、各ノード１００のメモリ１０２に格納するチェックポインティング部１０８と、各プロセスで障害が発生する前に、複数の将来の障害リカバリ用の予備ノード１００（図１では、「ｎ２１」と示す）をプロセス毎に選択するノード選択部２０６と、チェックポイントデータを選択された予備ノード１００に事前に割り当て、各プロセスで障害が発生する前に、チェックポイントデータを、各プロセスを実行する各ノード１００から、選択された予備ノード１００に送信させ、選択された予備ノード１００に、送信されたチェックポイントデータをメモリ１０２にそれぞれ格納させる事前割り当て部２０８と、プロセスで障害が起きたとき、複数の予備ノード１００の複数のメモリ１０２に格納されている、少なくとも一つのチェックポイントデータが、障害プロセスをリカバリするのに適しているかを判断する判断部２３０（リカバリ制御部２１２）と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの予備ノード１００上で一つのプロセスを実行し、その結果、障害プロセスをリカバリできるチェックポイント選択部２３２（リカバリ制御部２１２）と、リカバリに適しているチェックポイントが一つもないと判断されたとき、障害プロセス用の各予備ノードのメモリ１０２に格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部（分割指定部２４２、リカバリ制御部２１２）と、複数の予備ノード１００のそれぞれのチェックポイントデータの複数の分割部分は、全体として、障害プロセス用の完全なチェックポイントデータに統合され、複数の予備ノード１００からそれぞれチェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノード（図１には示されていない）にネットワーク３を介して送信し、新ノード上で、送信したチェックポイントデータの複数の分割部分を完全なチェックポイントデータに再編成し、完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、障害プロセスをリカバリできる再編成部２４４（新ノード選択部１４０、リカバリ制御部２１２）と、を備える。
【００４２】
図１に示すように、第１ノードｎ１１において、メモリ１０２はチェックポイントデータを格納する。処理部１０４は、管理装置２００の制御に従って分散プロセスを実行する。処理部１０４はメモリ（不図示）を使用し、プログラムまたはデータを記憶する。これは本発明の本質には関わらないので、本明細書では詳細な説明は省略する。
【００４３】
インタフェース部１０６は、ネットワーク用インタフェースの機能を果たす。ノード１００は、ネットワーク３上の他のノード１００、管理装置２００、および他の装置（不図示）とインタフェース部１０６を介して通信する。
【００４４】
チェックポインティング部１０８は、複数のプロセスに対しチェックポインティングを実行し、処理部１０４上で実行する各プロセスのチェックポイントデータを生成し、メモリ１０２に生成されたチェックポイントデータを格納する。本実施形態では、チェックポインティング部１０８はインクリメンタルまたは確率的なチェックポインティング、あるいは、それらの組み合わせであるチェックポインティングを実行することができる。
【００４５】
マルチキャスト部１１０は、チェックポインティング部１０８によって生成されたチェックポイントデータを予備ノード（第２ノードｎ２１）にインタフェース部１０６を介してネットワーク３経由でマルチキャストする。
【００４６】
制御部１１２は、管理装置２００の制御に従って、ノード１００の動作を制御する。
第２ノードｎ２１において、受信部１２０は、チェックポイントデータを第１ノードｎ１１からインタフェース部１０６を介して受信し、受信したチェックポイントデータをメモリ１０２に格納する。
【００４７】
管理装置２００において、リソース管理データデータベース２０２は、ノード１００などのリソース上に様々なデータを格納する。ノード制御部２０４は、ノード１００を制御して、本発明に係る分散プロセス、ならびに、チェックポインティングプロセスおよびリカバリプロセスを実行する。
【００４８】
ノード選択部２０６は、プロセス毎の将来の障害リカバリ用の予備ノードｎ２１、ｎ２２、・・・を、各プロセスで障害が発生する前に選択する。ここで、予備ノードｎ２１、ｎ２２、・・・の数はｋである。事前割り当て部２０８は、各プロセスで障害が発生する前に、選択された複数の予備ノードｎ２１にチェックポイントデータを事前に割り当て、各プロセスを実行する各第１ノードｎ１１から選択された複数の予備ノードｎ２１にネットワーク３を介して送信される。
【００４９】
障害検出部２１０は、障害が発生した障害を検出する。障害検出部２１０は、必ずしも管理装置２００に含まれる必要はなく、ネットワーク３上の他の監視装置からプロセスの障害に関する情報を単に受信してもよい。
【００５０】
以下、リカバリ制御部２１２について、図３を参照して詳細に説明する。
判断部２３０は、障害検出部２１０によって障害プロセスが検出されたとき、予備ノードｎ２１のメモリ１０２に、検出された障害プロセスをリカバリするのに適した少なくとも一つのチェックポイントデータが格納されているかを判断する。
判断部２３０は、下記に挙げるいくつかの基準に基づいて判断する。
１．ＣＰＵ負荷。ＣＰＵが高負荷な場合、ノードはリカバリに適していない。この基準は、計算集約型アプリケーションやユーザによって通常採用される。
２．利用可能なメモリ。利用可能なメモリが小さい場合、ノードはリカバリに適していない。この基準は、データ集約型アプリケーションやユーザによって通常採用される。
３．システムユーザによって決めることができるいくつかの他の基準。これは、ユーザのために残された機能である。
【００５１】
チェックポイント選択部２３２は、判断部２３０によって、少なくとも一つのチェックポイントデータがリカバリに適していると判断されたとき、障害プロセスをリカバリするための一つのチェックポイントデータを選択する。そして、チェックポイント選択部２３２は、少なくとも一つの予備ノードｎ２１上で、選択されたチェックポイントデータをアクティブにして、プロセスを実行させ、その結果、障害プロセスがリカバリされる。
【００５２】
チェックポイント選択部２３２は、少なくとも一つのチェックポイントデータがリカバリに適していると判断部２３０によって判断されたとき、チェックポイントデータから適切なリカバリポイントを見つける。リカバリ制御部２１２は、ノード制御部２０４に指示して、選択された予備ノード１００に、障害プロセス用のメモリコンテキストを準備させ、そして、リカバリポイントからリカバリプロセスを再スタートするために、リカバリされたプロセスをアクティブにする。
【００５３】
新ノード選択部２４０は、リカバリ用の新ノードを選択する。チェックポインティング用のノードを事前に選択するため、およびリカバリ用の予備ノードを新たに選択するための選択基準は、本発明では特定しない。なぜなら、システム製造者やユーザ次第だからである。もし、システムがコンピュータによるノードを十分に有するならば、各選択は、空のノードを指し示すだろう。さもなければ、選択は、最も低負荷のノードを指し示すだろう。確かに、アプリケーションの様々な属性は、選択の決定にも影響を及ぼすかもしれない。したがって、様々なアプリケーションとシステムのすべてに適合する基準はない。
【００５４】
分割指定部２４２は、障害プロセス用の予備ノードｎ２１の各々に、メモリ１０２内に存在するチェックポイントデータを１／ｋ分割部分に分割させ、その結果、各予備ノードの１／ｋ分割部分のチェックポイントデータは、全体として障害プロセス用の完全なチェックポイントデータに統合できる。
【００５５】
再編成部２４４は、判断部２３０によって障害プロセスのリカバリに適しているチェックポイントデータが一つのもないと判断されたとき、障害プロセス用の各予備ノードｎ２１に１／ｋ分割部分のチェックポイントデータを新ノード選択部２４０によって選択された新ノードにネットワーク３を介してそれぞれ送信させる。たとえば、どのチェックポイントデータもリカバリに適していない状況では、チェックポイントデータが格納される各ｎ２ｘにおいて、ＣＰＵは高負荷か、または、ほとんどのメモリが利用できないかもしれない。再編成部２４４は、そして、新ノードに、送信された分割部分のチェックポイントデータを、障害プロセス用の完全なチェックポイントデータに再編成させて、アクティブにしてプロセスを実行させ、その結果、障害プロセスをリカバリできる。リカバリ制御部２１２は、そして、ノード制御部２０４に指示して、新ノードに障害プロセス用のメモリコンテキストを準備させ、そして、リカバリされたプロセスをアクティブにする。
【００５６】
チェックポインティングとリカバリのメカニズムについて以下詳細に説明する。
（チェックポインティング）
プロセスは、インクリメンタルにチェックポイントされ、チェックポイントデータはノードｎ１１（図１）のローカルメモリ１０２に格納され、ｋｉ個の予備ノードｎ２１（図１）のリモートメモリ１０２にマルチキャストで同時に送信される。ｋｉ個のリモートメモリ１０２は、いくつかの基準に従い選択され、たとえば、他より少ないプロセスを実行している最初のｋｉ個のノードや、他より多くのメモリを有する最初のｋｉ個のノード、あるいは、ｎ個のノードからランダムに選択されたｋｉ個のノードなどである。ｎ個からｋｉ個のノードを選択する基準は、個々のアプリケーションまたはシステムに関連する。
【００５７】
プロセスのセットＫｉは、互いに連携するプロセスも極めて異なるため、他のプロセスの他のセットと極めて異なる点に注意する。さらに、プロセス毎のｋｉは、他とは異なってよく、たとえば、ｋｉは、データセンタ内のエネルギを節約するためのより短いプロセスのために、より小さいことが望まれる。このように、ｋｉは一般的に互いに同一ではない。このように、チェックポイントデータの総数は、下記の式１によって示され、事前に選択されるノードの総数は下記の式２によって示される。
【００５８】
【数１】
2013516665.tif 000003
【００５９】
【数２】
2013516665.tif 000004
【００６０】
複数のリモートノードを選択して、Ｎｃｋｐｔ個のデータをｎ個のノードの上に割り当てることは、特定のシステムにおいて技術的問題がある。本明細書では、ｋｉは等しくｋであり、チェックポイントデータをどのノードにも割り当てることができ、かつ、どのノードでも、チェックポイントデータの数は、上限が［(ｋ＋１)×ｍ／ｎ］より大きくならないようなケースが示されているだけである。同様に、ｋｉが異なる場合、ノードでは、異なったプロセスからのチェックポイントデータの数は一般的定義として上限が［（Ｎｃｋｐｔ＋ｍ）／Ｎｓｅｌｅｃｔ］以下である。一方、元の複数のプロセスもまた、チェックポイントデータとして見られるので、ここでは（ｋ＋１）となる。
【００６１】
（リカバリ）
リカバリもまた２要素である。リモートに格納されたチェックポイントデータの一つが障害プロセスのリカバリに適している場合、すなわち、「ヒット」の場合、メモリ内のチェックポイントデータから再構築された新たなプロセスを実行することのみが必要となるので、これが最も速いリカバリとなる。どのチェックポイントデータも障害プロセスをリカバリするのに適していないとき、様々なことが上述した場合より少し複雑になる。すなわち、「ミス」に対するリカバリは「ヒット」に対するリカバリより少し複雑である。最初に、ｋ個のチェックポイントデータがあるので（元のプロセスは障害のため利用できない）、各リモートノードは１／ｋのチェックポイントデータを新たに選択されたノードに送信する。新しいノードは、ノードが空でなければならない、あるいは、最も負荷が低くなければならないなどのいくつかの基準によって選択できる。したがって、データ伝送時間ｔＮは、下記の式３によって示される値となる。
【数３】
2013516665.tif 000005
期待されるリカバリ時間ｔＲは、下記の式４で示されることは容易に分かる。
【数４】
2013516665.tif 000006
もし、ファイ（φ）係数が、下記の式５で示されるファイ（φ）′（ダッシュ）によって表現される値とする場合、我々は、上記の式６によって示される期待されるリカバリ時間ｔＲを得る。
【数５】
2013516665.tif 000007
【数６】
2013516665.tif 000008
【００６２】
したがって、本発明において、期待されるリカバリ時間ｔＲは、上記の式６によって示される値となり、これは、上述した非特許文献に記載される技術によるよりも削減できる。
主な違いは、チェックポイントデータが、予め選択された多数のリモートノードの各メモリに格納されていることである。簡単にするために、本発明では、これらの事前に選択されたノードを将来リカバリ用ノードとして当てにしている。もし、この事前に選択されたリモートノードのうちの一つがリカバリに適しているならば、これが将来のプロセスをリカバリする最も早い方法である。
【００６３】
各チェックポイントデータは、ｋ個の分割部分に任意に分割できる。確かに、分割部分は、等しく、または不ぞろいなサイズ、たとえば、一定の接続帯域幅の等しいサイズにできる。新たに選択されたノードは、ｋ個の分割部分を全てマージして、一つの完全なチェックポイントデータとするだろう。そして、障害プロセスがリカバリされる。
【００６４】
基本的に、少なくとも1つのノードがヒットした場合、リカバリ時間が最も速く、すべてのノードがミスした場合、リカバリ時間は、他の技術で要する時間よりはるかに短い。豊富なリソースがあるシステムでは、ヒット率は非常に高い。わずかなリソースしかないシステムでは、最悪なケースでは、ファイ（φ）係数はファイ（φ）′（ダッシュ）に等しい。
【００６５】
本発明は、将来に賭けているが、本発明はいつも大成功する訳ではない。最悪の場合、ネットワーク伝送コストを考慮すると、リカバリのスピードアップはそれほど魅力的でなく、これは本発明の応用を制限する点からは弱点となる。チェックポイントデータは、リモートノードにマルチキャストされるべきであるので、ネットワーク伝送コストは明らかに高い。本発明では、インクリメンタルおよび確率的なｃｋｐｔｉｎｇが、全てのｃｋｐｔｉｎｇにおける、チェックポイントデータの量を減少させるのに使用され、伝送されるデータは減少する。伝送されるデータを減らすことはできるが、他の技術（ディスクベースチェックポインティングおよびディスクレスチェックポインティング）もまた、インクリメンタルまたは確率的なｃｋｐｔｉｎｇを使うことができ、その結果、ネットワーク伝送コストは比較的高い。
【００６６】
伝送されたデータの絶対量は、特定のシステムで見積もることができ、そして、ネットワーク容量に従って、システムの設計者は、本発明を使用できるかどうか決めることができる。インクリメンタルおよび確率的なチェックポインティングがチェックポイントデータを効果的に減らすことができるので、本発明は、ほとんどのシステムに適している。最終的に、本発明が、他の技術よりどれくらい優位かは、異なるシステム毎に様々であるヒット率Ｐｈに依存するが、最悪の場合であっても本発明は他より速い。
【００６７】
本発明は、分散または集中型耐障害性リソース管理に統合できる。ここでは、概念上のシステムのみを図示し、リソース管理データデータベース２０２、ノード制御部２０４、および管理装置２００の障害検出部は、心拍などのような、最も簡単な、障害が起きたところを検出する既存の方法を意味する。簡単のために、以下では、集中型システムを示し、管理装置２００は、ノードを選択し、障害検出に応答し、どこで障害プロセスをリカバリし、新たに選択されたノードにマージするためのシーケンス番号をチェックポイントデータの各分割部分をマークするかを決定することを含むグローバル制御を行う。
【００６８】
本実施形態の分散システム１は、上述したように搭載されたコンピュータプログラムに従って、様々な処理作業を実行し、それによって、上述したような様々なユニットが様々な機能として実現される。
【００６９】
本実施形態のコンピュータプログラムは、コンピュータに管理装置２００を実現させるプログラムであって、コンピュータに、各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードをプロセス毎に選択する手順、複数のノードに対して指示して、チェックポイントデータを選択された複数の予備ノードに事前に割り当てさせ、各プロセスで障害が発生する前に、チェックポイントデータを、各プロセスを実行する各ノードから、選択された複数の予備ノードに送信させ、選択された複数の予備ノードに、送信されたチェックポイントデータをメモリにそれぞれ格納させる手順、プロセスで障害が起きたとき、複数の予備ノードにおいて、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する手順、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、障害プロセスをリカバリできる手順、障害プロセス用の各予備ノードに対して指示して、メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の予備ノードのそれぞれのチェックポイントデータの複数の分割部分は、全体として、障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、リカバリに適しているチェックポイントが一つもないと判断されたとき、障害プロセス用の複数の予備ノードに対して指示して、それぞれチェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノードにネットワークを介して送信させる手順、新ノードに対して指示して、送信されたチェックポイントデータの複数の分割部分を完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、障害プロセスをリカバリできる手順を実行させるためのプログラムである。
【００７０】
上述したように構成された本実施形態の分散システム１における障害リカバリの方法について、以下説明する。図４は、本実施形態の分散システム１の動作の一例を示すフローチャートである。
【００７１】
本実施形態の方法は、ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおける障害リカバリ方法であって、複数のノードは、分散プロセスを実行し、その方法は、複数のプロセスに対しチェックポインティングを行い（ステップＳ１０５）、各プロセス用にチェックポイントデータを生成し、各ノードのメモリに格納し、各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードをプロセス毎に選択し、チェックポイントデータを前記選択された予備ノードに事前に割り当て（ステップＳ１０３）、各プロセスで障害が発生する前に、チェックポイントデータを、各プロセスを実行する各ノードから、選択された予備ノードに送信させ、選択された予備ノードに、送信されたチェックポイントデータをメモリにそれぞれ格納させ、プロセスで障害が起きたとき（ステップＳ１０９の「ＹＥＳ」）、複数の予備ノードの複数のメモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断し（ステップＳ１１１）、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき（ステップＳ１１１の「ヒット」）、障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの予備ノード上で一つのプロセスを実行し、その結果、障害プロセスをリカバリでき、リカバリに適しているチェックポイントが一つもないと判断されたとき（ステップＳ１１１の「ミス」）、障害プロセスの複数の予備ノードのメモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し（ステップＳ１２３）、複数の予備ノードのそれぞれのチェックポイントデータの複数の分割部分は、全体として、障害プロセス用の完全なチェックポイントデータに統合され、複数の予備ノードからそれぞれチェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノードにネットワークを介して送信し（ステップＳ１２５）、新ノードで、送信したチェックポイントデータの複数の分割部分を完全なチェックポイントデータに再編成し、完全なチェックポイントデータをアクティブにし、プロセスを実行させ（ステップＳ１２７）、その結果、障害プロセスをリカバリできる。
【００７２】
より詳細には、分散システムにおいて、管理装置２００が、図５に示される、たとえば、第１ノードｎ１１、ｎ１２、ｎ１３、およびｎ１４などのノード１３０上に複数のプロセスをディスパッチする。管理装置２００からの指示に従い、複数のノード１３０が複数のプロセスを実行する（ステップＳ１０１）
【００７３】
管理装置２００のノード選択部２０６が、各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノード１４０（ｎ２１、ｎ２２、ｎ２３、ｎ２４、およびｎ２５）を選択する（ステップＳ１０３）。たとえば、図５に示すように、ノード１４０（ｎ２１、ｎ２２、およびｎ２４）が、ノード１３０（ｎ１１）によって実行されるプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２１、ｎ２２、およびｎ２５）が、ノード１３０（ｎ１２）によって実行されるプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２２、ｎ２３、およびｎ２４）が、ノード１３０（ｎ１３）が実行しているプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２３、ｎ２４，およびｎ１５）が、ノード１３０（ｎ１４）によって実行されているプロセスのリカバリ用の予備ノードとして選択される。
【００７４】
図３のフローチャートに戻り、ノード１３０において、チェックポインティング部１０８が、インクリメンタルチェックポインティングを実行して、チェックポイントデータを生成し、メモリ１０２に格納する（ステップＳ１０５）。ノード１３０において、マルチキャスト部１１０が、実行しているプロセスのための生成されたチェックポイントデータを、予備ノード１４０にマルチキャストする（ステップＳ１０６）。そして、予備ノード１４０が、チェックポイントデータを受信し、受信したチェックポイントデータをメモリ１０２にそれぞれ格納する。たとえば、図５に示すように、ノード１３０（ｎ１１）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１１」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）にネットワーク３を介して送信される。ノード１３０（ｎ１２）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１２」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２５）にネットワーク３を介して送信される。ノード１３０（ｎ１３）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１３」は、予備ノード１４０（ｎ２２、ｎ２３、およびｎ２４）にネットワーク３を介して送信される。ノード１３０（ｎ１４）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１４」は、予備ノード１４０（ｎ２３、ｎ２４、およびｎ２５）にネットワーク３を介して送信される。
【００７５】
チェックポイントデータ「ＣＫＰＴ１２」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）によって受信され、そして、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）のメモリ１０２に格納される。
図３のフローチャートに戻り、管理装置２００の障害検出部２１０がノード１３０によって実行される動作中のプロセスを監視する（ステップＳ１０７）。管理装置２００の障害検出部２１０によってプロセスの障害が検出されたとき（ステップＳ１０９の「ＹＥＳ」）、管理装置２００の判断部２３０が、少なくとも一つのチェックポイントデータが予備ノード１４０上の検出された障害プロセスをリカバリするのに適しているかを判別する（ステップＳ１１１）。ここでは、障害はノード１３０（ｎ１２）によって実行されるプロセス内で発生している。
【００７６】
管理装置２００の判断部２３０が、少なくとも一つのチェックポイントデータがリカバリに適していると判断したとき（ステップＳ１１１の「ヒット」）、管理装置２００のチェックポイント選択部２３２が、メモリ１０２内のチェックポイントデータ「ＣＫＰＴ１２」を格納している予備ノード１４０（ｎ２１、ｎ２２およびｎ２５）から１つを選択する。この場合、予備ノードｎ２１が管理装置２００のチェックポイント選択部２３２によって選択されたとする。図６に示すように、管理装置２００のリカバリ制御部２１２が、障害ノード１５０（ｎ２１）に、ネットワーク３を介してプロセスをリカバリするよう指示する。
【００７７】
管理装置２００の指示に従い、ノード１６０（ｎ２１）の制御部１１２が、メモリ１０２内に格納されているチェックポイントデータをアクティブにし、処理部１０４にプロセスを実行させ、その結果、障害プロセスがリカバリされる（ステップＳ１１３）。このようにして、適切なリカバリ用のチェックポイントデータを有する予備ノード１４０を用いて直接的なリカバリが行える。
【００７８】
フローチャートのステップをステップＳ１０３に戻り、図７に示すように、管理装置２００のノード選択部２０６が、新ノードを選択し、再度、障害ノード１５０（ｎ２１２）の代わりにプロセスを新たに開始するノード１６０（ｎ２１）によって実行されるプロセス要の予備ノード１４０（ｎ２２、ｎ２３、およびｎ２５）を選択する。したがって、ノード１４０（ｎ２５）は、ノード１６０（ｎ２１）の代わりに、ノード選択部２０６によって追加的に選択される。
【００７９】
管理装置２００の判断部２３０がどのチェックポイントデータも障害リカバリに適していないと判断したとき（ステップＳ１１１の「ミス」）、管理装置２００の新ノード選択部２４０の分割指定が、分散システム１の中からリカバリ用の新ノードを選択する。ここで、図８に示すように、ノード１７０（ｎ３１）が、管理装置２００の新ノード選択部２４０によってリカバリ用の新ノードとして選択される（ステップＳ１２１）。
【００８０】
そして、管理装置２００の分割指定部２４２が、ノード１４０（ｎ２１、ｎ２２、およびｎ２５）に指示して、メモリ１０２に格納されている既存のチェックポイントデータを、障害プロセスのために、いくつかの分割部分、ここでは３つの分割部分に分割させる。さらに、管理装置２００の分割指定部２４２が、ノード（ｎ２１、ｎ２２、およびｎ２５）に指示して、予備ノード（ｎ２１、ｎ２２、およびｎ２５）それぞれの分割部分のチェックポイントデータを統合して障害プロセス用の完全なチェックポイントデータに統合するために、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２５）それぞれのチェックポイントデータの分割部分を順次、指定する（ステップＳ１２３）。
【００８１】
管理装置２００の指示に従って、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２５）の各々の制御部１１２が、メモリ１０２に格納されている既存のチェックポイントデータを３つの分割部分に分割する。さらに、管理装置２００からの指示に従って、各ノード１４０（ｎ２１、ｎ２２、およびｎ２５）の制御部１１２が、チェックポイントデータの３分の１の分割部分の一つを新ノード１７０（ｎ３１）にネットワーク３を介して送信する（ステップＳ１２５）。
【００８２】
新ノード１７０（ｎ３１）は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２５）それぞれから３分の１分割のチェックポイントデータを計３つネットワーク３を介して受信する。上述したように、３つの３分の１分割のチェックポイントデータは、全体として、障害プロセス用の完全なチェックポイントデータに統合できる。新ノード１７０（ｎ３１）の制御部１１２が、上述したチェックポイントの分割部分を、障害プロセス用の完全なチェックポテンシャルデータに統合する。制御部１１２が、チェックポイントデータをアクティブにして、管理装置２００の制御に従い、処理部１０４に、チェックポイントデータからプロセスを再スタートさせ、その結果、障害プロセスをリカバリできる（ステップＳ１２７）。
【００８３】
したがって、ノード１７０（ｎ３１）は、図９に示すように、障害ノード１３０（ｎ１２）の代わりにプロセスを実行できる。このフローチャートのステップはステップＳ１０３に戻る。
【００８４】
以上、本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【００８５】
システムの上記実施形態において、複数のプロセスが複数のノードによってそれぞれ実行される。すなわち、一つのプロセスが一つのノードのみによって実行される。しかし、一つのプロセスが複数のノードによって実行されてもよい。この場合もまた、上記実施形態と同様な方法で実行できる。
【００８６】
他の実施形態において、再編成部２４４は、新しく事前に割り当てられたノードを追加してもよいし、または新たに事前に割り当てたノードに事前に割り当てたノード内のデータを移動してもよく、その結果、各プロセスのチェックポイントデータの第１の数と、システムの最も初期に定義を満たす各事前に割り当てたノード内のチェックポイントデータの第２の数とを保証できる。
【００８７】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８８】
この出願は、２０１０年１月４日に出願された日本出願特願２０１０−０００２６８号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2013516665.tif 000009
【図２】
2013516665.tif 000010
【図３】
2013516665.tif 000011
【図４】
2013516665.tif 000012
【図５】
2013516665.tif 000013
【図６】
2013516665.tif 000014
【図７】
2013516665.tif 000015
【図８】
2013516665.tif 000016
【図９】
2013516665.tif 000017
【手続補正書】
【提出日】平成24年7月2日(2012.7.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおいて、複数の前記ノードは、プロセスをそれぞれ実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納し、
前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の複数の予備ノードを前記プロセス毎に選択し、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させ、
障害が発生した障害プロセスを検出し、
前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断し、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリでき、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセスの複数の前記予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノードで、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる障害リカバリ方法。
【請求項２】
請求項１に記載の障害リカバリ方法において、
前記複数予備ノードを選択する際、
残りのノードより少ないプロセスを実行している一つのノードを優先して選択する第１の方法、残りのノードより大きいメモリ容量を有する一つのノードを優先して選択する第２の方法、および、ランダムに一つのノードを選択する第３の方法を含む複数の方法の中から選択した方法で、前記将来の障害リカバリ用の複数予備ノードを選択する障害リカバリ方法。
【請求項３】
請求項１または２に記載の障害リカバリ方法において、
前記各プロセスに障害が発生する前に、前記プロセス毎にｋ個の予備ノードを選択し、
前記ネットワークを介して選択されたｋ個の予備ノードに対し、前記チェックポイントデータをマルチキャストし、
前記ｋ個の予備ノードの各々の前記メモリに前記チェックポイントデータを格納し、
前記障害プロセスの検出に呼応して、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の前記ｋ個の予備ノードの各々におれる前記チェックポイントデータを、１／ｋ分割部分に複数に分割し、ｋ個の予備ノードの各々のチェックポイントデータの１／ｋ分割部分は、全体として前記障害プロセス用の完全なチェックポイントデータに統合され、前記チェックポイントデータの前記１／ｋ分割部分を前記ネットワークを介して前記新ノードに前記ｋ個の予備ノードからそれぞれ送信する障害リカバリ方法。
【請求項４】
請求項３に記載の障害リカバリ方法において、
プロセス毎に、前記ｋが他のプロセスと異なる場合、前記予備ノードの前記メモリ内に格納されるチェックポイントデータの数の閾値は、上限が［（Ｎｃｋｐｔ＋ｍ）／Ｎｓｅｌｅｃｔ］であり、ここで、前記Ｎｃｋｐｔは各プロセス用のチェックポイントデータの総数であり、前記ｍは、前記ｎ個のノードで実行しているプロセスの数であり、前記Ｎｓｅｌｅｃｔは、前記予備ノードの総数である障害リカバリ方法。
【請求項５】
請求項３または４に記載の障害リカバリ方法において、
各プロセスのｋが同じ場合、異なるプロセスからのチェックポイントデータの数は、上限が［（ｋ＋１）×ｍ／ｎ］以下である障害リカバリ方法。
【請求項６】
請求項３乃至５いずれかに記載の障害リカバリ方法において、
さらに、前記予備ノードの各々から前記新ノードに、分割された１／ｋチェックポイントデータを送信し、前記分割された１／ｋデータは互いに異なり、
前記障害プロセスをリカバリするために、前記新ノードにおいて送信されたチェックポイントデータを再編成し、
前記障害プロセス用のメモリコンテキストを準備し、
そして、リカバリされたプロセスをアクティブにする障害リカバリ方法。
【請求項７】
請求項１乃至５いずれかに記載の障害リカバリ方法において、
さらに、リカバリに適した少なくとも一つのチェックポイントデータがあると判断されたとき、前記チェックポイントデータから適切なリカバリポイントを見つけ、
そして、前記障害プロセス用のメモリコンテキストを準備し、
前記リカバリポイントから再スタートすることによって、新たにリカバリされたプロセスを実行するのに適した前記予備ノード内でリカバリすべきプロセスを最終的にアクティブにする障害リカバリ方法。
【請求項８】
請求項１乃至７いずれかに記載の障害リカバリ方法において、
前記チェックポインティングは、インクリメンタルまたは確率的なチェックポイント、あるいは、それらの組み合わせである障害リカバリ方法。
【請求項９】
請求項１乃至８いずれかに記載の障害リカバリ方法において、
複数の前記分割部分の再編成は、
新しい事前に割り当てられたノードを追加する、または、前記新しい事前に割り当てられたノードに、事前に割り当てられたノード内のデータを移動することを含み、各プロセスのチェックポイントの第１の数と、システムの最も初期に定義を満たす各事前に割り当てられたノード内のチェックポイントデータの第２の数とを保証する障害リカバリ方法。
【請求項１０】
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードと、複数の前記ノードは、プロセスをそれぞれ実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納するチェックポインティング部と、
前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の複数の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる割り当て部と、
障害が発生した障害プロセスを検出する検出部と、
前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の各予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノード上で、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える分散システム。
【請求項１１】
分散システムにおける障害リカバリのための管理装置であって、前記分散システムは、ネットワークを介して互いに接続される複数のノードを含み、複数の前記ノードの各々はメモリを有し、複数の前記ノードはプロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の複数の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリに格納させる事前割り当て部と、
障害が発生した障害プロセスを検出する検出部と、
前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにするリカバリ部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記チェックポイントデータの複数の分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させ、前記新ノードに、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える管理装置。
【請求項１２】
管理装置を実現するコンピュータによって実行可能な記録媒体に記録されたコンピュータプログラムであって、複数のノードは、分散システム内で、ネットワークを介して互いに接続され、複数の前記ノードの各々は、メモリを有し、複数の前記ノードは、プロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記コンピュータに、
前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の複数の予備ノードを前記プロセス毎に選択する手順、
複数のノードに対して指示して、前記チェックポイントデータを前記選択された複数の予備ノードに事前に割り当てさせる手順、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された複数の予備ノードに送信させ、前記選択された複数の予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる手順、
障害が発生した障害プロセスを検出する手順、
前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する手順、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順、
前記障害プロセス用の各前記予備ノードに対して指示して、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の複数の前記予備ノードに対して指示して、それぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させる手順、
前記新ノードに対して指示して、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順を実行させるためのコンピュータプログラム。
【請求項１３】
分散システムにおけるノードであって、
複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、
複数の前記プロセスに対しチェックポインティングを行い、プロセス毎にチェックポイントデータを生成するチェックポインティング部と、
前記チェックポイントデータを格納するメモリと、
前記管理装置から指定された前記動作しているプロセスの将来の障害リカバリ用の複数の予備ノードに前記チェックポイントデータをマルチキャストし、前記指定された複数の予備ノードに、前記受信したチェックポイントデータを前記メモリにそれぞれ格納させるマルチキャスト部と、を備えるノード。
【請求項１４】
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、動作しているノード用の予備として機能し、
前記プロセスを実行している他のノードからチェックポイントデータを前記ネットワークを介して受信する受信部と、
受信したチェックポイントデータを格納するメモリと、
前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、
プロセスが障害を起し、かつ前記管理装置が、前記メモリに格納された前記チェックポイントデータが前記障害をリカバリするのに適していると判断したとき、前記管理装置の制御に従って、前記メモリに格納された前記チェックポイントデータをアクティブにし、前記処理部にプロセスを実行させ、その結果、障害プロセスをリカバリできるアクティブ化部と、
プロセスが障害を起し、かつ前記管理装置が、リカバリに適しているチェックポイントが一つもないと判断したとき、前記管理装置の制御に従って、前記メモリ内の現存するチェックポイントデータを、障害プロセス用に、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、
前記チェックポイントデータの複数の前記分割部分のうち一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信する送信部と、を備えるノード。
【請求項１５】
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、
将来の障害リカバリ用に予め準備された複数の予備ノードのそれぞれからチェックポイントデータの分割部分を受信し、プロセスをリカバリするためのチェックポイントデータを確保する受信部と、前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、
プロセスが障害を起こしたとき、前記管理装置の制御に従い、受信した前記チェックポイントデータの異なる複数の前記分割部分を、前記障害プロセス用の前記完全なチェックポイントデータに再編成し、アクティブにして、前記処理部にプロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備えるノード。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
一つの実施形態において、ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおいて、複数の前記ノードは、プロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納し、前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択し、前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させ、障害が発生した障害プロセスを検出し、前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断し、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリでき、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセスの複数の前記予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノードで、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる障害リカバリ方法が提供される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
別の実施形態において、ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードと、複数の前記ノードは、プロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納するチェックポインティング部と、前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、前記チェックポイントデータを前記選択された予備ノードに割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる割り当て部と、障害が発生した障害プロセスを検出する検出部と、前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する判断部と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の各予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部と、前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノード上で、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含む分散システムが提供される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
別の実施形態において、分散システムにおける障害リカバリのための管理装置であって、前記分散システムは、ネットワークを介して互いに接続される複数のノードを含み、複数の前記ノードの各々はメモリを有し、複数の前記ノードはプロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリに格納させる事前割り当て部と、障害が発生した障害プロセスを検出する検出部と、障害プロセスが検出されたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する判断部と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにするリカバリ部と、前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記チェックポイントデータの複数の分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させ、前記新ノードに、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含む管理装置が提供される。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
別の実施形態において、管理装置を実現するコンピュータによって実行可能な記録媒体に記録されたコンピュータプログラムであって、複数のノードは、分散システム内で、ネットワークを介して互いに接続され、複数の前記ノードの各々は、メモリを有し、複数の前記ノードは、プロセスをそれぞれ実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記コンピュータに、前記プロセスのいずれかで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択する手順、複数のノードに対して指示して、前記チェックポイントデータを前記選択された複数の予備ノードに事前に割り当てさせ、前記プロセスのいずれかで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された複数の予備ノードに送信させ、前記選択された複数の予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる手順、障害が発生した障害プロセスを検出する手順、前記プロセスで障害が起きたとき、検出された障害プロセスをリカバリするのに適しているチェックポイントデータが少なくとも一つ、複数の前記予備ノードの複数の前記メモリに格納されているかを判断する手順、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順、前記障害プロセス用の各前記予備ノードに対して指示して、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の複数の前記予備ノードに対して指示して、それぞれ前記チェックポイントデータの複数の前記分割部分の異なる一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させる手順、前記新ノードに対して指示して、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順を実行させるためのコンピュータプログラムが提供される。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】変更
【補正の内容】
【００１９】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、複数の前記プロセスに対しチェックポインティングを行い、プロセス毎にチェックポイントデータを生成するチェックポインティング部と、前記チェックポイントデータを格納するメモリと、前記管理装置から指定された前記動作しているプロセスの将来の障害リカバリ用の複数の予備ノードに前記チェックポイントデータをマルチキャストし、前記指定された複数の予備ノードに、前記受信したチェックポイントデータを前記メモリにそれぞれ格納させるマルチキャスト部と、を備えるノードが提供される。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、動作しているノード用の予備として機能し、前記プロセスを実行している他のノードからチェックポイントデータを前記ネットワークを介して受信する受信部と、受信したチェックポイントデータを格納するメモリと、前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、プロセスが障害を起し、かつ前記管理装置が、前記メモリに格納された前記チェックポイントデータが前記障害をリカバリするのに適していると判断したとき、前記管理装置の制御に従って、前記メモリに格納された前記チェックポイントデータをアクティブにし、前記処理部にプロセスを実行させ、その結果、障害プロセスをリカバリできるアクティブ化部と、プロセスが障害を起し、かつ前記管理装置が、リカバリに適しているチェックポイントが一つもないと判断したとき、前記管理装置の制御に従って、前記メモリ内の現存するチェックポイントデータを、障害プロセス用に、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、前記チェックポイントデータの複数の前記分割部分のうち一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信する送信部と、を備えるノードが提供される。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００２１
【補正方法】変更
【補正の内容】
【００２１】
別の実施形態において、分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、前記管理装置の制御に従ってプロセスを実行して動作させる処理部と、将来の障害リカバリ用に予め準備された複数の予備ノードのそれぞれからチェックポイントデータの分割部分を受信し、プロセスをリカバリするためのチェックポイントデータを確保する受信部と、前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータを構成し、プロセスが障害を起こしたとき、前記管理装置の制御に従い、受信した前記チェックポイントデータの異なる複数の前記分割部分を、前記障害プロセス用の前記完全なチェックポイントデータに再編成し、アクティブにして、前記処理部にプロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を含むノードが提供される。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。
【図１】  本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図２】  図１に示す分散システムのネットワーク構成を示すブロック図である。
【図３】  図１に示す分散システムの管理装置のリカバリ制御部の構成を示すブロック図である。
【図４】  本発明の実施の形態に係る分散システムの動作を示すフローチャートである。
【図５】  本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図６】  本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図７】  本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図８】  本発明の実施の形態に係る分散システムの動作を説明するための図である。
【図９】  本発明の実施の形態に係る分散システムの動作を説明するための図である。
【発明を実施するための形態】
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
第２ノードｎ２１、ｎ２２、・・・は、管理装置２００によって選択され、プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードの役割を果たす。複数の予備ノードｎ２１、ｎ２２、・・・は、複数のノード１００が実行するプロセス毎に準備される。管理装置２００は、将来の障害リカバリ用の予備ノードｎ２１、ｎ２２を選択する。この動作の詳細については後述する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
図１を参照すると、第１ノードｎ１１は、メモリ１０２、処理部１０４、インタフェース部（Ｉ／Ｆ）１０６、チェックポインティング部１０８、マルチキャスト部１１０、および制御部１１２を有する。第２ノードｎ１２は、第１ノードｎ１１と同じ構成要素に加え、伝送部１２０を有する。管理装置２００は、リソース管理データデータベース２０２、ノード制御部２０４、ノード選択部２０６、事前割り当て部２０８、障害検出部２１０、リカバリ制御部２１２、およびネットワーク３のインタフェースとして機能するインタフェース部（不図示）を含む。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００４１
【補正方法】変更
【補正の内容】
【００４１】
図１に示すように、本発明の実施の形態に係る分散システム１は、ネットワーク３を介して互いに接続される複数のノード１００を含み、各ノード１００は、メモリ１０２を有し、複数のノード１００（図１では、「ｎ１１」と示す）は、分散プロセスを実行し、複数のプロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、各ノード１００のメモリ１０２に格納するチェックポインティング部１０８と、各プロセスで障害が発生する前に、複数の将来の障害リカバリ用の予備ノード１００（図１では、「ｎ２１」と示す）をプロセス毎に選択するノード選択部２０６と、チェックポイントデータを選択された予備ノード１００に事前に割り当て、各プロセスで障害が発生する前に、チェックポイントデータを、各プロセスを実行する各ノード１００から、選択された予備ノード１００に送信させ、選択された予備ノード１００に、送信されたチェックポイントデータをメモリ１０２にそれぞれ格納させる事前割り当て部２０８と、プロセスで障害が起きたとき、複数の予備ノード１００の複数のメモリ１０２に格納されている、少なくとも一つのチェックポイントデータが、障害プロセスをリカバリするのに適しているかを判断する判断部２３０（リカバリ制御部２１２）と、少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの予備ノード１００上で一つのプロセスを実行し、その結果、障害プロセスをリカバリできるチェックポイント選択部２３２（リカバリ制御部２１２）と、リカバリに適しているチェックポイントが一つもないと判断されたとき、障害プロセス用の各予備ノードのメモリ１０２に格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部（分割指定部２４２、リカバリ制御部２１２）と、複数の予備ノード１００のそれぞれのチェックポイントデータの複数の分割部分は、全体として、障害プロセス用の完全なチェックポイントデータに統合され、複数の予備ノード１００からそれぞれチェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノード（図１には示されていない）にネットワーク３を介して送信し、新ノード上で、送信したチェックポイントデータの複数の分割部分を完全なチェックポイントデータに再編成し、完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、障害プロセスをリカバリできる再編成部２４４（新ノード選択部２４０、リカバリ制御部２１２）と、を備える。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
制御部１１２は、管理装置２００の制御に従って、ノード１００の動作を制御する。
第２ノードｎ２１において、伝送部１２０は、チェックポイントデータを第１ノードｎ１１からインタフェース部１０６を介して受信し、受信したチェックポイントデータをメモリ１０２に格納する。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
障害検出部２１０は、障害が発生した障害プロセスを検出する。障害検出部２１０は、必ずしも管理装置２００に含まれる必要はなく、ネットワーク３上の他の監視装置からプロセスの障害に関する情報を単に受信してもよい。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】００５５
【補正方法】変更
【補正の内容】
【００５５】
再編成部２４４は、判断部２３０によって障害プロセスのリカバリに適しているチェックポイントデータが一つのもいと判断されたとき、障害プロセス用の各予備ノードｎ２１に１／ｋ分割部分のチェックポイントデータを新ノード選択部２４０によって選択された新ノードにネットワーク３を介してそれぞれ送信させる。たとえば、どのチェックポイントデータもリカバリに適していない状況では、チェックポイントデータが格納される各予備ノードｎ２ｘにおいて、ＣＰＵは高負荷か、または、ほとんどのメモリが利用できないかもしれない。再編成部２４４は、そして、新ノードに、送信された分割部分のチェックポイントデータを、障害プロセス用の完全なチェックポイントデータに再編成させて、アクティブにしてプロセスを実行させ、その結果、障害プロセスをリカバリできる。リカバリ制御部２１２は、そして、ノード制御部２０４に指示して、新ノードに障害プロセス用のメモリコンテキストを準備させ、そして、リカバリされたプロセスをアクティブにする。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】００６５
【補正方法】変更
【補正の内容】
【００６５】
本発明は、将来に賭けているが、本発明はいつも大成功する訳ではない。最悪の場合、ネットワーク伝送コストを考慮すると、リカバリのスピードアップはそれほど魅力的でなく、これは本発明の応用を制限する点からは弱点となる。チェックポイントデータは、リモートノードにマルチキャストされるべきであるので、ネットワーク伝送コストは明らかに高い。本発明では、インクリメンタルおよび確率的なチェックポインティングが、全てのチェックポインティングにおける、チェックポイントデータの量を減少させるのに使用され、伝送されるデータは減少する。伝送されるデータを減らすことはできるが、他の技術（ディスクベースチェックポインティングおよびディスクレスチェックポインティング）もまた、インクリメンタルまたは確率的なチェックポインティングを使うことができ、その結果、ネットワーク伝送コストは比較的高い。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】００７３
【補正方法】変更
【補正の内容】
【００７３】
管理装置２００のノード選択部２０６が、各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノード１４０（ｎ２１、ｎ２２、ｎ２３、ｎ２４、およびｎ２５）を選択する（ステップＳ１０３）。たとえば、図５に示すように、ノード１４０（ｎ２１、ｎ２２、およびｎ２４）が、ノード１３０（ｎ１１）によって実行されるプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２１、ｎ２２、およびｎ２５）が、ノード１３０（ｎ１２）によって実行されるプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２２、ｎ２３、およびｎ２４）が、ノード１３０（ｎ１３）が実行しているプロセスのリカバリ用の予備ノードとして選択される。ノード１４０（ｎ２３、ｎ２４，およびｎ２５）が、ノード１３０（ｎ１４）によって実行されているプロセスのリカバリ用の予備ノードとして選択される。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】００７４
【補正方法】変更
【補正の内容】
【００７４】
図４のフローチャートに戻り、ノード１３０において、チェックポインティング部１０８が、インクリメンタルチェックポインティングを実行して、チェックポイントデータを生成し、メモリ１０２に格納する（ステップＳ１０５）。ノード１３０において、マルチキャスト部１１０が、実行しているプロセスのための生成されたチェックポイントデータを、予備ノード１４０にマルチキャストする（ステップＳ１０６）。そして、予備ノード１４０が、チェックポイントデータを受信し、受信したチェックポイントデータをメモリ１０２にそれぞれ格納する。たとえば、図５に示すように、ノード１３０（ｎ１１）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１１」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）にネットワーク３を介して送信される。ノード１３０（ｎ１２）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１２」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２５）にネットワーク３を介して送信される。ノード１３０（ｎ１３）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１３」は、予備ノード１４０（ｎ２２、ｎ２３、およびｎ２４）にネットワーク３を介して送信される。ノード１３０（ｎ１４）によって実行されるプロセス用のチェックポイントデータ「ＣＫＰＴ１４」は、予備ノード１４０（ｎ２３、ｎ２４、およびｎ２５）にネットワーク３を介して送信される。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】００７５
【補正方法】変更
【補正の内容】
【００７５】
チェックポイントデータ「ＣＫＰＴ１２」は、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）によって受信され、そして、予備ノード１４０（ｎ２１、ｎ２２、およびｎ２４）のメモリ１０２に格納される。
図４のフローチャートに戻り、管理装置２００の障害検出部２１０がノード１３０によって実行される動作中のプロセスを監視する（ステップＳ１０７）。管理装置２００の障害検出部２１０によってプロセスの障害が検出されたとき（ステップＳ１０９の「ＹＥＳ」）、管理装置２００の判断部２３０が、少なくとも一つのチェックポイントデータが予備ノード１４０上の検出された障害プロセスをリカバリするのに適しているかを判別する（ステップＳ１１１）。ここでは、障害はノード１３０（ｎ１２）によって実行されるプロセス内で発生している。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】００７６
【補正方法】変更
【補正の内容】
【００７６】
管理装置２００の判断部２３０が、少なくとも一つのチェックポイントデータがリカバリに適していると判断したとき（ステップＳ１１１の「ヒット」）、管理装置２００のチェックポイント選択部２３２が、メモリ１０２内のチェックポイントデータ「ＣＫＰＴ１２」を格納している予備ノード１４０（ｎ２１、ｎ２２およびｎ２５）から１つを選択する。この場合、予備ノードｎ２１が管理装置２００のチェックポイント選択部２３２によって選択されたとする。図６に示すように、管理装置２００のリカバリ制御部２１２が、ノード１６０（ｎ２１）に、ネットワーク３を介してプロセスをリカバリするよう指示する。
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】００７８
【補正方法】変更
【補正の内容】
【００７８】
フローチャートのステップをステップＳ１０３に戻り、図７に示すように、管理装置２００のノード選択部２０６が、再度、障害ノード１５０（ｎ１２）の代わりにプロセスを新たに開始するノード１６０（ｎ２１）によって実行されるプロセス要の予備ノード１４０（ｎ２２、ｎ２３、およびｎ２５）を選択する。したがって、ノード１４０（ｎ２５）は、ノード１６０（ｎ２１）の代わりに、ノード選択部２０６によって追加的に選択される。
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】００７９
【補正方法】変更
【補正の内容】
【００７９】
管理装置２００の判断部２３０がどのチェックポイントデータも障害リカバリに適していないと判断したとき（ステップＳ１１１の「ミス」）、管理装置２００の新ノード選択部２４０が、分散システム１の中からリカバリ用の新ノードを選択する。ここで、図８に示すように、ノード１７０（ｎ３１）が、管理装置２００の新ノード選択部２４０によってリカバリ用の新ノードとして選択される（ステップＳ１２１）。
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
この出願は、２０１０年１月４日に出願された日本出願特願２０１０−０００２６８号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
本発明は以下の態様も含むことができる。
（付記１）
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードを含むシステムにおいて、複数の前記ノードは、分散プロセスを実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納し、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択し、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させ、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断し、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリでき、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセスの複数の前記予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割し、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノードで、送信した前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる障害リカバリ方法。
（付記２）
付記１に記載の障害リカバリ方法において、
前記複数予備ノードを選択する際、
残りのノードより少ないプロセスを実行している一つのノードを優先して選択する第１の方法、残りのノードより大きいメモリ容量を有する一つのノードを優先して選択する第２の方法、および、ランダムに一つのノードを選択する第３の方法を含む複数の方法の中から選択した方法で、前記将来の障害リカバリ用の複数予備ノードを選択する障害リカバリ方法。
（付記３）
付記１または２に記載の障害リカバリ方法において、
前記各プロセスに障害が発生する前に、前記プロセス毎にｋ個の予備ノードを選択し、
前記ネットワークを介して選択されたｋ個の予備ノードに対し、前記チェックポイントデータをマルチキャストし、
前記ｋ個の予備ノードの各々の前記メモリに前記チェックポイントデータを格納し、
前記障害プロセスの検出に呼応して、リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の前記ｋ個の予備ノードの各々におれる前記チェックポイントデータを、１／ｋ分割部分に複数に分割し、ｋ個の予備ノードの各々のチェックポイントデータの１／ｋ分割部分は、全体として前記障害プロセス用の完全なチェックポイントデータに統合され、前記チェックポイントデータの前記１／ｋ分割部分を前記ネットワークを介して前記新ノードに前記ｋ個の予備ノードからそれぞれ送信する障害リカバリ方法。
（付記４）
付記３に記載の障害リカバリ方法において、
プロセス毎に、前記ｋが他のプロセスと異なる場合、前記予備ノードの前記メモリ内に格納されるチェックポイントデータの数の閾値は、上限が［（Ｎｃｋｐｔ＋ｍ）／Ｎｓｅｌｅｃｔ］であり、ここで、前記Ｎｃｋｐｔは各プロセス用のチェックポイントデータの総数であり、前記ｍは、前記ｎ個のノードで実行しているプロセスの数であり、前記Ｎｓｅｌｅｃｔは、前記予備ノードの総数である障害リカバリ方法。
（付記５）
付記３または４に記載の障害リカバリ方法において、
各プロセスのｋが同じ場合、異なるプロセスからのチェックポイントデータの数は、上限が［（ｋ＋１）×ｍ／ｎ］以下である障害リカバリ方法。
（付記６）
付記３乃至５いずれかに記載の障害リカバリ方法において、
さらに、前記予備ノードの各々から前記新ノードに、分割された１／ｋチェックポイントデータを送信し、前記分割された１／ｋデータは互いに異なり、
前記障害プロセスをリカバリするために、前記新ノードにおいて送信されたチェックポイントデータを再編成し、
前記障害プロセス用のメモリコンテキストを準備し、
そして、リカバリされたプロセスをアクティブにする障害リカバリ方法。
（付記７）
付記１乃至５いずれかに記載の障害リカバリ方法において、
さらに、リカバリに適した少なくとも一つのチェックポイントデータがあると判断されたとき、前記チェックポイントデータから適切なリカバリポイントを見つけ、
そして、前記障害プロセス用のメモリコンテキストを準備し、
前記リカバリポイントから再スタートすることによって、新たにリカバリされたプロセスを実行するのに適した前記予備ノード内でリカバリすべきプロセスを最終的にアクティブにする障害リカバリ方法。
（付記８）
付記１乃至７いずれかに記載の障害リカバリ方法において、
前記チェックポインティングは、インクリメンタルまたは確率的なチェックポイント、あるいは、それらの組み合わせである障害リカバリ方法。
（付記９）
付記１乃至８いずれかに記載の障害リカバリ方法において、
複数の前記分割部分の再編成は、
新しい事前に割り当てられたノードを追加する、または、前記新しい事前に割り当てられたノードに、事前に割り当てられたノード内のデータを移動することを含み、各プロセスのチェックポイントの第１の数と、システムの最も初期に定義を満たす各事前に割り当てられたノード内のチェックポイントデータの第２の数とを保証する障害リカバリ方法。
（付記１０）
ネットワークを介して互いに接続され、メモリをそれぞれ有する複数のノードと、複数の前記ノードは、分散プロセスを実行し、
複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、前記各ノードの前記メモリに格納するチェックポインティング部と、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる割り当て部と、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、選択されたチェックポイントをアクティブにして、少なくとも一つの前記予備ノード上で一つのプロセスを実行し、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の各予備ノードの前記メモリに格納されている現存するチェックポイントデータを、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
複数の前記予備ノードからそれぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信し、前記新ノード上で、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成し、前記完全なチェックポイントデータをアクティブにし、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える分散システム。
（付記１１）
分散システムにおける障害リカバリのための管理装置であって、前記分散システムは、ネットワークを介して互いに接続される複数のノードを含み、複数の前記ノードの各々はメモリを有し、複数の前記ノードは分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択するノード選択部と、
前記チェックポイントデータを前記選択された予備ノードに事前に割り当て、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された予備ノードに送信させ、前記選択された予備ノードに、送信されたチェックポイントデータを前記メモリに格納させる事前割り当て部と、
障害が発生した障害プロセスを検出する検出部と、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する判断部と、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできるチェックポイント選択部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにするリカバリ部と、
前記障害プロセス用の複数の前記予備ノードのそれぞれに、前記チェックポイントデータの複数の分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させ、前記新ノードに、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備える管理装置。
（付記１２）
ノードを実現するコンピュータによって実行可能な記録媒体に記録されたコンピュータプログラムであって、複数の前記ノードは、分散システム内で、ネットワークを介して互いに接続され、複数の前記ノードの各々は、メモリを有し、複数の前記ノードは、分散プロセスを実行し、複数の前記プロセスに対しチェックポインティングを行い、各プロセス用にチェックポイントデータを生成し、
前記コンピュータに、
前記各プロセスで障害が発生する前に、将来の障害リカバリ用の予備ノードを前記プロセス毎に選択する手順、
複数のノードに対して指示して、前記チェックポイントデータを前記選択された複数の予備ノードに事前に割り当てさせる手順、前記各プロセスで障害が発生する前に、前記チェックポイントデータを、前記各プロセスを実行する前記各ノードから、前記選択された複数の予備ノードに送信させ、前記選択された複数の予備ノードに、送信されたチェックポイントデータを前記メモリにそれぞれ格納させる手順、
前記プロセスで障害が起きたとき、複数の前記予備ノードの複数の前記メモリに格納されている、少なくとも一つのチェックポイントデータが、検出された障害プロセスをリカバリするのに適しているかを判断する手順、
少なくとも一つのチェックポイントがリカバリに適していると判断されたとき、前記障害プロセスをリカバリするためのチェックポイントを一つ選択し、少なくとも一つの前記予備ノードに、選択されたチェックポイントをアクティブにさせて、一つのプロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順、
前記障害プロセス用の各前記予備ノードに対して指示して、前記メモリ内の現存するチェックポイントデータを、複数の分割部分に分割させ、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合されるようにする手順、
リカバリに適しているチェックポイントが一つもないと判断されたとき、前記障害プロセス用の複数の前記予備ノードに対して指示して、それぞれ前記チェックポイントデータの複数の前記分割部分を、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信させる手順、
前記新ノードに対して指示して、送信された前記チェックポイントデータの複数の前記分割部分を前記完全なチェックポイントデータに再編成させ、アクティブにさせ、プロセスを実行させ、その結果、前記障害プロセスをリカバリできる手順を実行させるためのコンピュータプログラム。
（付記１３）
分散システムにおけるノードであって、
複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
複数の前記プロセスに対しチェックポインティングを行い、プロセス毎にチェックポイントデータを生成するチェックポインティング部と、
前記チェックポイントデータを格納するメモリと、
前記管理装置から指定された前記動作しているプロセスの将来の障害リカバリ用の複数の予備ノードに前記チェックポイントデータをマルチキャストし、前記指定された複数の予備ノードに、前記受信したチェックポイントデータを前記メモリにそれぞれ格納させるマルチキャスト部と、を備えるノード。
（付記１４）
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、動作しているノード用の予備として機能し、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
前記プロセスを実行している他のノードからチェックポイントデータを前記ネットワークを介して受信する受信部と、
受信したチェックポイントデータを格納するメモリと、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
プロセスが障害を起し、かつ前記管理装置が、前記メモリに格納された前記チェックポイントデータが前記障害をリカバリするのに適していると判断したとき、前記管理装置の制御に従って、前記メモリに格納された前記チェックポイントデータをアクティブにし、前記処理部にプロセスを実行させ、その結果、障害プロセスをリカバリできるアクティブ化部と、
プロセスが障害を起し、かつ前記管理装置が、リカバリに適しているチェックポイントが一つもないと判断したとき、前記管理装置の制御に従って、前記メモリ内の現存するチェックポイントデータを、障害プロセス用に、複数の分割部分に分割するチェックポイント分割部と、複数の前記予備ノードのそれぞれの前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
前記チェックポイントデータの複数の前記分割部分のうち一つを、リカバリ用に新たに選択された一つの新ノードに前記ネットワークを介して送信する送信部と、を備えるノード。
（付記１５）
分散システムにおけるノードであって、複数の前記ノードは、ネットワークを介して互いに接続され、前記ノードを制御する管理装置に前記ネットワークを介して接続され、
前記管理装置の制御に従って分散プロセスを実行して動作させる処理部と、
将来の障害リカバリ用に予め準備された複数の予備ノードのそれぞれからチェックポイントデータの分割部分を受信し、プロセスをリカバリするためのチェックポイントデータを確保する受信部と、前記チェックポイントデータの複数の前記分割部分は、全体として、前記障害プロセス用の完全なチェックポイントデータに統合され、
プロセスが障害を起こしたとき、前記管理装置の制御に従い、受信した前記チェックポイントデータの複数の前記分割部分を、前記障害プロセス用の前記完全なチェックポイントデータに再編成し、アクティブにして、前記処理部にプロセスを実行させ、その結果、前記障害プロセスをリカバリできる再編成部と、を備えるノード。
【国際調査報告】
2013516665.tif 000018
2013516665.tif 000019