分散トランザクション処理に関する研究
−不変時刻印方式−
データベースでは, 複数のユーザから投入される処理要求であるトランザクションの処理を行っていきますが, 各トランザクションを同時に処理することで, 応答時間の改善を行うことができます.
その一方で,トランザクション処理によって得られる参照結果や, データベースの内部状態が, トランザクションを逐次的に実行した場合と同一であるといった一貫性の保証が要求されます. この一貫性の保証を行うのが同時実行制御です.
分散型のデータベースでは, システムに投入されるトランザクションを全て把握するサイトが基本的には存在しないため, 単一データベースに比べ,同時実行制御は困難なものとなります.
従来から提案されている同時実行制御として,トランザクション毎に時刻印を付け, この時刻印を用いて行う時刻印方式があり,時刻印方式のなかにも, データの書き込み毎に, 書き込み以前のデータを消去してしまう単版時刻印方式と データの書き込みを行った後も書き込み以前のデータを保存しておく多版時刻印 方式があります.
単版時刻印方式は, 以前のデータの以前の版の値を読み出すような操作を実行することができません. このような読み出し操作を含むトランザクションは時刻印を新たに付け直して再実行されます. 一方多版時刻印方式では,このような読み出し操作も, 以前の版から読み出すことで実行できますが, 既に読み出しを行ったトランザクションの時刻印よりも小さな値をもつ書き込み操作は実行できません.
当研究室では,多版時刻印方式をベースに,各版に書き込み, 読み出し全ての操作履歴を記録することで, 時刻印の付け直しを行うことなく一貫性を保証する同時実行制御の研究を行ってきました. これが不変時刻印方式です.
この方式は以下のような特徴を持っています.
- 他の方式では実現が不可能であった,受け付け順にトランザクションの処理を行うことができ公平性が高い.
- 長トランザクションが,繰り返し時刻印の付け直しが行われ,処理が完了できないロックアウト状態を引き起こさない.
現在までに,不変時刻印方式のアルゴリズムの提案,その正当性の証明を行い.さらに,不変時刻印方式での応答時間に対する影響が大きい, アクティブなトランザクションの最小時刻印決定法に関して, 様々な方式の提案や評価を中心に研究を進めてきました.
また,このアクティブトランザクションの最小時刻印決定アルゴリズムは, 分散並列型イベントドリブンシミュレーションとして米国で活発に研究されている Time Warp Mechanism におけるGVT決定アルゴリズムとしても応用可能です.
今後は,これまでの研究成果を基に,高度ネットワーク社会における分散型のトランザクション処理システムの実用化を目指し,さらなる研究を進める予定です.
関係する主な研究発表
- 階層型マルチリングによるGVT決定アルゴリズム,
小林 真也,福田 宗弘,
情報処理学会論文誌, Vol.41, No.11, pp3161-3172(2000.11)
- Hierarchical Commitment Algorithm for Permanent Time Stamp Ordering,
Shin-ya KOBAYASHI,Kouji MATSUURA,
1998 International Conference on Parallel and Distributed Systems,
National Cheng-Kung University, Tainan, Taiwan, ROC(1998.12)
- 不変時刻印方式における階層型コミットメント制御の提案,
小林 真也,松浦 幸治,石森 宣行,福田 宗弘,
電子情報通信学会論文誌(D-I), Vol.J80-D-I, No.12, pp.1249-1258(1998.12) - 不変時刻印方式におけるマルチトークン型コミットメント制御,
小林 真也,石森 宣行,
電子情報通信学会論文誌(D-I), Vol.J80-D-I, No.11, pp.936-938(1997.11) - 不変時刻印方式における集中型コミットメント制御,
小林 真也,石森 宣行,
電子情報通信学会論文誌(D-I), Vol.J80-D-I, No.2, pp.173-176(1997.2) - 要求順サービス可能な時刻印方式について,
小林 真也,古川 誠,中西 暉,手塚 慶一,
電子情報通信学会論文誌(D-I), Vol.J74-D-I, No.3, pp.232-239(1991.3)
小林研究室のページにもどる.