Raft角色

一个Raft集群蕴含若干节点，Raft将这些节点分为三种状态：Leader、Follower、Candidate，每种状态负责的工作也不一样。失常状况下，集群中的节点只存在Leader与follower两种状态。

  • Leader(领导者)：负责日志的同步治理，解决来自客户端的申请，与follower放弃心跳
  • Follower(追随者)：响应Leader的日志同步申请，响应Candidate的邀票申请，以及将客户端申请到Follower的事务转发给Leader
  • Candidate(侯选者)：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发动选举，选举胜出后，从Candidate转为Leader状态。
Raft三个子问题

Raft实现了和Paxos雷同的性能，它将一致性合成为多个子问题：Leader选举、日志同步、安全性、日志压缩、成员变更。
这里重点看下选举、日志同步与安全性：

  • 选举：当Leader宕机或集群启动时，一个新的Leader须要被选举进去
  • 日志同步：Leader接管来自客户端的申请并将其以日志条目标模式同步到集群中的其它节点，并且强制要求其它节点的日志和本人保持一致
  • 安全性：如果有任何的服务器节点曾经利用了一个确定的日志条目到它的状态机中，那么其它节点不能在同一个日志索引地位利用一个不同的指令。

1. 选举原理

依据Raft协定，一个利用Raft协定的集群在刚启动时，所有节点的状态都是Follower。因为没有Leader，Follower无奈与Leader放弃心跳，因而，Follower会认为Leader曾经下线，进而转为Candidate状态。而后，Candidate将向集群中其它节点申请投票，批准本人降级为Leader。如果Candidate收到超过半数节点的投票(N/2+1)，它将成为Leader。

第一阶段：所有节点都是Follower
在筹备选举时，所有节点状态都是Follower，并且初始任期为0，同时启动选举定时器，每个节点的选举定时器超时工夫都在100-500毫秒之间且不统一，防止同时发动选举。

第二阶段：Follower转为Candidate并发动投票
节点启动后在一个选举定时器周期内未收到心跳和投票申请，则状态转为候选者Candidate状态，且Term自增，并向集群中所有节点发送投票申请并且重置选举定时器。每个节点的选举定时器超时工夫都不统一，所以最先转为Candidate的节点最有可能成为Leader。

第三阶段：投票阶段
节点收到投票申请后会依据以下状况决定是否承受投票申请：

  1. 申请节点的Term大于本人的Term，且本人还未投票给其它节点，则承受申请，将票投给它
  2. 申请节点的Term小于本人的Term，且本人琮未投票，则拒绝请求，将票投给本人

第四阶段：Candidate转为Leader
一轮选举过后，失常状况下会有一个Candidate收到超过半数节点（N/2+1）的投票，它将胜出并降级为Leader。而后定时发送心跳给其它节点，其它节点会转为Follower并与Leader放弃同步，至此，选举完结；如果未过半数会进行下一轮选举。

2. Raft日志同步

在一个Raft集群中，只有Leader节点可能解决客户端申请（如果申请到了Follower，它会将申请转发到Leader），客户端的每个申请都蕴含一条被复制状态机执行的指令。Leader将这条指令作为一条新的日志条目（Entry）附加到日志中去，而后并行地将附加条目发送给各个Followers，让它们复制这条上场条目。
当这条日志条目被各个Followers平安复制，Leader会将这条上场条目利用到它的状态机中，而后将执行后果返回给客户端。如果Follower解体或者运行迟缓，或者网络丢包，Leader会一直尝试附加日志条目直到所有的Follower都最终存储所有的日志条目，确保强一致性。

第一阶段：客户端申请提交到Leader
Leader在收到客户端申请后会将其作为日志条目（Entry）写入本地日志中，须要留神的是该Entry的状态是未提交（uncommitted），Leader并不会更新本地数据，因而它是不可读的。

第二阶段：Leader将Entry发送到其它Follower
Leader与Follower之间放弃着心跳分割，随心跳Leader将追加的Entry(AppendEntries)并行地发送给其它的Follower，并让它们复制这条上场条目，这一过程称为复制（Replicate）。

  1. Leader向Follower发送的Entry是AppendEntries. 在一个心跳周期内，Leader可能会接管到多条客户端的申请，因而，Leader发送给Follower也会是多个Entry也就是AppendEntries
  2. Leader在向Follower发送追加的Entry外，还会将上一条日志条目标索引地位(prevLogIndex)，Leader的任期号（Term）也一并发送。如果Follower在它的日志中找不到蕴含雷同索引地位和任期号的条目，那么它就会回绝接管新的日志条目，呈现这样的状况阐明Follower与Leader数据不统一了。
  3. 解决Leader与Follower数据不统一的问题。因为某些起因Leader上数据可能比Follower上的数据多也可能少。要使二者数据放弃雷同，Leader会找到最初两者达成统一的中央，而后将那个点之后的日志条目删除并发送本人的日志给Follower，所有这些操作都在进行附加日志的一致性查看时实现。
    Leader还会为每个Follower保护一个nextIndex，它示意下一个须要发送给Follower日志条目标索引地址。当一个Leader刚被选举进去的时候，它会初始化所有的nextIndex值，并给本人最初一条日志的index加1。如果一个Follower的日志和Leader不统一，那么在下一次附加日志一致性查看会失败。在被Follower回绝之后，Leader会减小该Follower对应的nextIndex值并进行重试。最终nextIndex会在某个地位使得Leader和Follower的日志达成统一，这时会将Follower抵触的日志条目全副删除并再加上Leader的日志，这样Follower的日志就会和Leader保持一致。

第三阶段：Leader期待Follower回应
Follower接管到Leader发来的复制申请后，可能会有两种回应：

  1. 写入本地日志中，返回Success;
  2. 一致性查看失败，回绝写入，返回False（解决形式见第二阶段）

须要留神的是，此时该Entry的状态在Leader中仍是未提交状态，当Leader收到大多数Follower Success回应后，会将第一阶段写入的Entry标记为提交状态，并此日志条目利用到它的状态机中。

第四阶段：Leader回应客户端
实现前三个阶段后，Leader会向客户端回应OK，示意写操作胜利。

第五阶段：Leader告诉Followers Entry已提交
Leader回应客户端后，将随着下一个心跳告诉各Follower， 各Folloer收到告诉后会将Entry标记为提交状态，至此，Raft集群超过半数节点曾经达到统一状态，能够确保强一致性。因为网络等起因可能会有局部Follower在某个工夫点内与Leader不统一，但最终还是会统一。

3. Raft算法之安全性
Raft如何保障对于给定的任期号（Term），Leader都领有之前任期的所有被提交的日志条目（也就是Leader的完整性）呢？
1) 为了保障所有之前的任期号中曾经提交的日志条目在选举的时候都会呈现在新的Leader中，Raft采纳的是日志条目单向传递，只从Leader传给Follower，并且Leader从不会笼罩本身本地日志中曾经存在的条目。
2) 一个Candidate只有蕴含了最新的已提交的log entry，并且取得了集群中大部分节点的认可才有可能博得选举，这也意味着每一个曾经提交的日志条目必定存在于至多一个服务器节点上。
Candidate在发送RequestVote RPC时，要带上本人的最初一条日志的term和log index，其余节点收到音讯时，如果发现自己的日志比申请中携带的更新，则回绝投票。日志比拟的准则是，如果本地的最初一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。
3) Leader能够复制后面任期的日志，然而不会被动提交后面任期的日志，而是通过提交以后任期的日志来间接地提交后面任期内的日志(这一点有些不太了解)

参考的文章：
分布式算法 - Raft算法
Raft协定安全性保障