CAP定理入門 - 分散システムの一貫性・可用性・分断耐性

CAP定理（Brewer’s Theorem）は、分散システムが備えるべき3つの性質「一貫性（Consistency）」「可用性（Availability）」「分断耐性（Partition Tolerance）」のうち、同時に満たせるのは最大2つまでであるという原則です。本記事では、CAP定理の正確な意味から、現実のシステム設計で使うPACELC、実際のデータベース選定までを体系的に解説します。

概要

CAP定理とは

2000年にEric BrewerがPODCで発表し、2002年にGilbert-Lynchによって形式的に証明された定理です。分散データストアにおいて、ネットワーク分断が発生した際に、整合性と可用性のどちらかを犠牲にせざるを得ないことを示しています。

flowchart TB
    subgraph CAP["CAP定理"]
        C["Consistency<br/>(一貫性)"]
        A["Availability<br/>(可用性)"]
        P["Partition Tolerance<br/>(分断耐性)"]
    end

    CP["CP型<br/>HBase / etcd<br/>ZooKeeper / MongoDB"]
    AP["AP型<br/>Cassandra / DynamoDB<br/>Riak / CouchDB"]
    CA["CA型<br/>(単一ノードDB)<br/>分散では実現不可"]

    C --- CP --- P
    A --- AP --- P
    C --- CA --- A

よくある誤解

CAP定理は「3つのうち2つを選ぶ」と単純化されがちですが、正しくは「ネットワーク分断が起きた時（Pが発生した時）、CとAのどちらを優先するか」です。分断が起きていない通常時は、CもAも両立できます。

原則・定義

3つの性質の定義

Consistency（一貫性）

すべてのノードが同時に同じデータを見ること。正確には「線形化可能性（Linearizability）」を指します。書き込みが完了したら、以降のどのノードからの読み取りも新しい値を返します。

// 線形化可能な動作
await db.write("x", 10);        // Node1 で書き込み
const value = await db.read("x"); // Node2 から読んでも必ず10

Availability（可用性）

故障していない全ノードが全てのリクエストに対して、エラーでない応答を返すこと。ただしそのレスポンスが最新である保証はありません。

Partition Tolerance（分断耐性）

ノード間のネットワークが任意のメッセージを失っても、システムが動作し続けること。現実の分散システムでは必須であり、事実上「P」は常に選択されます。

CAP選択のフロー

flowchart LR
    Start["分散システム設計"]
    Partition{"ネットワーク分断<br/>発生?"}
    Normal["通常運用<br/>C も A も実現"]
    Choice{"何を優先?"}
    CP_Path["CPを選択<br/>応答を停止して<br/>整合性を守る"]
    AP_Path["APを選択<br/>古い可能性のある<br/>データを返す"]

    Start --> Partition
    Partition -->|No| Normal
    Partition -->|Yes| Choice
    Choice -->|整合性| CP_Path
    Choice -->|可用性| AP_Path

構成要素

PACELC による拡張

Daniel Abadi が2012年に提唱した拡張定理で、CAP の欠点を補います。

If there is a Partition, choose between Availability and Consistency; Else (normal operation), choose between Latency and Consistency.

flowchart TB
    System["分散システム"]
    P{"Partition<br/>発生?"}
    PA["PA: 可用性優先"]
    PC["PC: 整合性優先"]
    EL["EL: 低レイテンシ優先"]
    EC["EC: 整合性優先"]

    System --> P
    P -->|Yes| PA
    P -->|Yes| PC
    P -->|No| EL
    P -->|No| EC

一貫性レベルのスペクトル

flowchart LR
    Strong["Linearizable<br/>(線形化可能)"]
    Sequential["Sequential<br/>(逐次一貫性)"]
    Causal["Causal<br/>(因果一貫性)"]
    ReadYour["Read Your<br/>Writes"]
    Eventual["Eventual<br/>(結果整合性)"]

    Strong --> Sequential --> Causal --> ReadYour --> Eventual

    style Strong fill:#fee
    style Eventual fill:#efe

強い順に: Linearizable > Sequential > Causal > Read-Your-Writes > Eventual

実装例

1. Quorum ベースの一貫性制御（Cassandra 風）

interface QuorumConfig {
  replicationFactor: number; // N: レプリカ数
  writeQuorum: number;       // W: 書き込み確認数
  readQuorum: number;        // R: 読み取り確認数
}

// 強整合性: W + R > N
const strongConsistency: QuorumConfig = {
  replicationFactor: 3,
  writeQuorum: 2,  // QUORUM
  readQuorum: 2,   // QUORUM
};

// 高可用性（結果整合性）: W + R <= N
const highAvailability: QuorumConfig = {
  replicationFactor: 3,
  writeQuorum: 1,  // ONE
  readQuorum: 1,   // ONE
};

class QuorumStore {
  constructor(
    private nodes: ReplicaNode[],
    private config: QuorumConfig,
  ) {}

  async write(key: string, value: string): Promise<void> {
    const timestamp = Date.now();
    const results = await Promise.allSettled(
      this.nodes.map((n) => n.write(key, value, timestamp)),
    );
    const ok = results.filter((r) => r.status === "fulfilled").length;
    if (ok < this.config.writeQuorum) {
      throw new Error(`Write quorum not met: ${ok}/${this.config.writeQuorum}`);
    }
  }

  async read(key: string): Promise<string | null> {
    const results = await Promise.allSettled(
      this.nodes.map((n) => n.read(key)),
    );
    const successful = results
      .filter((r): r is PromiseFulfilledResult<VersionedValue> => r.status === "fulfilled")
      .map((r) => r.value);

    if (successful.length < this.config.readQuorum) {
      throw new Error("Read quorum not met");
    }

    // Last-Write-Wins による競合解決
    return successful.reduce((latest, curr) =>
      curr.timestamp > latest.timestamp ? curr : latest,
    ).value;
  }
}

interface VersionedValue {
  value: string;
  timestamp: number;
}
interface ReplicaNode {
  write(k: string, v: string, ts: number): Promise<void>;
  read(k: string): Promise<VersionedValue>;
}

2. CRDTs による AP 型設計

// G-Counter: Grow-only counter (CRDT)
class GCounter {
  private counts: Map<string, number> = new Map();

  constructor(private readonly nodeId: string) {
    this.counts.set(nodeId, 0);
  }

  increment(): void {
    this.counts.set(this.nodeId, (this.counts.get(this.nodeId) ?? 0) + 1);
  }

  value(): number {
    return Array.from(this.counts.values()).reduce((a, b) => a + b, 0);
  }

  // 任意の順序でマージ可能（可換・結合的・冪等）
  merge(other: GCounter): void {
    for (const [nodeId, count] of other.counts) {
      const existing = this.counts.get(nodeId) ?? 0;
      this.counts.set(nodeId, Math.max(existing, count));
    }
  }
}

3. Two-Phase Commit（CP 型の典型）

class TwoPhaseCoordinator {
  async commit(participants: Participant[], tx: Transaction): Promise<boolean> {
    // Phase 1: Prepare
    const votes = await Promise.all(
      participants.map((p) => p.prepare(tx).catch(() => "NO" as const)),
    );

    if (votes.some((v) => v === "NO")) {
      await Promise.all(participants.map((p) => p.abort(tx)));
      return false;
    }

    // Phase 2: Commit
    await Promise.all(participants.map((p) => p.commit(tx)));
    return true;
  }
}

interface Participant {
  prepare(tx: Transaction): Promise<"YES" | "NO">;
  commit(tx: Transaction): Promise<void>;
  abort(tx: Transaction): Promise<void>;
}
interface Transaction {
  id: string;
}

2PC は整合性を保証しますが、コーディネータ障害時にブロックされるため、可用性は犠牲になります（典型的なCP）。

メリット・デメリット

CP型システムのメリット

1. データ整合性の保証: 常に最新の値が読める
2. 推論しやすい: アプリケーションロジックが単純
3. 金融・在庫等に適合: 正確性が不可欠な領域

CP型システムのデメリット

1. ダウンタイム発生: 分断時に応答不能
2. レイテンシ増: Quorum待ちでレスポンスが遅い
3. 可用性SLA: 99.99%達成が困難

AP型システムのメリット

1. 高可用性: 分断・故障に強い
2. 低レイテンシ: 最寄りのノードから即応答
3. 水平スケール: ノード追加が容易

AP型システムのデメリット

1. 古いデータ: 一時的に stale な値を返す
2. 競合解決が複雑: アプリ側で解決ロジックが必要
3. バグの温床: Read-Your-Writes が壊れるなど直感に反する挙動

ユースケース

CP型が適する

• 銀行口座残高、在庫管理
• ロック・リーダー選出（ZooKeeper, etcd）
• 設定管理・サービスディスカバリ
• 一意なIDの発行

AP型が適する

• ショッピングカート（Amazon Dynamo の原典）
• SNSのタイムライン、いいね数
• センサーデータ、ログ収集
• グローバル配信のCDNメタデータ

落とし穴

1. 「CA型」は分散システムでは存在しない

単一ノードのRDBMSを「CA」と呼ぶ人もいますが、それは分散ではありません。現実の分散システムでは、ネットワーク分断は必ず起きるため、Pを捨てる選択肢はありません。

2. MongoDB = CP? AP?

MongoDB は設定次第で挙動が変わります。writeConcern と readPreference の組み合わせで CP 寄りにも AP 寄りにもなります。「DB名で分類する」のではなく「設定で確認する」ことが重要です。

3. NewSQL の誤解

Google Spanner や CockroachDB は「CP かつ高可用性」と謳われますが、CAP 定理に反するわけではありません。TrueTime や原子時計により、分断の影響を極小化しつつ、厳密には分断時に一方を犠牲にしています。

4. 結果整合性を甘く見る

「最終的に一致する」という言葉から安心しがちですが、「何秒後に一致するか」「競合がどう解決されるか」を設計しないとバグります。

5. レプリケーションラグ

非同期レプリケーションでは、プライマリ書き込み直後にレプリカから読むと古い値が返ります。Read-Your-Writes が必要な画面では、プライマリから読むか、セッション一貫性を使います。

比較表

主要データベースの CAP/PACELC 分類

ベストプラクティス

1. ユースケース別に選ぶ: 1つのDBで全てをまかなわない（Polyglot Persistence）
2. 一貫性レベルを明示: Quorum 設定を意識的に選ぶ
3. 分断時の挙動を定義: SLA とフォールバック戦略を事前決定
4. 競合解決戦略: LWW / Vector Clock / CRDT / アプリロジック
5. 監視: レプリケーションラグ、Quorum 失敗率
6. カオステスト: 分断注入で挙動を検証（Jepsen テスト）
7. 読み書きパスの分離: CQRS で読み取り側だけ AP に寄せる
8. PACELC で議論: CAP より実用的な観点

まとめ

CAP定理は分散システム設計の出発点ですが、実際には PACELC や一貫性スペクトルを使って、より細かくトレードオフを検討します。

• CAP: 分断時にCとAのどちらを選ぶか
• PACELC: 通常時のレイテンシと一貫性のトレードオフも考える
• 選択: ビジネス要件（正確性 vs 可用性）で決まる
• 併用: 複数DBを使い分ける Polyglot Persistence が実用解
• 検証: Jepsen などで実装の正しさを確認

「全てを満たす魔法のDB」は存在しません。要件から逆算して選びましょう。

応用トピック

Read-Your-Writes 一貫性の実装

ユーザーが自分の書き込みを直後に読んだ際、必ず最新データが見えるべきです。非同期レプリケーションではこれが壊れがちなので、以下の対策を取ります。

class ReadYourWritesRouter {
  private recentWrites = new Map<string, number>(); // userId -> timestamp

  recordWrite(userId: string): void {
    this.recentWrites.set(userId, Date.now());
  }

  selectReplica(userId: string): "primary" | "replica" {
    const ts = this.recentWrites.get(userId);
    if (!ts) return "replica";
    // 最近5秒以内に書き込んだユーザーはプライマリから読む
    if (Date.now() - ts < 5000) return "primary";
    return "replica";
  }
}

Monotonic Read 一貫性

「一度新しい値を読んだら、二度と古い値に戻らない」保証です。ユーザーを同じレプリカにスティッキーに固定することで実現します。

因果一貫性（Causal Consistency）

因果関係のある操作の順序だけを保証する、線形化可能性よりも弱く、結果整合性より強い中間の一貫性です。Vector Clock や HLC（Hybrid Logical Clock）で実装します。

class VectorClock {
  private clock: Record<string, number> = {};

  constructor(private readonly nodeId: string) {
    this.clock[nodeId] = 0;
  }

  tick(): void {
    this.clock[this.nodeId] = (this.clock[this.nodeId] ?? 0) + 1;
  }

  merge(other: VectorClock): void {
    for (const [id, count] of Object.entries(other.clock)) {
      this.clock[id] = Math.max(this.clock[id] ?? 0, count);
    }
    this.tick();
  }

  happenedBefore(other: VectorClock): boolean {
    let strictlyLess = false;
    for (const id of new Set([...Object.keys(this.clock), ...Object.keys(other.clock)])) {
      const a = this.clock[id] ?? 0;
      const b = other.clock[id] ?? 0;
      if (a > b) return false;
      if (a < b) strictlyLess = true;
    }
    return strictlyLess;
  }
}

Jepsen テストによる検証

Kyle Kingsbury による Jepsen は、分散システムに対して実際にネットワーク分断やノード障害を注入し、一貫性違反を検出するテストフレームワークです。多くの有名DBが Jepsen テストで既知の問題を発見しており、自称する CAP 特性を実証的に検証する業界標準となっています。

Polyglot Persistence の実例

E-commerce システムの典型例:

参考リソース

• Brewer’s CAP Theorem - Julian Browne
• Gilbert & Lynch - Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (PDF)
• Daniel Abadi - Problems with CAP, and Yahoo’s little known NoSQL system
• Martin Kleppmann - Please stop calling databases CP or AP
• Jepsen - Distributed Systems Safety Research
• Amazon DynamoDB Paper (2007)
• Designing Data-Intensive Applications - Martin Kleppmann