CAP 是什么?
CAP 理论, 被戏称为 [帽子理论]CAP 理论由 Eric Brewer 在 ACM 研讨会上提出, 而后 CAP 被奉为分布式领域的重要理论 [1]
分布式系统的 CAP 理论: 首先把分布式系统中的三个特性进行了如下归纳:
一致性 (C): 在分布式系统中的所有数据备份, 在同一时刻是否同样的 值 (等同于所有节点访问同一份最新的数据副本)
可用性 (A): 在集群中一部分节点故障后, 集群整体是否还能响应客户端 的读写请求 (对数据更新具备高可用性)
分区容忍性 (P): 以实际效果而言, 分区相当于对通信的时限要求系统 如果不能在时限内达成数据一致性, 就意味着发生了分区的情况, 必须就当前 操作在 C 和 A 之间做出选择 (分区状态可以理解为部分机器不连通了, 比如 机器挂了, 繁忙失去响应, 单机房故障等)
Partition 字面意思是网络分区, 即因网络因素将系统分隔为多个单独的部 分, 有人可能会说, 网络分区的情况发生概率非常小啊, 是不是不用考虑 P, 保证 CA 就好要理解 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 是一个必须项, 而不是可选项
高可用数据一致性是很多系统设计的目标, 但是分区又是不可避免的事情 我们来看一看分别拥有 CACP 和 AP 的情况
CA without P: 如果不要求 P(不允许分区), 则 C(强一致性) 和 A(可用 性) 是可以保证的但其实分区不是你想不想的问题, 而是始终会存在, CA 系 统基本上是单机系统, 比如单机数据库 2PC 是实现强一致性的具体手段
image.png
CP without A: 如果不要求 A(可用), 相当于每个请求都需要在 Server 之间 强一致, 而 P(分区) 会导致同步时间无限延长, 如此 CP 也是可以保证的很 多传统的数据库分布式事务都属于这种模式
image.png
AP wihtout C: 要高可用并允许分区, 则需放弃一致性一旦分区发生, 节点 之间可能会失去联系, 为了高可用, 每个节点只能用本地数据 供服务, 而这 样会导致全局数据的不一致性现在众多的 NoSQL 都属于此类
CAP 理论的证明
该理论由 brewer 出, 2 年后就是 2002 年, Lynch 与其他人证明了 Brewer 猜 想, 从而把 CAP 上升为一个定理但是, 它只是证明了 CAP 三者不可能同时满 足, 并没有证明任意二者都可满足的问题, 所以, 该证明被认为是一个收窄的 结果
Lynch 的证明相对比较简单: 采用反证法, 如果三者可同时满足, 则因为允许 P 的存在, 一定存在 Server 之间的丢包, 如此则不能保证 C, 证明简洁而严谨
在该证明中, 对 CAP 的定义进行了更明确的声明:
C: 一致性被称为原子对象, 任何的读写都应该看起来是 原子的, 或串行的写后面的读一定能读到前面写的内容所有的读写请 求都好像被全局排序一样
A: 对任何非失败节点都应该在有限时间内给出请求的回 应 (请求的可终止性)
P: 允许节点之间丢失任意多的消息, 当网络分区发生时, 节点之间的消息可能会完全丢失
对于 CAP 进一步的案例解释
2010 年的这篇文章 brewers-cap-theorem-on-distributed-systems/, 用了三 个例子来阐述 CAP, 分别是 example1: 单点的 mysql;example2: 两个 mysql, 但不同的 mysql 存储不同的数据子集, 相当于 sharding;example3: 两个 mysql, 对 A 的一个 insert 操作, 需要在 B 上执行成功才认为操作完成 (类似 复制集) 作者认为在 example1 和 example2 上 都能保证强一致性, 但不能保 证可用性; 在 example3 这个例子, 由于分区 (partition) 的存在, 就需要在 一致性与可用性之间权衡对于复制而言, 在很多场景下不追求强一致性比 如用户支付之后, 交易记录落地了; 但可能消费记录的消息同步存在延迟, 比 如消息阻塞了在金融业务中, 采取类似两地三中心架构, 往往可能采取本地 数据和异地机房数据同时写成功再返回的方式这样付出了性能的损耗, 响应 时间变长但发生机房故障后, 能确保数据是完全可以读写的, 保障了一致性
CAP 理论澄清
[CAP 理论十二年回顾:"规则" 变了] 一文首发于 Computer 杂志, 后由 InfoQ 和 IEEE 联合呈现, 非常精彩 [2], 文章表达了几个观点
三选二是一个伪命题
不是为了 P(分区容忍性), 要在 A 和 C 之间选择一个分区很少出现, CAP 在 大多数时候允许完美的 C 和 A 但当分区存在或可感知其影响的情况下, 就要 预备一种策略去探知分区并显式处理其影响这样的策略应分为三个步骤: 探
知分区发生, 进入显式的分区模式以限制某些操作, 启动恢复过程以恢复数据
一致性并补偿分区期间发生的错误
一致性的作用范围其实反映了这样一种观念, 即在一定的边界内状态是一 致的, 但超出了边界就无从谈起比如在一个主分区内可以保证完备的一致性 和可用性, 而在分区外服务是不可用的 Paxos 算法和原子性多播 (atomic multicast) 系统一般符合这样的场景像 Google 的一般做法是将主分区归属 在单个数据中心里面, 然后交给 Paxos 算法去解决跨区域的问题, 一方面保证 全局协商一致 (global consensus) 如 Chubby, 一方面实现高可用的持久性存 储如 Megastore
ACIDBASECAP
ACID 和 BASE 这两个术语都好记有余而精确不足, 出现较晚的 BASE 硬凑的感觉 更明显, 它是 Basically Available, Soft state, Eventually consistent (基本可用软状态最终一致性) 的首字母缩写其中的软状态和最终一 致性这两种技巧擅于对付存在分区的场合, 并因此 高了可用性
CAP 与 ACID 的关系更复杂一些, 也因此引起更多误解其中一个原因是 ACID 的 C 和 A 字母所代表的概念不同于 CAP 的 C 和 A 还有一个原因是选择可用性 只部分地影响 ACID 约束
进一步看 [分区] 之后
image.png
用一下这张图 [引用自 link 2], 在状态 S 的时候是非分区状态, 而分区模式则 演化出来了 S1,S2, 那么问题来了, 分区恢复之后, 状态究竟是多少呢? 有几 种解决方案
分区恢复策略: 可交换多副本数据类型 注意, 能支持此类处理的场景是有限的
riak_dt 就是这样一种保障最终一致性实现的数据结构, 它分为 Operation- based CRDTsState-based CRDTs 2 种形态
riak_dt link 参见 link [3]
分区恢复策略: 回放合并 在分区恢复过程中, 设计师必须解决两个问题:
分区两侧的状态最终必须保持一致
并且必须补偿分区期间产生的错误
如上图所示, 对于分区恢复的状态 S * 可以通过未分区时的状态 S 为起点, 然后 按顺序 [回放] 相应的变化事件 [以特定方式推进分区两侧的一系列操作, 并在过 程中一直保持一致的状态]Bayou[link 4] 就是这个实现机制, 它会回滚数 据库到正确的时刻并按无歧义的确定性的顺序重新执行所有的操作, 最终使 所有的节点达到相同的状态
对于有冲突的情况, 比如版本管理软件 cvs, 存在人工介入消除冲突的处理策略
来源: http://www.jianshu.com/p/854014f91fa5