CAP定理の進化系？PACELC定理とは
TL;DR
- CAP定理は分散システムにおける基本的な主張で、あるシステムでConsistency, Availability, Partition Torelanceをすべて同時に満たすことはできない、というもの。
- PACELC定理はCAP定理の拡張。分散システムにおいてまずNetwork Toleranceが発生した場合とそうでない場合で場合分けし、それぞれでのトレードオフを考えるもの
なお、本記事は System Design Guide for Software Professionals: Build scalable solutions – from fundamental concepts to cracking top tech company interviews に基づいています。(PRリンクです)
まだこの本は読み進めている最中ですが、システムデザイン全体の話から具体的なアルゴリズムの話まで幅広く紹介されていて、システムデザインの概要をつかむにはいい本だと思います。
分散システムにおける問題
分散システム(Distributed System)とは、ものすごく大雑把に言えば複数のコンポーネント、プロセス、ノードが協調的に動作してサービスを提供するシステムと言えます。
古くからあるWeb3層なんて考えも、分散システムの走りと言えるかもしれません。昨今クラウドコンピューティングの台頭もあり、複数のシステムを組み合わせてサービスを提供することはよくあります。
そんな分散システムですが、いざ実装しようとすると様々な問題に直面します。複数のコンポーネントが協調的に動作するといいましたが、それが本質的に難しいことです。なぜならハードウェアは壊れます。あるいはソフトウェアではバグが発生します。もっというならヒューマンエラーも起きえます。例えばRPCがタイムアウトしたとして、相手が今壊れていて動かないのか、あるいは動いているけど何らかの理由でackが遅れているだけなのか、正確に知ることは極めて難しいです。
特に分散システムで問題になりがちなのは Network Partition と呼ばれる問題です。なぜなら、分散システムはネットワークを通じて強調動作することが多いので、途中経路のネットワークが分断されてしまったり、輻輳が発生して正常に通信ができない場合、システム全体に問題を及ぼす可能性があります。
CAP定理
CAP定理とは、分散システムにおいて障害が発生したときのトレードオフに関する主張です。CAPとは、Consistency, Availability, Partition toleranceの頭文字をとったもので、分散システムにおいて何らかの障害が発生した場合、このうち全てを満たすことは不可能なので、システムとしてはどれか2つのみを優先する、逆に言うならどれか一つは諦めざるを得ない、というものです。
例えばCAPのうちAP、つまりAvailabilityとPartition toleranceを優先する場合を考えます。この場合のシステムにおいて何らかの分断が発生したとしても、システムの提供するサービスは引き続き動作するが、Consistencyは担保されていない（つまり、一時的に一貫性がない状態が発生する。例えば、システムに対してアクセスしたクライアントごとに異なる結果を返す、など）状態が発生したりします。
もしくは、CP (ConsistencyとPartition tolerance)を優先する場合を考えます。この場合、すべてのコンポーネントが一貫したデータを持っていて、複数のクライアントからの要求に対して一貫した結果を返すことが期待されるが、システムのサービス提供時間が短くなる（つまり、一貫性が保たれなくなるくらいなら、システム全体を止めてしまう、など）ことがあります。
CAP定理のベン図。System Design Guide for Software Professionals: Build scalable solutionsより引用
これらはどちらがいいというものではなく、そのシステムに求める要求に応じて使い分けましょう、というのがCAP定理の言わんとすることかと思います。例えば銀行の預金システムみたいな厳密な一貫性が求められるシステムであれば、Availabilityを犠牲にしてでも一貫性を担保したい場合はあるでしょう。
PACELC定理
CAP定理を拡張した定理がPACELC定理です。PACELCは、ネットワーク分断があった場合とそうでない場合とで、トレードオフの考え方が違うという主張です。PACELCはそれぞれ以下の頭文字です。
- Partition tolerance: 分断への耐性を示します。
- Availability: 障害時においてもリクエストに対してどれだけレスポンスを返せるかの能力を示します。
- Consistency: 障害時において、複数のノードがどれだけ一貫した状態を共有しているかの能力を示します。
- Else: "もしくは" という意味です。PACELCでは、ネットワーク分断があった場合とそうでない場合とでトレードオフの考え方が違うという主張なので、この文字が入っています。
- Latency: あるリクエストからのレスポンスが返ってくるまでの時間を表します。
- Consistency Level: Consistencyという考え方は先のものと一緒ですが、その能力をレベル分けしたものです。
PACELC定理はCAP定理と比べてより細かい視点を与えてくれます。分断があった場合はAvailabilityかConsistencyを選びましょう、というのはCAP定理と一緒ですが、分断がない場合は、LatencyとConsistency (Level)のトレードオフだと主張します。
分断がない場合をもう少しかみ砕くと、Latencyを最小化したい場合、Consistencyを少し妥協する(つまり、Strong Consistencyを諦め、Eventual Consistencyにする)必要があるが、Consistencyが妥協できない場合はLatencyが少し伸びる可能性がある、と考えることができます。
この主張は割と直感的です。例えば3冗長でデータのレプリカを持つ分散システムを考えます。Strong Consistencyを担保したい場合、ナイーブに実装するなら、全てのデータのレプリカが確実に分散システムを構成する各ノードのうち、3つにデータが書かれたことを確認したうえでレスポンスをする必要があるために、Latencyは伸びる可能性が高いです。(勿論、現代的なシステムだとこのような場合はRaftなどを利用します。本記事で参照している本でも、RaftやPaxosについて触れています)
PACELC定理。System Design Guide for Software Professionals: Build scalable solutionsより引用
終わりに
昨今のシステム開発においては分散システムの考え方を取り入れないことはなかなかないでしょう。CAP定理やPACELC定理といった主張を知り、システムデザインをする際のトレードオフの整理に使いたいですね。
Discussion