Raft协议实现

ETCD中每个节点都是一个有限状态机，本节从节点启动时的入口函数开始，逐步梳理了整个Raft协议层的框架和数据流（基于V3.1.8源码）。

首先，在没有任何初始化数据文件时，节点启动时需要创建数据文件目录并与集群中其他的节点建立连接。此处不考虑通过服务发现来注册和配置集群节点，只考察用“--initial-cluster”静态配置节点列表的方式，本质上没有区别。

Raft协议的基础是消息和日志的管理，每条日志都对应至少四个状态：

· Unstable: 消息已经成功收到，但还没有持久化到WAL

· Stable: 这是一个隐含的状态，即日志已经持久化到当前节点的WAL中，但还没有和集群达成一致

· Committed：消息已经跟整个集群协商完毕，达成一致

· Applied：整个集群已经协商并达成一致的指令在当前节点执行完毕

简而言之，每个进入Raft状态机的消息首先会被缓存在Unstable Storage，这是一个内存中的数组，然后异步收集并持久化到WAL日志文件，日志提交后更新WAL文件的Metadata，最后提交完毕的消息会被批量在当前节点执行。Fig 2.1为ETCD节点初始化的总入口。

函数一开始会初始化数据目录和文件，Fig 2.2中重点关注最简单的逻辑，即节点参与组建一个新集群，即命令行初始化时指定参数：`--initial-cluster-state new`.

节点启动时会校验参数的合法性，比如—initial-cluster的格式以及是否有重复记录等等，当参数校验成功后，就开始正式启动一个Raft模块。Fig 2.3为初始化Raft节点。

启动节点时，伴随着启动Raft状态机（如Fig 2.4）。

启动Raft状态机时，将集群节点信息写入WAL并强行提交，这个逻辑有可能是为了让集群中节点快速找到彼此，快速收敛。Raft状态机初始化完毕后，Fig 2.5启动这个状态机，接收和响应Raft消息。

这个函数在这个Raft模块的逻辑中，算是相当晦涩难懂的了，其中使用了很多私有的Channel，没有文档介绍，也没有注释。Table 1大致列出关键的私有Channel变量的主要用途。

整个状态机的数据流非常复杂，这里主要关注非配置数据的写操作与Raft状态机的数据流。

Fig 2.6 中消息进入Unstable Storage之后，需要等待上一次Apply执行完毕，然后状态机会发起一个Ready消息，封装了还未持久化的消息和已经Commit的消息。

在Fig 2.7中，readyc的接收者收到一个Ready消息之后，对其中的两种数据分别做了处理，没有持久化WAL的消息做持久化，而已经提交的消息就在状态机中执行。

Fig 2.6与Fig 2.7分别显示了消息或日志的两种状态，即Unstable和Committed，在Fig 2.8中，ETCD节点将消息传入Raft状态机，和整个集群一起来协商、决策，其实就是让Stable状态的WAL日志转变为已经提交（Committed）的日志。

消息进入状态机之后，过程就变得简单多了。先来看一下整个状态机的入口，即Fig 2.9中的Raft.Step函数。

值得一提的是，分布式系统中，通常都需要对收到的消息做一些基本的校验，数据修改相关的消息必须保持和节点在同一个Lead Election的上下文之内（Term相同）。不符合要求的消息会被过滤，如Fig 2.9中提到的逻辑中，检查并对消息的Term和当前节点状态机的Term不一致的情况做了预处理：

· m.Term > r.Term：说明当前节点已经相对落后集群状态了，由于集群状态比当前节点新，以集群最新状态为准，当前节点会变为Follower。

· m.Term < r.Term：说明收到的消息落后于当前节点，除了Heartbeat消息以外的消息都会被直接丢弃。

只有消息的Term与当前节点一致时，消息才会正式进入状态机进行决策。Fig 2.10中的STEP实际上是一个函数变量，在状态机变化时可以修改这个变量的赋值，初始状态始终是Follower。从这个角度看Raft的实现，其实就是看STEP函数对不同消息的处理逻辑。

一共有三个STEP函数的实现，分别对应了Raft状态机中节点的三种状态：Follower、Candidate和Leader。

在正式介绍逻辑之前，先看一下常见消息类型：

· MsgHup: 本地节点中触发一次Lead Election

· MsgBeat：触发Leader向Follower发送一个MsgHearbeat消息

· MsgProp：尝试向本地日志中Append一条记录，在非Leader节点收到写请求的时候，会通过MsgProp类型将该请求转发给当前Leader节点

· MsgApp/MsgAppResp:Leader通知其他节点来同步日志的消息和响应

· MsgVote/MsgVoteResp: 要求其他节点给自己投票的消息和结果

· MsgPreVote/MsgPreVote：模拟一次Lead Election，但不修改集群的状态，用来恢复脑裂状态下的集群

· MsgSnap/MsgSnapStatus:Leader发起让其他节点同步一个Snapshot的请求和响应

· MsgHeartbeat/MsgHeartbeatResp：集群中的心跳和响应

· MsgUnreachable：这是节点内部用以暂时停止向节点发消息的优化机制，比如Follower节点正在生成快照，Leader节点就会暂时关闭向Follower发送MsgApp消息。

状态机逻辑也很复杂，本文只梳理Leader/Follower状态的主要处理逻辑，即stepLeader和stepFollower两个函数，分别处理了对应状态。

先看Leader节点对MsgProp（如写数据的请求）的处理逻辑。

再来看看Follower节点中的消息处理，Fig 2.13主要关注MsgProp、MsgApp和MsgHeartbeat。

Follower会把MsgProp转发给Leader节点，这就是为什么在一个集群中可以在任意节点发起读写请求，这样外部模块做负载均衡的逻辑也可以大大简化。

收到App消息时，Follower首先会“毫不犹豫地”将Lead Election计时器清零；紧接着当前节点的Leader会直接切换成消息的来源节点；最后进入消息处理逻辑，需要关注两个小细节：

· 如果消息晚于当前节点状态，会给对应的Leader返回响应来告知自己当前的状态

· 如果消息出现冲突（Term/Index和当前节点不一致），就会直接拒绝MsgApp消息