CAP定理在分布式系统设计中的最新应用

本文翻译自国外InfoQ和计算机杂志上一篇2012年旧文，本文就有关数据同步进行了讨论，特别关注业务事务的不变性与一致性如何在分布式系统中巧妙保证，探讨了长时间运行的事务的补偿机制。这些对分布式系统设计都有很大帮助。

原文大意如下：

CAP理论认为，任何联网的共享数据系统只能在三个属性中的两个。但是，通过明确处理分区，设计人员可以优化一致性和可用性，从而实现三者之间的某种权衡。

自CAP定理推出以来的十年中，设计师和研究人员已经使用（有时滥用）CAP理论作为探索各种新型分布式系统的依据。NoSQL运动也将其作为反对传统数据库的论据。

CAP定理指出，任何网络共享数据系统最多可以有三个理想的属性中的两个：

1.一致性（C）相当于拥有一份最新的数据;
2.该数据的高可用性（A）（用于更新）;
3.容忍网络分区（P）。

（banq注，关于CAP定理所有你不知道的中CAP解释更加易懂：

1.一致性。每一次读取都会让你得到最近的写入结果
2.可用性。每个节点（如果没有失败）总是能执行查询（读取和写入）操作
3.分区容忍。即使节点之间的连接关闭，其他两个属性也会得到保证。

分区P基本可以理解为出现网络故障导致的通讯中断，形成两个以上的各自为政的孤岛服务器节点。
）

CAP的这种表达是服务于它的目的，这是为了让设计师的思想敞开，上升到更广泛的系统中进行权衡; 的确，在过去的十年中，已经出现了大量的新系统，以及关于一致性和可用性的相对优点的争论。“三分之二”的表述却是有误导性的，因为它往往过分简化了属性之间的紧张关系。而这些细微差别却很重要。CAP仅禁止设计空间的一小部分：在分区存下的完美可用性和完美一致性。这种情况是很少能实现的。

虽然设计师仍然需要在分区存在情况下在一致性和可用性之间进行选择，但是处理分区和从分区中恢复的灵活性有着令人难以置信的好处。现代CAP目标应该是最大限度地提高一致性和可用性的组合，这对于特定的应用是有意义的。这种方法结合了分区发生和事后恢复的两种方式，从而帮助设计人员考虑CAP，超越其历史上的限制。

为什么“2/3”是误导

理解CAP最简单的方法是考虑分区两侧的两个节点。允许其中任意一个节点更新状态将导致两个节点变得不一致，从而放弃C，同样，如果选择是保持一致性，分区中任意一侧必须是一种不可用的状态，从而放弃A. 只有当节点一直完美通讯时才有可能保持两者的一致性和可用性，这又丧失P。因此普遍认为，对于广域系统来说，设计者不能放弃P，因此在C和A之间有一个困难的选择。从某种意义上说，NoSQL运动是关于首先关注可用性和其次才是一致性的选择; 遵循ACID属性（原子性，一致性，隔离性和持久性）的数据库则正好相反。

在20世纪90年代中期，我和我的同事们正在构建各种基于群集的广域系统（本质上是早期的云计算），包括搜索引擎，代理缓存和内容分发系统。由于收入目标和合同规范，系统可用性非常重要，所以我们发现自己经常选择通过采用缓存或日志记录更新等策略来优化可用性，实现之后的冲突解决校验。虽然这些策略确实提高了可用性，但是增加的代价是一致性降低。

这个一致性与可用性的争论的第一个版本表现为ACID与BASE，BASE在当时并没有得到很好的接受，主要是因为人们喜欢ACID的特性而不愿放弃。CAP定理的目的是证明探索更广阔的设计空间，因此是一种“2/3”的设计。

CAP定理首先出现在1998年秋季，1999年出版，并在2000年的“分布式计算原理专题讨论会”上发表了主题演讲 ，从而证明了这一点。
（这个定理被Eric Brewer在2000年分布式计算原理研讨会上提出。2002年，来自麻省理工学院的Seth Gilbert和Nancy Lynch发表了一个Brewer猜想的正式证明，使其成为了一个定理。根据Brewer的说法，他只是想让社区开始谈论这个问题，但他的话最终被解释为一个定理了。）

但是“2/3”的观点在几个方面有误导性。

首先，因为当分区很少时，或者当系统没有被分区时就没有理由放弃C或A. 其次，C和A之间的选择可以在相同的系统中以非常细的粒度出现多次; 子系统不仅可以做出不同的选择，而且可以根据操作甚至特定的数据或用户来选择。
最后，这三个属性是连续的，不是像二进制那样不是0就是1。可用性显然是从0到100％连续的，同时也有很多级别的一致性，甚至分区也有细微差别，包括系统内部是否存在分区的高低程度。

探索这些细微差别需要推动传统处理分区的方式，这是基本的挑战。因为在分区很少出现情况下，CAP应该在大多数情况下可以允许完美的C和A，但是当分区存在或被感知时，检测分区并明确说明分区的策略是有序的。这个策略应该有三个步骤：检测分区，进入明确的分区模式，可以限制一些操作，并启动恢复过程来恢复一致性，并弥补分区过程中犯的错误。

ACID，BASE和CAP

ACID和BASE代表了在一致性 - 可用性两点之间进行选择的设计哲学。ACID事务属性注重一致性，是关系数据库的传统方法。我和我的同事在20世纪90年代后期创建了BASE，以捕捉新兴的高可用性设计方法，并明确选择和范围。包括云在内的现代大规模广域系统都使用了两种方法的组合。

尽管这两个术语都比较精确，BASE这个缩写代表：基本可用，软状态，最终一致。软状态和最终一致性是存在分区的情况下能够很好地工作一种技术手段，这种手段能够提高可用性。

CAP和ACID之间的关系比较复杂，常常被误解，部分原因是ACID中的C和A虽然和CAP中C和A是相同的字母，但是表达不同的概念，选择可用性只会影响一些ACID保证。四个ACID属性是：

原子（A）。所有的系统都受益于原子操作。当我们将焦点放在可用性时，分区的两边应该仍然使用原子操作。而且，更高级别的原子操作（ACID暗示的那种）实际上简化了分区发生故障以后的恢复过程。

一致性（C）。在ACID中，C意味着事务预处理所有的数据库规则，例如唯一键。相比之下，CAP中的C仅指单一拷贝一致性，这是ACID一致性的严格子集。ACID的一致性也无法在分区之间保持。分区恢复将需要恢复ACID一致性。更一般地说，在分区中保持不变性也许是不可能的，因此需要仔细考虑哪些操作是不允许的，以及如何在恢复过程中恢复不变性。

隔离（I）。隔离性是CAP定理的核心：如果系统需要ACID隔离，则在分区过程中最多可以在一侧进行操作。一般而言，可序列化需要通信，这样就会面临跨分区的失败情况。在分区恢复过程中，通过补偿机制实现跨越分区的相对弱的正确性是可行的。

耐久性（D）。与原子性一样，尽管开发人员可能选择通过软状态（以BASE的形式）以避免它，因为其开销昂贵，但是没有理由禁止选择持久性。一个微妙之处是，在分区恢复过程中，可以反转在操作过程中在不知不觉中违反了不变的持久操作。然而，在恢复的时候，通过双方比较长的历史资料对比可以发现和纠正违反不变性的操作。一般来说，在分区的每一边运行ACID事务能够使得分区恢复变得更容易，并且使用一个框架来实现补偿事务有助于分区恢复。

Cap-latency连接

在其经典的解释中，CAP定理忽略了延迟，尽管在实践中，延迟和分区是深度相关的。在操作上，CAP的本质是，在发生了分区(网络故障)以后，有一段timeout时间，在这个时间内程序必须做出基本的决定：

1.取消操作，从而降低可用性，或

2.继续进行操作，从而导致风险不一致。

例如重试通信可以实现一致性，比如通过Paxos或两阶段提交2PC，这些都是只是延迟了决策。程序在某个时刻总是必须做出决定; 无限期地重试通信本质上是选择C而不是A。

因此，实际上，一个分区是通信的一段时间范围。在一段时间范围内未能达到一致意味着存在一个分区，因此这个操作必须在C和A之间进行选择。这些概念反映了关于延迟的核心设计问题：双方如果没有沟通通讯情况下会继续运行前进吗？

这种务实的观点引起了一些重要的后果。首先是没有分区的全局概念，因为一些节点可能检测到一个分区，而另一些节点可能不会。第二个结果是节点可以检测分区并进入分区模式，这是优化C和A的核心部分。

最后，这个观点意味着设计者可以根据目标响应时间故意设定时间范围; 边界更紧的系统可能会更频繁地进入分区模式，有时网络只是缓慢的，而不是实际的分区。

有时为了避免在大范围内保持一致性的高延迟，放弃强C是有意义的。雅虎的PNUTS系统通过异步实现维护远程副本同步而导致不一致。但是，它在本地机器实现主节点，从而减少延迟。这个策略在实践中运行良好，因为用户可据根据用户（正常）地理位置实现自然分区。理想情况下，每个用户是最靠近主数据的。

Facebook使用相反的策略：主数据始终在一个位置，所以远程用户通常有一个更接近但可能是陈旧的副本。但是，当用户更新其页面时，即使有更长的延迟时间，更新也会直接写入主数据节点。20秒后，用户会看到到最近的数据副本，在这个时候数据应该是反映最新数据。

CAP混乱

CAP定理的各个方面经常被误解，特别是可用性和一致性的范围，这可能会导致不希望的结果。如果用户根本无法访问服务，除非部分服务在客户端上运行，否则C和A之间没有选择。这种通常被称为断线操作或脱机模式,这种例外情况变得越来越重要。某些HTML5功能（特别是客户端持久性存储）使未连接的操作更容易。这些系统通常选择A而不是C，因此必须需要长时间的分区恢复（以保证一致性）。

一致性的范围反映了这样的想法：在某个边界内，状态是一致的，但是在这个边界之外就无法保证。例如，在主分区内，可以确保完整的一致性和可用性，而在分区之外，服务不可用。Paxos和原子多播系统通常符合这种情况。在Google中，主分区通常驻留在一个数据中心内;而Paxos被广泛用于确保全球范围内实现共识，如Chubby， 和高度可用的持久存储如Megastore。

独立的，自洽的子集可以在分区的情况下自行运行，尽管不能确保全局的不变性。例如，对于设计人员在节点间预分配数据的分片（sharding），很有可能每个分片在分区故障发生过程中都会持续独立运行。相反，如果相关状态被跨分区划分，或者全局不变量是非常必要时，那么充其量只有一方可以继续保持运行，最坏的情况是都无法继续运行。

选择一致性和可用性（CA）作为“2/3”是否合理？正如一些研究人员指出的那样，精确地说放弃P的意思是不够清晰的。设计师是否可以选择不分区呢？如果选择是CA，然后才是分区？最好从概率上考虑：选择CA意味着分区（网络故障）的概率远小于其他系统故障的概率如灾难或多个同时发生的故障。

这样的观点是有道理的，因为真实的系统会在一些失败都下失去了C和A，所以这三个属性都是程度的问题。在实践中，大多数集群组都假定在一个数据中心（单个站点）内没有分区，因此在单个站点内可以设计CA; 这样的设计，包括传统的数据库，都是CAP之前的默认选择。考虑到全球地区的高延迟，为了获得更好的性能，在大范围内放弃完美的一致性是相对常见的。

CAP混淆的另一个方面是丧失一致性的隐藏成本，这是需要掌握系统的不变性。一致性系统的微妙之处在于即使设计者不知道它们是什么，不变性也会保持不变。因此，广泛的合理的不变性将工作得很好。相反，当设计者选择A时，则需要在分区之后恢复不变性，因此必须对所有不变性都是明确掌握的，这是既具有挑战性又容易出错的。在微观CPU核编程方面，类似相同的并发更新问题，多线程编程比顺序编程更难一样。

管理分区

设计师面临的挑战是减轻分区(网络故障)对一致性和可用性的影响。关键的想法是非常明确地管理分区(网络故障)，不仅包括检测，还包括一个特定的恢复过程和对一个分区中可能违反的所有不变性的总结。这种管理方法有三个步骤：

1.检测分区的开始，
2.进入明确的分区模式，可能会限制一些操作
3.通信恢复时启动分区恢复。

最后一步旨在恢复一致性，并补偿程序在分区时各自运行犯的错误（数据不一致）。

正常情况下的操作是一系列的原子操作，因此分区总是在正常操作之间开始。系统超时后，检测到分区，检测端进入分区模式。如果确实存在分区，则双方都进入此模式，但也可以进行单向分区。在这种情况下，另一方根据需要进行通信，或者该方正确响应或不需要进行通信; 无论如何，操作应保持一致。但是由于检测端操作不一致，必须进入分区模式。使用法定数量选取的系统就是这种单向分区的一个例子。一方区域如果有符合法定数量的节点(比如共3个节点，有两个节点在一个区域就是符合法定数量)则可以继续，但另一方不能。支持断开操作的系统显然具有分区模式的概念，

一旦系统进入分区模式，两种策略是可能的。首先是限制一些操作，从而降低可用性。其次是记录有关在分区恢复过程中将有帮助的操作的额外信息。继续尝试通信将使系统能够识别分区何时结束。

哪些操作在发生分区时应该继续进行？

决定限制哪些操作主要取决于系统必须维护的不变性。给定一个不变性集合，设计者必须决定是否在分区模式下保持一个特定的不变性，或者有意在恢复过程中恢复它。例如，对于表中的键必须是唯一的这种不变性约束，设计人员通常决定冒风险违背这个不变性，并允许在分区中使用重复相同键。重复键很容易在恢复过程中检测到，假设可以合并，设计人员可以很容易地恢复全局的不变性（全局键的唯一性约束）。

然而，对于在分区中必须保持的不变性，设计者必须禁止或修改可能违反它的一些操作。（一般情况下，没有办法预知操作是否实际上将违反不变性，因为对方的状态并不可知。）一些外部化的活动，如信用卡充值，属于这种情况。在这种情况下，对付办法是记录下意图(用户操作意图，如命令/事件等)并在恢复后执行。这种情况通常属于工作流的一部分，比如有明确的订单处理状态的，在分区结束之前推迟操作几乎没有什么坏处。设计师以一种用户看不到的方式放弃了A。用户只知道他们下了订单，系统稍后会执行。

更一般地说，分区模式引起了用户界面体验的挑战，即用户传达任务是正在进行但没有完成。研究人员已经详细探讨了这个问题，对于断开连接的操作，这只是一个很长的分区。例如，Bayou的日历应用程序以不同的颜色显示潜在的不一致（暂定）条目。这样的情况在工作流程应用程序（如使用电子邮件通知的商务应用程序）和离线模式的云服务（例如Google Docs）中都会定期显现。

关注明确的原子操作而不仅仅是读写操作的一个原因是：分析高级操作对不变性的影响要容易得多。本质上，设计者必须建立一个表格，查看所有操作和所有不变性规则的交叉乘积，并为每个条目决定操作是否违反不变性约束。如果是这样，设计师必须决定是否禁止，推迟或修改操作。在实践中，这些决定还可以取决于已知状态等。例如，在存放某些数据的家庭节点的系统中，通常可以在家庭节点上进行5个操作，但是不能在其他节点上进行。

跟踪双方操作历史的最好方法是使用版本向量( version vectors)，它捕获操作之间的因果关系。向量的元素是一对（节点，逻辑时间），每个已更新对象的节点和最后一次更新的时间都有一个条目。如果一个对象有A和B的两个操作版本，如果A的时间大于或等于B，并且A的时间中至少有一次更大(时间数值是不断增大的)，则A比B新。

如果无法对版本向量排序，则更新是并发的，可能不一致。因此，根据双方的版本向量历史资料，系统可以容易地知道哪些操作已经按照已知的顺序执行，哪些操作是同时执行的。最近的研究证明，如果设计者选择关注可用性，那么这种因果一致性通常有最好的结果。

分区恢复

在某个时候，通信恢复，分区结束。在分区过程中，每一边都是可用的，各自都运行了一些操作，其中因为分区推迟了一些操作，并且违反了一些不变性约束。此时，系统知道双方的当前状态和历史操作记录，因为它在分区模式下保持了仔细的历史操作事件日志。这种情况下当前状态不如历史事件日志有用，系统可以从中推断出哪些操作实际上违反了不变性，哪些结果已经无法收回，包括发送给用户的响应。设计师必须在恢复过程中解决两个难题：

1.双方的状态必须保持一致
2.必须对分区模式下的错误进行补偿(让双方状态一致性，符合全局不变性约束)。

更容易修复当前状态的办法是：从分区时的状态开始，以某种方式向前滚动两组操作，从而一直保持两边一致的状态，。Bayou通过将数据库回滚到正确的时间来显式执行此操作，并以明确的，确定的顺序重播全套操作，以使所有节点达到相同的状态。类似地，源代码控制系统，如并行版本系统（CVS）从共享一致点和前滚更新开始合并分支（banq注：事件溯源也属于这种，区块链也是）。

大多数系统不能总是合并冲突。例如，CVS偶尔会出现用户必须手动解决的冲突，而具有脱机模式的wiki系统通常会在生成的文档中留下需要手动编辑的冲突。

相反，一些系统总是可以通过选择某些操作来合并冲突。一个恰当的例子就是Google文档中的文本编辑，它限制了应用样式和添加或删除文本等的操作。因此，虽然解决冲突在一般意义上是不可解决的，但实际上，设计者可以选择在分区过程中限制某些操作的使用，以便系统在恢复过程中自动合并状态。推迟具有风险的操作(banq注：所谓风险是可能违背不变性约束的操作，或在分区的情况下干脆停止写操作。)是一个相对简单的实施办法。

市面上通用框架一般是使用交换操作（commutative operations）实现状态自动状态收敛一致。系统连接历史操作日志，按照某种顺序排序，然后执行它们。交换性意味着能够将操作重新排列为以全局顺序为优先的顺序。不幸的是，仅使用交换操作比看起来更难; 例如，加法是可交换的，但是边界检查则不是（例如零余额）。

马克·夏皮罗（Marc Shapiro）及其同事在INRIA 18,19最近的工作大大改善了交换操作在状态融合中的应用。该团队开发了可交换的复制数据类型（CRDT），这是一类在分区之后可证明地收敛的数据结构，并描述了如何使用这些结构：

1.确保分区过程中的所有操作都是可交换的，或者
2.在格上表示值，并确保分区期间的所有操作相对于该格是单调递增的。

后一种方法通过移动到每一边的最大值来收敛状态。这是一个正规化formalization，亚马逊在其购物车中就是这么做的，分区之后，收敛值是两个两个购物车的联盟，这个联盟是一个单调集合操作。选择这种方案的结果是被删除的项目可能会重新出现。

但是，CRDT也可以实现添加和删除项目的分区容忍性。这种方法的本质是保持两套数据集：每套都有添加和删除的项目，不同的是集合的成员。每个简化集合进行收敛，因此差异化也是如此进行。在某些时候，系统可以简单地通过从两个集合中移除走已删除的项目来进行清理。但是，这种清理通常只有在系统没有分区的情况下才有可能。换句话说，设计者必须在分区期间禁止或推迟某些操作，但是这些操作不会限制敏感的可用性。因此，通过CRDT来实现状态，设计者可以选择A，并且在分区之后仍然保证状态自动收敛。