celloworldNavigate back to the homepage

分布式系统笔记:CAP定理

hidaris
March 8th, 2019 · 2 min read

Distributed systems for fun and profit 一书在开篇说到

Distributed programming is the art of solving the same problem that you can solve on a single computer using multiple computers.

分布式系统中各个节点的状态如何同步是一个难题,CAP 定理是这个问题相关的定理,也是很多分布式系统设计的理论基础。

CAP 定理是 Eric Brewer 于1998年发现,在2000年发表在 PODC,2002年被 Seth Gilbert 和 Nancy Lynch 证明。它指出在设计分布式系统时无法同时满足以下三个需求: 1. 一致性 (Consistency):每次读要么获得最新写入的数据,要么返回错误 2. 可用性 (Availability):每次请求都会返回一个非错误的响应,但是不保证获得的是最新写入的数据 3. 分区容错 (Partition Tolerance):任意数量的消息被节点间的网络丢弃或延迟,系统仍能继续运行

异步网络

在异步网络模型中,由于没有统一时钟,所有节点仅根据接收到的消息和本地的计算进行决策。

定理一:

在一个异步网络模型中,对于所有 fair executions(包括消息会丢失的),不可能实现一个满足以下属性的读写数据对象: 1. 可用性 2. 一致性

证明:

我们通过矛盾证明这点,假设存在一个算法 A 满足这些条件:一致性、可用性、分区容错。我们构造一个包含一次返回非一致结果的请求的 A 的执行。假设网络包含至少两个节点,那么它可以被分为不相交的非空集合:{G1,G2}。证明的基本思路是假设 G1 和 G2 之间的全部通讯消息都丢失。如果这时在 G1 上有一个写操作,接 G2 上有一个读操作,那么读操作只会返回 G1 写操作前的数据,而这点与一致性相矛盾。

推论一:

在一个异步网络模型中,不可能实现一个满足以下属性的读写数据对象: 1. 可用性,(对于所有 fair executions) 2. 一致性,(对于所有信息不会丢失的 fair executions)

证明:

主要问题是在异步网络模型中一个算法不能判断一个消息丢失与否或者是不是在传输通道中延迟。因此,如果在运算中不会丢失任何消息的前提下存在一个能够保证一致性的算法,那么该算法也能够在所有运算(消息可能丢失)情况下保证一致性。这将与定理一矛盾。

部分同步网络

尝试规避定理一的最显而易见的方法是意识到,在真实世界中,大部分网络并不是纯异步的。如果你允许网络中的每个节点有一个时钟,就有构建更强大网络的可能。

我们将讨论一个部分同步的网络模型,它所有的节点都有一个时钟,并且每个时钟都以相同的速率增长。然而,这些时钟并不是同步的,在同一时间,它们可能显示不同的值。事实上,时钟扮演计时器的角色:processes 可以用以衡量流逝了多少时间的本地状态变量。一个本地的计时器可以用来在某事件之后的确定间隔后调度另一个操作。进一步地,假设每一个消息要么在给定的时间 s 内到达,要么丢失。并且,所有的节点在给定时间 t 内处理完一个接收到的消息。

当任何消息都可能丢失时,即使在一个部分同步网络模型中,也不可能实现一个总是可靠,一致的数据对象。

定理二:

在一个部分同步网络模型中,对于所有 fair executions(包括消息会丢失的),不可能实现一个满足以下属性的读写数据对象: 1. 可用性 2. 一致性

证明:

这个证明和定理一的证很相似。 但是在部分同步模型中,类似与异步模型推论一的结论就不存在了,因为推论一的假设基于节点无法判断一个消息是否丢失。而在部分同步模型中,存在部分同步算法可以在所有消息传送正常的情况下返回一致性的数据,而仅仅在消息丢失时返回非一致性数据。对于读或写请求,节点发送一个消息给另一个节点,如果消息返回了,那么节点发送请求的数据;如果消息在给定的 2s+t 时间内没有返回,那么该节点断定消息丢失了,节点就可能返回一个不一致的请求数据。

CAP 定理明确了分布式系统所能实现系统的局限性,这三种性质俩俩组合会得到三种情况

  • CA (Consistency + Partition Tolerance): 这样的系统关注一致性和分区容错。它关注的是系统里大多数节点的一致性,只要系统里大多数节点的数据是一致的,少数节点在网络发送分区时数据没有更新到最新版本,只需要将这些节点的数据标记为不可以,就可以提供部分的可用性。典型的算法包括:Paxos和Quorum。典型的系统包括:MongoDB,HBase,Memcache。
  • AP (Availability + Partition Tolerance): 这样的系统关注可用性和分区容错。由于系统不保证数据一致性,因此数据可能会发送冲突,解决数据冲突就需要维护数据版本。典型的系统包括:Dynamo,Cassandra, RIAK,CouchDB。
  • CP (Consistency + Availability): CAP 理论提出就是针对分布式数据存储系统,在分布式环境中网络分区虽然是小概率事件,但是长期看是不可避免的,所以 P 这个属性是必须具备的。CA 系统只存在于单机环境,例如传统的关系型数据库 RDBMS(Oracle、MySQL)。

总结

CAP 指出:在某时刻如果满足 AP,分隔的节点同时对外服务但不能相互通信,将导致状态不一致,即不能满足 C;如果满足 CP,网络分区的情况下为达成 C,请求只能一直等待,即不满足 A;如果要满足 CA,在一定时间内要达到节点状态一致,要求不能出现网络分区,则不能满足 P。

CAP 理论的表述很好地服务了它的目的,即开阔设计者的思路,在多样化的取舍方案下设计出多样化的系统。在过去的十几年里确实涌现了不计其数的新系统,也随之在数据一致性和可用性的相对关系上产生了相当多的争论。“三选二”的公式一直存在着误导性,它会过分简单化各性质之间的相互关系。现在我们有必要辨析其中的细节。实际上只有“在分区存在的前提下呈现完美的数据一致性和可用性”这种很少见的情况是 CAP 理论不允许出现的。

虽然设计者仍然需要在分区的前提下对数据一致性和可用性做取舍,但具体如何处理分区和恢复一致性,这里面有不计其数的变通方案和灵活度。当代 CAP 实践应将目标定为针对具体的应用,在合理范围内最大化数据一致性和可用性的“合力”。这样的思路延伸为如何规划分区期间的操作和分区之后的恢复,从而启发设计者加深对 CAP 的认识,突破过去由于 CAP 理论的表述而产生的思维局限。

关于 P

Partition 字面意思是网络分区,即因网络因素将系统分隔为多个单独的部分,有人可能会说,网络分区的情况发生概率非常小啊,是不是不用考虑 P,保证 CA 就好[8]。要理解 P,我们看回 CAP 证明中 P 的定义:

In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another.

网络分区的情况符合该定义,网络丢包的情况也符合以上定义,另外节点宕机,其他节点发往宕机节点的包也将丢失,这种情况同样符合定义。现实情况下我们面对的是一个不可靠的网络、有一定概率宕机的设备,这两个因素都会导致 Partition,因而分布式系统实现中 P 是一个必须项,而不是可选项

P是否可以放弃

“三选二”的时候取 CA 而舍 P 是否合理?设计师可以选择不要分区吗?哪怕原来选了 CA,当分区出现的时候,你也只能回头重新在 C 和 A 之间再选一次。我们最好从概率的角度去理解:选择 CA 意味着我们假定,分区出现的可能性要比其他的系统性错误(如自然灾难、并发故障)低很多。

这种观点在实际中很有意义,因为某些故障组合可能导致同时丢掉 C 和 A,所以说 CAP 三个性质都是一个度的问题。实践中,大部分团体认为(位于单一地点的)数据中心内部是没有分区的,因此在单一数据中心之内可以选择 CA;CAP 理论出现之前,系统都默认这样的设计思路,包括传统数据库在内。然而就算可能性不高,单一数据中心完全有可能出现分区的情况,一旦出现就会动摇以 CA 为取向的设计基础。最后,考虑到跨区域时出现的高延迟,在数据一致性上让步来换取更好性能的做法相对比较常见。

CA并非二选一

P 是必选项,那3选2的选择题不就变成数据一致性(consistency)、服务可用性(availability)2选1?工程实践中一致性有不同程度,可用性也有不同等级,在保证分区容错性的前提下,放宽约束后可以兼顾一致性和可用性,两者不是非此即彼。

说明

目前笔者对分布式系统的理解还比较浅,这篇笔记可能有不少疏漏或错误,还请以原 paper 为主,我会在后续的学习中逐渐修正完善本文。

参考

  1. Seth Gilbert and Nancy Lynch, Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services (2002)
  2. brewer’s cap theory 详解
  3. CAP定理
  4. 分布式系统理论基础 - CAP
  5. CAP 理论十二年回顾:“规则”变了

More articles from hidaris

为 emacs lsp python 添加 virtualenv 支持

emacs lsp-mode 不支持 virtualenv,在此分享我的解决方案

November 4th, 2018 · 1 min read

The Expression Problem Revisited

The Expression Problem is a new name for an old problem. The goal is to define a datatype by cases, where one can add new cases to the datatype and new functions over the datatype, without recompiling existing code, and while retaining static type safety (e.g., no casts).

March 13th, 2016 · 1 min read
© 2016–2020 hidaris
Link to $https://twitter.com/zuodadaLink to $https://github.com/hidarisLink to $https://instagram.com/hidaris128