複数のサーバをもち、該各サーバが排他制御機構を有し、前記各サーバにおけるトランザクション原子性分離性が保障される分散キーバリューストアシステムにおいて、各サーバ上でのローカルトランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性分離性を保つグローバルトランザクション処理を実現する方法であって、コンピュータの処理によって、キーをグローバルトランザクションID、バリューをグローバルトランザクションの状態、終了待ちグローバルトランザクションIDリストとする管理用マップを全てのグローバルトランザクションの開始前に、あらかじめ、用意するステップと、前記コンピュータの処理によって、ある処理対象グローバルトランザクションを開始時に、前記複数のサーバのうちの1つのサーバで、前記管理用ローカルトランザクションを開始するステップと、前記コンピュータの処理によって、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションのIDをキーとし、workingという状態nullをバリューとするキーバリューペアを前記管理用マップに挿入するステップと、前記コンピュータの処理によって、前記管理用ローカルトランザクションで、前記管理用マップにおいて、処理対象グローバルトランザクションIDをキーとするバリューを、waitingという状態処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリストに更新して、前記管理用ローカルトランザクションをコミットするステップを有する、分散キーバリューストアシステムの制御方法。前記コンピュータの処理によって、処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリスト内の末尾の終了待ちグローバルトランザクションIDを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバルトランザクションIDをキーするバリューを照会するステップと、前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバルトランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカルトランザクションを再度開始して、グローバルトランザクションIDをキーとするバリューを、workingという状態nullに更新し、ロックの競合が終了したことを通知するステップをさらに有する、請求項1に記載の方法。前記コンピュータの処理によって、終了待ちグローバルトランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバルトランザクションIDをキーとするバリューを照会するステップと、前記コンピュータの処理によって、前記管理用マップにおいて、前記照会したバリューがwaitingという状態終了待ちグローバルトランザクションの終了待ちグローバルトランザクションIDリストの場合、前記ロック開放待ち用ローカルトランザクションをコミットし、処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリストに終了待ちグローバルトランザクションの終了待ちグローバルトランザクションIDリストを追加して、処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストを生成し、再度管理用ローカルトランザクションを開始し、処理対象グローバルトランザクションIDをキーとするバリューを、waitingという状態処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストに更新し、管理用ローカルトランザクションをコミットし、処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストの末尾のグローバルトランザクションIDを終了待ちグローバルトランザクションIDとして、請求項2におけるグローバルトランザクションの終了待機処理を行うステップをさらに有する、請求項1に記載の方法。前記処理対象グローバルトランザクションをコミットする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをcommittedに更新し、前記管理用ローカルトランザクションをコミットするステップをさらに有する、請求項1に記載の方法。前記処理対象グローバルトランザクションをロールバックする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをabortedに更新し、前記管理用ローカルトランザクションをコミットするステップをさらに有する、請求項1に記載の方法。複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストアシステムにおいて、各サーバ上でのローカルトランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性分離性を保つグローバルトランザクション処理を実現するプログラムあって、前記システムに、キーをグローバルトランザクションID、バリューをグローバルトランザクションの状態、終了待ちグローバルトランザクションIDリストとする管理用マップを全てのグローバルトランザクションの開始前に、あらかじめ、用意するステップと、前記コンピュータの処理によって、ある処理対象グローバルトランザクションを開始時に、前記複数のサーバのうちの1つのサーバで、前記管理用ローカルトランザクションを開始するステップと、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションのIDをキーとし、workingという状態nullをバリューとするキーバリューペアを前記管理用マップに挿入するステップと、前記管理用ローカルトランザクションで、前記管理用マップにおいて、処理対象グローバルトランザクションIDをキーとするバリューを、waitingという状態処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリストに更新して、前記管理用ローカルトランザクションをコミットするステップを実行させる、プログラム。処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリスト内の末尾の終了待ちグローバルトランザクションIDを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバルトランザクションIDをキーするバリューを照会するステップと、前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバルトランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカルトランザクションを再度開始して、グローバルトランザクションIDをキーとするバリューを、workingという状態nullに更新し、ロックの競合が終了したことを通知するステップをさらに有する、請求項6に記載のプログラム。終了待ちグローバルトランザクションIDを管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバルトランザクションIDをキーとするバリューを照会するステップと、前記管理用マップにおいて、前記照会したバリューがwaitingという状態終了待ちグローバルトランザクションの終了待ちグローバルトランザクションIDリストの場合、前記ロック開放待ち用ローカルトランザクションをコミットし、処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリストに終了待ちグローバルトランザクションの終了待ちグローバルトランザクションIDリストを追加して、処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストを生成し、再度管理用ローカルトランザクションを開始し、処理対象グローバルトランザクションIDをキーとするバリューを、waitingという状態処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストに更新し、管理用ローカルトランザクションをコミットし、処理対象グローバルトランザクションの新たな終了待ちグローバルトランザクションIDリストの末尾のグローバルトランザクションIDを終了待ちグローバルトランザクションIDとして、請求項6におけるグローバルトランザクションの終了待機処理を行うステップをさらに有する、請求項6に記載のプログラム。前記処理対象グローバルトランザクションをコミットする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをcommittedに更新し、前記管理用ローカルトランザクションをコミットするステップをさらに有する、請求項6に記載のプログラム。前記処理対象グローバルトランザクションをロールバックする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをabortedに更新し、前記管理用ローカルトランザクションをコミットするステップをさらに有する、請求項6に記載のプログラム。複数のサーバをもち、該複数のサーバが排他制御機構を有し、前記サーバにおけるトランザクション原子性が保障される分散キーバリューストアシステムにおいて、各サーバ上でのローカルトランザクション処理を組み合わせることで、全サーバ上でのトランザクション原子性分離性を保つグローバルトランザクション処理を実現するシステムあって、メモリと、キーをグローバルトランザクションID、バリューをグローバルトランザクションの状態、終了待ちグローバルトランザクションIDリストとする管理用マップを全てのグローバルトランザクションの開始前に、前記メモリにあらかじめ、用意する手段と、前記コンピュータの処理によって、ある処理対象グローバルトランザクションを開始時に、前記複数のサーバのうちの1つのサーバで、前記管理用ローカルトランザクションを開始する手段と、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションのIDをキーとし、workingという状態nullをバリューとするキーバリューペアを前記管理用マップに挿入する手段と、前記管理用ローカルトランザクションで、前記管理用マップにおいて、処理対象グローバルトランザクションIDをキーとするバリューを、waitingという状態処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリストに更新して、前記管理用ローカルトランザクションをコミットする手段を有する、システム。処理対象グローバルトランザクションの終了待ちグローバルトランザクションIDリスト内の末尾の終了待ちグローバルトランザクションIDを、管理用マップのキーとして管理する前記サーバ上で、ロック開放待ちトランザクションを開始し、終了待ちグローバルトランザクションIDをキーするバリューを照会する手段と、前記管理用マップにおいて、前記照会したバリューが存在しない、もしくは、バリューにおける終了待ちグローバルトランザクションの状態が、committedまたはabortedであることに応答して、前記ロック開放待ちトランザクションをコミットし、管理用ローカルトランザクションを再度開始して、グローバルトランザクションIDをキーとするバリューを、workingという状態nullに更新し、ロックの競合が終了したことを通知する手段をさらに有する、請求項11に記載のシステム。前記処理対象グローバルトランザクションをコミットする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをcommittedに更新し、前記管理用ローカルトランザクションをコミットする手段をさらに有する、請求項11に記載のシステム。前記処理対象グローバルトランザクションをロールバックする場合、前記管理用ローカルトランザクションで、前記処理対象グローバルトランザクションIDをキーとするバリューをabortedに更新し、前記管理用ローカルトランザクションをコミットする手段をさらに有する、請求項11に記載のシステム。この発明の目的は、シンプルな構成のKVS上で、ロールバックを不必要に発生させることなく、分散トランザクションを実現することにある。本発明は、各サーバの排他制御機構を用いて、各サーバでのローカルトランザクションの原子性分離性が保障される分散KVS上で、トランザクション間のロックの依存関係を保持し、ロックの開放待ちをKVSの排他制御機構を用いて認識することによって、上記課題を解決する。より具体的には、本発明のシステムは、キーをグローバルトランザクションID、バリューをグローバルトランザクションの状態、終了待ちグローバルトランザクションIDリストとする、管理用マップを用意する。そして、TxIDをグローバルトランザクションIDとするグローバルトランザクションの開始処理では、本発明のシステムは、KVS上で、管理用マップのキーTxIDを管理するサーバ上で、管理用ローカルトランザクションを開始する。次に、管理用ローカルトランザクションで、TxIDをキー、workingnullをバリューとするキーバリューペアKeyValuePairを挿入する。この管理用ローカルトランザクションは、グローバルトランザクションが終了コミットもしくはロールバックする際、もしくは、グローバルトランザクションが他のグローバルトランザクションのロック開放待ちとなるまで、終了しない。TxIDをグローバルトランザクションIDとするグローバルトランザクションが、終了待ちTxIDのグローバルトランザクションの終了を待機する処理では、本発明のシステムは、管理用ローカルトランザクションで、TxIDをキーとするバリューを、waiting終了待ちTxIDに更新し、管理用ローカルトランザクションをコミットする。次に、管理用マップのキー終了待ちTxIDを管理するサーバ上で、ロック開放待ち用ローカルトランザクションを開始し、キー終了待ちTxIDのバリューを照会する。このとき、照会したバリューが存在しない、もしくは、バリューにおけるグローバルトランザクションの状態がcommitted、abortedの場合、本発明のシステムは、ロック開放待ち用ローカルトランザクションをコミットし、再度管理用ローカルトランザクションを開始、TxIDをキーとするバリューを、workingnullに更新し、ロックの競合が終了したことを通知する再度、競合している可能性はある。一方、照会したバリューにおける、終了待ちTxIDの状態がwaitingで、バリューとして、さらに終了待ちTxIDリストが存在する場合、本発明のシステムは、ロック開放待ち用ローカルトランザクションをコミットし、TxIDの終了待ちTxIDリストにこの終了待ちTxIDリストを追加して新たなTxIDの終了待ちTxIDリストを生成する。そして、再度TxIDをキーとして管理するサーバ上で管理用ローカルトランザクションを開始して、TxIDのグローバルトランザクションの状態をwaitingに、また、TxIDの終了待ちTxIDリストを新たに生成したリストに更新し、コミットする。コミット後、新たに生成したTxIDの終了待ちTxIDリストの末尾のTxIDのグローバルトランザクションに対する終了待機処理を行う。なお、TxIDが、新たに生成したTxIDの終了待ちTxIDリスト内に含まれる場合は、ロールバックの処理を行い、アプリケーションにロールバックを通知する。これは、デッドロックの可能性がある。トランザクションをコミットまたはロールバックする場合、本発明のシステムは、管理用ローカルトランザクションにおいて、TxIDをキーとするバリューを、committednull、もしくは、abortednullに更新し、管理用ローカルトランザクションをコミットする。この発明によれば、シンプルなKVSにおいても。キーバリューペアのパーティショニングを考慮する必要がなく、利用用途が広がる。従来は、シンプルなKVSは、銀行口座の振替用アプリケーションは、ユーザーIDごとにデータを複数サーバに分割する場合、使えなかった。また、この発明によれば、KVS上で、分散ロック機構を別途実装する必要なく、分散トランザクションを実現することができる。さらに、この発明に従う、管理用マップに対するトランザクション処理、アプリケーション用マップに対するトランザクション処理は、サーバ増加分だけスループットを増加させることができる。また、ロックの競合発生時にも、ロックを待機させるため、オーバヘッドは少ない。結局、この発明によれば、管理マップの排他ロックをトランザクション中維持し続けることにより、不用意なロールバックを減らすことができるという効果が得られる。以下、図面を参照して、本発明の実施例を説明する。特に断わらない限り、同一の参照番号は、図面を通して、同一の対象を指すものとする。また、以下で説明するのは、本発明の一実施形態であり、この発明を、この実施例で説明する内容に限定する意図はないことに留意されたい。図1は、本発明の実施するためのシステムの全体を示す概要図である。図1において、複数のクライアントコンピュータ102a、102b102zは、インターネット104を介して、HTTPなどのプロトコルにより、分散処理システム106にアクセスする。分散処理システム106は、LANまたはWANなどの仕組みにより相互接続された複数のサーバ106a、106b、、106zをもつ。分散サーバシステム106は、キーバリューストアKVSの仕組みで、分散データベースを構築するシステムである。すなわち、各サーバ106a、106b、、106zにはIDが付与され、この方式には限定されないが、好適には、キーのハッシュバリューのmodを計算することで、そのキーを保持するサーバが一意的に決まる。従って、クライアントコンピュータ102a、102b102zは、照会するキーで、アクセスするサーバ106a、106b、、106zが決定される。好適には、サーバ106a、106b、、106zのうちの一台がカタログサーバと呼ばれるサーバで、そこには、他のサーバに格納されているキーその他の情報が格納され、クライアントコンピュータ102a、102b102zは、カタログサーバに一旦アクセスして、サーバ106a、106b、、106zのうちのどのサーバにアクセスするかの情報を取得してから、指示されたサーバとの接続を確立する。あるいは、クライアントコンピュータがアクセスした任意のサーバが他の複数のサーバにブロードキャストして、情報を取得する方式も使用できる。以下での説明では便宜上、クライアントコンピュータが、目的とするサーバを見つけて接続を確立したところから説明する。クライアントコンピュータ102a、102b102zは、分散処理システム106にアクセスするために、一意的なグローバルトランザクションIDを生成して、その後の分散処理システム106とのトランザクションに、そのグローバルトランザクションIDを使用する。次に、図2を参照して、図1で参照番号102a、102b102zのように示されているクライアントコンピュータのハードウェア構成について、説明する。図2において、クライアントコンピュータは、主記憶206、CPU204、IDEコントローラ208をもち、これらは、バス202に接続されている。バス202には更に、ディスプレイコントローラ214と、通信インターフェース218と、USBインターフェース220と、オーディオインターフェース222と、キーボードマウスコントローラ228が接続されている。IDEコントローラ208には、ハードディスクドライブHDD210と、DVDドライブ212が接続されている。DVDドライブ212は、必要に応じて、CD-ROMやDVDから、プログラムを導入するために使用する。ディスプレイコントローラ214には、好適には、LCD画面をもつディスプレイ装置216が接続されている。ディスプレイ装置216には、Webブラウザを通じて、アプリケーションの画面が表示される。USBインターフェース220には、必要に応じて、拡張ハードディスクなどのデバイスを接続をすることができる。キーボードマウスコントローラ228には、キーボード230と、マウス232が接続されている。キーボード230は、検索のためのキーデータや、パスワードなどを打ち込むために使用される。CPU204は、例えば、32ビットアーキテクチャまたは64ビットアーキテクチャに基づく任意のものでよく、インテル社のPentiumインテルコーポレーションの商標4、Core商標2Duo、AMD社のAthlon商標などを使用することができる。ハードディスクドライブ210には、少なくとも、オペレーティングシステムと、、分散処理システム106にアクセスするためのクライアント側のアプリケーションプログラム402a図4が格納されており、システムの起動時に、オペレーティングシステムは、メインメモリ206にロードされる。オペレーティングシステムは、WindowsXPマイクロソフトコーポレーションの商標、WindowsVistaマイクロソフトコーポレーションの商標、Windowsマイクロソフトコーポレーションの商標7、LinuxLinusTorvaldsの商標などを使用することができる。クライアント側のアプリケーションプログラム402aは、図4のブロック図や、図9~図14のフローチャートを参照して、後で詳細に説明する。通信インターフェース218は、オペレーティングシステムが提供するTCP/IP通信機能を利用して、イーサネット商標プロトコルなどにより、インターネット104を介して、分散処理システム106と通信する。図3は、分散処理システム106における、サーバ106aなどのハードウェア構成の概要ブロック図である。図示されているように、インターネット104を介して、サーバ106a、106a、106zが接続されている。サーバ106a、106a、106zは基本的に同一の構成なので、ここでは代表的にサーバ106aを示す。図3に示すように、クライアントコンピュータ102a、102b102zは、インターネット104を経由して、サーバ106aの通信インターフェース302に接続される。通信インターフェース302はさらに、バス304に接続され、バス304には、CPU306、主記憶RAM308、及びハードディスクドライブHDD310が接続されている。図示しないが、サーバ106aにはさらに、キーボード、マウス、及びディスプレイが接続され、これらによって、保守担当者が、サーバ106全体の管理やメンテナンス作業を行うようにしてもよい。サーバ106aのハードディスクドライブ310には、オペレーティングシステムが保存されている。ハードディスクドライブ310にはさらに、サーバ106aをWebサーバとして機能させるためのApacheなどのソフトウェア、及びJava仮想環境を実現するJavaEE、及びJava仮想環境上で動作する本発明に係る後述するアプリケーションプログラム402aが保存され、サーバ106aの立ち上げ時に、主記憶308にロードされて、動作する。これによって、クライアントコンピュータ102a、102b102zが、TCP/IPのプロトコルで、サーバ106にアクセスすることが可能となる。サーバ106aのハードディスクドライブ310にはさらに、IBMWebSphereeXtremeScaleなどのKVSを実現するためのソフトウェアが保存されている。ハードディスクドライブ310にはまた、本発明に従う、KVS用のトランザクション処理プログラム406a図4が保存されている。このトランザクション処理プログラム406aの機能については、図4のブロック図や、図9~図14のフローチャートを参照して、後で詳細に説明する。尚、上記サーバ106aとして、インターナョナルビジネスマシーンズコーポレーションから購入可能な、IBMインターナョナルビジネスマシーンズコーポレーションの商標SystemX、Systemi、Systempなどの機種のサーバを使うことができる。その際、使用可能なオペレーティングシステムは、AIXインターナョナルビジネスマシーンズコーポレーションの商標、UNIX、Linux、Windows2003Serverなどがある。図4は、クライアントコンピュータ102a、102b102zと、サーバ106a、106b、106zの各々における、処理プログラムの概要ブロック図を示す。なおここでは代表的に、クライアントコンピュータ102aとサーバ106aを示す。クライアントコンピュータ側のアプリケーションプログラム402aは、ハードティスクドライブ210に保存されており、クライアントコンピュータのユーザーの所定の操作で主記憶202にロードされて実行され、クライアントコンピュータから、サーバ上にあるKVSシステムに対して、トランザクションの開始、データの照会、データの更新、コミットなどの処理を指示する機能をもつ。アプリケーションプログラム402aは、システム全体で一意的なグローバルトランザクションIDを生成する機能404aをもつ。グローバルトランザクションIDの生成方法の1つの例は、クライアントコンピュータ102a、102b102zと、サーバ106a、106b、106zの各々に固有のIDを付与しておき、各クライアントコンピュータでトランザクションを開始する度に、そのクライアントコンピュータのIDクライアントコンピュータ内の増分される通し番号をグローバルトランザクションIDとすることであるが、システム全体で一意的なグローバルトランザクションIDになるようにする任意の方法を使用してもよい。アプリケーションプログラム402aは、グローバルトランザクションIDを生成してサーバ106aにアクセスすることができるが、別グローバルトランザクションIDを生成することにより、同時に複数のサーバにアクセスすることができる。サーバ106aのハードティスクドライブ310には、トランザクション処理プログラム406aと、例えばIBMWebSphereeXtremeScaleであるKVSプログラム408aと、KVSプログラム408aによって参照される、キーとバリューのペアが保存され、トランザクション処理プログラム406aとKVSプログラム408aは、サーバ106aのスタートアップ時に、主記憶308にロードされて動作する。トランザクション処理プログラム406aは、クライアントコンピュータ102aからの、グローバルトランザクションIDを伴うリクエストに応答して、レコードのロック、ロールバックなどの動作を行うようにKVSプログラム408aを制御するとともに、好適には主記憶308に、グローバルトランザクションIDと、状態と、待ちグローバルトランザクションIDを含むエントリをもつ管理用マップ412aを作成して、サーバ毎に維持する。さて、本発明に従うKVSシステムの構成と動作を説明する前に、従来の典型的ないくつかのKVSシステムの構成と動作を説明する。これらを参照することにより、本発明に従うシステムの特徴がより明らかになるものと思量する。図5は、従来の典型的なKVSの構成を示す図である。ここで改めてKVSについて説明すると、図示されているように、データはデータ502a、502b、502c、502dのように分割され、複数のサーバ102a、102b、102c、102dに分散して配置される。クライアントコンピュータ102aは、1台のサーバに対して、トランザクション処理を要求する。このとき。互いに素になるように、データは分散配置されている。データを配置するサーバは、好適には、キーのハッシュバリューのmodを計算することで決定される。クライアントコンピュータ102aは、beginトランザクションを開始する、putバリューを対応付ける、get対応するバリューを取得する、commitコミット、すなわち更新を確定するなどのコマンドを、キーのバリューによって決まるサーバに送って処理を要求する。このような従来構成のKVSは、分散トランザクションをサポートしていないので、各トランザクションでの更新範囲が複雑な場合、利用できない。トランザクションでの更新範囲が複雑になる例として、銀行口座の振込み、特に各口座残高を分散配置した場合や、ショッピングサイトにおいて、アカウント毎の履歴と、商品の在庫数を分散配置した場合がある。そこで、図6のようなKVSの構成が実現された。この構成においては、データを格納するフィールドを拡張して、dirtyupdateを格納するフィールドNEXTと、ロックバージョンを格納するVERのフィールドを、参照番号602a、602b、602c、602dに示すように追加した。これによれば、クライアント102aは、データにアクセスする前にロックを獲得する。そして、更新時、dirtyupdateとロックのバージョンを書き込む。一方、分散ロック機構604が別途設けられて、コミットされたロックのバージョンを管理する。その際、ロック獲得が成功したにも拘らず、NEXTバリューが存在する場合は、NEXTバリューをNOWバリューに変更し、ロックバージョンを更新して、処理を続行する。このような仕組みにより、分散トランザクションは実現可能である。しかし、別途分散ロック機構604を構築することは、ソフトウェアの開発コスト、管理コストの上昇につながる。そこで、別途の分散ロック機構を用いない、図7に示すようなKVSの構成が提案された。この構成では、データのテーブル702a、702b、702c、702d以外に、各サーバ106a、106b、106c、106dに、グローバルトランザクションID及びトランザクションの状態とからなる、トランザクションの状態を記録する管理テーブル704a、704b、704c、704dをそれぞれ別途設ける。この構成では、クライアント102aは、照会したバージョンを記録し、照会したバージョンが更新されていない場合のみコミット可能とする。そして、コミット後、別トランザクションで、トランザクション状態を更新し、バリューを更新する。この構成では、競合時、すなわち複数のクライアントが同一のデータを更新する場合、既存のトランザクションの状態をローバック状態にする。これによって、分散トランザクションは実現可能であるが、楽観的トランザクションしか実現できない。また、既存の製品のみで実現可能であるが、競合が発生した場合、ロールバックが多発し、性能が向上しない可能性がある。図8は、図7に示すようなKVSの構成を改善した、本発明の構成を示す。ここでの参照番号は、図4の機能ブロック図に対応する。すなわち、各サーバ106a、106b、106c、106dに、グローバルトランザクションID及びトランザクションの状態と、終了待ちグローバルトランザクションIDとからなる、管理用マップ412a、412b、412c、412dをそれぞれ別途設ける。そこで、STATEのフィールドに格納されるのがトランザクションの状態であり、WAITのフィールドに格納されるのが終了待ちグローバルトランザクションIDである。また、各サーバ106a、106b、106c、106dには、KVSのデータを格納するテーブルデータマップ410a、410b、410c、410dも設けられる。データマップ410a、410b、410c、410dはそれぞれ、キーを入れるフィールドであるKEYと、コミット確定済みのバリューを入れるフィールドであるNOWと、更新中のバリューを格納するフィールドNEXTと、ロック状態、すなわち更新中のグローバルトランザクションIDTxIDを格納するフィールドWRITINGと、照会中のグローバルトランザクションIDTxIDsを格納するREADINGをもつ。この構成では、クライアント102aは、ロックの情報を照会更新毎に更新する。そして、ロックが競合時、トランザクションの状態を更新し、終了待ちトランザクションの状態を監視する。コミットの後、クライアント102aは、トランザクション状態を更新し、別トランザクションでバリューを更新する。複数のクライアントが、同一のデータを更新する場合、すなわち競合時、競合するトランザクションの終了を既存のロック機構を利用することで、待機する。次に、本発明の処理のデータ構造とインターフェースについて説明する。想定するKVSのマップインタフェースは、次のとおりである。get:keyに対する共有ロックを獲得し、対応するvalueを取得する。put:keyに対する排他ロックを獲得し、valueを対応付ける。cas:keyに対する排他ロックを獲得し、バリューがprevだった場合に、valueを対応付ける。remove:keyに対する排他ロックを獲得し、valueを削除する。commit:keyに対する更新を確定し、獲得した全てのロックを開放する。マップ構成1つの分散マップをアプリケーションが利用することを想定トランザクションの状態管理用のマップTxStateMap。これは、図8に示すテーブル412a、412b、412cなどである。keyTxIDグローバルトランザクションIDvalue状態、待機中TxID。データ管理とロックの状態管理用のマップ。これは、図8に示すデータマップ410a、410b、410cなどである。key:アプリケーションが指定するkeyvalue:コミット確定済みのバリュー、更新中のバリュー、ロック状態、すなわち更新中のグローバルトランザクションID、照会中のグローバルトランザクションIDのリスト。また、トランザクションを実行中のクライアントがもつ状態として、以下のものがある。TxID-グローバルトランザクションID-これは、トランザクション開始時に生成される。DirtyList-更新中のDataMapのバリューReadingKeyList-照会中のDataMapのkeyさらにこの実施例では、終了済みTxIDリストとして、FinishTxIDsも用意される。次に、図9~図14のフローチャートを参照して、本発明の処理について説明する。図9~図14のフローチャートの動作を通して、基本的には、クライアントコンピュータから指示が出され、その指示に応答して、サーバで処理が行われ、必要に応じてサーバからクライアントに応答が返される態様である。まず図9は、トランザクションの開始時の処理のフローチャートを示す。この処理は基本的に、クライアントコンピュータ102a、102b、102zのアプリケーションプログラム402a、402b、402zのどれかで実行される。ステップ902では、クライアントコンピュータは、クライアントコンピュータ固有のIDクライアントコンピュータ内の増分される通し番号等により、グローバルトランザクションIDTxIDを生成する。ステップ904では、クライアントコンピュータ102aは、初期状態INITSTATEWorking、INITWAITINGとし、グローバルトランザクションIDを以って、対応するサーバ106aのトランザクションの状態管理用のマップTxStateMapに対して、putを実行する。このとき、コミットはしない。この管理用のマップに対するトランザクションは、管理用ローカルトランザクションと呼ばれる。なお、ここでクライアントコンピュータ102aとサーバ106aの組み合わせを例にとって説明しているが、実際上、クライアントコンピュータ102a、102b、102zとサーバ106a、106b、106zの任意の組み合わせがありえることに留意されたい。また、実際上、クライアントコンピュータ102aのアプリケーションプログラム404aがサーバに対するトランザクションを実行するが、以下の説明では便宜上、クライアントコンピュータ102aが実行すると記述する。図10は、照会時の処理、すなわち、mapに対してkeyのバリューを照会する場合の処理のフローチャートを示す図である。図10のステップ1002では、クライアントコンピュータ102aは、対応するサーバ106aのトランザクション処理プログラム406aに問い合わせして、DataMapputという問い合わせを行い、その結果のエントリをVに格納する。そして、DataMapcommitにより、コミットする。ステップ1004では、クライアントコンピュータ102aからの指示で、サーバ102aが、NEWVで、Vを一旦NEWにコピーし、NEWREADINGaddにより、データマップ410aのREADINGフィールドにTxIDを格納する。ステップ1006では、サーバ106aは、VWRITINGNULLかどうか判断し、そうでないなら、ステップ1008は、VWRITINGのトランザクションの終了を待機する。そして、ステップ1010で、VWRITINGがコミット済みかどうか判断し、もしそうなら、ステップ1012で、NEWNOWNEWNEXTと格納し、NEWNEXTNULLとする。そうでなければステップ1014で単に、NEWNEXTNULLとする。こうして次にステップ1016に進む。ステップ1006でVWRITINGNULLであると判断されたなら、直接ステップ1016に進む。ステップ1016では、クライアントコンピュータ102aは、DataMapcasをトランザクション処理プログラム406aに指示し、次にトランザクション処理プログラム406aは、DataMapcommitにより、コミットする。サーバ106aは、ステップ1018で、CASが成功したかどうかを判断し、もしそうなら、ステップ1020で、ReadingKeyListaddにより、keyをReadingKeyListに追加して、処理を終える。ステップ1018で、CASが成功しなかったと判断されると、処理はステップ1002に戻る。図11は、更新時の処理、すなわち、mapに対してkeyのバリューをvに更新する場合の処理のフローチャートを示す図である。図11のステップ1102では、クライアントコンピュータ102aは、トランザクション処理プログラム406aにDataMapputという問い合わせを行い、するとサーバ106aは、その結果のエントリをVに格納する。そして、DataMapcommitにより、コミットする。ステップ1104では、サーバ106aは、DIRTYVで、Vを一旦DIRTYにコピーし、DIRTYNEXTvとセットし、さらに、DIRTYWRITINGTxIDとセットする。ステップ1106では、サーバ106aは、VWRITINGTxIDかどうか判断し、そうでないなら、ステップ1108で、VWRITINGNULLかどうか判断する。もしそうでないなら、ステップ1110で、VWRITINGのTxに対する終了処理の待機を行う。次にステップ1112では、VWRITINGがコミット済みかどうか判断し、そうならDIRTYNOWVNEXTとしてステップ1116に進む。VWRITINGがコミット済みでないなら、直接ステップ1116に進む。一方、ステップ1108で、VWRITINGNULLであると判断された場合、直接ステップ1116に進む。ステップ1116では、サーバ106aは、DIRTYREADINGremoveにより、DIRTYREADINGからTxIDを除去する。ステップ1118では、サーバ106aは、VREADINGisEmptyにより、VREADINGが空かどうか判断する。もし空であればステップ1122に進み、空でなければステップ1120で、DIRTYREADING中の全トランザクションに対する終了待機処理を行う。こうして、ステップ1106でYESの場合、ステップ1118でYESの場合、あるいはステップ1120に続いて、ステップ1122では、サーバ106aは、DIRTYREADINGDataMapcas及びDataMapcommitを実行する。ステップ1124では、サーバ106aは、CASが成功したかどうかを判断し、もしそうなら、ステップ1126で、ReadingKeyListremoveで、ReadingKeyListからkeyを除去し、DirtyListaddにより、DirtyListにDIRTYを追加する。一方、CASが成功しなかったと判断したら、処理はステップ1102に戻る。図12は、コミット時の処理のフローチャートを示す図である。コミット時には、ステップ1202で、前の状態であるPrevStateSTATEにWorkingがセットされ、新しい状態であるNewStateSTATEにCommittedがセットされ、TxStateMapcasを実行した後、TxStateMapcommitが実行される。次のステップ1204で、サーバ106aは、CASが成功したかどうかを判断し、そうでなければステップ1206でのロールバック処理に行く。ここでCASが失敗したということは、他のトランザクションから強制的にアボートされたことを意味する。一方、CASが成功したなら、ステップ1208で、サーバ106aは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ1210で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ1212でReadingKeyList中のCASが成功していないkeyを選択し、ステップ1214で、VDataMapgetNEWVVREADINGremoveDataMapcasDataMapcommitを実行し、CASが成功しない限りステップ1212に戻る。CASが成功するとステップ1210に進み、そして、ステップ1210でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。ステップ1208に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ106aは、ステップ1218でDirtyList中の選択していないバリューを選択し、ステップ1220でNEWDIRTYNEWNEXTNULLNEWNOWDIRTYNEXTNEWWRITINGNULLを実行し、ステップ1222でDataMapcas、DataMapcommitを実行して、ステップ1208に戻る。図13は、TxIDをグローバルトランザクションIDとするトランザクションが、TgtTxIDをグローバルトランザクションIDとするトランザクションの終了を待機する処理のフローチャートを示す図である。ステップ1302では、クライアントコンピュータ102aは、サーバ102aのトランザクション処理プログラム406aに働きかけて、WorkingStateSTATEWorkingWaitStateSTATEWaitingWaitStateWAITINGTgtTxIDTxStateMapcasTxStateMapcommitを実行する。そしてステップ1304で、サーバ106aは、CASが成功したかどうかを判断する。ここでCASが成功しなかったということは、他のトランザクションから強制的にアボートされたということであり、ステップ1306でロールバック処理を行う。CASが成功したと判断されると、サーバ106aは、ステップ1308で、TgtStateTxStateMapgetを実行し、次にTxStateMapcommitを実行する。ここでgetが実行されるのは、TgtTxIDのトランザクションがWaiting、Committed、Rollbacked時のみである。ステップ1310では、サーバ106aは、TgtStateWAITINGcontained、すなわち、TgtStateのWAITINGに、TxIDが含まれているかどうかを判断する。もしそうでなければ、デッドロックの可能性ありとして、ステップ1306でロールバック処理を行う。ステップ1310で、TgtStateのWAITINGに、TxIDが含まれていると判断されると、ステップ1312で、TgtStateSTATEがCommittedまたはRollbackedのどちらかであるかどうかが判断され、もしそうなら、ステップ1322に進んで、サーバ106aは、TxStateMapcasとFinishTxIDaddを実行し、その結果ステップ1324で、CASが成功したかどうか判断し、もし成功なら処理を終わり、そうでなければ、ステップ1326でロールバック処理を行う。ステップ1312に戻って、TgtStateSTATEがCommittedまたはRollbackedのどちらでもないなら、サーバ106aは、ステップ1314で、TgtTxIDはゾンビ、すなわち、長時間Waitingであるかどうか、判断する。もしそうなら、ステップ1318に進み、そこで、下記の処理を行う。NewTgtStateSTATERollbackedTxStateMapcasTxStateMapcommitステップ1320で、サーバ106aは、CASが成功したかどうか判断し、もし成功ならステップ1322に進み、そうでないなら、ステップ1308に戻る。ステップ1314に戻って、TgtTxIDはゾンビでないと判断されると、ステップ1316に進み、そこで、下記の処理を行う。PrevWaitStateWaitStateこれは、WaitStateをPrevWaitStateにコピーする処理である。WaitStateWAITINGaddAllこれは、WaitStateWAITINGのすべてのグローバルトランザクションIDをWaitStateWAITINGに追加する。TxStateMapcasTxStateMapcommitTgtTxIDTgtStatetailこれは、TgtStateWAITINGの最後にリストされているグローバルトランザクションIDをTgtTxIDに代入するものである。そして処理は、ステップ1304に戻る。図14は、ロールバック時の処理のフローチャートを示す図である。図14において、ステップ1402で、前の状態であるPrevStateSTATEにWorkingがセットされ、新しい状態であるNewStateSTATEにCommittedがセットされ、TxStateMapcasを実行した後、TxStateMapcommitが実行される。次に、ステップ1404で、サーバ106aは、DirtyListのすべてのバリューを選択したかどうかの判断を行う。もしそうなら、ステップ1406で、ReadingKeyList中の全てのバリューを選択したかどうかを判断し、そうでなければ、ステップ1408でReadingKeyList中のCASが成功していないkeyを選択し、ステップ1410で、VDataMapgetNEWVVREADINGremoveDataMapcasDataMapcommitを実行し、CASが成功しない限りステップ1408に戻る。そして、ステップ1210でReadingKeyList中の全てのバリューを選択したと判断されると、処理を終了する。ステップ1208に戻って、DirtyListのすべてのバリューを選択していないと判断されると、サーバ106aは、ステップ1414でDirtyList中の選択していないバリューを選択し、ステップ1416でNEWDIRTYNEWNEXTNULLNEWNOWDIRTYNEXTNEWWRITINGNULLを実行し、ステップ1418でDataMapcas、DataMapcommitを実行して、ステップ1404に戻る。次に、図15~図18の例を参照して、本発明のいくつかの典型的な処理の例を示す。なお、以下では説明の便宜上、データマップにおけるNOW、NEXTのバリューは省略する。また、図15~図18において、sは共有ロック、xは排他ロックをあらわす。まず図15は、Tx1がK1を照会後、コミットする例を示す。図15の1では、クライアントコンピュータがトランザクションTx1を開始し、これによって、管理マップ412aのKEYにTx1が格納され、STATEがWorkingとなる。図15の2で、Tx1が共有ロックK1を獲得すると、データマップ410aのKEYにK1が格納され、データマップ410aのREADINGにTx1が格納される。図15の3で、Tx1のコミット処理が行われ、管理マップ412aのSTATEがCommittedになる。図15の4で、Tx1の更なるコミット処理が行われ、データマップ410aのREADINGが{}になる。図16は、Tx1がK1を照会中、Tx2がK1の更新を試行し、Tx1のコミット後に処理されるという例を示す。図16の1では、Tx1がK1を照会中であることを示す。図16の2では、Tx2が共有ロックK1を獲得しようとするが、Tx1がK1を照会中なので、Tx2の照会はブロックされる。管理マップ412aのKEYTx2のエントリのWAITINGには、Tx1が入る。図16の3では、Tx1のコミット処理終了後Tx2が照会可能となり、図16の4では、Tx2が共有ロックK1を獲得再開する。これに応答して、管理マップ412aのKEYTx2のエントリのSTATEがWorkingになり、WAITINGはになる。図16の5では、Tx2の更新処理が開始され、データマップ410aのKeyK1に対応するWRITINGにTx2が格納される。図17は、Tx1の終了をTx2が待機し、Tx2の終了をTx3が待機する場合、Tx1が終了時にTx2が稼動を開始し、Tx3が依然としてTx2を待機する例を示す。図17の1では、管理マップ412aのエントリが示すように、Tx1のコミットを、Tx2が待機中である。図17の2では、Tx2が照会中のK2をTx3が更新開始する。ここでTx3は、Tx2がTx1待ちと認識する。図17の3では、Tx3がTx1を待機中になる。このことは、管理マップ412aのKEYTx3に対応する、WAITINGのTx2Tx1というエントリによって示される。図17の4は、Tx1がコミットされて終了した後に、Tx3がTx2待ちになる様子を示す。図18は、Tx1、Tx2、Tx3でデッドロックした場合、Tx1がロールバックする処理の例を示す。図18の1では、Tx1、Tx3がTx1を待機中になる。図18の2では、Tx1がTx3の照会中のバリューの更新を試みる。しかし、管理マップ412aのエントリから見て取れるように、Tx3に対応するエントリのWAITINGにTx1が含まれるため、図18の3に示すように、Tx1はロールバックする。すると、図18の4に示すように、Tx1のロールバック後、管理マップ412aのTx2とTx3のエントリのWAITINGのフィールドからTx1が消去され、Tx3はTx2待ちになる。この際、Tx1のSTATEをRollbackedにする前に、Tx2とTx3がTx1のSTATEを照会した場合は、すべてのトランザクションがロールバックするが、原子性は保障される。以上、特定のハードウェア及びソフトウェアのプラットアフォームの上で本発明の実施例を説明してきたが、本発明は、任意のコンピュータのハードウェア及びプラットフォームで実施可能であることを、この分野の当業者なら理解するであろう。