TinyKV 复盘

架构、Raft vs. Paxos、Multi-Raft

April 7, 2026

前言 #

准备简历，随意发散

一 | 架构 #

我的关注重点在 Storage 这个 KV 中间层上，既然引入了分布式，那么就不能以单机视角来看待整个系统，必须把网络通信考虑在内

解释 #

Server 层接收外界指令，通过事务机制进行并发控制、语义编排，向 Storage 发送 Message，通过 router、worker 并发调度

共识存在延迟，Server 用 Callback 来实现异步 IO

Raft Storage 是对 Storage 接口的实现，对外表现为一个具有延迟的 KV 服务

Raft Storage 管理多个 raft node 的上下文信息，并通过 router 转发 message，用 worker 分离执行级别

而 RawNode 对外表现为 Raft 节点，用 HasReady() 通知共识结果，只负责实现共识流程，而不与本地的状态机交互

Storage 层收到 Ready 数据后，将其应用到本地状态机，具体表现为写入 db，转发 msg，修改 region 状态

Client 对应 SQL 层，Database 对应存储层

消费与被消费 #

从消费角度看，可以明确各个模块交互的边界

server 消费 Command，生产 Message
worker 消费 Message，生产 Proposal 与 raft 行为
raft node 消费 Proposal，生产 Ready
applier 消费 Ready，生产 “状态转移“ 与 callback
server 消费 callback，生产 success 信号

整个系统表现为，消费 command，生产状态转移与 success 信号

其中存在两层异步，分别是 server 等待 callback 和 worker 等待 apply

前者用 callback 实现，后者用 proposal 寄存表实现

如何融入 Snapshot？ #

leader 发现 follower 落后过多时，会选择直接发送 snapshot

流程：

raft node 向 storage 发起异步 snapshot 请求，不断询问
storage 准备好快照，允许 raft node 发送
raft node 将 snapshot 元信息放入 msg，加入 sendMsg 队列
rawnode 发现有新 msg 需要发送，生成 Ready
handler 将其 msg 转发到 transport，再转发到目标节点
follower 收到 snapshot 后，将其安装到本地

snapshot 和其他普通的 msg 都会走 transport 路线，但 snapshot 是一个大文件，不能用单条信息传输

两点特殊：生成与发送

前者，我们用异步请求生成 snapshot，准备好才允许发送 msg

后者，我们在 transport 截流，特殊处理 snapshot msg，用专门的 snap worker 传输

另外，SnapshotMsg 只包含 metadata，真正处理 SST File 的逻辑都封装在 snap worker 里，通过 Snapshot gRPC 流传输

体现在示意图里，我们只需要增加一个 snap worker，从 transport 截流，接收 rawnode 的 snapshot 请求

这里提到的词是 ”异步“和”截流“，对应着大文件传输的处理技巧

发送方，通过 stream 发送 sst 文件，并用 gRPC 远程调用接收方的 Snapshot() 触发器

另外，普通 msg 也是走 stream RPC 调用，但直接通过 router 转发

接收方，触发 Snapshot() 后，将任务分配给 worker，组装好 snapshot 文件后，再将 msg 传入 router 通知 Raft 层进行 Install

用 while 循环的状态机就能实现 sst 的收发逻辑

二 | Raft #

流程 #

Candidate 选主，随机 election timeout
Leader 复制日志，覆盖 follower 上的记录
提交、应用日志，推进 index

term 由 leader 作为 TSO 分发，是单调的

还需要引入容错，防止 crush、restart 产生的不一致

原论文的两条限制：

Vote 限制：不能投票给 log 状态（term、index）早于自己的 candidate
Commit 限制：重启后，不可以提交之前 term 里 uncommitted 的日志

讲一下 vote 限制

[L1, F2,F3] [F4,F5] 其中 1 2 3 已经提交 log 3，并推进 commitIndex，而 4 5 仍停留在 log 2

此时 L1 宕机，选举 4 为新 leader L4 开始复制日志，覆盖掉 2 3 上的 log 3

然而 log 3 已经被 commit

这里 Commit 的问题，只要还没有 Apply，是可以通过回退 commitIndex 来弥补的，但是这样增加了不必要的复杂度

Raft 不允许这种情况，才引入 Vote 限制

讲一下 Commit 限制

原论文中的 Figure8

[T2] L1 写入 log2，将 log2 复制到 F2，宕机
[T3] L4 当选为 leader
[T3] L4 写入 log3，宕机（没有 log2）
[T4] L1 重新当选为 leader，将旧的 log2 复制到 F3
[T4] L1 推进 commitIndex，宕机
[T5] L4 再次当选，将 log3 复制到集群，覆盖了 Follower 上的 log2

这里 Log2 已经完成 commit，但被覆盖了

L4 当选的原因是，log3 的 term 为 T3，大于 log2 的 T2

同理 log3 也可以覆盖掉 log2

这里点出了关键因素：时间

从 T4 的 L1 看来，提交 T2 的 log 是有风险的：

T3 可能有其他 leader 存入 log
如果宕机，T3 log 可以覆盖掉我们提交的 T2 log

从 T2 的 L1 看来，提交 T2 的 log 是可以的：

不存在 Term 更大的 log
如果宕机，Vote 限制会阻止没有收到 T2 log 的人成为 leader
因此提交不会被覆盖

所以对 T4 的 L1 而言，解决方案是提交一个 T4 的 no-op，这样就安全了：

T4 log 被提交，不存在 Term 更大的 log
如果宕机，Vote 限制会阻止没有收到 T2 和 T4 log 的人成为 leader
因此提交不会被覆盖

…… 为什么？

说不清的感觉，先找出“问题是什么”

上面对于共识状态的判别是很暧昧的，为什么一旦 commit 就不能覆盖？

为什么要以 commit 作为判别标准呢？

commit 和 apply 是异步的，Raft 层不能掌握 apply 的时机，因此采用更严格的标准，将 commit 作为共识节点

只要达成 commit，Raft 的工作就结束了

上层 server 会在 apply 之前阻塞（等待 callback），因此不受 commit 与 apply 延迟的影响

以上的限制都是在维护 ”换主“ 问题，我们到底在保证什么？

我认为是在维护 ”共识状态“ 的单调性

leader 本身并不代表整个集群的共识结果，一条 uncommitted 的日志也可能因为宕机被覆盖

结合上一个问题，commitIndex 才是我们事实上的共识对象

我们保证的事实：

Vote 限制，即使宕机， leader 一定拥有全部 committed 日志（多数投票）
Commit 限制，推进 commitIndex 时 Term 一定是集群中最大的（no-op），从而保证 Vote 限制

所以二者都是在保证 vote 限制，也就是 commit 日志不丢失

因此在 ”换主“ 问题上，我们就是在维护 commit 序列的单调性，从而保证整个集群的 ”共识状态“ 也单调

围绕这一点，我们划分了明确的标准，也就降低了实现的复杂度

与 Paxos 的比较 #

Raft 之所以更容易理解，就是因为它引入了“单调性”，更符合直觉

日志流向是单调的，只允许从 leader 流向 follower
共识状态是单调的，两个限制保证 commit信息单调
选举是单调的，Term、VoteFor 都是不可逆增长
日志序列是单调的，追加写入，单调增长

而 Paxos 只需提一点：

proposer 可以从 acceptor 学习到共识 value

信息是双向流动的，这就破坏了直觉

共识算法，最重要的就是 ”共识状态“ 在哪里

Raft 里，Leader 管理着单调的”共识状态“

而 Paxos 不是这样，leader 甚至需要从集群中“学习共识“

Paxos 的“共识状态”在哪里呢？在 Quorum 里（过半集群）

这就引出另一个区别，Commit 时机：

Paxos 在 value 到达 Quorum 的最后一个节点时，完成事实 commit
此后新的 proposer 可以学习到该 value
Raft 将 commit 时机延后了，在 Quorum 都向 leader 确认收到后，leader 推进 commitIndex 时，完成事实 commit
此前只要没有推进 commitIndex，这些 Quorum 上的 log 就可以被覆盖

相比之下，Raft 更容易观测 Commit 进度，而 Paxos 的 Commit 进度则是隐藏在集群里

我们对比一下单个 value 的共识过程

Raft 写入：

leader 写入一条 log，向 follower 传播
leader 确认该 log 被 quorum 接收，推进 commitIndex

Paxos 写入：

proposer 向 acceptor 发起 prepare 请求
acceptor 承诺为 proposal 预留位置
proposer 确认 quorum 完成 prepare
proposer 发起一次 proposal
quorum 接收 proposal，完成事实共识

Raft 学习：

其他 follower 从 leader 学习 log
新重启的 leader 不需要学习，已经保证 commit 单调性

Paxos 学习：

learner 从 quorum 学习 value
其他 acceptor 从 proposal 学习
新重启的 proposer 启动 prepare 阶段，从 quorum 学习

可以发现，Paxos 存在“写入失败”的情况

当 proposal 发现当前已经达成共识，它就必须放弃自己原本打算提议的值了，还要帮助这个“共识值”继续传播，尽管它对这个值的来源一无所知

那么原本打算写入的 value，怎么办呢？这引出又一个区别，数据模型的不同

Raft 的共识单位是逻辑 index，与一个 log 对应

而 Multi-Paxos 的共识单位是物理 slot，一个槽位的来源是多样的，只需最后确定 value 共识即可，如果对一个 slot 的写入失败了，那么就换一个 slot 写

因此 Paxos 对 slot 是乱序写入，也引入了更多的复杂度

Multi-Paxos 是一种思想，其实现有许多变种，这里不再展开

关于 multi-paxos 参考使用multi-paxos实现日志同步应用

Raft 是 Paxos 的变种吗？

工程上，二者越来越接近，可是从动机上，二者是不同的

Paxos 是去中心化的，只关心一轮共识，它是自底向上，从 basic paxos 生长出来的

而 Raft 天生就是要解决应用层的问题，针对状态机上的连续 log 设置 leader 角色，是自顶向下展开设计的

Paxos 的优点，在于节点与共识集群的交互，无论如何都是自洽的，难点在于工程实现上，而 raft 则相反

常见的优化手段 #

分区情况下，candidate 会不断错误地发起选举，term 会一直增加，还会干扰原有 leader 的正常允许

针对这一点，提出 PreVote 优化：

candidate 发起选举前，会先发起一轮 preVote RPC，确认能收到 quorum 的 ack 信号，之后才增加 term 正常选举
缺点是增加了一轮 RPC

读操作也需要通过 leader propose 到集群，达成共识，然而读操作不修改状态机，这样也导致读效率底下

为什么效率低？因为达成共识的 read 请求，apply 到了多个副本上，而我们事实上只需要一次 apply 来读出数据

因此我们省略 read log 的实体，转而用 readIndex 来指代这条 log

流程：

收到读操作时，leader 主动发起一次心跳，同步日志
当 commitIndex 推进到 readIndex 时，我们知道现在可以读 leader 了

这就是 readIndex 优化

假如仍同步 read log（index = 3 write + 1 read）：

读日志会被发送到 follower 上
leader 推进 commitIndex = 4
follower 推进 applyIndex = 4
leader 也推进 applyIndex = 4，读出数据
apply 读日志前后，状态机无变化

使用 ReadIndex（index = 3 write）：

不会生成读日志
leader 记录 ReadIndex = 3
leader 发起心跳，推进 commitIndex = 3
leader 推进 ApplyIndex = 3
leader 检查到 ReadIndex = ApplyIndex，读出数据
没有产生读日志，状态机无变化

读操作不改变状态机，因此只在 leader，而不在 follower 上执行是可以的

readIndex 可以用到 follower 读上，因为状态机是一致的，但需要保证 applyIndex 与 readIndex 严格对齐

前面提到过，leader 的 commitIndex 是单调的，readIndex 对应的状态机也是唯一的

但 ReadIndex 还是需要一轮心跳共识来确认自己是最新的 leader，否则有可能出现过期读（其他 leader 已经修改了状态机）

如果当前 ApplyIndex 已经是最新的，那么直接读就好了，如何省略这轮“确认身份”的心跳呢？

采用租约机制，Lease Read 方案：

每次完成一轮心跳，我们就更新 lease 期限
在 lease 结束前，我们可以认为自己就是最新的 leader
收到心跳后， follower 至少要经过一个 electionTimeout 才会选出新 leader，在此之前，leader 不会改变
因此用 electionTimeout 作为 lease 延长时间

另外，lease 还需要考虑时钟偏移的影响

假如，leader 收不到 follower 的 ack，但 follower 可以正常接收信息
此时 leader 无法推进 commitIndex，follower 也不会发起选举，服务不可用

从 leader 端增加超时检测，如果收不到 follower 的 ack 就认为断联

当发现 quorum 断联时，leader 认为自己不能提供服务，让出位置，触发集群选举

简单记一下 log 的优化：

网络 batching，IO batching
pipeline，log 流水线同步，用 cache 组装乱序到达的 log
并行，leader 一边 append log 一边发送给 follower（网络与 IO 并行）
异步 apply

成员变更 #

reference: TiDB 在 Raft 成员变更上踩的坑

confchange 作为一条 log 在集群内完成共识

引入的问题是，quorum 的定义变得不稳定了

如果一次引入多个节点，很可能同时形成两个不重合的 quorum，造成不一致

而采用单步成员变更，就没有这个顾虑，因为新旧集群的两个 quorum 一定重合（可以证明）

然后用串行单步，就可以达成多个变更的效果

但是单步变更也有缺点

如果是偶数个节点，就会产生 [ab|cd] 的情况，此时两边都不存在 quorum，无法选举出 leader

这里的问题是 quorum 不等于 majority

quorum 是一个集合，其中的元素两两必有交集，我们令 Q(abcd) = M(abcd) + {bc} 就能解决上述问题

Raft 给的约束 Majority 其实是最大 quorum 的一个子集，因此这是一个 raft 设计本身的问题

单步变更会引入一个新的空节点，这破坏了 vote 限制，造成不一致

两点：

空节点，可以给落后的 candidate 投票
quorum 定义不稳定

[ab|cd] ADD[u] ADD[v] 中，[cd v] 可能已经对 ADD v 完成 commit a 重启后选择继续 commit 之前的 ADD u，并不知道 ADD v 存在但 ab 视角下，cd 不构成 quorum
因此可能对 [ab u] 达成共识，重复 commit

针对这一点，一条 no-op 就可以解决，d 会先同步一条 no-op 在 [abcd] 中，保证 vote 限制，再执行 ADD v

之前的 commit 限制自动解决了这个问题

Joint 变更一次引入多个节点，它采用了一个过渡态保证 quorum 定义稳定

以 [abc] -> [cde] 为例，分两阶段：

先达成 [abc] or [cde] 新旧并存的共识
commit 后，再发起新一轮共识，过渡到 [cde]

quorum 的变化：1# Q(abc) --> 2# Q(abc) && Q(cde) --> 3# Q(cde)

脑裂问题，其实就是分别在 Q(abc) 和 Q(cde) 中产生了两个不相交的 quorum，进而导致两个 leader

我们引入 #2 阶段，这样就强制相邻两个阶段的 quorum 相交了

进入 #3 阶段，由于 commit 单调性，仍处在 #1 的节点不可能成为 leader（因为 #2 已经完成 commit）

如果 #2 commit 之前，选出了 #1 的节点作为 leader，那么它会覆盖掉我们写入的 uncommit 的 confchange 日志，这次变更也就失败了

而 #3 完成 commit 后，单调性也会导致 #2 节点无法成为 leader，这样新 leader 只会在新集群中产生，可以正常服务

关于 joint 变更的优化

新的空节点，需要长时间同步 log，在完成 confchange 之前，我们可以先让其作为 learner 提前追赶集群

完成 #2 的 commit 时，leader 可能并不在 [cde] 里，而是应该被删除的节点，此时 leader 的 quorum 里不包括它自己

这让我反思自己的 election 实现，如果简单统计个数按 majority 实现，可能就会忽略这种情况，产生 bug

按照 quorum 集合的定义，用函数实现，会更健壮，扩展性也更好

针对旧节点，当它停留在 #1 时，可能收不到移除自己的指令

此时它会不断发起选举，增加 term，干扰新集群的 election

用 PreVote 方案可以解决

也可以在 follower 端加上 lease 机制，租约期限内认为 leader 仍存活，从而拒绝投票

关于 confchange 的 apply 时机

如果 conf 指令需要等到 commitIndex 推进后再 apply 的话，成本很高，因为 leader 需要等待所有人的 apply ack 后才能执行下一步

普通指令不需要 apply ack，而 conf 指令存在依赖关系，这样就多一轮 RPC

我们不希望这样，能不能收到 conf 时立刻 apply 而不等待 commit 呢？这样就不需要 apply ack 了

这样是可以的

如果 commit 成功，那么正常运行
如果 commit 失败，那么新 leader 会覆盖掉这条 log，同时我们会 apply 正确的 conf 信息

leader 移除自己时是特例，此时要么延迟到 commit 再 apply，要么直接 transfer leader 让出领导权

三 | Multi-Raft #

Split #

reference : TiKV 源码解析系列文章（二十）Region Split 源码解析

如果只有一个 region，那么会出现热点问题

假如分成 region A 和 B，那么就可以把 A 的 leader 转移到另一台机器上，分摊服务压力

因此 multi-raft 是对 ”服务粒度“ 做了划分，split 只是在逻辑上分裂出不同的 region，细化管理权限，而不需要真正对底层数据做分片

不同的 region 共用一个 raftstore 逻辑，通过 router 路由 msg

我们引入第三方 PD 负责资源调度，这样各个节点就有可靠的信息源

raftstore 就只需要负责实现 apply split 的部分，“何时触发 split” 交给 scheduler 考虑

即便是本地感知到需要 split ，也需要先发信息给 scheduler，再由 scheduler 发起 split 命令

split 和其他 raft 命令一样，需要通过 propose-commit-apply 流程才能应用

与 confchange 不同，split 并不影响 quorum 的定义

apply split 做的事情：

更新 region epoch（version, conf_ver）
修改旧 region 的元信息
初始化新 region 的元信息，使得可以读写状态机
将新 raft 节点注册到 router（log 为空，index 初始化为 5 与重启节点区分）

这里旧 region 继承了所有的旧 log，conf 成员不变

因此旧 region 的 leader 负责将 split 指令同步到落后的 follower 上

在此之前，即使新 region 的 leader 向 follower 发起同步，router 也会因为找不到新 region 而丢弃信息（因为落后节点还没有 apply split 指令）

以上讨论了跨 version 的同步问题，跨 conf_ver 的处理之前也已经说过

这里 split 时，只修改了 region 的 version，没有对 raft peer 做调整，因此 router 是可以收到旧 region 的信息的

注意，新 region 在初始化 raft peer 之后，是无法提供服务的（没有选出 leader），也就没法通知 PD 产生了新 region

而旧 region 已经在 PD 中完成注册，这导致 PD 会有一段无法服务的真空区间

这是不可避免的，因为 quorum 执行 apply 需要时间，在新 region 出现可工作的 quorum 之前，无法选出 leader

另外 split 会影响 lease read，我们选择让 leader 在收到 split log 之后不再续约 lease，直到完成 apply split

Merge #

Merge 分三阶段，假设 A 吞并 B：

PD 将两个 region A 和 B 的 range 和 peers 都对齐，触发 Merge
我们先在 B 上同步一条 PrepareMerge 信息，让 B leader 停止服务，但还会继续同步 log（需要保证所有 uncommited 的日志都不影响 epoch 服务）
随后在 A 上同步一条 CommitMerge 信息，将 region 合并到 A，并且将 B 的旧服务路由到 A

这里的细节：

Prepare 阶段，B 会锁住，并定期检查 A 是否有变化（PD 可能会调度 A），如果 A 与 PrepareMerge 开始时的状态不一致了，就 rollback merge
Prepare 完成时，如何通知 A 开始 Commit 呢？
这里我们让 B 中的本地 peer 定期向 A 发 Commit，如果 A peer 不是 leader 就丢弃
这样避免走网络通信，简化实现
A 完成 log 同步时，应用 CommitMerge，合并 region range，并将 B 标记为已删除，完成合并

merge 太难，不展开讲了

讨论一下 Multi-raft 和单 raft 相比，引入了哪些复杂交互

一般 raft 保证一定只有一个 leader，也就是 ”服务入口“ 是唯一的

而 Multi 引入多 region，服务入口开始不一致，这导致 client 需要通过 PD 重新路由，region 需要随时通知 PD

PD 与 RaftStore 的交互存在延迟，这就引入网络问题，请求 split 到确认发起 split 之间，raftstore 可能就插入了一条 confChange log

此时，我们需要在 Apply 上动手，既然这些 log 会修改 Epoch，那么我们就加一层 Epoch 判断即可，这样就可以过滤掉类似的“过期”指令

从 Apply 层进行过滤，就自动保证了这些 cmd 不会在同一个 Epoch 上产生分歧

那么 Apply 层挡不住哪些操作呢？

首先是跳过 Apply 的 Snapshot，Follower 可能只修改了 db，而没有修改 region 元数据，这就需要 snapshot 携带 Epoch 等信息

或者我们可以截断 Snapshot，重启一次，这次 Snapshot 带有最新的信息

还有 lease read，与租约的交互需要重新考虑

事务层 #

reference : TiKV 事务模型概览，Google Spanner 开源实现

跨 region 的事务，用 Percolator + MVCC 来管理

相比于 2PC，Percolator 不需要中心管理器，只需要一个分配时间戳的 TSO

Percolator 流程：

Prepare，选一个 key 作为 primary key，然后给各个 key 上加锁，并记录一个指向 primary key 的指针
Commit，提交 primary key 即可，并删除 lock，事务结束
其他 key 的 commit 是异步的，通过检查 primary key 来执行

如果 primary 提交失败了，就回滚

其他 key 在读时，如果发现有锁，就去查 primary key 的状态

如果 primary 还有锁，说明事务还没提交
如果没有锁，并且 primary 写成功了，说明 commit 成功，直接提交 prepare 里的内容
如果没锁，primary写失败，说明 rollback了，同样 rollback

如果是 2PC，其他人只能被动等待 manager 的 commit 信号

这里可以主动去查询 primary key，得知事务状态

相比之下， Percolator 只需要一轮对 primary key 的 commit，相比之下 2PC 需要对每个 key 都来一轮

总结 #

本文以 TiKV 为参考，梳理了 Raft 相关的知识

理解上层的协作后，对 lab 实现的恐惧也消失了，之前做的还是有偷懒的地方