1、前言

分布式一致性协议是分布式系统的基石,其基本功能是在分布式系统中(多个进程之间)针对某些值达成一致,同时确保分布式系统高可用。业界提出较早且相对成熟的分布式一致性算法是PAXOS,是由Lamport (美国计算机科学家)在1990年提出,PAXOS的发展历程也出现了很多变种,包括Multi Paxos、Fast Paxos、EPaxos等,但算法的核心是基本一致的。后来Stanford的同学认为Paxos算法过于复杂,难以理解,于是提出了Raft算法,Raft一定程度上简化了Paxos的实现,两者的差异我们会在后续文章中提提到。本文希望通过梳理分布式一致性算法的演进来增加大家对分布式协商一致的深度理解。

一致性协议并非只有我们前面提到的Paxos和Raft,早期的两阶段提交和三阶段提交也是常用的一致性协议,不过对于工程实现而言,这两种协议有着不可避免的劣势,在容错方面有着天然的不足,所以才会被后来者替代,但在一些特定场景的实现中,仍然存在着应用。新兴的一致性协议是对之前的协议的完善和改进,所以理解两阶段和三阶段提交协议有助于我们了解一致性协议的演进历程,同时对新兴的一致性协议有认知。

2、两阶段提交协议(2PC:Two-Phrase Commit)

两阶段提交协议的目标在于在分布式系统中保证数据的一致性,许多分布式系统采用该协议提供对分布式事务的支持(提供但不一定有人用,呵呵~)。 顾名思义,该协议将一个分布式的;事务过程拆分成两个阶段:投票阶段和事务提交阶段。为了让整个数据库集群能够正常的运行,该协议指定了一个“协调者”单 点,用于协调整个数据库集群的运行,为了简化描述,我们将数据库里面的各个节点称为“参与者”,三阶段提交协议中同样包含“协调者”和“参与者”这两个定 义。

第一阶段:投票阶段

该阶段的主要目的在于打探数据库集群中的各个参与者是否能够正常的执行事务,具体步骤如下:

第二阶段:事务提交阶段

在第一阶段协调者的询盘之后,各个参与者会回复自己事务的执行情况,这时候存在三种可能

对于第一种情况,协调者将向所有的参与者发出提交事务的通知,具体步骤如下

事务提交时序图

对于第二、三种情况,协调者均认为参与者无法正常成功执行事务,为了整个集群数据的一致性,所以要向各个参与者发送事务回滚通知,具体步骤如下

事务回滚时序图

两阶段提交协议解决的是分布式数据库数据强一致性问题,其原理简单,易于实现,但是缺点也是显而易见的,主要缺点如下:

  • 单点问题
    协调者在整个两阶段提交过程中扮演着举足轻重的作用,一旦协调者所在服务器宕机,那么就会影响整个数据库集群的正常运行,比如在第二阶段中,如果协调者因为故障不能正常发送事务提交或回滚通知,那么参与者们将一直处于阻塞状态,整个数据库集群将无法提供服务。
  • 同步阻塞
    两阶段提交执行过程中,所有的参与者都需要听从协调者的统一调度,期间处于阻塞状态而不能从事其他操作,这样效率及其低下。
  • 数据不一致性
    两阶段提交协议虽然为分布式数据强一致性所设计,但仍然存在数据不一致性的可能,比如在第二阶段中,假设协调者发出了 事务commit的通知,但是因为网络问题该通知仅被一部分参与者所收到并执行了commit操作,其余的参与者则因为没有收到通知一直处于阻塞状态,这 时候就产生了数据的不一致性。

3、三阶段提交协议(3PC:Three-Phrase Commit)

针对两阶段提交存在的问题,三阶段提交协议通过引入一个“预询盘”阶段,以及超时策略来减少整个集群的阻塞时间,提升系统性能。三阶段提交的三个阶段分别为:can_commit,pre_commit,do_commit。

第一阶段:can_commit

该阶段协调者会去询问各个参与者是否能够正常执行事务,参与者根据自身情况回复一个预估值,相对于真正的执行事务,这个过程是轻量的,具体步骤如下:

第二阶段:pre_commit

本阶段协调者会根据第一阶段的询盘结果采取相应操作,询盘结果主要有三种

针对第一种情况,协调者会向所有参与者发送事务执行请求,具体步骤如下:

在上面的步骤中,如果参与者等待超时,则会中断事务。 针对第二、三种情况,协调者认为事务无法正常执行,于是向各个参与者发出abort通知,请求退出预备状态,具体步骤如下

事务中断时序图

第三阶段:do_commit

如果第二阶段事务未中断,那么本阶段协调者将会依据事务执行返回的结果来决定提交或回滚事务,分为三种情况

针对第一种情况,协调者向各个参与者发起事务提交请求,具体步骤如下:

事务提交时序图
针对第二、三种情况,协调者认为事务无法正常执行,于是向各个参与者发送事务回滚请求,具体步骤如下:

事务回滚时序图
在本阶段如果因为协调者或网络问题,导致参与者迟迟不能收到来自协调者的commit或rollback请求,那么参与者将不会如两阶段提交中那样陷入阻塞,而是等待超时后继续commit。相对于两阶段提交虽然降低了同步阻塞,但仍然无法避免数据的不一致性。

两阶段提交与三阶段提交的差异:

3PC对于协调者和参与者都设置了超时机制(在2PC中,只有协调者拥有超时机制,即如果在一定时间内没有收到参与者的消息则默认失败)。在2PC的准备阶段和提交阶段之间,插入预提交阶段,使3PC拥有CanCommit、PreCommit、DoCommit三个阶段。PreCommit是一个缓冲,保证了在最后提交阶段之前各参与节点的状态是一致的。简单来讲,增加第一个阶段的目的是确保各个节点的状态一致(可以接收提交),由于经过第一轮的确认,在短时间内,节点发生故障的可能性小,并且第一阶段还未改变节点任何状态,如果此时检测到故障节点,不需要做回退。整体来看经过第一轮确认后,系统是高概率可以走完三个阶段并最终完成决议的提交。所以增加第一阶段是尽可能的确保了在提交决议前节点状态不一致的可能性。

然而,三阶段也不是完美的,也可能出现数据不一致的问题。例如如果进入PreCommit后,协调者发出的是abort请求,假设只有一个参与者收到并进行了abort操作,而其他对于系统状态未知的参与者会根据3PC规则选择继续Commit,此时系统状态就发生不一致性。

4、Paxos协议

前面铺垫了那么多,终于轮到了我们大名鼎鼎的Paxos了,Paxos设计目标仍然和2PC和3PC一样,需要解决分布式系统各种一致性协商问题,但是Paxos需要更加强壮,即可以容忍节点故障,能否处理数据不一致的问题等,这些问题的解决对Paxos提出了更高的挑战。为了解决这些问题,Paxos有了一些新的概念:

1、大多数原则:是指当一个分布式系统(2P+1)个节点中大多数节(P+1)点对某个提议同意后,该提议就可以生效。

2、容错规则:当系统存在2P+1个节点,可容忍的最大故障节点数为P。当系统正常节点数<P+1时,系统无法再提供服务

3、全局有序:全局有序是针对提交决议的编号而言的,为了保证参与协商的各个节点能够有效的运行,不出现乱序问题,要求每个请求具有唯一的编号。如何保证提交的决议全局有序呢?常见的方式如下:

方案一存在一个问题:在决议在commit之前,如果认可的节点又接收了其他新的提议,则会导致之前认可的决议无法commit。如下图所示:

(1)优点:解决了决议编号冲突的问题,避免了多个协调者发起大量无效的决议提交,降低系统网络负载,解决了活锁问题;

(2)缺点:所有请求均通过一个节点提交,单节点成为瓶颈,如果master故障,需要有选举机制来从剩余的参与者中选取新的master节点,在新master产生之前,系统无法对外提供提交决议的服务。

4、学习者:区别于协调者和参与者,Paxos引入一个新的角色学习者,学习者不参与决议的协商,仅仅学习协商的结果,学习者的引入个人觉得至少可以从另个角度理解:

(1)节点规模问题:在大型的分布式系统中,节点数是海量的,如果所有节点都参与协商会产生大量的网络通信,所以一般的做法是选举部分奇数节点(3、5、7)参与协商,其他节点可以做为学习者存在,向其推送决议内容;

(2)可以利用学习者将决议内容进行备份,例如在跨区域的网络中做异地备份。

了解完这些背景后,我们来正式看下paxos协议的具体约束和流程:

Paxos约束条件:
P1:一个acceptor必须接受(accept)第一次收到的提案。
注意P1是不完备的。如果恰好一半acceptor接受的提案具有value A,另一半接受的提案具有value B,那么就无法形成多数派,无法批准任何一个value。
约束2并不要求只批准一个提案,暗示可能存在多个提案。只要提案的value是一样的,批准多个提案不违背约束2。于是可以产生约束P2:
P2:一旦一个具有value v的提案被批准(chosen),那么之后批准(chosen)的提案必须具有value v。
注:通过某种方法可以为每个提案分配一个编号,在提案之间建立一个全序关系,所谓“之后”都是指所有编号更大的提案。
如果P1和P2都能够保证,那么约束2就能够保证。
批准一个value意味着多个acceptor接受(accept)了该value.因此,可以对P2进行加强:
P2a:一旦一个具有value v的提案被批准(chosen),那么之后任何acceptor再次接受(accept)的提案必须具有value v
由于通信是异步的,P2a和P1会发生冲突。如果一个value被批准后,一个proposer和一个acceptor从休眠中苏醒,前者提出一个 具有新的value的提案。根据P1,后者应当接受,根据P2a,则不应当接受,这中场景下P2a和P1有矛盾。于是需要换个思路,转而对 proposer的行为进行约束:
P2b:一旦一个具有value v的提案被批准(chosen),那么以后任何proposer提出的提案必须具有value v。
由于acceptor能接受的提案都必须由proposer提出,所以P2b蕴涵了P2a,是一个更强的约束。
但是根据P2b难以提出实现手段。因此需要进一步加强P2b。
假设一个编号为m的value v已经获得批准(chosen),来看看在什么情况下对任何编号为n(n>m)的提案都含有value v。因为m已经获得批准(chosen),显然存在一个acceptors的多数派C,他们都接受(accept)了v。考虑到任何多数派都和C具有至少 一个公共成员,可以找到一个蕴涵P2b的约束P2c:
P2c:如果一个编号为n的提案具有value v,那么存在一个多数派,要么他们中所有人都没有接受(accept)编号小于n 的任何提案,要么他们已经接受(accept)的所有编号小于n的提案中编号最大的那个提案具有value v。
Paxos过程:
通过一个提案分为两个阶段:
1. prepare阶段:
proposer(提案发起者)选择一个提案编号n并将提案编号n请求发送给acceptors中的一个多数派(acceptors的一个子集);
acceptor收到提案编号消息后,如果提案的编号n大于之前收到的提案编号,则承诺不再回复小于n的提案;如果该acceptor已经批准过提案,则将自己批准的提案回复给proposer;
2. 批准阶段:
当一个proposer收到了多数acceptors对提案的承若(回复)后,就进入批准阶段。它要向回复提案请求的 acceptors发送accept请求,如果没有发现有一个acceptor接受过一个提案,那么向所有的acceptor发起自己的提案(自己的值和提案编号n),否则,从所有acceptors的回包中选择提案编号最大的提案,将该提案的值作为此次提案的值,提案编号仍然为n。
在不违背自己向其他proposer的承诺的前提下,acceptor收到accept请求后即接受这个请求。

参考文献:

1、对分布式事务及两阶段提交、三阶段提交的理解:https://www.cnblogs.com/binyue/p/3678390.html

2、分布式事务 - 两阶段提交与三阶段提交:https://blog.csdn.net/sofia1217/article/details/53968177

3、Paxos协议学习笔记:https://www.jianshu.com/p/5e9aeb46540f