Quartz 5

データベースとトランザクション理論

Properties1
tagsdatabase, transaction, acid, cap, concurrency, distributed-systems

4 min read

データベースとトランザクション理論

RDB/分散DBの正しさと性能を支える理論群。_moc-web-infra

ACID特性

トランザクションが満たすべき4性質。

  • Atomicity: 全て実行されるか全く実行されないか
  • Consistency: 矛盾(整合性制約違反)が起きない
  • Isolation: 並行実行しても互いに干渉しない
  • Durability: コミット結果は永続的

CAP定理

分散DBでは Consistency(一貫性)・Availability(可用性)・Partition-tolerance(分断耐性)の3つを同時には満たせない。ネットワーク分断が前提なので実質 CP か AP の選択になる。

トランザクション分離レベル

弱い順に異常が起きる。READ UNCOMMITTED < READ COMMITTED(PostgreSQL/Oracleの既定) < REPEATABLE READ(MySQLの既定) < SERIALIZABLE。

  • Dirty Read: 未コミットデータを読む
  • Fuzzy/Non-Repeatable Read: 再読込で値が変わる
  • Phantom Read: 範囲処理中に他txの追加行が見える
    SERIALIZABLE は読む全行に共有ロックをかけるため性能が落ちる。

排他制御

  • 楽観ロック: ロックせず、更新時に値が初回と同じかチェック(version列など)
  • 悲観ロック: SELECT ... FOR UPDATE で先にロック

直列化可能性とSilo

トランザクションスケジュールの正しさは「直列実行と同じ結果(Serializable)」で定義される。判定強度の異なる等価性: Final State < View Equivalence(NP完全) < Conflict Serializability(CSR、高速判定可)。Two Phase Lock は CSR を動的に生成できるがデッドロックが起き、Wait-Die / Wound-Wait / No-Wait で回避する。Optimistic Concurrency Control はコミットまでロックを取らない方式で、Read が多くマルチコアにスケールするため近年の研究で主流。

  • ログ: ディスクのヘッドシークを減らすためトランザクションをログ(undo/redo、冪等)にまとめ、秒間コミット数を稼ぐ。
  • In-Memory DB は Redo ログのみで十分。Bw-Tree/Mass-Tree などマルチコア特化のB+木亜種が研究されている。
  • Silo(SOSP’13): 40msごとにインクリメントするグローバルなエポックを用いてTIDの上位32bitを決め、ログ順序管理のボトルネック(中央集権的increment)を回避。700k tx/s/32core。
  • Google Spanner: 複数DC間複製・SQLライクKVS。TrueTime API で時刻ずれを管理。OSS実装が CockroachDB。

スケーリングと整合性

  • nosql-databases と RDB のトレードオフ
  • シャーディング: 水平分割(行をキーで複数ノードへ分散)
  • レプリケーション: 読み取りスケールのため read replica を増やす。postgresql や Amazon Aurora(最大15 read replica)
  • 結果整合性(Eventual Consistency): スケーラビリティのため一貫性を緩めた整合性モデルの一種。線形化可能性・逐次一貫性・Causal Consistency・Read Your Write など強度の異なるモデルがある。
  • テーブル正規化: 冗長を排し更新異常を防ぐ設計

関連

Graph View

Backlinks