このページでは、トランザクションのACID特性、共有ロックと専有ロック、デッドロック、2相ロック方式、MVCCなどの同時実行制御がわかります。
- 一言で言うと：
- DBMS（データベース管理システム）が、たくさんの人が同時に使っても、壊れても、データを正しく保つ仕組みと、速く動かす工夫の話
- 正しさの約束（ACID特性）、同時に使うときの交通整理（ロック、MVCC）、壊れたときの復旧（ログ、チェックポイント、ロールバック／ロールフォワード）、速さ（インデックス、オプティマイザ、チューニング）が出てくる
約束（トランザクション、ACID特性）→ 同時に使う（ロック、デッドロック、2相ロック、MVCC）→ 壊れたら戻す（ログ、WAL、チェックポイント、障害の3種類、バックアップ）→ 速く探す（インデックス、オプティマイザ）→ 速さを保つ（分割、再編成）
覚え方の軸
- ACIDは「全部かゼロか・矛盾なし・混ざらない・消えない」
- 原子性（A）はCOMMITかROLLBACKのどちらか、一貫性（C）は矛盾がない、隔離性（I）は同時に動かしても順番に動かした結果と同じ、耐久性（D）はCOMMITしたら障害でも消えない
- ロックは「読むなら共有、書くなら専有」
- 共有どうしだけ同時OK。専有が絡むと待つ
- 粒度が小さいほど同時に動けるが、ロックの手間（オーバヘッド）が増える
- 逆の順番でロックするとデッドロック。同じ順番ならデッドロックしない
トランザクション管理：ACID特性（★）
- トランザクション管理：
- DBMSが持つ、複数の利用者が同時にデータベースにアクセスしても、データの矛盾を起こさない仕組み
- トランザクション：
- トランザクション管理を行うための、SQL処理の最小単位
- 「回復の単位（unit of recovery）」とも呼ばれる
- 例えば、「AさんからBさんへの振込み」なら、「Aの口座から引く」と「Bの口座に足す」が1つのトランザクション
- TPモニタ：
- アプリケーションプログラムとDBMSの中間に位置するミドルウェア
- トランザクションのACID特性を保証する「トランザクション管理機能」を持つ
ACID特性（★）
| 特性 | 中身 |
|---|---|
| 原子性（Atomicity） | 更新処理トランザクションが正常終了した場合にのみデータベースへの反映を保証し、異常終了した場合は処理が何もなかった状態に戻すこと。すべての処理が完了するか（All）、まったく実行されていない状態か（Nothing）のどちらかで終わらなければならない。COMMIT（正常終了）とROLLBACK（異常終了）で実現する |
| 一貫性（Consistency） | トランザクションの処理で、データベース内のデータに矛盾が生じないこと。つまり、常に整合性のある状態が保たれていること |
| 隔離性（Isolation） | 複数のトランザクションを同時（並行）に実行した場合と、順（直列）に実行した場合の処理結果が一致すること。独立性ともいう |
| 耐久性（Durability） | いったん正常終了（COMMIT）したトランザクションの結果は、その後障害が発生してもデータベースから消失しないこと。つまり、トランザクションの再実行を必要としない |
- COMMIT（コミット）：
- 更新処理を確定し、データベースへの反映を保証する
- ROLLBACK（ロールバック）：
- 更新処理をすべて取り消し、トランザクション開始時点の状態へ戻す
- トランザクションのスケジューリング：
- 複数のトランザクションを同時に実行しても、それが正しい順で実行されるように順序づけすること
- 基本的な考え方は、並行実行の結果と直列実行の結果が等しくなるように調整すること
- この直列可能性を保証する方法にロックがある
- ACIDの例え：
- 原子性は、振込みで「引いたのに足されない」が起きない（全部やるか、全部やらないか）
- 一貫性は、振込みの前後で、2人の残高の合計が変わらない
- 隔離性は、2人が同時に振り込んでも、1人ずつ順番に振り込んだのと同じ結果になる
- 耐久性は、「振込完了」と表示された後に停電しても、振込みは消えない
- 結果整合性：
- ACID特性では、厳密な一貫性（完全一貫性）が求められる
- これに対し、結果的に一貫性が保たれればよいという考え方が結果整合性
- 分散トランザクション分野や、ビッグデータを高速に処理するためのNoSQLなどで取り入れられている
同時実行制御：同時に使っても矛盾させない（★）
- 同時実行制御（並行性制御）：
- 複数のトランザクションを同時に実行しても、矛盾を起こさずに処理を実行するメカニズム
- 代表的な方法は、ロック（単版同時実行制御）と多版同時実行制御
- 単版同時実行制御：
- 多版同時実行制御に対して、ロックによる通常の同時実行制御をこう呼ぶ
① ロック
- ロックが必要な理由：
- ACID特性の隔離性により、複数のトランザクションを同時実行しても、結果は直列実行した結果と同じにならなければならない
- でも、同時実行制御をしない環境では、結果が違ってしまう場合がある
変更消失（ロストアップデート）の例（★）
- TR1がaを読む：
- ①TR1が、データa（値は5）を読み込む
- TR2もaを読む：
- ②TR2も、データa（値は5）を読み込む
- TR1が更新：
- ③TR1が「a＋5」で、aを10に更新（COMMIT）
- TR2が更新：
- ④TR2が「a＋10」で、aを15に更新（COMMIT）
- 結果：
- ⑤aを読むと15。TR1の更新内容（＋5）が失われている
- 変更消失（ロストアップデート）：
- このように、ある更新が、別のトランザクションの更新で上書きされて消えること
- 正しい結果：
- TR1、TR2を順に実行すれば、データaの値は 5 ＋ 5 ＋ 10 ＝ 20 になる
- ダーティリード：
- 他のトランザクションが更新中の、コミットされていないデータを読み込んでしまうこと
- 上の例で、TR1がまだCOMMITしていないaをTR2が読んでいたら、それがダーティリード
- ロック（鍵）：
- 変更消失などを防ぐため、DBMSはデータaにロックをかけ、先にデータaにアクセスしたトランザクションの処理が終了するか、ロックが解除されるまで、他のトランザクションを待たせる
- トランザクションの終了時点で、ロックは解除される
- ロックの例え：
- 共有の予定表を、1人が書き込んでいる間は「使用中」の札を掛けて、他の人に待ってもらう
② デッドロック
- デッドロック：
- ロックを複数のデータに対して行おうとすると、互いにロックの解除を待ち続ける状態に陥ることがある。この状態
デッドロック発生の仕組み
| トランザクション | データを専有する順序 |
|---|---|
| TR1 | A → B → C |
| TR2 | B → C → A |
| TR3 | A → B → C |
- 前提：
- 各トランザクションは、表の順にデータを専有し、トランザクション終了時に3つの資源を一括して解放する
- TR1とTR2のデッドロック：
- TR1がAをロックし、TR2がBをロックする
- TR1は次にBがほしいが、TR2がBを持っているので進めない
- TR2は（Cの後に）Aがほしいが、TR1がAを持っているので進めない
- お互いに相手の解放を待ち続ける
- デッドロックが起きる組合せ：
- 違う順や逆の順でデータを専有するトランザクションの間では、デッドロックが起きる可能性がある
- データを専有する順序が等しいトランザクション（TR1とTR3）の間では、デッドロックは起こらない
- デッドロックの検出と解除：
- デッドロックが起きているかは、待ちグラフを作って、閉路（サイクリック）を持つかどうかで判定できる
- 待ちグラフでデッドロックを検出したら、そのトランザクションのうち1つを強制的に終了させて解除する
- 待ちグラフの例：
- X → Z → Y → X のように矢印が一周していれば、X、Z、Yがデッドロック状態（輪に入っていないWは関係ない）
- このうち1つを強制終了させれば、デッドロックは解除される
- デッドロックの例え：
- 細い一本道で、向かい合った2台の車が「そっちが下がれ」と譲らない。全員が「同じ方向から入る」ルールにすれば起きない
③ ロック方式
| 方式 | 中身 | 直列可能性 | デッドロック |
|---|---|---|---|
| 2相ロック方式 | 「使うすべてのデータにロックをかけ（第1相）、処理後ロックを解除する（第2相）」。各トランザクションは、必要なロック獲得命令をすべて実行した後にだけ、ロック解除命令を実行できる | 保証される | 発生の可能性が残る |
| 木規約 | データに順番を付け、その順番どおりにロックをかけていく。順番付けには木（有向木）を使う | 保証される | 発生しない |
- 2相ロッキングプロトコル：
- 2相ロック方式は、2相ロッキングプロトコルともいう
- 木規約のルール：
- ①最初に、任意の節にロックをかける
- ②次にロックをかけられるのは、その節の子だけ
- ③ロックの解除は、任意の時点でできる
- 有向木：
- 方向を持った有向グラフの1つ
- 木規約の弱点：
- トランザクションの同時実行性が低くなるので、特殊な場合にしか使われない
- 2相ロック方式の例え：
- 引っ越しで、必要な部屋の鍵を全部借りてから作業し、終わったら返し始める。返し始めたら、もう新しい鍵は借りない
④ ロックの種類
- ロックモード：
- DBMSは、トランザクションの同時実行性を高めるため、専有ロック（占有ロック）と共有ロックの2つを用意している
- 専有ロック：
- データ更新をする場合に使うロック
- データに対する他のトランザクションからのアクセスは一切禁止される
- 占有または排他ともいう
- 共有ロック：
- 通常、データの読取りの際に使うロック
- 参照のみを許可する
- 共用ともいう
同時実行の可否（★）
| 後続 ＼ 先行 | 共有 | 専有 |
|---|---|---|
| 共有 | ○ | × |
| 専有 | × | × |
- 共有ロックの利点：
- 先行トランザクションが共有ロックをかけたデータを、後続トランザクションも参照できるので、待ちが発生せず、同時実行性を高められる
- ロックの種類の例え：
- 共有ロックは、図書館の閲覧。何人でも同時に読める
- 専有ロックは、原稿の書き直し中。書いている間は誰も読めないし、他の人も書けない
⑤ ロックの粒度
- ロックの粒度：
- ロックは、表、ブロック、行といった単位でかけられる。このロックの単位
- ブロック：
- 物理的なI/Oの単位
| 粒度 | 同時実行性 | オーバヘッド | 管理 |
|---|---|---|---|
| 小さい（行） | 高い | ロックの回数が多く、ロック制御のオーバヘッドが増える | − |
| 大きい（表） | ロックの解除待ちが長くなり、低い | 少ない | トランザクション管理は容易 |
- 粒度の例え：
- 行ロックは「1つの席だけ予約」、表ロックは「お店ごと貸し切り」。貸し切りは手続きは楽だが、他の客は入れない
⑥ 多版同時実行制御（MVCC）
- 多版同時実行制御（MVCC：MultiVersion Concurrency Control）：
- 同時実行性を高め、かつ一貫性のあるトランザクション処理を実現する仕組み
- 通常のロックの問題：
- 専有ロック中（更新中）のデータは参照できないので、後続トランザクションはロックの解除を待つ
- MVCCの仕組み：
- 更新中のデータに参照要求をした場合は、更新前（トランザクション開始前）の内容が返される
- だから、後続トランザクションは待たずに処理できる
- つまり、専有ロックと共有ロックの同時確保を可能にして同時実行性を高め、後続トランザクションに、現在からさかのぼったある時点の一貫性のあるデータを提供することで、整合性を欠いたデータの参照を防ぐ
- MVCCの例え：
- 店員が商品棚を入れ替え中でも、客には「入れ替え前の棚の写真」を見せて買い物を続けてもらう
整合性を欠いたデータの参照（★）
| 現象 | 中身 |
|---|---|
| ダーティリード | 他のトランザクションが更新中の、コミットされていないデータを読み込む |
| アンリピータブルリード | 再度読み込んだデータが、他のトランザクションにより更新されている（前回読み込んだ値と一致しない） |
| ファントムリード | 再度読み込んだデータの中に、他のトランザクションによって追加・削除されたデータがある（前回と検索結果が違う） |
- 3つの現象の例え：
- ダーティリードは、まだ下書きの原稿を読んでしまう
- アンリピータブルリードは、もう一度読んだら、同じ行の金額が変わっていた
- ファントムリードは、もう一度検索したら、行が増えていた（幽霊のように現れた）
⑦ その他の同時実行制御方式
その他の同時実行制御
| 方式 | 中身 |
|---|---|
| 時刻印方式（時刻印アルゴリズム） | トランザクションが発生した時刻印（タイムスタンプ）Tと、データの最新時刻印（読込み時刻印Tr、書込み時刻印Tw）を比べて、読み書きの判断をする。読込みは Tw ≦ T のときだけ行い、読み込んだ後は、Trに T を設定する。書込みは Tr ≦ T かつ Tw ≦ T のときだけ行い、書き込んだ後は、Twに T を設定する |
| 楽観的方式 | 同じデータへのアクセスはめったに起きないと考えて処理を進め、書き込む直前に、そのデータが他のトランザクションに更新されたかを確かめる。更新されていればロールバックし、されていなければ書き込む |
- デッドロックが起きない：
- 上の2つの方法は、ロックをかけないので、デッドロックは発生しない
- 時刻印方式の考え方：
- 「自分より新しいトランザクションが、すでにそのデータを触っていたら、手を出さない」
- 例えば、T＝10のトランザクションは、Tw＝12（もっと新しいTRが書いた）のデータは読めない
- 楽観的方式の例え：
- 共有のファイルを鍵をかけずに編集し、保存する直前に「誰かが先に保存していないか」を確かめる。先に保存されていたら、自分の編集はやり直し
混同しやすいペア
- 原子性 ／ 一貫性
- 原子性は、全部やるか全部やらないか（COMMIT、ROLLBACK）
- 一貫性は、データに矛盾がない（整合性が保たれている）
- 隔離性 ／ 耐久性
- 隔離性（独立性）は、同時実行しても、直列実行と同じ結果になる（ロックで実現）
- 耐久性は、COMMITした結果は、障害が起きても消えない
- ACID特性 ／ 結果整合性（BASE特性）
- ACID特性は、厳密な一貫性（完全一貫性）を求める
- 結果整合性は、最終的に一貫性が保たれればよい（NoSQLなど）
- 変更消失（ロストアップデート） ／ ダーティリード
- 変更消失は、ある更新が、別のトランザクションの更新で上書きされて消える
- ダーティリードは、コミットされていないデータを読み込む
- アンリピータブルリード ／ ファントムリード
- アンリピータブルリードは、もう一度読むと、値が更新されている
- ファントムリードは、もう一度読むと、行が追加・削除されている
- 2相ロック方式 ／ 木規約
- 2相ロック方式は、全部ロックしてから解除する。直列可能性は保証するが、デッドロックは起こりうる
- 木規約は、木の順番にロックする。デッドロックが起きないが、同時実行性が低い
- 共有ロック ／ 専有ロック
- 共有ロック（共用）は、読取り用。参照だけ許可。共有どうしは同時OK
- 専有ロック（占有、排他）は、更新用。他からのアクセスを一切禁止
- ロックの粒度が小さい ／ 大きい
- 小さいと、同時実行性は高いが、オーバヘッドが大きい
- 大きいと、管理は容易だが、同時実行性が低い
- 単版同時実行制御 ／ 多版同時実行制御（MVCC）
- 単版は、通常のロック。更新中のデータは、ロック解除まで待つ
- 多版は、更新中でも更新前のデータを返すので、待たずに読める
- 時刻印方式 ／ 楽観的方式
- 時刻印方式は、タイムスタンプを比べて読み書きを判断する
- 楽観的方式は、書き込む直前に、他に更新されていないか確かめる
- どちらもロックを使わないので、デッドロックは起きない