[转] CAP定理的证明

CAP介绍

在理论计算机科学中,CAP定理(CAP theorem),又被称作布鲁尔定理(Brewer’s theorem),它指出对于一个分布式计算系统来说,不可能同时满足以下三点:

  • 一致性(Consistency) (等同于所有节点访问同一份最新的数据副本)
  • 可用性(Availability)(每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据)
  • 分区容错性(Partition tolerance)(以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择)

对于分布式系统来讲,避免不了分区状态和分区恢复状态,一旦进入,我们必须在C和A之间做出妥协,这个妥协也不是说你只选择C而完全不考虑A,可以在CA的实现比例上进行权衡,比如主A辅C,实现基本可用,最终一致。BASE理论就是用来解决这个问题。

BASE理论

BASE 是 Basically Available(基本可用)、Soft state(软状态)和 Eventually consistent (最终一致性)三个短语的缩写,是对 CAP 中 AP 的一个扩展。
基本可用:分布式系统在出现故障时,允许损失部分可用功能,保证核心功能可用。
软状态:允许系统中存在中间状态,这个状态不影响系统可用性,这里指的是 CAP 中的不一致。
最终一致:最终一致是指经过一段时间后,所有节点数据都将会达到一致。

BASE 解决了 CAP 中理论没有网络延迟,在 BASE 中用软状态和最终一致,保证了延迟后的一致性。
BASE 和 ACID 是相反的,它完全不同于 ACID 的强一致性模型,而是通过牺牲强一致性来获得可用性,并允许数据在一段时间内是不一致的,但最终达到一致状态。

BASE理论的意义在于,我们不必在A或C中做出选择,可以实现部分的A和C

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

定理一:在一个异步网络模型中,没有可能实现一个满足以下属性的读写数据对象:
1、可用性
2、一致性
对于所有对等运算(包括消息会丢失的)
证明:
假设存在一个算法A满足这些条件:一致性、可用性、分区容忍性。我们构造一次A的执行,包括一个返回非一致结果的请求。假设网络包含至少两个节点,那么它可以被分为不相关的非空集合:{G,H}。假设所有G和H之间的通讯消息都丢失,这是可能的。如果这时在G上有一个写操作,接着H上有一个读操作,那么读操作将无法返回早些的写操作。

推论一:在一个异步网络模型中,没有可能实现一个满足以下属性的读写数据对象:
1、可用性,所有对等运算
2、一致性,所有对等运算,但消息不会丢失
证明:
主要问题是在异步网络模型中一个算法没有办法去判断一个消息是否丢失或者在传输通道中被延迟。因此,如果在运算中不会丢失任何消息的前提下存在一个能够保证一致性的算法,那么该算法也能够在所有运算(消息可能丢失)情况下保证一致性。这将与定理一矛盾。

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

定理二:在一个部分同步网络模型中,没有可能实现一个满足以下属性的读写数据对象:

1、可用性
2、一致性

对于所有对等运算(包括消息会丢失的)

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

理论参考价值

在Google使用廉价的PC机搭建了强大的、高可靠的计算和存储平台之后,互联网公司一致性地选择使用PC集群支撑全部的业务,这个理论指明了实现满足可用性、分区容忍性的分布式系统是可行的,并且该分布式系统在没有故障的情况下可以提供良好的一致性读写。

引用: http://blog.fens.me/distribution-cap/

发表评论