Skip to content
←

필사 모드: CAP定理をごまかさずに理解する

日本語
0%
정확도 0%
💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

はじめに — 「二つを選べ」の問題

分散システムを学びはじめると、ほぼ必ずCAP定理に出会います。そしてほぼ必ず、こう要約された形で出会います。「一貫性（Consistency）、可用性（Availability）、分断耐性（Partition tolerance）のうち二つしか選べない」。三角形の図がついてきて、各データベースを三つの辺のどれかに貼り付けます。

この説明は覚えやすいのですが、間違いです。正確には、丸めすぎて誤解を招きます。実際のCAP定理が述べていることは、はるかに狭く精密です。この記事の目的は、その丸めを取り除くことです。ごまかしなしで、三つの文字がそれぞれ何を厳密に意味するのか、なぜ「三つのうち二つ」が誤解なのか、そしてこの定理が実際のシステム設計にとって何を意味するのかを押さえます。

三つの文字の厳密な定義

まず用語をきちんと固定しなければなりません。CAPの三つの文字は日常語のように聞こえますが、定理のなかでは非常に具体的な意味を持ちます。

C — 一貫性（Consistency）。 ここでの一貫性は**線形化可能性（linearizability）**を意味します。平たく言えば、すべてのクライアントがデータのコピーが一つしかないかのように見る、ということです。ある書き込みが成功して完了したら、その後に始まるすべての読み取りは、その書き込み（またはより新しい書き込み）を必ず見なければなりません。古い値を返してはいけません。これは後で扱うACIDのCとはまったく別の概念です。

A — 可用性（Availability）。 ここでの可用性は「故障していないすべてのノードが、すべてのリクエストに対して（エラーではない）応答を必ず返す」ということです。要は「故障していないすべてのノード」です。一部のノードが応答すればよいのではなく、生きているノードならすべて答えなければなりません。しかもその答えは妥当な時間内に来なければなりません。いつまでも待たせるのは可用とはみなしません。

P — 分断耐性（Partition tolerance）。 パーティション（partition）とは、ネットワークが分かれてノードのグループ間でメッセージがやり取りできなくなる状況です。分断耐性とは、こうしたパーティションが起きてもシステムが動き続けるという性質です。

この三つの定義を並べて見ると、よくある三角形の図がなぜ誤解を招くのか、その手がかりが見えてきます。

なぜ「三つのうち二つ」が間違いなのか

核心はこれです。分断耐性（P）は選択肢ではありません。 ネットワークパーティションは、あなたが選ぶかどうかにかかわらず現実に起きます。スイッチが死に、ケーブルが切れ、データセンター間のリンクが一瞬詰まります。複数の機械がネットワークで通信するかぎり、パーティションは「起こるかもしれないこと」ではなく「いつか必ず起こること」です。

ですから「Pを捨てる」という選択肢は事実上存在しません。パーティションに耐えられないシステムは、パーティションが起きた瞬間に間違った答えを返すか、データが壊れます。まともな分散システムにおいて、Pは交渉の対象ではありません。

では実際の選択は何でしょうか。CAP定理が本当に述べているのはこれです。

ネットワークパーティションが起きたその瞬間に、あなたは一貫性（C）か可用性（A）のどちらかを諦めなければならない。

パーティションが起きると、ノードのグループどうしが通信できなくなります。このとき片方のグループに書き込みリクエストが来たら、選べるのはちょうど二つだけです。

  • 可用性を取る（AP）：とにかく書き込みを受け入れて応答する。ただし別のグループはこの変更を知らないので、そちらで読むと古い値が出る。一貫性を諦めたことになる。
  • 一貫性を取る（CP）：別のグループと合意できないので、このリクエストを拒否するか止める。応答できないので、可用性を諦めたことになる。

つまりCAPは「平常時に三つのうち二つを選ぶ」問題ではなく、「パーティションが起きたときにCかAか」を選ぶ問題です。パーティションのない平常時にはCとAの両方を享受できます。選択はパーティションという例外的な状況でのみ強制されます。

  パーティションなし（正常）    パーティション発生
  ┌─────────────────┐        ┌─────────────────┐
  │ CとAの両方を      │  -->   │ CかAのどちらか    │
  │ 享受できる        │        │ 一つだけを選ぶ    │
  └─────────────────┘        └─────────────────┘

PACELC — より完全な絵

CAPは重要な半分を抜かしています。それは「パーティションがないときはどうなのか」です。CAPはパーティションの状況だけを語り、正常な状況については沈黙します。しかしシステムのほとんどの時間はパーティションのない正常状態です。その時間のトレードオフを説明するのがPACELCです。

PACELCはこう読みます。

パーティション（P）が起きれば、可用性（A）と一貫性（C）のあいだで選ぶ。そうでなければ（Else, E）、レイテンシ（L）と一貫性（C）のあいだで選ぶ。

前半（PAC）はCAPと同じです。新しいのは後半（ELC）です。パーティションのない正常な状況でも、依然としてトレードオフがあるということです。強い一貫性を保つには複数のレプリカが合意しなければならず、その合意には時間がかかります。 つまり一貫性を高めるとレイテンシが増えます。逆にレイテンシを下げるには合意をゆるめるか省かねばならず、そうすると一貫性が弱まります。

この枠組みで見ると、システムを二つの軸で分類できます。

分類パーティション時（PAC）正常時（ELC）意味
PA/EL可用性優先レイテンシ優先常に速さと可用性を取る
PC/EC一貫性優先一貫性優先常に一貫性を取る
PA/EC可用性優先一貫性優先パーティション時だけ可用性を譲らない
PC/EL一貫性優先レイテンシ優先パーティション時だけ一貫性を死守

PACELCがCAPより優れているのは、私たちが実際に毎日直面するトレードオフを捉えているからです。パーティションはまれな出来事ですが、「一貫性かレイテンシか」は正常運用のあいだずっと続く選択です。

実システムはどこに立っているか

理論を実システムに当てると、はるかに鮮明になります。

Amazon Dynamo系 — AP（そしてEL）。 Dynamoとその子孫たち（たとえばCassandra、Riak、DynamoDBの一部の設定）は可用性を最優先に設計されています。パーティションが起きても書き込みを受け入れ続け、あとでレプリカが再び出会ったときに衝突を解消します。この系統は**結果整合性（eventual consistency）**を提供します。今この瞬間はノードごとに値が違うかもしれませんが、時間が経てば収束します。正常な状況でも合意を待たずに低レイテンシを取るのでELに近いです。「カートは絶対に止まってはいけない」という要求がこの選択を生みました。二つの端末で入れた品物が一瞬食い違っても、あとで合わせればよいからです。

Google Spanner — CP（そしてEC）。 Spannerは正反対の極です。地球規模に分散したデータベースでありながら、強い一貫性（外部一貫性、事実上の線形化可能性）を提供します。パーティションが起きると、合意（Paxos）に到達できない側は書き込みを止めます。つまり一貫性のために可用性を譲ります。正常な状況でもレプリカ間の合意と精密な時刻同期を経るのでレイテンシが増えます。すなわちECです。Spannerが有名なのは、原子時計とGPSで作ったTrueTimeという仕組みで、この強い一貫性を地球規模で実用的な性能で実現したからです。しかしCAPを回避したわけではありません。パーティションが起きればやはり可用性を諦めます。

伝統的な単一ノードのRDBMS。 一台のPostgreSQLやMySQLのインスタンスはどうでしょうか。ここにはネットワークで分かれたレプリカがないので、パーティションという概念そのものがぼやけます。CAPは本質的に複数ノードに複製されたデータを扱う定理です。単一ノードはその舞台の外にあります。もちろんレプリケーションを付けた瞬間に、再びこのトレードオフの舞台に上がります。

まとめるとこうです。どのシステムも「CAPを破った」とか「三つとも持っている」とは言えません。パーティションが起きれば、誰もがCとAのあいだで選ばなければなりません。違いはどちらを選ぶよう設計したかだけです。

CAPのCとACIDのCは違う

ここで非常によくある混同を必ず押さえなければなりません。CAPのCとACIDのCは、綴りが同じだけで意味はまったく違います。

  • CAPのC = 線形化可能性。 複数のレプリカにまたがって、すべてのクライアントが最新の値を見ること。これは分散レプリケーションに関する性質です。
  • ACIDのC = 一貫性だが、ここでは「制約の保存」。 トランザクションがデータベースの不変条件（外部キー、一意制約、ユーザーが定義した規則など）を壊さず、有効な状態から有効な状態へのみ移すこと。これは一つのトランザクションの整合性に関する性質です。

両者は別の階層の話です。ACIDのCはアプリケーションが定義した規則をデータベースが守るという約束であり、CAPのCは複数のレプリカが同じ値を見せるという約束です。この二つを一緒くたにすると、「CPシステムはACIDを保証する」といった誤った文章を書いてしまいます。実際には互いに独立した概念です。

もう一歩踏み込むと、分散トランザクションでよく言う分離レベルの最上位である**直列化可能性（serializability）と、CAPの線形化可能性（linearizability）も違います。直列化可能性は複数のトランザクションが何らかの逐次実行と等価な結果を出すことであり、線形化可能性は単一オブジェクトの操作が実時間の順序を守ることです。この二つを合わせた強い保証を厳密直列化可能性（strict serializability）**と呼び、Spannerが目指すのがだいたいここです。用語が似ていて紛らわしいので、「何についての順序保証なのか」を常に問い直すべきです。

一貫性はスペクトラムである

CAPは一貫性を「線形化可能かどうか」の二分法で扱いますが、現実の一貫性は広いスペクトラムです。強い側から弱い側へ何段階か辿ると感覚がつかめます。

  • 線形化可能（linearizable）：もっとも強い。すべての読み取りが最新の書き込みを見る。
  • 逐次一貫性（sequential）：すべてのクライアントが同じ順序で操作を見るが、その順序が実時間と一致する必要はない。
  • 因果一貫性（causal）：因果関係のある操作だけ順序を守る。無関係な操作は順序が入れ替わって見えてもよい。
  • 結果整合性（eventual）：新しい書き込みがなければ、いつかはすべてのレプリカが同じ値に収束する。それまでは古い値を見ることがある。

APシステムが「一貫性を諦める」と言うとき、たいていは完全な無秩序に落ちるのではなく、このスペクトラムの弱い側（たとえば結果整合性や因果一貫性）を選んでいます。ですから「APかCPか」という二分法よりも、「どの水準の一貫性をどんな代償で買うのか」を問うほうが実務に近いです。

よくある誤解

ここまでの内容を誤解のリストとして整理し直すとこうなります。

  • 「平常時に三つのうち二つを選ぶ」 — 違う。パーティションがなければCとAの両方を享受する。選択はパーティションの瞬間にのみ強制される。
  • 「Pは捨てられる選択肢だ」 — 違う。ネットワークパーティションは現実に必ず起きるので、分散システムにおいてPは事実上必須。
  • 「CAシステムが存在する」 — 複数ノードに複製されたシステムでパーティションを無視するCAは実質的に成り立たない。パーティションが起きれば結局CかAのどちらかを失う。
  • 「CPシステムは常に利用不可の状態になる」 — 違う。CPシステムはパーティションが起きたその瞬間、その影響を受けた部分でだけ可用性を譲る。平常時はちゃんと応答する。
  • 「CAPのCはACIDのCだ」 — 違う。前節で見たとおりまったく別の概念。
  • 「結果整合性はデータがぐちゃぐちゃという意味だ」 — 違う。収束を保証し、因果関係の維持のようなより強い形もある。

設計者のための実践指針

この理論を実際の決定に移すときに役立つ問いを整理します。

まずこのデータに古い値を一瞬見せてもよいかを問うべきです。ソーシャルフィードのいいね数、商品の閲覧数などは一瞬食い違っても大ごとではありません。ここではAPと低レイテンシが妥当です。逆に、銀行残高、在庫数、座席予約のように二重に売ってはいけないデータは強い一貫性が必要なので、CP側に傾きます。

次にパーティションが起きたときの動作を明示的に設計したかを問うべきです。多くの事故は「パーティションは起きないだろう」という暗黙の前提から来ます。パーティションは必ず来るので、「そのとき書き込みを止めるのか、受け入れてあとで和解させるのか」をあらかじめ決めておかねばなりません。後者を選んだなら、衝突解消の戦略（最新タイムスタンプ優先、バージョンベクトル、CRDTなど）も一緒に決める必要があります。

最後に正常時のレイテンシ予算を知っているかを問うべきです。PACELCのELCが言うように、強い一貫性は正常時でもレイテンシを招きます。地球の裏側のレプリカまで合意を待つ費用を負担できるのか、それとも地域ごとに弱い一貫性を許してレイテンシを削るのかを決めなければなりません。

おわりに

CAP定理は分散システムでもっともよく引用され、もっともよく誤解される結果です。手ぶりまじりの「三つのうち二つを選べ」という要約は覚えやすいのですが、肝心の真実を隠します。本当の話ははるかに精密です。分断耐性は事実上必須であり、本当の選択はパーティションが起きた瞬間にのみ、一貫性と可用性のあいだで行われます。そしてPACELCが思い出させるように、パーティションのない平常時にも、一貫性とレイテンシのあいだの静かなトレードオフが常に流れています。

Dynamoが可用性を、Spannerが一貫性を選んだのは、どちらか一方が正しいからではなく、それぞれが解こうとする問題が違ったからです。よい設計者は「CAPに勝った」とは主張しません。代わりに「このデータについて、パーティションが起きたとき、私は何を諦めるのか」という問いにはっきり答えます。手ぶりを取り除いてみれば、CAPは魔法の三角形ではなく、そのはっきりした問いを投げかけさせてくれる正直な道具になります。

参考資料

현재 단락 (1/65)

分散システムを学びはじめると、ほぼ必ずCAP定理に出会います。そしてほぼ必ず、こう要約された形で出会います。「一貫性（Consistency）、可用性（Availability）、分断耐性（Parti...

작성 글자: 0자원문 글자: 6,956자작성 단락: 0/65