(57)【特許請求の範囲】
【請求項１】
コンピュータに、
受信したデータに付与された第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、第１マップに記録し、
前記第１マップに記憶された第１識別子の数が閾値に達した後、前記第１マップに記憶された負荷情報に基づいて選択した第１識別子を、前記第１マップから削除し、
受信したデータに付与された第１識別子に対する所定の計算で算出した、該第１識別子よりも短いデータ長の第２識別子と、該第１識別子が付与されたデータを処理するノードとを対応付けて記憶する第２マップに、前記第１マップから削除した第１識別子と、該第１識別子が付与されたデータの処理に関する負荷情報とを、該第１識別子に対する前記所定の計算で算出した第２識別子に対応付けて記録し、
前記第１マップに記憶された第１識別子の数が前記閾値に満たないとき、前記第２マップに記憶された第１識別子から、負荷情報に基づいて第１識別子を選択し、
選択した該第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、前記第１マップに記録し、
データの受信に応じ、該データに付与された第１識別子が前記第１マップに記憶されていれば、前記第１マップにおいて該第１識別子に対応付けられたノードに該データを処理させることを決定し、該第１識別子が前記第１マップに記憶されていなければ、該第１識別子に対する所定の計算で算出した第２識別子に対応付けて、前記第２マップに登録されているノードに、該データを処理させることを決定する、
処理を実行させる処理プログラム。
【請求項２】
前記第１マップからの第１識別子の削除では、前記第１マップに記憶された複数の第１識別子のうち、負荷情報に示される負荷が小さい方から所定数の第１識別子を削除する請求項１記載の処理プログラム。
【請求項３】
前記第２マップからの第１識別子の選択では、前記第２マップに記憶された第１識別子のうち、負荷情報に示される負荷が大きい方から所定数の第１識別子を選択する請求項１記載の処理プログラム。
【請求項４】
前記第２マップからの第１識別子の選択では、前記第２マップから、対応付けられた第１識別子の負荷情報に示される負荷の合計が大きい方から所定数の第２識別子を選択し、選択した該第２識別子に対応付けられた第１識別子の中から、負荷情報に基づいて第１識別子を選択する、
請求項１乃至３のいずれかに記載の処理プログラム。
【請求項５】
前記コンピュータに、さらに、
複数のノードの負荷が均等化されるように、前記第１マップにおいて第１識別子に対応付けられたノードと、前記第２マップにおいて第２識別子に対応付けられたノードとを変更する、
処理を実行させる請求項１乃至４のいずれかに記載の処理プログラム。
【請求項６】
コンピュータが、
受信したデータに付与された第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、第１マップに記録し、
前記第１マップに記憶された第１識別子の数が閾値に達した後、前記第１マップに記憶された負荷情報に基づいて選択した第１識別子を、前記第１マップから削除し、
受信したデータに付与された第１識別子に対する所定の計算で算出した、該第１識別子よりも短いデータ長の第２識別子と、該第１識別子が付与されたデータを処理するノードとを対応付けて記憶する第２マップに、前記第１マップから削除した第１識別子と、該第１識別子が付与されたデータの処理に関する負荷情報とを、該第１識別子に対する前記所定の計算で算出した第２識別子に対応付けて記録し、
前記第１マップに記憶された第１識別子の数が前記閾値に満たないとき、前記第２マップに記憶された第１識別子から、負荷情報に基づいて第１識別子を選択し、
選択した該第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、前記第１マップに記録し、
データの受信に応じ、該データに付与された第１識別子が前記第１マップに記憶されていれば、前記第１マップにおいて該第１識別子に対応付けられたノードに該データを処理させることを決定し、該第１識別子が前記第１マップに記憶されていなければ、該第１識別子に対する所定の計算で算出した第２識別子に対応付けて、前記第２マップに登録されているノードに、該データを処理させることを決定する、
データ処理方法。
【請求項７】
受信したデータに付与された第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、第１マップに記録する第１記録手段と、
前記第１マップに記憶された第１識別子の数が閾値に達した後、前記第１マップに記憶された負荷情報に基づいて選択した第１識別子を、前記第１マップから削除する削除手段と、
受信したデータに付与された第１識別子に対する所定の計算で算出した、該第１識別子よりも短いデータ長の第２識別子と、該第１識別子が付与されたデータを処理するノードとを対応付けて記憶する第２マップに、前記第１マップから削除した第１識別子と、該第１識別子が付与されたデータの処理に関する負荷情報とを、該第１識別子に対する前記所定の計算で算出した第２識別子に対応付けて記録する第２記録手段と、
データの受信に応じ、該データに付与された第１識別子が前記第１マップに記憶されていれば、前記第１マップにおいて該第１識別子に対応付けられたノードに該データを処理させることを決定し、該第１識別子が前記第１マップに記憶されていなければ、該第１識別子に対する所定の計算で算出した第２識別子に対応付けて、前記第２マップに登録されているノードに、該データを処理させることを決定する決定手段とを有し、
前記第１記録手段は、前記第１マップに記憶された第１識別子の数が前記閾値に満たないとき、前記第２マップに記憶された第１識別子から、負荷情報に基づいて第１識別子を選択し、選択した該第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、前記第１マップに記録する、
処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理プログラム、データ処理方法、および処理装置に関する。
【背景技術】
【０００２】
コンピュータシステムには、クラスタやクラウド上で動作するスケーラブルなシステムがある。例えば分散ＫＶＳ（Key-Value Store）システムや、並列ＣＥＰ（複合イベント処理：Complex Event Processing）システムなどである。
【０００３】
スケーラブルなシステムでは、負荷に応じた数のノード（サーバなどのコンピュータ）で並列処理が行われる。並列処理には、処理対象のデータを分散させるデータ並列処理がある。データ並列を行うシステムでは、入力されたデータをどのノードで処理するのかが、例えば位置管理テーブルを用いて管理される。位置管理テーブルには、データのキーに対応付けて、そのデータを処理するノード名が登録される。各ノードは、位置管理テーブルを参照して、入力されたデータを処理するノードを識別する。例えば各ノードは、入力されたデータを処理するノードが自分自身であれば、データを処理する。また各ノードは、入力されたデータを処理するノードが自分以外のノードであれば、そのノードにデータを送信する。
【０００４】
データ並列システムの場合、処理するデータ量の増大に伴い、位置管理テーブルのサイズも増大する。位置管理テーブルのサイズの増大は、各ノードのメモリ容量を圧迫する。そこで位置管理テーブルのサイズを小さくするため、ハッシュ関数が利用される。この場合、位置管理テーブルには、ハッシュ値に対応付けて、ノード名が登録される。そして、キーに対するハッシュ関数の計算結果（ハッシュ値）が同じ値になるデータは、同じノードで処理される。ハッシュ関数を用いることで、位置管理テーブルは、ハッシュ関数の計算結果として得られる値の数分のエントリを登録できればよくなり、位置管理テーブルのサイズの肥大化を抑止できる。
【０００５】
なお、大量のデータの管理方法としては、例えば特定のキーに対してバースト的に大量のリクエストが発生した時に、特定のノードに負荷が集中しないように負荷を分散することのできる分散データの管理方法がある。また、イベントデータの発生頻度やイベント条件の更新頻度などが異なる複数のユースケースそれぞれに適した分散処理装置特定方法を選択する分散処理制御方法もある。さらに、データ再配置先の決定処理にかかる計算時間を削減することができるデータ再配置装置も考えられている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００８−５４４９号公報
【特許文献２】特開２０１３−１０１４４６号公報
【特許文献３】特開２０１３−１１７７６３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、ハッシュ関数を用いると、位置管理テーブルのサイズは抑止できるものの、キーの分布によっては、入力された多数のデータのキーのハッシュ値が不均一になり、ノードの負荷が不均一になる場合がある。
【０００８】
１つの側面では、本件は、ノード間の負荷の差の抑制を可能とすることを目的とする。
【課題を解決するための手段】
【０００９】
１つの案では、コンピュータに、以下の処理を実行させる処理プログラムが提供される。処理プロラムに基づいて、コンピュータは、受信したデータに付与された第１識別子、該第１識別子が付与されたデータを処理するノード、および該第１識別子が付与された該データの処理に関する負荷情報を対応付けて、第１マップに記録する。またコンピュータは、第１マップに記憶された第１識別子の数が閾値に達した後、第１マップに記憶された負荷情報に基づいて選択した第１識別子を、第１マップから削除する。そしてコンピュータは、データの受信に応じ、該データに付与された第１識別子が第１マップに記憶されていれば、第１マップにおいて該第１識別子に対応付けられたノードに該データを処理させることを決定し、該第１識別子が第１マップに記憶されていなければ、該第１識別子に対する所定の計算で算出した第２識別子であり、該第１識別子よりも短いデータ長の該第２識別子に対応付けて、第２マップに登録されているノードに、該データを処理させることを決定する。
【発明の効果】
【００１０】
１態様によれば、ノード間の負荷の差の抑制が可能となる。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態に係る処理装置の機能構成例を示す図である。
【図２】複合イベント処理の一例を示す図である。
【図３】データ並列処理の一例を示す図である。
【図４】第２の実施の形態の複合イベント処理システム構成例を示す図である。
【図５】本実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。
【図６】各ノードの機能の一例を示すブロック図である。
【図７】ノード内の要素間の通信例を示す図である。
【図８】イベント転送部の機能の一例を示すブロック図である。
【図９】位置管理部の機能の一例を示すブロック図である。
【図１０】ＶＮｏｄｅマップテーブルの一例を示す図である。
【図１１】個別キーマップテーブルの一例を示す図である。
【図１２】初期記憶位置設定処理の手順の一例を示すフローチャートである。
【図１３】イベント受信処理の手順の一例を示すフローチャートである。
【図１４】イベント送信処理の手順の一例を示すフローチャートである。
【図１５】位置読出処理の手順の一例を示すフローチャートである。
【図１６】状態情報移動処理の手順の一例を示すフローチャートである。
【図１７】位置変更処理の手順の一例を示すフローチャートである。
【図１８】位置書込処理の手順の一例を示すフローチャートである。
【図１９】自ノードの負荷に関する負荷情報記録処理の手順を示すフローチャートである。
【図２０】他ノードの負荷に関する負荷情報記録処理の手順の一例を示すフローチャートである。
【図２１】個別管理キー入替処理の手順の一例を示すフローチャートである。
【図２２】入替対象決定処理の手順の一例を示すフローチャートである。
【図２３】入替処理の手順の一例を示すフローチャートである。
【図２４】入替前の状態を示す図である。
【図２５】入替後の状態を示す図である。
【発明を実施するための形態】
【００１２】
以下、本実施の形態について図面を参照して説明する。なお各実施の形態は、矛盾のない範囲で複数の実施の形態を組み合わせて実施することができる。
〔第１の実施の形態〕
図１は、第１の実施の形態に係る処理装置の機能構成例を示す図である。第１の実施の形態に係る処理装置１０は、ノード１〜４にデータ並列で処理させるデータ５，６の処理を実行させるノードを管理する。データ５，６には、第１識別子が付与されている。第１識別子は、例えばキーとも呼ばれる。
【００１３】
処理装置１０は、データに付与された第１識別子に基づいて、そのデータを処理するノードを決定する。そのために処理装置１０は、第１マップ１１、第２マップ１２、第１記録手段１３、削除手段１４、決定手段１５、第２記録手段１６、および処理ノード変更手段１７を有する。
【００１４】
第１マップ１１は、データの第１識別子単位で、そのデータを処理するノードを管理するための管理情報の記憶領域である。第１マップ１１には、受信したデータに付与された第１識別子、第１識別子が付与されたデータを処理するノード、および第１識別子が付与された該データの処理に関する負荷情報を対応付けて記憶される。
【００１５】
第２マップ１２は、データに付与された第１識別子に対する所定の計算で算出した第２識別子（例えばハッシュ値）単位で、そのデータを処理するノードを管理するための管理情報の記憶領域である。第２マップ１２には、第２識別子、所定の計算の結果が第２識別子となる第１識別子が付与されたデータを処理するノードが対応付けて記憶される。また第２マップ１２には、第２識別子に対応付けて、受信したデータに付与された第１識別子のうち、計算により第２識別子となった第１識別子と、その第１識別子が付与されたデータの処理に関する負荷情報が記憶される。
【００１６】
第１記録手段１３は、受信したデータに付与された第１識別子、その第１識別子が付与されたデータを処理するノード、およびその第１識別子が付与されたデータの処理に関する負荷情報を対応付けて、第１マップ１１に記録する。なお負荷情報は、例えば、データの処理の実行後に、そのデータを処理したノードから取得して、第１マップ１１に記録される。なお第１マップ１１に記録できる第１識別子の数には、所定の閾値が上限となる。第１記録手段１３は、第１マップ１１に記録された第１識別子の数が閾値に達するまで、第１識別子を第１マップ１１に記録する。第１マップ１１に記録された第１識別子の数が、閾値に達した後は、第１マップ１１から第１識別子が削除されるまで、第１記録手段１３は、第１マップ１１への第１識別子の記録は行わない。
【００１７】
第１記録手段１３は、例えば、第１マップ１１に記憶された第１識別子の数が閾値に満たないとき、第２マップ１２に記憶された第１識別子から、負荷情報に基づいて第１識別子を選択する。そして第１記録手段１３は、選択した第１識別子、第１識別子が付与されたデータを処理するノード、および第１識別子が付与されたデータの処理に関する負荷情報を対応付けて、第１マップ１１に記録する。例えば第１記録手段１３は、第２マップ１２に記憶された第１識別子のうち、負荷情報に示される負荷が大きい方から所定数の第１識別子を選択し、第１マップ１１に記録する。
【００１８】
第１記録手段１３は、第２マップ１２に記憶された第１識別子を選択する際、例えば第２マップ１２から、対応付けられた第１識別子の負荷情報に示される負荷の合計が大きい方から所定数の第２識別子を選択する。そして第１記録手段１３は、選択した第２識別子に対応づけられた第１識別子の中から、負荷情報に基づいて第１識別子を選択する。
【００１９】
削除手段１４は、第１マップ１１に記憶された第１識別子の数が閾値に達した後、第１マップ１１に記憶された負荷情報に基づいて選択した第１識別子を、第１マップ１１から削除する。例えば削除手段１４は、第１マップ１１に記憶された複数の第１識別子のうち、負荷情報に示される負荷が小さい方から所定数の第１識別子を選択し、その第１識別子を削除する。
【００２０】
決定手段１５は、データ５，６の受信に応じ、データ５，６に付与された第１識別子が第１マップ１１に記憶されていれば、第１マップ１１において該第１識別子に対応付けられたノードに該データを処理させることを決定する。また決定手段１５は、第１識別子が第１マップ１１に記憶されていなければ、データ５，６に付与された第１識別子に対する所定の計算で算出した第２識別子に対応付けて、第２マップ１２に登録されているノードに、データ５，６を処理させることを決定する。そして決定手段１５は、データ５，６を、そのデータを処理させると決定したノードに送信する。
【００２１】
第２記録手段１６は、第１マップ１１から削除した第１識別子と、その第１識別子が付与されたデータの処理に関する負荷情報とを、第１識別子に対する所定の計算で算出した第２識別子に対応付けて、第２マップ１２に記録する。
【００２２】
処理ノード変更手段１７は、複数のノード間の負荷の差が少なくなるように、第１マップ１１において第１識別子に対応付けられたノードと、第２マップ１２において第２識別子に対応付けられたノードとを変更する。例えば処理ノード変更手段１７は、負荷の大きいノードに対応付けられた第１識別子または第２識別子を選択し、選択した第１識別子または第２識別子に対応するノードを、負荷の少ないノードに変更する。
【００２３】
このような処理装置１０によれば、例えばデータ５を受信すると、まず第１マップ１１が参照される。図１の例では、データ５の第１識別子「１２０」は第１マップ１１に記憶されており、ノード名「Ｎｏｄｅ  １」のノード２が対応付けられている。そこでデータ５は、ノード２に転送され、ノード２においてデータ５が処理される。また処理装置１０がデータ６を受信すると、まず第１マップ１１が参照される。図１の例では、データ６の第１識別子「５２」は第１マップ１１に記憶されていない。そこで第２マップ１２が参照される。ここで、第１識別子「５２」に所定の計算を行った結果は「０」であるものとする。図１の例では、第２マップ１２において、第２識別子「０」には、ノード名「Ｎｏｄｅ  ０」のノード１が対応付けられている。そこでデータ６は、ノード１に転送され、ノード１においてデータ６が処理される。
【００２４】
このように第１の実施の形態では、データ並列における各データを処理するノードを管理するための管理情報として、第１マップ１１と第２マップ１２とを併用している。そのため、受信したデータの第１識別子の数が少ない間は、第１マップ１１を用いて、各データを処理するノードがキー単位で管理される。キー単位で管理されることで、ノードに実行させるデータを小さい単位で調整でき、ノード間の負荷の差を抑制できる。
【００２５】
第１識別子の数が増加すると、第１マップ１１で管理しきれない分が、第２マップ１２で管理される。第２マップ１２における第２識別子は、例えばハッシュ値のように、第１識別子よりもデータ長が短い。そのため、生成される可能性のあるすべての第２識別子を第２マップ１２に記録したとしても、第１識別子のすべてを個別に管理する場合よりも、第２マップ１２のサイズは小さくなる。従って、管理情報のデータ量の肥大化が抑止される。
【００２６】
なお第２識別子は、第１識別子よりもデータ長が短いため、異なる第１識別子の所定の計算の結果、同じ第２識別子となることがある。そこで、例えば第１マップ１１から第１識別子を削除する際に、例えば、負荷の少ない方から所定数の第１識別子を削除することで、第１マップ１１には、比較的負荷の大きい第１識別子が残され、負荷の少ない第１識別子が、第２マップ１２により第２識別子単位で管理される。１つの第２識別子に複数の第１識別子が属し、それらの第１識別子が付与されたデータが同じノードで処理されることになっても、第１識別子それぞれの負荷が少なくてすめば、そのノードの負荷が過大にならずにすむ。特定のノードの負荷が過大になることが抑止されれば、ノード間の負荷の差は小さくなる。
【００２７】
また第１マップ１１に空きがあれば、例えば、第２マップ１２に第２識別子に対応付けて記録されている第１識別子のうち、負荷の大きい方から所定数の第１識別子が、第１マップ１１に記録される。これにより、第２マップ１２により第２識別子単位で管理されるようになった第１識別子でも、負荷の高い第１識別子は、第１マップ１１に記録して第１識別子単位で管理できる。その結果、１つの第２識別子に複数の第１識別子が属し、それらの第１識別子が付与されたデータの処理の負荷が高いことにより、その第２識別子に対応付けられたノードの負荷が過大になることを抑止できる。
【００２８】
さらに、第２マップ１２に記録されていた第１識別子のうち、負荷の大きい方から所定数の第１識別子を第１マップ１１に記録するとき、例えば対応付けられた第１識別子の負荷情報に示される負荷の合計が大きい方から所定数の第２識別子が選択される。そして選択され第２識別子に対応づけられた第１識別子の中から、負荷情報に基づいて、第１マップ１１に記録する第１識別子が選択される。これにより、ノード間の負荷の均等化が促進される。
【００２９】
なお、第１記録手段１３、削除手段１４、決定手段１５、第２記録手段１６、および処理ノード変更手段１７は、例えば処理装置１０が有するプロセッサにより実現することができる。また、第１マップ１１および第２マップ１２は、例えば処理装置１０が有するメモリにより実現することができる。
【００３０】
図１の例では、ノード１〜４とは別に処理装置１０が設けられているが、処理装置１０が有する要素の一部または全部を、いずれか１つまたは複数のノード内に設けてもよい。また、図１に示した各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。
【００３１】
〔第２の実施の形態〕
次に第２の実施の形態について説明する。第２の実施の形態は、複合イベント処理（ＣＥＰ）システムにおいて、多数のデータを分散処理するものである。複合イベント処理では、ビッグデータと呼ばれる膨大な量のデータを処理する場合がある。
【００３２】
図２は、複合イベント処理の一例を示す図である。複合イベント処理システム３０は、ビッグデータと呼ばれる膨大な量のデータを処理するコンピュータシステムである。例えば複合イベント処理システム３０は、各種機器が有するセンサからデータを取得する（センシングする）。例えば１つの機器から送信されるデータは、ストリームとして複合イベント処理システム３０に入力される。
【００３３】
センサを有する機器には、気象衛星、定点カメラ、スマートシティ内の機器、携帯端末、物流センタ内のシステム、健康機器、交通監視システムなどがある。センシング対象のセンサの量が膨大になれば、各センサから複合イベント処理システム３０に送信されるデータは、ビッグデータとなる。
【００３４】
複合イベント処理システム３０では、データを受信すると、予め用意されたルールを適用し、そのデータの出力元の機器の状態に応じ、ユーザに役立つ情報を抽出する。そして複合イベント処理システム３０は、例えばユーザの所有する携帯端末３１を制御して、ユーザのナビゲーションを行う。ナビゲーションにより、役立つ情報がユーザに知らされる。
【００３５】
複合イベント処理システム３０では、ビッグデータを効率的に処理するために、データ並列処理を行う。
図３は、データ並列処理の一例を示す図である。例えば複合イベント処理システム３０は、店舗４２が提供するサービスの契約者に関する契約者情報３２を保持する。そして複合イベント処理システム３０は、契約者それぞれが有する管理対象機器４１ａ，４１ｂ，・・・から、契約者ＩＤ付きの位置情報を取得する。管理対象機器４１ａ，４１ｂ，・・・は、例えば携帯端末である。複合イベント処理システム３０では、契約者ＩＤごとの契約者情報３２の検索を、並列で処理する。そして複合イベント処理システム３０は、例えば、契約者の位置と嗜好とに基づいて、その契約者に合ったクーポンの発行依頼を、店舗４２内のサーバに送信する。すると、店舗４２内のサーバが、契約者ごとの適切なクーポンを、契約者が所有する管理対象機器４１ａ，４１ｂ，・・・宛てに送信する。
【００３６】
複合イベント処理システム３０では、このような並列処理が、様々な入力データに応じて実行される。そのため入力データ量が肥大化した場合、効率的に処理するために、複数のノードでデータを処理することになる。
【００３７】
第２の実施の形態の複合イベント処理システム３０は、管理対象機器４１ａ，４１ｂ，・・・からのデータ入力をイベントとし、そのイベントのキーに基づいて、イベントを複数のノードのいずれかに処理させる。イベントのキーとしては、例えば管理対象機器４１ａ，４１ｂ，・・・のＩＤを用いることができる。管理対象機器４１ａ，４１ｂ，・・・のＩＤをキーとしてイベントの振り分けを行えば、ある管理対象機器が出力したデータを、１つのノードで処理することができる。
【００３８】
なお同じキーを有する複数のイベントは、そのキーに対応する状態情報を記憶するノードで処理される。例えばキーが自動車のＩＤである場合、キーに対応する状態情報は、その自動車の状態（外部から施錠中か、正しく解錠されたかなど）を示す情報である。この自動車のセンサがエンジン始動操作を検知し、その操作を示すデータを複合イベント処理システム３０に送信すると、自動車が外部から施錠中であれば、データに応じたイベント処理により、例えばセキュリティセンタに対して警報が発せられる。他方、自動車が正しく解錠されていれば、データに応じたイベント処理により、自動車の運行開始が記録される。このように、キーに対応する状態情報の内容に応じて、イベントの処理結果が異なる。そのため、同じキーを有するイベントは、そのキーの状態情報を記憶するサーバに転送される。そのキーを有するイベントを処理するサーバを変更する場合、変更先のサーバへ状態情報が送信される。
【００３９】
ここで、すべてのキーについて、どのノードで実行するのかを位置管理テーブルで管理すると、入力されるデータの増加に伴い、位置管理テーブルが肥大化する。例えばキーが３２ビットの符号なし整数型（unsigned int）の場合、位置管理テーブルのエントリ数は最大４０億個となる。その結果、各ノードのメモリ容量が圧迫される。しかも位置管理テーブル内のエントリ数が多ければ、位置管理テーブルの更新頻度も多くなり、ノードの処理負荷が増大する。
【００４０】
位置管理テーブルの肥大化を抑止するためには、ハッシュ関数を用いることができる。ハッシュ関数を用いる場合、位置管理テーブルには、ハッシュ値と、ハッシュ関数による計算の結果、そのハッシュ値となるキーを有するイベントを処理するノードとの対応関係が登録される。ハッシュ関数を用いることで、位置管理テーブルに登録するエントリ数を抑止できる。ただし、ハッシュ関数を用いてイベントを処理するノードを管理すると、ハッシュ関数によって得られるハッシュ値が不均一になることで、ノードの負荷が不均一になることがある。
【００４１】
第２の実施の形態では、位置管理テーブルの肥大化と、ノードの負荷の不均一化とを抑止するために、キーごとのイベントのノードへの割り当てと、ハッシュ関数を用いたイベントのノードへの割り当てとを併用する。以下、同じハッシュ値が得られるキーの集合をＶＮｏｄｅと呼ぶ。
【００４２】
ハッシュ関数を使ってキー単位の状態を束ねて扱うことで、データ並列性を引き出すことができる。なお第２の実施の形態では、キーごとのイベントのノードへの割り当てを併用するため、データ並列性が十分引き出せるだけのＶＮｏｄｅを設ければよく、それ以上の細分化はしなくてもよい。例えばデータ並列性は利用するノード数の１０倍程度もあれば十分である。すなわち、ノードを１，０００台利用するならば、ＶＮｏｄｅ数を１０，０００個用意し、１０，０００並列を確保できればよい。
【００４３】
なお、キーとノードとの対応関係の管理に求められる要件は、以下の通りである。
第１の要件は、高速性を得るため、イベント転送の度にキーからＶＮｏｄｅを特定できることである。この場合、イベントの１回の転送で目的のノードにたどり着くことが望ましい。
【００４４】
第２の要件は、ＶＮｏｄｅマップテーブルの保持に用いるメモリ容量が十分小さいことである。例えばＶＮｏｄｅマップテーブルのエントリ数は、１０，０００個ぐらいまでに抑えることが望ましい。なお第２の実施の形態では、キーごとの負荷量が管理されるが、使用するメモリ容量の抑制のためには、ＶＮｏｄｅと、そのＶＮｏｄｅに属する各キーの負荷量との対応関係は、マップ以外の手段で管理することが望ましい。
【００４５】
第３の要件は、ＶＮｏｄｅの属するキーを有するイベントを実行するためのノードの負荷と、キー単位で管理している各キーを有するイベントを実行するためのノードの負荷との差が少ないことである。負荷の差を少なくしておけば、例えば突出して負荷の大きいＶＮｏｄｅが生じることが抑止できる。突出して負荷の大きいＶＮｏｄｅがあると、そのＶＮｏｄｅのイベントを処理するノードの負荷が過大となるため、ノード間の負荷の均一化が図りづらくなる。突出して負荷の大きいＶＮｏｄｅの発生を抑止できれば、ノード間の負荷の均一化が図りやすくなる。
【００４６】
なお複数のＶＮｏｄｅ間で、所属キー数をなるべく均等にするようにしてもよい。キーごとの負荷に大差がないことが分かっていれば、ＶＮｏｄｅの所属キー数を均等にすることで、ノード間の負荷も均等化されることが期待できる。特に各ＶＮｏｄｅに属するキー数が不均一になりやすい場合には、所属キー数をなるべく均等にすることが、ノード間の負荷の均等化に有効に作用する。各ＶＮｏｄｅに属するキー数が不均一になりやすい場合とは、例えばキーが疎な場合である。キーが疎とは、例えばキーが複数の数字で表されるとき、飛び飛びの数字しかキーとして使用されていないような場合である。高速道路のあるインターチェインジを通過した車両のナンバーをキーとした場合、キーは疎となる。
【００４７】
第４の要件は、キー数が少ないときには、キーをそのまま扱えることである。キーが少ないのであれば、ハッシュ関数を用いずに、キーごとに適切な振り分け先のノードを管理した方が、負荷の均等化を促進できる。キーをそのまま扱えるようにした場合でも、キー数が増加すれば、一部のキーをＶＮｏｄｅで管理するように移行させ、キー数が減少すれば、ＶＮｏｄｅで管理していたキーをキー単位に管理するように移行させることが望ましい。キーの管理方法を、キー単位とＶＮｏｄｅ単位とで相互に移行させる場合でも、少ない処理負荷で移行できることが望ましい。また、ＶＮｏｄｅに属するキーに対応するイベントの単位時間当たりの処理数と、キー単位で振り分け先のノードが管理されているキーに対応するイベントの単位時間当たりの処理数との差は、少ないことが望ましい。
【００４８】
第５の要件は、同一ＶＮｏｄｅに属するキーであっても同時に実行できることである。
以上の要件を満たすために、第２の実施の形態の複合イベント処理システム３０では、以下のようにしてキーとノードとの対応関係を管理する。
・キーのままでノードとの対応をキー用のマップで保持する。
・ＶＮｏｄｅについても、ノードとの対応をマップで保持する。
・両マップのサイズに上限を設け、キー用のマップのサイズが上限いっぱいになったら、負荷が軽いキーからＶＮｏｄｅでの管理に以降する。
・どのキーがどのＶＮｏｄｅに入るかは、ハッシュ法などを用いる。
・定期的にＶＮｏｄｅやキー単独の負荷が均一になるように、キー用のマップとＶｎｏｄｅ用のマップとの間で、キーの入替を行う。
・イベント転送時には、そのキーが単独でノードに割り付けられているかをまず調べ、存在しなければＶＮｏｄｅの担当ノードに転送し、Ｖｎｏｄｅ担当ノードに存在の有無をチェックさせる。
・キーが新規作成の場合には、Ｖｎｏｄｅの担当ノード上でキーを新規作成し、キー単独でマップに入れるか、ＶＮｏｄｅに入れるかを選択する。
・マップをシステム全体で共有するため、キー単独でマップに入れた場合、マップの変更依頼を、キーとノードとの対応関係を管理するマネージャに送る。
【００４９】
以下、キーごとのイベントのノードへの割り当てと、ハッシュ関数を用いたイベントのノードへの割り当てとを併用した複合イベント処理システム３０について、詳細に説明する。
【００５０】
図４は、第２の実施の形態の複合イベント処理システム構成例を示す図である。ネットワーク２０を介して管理対象機器４１ａ，４１ｂ，・・・とロードバランサ３００とが接続されている。管理対象機器４１ａ，４１ｂ，・・・は、センサの計測値などのデータを、ネットワーク２０を介してロードバランサ３００に送信する。
【００５１】
ロードバランサ３００には、スイッチ２８を介して、複数のノード１００，１００ａ，１００ｂ，１００ｃと管理ノード２００とが接続されている。ロードバランサ３００は、管理対象機器４１ａ，４１ｂ，・・・から受信したデータを、ラウンドロビンなどの所定のアルゴリズムで、複数のノード１００，１００ａ，１００ｂ，１００ｃに振り分ける。各データは、処理対象のイベントとして振り分け先のノードに転送される。
【００５２】
複数のノード１００，１００ａ，１００ｂ，１００ｃは、イベントを処理するノードを管理するための位置管理情報を有する。複数のノード１００，１００ａ，１００ｂ，１００ｃは、イベントを受信すると、位置管理情報を参照し、そのデータを処理するノードが、自分自身か否かを判断する。イベントを受信したノードは、そのイベントを処理するのが自分自身であれば、そのイベントに応じた処理を実行する。またイベントを受信したノードは、そのイベントを処理するのが自分自身でなければ、そのイベントに応じた処理を実行するノードに、イベントを転送する。
【００５３】
管理ノード２００は、負荷が均等化されるようにイベントを処理するノードを決定し、複数のノード１００，１００ａ，１００ｂ，１００ｃそれぞれの位置管理情報の更新を指示する。複数のノード１００，１００ａ，１００ｂ，１００ｃそれぞれは、管理ノード２００からの指示に従って、位置管理情報を更新する。
【００５４】
なお複数のノード１００，１００ａ，１００ｂ，１００ｃは、自身が処理するイベントのデータの送信元の管理対象機器の、現在の状態を管理している。複数のノード１００，１００ａ，１００ｂ，１００ｃは、位置管理情報の更新により、自身が処理してきたイベントを、以後、別のノードに処理させることになった場合、そのイベントの送信元の管理対象機器の状態を示す情報を、そのノードに送信する。
【００５５】
図５は、本実施の形態に用いるコンピュータのハードウェアの一構成例を示す図である。ノード１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１には、バス１０９を介してメモリ１０２と複数の周辺機器が接続されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、またはＤＳＰ（Digital Signal Processor）である。プロセッサ１０１がプログラムを実行することで実現する機能の少なくとも一部を、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）などの電子回路で実現してもよい。
【００５６】
メモリ１０２は、ノード１００の主記憶装置として使用される。メモリ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０２には、プロセッサ１０１による処理に必要な各種データが格納される。メモリ１０２としては、例えばＲＡＭ（Random Access Memory）などの揮発性の半導体記憶装置が使用される。
【００５７】
バス１０９に接続されている周辺機器としては、ＨＤＤ（Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、光学ドライブ装置１０６、機器接続インタフェース１０７およびネットワークインタフェース１０８がある。
【００５８】
ＨＤＤ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ＨＤＤ１０３は、ノード１００の補助記憶装置として使用される。ＨＤＤ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、補助記憶装置としては、フラッシュメモリなどの不揮発性の半導体記憶装置を使用することもできる。
【００５９】
グラフィック処理装置１０４には、モニタ２１が接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令に従って、画像をモニタ２１の画面に表示させる。モニタ２１としては、ＣＲＴ（Cathode Ray Tube）を用いた表示装置や液晶表示装置などがある。
【００６０】
入力インタフェース１０５には、キーボード２２とマウス２３とが接続されている。入力インタフェース１０５は、キーボード２２やマウス２３から送られてくる信号をプロセッサ１０１に送信する。なお、マウス２３は、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００６１】
光学ドライブ装置１０６は、レーザ光などを利用して、光ディスク２４に記録されたデータの読み取りを行う。光ディスク２４は、光の反射によって読み取り可能なようにデータが記録された可搬型の記録媒体である。光ディスク２４には、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。
【００６２】
機器接続インタフェース１０７は、ノード１００に周辺機器を接続するための通信インタフェースである。例えば機器接続インタフェース１０７には、メモリ装置２５やメモリリーダライタ２６を接続することができる。メモリ装置２５は、機器接続インタフェース１０７との通信機能を搭載した記録媒体である。メモリリーダライタ２６は、メモリカード２７へのデータの書き込み、またはメモリカード２７からのデータの読み出しを行う装置である。メモリカード２７は、カード型の記録媒体である。
【００６３】
ネットワークインタフェース１０８は、ネットワーク２０に接続されている。ネットワークインタフェース１０８は、ネットワーク２０を介して、他のコンピュータまたは通信機器との間でデータの送受信を行う。
【００６４】
以上のようなハードウェア構成によって、第２の実施の形態の処理機能を実現することができる。なお、第１の実施の形態に示した処理装置１０も、図５に示したノード１００と同様のハードウェアにより実現することができる。また他のノード１００ａ，１００ｂ，１００ｃ、管理ノード２００、およびロードバランサ３００も、図５に示したノード１００と同様のハードウェアにより実現することができる。
【００６５】
ノード１００は、例えばコンピュータ読み取り可能な記録媒体に記録されたプログラムを実行することにより、第２の実施の形態の処理機能を実現する。ノード１００に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。例えば、ノード１００に実行させるプログラムをＨＤＤ１０３に格納しておくことができる。プロセッサ１０１は、ＨＤＤ１０３内のプログラムの少なくとも一部をメモリ１０２にロードし、プログラムを実行する。またノード１００に実行させるプログラムを、光ディスク２４、メモリ装置２５、メモリカード２７などの可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えばプロセッサ１０１からの制御により、ＨＤＤ１０３にインストールされた後、実行可能となる。またプロセッサ１０１が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００６６】
図６は、各ノードの機能の一例を示すブロック図である。ノード１００は、通信部１１０、イベント転送部１２０、およびイベント処理部１３０を有する。通信部１１０は、他のノードとの間でイベントなどの情報の送受信を行う。イベント転送部１２０は、イベント処理部１３０で発生したイベントの他のノードへの転送や、受信したイベントのイベント処理部１３０への転送を行う。イベント処理部１３０は、受信したイベントを処理する。他のノード１００ａ，１００ｂ，１００ｃもノード１００と同様に、通信部１１０ａ，１１０ｂ，１１０ｃ、イベント転送部１２０ａ，１２０ｂ，１２０ｃ、およびイベント処理部１３０ａ，１３０ｂ，１３０ｃを有する。
【００６７】
管理ノード２００は、マネージャ２１０を有する。マネージャ２１０は、イベントをどのノードに処理させるのかを管理する。例えばマネージャ２１０は、負荷の重いノードで実行しているイベントを、負荷の軽いノードで実行させるように、イベントのノードへの割り当てを変更する。
【００６８】
次にノード１００内の要素間の通信内容について説明する。
図７は、ノード内の要素間の通信例を示す図である。通信部１１０は、ロードバランサ３００または他のノードからイベントまたは負荷情報を受信すると、受信したイベントまたは負荷情報をイベント転送部１２０に送信する。通信部１１０は、他のノードから、キーに対応する状態情報を受信すると、その状態情報をイベント処理部１３０に送信する。通信部１１０は、管理ノード２００から位置変更要求を受信すると、その位置変更要求をイベント転送部１２０に送信する、通信部１１０は、管理ノード２００から状態移動依頼を受信すると、その状態受信依頼をイベント処理部１３０に送信する。通信部１１０は、イベント転送部１２０からイベントを受信すると、そのイベントの宛先として指定されているノードへ、そのイベントを送信する。通信部１１０は、イベント転送部１２０から入替情報を受信すると、その入替情報を管理ノード２００に送信する。通信部１１０は、イベント処理部１３０から状態移動完了の通知を受信すると、その通知を管理ノード２００に送信する。通信部１１０は、イベント処理部１３０からキーに対応する状態情報を受信すると、以後、そのキーに対応するイベントを処理するノードへ、状態情報を送信する。
【００６９】
イベント転送部１２０は、通信部１１０またはイベント処理部１３０からイベントを受信すると、そのイベントを処理するノードを判断する。ノード１００自身が処理するイベントであれば、イベント転送部１２０は、受信したイベントをイベント処理部１３０に送信する。また他のノードが処理するイベントであれば、イベント転送部１２０は、そのイベントを処理するノードを宛先に指定し、受信したイベントを通信部１１０に送信する。イベント転送部１２０は、通信部１１０から位置変更要求を受信すると、内部に保持している位置管理情報を更新する。イベント転送部１２０は、通信部１１０から負荷情報を受信すると、内部に保持している他のノードの負荷情報を更新する。イベント転送部１２０は、キー単位で管理するイベントと、ＶＮｏｄｅ単位で管理するイベントとを入替えると、入替結果を示す入替情報を通信部１１０に送信する。
【００７０】
イベント処理部１３０は、イベント転送部１２０からイベントを受信すると、そのイベントの処理を実行する。イベントの処理の実行の結果、別のイベントが発生した場合、イベント処理部１３０は、発生したイベントをイベント転送部１２０に送信する。イベント処理部１３０は、イベントの実行により生じたノード１００の負荷を示す負荷情報を、イベント転送部１２０に送信する。イベント処理部１３０は、キーに対応する状態移動依頼を受信すると、該当する状態情報を通信部１１０に送信する。
【００７１】
次に、イベント転送部１２０の機能を、さらに詳細に説明する。
図８は、イベント転送部の機能の一例を示すブロック図である。イベント転送部１２０は、イベント受信先確認部１２１、イベント送信先検索部１２２、および位置管理部１２３を有する。
【００７２】
イベント受信先確認部１２１は、通信部１１０が他のノードなどから受信したイベント（受信イベント）を取得すると、その受信イベントの受信先を確認する。例えばイベント受信先確認部１２１は、受信イベントのキーを指定した位置読出要求を、位置管理部１２３に送信する。位置管理部１２３からは、受信イベントのキーに対応する状態情報を記憶するノードの位置（ノード名やアドレス）が、位置情報として返信される。イベント受信先確認部１２１は、取得した位置情報が自身のノード１００であれば、受信イベントをイベント処理部１３０に送信する。またイベント受信先確認部１２１は、取得した位置情報が他のノードであれば、受信イベントを、位置情報に示されるノード宛ての送信イベントとして、通信部１１０に送信する。
【００７３】
イベント送信先検索部１２２は、イベント処理部１３０が発行したイベント（送信イベント）を取得すると、その送信イベントの受信先を確認する。例えばイベント送信先検索部１２２は、送信イベントのキーを指定した位置読出要求を、位置管理部１２３に送信する。位置管理部１２３からは、送信イベントのキーに対応する状態情報を記憶するノードの位置（ノード名やアドレス）が、位置情報として返信される。イベント送信先検索部１２２は、取得した位置情報が自身のノード１００であれば、送信イベントをイベント処理部１３０に送信する。またイベント送信先検索部１２２は、取得した位置情報が他のノードであれば、送信イベントを、位置情報に示されるノード宛ての送信イベントとして、通信部１１０に送信する。
【００７４】
位置管理部１２３は、イベント受信先確認部１２１またはイベント送信先検索部１２２から位置読出要求を受信すると、キー単位またはＶＮｏｄｅ単位でキーに対応するイベントを処理するノードを関連づけたマップを参照する。そして位置管理部１２３は、参照したマップに基づいて、位置読出要求で指定されたキーに対応するノードを特定する。そして位置管理部１２３は、特定したノードを示す位置情報を、イベント受信先確認部１２１またはイベント送信先検索部１２２に送信する。また位置管理部１２３は、通信部１１０から位置変更要求を受信すると、位置変更要求に応じて、キー単位またはＶＮｏｄｅ単位でキーに対応するイベントを処理するノードを関連づけたマップを更新する。そして位置管理部１２３は、マップの更新が完了すると、書込完了の応答を通信部１１０に送信する。位置管理部１２３は、キー単位で管理するキーとＶＮｏｄｅ単位で管理するキーとの入替を実施した場合、入替内容を示す入替情報を通信部１１０に送信する。さらに位置管理部１２３は、通信部１１０またはイベント処理部１３０から、キーに対応するイベントの処理の負荷情報を受信すると、そのキーに対応付けて負荷情報を記憶する。
【００７５】
次に、位置管理部１２３の機能を、さらに詳細に説明する。
図９は、位置管理部の機能の一例を示すブロック図である。位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａ、個別キーマップテーブル１２３ｂ、表選択部１２３ｃ、および定期調整部１２３ｄを有する。
【００７６】
ＶＮｏｄｅマップテーブル１２３ａは、ＶＮｏｄｅに属するキーを特定する情報（例えばハッシュ値）に対応付けて、そのキーに対応するイベントを処理するノードが登録されたデータテーブルである。
【００７７】
個別キーマップテーブル１２３ｂは、イベントのキーに対応付けて、そのイベントを処理するノードが登録されたデータテーブルである。
表選択部１２３ｃは、通信部１１０から位置変更要求を受信すると、位置変更要求に従ってＶＮｏｄｅマップテーブル１２３ａまたは個別キーマップテーブル１２３ｂを更新する。例えば位置変更要求により、あるＶＮｏｄｅに属するキーに対応するイベントを処理するノードの変更が指示された場合を想定する。この場合、表選択部１２３ｃは、ＶＮｏｄｅマップテーブル１２３ａ内の該当ＶＮｏｄｅに関するエントリに関する、ノード変更の書込要求を出力する。この書込要求に基づいて、ＶＮｏｄｅマップテーブル１２３ａ内の該当エントリが更新される。また位置変更要求により、あるキーに対応するイベントを処理するノードの変更が指示された場合、表選択部１２３ｃは、個別キーマップテーブル１２３ｂ内の該当キーに関するエントリに関する、ノード変更の書込要求を出力する。この書込要求に基づいて、個別キーマップテーブル１２３ｂ内の該当エントリが更新される。書込要求に応じたエントリ更新の書き込みが完了すると、表選択部１２３ｃは、通信部１１０へ書込完了の応答を送信する。
【００７８】
また表選択部１２３ｃは、イベント受信先確認部１２１またはイベント送信先検索部１２２から位置読出要求を受信すると、位置読出要求で指定されたキーに対応するエントリの、個別キーマップテーブル１２３ｂからの読出要求を出力する。個別キーマップテーブル１２３ｂからの読出要求では、個別キーマップテーブル１２３ｂから、読出要求で指定したキーに対応するノードのノード名が、読出結果として出力される。個別キーマップテーブル１２３ｂからノード名が検出できない場合、表選択部１２３ｃは、位置読出要求で指定されたキーに対応するエントリの、ＶＮｏｄｅマップテーブル１２３ａからの読出要求を出力する。ＶＮｏｄｅマップテーブル１２３ａからの読出要求の際には、表選択部１２３ｃは、ハッシュ関数によりキーに対応するハッシュ値を計算し、ハッシュ値を指定した読出要求を出力する。すると、ＶＮｏｄｅマップテーブル１２３ａから、指定したハッシュ値に対応するＶＮｏｄｅのノード名が出力される。表選択部１２３ｃは、位置読出要求に対応する位置情報として、個別キーマップテーブル１２３ｂまたはＶＮｏｄｅマップテーブル１２３ａから取得したノード名を出力する。
【００７９】
定期調整部１２３ｄは、個別キーマップテーブル１２３ｂによりキー単位で管理されているキーと、ＶＮｏｄｅマップテーブル１２３ａによりＶＮｏｄｅ単位で管理されているキーとの入替を、定期的に行う。例えば定期調整部１２３ｄは、キーの入替を行う場合、個別キーマップテーブル１２３ｂまたはＶＮｏｄｅマップテーブル１２３ａへの読出要求により、各テーブル内のエントリを読み出す。また定期調整部１２３ｄは、キーの入替を行う場合、個別キーマップテーブル１２３ｂまたはＶＮｏｄｅマップテーブル１２３ａへの書込要求により、個別キーマップテーブル１２３ｂまたはＶＮｏｄｅマップテーブル１２３ａの内容を更新する。
【００８０】
さらに定期調整部１２３ｄは、キーごとの負荷情報を受信すると、そのキーに対応付けて、負荷情報を個別キーマップテーブル１２３ｂとＶＮｏｄｅマップテーブル１２３ａとに登録する。
【００８１】
なお、図６〜図９に示したノード１００，１００ａ，１００ｂ，１００ｃ内の各要素間を接続する線は通信経路の一部を示すものであり、図示した通信経路以外の通信経路も設定可能である。また、図６〜図９に示した各要素の機能は、例えば、その要素に対応するプログラムモジュールをコンピュータに実行させることで実現することができる。
【００８２】
次に、各マップテーブルの内容について詳細に説明する。
図１０は、ＶＮｏｄｅマップテーブルの一例を示す図である。ＶＮｏｄｅマップテーブル１２３ａには、ハッシュ値、ノード名、収容キー数、合計ＣＰＵ負荷、合計メモリ使用量、および個別キー負荷情報の欄が設けられている。ＶＮｏｄｅマップテーブル１２３ａには、ＶＮｏｄｅごとのエントリが登録されている。
【００８３】
ハッシュ値の欄には、ＶＮｏｄｅに属するイベントが有するキーに基づいて、ハッシュ関数の計算によって得られるハッシュ値が設定される。ハッシュ値としては、例えばメルセンヌ数が用いられる。ノード名の欄には、ＶＮｏｄｅに属するイベントを実行するノードのノード名が設定される。収容キー数の欄には、ＶＮｏｄｅに属するキー（収容キー）の数が設定される。合計ＣＰＵ負荷の欄には、収容キーを有するイベントの処理を実行することによるＣＰＵへの負荷が設定される。ＣＰＵの負荷は、例えばＣＰＵの使用回数で表される。またＣＰＵ使用率をＣＰＵの負荷としてもよい。合計メモリ使用量の欄には、収容キーを有するイベントの処理を実行することにより使用されるメモリの合計量が設定される。
【００８４】
個別キー負荷情報の欄には、自ノードでイベントを実行するＶＮｏｄｅに属する各キーの負荷情報（個別キー負荷情報）が設定される。個別キー負荷情報には、例えば、キー値と、そのキーを有するイベントを実行することによるＣＰＵ負荷とメモリ使用量とが含まれる。図１０の例では、ノード１００自身のノード名が「Ｎｏｄｅ  ３」である場合であり、ノード名の欄に「Ｎｏｄｅ  ３」と設定されているエントリについてのみ、個別キー負荷情報が設定されている。ノード１００以外のノードに対応するエントリについては、個別キー負荷情報の欄は空欄である。自ノードで実行するイベントに関するＶＮｏｄｅのエントリにのみ個別キー負荷情報を設定するようにすることで、ＶＮｏｄｅマップテーブル１２３ａのサイズを低減することができる。また個別キー負荷情報の欄には、例えば連結リスト形式で個別キー負荷情報が設定される。
【００８５】
なお図１０では、分かりやすいようにＶＮｏｄｅマップテーブル１２３ａを表イメージで記載したが、HashMapのような構造であってもよい。
図１１は、個別キーマップテーブルの一例を示す図である。個別キーマップテーブル１２３ｂには、キー値、ノード名、ＣＰＵ負荷、およびメモリ使用量の欄が設けられている。個別キーマップテーブル１２３ｂには、キー単位で管理されるキーごとのエントリが登録されている。
【００８６】
キー値の欄には、発生したイベントが有していたキーの値（キー値）が設定される。ノード名の欄には、対応するキーを有するイベントの処理を実行するノードのノード名が設定される。ＣＰＵ負荷の欄には、対応するキーを有するイベントの処理を実行することによるＣＰＵ負荷が設定される。メモリ使用量の欄には、対応するキーを有するイベントの処理を実行する際のメモリ使用量が設定される。
【００８７】
なお図１１では、分かりやすいように個別キーマップテーブル１２３ｂを表イメージで記載したが、HashMapのような構造であってもよい。
以上のような構成のシステムを用いて、データ並列による複合イベント処理が行われる。各データを処理するノードは、ＶＮｏｄｅマップテーブル１２３ａと個別キーマップテーブル１２３ｂとを用いて管理される。各データを処理するノードの管理に関する処理について詳細に説明する。
【００８８】
複合イベント処理システム３０の運用開始前に、ＶＮｏｄｅマップテーブル１２３ａに対する初期記憶位置設定処理が行われる。
図１２は、初期記憶位置設定処理の手順の一例を示すフローチャートである。
【００８９】
［ステップＳ１０１］ノード１００の位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａに初期値を設定する。例えば位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａのハッシュ値の欄に、生成可能なハッシュ値を設定する。また位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａのハッシュ値の欄以外の各欄に、０やｎｕｌｌなど初期値を設定する。他のノード１００ａ，１００ｂ，１００ｃでも同様の初期値設定処理が行われる。
【００９０】
［ステップＳ１０２］管理ノード２００のマネージャ２１０は、生成可能なハッシュ値ごとに、対応するＶＮｏｄｅに属するキーを有するイベントを処理するノードを決定する。例えばマネージャ２１０は、各ノード１００，１００ａ，１００ｂ，１００ｃで処理するＶＮｏｄｅ数が均等になるように、ＶＮｏｄｅに属するキーを有するイベントを処理するノードを決定する。そしてマネージャ２１０は、各ノード１００，１００ａ，１００ｂ，１００ｃに対して、各ＶＮｏｄｅについての、ＶＮｏｄｅに属するキーを有するイベントの実行位置のノードを示す位置変更要求を送信する。この位置変更要求には、例えばハッシュ値と、そのハッシュ値が得られるキーを有するイベントを実行するノードのノード名との組が含まれる。例えばノード１００に送信された位置変更要求は、通信部１１０からイベント転送部１２０に送られる。イベント転送部１２０では、位置変更要求を位置管理部１２３が受信する。
【００９１】
［ステップＳ１０３］各ノード１００，１００ａ，１００ｂ，１００ｃのイベント転送部１２０，１２０ａ，１２０ｂ，１２０ｃは、位置書込処理を行う。位置書込処理により、各ノード１００，１００ａ，１００ｂ，１００ｃ内のＶＮｏｄｅマップテーブルに、ＶＮｏｄｅのハッシュ値に対応付けて、ノード名が設定される。
【００９２】
このような初期記憶位置設定処理を実施した後、システムの運用が開始される。システムの運用が開始されると、管理対象機器４１ａ，４１ｂ，・・・からデータが入力され、入力データを処理するイベントが発生する。発生したイベントは、ロードバランサ３００によって、いずれかのノードに転送される。イベントを受信したノードでは、イベント受信処理が行われる。
【００９３】
図１３は、イベント受信処理の手順の一例を示すフローチャートである。以下、ノード１００がイベントを受信した場合を想定して、イベントの受信処理を説明する。
［ステップＳ１１１］通信部１１０は、受信イベントをイベント転送部１２０に送信する。
【００９４】
［ステップＳ１１２］イベント転送部１２０では、イベント受信先確認部１２１が、受信イベントが有するキーを指定して、位置管理部１２３に位置読出要求を送信する。
［ステップＳ１１３］位置管理部１２３は、指定されたキーに対応する状態情報の位置読出処理を行う。この処理の詳細は後述する（図１５参照）。
【００９５】
［ステップＳ１１４］イベント受信先確認部１２１は、位置管理部１２３から位置情報を受信し、その位置情報のノード名が自ノード（ノード１００）か否かを判断する。位置情報のノード名が自ノードであれば、処理がステップＳ１１５に進められる。位置情報のノード名が自ノードでなければ、処理がステップＳ１１６に進められる。
【００９６】
［ステップＳ１１５］イベント受信先確認部１２１は、位置情報のノード名が自ノードの場合、受信イベントをイベント処理部１３０に送信し、イベント受信処理を終了する。
［ステップＳ１１６］イベント受信先確認部１２１は、位置情報のノード名が自ノードでない場合、受信イベントを、取得した位置情報のノード名を宛先とする送信イベントに変更し、その送信イベントの送信を、通信部１１０に依頼する。すると通信部１１０が、送信イベントを、宛先で指定されたノードに送信する。その後、イベント受信処理が終了する。
【００９７】
イベント処理部１３０でイベントを実行した場合、他のイベントが発生する場合がある。イベントが発生すると、そのイベントの送信処理が行われる。
図１４は、イベント送信処理の手順の一例を示すフローチャートである。
【００９８】
［ステップＳ１２１］イベント処理部１３０は、発生したイベントにキーを付与し、送信イベントとしてイベント転送部１２０に送信する。
［ステップＳ１２２］イベント転送部１２０では、イベント送信先検索部１２２が、送信イベントが有するキーを指定して、位置管理部１２３に位置読出要求を送信する。
【００９９】
［ステップＳ１２３］位置管理部１２３は、指定されたキーに対応する状態情報の位置読出処理を行う。この処理の詳細は後述する（図１５参照）。
［ステップＳ１２４］イベント送信先検索部１２２は、位置管理部１２３から位置情報を受信し、その位置情報のノード名が自ノード（ノード１００）か否かを判断する。位置情報のノード名が自ノードであれば、処理がステップＳ１２５に進められる。位置情報のノード名が自ノードでなければ、処理がステップＳ１２６に進められる。
【０１００】
［ステップＳ１２５］イベント送信先検索部１２２は、位置情報のノード名が自ノードの場合、送信イベントをイベント処理部１３０に送信し、イベント受信処理を終了する。
［ステップＳ１２６］イベント送信先検索部１２２は、位置情報のノード名が自ノードでない場合、取得した位置情報のノード名を送信イベントの宛先として、その送信イベントの送信を通信部１１０に依頼する。すると通信部１１０が、送信イベントを、宛先で指定されたノードに送信する。その後、イベント受信処理が終了する。
【０１０１】
次にステップＳ１１３またはステップＳ１２３で行われる位置読出処理について、詳細に説明する。
図１５は、位置読出処理の手順の一例を示すフローチャートである。
【０１０２】
［ステップＳ１３１］位置管理部１２３の表選択部１２３ｃは、個別キーマップテーブル１２３ｂを参照し、位置読出要求で指定されたキーが存在するか否かを判断する。キーが存在していれば、処理がステップＳ１３２に進められる。存在していなければ、処理がステップＳ１３３に進められる。
【０１０３】
［ステップＳ１３２］表選択部１２３ｃは、位置読出要求で指定されたキーを有するエントリを個別キーマップテーブル１２３ｂから抽出し、そのエントリ内のノード名を取得する。そして表選択部１２３ｃは、位置読出要求の送信元に、ノード名を位置情報として応答する。その後、位置読出処理が終了する。
【０１０４】
［ステップＳ１３３］表選択部１２３ｃは、該当するキーが存在しない場合、そのキーのハッシュ値を算出する。表選択部１２３ｃは、ＶＮｏｄｅマップテーブル１２３ａ内の、算出したハッシュ値に対応するエントリからノード名を取得する。
【０１０５】
［ステップＳ１３４］表選択部１２３ｃは、取得したノード名が自ノード（ノード１００）のノード名かを判断する。自ノードのノード名であれば、処理がステップＳ１３６に進められる。自ノードのノード名でなければ、処理がステップＳ１３５に進められる。
【０１０６】
［ステップＳ１３５］表選択部１２３ｃは、自ノードのノード名でなければ、位置読出要求の送信元に、取得したノード名を宛先の位置情報として応答する。その後、位置読出処理が終了する。
【０１０７】
［ステップＳ１３６］表選択部１２３ｃは、自ノードのノード名であれば、個別キーマップテーブル１２３ｂに空きがあるか否かを判断する。例えば位置管理部１２３には、個別キーマップテーブル１２３ｂの最大エントリ数が設定されている。現在の個別キーマップテーブル１２３ｂ内のエントリ数が最大エントリ数に満たなければ、空きがあると判断される。空きがある場合、処理がステップＳ１３７に進められる。空きがなければ、処理がステップＳ１３８に進められる。
【０１０８】
［ステップＳ１３７］表選択部１２３ｃは、キー新規登録の位置書込処理を行う。これにより、個別キーマップテーブル１２３ｂの空きエントリに、キー値と自ノードのノード名が記録される。この位置書込処理の詳細は後述する（図１８参照）。
【０１０９】
［ステップＳ１３８］表選択部１２３ｃは、位置読出要求の送信元に、自ノードのノード名を宛先の位置情報として応答する。その後、位置読出処理が終了する。
位置読出処理では、ＶＮｏｄｅ単位で管理されていたキーの位置読出要求が出された場合、そのキーを有するイベントを処理するノードが自ノードであり、個別キーマップテーブル１２３ｂに空きがあれば、そのキーの管理が、キー単位に移行される。すなわちそのキーに関するキー値とノード名とが、個別キーマップテーブル１２３ｂに書き込まれる。これにより、使用されたキーから順に、ＶＮｏｄｅ単位での管理から、キー単位での管理に移行される。
【０１１０】
ＶＮｏｄｅ単位での管理とキー単位での管理とは、マネージャ２１０からの位置変更要求に応じた位置変更処理によっても変更される。例えばマネージャ２１０は、ノード間の負荷の差が少なくなるように、キーまたはＶＮｏｄｅについて、対応するイベントの処理を実行するノードを変更する。その際、位置変更処理に先だって、各キーに対応する状態情報の移動が行われる。
【０１１１】
図１６は、状態情報移動処理の手順の一例を示すフローチャートである。
［ステップＳ１４１］マネージャ２１０は、各ノード１００，１００ａ，１００ｂ，１００ｃから通知された負荷情報に基づいて、状態情報の移動の要否を判断する。例えばマネージャ２１０は、ノード間の負荷の差が所定値以上になっている場合、状態情報の移動をすると判断する。状態情報を移動する場合、マネージャ２１０は、負荷が高いノードで処理しているキーまたはＶＮｏｄｅに対応する状態情報を、負荷の低いノードに移動することを決定する。
【０１１２】
以下、ノード１００ａからノード１００へ状態情報を移動するものとして、ステップＳ１４２〜ステップＳ１４７の処理を説明する。
［ステップＳ１４２］マネージャ２１０は、移動対象の状態情報を有するノード１００ａのイベント処理部１３０ａに、移動する状態情報と移動先のノード１００とを指定して、状態移動依頼を送信する。
【０１１３】
［ステップＳ１４３］ノード１００ａのイベント処理部１３０ａは、状態移動依頼を受信すると、通信部１１０ａに状態情報を送信し、移動先のノード１００への状態情報の送信を依頼する。
【０１１４】
［ステップＳ１４４］通信部１１０ａは、状態情報をノード１００宛てに送信する。
［ステップＳ１４５］移動先のノード１００では、通信部１１０が状態情報を受信する。
【０１１５】
［ステップＳ１４６］状態情報を受信した通信部１１０は、イベント処理部１３０へ状態情報を転送する。
［ステップＳ１４７］イベント処理部１３０は、受信した状態情報を保持すると共に、マネージャ２１０への状態移動完了の通知を、通信部１１０に送信する。通信部１１０は、状態移動完了の通知を、マネージャ２１０に送信する。
【０１１６】
［ステップＳ１４８］マネージャ２１０は、状態情報の移動に合わせて、各キーを有するイベントを処理するノードが変更されるように、すべてのノード１００，１００ａ，１００ｂ，１００ｃに対して、位置変更要求を送信する。
【０１１７】
マネージャ２１０が送信した位置変更要求は、各ノード１００，１００ａ，１００ｂ，１００ｃで受信される。そして各ノード１００，１００ａ，１００ｂ，１００ｃそれぞれで、位置変更処理が行われる。以下、ノード１００における変更処理を詳細に説明する。
【０１１８】
図１７は、位置変更処理の手順の一例を示すフローチャートである。
［ステップＳ１５１］通信部１１０は、マネージャ２１０から位置変更要求を受信する。通信部１１０は、受信した位置変更要求をイベント転送部１２０に送信する。
【０１１９】
［ステップＳ１５２］イベント転送部１２０内の位置管理部１２３が、位置書込処理を行う。位置書込処理の詳細は後述する（図１８参照）。
［ステップＳ１５３］位置管理部１２３は、位置書込処理が終了すると、書込完了の応答を通信部１１０へ送信する。通信部１１０は、書込完了応答をマネージャ２１０に送信する。
【０１２０】
図１８は、位置書込処理の手順の一例を示すフローチャートである。
［ステップＳ１６１］位置管理部１２３の表選択部１２３ｃは、受信した位置変更要求が、ＶＮｏｄｅに関する位置変更要求なのか否かを判断する。ＶＮｏｄｅに関する位置変更要求は、特定のＶＮｏｄｅに属するキーを有するイベントを実行するノードの変更要求である。ＶＮｏｄｅに関する位置変更要求には、ＶＮｏｄｅに属するキーに対応するハッシュ値と、変更先のノードのノード名とが含まれる。ＶＮｏｄｅに関する位置変更要求であれば、処理がステップＳ１６２に進められる。ＶＮｏｄｅに関する位置変更要求でなければ、キーに関する位置の変更要求であると判断され、処理がステップＳ１６３に進められる。
【０１２１】
なおキーに関する位置変更要求には、個別キーマップテーブル１２３ｂからのキーのエントリの削除要求と、キーに対応するノード名の登録要求とがある。キーに関する位置の変更要求には、キーのキー値が含まれる。またキーに関する位置の変更要求が、キーに対応するノード名の登録要求であれば、登録するノード名が位置の変更要求に含まれる。
【０１２２】
［ステップＳ１６２］ＶＮｏｄｅに関する位置変更要求であれば、表選択部１２３ｃは、ＶＮｏｄｅマップテーブル１２３ａから、位置変更要求に示されたハッシュ値に該当するレコードを検索する。そして表選択部１２３ｃは、該当するレコードのノード名を、位置変更要求に示されたノード名に更新する。その後、位置書込処理が終了する。
【０１２３】
［ステップＳ１６３］表選択部１２３ｃは、キーに関する位置変更要求の場合、その位置変更要求が、キーのエントリの削除要求なのか否かを判断する。削除要求であれば、処理がステップＳ１６４に進められる。削除要求でなければ、処理がステップＳ１６５に進められる。
【０１２４】
［ステップＳ１６４］表選択部１２３ｃは、キーのエントリの削除要求であれば、位置変更要求に示されるキーに対応するエントリを、個別キーマップテーブル１２３ｂから検索する。そして表選択部１２３ｃは、該当するエントリを削除する。その後、位置書込処理が終了する。
【０１２５】
［ステップＳ１６５］キーのエントリの削除要求でなければ、表選択部１２３ｃは、位置変更要求に示されるキーに対応するエントリが、個別キーマップテーブル１２３ｂにあるか否かを判断する。該当するエントリがあれば、処理がステップＳ１６６に進められる。該当するエントリがなければ、処理がステップＳ１６７に進められる。
【０１２６】
［ステップＳ１６６］表選択部１２３ｃは、個別キーマップテーブル１２３ｂから、位置変更要求に示されるキーに対応するエントリを抽出する。そして表選択部１２３ｃは、該当エントリのノード名を、位置変更要求に示されるノード名に変更する。その後、位置書込処理が終了する。
【０１２７】
［ステップＳ１６７］表選択部１２３ｃは、位置変更要求に示されるキー値とノード名とを、個別キーマップテーブル１２３ｂの空きエントリに書き込む。その後、位置書込処理が終了する。
【０１２８】
以上のようにして、キーまたはＶＮｏｄｅに対応するイベントを実行するノードが変更される。ノード間の負荷が減少するように変更されることで、システム内でのノードの負荷が均等化され、システムの運用効率が向上する。
【０１２９】
なおキーまたはＶＮｏｄｅによるノードの負荷を適切に判断するため、各ノードにおいて負荷情報が適宜記録される。各ノードは、自ノードの負荷情報と、他ノードの負荷情報とを共に記録する。自ノードの負荷情報については、キーごとの負荷とＶＮｏｄｅごとの負荷とが記録される。他ノードの負荷情報については、ＶＮｏｄｅごとの負荷が記録される。以下、負荷情報記録処理について詳細に説明する。
【０１３０】
図１９は、自ノードの負荷に関する負荷情報記録処理の手順を示すフローチャートである。
［ステップＳ１７１］ノード１００のイベント処理部１３０は、定期的に自ノードで処理するイベントのキーごとの負荷を取得する。例えばイベント処理部１３０は、イベントを処理するプロセスのＣＰＵ負荷や、そのプロセスのメモリ使用量をＯＳから取得する。イベント処理部１３０は、取得した負荷情報、対応するイベントが有するキーに対応付けて、位置管理部１２３に送信する。
【０１３１】
［ステップＳ１７２］位置管理部１２３は、負荷情報に対応付けられたキーに対応する、個別キーマップテーブル１２３ｂのエントリがあるか否かを判断する。該当するエントリがあれば、処理がステップＳ１７３に進められる。該当するエントリがなければ、処理がステップＳ１７４に進められる。
【０１３２】
［ステップＳ１７３］位置管理部１２３は、受信した負荷情報に対応付けられたキーに対応する、個別キーマップテーブル１２３ｂ内のエントリに、その負荷情報（ＣＰＵ負荷、メモリ使用量）を記録する。
【０１３３】
［ステップＳ１７４］位置管理部１２３は、受信した負荷情報に対応付けられたキーのハッシュ値を計算し、そのハッシュ値に対応するエントリをＶＮｏｄｅマップテーブル１２３ａから検索する。
【０１３４】
［ステップＳ１７５］位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａの該当エントリの個別キー負荷情報に、受信した負荷情報を記録する。
［ステップＳ１７６］位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａの該当エントリの統計値（合計ＣＰＵ負荷、合計メモリ使用量）を更新する。
【０１３５】
［ステップＳ１７７］位置管理部１２３は、マネージャ２１０にキーごとの負荷情報を通知する。
このようにして、自ノードの負荷に関する負荷情報が記録される。
【０１３６】
図２０は、他ノードの負荷に関する負荷情報記録処理の手順の一例を示すフローチャートである。
［ステップＳ１８１］位置管理部１２３は、定期的に、マネージャ２１０から他ノードのキーごとの負荷情報を取得する。
【０１３７】
［ステップＳ１８２］位置管理部１２３は、負荷情報に対応するキーのハッシュ値を計算し、そのハッシュ値に対応するエントリをＶＮｏｄｅマップテーブル１２３ａから検索する。
【０１３８】
［ステップＳ１８３］位置管理部１２３は、ＶＮｏｄｅマップテーブル１２３ａの該当エントリの統計値（合計ＣＰＵ負荷、合計メモリ使用量）を更新する。
以上のようにして、位置管理部１２３は、負荷情報を更新することができる。そして位置管理部１２３の定期調整部１２３ｄは、キー単位で管理するキー（個別管理キー）の入替処理を、定期的に行う。
【０１３９】
図２１は、個別管理キー入替処理の手順の一例を示すフローチャートである。
［ステップＳ１９１］マネージャ２１０と各ノードが連携し、入替対象のキーの決定処理を行う。入替対象決定処理の詳細は後述する（図２２参照）。
【０１４０】
以下、ＶＮｏｄｅ単位で管理していたキーをキー単位で管理するようにすることを、個別管理化と呼ぶ。逆に、キー単位で管理していたキーをＶＮｏｄｅ単位で管理するようにすることを、個別管理解除と呼ぶ。
【０１４１】
［ステップＳ１９２］マネージャ２１０は、個別管理解除対象のキーの負荷と、個別管理化対象キーの負荷とを比較する。そしてマネージャ２１０は、個別管理化対象キーの負荷の方が、個別管理解除対象のキーの負荷よりも大きい場合にのみ、入替を許可する。マネージャ２１０が入替を許可すると、その旨が、定期調整部１２３ｄに通知される。入替が許可されると、処理がステップＳ１９３に進められる。すべてのキーの入替が許可されなかった場合、入替処理は終了する。
【０１４２】
［ステップＳ１９３］各ノードは、決定された入替対象のキーの入替（個別管理化または個別管理解除）を行う。入替処理の詳細は後述する（図２３参照）。
図２２は、入替対象決定処理の手順の一例を示すフローチャートである。
【０１４３】
［ステップＳ２０１］各ノード１００，１００ａ，１００ｂ，１００ｃは、自ノードが処理を実行しているイベントのキーが属するＶＮｏｄｅの負荷情報（ＣＰＵ使用率、メモリ使用量など）をマネージャ２１０に通知する。
【０１４４】
［ステップＳ２０２］マネージャ２１０は、負荷の大きなＶＮｏｄｅから順に、所定個数分のＶＮｏｄｅを選択し、個別管理化対象のキーの抽出元とする。なお収容キー数の大きなＶＮｏｄｅから順に、所定個数分のＶＮｏｄｅを選択し、個別管理化対象のキーの抽出元としてもよい。収容キー数の大きなＶＮｏｄｅを個別管理化対象のキーの抽出元とすることで、ＶＮｏｄｅ間の収容キー数の均等化を図ることができる。収容キー数でＶＮｏｄｅの選択を行うのであれば、ステップＳ２０１の負荷情報の通知は不要となり、処理の効率化が図れる。
【０１４５】
マネージャ２１０は、選択したＶＮｏｄｅに属するキーを有するイベントを処理するノードに対して、そのＶＮｏｄｅからの個別管理化対象のキーの選択を指示する。以下、ノード１００に対して指示が出されたものとする。
【０１４６】
［ステップＳ２０３］ノード１００の定期調整部１２３ｄは、マネージャ２１０が選択したＶＮｏｄｅの属するキーを、個別管理化の候補とするキーを選択する。
［ステップＳ２０４］定期調整部１２３ｄは、候補のキーと、そのキーの負荷情報とを、マネージャ２１０に通知する。
【０１４７】
［ステップＳ２０５］マネージャ２１０は、候補のキーの中から、負荷の重い所定数のキーを個別管理化対象のキーに決定する。
［ステップＳ２０６］マネージャ２１０は、ノード１００の個別キーマップテーブル１２３ｂにより個別管理しているキーの中から、負荷の軽い所定数のキーを個別管理解除キーに決定する。個別管理化対象のキーの数分の空きエントリが個別キーマップテーブル１２３ｂ内にあるかどうかを判断する。空きエントリが不足している場合、定期調整部１２３ｄは、個別キーマップテーブル１２３ｂ内の負荷の軽いキーから順に、空きエントリの不足分だけ選択し、個別管理解除対象のキーとする。
【０１４８】
図２３は、入替処理の手順の一例を示すフローチャートである。
［ステップＳ２１１］マネージャ２１０は、ノード１００に対して、個別キーマップテーブル１２３ｂ内に個別管理化対象のキーの数分の空きエントリを作成するように指示する。このときマネージャ２１０からノード１００に、個別管理解除対象のキーが通知される。
【０１４９】
［ステップＳ２１２］ノード１００の定期調整部１２３ｄは、個別管理解除対象のキーのエントリを、個別キーマップテーブル１２３ｂから削除することをマネージャ２１０に通知する。この通知は、ステップＳ２１４の後に行ってもよい。
【０１５０】
［ステップＳ２１３］定期調整部１２３ｄは、個別管理解除対象キーの負荷を、ＶＮｏｄｅマップテーブル１２３ａ内の、そのキーのハッシュ値に対応するエントリの負荷情報に追加する。例えば定期調整部１２３ｄは、個別管理解除対象キーのＣＰＵ負荷を合計ＣＰＵ負荷に加算し、メモリ使用量を合計メモリ使用量に加算する。また個別管理解除対象キーのキー値と負荷情報とを、個別キー負荷情報に追加登録する。さらに定期調整部１２３ｄは、個別管理解除対象キーの数を、収容キー数に加算する。
【０１５１】
［ステップＳ２１４］定期調整部１２３ｄは、個別管理解除対象キーのエントリを、個別キーマップテーブル１２３ｂから削除する。
［ステップＳ２１５］マネージャ２１０は、個別管理化対象キーの個別キーマップテーブル１２３ｂへの登録を、ノード１００に指示する。
【０１５２】
［ステップＳ２１６］ノード１００の定期調整部１２３ｄは、個別管理化対象キーを個別キーマップテーブル１２３ｂに登録し、個別管理化対象キーを追加したことをマネージャに通知する。
【０１５３】
［ステップＳ２１７］定期調整部１２３ｄは、個別管理化対象キーの負荷を、ＶＮｏｄｅマップテーブル１２３ａ内の、そのキーのハッシュ値に対応するエントリの負荷情報に追加する。例えば定期調整部１２３ｄは、個別管理化対象キーのＣＰＵ負荷を合計ＣＰＵ負荷から減算し、メモリ使用量を合計メモリ使用量に減算する。また個別管理化対象キーのキー値と負荷情報とを、個別キー負荷情報から削除する。さらに定期調整部１２３ｄは、個別管理化対象キーの数を、収容キー数から減算する。
【０１５４】
［ステップＳ２１８］定期調整部１２３ｄは、個別管理化対象キーのエントリを個別キーマップテーブル１２３ｂに追加する。
このようにして、キー単位で管理していたキーと、ＶＮｏｄｅ単位で管理していたキーとの管理単位の入替が行われる。この際、負荷の高いＶＮｏｄｅに属していたキーのうち、負荷の高いキーの個別管理化が行われ、キー単位で管理していたキーのうち、負荷の低いキーの個別管理解除が行われる。これにより、各ＶＮｏｄｅの負荷の統計量（合計ＣＰＵ負荷または合計メモリ使用量）と、キー単位で管理している各キーの負荷（ＣＰＵ負荷またはメモリ使用量）との差が小さくなる。
【０１５５】
次に図２４、図２５を参照し、個別管理するキーの入替例を説明する。
図２４は、入替前の状態を示す図である。図２４の例では、ハッシュ値「０」のＶＮｏｄｅが、個別管理化するキーの抽出元として選択されたものとする。現在、このＶＮｏｄｅに属するキー数は３である。個別キーマップテーブル１２３ｂの最大エントリ数は２エントリである。また、個別キーマップテーブル１２３ｂには、現在、２エントリが登録されている。入替の判断に用いる負荷情報としては、メモリ使用量のみを用いるものとする。また入替時に一度に選択するキー数は１つとする。
【０１５６】
図２４の例では、既に個別管理化するキーの抽出元とするＶＮｏｄｅが選択されているため、選択されたＶＮｏｄｅに属するキー（キー値「３」、「７９」、「３３」）の中から、負荷の最も高いキーが、個別管理化対象のキーとして選択される。図２４の例では、キー値「７９」のキーのメモリ使用量が「６００」であり、負荷が最も高い。そのためキー値「７９」のキーが、個別管理対象のキーとして選択される。
【０１５７】
また個別キーマップテーブル１２３ｂからは、最も負荷の少ないキーが、個別管理解除対象のキーとして選択される。図２４の例では、キー値「５２」のキーのメモリ使用量が「１０」であり、最も負荷が少ない。そこでキー値「５２」のキーが、個別管理解除対象のキーとして選択される。
【０１５８】
このとき個別管理化対象のキーの負荷と、個別管理解除対象のキーの負荷とが比較され、個別管理化対象のキーの負荷の方が大きければ、入替が認められる。図２４の例では、個別管理化対象のキー（キー値「７９」）の負荷は「６００」であり、個別管理解除対象のキー（キー値「５２」）の負荷「１０」よりも大きいため、入替が認められる。
【０１５９】
入替が認められると、定期調整部１２３ｄからマネージャ２１０に、キー値「５２」のキーを個別管理解除対象キーとすることが通知される。次に、ＶＮｏｄｅマップテーブル１２３ａのハッシュ値「０」のエントリの収容キー数が１加算され「４」になる。合計メモリ使用量が１０加算され「９１０」になる。またＶＮｏｄｅマップテーブル１２３ａの個別キー負荷情報に、キー値「５２」のキーの負荷情報が追加される。そして個別キーマップテーブル１２３ｂから、キー値「５２」のキーのエントリを削除される。これにより、個別キーマップテーブル１２３ｂに、空きエントリが確保される。
【０１６０】
空きエントリが作成されると、定期調整部１２３ｄからマネージャ２１０に、キー値「７９」のキーが個別管理化対象のキーとして通知される。次に、ＶＮｏｄｅマップテーブル１２３ａのハッシュ値「０」のエントリの収容キー数が１減算され「３」になる。さらに、合計メモリ使用量が「６００」減算され「３１０」になる。ＶＮｏｄｅマップテーブル１２３ａの個別キー負荷情報からは、キー値「７９」の負荷情報が削除される。そして個別キーマップテーブル１２３ｂに、キー値「７９」のエントリが追加される。
【０１６１】
図２５は、入替後の状態を示す図である。図２５に示すように、キー単位で管理するキーの入替処理を行ったことで、ハッシュ値「０」のＶＮｏｄｅの負荷が低下し、キー単位で管理されているキーのうち、最も負荷の少ないキーの負荷が増加している。その結果、ＶＮｏｄｅの負荷と、キー単位で管理しているキーの負荷との差が少なくなっている。これらの負荷の差が少なくなることで、ＶＮｏｄｅに属するキーを有するイベントを処理するノード、またはキー単位で管理しているキーに属するキーを有するイベントを処理するノードを変更する際に、ノード間の負荷の均等化が容易となる。例えば負荷が極端に高いＶＮｏｄｅがあると、そのＶＮｏｄｅに属するキーを有するイベントをどのノードに処理させるようにしても、そのノードは過負荷となってしまう。上記の入替処理を実施すれば、負荷が極端に高いＶＮｏｄｅが生じることを抑止できる。その結果、ノード間の負荷の均等化が促進される。
【０１６２】
なお、第２の実施の形態における図１２〜図２３の処理は、管理ノード２００のマネージャ２１０と各ノード１００，１００ａ，１００ｂ，１００ｃの要素とが連携して実行しているが、全体をいずれか１つの装置（例えば管理ノード）で実施することもできる。
【０１６３】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１６４】
１〜４  ノード
５，６  データ
１０  処理装置
１１  第１マップ
１２  第２マップ
１３  第１記録手段
１４  削除手段
１５  決定手段
１６  第２記録手段
１７  処理ノード変更手段
【図１】
0006464688.tif 000002
【図２】
0006464688.tif 000003
【図３】
0006464688.tif 000004
【図４】
0006464688.tif 000005
【図５】
0006464688.tif 000006
【図６】
0006464688.tif 000007
【図７】
0006464688.tif 000008
【図８】
0006464688.tif 000009
【図９】
0006464688.tif 000010
【図１０】
0006464688.tif 000011
【図１１】
0006464688.tif 000012
【図１２】
0006464688.tif 000013
【図１３】
0006464688.tif 000014
【図１４】
0006464688.tif 000015
【図１５】
0006464688.tif 000016
【図１６】
0006464688.tif 000017
【図１７】
0006464688.tif 000018
【図１８】
0006464688.tif 000019
【図１９】
0006464688.tif 000020
【図２０】
0006464688.tif 000021
【図２１】
0006464688.tif 000022
【図２２】
0006464688.tif 000023
【図２３】
0006464688.tif 000024
【図２４】
0006464688.tif 000025
【図２５】
0006464688.tif 000026