王国のたとえで理解するCAP定理：分散システムの本質的な制約

この記事は、sirius strebe氏による記事 ["CAP Theorem explained with a horse and carriage"](https://www.asksiri.us/blog/2025-02-14.md) を元に、日本語での解説を加えて再構築したものです。

分散システムを設計する際に避けて通れない重要な概念の一つが「CAP定理」です。この定理は時として抽象的に感じられ、完全な理解が難しいものです。本記事では、王国の法律システムというたとえを用いて、CAP定理の本質を分かりやすく解説していきます。

## CAP定理とは

CAP定理は、分散システムにおいて以下の3つの特性を同時に満たすことは不可能であることを示した定理です：

- Consistency（整合性）：すべてのノードが同じデータを見ることができる
- Availability（可用性）：システムが常に利用可能である
- Partition Tolerance（分断耐性）：ネットワークの分断が発生しても動作する

## 王国のたとえで理解する

広大な王国の統治者であるあなたは、法律を通じて国民の秩序を維持しています。すべての市民が法律を知ることができるよう、各都市の広場に法律を刻んだ石板を設置することにしました。読み書きができない市民のために、法律は定期的に読み上げられます。

ところが、新しい法律を制定しようとしたとき、問題が発生します。洪水により、いくつかの都市への道が寸断されてしまったのです。この状況は、分散システムにおけるネットワーク分断と同じような問題を引き起こします。

### 統治者の選択

この状況で、統治者であるあなたには以下の選択肢があります：

1. すべての都市に新しい法律が行き渡るまで、法律の施行を延期する（整合性優先）
2. 到達可能な都市から順次法律を更新し、一時的に法律の内容に地域差が生じることを許容する（可用性優先）

これは分散システムにおけるCAP定理のジレンマを見事に表現しています。

### CAP定理との対応関係

王国のシナリオを分散システムの文脈に置き換えてみましょう：

**Consistency（整合性）：法の統一性**
- すべての都市で同じ法律が参照できる状態を保つ
- 分散システムでは：どのノードにアクセスしても同じデータが得られる

**Availability（可用性）：法の参照可能性**
- 市民がいつでも（たとえ古い版でも）法律を参照できる
- 分散システムでは：システムが常にリクエストに応答できる

**Partition Tolerance（分断耐性）：通信経路の分断への対応**
- 道路の寸断（洪水）が発生しても統治を継続できる
- 分散システムでは：ネットワーク障害が発生しても動作継続できる

## 現代のCAP定理の解釈

現代の分散システムにおいて、Partition Tolerance（分断耐性）は必須の要件として考えられています。王国でも同様です。洪水や自然災害は避けられないものであり、それを前提とした統治システムが必要になります。

したがって、実際の選択は以下の2つに絞られます：

1. CP（整合性＋分断耐性）を選ぶ
   - 法の統一性を重視し、一時的に法の更新を停止する
   - 全都市で同じ法律が参照できることを保証

2. AP（可用性＋分断耐性）を選ぶ
   - 法の参照可能性を重視し、一時的な不一致を許容
   - 各都市が独自に法律を更新可能

## 実際のデータベースシステムでの例：PostgreSQL

この考え方は実際のデータベースシステムでも適用されています。PostgreSQLのレプリケーション方式を例に見てみましょう。

### CPを重視する方式

```sql
-- 二相コミットを使用した強整合性の確保
PREPARE TRANSACTION 'transaction_1';
-- すべてのレプリカで準備が完了したことを確認
COMMIT PREPARED 'transaction_1';
```

1. **Shared Disk Failover**
   - 複数のサーバーで単一のディスクアレイを共有
   - 強い整合性を保証するが、ディスク障害時は全サーバーが停止

2. **File System Replication**
   - ファイルシステムの変更をリアルタイムにミラーリング
   - レプリカの一貫性を完全に保証

### APを重視する方式

```sql
-- 非同期レプリケーションの設定
ALTER SYSTEM SET synchronous_commit TO 'off';
```

1. **Write-Ahead Log Shipping**
   - WALレコードのストリームを使用
   - データの一部損失を許容し、高可用性を実現

2. **Logical Replication**
   - データ修正を非同期で送信
   - コンフリクトの可能性を許容しつつ、高可用性を確保

## システム設計での実践的な判断

CAP定理を理解した上で、システムの要件に応じて適切な設計を選択する必要があります。

### CPを選ぶべき場合

金融取引や在庫管理など、データの一貫性が極めて重要なシステムです：

```python
def transfer_money(from_account, to_account, amount):
    with transaction.atomic():  # 強整合性を保証
        from_account.balance -= amount
        to_account.balance += amount
        # すべてのレプリカで更新が完了するまでコミットしない
```

### APを選ぶべき場合

SNSのタイムラインや分析システムなど、多少の遅延や不整合を許容できるシステムです：

```python
def update_timeline(user_id, post):
    # 非同期でレプリカに反映
    async_replicate(post)
    # 即座にレスポンスを返す
    return {'status': 'accepted'}
```

## まとめ

CAP定理は分散システムにおける基本的な制約を示しています。王国の法律システムのたとえを通じて見たように、これはトレードオフの関係であり、システムの要件に応じて適切な設計選択を行う必要があります。

現代のシステム設計では、ネットワークの分断（＝洪水による道路の寸断）は避けられないものとして考えられています。そのため、実際の設計判断は主にConsistencyとAvailabilityのバランスをどうとるかという点に集中します。

システムの要件を慎重に検討し、適切なトレードオフを選択することが、成功する分散システム設計の鍵となります。そして、いったん選択をした後も、洪水が引いて道が開通したときのように、システムの状態が正常に戻った際の適切な回復手順を用意しておくことが重要です。

## 参考資料

- [PostgreSQL Documentation: High Availability, Load Balancing, and Replication](https://www.postgresql.org/docs/current/different-replication-solutions.html)
- [Distributed Systems for Fun and Profit](http://book.mixu.net/distsys/single-page.html)
- [CAP Theorem Explained with a horse and carriage](https://www.asksiri.us/blog/2025-02-14.md) - 本記事の原典
- [Jepsen: On the CAP Theorem](https://jepsen.io/consistency)