CAPと一貫性モデル

CAPは「3つの中から2つを選ぶ」ものではない——ネットワーク分断は避けられず、発生時には一貫性と可用性の間の選択を余儀なくされる。linearizabilityからeventualまで、一貫性はスイッチではなくスペクトルであり、それぞれの選択には対応するエンジニアリングコストと適用シーンが存在する。

CAP定理 (Brewer 2000)

CAPは「一貫性、可用性、分断耐性の3つの中から2つを選ぶ」という意味ではない。Eric Brewer本人の本来の意図は、⁠ネットワーク分断は避けられず、それが発生した際に、あなたは一貫性と可用性のどちらかを犠牲にして選択しなければならないということである。

分散システムにおけるこれらの用語の正確な定義は以下の通り：

• Consistency (一貫性): Linearizabilityと同等——すべての操作が、あるグローバルな順序でアトミックに実行されたかのように振る舞う。読み取り操作は、必ず直近の書き込みの結果を返さなければならない。「最終的な一貫性」でも「read-your-writes」でもなく、最も強力な形式化定義である。
• Availability (可用性): 障害が発生していないノードは、すべてのリクエストに対してエラーではない応答を返さなければならない。注意——「最新データを返す」ことではなく、「errorやtimeoutではなく、必ずresponseを返す」ことである。古いデータを返しても、それはavailableとみなされる。
• Partition Tolerance (分断耐性): システムが任意のネットワーク分断下でも稼働し続けること。ネットワーク分断とは、ノードの一部間でメッセージの損失や遅延が閾値を超えた状態を指す。

したがって、より正確な表現は、⁠ネットワークが正常な場合はCA（強一貫性＋高可用性）を選択できるが、ネットワーク分断が発生した場合はCまたはAのいずれかを放棄しなければならない⁠——「全ノードが新しいデータを見る」ことと「全ノードが即座に応答する」ことの両方を同時に保証することは不可能である。

なぜP発生時にCAを両立できないのか

最も単純な例として、2つのノードAとBがあり、ネットワークが切断されて分断されるとする。クライアントがAに x=1 を書き込む。ここで別のクライアントがBからxを読み取る。

• Bが即座に古い値を返す（可用性を保証）→ 一貫性が崩れる（Cを放棄）
• BがAから同期するまで応答を拒否する（一貫性を保証）→ 可用性が失われる（Aを放棄）

魔法はない——これは物理法則である。AとB間のメッセージ遅延は、最悪の場合、無限大になり得る。

PACELC拡張

CAPは「分断発生時」のみを議論している。PACELCはもう半分を追加した：⁠ネットワークが正常な場合（分断がない場合）、レイテンシーと一貫性の間でトレードオフを行わなければならない⁠——正常なメッセージ往復にも時間がかかるからである。強一貫性の操作（linearizable readなど）は、ネットワークが完璧であっても、過半数のノードの確認を待つ必要があるため、より高いレイテンシーを招く。

一貫性のスペクトル（強から弱へ）

Linearizability (強一貫性、アトミック一貫性)

定義：各操作は、それが呼び出されてから返されるまでの間のいくつかの瞬間にアトミックに実行されたかのように見える。すべての操作にはグローバルな順序があり、この順序はリアルタイムと一致しなければならない——操作Aが操作Bが開始される前に返された場合、Aはグローバル順序においてBの前に存在しなければならない。

linearizabilityを満たすシステム：etcd (ReadIndex + Raft)、ZooKeeper (sync後のリーダー読み取り)、Google Spanner (TrueTime)。

Sequential Consistency (順序一貫性)

linearizabilityより少し弱い：すべての操作にはグローバルな順序があるが、この順序はリアルタイムを尊重する必要はない⁠——各クライアント自身の操作順序が保持されていればよい。

つまり、クライアント1の write(1) が write(2) より前であっても、クライアント2の読み取りは write(2) の前でも 2 を見ることができる（write(2) が読み取りの後に呼び出された場合でも）——クライアント1の操作順序が 1→2 である限り。これは実際によく見られる現象である：フォロワーへの非同期レプリケーションにより、クライアント2が新しいデータを先に参照する可能性がある。

Causal Consistency (因果一貫性)

順序一貫性よりさらに弱い：⁠因果関係のある操作のみが、すべてのノードで同じ順序で参照されることを保証し、並発的な操作は任意の順序でよい。

因果関係の定義 (Lamport's happens-before)：操作Aが操作Bの前に発生した場合（同一クライアント内）、またはAの結果がBによって観察され、何らかの形でBに影響を与えた場合（例えば、BがAが書き込んだ値を読み取った場合）、A→B と定義される。A→B は、すべてのノードがAをBの前に参照しなければならないことを意味する。

因果関係のない並発操作：順序は問題なく、最終的にはCRDTやバージョンベクトルによって解決される。

実装：ベクトルクロック（Dynamo/Riak）、Lamportタイムスタンプ（MongoDBレプリカセットの lastWriteDate）。

Eventual Consistency (最終一貫性)

最も弱い保証：新しい書き込みが行われなくなれば、最終的にすべてのレプリカが同じ値に収束する。「どのくらい速くか」「中間状態で何が見えるか」は保証されない。

DNS、CDN、マルチリーダー非同期レプリケーション（MySQLレプリケーションラグ）などで一般的。

各モデルの形式化の違い

実務におけるコスト

強一貫性 = より高いレイテンシー + より低い可用性：

• レイテンシー: linearizable read は過半数のノードからの応答を待つ必要がある（Raft ReadIndex + ハートビートによるリーダー身份の確認）→ 1-2 RTT
• 可用性⁠: 分断発生時、linearizable システムは書き込みを拒否しなければならない（etcdの場合、少数派パーティションでは読み取り専用になる）
• スケーラビリティ⁠: すべての書き込みはリーダーを経由しなければならない（Raft/Paxosのログレプリケーション）→ 書き込みスループットは単一ノードに制限される

なぜ多くのシステムが最終一貫性を選択するのか：Amazon Dynamoの設計哲学——ショッピングカートサービスが一貫性のために利用できなくなれば、直接的な売上損失につながる。世界最大の分散データベースであるDNSは、究極の可用性を得るために、数分から数時間の一貫性遅延を選択した。

参考文献

• 論文⁠: "Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services" (Gilbert & Lynch, 2002 — CAPの形式化証明)
• 論文⁠: "Consistency Tradeoffs in Modern Distributed Database System Design" (PACELC, 2012)
• 論文⁠: "Linearizability: A Correctness Condition for Concurrent Objects" (Herlihy & Wing, 1990)

キーワード: CAP, PACELC, linearizability, sequential consistency, causal consistency, eventual consistency, happens-before