etcd raft源码导读

上个月写了一篇《etcd raft》，对etcd的设计思想以及一些概念做了一个概要的介绍。这篇文章则是从具体代码实现的角度来稍微深入介绍一下。代码是基于v3.4.15。

启动 & 初始化

etcd raft提供了两个函数StartNode和RestartNode用于初始化一个raft node。StartNode用于启动一个新节点，需要传入Peer信息。而RestartNode则是启动一个已经有数据的节点，签名分别如下：

func StartNode(c *Config, peers []Peer) Node 
func RestartNode(c *Config) Node

代码位置：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/node.go#L214-L242

对于一个全新的节点，需要传入Peer信息，用于构建cluster membership信息。关键是通过调用applyConfChange，

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/bootstrap.go#L77

对于已经存在数据的节点，启动的时候会加载snapshot，并且replay WAL文件。其实这也不属于etcd raft的范畴，不过为了完整的理解启动 & 初始化的过程，所以还是要讲一下。

snapshot保存在snap目录中，是后缀为".snap"的文件。在目录snap中，还有一个文件"db"，除此之外，etcd认为其它的文件都是无效的。具体是通过方法snapNames以及checkSuffix来实现的，

https://github.com/etcd-io/etcd/blob/v3.4.15/etcdserver/api/snap/snapshotter.go#L236-L277

在snap目录中可能会有很多snapshot文件，而etcd只会加载最新的一个snapshot文件。因为方法snapNames返回的snapshot文件名是按时间的倒序排列的，也就是从新到旧。在加载的时候，从第一个文件开始加载，如果加载失败，就会继续尝试加载下一个文件，至少成功为止。

加载snapshot主要就是读文件内容，然后反序列化的过程。而反序列化的代码是protocol buffer生成的。中间也会检查crc校验和。具体代码参考函数Read：

https://github.com/etcd-io/etcd/blob/v3.4.15/etcdserver/api/snap/snapshotter.go#L169-L232

反序列化出来的snapshot结构体定义为：

type Snapshot struct {
  Data             []byte           `protobuf:"bytes,1,opt,name=data" json:"data,omitempty"`
  Metadata         SnapshotMetadata `protobuf:"bytes,2,opt,name=metadata" json:"metadata"`
  XXX_unrecognized []byte           `json:"-"`
}

其中Data就是具体的数据，没什么好说的。Metadata则包含了比较重要的信息，比如Peer信息；这就是为什么启动一个已经存在数据的节点时不需要传入Peer信息，因为从snapshot中可以还原出peer信息。另外，Metadata中还包含了Term和Index信息(关于这两个概念，请参考前一篇文章)。这里的Index信息主要为了接下来的加载WAL用的。加载完snapshot之后，紧接着就是replay WAL文件(后缀是.wal)，这里注意，etcd只是读取WAL文件中该Index之后的记录。

加载snapshot以及replay WAL文件都是etcdserver的工作，raft并不关心这个过程。etcdserver加载完数据，并且创建一个Storage对象之后，传给RestartNode即可。参考：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L147

Heartbeat Interval & Election Timeout

这两个参数对于etcd的性能调优非常重要，分别控制心跳与选举的间隔/时机。对应的两个命令行参数如下，单位都是毫秒，

--heartbeat-interval
--election-timeout

代码位置：

https://github.com/etcd-io/etcd/blob/v3.4.15/etcdmain/config.go#L154-L155

默认值分别为100ms(heartbeat)和1000ms(election)，代码位置：

https://github.com/etcd-io/etcd/blob/v3.4.15/embed/config.go#L398-L399

关于如何tunning这两个参数，建议阅读：

https://etcd.io/docs/v3.4/tuning/#time-parameters

这里要注意一点，对于electionTimeout，每个raft节点实际使用的是一个在如下范围内的随机值，而且每次变换身份（例如从follower到candidate）的时候，都会重新计算出一个新的随机值。

[electiontimeout, 2 * electiontimeout - 1]

为什么要使用一个随机值？是为了防止很多follower同时变成candidate，大家会同时发起投票，那么投票结果可能会分裂，谁也无法获得超过半数的票数。从而导致不断的选举，长时间选不出leader。使用随机值就可以避免这种情况发生。关于使用随机值的详细解释，请参考下面论文的5.2节，

https://raft.github.io/raft.pdf

另外，raft节点并不依赖于具体的时钟，实际使用的是Tick。上面已经讲过，heartbeatInterval和electionTimeout的默认值分别是100ms和1000ms，那么一个tick默认就是100ms。raft节点使用的heartbeatInterval是1个tick，默认的electionTimeout是10个tick。具体可参考如下代码：

https://github.com/etcd-io/etcd/blob/v3.4.15/embed/config.go#L747
https://github.com/etcd-io/etcd/blob/v3.4.15/etcdserver/raft.go#L497-L498

状态机

etcd是强一致性的分布式K/V数据库，etcd cluster主要就是依赖于raft来维护一个分布式的状态机。所有的写请求都是由leader来处理，然后由leader再发送给所有的follower。每一条log entry都会经历三个阶段：

• unstable
  

• committed
  

• applied

对应的数据结构定义：

https://github.com/etcd-io/etcd/blob/main/raft/log.go#L30-L38

大致处理流程如下：

1. 首先leader将接收到的client的数据写入本地log；这些新加的log处于unstable状态；

2. 然后leader将log发送给其它节点，当超过半数的节点(包括leader自己)收到了log，那么这些log就被认为是committed；

3. 最后leader通知应用(也就是etcdserver)apply这些已经committed的log到自己的状态机。
   
   

第一个阶段之所以是unstable，是因为如果leader还没有来得及将log发送给超过半数的节点，自己就crash或者网络掉线了。当新的leader产生之后，就可能会覆盖掉这些还未committed的log。

leader向其它节点同步数据的逻辑参考：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L528-L535

如何处理前任leader的log entry?

leader在处理log 的过程中，可能会crash或者掉线，从而选举产生新的leader。这里就涉及一个问题，新的leader如何处理前任未处理完的log？如果log还没有发送到超过半数的节点上，那不用特殊处理，这种log要么被覆盖，要么被新leader发送到超过半数的节点上。

但是如果某个log entry在上一个term期间已经被发送到多数节点上，但还没有commit，leader就crash了。对于这种log，新leader该如何处理？这个问题稍微有点烧脑，就直接说结论：leader永远不能commit前一个任期的log entries，哪怕这些log已经被发送到了多数节点上了。只能通过commit当前任期内的log，来间接commit之前任期的log。

之所以这样，就是为了防止之前任期的log被commit之后，又被覆盖。而这显然违背了raft的"Leader Completeness"的设计原则：

If a log entry is committed in a given term, then that entry will be present in the logs of the leaders for all higher-numbered terms.

具体请参考Paper的Figure 3以及5.4.2节，

https://raft.github.io/raft.pdf

如果当前任期一直没有写请求，那么前任的遗留log可能一直得不到处理。所以etcd raft采取的做法是新leader当选后，会立马生成一个no-op entry，目的就是为了尽快地间接commit前一个任期内已经发送给多数节点但尚未commit的 log。参考代码：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L755-L756

阅读etcd raft代码的一个小技巧

etcd raft与etcdserver之间是通过channel异步交互，而且要借助于transport来传输log。所以在阅读源码的过程中，被这些和raft无关的细节缠绕。如果你只是想理解raft的实现原理，那么就可以有意识的跳过这些细节。

例如leader需要将log发送给其它节点，会调用send方法，代码如下：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L401-L431

上面代码的最后一行如下。这里你可以这样认为：只要将message添加到了r.msgs这个slice里面，这个消息就已经发送出去了。

r.msgs = append(r.msgs, m)

当然，实际发送的过程肯定比较复杂。首先会通过channel传递给应用层(etcdserver)，然后应用层再借助于transport package将消息发送出去。但是如果你的目的只是为了理解raft，就没必要操心这些细节。

Workflow

本来打算结合几个典型的workflow来梳理一下代码，但这篇文章已经写得过长了。这里就不展开写了。这里只是单独提一下，对于一个全新的etcd cluster，刚开始启动的时候，所有节点都没有任何数据，身份都是follower，开始大家都默默的等待election timeout。然后某个时刻，某个节点的election timeout到期了，就将自己变成candidate身份，触发了选举流程。顺利的话，获得超过半数的选票(包括自己)，就当选为leader。之后就是正常的heartbeat，以及正常处理client请求。具体请参考如下几处代码：

https://github.com/etcd-io/etcd/blob/v3.4.15/raft/node.go#L384
https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L659-L666
https://github.com/etcd-io/etcd/blob/v3.4.15/raft/raft.go#L1589-L1591

--END--