前言

之前解析过Raft协议基本原理（传送门），一直想找个具体实现来看一下。Etcd是一款开源的分布式KV数据库，由于K8S中使用它作为注册和配置中心而被广泛认知。跟它最类似的产品还有相同应用场景Zookeeper，经常被用作注册中心和分布式锁。Etcd也是比较早的使用Raft协议来实现分布式存储的产品，而且它的架构设计中将raft协议部分单独剥离出来，这样其它的程序如果想用raft协议，可以直接依赖它的raft模块。后续几篇文章将通过etcd源码来查看如何完整实现一个Raft协议。

知识准备

Etcd是使用Go语言实现的，如果之前没了解过Go但是用过其它面向对象的语言（如Java），相信对文章中90%以上内容的理解都不会有问题。如果想要自己对照着源码一起看文章，了解下Go的基本概念还是必要的。可以着重了解下Go的如下特性：

• interface和struct
• 方法和函数的区别
• channel 通道，Go语言设计思想的核心，etcd设计中大量用到

etcd架构

Etcd本质上是一个分布式KV数据库，Raft只是它为了实现分布式数据一致性所采用的协议。在整个架构上，我们只需要关心围绕着Raft部分模块的设计。相关模块的架构如下：

EtcdServer

模块分解

EtcdServer

EtcdServer可以看作是etcd节点的核心控制器，它即实现了etcd的一个服务节点，每个EtcdServer都包含了一个Raft的节点实现。它主要包含如下的功能：
节点初始化
etcd节点启动时会初始化并启动一个EtcdServer，启动的过程主要包含如下的部分：

• 重启时会加载之前已经持久化到磁盘的数据，恢复整个Server。数据包括WAL中的日志数据和KV的snapshot数据。etcd节点在运行过程中，如果数据已经写到boltDB中，则会永久存储。但是日志数据有可能还没有commit或者apply，这部分数据会在WAL文件中，etcd启动时会重新将这部分数据重新加载到raft内存中。
• 启动Raft状态机，启动后将通过raftNode和raft状态机进行交互
• 初始化和集群中其它节点的通信

请求通信
EtcdServer会发送/接收两种来源的请求，客户端和集群其它节点

• 客户端请求，EtcdServer收到客户端的写请求和线性读请求后，会交给Raft来处理，然后等待处理完成后回复客户端。
• 集群节点间的请求，包括心跳、投票、日志复制，当raft模块发现需要有请求发送给其它节点时就会通过EtcdServer来转发，这样就降低了Raft模块的复杂性。

发起心跳
EtcdServer通过内置一个定时器来定时触发Raft的心跳接口。如果是Leader，则发送心跳给集群中其他节点；如果是Follower则检查Leader的心跳是否超时，以决定是否发起一次新的选举 。

日志持久化
上面的架构图中，Raft模块也保存有日志条目，但是这个日志条目其实只是在内存中，真正的数据持久化是由EtcdServer完成的。回忆下Raft协议中，只规定了哪些数据和属性应该持久化，而并没有规定怎么存，存在什么地方。所以etcd将持久化部分和Raft协议部分分开实现是合理的。

KV数据操作
Raft协议只保证日志复制的一致性，对于最终日志应用不关心。etcd是KV数据库，所以收到raft可以将日志应用的时候，就会将日志中包含的操作应用到后端的KV存储中。KV存储部分的逻辑不属于Raft的范围，所以后续不会关注这一块的实现。

Raft

Raft模块是协议算法的实现，后续的源码解读也会集中在这一模块上。
Node
Node接口代表raft集群中的一个节点，对外提供操作raft协议节点的方法。如果有别的程序想只使用etcd的raft实现的话，可以启动一个Node，然后直接调用这个接口来和raft状态机交互就可以了。

type Node interface {
    // 触发一次心跳，raft会在触发后检查leader选举超时或发送心跳
    Tick()
    // 触发节点将自己变成候选人，开始选举
    Campaign(ctx context.Context) error
    // 提交日志条目
    Propose(ctx context.Context, data []byte) error
    // 集群配置变更
    ProposeConfChange(ctx context.Context, cc pb.ConfChangeI) error
    // 发送一条消息给状态机，触发状态变化
    Step(ctx context.Context, msg pb.Message) error
    // 如果raft状态机有变化，会通过channel返回一个Ready的数据结构，里面包含变化信息，比如日志变化、心跳发送等。调用方在处理完后需要调用Advance()方法告诉状态机上一个Ready处理完了
    Ready() <-chan Ready
    Advance()
    // 应用集群变化到状态机
    ApplyConfChange(cc pb.ConfChangeI) *pb.ConfState
    // 将Leader转给transferee.
    TransferLeadership(ctx context.Context, lead, transferee uint64)
    // 请求一次线性读
    ReadIndex(ctx context.Context, rctx []byte) error
    // raft state machine当前状态.
    Status() Status
    // 告诉状态机指定id节点不可达.
    ReportUnreachable(id uint64)
    // 告诉状态机给id节点发送snapshot的最终处理状态.
    ReportSnapshot(id uint64, status SnapshotStatus)
    // 关闭节点.
    Stop()
}

struct node 是Node接口的默认实现，它包含了多了go channel来接收请求，也就是说对它的调用大部分都是异步处理的。在启动的时候会读取channel中的消息，然后调用RawNode相应的方法来处理请求。

type node struct {
    propc      chan msgWithResult
    recvc      chan pb.Message
    confc      chan pb.ConfChangeV2
    confstatec chan pb.ConfState
    readyc     chan Ready
    advancec   chan struct{}
    tickc      chan struct{}
    done       chan struct{}
    stop       chan struct{}
    status     chan chan Status

    rn *RawNode
}

node中定义的channel基本可以和接口中的方法对应上，propc用来接收日志，recvc用来接收除日志之外的消息。
RawNode
RawNode只是对raft做了一层封装，可以看成是raft的Facade接口。Node通过调用RawNode的接口来操作raft，而RawNode的大部分操作只是对raft的Step()方法做了一个封装。RawNode同时缓存了两个State属性，是为了在获取raft状态机数据时比对状态是否有变化。

type RawNode struct {
    raft       *raft
    prevSoftSt *SoftState
    prevHardSt pb.HardState
}

RawNode对于状态机操作的方法都直接发给raft，比如接收新日志的方法实现如下：

func (rn *RawNode) Propose(data []byte) error {
    return rn.raft.Step(pb.Message{
        Type: pb.MsgProp,
        From: rn.raft.id,
        Entries: []pb.Entry{
            {Data: data},
        }})
}

还有一对重要的方法是Ready()和Advance()，当raft状态机有变化时，包括状态和数据变化，通过Ready()方法就可以取到变化的数据，调用方拿到数据后该持久化的持久化，该发送的发送。在调用方处理完后调用Advance()方法通知raft状态机已处理完成。
raft
协议算法的核心实现，实际上就是一个状态机的实现，当有外部请求来的时候，比如新的日志，发送心跳等，就调用它的Step()方法来触发状态机。它维护了Raft协议中规定的所有属性，如Term、CommitIndex、Vote等。同时通过RaftLog来持有日志。

type raft struct {
    //在raft集群中的唯一id
    id uint64
    //选举周期
    Term uint64
    //上一次投票的节点，Leader等于自己的id
    Vote uint64
    //线性读状态
    readStates []ReadState
    // 日志
    raftLog *raftLog
    ....
    // 跟踪Follower节点的状态，比如日志复制的matchIndex
    prs tracker.ProgressTracker
    // 当前节点的类型
    state StateType
    // 节点是不是 learner.
    isLearner bool
     // 待发送给其它节点的消息
    msgs []pb.Message
    // leader id，leader人工转移时的目标节点
    leadTransferee uint64
    ...
    // 还未提交的日志条数，非准确值
    uncommittedSize uint64
    readOnly *readOnly
    // 选举时记录ticks
    electionElapsed int
    // 记录心跳的ticks
    heartbeatElapsed int
    ...
    //心跳超时
    heartbeatTimeout int
    // 选举超时
    electionTimeout  int
    //随机选举超时
    randomizedElectionTimeout int
    disableProposalForwarding bool

    tick func()
    step stepFunc
    ...
}

raft的属性基本跟raft协议中规定的节点的属性对应，其中raftLog在内存中存储了日志条目，prs跟踪节点日志复制的进度。
关于心跳和选举超时的计时，etcd是用tick的方式来计算的，每两次tick之间的耗时其实就是心跳时间。所有的超时都是以tick的倍数来计算的，比如electionTimeout等于2，就是选举超时是两倍的心跳时间间隔。randomizedElectionTimeout就是raft协议中建议的，选举超时应该是在一个范围内的随机值，防止所有Follower在Leader超时后同时发起选举。
msg属性用来存储需要处理的消息，比如心跳。前面讲过raft模块只负责状态机的算法处理，而持久化及通信部分则交给调用方处理，这个msg就是存放需要处理的消息。
raft中最后两个属性tick和step是函数类型，在节点处于不同角色时，这个属性对应的方法实现是不一样的。比如tick()方法，在Follower中被调用时是检查距离上次收到Leader心跳是否超时，而在Leader中是向Follower发送心跳。step()方法也一样，不同的节点类型收到同一种消息时的处理逻辑是不一样的。

函数类型对Java程序员可能比较陌生，在有的语言中也叫方法指针。是指一个成员变量指向的是一个方法，在赋值的时候是将一个方法实现赋给这个变量

其它概念

• HardState, 封装了raft协议中规定的需要实时持久化的状态属性：当前选举周期、投票和已提交的Index

type HardState struct {
    Term             uint64 `protobuf:"varint,1,opt,name=term" json:"term"`
    Vote             uint64 `protobuf:"varint,2,opt,name=vote" json:"vote"`
    Commit           uint64 `protobuf:"varint,3,opt,name=commit" json:"commit"`
    XXX_unrecognized []byte `json:"-"`
}

• SoftState, 封装了raft协议中规定的无需持久化的状态信息：当前的Leader，节点角色

type SoftState struct {
    Lead      uint64 // must use atomic operations to access; keep 64-bit aligned.
    RaftState StateType
}

• state，一个raft节点只可能是4中角色中的一种：
  Follower：接收Leader的日志
  Candidate： 发起投票的候选人
  Leader：发送心跳和日志给Follower
  PreCandidate：如果PreVote打开的话，在正式变成候选人之前需要获得超半数节点的同意，在征询意见时节点处于的角色
• step，所有发给对状态机的请求，其实都是调用的它的step方法，对于不同的角色，处理Step方法的参数逻辑也是不一样的

RaftLog

从名字可以看出，RaftLog用于存储日志条目，它的所有数据都是在内存中。

type raftLog struct {
    // 上一次snapshot之后，已经被持久化的日志条目
    storage Storage
    // 所有还没有被持久化的日志条目
    unstable unstable
    // 已经commit的日志index
    committed uint64
    // 已经应用到状态机的日志的index
    applied uint64
    ...
    ...
}

RaftLog中的日志条目不是一直存着的，这样内存会爆掉，对于EtcdServer来说,已经应用到KV的日志条目不会再用到了（除非有Follower的日志落后很多），所以EtcdServer会定期对KV做Snapshot，然后告诉raft状态机可以删除已包含在快照中日志。

Storage

日志的持久化存储和最终应用不是raft协议关心的部分，它只是要求节点在收到日志并持久化后才能回复客户端成功。所以etcd并没有把持久化的部分放在raft状态机中，而是通过EtcdServer来做的。
WAL
WAL全称是Write Ahead Log，是数据库中常用的持久化数据的方法。比如我们更新数据库的一条数据，如果直接找到这条数据并更新，可能会耗费比较长的时间。更快更安全的方式是先写一条Log数据到文件中，然后由后台线程来完成最终数据的更新，这条log中通常包含的是一条指令。
etcd通过wal将日志持久化，wal中一条日志的结构如下：

type Record struct {
    Type             int64  `protobuf:"varint,1,opt,name=type" json:"type"`
    Crc              uint32 `protobuf:"varint,2,opt,name=crc" json:"crc"`
    Data             []byte `protobuf:"bytes,3,opt,name=data" json:"data,omitempty"`
    XXX_unrecognized []byte `json:"-"`
}

• Type：日志的类型
  metadataType：元数据，代表Data中存的是节点信息，id、clusterid
  entryType：日志条目，代表Data中是收到的客户端的日志
  stateType：状态，每次HardState有变化时会写一条数据到wal中
  crcType：校验位，读WAL时会根据Crc的值校验防止文件损坏
  snapshotType：Snapshot记录，每做一次KV的snapshot都会记录一条wal日志，这是为了节点重启时恢复数据。

SnapShotter
etcd需要定期对KV做快照，快照的目的一是为了在新的Follower加进来时可以快速复制数据，二是做完快照后可以清除日志释放空间，三是重启时从快照中恢复比从日志中恢复要快的多。

KV
etcd是一个KV数据库，客户端写一条数据给etcd时，通过复制日志将数据发送到超过半数节点，然后写道KV中才会返给客户端成功。etcd的KV使用自研的boltDB实现，提供了事务和监听Key变化的功能。

总结

简单总结了etcd中raft相关的模块，为后面理解raft实现做准备。etcd中对于raft算法的实现都在raft这个struct中，而数据的存储以及集群节点间的通信通过EtcdServer来完成，很好的做了模块的解耦，也使其它的产品可以很容易的集成它的raft实现。
整个Server启动后运行的逻辑如下：

• EtcdServer定时触发raft中的心跳接口，raft根据自身角色决定是发送心跳还是检查是否要发起选举
• EtcdServer调用raft的Ready接口查看是否需要有数据处理，包括需持久化的日志，需要发给Follower的投票、心跳或者日志，需应用到KV的日志等
• EtcdServer在收到其它节点的消息后调用raft的Step触发raft状态机处理
• EtcdServer在收到客户端更新请求时，发送给raft处理，一直到请求在KV中生效，回复客户端成功

后续文章通过阅读源码来理解etcd中的选举、日志复制、持久化实现逻辑。