分布式与一致性协议之Raft算法(二)

Raft算法

什么是任期

我们知道，议会选举中的领导者是有任期的，当领导者任命到期后，需要重新再次选举。Raft算法中的领导者也是有任期，每个任期由单调递增的数字(任期编号)标识。比如，节点A的任期编号是1。任期编号会随着选举的举行而变化，分析如下。

• 1.跟随者在领导者心跳信息超时并推荐自己为候选人时，会增加自己的任期编号，比如节点A的当前任期编号为0，那么在推荐自己为候选人时，它会将自己的任期编号增加为1。
• 2.如果一个服务器节点发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点B的任期编号是0，当受到来自节点A的请求投票RPC消息时，因为消息中包含了节点A的任期编号，且编号为1，所以节点B将把自己的编号更新为1.

与现实议会选举中的领导者的任期不同，Raft算法中的任期不只是指时间段，而且任期编号的大小会影响领导者选举和请求的处理。

• 1.Raft算法中约定，如果一个候选人或者领导者发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B收到来自新领导者的包含任期编号为4的心跳信息，那么节点B将立即恢复成跟随者状态
• 2.Raft算法中还约定，如果一个节点接收到一个包含较小的任期编号值得请求，那么它会直接拒绝这个请求。比如任期编号为4的节点C在收到任期编号为3的请求投票RPC消息时，会拒绝这个消息。可以看到，Raft算法中的任期比议会选举中的任期要复杂一些。同样，Raft算法中的选举规则的内容也会比较多

选举有哪些规则

在议会选举中，比成员身份、领导者的任期还重要的就是选举的规则，比如一人一票、弹劾制度等。“无规矩不成方圆”，Raft算法中也约定了选举规则，主要包含以下内容。

• 1.领导者周期性的向所有跟随者发送心跳消息(即不包含日志项的日志复制RPC消息)，通知大家我是领导者，阻止跟随者发起新的选举。

• 2.如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，同时推荐自己为候选人，发起领导者选举。

• 3.在一次选举中，赢得大多数选票的候选人将晋升为领导者

• 4.在一个任期内，领导者一直都会是领导者，直到它自身出现问题(比如宕机)或者网络延迟，其他节点才会发起一轮新的选举。

• 5.在一次选举中，每一个服务器节点最多会对一个任期编号透出一张选票，并且按照"先来先服务"的原则进行投票。比如任期编号为3的节点C
  先收到了一个包含任期编号为4的投票请求(来自节点A),又收到了1个包含任期编号为4的投票请求(来自节点B),那么节点C将会把唯一一张选票
  投给节点A，在收到节点B的投票请求RPC消息时，它已没有选票可投了，如图所示
  

• 6.日志完整性高的跟随者(也就是最后一条日志对应的任期编号值更大，索引号更大)拒绝投票给日志完整性低的候选人。比如节点B的任期编号为3，节点C的任期编号是4，节点B的最后一条日志项对应的任期编号为3，而节点C的最后一条日志项对应的任期编号为2，那么当节点C请求节点B投票给自己时，节点B将拒绝投票，如图所示。
  

• 注意。
  选举时跟随者发起的，推荐自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标是保证在一个给定的任期内有且只有一个领导者。

其实在选举中，除了选举规则外，我们还需要避免一些导致选举失败的情况，比如同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。那么Raft算法是如何避免这个问题的呢?答案就是采用随机超时时间。

如何理解随机超时时间

议会选举中常出现未达到指定票数，选举无效，需要重新选举的情况。Raft算法的选举中也u才能在类似的问题，那它是如何处理选举无效的问题呢？其实,Raft算法巧妙地使用了随机选举超时时间的方法，即把超时时间都分散开来，在大多数情况下只有一个服务器节点发起选举，而不是同时发起选举，从而减少因选票瓜分导致选举失败的情况。在Raft算法中，随机超时时间有两种含义，这也是很多人容易理解错误的地方,需要注意一下:

• 1.跟随者等待领导者心跳信息超时的时间间隔是随机的。

• 2.如果候选人在一个随机时间间隔内没有赢得过半票数，那么选举无效，然后候选人会发起新一轮的选举，也就是说，等待选举超时的时间间隔是随机的。

• 注意
  Raft算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导者，也极大地减少了选举失败的情况

Raft是如何复制日志的

我们知道Raft除了能实现一系列值得共识之外，还能实现各节点日志的一致。但是，你也许会有这样的疑惑:“什么是日志?它和我的业务数据有什么关系呢?”
想象一下，一个木筏(Raft)是由多根整齐一致的原木(Log)组成的，原木又是由木质材料组成的，已知日志是由多条日志项(Log Entry)组成的，如果把日志比喻成原木，那么日志项就是木质材料。在Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端的写请求后，处理写请求的过程就是一个复制和应用(Apply)日志项到状态机的过程。那么Raft算法是如何复制日志，又是如何实现日志的一致的呢？这些内容是Raft算法中非常核心的内容

如何理解日志

副本数据是以日志的形式存在的，而日志由日志项组成，那么日志项究竟是什么呢？
其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令(Command)，以及一些附加信息，比如索引值(Log Index)、任期编号(Term),如图所示。

• 1.指令:一条由客户端请求指定的、状态机需要执行的命令。你可以将指令理解成客户端指定的数据
• 2.索引值:日志项对应的整数索引值，用于标识日志项，是一个连续的、单调递增的整数号码
• 3.任期编号:创建这条日志项的领导者的任期编号。

从图中可以看到，一届领导者任期往往有多条日志项，而且日志项的索引值是连续的，这一点需要特别注意。
现在你可能会问:不是说Raft算法实现了个节点间日志的一致吗？为什么上图中的4个跟随者的日志都不一样呢?日志是如何复制的呢？Raft又是如何实现日志的一致呢？