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