背景

在常见的分布式系统中，总会发生诸如机器宕机或网络异常（包括网络消息的延迟、丢失、重复、乱序，还有网络分区）等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个状态（日志、数据、命令等）的值达成一致，并且保证不论发生以上任何异常，都不会破坏整个系统的一致性。

一、拜占庭将军问题

拜占庭将军问题提供了对分布式共识问题的一种情境化描述。
是分布式系统领域最复杂的容错模型，他描述如何在存在恶意行为（消息篡改或者伪造）的情况下使分布式系统达成一致，是我们理解分布式一致性协议和算法的重要基础。参考：https://zhuanlan.zhihu.com/p/107439021

分析

将军数量可以任意，假如有将军数量为三，分布在不同的地方，他们之间可以两两通过消息互相通信，目的：最终达成一致进攻或者撤退的共识。

（1）如果三个将军都是忠诚的（对于某个将军发送给其他将军的消息总是一致的），那么最终都会达成一致进攻或者撤退的共识。

（2）如果三个将军存在一个敌将，敌将会散布虚假的进攻、撤退消息，目的：为了就是破坏共识。

• 以0和1表示撤退、进攻的消息。
• 以组合**(out：发出,in：收到)**表示某个将军发出、收到消息的状态。那么对于某个将军某次的协商状态：(0,0)、(0,1)、(1,0)、(1,1)
• 以A、B、C表示三位将军

下图以C为叛将为例，C干扰A发送进攻信号，导致将军A单独进攻。

其实总共有6种协商不一致的情况，对于叛军可能是A、B、C任一个，因此共三种情况。
而对于将军A、B不一致的情况为A(0,1) and B(1,0) 、A(1,0) and B(0,1)。
ps：如果将军A、B总是一致的，那么无论叛军C如何干扰都没用。

推论

假定总共存在m位叛将，那么至少总将领数为 3m + 1，那么最终总能达成一致的行动计划。
值的注意的是, 在这个算法中, 叛将人数_m_是已知的, 且叛将人数_m_决定了迭代递归的次数（按照叛将拆分小组，保证每个小组内一个叛将）
即叛将数_m_决定了进行作战信息协商的轮数, 如果存在_m_个叛将, 则需要进行_m+1_轮作战信息协商. 这也是上述存在1个叛将时需要进行两轮作战信息协商的原因.

解决方案

Leslie Lamport在论文中给出了两种拜占庭将军问题的解决方案, 也就是证明3m + 1的问题，即对于二忠一叛的条件下，想要总是达到一致性是不可能的。

• 口信消息型解决方案(A solution with oral message)
• 签名消息型解决方案(A solution with signed message).

1、口信型解决方案

口信消息规定

• 任何已经发送的消息都将被正确传达
• 消息的接收者知道是谁发送了消息
• 消息的缺席可以被检测

通过规定可得知，口信消息不能篡改但是可以被伪造，由拜占庭问题的3m+1得出，可以以3忠1叛推导，首先发送消息的为指挥官，其余为副官，需要做两轮协商，没收到作战消息就撤退。

2、签名型解决方案

简言之就是忠将具有识别消息是否被篡改的能力，根据虚假信息找出叛将军。
在口信消息定义的基础上增加定义

• 忠诚将军的签名无法伪造，消息无法被篡改和伪造（口信消息定义是消息不能篡改但是可以被伪造）
• 任何人都能验证将军签名的真伪

还是以三将军为例，三个将军2个忠一个叛

同样可以类比多忠多叛的情况。
在消息篡改能被发现的条件下

• 如果莫将发出不一致的消息，直接被判别为叛将
• 如果某将发出消息一致，那么就证明是忠将，如果收到其他将军转发的消息和自己收到的不一致，那么就找出了叛将

因此，签名消息型解决方案可以处理任何数量叛将的场景，因为三个一小组在消息不能篡改的前提下，总能找出叛将。

总结

拜占庭将军问题提供了对分布式共识问题的一种情景化描述，为理解和分类现有众多分布式一致性协议和算法提供了框架，现有的分布式一致性算法主要分为两类

• 一类是故障容错算法：即非拜占庭算法，解决的是分布式系统存在故障但是不存在被恶意攻击的场景下的共识问题，主要针对消息丢失、重复等问题，面对消息被篡改就无力了，一般用于局域网场景下的分布式算法，如Paxos、Raft、ZAB协议等。
• 一类是拜占庭算法：既可以解决分布式系统故障，又可解决恶意攻击的问题，如在数字货币的区块链技术中，属于此类算法有PBFT、PoW算法。

二、Paxos算法

参考：https://www.cnblogs.com/linbingdong/p/6253479.html
目的就是保证所有分布式节点（进程）上面某各状态（值）的一致性。具体就是通过协商保证只有一个value会被选定，当value被选定后，分布式节点（进程）最终也能获取到被选定的value。

3.1、单个Acceptor推导

也是最简单的方案，从众多实例选出一个Acceptor接受者。

只有一个Acceptor接受者，其他的Proposer将自己的value发送给Acceptor，Acceptor选出一个一致性value最为最终的一致性value，其他Properer在变成Learner学习这个一致性value。

不足：存在单Acceptor故障

3.2、多个Acceptor推导

单个Acceptor存在单点故障，需要拓展为多个。

多个Acceptor如何选定一个value？

1、约束Acceptor接受第一个propose value作为一致性value，并且达到半数Acceptor选定的proopose value才会作为最终的一致性value。存在问题：多个不同value被选定的情况

2、约束每个Acceptor需要能够接受多个不同的value，也就是对propose value编号。如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v。（即已经出现半数Accepor接受propose value并且选定，剩余部分Acceptor也需要提出接受propose value选定）

存在问题：假设总有5个Acceptor，Propooser2提出 propose value = (M1,V1)，假如Acceptor2～Acceptor5接受，他们都认为V1被选中。但是Acceptor1刚从宕机恢复，需要满足约束1，即接受Acceptor1的propose value = [M2,V2]，此时会造成与约束2的矛盾情形。

分析上述矛盾情形，而而从Accepor角度是无法满足约束1、2同时成立的。

3、约束某个propose value = v的提案被选定后，剩下Proposer提出的编号更高的提案的propose value = v。

为了满足约束3，需要Proposer提出自己的propose value的时候，先去Learn已经被选定或者是可能被选定的value，然后以此value作为自己准备提出的propose value，这个阶段成为Prepare阶段。如果没有propose value被选定，Proposer才可以自己决定value的值。这样才能达成一致。

3.3、提案生成算法

上文提到的Prepare阶段

1、Proposer选择一个新的提案编号N，然后向某个Acceptor集合（半数以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response）。

• (a) 向Proposer承诺保证不再接受任何编号小于N的提案。
• (b) 如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于N的最大编号的提案。（这里就是Propposer的Learn过程）

我们将该请求称为编号为N的Prepare请求，这个请求就是选取合适的编号。

2、如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为N，Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案，那 么此时V就可以由Proposer自己选择。

生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。（注意：此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合）

3.4、提案接受算法

Acceptor可以忽略任何一个请求，包括Prepare和Accept请求，而不用担心破坏算法的安全性。

下面讨论响应情形，当Acceptor接收到一个编号为N的Prepare请求：

• 如果N大于之前响应过的所有Prepare请求编号：需要响应给之前接受过编号最大的提案供Proposer去学习。
• 如果N小于之前响应过的所有Prepare请求编号：直接忽略或者返回error。

然后Proposer根据响应调整编号以及propose value，然后发送Accept请求

Paxos算法的两个阶段

• 阶段一：
  • (a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
  • (b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
• 阶段二：
  • (a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
  • (b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

简单理解就是Proposer首先发送prepare请求询问各个Acceptor自己来的是不是最早的（编号最小的）

• 不是最早的而是最晚的，Acceptor将来的上一个紧邻的人时间告诉Proposer。
• 是最早的，Acceptor承诺只接受更晚来时间的询问。

如果收到了半数以上Acceptor的响应，那么确定编号为N，之后propose value 从响应中提案选一个最大的（如果响应都没提案，那么自己选定），然后再次拿着[N,V]请求全部的Acceptors请求他们接受自己提案。

三、Raft算法

参考：https://cloud.tencent.com/developer/article/1525566

Raft是用于管理复制日志的一致性算法。它的效果相当于(multi-)Paxos，跟Paxos一样高效，但结构与Paxos不同。这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。

3.1、概述

Raft是用于管理复制日志的一致性算法。它的效果相当于(multi-)Paxos，跟Paxos一样高效，但结构与Paxos不同。这使得Raft比Paxos更容易理解，也为构建实用系统提供了更好的基础。
它将一致性分解为多个子问题：

• Leader选举（Leader election）
• 日志同步（Log replication）
• 安全性（Safety）
• 日志压缩（Log compaction）
• 成员变更（Membership change）

同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。Raft将系统中的角色分为

• 领导者（Leader）：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。
• 跟从者（Follower）：接受并持久化Leader同步的日志。
• 候选人（Candidate）：不一致情况才会出现的临时角色。

Raft要求系统在任意时刻最多只有一个Leader、正常工作期间只有Leader、Followers。
Raft算法将时间分为一个个任期term，每个term的开始都是Leader选举

3.2、Leader的选举

从整体集群来看，Raft算法将时间分为一个个的任期（term），每一个term的开始都是Leader选举。在成功选举Leader之后，Leader会在整个term内管理整个集群。如果Leader选举失败，该term就会因为没有Leader而结束。

从集群的某个服务器节点来看，Raft通过心跳机制来触发Leader选举，对于某个节点来说，会有一个固定的触发选举的超时时间，当服务器启动的时候，他们以Follower的身份开始进行一次选举
1、观察情况：

• 当固定的触发选举超时时间内，自己是Follower并且从Leader、Candiate接受有效的RPC请求，自己就会保持Follower状态。
• 当超过固定的触发选举超时时间，自己是Follower并且没有收到Leader、Candiate有效的RPC请求，自己就会等待随机的一个时间发起一次Leader选举。

2、想法：也就是某个Follower在一个时间段（选举超时时间）内没收到Leader、Candiate的心跳信息，就会认为Leader挂了，并且没有其他Follower正在选举，就自己想当Leader。
3、行动：等待一段随机的时间，将term加1，将自己变为Candiate，然后发起一次选举，具体就是先给自己投一票，然后想其他服务器发送RequestVote RPC 请求拉票。

4、最终的结果有三

• 赢了：赢得了多数的vote，成功选举Leader。
• 输了：收到了Leader的消息，表示其他服务器抢先当上了Leader。
• 平局：势均力敌，选票数不足，等待下一次选举机会。

无论是否选举出了Leader，上述步骤就是一个term。

假如是某个节点自己的问题导致不能和Leader和其他节点通信了，经过上述上选举过程，最终结果为平局，等待若工个选举，最后能接收到Leader的心跳，经历Follower—>Candiate—>Follower。

3.3、日志同步

Leader选出后，Leader就开始接受client请求，把请求信息记录在Log entries，然会AppendEntries RPC广播发给其他非Leader节点。
当这条日志被复制到大多数机器上，如果不成功，就一直重试直到大多数Followers最终存储了所有的日志条目，Leader将这条日志操作持久化到自己状态机，并向client返回执行的结果。

日志的格式：编号log index 和 term标志某一日志条目Log entries。方格内部为term、日志指令。

一般情况下Leader和Followers的日志需要保持一致，除非Leader崩溃，日志的特点

• 如果不同日志中，两个日志条目的log index和term是一致的，那么该日志存储的命令是相同的，特性来源：Leader在一个term内给log index 最多创建一条日志条目，同时该条目在日志中的位置也不会改变。
• 如果不同日志中，两个日志条目的log index和term是一致的，那么他们之前地所有日志条目都是相同的。特性来源：日志条目的简单一致性检查，Leader每次会发送的日志条目和紧邻的前面的日志条目，如果Follower没在他的日志中找到log index和term都相同的日志，他就会拒绝新的日志条目。

下图为Leader和Followers日志条目不同的情况，方格内为term。一个Follower可能会丢失掉Leader上的一些条目（日志长度不一致，a为9，b为4 … ），也有可能包含一些Leader没有的条目，也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。

此时Leader新的日志记录的logindx = 11，term = 8。

• 对于（a）尝试到lterm，index = 9，6，发现前缀一样，则对于（a）需要补全log index = 9以后的日志条目
• 对于（b）尝试term ，index = 4，4就要补全log index = 4以后的日志条目。
• …

Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。也就是每次都是一致前缀覆盖。

3.4、安全性

两条限制保证安全性，也就是上述日志同步的正确性

• 拥有最新的已提交的log entry的Folower才有资格成为Leader：这个保证依赖投票时候的RequestVote RPC时候，要带上自己的最后一条日志term和log index，其他节点收到消息时，发现自己的日志比请求中携带的日志更新，则拒绝投票（认为自己更适合做Leader）。比较的日志新程度term优先级高于log index。
• Leader只能推进提交commit index来提交当前term的已经复制到大多数服务器上的日志。旧的term只能覆盖提交。主要是为了防止不同term换了Leader但是已提交日志又被覆盖的情况。

如下图，举例不遵守安全性导致日志被覆盖的情况。方格内为term，以（term，index）记为一次日志

• term = 1，S1为Leader，将（1，1）同步到（S1、S2、S3、S4、S5）
• term = 2，在阶段（a），S1为Leader，且S1写入日志（term，index）为（2，2），（不考虑安全性2）并且日志被同步写入了S2，此时term = 2
• term = 3，在阶段（b），S1离线，触发新的选主选中了S5，此时term = 2 + 1 = 3，S5尚未将日志推送到Followers就离线了，进而触发了一次新的选主。
• term = 4，在阶段（c），之前离线的S1经过重新上线后被选中变成Leader，此时系统term为4，此时S1会将自己的日志同步到Followers，按照上图就是将日志（2， 2）同步到了S3，而此时由于该日志已经被同步到了多数节点（S1, S2, S3），因此，此时日志（2，2）可以被提交了，但是（4，3）日志未被提交。
• term = 5，在阶段（d），S1又下线了，触发一次选主，此时S5的日志最新可能被选为主，因为term = 5 > 4 and 最新的日志为（3，2）比大多数节点（S2,S3,S4）都新，然后S5会将自己的日志更新到Followers，于是S2、S3中已经被提交的日志（2，2）被截断了。

增加上述限制后，也就是在（c）阶段，即使日志（2，2）已经被大多数节点（S1、S2、S3）确认了，但是它不能被提交，因为它是来自之前term = 2 的日志（就是在这个阶段，S5产生了term = 3，导致S1的term = 2不是最新的），直到S1在当前term = 4产生的日志（4， 4）被大多数Followers确认，S1方可提交日志（4，4）这条日志，当然，根据Raft定义，（4，4）之前的所有日志也会被提交。此时即使S1再下线，重新选主时S5不可能成为Leader，因为它没有包含大多数节点已经拥有的日志（4，4）。

简言之，还是以term大的为准，同步到大多数节点并且没有比当前Leader更大的term，才可同步日志，另term相同的才会以log index为准。

3.5、日志压缩

在实际的系统中，不能让日志无限增长，否则系统重启时需要花很长的时间进行回放，从而影响可用性。Raft采用对整个系统进行snapshot来解决，snapshot之前的日志都可以丢弃。

每个副本独立的对自己的系统状态进行snapshot，并且只能对已经提交的日志记录进行snapshot。

Snapshot中包含以下内容：

• 日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
• 系统当前状态。

做snapshot既不要做的太频繁，否则消耗磁盘带宽， 也不要做的太不频繁，否则一旦节点重启需要回放大量日志，影响可用性。推荐当日志达到某个固定的大小做一次snapshot。
做一次snapshot可能耗时过长，会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。