Raft KV 与 Snapshot

使用 raft + 单机 KV 引擎构建分布式 KV 存储，是一种常见的方式。比如 TiKV, CockroachDB 等。本文重点讨论如何进行 raft snapshot。

Table of Contents

1 raft 与 snapshot

1.1 raft 基础

raft 共识算法网络上有众多优秀的文章。本文仅讲述主要概念。

图 - raft 复制状态机 [1]

上图是一组 raft 复制状态机。需要意识到的是，raft 只是一个共识算法。

我们想实现高可用的业务逻辑，称为状态机(state machine, FSM)。
状态机的每个操作，经过共识算法的处理，形成日志(Log)，持久化，并 apply 到业务状态机上。
外部调用者，称为客户端(Client)。
整个共识算法、持久化、状态机，统称为服务端(Server)。

1.2 raft kv 系统设计

根据 raft 的抽象，基于 raft + 单机 KV 引擎的系统可以如下设计。

图 - 基于 raft 的分布式 KV 存储

其中：

状态机：为单机存储引擎，如 LSM 类型 KV 数据库 RocksDB。
日志：每次 KV 读写的操作，如 Put, Del, Read。他们也可以是一组 batch 操作，一组 KV Put Del。
客户端：KV 调用者，读请求或者写请求。
服务端：包含整个状态机、raft 框架、日志系统。

Server 对外暴露的接口，可以如下

KV Get
KV Put
KV Del
KV Batch Get/Put/Del

1.3 raft snapshot

(注：这里指 raft 的快照，而不是 MVCC 数据库的快照)
为什么要做 snapshot？根据上述，自己业务状态机某个时刻的状态，本质上是根据从 0 开始的 log apply 建立出来的。那么我们从 0 重放这些 log，也能得到一模一样的状态机。

随着操作的增加，log 总不能无限增长。因此需要在某个时刻做状态机的 snapshot。一旦完成，无论是 leader 还是 follower 都可以用这个 snapshot + 后续的 log 重建状态机。

raft snapshot 完成了 log compaction。

1.4 raft 框架的 snapshot 接口

raft 框架不理解应用层状态机的具体含义，必须由用户去实现自己的 SnapshotLoader 和 SnapshotSaver。raft 框架会负责调用时机、数据流的持久化或者网络传输。

在 save snapshot 过程中，用户将自己的状态机序列化成数据流，由 raft 框架负责持久化，或者网络传输给其他 Follower。
在 load snapshot 过程中，用户将数据流转换回自己的状态机。

比如 baidu/braft [3]，要求用户实现以下 snapshot 接口，框架在需要时调用。

    // user defined snapshot generate function, this method will block on_apply.
    // user can make snapshot async when fsm can be cow(copy-on-write).
    virtual void on_snapshot_save(::braft::SnapshotWriter* writer,
                                  ::braft::Closure* done);

    // user defined snapshot load function
    virtual int on_snapshot_load(::braft::SnapshotReader* reader);

hashicorp/raft [4] 也要求用户实现类似的 snapshot 接口，定义如下。

type FSM interface {
    // Apply is called once a log entry is committed by a majority of the cluster.
    //
    // Apply should apply the log to the FSM. Apply must be deterministic and
    // produce the same result on all peers in the cluster.
    //
    // The returned value is returned to the client as the ApplyFuture.Response.
    Apply(*Log) interface{}

    // Snapshot returns an FSMSnapshot used to: support log compaction, to
    // restore the FSM to a previous state, or to bring out-of-date followers up
    // to a recent log index.
    //
    // The Snapshot implementation should return quickly, because Apply can not
    // be called while Snapshot is running. Generally this means Snapshot should
    // only capture a pointer to the state, and any expensive IO should happen
    // as part of FSMSnapshot.Persist.
    //
    // Apply and Snapshot are always called from the same thread, but Apply will
    // be called concurrently with FSMSnapshot.Persist. This means the FSM should
    // be implemented to allow for concurrent updates while a snapshot is happening.
    Snapshot() (FSMSnapshot, error)

    // Restore is used to restore an FSM from a snapshot. It is not called
    // concurrently with any other command. The FSM must discard all previous
    // state before restoring the snapshot.
    Restore(snapshot io.ReadCloser) error
}

1.5 raft snapshot 调用时机

save snapshot 的时机可以是

使用定时任务触发。
日志累计一定数目后触发。
无论是 follower 还是 leader，都需要 save snapshot，以压缩日志条目。

load snapshot 的时机一般有 2 个：

raft 节点启动时，需要将最近一次 snapshot 加载。
follower 节点与 leader 节点相差的日志过大，leader 已经做了对应日志的 compaction，不得不将完整的 snapshot 传给 follower。follower load snapshot 后，再 apply 后续的日志。

1.6 注意: raft FSM 调用的串行性质

在 braft 和 hashicorp/raft 中，框架调用用户状态机 FSM 的 apply, snapshot_save, snapshot_load，一定是串行的。这意味着

snapshot_save 很像一种 “中断”，函数返回必须要快，否则会阻塞后续的 apply 操作。
snapshot_save 中无论直接还是间接，不能有再次调用 FSM 的操作（比如期间执行一个 OP），否则会死锁。

正是这个性质引发了我们今天的讨论：究竟应该如何做 snapshot，才能达到性能和写硬盘的平衡？

2 方案 A: 锁定并全量 dump

适用于无法快速获取快照的内存状态机。流程如下

raft 框架调用 do snapshot
用户 lock 状态机，阻塞后续 client 调用
copy 一份内存状态副本
开异步线程，dump 内存状态副本到 raft 框架提供的 io writer。
不必等待异步线程结束，立刻 unlock 状态机，do snapshot 快速返回

适用场景：

内存状态量不大
本地数据库本来不支持 MVCC 快照读。

不适用：

用户无法接受内存 copy 时候的阻塞
内存量过大，容易 OOM

该方式是一个最朴素的方案。但如果数据只有数百 MiB，切延迟不敏感，完全可以接受。

3 方案 B: MVCC 引擎创建快照并异步迭代

按 raft 算法，日志一定是顺序 apply 的。但打快照过程不意味着完全阻塞后续日志的 apply。许多框架之所以顺序调用用户 FSM，是为了确保在进行快照时，所有已应用的日志条目都已经被处理。即快照的生成不应该影响日志条目的应用顺序。

因此，如果我们使用了支持 MVCC 快照读的本地存储数据库，就可以在 raft do snashot 时获取快照读的句柄，随即立刻返回，不阻塞后续日志的 apply。同时，使用这个句柄，将所有 KV 对 dump 进 do raft 框架的 data writer。

适用场景：

本地数据引擎天生支持 MVCC 读
dump 的 snapshot 天生是数据库的备份文件

缺点：

数据仍然会被 dump 到本地文件，产生写放大和空间放大
本质上，kv 数据分别写入了 raft log、raft snapshot、local kv database
当数据量达到一定程度后，空间放大和写放大不可接受

本方案是相当有效的一种方案，根据笔者调研，etcd 等系统采用了这种方式。用户可以很方便地使用备份文件迁移和重建系统。节点管理时，也会将完整的 snapshot 文件传输到对端。

4 方案 C: 存储引擎即快照

更进一步地，直接将 local kv database 作为 snapshot。消灭 raft snapshot 阶段的空间放大和写放大。

4.1 实现

考虑以下步骤

raft 框架通知我们，需要 raft snapshot。
我们仅记录很小的元数据（比如当前 apply id，正在进行 snapshot 等元数据信息）
snapshot 直接返回

虽然我们写了一个 “空” 的 snapshot 给 raft 框架，但是我们作为业务状态机，是了解 KV 数据切切实实存在我们的数据库的。反过来，当读取这个 “空” snapshot 时候，只能有 2 种情况

自身进程重启了，raft node 首次启动，load 自身的 snapshot

由于我们知道自己的 kv database 一定存储了比上次 snapshot 更“新” 的数据，因此 load snapshot 什么都不需要做，在当前 kv database 基础上继续 apply log 即可。

自身是 leader，follower 尝试加载 leader 的 snapshot

此时，我们重载 raft 框架读 snapshot 的操作，由方案 B 的读本地 snapshot 文件，改为全量快照读本地 kv database。这种操作对 follower 是透明的，它将全量 snapshot 存于本地，再 ingest 进自己的 kv database 即可。

图: kv database 即 snapshot

baidu 的 BaikalDB 数据面采用了这种方式 [5] [6] [7]。

4.2 重要前提：FSM log 必须是幂等的

方案 C 数据正确性的一个重要前提，是 KV FSM log 的设计必须是幂等的。考虑以下场景

leader raft snapshot @ log_id=10004
raft commit and apply log_id=10005~10006
另一个 follower 出现，因进度相差过大，开始加载 leader raft snapshot @ log_id=10004
新的写 kv 请求 commit 并 apply, log_id=10007
follower 加载了 snapshot@10004。但实际上，它加载的全量 kv 版本是 @10006，raft 框架却认为是 10004
follower raft 框架 再次 apply log @ log_id=10005~10007

对于一个 log，是至少一次被 apply 到状态机的。因此 log 的设计必须是幂等的。由于我们的 log 本身是 kv pair 的 put、del，所以数据是最终一致的。

4.3 优缺点

优点

减少了大量数据 snapshot 的写放大和空间放大，大大提高性能
设计巧妙，直接利用了 fsm log 的幂等性

缺点

实现的方式，需要仔细理解并推演
对于想全量 backup 的集群，还需要自行设计备份手段

5 小结

本文聚焦于 raft kv 的 snapshot 实现。简单描述 raft 原理后，探讨了几个著名 raft 框架给用户层的接口，以及 snapshot 实现的注意点。

分别列举了笔者调研过的几种 snapshot 实现方式，探讨了其优缺点。

笔者认为，对于一般的元数据系统，规模如能接受，使用方案 B 比较方便易懂。对于海量数据节点，需要减少 snapshot 的空间和写放大，可以考虑方案 C。

感谢一起研讨各类 snapshot 方案的同事 Charlie。

6 其他讨论

实现 raft kv 系统，还有一些有趣的事项可以探讨：

读 kv，需要经过 raft 共识吗？如何保证读一致性？
raft node 管理接口，先增加节点再传数据，还是先传数据再加入集群？
扩展到 multi raft，如何优化网络层和存储层？

参考

[1] Raft 论文 - https://raft.github.io/raft.pdf
[2] Raft 算法解析 - https://www.calvinneo.com/2019/03/12/raft-algorithm/
[3] C++ raft 框架 baidu/braft https://github.com/baidu/braft
[4] Go raft 框架 hashicorp/raft https://github.com/hashicorp/raft
[5] baidu/BaikalDB https://github.com/baidu/BaikalDB
[6] braft 快照的实现 https://luobuda.github.io/2022/02/15/braft-snapshot%E5%AE%9E%E7%8E%B0/
[7] BaikalDB基于raft和rocksdb的快照机制的实现原理 https://github.com/baidu/BaikalDB/issues/105