データベースのトランザクション処理について整理する（その1）

はじめに

この記事はオライリーから出版されている「詳説データベース」から得られた知識を自分用にまとめるための記事です。自分なりの解釈を含みまとめるので、もしかすると誤りが含まれているかもしれません。

トランザクション

データベース管理システムにおける動作の、分割不可能な単位。複数の操作をひとまとめにしたものである。
以下のACID特性を維持する必要がある。

1. 原子性（Atomicity）

• 分割不可能であり、トランザクション内のすべてのステップが成功するか、しないかとなる。
  • 部分的にトランザクションを適用することはできない。
• トランザクションは最終的にコミットかロールバックが行われる。

1. 一貫性（Consistency）

• データベースのすべての特性（制約・参照整合性など）を維持したまま、データベースをある有効な状態から別の有効な状態へ変化する。
• 別の言い方をすると、トランザクションの前後でデータの整合性が保たれる。

1. 分離性（Isolatiion）

• 並列して実行される複数のトランザクションは互いに干渉を受けない。
• 状態変更の可視化のタイミングや並行するトランザクションにどの変更を可視化するかを定義する。

1. 永続性（Durability）

• 何らかの障害があっても、データベースのすべての変更をディスク上に永続化する。

これらを実現するための基本コンポーネントとして「トランザクションマネージャ」「ロックマネージャ」「ページキャッシュ」「ログマネージャ」が存在し、これらによってデータベースシステムが構成される。

バッファ管理

大半のデータベースは、永続ストレージとメインメモリの2種類の記憶装置で構成される。永続ストレージへのアクセスは一般的に遅いので、アクセスする回数を減らすためにページをメモリ内にキャッシュする。

メモリにキャッシュされたページは、他のプロセスがディスク上のデータを変更していない、という前提のもとに利用できる。このアプローチは仮想ディスク（ページキャッシュまたはバッファプール）と呼ばれる。

用語まとめ

• ページイン
  • 未キャッシュのページがディスクから読み込まれること
• フラッシュ
  • キャッシュされたページに変更が加えられ、ディスクに書き戻すこと
• ダーティ
  • キャッシュされたページに変更が加えられたものの、フラッシュされていない状態

キャッシュ

キャッシュの利用率を高めることで、永続ストレージにアクセスせずにより多くの読み取り、書き込みに対応できる。
ただし、ページキャッシュには容量に限りがあるので、古いページの退避が必要になる。ページの内容がディスクと同期済みであれば即座に退避できるが、そうでなければ（ダーティであれば）フラッシュする必要がある。

データベースがクラッシュした場合に、フラッシュされなかったデータはすべて失われてしまう。そのため、フラッシュはチェックポイントプロセスと協調して動作し、永続化されるようにする。
チェックポイントプロセスは、WAL（ログ先行書き込み）とページキャッシュを制御し、フラッシュ済みのキャッシュに関する操作のログのみ廃棄するように管理する。

ページキャッシュの容量限界に達したとき、古いページを退避させないと新しいページがロードできない。
退避させるためのルール（退避ポリシー・ページ置換ポリシー）に基づいて行われる。例は以下。

ポリシー例

• FIFOとLRU
  • First In First Out（先入れ先出し）
    • 最も利用頻度が高いと想定されるページは真っ先にページインする。
    • このアルゴリズムではそれが最初に置換されてしまうので実用的でない。
  • Least Recently Used
    • 利用履歴による管理
• CLOCK
  • アクセスビットを利用してページ参照を管理
• LFU
  • Least Frequent Used
    • 利用頻度による管理

リカバリ

ログ先行書き込み（WAL: Write Ahead Log またはコミットログ）はクラッシュ、リカバリに使用されるディスク上の構造。
キャッシュされた内容がディスクへのフラッシュで書き戻されるまでは、操作履歴を保持するディスク上のコピーはWALにだけ存在する。
WALは追記型なので、書き込まれた内容はイミュータブル。

すべての状態の変更は、更新前イメージと更新後イメージ、あるいはそれらに対するundoとredoにより表現できる。

• 更新前イメージに対するredo -> 更新後イメージ
• 更新後イメージに対するundo -> 更新前イメージ

物理ログと論理ログを使用することで、レコードやページをある状態から別の状態へ変化させることができる。
多くのデータベースシステムではこれらの物理ログ、論理ログ、undo、redoのアプローチを利用している。論理ログを使用して同時実行性とパフォーマンスのためにundoを実行し、物理ログを使用してリカバリ時間を改善するためにredoを実行する。

メモリ内で行われた変更をいつディスクにフラッシュすべきかの決定のため、stealポリシーとforceポリシーを定義する。

• stealポリシー
  • ページのフラッシュを、トランザクションがコミットされる前であっても許容する
• no-stealポリシー
  • コミットされていないトランザクションの内容をディスクにフラッシュすることを許容しない
• forceポリシー
  • トランザクションがコミットされる前に、変更されたすべてのページをディスクにフラッシュする
• no-forceポリシー
  • トランザクションの間に変更されたページの中に、まだフラッシュされていないページがあったとしてもコミットを許容する

undoはコミットされたトランザクションでforceされたページの更新をロールバックする。redoはコミットされたトランザクションで実行された変更をディスクに適用する。

no-stealポリシーを使用すると、redoのエントリのみを使用したリカバリの実装が可能になる。
forceポリシーを使用すると、クラッシュリカバリにおいて追加作業を行わなくてもコミット済みのトランザクションの結果を再構築できるが、必要なI/Oのためトランザクションに時間が比較的長くかかる。

ARIES（Algorithm for Recovery and Isolation Exploiting Semantics）

ログ先行書き込みアルゴリズムの一つ。steal/no-forceを採用。
このシステムが論文で解説されたのは1992年であるが、概念やアプローチ、パラダイムは現在においても重要な意味を持っているので調べてみるのが良い。