一、分布式理论:一致性算法 Paxos

1. Paxos解决了什么问题？

Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中，快速且正确地在集群内部对某个数据的值达成一致

2. 概念

提案proposal

• 提案编号（proposal ID）
• 提案的值（value）

Paxos的三种角色

• Proposer提案人
• Acceptor决策者
• Learners终决策的学习者 （就是最终将决策完的value，落实到下来。到物理机）

3、Paxos的流程

提案要求

对于任意的Mn和Vn,如果提案[Mn,Vn]被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个：

• 要么S中每个Acceptor都没有接受过编号小于Mn的提案。
• 要么S中所有Acceptor批准的所有编号小于Mn的提案中，编号大的那个提案的value值为Vn

proposer生成提案

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

（a）Acceptor向Proposer承诺保证不再接受任何编号小于N的提案。

（b）如果Acceptor已经接受过提案，那么就向Proposer反馈已经接受过的编号小于N的，但为大编号的提案的值

我们将该请求称为编号为N的Prepare请求

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

生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。我们称该请求为Accept请求

accept接受提案

一个Acceptor可能会受到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求作出响应的条件分别如

• Prepare请求：Acceptor可以在任何时候响应一个Prepare请求
• Accept请求：在不违背Accept现有承诺的前提下，可以任意响应Accept请求

算法优化

Acceptor忽略编号小于当前最大变好的Prepare请求

4. Learner学习被选定value

方案一：

Learner获取一个已经被选定的提案的前提是，该提案已经被半数以上的Acceptor批准，因此，简单的做法就是一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner

很显然，这种做法虽然可以让Learner尽快地获取被选定的提案，但是却需要让每个Acceptor与所有的Learner逐个进行一次通信，通信的次数至少为二者个数的乘积

方案二：

另一种可行的方案是，我们可以让所有的Acceptor将它们对提案的批准情况，统一发送给一个特定的Learner（称为主Learner）, 各个Learner之间可以通过消息通信来互相感知提案的选定情况，基于这样的前提，当主Learner被通知一个提案已经被选定时，它会负责通知其他的learner

在这种方案中，Acceptor首先会将得到批准的提案发送给主Learner,再由其同步给其他Learner。因此较方案一而言，方案二虽然需要多一个步骤才能将提案通知到所有的learner，但其通信次数却大大减少了，通常只是 Acceptor和Learner的个数总和，但同时，该方案引入了一个新的不稳定因素：主Learner随时可能出现故障

方案三：

在讲解方案二的时候，我们提到，方案二大的问题在于主Learner存在单点问题，即主Learner随时可能出现故 障，因此，对方案二进行改进，可以将主Learner的范围扩大，即Acceptor可以将批准的提案发送给一个特定的 Learner集合，该集合中每个Learner都可以在一个提案被选定后通知其他的Learner。这个Learner集合中的 Learner个数越多，可靠性就越好，但同时网络通信的复杂度也就越高

5. 如何保障Paxos算法的活性

假设存在这样一种极端情况，有两个Proposer依次提出了一系列编号递增的提案，导致终陷入死循环，没有 value被选定

解决：通过选取主Proposer，并规定只有主Proposer才能提出议案。这样一来只要主Proposer和过半的Acceptor 能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准，这样通过选择一个主Proposer，整套Paxos算法就能够保持活性

三、分布式理论:一致性算法 Raft

概念

Raft 是一种为了管理复制日志的一致性算法。

Raft将一致性算法分解成了3模块

1. 领导人选举
2. 日志复制
3. 安全性

领导人角色

• 领导者(leader)：处理客户端交互，日志复制等动作，一般一次只有一个领导者
• 候选者(candidate)：候选者就是在选举过程中提名自己的实体，一旦选举成功，则成为领导者
• 跟随者(follower)：类似选民，完全被动的角色，这样的服务器等待被通知投票

节点异常

• leader不可用
• follower不可用
• 多个candidate或多个leader
• 新节点加入集群

异常的解决

1. leader 不可用；

• 一般情况下，leader 节点定时发送 heartbeat 到 follower 节点。
• 由于某些异常导致 leader 不再发送 heartbeat ，或 follower 无法收到 heartbeat 。
• 当某一 follower 发生 election timeout 时，其状态变更为 candidate，并向其他 follower发起投票。
• 当超过半数的 follower 接受投票后，这一节点将成为新的 leader，leader 的步进数加1并开始向follower同步日志
• 当一段时间之后，如果之前的 leader 再次加入集群，则两个 leader 比较彼此的步进数，步进数低的leader将切换自己的状态为follower。
• 较早前leader中不一致的日志将被清除，并与现有 leader中的日志保持一致。

2. follower 不可用；

• 集群中的某个 follower 节点发生异常，不再同步日志以及接收 heartbeat。
• 经过一段时间之后，原来的 follower 节点重新加入集群。
• 这一节点的日志将从当时的 leader 处同步。

3. 多个 candidate 或多个 leader；

• 初始状态下集群中的所有节点都处于 follower 状态。
• 两个节点同时成为 candidate 发起选举。
• 两个 candidate 都只得到了少部分 follower 的接受投票。
• candidate 继续向其他的 follower 询问。
• 由于一些 follower 已经投过票了，所以均返回拒绝接受。
• candidate 也可能向一个 candidate 询问投票。
• 在步进数相同的情况下，candidate 将拒绝接受另一个 candidate 的请求。
• 由于第一次未选出 leader，candidate 将随机选择一个等待间隔（150ms ~ 300ms）再次发起投 票。
• 如果得到集群中半数以上的 follower 的接受，这一 candidate 将成为 leader。
• 稍后另一个 candidate 也将再次发起投票。
• 由于集群中已经选出 leader，candidate 将收到拒绝接受的投票。
• 在被多数节点拒绝之后，并已知集群中已存在 leader 后，这一 candidate 节点将终止投票请求、切换为 follower，从 leader 节点同步日志。

日志复制过程

• 客户端的每一个请求都包含被复制状态机执行的指令。
• leader把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让他们复制这条信息。
• 跟随者响应ACK,如果 follower 宕机或者运行缓慢或者丢包，leader会不断的重试，直到所有的 follower 终都复制了所有的日志条目。
• 通知所有的Follower提交日志，同时领导人提交这条日志到自己的状态机中，并返回给客户端