CAP和一致性模型

一致性模型定义了复制系统对读取返回值的保证，而CAP定理则限定了在网络分区下，哪些保证可以与可用性共存。

Definition

一致性模型是复制数据存储与其客户端之间的一项契约，规定了并发读写的允许结果；CAP定理指出，在网络分区存在的情况下，分布式数据存储不能同时提供线性一致性和可用性。

Scope

本主题涵盖了形式化的一致性模型——线性一致性、顺序一致性、因果一致性和最终一致性——以及它们按强度排序；CAP定理及其精确的表述和证明；以及PACELC等在没有分区的情况下也考虑延迟-一致性权衡的改进模型。它提供了指定和比较复制系统保证的词汇。

Core questions

• 线性一致性、顺序一致性、因果一致性和最终一致性在强度上有何不同？
• CAP定理究竟禁止了什么，又允许了什么？
• 在没有分区的情况下，延迟因素如何改进一致性权衡？

Key theories

线性一致性和顺序一致性

线性一致性要求每个操作在调用和响应之间的某个瞬间原子地生效，并与实时保持一致；顺序一致性放弃了实时要求，只要求存在一个单一的合法交错，且尊重每个进程的顺序。

CAP定理

Gilbert和Lynch证明，当网络可能在副本之间丢弃消息时，任何复制数据存储都无法同时保证线性一致性和可用性，这使得在分区期间必须做出选择。

PACELC改进

PACELC通过指出即使没有分区，系统也会在延迟和一致性之间进行权衡来扩展CAP，因此设计特点在于其在分区期间和正常操作中的行为。

Clinical relevance

每个分布式数据库和存储服务都必须声明一个一致性模型，而CAP和PACELC的权衡解释了为什么有些系统优先考虑可用性，而另一些系统则优先考虑一致性；理解它们对于选择和操作数据基础设施至关重要。

History

Lamport于1979年定义了顺序一致性，Herlihy和Wing于1990年形式化了线性一致性；Brewer于2000年提出了CAP权衡猜想，Gilbert和Lynch于2002年证明了它，Abadi在2012年通过PACELC的重新框架阐明了延迟，而不仅仅是分区，是驱动一致性选择的因素。

Debates

CAP是否经常被误解？

CAP经常被概括为“三选二”，但精确的结果只在分区期间强制进行一致性-可用性选择；批评者认为这种过度简化掩盖了PACELC所捕捉到的更相关的日常延迟-一致性权衡。

Key figures

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

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

CAP是否意味着一个系统只能拥有一致性、可用性和分区容错性中的两个？

不完全是。分区是网络的固有事实，而非设计选择，因此真正的决定是在分区期间如何做：牺牲强一致性以保持可用，或牺牲可用性以保持一致。当没有分区时，系统可以同时保持一致和可用。