一篇文章带给你Etcd-Raft学习

从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致

• Leader 选举，Leader 故障后集群能快速选出新 Leader;
• 日志复制， 集群只有 Leader 能写入日志， Leader 负责复制日志到 Follower 节点，并强制 Follower 节点与自己保持相同;
• 安全性，成员变更，一个任期内集群只能产生一个 Leader、已提交的日志条目在发生 Leader 选举时，一定会存在更高任期的新 Leader 日志中、各个节点的状态机应用的任意位置的日志条目内容应一样等。

Leader 选举

raft 算法本质上是一个大的状态机，任何的操作例如选举、提交数据等，最后都被封装成一个消息结构体，输入到 raft 算法库的状态机中。raft 算法其实由好几个协议组成，etcd-raft 将其统一定义在了 Message 结构体之中，以下总结了该结构体的成员用途：

type Message struct { 
Type             MessageType `protobuf:"varint,1,opt,name=type,enum=raftpb.MessageType" json:"type"` // 消息类型 
To               uint64      `protobuf:"varint,2,opt,name=to" json:"to"` // 消息接收者的节点ID 
From             uint64      `protobuf:"varint,3,opt,name=from" json:"from"` // 消息发送者的节点 ID 
Term             uint64      `protobuf:"varint,4,opt,name=term" json:"term"` // 发送消息的节点的Term值。如果Term值为0，则为本地消息，在etcd-raft模块的实现中，对本地消息进行特殊处理。 
LogTerm          uint64      `protobuf:"varint,5,opt,name=logTerm" json:"logTerm"` // 该消息携带的第一条Entry记录的Term值，日志所处的任期ID 
Index            uint64      `protobuf:"varint,6,opt,name=index" json:"index"` // 日志索引ID，用于节点向 Leader 汇报自己已经commit的日志数据ID 
Entries          []Entry     `protobuf:"bytes,7,rep,name=entries" json:"entries"` // 如果是MsgApp类型的消息，则该字段中保存了Leader节点复制到Follower节点的Entry记录 
Commit           uint64      `protobuf:"varint,8,opt,name=commit" json:"commit"` // 消息发送节点提交日志索引 
Snapshot         Snapshot    `protobuf:"bytes,9,opt,name=snapshot" json:"snapshot"` // 在传输快照时，该字段保存了快照数据 
Reject           bool        `protobuf:"varint,10,opt,name=reject" json:"reject"` // 主要用于响应类型的消息，表示是否拒绝收到的消息 
RejectHint       uint64      `protobuf:"varint,11,opt,name=rejectHint" json:"rejectHint"` //在Follower节点拒绝Leader节点的消息之后，会在该字段记录一个Entry索引值供Leader节点 
Context          []byte      `protobuf:"bytes,12,opt,name=context" json:"context,omitempty"` // 消息携带的一些上下文信息。例如，该消息是否与Leader节点转移相关 
XXX_unrecognized []byte      `json:"-"` 
} 

Message结构体相关的数据类型为 MessageType，MessageType 有 19 种。当然，并不是所有的消息类型都会用到上面定义的Message结构体中的所有字段，因此其中有些字段是Optinal的。

   MsgHup            MessageType = 0  //当Follower节点的选举计时器超时，会发送MsgHup消息 
MsgBeat           MessageType = 1  //Leader发送心跳，主要作用是探活，Follower接收到MsgBeat会重置选举计时器，防止Follower发起新一轮选举 
MsgProp           MessageType = 2  //客户端发往到集群的写请求是通过MsgProp消息表示的 
MsgApp            MessageType = 3  //当一个节点通过选举成为Leader时，会发送MsgApp消息 
MsgAppResp        MessageType = 4  //MsgApp的响应消息 
MsgVote           MessageType = 5  //当PreCandidate状态节点收到半数以上的投票之后，会发起新一轮的选举，即向集群中的其他节点发送MsgVote消息 
MsgVoteResp       MessageType = 6  //MsgVote选举消息响应的消息 
MsgSnap           MessageType = 7  //Leader向Follower发送快照信息 
MsgHeartbeat      MessageType = 8  //Leader发送的心跳消息 
MsgHeartbeatResp  MessageType = 9  //Follower处理心跳回复返回的消息类型 
MsgUnreachable    MessageType = 10 //Follower消息不可达 
MsgSnapStatus     MessageType = 11 //如果Leader发送MsgSnap消息时出现异常，则会调用Raft接口发送MsgUnreachable和MsgSnapStatus消息 
MsgCheckQuorum    MessageType = 12 //Leader检测是否保持半数以上的连接 
MsgTransferLeader MessageType = 13 //Leader节点转移时使用，本地消息 
MsgTimeoutNow     MessageType = 14 //Leader节点转移超时，会发该类型的消息，使Follower的选举计时器立即过期，并发起新一轮的选举 
MsgReadIndex      MessageType = 15 //客户端发往集群的只读消息使用MsgReadIndex消息（只读的两种模式：ReadOnlySafe和ReadOnlyLeaseBased） 
MsgReadIndexResp  MessageType = 16 //MsgReadIndex消息的响应消息 
MsgPreVote        MessageType = 17 //PreCandidate状态下的节点发送的消息 
MsgPreVoteResp    MessageType = 18 //预选节点收到的响应消息   

然后是 raft 算法的实现，node 结构体实现了 Node 接口，对etcd-raft模块具体实现的一层封装，方便上层模块使用etcd-raft模块。其定义如下：

type node struct { 
 
propc      chan msgWithResult      //该通道用于接收MsgProp类型的消息 
 
recvc      chan pb.Message         //除MsgProp外的其他类型的消息都是由该通道接收的 
 
confc      chan pb.ConfChangeV2    //当节点收到EntryConfChange类型的Entry记录时，会转换成ConfChange，并写入该通道中等待处理。在ConfChange中封装了其唯一 ID、待处理的节点 ID （NodeID 字段）及处理类型（Type 字段，例如，ConfChangeAddNode类型表示添加节点）等信息 
confstatec chan pb.ConfState       //在ConfState中封装了当前集群中所有节点的ID，该通道用于向上层模块返回ConfState实例 
 
readyc     chan Ready              //Ready结构体的功能在上一小节已经介绍过了，该通道用于向上层模块返回Ready实例，即node.Ready（）方法的返回值 
 
advancec   chan struct{}           //当上层模块处理完通过上述readyc通道获取到的Ready实例之后，会通过node.Advance（）方法向该通道写入信号，从而通知底层raft实例 
 
tickc      chan struct{}                //用来接收逻辑时钟发出的信号，之后会根据当前节点的角色推进选举计时器和心跳计时器 
 
done       chan struct{}           //当检测到done通道关闭后，在其上阻塞的goroutine会继续执行，并进行相应的关闭操作 
 
stop       chan struct{}           //当node.Stop（）方法被调用时，会向该通道发送信号，在后续介绍中会提到，有另一个goroutine会尝试读取该通道中的内容，当读取到信息之后，会关闭done通道。 
 
status     chan chan Status        //注意该通道的类型，其中传递的元素也是Channel类型，即node.Status（）方法的返回值 
 
 rn        *RawNode 
 
} 

下面我们来看看 raft StateMachine 的状态机转换，实际上就是 raft 算法中各种角色的转换。每个 raft 节点，可能具有以下三种状态中的一种。

• Candidate：候选人状态，该状态意味着将进行一次新的选举。
• Follower：跟随者状态，该状态意味着选举结束。
• Leader：领导者状态，选举出来的节点，所有数据提交都必须先提交到 Leader 上。

每一个状态都有其对应的状态机，每次收到一条提交的数据时，都会根据其不同的状态将消息输入到不同状态的状态机中。同时，在进行 tick 操作时，每种状态对应的处理函数也是不一样的。因此 raft 结构体中将不同的状态及其不同的处理函数，独立出来几个成员变量：

• state，保存当前节点状态;
• tick 函数，每个状态对应的 tick 函数不同;
• step，状态机函数，同样每个状态对应的状态机也不相同

我们接着看 etcd-raft 状态转换。etcd-raft StateMachine 封装在 raft机构体中，etcd为了不让entry落后的太多的直接进行选举，多了一个其PreCandidate状态，转换如下图：

raft 状态转换的接口都在 raft.go 中，其定义如下：

//在newRaft（）函数中完成初始化之后，会调用 becomeFollower（）方法将节点切换成 Follower状态，其中会设置raft实例的多个字段 
func (r *raft) becomeFollower(term uint64, lead uint64) { 
 r.step = stepFollower //设置函数处理Follower节点处理消息的行为 
 r.reset(term) //在reset（）方法中会重置raft实例的多个字段 
 r.tick = r.tickElection //将tick字段设置成tickElection函数 
 r.lead = lead //设置当前节点的leader节点 
    //修改当前节点的角色 
 r.state = StateFollower 
} 
 
//如果当前集群开启了 PreVote 模式，当 Follower 节点的选举计时器超时时，会先调用becomePreCandidate（）方法切换到PreCandidate状态，becomePreCandidate（） 
func (r *raft) becomePreCandidate() { 
    //检查当前节点的状态，禁止leader直接切换到PreCandidate状态 
 if r.state == StateLeader { 
  panic("invalid transition [leader -> pre-candidate]") 
 } 
    //设置函数处理Candidate节点处理消息的行为 
 r.step = stepCandidate  
 r.prs.ResetVotes() 
 r.tick = r.tickElection 
 r.lead = None 
    //修改当前节点的角色 
 r.state = StatePreCandidate  
} 
//当节点可以连接到集群中半数以上的节点时，会调用 becomeCandidate（）方法切换到Candidate状态，becomeCandidate（） 
func (r *raft) becomeCandidate() { 
 // TODO(xiangli) remove the panic when the raft implementation is stable 
 if r.state == StateLeader { 
  panic("invalid transition [leader -> candidate]") 
 } 
    //在reset（）方法中会重置raft实例的多个字段 
 r.step = stepCandidate 
 r.reset(r.Term + 1) //在reset（）方法中会重置raft实例的多个字段 
 r.tick = r.tickElection 
 r.Vote = r.id //在此次的选举中，Candidate节点会将选票投给自己 
    //修改当前节点的角色 
 r.state = StateCandidate 
} 
 
//当 Candidate 节点得到集群中半数以上节点的选票时，会调用 becomeLeader（）方法切换成Leader状态，becomeLeader（） 
func (r *raft) becomeLeader() { 
    //检查当前节点的状态，机制从follower直接切换成leader状态 
 if r.state == StateFollower { 
  panic("invalid transition [follower -> leader]") 
 } 
 r.step = stepLeader 
 r.reset(r.Term) //在reset（）方法中会重置raft实例的多个字段 
 r.tick = r.tickHeartbeat 
 r.lead = r.id //将leader字段设置成当前节点的id 
 r.state = StateLeader //更新当前节点的角色 
    //检查未提交的记录中是否存在多条集群配置变更的Entry记录 
 r.prs.Progress[r.id].BecomeReplicate() 
 r.pendingConfIndex = r.raftLog.lastIndex() 
 emptyEnt := pb.Entry{Data: nil} 
    //向当前节点的raftLog中追加一条空的Entry记录 
 if !r.appendEntry(emptyEnt) { 
    } 
 r.reduceUncommittedSize([]pb.Entry{emptyEnt}) 
} 

tick 函数，每个状态对应的 tick 函数不同，下面分析两个tick：

func (r *raft) tickElection() { 
 r.electionElapsed++ //递增electionElapsed计时器 
 
 if r.promotable() && r.pastElectionTimeout() { //检查是否在集群中与检查单签的选举计时器是否超时 
  r.electionElapsed = 0 
  r.Step(pb.Message{From: r.id, Type: pb.MsgHup}) //发起step处理pb.MsgHup类型消息。 
 } 
} 
 
func (r *raft) tickHeartbeat() { 
 r.heartbeatElapsed++ //递增heartbeatElapsed计时器 
 r.electionElapsed++ //递增electionElapsed计时器 
 if r.electionElapsed >= r.electionTimeout { 
  r.electionElapsed = 0 //重置选举计时器，leader节点不会主动发起选举 
  if r.checkQuorum { //进行多数检查 
   r.Step(pb.Message{From: r.id, Type: pb.MsgCheckQuorum}) //发起大多数检查。 
  } 
        //选举计时器处于electionElapsed~randomizedElectionTimeout时段之间时，不能进行leader转移 
  if r.state == StateLeader && r.leadTransferee != None { 
   r.abortLeaderTransfer() //清空raft.leadTransferee字段，放弃转移 
  } 
 } 
 if r.state != StateLeader { //只有laeder能发送tickHeartbeat 
  return 
 } 
 if r.heartbeatElapsed >= r.heartbeatTimeout { //心跳计时器超时 
  r.heartbeatElapsed = 0 //重置心跳计时器 
  r.Step(pb.Message{From: r.id, Type: pb.MsgBeat}) //发起step处理MsgBeat类型消息 
 } 
} 

跟随者、预选候选人、候选人、领导者 4 种节点状态都有分别对应的功能函数，当需要查看各节点状态相关的功能实现时(比如，跟随者如何接收和处理日志)，都可以将对应的函数作为入口函数，来阅读代码和研究功能实现。

日志复制

这里重点看一下raft.appendEntry()方法，它的主要操作步骤如下：(1)设置待追加的Entry记录的Term值和Index值。

(2)向当前节点的raftLog中追加Entry记录。

(3)更新当前节点对应的Progress实例。

(4)尝试提交Entry记录，即修改raftLog.committed字段的值。

raft.appendEntry()方法的具体实现如下：

func (r *raft) appendEntry(es ...pb.Entry) (accepted bool) { 
 li := r.raftLog.lastIndex()//获取raftLog中最后一条记录的索引值 
 for i := range es {//更新待追加记录的Term值和索引值 
  es[i].Term = r.Term//Entry记录的Term指定为当前leader节点的任期号 
  es[i].Index = li + 1 + uint64(i) //为日志记录指定的Index 
 } 
 li = r.raftLog.append(es...)//向raft中追加记录 
    //更新当前节点对应的Progress,主要是更新Next和Match 
 r.prs.Progress[r.id].MaybeUpdate(li) 
    //尝试提交Entry记录 
 r.maybeCommit() 
 return true 
} 

在Progress.mayUpdate()方法中，会尝试修改Match字段和Next字段，用来标识对应节点Entry记录复制的情况。Leader节点除了在向自身raftLog中追加记录时(即appendEntry()方法)会调用该方法，当Leader节点收到Follower节点的MsgAppResp消息(即MsgApp消息的响应消息)时，也会调用该方法尝试修改Follower节点对应的Progress实例。Progress.MayUpdate()方法的具体实现如下：

func (pr *Progress) MaybeUpdate(n uint64) bool { 
 var updated bool 
 if pr.Match < n { 
  pr.Match = n //n之前所有的Entry记录都已经写入对应节点的raftLog中 
  updated = true 
        //下面将Progress.paused设置为false，表示leader节点可以继续向对应Follower 
        //节点发送MsgApp消息 
  pr.ProbeAcked() 
 } 
 pr.Next = max(pr.Next, n+1)//将Next值加一，下一次复制Entry记录开始的位置 
 return updated 
} 

如果该Entry记录已经复制到了半数以上的节点中，则在raft.maybeCommit()方法中会尝试将其提交。除了 appendEntry()方法，在 Leader 节点每次收到 MsgAppResp 消息时也会调用maybeCommit()方法，maybeCommit()方法的具体实现如下：

func (r *raft) maybeCommit() bool { 
 mci := r.prs.Committed() 
 return r.raftLog.maybeCommit(mci, r.Term) 
} 
 
func (p *ProgressTracker) Committed() uint64 { 
 return uint64(p.Voters.CommittedIndex(matchAckIndexer(p.Progress))) 
} 
//将node分两个组，JointConfig是大多数的组，有兴趣的看一看quorum包的实现 
func (c JointConfig) CommittedIndex(l AckedIndexer) Index {//比较大多数的node的前俩个Index，返回Match的值。 
 idx0 := c[0].CommittedIndex(l) 
 idx1 := c[1].CommittedIndex(l) 
 if idx0 < idx1 { 
  return idx0 
 } 
 return idx1 
} 
//更新raftLog.committed字段，完成提交 
func (l *raftLog) maybeCommit(maxIndex, term uint64) bool { 
 if maxIndex > l.committed && l.zeroTermOnErrCompacted(l.term(maxIndex)) == term { 
  l.commitTo(maxIndex) 
  return true 
 } 
 return false 
} 

etcd 将 raft 相关的所有处理都抽象为了 Message，通过 Step 接口处理各类消息的入口，首先根据Term"值"对消息进行分类处理，再根据消息的"类型"进行分类处理：

func (r *raft) Step(m pb.Message) error { 
 switch {//首先根据消息的Term值进行分类处理 
 case m.Term == 0://本地消息不做处理。MsgHup，MsgProp和MsgReadIndex是本地消息 
 case m.Term > r.Term: 
 case m.Term < r.Term://细节部分，可以自己研究源码 
 } 
 switch m.Type {//根据Message的Type进行分类处理 
 case pb.MsgHup://这里针对MsgHup类型的消息进行处理。 
  if r.preVote {//检查是不是开启了preVote，如果是开启了先调用raft.hup方法，发起preVote。 
  } else { 
   r.hup(campaignElection)//下面讲述 
  } 
 case pb.MsgVote, pb.MsgPreVote: //对MsgVote，MsgPreVote类型的消息进行处理。 
  canVote := r.Vote == m.From || 
   (r.Vote == None && r.lead == None) || 
   (m.Type == pb.MsgPreVote && m.Term > r.Term) 
  if canVote && r.raftLog.isUpToDate(m.Index, m.LogTerm) { 
   r.send(pb.Message{To: m.From, Term: m.Term, Type: voteRespMsgType(m.Type)}) 
   if m.Type == pb.MsgVote { 
    r.electionElapsed = 0 
    r.Vote = m.From 
   } 
  } else { 
   r.send(pb.Message{To: m.From, Term: r.Term, Type: voteRespMsgType(m.Type), Reject: true}) 
  } 
 default://对于其他类型的消息处理，对应的node的step函数处理 
  err := r.step(r, m) 
  if err != nil { 
   return err 
  } 
 } 
 return nil 
} 

这里主要使用hup函数对Message来做处理，在raft.campaign()方法中，除了完成状态切换，还会向集群中的其他节点发送相应类型的消息，例如，如果当前 Follower 节点要切换成 PreCandidate 状态，则会发送 MsgPreVote 消息：

func (r *raft) hup(t CampaignType) { 
 if r.state == StateLeader {//忽略leader 
  return 
 } 
    //方法会检查prs字段中是否还存在当前节点对应的Progress实例，这是为了监测当前节点是否被从集群中移除了 
    if !r.promotable() { 
  return 
 } 
    //获取raftLog中已提交但未应用的Entry记录，异常处理 
 ents, err := r.raftLog.slice(r.raftLog.applied+1, r.raftLog.committed+1, noLimit) 
 r.campaign(t) 
} 
func (r *raft) campaign(t CampaignType) { 
    //该方法的会发送一条包含Term值和类型 
 var term uint64 
 var voteMsg pb.MessageType 
 if t == campaignPreElection {//切换的目标状态是Precandidate 
  r.becomePreCandidate() 
  voteMsg = pb.MsgPreVote 
        //确定要发送的Term值，这里只是增加了消息的Term值，并未增加raft.term字段的值 
  term = r.Term + 1 
 } else {//切换的目标状态是Candidate 
  r.becomeCandidate() 
  voteMsg = pb.MsgVote 
        //给raft.Term字段的值，并将当前节点的选票投给自身 
  term = r.Term 
 } 
 if _, _, res := r.poll(r.id, voteRespMsgType(voteMsg), true); res == quorum.VoteWon { 
        //当得到足够的选票时，则将PreCandidate状态的节点切换成Candidate状态 
        //Candidate状态的节点则切换成Leader状态 
  if t == campaignPreElection { 
   r.campaign(campaignElection) 
  } else { 
   r.becomeLeader() 
  } 
  return 
 } 
 var ids []uint64 
 { 
  idMap := r.prs.Voters.IDs() 
  ids = make([]uint64, 0, len(idMap)) 
  for id := range idMap { 
   ids = append(ids, id) 
  } 
  sort.Slice(ids, func(i, j int) bool { return ids[i] < ids[j] }) 
 } 
 for _, id := range ids {//状态切换完成之后，当前节点会向集群中所有节点发送指定类型的消息 
  if id == r.id { //跳过当前节点自身 
   continue 
  } 
        var ctx []byte 
        //在进行Leader节点转移时，MsgPreVote或MsgVote消息会在Context字段中设置该特殊值 
  if t == campaignTransfer { 
   ctx = []byte(t) 
  } 
        //发送指定类型的消息，其中Index和LogTerm分别是当前节点的raftLog 
        //最后一条消息的Index值和Term值 
  r.send(pb.Message{Term: term, To: id, Type: voteMsg, Index: r.raftLog.lastIndex(), LogTerm: r.raftLog.lastTerm(), Context: ctx}) 
 } 
} 

Follower 节点在选举计时器超时的行为：首先它会通过 tickElection()创建MsgHup消息并将其交给raft.Step()方法进行处理;raft.Step()方法会将当前Follower节点切换成PreCandidate状态，然后创建MsgPreVote类型的消息，最后将该消息追加到raft.msgs字段中，等待上层模块将其发送出去。

本文转载自微信公众号「运维开发故事」，可以通过以下二维码关注。转载本文请联系运维开发故事公众号。