前言
之前解析过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
以上的架构并不是整个etcd，而只是提取了和Raft相关的模块。从上图中可以看出，etcd中raft协议模块和其它模块是分开的，Raft模块只负责协议状态机的正常转换，而数据的持久化及和其它节点的通信通过EtcdServer调用其它模块来实现。这样就很好的保证了协议部分的低耦合，其它的程序如果要用Raft协议，可以直接将Raft模块集成进自己程序。
EtcdServer
etcd的主线程，代表一个etcd节点。
Storage
负责日志条目的持久化以及数据Snapshot备份
KV
etcd的KV持久化存储，这个模块其实跟raft没有多大关系。因为raft协议只负责告诉使用方什么时候可以把日志应用生效，至于日志中的数据怎么用不是Raft关心的范畴。etcd是KV数据库，它的数据存储在boltDB中。当etcd客户端写数据时，etcd通过raft leader节点将数据复制到超过半数节点并应用到boltDB后返回成功。
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中的选举、日志复制、持久化实现逻辑。
网友评论