METIS：無線環境を考慮したトランザクション処理システム

全文

(1)データベースシステム 128−３（２００２．７．１７）. METIS: 無線環境を考慮したトランザクション処理システム見山今井. 成志y 倫太yy. 川島英之y 安西祐一郎yy. 無線環境下では、予期せぬ通信切断によってトランザクション処理の中止が頻繁に起こり得る。そのつどユーザは再接続時に初めから処理をやり直す必要がある。そこで本論文では、ユーザが再接続したときに処理の再開を可能にさせるトランザクション処理システムを提案する。並行性を高めるために、にはユーザが再接続されるまでロックを解放する機構が導入されている。これはトランザクションを仮に終了させるを実装し、動作の検証を行った仮コミット、および補償トランザクションにより実現される。結果、突発的な通信切断が起こる環境下で、処理の再開が可能となることを確認した。また、の再開機構によるオーバヘッドは、約に抑えられることを確認した。. Transaction Intermediate System). METIS. 7%. METIS(Mobile Environment METIS METIS. METIS: Awireless transaction processing system considering environment Seiji Miyama,y Hideyuki Kawashima,y Michita Imaiyy and Yuichiro Anzaiyy. Under wireless environment, a transaction often aborted due to the unexpected communication disconnection. At each abortion, a user needs to reconnect to the system and to start the transaction over again. To address this problem we investigate the transaction system that resumes the aborted process when the user reconnects to the system. In this paper, we propose the Mobile Envionment Transaction Intermediate System (METIS). To raise concurrency, METIS releases a lock while waiting for the user to reconnect. This is realized with tentative commit and compensative transaction. The tentative commit terminates the transaction process temporarily. We implemented METIS and con

(2) rmed that it successfully resumes the transaction after the sudden disconnection with less than 7 % of overhead. 1. はじめに. クセスにおけるトランザクション処理の性能を悪化させ. 近年、インターネットを利用したチケット予約や株取. る、ユーザに望まれないトランザクションの中止である。. てしまう。具体的には、予期せぬ通信切断によって発生す. り引きなど、オンラインでのデータベースアクセスが当. 予期せぬ通信切断によってトランザクションが中止さ. たり前のようになってきている。オンラインで行うこと. れた場合、ユーザは処理を最初からやり直さなければな. で処理時間や人件費の削減が可能となることから、今後. らない。これに対してユーザが再接続したときに処理の. さらにこの需要が高まると考えられる。. 再開を可能にさせる手法が提案されている 4) が、データ. また、携帯電話、PDA といった無線携帯端末の小型化、. ベースシステム内部では、再接続待ちをしているトラン. 高性能化が進む一方で、高速な無線・移動体通信ネット. ザクションにデータのロックを占有され続けてしまい、他. ワーク環境も整備されつつある。携帯電話の国内での加. のユーザのアクセスが待たされてしまうという問題が生. 入者数は 6500 万人を越え 1) 、無線 LAN のアクセスポイントも、駅や街頭といった様々な場所で続々と設置され. じる。そこで本研究では、これらの問題を考慮したトラン. METIS(Mobile Environment Transaction Intermediate System) を提案. ザクション処理システム. てきている。そのような無線環境の整備に伴って、オンラインでのデータベースアクセスも、無線環境下で行われるように. する。METIS は、予期せぬ通信切断が起きたときに、処. なってきている。携帯電話と無線. 理の状態を仮想的に維持して、ユーザの再接続時に処理. LAN のサービスを意. 識せずに切り替えながら利用できるようになる技術も開. の再開を可能にさせると共に、再接続されるまでロック. 発されていることより、今後ますます無線環境下からの. を解放する機能を持つ。. 本論文の構成は以下の通りである。第 2 章で、無線環. データベースアクセスは増加すると考えられる。しかし無線環境下での特有の問題が、データベースア. 境下における問題点を明らかにし、関連研究を挙げる。. y 慶應義塾大学大学院理工学研究科. び動作について述べ、第 4 章では提案手法の有用性につ. Gradudate School of Science and Technology, Keio University. yy 慶應義塾大学理工学部. Faculty of Science and Technology, Keio University. 第 3 章で本論文で提案するシステム METIS の設計およ. いて実験により評価を行う。そして第 5 章で結論を述べ. る。最後に第 6 章で今後の課題について論じる。. 1 −17−.

(3) 2. 無線環境下におけるトランザクション処理の問題点と関連研究. 2.1. でも、他ユーザからの読み出しは可能にすることで、システムのスループットの向上を図っている手法 3) が提案されている。しかし、あるユーザがキャッシングしてい. 無線環境下での問題点. るデータには、たとえそのユーザが書き込みを行ってい. 無線環境下は通信回線品質が悪いため、予期せぬ通信切. 断が起こる可能性がある。さらに端末が携帯電話や PDA などの場合、マシンパワーが貧弱な上に、フルキーボー. なくても、他ユーザは書き込みを行うことは許されない。そのため楽観的手法に比べてシステムのスループットは低くなる。. ドやマウスが無いという入力機構の貧弱さも問題点とし. 無線環境下では、端末は長時間ネットワークから通信. て挙げられる。また、これらの端末はバッテリで駆動す. 切断される可能性がある。楽観的手法の場合、更新した. るため、バッテリの消費電力をできるだけ抑えることも. データをサーバに戻すまでの時間が長い程、他ユーザと. 必要になる。以下に無線環境下の問題点をリストアップ. の更新の衝突回数が多くなると考えられ、トランザクショ. する。. ンがアボートされる可能性が高くなる。また、悲観的手. (1) (2) (3). 予期せぬ通信切断が起こること. 法の場合、端末が長時間ネットワークから通信切断され. マシンパワーが貧弱であること. た状態にあると、その間はロックが解放されないので、シ. 入出力機構が貧弱であること. ステムのスループットを低下させてしまう可能性がある。. これらの問題点の中で、本研究では 1 番目の「予期せ. 2.3.1. ぬ通信切断が起こること」に着目する。. 再接続時に処理の再開を可能にさせる手法. 無線環境下での予期せぬ通信切断への対処方法には、. 上記の 3 つの問題点は独立していない。処理の途中で. キャッシングの他に、予期せぬ通信切断時に、サーバ側. 予期せぬ通信切断が起こると、再接続した際に処理をも. で処理の状態を維持し、再接続してきたユーザに処理を. う一度最初からやり直さなければならない。従って通信. 再開させる手法がある。この手法の場合、処理状態を維持するためにエージェ. 切断前までに行っていた処理が全くの無駄になってしまう。これは電力を余分に消費することにもつながるため、. ントが用いられることが多い 4) 。エージェントを通信先. バッテリで駆動する無線端末には望ましくない。さらに. のマシンで立ち上げておき、通信路が切断された場合、. 入力機構も貧弱であるので、ユーザがもう一度面倒な入. エージェントに処理の状態を維持させる。. 力をやり直すのは、かなりの労力が必要となる。そこで. この手法を用いた場合、ロック占有の問題が生じる。こ. 予期せぬ通信切断への対処をすることは、その他の 2 つ. れは再接続待ちをしているトランザクションによってロッ. の問題点への間接的な対処となる。. クが占有され続けることにより、他のユーザのアクセス. 2.2. 関連研究. が待たされてしまう問題である。ユーザからの要求を逐次エージェントが記憶し、通信. 無線環境下の予期せぬ通信切断への対処方法として、キャッシングをクライアント側で行いそれを用いて処理. 切断時には一旦処理をアボートさせる手法 5) が提案され. を行う手法と、ユーザの再接続時に通信切断が起きる直. ている。ユーザからの再接続があった場合、エージェン. 前からの処理の再開を可能にさせる手法の二種類が提案. トは記憶しておいた処理を再実行し、通信切断直前の状. されている。次にこれら二つの手法について説明する。. 態まで復元する。この手法は通信切断時に処理をアボー. 2.3. キャッシングによる手法. トしているので、ロックを占有することはない。しかし. 予期せぬ通信切断に対する手法として、通信切断時に. アボートしてから再接続するまでの間に、通信切断が起. ユーザ側でデータを利用できるようにするために、ユーザ. こらなければ確保できていたはずのデータを、他のユー. の無線端末内にデータをキャッシングする手法がある。こ. ザによって横取りされてしまう可能性がある。また、こ. の手法は楽観的手法と悲観的手法の 2 通りに分類できる。楽観的手法の場合、無線端末内にキャッシングしたデー. のシステムはデータベースサーバにエージェントを立ち上げるので、データベースが分散して存在する場合には、. タに対して更新を行うときに、他ユーザとの更新による. エージェント間の協調が必要になる。しかしこれについ. 衝突を考慮しない。更新を行ったデータをサーバへ反映. ては無考慮であるので、分散トランザクション処理へ適. させる段階で、他ユーザとの更新の衝突が発見された場. 用できるかは不明である。. 合、衝突している更新の中でコミットされるのは 1 つの. みに限定される。このためコミットされないトランザクションのそれまでの操作はアボートされてしまう。これ. 2.4. 較. キャッシングを行う手法と、再接続時に処理の再開を. 可能にさせる手法の 2 種類について比較検討を行う。. に対して管理者が優先するユーザを設定し、そのユーザの更新以外はアボートする手法 2) が提案されている。. 比. キャッシングを行う手法では、楽観的な手法によるキャッシングしたデータをサーバに反映させる段階で更新が衝. 悲観的手法の場合、キャッシングを行う段階でそのデー. 突する問題や、悲観的な手法によるロック占有の問題が、. タのロックを獲得し、トランザクションをユーザの無線. ユーザ数の増大とともに頻発してしまう。また 2.1 節で. 端末内で終了させる。この手法を用いると、ロックが占. 述べたようにマシンパワーが貧弱な無線端末を使う場合、. 有されている間は、他ユーザがそのデータを読み出すこ. キャッシングによってデータを端末に保存することは端. とも書き込むこともできない。この制約を緩め、無線端. 末の記憶容量を圧迫してしまうので避けるべきである。. 末内で変更された値を、トランザクションが終了する前. 2 −18−. 一方、再接続時に処理の再開を可能にさせる手法は、.

(4) 再接続待ちの間、ロック占有の問題が発生する。しかし. METIS-M. キャッシングを行う必要はなく、マシンパワーが貧弱な. METIS-D METIS-C. 無線端末にも適用可能である。. user. M-CM. 以上より、無線環境下からトランザクション処理を行. DBS. う際の予期せぬ通信切断への対処方法として、再接続時. Request. M-TM. に処理の再開を可能にさせる手法は、キャッシングを行. DBS. う手法に比べて優れていると言える。. 3. METIS : 無線環境を考慮したトランザク. DBS. M-TM. ション処理システム. wireless (or wired). 分散環境において、TP モニタというトランザクション. 図. 処理システムが大きな役割を果たす。そこで本研究では、. wired. 1. METIS の構成. TP モニタの基本機能を持ち、ユーザの再接続時に処理. から与えられたトランザクション ID を保存する。そ. の再開を可能にさせ、ロック占有の問題を解決するトラ. してそのユーザが再び接続してきたら、新規接続か. ンザクション処理システム. 再接続の選択をさせる。. METIS(Mobile Environment Transaction Intermediate System) を設計. . METIS-D(Database). METIS は、予期せぬ通信切断時に、仮想的に処理の状. METIS-D はデータベースシステムが存在するマシンそれぞれに存在する。METIS-D は METIS-M から. 態を維持して、ユーザの再接続時に処理の再開を可能に. 受け取った要求をローカルのデータベースシステムへ. および実装する。. 送信して、トランザクションを実行させる。METISD を設けることで、将来的に異種のデータベースシステムを METIS が管理できるようになる。. させると共に、再接続までロックを解放する機能を持つ。本章ではまず METIS を設計するにあたり想定したア. プリケーションについて述べる。その後 METIS の構成. . 要素および動作について述べる。. 3.1. 想定アプリケーション. METIS を設計するにあたり、ホテルと飛行機の予約を同時に行うシステムを想定アプリケーションとした。分散トランザクション処理を行うために、ホテルの空室データと飛行機の空き座席のデータは別のマシンのデータベースに分散して格納されているものとする。. METIS-M(Middle). METIS-M は METIS-C と METIS-D の中間に位置し、METIS-C から送られてきた要求を、対応する METIS-D へ送信する。分散環境における要求の振り分けや、要求を BEGIN や COMMIT(または ABORT) でくくる囲い込みを行う。また METIS-M は、予期せぬ通信切断に対して、再接続を可能にさせる。METIS-M はと. M-CM MTM から構成される。 { M-CM(M-Connection Manager). ユーザはインタラクティブにホテルの予約と飛行機の予約を行い、満足な結果が得られた場合はコミットする。そうでない場合は、処理の途中でアボートし、それまで. の処理を破棄する。例えば 1 泊 2 日の出張を考えると次. M-CM は METIS-C からの接続要求を受けて起 M-TM を生. のようになる。. (1) (2) (3). 動する。新規接続の場合は新しく. 成する。再接続の場合は再接続待ちをしている. 行きの飛行機の検索 → 予約. M-TM を探す。. 出張先のホテルの検索 → 予約. { M-TM(M-Transaction Manager). 帰りの飛行機の検索 → 予約. 約ができなかったとき、出張は中止になるかもしれない。. M-TM は、METIS-C から新規接続要求があったとき M-CM によって生成される。ユーザの. その場合ホテルの予約が不可能と分かった時点でユーザ. 要求からアクセスするデータの位置情報を得て、. はトランザクションをアボートする。もし帰りの飛行機. 該当するデータを持つデータベースシステムに. もし行きの飛行機は予約可能であったが、ホテルの予. アクセスする METIS-D へ送信する。予期せぬ. まで全て予約可能だった場合のみ、ユーザはトランザク. ションをコミットする。予約は一回に 1 つしか行えない. 通信切断によって METIS-C との通信が一時途. と仮定した。このように想定アプリケーションとして、イ. 3.3. ンタラクティブなトランザクションを考え、コミットもしくはアボートはユーザが決定できるものとした。. 3.2. 本システムにおいて通信切断の起こらない通常実行時. のトランザクション処理の動作を図 2 に示す。図中の番号. 構成要素. METIS の構成要素を図 1 に示す。 METIS は以下の 3 つの要素から構成される。 . METIS-C(Client). 絶えたら、再接続待ち状態に入る。通常処理. は次に説明する処理の流れのステップ数と対応している。通常実行時の処理の流れは以下のようになる。. METIS-C はユーザからの要求を受け取り、それらを METIS-M が求める型へ変換して送信する。予期せぬ通信切断時には、ユーザ名および METIS-M. (1). 3 −19−. 認証処理. (a). ユーザが入力したユーザ名、パスワードを元. に、METIS-C は. METIS-M の M-CM へ. 接続要求を送信する.

(5) METIS-M. METIS-C. M-CM 1(b).Authenticate. 1(a). 1(c).Create. client 3(a),4(a) Request. 3.4. METIS-D. 2(b),3(c),4(c). METIS-M. M-TM 3(b).Record. 4(d). 3 のように動. 作する。. DBS 2(a),3(b),4(b). 予期せぬ通信切断時の動作. 予期せぬ通信切断時には、METIS は図. METIS-D. DBS 2(a),3(b),4(b). M-CM DBS. 2(b),3(c),4(c) 3(a),4(a). 2(a),3(b),4(b) M-TM. METIS-C DBS 2(b),3(c),4(c). 2. 2.Wait Reconnect. 0.Disconnect. 4(d). 図. M-TM. 1(a). Record user name & transaction ID. 1(b),3(a) 1(b),3(a) DBS. No Reconnect. 1(b),3(a). 通常の動作 3(b).Time-out 1(b),3(a). ( b ) M-CM は接続要求を受けると認証処理を (c) (2). 図. 行う. 認証に成功すると M-CM は M-TM を生成. し、それに一意なトランザクション ID を割. (1). り当てる. ( a ) METIS-C はユーザの意志に反する通信切名およびトランザクション ID を保存する. ( b ) METIS-M の M-TM は、トランザクション終了前の通信切断を検出すると、全て. ( b ) METIS-D は BEGIN を受け取ると、それる (以後. COMMT もしくは ABORT を受け取るまでトランザクションは終了しない) ( c ) METIS-C へトランザクションの開始を通. (2) (3). 知し、ユーザの要求の受け付けを開始する. ( a ) METIS-C はユーザの要求を METIS-M の対応する M-TM へ送信する ( b ) 要求を M-TM は受け取った要求を保存すると共に、順次対応する METIS-D へ送信する. ミット (後述) を行う再接続待ち. M-TM はシステム管理者によって設定された時間、 METIS-D からの再接続要求を待つタイムアウト. (a). 再接続要求を一定時間待った後、M-TM は 3.3 節で述べた通常処理・3b で保存した要求をもとに補償トランザクション (後述) を生成して実行する. ( b ) M-TM はタイムアウトし、コミットもしくはアボート時と同様に役目を終え破棄されるシステム管理者は再接続待ちが可能な. M-TM の数を. 制限する。この理由は、再接続待ち中の M-TM が多くな. れをローカルのマシンのデータベースシス. りすぎて、新しい接続に対して M-TM が作成できなくな. を介して METIS-C へ返される). 待ち動作に入る段階で、既に再接続待ちの許容数を超え. テムへ送信し実行させる (結果は METIS-M. (4). の METIS-D へ COMMIT を送信して仮コ. 要求実行. ( c ) METIS-D はユーザの要求を受け取ると、そ. 通信切断時の動作. 断をポーリングにより検出すると、ユーザ. ( a ) M-TM は、生成されると全ての METIS-D へ BEGIN を送信し、グローバルトランザ. し、ローカルトランザクションを開始させ. 3. 通信切断検出時の動作. トランザクションの開始. をローカルのデータベースシステムへ送信. DBS 1(b),3(a). クションの開始を宣言する. (3). 1(b),3(a). コミットもしくはアボート. ( a ) METIS-C は、ユーザが要求の実行結果を元に決定した COMMIT もしくは ABORT を、METIS-M の M-TM へ送信する ( b ) M-TM は METIS-C から COMMIT もしくは ABORT を受け取ると、それを全ての METIS-D へ送信する ( c ) METIS-D は COMMIT もしくは ABORT. ることを回避するためである。もしステップ 2 の再接続. ていたら、最も古い. M-TM の再接続待ち状態を解除し. てから再接続待ち状態へ移る。解除されたものは、補償トランザクションを実行した後、破棄される。仮コミット仮コミットとは、ロックを解放するために、仮にコミッ. トをすることである。ステップ 1b で仮コミットを行うことでロックを解放し、再接続待ちをしている間、ロックを占有し続けるのを回避する。これによりユーザのトラ. を受け取ると、それをローカルのデータベー. ンザクションは、文献 5) で用いられていた、アボートす. スシステムへ送信し、トランザクションを. る手法とは違い、自分のデータを再接続するまでの間に. 終了させる. 横取りされることなく、ロックを解放することができる。. はアボートされたことを伝える. 償トランザクションを実行する。. ( d ) METIS-M は METIS-C へコミットもしく M-TM はコミットもしくはアボートするとその役目を終え破棄される。. もし後で仮コミットよる変更を取り消したい場合は、補補償トランザクション. ステップ 3 の補償トランザクションとは、ステップ 1b で行った仮コミットの効果を元に戻すトランザクション. 4 −20−.

(6) のことである。手順は次の通りである。. (1) (2). ち状態にあった場合、それに再接続要求を. 全ての METIS-D へ BEGIN を送信影響を与えた要求と逆の要求を送信. (例えば、ホテルの空室を一つ減らす操作をした場. (3). 増やす操作となる). トランザクションを生成して実行し、仮コミット. 全ての METIS-D へ COMMIT を送信. この補償トランザクションを用いることで、仮コミッ. (4). トの影響をなくし、データベースの状態を元に戻すことができる。. 3.5. 補償トランザクション. 再接続要求を受けた M-TM は、3.3 節で述べた通. 常処理・ステップ 3b で保存した要求を元に、補償. 合、補償トランザクションはホテルの空室を一つ. (3). 伝える. によって変更されたデータを元に戻す通信切断前のトランザクションの再実行. ( a ) M-TM は全ての METIS-D へ BEGIN を送信する. 予期せぬ通信切断によって、トランザクションを一時. ( b ) M-TM は保存しておいた通信切断前までのトランザクション (通常処理・ステップ 3b). 中止させられたユーザが、再接続をするときの動作を図. を再実行し、データの状態を通信切断直前. 再接続時の動作. 4 に示す。. (5) METIS-M METIS-D M-CM 1(d).Authenticate. METIS-C. 1(c).Reconnect. client. 3,4,5. 2(b) 1(a). 1(b). Reconnect or New connect ?. 2(a).Seek(ID = x) 3,4,5. 5 M-TM (ID = x) 2(c).Reconnect. DBS 3,4,5 DBS 3,4,5. 3,4,5 DBS. 4. M-TM は再接続処理が終了したことを METIS-C へ送信し、トランザクションを再開する (最終的にステップ 4a に対応する COMMIT もしくは ABORT が送信されてトランザクションは終了する) ステップ 3 で補償トランザクションを実行した後、ステップ 4b で、通信切断前までに行われていたトランザク. ションを再実行することで、通信切断前の状態を復元する。これによりユーザは通信切断直前からの処理を再開. 3,4,5. 図. 再接続時の動作. 可能となる。. 3.6. 接続の選択-認証. ( a ) METIS-C は接続要求をしてきたユーザ名. (c) (d). るまでの間、その M-TM によって、いくつかのレコードのロックが、保持され続けてしまう可能性がある。その. によってトランザクションを中止させられ. 間、他のクライアントはこのレコードへアクセスができ. 断する再接続要求が可能なユーザである場合、. なくなるという、ロック獲得の衝突が発生する。. ロック衝突の問題に対して MVCC(Multi Version Con-. currency Control)6) という方式がある。これは、個々の. METIS-C は再接続要求か新規接続かをユー. トランザクションはデータベースからの読み出しの間、. ザに選択させる. データの現在の状態には関知せず、現在から遡ったある. ユーザが再接続を選択した場合、METIS-C は再接続要求を M-CM へ送信する. 再接続要求を受け取った M-CM は認証処理. を行う. ステップ 1c でユーザが新規接続を要求してきた場合、もし前の接続が再接続待ちをしていたら、そ. の M-TM は破棄される。1 ユーザに対して再接続待ちをしている M-TM が複数存在しないようにこ. (2). を行わなかった場合、再接続もしくはタイムアウトされ. を見ることにより、前回予期せぬ通信切断た (つまり再接続要求が可能な) ユーザか判. (b). ロックの解放について. 予期せぬ通信切断時の動作・ステップ 1b で仮コミット. 再接続の処理の流れは以下のようになる。. (1). の状態へ戻す再開. こで調整を行う。. 対応する M-TM の探索. ( a ) M-CM はユーザの認証に成功すると、再接続要求に含まれるトランザクション ID を元に、再接続待ちをしている M-TM の中か. 時点におけるデータベースの情報を参照する手法である。この手法の場合、読み出したいデータに対して現在書き込みが行われていても、読み出しは現在の状態ではなく、現在から遡ったある時点を読み出すのでロック獲得の衝突は起こらない。しかしこれも書き込みの場合はロック獲得の衝突が発生してしまう。トランザクションの存続期間が短い場合はこの手法は有効であるが、再接続待ちという不確定な時間ロックを保持し続けてしまうのは望ましくない。また文献 5) のようにロックを解放するためにアボートしてしまうと、再接続するまでの間に、通信切断が起こらない環境ならば確保できていたデータを、他のユーザに横取りされてしまう可能性がある。. そこで METIS では、仮コミットと補償トランザクショ. ら対応するものを探す. ンを取り入れることで、ロックの占有問題を解決してい. た場合、以前の接続は既にタイムアウトさ. 作・ステップ 3) してから、トランザクションを再実行 (再. ( b ) M-CM は対応する M-TM が発見できなかっれていることを METIS-C ヘ伝える ( c ) M-CM は対応する M-TM がまだ再接続待. る。しかし補償トランザクションを実行 (再接続時の動. 接続時の動作・4b) するまでに、他のクライアントから. の書き込み要求が割り込むと、結局他ユーザの横取りを. 5 −21−.

(7) 許してしまうことになる。そのため METIS では、補償トランザクション実行後から通信切断以前のトランザクション再実行までの間は、他のクライアントは書き込み要求を送信できないようにする必要がある。. オーバヘッドを算出した。. (A). 本論文で提案する METIS を介して要求を送信す. る方法. ( B ) METIS-M から再開機構を取り除いたものを介して要求を送信する方法. 4. 評価および考察. {. これは TP モニタの基本機能のみを備えたトランザクション処理システムに相当する. 本章では、システムに与える負荷を変化させて、トラン. ザクションが終了するまでの時間を、METIS と METIS. { (A) との主な違いは、M-CM の機能および、 M-TM が逐次行う要求の保存が必要なくなる. から再開機構を取り除いたもの (基本機能を備えた TP モ. ニタと見なせる) それぞれについて測定し、基本性能を. ことである. 評価する。次に通信切断確率を変化させ、同様に 2 つの. 実験は、同時にシステムにアクセスするユーザ数 N を. システムでトランザクションが終わるまでの時間を測定. 増加させて、トランザクションが終了するまでの時間を. し、再開機構について考察する。. 4.1. 想定アプリケーション. 第 3 章で述べたホテルと飛行機の予約をインタラクティ. それぞれ測定した。N は 0、10、20、30、60 の 5 種類を用いた。同時にシステムにアクセスしているユーザはつの METIS-D へ均等に検索をしつづける。. ブに行うシステムを想定アプリケーションに用い、測定を行うにあたり以下のように環境を設定した。. 予約する目的地には a,. b, c, d, e の 5 つの場所が存. 結果のグラフを図. 3. 5 に示す。図中の (A)、(B) は前述. のものと対応する。. 在する. ホテルも飛行機もデータは 1 年分存在するマシン 1 のデータベースには、ホテルの空室データ. 2400. が 1 年分格納されている. 2200. Time(ms). マシン 2 のデータベースには、飛行機の空き座席データが 1 月から 6 月の半年分格納されている. マシン 3 のデータベースには、飛行機の空き座席デー. 2000. 1800. タが 7 月から 12 月の半年分格納されている. 以上の想定環境で、次に示す 12 ステップのトランザク. 1600 (A) (B) 0. 10. 20. ションを行ったときにかかる時間を測定した。. (1) (2) (3) (4) (5) (6) (7) (8) (9) ( 10 ) ( 11 ) ( 12 ). 4.2. 図. ログイン. 6 月 30 日の a → b の飛行機を検索 6 月 30 日の a → b の飛行機を予約 6 月 30 日の b のホテルを検索 6 月 30 日の b のホテルを予約 7 月 1 日の b → c の飛行機を検索 7 月 1 日の b → c の飛行機を予約 7 月 1 日の c のホテルを検索 7 月 1 日の c のホテルを予約 7 月 2 日の c → a の飛行機を検索 7 月 2 日の c → a の飛行機を予約. 40. 50. 60. 基本性能の測定. (A) と (B) の差が METIS の再開機構によるオーバヘッドになる。図. 5 より、METIS の再開機構によるオーバヘッドは %以下であった。. 認められるが、それは 7. 4.4. 通信切断が起こる環境下での評価. 本節では、METIS が予期せぬ通信切断が起こる環境下でどれほど有用であるかを検証するため、前節で説明した. (A)、(B) のシステムについて、次のような条件で. 実験した。. 4.1 節で述べた 12 ステップの要求において、各インタ. コミット再接続によるトランザクション処理の再開の確認. METIS の目的は、無線環境下での予期せぬ通信切断. を考慮して、ユーザの再接続時に処理の再開を可能にすることである。前述のトランザクションの各ステップで、通信切断を試みたところ、再接続後の処理の再開が可能である確認した。. 4.3. 5. 30 Client N. 基本性能の評価. METIS は、TP モニタの基本機能を備えたトランザク. ラクションの間に確率 p で通信切断を起こし、トランザ. クションが終了するまでの時間を測定した。p は 0、5、. 10、15、20(%) の 5 種類を用いた。結果のグラフを図 6 に示す。図中の (A)、(B) は前節のものと対応する。. 通信切断確率が 0 %の時は、再開機構によるオーバヘッ. ドのため (B) の方が処理にかかる時間は短い。しかし (B). は、通信切断確率が高くなるにつれて、トランザクションを終了するまでにかかる時間が急激に上昇しているの. ション処理システムに、再接続時の処理の再開を可能に. に対して、(A) ではさほど大きな上昇は見られない。(B). させる機構が取り入れられたものである。そこで次に示. では通信切断が起きる度にもう一度処理を最初からやり. す. (A)、(B) の条件で、前述のトランザクションが終了. するまでの時間を測定し、その時間から再開機構による. 直す必要がある。これより、通信切断確率が 20. %の時に. トランザクションを終了するまでの時間は、通信切断確. 6 −22−.

(8) 7、9、11 ステップ目でロック獲得の衝突が起こる。システム (II) では、ロックが獲得できなかった場合、通信切断が起こると最高で約 5 秒間待たされることになる。通信切断確率が高くなるほど待たされる機会が多くなり、12. 10000. 9000. 8000. Time(ms). 7000. 6000. ステップのトランザクションを終了するまでの時間が増. 5000. えると予想される。. 一方 METIS(システム (I)) では、通信切断が起こった. 4000. 3000. 場合は一旦ロックを解放するので待たされる必要がない。よって通信切断確率が高くなっても、12 ステップのトラ. 2000 (A) (B) 1000 0. 5. 10. 15. ンザクションを終了するまでの時間に変化は表れないと. 20. Disconnection rate p(%). 図. 率が 0. 4.5. 6. 予想される。. 通信切断が起こる環境での測定. 結果を図 7 に示す。切断確率 p は 0、5、10、15、20(%). %の時に比べて、約 4.6 倍必要となった。. の 5 種類を用いた。. ロックの解放についての評価. 再接続による処理の再開を可能にさせた場合、再接続. 6500. 待ちをしているトランザクションによって、ロック占有. 6000. の問題が発生してしまう。METIS では、仮コミットと補. 5500 5000. 償トランザクションを用いることでロック占有の問題を. 4500 Time(ms). 解決している。METIS で実装した機構の有効性を確認するために以下の実験を行った。. 4000 3500. ( I ) METIS(仮コミットによってロックを解放する) ( II ) 再接続待ちの間ずっとロックを維持し続けるシス. 3000 2500 2000 (I) (II). テム. 1500. 以上の (I)、(II) について前述の 12 ステップのトラン. 0. 図. ザクションが終了するまでの時間を測定した。その際ロック獲得の衝突を発生させるために次のように設定した。. . 12 ステップのトランザクションを行うユーザに通信切断は起こらない. . 12 ステップのトランザクションを行うユーザ以外に周囲に 5 ユーザ存在する 5 ユーザはそれぞれ次のような動作を繰り返す () の部分は通信切断が起こった時のみ実行される { ユーザ 1 ログイン → 6 月 30 日の a → b の飛行機を予約 → 確率 p で通信切断が起こる. {. (→ 5 秒待機 → 再接続) → アボートユーザ 2 ログイン → 6 月 30 日の b のホテルを予約 → 確率 p で通信切断が起こる. (→ 5 秒待機 → 再接続) → アボート { ユーザ 3 ログイン → 7 月 1 日の b → c の飛行機を予約 → 確率 p で通信切断が起こる. {. (→ 5 秒待機 → 再接続) → アボートユーザ 4 ログイン → 7 月 1 日の c のホテルを予約 → 確. 率 p で通信切断が起こる. (→ 5 秒待機 → 再接続) → アボート { ユーザ 5 ログイン → 7 月 2 日の c → a の飛行機を予約 → 確率 p で通信切断が起こる. (→ 5 秒待機 → 再接続) → アボート 12 ステップのトランザクションを行うユーザは、3、5、. 5. 7. 10 Disconnection rate p(%). 15. 20. ロック獲得の衝突による時間変化. 予想通りシステム (II) の場合は、通信切断確率が高く. なるにつれて、12 ステップのトランザクションを終了するまでにかかる時間も増加しいる。一方 METIS の場合. は切断確率が変化しても、12 ステップのトランザクションを終了するまでの時間に変化はほとんど見られない。このことから、システム (II) の再開機構はロックを維持し続けるため、大幅にトランザクション処理の効率が低下いるが、METIS の再開機構によるトランザクション処理の効率の低下は見られないと言える。. 5. 結. 論. 本論文では、無線環境下での予期せぬ通信切断を考慮して、ユーザが再接続したときにトランザクション処理を再開することのできるトランザクション処理システム. METIS を設計および実装した。この際、再接続待ちを. しているトランザクションがロックを占有してしまう問題が発生したが、METIS では仮コミットと補償トランザクションを用いることによってこれを解決した。. 実験によって METIS の動作を検証した結果、通信切断. 後でも再接続による処理の再開が可能となることが確認. できた。また処理の再開機構によるオーバヘッドは 7%以内に抑えられることも確認できた。. METIS を用いることで、無線環境下での予期せぬ通. 信切断から起こるトランザクション処理の中止を防ぐことができるため、処理の効率が向上するとともに、ユーザは処理の再実行をする必要がなく、ユーザの労力を軽減できることを示した。. 7 −23−.

(9) 6. 今後の課題本研究で設計および実装した METIS は、ユーザの再. クションに対しては仮コミットを行う。この問題は、預金した状態で仮コミットを行った場合に操作がしきい値を越える可能性があるので、預金に対してはアボートを. 接続時に処理の再開を可能にさせ、ロック占有の問題を解. 行うことで解決できる。. の M-TM がトランザクションの状態を維持しユーザの再. ば確保できていたはずのデータを横取りされる」ことを. 接続による処理の再開を可能にさせる。また、仮コミッ. 防止するためであった。これを踏まえると、お金を引き出. トおよび補償トランザクションを用いることで、ロック. す場合には仮コミットを用いてデータを反映させること. 決するトランザクション処理システムである。METIS-M. 占有の問題を解決した。しかし METIS には次のような課題が考えられる。. METIS-M の分散化. 本研究では、METIS-M はシステム内で一つのみ存在. する。しかし METIS-D の数が増加した場合、負荷を考慮して METIS-M も複数に分散すべきである。この場合 METIS-M 間で、再接続待ちをしている M-TM の受け. 仮コミットを導入した理由は、「通信切断が起きなけれ. が必要と考えられるが、預金する場合は横取りの心配が無いので必要ない。よって、預金に対してはアボートを用いることで、残高が負の値になるという問題を解決でき、引き出しに対しては仮コミットを用いることで、横取りの問題を解決できる。しかし、前述の例のように、負の値になることだけが必ずデータベースで問題になるとは限らない。例えば在. 渡しなどが必要になる可能性もあるため、さらなる検討. 庫管理のデータベースの場合は、一定以上の値になるこ. が必要になる。. とも問題になるかもしれない。この場合、仮コミットとア. 仮コミットと補償トランザクション. METIS はロック占有の問題に対して、仮コミットと補. ボートを使い分ける条件が、前述の預金の例とは変わってくる。このように、使い分けの条件はデータベースが. 償トランザクションを用いたが、これは不具合を発生さ. 用いられているアプリケーションによって異なり、本研. せる可能性がある。以下にその例を示す。. 究ではその条件を一般的に表現するまでには至っていな. ( 1 ) A の口座に 1000 円入っている ( 2 ) 無線環境下から A が 1000 円預金し、コミットする前に通信が切断された. ( a ) M-TM によって仮コミットされる ( b ) A の口座は 2000 円になる ( 3 ) B が、A の口座から 1500 円引き出すトランザクションを実行し、コミットする. ( 4 ) A の再接続要求は無く、M-TM はタイムアウトする. ( a ) M-TM は補償トランザクションを実施する ( b ) 「1000 円預金する」に対する補償トランザクションは「1000 円引き出す」である ( c ) B が口座から 1500 円引き出したため口座には 500 円しか残っていないこの場合、ステップ 4b で補償トランザクションを実行すると、A の口座の預金額が負の値になってしまう。この例で問題を発生させる原因は、ステップ 2 の仮コミットにある。処理が不完全な値を一旦コミットすることで問題が発生する。本研究で想定した、ホテルと飛行機の予約を同時に行うアプリケーションは、予約を一回に 1 つ. しか行えない設定にした。このため、必ず負の値になる. 前に空室もしくは空き座席が 0 になるので、データベー. スシステムで 0 に対する予約を制限しておけば、この問. い。よってこの問題は今後の課題としておく。. 参. 考. 文. 献. 1) \移動電気通信事業加入者の現況=速報=(平成 13 年 10 月末現在)", http://www.soumu .go.jp/joho tsusin/pressrelease/japanese /sogo tsusin/011112 1.html. 2) Robert Gruber and Frans Kaashoek and Barbara Liskov and Luiba Shrira: \Disconnected Operation in the Thor Object-Oriented Database System", Proceedings of the IEEE Workshop on Mobile Computing System and Applications,1994. 3) Sanjay Kumar Madria and Bharat Bhargava: \A Transaction Model for Mobile Computing", Database Engineering and Applications Symposium, pp.92-102, 1998. 4) 新谷虎松, 大囿忠親, 福田直樹: \モバイルエージェントの応用 -マルチエージェントシステムのためのモビリティの利用-", 人工知能学会誌, Vol.16, pp.488493, April, 2001. 5) 梅染充男, 古坂大地, 岩本健嗣, 西尾信彦, 徳田英幸: \無線環境に適したトランザクション・システムの構築", 情報処理学会第 61 回全国大会公演論文集 (1), 2000. 6) \Multi-Version Concurrency Contro", http://www.postgresql.org/idocs/index.php?mvcc.html.. 題は発生しない。しかし前述の例では、0 をまたいで正. の値から負の値になるので問題が発生する。つまり一回の操作によりしきい値をまたぐ可能性がある場合、問題が発生するのである。この問題への解決策として、予期せぬ通信切断が起こった場合に、仮コミットとアボートを使い分ける手法を検討中である。前述の例の場合、通信切断が起こった時に、お金を預金したトランザクションに対しては仮コミットを行わずにアボートを行い、お金を引き出したトランザ. 8 −24−.

(10)