etcd raft

断断续续花了一个半月的时间，终于将etcd中raft具体实现的代码大致过了一遍，将其设计以及workflow基本梳理清楚了。以后遇到任何相关的问题，再来看代码，应该会容易很多。我是直接看的master上的代码，看的过程中pull过一次github上的代码，目前本地最后一个commit是：

0c1e6d05e7d19f5c35ec15b6bbb49090b476f118

本文主要是做一个阶段性的总结。在本文中，我不会讲述过多的代码细节，因为如果你从来没有看过相关的代码，甚至也没有看过相关的paper，那么就是听天书，毫无意义。本文主要是分享总结其设计以及workflow。

相关的论文

看代码之前，一定要仔细看一下相关的论文。etcd raft就是根据下面的论文实现的。我看的是第一篇论文，第二篇还没来得及看。

https://raft.github.io/raft.pdf https://github.com/ongardie/dissertation/blob/master/stanford.pdf

作者在设计raft算法的时候，主要看重的是易懂性。其实主要就是和Paxos做对比。Paxos虽然曾经是共识算法事实上的标准，但它实在太难理解了，所以作者才设计了更为简单易懂的raft。

raft算法中有两个最重要也是最基本的概念：

1. Term: 任期，每个任期内最多有一个节点当选为leader。任期是一个单调递增的整数。
   

2. Index：日志索引，每一条命令都对应一个全局唯一的索引。也是递增的整数。
   

raft算法解决几个主要问题是：

1.  leader选举；
   

2. 日志复制；

3. 日志压缩；
   

4. 成员变化；
   

leader通过周期性的heartbeat来维持自己的leader地位，如果follower超过一定的时间没有收到heartbeat，follower就会发起新一轮的选举。选举的过程就是投票的过程，谁获得了超过半数的票，谁就当选为leader。

leader会负责处理用户的写请求，并将数据分发到其它节点。随着时间的推移，日志数据会越来越多，所以需要进行日志压缩，方法就是生成快照(snapshot)，然后截止到快照的Index的所有日志都可以删除了。

raft还支持动态的成员改变，比如增加或者删除成员。这里一个关键的问题是要防止在成员改变过程中，有两个成员同时当选leader的情况。采用的措施就是两阶段的配置改变。

raft的实现思想

在etcd中，raft是作为一个library存在的，要了解其设计思想，首先肯定要阅读它的readme文档：

https://github.com/etcd-io/etcd/tree/master/raft

etcd中的raft是目前使用最广泛的raft library，它与其它raft实现最大的区别在于它的实现中不包含传输以及存储。用户需要自己去实现传输和存储，对于etcd来说，用户就是etcdserver。这么设计的好处就是其设计与实现很简单，也很灵活。

raft library内部主要是维护了一个状态机。

另外，值得一提的是raft与上层应用的交互不是通过直接的函数调用，而是通过异步的channel。虽然raft提供一个接口Node(如下)来供上层应用直接调用，但其实也是channel的一个封装而已。

// Node represents a node in a raft cluster.
type Node interface {
  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
  Ready() <-chan Ready


  Advance()
  ApplyConfChange(cc pb.ConfChangeI) *pb.ConfState


  TransferLeadership(ctx context.Context, lead, transferee uint64)me rctx attached.
  ReadIndex(ctx context.Context, rctx []byte) error
  
  Status() Status
  ReportUnreachable(id uint64)
  ReportSnapshot(id uint64, status SnapshotStatus)


  Stop()
}

raft library与上层应用之间的交互可以通过下面这个简单的图来说明。其中的consumer就是指应用层。raft library的处理结果通过ready channel传递给应用层。而应用层主要是通过调用Step方法将消息传递给raft library。

应用层还可以通过调用Propose和ProposeConfChange这两个方法将数据传递给raft library。

传输以及存储接口

前面已经讲过，raft library并不实现具体的传输以及存储。在raft library中只是定义相应的接口。存储接口定义如下：

type Storage interface {
  InitialState() (pb.HardState, pb.ConfState, error)


  Entries(lo, hi, maxSize uint64) ([]pb.Entry, error)
  Term(i uint64) (uint64, error)


  LastIndex() (uint64, error)
  FirstIndex() (uint64, error)


  Snapshot() (pb.Snapshot, error)
}

raft library有一个对应的存储实现MemoryStorage，具体代码位置：

https://github.com/etcd-io/etcd/blob/8162d9cbdfd38eac35c218883f4b01e47450bcee/raft/storage.go#L46

可能有人就会问，前面不是说raft library不具体实现传输和存储吗，怎么这里又实现了一个MemoryStorage？注意，这里的存储实现并不持久化，应用层仍然需要实现自己的存储，并持久化。

对应的传输接口如下：

type Transporter interface {
  // Start starts the given Transporter.
  // Start MUST be called before calling other functions in the interface.
  Start() error
  Handler() http.Handler
  Send(m []raftpb.Message)
  SendSnapshot(m snap.Message)


  AddRemote(id types.ID, urls []string)
  AddPeer(id types.ID, urls []string)
  RemovePeer(id types.ID)
  RemoveAllPeers()
  UpdatePeer(id types.ID, urls []string)
  
  ActiveSince(id types.ID) time.Time
  ActivePeers() int


  Stop()
}

对应的代码位置：

https://github.com/etcd-io/etcd/blob/8162d9cbdfd38eac35c218883f4b01e47450bcee/server/etcdserver/api/rafthttp/transport.go#L42

这里要说明一点，其实传输接口的定义并不属于raft library的一部分。因为raft library是通过channel与应用层交互。应用层通过channel获取到需要的数据之后，怎么传输，完全是应用层自己的事情。

raft处理逻辑

raft library内部主要通过一个goroutine来循环处理消息。具体代码位置：

https://github.com/etcd-io/etcd/blob/8162d9cbdfd38eac35c218883f4b01e47450bcee/raft/node.go#L300

消息主要有两个来源。一个来源就是Timer，就是固定间隔的周期性的触发。每次触发执行的时候，节点会根据自己的身份做不同的处理。例如follower，会判断是否超过了election timeout，如果超过了，就会发起新一轮的选举。另一个来源，就是来自应用层的各种消息，比如client的请求等。

说是两个来源，其实是一个来源，都是来自于应用层。

WAL

WAL是Write Ahead Log的首字母缩写。所有写入etcd的数据都会先写入WAL文件并持久化，然后才会写入MemoryStorage或db文件。etcd在启动的时候，会replay WAL文件中的数据(命令)。

并不是每一个用户的写请求的数据都会被持久化化到snapshot或者db文件，但是所有经过raft处理过的数据(命令)肯定会持久化到WAL文件。

WAL不属于raft的范畴，但是它是保证数据不丢失的关键，所以这里单独提一下。

raftexample

etcd中的raft只是一个library，所以我们可以用它来实现我们自己的各种分布式应用。etcd官方还特意提供了一个example(分布式Key-value数据库)来演示如何使用raft library，也就是raftexample，链接如下：

https://github.com/etcd-io/etcd/tree/master/contrib/raftexample

这个例子本身并不复杂，核心还是要理解上面说的raft library。读代码的过程中，画了一个简略的图(如下)。图片橙色标注的node是raft library与应用层交互的边界，左侧(以及上面部分)是属于raft library的范畴，右下侧是应用层以及传输层。这个图大概看看就行了，如果真有兴趣仔细看，就看看我上面说的几个接口所在的位置。

--END--