JP2003058404A - 分散データベースの同時実行制御システム - Google Patents

Abstract

(57)【要約】 【課題】 高い頑健性と、少ない通信量および遅延量を
実現する。 【解決手段】 同じデータを複数のデータベースサーバ
に冗長に配置して構成される分散データベースの同時実
行制御システムにおいて、各データベースサーバは、競
合演算操作の対象となるデータを指定するデータ指定情
報と、当該競合演算操作の内容を記述した操作情報と、
各データベースサーバにおいて該当するデータ指定情報
に関する該当する操作情報の競合演算操作が既に完了し
ているか否かを指定する操作完了情報とを有するトーク
ン構造体を、データベースサーバ間で巡回させ、受け取
った当該トークン構造体の有するデータ指定情報、操作
情報、および操作完了情報に応じたデータベース管理処
理を、自動的に起動するアクティブ起動手段を備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は分散データベースの
同時実行制御システムに関するものである。

【０００２】

【従来の技術】文献名：A.Goshinski, "Distributed
Operating Systems - The Logical Design" , A
ddison Wesley 信頼性向上、可用性向上、アクセス時間短縮、スループ
ット向上を目的として、データの複製を複数のサイトに
置く分散データベースがよく利用される。

【０００３】従来、このような分散データベースに対し
て複数のトランザクションが並行して更新を行なう可能
性がある場合に、一貫性のある更新を行なう方式とし
て、次の（１）〜（４）の方式がある。

【０００４】（１）全コピーロック方式 この方式では、全てのデータベースサイトのロックに成
功したトランザクションがデータの更新を行なう。実際
にはそのサイトのデータベース管理システム（以下、
「ＤＢＭＳ」と略す）が全てのサイトのデータの更新を
行なうことになる。

【０００５】全てのデータベースサイトのロックに成功
できなかったトランザクション、すなわち、１つでもロ
ックに失敗したトランザクションは、ロックを異常終了
（アボート）する。

【０００６】（２）多数決ロック方式 この方式では、過半数のデータベースサイトのロックに
成功したトランザクションがデータの更新を行なう。実
際にはそのサイトのＤＢＭＳが全てのサイトの更新を行
なうことになる。同一の重みで過半数を求めるのではな
く、重み付けを行なって投票する方法もある。

【０００７】この方式でも、前記全コピーロック方式と
同様、１つでもロックに失敗したトランザクションはロ
ックをアボートする。

【０００８】（３）プライマリコピー方式 この方式では、１つのデータに対してプライマリとなる
データベースサイトを固定し、ロックはプライマリデー
タに対してのみ行なう。そして、ロックに成功したら、
そのサイトのＤＢＭＳが全てのサイトの更新を行なう。

【０００９】（４）トークンパッシング この方式では、図２に示すように、関連するサイト１〜
６で論理的なリングを構成し、トークンをあるサイトの
ＤＢＭＳから別のサイトのＤＢＭＳへ渡す（例えば、サ
イト１からサイト２へ渡す）。トークンを渡されたＤＢ
ＭＳは自サイトのトランザクションで更新待ちになって
いるものがあるか調べ、あれば更新を行なう。トークン
の存在は、更新権の存在を意味する。

【００１０】当該（４）の方式では、図３に示すよう
に、例えばサイト５で、あるデータの更新が行われた場
合には、他の全サイトの当該データに対してもトークン
を受け取ったときにそれと同じ内容の更新を実行するこ
とにより、データの一貫性を保持することができる。

【００１１】

【発明が解決しようとする課題】しかし、以上述べたい
ずれの方式であっても頑健性と少ない通信量、遅延量を
同時に満足することはできない。

【００１２】すなわち、（１）、（２）の方式では必要
な数のロックに成功するまでに多くの通信量を要する
上、ロックに失敗した場合アボートし、ロックをやり直
さなければならない。

【００１３】また、（３）の方式は単純であるが、プラ
イマリデータのあるサイトに障害があれば全システムの
停止につながるという意味で脆弱である。またアクセス
が集中しやすく、効率面でも問題である。

【００１４】さらに、（４）の方式は、通信量は比較的
少ないが、更新するときは更新が終了するまで他のサイ
トヘトークンを渡さないため、遅延が大きい。

【００１５】また、どの方式も更新時に、更新を始める
サイトに負荷が集中するという問題がある。

【００１６】

【課題を解決するための手段】かかる課題を解決するた
めに、本発明では、同じデータを複数のデータベースサ
ーバに冗長に配置して構成される分散データベースの同
時実行制御システムにおいて、（１）各データベースサ
ーバは、競合演算操作の対象となるデータを指定するデ
ータ指定情報と、（２）当該競合演算操作の内容を記述
した操作情報と、（３）各データベースサーバにおいて
該当するデータ指定情報に関する該当する操作情報の競
合演算操作が既に完了しているか否かを指定する操作完
了情報とを有するトークン構造体を、データベースサー
バ間で巡回させ、（４）受け取った当該トークン構造体
の有するデータ指定情報、操作情報、および操作完了情
報に応じたデータベース管理処理を、自動的に起動する
アクティブ起動手段を備えることを特徴とする。

【００１７】

【発明の実施の形態】（Ａ）実施形態 以下、本発明にかかる分散データベースの同時実行制御
システムを、各データベースサーバのＤＢＭＳがリレー
ショナルモデルを提供する場合を例に、実施形態につい
て説明する。

【００１８】（Ａ−１）第１の実施形態の構成 本実施形態の同時実行制御システムの論理的な全体構成
例は、図２と同様で、サイト間で論理的なリング状のネ
ットワークを構成するものであってよい。なお、１サイ
ト内に複数のデータベースサーバが存在することも可能
であるため、サイトとデータベースサーバは必ずしも１
対１に対応しないが、ここでは、１つのサイト内にはた
だ１つのデータベースサーバが存在するものとする。

【００１９】各サイト内のデータベースサーバは、実質
的に同じ構成のＤＢＭＳ１０を有している。当該ＤＢＭ
Ｓ１０の主要部の構成例は、図１に示す通りである。

【００２０】（Ａ−１−１）ＤＢＭＳの構成例 区１において、当該ＤＢＭＳ１０は、データ格納部１１
と、アクティブプログラム実行環境部１２と、トランザ
クション制御部１４と、アクティブプログラム実行制御
部１３と、通信制御部１５とを備えている。

【００２１】このうちデータ格納部１１は実際のデータ
を格納する物理的なデータベースである。リレーショナ
ルモデルに対応する本実施形態の場合、当該データ格納
部１１は関係データベースなので、格納されるデータの
データ構造は２次元のテーブル（すなわち、関係表）の
形態を有している。また、各サイトにおけるデータ格納
部１１は、同じ論理データベースの断片であってよい。
断片は、論理データベースの関係表を、射影、制約によ
って分割することにより生成され得る。

【００２２】当該データ格納部１１が格納しているデー
タのすべてが、必ずしも他のサイトのデータ格納部にも
冗長に格納されている必要はないが、分散データベース
である以上、少なくとも一部のデータは冗長に格納して
おく必要がある。スループットの向上、信頼性の向上、
可用性の向上などの分散データベースの利点は、同一の
データを複数のコンピュータ（すなわちデータベースサ
ーバ）に冗長に格納することによってはじめて得られる
ものである。

【００２３】また、前記通信制御部１５は、複数のクラ
イアントを接続している。そのうちの１つであるクライ
アント１６は、ユーザＵ１の要求に応じてアプリケーシ
ョンＡＬ１を起動する部分である。当該アプリケーショ
ンＡＬ１が、ＤＢＭＳ１０に対し、データ格納部１１が
格納しているデータに対するデータ操作要求（データの
検索や更新などの要求）を行う。

【００２４】当該通信制御部１５はまた、クライアント
だけでなく、他のサイト（当該ＤＢＭＳ１０がサイト４
のＤＢＭＳであるとすると、例えば、サイト１など）の
ＤＢＭＳとのあいだで、後述するアクティブプログラム
ＡＰ１を送受し、巡回させる機能も備えている。簡単の
ためにリングを構成するサイトの数を４つとし、４→１
→２→３→４→…の転送を繰り返すことによって当該ア
クティブプログラムＡＰ１を巡回させるものとすると、
サイト４のＤＢＭＳ１０は、サイト３のＤＢＭＳからア
クティブプログラムＡＰ１を受信し、サイト１のＤＢＭ
Ｓに対してアクティブプログラムＡＰ１を送信すること
となる。

【００２５】次に、トランザクション制御部１４はクラ
イアント１６からのデータ操作要求にしたがいトランザ
クションを実行する部分である。ここで、トランザクシ
ョンとは、クライアント１６からのデータ操作要求に応
じて実行される１または複数の操作演算の系列である。
操作演算には、書込み演算や読出し演算などが含まれ
る。

【００２６】クライアントは前記断片がどのように生成
されたか、あるいは、各データが各サイトのデータ格納
部（１１）内に冗長に格納されているか否かとは独立に
前記論理データベースを操作し、データ操作を実行でき
る必要があるため、前記論理データベースに対して行わ
れるクライアントからのデータ操作要求は、自動的に、
各断片（各サイトのデータ格納部１１）に対するトラン
ザクションに変換される。

【００２７】分散データベースでは、複数のトランザク
ションが並列実行（交互実行）されるため、並列実行の
正当性を担保する必要がある。トランザクションの正当
な並列実行とは、並列実行せずに直列実行を行った場
合、すなわち、第１のトランザクションの全演算を実行
し終えたあとで、第２のトランザクションの演算の実行
を開始し、当該第２のトランザクションの全演算を実行
し終えたあとで、第３のトランザクションの演算の実行
を開始し、…というように、同時には単独のトランザク
ションだけを実行した場合の最終的なデータの状態と、
当該並列実行を行ったあとの最終的なデータの状態とが
完全に同じになる並列実行である。このような並列実行
の正当性のことを、直列可能性という。

【００２８】トランザクションを構成する読出し演算を
実行してもデータの内容に変化は生じないため読出し演
算相互間では競合関係（排他的な関係）は発生しない
が、書込み演算相互間、あるいは読出し演算と書込み演
算の間では、競合関係が発生し得る。直列可能性を確保
するためには、このような競合関係にある演算の実行順
序を一定に維持する必要がある。

【００２９】次に、アクティブプログラム実行制御部１
３は、通信制御部１５から受け取った前記アクティブプ
ログラムＡＰ１をアクティブプログラム実行環境部１２
に渡し、当該アクティブプログラム実行環境部１２で自
動的に起動させるなどの実行制御を行なう部分である。

【００３０】一般にアクティブプログラムとは、ノード
からノードヘ伝搬しながら、あるタスクを果たすソフト
ウェアプログラムを指す。伝搬するプログラムのサイズ
を小さくし、共通で使われるモジュールの保守性をよく
するために各サイトにプレインズトールするプログラム
モジュールが用意されるのが普通である。プログラムモ
ジュールがプレインズトールされている場合、アクティ
ブプログラムはサイトにプレインズトールされたプログ
ラムモジュールを参照して実行される。プレインズトー
ルするプログラムはプログラムモジュール用のサーバか
らダウンロードするなどしてインストールされる。当該
プログラムモジュールはアクティブプログラム実行環境
部１２の構成要素となる。

【００３１】アクティブプログラムＡＰ１は、図４に示
す宛先リストと、図５に示す更新内容キューを備え、さ
らに、前記プログラムモジュールと連携して当該更新内
容キュー等に対応した処理を実行するためのコード（例
えば、中間コード状態のコードでもよい）を備えてい
る。

【００３２】更新内容キューは、広義の更新（すなわ
ち、データの変更、挿入、削除）の内容を示したキュー
である。また更新内容キューに対応した処理とは、更新
内容キューに応じて実行されるデータ格納部１１に対す
る読出し演算、書込み演算、削除演算などである。な
お、削除演算は、削除するデータのサイズやＤＢＭＳ１
０の実装によっては、物理的に書込み演算（無効を意味
するビットパターンの書込み等）に等しい操作となる可
能性も高い。

【００３３】更新内容キューの実現には様々な方法が考
えられるが、一般的には、リスト構造を利用して論理的
に実現するのが普通である。

【００３４】図４において、サイト番号１〜４は、各サ
イト（すなわち、各データベースサーバ）を識別するた
めの番号であり、アドレスは各サイトのアドレスであ
る。図示の例では、一例として、ＩＰアドレスの１０進
表現をドット表記したものを示している。当該アドレス
（例えば、１７２．１８．２０９．１７１）は、アクテ
ィブプログラムＡＰ１をサイト１〜４間で巡回するため
に、自サイトから送信すべきサイトのアドレスを認識す
るのに利用することができる。

【００３５】また、図５において、データ項目Ａ、Ｂ、
Ｄは、演算の対象となるデータであって、サイト１〜４
のうち少なくとも２つのサイトで冗長に持っている可能
性のあるデータを指定する部分である。ここでは、デー
タ格納部１１が格納しているデータを変化させる書込み
演算と削除演算によって実行される更新の対象になるデ
ータ項目だけを示している。

【００３６】図５に示す更新内容キューのなかの更新内
容は、更新後の各データの内容を示した部分である。

【００３７】また、更新内容の右側にある４×４の更新
状態マトリックスＬＧは、各サイト１〜４において各デ
ータ項目の更新が終了したか否か、すなわち更新状態を
示す部分で、各サイトにおけるログ情報をまとめたもの
に相当する。更新状態マトリックスＬＧのなかで、更新
状態１は更新終了を示し、更新状態０は未更新を示す。

【００３８】したがって、上述した巡回の順序（４→１
→２→３→４→…）と当該更新状態マトリックスＬＧの
内容を対比すると、データ項目Ａ、更新内容１、更新状
態１１１０のタプルＴＵ１は、サイト１のトランザクシ
ョンの構成要素である書込み演算に起因して生成された
タプルであり、サイト１の次にアクティブプログラムＡ
Ｐ１を受け取るサイト２、その次に受け取るサイト３で
はすでに対応する更新が終了して更新状態が１となって
いるものの、アクティブプログラムＡＰ１を受け取った
ばかりのサイト４ではまだ、その更新が終了していない
ために更新状態が０である。

【００３９】他のタプルＴＵ２〜ＴＵ４についても同様
で、タプルＴＵ２はサイト２のトランザクションの構成
要素である書込み演算に起因して生成されたタプルであ
り、タプルＴＵ３はサイト３のトランザクションの構成
要素である書込み演算に起因して生成されたタプルであ
り、タプルＴＵ４はサイト４のトランザクションの構成
要素である削除演算（書込み演算）に起因して生成され
たタプルであることがわかる。

【００４０】そして、すべてのサイト１〜４における更
新が終了したデータに対応するタプルは、当該更新内容
キューから削除される。例えば、図示の状態で、タプル
ＴＵ１のなかの更新状態は、１１１０となっているが、
サイト４によって当該更新が終了して、更新状態が１１
１１となると、当該データＡに関する更新内容１の更新
につき、サイト１〜４間で、データの一貫性が確保され
たことになるので、当該タプルＴＵ１は、更新状態マト
リックスＬＧの対応する行（図示の状態で１１１０の
行）も含めて削除されることになる。

【００４１】なお、後述する図６のフローチャートの内
容を考慮すると、アクティブプログラムＡＰ１が存在し
ているサイト（ここでは、サイト４）における更新は、
それ以前のサイトにおける更新に対するデータの一貫性
を持たせる処理のあとで実行されるため、本実施形態の
更新内容キューは図５に示したような状態を取ることは
実際にはあり得ない（タプルＴＵ４におけるサイト４の
更新状態が１となる前に、タプルＴＵ１〜ＴＵ３のサイ
ト４における更新状態が１となるため）。

【００４２】また、読出し演算によって得られたデータ
の内容などは、１つのトランザクションが正常終了（コ
ミット）したときにまとめてクライアント１６上のアプ
リケーションＡＬ１に返すようにするとよい。

【００４３】以下、上記のような構成を有する本実施形
態の動作について、図６、図７のフローチャートを参照
しながら説明する。

【００４４】図６のフローチャートは、Ｐ１〜Ｐ５の各
ステップから構成されており、図７のフローチャート
は、Ｐ１１〜Ｐ１５の各ステップから構成されている。

【００４５】（Ａ−２）第１の実施形態の動作図６は、
前記アクティブプログラムＡＰ１が実行する処理を示し
たフローチャートであり、図７は、アクティブプログラ
ムＡＰ１受信時のＤＢＭＳ１０の処理を示すフローチャ
ートである。両者は、まったく同一の処理を、異なる観
点からみたものである。

【００４６】図６および図７において、アクティブプロ
グラムＡＰ１は、その内部で保持する図４の宛先リスト
に従い、次のサイトヘ自ら移動する（Ｐ１）。ただし、
この移動は、アクティブプログラム実行環境部１２や通
信制御部１５の支援があって実現されるものであること
は当然である（サイト３におけるＰ１５）。

【００４７】ここでは、この移動により、アクティブプ
ログラムＡＰ１が、サイト３のＤＢＭＳから、図１に示
すサイト４のＤＢＭＳ１０へ到達したものとする。ＤＢ
ＭＳ１０に到達したアクティブプログラムＡＰ１は、通
信制御部１５を介してアクティブプログラム実行環境部
１２に転送され、当該アクティブプログラム実行環境部
１２において自動的に起動される（Ｐ１１、Ｐ１２）。

【００４８】これにより、アクティブプログラムＡＰ１
は、内部で保持する更新内容キューを参照し、キューの
先頭から順に更新データを取り出し、ＤＢＭＳ１０に対
して該当するデータの更新を要求し、ＤＢＭＳ１０側の
トランザクション制御部１４ではこの要求に応える（Ｐ
１３）。図５の状態では、タプルＴＵ１がキューの先頭
にあたるため、ＴＵ１、ＴＵ２、ＴＵ３の順番でデータ
の更新が要求されることになる。

【００４９】必ずしも該当するデータをサイト４のＤＢ
ＭＳ１０が管理している（すなわち、データ格納部１１
に格納している）わけではないので、非存在エラーが発
生するかもしれないが、非存在エラーが発生した場合に
は、擬似正常終了とし、当該タプルに対応する更新が正
常に終了した場合と同様に、更新状態を１にする。非存
在エラーが発生したときに更新状態を１としなけれぱ、
アクティブプログラムＡＰ１が巡回を繰り返すことによ
って、更新内容キューのサイズが際限なく大きくなって
しまう等の不都合が生じるからである。

【００５０】例えば、図５に示すデータＡ、Ｄはサイト
４のＤＢＭＳ１０が管理しているものの、データＢにつ
いては管理していない場合には、ステップＰ２で、アク
ティブプログラム実行環境部１２から、まず最初にタプ
ルＴＵ１に対応して、データＡを１に上書きする更新要
求が行われて、その更新が実行されタプルＴＵ１の更新
状態が１１１１となったところで、当該タプルＴＵ１は
削除する。

【００５１】次に、ステップＰ３は、まだ更新すべきタ
プルＴＵ２が存在するためＹｅｓ側に分岐して、当該タ
プルＴＵ２に対応する更新要求が行われ（Ｐ２）、その
更新が実行されると、該当する更新状態を０から１に変
化させる。これによりタプルＴＵ２の更新状態はそれま
での０１１０から０１１１に変化するが、まだサイト１
による更新が終了していないために当該タプルＴＵ２は
削除されない。

【００５２】このあとのステップＰ３でも、タプルＴＵ
３に対応する更新を行うために再度Ｙｅｓ側に分岐し、
その更新を実行後、該当する更新状態は１になされる。

【００５３】当該タプルＴＵ３以降にはタプルは存在し
ない（タプルＴＵ４はこの時点ではまだ生成されていな
い）ため、今度は、ステップＰ３はＮｏ側に分岐して処
理はステップＰ４に進む。

【００５４】ステップＰ４ではそのサイト（ここでは、
サイト４）からのデータ更新要求があるか否かが検査さ
れ、無ければＮｏ側に分岐して次の巡回先サイトである
サイト１へ、アクティブプログラムＡＰ１が送信され、
有ればＹｅｓ側に分岐してステップＰ５の処理が行われ
る。

【００５５】図５では、当該サイト４で、データＤの削
除（書込み演算）を含むトランザクションが前記クライ
アント１６上のアプリケーションＡＬ１から供給されて
いるケースに対応する。

【００５６】もしも当該データＤがサイト４のＤＢＭＳ
１０が搭載するデータ格納部１１だけにしか存在せず、
他のサイト１〜３のデータ格納部には存在しないことが
予め判明している場合には、当該データＤの削除を行っ
たとしても、それに応じて当該タプルＴＵ４を更新内容
キューに入れる必要はない。

【００５７】ただしここでは、当該データＤがサイト４
以外のＤＢＭＳが搭載するデータ格納部にも存在するこ
とが判明しているか、判明していないとしても、少なく
とも存在する可能性が０でないものとして、ステップＰ
５で、当該タプルＴＵ４を更新内容キューの最後尾に格
納している。図５の状態では、すでにサイト４における
データＤの削除は終了しているため、タプルＴＵ４の更
新状態は、０００１である。

【００５８】サイト４の当該データＤの削除を含むトラ
ンザクションに、当該削除以外の操作演算が含まれてい
る場合には、その操作演算の数だけ、タプルＴＵ４の下
に後続のタプルが連続生成されることになる。そしてこ
の時点では、これらタプルの更新状態は、タプルＴＵ４
と同じ０００１である。

【００５９】ただしこのケースでは当該トランザクショ
ンに含まれている操作演算は１つだけで、当該タプルＴ
Ｕ４に対応する更新以外には、更新内容キューに入れる
べき更新に対応するクライアント（１６など）からの更
新要求はないため、処理は前記ステップＰ１に進む。

【００６０】ステップＰ１によってサイト４からアクテ
ィブプログラムＡＰ１を受け取るサイト１や、それ以降
に受け取るサイト２、サイト３などでも、図６、図７の
フローチャートにしたがって以上と同様な処理が行われ
得る。

【００６１】アクティブプログラムＡＰ１を巡回するサ
イトの順番が一定なので、以上の処理によって、上述し
た直列可能性が確保できることは明白である。

【００６２】一方、各ＤＢＭＳは自サイトのクライアン
トからのトランザクション処理を行なう。トランザクシ
ョンは２相ロックを使って実行される。２相ロックで
は、前記競合関係にある演算の処理に先立って全ての必
要なデータのロックを行ない、処理の最後に全てのロッ
クしたデータをアンロックする。

【００６３】トランザクションはアクティブプログラム
ＡＰ１を受信していないときにロックが必要となると、
当該トランザクション処理はブロックしておき、アクテ
ィブプログラムＡＰ１を受信したときに図７の処理を行
なう。

【００６４】ブロックしていたトランザクション処理
は、図７のステップＰ１４で、最後まで実行される。必
要なロックはアクティブプログラムＡＰ１の受信時点で
全て得られるからである。当該トランザクション処理が
データの更新を伴うときは、自サイトのデータ更新を行
なってから、アクティブプログラムＡＰ１に対し、自サ
イトからのデータ更新要求を送る。これにより、アクテ
ィブプログラムＡＰ１の内部の更新内容キューには、当
該データ更新要求に対応した１または複数の新たなタプ
ルが生成されることとなる。

【００６５】図５の更新内容キューでは、各タプルＴＵ
１〜ＴＵ４のそれぞれを１つのトランザクションに対応
するものとみることができるが、その場合、各トランザ
クションは１つの操作演算しか含まれていない簡単なも
のである。１トランザクション中に複数の操作演算が含
まれたもう少し複雑な例を想定すると、例えば、次のよ
うなトランザクションＴＲ１〜ＴＲ４があり得る。な
お、あるサイトがクライアントから受け取ったデータ操
作要求に対応するトランザクションの処理は、これらト
ランザクションＴＲ１〜ＴＲ４の各サイトにおける処理
と並行に実行される。

【００６６】ここでは、データＡ、Ｂ、Ｃは全てのサイ
ト１〜４が冗長に保持するものとしている。

【００６７】 サイト１：データＡのロック。データＡの更新。データＡのアンロック。 …ＴＲ１ サイト２：データＡ、Ｂのロック。データＡ，Ｂの更新。データＡ、Ｂの アンロック …ＴＲ２ サイト３：データＣの読み取り。データＡのロック。データＡの更新。デ ータＡのアンロック …ＴＲ３ サイト４：データＢ、Ｃのロック。データＢ，Ｃの更新。データＢ、Ｃの アンロック。 …ＴＲ４ サイト１がクライアントから受け取るトランザクション
ＴＲ１では、データＡの更新操作ＷＡ１が行われ、サイ
ト２がクライアントから受け取るトランザクションＴＲ
２では、データＡの更新操作ＷＡ２とデータＢの更新操
作ＷＢ１が行われ、サイト３がクライアントから受け取
るトランザクションＴＲ３では、データＣの読み取り操
作ＲＣ１と、データＡの更新操作ＷＡ３が行われ、サイ
ト４がクライアントから受け取るトランザクションＴＲ
４には、データＢの更新操作ＷＢ２とデータＣの更新操
作ＷＣ１が行われる。

【００６８】アクティブプログラムＡＰ１はサイト１→
２→３→４→１…の順に巡回するとする（以下の時刻ｔ
１〜ｔ７は等間隔な時間の区切りを表すものではなく、
アクティブプログラムＡＰ１が移動した時点を表す）。
また、以下に記述した処理は、主として、前記ステップ
Ｐ２、Ｐ３、Ｐ１３、Ｐ１４における処理の内容を示
す。

【００６９】時刻ｔ１：アクティブプログラムＡＰ１は
サイト１へ移動する。サイト１はデータＡに対し更新操
作ＷＡ１を実行する。このとき、更新内容キューの最後
尾に、当該更新操作ＷＡ１に対応するタプルを追加す
る。

【００７０】サイト３ではデータＣの読み取りが他の演
算とのあいだに前記競合関係を持たなければ、ロックは
必要ないため、この時点でデータＣの読み取り操作ＲＣ
１を実行して、トランザクションＴＲ３の一部を実行す
ることが可能である。

【００７１】また、ここでは、データＡ、Ｂ、Ｃは全て
のサイト１〜４が冗長に保持するものとの前提を置いて
いるが、一般的な分散データベースにはこのような前提
を置くことはできず、データＣの有効な検索結果を得る
ためには他のサイトの検索も必要である。例えば、サイ
ト３のデータ格納部にはデータＣが存在せず、他のサイ
ト（例えば、サイト１）のデータ格納部に存在している
可能性もあるからである。

【００７２】トランザクションＴＲ１〜ＴＲ４中のデー
タＣの読み取り操作ＲＣ１以外の処理（操作）はすべ
て、排他的な関係にあり、ロックが必要であるため、ア
クティブプログラムＡＰ１が受信されるまでブロックさ
れる。

【００７３】時刻ｔ２：アクティブプログラムＡＰ１は
サイト２へ移動する。サイト２のトランザクション制御
部１４はアクティブプログラムＡＰ１からの要求に従
い、前記更新操作ＷＡ１に応じてデータＡを更新したの
ち、ブロックしていた処理を再開し、データＡの更新操
作ＷＡ２と、データＢの更新操作ＷＢ１とを実行する。
このとき、更新内容キューの最後尾に、当該更新操作Ｗ
Ａ２とＷＢ１の内容に対応するタプルが、この順番で追
加される。

【００７４】時刻ｔ３：当該更新内容キューを収容した
アクティブプログラムＡＰ１はサイト３へ移動する。

【００７５】サイト３はアクティブプログラムＡＰ１か
らの要求に従い、サイト１によるデータＡの更新操作Ｗ
Ａ１、サイト２によるデータＡの更新操作ＷＡ２，サイ
ト２によるデータＢの更新操作ＷＢ１を行った後、ブロ
ックしていた処理を再開して、データＡに対し更新操作
ＷＡ３を実行する。

【００７６】読み取り操作ＲＣ１ではデータＣの内容に
変化は生じないものの、データＣの実体がサイト３のデ
ータ格納部に存在しないことも有り得るため、必要に応
じて、当該サイト３では、更新操作ＷＡ３に対応したタ
プルだけでなく、当該読み取り操作ＲＣ１に対応するタ
プルを更新内容キューの最後尾に入れてもよい。その場
合、順番は、トランザクションＴＲ３に対応して、読み
取り操作ＲＣ１、更新操作ＷＡ３の順番になる。

【００７７】データＣの実体を格納しているデータ格納
部を持つサイトで、読み取り操作ＲＣ１に応じた有効な
データＣが得られた場合には、そのデータＣの内容は、
別途、サイト３まで送信されることとなる。

【００７８】時刻ｔ４：当該更新操作ＷＡ１の更新内容
キューを収容したアクティブプログラムＡＰ１はサイト
４へ移動する。サイト４はアクティブプログラムＡＰ１
からの要求に従い、サイト１によるデータＡの更新操作
ＷＡ１、サイト２によるデータＡ，Ｂの更新操作ＷＡ
２、ＷＢ１、サイト３によるデータＡの更新操作ＷＡ３
を行った後、ブロックしていた処理を再開して、データ
Ｂの更新操作ＷＢ２とデータＣの更新操作ＷＣ１を実行
する。そして、当該更新操作ＷＢ２とＷＣ１に対応する
タプルが、この順番で、更新内容キューの最後尾に追加
される。

【００７９】当該サイト４の処理によって、サイト１に
よるデータＡの更新操作ＷＡ１は全てのサイト１〜４で
反映され、更新操作ＷＡ１に関するデータＡの一頁性が
確保されたので、当該更新操作ＷＡ１に対応するタプル
（キューの先頭のタプル）は更新内容キューから除去す
る。

【００８０】時刻ｔ５：当該タプルの除去を受け、前記
更新操作ＷＢ２とＷＣ１に対応するタプルの追加を受け
た更新内容キューを収容したアクティブプログラムＡＰ
１は、再ぴサイト１へ移動する。

【００８１】サイト１はアクティブプログラムＡＰ１か
らの要求に従い、サイト２によるデータＡ，Ｂの更新操
作ＷＡ２、ＷＢ１、サイト３によるデータＡの更新操作
ＷＡ３、サイト４によるデータＢ，Ｃの更新操作ＷＢ
２、ＷＣ１を行う。このサイト２による処理で、サイト
２による更新操作ＷＡ２、ＷＢ１は全てのサイト１〜４
で反映され、更新操作ＷＡ２、ＷＢ１に関するデータＡ
とデータＢの一貫性が確保されたので、更新操作ＷＡ
２、ＷＢ１に対応するタプル（この時点で、キューの先
頭にあるタプル）を、更新内容キューから除去する。

【００８２】もしもこの時点で、当該サイト１のクライ
アントからトランザクションＴＲ１につづく新たなトラ
ンザクションの要求があれば、そのトランザクションに
対応する処理を実行し、新たなタプルを更新内容キュー
の最後尾に追加することとなるが、ここでは、新たなト
ランザクションの要求は無かったものとする。

【００８３】時刻ｔ６：当該２タプルの除去を受けた更
新内容キューを収容したアクティブプログラムＡＰ１
は、サイト２に対する２度目（２巡目）の移動を実行す
る。

【００８４】サイト２はアクティブプログラムＡＰ１か
らの要求に従い、サイト３によるデータＡの更新操作Ｗ
Ａ３、サイト４によるデータＢ，Ｃの更新操作ＷＢ２、
ＷＣ１を行う。これによりサイト３によるデータＡの更
新操作ＷＡ３は全てのサイト１〜４で反映され、更新操
作ＷＡ３に関するデータＡの一貫性が確保されたので、
更新操作ＷＡ３に対応するタプルを更新内容キューから
除去する。

【００８５】もしもこの時点で、当該サイト２のクライ
アントからトランザクションＴＲ２につづく新たなトラ
ンザクションの要求があれば、そのトランザクションに
対応する処理を実行し、新たなタプルを更新内容キュー
の最後尾に追加することとなるが、ここでも、新たなト
ランザクションの要求は無かったものとする。

【００８６】時刻ｔ７：アクティブプログラムＡＰ１は
サイト３へ移動する。

【００８７】サイト３はアクティブプログラムＡＰ１か
らの要求に従い、サイト４によるデータＢ，Ｃの更新操
作ＷＢ２、ＷＣ１を行う。これによりサイト４によるデ
ータＢ，Ｃの更新操作ＷＢ２、ＷＣ１は全てのサイト１
〜４で反映され、更新操作ＷＢ２、ＷＣ１に関するデー
タＢ，Ｃの一貫性が確保されたので、更新操作ＷＢ２、
ＷＣ１に対応するタプルを更新内容キューから除去す
る。

【００８８】もしもこの時点で、当該サイト３のクライ
アントからトランザクションＴＲ３につづく新たなトラ
ンザクションの要求があれば、そのトランザクションに
対応する処理を実行し、新たなタプルを更新内容キュー
の最後尾に追加することとなるが、ここでも、新たなト
ランザクションの要求は無かったものとする。

【００８９】この場合、当該時刻ｔ７までの処理で、ア
クティブプログラムＡＰ１の更新内容キューは空になる
が、この後も、いつでも新たなトランザクションの要求
に対応できるように、アクティブプログラムＡＰ１はサ
イト１〜４を巡回し続ける。

【００９０】以上の実行手順により、更新に関するトラ
ンザクション実行の直列化順序は、サイト１→サイト２
→サイト３→サイト４のようになり、冗長に格納してい
る全データにつきデータベース（データ格納部１１）の
一貫性が維持される。

【００９１】なお、以上の説明では、サイト間では１→
２→３→４…の順番でアクティブプログラムＡＰ１を巡
回させたが、サイトの順番などは必要に応じて動的に変
更することが可能である。例えば、サイト２に障害が発
生した場合にはサイト１からサイト３へ送信し、以降
は、復旧するまでサイト２を除外してアクティブプログ
ラムＡＰ１を巡回させることも可能である。

【００９２】また、最初にアクティブプログラムＡＰ１
の巡回を始めるサイトは、例えば、全サイトを管理する
管理センタを設け、当該管理センタからの指示で決定す
るようにしてもよい。

【００９３】なお、本実施形態では、同じデータをでき
るだけ多くのサイトで冗長に格納するようにすれば、い
くつかのサイトに障害が発生した場合でも、そのデータ
に対する操作を続行することができる可能性が高まる。

【００９４】（Ａ−３）第１の実施形態の効果 以上のように本実施形態によれば、１つのサイトに対す
る更新要求と更新自体を並行して行なうことと、複数の
更新をまとめて行なうこと、更新自体に遠隔通信を必要
としないこと等により、通信量および更新に伴う遅延量
が削減できる。更新はアクティブプログラム内で直列化
するので、一貫性も保たれる。

【００９５】また本実施形態では、上述したプライマリ
コピー方式のように各データに対する特別なサイトを設
けず、一部のサイトに障害が発生した場合でも、分散デ
ータベース全体としては障害発生前とほぼ同等な性能を
維持することが可能で、頑健性の点でも優れている。

【００９６】さらに、本実施形態によれば、更新時にも
更新を始める１つのサイトに負荷が集中することがない
ので、負荷が軽減できる。

【００９７】（Ｂ）第２の実施形態 以下では、本実施形態が第１の実施形態と相違する点に
ついてのみ説明する。第１の実施形態はトランザクショ
ンが終了するまでアクティブプログラムＡＰ１を占有す
るので並列実行の操作単位を決めるロックの粒度が粗
く、一貫性は保存されるが、同時実行性は低い。

【００９８】本実施形態は、ロックの粒度をより細かく
して、同時実行性を高くすることによりスループットを
高めることを特徴とする。

【００９９】（Ｂ−１）第２の実施形態の構成および動
作 本実施形態の分散データベース管理システムの主要部の
構成例は図１と同じである。

【０１００】ただし本実施形態で使用するアクティブプ
ログラムＡＰ１は、図３に示した宛先リスト、図５に示
した更新内容キューに加えて、図８に示すロックリスト
を保持する点が相違する。

【０１０１】図８において、ロックリストは、ロックを
行ったサイト番号と現在ロックしているデータ項目から
成るリストである。アクティブプログラムＡＰ１を保持
する巡回先のサイトは、ロックリストにないデータ項目
に対してのみロックをかけることができるが、アクティ
ブプログラムＡＰ１を保持しないサイトはどのデータ項
目に対してもロックをかけることは許されない。

【０１０２】図示の状態では、サイト１がデータＡをロ
ックし、サイト２がデータＢとＣをロックしている。た
だしロックは、本来サイト単位ではなくトランザクショ
ン単位に実行するものであるので、ここで行われるデー
タＡのロックは、サイト１がクライアントから受け取っ
たあるデータ操作要求に対応するトランザクションのた
めのロックであり、データＢとＣのロックは、サイト２
がクライアントから受け取ったあるデータ操作要求に対
応するトランザクションのためのロックである。もちろ
ん、サイト２が行ったデータＢのロックと、データＣの
ロックが、別個のトランザクションのためのロックであ
ってもかまわない。

【０１０３】次に、図９および図１０を用いて、本実施
形態の動作について説明する。

【０１０４】図９は、アクティブプログラムＡＰ１の動
作を示すフローチャートであり、図１０は、アクティブ
プログラムＡＰ１受信時のＤＢＭＳの動作を示すフロー
チャートである。図９のフローチャートはＰ２１〜Ｐ２
８の各ステップから構成されており、図１０のフローチ
ャートはＰ３１〜Ｐ３８の各ステップから構成されてい
る。

【０１０５】図９および図１０において、アクティブプ
ログラムＡＰ１内部で保持する宛先リストに従い、アク
ティブプログラムＡＰ１が次のサイトヘ白ら移動する
（Ｐ２１）。ただし、この移動は、アクティブプログラ
ム実行環境部１２や通信制御部１５の支援があって実現
されるものであることは当然である（Ｐ３８）。

【０１０６】次に、アクティブプログラムＡＰ１内部で
保持する更新内容キューを参照し、キューの先頭から順
に更新データを取り出し、移動先のサイトのＤＢＭＳ１
０に対して該データの更新を要求する（Ｐ２２）。この
要求は、アクティブプログラム実行環境部１２が、受け
取ったアクティブプログラムＡＰ１を自動的に起動する
ことによって実行される。

【０１０７】非存在エラーが発生した場合に擬似正常終
了として更新状態を１とし、すべてのサイトの更新状態
が１となったタプルは、更新内容キューから除去する点
や、これらの操作が更新内容キューに未処理のタプルが
なくなるまで繰り返される点などは、第１の実施形態と
同様である（Ｐ２３、Ｐ３３）。

【０１０８】このあとステップＰ２４、Ｐ３４におい
て、アクティブプログラムＡＰ１は、巡回先のサイトの
ＤＢＭＳ１０に対して、データロック要求があるか問い
合わせ、あれば処理はステップＰ２５，Ｐ３５側へ分岐
し、なければ処理はステップＰ２７、Ｐ３７側へ分岐す
る。このときデータロックの必要性を判定し、必要な場
合にデータロック要求を出力するのは、当該ＤＢＭＳ１
０のトランザクション制御部１４である。

【０１０９】ステップＰ２５、Ｐ３５では、アクティブ
プログラムＡＰ１は、ＤＢＭＳ１０からロックするデー
タの情報を受け取り、前記ロックリストに基づいてロッ
ク可能性を判定する。要求のあったデータ項目が既にロ
ックリストにあれば、ロック不可能と判定して、エラー
を返し、処理はステップＰ２７、Ｐ３７側へ分岐する
が、ロック可能である場合にはステップＰ２６、Ｐ３６
側へ分岐する。

【０１１０】ステップＰ２６では、アクティブプログラ
ムＡＰ１が、要求のあったデータ項目をロックリストに
サイト番号と共に追加し、ステップＰ３６では、トラン
ザクション制御部１４がそれまで対象データのロックが
得られないためにブロックしていたトランザクションの
演算操作を再開する。

【０１１１】ステップＰ２６、Ｐ３６につづいて、ステ
ップＰ２５やＰ３５がＮｏ側に分岐した場合と同じ前記
ステップＰ３７に進む。

【０１１２】ステップＰ２７、Ｐ３７では、ＤＢＭＳ１
０から既にそのサイトでのみ更新が完了したデータのデ
ータ項目と更新内容を受け取り、更新内容キューの末尾
につなげる（Ｐ２８）が、そのサイトでのみ更新が完了
したデータがなければ、ステップＰ３７では何も行われ
ない。

【０１１３】いずれにしても、当該ステップＰ２７また
はＰ２８、あるいはＰ３７の次には、前記宛先リストに
したがって、アクティブプログラムＡＰ１が次の巡回先
のサイトに移動することになる。そしてその巡回先のサ
イトでも、以上と同様な処理が繰り返される。

【０１１４】なお、各ＤＢＭＳが自サイトのクライアン
トからのトランザクション処理を行なう際に、ロックを
用いる点や、あるサイトがクライアントから受け取った
データ操作要求に対応するトランザクションの処理が、
前記トランザクションＴＲ１〜ＴＲ４などの各サイトに
おける処理と並行に実行される点なども、第１の実施形
態と同じである。

【０１１５】次に、アクティブプログラムＡＰ１はサイ
ト１→２→３→４→１…の順に巡回し、データＡ，Ｂ，
Ｃは全てのサイト１〜４が冗長に保持するものとする第
１の実施形態と同じ前提で、第１の実施形態と同じ次の
トランザクションＴＲ１〜ＴＲ４を処理するものとす
る。

【０１１６】 サイト１：データＡのロック。データＡの更新。データＡのアンロック。

【０１１７】 …ＴＲ１ サイト２：データＡ、Ｂのロック。データＡ，Ｂの更新。データＡ、Ｂの アンロック。 …ＴＲ２ サイト３：データＣの読み取り。データＡのロック。データＡの更新。デ ータＡのアンロック。…ＴＲ３ サイト４：データＢ、Ｃのロック。データＢ，Ｃの更新。データＢ、Ｃの アンロック。 …ＴＲ４ サイト１がクライアントから受け取るトランザクション
ＴＲ１では、データＡの更新操作ＷＡ１が行われ、サイ
ト２がクライアントから受け取るトランザクションＴＲ
２では、データＡの更新操作ＷＡ２とデータＢの更新操
作ＷＢ１が行われ、サイト３がクライアントから受け取
るトランザクションＴＲ３では、データＣの読み取り操
作ＲＣ１と、データＡの更新操作ＷＡ３が行われ、サイ
ト４がクライアントから受け取るトランザクションＴＲ
４には、データＢの更新操作ＷＢ２とデータＣの更新操
作ＷＣ１が行われる。

【０１１８】この条件の下、最初の前記時刻ｔ１でアク
ティブプログラムＡＰ１はサイト１へ移動する。このと
き図７のロックリストは空であるものとすると、サイト
１が前記更新操作ＷＡ１を行うためにデータＡのロック
をアクティブプログラムＡＰ１に要求すると、成功する
ので、当該ロックに対応するトランザクションＴＲ１を
開始する。

【０１１９】このとき同時に、サイト３でもロックの不
要なデータＣの読み取り操作ＲＣ１を行い得る点や、他
のサイトではロックが必要なため処理をブロックする点
なども、第１の実施形態と同様である。

【０１２０】また、時刻ｔ２でアクティブプログラムＡ
Ｐ１がサイト２へ移動したとき、サイト２は前記更新操
作ＷＡ２とＷＢ１を行うためにデータＡ，Ｂのロックを
アクティブプログラムＡＰ１に要求するが、データＡは
既にロックされているので、失敗通知を受信する。した
がってトランザクションＴＲ２はブロックしたままであ
る。

【０１２１】このとき、データＢだけをロックすること
は可能であるが、ロックは行わない。データＡより先に
データＢのロック要求に成功していても、データＢのロ
ックはアボートする。ここで、データＢのロックだけを
行うとサイト内、あるいはサイト間でデッドロックが発
生する可能性が高くなる等の不都合があるため、１つの
トランザクションの実行に必要な一連のロックは一括し
て獲得し、一括獲得できない場合には、一部だけの獲得
は行わないようにするのが効率的である。

【０１２２】時刻ｔ３でアクティブプログラムＡＰ１が
サイト３へ移動すると、サイト３は前記トランザクショ
ンＴＲ３の更新操作ＷＡ３を行うためにデータＡのロッ
クをアクティブプログラムＡＰ１に要求するが、ロック
リスト上で、データＡは既にロックされているため、失
敗通知を受信する。したがって当該トランザクションＴ
Ｒ３はブロックされたままである。

【０１２３】次に、時刻ｔ４でアクティブプログラムＡ
Ｐ１がサイト４へ移動すると、サイト４はトランザクシ
ョンＴＲ４の更新操作ＷＢ２、ＷＣ１を行うためにデー
タＢ，ＣのロックをアクティブプログラムＡＰ１に要求
し、成功するので、当該トランザクションＴＲ４を開始
する。

【０１２４】このあと時刻ｔ５でアクティブプログラム
ＡＰ１は再びサイト１へ移動する。ここからは、アクテ
ィブプログラムＡＰ１の２巡回目の処理である。

【０１２５】サイト１はトランザクションＴＲ１を完了
しており、ローカルでのデータＡの更新を終えている。

【０１２６】そこで、サイト１はデータＡの更新内容を
アクティブプログラムＡＰ１の更新内容キューに追加す
る。同時にデータＡのロックをロックリストから除去す
る。なお、この時点で、前記トランザクションＴＲ１以
外の新たなトランザクションがサイト１のクライアント
からのデータ操作要求に対応して生成され得るが、ここ
では、簡単のために、新たなトランザクションの生成は
行われないものとする。この点は、以降の巡回先のサイ
トでも同様である。

【０１２７】時刻ｔ６でアクティブプログラムＡＰ１は
サイト２へ移動する。

【０１２８】サイト２はアクティブプログラムＡＰ１か
らの要求に従い、前記トランザクションＴＲ１の更新操
作ＷＡ１に応じてデータＡを更新した後、データＡ，Ｂ
のロックをアクティブプログラムＡＰ１に要求するが、
データＢは既にロックされているので、失敗通知を受信
する。データＡのロックだけは成功するが、データＢの
ロックに失敗したために、データＡのロックはアボート
する。

【０１２９】時刻ｔ７でアクティブプログラムＡＰ１は
サイト３へ移動する。

【０１３０】サイト３はアクティブプログラムＡＰ１か
らの要求に従い、前記トランザクションＴＲＡの更新操
作ＷＡ１に応じてデータＡを更新する。さらにサイト３
は、トランザクションＴＲ３を実行するためデータＡの
ロックをアクティブプログラムＡＰ１に要求する。前回
とはロックリストの内容が変化しているため、今回は、
当該ロックに成功し、トランザクションＴＲ３を開始す
る。

【０１３１】次に、時刻ｔ８でアクティブプログラムＡ
Ｐ１はサイト４へ移動する。

【０１３２】サイト４はアクティブプログラムＡＰ１か
らの要求に従い、前記トランザクションＴＲ１の更新操
作ＷＡ１に応じてデータＡを更新する。この更新によ
り、サイト１によるデータＡの更新操作ＷＡ１は全ての
サイトのデータ格納部に反映されたので、当該更新操作
ＷＡ１に対応するタプルは、更新内容キューから除去す
る。

【０１３３】また、この時点ではすでに、サイト４はト
ランザクションＴＲ４を完了しており、ローカルでのデ
ータＢ，Ｃの更新操作ＷＢ２、ＷＣ１を終えている。

【０１３４】そこで、サイト４は更新操作ＷＢ２、ＷＣ
１の内容をアクティブプログラムＡＰ１の更新内容キュ
ーに追加する。同時にデータＢ，Ｃのロックをロックリ
ストから除去する。

【０１３５】時刻ｔ９でアクティブプログラムＡＰ１が
サイト１に対する３回目の移動を行うと、サイト１はア
クティブプログラムＡＰ１からの要求に従い、トランザ
クションＴＲ４の更新操作ＷＢ２、ＷＣ１に応じて、デ
ータＢ，Ｃを更新する。ここからは、アクティブプログ
ラムＡＰ１の３巡回目の処理である。

【０１３６】次に、時刻ｔ１０でアクティブプログラム
ＡＰ１がサイト２へ移動すると、サイト２はアクティブ
プログラムＡＰ１からの要求に従い、トランザクション
ＴＲ４の更新操作ＷＢ２、ＷＣ１に応じてデータＢ，Ｃ
を更新する。

【０１３７】さらにサイト２はトランザクションＴＲ２
を実行するため、データＡ，Ｂのロックをアクティブプ
ログラムＡＰ１に要求するが、データＡは既にロックさ
れているので、失敗通知を受信する。データＢのロック
は成功してもアボートする。

【０１３８】時刻ｔ１１でアクティブプログラムＡＰ１
はサイト３へ移動する。

【０１３９】サイト３はアクティブプログラムＡＰ１か
らの要求に従い、トランザクションＴＲ４の更新操作Ｗ
Ｂ２、ＷＣ１に対応してデータＢ，Ｃを更新する。これ
により、サイト４による更新操作ＷＢ２、ＷＣ１の内容
は、全てのサイトで反映されたので、更新南容キューか
ら除去する。

【０１４０】この時点ではすでに、サイト３は自身がク
ライアントから受け取ったデータ操作要求に対応するト
ランザクションＴＲ３を完了しており、更新操作ＷＡ３
に対応したローカルでのデータＡの更新を終えている。

【０１４１】そこで、サイト３は当該更新操作ＷＡ３に
対応したデータＡの更新内容をアクティブプログラムＡ
Ｐ１の更新内容キューに追加する。同時にデータＡのロ
ックをロックリストから除去する。

【０１４２】処理ｔ１２でアクティブプログラムＡＰ１
がサイト４へ移動すると、サイト４はアクティブプログ
ラムＡＰ１からの要求に従い、トランザクションＴＲ３
の更新操作ＷＡ３に応じてデータＡを更新する。

【０１４３】処理ｔ１３でアクティブプログラムＡＰ１
がサイト１へ移動すと、４巡回目の処理がはじまる。

【０１４４】サイト１はアクティブプログラムＡＰ１か
らの要求に従い、トランザクションＴＲ３の更新操作Ｗ
Ａ３に応じてデータＡを更新する。

【０１４５】なお、更新操作の内容がデータの単なる上
書きである場合には、同じデータＡに対する更新操作
は、ＷＡ１、ＷＡ２、ＷＡ３のそれぞれを実行しなくて
も、データＡの最後の値（ここではＷＡ３の結果）を最
初の値に上書きするだけでデータの一貫性を確保するこ
とも可能であるが、一般的にはそうではないし、できる
だけ早期に一貫性を確保することも必要なので、各更新
操作ごとに、一貫性を確保する更新操作を行っている。
一例としては、データＡの値が整数値で、ＷＡ１、ＷＡ
２、ＷＡ３がそれぞれインクリメントを示す場合など
は、最後の更新操作だけを行うと、最終的なデータの値
が異なるものとなってしまう。

【０１４６】次に、時刻ｔ１４でアクティブプログラム
ＡＰ１がサイト２へ移動すると、サイト２はアクティブ
プログラムＡＰ１からの要求に従い、トランザクション
ＴＲ３の更新操作ＷＡ３に応じてデータＡを更新する。
これにより、当該更新操作ＷＡ３の内容は全てのサイト
に反映されたので、当該更新操作ＷＡ３に対応するタプ
ルが更新内容キューから除去される。このとき更新内容
キューは空になる。

【０１４７】当該サイト２では、前記トランザクション
ＴＲ２が未処理のまま残っているため、このとき、サイ
ト２はトランザクションＴＲ２の更新操作ＷＡ２とＷＢ
１を行うためにデータＡ，Ｂのロックをアクティブプロ
グラムＡＰ１に要求する。この要求は、両方とも成功
し、トランザクションＴＲ２を開始する。

【０１４８】時刻ｔ１５でアクティブプログラムＡＰ１
はサイト３へ移動するが、サイト３では何もしない。

【０１４９】同様に、時刻ｔ１６でサイト４へ移動した
ときも、時刻ｔ１７でサイト１へ移動したときも、アク
ティブプログラムＡＰ１は何も新たな処理を実行しな
い。

【０１５０】時刻ｔ１８でアクティブプログラムＡＰ１
がサイト２へ移動すると、この時点までにサイト２では
前記トランザクションＴＲ２を完了しており、更新操作
ＷＡ２、ＷＢ１に応じて、ローカルのデータＡ，Ｂの更
新を終えている。

【０１５１】そこでサイト２は、更新操作ＷＡ２、ＷＢ
１に応じたデータＡ，Ｂの更新内容をアクティブプログ
ラムＡＰ１の更新内容キューに追加する。同時にデータ
Ａ，Ｂのロックをロックリストから除去する。

【０１５２】時刻ｔ１９でアクティブプログラムＡＰ１
がサイト３へ移動すると、サイト３はアクティブプログ
ラムＡＰ１からの要求に従い、トランザクションＴＲ２
の更新操作ＷＡ２、ＷＢ１に応じてデータＡ，Ｂを更新
して、データＡ，Ｂの一貫性を確保する。

【０１５３】以降の各時刻でも同様に、時刻ｔ２０では
サイト４で、時刻ｔ２１ではサイト１で、アクティブプ
ログラムＡＰ１は、トランザクションＴＲ２の更新操作
ＷＡ２，ＷＢ１に応じてデータＡ，Ｂを更新して、デー
タの一貫性を確保する。

【０１５４】時刻ｔ２１におけるサイト１の更新で、ト
ランザクションＴＲ２の更新操作ＷＡ２、ＷＢ１の内容
は全てのサイトで反映されたので、更新内容キューから
除去する。これでアクティブプログラムＡＰ１の更新内
容キューは空になるが、この後もアクティブプログラム
ＡＰ１はサイト１〜４を巡回し続け、新たなトランザク
ションの発生に対応する。

【０１５５】以上の実行手順により、更新に関するトラ
ンザクション実行の直列化順序は、サイト１→サイト４
→サイト３→サイト２のようになり、データベースの一
貫性が維持される。

【０１５６】本実施形態の場合、第１の実施形態に比べ
て全てのトランザクションＴＲ１〜ＴＲ４が終了し、更
新操作に応じたデータの一貫性が確保されるまでのアク
ティブプログラムＡＰ１の巡回数は多くなるが、各サイ
トにおけるトランザクション処理とアクティブプログラ
ムＡＰ１の巡回、データの更新は並行して処理されるの
で、同時実行性は高まり、スループットも高くなる。

【０１５７】（Ｂ−２）第２の実施形態の効果 以上のように本実施形態によれば、第１の実施形態の効
果とほぼ同等な効果を得ることができる。

【０１５８】加えて、本実施形態では、ロックの粒度が
細かくなり同時実行性が向上するため、スループットを
高めることが可能である。

【０１５９】（Ｃ）他の実施形態 上記第１、第２の実施形態では、リレーショナルモデル
を例に説明したが、本発明は、リレーショナルモデル以
外にも適用可能である。例えば、階層型、ネットワーク
型、オブジェクト型などのデータベース管理システムを
用いてもよい。

【０１６０】また、データベースの代わりに、ファイル
のリプリケーション（Replication）が分散しており、
更新要求をそれぞれのサイトで並行して受け付けるとき
にも、本発明が適用できる。

【０１６１】さらに、前記更新内容キューで、同じデー
タ項目に対して複数回の更新が存在するとき、最適化し
て１回で更新することも可能である。

【０１６２】なお、上記第２の実施形態で、ロックする
単位はデータ単位としたが、データ群単位、表単位、表
群単位でロックすることも容易に実現できる。

【０１６３】また、上記第１および第２の実施形態で
は、２相ロック方式を用いたが、読出し演算まで図５に
示す更新内容キューに格納し、１つのトランザクション
に含まれる全操作演算は連続して更新内容キューに入れ
るようにした場合には、各ＤＢＭＳ内における競合する
データに対するデータ操作のスケジュールは完全に固定
され当該更新内容キューによって厳密に規定されるた
め、いわゆる時刻印順化（timestamp algorithm）方式
に類似した方式となる。この場合、データ操作要求をク
ライアントから受け取ったサイトも含め、すべてのサイ
トは、当該スケジュールにしたがってトランザクション
を進めることになるから、ロックは不要であり、デッド
ロックは発生しない。

【０１６４】

【発明の効果】以上に説明したように、本発明によれ
ば、高い頑健性と、少ない通信量および遅延量を実現す
ることが可能である。

【図面の簡単な説明】

【図１】第１および第２の実施形態にかかる同時実行制
御システムで使用するＤＢＭＳの主要部の構成例を示す
概略図である。

【図２】サイトによって構成されるリングの全体構成例
を示す概略図である。

【図３】サイトによって構成されるリングの動作説明図
である。

【図４】第１および第２の実施形態で使用する宛先リス
トの構成例を示す概略図である。

【図５】第１および第２の実施形態で使用する更新内容
キューの構成例を示す概略図である。

【図６】第１の実施形態のアクティブプログラムの動作
を示すフローチャートである。

【図７】第１の実施形態のＤＢＭＳの動作を示すフロー
チャートである。

【図８】第２の実施形態で使用するロックリストの構成
例を示す概略図である。

【図９】第２の実施形態のアクティブプログラムの動作
を示すフローチャートである。

【図１０】第２の実施形態のＤＢＭＳの動作を示すフロ
ーチャートである。

【符号の説明】

１〜４…サイト、１０…ＤＢＭＳ，１１…データ格納
部、１２…アクティブプログラム実行環境部、１３…ア
クティブプログラム実行制御部、１４…トランザクショ
ン制御部、１５…通信制御部、１６…クライアント。

Claims (3)

【特許請求の範囲】
1. 【請求項１】 同じデータを複数のデータベースサーバ
   に冗長に配置して構成される分散データベースの同時実
   行制御システムにおいて、 各データベースサーバは、 競合演算操作の対象となるデータを指定するデータ指定
   情報と、 当該競合演算操作の内容を記述した操作情報と、 各データベースサーバにおいて該当するデータ指定情報
   に関する該当する操作情報の競合演算操作が既に完了し
   ているか否かを指定する操作完了情報とを有するトーク
   ン構造体を、データベースサーバ間で巡回させ、 受け取った当該トークン構造体の有するデータ指定情
   報、操作情報、および操作完了情報に応じたデータベー
   ス管理処理を、自動的に起動するアクティブ起動手段を
   備えることを特徴とする分散データベースの同時実行制
   御システム。
2. 【請求項２】 請求項１の分散データベースの同時実行
   制御システムにおいて、 前記トークン構造体は、 前記巡回を支援するため、各データベースサーバを指定
   する少なくとも宛先アドレス情報を有することを特徴と
   する分散データベースの同時実行制御システム。
3. 【請求項３】 請求項１または２の分散データベースの
   同時実行制御システムにおいて、 前記トークン構造体は、 各データベースサーバが既にロックしているデータを示
   すロック済みデータ情報を有することを特徴とする分散
   データベースの同時実行制御システム。