CAP理论
CAP理论断言任何基于网络的数据共享系统,最多只能满足数据一致性、可用性、分区容忍性三要素中的两个要素。但是通过显式处理分区情形,系统设计师可以做到优化数据一致性和可用性,进而取得三者之间的平衡。
自打引入CAP理论的十几年里,设计师和研究者已经以它为理论基础探索了各式各样新颖的分布式系统,甚至到了滥用的程度。NoSQL运动也将CAP理论当作对抗传统关系型数据库的依据。
CAP理论主张任何基于网络的数据共享系统,都最多只能拥有以下三条中的两条:
•数据一致性(C),等同于所有节点访问同一份最新的数据副本;
•对数据更新具备高可用性(A);
•能容忍网络分区(P)。
CAP理论的表述很好地服务了它的目的,即开阔设计师的思路,在多样化的取舍方案下设计出多样化的系统。在过去的十几年里确实涌现了不计其数的新系统,也随之在数据一致性和可用性的相对关系上产生了相当多的争论。“三选二”的公式一直存在着误导性,它会过分简单化各性质之间的相互关系。现在我们有必要辨析其中的细节。实际上只有“在分区存在的前提下呈现完美的数据一致性和可用性”这种很少见的情况是CAP理论不允许出现的。
虽然设计师仍然需要在分区的前提下对数据一致性和可用性做取舍,但具体如何处理分区和恢复一致性,这里面有不计其数的变通方案和灵活度。当代CAP实践应将目标定为针对具体的应用,在合理范围内最大化数据一致性和可用性的“合力”。这样的思路延伸为如何规划分区期间的操作和分区之后的恢复,从而启发设计师加深对CAP的认识,突破过去由于CAP理论的表述而产生的思维局限。
为什么“三选二”公式有误导性
理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致,即丧失了C性质。如果为了保证数据一致性,将分区一侧的节点设置为不可用,那么又丧失了A性质。除非两个节点可以互相通信,才能既保证C又保证A,这又会导致丧失P性质。一般来说跨区域的系统,设计师无法舍弃P性质,那么就只能在数据一致性和可用性上做一个艰难选择。不确切地说,NoSQL运动的主题其实是创造各种可用性优先、数据一致性其次的方案;而传统数据库坚守ACID特性(原子性、一致性、隔离性、持久性),做的是相反的事情。下文“ACID、BASE、CAP”小节详细说明了它们的差异。
事实上,CAP理论本身就是在类似的讨论中诞生的。早在1990年代中期,我和同事构建了一系列的基于集群的跨区域系统(实质上是早期的云计算),包括搜索引擎、缓存代理以及内容分发系统1。从收入目标以及合约规定来讲,系统可用性是首要目标,因而我们常规会使用缓存或者事后校核更新日志来优化系统的可用性。尽管这些策略提升了系统的可用性,但这是以牺牲系统数据一致性为代价的。
关于“数据一致性 VS 可用性”的第一回合争论,表现为ACID与BASE之争2。当时BASE还不怎么被人们接受,主要是大家看重ACID的优点而不愿意放弃。提出CAP理论,目的是证明有必要开拓更广阔的设计空间,因此才有了“三选二”公式。CAP理论最早在1998年秋季提出,1999年正式发表3,并在2000年登上Symposium on Principles of Distributed Computing大会的主题演讲4,最终确立了该理论的正确性。
“三选二”的观点在几个方面起了误导作用,详见下文“CAP之惑”小节的解释。首先,由于分区很少发生,那么在系统不存在分区的情况下没什么理由牺牲C或A。其次,C与A之间的取舍可以在同一系统内以非常细小的粒度反复发生,而每一次的决策可能因为具体的操作,乃至因为牵涉到特定的数据或用户而有所不同。最后,这三种性质都可以在程度上衡量,并不是非黑即白的有或无。可用性显然是在0%到100%之间连续变化的,一致性分很多级别,连分区也可以细分为不同含义,如系统内的不同部分对于是否存在分区可以有不一样的认知。
要探索这些细微的差别,就要突破传统的分区处理方式,而这是一项根本性的挑战。因为分区很少出现,CAP在大多数时候允许完美的C和A。但当分区存在或可感知其影响的情况下,就要预备一种策略去探知分区并显式处理其影响。这样的策略应分为三个步骤:探知分区发生,进入显式的分区模式以限制某些操作,启动恢复过程以恢复数据一致性并补偿分区期间发生的错误。
ACID、BASE、CAP
ACID和BASE代表了两种截然相反的设计哲学,分处一致性-可用性分布图谱的两极。ACID注重一致性,是数据库的传统设计思路。我和同事在1990年代晚期提出BASE,目的是抓住当时正逐渐成型的一些针对高可用性的设计思路,并且把不同性质之间的取舍和消长关系摆上台面。现代大规模跨区域分布的系统,包括云在内,同时运用了这两种思路。
这两个术语都好记有余而精确不足,出现较晚的BASE硬凑的感觉更明显,它是“Basically Available, Soft state, Eventually consistent(基本可用、软状态、最终一致性)”的首字母缩写。其中的软状态和最终一致性这两种技巧擅于对付存在分区的场合,并因此提高了可用性。
CAP与ACID的关系更复杂一些,也因此引起更多误解。其中一个原因是ACID的C和A字母所代表的概念不同于CAP的C和A。还有一个原因是选择可用性只部分地影响ACID约束。ACID四项特性分别为:
原子性(A)。所有的系统都受惠于原子性操作。当我们考虑可用性的时候,没有理由去改变分区两侧操作的原子性。而且满足ACID定义的、高抽象层次的原子操作,实际上会简化分区恢复。
一致性(C)。ACID的C指的是事务不能破坏任何数据库规则,如键的唯一性。与之相比,CAP的C仅指单一副本这个意义上的一致性,因此只是ACID一致性约束的一个严格的子集。ACID一致性不可能在分区过程中保持,因此分区恢复时需要重建ACID一致性。推而广之,分区期间也许不可能维持某些不变性约束,所以有必要仔细考虑哪些操作应该禁止,分区后又如何恢复这些不变性约束。
隔离性(I)。隔离是CAP理论的核心:如果系统要求ACID隔离性,那么它在分区期间最多可以在分区一侧维持操作。事务的可串行性(serializability)要求全局的通信,因此在分区的情况下不能成立。只要在分区恢复时进行补偿,在分区前后保持一个较弱的正确性定义是可行的。
持久性(D)。牺牲持久性没有意义,理由和原子性一样,虽然开发者有理由(持久性成本太高)选择BASE风格的软状态来避免实现持久性。这里有一个细节,分区恢复可能因为回退持久性操作,而无意中破坏某项不变性约束。但只要恢复时给定分区两侧的持久性操作历史记录,破坏不变性约束的操作还是可以被检测出来并修正的。通常来讲,让分区两侧的事务都满足ACID特性会使得后续的分区恢复变得更容易,并且为分区恢复时事务的补偿工作奠定了基本的条件。
CAP和延迟的联系
CAP理论的经典解释,是忽略网络延迟的,但在实际中延迟和分区紧密相关。CAP从理论变为现实的场景发生在操作的间歇,系统需要在这段时间内做出关于分区的一个重要决定:
•取消操作因而降低系统的可用性,还是
•继续操作,以冒险损失系统一致性为代价
依靠多次尝试通信的方法来达到一致性,比如Paxos算法或者两阶段事务提交,仅仅是推迟了决策的时间。系统终究要做一个决定;无限期地尝试下去,本身就是选择一致性牺牲可用性的表现。
因此以实际效果而言,分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性,就意味着发生了分区的情况,必须就当前操作在C和A之间做出选择。这就从延迟的角度抓住了设计的核心问题:分区两侧是否在无通信的情况下继续其操作?
从这个实用的观察角度出发可以导出若干重要的推论。第一,分区并不是全体节点的一致见解,因为有些节点检测到了分区,有些可能没有。第二,检测到分区的节点即进入分区模式——这是优化C和A的核心环节。
最后,这个观察角度还意味着设计师可以根据期望中的响应时间,有意识地设置时限;时限设得越短,系统进入分区模式越频繁,其中有些时候并不一定真的发生了分区的情况,可能只是网络变慢而已。
有时候在跨区域的系统,放弃强一致性来避免保持数据一致所带来的高延迟是非常有意义的。Yahoo的PNUTS系统因为以异步的方式维护远程副本而带来数据一致性的问题5。但好处是主副本就放在本地,减小操作的等待时间。这个策略在实际中很实用,因为一般来讲,用户数据大都会根据用户的(日常)地理位置做分区。最理想的状况是每一位用户都在他的数据主副本附近。
Facebook使用了相反的策略6:主副本被固定在一个地方,因此远程用户一般访问到的是离他较近,但可能已经过时的数据副本。不过当用户更新其页面的时候是直接对主副本进行更新,而且该用户的所有读操作也被短暂转向从主副本读取,尽管这样延迟会比较高。20秒后,该用户的流量被重新切换回离他较近的副本,此时副本应该已经同步好了刚才的更新。
CAP之惑
CAP理论经常在不同方面被人误解,对于可用性和一致性的作用范围的误解尤为严重,可能造成不希望看到的结果。如果用户根本获取不到服务,那么其实谈不上C和A之间做取舍,除非把一部分服务放在客户端上运行,即所谓的无连接操作或称离线模式7。离线模式正变得越来越重要。HTML5的一些特性,特别是客户端持久化存储特性,将会促进离线操作的发展。支持离线模式的系统通常会在C和A中选择A,那么就不得不在长时间处于分区状态后进行恢复。
“一致性的作用范围”其实反映了这样一种观念,即在一定的边界内状态是一致的,但超出了边界就无从谈起。比如在一个主分区内可以保证完备的一致性和可用性,而在分区外服务是不可用的。Paxos算法和原子性多播(atomic multicast)系统一般符合这样的场景8。像Google的一半做法是将主分区归属在单一个数据中心里面,然后交给Paxos算法去解决跨区域的问题,一方面保证全局协商一致(global consensus)如Chubby9,一方面实现高可用的持久性存储如Megastore10。
分区期间,独立且能自我保证一致性的节点子集合可以继续执行操作,只是无法保证全局范围的不变性约束不受破坏。数据分片(sharding)就是这样的例子,设计师预先将数据划分到不同的分区节点,分区期间单个数据分片多半可以继续操作。相反,如果被分区的是内在关系密切的状态,或者有某些全局性的不变性约束非保持不可,那么最好的情况是只有分区一侧可以进行操作,最坏情况是操作完全不能进行。
“三选二”的时候取CA而舍P是否合理?已经有研究者指出了其中的要害——怎样才算“舍P”含义并不明确11,12。设计师可以选择不要分区吗?哪怕原来选了CA,当分区出现的时候,你也只能回头重新在C和A之间再选一次。我们最好从概率的角度去理解:选择CA意味着我们假定,分区出现的可能性要比其他的系统性错误(如自然灾难、并发故障)低很多。
这种观点在实际中很有意义,因为某些故障组合可能导致同时丢掉C和A,所以说CAP三个性质都是一个度的问题。实践中,大部分团体认为(位于单一地点的)数据中心内部是没有分区的,因此在单一数据中心之内可以选择CA;CAP理论出现之前,系统都默认这样的设计思路,包括传统数据库在内。然而就算可能性不高,单一数据中心完全有可能出现分区的情况,一旦出现就会动摇以CA为取向的设计基础。最后,考虑到跨区域时出现的高延迟,在数据一致性上让步来换取更好性能的做法相对比较常见。
CAP还有一个方面很多人认识不清,那就是放弃一致性其实有隐藏负担,即需要明确了解系统中存在的不变性约束。满足一致性的系统有一种保持其不变性约束的自然倾向,即便设计师不清楚系统中所有的不变性约束,相当一部分合理的不变性约束会自动地维持下去。相反,当设计师选择可用性的时候,因为需要在分区结束后恢复被破坏的不变性约束,显然必须将各种不变性约束一一列举出来,可想而知这件工作很有挑战又很容易犯错。放弃一致性为什么难,其核心还是“并发更新问题”,跟多线程编程比顺序编程难的原因是一样的。