(57)【特許請求の範囲】
【請求項１】
コンピュータに、
第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断し、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする割当プログラム。
【請求項２】
前記コンピュータに、
前記第１の処理の処理対象に固有の識別情報を生成する処理を実行させ、
前記第１の処理を割り当てる処理は、
前記データが入力されたことを検出した場合、前記ノード群のうちのいずれかのノードに、生成した前記識別情報とともに、前記データを処理対象とする前記第１の処理を割り当て、
前記第２の処理を割り当てる処理は、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記識別情報とともに、前記第１の処理の処理結果を処理対象とする第２の処理を割り当てることを特徴とする請求項１に記載の割当プログラム。
【請求項３】
前記第２の処理を割り当てる処理は、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記第１の処理の処理結果の属性をもとに前記第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする請求項１または２に記載の割当プログラム。
【請求項４】
コンピュータに、
第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断し、
前記データが入力されたことを検出した場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断し、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする割当プログラム。
【請求項５】
前記コンピュータに、
前記第１の処理の処理対象に固有の識別情報を生成する処理を実行させ、
前記第１の処理を割り当てる処理は、
前記データが入力されたことを検出した場合、前記ノード群のうちのいずれかのノードに、生成した前記識別情報とともに、前記データを処理対象とする前記第１の処理を割り当て、
前記第２の処理を割り当てる処理は、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記識別情報とともに、前記第１の処理の処理結果を処理対象とする第２の処理を割り当てることを特徴とする請求項４に記載の割当プログラム。
【請求項６】
前記第２の処理を割り当てる処理は、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記第１の処理の処理結果の属性をもとに前記第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てることを特徴とする請求項４または５に記載の割当プログラム。
【請求項７】
第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出する検出部と、
前記検出部によって前記データが入力されたことが検出された場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当てる第１の割当部と、
前記データが入力されたことが検出された場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断する判断部と、
前記判断部によって前記データに前記末尾情報が付与されていると判断された場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる第２の割当部と、
を有することを特徴とする割当装置。
【請求項８】
第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出する検出部と、
前記検出部によって前記データが入力されたことが検出された場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当てる第１の割当部と、
前記検出部によって前記データが入力されたことが検出された場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断する第１の判断部と、
前記検出部によって前記データが入力されたことが検出された場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断する第２の判断部と、
前記第１の判断部によって前記データ群が前記記憶部に入力されたと判断され、かつ、前記第２の判断部によって前記データ群が前記一連のデータ群の末尾のデータ群であると判断された場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる第２の割当部と、
を有することを特徴とする割当装置。
【請求項９】
コンピュータが、
第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断し、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行することを特徴とする割当方法。
【請求項１０】
コンピュータが、
第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断し、
前記データが入力されたことを検出した場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断し、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行することを特徴とする割当方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、割当プログラム、割当装置、および割当方法に関する。
【背景技術】
【０００２】
近年、膨大なデータを処理する技術として、ＭａｐＲｅｄｕｃｅという分散処理技術がある。ＭａｐＲｅｄｕｃｅは、データの処理をＭａｐ処理とＲｅｄｕｃｅ処理の２段階に分けて行うものであり、あらかじめ定義された期間ごとにデータベースに蓄積されたデータを複数に分割し、複数のノードの各々が、分割されたデータを処理対象として何らかの処理を施すＭａｐ処理を実行する。そして、複数のノードの少なくともいずれかのノードが、Ｍａｐ処理の処理結果を処理対象として、データ全体についての処理結果を取得するＲｅｄｕｃｅ処理を実行する。
【０００３】
関連する技術として、複数のユーザの各々についてそれぞれの興味集合を記憶した情報に対して、ＭａｐＲｅｄｕｃｅを適用し、ユーザのクラスタリングを可能にするための技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特表２００９−５０５２９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術では、処理対象となる全データに対して一括してＭａｐ処理を施すため、処理対象となる全データが揃うのを待ってＭａｐ処理の実行を開始することになり、Ｍａｐ処理の実行開始が遅れてしまう。また、処理対象となる全データに対して一括してＭａｐ処理を施すと、各ノードのＭａｐ処理の実行時間帯が集中してＭａｐ処理の遅延を招いてしまう。
【０００６】
一側面では、本発明は、順次入力される一連のデータに対する分散処理の効率化を図ることを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出し、データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードにデータを処理対象とする第１の処理を割り当て、データが入力されたことを検出した場合、データに、第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断し、データに末尾情報が付与されていると判断した場合、ノード群のうちのいずれかのノードに、一連のデータの各々のデータを処理対象として実行された第１の処理の処理結果の属性をもとに第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てる割当プログラム、割当装置、および割当方法が提案される。
【０００８】
また、本発明の他の側面によれば、第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出し、データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードにデータを処理対象とする第１の処理を割り当て、データが入力されたことを検出した場合、データ群に含まれるデータの個数と、記憶部に入力されたデータの個数とに基づいて、データ群が記憶部に入力されたか否かを判断し、データが入力されたことを検出した場合、データ群が第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断し、データ群が記憶部に入力されたと判断し、かつ、データ群が一連のデータ群の末尾のデータ群であると判断した場合、ノード群のうちのいずれかのノードに、一連のデータ群の各々のデータを処理対象として実行された第１の処理の処理結果の属性をもとに第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てる割当プログラム、割当装置、および割当方法が提案される。
【発明の効果】
【０００９】
本発明の一様態によれば、順次入力される一連のデータに対する分散処理の効率化を図ることができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施の形態１にかかる分散処理システムの動作例を示す説明図（その１）である。
【図２】図２は、実施の形態１にかかる分散処理システムの動作例を示す説明図（その２）である。
【図３】図３は、分散処理システムのシステム構成例を示す説明図である。
【図４】図４は、マスタノードのハードウェア構成例を示すブロック図である。
【図５】図５は、分散処理システムのソフトウェア構成例を示す説明図である。
【図６】図６は、ＨＤＦＳによるファイルの記憶方法の一例を示す説明図である。
【図７】図７は、ブロックとスプリットの関係を示す説明図である。
【図８】図８は、マスタノードの機能構成例を示すブロック図である。
【図９】図９は、ＭａｐＲｅｄｕｃｅ処理の具体例を示す説明図である。
【図１０】図１０は、順次入力されたスプリットを一度に処理するＭａｐＲｅｄｕｃｅ処理の処理例を示す説明図である。
【図１１】図１１は、順次入力されたスプリットを逐次処理するＭａｐＲｅｄｕｃｅ処理の具体例を示す説明図である。
【図１２】図１２は、ＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その１）である。
【図１３】図１３は、ＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その２）である。
【図１４】図１４は、準備処理手順の一例を示すフローチャートである。
【図１５】図１５は、初期化処理手順の一例を示すフローチャートである。
【図１６】図１６は、Ｍａｐタスク生成処理手順の一例を示すフローチャートである。
【図１７】図１７は、Ｍａｐタスク割当処理手順の一例を示すフローチャートである。
【図１８】図１８は、Ｍａｐ処理手順の一例を示すフローチャートである。
【図１９】図１９は、シャッフル＆ソート処理手順の一例を示すフローチャートである。
【図２０】図２０は、Ｒｅｄｕｃｅ処理手順の一例を示すフローチャートである。
【図２１】図２１は、実施の形態２にかかる分散処理システムの動作例を示す説明図である。
【図２２】図２２は、実施の形態２にかかるマスタノードの機能構成例を示すブロック図である。
【図２３】図２３は、実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その１）である。
【図２４】図２４は、ファイル受付処理手順の一例を示すフローチャートである。
【図２５】図２５は、実施の形態２にかかるＭａｐタスク生成処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、開示の割当プログラム、割当装置、および割当方法の実施の形態を詳細に説明する。なお、実施の形態１にかかる割当装置の例として、分散処理システム内において、スレーブノードに処理を割り当てる、マスタノードにて説明を行う。
【００１２】
（実施の形態１）
図１および図２は、実施の形態１にかかる分散処理システムの動作例を示す説明図（その１）および（その２）である。分散処理システム１００は、第１の処理および第２の処理を割り当てるマスタノード１０１と、第１の処理および第２の処理が割り当てられるスレーブノード１０２と、データベース１１０を含む。スレーブノード１０２は、分散処理システム１００内にｎ台存在していてもよい。ｎは１以上の整数である。図１の例では、分散処理システム１００は、スレーブノード１０２＃１とスレーブノード１０２＃２を含んでいる。以下の説明では、ｘをインデックスとし、末尾記号“＃ｘ”が付与されている記号については、ｘ番目のスレーブノード１０２について説明しているとする。ｘは１からｎまでの整数となる。また、スレーブノード１０２と表現されている場合、スレーブノード１０２全てに共通する説明を行っているとする。
【００１３】
スレーブノード１０２に割り当てられる第１の処理は、他のスレーブノード１０２に割り当てられる第１の処理とは独立したものであり、スレーブノード１０２に割り当てられた全ての第１の処理を並列に実行できる処理である。たとえば、第１の処理は、データベース１１０に入力されたデータを用いて、他の入力されたデータを処理対象とする別の第１の処理とは独立して、ｋｅｙＶａｌｕｅの形式にてデータを出力する処理である。ｋｅｙＶａｌｕｅの形式となるデータとは、Ｖａｌｕｅフィールドに格納された任意の保存したい値と、ｋｅｙフィールドに格納された保存したいデータに対応する一意の標識と、の組である。
【００１４】
第２の処理は、第１の処理の処理結果の属性をもとに前記第１の処理の処理結果を集約した１以上の処理結果を処理対象とする処理である。たとえば、第１の処理の処理結果が、ｋｅｙＶａｌｕｅの形式となるデータである場合、第２の処理は、第１の処理の処理結果の属性となるＫｅｙフィールドをもとに第１の処理結果を集約した１つ以上の処理結果を処理対象とする処理である。また、たとえば、第２の処理は、Ｖａｌｕｅフィールドをもとに第１の処理結果を集約した１つ以上の処理結果を処理対象とする処理であってもよい。
【００１５】
データベース１１０は、分散処理システム１００内の装置がアクセス可能な記憶領域である。また、データベース１１０は、第１の処理の処理対象となるデータが順次入力される。
【００１６】
データは、どのようなデータであってもよい。たとえば、一連のデータは、ある時間帯の計測結果を記録したファイルである。また、一連のデータのいずれかのデータは、たとえば、ファイルを論理的な区切りにて分割したスプリットである。論理的な区切りとは、たとえば、ファイルの行単位である。
【００１７】
ある時間帯の計測結果は、たとえば、１分間ごとの道路ごとの道路通行量の計測結果である。または、ある時間帯の計測結果は、１分間ごとのある室内の温度や湿度の計測結果でもよい。分散処理システム１００は、一連のデータを参照して、第１の処理および第２の処理を実行し、処理結果を出力する。たとえば、分散処理システム１００は、１分間ごとの道路ごとの道路通行量の計測結果を５分間分用いて、各道路の車両数を計数し、渋滞情報として出力する。
【００１８】
以下、１４：１１〜１４：１５までの５分間の計測ファイル１１１〜１１３を分割したスプリットが順次入力される状態において、分散処理システム１００が、計測ファイル群を用いて渋滞情報を出力することを前提として説明を行う。また、計測ファイル１１３には、渋滞情報の処理対象の最後のファイルであることを示す末尾情報１１４が付与されているとする。さらに、分散処理システム１００は、渋滞情報を算出する処理を、スレーブノード１０２＃１と、スレーブノード１０２＃２とに分散して処理する。分散して処理するソフトウェアとして、実施の形態１にかかる分散処理システム１００は、Ｈａｄｏｏｐを採用した例を用いて説明する。
【００１９】
また、Ｈａｄｏｏｐにて用いられている用語を用いて、実施の形態１にかかる分散処理システム１００を説明する。「ジョブ」は、Ｈａｄｏｏｐにおける処理単位である。たとえば、渋滞情報を算出する処理が１つのジョブとなる。「タスク」は、ジョブが分割された処理単位である。タスクは、第１の処理であるＭａｐ処理を実行するＭａｐタスクと、第２の処理であるＲｅｄｕｃｅ処理を実行するＲｅｄｕｃｅタスクとの２種類がある。Ｒｅｄｕｃｅタスクは、Ｒｅｄｕｃｅ処理を実行しやすくするため、Ｒｅｄｕｃｅ処理の前に、ＫｅｙフィールドをもとにＭａｐ処理の処理結果を集約するシャッフル＆ソート処理を実行する。
【００２０】
図１では、分散処理システム１００の時刻ｔ１における状態と、時刻ｔ２における状態とを表示する。図２では、分散処理システム１００の時刻ｔ３における状態と、時刻ｔ４における状態と、時刻ｔ５における状態とを表示する。なお、時刻ｔ１、時刻ｔ２、時刻ｔ３、時刻ｔ４、時刻ｔ５の順に時間が経過しているとする。
【００２１】
図１に示す時刻ｔ１において、マスタノード１０１は、渋滞情報を算出するというジョブの実行要求を受け付ける。また、図１に示す時刻ｔ１において、マスタノード１０１は、データベース１１０に、１４：１１の計測ファイル１１１のスプリット１が入力されたことを検出する。スプリット１が入力されたことを検出した場合、マスタノード１０１は、スレーブノード１０２＃１にスプリット１を処理対象とする、ジョブを分割したＭａｐ処理１を割り当てる。
【００２２】
このとき、処理対象となる全部のスプリットが揃うのを待たずに一部のスプリットに対するＭａｐ処理の実行を開始すると、一部のスプリットをジョブ全体の処理対象とみなしてＭａｐＲｅｄｕｃｅ処理が実行され、期待する処理結果を得られない場合がある。処理結果を正確にするため、マスタノード１０１は、同一ジョブとして処理する計測ファイル群の末尾のスプリットであることを示す末尾情報がスプリット１に付与されているか否かを判断する。スプリット１には末尾情報が付与されていないため、マスタノード１０１は、スプリットがまだ入力され続けると判断する。
【００２３】
図１に示す時刻ｔ２において、マスタノード１０１は、データベース１１０に、１４：１４の計測ファイル１１２のスプリット２が入力されたことを検出する。スプリット２が入力されたことを検出した場合、マスタノード１０１は、スレーブノード１０２＃２にスプリット２を処理対象とするＭａｐ処理２を割り当てる。また、図１に示す時刻ｔ２において、スレーブノード１０２＃１は、Ｍａｐ処理１を完了しており、Ｍａｐ処理結果１を保持している。また、マスタノード１０１は、スプリット２に末尾情報が付与されているか否かを判断する。スプリット２には末尾情報が付与されていないため、マスタノード１０１は、スプリットがまだ入力され続けると判断する。
【００２４】
図２に示す時刻ｔ３において、マスタノード１０１は、データベース１１０に、１４：１５の計測ファイル１１３のスプリット３が入力されたことを検出する。スプリット３が入力されたことを検出した場合、マスタノード１０１は、スレーブノード１０２＃１にスプリット３を処理対象とするＭａｐ処理３を割り当てる。また、図２に示す時刻ｔ３において、スレーブノード１０２＃２は、Ｍａｐ処理２を完了しており、Ｍａｐ処理結果２を保持している。また、マスタノード１０１は、スプリット３に末尾情報が付与されているか否かを判断する。スプリット３には末尾情報が付与されていないため、マスタノード１０１は、スプリットがまだ入力され続けると判断する。
【００２５】
図２に示す時刻ｔ４において、マスタノード１０１は、データベース１１０に、１４：１５の計測ファイル１１３のスプリット４が入力されたことを検出する。スプリット４は、計測ファイル１１３の末尾であるとする。また、データベース１１０にスプリット４を入力する装置は、スプリット３の入力が完了した後に、スプリット４を入力する。スプリット４は計測ファイル１１３の末尾であるため、スプリット４は、末尾情報１１４が付与されている。スプリット４が入力されたことを検出した場合、マスタノード１０１は、スレーブノード１０２＃２にスプリット４を処理対象とするＭａｐ処理４を割り当てる。また、図２に示す時刻ｔ３において、スレーブノード１０２＃２は、Ｍａｐ処理２を完了しており、Ｍａｐ処理結果２を保持している。
【００２６】
また、マスタノード１０１は、スプリット４に末尾情報１１４が付与されているか否かを判断する。スプリット４には末尾情報１１４が付与されているため、マスタノード１０１は、スプリットの入力が終了したと判断する。スプリットに末尾情報１１４が付与されていると判断した場合の動作について、図２に示す時刻ｔ５にて説明する。
【００２７】
図２に示す時刻ｔ５において、マスタノード１０１は、Ｍａｐ処理結果１〜４をＭａｐ処理結果の属性をもとに集約するシャッフル＆ソート処理１、２を、スレーブノード１０２＃１と、スレーブノード１０２＃２に割り当てる。シャッフル＆ソート処理１は、Ｍａｐ処理結果１とＭａｐ処理結果３を処理対象としている。シャッフル＆ソート処理２は、Ｍａｐ処理結果２とＭａｐ処理結果４を処理対象としている。また、図２では図示していないが、スレーブノード１０２＃１は、シャッフル＆ソート処理１の処理結果を処理対象として、Ｒｅｄｕｃｅ処理１を実行する。また、スレーブノード１０２＃２は、シャッフル＆ソート処理２の処理結果を処理対象として、Ｒｅｄｕｃｅ処理２を実行する。
【００２８】
このように、分散処理システム１００は、データベース１１０に順次入力されるデータに対してＭａｐ処理を逐次実行し、末尾情報が付与されたデータまでのＭａｐ処理完了後にシャッフル＆ソート処理に移行する。データに対して逐次実行することと、末尾情報が付与されたデータまでシャッフル＆ソート処理の実行を待つことにより、分散処理システム１００は、同一ジョブのＭａｐ処理の実行時間帯の集中を避け、効率的に分散処理を実行することができる。以下、図２〜図２０を用いて、分散処理システム１００について説明する。
【００２９】
図３は、分散処理システムのシステム構成例を示す説明図である。分散処理システム１００は、マスタノード１０１と、スレーブノード１０２＃１〜ｎと、ジョブクライアント３０１と、ＨＤＦＳ（Ｈａｄｏｏｐ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｆｉｌｅ  Ｓｙｓｔｅｍ）クライアント３０２とを含む。マスタノード１０１〜ＨＤＦＳクライアント３０２とは、それぞれ、ネットワーク３１１にて接続されている。また、マスタノード１０１と、スレーブノード１０２＃１〜ｎを含めてＨａｄｏｏｐクラスタ３１２として定義する。Ｈａｄｏｏｐクラスタ３１２は、ジョブクライアント３０１と、ＨＤＦＳクライアント３０２を含んでもよい。
【００３０】
マスタノード１０１は、Ｍａｐ処理と、Ｒｅｄｕｃｅ処理をスレーブノード１０２＃１〜スレーブノード１０２＃ｎに割り当てる装置である。スレーブノード１０２＃１〜スレーブノード１０２＃ｎは、割り当てられたＭａｐ処理と、Ｒｅｄｕｃｅ処理を実行する装置である。
【００３１】
ジョブクライアント３０１は、データベース１１０に入力される計測ファイルと、実行可能ファイルとなるプログラムと、実行ファイルの設定ファイルとを記憶しており、ジョブの実行要求をマスタノード１０１に通知する装置である。
【００３２】
なお、計測ファイルは、計測ファイルを生成する分散処理システム１００以外のシステムに含まれる装置からジョブクライアント３０１に送信されてもよいし、分散処理システム１００の運用者等により、ジョブクライアント３０１に格納されてもよい。また、計測ファイルをスプリットに分割する装置は、ジョブクライアント３０１でもよいし、マスタノード１０１でもよい。また、ジョブクライアント３０１は、計測ファイルに末尾情報を付与する。たとえば、ジョブクライアント３０１は、１４：１１〜１４：１５の計測ファイルを用いる渋滞情報を算出するジョブを登録しており、１４：１５の計測ファイル１１３を取得した場合、１４：１５の計測ファイル１１３の末尾に末尾情報を付与する。
【００３３】
ＨＤＦＳクライアント３０２は、Ｈａｄｏｏｐ独自のファイルシステムである、ＨＤＦＳのファイル操作を行う端末である。ネットワーク３１１は、たとえば、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットである。
【００３４】
（マスタノード１０１のハードウェア）
図４は、マスタノードのハードウェア構成例を示すブロック図である。図４において、マスタノード１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）４０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）４０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）４０３と、を含む。また、マスタノード１０１は、磁気ディスクドライブ４０４と、磁気ディスク４０５と、ＩＦ（Ｉｎｔｅｒｆａｃｅ）４０６と、を含む。また、各部はバス４０７によってそれぞれ接続されている。
【００３５】
ＣＰＵ４０１は、マスタノード１０１の全体の制御を司る演算処理装置である。ＲＯＭ４０２は、ブートプログラムなどのプログラムを記憶する不揮発性メモリである。ＲＡＭ４０３は、ＣＰＵ４０１のワークエリアとして使用される揮発性メモリである。磁気ディスクドライブ４０４は、ＣＰＵ４０１の制御にしたがって磁気ディスク４０５に対するデータのリード／ライトを制御する制御装置である。磁気ディスク４０５は、磁気ディスクドライブ４０４の制御で書き込まれたデータを記憶する不揮発性メモリである。なお、ＲＯＭ４０２、磁気ディスク４０５のいずれかの記憶装置に、実施の形態１にかかる割当プログラムが格納されていてもよい。
【００３６】
ＩＦ４０６は、通信回線を通じて、ネットワーク３１１を介し他の装置に接続される。そして、ＩＦ４０６は、ネットワーク３１１と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。ＩＦ４０６には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３７】
なお、マスタノード１０１の管理者がマスタノード１０１を直接操作する場合、図４には図示していないが、マスタノード１０１は、光ディスクドライブと、光ディスクと、ディスプレイと、マウスと、を有していてもよい。
【００３８】
光ディスクドライブは、ＣＰＵ４０１の制御にしたがって光ディスクに対するデータのリード／ライトを制御する制御装置である。光ディスクは、光ディスクドライブの制御で書き込まれたデータを記憶したり、光ディスクに記憶されたデータをコンピュータに読み取らせたりする。
【００３９】
ディスプレイは、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。たとえば、ディスプレイは、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００４０】
キーボードは、文字、数字、各種指示などの入力のためのキーを有し、データの入力を行う。また、キーボードは、タッチパネル式の入力パッドやテンキーなどであってもよい。マウスは、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。また、マスタノード１０１は、マウスの代わりとして、ポインティングデバイスとして同様に機能を有するものであれば、トラックボールやジョイスティックなどであってもよい。
【００４１】
また、スレーブノード１０２＃１と、スレーブノード１０２＃２と、ジョブクライアント３０１は、ＣＰＵと、ＲＯＭと、ＲＡＭと、磁気ディスクドライブと、磁気ディスクと、を有する。また、ＨＤＦＳクライアント３０２は、ＣＰＵと、ＲＯＭと、ＲＡＭと、磁気ディスクドライブと、磁気ディスクと、光ディスクドライブと、光ディスクと、ディスプレイと、マウスと、を有する。
【００４２】
図５は、分散処理システムのソフトウェア構成例を示す説明図である。マスタノード１０１は、ジョブトラッカー５０１と、ジョブスケジューラ５０２と、ネームノード５０３と、ＨＤＦＳ５０４と、メタデータテーブル５０５とを有する。スレーブノード１０２＃ｘは、タスクトラッカー５１１＃ｘと、データノード５１２＃ｘと、ＨＤＦＳ５１３＃ｘと、Ｍａｐタスク５１４＃ｘと、Ｒｅｄｕｃｅタスク５１５＃ｘを有する。ｘは、１からｎまでの整数である。ジョブクライアント３０１は、ＭａｐＲｅｄｕｃｅプログラム５２１と、ＪｏｂＣｏｎｆ５２２とを、有する。ＨＤＦＳクライアント３０２は、ＨＤＦＳクライアントアプリケーション５３１と、ＨＤＦＳ  ＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）５３２と、を有する。
【００４３】
また、図１に示したデータベース１１０は、ＨＤＦＳ５０４、ＨＤＦＳ５１３＃１〜ｎとなる。また、Ｈａｄｏｏｐは、ＨＤＦＳ以外のファイルシステムであってもよい。たとえば、分散処理システム１００は、データベース１１０として、マスタノード１０１とスレーブノード１０２＃１〜ｎが、ＦＴＰ（Ｆｉｌｅ  Ｔｒａｎｓｆｅｒ  Ｐｒｏｔｏｃｏｌ）によりアクセス可能なファイルサーバを採用してもよい。
【００４４】
ジョブトラッカー５０１は、実行すべきジョブをジョブクライアント３０１から受け付ける。続けて、ジョブトラッカー５０１は、クラスタ中の利用可能なタスクトラッカー５１１に、Ｍａｐタスク５１４、Ｒｅｄｕｃｅタスク５１５を割り当てる。ジョブスケジューラ５０２は、次に実行するジョブを決定する。具体的に、ジョブスケジューラ５０２は、ジョブクライアント３０１から要求された複数のジョブのうち、次に実行するジョブを決定する。また、ジョブスケジューラ５０２は、決定したジョブに対して、スプリットが入力される都度、Ｍａｐタスク５１４を生成する。
【００４５】
ネームノード５０３は、Ｈａｄｏｏｐクラスタ３１２内のファイルの記憶先を制御する。たとえば、ネームノード５０３は、データベース１１０に入力されたファイルが、ＨＤＦＳ５０４、ＨＤＦＳ５１３＃１〜ｎのどこに記憶されるかを決定し、決定されたＨＤＦＳにファイルを送信する。
【００４６】
ＨＤＦＳ５０４、ＨＤＦＳ５１３＃１〜ｎは、ファイルを分散して記憶する記憶領域である。具体的に、ＨＤＦＳ５１３＃１〜ｎは、ファイルを物理的な区切りにて分割したブロック単位にて記憶している。メタデータテーブル５０５は、ＨＤＦＳ５０４、ＨＤＦＳ５１３＃１〜ｎに記憶しているファイルの位置を記憶する記憶領域である。メタデータテーブル５０５を用いた具体的なファイルの記憶方法としては、図６にて後述する。また、ブロックとスプリットの関係は、図７にて後述する。
【００４７】
タスクトラッカー５１１は、ジョブトラッカー５０１から割り当てられたＭａｐタスク５１４やＲｅｄｕｃｅタスク５１５を、自装置に実行させる。また、タスクトラッカー５１１は、Ｍａｐタスク５１４やＲｅｄｕｃｅタスク５１５の進捗状況や処理の完了報告をジョブトラッカー５０１に通知する。
【００４８】
データノード５１２は、スレーブノード１０２内のＨＤＦＳ５１３を制御する。Ｍａｐタスク５１４は、Ｍａｐ処理を実行する。Ｒｅｄｕｃｅタスク５１５は、Ｒｅｄｕｃｅ処理を実行する。また、Ｒｅｄｕｃｅタスク５１５は、Ｒｅｄｕｃｅ処理を行う前段階として、シャッフル＆ソート処理を実行する。シャッフル＆ソート処理は、Ｍａｐ処理の結果を集約する処理を行う。具体的に、シャッフル＆ソート処理は、Ｍａｐ処理の結果をＫｅｙごとに並び替え、同一のｋｅｙとなったＶａｌｕｅを纏めて、Ｒｅｄｕｃｅ処理に出力する。
【００４９】
ＭａｐＲｅｄｕｃｅプログラム５２１は、Ｍａｐ処理を実行するプログラムと、Ｒｅｄｕｃｅ処理を実行するプログラムとである。ＪｏｂＣｏｎｆ５２２は、ＭａｐＲｅｄｕｃｅプログラム５２１の設定を記述したプログラムである。設定の例としては、Ｍａｐタスク５１４の生成数や、Ｒｅｄｕｃｅタスク５１５の生成数や、ＭａｐＲｅｄｕｃｅ処理の処理結果の出力先等である。
【００５０】
ＨＤＦＳクライアントアプリケーション５３１は、ＨＤＦＳを操作するアプリケーションである。ＨＤＦＳ  ＡＰＩ５３２は、ＨＤＦＳにアクセスするＡＰＩである。ＨＤＦＳ  ＡＰＩ５３２は、たとえば、ＨＤＦＳクライアントアプリケーション５３１からファイルのアクセス要求があった場合、データノード５１２に、ファイルを保持しているか否かを問い合わせる。
【００５１】
図６は、ＨＤＦＳによるファイルの記憶方法の一例を示す説明図である。図６の（Ａ）では、メタデータテーブル５０５の記憶内容の一例を示している。図６の（Ｂ）では、ファイルの分割方法を示している。図６の（Ｃ）では、メタデータテーブル５０５の記憶内容に従った、ＨＤＦＳ５１３の記憶内容の一例を示している。
【００５２】
図６の（Ａ）に示すメタデータテーブル５０５は、レコード６０１−１〜５を記憶する。メタデータテーブル５０５は、ファイルパス、ブロック番号、データノードという３つのフィールドを含む。ファイルパスフィールドには、ルートパスからのファイルの位置を示す文字列が格納される。ブロック番号フィールドには、ファイルを物理的に分割した際のブロックのＩＤが格納される。データノードフィールドには、該当のブロックＩＤにて示されるブロックが格納されているデータノードのＩＤが格納される。図６に示すデータノードフィールドは、ＨＤＦＳ５１３のインデックスが格納されているとする。
【００５３】
たとえば、レコード６０１−１は、ファイルパス“／ｆｉｌｅ／Ｘ．ｔｘｔ”のブロック番号１が、ＨＤＦＳ５１３＃１、＃４、＃６に格納されていることを示す。このように、ＨＤＦＳは、１つのファイルをブロックに分割し、ブロックを複数のＨＤＦＳ５１３に格納する。また、分割したブロックの格納先は、ブロック間で異なる組合せとなるように配置する。たとえば、ファイルパス“／ｆｉｌｅ／Ｘ．ｔｘｔ”のブロック番号１は、ＨＤＦＳ５１３＃１、＃４、＃６に格納されており、ファイルパス“／ｆｉｌｅ／Ｘ．ｔｘｔ”のブロック番号２は、ＨＤＦＳ５１３＃２、＃４、＃５に格納されている。
【００５４】
図６の（Ｂ）に示す説明図は、ファイルの分割方法を示している。図６の（Ｂ）では、ファイルパス“／ｆｉｌｅ／Ｘ．ｔｘｔ”とファイルパス“／ｆｉｌｅ／Ｙ．ｔｘｔ”の分割方法を示している。ネームノード５０３は、たとえば、ファイルパス“／ｆｉｌｅ／Ｘ．ｔｘｔ”にて示すファイルが入力されてきた場合、６４［ＭＢ］ごとのブロックに分割する。ネームノード５０３は、１つ目のブロックの名称を“／ｆｉｌｅ／Ｘ．ｔｘｔ−１”に設定する。同様に、ネームノード５０３は、２つ目のブロックの名称を“／ｆｉｌｅ／Ｘ．ｔｘｔ−２”に設定し、３つ目のブロックの名称を“／ｆｉｌｅ／Ｘ．ｔｘｔ−３”に設定する。
【００５５】
図６の（Ｃ）に示す説明図は、メタデータテーブル５０５の記憶内容に従った、ＨＤＦＳ５１３の記憶内容の一例を示している。たとえば、ＨＤＦＳ５１３＃１は、“／ｆｉｌｅ／Ｘ．ｔｘｔ−１”にて示されるブロックと、“／ｆｉｌｅ／Ｘ．ｔｘｔ−３”にて示されるブロックと、“／ｆｉｌｅ／Ｙ．ｔｘｔ−２”にて示されるブロックと、を記憶する。
【００５６】
図７は、ブロックとスプリットの関係を示す説明図である。ブロックとはファイルの物理的な分割単位であり、スプリットとはデータの一連の論理的な分割単位である。図７では、ファイルパスが“／ｆｉｌｅ／Ｘ．ｔｘｔ”にて示されるファイルを用いて、分割されたブロックと、分割されたスプリットの例を説明する。スプリットに分割する場合、ネームノード５０３は、“／ｆｉｌｅ／Ｘ．ｔｘｔ”にて示されるファイルのうち、１〜５行目までをスプリット１に設定し、６〜９行目までをスプリット２に設定し、１０、１１行目をスプリット３に設定する。
【００５７】
また、ネームノード５０３は、“／ｆｉｌｅ／Ｘ．ｔｘｔ”にて示されるファイルのうち、先頭の６４［ＭＢ］分のデータをブロック１に設定し、次の６４［ＭＢ］分のデータをブロック２に設定し、残余のデータをブロック３に設定する。
【００５８】
（マスタノード１０１の機能構成）
次に、マスタノード１０１の機能構成について説明する。図８は、マスタノードの機能構成例を示すブロック図である。マスタノード１０１は、受付部８０１と、検出部８０２と、生成部８０３と、第１の割当部８０４と、判断部８０５と、第２の割当部８０６と、を含む。制御部となる受付部８０１〜第２の割当部８０６は、記憶装置に記憶されたプログラムをＣＰＵ４０１が実行することにより、受付部８０１〜第２の割当部８０６の機能を実現する。記憶装置とは、具体的には、たとえば、図４に示したＲＯＭ４０２、ＲＡＭ４０３、磁気ディスク４０５などである。または、ＩＦ４０６を経由して他のＣＰＵが実行することにより、受付部８０１〜第２の割当部８０６の機能を実現してもよい。
【００５９】
受付部８０１は、Ｍａｐ処理の開始要求を受け付ける。たとえば、受付部８０１は、ダミーファイルをジョブクライアント３０１から受け付けた場合、Ｍａｐ処理の開始要求として受け付ける。ダミーファイルは、たとえば、分散処理システム１００の設計者によって予め指定されたファイル名称であってもよいし、データが空であるファイルをダミーファイルとしてもよい。受付部８０１の機能により、分散処理システム１００は、順次入力されたファイルを逐次処理するＭａｐＲｅｄｕｃｅ処理の開始の契機を検出できる。なお、受け付けた開始要求は、ＲＡＭ４０３、磁気ディスク４０５などの記憶領域に記憶される。
【００６０】
検出部８０２は、Ｍａｐ処理の処理対象となるスプリットが順次入力されるデータベース１１０に、新たなスプリットが入力されたことを検出する。たとえば、検出部８０２は、データベース１１０を一定周期で参照し、前回からのデータベースに記憶されたスプリット一覧からの差分により、スプリットが入力されたことを検出する。または、検出部８０２は、ネームノード５０３に新たなスプリットが入力されたかを定期的に問い合わせて、入力されたという応答があれば、スプリットが入力されたことを検出してもよい。なお、マスタノード１０１は、スプリットをジョブクライアント３０１から受け付けてもよいし、ファイルを受け付けて、スプリットに分割し、データベース１１０に入力してもよい。スプリットを受け付けた場合、マスタノード１０１は、ネームノード５０３の制御により、受け付けたスプリットをデータベース１１０に入力する。
【００６１】
また、検出部８０２は、受付部８０１によって開始要求が受け付けられた場合、データベース１１０に新たなスプリットが入力されたことを検出する処理の実行を開始する。たとえば、検出部８０２は、開始要求が受け付けられた場合に、データベース１１０を一定周期で参照し始める。検出部８０２の機能により、分散処理システム１００は、スプリットがデータベース１１０に入力されたタイミングにて、Ｍａｐ処理を実行することができる。なお、検出結果は、ＲＡＭ４０３、磁気ディスク４０５などの記憶領域に記憶される。
【００６２】
生成部８０３は、受付部８０１によって開始要求が受け付けられた場合、Ｍａｐ処理の処理対象に固有の識別情報を生成する。処理対象に固有の識別情報とは、処理対象を識別可能な情報である。生成部８０３は、たとえば、処理対象となるスプリット１、２…に、「１」という識別情報を生成する。また、一旦末尾情報を受け付けた後、再び開始要求が受け付けられた場合、生成部８０３は、新たな識別情報として、たとえば、「２」という識別情報を生成する。開始要求は、ジョブ単位で通知されてくるため、識別情報は、ジョブの識別情報となる。以下、識別情報を、「ジョブＩＤ」と呼称する。なお、生成した識別情報は、ＲＡＭ４０３、磁気ディスク４０５などの記憶領域に記憶される。
【００６３】
第１の割当部８０４は、検出部８０２によって新たなスプリットが入力されたことが検出された場合、通信可能なノード群のうちのいずれかのノードに新たなスプリットを処理対象とするＭａｐ処理を割り当てる。たとえば、第１の割当部８０４は、スプリット１が入力されたことが検出された場合、スレーブノード１０２＃１〜ｎのうちのスレーブノード１０２＃１に、スプリット１を処理対象とするＭａｐ処理を割り当てる。
【００６４】
また、第１の割当部８０４は、次に示す条件の場合に、ノード群のうちのいずれかのノードに、生成部８０３によって生成されたジョブＩＤとともに、新たなスプリットを処理対象とするＭａｐ処理を割り当ててもよい。条件は、検出部８０２によって新たなスプリットが入力されたことが検出された場合である。たとえば、第１の割当部８０４は、スレーブノード１０２＃１に、ジョブＩＤ：１とともに、スプリット１を処理対象とするＭａｐ処理を割り当てる。
【００６５】
判断部８０５は、検出部８０２によって新たなスプリットが入力されたことが検出された場合、新たなスプリットに、Ｍａｐ処理の処理対象となる一連のスプリットの末尾のスプリットであることを示す末尾情報が付与されているか否かを判断する。一連のスプリットは、同一のジョブとして処理する処理対象となる。
【００６６】
末尾情報は、スプリットの内容とは区別可能な値である。たとえば、計測ファイルがテキストデータである場合、末尾情報は、テキストデータの末尾に記述された、道路通行量の計測結果に登場しないタグであってもよいし、バイナリデータであってもよい。タグは、たとえば、マークアップ言語にて採用されている表記方法にしたがってもよい。たとえば、末尾情報は、“＜ＥＮＤ＞”という文字列となる。
【００６７】
判断部８０５は、たとえば、スプリット１に末尾情報が付与されているか否かを判断する。判断部８０５の機能により、順次入力されるスプリット群のうち、同一のジョブとして処理する一連のスプリットを特定することができる。なお、判断結果は、ＲＡＭ４０３、磁気ディスク４０５などの記憶領域に記憶される。
【００６８】
第２の割当部８０６は、判断部８０５が新たなスプリットに末尾情報が付与されていると判断した場合、ノード群のうちのいずれかのノードにＲｅｄｕｃｅ処理を割り当てる。Ｒｅｄｕｃｅ処理は、一連のスプリットの各々を処理対象として実行されたＭａｐ処理の処理結果の属性をもとにＭａｐ処理の処理結果を集約した１以上の処理結果を処理対象とする。
【００６９】
たとえば、検出部８０２が、スプリット１、スプリット２、スプリット３、スプリット４を順次検出し、判断部８０５が、スプリット４に末尾情報が付与されていると判断したとする。この場合、第２の割当部８０６は、スプリット１〜４を処理対象としたＭａｐ処理の処理結果の属性をもとにＭａｐ処理の処理結果を集約した１以上の処理結果を処理対象とするＲｅｄｕｃｅ処理を、スレーブノード１０２＃１、２に割り当てる。
【００７０】
また、第２の割当部８０６は、新たなスプリットに末尾情報が付与されていると判断した場合、ノード群のうちのいずれかのノードに、ジョブＩＤとともに、１以上の処理結果を処理対象とする第２の処理を割り当ててもよい。第２の割当部８０６の機能により、分散処理システム１００は、分散して処理されたＭａｐ処理の処理結果から、ジョブの出力結果を得ることができる。
【００７１】
図９は、ＭａｐＲｅｄｕｃｅ処理の具体例を示す説明図である。図９では、１４：１１〜１４：１５の計測ファイルを用いて、渋滞情報を算出する場合の具体例を示す。計測ファイル１１１は、ｋｅｙとして道路の識別情報、ｖａｌｕｅとして道路を通過した種別、を組としたレコード群が記述されているとする。また、道路を通過した種別としては、“四輪車”、“二輪車”、“歩行者”の３種類があるとする。
【００７２】
１つ目のレコードが、（道路１，四輪車）である。２つ目のレコードが、（道路２，二輪車）である。３つ目のレコードが、（道路４，四輪車）である。ジョブトラッカー５０１は、１つ目から３つ目のレコード群をスプリット１とする。また、４つ目のレコードが、（道路２，四輪車）である。５つ目のレコードが、（道路３，歩行者）である。６つ目のレコードが、（道路３，四輪車）である。ジョブトラッカー５０１は、４つ目から６つ目のレコード群をスプリット２とする。また、７つ目のレコードが、（道路４，二輪車）である。８つ目のレコードが、（道路２，四輪車）である。９つ目のレコードが、（道路５，四輪車）である。ジョブトラッカー５０１は、７つ目から９つ目のレコード群をスプリット３とする。
【００７３】
また、Ｍａｐ処理は、Ｖａｌｕｅフィールドに“四輪車”が格納されているレコードを抽出する処理である。Ｒｅｄｕｃｅ処理は、道路ごとの“四輪車”を計数する処理である。Ｍａｐ処理とＲｅｄｕｃｅ処理を行うことにより、分散処理システム１００は、道路ごとの渋滞情報を算出することになる。また、分散処理システム１００は、Ｍａｐ処理とＲｅｄｕｃｅ処理の間に、シャッフル＆ソート処理を実行する。
【００７４】
ジョブスケジューラ５０２がデータベース１１０にスプリット１が入力されたことを検出した場合、ジョブトラッカー５０１は、スプリット１を処理対象とするＭａｐ処理１をスレーブノード１０２＃１に割り当てる。また、ジョブスケジューラ５０２がスプリット２やスプリット３が入力されたことを検出した場合、ジョブトラッカー５０１は、スプリット２、スプリット３を処理対象とするＭａｐ処理２、Ｍａｐ処理３をスレーブノード１０２＃１に割り当てる。なお、Ｍａｐ処理は、独立したスプリットに対して処理を行うため、それぞれ独立して動作することが可能である。
【００７５】
Ｍａｐ処理１は、（道路１，四輪車）、（道路２，二輪車）、（道路４，四輪車）のうち、（道路１，四輪車）、（道路４，四輪車）を抽出する。また、Ｍａｐ処理２は、（道路２，四輪車）、（道路３，歩行者）、（道路３，四輪車）のうち、（道路２，四輪車）、（道路３，四輪車）を抽出する。また、Ｍａｐ処理３は、（道路４，二輪車）、（道路２，四輪車）、（道路５，四輪車）のうち、（道路２，四輪車）、（道路５，四輪車）を抽出する。Ｍａｐ処理１〜３は、処理が完了すると、タスクトラッカー５１１を経由して、ジョブトラッカー５０１に処理が完了したことを通知する。
【００７６】
同様に、ジョブトラッカー５０１は、１４：１２の計測ファイル９０１を分割したスプリット群を処理対象とするＭａｐ処理４〜６をスレーブノード１０２＃２に割り当てる。Ｍａｐ処理４は、計測ファイル９０１を分割したスプリットのうち、（道路１，四輪車）、（道路４，四輪車）を抽出する。Ｍａｐ処理５は、計測ファイル９０１を分割したスプリットのうち、（道路５，四輪車）を抽出する。Ｍａｐ処理６は、計測ファイル９０１を分割したスプリットのうち、（道路１，四輪車）、（道路６，四輪車）を抽出する。同様に、ジョブトラッカー５０１は、１４：１５の計測ファイル１１３を分割したスプリット群を処理対象とするＭａｐ処理Ｌをスレーブノード１０２＃ｎに割り当てる。Ｌは、１以上の整数である。
【００７７】
Ｍａｐ処理１〜Ｌの処理が完了した場合、ジョブトラッカー５０１は、Ｍａｐ処理１〜Ｌの処理結果を処理対象とするシャッフル＆ソート処理１〜Ｍをスレーブノード１０２＃１〜ｎに実行させる。Ｍは１以上の整数である。たとえば、ジョブトラッカー５０１は、ｋｅｙフィールドが“道路１”、または“道路２”となるレコードを処理対象とするシャッフル＆ソート処理１をスレーブノード１０２＃１に割り当てる。ジョブトラッカー５０１は、ｋｅｙフィールドが“道路１”、または“道路２”となったレコードをスレーブノード１０２＃１に送信するように、スレーブノード１０２＃１以外のスレーブノード１０２に指示する。同様に、ジョブトラッカー５０１は、ｋｅｙフィールドが“道路３”、または“道路４”となるレコードを処理対象とするシャッフル＆ソート処理２をスレーブノード１０２＃２に割り当てる。
【００７８】
たとえば、シャッフル＆ソート処理１は、処理結果の属性の一つであるｋｅｙフィールドの“道路１”に関して、（道路１，（四輪車，四輪車，四輪車））のように集約する。また、シャッフル＆ソート処理１は、“道路２”に関して、（道路２，（四輪車，四輪車））のように集約する。また、シャッフル＆ソート処理２は、“道路３”に関して、（道路３，（四輪車））のように集約する。また、シャッフル＆ソート処理２は、“道路４”に関して、（道路４，（四輪車，四輪車））のように集約する。シャッフル＆ソート処理は、シャッフル＆ソート処理を実行するスレーブノード１０２同士が協調して動作する。また、シャッフル＆ソート処理は、Ｍａｐ処理が全て完了した後に行われる。
【００７９】
シャッフル＆ソート処理が完了した場合、ジョブトラッカー５０１は、シャッフル＆ソート処理の処理結果を処理対象とするＲｅｄｕｃｅ処理１〜Ｎをスレーブノード１０２＃１〜ｎに実行させる。Ｎは、１以上の整数である。たとえば、ジョブトラッカー５０１は、“道路１”に対して集約した処理結果を処理対象とするＲｅｄｕｃｅ処理１をスレーブノード１０２＃１に割り当てる。また、ジョブトラッカー５０１は、“道路２”に対して集約した処理結果を処理対象とするＲｅｄｕｃｅ処理２をスレーブノード１０２＃１に割り当てる。同様に、ジョブトラッカー５０１は、“道路３”に対して集約した処理結果を処理対象とするＲｅｄｕｃｅ処理３と、“道路４”に対して集約した処理結果を処理対象とするＲｅｄｕｃｅ処理４とを、スレーブノード１０２＃２に割り当てる。
【００８０】
たとえば、Ｒｅｄｕｃｅ処理１は、（道路１，（四輪車，四輪車，四輪車））から、“四輪車”の個数を計数し、（道路１，３）を出力する。また、Ｒｅｄｕｃｅ処理２は、（道路２，（四輪車，四輪車））から、“四輪車”の個数を計数し、（道路２，２）を出力する。また、Ｒｅｄｕｃｅ処理３は、（道路３，（四輪車））から、“四輪車”の個数を計数し、（道路３，１）を出力する。また、Ｒｅｄｕｃｅ処理４は、（道路４，（四輪車，四輪車））から、“四輪車”の個数を計数し、（道路４，２）を出力する。なお、Ｒｅｄｕｃｅ処理は、独立したスプリットに対して処理を行うため、それぞれ独立して動作することが可能である。
【００８１】
次に、ＭａｐＲｅｄｕｃｅ処理が実行されるタイミングについて図１０と図１１を用いて説明する。図１０では、スプリットに末尾情報が付与されていなく、順次入力されたスプリットを一度に処理する場合のＭａｐＲｅｄｕｃｅ処理が実行されるタイミングについて説明する。図１１では、実施の形態１の特徴となる動作である、順次入力されたスプリットを逐次実行する場合のＭａｐＲｅｄｕｃｅ処理が実行されるタイミングについて説明する。
【００８２】
以下、図１０と図１１に共通する説明を行う。図１０と図１１では、時刻０から時刻８ｔまでの時間帯を示しており、時刻０〜時刻８ｔの時間間隔は等間隔とし、１つの時間間隔をｔとする。また、Ｍａｐ処理の処理時間を２ｔとし、シャッフル＆ソート処理とＲｅｄｕｃｅ処理の処理時間を、１ｔとする。また、Ｍａｐ処理、シャッフル＆ソート処理、Ｒｅｄｕｃｅ処理は、スレーブノード１０２＃１、２にて実行されるとする。また、計測ファイル１１１が分割されたスプリット１がデータベース１１０に入力される時刻を時刻０とし、計測ファイル１１２が分割されたスプリット２がデータベース１１０に入力される時刻を時刻ｔとする。また、計測ファイル１１３が分割されたスプリット３がデータベース１１０に入力される時刻を時刻２ｔとし、計測ファイル１１３が分割されたスプリット４がデータベース１１０に入力される時刻を時刻３ｔとする。
【００８３】
また、１４：１１から１４：１５の計測ファイルを用いて渋滞情報を算出するというジョブＩＤ：１が付与されたジョブがジョブクライアント３０１に登録されているものとする。また、図１０および図１１には時刻１４：１１〜時刻１４：１３の計測ファイルに対する処理を図示していないが、スレーブノード１０２＃１〜ｎのいずれかのスレーブノード１０２にて処理しているものとする。
【００８４】
図１０は、順次入力されたスプリットを一度に処理するＭａｐＲｅｄｕｃｅ処理の処理例を示す説明図である。図１０に示す分散処理システム１００は、時刻４ｔになり、１４：１１から１４：１５の計測ファイルが分割されたスプリットが揃った時点にて、ジョブＩＤ：１のジョブを実行開始する。時刻４ｔにて、ジョブトラッカー５０１は、計測ファイル１１１のスプリット１を処理対象とするＭａｐ処理１と、計測ファイル１１３のスプリット３を処理対象とするＭａｐ処理３をスレーブノード１０２＃１に割り当てる。さらに、ジョブトラッカー５０１は、計測ファイル１１２のスプリット２を処理対象とするＭａｐ処理２と、計測ファイル１１３のスプリット４を処理対象とするＭａｐ処理４をスレーブノード１０２＃２に割り当てる。
【００８５】
時刻４ｔから時刻５ｔにかけて、スレーブノード１０２＃１は、Ｍａｐ処理１を実行する。Ｍａｐ処理１の完了後、時刻６ｔから時刻７ｔにかけて、スレーブノード１０２＃１は、Ｍａｐ処理３を実行する。同様に、時刻４ｔから時刻５ｔにかけて、スレーブノード１０２＃２は、Ｍａｐ処理２を実行する。Ｍａｐ処理２の完了後、時刻６ｔから時刻７ｔにかけて、スレーブノード１０２＃１は、Ｍａｐ処理４を実行する。
【００８６】
Ｍａｐ処理１〜４が完了した後、時刻８ｔにて、ジョブトラッカー５０１は、Ｍａｐ処理結果１とＭａｐ処理結果３を処理対象とするシャッフル＆ソート処理１をスレーブノード１０２＃１に割り当てる。同様に、時刻８ｔにて、ジョブトラッカー５０１は、Ｍａｐ処理結果２とＭａｐ処理結果４を処理対象とするシャッフル＆ソート処理２をスレーブノード１０２＃２に割り当てる。
【００８７】
時刻８ｔにて、スレーブノード１０２＃１は、シャッフル＆ソート処理１を実行する。シャッフル＆ソート処理１が完了後、時刻９ｔにて、スレーブノード１０２＃１は、Ｒｅｄｕｃｅ処理１を実行する。同様に、時刻８ｔにて、スレーブノード１０２＃２は、シャッフル＆ソート処理２を実行する。シャッフル＆ソート処理２が完了後、時刻９ｔにて、スレーブノード１０２＃２は、Ｒｅｄｕｃｅ処理２を実行する。このように、順次入力されたファイルを一度に処理するＭａｐＲｅｄｕｃｅ処理の場合、ジョブＩＤ：１の処理時間は９ｔとなる。
【００８８】
図１１は、順次入力されたスプリットを逐次処理するＭａｐＲｅｄｕｃｅ処理の具体例を示す説明図である。図１１に示す分散処理システム１００は、時刻０にて、ジョブＩＤ：１のジョブの処理対象となる、計測ファイル１１１のスプリット１がデータベース１１０に入力された時点にて、ジョブＩＤ：１のジョブを実行開始する。スプリット１がデータベース１１０に入力された場合、ジョブトラッカー５０１は、スプリット１を処理対象とするＭａｐ処理１をスレーブノード１０２＃１に割り当てる。時刻ｔから時刻２ｔにかけて、スレーブノード１０２＃１は、Ｍａｐ処理１を実行する。
【００８９】
時刻ｔにて、計測ファイル１１２が分割されたスプリット２が入力された場合、ジョブトラッカー５０１は、スプリット２を処理対象とするＭａｐ処理２をスレーブノード１０２＃２に割り当てる。時刻２ｔから時刻３ｔにかけて、スレーブノード１０２＃２は、Ｍａｐ処理２を実行する。
【００９０】
時刻２ｔにて、計測ファイル１１３が分割されたスプリット３が入力された場合、ジョブトラッカー５０１は、スプリット３を処理対象とするＭａｐ処理３をスレーブノード１０２＃１に割り当てる。また、時刻３ｔにて、計測ファイル１１３が分割されたスプリット４が入力された場合、ジョブトラッカー５０１は、計測ファイル１１３のスプリット４を処理対象とするＭａｐ処理４をスレーブノード１０２＃２に割り当てる。時刻３ｔから時刻４ｔにかけて、スレーブノード１０２＃１は、Ｍａｐ処理３を実行する。Ｍａｐ処理２の完了後、時刻４ｔから時刻５ｔにかけて、スレーブノード１０２＃２は、Ｍａｐ処理４を実行する。
【００９１】
Ｍａｐ処理１〜４が完了した後、時刻６ｔにて、ジョブトラッカー５０１は、Ｍａｐ処理結果１とＭａｐ処理結果３を処理対象とするシャッフル＆ソート処理１をスレーブノード１０２＃１に割り当てる。同様に、時刻６ｔにて、ジョブトラッカー５０１は、Ｍａｐ処理結果２とＭａｐ処理結果４を処理対象とするシャッフル＆ソート処理２をスレーブノード１０２＃２に割り当てる。
【００９２】
時刻６ｔにて、スレーブノード１０２＃１は、シャッフル＆ソート処理１を実行する。シャッフル＆ソート処理１が完了後、時刻７ｔにて、スレーブノード１０２＃１は、Ｒｅｄｕｃｅ処理１を実行する。同様に、時刻６ｔにて、スレーブノード１０２＃２は、シャッフル＆ソート処理２を実行する。シャッフル＆ソート処理２が完了後、スレーブノード１０２＃２は、Ｒｅｄｕｃｅ処理２を実行する。このように、入力されたファイルを逐次処理するＭａｐＲｅｄｕｃｅ処理の場合、ジョブＩＤ：１の処理時間は７ｔとなる。図１０の動作と比較して、図１１の動作では、Ｍａｐ処理を先行して処理することができるため、ジョブにかかる処理の時間短縮が可能となる。続けて、図１１にて示した動作を行うＭａｐＲｅｄｕｃｅ処理を図１２、図１３を用いて説明する。
【００９３】
図１２および図１３は、ＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その１）および（その２）である。ＭａｐＲｅｄｕｃｅ処理は、ジョブの実行要求を受け付けた場合に実行する処理である。また、図１２と図１３では、ＭａｐＲｅｄｕｃｅ処理を実行するスレーブノード１０２がスレーブノード１０２＃１、２の２台にて実行する場合を想定して説明する。また、マスタノード１０１では、ジョブトラッカー５０１とジョブスケジューラ５０２が連携して、ＭａｐＲｅｄｕｃｅ処理を実行する。また、スレーブノード１０２＃１、２では、タスクトラッカー５１１と、Ｍａｐタスク５１４と、Ｒｅｄｕｃｅタスク５１５が連携して、ＭａｐＲｅｄｕｃｅ処理を実行する。
【００９４】
図１２に示すフローチャートにて、ジョブトラッカー５０１は、準備処理を実行する（ステップＳ１２０１）。準備処理の詳細は、図１４にて後述する。準備処理の実行後、ジョブトラッカー５０１とジョブスケジューラ５０２は、初期化処理を実行する（ステップＳ１２０２）。初期化処理の詳細は、図１５にて後述する。初期化処理の終了後、ジョブスケジューラ５０２は、スプリットがＨＤＦＳに入力されたことを検出したか否かを判断する（ステップＳ１２０３）。入力されたスプリットがない場合（ステップＳ１２０３：Ｎｏ）、ジョブスケジューラ５０２は、一定時間経過後、ステップＳ１２０３の処理を再び実行する。
【００９５】
入力されたスプリットがある場合（ステップＳ１２０３：Ｙｅｓ）、ジョブスケジューラ５０２は、Ｍａｐタスク生成処理を実行する（ステップＳ１２０４）。Ｍａｐタスク生成処理の詳細は、図１６にて後述する。Ｍａｐタスク生成処理の終了後、ジョブトラッカー５０１は、Ｍａｐタスク割当処理を実行する（ステップＳ１２０５）。Ｍａｐタスク割当処理の詳細は、図１７にて後述する。また、Ｍａｐタスクが割り当てられたスレーブノード１０２は、図１３にて示す処理に移行する。
【００９６】
たとえば、ステップＳ１２０５の１回目の処理にて、Ｍａｐタスク５１４がスレーブノード１０２＃１に割り当てられた場合、タスクトラッカー５１１＃１とＭａｐタスク５１４＃１は、図１３に示すステップＳ１３０１の処理を実行する。また、ステップＳ１２０５の２回目の処理にて、Ｍａｐタスク５１４がスレーブノード１０２＃２に割り当てられた場合、タスクトラッカー５１１＃２とＭａｐタスク５１４＃２は、図１３に示すステップＳ１３０３の処理を実行する。
【００９７】
Ｍａｐタスク割当処理の終了後、ジョブスケジューラ５０２は、末尾情報が付与されたスプリットを検出したか否かを判断する（ステップＳ１２０６）。末尾情報が付与されたスプリットを検出したか否かを判断する例としては、たとえば、後述するステップＳ１６０５の処理によって末尾情報が付与されたスプリットを検出したことを記憶しているか否かを判断することである。末尾情報が付与されたスプリットを検出していない場合（ステップＳ１２０６：Ｎｏ）、ジョブスケジューラ５０２は、ステップＳ１２０３の処理に移行する。末尾情報が付与されたスプリットを検出した場合（ステップＳ１２０６：Ｙｅｓ）、ジョブトラッカー５０１は、図１３に示すステップＳ１３０５の処理に移行する。なお、ステップＳ１２０６：Ｙｅｓの場合、ジョブスケジューラ５０２は、初期化処理内の、後述するステップＳ１５０３が行われるまで、内部キューを一定時間おきに参照する。
【００９８】
次に、図１３に示すフローチャートにて、タスクトラッカー５１１＃１とＭａｐタスク５１４＃１は、Ｍａｐ処理を実行する（ステップＳ１３０１）。Ｍａｐ処理の詳細は、図１８にて後述する。Ｍａｐ処理の終了後、タスクトラッカー５１１＃１は、Ｍａｐ処理の完了をマスタノード１０１に通知する（ステップＳ１３０２）。同様に、タスクトラッカー５１１＃２とＭａｐタスク５１４＃２は、Ｍａｐ処理を実行する（ステップＳ１３０３）。Ｍａｐ処理の終了後、タスクトラッカー５１１＃２は、Ｍａｐ処理の完了をマスタノード１０１に通知する（ステップＳ１３０４）。
【００９９】
ステップＳ１２０６の終了後、ジョブトラッカー５０１は、Ｍａｐ処理の完了を受け付けたか否かを判断する（ステップＳ１３０５）。Ｍａｐ処理の完了を受け付けていない場合（ステップＳ１３０５：Ｎｏ）、ジョブトラッカー５０１は、一定時間経過後、ステップＳ１３０５の処理を再び実行する。Ｍａｐ処理の完了を受け付けた場合（ステップＳ１３０５：Ｙｅｓ）、ジョブトラッカー５０１は、Ｍａｐ処理が完了したスレーブノード１０２に対して、Ｍａｐ処理結果の送信を指示する（ステップＳ１３０６）。
【０１００】
Ｍａｐ処理結果の送信指示を受け付けたタスクトラッカー５１１＃１は、Ｍａｐ処理結果をスレーブノード１０２＃２に送信する（ステップＳ１３０７）。このとき、送信対象となるＭａｐ処理結果は、スレーブノード１０２＃２にて実行される予定のシャッフル＆ソート処理およびＲｅｄｕｃｅ処理の処理対象となるデータである。同様に、Ｍａｐ処理結果の送信指示を受け付けたタスクトラッカー５１１＃２は、Ｍａｐ処理結果をスレーブノード１０２＃１に送信する（ステップＳ１３０８）。
【０１０１】
ステップＳ１３０６の実行終了後、ジョブトラッカー５０１は、Ｍａｐ処理の完了を同一ジョブＩＤの全てのＭａｐ処理から受け付けたか否かを判断する（ステップＳ１３０９）。同一ジョブＩＤのＭａｐ処理にて、まだ完了を受け付けていないＭａｐ処理がある場合（ステップＳ１３０９：Ｎｏ）、ステップＳ１３０５の処理に移行する。同一ジョブＩＤの全てのＭａｐ処理から完了を受け付けた場合（ステップＳ１３０９：Ｙｅｓ）、ジョブトラッカー５０１は、該当のジョブＩＤのシャッフル＆ソート処理の実行をジョブトラッカー５０１に指示する（ステップＳ１３１０）。ステップＳ１３１０の終了後、ジョブトラッカー５０１は、ＭａｐＲｅｄｕｃｅ処理を終了する。
【０１０２】
シャッフル＆ソート処理の実行指示を受け付けたタスクトラッカー５１１＃１は、Ｒｅｄｕｃｅタスク５１５＃１にシャッフル＆ソート処理を実行させる（ステップＳ１３１１）。シャッフル＆ソート処理の詳細は、図１９にて後述する。シャッフル＆ソート処理の実行後、Ｒｅｄｕｃｅタスク５１５＃１は、Ｒｅｄｕｃｅ処理を実行する（ステップＳ１３１２）。Ｒｅｄｕｃｅ処理の詳細は、図２０にて後述する。Ｒｅｄｕｃｅ処理の終了後、タスクトラッカー５１１＃１は、ＭａｐＲｅｄｕｃｅ処理を終了する。なお、Ｒｅｄｕｃｅタスク５１５＃１も、Ｒｅｄｕｃｅ処理終了後に、処理を終了する。
【０１０３】
また、シャッフル＆ソート処理の実行指示を受け付けたタスクトラッカー５１１＃２は、Ｒｅｄｕｃｅタスク５１５＃２にシャッフル＆ソート処理を実行させる（ステップＳ１３１３）。シャッフル＆ソート処理の実行後、Ｒｅｄｕｃｅタスク５１５＃２は、Ｒｅｄｕｃｅ処理を実行する（ステップＳ１３１４）。Ｒｅｄｕｃｅ処理の終了後、タスクトラッカー５１１＃２は、ＭａｐＲｅｄｕｃｅ処理を終了する。ＭａｐＲｅｄｕｃｅ処理を実行することにより、分散処理システム１００は、ジョブの実行に関して、入力されたスプリットを検出した時に順次Ｍａｐ処理を実行することができ、ジョブの実行にかかる処理時間を短縮することができる。
【０１０４】
次に、図１４〜図２０にて、ＭａｐＲｅｄｕｃｅ処理にて呼び出される処理のフローチャートを説明する。図１４〜図２０では、実行主体が１つのソフトウェアによる装置である場合、表示の簡略化のため、各ステップ内の実行主体の表記を省略する。
【０１０５】
図１４は、準備処理手順の一例を示すフローチャートである。準備処理は、ジョブを実行する前に実行しておく処理である。また、準備処理は、マスタノード１０１のジョブトラッカー５０１が実行する。
【０１０６】
ジョブトラッカー５０１は、ジョブクライアント３０１から、“プログラム名＋ダミー入力ファイル名”となるジョブ実行要求を受け付ける（ステップＳ１４０１）。次に、ジョブトラッカー５０１は、ジョブＩＤを生成する（ステップＳ１４０２）。続けて、ジョブトラッカー５０１は、生成したジョブＩＤをジョブクライアント３０１に通知する（ステップＳ１４０３）。ジョブトラッカー５０１は、ジョブのダミー入力スプリットをパラメータとして、ＭａｐＲｅｄｕｃｅプログラム５２１を開始する（ステップＳ１４０４）。ステップＳ１４０４の実行完了後、ジョブトラッカー５０１は、準備処理を終了する。準備処理を実行することにより、分散処理システム１００は、ジョブの実行を開始できる。
【０１０７】
また、ステップＳ１４０１の処理にて、“プログラム名＋実ファイル名”となるジョブ実行要求を受け付けた場合、分散処理システム１００は、図１０にて示したＭａｐＲｅｄｕｃｅ処理を実行してもよい。この場合、ジョブトラッカー５０１は、ステップＳ１４０３の実行後、実ファイルから、入力スプリットを算出する。具体的な算出処理として、ジョブトラッカー５０１は、実ファイルを６４［ＭＢ］ごとに分割して、入力スプリットを算出する。また、分散処理システム１００は、ステップＳ１２０３の処理を行わず、Ｙｅｓのルートを処理する。また、ジョブトラッカー５０１は、ステップＳ１２０６の処理を、「実ファイル名が分割されたスプリットを全て読み込んだか？」とする。
【０１０８】
また、ステップＳ１４０１の処理にて、“プログラム名＋実ファイル名＋ダミー入力ファイル名”となるジョブ実行要求を受け付けた場合、分散処理システム１００は、既に入力済みのスプリットに対して図１０にて示したＭａｐＲｅｄｕｃｅ処理を実行してもよい。続けて、分散処理システム１００は、これから入力されてくるスプリットに対して図１０にて示したＭａｐＲｅｄｕｃｅ処理を実行してもよい。
【０１０９】
このような処理を行う場合、ジョブトラッカー５０１は、ステップＳ１４０３の実行後、実ファイルから、入力スプリット数を算出する。また、分散処理システム１００は、ステップＳ１２０３の処理を行わず、Ｙｅｓのルートを処理する。また、ジョブトラッカー５０１は、ステップＳ１２０６の処理を、「実ファイル名が分割されたスプリットを全て読み込んだか」とする。全て読み込んだ後、ジョブトラッカー５０１は、ステップＳ１２０３の処理を行う。さらに、ジョブトラッカー５０１は、ステップＳ１２０６の処理を、「末尾情報が付与されたスプリットを検出したか？」とする。
【０１１０】
図１５は、初期化処理手順の一例を示すフローチャートである。初期化処理は、ジョブの初期化を行う処理である。また、初期化処理は、マスタノード１０１のジョブトラッカー５０１と、ジョブスケジューラ５０２とが連携して実行する。ジョブトラッカー５０１は、ジョブクライアント３０１から、ジョブの初期化要求を受け付ける（ステップＳ１５０１）。次に、ジョブトラッカー５０１は、初期化したジョブを内部キューに格納する（ステップＳ１５０２）。ステップＳ１５０３の処理完了後、ジョブトラッカー５０１は、初期化処理を終了する。
【０１１１】
ジョブスケジューラ５０２は、内部キューにジョブがあるか否かを一定周期にて判断している。ステップＳ１５０２の実行後、ジョブスケジューラ５０２は、内部キューからジョブを取り出す（ステップＳ１５０３）。ステップＳ１５０３の処理完了後、ジョブスケジューラ５０２は、初期化処理を終了する。初期化処理を実行することにより、分散処理システム１００は、実行要求のあったジョブ順に処理を実行することができる。
【０１１２】
図１６は、Ｍａｐタスク生成処理手順の一例を示すフローチャートである。Ｍａｐタスク生成処理は、スレーブノード１０２に割り当てるＭａｐタスク５１４を生成する処理である。また、Ｍａｐタスク生成処理は、ジョブスケジューラ５０２が実行する。
【０１１３】
ジョブスケジューラ５０２は、ＨＤＦＳに入力されたスプリットを取得する（ステップＳ１６０１）。次に、ジョブスケジューラ５０２は、スプリットを処理対象とする１つのＭａｐタスク５１４を生成する（ステップＳ１６０２）。続いて、ジョブスケジューラ５０２は、生成したＭａｐタスク５１４に、ジョブＩＤを付与する（ステップＳ１６０３）。次に、ジョブスケジューラ５０２は、スプリットに末尾情報が付与されているか否かを判断する（ステップＳ１６０４）。
【０１１４】
末尾情報が付与されている場合（ステップＳ１６０４：Ｙｅｓ）、ジョブスケジューラ５０２は、末尾情報が付与されたスプリットを検出したことを記憶する（ステップＳ１６０５）。ステップＳ１６０５の処理完了後、または、末尾情報が付与されていない場合（ステップＳ１６０４：Ｎｏ）、ジョブスケジューラ５０２は、Ｍａｐタスク生成処理を終了する。Ｍａｐタスク生成処理を実行することにより、分散処理システム１００は、スレーブノード１０２に割り当てるＭａｐタスク５１４を生成できる。
【０１１５】
図１７は、Ｍａｐタスク割当処理手順の一例を示すフローチャートである。Ｍａｐタスク割当処理は、スレーブノード１０２にＭａｐタスク５１４を割り当てる処理である。また、Ｍａｐタスク割当処理は、ジョブスケジューラ５０２によるＭａｐタスク５１４の生成後、ジョブトラッカー５０１が実行する。
【０１１６】
ジョブトラッカー５０１は、タスクトラッカー５１１から受け付けたハートビート通信を参照して、Ｍａｐタスク５１４の割当先を決定する（ステップＳ１７０１）。ハートビート通信は、各スレーブノード１０２にて新たに実行可能なタスク数を含む。たとえば、あるスレーブノード１０２が、実行可能なタスク数の最大が５であり、Ｍａｐタスク５１４およびＲｅｄｕｃｅタスク５１５が計３つ実行中であるとする。この場合、あるスレーブノード１０２は、ハートビート通信に、新たに実行可能なタスク数が２であるという情報を含めてマスタノード１０１に通知する。ジョブトラッカー５０１は、スレーブノード１０２＃１〜ｎのうち、たとえば、新たに実行可能なタスク数が最も大きいスレーブノード１０２を、Ｍａｐタスク５１４の割当先に決定する。
【０１１７】
ステップＳ１７０１の処理完了後、ジョブトラッカー５０１は、決定した割当先に、Ｍａｐタスク５１４を割り当てる（ステップＳ１７０２）。ステップＳ１７０２の処理完了後、ジョブトラッカー５０１は、Ｍａｐタスク割当処理を終了する。Ｍａｐタスク割当処理を実行することにより、分散処理システム１００は、Ｍａｐ処理を各スレーブノード１０２に分散することができる。
【０１１８】
図１８〜図２０では、スレーブノード１０２にて行われる処理についてのフローチャートを示す。図１８〜図２０にて示すフローチャートは、スレーブノード１０２＃１〜ｎのうちのいずれのスレーブノード１０２も行う。以下では、説明の簡略化のため、スレーブノード１０２＃１が実行する場合を例にして説明する。
【０１１９】
図１８は、Ｍａｐ処理手順の一例を示すフローチャートである。Ｍａｐ処理は、処理対象となるスプリットから、（ｋｅｙ，Ｖａｌｕｅ）を生成する処理である。また、Ｍａｐ処理は、タスクトラッカー５１１＃１と、スレーブノード１０２＃１に割り当てられたＭａｐタスク５１４＃１とが連携して実行する。
【０１２０】
タスクトラッカー５１１＃１は、ジョブプログラムをＨＤＦＳからスレーブノード１０２＃１のローカル記憶領域にコピーする（ステップＳ１８０１）。次に、タスクトラッカー５１１＃１は、スプリットをＨＤＦＳから、スレーブノード１０２＃１のローカル記憶領域にコピーする（ステップＳ１８０２）。ステップＳ１８０２の処理完了後、タスクトラッカー５１１＃１は、Ｍａｐ処理を終了する。
【０１２１】
続けて、Ｍａｐタスク５１４＃１は、スプリットを処理対象として、ジョブプログラム内のＭａｐ処理を実行する（ステップＳ１８０３）。ステップＳ１８０３の処理完了後、Ｍａｐタスク５１４＃１は、Ｍａｐ処理を終了する。Ｍａｐ処理を実行することにより、分散処理システム１００は、分割されたスプリットに対して、他のスプリットとは独立してジョブの処理を実行することができる。
【０１２２】
図１９は、シャッフル＆ソート処理手順の一例を示すフローチャートである。シャッフル＆ソート処理は、Ｍａｐ処理の処理結果を処理対象として、１つ以上の処理結果に集約する処理である。また、シャッフル＆ソート処理は、スレーブノード１０２＃１に割り当てられたＲｅｄｕｃｅタスク５１５＃１が実行する。
【０１２３】
Ｒｅｄｕｃｅタスク５１５＃１は、各Ｍａｐタスクの処理結果となるレコードに含まれるジョブＩＤが同一となるレコードを処理対象に設定する（ステップＳ１９０１）。次に、Ｒｅｄｕｃｅタスク５１５＃１は、処理対象を、Ｋｅｙフィールドの値が同一のレコード同士で集約する（ステップＳ１９０２）。続けて、Ｒｅｄｕｃｅタスク５１５＃１は、Ｋｅｙフィールドをもとに、並び替える（ステップＳ１９０３）。次に、Ｒｅｄｕｃｅタスク５１５＃１は、処理結果を、Ｒｅｄｕｃｅ処理に送信する（ステップＳ１９０４）。ステップＳ１９０４の処理完了後、Ｒｅｄｕｃｅタスク５１５＃１は、シャッフル＆ソート処理を終了する。シャッフル＆ソート処理の処理結果を用いることにより、スレーブノード１０２は、次に実行するＲｅｄｕｃｅ処理を実行しやすくする。
【０１２４】
図２０は、Ｒｅｄｕｃｅ処理手順の一例を示すフローチャートである。Ｒｅｄｕｃｅ処理は、集約された処理結果を処理対象として、ジョブの処理結果を出力する処理である。また、Ｒｅｄｕｃｅ処理は、Ｒｅｄｕｃｅタスク５１５＃１が実行する。
【０１２５】
Ｒｅｄｕｃｅタスク５１５は、Ｋｅｙフィールドの値が同一となるレコード群を処理対象として、ジョブプログラム内のＲｅｄｕｃｅ処理を実行する（ステップＳ２００１）。次に、Ｒｅｄｕｃｅタスク５１５は、Ｒｅｄｕｃｅ処理の処理結果を出力する（ステップＳ２００２）。ステップＳ２００２の処理完了後、Ｒｅｄｕｃｅタスク５１５は、Ｒｅｄｕｃｅ処理を終了する。Ｒｅｄｕｃｅ処理を実行することにより、分散処理システム１００は、ジョブクライアント３０１にジョブの実行を要求した装置に出力結果を提示することができる。
【０１２６】
以上説明したように、実施の形態１にかかる割当装置によれば、データベース１１０に順次入力されるスプリットに対してＭａｐ処理を逐次割り当て、ジョブを区切る末尾情報が付いたスプリットまでのＭａｐ処理完了後にシャッフル処理に移行する。スプリットに対して逐次Ｍａｐ処理を割り当てることと、末尾情報が付与されたスプリットまでシャッフル＆ソート処理の実行を待つことにより、分散処理システム１００は、同一ジョブのＭａｐ処理の実行時間帯の集中を避けることができる。
【０１２７】
たとえば、分散処理システム１００は、Ｍａｐ処理の実行時間帯の集中を避け、Ｍａｐ処理を先行して実行することにより、Ｍａｐ処理の実行待ちの時間が短縮されるため、同一ジョブの処理時間を短縮することができる。また、同一ジョブのＭａｐ処理の実行時間帯が集中する場合、データベース１１０へのアクセス負荷が増大し、スプリットを取得するのに時間がかかるため、Ｍａｐ処理が遅延してしまう。実施の形態１にかかる分散処理システム１００は、同一ジョブのＭａｐ処理の実行時間帯の集中を避けることができるため、アクセス負荷が増大せず、Ｍａｐ処理の遅延を抑制できる。また、分散処理システム１００は、現在のジョブに含まれるスプリットの個数を取得しなくとも、正しい処理結果を得ることができる。
【０１２８】
また、実施の形態１にかかる割当装置によれば、開始要求を受け付けた場合、新たなスプリットが入力されたことを検出する処理の実行を開始してもよい。これにより、分散処理システム１００は、開始要求となるダミーファイルを受け付けた場合に図１１にて示したＭａｐＲｅｄｕｃｅ処理を行い、実ファイルを受け付けた場合に図１０にて示したＭａｐＲｅｄｕｃｅ処理を行う、といった処理の切り替えが行える。図１０にて示したＭａｐＲｅｄｕｃｅ処理では、一度にＭａｐ処理を行うため、Ｍａｐ処理の処理結果を各スレーブノード１０２が保持する時間を短くすることができる。
【０１２９】
たとえば、１日ごとの計測ファイルを１か月分用いて処理するジョブがあった場合、図１１に示したＭａｐＲｅｄｕｃｅ処理は、初めの１日目の計測ファイルに対するＭａｐ処理の処理結果を、１か月分保持し続けることになる。このようなジョブを実行する場合、分散処理システム１００は、初めに実スプリットを受け付けることにより、図１０にて示したＭａｐＲｅｄｕｃｅ処理を実行できる。また、開始要求を受け付けることにより、これからＭａｐ処理の割当を行うことが事前にわかるため、割当装置は、割当の準備をすることができる。たとえば、データベース１１０がＨＤＦＳであれば、タスクが割り当てられていないスレーブノード１０２があるか否かを事前に調べておくことができる。
【０１３０】
また、分散処理システム１００は、入力済みのスプリットに対して図１０にて示したＭａｐＲｅｄｕｃｅ処理を行い、続けて、これから入力されるスプリットに対して図１１にて示したＭａｐＲｅｄｕｃｅ処理を行ってもよい。たとえば、１日ごとの計測ファイルを１か月分用いて処理するジョブがあり、２９日目にてジョブを開始する場合を想定する。このとき、分散処理システム１００は、１〜２９日目の計測ファイルに対して図１０にて示したＭａｐＲｅｄｕｃｅ処理を行う。次に、分散処理システム１００は、３０日目の計測ファイルが入力されるのを待ち、入力されたら計測ファイルが分割されたスプリットに対して図１１にて示したＭａｐＲｅｄｕｃｅ処理を行う。
【０１３１】
また、実施の形態１にかかる割当装置によれば、ジョブＩＤとＭａｐ処理をスレーブノード１０２に割り当てるとともに、ジョブＩＤとＲｅｄｕｃｅ処理をスレーブノード１０２に割り当ててもよい。これにより、ジョブトラッカー５０１は、スレーブノード１０２内に記憶されているＭａｐ処理の処理結果が複数のジョブ分存在する場合、集約対象となるスプリットを、ジョブＩＤを用いて指定することができる。
【０１３２】
（実施の形態２）
実施の形態１にかかる分散処理システム１００では、データベース１１０に順次入力されたスプリットに対して、末尾情報が付与されたスプリットを検出するまで同一のジョブとしてＭａｐ処理を実行している。しかし、データベース１１０に入力されるスプリットの順番が期待した通りとはならない場合も有り得る。たとえば、ジョブトラッカー５０１が、計測ファイル１１３を分割してスプリット３、末尾情報が付与されたスプリット４という順序でデータベース１１０に入力したとする。このとき、スプリット３が入力の途中で送信エラーとなって再送となった場合、スプリット４がスプリット３より先にデータベース１１０に入力されることになる。また、スプリット４のデータサイズが小さく、スプリット３より先に入力完了した場合も、スプリット４がスプリット３より先にデータベース１１０に入力されることになる。
【０１３３】
上述した現象が発生した場合、実施の形態１にかかる分散処理システム１００では、スプリット３を次のジョブの処理対象として扱うため、期待する処理結果を得られない場合がある。そこで、実施の形態２にかかる分散処理システム１００は、スプリットの入力される順番が保証されていなくとも、正しい処理結果が得られるようにする。なお、実施の形態１において説明した箇所と同様の箇所については、同一符号を付して図示および説明を省略する。
【０１３４】
図２１は、実施の形態２にかかる分散処理システムの動作例を示す説明図である。図２１に示す、実施の形態２にかかる分散処理システム２１００は、実施の形態２にかかるマスタノード２１０１と、スレーブノード１０２と、データベース１１０と、を含む。図２１では、分散処理システム２１００の時刻ｔ１における状態と、時刻ｔ２における状態とを表示する。なお、時刻ｔ１、時刻ｔ２の順に時間が経過しているとする。また、分散処理システム２１００では、マスタノード２１０１が、計測ファイルをスプリットに分割するとする。
【０１３５】
図２１に示す時刻ｔ１の前に、マスタノード２１０１は、渋滞情報を算出するというジョブの実行要求を受け付けているとする。このとき、マスタノード２１０１は、ジョブに対して、ジョブＩＤ：１を生成する。次に、マスタノード２１０１は、１４：１１〜１４：１４の計測ファイルを受け付ける。このとき、マスタノード２１０１は、１４：１１〜１４：１４の計測ファイルを分割し、各スプリットにジョブＩＤ：１を示す情報を付与する。また、マスタノード２１０１は、各スプリットの個数を記憶しておく。時刻ｔ１の前の時点にて、マスタノード２１０１は、１４：１１〜１４：１４のスプリットの個数が１０であったとして記憶したとする。続けて、マスタノード２１０１は、１０個のスプリットを処理対象とするＭａｐ処理をスレーブノード１０２＃１とスレーブノード１０２＃２に、それぞれ割り当てる。
【０１３６】
図２１に示す時刻ｔ１において、マスタノード２１０１は、１４：１５の計測ファイル１１３を受け付けた場合、計測ファイル１１３を４つのスプリットに分割する。また、マスタノード２１０１は、１４：１５の計測ファイル１１３がジョブＩＤ：１の末尾のファイルであることを判断し、ジョブＩＤ：１の処理対象となる一連のスプリットの個数が１０＋４＝１４であると記憶する。なお、計測ファイル１１３がジョブＩＤ：１の末尾のファイルであることを判断する方法としては、たとえば、ジョブクライアント３０１が、計測ファイル１１３をジョブＩＤ：１の末尾のファイルであることをマスタノード２１０１に通知することである。
【０１３７】
スプリットの分割後、マスタノード２１０１は、分割したスプリット１１〜１４にジョブＩＤ：１を付与する。続けて、マスタノード２１０１は、スプリット１１〜１４をデータベース１１０に入力する。このとき、データベース１１０にスプリット１１〜１４を入力する順序はどのような順序であってもよい。マスタノード２１０１は、データベース１１０にスプリット１１〜１４のいずれかのスプリットが入力されたことを検出すると、いずれかのスプリットを処理対象とするＭａｐ処理をスレーブノード１０２＃１、２に割り当てる。
【０１３８】
また、マスタノード２１０１は、データベース１１０に入力されたスプリットの個数を計数し、計数したジョブＩＤ：１の処理対象となる一連のスプリットの個数と比較する。一連のスプリットの個数と入力されたスプリットの個数とが一致した場合、マスタノード２１０１は、いずれかのスプリットが一連のスプリットの末尾のスプリットであると判断する。判断後の動作について、時刻ｔ２にて説明する。
【０１３９】
図２１に示す時刻ｔ２において、マスタノード２１０１は、Ｍａｐ処理結果の属性をもとに、Ｍａｐ処理の処理結果を集約するシャッフル＆ソート処理１、２を、スレーブノード１０２＃１と、スレーブノード１０２＃２に割り当てる。このように、分散処理システム２１００は、データベースに順次入力されるデータに対してＭａｐ処理を逐次実行し、入力されたスプリットの個数と、一連のスプリットの個数とが一致した場合、シャッフル処理に移行する。これにより、分散処理システム２１００は、スプリットの入力される順番が保証されていなくとも、正しい処理結果を得ることができる。以下、図２２〜図２５を用いて、実施の形態２にかかる分散処理システム２１００の説明を行う。
【０１４０】
（マスタノード２１０１の機能構成）
図２２は、実施の形態２にかかるマスタノードの機能構成例を示すブロック図である。実施の形態２にかかるマスタノード２１０１は、受付部８０１と、検出部８０２と、生成部８０３と、第１の割当部８０４と、第２の割当部８０６と、第１の判断部２２０１と、第２の判断部２２０２とを含む。
【０１４１】
制御部となる受付部８０１〜第１の割当部８０４、第２の割当部８０６、第１の判断部２２０１、第２の判断部２２０２は、記憶装置に記憶されたプログラムをＣＰＵ４０１が実行することにより、機能を実現する。記憶装置とは、具体的には、たとえば、図４に示したＲＯＭ４０２、ＲＡＭ４０３、磁気ディスク４０５などである。または、ＩＦ４０６を経由して他のＣＰＵが実行することにより、受付部８０１〜第１の割当部８０４、第２の割当部８０６、第１の判断部２２０１、第２の判断部２２０２の機能を実現してもよい。実施の形態２にかかる受付部８０１〜第１の割当部８０４は、実施の形態１にかかる受付部８０１〜第１の割当部８０４と同一の機能であるため、説明を省略する。
【０１４２】
第１の判断部２２０１は、次に示す条件を満たす場合、データ群に含まれるスプリットの個数とデータベース１１０に入力されたスプリットの個数とに基づいて、スプリット群がデータベース１１０に入力されたか否かを判断する。条件は、検出部８０２によって新たなスプリットが入力されたことが検出された場合である。スプリット群は、たとえば、１つのファイルである。また、データベース１１０に入力されたスプリットの個数は、マスタノード２１０１のローカル記憶領域に入力された個数であってもよい。
【０１４３】
たとえば、第１の判断部２２０１は、ファイルに含まれるスプリットの個数と入力されたスプリットの個数が一致した場合、ファイルが分割されたスプリット群がデータベース１１０に入力されたと判断する。また、第１の判断部２２０１は、ファイルに含まれるスプリットの個数と入力されたスプリットの個数が異なった場合、ファイルが分割されたスプリット群のうちデータベース１１０に入力されていないスプリットがあると判断する。
【０１４４】
また、第１の判断部２２０１は、検出部８０２によって新たなスプリットが入力されたことが検出された場合、データベース１１０に入力されたスプリットの個数をインクリメントしてもよい。たとえば、現在のデータベース１１０に入力されたスプリットの個数が１０であり、検出部８０２によって新たなスプリットが入力されたことが検出された場合、第１の判断部２２０１は、入力されたスプリットの個数を１１にインクリメントする。
【０１４５】
また、第１の判断部２２０１は、第１の割当部８０４によってノード群のうちのいずれかのノードにＭａｐ処理が割り当てられた場合、データベース１１０に入力されたデータの個数をインクリメントしてもよい。たとえば、現在のデータベース１１０に入力されたスプリットの個数が１０であり、第１の割当部８０４によっていずれかのノードにＭａｐ処理が割り当てられた場合、判断部２２０１は、入力されたスプリットの個数を１１にインクリメントする。なお、判断結果は、ＲＡＭ４０３、磁気ディスク４０５などの記憶領域に記憶される。
【０１４６】
第２の判断部２２０２は、検出部８０２によって新たなスプリットが入力されたことが検出された場合、スプリット群がＭａｐ処理の処理対象となる一連のスプリット群の末尾のスプリット群であるか否かを判断する。たとえば、マスタノード２１０１がジョブクライアントから末尾のファイルを送信したことを受け付けた場合に末尾のファイルを受け付けたことを記憶しておく。第２の判断部２２０２は、末尾のファイルを受け付けたことを記憶する記憶領域を参照して、末尾のファイルを受け付けていた場合、スプリット群の分割元であるファイルが、Ｍａｐ処理の処理対象となる一連のファイルの末尾のファイルであると判断する。
【０１４７】
第２の割当部８０６は、次に示す条件を満たす場合、ノード群のうちのいずれかのノードに、Ｒｅｄｕｃｅ処理を割り当てる。条件は、第１の判断部２２０１によってスプリット群がデータベース１１０に入力されたと判断されており、かつ、第２の判断部２２０２によってスプリット群が一連のスプリット群の末尾のスプリット群であると判断された場合である。なお、実施の形態２にかかる第２の割当部８０６は、実施の形態１にかかる第２の割当部８０６と比較して、実行する契機が異なるだけであるため、詳細の説明を省略する。
【０１４８】
以下、図２３〜図２５を用いて実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理と、実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理から呼び出される処理について説明する。なお、実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その２）は、図１３にて示したＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その２）と同一であるため、説明を省略する。また、実施の形態２にかかる準備処理と、初期化処理と、Ｍａｐタスク割当処理と、シャッフル＆ソート処理と、Ｒｅｄｕｃｅ処理とは、実施の形態１にかかる同名の処理と同一の処理内容であるため、説明を省略する。
【０１４９】
図２３は、実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その１）である。実施の形態２にかかるＭａｐＲｅｄｕｃｅ処理のうち、ステップＳ２３０１、ステップＳ２３０２、ステップＳ２３０５、ステップＳ２３０７、ステップＳ２３０８は、ステップＳ１２０１〜ステップＳ１２０５と同一であるため、説明を省略する。
【０１５０】
ステップＳ２３０２の終了後、ジョブスケジューラ５０２は、入力された現在のジョブＩＤのスプリットの個数を０に設定する（ステップＳ２３０３）。ステップＳ２３０３の実行後、ジョブトラッカー５０１は、ファイル受付処理を実行する（ステップＳ２３０４）。ファイル受付処理は、図２４にて後述する。ステップＳ２３０４の実行後、ジョブスケジューラ５０２は、ステップＳ２３０５の処理を実行する。また、入力されたスプリットがある場合（ステップＳ２３０５：Ｙｅｓ）、ジョブスケジューラ５０２は、入力された現在のジョブＩＤのスプリットの個数をインクリメントする（ステップＳ２３０６）。ステップＳ２３０６の実行完了後、ジョブスケジューラ５０２は、ステップＳ２３０７の処理を実行する。
【０１５１】
なお、ステップＳ２３０６について、ジョブスケジューラ５０２は、入力されたスプリットに現在のジョブＩＤを示す情報とは異なる情報が付与されてない場合、現在のジョブＩＤの入力されたデータの個数をインクリメントしない。そして、ジョブスケジューラ５０２は、ステップＳ２３０４の処理に移行する。
【０１５２】
また、ステップＳ２３０８の実行完了後、ジョブスケジューラ５０２は、末尾のスプリットを検出したか否か判断する（ステップＳ２３０９）。末尾のスプリットでない場合（ステップＳ２３０９：Ｎｏ）、ジョブスケジューラ５０２は、ステップＳ２３０４の処理に移行する。また、末尾のスプリットである場合（ステップＳ２３０９：Ｙｅｓ）、ジョブスケジューラ５０２は、ＭａｐＲｅｄｕｃｅ処理手順の一例を示すフローチャート（その２）に移行する。
【０１５３】
図２４は、ファイル受付処理手順の一例を示すフローチャートである。ファイル受付処理は、初期化処理の後に行う処理である。また、ファイル受付処理は、マスタノード２１０１のジョブトラッカー５０１が実行する。
【０１５４】
ジョブトラッカー５０１は、ジョブクライアント３０１からファイルを受け付けたか否かを判断する（ステップＳ２４０１）。ファイルを受け付けた場合（ステップＳ２４０１：Ｙｅｓ）、ジョブトラッカー５０１は、ファイルをスプリットに分割する（ステップＳ２４０２）。次に、ジョブトラッカー５０１は、現在のジョブＩＤのスプリットの個数を更新する（ステップＳ２４０３）。具体的に、ジョブトラッカー５０１は、ステップＳ２４０２にて、現在のジョブＩＤのスプリットの個数に、分割したスプリットの個数を加算する。
【０１５５】
続けて、ジョブトラッカー５０１は、スプリットにジョブＩＤを示す情報を付与する（ステップＳ２４０４）。ジョブＩＤを示す情報は、スプリットの内容とは区別可能な値であって、ジョブＩＤが記載された情報である。たとえば、ジョブＩＤが１である場合、ジョブＩＤを示す情報は、＜１＞となる。次に、ジョブトラッカー５０１は、現在のジョブＩＤの末尾のファイルを受け付けたか否かを判断する（ステップＳ２４０５）。末尾のファイルを受け付けた場合（ステップＳ２４０５：Ｙｅｓ）、ジョブトラッカー５０１は、現在のジョブＩＤの末尾のファイルを受け付けたことを記憶する（ステップＳ２４０６）。ステップＳ２４０６の実行終了後、ジョブトラッカー５０１は、ファイル受付処理を終了する。
【０１５６】
ジョブクライアント３０１からファイルを受け付けていない場合（ステップＳ２４０１：Ｎｏ）、または、末尾のファイルを受け付けていない場合（ステップＳ２４０５：Ｎｏ）、ジョブトラッカー５０１は、ファイル受付処理を終了する。ファイル受付処理を実行することにより、分散処理システム２１００は、入力されたスプリットにジョブＩＤを示す情報を付与することができる。
【０１５７】
図２５は、実施の形態２にかかるＭａｐタスク生成処理手順の一例を示すフローチャートである。実施の形態２にかかるＭａｐタスク生成処理のうち、ステップＳ２５０１〜Ｓ２５０３は、ステップＳ１６０１〜ステップＳ１６０３と同一であるため、説明を省略する。
【０１５８】
ステップＳ２５０３の実行完了後、ジョブスケジューラ５０２は、入力されたスプリットの個数と現在のジョブＩＤのスプリットの個数が一致するか否かを判断する（ステップＳ２５０４）。個数が一致する場合（ステップＳ２５０４：Ｙｅｓ）、ジョブスケジューラ５０２は、続けて、現在のジョブＩＤの末尾のファイルを受け付けているか否かを判断する（ステップＳ２５０５）。現在のジョブＩＤの末尾のファイルを受け付けている場合（ステップＳ２５０５：Ｙｅｓ）、ジョブスケジューラ５０２は、末尾のスプリットを検出したことを記憶する（ステップＳ２５０６）。個数が一致しない場合（ステップＳ２５０４：Ｎｏ）、または、現在のジョブＩＤの末尾のファイルを受け付けていない場合（ステップＳ２５０５：Ｎｏ）、ジョブスケジューラ５０２は、Ｍａｐタスク生成処理を終了する。なお、図２３にて示したステップＳ２３０６の処理は、ステップＳ２５０１の次からステップＳ２５０４の前までのタイミングで行われてもよい。
【０１５９】
以上説明したように、実施の形態２にかかる割当装置によれば、スプリットを分割する際にジョブＩＤを示す情報を付与し、分割時のスプリットの個数と入力されたスプリットの個数が一致し、かつ末尾のファイルを受け付けた場合、シャッフル処理に移行する。これにより、分散処理システム２１００は、スプリットの入力された順番が保証されていなくとも、正しい処理結果を得ることができる。
【０１６０】
たとえば、分割時のスプリットの個数が３であり、スプリットの入力された順番が、ジョブＩＤ：１の１番目のスプリット、ジョブＩＤ：１の２番目のスプリット、ジョブＩＤ：２の１番目のスプリット、ジョブＩＤ：１の３番目のスプリット、となったとする。ジョブＩＤ：１の２番目のスプリットが入力されたことを検出した時点において、割当装置は、入力されたスプリットが現在のジョブＩＤ：１ではないので、Ｍａｐ処理を割り当てない。
【０１６１】
続けて、ジョブＩＤ：１の３番目のスプリットが入力されたことを検出した時点において、割当装置は、入力されたスプリットが現在のジョブＩＤ：１となるため、Ｍａｐ処理を割り当てる。ジョブＩＤ：１の１＝３番目のスプリットを処理対象とするＭａｐ処理の完了後、割当装置は、シャッフル＆ソート処理を実行する。これにより、割当装置は、入力されたスプリットが次のジョブと混合していても、正しい処理結果を得ることができる。
【０１６２】
また、実施の形態２にかかる割当装置によれば、入力されたスプリットの個数を、記憶部に入力されたことを検出した場合にインクリメントしてもよいし、Ｍａｐ処理を割り当てた場合にインクリメントしてもよい。これにより、割当装置は、入力されたスプリットの個数を数えることができる。
【０１６３】
なお、実施の形態１、２で説明した割当方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本割当プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本割当プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１６４】
上述した実施の形態１、２に関し、さらに以下の付記を開示する。
【０１６５】
（付記１）コンピュータに、
第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断し、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする割当プログラム。
【０１６６】
（付記２）前記コンピュータに、
前記第１の処理の処理対象に固有の識別情報を生成する処理を実行させ、
前記第１の処理を割り当てる処理は、
前記データが入力されたことを検出した場合、前記ノード群のうちのいずれかのノードに、生成した前記識別情報とともに、前記データを処理対象とする前記第１の処理を割り当て、
前記第２の処理を割り当てる処理は、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記識別情報とともに、前記第１の処理の処理結果を処理対象とする第２の処理を割り当てることを特徴とする付記１に記載の割当プログラム。
【０１６７】
（付記３）前記第２の処理を割り当てる処理は、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記第１の処理の処理結果の属性をもとに前記第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする付記１または２に記載の割当プログラム。
【０１６８】
（付記４）コンピュータに、
第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断し、
前記データが入力されたことを検出した場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断し、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行させることを特徴とする割当プログラム。
【０１６９】
（付記５）前記コンピュータに、
前記第１の処理の処理対象に固有の識別情報を生成する処理を実行させ、
前記第１の処理を割り当てる処理は、
前記データが入力されたことを検出した場合、前記ノード群のうちのいずれかのノードに、生成した前記識別情報とともに、前記データを処理対象とする前記第１の処理を割り当て、
前記第２の処理を割り当てる処理は、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記識別情報とともに、前記第１の処理の処理結果を処理対象とする第２の処理を割り当てることを特徴とする付記４に記載の割当プログラム。
【０１７０】
（付記６）前記コンピュータに、
前記データが入力されたことを検出した場合、前記記憶部に入力されたデータの個数をインクリメントする処理を実行させ、
前記データ群が前記記憶部に入力されたか否かを判断する処理は、
前記データが入力されたことを検出した場合、前記データ群に含まれるデータの個数と、インクリメントした前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断することを特徴とする付記４または５に記載の割当プログラム。
【０１７１】
（付記７）前記コンピュータに、
前記ノード群のうちのいずれかのノードに前記第１の処理が割り当てられた場合、前記記憶部に入力されたデータの個数をインクリメントする処理を実行させ、
前記データ群が前記記憶部に入力されたか否かを判断する処理は、
前記データが入力されたことを検出した場合、前記一連のデータに含まれるデータの個数と、インクリメントした前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断することを特徴とする付記４または５に記載の割当プログラム。
【０１７２】
（付記８）前記第２の処理を割り当てる処理は、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記第１の処理の処理結果の属性をもとに前記第１の処理の処理結果を集約した１以上の処理結果を処理対象とする第２の処理を割り当てることを特徴とする付記４〜７のいずれか一つに記載の割当プログラム。
【０１７３】
（付記９）第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出する検出部と、
前記検出部によって前記データが入力されたことが検出された場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当てる第１の割当部と、
前記データが入力されたことが検出された場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断する判断部と、
前記判断部によって前記データに前記末尾情報が付与されていると判断された場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる第２の割当部と、
を有することを特徴とする割当装置。
【０１７４】
（付記１０）第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出する検出部と、
前記検出部によって前記データが入力されたことが検出された場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当てる第１の割当部と、
前記検出部によって前記データが入力されたことが検出された場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断する第１の判断部と、
前記検出部によって前記データが入力されたことが検出された場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断する第２の判断部と、
前記第１の判断部によって前記データ群が前記記憶部に入力されたと判断され、かつ、前記第２の判断部によって前記データ群が前記一連のデータ群の末尾のデータ群であると判断された場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる第２の割当部と、
を有することを特徴とする割当装置。
【０１７５】
（付記１１）コンピュータが、
第１の処理の処理対象となるデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データに、前記第１の処理の処理対象となる一連のデータの末尾のデータであることを示す末尾情報が付与されているか否かを判断し、
前記データに前記末尾情報が付与されていると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータの各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行することを特徴とする割当方法。
【０１７６】
（付記１２）コンピュータが、
第１の処理の処理対象となるデータ群の各々のデータが順次入力される記憶部に、データが入力されたことを検出し、
前記データが入力されたことを検出した場合、通信可能なノード群のうちのいずれかのノードに前記データを処理対象とする前記第１の処理を割り当て、
前記データが入力されたことを検出した場合、前記データ群に含まれるデータの個数と、前記記憶部に入力されたデータの個数とに基づいて、前記データ群が前記記憶部に入力されたか否かを判断し、
前記データが入力されたことを検出した場合、前記データ群が前記第１の処理の処理対象となる一連のデータ群の末尾のデータ群であるか否かを判断し、
前記データ群が前記記憶部に入力されたと判断し、かつ、前記データ群が前記一連のデータ群の末尾のデータ群であると判断した場合、前記ノード群のうちのいずれかのノードに、前記一連のデータ群の各々のデータを処理対象として実行された前記第１の処理の処理結果を処理対象とする第２の処理を割り当てる、
処理を実行することを特徴とする割当方法。
【符号の説明】
【０１７７】
１００，２１００  分散処理システム
１０１，２１０１  マスタノード
１０２  スレーブノード
１１０  データベース
８０１  受付部
８０２  検出部
８０３  生成部
８０４  第１の割当部
８０５  判断部
８０６  第２の割当部
２２０１  第１の判断部
２２０２  第２の判断部
【図１】
0005853866.tif 000002
【図２】
0005853866.tif 000003
【図３】
0005853866.tif 000004
【図４】
0005853866.tif 000005
【図５】
0005853866.tif 000006
【図６】
0005853866.tif 000007
【図７】
0005853866.tif 000008
【図８】
0005853866.tif 000009
【図９】
0005853866.tif 000010
【図１０】
0005853866.tif 000011
【図１１】
0005853866.tif 000012
【図１２】
0005853866.tif 000013
【図１３】
0005853866.tif 000014
【図１４】
0005853866.tif 000015
【図１５】
0005853866.tif 000016
【図１６】
0005853866.tif 000017
【図１７】
0005853866.tif 000018
【図１８】
0005853866.tif 000019
【図１９】
0005853866.tif 000020
【図２０】
0005853866.tif 000021
【図２１】
0005853866.tif 000022
【図２２】
0005853866.tif 000023
【図２３】
0005853866.tif 000024
【図２４】
0005853866.tif 000025
【図２５】
0005853866.tif 000026