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

ミドルウェアとかやってます

CMU Database Systems をひたすら追っていく ~20 Logging Schemes~

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

はじめに

今日はログ周りの話。
WAL とか、ACID の原子性、耐久性、一貫性などを担保するための重要な要素。

Logging Schemes

リカバリアルゴリズムはデータベースに置いて一貫性、原子性、耐久性を確保する上で需要な要素となっている。
このリカバリアルゴリズムで行う大きく分けて2つにわかれる。

  • DBMS が障害から回復するために通常のトランザクション処理中に行うアクション
  • データベースの原子性、一貫性、耐久性を保証する状態に回復できなかった場合のアクション

またここのでキーワードとして以下の2つがある。

Failure Classification

DBMS で起こる障害は大きくわけて 3 つに分類できる。

Transaction Failures
System Failure
  • Software Failure: DBMS のソフトウェア的な問題でシステムを終了する必要がある場合
  • Hardware Failure: DBMS をホストしているマシンがクラッシュするなど
Storage Media Failure:
  • Non-Repairable Hardware Failure: ディスク障害、不揮発性ストレージの一部がクラッシュする。これから回復するにはアーカイブバージョンから復元するしかない。

Buffer Pool Management Policies

バッファプールを管理するポリシーの2つを紹介する。

例えば、No-Steal + Force で実装するなら。
変更がディスクに書き込まれなかった場合は、中止されたトランザクションによる変更を元に戻す必要はない。
また、コミット時に全ての変更がディスクに書き込まれることが保証されているため変更をやり直す必要はない。
ただし、トランザクションが変更する必要のある全てのデータがメモリに収まらない場合、トランザクションがコミットする前のダーティページをディスクに書き込まないため、そのトランザクションを実行できないという制限がある。

Steal Policy

DBMS がコミットされていないトランザクションが不揮発性ストレージ内のオブジェクトに対して最新のコミットを上書きするかどうか

  • Steal: 許可する
  • No-Streal: 許可しない
Force Policy

トランザクションがコミットされる前に DBMSトランザクションによって行われた全ての更新がストレージに反映されることを保証するかどうか。

  • Force: 保証される
  • No-Force: 保証されない

Write-Ahead Logging

ディスクページに変更が加えられる前にデータベースに加えられた全ての変更のログをログファイルに記録する手法。
殆どの DBMS で使用されているが、リカバリするためにはログを追う必要があるので処理に時間が掛かる。
ログはDBを復旧するための UNDO, REDO に必要な全ての情報を持っている。
Steal + No-Force システムを例に解説する。

Implementation

更新されたページの関連する全てのログレコードはページ自体がストレージに書きこまれるよりも前に永続化される。

Deferred Updates

  • トランザクションがコミットされるまで DBMS がダーティレコードをディスクに書き込むのを防ぐ場合、変更前の値を保持する必要はない。
  • トランザクションのメモリ使用量が DBMS 側の使用可能なメモリ量より大きい場合は機能しない。
  • ログに元の値がない場合は UNDO することができない(Steal ポリシーはこのために使用する)

Checkpoint

WAL の大きな問題としログファイルが肥大化するという問題がある。
クラッシュ時にこのログファイルが肥大化していると、ログを追ってリカバリする処理に時間がかかることがある。
そのため、チェックポイントを設け定期的にバッファの持つ情報をディスクにフラッシュする必要がある。

チェックポイントはどの程度設けるのが良いという基準はなく、チェックポイントが多すぎるとパフォーマンスが低下し、少なすぎるとその意味が薄れてしまう。
そのため、DBMS が担う役割や要求パフォーマンスに左右される。

Blocking Checkpoint の実装
  • 新たなトランザクションの生成を止め、アクティブなトランザクションが全て完了するのを待つ
  • メモリに存在するログレコードとダーティブロックをストレージにフラッシュする。
  • ログにチェックポイントエントリを書き込みストレージにフラッシュする。

おわりに

次はリカバリについて