Database Lecture 7/1

並行制御とロック

ある町のホテルの空室数をX、この町にいく飛行機の空席数をYとする。

H-S --- Sがホテルの予約を取る
H-T --- Tがホテルの予約を取る
J-S --- Sが飛行機の予約を取る
J-T --- Tが飛行機の予約を取る
LX-S --- SがXをロックする
LX-T --- TがXをロックする
LX-S --- SがYをロックする
LX-T --- TがYをロックする
RX-S --- SがXをロック解除する
RX-T --- TがXをロック解除する
RY-S --- SがYをロック解除する
RY-T --- TがYをロック解除する

(1) この二つのトランザクションがデッドロック(dead lock)する操作の順序を示せ
(2) デットロックしないようにするには、うまく順序を付けてロックしてやれば良い。どうすれば良いか説明せよ。
(3) デットロックしないtribialでない実行例を示せ。

(1) LX-S, LY-T, LX-T, LY-S
(2) X,Y の順に必ずロックすることに決めれば良い
(3) LX-S --- SがXをロックする
LX-S --- SがYをロックする
LX-T --- TがXをロックする (ここでTはSがロックを解除するまで待つ)
H-S --- Sがホテルの予約を取る
J-S --- Sが飛行機の予約を取る
RX-S --- SがXをロック解除する (ここでTはロックがとれる)
H-T --- Tがホテルの予約を取る
RY-S --- SがYをロック解除する
LX-T --- TがYをロックする
J-T --- Tが飛行機の予約を取る
RX-T --- TがXをロック解除する
RY-T --- TがYをロック解除する

問題2: この場合に平行して動作できる操作を横に並べて、

     LX-T
     RX-W-S RX-W-T

アボート

実際には、トランザクション一つにつきロックを一つだけとるような方法が簡単であり効果的だ。しかし、この方法は一度にたくさんのアクセスが来る場合には適さない。

もし、データのアクセス頻度が大きく、デッドロックは稀にしか起きないのならば、「取りあえずロックしていく。ロックがとれないようだったら、しばらく待って、あきらめる」という方法がある。(楽観的平行制御 Optimistic Concurrency Control)

この場合、あきらめたトランザクションは、今まで行った作業の取り消しをおこなう必要がある。これをトランザクションのアボート(abort)という。アボートは、ディスクアクセスなどに失敗した場合、その他、アプリケーションの都合によっても起きる。

例

前の例題で、飛行機だけ予約が取れても、ほてるだけ予約が取れても、役にたたない。もし、それぞれの残りが一つの場合、SとTが飛行機とホテルを別々に予約できてしまう。(そして、お互いにキャンセル待ちに入る...) そうしないためには、飛行機とホテルをセットにすれば良かった。

セットにしない場合でも、飛行機とホテルの予約をとって、どちらかが取れなかったらアボートするという方法でも良い。この時にも、予約の順序を決めると、それぞれが一つづつ残っているのに誰も予約できなかったというようなこと防ぐことができる。

カスケーディングアボート

2相ロックを使っていれば、通常はロックによるアボートでは、カスケーディングアボートは起こらない。しかし、その他の要因によるアボートではカスケーディングアボートが無制限に起きる可能性がある。

これを防ぐには、2相ロックの解除を徐々にではなく、一度に行えば良い。(狭義の2相ロック) しかし、この方法もアクセス頻度が大きい場合には並列度を下げるので嫌われることが多い。

コミットとログ

commit work (トランザクションがちゃんと終わったことを示す)
rollback (トランザクションは失敗して、なかったことにする)

普通、データベースシステムは、どのトランザクションがコミットしたかを記録している。これはログ(log)と呼ばれる。何もしなければログはどんどん大きくなっていく。カスケーディングアボートに備えるために、ずーとログを取っておかなくてはならないからである。

ある時点で、データベースの状態をとっておき、それを正規の状態と決めれば、その時点より前のログを取っておく必要はない。それはバックアップ(backup)と呼ばれる。バックアップの後は、明示的にトランザクションログを消さなくてはならないデータベースも多い。

Unix には、sync というコミットに近い動作がある。これは、アプリケーションからは書き込みは終わっているが、OSはディスクにデータを書き込んでいない状態を解消する。したがって、Unix上のファイルシステムをもとにしたデータベースは本当の意味で安全になることはない。多くのデータベースではファイルシステムを経由せずに直接ディスクを操作することでこれを回避している。

Time Warp メカニズム

リアルタイムシミュレーションを考えよう。この時、シミュレーションするイベントは時刻が付いている。シミュレーションするオブジェクトは、状態の変更を関連するオブジェクトにメッセージとして送る。これでだいたいの場合はうまくいく。気まずいのは自分が既に状態を変更してしまった後に、過去の時点のメッセージが届いた場合である。この時に受け取ったものは自分自身をアボートし、アンチメッセージを送る。アンチメッセージを送るためにオブジェクトはメッセージの履歴を覚えてなければならない。

これは一種の楽観的平行制御である。この方法では全体に仮想的な時間(Virtual Time)が流れていて、局所的には時間が逆転する(Time warp) 可能性がある。このシステムでも、ある時点の実行を固定する操作を導入すれば、覚えておくメッセージを減らすことができる。

この方法は、データベースのアボート、コミットと類似している。

2相コミット

まず、トランザクションは(これは一つのサイトにある)、「コミットするぞ」というメッセージをすべてのサイトに送る。そして「コミットしていいぞ」というメッセージが全部のサイトから来た時点で、ログにトランザクションを書き込む。もし、一つでも「だめだ」という答が来たら、トランザクションはロールバックする。どちらの場合も、その結果を全部のサイトに伝える。

これらは実際のデータベース、特にSQL levelからは見えない動作であるが、一応、常識として覚えておこう。

PerlによるMiniSQLのアクセス

#!/usr/open/bin/perl5

use Msql ();

$host = 'bw04';
$database = 'test';
$Db = Msql->Connect($host,$database) or die;

$sth = $Db->Query("select * from アンケート\n") or die $Msql::db_errstr;

for (0..$sth->numfields-1) {
  print "type=",  $sth->type->[$_];
  print "\tlength=",$sth->length->[$_];
  print "\tname=",$sth->name->[$_];
  print "\n";
}
$sth->DataSeek(0);
while (@row = $sth->FetchRow) {
  print "@row\n";
}

print "\n";

Prev Next Kono's home page