(57)【要約】【課題】【解決手段】グラフベースの計算は、構成要素間のデータフローを表す１つ又は複数のリンクによって接続されたグラフ構成要素を表す複数のノードを有する。計算を作成することは、計算において複数のトランザクションを処理するために、構成要素の少なくとも第１のセットを識別することと、第１のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第２のグループに関連付けることとを含む。少なくとも第１及び第２のトランザクションを処理するために計算を実行することは、第１のグループの最終データ記録に対応するデータ操作の構成要素の第１のセットによる実行後まで、第２のグループの初期データ記録に対応するデータ操作の構成要素の第１のセットによる実行を遅延させることを含む。【選択図】  図１
2013506199.tif 000002
【特許請求の範囲】
【請求項１】
グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続された前記グラフ構成要素を表す複数のノードを有するグラフベースの計算を作成することであって、
前記計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別すること、及び
第１のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第２のグループに関連付けること、
を含む、作成することと、
前記第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行後まで、前記第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行を遅延させることを含む、少なくとも前記第１及び第２のトランザクションを処理するために前記グラフベースの計算を実行することと、
を含む、コンピュータによる実現方法。
【請求項２】
前記グラフベースの計算を実行することが、
前記第１及び第２のトランザクションに対応する前記データ記録及びデータ操作を処理すること、及び
障害が検出された時点で、前記処理されたトランザクションに対応するすべての処理されたデータ記録及びデータ操作をロールバックすることによって、トランザクションの第１のバッチをロールバックすること、
によって、前記第１及び第２のトランザクションを前記トランザクションの第１のバッチとして実行すること、
をさらに含む、請求項１に記載の方法。
【請求項３】
少なくとも出力ポートを有する第１のグラフ構成要素を、前記グラフ構成要素の第１のセットに関するデータフローの開始として指定すること、及び、
少なくとも入力ポートを有する第２のグラフ構成要素を、前記グラフ構成要素の第１のセットに関するデータフローの終了として指定すること、
をさらに含む、請求項１に記載の方法。
【請求項４】
前記１つ又は複数のトランザクションを処理するために、前記グラフ構成要素の第１のセットを動的に呼び出すことをさらに含む、請求項１に記載の方法。
【請求項５】
前記トランザクションの第１のバッチにおいてほぼすべてのトランザクションを正常に処理した時点で、前記トランザクションの第１のバッチをコミットすることをさらに含む、請求項１に記載の方法。
【請求項６】
前記トランザクションの第１のバッチをコミットすることが、前記トランザクションの第１のバッチにおける前記トランザクションのそれぞれに対応するすべての前記データ操作を、ほぼ同時にコミットすることを含む、請求項５に記載の方法。
【請求項７】
前記障害を検出することが、前記トランザクションの第１のバッチのトランザクションにおける前記データ記録のそれぞれに対応する前記データ操作のうちのいずれかの障害を検出することを含む、請求項２に記載の方法。
【請求項８】
前記障害の検出後、前記トランザクションの第１のバッチの未処理のトランザクションと、前記トランザクションの第１のバッチの処理中にコミットされなかった前記処理済みトランザクションとを、トランザクションの第２の異なるバッチとして再処理することをさらに含む、請求項２に記載の方法。
【請求項９】
前記障害の検出後、前記トランザクションの第１のバッチに関連付けられた前記処理済み及び未処理のトランザクションのそれぞれを、一連の離散バッチとして再処理することをさらに含む、請求項２に記載の方法。
【請求項１０】
前記障害の検出後、障害の発生した１つ又は複数のトランザクションを障害トランザクションとして識別すること、
前記障害トランザクションを除く前記トランザクションの第１のバッチを第２の異なるバッチとして再処理すること、及び、
前記障害トランザクションを第３のバッチとして再処理すること、
をさらに含む、請求項２に記載の方法。
【請求項１１】
前記第１のトランザクションの実行過程において、前記グラフベースの計算に属するグラフ構成要素のセットによって、第１のデータベース内の１つ又は複数のデータ操作を実行することをさらに含む、請求項２に記載の方法。
【請求項１２】
前記第１のトランザクションの実行過程において、前記第１のデータベースを用いて第１のセッションを確立することであって、前記第１のセッションは、前記第１のトランザクションを処理するグラフ構成要素の第１のセットのうちの１つ又は複数によって共有される、確立することをさらに含む、請求項１１に記載の方法。
【請求項１３】
前記第１のトランザクションのサイズがユーザによって指定される、請求項２に記載の方法。
【請求項１４】
コンピュータ・プログラムが、
グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続された前記グラフ構成要素を表す複数のノードを有するグラフベースの計算を作成することであって、
前記計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別すること、及び
第１のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第２のグループに関連付けること、
を含む、作成することと、
前記第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行後まで、前記第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行を遅延させることを含む、少なくとも前記第１及び第２のトランザクションを処理するために前記グラフベースの計算を実行することと、
を、コンピュータに実行させるための命令を含む、コンピュータ・プログラムを格納するコンピュータ読み取り可能媒体。
【請求項１５】
グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続された前記グラフ構成要素を表す複数のノードを有するグラフベースの計算を作成するための手段であって、
前記計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別すること、及び
第１のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及び前記データ記録に対応するデータ操作の第２のグループに関連付けること、
を含む、作成するための手段と、
前記第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行後まで、前記第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の前記第１のセットによる実行を遅延させることを含む、少なくとも前記第１及び第２のトランザクションを処理するために前記グラフベースの計算を実行するための手段と、
を含む、コンピュータ・システム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、それぞれが参照により本明細書に組み込まれた、２００９年９月２５日出願の米国特許出願第６１／２４５，８６２号、及び２００９年１２月１５日出願の米国特許出願第１２／６３８，５８８号に対する優先権を主張するものである。
【０００２】
本開示は、グラフベース・アプリケーションにおけるトランザクションの処理に関する。
【背景技術】
【０００３】
複雑な計算は、しばしば、計算の構成要素が、グラフの頂点と、グラフのリンク（弧、辺）に対応する構成要素間のデータフローとに関連付けられた、有向グラフを介したデータフローとして表すことができる。こうしたグラフベースの計算については、米国特許第５，９６６，０７２号「Executing Computations Expressed As Graphs」に記載されている。グラフベースの計算を実行するための１つの手法は、それぞれがグラフの異なる頂点に関連付けられたいくつかのプロセスを実行すること、及び、グラフのリンクに従ってプロセス間に通信経路を確立することである。たとえば、この通信経路は、ＴＣＰ／ＩＰ又はＵＮＩＸドメイン・ソケットを使用するか、又は、共有メモリを使用して、プロセス間でデータを渡すことができる。
【発明の概要】
【課題を解決するための手段】
【０００４】
一態様では、概略的に、コンピュータによる実現（computer-implemented）方法は、計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別することと、第１のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第２のグループに関連付けることとによって、グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続されたグラフ構成要素を表す複数のノードを有するグラフベースの計算を作成する（prepare）ことを含む。この方法は、第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の第１のセットによる実行後まで、第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の第１のセットによる実行を遅延させることを含む、少なくとも第１及び第２のトランザクションを処理するためにグラフベースの計算を実行することを含む。
【０００５】
本態様は、以下の特徴のうちの１つ又は複数を含むことができる。
【０００６】
グラフベースの計算の実行は、第１及び第２のトランザクションに対応するデータ記録及びデータ操作を処理すること、ならびに、障害が検出された時点で、処理されたトランザクションに対応するすべての処理されたデータ記録及びデータ操作をロールバック（rolling back）することによってトランザクションの第１のバッチをロールバックすること、によって、第１及び第２のトランザクションをトランザクションの第１のバッチとして実行することを、含むことができる。
【０００７】
方法は、少なくとも出力ポートを有する第１のグラフ構成要素を、グラフ構成要素の第１のセットに関するデータフローの開始として指定すること、及び、少なくとも入力ポートを有する第２のグラフ構成要素を、グラフ構成要素の第１のセットに関するデータフローの終了として指定することを、含むこともできる。
【０００８】
方法は、１つ又は複数のトランザクションを処理するために、グラフ構成要素の第１のセットを動的に呼び出すことを含むこともできる。
【０００９】
方法は、トランザクションの第１のバッチにおいてほぼすべてのトランザクションを正常に処理した時点で、トランザクションの第１のバッチをコミットすることを含むこともできる。トランザクションの第１のバッチをコミットすることは、トランザクションの第１のバッチにおけるトランザクションのそれぞれに対応するすべてのデータ操作を、ほぼ同時にコミットすることを含むことができる。
【００１０】
障害を検出することは、たとえば、トランザクションの第１のバッチのトランザクションにおけるデータ記録のそれぞれに対応するデータ操作のうちのいずれかの障害を検出することを含むことができる。
【００１１】
方法は、障害の検出後、トランザクションの第１のバッチの未処理のトランザクションと、トランザクションの第１のバッチの処理中にコミットされなかった処理済みトランザクションとを、トランザクションの第２の異なるバッチとして再処理することを含むこともできる。
【００１２】
方法は、障害の検出後、トランザクションの第１のバッチに関連付けられた処理済み及び未処理のトランザクションのそれぞれを、一連の離散バッチとして再処理することを含むこともできる。
【００１３】
方法は、障害の検出後、障害の発生した１つ又は複数のトランザクションを障害トランザクションとして識別すること、障害トランザクションを除くトランザクションの第１のバッチを第２の異なるバッチとして再処理すること、及び、障害トランザクションを第３のバッチとして再処理することを、含むこともできる。
【００１４】
方法は、第１のトランザクションの実行過程において、グラフベースの計算に属するグラフ構成要素のセットによって、第１のデータベース内の１つ又は複数のデータ操作を実行することを含むこともできる。方法は、第１のトランザクションの実行過程において、第１のデータベースを用いて第１のセッションを確立することを含むことも可能であり、この第１のセッションは、第１のトランザクションを処理するグラフ構成要素の第１のセットのうちの１つ又は複数によって共有される。
【００１５】
第１のトランザクションのサイズは、ユーザによって指定可能である。
【００１６】
他の態様では、概略的に、コンピュータ読み取り可能媒体は、計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別することと、第１のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第１のグループに関連付けることと、第２のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第２のグループに関連付けることとを含む、グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続されたグラフ構成要素を表す複数のノードを有するグラフベースの計算を作成すること、ならびに、第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の第２のセットによる実行後まで、第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の第１のセットによる実行を遅延させることを含む、少なくとも第１及び第２のトランザクションを処理するためにグラフベースの計算を実行することを、コンピュータに実行させるための命令を含む、コンピュータ・プログラムを格納する。
【００１７】
他の態様では、概略的に、コンピュータ・システムは、計算において複数のトランザクションを処理するために、グラフ構成要素の少なくとも第１のセットを識別することと、第１のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第１のグループに関連付けること、及び、第２のトランザクションを、１つ又は複数のデータ記録及びデータ記録に対応するデータ操作の第２のグループに関連付けることとを含む、グラフ構成要素間のデータフローを表す１つ又は複数のリンクによって接続されたグラフ構成要素を表す複数のノードを有するグラフベースの計算を作成するための手段、ならびに、第１のグループの最終データ記録に対応するデータ操作のグラフ構成要素の第２のセットによる実行後まで、第２のグループの初期データ記録に対応するデータ操作のグラフ構成要素の第１のセットによる実行を遅延させることを含む、少なくとも第１及び第２のトランザクションを処理するためにグラフベースの計算を実行するための手段を含む。
【００１８】
本発明の１つ又は複数の実施形態の詳細について、添付の図面及び以下の説明で述べる。本発明の他の特徴、目的、及び利点は、この説明及び図面、並びに特許請求の範囲から明らかとなろう。
【図面の簡単な説明】
【００１９】
【図１】グラフベース・システムを示すブロック図である。
【図２】トランザクション処理を示す例示的データフロー・グラフである。
【図３】トランザクション処理を示す例示的データフロー・グラフである。
【図４】トランザクション処理を示す例示的データフロー・グラフである。
【図５】トランザクション処理の例示的シナリオを示す図である。
【図６】データフロー・グラフの作成及びデータフロー・グラフにおけるトランザクションの実行の、例示的プロセスを示す流れ図である。
【発明を実施するための形態】
【００２０】
図１を参照すると、グラフベースの計算を実行するための計算システム１００は、データ・ストレージ１０２に結合された開発環境１０４と、データ・ストレージ１０２に結合されたランタイム環境１０６とを含む。開発者１０１は、開発環境１０４を使用してアプリケーションを構築する。アプリケーションは、開発者が開発環境１０４を使用した結果としてデータ・ストレージ１０２に書き込まれることが可能な、データ・ストレージ１０２内のデータ構造によって指定された１つ又は複数のデータフロー・グラフに関連付けられる。データ構造は、たとえばデータフロー・グラフの頂点（構成要素又はデータ・セットを表す）及び頂点間のリンク（データフローを表す）を指定する。データ構造は、構成要素、データ・セット、及びグラフのデータフローの、様々な特徴を含むこともできる。データ処理アプリケーションは、たとえば、処理構成要素のグラフを介して１つ又は複数の入力データ・セットから１つ又は複数の出力データ・セットへと流れるデータ上で実行される計算を実装する、データフロー・グラフに関連付けることができる。
【００２１】
ランタイム環境１０６は、ＵＮＩＸオペレーティング・システムなどの好適なオペレーティング・システムの制御の下で、１つ又は複数の汎用コンピュータ上でホスト可能である。たとえばランタイム環境１０６は、ローカル（たとえばＳＭＰコンピュータなどのマルチプロセッサ・システム）、又はローカル分散型（たとえばクラスタ又はＭＰＰとして結合された複数プロセッサ）、又はリモート分散型（たとえばＬＡＮ又はＷＡＮを介して結合された複数プロセッサ）、又はそれらの任意の組み合わせのいずれかの、複数の中央処理ユニット（ＣＰＵ）を使用するコンピュータ・システムの構成を含む、多重ノード並列計算環境を含むことができる。グラフ内で複数構成要素を同時に実行することによって、１つの形の並列処理が提供される。追加の並列処理は、グラフの異なる構成要素を異なる計算ノード（たとえば異なるＣＰＵ）に分散させることによって、達成可能である。並列処理をランタイム環境１０６に導入するために、グラフの要素（たとえばデータ・セット、構成要素、及びフロー）を明示的又は暗黙的に複製することができる。
【００２２】
ユーザ１０３は、たとえばコマンド行又はグラフィカル・インターフェースを使用して、ランタイム環境１０６と対話する（interact）ことができる。ランタイム環境１０６は、所与のデータフロー・グラフを指定する格納済みのグラフ・データ構造を読み出すため、及び、構成要素の計算を実行するためのプロセス（たとえば、ホスト・オペレーティング・システム内での実行のプロセス又はスレッド）などの計算リソースを割振り及び構成するための、事前実行モジュール１１０を含む。
【００２３】
ランタイム環境１０６はまた、事前実行モジュール１１０によってデータフロー・グラフに割り当てられるプロセスの実行をスケジューリング及び制御するための、実行モジュール１１２を含む。実行モジュール１１２は、データベース・エンジン、データ・ストレージ、又は、グラフ構成要素に関連付けられた処理中にアクセスされる他のモジュールなどの、システム１００に結合された外部計算リソースと対話することができる。
【００２４】
報告モジュール１１４は、データフロー・グラフの実行後、又は実行中所定の間隔で、
データフロー・グラフの個々の構成要素に関連付けられた統計などの、所与の計算を特徴付ける情報を提供する。報告モジュール１１４によって報告される情報の一部は、データフロー・グラフによって生成された出力から取得される。報告される情報の一部は、データフロー・グラフの実行を監視することによって取得される。
【００２５】
ランタイム監視モジュール（ＲＭＭ）１１６は、データフロー・グラフに割り当てられた１つ又は複数のプロセスの実行を監視し、情報を報告モジュール１１４に提供する。この情報は、たとえば、中央処理ユニット（ＣＰＵ）が各構成要素の実行に専念する時間、又は、各構成要素によって処理されるデータの量を含む。
【００２６】
図２を参照すると、例示的データフロー・グラフ２００は、データフロー・グラフ２００の構成要素２０４Ａ〜２０４Ｉ（全体として２０４）によって処理されることになる１つ又は複数の入力データ記録を有する入力データ・セット２０１を含む。いくつかの実装では、入力データ記録２０１は構成要素２０４の１つ又は複数の入力ポートに入り、出力データ記録（いくつかのケースでは、入力データ記録２０１、又は入力データ記録２０４の処理済みバージョン）は通常、構成要素２０４の１つ又は複数の出力ポートから出る。いくつかの実装では、単一の入力データ記録２０１の処理の結果、複数の出力データ記録を生じさせることができる。グラフ２００では、構成要素２０４Ｃ、２０４Ｉ、及び２５５からの出力データ記録は、出力データ・セット２０６Ａ〜２０６Ｃ（全体として２０６）に格納される。例示的データフロー・グラフ２００については、参照により本明細書に組み込まれた、２００６年５月１６日付出願の米国特許出願第１１／４３４，６２３号により詳細に記載されている。
【００２７】
アップストリーム構成要素（たとえば２０４Ａ）の出力からダウンストリーム構成要素（たとえば２０４Ｂ又は２４０）への記録の流れは、一般に、ダウンフロー・リンク２４５のいずれかを介して同時に発生可能である。これにより、データフロー・グラフ２００内の異なる構成要素２０４が異なる記録上で同時にタスクを実行することが可能であり、これによって、データフロー・グラフ２００によって実行中の計算全体に対してある形のパイプライン並列処理が提供される。言い換えれば、計算の所与の部分はアップストリーム構成要素２０４によって記録の所与のセット上で実行され、これと並列に、計算の異なる部分はダウンストリーム構成要素２０４によって記録の異なるセット上で実行される。
【００２８】
データフロー・グラフ２００は並列処理システム上で実行可能であり、ファイル操作動作（作成、削除、及び名前変更など）とデータ操作動作（読み取り及び書き込みなど）との組み合わせによって、データの複数の外部集合を変更することができる。こうしたデータの外部集合の１つがデータベース・システム２０９である。データフロー・グラフ２００の構成要素２０４は、データベース・システム２０９にアクセスするように構成される。この関連で、グラフ２００によって処理されるデータ記録は、データベース・システム２０９上で実行されることになる１つ又は複数のデータ操作に関連付けられる。
【００２９】
ある実装では、以下でより詳細に説明するように、構成要素２０４はトランザクション特性を提供するように構成可能である。たとえば図３を参照し、現金自動預け払い機（ＡＴＭ）での顧客のセッションから受け取った情報に基づく、銀行の顧客記録の更新に関する計算グラフ３００について考えてみる。この動作において、構成要素３１５は、ＡＴＭから情報を読み取り、データ記録３１２と、情報に基づいてデータベース・システム２０９内で実行されることになる関連付けられたデータ操作とを生成する。図に示されるように、構成要素「口座を妥当性検査」３０６ａ、「残高をチェック」３０６ｂ、及び「残高を更新」３０６ｃは、すべて同じデータベース・システム２０９にアクセスする。ＡＴＭに入力される顧客の個人識別番号（ＰＩＮ）に関する情報を担持する第１のデータ記録３１２ａは、「口座を妥当性検査」２０６ａによって処理される。顧客の口座からある金額が引き落とされることを示す情報を担持する第２のデータ記録３１２ｂは、「残高を更新」３０６ｃによって処理される。
【００３０】
第１のデータ記録３１２ａが第２のデータ記録３１２ｂとは独立に処理される場合、データベース２０９に対する独立したコミットによって、顧客の情報が妥当性検査される前にデータベースの口座の残高が更新される結果となる。したがって、データベース・システム２０９に含まれるデータは、所望の形ではなくなる。この状況に対処するために、単一の単位として一緒にコミットされるか又は障害が発生する（即ちロールバック（rolled back））必要のあるデータ記録３１２及び関連付けられた動作は、記録３１２及び記録３１２に対応する動作がすべて処理された後でのみ全体としてコミットされるトランザクションとして、グループ化される。同じトランザクションの一部として処理されるようにまとめてグループ化される記録３１２は、「作業単位」と呼ぶことができる。さらにオプションで、バッチ内のトランザクションがまとめてコミットされるか、又はバッチ全体がロールバックされるように、異なるトランザクションを、単位として処理されるトランザクションのバッチにまとめてグループ化することもできる。トランザクションのバッチのサイズ、すなわち、バッチ内のトランザクションの数は、ユーザが指定するか、又は事前実行モジュール１１０（図１）が自動的に決定することができる。さらに、構成要素３１５、３０６ａ〜ｄ、及び３１０は、以下で詳細に説明するように、トランザクション単位に対応するセットにまとめてグループ化される。したがってデータ記録３１２は、それぞれが独立した別個の単位としてデータベース２０９にコミットされる、個々のトランザクション又はトランザクションのバッチ内のトランザクション単位で処理される。
【００３１】
この例では、構成要素３０６ａ〜ｃは、それぞれ、データベース・システム２０９内のデータにアクセスするように、たとえばこのデータを受信、修正、及び／又は削除するように、構成される。一連のデータ記録３１２は、「読み取り」構成要素３１５によって入力として受信される。データ記録３１２及び関連付けられたデータ操作の処理によって、データベース・システム２０９が永続的に変更される場合、この変更は「コミットされた」と言われる。こうしたコミットされた変更は、コンピューティング・システム１００内のすべてのプロセスに対して可視である。この関連で、データ記録３１２及び関連付けられたデータ操作によって実行された変更をデータベース・システム２０９内で永続とするために、データ記録３１２及び関連付けられた動作に対応する各トランザクションに対してコミット動作が実施される。障害が発生した場合、データ記録３１２及び関連付けられたデータ操作を含む障害トランザクションは、単一の単位としてロールバック可能であり（すなわち、動作が実行される前のデータベース・システム２０９の以前の状態を復元することが可能であり）、データ記録３１２及び関連付けられた動作は廃棄するか又は障害の理由に対処した後で再処理することができる。障害は、様々な理由で発生可能である。たとえば障害は、たとえばメモリ割り振りにおけるエラー、又はメモリ・スペースへの書き込みにおける競合システムなどの、障害とすることができる。障害は、たとえば、ほぼ空の口座から資金を引き出そうとするなどの、基礎となるデータ操作における障害とすることもできる。こうしたシナリオでは、データ記録３１２及び関連付けられたデータ操作を含むトランザクションに障害が発生することになる。
【００３２】
一般に、データ記録３１２及び関連付けられたデータ操作を含むあらゆるトランザクションの処理後のコミットは、費用がかかる可能性がある。典型的なコミット動作では、データベース・システム２０９は、データ操作によってデータベース・システム２０９に対して実行されたあらゆる修正を、物理ディスク（たとえば、データベース・システム２０９に関連付けられたデータを格納するハード・ディスク）に書き込む。いくつかの例では、ログ・ファイル（図示せず）の更新も必要な場合があるため、コミット動作の実施に関与する処理サイクルの数がさらに増加する。したがって、コミット動作には、かなりのリソース及び処理サイクルが必要となる可能性がある。したがって、複数トランザクションのバッチに対するコミット動作のグループ化について本明細書で説明される例示的技法は、この費用の一部を軽減し、リソースを節約する。
【００３３】
前述のように、別々のトランザクションに関連付けられた作業単位でデータ記録の着信流れを処理することで、そうでなければそれらのトランザクションに関する動作を処理する構成要素のセット内に存在することになるパイプライン並列処理を抑制することによって、あるトランザクション特性（たとえば、以下でより詳細に説明される分離）を実行可能にする。再度図２を参照すると、トランザクションは、データフロー・グラフ２００全体によって定義される計算の一部によって実行可能である。たとえば、データベース・システム２０９と共に実施されるトランザクションは、データベース・システム２０９と通信する構成要素２０４Ｄ〜Ｇのみを含むことができる。これらのラインに沿って、ある実装では、構成要素２０４Ｄ〜Ｇを含むトランザクションを実施するためのセット２５０を定義することができる。このように、構成要素２０４Ｄ〜Ｇのセット２５０は、トランザクションに関与するデータ記録に関する動作をまとめて実行することができる。いくつかの例では、それぞれが異なるタイプのトランザクションを実施する、構成要素の複数のセット２５０が存在可能である。セット２５０は、様々な方法で確立することができる。たとえばセット２５０は、グラフが実行される前に確立可能である。いくつかの例では、セットはグラフの開始時に確立可能である。構成要素（図示せず）は、セットを動的に呼び出すためにユーザによって定義可能である。いくつかの実装では、データフロー・グラフ２００の実行時に、事前実行モジュール１１０（図１）が、トランザクションを処理するためのセット２５０の一部となる構成要素２０４を識別することができる。
【００３４】
ある実装では、所与のトランザクションに関するトランザクション処理の開始と終了の境界を定める１つ又は複数の特別な構成要素２４０、２５５の使用を通じて、セット２５０を確立することができる。いくつかの例では、構成要素２４０、２５５は、ユーザ（たとえば図１のユーザ１０３）に対してグラフ２００が展開される前に、設計者（たとえば図１の開発者１０１）によって指定可能である。いくつかの例では、構成要素２４０、２５５は、グラフ２００を修正するための機能を有するエンドユーザ１０３によって指定可能である。図に示されるように、たとえば少なくとも出力ポートを有する「トランザクションを開始」（ＢＴ）２４０などの第１の構成要素を、トランザクションに関するデータフロー２４５の開始として指定することが可能であり、たとえば少なくとも入力ポートを有する「トランザクションを終了」（ＥＴ）２５５などの第２の構成要素を、トランザクションに関するデータフロー２４５の終了として指定することが可能である。いくつかの実装では、トランザクションのデータ記録に関連付けられたトランザクションの動作を実行する構成要素２０４のセット２５０は、トランザクション単位（ＴＵ）と呼ばれる。処理中の単一のトランザクションに関するデータ記録のみがＴＵ内に流入できるように保証することによって、ＴＵ内のパイプライン並列処理は抑制される。ＴＵによって処理されることになる次のトランザクションに関するデータ記録は、前のトランザクションが（たとえばコミットされることによって）完了した後にＴＵ内に流入することができる。ＢＴ２４０及びＥＴ２５０は、この条件を強化するために通信可能である。データフロー・グラフ２００は複数のＴＵを有することができる。
【００３５】
いくつかの実装では、始動時にグラフ２００を分析して、セット２５０内の構成要素２０４を決定することができる。セット２５０内の構成要素２０４は、単一プロセスで実行可能である。この手法では、事前実行モジュール１１０（図１）はグラフ２００の構成要素２０４を、それぞれが１つ又は複数の構成要素２０４を含む１つ又は複数のセットに分割する。１つ又は複数の構成要素２０４を含む各セットに、異なるプロセスを割り当てることができる。したがって、同じセット内に配置された１つ又は複数の構成要素２０４の場合、それらの構成要素２０４によって表される計算を同じプロセス内で実行するように「まとめて折り畳む」ことができる。プロセス内の１つ又は複数の構成要素２０４は逐次実行される。このように、記録は、別のプロセス内にあった場合に実行可能な順序で、プロセス内の１つの構成要素２０４から次へと渡される。
【００３６】
所与のセット２５０内の構成要素２０４について、ＢＴ２４０及びＥＴ２５５は前述のように指定される。ＢＴ２４０への１つの入力、１つ又は複数のＥＴ２５５からのオプション出力、及びセット２５０内の構成要素からの他の出力が存在可能である。いくつかの実装では、ＢＴ２４０のアップストリームの構成要素（たとえば構成要素２０４Ａ）及びＥＴ２５５のダウンストリームの構成要素が存在可能である。
【００３７】
ある実装では、所与のトランザクションの処理に潜在的に関与可能な構成要素２０４は、「発見」プロセスを使用して、それらがセット２５０の一部であることをＢＴ２４０に示すことができる。たとえば、構成要素２０４Ｄ〜Ｇは、セット２５０の一部である。単一のプロセスに折り畳まれた各構成要素２０４は、トランザクションの始動時に呼び出される始動ルーチンを含むことができる。構成要素２０４Ｄ〜Ｇのそれぞれに、セット２５０の名前を指定するパラメータが割り当てられる。始動時に、構成要素２０４Ｄ〜Ｇはそれらをセット２５０に割り当てられた構成要素２０４として登録するため、結果としてＢＴ２４０は、所与のトランザクションの処理に関与する構成要素２０４Ｄ〜Ｇを知ることができる。
【００３８】
一例では、ＢＴ２４０がデータ記録２０１を受信すると新規のトランザクションが開始するが、他のトランザクションはアクティブではない。トランザクションの開始時に、ＢＴ２４０は、トランザクションの処理を開始するよう各構成要素２０４及びＥＴ２５５に指示する。トランザクションに関連付けられたデータ記録２０１は、構成要素２０４Ｄ〜Ｇの間でトランザクション内のデータフロー２４５の一部として渡される。トランザクション処理の最後に、ＥＴ２５５は、前述のようにトランザクションの結果をコミット又は停止することができる。
【００３９】
さらにいくつかの実装では、セット２５０内の１つ又は複数の構成要素２０４Ｄ〜Ｇは、データベース・システム２０９にアクセスするために接続を共有することができる。したがって、セット２５０内の構成要素２０４Ｄ〜Ｇを使用してトランザクションを実行する過程において、データベース・システム２０９を用いてセッションを確立し、セット２５０内の構成要素２０４Ｄ〜Ｇによってこれを共有することができる。このように、トランザクションのバッチ処理との関連において、データベース・システム２０９に関連するすべてのデータ記録及び関連付けられたデータ操作を同じデータベース・セッション内で処理することができる。
【００４０】
計算グラフのコンテキストにおける信頼性を向上させるために、データフロー・グラフ２００のＴＵは、「ＡＣＩＤ」特性を提供するトランザクションを実装するように構成され、すなわち、システム１００は、所与のトランザクションに関するデータ記録２０１及び関連付けられたデータ操作に関して、「原子性（atomicity）」、「一貫性」、「隔離」、及び「耐久性」を保証する。たとえばＴＵは、原子性特性を満たすために、単一のトランザクション内で実行されたデータベース・システム２０９への変更に関連付けられたすべての動作がまとめてコミットされるように、データベース・システム２０９と対話する。たとえば図３の例では、顧客の口座に対する更新は、顧客の情報が正常に妥当性検査された場合にのみ、正常に実行されることになる。同様に、口座間で資金を振り替えるアプリケーションの場合、原子性特性は、一方の口座からの引き落としが正常に実行された場合、他方の口座への対応する入金が正常に実行されることを保証する。このように、データベース・システム２０９内ですべての変更が実行されるか、又は一切の変更が実行されない。
【００４１】
原子性に加えて、システム１００は、トランザクションの開始時及び終了時に、データベース２０９内のデータが一貫した状態にあることを保証する。これは、データベース２０９が「一貫性」特性を満たすことを保証するものである。たとえば、口座間で資金を振り替えるアプリケーションにおいて、一貫性特性は、各トランザクションの開始時及び終了時に、両方の口座の合計資金額が同じであることを保証する。
【００４２】
さらにシステム１００は、トランザクションの中間状態が他のトランザクションには不可視であることを保証する。これは、システム１００が「分離」特性を満たすことを保証するものである。たとえば、口座間で資金を振り替えるアプリケーションにおいて、他のトランザクションは、一方の口座又は他方の口座において振り替えられた資金はわかるが、両方の口座におけるそれはわからない。
【００４３】
最後に、トランザクションが正常に完了した後、システム１００は、たとえシステム障害が発生しても、データへの変更は持続的であり失われないことを保証する。これは、システム１００が「耐久性」特性を満たすことを保証するものである。たとえば、口座間で資金を振り替えるアプリケーションにおいて、耐久性特性は、各口座に対して実行された変更が失われないことを保証する。
【００４４】
トランザクションの処理の間、諸技法を使用して障害に対処することができる。障害が発生した場合、データベース・システム２０９に対して部分的変更が実行されている可能性があるため、現行のアプリケーション又は他のアプリケーションは、データベース・システム２０９内のデータが訂正されるまでこれを使用することができない。通常これは、データベース・システム２０９内の記録が修正されているか、又は計算の過程で作成された場合に発生する。並列処理システムでは、データベース・システム２０９はしばしば多くの異なるコンピューティング・システム及びストレージ・ユニット（たとえば磁気ディスク）全体にわたるものであり、データの状態を「ロールバックする」作業の必要性がストレージ・ユニットの数に比例して高くなるため、問題が大きくなる。
【００４５】
こうした障害から回復するためには、現行の（すなわち障害が発生した）アプリケーションをシャットダウンした後、開始以降にアプリケーションによって実行されたすべての変更を取り消す（「完全ロールバック」）か、又はシステムの状態を中間の「チェックポイント」まで復元し、その地点から実行を再開する（「部分ロールバック」）ことが必要な可能性がある。
【００４６】
上記で提案したように、データフロー・グラフ２００の特徴は、データ記録２０１及びそれらの対応するデータ操作を複数のトランザクションに関連付けられることである。所与のトランザクションに関連付けられたデータ記録２０１及び対応するデータ操作は、単一の単位としてコミットする（すなわち永続的にする（made permanent））か、又はロールバックする（すなわち取り消す（undone））ことができる。
【００４７】
次に図４を参照すると、データフロー・グラフ４００は、グラフ構成要素４０６ａ〜ｄ（全体として４０６）及び４１０ａ〜ｃ（全体として４１０）を含む。図に示されるように、構成要素４０６のセット４０２は、トランザクションを処理するためのＴＵとして定義される。さらに構成要素４０６は、データベース・システム２０９と通信している。ある実装では、たとえば構成要素４１０などのある構成要素はセット４０２に含まれないため、セット４０２に関連付けられたトランザクションの処理には関与しない。
【００４８】
ある実装では、入力データ記録３１２は、トランザクション４１４ａ、４１４ｂ（全体として４１４）のバッチにまとめてグループ化され、そのそれぞれがＴＵ４０２内で処理されることになる「作業単位」内の異なる記録グループに対応する。データ記録３１２をトランザクション４１４に関する作業単位にグループ化することは、様々な方法で実行可能である。たとえば、ユーザ１０３は、各トランザクション４１４に関するトランザクション・サイズ（すなわちデータ記録３１２の数）を定義することができる。いくつかの例では、事前実行モジュール１１０（図１）は、たとえばデータ記録の所定の特徴に基づいて、データ記録を自動的にトランザクション４１４に分割することができる。たとえば、データ記録３１２が、たとえば「チェックアウト・キャッシュ・レジスタ」などからのライン品目記録のストリームである場合、各記録３１２は、たとえば「レジスタ番号」、「トランザクション番号」、「品目番号」、「品目コード」、及び「価格」などの、特徴を含むことができる。チェックアウト・レジスタで発生する各販売が単一のトランザクションとして評価される必要のある場合、すべての記録３１２は、「レジスタ番号」及び／又は「トランザクション番号」に基づいて、単一のトランザクション４１４にまとめてグループ化することができる。
【００４９】
ある例では、異なるトランザクション間を分離するために、セット４０２の構成要素４０６ａ〜ｄは、一度に１つのトランザクション、たとえばトランザクション４１４ａのみを処理する。したがって、最終の構成要素４０６ｄがトランザクション４１４ａの最終データ記録を処理した後にのみ、第１の構成要素４０６ａがトランザクション４１４ｂの第１のデータ記録を処理することができる。
【００５０】
いくつかの実装では、コミット動作は各トランザクション後には実行されず、むしろ遅延されて、トランザクションのバッチに対して一度に実行される。以下の例では、「バッチ」とは、複数のトランザクション及びそれらの対応する作業単位のバッチを言い表すものであり、それぞれがそれらのトランザクションで実行されることになる記録で構成される。次に図５を参照すると、例示的シナリオは、作業単位５１０ａ〜ｅのバッチ５０９を受信及び処理するためのＴＵ内の構成要素のセット５０２を含む、データフロー・グラフ５００の一部を示すものである。図に示されるように、セット５０２は、処理のための５つの入力作業単位５１０ａ〜ｅを有するバッチ５０９をキューに入れている。バッチ５０９の実行過程において、構成要素５０８ａ〜ｃは、データベース・システム２０９との共通セッションを共有する。作業単位５１０ａ及び５１０ｂに関する入力トランザクションは、セット５０２によってすでに処理されたものとして、それらのトランザクションの処理結果５１４ａ及び５１４ｂとして示されており、完了している（ただしコミットされていない）ものとしてマーク付けされている。さらに入力作業単位５１０ｃは現在、構成要素５０８ａ内で作業単位５１２ｃとして処理されている。構成要素５０８による処理中に、作業単位５１２ｃに含められた記録は、入力作業単位５１０ｃに含められた記録に関連して変更可能であるが、どちらも、異なる時点での所与のトランザクションに関連付けられた記録に対応している。前述のように、ＴＵの構成要素は、一度に所与のトランザクションに関する１つの作業単位のみを処理する。
【００５１】
作業単位５１２ｃに関するトランザクションの処理中に障害が発生した場合、以前に処理されたトランザクションの結果５１４ａ及び５１４ｂによって表される変更はロールバックされる。処理済みトランザクションのこれらの結果５１４ａ及び５１４ｂに対応する入力作業単位５１０ａ及び５１０ｂは、セット５０２の入力時に依然として使用可能である。いくつかの実装では、障害が発生した場合、作業単位５１０ａ〜ｅに対応するトランザクションは、バッチ５０９の解体（unbundling）によって再処理することができる。すなわち、関連付けられたデータ記録及び動作を含む、バッチ５０９内の作業単位５１０ａ〜ｅに対応する各トランザクションは、別々に処理可能であり、１つ又は複数の別個のトランザクションに基づくデータベース２０９への変更は、次のトランザクション処理の前にコミット可能である。いくつかの実装では、障害の発生したトランザクション、たとえば入力作業単位５１０ｃ（又は処理済み作業単位５１２ｃ）に対応するトランザクションが識別可能であるため、バッチ５０９内の関連付けられたデータ記録及び動作を含むトランザクションは、障害が発生したトランザクションならびに（入力作業単位５１０ｃの）関連付けられたデータ記録及び動作を伴わない新しいバッチ５０９として再処理することができる。いくつかの実装では、障害の発生したトランザクションを単独で処理することが可能であり、バッチ５０９内の残りのトランザクションは、２つ又はそれ以上のより小さなトランザクションのバッチ（図示せず）に分割され、１つずつ処理することができる。たとえば、作業単位５１０ａ及び５１０ｂに対応するトランザクションは第１のバッチとして処理可能であり、作業単位５１０ｄ及び５１０ｅに対応するトランザクションは第２のバッチとして処理可能である。
【００５２】
次に図６を参照すると、グラフベースの計算を作成し、計算中にトランザクションを実行するための、流れ図６００が示されている。１つ又は複数のトランザクションを処理するために、構成要素の１つ又は複数のセット（たとえば図４の構成要素４０６のセット４０２）が識別される（ステップ６０２）。前述のように、トランザクション単位（ＴＵ）は、構成要素４０６のセット４０２を動的に呼び出すように構成された構成要素を介して識別するか、又は、１つ又は複数の特別の構成要素（たとえば図２の構成要素２４０及び２５５）を使用して境界を定めることが可能である。
【００５３】
データ記録及びそれらの対応するデータ操作は、ＴＵによって処理されることになるトランザクションのバッチ内のトランザクションに関連付けられる（ステップ６０６）。たとえばトランザクション４１４（図４）は、データ記録３１２及び対応する動作に関連付けられる。いくつかの例では、ユーザ１０３がトランザクションのバッチ内の各トランザクション４１４についてトランザクション・サイズ（すなわちデータ記録３１２の数）を指定することが可能であるか、又は、事前実行モジュール１１０（図１）がデータ記録３１２及び対応する動作を自動的にトランザクションにグループ化することが可能である。次に、構成要素のセット４０２による実行のために、トランザクション４１４が選択される（ステップ６１０）。トランザクションは、各トランザクションについて一単位としてデータ記録３１２を処理することによって、実行可能である（ステップ６１４）。
【００５４】
トランザクション４１４の処理中に、障害が発生する可能性がある。前述のように、データ記録３１２及びその関連付けられたデータ操作は、たとえばシステム障害及び／又は動作障害などを含む様々な理由で、障害が発生する可能性がある。したがって、トランザクション４１４が処理されている間、こうした障害又は他のエラーについてトランザクション４１４をチェックすることができる（ステップ６１８）。障害が検出されない場合、トランザクション４１４に関連付けられたデータ記録３１２及び対応するデータ操作の処理の結果は、単一の単位としてコミットされる（ステップ６２２）。トランザクション４１４の処理中に障害が発生した場合、対応するデータベース（たとえば図３のデータベース２０９）に対して実行された任意の変更をロールバックする必要がある（ステップ６２６）。さらに、障害トランザクション４１４が、まとめてコミットされる複数のトランザクションのバッチ内で処理されている場合、トランザクションの障害バッチを解体し、バッチ内の個別のトランザクションに対応するデータ記録３１２及び関連付けられたデータ操作を、障害トランザクションを伴うか又は伴わずに、個別に再処理することができる（ステップ６３０）。いくつかの実装では、障害が発生したバッチ内のトランザクションを、個別に（各トランザクション４１４の再処理後にデータベース２０９にコミットされた変更と共に）、又は前述の代替技法を使用して、再処理することができる。
【００５５】
前述の技法は、コンピュータ上で実行するためのソフトウェアを使用して実装可能である。たとえば、ソフトウェアは、それぞれが少なくとも１つのプロセッサと、少なくとも１つのデータ・ストレージ・システム（揮発性及び不揮発性のメモリ及び／又はストレージ要素を含む）と、少なくとも１つの入力デバイス又はポートと、少なくとも１つの出力デバイス又はポートとを含む、１つ又は複数のプログラム済み又はプログラム可能コンピュータ・システム（分散型、クライアント／サーバ、又はグリッドなどの様々なアーキテクチャとすることが可能である）上で実行する、１つ又は複数のコンピュータ・プログラム内に、手順を形成する。ソフトウェアは、たとえば計算グラフの設計及び構成に関する他のサービスを提供する大規模プログラムの、１つ又は複数のモジュールを形成することができる。グラフのノード及び要素は、データ・リポジトリに格納されたデータ・モデルに適合するコンピュータ読み取り可能媒体又は他の編成データに格納されたデータ構造として実装可能である。
【００５６】
ソフトウェアは、ＣＤ−ＲＯＭなどのストレージ媒体上に提供するか、汎用又は特定用途向けのプログラム可能コンピュータによって読み取り可能であるか、又は、実行されるコンピュータにネットワークの通信媒体を介して（伝搬信号内に符号化されて）送達することが可能である。すべての機能は、特定用途向けコンピュータ上で、又はコプロセッサなどの特定用途向けハードウェアを使用して、実行可能である。ソフトウェアは、ソフトウェアによって指定された計算の異なる部分が異なるコンピュータによって実行される、分散様式で実装可能である。こうした各コンピュータ・プログラムは、好ましくは、本明細書で説明された手順を実行するために、ストレージ媒体又はデバイスがコンピュータ・システムによって読み取られた場合、コンピュータを構成及び動作させるための、汎用又は特定用途向けのプログラム可能コンピュータによって読み取り可能な、ストレージ媒体又はデバイス（たとえばソリッド・ステート・メモリ又は媒体、あるいは磁気又は光媒体）上に格納されるか、又はこれらにダウンロードされる。本発明のシステムは、コンピュータ・プログラムと共に構成された、コンピュータ読み取り可能ストレージ媒体として実装されるものとみなすことも可能であり、このストレージ媒体は、本明細書で説明された機能を実行するために、特定の事前に定義された様式でコンピュータ・システムを動作させるように構成される。
【００５７】
以上、本発明のいくつかの実施形態について説明してきた。しかしながら、本発明の趣旨及び範囲を逸脱することなく、様々な修正が実行可能であることを理解されよう。たとえば、前述のステップのうちのいくつかは順序に依存するものではないため、説明されたものとは異なる順序で実行可能である。
【００５８】
前述の説明は、添付の特許請求の範囲によって定義される本発明の範囲を、限定するのではなく例示することを意図するものであることを理解されよう。たとえば前述のいくつかの機能ステップは、処理全体に大幅に影響を与えることなく、異なる順序で実行可能である。他の諸実施形態は、以下の特許請求の範囲内にある。
【図１】
2013506199.tif 000003
【図２】
2013506199.tif 000004
【図３】
2013506199.tif 000005
【図４】
2013506199.tif 000006
【図５】
2013506199.tif 000007
【図６】
2013506199.tif 000008
【国際調査報告】
2013506199.tif 000009