Raft算法 | newrain-zh博客

type

status

date

slug

summary

一、基本概念介绍

1.基本属性

1.1 状态

Raft中每个节点的状态分为三种 Follower、Candidate、Leader。同一时间每个节点只会是一种状态。

Leader

负责接受客户端的命令，进行读写操作
发送心跳和日志（AE RPC）

Follower

做为副本存在，接受 Leader 节点发送的日志。

Candidate

发起选举，向其他节点发送投票 RPC，如果获得超过过半节点的选票则成为 Leader。

1.2 任期

任期（Term）是一个核心机制，其本质是一个逻辑时钟，用于表示系统的演进阶段，协调各个节点行为并确保一致性。

任期是自增的，初始化为 0，单调递增。每个节点都使用 currentTerm 来保存当前节点的任期数。

任期的自增趋势和任期数，可以看出系统的是否存在问题。

如果一开始任期为 1，运行了很长时间说明，还是为 1，说明系统、网络状态都是非常稳定。当然这里的情况比较理想化了。

如果短期内任期疯狂自增，则说明系统可能出现了一直在选举、或是网络出现异常等状况

1.3 日志

Log是 Leader 操作排序的一种手段，对于复制状态机来说所有副本不仅要执行相同的操作，还需要相同的顺序执行这些操作。而 Log与其他很多事务，共同构成了 Leader 对接收到的客户端操作分配顺序的机制。日志是需要持久化存储的。

1.4 其他属性

voteFor 投票给谁

commitIndex 当前节点提交的日志索引

lastApplied 当前节点最后应用到状态机的日志索引

nextIndex [] 其他节点下一个待发送的日志索引

matchIndex [] 其他节点已经复制的日志索引

lastIncludedIndex 快照中包含的最后日志的索引

lastIncludedTerm 快照中包含的最后日志的任期数

snapshot [] 快照

二、“过半“特性

在 Raft中，选举和提交日志都要满足过半节点同意才能执行操作，这也是共识算法能够避免脑裂问题的核心手段。

什么是过半

过半的意思是超过一半的节点同意一个决策。如果一个集群有 N 个节点，那么过半就是至少需要 [N/2+1]个节点同意，才能达成共识。例如 5 个节点，则至少需要 3 个节点同意某个操作或日志条目。

过半的基准

过半还有一个需要注意的点是，是所有服务器的节点的数量一半，而不是开机(在线)的服务器的一半。

「所有服务器数量的一半」 vs. 「当前开机服务器数量的一半」

所有服务器数量

指整个系统中注册的服务器总数，无论它们当前是否在线。

例如：系统共有 5 台服务器，无论实际有几台开机，总数为 5。

过半要求：需满足 ⌈总服务器数/2⌉ + 1。

例如：5 台服务器时，过半是 3 台（即严格超过半数）。

当前开机服务器数量

仅指当前在线的服务器数量，可能动态变化（如故障、维护时减少）。

过半要求：若当前 3 台在线，过半是 2 台（即超过 1.5）。

为什么以所有服务器的节点为基准？

防止脑裂

如果以“当前在线服务器数量”计算，当网络分区（如部分服务器失联）时，多个分区可能同时达到自己的“过半”，导致数据不一致。

例如：总共有 5 台服务器，若 3 台在线形成一个分区，2 台离线形成另一个分区。若允许在线分区的 2/3 达成共识，而离线分区可能误以为自己是多数，导致冲突。

确保一致性

固定以总服务器数为基准，能保证唯一性：任何决策必须获得超过总服务器半数的支持，避免同时存在多个有效结果。

容错能力

系统设计时需预定义容错上限（如允许最多 2 台故障），通过总服务器数计算，可明确系统的最小安全规模（如 5 台允许 2 台故障后仍有过半的 3 台存活）。

hints:

以所有服务器节点为基准也带了问题，就是无法随心所欲的进行扩容和缩容。当然有解决方案，目前是实验 Raft算法中未牵扯到，这里暂时记下。

过半重叠特性

过半的让新老集群至少有一个重叠的，这样就能保证至少有一个服务器是知道最新的任期，日志状况。即使集群出现故障，也会产生一个正确的 Leader。

三、选举

选举的时机与过程

选举是为了挑选出一个主节点，负责与应用层进行交互。选举的时机发生在节点的选举计时器到期，当前节点变为候选人，向其他节点开始发起投票（Vote RPC），如果得票数达成了“过半”，那么候选人将成为 Leader，并向其他节点广播（心跳），新 Leader的任期号，至此选举过程完成。

谁能成为Leader

在系统最初时，某个节点先计时器先到期，成为 Leader的可能性会大些，这里说的是可能，因为要考虑网络情况、系统崩溃等状态，先发起投票的，也有可能不是最先完成的。

成为 Leader的要满足以下两个条件其中之一：

候选人最后一条 Log 条目的任期号大于本地最后一条 Log 条目的任期号；

候选人最后一条 Log 条目的任期号等于本地最后一条条目的任期号，且候选人的 Log 记录长度长度大于等于本地 Log记录的长度。

四、日志复制

1. 日志结构

一般日志命名为 LogEntry,通常日志的结构如下

在实现Raft算法时可酌情进行修改。

2.心跳、日志复制流程

通常来说日志都是伴随着心跳发送出去，心跳也就是日志为空的 AE RPC请求。（但是在具体实现中，也可以将心跳 RPC 和 AppendEntries RPC 分割开来实现）这里将这两个功能放在一起说明。

日志复制正确路径的大体流程如下：

心跳计时器到期，Leader 节点构建参数发送 AE RPC 请求。

如果待接受节点的 nextIndex 和 Leader节点的 lastLogIndex相等，则发送空日志。

其他节点校验请求合法，并将日志（如果有日志的话）追加到本地，重置选举计时器，回复该请求。

合法校验主要包括以下部分：

a.任期是否合法，

如果发送节点的任期低于当前节点，则说明是过期请求，直接拒绝处理。

如果发送节点的任期高于当前节点，当前节点则需要做降级处理。

b.日志是否合法

Leader 发送的日志和当前节点的日志是否冲突。

Leader 节点统计其他节点的回复，如果回复成功的节点“过半”，Leader节点提交日志，并应用到状态机。

3. AppendEntries RPC

论文图 2 已经给出这部分的相关说明。

Leader 通过 AE RPC 发送日志给其他节点，其他节点接受到 AE RPC 请求开始，校验合法性然后将日志追加到本地。

构建发送参数

快照

Raft 协议通过一致性的日志（Log）来保证状态机的同步。每个集群中的节点都维护一份日志，记录了系统状态的改变。随着时间推移，日志会变得越来越长。这个时候如果每个节点都要存储所有日志项，会占用大量的存储空间和内存资源，且在节点崩溃时恢复日志也会变得非常耗时。

为了优化这一问题，Raft 引入了日志快照的概念。

快照的生成

Raft 协议中的日志快照是指将状态机的当前状态保存为一个单独的文件，而不是存储所有的日志条目。快照的生成通常是基于以下的条件：

1. 日志条目过多：当日志的条目数达到一定量时，Raft 会生成快照。

2. 日志索引一定范围内的条目已提交：Raft 节点在某个时间点会决定一个日志条目是否可以被清理，并保存该时间点的快照。

实验部分

LAB 2A 选举

论文第 5 节描述
If a server receives a message with a term T greater than its currentTerm,it updates its currentTerm to T and immediately reverts to follower state.
如果某个节点收到一个任期 T 大于它的 currentTerm 的消息，它会将自己的 currentTerm 更新为 T，并立即降级为跟随者（follower）。

Raft中，每个节点都有一个记录任期（currentTerm），任期随着时间增加，会有以下情况导致节点之间的任期不一致

一个新 Leader被选举时，任期会递增

选举超时触发任期自增

节点间的网络延迟导致不同步的任期值

Raft 的规则规定，当一个节点发现任期落后时，它必须更新自己的 currentTerm 并回到跟随者状态，表示它承认自己不是当前任期的领导者。

应用场景

1. 选票请求（RequestVote RPC）

如果一个节点接收到的 RequestVote 的 term 比自己的 currentTerm 更大，它会更新自己的任期并降级为跟随者。

2. 日志追加（AppendEntries RPC）

如果一个节点接收到的 AppendEntries 的 term 比自己的 currentTerm 更大，同样需要更新任期并回到跟随者。

3. 一致性维护

确保集群中的所有节点对当前任期达成一致，避免出现多个领导者。

目的

1. 保持任期一致性：

防止多个节点自认为是领导者，确保只有一个合法的领导者存在。

2. 解决脑裂问题：

如果一个节点任期过低，它可能会试图和其他节点通信，从而破坏一致性规则。

3.简化选举和日志复制的流程：

保证只有具有最新任期的领导者或候选者参与决策。

为什么选举时间要大于心跳时间

Raft算法中一个非常重要的原则心跳时间必须显著小于选举定时器的最小值。

主要有以下原因：

如果心跳时间太长，而选举定时器的最小值太短，可能还会发生以下问题：

领导者还未来得及发送心跳，跟随者的选举定时器已经超时。

跟随者误以为领导者失效，从而发起选举，导致集群进入不必要的选举。

确保领导者存活的有效检测

心跳时间小于选举定时器，报保证跟随者能够在选举定时器之前，至少收到一条心跳

这样跟随者会重置选举定时器，继续等待领导者的心跳，从而避免错误的选举

示例

假设：心跳时间 = 50ms 选举定时器范围 = 200ms 至 400ms

在这种情况下：领导者每隔 50ms 发送一次心跳，确保在选举定时器触发之前（最短是 200ms），跟随者至少能收到 4 次心跳。跟随者每次收到心跳时都会重置选举定时器，因此不会误触发选举。

但如果：心跳时间 = 300ms 选举定时器范围 = 200ms 至 400ms

可能会发生：跟随者在 200ms 内没有收到心跳，认为领导者已经失效，直接进入选举状态，即便领导者其实还在。

选举定时器

选举定时器是 Follower 节点和 Candidate 节点用来触发选举的机制，而 Leader节点通过定时发送心跳（Heartbeat）来维持自己的领导地位。

需要说明下:

Leader 节点不需要重置自己的选举定时器，当然你可以在发送 AE RPC 来重置自己的选举定时器。

Follower 节点 • 如果在超时前未收到 Leader 的心跳（AppendEntries RPC）或 Candidate 的投票请求（RequestVote RPC），Follower 会转换为 Candidate 并发起新一轮选举。

重置条件：接受到合法任期的心跳或投票请求，会重置自己的选举定时器

Candidate节点

Candidate 在发起选举时也会启动选举定时器。

如果超时前未获得多数节点的投票，会重新发起选举（自增任期并请求投票）。

重置条件：如果 Candidate 收到更高的任期的 Leader 心跳，会退化为 Follower 并重置定时器。

LAB2A 代码部分

主要实现make、ticker、AppendEntries RPC、RequestVote RPC 三个部分，分为这三个部分依次说明。

初始化 make

make 方法是初始化一个 Raft 节点，构建一个 Raft 节点所需的属性可以分为以下三类

公共：任期、状态、日志、心跳计时器、选举定时器

投票：votedFor

日志匹配：nextIndex、matchIndex

🟡

这里的日志中我加了一个 index 属性，便于输出日志和排查问题。

初始化一条空日志是为了方便后面获取发送 Rpc 的为空判断和方便计算索引。

ticker

主要用于心跳定时器器和选举定时器到期做的操作，选举与发送 AppendEntries RPC。这里有更优雅的解决方案就是采取事件驱动编程，这样代码的可读性和维护性比较好。

选举

这一部分要做的事时发起投票请求，已经接受者接到投票请求处理，以及发起者接收到投票请求后的处理（主要是赢得选举的部分）。

LAB 2B 日志复制

如何判断是否提交日志

如果该日志已经复制到在过半节点中，则可以提交日志。

AppendEntries

LAB 2D 日志快照

提交日志

在 LAB 2A、2B、2C 时该代码是没有问题的。在 LAB 2D中使用该方法提交日志会有问题。

Leader 节点0 logs = [1,2,3,4,5,6,7] commitIndex=7 matchIndex=[0,7,7]

Follower 节点1 logs = [1,2,3,4,5,6,7] commitIndex=1

Follower 节点2 logs = [1,2,3,4,5,6,7] commitIndex=1

Leader节点 0 试图提交日志 7，但是一直无法提交成功。导致重新选举。因为applyLogs()方法中向通道发送信息阻塞，而 rf节点的锁一直无法释放，无法发送AE RPC 请求，结果其他节点选举计时器到时而发起重新选举的请求，最终会导致产生两个 Leader，而新 Leader也是没办法继续提交日志到状态机中。

通道的阻塞特性 Go 语言中的通道（chan）是阻塞的。如果 applyCh 通道的缓冲区已满，发送操作（<-）会阻塞，直到有接收者从通道中读取数据。如果在发送操作时持有锁（rf.mu），而接收者（上层应用）可能也在等待锁，就会导致死锁。例如： Raft 持有锁并尝试发送数据到 applyCh，但 applyCh 已满，发送操作阻塞。上层应用尝试获取锁以处理 applyCh 中的数据，但由于锁被 Raft 持有，上层应用无法继续执行。这样，Raft 和上层应用互相等待，导致程序无法继续运行。

锁的持有时间过长在 Raft 的实现中，锁（rf.mu）通常用于保护共享状态（例如 commitIndex、lastApplied、logs 等）。如果在发送到 applyCh 时持有锁，锁的持有时间会延长，增加了其他 Goroutine 等待锁的时间，降低了并发性能。这可能导致 Raft 的其他操作（例如处理 RPC 请求、选举等）被阻塞，影响系统的整体响应速度。

锁的粒度应该尽可能小，只在必要时保护共享状态。发送到 applyCh 的操作并不需要保护共享状态，因此不需要持有锁。如果在发送到 applyCh 时持有锁，会导致锁的粒度过大，增加了锁竞争的可能性。

全局索引、局部索引、lastIncludedIndex

全局索引（Global Index）：日志在整个 Raft 运行期间的真实索引，不会因为快照而改变。

局部索引（Local Index）: 日志在 rf.logs 数组的索引，会受到快照的影响。

lastIncludedIndex：最新快照包含的日志索引，快照之前的日志都已经删除

示例

此时 lastIncludedIndex =0 Global Index 和 Local Index 相同

进行快照 Snapshot(index=4)

此时 lastIncludedIndex==index=3

Global Index =[4,5]

Local Index =[0,1]

GlobalToLocalIndex(4) = 4 - 4 = 0

LocalToGlobalIndex(0) = 0 + 4= 4

优化

只读请求

只读请求不会写日志，但需要确认 Leader 是当前任期的真正 Leader。