跳至主要內容

MIT 6.824 Lab 3学习笔记

SyYhunfhds2026/4/16大约 11 分钟

参考资料

Lab 3

理论部分

选举流程和实现要求

  • 节选自译文对论文图二的解释

Raft 是一种用来管理章节 2 中描述的复制日志的算法。图 2 为了参考之用，总结这个算法的简略版本，图 3 列举了这个算法的一些关键特性。图中的这些元素会在剩下的章节逐一介绍。

Raft 通过选举一个杰出的领导人，然后给予他全部的管理复制日志的责任来实现一致性。领导人从客户端接收日志条目（log entries），把日志条目复制到其他服务器上，并告诉其他的服务器什么时候可以安全地将日志条目应用到他们的状态机中。拥有一个领导人大大简化了对复制日志的管理。例如，领导人可以决定新的日志条目需要放在日志中的什么位置而不需要和其他服务器商议，并且数据都从领导人流向其他服务器。一个领导人可能会发生故障，或者和其他服务器失去连接，在这种情况下一个新的领导人会被选举出来。

通过领导人的方式，Raft 将一致性问题分解成了三个相对独立的子问题，这些问题会在接下来的子章节中进行讨论：

  • 领导选举：当现存的领导人发生故障的时候, 一个新的领导人需要被选举出来（章节 5.2）
  • 日志复制：领导人必须从客户端接收日志条目（log entries）然后复制到集群中的其他节点，并强制要求其他节点的日志和自己保持一致。
  • 安全性：在 Raft 中安全性的关键是在图 3 中展示的状态机安全：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其他服务器节点不能在同一个日志索引位置应用一个不同的指令。章节 5.4 阐述了 Raft 算法是如何保证这个特性的；这个解决方案涉及到选举机制（5.2 节）上的一个额外限制。

在展示一致性算法之后，这一章节会讨论一些可用性的问题和计时在系统中的作用。

状态：

所有服务器上的持久性状态 (在响应 RPC 请求之前，已经更新到了稳定的存储设备)

参数解释
currentTerm服务器已知最新的任期（在服务器首次启动时初始化为0，单调递增）
votedFor当前任期内收到选票的 candidateId，如果没有投给任何候选人 则为空
log[]日志条目；每个条目包含了用于状态机的命令，以及领导人接收到该条目时的任期（初始索引为1）

所有服务器上的易失性状态

参数解释
commitIndex已知已提交的最高的日志条目的索引（初始值为0，单调递增）
lastApplied已经被应用到状态机的最高的日志条目的索引（初始值为0，单调递增）

领导人（服务器）上的易失性状态 (选举后已经重新初始化)

参数解释
nextIndex[]对于每一台服务器，发送到该服务器的下一个日志条目的索引（初始值为领导人最后的日志条目的索引+1）
matchIndex[]对于每一台服务器，已知的已经复制到该服务器的最高日志条目的索引（初始值为0，单调递增）

追加条目（AppendEntries）RPC：

由领导人调用，用于日志条目的复制，同时也被当做心跳使用

参数解释
term领导人的任期
leaderId领导人 ID 因此跟随者可以对客户端进行重定向（译者注：跟随者根据领导人 ID 把客户端的请求重定向到领导人，比如有时客户端把请求发给了跟随者而不是领导人）
prevLogIndex紧邻新日志条目之前的那个日志条目的索引
prevLogTerm紧邻新日志条目之前的那个日志条目的任期
entries[]需要被保存的日志条目（被当做心跳使用时，则日志条目内容为空；为了提高效率可能一次性发送多个）
leaderCommit领导人的已知已提交的最高的日志条目的索引
返回值解释
term当前任期，对于领导人而言 它会更新自己的任期
success如果跟随者所含有的条目和 prevLogIndex 以及 prevLogTerm 匹配上了，则为 true

接收者的实现：

  1. 返回假 如果领导人的任期小于接收者的当前任期（译者注：这里的接收者是指跟随者或者候选人）（5.1 节）
  2. 返回假 如果接收者日志中没有包含这样一个条目 即该条目的任期在 prevLogIndex 上能和 prevLogTerm 匹配上 （译者注：在接收者日志中 如果能找到一个和 prevLogIndex 以及 prevLogTerm 一样的索引和任期的日志条目 则继续执行下面的步骤 否则返回假）（5.3 节）
  3. 如果一个已经存在的条目和新条目（译者注：即刚刚接收到的日志条目）发生了冲突（因为索引相同，任期不同），那么就删除这个已经存在的条目以及它之后的所有条目 （5.3 节）
  4. 追加日志中尚未存在的任何新条目
  5. 如果领导人的已知已提交的最高日志条目的索引大于接收者的已知已提交最高日志条目的索引（leaderCommit > commitIndex），则把接收者的已知已经提交的最高的日志条目的索引commitIndex 重置为 领导人的已知已经提交的最高的日志条目的索引 leaderCommit 或者是 上一个新条目的索引 取两者的最小值

请求投票（RequestVote）RPC：

由候选人负责调用用来征集选票（5.2 节）

参数解释
term候选人的任期号
candidateId请求选票的候选人的 ID
lastLogIndex候选人的最后日志条目的索引值
lastLogTerm候选人最后日志条目的任期号
返回值解释
term当前任期号，以便于候选人去更新自己的任期号
voteGranted候选人赢得了此张选票时为真

接收者实现：

  1. 如果term < currentTerm返回 false （5.2 节）
  2. 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他（5.2 节，5.4 节）

所有服务器需遵守的规则：

所有服务器：

  • 如果commitIndex > lastApplied，则 lastApplied 递增，并将log[lastApplied]应用到状态机中（5.3 节）
  • 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，则令 currentTerm = T，并切换为跟随者状态（5.1 节）

跟随者（5.2 节）：

  • 响应来自候选人和领导人的请求
  • 如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，就自己变成候选人

候选人（5.2 节）：

  • 在转变成候选人后就立即开始选举过程
    • 自增当前的任期号（currentTerm）
    • 给自己投票
    • 重置选举超时计时器
    • 发送请求投票的 RPC 给其他所有服务器
  • 如果接收到大多数服务器的选票，那么就变成领导人
  • 如果接收到来自新的领导人的附加日志（AppendEntries）RPC，则转变成跟随者
  • 如果选举过程超时，则再次发起一轮选举

领导人：

  • 一旦成为领导人：发送空的附加日志（AppendEntries）RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以防止跟随者超时（5.2 节）
  • 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端（5.3 节）
  • 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex（lastLogIndex ≥ nextIndex），则发送从 nextIndex 开始的所有日志条目：
    • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
    • 如果因为日志不一致而失败，则 nextIndex 递减并重试
  • 假设存在 N 满足N > commitIndex，使得大多数的 matchIndex[i] ≥ N以及log[N].term == currentTerm 成立，则令 commitIndex = N（5.3 和 5.4 节）

实践部分

实现选举机制

问题排查

Lab 3A

Go 1.18遗留问题


非 常量字符串引用？？
t.Fatalf的第一个参数应该是字符串字面量，而不是变量

任期冲突


因为是自顶向下实现，所以AppendEntries当时还没写好

【ReElection3A】Brain Split


原来的实现中，Candidate选举超时时不会自增任期，导致历史心跳仍然有效


改完之后第一个测试炸了

可能是因为requestVotes也没有写完的锅

【ReElection 3A】 脑裂最新力作


此时已经重写了2/3的选举机制

  • 旧Leader卡了一下没回复
  • 俩Follower立马开始选举
  • 但是requestVote的比对优先级是：
    1. 是Leader就不干
    2. 比对任期
    3. 比对日志索引（待实现）
  • 旧Leader上线后不会响应Candidate的投票请求，Candidate拉不到票只能重新开始选举，Candidate也不会给对方投票

这是当时的Leader实现：

func (rf *Raft) doLeader(ctx context.Context) {
	rf.log.Info("节点已成为Leader")
	ticker := time.NewTicker(rf.heartbeatInterval)
	defer ticker.Stop()

	rf.heartbeatBroadcast() // 心跳日志广播

	for {
		select {
		case <-ctx.Done():
			return
		case <-ticker.C:
			// 进行心跳日志
			rf.heartbeatBroadcast()
		}
	}

}

可以看到是完全不处理最近心跳和最近投票的


现在可以强行切换状态了，但仍然不通过

2026-04-28T21:37:51.651+0800    DEBUG   raft1/functionalities.go:47     节点未收到心跳日志, 也未进行投票, 将开始选举    {"server-id": 1}
2026-04-28T21:37:51.651+0800    INFO    raft1/raft.go:122       节点状态已切换  {"server-id": 1, "old-role": "Follower", "new-role": "Candidate"}
2026-04-28T21:37:51.653+0800    DEBUG   raft1/raft_rpc.go:52    节点收到投票请求        {"server-id": 0, "节点当前任期": 14, "请求来源ID": 1, "请求来源的任期": 14}
2026-04-28T21:37:51.656+0800    DEBUG   raft1/utilities.go:106  Candidate已收到投票回复 {"server-id": 1, "请求目标ID": 0}
2026-04-28T21:37:51.658+0800    DEBUG   raft1/raft_rpc.go:52    节点收到投票请求        {"server-id": 2, "节点当前任期": 14, "请求来源ID": 1, "请求来源的任期": 14}
Fatal: expected one leader, got none
        /develop/6.5840/src/raft1/test.go:150
        /develop/6.5840/src/raft1/raft_test.go:65
2026-04-28T21:37:51.659+0800    DEBUG   raft1/utilities.go:106  Candidate已收到投票回复 {"server-id": 1, "请求目标ID": 2}
2026-04-28T21:37:51.659+0800    INFO    raft1/functionalities.go:69     节点开始选举    {"server-id": 1, "节点当前任期": 14}


神了，这请求是哪来的

【ReElection 3A】 终于成功一次


NMD终于成功一次

【ReElection 3A】 任期相同的脑裂

2026-04-28T22:27:35.666+0800    DEBUG   raft1/raft_rpc.go:222   已完成一次日志附加请求  {"server-id": 0, "当前任期": 3, "请求目标ID": 2, "响应体中的任期": 3}
2026-04-28T22:27:35.666+0800    INFO    raft1/utilities.go:131  已发送心跳日志  {"server-id": 0, "destination-id": 2, "Leader当前任期": 3}
2026-04-28T22:27:35.714+0800    INFO    raft1/raft_rpc.go:162   节点收到日志附加请求    {"server-id": 1, "节点当前任期": 3, "请求来源ID": 0, "请求来源的任期": 3}
2026-04-28T22:27:35.715+0800    DEBUG   raft1/raft_rpc.go:222   已完成一次日志附加请求  {"server-id": 0, "当前任期": 3, "请求目标ID": 1, "响应体中的任期": 3}
2026-04-28T22:27:35.715+0800    INFO    raft1/utilities.go:131  已发送心跳日志  {"server-id": 0, "destination-id": 1, "Leader当前任期": 3}
2026-04-28T22:27:35.716+0800    INFO    raft1/raft_rpc.go:162   节点收到日志附加请求    {"server-id": 2, "节点当前任期": 3, "请求来源ID": 0, "请求来源的任期": 3}
2026-04-28T22:27:35.717+0800    DEBUG   raft1/raft_rpc.go:222   已完成一次日志附加请求  {"server-id": 0, "当前任期": 3, "请求目标ID": 2, "响应体中的任期": 3}
2026-04-28T22:27:35.717+0800    INFO    raft1/utilities.go:131  已发送心跳日志  {"server-id": 0, "destination-id": 2, "Leader当前任期": 3}
2026-04-28T22:27:35.763+0800    INFO    raft1/raft_rpc.go:162   节点收到日志附加请求    {"server-id": 1, "节点当前任期": 3, "请求来源ID": 0, "请求来源的任期": 3}
Fatal: term 3 has 2 (>1) leaders
        /develop/6.5840/src/raft1/test.go:134
        /develop/6.5840/src/raft1/raft_test.go:77

页面底部

编辑此页
最近更新
贡献者: SyYhunfhds
syy-blogs is licensed under CC BY-NC-SA 4.0. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/4.0/
Copyright © 2026 SyYhunfhds