Document

リカバリ
東大生研情報融合研究センタ
喜連川優
リカバリの考え方
• トランザクション障害からのリカバリとは障
害時点に最も近いconsistentな状態へ復帰
することを指す
• ログ：リカバリのための情報格納
• カタストロフィーからの復帰
– テープ上のバックアップからログを適応して
(redo)障害直前の状態まで戻す
• アボート等からの回復
– オンラインログを利用して、処理を元に戻す
（undo）ことにより正常な状態へ戻す
更新手法
• Deferred update
– トランザクションがコミットするまで、更新情報
をすぐにはディスクに反映しない手法。NOUNDO/REDO 方式と呼ばれる。
• Immediate update
• Immediate Update
– コミット前にデータベースが更新される可能性
がある。UNDO/REDO 手法と呼ばれる。
– すべての更新をＤＢに反映した後にのみ、コ
ミットするという手法を採用する場合には
redoは不要となるため、UNDO/NO-REDO手
法と呼ばれる。
• ＯＳとの関連が非常に強いのが実情
• 性能上極めて重要なため、ＯＳに制御を委ねる
のではなく、ＤＢＭＳが強制管理
• <disk page address, buffer location>
• pin, un-pin操作
• 更新技法
– Inplace update 元の場所を更新（ログが必須）
– Shadowing
新しい場所に更新を保存
ＷｒｉｔｅＡｈｅａｄＬｏｇ
• in-place updateをする場合には、リカバリ
のためにはログが不可欠であり、before
imageがＤＢ上で上書きされる前にログ上
にBIを強制的に書き込む必要がある。この
処理は write ahead loggingと呼ばれる。
• steal/ no steal
– コミット前には更新をＤＢに書かない(no steal)：
deferredと同義
– 書き込みを許す。(steal)
• force/ no force
– コミット時にＤＢをすぐ更新(force)
– 更新しなくても良い(no force)
• 通常のＤＢＭＳは steal/ no force
– Stealにしないと巨大なバッファ空間が必要
– No forceにすると、更新頻度の高いページを毎
回ディスクに書き込む必要がなくなる。
チェックポイント
• ＤＢＭＳのバッファの更新された全てのブロックを
定期的にＤＢに吐き出す。
• この時、ログ上に[checkpoint]なるレコードを記録
• [checkpoint]以前の[commit,T]なるトランザクショ
ンに対しては障害発生時にredo不要。
• チェックポイントの期間設定はどうする？
– ○分毎あるいは
– ○個のトランザクションがコミットする毎
チェックポイントの取得
•
•
•
•
トランザクションの実行を一時的にサスペンド
更新された主記憶上のバッファをＤＢへ強制的に反映
[checkpoint]の書き込み
トランザクションの再開
– 追加情報：アクティブトランザクションのリスト、それぞれに対して、最初
と最後のログレコードの場所も書き込んでおくと、UNDOが容易。
• Fuzzy checkpointing
– [checkpoint]レコードを書き、ＤＢに書きながら通常トランザクションを実
行。書き込み終了以前には前の[checkpoint]を利用。完了すると当該
[checkpoint]に切り替え。
ロールバック
• データベースを更新し、コミット前に障害が発生し
たらロールバックが必要。
• undo logを利用
• 例
– Ｔ３が最初に起動され、＊でＢを更新
– Ｔ２が＊＊時点でその値を参照し、更に更新、また、Ｔ
２は下の＊＊でもＤを更新。
– 従ってＴ３をロールバックすると、その更新を参照した
Ｔ２も同時にロールバックする必要がある。
• 通常はcascade rollbackをすることはまづない。プ
ロトコルをstrictにしている為。
• ログにreadを入れているが、これはcascade
rollbackの必要性を判断する為のものであり、
strictにすればこのエントリも不要。
Deferred Update時のリカバリ
• Deferred Update protocol:
– トランザクションはコミットポイントに至るまでデータ
ベースを変更出来ない。
– トランザクションは全ての更新をログに書きそれをディ
スクに強制書き込みするまではコミットポイントに至ら
ない
• 一般的にはトランザクションが短い実行時間で、
更新対象数が少ない場合にのみ適応可能。そ
れ以外はバッファ溢れが生ずる。
• ＷＡＬと同じこと。
• ＮＯＵＮＤＯ/ＲＥＤＯプロトコル
同時実行制御とリカバリ
（単一ユーザ）
• 最近のチェックポイント以降、コミットしたトランザ
クションのリスト及び、アクティブトランザクショ
ンのリスト（この場合高々一つ）を利用
• コミットしたトランザクションwrite操作をログから
抽出し、記載された順にREDOを施す。その後再
投入
• ここでREDOとは[write_item,T,X,new_value]なる
エントリに対して、new_valueをXに設定すること。
• REDO= idempotent
– リカバリ最中にシステムがダウンしても回復可能
T1のwriteのみREDO
T2は未コミット
マルチユーザ環境
• 同時実行制御とリカバリは強い関連が有り一体
化することが多い。一般的には並列性を上げよう
とすると、その分だけリカバリが複雑になること
が多い。
• Strict Two Phase Locking:コミット時点までロック
を開放しない。
• 前述同様に最近のチェックポイント以降、コミット
したトランザクションリストとアクティブトランザク
ションリストを利用
• ログに記載された順でコミットしたトランザクショ
ンのみそのWRITE操作をREDO。アクティブでコ
ミット前のトランザクションを再投入
例
•
•
•
•
•
•
•
ｔ１：チェックポイント
T1はコミット済み
T3,T4は未コミット
t2 ：システムダウン
T2とT3はコミット、T4とT5はまだ。
T1のREDO不要チェックポイント前
T2とT3のREDO必要、チェックポイントの後でコ
ミットしている。
• T4とT5は REDO不要
リカバリの効率化
• REDOを昔から現在にむかって適応する
のではなく、時間を遡って適用する。
REDONEリストを作成し、既にREDOして
いたら、無視する。（どうせ上書きしている
ので）
• マルチユーザのリカバリの例
UNDO/REDO Recovery based
on Immediate Updates
• 最近のチェックポイント以降のコミットしたトランザク
ションのリスト（コミットリスト）とアクティブトランザク
ションのリストを利用
• アクティブトランザクションのwrite操作をUNDOする。
• UNDOとは[write_item, T,X,oldvalue,newvalue] なるロ
グエントリに関して、Xの値をoldvalueに設定。UNDO
操作はログに書き込まれた順序と逆の順序で行う。
• コミットしたトランザクションに関しては前述のように
REDO操作を行う。
Shadow Paging
• トランザクション実行開始時にcurrentからshadow
にページへのポインタをコピー、それをディスク
へ格納。ディレクトリはメモリ常駐
• 前の状態をshadow pageとしてshadow directoryに
保持
• トランザクションはcurrent directoryの指すページ
を操作
• コミット時にはshadowを破棄
• アボート時にはcurrentを破棄
• 問題
– Currentからshadowへのディレクトリ移動をATOMICに実行するこ
とが前提
– ディスク上でのデータページが動くため最適化困難
– GC

Download Report