CAP定理と一貫性モデル

CAP定理は、ネットワーク分断に直面した分散データストアが、一貫性または可用性のいずれかを犠牲にしなければならないと述べており、一貫性モデルは、システムが更新の可視性と順序付けに関してどのような保証を提供するのかを正確に規定します。

Definition

CAP定理は、ネットワーク化された共有データシステムが、一貫性、可用性、および分断耐性のうち、同時に最大2つまでしか保証できないと主張します。一貫性モデルは、アプリケーションがレプリカ全体での読み取りと書き込みの順序と可視性について何を観察できるかを指定する契約です。

Scope

このトピックでは、CAP定理とその形式化、ネットワーク分断時にのみ真のトレードオフが生じるという実践的な解釈、およびその結果としてのPACELCの洗練について説明します。また、強力な（線形化可能な）一貫性から因果一貫性、最終一貫性までの幅広い一貫性モデルと、ACIDとは対照的なBASEスタイルについても取り上げます。これらのモデルがレプリケートされたデータストアの設計をどのように導くかについても扱います。強力な一貫性を実装するために使用される合意プロトコルとコミットプロトコルは、分散データベースの項目で扱われるため、ここでは除外します。

Core questions

• CAPにおける一貫性、可用性、分断耐性とは具体的に何を意味するのか？
• 一貫性と可用性の間の真の選択が分断時にのみ強制されるのはなぜか？
• 強力な一貫性、因果一貫性、最終一貫性は、その保証においてどのように異なるのか？
• 最終一貫性は何を約束し、何を約束しないのか？
• BASEの哲学はACIDとどのように対照的か？

Key concepts

• 一貫性、可用性、分断耐性
• ネットワーク分断
• 線形化可能性 / 強力な一貫性
• 因果一貫性
• 最終一貫性
• PACELC
• BASE対ACID
• 競合解決

Key theories

CAP定理

ギルバートとリンチによって形式化されたCAPは、ネットワークが分断された場合、レプリケートされたストアが、古くなったデータを返すこと（可用性）と、単一の一貫した値を維持するためにサービスを拒否すること（一貫性）のいずれかを選択しなければならないことを示します。実際のネットワークでは、分断耐性はオプションではありません。

一貫性のスペクトラム

一貫性モデルは、読み取りが常に最新の書き込みを反映する強力な（線形化可能な）一貫性から、因果関係の順序を保持する因果一貫性、そして新しい書き込みがない場合にレプリカが時間とともに収束する最終一貫性まで多岐にわたります。

BASE対ACID

高可用性システムは、しばしばBASEスタイル（基本的に利用可能、ソフトステート、最終的に一貫性）を採用します。これは、分断時や大規模な状況下でも応答性を維持するために、強力なACID保証を意図的に緩和するものです。

Clinical relevance

CAPと一貫性モデルは、分散データシステムにおける中心的な設計選択を枠組み化します。それは、ネットワーク障害発生時に、ストアが常に回答すること（可用性）を優先するか、常に正しく回答すること（一貫性）を優先するかというものであり、この決定は、すべてのグローバル分散アプリケーションの動作と保証を形成します。

History

エリック・ブリュワーは2000年頃にCAPのトレードオフを提唱し、ギルバートとリンチが2002年にそれを正式に証明しました。AmazonのDynamo（2007年）とフォーゲルスの2009年のエッセイは、実践における最終一貫性を普及させました。ブリュワーの2012年の回顧録は、CAPが完全な一貫性と可用性を禁止するのは分断時のみであることを明確にし、PACELCの定式化は後に、分断がない場合のレイテンシと一貫性のトレードオフを追加しました。

Debates

一貫性と可用性のトレードオフはどれほど根本的なものか

初期の解釈では、CAPは一貫性と可用性の間で永続的な選択を強制するものと見なされていました。しかし、ブリュワーの回顧録を含む後の分析では、トレードオフは分断時にのみ発生し、それ以外の場合にはシステムは概ね一貫性と可用性の両方を提供できると主張されており、CAPが設計をどの程度厳密に制約するかという見方が再構築されています。

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Werner Vogels

Seminal works

• gilbert2002
• brewer2012
• vogels2009

Frequently asked questions

CAPは3つの特性のうち2つしか持てないという意味ですか？

「2つを選ぶ」という一般的な表現は誤解を招きます。分散システムにおいて分断耐性は実際にはオプションではないため、真の選択は一貫性と可用性の間にあり、その選択は分断が実際に発生している間にのみ行われる必要があります。ネットワークが健全な場合、システムは一貫性と可用性の両方を提供できます。

最終一貫性は具体的に何を保証しますか？

最終一貫性は、データ項目に新しい更新が行われない場合、すべてのレプリカが最終的に同じ値に収束することを保証します。いつ収束するか、また読み取りが最新の書き込みを反映するかどうかは保証されません。したがって、最終一貫性を使用するアプリケーションは、一時的に古い読み取りや競合する読み取りを許容し、多くの場合、競合解決を自ら処理する必要があります。