(57)【要約】  複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を備え、データユニット出力制御手段は、同一の複数の複製データユニットの出力先をそれぞれ異なるデータユニット処理部に割り当てるとともに、予め設定された少なくとも２つのデータユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、データユニット処理部の組合せ毎に取得した複製データユニット群の数のばらつき度合いが小さくなるように、複数の複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる。
2014125543.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を備え、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【請求項２】
請求項１に記載の情報処理装置であって、
前記データユニット出力制御手段は、さらに、前記データユニット処理部毎に割り当てる前記複製データユニットの数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【請求項３】
請求項１または２に記載の情報処理装置であって、
前記データユニット出力制御手段は、前記データユニット処理部の組合せ毎に取得した、同一の複製データユニットが割り当てられた前記複製データユニット群の数の所定の基準値に対するばらつき度合いを算出し、算出した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【請求項４】
請求項１乃至３のいずれかに記載の情報処理装置であって、
前記データユニット出力制御手段は、前記データユニット処理部の組合せ毎に取得した、同一の複製データユニットが割り当てられた前記複製データユニット群の数のばらつき度合いが小さくなり、且つ、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数の総和が最小になるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【請求項５】
請求項１乃至４のいずれかに記載の情報処理装置であって、
前記データユニット出力制御手段は、出力先としての前記データユニット処理部と、当該データユニット処理部へ割り当てた前記複製データユニットと、を対応付けたデータユニット出力表を生成し、生成した前記データユニット出力表に基づいて、複数の前記複製データユニットを複数の前記データユニット処理部へ出力する、
情報処理装置。
【請求項６】
請求項１乃至５のいずれかに記載の情報処理装置であって、
複数の前記データユニットに対する処理要求を取得し、取得した処理要求を前記各データユニットに対応付けて分割した分割処理要求を生成し、前記データユニット処理部から、当該データユニット処理部に割り当てられた前記複製データユニットを特定する特定情報を取得した場合に、取得した当該特定情報にて特定される前記複製データユニットに対応する前記分割処理要求を、前記データユニット処理部へ出力する処理要求制御手段、
を備える情報処理装置。
【請求項７】
請求項６に記載の情報処理装置であって、
前記処理要求制御手段は、取得した前記特定情報にて特定される前記複製データユニットに対応する前記分割処理要求のうち、他のデータユニット処理部へ出力していない前記分割処理要求であり、且つ、各データユニット処理部に割り当てられた前記複製データユニットの数の総和を算出し、算出した当該総和を前記データユニット処理部の数で割った平均値以下の数の前記分割処理要求を、前記データユニット処理部へ出力する、
情報処理装置。
【請求項８】
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力する場合に、
同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、
予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理方法。
【請求項９】
請求項８に記載の情報処理方法であって、
前記データユニット処理部毎に割り当てる前記複製データユニットの数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理方法。
【請求項１０】
情報処理装置に、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を実現させるとともに、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
ことを実現させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置にかかり、特に、所定のデータに対して分散並列処理を行う情報処理装置に関する。
【背景技術】
【０００２】
大規模データを処理する場合に、大規模データを複数のデータユニットに分割し、分割した複数のデータユニットのそれぞれに対する処理を、複数のワークユニットのそれぞれが行う分散処理システムの技術が知られている。【０００３】
例えば、分散処理システムの技術では、まず大規模データを分割したデータユニット群全体または一部を処理対象にしたクライアントからの処理要求（ジョブ）をデータユニット毎に分割する。続いて、分割した各データユニットに対して所定の処理を行うワークユニットに対するデータユニットの処理要求（タスク）を生成する。次に、この処理要求に応じて、複数のワークユニットのそれぞれは、データユニットに対する所定の処理を行い、処理結果を出力する。そして、分散処理システムの技術では、タスクの処理結果を集約することで、大規模データの全体または一部についてデータユニットに対する処理を行う。【０００４】
このような分散処理システムの技術では、少数のワークユニット（例えば物理サーバ）に障害等が発生しダウンした場合でも処理結果を返すことができる信頼性の高い、大規模データの分散処理システムが望まれている。また、分散処理システムの技術では、多数のワークユニットが必要になるため、ワークユニットと当該ワークユニットへ処理を指示する制御部との間の通信回数および通信量を小さくして、タスクの配送によるオーバーヘッドを小さくすることが望まれている。【０００５】
ここで、分散処理システムの技術では、複数のワークユニットに対する処理負荷を分散する技術が知られている（例えば特許文献１参照）。この特許文献１では、複数のプロセッサに分散配置された各種データに対するアクセス要求があった場合に、アクセス要求に応じた処理を所望のデータが配置されている特定のプロセッサで行う分散型データベース管理システムが処理負荷偏り検出部とデータ配置変更部を備えている。そして、この処理負荷偏り検出部が、データユニットへのアクセス情報とシステム負荷統計情報に基づき、処理負荷偏りを検出し、その負荷偏りに応じて、データの配置構成を変えることで、タスクの負荷を分散させることができる。【０００６】
また、上記の分散処理システムの技術では、データユニットが消失しないように複数のワークユニットのそれぞれに対して同じデータユニットを分散配置するデータの冗長化配置技術が知られている（例えば特許文献２参照）。この特許文献２では、ストレージの物理ノードをグループに分類する手段と、グループ内に分散データと当該分散データの複製データとが存在しないようにデータを割り当てる手段と、を備えている。このような構成を有する分散処理システムは、複製データを複数の異なるグループに配置することで、データの冗長性を保つことができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平９−２１８８５８号公報
【特許文献２】再特ＷＯ２００８／１１４４４１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上記した冗長化配置技術では、冗長性だけを考慮してデータユニットを分散配置するため、複数のワークユニットのそれぞれがデータユニットに対する処理を行う場合に、全ての処理が完了するまでの時間が長くなることがあった。【０００９】
例えば、２つのワークユニットのそれぞれが同一のデータユニットを多く有する場合、一方のワークユニットに障害等が発生すると、他方のワークユニットが一方のワークユニットの代わりにデータユニットに対する処理を行う。このため、他方のワークユニットが処理するデータユニットの数が増加する。また、障害等が発生した一方のワークユニットが保持するデータユニットと同一のデータユニットを保持していない他のワークユニットは、一方のワークユニットの代わりにデータユニットに対する処理を行うことができない。この結果、分散処理システム全体で同時に処理を行うワークユニットの数が少なくなるため、全てのデータユニットに対する処理が完了するまでに時間がかかり、スループットが低下するという問題があった。【００１０】
このため、本発明の目的は、上述した課題であるスループットが低下するという問題を解決することが可能な情報処理装置を提供することにある。
【課題を解決するための手段】
【００１１】
かかる目的を達成するため本発明の一形態である情報処理装置は、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を備え、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
という構成を取る。【００１２】
また、本発明の他の形態である情報処理方法は、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力する場合に、
同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、
予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
という構成を取る。【００１３】
また、本発明の他の形態であるプログラムは、
情報処理装置に、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を実現させるとともに、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
ことを実現させるためのプログラムである。
【発明の効果】
【００１４】
本発明は、以上のように構成されることにより、全てのデータユニットに対する処理のスループットを向上させることができる。
【図面の簡単な説明】
【００１５】
【図１】本発明の第１実施形態に係る分散処理システムの構成を表す図である。
【図２】ワークユニット記憶部の例を説明するための図である。
【図３】マスタデータ記憶部の例を説明するための図である。
【図４】データユニットの割り当てを説明するための図である。
【図５】データユニットの割り当てを説明するための図である。
【図６】ミラーテーブル値を説明するための図である。
【図７】データ配置記憶部の例を説明するための図である。
【図８】データ配置マトリクスの例を示す図である。
【図９】ミラーテーブル値の標準偏差の例を示す図である。
【図１０】データ配置マトリクスの例を示す図である。
【図１１】ミラーテーブル値の標準偏差の例を示す図である。
【図１２】ミラーテーブル値の総和の例を説明するための図である。
【図１３】ジョブ記憶部の例を説明するための図である。
【図１４】タスク記憶部の例を説明するための図である。
【図１５】複製データ記憶部の例を説明するための図である。
【図１６】タスク記憶部の例を説明するための図である。
【図１７】タスク記憶部の例を説明するための図である。
【図１８】タスク記憶部の例を説明するための図である。
【図１９】ジョブ記憶部の例を説明するための図である。
【図２０】ジョブ完了までのタイミングを説明する図である。
【図２１】ジョブ完了までのタイミングを説明する図である。
【図２２】情報処理装置の動作を説明するための図である。
【図２３】データ配置管理部の動作を説明するための図である。
【図２４】データ配置計画部の動作を説明するための図である。
【図２５】タスク管理部の動作を説明するための図である。
【図２６】ワークユニット部の動作を説明するための図である。
【図２７】タスクスケジュール部の動作を説明するための図である。
【図２８】タスク集約部の動作を説明するための図である。
【図２９】本発明の第２実施形態に係る情報処理ユニットの機能を表すブロック図である。
【発明を実施するための形態】
【００１６】
以下、本発明に係る分散処理システムの実施形態について図１乃至図２８を参照して説明する。図１乃至図２１は、分散処理システムの構成を説明するための図である。図２２乃至図２８は、分散処理システムの動作を説明するための図である。
【００１７】
＜第１実施形態＞
（構成）
図１に示すように、本発明の第１実施形態に係る分散処理システム１は、情報処理装置１１と、ジョブクライアント１２と、システム管理クライアント１３と、を備える。ジョブクライアント１２は、情報処理装置１１に実行させるためのジョブ（処理要求）を投入する。システム管理クライアント１３は、ジョブに基づいて生成されるタスク（分割処理要求）を実行する複数のワークユニット（後述するワークユニット部２５）のそれぞれを管理する。そして、情報処理装置１１は、ジョブクライアント１２から投入されたジョブに基づく複数のタスクを生成し、生成した複数のタスクを複数のワークユニットのそれぞれに実行させる。例えば、ジョブクライアント１２は、投入するジョブの内容として任意の文字列を出力する。そして、情報処理装置１１は、ジョブクライアント１２から出力された任意の文字列と、予め記憶された文字列と、を比較し、一致する文字の個数を出力する処理を実行する。
【００１８】
まず、情報処理装置１１の構成について説明する。情報処理装置１１は、ワークユニット管理部２１と、タスク管理部２２と、タスク集約部２３と、データ配置管理部２４と、複数のワークユニット部２５Ａ乃至２５Ｎ（以下、個々に区別しない場合にワークユニット部２５と記載する）と、を備える。なお、情報処理装置１１を構成する各機能部は、例えばそれぞれ異なる物理的なサーバ上に配置される。その場合には、情報処理装置１１を構成する各機能部は、それぞれ中央演算装置（ＣＰＵ：Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ストレージと、ネットワークインタフェースカード（ＮＩＣ）とを備え、オペレーティングシステム（ＯＳ）の制御で動作することができる。そして、ワークユニット管理部２１と、タスク管理部２２と、タスク集約部２３と、データ配置管理部２４と、複数のワークユニット部２５と、を構成する各サーバは、ネットワーク等（例えばＴＣＰ（Transmission Control Protocol）／ＩＰ（Internet Protocol））を介して接続することができる。
【００１９】
以下に、分散処理システム１における、データユニットの割り当て処理と、ジョブ登録処理と、ジョブ実行処理と、のそれぞれについて順番に説明する。データユニットは、所定のデータ（例えば大規模データ）を複数に分割したものである。データユニットの割り当て処理は、各データユニットを複数のワークユニット部２５（データユニット処理部）のそれぞれに割り当てる処理である。ジョブ登録処理は、ジョブクライアント１２から投入されたジョブをデータユニットに対応付けて分割したタスクを生成する処理である。そして、ジョブ実行処理では、ワークユニット部２５が、タスクに基づいて、割り当てられたデータユニットに対する所定の処理を実行する。
【００２０】
なお、データユニットの割り当て処理は最初に1回行われることとし、ジョブ登録処理とジョブ実行処理については、繰り返し実行されることとする。また、データユニットを割り当てるワークユニット部２５の数に変更があったとき等、分散処理システム１の構成が変化した場合に、データユニット割り当て処理は再度行われる。
【００２１】
なお、以下では、ワークユニット部２５の数（ワークユニット数）ｗが３であり、データユニット数ｄが４であり、データユニットの冗長度数ｒが２である場合について説明する。勿論、ワークユニット数ｗとデータユニット数ｄと冗長度数ｒとは上記に限られず、それぞれ２以上の整数であればよい。冗長度数ｒはデータユニット毎に変わらない値である。また、データユニットを複製した、同一の複数の複製データユニットは、それぞれ異なる複数のワークユニット部２５に配置される（割り当てられる）。また、この時、ワークユニット数ｗ＜冗長度数ｒの場合は冗長度を満たせないので、１＜ｒ≦ｗになる。
【００２２】
また、本実施形態では、少ないワークユニット数で負荷均衡が行えることが目的である。そのため、各ワークユニット部２５には１つ以上データユニットが配置されたほうがよく、ワークユニット数ｗ≦データユニット数ｄ×冗長度数ｒが成立する。この条件が成立するように、後述するマスタデータ記憶部６３にデータＩＤ（Identification）とデータ内容を登録し、ワークユニット記憶部３１にはワークユニットＩＤとワークユニット名を記録する。
【００２３】
最初に、複数のワークユニット部２５（データユニット処理部）のそれぞれに、複数のデータユニットを割り当てる（配置する）データユニットの割り当て処理について説明する。ここでは、まず、ワークユニット管理部２１の構成について説明する。ワークユニット管理部２１は、図２に示すように、ワークユニット部２５毎に予め設定したユニークなワークユニットＩＤと、ワークユニット部２５（例えばワークユニット名）と、を対応付けて記憶するワークユニット記憶部３１を備える。例えば、ワークユニット記憶部３１には、ワークユニットＩＤ「１」乃至「３」のそれぞれに対応付けられた３つのワークユニット部２５（例えばワークユニット名）が記憶される。
【００２４】
続いて、データ配置管理部２４（データユニット出力制御手段）の構成について説明する。データ配置管理部２４は、データ配置計画部６１と、データ配置実行部６２と、マスタデータ記憶部６３と、データ配置記憶部６４と、を備える。
【００２５】
マスタデータ記憶部６３は、データユニット毎に予め設定したユニークなデータＩＤと、当該データＩＤにて示されるデータユニットのデータ内容と、を対応付けて記憶する（例えば図３）。例えば、分散処理システム１では、ジョブクライアント１２が情報処理装置１１へジョブを投入する前に、システム管理クライアント１３が、データＩＤとデータ内容とをデータ配置管理部２４へ出力する。そして、データ配置管理部２４が、取得したデータＩＤとデータ内容とをマスタデータ記憶部６３に記憶する。なお、データ内容は、後述するワークユニット部２５のタスク実行部７２が処理を行えるデータ内容であれば、どのような内容でもよい。
【００２６】
データ配置計画部６１は、ワークユニット記憶部３１に記憶された複数のワークユニット部２５の情報と、マスタデータ記憶部６３に記憶された複数のデータユニットとの情報と、予め設定されたデータユニットの冗長度数ｒと、に基づいて、複数のワークユニット部２５のそれぞれへ複数のデータユニットを割り当てる（配置を計画する）。そして、データ配置計画部６１は、複数のデータユニットのそれぞれを予め設定された数（冗長度数ｒ）ずつ複製した各データユニット（複製データユニット）を、複数のワークユニット部２５へ出力する。
【００２７】
具体的には、データ配置計画部６１は、以下の４つの条件を満たすように複数のデータユニットを複数のワークユニット部２５のそれぞれに割り当てる。すなわち、まず、データ配置計画部６１は、（Ａ）同一のデータＩＤに対応するデータユニットの複製（同一の複数の複製データユニット）を、それぞれ異なるワークユニット部２５に割り当てる。そして、データ配置計画部６１は、（Ｂ）各データＩＤに対応するデータユニットの数（データユニットの冗長度数ｒ）を全て等しくする。さらに、データ配置計画部６１は、（Ｃ）各ワークユニット部２５に割り当てるデータユニット数（複製データユニットの数）の標準偏差が最小となる（ばらつき度合いが小さくなる）組合せを選択する。そして、さらに、データ配置計画部６１は、選択した組合せの中で（Ｄ）異なる少なくとも２つのワークユニット部２５に割り当てられる同一のデータＩＤに対応するデータユニットの個数（ミラーテーブル値、複製データユニット群の数）の標準偏差が最小になり、かつ、ワークユニット部２５の組合せのミラーテーブル値の合計値（総和）が最小になる配置パターンを選択する。そして、これらの条件を満たすデータ配置パターンが複数存在する場合には、データ配置計画部６１は、任意の一つの配置パターンを選択する。なお、（Ａ）と（Ｂ）の条件は満たさなければならないが、（Ｃ）、（Ｄ）の順番は逆でも良い。また、（Ｃ）と（Ｄ）の条件のうちの一方（特に条件（Ｄ））を満たすようにすることもできる。
【００２８】
以下、データ配置計画部６１のデータユニットの割り当て処理について具体的に説明する。まず、データ配置計画部６１は、例えばワークユニットＩＤを縦軸、データＩＤを横軸としたデータ配置マトリクス（データユニット出力表）を作成する。そして、データ配置計画部６１は、作成したデータ配置マトリクスの領域を理想データ配置可能領域と理想データ配置不可能領域とに分割する。
【００２９】
具体的には、データ配置計画部６１は、データ配置マトリクスのデータＩＤ列の領域を、データＩＤの若い順から、ワークユニット数ｗとデータユニットの冗長度数ｒの組合せ数（ｗＣｒ）毎に分割する。ここで、データ配置マトリクスの領域のうち、区切られた領域の列数がｗＣｒとなる領域を理想データ配置可能領域とし、区切られた領域の列数がｗＣｒより小さい値となる領域を理想データ配置不可能領域とする。
【００３０】
例えば、ワークユニット数ｗが３であり、データユニットの冗長度数ｒが２である場合、ワークユニット数ｗと冗長度数ｒの組合せ数は３Ｃ２＝３になる。このため、データ配置計画部６１は、図４に示すようにデータＩＤ「１」乃至「３」の列の領域を理想データ配置可能領域１０１として分割し、図５に示すようにデータＩＤ「４」の列の領域を理想データ配置不可能領域１０２として分割する。例えば、上記したようにワークユニット数ｗが３になり、データユニット数ｄが３になり、冗長度数ｒが２になる場合、ワークユニットＩＤとデータＩＤとの組合せｗＣｒは３であり、データユニット数ｄも３であるため、理想データ配置可能領域の数は１（ｗＣｒをｄで割った商）になる。
【００３１】
続いて、データ配置計画部６１は、分割した理想データ配置可能領域１０１に対して、複数のデータユニットの配置を計画する（データユニットの割り当てを行う）。具体的には、データ配置計画部６１は、まず、全ワークユニットＩＤから予め設定されたデータユニットの冗長度数ｒのワークユニットＩＤを選択する組合せ（データ配置パターン）を算出する。例えば、３つのワークユニットＩＤ「１」乃至「３」から２つ（冗長度数ｒ）のワークユニットＩＤを選択する場合、その組合せは（１，２），（１，３），（２，３）の３通りになる。
【００３２】
そして、データ配置計画部６１は、理想データ配置可能領域に、算出したデータ配置パターンを均一に割り当てる（例えば図４参照）。この条件を満たせば、ワークユニットＩＤの組合せを、理想データ配置可能領域内のどのデータＩＤの列に配置してもよい。なお、データ配置計画部６１は、理想データ配置可能領域１０１に対するデータ配置パターンが複数存在する場合には、任意の一つを選ぶ。例えば、データ配置計画部６１は、図４に示すように、ワークユニットＩＤの組合せ（１，２）をデータＩＤ「１」の列に割り当てる。また、データ配置計画部６１は、ワークユニットＩＤの組合せ（１，３）をデータＩＤ「２」の列に割り当てる。さらに、データ配置計画部６１は、ワークユニットＩＤの組合せ（２，３）をデータＩＤ「３」の列に割り当てる。このように、データ配置計画部６１は、各ワークユニットＩＤの組み合わせを各データＩＤの列に割り当てたデータ配置パターンを選択（算出）する。
【００３３】
次に、データ配置計画部６１は、理想データ配置不可能領域１０２に対して、冗長度数ｒを満たすようにデータユニットを配置する。具体的には、データ配置計画部６１は、理想データ配置不可能領域１０２に対して、ｗ個のワークユニットＩＤからｒ個のワークユニットＩＤを選択するワークユニットＩＤの組合せｗＣｒを割り当てるデータ配置パターンを算出する。図５の例では、データ配置計画部６１は、データ配置パターンとして、データＩＤ「４」の列に配置するワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を算出する。
【００３４】
次に、データ配置計画部６１は、上述した条件（Ｃ）を満たすデータ配置パターンを算出する。つまり、データ配置計画部６１は、理想データ配置可能領域１０１と理想データ配置不可能領域１０２とのそれぞれに対して算出したデータ配置パターンから、各ワークユニットＩＤに割り当てられるデータユニット数の標準偏差が最小になるデータ配置パターンを算出する。なお、上記した例では、算出したデータ配置パターン（ワークユニットＩＤの組合せ（１，２），（２，３），（１，３））のそれぞれに対して算出した各ワークユニットＩＤに割り当てられるデータユニット数の標準偏差は、全て同じになる。従って、データ配置計画部６１は、理想データ配置不可能領域１０２に対するデータ配置パターンとして、ワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を算出する。
【００３５】
次に、データ配置計画部６１は、上述した条件（Ｄ）を満たすデータ配置パターンを算出る。つまり、データ配置計画部６１は、算出したデータ配置パターンの中から、ミラーテーブル値の標準偏差が最小になるデータ配置パターンを選択する。ミラーテーブル値は、予め設定された少なくとも２つの各ワークユニット部２５に同一のデータＩＤのデータユニットが割り当てられた同一のデータＩＤのデータユニットの個数（同一の複製データユニット群の数）を表す。ここでは、データ配置計画部６１は、算出したワークユニットＩＤの組合せ毎に、ミラーテーブル値を算出（取得）し、ミラーテーブル値の標準偏差が最小になり、且つ、ワークユニット間のミラーテーブル値の合計値が最小になるデータ配置パターンを選択する。なお、データ配置計画部６１は、少なくともミラーテーブル値の標準偏差が最小になるデータ配置パターンを選択すればよい。
【００３６】
図５は、理想データ配置不可能領域１０２（データＩＤ「４」の列）のデータ配置パターンとして、ワークユニットＩＤの組合せ（１，２）を選択した例を示す図である。そして、例えば、データ配置計画部６１は、図５のデータ配置パターンに対して、ワークユニットＩＤの組合せ毎にミラーテーブル値を算出する。つまり、データ配置計画部６１は、図６に示すように、ワークユニットＩＤの組合せ（１，２）に対するミラーテーブル値として「２」を算出する。また、データ配置計画部６１は、ワークユニットＩＤの組合せ（２，３）に対するミラーテーブル値として「１」を算出する。そして、データ配置計画部６１は、ワークユニットＩＤの組合せ（１，３）に対するミラーテーブル値として「１」を算出する。なお、上記した例では、算出したデータ配置パターン（ワークユニットＩＤの組合せ（１，２），（２，３），（１，３））のそれぞれに対して算出したワークユニットＩＤの組合せ毎のミラーテーブル値の標準偏差は、全て同じになる。従って、例えば、データ配置計画部６１は、理想データ配置不可能領域１０２に対するデータ配置パターンとして、ワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を選択する。
【００３７】
なお、上述した条件（Ｃ）と（Ｄ）とを満たす理想データ配置不可能領域１０２のデータ配置パターンが複数ある場合には、データ配置計画部６１は、任意の一つを理想データ配置不可能領域１０２のデータ配置パターンとして選択する。例えば、データ配置計画部６１は、データＩＤ「４」の列に対して、ワークユニットＩＤの組合せが（１，２）になるデータ配置パターンを選択する。これにより、データ配置計画部６１は、複数のデータユニットを複数のワークユニット部２５のそれぞれに割り当てるデータ配置パターンを決定することができる。
【００３８】
そして、データ配置計画部６１は、作成したデータ配置マトリクスを、データ配置記憶部６４に記憶する。図７はワークユニット数が３、データ数が４の場合のデータ配置マトリクスの例である。図７の例では、「○」がワークユニットＩＤに対応するワークユニット部２５に、データＩＤに対応する複製データユニットを割り当てた（配置済みである）ことを示している。また、図７の例では、空欄は、ワークユニット部２５に複製データユニットを配置していないことを意味している。
【００３９】
ここで、上述した条件（Ａ）乃至（Ｃ）を満たすが、条件（Ｄ）を満たさない場合のデータ配置パターンについて説明する。図８は、データユニットの冗長度数ｒと各ワークユニットに割り当てられたデータユニットの数は等しいが、図７のデータ配置マトリクスよりもミラーテーブル値の標準偏差値が大きくなるデータ配置マトリクスの例である。そして、データ配置計画部６１は、図８のデータ配置マトリクスのデータ配置パターンに対して、ワークユニットＩＤの組合せ毎にミラーテーブル値を算出し、標準偏差を算出する。図９は、図８のデータ配置マトリクスのデータ配置パターンに対して算出したミラーテーブル値と標準偏差を示す図である。図９に示すように、図８のデータ配置マトリクス（のデータ配置パターン）におけるミラーテーブル値の標準偏差は０．９４となる。
【００４０】
一方、上述した条件（Ａ）乃至（Ｃ）に加えて、条件（Ｄ）を満たすデータ配置パターンは、図１０のデータ配置マトリクスのようになる。そして、データ配置計画部６１は、図１０のデータ配置マトリクスのデータ配置パターンに対して、ミラーテーブル値と標準偏差を算出する。ミラーテーブル値と標準偏差の算出結果を図１１に示す。図１１に示すように、図１０のデータ配置マトリクスにおけるミラーテーブル値の標準偏差値は、０．４７になる。
【００４１】
また、図１２Ａを参照して、条件（Ｄ）を満たさない場合のデータ配置パターンについて説明する。図１２Ａは、ミラーテーブル値の総和が大きくなるデータ配置マトリクスの例である。図１２Ａに示すように、ワークユニットＩＤ「１」，「２」のワークユニット部２５のそれぞれには、データＩＤ「１」，「２」のデータユニットが割り当てられている。この場合、データ配置計画部６１は、ミラーテーブル値（の総和）として２を算出し、標準偏差として０を算出する。
【００４２】
一方、条件（Ｄ）を満たすデータ配置パターンは、図１２Ｂのデータ配置マトリクスのようになる。図１２Ｂの例では、データ配置計画部６１は、ミラーテーブル値（の総和）として１を算出し、標準偏差として０を算出する。このように、ミラーテーブル値の標準偏差が同じ値でも、ミラーテーブル値の合計値（総和）が異なる場合がある。このような場合に、データ配置計画部６１は、ミラーテーブル値の総和が最小になるデータ配置パターンを選択する。
【００４３】
このように、ミラーテーブル値の標準偏差（ばらつき度合い）が小さくなり、かつ、ワークユニット部２５の組合せのミラーテーブル値の合計値が最小になるようにデータ配置パターンを選択（算出）することで、重複するデータユニットが１つのワークユニット部２５に集中することがなく分散して割り当てられる。従って、あるワークユニット部２５に障害等が発生した場合でも、障害等が発生したワークユニット部２５が保持するデータユニットと同一のデータユニットを保持するワークユニット部２５が、代わりにデータユニットに対する処理を行うことができる。この結果、全てのデータユニットに対するタスクを迅速に行い、スループットを向上させることができる。
【００４４】
最後に、データ配置実行部６２は、データ配置記憶部６４に記憶されたデータ配置マトリクスに基づいて、複数のデータユニットを複数のワークユニット部２５のそれぞれへ出力する。具体的には、データ配置実行部６２は、データ配置マトリクスに基づいて、複製データユニットが配置済みのワークユニットＩＤとデータＩＤの組合せのデータ配置リストを取得する。そして、データ配置実行部６２は、データＩＤをキーにしてマスタデータ記憶部６３からデータ内容を取得し、ワークユニットＩＤに対応するワークユニット部２５の複製データ記憶部７３に、データＩＤと当該データＩＤに対応するデータ内容とを出力する。これにより、複製データ記憶部７３に、複製データユニットが記憶され、複数の複製データユニットを複数のワークユニット部２５のそれぞれに配置することができる。
【００４５】
次に、ジョブを実行するためのジョブ登録処理について説明する。まず、タスク管理部２２の構成について説明する。タスク管理部２２（処理要求制御手段）は、ジョブ受信部４１と、タスク生成部４２と、タスクスケジュール部４３と、ジョブ記憶部４４と、タスク記憶部４５と、を備える。
【００４６】
ジョブ受信部４１は、ジョブクライアント１２からジョブを受信し、受信したジョブをジョブ記憶部４４に記憶する。例えば、ジョブ受信部４１は、ジョブクライアント１２からジョブを受信すると、ジョブ毎にユニークなジョブＩＤを発行する。そして、ジョブ受信部４１は、図１３に示すようにジョブ記憶部４４にジョブＩＤと、ジョブクライアント１２が投入するジョブ内容と、ジョブを受信したことを表すジョブ状態「待機中」と、を対応付けて記憶する。ジョブ状態は、ジョブに関連するタスクがタスクスケジュール部４３により出力されると「実行中」に変更され、ジョブに関連する全てのタスクが完了すると「完了」に変更される。また、ジョブ受信部４１は、ジョブを受信した場合に、タスク生成部４２にジョブをタスクに分割するように要求を出す。
【００４７】
タスク生成部４２は、ジョブ受信部４１が受信したジョブを、マスタデータ記憶部６３に記憶されたデータユニットの数に応じて分割した、当該データユニットに対するタスクを生成し、生成した各タスクをタスク記憶部４５に記憶する。そして、タスク生成部４２は、図１４に示すように、タスクを識別するタスクＩＤと、タスクの元となるジョブＩＤと、タスクの対象になるデータユニットのデータＩＤと、タスクが登録された状態であるタスク状態「待機中」と、を対応付けてタスク記憶部４５に記憶する。タスク状態は、タスク生成部４２がタスクを生成しタスク記憶部４５に記憶した段階では「待機中」になる。また、タスク状態は、タスクスケジュール部４３がワークユニット部２５にタスクを出力した時には「実行中」になる。そして、タスク状態は、ワークユニット部２５がタスク結果を処理しタスク結果をタスク集約部２３に出力し、タスク集約部２３がタスク記憶部４５にタスク結果を記憶した時に「完了」になる。このように、タスク生成部４２は、ジョブから、複数のデータユニットのそれぞれに対応付けて分割したタスクを生成し、タスク記憶部４５に登録（記憶）する。
【００４８】
最後に、ジョブ実行処理について説明する。この例では、図７のデータ配置マトリクスに基づいて、３つのワークユニット部２５のそれぞれにデータユニットが割り当てられた状態であるとする。つまり、ワークユニットＩＤ「１」のワークユニット部２５（複製データ記憶部７３）には、データＩＤ「１」，「２」，「４」のデータユニットの複製（複製データユニット）が配置されているものとする。また、ワークユニットＩＤ「２」のワークユニット部２５には、データＩＤ「１」，「３」，「４」のデータユニットの複製が配置されているものとする。そして、ワークユニットＩＤ「３」のワークユニット部２５には、データＩＤ「２」，「３」のデータユニットの複製が配置されているものとする（例えば、図１５参照）。
【００４９】
ここで、ジョブに基づくタスクを実行するワークユニット部２５について説明する。ワークユニット部２５は、タスク要求部７１と、タスク実行部７２と、複製データ記憶部７３と、を備える。タスク要求部７１は、実行するタスクが無いあるいは少ない場合に、分散処理システム１全体でユニークであるワークユニットＩＤと、複製データ記憶部７３に記憶されたデータＩＤ（データユニットを特定する特定情報）の全てを、タスクスケジュール部４３にタスク要求として出力する。例えば、ワークユニットＩＤ「３」のワークユニット部２５は、自身の複製データ記憶部７３に記憶されたデータＩＤ「２」，「３」を示すリストを作成し、当該リストと、自身のワークユニットＩＤ「３」と、を対応付けたタスク要求をタスクスケジュール部４３に出力する。
【００５０】
そして、タスクスケジュール部４３は、ワークユニット部２５から出力されたタスク要求に対するタスクをタスク記憶部４５から取得し、タスク要求を出力したワークユニット部２５へ、取得したタスクを出力する。例えば、タスクスケジュール部４３は、ワークユニットＩＤ「３」のワークユニット部２５から出力された、ワークユニットＩＤ「３」と、当該ワークユニット部２５自身が記憶するデータＩＤ「２」，「３」を示すリストを受信する。続いて、タスクスケジュール部４３は、タスクの状態が「待機中」であり、かつ、受信したリストに含まれるデータＩＤに合致するタスクＩＤをタスク記憶部４５から検索し、合致する全てのまたは一部のジョブＩＤを取得する。なお、タスクスケジュール部４３は、ジョブＩＤを取得する際に、複数のジョブＩＤが存在する場合には、一つのジョブＩＤを取得してもよいし、全てのジョブＩＤを取得してもよい。例えば、タスクスケジュール部４３は、データＩＤ「２」，「３」に合致するタスクＩＤ「２」，「３」を検索し、タスクＩＤ「２」，「３」のそれぞれに対応するタスクの情報を取得する。
【００５１】
そして、タスクスケジュール部４３は、タスクＩＤ「２」，「３」のそれぞれに、タスクを要求したワークユニットＩＤ「３」を対応付けて登録するとともに、タスク状態として「実行中」を登録する（例えば図１６参照）。続いて、タスクスケジュール部４３は、取得したジョブＩＤ（例えばジョブＩＤ「１」）に対応するジョブ内容を取得する。最後に、タスクスケジュール部４３は、タスクＩＤと、ジョブＩＤと、データＩＤと、ジョブの内容と、を一つのタスク要求のレスポンス（タスク情報）にし、ワークユニット部２５へ出力する。例えば、タスクスケジュール部４３は、ワークユニットＩＤ「３」のワークユニット部２５へ、データＩＤ「２」，「３」に対応するタスク情報を出力する。
【００５２】
ワークユニット部２５のタスク要求部７１は、タスクスケジュール部４３からタスク要求のレスポンス（タスク情報）を受信した場合、タスク実行部７２に、タスク情報を出力する。そして、タスク実行部７２は、タスク情報に含まれるジョブの内容に基づいて、タスク（データユニットに対する所定の処理）を実行する。１つのタスクは、特定のデータユニットに対応付けられている。このため、タスク実行部７２は、タスク情報に含まれるデータＩＤをキーにして、複製データ記憶部７３からタスクの対象になる複製データユニットを取得する。続いて、タスク実行部７２は、複製データ記憶部７３に記憶された複製データユニットのデータ内容と、ジョブ内容と、に基づいて、タスクを実行する。実行する内容については、ジョブ内容とデータ内容に対するどのような処理であってもよい。また、タスク実行部７２は、一つのジョブＩＤに対応付けられたタスク群を並列に実行してもよいし、シリアル（１つずつ順番）に実行してもよい。
【００５３】
例えば、図１５に示すように、データＩＤ「２」のデータ内容は「ＹＹＹ」であり、データＩＤ「３」のデータ内容は「ＺＺＺ」であり、図１３に示すように、ジョブＩＤ「１」のジョブ内容は「ＡＡＡ」である。従って、タスク実行部７２は、タスクの処理がジョブ内容とデータ内容とで一致する文字数をカウントする処理の場合には、タスクＩＤ「２」のタスク処理結果として「０」を出力し、タスクＩＤ「３」のタスク処理結果として「０」を出力する。
【００５４】
そして、タスク実行部７２は、タスク情報に含まれる一部または全てのタスク群の実行が完了した場合に、タスクＩＤと、タスクＩＤに紐付くジョブＩＤと、タスクの処理結果としてのタスク結果と、からなるタスクの実行結果のリストを、タスク実行結果群として、タスク結果受信部５１に出力する。また、タスク実行部７２は、タスク要求部７１に新たなタスクを取得するように依頼をする。
【００５５】
ここで、ワークユニットＩＤ「３」のワークユニット部２５がタスク要求を出力した後、ワークユニットＩＤ「１」のワークユニット部２５がタスク要求を出力した場合について説明する。例えば、ワークユニットＩＤ「１」のワークユニット部２５は、自身の複製データ記憶部７３に記憶されたデータＩＤ「１」，「２」，「４」を示すリストを作成する。そして、ワークユニットＩＤ「１」のワークユニット部２５は、当該リストと、自身のワークユニットＩＤ「１」と、を対応付けたタスク要求をタスクスケジュール部４３に出力する。
【００５６】
続いて、タスクスケジュール部４３は、ワークユニットＩＤ「１」のワークユニット部２５から出力された、ワークユニットＩＤ「１」と、当該ワークユニット部２５自身が記憶するデータＩＤ「１」，「２」，「４」を示すリストを受信する。すると、タスクスケジュール部４３は、データＩＤ「１」，「２」，「４」に合致するタスクＩＤ「１」，「２」，「４」を検索し、タスク状態が「待機中」であるタスクＩＤ「１」，「４」のそれぞれに対応するタスクの情報を取得する。
【００５７】
そして、タスクスケジュール部４３は、タスクＩＤ「１」，「４」のそれぞれに、タスクを要求したワークユニットＩＤ「１」を対応付けて登録するとともに、タスク状態として「実行中」を登録する（例えば図１６参照）。続いて、タスクスケジュール部４３は、取得したジョブＩＤ「１」に対応するジョブ内容を取得し、タスクＩＤと、ジョブＩＤと、データＩＤと、ジョブの内容と、をタスク情報として、ワークユニットＩＤ「１」のワークユニット部２５へ出力する。
【００５８】
なお、タスクの配送（出力）方法は、上記に限られない。例えば、タスクスケジュール部４３は、各ワークユニット部２５に割り当てられたデータユニットの数の平均値以下の数のタスクをワークユニット部２５へ出力することができる。まず、タスクスケジュール部４３は、各ワークユニット部２５に割り当てられたデータユニット数の総和を算出する。図７の例では、ワークユニットＩＤ「１」のワークユニット部２５には３つのデータユニットが割り当てられている。また、ワークユニットＩＤ「２」のワークユニット部２５には３つのデータユニットが割り当てられている。そして、ワークユニットＩＤ「３」のワークユニット部２５には２つのデータユニットが割り当てられている。従って、タスクスケジュール部４３は、データユニット数の総和として８（＝３＋３＋２）を算出する。なお、データユニット数の総和は、冗長度数ｒ（＝２）とデータユニット数ｄ（＝４）との積により算出することができる。そして、タスクスケジュール部４３は、算出したデータユニット数の総和をワークユニット数ｗ（＝３）で割り、平均値（＝２．６）を算出する。
【００５９】
そして、タスクスケジュール部４３は、算出した平均値以下の数のタスクを取得する。例えば、タスクスケジュール部４３は、算出した平均値が２．６である場合、最大で２つのタスクを取得する。例えば、タスクスケジュール部４３は、３つのタスク（タスクＩＤ「１」，「３」，「４」）から任意の２つのタスクを選択する。そして、タスクスケジュール部４３は、選択した２つのタスクをワークユニットＩＤ「２」のワークユニット部２５へ出力する。このように、一度に出力するタスクの最大値を設定することで、所定のワークユニット部２５に割り当てられたデータユニットに対する分割処理要求の全てが、他のデータユニット処理部に出力される可能性が小さくなり、分割処理要求に対する処理を行うことができないデータユニット処理部の数が減少する。この結果、全ての分割処理要求（データユニット）に対する処理を迅速に行い、スループットを向上させることができる。
【００６０】
続いて、ワークユニット部２５からタスク実行結果群を受信するタスク集約部２３の構成の詳細について説明する。タスク集約部２３は、タスク結果受信部５１と、ジョブ結果出力部５２と、を備える。
【００６１】
タスク結果受信部５１は、ワークユニット部２５から受信したタスク実行結果群を、タスク毎にタスク記憶部４５に記憶する。具体的には、タスク結果受信部５１は、タスク実行結果群に含まれるタスクのタスクＩＤをキーにして、タスク記憶部４５から該当するレコードを探し、タスクのタスク実行結果をタスク結果として記憶するとともに、タスク状態として「完了」をタスク記憶部４５に記憶する。続いて、タスク結果受信部５１は、タスク実行結果の受信後に、ジョブ結果出力部５２にジョブの完了判定依頼を出力する。
【００６２】
ジョブ結果出力部５２は、ジョブの完了判定処理を行い、ジョブに紐付くタスクが全て「完了」になっている場合にタスクの集計処理を行い、ジョブの結果生成をしてクライアントに出力する。具体的には、ジョブ結果出力部５２は、タスク記憶部４５に記憶されたタスク群をジョブＩＤ毎にグルーピングし、そのジョブＩＤ毎に、そのジョブＩＤに紐付くタスク群のタスク状態が全て「完了」になっているかを判定する。そして、ジョブ結果出力部５２は、ジョブＩＤ毎にジョブＩＤに紐付くタスクのタスク状態が全て「完了」である場合（例えば図１８）には、そのジョブＩＤは完了していると判定する。そして、ジョブ結果出力部５２は、ジョブのタスク記憶部４５のそのジョブＩＤに紐付くタスクのタスク結果を取得し、タスク結果に対して集計処理を行い、ジョブ結果を生成する。集計処理はタスク結果に対するどのような処理でも良く、それにより生成されるジョブ結果もどのようなものでもよい。ジョブ結果出力部５２は、完了していないジョブＩＤのジョブに対しては何もしない。続いて、ジョブ結果出力部５２は、完了したジョブのジョブ結果をジョブクライアント１２に返却し、ジョブ記憶部４４の該当するジョブＩＤのジョブ状態を「完了」に変更する（例えば図１９）。
【００６３】
ここで、図２０と図２１とを参照して、ミラーテーブル値の標準偏差の違いによるジョブ完了までの処理について説明する。図２０は、ミラーテーブル値の標準偏差が高いデータ配置パターン（例えば図８）のジョブ完了までのタイミングチャートを示す。図２１は、ミラーテーブル値の標準偏差が最小になるデータ配置パターン（例えば図１０）のジョブ完了までのタイミングチャートを示す。なお、図２０と図２１の例では、ジョブ「１」乃至「４」の４つのジョブのそれぞれに、４つのタスク「１」乃至「４」が割り当てられており、当該タスクが対象とするデータユニットが図８または図１０のデータ配置パターンに示すように割り当てられているものとする。また、ここでは、１つのタスク（データユニットに対する処理）が完了するのに１秒かかるものとする。さらに、タスクスケジュール部４３は、ジョブの番号が小さい順（つまりジョブ「１」から順番）に、ジョブに対応するタスクを出力するものとする。
【００６４】
そして、図２０の例では、図８のデータ配置パターンに示すようにデータユニットが記憶されているものとする。つまり、例えば、ワークユニット部「ＷＵ１」，「ＷＵ２」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「１」，「３」のデータユニットを予め記憶している。また、ワークユニット部「ＷＵ３」，「ＷＵ４」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「２」，「４」のデータユニットを予め記憶している。
【００６５】
この図２０の例では、まず、ワークユニット部「ＷＵ１」がタスクスケジュール部４３に対してタスク要求を出力し、ジョブ「１」に対応するタスク「１」，「３」（以下、ジョブ１（１，３）と記載する）を取得する。そして、ワークユニット部「ＷＵ１」は、取得したタスクを実行する。また、同様に、ワークユニット部「ＷＵ２」は、ジョブ２（１，３）を取得し、取得したタスクを実行する。続いて、ワークユニット部「ＷＵ３」は、ジョブ１（２，４）を取得し実行し、ワークユニット部「ＷＵ４」は、ジョブ２（２，４）を取得し実行する。これにより、タスクスケジュール部４３は、ジョブ「１」，「２」に対するタスクを全て出力することができる。
【００６６】
このような場合に、ワークユニット部「ＷＵ３」に障害等が発生し、ジョブ１（２，４）が完了するまでに５秒かかる例について説明する。ワークユニット部「ＷＵ１」は、ジョブ１（１，３）が完了する（２秒経過する）と、続いてジョブ３（１，３）を取得し実行する。また、同様にワークユニット部「ＷＵ２」は、ジョブ２（１，３）が完了すると、続いてジョブ４（１，３）を取得し実行する。これにより、ジョブ「１」乃至「４」のそれぞれに対応するタスク「１」，「３」を全て実行することができる。
【００６７】
一方、ワークユニット部「ＷＵ４」は、ジョブ２（２，４）が完了したとき、ワークユニット部「ＷＵ３」はジョブ１（２，４）を実行中であるので、ジョブ３（２，４）を取得し実行する。そして、ワークユニット部「ＷＵ４」は、ジョブ３（２，４）が完了したとき、ワークユニット部「ＷＵ３」はまだジョブ１（２，４）を実行中であるので、ジョブ４（２，４）を取得し実行する。このため、図２０の例では、ジョブ「１」乃至「４」のそれぞれに対応する全てのタスクが完了するまでの時間は６秒になる。
【００６８】
これに対して、図２１の例では、図１０のデータ配置パターンに示すようにデータユニット部が記憶されているものとする。つまり、例えば、ワークユニット部「ＷＵ１」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「１」，「４」のデータユニットを予め記憶している。そして、ワークユニット部「ＷＵ２」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「１」，「２」のデータユニットを予め記憶している。同様に、ワークユニット部「ＷＵ３」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「２」，「３」のデータユニットを予め記憶しており、ワークユニット部「ＷＵ４」は、ジョブ１乃至４のそれぞれに対応するデータＩＤ「３」，「４」のデータユニットを予め記憶している。
【００６９】
図２１の例では、まず、ワークユニット部「ＷＵ１」は、ジョブ１（１，４）を取得し実行する。続いて、ワークユニット部「ＷＵ３」は、ジョブ１（２，３）を取得し実行する。同様に、ワークユニット部「ＷＵ２」は、ジョブ２（１，２）を取得し実行し、ワークユニット部「ＷＵ４」は、ジョブ２（３，４）を取得し実行する。これにより、タスクスケジュール部４３は、ジョブ「１」，「２」に対するタスクを全て出力することができる。このような場合に、図２０の例と同様に、ワークユニット部「ＷＵ３」に障害等が発生し、ジョブ１（２，３）が完了するまでに５秒かかる例について説明する。
【００７０】
ワークユニット部「ＷＵ１」は、ジョブ１（１，４）が完了する（２秒経過する）と、続いてジョブ３（１，４）を取得し実行する。次に、ワークユニット部「ＷＵ２」は、ジョブ２（１，２）が完了すると、ジョブ３（２）を取得し実行する。続いて、ワークユニット部「ＷＵ４」は、ジョブ２（３，４）が完了すると、ジョブ３（３）を取得し実行する。これにより、タスクスケジュール部４３は、ジョブ「３」に対するタスクを全て出力することができる。
【００７１】
そして、ワークユニット部「ＷＵ２」は、ジョブ３（２）が完了する（１秒経過する）と、ジョブ４（１，２）を取得し実行する。同様に、ワークユニット部「ＷＵ４」は、ジョブ３（３）が完了すると、ジョブ４（３，４）を取得し実行する。このため、図２１の例では、ジョブ「１」乃至「４」のそれぞれに対応する全てのタスクが完了するまでの時間は５秒になる。このように、上述した条件（Ａ）乃至（Ｄ）を満たすデータ配置パターンを選択することで、スループットを向上することができる。
【００７２】
このように、本実施形態では、データユニットの冗長度が等しくなるように、ワークユニット部２５にデータユニットが配置されている。そして、ワークユニット部２５が保持するデータユニット数の標準偏差が最小となるようにワークユニット部２５に均一のデータユニット数が配置される。さらに、ワークユニット部２５間で同一の複製データユニットを保持する個数の標準偏差が小さくなるような配置になるデータ配置パターンを作成する。このような、データ配置パターンを作成することによりシステムの冗長性の維持とワークユニット部２５の負荷分散が可能になる。
【００７３】
さらに、データユニットが配置されたワークユニット部２５は、自身が保持するデータＩＤのリストをタスクスケジュール部４３に出力し、タスクスケジュール部４３は処理対象であるデータユニットの識別子が合致するタスク群の中から、他のワークユニット部２５が既に取得していないタスクを返す。このため、タスクスケジュール部４３は、ワークユニット部２５で必要なタスクでかつ他のワークユニット部２５で実行されていないタスク群だけを出力するため、データユニットが冗長配置されていても同じデータユニットに対するタスクを重複して処理することがない。このように構成されているため、異なるワークユニット部２５で同時に複数の異なるタスク群を分散して実行できるため、システムの冗長度を保ちながら、ジョブが完了するまでの時間を短くすることができる。
【００７４】
（動作）
以下では、図２２を用いて、分散処理システム１の全体の動作手順について詳細に説明する。まず初めに、ジョブがクライアントから投入される前に、各ワークユニット部２５には処理対象となるデータ配備がされていなければならない。データ配備が行われた後に、ジョブクライアント１２からのジョブ登録と、タスクスケジュール部４３と、ワークユニット部２５と、タスク集約部２３と、によるジョブ実行の動作手順が動作することで、ジョブが実行されクライアントにジョブ結果が出力される。以下では、データ配備の動作手順、ジョブ登録の手順、ジョブ実行の手順の詳細について説明を行う。
【００７５】
まず、図２２を参照して、本実施の形態におけるデータ配備の動作手順について説明する。ここでは、まず、ワークユニット管理部２１は、ワークユニット記憶部３１にワークユニットを登録する（ステップＳ１）。具体的には、まず、システム管理クライアント１３が複数のワークユニット部２５のそれぞれにユニークな（個別の）ワークユニットＩＤを払い出す。そして、ワークユニット管理部２１は、システム管理クライアント１３にて払い出されたワークユニットＩＤを取得し、ワークユニット記憶部３１に登録（記憶）する。例えば、ワークユニット部２５が３つ存在する場合、図２に示すように、ワークユニット記憶部３１に３つのワークユニットＩＤと、当該ワークユニットＩＤに対応するワークユニット部２５の情報（例えばワークユニット名）と、が対応付けて記憶される。
【００７６】
続いて、データ配置管理部２４は、データ配置記憶部６４にマスタデータを登録する（ステップＳ２）。具体的には、ます、システム管理クライアント１３が複数のデータユニットのそれぞれにユニークなデータＩＤを払い出す。そして、データ配置管理部２４は、システム管理クライアント１３にて払い出されたデータＩＤを取得し、データ配置記憶部６４に登録する。例えば、図３に示すように、４つのデータユニット（データ内容）のそれぞれにデータＩＤが対応付けて記憶される。なお、データ内容は、ワークユニット部２５のタスク実行部７２が実行できる内容であれば、どのようなデータ内容でもよい。
【００７７】
そして、データ配置計画部６１は、データユニット配置計画処理を行う（ステップＳ３）。図２３を参照して、データユニット配置計画処理について説明する。図２３のデータユニット配置計画処理では、まず、データ配置計画部６１は、ワークユニットＩＤを縦軸、データＩＤを横軸としたデータの配置マトリクスを作成する（ステップＳ２１）。続いて、データ配置計画部６１は、ステップＳ２１の処理にて作成したデータ配置マトリクスの領域を理想データ配置可能領域と理想データ配置不可能領域とに分割する（ステップＳ２２）。
【００７８】
具体的には、データ配置計画部６１は、データ配置マトリクスのデータＩＤ列の領域を、データＩＤの若い順から、ワークユニット数ｗとデータユニットの冗長度数ｒの組合せ数（ｗＣｒ）毎に分割する。ここで、データ配置マトリクスの領域のうち、区切られた領域の列数がｗＣｒとなる領域を理想データ配置可能領域とし、区切られた領域の列数がｗＣｒより小さい値となる領域を理想データ配置不可能領域とする。例えば、ワークユニット数ｗが３であり、データユニットの冗長度数ｒが２であり、データユニット数ｄが４である場合、ワークユニット数ｗと冗長度数ｒの組合せ数は３Ｃ２＝３になる。このため、図４に示すように、データＩＤが１乃至３の列の領域が理想データ配置可能領域になり、図５に示すように、データＩＤが４の列の領域が理想データ配置不可能領域になる。
【００７９】
続いて、データ配置計画部６１は、ステップＳ２２の処理にて分割した理想データ配置可能領域を１つ取得する（ステップＳ２３）。図４の例では、データ配置可能領域は１つであるので、データＩＤ１乃至ＩＤ３の列の領域を示す理想データ配置可能領域を取得する。続いて、データ配置計画部６１は、ステップＳ２３の処理にて取得したデータ配置可能領域に対して、データ配置パターンを算出する（ステップＳ２４）。
【００８０】
具体的には、データ配置計画部６１は、全ワークユニットＩＤの中から事前に与えられたデータユニットの冗長度数ｒのワークユニットＩＤを選択する組合せであるデータ配置パターンを算出する。そして、全ての理想データ配置可能領域において、このワークユニットＩＤからデータユニットの冗長度数ｒを選ぶ組合せのパターンを全て均一に含むように、ワークユニットＩＤの組合せをデータＩＤに対して割り当てる。この条件を満たせば、どのワークユニットＩＤの組合せを、理想データ配置可能領域内のデータＩＤ列に配置してもよい。ここで計算された理想データ配置可能領域へのデータ配置パターンが複数存在する場合は、任意の一つを選ぶ（例えば図４）。
【００８１】
次に、データ配置計画部６１は、全ての理想データ配置可能領域を取得したか否かを判定する（ステップＳ２５）。全ての理想データ配置可能領域を取得していないと判定した場合、処理はステップＳ２３に戻り、それ以降の処理が繰り返される。一方、全ての理想データ配置可能領域を取得したと判定した場合、処理はステップＳ２６に進む。上述した図４の例では、理想データ配置可能領域は１つであるので処理はステップＳ２６に進む。
【００８２】
ステップＳ２６において、データ配置計画部６１は、理想データ配置不可能領域のデータ配置計画作成処理を行う。理想データ配置不可能領域のデータ配置計画作成処理について図２４を参照して説明する。
【００８３】
図２４のデータ配置計画作成処理では、まず、冗長度を満たす配置パターンを算出する（ステップＳ３１）。具体的には、まず、データ配置計画部６１は、ｗ個のワークユニットＩＤからｒ個のワークユニットＩＤを選択するワークユニットＩＤの組合せｗＣｒを算出する。そして、データ配置計画部６１は、理想データ配置不可能領域内のデータＩＤの列数（例えば１）だけ、そのワークユニットＩＤの組合せを配置する（割り当てる）データ配置パターンを算出する。図５の例では、データ配置計画部６１は、データ配置パターンとして、データＩＤが４の列に配置するワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を算出する。
【００８４】
続いて、データ配置計画部６１は、ステップＳ３１の処理にて算出したデータ配置パターンの中から、各ワークユニットＩＤに割り当てられるデータユニット数の標準偏差が最小になるデータ配置パターンを算出する（ステップＳ３２）。具体的には、算出したデータ配置パターンの中から、配置されたデータユニット数が最小になるワークユニットＩＤを含み、且つ、各ワークユニットＩＤに割り当てられるデータユニット数の標準偏差が最小になるデータ配置パターンを算出する。図５の例では、データ配置計画部６１は、データ配置パターンとして、ワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を算出する。
【００８５】
そして、データ配置計画部６１は、ステップＳ３２の処理にて算出したデータ配置パターンの中から、ミラーテーブル値の標準偏差が最小になるデータ配置パターンを選択する（ステップＳ３３）。ミラーテーブル値は、２つのワークユニットのそれぞれに割り当てられる同一のデータＩＤのデータユニットの個数である。
【００８６】
図５は、データ配置不可能領域（データＩＤが４の列）のデータ配置パターンとして、ワークユニットＩＤの組合せ（１，２）を選択した場合の例を示す図である。そして、図６に示すように、ワークユニットＩＤの組合せ（１，２）に対するミラーテーブル値は「２」になり、組合せ（２，３）に対するミラーテーブル値は「１」になり、組合せ（１，３）に対するミラーテーブル値は「１」になる。そして、例えば、データ配置計画部６１は、データ配置パターンとして、ワークユニットＩＤの組合せ（１，２），（２，３），（１，３）を選択する。
【００８７】
上記したように、ステップ３３の処理にて選択したデータ配置パターンが複数ある場合は、データ配置計画部６１は、その中から任意の一つを選び、選んだデータ配置パターンを理想データ配置不可能領域でのデータ配置パターンとする。例えば、データ配置計画部６１は、データＩＤが４の列に対して、ワークユニットＩＤの組合せ（１，２）を選択する。これにより、データ配置計画部６１は、データ配置マトリクス中の全ての領域について、データ配置計画の作成を完了し、処理は図２３のステップＳ２７に進む。
【００８８】
そして、図２３のステップＳ２７において、データ配置計画部６１は、データ配置マトリクスを記憶する（ステップＳ２７）。つまり、データ配置計画部６１は、図２３のステップＳ２４の処理にて算出した理想データ配置可能領域のデータ配置パターンと、図２４のステップＳ３３の処理にて算出した理想データ配置不可能領域のデータ配置パターンと、を１つのデータ配置マトリクスとして、データ配置記憶部６４に記憶する（例えば図７）。そして、ステップＳ２７の処理の後、処理は図２２のステップＳ４に進む。
【００８９】
そして、図２２のステップＳ４において、データ配置実行部６２は、ステップＳ２７の処理にて記憶されたデータ配置マトリクスに基づいて、各データユニットを出力する（ステップＳ４）。具体的には、まず、データ配置実行部６２は、データ配置マトリクスに基づいて、各ワークユニットＩＤに割り当てられたデータＩＤに対応するデータユニットを、マスタデータ記憶部６３に記憶されたマスタデータから取得する。そして、データ配置実行部６２は、取得したデータユニット（複製データユニット）と、当該複製データユニットに対応付けられたデータＩＤと、をワークユニットＩＤにて示されるワークユニット部２５へ出力する。そして、ワークユニット部２５は、データ配置管理部２４から出力されたデータＩＤと複製データユニットとを対応付けて、複製データ記憶部７３に記憶する。これにより、各ワークユニット部２５が、複製データ記憶部７３に記憶したデータユニットに対する所定の処理を実行することが可能になる。
【００９０】
次に、図２５を参照して、クライアントから投入されたジョブを実行する場合の処理について説明する。まず、タスク管理部２２のジョブ受信部４１は、ジョブクライアント１２から出力されたジョブを受信する（ステップＳ４１）。このジョブは、マスタデータに対する処理要求を表す。続いて、ジョブ受信部４１は、ステップＳ４１の処理にて受信したジョブを記憶する（ステップＳ４２）。具体的には、ジョブ受信部４１は、ジョブ毎にユニークなジョブＩＤと、ジョブ状態として「待機中」をジョブ記憶部４４に対応づけて記憶する（例えば図８）。
【００９１】
続いて、タスク生成部４２は、ステップＳ４１の処理にて受信したジョブに対応するタスクを生成する（ステップＳ４３）。具体的には、タスク生成部４２は、マスタデータ記憶部６３に記憶されたデータＩＤ（データユニット）の数のタスクを生成する。そして、タスク生成部４２は、ステップＳ４３の処理にて生成したタスクを記憶する（ステップＳ４４）。具体的には、タスク生成部４２は、生成したタスク毎に設定したユニークなタスクＩＤと、タスクの分割元となるジョブＩＤと、タスクが対象とするデータＩＤと、タスク状態として「待機中」と、を対応付けてタスク記憶部４５に記憶する（例えば図１４）。なお、タスクの対象となるデータＩＤは、タスク毎に異なるものでなければならない。ステップＳ４４の処理の後、処理は終了する。これにより、各データユニットに対するタスクを割り当てることができる。
【００９２】
次に、図２６乃至図２８を参照して、タスクを実行する場合の処理について説明する。ワークユニット群は複数のワークユニット部２５から構成され、それぞれのワークユニット部２５は独立して動くものとする。
【００９３】
まず、ワークユニット部２５は、複製データ記憶部７３に記憶されたデータＩＤ（データユニット）のリストを取得する（ステップＳ６１）。続いて、ワークユニット部２５は、タスク管理部２２に対してタスク要求を出力する（ステップＳ６２）。このタスク要求には、ステップＳ６１の処理にて取得したデータＩＤのリストが含まれる。
【００９４】
次に、タスクスケジュール部４３は、ワークユニット部２５から出力されたタスク要求を受信する（図２７のステップＳ７１）。続いて、タスクスケジュール部４３は、ステップＳ７１の処理にて受信したタスク要求に基づくタスクを取得する（ステップＳ７２）。具体的には、タスクスケジュール部４３は、タスクの状態が「待機中」であり、受信したタスク要求に含まれるデータＩＤのリストと合致するタスクＩＤ群をタスク記憶部４５から検索し、合致する全てのタスクまたは一部のタスク（タスク群）を取得する。
【００９５】
そして、タスクスケジュール部４３は、ステップＳ７２の処理にて取得したタスクに基づくタスク情報を出力する（ステップＳ７３）。具体的には、タスクスケジュール部４３は、まず、取得したタスクのそれぞれのタスク状態を「実行中」に変更する（例えば図１６）。また、タスクスケジュール部４３は、取得したタスクのそれぞれに対応付けて、タスク要求を出力したワークユニット部２５のワークユニットＩＤを記憶する。
【００９６】
次に、タスクスケジュール部４３は、取得したタスクのタスクＩＤに対応するジョブＩＤのリストを取得する。続いて、タスクスケジュール部４３は、ジョブ記憶部４４から該当のジョブＩＤに対応するジョブ内容を取得する。そして、タスクスケジュール部４３は、タスクＩＤと、当該タスクＩＤに対応するジョブＩＤと、当該タスクＩＤに対応するデータＩＤと、ジョブＩＤに対応するジョブの内容と、をタスク情報として、タスク要求を出力したワークユニット部２５に出力する。
【００９７】
次に、ワークユニット部２５のタスク要求部７１は、タスク情報を受信する（ステップＳ６３）。続いて、ワークユニット部２５のタスク要求部７１は、タスク情報にタスクが含まれているか否かを判定する（ステップＳ６３）。例えば受信したタスク情報にタスクが含まれていない場合（ステップＳ６３：Ｎｏ）、つまりワークユニット部２５が出力したタスク要求に対するタスクが存在しない（例えば他のワークユニット部２５が当該タスクを実行した）場合、処理はステップＳ６１に戻り、タスク要求部７１は、次のタスクの要求を行う。
【００９８】
一方、タスク情報にタスクが含まれている場合（ステップＳ６３：Ｙｅｓ）、タスク実行部７２は、タスクを実行する（ステップＳ６５）。例えば、タスク実行部７２は、タスク情報に含まれるデータＩＤをキーにして、複製データ記憶部７３からタスクの対象となるデータユニットのデータ内容を取得する。続いて、タスク実行部７２は、取得したデータ内容と、タスクＩＤに対応するジョブＩＤのジョブのジョブ内容と、に基づいて、タスクの処理を実行する。実行する内容については、ジョブ内容とデータ内容に対するどのような処理であってもよい。
【００９９】
そして、タスク実行部７２は、タスクの実行結果を出力する（ステップＳ６６）。具体的には、タスク実行部７２は、タスク要求のレスポンスに含まれる全てのタスク群の実行が完了したら、全てのタスクの実行結果として、タスクＩＤと、当該タスクＩＤに対応付けられたジョブＩＤと、タスクの処理結果としてのタスク結果と、からなるタスクの実行結果のリストを、タスク実行結果群として、タスク結果受信部５１に出力する。ステップＳ６６の処理の後、処理はステップＳ６２に戻る。つまり、タスク要求部７１は、新たなタスク要求を出力する。
【０１００】
次に、図２８を参照して、タスクの実行結果を受信するタスク集約部２３の処理について説明する。まず、タスク結果受信部５１は、図２６のステップＳ６６の処理にて出力されたタスクの実行結果を受信する（ステップＳ８１）。続いて、タスク結果受信部５１は、受信したタスク実行結果のリストをタスク毎にタスク記憶部４５に記憶する（ステップＳ８２）。具体的には、タスク実行結果に含まれるタスクＩＤをキーにして、タスク記憶部４５から該当するレコードを探し、タスク実行結果であるタスク結果と、タスク状態として完了状態である「完了」と、をタスク記憶部４５に記憶する。
【０１０１】
次に、ジョブ結果出力部５２は、完了したジョブを取得する（ステップＳ８３）。例えば、ジョブ結果出力部５２は、ジョブＩＤ毎にそのジョブＩＤに対応付けられたタスク群の状態が「完了」になっているものを取得する。続いて、ジョブ結果出力部５２は、ジョブ結果を生成する（ステップＳ８４）。例えば、ジョブ結果出力部５２は、タスク記憶部４５から、ジョブＩＤに対応付けられたタスク結果に対して集計処理を行い、ジョブ結果を生成する。なお、集計処理はタスク結果に対するどのような処理でも良く、それにより生成されるジョブ結果もどのようなものでもよい。そして、ジョブ結果出力部５２は、完了したジョブのジョブ結果をジョブクライアント１２に出力する（ステップＳ８５）。またこのとき、ジョブ結果出力部５２は、ジョブ記憶部４４の該当するジョブＩＤのジョブの状態を完了状態である「完了」に変更する（例えば図１８）。
【０１０２】
このように、本実施の形態では、データユニットの冗長度が等しくなるように、ワークユニット部２５にデータユニットが配置されている。そして、ワークユニット部２５が保持するデータユニット数の標準偏差が最小となるようにワークユニット部２５に均一のデータユニット数が配置される。さらに、ワークユニット部２５間で同一の複製データユニットを保持する個数の標準偏差が小さくなるような配置になるデータ配置パターンを作成する。このような、データ配置パターンを作成することによりシステムの冗長性の維持とワークユニット部２５の負荷分散が可能になる。
【０１０３】
さらに、データユニットが配置されたワークユニット部２５は、自身が保持するデータＩＤのリストをタスクスケジュール部４３に出力し、タスクスケジュール部４３は処理対象であるデータユニットの識別子が合致するタスク群の中から、他のワークユニット部２５が既に取得していないタスクを返す。このため、タスクスケジュール部４３は、ワークユニット部２５で必要なタスクでかつ他のワークユニット部２５で実行されていないタスク群だけを出力するため、データユニットが冗長配置されていても同じデータユニットに対するタスクを重複して処理することがない。このように構成されているため、異なるワークユニット部２５で同時に複数の異なるタスク群を分散して実行できるため、システムの冗長度を保ちながら、ジョブが完了するまでの時間を短くすることができる。
【０１０４】
また、本実施の形態では、データ配置パターンにより、ワークユニット部２５毎のデータ配置数の標準偏差が最小になることから、ワークユニット部２５で同時に処理が可能な最大タスク数については、ワークユニット部２５間で平準化されるため、ワークユニット部２５の処理量は均一になりやすい。さらに、ワークユニット部２５間で同一のデータユニットの保持個数の標準偏差が小さくなるように配置計画をしていることから、あるワークユニット部２５において、あるデータユニットを対象にしたタスクのタスク実行時間が長くなっている場合でも、その遅いタスクを実行しているワークユニット部２５が保持するデータユニット群と同じ複製データユニットを保持する他のワークユニット部２５が、その遅いタスクを実行しているワークユニット部２５が保持する他のデータＩＤに対応付けられたタスクを実行することができる。従って、データ配置的にワークユニット部２５間で負荷のロードバランスができる。
【０１０５】
それに加えて、複製データユニットを配置されたワークユニット部２５が、自身が保持するデータＩＤのリストをタスクスケジュール部４３に出力することでタスクを取得し、取得したタスク群が終わったら次のタスクを取得しに行くというプル型のタスク取得をしていることから、このデータ配置方法と組合せることで、ワークユニット部２５間でタスクの処理の負荷のロードバランスが可能である。従って、このようなデータ配置とタスクの取得方法の方式であり、ワークユニット部２５間でタスクの処理のロードバランスが可能となり、ジョブ数が有限の場合に全てのジョブが完了するまでの時間が短くなり、複数のジョブが存在する場合にジョブのスループットを向上することができる。
【０１０６】
また、本実施の形態では、データ配置計画部６１のデータユニットを分散配置するアルゴリズムが、データユニットの冗長性を満たすこと、ワークユニット部２５が保持するデータユニットの個数の標準偏差が最小となること、ワークユニット部２５間で同一のデータユニットを保持する個数の合計値が最小となることの組合せを満たすようにデータ配置を行い、必要最低限のデータ数で冗長度を満たしながら負荷のバランスが行えるデータ配置を行っているため、少ない外部記憶またはメモリで分散データを保持することが可能になっていることができる。この結果、少ないワークユニット部２５のサーバ台数で、データユニットを分散配置することが可能である。
【０１０７】
また、本実施の形態では、このようなデータ配置に基づき、ワークユニット部２５がプル型でタスクを取得する方式であるため、システム負荷を監視して統計情報により負荷を計算するわけではなく、ワークユニット部２５にシステム負荷の監視させることによりワークユニット部２５に負荷を与えることなく、ワークユニット部２５のタスクの負荷を分散することができる。
【０１０８】
＜第２実施形態＞
次に、本発明の第２実施形態に係る分散処理システムについて図２９を参照して説明する。
第２実施形態に係る分散処理システム２０１は、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部２１２へ出力するデータユニット出力制御部２１１（データユニット出力制御手段）を備え、
データユニット出力制御部２１１は、同一の複数の複製データユニットの出力先をそれぞれ異なるデータユニット処理部２１２に割り当てるとともに、
予め設定された少なくとも２つのデータユニット処理部２１２の組合せ毎に、当該組合せられた各データユニット処理部２１２に同一の複製データユニットが割り当てられた当該同一の複製データユニット群の数を取得し、データユニット処理部２１２の組合せ毎に取得した複製データユニット群の数のばらつき度合いが小さくなるように、複数の複製データユニットの出力先を各データユニット処理部２１２のそれぞれに割り当てる。
【０１０９】
上記構成によれば、データユニット出力制御部２１１は、複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部２１２へ出力する場合に、例えばデータユニットの識別情報が同じ複数の複製データユニットのそれぞれを異なるデータユニット処理部２１２に割り当てる。また、予め設定された少なくとも２つのデータユニット処理部２１２の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた当該同一の複製データユニット群の数（ミラーテーブル値）を取得し、データユニット処理部２１２の組合せ毎に取得したミラーテーブル値のばらつき度合いが小さくなるように、複数の複製データユニットの出力先を各データユニット処理部２１２のそれぞれに割り当てる。このため、同一のデータユニットの複製を保持するデータユニット処理部２１２が１つのデータユニット処理部２１２に集中することなく分散して割り当てられる。従って、所定のデータユニット処理部に障害等が発生した場合でも、障害等が発生したデータユニット処理部２１２が保持する複製データユニットと同一の複製データユニットを保持するデータユニット処理部のそれぞれが、代わりに複製データユニットに対する所定の処理を行うことができる。この結果、全てのデータユニットに対する処理を迅速に行い、スループットを向上させることができる。
【０１１０】
以上、上記実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成及び詳細に、本願発明の範囲内において当業者が理解し得る様々な変更をすることができる。
【０１１１】
＜付記＞
上記実施形態の一部又は全部は、以下の付記のように記載され得るが、以下には限られない。
【０１１２】
（付記１）
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を備え、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【０１１３】
上記構成によれば、データユニット出力制御手段は、複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力する場合に、例えばデータユニットの識別情報が同じ複数の複製データユニットのそれぞれを異なるデータユニット処理部に割り当てる。また、予め設定された少なくとも２つのデータユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数（ミラーテーブル値）を取得し、データユニット処理部の組合せ毎に取得したミラーテーブル値のばらつき度合いが小さくなるように、複数の複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる。このため、同一のデータユニットの複製を保持するデータユニット処理部が１つのデータユニット処理部に集中することなく分散して割り当てられる。従って、所定のデータユニット処理部に障害等が発生した場合でも、障害等が発生したデータユニット処理部が保持する複製データユニットと同一の複製データユニットを保持するデータユニット処理部のそれぞれが、代わりに複製データユニットに対する所定の処理を行うことができる。この結果、全てのデータユニットに対する処理を迅速に行い、スループットを向上させることができる。
【０１１４】
（付記２）
付記１に記載の情報処理装置であって、
前記データユニット出力制御手段は、さらに、前記データユニット処理部毎に割り当てる前記複製データユニットの数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【０１１５】
上記構成によれば、データユニット出力制御手段は、データユニット処理部毎に割り当てる複製データユニットの数のばらつき度合いが小さくなるように、複数の複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる。このため、１つのデータユニット処理部に複製データユニットが集中して出力されることがなく、複数のデータユニット処理部のそれぞれに複製データユニットが分散して出力される。この結果、所定のデータユニット処理部に障害等が発生した場合でも、他のデータユニット処理部が代わりに所定の処理を行うことができる。この結果、全てのデータユニットに対する処理をより迅速に行い、スループットを向上させることができる。
【０１１６】
（付記３）
付記１または２に記載の情報処理装置であって、
前記データユニット出力制御手段は、前記データユニット処理部の組合せ毎に取得した、同一の複製データユニットが割り当てられた前記複製データユニット群の数の所定の基準値に対するばらつき度合いを算出し、算出した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【０１１７】
上記構成によれば、データユニット出力制御手段は、データユニット処理部の組合せ毎のミラーテーブル値の所定の基準値に対するばらつき度合い（例えば標準偏差）を算出する。そして、算出した標準偏差が小さくなるように、複数の複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる。このように、同一の複製データユニットの数のばらつき度合いを小さくすることで、データユニット処理部の組合せ毎の同一の複製データユニットの数を平準化にすることができる。この結果、複数の複製データユニットのそれぞれを、より迅速かつ確実に複数のデータユニット処理部に分散することができる。
【０１１８】
（付記４）
付記１乃至３のいずれかに記載の情報処理装置であって、
前記データユニット出力制御手段は、前記データユニット処理部の組合せ毎に取得した、同一の複製データユニットが割り当てられた前記複製データユニット群の数のばらつき度合いが小さくなり、且つ、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数の総和が最小になるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理装置。
【０１１９】
上記構成によれば、データユニット出力制御手段は、データユニット処理部の組合せ毎に取得したミラーテーブル値のばらつき度合いが小さくなり、且つ、データユニット処理部の組合せ毎に取得したミラーテーブル値の総和が最小になるように、複数の複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる。このように、複製データユニット群の数のばらつき度合いが同じになるデータユニットの割り当てパターンが存在する場合に、データユニット処理部の組合せに対して、重複するデータユニット（複製データユニット）の数を小さくすることができる。このため、データユニットに対する処理要求が１つのデータユニット処理部に集中して出力されることがなく、複数のデータユニット処理部のそれぞれに複製データユニットが分散して出力される。この結果、全てのデータユニットに対する処理をより迅速に行い、スループットを向上させることができる。
【０１２０】
（付記５）
付記１乃至４のいずれかに記載の情報処理装置であって、
前記データユニット出力制御手段は、出力先としての前記データユニット処理部と、当該データユニット処理部へ割り当てた前記複製データユニットと、を対応付けたデータユニット出力表を生成し、生成した前記データユニット出力表に基づいて、複数の前記複製データユニットを複数の前記データユニット処理部へ出力する、
情報処理装置。
【０１２１】
上記構成によれば、データユニット出力制御手段は、複製データユニットとデータユニット処理部とを割り当てるために、データユニット処理部と、当該データユニット処理部へ出力するデータユニットと、を対応付けたデータユニット出力表（例えばデータ配置マトリクス）を生成する。このため、複製データユニットの管理、制御が容易になり、より迅速かつ確実に複製データユニットをデータユニット処理部へ出力することができる。
【０１２２】
（付記６）
付記１乃至５のいずれかに記載の情報処理装置であって、
複数の前記データユニットに対する処理要求を取得し、取得した処理要求を前記各データユニットに対応付けて分割した分割処理要求を生成し、前記データユニット処理部から、当該データユニット処理部に割り当てられた前記複製データユニットを特定する特定情報を取得した場合に、取得した当該特定情報にて特定される前記複製データユニットに対応する前記分割処理要求を、前記データユニット処理部へ出力する処理要求制御手段、
を備える情報処理装置。
【０１２３】
上記構成によれば、処理要求制御手段は、複数のデータユニットに対する処理要求（例えばジョブ）を取得し、取得した処理要求をデータユニットに対応付けて分割した分割処理要求（データユニット毎のタスク）を生成する。そして、データユニット処理部から、当該データユニット処理部に割り当てられた複製データユニットの特定情報を取得した場合に、データユニット処理部に割り当てられた複製データユニットに対応付けられたタスクを取得し、当該タスクをデータユニット処理部へ出力する。このため、例えば大規模データに対する処理要求（ジョブ）を効率的に分割し、各データユニット処理部へ出力することができる。この結果、大規模データに対する処理を迅速に行い、スループットを向上させることができる。
【０１２４】
（付記７）
付記６に記載の情報処理装置であって、
前記処理要求制御手段は、取得した前記特定情報にて特定される前記複製データユニットに対応する前記分割処理要求のうち、他のデータユニット処理部へ出力していない前記分割処理要求であり、且つ、各データユニット処理部に割り当てられた前記複製データユニットの総和を算出し、算出した当該総和を前記データユニット処理部の数で割った平均値以下の数の前記分割処理要求を、前記データユニット処理部へ出力する、
情報処理装置。
【０１２５】
上記構成によれば、処理要求制御手段は、他のデータユニット処理部へ出力していない分割処理要求であり、且つ、各データユニット処理部に割り当てられた複製データユニットの総和を算出し、算出した当該総和を前記データユニット処理部の数で割った平均値以下の数の分割処理要求を、データユニット処理部へ出力する。このため、データユニット処理部が一度に扱う複製データユニットの数が少なくなるので、他のデータユニット処理部へ出力していない分割処理要求の数が増加する。従って、所定のデータユニット処理部が保持するデータユニットに対する分割処理要求の全てが、他のデータユニット処理部に出力される可能性が小さくなり、分割処理要求に対する処理を行うことができないデータユニット処理部の数が減少する。この結果、全ての分割処理要求（データユニット）に対する処理を迅速に行い、スループットを向上させることができる。
【０１２６】
（付記８）
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力する場合に、
同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、
予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理方法。
【０１２７】
（付記９）
付記８に記載の情報処理方法であって、
前記データユニット処理部毎に割り当てる前記複製データユニットの数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
情報処理方法。
【０１２８】
（付記１０）
情報処理装置に、
複数のデータユニットのそれぞれを予め設定された数ずつ複製した各複製データユニットを、複数のデータユニット処理部へ出力するデータユニット出力制御手段を実現させるとともに、
前記データユニット出力制御手段は、同一の複数の前記複製データユニットの出力先をそれぞれ異なる前記データユニット処理部に割り当てるとともに、予め設定された少なくとも２つの前記データユニット処理部の組合せ毎に、当該組合せられた各データユニット処理部に同一の複製データユニットが割り当てられた複製データユニット群の数を取得し、前記データユニット処理部の組合せ毎に取得した前記複製データユニット群の数のばらつき度合いが小さくなるように、複数の前記複製データユニットの出力先を各データユニット処理部のそれぞれに割り当てる、
ことを実現させるためのプログラム。
【０１２９】
なお、上記各実施形態及び付記において記載したプログラムは、記憶装置に記憶されていたり、コンピュータが読み取り可能な記録媒体に記録されている。例えば、記録媒体は、フレキシブルディスク、光ディスク、光磁気ディスク、及び、半導体メモリ等の可搬性を有する媒体である。
【０１３０】
以上、上記各実施形態を参照して本願発明を説明したが、本願発明は、上述した実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明の範囲内で当業者が理解しうる様々な変更をすることができる。
【０１３１】
なお、本発明は、日本国にて２０１３年２月１５日に特許出願された特願２０１３−０２７３１２の特許出願に基づく優先権主張の利益を享受するものであり、当該特許出願に記載された内容は、全て本明細書に含まれるものとする。
【符号の説明】
【０１３２】
１      分散処理システム
１１    情報処理装置
１２    ジョブクライアント
１３    システム管理クライアント
２１    ワークユニット管理部
２２    タスク管理部
２３    タスク集約部
２４    データ配置管理部
２５    ワークユニット部
３１    ワークユニット記憶部
４１    ジョブ受信部
４２    タスク生成部
４３    タスクスケジュール部
４４    ジョブ記憶部
４５    タスク記憶部
５１    タスク結果受信部
５２    ジョブ結果出力部
６１    データ配置計画部
６２    データ配置実行部
６３    マスタデータ記憶部
６４    データ配置記憶部
７１    タスク要求部
７２    タスク実行部
７３    複製データ記憶部
２０１  分散処理システム
２１１  データユニット出力制御部
２１２  データユニット処理部
【図１】
2014125543.tif 000003
【図２】
2014125543.tif 000004
【図３】
2014125543.tif 000005
【図４】
2014125543.tif 000006
【図５】
2014125543.tif 000007
【図６】
2014125543.tif 000008
【図７】
2014125543.tif 000009
【図８】
2014125543.tif 000010
【図９】
2014125543.tif 000011
【図１０】
2014125543.tif 000012
【図１１】
2014125543.tif 000013
【図１２】
2014125543.tif 000014
【図１３】
2014125543.tif 000015
【図１４】
2014125543.tif 000016
【図１５】
2014125543.tif 000017
【図１６】
2014125543.tif 000018
【図１７】
2014125543.tif 000019
【図１８】
2014125543.tif 000020
【図１９】
2014125543.tif 000021
【図２０】
2014125543.tif 000022
【図２１】
2014125543.tif 000023
【図２２】
2014125543.tif 000024
【図２３】
2014125543.tif 000025
【図２４】
2014125543.tif 000026
【図２５】
2014125543.tif 000027
【図２６】
2014125543.tif 000028
【図２７】
2014125543.tif 000029
【図２８】
2014125543.tif 000030
【図２９】
2014125543.tif 000031
【国際調査報告】
2014125543.tif 000032
2014125543.tif 000033