読者です 読者をやめる 読者になる 読者になる

脳汁portal

アメリカ在住(だった)新米エンジニアがその日学んだIT知識を書き綴るブログ

CAP定理

nosql

CAP定理

CAP定理はブリュワーの定理とも呼ばれ、分散コンピュータシステムのマシン間の情報複製に関する定理。ウェブサービスを想定して作られた定理。
ノード間のデータ複製において、同時に次の3つの保証を提供することはできない。

一貫性 (Consistency)

全てのノードにおいて同時に同じデータが見えなければならない。

可用性 (Availability)

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

分断耐性 (Partition-tolerance)

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

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


組み合わせ

f:id:portaltan:20151013140256p:plain

可用性+分断耐性(AP型)

  • ネットワーク分断が発生しても、全てのノードがリクエストを受理し続ける
  • 結果として更新前の古いデータを読み出してしまったり、分断されたグループ間でデータに相違が生じる可能性がある
  • システム全体としての整合性を犠牲にする代わりに可溶性を保つ
  • 一定時間以内に一貫性を成立させるシステム(結果整合性; eventually consistent)を用いることが多い
  • 3種の中ではこの方式が最も障害に強い
採用しているプロダクト
    • Dynamo
    • Cassandra
    • CouchDB
    • Voldemort
    • Tokyo Cabinet
    • Riak
    • ROMA

一貫性+可用性(CA型)

  • ネットワーク分断が発生した際は、片方を切り捨てる
  • Amazon Relational Database Service の Multi-AZ 配備もこれに該当
採用しているプロダクト

一貫性+分断耐性(CP型)

  • ネットワーク分断が発生した場合、どれか1つのグループのみでリクエストを受理し、残りのグループは参照も更新もできないようにする
  • 一部のグループの可用性を犠牲にする替わりにシステム全体として整合性を保つ
採用しているプロダクト


まとめ

  • RDBはAC
  • NoSQLはほとんどCPとAP
    • ビッグデータを扱うことが多いため、複数nodesで構成される分散システムとなることに起因する
    • その上で整合性を重視するか可用性を重視するかを選ぶ