Nacos微服务注册中心-Raft选举算法简析 _Raft算法

Raft，分布式共识算法，是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。如redis-sentinel，etcd等都使用Raft协议解决分布式一致性的问题。
Nacos注册中心是阿里巴巴贡献的开源项目，兼具服务注册发现、动态配置管理、动态DNS等功能。nacos集群使用了raft协议，来解决分布式一致性问题。

一、Raft算法概述Raft算法由leader节点来处理一致性问题。leader节点接收来自客户端的请求日志数据，然后同步到集群中其它节点进行复制，当日志已经同步到超过半数以上节点的时候，leader节点再通知集群中其它节点哪些日志已经被复制成功，可以提交到raft状态机中执行。

通过以上方式，Raft算法将要解决的一致性问题分为了以下几个子问题。

leader选举：集群中必须存在一个leader节点。
日志复制：leader节点接收来自客户端的请求，然后将这些请求序列化成日志数据再同步到集群中其它节点。
安全性：如果某个节点已经将一条提交过的数据输入raft状态机执行了，那么其它节点不可能再将相同索引的另一条日志数据输入到raft状态机中执行。

Raft节点有三种状态，follower、candidate、leader 。

Leader：领导者，一个集群里只能存在一个Leader 。
Follower：跟随者，Follower是被动的，一个客户端的修改数据请求如果发送到Follower上面时，会首先由Follower重定向到Leader上。
Candidate：参与者，一个节点切换到这个状态时，将开始进行一次新的选举。

各状态之间的转化如下图：

文章插图

上图中标记了状态切换的6种路径，下面做一个简单介绍。

start up：起始状态，节点刚启动的时候自动进入的是follower状态。
times out, starts election：follower在启动之后，将开启一个选举超时的定时器，当这个定时器到期时，将切换到candidate状态发起选举。
times out, new election：进入candidate 状态之后就开始进行选举，但是如果在下一次选举超时到来之前，都还没有选出一个新的leader，那么还会保持在candidate状态重新开始一次新的选举。
receives votes from majority of servers：当candidate状态的节点，收到了超过半数的节点选票，那么将切换状态成为新的leader 。
discovers current leader or new term：candidate状态的节点，如果收到了来自leader的消息，或者更高任期号的消息，都表示已经有leader了，将切换回到follower状态。
discovers server with higher term：leader状态下如果收到来自更高任期号的消息，将切换到follower状态。这种情况大多数发生在有网络分区的状态下。

关于Raft协议，首先，可以看一下动画，初步认识一下这个分布式公式算法的具体步骤。

http://thesecretlivesofdata.com/raft/

整个过程大致分为 Leader选举（Leader Election ）、日志复制（Log Replication）两步。

二、Leader选举（Leader Election）【Nacos微服务注册中心-Raft选举算法简析】Raft算法是使用心跳机制来触发leader选举的。
①所有节点一开始都是follower状态，一定时间未收到leader的心跳，则进入candidate状态，参与选举；
②选出leader后，leader通过向follower发送心跳来表明存活状态，若leader故障，则整体退回到 ①中的状态；
③每次选举完成后，会产生一个term，term本身是递增的，充当了逻辑时钟的作用；

具体的选举过程：
等待heartbeat，若超时未等到，准备选举---->新增当前任期号（term），转变为candidate状态---->给自己投票，然后给其他节点发送投票请求---->等待选举结果。
每一次开始一次新的选举时，称为一个“任期” 。每个任期都有一个对应的整数与之关联，称为“任期号”，任期号用单词“Term”表示，这个值是一个严格递增的整数值。
Raft节点之间通过RPC请求来互相通信，主要有以下两类RPC请求。RequestVote RPC用于candidate状态的节点进行选举之用，而AppendEntries RPC由leader节点向其他节点复制日志数据以及同步心跳数据的。

具体投票过程有三个约束：
（1）在同一任期内，单个节点最多只能投一票；
（2）候选人知道的信息不能比自己的少(Log与term)；
（3）first-come-first-served 先来先得。

选举的三种情况：