CAP は3つから2つではない — 定理が二択にしているのはどれか — 分散システムの土台

リクエストがアプリケーションに届くまで

ブラウザURL入力
DNS名前→IP
ルータ経路選択
ロードバランサ振り分け
Nginx受け口
アプリ処理今ここ
DB保存

前回、FLP が潰すのは停止性であって安全性ではないことを見ました。今回は同じ対立が CAP という名前で語られるとき、何が二択になっているのかを原文で確かめます。

まず結論

Gilbert & Lynch 2002 の Theorem 1 が同時に満たせないとしているのは Availability と Atomic consistency の2つで、分断耐性はそこに並ばず、定理が成り立つ世界の設定の側に置かれています。

提唱者の Brewer 自身が2012年に The "2 of 3" formulation was always misleading と書いています。選択は分断が起きている間に、しかも操作ごとに発生します。

? 読む前に予測

CAP 定理を形式化した Gilbert & Lynch 2002 の Theorem 1 は、いくつの性質を並べて「同時には満たせない」と述べているでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

定理が二択にしているのは、どれとどれか

前回、FLP が潰すのは停止性であって安全性ではないことを見ました。同じ対立が CAP という名前で語られます。ただし流布している形は、原文と違います。Gilbert & Lynch 2002 の Theorem 1 の逐語です。

Theorem 1 It is impossible in the asynchronous network model to implement a read/write data object that guarantees the following properties:

Availability

Atomic consistency

in all fair executions (including those in which messages are lost).

箇条書きは2つです。Partition tolerance が入っていません。誤植ではなく論文の作りで、分断耐性は §2.3 でこう置かれています。

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.

つまり分断耐性は選択肢ではなく、定理が成り立つ世界の設定です。「メッセージが任意に失われうる」世界の中で C と A は同時に満たせない。これが定理の形です。

証明の骨格も難解ではありません。§3.1 です。

The basic idea of the proof is to assume that all messages between G1 and G2 are lost. Then if a write occurs in G1, and later a read occurs in G2, then the read operation cannot return the results of the earlier write operation.

2ノードで足ります。届かないメッセージは読めない、というだけです。

Theorem 1 の構造。P は並んでいる性質ではなく、外枠の設定

前提(モデル)メッセージが任意に失われうるネットワーク = P

この世界の中で

Availabilityいつかは必ず応答が返る

Atomic consistency単一ノードのように見える

同時には満たせない

二択が発生する選ぶのは C と A のどちらか

・P を「選ばない」という選択肢は、この図に置き場所がない

具体実物

CAP の A は「速い」という意味ではない

可用性の定義は実務の語感とずれます。§2.2 です。

For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response. That is, any algorithm used by the service must eventually terminate. In some ways this is a weak definition of availability: it puts no bound on how long the algorithm may run before terminating, and therefore allows unbounded computation.

時間の上限を置かないと論文自身が断っています。CAP の A は「速い」ではなく「いつかは必ず返る」だけ。A を捨てるとは、遅くなることではなく返ってこなくなることです。

本コースで見た etcd の分断実測がこれでした。少数派に落ちた1台への書き込みは、即座にエラーが返ったのではなく context deadline exceeded になるまで返りません。

✓ ここまでの確認

Gilbert & Lynch 2002 における Partition tolerance の位置づけとして正確なのはどれですか。

抽象原理

平常時は両方取れる、には限定が要る

Brewer は2012年の記事で自ら定式化を訂正しています。冒頭節です。

The "2 of 3" formulation was always misleading because it tended to oversimplify the tensions among properties. Now such nuances matter. CAP prohibits only a tiny part of the design space: perfect availability and consistency in the presence of partitions, which are rare.

見出し Why "2 of 3" is misleading には理由が3つ挙がっています。

First, because partitions are rare, there is little reason to forfeit C or A when the system is not partitioned. Second, the choice between C and A can occur many times within the same system at very fine granularity; not only can subsystems make different choices, but the choice can change according to the operation or even the specific data or user involved. Finally, all three properties are more continuous than binary.

「平常時は両方取れる」を無条件に書くと、一次ソースに反します

Gilbert & Lynch 2012 の §2 は、純粋非同期モデルについてこう書いています。

In fact, if communication is asynchronous … it is possible for the same situation to occur even in executions in which there are no messages lost, i.e., no actual partition! Notably, in the scenario describe above, server p2 eventually must return a response, even if the system is partitioned; … Thus it is even impossible to guarantee consistency when there are no partitions, and return a bad (inconsistent) answer only when partitions occur.

時計もタイムアウトも無い純粋非同期モデルでは、必ず応答を返す系は、分断が無くても一貫性を保証できません。 遅れが十分大きければ、分断と同じ状況になるからです。両方取れるのは部分同期モデルの話で、根拠は GL2002 §4.3。

There are partially synchronous algorithms that will return atomic data when all messages in an execution are delivered (i.e., there are no partitions), and will only return inconsistent (and, in particular, stale) data when messages are lost.

そのモデルの定義は §4.1 にあり、各ノードが時計を持ち(同期はしていない)、各メッセージは既知の時間 tmsg 以内に届くか失われるかのどちらかです。

前回の FLP と同じ構造です。「タイムアウトが使える」という仮定を置いた瞬間に、不可能性の射程の外へ出ます。前回は Raft 論文がその語を使っていないので断定を避けましたが、GL2002 は明示的に partially synchronous model と書いているので、こちらは断定できます。

GL2012 §1 は、この対立に名前を付けています。

Consistency (as defined in the CAP Theorem) is a classic safety property … Availability is a classic liveness property … The CAP Theorem, in this light, is simply one example of the fundamental fact that you cannot achieve both safety and liveness in an unreliable distributed system.

前回 FLP で見たのと同じ土俵です。CAP を FLP と別の話として覚えると、この接続を落とします。

具体実物

「2つを選ぶ」の中身を読むと、選択肢になっていない

§3.2 は「2つ」それぞれの中身に例を挙げています。

GL2002 §3.2 が挙げる例(論文自身が trivial と呼んでいるもの)表

節        組み合わせ            論文が挙げる例
3.2.1     Atomic + Partition   全要求を無視する系(trivial)
3.2.2     Atomic + Available   分断が無ければ可能。LAN の例
3.2.3     Available + Partition 常に初期値 v0 を返す系(trivially)

§3.2.1 は The trivial system that ignores all requests meets these requirements、§3.2.3 は the service can trivially return v0, the initial value, in response to every request。片方の極限は何も応答しない系、もう片方は常に初期値を返す系。どちらも論文が trivial と呼んでいます。

Brewer は "CA" という組み合わせ自体を CAP Confusion 節で切り捨てています。

As some researchers correctly point out, exactly what it means to forfeit P is unclear. Can a designer choose not to have partitions? If the choice is CA, and then there is a partition, the choice must revert to C or A.

分断を「選ばない」ことはできません。起きたらそのとき C か A に戻るだけです。そして Brewer は、分断そのものを時間で定義し直しています。Cap-latency connection 節です。

Operationally, the essence of CAP takes place during a timeout … Thus, pragmatically, a partition is a time bound on communication.

さらに there is no global notion of a partition, since some nodes might detect a partition, and others might not とも書いています。本コースで「落ちているとは言えない」と見たのと同じことです。分断とは、各ノードが自分のタイムアウトで勝手に下している判定です。

✓ ここまでの確認

「分断が起きていない平常時は一貫性と可用性の両方が取れる」と書くとき、必ず添えるべき限定はどれですか。

⇄ 2つを見比べる

具体例 A

Cassandra の Consistency Level(公式文書の記述)

Cassandra 公式の Tunable Consistency 節は、自らの仕組みを操作ごとの交換だと説明しています。読みと書きそれぞれに何ノードの応答を要求するかをクライアントが指定するので、同じクラスタへの2つの操作が別々の点を選べます。

公式が述べている仕組み(Tunable Consistency / Picking Consistency Levels)表

記述               逐語の要点
交換の粒度         per-operation tradeoff between consistency and availability
重なりの条件       W + R > RF
重なると何が言えるか guaranteed to participate in both the write and the read

具体例 B

分断した etcd の3操作(本コースの実測)

3ノードを1対2に分断し、少数派側で3つの操作を試した実測です。同じ分断・同じ瞬間に3通りに振る舞いました。書き込みと既定の読み取りは返らず、`--consistency=s` の読み取りだけが分断前の古い値を返しています。

少数派側の3操作(etcd 3.5.17、2026-09-18 の実測)表

操作                     結果
書き込み                 context deadline exceeded(返らない)
線形化可能読み取り       context deadline exceeded(返らない)
consistency=s の読み取り before-partition(古い値が返る)

公式文書が語る設計と、別製品の分断実測。共通している構造は何でしょうか。

「この系は C 側だ」と一言で言えるかを、両方で考えてみてください。

実務の場面設計レビューで AI が返してきた、もっともらしい CAP の説明

「CAP 定理により3つから2つを選ぶ必要があります。本システムは CP を選択しているため、分断時は一貫性を優先して停止します。平常時は C と A の両方が得られます」。おかしい箇所が3つあります。

1つ目。「3つから2つ」は Theorem 1 の形ではありません。ただし強く否定しすぎると逆に誤りで、§3.2 にはその言い方があります。指摘すべきは「二択にしているのは C と A で、P は前提」という構造のほうです。

2つ目。「CP を選択しているため停止します」は、系に1つのラベルを貼っています。Brewer は操作ごとに選択が変わりうると書き、etcd の実測でも3操作が分かれました。問い返すべきは「どの操作の話ですか」。

3つ目。「平常時は両方得られます」に限定がありません。GL2012 は純粋非同期モデルで必ず応答を返す系について Thus it is even impossible to guarantee consistency when there are no partitions, and return a bad (inconsistent) answer only when partitions occur. と書いています。

3つとも正しい断片を、当てはまらない強さと範囲に広げた型です。前回の FLP と同じ手口。手がかりも同じで、どのモデルの話か、どの粒度の話かを問い返すことです。

この章のまとめ

GL2002 の Theorem 1 が並べるのは Availability と Atomic consistency の2つ。Partition tolerance は §2.3 の「メッセージが任意に失われうる」という前提の側にある。
ただし同じ論文の §3.2 には any two of these three properties can be achieved という文がある。「論文は3つから2つとは言っていない」と断定してはいけない。
CAP の A は「速い」ではない。「いつかは必ず返る」だけ。A を捨てるとは返ってこなくなること。
Brewer は2012年に The "2 of 3" formulation was always misleading と自ら訂正している。
「平常時は両方取れる」は部分同期モデルの話。 純粋非同期では、必ず応答を返す系は分断が無くても一貫性を保証できないと GL2012 が明記。
選択の粒度は系ではなく操作。Cassandra 公式の per-operation tradeoff と etcd の分断実測が同じ形。
GL2012 は一貫性を安全性、可用性を活性と位置づけている。前回の FLP と同じ土俵。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

使っているデータストアで、読み取りの一貫性を操作ごとに指定する方法があるか公式文書を調べる(無ければ、その系では固定ということ)
自分が運用している系について「分断時に止まるのはどの操作か」を、系全体ではなく操作ごとに書き出す。書けない操作があれば、それが未確認の箇所
設計文書やレビューに「CP」「AP」という分類語が出てきたら、どの操作について言っているのかを確認する
Brewer の「分断とは通信の時間上限である」という見方で、自分の系のタイムアウト値を読み直す

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 4正解: 0

Brewer が2012年の記事で "2 of 3" の定式化について述べたこととして正確なのはどれですか。

用語集(5語)

Atomic consistency(原子的一貫性): GL2002 §2.1 の定義では、全操作に全順序が存在し、各操作が単一の瞬間に完了したように見えること。単一ノード上で一度に1操作ずつ処理しているかのように振る舞うこと。線形化可能性と同じもの。
Availability(CAP における可用性): GL2002 §2.2 の定義では、故障していないノードが受けたすべての要求がいつか応答に至ること。it puts no bound on how long the algorithm may run before terminating と論文自身が断っており、速さの保証ではない。
Partition tolerance(分断耐性): GL2002 では選択肢ではなくモデルの設定。§2.3 が to lose arbitrarily many messages sent from one node to another と定めている。
部分同期モデル: GL2002 §4.1 のモデル。各ノードが時計を持ち、すべて同じ速さで進む(同期はしていない)。各メッセージは既知の時間 tmsg 以内に届くか、失われるかのいずれか。
安全性 / 活性: GL2012 §1 の枠組み。安全性は「悪いことが起きない」、活性は「いつか良いことが起きる」。一貫性を安全性、可用性を活性の典型例としている。

CAP は3つから2つではない — 定理が二択にしているのはどれか