CAP Twelve Years Later: How the "Rules" Have Changed (2012)
December 23, 2023CAP定理は、データベースが一貫性 (Consistency), 可用性 (Availability), 分断耐性 (Partition Tolerance) から2つしか選択できない定理として知られる。 この定理は、Martin Kleppmannによって、その著書Designing Data-Intensive ApplicationsやA Critique of the CAP Theorem で批判されている。 CAP定理をなづけたBrewerは、CAP Twelve Years Later: How the “Rules” Have Changedで、2つを選択するという表現は誤解をまねく表現であると認め、現実的にはデータベースはネットワークの分断時に一貫性と可用性のトレードオフにさまられると主張した。 CAP定理の発表された12年後の今日では、分断時における一貫性と可用性の最適化に、各ノードの操作履歴を記録するversion verctorsやCommutative Replicated Data Types (CRDTs) を利用できる。
CAP定理の3性質の定義も誤解されやすい。 CAP定理の一貫性はデータの最新の値が常に1つに定まることである。 CAP定理の3性質を厳密に定義し証明をあたえたBrewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Webは、一貫性を線形化可能性とみなす。 また、ACIDの一貫性がトランザクション前後における複数のデータ間の整合性であり、CAPの一貫性が単一のデータに対する言及であることから、両者の一貫性の意味はちがう。
CAP定理が誤解をまねきやすい理由が3つあげられている。 まず、ネットワークの分断はまれで、分断のないときに一貫性や可用性を犠牲にする理由は乏しい。 次に、一貫性と可用性のトレードオフは個別の操作やデータに対して決められるので、データベースのすべてのデータや操作が同様のトレードオフである必要はない。 最後に、3つとも、あるかないかの二値ではなく段階のある性質であり、厳密にどの2つの性質が選ばれたのか明確にできないことがある。
ネットワークの段階的な性質に、分断と遅延を客観的に区別できないことがある。 デーベースは、分断とみなす遅延時間のしきい値を設定し、分断を検知したら分断を想定した操作に移り、ネットワークの回復を検知しなければならない。 回復後には、分断されていたノードごとの操作をマージする必要があり、version verctorsやCRDTsはマージの衝突、回避に応用される。