区块链快速⼊门（三）——CFT（⾮拜占庭容错）共识算法
⼀、CFT简介
CFT（Crash Faul涮火锅的食材有哪些
t Tolerance），即故障容错，是⾮拜占庭问题的容错技术。
Paxos 问题是指分布式的系统中存在故障(crash fault)，但不存在恶意(corrupt)节点的场景(即可能消息丢失或重复，但⽆错误消息)下的共识达成问题，是分布式共识领域最为常见的问题。最早由Leslie Lamport⽤ Paxon 岛的故事模型来进⾏描述⽽得以命名。解决Paxos问题的算法主要有Paxos系列算法和Raft算法，Paxos算法和Raft算法都属于强⼀致性算法。
⼆、Paxos算法
1、Paxos算法产⽣背景
在常见的分布式系统中，总会发⽣诸如机器宕机或⽹络异常（包括消息的延迟、丢失、重复、乱序，⽹络分区）等情况。Paxos算法需要解决的问题就是如何在⼀个可能发⽣异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成⼀致，并且保证不论发⽣任何异常，都不会破坏整个系统的⼀致性。
Paxos算法⽤于解决分布式系统的⼀致性问题。
2、Paxos算法简介
1990年，Leslie Lamport 在论⽂《The Part-time Parliament》中提出了Paxos共识算法，在⼯程⾓度实现了⼀种最⼤化保障分布式系统⼀致性(存在极⼩的概率⽆法实现⼀致)的机制。Leslie Lamport作为分布式系统领域的早期研究者，因为相关成果获得了2013年度图灵奖。
Leslie Lamport在论⽂中将Paxos问题表述如下：
希腊岛屿Paxon上的执法者在议会⼤厅中表决通过法律（⼀次Paxos过程），并通过服务员（propor）传递纸条的⽅式交流信息，每个执法者会将通过的法律记录在⾃⼰的账⽬上。问题在于执法者和服务员都不可靠，他们随时会因为各种事情离开议会⼤厅（服务器拓机或⽹络断开），并随时可能有新的执法者进⼊议会⼤厅进⾏法律表决（新加⼊机器），使⽤何种⽅式能够使得表决过程正常进⾏，且通过的法律不发⽣⽭盾（对⼀个值达成⼀致）。
Paxos过程中不存在拜占庭将失眠怎么发朋友圈
军问题（消息不会被篡改）和两将军问题（信道可靠）。
Paxos是⾸个得到证明并被⼴泛应⽤的共识算法，其原理类似两阶段提交算法，进⾏了泛化和扩展，通过女孩怎么养
消息传递来逐步消除系统中的不确定状态。
作为后续很多共识算法(如 Raft、ZAB等)的基础，Paxos算法基本思想并不复杂，但最初论⽂中描述⽐较难懂，甚⾄连发表也⼏经波折。2001年，Leslie Lamport专门发表论⽂《Paxos Made Simple》进⾏重新解释，其对Paxos算法的描述如下：
Pha1
(a) A propor lects a proposal number n and nds a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promi not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.
Pha 2
(a) If the propor receives a respon to its prepare requests (numbered n) from a majority of acceptors, then it nds an accept request to each of tho acceptors for a proposal numbered n with a v香信菇
alue v , where v is the value of the highest-numbered proposal among the respons, or is any value if the respons reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.
Paxos算法⽬前在Google的Chubby、MegaStore、Spanner等系统中得到了应⽤，Hadoop中的ZooKeeper也使⽤了Paxos算法，但使⽤的算法是原始Paxos算法的改进算法。通常以Paxos算法为基础，在实现过程中处理实际应⽤场景中的具体细节，可以得到⼀个Paxos改进算法。
3、Paxos算法原理
Paxos算法的基本思路类似两阶段提交：多个提案者先要争取到提案的权利(得到⼤多数接受者的⽀持)；成功的提案者发送提案给所有⼈进⾏确认，得到⼤部分⼈确认的提案成为批准的结案。
Paxos协议有三种⾓⾊：Propor（提议者），Acceptor（决策者），Learner（决策学习者）。
Paxos 是⼀个两阶段的通信协议，Paxos算法的基本流程如下：
第⼀阶段Prepare：
A、Propor⽣成⼀个全局唯⼀的提案编号N，然后向所有Acceptor发送编号为N的Prepare请求。
B、如果⼀个Acceptor收到⼀个编号为N的Prepare请求，且N⼤于本Acceptor已经响应过的所有Prepare请求的编号，那么本Acceptor 就会将其已经接受过的编号最⼤的提案（如果有的话）作为响应反馈给Propor，同时本Acceptor承诺不再接受任何编号⼩于N的提案。
第⼆阶段 Accept
A、如果Propor收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么Propor就会发送⼀个针对[N,V]提案的Accept请求给半数以上的Acceptor。V就是收到的响应中编号最⼤的提案的value，如果响应中不包含任何提案，那么V由Propor⾃⼰决定。
B、如果Acceptor收到⼀个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号⼤于N的Prepare武当山下
请求做出过响应，Acceptor 就接受该提案。
Paxos 并不保证系统总处在⼀致的状态。但由光量子计算机
于每次达成共识⾄少有超过⼀半的节点参与，最终整个系统都会获知共识结果。如果提案者在提案过程中出现故障，可以通过超时机制来缓解。
Paxos 能保证在超过⼀半的节点正常⼯作时，系统总能以较⼤概率达成共识。
4、提案ID的⽣成算法
对于精彩的意思
提案ID的选择，《Paxos made simple》中提到的是让所有的Propor都从不相交的数据集合中进⾏选择。
Google的Chubby论⽂中给出提案ID的⽣成算法如下：假设有n个Propor，每个编号为ir(0<=ir<n)，Proposal编号的任何值奇耻大辱
s都应该⼤于它已知的最⼤值，并且满⾜：
s %n = ir => s = m*n + ir
Propor已知的最⼤值来⾃两部分：Propor⾃⼰对编号⾃增后的值和接收到Acceptor的拒绝后所得到的值。
以3个Propor P1、P2、P3为例，开始m=0，编号分别为0，1，2。
1） P1提交的时候发现了P2已经提交，P2编号为1 >P1的0，因此P1重新计算编号：new P1 = 1*3+1 = 4；
2） P3以编号2提交，发现⼩于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5。
5、Paxos算法的活锁
如果两个提案者恰好依次提出更新的提案，则导致活锁，系统会永远⽆法达成共识(实际发⽣概率很⼩)。活锁没有产⽣阻塞，但是⼀直⽆法达成⼀致。
活锁有三种解决⽅案：
A、在被打回第⼀阶段再次发起PrepareRequest请求前加⼊随机不同的英语单词
等待张小西
时间。
B、设置⼀个超时时间，到达超时时间后，不再接收PrepareRequest请求。
C、在Propor中选举出⼀个leader，通过leader统⼀发出PrepareRequest和AcceptRequest。
6、Paxos算法异常处理
Paxos算法在执⾏过程中会产⽣很多的异常情况：Propor宕机，Acceptor在接收Proposal后宕机，Propor接收消息后宕
机，Acceptor在Accept后宕机，Learner宕机，存储失败等等。
为保证Paxos算法的正确性，Propor、Aceptor、Learner都需要实现持久存储，以做到Server恢复后仍能正确参与Paxos处理。
Propor存储已提交的最⼤proposal编号、决议编号（instance id）。
Acceptor存储已承诺（promi）的最⼤编号、已接受（Accept）的最⼤编号和Value、决议编号。
Learner存储已学习过的决议和编号。
7、Paxos算法应⽤
Paxos算法只有两种情况下服务不可⽤:⼀是超过半数的Propor异常，⼆是出现活锁。前者可以通过增加Propor的个数来降低由于Propor异常影响服务的概率，后者本⾝发⽣的概率就极低。
Paxos是分布式系统⼀致性协议的基础，其它的协议（raft、zab等）都是Paxos协议的改进版本。Paxos侧重理论，实现Paxos⾮常困难。
微信后台⽣产级Paxos类库PhxPaxos实现：
基于Paxos算法的改进算法的资料集合：
三、三军问题
1、三军问题简介
三军问题的描述如下：
1） 1⽀红军在⼭⾕⾥扎营，在周围的⼭坡上驻扎着3⽀蓝军；
2） 红军⽐任意1⽀蓝军都要强⼤；如果1⽀蓝军单独作战，红军胜；如果2⽀或以上蓝军同时进攻，蓝军胜；
3） 三⽀蓝军需要同步他们的进攻时间；但他们惟⼀的通信媒介是派通信兵步⾏进⼊⼭⾕，在那⾥他们可能被俘虏，从⽽将信息丢失；或者为了避免被俘虏，可能在⼭⾕停留很长时间；
4） 每⽀军队有1个参谋负责提议进攻时间；每⽀军队也有1个将军批准参谋提出的进攻时间；很明显，1个参谋提出的进攻时间需要获得⾄少2个将军的批准才有意义；
5） 问题：是否存在⼀个协议，能够使得蓝军同步他们的进攻时间？
三军问题符合Paxos问题场景，参谋和将军需要遵循⼀些基本的规则：
1） 参谋以两阶段提交（prepare/commit）的⽅式来发起提议，在Prepare阶段需要给出⼀个提议编号；
2） 在Prepare阶段产⽣冲突，将军以提议编号⼤⼩来裁决，提议编号⼤的参谋胜出；
3） 参谋在Prepare阶段如果收到将军返回的已接受进攻时间，在Commit阶段必须使⽤返回的进攻时间；
2、两参谋先后提议场景
A、参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
B、3个将军收到参谋1的提议，由于之前还没有保存任何编号，因此把（编号1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（ok）；
C、参谋1收到⾄少2个将军的回复，再次派通信兵带信给3个将军，内容为（编号1，进攻时间1）；
D、3个将军收到参谋1的时间，把（编号1，进攻时间1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；
E、参谋1收到⾄少2个将军的（Accepted）内容，确认进攻时间已经被⼤家接收；
F、参谋2发起提议，派通信兵带信给3个将军，内容为（编号2）；
G、3个将军收到参谋2的提议，由于（编号2）⽐（编号1）⼤，因此把（编号2）保存下来，避免遗忘；⼜由于之前已经接受参谋1的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
H、参谋2收到⾄少2个将军的回复，由于回复中带来了已接受的参谋1的提议内容，参谋2因此不再提出新的进攻时间，接受参谋1提出的时间；
3、两参谋交叉提议场景
1） 参谋1发起提议，派通信兵带信给3个将军，内容为（编号1）；
2） 3个将军的情况如下
A、将军1和将军2收到参谋1的提议，将军1和将军2把（编号1）记录下来，如果有其他参谋提出更⼩的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
B、负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
3） 参谋2在同⼀时间也发起了提议，派通信兵带信给3个将军，内容为（编号2）；
4） 3个将军的情况如下
A、将军2和将军3收到参谋2的提议，将军2和将军3把（编号2）记录下来，如果有其他参谋提出更⼩的编号，将被拒绝；同时让通信兵带信回去，内容为（ok）；
B、负责通知将军1的通信兵被抓，因此将军1没收到参谋2的提议；
5） 参谋1收到⾄少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号1，进攻时间1）；
6） 2个将军的情况如下
A、将军1收到了（编号1，进攻时间1），和⾃⼰保存的编号相同，因此把（编号1，进攻时间1）保存下来；同时让通信兵带信回去，内容为（Accepted）；
B、将军2收到了（编号1，进攻时间1），由于（编号1）⼩于已经保存的（编号2），因此让通信兵带信回去，内容为（Rejected，编号2）；
7） 参谋2收到⾄少2个将军的回复，再次派通信兵带信给有答复的2个将军，内容为（编号2，进攻时间2）；
8） 将军2和将军3收到了（编号2，进攻时间2），和⾃⼰保存的编号相同，因此把（编号2，进攻时间2）保存下来，同时让通信兵带信回去，内容为（Accepted）；
9） 参谋2收到⾄少2个将军的（Accepted）内容，确认进攻时间已经被多数派接受；
10） 参谋1只收到了1个将军的（Accepted）内容，同时收到⼀个（Rejected，编号2）；参谋1重新发起提议，派通信兵带信给3个将军，内容为（编号3）；
11） 3个将军的情况如下
A、将军1收到参谋1的提议，由于（编号3）⼤于之前保存的（编号1），因此把（编号3）保存下来；由于将军1已经接受参谋1前⼀次的提议，因此让通信兵带信回去，内容为（编号1，进攻时间1）；
B、将军2收到参谋1的提议，由于（编号3）⼤于之前保存的（编号2），因此把（编号3）保存下来；由于将军2已经接受参谋2的提议，因此让通信兵带信回去，内容为（编号2，进攻时间2）；
C、 负责通知将军3的通信兵被抓，因此将军3没收到参谋1的提议；
12） 参谋1收到了⾄少2个将军的回复，⽐较两个回复的编号⼤⼩，选择⼤编号对应的进攻时间作为最新的提议；参谋1再次派通信兵带信给有答复的2个将军，内容为（编号3，进攻时间2）；
