学习分享｜Etcd/Raft 原理篇

575次阅读  |  发布于1年以前

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

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

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

前言

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

一、原理解析

1. 最小原则

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

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

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

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

2. 核心功能

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

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

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

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中状态，不同的状态，其会采取不同的行为：

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

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

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

leader转让：

二、总结思考

参考文档：

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8