(57)【特許請求の範囲】
【請求項１】
コンピュータに、
特定のデータに対して実行すべき第１のオペレーションの内容を表す内容情報及び当該第１のオペレーションの内容情報の受信時刻である第１の受信時刻を取得し、
前記特定のデータに対して既に実行したオペレーションの内容情報と、当該オペレーションの内容情報の受信時刻とを対応付けて格納するデータ格納部から、前記第１の受信時刻より後の受信時刻に対応付けられている第２のオペレーションの内容情報を特定し、
取得された前記第１のオペレーションの内容情報及び特定された前記第２のオペレーションの内容情報に基づき、前記第１のオペレーション及び前記第２のオペレーションを、受信時刻が早い順に前記特定のデータに対して実行する、
処理を実行させるプログラム。
【請求項２】
前記第１のオペレーションの内容情報の受信時刻が、前記データ格納部に格納されている前記受信時刻のいずれよりも後である場合、前記特定のデータに対して、取得された前記第１のオペレーションの内容情報に基づき前記第１のオペレーションを実行する
処理をさらに実行させる請求項１記載のプログラム。
【請求項３】
前記データ格納部には、アプリケーション・プログラムの通知リストがさらに格納されており、
前記第１のオペレーション及び前記第２のオペレーションを受信時刻が早い順に実行した場合には、前記データ格納部に格納されている前記アプリケーション・プログラムの通知リストにより特定されるアプリケーション・プログラムに実行結果を通知するためのデータを生成する
処理をさらに実行させる請求項１又は２記載のプログラム。
【請求項４】
前記取得する処理において、
前記第１のオペレーションの内容情報をクライアント端末から受信し、
前記第１のオペレーションの内容情報の受信時刻を取得する、
請求項１乃至３のいずれか１つ記載のプログラム。
【請求項５】
前記取得する処理において、
前記コンピュータとは異なる他のコンピュータから、前記第１のオペレーションの内容情報及び当該第１のオペレーションの内容情報の受信時刻を受信する
請求項１乃至３のいずれか１つ記載のプログラム。
【請求項６】
前記第２のオペレーションは、前記第１のオペレーションを実行した後の前記特定のデータに対して実行すべきオペレーションである
請求項１乃至５のいずれか１つ記載のプログラム。
【請求項７】
特定のデータに対して既に実行したオペレーションの内容を表す内容情報と、当該オペレーションの内容情報の受信時刻とを対応付けて格納するデータ格納部と、
前記特定のデータに対して実行すべき第１のオペレーションの内容情報及び当該第１のオペレーションの内容情報の受信時刻である第１の受信時刻を取得する取得部と、
前記データ格納部から、前記第１の受信時刻より後の受信時刻に対応付けられている第２のオペレーションの内容情報を特定し、取得された前記第１のオペレーションの内容情報及び特定された前記第２のオペレーションの内容情報に基づき、前記第１のオペレーション及び前記第２のオペレーションを、受信時刻が早い順に前記特定のデータに対して実行する再実行部と、
を有する情報処理装置。
【請求項８】
コンピュータが、
特定のデータに対して実行すべき第１のオペレーションの内容を表す内容情報及び当該第１のオペレーションの内容情報の受信時刻である第１の受信時刻を取得し、
前記特定のデータに対して既に実行したオペレーションの内容情報と、当該オペレーションの内容情報の受信時刻とを対応付けて格納するデータ格納部から、前記第１の受信時刻より後の受信時刻に対応付けられている第２のオペレーションの内容情報を特定し、
取得された前記第１のオペレーションの内容情報及び特定された前記第２のオペレーションの内容情報に基づき、前記第１のオペレーション及び前記第２のオペレーションを、受信時刻が早い順に前記特定のデータに対して実行する、
処理を実行する情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データストアに関する。大規模分散データストアにおけるデータに対してオペレーションを実行する際に利用することもできる。
【背景技術】
【０００２】
ネットワークを介して接続された複数のノードがデータを分散して保持することにより、可用性等の向上を実現するシステムが存在する。このようなシステムは、分散データストア（Distributed Data Store）と呼ばれることがある。
【０００３】
図１は、分散データストアのシステム構成の一例を示したものである。図１を用いて、分散データストアが分散トランザクションを受理した際に行われる処理の一例を説明する。例えばノードＢにおける分散フレームワーク１２が、オペレーションのデータを含む分散トランザクションの実行要求をクライアント端末等から受信する。ここでは、ｇｅｔ（Ａ１）というオペレーション（すなわち、データＡ１を取得するというオペレーション）のデータを受信したとする。そして、ノードＢにおける分散フレームワーク１２は、分散ハッシュテーブル（ＤＨＴ：Distributed Hash Table）等を用いて、オペレーションの実行対象となるデータを保持するノードを特定する。分散トランザクションの実行要求に複数のオペレーションのデータが含まれる場合には、複数のノードが特定されることがあるが、ここではノードＡだけが特定されたとする。すると、ノードＢの分散フレームワーク１２は、オペレーションのデータをノードＡの分散フレームワーク１１に回送する。一方、ノードＡの分散フレームワーク１１は、ノードＢからオペレーションのデータを受信すると、当該オペレーションを実行する（すなわち、データＡ１の値を取得する）。さらに、ノードＡの分散フレームワーク１１は、ノードＢにデータＡ１の値を送信する。そして、ノードＢの分散フレームワーク１２は、ノードＡからデータＡ１の値を受信すると、クライアント端末に送信する。
【０００４】
このような分散データストアでは、複数のノードのうちのいずれもが分散トランザクションの実行要求を受信する可能性があり、実行要求を受信した時点ではトランザクションのシリアライズ（順序付け）は行わず、タイムスタンプ等を用いて後に解決することが行われる。
【０００５】
そして、このような分散データストアでは、分散トランザクションの実行要求を受信したノード（以下、レセプタと呼ぶ）とオペレーションの実行対象となるデータを保持するノード（以下、コンテナと呼ぶ）が必ずしも一致するわけではない。従って、例えばノード間の通信遅延により、コンテナに特定のオペレーションのデータが到着するタイミングが遅れると、本来実行すべき順序とは異なる順序でオペレーションを実行してしまうことがある。また、複数のノードでデータのレプリカを保持するような分散データストアでは、レプリカ間でデータを同期するタイミングが遅れると、同期が行われる前に、本来は同期の後に実行すべきオペレーションを先に実行してしまうことがある。
【０００６】
そして、オペレーションを実行する順序と本来の正しい実行順序が変わってしまうと、以下のような問題が生じる。例えば、あるデータに対して、１番目のオペレーションとして２を設定し、２番目のオペレーションとして３を加え、３番目のオペレーションとして４をかける必要があるとする。ここで、オペレーションが本来の順序どおりに実行された場合には、実行結果は２０になる。しかし、２番目に実行すべきオペレーションと３番目に実行すべきオペレーションが逆になった場合には、実行結果は１１になってしまう。すなわち、分散データストアにおけるデータに対して、実行結果が実行順序に依存するオペレーションを実行すると、正しい実行結果が得られないことがある。従って、分散データストアにおけるデータに対しては、実行結果が実行順序に依存しないオペレーション（例えば、即値を設定するオペレーションやデータの値を取得するためのオペレーション）でなければ適用が難しいという問題がある。
【０００７】
なお、上で述べたような分散データストアのように、複数のノードが分散して処理を行うシステムにおいては、ＣＡＰ定理（CAP Theorem）という定理が成立すると言われている。ＣＡＰ定理とは、Consistency（データの一貫性）と、Availability（システムの可用性）と、Tolerance to network Partitions（ネットワーク分断への耐性）とを全て同時に実現することはできないという定理である。上で述べたような分散データストアにおいては、「システムの可用性」及び「ネットワーク分断への耐性」は優先して実現すべき性質であるため、「データの一貫性」についての厳密性を緩めた形でシステムが構築されることがある。その結果、ユーザには一時的に更新前のデータが提示されるといった事態が生じてしまうことがあるが、例えば大規模掲示板の書き込み内容やショッピングサイトの商品説明ページなどの場合、一時的にそのような事態が生じても問題はないことが多い。このような、ある時点ではデータの整合が取れていないかもしれないが、最終的に整合が取れていれば良いという考え方は、結果整合性（Eventual Consistency）と呼ばれることがある。
【０００８】
従来、分散データストアに関する技術として、以下のような技術が存在する。具体的には、複数のノードでデータのレプリカを保持し、バックグラウンドでデータへの変更をレプリカに反映させていくことにより、可用性を確保する。データに矛盾（conflict）が生じた場合には、アプリケーション側において、データの読み出し時に矛盾を解消するための処理を行う。
【０００９】
しかし、上で述べたようなオペレーションの実行順序の誤りを分散データストア側において解消し、実行順序に依存性のあるオペレーション等を実行可能にするための技術は存在しない。
【先行技術文献】
【特許文献】
【００１０】
【非特許文献１】G. DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store", Proc. SOSP 2007
【発明の概要】
【発明が解決しようとする課題】
【００１１】
従って、１つの側面では、分散データストアにおいて、実行結果が実行順序に依存するオペレーションを適切に処理するための技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本情報処理方法は、特定のデータに対して実行すべき第１のオペレーションの内容を表す内容情報及び当該第１のオペレーションの内容情報の受信時刻である第１の受信時刻を取得し、特定のデータに対して既に実行したオペレーションの内容情報と、当該第２のオペレーションの内容情報の受信時刻とを対応付けて格納するデータ格納部から、第１の受信時刻より後の受信時刻に対応付けられている第２のオペレーションの内容情報を特定し、取得された第１のオペレーションの内容情報及び特定された第２のオペレーションの内容情報に基づき、第１のオペレーション及び第２のオペレーションを、受信時刻が早い順に特定のデータに対して実行する処理を含む。
【発明の効果】
【００１３】
分散データストアにおいて、実行結果が実行順序に依存するオペレーションを適切に処理することができるようになる。
【図面の簡単な説明】
【００１４】
【図１】図１は、分散データストアの一例を示す図である。
【図２】図２は、第１の実施の形態に係る情報処理装置の機能ブロック図である。
【図３】図３は、第１の実施の形態に係る処理フローを示す図である。
【図４】図４は、第２の実施の形態に係るシステムの構成図である。
【図５】図５は、第２の実施の形態に係るノード装置の機能ブロック図である。
【図６】図６は、ローカルデータ格納部に格納されるオペレーション履歴データの一例を示す図である。
【図７】図７は、ローカルデータ格納部に格納されるアプリケーション通知リストの一例を示す図である。
【図８】図８は、レセプタとなるノードの処理フローを示す図である。
【図９】図９は、レセプタとなるノードの処理フローを示す図である。
【図１０】図１０は、コンテナとなるノードの処理フローを示す図である。
【図１１】図１１は、コンテナとなるノードの処理フローを示す図である。
【図１２】図１２は、オペレーション履歴データについて説明するための図である。
【図１３】図１３は、再実行の方法について説明するための図である。
【図１４】図１４は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１５】
［実施の形態１］
第１の実施の形態に係る情報処理装置の機能ブロック図を図２に示す。第１の実施の形態に係る情報処理装置は、取得部１０１１と、再実行部１０１３と、データ格納部１０１５とを有する。取得部１０１１は、オペレーションのデータ及び当該オペレーションのデータの受信時刻を取得する処理を行う。再実行部１０１３は、データ格納部１０１５に格納されているデータを用いて処理を行う。データ格納部１０１５には、特定のデータに対して既に実行したオペレーションのデータと当該オペレーションのデータの受信時刻とが特定のデータに対応付けて格納されている。なお、図１に示した情報処理装置を複数用いて処理システムが構築される。
【００１６】
次に、図２に示した情報処理装置の処理内容を図３を用いて説明する。まず、取得部１０１１は、特定のデータに対して実行すべき第１のオペレーションのデータ及び当該第１のオペレーションのデータの受信時刻を取得する（ステップＳ１００１）。取得部１０１１による処理の結果は、再実行部１０１３に出力される。そして、再実行部１０１３は、データ格納部１０１５において特定のデータに対応付けて格納されている受信時刻のいずれより、第１のオペレーションのデータの受信時刻が後であるか判断する（ステップＳ１００３）。また、再実行部１０１３は、第１のオペレーションのデータの受信時刻がデータ格納部１０１５に特定のデータに対応付けて格納されている受信時刻のいずれよりも後ではないと判断された場合、第２のオペレーション及び第１のオペレーションを、受信時刻が早い順に実行する（ステップＳ１００５）。
【００１７】
以上のような処理を実施することにより、第１及び第２のオペレーションの実行結果が実行順序に依存する場合であっても正しい実行結果を得ることができるようになる。
【００１８】
［実施の形態２］
次に、第２の実施の形態について説明する。図４に、第２の実施の形態に係るシステムの構成図を示す。例えばインターネットであるネットワーク１には、ノード装置３１乃至３３と、ユーザ端末５と、アプリケーション・プログラム７１を含むユーザ端末７とが接続されている。ノード装置３１乃至３３はネットワーク９を介して互いに接続されており、ノード装置３１乃至３３を含むシステムは、分散データストアを実現する。図４では、ノード装置は３台、ユーザ端末は４台である例を示しているが、数に限定はない。
【００１９】
図５に、ノード装置の機能ブロック図を示す。ノード装置は、通信部３０１と、ロケータ部３０２と、データ管理部３０３と、ローカルデータ格納部３０４とを含む。
【００２０】
通信部３０１は、ユーザ端末５から分散トランザクションの実行要求を受信し、当該実行要求に含まれるオペレーションの実行対象となるデータを保持するノード装置に対してオペレーションのデータを回送する処理等を実施する。なお、通信部３０１は、実行要求に含まれるオペレーションの実行対象となるデータを自ノード装置が保持している場合には、データ管理部３０３に対してオペレーションのデータを出力する。ロケータ部３０２は、例えばコンシステント・ハッシング（Consistent Hashing）等によりオペレーションの実行対象となるデータを保持するノードを特定する。データ管理部３０３は、通信部３０１から受け取ったオペレーションのデータに基づき、オペレーションを実行する処理等を行う。また、データ管理部３０３は、ローカルデータ格納部３０４に格納されているデータを管理する。
【００２１】
図６に、ローカルデータ格納部３０４に格納されているオペレーション履歴データの一例を示す。図６の例では、各データに対応付けて、当該データに対して既に実行したオペレーションのデータと、当該オペレーションのデータに対して付与されたタイムスタンプが格納されるようになっている。図６の例では、例えばデータＡに対しては、タイムスタンプ「ｔ＝０」が付与されている「Ｓｅｔ（１）」というオペレーションと、タイムスタンプ「ｔ＝２」が付与されている「Ｍｕｌ（３）」というオペレーションと、タイムスタンプ「ｔ＝３」が付与されている「Ａｄｄ（２）」というオペレーションとが既に実行されたことを示している。
【００２２】
なお、本実施の形態における「実行結果が実行順序に依存するオペレーション」には、更新前の値を用いるオペレーションが含まれる。例えば、更新前の値をｘとし、更新後の値をｙとした場合、ｙ＝１１（即値代入）、ｙ＝ｘ．Ｉｎｃ（）＝ｘ＋１（インクリメント）、ｙ＝ｘ．Ａｄｄ（２）＝ｘ＋２（加算）、ｙ＝ｘ2＋２ｘ＋３、ｙ＝ｓｉｎ（ｘ）等が該当する。その他、デクリメント、減算、乗法及び除法等も該当する。
【００２３】
図７に、ローカルデータ格納部３０４に格納されているアプリケーション通知リストの一例を示す。図７の例では、データ名の列と、アプリケーションの列とが含まれる。
【００２４】
次に、図８乃至図１３を用いて、図４に示したシステムの処理内容について説明する。まず、図８及び図９を用いて、レセプタとなるノード装置において行われる処理について説明する。ここでは、ノード装置３２がレセプタとなる場合を例にして説明する。
【００２５】
まず、ノード装置３２の通信部３０１は、実行すべきオペレーションのデータを含む分散トランザクションの実行要求をユーザ端末５から受信し、メインメモリ等の記憶装置に格納する（図８：ステップＳ１）。
【００２６】
また、ノード装置３２の通信部３０１は、ステップＳ１において受信した分散トランザクションの実行要求に対しタイムスタンプを付与する（ステップＳ３）。例えばＬａｍｐｏｒｔのアルゴリズム等を用いて、ノード装置３１乃至３３の間で予め論理クロック（論理時計）の値を交換しておき、その論理クロックの値をタイムスタンプとして付与する。
【００２７】
そして、ノード装置３２の通信部３０１は、分散トランザクションの実行要求に含まれる未処理の１つ分のオペレーションのデータを特定する（ステップＳ５）。また、ステップＳ５において、ノード装置３２の通信部３０１は、当該オペレーションのデータをノード装置３２のロケータ部３０２に出力する。
【００２８】
一方、ノード装置３２のロケータ部３０２は、通信部３０１から受け取ったオペレーションのデータに含まれる、オペレーションの実行対象となるデータを特定するためのデータに対して例えばコンシステント・ハッシング等を行うことにより、当該オペレーションの実行対象となるデータを保持するノード装置（コンテナ）を特定する（ステップＳ７）。ここでは、ノード装置３１がコンテナとして特定されたとする。さらに、ステップＳ７において、ノード装置３２のロケータ部３０２は、ノード装置３１がコンテナとして特定された旨をノード装置３２の通信部３０１に対して通知する。
【００２９】
そして、ノード装置３２の通信部３０１は、ロケータ部３０２からの通知を受けると、ステップＳ５において特定されたオペレーションのデータと、ステップＳ３において付与されたタイムスタンプとを含むオペレーション実行指示をコンテナであるノード装置３１に回送する（ステップＳ９）。なお、もしステップＳ７においてノード装置３２がコンテナとして特定された場合には、通信部３０１は、ステップＳ５において特定されたオペレーションのデータと、ステップＳ３において付与されたタイムスタンプとを含むオペレーション実行指示をノード装置３２のデータ管理部３０３に通知する。
【００３０】
そして、ノード装置３２の通信部３０１は、全てのオペレーションのデータを処理したか判断する（ステップＳ１１）。全てのオペレーションのデータを処理していない場合（ステップＳ１１：Ｎｏルート）、次のオペレーションのデータについて処理を実施するため、ステップＳ５の処理に戻る。一方、全てのオペレーションのデータを処理した場合（ステップＳ１１：Ｙｅｓルート）、処理は端子Ａを介して図９のステップＳ１３に移行する。
【００３１】
図９を用いて、端子Ａ以降の処理について説明する。その後、ノード装置３２の通信部３０１は、オペレーションの実行結果をコンテナから受信する（ステップＳ１３）。なお、ステップＳ１３においては、ノード装置３２の通信部３０１は、ノード装置３２のデータ管理部３０３からオペレーションの実行結果を取得する場合もある。
【００３２】
そして、ノード装置３２の通信部３０１は、ステップＳ１３において受信したオペレーションの実行結果のデータを集約してトランザクションの実行結果のデータを生成し、ユーザ端末５に送信する（ステップ１５）。オペレーションの実行結果を集約する方法は、トランザクションの種別毎に異なる。
【００３３】
また、ノード装置３２の通信部３０１は、オペレーションの再実行が行われたデータと当該データのデータ名とアプリケーションの通知リストとを含む再実行発生通知をコンテナから受信する（ステップＳ１７）。そして、ノード装置３２の通信部３０１は、オペレーションの再実行が行われたデータと当該データのデータ名とを、アプリケーション通知リストにより特定されるアプリケーション・プログラム７１に通知する（ステップＳ１９）。ステップＳ１９においては、例えば、指定されたＩＰアドレス及びポート番号を用いてメッセージを送信したり、指定されたＷｅｂ ＡＰＩ（Application Programming Interface）を呼び出したり、又は指定された関数をデータサービス用ライブラリ経由でコールバックすることにより行う。また、ステップＳ１９においては、データ名だけを通知するようにしてもよい。なお、コンテナにおいてオペレーションの再実行が行われていない場合には、ステップＳ１７及びＳ１９は実施されない。そして処理を終了する。
【００３４】
以上のような処理を実施することにより、分散トランザクションの実行要求を処理することができるようになる。また、オペレーションの再実行が行われたことを知りたい者等は、自身が操作する端末等に搭載されたアプリケーション・プログラムを介して通知を受けることができるようになる。
【００３５】
次に、図１０乃至図１３を用いて、コンテナとなるノード装置において行われる処理について説明する。ここでは、コンテナがノード装置３１であり、レセプタがノード装置３２である場合を例にして説明する。
【００３６】
まず、ノード装置３１の通信部３０１は、オペレーションのデータ及びタイムスタンプを含むオペレーション実行指示をレセプタであるノード装置３２から受信し（ステップＳ３１）、ノード装置３１のデータ管理部３０３に出力する。
【００３７】
そして、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したオペレーションのデータが、ローカルデータ格納部３０４に格納されているアプリケーション通知リストを更新するためのオペレーションであることを表しているか判断する（ステップＳ３３）。アプリケーション通知リストを更新するためのオペレーションであると判断された場合には（ステップＳ３３：Ｙｅｓルート）、ノード装置３１のデータ管理部３０３は、ローカルデータ格納部３０４に格納されているアプリケーション通知リストの更新を行う（ステップＳ３５）。ステップＳ３５においては、例えば、アプリケーション通知リストに含まれるデータに対して変更、削除又は追加等の処理が行われる。また、ノード装置３１のデータ管理部３０３は、更新の結果を通知するためのデータを生成し、ノード装置３１の通信部３０１に出力する。そして、ノード装置３１の通信部３０１は、更新の結果を通知するためのデータをレセプタであるノード装置３２に送信する（ステップＳ３７）。そして端子Ｃを介して処理を終了する。
【００３８】
一方、アプリケーション通知リストを更新するためのオペレーションではないと判断された場合（ステップＳ３３：Ｎｏルート）、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したオペレーションのデータが、ローカルデータ格納部３０４に格納されているデータの値を取得するためのオペレーション（例えばＧｅｔというオペレーション）であることを表しているかを判断する（ステップＳ３９）。ローカルデータ格納部３０４に格納されているデータの値を取得するためのオペレーションではないと判断された場合（ステップＳ３９：Ｎｏルート）、処理は端子Ｂを介して図１１のステップＳ５１に移行する。
【００３９】
一方、ローカルデータ格納部３０４に格納されているデータの値を取得するためのオペレーションであると判断された場合（ステップＳ３９：Ｙｅｓルート）、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したタイムスタンプ及びローカルデータ格納部３０４においてオペレーションの実行対象となるデータに対応付けて格納されているタイムスタンプに従い、既に実行したオペレーションをタイムスタンプが古い順に再度実行し、オペレーションの実行対象となるデータの値を取得する（ステップＳ４１）。また、ノード装置３１のデータ管理部３０３は、ステップＳ４１において取得したデータの値をレセプタであるノード装置３２に送信する（ステップＳ４３）。そして、処理は端子Ｃを介して終了する。
【００４０】
次に、図１１を用いてステップＳ５１以降の処理について説明する。ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したオペレーションのデータ及びタイムスタンプをローカルデータ格納部３０４に格納されているオペレーション履歴データに追加する（ステップＳ５１）。
【００４１】
ここで、図１２及び図１３を用いて、オペレーション履歴データにデータを追加する方法について説明する。図１２の例は、データＡに関するオペレーション履歴データにデータが追加されていく様子を示している。図１２の例では、最初の段階では、データＡに関するオペレーション履歴データは存在しないが、次の段階において、「Ｓｅｔ（７），ｔ＝０」というデータが格納され、データＡには７が設定されている。さらに次の段階では、「Ａｄｄ（１），ｔ＝２」というデータが追加され、データＡの値は８になっている。さらに次の段階において、「Ｍｕｌ（２），ｔ＝３」というデータが追加され、データＡの値は１６になっている。そして、最後の段階において、「Ｓｕｂ（３），ｔ＝４」というデータが追加され、データＡの値は１３になっている。図１２の例では、３番目の段階から最後の段階までにおいて、新たに追加されたオペレーションに対して付与されているタイムスタンプは、既に履歴として格納されているタイムスタンプのいずれよりも後のものであるため、オペレーションの到着順でそのままオペレーションを実行している。なお、ここでは、ｔの値が大きいほど後に付与されたタイムスタンプであるとする。
【００４２】
一方、図１３は、「ｔ＝４」というタイムスタンプが付与されたオペレーションを実行した後に、「ｔ＝３」というタイムスタンプが付与されたオペレーションが到着した場合の例である。「ｔ＝４」というタイムスタンプが付与された「Ｍｕｌ（３）」というオペレーションを実行した段階では、データＡの値は２４になっている。ここで、「ｔ＝３」というタイムスタンプが付与された「Ａｄｄ（２）」というオペレーションが到着した場合に、そのままこのオペレーションを実行すると、データＡの値は２６になる。しかし、本来のオペレーションの実行順序は、「ｔ＝３」のオペレーションを実行した後に「ｔ＝４」のオペレーションを実行するという順序である。
【００４３】
そこで本実施の形態においては、図１３で述べた例のように本来先に実行すべきオペレーションが後に到着したような場合には、以下のような対応を行う。すなわち、タイムスタンプにより特定される実行順序どおりに並ぶように、オペレーションのデータ及びタイムスタンプをオペレーション履歴データに追加する。さらに、オペレーション履歴データを用いて、データＡに対してオペレーションを再実行する。図１３の例では、このような再実行を行うことにより、データＡには３０という正しい値が設定される。なお、本実施の形態においては、データの値を取得するためのオペレーションのデータは、オペレーション履歴データには追加されない。データの値を取得するためのオペレーションは、データの値には影響を及ぼさないためである。
【００４４】
図１１の説明に戻り、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したタイムスタンプが、ローカルデータ格納部に３０４においてオペレーションの実行対象となるデータに対応付けて格納されているタイムスタンプのいずれよりも後のタイムスタンプ（すなわち、最も新しいタイムスタンプ）であるかを判断する（ステップＳ５３）。
【００４５】
ステップＳ５３において最も新しいタイムスタンプであると判断された場合（ステップＳ５３：Ｙｅｓルート）、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したオペレーションのデータに基づきオペレーションを実行する（ステップＳ５５）。そして、オペレーションの実行結果をレセプタであるノード装置３２に送信する（ステップＳ５７）。
【００４６】
一方、ステップＳ５３において最も新しいタイムスタンプではないと判断された場合（ステップＳ５３：Ｎｏルート）、ノード装置３１のデータ管理部３０３は、ステップＳ３１において受信したタイムスタンプ及びローカルデータ格納部３０４においてオペレーションの実行対象となるデータに対応付けて格納されているタイムスタンプにより特定される実行順序に従い、既に実行したオペレーションをタイムスタンプが古い順に再度実行し、さらにステップＳ３１において受信したオペレーションのデータに係るオペレーションを実行する（ステップＳ５９）。そして、ノード装置３１のデータ管理部３０３は、再実行が行われたデータと当該データのデータ名及びアプリケーション通知リストを含む再実行発生通知を生成し、レセプタであるノード装置３２に送信する（ステップＳ６１）。そして、処理を終了する。
【００４７】
以上のような処理を実施することにより、分散データストアにおいて、データの値を取得するためのオペレーションのみならず、実行結果が実行順序に依存するオペレーションを適切に処理できるようになる。
【００４８】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、上で説明した情報処理装置及びノード装置の機能ブロック図は必ずしも実際のプログラムモジュール構成に対応するものではない。
【００４９】
また、上で説明した各テーブルの構成は一例であって、必ずしも上記のような構成でなければならないわけではない。さらに、処理フローにおいても、処理結果が変わらなければ処理の順番を入れ替えることも可能である。さらに、並列に実行させるようにしても良い。
【００５０】
なお、上で述べた例では、複数のノード装置が稼働するような例を示しているが、例えば単体の装置に複数のプロセスを起動させて上で述べたような処理を実行させるようにしてもよい。
【００５１】
なお、上で述べたノード装置３１乃至３３は、コンピュータ装置によって実現することもできる。例えば、図１４に示すように、メモリ２５０１とプロセッサ（ＣＰＵ２５０３）とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とを備え、これらがバス２５１９を介して接続されたコンピュータを用いてもよい。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５等の記憶部に格納しておき、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出して利用することもできる。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行ってもよい。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納してもよい。実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされてもよい。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。なお、図２のデータ格納部１０１５は、図１４におけるメモリ２５０１やＨＤＤ２５０５等として実現してもよい。図５のローカルデータ格納部３０４についても同様である。図２の取得部１０１１及び再実行部１０１３は、プロセッサ２５０３及びプログラムの組み合わせ、すなわち、プロセッサ２５０３がプログラムを実行することにより実現してもよい。より具体的には、プロセッサ２５０３は、ＨＤＤ２５０５又はメモリ２５０１に記憶されたプログラムに従った動作を行うことで、上で述べたような処理部として機能してもよい。図５の通信部３０１、ロケータ部３０２及びデータ管理部３０３についても同様である。
【００５２】
以上述べた本技術の実施の形態をまとめると以下のようになる。
【００５３】
本情報処理方法は、複数のノード装置を含む処理システムにおける複数のノード装置のうちのいずれかのノード装置により実行される。そして、本情報処理方法は、特定のデータに対して実行すべき第１のオペレーションのデータ（例えば演算内容を表すデータであり、さらに具体的には、例えば加算を表す「Ａｄｄ」というデータ及び加算する値）及び当該第１のオペレーションのデータの受信時刻を取得する取得ステップと、特定のデータに対して既に実行した第２のオペレーションのデータと当該第２のオペレーションのデータの受信時刻とを特定のデータに対応付けて格納するデータ格納部において特定のデータに対応付けて格納されている受信時刻のいずれより、第１のオペレーションのデータの受信時刻が後であるか判断するステップと、第１のオペレーションのデータの受信時刻がデータ格納部に特定のデータに対応付けて格納されている受信時刻のいずれよりも後ではないと判断された場合、第２のオペレーション及び第１のオペレーションを、受信時刻が早い順に実行する再実行ステップとを含む。
【００５４】
このようにすれば、実行結果が実行順序に依存するオペレーションを適切に処理できるようになる。
【００５５】
また、第１のオペレーションのデータの受信時刻がデータ格納部に特定のデータに対応付けて格納されている受信時刻のいずれよりも後であると判断された場合、特定のデータに対して第１のオペレーションを実行するステップをさらに含むようにしてもよい。第１のオペレーションが第２のオペレーションよりも後に実行すべきオペレーションである場合には、第１のオペレーションだけを実行すれば正しい実行結果を得ることができるからである。
【００５６】
また、上で述べたデータ格納部には、特定のデータに対応付けてアプリケーション・プログラムの通知リストがさらに格納されるようにしてもよい。そして、再実行ステップが実行された場合には、データ格納部に特定のデータに対応付けて格納されているアプリケーション・プログラムの通知リストにより特定されるアプリケーション・プログラムに再実行ステップの実行結果を通知するためのデータを生成するステップをさらに含むようにしてもよい。これにより、特定のデータに対してオペレーションの再実行が行われたことを知りたい者等は、自身が操作する端末等に搭載されたアプリケーション・プログラムを介して通知を受けることができるようになる。
【００５７】
また、上で述べた取得ステップが、第１のオペレーションのデータをクライアント端末から受信するステップと、第１のオペレーションのデータの受信時刻を取得するステップとを含むようにしてもよい。これにより、オペレーションのデータをクライアント端末から直接受信するような場合であっても対処可能になる。
【００５８】
また、上で述べた取得ステップが、複数のノード装置のうちの他のノード装置から、第１のオペレーションのデータ及び当該第１のオペレーションのデータの受信時刻を受信するステップを含むようにしてもよい。これにより、オペレーションのデータのレセプタとなるノードとコンテナとなるノードが異なる場合であっても対処可能になる。
【００５９】
なお、上記方法による処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００６０】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００６１】
（付記１）
複数のノード装置を含む処理システムにおける前記複数のノード装置のうちのいずれかのノード装置に実行させるためのプログラムであって、
特定のデータに対して実行すべき第１のオペレーションのデータ及び当該第１のオペレーションのデータの受信時刻を取得する取得ステップと、
前記特定のデータに対して既に実行した第２のオペレーションのデータと当該第２のオペレーションのデータの受信時刻とを前記特定のデータに対応付けて格納するデータ格納部において前記特定のデータに対応付けて格納されている前記受信時刻のいずれより、前記第１のオペレーションのデータの受信時刻が後であるか判断するステップと、
前記第１のオペレーションのデータの受信時刻が前記データ格納部に前記特定のデータに対応付けて格納されている前記受信時刻のいずれよりも後ではないと判断された場合、前記第２のオペレーション及び前記第１のオペレーションを、受信時刻が早い順に実行する再実行ステップと、
を実行させるためのプログラム。
【００６２】
（付記２）
前記第１のオペレーションのデータの受信時刻が前記データ格納部に前記特定のデータに対応付けて格納されている前記受信時刻のいずれよりも後であると判断された場合、前記特定のデータに対して前記第１のオペレーションを実行するステップ
をさらに実行させるための付記１記載のプログラム。
【００６３】
（付記３）
前記データ格納部には、前記特定のデータに対応付けてアプリケーション・プログラムの通知リストがさらに格納されており、
前記再実行ステップが実行された場合には、前記データ格納部に前記特定のデータに対応付けて格納されている前記アプリケーション・プログラムの通知リストにより特定されるアプリケーション・プログラムに前記再実行ステップの実行結果を通知するためのデータを生成するステップ
をさらに実行させるための付記１又は２記載のプログラム。
【００６４】
（付記４）
前記取得ステップが、
前記第１のオペレーションのデータをクライアント端末から受信するステップと、
前記第１のオペレーションのデータの受信時刻を取得するステップと、
を含む付記１乃至３のいずれか１つ記載のプログラム。
【００６５】
（付記５）
前記取得ステップが、
前記複数のノード装置のうちの他のノード装置から、前記第１のオペレーションのデータ及び当該第１のオペレーションのデータの受信時刻を受信するステップ
を含む付記１乃至３のいずれか１つ記載のプログラム。
【００６６】
（付記６）
特定のデータに対して既に実行した第１のオペレーションのデータと当該第１のオペレーションのデータの受信時刻とを前記特定のデータに対応付けて格納するデータ格納部と、
特定のデータに対して実行すべき第２のオペレーションのデータ及び当該第２のオペレーションのデータの受信時刻を取得する取得部と、
前記データ格納部において前記特定のデータに対応付けて格納されている前記受信時刻のいずれより、前記第２のオペレーションのデータの受信時刻が後であるか判断し、前記第２のオペレーションのデータの受信時刻が前記データ格納部に前記特定のデータに対応付けて格納されている前記受信時刻のいずれよりも後ではないと判断された場合、前記第１のオペレーション及び前記第２のオペレーションを、受信時刻が早い順に実行する再実行部と、
を有する情報処理装置。
【００６７】
（付記７）
複数のノード装置を含む処理システムにおける前記複数のノード装置のうちのいずれかのノード装置により実行される情報処理方法であって、
特定のデータに対して実行すべき第１のオペレーションのデータ及び当該第１のオペレーションのデータの受信時刻を取得するステップと、
前記特定のデータに対して既に実行した第２のオペレーションのデータと当該第２のオペレーションのデータの受信時刻とを前記特定のデータに対応付けて格納するデータ格納部において前記特定のデータに対応付けて格納されている前記受信時刻のいずれより、前記第１のオペレーションのデータの受信時刻が後であるか判断するステップと、
前記第１のオペレーションのデータの受信時刻が前記データ格納部に前記特定のデータに対応付けて格納されている前記受信時刻のいずれよりも後ではないと判断された場合、前記第２のオペレーション及び前記第１のオペレーションを、受信時刻が早い順に実行する再実行ステップと、
を含む情報処理方法。
【符号の説明】
【００６８】
１，９  ネットワーク    ３１，３２，３３  ノード装置
５，７  ユーザ端末
３０１  通信部    ３０２  ロケータ部
３０３  データ管理部    ３０４  ローカルデータ格納部
１０１１  取得部    １０１３  再実行部
１０１５  データ格納部
【図１】
0005598089.tif 000002
【図２】
0005598089.tif 000003
【図３】
0005598089.tif 000004
【図４】
0005598089.tif 000005
【図５】
0005598089.tif 000006
【図６】
0005598089.tif 000007
【図７】
0005598089.tif 000008
【図８】
0005598089.tif 000009
【図９】
0005598089.tif 000010
【図１０】
0005598089.tif 000011
【図１１】
0005598089.tif 000012
【図１２】
0005598089.tif 000013
【図１３】
0005598089.tif 000014
【図１４】
0005598089.tif 000015