(57)【要約】【課題】並列分散処理システムにおいて、エントリの移動時間をユーザに意識させず、効率的にエントリを移動する。【解決手段】複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、ノード間の移動が可能な複数のエントリ２２において、並列処理を行う並列分散処理方法および並列分散処理システム１００であって、各エントリ２２において、計算処理を行うとともに、ノード変更されるエントリ２２のデータを、エントリ２２の変更先ノードへ移動することで、エントリ２２の移動を行うことを特徴とする。【選択図】図１
2013069189.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、前記ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、
前記ノードは、
前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動する
ことを特徴とする並列分散処理方法。
【請求項２】
前記ノードは、
前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先ノードへコピーし、
前記計算処理およびコピーの終了後に、前記コピーしたエントリに関するデータを削除する
ことによって、前記移動を行う
ことを特徴とする請求項１に記載の並列分散処理方法
【請求項３】
前記ノードは、
少なくとも前記エントリと、該エントリを有するノードと、該ノードの識別情報と、が組の情報として格納されているパーティションテーブルを有する
ことを特徴とする請求項１または請求項２に記載の並列分散処理方法。
【請求項４】
前記ノードは、
自身の前記ノードに前記残すエントリから計算処理を始め、前記変更元ノードから移動されたデータを用いた計算処理は、前記自身のノードに残すエントリにおける計算処理の終了後に行う
ことを特徴とする請求項１から請求項３のいずれか一項に記載の並列分散処理方法。
【請求項５】
前記ノードは、各エントリの計算処理において、各エントリから異なるエントリへメッセージを送信することが可能であり、各ノードは、自身が保持するエントリが他のエントリから送信されたメッセージを受信するためのバッファを備え、
前記データとともに、前記バッファのデータも変更先ノードへ移動する
ことを特徴とする請求項４に記載の並列分散処理方法。
【請求項６】
前記ノードは、
前記移動エントリから計算処理を始めるとともに、前記計算処理の結果と、前記計算処理に使用したデータを変更先ノードへコピーし、
前記計算処理を行うとともに、前記計算処理に使用したデータを移動し、
前記移動エントリにおける計算処理が終了すると、自身に残すエントリにおける計算処理を行い、当該計算処理の結果を自身の記憶部に格納する
ことを特徴とする請求項１から請求項３のいずれか一項に記載の並列分散処理方法。
【請求項７】
複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、
互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第１のノードと、第２のノードとが存在し、
前記第１のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第２のノードへコピーするとともに、
前記第２のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第１のノードへコピーし、
前記第１のノードで、すべての計算結果が得られたが、前記第２のノードにおいて、計算結果を得ていない場合、
前記第１のノードは、前記第２のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、
次の計算処理が始まった際に、前記第１のノードおよび前記第２のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第１のノードは、前記保持している計算結果を前記第２のノードへコピーする
ことを特徴とする並列分散処理方法。
【請求項８】
前記第１のノードおよび前記第２のノードで行われる、前記計算結果を得ていないエントリにおける計算結果を保持した後における計算処理は、
前記計算結果が保持されているエントリの計算が、後になるよう行われる
ことを特徴とする請求項７に記載の並列分散処理方法。
【請求項９】
前記エントリは、複数のタイプに分類され、
前記並列処理毎に、異なるタイプの前記エントリで、当該並列処理を行う
ことを特徴とする請求項１から請求項８のいずれか一項に記載の並列分散処理方法。
【請求項１０】
複数のノードにおいて並列処理を行う仮想的な計算単位である、複数のエントリが配置されている並列分散処理システムであって、
前記ノードは、
前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動する
ことを特徴とする並列分散処理システム。
【請求項１１】
複数のノードにおいて並列処理を行う仮想的な計算単位である、複数のエントリが配置されている並列分散処理システムであって、
互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第１のノードと、第２のノードとが存在し、
前記第１のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第２のノードへコピーするとともに、
前記第２のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第１のノードへコピーし、
前記第１のノードで、すべての計算結果が得られたが、前記第２のノードにおいて、計算結果を得ていない場合、
前記第１のノードは、前記第２のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、
次の計算処理が始まった際に、前記第１のノードおよび前記第２のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第１のノードは、前記保持している計算結果を前記第２のノードへコピーする
ことを特徴とする並列分散処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
各ノードに配置されているエントリにおいて並列処理を行う並列分散処理方法および並列分散処理システムの技術に関する。
【背景技術】
【０００２】
並列分散処理のフレームワークの１つとしてＰｒｅｇｅｌ（非特許文献１参照）がある。これはグラフ構造に基づく処理を実行するためのフレームワークである。このＰｒｅｇｅｌでは、論理的な計算単位である各エントリ（あるいはｖｅｒｔｅｘ：グラフの頂点）がデータを保持し、エントリ間の仮想的な接続関係であるエッジ（ｅｄｇｅ：辺）を辿ってメッセージのやりとりを行う。各エントリは、他エントリからメッセージを受信すると、受信メッセージと自身が保持するデータに基づき、定められた処理（計算処理）を行い、自身が保持するデータを更新する。また必要に応じてエッジで接続されている別のエントリに対してメッセージを送信する。また、事前に宛先エントリの識別子が分かっている場合は、エッジが定義されていないエントリにもメッセージ送信できる。
【０００３】
各エントリは複数のノード（論理的な計算機）に分散配置されている。そして、各エントリは、ＢＳＰ（Bulk Synchronous Parallel）モデルに従い、エントリ毎に計算およびメッセージ送信処理を実行する。すなわち、計算処理とメッセージ送信は、各エントリ間で同期的かつ交互に行われる。すべてのエントリにおいて計算処理（並列計算処理）が終了した後、各エントリは、メッセージを次のエントリへ送信（メッセージ送信）する。すべてのメッセージについて送信が終了したら、各エントリは再び並列計算処理を行う。従って、ある並列計算処理の結果として送信したメッセージは、次回の並列計算処理で初めて利用可能となる。このようなシステムは、データアクセスの競合を防止したり、処理の一意性（必ず同じ結果になること）を保障したりすることができる。
【０００４】
また、ノードの負荷を均等化する別の技術として、特許文献１に記載の技術がある。この技術における分散型データベース管理システムは、各プロセッサにおける処理負荷の偏りを検出し、このプロセッサにおける処理負荷の偏りを均等化するように、データの分散配置構成を変更するものである。この技術において、各ノードは自身が保持するデータに対して処理（計算）を行うため、データの配置を調整することで、ノードの負荷を均等化することができる。
【０００５】
このような、並列分散処理システムおけるノードの負荷均等化および耐障害性の向上を実現する技術として、特許文献２に記載の技術がある。この技術における分散並列型処理システムは、各データの複製を、本来そのデータを所有するノード以外のノードで作成しておく。そして、あるノードが障害停止した場合や、あるノードの負荷が大きくなった場合、分散並列型処理システムは、そのノードが所有するデータの複製を、保持しているノードが処理を代理実行するものである。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平９−２１８８５８号公報
【特許文献２】特開２００１−１０１１４９号公報
【非特許文献】
【０００７】
【非特許文献１】Ｐｒｅｇｅｌ：  ａ  ｓｙｓｔｅｍ  ｆｏｒ  ｌａｒｇｅ−ｓｃａｌｅ  ｇｒａｐｈ  ｐｒｏｃｅｓｓｉｎｇ，  ＳＩＧＭＯＤ  ２０１０
【発明の概要】
【発明が解決しようとする課題】
【０００８】
非特許文献１に記載の技術は、ノード障害に対する対策としてチェックポイントを利用している。チェックポイントとは、ある瞬間のシステム状態（エントリの状態）をストレージ装置に記録しておき、障害発生時にストレージ装置からデータを読み出し、チェックポイント取得時の配置状態に戻す手法である。
【０００９】
チェックポイントの取得は、エントリの配置が確定している状態で行う必要があるため、システムは、エントリ間のメッセージ送信が終了し、各エントリにおける並列計算処理が行われる直前にチェックポイントを取得する必要がある。すなわち、チェックポイント取得のためだけの処理時間が必要になり、全体的な処理時間が増大するという課題がある。
【００１０】
また、非特許文献１に記載の技術は、ノードの負荷均等化を実現するため、パーティション関数を使ってエントリのノードへの配置方法を決定している。パーティション関数はエントリ識別子を引数として与えると、そのエントリを配置すべきノードの識別子を出力する関数である。この方法ではエントリとノードとの関係が固定的になる。
一方、複数ジョブの同時実行が可能なシステムでは、ジョブ実行前において、すでに他のジョブが実行されている場合や、ジョブ実行中に他のジョブが実行される場合があり、各ノードの余剰リソースの比が動的に変化するという特徴がある。このような計算機環境において、非特許文献１の記載の技術のようなエントリの配置を固定的に決める方法では、各ノードの負荷を均等化できない場合がある。
【００１１】
また、特許文献１に記載の技術は、前記したように、各ノードの処理負荷を均等化するため、ノードへのデータ配置を変更する手法である。この技術を非特許文献１に適用しようとすると、非特許文献１に記載の技術では、エントリの配置が確定している状態でデータ配置の変更を行う必要があるため、チェックポイント取得と同様に、データ配置変更のためだけの処理時間が必要になり、全体として処理時間が増大するという課題がある。
【００１２】
特許文献２に記載の技術は、前記したように、予めデータの複製を異なるノードに作成しておき、あるノードの負荷が高くなったときに複製データを持つノードが処理を代理実行することで、ノードの負荷均等化を実現するものである。しかしながら、このような技術を非特許文献１に記載の技術に適用しようとすると、非特許文献１に記載の技術では、エントリの配置が確定している状態で複製データを作成する必要があるため、チェックポイント取得の場合と同様に、データの複製作成のためだけの処理時間が必要になり、全体として処理時間が増大する。
【００１３】
そのため、並列分散処理システムにおいて、効率的にエントリを移動する技術が求められる。
【課題を解決するための手段】
【００１４】
本発明における一の手段は、複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、前記ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、前記ノードは、前記エントリにおいて、計算処理を行うとともに、ノードが変更されるエントリのデータを、前記エントリの変更先のノードへ移動することを特徴とする。
【００１５】
さらに、本発明の他の手段は、複数のノードを有し、各ノードにおいて動作する仮想的な計算単位であり、ノード間の移動が可能な複数のエントリにおいて、並列処理を行う並列分散処理方法であって、互いに前記エントリのバックアップ元と、前記エントリのバックアップ先の関係にある第１のノードと、第２のノードとが存在し、前記第１のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第２のノードへコピーするとともに、前記第２のノードが計算処理を行い、前記計算処理の結果である計算結果を前記第１のノードへコピーし、前記第１のノードで、すべての計算結果が得られたが、前記第２のノードにおいて、計算結果を得ていない場合、前記第１のノードは、前記第２のノードにおいて、計算結果を得ていないエントリにおける計算結果を保持し、次の計算処理が始まった際に、前記第１のノードおよび前記第２のノードは、計算処理および計算結果のコピーを互いに行うとともに、前記第１のノードは、前記保持している計算結果を前記第２のノードへコピーすることを特徴とする。
その他の解決手段については、実施形態中で説明することとする。
【発明の効果】
【００１６】
本発明によれば、並列分散処理システムにおいて、効率的にエントリを移動することができる。
【図面の簡単な説明】
【００１７】
【図１】本実施形態に係る並列分散処理システムの構成例を示す図である。
【図２】本実施形態に係る計算機のハードウェア構成図である。
【図３】本実施形態に係る並列処理のモデル例を示す図である。
【図４】本実施形態に係る並列処理の動作モデル例を示す図である。
【図５】本実施形態に係るパーティションテーブルの例を示す図でる。
【図６】本実施形態に係るデータテーブルの例を示す図である。
【図７】本実施形態に係るエントリの再配置例を示す図である。
【図８】第１実施形態に係るエントリの再配置における動作を示す図である（その１）。
【図９】第１実施形態に係るエントリの再配置における動作を示す図である（その２）。
【図１０】第１実施形態に係るエントリの再配置における動作を示す図である（その３）。
【図１１】第１実施形態に係るエントリの再配置における動作を示す図である（その４）。
【図１２】第１実施形態に係るエントリの再配置における動作を示す図である（その５）。
【図１３】第１実施形態に係るエントリの再配置における動作を示す図である（その６）。
【図１４】第２実施形態に係るエントリの再配置における動作を示す図である（その１）。
【図１５】第２実施形態に係るエントリの再配置における動作を示す図である（その２）。
【図１６】第２実施形態に係るエントリの再配置における動作を示す図である（その３）。
【図１７】第２実施形態に係るエントリの再配置における動作を示す図である（その４）。
【図１８】第２実施形態に係るエントリの再配置における動作を示す図である（その５）。
【図１９】第３実施形態に係るエントリの再配置における動作を示す図である（その１）。
【図２０】第３実施形態に係るエントリの再配置における動作を示す図である（その２）。
【図２１】第３実施形態に係るエントリの再配置における動作を示す図である（その３）。
【図２２】第３実施形態に係るエントリの再配置における動作を示す図である（その４）。
【図２３】第３実施形態に係るエントリの再配置における動作を示す図である（その５）。
【図２４】第３実施形態に係るエントリの再配置における動作を示す図である（その６）。
【図２５】第３実施形態に係るエントリの再配置における動作を示す図である（その７）。
【図２６】第４実施形態に係る並列処理の動作モデル例を示す図である。
【発明を実施するための形態】
【００１８】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１９】
（システム構成図）
図１は、本実施形態に係る並列分散処理システムの構成例を示す図である。
並列分散処理システム１００は、１つのマスタノード１、複数のスレーブノード２、クライアントノード３を有している。
マスタノード１と、スレーブノード２は、それぞれ論理的な計算機であり、１つのサーバで複数のノード（マスタノード１、スレーブノード２）を実行してもよいし、単独のノードを実行するようにしてもよい。
なお、各ノードは仮想的なネットワーク４で相互に接続されている。
【００２０】
マスタノード１は、スレーブノード２の動作状況を管理する論理的な計算機であり、実際の計算処理はスレーブノード２上で行われる。なお、マスタノード１がスレーブノード２を兼ねることも可能である。
また、並列分散処理システム１００が実行する各ジョブは、複数のタスク２１に分割されて実行される。
【００２１】
マスタノード１は、ジョブマネージャ１１および分散ファイルシステム１２を実行している。
ジョブマネージャ１１は、スレーブノード２におけるジョブや、タスク２１の実行状態を管理する。具体的には、ジョブとタスク２１との対応関係、タスク２１とそのタスク２１を実行するスレーブノード２との対応関係、各タスク２１の進捗率などを管理する。
なお、分散ファイルシステム１２については後記する。
スレーブノード２は、実際の計算処理を行う論理的な計算機であり、少なくとも１つのタスク２１と、タスクマネージャ２３と、分散ファイルシステム２４が実行されている。
タスク２１では、複数のエントリ２２が実行されている。エントリ２２は、タスク２１や、ノード間を移動可能である。
タスクマネージャ２３は、各スレーブノード２で実行中のタスク２１の実行状態（実行中タスク２１の進捗率など）を管理する。タスクマネージャ２３はタスク２１を実行する際、１つのタスク２１に対して複数のスレッドを割り当て実行することで、ＣＰＵ（Central Processing Unit）２０１（図２）がマルチコアの場合にもＣＰＵリソースを有効活用できる。
【００２２】
なお、ファイルサイズが大きい場合、１つのファイルが複数のノードに分割配置されることがある。
分散ファイルシステム１２，２４は、このような場合に、並列分散処理システム１００のようにファイルの本体が複数のノードに分散配置されたときに、同一のパス名で、どのノードからもすべてのファイルへアクセス可能にするためのシステムである。分散ファイルシステム１２，２４を使用すると、アクセスすべきデータが、自身のノードに格納されておらず、他のノードに格納されている場合、他のノードの分散ファイルシステム１２，２４を経由して、データにアクセスする。
スレーブノード２群の負荷状況に応じて、生成したタスク２１の実行スレーブノードが動的に決定されるため、計算処理を実際に実行するスレーブノード２をどれにするかは事前に決まっていない。分散ファイルシステム１２，２４を使用することによって、どのスレーブノード２でタスク２１が実行された場合も、そのタスク２１は指定したファイルの指定したデータ位置にアクセスすることが可能となる。
【００２３】
クライアントノード３はユーザインタフェースを提供する計算機端末である。利用者がクライアントノード３を操作して、並列分散処理システム１００にジョブ実行指示を通知すると、クライアントノード３はマスタノード１のジョブマネージャ１１にジョブ実行指示を送信する。ジョブマネージャ１１は指示されたジョブを複数のタスク２１に分割し、スレーブノード２のタスクマネージャ２３に各タスク２１を配布し、タスクマネージャ２３に実行指示する。
【００２４】
各スレーブノード２が複数のジョブを同時実行する場合は、図１に示すように、１つのスレーブノード２内に複数のタスク２１が生成される場合がある。
【００２５】
ジョブマネージャ１１とタスクマネージャ２３は並列分散処理システム１００に常に常駐しており、サービスプロセスとして動作する。すなわち、ジョブを実行していないときは、ジョブマネージャ１１とタスクマネージャ２３は利用者からのジョブ実行要求を待つ待機状態となっている。また、タスク２１はジョブを実行するたびに動的に生成されるプロセスであり、ジョブ実行を開始すると、タスクマネージャ２３はタスク２１に対応するプロセスを動的に生成する。異なるジョブ同士が影響しあうと、ジョブ実行の性能や安定性が低くなる場合があるため、タスクマネージャ２３は、異なるジョブを異なるプロセスに分離することで、ジョブ同士の影響を低減している。
【００２６】
（ハードウェア構成）
図２は、本実施形態に係るマスタノードや、スレーブノードを実行する計算機のハードウェア構成図である。
計算機２００は、ＣＰＵ２０１、ＬＡＮ（Local Area Network）２５０に接続されるＬＡＮ  Ｉ／Ｆ(Interface)２０２、入出力Ｉ／Ｆ２０３、メモリ２０４、ディスクＩ／Ｆ２０５がバス２０６を介して内部で接続されている。入出力Ｉ／Ｆ２０３には、キーボード２１０、マウス２２０、ディスプレイ２３０が接続されており、利用者はこれらを使用してジョブの実行を指示する。ディスクＩ／Ｆ２０５には、ＯＳ（Operating System）や、各ノードで動作するサービスプロセスのプログラムや、処理を行うための解析対象データが記録されているＨＤＤ（Hard Disk Drive）２４０が接続されている。並列分散処理システム１００（図１）起動時にディスク装置１０９から各プログラムがメモリ２０４に読み込まれ、ＣＰＵ２０１がプログラムを実行することで、ジョブマネージャ１１、タスク２１、エントリ２２、タスクマネージャ２３などが具現化する。なお、マスタノード１（図１）とスレーブノード２（図２）を実行している計算機２００については、ユーザが直接入出力操作を行うことはないため、キーボード２１０、マウス２２０、ディスプレイ２３０を省略することができる。
【００２７】
（並列処理モデル）
図３は、本実施形態に係る並列処理のモデル例を示す図である。なお、以下、本実施形態に係る並列分散処理システム１００を、適宜「本システム１００」あるいは「システム１００」と称することがある。
本システム１００では、キー−データ値形式のデータを保持するエントリ２２（２２ａ〜２２ｃ）同士が相互にメッセージを交換する。例えば、エントリ２２ａは「ｋ１」というキーと「ｖ１１」というデータ値を保持している。同様に、エントリ２２ｂは「ｋ２」というキーと「ｖ２１」というデータ値を保持しており、エントリ２２ｃは「ｋ３」というキーと「ｖ３１」というデータ値を保持している。
【００２８】
キーはエントリ２２の識別子であり、エントリ２２の生成時に作成され、ジョブの実行中は変更されることはない。データ値はエントリ２２が保持するデータそのものであり、並列処理を実行する過程で変更される場合がある。
各エントリ２２は、他のエントリ２２からメッセージを受信すると、自身が保持するデータ値と受信したメッセージに基づいて計算処理を行い、必要に応じてデータ値を更新し、他のエントリ２２に新たなメッセージを送信する。この処理はユーザプログラムとして実装される。メッセージ送信は送信先エントリのキーを指定することで行われる。各エントリ２２はシステム１００内のスレーブノード２に分散配置されるが、各エントリ２２がどのスレーブノード２に配置されているかは、ジョブマネージャ１１が管理しているため、ユーザプログラムはメッセージの送信先スレーブノード２を指定する必要はない。
【００２９】
ここで、データ値は１つの値である必要はなく、複数の値の組であっても、ネスト構造であってもよい。従って、データ値の更新処理においてデータ値全体を更新する場合もあるし、データ値の一部を更新する場合もある。
【００３０】
図４に示すように、本システム１００では、ＢＳＰモデルに基づき、一連の並列計算とメッセージ送信とが同期しながら実行される。なお、図４において、符号２２ａ〜２２ｃは図３と同様であるため、説明を省略する。
例えば「Ｐｈａｓｅ１」では、各エントリ２２は、ユーザプログラムに記載された処理（計算処理、データ値更新、メッセージ送信など）を行う。各エントリ２２の処理は並列実行され、すべてのエントリ２２の処理が完了するまで待つ（同期）。すべてのエントリ２２で、処理が完了したら、システム１００は「Ｐｈａｓｅ２」に移行し、各エントリ２２は再びユーザプログラムに記載された処理を行う。このとき、「ｖ１１」、「ｖ２１」、「ｖ３１」の各データ値は、「ｖ１２」、「ｖ２２」、「ｖ３２」に更新される。このように、「Ｐｈａｓｅ１」でエントリ２２が送信したメッセージは、「Ｐｈａｓｅ２」で初めて利用可能となる。ＢＳＰモデルでは、このような各「Ｐｈａｓｅ」のことを「ｓｕｐｅｒｓｔｅｐ」と呼ぶ。以下、本実施形態では、この「ｓｕｐｅｒｓｔｅｐ」を「並列処理期間」と称することとする。そして、この並列処理期間に各エントリ２２において分散して行われる処理を並列処理（計算処理、データ値更新、メッセージ送信など）と称することとする。
【００３１】
本システム１００では、非特許文献１のようにエントリ２２間のエッジを仮定しないが、エッジの有無に関して本質的な差異はない。つまり、本システム１００においてエッジが設定されるようにしてもよい。本システム１００においてメッセージの送信先エントリがわかっていない場合、そのエントリ２２のキーを送信元エントリ２２がデータ値として保持しておく必要があるが、これはエントリ２２から別のエントリ２２へのエッジを作成することと等価であるからである。
【００３２】
（パーティションテーブル）
図５は、本実施形態に係るパーティションテーブルの例を示す図でる。
パーティションテーブルは、どのキーを有するエントリ２２が、どのタスク２１、あるいは、どのノードで実行されているかを管理するためのテーブルである。
図１で説明したように、本システム１００では、各タスク２１が複数のエントリ２２を保持しており、各タスク２１が複数のエントリ２２の処理を行う。各タスク２１が保持するエントリ２２の一覧は、図５に示すパーティションテーブルで管理されている。パーティションテーブルにおける各レコードが１つのタスク２１に対応している。「開始キー」と「終了キー」とで示された範囲が、対応するタスク２１が保持するエントリ２２のキーの範囲を表す。タスクＩＤ（Identification）はタスク２１の識別子であり、ノードＩＤはそのタスク２１が存在するノードの識別子である。宛先は、対応するノードの受信アドレスである。パーティションテーブルはジョブ毎に生成されるが、ジョブマネージャ１１とそのジョブに関わるすべてのタスク２１を管理しているタスクマネージャ２３が同一のパーティションテーブルを保持している。
【００３３】
ジョブマネージャ１１は、ジョブ開始時にパーティションテーブル（図５）を作成し、タスクマネージャ２３にタスク２１の生成を指示する。タスク２１の宛先はスレーブノード２のアドレスとポート番号の組から構成される。複数ジョブが同時実行される場合、複数のタスク用プロセスを１つのスレーブノード２上で実行するため、各タスク用プロセスに異なる受信用ポートを割り当てる必要がある。タスクマネージャ２３はタスク２１の生成指示を受けると、タスク用プロセスへの受信ポートの割り当てを行い、タスク用プロセスを生成する。タスク用プロセスの生成が完了すると、タスクマネージャ２３はタスク２１の宛先（アドレスとポート番号）をジョブマネージャ１１に返し、ジョブマネージャ１１は自身のパーティションテーブルにおいて、対応するタスク２１の宛先（図５）を更新する。
すべてのタスク２１について生成が完了すると、ジョブマネージャ１１は実行しているジョブに関わるすべてのタスク２１を管理しているタスクマネージャ２３へパーティションテーブルを送信する。このようにして、タスク２１の生成時にすべてのタスクマネージャ２３に同一のパーティションテーブルが配布される。
【００３４】
（データテーブル）
図６は、本実施形態に係るデータテーブルの例を示す図である。
データテーブルは、どのエントリ２２が、どのようなデータ値を保持しているかを管理するためのテーブルである。
各タスクマネージャ２３は、図６に示すデータテーブルを参照して、自身が保持するエントリ２２のデータ値を管理している。データテーブルは、エントリ２２のキー（ｋ）、計算処理の結果のデータ値である「Ｄｎ」、並列処理中に受信したメッセージである「Ｂｒ」、並列処理期間開始前にエントリ２２が保持しているデータ値である「Ｄ」、前回の並列処理で受信したメッセージである「Ｂｕ」を有している。「Ｂｕ」は、エントリにおいて他のエントリから送信されたメッセージを受信するためのバッファである。ここで、「Ｄｎ」＝「Ｄ」＋「Ｂｕ」である（前記したように、並列処理中に受信したメッセージ「Ｂｒ」は、次の並列処理期間にならないと使用することができない）。なお、実際には、「Ｄｎ」は「Ｄ」との差分が格納されることが多い。さらに、データテーブルは、データ値のバックアップである「Ｄｂ」、メッセージのバックアップである「Ｂｂ」の各データ値を有している。このうち「Ｄｂ」と「Ｂｂ」は、エントリ２２を二重化する場合に利用する（第３実施形態で後記）。
なお、図６において、各欄が空欄となっているが、実際にはデータ値が格納されている。
【００３５】
ジョブマネージャ１１は、図６に示すようなすべてのエントリ２２に関するデータテーブルを有しているが、タスクマネージャ２３は、システム１００における、すべてのエントリ２２に関するデータテーブルを有してもよいし、自身に対応するエントリ２２に関するデータテーブルを有してもよい。
【００３６】
（並列処理の概要）
ここで、並列処理の概要を記載する。具体的な処理は、図７以降を参照して後記する。
並列処理期間において、各エントリ２２はデータテーブルを参照して、自身に対応するエントリ２２の「Ｄ」と「Ｂｕ」を用いてユーザが定義した計算処理を実行する。前記したように、「Ｄ」は、並列処理期間開始時にエントリ２２が保持しているデータ値であり、「Ｂｕ」は前回の並列処理期間で受信したメッセージである。データ値の更新を行う場合、エントリ２２は、更新前との差分を計算処理の結果「Ｄｎ」として格納する。各タスク２１は自分が保持するすべてのエントリ２２の並列処理が終了したら、「Ｄｎ」と「Ｄ」とをマージ（データの結合など）し、マージ後のデータ値を、新たな「Ｄ」とする。各タスク２１は、この新たな「Ｄ」を並列処理期間終了後のデータ値として更新する。
【００３７】
各タスク２１は、他のタスク２１が保持するエントリ２２に対してメッセージを送信する。このとき、タスク２１は、タスクマネージャ２３が保持しているパーティションテーブルの宛先（図５）を参照して、送信先スレーブノード２を決定する。すなわちタスク２１は、メッセージ送信時に宛先エントリ２２のキーに対応するエントリ２２をパーティションテーブルから検出する。そして、タスク２１は、検出されたエントリ２２の宛先（図５）に対してメッセージを送信する。送信するメッセージには、メッセージ本体と宛先エントリ２２のキーが含まれている。
【００３８】
メッセージを受信したタスク２１は、自身が保持するデータテーブル（図６）を参照し、メッセージに含まれるキーに対応するエントリ２２の「Ｂｒ」（並列処理中に受信したメッセージ）に受信したメッセージを追加する。「Ｂｒ」へのメッセージ追加方法は、（ａ）メッセージを単純に追加していく方法と、（ｂ）集約計算を行う方法がある。（ａ）の場合、「Ｂｒ」は、最終的に複数のエントリ２２から受信したメッセージのリストになる。また、（ｂ）の例として、すべてのエントリ２２から受信したメッセージの和を「Ｂｒ」の結果とする処理などが挙げられる。和は結合法則と交換法則を満たすため、（ｂ）の場合、メッセージを受信するたびに、タスク２１は、受信したメッセージを「Ｂｒ」のデータ値に加算したデータ値を計算し、その結果を新たな「Ｂｒ」の値として更新する。このような演算が集約処理であり、結合法則と交換法則を満たす演算であればどのような演算であってもよい。他の集約処理の例として、最大、最小、二乗和などが用いられていてもよい。また、集約処理を行う場合、送信側タスク２１において、同一エントリ２２へ送信するメッセージを予め集約した後、集約結果を送信してもよい。これによって、ネットワーク転送量を削減することができる。
【００３９】
メッセージ送信処理は、並列処理期間の途中では他のエントリ２２からメッセージを受信する可能性があり、「Ｂｒ」のデータ値を確定することができない。従って、ある並列処理期間が終了した時点、つまりすべてのエントリ２２がある並列処理期間での並列処理を終えた時点で、その並列処理期間で更新された「Ｂｒ」の値が確定する。ある並列処理期間が終了し「Ｂｒ」が確定したら、タスク２１は、並列処理中に「Ｂｒ」を「Ｂｕ」（並列処理期間開始前にエントリ２２が保持しているデータ値）に移動する。これによって、タスク２１は、次回の並列処理期間において、受信したメッセージを使えるようになる。
【００４０】
（負荷均等化の具体例）
続いて、図１を参照しつつ、図７〜図１８に沿って本システム１００における負荷均等化の手法を説明する。これは各スレーブノード２が保持するデータ量をノード性能に応じて調整することで、スレーブノード２の計算負荷を均等化する方法である。これを行うためにはデータ値をスレーブノード２間で移動する必要があるが、前記したように、ＢＳＰモデルにおける並列処理期間と次の並列処理期間の間にデータ移動を行うと、データ移動処理のためだけの時間が必要になる。そこで本実施形態におけるシステム１００は、並列処理期間の実行中にデータ移動を並行して行うことで、データ移動処理の時間を並列処理期間の処理時間の中に隠蔽し、全体処理時間を削減するようにする。
【００４１】
例えば、初期配置状態では図７の上段に示すように各ノード（以降では、スレーブノード２のことを単に「ノード」と称する）にエントリ２２が割り当てられたと仮定する。図７の横軸は各ノードが保持するエントリ２２のキーを表している。図７の上段の例に示すように、「ノード１」は「ｋ１」〜「ｋ１５０」、「ノード２」は「ｋ１５１」（図示せず）〜「ｋ２２５」、「ノード３」は「ｋ２２６」（図示せず）〜「ｋ３００」のキーに対応するエントリ２２を保持している。
【００４２】
各ノードの性能が同一であれば、図７の上段に示す図では、「ノード１」に係る負荷が大きいため、図７の下段のようにエントリ２２を移動して、各ノードにおける負荷を均等化する。すなわち、ジョブマネージャ１１は、図７の下段のように各ノードに割り当てるキーの範囲を変更する。このとき、ジョブマネージャ１１は、「ｋ１０１」〜「ｋ１５０」のキー範囲のエントリ２２を「ノード１」から「ノード２」へ移動する。そして、ジョブマネージャ１１は、「ｋ２０１」〜「ｋ２２５」のキー範囲のエントリ２２を「ノード２」から「ノード３」へ移動する。このようにすることで、「ノード１」は「ｋ１」〜「ｋ１００」までのエントリ２２を有し、「ノード２」は「ｋ１０１」（図示せず）〜「ｋ２００」までのエントリ２２を有し、「ノード３」は「ｋ２０１」（図示せず）〜「ｋ３００」までのエントリ２２を有する。つまり、各ノードは、１００づつのエントリ２２を有することになり、各ノードの性能が同一であれば、負荷均等化を図ることができる。なお、ここでは、説明を簡単にするため、各ノードの性能が同一であることを仮定したが、ノード性能が異なる場合は、ノード性能の比に応じてエントリ２２の分配比を調整すればよい。
【００４３】
《第１実施形態》
続いて、図７に示すような負荷均等化の具体的な手順の第１実施形態を、図８〜図１３を参照して説明する。なお、第１実施形態〜第３実施形態におけるシステム１００の構成、ハードウェア構成は、図１および図２に示す構成と同様であるため、説明を省略する。
なお、図８〜図２５において、縦軸が各ノード（タスク２１）が保持するエントリ２２のキーを示している。また、各エントリ２２は、横方向に対応する各種データ値を有している。また、図８〜図２５において、破線で示した矩形はデータ値が存在しないことを示しており、実線の矩形はデータ値が存在することを示している。
【００４４】
図８〜図２５の各図において、矩形内に示した記号の添え字はデータ値のバージョンを示す。例えば図８において「ノード１」は、同期開始前にエントリ２２が保持しているデータ値である「Ｄ」と、前回の並列処理期間で受信したメッセージ「Ｂｕ」を自分が担当するすべての範囲のキーに対して保持している。「Ｄ」には「Ｄ１」、「Ｂｕ」には「Ｂ１」と記載されているが、この添え字「１」がバージョンである。詳細は後記するが、図９の「ノード１」では、「ｋ１００」〜「ｋ８５」の範囲のキーについてエントリ２２の並列処理が終了し、データ値の差分である「Ｄｎ」の部分に「ｄ２」と記載されている。ここで、添え字が「２」になっているが、このデータ値がバージョン「１」のデータ値（「Ｄ１」と「Ｂ１」）に基づいて生成されたため、バージョンが「２」に上がったことによる。
【００４５】
まず各タスク２１は、データ値の再分配を行う前に並列処理期間を最低１回実行し、各ノードにおける並列処理期間の実行時間を計測する。並列処理期間が終了したら、計測結果は各タスク２１からジョブマネージャ１１に集められ、ジョブマネージャ１１は計測結果に基づき、各ノードに割り当てるキーの比を計算する。
具体的には、既存のエントリ２２の分配比がｘ１：ｘ２：ｘ３であり、処理時間の比がｔ１：ｔ２：ｔ３であった場合、ジョブマネージャ１１は、エントリ２２の分配比がｘ１／ｔ１：ｘ２／ｔ２：ｘ３／ｔ３になるように調整することで、理論的には次回の処理時間の比を１：１：１にすることができる。ジョブマネージャ１１は、このようなエントリ２２の分配比を、パーティションテーブル（図５）を参照して計算する。
【００４６】
このようにして算出した各ノードへのエントリ２２の割り当てが、図７の下段に示すように「ノード１」に対して「ｋ１」〜「ｋ１００」、「ノード２」に対して「ｋ１０１」〜「ｋ２００」、「ノード３」に対して「ｋ２０１」〜「ｋ３００」になったと仮定する。ジョブマネージャ１１は、再配置後のキーの範囲（つまり、図５のパーティションテーブル）を各ノードに配布し、次回の並列処理期間を開始するように各タスク２１に要求する。
以下、図７の上段の配置状態から、図７の下段の配置状態へエントリ２２を再配置する具体的な手順を説明する。
【００４７】
（図８）
並列処理期間の開始時点で各ノードが保持するエントリ２２は図８のようになっている。ここで、図８におけるエントリ２２の配置状態は、図７の上段と同様の配置状態である。各ノードのタスク２１は、ジョブマネージャ１１から配布された再配置後のキーの範囲に基づき、他のノードに送信すべきキーの範囲を確定する。具体的には、「ノード１」は「ｋ１０１」〜「ｋ１５０」を「ノード２」に送信し、「ノード２」は「ｋ２０１」〜「ｋ２２５」を「ノード３」に送信することを確定する。この結果、この並列処理期間の終了後には、「ノード１」が「ｋ１」〜「ｋ１００」のエントリ２２を有し、「ノード２」が「ｋ１０１」〜「ｋ２００」のエントリ２２を有し、「ノード３」が「ｋ２０１」〜「ｋ３００」のエントリ２２を有することになる。
【００４８】
（図９）
図９は、並列処理期間開始からしばらく時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
各ノードのタスク２１は再配置後に自身が担当するキー範囲のエントリ２２の並列処理の実行を開始すると共に、再配置対象のエントリ２２のデータ値（「Ｄ」および「Ｂｕ」）を宛先ノードのタスク２１にする。
例えば、「ノード２」は再配置後に「ｋ１０１」〜「ｋ２００」の範囲のキーを担当することになるが、「ｋ１０１」〜「ｋ１５０」の範囲のキーは保持していない（現時点では、「ノード１」が保持している）。従って、「ノード２」は、エントリ２２の並列処理の実行を、再配置後自身が保持し、かつ、現時点でも自身が保持している最大のキーである「ｋ２００」から開始し、キーの値が小さくなる方向（「ｋ２００」→「ｋ１５１」）にエントリ２２の並列処理を進めていく。なお、図９〜図１３において、並列処理を進める方向を黒く塗りつぶした矢印で示す。
【００４９】
図９の時刻では、「ノード２」は「ｋ２００」から「ｋ１８５」まで並列処理を進めており、計算処理の結果として「ｋ２００」〜「ｋ１８５」の範囲のエントリ２２において「Ｄｎ」のデータ値（「ｄ２」）が格納されている。
【００５０】
このような計算処理と並行して、各ノードは、「Ｄ」、「Ｂｕ」のデータ値を再配置後のノードへコピーしていくが、このとき、以下に記載するような手順でデータ値のコピーを行う。例えば、前記したような「ノード２」の並列処理動作を見越して、「ノード１」は「ノード２」との再配置前のキー境界に近いデータ値から優先的に「ノード２」にコピーする。つまり、「ノード２」は「ｋ２００」から順にキーの値が小さくなる方向にエントリ２２の並列処理を行うため、「ノード１」は「ｋ１０１」〜「ｋ１５０」の範囲のデータ値を「ノード２」にコピーするときに、再配置前のキー境界である「ｋ１５０」からコピーを開始しする。そして、「ノード１」は、「ｋ１５０」からキーの値が小さくなる方向（「ｋ１５０」→「ｋ１０１」）に「ｋ１０１」まで順次データ値をコピーする。なお、図９〜図１３において、コピーしていく方向をハッチングの矢印で示し、コピーされるていく方向を白抜きの矢印で示す。これによって、「ノード２」におけるエントリ２２の処理をなるべく滞らせずに実行することが可能となる。
【００５１】
なお、図９において、「ノード１」は「ｋ１５０」〜「ｋ１３０」までのデータ値をコピーしているのに、「ノード２」では「ｋ１５０」〜「ｋ１３５」までしかデータ値を受信していない。これは、送信・受信のタイムラグのためである。
すべてのノードにおいて、エントリ２２の実行順序と、エントリ２２のノード間送信順序はこのようなルールに基づいて実行する。
なお、エントリ２２の計算処理とエントリ２２のデータ値のコピーは非同期に行われるため、エントリ２２の計算処理が完了したキーに対応するすべての「Ｄｎ」、「Ｄ」のコピーが完了しているわけではない。なお、エントリ２２の計算処理とエントリ２２のデータ値のコピーが同期的に行われてもよい。
【００５２】
図９における「Ｄｎ」、「Ｄ」、「Ｂｕ」におけるエントリの配置状態を、以下に整理する。
ノード１：「ｋ１００」〜「ｋ８５」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１３０」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」へコピー済み。
ノード２：「ｋ２００」〜「ｋ１８５」まで計算処理が完了済み（「ｄ２」）。「ｋ１２２５」〜「ｋ２０５」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード３」へコピー済み。「ｋ１５０」〜「ｋ１３５」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２８５」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２１０」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」から受信済み。
【００５３】
並列処理期間中に各エントリ２２が他のエントリ２２に対して送信するメッセージは、再配置後のエントリ配置に基づき送信される。従って、各ノードは再配置後に自身が担当する範囲のキーに対応するメッセージを受信することになる。
例えば、「ノード１」は再配置後に「ｋ１」〜「ｋ１００」のキー範囲のエントリ２２を担当するため、「Ｂｒ」はこの範囲のデータ値のみを受信し、保持する。図９では、「ノード１」において、「ｋ１」〜「ｋ１００」のキー範囲に該当する「Ｂｒ」が実線の矩形として示されている。ただし、並列処理期間実行中であり「Ｂｒ」の値は確定していないため、図９において、「Ｂｒ」ではバージョン番号を伴ったデータ値を記載していない（以降の図でも同様の理由から、確定前の「Ｂｒ」にはバージョン番号を記載しない）。また、再配置後、「ノード１」はそもそも「ｋ１０１」〜「ｋ１５０」のキー範囲のエントリ２２を担当しないため、図９では対応する「Ｂｒ」の部分の破線表示を行っていない。
同様の理由から、「ノード２」では「ｋ１０１」〜「ｋ２００」のキー範囲に該当する「Ｂｒ」が、「ノード３」では「ｋ２０１」〜「ｋ３００」のキー範囲に該当する「Ｂｒ」が実線の矩形として示されている。以降の図でも、「Ｂｒ」は同様に示されるため、図１０、図１１では「Ｂｒ」の説明を省略することとする。
【００５４】
（図１０）
図１０は、図９からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
各ノードにおけるエントリの配置状態は以下の通りである。
ノード１：「ｋ１００」〜「ｋ５５」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１０５」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」へコピー済み。
ノード２：「ｋ２００」〜「ｋ１５５」まで計算処理が完了済み（「ｄ２」）。「ｋ１２２５」〜「ｋ２０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード３」へコピー済み。「ｋ１５０」〜「ｋ１１０」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２５５」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」から受信済み。
【００５５】
図１０に示す時刻では、「ノード２」から「ノード３」へのデータ値（「Ｄ」および「Ｂｕ」）のコピーは完了しているが、「ノード１」から「ノード２」へのデータ値のコピーは未完である。
【００５６】
（図１１）
図１１は、図１０からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
各ノードにおけるエントリの配置状態は以下の通りである。
ノード１：「ｋ１００」〜「ｋ１５」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」へコピー済み。
ノード２：「ｋ２００」〜「ｋ１１５」まで計算処理が完了済み（「ｄ２」）。「ｋ１２２５」〜「ｋ２０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード３」へコピー済み。「ｋ１５０」〜「ｋ１０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２２１５」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「Ｄ１」、「Ｂ１」）が「ノード２」から受信済み。
【００５７】
図１１に示す時刻では、「ノード２」から「ノード３」へのデータ値（「Ｄ」および「Ｂｕ」）のコピーに加え、「ノード１」から「ノード２」へのデータ値のコピーも完了している。しかし、各ノードにおける計算処理（「ｄ２」）は未完である。
【００５８】
(図１２）
図１２は、図１１からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
図１２では、データ値のコピー、および各ノードにおける計算処理が終了している。図１２の時点で並列処理期間における並列処理が終了し、ＢＳＰモデルにおける同期の配置状態へ移行する。
並列処理期間が終了したことで、「Ｂｒ」の状態が確定しているため、各ノードにおける「Ｂｒ」の矩形の内部に「Ｂ２」とバージョン番号の添え字付の値を記載している。
また、「ノード１」における「ｋ１５０」〜「ｋ１０１」、「ノード２」における「ｋ２２５」〜「ｋ２０１」は、該当するノードにおける計算処理を行っていないため、データ値が存在しない破線矩形となっている。
【００５９】
（図１３）
図１３は、図１２からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
図１３は同期中におけるエントリの配置状態を示しており、この同期中に、各ノードのタスク２１は、「Ｄｎ」の値を「Ｄ」にマージし（「ｄ２」＋「Ｄ１」）、「Ｄｎ」をクリアする。また各ノードのタスク２１は、「Ｂｒ」を「Ｂｕ」に移動し、「Ｂｒ」をクリアする。
図１３では「Ｄ」の値が「Ｄ２」になっているが、１つ前のバージョンのデータ値である「Ｄ１」が新バージョンデータ値への差分「ｄ２」をマージした結果「Ｄ２」になったためである（「ｄ２」＋「Ｄ１」＝「Ｄ２」）。最後に、各ノードのタスク２１は、自身が保持するパーティションテーブル（図５）の開始キー、終了キーを再配置後の値に更新する。
【００６０】
（第１実施形態の効果）
以上説明したように、並列処理期間において各ノードが再配置後のエントリ２２に対する処理を行いつつ、データ値のコピー（送信）を行うことで、システム１００はエントリ２２の再配置処理時間を隠蔽することができ、全体処理時間を短縮することが可能になる。
つまり、並列処理期間において、各ノードがエントリ２２の計算処理を行うとともに、再配置後のエントリ２２に従ってデータ値をコピーするため、システム１００はエントリ２２の再配置処理時間をエントリ２２の計算処理に隠すことができ、全体処理時間を短縮することが可能になる。なお、データ値のコピーは、計算処理に比べて、ＣＰＵ２０１（図２）やメモリ２０４（図２）の使用率が著しく低いため、データ値のコピーが並列処理時間に与える影響は小さい。
【００６１】
《第２実施形態》
続いて、図７に示すような負荷均等化の具体的な手順の第２実施形態を、図１４〜図１８を参照して説明する。
第１実施形態の技術は、エントリ２２の再配置処理で「Ｄ」と「Ｂｕ」をノード間で送信していたが、コピーするデータ量が多い場合、データ値のコピー処理に多くの時間を費やしてしまい、全体処理時間の削減効果が小さくなるという課題がある。そこで第２実施形態におけるシステム１００は、再配置処理で「Ｄ」と「Ｂｕ」の代わりに「Ｄｎ」と「Ｄ」を送信する方法について説明する。
この方式は、「Ｂｕ」に比較して「Ｄｎ」のデータ量が十分に小さい場合に有効になる。
【００６２】
第１実施形態との違いはエントリ２２の再配置処理であるため、以下ではエントリ２２の再配置処理のみ説明する。第１実施形態と同様、図７に示すようにエントリ２２の再配置を行う場合を例として説明する。各ノードのタスク２１が他のノードにコピーするエントリ２２のキーの範囲を確定する処理までは、第１実施形態と同じであるため説明を省略する。
【００６３】
（図１４）
図１４は、並列処理期間の開始時点における各ノードにおけるエントリの配置状態を示す図である。
図１４は、図８と同様であるため、説明を省略する。
【００６４】
（図１５）
並列処理期間が開始すると、各ノードは、再配置前のエントリ２２に対する処理を行うと共に、再配置後のエントリ２２については計算処理の結果の「Ｄｎ」と「Ｄ」を再配置先にコピーする。
例えば、「ノード１」は、同期開始時点で「ｋ１」〜「ｋ１５０」のキー範囲のエントリ２２を保持しており、このうち「ｋ１０１」〜「ｋ１５０」のキー範囲のエントリ２２に対応するデータ値が「ノード２」に送信される必要がある。ネットワーク４（図１）の状態によっては、データ値の送信には時間がかかる可能性があるため、システム１００は送信対象エントリ２２（「ノード１」では「ｋ１０１」〜「ｋ１５０」）の並列処理を優先して実行し、このキー範囲のデータ値のコピー処理を開始する。従って、「ノード１」は「ｋ１０１」〜「ｋ１５０」のキー範囲のエントリ２２における並列処理を、再配置後にも「ノード１」に残るエントリ２２（「ｋ１」〜「ｋ１００」）より先に実行し、計算処理結果である「Ｄｎ」（「ｄ２」）が作成できたものから順に「ノード２」にコピーする。
【００６５】
このような制御を行うため、「ノード１」は「ｋ１５０」からエントリ２２の並列処理を開始し、キーの値が小さくなる方向（「ｋ１５０」→「ｋ１」）に並列処理を行っている。つまり、「ノード１」は再配置前のノード間のキー境界（ここでは、「ｋ１５０」）に近いデータ値からエントリ２２の並列処理を開始している。
図１５において、「ノード１」は「ｋ１５０」から「ｋ１２５」までのエントリ２２の計算処理が完了し、対応する「Ｄｎ」（「ｄ２」）の作成が完了している。エントリ２２の計算処理とエントリ２２のデータ値のコピーは非同期に行われるため、エントリ２２の計算処理が完了したキーに対応するすべての「Ｄｎ」、「Ｄ」のコピーが完了しているわけではない。なお、エントリ２２の計算処理とエントリ２２のデータ値のコピーが同期的に行われてもよい。
図１５では、「ノード１」において計算処理が完了している「ｋ１５０」〜「ｋ１２５」のデータ値のうち、「ｋ１５０」〜「ｋ１３０」の範囲の「Ｄｎ」、「Ｄ」のコピーが完了している（「ノード２」参照）。
【００６６】
また、第２実施形態では、同じエントリ２２に対応する「Ｄｎ」と「Ｄ」とを対にして、送信先ノードへコピーする。ただし、必ずしも「Ｄｎ」と「Ｄ」を対にしてコピーする必要はなく、ネットワーク４の帯域に余裕がある場合は、すべての「Ｄｎ」のコピーが完了する前に、すべての「Ｄ」のコピーを完了してもよい。
なお、図１５、図１６において、計算およびコピーしていく方向を黒く塗りつぶした矢印で示し、コピーされていく方向を白抜きの矢印で示す。
【００６７】
同様に、図１５において、「ｋ２２５」〜「ｋ２０１」の範囲のエントリ２２を「ノード３」に再配置する必要があるため、「ノード２」は再配置前のキー境界「ｋ２２５」から「ｋ２２５」→「ｋ２０１」の方向にエントリ２２の並列処理を開始し、「ｋ２０５」まで計算処理を終えている。そして「ノード３」は「ｋ２２５」〜「ｋ２１０」の範囲の「Ｄｎ」（「ｄ２」）と「Ｄ」（「Ｄ１」）の受信を完了している。
【００６８】
図１５における「Ｄｎ」、「Ｄ」におけるエントリの配置状態を、以下に整理する。
ノード１：「ｋ１５０」〜「ｋ１２５」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１３０」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」へコピー済み（「ノード２」の「Ｄｎ」、「Ｄ」参照）。
ノード２：「ｋ２２５」〜「ｋ２０５」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２１０」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード３」へコピー済み（「ノード３」の「Ｄｎ」、「Ｄ」参照）。「ｋ１５０」〜「ｋ１３０」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２８０」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２１０」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」から受信済み。
【００６９】
なお、第２実施形態では、既に計算処理を行った結果（「Ｄｎ」）を送信先ノードで送っているため、送信先ノードでは、改めて「Ｄ」と「Ｂｕ」を用いた計算処理を行う必要はない。そのため、各ノードにおいて「Ｂｕ」のコピーは行われていない（図１６、図１７も同様）。
また、「Ｂｒ」については、第１実施形態と同様であるため、説明を省略する。
【００７０】
（図１６）
図１６は、図１５からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。なお、前記したように計算およびコピーの方向を黒く塗りつぶした矢印で示し、コピーされる方向を白抜きの矢印で示している。
各ノードにおけるエントリの配置状態は以下の通りである。
ノード１：「ｋ１５０」〜「ｋ９５」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」へコピー済み（「ノード２」の「Ｄｎ」、「Ｄ」参照）。
ノード２：「ｋ２２５」〜「ｋ１７０」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード３」へコピー済み（「ノード３」の「Ｄｎ」、「Ｄ」参照）。「ｋ１５０」〜「ｋ１０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２２６」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」から受信済み。
【００７１】
図１６では、各ノードにおけるデータ値のコピーは完了しているが、「ノード１」、「ノード２」において計算処理が未完である（「ノード３」は計算処理も完了している）。
【００７２】
（図１７）
図１７は、図１６からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
各ノードにおけるエントリの配置状態は以下の通りである。
ノード１：「ｋ１５０」〜「ｋ１」まで計算処理が完了済み（「ｄ２」）。「ｋ１５０」〜「ｋ１０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」へコピー済み（「ノード２」の「Ｄｎ」、「Ｄ」参照）。
ノード２：「ｋ２２５」〜「ｋ１５１」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード３」へコピー済み（「ノード３」の「Ｄｎ」、「Ｄ」参照）。「ｋ１５０」〜「ｋ１０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード１」から受信済み。
ノード３：「ｋ３００」〜「ｋ２２６」まで計算処理が完了済み（「ｄ２」）。「ｋ２２５」〜「ｋ２０１」までのデータ値（「ｄ２」、「Ｄ１」）が「ノード２」から受信済み。
【００７３】
図１７の時点で、各ノードにおける計算処理およびデータ値のコピーが完了している。そして、図１７の時点で、並列処理期間の並列処理が終了し、ＢＳＰモデルにおける同期の状態へ以降する。ここで、第１実施形態と同様に、並列処理期間が終了したことで、「Ｂｒ」の状態が確定しているため、「Ｂｒ」の矩形の内部に「Ｂ２」とバージョン番号の添え字付の値を記載している。
【００７４】
（図１８）
図１８は、図１７からさらに時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
図１８は同期中におけるエントリの配置状態を示しており、この同期中に、各ノードのタスク２１は、再配置後のエントリ２２に対して「Ｄｎ」の値を「Ｄ」にマージし（「ｄ２」＋「Ｄ１」＝「Ｄ２」）、また、Ｄｎをクリアする。そして、各ノードのタスク２１は、「Ｂｒ」を「Ｂｕ」に移動し、「Ｂｒ」をクリアする。なお、「Ｄ」におけるバージョン番号は第１実施形態と同様であるため、説明を省略する。
最後に、各ノードのタスク２１は、自身が保持するパーティションテーブルの開始キー、終了キーを再配置後の値に更新する。
【００７５】
（第２実施形態の効果）
第２実施形態によれば、「Ｂｕ」の代わりに「Ｄｎ」（この値は、差分であることが多いのでデータ量が小さい）を、送信先ノードへコピー（送信）することにより、送信データ量の削減が可能となる。
【００７６】
《第３実施形態》
次に、図１９から図２５を参照して、本発明の第３実施形態を説明する。
第３実施形態におけるシステム１００は、耐障害性を維持しつつ、データ移動の時間を隠蔽することを目的とする。
耐障害性とノードの負荷均等化を両立するための技術として特許文献２に記載の技術が挙げられるが、前記したように、データ値の複製処理に対して余分な時間が必要となり、全体の処理時間が増大するという課題がある。このような課題に対し、第３実施形態におけるシステム１００は、エントリ２２における並列処理を行いつつ、データ値の複製を行うことで、全体の処理時間を削減する。
【００７７】
第３実施形態と、第１実施形態、第２実施形態との違いは並列処理期間におけるエントリ２２の処理とデータ複製処理であるため、この部分を中心に説明する。第３実施形態ではすべてのエントリ２２のデータ値は２つのノードが保持する。主としてデータ値を管理し、エントリ２２の処理を行うノードをプライマリノードと呼び（単に「プライマリ」と適宜称する：第１のノード）、データ値の複製を保持し、負荷が小さいときにエントリ２２の処理を代理実行するノード（つまり、バックアップ用のノード）をレプリカノードと呼ぶ（単に「レプリカ」と適宜称する：第２のノード）。第３実施形態において、レプリカは別のキー範囲に対するプライマリを兼ねるため、プライマリに比べて計算処理能力（代理実行能力）が低いと仮定する。ただし、レプリカを専用のノードとし、プライマリと同等の計算処理能力を持つ構成としてもよい。
【００７８】
（図１９）
図１９は、並列処理期間の開始時点におけるプライマリとレプリカにおけるエントリの配置状態を示す図である。
図１９に示すように、プライマリとレプリカとでは、キー範囲「ｋ１」〜「ｋ１００」に対するエントリ２２のデータ値（「Ｄ」、「Ｂｕ」）が二重化されている。
【００７９】
（図２０）
図２０は、並列処理期間開始からしばらく時間が経過したときの、各ノードにおけるエントリの配置状態を示す図である。
並列処理期間が開始されエントリ２２の処理が始まると、プライマリはキーの値が最小である「ｋ１」からエントリ２２の並列処理を開始し、「ｋ１００」の方向（「ｋ１」→「ｋ１００」）へ並列処理を進めていく。プライマリは計算処理が完了したエントリ２２から順に、計算処理結果である「Ｄｎ」（「ｄ１」）をレプリカへコピーする。エントリ２２の計算処理と「Ｄｎ」のコピーは非同期に行われるため、計算処理中のエントリ２２のキーとコピー中のＤｎに対応するキーは一致しない。なお、エントリ２２の計算処理と「Ｄｎ」のコピーが同期的に行われてもよい。図１９では、「ｋ１」〜「ｋ４０」のエントリ２２における計算処理が完了し、「ｋ１」〜「ｋ２０」の「Ｄｎ」のコピーが完了している（レプリカ参照）。
なお、図２０〜図２３において、計算およびコピーしていく方向を黒く塗りつぶした矢印で示し、コピーされていく方向を白抜きの矢印で示す。
【００８０】
レプリカは負荷に余裕があり代理実行が可能であれば、プライマリが行うエントリ２２の処理を肩代わりする。図２０の例では、レプリカはプライマリの実行と処理が重ならないようにするため、プライマリとは逆順にエントリ２２の処理を代理実行している。つまり、キーの値が最大である「ｋ１００」からエントリ２２の処理を開始し、「ｋ１」の方向（「ｋ１００」→「ｋ１」）へ進めていく。レプリカは代理実行したエントリ２２の計算処理の結果である「Ｄｎ」（「ｄ１」）をプライマリへコピーする。図１９の例では、レプリカは「ｋ１００」〜「ｋ８５」のエントリ２２における計算処理が完了し、このうち、「ｋ１００」〜「ｋ９０」のエントリ２２についてデータ値（「Ｄｎ」）のコピーが完了している（プライマリ参照）。
なお、プライマリと、レプリカの並列処理が重ならないようにすれば、並列処理の方向は、図１９に示す方向に限らない。例えば、それぞれの向きが逆向きでもよいし、任意のエントリ２２から互いに逆方向に並列処理を進めてもよい。
【００８１】
このようにプライマリとレプリカはエントリ２２の処理を分担するが、そのエントリ２２の並列処理を実行したノードがプライマリであってもレプリカであっても、並列処理を行っている他のエントリ２２が送信したメッセージは、プライマリに送信される。従って、図１９〜図２５において、レプリカには「Ｂｒ」が存在していない。ただし、他のエントリ２２へのメッセージは、プライマリおよびレプリカから送信される。つまり、レプリカは、自身が計算したエントリ２２については、メッセージの送信を行う。
【００８２】
図２０の時点におけるプライマリと、レプリカにおけるエントリの配置状態を整理すると以下のようになる。
プライマリ：「ｋ１」〜「ｋ４０」まで計算処理が完了済み（「ｄ１」）。「ｋ１」〜「ｋ２０」までのデータ値がレプリカへコピー済み（レプリカの「Ｄｎ」参照）。「ｋ１００」〜「ｋ９０」までのデータ値をレプリカから受信済み（「ｄ１」）。
レプリカ：「ｋ１００」〜「ｋ８５」まで計算処理が完了済み（「ｄ１」）。「ｋ１００」〜「ｋ９０」までのデータ値がプライマリへコピー済み（プライマリの「Ｄｎ」参照）。「ｋ１」〜「ｋ２０」までのデータ値をプライマリから受信済み（「ｄ１」）。
【００８３】
（図２１）
図２１は、図２０からさらに時間が経過したときの、各ノードにおけるエントリの配置配置状態を示す図である。
プライマリと、レプリカにおけるエントリの配置配置状態は以下の通りである。
プライマリ：「ｋ１」〜「ｋ８０」まで計算処理が完了済み（「ｄ１」）。「ｋ１」〜「ｋ５０」までのデータ値がレプリカへコピー済み（レプリカの「Ｄｎ」参照）。「ｋ１００」〜「ｋ８０」までのデータ値をレプリカから受信済み（「ｄ１」）。
レプリカ：「ｋ１００」〜「ｋ７０」まで計算処理が完了済み（「ｄ１」）。「ｋ１００」〜「ｋ８０」までのデータ値がプライマリへコピー済み（プライマリの「Ｄｎ」参照）。「ｋ１」〜「ｋ５０」までのデータ値をプライマリから受信済み（「ｄ１」）。
【００８４】
図２１の時点で、並列処理期間が終了したとする。
すると、図２１の時点で、プライマリはすべてのエントリ２２についての計算処理結果（「ｄ１」）を保持している。プライマリ自身が計算処理を実行したエントリ２２と、レプリカから受信した計算処理結果が一致した地点が「ｋ８０」である。
一方、図２１の時点で、レプリカは「ｋ１００」から開始した代理実行が「ｋ７０」まで進んでおり、プライマリにはこのうち「ｋ１００」〜「ｋ８０」のデータ値がコピーされている。
【００８５】
すなわち、「ｋ７０」〜「ｋ８０」のエントリ２２については、プライマリとレプリカの両方で計算処理を行っている。前記したように、プライマリも、レプリカも自身が計算したエントリ２２については、メッセージの送信を行うため、「ｋ７０」〜「ｋ８０」のエントリ２２に関して、プライマリとレプリカの双方からメッセージが送信されてしまう。その結果、他のノードにおけるプライマリは、プライマリとレプリカの双方から送信されたメッセージを受信してしまう。同一メッセージを２回「Ｂｒ」に適用すると、「Ｂｒ」の値が不正になるため、各ノードのプライマリではメッセージの重複受信を検出する必要がある。例えば、各ノードのプライマリでは受信したメッセージの送信元エントリのキーの集合を保持しておくことで、重複受信を検出することができる。つまり、各ノードのプライマリは、メッセージを受信したとき、そのメッセージの送信元のキーを保持しておく。そして、プライマリはメッセージを受信するたびに、そのメッセージの送信元のキーと、保持しているキーとを比較することで、メッセージを重複受信していないか否かを判定する。
なお、メッセージを重複受信していることが検知された場合、プライマリは、後から受信したメッセージを破棄するなどの処理を行う。
【００８６】
（図２１→図２２）
ここで、前記したように図２１の時点で並列処理期間は終了しており、ＢＳＰモデルにおける同期の状態になる。
この間、レプリカは自身が保持する「Ｄｎ」を「Ｄ」にマージし、「Ｄｎ」を保持していないキー範囲（「ｋ５１」〜「ｋ６９」）の「Ｄ」と「Ｂｕ」については、それぞれレプリカ自身の「Ｄｂ」、「Ｂｂ」にバックアップする。
【００８７】
また、プライマリは、すべてのエントリ２２において「Ｄｎ」を「Ｄ」にマージし、「Ｂｒ」を「Ｂｕ」へ移動する。さらに、プライマリは、レプリカが保持していない「ｋ５１」〜「ｋ６９」のＤｎ（「ｄ１」）をプライマリ自身の「Ｄｂ」にバックアップする。またプライマリは、すべてのエントリ２２における「Ｂｒ」をまとめてレプリカへコピーする。レプリカは、プライマリから「Ｂｒ」を受信すると、受信した「Ｂｒ」を「Ｂｕ」に格納する。
【００８８】
このようにすることで、キー範囲「ｋ１」〜「ｋ５０」および「ｋ７０」〜「ｋ１００」に対応するデータ値（「Ｄ」、「Ｂｕ」）については、並列処理期間実行後のデータ値が二重化されることになる。
それ以外のキー範囲、すなわち「ｋ５１」〜「ｋ６９」については、プライマリは並列処理期間実行後のデータ値（「Ｄ」（「Ｄ１」）、「Ｂｕ」（「Ｂ１」））を保持している。しかし、レプリカは、このキー範囲（「ｋ５１〜「ｋ６９」）については、「Ｄ」を保持していない。ただし、レプリカはこのキー範囲（「ｋ５１」〜「ｋ６９」）において、「Ｄｂ」、「Ｂｂ」に並列処理期間実行前のデータ値（「Ｄ０」、「Ｂ０」）を保持しているため、これを使用して再計算することで並列処理期間実行後の「Ｄ」（「Ｄ１」）を作成することができる（「Ｄ０」＋「Ｂ０」＝「ｄ１」、「ｄ１」＋「Ｄ０」＝「Ｄ１」）。
【００８９】
つまり、レプリカは、並列処理期間実行後のデータ値（「Ｄ１」、「Ｂ１」）を持つことと等価であり、データ値は問題なく二重化されていると言える。
【００９０】
以上の処理を完了した結果が、図２２に示される状態である。
【００９１】
なお、プライマリ−レプリカ間の並列処理が完了しても、他のエントリ２２における計算処理が完了していない場合がある。このような場合、他のエントリ２２の計算処理が完了するのを待つ必要があるため、プライマリ・レプリカは、以下のような処理を行ってもよいが、本実施形態では、以下の処理を行わなかったものとして処理の説明を進める。
つまり、この待ち時間を利用してプライマリはレプリカへ、適時「ｋ５１」〜「ｋ６９」の「Ｄｂ」（「ｄ１」）をコピーしてもよい。
そして、レプリカは「ｄ１」を受信したら「Ｄｂ」（「Ｄ０」）とマージし、マージ結果を「Ｄ」（「Ｄ１」）に格納していく。そして、レプリカは、マージと、マージ結果の格納と並行して更新が完了したキーに対応する「Ｄｂ」と「Ｂｂ」を順次クリアするようにしてもよい。またプライマリでは、「Ｄｂ」（「ｄ１」）のコピーが完了したキーに対応する「Ｄｂ」を順次クリアしてもよい。
【００９２】
（図２２→図２３）
次の並列処理期間において、レプリカでエントリ２２の計算処理を代理実行する際にキーを進める方向として、（ａ）「ｋ１」→「ｋ１００」、および（ｂ）「ｋ１００」→「ｋ１」の２つの選択肢がある。この場合、どちらの方向から計算処理の代理実行を行うのかが、以下に示すように設定される必要がある。
【００９３】
図２２の時点で、レプリカは中間のキー範囲「ｋ５１」〜「ｋ６９」のエントリ２２のデータ値（「Ｄ」）を保持していないため、この範囲のエントリ２２における計算処理を実行することはできない。そこでレプリカは、なるべく多くのエントリ２２に対して代理実行を実行できるようにするため、「Ｄ」の存在するキー範囲においてエントリ２２が多い側から代理実行を開始する。次の並列処理期間開始時点で図２２に示すような配置状態であれば、「ｋ１」〜「ｋ５０」のキー範囲のレプリカの方が、「ｋ７０」〜「ｋ１００」のキー範囲より、多くのデータ値「Ｄ」（「Ｄ１」）を保持している。よって、レプリカは、「ｋ１」→「ｋ１００」の方向で代理実行を進めるよう代理実行の方向を設定する。
【００９４】
レプリカは自身がプライマリとして管理するエントリ２２を保持するため、並列処理期間が開始されたら直ちに代理実行を開始するわけではない。並列処理期間開始時にレプリカは代理実行の方向を決めておき、実際の代理実行は、自身の負荷が低いときに行う。
【００９５】
レプリカが代理実行の方向を決めたらプライマリは、その逆順（つまり、「ｋ１００」→「ｋ１」）の方向でエントリ２２の並列処理を行う。これによって、並列処理を行うエントリ２２が、プライマリとレプリカとで重複しないようにすることができる。
また、プライマリは「Ｄｂ」（「ｄ１」）の残りをレプリカに送信するが、なるべくレプリカでの代理実行を継続できるように、レプリカの代理実行の方向と同方向となるよう「Ｄｂ」をコピーする。
すなわち、本実施形態では、レプリカが「ｋ１」→「ｋ１００」の方向で代理実行を行うので、プライマリは同方向となる「ｋ５１」→「ｋ６９」の方向で「Ｄｂ」（「ｄ１」）を送信する。
【００９６】
（図２３）
図２３は、並列処理期間開始から所定時間が経過したときにおけるエントリの配置状態を示す図である。
図２３の時点におけるエントリの配置状態は以下の通りである。
プライマリ：「ｋ１００」〜「ｋ４０」まで計算処理が完了済み（「ｄ２」）。「ｋ１００」〜「ｋ５５」までのデータ値（「ｄ２」）がレプリカへコピー済み（レプリカの「Ｄｎ」参照）。「ｋ１」〜「ｋ１０」までのデータ値（「ｄ２」）をレプリカから受信済み（「ｄ２」）。「ｋ５１」〜「ｋ６５」までの「Ｄｂ」（「ｄ１」）をレプリカへ送信済み。
レプリカ：「ｋ１」〜「ｋ１０」まで計算処理が完了済み。「ｋ１」〜「ｋ１０」までのデータ値（「ｄ２」）がプライマリへコピー済み（プライマリの「Ｄｎ」参照）。「ｋ１００」〜「ｋ５５」までのデータ値（「ｄ２」）をプライマリから受信済み。「ｋ５１」〜「ｋ６５」までのデータ値（「ｄ１」）をプライマリから受信し、それを自身の「Ｄｂ」（「Ｄ０」）とマージすることで「Ｄ」（「Ｄ１」）を生成済み。
ここで、レプリカからプライマリへコピーしたキー範囲が、「ｋ１」〜「ｋ１０」と同じであるのは、レプリカが自身の負荷に余裕のあるときに計算・コピーを行っているためである。
【００９７】
（図２４）
図２４は、図２３の時点からさらに時間が経過し、並列処理期間が終了した直後におけるエントリの配置状態を示す図である。
図２４の時点におけるエントリの配置状態は以下の通りである。
プライマリ：「ｋ１００」〜「ｋ３０」まで計算処理が完了済み。「ｋ１００」〜「ｋ５０」までのデータ値（「ｄ２」）がレプリカへコピー済み（レプリカの「Ｄｎ」参照）。「ｋ１」〜「ｋ３０」までのデータ値（「ｄ２」）をレプリカから受信済み（従って、「Ｄｎ」のデータ値をすべて保持している）。「ｋ５１」〜「ｋ６９」までの「Ｄｂ」（「ｄ１」）をレプリカへ送信済み。
レプリカ：「ｋ１」〜「ｋ３０」まで計算処理が完了済み。「ｋ１」〜「ｋ３０」までのデータ値（「ｄ２」）がプライマリへコピー済み（プライマリの「Ｄｎ」参照）。「ｋ１００」〜「ｋ５０」までのデータ値（「ｄ２」）をプライマリから受信済み。「ｋ５１」〜「ｋ６９」までのデータ値（「ｄ１」）をプライマリから受信し、それを自身の「Ｄｂ」（「Ｄ０」）とマージすることで「Ｄ」（「Ｄ１」）を生成済み（従って、「Ｄ」（「Ｄ１」）のデータ値をすべて保持している）。
【００９８】
ここで、プライマリでは「ｋ１００」〜「ｋ３０」までの計算処理が完了しているのに、レプリカが「ｋ１００」〜「ｋ５０」までしかデータ値を受信していないのは、レプリカの性能が、プライマリより低いためである。
【００９９】
図２４の時点において、レプリカは、前回の並列処理期間で処理が完了していなかった「ｋ５１」〜「ｋ６９」のキー範囲のデータ値「Ｄ」（「Ｄ１」）をすべて保持することができるが、新たに「ｋ３１」〜「ｋ４９」のキー範囲のデータ値「Ｄｎ」（「ｄ２」）について計算処理が間に合わず、当該範囲のデータ値を保持していない状態となっている。
【０１００】
（図２４→図２５）
図２４の時点で並列処理期間が終了したとすると、図２４におけるエントリの配置状態から、プライマリおよびレプリカは、図２１→図２２と同様の処理を行う。
すなわち、レプリカは自身が保持しているキー範囲（「ｋ１」〜「ｋ３０」、「ｋ５０」〜「ｋ１００」）の「Ｄｎ」（「ｄ２」）を「Ｄ」（「Ｄ１」）にマージして、マージした結果（「Ｄ２」）を「Ｄ」に格納する。
また、レプリカは、「Ｄｎ」を保持していないキー範囲（「ｋ３１」〜「ｋ４９」）の「Ｄ」（「Ｄ１」）と「Ｂｕ」（「Ｂ１」）については、それぞれ自身の「Ｄｂ」、「Ｂｂ」にバックアップをとる。
【０１０１】
またプライマリは、「Ｄｎ」（「ｄ２」）をＤ（「Ｄ１」）にマージし、「Ｂｒ」（Ｂ２」）を「Ｂｕ」に移動する。そして、プライマリは、レプリカが保持していない「ｋ３１」〜「ｋ４９」のキー範囲の「Ｄｎ」（「ｄ２」）を自身の「Ｄｂ」にバックアップする。またプライマリは、すべてのキー範囲の「Ｂｒ」（「Ｂ２」）をまとめてレプリカに送信する。レプリカは「Ｂｒ」（「Ｂ２」）をプライマリから受信したら、受信したデータ値（「Ｂ２」）を「Ｂｕ」に代入する。
以上の処理を行うことで、各エントリ２２におけるエントリの配置状態は、図２５に示すようになる。
そして、ジョブマネージャ１１は、各エントリ２２に関する情報をデータテーブルに反映することによって、データテーブルを更新する。
【０１０２】
（第３実施形態の効果）
第３実施形態によれば、システム１００はレプリカにおいて、すべての代理実行が終了せずに並列処理期間が終了しても、次の並列処理期間で終了しなかったキー範囲の代理実行を行いつつ、新たな代理実行も行うことができるため、効率的に複製を行うことができる。
【０１０３】
《第４実施形態》
図２６は、第４実施形態に係る並列計算処理の概要を示す図である。なお、第４実施形態でも、システム構成、ハードウェア構成は、図１、図２と同様であるので、システム構成、ハードウェア構成に対する図示、説明を省略する。
第１実施形態〜第３実施形態では、図４に示すような、各並列処理期間で同一のエントリ群が並列計算を実行するモデルに基づいていた。
しかしながら、実際には、図２６に示すように、並列処理期間毎に異なるエントリ群が並列計算を実行する場合がある。第４実施形態では、このような並列分散処理システム１００の場合を、第１実施形態〜第３実施形態に適用した場合について説明する。
【０１０４】
図２６において、各エントリ２２は、図３，図４に示すような（キー，データ値）に加えてタイプ（種別）という属性を有している。例えば、図１１の左上に記載したエントリ２２には「（Ｔ１，ｋ１，ｖ１１）」と記載されているが、これはタイプが「Ｔ１」で、キーが「ｋ１」で、データ値が「ｖ１１」であることを示している。
この、並列分散処理システム１００ではタイプが同一のエントリ群が同じ並列処理期間で並列計算処理を行い、同期後の次の並列処理期間では、前回の並列処理期間とは異なるタイプのエントリ群が並列計算処理を行う。そして並列処理期間を繰り返すうちに、ある並列処理期間で以前処理を実行したエントリ群が再び並列処理を行う。
例えば、図２６における「Ｐｈａｓｅ１」ではタイプが「Ｔ１」のエントリ群が並列計算処理を行い、次の「Ｐｈａｓｅ２」ではタイプが「Ｔ２」のエントリ群が並列計算処理を行っている。そして、「Ｐｈａｓｅ３」では再びタイプが「Ｔ１」のエントリ群の処理を行っている。
なお、タイプ「Ｔ２」のエントリ群における「ｗ１１」はデータ値を示している。
【０１０５】
このような並列分散処理システム１００を実現するために、図５に示すパーティションテーブルおよび図６に示すデータテーブルがタイプ毎に作成される。前記したように、元々、パーティションテーブル、データテーブルはジョブ毎に作成していたため、第４実施形態では、パーティションテーブルおよびデータテーブルがジョブとタイプの組み合わせ毎に作成されることになる。なお、１つのタイプに属するエントリ群の処理が並列実行されるため、タイプ単位で負荷の均等化が実現できることが望ましい。このために、タイプ毎にパーティションテーブルおよびデータテーブルが作成されている。
【０１０６】
続いて、図２６に示す並列分散処理システム１００を第１実施形態〜第３実施形態のそれぞれに適用した場合の処理について説明する。
【０１０７】
（第１実施形態に適用した場合）
第１実施形態の図８から図１３で説明したデータ再配置処理において、エントリ２２が送信したメッセージは並列処理期間で並列処理を実行中のエントリ群が受け取っていたが、第４実施形態では次の並列処理期間で並列計算処理を実行するタイプのエントリ群（従って、現在並列計算処理を行っているエントリ群とは異なるエントリ群）が受信することになる。従って、図８から図１３に、各エントリ２２が送信したメッセージは図示されている「Ｂｒ」へは送信されず、次の並列処理期間で並列計算処理を行うエントリ群の「Ｂｒ」へメッセージが送信される。
【０１０８】
そして、再配置の際に、システム１００はメッセージ送信先のエントリ群のデータ値の再配置は行わず、メッセージ送信元のエントリ群のデータ値の再配置を行う。つまり、システム１００は、現在並列計算処理を行っているエントリ群については再配置を行うが、次の並列処理期間で並列計算処理を行うエントリ群については、再配置を行わない。従って、エントリ２２のメッセージを実際に送信するノードは、次に並列処理を行うタイプのパーティションテーブルを使って決定される。その他の処理については、第１実施形態で説明した処理とと同様である。
【０１０９】
ただし、第１実施形態に適用する場合、ある並列処理期間で各タスクの実行時間が計測され、各タスクへのデータ配置が決定された後、システム１００は、次に最初のタスクとはタイプが異なるタスク群の並列処理を実行している間に、最初のタスクに関するデータの再配置を行うことができる。またデータの再配置が完了する前に、最初に実行時間を計測したタスクと同じタイプのタスク群を実行することになった場合、データの再配置を続けながらそのタスク群の並列処理を行うことが可能である。このように、システム１００はデータの再配置処理を効率化することができる。例えば図２６の例では「Ｐｈａｓｅ１」でタイプが「Ｔ１」のエントリ群の並列計算処理を行うタスク群の実行時間が計算され、各タスクへの最適なデータ配置が決定される。そして「Ｐｈａｓｅ２」で「Ｔ２」のエントリ群の並列計算処理を行っている間に、「Ｔ１」のエントリ群の再配置が行われる。
【０１１０】
（第２実施形態に適用した場合）
第４実施形態に係る並列分散処理システム１００を、第２実施形態に適用した場合も第１実施形態に適用した場合と同様である。
すなわち、エントリ２２のメッセージを実際に送信するノードは、次に並列処理を行うタイプのパーティションテーブルを使って決定する。図１５〜図１７では、並列処理期間で並列計算処理を実行中のエントリ２２の「Ｂｒ」に受信したメッセージが蓄積されていくが、第４実施形態を適用すると、並列処理期間で処理を実行中のエントリ群はメッセージを受信せず、次の並列処理期間で並列計算処理を行うエントリ群がメッセージを受信する。その他の処理については、第２実施形態と同様の処理である。
【０１１１】
第２実施形態においても、第１実施形態へ第４実施形態を適用した場合のデータ再配置効率化手法を実施することが可能である。ただし、第２実施形態はエントリの計算を行ってから計算結果を再配置先へ送信するため、データ再配置処理が次回の並列計算処理を開始するまでに完了しなかった場合、各タスクは次回の並列計算処理開始時点で保持するデータに対して並列計算処理を行い、その結果を再配置先へ送信することになる。
【０１１２】
（第３実施形態に適用した場合）
第４実施形態係る並列分散処理システム１００を、第３実施形態に適用した場合についても、エントリ２２のメッセージ送信に関しては第１実施形態、第２実施形態に適用した場合と同様である。各エントリ２２が送信したメッセージは、次の並列処理期間で並列計算処理を実行するエントリ群のプライマリに対して送信される。従って、図２１、図２２に移行する過程で、プライマリは、レプリカへ「Ｂｒ」の内容を送信しているが、第４実施形態を適用した場合では、次の並列処理期間を実行するエントリ群のプライマリから、次の並列計算処理を実行するレプリカに対して「Ｂｒ」の内容を送信することになる。
つまり、並列処理の実行順が図２６で示すような順番であるとすると、「Ｐｈａｓｅ１」終了時に、「Ｔ２」のプライマリは「Ｔ２」のレプリカへ「Ｂｒ」の内容を送信し、次の「Ｐｈａｓｅ２」終了時に、「Ｔ１」のプライマリは「Ｔ１」のレプリカへ「Ｂｒ」の内容を送信することとなる。
【０１１３】
また、図２２において、プライマリの「Ｄｂ」にバックアップされた未送信データ値（「ｄ２」）が残っているが、次の並列処理期間（図２３〜図２５）では、これらのプライマリ、レプリカは、並列計算処理を行わないため、次の並列処理期間の処理中に、プライマリの「Ｄｂ」のデータ値（「ｄ２」）をレプリカに送信し、レプリカは、受信したデータ値を基に「Ｄ」を生成することができる。そのため、第３実施形態より効率的な複製が可能となる。その他の処理については、第３実施形態における処理と同様である。
【０１１４】
（第４実施形態の効果）
第４実施形態によれば、並列処理期間毎に異なるエントリ群で並列計算処理を行うことで、並列分散処理システム１００全体の負荷を低減することができる。
【符号の説明】
【０１１５】
１      マスタノード
２      スレーブノード（ノード：第１のノード、第２のノードを含む）
３      クライアントノード
１１    ジョブマネージャ
１２    分散ファイルシステム（マスタノード）
２１    タスク
２２，２２ａ〜２２ｃ  エントリ
２３    タスクマネージャ
２４    分散ファイルシステム（スレーブノード）
【図１】
2013069189.tif 000003
【図２】
2013069189.tif 000004
【図３】
2013069189.tif 000005
【図４】
2013069189.tif 000006
【図５】
2013069189.tif 000007
【図６】
2013069189.tif 000008
【図７】
2013069189.tif 000009
【図８】
2013069189.tif 000010
【図９】
2013069189.tif 000011
【図１０】
2013069189.tif 000012
【図１１】
2013069189.tif 000013
【図１２】
2013069189.tif 000014
【図１３】
2013069189.tif 000015
【図１４】
2013069189.tif 000016
【図１５】
2013069189.tif 000017
【図１６】
2013069189.tif 000018
【図１７】
2013069189.tif 000019
【図１８】
2013069189.tif 000020
【図１９】
2013069189.tif 000021
【図２０】
2013069189.tif 000022
【図２１】
2013069189.tif 000023
【図２２】
2013069189.tif 000024
【図２３】
2013069189.tif 000025
【図２４】
2013069189.tif 000026
【図２５】
2013069189.tif 000027
【図２６】
2013069189.tif 000028