CAP 定理
CAP 定理指出对于一个分布式系统来说,不可能同时满足以下三点:
- 一致性 (Consistence): 等同于所有节点访问同一份最新的数据副本 (强一致性)
- 可用性 (Availability): 每次请求都能获取到非错的响应,但是不保证获取的数据为最新数据
- 分区容错性 (Partition tolerance): 系统中任意信息的丢失或失败不会影响系统的继续运作。
由 CAP 定理可知数据库的设计需要权衡取舍,所以可以把系统大致分为三类:
- CA: 单点集群,满足一致性,可用性的系统,通常在可扩展性上不太强大
- CP: 满足一致性,分区容忍性的系统,通常性能不是特别高
- AP: 满足可用性,分区容忍性的系统,通常可能对一致性要求低一些
BASE理论
BASE 理论是对 CAP 理论的延伸,核心思想是虽然无法做到强一致性 (Strong Consistency),但可以采用适合的方式达到最终一致性 (Eventual Consitency)
BASE 包含三部分:
- 基本可用 (Basically Available): 指分布式系统在出现故障的时候,允许损失部分可用性,保证核心可用
- 软状态 (Soft State): 指允许系统存在中间状态,而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本,允许不同节点间副本同步的延时就是软状态的体现。mysql replication 的异步复制也是一种体现
- 最终一致性 (Eventual Consistency): 指系统中的所有数据副本经过一定时间后,最终能够达到一致的状态。最终一致性是弱一致性的一种特殊情况
分布式事务
分布式事务用于在分布式系统中保证不同节点之间的数据一致性,通常会涉及到多个数据库。分布式事务处理的关键是必须有一种方法可以知道事务在任何地方所做的所有动作,提交或回滚事务的决定必须产生统一的结果(全部提交或全部回滚)。
XA 规范
Open Group定义了一套DTP分布式模型,主要含有:
- AP(应用程序)
- TM(事务管理器)
- RM(资源管理器) —- 通常指数据库
- CRM(通讯资源管理器)四部分 —- 消息中间件
XA则是DTP模型定义TM和RM之前通讯的接口规范。XA接口函数由数据库厂商提供。TM交易中间件用它来通知数据库事务的开始、结束以及提交、回滚等。 二阶段提交和三阶段提交就是根据这种思想衍生而来。
2PC
角色:协调者(coordinator),参与者(participants, 或cohort)
保证事务在提交时,协调者和参与者处于一致性状态,如果其中有一个参与者出现了故障或者网络问题,不能及时的回应协调者,那么这次事务就宣告失败或者出现阻塞。
准备阶段
事务协调者(事务管理器)给每个参与者(资源管理器)发送Prepare消息,每个参与者要么直接返回失败(如权限验证失败),要么在本地执行事务,写本地的redo和undo日志,但不提交
提交阶段
如果协调者收到了参与者的失败消息或者超时,直接给每个参与者发送回滚(Rollback)消息;否则,发送提交(Commit)消息;参与者根据协调者的指令执行提交或者回滚操作,释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
二阶段提交看起来确实能够提供原子性的操作,但是不幸的事,二阶段提交还是有几个缺点的:
同步阻塞问题。在事务执行过程中,所有参与节点都是事务阻塞型的。参与者占有公共资源时,其他第三方节点访问公共资源则会处于阻塞。
单点故障。在2PC中由协调者进行协调,一旦协调者发生故障,参与者会阻塞。尤其在第二阶段commit阶段,协调者发生故障,那么所有的参与者还都处于锁定事务资源的状态中,而无法继续完成事务操作。
如果是协调者挂掉,可以重新选举一个协调者,但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题
数据不一致。在二阶段提交的阶段二中,当协调者向参与者发送commit请求之后,发生了局部网络异常或者在发送commit请求过程中协调者发生了故障,导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。
二阶段无法解决的问题。协调者发出commit消息,并且只有部分参与者收到消息,此时协调者和收到消息的参与者发生宕机。那么即使协调者通过 选举协议 产生了新的协调者,这条事务的状态也是不确定的,集群中不能判断出事务是否被已经提交。
3PC
相比2PC,3PC引入超时机制,并把2PC的准备阶段再次一分为二,这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。
相对于2PC,3PC主要解决:单点故障问题、减少阻塞。因为一旦参与者无法“及时”收到来自协调者的信息之后,他会默认执行commit,而不会一直持有事务资源并处于阻塞状态。
通过上述过程可知最后无论是二阶段提交还是三阶段提交都无法彻底解决分布式的一致性问题,如果系统正常运行都能满足强一致性,但是如果出现意外还是会导致不一致,不过可以通过其他手段达到一致性,比如分区数据恢复或者事务补偿机制或者采用其他一致性算法。
分区数据恢复
复杂的数据恢复可以参见 SVN 的版本控制,可能可以自动合并,也可能会发生冲突然后需要人工干预。
简单的数据恢复可以参见 Mysql 的主从同步,数据可以自动从主库导到从库。
合并分区数据达成一致并不是最困难的,更困难的是处理分区过程中产生的错误。当分区操作引起错误,可以通过事务补偿补救错误,这可能是人工的也可能是自动的。
分区事务补偿
比如 MQ 消息事务和 TCC 事务协议就是一种补偿机制:
- MQ 事务: 利用消息中间件来异步完成事务的后一半更新,实现系统的最终一致性
- TCC 事务: TCC 是阿里巴巴提出的协议,将一个事务分为 Try、Commit、Cancel 三部分,也可以达到最终一致性
其他一致性算法
- Paxos 算法: 一种基于消息传递且具有高度容错特性的一致性算法
- Raft 算法: Raft 是一个共识算法,用于取代 Paxos。Raft 的目标是提供更好理解的算法,并且证明可以提供与 Paxos 相同的容错性以及性能
- Zab: Zookeeper atomic broadcast protocol,是 Zookeeper 内部用到的一致性协议。相比 Paxos,Zab 最大的特点是保证强一致性 (strong consistency,或叫线性一致性 linearizable consistency)