リカバリ 東大生研　情報融合研究センタ 喜連川優

リカバリの考え方 トランザクション障害からのリカバリとは障害時点に最も近いconsistentな状態へ復帰することを指す ログ：リカバリのための情報格納 カタストロフィーからの復帰 テープ上のバックアップからログを適応して(redo)障害直前の状態まで戻す アボート等からの回復 オンラインログを利用して、処理を元に戻す（undo）ことにより正常な状態へ戻す

更新手法 Deferred update Immediate update トランザクションがコミットするまで、更新情報をすぐにはディスクに反映しない手法。NO-UNDO/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 force 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はコミット済み 　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