前言：由于最近找工作战况严峻，不得以只能再掏个去年的项目，顺便温故一下之前学习分布式知识，commit就是最好的证明~PS：希望写这个Lab的不要太功利，bug才是真正提高自己水平的~

那段时光也是最能静下心来，算是研究生生涯中相对美好的时光，感谢这个实验陪我度过生命中至暗的时刻~~~

image-20240914105627683

人生没有绝对的成功，以个人最舒服的姿态和最擅长的方式去活一生就已足够！

摘自：2022 互联网求职经验分享

实验介绍

lab2 的内容是要实现一个除了节点变更功能外的 raft 算法，还是比较有趣的。 它被划分成了Lab2A、Lab2B、Lab2C和Lab2D四个子任务：

  1. Lab2A：实现 leader election、heartbeat。
  2. Lab2B：实现 Log replication。
  3. Lab2C：实现 state persistent。
  4. Lab2D：实现 SnapShot

实现的话建议先看官方文档，可以帮助我们避开很多的🕳，推荐：MIT6.824 来自己动手实现一个Raft协议吧(Lab2A)

剩下的只要严格根据论文的这张图实现，就可以完成了~

image-20240604203937594

任务要求

  • 实现Raft的leader选举和心跳机制（没有log entries的AppendEntriesRPCs）。
  • Part 2A的目标是：选出一个leader，在没有故障的情况下，这个leader仍然是leader；如果旧leader故障，或者旧leader的数据包丢失，那么新的leader接管。
  • 运行go test -run 2A来测试你的Part 2A部分的代码。
  • 路径切换到6.824/src/raft再执行测试go test -run 2A
  • 若Part 2A全部通过，则显示如下：
1
2
3
4
5
6
7
8
9
go
$ go test -run 2A
Test (2A): initial election ...
... Passed -- 4.0 3 32 9170 0
Test (2A): election after network failure ...
... Passed -- 6.1 3 70 13895 0
PASS
ok raft 10.187s
$

每个"Passed"行包括5个数字，它们分别是：

  1. 测试花费的时间（以秒为单位）
  2. Raft peers的数量（通常是3或5）
  3. 在测试期间发送的RPC的数量
  4. RPC消息中的总字节数
  5. 以及Raft报告提交的日志条目的数量。

任务提示

  • 你不能直接运行你的Raft实现；相反，你应该通过tester来运行它，即运行go test -run 2A
  • 根据Raft论文中的Figure 2，此阶段，你关心的是发送和接收RequestVote RPCs、与选举相关的服务器规则以及与leader选举相关的状态

在这个实验，只需要关注画红框的实现

image-20240914101158374

  • 将Figure 2中的leader选举的状态添加到raft.go中的Raft结构中。

    你还需要定义一个结构来保存关于每个日志条目的信息。

  • 填充RequestVoteArgs和RequestVoteReply结构体。修改Make()以创建一个后台groutine，当它有一段时间没有收到另一个peer的消息时，通过发送RequestVote RPCs周期性地启动leader选举。

    通过这种方式，peer将了解谁是leader，如果已经有leader，或者自己成为leader。

    实现RequestVote() RPC处理程序，以便服务器相互投票。

  • 要实现心跳（heartbeats），定义一个AppendEntries RPC结构(尽管你可能还不需要所有参数)，并让leader定期发送它们。编写一个AppendEntries RPC处理方法，重置选举超时，以便当一个server已经当选时，其他servers不会仍想成为leader。

  • 确保不同peers的选举超时不总是同时发生，否则所有peers只会为自己投票，没有人会成为leader。

  • tester要求leader每秒发送heartbeat RPCs不超过10次。

  • tester要求你的Raft在旧leader故障后的5秒内选出一个新的leader（如果大多数peer仍然可以通信）。

    但是，请记住，如果出现分裂投票，leader选举可能需要多轮（如果数据包丢失或候选人不幸选择了相同的随机退出时间，则可能发生这种情况）。您必须选择足够短的选举超时设定（以及心跳间隔），以便即使需要多轮选举，也很可能在5秒内完成选举。

  • 论文的5.2节提到了150到300毫秒范围内的选举超时设定。只有当leader发出的心跳频率大大超过每150毫秒一次时，这个范围才有意义。因为测试器将你的心跳限制为每秒10次，所以你必须使用比论文的150到300毫秒更大的选举超时设定的同时又不能太大，因为那样您可能无法在5秒内选出领导者。

  • 你或许会发现Go的rand很有用。

  • 你需要编写定期或延迟后执行操作的代码。要做到这一点，最简单的方法是创建一个带有调用了time.Sleep()的循环的goroutine。不要使用Go的time.Timer或 time.Ticker ，它们很难使用正确。

  • 阅读关于locking和structure的建议（一定要读！！！否则Part 2A会遇到很多加锁不合理导致的死锁和DATA RACE！！！）。如果你的代码在通过测试时遇到困难，请再次阅读论文的Figure 2，leader选举的完整逻辑就分布在Figure的多个部分。

  • 不要忘记实现GetState()

  • tester在永久关闭一个实例时会调用你的Raft的rf.Kill()。你可以使用rf.killed()检查Kill()是否已被调用。

  • 你可能希望在所有循环中都这样做，以避免死亡的Raft实例打印令人困惑的消息。

  • 调试代码的一个好方法是在peer发送或接收消息时插入print语句，并使用go test -run 2A > out将输出收集到一个文件中。然后，通过研究out文件中的消息跟踪，你可以确定你的实现在哪里偏离了期望的协议。

  • 你可能会发现util.go中的DPrintf在调试不同的问题时打开和关闭打印非常有用。

  • Go RPC只发送名称以大写字母开头的结构字段（导出的）。

    子结构也必须有大写的字段名（例如数组中的日志记录字段）。labgob包会提醒你这一点，不要忽视警告。

  • 用go test -race检查你的代码，并修复它报告的任何race。

实验思路

首先在test_test.go文件写了测试程序，通过make_config 函数创建一个配置对象 config，该对象管理一组 Raft 实例的测试环境。

这部分可以详细读一下。

raft结构体数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type Raft struct {
	mu        sync.Mutex          // Lock to protect shared access to this peer's state
	peers     []*labrpc.ClientEnd // RPC end points of all peers
	persister *Persister          // Object to hold this peer's persisted state
	me        int                 // this peer's index into peers[]
	dead      int32               // set by Kill()

	// Your data here (2A, 2B, 2C).
	// Look at the paper's Figure 2 for a description of what
	// state a Raft server must maintain.
	// 根据论文的要求定义
	currentTerm     int         // Server当前的term
	voteFor         int         // Server在选举阶段的投票给了谁
	voteGrantedNum  int         // 收集到的投票数量
	state           int         // 当前状态
	heartbeatTimer  *time.Timer // 心跳超时时间
	electionTimeout *time.Timer // 随机选举时间
}

我们通过raft.go中的Make函数初始化raft实例。

  1. 创建 Raft 实例：
    • rf := &Raft{}：创建一个新的 Raft 实例 rf。
  2. 设置Raft 实例的基本属性：
    • rf.peers = peers：设置 Raft 实例的 peers 列表，即与其他 Raft 实例的通信端点。
    • rf.persister = persister：设置 Raft 实例的持久化对象，用于保存和恢复 Raft 状态。
    • rf.me = me：设置 Raft 实例的 ID，标识当前实例。
  3. 初始化 Raft 实例的参数：
    • rf.currentTerm = 0：初始化当前任期为 0。
    • rf.voteFor = -1：初始化投票状态为未投票。
    • rf.voteGrantedNum = 0：初始化获得的投票数为 0。
    • rf.state = StateFollower：初始化状态为 Follower。
    • rf.electionTimeout = time.NewTimer(RandomizedElectionTimeout())：设置随机选举超时定时器。
    • rf.heartbeatTimer = time.NewTimer(StableHeartbeatTimeout())：设置稳定心跳定时器。
  4. 从持久化状态中恢复 Raft 实例的状态：
    • rf.readPersist(persister.ReadRaftState())：从持久化对象中读取 Raft 状态，并恢复到当前 Raft 实例中。
  5. 启动 ticker goroutine：
    • go rf.ticker()：启动一个 goroutine 来处理选举和心跳定时器，以开始选举过程。
  6. 返回初始化完成的 Raft 实例：
    • return rf：返回初始化完成的 Raft 实例。

这里的超时时间设置如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const (
	HeartbeatTimeout = 50  //  心跳超时 针对leader
	ElectionTimeout  = 150 //  选举超时
)

func StableHeartbeatTimeout() time.Duration {
	return time.Duration(HeartbeatTimeout) * time.Millisecond
}

func RandomizedElectionTimeout() time.Duration {
	// Note：RandomizedElectionTimeout between [T,2T]
	// bug : not sure
	return time.Duration(ElectionTimeout+rand.Intn(ElectionTimeout*2)) * time.Millisecond
	// return ElectionTimeout + (time.Duration(rand.Int63()) % ElectionTimeout)
}

通过go rf.ticker()函数启动 raft。

ticker 函数

ticker 方法是 Raft 实例的一个 goroutine，用于处理选举超时和心跳定时器。以下是该方法的详细总结：

  1. 无限循环：
    • for !rf.killed() { ... }：只要 Raft 实例没有被终止，就持续运行。
  2. 选举超时处理：
    • select { case <-rf.electionTimeout.C: ... }：等待选举超时定时器触发。
      • rf.mu.Lock()：加锁，确保线程安全。
      • if rf.state != StateLeader { ... }：如果当前状态不是 Leader，则开始选举。
        • rf.changeInfo()：改变 Raft 实例的状态信息，准备选举。
        • rf.mu.Unlock()：解锁，确保在请求投票过程中不持有锁。
        • PrettyDebug(dInfo, "S%dterm:%d=state:%d=[StartElect]", rf.me, rf.currentTerm, rf.state)：打印调试信息，表示开始选举。
        • rf.startElection()：发起选举请求。
      • else { rf.mu.Unlock() }：如果当前状态是 Leader，则解锁并继续。
  3. 心跳定时器处理：
    • case <-rf.heartbeatTimer.C: ...：等待心跳定时器触发。
      • rf.mu.Lock()：加锁，确保线程安全。
      • if rf.state == StateLeader { ... }：如果当前状态是 Leader，则广播心跳。
        • rf.BroadcastHeartbeat()：向所有 Follower 发送心跳消息。
        • rf.heartbeatTimer.Reset(StableHeartbeatTimeout())：重置心跳定时器。
      • rf.mu.Unlock()：解锁。

这里主要2个功能，超时选举和心跳机制。

当选举时间超时的时候，那么就会改变自身状态变成候选者，然后开始拉选票。

【下面给出其逻辑，读者自行实现】

startElection 函数的主要功能是发起选举，并向所有 peers 发送请求投票 RPC。它通过遍历所有 peers，并启动 goroutine 来处理每个 peer 的投票结果。如果获得的投票数超过半数，则当前 Raft 实例成为 Leader，并广播心跳消息。如果投票未被授予，则根据回复中的任期更新当前任期和状态。通过这种方式，startElection 方法确保 Raft 实例能够有效地发起选举并处理投票结果。

这里比较核心的就是RPC：RequestVote

【下面给出其逻辑，读者自行实现】

RequestVote 函数的主要功能是处理请求投票 RPC。它首先检查请求的任期是否小于当前 Raft 实例的任期，如果是，则拒绝投票。如果请求的任期大于当前任期，则更新当前任期和状态。然后，检查是否已经投过票，并且是否投给当前请求的候选人，如果是，则拒绝投票。最后，投票给请求的候选人，并重置选举超时定时器。通过这种方式，RequestVote 方法确保 Raft 实例能够正确处理请求投票 RPC，并维护集群的一致性。

心跳机制的话也是一样的。根据论文实现即可。

实验调试

image-20240914105426791

经验之谈：调试的话一般是通过日志，信息短的话通过可视化直接查看。

bug1

思考：你断开之后，别人向你发的请求你没有收到？
解决方案：改变超时时间
猜测原因：你还没起来或者阻塞了

错误的情况

image-20240914105448848

正确情况

image-20240914105556426

bug2

日志文件巨大，死循环了，貌似是活锁，猜的真准！

image-20240914105823850

image-20240914105650414

分析日志：从日志中可以看到，系统处于一个无限循环中，反复发送 RequestVote 请求，即 SendRequestVote-loop 不断重复，这表明某种操作在持续进行，但并没有实际进展。这种行为可能是由于多个节点在选举过程中不断请求投票，但始终无法成功进入到下一个状态。

可能原因：

  • 网络延迟或通信问题：节点之间的消息来回传递，但由于网络延迟、丢包等原因，选举过程无法完成，导致节点一直反复请求投票。
  • 选举超时设置不佳：如果多个节点几乎同时进入选举状态并开始发送投票请求，它们可能会持续干扰彼此，导致活锁。
  • 选举过程中的竞争：多个节点可能同时尝试成为领导者，彼此互相干扰，导致选举无法成功完成。

解决方法：

  1. 引入随机化超时：在分布式系统中，特别是在选举过程中，随机化超时是一种常见的处理活锁的策略。通过给选举超时设置一个随机范围，可以减少多个节点同时进入选举状态的概率，从而避免活锁的发生。
  2. 调整超时和重试机制：适当地增加超时的间隔时间，减少频繁的请求重发。
  3. 网络优化：如果是由于网络问题导致的活锁，可以考虑优化网络，减少延迟和丢包的情况。

活锁概念：

活锁（Livelock）是一种类似于死锁的情形，但不同的是，在活锁中，系统的各个进程或线程并没有完全停滞不前，而是一直在做一些操作（通常是尝试去解决冲突或问题），但由于相互干扰，系统无法取得任何实际进展。也就是说，活锁中的某些进程或线程仍在不断改变状态，但没有一个能够完成它们的任务。

在活锁中，进程或线程会：

  1. 不断地做出响应并尝试解决问题。
  2. 由于每个进程都在做出响应，导致整体系统无法前进。

最后，将选举超时时间设置成RandomizedElectionTimeout() = (ElectionTimeout + rand.Intn(ElectionTimeout)) * time.Millisecond即可解决。