# 直列化可能性 ## 定義 直列化可能性(serializability)とは、トランザクションが並行実行されても、結果が何らかの直列実行(一度に 1 つずつ実行)と同じになることをデータベースが保証する、最強の分離レベルである。データベースはすべての可能な競合状態(race condition)を防止する。実現手法は主に 3 系統に分かれる: (1) 実際の直列実行、(2) 2相ロック(2PL)、(3) 直列化可能スナップショット分離(SSI)。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Serializability") ## 実際の直列実行(Actual Serial Execution) 単一スレッドで 1 度に 1 トランザクションずつ実行することで、競合検出・防止のロジックを完全に省く方式。2000 年代以降実用化された背景には (1) 主記憶に収まるデータセットの増加、(2) OLTP トランザクションが短く読み書き数が少ないという 2 つの発展がある。VoltDB/H-Store・Redis・Datomic が採用する。 - **ストアドプロシージャの必須化**: 対話的なマルチステートメントトランザクション(クエリのたびにアプリ⇔DB 間のネットワーク往復)を許すと単一スレッドのスループットが著しく低下するため、トランザクション全体を事前にストアドプロシージャとして DB に送る必要がある - **シャーディング**: 各シャードに専用の実行スレッドを割り当てれば CPU コア数に比例したスケールが可能だが、複数シャードにまたがるトランザクションは全シャードで足並みを揃える必要があり著しく遅い(VoltDB 実測でクロスシャード書き込みは約 1,000/秒、単一シャードの桁違いに下) - 制約: トランザクションは小さく高速でなければならない。データセットは主記憶に収まる必要がある (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Actual Serial Execution", "Encapsulating transactions in stored procedures", "Sharding", "Summary of serial execution") ## 2相ロック(2PL、Two-Phase Locking) 約 30 年間、直列化可能性を実現する唯一の実用的手法だった。read committed のロックより強力で、読み取りが共有(shared)ロック、書き込みが排他(exclusive)ロックを要求し、書き込みは読み取りをブロックし、読み取りも書き込みをブロックする(スナップショット分離の「readers never block writers」とは対照的)。 - **成長フェーズと収縮フェーズ**: トランザクション実行中にロックを取得し続け(growing)、コミット/中断時にすべて解放する(shrinking)。この 2 段階構造が名前の由来 - **述語ロック(predicate lock)**: 特定の行ではなく検索条件にマッチする**すべての**オブジェクト(未挿入のものを含む)に対するロック。ファントムを防ぐために理論上必要だが性能が悪い - **インデックスレンジロック(index-range lock、next-key locking)**: 述語ロックを近似する実用的な実装。インデックスエントリやインデックス範囲に共有ロックを付け、対象がなければテーブル全体にフォールバックする - **性能問題**: ロック取得・解放のオーバーヘッドに加え、並行性の低下(競合しうる操作は必ず片方が待つ)により、高パーセンタイルレイテンシが不安定になりやすい。read committed よりデッドロックが頻発する > [!note] 2PL(2相ロック)と 2PC(2相コミット)は名前が似ているだけで無関係の概念。2PL は分離性、2PC は分散環境での原子コミット(→ [[分散トランザクション]])を扱う。 (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Two-Phase Locking", "2PL is not 2PC", "Implementation of 2PL", "Performance of 2PL", "Predicate locks", "Index-range locks") ## 直列化可能スナップショット分離(SSI、Serializable Snapshot Isolation) 2008 年に発表された比較的新しいアルゴリズムで、スナップショット分離とほぼ変わらない性能コストで完全な直列化可能性を提供する。PostgreSQL の serializable レベル、SQL Server の Hekaton、HyPer(単一ノード)、CockroachDB・FoundationDB(分散)、BadgerDB(組み込み)などで採用される。 - **楽観的並行性制御**: 2PL や実際の直列実行が「悲観的」(何か問題が起きる可能性があればブロックする)であるのに対し、SSI は「楽観的」(トランザクションをまず進め、コミット時に直列化可能性が破られていないか検査し、破られていれば中断・リトライする) - **陳腐化した前提(outdated premise)の検出**: (1) 陳腐化した MVCC 読み取りの検出(コミット時に、可視性ルールで無視した書き込みが後にコミットされていないか確認)と、(2) 事前の読み取りに影響する書き込みの検出(インデックスレンジロックに似た仕組みで、後続の書き込みが以前の読み取りに影響したかを記録し、tripwire として通知する)の 2 経路がある - **性能特性**: 2PL と異なりロック待ちが発生しない(readers never block writers はスナップショット分離と同じ)。実際の直列実行と異なり複数マシンに分散できる(FoundationDB は検出処理自体を複数ノードに分散する)。コンテンションが高いと中断率が上がるため、読み書きトランザクションは短く保つ必要がある(長時間の読み取り専用トランザクションは問題ない) (Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Serializable Snapshot Isolation", "Pessimistic versus optimistic concurrency control", "Decisions based on an outdated premise", "Detection of stale MVCC reads", "Detection of writes that affect prior reads", "Performance of serializable snapshot isolation") ## 横断的知見 - **2つの独立教科書が「2PL と 2PC は名前が似ているだけの無関係な概念」という同じ注意書きを独立に挿入している**: DDIA は "2PL is not 2PC" という節を設けて両者の混同に注意を促す。詳説 データベース5章§5.3.8も "二相ロックは、ツーフェーズコミット(13章)と名前が似ていますが、両者はまったく異なる概念です。ツーフェーズコミットは、分散したマルチパーティションでのトランザクションに使用されるプロトコルであるのに対して、二相ロックは、直列化可能性の実装に使用されることの多い同時実行制御の仕組みです" と、ほぼ同一の注意書きを独立に挿入している。2つの独立した教科書が同じ誤解ポイントに同じ形で言及していることは、この命名混同が読者に広く共有される陥りやすい誤りであることを裏付ける。(Source: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "2PL is not 2PC", [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.3.8) - **詳説 データベースの楽観的同時実行制御(OCC)の3フェーズモデルは、DDIA の SSI 説明の一般化された祖先にあたる**: 詳説 データベース5章§5.3.5は OCC を「読み取りフェーズ(プライベートコンテキストで実行)→検証フェーズ(読み取り/書き込みセットの競合検査、既にコミット済みのトランザクションとの競合を見る後方指向、現在検証中のトランザクションとの競合を見る前方指向の2方式)→書き込みフェーズ(競合なしなら反映)」の3段階として定義する。DDIA が説明する SSI の「陳腐化した MVCC 読み取りの検出」はこの後方指向検証の具体化、「事前の読み取りに影響する書き込みの検出」は前方指向検証の具体化に相当し、SSI は詳説 データベースが示す一般的な OCC の枠組みに MVCC ベースの可視性ルールを組み込んだ特殊化として位置づけ直せる。この対応関係は DDIA 単独でも詳説 データベース単独でも明示されておらず、両方を突き合わせて初めて見える構造である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.3.5, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Serializable Snapshot Isolation") - **詳説 データベースはデッドロック対処(waits-forグラフ、Wait-die/Wound-wait)を独立した節として持つが、DDIA の直列化可能性の章にはこれに対応する記述がない**: 2PL 実装時の中核的な運用上の課題であるデッドロックの検出・回避について、詳説 データベース5章§5.3.8.1はwaits-forグラフによる循環検出と、タイムスタンプ優先順位に基づくWait-die/Wound-wait方式(RAMAKRISHNAN03)を具体的に説明する。DDIA の "Two-Phase Locking" 節はロック取得・解放のオーバーヘッドや高パーセンタイルレイテンシの不安定さには触れるが、デッドロックの具体的な検出・回避アルゴリズムには踏み込まない。これは2つの教科書の対象範囲の違い(詳説 データベースは実装寄り、DDIA は分離性の意味論寄り)を示す非対称なカバレッジであり、2PL の完全な理解にはデッドロック対処の節を持つ詳説 データベース側の記述が不可欠である。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] §5.3.8.1, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Performance of 2PL") - [[OLTPシステムアーキテクチャ]] は Shore の測定でロック・ラッチの命令数コストを定量化しており、2PL の性能問題を別角度から裏付ける関係にあるが、まだ明示的な突き合わせは行っていない。 - **直列化可能性(トランザクションの順序)と線形化可能性(単一オブジェクトの実時間順序)は、しばしば同じ「一貫性」という語で語られるが本質的に異なる保証である**: 直列化可能性は「並行実行されたトランザクション群の結果が、何らかの直列実行(一度に1つずつ)と同じになる」ことだけを保証し、その直列順序がウォールクロック上のどの順序であるべきかには関与しない(実行順序と因果的に矛盾しない任意の順序でよい)。一方、詳説 データベース11章が定義する線形化可能性は、単一オブジェクトに対する個々の読み書き操作が「その開始と終了の間のある時点で正確に一度にすべての読み手から見える」ことを要求し、操作の実時間順序(ウォールクロック順)を直接の対象とする。両者は独立した軸であり、直列化可能だが線形化可能でない実行(トランザクションの順序は一貫しているが、その順序が実時間と食い違う)も、逆に線形化可能だが直列化可能でない実行(個々の単一オブジェクト操作は実時間順序を守るが、複数オブジェクトにまたがるトランザクションとしては一貫した直列順序に整理できない)も理論上ありうる。この2つを両方満たす保証が[[外部一貫性]]ページで扱う「厳密直列化可能性(strict serializability)」であり、Spannerのcommit waitはこれを実現するための具体的なコストである。(Source: [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.5.2, [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] "Serializability") ## 未解決の問い - SSI の中断率とコンテンションの関係は、[[OLTPシステムアーキテクチャ]] が測定した従来型ロックマネージャの命令数コストと比べて、実運用ワークロードでどちらが総合的に有利か、定量比較は存在するか。 - CockroachDB・FoundationDB のような分散 SSI 実装は、単一ノード SSI(PostgreSQL)と比べて検出処理の分散化にどのような追加コストを払っているか。→ [[分散トランザクション]] の 2PC 議論との接続。 - 実際の直列実行(VoltDB 系)とストアドプロシージャ必須という制約は、モダンなアプリケーション開発フロー(マイクロサービス・ORM 主体の開発)とどこまで両立するか。 - 詳説 データベースが示す OCC 3フェーズモデルと DDIA の SSI 説明の対応関係(本節参照)を前提にすると、SSI 以外の MVCC ベース OCC 実装(タイムスタンプ順序付けベースなど)は、後方指向・前方指向検証のどちらに寄っているか、実装事例を収集して整理する余地がある。 - 詳説 データベースの Wait-die/Wound-wait のようなデッドロック回避アルゴリズムを、DDIA が扱う SSI ベースの直列化可能性システムと組み合わせた場合(SSI はロックを使わないため一見無関係だが、SSI 内部の tripwire 機構が同種の優先順位づけを必要とするか)、両者は接続できるか。 ## 関連 - ソース: [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]] / [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] - 概念: [[ACIDと分離レベル]] / [[スナップショット分離とMVCC]] / [[ロストアップデートと書き込みスキュー]] / [[分散トランザクション]] / [[OLTPシステムアーキテクチャ]] / [[線形化可能性]] / [[外部一貫性]] - 実体: [[VoltDB]] / [[CockroachDB]] / [[PostgreSQL]] ## 出典 - [[@2026__OReilly__Designing Data-Intensive Applications 2E - Chapter 8 Transactions]]("Serializability", "Actual Serial Execution", "Two-Phase Locking", "Serializable Snapshot Isolation") - [[@2021__OReillyJapan__詳説 データベース - Chapter 5 トランザクション処理とリカバリ]](§5.3.1 直列化可能性、§5.3.5 楽観的同時実行制御、§5.3.8 2PLとデッドロック対処) - [[@2021__OReillyJapan__詳説 データベース - Chapter 11 レプリケーションと一貫性]] §11.5.2 線形化可能性(直列化可能性との対比)