简介

一致性协议主要是为了解决分布式环境下的数据一致性问题。

对于单节点应用来说，数据的同步相对较简单。例如数据库的事务，多线程中的锁，都是为了保证数据的一致性。

而对于分布式环境来说，没有完善的强一致性解决方案。

在2000年，加州大学伯克利分校Eric Brewer教授提出了CAP猜想(后被证明可行)：一个分布式系统不可能同时满足一致性(C:Consistency), 可用性(A:Abailability)和分区容错性(P:Partition tolerance)这三个基本需求，最多只能同时满足其中的两项。

后eBay架构师Dan Pritchett提出了BASE理论，即Basically Available(基本可用),Soft state(软状态)和Eventually consisent(最终一致性)。 其核心思想即无法做到强一致性，但系统可以根据自身做到最终一致性。

故对于分布式系统设计，目前的做法是保证可用性和分区容错性的基础上去实现最终一致性。

而对于最终一致性处理，比较著名的协议和算法便是：二阶段提交协议(2PC)，三阶段提交协议(3PC)以及Paxos算法。

2PC

二阶段提交主要是引入了协调者来协调各个节点。

阶段一:提交事务请求

• 事务询问

  协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各参与者的响应

• 执行事务

  各参与者执行事务操作，并将Undo和Redo信息记录事务日志

• 各参与者像协调者反馈事务询问的响应

  如果事务执行成功，返回Yes;否则返回No

阶段二:执行事务提交

如果所有参与者返回Yes则执行事务提交

• 发送提交请求

  协调者向左右参与者节点发送Commit请求

• 事务提交

  参与者接收到Commit请求，提交事务

• 反馈事务提交结果

  参与者提交事务后，向协调者发送完成消息

• 完成事务

  协调者接收到所有参与者反馈的消息后，完成事务

如果有参与者返回No则执行中断事务

• 发送回滚请求

  协调者向所有参与者发出Rollback请求

• 事务回滚

  参与者根据Undo信息来执行事务回滚

• 反馈事务回滚结果

  参与者完成回滚后，向协调者发送消息

• 中断事务

  协调者接收到消息后，完成事务中断

优点

简单易实现

缺点

• 同步阻塞

  在二阶段提交过程中，所有参与该事务操作的逻辑都处于阻塞状态

• 协调者单点

  整个过程过度依赖协调者，而协调者只有一个，当协调者出现问题，则后续操作无法执行

• 数据不一致

  当协调者发送事务提交信息时，如果有参与者没有接收到，则会出现数据不一致的情况

• 容错机制不够完善

  只要有一个参与者失败，则全部失败，没有相应的容错机制

3PC

3PC主要是对2PC的执行流程进行了优化。

阶段一:CanCommit

• 事务询问

  协调者向参与者发送包含事务内容的canCommit请求，询问是否可以执行事务

• 参与者反馈事务询问

  参与者接收到canCommit请求后，根据自身情况返回Yes或No

阶段二:PreCommit

如果参与者都返回Yes,则执行事务预提交

• 发送预提交请求

  协调者发送preCommit请求，进入Prepared阶段

• 事务预提交

  参与者接收到preCommit请求后，会执行事务操作，并将Undo和Redo记录到日志

• 反馈事务执行响应

  如果参与者执行了事务，则回馈相应信息，同时等待提交或终止指令

如果有参与者返回No，则中断事务

• 发送中断请求

  协调者发送终止命令

• 中断事务

  无论是收到来自协调者的终止命令还是等待超时，参与者都中断事务

阶段三:doCommit

协调者接收到了所有参与者的响应则执行提交

• 发送提交请求

  协调者向所有参与者发送doCommit请求

• 事务提交 参与者接收到doCommit请求，执行事务提交

• 反馈事务提交结果

  参与者完成事务提交后，向协调者发送消息

• 完成事务

  协调者接收到所有参与者反馈的消息后，完成事务

如果有协调者反馈No，则中断事务

• 发送中断请求

  协调者向所有参与者发送终止请求

• 事务回滚

  参与者接收到abort请求后，利用日志中的Undo信息进行事务回滚

• 反馈事务回滚结果

  参与者在完成事务回滚之后，向协调者发送消息

• 中断事务

  协调者接收到参与者的反馈消息，中断事务

特别说明：此阶段中，如果出现网络问题，参与者未收到响应指令，则在超时后执行提交事务操作。

优点

通过超时时间的设置，降低了协调者的参与度

缺点

由于超时时间的引入，可能导致数据不一致的情况。

比如在:阶段三，协调者要发送中断事务，但是其中一个参与者没收到，则超时后自动提交了事务，导致数据不一致。

Paxos算法

2PC和3PC都存在缺点，而Paxos算法可以说是目前解决分布式最终一致性的最佳解决方案。当然也是相对较难理解的算法。

Paxos算法中主要有三个角色，Proposer,Acceptor和Learner。而其中最主要的参与者是Proposer和Acceptor,还有一个就是全局计数器，这个不在Paxos算法之内，需额外实现。

示例一

参照上图，以一个相对较简单的流程先来描述Paxos算法过程。

1. 针对某件事做决策时，Proposer分别从全局计数器中获得唯一的编号,这里假设p1,p2编号分别为1，2
2. Proposer将编号及其提议一起提交给Acceptor的大多数(这里就提交给所有的Acceptor)，形如[编号,提议]，例如p1就是[1,p1的提议]
3. 步骤3
   • 3-1. 假设a1,a2,a3先收到了p1的提议，则直接同意，并记录信息。(参考Paxos算法P1)形如[编号，提议，最大编号]，这里就是[1,p1的提议,1]
   • 3-2. 然后a1,a2,a3接收到了p2的提议。因为之前同意了p1的提议，但是p2的编号大于p1的编号，则也同意，但是反馈，已同意了p1的提议。修改最大编号[1,p1的提议,2](参考Paxos算法P2a，P2b)
4. 步骤4
   • 4-1. p1接收到了三个同意，则准备正式提交提议
   • 4-2. p2接收到三个同意，但是反馈说已经同意了p1的提议了，于是p2修改提议为[2,p1的提议]进行提交(参考Paxos算法P2，P2b)
5. 步骤5
   • 5-1. a1,a2,a3接收到p1的正式提议，目前a1,a2,a3的信息为[1,p1的提议,2]，p1的编号小于2，直接拒绝。
   • 5-2. a1,a2,a3接收到p2的提议，目前a1,a2,a3信息为[1,p1的提议,2]，p2的编号为2,同意。
6. 最终结果为[1,p1的提议,2]

Paxos算法条件

• P1：An acceptor must accept the first proposal that it receives. 即一个Acceptor必须要同意其收到的第一个提议
• P2：If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v. 如果一个包含了v的提议被选中，则后面序号高于此提议序号的被选中的提议需要包含v
• P2a：If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v. 如果一个包含了v的提议被选中，则后面序号高于此提议序号的被接受的提议需要包含v
• P2b：If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v. 如果一个包含了v的提议被选中，则后面序号高于此提议序号的被提出的提议需要包含v

• P2c：For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either

  • (a) no acceptor in S has accepted any proposal numbered less than n, or
  • (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

  对于任意的v和n,如果[n,v]被提出，则有一个S集合，这个S集合由半数以上Acceptor组成，且这些Acceptor满足如下条件之一: - (a) 没有同意任何小于n的提议 - (b) 有同意了小于n的提议，但是所同意的提议中，编号最大的那个提议值为v

示例二

下面再描述一个较为复杂的流程

1. Proposer分别从全局计数器中获得唯一的编号,这里假设p1,p2,p3编号分别为1，2，3
2. Proposer将编号及其提议一起提交给Acceptor的大多数(这里p1提交给a1,a2,a3。p2提交给a2,a3,a4。p3提交给a3,a4,a5)
3. 步骤3
   • 3-1. 假设a1,a2,a3先收到了p1的提议，则直接同意，并记录信息。(参考Paxos算法P1)形如[编号，提议，最大编号]，这里就是[1,p1的提议,1]
   • 3-2. 然后a2,a3,a4接收到了p2的提议。对于a4，直接同意。对于a2,a3,因为之前同意了p1的提议，但是p2的编号大于p1的编号，则也同意，但是反馈，已同意了p1的提议。修改最大编号1,p1的提议,2
4. 3-3. 接着a3,a4,a5接收到了p3的提议，对于a5直接同意。而对于a3已经同意了p1,p3的编号大于p1，则同意，并反馈已同意了p1的提议,修改最大编号[1,p1的提议,3]。对于a4,已经同意了p2，做类似反馈，修改最大编号[2,p2的提议,3]
5. 步骤4
   • 4-1. p1接收到了三个同意，则准备正式提交提议[1,p1的提议]
   • 4-2. p2接收到三个同意，但是反馈说已经同意了p1的提议了，于是p2修改提议为[2,p1的提议]进行提交(参考Paxos算法P2，P2b)
   • 4-3. p3接收到了三个同意，但是反馈说已经同意了p1,p2的提议，于是p3修改提议为[3,p2的提议]，取同意的提议中编号大的提议
6. 步骤5
   • 5-1. a1,a2,a3接收到p1的正式提议[1,p1的提议],a1[1,p1的提议,1]直接同意。a2[1,p1的提议,2]，p1编号小于2,拒绝。a3[1,p1的提议,3],p1小于3，拒绝.
   • 5-2. a2,a3,a4接收到p2的正式提议[2,p1的提议],a2[1,p1的提议,2]，同意。a3[1,p1的提议,3],p2小于3，拒绝.a4[2,p2的提议,3],p2小于3，拒绝
   • 5-3. a3,a4,a5接收到p3的正式提议[3,p2的提议],a3[1,p1的提议,3],同意，修改记录[2,p2的提议,3].a4[2,p2的提议,3],同意，修改记录[3,p2的提议,3].a5[3,p3的提议,3]，同意，修改记录[3,p2的提议,3]
7. 步骤6
   • 6-1. p1接收到a2,a3的拒绝，提议废除
   • 6-2. p2接收到a3,a4的拒绝，提议废除
   • 6-3. p3接收到同意，提议成功。
8. 最终结果为[3,p2的提议,3]