学习分享｜Etcd/Raft 原理篇

发表于 11月以前 | 总阅读数：350 次

近期负责的项目中有一个场景需要依赖数据一致性算法，因此做了一些相关的调研。

本文是根据近期对【Etcd-Raft】的学习把自己的理解做个简单整理和分享。

注：本文并没有对Etcd/Raft源码和流程事无巨细的解剖，更多地关注其核心功能以及过程中个人觉得值得学习的点。

前言

Raft是什么？

Etcd是什么？

为什么选择etcd-raft

文章主要讲解 etcd/raft——原理解析篇。

一、原理解析

1. 最小原则

etcd中实现的raft实现本质上是提供了一个基于raft的sdk，作为sdk方式接入到etcd中，和etcd存储系统是解耦的。同时sdk的实现非常巧妙，只实现了基本的功能，包括leader选举、日志处理、状态变更等逻辑。上层的网络传输、数据存储等模块，提供接口由上层应用者来实现：

存储层：定义了Storage接口用来管理raft log，用户也可以自行实现该接口并作为参数传入，非常灵活；同时也提供了对该接口一个基于改接口的存储实现MemoryStorage，该实现是基于内存数组实现的非持久化的存储。
网络层：节点间的数据通信这部分在实现中没有做任何约束，通过channel来和应用层交互，由应用层用户自定义实现来处理收到的消息。

简单画个图来表达这种设计：

我暂且把这种设计原则称之为“最小原则”，sdk中只实现基本的核心功能，sdk依赖的其他能力只定义好接口，通过参数或者其他的方式进行注入。

（后续的开发中可以借鉴这种思想，不一定大而全的sdk实现就是好用的，可能反而会冗余或者互相依赖等，当然也要分具体的场景具体分析）

2. 核心功能

一条数据提交到raft集群后，etcd/raft内部保证数据在集群各节点是一致的，其实现流程如下：

整个etcd/raft可以抽象概括为2大模块：

日志复制模块：外部提交的数据统称为日志，通过日志复制算法，实现数据的分布式一致性。
集群变更选举模块：实现集群选举功能，和集群节点配置的管理，同时对原生raft选主算法做了一些算法和性能优化。

下面分别针对这两大功能结合代码做详细介绍。

2.1. 日志复制模块

日志存储结构

type raftLog struct {
  // storage存储了从最后一次snapshot到现在的所有可靠的（stable）日志（Entry),即保存到snapshot之后提交的数据，
    // 同时Storage定义为接口，由上层使用者实现和维护的，raft需要访问的时候直接读取无需访问上层持久化的存储。
  storage Storage
  // 用于保存还没有持久化的数据和快照，与storage形成了鲜明的对比，使用者没有通知raft日志持久化完毕前，这些日志都还不可靠
    // 当使用者持久化完毕后，这些日志就会从unstable删除，最终都会保存到storage中
  unstable unstable
  // committed保存是写入持久化存储storage中的最高index，
    // 这里提交索引是集群的一个状态，而不是某一节点的状态，它是由leader统计出来的，并广播给所有的节点。
  committed uint64
  // 已经提交的日志要被使用者应用，applied就是该节点已经被应用的最大索引
  // 一条日志首先要提交成功（即committed），才能被applied到状态机中因此以下不等式一直成立：applied <= committed
  applied uint64
  logger Logger
}
type unstable struct {
  snapshot *pb.Snapshot // 保存还没有持久化的快照数据
  entries []pb.Entry    // 还未持久化的日志提交粒度的数据
  offset  uint64        // offset保存的为entries数组中的数据的起始index
  logger Logger
}

raftLog是节点上用来存储日志的结构，按照是否已持久化到稳定存储，可分为两部分：已持久化到稳定存储的部分（stable）和还未持久化到稳定存储的部分（unstable）

对于unstable，按照代码逻辑推断(并不是100%确定)：快照和entrise数据不会同时存在，快照只会在启动时进行快照数据恢复时存在，当应用层使用快照数据进行恢复之后，raft切换为可以接收日志数据的状态，后续的日志数据都会写到entrise数组中了，而两者的分界线就是offset变量。

一条提交的日志会首先写入到unstable中，因为unstable为非未持久化数据的缓冲区，因此这其中的数据可能会发生回滚（rollback）现象，具体实现为

func (u *unstable) truncateAndAppend(ents []pb.Entry) {
  // 先拿到这些数据的第一个索引
  after := ents[0].Index
  switch {
  case after == u.offset+uint64(len(u.entries)):
    // 如果正好是紧接着当前数据的，就直接append
    u.entries = append(u.entries, ents...)
  case after <= u.offset:
    // 如果比当前偏移量小，那用新的数据替换当前数据，需要同时更改offset和entries
    u.offset = after
    u.entries = ents
  default:
    // 到了这里，说明 u.offset < after < u.offset+uint64(len(u.entries))
    // 那么新的entries需要拼接而成
    u.entries = append([]pb.Entry{}, u.slice(u.offset, after)...)
    u.entries = append(u.entries, ents...)
  }
}

对于Storage，前文提到raft中有个基于内存的实现MemoryStorage，同时使用者可以在应用层自定义实现持久化存储。Storage的接口以及MemoryStorage的具体实现如下，MemoryStorage增加了蓝色部分的对数据的写操作实现，这些都会在上层应用层用到，而Raft库仅仅需要读操作即可。

Storage接口定义的是持久化存储，之所以etcd使用了基于内存的MemoryStorage，是因为etcd在写入MemoryStorage前，需要先写入预写日志（Write Ahead Log，WAL）或快照。而预写日志和快照是保存在稳定存储中的。这样，在每次重启时，etcd可以基于保存在稳定存储中的快照和预写日志恢复MemoryStorage的状态。也就是说，etcd的稳定存储是通过快照、预写日志、MemoryStorage三者共同实现的。

日志存储过程

a.首先，raft库会首先将日志数据写入未持久化数据缓冲区。

b.由于未持久化数据缓冲区中有新增的数据，会通过Ready结构体通知给应用层。

c.应用层收到Ready结构体之后，将其中的数据写入WAL持久化存储，然后更新这块数据到`已持久化数据缓冲区

d.持久化完毕后，应用层通过Advance接口通知Raft库这些数据已经持久化，于是raft库修改未持久化数据缓冲区将客户端刚提交的数据从这个缓冲区中删除。

e.持久化完毕之后，除了通知删除未持久化数据缓冲区，还讲数据通过网络同步给集群中其他节点。

对于存储结构raftLog、storage 和unstable等和相关的代码函数细节这里不再展开解析，感兴趣的可以通过最后给的地址去翻阅，整体上这块实现不算复杂。

日志复制进度跟踪

在etcd-raft中，tracker是raft代码目录下单独的一个包，核心实现就包括一个ProgressTracker。

了解核心类是ProgressTracker之前，需要先看其变量Progress，根据注释不难理解，Leader节点除了要维护未持久化缓冲区之外，还需要维护一个数据结构，用于保存集群中其他节点的进度，简称Progress，简单描述就是作为集群的leader，需要知道其他节点日志同步的具体情况。

其结构定义解释如下：

type Progress struct {
  // Next保存的是下一次leader发送append消息时传送过来的日志索引
  // 当选举出新的leader时，首先初始化Next为该leader最后一条日志+1
  // 如果向该节点append日志失败，则递减Next回退日志，一直回退到索引匹配为止

  // Match保存在该节点上保存的日志的最大索引，初始化为0
  // 正常情况下，Next = Match + 1
  // 以下情况下不是上面这种情况：
  // 1. 切换到Probe状态时，如果上一个状态是Snapshot状态，即正在接收快照，那么Next = max(pr.Match+1, pendingSnapshot+1)
  // 2. 当该follower不在Replicate状态时，说明不是正常的接收副本状态。
  //    此时当leader与follower同步leader上的日志时，可能出现覆盖的情况，即此时follower上面假设Match为3，但是索引为3的数据会被
  //    leader覆盖，此时Next指针可能会一直回溯到与leader上日志匹配的位置，再开始正常同步日志，此时也会出现Next != Match + 1的情况出现
  Match, Next uint64

  // 三种状态
  // ProgressStateProbe：探测状17
  // ProgressStateReplicate：副本状态
  // ProgressStateSnapshot：快照状态
  State ProgressStateType

    // 探测状态时才有用，表示探测消息是否已经发送了，如果发送了就不会再发了，避免不必要的IO。
  ProbeSent bool

  // 如果向该节点发送快照消息，PendingSnapshot用于保存快照消息的索引
  // 当PendingSnapshot不为0时，该节点也被标记为暂停状态。
  // raft只有在这个正在进行中的快照同步失败以后，才会重传快照消息
  PendingSnapshot uint64

  // 如果进程最近处于活跃状态则为 true（收到来自跟随者的任意消息都认为是活动状态）。在超时后会重置重置为false
  RecentActive bool

  // 用于实现滑动窗口，用来做流量控制，后边会展开单独作为一个额外福利介绍
  Inflights *Inflights
}

了解完Progress后会发现ProgressTracker就是Progress的一个管理器，其整体实现比较简单本文不再介绍。总结来说，Progress结构体做的工作：

1.维护follower节点的match、next索引，(0, Next)的日志已经发送给节点了，(0,Match]是节点的已经接收到的日志。

2.维护着follower节点当前的状态3中状态，不同的状态，其会采取不同的行为：

StateProbe：探测状态。当 follower因异常原因落后Leader节点数据过多，此时会拒绝了最近主同步的append消息，那么就标记该follower会进入Probe状态。leader 会试图继续往前追溯该 follower 的日志从哪里开始丢失的。在probe 状态时，leader 每次最多 append 一条日志，如果收到的回应中带有 RejectHint 信息，则回退 Next 索引，以便下次重试。在初始时，leader 会把所有 follower 的状态设为 probe，因为它并不知道各个 follower 的同步状态，所以需要慢慢试探
StateReplicate：副本状态。正常接收副本数据的状态，当处于该状态时，leader在发送副本消息之后，就修改该节点的next索引为发送消息的最大索引+1,此时Inflights值也会放大用于快速日志复制。
StateSnapshot：接收快照状态。当 leader 向某个 follower 发送 append 消息，试图让该 follower 状态跟上 leader 时，发现此时 leader上保存的索引数据已经对不上了，比如leader在index为10之前的数据都已经写入快照中了，但是该 follower 需要的是 10 之前的数据，此时就会切换到该状态下，发送快照给该 follower。当快照数据同步追上之后，并不是直接切换到 Replicate 状态，而是首先切换到 Probe 状态。

3.流量控制Inflights，避免follower节点超载

Inflights流控实现

Inflights主要用于StateReplicate状态下在日志复制时可以控制数据传输速度，具体大小用户可以在应用层指定。设计上非常的巧妙，其思想类似于“往池子注水和放水”的过程，通过给定池子的大小控制流速。而raft在实现上没有使用queue，而是在一个内存块上采用循环方式模拟queue的特性，这样效率会更高。

2.2. 选主模块

对于选举算法有很多实现，我之前开发中也实现过一个raft选举算法传送门，一般节点包含三种不同的角色candidate、follower、leader。每种角色对不同类型的日志数据需要有不同的处理，这里选主流程不展开，本节的目的主要在于发现etcd/raft中我理解与众不同的地方。

在etcd/raft的实现中，巧妙之处在于针对三种不同的角色，通过修改函数指针的方式在切换了不同角色时的处理，大概意思如下图所示：

也就是说在于其很好地剥离了各模块的职责。在etcd/raft的实现中，raft结构体是一个Raft状态机，其通过Step方法进行状态转移。只要涉及到Raft状态机的状态转移，最终都会通过Step方法完成。可能我也解释的不是很到位，具体可以看下代码实现：

//Step为节点收到应用层发来的消息，就会执行对应逻辑
func (r *raft) Step(m pb.Message) error {
    //...
    switch m.Type {
        case pb.MsgHup: //准备选举时触发
        //...
        case pb.MsgVote, pb.MsgPreVote: //在选举中触发
        //...
        default:
            r.step(r, m)
    }
}

Step 其实就是根据消息类型的不同（MsgHup/MsgVote/MsgPreVote）而去执行对应的逻辑（状态机）。而对于其他状态，此时则会执行 default 中的 step（函数指针，根据节点角色执行不同的函数stepLeader/stepFollower/stepCandidate）

对其他执行选择的流程，本文不再介绍。

2.3. 变更模块

etcd/raft采用将修改集群配置的命令放在日志条目中来处理，也就是一个配置变更其实是一次日志数据的提交，不过是一种特殊类型的日志这样做的好处是：

可以继续沿用原来的AppendEntries命令来同步日志数据，只要把修改集群的命令作为一种特殊的命令就可以了。
在这个过程中，可以继续处理客户端请求。

成员删减：操作作为日志的特殊类型，当可以进行commit的情况下，各个节点拿出该消息进行节点内部的成员删减操作。

leader转让：

旧leader在接收到转让leader消息之后，会做如下的判断：a. 如果新的leader上的日志，已经跟当前leader上的日志同步了，那么发送timeout消息。b. 否则继续发append消息到新的leader上，目的为了让其能够与旧leader日志同步。
当旧leader处于转让leader状态时，将停止接收新的prop消息，这样就避免出现在转让过程中新旧leader一直日志不能同步的情况。
当旧leader收到append消息应答时，如果当前处于leader转让状态，那么会判断新的leader日志是否已经与当前leader同步，如果是将发送timeout消息。
新的leader当收到timeout消息时，将使用context为campaignTransfer的选举消息发起新一轮选举，当context为该类型时，此时的选举是强制进行的。