トランザクションの学習メモ ― 並行性制御、分散コミット、シャーディング

接続された3つのデータベースを描いたイラスト

トランザクションを考えるときは、性能、処理の並列性、原子性を保証する範囲、水平スケールのしやすさなどのトレードオフが関わってきます。注文と明細をまとめて保存し、失敗したらロールバックするという基本から一歩進んで、同じデータを並行して更新するときや、1件の処理が複数のシャードにまたがるときには、どんな仕組みや調整が必要になるのでしょうか。まずは個々の方式を深掘りする前に、それぞれが何を保証し、どこで待ち時間や再試行、通信のコストが生じるのか、特性の全体像をざっくり押さえておきたいと思いました。

その入口として、本を読みながら出てきた用語を、何が壊れるか、同時実行をどう制御するか、複数の参加者でどう確定するか、データをどこに置くかの4つに分けて整理しました。

1. 同時実行で何が壊れるか

用語何が起きるか
ダーティーリードAがまだコミットしていない値をBが読む。Aがロールバックすると、Bは確定しなかった値を使ったことになる。
ダーティーライトAがまだコミットしていない書き込みをBが上書きする。
ロストアップデートAとBが残高100を読み、それぞれ10を引いて90を書き戻す。2回引いた結果が90になり、片方の更新が失われる。
ファントムAが同じ条件で2回検索する間にBが行を追加してコミットし、2回目の検索結果にその行が現れる。
ライトスキューAとBが共通の条件を読んで別々の行を更新し、両方の更新が残った結果、業務ルールが壊れる。

ライトスキューの例として、「当番を最低1人残す」というルールを考えます。いまはAとBの2人が当番で、どちらも自分を当番から外そうとしています。

順番トランザクションAトランザクションB
1当番が2人いると読む当番が2人いると読む
2Aを当番から外すBを当番から外す
3コミットするコミットする

スナップショット分離では、2つのトランザクションが別々の行に書き込むため、両方コミットできる場合があります。結果は当番0人です。両方とも正常終了しているので、エラー時にロールバックする実装では防げません。

ロストアップデートでは、同じ行に対する更新の片方が消えます。当番のライトスキューでは、別々の行への更新が両方残ります。更新先の行だけを見ても問題がわからないのは、「最低1人」という制約が複数の行にまたがっているからです。

仮にAが先に処理を終えていたら、Bは「残り1人」と読んで更新を見送ります。並行に実行しても、何らかの順序で1件ずつ実行した場合と同等になる性質を直列化可能性と呼びます。

2. 同時実行をどう制御するか

用語何をするか
悲観的並行性制御衝突し得る操作をロックなどで先に制御する。SELECT ... FOR UPDATE は対象行を先に押さえる例。
楽観的並行性制御まず処理を進め、競合を検査して、続行できない処理を中止する。更新時にバージョン番号を照合する方法が一例。
二相ロック(2PL)ロックを取得する段階と解放する段階に分ける。一度解放を始めたら、新しいロックは取らない。
述語ロックWHERE room_id = 1 AND status = 'reserved' のような検索条件で読んだ結果を保護する。既存行に加えて、後から条件に入ってくる行も考慮する。
インデックス範囲ロックインデックス上のキーの範囲や隙間を押さえる。たとえば id BETWEEN 10 AND 20 を読んだとき、範囲内への挿入を待たせる方式がある。
シリアライザブルスナップショット分離(SSI)スナップショットを読みながら処理を進め、読み書きの依存関係を追跡する。直列実行と矛盾し得る組み合わせを検出すると、トランザクションを中止する。ライトスキューも防げる。

悲観的・楽観的は、並行性制御の方針です。ロックで先に衝突を制御するのが悲観的な方針で、SSIのように処理を進めながら依存関係を追い、必要に応じて中止するのは楽観的な発想に近いです。

述語ロックとインデックス範囲ロックは、ファントムの例で考えると関係が見えます。id BETWEEN 10 AND 20 で現在存在する10と20の行をロックしても、その行ロックだけでは15の挿入を防げません。インデックス上の隙間まで押さえる方式なら、15の挿入も待たせられます。

PostgreSQLの SERIALIZABLE がSSIで使う「述語ロック」は、ある書き込みが先に実行されていたら、並行トランザクションの読み取り結果が変わっていたかを追跡するためのものです。この述語ロック自体は書き込みを待たせません。

当番の例では、Bの更新が「Bは当番だ」というAの読み取りに影響し、Aの更新もBの読み取りに影響します。SSIはこうした依存関係を追います。シリアライゼーション失敗が起きたら、アプリはトランザクション全体をやり直します。「当番が何人残っているか」を読み直すところからやり直すので、もう片方がコミットした後なら、残り1人だと判断できます。

PostgreSQL公式ドキュメント ― Transaction Isolation

3. 複数の参加者でどう確定するか

別々のシャードにある口座間で振り替える場合、出金だけ確定して入金が取り消されると困ります。ここで必要なのは、1件のトランザクションに参加したリソースの間で、コミットか中止かの決定をそろえることです。 このように、複数のDBやシャードなどにまたがる処理を1つのトランザクションとして扱うのが分散トランザクションです。以下の二相コミットはその確定を調整する方式で、XAはDBやキューなどを共通のインターフェースでその調整に参加させるための標準です。

用語何をするか
二相コミット(2PC)まず全参加者にコミットの準備ができるか確認する。全員が準備できればコミットを決め、準備できない参加者がいれば中止を決める。準備済みの参加者は、障害で最終決定がわからなくなると待つことがある。
三相コミット(3PC)最終コミットの前に PRE-COMMIT を挟む。ネットワーク分断がないなどの前提で、障害時に2PCのような待ち状態を避けることを狙う。
DB内部の分散トランザクションアプリからは1つのDBに見え、そのDBが内部の複数シャードにまたがる処理を調整する。
ヘテロトランザクション異なる種類のリソースをまたぐトランザクション。たとえばDBへの書き込みとメッセージキューへの送信を一緒に確定する。
XAトランザクショントランザクションマネージャーがXA対応のDBやキューなどを二相コミットで調整する。XAはそのための標準インターフェース。

二相ロックの二相は「取得と解放」。二相コミットの二相は「準備と決定」。 前者は複数のトランザクションをどう同時に実行するか、後者は1つのトランザクションを複数の参加者でどう確定するかに対応します。

Database System Concepts ― Distributed Databases(2PC・3PC)

4. データをどこに置くか

シャーディングは、データをキーなどで分割し、複数ノードに配置することです。クロスシャードトランザクションは、1件のトランザクションがその分割をまたぐことです。振替元と振替先の口座が同じシャードにあれば単一シャードで完結し、別々にあればクロスシャードになります。

ここは、シャーディング → 1件の処理が複数シャードに触れる → DB内部の分散トランザクションになる → 参加シャード間でコミットを調整する、という順に考えるとつながります。

たとえばSpannerでは、単一の分割単位への書き込みでもレプリカ間の通信があります。複数の分割単位にまたがる書き込みでは、そこに分割間の二相コミットが加わります。

Google Cloud公式ドキュメント ― Life of Spanner Reads & Writes

5. まとめ

分離レベルと防げる不整合のおさらい

まず、並行性制御の話を分離レベルごとに整理します。下の表は一般的な特性の概略です。「発生し得る」は必ず起きるという意味ではなく、その分離レベルだけでは防止を保証しないことを表します。

分離レベル・方式ダーティーリードリードスキューファントムロストアップデートライトスキュー
リードアンコミッテッド発生し得る発生し得る発生し得る発生し得る発生し得る
リードコミッテッド防止発生し得る発生し得る発生し得る発生し得る
スナップショット分離防止防止防止※実装・操作による発生し得る
シリアライザブル防止防止防止防止防止

リードスキューは、関連する複数の値を異なる時点の状態で読んでしまうことです。たとえば口座間の振替の途中で、片方は振替前、もう片方は振替後の残高を読むと、合計額が合わなく見える場合があります。

※スナップショット分離の「ファントムを防止」は、同じスナップショットに対する通常の読み取りが対象です。検索条件に関わる更新の競合まで防げるとは限らず、本文の当番の例のようなライトスキューは残ります。また、ロストアップデートの扱いはDBの競合検出や更新の書き方によって異なります。

分離レベルの名前と保証の対応はDBごとに異なります。たとえばPostgreSQLでは、READ UNCOMMITTEDはREAD COMMITTEDと同じ動作をし、REPEATABLE READはスナップショット分離を提供します。他のDBのREPEATABLE READも同じ保証だとは限らないため、利用するDBの仕様を確認します。

参考:PostgreSQL公式ドキュメント ― Transaction Isolation

この表が扱うのは、同時実行による干渉をどこまで防ぐかです。複数のDBやシャードで確定をそろえる分散コミット、調整の範囲を左右するデータ配置も合わせて考えると、記事全体のつながりが見えてきます。

今回の用語は、「同時実行で何が壊れるか」「同時実行をどう制御するか」「複数の参加者でどう確定するか」「データをどこに置くか」の4つに分けると、関係を追いやすくなりました。並行性制御は複数の処理の干渉を扱い、分散コミットは1つの処理に参加するDBやシャード間の確定を扱います。さらに、データの配置によって、どこまで調整が必要になるかも変わります。

守りたい業務ルールや原子性の範囲に応じて仕組みを選ぶと、ロックによる待ち時間、競合時の再試行、シャード間の通信などのコストが見えてきます。性能や並列性、水平スケールのしやすさを考えるときも、どの保証をどの範囲で必要としているかが出発点になります。

まずは用語を全部覚えるよりも、「何を守る仕組みで、そのためにどんな調整が増えるのか」を押さえておく。実際のDBの仕様や設計を読むときに、この全体像に立ち返りながら、必要な部分を深掘りしていきたいと思います。

コメントを残す

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です