当前位置 : 首页 » 文章分类 :  开发  »  Raft分布式一致性算法

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,等待下面三种情形发生;

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

注意事项:

  • 服务器在一个任期内,最多能给一个候选人投票,采用先到先服务原则;
  • 候选者等待投票时,可能会接收到来自其它声明为领导人的的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/


上一篇 HikariCP

下一篇 Spring-Cloud-Netflix-Zuul

阅读
评论
1,238
阅读预计5分钟
创建日期 2019-05-21
修改日期 2020-03-11
类别
标签

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论