(57)【要約】  計算グリッド上に高可用性データ並列操作を実装するための新しい方法を提供する。この新しい方法は、サーバが故障した後、またはグリッドがネットワークの部分的故障を経験した後に高可用性を提供する。本発明は、高可用性分散キャッシュ内の区画に記憶された、選択されたオブジェクトに対してデータ並列操作のメソッドを呼び出す。それにより、本発明は、サーバ故障、またはネットワーク故障の発生後でさえ、データ並列操作の中のメソッド呼出しの進捗を確実に追跡する手段として、分散キャッシュにより実装された高可用性データ区画を使用することによる利益を得る。キャッシュの区画を追跡の基礎として使用することにより、本発明の方法は、メソッド呼出しを再び開始し、それにより、データ並列操作の完了を保証することができるようになる。本発明はまた、キャッシュ内の完了オブジェクトを使用して、データ並列操作の完了が高可用性の方法で検出され、報告されるのを保証する。
2010541100.tif 000002
【特許請求の範囲】
【請求項１】
メソッド呼出しの進捗および完了を追跡することにより、複数のノードを含む計算グリッド内の高可用性データ並列操作を実装する方法であって、
ａ）高可用性分散キャッシュシステムを使用して、各区画に少なくとも１つのデータオブジェクトを含む少なくとも２つの高可用性区画を前記複数のノードに記憶し、残存するノードに故障したノードの前記区画を分配し、
ｂ）前記分散キャッシュの前記ノード上のすべての区画の中の選択されたオブジェクトに対して１組のメソッド呼出しを含むデータ並列操作を実行し、その結果を前記分散キャッシュ内に記憶された別のオブジェクトに統合し、
ｃ）すべての選択されたデータオブジェクトに対する前記メソッド呼出しの完了に関して、開始ノード、または前記開始ノードが故障した場合にはその後継ノードに、各区画に対する前記データ並列操作の完了を報告し、
ｄ）構成するデータオブジェクトすべてについてどの区画が自分の結果を前記開始ノード、またはその後継ノードに報告したかを判断することにより、前記データ並列操作の完了を追跡し、
ｅ）ノードが故障した後に、前記メソッド呼出しの前記開始ノード、またはその後継ノード上でメソッドを実行して、前記故障ノード上のどの区画が結果を報告していないかを判断し、
ｆ）前記残存するノード上の前記区画内の選択されたオブジェクトに対してメソッド呼出しを再び開始する、
ことを含む方法。
【請求項２】
前記データ並列操作の前記メソッド呼出しを実行するノードの前記故障が、ネットワーク通信リンク故障によるものである、請求項１に記載の方法。
【請求項３】
前記データ並列操作の前記メソッド呼出しを実行するノードの前記故障が、ノード自体の故障によるものである、請求項１に記載の方法。
【請求項４】
前記メソッドの完了、または故障に関する前記状態報告が、区画内の少なくとも１つのデータオブジェクトにより送られる、請求項１に記載の方法。
【請求項５】
区画がそのデータオブジェクトを前記メソッド呼出しに応答させなかったことを立証する前記状態報告を受け取ったとき、前記メソッド呼出しの前記開始ノードが、報告結果に満足がいくまで、その区画に前記呼出しを再送する、請求項４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００７年１０月３日に出願された米国仮出願第６０／９９７，６１２号に対し優先権を主張する。
【背景技術】
【０００２】
「計算グリッド」（「計算クラスタ」としても知られる）は、コンピュータネットワークにより相互接続された１組のコンピュータから成り、しばしば「並列アプリケーション」と呼ばれる単一のアプリケーションプログラムを実行するために使用される。各コンピュータを一般に計算「ノード」と呼ぶ。アプリケーションプログラムはさらに計算「タスク」に分割される。各計算タスクは異なるノード上で実行されるコンピュータプログラムの一部である。これらのタスクは、一般に別個のデータを同時に操作し、タスクは、このアプリケーションにより実行される計算全体の一部として互いに通信することもある。
【０００３】
並列アプリケーションの１つの例が、天気シミュレーションモデルであり、このモデルでは、計算グリッドの各ノードが、１日のうちの所与のシミュレーション時刻における世界の別個の地域の天気の影響をモデルするタスクを実行する。これらのタスクを総括したものが、模擬時刻における総合地域の天気システム全体をモデルする。各タスクの一部として、ノードが他のノードと通信して、隣接地域からの天気情報を得る、または引き渡すこともある。並列アプリケーションは、一連の時間間隔全体の天気をモデルする。
【０００４】
並列アプリケーションを構成するタスクを開始する一般的な方法が、１つのノードがすべてのノードに別個のデータ（時には「オブジェクト」と呼ばれることもある）に対し単一の計算機能（時には「メソッド」と呼ばれることもある）を実行するよう指示する「データ並列操作」を実行することである。データ並列操作は、計算グリッドの大部分、またはすべてのノード内の選択されたデータに対する１組の「メソッド呼出し」から成る。性能を最大にするためには、計算ノード上で並列に（すなわち、同時に）これらのメソッド呼出しを実行する。すべてのノードがこの機能を実行し、新しいデータを作成する、または自身の特定の１組のデータを更新する。データ並列操作の実装の一部として、すべてのノードがこのメソッドの実行を完了したときに開始ノードに通知する。これにより、開始ノードが別のデータ並列操作を開始することができる。データ並列操作の一例を図２に示す。
【０００５】
たとえば、上記の天気シミュレーションモデルを表すオブジェクトを１組の領域「ｒ」に対する地域オブジェクトのリスト「ｒｅｇｉｏｎ［ｒ］」として表すことができ、その計算メソッドを関数「ｍｏｄｅｌ＿ｗｅａｔｈｅｒ（）」として表すことができる。この関数が地域オブジェクトを操作する。何らかの手段（分散キャッシュを使用するなど）により、この地域オブジェクトを計算グリッドのノードに分配したと仮定する。データ並列操作では、１つのノードがすべてのノードに対し、割り当てられた地域に対してｍｏｄｅｌ＿ｗｅａｔｈｅｒ（）メソッドを実行するよう指示する。
【０００６】
並列アプリケーションの別の例として、計算グリッドの各ノードが別個の１組の財務資産を分析し、資産ごとの結果を収集するタスクを実行する財務分析アプリケーションがある。たとえば、この分析では、現在の市況に基づいて各資産を分析して、その資産の価値を判断することができる。次に各分析結果を結合して、すべての資産を含む最終報告書にする。
【０００７】
財務分析の例では、上記の財務資産を表すオブジェクトを、１組の顧客「ｃ」に対する資産オブジェクトのリスト「ｐｏｒｔｆｏｌｉｏ［ｃ］」として表すことができ、その計算メソッドを関数「ａｎａｌｙｚｅ＿ｐｏｒｔｆｏｌｉｏ（）」として表すことができる。この関数が資産オブジェクトを操作する。何らかの手段（分散キャッシュを使用するなど）により、資産オブジェクトを計算グリッドのノードに分配したと仮定する。データ並列操作では、１つのノードがすべてのノードに対し、その近傍に記憶された資産オブジェクトに対してａｎａｌｙｚｅ＿ｐｏｒｔｆｏｌｉｏ（）メソッドを実行するよう指示する。これにより、計算グリッドは各ノードの資産オブジェクトの一部を並列に分析して、この操作にかかる時間を最小にする。
【０００８】
データ並列操作は、グリッド内のノードが繰り返し管理者ノードからの独立した作業タスクを求め、受け取る「管理並列操作」（「管理者／ワーカーパラダイム」とも呼ばれる）と呼ばれる、タスクを開始するための別の方法と区別される。両方法とも、様々なアプリケーションでの用途があるが、本発明の対象はデータ並列アプリケーションである。
【０００９】
データ並列操作の実装には、以下の３つのステップを順に実行する必要がある。
【００１０】
１．複数のデータセットに対して、指定されたメソッドを呼び出すために、１つのノードがすべてのノード上のタスクを開始する。
【００１１】
２．すべてのノードが、指定されたメソッドを別個のデータセットに対して実行することにより、そのタスクを実行する。
【００１２】
３．このタスクがすべての指定されたデータセットで完了したことを、すべてのノードが発信元ノード（故障が発生した場合には、その後継ノード）に伝達し、結果を報告し、その結果を統合する。
【００１３】
数１０年にわたり、数多くの並列計算システムがデータ並列操作を実装してきた。しかし、従来の実装では、一般にデータ並列操作の実行中に計算ノード、およびノード間の通信操作が故障しないと仮定していた。故障が発生すれば、データ並列操作を再起動するようになっていた。不都合なことに、財務サービスなどのスピードが重視される多くのアプリケーションでは、データ並列操作を再実行するのに必要な遅延を許容することができない。
【００１４】
サーバ、または通信ネットワークのサーバ部分の故障に耐えるデータ並列操作の実装を「高可用性」実装と言う。本発明は、ノード、またはネットワークの一部分（ネットワーク・インターフェース・カードなど）が、前述の３つのステップのうち１つのステップの間に故障した場合でも、データ並列操作をうまく完了することができるように、高可用性データ並列操作を実行するための方法を説明する。
【００１５】
データ並列操作を実装するために、この数１０年間、数多くの計算グリッド（並列計算システムとしても知られる）が作られてきた。２つの例に、Ｔｈｉｎｋｉｎｇ  Ｍａｃｈｉｎｅｓ社のＣｏｎｎｅｃｔｉｏｎ  Ｍａｃｈｉｎｅ、およびＩｎｔｅｌ  Ｐａｒａｇｏｎ  Ｐａｒａｌｌｅｌ  Ｓｕｐｅｒｃｏｍｐｕｔｅｒが含まれる。つい最近、標準のＴＣＰ／ＩＰ通信ネットワークを使用して、ソフトウェアの形でデータ並列操作を実装するサーバコンピュータのクラスタとして計算グリッドが実装された。しかし、これらの実装のどれも、サーバの故障、または部分的なネットワーク故障後にデータ並列操作を高可用性にするという問題を解決していない。
【００１６】
信頼できる分散計算システムにおいて、１組の協力するコンピュータ用のメンバシップを作成し、サーバ故障後にそのメンバシップを高可用性にするという問題が取り組まれてきた。これらのシステムは、すべての協力するコンピュータ上で実行されるソフトウェア層を提供する。この層は、コンピュータが共通のメンバシップに参加すること、およびメンバシップから退くことを可能にする。これらのシステムは、一種の信頼できるマルチキャストを実装しているので、すべてのコンピュータが確実にマルチキャストメッセージを受け取ることができる。１台のコンピュータが故障すれば、このソフトウェアは新しいメンバシップを形成し、残存するメンバすべてに対して新しいメンバシップを確認する。メンバのコンピュータは、１つまたは複数のコンピュータにメッセージを送ることができ、一般に各メンバシップのどのノードがそのメッセージを受け取ったかを判断することができる。これらの分散計算システムの２つの例が、ＩｓｉｓおよびＥｎｓｅｍｂｌｅである。
【００１７】
信頼できるマルチキャストを使用し、かつ故障が発生した場合にはメンバシップ変更を検出することにより、信頼できる分散計算システムにおいて高可用性な方法でデータ並列操作のステップ１を実装するためのメソッドが作り出された。図２の黒い矢印が、すべてのノードに対するメソッド呼出しを分配するために、信頼できるマルチキャストを使用していることを図示している。しかし、これらのシステムには、データ並列操作の３つのステップすべてが実装されたわけではなかった。特に、これらのシステムは、このメソッドをすべてのデータセットで実行し、かつ発信元ノード（または、故障が発生した場合には、その後継ノード）に完了を通知することを保証するための手段を提供していない。
【００１８】
信頼できる分散計算システムは、主にコンピュータのメンバシップに焦点を当てているので、データ並列操作を完了する目的のために、各コンピュータに割り当てられたデータを追跡する手段を提供していない。コンピュータの故障後に、新しいメンバシップを知ることは、そのメソッドがどのデータセットを完了したか、およびどのデータセットが依然としてノード上でそのメソッドを実行される必要があるかを、残存するノードに伝えることにはならない。また、新しいメンバシップを知ることは、故障したノードが実行することになっていたタスクを残存するノードが再分配することができるように、ノード上のデータセットの配置を管理する手段を提供することにもならない。
【００１９】
ＳｃａｌｅＯｕｔ  Ｓｏｆｔｗａｒｅ、  Ｉｎｃ．およびＴａｎｇｏｓｏｌ社の市販のソフトウェア製品などの分散キャッシュが、データオブジェクトを記憶し、それらを計算グリッド内のすべてのノードが利用できるようにするように作られた（「サーバファーム」としても知られる）。一般に、ノード故障、またはネットワークの一部分の故障後に、すべてのデータオブジェクトを高可用性に保つよう、分散キャッシュを構成することができる。これは、必要があれば、オブジェクトを他のノードに複製し、その複製されたコピーを使用して、ノード故障から回復することにより達成される。さらに、データオブジェクトがすべてのサーバにわたり均等に広がるように、計算グリッド内のノードにデータオブジェクトを自動的に分配するように分散キャッシュを構成することができる。これを行う一般的な方法が、データオブジェクトを「区画（ｐａｒｔｉｔｉｏｎ）」と呼ばれるオブジェクトのグループに分け、ノードに区画を均等に分配することである。区画の数がノードの数よりもはるかに多くなる場合もある（一般に、計算グリッドのノードに負荷を分散させるために区画を使用することは、従来技術で十分に確立されている）。区画化された分散データキャッシュの例を図３に示す。ノードが故障した場合、そのキャッシュの区画が図４に示すように残存するノードに再分配され、そのオブジェクトはその元の区画に割り当てられたままである。区画の数は変わらないままである。
【００２０】
分散計算システムによる信頼できるマルチキャストと組み合わされ、分散キャッシュは、前述のデータ並列操作の中のステップ１、およびステップ２の一部を完了するための優れた基礎となる。まず、このメソッドにより操作されるデータセットを、データオブジェクトとして分散キャッシュに記憶させる。キャッシュは、このデータオブジェクトをキャッシュの区画間に均等に分配することにより、グリッドのノードに均等に分配する。ステップ１で、メソッド呼出しがすべてのノードに確実にマルチキャストされると、各ノードは分散キャッシュがローカルノード上に置いたデータオブジェクトに対してメソッドを呼び出すことができる（分散キャッシュがこれを行うための手段を提供すると仮定する）。データオブジェクトは高可用性なので、ノードの故障、または部分的なネットワーク故障によりアクセスが不可能になった場合にも、データセットは失われない。また、故障後、分散キャッシュは、必要に応じて残存するノードにすべてのオブジェクトを再分配する。
【００２１】
しかしながら、従来技術のこの組み合わせは、データ並列操作のステップ２およびステップ３を完全に実装していないので、データ並列操作全体を高可用性にしない。故障が発生した後、従来技術では、指定されたデータオブジェクトすべてに対してメソッドがうまく呼び出されたこと、およびデータ並列操作の完了が発信元ノード（または、故障が発生した後の、その後継ノード）に伝達されることを保証するという問題を解決しない。
【発明の概要】
【発明が解決しようとする課題】
【００２２】
本発明は、メソッド呼出しの進捗、および完了を追跡することにより、複数のノード（コンピュータ）から成る計算グリッドに高可用性データ並列操作を実装する方法を開示する。
【課題を解決するための手段】
【００２３】
本発明は、高可用性分散キャッシュシステムを利用する。このシステムは、前記複数のノードに少なくとも２つの高可用性区画を記憶し、前記複数のノードの中の各区画内に少なくとも１つのデータオブジェクトを含み、故障したノードの前記区画を残存するノードに分配する。本発明は、計算グリッド上に高可用性データ並列操作を実装するための基礎として、ノードの代わりに、分散キャッシュ内の高可用性区画を使用する。本発明の第１ステップは、分散キャッシュのすべての区画内の選択されたオブジェクトに対して、１組のメソッド呼出しから成るデータ並列操作を実行し、その結果をそのキャッシュ内に記憶された別の高可用性オブジェクトに統合することである。次のステップは、各区画内の選択されたデータオブジェクトすべてに対するメソッド呼出しの完了に関して、開始ノード、または開始ノードが故障した場合にはその後継ノードに各区画でのデータ並列操作の完了を報告することである。どの区画が、構成要素のデータオブジェクトすべてについてのその区画の結果を開始ノード、またはその後継ノードに報告したかを判断することにより、開始ノード、またはその後継ノード上のメソッドがデータ並列操作の完了を追跡する。ノードが故障した後、データ並列操作が最終的に完了するように、このメソッドは、故障したノードのどの区画が結果を報告しなかったかを判断し、前記区画に対するデータ並列操作のためのメソッド呼出しを残存するノード上で再び開始する。
【図面の簡単な説明】
【００２４】
【図１】４つのノードを含む計算グリッドの例である。
【図２】４つのノードを含む計算グリッド上で実行されるデータ並列操作を示す図である。
【図３】計算グリッドに広がる分散区画化データキャッシュを示す図である（従来技術）。
【図４】ノード故障後の分散区画化データキャッシュを示す図である。
【図５】区画化分散キャッシュ内のすべての区画に対するデータ並列操作の呼出しを示す図である。
【図６】本発明における高可用性データ並列操作実装のための一連のステップを示す図である。
【図７】各ノード上でデータ並列操作を実行する方法を示す図である。
【発明を実施するための形態】
【００２５】
図１は、４つのノードを有する計算グリッドの一般的な従来技術の例を示す。図２は、４つのノードを有する計算グリッド上で実行されるデータ並列操作の従来技術の例を示す。この操作は、４つのデータセットにメソッドＭを並列に実行する。この操作はノードのうちどれによっても起動することができることに留意されたい。
【００２６】
図３は、計算グリッドに広がる分散区画化データキャッシュを示す（従来技術）。このデータキャッシュにより、データオブジェクト（図の円）がすべてのノードで大域的にアクセス可能になり、サーバの故障、またはネットワークの一部の故障後に、これらのオブジェクトが高可用性に保たれる。キャッシュは、１組の区画として構成され、各区画は、キャッシュの中にデータオブジェクトのサブセットを保持する。次に、区画がノード全体に均等に分配され、ノード故障、または部分的ネットワーク故障後に、必要に応じて再分配される。これを行う能力は、当業者に知られている。図に示すように、ノードよりも多くの区画があることに留意されたい。
【００２７】
図４は、ノード故障後の分散区画化データキャッシュを示す。残存するノードで区画が再分配されたことに留意されたい。ノードが故障する前の区画の総数は変わらないままであり、すべてのデータオブジェクトがその元の区画に割り当てられたままである。
【００２８】
図５は、本発明のステップ１の、区画化分散データキャッシュ内のすべての区画に対するデータ並列操作の呼出しを示す。この操作のメソッドが、指定された１組のデータオブジェクトに対して呼び出されることに留意されたい。このオブジェクトは、データ区画内に含まれるすべてのオブジェクトのサブセットの場合もある。
【００２９】
本発明の核心は、計算グリッド内の「ノード」の代わりに分散キャッシュの「区画」に対して操作のメソッドを呼び出すことによる、データ並列操作を高可用性にする新しい仕組みを提供することである。区画、およびそれらが含むデータオブジェクトがノード全体に均等に分配されるので、図５に示すように、計算グリッド内のすべてのノードでデータ並列操作が呼び出される。データ並列操作の進捗を追跡するためにデータ区画を使用することで、分散キャッシュの高可用性オブジェクトの中にこの状態情報を保持することによりデータ並列操作の進捗および完了を追跡し、ノード故障後にデータ並列操作を再び開始することが可能になる。区画を使用することが、ノード故障後にどの操作を再び開始しなければならないかを判断する基礎となる。また、このアルゴリズムが従来技術で確立されたいくつかの手段により実行されている間に故障が発生した場合、分散キャッシュが、別のノード（「後継ノード」と呼ぶ）上でこのアルゴリズムを再び開始することができることにも留意されたい。
【００３０】
図６は、本発明の高可用性データ並列操作を実装するための一連のステップを示す。最初のステップでは、すべてのノード上ですべての区画内のすべての選択されたオブジェクトについてデータ並列操作が開始され、ステップ２で、データ並列操作の完了、またはノード故障の報告を待つ。データキャッシュが、すべての区画、およびそれを構成するデータオブジェクトを高可用性のやり方で保持し、その結果、それらはノード故障、または部分的なネットワーク故障に耐え得る。
【００３１】
また、ステップ３で、大域結果オブジェクトへの高可用性の更新として統合操作も実行され、すべての区画からの結果を統合する。区画が各自結果オブジェクト（ＲＯ）を作成し、ステップ３でそれを大域結果オブジェクト（ＧＲＯ）に統合する。この統合操作は、バイナリマージ木などの一連のステップで実行することができ、各ＲＯをＧＲＯに直接統合する必要がないことに留意されたい。大域結果オブジェクトに統合された結果オブジェクトに関する区画リストが、大域結果オブジェクトにより保持される。データキャッシュの区画すべてが結果を報告したとき、データ並列操作が完了したことになる。
【００３２】
図６は、具体的にデータ並列操作の間に故障ノードから回復するためのアルゴリズムを表す。このアルゴリズムは、データ並列操作の開始および完了を遂行するコンピュータノード上で実行される。このアルゴリズムは、データ並列操作の完了を待っている間にノードが故障したことを特定する（分散キャッシュが、ノード故障を報告し、どのノードにどの区画が記憶されているかを報告する仕組みを提供する。ノード故障の明示的な報告を受け取ることによるのではなく、データ並列操作の完了タイムアウトを待つことによるなど、他の手段でもノード故障を特定することができる）。この場合、このアルゴリズムは、大域結果オブジェクト（ＧＲＯ）と一緒に記憶された区画リストを使用して、区画の結果を区画０のＧＲＯに報告しなかった故障ノード上の区画に対するデータ並列操作を再び開始する。分散データキャッシュは、故障から復旧するために、故障したノードの区画を他のノード上に自動的に再ホスティングすることに留意されたい。これにより、データ並列操作が再び開始したときに、残存するノードが、欠けている結果を計算し、最終的にこの操作を完了できるようになる。また、このアルゴリズムが実行されている間に故障が発生した場合、分散キャッシュはこのアルゴリズムを別のノード上で再び開始することができることに留意されたい。
【００３３】
図７は、各ノード上で実行されるデータ並列操作を示す。この操作は、ローカルノード上に常駐する区画内の選択されたオブジェクトすべてに対してデータ並列操作を呼び出す。次に、この操作は、その結果を近傍の結果オブジェクトＲＯに統合する。最後に、この操作は、ＲＯを区画０の大域結果オブジェクトＧＲＯに統合し、分散キャッシュのどの区画が完了したかを報告する。この実装では、直接ＧＲＯにではなく、たとえば、バイナリマージ木の形の他の中間結果オブジェクトにＲＯを統合することができることに留意されたい。ノード故障が発生した場合、図７に示す一連のステップが中断される場合があり、結果が報告されないことになる。この場合、図６に示す一連のステップが、ノード故障のために結果を報告しなかった区画に対するデータ並列操作を再び開始する。
【００３４】
このシーケンスは以下の通りである。
【００３５】
１．１つのノードが、分散キャッシュ内の指定された１組のオブジェクトにメソッド呼出しを分配する。これらのオブジェクトは、データセットを含み、そのデータセットに対してメソッドを呼び出す（従来技術の熟練者により十分に確立された、分散キャッシュの問合せ機構を使用して１組のオブジェクトを選択することができることに留意されたい）。次に、データキャッシュは、各区画内の指定された１組のオブジェクトに対する呼出しのために、メソッド呼出しをすべての区画に分配する。
【００３６】
２．すべてのノード上の分散キャッシュが、各ノード上の区画内のすべてのオブジェクトに対してメソッドを呼び出す。各区画は、メソッド呼出しを完了したオブジェクトを追跡し、高可用性の複製された記憶装置の一部である近傍の「結果オブジェクト」の中にこの情報を記憶する。サーバが故障した場合、または部分的なネットワーク故障後に利用できなくなった場合、分散キャッシュは、残存するノードにその区画を再ホスティングし、これらのノードは、近傍にホスティングしているすべての区画についてメソッド呼出しを完了する。これは、データキャッシュの区画を通常に回復する一環として、近傍の結果オブジェクトを調べ、次に、その区画内の残りのオブジェクトに対してメソッドを呼び出すことにより、完了する（複数の故障により、この復旧過程が繰り返されことになる場合があることに留意されたい）。
【００３７】
３．結果オブジェクトを使用して、分散キャッシュ内の各区画が、その区画に対するすべてのメソッド呼出しをいつ完了したかを判断する。次に、各区画は、すべての区画に関する完了の進捗を記憶する「大域結果オブジェクト」にこの情報を統合する。統合操作は、大域結果オブジェクトに対する更新、または中間結果オブジェクトに対する更新という形をとる。中間結果オブジェクトはその後、大域結果オブジェクトに統合される。最後の統合で、すべての区画が完了を報告したと判断された場合、分散キャッシュは開始ノード（または、故障が発生した場合には、その後継ノード）に信号を送る。大域結果オブジェクトに統合する前、またはその間にノードが故障した場合、故障ノード上の区画に対するメソッド呼出し、および統合操作は、ステップ２のように、必要に応じて、データ区画の正常復旧後に残存するノード上で再び開始される。また、大域結果オブジェクトは、分散キャッシュ内に記憶されたオブジェクトとしてサーバ故障に耐えることが保証されている。
【００３８】
統合操作はまた、ユーザ指定のリダクション操作を実行して、データ並列メソッド呼出しの結果を結合することもできる。たとえば、すべてのデータオブジェクト全体の最大値を計算することができる。このように、本発明のメソッドは、高可用性マップ／リデュースアルゴリズムを実装するのに役立つ。マップ／リデュースアルゴリズムは、従来技術で説明されており、広く使用されている。
【００３９】
高可用性なやり方でデータ並列操作を実装するこの方法には、従来技術にまさる重要な利点が３つある。
【００４０】
・ステップ１では、データキャッシュの区画がすべてのノードにわたり均等に分配され、かつデータオブジェクトがすべての区画にわたり均等に分配されるので、本発明は、ノードに対するメソッドの直接呼出しと同じ拡張性を享受する。これにより、すべてのノードがデータ並列操作に参加し、かつ同量の作業を行うことが保証され、このことは故障発生後でさえも当てはまる。
【００４１】
・データ並列操作を追跡するためにデータ区画を使用することが、当然、サーバ故障、および部分的なネットワーク故障に対処するための基礎となる。区画、およびそれを構成するオブジェクトの数が、サーバ故障、または部分的なネットワーク故障後にも変わらないままなので、区画により、ステップ２のデータ並列操作の進捗を確実に追跡することができ、ステップ３でその操作の完了を確実に報告することができる。データ並列操作の進捗を追跡するために、分散キャッシュのデータ区画、および結果オブジェクトを使用することで、データ複製、および分散キャッシュの復旧により、それらの本来の高可用性を利用している。本発明は、現在のデータ並列システムに欠けている高可用性を提供する。
【００４２】
・データ並列操作を実装し追跡するこの方法はまた、アプリケーションプログラムに、一連のノードメンバシップを追跡させて、ステップ２でどのデータオブジェクトがメソッドを呼び出されたか、またはデータ並列操作により処理されないで残存するかを判断させるという難しさおよび複雑さを回避する。既知のメンバシップ全体に信頼できるマルチキャストを採用する分散計算システムでは、サーバ故障後にどのデータオブジェクトを個々に操作すべきかを知る演繹能力がメンバシップ内のノードにない。故障後のノード全体へのオブジェクトの再分配を実装することは、区画を有する高可用性分散キャッシュを実装することと等価である。本発明は、データ並列操作の完了を追跡する、煩雑でない、より信頼できる方法を構成する。
【００４３】
したがって、本発明の特定の実施形態の説明として本発明を説明してきたが、本発明はそれに限定されるわけではない。本発明の精神および範囲内で詳細を変更することができ、前記精神および範囲は広く解釈され、本書に添付の特許請求の範囲の特徴以外は限定されない。
【図１】
2010541100.tif 000003
【図２】
2010541100.tif 000004
【図３】
2010541100.tif 000005
【図４】
2010541100.tif 000006
【図５】
2010541100.tif 000007
【図６】
2010541100.tif 000008
【図７】
2010541100.tif 000009
【国際調査報告】
2010541100.tif 000010