本文并不会对每种算法进行深入，我只是参考了部分网上的博客和整理的资料，也只是处于一种懵懂的状态。

本文参考资源：

Paxos算法 - 维基百科，自由的百科全书

raft协议应用方面的疑问？ - 知乎

如何浅显易懂地解说 Paxos 的算法？ - 知乎

一致性算法（Paxos、Raft、ZAB）_哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

一文搞懂Raft算法 - xybaby - 博客园一文搞懂Raft算法 - xybaby - 博客园

还有一些没记下来，研究这些东西有英文能力的还是尽量去读发明者所著论文吧。。

拜占庭将军问题

拜占庭帝国有许多支军队，不同军队的将军之间必须制定一个统一的行动计划，从而做出仅供或者撤退的决定，同时，各个将军在地理上都是被分隔开的，只能依靠军队的通讯员来进行通讯。然而，在所有的通讯员中可能会存在叛徒，这些叛徒可以篡改信息，从而达到欺骗将军的目的。

为了解决网络分区情况下，部分节点之间的通讯可能出现消失丢失或消息被篡改的情况。衍生出了几种共识算法：

Basic Paxos

Paxos是早期的共识算法，由拜占庭将军问题的提出者 Leslie Lamport 所发明。谷歌的分布式锁服务 Chubby 就是以 Paxos 算法为基础。

在古希腊有一个叫做 Paxos 的小岛，岛上采用议会的形式来通过法令，议会中的议员通过信使进行消息的传递。议员和信使都是兼职的，他们随时有可能会离开议会厅，并且信使可能会重复地传递消息，也可能一去不复返。因此，议会协议要保证在这种情况下法令仍然能够正确的产生，并且不会出现冲突。

Paxos算法假设没有拜占庭将军问题，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息。

paxos有三个版本：
+ Basic Paxos
+ Multi Paxos
+ Fast Paxos

在paxos算法中，有四种角色，分别具有三种不同的行为，但多数情况，一个进程可能同时充当多种角色。
+ client ：系统外部角色，请求发起者，不参与决策
+ proposer ：提案提议者（至少一个）
+ acceptor ：提案的表决者，即是否accept该提案，只有超过半数以上的acceptor接受了提案，该提案才被认为被“选定”（至少三个，必须单数）
+ learners ：提案的学习者，当提案被选定后，其同步执行提案，不参与决策

paxos算法的思想是，proposer 将发起提案（value）给所有 accpetor，超过半数 accpetor 获得批准后，proposer将提案写入 accpetor 内，最终所有 accpetor 获得一致性的确定性取值，且后续不允许再修改。learners只能“学习”被批准的提案。

Paxos算法分为两个阶段：prepare阶段、accept阶段，这两个阶段是针对proposer的，多个proposer进入accpet的时间具有先后顺序。

Prepare阶段

1. proposer提出一个提案，编号为N,发送给所有的acceptor。（Proposal Number：提议编号，可理解为提议版本号，要求不能冲突，每次生成必须是递增的）
2. 每个acceptor都保存自己的accept的最大提案编号maxN，当acceptor收到prepare(N)请求时，会比较N与maxN的值，若N小于maxN,则提案已过时，拒绝prepare(N)请求。若N大于等于maxN，则接受提案，并将该acceptor曾经接受过的编号最大的提案Proposal(myid,maxN,value)反馈给proposer：其中myid表示acceptor的标识id，maxN表示接受过的最大提案编号maxN，value表示提案内容。若当前acceptor未曾accept任何提议，会将proposal(myid,null,null)反馈给提议者。

acceptor在接收提案之后做出两个保证（Promise）：

1. 不再接受Proposal Number小于等于（注意：这里是<= ）当前请求的Prepare请求。
2. 不再接受Proposal Number小于（注意：这里是< ）当前请求的Propose请求。

accept 阶段

1. proposal发出prepare(N),若收到超过半数acceptor的反馈，proposal将真正的提案内容proposal(N,value)发送给acceptor。
2. acceptor接受提议者发送的proposal(N,value)提案后，会比较自己曾经accept过的最大提案编号maxN和反馈过的prepare的最大编号，若N大于这两个编号，则当前表决者accept该提案，并反馈给提议者。否则拒绝该提议。（最后确认的提议基本上就是版本号最新的提议，而版本号最新的提议内容永远是被大多数acceptor接收提案内容）

被拒绝的Proposer可以重新进入Prepare阶段，并将自己的提案编号自增。

Basic Paxos存在活锁问题，两个Proposers交替Prepare成功，而Accept失败，形成活锁（Livelock）。

Multi-Paxos

Multi-Paxos引入了Leader概念，它是唯一的Proposer，所有的请求都需经过Leader。

Multi-Paxos首先需要选举Leader，Leader的确定也是一次决议的形成，所以可执行一次Basic Paxos实例来选举出一个Leader。 选出Leader之后只能由Leader提交Proposal，在Leader宕机之后服务临时不可用，需要重新选举Leader继续服务。在系统中仅有一个Leader进行Proposal提交的情况下，Prepare阶段可以跳过。

Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例，从而使得Leader的连续提交只需要执行一次Prepare阶段，后续只需要执行Accept阶段，将两阶段变为一阶段，提高了效率。为了区分连续提交的多个实例，每个实例使用一个Instance ID标识，Instance ID由Leader本地递增生成即可。

Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性，这样的场景即退化为Basic Paxos。

Chubby和Boxwood均使用Multi-Paxos。ZooKeeper使用的ZAB也是Multi-Paxos的变形。

Raft

之前写的博客Redis主从复制、哨兵、集群详解中，redis的哨兵机制sentinel就是使用的raft思想，有leader sentinel和leader选举。

Raft基于Multi-Paxos思想，它把Multi-Paxos划分为三个子问题：
+ Leader Election：Leader的选举
+ Log Replication：leader同步log到其他节点
+ safety：保证被复制到大多数节点的日志不会被回滚

Raft定义的角色：
+ Leader：
+ Follower：
+ Candidate：如果Leader失效（宕机），follower中会产生candidate竞选leader

leader会不停的给follower发心跳消息，表明自己的存活状态。如果leader故障，follower会在一段时间内没有收到leader的心跳包，过了超时时间那么follower会转换成candidate，重新选出leader。

raft官方参考：

https://raft.github.io/

http://thesecretlivesofdata.com/raft/

Leader Election

leader选举的过程：

• 增加节点本地的 current term ，切换到candidate状态
• 投自己一票
• 并行给其他节点发送 RequestVote RPCs
• 等待其他节点的回复
• 在这个过程中，根据来自其他节点的消息，可能出现三种结果
  • 收到majority的投票（含自己的一票），则赢得选举，成为leader
  • 被告知别人已当选，那么自行切换到follower
  • 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举

第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。

而一个节点是否给其他节点投票的原则是
+ 对方term（任期） 和 log 都至少和自己的一样新
+ 先到先得

如果出现平票的情况，各候选人会产生一个随机的timeout之后重新发起竞选，依据先到先得原则不会再平票。（并且很多实现是需要节点个数为奇数）

log replication

当有了leader，系统应该进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。

leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command。下一次的的心跳包follower给leader返回ack，leader再把响应返回给请求发起者（Client）。

safety

Follower 宕机

当 leader 在 commit log 时, 某 follower 宕机，然后这个 follower 后来被选为 leader,它会覆盖掉现在 follwer 那些已经 committed log, 由于这些 log 是已经执行过的,所以结果不同的机器就执行不同的指令. 在选举过程中,再加多一个限制就可以防止这种情况发生, 即:

Leader completeness property:
对于任意一个 term, leader 都要包含所有在之前 term 里 committed 的 log。

Leader 宕机

数据到达Leader节点前

这个阶段 Leader 挂掉不影响一致性

数据到达Leader节点，但未复制到Follower节点

这个阶段 Leader 挂掉，数据属于未提交状态，Client 不会收到 Ack 会认为超时失败可安全发起重试。Follower 节点上没有该数据，重新选主后 Client 重试重新提交可成功。原来的 Leader 节点恢复后作为 Follower 加入集群重新从当前任期的新 Leader 处同步数据，强制保持和 Leader 数据一致。

数据到达Leader节点，成功复制到所有Follower节点，但还未向Leader响应接收

这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态（Uncommitted）但保持一致，重新选出 Leader 后可完成数据提交，此时 Client 由于不知到底提交成功没有，可重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。

数据到达Leader节点，成功复制到部分Follower节点，但还未向Leader响应接收

这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为Leader 再强制同步数据到 Follower，数据不会丢失并最终一致。

数据到达Leader节点，成功复制到Follower所有或多数节点，数据在所有节点都处于已提交状态，但还未响应Client

这个阶段 Leader 挂掉，集群内部数据其实已经是一致的，Client 重复重试基于幂等策略对一致性无影响。

网络分区导致的脑裂情况，出现双 Leader

如果出现网络分区情况，可能会出现两边各推选出一个leader，但如果leader不能将log复制到大多数节点（majority），就不会给请求发起者返回成功消息，并让接收到自己日志复制的请求的节点回滚。（还有一个last_index, term_id作为leader竞选的依据，只有拥有最新的redo log的candidate才能成为leader）

网络恢复后旧的 Leader 发现集群中有更新任期（Term）的新 Leader 则自动降级为Follower 并从新 Leader 处同步数据达成集群数据一致。