Raft分布式一致性算法

分布式一致性算法 Raft 笔记

Raft 是一个一致性协议，提供几个重要的功能：

Leader 选举
成员变更
日志复制

Raft分布式一致性算法

leader/follower/candidate

Raft将系统中的角色分为领导者（Leader）、跟从者（Follower）和候选人（Candidate）

系统中最多只有一个leader，如果在一段时间里发现没有leader，则大家通过选举-投票选出leader。
leader会不停的给follower发心跳消息，表明自己的存活状态。
如果leader故障，那么follower会转换成candidate，重新选出leader。

Raft要求系统在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

term任期

term：任期，比如新的选举任期，即整个集群初始化时，或者新的Leader选举就会开始一个新的选举任期。
term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。

raft角色状态转换图

所有节点启动时都是follower状态；
在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举；
如果收到majority的造成票（含自己的一票）则切换到leader状态；
如果发现其他节点比自己更新，则主动切换到follower。

RPC

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs）
基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起，然后 附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制。
为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试，并且他们能够并行的发起 RPCs 来获得最佳的性能。

RPC有三种：
RequestVote RPC：候选人在选举期间发起
AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成
InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。

超时

超时设置：
BroadcastTime : 领导者的心跳超时时间
Election Timeout: 追随者设置的候选超时时间

BroadcastTime应该比ElectionTimeout小一个数量级，为的是使领导人能够持续发送心跳信息（heartbeat）来阻止追随者们开始选举；

什么时候触发选举？

选举触发条件：
一般情况下，追随者接到领导者的心跳时，把ElectionTimeout清零，不会触发；
领导者故障，追随者的ElectionTimeout超时发生时，会变成候选者，触发领导人选取；

选举过程

如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。步骤如下：

追随者自增当前任期，转换为Candidate，对自己投票，并发起RequestVote RPC，等待下面三种情形发生；

获得超过半数服务器的投票，赢得选举，成为领导者；
另一台服务器赢得选举，并接收到对应的心跳，成为追随者；
选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举；

注意事项：

服务器在一个任期内，最多能给一个候选人投票，采用先到先服务原则；
候选者等待投票时，可能会接收到来自其它声明为领导人的的AppendEntries RPC。如果该领导人的任期（RPC中有）比当前候选人的当前任期要大，则候选人认为该领导人合法，并转换成追随者；如果RPC中的任期小于候选人的当前任期，则候选人拒绝此次RPC，继续保持候选人状态；
候选人既没有赢得选举也没有输掉选举：如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。所以Raft使用的随机的选举超时时间（150~300ms之间），来避免这种情况发生。

分布式理论(六) - 一致性协议Raft
https://juejin.im/post/5b2664e2f265da59584d8c90

Raft一致性算法笔记
https://www.jianshu.com/p/096ae57d1fe0

raft可以看看这个动画
RAFT 动画演示 The Secret Lives of Data
http://thesecretlivesofdata.com/raft/

Raft算法详解
https://zhuanlan.zhihu.com/p/32052223

很短 | 图解 Raft 算法
https://mp.weixin.qq.com/s/aQq02jLLwBzF8bJZNpqVxA

The Raft Consensus Algorithm
https://raft.github.io/