←【ファイルとデータベース】シラバスへ

第13回講義内容へ→

←講義のツボメニューへ

トランザクション処理とデータベース制御〜たくさんの人に同一のデータベースを利用させるしくみ」

【2000.07.07 １限　第12回】

今回の主な参照箇所：文献[3]のP.23-27と、第１０回「分散データベースシステム」（P.189〜P.210）、この他、
[4]北川博之：データベースシステム、昭晃堂、pp.147-172、1996.
も参照した。

トランザクション

• アプリケーションにおけるひとまとまりの処理を構成するデータベース操作の集まりを「トランザクション」という。
• たとえば、預金口座Ａから別の口座Ｂに１万円を送金するという処理は、細部を無視すると以下のような一連のデータ操作からなる。
  
  read(A,x))
  read(B,y)
  x:=x-10000
  y:=y+10000
  write(A,x)
  write(B,y)
  
  read：データの読み出し
  write：データの書き込み
  read(A,x)：データベース中のAを読んでその値を変数xに転送。
  write(A,x)：変数xの値をデータベース中のAの値として書くこと。
  
• 上記の一連のreadやwriteは一つのトランザクションを構成し、そのすべてが適切に実行されて、初めてひとまとまりの送金処理として意味をなす。
• 従って、ＤＢＭＳにおけるデータ操作という視点ではreadやwriteが基本操作であるが、アプリケーションの立場からは個々のreadやwriteではなく、トランザクションがデータベース処理の単位でなければならない。
• コミットとアボート：
  • トランザクション中のデータ操作がすべて確定したものとしてデータベースに反映することを、「コミットする」という。
  • トランザクション中のデータ操作がすべて向こうだったとして棄却すること、「アボートする」という。
  ※トランザクションは必ず、コミットされるかアボートされるかのいずれかである。
• トランザクションをアボートするとき、なされていたデータ更新をすべて元の状態に戻すことを、「ロールバックする」という。

並行処理と直列可能性
１．並行処理における不整合

• トランザクションの並行処理：通常、ＤＢＭＳは複数のトランザクションからの基本操作要求をインターリーブして実行する。
• 並行処理における不整合の例
  

  トランザクションT1 read(A,x) x:=x+10000 write(A,x)

  トランザクションT2 read(A,y) y:=y-10000 write(A,y)

  この順序で基本操作が実行された場合、トランザクションT2の更新はデータベースに反映されない。
  

  トランザクションT1 s:=0 read(A,x) s:=s+x read(B,y) s:=s+y

  トランザクションT2 read(A,x) z:=z-10000 write(A,z) read(B,w) w:=w+10000 write(B,w)

  この順序で基本操作が実行された場合、トランザクションT1は誤った合計値を算出する。

２．直列可能性とスケジュール

• 上記のような不整合が生じないための一つの基準は、トランザクションT1...Tnを並行処理したときの実験結果が、それらを逐次処理したときの実行結果と一致すること。これを「直列化可能性」と呼ぶ。
• データベースに対する基本操作は、
  Ri(A)：トランザクションTiによる項目Aのread、
  Wi(A)：トランザクションTiによる項目Aのwrite、
  Ci：トランザクションTiのコミット、
  Ai：トランザクションTiのアボート
  のいずれかの基本操作の列とみなせる。
• トランザクションT1...Tnに対するスケジュールとは、T1...Tnの基本操作の前後関係は保持するという条件の元に、インターリーブして一列に並べたもの。すなわち、スケジュールはT1...Tnを並行処理する際のある一つの可能な基本操作の実行順序を表す。
• 例えば、上記の例のT1およびT2は以下のように表せる。
  T1:R1(A)R1(B)
  T2:R2(A)W2(A)R2(B)W2(B)
  
• T1,T2がそれぞれの最後のread,writeの直後にコミットを実行したとすれば、実行順序は以下のスケジュールで表せる。
  R2(A)W2(A)R1(A)R1(B)C1R2(B)W2(B)C2
  
• スケジュールは直列スケジュールと非直列スケジュールに分類される：
  • 「直列スケジュール」＝対象トランザクション群を何らかの順序で逐次処理する場合のスケジュール。
  • 「非直列スケジュール」＝直列スケジュール以外のスケジュール
• スケジュールの等価性の定義：同じトランザクションの集合に対する２つのスケジュールS1とS2は、次の条件を満たすとき競合等価であるという。
  1. S1においてRi(A)(wi(A))がWj(A)(Rj(A))に先行するならば、S2においても同様の関係が成り立つ。
  2. S1においてwi(A)がwj(A)に先行するならば、S2においても同様の関係が成り立つ。

ロックを用いた同時実行制御

• 実際のＤＢＭＳにおいて、直列可能性を保証するために使われるのが「ロック」である。
• 「ロック」＝ある資源に対して、他からアクセス出来ないように鍵をかけること。
• ロックの単位：データベース、レコード、ブロック、ページ、レコード中の任意のフィールド、など。
• ロックの２種：
  • 共有：後続に対し、共有しようとするものは受け付け、排他しようとする者は認めずはねつける。
  • 排他：後続の他者をはねつける。
• トランザクションがコミットまたはロールバックされると、かかっていたロックはすべて解除される。
• 通常は、トランザクションの最初に資源ごとにロックをかける操作を集中させ、トランザクションの最後にロックを解除する操作を集中させるので、「二相ロック（2 Phase Lock;2PL）」と呼ばれる。

デッドロック

• デッドロック：複数のユーザが複数の資源に同時にアクセスしようとすると起こる。
• デッドロックが起こったら、どちらかのトランザクションを強制的にロールバックして解決する。

時刻印を用いた同時実行制御

• 各トランザクションに発生順に一意的な時刻印を与え、その時刻印の順にトランザクションを逐次実行する場合と等価なスケジュールが生じるように制御を行う方法は、「時刻印順方式」と呼ばれる。
• この方式では、データベース中の各項目について、以下の２種類の時刻印を持たせる。
  • RTS(A)：これまでにAのreadを行ったトランザクションの時刻印のうち最大値。
  • WTS(A)：これまでにAのwriteを行ったトランザクションの時刻印のうち最大値。
• 時刻印TS(Ti)をもつトランザクションTiの項目Aのreadとwriteの操作は、以下の規約に従って行う。
  • read
    1. TS(Ti)<WTS(A)のとき、本来Tiが読み出すべきAの値はwriteにより失われてしまっているので、Tiはアボートする。
    2. それ以外の時：TiはAのreadを行うとともに、RTS(A)=max(RTS(A),TS(Ti))とする。
  • write
    1. TS(Ti)<RTS(A)のとき、Tiがwriteを行った後のA値をreadで読むべきトランザクションが先にreadを行ってしまっているので、Tiはアボートする。
    2. TS(Ti)>=RTS(A)かつTS(Ti)<WTS(A)のとき：同様にTiはwriteの時機を逸していしまっているのでアボートする。
    3. それ以外の時：TiはAのwriteを行うとともに、WTS(A)=max(WTS(A),TS(Ti))とする。

楽観的同時実行制御

• ほとんどのトランザクションがreadだけを行う場合や、複数トランザクションが同時に発生することがあまりない場合は、トランザクション同士の競合は低い。
• 「楽観的同時実行制御」は、とりあえず他のトランザクションとの競合はないものとしてトランザクションの実行を行い、終了の際に本当に競合がなかったかどうかを確認するというもの。
• 基本的手法：
  1. 読み出しフェーズ：
     トランザクション中の処理を実行する。ただし、readではデータベース中の項目の値をそのトランザクション固有の作業領域に読み出す。また、writeではその作業領域中で書き込みを行うだけで、データベースへの書き込みはいっさい行わない。
  2. 確認フェーズ：
     3.の書き込みフェーズにおいてデータベースへの書き込みを行った場合に、他のトランザクションとの競合が生じないかを、下記に述べる方法で確認する。
  3. 書き込み確認フェーズ：
     確認フェーズの確認処理をパスした場合には、作業領域内で更新された項目のデータベースへの書き込みを行いトランザクションをコミットする。もしパスしなかった場合には、トランザクションをアボートする。
• 確認方法：各トランザクションTiには、読み出しフェーズの開始時点で時刻印Start(Ti)、確認フェーズの開始時点で時刻印Validate(Ti)を与える。また、Tiが読み出しフェーズにおいてreadを行った項目とwriteを行った項目の集合を、それぞれrset(Ti),wset(Ti)とする。Tiの確認フェーズでは、
  Start(Ti)<Validate(Tj)<Validate(Ti)
  になる時刻印Validate(Tj)をもつすべてのトランザクションTjについて、
  Rset(Ti)∩wset(Tj)=φ
  という条件が満たされるか調べる。もし満たされなければ、Tiは確認処理をパスしたものとする。

参考：分散データベースシステム

• 「分散システム」＝処理要素があちこちにあって、その間に通信手段が存在し、個々の処理要素が協調して何かの処理を行うシステムのこと。
• 処理内容がデータベース操作の場合、「分散データベースシステム」という。
• 実際は、それぞれ別の場所で単独で稼働しているデータベース間でデー場の共有をはかる場合が多い。
• それぞれのシステムは「サイト」と呼ばれる。あるサイトを基準として「ローカルサイト」と呼び、それ以外のサイトを「リモートサイト」と呼ぶこともある。
• 分散システムの利点：拡張性が高いこと、負荷を分散できること。
• 分散システムの欠点：処理が複雑になること。
• 分散データベースシステムの欠点：
  • 分散同時実行制御
  • 分散トランザクション管理
  • データ辞書の分散化：データ辞書にはＤＢＭＳが管理するすべてのデータベースの情報が格納されており、データ操作のたびにデータ辞書を見るのでデータ辞書を分散環境のどこに置くかで効率が大きく変化する。
• 「アクセス透過性」＝ローカルサイトにあるデータもリモートサイトにあるデータも同一の方式でアクセスでき、ユーザにローカルとリモートの違いを意識させないこと。

---

←【ファイルとデータベース】シラバスへ

第13回講義内容へ→

←講義のツボメニューへ
←鈴木研究室ホームへ