Raft算法 - ihsiao-软件开发技术分享

节点状态#

节点状态: 领导者(Leader), 跟随者(Follower), 候选人(Candidate)

任何时候节点都处于其中一种状态.

跟随者(Follower)

只能接收和处理来自领导者(Leader)的消息

当等待领导者心跳信息超时的时候, 就主动站出来, 推荐自己当候选人(Candidate)

候选人(Candidate)

候选人向其他节点发送请求投票(RequestVote)RPC消息, 通知其他节点来投票, 如果赢得大多数选票, 就晋升成为领导者(Leader)

领导者(Leader)

处理写请求, 管理日志复制和不断地发送领导者的心跳信息.

注意: 任意时间, 节点内有且只有一个领导者(Leader)节点

随机超时特性#

在Raft中, 随机超时有两种含义

跟随者等待领导者心跳的超时时间间隔是随机的
候选人在发起选票后, 如果选票没有超过一半, 那么本次发起请求投票选举失败. 那么再一次发起投票的时间是随机的.

选举过程#

假设有三个节点: A, B, C

初始状态, 所有节点为跟随者(Follower)状态.
节点等待领导者心跳信息超时, 随机超时时间最短的节点最先发起选举.

假设节点A等待超时时间最短, 则A最先发起选举: 增加自己任期编号, 给自己投一张选票, 并推举自己为候选人. 向其他节点发送请求投票RPC消息, 请它们选自己为领导者.

如果候选人在选举时间内赢得大多数选票, 那么它就会成为本届内新的领导者.

节点A当选领导者后, 它将周期性发送心跳消息: 通知其他服务器我是领导者, 阻止其他节点发起新的选举.

选举过程中的问题#

节点间如何通讯?

节点间沟通采用远程过程调用(RPC). 两类RPC:

1. 请求投票(RequestVote)RPC: 由候选人在选举期间发起, 通知各节点进行投票;
2. 日志复制(AppendEntries)RPC: 由领导者发起, 用来复制日志和发送心跳消息.

什么是任期?

节点状态是不稳定的, 所以领导者状态不会时永久的.

任期就是一个带有任期编号的时间段, 时间段从节点状态变为领导者开始, 到领导者状态结束.

任期有以下特点:

1. 每个任期都是有编号的, 新的任期编号由旧的任期编号加一得出;
2. 当一个节点收到消息中的任期编号比自己的任期编号大, 则更新自己的任期编号.

Raft处理:

1. 当一个候选人或领导者, 发现自己的任期编号比其他节点小, 则状态立刻变为跟随着;
2. 如果收到的消息中任期编号比自己小, 则节点会直接拒接这个请求.

选举有那些规则?
- 领导者(Leader)必须周期性地向所有节点发送心跳消息.
- 在随机超时时间内, 跟随者(Follower)状态的节点没有收到心跳消息, 则会变为候选人(Candidate)状态, 并推举自己为Leader, 发起请求投票消息.
- 在一次选举中, 获得的票数大于一半(集群半数以上的选票)时, 候选人(Candidate)变为领导者(Leader).
- 一次任期内, 领导者一直是领导者, 除非自己出现问题, 或者网络原因, 其他节点发起了新一轮选举.
- 一次任期选举(带有相同任期编号投票请求)中, 一个节点只有一张选票. 按照先到先得原则.
- 日志完整性高的跟随着(最后一条日志项对应的任期编号大, 索引号更大), 拒绝投标给日志完整性低的候选人.

Raft协议的限制与局限#

Raft的强领导模型是”一切以领导者为主”，也相当于单机了。性能和吞吐量也会受到限制.

什么是日志#

日志由日志项组成. 而日志项是一种数据格式, 包含用户指定的数据(即: 指令 command), 还包含一些附加信息, 比如: 索引(Log Index), 任期编号(Term).

类似:

type LogItem struct {
	Data	interface{}	// 用户指定数据
	Index	int				// 日志索引
	Term	int				// 任期编号
}

注意: 节点的日志项的索引值是连续的.

如何复制日志#

日志复制可以理解为优化后的二阶段提交(将二阶段优化成一阶段), 减少一半的往返消息, 减少一半的消息延迟.

日志复制过程#

领导者发送日志复制(AppendEntries)RPC消息, 将日志项复制到集群其他节点;
当领导者收到大多数”复制成功”响应后, 它将日志项应用到它的状态机, 并返回成功给客户端; 如果领导者没有收到大多数成功的消息, 则返回错误给客户端.

实现日志的一致#

在Raft算法中, 领导者通过强制跟随者直接复制自己的日志项, 处理不一致日志. 即: Raft是通过以领导者的日志为准, 来实现各节点的一致的.

两个变量:

PrevLogEntry: 表示前一条日志项的索引值. 前一条是相对于领导者想要复制的日志项的前一条.
PrevLogTerm: 表示前一条日志项的任期值.

假设领导者发送的消息如下:

type SyncMessage struct {
	item			*LogItem	// 需要同步的日志项
	PreLogEntry	int			// item项前一项的日志索引值
	PreLogTerm	int			// item项前一项的日志任期值
}

日志的一致的复制过程如下:

领导者发送日志复制RPC消息. 消息内容如上
跟随着接收消息后, 查找本地日志中索引值 =PrevLogEntry, 任期值 = PreLogTerm的日志项, 如果没有找到, 那么说明日志与领导者不一致. 则跟随者会拒绝接收新的日志项, 并返回失败消息给领导者.
这时, 领导者会递减要复制的日志项: PreLogEntry - 1, PreLogTerm - 1, item - 1, 即: 整体往后移. 同时再次发送RPC消息给跟随者
当跟随者收到消息并在本地日志中找到相同索引值和任期值的日志项, 则消息并将新的item写入本地日志.

成员变更#

什么是配置(Configuration)#

配置是指: 集群有那些节点组成的, 是集群各节点地址信息的集合. 比如节点A, B, C组成一个集群, 那么集群的配置就是[A, B, C]集合.

单节点变更#

单节点变更, 就是通过一次变更一个节点实现成员变更.

如果需要变更多个节点, 那么就执行多次单节点变更.

单节点变更的实现#

领导者向新加入的节点同步数据;
领导者将新集群配置[…, 新节点]作为一个日志项, 发起日志复制RPC请求, 集群其他节点收到请求后, 将新的配置日志项应用(Apply)到本地状态机, 完成单节点变更.

单节点变更的问题#

在分区错误, 节点故障等情况下, 如果发起单节点变更请求, 那么就可能出现问题: 单节点变更尚未完成, 新的单节点变更又在执行, 那么集群就有可能出现两个领导者的情况.

如何处理: 在领导者启动的时候, 创建一个NO_OP日志项(空日志项), 只有当领导者将NO_OP日志项应用后, 在执行成员变更请求.

引用#

分布式协议与算法实战_分布式_分布式算法-极客时间

#01 Blogs/blog#