CAP定理を見直す。“CAPの3つから2つを選ぶ”という説明はミスリーディングだった

2013年1月28日

分散システムにおいては以下の3つの要素のうち2つしか同時に満たすことができない、というCAP定理を提唱したのは、Eric Brewer氏でした。

C：Consistency（一貫性）
A：Availability（可用性）
P：Tolerance to network Paritions（ネットワーク分断への耐性）

一般にリレーショナルデータベースでは、一貫性（C）と可用性（A）をできるだけ保証する代わりに、ネットワーク分断への耐性（P）を犠牲にしています。ネットワークが途中で切れたり大きく遅延した場合、動作が保証されなくなってしまうわけです。

12年後のCAP定理: "法則"はどのように変わったか

一方でNoSQLでは一貫性（C）よりも可用性（A）とネットワーク分断への耐性（P）を優先させるものが多く、分散システムでの動作に向いていると説明されます。このようにNoSQLの説明にこのCAP定理がしばしば引用されることになり、NoSQLの普及とともにCAP定理も広く知られるようになりました。

しかし、今月Publickeyで公開した記事「NoSQLの現状。これまでの成功と失敗」の結論部分では、こういう単純なCAP定理の理解に対して「今では、Eric Brewer氏はその定理を改め、シンプルなCAPを主張する時代は完全に終わっています」と指摘しています。

どういうことなのでしょうか？

CAP定理を提唱したEric Brewer氏自身が執筆し、昨年5月にInfoQに掲載された記事「12年後のCAP定理: “法則”はどのように変わったか」で、Brewer氏は次のように書いています。

“3のうち2つ”という公式はミスリーディングでした。というのは、この公式は3つの属性の緊張関係を過度に単純化してしまうからです。過度の単純化は問題です。

Brewer氏自身が、CAP定理の過度な単純化は問題であるとし、

現在のCAPの目的は特定のアプリケーションが必要とする一貫性と可用性を最適化することでしょう。

と書いています。

では、現在においてCAP定理とはどのように解釈すべきものなのでしょうか。ここではBrewer氏の書いた「「12年後のCAP定理: “法則”はどのように変わったか」」から、その記事の前半部を引用しつつ、解説を加えながら見ていくことにしましょう（InfoQ Japanからの転載許可を得ています）。

まず、Brewer氏がなぜ“3つのうち2つ”といった単純な理解では不十分なのか、その理由を解説した章を読んでみましょう。分かりやすいように、大事だと思われるポイントを太字にしました。

なぜ“3つのうち2つ”がミスリーディングなのか

CAPを理解する最も簡単な方法は分割の両側にひとつずつノードがある場合を考えることです。片方のノードだけ状態を更新できるようにすると、2つのノードに一貫性がなくなります。つまり、Cが失われます。

一貫性を維持しようとすれば、一方のノードは利用できない状態であるかのように動作しなければなりません。この場合、Aが失われます。一貫性と可用性が維持できるのは、ふたつのノードが通信できる場合だけです。この場合、Pが失われます。一般的には、広域システムの場合、設計者はPを失えませんので、CとAの間で難しい選択を強いられます。

ある意味ではNoSQLの勃興は可用性を第一優先に、一貫性を二の次にする選択肢を生み出していると言えます。ACID属性に従うデータベース（原子性、一貫性、独立性、耐久性）はこの反対です。"ACID、BASE、CAP"のセクションでこの違いを詳述します。

実のところ、この違いについての検討がCAP定理を生み出しました。1990年代中頃、私は同僚と共にさまざまなクラスタベースの広域システム(クラウドコンピューティングの先駆け)を構築していました。検索エンジンやプロキシキャッシュ、コンテンツ配信システムなどです（*1）。収益目標と契約仕様のため、システムの可用性が第一優先になり、私たちはキャッシュを採用したり、後からのデータ復旧に使うために更新を記録したりして、可用性を最適化しました。しかし、このような方法で可用性は向上さしましたが、一貫性が犠牲になりました。

一貫性対可用性の議論の最初のバージョンはACID対BASEというかたちで現れました（*2）。しかし、この議論は当時あまり受け入れられませんでした。皆、ACID属性を好んでおり、ACIDを諦められなかったからです。CAP定理の目的はより広く設計について探索する必要があることを示すことでした。そして、"3つのうち2つ"という公式がうまれました。CAP定理は1998年の秋に生まれ、1999年に発表され、2000年のSymposium on Principles of Distributed Computing（*4）の基調講演での発表がきっかけで証明されました。

“CAPの混乱”セクションで説明する通り、“3つのうち2つ”はいくつかの場面でミスリーディングです。まず、分割は滅多に起きないので、分割のない状態ではCやAは失われません。次に、同じシステムの中でとても細かい粒度で何度もCとAのどちらかを選択する場合があります。サブシステムによって異なる選択をすることもできますし、操作やデータや関係するユーザによって選択を変えることもできます。最後に、3つの属性は満たす/満たせないのふたつの選択肢しかないのではなく、度合いがあります。可用性は明らかに0%から100%まで度合いがありますが、一貫性にも多様なレベルがあります。分割耐性にも同様です。システムに分割があるかどうかについての意見の相違も含んだ度合いがあります。

このような度合いを調べ、3つの属性の最適化を図る場合、分割への従来の対処法をより推し進める必要がありますが、これには根本的な困難が伴います。分割は滅多に起きないので、ほとんどの場合、完璧なCとAを実現できますが、分割が発生した場合のために、分割を検知し明示的に対処する仕組みを整えておく必要があります。この仕組みは3つのステップに分かれます。まずは分割を検知するステップ、そして、動作が制限される分割モードに明示的に移行するステップ、最後に復旧処理を起動し一貫性を復元し、分割中に発生した動作不良を補償するステップです。

ここでBrewer氏が挙げたポイントは、同じシステムの中でもネットワークが分断した状態になったときに一貫性（C）を優先させるか、可用性（A）を優先させるかは細かい粒度でさまざまな選択があること、そして可用性（A）や一貫性（C）などには度合いがある、といった点です。それゆえに、CAPの3つから2つを選ぶこと、といった単純な説明はミスリードである、と言いたいのでしょう。

Brewer氏は以下の章で、CAPの本質はネットワーク分断によって処理のタイムアウトが発生したときに表れる、と書いています。つまり、ネットワーク分断が発生するとシステム内の一貫性（C）が確認できなくなってしまうため、処理を止めてでも一貫性が失われないようにするのか、それとも一貫性はなくてもいいから処理を止めずに可用性（A）を優先させるのか、選択によってシステムの性格が大きくことなるためです。

この説明によって、単純にCAPの3つから2つを選ぶのではなく、状況に応じた選択肢やさまざまな度合いがあることが分かります。

CAPと通信の遅延

通常の解釈では、CAP定理は遅延を無視しています。しかし実際には、遅延と分割には深い関連があります。CAPの本質はタイムアウトが発生した時に現れます。つまり、プログラムが分割が発生した場合の判断をしなければならない時です。すなわち、

処理を中断して可用性を犠牲にする。あるいは

処理を進めて一貫性を犠牲にする。

例えばPaxosや2フェーズコミットを使って一貫性を保証するために通信のリトライをするのは、この決定を遅らせているだけです。プログラムはどこかの時点で判断を下さなければなりません。無限にリトライを続けるのは、AよりもCを優先するということです。

実際には分割は通信上のある一定の時間幅として現れます。その一定の時間内に一貫性を保証することに失敗したということが分割の発生を示し、その処理についてCかAのどちらかを選択することになります。このような考えは遅延に関する設計上の本質的な課題を捉えます。つまり、分割の両側は通信しないで、それぞれ独立して処理を進めるかどうかということです。

この実践的な視点から考えるといくつかの重要な結論が導けます。第一に全体に適用できる分割の概念は存在しないということです。というのは、あるノードは分割を検知するかもしれませんが、別のノードは検知しないかもしれないからです。第二にノードは分割を検知すると分割モード、つまりCとAの最適化を目指すモードになるということです。

最後に、設計者は通信相手の応答時間を踏まえて意図的に時間幅を設定できるということです。この時間幅が狭いシステムはネットワークが遅いだけで、実際には分割が発生していない場合でも分割モードになってしまうかもしれません。

広域にまたがって一貫性を維持するために発生する遅延を避けるために厳密なCを諦めた方がよい場合もあります。YahooのPNUTSはリモートのコピーを非同期でメンテナンスするため、一貫性が崩れます（*5）。しかし、マスタコピーがローカルにあるので、遅延は発生しにくいです。実際、この方法は上手く動作します。ユーザのデータが、そのユーザのいる場所によって自然に分かれているからです。各ユーザのデータマスタがそのユーザの近くにあるのは理想的です。

Facebookは反対の方法を採用しています（*6）。マスタコピーをひとつの場所に置き、ユーザは、自分のいる場所に近いが最新でない可能性のあるコピーを利用します。しかし、ユーザがページの更新を行うと、少しの間、遅延が発生しつつも、更新も読み込みもマスタコピーに対して行われます。20秒経つと、近くにあるコピーを参照するようになります。つまり、更新が近くのコピーに反映されるまではマスタコピーを参照するのです。

CAPのPはネットワーク分断（Partiton）のPですが、そもそもネットワークが分断したという判断をシステムが完璧に行うことはできないと、Brewer氏は指摘しています。システムの一部だけがネットワーク分断を検知したときの動作や、分断していないかもしれないけれど遅延した状態がある程度続いたらどこかで分断と見なす、などの動作があるわけです。

そしてその実装も、Yahoo!やFacebookの例が紹介されているように単一ではありません。

次の章ではCAP定理がなぜ混乱しやすいのか。それらを具体的な例で示し、まとめています。

CAPの混乱

CAP定理は誤解されがちです。特に可用性と一貫性の範囲については誤解が多いです。この誤解が原因で望ましくない結果になる場合があります。ユーザがサービスを全く利用できなければ、CもAも選択できません。この場合、ユーザのクライアント環境でサービスの一部を動かすしかありません。この例外処理は非接続処理やオフラインモードとして知られていますが（*7）、次第に重要になっています。クライアント永続化ストレージのようなHTML5の機能のいくつかは、この非接続処理を容易にします。このような機能はCよりもAを優先するものであり、長時間の分割が発生した場合は復旧を行わなければなりません。

一貫性とは、ある範囲内では状態の一貫性が維持されるが、その範囲外は全く考慮されない、ということです。例えば、最優先される範囲の内部では一貫性と可用性を完全に保証できるものの、その範囲の外ではサービスが利用できない、ということです。Paxosや原子的同報通信システムはこのシナリオで利用できます（*8）。Googleでは普通、最優先される範囲はひとつのデータセンター内で完結しています。しかし、Chubby（*9）で使われているPaxosはグローバルなコンセンサスを確保するために広域で使われます。Megastore（*10）の高可用永続化ストレージも同様です。

独立していて、一貫性のある部分は分割が発生しても処理を進められますが、グローバルな不変式を侵している可能性があります。例えば、シャーディングをする場合です。設計者が各ノードにデータを分けた場合、各シャードは分割が発生したときに処理を進めても問題なさそうです。反対に関連する状態が分割を横断している場合や、グローバルな不変式が必要な場合は、最高でもひとつのノードだけ処理を進めることしかできません。最悪の場合は全く処理を進められません。

“3つのうちの2つ”として一貫性と可用性(CA)を選ぶのは合理的でしょうか。一部の研究者が正しく指摘しているように、Pを失うということが正確に何を意味するのか明確ではありません（*11,*12）。設計者は分割が起こらないことを選択できるのでしょうか。CAを選び、分割が発生した場合、CかAの選択に逆戻りします。これは確率論的に考えるのが良いでしょう。CAを選ぶということは分割発生の確率を、災害や複数の問題の同時発生による障害など他の障害の発生確率よりもはるかに小さく見積もるということを意味します。

このように考えるのは意味があります。現実のシステムはある種の障害の発生が重なるとCとAを両方とも失います。つまり、3つの属性はすべて程度の問題なのです。実際にはほとんどの場合、ひとつのデータセンター内では分割は発生しないと仮定し、CAを保証する設計がされています。従来のデータベースもこのような設計になっていますが、CAPが登場するまでは既定の設計でした。しかし、ひとつのデータセンター内で分割が発生することは少ないとはいえ、可能性はあるので、CAを保証する設計は問題を孕みます。広域で遅延が発生することを前提として、より良い性能を求めるため完全な一貫性をあきらめるのが相対的に一般的な設計です。

CAPの混乱の要因は他にもあります。それは一貫性を失う場合の隠れたコストです。すなわちシステムの不変式を明らかにしなければならないということです。一貫性のある小さなシステムの美点は、設計者が意識しなくても不変式が維持できることです。反対に、設計者がAを選んだ場合、分割が発生した時に不変式を復元できるようにしておく必要があります。したがって、すべての不変式を把握しておく必要がありますが、これは難しく問題が発生しやすいです。この問題は本質的には、マルチスレッドによる並列更新を難しくしている問題と同じです。

元記事「12年後のCAP定理: "法則"はどのように変わったか」では、このあとネットワーク分断時にどのような処理が考えられるのか、分割の復旧時における処理など、さらに詳しい考察を加えています。

参考

E. Brewer, "Lessons from Giant-Scale Services," IEEE Internet Computing, July/Aug. 2001, pp. 46-55.
A. Fox et al., "Cluster-Based Scalable Network Services," Proc. 16th ACM Symp. Operating Systems Principles (SOSP 97), ACM, 1997, pp. 78-91.
A. Fox and E.A. Brewer, "Harvest, Yield and Scalable Tolerant Systems," Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pp. 174-178.
E. Brewer, "Towards Robust Distributed Systems," Proc. 19th Ann. ACM Symp.Principles of Distributed Computing (PODC 00), ACM, 2000, pp. 7-10; on-line resource.
B. Cooper et al., "PNUTS: Yahoo!’s Hosted Data Serving Platform," Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
J. Sobel, "Scaling Out," Facebook Engineering Notes, 20 Aug. 2008; on-line resource.
J. Kistler and M. Satyanarayanan, "Disconnected Operation in the Coda File System" ACM Trans. Computer Systems, Feb. 1992, pp. 3-25.
K. Birman, Q. Huang, and D. Freedman, "Overcoming the ‘D’ in CAP: Using Isis2 to Build Locally Responsive Cloud Services," Computer, Feb. 2011, pp. 50-58.
M. Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems," Proc. Symp. Operating Systems Design and Implementation (OSDI 06), Usenix, 2006, pp. 335-350.
J. Baker et al., "Megastore: Providing Scalable, Highly Available Storage for Interactive Services," Proc. 5th Biennial Conf. Innovative Data Systems Research (CIDR 11), ACM, 2011, pp. 223-234.
D. Abadi, "Problems with CAP, and Yahoo’s Little Known NoSQL System," DBMS Musings, blog, 23 Apr. 2010; on-line resource.