(57)【特許請求の範囲】
【請求項１】
一以上のデータに関して連続して実行される一以上の操作命令を含む処理単位の実行要求を受け付ける一以上の受付ノードと、前記操作命令に基づいて操作されるデータを保持する一以上の保持ノードをと有する情報処理システムであって、
前記受付ノードは、
前記処理単位間の第一の順序関係を示す第一の順序情報を、前記処理単位ごとに当該処理単位に含まれるぞれぞれの前記操作命令に付与する順序情報付与手段と、
前記操作命令を前記保持ノードに送信する操作命令送信手段と、
前記処理単位内において他の前記操作命令の実行結果に依存する前記操作命令が有る場合に、当該他の操作命令が再実行されたことを通知させるための通知命令を当該他の操作命令に関連付ける通知命令付与手段とを有し、
前記保持ノードは、
前記操作命令の受信に応じて、当該保持ノードが保持するデータに関する前記操作命令を実行する操作命令実行手段を有し、
前記操作命令実行手段は、既に実行した一以上の第一の操作命令よりも前記第一の順序関係が前であることを示す前記第一の順序情報が付与された第二の操作命令が受信された場合は、前記第二の操作命令の実行後に前記第一の操作命令を再実行し、
第一の前記保持ノードの前記操作命令実行手段は、前記通知命令に関連付けられている前記操作命令の再実行に応じ、当該操作命令が再実行されたことを当該操作命令の実行結果に依存する前記操作命令の操作対象のデータに対応する第二の前記保持ノードに通知し、
前記第二の保持ノードは、前記通知命令に関連付けられている前記操作命令を前記第一の保持ノードに実行させ、当該操作命令の実行結果を用いて当該操作命令の実行結果に依存する前記操作命令を再実行する情報処理システム。
【請求項２】
前記順序情報付与手段は、同一の前記処理単位に含まれる前記操作命令ごとに、当該処理単位内における第二の順序関係を示す第二の順序情報を更に付与し、
前記操作命令実行手段は、既に実行した一以上の第三の操作命令よりも前記第二の順序関係が前であることを示す前記第二の順序情報が付与された第四の操作命令が受信された場合は、前記第四の操作命令の実行後に前記第三の操作命令を再実行する請求項１記載の情報処理システム。
【請求項３】
前記操作命令実行手段は、前記通知命令に関連付けられている前記操作命令が再実行された場合に、当該操作命令の操作対象のデータの当該再実行後の状態が当該再実行前の状態と異なるときに、当該操作命令が再実行されたことを通知する請求項１又は２記載の情報処理システム。
【請求項４】
前記操作命令実行手段は、前記操作命令の実行に応じ、当該操作命令の実行通知を当該操作命令に係る前記受付ノードに通知し、
前記受付ノードは、
前記実行通知に基づいて、前記処理単位に含まれる全ての前記操作命令の終了を判定し、当該受付ノードが受け付けた前記処理単位の中で全ての前記操作命令が終了していない前記処理単位に付与されている識別情報に基づいて、全ての前記操作命令が終了した前記処理単位の実行結果を出力する時期を判定する終了処理手段とを有する請求項１乃至３いずれか一項記載の情報処理システム。
【請求項５】
一以上のデータに関して連続して実行される一以上の操作命令を含む処理単位の実行要求を受け付ける一以上の受付ノードと、前記操作命令に基づいて操作されるデータを保持する一以上の保持ノードをと有する情報処理システムにおける情報処理方法であって、
前記受付ノードは、
前記処理単位間の第一の順序関係を示す第一の順序情報を、前記処理単位ごとに当該処理単位に含まれるぞれぞれの前記操作命令に付与する順序情報付与手順と、
前記操作命令を前記保持ノードに送信する操作命令送信手順と、
前記処理単位内において他の前記操作命令の実行結果に依存する前記操作命令が有る場合に、当該他の操作命令が再実行されたことを通知させるための通知命令を当該他の操作命令に関連付ける通知命令付与手順とを実行し、
前記保持ノードは、
前記操作命令の受信に応じて、当該保持ノードが保持するデータに関する前記操作命令を実行する操作命令実行手順を実行し、
前記操作命令実行手順は、既に実行した一以上の第一の操作命令よりも前記第一の順序関係が前であることを示す前記第一の順序情報が付与された第二の操作命令が受信された場合は、前記第二の操作命令の実行後に前記第一の操作命令を再実行し、
第一の前記保持ノードの前記操作命令実行手順は、前記通知命令に関連付けられている前記操作命令の再実行に応じ、当該操作命令が再実行されたことを当該操作命令の実行結果に依存する前記操作命令の操作対象のデータに対応する第二の前記保持ノードに通知し、
前記第二の保持ノードは、前記通知命令に関連付けられている前記操作命令を前記第一の保持ノードに実行させ、当該操作命令の実行結果を用いて当該操作命令の実行結果に依存する前記操作命令を再実行する情報処理方法。
【請求項６】
前記順序情報付与手順は、同一の前記処理単位に含まれる前記操作命令ごとに、当該処理単位内における第二の順序関係を示す第二の順序情報を更に付与し、
前記操作命令実行手順は、既に実行した一以上の第三の操作命令よりも前記第二の順序関係が前であることを示す前記第二の順序情報が付与された第四の操作命令が受信された場合は、前記第四の操作命令の実行後に前記第三の操作命令を再実行する請求項５記載の情報処理方法。
【請求項７】
前記操作命令実行手順は、前記通知命令に関連付けられている前記操作命令が再実行された場合に、当該操作命令の操作対象のデータの当該再実行後の状態が当該再実行前の状態と異なるときに、当該操作命令が再実行されたことを通知する請求項５又は６記載の情報処理方法。
【請求項８】
前記操作命令実行手順は、前記操作命令の実行に応じ、当該操作命令の実行通知を当該操作命令に係る前記受付ノードに通知し、
前記受付ノードは、
前記実行通知に基づいて、前記処理単位に含まれる全ての前記操作命令の終了を判定し、当該受付ノードが受け付けた前記処理単位の中で全ての前記操作命令が終了していない前記処理単位に付与されている識別情報に基づいて、全ての前記操作命令が終了した前記処理単位の実行結果を出力する時期を判定する終了処理手順とを実行する請求項５乃至７いずれか一項記載の情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム及び情報処理方法に関し、特に分散管理されるデータを処理する情報処理システム及び情報処理方法に関する。
【背景技術】
【０００２】
分散トランザクションとは、一つのトランザクションに属する処理が複数のノード（コンピュータ）に分散されて実行される処理形態をいう。トランザクションとは、関連する複数の処理を一つの処理単位として実行する情報処理の単位のことである。
【０００３】
従来、分散トランザクションに関して、トランザクションモニタのように、分散実行される処理を一箇所に集めて直列化する技術がある。また、分散トランザクションにおいて処理対象とされるデータに対してロックをかけることによって、分散実行される処理を論理的に直列化する技術がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１０−１１６２１５号公報
【特許文献２】特開平１０−６９４１８号公報
【特許文献３】特表２００８−５２５９２３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、分散実行される処理を直列化するような従来の技術では、処理の並列性が失われ、また、処理の直列化又は同期化に必要となる通信負荷によって、処理性能の向上を図るのが困難であるという問題がある。斯かる通信負荷は、分散トランザクションにおいて利用されるノード数が多ければ多いほど、増加する傾向にある。すなわち、分散トランザクションを処理するシステムの規模が大きくなればなるほど、処理性能の劣化が顕著になってしまう。
【０００６】
本発明は、上記の点に鑑みてなされたものであって、分散管理されるデータに対する操作命令列の並列性を向上させることのできる情報処理システム及び情報処理方法の提供を目的とする。
【課題を解決するための手段】
【０００７】
そこで上記課題を解決するため、情報処理システムは、一以上のデータに関して連続して実行される一以上の操作命令を含む処理単位の実行要求を受け付ける一以上の受付ノードと、前記操作命令に基づいて操作されるデータを保持する一以上の保持ノードをと有し、前記受付ノードは、前記処理単位間の第一の順序関係を示す第一の順序情報を、前記処理単位ごとに当該処理単位に含まれるぞれぞれの前記操作命令に付与する順序情報付与手段と、前記操作命令を前記保持ノードに送信する操作命令送信手段とを有し、前記保持ノードは、前記操作命令の受信に応じて、当該保持ノードが保持するデータに関する前記操作命令を実行する操作命令実行手段を有し、前記操作命令実行手段は、既に実行した一以上の第一の操作命令よりも前記第一の順序関係が前であることを示す前記第一の順序情報が付与された第二の操作命令が受信された場合は、前記第二の操作命令の実行後に前記第一の操作命令を再実行する。
【発明の効果】
【０００８】
開示された技術によれば、分散管理されるデータに対する操作命令列の並列性を向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の実施の形態における情報処理システムの構成例を示す図である。
【図２】本発明の実施の形態における情報処理装置のハードウェア構成例を示す図である。
【図３】レセプタ及びコンテナの機能構成例を示す図である。
【図４】操作命令列受け付け時におけるレセプタによる処理手順を説明するためのフローチャートである。
【図５】処理の進行に応じた操作命令列の遷移例を示す図である。
【図６】コンテナによる操作命令列受信時の処理手順を説明するためのフローチャートである。
【図７】操作命令実行履歴記憶部の構成例を示す図である。
【図８】確定状態記憶部の構成例を示す図である。
【図９】コールバック処理において依存先のコンテナが実行する処理手順を説明するためのフローチャートである。
【図１０】コールバック処理において依存元のコンテナが実行する処理手順を説明するためのフローチャートである。
【図１１】実行通知に応じてレセプタが実行する処理手順を説明するためのフローチャートである。
【図１２】確定プロトコルのシーケンス図の一例である。
【図１３】一つの操作命令列に他の操作命令列が割り込む例を示す図である。
【図１４】一つの操作命令列内の操作命令の実行順が逆転してしまう例を示す図である。
【図１５】依存先の操作命令の投機的な実行により実行結果が不正となる例を示す図である。
【発明を実施するための形態】
【００１０】
以下、図面に基づいて本発明の実施の形態を説明する。図１は、本発明の実施の形態における情報処理システムの構成例を示す図である。同図において、情報処理システム１は、レセプタＲ１及Ｒ２等の一以上のレセプタＲと、コンテナＣ１、Ｃ２、及びＣ３等の一以上のコンテナＣとを含む。
【００１１】
レセプタＲは、操作命令列の実行要求を受け付けるノードである。操作命令列は、連続的に実行（一連実行）されるべき処理単位としての、一以上の操作命令の配列をいう。操作命令列は、一般的にトランザクションと呼ばれる概念に近い。但し、本実施の形態の操作命令列には、ｃｏｎｓｉｓｔｅｎｔなものだけでなく、ｅｖｅｎｔｕａｌなものも含まれる。ｃｏｎｓｉｓｔｅｎｔな操作命令列は、操作命令列間の順序関係に正しく維持されることが要求される。一方、ｅｖｅｎｔｕａｌな操作命令列は、操作命令列間の順序関係が維持されることは要求されない。ｃｏｎｓｉｓｔｅｎｔな操作命令列とｅｖｅｎｔｕａｌな操作命令列とを区別しない場合、単に、操作命令列という。
【００１２】
なお、操作命令とは、情報処理システム１において管理対象とされているデータに対する操作の実行命令をいう。操作には、例えば、データの状態を変化させる各種処理や、取得及び削除等が含まれる。レセプタＲは、受信された操作命令列を当該操作命令列において操作対象とされるデータに対応するコンテナＣに送信する。
【００１３】
コンテナＣは、情報処理システム１において管理対象とされるデータを、データストアを用いて、キー・バリューストア（ｋｅｙ−ｖａｌｕｅ  ｓｔｏｒｅ）の形式によって保持又は格納するノードである。キーは、データ名であり、ｖａｌｕｅは、データの実体（以下、単に「データ」という。）である。したがって、複数のコンテナＣによって、分散キー・バリューストアが実現される。分散キー・バリューストアにおいて、各データが所在するノード（本実施の形態ではコンテナＣ）は、キー（データ名）に基づいて一意に定まる。本実施の形態では、便宜上、各コンテナＣは、それぞれ一つのデータを保持することとする。但し、一つのコンテナＣが二以上のデータを保持する形態を除外する趣旨ではない。コンテナＣは、レセプタＲより受信される操作命令を自らが保持するデータに対して実行する。したがって、操作命令は、コンテナＣが受け付け可能な単位におけるデータに対する操作の命令であるといえる。各コンテナＣ間においても、コールバックと呼ばれる仕組みに基づいて操作命令の呼び出しは行われる。コールバックとは、操作命令の依存関係が維持された状態による操作命令列の実行を実現するための仕組みである。本実施の形態において、操作命令の依存関係とは、異なるデータを操作対象とする操作命令間において、一方の操作命令の実行結果が他方の操作命令に影響を及ぼす関係をいう。ここでいう一方の操作命令（すなわち、他方に依存される操作命令）を依存先といい、他方の操作命令（すなわち、一方に依存する操作命令）を依存元という。
【００１４】
なお、コンテナＣによって保持されるデータの種別は所定のものに限定されない。数値、文字、文字列、文書データ、画像データ、動画データ、音声データ、その他の電子データ等、各種のデータが保持対象となりうる。
【００１５】
また、分散キー・バリューストアは、ＤＨＴ（Distributed Hash Table）等、公知技術を用いて実現可能であるため、その詳細（例えば、キーに基づいてどのようにコンテナＣを特定することができるか等）については省略する。
【００１６】
上記各ノードは、ＬＡＮ（Local Area Network）又はインターネット等のネットワークを介して接続される一台以上の情報処理装置（コンピュータ）によって実現される。本実施の形態におけて、「ノード」と情報処理装置との関係は、１対１限定されない。例えば、図１に示される各ノード（レセプタＲ又はコンテナＣ）は、それぞれが一つ情報処理装置であってもよい。または、レセプタＲ１及びコンテナＣ１に一つ、コンテナＣ２に一つ、レセプタＲ１及びコンテナＣ３に一つの情報処理装置が割り当てられてもよい。
【００１７】
したがって、各情報処理装置がレセプタＲであるかコンテナＣであるかは、操作命令列ごとに異なりうる。或る操作命令列についてレセプタＲとして機能した情報処理装置は、他の操作命令列においてコンテナＣとして機能してもよい。また、一つの操作命令列に関して一つの情報処理装置がレセプタＲ及びコンテナＣの双方として機能してもよい。
【００１８】
図２は、本発明の実施の形態における情報処理装置のハードウェア構成例を示す図である。図２の情報処理装置１０は、それぞれバスBで相互に接続されているドライブ装置１００と、補助記憶装置１０２と、メモリ装置１０３と、ＣＰＵ１０４と、インタフェース装置１０５とを有する。
【００１９】
情報処理装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記録した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。例えば、コンテナＣとしての情報処理装置１０の補助記憶装置１０２は、図１におけるデータストアとして機能する。
【００２０】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従って情報処理装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２１】
図３は、レセプタ及びコンテナの機能構成例を示す図である。同図において、レセプタＲは、操作命令列受付部１１、順序情報付与部１２、コールバック付与部１３、操作命令送信部１４、確定プロトコル制御部１５、終了処理部１６、及び操作命令列記憶部１７等を有する。これら各部は、レセプタＲとしての情報処理装置１０にインストールされたプログラムがＣＰＵ１０４に実行させる処理により実現される。
【００２２】
操作命令列受付部１１は、操作命令列の実行要求を受け付ける。当該実行要求は、ネットワークを介して他のコンピュータより受信されてもよいし、レセプタＲとしての情報処理装置１０においてユーザにより入力されてもよい。本実施の形態では、当該他のコンピュータ及び当該ユーザ等を「クライアント」と呼ぶ。
【００２３】
順序情報付与部１２は、操作命令列単位で一意であり、時間軸上における順序関係（前後関係）を識別可能な値（例えば、番号）を、実行要求に係る操作命令列に付与する。操作命令列単位で一意であるということは、情報処理システム１において一意である（すなわち、複数のレセプタＲ間で重複することはない）ことをいう。本実施の形態において、当該番号を「論理クロック」という。例えば、ランポート論理クロックを本実施の形態の論理クロックとして用いてもよい。ランポート論理クロックは、「http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf」に詳しい。
【００２４】
または、各レセプタＲが同期信号を交換することにより、論理クロックが実現されてもよい。同期信号では、確保された論理クロックの値が交換される。具体的には、「１００」という論理クロックを確保したレセプタＲは、そのことを他のレセプタＲに通知する。そうすることにより、何番までの論理クロックが確保されているのかについて各レセプタＲ間で知識を共有することができる。論理クロックが重複した場合、優先度の高いレセプタＲが当該論理クロックを使用すればよい。
【００２５】
更に、現在の論理クロックの値が記録されたタグデータを、一筆書きの経路で各レセプタＲに流通（周回）させることにより、論理クロックが実現されてもよい。当該タグデータを受信したレセプタＲは、自らが論理クロックを確保する場合は、当該タグデータの値を論理クロックとして確保し、当該タグデータに例えば１を加算して、当該タグデータを流通させる。
【００２６】
本実施の形態において、論理クロックは、操作命令列間の実行順の順序関係を示す情報として利用される。順序情報付与部１２は、また、一つの操作命令列内における操作命令の順序関係を示す情報（以下、「操作命令番号」という。）を各操作命令に付与する。操作命令番号は、一つの操作命令列内で一意であればよい。
【００２７】
なお、本実施の形態では、論理クロックの値と操作命令番号とは、一つのデータによって表現される。当該データを、以下「タイムスタンプ」という。すなわち、本実施の形態では、順序情報付与部１２によって、操作命令ごとに、論理クロックの値及び操作命令番号を含むタイムスタンプが付与される。
【００２８】
コールバック付与部１３は、操作命令列内に、他の操作命令の実行結果に依存する操作命令が存在する場合は、当該他の操作命令にコールバック命令を付与する（関連付ける）。他の操作命令の実行結果に依存する操作命令とは、当該他の操作命令がデータの取得命令である場合に、取得されたデータに対して操作を行う操作命令が一例として挙げられる。また、コールバック命令とは、コールバック命令が付与された操作命令が再実行された場合に、当該操作命令が再実行されたことを通知させるための通知命令をいう。すなわち、コールバック命令が付与された操作命令を再実行したコンテナＣは、当該操作命令が再実行されたことを当該操作命令の依存元の他のコンテナＣに通知する。
【００２９】
操作命令列記憶部１７は、受け付けられた操作命令列を補助記憶装置１０２又はメモリ装置１０３を用いて記憶する。
【００３０】
操作命令送信部１４は、操作命令列を、当該操作命令列において操作対象とされるデータを保持するコンテナＣに送信（配信）する。
【００３１】
確定プロトコル制御部１５は、レセプタＲ間及びコンテナＣ間において、どの操作命令列までの確定が保証されたかに関する知識を共有するための仕組みを実現するための処理を実行する。本実施の形態において、当該仕組みを「確定プロトコル」という。操作命令列が確定されるとは、操作命令列間の順序関係が保証された上で操作命令列の実行が終了したことをいう。なお、どの操作命令列までの確定が保証されたかに関する知識は、必ずしも現実にどの操作命令列が確定されたかを示すものではない。当該知識は、あくまでも、どの操作命令列までが確定されたと判断して安全かを示すものである。なお、本実施の形態において、操作命令列に関して「確定」又は「未確定」というとき、確定プロトコルに基づく確定又は未確定を意味する。
【００３２】
終了処理部１６は、操作命令列の終了の判定及び当該終了に応じた処理を実行する。操作命令列に含まれる全ての操作命令の実行が順序正しく終了した場合、当該操作命令列は終了する。なお、操作命令列の終了は、必ずしも操作命令列の確定を伴わない。終了は、他の操作命令列との前後関係は問わないからである。
【００３３】
一方、コンテナＣは、操作命令受信部２１、操作命令ソート部２２、操作命令実行部２３、確定処理部２４、操作命令実行履歴記憶部２５、及び確定状態記憶部２６等を有する。
【００３４】
操作命令受信部２１は、レセプタＲによって配信される操作命令を受信する。操作命令ソート部２２は、新たに受け付けられた操作命令と、操作命令実行履歴記憶部２５に記録されている操作命令とを、それぞれのタイムスタンプに基づいてソート（整列）する。
【００３５】
操作命令実行部２３は、当該コンテナＣが保持するデータに対して操作命令を投機的に実行（投機実行）する。操作命令の投機実行とは、タイムスタンプに基づけば先に実行すべき操作命令が存在するか否かに拘わらず、操作命令を実行することをいう。また、操作命令実行部２３は、操作対象となるデータについて排他制御（ロック）は行わない。投機実行すること及び排他制御を行わないことにより、複数のコンテナＣによる並列性を向上させることができる。
【００３６】
但し、投機実行により、操作命令の順序関係が保証されなくなってしまう。そこで、操作命令実行部２３は、操作命令ソート部２２によるソート結果に応じて、操作命令実行履歴記憶部２５に記録されている、既に実行済みの操作命令を再実行する。当該再実行により、投機実行による操作命令の実行順の不整合が是正される。また、操作命令実行部２３は、各操作命令を一つずつ直列的に実行する。したがって、排他制御が行われないことによる不都合の発生を回避することができる。なお、本実施の形態では、操作命令が直列的に実行されるのであって、操作命令列（例えば、トランザクション）単位で見ると、並列的に実行されうる。
【００３７】
操作命令実行履歴記憶部２５は、補助記憶装置１０２又はメモリ装置１０３を用いて、新たに受信された操作命令及び実行済みの操作命令をその実行順（タイムスタンプ順）に記憶する。確定状態記憶部２６は、当該コンテナＣが保持するデータについて、確定した操作命令列の実行結果の状態（値）を補助記憶装置１０２又はメモリ装置１０３を用いて記憶する。
【００３８】
確定処理部２４は、確定プロトコルによって確定されたと判断できる操作命令列に関して、確定処理を実行する。例えば、確定処理部２４は、当該操作命令列に属する操作命令を操作命令実行履歴記憶部２５より除去する。
【００３９】
以下、情報処理システム１の処理手順について説明する。図４は、操作命令列受け付け時におけるレセプタによる処理手順を説明するためのフローチャートである。
【００４０】
ステップＳ１０１において、操作命令列受付部１１は、操作命令列の実行要求を受け付ける。操作命令列受付部１１は、受け付けた操作命令列を操作命令列記憶部１７に記録しておく。
【００４１】
図５は、処理の進行に応じた操作命令列の遷移例を示す図である。同図には、操作命令列Ｔ１及びＴ２の二つの操作命令列について、図４の処理の進行に応じた遷移例が示されている。ここでは、操作命令列Ｔ１に注目することとする。すなわち、操作命令列Ｔ１が実行対象として受け付けられたこととする。実行要求受け付け時の操作命令列Ｔ１の状態は、例えば、（１）に示される通りである。状態（１）において、操作命令列Ｔ１は、ｓｅｔ（Ｙ，１０）、ａ＝ｇｅｔ（Ｙ）、ａｄｄ（Ｘ，ａ）、及びｍｕｌ（Ｘ，２）の４つの操作命令を含む。ｓｅｔ（Ｙ，１０）は、データＹへの１０のセット（設定）を意味する。ａ＝ｇｅｔ（Ｙ）は、データＹの値を取得しａに代入することを意味する。ａｄｄ（Ｘ，ａ）は、データＸにａの値をＸに加算することを意味する。ｍｕｌ（Ｘ，２）は、データＸに２を乗ずることを意味する。
【００４２】
上記より明らかなように、本実施の形態において、操作命令は、以下の形式で表現される。
【００４３】
操作命令名（引数・・・）
【００４４】
基本的に、第一引数は、操作対象とされるデータの識別子（データ名）である。第二引数が有る場合、第二引数は、第一引数によって識別されるデータに対して操作命令が作用する値である。
【００４５】
続いて、順序情報付与部１２は、論理クロック（すなわち、複数のレセプタＲを跨いで一意性が保証された番号）を確保し、確保された論理クロックを当該操作命令列Ｔ１に割り当てる（Ｓ１０２）。
【００４６】
続いて、確定プロトコル制御部１５は、ローカル確定クロックの値を算出する（Ｓ１０３）。ローカル確定クロックとは、一つのレセプタＲが確定されたと推定する操作命令列に対する論理クロックの値である。ローカル確定クロックは、以下の式によって算出される。
【００４７】
ｍｉｎ（操作命令列記憶部１７に記録されている操作命令列に対して割り当てられている論理クロックの値）−１
【００４８】
例えば、一つのレセプタＲの操作命令列に３つの操作命令列が記録されており、それぞれに割り当てられた論理クロックの値が１００、１０１、１０３であるとする。この場合、最小値は１００である。したがって、当該レセプタＲのローカル確定クロックの値は、１００−１＝９９となる。すなわち、当該レセプタＲは、９９までの値が論理クロックとして割り当てられた操作命令列は確定されたものと推定する。後述されるように、ローカル確定クロックは、確定プロトコルを実現するために用いられる。
【００４９】
続いて、順序情報付与部１２は、操作命令列Ｔ１に含まれる各操作命令にタイムスタンプを付与する（Ｓ１０４）。その結果、操作命令列Ｔ１は、図５の（２）に示される状態となる。状態（２）において、操作命令毎に左の列に付与された値がタイムスタンプである。
【００５０】
本実施の形態において、タイムスタンプは、以下の形式によって表現される。
＜論理クロック＞．＜操作命令番号＞．＜再実行回数＞
【００５１】
すなわち、３つの階層概念がドットで区切られて表現される。但し、当該表現形式は、一例にすぎない。区切り記号はドットでなくてもよい。または、各階層概念の桁数が固定であれば、区切り記号が無くてもよい。また、３つの階層概念の並び順が上記と異なっていてもよい。
【００５２】
論理クロックは、同一の操作命令列に属する各操作命令には、当該操作命令列に付与された値が付与される。すなわち、同一の操作命令列に属する操作命令列のタイムスタンプに含まれる論理クロックは共通のものである。同図では、操作命令列Ｔ１のタイムスタンプが「１０１」である例が示されている。
【００５３】
操作命令番号は、操作命令列内における操作命令の実行順を示す値である。したがって、同一の操作命令列内において、操作命令ごとに一意な値となる。同図では、００〜０４の値が順番に付与されている。但し、一つのレセプタＲ内で一意な値が操作命令番号として付与されてもよい。例えば、操作命令列Ａの操作命令には、００〜０４が操作命令番号として付与され、操作命令列Ｂの操作命令には、０５以降の操作命令番号が付与されるといった具合である。
【００５４】
再実行回数は、操作命令の再実行回数である。再実行回数の初期値は「００」であり、再実行が行われるたびにインクリメントされる。
【００５５】
続いて、コールバック付与部１３は、操作命令列Ｔ１内に、他の操作命令の実行結果に依存する操作命令の有無を判定する（Ｓ１０５）。操作命令列Ｔ１内において、ａｄｄ（Ｘ，ａ）の第二引数ａは、ａ＝ｇｅｔ（Ｙ）の実行結果である。したがって、ａｄｄ（Ｘ，ａ）は、ａ＝ｇｅｔ（Ｙ）の実行結果に依存する。ａの値に応じて、ａｄｄ（Ｘ，ａ）の結果は変化するからである。
【００５６】
よりロジカルに説明すると、本実施の形態の場合、コールバック付与部１３は、他の操作命令の実行結果を格納する変数を引数に含む操作命令の有無を判定する。当該操作命令が存在する場合、当該操作命令は、当該他の操作命令の実行結果に依存すると判定される。但し、当該判定方法は、操作命令の表記法に応じて適宜変更されてよい。
【００５７】
他の操作命令の実行結果に依存する操作命令が有る場合（Ｓ１０５でＹｅｓ）、コールバック付与部１３は、依存される側（依存先）の操作命令に対し、コールバック命令を付与する（Ｓ１０６）。その結果、操作命令列Ｔ１は、図５の（３）に示されるようになる。
【００５８】
ａｄｄ（Ｘ，ａ）とａ＝ｇｅｔ（Ｙ）との関係において、ａｄｄ（Ｘ，ａ）が依存元であり、ａ＝ｇｅｔ（Ｙ）が依存先に相当する。したがって、状態（３）では、ａ＝ｇｅｔ（Ｙ）に対してコールバック命令（「Ｃｂ（Ｙ，Ｘ，１０１．０１．００）」）が付与されている。すなわち、本実施の形態において、コールバック命令は、以下の形式によって表現される。
【００５９】
Ｃｂ（＜依存先のデータ名＞，＜依存元のデータ名＞，・・・，＜コールバック命令に応じて再実行を開始する操作命令のタイムスタンプ＞）
【００６０】
本実施の形態において、コールバック命令の操作命令名は、「Ｃｂ」である。
【００６１】
第一引数の＜依存先のデータ名＞は、操作命令間の依存関係において、依存先の操作命令において操作対象とされるデータのデータ名である。当該データ名は、実質的に、依存先の操作命令を実行するコンテナＣの識別情報である。
【００６２】
第二引数の＜依存元のデータ名＞は、操作命令間の依存関係において、依存元の操作命令において操作対象とされるデータのデータ名である。当該データ名は、実質的に、依存元の操作命令を実行するコンテナＣの識別情報である。
【００６３】
操作命令間の依存関係は、当該操作命令によって操作対象とされるデータ間の依存関係と等価であるといえる。し依存先のデータ名に係るデータの状態が変更された場合、依存元のデータ名に係るデータの状態は影響を受けるからである。たがって、上記では、依存先のデータ名又は依存元のデータ名といった表現が用いられている。なお、依存先のデータは、複数存在しうる。例えば、操作命令列Ｔ１において、ａ＝ｇｅｔ（Ｙ）より後に、ａｄｄ（Ｚ，ａ）という操作命令が含まれていた場合、データＺもデータＹに依存する。したがって、依存元のデータ名の引数の数は１以上指定されうる。
【００６４】
最後尾の引数の＜コールバック命令に応じて再実行を開始する操作命令のタイムスタンプ＞は、当該コールバック命令が付与された操作命令のタイムスタンプとされる。すなわち、ａ＝ｇｅｔ（Ｙ）に対して付与されたタイムスタンプである。
【００６５】
続いて、操作命令送信部１４は、操作命令列Ｔ１に当該レセプタＲの識別情報を付与して、操作命令列Ｔ１において操作対象とされるデータを保持するコンテナＣに送信する（Ｓ１０７）。レセプタＲの識別情報は、コンテナＣがネットワーク通信においてレセプタＲを識別可能なものであればよい。操作命令列Ｔ１において操作対象とされるデータを保持するコンテナＣとは、操作命令列Ｔ１に含まれるいずれかの操作命令によって操作対象とされるデータを保持するコンテナＣをいう。したがって、相互に異なるデータを操作する操作命令が一つの操作命令列に含まれている場合、複数のコンテナＣが当該操作命令列の送信先となりうる。操作命令列Ｔ１には、データＹを操作する操作命令と、データＸを操作する操作命令が含まれている。したがって、操作命令列Ｔ１は、データＸを保持するコンテナＣｘと、データＹを保持するコンテナＣｙとのそれぞれに送信される。
【００６６】
但し、操作命令送信部１４は、操作命令列の最初の操作命令によって操作対象とされるデータを保持するコンテナＣのみに操作命令列を送信するようにしてもよい。この場合、当該操作命令列に関係するコンテナＣ間において、当該操作命令列が伝搬されればよい。具体的には、操作命令列を受信したコンテナＣは、自らが保持しないデータを操作対象とする操作命令を検出したら、当該データを保持するコンテナＣに操作命令列を転送する。例えば、操作命令列Ｔ１の場合、レセプタＲからの送信先はコンテナＣｙとなる。コンテナＣｙは、ａｄｄ（Ｘ，ａ）を検出すると、コンテナＣｘに当該操作命令列を転送する。
【００６７】
また、レセプタＲが各コンテナＣに操作命令列を送信する場合、必ずしも操作命令列に含まれる全ての操作命令が、各コンテナＣに送信されなくてもよい。すなわち、各コンテナＣへの送信対象は、当該コンテナＣに関係する操作命令に限定されてもよい。この場合、レセプタＲからコンテナＣへは、操作命令ごとに送信が行われてもよいし、当該コンテナＣに関係する複数の操作命令がまとめられて送信されてもよい。
【００６８】
本実施の形態において、各データを保持するコンテナＣは、各データのデータ名に基づいて一意に定まる。そして、各操作命令において操作対象とされるデータのデータ名は、各操作命令の第一引数に指定されている。したがって、操作命令送信部１４又は各コンテナＣは、各操作命令の第一引数に基づいて、操作命令列の送信先のコンテナＣを判定する。
【００６９】
なお、状態（３）の操作命令列Ｔ１の内容は、少なくとも操作命令列Ｔ１の実行が終了するまで操作命令列記憶部１７に保持される。したがって、操作命令列記憶部１７には、複数の操作命令列が記録されうる。
【００７０】
ところで、図５には、操作命令列Ｔ２も示されている。操作命令列Ｔ２の状態（１）は、レセプタＲが受け付けた時点の状態を示す。操作命令列Ｔ２の（２）は、各操作命令にタイムスタンプが付与された状態を示す。ここで、操作命令列Ｔ２の各操作命令のタイムスタンプは、「１００」で始まっている。すなわち、操作命令列Ｔ２に対する論理クロックは「１００」である。本実施の形態では、論理クロックの最小値は「０」であり、時間の経過（論理クロックの確保）に応じて値が大きくなることとする。したがって、操作命令列Ｔ２は、操作命令列Ｔ１より前にレセプタＲによって受け付けられたことが分かる。なお、操作命令列Ｔ２を付け付けたレセプタＲと、操作命令列Ｔ１を受け付けたレセプタＲとは、同じノードであってもよいし異なるノードであってもよい。操作命令列Ｔ２は、データＸを操作対象とするｓｅｔ（Ｘ，２０）のみを含むため、コンテナＣｘに送信される。
【００７１】
このように、情報処理システム１では、各操作命令列は、複数のレセプタＲより非同期的に各コンテナＣに送信される。
【００７２】
続いて、コンテナＣの処理手順について説明する。図６は、コンテナによる操作命令列受信時の処理手順を説明するためのフローチャートである。
【００７３】
コンテナＣの操作命令受信部２１は、操作命令列の受信を待機している。操作命令受信部２１は、操作命令列を受信すると、当該操作命令列より、当該コンテナＣに関係する操作命令を抽出する（Ｓ１１１）。当該コンテナＣに関係する操作命令とは、当該コンテナＣが保持するデータを操作対象とする操作命令である。より具体的には、第一引数に当該コンテナＣが保持するデータのデータ名が指定された操作命令である。例えば、図５のコンテナＣｘにおいて操作命令列Ｔ１が受信された場合、ａｄｄ（Ｘ，ａ）及びｍｕｌ（Ｘ，２）が当該操作命令に該当する。また、コールバック命令が付与されている操作命令であって、当該コールバック命令の第二引数以降に、依存元のデータ名として、当該コンテナＣが保持するデータのデータ名が指定されている操作命令も当該コンテナＣに関係する操作命令に含まれる。例えば、図５のコンテナＣｘにおいて操作命令列Ｔ１が受信された場合、ａ＝ｇｅｔ（Ｙ）が当該操作命令に該当する。以下抽出された１以上の操作命令を「対象操作命令群」という。
【００７４】
なお、レセプタＲが、操作命令の送信先を当該操作命令が操作対象とするデータを保持するコンテナＣに限定する場合上記に説明した抽出処理はコンテナＣでは不要である。また、レセプタＲにおいて操作命令列が分解されて操作命令ごとに送信が行われる場合は、以下の処理手順における対象操作命令群は、受信された一つの操作命令に置き換えられればよい。
【００７５】
続いて、操作命令ソート部２２は、対象操作命令群と、既に操作命令実行履歴記憶部２５に記録されている操作命令とを、それぞれに付与されているタイムスタンプに基づいて昇順にソートし、ソート結果によって操作命令実行履歴記憶部２５を更新する（Ｓ１１２）。すなわち、ソート結果が操作命令実行履歴記憶部２５に記録される。ここで、既に操作命令実行履歴記憶部２５に記録されていた操作命令は、対象信操作命令群とは異なる操作命令列に属する操作命令である。したがって、ソートは、複数の操作命令列に跨って実行される。
【００７６】
図７は、操作命令実行履歴記憶部の構成例を示す図である。同図に示されるように、操作命令実行履歴記憶部２５には、未確定の操作命令列に属する操作命令ごとに、タイムスタンプ、操作命令、及び実行結果が記録される。実行結果は、当該コンテナＣが保持するデータについて、当該操作命令の実行後における状態である。ソート結果によって操作命令実行履歴記憶部２５が更新される場合、対象操作命令群に含まれる操作命令の実行結果は空としておけばよい。なお、タイムスタンプに基づくソートでは、まず、論理クロックの大小が比較され、論理クロックが同じ場合は、操作命令番号が比較される。したがって、ソート順において、或る操作命令列に属する操作命令列の間に、他の操作命令列の属する操作命令が挿入されることはない。また、本実施の形態において、各コンテナＣは一つのデータを保持する。したがって、操作命令実行履歴記憶部２５はとデータとは１対１に対応する。
【００７７】
続いて、操作命令実行部２３は、ソートによって、実行済みの操作命令の順番に変更が有ったか否かを判定する（Ｓ１１３）。すなわち、実行済みの操作命令の中で対象操作命令群よりもタイムスタンプが後である操作命令の有無が判定される。
【００７８】
該当する操作命令が無い場合（Ｓ１１３でＮｏ）、操作命令実行部２３は、対象操作命令群に含まれる操作命令を操作命令番号の順に投機的に実行する（Ｓ１１４）。操作命令実行部２３は、各受信操作命令の実行結果を操作命令実行履歴記憶部２５に記録する。
【００７９】
例えば、対象操作命令群がソート順で最後尾である場合、又は対象操作命令群の受信時に操作命令実行履歴記憶部２５が空であった場合が、この場合に相当する。ここで、「投機的に」というのは、対象操作命令群よりもタイムスタンプが前である操作命令列が以後において受信されないことはこの時点では保証されていないからである。また、当該コンテナＣの対象操作命令群と同じ操作命令列に属する操作命令であって、他のコンテナＣにおいて実行される操作命令列との実行順はこの時点では保証されていないからである。
【００８０】
なお、各操作命令の実行対象は、データストア内に記憶されているデータである。すなわち、投機的な実行においても、いわゆるマスタデータが直接的に操作される。
【００８１】
一方、該当する操作命令が有る場合（Ｓ１１３でＹｅｓ）、操作命令実行部２３は、まず、対象操作命令群に含まれる操作命令を投機的に実行する（Ｓ１１５）。操作命令実行部２３は、各操作命令の実行結果を操作命令実行履歴記憶部２５に記録する。この際、対象操作命令群において先頭の操作命令の操作対象は、ソート順において当該操作命令の一つ前の操作命令に対して操作命令実行履歴記憶部２５に記録されている実行結果である。但し、対象操作命令群がソート順において先頭である場合、確定状態記憶部２６に記録されているデータが、当該操作命令の操作対象とされる。受信操作命令の２番目以降の操作命令の操作対象は、データストア内に記憶されているデータである。
【００８２】
図８は、確定状態記憶部の構成例を示す図である。同図に示されるように、確定状態記憶部２６は、最後に確定された操作命令列のタイムスタンプ（論理クロック）及び当該操作命令列の実行後のデータの状態（確定状態）を記憶する。
【００８３】
ステップＳ１１５において、データストア内におけるデータが先頭の操作命令の操作対象とされないのは、この場合における当該データの状態は、正しくない実行順によって操作命令が実行された結果として得られた状態だからである。なお、ステップＳ１１５における各操作命令の実行結果は、データストアに反映される。
【００８４】
続いて、操作命令実行部２３は、タイムスタンプが対象操作命令群より後である操作命令を、操作命令実行履歴記憶部２５に記録されている順番で（すなわち、タイムスタンプの順番で）実行する（Ｓ１１６）。すなわち、タイムスタンプが対象操作命令群より後である操作命令について再実行が行われる。再実行において、操作対象はデータストアに記憶されているデータである。また、該当する操作命令が実行されるたびにその実行結果がデータストアに反映される。なお、操作命令実行部２３は、再実行された操作命令のタイムスタンプにおける再実行回数をインクリメントする。すなわち、当該再実行回数に１が加算される。
【００８５】
なお、ステップＳ１１４、Ｓ１１５、又はＳ１１６において、コールバック命令が付与されている操作命令であって、当該コールバック命令の第二引数以降に、依存元のデータ名として、当該コンテナＣが保持するデータのデータ名が指定されている操作命令については、当該操作命令に対応するコンテナＣに対して実行要求が送信される。例えば、図５のコンテナＣｘの操作命令実行部２３は、ａ＝ｇｅｔ（Ｙ）の実行要求をコンテナＣｙに対して送信する。当該実行要求を受信したコンテナＣｙでは、図６に示される処理が実行される。コンテナＣｘの操作命令実行部２３は、当該実行要求に応じてコンテナＣｙより返信される値をａに代入して、ａｄｄ（Ｘ，ａ）以降の操作命令を実行する。
【００８６】
但し、依存先（例えば、ａ＝ｇｅｔ（Ｙ））の実行結果の返信を待機せずに、当該依存先の次以降の操作命令が進められてもよい。この場合、依存先の実行結果が返信されるまで不定な値を引数に含む依存元（例えば、ａｄｄ（Ｘ，ａ））の実行はパス（無視）して、以降の操作命令を実行してしまえばよい。
【００８７】
依存元の操作命令を無視しても構わないのは、当該操作命令を無視したとしても、後述するコールバック命令の実行により、依存元の操作命令は実行されるからである。または、依存先の実行結果が返信された後、依存元の操作命令を実行し、依存元の操作命令の次以降の操作命令を再実行してもよい。
【００８８】
ステップＳ１１４又はＳ１１６に続いて、操作命令実行部２３は、実行した各操作命令のタイムスタンプを指定して、各操作命令の実行通知を当該操作命令の送信元のレセプタＲに送信する（Ｓ１１７）。実行通知には、例えば、実行の成否を示す情報が含まれている。また、実行結果として得られたデータが含まれていてもよい。操作命令の送信元のレセプタＲは、操作命令列に付与されているレセプタＲの識別情報に基づいて判定すればよい。なお、実行がパス（無視）された操作命令については、実行通知は送信されない。また、依存先の操作命令のように他のコンテナＣに対して実行要求を送信した操作命令についても、実行通知は送信されない。当該操作命令に関する実行通知は、当該他のコンテナＣより送信されるからである。更に、他のコンテナＣからの実行要求に応じて実行された操作命令についても実行通知は送信されない。他のコンテナＣからの実行要求（呼び出し）に応じて実行された操作命令とは、例えば、コンテナＣｘからの実行要求（呼び出し）に応じてコンテナＣｙにおいて実行されるａ＝ｇｅｔ（Ｙ）のような操作命令である。他のコンテナＣからの呼び出しに応じて実行された操作命令の実行通知がレセプタＲに送信されてしまうと、レセプタＲにおいて、当該操作命令を含む操作命令列が、操作命令の実行順が維持された状態で実行が終了したか否かを判定するのが困難となるからである。したがって、ａ＝ｇｅｔ（Ｙ）の実行通知については、コンテナＣｙにおける操作命令列Ｔ１の受信に応じてコンテナＣｙにおいて実行される際にコンテナＣｙよりレセプタＲに送信される。
【００８９】
なお、上記では、操作命令実行履歴記憶部２５が各操作命令の実行結果を記憶可能な例を説明したが、操作命令実行履歴記憶部２５が、各操作命令の実行結果を記憶しないようにしてもよい。この場合、新たな操作命令列が受信されるたびに、操作命令実行履歴記憶部２５に記録された全ての操作命令がソート順に実行されればよい。ソート順において先頭の操作命令の操作対象は、確定状態記憶部２６に記録されている確定状態とし、２番目以降の操作命令の操作対象は、データストアに記録されているデータとすればよい。
【００９０】
続いて、コールバック命令に基づく処理（コールバック処理）について説明する。まず、コールバックの意義について説明する。
【００９１】
例えば、図５において、データＸを保持するコンテナＣｘは、操作命令列Ｔ１に関して、ａｄｄ（Ｘ、ａ）及びｍｕｌ（Ｘ，２）を実行する。また、コンテナＣｘは、ａ＝ｇｅｔ（Ｙ）の実行要求をコンテナＣｙに送信する。ａ＝ｇｅｔ（Ｙ）は、コンテナＣｘが実行する操作命令（ａｄｄ（Ｘ，ａ））の依存先の操作命令だからでる。
【００９２】
一方、データＹを保持するコンテナＣｙは、操作命令列Ｔ１に関して、ｓｅｔ（Ｙ，１０）及びａ＝ｇｅｔ（Ｙ）を実行する。
【００９３】
ここで、コンテナＣｙにおいてｓｅｔ（Ｙ，１０）が実行される前に、コンテナＣｘは、ａ＝ｇｅｔ（Ｙ）の実行要求をコンテナＣｙに送信する可能性がある。この場合、コンテナＣｙにおいて、ｓｅｔ（Ｙ，１０）の実行前のＹの値（状態）が「２０」であったとすると、コンテナＣｘでは、ａ＝２０として、ａｄｄ（Ｘ，ａ）以降の処理が実行されてしまう。その後、コンテナＣｙにおいてｓｅｔ（Ｙ，１０）が実行されると、操作命令列Ｔ１内において正しい順序が確保されない状態で操作命令列Ｔ１に含まれる全ての操作命令の実行が終了してしまう。そうすると、操作命令列Ｔ１の実行結果は不正なものとなってしまう。斯かる事態の発生を防止するための仕組みが本実施の形態におけるコールバックである。
【００９４】
図９は、コールバック処理において依存先のコンテナが実行する処理手順を説明するためのフローチャートである。同図の処理は、図６のステップＳ１１６において、コールバック命令が付与された操作命令が再実行されたときに当該操作命令を再実行したコンテナＣにおいて実行される。
【００９５】
ステップＳ１２１において、操作命令実行部２３は、コールバック命令が付与された操作命令の再実行の後、当該コンテナＣが依存先であるか否かを判定する。具体的には、当該コンテナＣが、当該コールバック命令の第一引数に指定されているデータ名に係るデータを保持するコンテナＣであるか否かが判定される。
【００９６】
当該コンテナＣが依存先である場合（Ｓ１２１でＹｅｓ）、操作命令実行部２３は、当該コールバック命令が付与された操作命令の再実行の実行結果が前回の実行結果と異なるか否かを判定する。前回の実行結果は、当該操作命令の再実行前に、操作命令実行履歴記憶部２５において当該操作命令に対して記憶されていた実行結果である。
【００９７】
例えば、コンテナＣｘからのａ＝ｇｅｔ（Ｙ）の実行要求に応じてコンテナＣｙが当該操作命令を実行した後にコンテナＣｙにおいて操作命令列Ｔ１が受信された場合、当該受信に応じて実行されるａ＝ｇｅｔ（Ｙ）の値は、前回と異なりうる。当該受信に応じて実行される場合は、ａ＝ｇｅｔ（Ｙ）の前に、ｓｅｔ（Ｙ，１０）が実行されるからである。
【００９８】
比較した実行結果が異なる場合（Ｓ１２２でＹｅｓ）、操作命令実行部２３は、当該操作命令に付与されているコールバック命令を実行する（Ｓ１２３）。すなわち、操作命令実行部２３は、コールバック命令の第二引数以降に指定されているデータ名に係るコンテナＣに対して、コールバック命令の最後尾の引数の値を指定して、操作命令の再実行要求を送信する。当該再実行要求は、コールバック命令が付与された命令の再実行の通知に相当する。本実施の形態において、コールバック命令の最後尾の引数は、当該コールバック命令が付与された操作命令に対するタイムスタンプである。したがって、当該再実行要求は、当該コールバック命令が付与された操作命令の再実行要求に相当する。より具体的には、「Ｃｂ（Ｙ，Ｘ，１０１．０１．００）」というコールバック命令の場合、コンテナＣｘに対して、タイムスタンプが「１０１．０１．００」以降の操作命令の再実行要求が送信される。
【００９９】
なお、操作命令実行履歴記憶部２５が各操作命令の実行結果を記憶しない場合、前回の実行結果との比較を行うことなく、コールバック命令が付与された操作命令が実行されるたびに、コールバック命令が実行されればよい。この場合、コールバック命令が付与された操作命令が初めて実行される場合は、コールバック命令は実行されなくてもよい。但し、本実施の形態のように、コールバック命令が付与された操作命令の実行結果が前回と異なる場合にコールバック命令を実行することにより、コンテナＣの処理負荷及び通信量の軽減を図ることができる。
【０１００】
また、依存先の操作命令の実行結果の返信を待たずに他の操作命令の実行が行われる可能性が有る場合も、コールバック命令が付与された操作命令が実行されるたびに、コールバック命令が実行されればよい。この場合、コールバック命令が付与された操作命令が初めて実行される場合であっても、コールバック命令を実行するとよい。仮に、コールバック命令が付与された操作命令について再実行が行われない場合、当該依存元の引数の値が不定のままとなってしまうからである。
【０１０１】
続いて、コールバック命令の実行によってコンテナＣより送信される再実行要求を受信したコンテナＣが実行する処理について説明する。
【０１０２】
図１０は、コールバック処理において依存元のコンテナが実行する処理手順を説明するためのフローチャートである。
【０１０３】
依存元のコンテナＣにおいて、コールバック命令に基づく再実行要求が受信されると（Ｓ１３１）、当該コンテナＣの操作命令送信部１４は、操作命令実行履歴記憶部２５に記録されている操作命令のうち、当該再実行要求に指定されているタイムスタンプ以降の操作命令を再実行する（Ｓ１３２）。なお、ステップＳ１３２における、各操作命令の実行内容は、図６のステップＳ１１６と同様である。
【０１０４】
例えば、図５におけるコンテナＣｘにおいて、「Ｃｂ（Ｙ，Ｘ，１０１．０１．００）」に基づく再実行要求が受信された場合、ａ＝ｇｅｔ（Ｙ）の実行要求がコンテナＣｙに送信され、ａｄｄ（Ｘ，ａ）、ｍｕｌ（Ｘ，２）がコンテナＣｘにおいて実行される。なお、ステップＳ１３２では、ａ＝ｇｅｔ（Ｙ）の実行結果が返信された後（すなわち、ａの値が明確になった後）、ａに具体的な値が代入されてａｄｄ（Ｘ，ａ）の実行要求が送信されるのが望ましい。すなわち、依存先の操作命令の実行結果を受けて、依存元の操作命令の実行要求が送信されるのが望ましい。
【０１０５】
なお、再実行要求に指定されたタイムスタンプに対応する操作命令が操作命令実行履歴記憶部２５に記録されていない場合、当該再実行要求は無視されてよい。このような状況は、当該コンテナＣにおいては、まだ、依存元の操作命令を含む操作命令列が受信されていない場合に発生しうる。この場合、その後の当該コンテナＣにおける当該操作命令列の受信に応じた依存元の操作命令の実行により、同一操作命令列内における操作命令の順序関係は正しく維持されるからである。
【０１０６】
続いて、図６のステップＳ１１７において送信される実行通知を受信したレセプタＲによって実行される処理について説明する。
【０１０７】
図１１は、実行通知に応じてレセプタが実行する処理手順を説明するためのフローチャートである。
【０１０８】
レセプタＲにおいて実行通知が受信されると、当該レセプタＲの終了処理部１６は、当該実行通知に指定されているタイムスタンプに係る操作命令の実行は終了したことを記憶する（Ｓ１４１）。例えば、操作命令列記憶部１７に操作命令列ごとに記録されている操作命令に対して、実行が終了したことを示す情報が付与される。
【０１０９】
続いて、終了処理部１６は、操作命令列記憶部１７に記録されている操作命令列の中で、全ての操作命令が終了した操作命令列の有無を判定する（Ｓ１４２）。全ての操作命令が終了した操作命令列が有る場合（Ｓ１４２でＹｅｓ）、終了処理部１６は、当該操作命令列がｃｏｎｓｉｓｔｅｎｔな操作命令列であるか否かを判定する（Ｓ１４３）。操作命令列がｃｏｎｓｉｓｔｅｎｔであるか否かは、クライアントより指定される。すなわち、図４のステップＳ１０１の操作命令列の受け付け時において、当該操作命令列の属性情報の一つとして、当該操作命令列がｃｏｎｓｉｓｔｅｎｔであるかｅｖｅｎｔｕａｌであるかが指定される。なお、当該属性情報には、例えば、クライアントの識別情報等も含まれる。
【０１１０】
当該操作命令列がｃｏｎｓｉｓｔｅｎｔである場合（Ｓ１４３でＹｅｓ）、終了処理部１６は、当該操作命令列は確定プロトコルに基づいて確定可能か否かを判定する（Ｓ１４４）。この判定は、実質的に当該操作命令の実行結果の出力の可否の判定に相当する。すなわち、ｃｏｎｓｉｓｔｅｎｔな操作命令に関しては確定プロトコルに基づいて実行結果の出力の時期（タイミング）が判定される。
【０１１１】
当該操作命令が確定可能な場合（Ｓ１４４でＹｅｓ）、終了処理部１６は、当該操作命令列の実行結果をクライアントに出力する（Ｓ１４５）。実行結果の出力は、ネットワークを介した返信、表示装置への表示等、様々な形態がある。また、実行結果の内容には、実行の成否を示す情報や、データの参照を要求する操作命令列であればデータ等が含まれる。出力先のクライアントは、操作命令列の属性情報に含まれているクライアントの識別情報に基づいて判断される。当該操作命令列を確定可能でない場合（Ｓ１４４でＮｏ）終了処理部１６は、当該操作命令列の実行結果は出力しない。
【０１１２】
一方、当該操作命令列がｅｖｅｎｔｕａｌである場合（Ｓ１４３でＮｏ）、終了処理部１６は、当該操作命令列の確定の可否を判定することなく、当該操作命令列の実行結果を出力する（Ｓ１４５）。
【０１１３】
続いて、終了処理部１６は、当該操作命令列を操作命令列記憶部１７より削除する（Ｓ１４６）。操作命令列記憶部１７より操作命令列が削除されたことに応じ、確定プロトコル制御部１５は、当該レセプタＲのローカル確定クロックを更新する（Ｓ１４７）。すなわち、現時点において操作命令列記憶部１７に記録されている操作命令列に対する論理クロックの最小値より１を減じた値が新たなローカル確定クロックとされる。
【０１１４】
次に、確定プロトコルについて説明する。上記したように、各レセプタＲは、自らのローカル確定クロックを管理している。確定プロトコルにおいて、各レセプタＲは、それぞれのローカル確定クロックを交換することにより、情報処理システム１の系全体の確定クロック（以下、「グローバル確定クロック」という。）を判定する。なお、グローバル確定クロックは、各レセプタＲが他のローカル確定クロックに関する情報を獲得するタイミングのずれによってレセプタＲごとに値が異なりうる。
【０１１５】
図１２は、確定プロトコルのシーケンス図の一例である。同図では、レセプタＲａ及びレセプタＲｂのそれぞれのローカル確定クロック及びグローバル確定クロックについて、時間の経過に応じた値の遷移が示されている。同図の初期状態では、レセプタＲａ及びレセプタＲｂは、相互のローカル確定プロトコルを知らないこととする。
【０１１６】
例えば、ステップＳ２０１において、レセプタＲｂの確定プロトコル制御部１５は、レセプタＲａのローカル確定クロックと、レセプタＲｂのローカル確定クロックとを含むローカル確定クロックの一覧（以下、「論理クロックリスト」という。）をレセプタＲａに送信する。なお、｛Ａ：０，Ｂ：２｝という表記は、レセプタＲａのローカル確定クロック（Ａ）の値は「０」であり、レセプタＲｂのローカル確定クロック（Ｂ）の値は「２」であることを示す。レセプタＲａのローカル確定クロックの値に「０」が指定されているのは、レセプタＲｂはレセプタＲａのローカル確定クロックの値を知らないからである。したがって、「０」以外の値（例えば、−１）等が指定されていてよい。
【０１１７】
レセプタＲａの確定プロトコル制御部１５は、論理クロックリストを受信すると、レセプタＲａの現在のローカル確定クロックと、当該論理クロックリストに含まれているレセプタＲｂのローカル確定クロックとに基づいて、グローバル確定クロックを求める（Ｓ２０２）。具体的には、論理クロックリストに含まれているローカル確定クロックの最小値がグローバル確定クロックとされる。ステップＳ２０２においてレセプタＲａのローカル確定クロックは「５」である。したがって、「５」と「２」との最小値である「２」がグローバル確定クロックとされる。
【０１１８】
なお、各レセプタＲのローカル確定クロックは、操作命令列の受信時や、操作命令列の終了時等、論理クロックリストの交換とは非同期に更新される。
【０１１９】
続いて、レセプタＲａの確定プロトコル制御部１５は、受信した論理クロックリストに対して自らのローカル確定クロックの値を更新した論理クロックリスト｛Ａ：５、Ｂ：２｝をレセプタＲｂに送信する（Ｓ２０３）。
【０１２０】
レセプタＲｂの確定プロトコル制御部１５は、論理クロックリストを受信すると、レセプタＲａのローカル確定クロック「５」と、レセプタＲｂの現在のローカル確定クロック「７」とに基づいて、グローバル確定クロックは「５」であると判定する（Ｓ２０４）。続いて、レセプタＲｂの確定プロトコル制御部１５は、受信した論理クロックリストに対して自らのローカル確定クロックの値を更新した論理クロックリスト｛Ａ：５、Ｂ：７｝をレセプタＲａに送信する（Ｓ２０５）。
【０１２１】
レセプタＲａの確定プロトコル制御部１５は、論理クロックリストを受信すると、レセプタＲａの現在のローカル確定クロック「９」と、レセプタＲｂのローカル確定クロック「７」とに基づいて、グローバル確定クロックは「７」であると判定する（Ｓ２０６）。続いて、レセプタＲａの確定プロトコル制御部１５は、受信した論理クロックリストに対して、自らのローカル確定クロックの値を更新した論理クロックリスト｛Ａ：９、Ｂ：７｝をレセプタＲａに送信する（Ｓ２０７）。
【０１２２】
ステップＳ２０８以降も、同様の手順によってグローバル確定クロックが更新される。また、図１２では、便宜上、二つのレセプタＲ間で論理クロックリストがやり取りされる例について説明したが、レセプタＲが３つ以上有る場合、論理クロックリストは、３つ以上の要素（ローカル確定クロック）を含み、当該レセプタＲ間を一筆書きの経路で流通（周回）する。この場合、３つ以上のローカル確定クロックの最小値がグローバル確定クロックとされる。また、論理クロックリストは、コンテナＣ間も流通する。但し、コンテナＣにおいては、論理クロックリストの更新は行われない。
【０１２３】
すなわち、論理クロックリストは、レセプタＲ及びコンテナＣ間を一筆書きの経路で流通し、各レセプタＲによって更新される。
【０１２４】
論理クロックリストを受信したコンテナＣの確定処理部２４は、論理クロックリストに基づいてグローバル確定クロックを判定する。続いて、当該確定処理部２４は、グローバル確定クロック以下の論理クロックに係る操作命令列に属する操作命令を、操作命令実行履歴記憶部２５より削除する。更に、当該確定処理部２４は、削除した操作命令の中で末尾の操作命令のタイムスタンプ及び実行結果を確定状態記憶部２６に記録する。
【０１２５】
レセプタＲにおいて、グローバル確定クロックは、ｃｏｎｓｉｓｉｔｅｎｔな操作命令列が確定可能か否かの判定（図１１のステップＳ１４４）に用いられる。すなわち、グローバル確定クロックの値が当該操作命令の「論理クロック−１」であれば、当該操作命令は確定可能であると判定される。一方、グローバル確定クロックの値が当該操作命令の「論理クロック−１」未満であれば、当該操作命令は、確定不可能であると判定される。
【０１２６】
上述したように、本実施の形態では、分散して管理されているデータに関する操作命令列について、排他制御や一元的な制御を行わない。また、操作命令列に含まれる各操作命令は投機的に実行される。したがって、操作命令列間の並列性をより向上させることができ、ひいては操作命令列の実行処理の高速化を図ることができる。
【０１２７】
また、各操作命令列に含まれる操作命令には、操作命令列ごとに一意な論理クロックを含むタイムスタンプが付与され、斯かるタイムスタンプに基づいて操作命令の実行順が制御される。また、コンテナＣに対する操作命令の到着順が正しくない場合には、少なくとも正しくない部分について再実行が行われる。その結果、例えば、図１３に示されるような事態の発生は適切に防止される。
【０１２８】
図１３は、一つの操作命令列に他の操作命令列が割り込む例を示す図である。同図では、操作命令列Ｔ３に含まれる二つの操作命令（ｍｕｌ（Ｘ，５）、ａｄｄ（Ｘ，２））の間に、操作命令列Ｔ４が割り込んでいる例が示されている。本実施の形態では、ａｄｄ（Ｘ，２）がコンテナＣｘに受信された際に、論理クロックを含むタイムスタンプによるソートによって操作命令列Ｔ３及びＴ４は区別されて実行される。したがって、このような事態の発生は防止される。
【０１２９】
また、各操作命令列に付与されるタイムスタンプには、一つの操作命令列内における操作命令の実行順を示す操作命令番号が含まれ、斯かるタイムスタンプに基づいて実行順が制御される。また、コンテナＣに対する操作命令の到着順が正しくない場合には、少なくとも正しくない部分について再実行が行われる。その結果、図１４に示されるような事態の発生は適切に防止される。
【０１３０】
図１４は、一つの操作命令列内の操作命令の実行順が逆転してしまう例を示す図である。同図では、操作命令列Ｔ３に含まれる二つの操作命令の実行順が逆転してしまっている例が示されている。本実施の形態では、コンテナＣｘにおいて、ｍｕｌ（Ｘ，５）が受信された際に、操作命令番号を含むタイムスタンプに基づくソート順で各操作命令が実行されるため、このような事態の発生は防止される。
【０１３１】
また、コールバックにより、依存元と依存先との順序関係も適切に確保される。したがって、依存先の操作命令の投機的な実行による実行結果の不正を是正することができる。例えば、図１５に示されるような状態が一時的に発生したとしても、コールバックにより正しい順序で操作命令を再実行することにより、当該状態を是正することができる。
【０１３２】
図１５は、依存先の操作命令の投機的な実行により実行結果が不正となる例を示す図である。同図では、操作命令列Ｔ５において、最初に実行されるべきｓｅｔ（Ｙ，１０）が実行される前に、ａ＝ｇｅｔ（Ｙ）が実行され、ｇｅｔ（Ｙ）に対してａを介して依存するａｄｄ（Ｘ，ａ）が実行されることにより、実行結果が不正となる例が示されている。本実施の形態では、一時的のこのような状態が発生したとしても、コンテナＣｙにおいてｓｅｔ（Ｙ，１０）が受信された際に、ａ＝ｇｅｔ（Ｙ）が再実行され、当該再実行に応じてコールバックが機能する。その結果、ａに依存するａｄｄ（Ｘ，ａ）を、正しいａの値によって再実行することができる。
【０１３３】
上記の効果により、本実施の形態では、操作命令列の実行に関して、結果整合性（Ｅｖｅｎｔｕａｌ  Ｃｏｎｓｉｓｔｅｎｃｙ）を確保することができる。
【０１３４】
また、確定プロトコルを導入することにより、ｃｏｎｓｉｓｉｔｅｎｔな操作命令列に関して、確定のタイミングを検知することができる。なお、ｃｏｎｓｉｓｉｔｅｎｔな操作命令列が要求されないシステム環境においては、確定プロトコルは必ずしも必要ではない。確定プロトコルが導入されなくても、結果整合性は確保されるからである。
【０１３５】
なお、本実施の形態では、便宜上、各コンテナＣは一つのデータを保持する例について説明したが、一つのコンテナＣに２以上のデータが保持されてもよい。この場合、操作命令実行履歴記憶部２５は、データごとに実装されればよい。
【０１３６】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【０１３７】
以上の説明に関し、更に以下の項を開示する。
（付記１）
一以上のデータに関して連続して実行される一以上の操作命令を含む処理単位の実行要求を受け付ける一以上の受付ノードと、前記操作命令に基づいて操作されるデータを保持する一以上の保持ノードをと有する情報処理システムであって、
前記受付ノードは、
前記処理単位間の第一の順序関係を示す第一の順序情報を、前記処理単位ごとに当該処理単位に含まれるぞれぞれの前記操作命令に付与する順序情報付与手段と、
前記操作命令を前記保持ノードに送信する操作命令送信手段とを有し、
前記保持ノードは、
前記操作命令の受信に応じて、当該保持ノードが保持するデータに関する前記操作命令を実行する操作命令実行手段を有し、
前記操作命令実行手段は、既に実行した一以上の第一の操作命令よりも前記第一の順序関係が前であることを示す前記第一の順序情報が付与された第二の操作命令が受信された場合は、前記第二の操作命令の実行後に前記第一の操作命令を再実行する情報処理システム。
（付記２）
前記順序情報付与手段は、同一の前記処理単位に含まれる前記操作命令ごとに、当該処理単位内における順序を示す第二の順序情報を更に付与し、
前記操作命令実行手段は、既に実行した一以上の第三の操作命令よりも前記第二の順序関係が前であることを示す前記第二の順序情報が付与された第四の操作命令が受信された場合は、前記第四の操作命令の実行後に前記第三の操作命令を再実行する付記１記載の情報処理システム。
（付記３）
前記受付ノードは、
前記処理単位内において他の前記操作命令の実行結果に依存する前記操作命令が有る場合に、当該他の操作命令が再実行されたことを通知させるための通知命令を当該他の操作命令に関連付ける通知命令付与手段を有し、
第一の前記保持ノードの前記操作命令実行手段は、前記通知命令に関連付けられている前記操作命令の再実行に応じ、当該操作命令が再実行されたことを当該操作命令の実行結果に依存する前記操作命令の操作対象のデータに対応する第二の前記保持ノードに通知し、
前記第二の保持ノードは、前記通知命令に関連付けられている前記操作命令を前記第一の保持ノードに実行させ、当該操作命令の実行結果を用いて当該操作命令の実行結果に依存する前記操作命令を再実行する付記１又は２記載の情報処理システム。
（付記４）
前記操作命令実行手段は、前記通知命令に関連付けられている前記操作命令が再実行された場合に、当該操作命令の操作対象のデータの当該再実行後の状態が当該再実行前の状態と異なるときに、当該操作命令が再実行されたことを通知する付記３記載の情報処理システム。
（付記５）
前記操作命令実行手段は、前記操作命令の実行に応じ、当該操作命令の実行通知を当該操作命令に係る前記受付ノードに通知し、
前記受付ノードは、
前記実行通知に基づいて、前記操作命令列に含まれる全ての前記操作命令の終了を判定し、当該受付ノードが受け付けた前記操作命令列の中で全ての前記操作命令が終了していない前記操作命令列に付与されている前記第一の識別情報に基づいて、全ての前記操作命令が終了した前記操作命令列の実行結果を出力する時期を判定する終了処理手段とを有する付記１乃至４いずれか一項記載の情報処理システム。
（付記６）
一以上のデータに関して連続して実行される一以上の操作命令を含む処理単位の実行要求を受け付ける一以上の受付ノードと、前記操作命令に基づいて操作されるデータを保持する一以上の保持ノードをと有する情報処理システムにおける情報処理方法であって、
前記受付ノードは、
前記処理単位間の第一の順序関係を示す第一の順序情報を、前記処理単位ごとに当該処理単位に含まれるぞれぞれの前記操作命令に付与する順序情報付与手順と、
前記操作命令を前記保持ノードに送信する操作命令送信手順とを実行し、
前記保持ノードは、
前記操作命令の受信に応じて、当該保持ノードが保持するデータに関する前記操作命令を実行する操作命令実行手順を実行し、
前記操作命令実行手順は、既に実行した一以上の第一の操作命令よりも前記第一の順序関係が前であることを示す前記第一の順序情報が付与された第二の操作命令が受信された場合は、前記第二の操作命令の実行後に前記第一の操作命令を再実行する情報処理方法。
（付記７）
前記順序情報付与手順は、同一の前記処理単位に含まれる前記操作命令ごとに、当該処理単位内における順序を示す第二の順序情報を更に付与し、
前記操作命令実行手順は、既に実行した一以上の第三の操作命令よりも前記第二の順序関係が前であることを示す前記第二の順序情報が付与された第四の操作命令が受信された場合は、前記第四の操作命令の実行後に前記第三の操作命令を再実行する付記６記載の情報処理方法。
（付記８）
前記受付ノードは、
前記処理単位内において他の前記操作命令の実行結果に依存する前記操作命令が有る場合に、当該他の操作命令が再実行されたことを通知させるための通知命令を当該他の操作命令に関連付ける通知命令付与手順を実行し、
第一の前記保持ノードの前記操作命令実行手順は、前記通知命令に関連付けられている前記操作命令の再実行に応じ、当該操作命令が再実行されたことを当該操作命令の実行結果に依存する前記操作命令の操作対象のデータに対応する第二の前記保持ノードに通知し、
前記第二の保持ノードは、前記通知命令に関連付けられている前記操作命令を前記第一の保持ノードに実行させ、当該操作命令の実行結果を用いて当該操作命令の実行結果に依存する前記操作命令を再実行する付記６又は７記載の情報処理方法。
（付記９）
前記操作命令実行手順は、前記通知命令に関連付けられている前記操作命令が再実行された場合に、当該操作命令の操作対象のデータの当該再実行後の状態が当該再実行前の状態と異なるときに、当該操作命令が再実行されたことを通知する付記８記載の情報処理方法。
（付記１０）
前記操作命令実行手順は、前記操作命令の実行に応じ、当該操作命令の実行通知を当該操作命令に係る前記受付ノードに通知し、
前記受付ノードは、
前記実行通知に基づいて、前記操作命令列に含まれる全ての前記操作命令の終了を判定し、当該受付ノードが受け付けた前記操作命令列の中で全ての前記操作命令が終了していない前記操作命令列に付与されている前記第一の識別情報に基づいて、全ての前記操作命令が終了した前記操作命令列の実行結果を出力する時期を判定する終了処理手順とを実行する付記６乃至９いずれか一項記載の情報処理方法。
【符号の説明】
【０１３８】
１            情報処理システム
１１        操作命令列受付部
１２        順序情報付与部
１３        コールバック付与部
１４        操作命令送信部
１５        確定プロトコル制御部
１６        終了処理部
１７        操作命令列記憶部
２１        操作命令受信部
２２        操作命令ソート部
２３        操作命令実行部
２４        確定処理部
２５        操作命令実行履歴記憶部
２６        確定状態記憶部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
Ｂ            バス
Ｃ            コンテナ
Ｒ            レセプタ
【図１】
0005531760.tif 000002
【図２】
0005531760.tif 000003
【図３】
0005531760.tif 000004
【図４】
0005531760.tif 000005
【図５】
0005531760.tif 000006
【図６】
0005531760.tif 000007
【図７】
0005531760.tif 000008
【図８】
0005531760.tif 000009
【図９】
0005531760.tif 000010
【図１０】
0005531760.tif 000011
【図１１】
0005531760.tif 000012
【図１２】
0005531760.tif 000013
【図１３】
0005531760.tif 000014
【図１４】
0005531760.tif 000015
【図１５】
0005531760.tif 000016