Part 2B: Log Replication 日志复制 (困难)
文章目录
Lab1：MapReduce
Lab2：Raft 实验解读
Lab2A：领导者选举 leader election
我的代码实现（附带详细代码注释）
直达gitee链接
https://gitee.com/zhou-xiujun/xun-go/tree/master/com/xun/Mit-6.824-xun
Part 2B部分主要实现领导者和跟随者的代码以附加新的日志条目，以便通过 go test -run 2B 测试。
提示：
- 首要目标应该是通过
TestBasicAgree2B()。首先实现Start()方法，然后编写代码，通过AppendEntriesRPC 发送和接收新的日志条目，按照论文中的图 2 实现。在每个节点上将每个新提交的条目发送到applyCh。 - 需要实现选举限制（论文的第 5.4.1 节）。
- 在早期的 Lab 2B 测试中，可能无法达成一致的一个原因是，即使领导者还在，仍然进行反复选举。检查选举计时器管理中的错误，或者检查在赢得选举后有没有立即发送心跳。
- 你的代码可能会有循环去反复检查某些事件。不要让这些循环在没有暂停的情况下连续执行，因为这会减慢你的实现速度，导致测试失败。使用 Go 的条件变量，或者在每次循环迭代中插入
time.Sleep(10 * time.Millisecond)。 - 为了将来更好地进行实验，请编写（或重写）干净且清晰的代码。可以参考指导页面，获取开发和调试代码的提示。
- 如果测试失败，查看
config.go和test_test.go中的测试代码，以更好地理解测试的内容。config.go还展示了测试者如何使用 Raft API。
如果你的代码运行得太慢，你的代码可能在之后的实验的测试中无法通过。可以使用 time 命令检查解决方案使用了多少实时时间和CPU时间。以下是典型的输出：
$ time go test -run 2B
Test (2B): basic agreement ...
... Passed -- 0.9 3 16 4572 3
Test (2B): RPC byte count ...
... Passed -- 1.7 3 48 114536 11
Test (2B): agreement after follower reconnects ...
... Passed -- 3.6 3 78 22131 7
Test (2B): no agreement if too many followers disconnect ...
... Passed -- 3.8 5 172 40935 3
Test (2B): concurrent Start()s ...
... Passed -- 1.1 3 24 7379 6
Test (2B): rejoin of partitioned leader ...
... Passed -- 5.1 3 152 37021 4
Test (2B): leader backs up quickly over incorrect follower logs ...
... Passed -- 17.2 5 2080 1587388 102
Test (2B): RPC counts aren't too high ...
... Passed -- 2.2 3 60 20119 12
PASS
ok 6.824/raft 35.557s
real 0m35.899s
user 0m2.556s
sys 0m1.458s
$
“ok 6.824/raft 35.557s”意味着Go测量到2B测试所需的时间为实际时间（挂钟）的35.557秒。“user 0m2.556s”意味着代码消耗了2.556秒的CPU时间，即实际执行指令所花费的时间（而不是等待或睡眠）。如果你的解决方案在2B测试中使用的实时时间远远超过一分钟，或者CPU时间远远超过5秒，以后可能会遇到问题。请查找睡眠或等待RPC超时所花费的时间、在没有睡眠或等待条件或通道消息的情况下运行的循环，或者发送的大量RPC。
实现细节：
这里只展示了部分，具体的可以参考代码注释
1、commitIndex 和 lastApplied
在Raft分布式一致性算法中，commitIndex 和 lastApplied 是两个非常重要的状态变量，它们分别追踪不同的进度指标，但都与日志的提交和应用紧密相关。下面是这两个变量关系的简要说明：
- commitIndex: 此变量记录了已知被集群中大多数节点复制的最高日志条目的索引。换句话说，它是Raft领导者可以安全地认为已经被持久化并且可以被所有追随者接受的日志条目的最高索引。当领导者收到足够多的追随者对某个日志条目的确认（通过心跳或AppendEntries RPC响应），它就会更新commitIndex。这个值的更新是领导者决定哪些日志可以被提交（即应用到状态机）的基础。
- lastApplied: 此变量记录了状态机实际应用的最高日志条目的索引。这意味着，索引小于或等于lastApplied的日志条目，其包含的命令已经被执行并且影响到了服务的状态。lastApplied在Raft节点作为追随者或领导者时都会更新，每当有新的日志条目被安全地提交（即commitIndex前进），Raft节点就会逐步将这些已提交的日志应用到状态机上，同时更新lastApplied。
两者之间的关系：
lastApplied总是小于等于commitIndex。这是因为只有当一个日志条目被提交（即其索引大于等于commitIndex），它才能被应用到状态机上，从而更新lastApplied。
在正常操作下，每当有新的日志条目被提交（即commitIndex增加），Raft节点随后会逐步将这些已提交的日志应用到状态机，导致lastApplied逐渐追赶commitIndex。但在某些情况下，比如刚成为领导者或处理日志应用的延迟，lastApplied可能会暂时落后于commitIndex。
维护这两个变量的正确性是确保系统一致性和容错性的关键。commitIndex确保了安全性，即不会丢失已提交的日志；而lastApplied确保了系统状态的一致更新，即所有已提交的更改最终都会反映在服务状态中。
2、nextIndex 和 matchIndex
在Raft分布式一致性算法中，nextIndex 和 matchIndex 是两个核心状态变量，它们维护在每个Raft节点（尤其是领导者节点）中，用以管理与其它节点（跟随者节点）间日志复制的过程。这两个索引反映了领导者如何高效且正确地推进日志同步，确保整个集群的日志一致性。下面是它们之间关系的详细说明：
nextIndex:
定义: 对于每一个跟随者，nextIndex[i] 存储的是领导者计划发送给跟随者i的下一个日志条目的索引。初始化时，它通常被设置为领导者当前日志的最后一条日志的索引加1，意味着领导者将从跟随者尚未有的第一条日志开始发送。
作用: 该变量控制了领导者向特定跟随者发送日志的起点，是解决日志不一致性和优化日志复制效率的关键。当跟随者的日志与领导者不一致时，领导者会根据跟随者的反馈适当减少nextIndex值，以找到两方日志中共同的部分，从而避免日志冲突。
matchIndex:
定义: 同样针对每个跟随者，matchIndex[i] 记录了领导者已知的、在跟随者i上已成功复制的最高日志条目的索引。初始化时为0，随着日志复制过程的进行，这个值会单调递增。
作用: 它反映了跟随者与领导者日志同步的最远进度。领导者使用matchIndex来决定何时可以安全地提升commitIndex，即当大多数跟随者的matchIndex满足条件时，领导者可以提交日志。此外，matchIndex也用于领导者计算多数派，以决定哪些日志条目可以被提交。
两者之间的关系:
协调复制: 在日志复制过程中，nextIndex指示发送的起始点，而matchIndex记录了已确认的终点。领导者通过比较跟随者的回复（如AppendEntries RPC的响应）来动态调整nextIndex，以解决日志不一致问题。一旦跟随者确认了一组日志条目，领导者就会更新该跟随者的matchIndex，表示这些日志已被安全复制。
同步进展: 当nextIndex与matchIndex之间的差距缩小，意味着跟随者正在逐步赶上领导者，日志同步在进行中。反之，如果差距增大或不变，可能表示存在日志不一致或其他通信问题。
安全性保证: 通过这两个索引的协同工作，Raft确保了日志的一致性，防止了旧日志覆盖新日志的情况，同时也保证了提交的日志在大多数节点上都是持久化的，这是Raft算法实现数据一致性的基础。
3、ConvertToLeader时重置nextIndex
在Raft算法中，当一个节点转换为领导者（Leader）角色时，确实会将其nextIndex数组中的所有项初始化为其本地日志的最后一条日志的索引加1。这样做基于以下几点考虑和机制设计：
初始化策略：这是一种保守的初始化策略。虽然看起来直接将nextIndex设置为领导者日志的末尾可能导致与一些跟随者（Follower）的日志不匹配，但这是为了快速探测到不一致并作出相应调整。如果跟随者的日志实际上没有达到领导者日志的长度，后续的AppendEntries请求会因为日志不匹配而失败（因为跟随者的日志索引处的日志任期号与领导者尝试发送的日志任期号不一致），领导者会相应地减小nextIndex值，直到找到匹配点。
探测不一致：通过这样的初始化，领导者能够快速发现并解决日志不一致的问题。当领导者首次尝试发送日志时，如果跟随者的日志不包含领导者尝试发送的日志条目，跟随者会回复一个拒绝消息，告知领导者其日志的最后一条条目的任期号。领导者收到这类反馈后，会相应降低对该跟随者的nextIndex，然后尝试发送一个较旧的日志条目，直至找到两个节点日志中匹配的部分。
效率与一致性权衡：这种做法在一定程度上牺牲了初次同步的效率，因为可能会导致跟随者频繁拒绝领导者的消息，但从长期看，它能快速收敛到一致状态，并确保日志的一致性。相比从一个较低的索引开始逐步试探，直接设置较高的nextIndex可以更快地在大多数情况下找到正确的匹配点，尤其是在跟随者日志相对落后不多的情况下。
安全性：尽管直接将nextIndex设置为最大值可能导致短期内的RPC失败，但Raft算法的设计确保了即使在这种情况下，也不会破坏系统的安全性。领导者始终只会在其当前任期的日志条目上进行投票，而且只有当大多数节点确认了日志条目，才会提交日志，这保证了日志的一致性和正确性。
综上所述，虽然这种初始化方式可能会在转换为领导者后立即遇到一些日志不匹配的错误，但它是一种快速探测并解决日志不一致性的策略，且在Raft算法的框架内，通过后续的调整和重试机制，能够确保集群最终达到一致状态。
4、处理日志复制信息 AppendEntriesHandler
func (rf *Raft) AppendEntriesHandler(args *AppendEntriesArgs, reply *AppendEntriesReply) {
rf.mu.Lock()
defer rf.mu.Unlock()
// 传一个带有当前任期的结构体表示接收到了Leader的请求。
// 初始化响应的任期为当前任期
reply.Term = rf.currentTerm
// 老Leader重连后Follower不接受旧信号
if rf.currentTerm > args.Term {
return
}
// 收到Leader更高的任期时，更新自己的任期，转为 leader 的追随者
// 或者如果当前节点是候选者，则更新自己的任期，转为追随者
if rf.currentTerm < args.Term || (rf.currentTerm == args.Term && rf.role == Candidate) {
rf.ConvertToFollower(args.Term)
}
// 向 appendEntriesChan 发送一个空结构体，以表示接收到了领导者的请求
//rf.appendEntriesChan <- struct {}{}
// 发送心跳重置计时器或日志条目后
rf.appendEntriesChan <- AppendEntriesReply{Term: rf.currentTerm, Success: true}
if args.PrevLogIndex >= len(rf.logs) {
return
}
lastLog := rf.logs[args.PrevLogIndex]
// 最后的日志对不上 因此需要让Leader对该节点的nextIndex - 1
if args.PrevLogTerm != lastLog.Term {
return
}
reply.Success = true
//领导者尝试让跟随者追加的日志条目范围完全落在跟随者已知的已提交日志区间内，那就不需要再复制了
if args.PrevLogIndex+len(args.Entries) <= rf.commitIndex {
return
}
// 在PrevLogIndex处开始复制一份日志
rf.logs = append(rf.logs[:args.PrevLogIndex+1], args.Entries...)
// 更新commitIndex
rf.commitIndex = min(len(rf.logs)-1, args.LeaderCommit)
}
（1）
if args.PrevLogIndex >= len(rf.logs) {
return
}
在Raft算法中处理AppendEntries RPC请求的逻辑里，它用来检查跟随者（Follower）接收到的来自领导者（Leader）的心跳或日志复制请求中的前一个日志条目索引（PrevLogIndex）是否合理。具体分析如下：
参数解释:
args.PrevLogIndex: 旧的日志条目的索引，是上次同步的最后一条日志的索引。这是领导者在发送AppendEntries请求时携带的参数，表示跟随者应该在其日志中查找的前一个日志条目的索引，以便进行日志匹配和连续性检查。领导者期望在这个索引位置的日志条目与它正尝试追加的日志条目之前是连续的。
len(rf.logs): 表示当前跟随者（处理这个RPC请求的节点）日志的条目数量。如果跟随者的日志为空，则这个值为0。
检查目的:
该检查是为了确保领导者请求的前一个日志条目索引没有超过跟随者当前日志的实际长度。如果args.PrevLogIndex大于跟随者日志的长度，这意味着领导者认为跟随者应该有一个比实际更长的日志，这通常是因为领导者和跟随者之间的日志出现了不一致，或者跟随者落后很多且领导者的信息过时。
返回处理:
当检测到args.PrevLogIndex > len(rf.logs)时，跟随者直接返回，不进一步处理这次AppendEntries请求。这是因为在这种情况下，继续处理没有意义：按照领导者提供的索引，跟随者找不到匹配的日志条目来验证接下来的日志条目是否可以正确追加。此时，跟随者通常会在响应中设置success = false，并可能通过ConflictIndex或ConflictTerm等字段告知领导者具体的不匹配信息。
后续动作:
领导者收到这样的失败响应后，会根据跟随者的反馈调整其nextIndex值，然后重试发送AppendEntries请求，从一个更早的索引开始，以解决日志不一致的问题。这样，通过一系列的尝试与调整，Raft算法能够最终确保集群间日志的一致性。
因此，这一检查是Raft算法中处理日志不一致和确保日志复制正确性的重要环节，有助于维护分布式系统中数据的一致性和完整性。
**（2）**在Raft算法中，领导者（Leader）通过AppendEntries RPC向跟随者（Follower）发送心跳或日志条目时，会携带LeaderCommit字段，指示领导者已知的提交索引，即集群中大多数节点已经持久化的日志条目的最高索引。跟随者接收到这个信息后，会更新其本地的commitIndex，以反映集群的最新提交状态，而这个更新操作通常采用如下形式：
rf.commitIndex = min(len(rf.logs) - 1, args.LeaderCommit)
这里使用min()函数取最小值的原因在于确保两个关键条件得到满足：
不超出本地日志范围：len(rf.logs) - 1代表跟随者当前日志的最后一个索引。通过比较，确保commitIndex不会超过跟随者实际拥有的日志条目范围。这是因为跟随者不能提交不存在于其日志中的条目，即使领导者认为那些条目已被集群大多数成员提交。这是对日志完整性的保护，避免了“未来日志条目”的错误提交。
保持一致性：args.LeaderCommit是领导者告知的已提交日志的最高索引。跟随者需要确保自己的commitIndex至少达到这个值，以保证整个集群的一致性。如果跟随者的日志足够新，能够包含领导者所提交的所有日志条目，那么跟随者的commitIndex就应该更新为args.LeaderCommit，以反映集群的最新一致状态。
综合以上两点，min()函数在这里的作用是平衡了跟随者日志的实际情况与集群的提交进度，既避免了因领导者信息超前而导致的日志不匹配问题，又确保了跟随者能够尽可能地跟上集群的提交状态，保证了Raft算法的一致性原则。
（3）
if args.PrevLogIndex + len(args.Entries) <= rf.commitIndex {
return
}
这段代码出现在Raft算法中跟随者（Follower）节点处理来自领导者（Leader）的AppendEntries RPC请求的逻辑中。它的目的是为了确保领导者尝试提交的日志条目区间不会与跟随者当前已知的提交日志索引冲突或逆序。具体分析如下：
参数解释:
args.PrevLogIndex: 这是领导者在AppendEntries请求中携带的参数，表示跟随者日志中紧邻新日志条目之前的一个条目的索引。领导者期望跟随者在此索引位置的日志条目之后追加新的条目。
len(args.Entries): 表示领导者尝试追加到跟随者日志中的日志条目数量。
rf.commitIndex: 跟随者当前已知的提交日志的最高索引，即跟随者已经持久化并被集群中大多数节点确认的日志条目。
逻辑解释:
当args.PrevLogIndex + len(args.Entries) <= rf.commitIndex时，意味着领导者尝试让跟随者追加的日志条目范围完全落在跟随者已知的已提交日志区间内。这在正常情况下不应该发生，因为领导者应当总是尝试追加在其已知提交日志之后的新日志，或者是修复不一致的日志。
为何返回:
如果上述条件成立，这可能意味着一种逻辑错误或日志的严重不一致。为了避免潜在的混乱和数据损坏，跟随者选择直接拒绝此次AppendEntries请求，不进行任何日志追加操作。这可以视为一种防御性编程措施，旨在维护日志的一致性和集群状态的正确性。
潜在原因:
这种情况可能是由于网络延迟、消息乱序、或是领导者状态机的逻辑错误导致的。例如，领导者可能基于过时的信息发出了这个请求，或者领导者和跟随者之间存在严重的日志不一致，需要通过更复杂的日志匹配和修复流程来解决。
5、发起投票函数sendAllRequestVote
// sendAllRequestVote 向所有其他 Raft 节点发送请求投票的 RPC。
// 该函数首先构建 RequestVoteArgs，然后向所有其他节点并行发送请求投票的 RPC。
func (rf *Raft) sendAllRequestVote() {
rf.mu.Lock()
defer rf.mu.Unlock()
// 取出自己的已知的已提交的最后一条日志条目。不能直接取最后一条，因为commitIndex是大多数节点
// 都已经提交了的，是安全的索引。
// 看解释
lastLog := rf.logs[rf.commitIndex]
// 构建请求投票的参数
args := &RequestVoteArgs{
Term: rf.currentTerm, // 当前任期
CandidateId: rf.me, // 候选人 ID
LastLogIndex: lastLog.Index, // 候选人记录的最后一个已提交的日志条目的索引
LastLogTerm: lastLog.Term, // 候选人记录的最后一个已提交的日志条目的任期
}
// 向所有其他节点发送请求投票的 RPC
for i := range rf.peers {
// 对于非当前节点的其他节点发送，并且本身为候选者状态
if i != rf.me && rf.role == Candidate {
// 并行发送请求投票的 RPC
go func(id int) {
// 接收返回参数
ret := &RequestVoteReply{
Term: 0,
VoteGranted: false,
}
rf.sendRequestVote(id, args, ret)
}(i)
}
}
}
在Raft算法中，当一个节点转变为候选人（Candidate）并发起投票请求时，它向其他节点发送请求投票（RequestVote）的RPC，这个请求包含了候选人的信息以及它最后已知的提交日志条目的索引和任期号。候选人选择在投票请求中包含已提交的最后一条日志而不是其日志的最后一条，原因在于以下几个方面：
确保安全性：Raft强调安全性优先于可用性。使用已提交的日志条目作为竞选依据，可以确保如果该候选人赢得选举并成为领导者，它所提议的日志至少包含了集群中大多数节点已经同意的内容。这样，即使候选人的日志末尾有未提交的条目，也不会因为这部分日志的不确定性而影响集群状态的一致性。
促进日志匹配：在Raft中，日志匹配是确保数据一致性的关键。候选者提供已提交日志而非最新日志，可以帮助解决日志不一致问题。如果候选者使用其未提交的日志作为竞选依据，可能会导致选举出一个包含其他节点未见过的日志条目的领导者，进而引发更多的日志冲突和需要解决的不一致问题。
简化日志匹配逻辑：使用已提交日志简化了跟随者判断是否投票给候选者的过程。跟随者只需比较自己已知的提交日志的任期和索引与候选者提供的信息，如果候选者的日志至少一样新（即任期相同或更大，且索引不小于跟随者已知的最大已提交索引），跟随者就更倾向于投票给它。这样可以减少因日志不一致导致的投票拒绝，加速选举过程。
避免潜在的分叉：如果候选者使用自己未提交的日志作为竞选标准，当选后可能会尝试提交这部分日志，而这些日志可能并未在集群中大多数节点上达成一致，从而造成日志分叉，影响数据一致性。使用已提交日志作为基准，可以减少这种情况的发生。
综上所述，候选者在发起投票时选择包含其已知的已提交的最后一条日志条目而非其日志的最后一条，是出于增强系统安全性、促进日志匹配、简化决策逻辑以及避免日志分叉的考虑，这些都是为了确保Raft算法在分布式环境下的稳定性和一致性。
结果：
这里多运行了两个测试，但是总体时间还是在60秒以上。
PS E:\GoLangProgram\code\xun-go\com\xun\Mit-6.824-xun\src\raft> go test -run 2B
Test (2B): basic agreement ...
... Passed -- 2.1 3 36 9986 3
Test (2B): RPC byte count ...
... Passed -- 6.1 3 110 131280 11
Test (2B): test progressive failure of followers ...
... Passed -- 6.1 3 120 29196 3
Test (2B): test failure of leaders ...
... Passed -- 7.6 3 230 54502 3
Test (2B): agreement after follower reconnects ...
... Passed -- 8.7 3 158 42723 8
Test (2B): no agreement if too many followers disconnect ...
... Passed -- 4.6 5 188 44898 3
Test (2B): concurrent Start()s ...
... Passed -- 1.2 3 20 5486 6
Test (2B): rejoin of partitioned leader ...
... Passed -- 8.2 3 222 56958 4
Test (2B): leader backs up quickly over incorrect follower logs ...
... Passed -- 67.9 5 4828 4299403 107
Test (2B): RPC counts aren't too high ...
... Passed -- 2.7 3 46 13068 12
PASS
ok 6.824/raft 115.223s
此时lab2A还是成功的：
我的代码实现（附带详细代码注释）
直达gitee链接
https://gitee.com/zhou-xiujun/xun-go/tree/master/com/xun/Mit-6.824-xun
相关链接
标签：...,--,领导者,条目,跟随者,rf,2B,分布式系统,日志 From： https://blog.csdn.net/weixin_44615954/article/details/140232252