Raft算法简介
Raft算法是Paxos算法的工程实现，主要特点就是通过较为简单的算法实现分布式系统的数据一致性和高可用。
Raft 算法是解决分布式系统一致性问题的，与 Paxos 实现的功能相同，相对来说更容易实现和理解。
为什么需要Raft?
Raft 算法是解决分布式系统一致性问题的，比如：大家熟悉的很多中间件Etcd、Consul、Zookeeper、Tikv等，都会涉及到分布式场景的数据一致性问题。
共识算法是实现这类组件的关键算法，共识算法是协调多个节点达成共识的算法，这是构建高可用系统的基石。
共识算法有很多种，比如：paxos、raft、zab等，paxos以复杂和难以理解著称，通常来说raft是更容易理解的算法，也更容易在工程实践中采用。
Raft算法角色
在Raft算法中，一个集群里面的所有节点有以下三种状态：
1.跟随者(follower)
类似选民，完全被动的角色，这样的服务器等待被通知投票。
2.候选者(candidate)
候选者就是在选举过程中提名自己的实体，一旦选举成功，则成为领导者。
3.领导者(leader)
领导者的作用：处理客户端交互，日志复制等动作，Raft 要求系统在任何一个时刻最多只有一个 Leader，正常工作期间只有 Leader 和 Follower。
每一次开始一次新的选举时，称为一个“任期”，每个任期都有一个对应的整数与之关联，称为“任期号”，任期号用单词“Term”表示，这个值是一个严格递增的整数值。
Raft 算法角色状态转换，如下图所示：
Raft算法实现原理
实现 Raft 算法两个最重要的事是：一个是leader选举(选主)，一个是日志复制，下面我重点详解。
leader选举
Raft通过心跳机制来触发leader选举，当一个服务器启动时，默认位于followers状态，并且一直持续知道它一直接受到leader的RPC请求。
leader会周期性发送心跳给所有的followers，如果follower一段时间内没有接受到心跳，那么就认为当前没有leader应该开始leader selection。
一个最小的 Raft集群需要三个参与者，这样才可能投出多数票，如下图所示：
第一种：A节点要投自己一票，并把提议拉票请求发给B和C，如下图所示：
B和C接受了A的提议，也投票给A，最终A成为Leader。
第二种：A节点投了自己一票，B节点也投了自己一票，C节点支持A节点的提议，如下图所示：
第二种少数服从多数，最终A成为Leader。
第三种：A节点、B节点、C节点都各自投了自己一票，如下图所示：
这样就没有节点获得多数票，第三种情况本轮投票无效，出现了平票（Split Votes），因为没有任何一方获得多数票，所以要发起新的一轮投票。
Raft协议为了不让选举机制反复出现平票，定义了一个随机超时机制（randomized election timeouts），一旦发生平票，平票的节点会各自再来一次随机timeout倒数，然后重新拉票，先发起拉票的节点就可以优先获得了多数节点的投票。
日志复制
在 Raft 算法中需要实现分布式一致性的数据被称作日志， Raft 算法中的数据提交记录，会按照时间顺序进行追加，Raft 也是严格按照时间顺序并已一定的格式写入日志文件中。
下面这张图就描述了Raft集群中日志的组成结构：
每一个小方框就是entry，每个日志项包含一条命令、任期信息、日志项在日志中的位置信息(索引值 LogIndex)。
- 指令：由客户端请求发送的执行指令，有点绕口，我觉得理解成客户端需要存储的日志数据即可。
- 索引值：日志项在日志中的位置，需要注意索引值是一个连续并且单调递增的整数。
- 任期编号：创建这条日志项的领导者的任期编号。
Raft 的日志复制过程，大致如下图所示：
1.领导者接收到客户端发来的请求，创建一个新的日志项，并将其追加到本地日志中；
2.接着领导者通过追加条目 RPC 请求，将新的日志项复制到跟随者的本地日志中；
3.当领导者收到大多数跟随者的成功响应之后，则将这条日志项应用到状态机中，可以理解成该条日志写成功了；
4.最后领导者返回日志写成功的消息响应客户端。
陈睿mikechen
10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》