トランザクション処理システム、方法及びプログラム
【課題】シンプルな構成のＫＶＳ上で、ロールバックを不必要に発生させることなく、分散トランザクションを実現する。
【解決手段】キーをグローバル・トランザクションＩＤ、バリューを{トランザクションの状態,終了待ちグローバル・トランザクションＩＤ}とする、管理用マップ４１２ａ〜４１２ｄを用意する。グローバル・トランザクションの開始処理では、管理用マップのキーを管理するサーバ１０６ａ〜１０６ｄ上で、管理用ローカル・トランザクションを開始する。グローバル・トランザクションの終了を待機する処理では、管理用マップのキーを管理するサーバ上で、ロック開放待ち用ローカル・トランザクションを開始し、競合するトランザクションの終了を待機する。
【解決手段】キーをグローバル・トランザクションＩＤ、バリューを{トランザクションの状態,終了待ちグローバル・トランザクションＩＤ}とする、管理用マップ４１２ａ〜４１２ｄを用意する。グローバル・トランザクションの開始処理では、管理用マップのキーを管理するサーバ１０６ａ〜１０６ｄ上で、管理用ローカル・トランザクションを開始する。グローバル・トランザクションの終了を待機する処理では、管理用マップのキーを管理するサーバ上で、ロック開放待ち用ローカル・トランザクションを開始し、競合するトランザクションの終了を待機する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、分散処理システム、特に分散データベース・システム上でのトランザクションの処理に関し、より詳しくは、キー・バリュー・ストア(Key Value Store、以下ＫＶＳと称する）方式におけるトランザクションの処理に関するものである。
【背景技術】
【０００２】
分散データベース・システムは周知であり、例えば、次のような従来技術がある。
特開２００７−１８８５１８号公報は、オーナーシップグループを用いる分散データベース・システムに関し、データ項目のオーナーシップを示すデータを変更するステップを、不可分(atomic)の動作とすることを開示する。
【０００３】
分散データベース・システムは一般に、リレーショナル・データベースを実装し、問い合わせにＳＱＬのような構文を用いる。
【０００４】
最近になって、キー(key)とバリュー(value)の組を書き込み、キーを指定することでバリューを読み出すことができる、キー・バリュー・ストア（ＫＶＳ）と呼ばれるデータベース管理ソフトウェアが使われるようになってきた。ＫＶＳの特徴は、問い合わせがシンプルであるため検索が高速であり、使用するサーバの台数が増えるほど性能を高めることができるというケーラビリティに優れる。そこで、複数台のサーバにデータを分散させることができる分散ＫＶＳも実装されている。
【０００５】
また、ＫＶＳでは、素朴な実装では、処理の原子性(atomicity)、分離性（isolation）は、細かい処理単位に限定されてしまう。例えば、memcachedや、Redis等のKVSでは、1つの照会・更新処理の原子性・分離性しか保障されない。また、WebSphere eXtreme Scaleや、Google App Engineでは、1台のサーバで管理するデータに対する照会・更新処理の原子性・分離性しか保障されない。しかし、アプリケーションが複数のサーバ上のデータに対する更新処理を行う場合、それらの処理に対して原子性・分離性が必須となる場合がある。
【０００６】
一方、従来の分散データベースのように、分散ロック機構を利用した場合、システム全体が複雑となり、ＫＶＳの簡潔な実装による特性を生かすことができない。すなわち、ＫＶＳの各サーバでの複数の照会・更新処理に対するトランザクション原子性が保障される分散ＫＶＳ上で、その各サーバの排他制御機構を用いて、システム全体のトランザクション原子性・分離性を保障するための、複数のサーバを跨った排他制御機構が必須である。
【０００７】
すなわち、アプリケーション上のトランザクション（グローバル・トランザクション）の各処理を、ＫＶＳ上の複数トランザクション（ローカル・トランザクション）として処理することで、分散トランザクションをＫＶＳ上で実現可能である。より具体的には次のようにする。
− まず、ＫＶＳのバリューを、ロックの状態（ロックを保持するグローバル・トランザクションＩＤとロックの種類）とコミット済みのバリュー、更新中のバリューとする。
− また、管理用マップをKVS上に別途用意し、グローバル・トランザクションの開始時は、管理用マップにグローバル・トランザクションの状態を追加する、ローカル・トランザクションを処理する。
− 照会・更新処理は、ロックの状態、コミット済みのバリュー、更新中のバリューを照会・更新するローカル・トランザクションとして処理する。
− コミット・ロールバック処理は、複数のローカル・トランザクションとして実現する。そして、照会・更新した全てのキーごとに、ロックの状態、コミット済みのバリュー、更新中のバリューを更新するローカル・トランザクションとする。
【０００８】
このような手法の例として、「オープンソース徹底活用 Slim3 on Google App Engine for Java」ひがやすお・小川信一著、秀和システム、p.241-251に記述された手法がある。そこには、Google App Engineでグローバル・トランザクションを実現する方法が開示されている。
【０００９】
また、http://research.google.com/pubs/pub36726.htmlには、Google Percolatorが記述されている。
【００１０】
従来技法は、アプリケーションが異常終了する場合を想定し、管理用マップをKVSに用意し、トランザクションの状態（Working, Committed、Aborted）を管理する。そのとき、照会時、ロックを保持していると思われるトランザクションの状態が、Committed、Abortedの場合は、それぞれ、コミット済みのバリュー、更新前のバリューを利用可能となる。しかし、このようなシステムにおいては、ロックが競合した際には、分離性を保障するには、いかなる場合も、ロールバックする必要がある。
【００１１】
http://labs.google.com/papers/chubby.htmlに記述されている、Google Chubbyは、分散ロック機構を利用することにより、分散トランザクションを実現可能とする。しかし、別途分散ロック機構を構築することは、ソフトウェア開発コスト及び管理コストが余分にかかる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−１８８５１８号公報
【非特許文献】
【００１３】
【非特許文献１】「オープンソース徹底活用 Slim3 on Google App Engine for Java」ひがやすお・小川信一著、秀和システム、p.241-251
【非特許文献２】http://research.google.com/pubs/pub36726.html
【非特許文献３】http://labs.google.com/papers/chubby.html
【発明の概要】
【発明が解決しようとする課題】
【００１４】
この発明の目的は、シンプルな構成のＫＶＳ上で、ロールバックを不必要に発生させることなく、分散トランザクションを実現することにある。
【課題を解決するための手段】
【００１５】
本発明は、各サーバの排他制御機構を用いて、各サーバでのローカル・トランザクションの原子性・分離性が保障される分散ＫＶＳ上で、トランザクション間のロックの依存関係を保持し、ロックの開放待ちをＫＶＳの排他制御機構を用いて認識することによって、上記課題を解決する。
【００１６】
より具体的には、本発明のシステムは、キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする、管理用マップを用意する。
【００１７】
そして、[TxID]をグローバル・トランザクションＩＤとするグローバル・トランザクションの開始処理では、本発明のシステムは、ＫＶＳ上で、管理用マップのキー [TxID]を管理するサーバ上で、管理用ローカル・トランザクションを開始する。次に、管理用ローカル・トランザクションで、[TxID]をキー、{working, null}をバリューとするキー・バリュー・ペア（Key-Value Pair）を挿入する。この管理用ローカル・トランザクションは、グローバル・トランザクションが終了（コミットもしくはロールバック）する際、もしくは、グローバル・トランザクションが他のグローバル・トランザクションのロック開放待ちとなるまで、終了しない。
【００１８】
[TxID]をグローバル・トランザクションＩＤとするグローバル・トランザクションが、[終了待ちTxID]のグローバル・トランザクションの終了を待機する処理では、本発明のシステムは、管理用ローカル・トランザクションで、 [TxID]をキーとするバリューを、{waiting, [終了待ちTxID]}に更新し、管理用ローカル・トランザクションをコミットする。次に、管理用マップのキー [終了待ちTxID] を管理するサーバ上で、ロック開放待ち用ローカル・トランザクションを開始し、キー[終了待ちTxID]のバリューを照会する。
【００１９】
このとき、照会したバリューが存在しない、もしくは、バリューにおけるグローバル・トランザクションの状態がcommitted、abortedの場合、本発明のシステムは、ロック開放待ち用ローカル・トランザクションをコミットし、再度管理用ローカル・トランザクションを開始、 [TxID]をキーとするバリューを、{working,null}に更新し、ロックの競合が終了したことを通知する（再度、競合している可能性はある）。
【００２０】
一方、照会したバリューにおける、 [終了待ちTxID]の状態がwaitingで、バリューとして、さらに終了待ちTxIDリストが存在する場合、本発明のシステムは、ロック開放待ち用ローカル・トランザクションをコミットし、[TxID]の終了待ちTxIDリストにこの終了待ちTxIDリストを追加して新たな[TxID]の終了待ちTxIDリストを生成する。そして、再度[TxID]をキーとして管理するサーバ上で管理用ローカル・トランザクションを開始して、[TxID]のグローバル・トランザクションの状態をwaitingに、また、[TxID]の終了待ちTxIDリストを新たに生成したリストに更新し、コミットする。 コミット後、新たに生成した[TxID]の終了待ちTxIDリストの末尾のTxIDのグローバル・トランザクションに対する終了待機処理を行う。なお、[TxID]が、新たに生成した[TxID]の終了待ちTxIDリスト内に含まれる場合は、ロールバックの処理を行い、アプリケーションにロールバックを通知する。これは、デッドロックの可能性がある。
【００２１】
トランザクションをコミットまたはロールバックする場合、本発明のシステムは、管理用ローカル・トランザクションにおいて、 [TxID]をキーとするバリューを、{committed,null}、もしくは、 {aborted,null}に更新し、管理用ローカル・トランザクションをコミットする。
【発明の効果】
【００２２】
この発明によれば、シンプルなＫＶＳにおいても。キー・バリュー・ペアのパーティショニングを考慮する必要がなく、利用用途が広がる。従来は、シンプルなＫＶＳは、銀行口座の振替用アプリケーションは、ユーザーIDごとにデータを複数サーバに分割する場合、使えなかった。
【００２３】
また、この発明によれば、ＫＶＳ上で、分散ロック機構を別途実装する必要なく、分散トランザクションを実現することができる。
【００２４】
さらに、この発明に従う、管理用マップに対するトランザクション処理、アプリケーション用マップに対するトランザクション処理は、サーバ増加分だけスループットを増加させることができる。また、ロックの競合発生時にも、ロックを待機させるため、オーバヘッドは少ない。
【００２５】
結局、この発明によれば、管理マップの排他ロックをトランザクション中維持し続けることにより、不用意なロールバックを減らすことができるという効果が得られる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施するためのシステム全体の概要図である。
【図２】クライアント・コンピュータのハードウェアの概要ブロック図である。
【図３】サーバのハードウェアの概要ブロック図である。
【図４】クライアント・コンピュータとサーバにおける機能ブロック図である。
【図５】従来のＫＶＳシステムの概要を示す図である。
【図６】従来のＫＶＳシステムの概要を示す図である。
【図７】従来のＫＶＳシステムの概要を示す図である。
【図８】本発明の従来のＫＶＳシステムの概要を示す図である。
【図９】トランザクションの開始時の処理のフローチャートを示す図である。
【図１０】照会時の処理のフローチャートを示す図である。
【図１１】更新時の処理のフローチャートを示す図である。
【図１２】コミット時の処理のフローチャートを示す図である。
【図１３】あるトランザクションが、別トランザクションの終了を待機する処理のフローチャートを示す図である。
【図１４】ロールバック時の処理のフローチャートを示す図である。
【図１５】トランザクションの処理の一例を示す図である。
【図１６】トランザクションの処理の一例を示す図である。
【図１７】トランザクションの処理の一例を示す図である。
【図１８】トランザクションの処理の一例を示す図である。
【発明を実施するための形態】
【００２７】
以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことに留意されたい。
【００２８】
図１は、本発明の実施するためのシステムの全体を示す概要図である。図１において、複数のクライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、インターネット１０４を介して、ＨＴＴＰなどのプロトコルにより、分散処理システム１０６にアクセスする。
【００２９】
分散処理システム１０６は、ＬＡＮまたはＷＡＮなどの仕組みにより相互接続された複数のサーバ１０６ａ、１０６ｂ、・・・、１０６ｚをもつ。分散サーバ・システム１０６は、キー・バリュー・ストア（ＫＶＳ）の仕組みで、分散データベースを構築するシステムである。すなわち、各サーバ１０６ａ、１０６ｂ、・・・、１０６ｚにはＩＤが付与され、この方式には限定されないが、好適には、キーのハッシュ・バリューのmodを計算することで、そのキーを保持するサーバが一意的に決まる。
【００３０】
従って、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、照会するキーで、アクセスするサーバ１０６ａ、１０６ｂ、・・・、１０６ｚが決定される。好適には、サーバ１０６ａ、１０６ｂ、・・・、１０６ｚのうちの一台がカタログ・サーバと呼ばれるサーバで、そこには、他のサーバに格納されているキーその他の情報が格納され、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、カタログ・サーバに一旦アクセスして、サーバ１０６ａ、１０６ｂ、・・・、１０６ｚのうちのどのサーバにアクセスするかの情報を取得してから、指示されたサーバとの接続を確立する。あるいは、クライアント・コンピュータがアクセスした任意のサーバが他の複数のサーバにブロードキャストして、情報を取得する方式も使用できる。以下での説明では便宜上、クライアント・コンピュータが、目的とするサーバを見つけて接続を確立したところから説明する。
【００３１】
クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、分散処理システム１０６にアクセスするために、一意的なグローバル・トランザクションＩＤを生成して、その後の分散処理システム１０６とのトランザクションに、そのグローバル・トランザクションＩＤを使用する。
【００３２】
次に、図２を参照して、図１で参照番号１０２ａ、１０２ｂ・・・１０２ｚのように示されているクライアント・コンピュータのハードウェア構成について、説明する。図２において、クライアント・コンピュータは、主記憶２０６、ＣＰＵ２０４、ＩＤＥコントローラ２０８をもち、これらは、バス２０２に接続されている。バス２０２には更に、ディスプレイ・コントローラ２１４と、通信インターフェース２１８と、ＵＳＢインターフェース２２０と、オーディオ・インターフェース２２２と、キーボード・マウス・コントローラ２２８が接続されている。ＩＤＥコントローラ２０８には、ハードディスク・ドライブ（ＨＤＤ）２１０と、ＤＶＤドライブ２１２が接続されている。ＤＶＤドライブ２１２は、必要に応じて、ＣＤ−ＲＯＭやＤＶＤから、プログラムを導入するために使用する。ディスプレイ・コントローラ２１４には、好適には、ＬＣＤ画面をもつディスプレイ装置２１６が接続されている。ディスプレイ装置２１６には、Ｗｅｂブラウザを通じて、アプリケーションの画面が表示される。
【００３３】
ＵＳＢインターフェース２２０には、必要に応じて、拡張ハードディスクなどのデバイスを接続をすることができる。
【００３４】
キーボード・マウス・コントローラ２２８には、キーボード２３０と、マウス２３２が接続されている。キーボード２３０は、検索のためのキーデータや、パスワードなどを打ち込むために使用される。
【００３５】
ＣＰＵ２０４は、例えば、３２ビット・アーキテクチャまたは６４ビット・アーキテクチャに基づく任意のものでよく、インテル社のＰｅｎｔｉｕｍ（インテル・コーポレーションの商標）４、Ｃｏｒｅ（商標）２ Ｄｕｏ、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。
【００３６】
ハードディスク・ドライブ２１０には、少なくとも、オペレーティング・システムと、、分散処理システム１０６にアクセスするためのクライアント側のアプリケーション・プログラム４０２ａ（図４）が格納されており、システムの起動時に、オペレーティング・システムは、メインメモリ２０６にロードされる。オペレーティング・システムは、Ｗｉｎｄｏｗｓ ＸＰ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ Ｖｉｓｔａ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ（マイクロソフト・コーポレーションの商標） ７、Ｌｉｎｕｘ（Linus Torvaldsの商標）などを使用することができる。クライアント側のアプリケーション・プログラム４０２ａは、図４のブロック図や、図９〜図１４のフローチャートを参照して、後で詳細に説明する。
【００３７】
通信インターフェース２１８は、オペレーティング・システムが提供するＴＣＰ／ＩＰ通信機能を利用して、イーサネット（商標）・プロトコルなどにより、インターネット１０４を介して、分散処理システム１０６と通信する。
【００３８】
図３は、分散処理システム１０６における、サーバ１０６ａなどのハードウェア構成の概要ブロック図である。図示されているように、インターネット１０４を介して、サーバ１０６ａ、１０６ａ、・・・１０６ｚが接続されている。サーバ１０６ａ、１０６ａ、・・・１０６ｚは基本的に同一の構成なので、ここでは代表的にサーバ１０６ａを示す。図３に示すように、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、インターネット１０４を経由して、サーバ１０６ａの通信インターフェース３０２に接続される。通信インターフェース３０２はさらに、バス３０４に接続され、バス３０４には、ＣＰＵ３０６、主記憶（ＲＡＭ）３０８、及びハードディスク・ドライブ（ＨＤＤ）３１０が接続されている。
【００３９】
図示しないが、サーバ１０６ａにはさらに、キーボード、マウス、及びディスプレイが接続され、これらによって、保守担当者が、サーバ１０６全体の管理やメンテナンス作業を行うようにしてもよい。
【００４０】
サーバ１０６ａのハードディスク・ドライブ３１０には、オペレーティング・システムが保存されている。
【００４１】
ハードディスク・ドライブ３１０にはさらに、サーバ１０６ａをＷｅｂサーバとして機能させるためのＡｐａｃｈｅなどのソフトウェア、及びＪａｖａ仮想環境を実現するＪａｖａ ＥＥ、及びＪａｖａ仮想環境上で動作する本発明に係る後述するアプリケーション・プログラム４０２ａが保存され、サーバ１０６ａの立ち上げ時に、主記憶３０８にロードされて、動作する。これによって、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚが、ＴＣＰ／ＩＰのプロトコルで、サーバ１０６にアクセスすることが可能となる。
【００４２】
サーバ１０６ａのハードディスク・ドライブ３１０にはさらに、IBM(R) WebSphere eXtreme ScaleなどのＫＶＳを実現するためのソフトウェアが保存されている。ハードディスク・ドライブ３１０にはまた、本発明に従う、ＫＶＳ用のトランザクション処理プログラム４０６ａ（図４）が保存されている。このトランザクション処理プログラム４０６ａの機能については、図４のブロック図や、図９〜図１４のフローチャートを参照して、後で詳細に説明する。
【００４３】
尚、上記サーバ１０６ａとして、インターナョナル・ビジネス・マシーンズ・コーポレーションから購入可能な、ＩＢＭ（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）System X、System i、System pなどの機種のサーバを使うことができる。その際、使用可能なオペレーティング・システムは、AIX（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）、UNIX(The Open Groupの商標)、Linux(商標)、Windows(商標)2003 Serverなどがある。
【００４４】
図４は、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚと、サーバ１０６ａ、１０６ｂ、・・・１０６ｚの各々における、処理プログラムの概要ブロック図を示す。なおここでは代表的に、クライアント・コンピュータ１０２ａとサーバ１０６ａを示す。
【００４５】
クライアント・コンピュータ側のアプリケーション・プログラム４０２ａは、ハードティスク・ドライブ２１０に保存されており、クライアント・コンピュータのユーザーの所定の操作で主記憶２０２にロードされて実行され、クライアント・コンピュータから、サーバ上にあるＫＶＳシステムに対して、トランザクションの開始、データの照会、データの更新、コミットなどの処理を指示する機能をもつ。
【００４６】
アプリケーション・プログラム４０２ａは、システム全体で一意的なグローバル・トランザクションＩＤ(TxID)を生成する機能４０４ａをもつ。グローバル・トランザクションＩＤの生成方法の１つの例は、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚと、サーバ１０６ａ、１０６ｂ、・・・１０６ｚの各々に固有のＩＤを付与しておき、各クライアント・コンピュータでトランザクションを開始する度に、そのクライアント・コンピュータのＩＤ＋クライアント・コンピュータ内の増分される通し番号をグローバル・トランザクションＩＤとすることであるが、システム全体で一意的なグローバル・トランザクションＩＤになるようにする任意の方法を使用してもよい。
【００４７】
アプリケーション・プログラム４０２ａは、グローバル・トランザクションＩＤを生成してサーバ１０６ａにアクセスすることができるが、別グローバル・トランザクションＩＤを生成することにより、同時に複数のサーバにアクセスすることができる。
【００４８】
サーバ１０６ａのハードティスク・ドライブ３１０には、トランザクション処理プログラム４０６ａと、例えばIBM(R) WebSphere eXtreme ScaleであるＫＶＳプログラム４０８ａと、ＫＶＳプログラム４０８ａによって参照される、キー(KEY)とバリュー(VALUE)のペアが保存され、トランザクション処理プログラム４０６ａとＫＶＳプログラム４０８ａは、サーバ１０６ａのスタートアップ時に、主記憶３０８にロードされて動作する。
【００４９】
トランザクション処理プログラム４０６ａは、クライアント・コンピュータ１０２ａからの、グローバル・トランザクションＩＤを伴うリクエストに応答して、レコードのロック、ロールバックなどの動作を行うようにＫＶＳプログラム４０８ａを制御するとともに、好適には主記憶３０８に、グローバル・トランザクションＩＤと、状態と、待ちグローバル・トランザクションＩＤを含むエントリをもつ管理用マップ４１２ａを作成して、サーバ毎に維持する。
【００５０】
さて、本発明に従うＫＶＳシステムの構成と動作を説明する前に、従来の典型的ないくつかのＫＶＳシステムの構成と動作を説明する。これらを参照することにより、本発明に従うシステムの特徴がより明らかになるものと思量する。
【００５１】
図５は、従来の典型的なＫＶＳの構成を示す図である。ここで改めてＫＶＳについて説明すると、図示されているように、データはデータ５０２ａ、５０２ｂ、５０２ｃ、５０２ｄのように分割され、複数のサーバ１０２ａ、１０２ｂ、１０２ｃ、１０２ｄに分散して配置される。クライアント・コンピュータ１０２ａは、１台のサーバに対して、トランザクション処理を要求する。このとき。互いに素(disjoint)になるように、データは分散配置されている。データを配置するサーバは、好適には、キーのハッシュ・バリューのmodを計算することで決定される。
【００５２】
クライアント・コンピュータ１０２ａは、begin（トランザクションを開始する）、put（バリューを対応付ける）、get（対応するバリューを取得する）、commit（コミット、すなわち更新を確定する）などのコマンドを、キーのバリューによって決まるサーバに送って処理を要求する。
【００５３】
このような従来構成のＫＶＳは、分散トランザクションをサポートしていないので、各トランザクションでの更新範囲が複雑な場合、利用できない。トランザクションでの更新範囲が複雑になる例として、銀行口座の振込み、特に各口座残高を分散配置した場合や、ショッピングサイトにおいて、アカウント毎の履歴と、商品の在庫数を分散配置した場合がある。
【００５４】
そこで、図６のようなＫＶＳの構成が実現された。この構成においては、データを格納するフィールドを拡張して、dirty updateを格納するフィールドNEXTと、ロックバージョンを格納するVERのフィールドを、参照番号６０２ａ、６０２ｂ、６０２ｃ、６０２ｄに示すように追加した。
【００５５】
これによれば、クライアント１０２ａは、データにアクセスする前にロックを獲得する。そして、更新時、dirty updateとロックのバージョンを書き込む。一方、分散ロック機構６０４が別途設けられて、コミットされたロックのバージョンを管理する。その際、ロック獲得が成功したにも拘らず、NEXTバリューが存在する場合は、NEXTバリューをNOWバリューに変更し、ロック・バージョンを更新して、処理を続行する。このような仕組みにより、分散トランザクションは実現可能である。しかし、別途分散ロック機構６０４を構築することは、ソフトウェアの開発コスト、管理コストの上昇につながる。
【００５６】
そこで、別途の分散ロック機構を用いない、図７に示すようなＫＶＳの構成が提案された。この構成では、データのテーブル７０２ａ、７０２ｂ、７０２ｃ、７０２ｄ以外に、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄに、グローバル・トランザクションＩＤ(TxID)及びトランザクションの状態とからなる、トランザクションの状態を記録する管理テーブル７０４ａ、７０４ｂ、７０４ｃ、７０４ｄをそれぞれ別途設ける。この構成では、クライアント１０２ａは、照会したバージョンを記録し、照会したバージョンが更新されていない場合のみコミット可能とする。そして、コミット後、別トランザクションで、トランザクション状態を更新し、バリューを更新する。
【００５７】
この構成では、競合時、すなわち複数のクライアントが同一のデータを更新する場合、既存のトランザクションの状態をローバック状態にする。これによって、分散トランザクションは実現可能であるが、楽観的トランザクションしか実現できない。また、既存の製品のみで実現可能であるが、競合が発生した場合、ロールバックが多発し、性能が向上しない可能性がある。
【００５８】
図８は、図７に示すようなＫＶＳの構成を改善した、本発明の構成を示す。ここでの参照番号は、図４の機能ブロック図に対応する。すなわち、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄに、グローバル・トランザクションＩＤ(TxID)及びトランザクションの状態と、終了待ちグローバル・トランザクションＩＤとからなる、管理用マップ４１２ａ、４１２ｂ、４１２ｃ、４１２ｄをそれぞれ別途設ける。そこで、STATEのフィールドに格納されるのがトランザクションの状態であり、WAITのフィールドに格納されるのが終了待ちグローバル・トランザクションＩＤである。
【００５９】
また、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄには、ＫＶＳのデータを格納するテーブル（データ・マップ）４１０ａ、４１０ｂ、４１０ｃ、４１０ｄも設けられる。データ・マップ４１０ａ、４１０ｂ、４１０ｃ、４１０ｄはそれぞれ、キーを入れるフィールドであるKEYと、コミット確定済みのバリューを入れるフィールドであるNOWと、更新中のバリューを格納するフィールドNEXTと、ロック状態、すなわち更新中のグローバル・トランザクションＩＤ TxIDを格納するフィールドWRITINGと、照会中のグローバル・トランザクションＩＤTxIDsを格納するREADINGをもつ。
【００６０】
この構成では、クライアント１０２ａは、ロックの情報を照会・更新毎に更新する。そして、ロックが競合時、トランザクションの状態を更新し、終了待ちトランザクションの状態を監視する。コミットの後、クライアント１０２ａは、トランザクション状態を更新し、別トランザクションでバリューを更新する。
【００６１】
複数のクライアントが、同一のデータを更新する場合、すなわち競合時、競合するトランザクションの終了を既存のロック機構を利用することで、待機する。
【００６２】
次に、本発明の処理のデータ構造とインターフェースについて説明する。
想定するＫＶＳのマップ・インタフェースは、次のとおりである。
get(key) ：keyに対する共有ロックを獲得し、対応するvalueを取得する。
put(key,value) ：keyに対する排他ロックを獲得し、valueを対応付ける。
cas(key,prev, value) ：keyに対する排他ロックを獲得し、バリューがprevだった場合に、valueを対応付ける。
remove(key) ：keyに対する排他ロックを獲得し、valueを削除する。
commit() ：keyに対する更新を確定し、獲得した全てのロックを開放する。
【００６３】
マップ構成（1つの分散マップをアプリケーションが利用することを想定）
トランザクションの状態管理用のマップ（TxStateMap）。これは、図８に示すテーブル４１２ａ、４１２ｂ、４１２ｃなどである。
key : TxID （グローバル・トランザクションＩＤ）
value: 状態 (Working|Committed|Rollbacked|Waiting) (STATE)、待機中TxID(WAITING)。
データ管理とロックの状態管理用のマップ (DataMap)。これは、図８に示すデータ・マップ４１０ａ、４１０ｂ、４１０ｃなどである。
key： アプリケーションが指定するkey
value： コミット確定済みのバリュー(NOW)、更新中のバリュー(NEXT)、ロック状態、すなわち更新中のグローバル・トランザクションＩＤ (WRITING)、照会中のグローバル・トランザクションＩＤのリスト(READING)。
【００６４】
また、トランザクションを実行中のクライアントがもつ状態として、以下のものがある。
TxID
− グローバル・トランザクションＩＤ
− これは、トランザクション開始時に生成される。
DirtyList
− 更新中のDataMapのバリュー
ReadingKeyList
− 照会中のDataMapのkey
さらにこの実施例では、終了済みTxIDリストとして、FinishTxIDsも用意される。
【００６５】
次に、図９〜図１４のフローチャートを参照して、本発明の処理について説明する。図９〜図１４のフローチャートの動作を通して、基本的には、クライアント・コンピュータから指示が出され、その指示に応答して、サーバで処理が行われ、必要に応じてサーバからクライアントに応答が返される態様である。
【００６６】
まず図９は、トランザクションの開始時の処理のフローチャートを示す。この処理は基本的に、クライアント・コンピュータ１０２ａ、１０２ｂ、・・・１０２ｚのアプリケーション・プログラム４０２ａ、４０２ｂ、・・・４０２ｚのどれかで実行される。
【００６７】
ステップ９０２では、クライアント・コンピュータは、クライアント・コンピュータ固有のＩＤ＋クライアント・コンピュータ内の増分される通し番号等により、グローバル・トランザクションＩＤ TxIDを生成する。
【００６８】
ステップ９０４では、クライアント・コンピュータ１０２ａは、初期状態INIT.STATE = Working、INIT.WAITING = {}とし、グローバル・トランザクションＩＤ(TxID)を以って、対応するサーバ１０６ａのトランザクションの状態管理用のマップTxStateMapに対して、put(TxID,INIT)を実行する。このとき、コミットはしない。この管理用のマップに対するトランザクションは、管理用ローカル・トランザクションと呼ばれる。なお、ここでクライアント・コンピュータ１０２ａとサーバ１０６ａの組み合わせを例にとって説明しているが、実際上、クライアント・コンピュータ１０２ａ、１０２ｂ、・・・１０２ｚとサーバ１０６ａ、１０６ｂ、・・・１０６ｚの任意の組み合わせがありえることに留意されたい。また、実際上、クライアント・コンピュータ１０２ａのアプリケーション・プログラム４０４ａがサーバに対するトランザクションを実行するが、以下の説明では便宜上、クライアント・コンピュータ１０２ａが実行すると記述する。
【００６９】
図１０は、照会時の処理、すなわち、mapに対してkeyのバリューを照会する場合の処理のフローチャートを示す図である。図１０のステップ１００２では、クライアント・コンピュータ１０２ａは、対応するサーバ１０６ａのトランザクション処理プログラム４０６ａに問い合わせして、DataMap.put(key)という問い合わせを行い、その結果のエントリをVに格納する。そして、DataMap.commit()により、コミットする。
【００７０】
ステップ１００４では、クライアント・コンピュータ１０２ａからの指示で、サーバ１０２ａが、NEW = Vで、Vを一旦NEWにコピーし、NEW.READING.add(TxID)により、データ・マップ(DataMap)４１０ａのREADINGフィールドにTxIDを格納する。
【００７１】
ステップ１００６では、サーバ１０６ａは、V.WRITING == NULLかどうか判断し、そうでないなら、ステップ１００８は、V.WRITINGのトランザクションの終了を待機する。そして、ステップ１０１０で、V.WRITINGがコミット済みかどうか判断し、もしそうなら、ステップ１０１２で、NEW.NOW = NEW.NEXTと格納し、NEW.NEXT = NULLとする。そうでなければステップ１０１４で単に、NEW.NEXT = NULLとする。こうして次にステップ１０１６に進む。
【００７２】
ステップ１００６でV.WRITING == NULLであると判断されたなら、直接ステップ１０１６に進む。
【００７３】
ステップ１０１６では、クライアント・コンピュータ１０２ａは、DataMap.cas(key,V,NEW)をトランザクション処理プログラム４０６ａに指示し、次にトランザクション処理プログラム４０６ａは、DataMap.commit()により、コミットする。
【００７４】
サーバ１０６ａは、ステップ１０１８で、CASが成功したかどうかを判断し、もしそうなら、ステップ１０２０で、ReadingKeyList.add(key)により、keyをReadingKeyListに追加して、処理を終える。ステップ１０１８で、CASが成功しなかったと判断されると、処理はステップ１００２に戻る。
【００７５】
図１１は、更新時の処理、すなわち、mapに対してkeyのバリューをv'に更新する場合の処理のフローチャートを示す図である。図１１のステップ１１０２では、クライアント・コンピュータ１０２ａは、トランザクション処理プログラム４０６ａにDataMap.put(key)という問い合わせを行い、するとサーバ１０６ａは、その結果のエントリをVに格納する。そして、DataMap.commit()により、コミットする。
【００７６】
ステップ１１０４では、サーバ１０６ａは、DIRTY = Vで、Vを一旦DIRTYにコピーし、DIRTY.NEXT = v'とセットし、さらに、DIRTY.WRITING = TxIDとセットする。
【００７７】
ステップ１１０６では、サーバ１０６ａは、V.WRITING == TxIDかどうか判断し、そうでないなら、ステップ１１０８で、V.WRITING == NULLかどうか判断する。もしそうでないなら、ステップ１１１０で、V.WRITINGのTxに対する終了処理の待機を行う。次にステップ１１１２では、V.WRITINGがコミット済みかどうか判断し、そうならDIRTY.NOW = V.NEXTとしてステップ１１１６に進む。V.WRITINGがコミット済みでないなら、直接ステップ１１１６に進む。一方、ステップ１１０８で、V.WRITING == NULLであると判断された場合、直接ステップ１１１６に進む。
【００７８】
ステップ１１１６では、サーバ１０６ａは、DIRTY.READING.remove(TxID)により、DIRTY.READINGからTxIDを除去する。
【００７９】
ステップ１１１８では、サーバ１０６ａは、V.READING.isEmpty()により、V.READINGが空かどうか判断する。もし空であればステップ１１２２に進み、空でなければステップ１１２０で、DIRTY.READING中の全トランザクションに対する終了待機処理を行う。
【００８０】
こうして、ステップ１１０６でYESの場合、ステップ１１１８でYESの場合、あるいはステップ１１２０に続いて、ステップ１１２２では、サーバ１０６ａは、DIRTY.READING = {}, DataMap.cas(key,V,DIRTY)及びDataMap.commit()を実行する。
【００８１】
ステップ１１２４では、サーバ１０６ａは、CASが成功したかどうかを判断し、もしそうなら、ステップ１１２６で、ReadingKeyList.remove(key)で、ReadingKeyListからkeyを除去し、DirtyList.add(DIRTY)により、DirtyListにDIRTYを追加する。一方、CASが成功しなかったと判断したら、処理はステップ１１０２に戻る。
【００８２】
図１２は、コミット時の処理のフローチャートを示す図である。コミット時には、ステップ１２０２で、前の状態であるPrevState.STATEにWorkingがセットされ、新しい状態であるNewState.STATEにCommittedがセットされ、TxStateMap.cas(TxID, PrevState, NewState)を実行した後、TxStateMap.commit()が実行される。
【００８３】
次のステップ１２０４で、サーバ１０６ａは、ＣＡＳが成功したかどうかを判断し、そうでなければステップ１２０６でのロールバック処理に行く。ここでＣＡＳが失敗したということは、他のトランザクションから強制的にアボートされたことを意味する。
【００８４】
一方、ＣＡＳが成功したなら、ステップ１２０８で、サーバ１０６ａは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ１２１０で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ１２１２でReadingKeyList中のCASが成功していないkeyを選択し、ステップ１２１４で、
V = DataMap.get(key)
NEW = V
V.READING.remove(TxID)
DataMap.cas(key,V,NEW)
DataMap.commit()
を実行し、ＣＡＳが成功しない限りステップ１２１２に戻る。ＣＡＳが成功するとステップ１２１０に進み、そして、ステップ１２１０でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。
【００８５】
ステップ１２０８に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ１０６ａは、ステップ１２１８でDirtyList中の選択していないバリュー(DIRTY)を選択し、ステップ１２２０で
NEW = DIRTY
NEW.NEXT = NULL
NEW.NOW = DIRTY.NEXT
NEW.WRITING = NULL
を実行し、ステップ１２２２でDataMap.cas(key,DIRTY,NEW)、DataMap.commit()を実行して、ステップ１２０８に戻る。
【００８６】
図１３は、TxIDをグローバル・トランザクションＩＤとするトランザクションが、TgtTxIDをグローバル・トランザクションＩＤとするトランザクションの終了を待機する処理のフローチャートを示す図である。
【００８７】
ステップ１３０２では、クライアント・コンピュータ１０２ａは、サーバ１０２ａのトランザクション処理プログラム４０６ａに働きかけて、
WorkingState.STATE = Working
WaitState.STATE = Waiting
WaitState.WAITING = {TgtTxID}
TxStateMap.cas(TxID,WorkingState,WaitState)
TxStateMap.commit()
を実行する。
【００８８】
そしてステップ１３０４で、サーバ１０６ａは、ＣＡＳが成功したかどうかを判断する。ここでＣＡＳが成功しなかったということは、他のトランザクションから強制的にアボートされたということであり、ステップ１３０６でロールバック処理を行う。
【００８９】
ＣＡＳが成功したと判断されると、サーバ１０６ａは、ステップ１３０８で、TgtState = TxStateMap.get(TgtTxID)を実行し、次にTxStateMap.commit()を実行する。ここでgetが実行されるのは、TgtTxIDのトランザクションがWaiting、Committed、Rollbacked時のみである。
【００９０】
ステップ１３１０では、サーバ１０６ａは、TgtState.WAITING.contained(TxID)、すなわち、TgtStateのWAITINGに、TxIDが含まれているかどうかを判断する。もしそうでなければ、デッドロックの可能性ありとして、ステップ１３０６でロールバック処理を行う。
【００９１】
ステップ１３１０で、TgtStateのWAITINGに、TxIDが含まれていると判断されると、ステップ１３１２で、TgtState.STATEがCommittedまたはRollbackedのどちらかであるかどうかが判断され、もしそうなら、ステップ１３２２に進んで、サーバ１０６ａは、TxStateMap.cas(TxID,WaitState,WorkingState)とFinishTxID.add(WaitingTxID)を実行し、その結果ステップ１３２４で、ＣＡＳが成功したかどうか判断し、もし成功なら処理を終わり、そうでなければ、ステップ１３２６でロールバック処理を行う。
【００９２】
ステップ１３１２に戻って、TgtState.STATEがCommittedまたはRollbackedのどちらでもないなら、サーバ１０６ａは、ステップ１３１４で、TgtTxIDはゾンビ、すなわち、長時間Waitingであるかどうか、判断する。もしそうなら、ステップ１３１８に進み、そこで、下記の処理を行う。
NewTgtState.STATE = Rollbacked
TxStateMap.cas(TgtTxID,TgtState,NewTgtState)
TxStateMap.commit()
【００９３】
ステップ１３２０で、サーバ１０６ａは、ＣＡＳが成功したかどうか判断し、もし成功ならステップ１３２２に進み、そうでないなら、ステップ１３０８に戻る。
【００９４】
ステップ１３１４に戻って、TgtTxIDはゾンビでないと判断されると、ステップ１３１６に進み、そこで、下記の処理を行う。
PrevWaitState = WaitState
// これは、WaitStateをPrevWaitStateにコピーする処理である。
WaitState.WAITING.addAll(TgtState.WAITING)
// これは、WaitState.WAITINGのすべてのグローバル・トランザクションＩＤをWaitState.WAITINGに追加する。
TxStateMap.cas(key,prevWaitState,WaitState)
TxStateMap.commit()
TgtTxID = TgtState.tail()
// これは、TgtState.WAITINGの最後にリストされているグローバル・トランザクションＩＤをTgtTxIDに代入するものである。
そして処理は、ステップ１３０４に戻る。
【００９５】
図１４は、ロールバック時の処理のフローチャートを示す図である。図１４において、ステップ１４０２で、前の状態であるPrevState.STATEにWorkingがセットされ、新しい状態であるNewState.STATEにCommittedがセットされ、TxStateMap.cas(TxID, PrevState, NewState)を実行した後、TxStateMap.commit()が実行される。
【００９６】
次に、ステップ１４０４で、サーバ１０６ａは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ１４０６で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ１４０８でReadingKeyList中のCASが成功していないkeyを選択し、ステップ１４１０で、
V = DataMap.get(key)
NEW = V
V.READING.remove(TxID)
DataMap.cas(key,V,NEW)
DataMap.commit()
を実行し、ＣＡＳが成功しない限りステップ１４０８に戻る。そして、ステップ１２１０でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。
【００９７】
ステップ１２０８に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ１０６ａは、ステップ１４１４でDirtyList中の選択していないバリュー(DIRTY)を選択し、ステップ１４１６で
NEW = DIRTY
NEW.NEXT = NULL
NEW.NOW = DIRTY.NEXT
NEW.WRITING = NULL
を実行し、ステップ１４１８でDataMap.cas(key,DIRTY,NEW)、DataMap.commit()を実行して、ステップ１４０４に戻る。
【００９８】
次に、図１５〜図１８の例を参照して、本発明のいくつかの典型的な処理の例を示す。なお、以下では説明の便宜上、データ・マップ(DataMap)におけるNOW、NEXTのバリューは省略する。また、図１５〜図１８において、sは共有ロック(Shared)、ｘは排他ロック(eXclusive)をあらわす。
【００９９】
まず図１５は、Tx1がK1を照会後、コミットする例を示す。図１５の１では、クライアント・コンピュータがトランザクションTx1を開始し、これによって、管理マップ４１２ａのKEYにTx1が格納され、STATEがWorkingとなる。
【０１００】
図１５の２で、Tx1が共有ロックK1を獲得すると、データ・マップ４１０ａのKEYにK1が格納され、データ・マップ４１０ａのREADINGに{Tx1}が格納される。
【０１０１】
図１５の３で、Tx1のコミット処理が行われ、管理マップ４１２ａのSTATEがCommittedになる。
【０１０２】
図１５の４で、Tx1の更なるコミット処理が行われ、データ・マップ４１０ａのREADINGが｛｝になる。
【０１０３】
図１６は、Tx1がK1を照会中、Tx2がK1の更新を試行し、Tx1のコミット後に処理されるという例を示す。
【０１０４】
図１６の１では、Tx1がK1を照会中であることを示す。図１６の２では、Tx2が共有ロックK1を獲得しようとするが、Tx1がK1を照会中なので、Tx2の照会はブロックされる。管理マップ４１２ａのKEY = Tx2のエントリのWAITINGには、{Tx1}が入る。
【０１０５】
図１６の３では、Tx1のコミット処理終了後Tx2が照会可能となり、図１６の４では、Tx2が共有ロックK1を獲得再開する。これに応答して、管理マップ４１２ａのKEY = Tx2のエントリのSTATEがWorkingになり、WAITINGは{}になる。
【０１０６】
図１６の５では、Tx2の更新処理が開始され、データ・マップ４１０ａのKey = K1に対応するWRITINGにTx2が格納される。
【０１０７】
図１７は、Tx1の終了をTx2が待機し、Tx2の終了をTx3が待機する場合、Tx1が終了時にTx2が稼動を開始し、Tx3が依然としてTx2を待機する例を示す。
【０１０８】
図１７の１では、管理マップ４１２ａのエントリが示すように、Tx1のコミットを、Tx2が待機中である。図１７の２では、Tx2が照会中のK2をTx3が更新開始する。ここでTx3は、Tx2がTx1待ちと認識する。
【０１０９】
図１７の３では、Tx3がTx1を待機中になる。このことは、管理マップ４１２ａのKEY = Tx3に対応する、WAITINGの{Tx2,Tx1}というエントリによって示される。
【０１１０】
図１７の４は、Tx1がコミットされて終了した後に、Tx3がTx2待ちになる様子を示す。
【０１１１】
図１８は、Tx1、Tx2、Tx3でデッドロックした場合、Tx1がロールバックする処理の例を示す。図１８の１では、Tx1、Tx3がTx1を待機中になる。図１８の２では、Tx1がTx3の照会中のバリューの更新を試みる。
【０１１２】
しかし、管理マップ４１２ａのエントリから見て取れるように、Tx3に対応するエントリのWAITINGにTx1が含まれるため、図１８の３に示すように、Tx1はロールバックする。
【０１１３】
すると、図１８の４に示すように、Tx1のロールバック後、管理マップ４１２ａのTx2とTx3のエントリのWAITINGのフィールドからTx1が消去され、Tx3はTx2待ちになる。この際、Tx1のSTATEをRollbackedにする前に、Tx2とTx3がTx1のSTATEを照会した場合は、すべてのトランザクションがロールバックするが、原子性は保障される。
【０１１４】
以上、特定のハードウェア及びソフトウェアのプラットアフォームの上で本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを、この分野の当業者なら理解するであろう。
【符号の説明】
【０１１５】
１０２ クライアント・コンピュータ
１０６ サーバ
２０２ 主記憶
２０４ ＣＰＵ
２０６ メインメモリ
２０６ 主記憶
２１０ ハードディスク・ドライブ
３０６ ＣＰＵ
３０８ 主記憶
３１０ ハードディスク・ドライブ
４０４ アプリケーション・プログラム
４０６ トランザクション処理プログラム
４０８ ＫＶＳプログラム
４１０ データ・マップ
４１２ 管理用マップ
【技術分野】
【０００１】
この発明は、分散処理システム、特に分散データベース・システム上でのトランザクションの処理に関し、より詳しくは、キー・バリュー・ストア(Key Value Store、以下ＫＶＳと称する）方式におけるトランザクションの処理に関するものである。
【背景技術】
【０００２】
分散データベース・システムは周知であり、例えば、次のような従来技術がある。
特開２００７−１８８５１８号公報は、オーナーシップグループを用いる分散データベース・システムに関し、データ項目のオーナーシップを示すデータを変更するステップを、不可分(atomic)の動作とすることを開示する。
【０００３】
分散データベース・システムは一般に、リレーショナル・データベースを実装し、問い合わせにＳＱＬのような構文を用いる。
【０００４】
最近になって、キー(key)とバリュー(value)の組を書き込み、キーを指定することでバリューを読み出すことができる、キー・バリュー・ストア（ＫＶＳ）と呼ばれるデータベース管理ソフトウェアが使われるようになってきた。ＫＶＳの特徴は、問い合わせがシンプルであるため検索が高速であり、使用するサーバの台数が増えるほど性能を高めることができるというケーラビリティに優れる。そこで、複数台のサーバにデータを分散させることができる分散ＫＶＳも実装されている。
【０００５】
また、ＫＶＳでは、素朴な実装では、処理の原子性(atomicity)、分離性（isolation）は、細かい処理単位に限定されてしまう。例えば、memcachedや、Redis等のKVSでは、1つの照会・更新処理の原子性・分離性しか保障されない。また、WebSphere eXtreme Scaleや、Google App Engineでは、1台のサーバで管理するデータに対する照会・更新処理の原子性・分離性しか保障されない。しかし、アプリケーションが複数のサーバ上のデータに対する更新処理を行う場合、それらの処理に対して原子性・分離性が必須となる場合がある。
【０００６】
一方、従来の分散データベースのように、分散ロック機構を利用した場合、システム全体が複雑となり、ＫＶＳの簡潔な実装による特性を生かすことができない。すなわち、ＫＶＳの各サーバでの複数の照会・更新処理に対するトランザクション原子性が保障される分散ＫＶＳ上で、その各サーバの排他制御機構を用いて、システム全体のトランザクション原子性・分離性を保障するための、複数のサーバを跨った排他制御機構が必須である。
【０００７】
すなわち、アプリケーション上のトランザクション（グローバル・トランザクション）の各処理を、ＫＶＳ上の複数トランザクション（ローカル・トランザクション）として処理することで、分散トランザクションをＫＶＳ上で実現可能である。より具体的には次のようにする。
− まず、ＫＶＳのバリューを、ロックの状態（ロックを保持するグローバル・トランザクションＩＤとロックの種類）とコミット済みのバリュー、更新中のバリューとする。
− また、管理用マップをKVS上に別途用意し、グローバル・トランザクションの開始時は、管理用マップにグローバル・トランザクションの状態を追加する、ローカル・トランザクションを処理する。
− 照会・更新処理は、ロックの状態、コミット済みのバリュー、更新中のバリューを照会・更新するローカル・トランザクションとして処理する。
− コミット・ロールバック処理は、複数のローカル・トランザクションとして実現する。そして、照会・更新した全てのキーごとに、ロックの状態、コミット済みのバリュー、更新中のバリューを更新するローカル・トランザクションとする。
【０００８】
このような手法の例として、「オープンソース徹底活用 Slim3 on Google App Engine for Java」ひがやすお・小川信一著、秀和システム、p.241-251に記述された手法がある。そこには、Google App Engineでグローバル・トランザクションを実現する方法が開示されている。
【０００９】
また、http://research.google.com/pubs/pub36726.htmlには、Google Percolatorが記述されている。
【００１０】
従来技法は、アプリケーションが異常終了する場合を想定し、管理用マップをKVSに用意し、トランザクションの状態（Working, Committed、Aborted）を管理する。そのとき、照会時、ロックを保持していると思われるトランザクションの状態が、Committed、Abortedの場合は、それぞれ、コミット済みのバリュー、更新前のバリューを利用可能となる。しかし、このようなシステムにおいては、ロックが競合した際には、分離性を保障するには、いかなる場合も、ロールバックする必要がある。
【００１１】
http://labs.google.com/papers/chubby.htmlに記述されている、Google Chubbyは、分散ロック機構を利用することにより、分散トランザクションを実現可能とする。しかし、別途分散ロック機構を構築することは、ソフトウェア開発コスト及び管理コストが余分にかかる。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−１８８５１８号公報
【非特許文献】
【００１３】
【非特許文献１】「オープンソース徹底活用 Slim3 on Google App Engine for Java」ひがやすお・小川信一著、秀和システム、p.241-251
【非特許文献２】http://research.google.com/pubs/pub36726.html
【非特許文献３】http://labs.google.com/papers/chubby.html
【発明の概要】
【発明が解決しようとする課題】
【００１４】
この発明の目的は、シンプルな構成のＫＶＳ上で、ロールバックを不必要に発生させることなく、分散トランザクションを実現することにある。
【課題を解決するための手段】
【００１５】
本発明は、各サーバの排他制御機構を用いて、各サーバでのローカル・トランザクションの原子性・分離性が保障される分散ＫＶＳ上で、トランザクション間のロックの依存関係を保持し、ロックの開放待ちをＫＶＳの排他制御機構を用いて認識することによって、上記課題を解決する。
【００１６】
より具体的には、本発明のシステムは、キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする、管理用マップを用意する。
【００１７】
そして、[TxID]をグローバル・トランザクションＩＤとするグローバル・トランザクションの開始処理では、本発明のシステムは、ＫＶＳ上で、管理用マップのキー [TxID]を管理するサーバ上で、管理用ローカル・トランザクションを開始する。次に、管理用ローカル・トランザクションで、[TxID]をキー、{working, null}をバリューとするキー・バリュー・ペア（Key-Value Pair）を挿入する。この管理用ローカル・トランザクションは、グローバル・トランザクションが終了（コミットもしくはロールバック）する際、もしくは、グローバル・トランザクションが他のグローバル・トランザクションのロック開放待ちとなるまで、終了しない。
【００１８】
[TxID]をグローバル・トランザクションＩＤとするグローバル・トランザクションが、[終了待ちTxID]のグローバル・トランザクションの終了を待機する処理では、本発明のシステムは、管理用ローカル・トランザクションで、 [TxID]をキーとするバリューを、{waiting, [終了待ちTxID]}に更新し、管理用ローカル・トランザクションをコミットする。次に、管理用マップのキー [終了待ちTxID] を管理するサーバ上で、ロック開放待ち用ローカル・トランザクションを開始し、キー[終了待ちTxID]のバリューを照会する。
【００１９】
このとき、照会したバリューが存在しない、もしくは、バリューにおけるグローバル・トランザクションの状態がcommitted、abortedの場合、本発明のシステムは、ロック開放待ち用ローカル・トランザクションをコミットし、再度管理用ローカル・トランザクションを開始、 [TxID]をキーとするバリューを、{working,null}に更新し、ロックの競合が終了したことを通知する（再度、競合している可能性はある）。
【００２０】
一方、照会したバリューにおける、 [終了待ちTxID]の状態がwaitingで、バリューとして、さらに終了待ちTxIDリストが存在する場合、本発明のシステムは、ロック開放待ち用ローカル・トランザクションをコミットし、[TxID]の終了待ちTxIDリストにこの終了待ちTxIDリストを追加して新たな[TxID]の終了待ちTxIDリストを生成する。そして、再度[TxID]をキーとして管理するサーバ上で管理用ローカル・トランザクションを開始して、[TxID]のグローバル・トランザクションの状態をwaitingに、また、[TxID]の終了待ちTxIDリストを新たに生成したリストに更新し、コミットする。 コミット後、新たに生成した[TxID]の終了待ちTxIDリストの末尾のTxIDのグローバル・トランザクションに対する終了待機処理を行う。なお、[TxID]が、新たに生成した[TxID]の終了待ちTxIDリスト内に含まれる場合は、ロールバックの処理を行い、アプリケーションにロールバックを通知する。これは、デッドロックの可能性がある。
【００２１】
トランザクションをコミットまたはロールバックする場合、本発明のシステムは、管理用ローカル・トランザクションにおいて、 [TxID]をキーとするバリューを、{committed,null}、もしくは、 {aborted,null}に更新し、管理用ローカル・トランザクションをコミットする。
【発明の効果】
【００２２】
この発明によれば、シンプルなＫＶＳにおいても。キー・バリュー・ペアのパーティショニングを考慮する必要がなく、利用用途が広がる。従来は、シンプルなＫＶＳは、銀行口座の振替用アプリケーションは、ユーザーIDごとにデータを複数サーバに分割する場合、使えなかった。
【００２３】
また、この発明によれば、ＫＶＳ上で、分散ロック機構を別途実装する必要なく、分散トランザクションを実現することができる。
【００２４】
さらに、この発明に従う、管理用マップに対するトランザクション処理、アプリケーション用マップに対するトランザクション処理は、サーバ増加分だけスループットを増加させることができる。また、ロックの競合発生時にも、ロックを待機させるため、オーバヘッドは少ない。
【００２５】
結局、この発明によれば、管理マップの排他ロックをトランザクション中維持し続けることにより、不用意なロールバックを減らすことができるという効果が得られる。
【図面の簡単な説明】
【００２６】
【図１】本発明の実施するためのシステム全体の概要図である。
【図２】クライアント・コンピュータのハードウェアの概要ブロック図である。
【図３】サーバのハードウェアの概要ブロック図である。
【図４】クライアント・コンピュータとサーバにおける機能ブロック図である。
【図５】従来のＫＶＳシステムの概要を示す図である。
【図６】従来のＫＶＳシステムの概要を示す図である。
【図７】従来のＫＶＳシステムの概要を示す図である。
【図８】本発明の従来のＫＶＳシステムの概要を示す図である。
【図９】トランザクションの開始時の処理のフローチャートを示す図である。
【図１０】照会時の処理のフローチャートを示す図である。
【図１１】更新時の処理のフローチャートを示す図である。
【図１２】コミット時の処理のフローチャートを示す図である。
【図１３】あるトランザクションが、別トランザクションの終了を待機する処理のフローチャートを示す図である。
【図１４】ロールバック時の処理のフローチャートを示す図である。
【図１５】トランザクションの処理の一例を示す図である。
【図１６】トランザクションの処理の一例を示す図である。
【図１７】トランザクションの処理の一例を示す図である。
【図１８】トランザクションの処理の一例を示す図である。
【発明を実施するための形態】
【００２７】
以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことに留意されたい。
【００２８】
図１は、本発明の実施するためのシステムの全体を示す概要図である。図１において、複数のクライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、インターネット１０４を介して、ＨＴＴＰなどのプロトコルにより、分散処理システム１０６にアクセスする。
【００２９】
分散処理システム１０６は、ＬＡＮまたはＷＡＮなどの仕組みにより相互接続された複数のサーバ１０６ａ、１０６ｂ、・・・、１０６ｚをもつ。分散サーバ・システム１０６は、キー・バリュー・ストア（ＫＶＳ）の仕組みで、分散データベースを構築するシステムである。すなわち、各サーバ１０６ａ、１０６ｂ、・・・、１０６ｚにはＩＤが付与され、この方式には限定されないが、好適には、キーのハッシュ・バリューのmodを計算することで、そのキーを保持するサーバが一意的に決まる。
【００３０】
従って、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、照会するキーで、アクセスするサーバ１０６ａ、１０６ｂ、・・・、１０６ｚが決定される。好適には、サーバ１０６ａ、１０６ｂ、・・・、１０６ｚのうちの一台がカタログ・サーバと呼ばれるサーバで、そこには、他のサーバに格納されているキーその他の情報が格納され、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、カタログ・サーバに一旦アクセスして、サーバ１０６ａ、１０６ｂ、・・・、１０６ｚのうちのどのサーバにアクセスするかの情報を取得してから、指示されたサーバとの接続を確立する。あるいは、クライアント・コンピュータがアクセスした任意のサーバが他の複数のサーバにブロードキャストして、情報を取得する方式も使用できる。以下での説明では便宜上、クライアント・コンピュータが、目的とするサーバを見つけて接続を確立したところから説明する。
【００３１】
クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、分散処理システム１０６にアクセスするために、一意的なグローバル・トランザクションＩＤを生成して、その後の分散処理システム１０６とのトランザクションに、そのグローバル・トランザクションＩＤを使用する。
【００３２】
次に、図２を参照して、図１で参照番号１０２ａ、１０２ｂ・・・１０２ｚのように示されているクライアント・コンピュータのハードウェア構成について、説明する。図２において、クライアント・コンピュータは、主記憶２０６、ＣＰＵ２０４、ＩＤＥコントローラ２０８をもち、これらは、バス２０２に接続されている。バス２０２には更に、ディスプレイ・コントローラ２１４と、通信インターフェース２１８と、ＵＳＢインターフェース２２０と、オーディオ・インターフェース２２２と、キーボード・マウス・コントローラ２２８が接続されている。ＩＤＥコントローラ２０８には、ハードディスク・ドライブ（ＨＤＤ）２１０と、ＤＶＤドライブ２１２が接続されている。ＤＶＤドライブ２１２は、必要に応じて、ＣＤ−ＲＯＭやＤＶＤから、プログラムを導入するために使用する。ディスプレイ・コントローラ２１４には、好適には、ＬＣＤ画面をもつディスプレイ装置２１６が接続されている。ディスプレイ装置２１６には、Ｗｅｂブラウザを通じて、アプリケーションの画面が表示される。
【００３３】
ＵＳＢインターフェース２２０には、必要に応じて、拡張ハードディスクなどのデバイスを接続をすることができる。
【００３４】
キーボード・マウス・コントローラ２２８には、キーボード２３０と、マウス２３２が接続されている。キーボード２３０は、検索のためのキーデータや、パスワードなどを打ち込むために使用される。
【００３５】
ＣＰＵ２０４は、例えば、３２ビット・アーキテクチャまたは６４ビット・アーキテクチャに基づく任意のものでよく、インテル社のＰｅｎｔｉｕｍ（インテル・コーポレーションの商標）４、Ｃｏｒｅ（商標）２ Ｄｕｏ、ＡＭＤ社のＡｔｈｌｏｎ（商標）などを使用することができる。
【００３６】
ハードディスク・ドライブ２１０には、少なくとも、オペレーティング・システムと、、分散処理システム１０６にアクセスするためのクライアント側のアプリケーション・プログラム４０２ａ（図４）が格納されており、システムの起動時に、オペレーティング・システムは、メインメモリ２０６にロードされる。オペレーティング・システムは、Ｗｉｎｄｏｗｓ ＸＰ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ Ｖｉｓｔａ（マイクロソフト・コーポレーションの商標）、Ｗｉｎｄｏｗｓ（マイクロソフト・コーポレーションの商標） ７、Ｌｉｎｕｘ（Linus Torvaldsの商標）などを使用することができる。クライアント側のアプリケーション・プログラム４０２ａは、図４のブロック図や、図９〜図１４のフローチャートを参照して、後で詳細に説明する。
【００３７】
通信インターフェース２１８は、オペレーティング・システムが提供するＴＣＰ／ＩＰ通信機能を利用して、イーサネット（商標）・プロトコルなどにより、インターネット１０４を介して、分散処理システム１０６と通信する。
【００３８】
図３は、分散処理システム１０６における、サーバ１０６ａなどのハードウェア構成の概要ブロック図である。図示されているように、インターネット１０４を介して、サーバ１０６ａ、１０６ａ、・・・１０６ｚが接続されている。サーバ１０６ａ、１０６ａ、・・・１０６ｚは基本的に同一の構成なので、ここでは代表的にサーバ１０６ａを示す。図３に示すように、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚは、インターネット１０４を経由して、サーバ１０６ａの通信インターフェース３０２に接続される。通信インターフェース３０２はさらに、バス３０４に接続され、バス３０４には、ＣＰＵ３０６、主記憶（ＲＡＭ）３０８、及びハードディスク・ドライブ（ＨＤＤ）３１０が接続されている。
【００３９】
図示しないが、サーバ１０６ａにはさらに、キーボード、マウス、及びディスプレイが接続され、これらによって、保守担当者が、サーバ１０６全体の管理やメンテナンス作業を行うようにしてもよい。
【００４０】
サーバ１０６ａのハードディスク・ドライブ３１０には、オペレーティング・システムが保存されている。
【００４１】
ハードディスク・ドライブ３１０にはさらに、サーバ１０６ａをＷｅｂサーバとして機能させるためのＡｐａｃｈｅなどのソフトウェア、及びＪａｖａ仮想環境を実現するＪａｖａ ＥＥ、及びＪａｖａ仮想環境上で動作する本発明に係る後述するアプリケーション・プログラム４０２ａが保存され、サーバ１０６ａの立ち上げ時に、主記憶３０８にロードされて、動作する。これによって、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚが、ＴＣＰ／ＩＰのプロトコルで、サーバ１０６にアクセスすることが可能となる。
【００４２】
サーバ１０６ａのハードディスク・ドライブ３１０にはさらに、IBM(R) WebSphere eXtreme ScaleなどのＫＶＳを実現するためのソフトウェアが保存されている。ハードディスク・ドライブ３１０にはまた、本発明に従う、ＫＶＳ用のトランザクション処理プログラム４０６ａ（図４）が保存されている。このトランザクション処理プログラム４０６ａの機能については、図４のブロック図や、図９〜図１４のフローチャートを参照して、後で詳細に説明する。
【００４３】
尚、上記サーバ１０６ａとして、インターナョナル・ビジネス・マシーンズ・コーポレーションから購入可能な、ＩＢＭ（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）System X、System i、System pなどの機種のサーバを使うことができる。その際、使用可能なオペレーティング・システムは、AIX（インターナョナル・ビジネス・マシーンズ・コーポレーションの商標）、UNIX(The Open Groupの商標)、Linux(商標)、Windows(商標)2003 Serverなどがある。
【００４４】
図４は、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚと、サーバ１０６ａ、１０６ｂ、・・・１０６ｚの各々における、処理プログラムの概要ブロック図を示す。なおここでは代表的に、クライアント・コンピュータ１０２ａとサーバ１０６ａを示す。
【００４５】
クライアント・コンピュータ側のアプリケーション・プログラム４０２ａは、ハードティスク・ドライブ２１０に保存されており、クライアント・コンピュータのユーザーの所定の操作で主記憶２０２にロードされて実行され、クライアント・コンピュータから、サーバ上にあるＫＶＳシステムに対して、トランザクションの開始、データの照会、データの更新、コミットなどの処理を指示する機能をもつ。
【００４６】
アプリケーション・プログラム４０２ａは、システム全体で一意的なグローバル・トランザクションＩＤ(TxID)を生成する機能４０４ａをもつ。グローバル・トランザクションＩＤの生成方法の１つの例は、クライアント・コンピュータ１０２ａ、１０２ｂ・・・１０２ｚと、サーバ１０６ａ、１０６ｂ、・・・１０６ｚの各々に固有のＩＤを付与しておき、各クライアント・コンピュータでトランザクションを開始する度に、そのクライアント・コンピュータのＩＤ＋クライアント・コンピュータ内の増分される通し番号をグローバル・トランザクションＩＤとすることであるが、システム全体で一意的なグローバル・トランザクションＩＤになるようにする任意の方法を使用してもよい。
【００４７】
アプリケーション・プログラム４０２ａは、グローバル・トランザクションＩＤを生成してサーバ１０６ａにアクセスすることができるが、別グローバル・トランザクションＩＤを生成することにより、同時に複数のサーバにアクセスすることができる。
【００４８】
サーバ１０６ａのハードティスク・ドライブ３１０には、トランザクション処理プログラム４０６ａと、例えばIBM(R) WebSphere eXtreme ScaleであるＫＶＳプログラム４０８ａと、ＫＶＳプログラム４０８ａによって参照される、キー(KEY)とバリュー(VALUE)のペアが保存され、トランザクション処理プログラム４０６ａとＫＶＳプログラム４０８ａは、サーバ１０６ａのスタートアップ時に、主記憶３０８にロードされて動作する。
【００４９】
トランザクション処理プログラム４０６ａは、クライアント・コンピュータ１０２ａからの、グローバル・トランザクションＩＤを伴うリクエストに応答して、レコードのロック、ロールバックなどの動作を行うようにＫＶＳプログラム４０８ａを制御するとともに、好適には主記憶３０８に、グローバル・トランザクションＩＤと、状態と、待ちグローバル・トランザクションＩＤを含むエントリをもつ管理用マップ４１２ａを作成して、サーバ毎に維持する。
【００５０】
さて、本発明に従うＫＶＳシステムの構成と動作を説明する前に、従来の典型的ないくつかのＫＶＳシステムの構成と動作を説明する。これらを参照することにより、本発明に従うシステムの特徴がより明らかになるものと思量する。
【００５１】
図５は、従来の典型的なＫＶＳの構成を示す図である。ここで改めてＫＶＳについて説明すると、図示されているように、データはデータ５０２ａ、５０２ｂ、５０２ｃ、５０２ｄのように分割され、複数のサーバ１０２ａ、１０２ｂ、１０２ｃ、１０２ｄに分散して配置される。クライアント・コンピュータ１０２ａは、１台のサーバに対して、トランザクション処理を要求する。このとき。互いに素(disjoint)になるように、データは分散配置されている。データを配置するサーバは、好適には、キーのハッシュ・バリューのmodを計算することで決定される。
【００５２】
クライアント・コンピュータ１０２ａは、begin（トランザクションを開始する）、put（バリューを対応付ける）、get（対応するバリューを取得する）、commit（コミット、すなわち更新を確定する）などのコマンドを、キーのバリューによって決まるサーバに送って処理を要求する。
【００５３】
このような従来構成のＫＶＳは、分散トランザクションをサポートしていないので、各トランザクションでの更新範囲が複雑な場合、利用できない。トランザクションでの更新範囲が複雑になる例として、銀行口座の振込み、特に各口座残高を分散配置した場合や、ショッピングサイトにおいて、アカウント毎の履歴と、商品の在庫数を分散配置した場合がある。
【００５４】
そこで、図６のようなＫＶＳの構成が実現された。この構成においては、データを格納するフィールドを拡張して、dirty updateを格納するフィールドNEXTと、ロックバージョンを格納するVERのフィールドを、参照番号６０２ａ、６０２ｂ、６０２ｃ、６０２ｄに示すように追加した。
【００５５】
これによれば、クライアント１０２ａは、データにアクセスする前にロックを獲得する。そして、更新時、dirty updateとロックのバージョンを書き込む。一方、分散ロック機構６０４が別途設けられて、コミットされたロックのバージョンを管理する。その際、ロック獲得が成功したにも拘らず、NEXTバリューが存在する場合は、NEXTバリューをNOWバリューに変更し、ロック・バージョンを更新して、処理を続行する。このような仕組みにより、分散トランザクションは実現可能である。しかし、別途分散ロック機構６０４を構築することは、ソフトウェアの開発コスト、管理コストの上昇につながる。
【００５６】
そこで、別途の分散ロック機構を用いない、図７に示すようなＫＶＳの構成が提案された。この構成では、データのテーブル７０２ａ、７０２ｂ、７０２ｃ、７０２ｄ以外に、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄに、グローバル・トランザクションＩＤ(TxID)及びトランザクションの状態とからなる、トランザクションの状態を記録する管理テーブル７０４ａ、７０４ｂ、７０４ｃ、７０４ｄをそれぞれ別途設ける。この構成では、クライアント１０２ａは、照会したバージョンを記録し、照会したバージョンが更新されていない場合のみコミット可能とする。そして、コミット後、別トランザクションで、トランザクション状態を更新し、バリューを更新する。
【００５７】
この構成では、競合時、すなわち複数のクライアントが同一のデータを更新する場合、既存のトランザクションの状態をローバック状態にする。これによって、分散トランザクションは実現可能であるが、楽観的トランザクションしか実現できない。また、既存の製品のみで実現可能であるが、競合が発生した場合、ロールバックが多発し、性能が向上しない可能性がある。
【００５８】
図８は、図７に示すようなＫＶＳの構成を改善した、本発明の構成を示す。ここでの参照番号は、図４の機能ブロック図に対応する。すなわち、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄに、グローバル・トランザクションＩＤ(TxID)及びトランザクションの状態と、終了待ちグローバル・トランザクションＩＤとからなる、管理用マップ４１２ａ、４１２ｂ、４１２ｃ、４１２ｄをそれぞれ別途設ける。そこで、STATEのフィールドに格納されるのがトランザクションの状態であり、WAITのフィールドに格納されるのが終了待ちグローバル・トランザクションＩＤである。
【００５９】
また、各サーバ１０６ａ、１０６ｂ、１０６ｃ、１０６ｄには、ＫＶＳのデータを格納するテーブル（データ・マップ）４１０ａ、４１０ｂ、４１０ｃ、４１０ｄも設けられる。データ・マップ４１０ａ、４１０ｂ、４１０ｃ、４１０ｄはそれぞれ、キーを入れるフィールドであるKEYと、コミット確定済みのバリューを入れるフィールドであるNOWと、更新中のバリューを格納するフィールドNEXTと、ロック状態、すなわち更新中のグローバル・トランザクションＩＤ TxIDを格納するフィールドWRITINGと、照会中のグローバル・トランザクションＩＤTxIDsを格納するREADINGをもつ。
【００６０】
この構成では、クライアント１０２ａは、ロックの情報を照会・更新毎に更新する。そして、ロックが競合時、トランザクションの状態を更新し、終了待ちトランザクションの状態を監視する。コミットの後、クライアント１０２ａは、トランザクション状態を更新し、別トランザクションでバリューを更新する。
【００６１】
複数のクライアントが、同一のデータを更新する場合、すなわち競合時、競合するトランザクションの終了を既存のロック機構を利用することで、待機する。
【００６２】
次に、本発明の処理のデータ構造とインターフェースについて説明する。
想定するＫＶＳのマップ・インタフェースは、次のとおりである。
get(key) ：keyに対する共有ロックを獲得し、対応するvalueを取得する。
put(key,value) ：keyに対する排他ロックを獲得し、valueを対応付ける。
cas(key,prev, value) ：keyに対する排他ロックを獲得し、バリューがprevだった場合に、valueを対応付ける。
remove(key) ：keyに対する排他ロックを獲得し、valueを削除する。
commit() ：keyに対する更新を確定し、獲得した全てのロックを開放する。
【００６３】
マップ構成（1つの分散マップをアプリケーションが利用することを想定）
トランザクションの状態管理用のマップ（TxStateMap）。これは、図８に示すテーブル４１２ａ、４１２ｂ、４１２ｃなどである。
key : TxID （グローバル・トランザクションＩＤ）
value: 状態 (Working|Committed|Rollbacked|Waiting) (STATE)、待機中TxID(WAITING)。
データ管理とロックの状態管理用のマップ (DataMap)。これは、図８に示すデータ・マップ４１０ａ、４１０ｂ、４１０ｃなどである。
key： アプリケーションが指定するkey
value： コミット確定済みのバリュー(NOW)、更新中のバリュー(NEXT)、ロック状態、すなわち更新中のグローバル・トランザクションＩＤ (WRITING)、照会中のグローバル・トランザクションＩＤのリスト(READING)。
【００６４】
また、トランザクションを実行中のクライアントがもつ状態として、以下のものがある。
TxID
− グローバル・トランザクションＩＤ
− これは、トランザクション開始時に生成される。
DirtyList
− 更新中のDataMapのバリュー
ReadingKeyList
− 照会中のDataMapのkey
さらにこの実施例では、終了済みTxIDリストとして、FinishTxIDsも用意される。
【００６５】
次に、図９〜図１４のフローチャートを参照して、本発明の処理について説明する。図９〜図１４のフローチャートの動作を通して、基本的には、クライアント・コンピュータから指示が出され、その指示に応答して、サーバで処理が行われ、必要に応じてサーバからクライアントに応答が返される態様である。
【００６６】
まず図９は、トランザクションの開始時の処理のフローチャートを示す。この処理は基本的に、クライアント・コンピュータ１０２ａ、１０２ｂ、・・・１０２ｚのアプリケーション・プログラム４０２ａ、４０２ｂ、・・・４０２ｚのどれかで実行される。
【００６７】
ステップ９０２では、クライアント・コンピュータは、クライアント・コンピュータ固有のＩＤ＋クライアント・コンピュータ内の増分される通し番号等により、グローバル・トランザクションＩＤ TxIDを生成する。
【００６８】
ステップ９０４では、クライアント・コンピュータ１０２ａは、初期状態INIT.STATE = Working、INIT.WAITING = {}とし、グローバル・トランザクションＩＤ(TxID)を以って、対応するサーバ１０６ａのトランザクションの状態管理用のマップTxStateMapに対して、put(TxID,INIT)を実行する。このとき、コミットはしない。この管理用のマップに対するトランザクションは、管理用ローカル・トランザクションと呼ばれる。なお、ここでクライアント・コンピュータ１０２ａとサーバ１０６ａの組み合わせを例にとって説明しているが、実際上、クライアント・コンピュータ１０２ａ、１０２ｂ、・・・１０２ｚとサーバ１０６ａ、１０６ｂ、・・・１０６ｚの任意の組み合わせがありえることに留意されたい。また、実際上、クライアント・コンピュータ１０２ａのアプリケーション・プログラム４０４ａがサーバに対するトランザクションを実行するが、以下の説明では便宜上、クライアント・コンピュータ１０２ａが実行すると記述する。
【００６９】
図１０は、照会時の処理、すなわち、mapに対してkeyのバリューを照会する場合の処理のフローチャートを示す図である。図１０のステップ１００２では、クライアント・コンピュータ１０２ａは、対応するサーバ１０６ａのトランザクション処理プログラム４０６ａに問い合わせして、DataMap.put(key)という問い合わせを行い、その結果のエントリをVに格納する。そして、DataMap.commit()により、コミットする。
【００７０】
ステップ１００４では、クライアント・コンピュータ１０２ａからの指示で、サーバ１０２ａが、NEW = Vで、Vを一旦NEWにコピーし、NEW.READING.add(TxID)により、データ・マップ(DataMap)４１０ａのREADINGフィールドにTxIDを格納する。
【００７１】
ステップ１００６では、サーバ１０６ａは、V.WRITING == NULLかどうか判断し、そうでないなら、ステップ１００８は、V.WRITINGのトランザクションの終了を待機する。そして、ステップ１０１０で、V.WRITINGがコミット済みかどうか判断し、もしそうなら、ステップ１０１２で、NEW.NOW = NEW.NEXTと格納し、NEW.NEXT = NULLとする。そうでなければステップ１０１４で単に、NEW.NEXT = NULLとする。こうして次にステップ１０１６に進む。
【００７２】
ステップ１００６でV.WRITING == NULLであると判断されたなら、直接ステップ１０１６に進む。
【００７３】
ステップ１０１６では、クライアント・コンピュータ１０２ａは、DataMap.cas(key,V,NEW)をトランザクション処理プログラム４０６ａに指示し、次にトランザクション処理プログラム４０６ａは、DataMap.commit()により、コミットする。
【００７４】
サーバ１０６ａは、ステップ１０１８で、CASが成功したかどうかを判断し、もしそうなら、ステップ１０２０で、ReadingKeyList.add(key)により、keyをReadingKeyListに追加して、処理を終える。ステップ１０１８で、CASが成功しなかったと判断されると、処理はステップ１００２に戻る。
【００７５】
図１１は、更新時の処理、すなわち、mapに対してkeyのバリューをv'に更新する場合の処理のフローチャートを示す図である。図１１のステップ１１０２では、クライアント・コンピュータ１０２ａは、トランザクション処理プログラム４０６ａにDataMap.put(key)という問い合わせを行い、するとサーバ１０６ａは、その結果のエントリをVに格納する。そして、DataMap.commit()により、コミットする。
【００７６】
ステップ１１０４では、サーバ１０６ａは、DIRTY = Vで、Vを一旦DIRTYにコピーし、DIRTY.NEXT = v'とセットし、さらに、DIRTY.WRITING = TxIDとセットする。
【００７７】
ステップ１１０６では、サーバ１０６ａは、V.WRITING == TxIDかどうか判断し、そうでないなら、ステップ１１０８で、V.WRITING == NULLかどうか判断する。もしそうでないなら、ステップ１１１０で、V.WRITINGのTxに対する終了処理の待機を行う。次にステップ１１１２では、V.WRITINGがコミット済みかどうか判断し、そうならDIRTY.NOW = V.NEXTとしてステップ１１１６に進む。V.WRITINGがコミット済みでないなら、直接ステップ１１１６に進む。一方、ステップ１１０８で、V.WRITING == NULLであると判断された場合、直接ステップ１１１６に進む。
【００７８】
ステップ１１１６では、サーバ１０６ａは、DIRTY.READING.remove(TxID)により、DIRTY.READINGからTxIDを除去する。
【００７９】
ステップ１１１８では、サーバ１０６ａは、V.READING.isEmpty()により、V.READINGが空かどうか判断する。もし空であればステップ１１２２に進み、空でなければステップ１１２０で、DIRTY.READING中の全トランザクションに対する終了待機処理を行う。
【００８０】
こうして、ステップ１１０６でYESの場合、ステップ１１１８でYESの場合、あるいはステップ１１２０に続いて、ステップ１１２２では、サーバ１０６ａは、DIRTY.READING = {}, DataMap.cas(key,V,DIRTY)及びDataMap.commit()を実行する。
【００８１】
ステップ１１２４では、サーバ１０６ａは、CASが成功したかどうかを判断し、もしそうなら、ステップ１１２６で、ReadingKeyList.remove(key)で、ReadingKeyListからkeyを除去し、DirtyList.add(DIRTY)により、DirtyListにDIRTYを追加する。一方、CASが成功しなかったと判断したら、処理はステップ１１０２に戻る。
【００８２】
図１２は、コミット時の処理のフローチャートを示す図である。コミット時には、ステップ１２０２で、前の状態であるPrevState.STATEにWorkingがセットされ、新しい状態であるNewState.STATEにCommittedがセットされ、TxStateMap.cas(TxID, PrevState, NewState)を実行した後、TxStateMap.commit()が実行される。
【００８３】
次のステップ１２０４で、サーバ１０６ａは、ＣＡＳが成功したかどうかを判断し、そうでなければステップ１２０６でのロールバック処理に行く。ここでＣＡＳが失敗したということは、他のトランザクションから強制的にアボートされたことを意味する。
【００８４】
一方、ＣＡＳが成功したなら、ステップ１２０８で、サーバ１０６ａは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ１２１０で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ１２１２でReadingKeyList中のCASが成功していないkeyを選択し、ステップ１２１４で、
V = DataMap.get(key)
NEW = V
V.READING.remove(TxID)
DataMap.cas(key,V,NEW)
DataMap.commit()
を実行し、ＣＡＳが成功しない限りステップ１２１２に戻る。ＣＡＳが成功するとステップ１２１０に進み、そして、ステップ１２１０でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。
【００８５】
ステップ１２０８に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ１０６ａは、ステップ１２１８でDirtyList中の選択していないバリュー(DIRTY)を選択し、ステップ１２２０で
NEW = DIRTY
NEW.NEXT = NULL
NEW.NOW = DIRTY.NEXT
NEW.WRITING = NULL
を実行し、ステップ１２２２でDataMap.cas(key,DIRTY,NEW)、DataMap.commit()を実行して、ステップ１２０８に戻る。
【００８６】
図１３は、TxIDをグローバル・トランザクションＩＤとするトランザクションが、TgtTxIDをグローバル・トランザクションＩＤとするトランザクションの終了を待機する処理のフローチャートを示す図である。
【００８７】
ステップ１３０２では、クライアント・コンピュータ１０２ａは、サーバ１０２ａのトランザクション処理プログラム４０６ａに働きかけて、
WorkingState.STATE = Working
WaitState.STATE = Waiting
WaitState.WAITING = {TgtTxID}
TxStateMap.cas(TxID,WorkingState,WaitState)
TxStateMap.commit()
を実行する。
【００８８】
そしてステップ１３０４で、サーバ１０６ａは、ＣＡＳが成功したかどうかを判断する。ここでＣＡＳが成功しなかったということは、他のトランザクションから強制的にアボートされたということであり、ステップ１３０６でロールバック処理を行う。
【００８９】
ＣＡＳが成功したと判断されると、サーバ１０６ａは、ステップ１３０８で、TgtState = TxStateMap.get(TgtTxID)を実行し、次にTxStateMap.commit()を実行する。ここでgetが実行されるのは、TgtTxIDのトランザクションがWaiting、Committed、Rollbacked時のみである。
【００９０】
ステップ１３１０では、サーバ１０６ａは、TgtState.WAITING.contained(TxID)、すなわち、TgtStateのWAITINGに、TxIDが含まれているかどうかを判断する。もしそうでなければ、デッドロックの可能性ありとして、ステップ１３０６でロールバック処理を行う。
【００９１】
ステップ１３１０で、TgtStateのWAITINGに、TxIDが含まれていると判断されると、ステップ１３１２で、TgtState.STATEがCommittedまたはRollbackedのどちらかであるかどうかが判断され、もしそうなら、ステップ１３２２に進んで、サーバ１０６ａは、TxStateMap.cas(TxID,WaitState,WorkingState)とFinishTxID.add(WaitingTxID)を実行し、その結果ステップ１３２４で、ＣＡＳが成功したかどうか判断し、もし成功なら処理を終わり、そうでなければ、ステップ１３２６でロールバック処理を行う。
【００９２】
ステップ１３１２に戻って、TgtState.STATEがCommittedまたはRollbackedのどちらでもないなら、サーバ１０６ａは、ステップ１３１４で、TgtTxIDはゾンビ、すなわち、長時間Waitingであるかどうか、判断する。もしそうなら、ステップ１３１８に進み、そこで、下記の処理を行う。
NewTgtState.STATE = Rollbacked
TxStateMap.cas(TgtTxID,TgtState,NewTgtState)
TxStateMap.commit()
【００９３】
ステップ１３２０で、サーバ１０６ａは、ＣＡＳが成功したかどうか判断し、もし成功ならステップ１３２２に進み、そうでないなら、ステップ１３０８に戻る。
【００９４】
ステップ１３１４に戻って、TgtTxIDはゾンビでないと判断されると、ステップ１３１６に進み、そこで、下記の処理を行う。
PrevWaitState = WaitState
// これは、WaitStateをPrevWaitStateにコピーする処理である。
WaitState.WAITING.addAll(TgtState.WAITING)
// これは、WaitState.WAITINGのすべてのグローバル・トランザクションＩＤをWaitState.WAITINGに追加する。
TxStateMap.cas(key,prevWaitState,WaitState)
TxStateMap.commit()
TgtTxID = TgtState.tail()
// これは、TgtState.WAITINGの最後にリストされているグローバル・トランザクションＩＤをTgtTxIDに代入するものである。
そして処理は、ステップ１３０４に戻る。
【００９５】
図１４は、ロールバック時の処理のフローチャートを示す図である。図１４において、ステップ１４０２で、前の状態であるPrevState.STATEにWorkingがセットされ、新しい状態であるNewState.STATEにCommittedがセットされ、TxStateMap.cas(TxID, PrevState, NewState)を実行した後、TxStateMap.commit()が実行される。
【００９６】
次に、ステップ１４０４で、サーバ１０６ａは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ１４０６で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ１４０８でReadingKeyList中のCASが成功していないkeyを選択し、ステップ１４１０で、
V = DataMap.get(key)
NEW = V
V.READING.remove(TxID)
DataMap.cas(key,V,NEW)
DataMap.commit()
を実行し、ＣＡＳが成功しない限りステップ１４０８に戻る。そして、ステップ１２１０でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。
【００９７】
ステップ１２０８に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ１０６ａは、ステップ１４１４でDirtyList中の選択していないバリュー(DIRTY)を選択し、ステップ１４１６で
NEW = DIRTY
NEW.NEXT = NULL
NEW.NOW = DIRTY.NEXT
NEW.WRITING = NULL
を実行し、ステップ１４１８でDataMap.cas(key,DIRTY,NEW)、DataMap.commit()を実行して、ステップ１４０４に戻る。
【００９８】
次に、図１５〜図１８の例を参照して、本発明のいくつかの典型的な処理の例を示す。なお、以下では説明の便宜上、データ・マップ(DataMap)におけるNOW、NEXTのバリューは省略する。また、図１５〜図１８において、sは共有ロック(Shared)、ｘは排他ロック(eXclusive)をあらわす。
【００９９】
まず図１５は、Tx1がK1を照会後、コミットする例を示す。図１５の１では、クライアント・コンピュータがトランザクションTx1を開始し、これによって、管理マップ４１２ａのKEYにTx1が格納され、STATEがWorkingとなる。
【０１００】
図１５の２で、Tx1が共有ロックK1を獲得すると、データ・マップ４１０ａのKEYにK1が格納され、データ・マップ４１０ａのREADINGに{Tx1}が格納される。
【０１０１】
図１５の３で、Tx1のコミット処理が行われ、管理マップ４１２ａのSTATEがCommittedになる。
【０１０２】
図１５の４で、Tx1の更なるコミット処理が行われ、データ・マップ４１０ａのREADINGが｛｝になる。
【０１０３】
図１６は、Tx1がK1を照会中、Tx2がK1の更新を試行し、Tx1のコミット後に処理されるという例を示す。
【０１０４】
図１６の１では、Tx1がK1を照会中であることを示す。図１６の２では、Tx2が共有ロックK1を獲得しようとするが、Tx1がK1を照会中なので、Tx2の照会はブロックされる。管理マップ４１２ａのKEY = Tx2のエントリのWAITINGには、{Tx1}が入る。
【０１０５】
図１６の３では、Tx1のコミット処理終了後Tx2が照会可能となり、図１６の４では、Tx2が共有ロックK1を獲得再開する。これに応答して、管理マップ４１２ａのKEY = Tx2のエントリのSTATEがWorkingになり、WAITINGは{}になる。
【０１０６】
図１６の５では、Tx2の更新処理が開始され、データ・マップ４１０ａのKey = K1に対応するWRITINGにTx2が格納される。
【０１０７】
図１７は、Tx1の終了をTx2が待機し、Tx2の終了をTx3が待機する場合、Tx1が終了時にTx2が稼動を開始し、Tx3が依然としてTx2を待機する例を示す。
【０１０８】
図１７の１では、管理マップ４１２ａのエントリが示すように、Tx1のコミットを、Tx2が待機中である。図１７の２では、Tx2が照会中のK2をTx3が更新開始する。ここでTx3は、Tx2がTx1待ちと認識する。
【０１０９】
図１７の３では、Tx3がTx1を待機中になる。このことは、管理マップ４１２ａのKEY = Tx3に対応する、WAITINGの{Tx2,Tx1}というエントリによって示される。
【０１１０】
図１７の４は、Tx1がコミットされて終了した後に、Tx3がTx2待ちになる様子を示す。
【０１１１】
図１８は、Tx1、Tx2、Tx3でデッドロックした場合、Tx1がロールバックする処理の例を示す。図１８の１では、Tx1、Tx3がTx1を待機中になる。図１８の２では、Tx1がTx3の照会中のバリューの更新を試みる。
【０１１２】
しかし、管理マップ４１２ａのエントリから見て取れるように、Tx3に対応するエントリのWAITINGにTx1が含まれるため、図１８の３に示すように、Tx1はロールバックする。
【０１１３】
すると、図１８の４に示すように、Tx1のロールバック後、管理マップ４１２ａのTx2とTx3のエントリのWAITINGのフィールドからTx1が消去され、Tx3はTx2待ちになる。この際、Tx1のSTATEをRollbackedにする前に、Tx2とTx3がTx1のSTATEを照会した場合は、すべてのトランザクションがロールバックするが、原子性は保障される。
【０１１４】
以上、特定のハードウェア及びソフトウェアのプラットアフォームの上で本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを、この分野の当業者なら理解するであろう。
【符号の説明】
【０１１５】
１０２ クライアント・コンピュータ
１０６ サーバ
２０２ 主記憶
２０４ ＣＰＵ
２０６ メインメモリ
２０６ 主記憶
２１０ ハードディスク・ドライブ
３０６ ＣＰＵ
３０８ 主記憶
３１０ ハードディスク・ドライブ
４０４ アプリケーション・プログラム
４０６ トランザクション処理プログラム
４０８ ＫＶＳプログラム
４１０ データ・マップ
４１２ 管理用マップ
【特許請求の範囲】
【請求項１】
複数のサーバをもち、該各サーバが排他制御機構を有し、前記各サーバにおけるトランザクション原子性・分離性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現する方法であって、
コンピュータの処理によって、キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、あらかじめ、用意するステップと、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始するステップと、
前記コンピュータの処理によって、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入するステップと、
前記コンピュータの処理によって、前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットするステップを有する、
分散キーバリューストア・システムの制御方法。
【請求項２】
前記コンピュータの処理によって、処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会するステップと、
前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知するステップをさらに有する、
請求項１に記載の方法。
【請求項３】
前記コンピュータの処理によって、終了待ちグローバル・トランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーとするバリューを照会するステップと、
前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューが{waitingという状態, 終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}の場合、
前記ロック開放待ち用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストに終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストを追加して、処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストを生成し、
再度管理用ローカル・トランザクションを開始し、
処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリスト}に更新し、
管理用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストの末尾のグローバル・トランザクションIDを終了待ちグローバル・トランザクションIDとして、請求項２におけるグローバル・トランザクションの終了待機処理を行うステップをさらに有する、
請求項１に記載の方法。
【請求項４】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項１に記載の方法。
【請求項５】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項１に記載の方法。
【請求項６】
複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現するプログラムあって、
前記システムに、
キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、あらかじめ、用意するステップと、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始するステップと、
前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入するステップと、
前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットするステップを実行させる、
プログラム。
【請求項７】
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会するステップと、
前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知するステップをさらに有する、
請求項６に記載のプログラム。
【請求項８】
終了待ちグローバル・トランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーとするバリューを照会するステップと、
前記管理用マップにおいて、前記照会したバリューが{waitingという状態, 終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}の場合、
前記ロック開放待ち用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストに終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストを追加して、処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストを生成し、
再度管理用ローカル・トランザクションを開始し、
処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリスト}に更新し、
管理用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストの末尾のグローバル・トランザクションIDを終了待ちグローバル・トランザクションIDとして、請求項６におけるグローバル・トランザクションの終了待機処理を行うステップをさらに有する、
請求項６に記載のプログラム。
【請求項９】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項６に記載のプログラム。
【請求項１０】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項６に記載のプログラム。
【請求項１１】
複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現するシステムあって、
メモリと、
キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、前記メモリにあらかじめ、用意する手段と、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始する手段と、
前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入する手段と、
前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットする手段を有する、
システム。
【請求項１２】
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会する手段と、
前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知する手段をさらに有する、
請求項１１に記載のシステム。
【請求項１３】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットする手段をさらに有する、請求項１１に記載のシステム。
【請求項１４】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットする手段をさらに有する、請求項１１に記載のシステム。
【請求項１】
複数のサーバをもち、該各サーバが排他制御機構を有し、前記各サーバにおけるトランザクション原子性・分離性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現する方法であって、
コンピュータの処理によって、キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、あらかじめ、用意するステップと、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始するステップと、
前記コンピュータの処理によって、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入するステップと、
前記コンピュータの処理によって、前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットするステップを有する、
分散キーバリューストア・システムの制御方法。
【請求項２】
前記コンピュータの処理によって、処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会するステップと、
前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知するステップをさらに有する、
請求項１に記載の方法。
【請求項３】
前記コンピュータの処理によって、終了待ちグローバル・トランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーとするバリューを照会するステップと、
前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューが{waitingという状態, 終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}の場合、
前記ロック開放待ち用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストに終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストを追加して、処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストを生成し、
再度管理用ローカル・トランザクションを開始し、
処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリスト}に更新し、
管理用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストの末尾のグローバル・トランザクションIDを終了待ちグローバル・トランザクションIDとして、請求項２におけるグローバル・トランザクションの終了待機処理を行うステップをさらに有する、
請求項１に記載の方法。
【請求項４】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項１に記載の方法。
【請求項５】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項１に記載の方法。
【請求項６】
複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現するプログラムあって、
前記システムに、
キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、あらかじめ、用意するステップと、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始するステップと、
前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入するステップと、
前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットするステップを実行させる、
プログラム。
【請求項７】
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会するステップと、
前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知するステップをさらに有する、
請求項６に記載のプログラム。
【請求項８】
終了待ちグローバル・トランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーとするバリューを照会するステップと、
前記管理用マップにおいて、前記照会したバリューが{waitingという状態, 終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}の場合、
前記ロック開放待ち用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストに終了待ちグローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリストを追加して、処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストを生成し、
再度管理用ローカル・トランザクションを開始し、
処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリスト}に更新し、
管理用ローカル・トランザクションをコミットし、
処理対象グローバル・トランザクションの新たな終了待ちグローバル・トランザクションＩＤリストの末尾のグローバル・トランザクションIDを終了待ちグローバル・トランザクションIDとして、請求項６におけるグローバル・トランザクションの終了待機処理を行うステップをさらに有する、
請求項６に記載のプログラム。
【請求項９】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項６に記載のプログラム。
【請求項１０】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットするステップをさらに有する、請求項６に記載のプログラム。
【請求項１１】
複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストア・システムにおいて、各サーバ上でのローカル・トランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性・分離性を保つグローバル・トランザクション処理を実現するシステムあって、
メモリと、
キーをグローバル・トランザクションＩＤ、バリューを{グローバル・トランザクションの状態、終了待ちグローバル・トランザクションＩＤリスト}とする管理用マップを全てのグローバル・トランザクションの開始前に、前記メモリにあらかじめ、用意する手段と、
前記コンピュータの処理によって、ある処理対象グローバル・トランザクションを開始時に、前記複数のサーバのうちの１つのサーバで、前記管理用ローカル・トランザクションを開始する手段と、
前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションのＩＤをキーとし、{workingという状態,null}をバリューとするキー・バリュー・ペアを前記管理用マップに挿入する手段と、
前記管理用ローカル・トランザクションで、前記管理用マップにおいて、処理対象グローバル・トランザクションＩＤをキーとするバリューを、{waitingという状態, 処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト}に更新して、前記管理用ローカル・トランザクションをコミットする手段を有する、
システム。
【請求項１２】
処理対象グローバル・トランザクションの終了待ちグローバル・トランザクションＩＤリスト内の末尾の終了待ちグローバル・トランザクションＩＤを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバル・トランザクションＩＤをキーするバリューを照会する手段と、
前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバル・トランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカル・トランザクションを再度開始して、グローバル・トランザクションＩＤをキーとするバリューを、{workingという状態,null}に更新し、ロックの競合が終了したことを通知する手段をさらに有する、
請求項１１に記載のシステム。
【請求項１３】
前記処理対象グローバル・トランザクションをコミットする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{committed,{}}に更新し、前記管理用ローカル・トランザクションをコミットする手段をさらに有する、請求項１１に記載のシステム。
【請求項１４】
前記処理対象グローバル・トランザクションをロールバックする場合、前記管理用ローカル・トランザクションで、前記処理対象グローバル・トランザクションＩＤをキーとするバリューを{ aborted,{}}に更新し、前記管理用ローカル・トランザクションをコミットする手段をさらに有する、請求項１１に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２０１３−３３３４５（Ｐ２０１３−３３３４５Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１１−１６８４６１（Ｐ２０１１−１６８４６１）
【出願日】平成２３年８月１日（２０１１．８．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＪＡＶＡ
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願日】平成２３年８月１日（２０１１．８．１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＪＡＶＡ
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
[ Back to top ]