概要
情報技術の基礎として理解しておきたいデータベース管理について、トランザクション、ACID特性、排他制御、セマフォ、障害回復、性能向上を整理する。
トランザクション管理は、複数の処理が同時に動いてもデータの整合性を保ち、障害が起きても復旧できるようにする仕組みとなる。
ACID特性、ロック、ログ、ロールバック・ロールフォワードをつなげて理解することが重要となる。
この記事の構成
- トランザクション
トランザクションとは、データの整合性を保つことを目的にデータベース操作の一連の流れをひとまとめにした処理範囲または、 処理単位。 - 排他制御
排他制御は、同じデータへ複数のトランザクションが同時にアクセスした際の競合を制御し、整合性を保つ仕組み。 - セマフォ
セマフォの意味と要点を具体例から整理。 - データベース障害の回復処理
データベース障害の回復処理の意味と要点を具体例から整理。 - データベースの性能向上
データベースの性能を向上させる代表的なもので、テーブル更新毎にキーとデータの格納場所（ポインタ）を保持し、検索時に索引することで、検索速度を上げるインデックスがある。
トランザクション
トランザクションとは、データの整合性を保つことを目的にデータベース操作の一連の流れをひとまとめにした処理範囲または、処理単位を指す。
※ MVCC（Multi-Version Concurrency Control：多版同時実行制御）は、同じデータの複数の版を管理し、トランザクションごとに適切な版を参照させることで、読取りと書込みの競合を減らす同時実行制御技術である。具体的な挙動はDBMSによって異なる。
また、トランザクションが持つべき性質として、以下 \(4\) つの特性があり、これをACID特性と呼ぶ。
-
原子性／不可分性（Atomicity）
トランザクション処理は、コミット（すべて実行される）または、ロールバック（一つも実行されない）のどちら一方の結果でなければならない。 -
一貫性／整合性（Consistency）
トランザクション前後でデータの整合性を保ち、一貫したデータを確保しなければならない。 -
独立性／隔離性（Isolation）
複数のトランザクションを同時実行しても、定められた分離レベルに従って互いの途中結果から受ける影響を制御。最も厳しい直列化可能レベルでは、逐次実行した場合と同等の結果を保証する。 -
耐久性／永続性（Durability）
一旦コミットされたトランザクションの結果は、システム障害が発生しても失われないよう永続化されなければならない。
排他制御
排他制御は、同じデータへ複数のトランザクションが同時にアクセスした際の競合を制御し、整合性を保つ仕組みである。ロック対象が異なれば、複数のトランザクションが並行して更新できる場合もある。
-
共有ロック
データを参照する場合に用いられるロックで、一般に複数のトランザクションが同時に共有ロックを取得できる一方、競合する専有ロックの取得を待たせる。 -
専有ロック（排他ロック）
データを更新する場合などに用いられ、競合するロックを他のトランザクションが取得できないようにする。通常の参照まで待たせるか、いつ取得・解放するかは、DBMS、ロック粒度、分離レベル、MVCCの実装によって異なる。 -
デッドロック
複数のトランザクションが、互いに相手の保持する行、テーブルなどの資源の解放を循環して待ち続け、処理を進められない状態を指す。
すべてのトランザクションで資源を取得する順序を統一することは、デッドロックを減らす代表的な対策となる。 -
\(2\) 相ロック（ツーフェーズロック）
ロックを取得できるが解放しない成長相と、ロックを解放できるが新たに取得しない縮退相の \(2\) 段階に分けるロック制御方法。最初のロックを解放した後は、新しいロックを取得しない。
セマフォ
セマフォとは、共有の資源（リソース）に対して、利用制御する排他的な仕組みのことを指し、セマフォの値（セマフォ変数 \(S\)）は、利用可能な資源数（リソース数）を表す。
また、プログラムリソースの占有有無によって、セマフォ変数 \(S\) が増減し、\(0\) の場合は、リソース解放待ちとなり、\(1\) 以上となるまで待機する。
このセマフォ変数 \(S\) の制御は、次の \(P\) 操作、\(V\) 操作で管理される。
-
\(P\) 操作（デクリメント）
資源をロックし、セマフォ変数 \(S\) を \(1\) つ減算して、セマフォを確保する。 -
\(V\) 操作（インクリメント）
資源をアンロックし、セマフォ変数 \(S\) を \(1\) つ加算して、セマフォを解放する。
データベース障害の回復処理
以下、大別したデータベース障害とその回復方法。
-
トランザクション障害
メモリ不足やデッドロックに伴う強制終了などにより、トランザクションが異常終了する障害。
DBMS に異常はないため、ロールバックによりトランザクション開始前または指定したセーブポイントの状態へ戻すことで復旧する。 -
システム障害
DBMSやOSの異常終了、電源断などにより、メモリ上の情報が失われる障害。
再起動時にログを利用し、未完了の更新を取り消したり、コミット済みでデータファイルへ未反映の更新を再実行したりして復旧する。 -
ハードウェア障害（媒体要因）
ハードディスクの故障等でデータ自体が破損する障害で、日次など定期的に取られるバックアップデータから復旧する。
バックアップ後に更新されたデータについては、保存されたログを適用して復旧時点までロールフォワードする。 -
ログファイルによる障害復旧対策
多くのDBMSではWAL（Write-Ahead Logging）を用い、データファイルを更新する前に、その変更を表すログを永続ストレージへ書き出す。ログの形式や保存先はDBMSの実装や構成によって異なり、必ず更新前後のデータを別のハードディスクへ保存するとは限らない。
コミット時点でデータページがまだディスクへ反映されていなくても、必要なログが永続化されていれば、障害後にコミット済みの変更をREDOして復旧できる。未コミットの変更を取り消す処理はUNDOに相当する。
バックアップへログを適用してバックアップ取得後の状態まで進める復旧を、一般にロールフォワードという。 -
チェックポイント
ログに記録された変更が一定時点までデータファイルへ反映済みであることを示す基準点。障害回復では直近のチェックポイントを起点に必要なログを再適用できるため、回復時に調べる範囲を減らせる。
データベースの性能向上
データベースの性能を向上させる代表的なもので、テーブル更新毎にキーとデータの格納場所（ポインタ）を保持し、検索時に索引することで、検索速度を上げるインデックスがある。
※ インデックスは、単一列だけでなく複数列、式、条件を対象に作成できるDBMSもある。テーブル更新時にはインデックスも更新されるため、検索性能だけでなく更新コストも考慮する必要がある。
また、インデックス情報は、様々なデータ構造で持つことができるため、システム仕様やデータベース環境に応じて、検索対象や検索方法に適したデータ構造を選ぶ必要がある。
以下、代表的なインデックスのデータ構造。
-
\(B\)木インデックス（\(B\)-tree）
\(B\)木は、一つのノードに複数のキーと子へのポインタを持ち、木の高さが偏らないように保つ平衡多分木である。キーを順序付けて保持し、ルートから分岐探索することで検索処理を高速化する。等価検索やBETWEENなどの範囲検索、並び順を利用した走査に適している。AND、OR、NOTを含む条件で利用されるかは、列、演算子、選択性、実行計画などによって決まる。
※ 木構造については、下記の先行ページを参照。 -
\(B+\)木インデックス（\(B+\)-tree）
実データへの参照をリーフ（葉）に持ち、リーフ同士を順序に沿ってポインタでつないだデータ構造。等価検索に加え、範囲検索や順次走査を効率良く行える。 -
ビットマップインデックス
列の値ごとに該当行をビット列で表すデータ構造。状態区分など値の種類が少ない低カーディナリティの列を、複数条件で集計・検索する用途に適している。 -
ハッシュインデックス
キー値からハッシュ関数（※）で求めたハッシュ値を用いて、対応する格納位置を探索する。主に等価検索に適しており、大小比較を使う範囲検索には一般に適さない。異なるキーから同じハッシュ値が得られる衝突への対処方法は、DBMSの実装によって異なる。
※ ハッシュ関数、シノニムについては、下記の先行ページを参照。
応用情報技術 - アルゴリズム > 探索アルゴリズム
まとめ
- トランザクションは複数のデータベース操作を一つの処理単位として扱い、コミットで確定、ロールバックで処理前の状態へ戻す。
- ACIDの一貫性は整合性を保つ性質、独立性は同時実行する他の処理からの干渉を抑える性質。
- 共有ロック同士は両立するが、専有ロックは競合する操作をブロックする。デッドロックは複数処理が互いの解除を待ち続ける状態。
- 2相ロックはロックを増やす段階と解放する段階を分け、トランザクションの直列化可能性を確保する。
- 障害回復では、更新前ログを使うロールバックと更新後ログを使うロールフォワードを使い分け、チェックポイントを復旧処理の起点に利用。