作为网易数帆开源的高性能、高可用、高可靠的新一代分布式存储系统，Curve 对于多副本数据同步、负载均衡、容灾恢复方面都有较高的要求。网易数帆存储团队选用 Raft 算法作为 Curve 底层一致性协议，并基于 Raft 的特性，实现了异常情况下的数据迁移和自动恢复。本文首先简要介绍一下 Raft 算法的一些基本概念和术语，再详细介绍其在 Curve 中的实践。
Raft 一致性算法介绍
Raft 算法中，有 Leader、Follower、Candidate 三种角色，它们之间的转换关系如下图：
在同一时刻，只能有一个 Leader，当选 Leader 后到发起下一次选举称为一个任期（term），Leader 负责通过心跳向 follower 保持统治，并同步数据给 Follower。Follower 发起选举的前提是超时未收到 Leader 的心跳。
Leader 竞选：RAFT 是一种 Majority 的协议，即赢得选举的条件是获得包括自己以内的大多数节点的投票。Follower 超时未收到 Leader 的心跳，则会成为 Candidate，发起新一轮的选举。每个节点在每个 Term 内只能投一次票，且服从先到先服务原则。为了避免多个 Follower 同时超时，raft 中的选举超时时间是一个固定时间加一个随机时间。
日志复制：在任期内，Leader 接收来自 client 的请求，并将其封装成一个日志条目（Raft Log Entry）把它 append 到自己的 raft log 中，然后并行地向其它服务器发起 AppendEntries RPC，当确定该 entry 被大多数节点成功复制后（这个过程叫 commit），就可以执行命令（这一步叫 apply），并返回给 client 结果。log entry 由三个部分组成，分别是：1、log index，2、log 所属的 term，3、要执行的命令。
配置变更：在 Raft 中，称复制组有哪些成员称为配置，配置并不是固定的，会根据需求增删节点或异常情况下需要替换掉有问题的节点。从一个配置直接切换到另一个配置是不安全的，因为不同的服务器会在不同的时间点进行切换。因此 Raft 配置变更时，会先创建一个特殊的 log entry Cold,new，这条 entry 被 commit 后，会进入共同一致阶段，即新旧配置一起做决定。这时候，再生成一个 Cnew 的 log entry，等这条 entry 被 commit 后，就可以由新配置独立做决定了。
安装快照：Raft 快照指的是某个时刻保存下来的系统状态的集合。快照有两方面的作用：一个是日志压缩，打了快照之后，在此时刻之前的 log entry 就可以删除了。另一个是启动加速，系统起来的时候不需要重新回放所有日志。当 Leader 同步日志给 Follower 的时候，发现所需的 log entry 已经被快照删掉了，即可通过发送 InstallSnapshot RPC 给 Follower 进行同步。
Raft 算法在 Curve 中的应用
Curve 系统是一个分布式存储系统，在 Curve 系统中，数据分片的最小单位称之为 Chunk，默认的 Chunk 大小是 16MB。在大规模的存储容量下，会产生大量的 Chunk，如此众多的 Chunk，会对元数据的存储、管理产生一定压力。因此引入 CopySet 的概念。CopySet 可以理解为一组 ChunkServer 的集合，一个 Copyset 管理多个 Chunk，多副本间的同步和管理已 Copyset 为单位组织。ChunkServer，Copyset 和 Chunk 三者之间的关系如下图：
Curve copyset 选用了 braft 作为一致性协议的组件，使用方式为 multi-raft，即同一个机器，可以属于多个复制组，反过来说，一个机器上，可以存在多个 raft 实例。基于 braft，我们实现了副本间数据同步，系统调度，轻量级 raft 快照等功能，下面一一详细介绍。
副本间数据同步
CopysetNode 在 ChunkServer 端封装了 braft node，具体关系如下图所示：
Curve client 发送一个写请求时，三副本情况下的具体的步骤如下：
Client 发送写请求给 Leader ChunkServer。
ChunkServer 收到请求，将请求封装成一个 log entry，提交给 raft。
braft 模块在本地持久化 entry 的同时发送 entry 给其他副本（ChunkServer）。
本地持久化 entry 成功，且另一个副本也落盘成功则 commit。
commit 后执行 apply，apply 即执行我们的写盘操作。
在此过程中，用户的数据和操作，通过 braft 中的 log entry 的方式在副本间传递，进行数据同步。在三副本场景下，向上层返回的时间取决于两个较快的副本的速度，因此可以减少慢盘的影响。对于较慢的那个副本，leader 也会通过无限重试的方式同步数据，因此在系统正常工作的前提下，最终三个副本的数据是一致的。
基于 Raft 的系统调度
在 Curve 中，ChunkServer 定期向元数据节点 MDS 上报心跳，心跳中除了 ChunkServer 自身的一些统计信息，还包含 ChunkServer 上面的 CopySet 的统计信息，包含它的 leader，复制组成员，是否有配置变更执行中，配置的 epoch 等。MDS 基于这些统计信息，会生成一系列的 Raft 配置变更请求并下发给 Copyset 的 leader 所在的 ChunkServer。
下发配置变更
Curve ChunkServer 会定期向 MDS 上报心跳。MDS 调度下发配置变更是在心跳的 response 中完成的。上报心跳的过程如下图：
心跳是定时任务触发的，ChunkServer 除了上报一些自己的容量信息等统计信息外，还会上报 Copyset 的一些信息，比如 leader，成员，epoch，是否有进行中的配置变更等。
MDS 在心跳 response 中下发配置变更的过程如下图：
ChunkServer 收到 response 后，解析其中的配置变更信息，并下发给每个 Copyset。
Curve epoch
epoch 同步配置。MDS 生成的调度信息，是由后台定时任务触发，并在 ChunkServer 下一次请求到来时在 response 中下发的，因此 MDS 下发的配置变更有可能是过期的。为了实现 MDS 和 ChunkServer 之间的配置同步，Curve 引入了 epoch 机制，初始状态，epoch 初始为 0，每进行一次配置变更（包括 leader 变更），epoch 都会加一。当 MDS 中的 epoch 等于 ChunkServer 端的 epoch 时，即将下发的配置变更才被认为是有效的。epoch 与 term 有何区别？term 用于表示 Leader 的任期，即只跟选举有关，而 epoch 是与配置变更相关的，也包括了 Leader 选举这种情况。
epoch 的更新。epoch 是在 ChunkServer 端更新的，braft 在实现上提供了一个用户状态机，在 braft 内部发生变化，比如 apply，出错，关闭，打快照，加载快照，leader 变更，配置变更等时会调用用户状态机中对应的函数。Curve copyset 通过继承的方式实现这个用户状态机来完成与 braft 的交互，epoch 是在 on_configuration_committed 函数中加一的。在 braft 中，当 Leader 变更的时候会把当前的配置再提交一遍，因此在 on_configuration_committed 中增加 epoch 即可保证在配置发生变化或者 Leader 变更时 epoch 顺序递增。
epoch 的持久化。在 MDS 端，epoch 随着 CopySet 的其他信息一起持久化在 etcd 中。ChunkServer 也对 epoch 进行了持久化，但是 ChunkServer 中持久化 epoch 并不是每次 epoch 发生变化都需要持久化的。这是利用了 raft 的日志回放和快照功能。考虑以下两种情况：
假设 raft 没有打快照，那么就不需要持久化 epoch，因为所有操作日志，包括配置变更的 entry 都已持久化，当服务重启的时候，回放这些日志的时候会依次再调用一遍 on_configuration_committed，最后 epoch 会恢复到重启前的值。
当 raft 有快照时，打快照前的 entry 都会被删除，就不能通过上面的方式回放，因此必须要持久化。但我们只需要在打 raft 快照时持久化 epoch 的当前值即可。这样当系统重启的时候，会先安装 raft 快照，安装后 epoch 恢复到快照时的值，再通过执行后面的 log entry，最终 epoch 恢复到重启前的值。在打快照时更新 epoch 是在 on_snapshot_save 函数中完成的。
Raft 轻量级快照
上面介绍 Raft 算法的时候介绍过，Raft 需要定时打快照，以清理老的 log entry，否则 Raft 日志会无限增长下去。打快照的时候需要保存系统当前的状态，对于 Curve 块存储场景来说，系统状态就是 Chunk 当前的数据。直观的方案是将打快照时刻的全部 chunk 拷贝一遍备份起来。但是这样有两个问题：
空间上要多出一倍，空间浪费非常严重。
Curve 默认打快照的间隔是 30 分钟一次，这种方案下会有频繁的数据拷贝，对磁盘造成很大的压力，影响正常的 IO。
因此，Curve 中使用的 Raft 快照是轻量级的，即打快照的时候只保存当前的 Chunk 文件的列表，不对 Chunk 本身做备份。具体流程如下：
这样操作，Follower 下载到的 chunk 文件不是打快照时的状态，而是最新的状态，在回放日志的时候，会把这些新数据再写一遍。但这对于我们的场景是可以接受的，因为底层都是覆盖写是幂等的，即写一次和写多次结果是一致的。
小结
本篇文章首先介绍了 Raft 一致性算法的一些基本概念。随后介绍了 Raft 算法新一代高性能分布式存储系统 Curve 中的应用，分别从数据同步、系统调度和 Raft 快照三个角度介绍了 Curve 中使用 Raft 的细节。关于 Curve 的更多介绍详见我们的代码仓库。另外，Curve 开源分享也在火热进行中，分享的 PPT 可以在仓库中获取。
作者简介
查日苏，网易数帆存储团队高级 C++开发工程师，高性能分布式存储系统 Curve 核心开发。
