処理装置、分散処理システム、及び処理プログラム
【課題】分散処理システムにおける性能・スケーラビリティを改善する。
【解決手段】Ｒｅｄｕｃｅ処理部における集約キーの更新ができなくなるまで、Ｍａｐ処理部が複数のデータそれぞれが有するキーを、集約キー、未使用キー、及び使用済みキーとして関連付けてＭａｐデータを生成する処理と、Ｒｅｄｕｃｅ処理部が、集約キーを用いてＭａｐデータを集約するとともに、集約後のＭａｐデータのグループに含まれる各Ｍａｐデータの未使用キーを全て取得し、取得された未使用キーのうちの１つで、集約後のＭａｐデータのグループに含まれる各Ｍａｐデータの集約キーを更新する（ステップＳ３８）処理と、を繰り返す。これにより、関係データベースを用いなくとも、処理対象のデータを参照するのみで、複数のＭａｐデータを集約することができる。
【解決手段】Ｒｅｄｕｃｅ処理部における集約キーの更新ができなくなるまで、Ｍａｐ処理部が複数のデータそれぞれが有するキーを、集約キー、未使用キー、及び使用済みキーとして関連付けてＭａｐデータを生成する処理と、Ｒｅｄｕｃｅ処理部が、集約キーを用いてＭａｐデータを集約するとともに、集約後のＭａｐデータのグループに含まれる各Ｍａｐデータの未使用キーを全て取得し、取得された未使用キーのうちの１つで、集約後のＭａｐデータのグループに含まれる各Ｍａｐデータの集約キーを更新する（ステップＳ３８）処理と、を繰り返す。これにより、関係データベースを用いなくとも、処理対象のデータを参照するのみで、複数のＭａｐデータを集約することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、処理装置、分散処理システム、及び処理プログラムに関する。
【背景技術】
【０００２】
大量データを対象にした分析処理には、非常に長い処理時間を要する。これに対し、最近では、複数のマシンを用いて分散・並列処理を行うことで処理時間を短縮するアプローチがとられている。分散・並列処理としては、例えば、MapReduceアルゴリズムを用いた方法（例えば、非特許文献１参照）がある。また、MapReduceアルゴリズムのオープンソース実装として、Apache Hadoopが存在している。
【０００３】
MapReduceは、主に元のデータを多数のキーと値のセットに分割する「Ｍａｐ処理」と、それらのキーと値のセットをあるルールによって集約する「Ｒｅｄｕｃｅ処理」とによって構成される。Ｍａｐ処理及びＲｅｄｕｃｅ処理の各処理は、それぞれ複数並列に実行可能であるため、それらを複数の処理マシン（サーバなど）に割り当てることにより、複数マシンの処理性能を活用することができる。
【０００４】
ただし、MapReduceによる分散・並列処理の効果を高めるには、それぞれのＭａｐ処理、Ｒｅｄｕｃｅ処理の独立性を高くし、他の部分に依存せずに処理を行えるようにする必要がある。
【０００５】
分析処理の一種として、大量のデータ群の中から、関係のあるデータをグルーピングするものがある。例えば、図３３（ａ）に示すように、ある時期に行われた業務ログを、図３３（ｂ）に示すように、一連となっている業務フロー単位にグルーピングする場合などである。グルーピングの処理では、あるグループのデータ群を扱う際、別のグループのデータを考慮する必要が無いため、各グループの処理を複数サーバに分散させることにより、効率的に処理が行える。
【０００６】
なお、図３３（ａ）のように一連の業務フローが１つのキー種（図３３（ａ）ではフローＩＤ）によって示されるデータをグルーピングする際には、MapReduceを用いることによってグルーピングは容易に達成される。MapReduceを行う処理マシンでは、あるキー値を持つデータ群を一箇所に集約する機能を標準で有しているためである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters OSDI 2004
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、図３４（ａ）のように、一連の業務フローを示すキーが複数（図３４（ａ）では３種）存在する場合もあり得る。なお、図３４（ｂ）は、図３４（ａ）のデータを集約した例を示している。このような場合には、単純にはグルーピングを行うことができない。複数のキー種を用いて関連のあるデータ群を集約する処理（以下、「複数キー集約処理」と呼ぶ）では、どのキーの組み合わせが一連のデータ群を示すのかが、データ全体を見ないと完全には確定しないからである。例えば、図３４（ａ）の場合、伝票番号＝001で集約しようとすると、伝票明細詳細テーブルのデータを集約できない。一方、伝票明細詳細番号＝001-001-001で集約する場合、伝票テーブルのデータを集約できない。
【０００９】
この場合、処理の進展に応じてキー値の組み合わせの情報を最新化しながら集約処理を進めるような工夫が必要であり、また、最新化する処理が不十分な場合には、データの集約漏れが発生する場合がある。
【００１０】
これに対し、キー種間の関連を管理する表をＲＤＢ（関係データベース(Relational Database））などに作成することも考えられる。しかるに、分散・並列処理する各処理マシンが共通に参照・更新する箇所があると、分散処理の性能・スケーラビリティが劣化するおそれがある。
【００１１】
そこで本件は上記の課題に鑑みてなされたものであり、性能・スケーラビリティの向上及びデータ集約漏れを防止することが可能な処理装置、分散処理システム、及び処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本明細書に記載の処理装置は、複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、を備え、前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返す処理装置である。
【００１３】
本明細書に記載の分散処理システムは、本明細書に記載の処理装置を複数備え、複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行する分散処理システムである。
【００１４】
本明細書に記載の処理プログラムは、複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、取得した前記未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させる処理プログラムである。
【発明の効果】
【００１５】
本明細書に記載の処理装置、分散処理システム、及び処理プログラムは、性能・スケーラビリティの向上、及びデータ集約漏れを防止することができるという効果を奏する。
【図面の簡単な説明】
【００１６】
【図１】一実施形態に係る分散処理システムの構成を概略的に示す図である。
【図２】処理サーバのハードウェア構成を示す図である。
【図３】処理サーバの機能ブロック図である。
【図４】MapReduce処理の基本的な処理内容について説明するための図である。
【図５】MapReduce処理の一連の流れについて示すフローチャートである。
【図６】図６（ａ）は、Ｍａｐ処理における入力データの一例を示す図であり、図６（ｂ）は、１つのＭａｐデータのキー及び値の具体的な内容を示す図である。
【図７】集約対象のＭａｐデータの一例を示す図である。
【図８】図８（ａ）〜図８（ｃ）は、図７の最下層のテーブルについてＭａｐ処理を行った場合の例を説明するための図である。
【図９】ステップＳ１４の具体的処理を示すフローチャート（その１）である。
【図１０】ステップＳ１４の具体的処理を示すフローチャート（その２）である。
【図１１】図１１（ａ）は集約キーがＺ＝０１０１０１の集約グループを示す図であり、図１１（ｂ）は、図１１（ａ）の集約グループのキー一覧リストであり、図１１（ｃ）は、図１１（ａ）の集約グループのデータ一覧リストである。
【図１２】図１０のステップＳ３８の処理を説明するための図である。
【図１３】１回目の集約により、同階層で同一のキー値を持つデータ群が集約された様子を示した図である。
【図１４】図１４（ａ）〜図１４（ｃ）は、集約キーがＹ＝０１０１のＭａｐデータを集約する処理を説明するための図（リスト１６，１８）が示されている。
【図１５】２回目の集約処理を行った後の状態を示す図である。
【図１６】３回目の集約処理を行った後の状態を示す図である。
【図１７】４回目の集約処理を行った後の状態を示す図である。
【図１８】５回目の集約処理を行った後の状態を示す図である。
【図１９】６回目の集約処理を行った後の状態を示す図である。
【図２０】７回目の集約処理を行った後の状態を示す図である。
【図２１】比較例において１回目の集約処理を行った後の状態を示す図である。
【図２２】比較例において２回目の集約処理を行った後の状態を示す図である。
【図２３】比較例において３回目の集約処理を行った後の状態を示す図である。
【図２４】比較例において４回目の集約処理を行った後の状態を示す図である。
【図２５】比較例において５回目の集約処理を行った後の状態を示す図である。
【図２６】比較例において６回目の集約処理を行った後の状態を示す図である。
【図２７】別例における図７に対応する図である。
【図２８】別例において１回目の集約処理を行った後の状態を示す図である。
【図２９】別例において２回目の集約処理を行った後の状態を示す図である。
【図３０】別例において３回目の集約処理を行った後の状態を示す図である。
【図３１】別例において４回目の集約処理を行った後の状態を示す図である。
【図３２】別例において５回目の集約処理を行った後の状態を示す図である。
【図３３】従来例を説明するための図（その１）である。
【図３４】従来例を説明するための図（その２）である。
【発明を実施するための形態】
【００１７】
以下、一実施形態について、図１〜図３２に基づいて詳細に説明する。図１には、分散処理システム１００の構成が概略的に示されている。本実施形態の分散処理システム１００では、複数のキーが与えられたデータを集約する「複数キー集約処理」を行うこととし、当該処理では、MapReduceアルゴリズムを適用するものとする。ここで、集約とは、同一のキーのデータを取得することを意味する。
【００１８】
分散処理システム１００は、図１に示すように、処理を実行するｎ台の処理装置としての処理サーバ１０と、各処理サーバ１０の処理を管理する管理サーバ２０と、を備える。各処理サーバ１０と管理サーバ２０は、ＬＡＮ（Local Area Network）、インターネットなどのネットワーク３０に接続されている。
【００１９】
図２には、処理サーバ１０のハードウェア構成が示されている。図２に示すように、処理サーバ１０は、ＣＰＵ９０、ＲＯＭ９２、ＲＡＭ９４、記憶部（ここではＨＤＤ（Hard Disk Drive））９６、入出力部９７、可搬型記憶媒体用ドライブ９９等を備えている。これら処理サーバ１０の構成各部は、バス９８に接続されている。処理サーバ１０では、ＲＯＭ９２あるいはＨＤＤ９６に格納されているプログラム（処理プログラム）、又は可搬型記憶媒体用ドライブ９９が可搬型記憶媒体９１から読み出したプログラム（処理プログラム）をＣＰＵ９０が実行することにより、図３の各部の機能が実現される。
【００２０】
図１に戻り、各処理サーバ１０のディスク（ＨＤＤ９６）は、仮想的に１つのディスクに見える分散ファイルシステム４０に組み込まれている。なお、図示の便宜上、図１では、ＨＤＤ９６を各処理サーバ１０の外側に出して示している。なお、図１の構成図は、MapReduceのオープンソース実装であるHadoopを用いる場合の一例を示すものであり、管理サーバ２０や分散ファイルシステム４０は、分散処理システム１００内に必ずしも設けなくてもよい。
【００２１】
図３には、処理サーバ１０の機能ブロック図が示されている。処理サーバ１０は、図３に示すように、関連付け部としてのＭａｐ処理部１２、及び集約部としてのＲｅｄｕｃｅ処理部１４、としての機能を有する。また、ＨＤＤ９６により、キー一覧リスト１６を格納する領域と、データ一覧リスト１８を格納する領域とが用意されている。
【００２２】
Ｍａｐ処理部１２は、分散ファイルシステム４０に格納されているデータを用いて、後述するＭａｐ処理を実行する。Ｒｅｄｕｃｅ処理部１４は、Ｍａｐ処理部１２においてＭａｐ処理されたデータを用いて、後述するＲｅｄｕｃｅ処理を行う。キー一覧リスト１６は、図１１（ｂ）に示すようなリストである。データ一覧リスト１８は、図１１（ｃ）に示すようなリストである。
【００２３】
次に、MapReduce処理の基本的な処理内容について、図４に基づいて、説明する。
【００２４】
MapReduce処理では、分散ファイルシステム４０上の処理対象のデータを、キーと値からなるＭａｐデータに分割する処理（Ｍａｐ処理）と、キーの値に応じてＭａｐデータを纏める処理（Ｒｅｄｕｃｅ処理）とを、各処理サーバ１０において分散・並列的に行う。
【００２５】
例えば、各処理サーバ１０において分散・並列的に行われたＭａｐ処理によって、図４の上段に示すようなＭａｐデータが生成されたとする。この場合、各処理サーバ１０又は管理サーバ２０は、各Ｍａｐデータのキーの値に対し、一意なハッシュ値を公知の計算方法により計算し、そのハッシュ値を処理サーバ数（図４では３）で割った剰余（０〜２）を求める。この場合、予め、各処理サーバ１０に関し、対応する剰余値を、図４の下段に示す番号（０〜２）で決めておくことで、各Ｍａｐデータを処理する処理サーバ１０を決定することができる。なお、同一の値のキーに対しては常に同一のハッシュ値が得られるため、同一のキー値を持ったＭａｐデータ群は１つの処理サーバに集められる。また、ハッシュ値が偏りのない前提であれば、各Ｍａｐデータの処理を各サーバに偏りなく分散させることができる。なお、上述したハッシュ値から一意に処理サーバを決定する方法は、最も単純な例である。したがって、例えば、ハッシュ値に加えて、その時点の処理サーバの負荷を考慮に入れるなどして、より高度に処理サーバを決定することとしてもよい。
【００２６】
各処理サーバ１０（Ｒｅｄｕｃｅ処理部１４）は、集められたＭａｐデータの集約キー（以下、単に「キー」とも呼ぶ）の値を参照する。そして、各処理サーバ１０（Ｒｅｄｕｃｅ処理部１４）は、同一のキー値を持ったＭａｐデータ（Ｍａｐデータ群）を１つのグループとし、そのグループに対してＲｅｄｕｃｅ処理を行う（図４の下段におけるキー＝ＣＣＣのグループ参照）。なお、管理サーバ２０は、各処理サーバ１０の状態を把握しているため、各処理サーバ１０におけるＭａｐ処理やＲｅｄｕｃｅ処理が完了したかどうかについても把握している。このため、管理サーバ２０は、Ｒｅｄｕｃｅ処理の結果を受けて、再度各処理サーバ１０にＭａｐ処理を実行させるなどすることで、MapReduce処理を繰り返し行うことができる。
【００２７】
次に、本実施形態の分散処理システム１００における、複数キー集約処理の詳細について、説明する。
【００２８】
なお、単一のキーでの集約であれば、上述したMapReduceの基本的な処理を行うことで実現できる（図３３参照）。しかし、複数のキーを用いた集約の場合、MapReduce処理を複数回繰り返してデータを集約する必要がある。
【００２９】
前述の通り、同じ集約キー（キー）を持ったＭａｐデータは、同じサーバ・同じグループへ集約される。このため、本実施形態では、キー値を変更しながら、複数回のMapReduce処理を繰り返すことで、段階的にデータを集約するアプローチを採用する。なお、キー値を変更した場合には、ハッシュ値も変わるので、キー値変更後のデータは、別の処理サーバで処理される可能性もある。
【００３０】
図５は、複数キー集約処理における具体的な処理の流れを示すフローチャートである。図５の複数キー集約処理では、Ｍａｐ処理とＲｅｄｕｃｅ処理とが必要回数繰り返される。
【００３１】
図５の処理では、まず、ステップＳ１０において、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、繰り返し制御用のカウンタとして、「キー変更カウンタ」を用意し、これを０に初期化する。なお、キー変更カウンタは、各処理サーバ１０が更新することができる。各処理サーバ１０では、Ｒｅｄｕｃｅ処理が終わったことを契機にキー変更カウンタを更新する。
【００３２】
次いで、ステップＳ１２では、各処理サーバ１０のＭａｐ処理部１２が、Ｍａｐ処理を実行する。このステップＳ１２では、Ｍａｐ処理部１２が、分散ファイルシステム４０上に存在する、入力データやＲｅｄｕｃｅ処理結果の中間生成データから、キー（集約キー）と値の組み合わせであるＭａｐデータ群を生成し、分散ファイルシステム４０に記憶する。
【００３３】
ここで、図５のステップＳ１２を実行するのが１回目（初回）である場合には、Ｍａｐ処理部１２は、入力データ（図６（ａ）に示すようなデータ）の各行の主キー値をキー（集約キー）とする（図６（ｂ）参照）。なお、主キー値がどの値であるかは、あらかじめ定義しておくものとする。図６（ａ）では、主キー値は最左列の値である。また、Ｍａｐ処理部１２は、図６（ｂ）に示すように、値に、行全体の情報とキーの管理情報とを設定して、Ｍａｐデータを生成する。なお、Ｍａｐ処理は各行独立に実行可能であるため、行数を処理サーバ１０の数で分割して、各処理サーバ１０で分散して実行するものとする。ここで、Ｍａｐデータのキーの管理情報は、図６（ｂ）に示すように、最初のキーを保存する「元キー」、未使用のキーを保存する「未使用キー」、過去に使用したキーを保存する「使用済みキー」、キー変更の必要が無いことを示す「固定フラグ」などである。
【００３４】
図７は、集約対象のＭａｐデータの一例を示している。図７に示す例では、データは３階層に分類されており、１９個のデータ実体が存在する。最上層ではＸが主キーとなっており、０１〜０５までのキー値が存在する。２番目の層ではＹが主キーとなっており、０１０１〜０１０５までのキー値が存在する。なお、２番目の層のデータは、関連キーとしてＸも有しているため、最上層のデータと関連付けられている。また、最下層の主キーはＺであり、０１０１０１〜０１０１０６までのキー値が存在する。なお、最下層のデータ（図６（ａ）のデータと同一）は、関連キーとしてＹを有しているため、２番目の層のデータと関連付けられている。
【００３５】
図７の例で特徴的なのは、関連の親子関係が複雑である点である。通常、このような構造のデータでは、一般には親と子の数の関係は１対多である。この点、図７の破線よりも右側のデータはそのような関係になっているが、図７の破線よりも左側では必ずしもそのような関係になっていない。例えばＺ＝０１０１０１のデータはＹ＝０１０１にもＹ＝０１０２にも関連している。親と子が常に１対多の関係であれば、下層のキーから順にＺ→Ｙ→Ｘと３回集約すればすべてのグループが正しく集約される。しかしながら、図７のようなケースではその方法では集約漏れするデータが生じるおそれがある。
【００３６】
ここで、図７の最下層のデータ（Ｍａｐデータ）の生成方法（Ｍａｐ処理方法）について、図８（ａ）〜図８（ｃ）に基づいて説明する。図８（ａ）は、最下層のデータのテーブル（元データ）である。図８（ａ）の元データは、管理サーバ２０又はいずれかの処理サーバ１０のＭａｐ処理部１２によって、図８（ｂ）に示すように、処理サーバ数（図８（ｂ）では、処理サーバ数が２であるものとする）に分割される。そして、各処理サーバ１０では、分割されたうちの１つのテーブルについて、Ｍａｐ処理を行い、図８（ｃ）に示すように、Ｍａｐデータを生成する。このような処理により生成されるＭａｐデータが、図７の最下層の７つのデータとなる。
【００３７】
図５に戻り、次のステップＳ１４では、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、Ｒｅｄｕｃｅ処理を実行する。このＲｅｄｕｃｅ処理では、まず、管理サーバ２０が、同一のキー値を持つＭａｐデータ群を１つの処理サーバ１０に集約する。そして、Ｒｅｄｕｃｅ処理部１４は、図９、図１０のフローチャートに沿った処理を実行する。
【００３８】
ここで、各処理サーバ１０に対する入力は、図７で示される構造を有するＭａｐデータの集合であり、キー値が同一のデータ群であるものとする。なお、キー値が同一のデータ群を、以下においては、「グループ」と呼ぶ。また、以下の説明では、図９、図１０の処理の説明と併せて、図１１（ａ）に示すＭａｐデータ（特に、図１１（ａ）において集約キーがＺ＝０１０１０１のデータ）のＲｅｄｕｃｅ処理を例にとり、説明する。
【００３９】
図９の処理では、まず、ステップＳ２０において、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、グループのデータ一覧リスト１８（図１１（ｃ）参照）、及びキー一覧リスト１６（図１１（ｂ）参照）を初期化する。次いで、ステップＳ２２では、Ｒｅｄｕｃｅ処理部１４が、グループの集約キーを使用済みキーとしてキー一覧リスト１６へ追加する（図１１（ｂ）の最下段参照）。
【００４０】
次いで、ステップＳ２４では、Ｒｅｄｕｃｅ処理部１４が、処理対象のＭａｐデータ（例えば、図１１（ａ）の１番のデータ）を取得する。次いで、ステップＳ２６では、Ｒｅｄｕｃｅ処理部１４が、Ｍａｐデータをグループのデータ一覧リスト１８へコピーする（図１１（ｃ）の１番のデータ参照）。次いで、ステップＳ２８では、Ｒｅｄｕｃｅ処理部１４が、ステップＳ２６でコピーしたＭａｐデータ中の未使用／使用済みキー値をグループのキー一覧リスト１６へコピーする。なお、ここでは、図１１（ｂ）のキー一覧リスト１６において、未使用キーの欄にＹ＝０１０１がコピーされるが、使用済みキーは存在していないため、使用済みキーの欄には何もコピーされない。
【００４１】
次いで、ステップＳ３０では、Ｒｅｄｕｃｅ処理部１４が、未処理のＭａｐデータが存在するか否かを判断する。ここでの判断が肯定された場合には、ステップＳ２４に戻り、ステップＳ２４〜Ｓ２８の処理を繰り返す。その結果、ステップＳ３０の判断が否定される段階では、図１１（ｃ）のデータ一覧リスト１８に、２番のデータがコピーされるとともに、図１１（ｂ）のキー一覧リスト１６に、未使用キーとして、Ｙ＝０１０２がコピーされる。このように、Ｒｅｄｕｃｅ処理部１４は、Ｍａｐデータ群から、各データを順次取得（１つずつ取得）して、データ一覧リスト１８及びキー一覧リスト１６にデータ、未使用キーや使用済みキーをコピーする。なお、キー一覧リスト１６における、未使用キーの欄と使用済みキーの欄は排他的ではなく、未使用キーの欄と使用済みキーの欄に同じキーを格納することもできる。一方、未使用キーの欄の中で重複したキー、あるいは使用済みキーの欄の中で重複したキーがある場合には、１つのみ残して重複するキーを削除してもよい。
【００４２】
以上のようにして、ステップＳ３０の判断が否定された場合には、図１０のステップＳ３２に移行する。
【００４３】
図１０のステップＳ３２では、Ｒｅｄｕｃｅ処理部１４が、データ一覧リスト１８の中に固定フラグが設定されたデータが存在するか否かを判断する。ここでの判断が否定された場合には、ステップＳ３４に移行する。なお、ステップＳ３２の判断が肯定された場合には、ステップＳ４８（このステップについては後述）に移行する。ここで、図１１（ｃ）の例では、データ一覧リスト１８に、固定フラグが設定されたデータは存在していない（全てｆａｌｓｅ）ので、ステップＳ３２の判断は肯定されて、ステップＳ３４に移行する。
【００４４】
ステップＳ３４に移行した場合、Ｒｅｄｕｃｅ処理部１４は、キー一覧リスト１６の中に未使用のキーが存在するか否かを判断する。図１１（ｂ）の例では、キー一覧リスト１６に、未使用のキーが存在しているので、ステップＳ３４の判断は肯定され、ステップＳ３６に移行する。
【００４５】
ステップＳ３６に移行した場合、Ｒｅｄｕｃｅ処理部１４は、データ一覧リスト１８中のどの元キーとも一致しない未使用キーが存在するか否かを判断する。図１１（ｂ）の例では、キー一覧リスト１６に、データ一覧リスト１８中のどの元キーとも一致しない未使用キーが２つ存在しているので、ここでの判断は肯定され、ステップＳ３８に移行する。
【００４６】
ステップＳ３６の判断が肯定され、ステップＳ３８に移行した場合、Ｒｅｄｕｃｅ処理部１４は、実体を持つ全データのキーを、未使用キーの欄から一つ選択したキーに書き換える。また、Ｒｅｄｕｃｅ処理部１４は、選択したキーを除き、グループのキー一覧リスト１６の内容を未使用／使用済みキーに格納する。すなわち、ステップＳ３８では、図１２に示すように、Ｒｅｄｕｃｅ処理部１４は、データ一覧リスト１８に含まれるＭａｐデータの１番のデータのキーと２番のデータのキーをＹ＝０１０１に書き換える。また、Ｒｅｄｕｃｅ処理部１４は、キー一覧リスト１６の未使用キーからＹ＝０１０１を除いた結果、すなわちＹ＝０１０２を各データの未使用キーに格納する。また、キー一覧リスト１６の使用済みキーであるＺ＝０１０１０１を各データの使用済みキーに格納する。
【００４７】
次いで、ステップＳ４０では、Ｒｅｄｕｃｅ処理部１４が、実体を持たないＭａｐデータが存在しない場合、新たに実体を持たないキーのみのＭａｐデータを１つ生成する。例えば、図１２において３番のデータとして示すデータを生成する。この場合、書き換える前のキー（＝集約キー）をキーとし、グループの未使用キー一覧の内容（図１１（ｂ））を未使用キーの欄に格納する。図１２の３番のデータでは、キーとしてグループの集約キーであるＺ＝０１０１０１を設定し、未使用キーにはグループのキー一覧リスト１６の未使用キーであるＹ＝０１０１とＹ＝０１０２を設定する。なお、使用済みキーの設定は必要なく、固定フラグは「false」とし、データ本体は空とする。
【００４８】
次いで、ステップＳ４６では、Ｒｅｄｕｃｅ処理部１４は、キー変更カウンタを１だけインクリメントする。次いで、ステップＳ５０では、Ｒｅｄｕｃｅ処理部１４が、図１に示す分散ファイルシステム４０上の、Ｍａｐデータ群の中間ファイルへの出力を行い、その後、図５のステップＳ１６に移行する。なお、ステップＳ５０で出力されるＭａｐデータ群は、図１２に示すデータである。
【００４９】
図１３は、１回目の集約により、同階層で同一のキー値を持つデータ群（グループ）が集約された様子を示した図である。なお、図１３に示すように、１回目の集約によって、Ｚ＝０１０１０１以外の２つのキー（Ｙ＝０１０１、Ｙ＝０１０３）のＭａｐデータも集約されている。この図において、データを示す箱（矩形枠）の左上に示す値（Ｚ＝０１０１０１等）が、各集約グループを示しており、その値の下に隣接して配置された箱の一群がグループのデータを示している。また、箱の内部の「未使用キー」は、図１１（ｂ）におけるキー一覧リスト１６の未使用キーの欄を示している。更に、箱の内部の「キー」の矢印の左側はその集約における集約キー、右側は未使用キーの中から一つ選択したキーで、次の集約において集約キーとなる値を示している。なお、図１３では、図示及び説明の簡単のため、使用済みキーは表示していない。なお、図１２のように、Reduce処理の終盤でキー情報のみのＭａｐデータが生成されている（図１２のデータ「３」）が、これは再集約（２回目以降の集約）が実施されたときにのみ意味を持つものなので、図１３では図示していない。なお、図１５において破線で示されている箱が、１回目の集約で生成されたキー情報のみのＭａｐデータである。
【００５０】
なお、図１０の処理において、キー一覧リスト１６の中に未使用のキーが存在していない場合（例えば、図１３の最上段のデータ等の場合）には、ステップＳ３４の判断が否定される。ステップＳ３４の判断が否定された場合には、Ｒｅｄｕｃｅ処理部１４は、キー変更カウンタを０に維持したまま、ステップＳ５０に移行し、Ｍａｐデータ群の中間ファイルへの出力を行った後、図５のステップＳ１６に移行する。
【００５１】
図５に戻り、次のステップＳ１６に移行すると、管理サーバ２０は、Ｒｅｄｕｃｅ処理のキー変更カウンタの集計値が１以上か否かを判断する。上記例では、いずれかのグループで集約キーの変更が発生しており、図１０のステップＳ４６を経ている。したがって、キー変更カウンタの集計値は１以上となるため、ステップＳ１６の判断は肯定され、ステップＳ１０に戻る。そして、ステップＳ１０〜Ｓ１６の処理（再度のMapReduce処理）を繰り返す。
【００５２】
なお、図１０の処理において、データ一覧中のどの元キーとも一致しない未使用キーが存在しない場合には、ステップＳ３６の判断が否定される。この場合、キー値の変更が一巡したとみなせるので、それ以上の変更は無意味となる。したがって、この場合には、ステップＳ４２に移行し、Ｒｅｄｕｃｅ処理部１４が、データ一覧リスト１８中の全データに対し、固定フラグを設定する。そして、ステップＳ４４において、Ｒｅｄｕｃｅ処理部１４は、データ一覧中の全データのキーを、使用済みキー一覧の中から、辞書式に判定して先頭となるキー値を変更する。なお、これらステップＳ４２、Ｓ４４の具体的処理については、後述する。その後は、上記と同様、ステップＳ４６、Ｓ５０を経て、図５のステップＳ１６に移行する。
【００５３】
また、図１０のステップＳ３２において、データ一覧リスト１８の中に固定フラグが設定されたデータが存在していた場合には、ステップＳ４８に移行する。このステップＳ４８では、Ｒｅｄｕｃｅ処理部１４が、データ一覧中の全データに対し、固定フラグを設定することで、その時点の集約キーをそのまま用いて再集約可能な状態にする。そして、ステップＳ５０において、Ｍａｐデータ群の中間ファイルへの出力を行った後、図５のステップＳ１６に移行する。
【００５４】
次に、２回目の集約処理について説明する。図１４（ａ）〜図１４（ｃ）には、集約キーがＹ＝０１０１のＭａｐデータを集約する処理を説明するための図（リスト１６，１８）が示されている。図１４（ｂ）のデータ一覧リストのうち１、２番目のデータは、図１２の１、２番目のデータと同一である。これに対し、３番目のデータは、図１３のＹ＝０１０１のグループを集約した際に生成されたデータ実体のないデータ（図１５の符号Ｄａで示す破線の箱参照）である。また、これら３つのデータからは、キー一覧リスト１６として、図１４（ａ）のようなリストが得られる。これら、図１４（ａ）のキー一覧リスト及び図１４（ｂ）のデータ一覧リストを用いて図１０の処理を行うと、図１４（ｃ）のような３つのデータを得ることができる。このような２回目の集約処理を行った後の状態が、図１５に示されている。図１５に示すように、２回目の集約処理の結果、集約キーがＹ＝０１０１のＭａｐデータ以外のＭａｐデータも集約されていることが分かる。
【００５５】
以下、同様に集約処理を繰り返すと、３回目の集約処理の結果は、図１６のようになる。また、４回目の集約処理の結果は、図１７のようになり、５回目の集約処理の結果は、図１８のようになり、６回目の集約処理の結果は、図１９のようになる。そして、７回目の集約処理の結果、図２０のようになる。図２０の状態では全グループに未使用キーが存在しなくなるため（全処理サーバ１０においてステップＳ３４が否定されるため）、キー変更カウンタは０のままとなる。この場合、図５のステップＳ１６の判断が否定され、ステップＳ１８に移行する。そして、管理サーバ２０は、ステップＳ１８において集約処理を完了する。
【００５６】
本実施形態では、上記のようなMapReduce処理を行うことで、図２０に示すように、Ｘ＝０４のグループとＸ＝０５の２グループとなる。これにより、複数のＭａｐデータを、図７の状態から正確に（集約漏れなく）２つのグループに集約できたことになる。
【００５７】
（比較例）
ここで、比較例（従来法を用いて、図７のデータを集約する場合）について説明する。なお、以下の処理は、各処理サーバ１０が行うものとする。
【００５８】
従来法としては、各データは変更可能なキー、不変の関連キーリスト（データにおいて定義されているキー）、再集約のフラグを兼ねる変更可能な予約関連キーを有することとする。また、上述した実施形態で用いたデータ実体を持たないキー値のみのデータは用いていない。従来法では、実体のないデータを用いないことを理由に、集約処理を全階層同時に行うことはできないため、キー値の種類毎に下層の方から順に集約する必要が生じる。
【００５９】
図２１には、元データの主キーをキー、関連キーを関連キーリストに格納し、最下層のキーであるＺを集約キーとして１回目の集約を行った結果が示されている。なお、図２１及びこれ以降の図面では、各データの識別のため、処理には使用しないＩＤを示している。図２１では、Ｚ＝０１０１０１のグループのみ、複数の関連キーを含んでいる。このように、グループ内に複数の関連キーが存在する場合、そのグループのデータには予約関連キーが設定される。予約関連キーの値は、そのグループの集約キーとなる。従って、Ｚ＝０１０１０１のグループではＺ＝０１０１０１が予約関連キーとなる。また、１回目の集約が行われたデータ又はグループのキーは、関連キーに変更される。
【００６０】
次いで、２回目の集約では、２番目の層のキーであるＹでの集約が行われる。その結果が図２２に示されている。ここで、図２２に示すように、Ｙ＝０１０１とＹ＝０１０２のグループには、１回目の集約時に予約関連キーを設定したデータが含まれている。このため、次の３回目の集約では、最上層のキーではなく、予約関連キーで集約が行われる。一方、予約関連キーが設定されていないグループについては、２回目と同じキー値で再度集約が行われる。
【００６１】
３回目の集約結果が図２３に示されている。予約関連キーでの集約を終えたので、次の集約は最上層のキーであるＸでの集約となるが、Ｚ＝０１０１０１とＹ＝０１０３のグループには複数のＸのキー値が含まれるため、各データに予約関連キーが設定される。
【００６２】
以下、上記と同様の処理が繰り返されることにより、４回目の集約処理の結果、図２４のようになり、５回目の集約処理の結果、図２５のようになり、６回目の集約処理の結果、図２６のようになる。図２６に示すように、６回目の集約処理が完了した段階では、上記実施形態と同様、データを２つのグループに集約することができる。
【００６３】
ここで、複数キー集約処理全体の処理量の概算として、処理対象となるグループ数を用いると、初期状態から集約完了までの累計総グループ数は、本実施形態の場合、６１グループ（図２０参照）、比較例の場合、６６グループ（図２６参照）となる。すなわち、初期状態から集約完了までの累計総グループ数は、本実施形態のほうが少ないことが分かる。また、前の集約時から変動があったグループの累計は、本実施形態が１４であり（図２０参照）、比較例が１５である（図２６参照）ので、本実施形態のほうが少ないことが分かる。
【００６４】
更に、本実施形態の場合、一度集約されたデータ群は、それ以降分断されることが無いのに対し、比較例では図２１から図２２へ遷移する際のＩＤ＝０１３、０１４のように、一度集約されたデータ群が分断されることがある。このような点から、本実施形態の方が、グループ内での統計処理などを漸次的に計算するのに都合が良いことになる。
【００６５】
（別例について）
以下、図７とは異なる例について、図２７〜図３２に基づいて説明する。なお、図２８〜図３２では、Ｍａｐデータの近傍に、集約処理に用いるキー一覧リスト１６を併記するものとする（一点鎖線で示す箱）。
【００６６】
図２７には、図７の例と同様に３階層に分かれているものの、関連がループしており、親子関係が明確ではないデータの一例が示されている。なお、この例では２系統のループがあるが、Ｚ＝０１０１０１が共通して含まれているため、集約処理の結果、全てのデータが１グループに集約されるのが正しい集約結果である。
【００６７】
図２７のデータに対して本実施形態の処理を適用し、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、１回目の集約処理を行った結果が図２８（矢印の下側のデータ）である。
【００６８】
図２８では、Ｒｅｄｕｃｅ処理部１４は、それぞれ元のデータの主キーで集約している。この場合、Ｚ＝０１０１０１のみ複数のデータが集約される。また、各グループに未使用のキーが存在するため、Ｒｅｄｕｃｅ処理部１４は、キーを未使用のキーのうちの１つに変更し、２回目の集約を行う。図２９には、２回目の集約を行った結果（矢印の下側のデータ）が示されている。
【００６９】
同様に、Ｒｅｄｕｃｅ処理部１４が３回目の集約を行うと図３０の矢印の下側の状態となる。ここで、Ｚ＝０１０１０１のグループでは、各データの未使用のキーが無くなり、実体の無いデータの未使用キーはグループ内のデータの元キーと一致するものしかなくなる（図１０のステップＳ３６が否定される）。これにより、キー変更が一巡したことがわかるため、固定フラグを設定するとともに（ステップＳ４２）、グループ内の使用済みキーの中から、辞書式に評価して先頭となるキー（ここでは、Ｘ＝０１）を見つけ、次の集約キーとする（ステップＳ４４）。なお、辞書式に評価して先頭を見つける処理は、各キー種の関係から親子関係（階層構造）の最上位を見つける処理を意味する。
【００７０】
同様にして、Ｒｅｄｕｃｅ処理部１４が４回目の集約を行うと、図３１の状態となる。ここで、Ｘ＝０１に集約されたグループには、固定フラグが設定されたデータが含まれる（ステップＳ３２が肯定される）。このため、Ｒｅｄｕｃｅ処理部１４は、固定フラグが設定されていなかったデータにも固定フラグを設定する（ステップＳ４８）。
【００７１】
また、Ｙ＝０１０２のグループでも、使用可能性のあるキーは元キーと一致するものしかなくなる（図１０のステップＳ３６が否定される）ため、キー変更一巡となる。このため、Ｒｅｄｕｃｅ処理部１４は、次の集約キーをＸ＝０１とし、固定フラグを設定する（ステップＳ４２）。この結果、図３２に示すように、Ｒｅｄｕｃｅ処理部１４が５回目の集約を行うと、すべてのデータが固定フラグ付きでＸ＝０１に集約され、集約が完了する。この場合、前述したように、１グループに正確に集約されることになる。以上のように、図２７のようなデータの関係がループする場合であっても、本実施形態では、正確に、データを集約することが可能である。
【００７２】
以上詳細に説明したように、本実施形態の処理サーバ１０によると、Ｍａｐ処理部１２が行う、複数のデータそれぞれが有するキーを、集約に用いる集約キー、集約において未だ用いていない未使用キー、及び既に集約に用いた使用済みキーのいずれかに分類して、Ｍａｐデータに関連付けて分散ファイルシステム４０に記憶する処理（ステップＳ１２）と、Ｒｅｄｕｃｅ処理部１４が行う、記憶された複数のデータのうち、同一の集約キーに関連付けられたＭａｐデータを取得する（ステップＳ２６）とともに、取得したＭａｐデータ群に含まれる未使用キーを全て取得し（ステップＳ２８）、取得した未使用キーのうちの１つを次の集約キーとして決定し、取得したデータに関連付けて記憶された集約キーを次の集約キーに更新し（ステップＳ３８）、取得したデータに関連付けて記憶された未使用キーを取得した未使用キーから次の集約キーを除いた残りの未使用キーに更新する（ステップＳ４０）処理を、Ｒｅｄｕｃｅ処理部１４における集約キーの更新ができなくなるまで繰り返す。これにより、ＲＤＢ（関係データベース）を用いなくとも、処理対象のデータを参照するのみで、複数のＭａｐデータを集約することができる。これにより、性能・スケーラビリティ改善効果を最大限に得ることが可能となる。また、Ｍａｐ処理部１２とＲｅｄｕｃｅ処理部１４とが処理を繰り返し行うことで、データに関連のある範囲のキーがデータ間を伝達していくので、データ集約の漏れをなくすことができる。
【００７３】
また、本実施形態では、Ｒｅｄｕｃｅ処理部１４は、複数のＭａｐデータを集約する際に、更新を行う前の集約キーを集約キーとし、集計された（取得された）未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たなＭａｐデータとして生成するので（ステップＳ４０）、親子関係（階層関係）にある全ての階層の集約処理を同時に行うことが可能となる。これにより、処理時間の短縮を図ることが可能となる。
【００７４】
また、本実施形態では、Ｒｅｄｕｃｅ処理部１４は、集約キーを更新できなくなったデータの集約キーを、使用済みキーとしてＭａｐデータに関連付けられているキーのうち、親子関係（階層関係）の最上位にあるキーで更新するとともに、Ｍａｐデータに、集約キーのそれ以上の更新を禁止するフラグ（固定フラグ）を設定する（データに対応付けて固定フラグを記憶する）（ステップＳ４２、Ｓ４４）。これにより、集約キーの更新が一巡したときには、それ以降、集約キーは更新されなくなるので、集約キーの更新が一巡したときに発生し得る、処理の永久ループを防止することが可能となる。
【００７５】
また、本実施形態の分散処理システム１００は、上記のような処理サーバ１０を複数備えているので、複数のＭａｐデータを、複数の処理サーバ１０上で分散・並行的にMapReduce処理することが可能となる。
【００７６】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、処理装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【００７７】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００７８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００７９】
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【００８０】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１） 複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、を備え、前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返すことを特徴とする処理装置。
（付記２） 前記集約部は、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶することを特徴とする付記１に記載の処理装置。
（付記３） 前記関連付け部は、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付け、前記集約部は、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新することを特徴とする付記１又は２に記載の処理装置。
（付記４） 付記１〜３のいずれかに記載の処理装置を複数備え、複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行することを特徴とする分散処理システム。
（付記５） 複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、取得した前記未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させることを特徴とする処理プログラム。
（付記６） 前記集約する処理では、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶する処理をコンピュータに実行させることを特徴とする付記５に記載の処理プログラム。
（付記７） 前記関連付ける処理では、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付ける処理をコンピュータに実行させ、前記集約する処理では、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、コンピュータに実行させることを特徴とする付記５又は６に記載の処理プログラム。
【符号の説明】
【００８１】
１０ 処理サーバ（処理装置）
１２ Ｍａｐ処理部（関連付け部）
１４ Ｒｅｄｕｃｅ処理部（集約部）
９０ ＣＰＵ（コンピュータ）
９６ ＨＤＤ（記憶部）
１００ 分散処理システム
【技術分野】
【０００１】
本件は、処理装置、分散処理システム、及び処理プログラムに関する。
【背景技術】
【０００２】
大量データを対象にした分析処理には、非常に長い処理時間を要する。これに対し、最近では、複数のマシンを用いて分散・並列処理を行うことで処理時間を短縮するアプローチがとられている。分散・並列処理としては、例えば、MapReduceアルゴリズムを用いた方法（例えば、非特許文献１参照）がある。また、MapReduceアルゴリズムのオープンソース実装として、Apache Hadoopが存在している。
【０００３】
MapReduceは、主に元のデータを多数のキーと値のセットに分割する「Ｍａｐ処理」と、それらのキーと値のセットをあるルールによって集約する「Ｒｅｄｕｃｅ処理」とによって構成される。Ｍａｐ処理及びＲｅｄｕｃｅ処理の各処理は、それぞれ複数並列に実行可能であるため、それらを複数の処理マシン（サーバなど）に割り当てることにより、複数マシンの処理性能を活用することができる。
【０００４】
ただし、MapReduceによる分散・並列処理の効果を高めるには、それぞれのＭａｐ処理、Ｒｅｄｕｃｅ処理の独立性を高くし、他の部分に依存せずに処理を行えるようにする必要がある。
【０００５】
分析処理の一種として、大量のデータ群の中から、関係のあるデータをグルーピングするものがある。例えば、図３３（ａ）に示すように、ある時期に行われた業務ログを、図３３（ｂ）に示すように、一連となっている業務フロー単位にグルーピングする場合などである。グルーピングの処理では、あるグループのデータ群を扱う際、別のグループのデータを考慮する必要が無いため、各グループの処理を複数サーバに分散させることにより、効率的に処理が行える。
【０００６】
なお、図３３（ａ）のように一連の業務フローが１つのキー種（図３３（ａ）ではフローＩＤ）によって示されるデータをグルーピングする際には、MapReduceを用いることによってグルーピングは容易に達成される。MapReduceを行う処理マシンでは、あるキー値を持つデータ群を一箇所に集約する機能を標準で有しているためである。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Jeffrey Dean and Sanjay Ghemawat. MapReduce: Simplified Data Processing on Large Clusters OSDI 2004
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、図３４（ａ）のように、一連の業務フローを示すキーが複数（図３４（ａ）では３種）存在する場合もあり得る。なお、図３４（ｂ）は、図３４（ａ）のデータを集約した例を示している。このような場合には、単純にはグルーピングを行うことができない。複数のキー種を用いて関連のあるデータ群を集約する処理（以下、「複数キー集約処理」と呼ぶ）では、どのキーの組み合わせが一連のデータ群を示すのかが、データ全体を見ないと完全には確定しないからである。例えば、図３４（ａ）の場合、伝票番号＝001で集約しようとすると、伝票明細詳細テーブルのデータを集約できない。一方、伝票明細詳細番号＝001-001-001で集約する場合、伝票テーブルのデータを集約できない。
【０００９】
この場合、処理の進展に応じてキー値の組み合わせの情報を最新化しながら集約処理を進めるような工夫が必要であり、また、最新化する処理が不十分な場合には、データの集約漏れが発生する場合がある。
【００１０】
これに対し、キー種間の関連を管理する表をＲＤＢ（関係データベース(Relational Database））などに作成することも考えられる。しかるに、分散・並列処理する各処理マシンが共通に参照・更新する箇所があると、分散処理の性能・スケーラビリティが劣化するおそれがある。
【００１１】
そこで本件は上記の課題に鑑みてなされたものであり、性能・スケーラビリティの向上及びデータ集約漏れを防止することが可能な処理装置、分散処理システム、及び処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
本明細書に記載の処理装置は、複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、を備え、前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返す処理装置である。
【００１３】
本明細書に記載の分散処理システムは、本明細書に記載の処理装置を複数備え、複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行する分散処理システムである。
【００１４】
本明細書に記載の処理プログラムは、複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、取得した前記未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させる処理プログラムである。
【発明の効果】
【００１５】
本明細書に記載の処理装置、分散処理システム、及び処理プログラムは、性能・スケーラビリティの向上、及びデータ集約漏れを防止することができるという効果を奏する。
【図面の簡単な説明】
【００１６】
【図１】一実施形態に係る分散処理システムの構成を概略的に示す図である。
【図２】処理サーバのハードウェア構成を示す図である。
【図３】処理サーバの機能ブロック図である。
【図４】MapReduce処理の基本的な処理内容について説明するための図である。
【図５】MapReduce処理の一連の流れについて示すフローチャートである。
【図６】図６（ａ）は、Ｍａｐ処理における入力データの一例を示す図であり、図６（ｂ）は、１つのＭａｐデータのキー及び値の具体的な内容を示す図である。
【図７】集約対象のＭａｐデータの一例を示す図である。
【図８】図８（ａ）〜図８（ｃ）は、図７の最下層のテーブルについてＭａｐ処理を行った場合の例を説明するための図である。
【図９】ステップＳ１４の具体的処理を示すフローチャート（その１）である。
【図１０】ステップＳ１４の具体的処理を示すフローチャート（その２）である。
【図１１】図１１（ａ）は集約キーがＺ＝０１０１０１の集約グループを示す図であり、図１１（ｂ）は、図１１（ａ）の集約グループのキー一覧リストであり、図１１（ｃ）は、図１１（ａ）の集約グループのデータ一覧リストである。
【図１２】図１０のステップＳ３８の処理を説明するための図である。
【図１３】１回目の集約により、同階層で同一のキー値を持つデータ群が集約された様子を示した図である。
【図１４】図１４（ａ）〜図１４（ｃ）は、集約キーがＹ＝０１０１のＭａｐデータを集約する処理を説明するための図（リスト１６，１８）が示されている。
【図１５】２回目の集約処理を行った後の状態を示す図である。
【図１６】３回目の集約処理を行った後の状態を示す図である。
【図１７】４回目の集約処理を行った後の状態を示す図である。
【図１８】５回目の集約処理を行った後の状態を示す図である。
【図１９】６回目の集約処理を行った後の状態を示す図である。
【図２０】７回目の集約処理を行った後の状態を示す図である。
【図２１】比較例において１回目の集約処理を行った後の状態を示す図である。
【図２２】比較例において２回目の集約処理を行った後の状態を示す図である。
【図２３】比較例において３回目の集約処理を行った後の状態を示す図である。
【図２４】比較例において４回目の集約処理を行った後の状態を示す図である。
【図２５】比較例において５回目の集約処理を行った後の状態を示す図である。
【図２６】比較例において６回目の集約処理を行った後の状態を示す図である。
【図２７】別例における図７に対応する図である。
【図２８】別例において１回目の集約処理を行った後の状態を示す図である。
【図２９】別例において２回目の集約処理を行った後の状態を示す図である。
【図３０】別例において３回目の集約処理を行った後の状態を示す図である。
【図３１】別例において４回目の集約処理を行った後の状態を示す図である。
【図３２】別例において５回目の集約処理を行った後の状態を示す図である。
【図３３】従来例を説明するための図（その１）である。
【図３４】従来例を説明するための図（その２）である。
【発明を実施するための形態】
【００１７】
以下、一実施形態について、図１〜図３２に基づいて詳細に説明する。図１には、分散処理システム１００の構成が概略的に示されている。本実施形態の分散処理システム１００では、複数のキーが与えられたデータを集約する「複数キー集約処理」を行うこととし、当該処理では、MapReduceアルゴリズムを適用するものとする。ここで、集約とは、同一のキーのデータを取得することを意味する。
【００１８】
分散処理システム１００は、図１に示すように、処理を実行するｎ台の処理装置としての処理サーバ１０と、各処理サーバ１０の処理を管理する管理サーバ２０と、を備える。各処理サーバ１０と管理サーバ２０は、ＬＡＮ（Local Area Network）、インターネットなどのネットワーク３０に接続されている。
【００１９】
図２には、処理サーバ１０のハードウェア構成が示されている。図２に示すように、処理サーバ１０は、ＣＰＵ９０、ＲＯＭ９２、ＲＡＭ９４、記憶部（ここではＨＤＤ（Hard Disk Drive））９６、入出力部９７、可搬型記憶媒体用ドライブ９９等を備えている。これら処理サーバ１０の構成各部は、バス９８に接続されている。処理サーバ１０では、ＲＯＭ９２あるいはＨＤＤ９６に格納されているプログラム（処理プログラム）、又は可搬型記憶媒体用ドライブ９９が可搬型記憶媒体９１から読み出したプログラム（処理プログラム）をＣＰＵ９０が実行することにより、図３の各部の機能が実現される。
【００２０】
図１に戻り、各処理サーバ１０のディスク（ＨＤＤ９６）は、仮想的に１つのディスクに見える分散ファイルシステム４０に組み込まれている。なお、図示の便宜上、図１では、ＨＤＤ９６を各処理サーバ１０の外側に出して示している。なお、図１の構成図は、MapReduceのオープンソース実装であるHadoopを用いる場合の一例を示すものであり、管理サーバ２０や分散ファイルシステム４０は、分散処理システム１００内に必ずしも設けなくてもよい。
【００２１】
図３には、処理サーバ１０の機能ブロック図が示されている。処理サーバ１０は、図３に示すように、関連付け部としてのＭａｐ処理部１２、及び集約部としてのＲｅｄｕｃｅ処理部１４、としての機能を有する。また、ＨＤＤ９６により、キー一覧リスト１６を格納する領域と、データ一覧リスト１８を格納する領域とが用意されている。
【００２２】
Ｍａｐ処理部１２は、分散ファイルシステム４０に格納されているデータを用いて、後述するＭａｐ処理を実行する。Ｒｅｄｕｃｅ処理部１４は、Ｍａｐ処理部１２においてＭａｐ処理されたデータを用いて、後述するＲｅｄｕｃｅ処理を行う。キー一覧リスト１６は、図１１（ｂ）に示すようなリストである。データ一覧リスト１８は、図１１（ｃ）に示すようなリストである。
【００２３】
次に、MapReduce処理の基本的な処理内容について、図４に基づいて、説明する。
【００２４】
MapReduce処理では、分散ファイルシステム４０上の処理対象のデータを、キーと値からなるＭａｐデータに分割する処理（Ｍａｐ処理）と、キーの値に応じてＭａｐデータを纏める処理（Ｒｅｄｕｃｅ処理）とを、各処理サーバ１０において分散・並列的に行う。
【００２５】
例えば、各処理サーバ１０において分散・並列的に行われたＭａｐ処理によって、図４の上段に示すようなＭａｐデータが生成されたとする。この場合、各処理サーバ１０又は管理サーバ２０は、各Ｍａｐデータのキーの値に対し、一意なハッシュ値を公知の計算方法により計算し、そのハッシュ値を処理サーバ数（図４では３）で割った剰余（０〜２）を求める。この場合、予め、各処理サーバ１０に関し、対応する剰余値を、図４の下段に示す番号（０〜２）で決めておくことで、各Ｍａｐデータを処理する処理サーバ１０を決定することができる。なお、同一の値のキーに対しては常に同一のハッシュ値が得られるため、同一のキー値を持ったＭａｐデータ群は１つの処理サーバに集められる。また、ハッシュ値が偏りのない前提であれば、各Ｍａｐデータの処理を各サーバに偏りなく分散させることができる。なお、上述したハッシュ値から一意に処理サーバを決定する方法は、最も単純な例である。したがって、例えば、ハッシュ値に加えて、その時点の処理サーバの負荷を考慮に入れるなどして、より高度に処理サーバを決定することとしてもよい。
【００２６】
各処理サーバ１０（Ｒｅｄｕｃｅ処理部１４）は、集められたＭａｐデータの集約キー（以下、単に「キー」とも呼ぶ）の値を参照する。そして、各処理サーバ１０（Ｒｅｄｕｃｅ処理部１４）は、同一のキー値を持ったＭａｐデータ（Ｍａｐデータ群）を１つのグループとし、そのグループに対してＲｅｄｕｃｅ処理を行う（図４の下段におけるキー＝ＣＣＣのグループ参照）。なお、管理サーバ２０は、各処理サーバ１０の状態を把握しているため、各処理サーバ１０におけるＭａｐ処理やＲｅｄｕｃｅ処理が完了したかどうかについても把握している。このため、管理サーバ２０は、Ｒｅｄｕｃｅ処理の結果を受けて、再度各処理サーバ１０にＭａｐ処理を実行させるなどすることで、MapReduce処理を繰り返し行うことができる。
【００２７】
次に、本実施形態の分散処理システム１００における、複数キー集約処理の詳細について、説明する。
【００２８】
なお、単一のキーでの集約であれば、上述したMapReduceの基本的な処理を行うことで実現できる（図３３参照）。しかし、複数のキーを用いた集約の場合、MapReduce処理を複数回繰り返してデータを集約する必要がある。
【００２９】
前述の通り、同じ集約キー（キー）を持ったＭａｐデータは、同じサーバ・同じグループへ集約される。このため、本実施形態では、キー値を変更しながら、複数回のMapReduce処理を繰り返すことで、段階的にデータを集約するアプローチを採用する。なお、キー値を変更した場合には、ハッシュ値も変わるので、キー値変更後のデータは、別の処理サーバで処理される可能性もある。
【００３０】
図５は、複数キー集約処理における具体的な処理の流れを示すフローチャートである。図５の複数キー集約処理では、Ｍａｐ処理とＲｅｄｕｃｅ処理とが必要回数繰り返される。
【００３１】
図５の処理では、まず、ステップＳ１０において、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、繰り返し制御用のカウンタとして、「キー変更カウンタ」を用意し、これを０に初期化する。なお、キー変更カウンタは、各処理サーバ１０が更新することができる。各処理サーバ１０では、Ｒｅｄｕｃｅ処理が終わったことを契機にキー変更カウンタを更新する。
【００３２】
次いで、ステップＳ１２では、各処理サーバ１０のＭａｐ処理部１２が、Ｍａｐ処理を実行する。このステップＳ１２では、Ｍａｐ処理部１２が、分散ファイルシステム４０上に存在する、入力データやＲｅｄｕｃｅ処理結果の中間生成データから、キー（集約キー）と値の組み合わせであるＭａｐデータ群を生成し、分散ファイルシステム４０に記憶する。
【００３３】
ここで、図５のステップＳ１２を実行するのが１回目（初回）である場合には、Ｍａｐ処理部１２は、入力データ（図６（ａ）に示すようなデータ）の各行の主キー値をキー（集約キー）とする（図６（ｂ）参照）。なお、主キー値がどの値であるかは、あらかじめ定義しておくものとする。図６（ａ）では、主キー値は最左列の値である。また、Ｍａｐ処理部１２は、図６（ｂ）に示すように、値に、行全体の情報とキーの管理情報とを設定して、Ｍａｐデータを生成する。なお、Ｍａｐ処理は各行独立に実行可能であるため、行数を処理サーバ１０の数で分割して、各処理サーバ１０で分散して実行するものとする。ここで、Ｍａｐデータのキーの管理情報は、図６（ｂ）に示すように、最初のキーを保存する「元キー」、未使用のキーを保存する「未使用キー」、過去に使用したキーを保存する「使用済みキー」、キー変更の必要が無いことを示す「固定フラグ」などである。
【００３４】
図７は、集約対象のＭａｐデータの一例を示している。図７に示す例では、データは３階層に分類されており、１９個のデータ実体が存在する。最上層ではＸが主キーとなっており、０１〜０５までのキー値が存在する。２番目の層ではＹが主キーとなっており、０１０１〜０１０５までのキー値が存在する。なお、２番目の層のデータは、関連キーとしてＸも有しているため、最上層のデータと関連付けられている。また、最下層の主キーはＺであり、０１０１０１〜０１０１０６までのキー値が存在する。なお、最下層のデータ（図６（ａ）のデータと同一）は、関連キーとしてＹを有しているため、２番目の層のデータと関連付けられている。
【００３５】
図７の例で特徴的なのは、関連の親子関係が複雑である点である。通常、このような構造のデータでは、一般には親と子の数の関係は１対多である。この点、図７の破線よりも右側のデータはそのような関係になっているが、図７の破線よりも左側では必ずしもそのような関係になっていない。例えばＺ＝０１０１０１のデータはＹ＝０１０１にもＹ＝０１０２にも関連している。親と子が常に１対多の関係であれば、下層のキーから順にＺ→Ｙ→Ｘと３回集約すればすべてのグループが正しく集約される。しかしながら、図７のようなケースではその方法では集約漏れするデータが生じるおそれがある。
【００３６】
ここで、図７の最下層のデータ（Ｍａｐデータ）の生成方法（Ｍａｐ処理方法）について、図８（ａ）〜図８（ｃ）に基づいて説明する。図８（ａ）は、最下層のデータのテーブル（元データ）である。図８（ａ）の元データは、管理サーバ２０又はいずれかの処理サーバ１０のＭａｐ処理部１２によって、図８（ｂ）に示すように、処理サーバ数（図８（ｂ）では、処理サーバ数が２であるものとする）に分割される。そして、各処理サーバ１０では、分割されたうちの１つのテーブルについて、Ｍａｐ処理を行い、図８（ｃ）に示すように、Ｍａｐデータを生成する。このような処理により生成されるＭａｐデータが、図７の最下層の７つのデータとなる。
【００３７】
図５に戻り、次のステップＳ１４では、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、Ｒｅｄｕｃｅ処理を実行する。このＲｅｄｕｃｅ処理では、まず、管理サーバ２０が、同一のキー値を持つＭａｐデータ群を１つの処理サーバ１０に集約する。そして、Ｒｅｄｕｃｅ処理部１４は、図９、図１０のフローチャートに沿った処理を実行する。
【００３８】
ここで、各処理サーバ１０に対する入力は、図７で示される構造を有するＭａｐデータの集合であり、キー値が同一のデータ群であるものとする。なお、キー値が同一のデータ群を、以下においては、「グループ」と呼ぶ。また、以下の説明では、図９、図１０の処理の説明と併せて、図１１（ａ）に示すＭａｐデータ（特に、図１１（ａ）において集約キーがＺ＝０１０１０１のデータ）のＲｅｄｕｃｅ処理を例にとり、説明する。
【００３９】
図９の処理では、まず、ステップＳ２０において、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、グループのデータ一覧リスト１８（図１１（ｃ）参照）、及びキー一覧リスト１６（図１１（ｂ）参照）を初期化する。次いで、ステップＳ２２では、Ｒｅｄｕｃｅ処理部１４が、グループの集約キーを使用済みキーとしてキー一覧リスト１６へ追加する（図１１（ｂ）の最下段参照）。
【００４０】
次いで、ステップＳ２４では、Ｒｅｄｕｃｅ処理部１４が、処理対象のＭａｐデータ（例えば、図１１（ａ）の１番のデータ）を取得する。次いで、ステップＳ２６では、Ｒｅｄｕｃｅ処理部１４が、Ｍａｐデータをグループのデータ一覧リスト１８へコピーする（図１１（ｃ）の１番のデータ参照）。次いで、ステップＳ２８では、Ｒｅｄｕｃｅ処理部１４が、ステップＳ２６でコピーしたＭａｐデータ中の未使用／使用済みキー値をグループのキー一覧リスト１６へコピーする。なお、ここでは、図１１（ｂ）のキー一覧リスト１６において、未使用キーの欄にＹ＝０１０１がコピーされるが、使用済みキーは存在していないため、使用済みキーの欄には何もコピーされない。
【００４１】
次いで、ステップＳ３０では、Ｒｅｄｕｃｅ処理部１４が、未処理のＭａｐデータが存在するか否かを判断する。ここでの判断が肯定された場合には、ステップＳ２４に戻り、ステップＳ２４〜Ｓ２８の処理を繰り返す。その結果、ステップＳ３０の判断が否定される段階では、図１１（ｃ）のデータ一覧リスト１８に、２番のデータがコピーされるとともに、図１１（ｂ）のキー一覧リスト１６に、未使用キーとして、Ｙ＝０１０２がコピーされる。このように、Ｒｅｄｕｃｅ処理部１４は、Ｍａｐデータ群から、各データを順次取得（１つずつ取得）して、データ一覧リスト１８及びキー一覧リスト１６にデータ、未使用キーや使用済みキーをコピーする。なお、キー一覧リスト１６における、未使用キーの欄と使用済みキーの欄は排他的ではなく、未使用キーの欄と使用済みキーの欄に同じキーを格納することもできる。一方、未使用キーの欄の中で重複したキー、あるいは使用済みキーの欄の中で重複したキーがある場合には、１つのみ残して重複するキーを削除してもよい。
【００４２】
以上のようにして、ステップＳ３０の判断が否定された場合には、図１０のステップＳ３２に移行する。
【００４３】
図１０のステップＳ３２では、Ｒｅｄｕｃｅ処理部１４が、データ一覧リスト１８の中に固定フラグが設定されたデータが存在するか否かを判断する。ここでの判断が否定された場合には、ステップＳ３４に移行する。なお、ステップＳ３２の判断が肯定された場合には、ステップＳ４８（このステップについては後述）に移行する。ここで、図１１（ｃ）の例では、データ一覧リスト１８に、固定フラグが設定されたデータは存在していない（全てｆａｌｓｅ）ので、ステップＳ３２の判断は肯定されて、ステップＳ３４に移行する。
【００４４】
ステップＳ３４に移行した場合、Ｒｅｄｕｃｅ処理部１４は、キー一覧リスト１６の中に未使用のキーが存在するか否かを判断する。図１１（ｂ）の例では、キー一覧リスト１６に、未使用のキーが存在しているので、ステップＳ３４の判断は肯定され、ステップＳ３６に移行する。
【００４５】
ステップＳ３６に移行した場合、Ｒｅｄｕｃｅ処理部１４は、データ一覧リスト１８中のどの元キーとも一致しない未使用キーが存在するか否かを判断する。図１１（ｂ）の例では、キー一覧リスト１６に、データ一覧リスト１８中のどの元キーとも一致しない未使用キーが２つ存在しているので、ここでの判断は肯定され、ステップＳ３８に移行する。
【００４６】
ステップＳ３６の判断が肯定され、ステップＳ３８に移行した場合、Ｒｅｄｕｃｅ処理部１４は、実体を持つ全データのキーを、未使用キーの欄から一つ選択したキーに書き換える。また、Ｒｅｄｕｃｅ処理部１４は、選択したキーを除き、グループのキー一覧リスト１６の内容を未使用／使用済みキーに格納する。すなわち、ステップＳ３８では、図１２に示すように、Ｒｅｄｕｃｅ処理部１４は、データ一覧リスト１８に含まれるＭａｐデータの１番のデータのキーと２番のデータのキーをＹ＝０１０１に書き換える。また、Ｒｅｄｕｃｅ処理部１４は、キー一覧リスト１６の未使用キーからＹ＝０１０１を除いた結果、すなわちＹ＝０１０２を各データの未使用キーに格納する。また、キー一覧リスト１６の使用済みキーであるＺ＝０１０１０１を各データの使用済みキーに格納する。
【００４７】
次いで、ステップＳ４０では、Ｒｅｄｕｃｅ処理部１４が、実体を持たないＭａｐデータが存在しない場合、新たに実体を持たないキーのみのＭａｐデータを１つ生成する。例えば、図１２において３番のデータとして示すデータを生成する。この場合、書き換える前のキー（＝集約キー）をキーとし、グループの未使用キー一覧の内容（図１１（ｂ））を未使用キーの欄に格納する。図１２の３番のデータでは、キーとしてグループの集約キーであるＺ＝０１０１０１を設定し、未使用キーにはグループのキー一覧リスト１６の未使用キーであるＹ＝０１０１とＹ＝０１０２を設定する。なお、使用済みキーの設定は必要なく、固定フラグは「false」とし、データ本体は空とする。
【００４８】
次いで、ステップＳ４６では、Ｒｅｄｕｃｅ処理部１４は、キー変更カウンタを１だけインクリメントする。次いで、ステップＳ５０では、Ｒｅｄｕｃｅ処理部１４が、図１に示す分散ファイルシステム４０上の、Ｍａｐデータ群の中間ファイルへの出力を行い、その後、図５のステップＳ１６に移行する。なお、ステップＳ５０で出力されるＭａｐデータ群は、図１２に示すデータである。
【００４９】
図１３は、１回目の集約により、同階層で同一のキー値を持つデータ群（グループ）が集約された様子を示した図である。なお、図１３に示すように、１回目の集約によって、Ｚ＝０１０１０１以外の２つのキー（Ｙ＝０１０１、Ｙ＝０１０３）のＭａｐデータも集約されている。この図において、データを示す箱（矩形枠）の左上に示す値（Ｚ＝０１０１０１等）が、各集約グループを示しており、その値の下に隣接して配置された箱の一群がグループのデータを示している。また、箱の内部の「未使用キー」は、図１１（ｂ）におけるキー一覧リスト１６の未使用キーの欄を示している。更に、箱の内部の「キー」の矢印の左側はその集約における集約キー、右側は未使用キーの中から一つ選択したキーで、次の集約において集約キーとなる値を示している。なお、図１３では、図示及び説明の簡単のため、使用済みキーは表示していない。なお、図１２のように、Reduce処理の終盤でキー情報のみのＭａｐデータが生成されている（図１２のデータ「３」）が、これは再集約（２回目以降の集約）が実施されたときにのみ意味を持つものなので、図１３では図示していない。なお、図１５において破線で示されている箱が、１回目の集約で生成されたキー情報のみのＭａｐデータである。
【００５０】
なお、図１０の処理において、キー一覧リスト１６の中に未使用のキーが存在していない場合（例えば、図１３の最上段のデータ等の場合）には、ステップＳ３４の判断が否定される。ステップＳ３４の判断が否定された場合には、Ｒｅｄｕｃｅ処理部１４は、キー変更カウンタを０に維持したまま、ステップＳ５０に移行し、Ｍａｐデータ群の中間ファイルへの出力を行った後、図５のステップＳ１６に移行する。
【００５１】
図５に戻り、次のステップＳ１６に移行すると、管理サーバ２０は、Ｒｅｄｕｃｅ処理のキー変更カウンタの集計値が１以上か否かを判断する。上記例では、いずれかのグループで集約キーの変更が発生しており、図１０のステップＳ４６を経ている。したがって、キー変更カウンタの集計値は１以上となるため、ステップＳ１６の判断は肯定され、ステップＳ１０に戻る。そして、ステップＳ１０〜Ｓ１６の処理（再度のMapReduce処理）を繰り返す。
【００５２】
なお、図１０の処理において、データ一覧中のどの元キーとも一致しない未使用キーが存在しない場合には、ステップＳ３６の判断が否定される。この場合、キー値の変更が一巡したとみなせるので、それ以上の変更は無意味となる。したがって、この場合には、ステップＳ４２に移行し、Ｒｅｄｕｃｅ処理部１４が、データ一覧リスト１８中の全データに対し、固定フラグを設定する。そして、ステップＳ４４において、Ｒｅｄｕｃｅ処理部１４は、データ一覧中の全データのキーを、使用済みキー一覧の中から、辞書式に判定して先頭となるキー値を変更する。なお、これらステップＳ４２、Ｓ４４の具体的処理については、後述する。その後は、上記と同様、ステップＳ４６、Ｓ５０を経て、図５のステップＳ１６に移行する。
【００５３】
また、図１０のステップＳ３２において、データ一覧リスト１８の中に固定フラグが設定されたデータが存在していた場合には、ステップＳ４８に移行する。このステップＳ４８では、Ｒｅｄｕｃｅ処理部１４が、データ一覧中の全データに対し、固定フラグを設定することで、その時点の集約キーをそのまま用いて再集約可能な状態にする。そして、ステップＳ５０において、Ｍａｐデータ群の中間ファイルへの出力を行った後、図５のステップＳ１６に移行する。
【００５４】
次に、２回目の集約処理について説明する。図１４（ａ）〜図１４（ｃ）には、集約キーがＹ＝０１０１のＭａｐデータを集約する処理を説明するための図（リスト１６，１８）が示されている。図１４（ｂ）のデータ一覧リストのうち１、２番目のデータは、図１２の１、２番目のデータと同一である。これに対し、３番目のデータは、図１３のＹ＝０１０１のグループを集約した際に生成されたデータ実体のないデータ（図１５の符号Ｄａで示す破線の箱参照）である。また、これら３つのデータからは、キー一覧リスト１６として、図１４（ａ）のようなリストが得られる。これら、図１４（ａ）のキー一覧リスト及び図１４（ｂ）のデータ一覧リストを用いて図１０の処理を行うと、図１４（ｃ）のような３つのデータを得ることができる。このような２回目の集約処理を行った後の状態が、図１５に示されている。図１５に示すように、２回目の集約処理の結果、集約キーがＹ＝０１０１のＭａｐデータ以外のＭａｐデータも集約されていることが分かる。
【００５５】
以下、同様に集約処理を繰り返すと、３回目の集約処理の結果は、図１６のようになる。また、４回目の集約処理の結果は、図１７のようになり、５回目の集約処理の結果は、図１８のようになり、６回目の集約処理の結果は、図１９のようになる。そして、７回目の集約処理の結果、図２０のようになる。図２０の状態では全グループに未使用キーが存在しなくなるため（全処理サーバ１０においてステップＳ３４が否定されるため）、キー変更カウンタは０のままとなる。この場合、図５のステップＳ１６の判断が否定され、ステップＳ１８に移行する。そして、管理サーバ２０は、ステップＳ１８において集約処理を完了する。
【００５６】
本実施形態では、上記のようなMapReduce処理を行うことで、図２０に示すように、Ｘ＝０４のグループとＸ＝０５の２グループとなる。これにより、複数のＭａｐデータを、図７の状態から正確に（集約漏れなく）２つのグループに集約できたことになる。
【００５７】
（比較例）
ここで、比較例（従来法を用いて、図７のデータを集約する場合）について説明する。なお、以下の処理は、各処理サーバ１０が行うものとする。
【００５８】
従来法としては、各データは変更可能なキー、不変の関連キーリスト（データにおいて定義されているキー）、再集約のフラグを兼ねる変更可能な予約関連キーを有することとする。また、上述した実施形態で用いたデータ実体を持たないキー値のみのデータは用いていない。従来法では、実体のないデータを用いないことを理由に、集約処理を全階層同時に行うことはできないため、キー値の種類毎に下層の方から順に集約する必要が生じる。
【００５９】
図２１には、元データの主キーをキー、関連キーを関連キーリストに格納し、最下層のキーであるＺを集約キーとして１回目の集約を行った結果が示されている。なお、図２１及びこれ以降の図面では、各データの識別のため、処理には使用しないＩＤを示している。図２１では、Ｚ＝０１０１０１のグループのみ、複数の関連キーを含んでいる。このように、グループ内に複数の関連キーが存在する場合、そのグループのデータには予約関連キーが設定される。予約関連キーの値は、そのグループの集約キーとなる。従って、Ｚ＝０１０１０１のグループではＺ＝０１０１０１が予約関連キーとなる。また、１回目の集約が行われたデータ又はグループのキーは、関連キーに変更される。
【００６０】
次いで、２回目の集約では、２番目の層のキーであるＹでの集約が行われる。その結果が図２２に示されている。ここで、図２２に示すように、Ｙ＝０１０１とＹ＝０１０２のグループには、１回目の集約時に予約関連キーを設定したデータが含まれている。このため、次の３回目の集約では、最上層のキーではなく、予約関連キーで集約が行われる。一方、予約関連キーが設定されていないグループについては、２回目と同じキー値で再度集約が行われる。
【００６１】
３回目の集約結果が図２３に示されている。予約関連キーでの集約を終えたので、次の集約は最上層のキーであるＸでの集約となるが、Ｚ＝０１０１０１とＹ＝０１０３のグループには複数のＸのキー値が含まれるため、各データに予約関連キーが設定される。
【００６２】
以下、上記と同様の処理が繰り返されることにより、４回目の集約処理の結果、図２４のようになり、５回目の集約処理の結果、図２５のようになり、６回目の集約処理の結果、図２６のようになる。図２６に示すように、６回目の集約処理が完了した段階では、上記実施形態と同様、データを２つのグループに集約することができる。
【００６３】
ここで、複数キー集約処理全体の処理量の概算として、処理対象となるグループ数を用いると、初期状態から集約完了までの累計総グループ数は、本実施形態の場合、６１グループ（図２０参照）、比較例の場合、６６グループ（図２６参照）となる。すなわち、初期状態から集約完了までの累計総グループ数は、本実施形態のほうが少ないことが分かる。また、前の集約時から変動があったグループの累計は、本実施形態が１４であり（図２０参照）、比較例が１５である（図２６参照）ので、本実施形態のほうが少ないことが分かる。
【００６４】
更に、本実施形態の場合、一度集約されたデータ群は、それ以降分断されることが無いのに対し、比較例では図２１から図２２へ遷移する際のＩＤ＝０１３、０１４のように、一度集約されたデータ群が分断されることがある。このような点から、本実施形態の方が、グループ内での統計処理などを漸次的に計算するのに都合が良いことになる。
【００６５】
（別例について）
以下、図７とは異なる例について、図２７〜図３２に基づいて説明する。なお、図２８〜図３２では、Ｍａｐデータの近傍に、集約処理に用いるキー一覧リスト１６を併記するものとする（一点鎖線で示す箱）。
【００６６】
図２７には、図７の例と同様に３階層に分かれているものの、関連がループしており、親子関係が明確ではないデータの一例が示されている。なお、この例では２系統のループがあるが、Ｚ＝０１０１０１が共通して含まれているため、集約処理の結果、全てのデータが１グループに集約されるのが正しい集約結果である。
【００６７】
図２７のデータに対して本実施形態の処理を適用し、各処理サーバ１０のＲｅｄｕｃｅ処理部１４が、１回目の集約処理を行った結果が図２８（矢印の下側のデータ）である。
【００６８】
図２８では、Ｒｅｄｕｃｅ処理部１４は、それぞれ元のデータの主キーで集約している。この場合、Ｚ＝０１０１０１のみ複数のデータが集約される。また、各グループに未使用のキーが存在するため、Ｒｅｄｕｃｅ処理部１４は、キーを未使用のキーのうちの１つに変更し、２回目の集約を行う。図２９には、２回目の集約を行った結果（矢印の下側のデータ）が示されている。
【００６９】
同様に、Ｒｅｄｕｃｅ処理部１４が３回目の集約を行うと図３０の矢印の下側の状態となる。ここで、Ｚ＝０１０１０１のグループでは、各データの未使用のキーが無くなり、実体の無いデータの未使用キーはグループ内のデータの元キーと一致するものしかなくなる（図１０のステップＳ３６が否定される）。これにより、キー変更が一巡したことがわかるため、固定フラグを設定するとともに（ステップＳ４２）、グループ内の使用済みキーの中から、辞書式に評価して先頭となるキー（ここでは、Ｘ＝０１）を見つけ、次の集約キーとする（ステップＳ４４）。なお、辞書式に評価して先頭を見つける処理は、各キー種の関係から親子関係（階層構造）の最上位を見つける処理を意味する。
【００７０】
同様にして、Ｒｅｄｕｃｅ処理部１４が４回目の集約を行うと、図３１の状態となる。ここで、Ｘ＝０１に集約されたグループには、固定フラグが設定されたデータが含まれる（ステップＳ３２が肯定される）。このため、Ｒｅｄｕｃｅ処理部１４は、固定フラグが設定されていなかったデータにも固定フラグを設定する（ステップＳ４８）。
【００７１】
また、Ｙ＝０１０２のグループでも、使用可能性のあるキーは元キーと一致するものしかなくなる（図１０のステップＳ３６が否定される）ため、キー変更一巡となる。このため、Ｒｅｄｕｃｅ処理部１４は、次の集約キーをＸ＝０１とし、固定フラグを設定する（ステップＳ４２）。この結果、図３２に示すように、Ｒｅｄｕｃｅ処理部１４が５回目の集約を行うと、すべてのデータが固定フラグ付きでＸ＝０１に集約され、集約が完了する。この場合、前述したように、１グループに正確に集約されることになる。以上のように、図２７のようなデータの関係がループする場合であっても、本実施形態では、正確に、データを集約することが可能である。
【００７２】
以上詳細に説明したように、本実施形態の処理サーバ１０によると、Ｍａｐ処理部１２が行う、複数のデータそれぞれが有するキーを、集約に用いる集約キー、集約において未だ用いていない未使用キー、及び既に集約に用いた使用済みキーのいずれかに分類して、Ｍａｐデータに関連付けて分散ファイルシステム４０に記憶する処理（ステップＳ１２）と、Ｒｅｄｕｃｅ処理部１４が行う、記憶された複数のデータのうち、同一の集約キーに関連付けられたＭａｐデータを取得する（ステップＳ２６）とともに、取得したＭａｐデータ群に含まれる未使用キーを全て取得し（ステップＳ２８）、取得した未使用キーのうちの１つを次の集約キーとして決定し、取得したデータに関連付けて記憶された集約キーを次の集約キーに更新し（ステップＳ３８）、取得したデータに関連付けて記憶された未使用キーを取得した未使用キーから次の集約キーを除いた残りの未使用キーに更新する（ステップＳ４０）処理を、Ｒｅｄｕｃｅ処理部１４における集約キーの更新ができなくなるまで繰り返す。これにより、ＲＤＢ（関係データベース）を用いなくとも、処理対象のデータを参照するのみで、複数のＭａｐデータを集約することができる。これにより、性能・スケーラビリティ改善効果を最大限に得ることが可能となる。また、Ｍａｐ処理部１２とＲｅｄｕｃｅ処理部１４とが処理を繰り返し行うことで、データに関連のある範囲のキーがデータ間を伝達していくので、データ集約の漏れをなくすことができる。
【００７３】
また、本実施形態では、Ｒｅｄｕｃｅ処理部１４は、複数のＭａｐデータを集約する際に、更新を行う前の集約キーを集約キーとし、集計された（取得された）未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たなＭａｐデータとして生成するので（ステップＳ４０）、親子関係（階層関係）にある全ての階層の集約処理を同時に行うことが可能となる。これにより、処理時間の短縮を図ることが可能となる。
【００７４】
また、本実施形態では、Ｒｅｄｕｃｅ処理部１４は、集約キーを更新できなくなったデータの集約キーを、使用済みキーとしてＭａｐデータに関連付けられているキーのうち、親子関係（階層関係）の最上位にあるキーで更新するとともに、Ｍａｐデータに、集約キーのそれ以上の更新を禁止するフラグ（固定フラグ）を設定する（データに対応付けて固定フラグを記憶する）（ステップＳ４２、Ｓ４４）。これにより、集約キーの更新が一巡したときには、それ以降、集約キーは更新されなくなるので、集約キーの更新が一巡したときに発生し得る、処理の永久ループを防止することが可能となる。
【００７５】
また、本実施形態の分散処理システム１００は、上記のような処理サーバ１０を複数備えているので、複数のＭａｐデータを、複数の処理サーバ１０上で分散・並行的にMapReduce処理することが可能となる。
【００７６】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、処理装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。
【００７７】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ（Digital Versatile Disc）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）などの可搬型記録媒体の形態で販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【００７８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【００７９】
上述した実施形態は本発明の好適な実施の例である。但し、これに限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変形実施可能である。
【００８０】
なお、以上の説明に関して更に以下の付記を開示する。
（付記１） 複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、を備え、前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返すことを特徴とする処理装置。
（付記２） 前記集約部は、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶することを特徴とする付記１に記載の処理装置。
（付記３） 前記関連付け部は、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付け、前記集約部は、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新することを特徴とする付記１又は２に記載の処理装置。
（付記４） 付記１〜３のいずれかに記載の処理装置を複数備え、複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行することを特徴とする分散処理システム。
（付記５） 複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、取得した前記未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させることを特徴とする処理プログラム。
（付記６） 前記集約する処理では、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶する処理をコンピュータに実行させることを特徴とする付記５に記載の処理プログラム。
（付記７） 前記関連付ける処理では、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付ける処理をコンピュータに実行させ、前記集約する処理では、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、コンピュータに実行させることを特徴とする付記５又は６に記載の処理プログラム。
【符号の説明】
【００８１】
１０ 処理サーバ（処理装置）
１２ Ｍａｐ処理部（関連付け部）
１４ Ｒｅｄｕｃｅ処理部（集約部）
９０ ＣＰＵ（コンピュータ）
９６ ＨＤＤ（記憶部）
１００ 分散処理システム
【特許請求の範囲】
【請求項１】
複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、
前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、
前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、
を備え、
前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返すことを特徴とする処理装置。
【請求項２】
前記集約部は、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶することを特徴とする請求項１に記載の処理装置。
【請求項３】
前記関連付け部は、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付け、
前記集約部は、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新することを特徴とする請求項１又は２に記載の処理装置。
【請求項４】
請求項１〜３のいずれか一項に記載の処理装置を複数備え、
複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行することを特徴とする分散処理システム。
【請求項５】
複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、
前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、
前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、
取得した前記データに含まれる未使用キーを全て取得し、
取得した前記未使用キーのうちの１つを次の集約キーとして決定し、
取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、
取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、
前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させることを特徴とする処理プログラム。
【請求項１】
複数のキー種を用いて分類された複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を実行する処理装置であって、
前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された、前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶する関連付け部と、
前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、該取得した未使用キーのうちの１つを次の集約キーとして決定し、前記取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する集約部と、
を備え、
前記集約キーの更新ができなくなるまで、前記関連付け部と前記集約部による処理を繰り返すことを特徴とする処理装置。
【請求項２】
前記集約部は、前記更新を行う前の前記集約キーを集約キーとし、取得した前記未使用キーのすべてを未使用キーとする、データとしての実体のないデータを新たな処理対象のデータとして生成して前記記憶部に記憶することを特徴とする請求項１に記載の処理装置。
【請求項３】
前記関連付け部は、前記処理対象のデータに、既に集約に用いた使用済みキーを関連付け、
前記集約部は、前記集約キーの更新ができなくなったデータに対応付けて前記記憶部に記憶された集約キーを、前記データに前記使用済みキーとして関連付けられているキーのうち、親子関係の最上位にあるキー種のキーで更新し、当該データに対応付けて前記集約キーの更新を禁止する情報を前記記憶部に記憶し、前記記憶部に格納された前記複数のデータのうち、同一の集約キーに関連付けられ、且つ、前記集約キーの更新を禁止する情報が関連付けられていないデータを取得し、取得した前記データに含まれる未使用キーを全て取得し、前記取得した未使用キーのうちの１つを次の集約キーとして決定し、取得した前記データに対応付けて前記記憶部に記憶された前記集約キーを前記次の集約キーに更新し、取得した前記データに対応付けて前記記憶部に記憶された前記未使用キーを取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新することを特徴とする請求項１又は２に記載の処理装置。
【請求項４】
請求項１〜３のいずれか一項に記載の処理装置を複数備え、
複数の処理対象のデータを前記複数の処理装置に分散して、当該複数の処理装置において並行処理を実行することを特徴とする分散処理システム。
【請求項５】
複数のキー種を用いて複数のデータの中から関連のあるデータを集約してデータ群を生成する処理を、コンピュータに実行させる処理プログラムであって、
前記複数のキー種を用いて分類された複数のデータを記憶する記憶部に記憶された前記複数のデータのそれぞれについて、該データが有する前記複数のキー種のキーを、前記集約に用いる集約キーと、未使用キーのいずれかに分類して、各データに関連付けて前記記憶部に記憶し、
前記記憶部に記憶された前記複数のデータのうち、同一の集約キーに関連付けられたデータを取得し、
取得した前記データに含まれる未使用キーを全て取得し、
取得した前記未使用キーのうちの１つを次の集約キーとして決定し、
取得した前記データに関連付けて前記記憶部に記憶された前記集約キーを、前記次の集約キーに更新し、
取得した前記データに関連付けて前記記憶部に記憶された前記未使用キーを、取得した前記未使用キーから前記次の集約キーを除いた残りの未使用キーに更新する処理を、
前記未使用キーの更新ができなくなるまで、コンピュータに繰り返し実行させることを特徴とする処理プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１】
【図３２】
【図３３】
【図３４】
【公開番号】特開２０１２−１９００７８（Ｐ２０１２−１９００７８Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１１−５０７４５（Ｐ２０１１−５０７４５）
【出願日】平成２３年３月８日（２０１１．３．８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願日】平成２３年３月８日（２０１１．３．８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]