(57)【要約】【課題】ＭａｐＲｅｄｕｃｅを実行する分散データ処理において、計算機資源を効率よく使うこと。【解決手段】ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置１０は、所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する。そして、分散データ処理装置１０は、計算された各データの処理負荷を用いて、Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する。【選択図】図１
2015191428.tif 000002
【特許請求の範囲】
【請求項１】
ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置であって、
所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する計算部と、
前記計算部によって計算された各データの処理負荷を用いて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する決定部と、
を有することを特徴とする分散データ処理装置。
【請求項２】
前記計算部は、前記処理負荷として、前記各データについて、入力キーに対応するバリューの数を示す頻度情報を計算することを特徴とする請求項１に記載の分散データ処理装置。
【請求項３】
ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置であって、
入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算する計算部と、
前記計算部によって計算された比率に応じて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、前記Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する決定部と、
を有することを特徴とする分散データ処理装置。
【請求項４】
前記計算部は、ＭａｐＲｅｄｕｃｅを実行した過去の入力データあるいは新たに入力されるデータから一部のデータをサンプルデータとして抽出し、該サンプルデータに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散されたサンプルデータに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算することを特徴とする請求項３に記載の分散データ処理装置。
【請求項５】
ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置で実行される分散データ処理方法であって、
所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する計算ステップと、
前記計算ステップによって計算された各データの処理負荷を用いて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する決定ステップと、
を含んだことを特徴とする分散データ処理方法。
【請求項６】
ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置で実行される分散データ処理方法であって、
入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算する計算ステップと、
前記計算ステップによって計算された比率に応じて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、前記Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する決定ステップと、
を含んだことを特徴とする分散データ処理方法。
【請求項７】
所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する計算ステップと、
前記計算ステップによって計算された各データの処理負荷を用いて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する決定ステップと、
をコンピュータに実行させるための分散データ処理プログラム。
【請求項８】
入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算する計算ステップと、
前記計算ステップによって計算された比率に応じて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、前記Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する決定ステップと、
をコンピュータに実行させるための分散データ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データ処理装置、分散データ処理方法及び分散データ処理プログラムに関する。
【背景技術】
【０００２】
従来、大規模なデータを処理するデータ処理が行われている。例えば、大規模なデータを複数の物理マシンで分散して並列処理を行うＭａｐＲｅｄｕｃｅと呼ばれる技術がある。このＭａｐＲｅｄｕｃｅでは、まず、大規模な入力データを複数の物理マシンに分散し、分散された入力データから必要なデータを抽出するＭａｐ処理を各物理マシンで行う。そして、ＭａｐＲｅｄｕｃｅでは、各物理マシンにおいて抽出されたデータを一部の物理マシンに集約して統合するＲｅｄｕｃｅ処理を行うことで、大規模な入力データに対する処理結果を取得する。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Yanpei  Chen，Sara  Alspaugh，Dhruba  Borthakur，Randy  Katz著，「Energy  Efficiency  for  Large-Scale  MapReduce  Workloads  with  Significant  Interactive  Analysis」，EuroSys'12  P43-P56
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかし、従来のＭａｐＲｅｄｕｃｅを実行する分散データ処理において、計算機資源を効率よく使うことができず、効率的にプログラムを実行することができない場合があるという課題があった。例えば、従来のＭａｐＲｅｄｕｃｅでは、Ｒｅｄｕｃｅ関数を実行する各プロセスは、データ量を勘案せずに各々処理を実行していたため、負荷が偏るという問題があった。また、例えば、Ｍａｐ関数を実行するコストとＲｅｄｕｃｅ関数を実行するコスト差を勘案せずに処理を実行していたため、Ｍａｐ関数やＲｅｄｕｃｅ関数を実行するマシンの処理能力を十分に使いきれていないという問題があった。
【課題を解決するための手段】
【０００５】
上述した課題を解決し、目的を達成するために、本発明は、ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置であって、所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する計算部と、前記計算部によって計算された各データの処理負荷を用いて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する決定部と、を有することを特徴とする。
【０００６】
また、本発明は、ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置であって、入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算する計算部と、前記計算部によって計算された比率に応じて、前記Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、前記Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する決定部と、を有することを特徴とする。
【発明の効果】
【０００７】
本発明によれば、ＭａｐＲｅｄｕｃｅを実行する分散データ処理において、計算機資源を効率よく使うことが可能である。
【図面の簡単な説明】
【０００８】
【図１】図１は、第一の実施の形態に係る分散データ処理装置の構成を示すブロック図である。
【図２】図２は、キー・バリューの組みの集合から計算されるヒストグラムのデータの一例を示す図である。
【図３】図３は、Ｒｅｄｕｃｅプロセスに割り当てる処理を説明する図である。
【図４】図４は、Ｒｅｄｕｃｅキー区間からＲｅｄｕｃｅプロセスへの対応関係を示す図である。
【図５】図５は、第一の実施の形態に係る分散データ処理装置における全体の処理の流れを示す図である。
【図６】図６は、第一の実施の形態に係る分散データ処理装置による頻度情報計算処理の流れを示すフローチャートである。
【図７】図７は、第一の実施の形態に係る分散データ処理装置によるＲｅｄｕｃｅ負荷平準化処理の流れを示すフローチャートである。
【図８】図８は、第一の実施の形態に係る分散データ処理装置によるＭａｐＲｅｄｕｃｅ間コスト比計算処理の流れを示すフローチャートである。
【図９】図９は、第一の実施の形態に係る分散データ処理装置によるＭａｐＲｅｄｕｃｅ負荷平準化処理の流れを示すフローチャートである。
【図１０】図１０は、分散データ処理プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明を実施するための形態（実施の形態）を説明する。なお、この実施の形態により本発明が限定されるものではない。
【００１０】
［第一の実施の形態］
以下の実施の形態では、第一の実施の形態に係る分散データ処理装置の構成および処理の流れを順に説明し、最後に第一の実施の形態による効果を説明する。
【００１１】
［分散データ処理装置の構成］
次に、図１を用いて、分散データ処理装置の構成を説明する。図１は、第一の実施の形態に係る分散データ処理装置の構成を示すブロック図である。分散データ処理装置１０は、ＭａｐＲｅｄｕｃｅにより分散されたデータを処理する。図１に示すように、この分散データ処理装置１０は、入出力部１１、制御部１２、記憶部１３を有する。以下にこれらの各部の処理を説明する。
【００１２】
入出力部１１は、各種情報の入出力を司る入出力インタフェースである。この入出力部１１は、例えば、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たな入力データを入力したり、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たな入力データを入力したり、入力データに対してデータ処理が行われた処理結果を出力したりする。
【００１３】
制御部１２は、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行するが、特に本発明に密接に関連するものとしては、Ｒｅｄｕｃｅ計算部１２ａ、ＭａｐＲｅｄｕｃｅ計算部１２ｂ、Ｒｅｄｕｃｅ決定部１２ｃ、ＭａｐＲｅｄｕｃｅ決定部１２ｄおよびＭａｐＲｅｄｕｃｅ実行部１２ｅを有する。
【００１４】
Ｒｅｄｕｃｅ計算部１２ａは、所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する。
【００１５】
具体的には、Ｒｅｄｕｃｅ計算部１２ａは、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータを入力として、ＭａｐＲｅｄｕｃｅプログラムを実行してＲｅｄｕｃｅ関数の入力キーの頻度情報を計算し、頻度情報を統計情報として統計情報記憶部１３ａに記録する。
【００１６】
例えば、Ｒｅｄｕｃｅ計算部１２ａは、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータからサンプリングを行い、サンプルデータを入力データとして、入力キーの頻度情報を計算してもよい。このように、サンプリングを行うことで、処理コストを削減することができる。
【００１７】
ここで、Ｒｅｄｕｃｅ関数の入力キーの頻度情報の計算処理について、具体例を挙げながら具体的に説明する。Ｒｅｄｕｃｅ計算部１２ａは、入力データに対してＭａｐ関数を実際に実行して、出力されるキー・バリューの組みの集合からキー値に関するヒストグラムなどの頻度分布を計算して、統計情報記憶部１３ａに記録する。
【００１８】
例えば、文書群を入力として転置インデックスを構築するＭａｐＲｅｄｕｃｅプログラムを考えた場合に、図２に例示するように、キーが単語でバリューがその単語を含む文書ＩＤを出力するようにＭａｐ関数が実装され、この場合のヒストグラムを得ることができる。なお、図２の例では、区間の粒度を簡易に決定しているが、区間の粒度は細かいほど負荷分散を正確に実施することができるため、区間の粒度は細かい方が望ましい。
【００１９】
ＭａｐＲｅｄｕｃｅ計算部１２ｂは、入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算する。
【００２０】
具体的には、ＭａｐＲｅｄｕｃｅ計算部１２ｂは、Ｍａｐ関数を実行する全プロセスの実行コストとＲｅｄｕｃｅ関数を実行する全プロセスの実行コストの比率を計算するため、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータを入力として、Ｍａｐ関数を実行する全プロセスの実行コストとＲｅｄｕｃｅ関数を実行する全プロセスの実行コストを取得し、これらのコスト比を計算する。
【００２１】
ＭａｐＲｅｄｕｃｅ計算部１２ｂは、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータからサンプリングを行い、サンプルデータを入力データとして、入力キーの頻度情報を計算してもよい。このように、サンプリングを行うことで、処理コストを削減することができる。
【００２２】
ＭａｐＲｅｄｕｃｅ計算部１２ｂは、入力データに対してＭａｐ関数とＲｅｄｕｃｅ関数を実際に実行して、Ｍａｐ関数を実行するプロセスの実行コストとＲｅｄｕｃｅ関数を実行するプロセスの実行コストを計測し、これらの実行コストの比を計算して統計情報記憶部１３ａに書き込む。例えば、ＭａｐＲｅｄｕｃｅ計算部１２ｂは、Ｍａｐ関数を実行するプロセス数が５で実行時間が２０分であり、Ｒｅｄｕｃｅ関数を実行するプロセス数が３で実行時間が６０分ならば、ｍａｐ／ｒｅｄｕｃｅの比は「５×２０／３×６０＝５／９」となる。
【００２３】
Ｒｅｄｕｃｅ決定部１２ｃは、Ｒｅｄｕｃｅ計算部１２ａによって計算された各データの処理負荷を用いて、Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する。
【００２４】
具体的には、Ｒｅｄｕｃｅ決定部１２ｃは、Ｒｅｄｕｃｅ計算部１２ａにより得られた入力キーの頻度情報を利用して、Ｒｅｄｕｃｅ関数を実行する全プロセスの実行時間が平準化されるようにＲｅｄｕｃｅプロセスへのデータの割り当ての関数を決定し、Ｍａｐ関数を実行する全マシンに割り当て関数を配布する。ただし、ＲｅｄｕｃｅプロセスとはＲｅｄｕｃｅ関数を実行するプロセスのことを指し、同様にＭａｐプロセスとはＭａｐ関数を実行するプロセスのことを指す。
【００２５】
このように、Ｒｅｄｕｃｅ決定部１２ｃは、Ｒｅｄｕｃｅ関数を実行するマシンにＭａｐ関数の実行結果を配布（シャッフル）する際に先に配布した割り当て関数を用いることで、Ｒｅｄｕｃｅ関数を実行する全プロセスの実行時間を平準化する。
【００２６】
ここで、Ｒｅｄｕｃｅ関数を実行する各プロセスにデータを割り当てる処理について、具体例を挙げながら具体的に説明する。まず、Ｒｅｄｕｃｅ決定部１２ｃは、統計情報記憶部１３ａからキーの頻度情報を読み込む。そして、Ｒｅｄｕｃｅ決定部１２ｃは、キー値に関するヒストグラムなどの頻度分布と、ＭａｐＲｅｄｕｃｅプログラムで指定されたＲｅｄｕｃｅプロセス数を入力として、ヒストグラムの分布を示すキー・バリューのデータが均等にＲｅｄｕｃｅプロセスに分割されるように入力データを割り当てるｐａｒｔｉｔｉｏｎ関数を導出する。
【００２７】
例えば、転置インデックスを構築する例では、頻度の大きいヒストグラムの区間順にＲｅｄｕｃｅプロセスの割り当てを行い、割り当てるＲｅｄｕｃｅプロセスは既に割り当て済みの頻度の総和が最小となるＲｅｄｕｃｅプロセスを選択するなどの方法によって、負荷の平準化を実現する。上述の１６の区間を３つのＲｅｄｕｃｅプロセスに割り当てる場合には、最初は３つの最大頻度の区間が全Ｒｅｄｕｃｅプロセスに割り当てる。例えば、図３の（１）に例示するように、Ｒｅｄｕｃｅプロセス「Ｒｅｄｕｃｅ１」に、区間１６（５−９から始まる単語、８００）を割り当て、Ｒｅｄｕｃｅプロセス「Ｒｅｄｕｃｅ２」に、区間１５（３−４から始まる単語、６００）を割り当て、Ｒｅｄｕｃｅプロセス「Ｒｅｄｕｃｅ３」に、区間１４（０−２から始まる単語、５００）を割り当てる。
【００２８】
次に、例えば、図３の（２）に例示するように、割り当て済みの頻度の総和が最小である「Ｒｅｄｕｃｅ３」に対して、残りで最大頻度である区間２（ｅ−ｇから始まる単語、２００）が割り当てられる。そして、例えば、図３の（３）に例示するように、割り当て済みの頻度の総和が最小である「Ｒｅｄｕｃｅ２」に対して、残りで最大頻度である区間１（ａ−ｄから始まる単語、１２０）が割り当てられ、最後の区間割り当てが完了するまで処理を継続する。
【００２９】
こうして得られるＲｅｄｕｃｅのキー区間からＲｅｄｕｃｅプロセスへの対応関係を関数として表現してＭａｐＲｅｄｕｃｅ実行部１２ｅに出力する。例えば、上記の例では、Ｒｅｄｕｃｅのキー区間からＲｅｄｕｃｅプロセスへの対応関係は、図４に例示するような対応関係になる。この関数は、キー区間を入力とし、キー区間に対応するＲｅｄｕｃｅプロセス番号を出力するものである。
【００３０】
ＭａｐＲｅｄｕｃｅ決定部１２ｄは、ＭａｐＲｅｄｕｃｅ計算部１２ｂによって計算された比率に応じて、Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する。
【００３１】
具体的には、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、ＭａｐＲｅｄｕｃｅ計算部１２ｂにより計算されたコスト比に応じてＭａｐ関数を実行する全プロセスの実行コストとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間が平準化されるように、Ｍａｐ関数を実行するプロセス数とＲｅｄｕｃｅ関数を実行するプロセス数を決定する。なお、総プロセス数は、利用可能なＣＰＵ数などにより決定する。
【００３２】
例えば、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、統計情報記憶部１３ａからＭａｐＲｅｄｕｃｅ間コスト比を読み込む。そして、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、Ｍａｐ関数を実行する全プロセスとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間が平準化されるように、Ｍａｐプロセス数とＲｅｄｕｃｅプロセス数を決定する。
【００３３】
具体的な例を挙げて説明すると、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、ｍａｐ／ｒｅｄｕｃｅの比が５／９である場合には、Ｎを整数としてｍａｐプロセス数を５Ｎ、ｒｅｄｕｃｅプロセス数を９Ｎと決定することで、Ｍａｐ関数を実行する全プロセスとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間を平準化することができる。こうして得られるｍａｐプロセス数とｒｅｄｕｃｅプロセス数をＭａｐＲｅｄｕｃｅ実行部１２ｅに出力する。
【００３４】
このように、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、ＭａｐＲｅｄｕｃｅ計算部１２ｂにより計算されたコスト比を用いて、Ｍａｐ関数を実行する全プロセスの実行コストとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間が平準化されるように、Ｍａｐ関数を実行するプロセス数とＲｅｄｕｃｅ関数を実行するプロセス数を決定することで、Ｍａｐ関数を実行する全プロセスとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間を平準化する。
【００３５】
ＭａｐＲｅｄｕｃｅ実行部１２ｅは、Ｒｅｄｕｃｅ決定部１２ｃにより決定されたデータ割り当て関数をＭａｐ関数を実行する全プロセスに配布し、ＭａｐＲｅｄｕｃｅ決定部１２ｄにより決定されたＭａｐ関数を実行するプロセス数とＲｅｄｕｃｅ関数を実行するプロセス数に従って、これらのプロセスを起動する。その後、処理対象となるデータ記憶部１３ｂからデータを読み込み、ＭａｐＲｅｄｕｃｅ処理を実行する。
【００３６】
また、記憶部１３は、制御部１２による各種処理に必要なデータおよびプログラムを格納するが、特に本発明に密接に関連するものとしては、統計情報記憶部１３ａおよび複数のデータ記憶部１３ｂを有する。例えば、記憶部１３は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、又は、ハードディスク、光ディスク等の記憶装置などである。
【００３７】
統計情報記憶部１３ａは、統計情報として、Ｒｅｄｕｃｅ計算部１２ａによって計算されたＲｅｄｕｃｅ関数を実行する入力キーの頻度情報を記憶する。また、統計情報記憶部１３ａは、ＭａｐＲｅｄｕｃｅ計算部１２ｂによって計算されたＭａｐ関数を実行するプロセスの実行コストとＲｅｄｕｃｅ関数を実行するプロセスの実行コストとの比率を記憶する。
【００３８】
複数のデータ記憶部１３ｂは、ＭａｐＲｅｄｕｃｅの処理対象となる入力データを記憶している。例えば、複数のデータ記憶部１３ｂは、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータ、および、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータを記憶する。
【００３９】
ここで、図５を用いて、分散データ処理装置１０における全体の処理の流れの一例を説明する。図５は、第一の実施の形態に係る分散データ処理装置における全体の処理の流れを示す図である。図５に示すように、分散データ処理装置１０のＲｅｄｕｃｅ計算部１２ａは、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータを入力として、Ｒｅｄｕｃｅ関数を実行する入力キーの頻度情報を計算して、統計情報として統計情報記憶部１３ａに記録する（ステップＳ１１）。
【００４０】
そして、分散データ処理装置１０のＭａｐＲｅｄｕｃｅ計算部１２ｂは、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータから得られるサンプルデータを入力として、Ｍａｐ関数を実行する全プロセスの実行コストとＲｅｄｕｃｅ関数を実行する全プロセスの実行コストとの比率を取得し、これらのコスト比（ＭａｐＲｅｄｕｃｅ間コスト比）を計算して統計情報として統計情報記憶部１３ａに記録する（ステップＳ１２）。
【００４１】
続いて、分散データ処理装置１０のＲｅｄｕｃｅ決定部１２ｃは、データ分析者がＭａｐＲｅｄｕｃｅを用いて分析処理要求を処理する際に、ＭａｐＲｅｄｕｃｅ実行部１２ｅから呼び出され、ステップＳ１１における出力結果であるキーの頻度情報を統計情報記憶部１３ａから読み出して、Ｒｅｄｕｃｅの負荷が平準化されるようＭａｐ関数を実行するプロセスからＲｅｄｕｃｅ関数を実行するプロセスへのデータ割り当て関数を決定して、ＭａｐＲｅｄｕｃｅ実行部１２ｅに返却する（ステップＳ１３）。
【００４２】
そして、分散データ処理装置１０のＭａｐＲｅｄｕｃｅ決定部１２ｄは、ＭａｐＲｅｄｕｃｅ実行部１２ｅから呼び出され、ステップＳ１２の出力結果であるＭａｐＲｅｄｕｃｅ間コスト比を統計情報記憶部１３ａから読み出して、Ｍａｐを実行するプロセス群とＲｅｄｕｃｅを実行するプロセス群の負荷が平準化されるようＭａｐ関数を実行するプロセス数とＲｅｄｕｃｅ関数を実行するプロセス数を決定してＭａｐＲｅｄｕｃｅ実行部１２ｅに返却する（ステップＳ１４）。
【００４３】
続いて、分散データ処理装置１０のＭａｐＲｅｄｕｃｅ実行部１２ｅは、Ｒｅｄｕｃｅ決定部１２ｃから返却されたデータ割り当て関数をＭａｐ関数を実行する全プロセスに配布し、ＭａｐＲｅｄｕｃｅ決定部１２ｄから返却されたＭａｐ関数を実行するプロセス数とＲｅｄｕｃｅ関数を実行するプロセス数に従って、これらのプロセスを起動する。その後、処理対象となるデータ記憶部１３ｂからデータを読み込み、ＭａｐＲｅｄｕｃｅ処理を実行する（ステップＳ１５）。
【００４４】
［分散データ処理装置による処理］
次に、図６〜図９のフローチャートを用いて、分散データ処理装置１０の処理手順を説明する。
【００４５】
まず、図６を用いて、第一の実施の形態に係る分散データ処理装置１０による頻度情報計算処理の流れを説明する。図６は、第一の実施の形態に係る分散データ処理装置による頻度情報計算処理の流れを示すフローチャートである。なお、図６に示す処理は、図５におけるステップＳ１１の処理に対応するものである。
【００４６】
図６に示すように、Ｒｅｄｕｃｅ計算部１２ａは、Ｒｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータから得られるサンプルデータを入力する（ステップＳ２１）。そして、Ｒｅｄｕｃｅ計算部１２ａは、サンプルデータを入力として、ＭａｐＲｅｄｕｃｅプログラムを実行してＲｅｄｕｃｅ関数の入力キーの頻度情報を計算し（ステップＳ２２）、頻度情報を統計情報として統計情報記憶部１３ａに記録する。
【００４７】
次に、図７を用いて、第一の実施の形態に係る分散データ処理装置１０によるＲｅｄｕｃｅ負荷平準化処理の流れを説明する。図７は、第一の実施の形態に係る分散データ処理装置によるＲｅｄｕｃｅ負荷平準化処理の流れを示すフローチャートである。なお、図７に示す処理は、図５におけるステップＳ１２の処理に対応するものである。
【００４８】
図７に示すように、Ｒｅｄｕｃｅ決定部１２ｃは、統計情報記憶部１３ａからキーの頻度情報を読み込み（ステップＳ３１）。そして、Ｒｅｄｕｃｅ決定部１２ｃは、キー値に関するヒストグラムなどの頻度分布と、ＭａｐＲｅｄｕｃｅプログラムで指定されたＲｅｄｕｃｅプロセス数を入力として、ヒストグラムの分布を示すキー・バリューのデータが均等にＲｅｄｕｃｅプロセスに分割されるように入力データを割り当てるｐａｒｔｉｔｉｏｎ関数を決定する（ステップＳ３２）。
【００４９】
次に、図８を用いて、第一の実施の形態に係る分散データ処理装置１０によるＭａｐＲｅｄｕｃｅ間コスト比計算処理の流れを説明する。図８は、第一の実施の形態に係る分散データ処理装置によるＭａｐＲｅｄｕｃｅ間コスト比計算処理の流れを示すフローチャートである。なお、図８に示す処理は、図５におけるステップＳ１３の処理に対応するものである。
【００５０】
図８に示すように、ＭａｐＲｅｄｕｃｅ計算部１２ｂは、ＭａｐＲｅｄｕｃｅ処理を実行した過去の入力データあるいは新たに入力するデータから得られるサンプルデータを入力する（ステップＳ４１）。ＭａｐＲｅｄｕｃｅ計算部１２ｂは、入力データに対してＭａｐ関数とＲｅｄｕｃｅ関数を実際に実行して、Ｍａｐ関数を実行するプロセスの実行コストとＲｅｄｕｃｅ関数を実行するプロセスの実行コストの見積もりを計算し（ステップＳ４２）、これらの実行コストの比を計算して統計情報記憶部１３ａに書き込む。
【００５１】
次に、図９を用いて、第一の実施の形態に係る分散データ処理装置１０によるＭａｐＲｅｄｕｃｅ負荷平準化処理の流れを説明する。図９は、第一の実施の形態に係る分散データ処理装置によるＭａｐＲｅｄｕｃｅ負荷平準化処理の流れを示すフローチャートである。なお、図９に示す処理は、図５におけるステップＳ１４の処理に対応するものである。
【００５２】
図９に示すように、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、統計情報記憶部１３ａからＭａｐＲｅｄｕｃｅ間コスト比を読み込む（ステップＳ５１）。そして、ＭａｐＲｅｄｕｃｅ決定部１２ｄは、Ｍａｐ関数を実行する全プロセスとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間が平準化されるように、Ｍａｐプロセス数とＲｅｄｕｃｅプロセス数を決定する（ステップＳ５２）。
【００５３】
［第一の実施の形態の効果］
このように、ＭａｐＲｅｄｕｃｅにより分散されたデータを複数のプロセスで処理する分散データ処理装置１０は、所定の区間で分けられた各データについて、Ｒｅｄｕｃｅ関数による処理がプロセスにより実行された場合におけるプロセスの処理負荷をそれぞれ計算する。そして、分散データ処理装置１０は、計算された各データの処理負荷を用いて、Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間が平準化されるように、各プロセスへのデータの割り当てを決定する。このため、分散データ処理装置１０は、Ｒｅｄｕｃｅ関数を実行する全プロセスの実行時間を平準化することで、ＭａｐＲｅｄｕｃｅを実行する分散データ処理において、計算機資源を効率よく使うことが可能である。
【００５４】
また、分散データ処理装置１０は、入力された各データに適用するＭａｐ関数による処理を実行するプロセスの実行コストと、分散された各データに適用するＲｅｄｕｃｅ関数による処理を実行するプロセスの実行コストとの比率を計算し、計算された比率に応じて、Ｒｅｄｕｃｅ関数の処理を実行する各プロセスの実行時間と、Ｍａｐ関数の処理を実行する各プロセスの実行時間とが平準化されるように、Ｍａｐプロセス数およびＲｅｄｕｃｅプロセス数を決定する。このため、Ｍａｐ関数を実行する全プロセスとＲｅｄｕｃｅ関数を実行する全プロセスの実行時間を平準化することで、ＭａｐＲｅｄｕｃｅを実行する分散データ処理において、計算機資源を効率よく使うことが可能である。
【００５５】
（システム構成等）
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００５６】
また、本実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００５７】
（プログラム）
また、上記実施の形態に係る分散データ処理装置１０が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。この場合、コンピュータがプログラムを実行することにより、上記実施の形態と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより上記実施の形態と同様の処理を実現してもよい。以下に、分散データ処理装置１０と同様の機能を実現する分散データ処理プログラムを実行するコンピュータの一例を説明する。
【００５８】
図１０は、分散データ処理プログラムを実行するコンピュータを示す図である。図１０に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【００５９】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【００６０】
ここで、図１０に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施の形態で説明した各テーブルは、例えばハードディスクドライブ１０９０やメモリ１０１０に記憶される。
【００６１】
また、分散データ処理プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、ハードディスクドライブ１０９０に記憶される。具体的には、上記実施の形態で説明した分散データ処理装置１０が実行する各処理が記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。
【００６２】
また、分散データ処理プログラムによる情報処理に用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【００６３】
なお、分散データ処理プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１０４１等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、分散データ処理プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【００６４】
１０    分散データ処理装置
１１    入出力部
１２    制御部
１２ａ  Ｒｅｄｕｃｅ計算部
１２ｂ  ＭａｐＲｅｄｕｃｅ計算部
１２ｃ  Ｒｅｄｕｃｅ決定部
１２ｄ  ＭａｐＲｅｄｕｃｅ決定部
１２ｅ  ＭａｐＲｅｄｕｃｅ実行部
１３    記憶部
１３ａ  統計情報記憶部
１３ｂ  データ記憶部
【図１】
2015191428.tif 000003
【図２】
2015191428.tif 000004
【図３】
2015191428.tif 000005
【図４】
2015191428.tif 000006
【図５】
2015191428.tif 000007
【図６】
2015191428.tif 000008
【図７】
2015191428.tif 000009
【図８】
2015191428.tif 000010
【図９】
2015191428.tif 000011
【図１０】
2015191428.tif 000012