前言

之前解析過Raft協(xié)議基本原理（傳送門），一直想找個具體實現(xiàn)來看一下。Etcd是一款開源的分布式KV數(shù)據(jù)庫，由于K8S中使用它作為注冊和配置中心而被廣泛認知。跟它最類似的產品還有相同應用場景Zookeeper，經常被用作注冊中心和分布式鎖。Etcd也是比較早的使用Raft協(xié)議來實現(xiàn)分布式存儲的產品，而且它的架構設計中將raft協(xié)議部分單獨剝離出來，這樣其它的程序如果想用raft協(xié)議，可以直接依賴它的raft模塊。后續(xù)幾篇文章將通過etcd源碼來查看如何完整實現(xiàn)一個Raft協(xié)議。

知識準備

Etcd是使用Go語言實現(xiàn)的，如果之前沒了解過Go但是用過其它面向對象的語言（如Java），相信對文章中90%以上內容的理解都不會有問題。如果想要自己對照著源碼一起看文章，了解下Go的基本概念還是必要的?？梢灾亓私庀翯o的如下特性：

• interface和struct
• 方法和函數(shù)的區(qū)別
• channel 通道，Go語言設計思想的核心，etcd設計中大量用到

etcd架構

Etcd本質上是一個分布式KV數(shù)據(jù)庫，Raft只是它為了實現(xiàn)分布式數(shù)據(jù)一致性所采用的協(xié)議。在整個架構上，我們只需要關心圍繞著Raft部分模塊的設計。相關模塊的架構如下：

EtcdServer

模塊分解

EtcdServer

EtcdServer可以看作是etcd節(jié)點的核心控制器，它即實現(xiàn)了etcd的一個服務節(jié)點，每個EtcdServer都包含了一個Raft的節(jié)點實現(xiàn)。它主要包含如下的功能：
節(jié)點初始化
etcd節(jié)點啟動時會初始化并啟動一個EtcdServer，啟動的過程主要包含如下的部分：

• 重啟時會加載之前已經持久化到磁盤的數(shù)據(jù)，恢復整個Server。數(shù)據(jù)包括WAL中的日志數(shù)據(jù)和KV的snapshot數(shù)據(jù)。etcd節(jié)點在運行過程中，如果數(shù)據(jù)已經寫到boltDB中，則會永久存儲。但是日志數(shù)據(jù)有可能還沒有commit或者apply，這部分數(shù)據(jù)會在WAL文件中，etcd啟動時會重新將這部分數(shù)據(jù)重新加載到raft內存中。
• 啟動Raft狀態(tài)機，啟動后將通過raftNode和raft狀態(tài)機進行交互
• 初始化和集群中其它節(jié)點的通信

請求通信
EtcdServer會發(fā)送/接收兩種來源的請求，客戶端和集群其它節(jié)點

• 客戶端請求，EtcdServer收到客戶端的寫請求和線性讀請求后，會交給Raft來處理，然后等待處理完成后回復客戶端。
• 集群節(jié)點間的請求，包括心跳、投票、日志復制，當raft模塊發(fā)現(xiàn)需要有請求發(fā)送給其它節(jié)點時就會通過EtcdServer來轉發(fā)，這樣就降低了Raft模塊的復雜性。

發(fā)起心跳
EtcdServer通過內置一個定時器來定時觸發(fā)Raft的心跳接口。如果是Leader，則發(fā)送心跳給集群中其他節(jié)點；如果是Follower則檢查Leader的心跳是否超時，以決定是否發(fā)起一次新的選舉 。

日志持久化
上面的架構圖中，Raft模塊也保存有日志條目，但是這個日志條目其實只是在內存中，真正的數(shù)據(jù)持久化是由EtcdServer完成的?；貞浵翿aft協(xié)議中，只規(guī)定了哪些數(shù)據(jù)和屬性應該持久化，而并沒有規(guī)定怎么存，存在什么地方。所以etcd將持久化部分和Raft協(xié)議部分分開實現(xiàn)是合理的。

KV數(shù)據(jù)操作
Raft協(xié)議只保證日志復制的一致性，對于最終日志應用不關心。etcd是KV數(shù)據(jù)庫，所以收到raft可以將日志應用的時候，就會將日志中包含的操作應用到后端的KV存儲中。KV存儲部分的邏輯不屬于Raft的范圍，所以后續(xù)不會關注這一塊的實現(xiàn)。

Raft

Raft模塊是協(xié)議算法的實現(xiàn)，后續(xù)的源碼解讀也會集中在這一模塊上。
Node
Node接口代表raft集群中的一個節(jié)點，對外提供操作raft協(xié)議節(jié)點的方法。如果有別的程序想只使用etcd的raft實現(xiàn)的話，可以啟動一個Node，然后直接調用這個接口來和raft狀態(tài)機交互就可以了。

type Node interface {
    // 觸發(fā)一次心跳，raft會在觸發(fā)后檢查leader選舉超時或發(fā)送心跳
    Tick()
    // 觸發(fā)節(jié)點將自己變成候選人，開始選舉
    Campaign(ctx context.Context) error
    // 提交日志條目
    Propose(ctx context.Context, data []byte) error
    // 集群配置變更
    ProposeConfChange(ctx context.Context, cc pb.ConfChangeI) error
    // 發(fā)送一條消息給狀態(tài)機，觸發(fā)狀態(tài)變化
    Step(ctx context.Context, msg pb.Message) error
    // 如果raft狀態(tài)機有變化，會通過channel返回一個Ready的數(shù)據(jù)結構，里面包含變化信息，比如日志變化、心跳發(fā)送等。調用方在處理完后需要調用Advance()方法告訴狀態(tài)機上一個Ready處理完了
    Ready() <-chan Ready
    Advance()
    // 應用集群變化到狀態(tài)機
    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當前狀態(tài).
    Status() Status
    // 告訴狀態(tài)機指定id節(jié)點不可達.
    ReportUnreachable(id uint64)
    // 告訴狀態(tài)機給id節(jié)點發(fā)送snapshot的最終處理狀態(tài).
    ReportSnapshot(id uint64, status SnapshotStatus)
    // 關閉節(jié)點.
    Stop()
}

struct node 是Node接口的默認實現(xiàn)，它包含了多了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狀態(tài)機數(shù)據(jù)時比對狀態(tài)是否有變化。

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

RawNode對于狀態(tài)機操作的方法都直接發(fā)給raft，比如接收新日志的方法實現(xiàn)如下：

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狀態(tài)機有變化時，包括狀態(tài)和數(shù)據(jù)變化，通過Ready()方法就可以取到變化的數(shù)據(jù)，調用方拿到數(shù)據(jù)后該持久化的持久化，該發(fā)送的發(fā)送。在調用方處理完后調用Advance()方法通知raft狀態(tài)機已處理完成。
raft
協(xié)議算法的核心實現(xiàn)，實際上就是一個狀態(tài)機的實現(xiàn)，當有外部請求來的時候，比如新的日志，發(fā)送心跳等，就調用它的Step()方法來觸發(fā)狀態(tài)機。它維護了Raft協(xié)議中規(guī)定的所有屬性，如Term、CommitIndex、Vote等。同時通過RaftLog來持有日志。

type raft struct {
    //在raft集群中的唯一id
    id uint64
    //選舉周期
    Term uint64
    //上一次投票的節(jié)點，Leader等于自己的id
    Vote uint64
    //線性讀狀態(tài)
    readStates []ReadState
    // 日志
    raftLog *raftLog
    ....
    // 跟蹤Follower節(jié)點的狀態(tài)，比如日志復制的matchIndex
    prs tracker.ProgressTracker
    // 當前節(jié)點的類型
    state StateType
    // 節(jié)點是不是 learner.
    isLearner bool
     // 待發(fā)送給其它節(jié)點的消息
    msgs []pb.Message
    // leader id，leader人工轉移時的目標節(jié)點
    leadTransferee uint64
    ...
    // 還未提交的日志條數(shù)，非準確值
    uncommittedSize uint64
    readOnly *readOnly
    // 選舉時記錄ticks
    electionElapsed int
    // 記錄心跳的ticks
    heartbeatElapsed int
    ...
    //心跳超時
    heartbeatTimeout int
    // 選舉超時
    electionTimeout  int
    //隨機選舉超時
    randomizedElectionTimeout int
    disableProposalForwarding bool

    tick func()
    step stepFunc
    ...
}

raft的屬性基本跟raft協(xié)議中規(guī)定的節(jié)點的屬性對應，其中raftLog在內存中存儲了日志條目，prs跟蹤節(jié)點日志復制的進度。
關于心跳和選舉超時的計時，etcd是用tick的方式來計算的，每兩次tick之間的耗時其實就是心跳時間。所有的超時都是以tick的倍數(shù)來計算的，比如electionTimeout等于2，就是選舉超時是兩倍的心跳時間間隔。randomizedElectionTimeout就是raft協(xié)議中建議的，選舉超時應該是在一個范圍內的隨機值，防止所有Follower在Leader超時后同時發(fā)起選舉。
msg屬性用來存儲需要處理的消息，比如心跳。前面講過raft模塊只負責狀態(tài)機的算法處理，而持久化及通信部分則交給調用方處理，這個msg就是存放需要處理的消息。
raft中最后兩個屬性tick和step是函數(shù)類型，在節(jié)點處于不同角色時，這個屬性對應的方法實現(xiàn)是不一樣的。比如tick()方法，在Follower中被調用時是檢查距離上次收到Leader心跳是否超時，而在Leader中是向Follower發(fā)送心跳。step()方法也一樣，不同的節(jié)點類型收到同一種消息時的處理邏輯是不一樣的。

函數(shù)類型對Java程序員可能比較陌生，在有的語言中也叫方法指針。是指一個成員變量指向的是一個方法，在賦值的時候是將一個方法實現(xiàn)賦給這個變量

其它概念

• HardState, 封裝了raft協(xié)議中規(guī)定的需要實時持久化的狀態(tài)屬性：當前選舉周期、投票和已提交的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協(xié)議中規(guī)定的無需持久化的狀態(tài)信息：當前的Leader，節(jié)點角色

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

• state，一個raft節(jié)點只可能是4中角色中的一種：
  Follower：接收Leader的日志
  Candidate： 發(fā)起投票的候選人
  Leader：發(fā)送心跳和日志給Follower
  PreCandidate：如果PreVote打開的話，在正式變成候選人之前需要獲得超半數(shù)節(jié)點的同意，在征詢意見時節(jié)點處于的角色
• step，所有發(fā)給對狀態(tài)機的請求，其實都是調用的它的step方法，對于不同的角色，處理Step方法的參數(shù)邏輯也是不一樣的

RaftLog

從名字可以看出，RaftLog用于存儲日志條目，它的所有數(shù)據(jù)都是在內存中。

type raftLog struct {
    // 上一次snapshot之后，已經被持久化的日志條目
    storage Storage
    // 所有還沒有被持久化的日志條目
    unstable unstable
    // 已經commit的日志index
    committed uint64
    // 已經應用到狀態(tài)機的日志的index
    applied uint64
    ...
    ...
}

RaftLog中的日志條目不是一直存著的，這樣內存會爆掉，對于EtcdServer來說,已經應用到KV的日志條目不會再用到了（除非有Follower的日志落后很多），所以EtcdServer會定期對KV做Snapshot，然后告訴raft狀態(tài)機可以刪除已包含在快照中日志。

Storage

日志的持久化存儲和最終應用不是raft協(xié)議關心的部分，它只是要求節(jié)點在收到日志并持久化后才能回復客戶端成功。所以etcd并沒有把持久化的部分放在raft狀態(tài)機中，而是通過EtcdServer來做的。
WAL
WAL全稱是Write Ahead Log，是數(shù)據(jù)庫中常用的持久化數(shù)據(jù)的方法。比如我們更新數(shù)據(jù)庫的一條數(shù)據(jù)，如果直接找到這條數(shù)據(jù)并更新，可能會耗費比較長的時間。更快更安全的方式是先寫一條Log數(shù)據(jù)到文件中，然后由后臺線程來完成最終數(shù)據(jù)的更新，這條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：元數(shù)據(jù)，代表Data中存的是節(jié)點信息，id、clusterid
  entryType：日志條目，代表Data中是收到的客戶端的日志
  stateType：狀態(tài)，每次HardState有變化時會寫一條數(shù)據(jù)到wal中
  crcType：校驗位，讀WAL時會根據(jù)Crc的值校驗防止文件損壞
  snapshotType：Snapshot記錄，每做一次KV的snapshot都會記錄一條wal日志，這是為了節(jié)點重啟時恢復數(shù)據(jù)。

SnapShotter
etcd需要定期對KV做快照，快照的目的一是為了在新的Follower加進來時可以快速復制數(shù)據(jù)，二是做完快照后可以清除日志釋放空間，三是重啟時從快照中恢復比從日志中恢復要快的多。

KV
etcd是一個KV數(shù)據(jù)庫，客戶端寫一條數(shù)據(jù)給etcd時，通過復制日志將數(shù)據(jù)發(fā)送到超過半數(shù)節(jié)點，然后寫道KV中才會返給客戶端成功。etcd的KV使用自研的boltDB實現(xiàn)，提供了事務和監(jiān)聽Key變化的功能。

總結

簡單總結了etcd中raft相關的模塊，為后面理解raft實現(xiàn)做準備。etcd中對于raft算法的實現(xiàn)都在raft這個struct中，而數(shù)據(jù)的存儲以及集群節(jié)點間的通信通過EtcdServer來完成，很好的做了模塊的解耦，也使其它的產品可以很容易的集成它的raft實現(xiàn)。
整個Server啟動后運行的邏輯如下：

• EtcdServer定時觸發(fā)raft中的心跳接口，raft根據(jù)自身角色決定是發(fā)送心跳還是檢查是否要發(fā)起選舉
• EtcdServer調用raft的Ready接口查看是否需要有數(shù)據(jù)處理，包括需持久化的日志，需要發(fā)給Follower的投票、心跳或者日志，需應用到KV的日志等
• EtcdServer在收到其它節(jié)點的消息后調用raft的Step觸發(fā)raft狀態(tài)機處理
• EtcdServer在收到客戶端更新請求時，發(fā)送給raft處理，一直到請求在KV中生效，回復客戶端成功

后續(xù)文章通過閱讀源碼來理解etcd中的選舉、日志復制、持久化實現(xiàn)邏輯。