CAP定理はブリュワーの定理とも呼ばれ、分散コンピュータシステムのマシン間の情報複製に関する定理。ウェブサービスを想定して作られた定理。

定義

ノード間のデータ複製において、同時に次の3つの保証を提供することはできない^[1][2]。

• 一貫性 (Consistency)

  すべてのデータ読み込みにおいて、最新の書き込みデータもしくはエラーのどちらかを受け取る。

• 可用性 (Availability)

  ノード障害により生存ノードの機能性は損なわれない。つまり、ダウンしていないノードが常に応答を返す。単一障害点が存在しないことが必要。

• 分断耐性 (Partition-tolerance)

  システムは任意の通信障害などによるメッセージ損失に対し、継続して動作を行う。通信可能なサーバーが複数のグループに分断されるケース（ネットワーク分断）を指し、1つのハブに全てのサーバーがつながっている場合は、これは発生しない。ただし、そのようなネットワーク設計は単一障害点をもつことになり、可用性が成立しない。RDBではそもそもデータベースを分割しないので、このような障害とは無縁である。

この定理によると、分散システムはこの3つの保証のうち、同時に2つの保証を満たすことはできるが、同時に全てを満たすことはできない^[3]。単一障害点があれば、ネットワーク分断が発生した際にシステムがバラバラに分裂しても、そこを基準に一貫した応答ができる(分断耐性+一貫性)が、可用性が成立しなくなる。

個別例

歴史

この定理は、インクトミの創業者でもあり、カリフォルニア大学バークレー校の計算機科学の教授でもあるエリック・ブリュワーが2000年の Symposium on Principles of Distributed Computing (PODC) で提案（数学的な用語では予想）したのが始まりである^[4]。

2002年にMITのSeth Gilbertとナンシー・リンチがブリュワーの予想の厳密な証明を提出し、定理として確立した^[1]。

参照

1. 1 2 Nancy Lynch and Seth Gilbert, conjecture and the feasibility of consistent, available, partition-tolerant web services”, ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.
2. ↑ "Brewer's CAP Theorem", julianbrowne.com, Retrieved 02-Mar-2010
3. ↑ "Brewers CAP theorem on distributed systems", royans.net
4. ↑ Eric Brewer, "Towards Robust Distributed Systems"

関連項目

• 結果整合性
• ACID_(コンピュータ科学)