MVCC - 多版同時実行制御とスナップショット分離

MVCC（Multi-Version Concurrency Control、多版同時実行制御）は、データベースにおいて複数のトランザクションが同時にデータにアクセスする際、各トランザクションに異なるバージョンのデータを提供することで、ロック競合を最小化する技術です。本記事では、MVCC の原理、分離レベル、実装例、デッドロック対策を体系的に解説します。

概要

MVCC とは

従来のロックベースの並行制御では、読み取り操作と書き込み操作が互いにブロックし合いますが、MVCC では読み取り操作が書き込みをブロックせず、書き込みも読み取りをブロックしません。

sequenceDiagram
    participant T1 as Transaction 1<br/>(READ)
    participant T2 as Transaction 2<br/>(WRITE)
    participant DB as Database<br/>(MVCC)

    T1->>DB: BEGIN (snapshot at t=10)
    T2->>DB: BEGIN
    T2->>DB: UPDATE users SET balance=1000 WHERE id=1
    T2->>DB: COMMIT (new version at t=11)

    Note over T1,DB: T1 は依然として t=10 のスナップショットを見る

    T1->>DB: SELECT balance FROM users WHERE id=1
    DB-->>T1: balance=500 (古いバージョン)

    T1->>DB: COMMIT

ロックベース vs MVCC

原則・定義

バージョン管理の仕組み

MVCC では、各行に複数のバージョンを保持します。各バージョンには以下の情報が付与されます。

スナップショット分離（Snapshot Isolation）

トランザクション開始時（または最初の SELECT 時）に、その時点でコミット済みのデータだけが見えます。他のトランザクションの変更は見えません。

分離レベルとの関係

構成要素

PostgreSQL の MVCC 実装

PostgreSQL では、各行（tuple）に以下のメタデータを持ちます。

// 簡略化した PostgreSQL のタプルヘッダ
struct HeapTupleHeader {
  TransactionId xmin; // この行を作成したトランザクションID
  TransactionId xmax; // この行を削除したトランザクションID（0なら有効）
  CommandId cmin;     // トランザクション内のコマンド番号
  CommandId cmax;
  // ... 他のメタデータ
};

Visibility Rules（可視性ルール）

トランザクション T が行を読む際、以下のルールで可視性を判定します。

1. xmin がコミット済みで、T より前 → 可視
2. xmax が未コミットまたは T より後 → 可視
3. それ以外 → 不可視

MySQL InnoDB の MVCC 実装

InnoDB は UNDO ログを使ってバージョンを管理します。

flowchart LR
    CurrentRow["現在の行<br/>(id=1, balance=1000, xid=123)"]
    UndoLog1["UNDO Log 1<br/>(balance=500, xid=100)"]
    UndoLog2["UNDO Log 2<br/>(balance=300, xid=80)"]

    CurrentRow -.rollback pointer.-> UndoLog1
    UndoLog1 -.rollback pointer.-> UndoLog2

古いトランザクションは UNDO ログを遡って、自分が見るべきバージョンを再構築します。

実装例

1. 簡易 MVCC エンジン（TypeScript）

interface Version {
  value: any;
  xmin: number; // 作成トランザクションID
  xmax: number; // 削除トランザクションID（0なら有効）
}

class MVCCStore {
  private data = new Map<string, Version[]>(); // key -> versions
  private currentXID = 0;
  private committedXIDs = new Set<number>();

  beginTransaction(): number {
    return ++this.currentXID;
  }

  commit(xid: number): void {
    this.committedXIDs.add(xid);
  }

  abort(xid: number): void {
    // トランザクションの変更を破棄（ガベージコレクションで削除）
  }

  write(key: string, value: any, xid: number): void {
    const versions = this.data.get(key) ?? [];

    // 既存の最新バージョンを論理削除
    const latest = versions.find((v) => v.xmax === 0);
    if (latest) {
      latest.xmax = xid;
    }

    // 新バージョンを追加
    versions.push({ value, xmin: xid, xmax: 0 });
    this.data.set(key, versions);
  }

  read(key: string, xid: number): any | undefined {
    const versions = this.data.get(key) ?? [];

    // 可視なバージョンを探す
    for (const v of versions.slice().reverse()) {
      if (this.isVisible(v, xid)) {
        return v.value;
      }
    }

    return undefined; // 見えるバージョンがない
  }

  private isVisible(version: Version, currentXID: number): boolean {
    // xmin がコミット済みで currentXID より前
    if (!this.committedXIDs.has(version.xmin) || version.xmin > currentXID) {
      return false;
    }

    // xmax が未設定、または未コミット、または currentXID より後
    if (version.xmax === 0) return true;
    if (!this.committedXIDs.has(version.xmax) || version.xmax > currentXID) {
      return true;
    }

    return false;
  }

  // ガベージコレクション: 全トランザクションから見えない古いバージョンを削除
  vacuum(): void {
    const minActiveXID = Math.min(...Array.from(this.committedXIDs));

    for (const [key, versions] of this.data) {
      const alive = versions.filter((v) => {
        // xmax が設定されていて、全てのアクティブトランザクションより前なら削除可能
        return v.xmax === 0 || v.xmax >= minActiveXID;
      });
      this.data.set(key, alive);
    }
  }
}

// 使用例
const store = new MVCCStore();

// トランザクション1: 書き込み
const t1 = store.beginTransaction();
store.write("user:1", { name: "Alice", balance: 500 }, t1);
store.commit(t1);

// トランザクション2: 読み取り開始
const t2 = store.beginTransaction();
console.log(store.read("user:1", t2)); // { name: 'Alice', balance: 500 }

// トランザクション3: 更新
const t3 = store.beginTransaction();
store.write("user:1", { name: "Alice", balance: 1000 }, t3);
store.commit(t3);

// トランザクション2 は依然として古いバージョンを見る
console.log(store.read("user:1", t2)); // { name: 'Alice', balance: 500 }
store.commit(t2);

// 新しいトランザクションは新バージョンを見る
const t4 = store.beginTransaction();
console.log(store.read("user:1", t4)); // { name: 'Alice', balance: 1000 }

2. PostgreSQL でのスナップショット分離

-- デフォルトは Read Committed（各ステートメントごとに新スナップショット）
BEGIN;
SELECT balance FROM users WHERE id = 1; -- 500

-- 別のトランザクションが更新
-- UPDATE users SET balance = 1000 WHERE id = 1; COMMIT;

SELECT balance FROM users WHERE id = 1; -- 1000 (新スナップショット)
COMMIT;

-- Repeatable Read（トランザクション開始時のスナップショット）
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT balance FROM users WHERE id = 1; -- 500

-- 別のトランザクションが更新してもスナップショットは変わらない
SELECT balance FROM users WHERE id = 1; -- 500 (同じスナップショット)
COMMIT;

3. MySQL InnoDB の MVCC 設定

-- デフォルトは Repeatable Read
SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;

BEGIN;
SELECT * FROM users WHERE id = 1; -- スナップショット確定

-- 別のトランザクションが更新
-- UPDATE users SET balance = 1000 WHERE id = 1; COMMIT;

SELECT * FROM users WHERE id = 1; -- 依然として古いバージョン
COMMIT;

-- Read Committed に変更
SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;

メリット・デメリット

メリット

1. 高い並行性: 読み取りが書き込みをブロックしない
2. デッドロック減少: 読み取りロックが不要
3. 一貫性のある読み取り: スナップショット分離で整合性を保証
4. Read-only クエリの高速化: ロック待ちなし

デメリット

1. ストレージ増加: 古いバージョンを保持するため容量が必要
2. VACUUM 必要: 古いバージョンの削除処理が必要（PostgreSQL）
3. Write Skew: Serializable でないと検出できない異常
4. 複雑性: 実装が複雑でデバッグが困難

ユースケース

1. 長時間実行される分析クエリ

OLAP（分析系）クエリは数分〜数時間かかりますが、MVCC により、他のトランザクションの更新をブロックしません。

-- 分析クエリ（30分かかる）
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT AVG(order_amount) FROM orders WHERE created_at > '2025-01-01';
-- ... 複雑な集計 ...
COMMIT;

-- 同時に OLTP クエリも実行可能
INSERT INTO orders (user_id, amount) VALUES (123, 5000); -- ブロックされない

2. 読み取り専用レプリカ

レプリカサーバーは MVCC により、プライマリの更新を受信しながら、読み取りクエリを並行実行できます。

3. Web アプリケーションのトランザクション

ユーザーのリクエストごとにトランザクションを開始し、他ユーザーの更新に影響されずに処理できます。

落とし穴

1. Write Skew（書き込みスキュー）

-- 残高の合計が 1000 以上を保つ制約があるとする
-- Account A: 600, Account B: 500

-- Transaction 1
BEGIN;
SELECT SUM(balance) FROM accounts; -- 1100
UPDATE accounts SET balance = 100 WHERE id = 'A'; -- 残りは 600 あるので OK と判断
COMMIT;

-- Transaction 2（同時実行）
BEGIN;
SELECT SUM(balance) FROM accounts; -- 1100
UPDATE accounts SET balance = 100 WHERE id = 'B'; -- 残りは 600 あるので OK と判断
COMMIT;

-- 結果: A=100, B=100 → 合計 200（制約違反!）

解決策: SERIALIZABLE または SELECT FOR UPDATE を使う。

2. Lost Update（更新の紛失）

Read Committed では、Read-Modify-Write パターンで更新が失われます。

-- Transaction 1
BEGIN;
SELECT balance FROM users WHERE id = 1; -- 500
-- balance に 100 を加算
UPDATE users SET balance = 600 WHERE id = 1;
COMMIT;

-- Transaction 2（同時実行）
BEGIN;
SELECT balance FROM users WHERE id = 1; -- 500（T1の更新前）
-- balance に 200 を加算
UPDATE users SET balance = 700 WHERE id = 1; -- T1の更新が失われる!
COMMIT;

-- 正しい結果は 800 だが、実際は 700

解決策: SELECT FOR UPDATE または UPDATE ... RETURNING を使う。

3. VACUUM の遅れ（PostgreSQL）

VACUUM が実行されないと、古いバージョンが蓄積してテーブルが肥大化します。

-- VACUUM の手動実行
VACUUM users;

-- ANALYZE も同時実行
VACUUM ANALYZE users;

-- Autovacuum の設定確認
SHOW autovacuum;

4. トランザクションID の枯渇（PostgreSQL）

PostgreSQL は32bit のトランザクションID を使うため、約20億トランザクションで wraparound が発生します。定期的な VACUUM が必須です。

5. Phantom Read（ファントムリード）

Repeatable Read でも、新しい行の挿入は見えてしまいます（DB によって挙動が異なる）。

-- Transaction 1
BEGIN TRANSACTION ISOLATION LEVEL REPEATABLE READ;
SELECT COUNT(*) FROM users WHERE age > 30; -- 100

-- Transaction 2
INSERT INTO users (name, age) VALUES ('Bob', 35);
COMMIT;

-- Transaction 1
SELECT COUNT(*) FROM users WHERE age > 30; -- 101（ファントムリード）
COMMIT;

PostgreSQL の Repeatable Read では Phantom Read も防がれますが、MySQL InnoDB では発生します。

比較表

主要 RDBMS の MVCC 実装

分離レベルと異常

ベストプラクティス

1. 分離レベルを適切に選択: デフォルトのまま使わず、要件に応じて設定
2. SELECT FOR UPDATE: 更新を伴う読み取りにはロックを取得
3. VACUUM の監視: PostgreSQL では Autovacuum の動作を確認
4. 長時間トランザクション回避: MVCC でも古いバージョンが残り続ける
5. Write Skew 対策: SERIALIZABLE または明示的ロック
6. Read-Modify-Write はアトミックに: UPDATE ... WHERE で条件付き更新
7. 分離レベルのテスト: 並行実行テストで異常を検出
8. 監視: トランザクション数、VACUUM 頻度、テーブル肥大化を監視

まとめ

MVCC は、データベースの並行性を劇的に向上させる技術です。

• 原理: 各トランザクションに異なるバージョンのデータを提供
• 利点: 読み書きのロック競合を回避、高い並行性
• スナップショット分離: 一貫性のある読み取りを保証
• 実装: PostgreSQL（Tuple）、InnoDB（UNDO）、Oracle（Tablespace）
• 注意: Write Skew、VACUUM、トランザクションID 枯渇

MVCC を理解することで、データベースのパフォーマンスと一貫性を適切にバランスできます。

応用トピック

Serializable Snapshot Isolation（SSI）

PostgreSQL の SERIALIZABLE は、スナップショット分離に Serialization Conflict Detection を追加し、Write Skew を検出します。

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- Write Skew が発生しそうな場合、エラーで中断
-- ERROR: could not serialize access due to read/write dependencies among transactions

Hybrid Logical Clocks（HLC）

CockroachDB や Spanner は、物理時刻と論理時刻を組み合わせた HLC で、グローバルな順序付けを実現します。

Optimistic Concurrency Control（楽観的並行制御）

アプリケーション層で MVCC を実装する手法で、バージョン番号を使って競合を検出します。

interface User {
  id: number;
  name: string;
  balance: number;
  version: number; // バージョン番号
}

async function updateBalance(userId: number, amount: number) {
  const user = await db.query("SELECT * FROM users WHERE id = $1", [userId]);

  // 残高を更新
  const newBalance = user.balance + amount;

  // バージョンが変わっていないことを確認して更新
  const result = await db.query(
    "UPDATE users SET balance = $1, version = version + 1 WHERE id = $2 AND version = $3",
    [newBalance, userId, user.version],
  );

  if (result.rowCount === 0) {
    throw new Error("Concurrent modification detected");
  }
}

MVCC in Distributed Systems

分散データベース（Spanner、CockroachDB）は、MVCC にタイムスタンプを組み合わせ、グローバルな一貫性を実現します。

参考リソース

• PostgreSQL Documentation - MVCC
• MySQL InnoDB - Multi-Versioning
• A Critique of ANSI SQL Isolation Levels - Microsoft Research
• Serializable Snapshot Isolation in PostgreSQL
• Designing Data-Intensive Applications - Chapter 7

関連記事

• データベーストランザクション - ACID 特性と分離レベルの詳細
• データベースインデックス最適化 - MVCC と組み合わせたクエリ最適化