分布式一致性算法 Raft

一、Raft 算法背景

在学术理论界，分布式一致性算法的代表还是 Paxos，但是少数理解的人觉得很简单，尚未理解的觉得很难，大多数人还是一知半解。Paxos 的可理解性 & 工程落地性的门槛很高。斯坦福学者花了很多时间理解 Paxos，于是他们研究出来 Raft。本文主要是介绍 Raft 算法的基本原理。

二、Raft 算法基本原理

共识算法就是保证一个集群的多台机器协同工作，在遇到请求时，数据能够保持一致。即使遇到机器宕机，整个系统仍然能够对外保持服务的可用性。

Raft 将共识问题分解三个子问题：

1. Leader election 领导选举：有且仅有一个 leader 节点，如果 leader 宕机，通过选举机制选出新的 leader；
2. Log replication 日志复制：leader 从客户端接收数据更新/删除请求，然后日志复制到 follower 节点，从而保证集群数据的一致性；
3. Safety 安全性：通过安全性原则来处理一些特殊 case，保证 Raft 算法的完备性；

所以，Raft 算法核心流程可以归纳为：

• 首先选出 leader，leader 节点负责接收外部的数据更新/删除请求；
• 然后日志复制到其他 follower 节点，同时通过安全性的准则来保证整个日志复制的一致性；
• 如果遇到 leader 故障，followers 会重新发起选举出新的 leader；

这里先介绍一下日志同步的概念：服务器接收客户的数据更新/删除请求，这些请求会落地为命令日志。只要输入状态机的日志命令相同，状态机的执行结果就相同。所以 Raft 的核心就是 leader 发出日志同步请求，follower 接收并同步日志，最终保证整个集群的日志一致性。

2.1 Leader Election 领导选举

集群中每个节点只能处于 Leader、Follower 和 Candidate 三种状态的一种:

1. follower 从节点：

• 节点默认是 follower；
• 如果**刚刚开始 ** 或 和 leader 通信超时，follower 会发起选举，变成 candidate，然后去竞选 leader；
• 如果收到其他 candidate 的竞选投票请求，按照先来先得 & 每个任期只能投票一次 的投票原则投票;

1. candidate 候选者：

• follower 发起选举后就变为 candidate，会向其他节点拉选票。candidate 的票会投给自己，所以不会向其他节点投票
• 如果获得超过半数的投票，candidate 变成 leader，然后马上和其他节点通信，表明自己的 leader 的地位；
• 如果选举超时，重新发起选举；
• 如果遇到更高任期 Term 的 leader 的通信请求，转化为 follower；

1. leader 主节点：

• 成为 leader 节点后，此时可以接受客户端的数据请求，负责日志同步；
• 如果遇到更高任期 Term 的 candidate 的通信请求，这说明 candidate 正在竞选 leader，此时之前任期的 leader 转化为 follower，且完成投票；
• 如果遇到更高任期 Term 的 leader 的通信请求，这说明已经选举成功新的 leader，此时之前任期的 leader 转化为 follower；

具体的节点状态转换参考下图：

Raft 算法把时间轴划分为不同