データ指向アプリケーションデザイン | 第07章 トランザクション

発表者: パク・ヒョンド、イ・スンイク

曖昧なトランザクションの概念

ACID

ACIDは、データベーストランザクションが安全に実行されることを保証する性質を指す略語である。

原子性（Atomicity）

データベースは、すべて反映されるか、何も反映されないことを保証する。原子性により、部分更新がより大きな問題を引き起こすことを防げる。

例: 航空券
チケットは、支払いと予約が必ず同時に行われるか、どちらも行われない必要がある。支払いは成功したが座席予約はされていない、という状態は許されない。
一つのトランザクションは航空券予約だけでなく、ホテル、移動手段、現在の為替レートで正確に換金される処理にも適用される。
出典: wikipedia

一貫性（Consistency）

トランザクションが正常に完了すると、常に一貫性のあるデータベース状態を維持することをいう。
出典: wikipedia

例: 会計システムでは、すべての口座にわたる貸方と借方が常に一致しなければならない。

一貫性（C）は、実際にはACIDに属するものではなく、アプリケーションの性質と見なされる。
データベース自体だけでは、不変条件に違反する誤ったデータの書き込みを防げないためである。
これはアプリケーションの責任と考えられ、一貫性を達成するためにデータベースの原子性と分離性に依存できる。

分離性（Isolation）

同時に実行されるトランザクションは互いに分離され、干渉できない。
あるトランザクションが複数回書き込む場合、別のトランザクションはその内容をすべて見るか、何も見ないかのどちらかでなければならず、一部だけを見ることはできない。

永続性（Durability）

データベースシステムの目的は、データを失う心配のない安全な保存場所を提供することである。
永続性は、トランザクションが正常にコミットされたなら、ハードウェア障害が発生したりデータベースが停止したりしても、そのトランザクションで記録したすべてのデータは失われないという保証である。

単一オブジェクト操作と複数オブジェクト操作

単一オブジェクト書き込み

原子性と分離性は、単一オブジェクトを変更する場合にも適用される。

そのため、ストレージエンジンはほぼ普遍的に、一つのノードに存在する単一オブジェクトレベルで原子性と分離性を提供することを目標にする。

例: 20KBのJSON文書をデータベースに書き込む場合。

最初の10KBを送信した後にネットワーク接続が切れる場合、データベースがディスク上の既存値を上書きしている途中で電源が落ちる場合、または文書を書き込んでいる最中に別のクライアントがその文書を読み、部分的に更新された値を読む場合を考える。

複数オブジェクトトランザクションの必要性

複数オブジェクトトランザクションは、データの複数部分を同期された状態に保つ必要があるときに必要である。

トランザクションがなくても、複雑なデータの書き込みと読み取りを行うアプリケーションは実装できる。

しかし、原子性がなければエラー処理ははるかに複雑になり、分離性がなければ並行性の問題が発生する可能性がある。

• 複数オブジェクトトランザクションは、外部キーなどの参照が有効な状態で保たれることを保証する。
• 複数文書を一度に更新するとき、非正規化されたデータの同期が崩れることを防ぐ。
• トランザクション分離性がなければ、あるインデックスではレコードが見えるが、別のインデックスはまだ更新されていないためレコードが見えない場合がある。

緩い分離レベル

コミット後読み取り（READ COMMITTED）

最も基本的なトランザクション分離レベルであり、このレベルでは二つのことを保証する。

• データベースから読むとき、コミット済みデータだけを見る。ダーティリードがない。
• データベースに書くとき、コミット済みデータだけを上書きする。ダーティライトがない。

ダーティリード防止

ダーティリードとは、あるトランザクションで処理した作業が完了していないにもかかわらず、別のトランザクションから見える現象である。

図7-2. 分離性違反: トランザクションが別トランザクションで書かれたがコミットされていないデータを読む（ダーティリード）

ダーティリードを防ぐことが有用な理由:

• ダーティリードが起きると、別のトランザクションが一部は更新された値、一部は更新されていない値を見ることがある。
• トランザクションがアボートされるとすべてロールバックされるべきだが、ダーティリードを許可すると、後でロールバックされるデータを別トランザクションが見る可能性がある。

ダーティライト防止

ダーティライトとは、二つのトランザクションが同じオブジェクトを同時に更新しようとするとき、先に書かれた内容がまだコミットされていないトランザクションによるものであり、後から実行された書き込みがその未コミット値を上書きする場合である。

図7-5. 別トランザクションで競合する書き込みを実行するとき、ダーティライトがあると内容が混ざる可能性がある。

別トランザクションで競合する書き込みを実行するとき、ダーティライトがあると内容が混ざる可能性があり、ダーティライトを防ぐことでいくつかの並行性問題を回避できる。

コミット後読み取りの実装

コミット後読み取りは、Oracle 11g、PostgreSQL、SQL Server 2012、MemSQLなどでデフォルト設定として使われている分離レベルである。

• ダーティライト防止: トランザクションがコミットまたはアボートされるまでロックを保持する。このロックはコミット後読み取りモードでデータベースにより自動的に実行される。
• ダーティリード防止: 過去のコミット済み値と現在書き込み中の新しい値の両方を記憶し、そのトランザクションが実行中の間は過去の値を読ませることでダーティリードを防げる。

図7-4. ダーティリード防止: ユーザー2はユーザー1のトランザクションがコミットされた後にだけxの新しい値を見る。

ダーティリード防止: ユーザー2はユーザー1のトランザクションがコミットされた後にだけxの新しい値を見る。

スナップショット分離と反復読み取り（Snapshot Isolation）

図7-6. 読み取りスキュー: Aliceは一貫性が崩れた状態のデータベースを見る。

コミット後読み取り分離レベルでも並行性バグが発生する可能性があり、この現象を非反復読み取り（nonrepeatable read）または読み取りスキュー（read skew）という。

上のような場合、数秒後に更新すれば一貫性のある口座を見られるが、状況によってはこのような不整合を許容できない場合もある。

例: バックアップでは元本とコピーのデータに差が出る。分析クエリや整合性確認では、大きな範囲をスキャンするクエリが異なる時点のデータベースの一部を見て、誤った結果を返す可能性がある。

スナップショット分離は、各トランザクションがデータベースの一貫したスナップショットから読む実装である。

つまり、トランザクションは開始時にデータベースへコミットされていたすべてのデータを見る。後で別トランザクションによりデータが変わっても、各トランザクションは特定時点の過去データを見るだけである。

スナップショット分離の実装

**多版型並行性制御（multi-version concurrency control, MVCC）**は、データベースがオブジェクトの複数バージョンを一緒に保持する技法である。

Q. コミット後読み取りもダーティリードを防ぐためにバージョンを使うが、何が違うのか。

A. コミット後読み取りはクエリごとに独立したスナップショットを使い、スナップショット分離はトランザクション全体に同じスナップショットを使う。つまり、バックアップされたレコードの複数バージョンのうち、どの以前のバージョンまで探すかが異なる。

一貫したスナップショットを見る可視性ルール

トランザクションはデータベースでオブジェクトを読むとき、トランザクションIDを使って何を見られ、何を見られないかを決定する。

出典: Real MySQL 8.0

動作方式:

• トランザクションIDがより大きい、つまり現在のトランザクション開始後に開始したトランザクションが書いたデータは、そのトランザクションのコミット有無に関係なくすべて無視される。

インデックスとスナップショット分離

多版データベースでのインデックスの動作:
一つの選択肢は、インデックスがオブジェクトのすべてのバージョンを指し、インデックスクエリが現在のトランザクションから見えないバージョンを除外し、ガベージコレクションがどのトランザクションからも見えなくなった古いオブジェクトバージョンを削除するときに対応するインデックス項目も削除する方法である。

PostgreSQL:

• 同じオブジェクトの別バージョンが同じページに保存できる場合、インデックス更新を回避する最適化を実行する。

CouchDB、Datomic、LMDB:

1. 書き込み時コピー（append-only/copy-on-write）の変種を使用する。
   ツリーのページが更新されるとき、上書きする代わりに変更された各ページの新しいコピーを作成する。ツリーのルートに至るまで存在する親ページはコピーされ、それらの子ページの新バージョンを指すように更新される。書き込みの影響を受けないページはコピーする必要がなく、不変のまま残る。
2. 追記専用Bツリーを使用する。
   書き込みを実行するすべてのトランザクションは新しいBツリールートを作成し、特定のルートはそれが作成された時点に該当するデータベースの一貫したスナップショットになる。後で実行される書き込みは新しいツリールートだけを作成でき、既存のBツリーを変更できないため、トランザクションIDに基づいてオブジェクトを除外する必要がない。
   ただし、この方法でもコンパクションとガベージコレクションを実行するバックグラウンドプロセスが必要である。

反復読み取りと紛らわしい名前

スナップショット分離は読み取り専用トランザクションで有用であり、SQL標準にスナップショット分離の概念がないため、複数のデータベースで異なる名前で呼ばれる。

• Oracle: Serializable
• PostgreSQL、MySQL: Repeatable Read

更新損失の防止

二つのトランザクションが同時に作業すると、二番目の書き込み作業が最初の変更を含まないため、変更の一つが失われる可能性がある。

解決策:

• 原子的書き込み操作
• 明示的なロック
• 更新損失の自動検出
• Compare-and-set
• 競合解消とレプリケーション

原子的書き込み操作

• 書き込み操作に原子性（Atomicity）を与えることで並行性安全性を得る。
• exclusive lockを獲得して実装する。更新が適用されるまで、別トランザクションはそのオブジェクトを読めない。
• または、すべての原子的操作を単一スレッドで実行するよう強制する方法もある。

明示的なロック

• アプリケーションで更新するオブジェクトを明示的にロックすること。
• 別トランザクションが同時に同じオブジェクトを読もうとすると、最初のread-modify-write周期が完了するまで待つよう強制される。

リスティング開発チーム > 07. トランザクション > スクリーンショット 2022-04-01 午後 1.30.42.png

例7-1. 行を明示的にロックして更新損失を防ぐ

BEGIN TRANSACTION;

SELECT * FROM figures
  WHERE name = 'robot' AND game_id = 222
  FOR UPDATE; (1)

-- 移動が有効か確認した後
-- 前のSELECTで返された位置を更新する。
UPDATE figures SET position = '4' WHERE id = 1234;

COMMIT;

更新損失の自動検出

• 複数トランザクションの並列実行を許可し、トランザクション管理者が更新損失を発見するとトランザクションをabortし、再試行を強制する方法。

Compare-and-set

• 値を最後に読んだ後で変更されていない場合だけ更新を許可することで、更新損失を回避する。

-- データベース実装によって安全な場合も安全でない場合もある
UPDATE wiki_pages SET content = 'new content'
  WHERE id = 1234 AND content = 'old content';

競合解消とレプリケーション

• ロックとcompare-and-set操作は、データの最新コピーが一つだけあると仮定する。
• マルチリーダーまたはリーダーレスレプリケーションを使うデータベースは、一般的に複数の書き込みが同時に実行され、非同期で複製されることを許可する。
• したがって、データの最新コピーが一つだけであるとは保証できない。
• レプリケーションが適用されたデータベースでよく使われる方法は、書き込みが同時に実行されるとき、一つの値に対して複数の競合バージョンが作成されることを許可し、後で競合を解消してそれらのバージョンをマージすることである。

書き込みスキューとファントム

• ほぼ同時に二つのトランザクションが開始されたと仮定する。

図7-8. アプリケーションバグを引き起こす書き込みスキューの例

• データベースでスナップショット分離を使うため、どちらも2を返し、二つのトランザクションは次の段階へ進む。
• 最低一人の医師が呼び出し待機しなければならないという要件に違反する。
• この現象を書き込みスキュー（write skew）という。

書き込みスキューを特徴づける

• 書き込みスキューは、二つのトランザクションが同じオブジェクト群を読み、その一部を更新するときに現れることがある。

書き込みスキューを引き起こすファントム

• あるトランザクションで実行した書き込みが、別トランザクションの検索クエリ結果を変えることをファントム（Phantom）という。

競合の具体化

• 競合の具体化とは何か。最初のselect時にロックできるオブジェクトがなかったため、データベースに人工的なロックオブジェクトを追加するということ。
• 対象rowを事前に作成し、lockをかける。トランザクション対象になる特定範囲のすべての組み合わせについて、事前にrowを作成しておく。たとえば会議室予約なら次の6か月分などである。
• 予約するトランザクションは、テーブルから目的の対象rowをロックできる。事前に生成されているためである。
• ここで生成されたrowは、単に同時変更を防ぐためのロック集合であり、実際に使われるデータではない。
• 欠点: 並行性制御メカニズムがアプリケーションデータモデルへ漏れ出すのは好ましくない。ほかの代替案が不可能なときの最後の手段として考慮する。

直列性

DBの並行性を管理する方式の問題点:

• 分離レベルは理解しにくく、データベースごとに実装の一貫性がない。
• アプリケーションコードを見て、特定の分離レベルでそのコードを実行するのが安全か判断しにくい。特に、同時に起きるすべてのことを把握できない大きなアプリケーションではなおさらである。
• 並行性問題は通常、非決定的、つまり間欠的なのでテストしにくい。タイミングが悪いときだけ問題が発生する。
• 代案は直列性分離を使うことである。
• 直列性分離は通常、最も強力な分離レベルと考えられる。
• 複数トランザクションが並列で実行されても、最終結果は並行性なしに一つずつ直列実行された場合と同じになることを保証する。

直列性を提供する三つの技法

• 文字どおりトランザクションを順番に実行する。
• 2段階ロック。
• 直列性スナップショット分離のような楽観的並行性制御技法。

実際の直列実行

• 並行性問題を避ける最も簡単な方法は、並行性を完全に取り除くことである。
• 一度に一つのトランザクションだけを、単一スレッドで直列に実行すればよい。
• 欠点は性能である。

トランザクションをストアドプロシージャ内にカプセル化する

• データベース初期には、トランザクションがユーザー活動全体の流れを含められるようにする意図があった。
• 航空券予約の複数過程、つまり経路選択、料金、利用可能座席の探索、旅行日程の決定などを一つのトランザクションとして表現し、原子的にコミットすることである。
• この方法を実装するためにデータベーストランザクションがユーザー入力を待たなければならないなら、非常に遅くなると予想される。
• 代わりに、トランザクションコード全体をストアドプロシージャとしてデータベースに事前提出する。
• トランザクションに必要なデータはすべてメモリにあり、ストアドプロシージャはネットワークやディスクI/Oなしに非常に速く実行されると仮定する。

図7-9. 対話型トランザクションとストアドプロシージャの違い（図7-8の例トランザクションを使用）

パーティショニング
各トランザクションが単一パーティション内でのみデータを読み書きするようにパーティショニングできるなら、各パーティションは別パーティションと独立して実行される独自のトランザクション処理スレッドを持てる。
この場合、各CPUコアに各自のパーティションを割り当てることで、トランザクション処理量をCPUコア数に合わせて線形に拡張できる。
しかし、複数パーティションにアクセスする必要があるトランザクションがあるなら、コーディネーションオーバーヘッドがあるため、単一パーティショントランザクションより非常に遅い。

直列実行まとめ
トランザクションの直列実行は、いくつかの制約の中で直列性分離を得る実用的な方法になった。

• すべてのトランザクションは小さく速くなければならない。遅いトランザクション一つが全体処理を遅延させる可能性があるため。
• アクティブなデータセットがメモリに載る場合に利用が制限される。単一スレッドトランザクションでディスクにアクセスすると、システムは非常に遅くなる。
• 書き込み処理量は、単一CPUコアで処理できる程度に十分低くなければならない。
• 複数パーティションにまたがるトランザクションも使えるが、使用できる程度には厳しい制限がある。

2段階ロック（2PL）

• トランザクションAがオブジェクトを読み、トランザクションBがそのオブジェクトに書き込みたいなら、BはAがコミットまたはアボートされるまで待たなければならない。これにより、BがAに気づかれず突然オブジェクトを変更できないことが保証される。

• トランザクションAがオブジェクトに書き込み、トランザクションBがそのオブジェクトを読みたいなら、BはAがコミットまたはアボートされるまで待たなければならない。図7-4で見たように、2PLを使う場合はオブジェクトの過去バージョンを読むことは許可されない。

• スナップショット分離と比較すると、スナップショット分離では読む側は決して書く側を妨げず、書く側も決して読む側を妨げない。

2段階ロックの実装

• MySQL、SQL Serverで直列性分離レベルを実装するために使われる。
• ロックは共有モード（shared mode）または排他モード（exclusive mode）で使われる。
• ロックが非常に多く使われるため、デッドロック、つまり二つのトランザクションが互いに待つ状態が非常に起こりやすい。

2段階ロックの性能

• 最大の弱点は性能である。
• ロックを獲得し解放するオーバーヘッドのため遅い。
• より重要な原因は並行性が低下すること。並行性と性能は反比例する。

述語ロック

条件に合うすべてのオブジェクトにロックを獲得することである。

SELECT * FROM bookings
   WHERE room_id = 123 AND
      end_time > '2018-01-01 12:00' AND
      start_time < '2018-01-01 13:00'

• 述語ロックは時間がかかる。条件に合うロックを確認するのに時間がかかるためである。
• このため、2PLをサポートするほとんどのデータベースは、実際にはインデックス範囲ロックやnext-key lockを実装して使用する。

インデックス範囲ロック

• たとえば、正午から午後1時まで123番の部屋を予約することに対する述語ロックを、すべての時間範囲で123番の部屋を予約するものとして近似してロックする。
• 上の例では、room_idまたは時間値にインデックスがあるはずなので、そのインデックス範囲にlockをかける。
• インデックス範囲ロックは述語ロックより精密ではないが、直列性を維持するために必須な範囲より広い範囲をロックする場合がある。しかしオーバーヘッドが低いため、よい妥協案になる。
• 範囲ロックを取得できる適切なインデックスがなければ、テーブル全体に共有ロックを取得する形に代替することもある。

直列性スナップショット分離（Serializable Snapshot Isolation, SSI）

• 直列性分離と良い性能は共存できるのか。
• 現在最も有望なのが直列性スナップショット分離である。
• スナップショット分離に比べ、わずかな性能損失があるだけである。

悲観的並行性制御 vs 楽観的並行性制御

• 2段階ロックは悲観的並行性制御メカニズムである。
  • 何かがうまくいかない可能性があるなら、何かをする前に状況が再び安全になるまで待つほうがよいという原則である。
• 直列性スナップショット分離は楽観的並行性制御メカニズムである。
  • 危険な状況が発生する可能性があるとき、トランザクションを止める代わりに、すべてがうまくいくという希望を持って進行するという意味である。
  • トランザクションがコミットしようとするとき、データベースは悪い状況が発生したか確認する。
  • 発生していればabortされ、再試行される。
  • 競合が激しいとabort率が上がるため性能が落ちる。
  • 予備容量が十分で、トランザクション間の競合が激しすぎなければ、楽観的並行性制御技法は性能がよい傾向がある。
  • SSI = スナップショット分離 + 直列性競合検出およびabortさせるトランザクションを決定するアルゴリズム。

古い読み取りを検出する

図7-10. トランザクションがMVCCスナップショットから古い値を読んだか検出する

過去の読み取りに影響する書き込みを検出する

図7-11. 直列性スナップショット分離で、トランザクションが別トランザクションの読んだデータを変更する場合を検出する