参考资料: http://thesecretlivesofdata.com/raft/

RAFT算法

1. 选举算法:1.1. 粗糙的选举过程描述1.2. 处理冲突2. 日志同步3. 成员变更

1. 选举算法:

我们来模拟一下 RAFT算法的 选举过程

1.1. 粗糙的选举过程描述

角色:

领导者 leader候选人 candidate跟随者 follower

背景:

假设: 此时每个节点记录的任期编号为1, 节点A是leader领导者节点

开始选举:

集群中, A节点leader下线, A节点不再向各个节点发送心跳包每个节点开始计算leader的心跳包超时时间(每个节点是随机的)B节点第一个到超时时间B节点设置自己的任期编号为2, 发送投票请求给其他所有节点其他节点如果是发现自己的任期编号小于2, 则将投票给B节点当B节点接收到的赞同票超过半数, 则选举结束节点B加冕为王, 开始向其他所有节点发送心跳包, 宣示主权

1.2. 处理冲突

以上的描述过于粗糙, 还有许多细节问题我们需要一一处理

问题1: 如果有多个节点一起发出投票请求, 接受者怎么处理?

同一个任期, 我只能投一次票, 谁的请求先发给我我就先给谁投票无论我是什么角色, 如果收到一个投票请求, 比我的任期编号高, 我立刻转换身份变成跟随者, 并给它投票

问题2: 如果没有一个候选者获得半数以上的投票怎么办?

如果候选者没有获得半数以上投票, 那么候选者开始计算超时时间(随机时间), 等待下一次发起投票, 候选者超时时间较短, 跟随者超时时间较长

2. 日志同步

日志同步的算法就要简单得多

步骤:

客户端向领导者发起请求,设置a=1领导者接收请求,修改数据,暂时hold住请求领导者将修改同步给其他所有节点跟随者接收到请求之后修改自己节点上的值 a=1, 这只是半提交跟随者发送修改成功的消息通知领导者当领导者收到半数以上跟随者修改成功的消息之后, 通知客户端修改成功同时领导者通知跟随者确认刚才修改的值 a=1 修改成功 这里使用了二阶段提交的算法, 3, 7, 两步就是两次提交的步骤

3. 成员变更

成员变更的算法也很简单 为了防止出现脑裂的情况发生, 成员变更, 尤其是增加成员, 我们一般采取单节点变更的方式

单节点变更, 就是通过一次变更一个节点实现成员变更如果有多个节点需要变更, 则需要执行多次单成员变更, 多次变更是串行的

步骤:

新节点向集群注册自己leader节点向新节点同步数据领导者将新节点的配置同步到其他跟随者节点上完成