Paxos & Raft

节点B任期编号：1

节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举，篡权。

接受（Accept）阶段

如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。

日志：    索引， 提案编号，提案命令

节点B任期编号：0超时时间：200ms

跟随者

接收者

节点C

候选人

选举领导者的过程

在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了

节点B任期编号：0

当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，将进行这样的处理：     由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。     节点 C 也是如此，它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。

随机超时时间：1. 跟随者等待领导者心跳信息超时的时间间隔，是随机的；2. 如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔，是随机的。

5：  提案编号     准备阶段 发送7：  提案       接受阶段发送

和重复执行 Basic Paxos 相比，Multi-Paxos 引入领导者节点之后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。

什么是任期：Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识，比如节点 A 的任期编号是 1。任期编号是随着选举的举行而变化的1. 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加为 1。2. 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编号更新为 1。任期编号的大小，会影响领导者选举和请求的处理：1. 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。2. 如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。

兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法。多次执行 Basic Paxos 实例，来实现一系列值的共识，存在问题：1. 如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。2.  2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。如何解决上面的 2 个问题呢？可以通过引入领导者和优化 Basic Paxos 执行来解决。

领导者

client2

集群中没有领导者，而节点 A 的等待超时时间最小（150ms），它会最先因为没有等到领导者的心跳信息，发生超时。这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。

思考： 节点间是如何通讯的呢？什么是任期呢？选举有哪些规则？随机超时时间又是什么？

节点C任期编号：0超时时间：300ms

节点A

当节点 A、B 收到提案编号为 5 的准备请求，和节点 C 收到提案编号为 1 的准备请求的时候，将进行这样的处理过程：       当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。       当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。

client1

发送心跳

总结：1. Raft 算法和兰伯特的 Multi-Paxos 不同之处，主要有 2 点。首先，在 Raft 中，不是所有节点都能当选领导者，只有日志较完整的节点（也就是日志完整度不比半数节点低的节点），才能当选领导者；其次，在 Raft 中，日志必须是连续的。2. Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导，也极大地减少了选举失败的情况。3. 本质上，Raft 算法以领导者为中心，选举出的领导者，以“一切以我为准”的方式，达成值的共识，和实现各节点日志的一致。

节点A任期编号：1

set  V=3

如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号。

V

Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态，在理解和算法实现上都相对容易许多。Raft 算法是现在分布式系统开发首选的共识算法。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。领导者就是 Raft 算法中的霸道总裁，Raft 算法是强领导者模型，集群中只能有一个“霸道总裁”。https://raft.github.io/http://thesecretlivesofdata.com/raft/Raft 算法支持 3 种状态：领导者（Leader）跟随者（Follower）候选人（Candidate）跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”

节点间如何通讯 ：在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的 RPC：1. 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；2. 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

请求投票

当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段

节点C任期编号：0

兰伯特提出的 Paxos 算法包含 2 个部分：一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。Paxos的角色：提议者（Proposer）：提议一个值，用于投票表决。接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值。学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。

节点A任期编号：1选票：3

写请求

set  V=7

提议者/接收者

投票给节点A

整个共识协商是分 2 个阶段进行的

节点C任期编号：1

节点B

client3

准备（Prepare）阶段

提案编号的大小代表着优先级，根据提案编号的大小，接受者保证三个承诺，具体来说：1.如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；2.如果接受请求的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；3.如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。

节点A任期编号：1选票：1

Basic Paxos 的容错能力，源自“大多数”的约定，当少于一半的节点出现故障的时候，共识协商仍能正常工作。

准备阶段：  请求---响应接受阶段：    请求---响应

首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求

实现 Multi-Paxos 算法的时候，需要实现如何选举领导者

节点A任期编号：0超时时间：150ms

已经达成共识

选举是跟随者发起的，推举自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标，是为了保证在一个给定的任期内最多只有一个领导者。选择的规则：1. 领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举。2. 如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举。3. 在一次选举中，赢得大多数选票的候选人，将晋升为领导者。4. 在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举。5. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。6. 日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。

领导者（Leader）

在初始状态下，集群中所有的节点都是跟随者的状态。Raft 算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。

优化 Basic Paxos 执行

最终结果： 3，还是7

思考： 如何在多个节点间确定某变量的值？当多个客户端同时修改分布式集群节点上的值，如何达成共识，确保各节点上的值一致？