(57)【要約】      （修正有）【課題】フローグラフに対する検索効率を向上させる。【解決手段】データベース装置は、情報処理システムにおいて行われた複数の処理と前記処理間の遷移とにおいて、遷移前の処理の属性に関する第１情報と、遷移後の処理の属性に関する第２情報と、遷移の属性に関する第３情報とを取得する情報取得部と、前記情報に基づき、第１情報が表す第１ノードと、第２情報が表す第２ノードと、第３情報が表す、第１及び第２ノード間を接続するエッジとを含む複数のデータ構造を、予め与えた複数のセグメントタイプに応じて、同じノード同士を１つのノードに統合し、複数のセグメントを構築するセグメント構築部と、複数のセグメントのそれぞれの時間の範囲を表すデータ期間を算出する期間算出部と、複数のセグメントを、期間算出部により算出された複数のデータ期間に関連づけて記憶する記憶部と、を備える。【選択図】図１
2016224856.tif 000002
【特許請求の範囲】
【請求項１】
情報処理システムにおいて行われた複数の処理と前記処理間の遷移とに関して、前記遷移前の前記処理の属性に関する第１情報と、前記遷移後の前記処理の属性に関する第２情報と、前記遷移の属性に関する第３情報とを含む複数のエッジ情報を取得する情報取得部と、
前記複数のエッジ情報に基づき、前記第１情報が表す第１ノードと、前記第２情報が表す第２ノードと、前記第３情報が表す、前記第１および第２ノード間を接続するエッジとを含む複数のデータ構造を、予め与えた複数のセグメントタイプのそれぞれに応じて、複数の前記データ構造に含まれる同じノード同士を１つのノードに統合することにより、結合し、複数のセグメントを構築するセグメント構築部と、
前記複数のセグメントのそれぞれの時間の範囲を表すデータ期間を、前記複数のセグメントに属する前記第１ノード、前記第２ノードおよび前記エッジに関連する前記第１情報、第２情報および前記第３情報の少なくとも１つに基づいて算出する期間算出部と、
前記複数のセグメントのそれぞれを、前記期間算出部により算出された複数の前記データ期間のそれぞれに関連づけて記憶する記憶部と
を備えたデータベース装置。
【請求項２】
前記期間算出部は、前記セグメントに属する前記第１ノード、前記第２ノードまたは前記エッジを、予め定められた基準に基づき複数のグループに分類し、前記分類した複数のグループのうちの１つである第１グループに属する前記第１ノード、前記第２ノードまたは前記エッジに関連する前記第１情報、前記第２情報または前記第３情報に含まれる時刻の情報のうち最も早い時刻と、前記分類した複数のグループのうちの１つである第２グループに属する前記第１ノード、前記第２ノードまたは前記エッジに関連する前記第１情報、前記第２情報および前記第３情報に含まれる時刻の情報のうち最も遅い時刻との間の期間を、前記データ期間とする
請求項１に記載のデータベース装置。
【請求項３】
前記期間算出部は、前記セグメントに属する前記第１ノード、前記第２ノードおよび前記エッジに関連する前記第１情報、前記第２情報および前記第３情報に含まれる複数の時刻に関する情報を、前記時刻に関する情報の時間軸に対する分布に基づき、複数のグループに分類し、前記複数のグループのそれぞれの時間の範囲を表す第２のデータ期間を、前記複数のグループそれぞれに属する前記第１ノード、前記２ノードおよび前記エッジに関連する前記第１情報、前記第２情報および前記第３情報の少なくとも１つに基づいて算出し、
前記記憶部は、前記セグメントを、算出された複数の前記第２のデータ期間に関連づけて記憶する
請求項１に記載のデータベース装置。
【請求項４】
前記複数の時刻に関する情報は、クラスタリングアルゴリズムに基づき、前記複数のグループに分類される
請求項３に記載のデータベース装置。
【請求項５】
前記第１ノードは、前記情報処理システムにて処理されたデータの流出元となるノードを表し、
前記第２ノードは、前記データの流出先となるノードを表し、
前記エッジは、前記第１ノードから前記第２ノードへのデータフローのイベントを表す
請求項１ないし４のいずれか一項に記載のデータベース装置。
【請求項６】
前記第１ノードおよび前記第２ノードは、前記情報処理システムにおける処理の実行を表し、
前記エッジは、前記第１ノードと前記第２ノードとの関係性を表す
請求項１ないし４のいずれか一項に記載のデータベース装置。
【請求項７】
請求項１ないし６のいずれか一項に記載のデータベース装置と、
検索要求を受け付ける検索クエリ受付部と、
前記検索要求に基づき、前記データベース装置に対する検索処理命令を生成する検索部と、
を備える検索装置。
【請求項８】
前記検索要求には、検索対象の期間の指定が含まれ、
前記データベース装置は、指定された前記検索対象の期間を完全に含む前記データ期間に関連づけて記憶された前記セグメントに関連する情報を抽出する
請求項７記載の検索装置。
【請求項９】
前記検索要求には、前記セグメントタイプの指定が含まれ、
前記データベース装置は、指定された前記セグメントタイプの前記セグメントに関連する情報を抽出する
請求項７記載の検索装置。
【請求項１０】
情報処理システムにおいて行われた複数の処理と前記処理間の遷移とに関して、前記遷移前の前記処理の属性に関する第１情報と、前記遷移後の前記処理の属性に関する第２情報と、前記遷移の属性に関する第３情報とを含む複数のエッジ情報を取得する情報取得ステップと、
前記複数のエッジ情報に基づき、前記第１情報が表す第１ノードと、前記第２情報が表す第２ノードと、前記第３情報が表す、前記第１および第２ノード間を接続するエッジとを含む複数のデータ構造を、予め与えた複数のセグメントタイプのそれぞれに応じて、複数の前記データ構造に含まれる同じノード同士を１つのノードに統合することにより、結合し、複数のセグメントを構築するセグメント構築ステップと
前記複数のセグメントのそれぞれの時間の範囲を表すデータ期間を、前記複数のセグメントに属する前記第１ノード、前記２ノードおよび前記エッジに関連する前記第１情報、第２情報および前記第３情報の少なくとも１つに基づいて算出する期間算出ステップと、
を備える部分グラフ構築方法。
【請求項１１】
請求項１０の部分グラフ構築方法に記載の各ステップと、
検索要求を受け付ける検索クエリ受付ステップと、
前記検索要求に基づき、検索処理命令を生成するステップと、
を備える検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、データベース装置、検索装置、部分グラフ構築方法、検索方法に関する。
【背景技術】
【０００２】
計算機システムの運用状態を把握するために、システムトレース技術が存在する。システムトレース技術とは、システムのデータフローのトレースを行い、データフローグラフを作成することにより、計算機システムの動作履歴を詳細に記録・分析する技術である。システムの異常時には、当該データフローグラフに基づき、異常の原因分析や異常箇所の特定を行うことにより、早期のシステム復旧を図ることができる。また、性能に問題のある箇所に対して、適切な性能改善施策を実施することにより、サービス品質の維持を図ることができる。
【０００３】
所定時刻における所望のデータの位置を検出するために、時刻を指定して検索を行う場合、検索実施時点までに記録したデータフローグラフ全域が検索範囲となる。そのため、システムが大規模化・複雑化し、グラフデータが大量にある場合には、当該検出処理に必要な計算機資源と計算時間も大量になり、迅速な状態の把握・分析が困難になる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００９−３７４９８号公報
【非特許文献】
【０００５】
【非特許文献１】Andrey Kan, Jeffrey Chan, James Bailey, and Christopher Leckie, “A query based approach for mining evolving graphs,” In Proceedings of the Eighth Australasian Data Mining Conference - Volume 101 (AusDM 09), Vol. 101. Australian Computer Society, Inc., Darlinghurst, Australia, (2009), p.139-150.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施形態は、フローグラフに対する検索効率を向上させる。
【課題を解決するための手段】
【０００７】
本発明の一態様としてのデータベース装置は、情報処理システムにおいて行われた複数の処理と前記処理間の遷移とに関して、前記遷移前の前記処理の属性に関する第１情報と、前記遷移後の前記処理の属性に関する第２情報と、前記遷移の属性に関する第３情報とを含む複数のエッジ情報を取得する情報取得部と、前記複数のエッジ情報に基づき、前記第１情報が表す第１ノードと、前記第２情報が表す第２ノードと、前記第３情報が表す、前記第１および第２ノード間を接続するエッジとを含む複数のデータ構造を、予め与えた複数のセグメントタイプのそれぞれに応じて、複数の前記データ構造に含まれる同じノード同士を１つのノードに統合することにより、結合し、複数のセグメントを構築するセグメント構築部と、前記複数のセグメントのそれぞれの時間の範囲を表すデータ期間を、前記複数のセグメントに属する前記第１ノード、前記第２ノードおよび前記エッジに関連する前記第１情報、第２情報および前記第３情報の少なくとも１つに基づいて算出する期間算出部と、前記複数のセグメントのそれぞれを、前記期間算出部により算出された複数の前記データ期間のそれぞれに関連づけて記憶する記憶部と、を備える。
【図面の簡単な説明】
【０００８】
【図１】第１の実施形態における検索装置の概略構成の一例を示すブロック図。
【図２】データフローグラフの一例を示す図。
【図３】グラフエッジのデータ構造の一例を示す図。
【図４】ノードデータの一例を示す図。
【図５】エッジデータの一例を示す図。
【図６】セグメントタイプの一例を示す図。
【図７】セグメントデータの一例を示す図。
【図８】セグメントタイプデータの一例を示す図。
【図９】データ期間計算の一例を示す図。
【図１０】データ期間の一例を示す図。
【図１１】フローグラフ更新処理の概略フローチャート。
【図１２】グラフエッジ追加処理のフローチャート。
【図１３】連結コンポーネントタイプのセグメント構築処理のフローチャート。
【図１４】パスタイプのセグメント構築処理のフローチャート。
【図１５】データ期間更新処理のフローチャート。
【図１６】検索処理のフローチャート。
【図１７】コントロールフローグラフの一例を示す図。
【図１８】グラフノードの一例を示す図。
【図１９】第２の実施形態におけるグラフエッジのデータ構造の一例を示す図。
【図２０】第２の実施形態におけるノードデータの一例を示す図。
【図２１】第２の実施形態におけるエッジデータの一例を示す図。
【図２２】本発明の一実施形態におけるハードウェア構成の一例を示すブロック図。
【発明を実施するための形態】
【０００９】
以下、図面を参照しながら、本発明の実施形態について説明する。
【００１０】
（第１の実施形態）
図１は、第１の実施形態に係る検索システムの概略構成の一例を示すブロック図である。第１の実施形態に係る検索システムは、監視対象１と、監視部２と、フローグラフＤＢ（データベース）装置３と、グラフ取得部４と、グラフ分析部５と、を有する。フローグラフＤＢ装置３は、受付部３０１と、グラフ情報追加部３０２と、ノード保存部３０３と、エッジ保存部３０４と、セグメント構築部３０５と、セグメント保存部３０６と、セグメントタイプ保存部３０７と、データ期間更新部３０８と、データ期間保存部３０９と、検索クエリ受付部３１０と、検索部３１１と、を備える。
【００１１】
第１の実施形態に係る検索システムは、情報処理システムである監視対象１における処理の流れを、フローグラフと呼ばれるグラフで表す。フローグラフにて表されるフローは、任意でよい。例えば、処理が行われたデータに関するフロー（データフロー）でも、処理そのものの流れに関するフロー（コントロールフロー）でもよい。第１の実施形態では、処理が行われたデータに関するフローとした場合を説明する。なお、情報処理システムを構成する情報処理装置は１つでも複数でもよい。
【００１２】
図２は、データフローグラフの一例を示す図である。フローグラフは、丸で示されたノード（節）と、線で示されたエッジ（枝）から構成される。
【００１３】
ノードは、ある時刻における監視対象１中のデータの位置を表す。データの位置とは、ある時刻において、当該データの処理を行っているホストまたはプロセスまたは両方を意味する。ノードは、データに関する情報を保持する。例えば、図２の右上に示すように、データの識別子（ＩＤ）、データが存在する計算機のホスト名、当該データを扱っているサービス名および処理名（プロセスＩＤ）、などの属性情報を保持する。
【００１４】
エッジは、ノードとノードを接続し、接続している一方のノードから他方のノードに、データが流れたというイベント（データフローイベント）を表す。エッジは、データが流れた時刻を属性情報として保持する。この属性情報を、エッジのタイムスタンプと称する。また、あるノードにおいて、データが入力される側のエッジを入力エッジと、データが出力される側のエッジを出力エッジと称する。
【００１５】
フローグラフは、データまたは処理の内容ごとに生成されてもよいし、１つのシステムに関する複数のデータまたは複数の処理をまとめて１つのフローグラフを生成してもよい。例えば、図２では、時刻１１：５３に左上段のエッジから始まるデータフローグラフと、時刻１１：５５に右中段のエッジから始まるデータフローグラフの２つの独立したデータフローグラフを含む。
【００１６】
データフローグラフを分析することで、監視対象１の動作に関する様々な知見を得ることができる。例えば、異常が発生した時刻を与え、当該時刻にデータを処理していると考えられるノードをデータフローグラフから抽出すれば、異常の原因箇所の絞込みや、異常の影響範囲の見積もりが可能になる。例えば、図２において、１２：０６に監視対象１の異常を検出した場合には、１２：０６時点でデータが処理されているノードである黒色のノードを検出する。
【００１７】
また、異常を多角的に分析するために、１つのノードを検出するのではなく、例えば、異常発生時にデータを処理していたホストの集合やサービスの集合などを検索してもよい。
【００１８】
データフローグラフから対象のノードを検出するには、全てのノードを走査することにより、入力エッジと出力エッジを判別し、当該両エッジのタイムスタンプを調べる必要がある。しかし、一般にデータフローグラフの全体は非常に大規模なデータであるため、ノードの全検索を行うことは、処理時間、検索処理に要する記憶容量等の観点から現実的ではない。ゆえに、第１の実施形態に係る検索システムでは、データフローグラフを１以上の部分グラフに分割し、当該部分グラフに対し検索を行う。以降、この部分グラフをセグメントと称する。
【００１９】
以下、各部について説明する。
【００２０】
監視部２は、監視対象１の処理を監視し、データの転送または変換などの処理が行われるたびに、当該処理に関するイベント情報を取得する。イベント情報は、監視対象１から監視部２に直接渡されてもよいし、監視部２が監視対象１のネットワークに流れるデータを監視したり、監視対象１が生成するログファイルを監視したりすることで、間接的に取得してもよい。
【００２１】
監視部２は、取得したイベント情報に基づき、グラフエッジを生成する。グラフエッジとは、データフローを形成する最小単位のデータである。グラフエッジのデータ構造は、始点ノード属性、終点ノード属性、エッジ属性の３種類の属性から構成される。グラフエッジは、フローグラフ上では、２つのノードと１つのエッジからなる構造で表される。
【００２２】
図３は、グラフエッジのデータ構造の一例を示す図である。始点ノードは、グラフエッジが表すデータフローの始点、つまりデータの流出元となるノードを意味し、終点ノードはデータフローの終点、つまりデータの流出先となるノードを意味する。始点ノード属性、終点ノード属性はそれぞれ、ホスト名、サービス名、プロセスＩＤ、データＩＤの属性を有し、これらの属性により、このグラフエッジに関するイベント情報を把握することができる。
【００２３】
エッジ属性は、タイムスタンプ、ソースファイル名、行番号の属性を有する。タイムスタンプは、このグラフエッジが表すデータフローイベントが発生した時刻を示す。ソースファイル名は、このデータフローを発生させたプログラムのソースファイル名である。行番号は、ソースファイルの中の行番号である。
【００２４】
なお、上記のグラフエッジに関する属性は、一例であり、図３の例に限られるものではない。含まれていない属性があってもよいし、その他の属性を含んでもよい。
【００２５】
監視部２により生成されたグラフエッジは、フローグラフＤＢ装置３に入力される。なお、ここでは、監視部２がグラフエッジを生成したが、フローグラフＤＢ装置３が生成してもよい。監視部２は、検知したデータに関する情報を全てフローグラフＤＢ装置３に入力し、フローグラフＤＢ装置３がフィルタリング等を行い、エッジデータを生成してもよい。
【００２６】
フローグラフＤＢ装置３は、監視対象１で処理されたデータのフローグラフに関するデータを格納する。また、フローグラフＤＢ装置３は、フローグラフの部分グラフであるセグメントを構築する。そして、構築したセグメントに対し、データ期間を付与する。データ期間は、セグメントが示す監視対象１で処理されたデータのフローの一部分において、そのデータが処理された期間を意味する。
【００２７】
グラフ取得部４は、フローグラフＤＢ装置３から分析対象の部分グラフを取得する。グラフ取得部４は、分析対象に対する検索クエリを生成し、フローグラフＤＢ装置３に送り、フローグラフＤＢ装置３は、グラフ取得部４から取得した検索クエリに基づき、部分グラフを検出し、グラフ取得部４に送る。
【００２８】
グラフ分析部５は、グラフ取得部４が取得した部分グラフを受け取り、分析を行う。この分析により、例えば異常発生時にデータを処理していた計算機ホストのリストや、異常発生時に処理されていたデータのリストなどを得ることができる。
【００２９】
以下、フローグラフＤＢ装置３の各部について説明する。
【００３０】
受付部３０１は、監視部２からグラフエッジを受け付ける。受け付けたグラフエッジはグラフ情報追加部３０２に渡される。
【００３１】
グラフ情報追加部３０２は、取得したグラフエッジをエッジ保存部３０４へ保存する。また、必要に応じて、グラフエッジの始点ノードと終点ノードの情報をノード保存部３０３へ保存する。
【００３２】
ノード保存部３０３は、フローグラフのノードに関するデータであるノードデータを保存する。図４は、ノード保存部３０３に格納されたノードデータの一例を示す図である。ノードＩＤは、ノードを一意に識別するＩＤを表す。ノードＩＤは、受付部３０１、グラフ情報追加部３０２、またはノード保存部３０３が付与してもよい。ホスト名、サービス名、プロセスＩＤ、データＩＤは、図３で示されたグラフエッジのノード属性と同様である。ノードＩＤはノード保存部３０３に対し一意であり、ノードＩＤと対応する各属性情報の組み合わせも、ノード保存部３０３に対し一意とする。図４の例では、ホスト名、サービス名、プロセスＩＤ、データＩＤの組み合わせで表示されているが、その他の属性情報を組み合わせてもよい。
【００３３】
エッジ保存部３０４は、フローグラフのエッジに関するデータであるエッジデータを保存する。図５は、エッジ保存部３０４に格納されたエッジデータの一例を示す図である。エッジＩＤは、エッジを一意に識別するＩＤを表す。エッジＩＤは、受付部３０１、グラフ情報追加部３０２、またはエッジ保存部３０４が付与してもよい。始点ノードＩＤ、終点ノードＩＤは、それぞれ当該エッジが接続する始点ノード、終点ノードを表し、ノード保存部３０３に保存されたノードＩＤと対応する。タイムスタンプ、ソースファイル名、行番号は、図３で示したグラフエッジのおけるエッジ属性と同様である。ここでは、始点ノードＩＤ、終点ノードＩＤ、タイムスタンプ、ソースファイル名、行番号の組み合わせで表示されているが、その他の属性情報を組み合わせてもよい。
【００３４】
セグメント構築部３０５は、エッジ保存部３０４およびノード保存部３０３に保存されたフローグラフのエッジデータおよびノードデータを参照し、セグメントを新規に構築または既存のセグメントを分離する。以降、セグメントの構築には、既存セグメントの分離を含むものとして記載する。セグメントは、予め定められた基準または方法に基づき生成され、１つのセグメントは、１以上のノードの集合として表される。
【００３５】
セグメント構築部３０５に構築されるセグメントは、構築する基準または方法によって、異なった構造となる。セグメント構築部３０５がセグメントを構築する基準または構築されたセグメントの種類を、ここでは「セグメントタイプ」と称する。図６は、セグメントタイプの一例を示す図である。セグメントタイプには、以下のようなものが考えられる。
【００３６】
１つのノードにより構成されているセグメントを、「ノード」タイプと称する。ノードタイプは、最も粒度が細かいセグメントである。
【００３７】
エッジを逆順あるいは正順に辿り、到達可能なノードの集合により構成されているセグメントを、「連結コンポーネント」タイプと称する。データグラフを図示した際に連結しているノード全てが一つのセグメントに属する。図６（Ａ）は、「連結コンポーネント」タイプの一例を示す図である。セグメントＡ１は、フローが分岐する連結コンポーネントタイプであり、セグメントＡ２は、フローが合流する連結コンポーネントタイプである。
【００３８】
「ホスト名」の属性が同一であるノードにより構成されているセグメントを、「ホスト」タイプと称する。
【００３９】
「ソースファイル名」の属性が同一であるエッジの始点ノード及び終点ノードにより構成されているセグメントを、「ファイル」タイプと称する。このタイプでは、１つのノードが複数のセグメントに含まれる可能性がある。
【００４０】
入力エッジがないノードから出力エッジを正順に辿り、出力エッジのないノードに至るまでの一本道の経路上に存在するノードにより構成されるセグメントを「パス」タイプと称する。このタイプでは、１つのノードが複数のセグメントに含まれる可能性がある。図６（Ｂ）は、「パス」タイプの一例を示す図である。図６（Ａ）で示されたセグメントＡ１は、途中のノードで２つのフローに分岐されているため、パスタイプで分類すると、セグメントＢ１とセグメントＢ２の２種類に分類される。また、図６（Ａ）で示されたセグメントＡ２も、合流前は２つのフローなため、パスタイプで分類すると、セグメントＢ３とセグメントＢ４の２種類に分類される。なお、「パス」タイプのセグメントは、パスの始点ノードと終点ノードが必ず存在しなければならないため、循環構造が含まれないデータグラフをセグメント構築の対象とする。
【００４１】
セグメント構築部３０５によるセグメント構築方法は、対象とするセグメントタイプごとに異なる。以下、新しいグラフエッジが一つ追加された際のセグメント構築部３０５の動作をセグメントタイプごとに示す。
【００４２】
セグメントがノードタイプの場合は、追加されたグラフエッジの始点ノードおよび終点ノードそれぞれについて、セグメント保存部３０６にそのノードＩＤがまだ存在しない場合は追加し、セグメントタイプ保存部３０７にノードタイプのセグメントとして登録する。
【００４３】
セグメントが連結コンポーネントタイプの場合は、始点ノードと終点ノードがともにフローグラフに存在しない場合は、新規セグメントを登録する。始点ノードと終点ノードのどちらかがフローグラフに存在する場合は、片方のノードが所属するセグメントに新規ノードを登録する。始点ノードと終点ノードがともにフローグラフに存在する既存のノードであり、かつ両ノードが異なる連結コンポーネントに属している場合は、二つの連結コンポーネントを接続し、一つの大きな連結コンポーネントとする。このセグメント併合の方法は、任意に定めて良い。始点ノードの所属するセグメントを終点ノードの所属するセグメントに併合してもよいし、セグメントＩＤの大小や、セグメントに含まれるノード数に基づき、併合される側と併合する側を定めてもよい。
【００４４】
セグメントがホストタイプの場合は、追加されたグラフエッジの始点ノードおよび終点ノードそれぞれに対し、当該ノードと同じホスト名の属性を持つノードを、ノード保存部３０３から検索する。検出した場合は、当該始点ノードまたは終点ノードを検出したノードが所属するセグメントに追加する。検出されない場合は、当該始点ノードまたは終点ノード１つからなる新規セグメントを生成し、登録する。
【００４５】
セグメントがファイルタイプの場合は、追加されたグラフエッジと同じソースファイル名の属性を持つエッジを、エッジ保存部３０４から検索する。検出した場合は、検出したエッジと接続されている始点ノードまたは終点ノードの所属するセグメントに、当該グラフエッジの始点ノードおよび終点ノードを追加する。エッジが検出されなかった場合は、当該グラフエッジの始点ノードおよび終点ノードからなる新規セグメントを生成する。
【００４６】
セグメントがパスタイプの場合は、グラフエッジを追加することで影響を受けるセグメントに対し、再構築の処理を行う。再構築の処理とは、例えば、影響を受けるセグメントにおける既存のパスを一旦全て削除し、改めて構築しなおしたパスで置き換えるといった方法がある。また、既存のパスセグメントへの影響が小さい場合は、グラフエッジを追加する処理を行った上で、エッジを追加されたパスセグメントが複数のパスを保有するかを確認し、分岐がある場合には、複数のパスセグメントに分離してもよい。再構築の処理により、新規グラフエッジがセグメントの如何なるノードに追加されても、パスセグメントとしての整合性を維持するように調整する。
【００４７】
なお、上記のセグメント構築の方法は、一例であり、任意でよい。例えば、追加ごとにセグメントの更新を行わずに、定刻に全セグメントの再構築などを行ってもよい。
【００４８】
セグメント構築部３０５は、１つのフローグラフから、予め定められた１つまたは複数のセグメントタイプのセグメントを構築してもよいし、生成することができる全てのセグメントタイプのセグメントを構築してもよい。例えば、図６の例では、１つのデータグラフから、連結コンポーネントタイプであるセグメントＡ１およびＡ２と、パスタイプであるセグメントＢ１からＢ４との合計６つのセグメントを作成してもよい。
【００４９】
また、セグメント構築部３０５は、既存のセグメントから、異なるセグメントタイプのセグメントを構築してもよい。例えば、図６（Ａ）の連結コンポーネントタイプであるセグメントＡ１およびＡ２が既に作成されている場合に、図示しない入力部からの指示を、受付部３０１などを介して受け取り、セグメントＡ１およびＡ２から、図６（Ｂ）に示すセグメントＢ１からＢ４を構築してもよい。
【００５０】
また、セグメント構築部３０５が構築するセグメントタイプを判断してもよい。例えば、エッジ保存部３０４およびノード保存部３０３に新たに追加されたデータの属性と予め定められた判断基準に基づき、当該処理は１つのホストで完結すると判断すれば、ホストタイプのセグメントを生成する。複数のホストによる複数の処理に関わるデータと判断すれば、連結コンポーネントタイプを生成するといった判断をしてもよい。
【００５１】
セグメント保存部３０６は、各セグメントに関する情報であるセグメントデータを保存する。図７は、セグメント保存部３０６に保存されるセグメントデータの一例を示す図である。図７の例では、セグメントを一意に識別するためのセグメントＩＤが付与されており、各セグメントが保持するノードＩＤが保存される。セグメントＩＤは、セグメント構築部３０５またはセグメント保存部３０６が付与してもよい。１つのセグメントに複数のノードが含まれるため、図７の例では、セグメントＩＤが同一である行が、当該セグメントＩＤのセグメントに含まれるノードの数だけ存在する。
【００５２】
なお、図７は一例であり、他の情報を含んでもよい。例えば、ノードＩＤだけでなく、エッジＩＤを含めてもよい。また、ノードＩＤに対応する情報、例えば、ノード保存部３０３が保持する情報を含めてもよい。また、データ構造も異なっていてもよい。例えば、セグメントＩＤを主キーとし、保有するノードを列ごとに格納してもよい。また、図７の例では、全てのセグメントを１つのテーブルに格納するが、セグメントをセグメントタイプごとに分けたテーブルを複数保持してもよい。当該テーブルは、同じ構造ではなく、セグメントタイプごとに異なっていてもよい。
【００５３】
セグメントタイプ保存部３０７は、セグメント種別情報を含む属性情報を保存する。図８は、セグメント保存部３０６に保存される、セグメントタイプに関するセグメントタイプデータの一例を示す図である。図８に示すように、１つのセグメントＩＤと、１つのセグメントタイプとが対応付けられる。
【００５４】
データ期間更新部３０８は、セグメント構築部３０５が構築した各セグメントにおけるデータ期間を算出する。データ期間は、そのセグメントに含まれる複数のエッジが保持する時刻に関する情報（タイムスタンプ）から算出される。なお、本実施形態では、エッジ属性にタイムスタンプがあるため、エッジから算出するとしているが、ノードがタイムスタンプを保持する場合は、ノードから算出してもよい。また、ノードおよびエッジの両方がタイムスタンプを保持する場合は、一方または両方から算出してもよい。
【００５５】
図９は、データ期間計算の一例を示す図である。この例では、データ期間更新部３０８は、セグメント入力エッジのタイムスタンプと、セグメント出力エッジのタイムスタンプと、セグメント内部エッジのタイムスタンプとの３種類のグループのタイプスタンプを用いる。セグメント入力エッジとは、始点ノードがセグメント外のノード、終点ノードがセグメント内のノードであるエッジを意味する。セグメント出力エッジは、始点ノードがセグメント内のノード、終点ノードがセグメント外のノードであるエッジを意味する。セグメント内部エッジは、始点ノードおよび終点ノードがセグメント内のノードであるエッジを意味する。ノードタイプのセグメントなどでは、セグメント入力エッジおよびセグメント出力エッジが複数となる場合もある。これらのエッジの集合は、セグメント保存部３０６のセグメントの情報に基づき、エッジ保存部３０４またはセグメント保存部３０６などから抽出すればよい。
【００５６】
データ期間の計算法は、任意でよい。例えば、図９（Ａ）のように、セグメント入力エッジのタイムスタンプの最も早い時刻をデータ期間開始時刻とし、セグメント出力エッジのタイムスタンプの最も遅い時刻をデータ期間終了時刻としてもよい。あるいは、特定のグループのみに注目し、例えばセグメント内部エッジのタイムスタンプの最も早い時刻をデータ期間開始時刻、最も遅い時刻をデータ期間終了時刻としてもよい。あるいは、上記３種類のタイムスタンプの種別によらずに、セグメントに含まれる全てのエッジのタイムスタンプのうち、最も早い時刻と、最も遅い時刻との間をデータ期間としてもよい。また、データ期間開始時刻は、そのグループの最も早い時刻でなくてもよい。グループのタイムスタンプの平均値でもよいし、３番目に早い時刻など、任意に決めてよい。同様に、データ期間終了時刻は、そのグループの最も遅い時刻でなくてもよい。
【００５７】
データ期間更新部３０８は、１つのセグメントに対して複数のデータ期間を算出してもよい。つまり、１つのセグメントが複数のデータ期間を保持してもよい。図９（Ｂ）は、複数のデータ期間を計算する一例を示す図である。この例では、当該セグメントに付随するタイムスタンプは、時間軸に対し、３つのまとまり（グループ）に分かれて分布している。データ期間更新部３０８は、これらのまとまり（グループ）ごとにデータ期間を計算する。
【００５８】
例えば、監視対象１のあるデータに対し、１０時にデータの上書き保存処理、１０時５分に読み出し処理が行われ、１１時に再度データの上書き保存処理が行われ、１１時５分に再度読み出し処理が行われた場合における連結コンポーネントタイプのセグメントを考える。この場合、データの場所が同じなため、１０時と１１時に行われたデータの保存処理は１つのノードで表されるときもある。そのため、これらの処理は、１つのセグメントで表される。しかし、当該セグメントのデータ期間を１０時から１１時５分とすると、実際にはデータが処理されていない時間帯、例えば１０時３０分から１０時３５分、に対する検索処理においても、当該セグメントが抽出されることとなり、非効率である。そこで、当該セグメントは、１０時から１０時５分のデータ期間１と、１１時から１１時５分のデータ期間２の２つのデータ期間を保持させることとする。この場合、１０時３０分から１０時３５分に対する検索処理においては、当該セグメントは抽出されず、検索の効率が向上する。
【００５９】
複数のデータ期間を算出するには、図９（Ｂ）のようなデータのまとまりを、複数のグループに分類（クラスタリング）する。クラスタリングは、最短距離法、Ｋ−ｍｅａｎｓ法など一般的なクラスタリングアルゴリズムに基づき、コンピュータなどに機械的に処理させることで行うことができる。
【００６０】
データ期間更新部３０８は、ノード数やエッジ数などのセグメントの情報やセグメントタイプなどに基づき、セグメントごとに、データ期間の計算法を変更してもよい。例えば、ノードタイプのセグメントは、セグメント内部エッジを持たないので、セグメント入力エッジとセグメント出力エッジに基づき、データ期間を計算することになる。一方、連結コンポーネントタイプのセグメントは、逆にセグメント内部エッジしか持たないため、内部エッジのタイムスタンプのみに基づき、データ期間を計算する。
【００６１】
また、セグメントによっては有限のデータ期間を計算できない場合もある。例えば、エッジを１つしか持たないノードタイプセグメントでは、データ期間計算に使えるタイムスタンプは１つしかない。このような場合は、データ期間を「なし」としてもよい。または、データ期間開始時刻と終了時刻をともに当該タイムスタンプ、つまり同時刻としてもよい。あるいは、データ期間開始時刻を当該タイムスタンプとし、データ期間終了時刻を「∞」としてもよい。逆に、データ期間終了時刻を当該タイムスタンプとし、データ期間開始時刻を「−∞」としてもよい。その他、データ期間計算の結果、データ期間開始時刻がデータ期間終了時刻よりも遅くなる場合も、データ期間を「なし」としてもよい。
【００６２】
データ期間保存部３０９は、データ期間更新部３０８により算出された、セグメントに付随するデータ期間の情報を格納する。図１０は、データ期間保存部３０９が格納するデータ期間の一例を示す図である。セグメントＩＤと、データ期間更新部３０８が算出した開始時刻および終了時刻が、対応付けられている。図１０の例では、開始時刻および終了時刻のみが格納されているが、その他の属性を加えてもよい。また、１つのセグメントＩＤに対し、複数のデータ期間を対応付けてもよい。また、１つテーブルに全てのセグメントが含まれているが、セグメントタイプごとに、テーブルを分けてもよい。検索処理において、セグメントタイプとデータ期間が指定された場合に、当該セグメントタイプのみが格納されたテーブルを検索することで、検索効率を上げることができる。
【００６３】
検索クエリ受付部３１０は、グラフ取得部４から発行される検索クエリを受け付ける。当該検索クエリは、検出するセグメントのデータ期間を指定することができ、対象となるセグメントを減らすことができる。また、検索対象のセグメントタイプを指定してもよいし、論理積、論理和などにより、複数の条件を組み合わせてもよい。
【００６４】
また、検索クエリ受付部３１０は、当該検索クエリにより検出されたデータを、検索部３１１から受け取り、グラフ取得部４に送る。
【００６５】
検索部３１１は、検索クエリ受付部３１０から取得した検索クエリに基づき、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９を検索し、所望のセグメントを検出する。
【００６６】
検索部３１１の具体的な処理について説明する。セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９が、ＳＱＬクエリを受付可能なデータベースのテーブルとして実現されている場合、検索部３１１は、受け付けた検索クエリを、ＳＱＬクエリに変換する。ＳＱＬクエリの一例は、次のようになる。
ＳＥＬＥＣＴ  ｓ．セグメントＩＤ，  ｓ．ノードＩＤ
ＦＲＯＭ  セグメント保存部３０６  ＡＳ  ｓ，
セグメントタイプ保存部３０７  ＡＳ  ｔ，
データ期間保存部３０９  ＡＳ  ｄ
ＷＨＥＲＥ  ｓ．セグメントＩＤ  ＝  ｔ．セグメントＩＤ
ＡＮＤ  ｓ．セグメントＩＤ  ＝  ｄ．セグメントＩＤ
ＡＮＤ  （検索条件）
上記ＳＱＬクエリの「（検索条件）」は、検索クエリ受付部３１０が受け付けた検索条件を、予め定められた条件式に基づき変換されたものが入力される。上記SQL文中の「AS」は、ASの前の語句を、asの後ろの文字でネーミングすることを意味する。上記の場合、セグメント保存部３０６を「ｓ」、セグメントタイプ保存部３０７を「ｔ」、データ期間保存部３０９を「ｄ」とする。よって、１行目は、「ｓ」であるセグメント保存部３０６にあるセグメントIDと、ノードIDを抽出することを意味する。「where」は、whereの後ろにある語句が抽出条件であることを表す。「ｓ」であるセグメント保存部３０６にあるセグメントIDが、「ｔ」であるデータ期間保存部３０９のセグメントIDと一致し、かつ「ｄ」であるデータ期間保存部３０９のセグメントIDとも一致し、かつ（検索条件）を満たすセグメント保存部３０６にあるセグメントIDが抽出されることを表す。
【００６７】
検索条件は、検索するセグメントタイプ、検索を行う期間などでもよい。検索期間は、開始時刻または終了時刻のみを指定してもよい。なお、データ期間保存部３０９に保存されたデータ期間の開始時刻と終了時刻はそれぞれ「−∞」、「∞」となる可能性があるが、検索期間に含めてもよいし、含めなくてもよい。例えば、入力クエリがセグメントタイプを指定する場合、「（検索条件）」は下記のようになる。
t.セグメントタイプ = type
また、入力クエリがデータ期間を指定する場合は、「（検索条件）」は下記のようになる。
(d.開始時刻 IS NULL AND d.終了時刻 IS NULL) OR (d.開始時刻 IS NULL AND time < d.終了時刻) OR (d.終了時刻 IS NULL AND time >= d.開始時刻) OR (time >= d.開始時刻 AND time < d.終了時刻)
上記SQL文中の「NULL」は、開始時刻または終了時刻が、「−∞」または「∞」であることを意味する。
【００６８】
なお、上記は一例であり、検索される各格納部が、検索部３１１の指示を受け付け、結果を返すことができればよい。また、上記の例のＳＱＬクエリでは、検索部３１１はセグメントＩＤとノードＩＤのみを取得しているが、さらにノード保存部３０３やエッジ保存部３０４も検索対象として、各ノードに付随する属性やエッジ、およびエッジの属性を取得するものとしてもよい。また、各セグメントのセグメントタイプや、セグメントに所属するノードの数などを取得してもよい。
【００６９】
検索部３１１は、上記のような変換規則に基づき、入力クエリを受付可能なクエリに変換し、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９にクエリを発行する。
【００７０】
セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９は、検索条件であるデータ期間、またはセグメントタイプなどのその他の検索条件などに基づき、検索結果を返し、検索部３１１は、所望のセグメントのノードＩＤのリストを得る。検索部３１１は、取得したセグメントに関する各種データを、検索クエリ受付部３１０に送る。
【００７１】
次に、第１の実施形態に係る検索装置の処理のフローについて説明する。第１の実施形態では、監視部２からの監視情報に基づきフローグラフを更新するフローグラフ更新処理と、グラフ取得部４からの検索クエリに基づき、検索結果を返す検索処理に係るフローがある。
【００７２】
図１１は、フローグラフ更新処理の概略フローチャートである。当該フローは、監視対象１から属性情報が送られてきたタイミングまたは、監視部２が監視すべきイベント等を検知したタイミングで開始される。
【００７３】
監視部２は、監視対象１から監視対象１のデータフローイベントを取得する（Ｓ１０１）。監視部２は、取得したデータフローイベントからグラフエッジを生成する（Ｓ１０２）。監視部２は生成したグラフエッジをフローグラフＤＢ装置３に送り、エッジ受付部３０１がグラフエッジを受け付ける（Ｓ１０３）。
【００７４】
エッジ受付部３０１は、受け付けたグラフエッジをグラフ情報追加部３０２に送り、グラフ情報追加部３０２は、グラフエッジ追加処理を行う（Ｓ１０４）。グラフエッジ追加処理終了後、セグメント構築部３０５は、セグメント構築処理を行う（Ｓ１０５）。セグメント構築処理終了後、データ期間更新部３０８は、データ期間更新処理を行う（Ｓ１０６）。以上が、フローグラフ更新処理の概略フローチャートとなる。
【００７５】
上記各部の処理は、その前の処理が終了後に、処理完了の情報または次の処理の入力データを受け取り、処理を開始することを想定しているが、任意のタイミングで動作するようにしてもよい。先の処理が複数回実行された後、または入力データが予め定めた基準数を超えたときに、次の処理を開始してもよい。例えば、セグメント構築部３０５は、追加されたグラフエッジをバッファリングし、グラフエッジの数が予め定めた基準数を超えたときに、まとめて処理を行うとしてもよい。
【００７６】
あるいは、前の処理とは完全に非同期に動作してもよい。例えば、所定の時刻などで定期的に処理が行われてもよいし、図示しない入力部からの指示を、受付部３０１などを介して、受け取った時点で処理が行われてもよい。また、セグメントタイプなどの種別によって、動作タイミングを変えてもよい。
【００７７】
また、セグメントタイプごとに処理のタイミングや方法を変更してもよい。例えば、セグメント構築処理においては、比較的セグメント構築が容易なノードタイプ、ホストタイプ、ファイルタイプなどはグラフエッジが追加される度に、連結コンポーネントタイプはグラフエッジが１００個追加されたときに、セグメントの再構築が必要であるパスタイプは定刻に、セグメント構築を行うとしてもよい。
【００７８】
以下、各部のフローについて説明する。
【００７９】
図１２は、グラフ情報追加部３０２によるグラフエッジ追加処理のフローチャートを示す図である。グラフ情報追加部３０２が１つのグラフエッジを追加する際の動作を示す。グラフ情報追加部３０２は、追加されたグラフエッジの始点ノードが既にノード保存部３０３に存在するかどうかを調べる（Ｓ２０１）。グラフエッジ中の４つのノード属性（ホスト名、サービス名、プロセスＩＤ、データＩＤ）が全て一致するエントリがノード保存部３０３に存在しない場合（Ｓ２０１のＮＯ）、グラフエッジのノード情報を、新しいエントリとしてノード保存部３０３に保存する（Ｓ２０２）。新しいエントリとしてノード保存部３０３に保存した後、または始点ノードがノード保存部３０３に存在する場合（Ｓ２０１のＹＥＳ）、グラフ情報追加部３０２は、ノード保存部３０３から始点ノードのノードＩＤを取得する（Ｓ２０３）。
【００８０】
次に、グラフエッジの終点ノードが既にノード保存部３０３に存在するかどうかを調べる（Ｓ２０４）。グラフエッジの終点ノードがノード保存部３０３に存在しない場合（Ｓ２０４のＮＯ）、グラフエッジのノード情報を、新しいエントリとしてノード保存部３０３に保存する（Ｓ２０５）。新しいエントリとしてノード保存部３０３に保存した後、または終点ノードがノード保存部３０３に存在する場合（Ｓ２０４のＹＥＳ）、グラフ情報追加部３０２は、ノード保存部３０３から終点ノードのノードＩＤを取得する（Ｓ２０６）。
【００８１】
グラフ情報追加部３０２は、グラフエッジに含まれるエッジ属性をエッジ保存部３０４の新しいエントリとして保存する（Ｓ２０７）。以上が、グラフエッジ追加処理のフローである。
【００８２】
図１３は、セグメント構築部３０５による連結コンポーネントタイプのセグメント構築処理のフローチャートである。このフローチャートでは、連結コンポーネントタイプのセグメントが構築される。連結コンポーネントタイプでは、追加されたグラフエッジの始点ノードおよび終点ノードが新しいノードか既存のノードか、既存のノードであれば両ノードが同一のセグメントに所属しているか否かでセグメント構築の方法が異なる。
【００８３】
セグメント構築部３０５は、追加されたグラフエッジの始点ノードおよび終点ノードが既にノード保存部３０３に存在するかどうかを調べる（Ｓ３０１）。
【００８４】
始点ノードおよび終点ノードの両方がノード保存部３０３に存在する場合（Ｓ３０１−１）、始点ノードおよび終点ノードが同じ連結コンポーネントに所属するかを調べる（Ｓ３０２）。同じ連結コンポーネントに所属しない場合（Ｓ３０２のＮＯ）は、セグメント保存部３０６に対し、始点ノードの所属するセグメントのセグメントＩＤを、終点ノードの所属するセグメントのセグメントＩＤで更新し（Ｓ３０３）、処理を終了する。この場合、追加されたグラフエッジで２つの連結コンポーネントが接続され、１つの大きな連結コンポーネントとなる。同じ連結コンポーネントに所属する場合（Ｓ３０２のＹＥＳ）は、セグメント構築部３０５は何も行わずに処理を終了する（Ｓ３０４）。
【００８５】
始点ノードおよび終点ノードのいずれか一方がノード保存部３０３に存在する場合（Ｓ３０１−２）は、新規ノードを既存ノードの所属するセグメントのセグメントＩＤで、セグメント保存部３０６に登録し（Ｓ３０４）、処理を終了する。
【００８６】
始点ノードおよび終点ノードの両方がノード保存部３０３に存在しない場合（Ｓ３０１−３）は、始点ノードと終点ノードからなる新規セグメントをセグメント保存部３０６に登録し（Ｓ３０６）、処理を終了する。以上が、連結コンポーネントタイプのセグメントを構築するフローとなる。
【００８７】
図１４は、パスタイプのセグメント構築処理のフローチャートである。このフローチャートでは、パスタイプのセグメントが構築される。
【００８８】
セグメント構築部３０５は、エッジ保存部を参照し、新たに追加されたエッジの始点ノードからエッジを正順に辿り、辿り着いた出力エッジのないノードを、「終端ノード集合」に含める（Ｓ４０１）。また、その追加されたエッジの終点ノードからエッジを逆順に辿り、辿り着いた入力エッジのないノードを、「始端ノード集合」に含める（Ｓ４０２）。そして、「始端ノード集合」に含まれる各始端ノードと、「終端ノード集合」に含まれる各終端ノードとの全ての組み合わせに対し、始端ノードから終端ノードを一本道に結ぶことができるパスを全て算出する（Ｓ４０３）。パスを求める方法は、公知の探索アルゴリズムを用いればよい。
【００８９】
セグメント構築部３０５は、算出した全てのパスに１つでも含まれるノードを含むパスタイプセグメントを、既存のパスタイプセグメントから削除する（Ｓ４０４）。そして、算出したパスそれぞれを新規セグメントとして、登録する（Ｓ４０５）。以上が、パスタイプのセグメントを構築するフローとなる。
【００９０】
図１５は、データ期間更新部３０８のデータ期間更新処理のフローチャートを示す図である。当該フローは、１つのセグメントに対する処理のフローチャートである。データ期間更新部３０８は、セグメント構築部３０５により更新された全セグメントに対し、データ期間更新処理を行うため、当該フローを対象セグメント全てに対し、繰り返し行う。
【００９１】
データ期間更新部３０８は、セグメント構築部３０５により更新されたセグメントに含まれるエッジを算出する（Ｓ５０１）。具体的には、セグメント保存部３０６から更新されたセグメントに含まれるノードを抽出し、当該ノードに接続されるエッジをエッジ保存部から取得する。更新されたセグメントの判別は、セグメント構築部３０５またはセグメント保存部３０６から、更新されたセグメントのセグメントＩＤなどの情報を取得すればよい。または、データ期間を更新する対象のセグメントを判別するためのフラグを、セグメント保存部３０６が格納するテーブルの１フィールドとして保存し、データ期間更新部３０８に参照させてもよい。
【００９２】
なお、セグメント構築部３０５が、セグメントに含まれるエッジを算出し、セグメント保存部３０６などに格納している場合は、格納された情報を参照してもよい。
【００９３】
データ期間更新部３０８は、エッジ保存部３０４の情報に基づき、算出したエッジから、セグメント入力エッジ、セグメント出力エッジ、セグメント内部エッジを求める（Ｓ５０２）。
【００９４】
データ期間更新部３０８は、予め定められた条件に基づき、データ期間開始時刻と、データ期間終了時刻を算出し、データ期間を算出する（Ｓ５０３）。条件は、前述のとおり、セグメント入力エッジのタイムスタンプの最も早い時刻をデータ期間開始時刻とし、セグメント出力エッジのタイムスタンプの最も遅い時刻をデータ期間終了時刻とする、といったものでよい。以上が、データ期間更新処理のフローとなる。
【００９５】
図１６は、検索処理のフローチャートである。検索クエリ受付部３１０は、グラフ取得部４から入力クエリを取得する（Ｓ６０１）。検索部３１１は、検索クエリ受付部３１０から入力クエリを取得し、セグメント保存部３０６、セグメントタイプ保存部３０７、およびデータ期間保存部３０９が受け付けることができるクエリに変換する（Ｓ６０２）。検索部３１１は、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９に対し検索クエリを発行し、検索クエリにマッチするノードのリストなどの検索結果を取得する（Ｓ６０３）。検索部３１１は、検索結果を検索クエリ受付部３１０に送り（Ｓ６０４）、グラフ取得部４は、検索クエリ受付部３１０を介して、検索結果を取得する。以上が、検索処理のフローとなる。
【００９６】
以上のように、第１の実施形態によれば、ノードとエッジの情報に基づくセグメントの構築、およびエッジのタイムスタンプに基づくデータ期間の算出を行うことで、セグメントのデータ期間に対して、検索を行うことができる。これにより、特定の時刻および時間範囲において、データ処理中のノードおよびノードの集合を、効率よく検索することができる。また、様々な種別のセグメントを構築することにより、様々な単位（粒度）のセグメントに対し、柔軟に検索することが可能となる。また、セグメントタイプを指定することで、ホスト単位やサービス単位など、様々な単位に対する検索を行うことができる。また、一本道のグラフ構造ではなく、分岐や集約を含む構造であるデータフローグラフでも検索を行うことができる。
【００９７】
（第２の実施形態）
次に、第２の実施形態について説明する。第１の実施形態と重複する説明は省略する。
【００９８】
第１の実施形態では、エッジデータがタイムスタンプを保持し、当該タイムスタンプに基づき、セグメントのデータ期間が算出された。一方、本発明はエッジではなく、ノードがタイムスタンプを保持するフローグラフに対しても、適用が可能である。そこで、本実施形態では、ノードがタイムスタンプを保持するフローグラフの一例として、コントロールフローグラフに対する処理を説明する。
【００９９】
図１７は、コントロールフローグラフの一例を示す図である。第１実施形態で説明したデータフローグラフは、監視対象１内で処理されるデータの流れを示すものである。一方、コントロールフローグラフは、監視対象１内で実行される処理の流れ（コントロールフロー）を示すものである。コントロールフローグラフにおけるノードは、ある処理のイベントを表し、エッジはイベント間の関係性を表す。
【０１００】
図１７の例では、ｔｈｅｎ、ｒ＿ｃａｌｌ、およびｒ＿ｒｅｔｕｒｎの３種類のエッジが記録されている。ｔｈｅｎエッジは、各ノードに対応する各イベントが、１つのスレッド内で、順番に発生したことを示す。プロセスやスレッドは、コンピュータのＣＰＵで実行される処理の単位を表す。１つのプロセスには、１つまたは複数のスレッドが含まれる。つまり、ｔｈｅｎエッジで接続されたノードは、同じスレッドによって実行されたことを示す。ｒ＿ｃａｌｌエッジは、ｒ＿ｃａｌｌエッジと接続される始点ノードがＲＰＣ（Ｒｅｍｏｔｅ  Ｐｒｏｃｅｄｕｒｅ  Ｃａｌｌ）のリクエスト発行イベントであることを示し、ｒ＿ｃａｌｌエッジと接続される終点ノードがＲＰＣのリクエストの受信イベントであることを示す。ｒ＿ｒｅｔｕｒｎエッジは、ｒ＿ｒｅｔｕｒｎエッジと接続される始点ノードがＲＰＣのレスポンス発行イベントであることを示し、終点ノードがそのレスポンスの受信イベントであることを示す。
【０１０１】
各ノードは、各ノードが表すイベントに関連する属性情報を保持する。例えば、イベントの発生時刻を示すタイムスタンプ、イベントの内容を表すログメッセージ、イベントが発生したホスト名、サービス名、プロセスＩＤ、スレッドＩＤ、ソースコードのファイル名、当該ファイルにおける行番号などの属性がある。
【０１０２】
このように、コントロールフローグラフは、イベントを表す各ノードが、イベント間の関係性を表すエッジにて接続されることにより、複数のホストを横断するような処理の流れを示すことができる。
【０１０３】
第２の実施形態の構成は、第１の実施形態と同じ構成を取ることができる。もしくは、第２の実施形態では、受付部３０１を、ノードに関する情報であるグラフノードを監視部２から受け付けるノード受付部と、グラフエッジを監視部２から受け付けるエッジ受付部に分けてもよい。同様に、グラフ情報追加部３０２を、グラフノードを追加するノード追加部と、グラフエッジを追加するエッジ追加部とに分けてもよい。以降、第２の実施形態の構成は、第１の実施形態と同じ構成として、説明する。
【０１０４】
監視部２は、監視対象１で発生するコントロールフローに関するイベントを監視し、検知したグラフノードを、フローグラフＤＢ装置３に入力する。図１８は、グラフノードの一例を示す図である。図１８の例では、グラフノードは、ノードＩＤと、ノードが意味するイベントが発生した時刻を示すタイムスタンプなどの属性からなる。これらの属性は、コントロールフローグラフにて、各ノードが保持する属性情報となる。ノードＩＤは、ノードを一意に識別するための識別子であるが、ノード保存部３０３に格納される際に、ノード保存部３０３が振り直してもよい。また、ノード保存部３０３ではなく、受付部３０１、グラフ情報追加部３０２が付与してもよい。この場合、受付部３０１は付与されたノードIDを監視部２へ伝達する。
【０１０５】
監視部２は、グラフノードに加えて、グラフエッジをフローグラフＤＢ装置３に入力してもよい。図１９は、第２の実施形態におけるグラフエッジのデータ構造の一例を示す図である。グラフエッジは、始点ノードＩＤ、終点ノードＩＤ、関係性の３つの属性を持つ。関係性は、始点ノードと終点ノードが表すイベント間の関係性である。監視部２は、グラフエッジを、グラフノードと同時に入力してもよいし、グラフノードとは無関係に、独立したタイミングで入力してもよい。
【０１０６】
第２の実施形態でのフローグラフＤＢ装置３の内部の各部については、第1実施形態での処理と異なる処理が行われるグラフ情報追加部、エッジ保存部、およびデータ期間更新部各部について説明する。
【０１０７】
グラフ情報追加部３０２は、取得した情報がグラフノードかグラフエッジかを確認する。グラフノードを取得した場合は、ノード保存部３０３を参照し、グラフノードの情報がないときは、ノード保存部３０３に追加する。当該追加は、ノードＩＤを比較してもよいし、保存時にノードＩＤを振り直す場合は、タイムスタンプや属性情報を比較してもよい。図２０は、ノード保存部３０３に格納される第２の実施形態におけるノードデータの一例を示す図である。第１の実施形態と異なり、タイムスタンプがノードデータに含まれる。
【０１０８】
グラフエッジを取得した場合は、エッジ保存部３０４を参照し、グラフエッジの情報がないときは、エッジ保存部３０４に追加する。図２１は、エッジ保存部３０４に格納される第２の実施形態におけるエッジデータの一例を示す図である。エッジデータには、エッジＩＤと、図１９で示したグラフエッジの属性が含まれる。第１の実施形態と異なり、タイムスタンプはエッジデータに含まれない。エッジＩＤは、受付部３０１、グラフ情報追加部３０２、またはエッジ保存部３０４が付与してもよい。
【０１０９】
データ期間更新部３０８は、第１の実施形態と同様、セグメント構築部３０５が構築した各セグメントにおけるデータ期間を計算する。しかし、第２実施形態では、エッジデータにタイプスタンプが含まれないため、第２実施形態におけるデータ期間更新部３０８は、エッジデータに代えて、ノードデータに基づき、データ期間を算出する。
【０１１０】
データ期間更新部３０８は、第１の実施形態にて用いたセグメント入力エッジ、セグメント出力エッジ、セグメント内部エッジの３種類のエッジに代わり、セグメント入力ノード、セグメント出力ノード、セグメント内部ノードの３種類のノードを用いる。セグメント入力ノードとは、データ期間の算出の対象セグメントに含まれないノードであり、かつ当該セグメント内のノードへ入力するエッジを有するノードを意味する。セグメント出力ノードとは、データ期間の算出の対象セグメントに含まれないノードであり、かつ当該セグメント内のノードから出力されるエッジを有するノードを意味する。セグメント内部ノードとは、データ期間の算出の対象セグメントに含まれるノードである。
【０１１１】
データ期間更新部３０８は、ノードデータおよびエッジデータに基づき、セグメント入力ノード、セグメント出力ノード、セグメント内部ノードを求める。具体例としては、セグメント保存部３０６を参照し、データ期間の算出の対象セグメントに所属する全ノードを、セグメント内部ノードとする。そして、エッジ保存部３０４を参照し、エッジごとに、始点ノードおよび終点ノードがセグメント内部ノードであるかを確認する。始点ノードがセグメント内部ノードであり、終点ノードが対象セグメントに含まれていない場合は、終点ノードをセグメント出力ノードとする。始点ノードが対象セグメントに含まれておらず、終点ノードがセグメント内部ノードである場合は、始点ノードをセグメント入力ノードとすればよい。
【０１１２】
セグメント入力ノード、セグメント出力ノード、セグメント内部ノードを求めた後のデータ期間更新部３０８のデータ期間の計算は、第１の実施形態のときの３種類のエッジのタイムスタンプの代わりに、３種類のノードのタイムスタンプを用いて、同様に計算すればよい。その他の処理は、第１の実施形態と同様である。
【０１１３】
以上のように、第２の実施形態によれば、ノードのみがタイムスタンプを持つコントロールフローグラフから、特定の時刻において実施されていた処理を、様々なグラフ粒度で効率よく検出することが可能となる。
【０１１４】
（第３の実施形態）
第１の実施形態は、エッジデータのみがタイムスタンプを有するデータフローグラフを用い、第２の実施形態は、ノードデータのみがタイムスタンプを有するコントロールフローグラフを用いたが、エッジデータとノードデータの両方がタイムスタンプを有するフローグラフを用いる第３の実施形態も可能である。
【０１１５】
第３の実施形態は、第１およびの第２の実施形態と構成は同じであるが、ノード保存部３０３のノードデータおよびエッジ保存部３０４のエッジデータは、データフローグラフの属性とコントロールフローグラフの両方の属性を格納することが異なる。
【０１１６】
また、データ期間更新部３０８は、セグメント入力エッジ、セグメント出力エッジ、セグメント内部エッジ、セグメント入力ノード、セグメント出力ノード、セグメント内部ノードの６種類のタイムスタンプを用いて、データ期間を計算することができる。データ期間更新部３０８は、セグメントタイプ等に基づき、データ期間の算出に用いるタイムスタンプの種類を決定すればよい。
【０１１７】
上記に説明した実施形態における各処理は、ソフトウェア（プログラム）によって実現することが可能である。よって、上記に説明した実施形態における検索装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用い、コンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することが可能である。
【０１１８】
図２２は、本発明の一実施形態におけるハードウェア構成の一例を示すブロック図である。検索装置は、プロセッサ６０１、主記憶装置６０２、補助記憶装置６０３、ネットワークインタフェース６０４、デバイスインタフェース６０５、入力装置６０６、出力装置６０７を備え、これらがバス６０８を介して接続された、コンピュータ装置として実現できる。
【０１１９】
プロセッサ６０１が、補助記憶装置６０３からプログラムを読み出して、主記憶装置６０２に展開して、実行することで、受付部３０１、グラフ情報追加部３０２、セグメント構築部３０５、データ期間更新部３０８、検索クエリ受付部３１０、検索部３１１の機能を実現することができる。
【０１２０】
本実施形態の検索装置は、当該検索装置で実行されるプログラムをコンピュータ装置に予めインストールすることで実現してもよいし、プログラムをＣＤ−ＲＯＭなどの記憶媒体に記憶して、あるいはネットワークを介して配布して、コンピュータ装置に適宜インストールすることで実現してもよい。
【０１２１】
ネットワークインタフェース６０４は、通信ネットワークに接続するためのインタフェースである。監視部２、グラフ取得部４などと通信にて接続される場合は、このネットワークインタフェース６０４にて実現してもよい。ここではネットワークインタフェースを１つのみ示しているが、複数のネットワークインタフェースが搭載されていてもよい。
【０１２２】
デバイスインタフェース６０５は、外部記憶媒体７などの機器に接続するインタフェースである。外部記憶媒体７は、ＨＤＤ、ＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＳＡＮ（Ｓｔｏｒａｇｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）等の任意の記録媒体でよい。エッジ保存部３０４、ノード保存部３０３、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９は、外部記憶媒体７としてデバイスインタフェース６０５に接続されてもよい。
【０１２３】
また、エッジ保存部３０４、ノード保存部３０３、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９は、データベースや、データベースのテーブルとして実現してもよい。
【０１２４】
主記憶装置６０２は、プロセッサ６０１が実行する命令、および各種データ等を一時的に記憶するメモリ装置であり、ＤＲＡＭ等の揮発性メモリでも、ＭＲＡＭ等の不揮発性メモリでもよい。補助記憶装置６０３は、プログラムやデータ等を永続的に記憶する記憶装置であり、例えば、ＨＤＤまたはＳＳＤ等がある。エッジ保存部３０４、ノード保存部３０３、セグメント保存部３０６、セグメントタイプ保存部３０７、データ期間保存部３０９などが保持するデータは、主記憶装置６０２、補助記憶装置６０３または外部記憶媒体に保存される。
【０１２５】
上記に、本発明の一実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１２６】
１  監視対象
２  監視部
３  フローグラフＤＢ装置
３０１  受付部
３０２  グラフ情報追加部
３０３  エッジ保存部
３０４  ノード保存部
３０５  セグメント構築部
３０６  セグメント保存部
３０７  セグメントタイプ保存部
３０８  データ期間更新部
３０９  データ期間保存部
３１０  検索クエリ受付部
３１１  検索部
４  グラフ取得部
５  グラフ分析部
６０１  プロセッサ
６０２  主記憶装置
６０３  補助記憶装置
６０４  デバイスインタフェース
６０５  ネットワークインタフェース
６０６  バス
７  外部記憶媒体
【図１】
2016224856.tif 000003
【図３】
2016224856.tif 000004
【図４】
2016224856.tif 000005
【図５】
2016224856.tif 000006
【図６】
2016224856.tif 000007
【図７】
2016224856.tif 000008
【図８】
2016224856.tif 000009
【図９】
2016224856.tif 000010
【図１０】
2016224856.tif 000011
【図１１】
2016224856.tif 000012
【図１２】
2016224856.tif 000013
【図１３】
2016224856.tif 000014
【図１４】
2016224856.tif 000015
【図１５】
2016224856.tif 000016
【図１６】
2016224856.tif 000017
【図１７】
2016224856.tif 000018
【図１８】
2016224856.tif 000019
【図１９】
2016224856.tif 000020
【図２０】
2016224856.tif 000021
【図２１】
2016224856.tif 000022
【図２２】
2016224856.tif 000023
【図２】
2016224856.tif 000024