それが僕には楽しかったんです。

僕と MySQL と時々 MariaDB

CMU Database Systems をひたすら追っていく ~21 Database Recovery~

この記事は「けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 24 日目の記事です。

はじめに

今回は実際にリカバリをどのように行うかという話。

Aries

Algorithm for Recovery and Isolation Exploiting Semantics の略で IBM が 1990 年代に研究したもの。
これを完全に採用しているものは少ないが、この手法に類似した方法を取っている。

ARIES の処理手順

  • WAL: ディスクに変更が書き込まれる前に変更をストレージに書き込む。
  • Repeating History during redo: 再起動時にアクションをリトレースし、クラッシュ前の正確な状態に戻す。
  • Logging Changes during undo: UNDO アクションを記録して、処理に失敗した場合はそのアクションを再度繰り返さないようにする。

WAL Records

グレコード形式を拡張して、追加情報を持つ必要がある。全てのログレコードに LSN*1を追加することで対応する。

  • 各ページには Page LSN が含まれ、最新の更新を示す。
  • またフラッシュされた最大の LSN も持つ
  • ディスクに書き込まれる前に、 page LSN <= flushed LSN となるようにログをフラッシュする

Normal Execution

Transaction Commits

  • COMMIT レコードをログに追加する。
  • トランザクションの COMMIT レコードへの全てのログはディスクにフラッシュされる。
  • コミットに成功すると TXN-END レコードを書き込む。これは内部でのみ使用されるためすぐにフラッシュする必要がない。

Transaction Abort

Compensation Log Record

  • CLR という更新レコードのアクションを取り消すためのアクションを記述する
  • 次に取り消される LSN も undo Next ポインタとして持っておく

アルゴリズム

  • ABORTレコードを書き込む
  • 更新を逆順い再生して、変更を削除する。更新毎に CLR エントリを書き込み以前の値を復元する
  • 最後に TXN-END ログレコードを書き込む

ARIES Recovery

ARIES は 3 つのフェーズで構成されている。
クラッシュ後は起動時にそのフェーズを逐次実行していく。

  • Analysis: WAL を読んでバッファプール内のダーティページとクラッシュ時のアクティブなトランザクションを確認する
  • Redo: ログ内の適切なポイントから始める全てのアクションを繰り返す
  • Undo: クラッシュする前にコミットしなかったトランザクションのアクションを元に戻す

おわりに

簡単にまとめたけど、これを一つずつちゃんとまとめないと理解できない気がしてきた

*1:ログシーケンス番号