CAPと一貫性モデル

一貫性モデルは、レプリケートされたシステムが返す値についてどのような保証を与えるかを定義し、CAP定理は、ネットワーク分断下でそれらの保証のうちどれが可用性と共存できるかの境界を定めます。

Definition

一貫性モデルは、レプリケートされたデータストアとそのクライアントとの間の契約であり、並行する読み取りと書き込みの許容される結果を規定します。CAP定理は、ネットワーク分断が存在する場合、分散データストアが線形化可能性と可用性の両方を提供することはできないと述べています。

Scope

このトピックでは、正式な一貫性モデル（線形化可能性、逐次一貫性、因果一貫性、結果整合性）とそれらの強度による順序付け、CAP定理とその正確な記述と証明、および分断がない場合の遅延と一貫性のトレードオフも考慮に入れるPACELCなどの改良について扱います。これにより、レプリケートされたシステムの保証を特定し比較するための語彙が提供されます。

Core questions

• 線形化可能性、逐次一貫性、因果一貫性、結果整合性は強度においてどのように異なりますか？
• CAP定理は正確には何を禁じ、何を許容していますか？
• 分断がない場合、遅延の考慮事項は一貫性のトレードオフをどのように洗練させますか？

Key theories

線形化可能性と逐次一貫性

線形化可能性は、各操作が呼び出しから応答までの間のどこかの時点でアトミックに実行されたように見え、実時間と整合することを要求します。逐次一貫性は実時間要件を緩和し、各プロセスの順序を尊重する単一の合法的なインターリーブのみを要求します。

CAP定理

ギルバートとリンチは、レプリカ間でネットワークがメッセージをドロップする可能性がある場合、レプリケートされたデータストアが線形化可能性と可用性の両方を保証することはできず、分断時に選択を迫られることを証明しました。

PACELCの改良

PACELCは、分断がない場合でもシステムが遅延と一貫性をトレードオフすることに注目し、CAPを拡張します。したがって、設計は分断時と通常動作時の両方での挙動によって特徴付けられます。

Clinical relevance

すべての分散データベースとストレージサービスは一貫性モデルを宣言する必要があり、CAPとPACELCのトレードオフは、なぜ一部のシステムが可用性を優先し、他のシステムが一貫性を優先するのかを説明します。これらを理解することは、データインフラストラクチャを選択し運用する上で不可欠です。

History

ランポートは1979年に逐次一貫性を定義し、ハーリヒーとウィングは1990年に線形化可能性を形式化しました。ブリューワーは2000年にCAPトレードオフを提唱し、ギルバートとリンチは2002年にそれを証明しました。アバディによる2012年のPACELCの再構築は、分断だけでなく遅延も一貫性の選択を左右することを明らかにしました。

Debates

CAPはしばしば誤解されていますか？

CAPは「3つのうち2つを選ぶ」と要約されることが多いですが、正確な結果は分断時にのみ一貫性と可用性の選択を強制します。批評家は、この単純化が、PACELCによって捉えられた、より関連性の高い日常的な遅延と一貫性のトレードオフを曖昧にしていると主張しています。

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

CAPは、システムが一貫性、可用性、分断耐性のうち2つしか持てないという意味ですか？

厳密には違います。分断はネットワークの事実であり、設計上の選択肢ではないため、実際の決定は分断時にどうするかです。つまり、可用性を維持するために強い一貫性を犠牲にするか、一貫性を維持するために可用性を犠牲にするかです。分断がない場合、システムは一貫性と可用性の両方を備えることができます。