(57)【要約】  メッセージ・バス上のメッセージ・フローを削減するためのシステム、方法、およびコンピュータ読み取り可能媒体が開示される。この方法は、複数の論理演算子のうちの少なくとも１つの論理演算子が、物理ノードのグループ内の所与の物理処理ノードでの処理を必要とするかどうかを判別することを含む。論理演算子が所与の物理処理ノードでの処理を必要とする旨の決定に応答して、論理演算子が所与の物理処理ノードにピンニングされる。複数の論理演算子内の各論理演算子は、メッセージ・バス上にある物理処理ノードのグループ内の初期の物理処理ノードに割り当てられる。【選択図】  図１
2009545043.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ・バス上のメッセージ・フローを削減するための、情報処理システムを伴う方法であって、
複数の論理演算子内の少なくとも１つの論理演算子が、物理ノード・グループ内の所与の物理処理ノードでの処理を必要とするかどうかを判別するステップと、
前記論理演算子が前記所与の物理処理ノードでの処理を必要とする旨の決定に応答して、前記論理演算子が前記所与の物理処理ノードにピンニングするステップと、
前記複数の論理演算子内の各論理演算子を、メッセージ・バス上にある前記物理処理ノード・グループ内の初期の物理処理ノードに割り当てるステップと、
を含む、方法。
【請求項２】
前記複数の論理演算子内の各論理演算子に関連付けられたメッセージ・フロー量を決定するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記メッセージ・フロー量が、
統計と、
観察と、
仮定と、
のうちの少なくとも１つに基づいて決定される、請求項３に記載の方法。
【請求項４】
前記複数の論理演算子内の各論理演算子をそれぞれの初期の物理処理ノードに割り当てるステップに関連付けられた、総メッセージ・フロー・コストを決定するステップをさらに含む、請求項１に記載の方法。
【請求項５】
前記メッセージ・フロー・コストが、前記初期の物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量の合計を含む、請求項４に記載の方法。
【請求項６】
前記複数の論理演算子内の少なくとも１つの論理演算子について、前記論理演算子に関連付けられた入力メッセージ・フロー量セットの合計が、前記論理演算子に関連付けられた出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの少なくとも１つであるかどうかを判別するステップと、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに先行する所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てるステップと、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも少ないことに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに対して、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある後続位置に位置する、後続の処理ノードに割り当てるステップと、
をさらに含む、請求項１に記載の方法。
【請求項７】
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、割り当てる前記ステップが、
前記物理処理ノードが、前記論理演算子のリソース要件を満たすために使用可能なリソースを備えるかどうかを判別するステップと、
前記物理処理ノードが使用可能なリソースを備えることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードの前記メッセージ・バス上の位置に位置する前記物理処理ノードに割り当てるステップと、
をさらに含む、請求項６に記載の方法。
【請求項８】
前記複数の論理演算子内の少なくとも１つの論理演算子が、少なくとも１つの他の論理演算子の親であるかどうかを判別するステップと、
前記論理演算子が親であることに応答して、前記論理演算子が、前記論理演算子の子論理演算子が割り当てられる前記物理処理ノードに先行する、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てられるかどうかを判別するステップと、
前記論理演算子が前記先行する物理処理ノード上にあることに応答して、前記論理演算子を、前記子論理演算子が割り当てられている前記物理処理ノードに再割り当てするステップと、
をさらに含む、請求項６に記載の方法。
【請求項９】
前記複数の論理演算子を各物理処理ノードに割り当てるステップに関連付けられた総メッセージ・フロー・コストを決定するステップをさらに含む、請求項６に記載の方法。
【請求項１０】
前記メッセージ・フロー・コストが、物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量の合計を含む、請求項６に記載の方法。
【請求項１１】
前記先行する物理処理ノードおよび前記後続の物理処理ノードのうちの１つに前記論理演算子のそれぞれを割り当てるステップに関連付けられた、後続のメッセージ・フロー・コストが、前記論理演算子のそれぞれを初期物理処理ノードに割り当てるステップに関連付けられた初期メッセージ・フロー・コストよりも少ないかどうかを判別するステップと、
前記後続のメッセージ・フロー・コストが前記初期メッセージ・フロー・コストよりも少ないことに応答して、前記後続のメッセージ・フロー・コストに関連付けられた前記論理演算子の前記割り当てを選択するステップと、
をさらに含む、請求項６に記載の方法。
【請求項１２】
メッセージ・バス上のメッセージ・フローを削減するためのシステムであって、
通信に関してメッセージ・バスに結合された複数の物理処理ノードと、
前記複数の物理処理ノードに通信に関して結合された情報処理システムとを備え、前記情報処理システムは、
前記物理処理ノードのうちの少なくとも１つに常駐する複数の論理演算子のうちの少なくとも１つの論理演算子が、前記物理処理ノードのうちの１つでの処理を必要とするかどうかを判別するため、および
前記論理演算子が前記所与の物理処理ノード上での処理を必要とする旨の決定に応答して、前記論理演算子を前記所与の物理処理ノードにピンニングするための、
論理演算子ピンナと、
前記複数の論理演算子内の各論理演算子を、メッセージ・バス上にある前記複数の物理処理ノード内の初期の物理処理ノードに割り当てるための、論理演算子アサイナと、
を備える、システム。
【請求項１３】
前記複数の論理演算子内の各論理演算子に関連付けられたメッセージ・フロー量を決定するための、メッセージ・フロー量アナライザをさらに備える、請求項１２に記載のシステム。
【請求項１４】
前記複数の論理演算子内の各論理演算子をそれぞれの初期物理処理ノードに割り当てるステップに関連付けられた、総メッセージ・フロー・コストを決定するための割り当てコスト・エスティメータをさらに備え、前記メッセージ・フロー・コストは、前記初期物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量の合計を含む、請求項１２に記載のシステム。
【請求項１５】
さらに前記論理演算子アサイナは、
前記複数の論理演算子内の少なくとも１つの論理演算子について、前記論理演算子に関連付けられた入力メッセージ・フロー量セットの合計が、前記論理演算子に関連付けられた出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの少なくとも１つであるかどうかを判別し、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに先行する所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当て、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも少ないことに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに対して、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある後続位置に位置する、後続の処理ノードに割り当てる、
請求項１２に記載のシステム。
【請求項１６】
さらに前記論理演算子アサイナは、
前記先行する物理処理ノードおよび前記後続の物理処理ノードのうちの１つに前記論理演算子のそれぞれを割り当てるステップに関連付けられた、後続のメッセージ・フロー・コストが、前記論理演算子のそれぞれを初期物理処理ノードに割り当てるステップに関連付けられた初期メッセージ・フロー・コストよりも少ないかどうかを判別し、
前記後続のメッセージ・フロー・コストが前記初期メッセージ・フロー・コストよりも少ないことに応答して、前記後続のメッセージ・フロー・コストに関連付けられた前記論理演算子の前記割り当てを選択する、
請求項１に記載のシステム。
【請求項１７】
メッセージ・バス上のメッセージ・フローを削減するためのコンピュータ読み取り可能媒体であって、
複数の論理演算子内の少なくとも１つの論理演算子が、物理ノード・グループ内の所与の物理処理ノードでの処理を必要とするかどうかを判別するための命令と、
前記論理演算子が前記所与の物理処理ノードでの処理を必要とする旨の決定に応答して、前記論理演算子が前記所与の物理処理ノードにピンニングするための命令と、
前記複数の論理演算子内の各論理演算子を、メッセージ・バス上にある前記物理処理ノード・グループ内の初期の物理処理ノードに割り当てるための命令と、
を備える、コンピュータ読み取り可能媒体。
【請求項１８】
前記複数の論理演算子内の少なくとも１つの論理演算子について、前記論理演算子に関連付けられた入力メッセージ・フロー量セットの合計が、前記論理演算子に関連付けられた出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの少なくとも１つであるかどうかを判別するための命令と、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに先行する所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てるための命令と、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも少ないことに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに対して、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある後続位置に位置する、後続の処理ノードに割り当てるための命令と、
をさらに備える、請求項１７に記載のコンピュータ読み取り可能媒体。
【請求項１９】
前記複数の論理演算子内の少なくとも１つの論理演算子が、少なくとも１つの他の論理演算子の親であるかどうかを判別するための命令と、
前記論理演算子が親であることに応答して、前記論理演算子が、前記論理演算子の子論理演算子が割り当てられる前記物理処理ノードに先行する、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てられるかどうかを判別するための命令と、
前記論理演算子が前記先行する物理処理ノード上にあることに応答して、前記論理演算子を、前記子論理演算子が割り当てられている前記物理処理ノードに再割り当てするための命令と、
をさらに備える、請求項１７に記載のコンピュータ読み取り可能媒体。
【請求項２０】
前記先行する物理処理ノードおよび前記後続の物理処理ノードのうちの１つに前記論理演算子のそれぞれを割り当てるステップに関連付けられた、後続のメッセージ・フロー・コストが、前記論理演算子のそれぞれを初期物理処理ノードに割り当てるステップに関連付けられた初期メッセージ・フロー・コストよりも少ないかどうかを判別するための命令と、
前記後続のメッセージ・フロー・コストが前記初期メッセージ・フロー・コストよりも少ないことに応答して、前記後続のメッセージ・フロー・コストに関連付けられた前記論理演算子の前記割り当てを選択するための命令と、
をさらに備える、請求項１７に記載のコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に分散処理システムの分野に関し、とりわけ、分散処理システム内の処理ノード間でのメッセージ・フローの削減に関する。
【背景技術】
【０００２】
企業はますます自社のビジネス・プロセスを自動化しており、さらに重要なことには、関連する低レベルのタスクもさらに自動化している。現在、企業には、過程、動作、手順、および業務報告を文書化する厳密なブックキーピングを維持するための、サーベンス・オクスリー法（Ｓａｒｂａｎｅｓ−Ｏｘｌｅｙ）、ＨＩＰＰＡ、およびテロ対策法（Ｐａｔｒｉｏｔｉｃ  Ａｃｔ）などの内部および外部規定が求められている。これに応答して組織は、自社のビジネス・プロセスを自動化および制御するための、ビジネス・アクティビティ・モニタリング（「ＢＡＭ」）などのソリューションに目を向けている。
【０００３】
新しい連邦規定の順守の必要性に加えて、ビジネス・プロセスの自動モニタリングは、生産性の増加にもつながる。イベントはいくつかの企業階層間を流れるため、このイベントを使用して階層の様々な構成要素を一括して見ることができる。イベントは、システム全体を流れ、情報を運び、プロセス全体を支持する、血球に似ている。
【０００４】
以下の考察では、イベントを全面的に活用する複雑なモニタリング・システムによってもたらされる課題のいくつかを例示する。第１の課題は、イベント・ソースおよびモニタに関するスケーラビリティである。たとえば、複雑なモニタリング・アプリケーションの諸要件に起因して生じるイベント管理への影響を考えてみる。イベントは様々なアーキテクチャ階層間を流れ、その後、分析処理のモニタリング関係タスクについて格納され、取り出される。ビジネス・プロセス・タスクの自動化の結果として、分析のために生成された、分析に必要なイベント数が増加する。同時に、これらのイベント全体にわたって複雑さが増加していく照会についての諸要件も段階的に増大する。これらのプロセスは、同じイベント管理リソースについて競合する。システムを流れるイベントの数が増えることの他の影響は、ネットワークおよび競合リソースの輻輳である。
【０００５】
単純な照会のみを許可することによってイベント管理ストレージにかかる負荷を減らすことは、モニタリング・システムの機能および潜在能力の低下につながるため、任意選択でないことに留意されたい。他の課題は、イベントの格納および照会の競合に伴うものである。自動化されるビジネス・タスクの数および詳細が増加すると、結果として、多数のイベントが生じる。最低でも、不可欠な主要業績評価指標（「ＫＰＩ」）の計算に寄与するイベントは、他の分析のために格納するべきである。この情報は、メトリクスが示す問題の出所を理解する際に不可欠である。格納されるべきイベントの量が増加すると、イベント全体にわたる照会の数および複雑さも増加する。イベント管理データベースは更新と照会の両方をサポートしなければならないため、システム全体のボトルネックになる。
【０００６】
さらに他の課題は、ネットワークおよび計算リソースに伴うものである。たとえば、多くの現在の複雑なモニタリング・システムは、ビジネス・プロセスによって生成されるイベントの数および率が増えることから生じる、ネットワークおよびミドルウェアの輻輳を経験する。これらの複雑なモニタリング・システムは、アプリケーション・レベルで無用な計算も実行する。メトリクスの計算に必要でないイベントが依然として処理およびフィルタリングされる必要があり、これが他の潜在的なボトルネックにつながる可能性がある。多くの現在のモニタリング・システムによって、冗長計算も実行される。フィルタリング・ステップは、異なるモニタリング・コンテキスト間で、さらには異なるモニタ間で重複する計算も含む可能性がある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
したがって、前述のような従来技術に伴う問題を克服することが求められている。
【課題を解決するための手段】
【０００８】
手短に言えば、本発明に従って、メッセージ・バス上のメッセージ・フローを削減するためのシステム、方法、およびコンピュータ読み取り可能媒体が開示されている。この方法は、複数の論理演算子のうちの少なくとも１つの論理演算子が、物理ノードのグループ内の所与の物理処理ノードでの処理を必要とするかどうかを判別することを含む。論理演算子が所与の物理処理ノードでの処理を必要とする旨の決定に応答して、論理演算子が所与の物理処理ノードにピンニング（pin）される。複数の論理演算子内の各論理演算子は、メッセージ・バス上にある物理処理ノードのグループ内の初期の物理処理ノードに割り当てられる。
【０００９】
他の実施形態では、メッセージ・バス上のメッセージ・フローを削減するためのシステムが開示される。このシステムは、通信に関してメッセージ・バスに結合された複数の物理処理ノードを備える。少なくとも１つの情報処理システムが、通信に関して複数の物理処理ノードに結合される。情報処理システムは、物理処理ノードのうちの少なくとも１つに常駐する複数の論理演算子のうちの少なくとも１つの論理演算子が、物理処理ノードのうちの１つでの処理を必要とするかどうかを判別するための、論理演算子ピンナ（pinner）を含む。この論理演算子ピンナは、論理演算子が所与の物理処理ノード上での処理を必要とする旨の決定に応答して、論理演算子を所与の物理処理ノードにピンニングする。情報処理システムは、複数の論理演算子内の各論理演算子を、メッセージ・バス上にある複数の物理処理ノード内の初期の物理処理ノードに割り当てるための、論理演算子アサイナ（assignor）も含む。
【００１０】
他の実施形態では、メッセージ・バス上のメッセージ・フローを削減するためのコンピュータ読み取り可能媒体が開示される。コンピュータ読み取り可能媒体は、複数の論理演算子内の少なくとも１つの論理演算子が、物理ノード・グループ内の所与の物理処理ノード上での処理を必要とするかどうかを判別するための、命令を備える。論理演算子が所与の物理処理ノード上での処理を必要とする旨の決定に応答して、論理演算子が所与の物理処理ノードにピンニングされる。複数の論理演算子内の各論理演算子は、メッセージ・バス上にある物理処理ノードのグループ内の初期の物理処理ノードに割り当てられる。
【００１１】
本発明の一利点は、分散ストリーム処理システムの構成要素間でのメッセージ・フローが削減され、処理の負荷が平均化されることである。本発明の他の利点は、イベントのストレージおよび照会によって生成されるデータの輻輳が、サブスクライビング（subscribing）・アプリケーションに不要なイベントを識別することによって緩和されることである。一実施形態では、アプリケーション・モデルのモニタリング計算モデルに基づくモデル駆動型「データ弁別」手法を使用して、サブスクライビング・アプリケーションにとって有用でないイベントを除去する。これにより、ネットワークに送信されるメッセージ数の削減、異なる構成要素での計算の削減、および冗長フィルタリング条件の削減が提供される。
【００１２】
添付の図面は、さらに様々な実施形態を例示する働き、および、すべてが本発明に従った様々な原理および利点を説明する働きをするものであって、同じ参照番号は別々の図面全体を通じて同一かまたは機能的に同様の要素を表し、以下の詳細な説明と共に明細書に組み込まれ、その一部を形成する。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に従った、バス接続された分散処理システムにおけるイベント・フローを示すシステム流れ図である。
【図２】本発明の実施形態に従った、分散処理システムを示す図である。
【図３】本発明の実施形態に従った、情報処理システムを示す詳細図である。
【図４】本発明の実施形態に従った、例示的メッセージ・バスを示す図である。
【図５】本発明の実施形態に従った、物理処理ノードへの論理演算子のピンニングを示す有向非巡回グラフである。
【図６】本発明の実施形態に従った、メッセージ・フロー量を示すように論理演算子に注釈が付けられた、図５の有向非巡回グラフを示す図である。
【図７】本発明の実施形態に従った、論理演算子が初期の物理処理ノードに割り当てられた、図５の有向非巡回グラフを示す図である。
【図８】本発明の実施形態に従った、図７における親論理演算子の、子論理演算子に割り当てられた物理処理ノードへの再割り当てを示す図である。
【図９】本発明の実施形態に従った、図７における論理演算子の、物理処理ノードへの再割り当てを示す図である。
【図１０】本発明の実施形態に従った、論理演算子を物理処理ノードへ初期に割り当てる例示的プロセスを示す、動作流れ図である。
【図１１】本発明の実施形態に従った、論理演算子を物理処理ノードへ再度割り当てる例示的プロセスを示す、動作流れ図である。
【図１２】本発明の実施形態に従った、親論理演算子を、子論理演算子に割り当てられた物理処理ノードへ再度割り当てる例示的プロセスを示す、動作流れ図である。
【発明を実施するための形態】
【００１４】
当業者であればわかるように、本発明は、ハードウェアまたはソフトウェア内で、あるいはハードウェアおよびソフトウェアの組み合わせ内で、生成可能である。しかしながら一実施形態では、本発明はソフトウェア内で実装される。好ましい実施形態に関連して開示されたような本発明の原理に従ったシステムまたは方法は、説明または請求された個々の機能またはステップを実行するための別々の要素または手段、あるいは開示または請求された機能またはステップのうちのいずれかの性能を組み合わせた１つまたは複数の要素または手段を有する、単一のコンピュータ・システム内で、生成可能であるか、あるいは、当業者であればわかるような任意の好適な手段によって相互接続された、分散コンピュータ・システム内で配置構成可能である。
【００１５】
好ましい実施形態に関連して開示されたような本発明の原理によれば、本発明および本発明の原理はいかなる特定種類のコンピュータ・システムにも限定されないが、当業者であればわかるように、説明された機能および説明された方法ステップを実行するために配置構成された任意の汎用コンピュータと共に使用可能である。前述のようなこうしたコンピュータの動作は、当業者であればわかるように、コンピュータの動作または制御で使用するために媒体上に含まれたコンピュータ・プログラムに従うものとすることができる。コンピュータ・プログラムを保持するかまたは含むために使用可能なコンピュータ媒体は、当業者であればわかるように、内蔵メモリなどのコンピュータの装備品とするか、またはディスクなどの移送可能媒体上にあるものとすることができる。
【００１６】
本発明は、いかなる特定のコンピュータ・プログラムまたは論理または言語、あるいは命令にも限定されないが、当業者であればわかるように、任意のこうした好適なプログラム、論理、または言語、あるいは命令で実施することができる。任意のこうしたコンピューティング・システムは、開示された発明の原理を制限することなく、とりわけ、コンピュータがデータ、命令、メッセージまたはメッセージ・パケット、および他のコンピュータ読み取り可能情報を、コンピュータ読み取り可能媒体から読み取ることができるようにする、少なくともコンピュータ読み取り可能媒体を含むことができる。コンピュータ読み取り可能媒体は、ＲＯＭ、フラッシュ・メモリ、フロッピィ・ディスク、ディスク・ドライブ・メモリ、ＣＤ−ＲＯＭ、および他の永続ストレージなどの、不揮発性メモリを含むことができる。加えてコンピュータ読み取り可能媒体は、たとえば、ＲＡＭ、バッファ、キャッシュ・メモリ、およびネットワーク回路などの、揮発性ストレージを含むこともできる。
【００１７】
さらに、コンピュータ読み取り可能媒体は、ネットワーク・リンクあるいはネットワーク・インターフェースまたはその両方などの一時状態媒体内に、コンピュータ読み取り可能情報を含むことができる。本発明は、ある実施形態に従って、メモリ・コピー動作のためのより効率的なメカニズムを提供することによって、従来技術に伴う問題を克服する。本発明は、プロセッサが、メモリ・コピー動作中に後続の命令の実行を続行できるようにし、それによって不要なプロセッサのダウンタイムを避ける。
【００１８】
イベント・バス接続システムに関する例示的なシステム・フロー
図１は、イベント・エミッタ１０２、１０４、１０６およびコンシューマ１０８のバス接続システム１００における、イベントおよびさらにはメタデータの流れを示す。一実施形態では、イベント・エミッタ１０２、１０４、１０６が様々なイベントを生成し、これらのイベントを、本明細書では「メッセージ・バス１１０」と呼ばれる共通イベント・インフラストラクチャ（たとえばイベント／メッセージ・バス１１０）に送信する。一実施形態では、イベントとは、状態の変更に関連する情報を含むメッセージである。たとえば、センサまたはタイマからの読み取りである。イベントは、時間に依存した情報を含むことが可能であり、構造化または非構造化テキストとすることができる。
【００１９】
一実施形態では、多くのイベントは、その後のデータ・マイニングのためにイベント・データベース１１２に格納される。さらにイベントは、イベントが発生した場合にコンシューマ・アプリケーション１０８などのイベント・モニタに送達することができる。たとえば、エミッタはメッセージ・バス１１０を介してイベント・モニタ１０８にイベントを伝送する。別の方法として、モニタ（コンシューマ１０８）で処理要件が生成され、エミッタ１０４まで（選択的に）押し下げられる場合がある。このプロセスは、プッシュ／非同期モデルと呼ぶことができる。別の方法として、イベント・モニタは、イベント・データベース１１２の照会を介してイベントを取り出すことができる。このプロセスはプル／同期モデルと呼ぶことができる。非同期的に送達されたイベントは、より高位の主要業績評価指標（「ＫＰＩ」）を計算するために、通常、モニタ（たとえばコンシューマ・アプリケーション１０８）内でさらに処理される。一実施形態では、イベント・バス１１０は、相関およびイベント格納／取り出しの責務を負うが、モニタは、ＫＰＩの計算およびモニタリング・ダッシュボードへの送達の責務を負う。一実施形態では、モニタリング・ダッシュボードは、モニタリング・タスクからの結果を分析者などのユーザに提供する。
【００２０】
複雑な相関または大量のイベント格納／取り出しを体験すると、メッセージ・バス１１０はボトルネックになる可能性がある。同様に、コンシューマ・アプリケーション１０８などのモニタは、イベント送達および複雑なＫＰＩ計算規則の場合、過負荷となる可能性がある。多くのイベントがいずれかのダッシュボード・インジケーションに寄与せず、除去される可能性があるため、これらのイベントは不必要な負荷をメッセージ・バス１１０およびモニタ１０８に加える。したがって、本発明の一利点は、多くのイベントのフィルタリング動作および格納動作が、メッセージ・フローを削減するためにイベント・エミッタ１０２、１０４、１０６方向へ「アップストリーム」に押し上げられ、これによってメッセージ・バス１１０でのボトルネックを最小限にすることである。
【００２１】
一実施形態では、フィルタリング動作および格納動作をイベント・エミッタ１０２、１０４、１０６のより近くに配置することは、ビジネス分析サブスクリプション（subscription）・エクストラクタ（「ＢＡＳＥ」）モジュール１１４、ならびにイベント全体にわたる条件の配置および分析（「ＰＬＡＣＥ」）モジュール１１６を使用して達成可能である。一実施形態では、ＢＡＳＥモジュール１１４は、モニタ１０８からイベント・サブスクリプションを分析し、これらのサブスクリプションから、展開可能な（deployment-ready）独立サブスクリプションの正規セットを抽出する。一実施形態では、サブスクリプションとは処理済みイベントの要求である。処理は、フィルタリング条件などの基本的なものとするか、結合などのより複雑なものとすることができる。一実施形態では、展開可能なサブスクリプションとは、独立して正しく処理されるように正しいフォーマットで形成または作成された記述である。一実施形態では、ＰＬＡＣＥモジュール１１６は、これらのサブスクリプションを入力と解釈し、依存性および負荷についての考慮事項に基づいて、それぞれのサブスクリプションをどれだけ「アップストリーム」に押し上げるべきかを決定する。一実施形態では、ＢＡＳＥモジュール１１４は、モニタ１０８によって使用されるモニタリング・モデルの仕様を使用する。ＢＡＳＥおよびＰＬＡＣＥモジュール１１４、１１６については、以下でさらに詳細に論じる。
【００２２】
例示的な分散ストリーム処理システム
図２に示されるように、本発明の実施形態に従った例示的な分散処理システム２００が示される。図２は、物理処理ノード２０２、２０４、２０６、２０８、２１０のサブセットを介してシステム２００に入る、様々なリアルタイム・ストリーム２１２、２１４、２１６、２１８を示す。一実施形態では、分散処理システム２００は、図１に示されたメッセージ・バス１１０などのメッセージ・バスを介して互いの間でメッセージを渡す、物理処理ノードのシステムである。処理ノード２０２、２０４、２０６、２０８、２１０は、たとえば単一のクラスタ内に一緒に配置されるか、または広域にわたって地理的に分散される場合がある。
【００２３】
図２は、論理演算子のネットワークとして処理ノード２０２、２０４、２０６、２０８、２１０上に展開されたアプリケーション、またはＰＥ  Ａ  ２２０などの処理要素（「ＰＥ」）も示す。各データ・ストリーム２１２、２１４、２１６、２１８は、データ・ストリームの基本情報単位である、一連のストリーム・データ・オブジェクト（ＳＤＯ）からなる。各処理要素は、その入力データ・ストリームから受け取ったＳＤＯ上で、たとえば選択、フィルタリング、集合、相関、分類、または変換などの、何らかの計算を実行する。一実施形態では、各物理処理ノード２０２、２０４、２０６、２０８、２１０を、イベントのプロデューサ（producer）、イベントのコンシューマ（consumer）、またはその両方とすることができる。
【００２４】
例示的情報処理システム
図３は、情報処理システムの詳細を示すブロック図である。一実施形態では、情報処理システムは、図２の物理処理ノード２０２、２０４、２０６、２０８、２１０のいずれかとすることができる。他の実施形態では、情報処理システムは、図２の物理処理ノード２０２、２０４、２０６、２０８、２１０に通信に関して結合された、別個かつ異質な情報処理システムである。
【００２５】
情報処理システムは、本発明の例示的実施形態を実施するように適合された、好適に構成された処理システムに基づく。同様に、任意の好適に構成された処理システムは、本発明の諸実施形態によって、たとえばパーソナル・コンピュータ、ワークステーションなどの情報処理システムとしても使用可能である。情報処理システムは、コンピュータ３０２を含む。コンピュータ３０２は、システム・バス３１４を介して、主メモリ３０６、大容量ストレージ・インターフェース３０８、ターミナル・インターフェース３１０、およびネットワーク・アダプタ・ハードウェア３１２に接続された、プロセッサ３０４を有する。大容量ストレージ・インターフェース３０８は、データ・ストレージ・デバイス３１６などの大容量ストレージ・デバイスを情報処理システムに接続するために使用される。特定タイプのデータ・ストレージ・デバイスの１つは、データをＣＤ  ３１８またはその等価物に格納し、そこからデータを読み取るために使用可能な、ＣＤドライブなどのコンピュータ読み取り可能媒体である。他のタイプのデータ・ストレージ・デバイスは、たとえばＮＴＦＳタイプのファイル・システム動作をサポートするように構成されたデータ・ストレージ・デバイスである。
【００２６】
主メモリ３０６は論理演算子ピンナ３２０を含む。論理演算子ピンナ３２０は、一実施形態では、論理演算子（たとえばＳＥＬＥＣＴ、ＪＯＩＮなど）が特定の物理処理ノードによる処理を必要とするかどうかを判別する。たとえば、オリジナルのイベント・エミッタでは、イベントのエミットを実行する必要があり、モニタリング構成要素（たとえばコンシューマ・アプリケーション１０８）によってＫＰＩ結果を戻す必要がある。一実施形態では、論理演算子は、処理済のイベントあたりのコスト、選択性、入力および出力条件、制約、およびそれに関連付けられたその他を有することができる。論理演算子が特定の物理処理ノードによる処理を必要とする場合、論理演算子ピンナ３２０は、その演算子をその必要なノードにピンニングする。言い換えれば、論理演算子がピンニングされた場合、その演算子は他の物理処理ノードに割り当てられない。
【００２７】
主メモリ３０６は論理演算子アノテータ（annotator）３２２も含む。論理演算子アノテータ３２２は、一実施形態では、論理演算子のメッセージ・フロー量を決定する。たとえば入力メッセージ・フロー量および出力メッセージ・フロー量は、各論理演算子について決定される。論理演算子アノテータ３２２は、一実施形態では、各論理演算子にその入力／出力メッセージ・フロー量を用いて注釈を付ける。主メモリ３０６は、論理演算子アサイナ３２４も含む。論理演算子アサイナ３２４は、一実施形態では、各論理演算子を物理処理ノードに割り当てる。たとえば論理演算子アサイナ３２４は、一実施形態では、各論理演算子を初期の物理処理ノードに割り当てる。
【００２８】
論理演算子の物理処理ノードへの初期割り当て後、コスト・エスティメータ３２６は、初期割り当てに関連付けられた総メッセージ・フロー量を推定することができる。総メッセージ・フロー量は、たとえば、物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量に基づく。論理演算子アサイナ３２４は、一実施形態では、論理演算子の物理処理ノードへの後続の割り当ても実行する。たとえばメッセージ・フロー量アナライザ３２８は、各論理演算子の入力および出力メッセージ・フロー量を分析する。メッセージ・フロー・アナライザ３２８は、次に、メッセージ・フロー入力量の合計がメッセージ・フロー出力量の合計よりも多いかまたはこれに等しいかどうかを判別する。これが真の場合、論理演算子アサイナ３２４は、論理演算子に割り当てられた現在の物理処理ノードの位置に先行する、所与のメッセージ・フロー・シーケンスに関するイベント／メッセージ・バス上のある位置に位置する物理処理ノードに、論理演算子を割り当てる。
【００２９】
論理演算子の入力量の合計が出力量の合計よりも多いかまたはこれに等しい場合、論理演算子はフィルタリングを実行している可能性が高い。論理演算子を再割り当てすることによって、時間的に早くそのフィルタリングを実行するため、メッセージ・バス上のボトルネックを避けるのに役立つ。たとえば、フィルタリングがメッセージ・バス１１０上のさらに下流で実行される場合、メッセージを必要としない物理処理ノードに不必要なメッセージが渡される。入力量の合計が出力量の合計よりも大きくないかまたはこれに等しくない場合、論理演算子はメッセージを生成している可能性が高い。したがって論理演算子アサイナは、論理演算子に現在割り当てられている物理処理ノードの位置に後続の、所与のメッセージ・フロー・シーケンスに関するイベント／メッセージ・バス上のある位置に位置する物理処理ノードに、論理演算子を再割り当てする。これによって、メッセージのコンシューマのより近くにメッセージを生成し、イベント／メッセージ・バス上のボトルネックを防ぐことができる。
【００３０】
いったん論理演算子が再割り当てされると、割り当てコスト・エスティメータ３２６によって、この後続割り当てに関する総メッセージ・フロー・コストが決定される。論理演算子アサイナ３２４は、初期の割り当てに関連付けられたメッセージ・フロー・コストと、後続の割り当てのメッセージ・フロー・コストとを比較する。後続のメッセージ・フロー・コストが初期のメッセージ・フロー・コストよりも低い場合、論理演算子アサイナはこの割り当てを選択する。他の実施形態では、割り当てプロセスの多数の反復を実行して、メッセージ・フロー・コストが最も低い可能な割り当て構成を決定することができる。
【００３１】
他の実施形態では、論理演算子アサイナ３２４は、物理処理ノードを論理演算子に割り当てる場合に、処理ノードの使用可能リソースを考慮に入れる。たとえば論理演算子アサイナ３２４が、先行する物理処理ノードに論理演算子を再割り当てすべきである旨を決定した場合、論理演算子アサイナ３２４は、一実施形態では、論理演算子の処理要件が物理処理ノードの使用可能リソースよりも多いかどうかを判別し、このノードは論理演算子に割り当てられない。他の実施形態では、論理演算子アサイナ３２４は物理処理ノードに論理演算子を再割り当てした後、現在その子論理演算子に割り当てられている物理処理ノードに先行する何らかの親論理演算子が、物理処理ノードに割り当てられているかどうかを判別する。これが真である場合、論理演算子アサイナ３２４は、親論理演算子を子論理演算子の物理処理ノードに再割り当てする。これにより、親論理演算子と子論理演算子との間を流れるメッセージが、メッセージ・バス上の１つの処理ノードから他の処理ノードへの流れと比較して同じ処理ノード上に発生可能となり、リソースが節約される。
【００３２】
さらに他の実施形態では、ＢＡＳＥモジュール１１４が主メモリ３０６に含まれることも可能である。ＰＬＡＣＥモジュールも主メモリ３０６に含まれることが可能であり、主メモリ３０６内に常駐する前述の要素の１つまたは複数を備える。
【００３３】
主メモリ３０６のそれぞれの構成要素は、主メモリ３０６内に同時に常駐するように示されているが、常時、あるいは同時に、主メモリ３０６内に完全に常駐する必要がないことは明らかである。一実施形態では、情報処理システム３００は、従来の仮想アドレス指定メカニズムを利用して、プログラムが、主メモリ３０６およびデータ・ストレージ・デバイス３１６などの複数の小規模なストレージ・エンティティへのアクセスではなく、本明細書ではコンピュータ・システム・メモリとして表される、大規模な単一ストレージ・エンティティへのアクセスを有するかのように挙動できるようにする。「コンピュータ・システム・メモリ」という用語は、本明細書では、情報処理システム３００の仮想メモリ全体を総称的に言い表すために使用されることに留意されたい。
【００３４】
コンピュータ３０２については、１つのＣＰＵ  ３０４のみが示されているが、複数のＣＰＵを備えるコンピュータ・システムが等しく効果的に使用可能である。本発明の諸実施形態は、それぞれが、ＣＰＵ  ３０４から処理をオフロードするために使用される別々の完全にプログラミングされたマイクロプロセッサを含むインターフェースを、さらに組み込む。端末インターフェース３１０は、１つまたは複数の端末３３０をコンピュータ３０２に直接接続して、コンピュータ３０２にユーザ・インターフェースを提供するために使用される。これらの端末３３０は、非インテリジェントまたは完全にプログラム可能なワークステーションであることが可能であり、システム管理者またはユーザが情報処理システム３００と通信できるようにするために使用される。端末３３０は、コンピュータ３０２に接続され、ビデオ・アダプタ、ならびに、キーボード、ポインティング・デバイスなどのためのインターフェースを含む、端末Ｉ／Ｆ  ３１０に含まれる端末インターフェース・ハードウェアによって制御される、ユーザ・インターフェースおよび周辺デバイスで構成されることも可能である。
【００３５】
主メモリ３０６に含まれるオペレーティング・システム（図示せず）は、Ｌｉｎｕｘ、ＵＮＩＸ、Ｗｉｎｄｏｗｓ  ＸＰ、およびＷｉｎｄｏｗｓ  Ｓｅｒｖｅｒ  ２００３オペレーティング・システムなどの、好適なマルチタスク・オペレーティング・システムである。本発明の諸実施形態は、任意の他の好適なオペレーティング・システムを使用することができる。本発明の一部の実施形態は、オペレーティング・システムの構成要素（図示せず）の命令が、情報処理システム３００内に配置された任意のプロセッサ上で実行できるようにする、オブジェクト指向フレームワーク・メカニズムなどの、アーキテクチャを利用する。ネットワーク・アダプタ・ハードウェア３１２は、無線ネットワーク、ＷＬＡＮ、ＬＡＮなど（図示せず）のネットワークへのインターフェースを提供するために使用される。本発明の諸実施形態は、現在のアナログあるいはデジタル技法またはその両方を含むか、あるいは、将来のネットワーキング・メカニズムを介する、任意のデータ通信接続を使用して動作するように適合可能である。
【００３６】
本発明の例示的な諸実施形態について、完全に機能するコンピュータ・システムとの関連において説明しているが、当業者であれば、諸実施形態が、たとえばＣＤ  ３１８などのＣＤ／ＤＶＤ、または他の形の記録可能媒体を介したプログラム製品として、あるいは任意のタイプの電子伝送メカニズムを介して、配布可能であることを理解されよう。
【００３７】
例示的メッセージ・バス
図４は、一実施形態では共通イベント・インターフェースである、例示的イベント／メッセージ・バス４１０を示す。一実施形態では、物理処理ノード４０２、４０４、４０６、４０８、４１４が通信に関してメッセージ・バス４１０に結合される。物理処理ノードは、一実施形態では、イベント／メッセージのプロデューサ、あるいは、モニタリング・アプリケーションなどのイベント／メッセージのコンシューマ、またはその両方を、含むことができる。一実施形態では、各物理処理ノード４０２、４０４、４０６、４０８、４１４は、コストおよび選択性などの意味論的および計算上の制約のセットに関連付けられる。これらの制約は、一実施形態では、どの物理処理ノード上に論理演算子が配置できるかを指示する。メッセージ・バス４１０は、一実施形態では、イベント・エミッタによって生成されたトピックにサブスクライブする。これらのトピックに関して発行されたメッセージは、メッセージ・バス４１０によって処理あるいは格納またはその両方が実行され、その後、それらのイベントにサブスクライブしている論理演算子へとルーティングされる。他方で、論理演算子はイベントの受け取りおよび処理を実行する。論理演算子は、ビジネス観察モニタ・モデルなどのモニタリング・モデルに従って、受け取ったメッセージをさらに処理する。他方でアプリケーションは、通常は結果が戻されるエンド・ポイントである。
【００３８】
アプリケーションによって使用されるモニタリング計算モデルは、一実施形態では、論理演算子４１４のＤＡＧ  ４１２によって表すことができる。ＤＡＧ  ４１２は、論理演算子を表すノードを備える。各論理演算子４１４は、一実施形態では、関連するコスト、選択性などを有する。たとえばコストは、時間単位あたりに処理されるメッセージの数とすることができる。一実施形態では、リーフ・ノードは、着信するイベントを処理する論理演算子であり、親のないノードは、主要業績評価指標（「ＫＰＩ」）の計算を完了する論理演算子である。一実施形態では、ＢＡＳＥモジュール１１４は、イベント・バス１１０またはエミッタへ押し下げることができる、演算子の部分グラフを抽出する。
【００３９】
ＢＡＳＥモジュール１１４は、一実施形態では、すべてのモニタリング・モデルを分析することから、アーキテクチャ上のフレームワークの「外部の」構成要素として説明することができる。これらのサブスクリプションはＸＭＬファイルに格納され、すべての構成要素に配布するためにＰＬＡＣＥに与えられる。ある展開では、ＢＡＳＥモジュール１１４は、サブスクリプションが変更されるごとに、またはそれほど頻繁でなく、実行することができる。ＢＡＳＥモジュール１１４がより頻繁に実行されるほど、各フィルタリング条件の選択性が高くなる。最低でも、モニタリング構成要素の範囲が「拡大される」、すなわちより多くのイベントを受け入れると必ず、ＢＡＳＥモジュール１１４が実行されなければならないことに留意されたい。これは、必要なイベントの不正なフィルタリングを避けることに役立つ。
【００４０】
ＰＬＡＣＥモジュール１１６は、分散処理システム２００内の、ＢＡＳＥモジュール１１４によって導出されたサブスクリプションと処理機能を備えた構成要素との間の、コーディネータである。ＰＬＡＣＥモジュール１１６は、ＢＡＳＥモジュール１１４によって生成されたＸＭＬファイルからのＤＡＧサブスクリプションを読み取り、ロード・バランシング・プロトコルと同様のプロトコルを介して他の構成要素と対話する。サブスクリプションの形の計算グラフがエミッタまで押し下げ可能な場合、これはエミッタ・フィルタリング条件に変わり、それによってエミッタによって生成されるイベントの数が削減される。サブスクリプションがメッセージ・バス４１０に押し入れられた場合、相関エンジンにフィルタリング条件を追加することが可能であり、それによってモニタリング・コンテキストに送達されるイベントの数が削減される。
【００４１】
負荷を考慮に入れるために、一実施形態では、ＰＬＡＣＥモジュール１１６は、処理構成要素、それらの機能、および可用性を表すトポロジ構造を構築する。ＰＬＡＣＥモジュール１１６は、そのホストの負荷を定期的にモニタリングし、標準的なロード・バランシング・プロトコルを使用してこの情報をその隣接するＰＬＡＣＥ構成要素と交換する。一実施形態では、ＰＬＡＣＥモジュール１１６は、（ＤＡＧサブスクリプションからの）論理演算子を、処理機能を備えたイベント・コンシューマまたはエミッタである物理ノードに割り当てる。この割り当てプロセスについて、以下で考察する。
【００４２】
物理処理ノードへの論理演算子の割り当て
図５〜図９は、物理処理ノードへの論理演算子の割り当てを示すＤＡＧを示す。図５は、論理演算子に対応する複数のノードを備えるＤＡＧ  ５００を示す。図５（および図６〜図９）は、物理処理ノード５０２、５０４、５０６、５０８、５１２、５１４、５１６のセットを含む、例示的メッセージ・バス５１０も含む。メッセージ・バス５１０は、イベント・バス５１０上の物理処理ノードの配置を示すための参照として示される。たとえば、所与のメッセージ・フロー・シーケンスでは、物理処理ノードＣ０  ５０２は、物理処理ノードＣ１  ５０４より前に処理を実行する。
【００４３】
前述のように、各論理演算子は、処理ノードに演算子を割り当てる場合に論理演算子アサイナ３２４によって使用される、メッセージ・プロセスあたりの関連コスト、選択性、入力および出力条件、制約などを含む。一実施形態では、物理処理ノード５０２、５０４、５０６、５０８、５１２、５１４、５１６は、サブスクリプションの受け入れおよび処理のための既知の機能（たとえば、サブスクリプションを処理するために割り振られたメモリおよびＣＰＵリソース）も有する。いずれかの論理演算子が特定の物理処理ノード上での処理を必要とする場合、これらの論理演算子はそのノードにピンニングされる。たとえば一実施形態では、論理演算子５１８、５２０、５２２、５２４、５２６、５２８、５３０、５３２は、それぞれ物理処理ノードＣ０  ５０２、Ｃ１  ５０４、ｅ１  ５０８、ｅ２  ５１２、ｅ３  ５１４、ｅ６  ５１６上での処理を必要とする。したがって、これらの論理演算子５１８、５２０、５２２、およびエミット側論理演算子５２４、５２６、５２８、５３０、５３２が、これらの物理処理ノードにピンニングされる。言い換えれば、ピンニングされた論理演算子５１８、５２０、５２２、５２４、５２６、５２８、５３０、５３２は、他の物理処理ノードに再割り当てされない。ピンニングされた論理演算子は、論理演算子内の黒丸で示される。
【００４４】
一実施形態では、１つの論理演算子を他の論理演算子に接続している各縁部に、図６に示されるような予測フロー量の注釈が付けられる。たとえば、論理演算子５２４から論理演算子５２２への予測メッセージ・フロー量は、時間単位あたり１５メッセージである。一実施形態では、予測メッセージ・フロー量は、分布あるいは初期量またはその両方の仮定、観察、高／低または高／中／低の格付けなどの単純な仮定などから算出された、統計から決定される。その後、論理演算子は、図７に示されるように初期物理処理ノードに割り当てられる。たとえば、ピンニングされた部分グラフ７３４、７３６が、ルートのホスティング構成要素に割り当てられる。ピンニングされた部分グラフとは、一実施形態では、ルートとしてピンニング・ノードを有する部分グラフであり、すべての子はピンニングされない。時間単位あたりのメッセージとしての初期コストは、一実施形態では、初期割り当てについて決定される。たとえば、図７に示された初期割り当ての区画１  ７３４のコストは、（１５＋４０＋２＋２１＋１）（２）＝１５８メッセージ／時間単位であり、初期割り当ての区画２  ７３６のコストは、（８＋８＋１０＋１）（２）＝５４メッセージ／時間単位である。したがって、初期割り当ての総コストは、２１２メッセージ／時間単位である。メッセージはメッセージ・バス５１０上で１つの物理ノードから他の物理処理ノードへと流れるため、各部分グラフ７３４、７３６のメッセージ・フロー・コストは２倍される。
【００４５】
物理処理ノードへの論理演算子の初期割り当ては、物理処理ノードのリソースに関する実行不可能なソリューションを生み出す可能性があることに留意されたい。しかしながら、以下で考察するように、この初期割り当ては、より最適な割り当て構成を生み出す割り当てを決定するためにさらに調整される。
【００４６】
図８は、図７に示された物理処理ノードの初期割り当ての調整を示す。ＤＡＧ  ５００の下部から始まり、上方へと移動すると、各演算子には「初期」から「後期」までの配置選択肢の順序付けセットが割り当てられる。これは、一実施形態では、論理演算子の入力メッセージ・フロー量の合計と出力メッセージ・フロー量の合計とを比較することによって実施される。たとえば、入力メッセージ・フロー量の合計が出力メッセージ・フロー量の合計よりも多いかまたはこれに等しい場合、論理演算子は物理処理ノード上で可能な限り「初期」に配置される。たとえば、最初は物理処理ノードＣ１  ５０４に割り当てられたノードｎ８  ８３８は、４０の入力メッセージ・フロー量および２０の出力メッセージ・フロー量を有する。したがってノードｎ８  ８３８は、現在はノードｎ８  ８３８に割り当てられている物理処理ノードの位置に先行する、所与のメッセージ・フロー・シーケンスに関するメッセージ・バス５１０上のある位置に位置する物理処理ノードに、再割り当てされる。
【００４７】
論理演算子が、入力されているメッセージ数よりも少ない数のメッセージを出力している場合、この演算子はフィルタリングを実行している可能性が高い。フィルタリング演算子を上流へ移動することによって、それらは後期ではなく初期に実行されるため、不必要なメッセージはそれらを必要としないアプリケーションに渡されない。これにより、メッセージ・バス５１０上のボトルネックが最小限となる。一実施形態では、論理演算子を物理処理ノードに割り当てる際に、物理処理ノードの使用可能リソースが考慮に入れられる。言い換えれば、論理演算子に関連付けられたコストよりも使用可能リソースが少ない場合、この特定の処理ノードは論理演算子に割り当てられない。
【００４８】
入力メッセージ・フロー量の合計が出力メッセージ・フロー量の合計よりも少ない場合、論理演算子はできる限り「後期」に配置され、物理処理ノードの使用可能リソースが与えられる。たとえば、初期に物理処理ノードＣ０  ５０２に割り当てられたノード（論理演算子）ｎ１０  ８４０は、１１の入力メッセージ・フロー量および４７の出力メッセージ・フロー量を有する。したがって、ノードｎ１０  ８４０は、ノードｎ１０  ８４０に割り当てられた現在の物理処理ノードである、Ｃ１  ５０４の位置に後続の、所与のメッセージ・フロー・シーケンスに関するメッセージ・バス５１０上のある位置に位置する、物理処理ノードＣ２  ５０６に再割り当てされる。一実施形態では、処理ノードは、受け取られているメッセージの数よりも多くのメッセージを出力している場合、メッセージのプロデューサである可能性が高い。これらの論理演算子を物理処理ノードへと移動することによって、メッセージの生成は可能な限り後期に実行されるため、メッセージ・バス１１０は、ボトルネックを発生させるようなメッセージで飽和されることがない。
【００４９】
一実施形態では、サイクルが解決される。言い換えれば、親論理演算子ごとに、そのいかなる子論理演算子よりも「初期」の物理処理ノードに割り当てられているかどうかが判別される。これが真である場合、親論理演算子は、その子の物理処理ノードに再割り当てされる。たとえば図８は、物理処理ノードＣ０  ５０２に割り当てられている親論理演算子ｎ１１  ８４２を示す。しかしながら、その子論理演算子ｎ１２  ８４４は、Ｃ０  ５０２よりも「後期」の処理ノードである物理処理ノードＣ１  ５００に割り当てられる。この例では、ノードＩＤは任意であることに留意されたい。これによりメッセージは、メッセージ・バス５１０上を進ませるために、親ノードｎ１１  ８４２から、その子ノードｎ１２  ８４４へ、およびその逆へと伝送される。したがって親ノードは、物理処理ノードＣ０  ５０２へと再割り当てされ、現在この物理処理ノードは、図９に示されるように、子ノードｎ１２  ８４４に割り当てられている。したがって、親ノードｎ１１  ８４２と子ノードｎ１２  ８４４との間のメッセージはメッセージ・バス５１０を横切る必要がなく、それによってシステム・リソースが節約され、ボトルネックが最小限となる。
【００５０】
一実施形態では、再割り当てされた物理処理ノード構成に関連付けられたコストも決定される。たとえば、物理処理ノードＣ０  ５０２に割り当てられている論理演算子のコストは（８＋８）（２）＋４７＝７９であり、物理処理ノードＣ１  ５０４に割り当てられている論理演算子のコストは（１５＋１０＋２＋２１＋１）（２）＝９８であり、物理処理ノードＣ２  ５０６に割り当てられている論理演算子のコストは（１０＋１）＝１１であって、再割り当てに関する総メッセージ・フロー・コストは７９＋９８＋１１＝１８８となる。その後、再割り当て構成に関連付けられたこのコストを、２１２である初期構成のコストと比較することができる。ここからわかるように、再割り当て構成に関連付けられたコストは、初期構成に関連付けられたコストよりも少ないため、実施用に選択される。より最適な（たとえばコストの少ない）物理処理ノード割り当て構成が存在するかどうかを判別するために、後続の割り当てを実行することができる。
【００５１】
論理演算子への物理処理ノードの初期割り当ての例示的プロセス
図１０は、論理演算子への物理処理ノードの初期割り当ての例示的プロセスを示す。図１０の動作流れ図はステップ１００２から始まり、ステップ１００４へと直接進む。論理演算子アサイナ３２４は、ステップ１００４で、いずれかの論理演算子が特定の物理処理ノードによる処理を必要とするかどうかを判別する。この判別の結果が否定的である場合、制御はステップ１００８へと進む。この判別の結果が肯定的である場合、論理演算子アサイナ３２４は、ステップ１００６で、これらの論理演算子をそれらの必要な物理処理ノードにピンニングする。論理演算子アサイナ３２４は、ステップ１００８で、各論理演算子に関する入力および出力メッセージ・フロー量を決定する。その後論理演算子は、ステップ１０１０で、初期物理処理ノードに割り当てられる。その後論理演算子アサイナは、ステップ１０１２で、論理演算子への物理処理ノードの初期割り当てに関する総メッセージ・フロー・コストを決定する。その後、制御フローは図１１の入口ポイントＡへと続く。
【００５２】
論理演算子への物理処理ノードの再割り当ての例示的プロセス
図１１は、最適な割り当て構成を決定するための、論理演算子への物理処理ノードの再割り当ての例示的プロセスを示す。動作流れ図は、入口ポイントＡから始まり、ステップ１１０２へと直接進む。論理演算子アサイナ３２４は、ステップ１１０２で、各論理演算子に関する入力および出力メッセージ・フロー量を分析する。論理演算子アサイナ３２４は、ステップ１１０４で、各論理演算子について、入力メッセージ・フロー量の合計が出力メッセージ・フロー量の合計よりも多いかまたはこれに等しいかどうかを判別する。この判別の結果が否定的である場合、論理演算子アサイナ３２４は、ステップ１１０６で、所与のメッセージ・フロー・シーケンスに関するメッセージ・バス３２４上の、現在論理演算子に割り当てられている物理処理ノードよりも後続のある位置に位置する物理処理ノードに、論理演算子を割り当てる。その後、制御はステップ１１１０に進む。
【００５３】
この判別の結果が肯定的である場合、論理演算子アサイナ３２４は、ステップ１１０８で、（所与のメッセージ・フロー・シーケンスに関する）メッセージ・バス上の、現在論理演算子に割り当てられている物理処理ノードの位置に先行する、ある位置に位置する物理処理ノードに、論理演算子を割り当てる。論理演算子アサイナ３２４は、ステップ１１１０で、論理演算子への物理処理ノードの再割り当てに関連付けられた総メッセージ・フロー・コストを決定する。
【００５４】
その後論理演算子アサイナ３２４は、ステップ１１１２で、後続の総メッセージ・フロー・コストが初期メッセージ・フロー・コストよりも少ないかどうかを判別する。この判別の結果が肯定的である場合、論理演算子アサイナ３２４は、ステップ１１１４で、後続の割り当てを選択する。その後、制御フローはステップ１１１６で終了する。この判別の結果が否定的である場合、論理演算子アサイナ３２４は、ステップ１１１８で、初期割り当てを選択する。その後、制御フローはステップ１１２０で終了する。一実施形態では、論理演算子が論理演算子を再割り当てする場合、候補となる物理処理ノードの使用可能リソースを考慮に入れる。たとえば、物理処理ノードの使用可能リソースが、論理演算子のコストよりも多いかまたはこれに等しいノードである場合、この物理処理ノードに論理演算子は割り当てられない。
【００５５】
子論理演算子の物理処理ノードへの親論理演算子の再割り当ての例示的プロセス
図１２は、子論理演算子のうちの１つの物理処理ノードへの親論理演算子の割り当ての例示的プロセスを示す。動作流れはステップ１２０２で開始され、ステップ１２０４へ直接進む。論理演算子アサイナ３２４は、ステップ１２０４で、親論理演算子が、現在子論理演算子に割り当てられている物理処理ノードの位置に先行する、メッセージ・バス上のある位置に位置する物理処理ノードに割り当てられるかどうかを判別する。この判別の結果が否定的である場合、制御フローはステップ１２０６で終了する。この判別の結果が肯定的である場合、論理演算子アサイナ３２４は、ステップ１２０８で、親論理演算子を、現在子論理演算子に割り当てられている物理処理オードに再割り当てする。
【００５６】
非限定的な例
本発明は、ハードウェア、ソフトウェア、またはハードウェアおよびソフトウェアの組み合わせで実現可能である。本発明の好ましい実施形態に従ったシステムは、１コンピュータ・システム内で集中的に、または、異なる要素がいくつかの相互接続されたコンピュータ・システムにまたがって散在する分散的に、実現可能である。任意の種類のコンピュータ・システム、または、本明細書で説明した方法を実施するように適合された他の装置が好適である。ハードウェアおよびソフトウェアの典型的な組み合わせは、ロードおよび実行された場合にコンピュータ・システムを制御し、その結果として本明細書で説明した方法を実施する、コンピュータ・プログラムを備えた、汎用コンピュータ・システムとすることができる。
【００５７】
一般に、本発明の諸実施形態を実施するために実行されるルーチンは、オペレーティング・システムまたは特定アプリケーションの一部、構成要素、プログラム、モジュール、オブジェクト、あるいは命令シーケンスの、いずれとして実施される場合でも、本明細書では「プログラム」と言い表される場合がある。コンピュータ・プログラムは、通常、ネイティブ・コンピュータによってマシン読み取り可能形式、したがって実行可能命令に変換されることになる、多数の命令からなる。またプログラムは、プログラムに対してローカルに常駐するか、またはメモリ内またはストレージ・デバイス上に見られる、変数およびデータ構造からなる。加えて、本明細書で説明する様々なプログラムは、本発明の特定実施形態で実施されるアプリケーションに基づいて識別することができる。しかしながら、後続のいかなる特定のプログラム命名法（nomenclature）も、単に便宜上使用されるものであるため、本発明は、こうした命名法によって識別あるいは示唆された、またはその両方の、任意の特定アプリケーションでのみ使用されるように限定されるべきではないことを理解されたい。
【００５８】
以上、本発明の特定の実施形態について開示してきたが、当業者であれば、本発明の範囲を逸脱することなく、特定の実施形態に対する変更が可能であることを理解されよう。したがって本発明の範囲は特定の実施形態に限定されるものではなく、添付の特許請求の範囲は、本発明の範囲内のこうした適用範囲、修正、および実施形態のうちのいずれかおよびすべてをカバーするものであることが意図される。
【図１】
2009545043.tif 000003
【図２】
2009545043.tif 000004
【図３】
2009545043.tif 000005
【図４】
2009545043.tif 000006
【図５】
2009545043.tif 000007
【図６】
2009545043.tif 000008
【図７】
2009545043.tif 000009
【図８】
2009545043.tif 000010
【図９】
2009545043.tif 000011
【図１０】
2009545043.tif 000012
【図１１】
2009545043.tif 000013
【図１２】
2009545043.tif 000014
【手続補正書】
【提出日】平成21年6月16日(2009.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
メッセージ・バス上のメッセージ・フローを削減するための、情報処理システムを伴う方法であって、
複数の論理演算子内の少なくとも１つの論理演算子が、物理ノード・グループ内の所与の物理処理ノードでの処理を必要とするかどうかを判別するステップと、
前記論理演算子が前記所与の物理処理ノードでの処理を必要とする旨の決定に応答して、前記論理演算子が前記所与の物理処理ノードにピンニングするステップと、
前記複数の論理演算子内の各論理演算子を、メッセージ・バス上にある前記物理処理ノード・グループ内の初期の物理処理ノードに割り当てるステップと、
を含み、前記割り当てるステップは、
前記複数の論理演算子内の少なくとも１つの論理演算子について、前記論理演算子に関連付けられた入力メッセージ・フロー量セットの合計が、前記論理演算子に関連付けられた出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの少なくとも１つであるかどうかを判別するステップと、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに先行する所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てるステップと、
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも少ないことに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードに対して、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある後続位置に位置する、後続の処理ノードに割り当てるステップと、
を含む、方法。
【請求項２】
前記メッセージ・フロー量が、
統計と、
観察と、
仮定と、
のうちの少なくとも１つに基づいて決定される、請求項１に記載の方法。
【請求項３】
前記複数の論理演算子内の各論理演算子をそれぞれの初期の物理処理ノードに割り当てるステップに関連付けられた、総メッセージ・フロー・コストを決定するステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記メッセージ・フロー・コストが、前記初期の物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量の合計を含む、請求項３に記載の方法。
【請求項５】
前記入力メッセージ・フロー量セットの合計が、前記出力メッセージ・フロー量セットの合計よりも多い、およびこれに等しい、のうちの１つであることに応答して、割り当てる前記ステップが、
前記物理処理ノードが、前記論理演算子のリソース要件を満たすために使用可能なリソースを備えるかどうかを判別するステップと、
前記物理処理ノードが使用可能なリソースを備えることに応答して、前記論理演算子を、前記論理演算子が現在関連付けられている前記物理処理ノードの前記メッセージ・バス上の位置に位置する前記物理処理ノードに割り当てるステップと、
をさらに含む、請求項１に記載の方法。
【請求項６】
前記複数の論理演算子内の少なくとも１つの論理演算子が、少なくとも１つの他の論理演算子の親であるかどうかを判別するステップと、
前記論理演算子が親であることに応答して、前記論理演算子が、前記論理演算子の子論理演算子が割り当てられる前記物理処理ノードに先行する、前記所与のメッセージ・フロー・シーケンスに関する前記メッセージ・バス上のある位置に位置する、先行する物理処理ノードに割り当てられるかどうかを判別するステップと、
前記論理演算子が前記先行する物理処理ノード上にあることに応答して、前記論理演算子を、前記子論理演算子が割り当てられている前記物理処理ノードに再割り当てするステップと、
をさらに含む、請求項１に記載の方法。
【請求項７】
前記複数の論理演算子を各物理処理ノードに割り当てるステップに関連付けられた総メッセージ・フロー・コストを決定するステップをさらに含む、請求項１に記載の方法。
【請求項８】
前記メッセージ・フロー・コストが、物理処理ノードにメッセージを伝送する各論理演算子に関連付けられたメッセージ・フロー量の合計を含む、請求項１に記載の方法。
【請求項９】
前記先行する物理処理ノードおよび前記後続の物理処理ノードのうちの１つに前記論理演算子のそれぞれを割り当てるステップに関連付けられた、後続のメッセージ・フロー・コストが、前記論理演算子のそれぞれを初期物理処理ノードに割り当てるステップに関連付けられた初期メッセージ・フロー・コストよりも少ないかどうかを判別するステップと、
前記後続のメッセージ・フロー・コストが前記初期メッセージ・フロー・コストよりも少ないことに応答して、前記後続のメッセージ・フロー・コストに関連付けられた前記論理演算子の前記割り当てを選択するステップと、
をさらに含む、請求項１に記載の方法。
【請求項１０】
前記請求項のいずれか一項に記載の方法のすべてのステップを実施するように適合された手段を備えるシステム。
【請求項１１】
前記請求項のいずれか一項に記載の方法のすべてのステップをコンピュータに実行させるコンピュータ・プログラム。
【国際調査報告】
2009545043.tif 000015
2009545043.tif 000016
2009545043.tif 000017