一致性协议.md

当一个事务跨越多个分布式节点时，为了保持事务处理的ACID特性，需要引入一个协调者组件来统一调度所有分布式节点（参与者）的执行逻辑，协调者负责调度参与者的行为，并最终决定这些参与者是否要真正进行事务提交。为了解决分布式一致性问题，诞生了二阶段提交协议、三阶段提交协议和Paxos算法。

2PC

2PC，即二阶段提交。为了使分布式事务处理过程中能保持原子性和一致性而设计的一种强一致性算法，分为两个阶段：

阶段一：提交事务请求（投票）

1. 事务询问：协调者向所有参与者发送事务内容，询问是否可以执行事务提交操作。
2. 执行事务：各参与者执行事务操作，并记录Undo/Redo日志。
3. 各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么就返回Yes响应，表示事务可以执行；否则返回No响应，表示事务不可执行。

阶段二：执行事务提交（执行）

如果所有参与者都返回Yes响应，那么就会执行事务提交：

1. 协调者向参与者发送提交请求
2. 参与者接收到后提交事务
3. 参与者相协调者反馈事务提交结果
4. 完成事务

任意一个参与者返回了No响应或者等待超时，那么就会中断事务：

1. 协调者向参与者发送回滚请求
2. 参与者接收到后回滚事务
3. 参与者相协调者反馈事务回滚结果
4. 中断事务

优点

原理简单、实现方便。

缺点

同步阻塞、单点问题、数据不一致（可能只有部分参与者接收到了Commit请求）、太过保守（没有较完善的容错机制）。

3PC

是2PC的改进版，将2PC的投票阶段一分为二，形成了CanCommit、PreCommit和doCpmmit三个阶段：

阶段一：CanCommit

1. 事务询问：协调者询问参与者时候否可以执行事务提交操作。
2. 各参与者向协调者反馈事务询问的响应。

阶段二：PreCommit

如果所有参与者都返回Yes响应，那么就会执行事务预提交：

1. 发送预提交请求：协调者向所有参与者发送preCommit请求
2. 执行事务：各参与者执行事务操作，并记录Undo/Redo日志。
3. 各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么就返回ACK响应，表示事务可以执行。

任意一个参与者返回了No响应或者等待超时，那么就会中断事务。

阶段三：doCommit

如果协调者发送了preCommit请求，并且接收到了所有参与者的ACK响应，那么就会执行事务提交：

1. 协调者向参与者发送提交请求
2. 参与者接收到后提交事务
3. 参与者相协调者反馈事务提交结果
4. 完成事务

否则：

1. 协调者向参与者发送回滚请求
2. 参与者接收到后回滚事务
3. 参与者相协调者反馈事务回滚结果
4. 中断事务

值得注意的是，一旦进入阶段三，当协调者与接收者之间无法通信时，参与者会在等待超时之后继续进行事务提交。

优点

相比2PC，降低了参与者的阻塞范围，并且能在在出现单点故障后继续达成一致。

缺点

如果某个参与者预提交事务失败，之后协调者和参与者无法通信，超时后参与者会提交事务，这必然会造成数据不一致。

Paxos算法

Paxos是一种分布式一致性算法。在多个节点中，每个节点可能都有一个值，并且这个值不一定相同，Paxos的作用就是选出一个值，并让所有节点接受这个值。

在Paxos算法中，节点一个有三种角色：Proposer（提议者）、Acceptor（接受者）、Learner（告知者），并且每台机器可能拥有其中不止一种角色。

Paxos算法分为两个阶段：

1. Proposer向过半Acceptor节点发送提案为[Mn, Vn]的Prepare请求，其中Mn为提案编号，Vn为提案值。Acceptor接收到Proposer的Prepare请求，此时可能会有两种情况：

• 该Acceptor还未接受过Prepare请求，那么此时将会接受该请求，并更新自身状态为[Mn, Vn]，并将[Mn, Vn]作为Prepare请求响应反馈给Proposer，并且承诺不会再接受任何编号比Mn小的请求。

• 该Acceptor已经接受过Prepare请求，此时有会有两种情况： - Mn小于之前接受过最大的请求编号，忽略该请求。 - Mn大于等于之前接受过最大的请求编号Mp，更新当前状态为[Mn, Vn]，并将[Mp, Vp]作为Prepare请求响应反馈给Proposer，并且承诺不会再接受任何编号比Mn小的请求。

2. 如果Proposer接收到半数以上Acceptor对其发出的提案[Mn, Vn]的Prepare请求的响应，那么就会向Acceptor发出一个提案为[Mn, Vx]的Accept请求，其中Vx为其接收到的Prepare请求响应中编号最大的提案的值（如果响应中不包含任意提案，那么就为任意值）。Acceptor接收到的Accept请求中，如果提案编号Mn不小于其承诺的最小编号，并且当前Acceptor没有通过任何编号大于Mn的Accept请求，那么就会通过这个Accept请求。如果有半数以上Acceptor通过了某个提案，那么就会告知部分Learner，再由这部分Learner同步给其他所有Learner通过的结果。

Raft算法

由于paxos算法过于繁杂，诞生了raft算法，raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。Raft一致性算法就是比Paxos简单又能实现Paxos所解决的问题的一致性算法。

Raft概述

角色

Raft把集群中的节点分为三种状态：Leader、 Follower 、Candidate，每种状态负责的任务不一样，Raft运行时提供服务的时候只存在Leader与Follower两种状态。

• Leader（领导者）：负责日志的同步管理，处理来自客户端的请求，与Follower保持着heartBeat联系。
• Follower（追随者）：刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求，把请求到Follower的事务转发给Leader。
• Candidate（候选者）：负责选举投票，Raft刚启动时由一个节点heartBeat等待超时后，从Follower转为Candidate发起选举，选举出Leader后从Candidate转为Leader状态。

Term

在Raft中使用了一个可以理解为纪元的概念，用Term作为一个纪元，每个Term都是一个连续递增的编号，每一轮选举都是一个Term纪元，在一个Term中只能产生一个Leader。Raft开始时所有Follower的Term为1，其中一个Follower逻辑时钟到期后转换为Candidate，Term加1，这时Term为2，然后开始选举，这时候有几种情况会使Term发生改变：

• 如果当前Term为2的任期内没有选举出Leader或出现异常，则Term递增，开始新一任期选举
• 当这轮Term为2的周期选举出Leader后，过后Leader宕掉了，然后其他Follower转为Candidate，Term递增，开始新一任期选举
• 当Leader或Candidate发现自己的Term比别的Follower小时Leader或Candidate将转为Follower，Term递增
• 当Follower的Term比别的Term小时，Follower也将更新Term保持与其他Follower一致

可以说每次Term的递增都将发生新一轮的选举，Raft保证一个Term只有一个Leader，在Raft正常运转中所有的节点的Term都是一致的，如果节点不发生故障一个Term会一直保持下去，当某节点收到的请求中Term比当前Term小时则拒绝该请求。

选举（Election）

Raft的选举由定时器来触发，每个节点的选举定时器时间都是不一样的，开始时状态都为Follower。某个节点定时器触发选举后Term递增，状态由Follower转为Candidate，向其他节点发起RequestVote RPC请求，这时候有三种可能的情况发生：

• 该RequestVote请求接收到过半数个节点的投票，从Candidate转为Leader，向其他节点发送heartBeat以保持Leader的正常运转
• 在此期间如果收到其他节点发送过来的AppendEntries RPC请求，如该节点的Term大则当前节点转为Follower，否则保持Candidate拒绝该请求
• Election timeout发生则Term递增，重新发起选举

在一个Term期间每个节点只能投票一次，所以当有多个Candidate存在时就会出现每个Candidate发起的选举都存在接收到的投票数都不过半的问题，这时每个Candidate都将Term递增、重启定时器并重新发起选举，由于每个节点中定时器的时间都是随机的，所以就不会多次存在有多个Candidate同时发起投票的问题。 有这么几种情况会发起选举：

1. Raft初次启动，不存在Leader，发起选举
2. Leader宕机或Follower没有接收到Leader的heartBeat，发生election timeout从而发起选举;

日志复制（Log Replication）

日志复制主要作用是用于保证节点的一致性，这阶段所做的操作也是为了保证一致性与高可用性；当Leader选举出来后便开始负责客户端的请求，所有事务（更新操作）请求都必须先经过Leader处理，要保证节点的一致性就要保证每个节点都按顺序执行相同的操作序列，日志复制就是为了保证执行相同的操作序列所做的工作；在Raft中当接收到客户端的日志后先把该日志追加到本地的Log中，然后通过heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送ACK，当Leader收到大多数Follower的ACK信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在自己的本地磁盘中。

安全性（Safety）

安全性是用于保证每个节点都执行相同序列的安全机制，如当某个Follower在当前Leader commit Log时变得不可用了，稍后可能该Follower又会倍选举为Leader，这时新Leader可能会用新的Log覆盖先前已committed的Log，这就是导致节点执行不同序列。Safety就是用于保证选举出来的Leader一定包含先前 commited Log的机制。

参考资料

• 《从Paxos到Zookeeper》

• raft动图