漆昼中温柔的不像话

静守着他的遗憾啊

旧的摇椅吱吱呀呀停不下

风卷走了满院的落叶落花

——暮色回响

完整代码见： https://github.com/SnowLegend-star/6.824

在完成Lab之前，务必把论文多读几遍，力求完全理解Leader选举、log日志等过程。

Part 3A: leader election (moderate)

先分析实验说明中的hints：

1. 你不能轻易直接运行你的 Raft 实现；相反，你应该通过测试程序运行它，即 go test -run 3A。
2. 按照论文的图 2。在此时，你需要关心发送和接收 RequestVote RPC、与选举相关的服务器规则以及与领导者选举相关的状态。
3. 将图 2 中与领导者选举相关的状态添加到 raft.go 中的 Raft 结构体中。你还需要定义一个结构体来保存每个日志条目的信息。

日志除了content，还有别的信息吗？怎么还要单独设置一个结构体

1. 填写 RequestVoteArgs 和 RequestVoteReply 结构体。修改 Make() 以创建一个后台 goroutine，当它有一段时间没有听到其他节点的消息时，会定期启动领导者选举，发送 RequestVote RPC。实现 RequestVote() RPC 处理程序，使得服务器互相投票。

在 Raft 协议中，当候选人 A 给追随者 B 发送请求投票（RequestVote）时，主要有两个步骤来决定追随者 B 是否会投票给候选人 A：

1、比较任期（Term）：

如果候选人 A 的任期（term = 5）大于追随者 B 的当前任期（currentTerm = 4），那么追随者 B 会更新它的当前任期为 5，并考虑是否投票给候选人 A。

如果候选人 A 的任期小于或等于追随者 B 的当前任期，追随者 B 将拒绝投票给候选人 A。

2、比较日志条目（lastLogIndex 和 lastLogTerm）：

即使候选人 A 的任期更大，追随者 B 仍然会检查候选人 A 的日志是否比自己更新。

追随者 B 会比较候选人 A 的 lastLogTerm 和自己的 lastLogTerm。

如果候选人 A 的 lastLogTerm 大于或等于追随者 B 的 lastLogTerm，则继续比较 lastLogIndex。

如果候选人 A 的 lastLogTerm 更大，则追随者 B 认为候选人 A 的日志更新。

如果 lastLogTerm 相等，则比较 lastLogIndex，lastLogIndex 更大表示日志更“新”。

不可能出现 lastLogTerm 更小但 lastLogIndex 更大的情况。

处理重复的投票请求：1、follower投票了但是因为网络延迟candidate没收到，Candidate会再次发送投票请求，follower会再次回复。如果直接判断follower的voteGranted状态，则candidate可能收到两次follower的回复，导致错误的votecount。可以为每次投票设置一个唯一标识符。

2、follower的投票直接丢失了，

1. 为了实现心跳，定义一个 AppendEntries RPC 结构体（尽管你可能不需要所有参数），并使领导者定期发送它们。编写一个 AppendEntries RPC 处理方法。
2. 测试程序要求领导者每秒最多发送 10 次心跳 RPC。 测试程序要求在旧领导者失败后 5 秒内选出新领导者（如果大多数节点仍能通信）。

每100ms给所有Follower发送一次心跳信息。

1. 论文第 5.2 节提到选举超时范围为 150 到 300 毫秒。这样的范围只有在领导者发送心跳频率远高于每 150 毫秒一次（例如每 10 毫秒一次）时才有意义。由于测试程序限制你每秒发送十次心跳，你将不得不使用比论文中的 150 到 300 毫秒更大的选举超时，但不要太大，因为那样你可能无法在 5 秒内选出领导者。

100毫秒发送一次心跳。那选举超时就设置为600?

1. 你可能会发现 Go 的 rand 有用。

可以用来设置随机超时时间，也可以用来为每个操作生成唯一的序列号

1. 你需要编写定期或延迟采取行动的代码。最简单的方法是创建一个带有 time.Sleep() 循环的 goroutine；请参阅 Make() 创建的 ticker() goroutine。不要使用 Go 的 time.Timer 或 time.Ticker，它们难以正确使用。
2. 如果你的代码在通过测试时遇到困难，请再次阅读图 2；领导者选举的完整逻辑分布在图的多个部分。
3. 不要忘记实现 GetState()。
4. 当测试程序永久关闭一个实例时，它会调用你的 Raft 的 rf.Kill()。你可以通过 rf.killed() 检查是否已调用 Kill()。你可能想在所有循环中这样做，以避免死掉的 Raft 实例打印混淆信息。

PartA不涉及Server的kill的问题。

1. Go RPC 只发送名称以大写字母开头的结构字段。子结构体也必须具有大写字母开头的字段（例如日志记录数组中的字段）。labgob 包会警告你这点；不要忽视这些警告。 这个实验最具挑战性的部分可能是调试。

这个warning还是比较友好的。要是没这个warning又要找半天原因看是什么导致rpc调用失败。

 

1. 花点时间使你的实现易于调试。编写打印信息以调试日志条目传播和提交的每个阶段。利用测试程序提供的日志记录功能。避免竞争条件并发。考虑为每个 goroutine 编写小型测试。

Hints其实是不难理解的，真正有点恶心的是goroutine的处理方式。写完大致框架后我就开始找bug了。开始还以为自己的选举逻辑有问题，看了几天都没发现什么问题。遂准备debug。其实我一直是抗拒对多线程debug的，总感觉调试不了，也没有去深入研究过。折腾了好久仍然调试无果，一看报错好像是多线程的异步执行导致debug终止。去群里问了下才发现尽量不要对多线程问题进行调试几乎是共识，打印log才是王道。可恶的是我看完第一节课就直接开始着手partA了，完全不知道后面TA提供了打印log的妙计。现在都快完成了再继续看课实在是没心情看下去，还是呼哧呼哧用printf大法吧。

记得给成员函数加锁，不然会发生data race。如果不是很确定就直接加把大锁保平安~

 

然后就是巨恶心的goroutine处理。对于RequestVote RPC和AppendEntries RPC，一定要记得使用goroutine，否则等处理完一个Follower的投票在继续处理下一个Follower很容易导致选举超时。

 

可以看到我的RequestVote RPC中有个死循环，如果某个Follower没能处理Candidate的投票请求，就不断尝试直到该RequestVote RPC成功调用。最初我就是没使用goroutine，导致选举总是失败。

 

使用了goroutine后，就要注意到异步执行可能带来的问题了。下面这种写法大概率会导致票数统计有问题，除非给RequestVoteReply加上FollowerId这个字段保证选票的唯一性。涉及处理goroutine执行得到的reply，还是要在相应的goroutine函数体内部处理，切不可出现下列这种情况。

 最后修改了无数遍代码后，终于是看到了“PASS”，看得我不由得大吼一声。Damn！改了好几天该死的代码，道心几近破碎，终于是拿下了。

考虑到后续代码都是基于PartA的，一定要测试许多遍确保万无一失才行。

 

关于Leader、Follower、Candidate何时更新自己的Term的问题

1. Leader：如果 Leader 收到一个带有更高 term 的 RPC，它会更新自己的 term 并退化为 Follower。
2. Candidate：如果 Candidate 收到一个带有更高 term 的 RPC，它会更新自己的 term 并退化为 Follower。
3. Follower：当 Follower 收到 RequestVote RPC 时，如果 Candidate 的 term 大于 Follower 的当前 term，Follower 会更新自己的 term，并将自己转变为 Follower（如果之前不是 Follower）。

如果两个Candidate平票，当做未选出Leader正常处理。

Follower的返回term问题

1. 在Raft协议中，如果一个Follower的当前任期（term）为1，而接收到了一个Leader发送的消息，该Leader的任期为2，根据Raft的规则，Follower会首先比较自己的任期与Leader的任期。

由于Leader的任期（2）高于Follower的任期（1），Follower会更新自己的任期为2，以匹配Leader的任期。

接着，Follower会根据Leader的指令进行相应的操作，如更新日志条目等。在这种情况下，当Follower回复Leader时，其回复中的reply.FollowerTerm应当是2，因为它已经更新了自己的任期来匹配Leader的任期。

一个问题：当Candidate选举失败的时候要不要令它回退到Follower状态呢？当然是可以完成这个实现的，问题是我发现忽略这个实现也没啥问题。

以下论述基于忽略Candidate选举失败时的状态回退。

当Candidate serverId选举失败后，如果我们选择不回退它的状态，那它就会一直以Candidate的身份存在，直到收到了Leader发来的heartbeat才会重置状态。在这种情况下，RequestVote()中就不可以加上是否Follower的判断了。

再来论述RequestVote()中上面这个判断存在的必要性(后文以上述判断代称)。对于首先假设集群处于Term X中，Leader正常发送heartbeat来维护统治。现在Leader挂了，需要选出一个新的Leader。如果只有一个Server率先发生timeout，那它可以顺理成章的当选为新Leader，这种情况没涉及Candidate的状态回退。

假如有两个Server A、B同时达到了timeout，那么A、B就会同时进行选举，此时Term=X+1。

1. A、B得到的选票不同(设A得票更多)，那么在Term=X+1轮选举完成。A向所有Server发送heartbeat，每个Server的状态都被重置被Follower，与投票先关的属性也都重置。直到下一次选举开始之前，除了A以外的所有Server都是Follower状态，故上述判断可以忽略。
2. A、B平票，那在Term=X+1轮的选举失败了。那么在Term=X+2时会出现新的Candidate C(C可能是包括A、B在内的某个Server)。C在向A、B发起投票请求时，尽管A、B在Term=X+1时的投票状态仍然保留，但是它们发现C的Term更大，所以会重置自己的voteFor状态，给C投票。如果此时加了上述判断，那A、B就无法进行投票，这是不符合预期的。
3. 多个服务器平票的情况类似，故不再赘述。

综上，上述判断是可以去掉的，也可以推出Candidate选举失败的时候没必要令它回退到Follower状态，并不会影响选举的进行。

goroutine和线程的辨析

分布式系统涉及了大量goroutine和锁的操作，最近我是越看越昏头，索性沉下心来研究了下goroutine的性质。这一看不知道，直接引出了我对线程并发执行的疑惑，现在就来好好辨析一下两者到底有什么区别。

还记得在学习CSAPP的时候，我对线程的理解如下：对于某个线程函数，所有线程都会共享这个线程里面的局部变量。

就拿这张PPT来说，我最初以为之所以会产生RACE，是因为main函数创建的若干个线程都会共享thread()内部的myid这个变量，导致这个变量不断被新的i覆盖。我记得上个月我还对race产生了新的疑问来着

 

当时我的思考是：既然线程是共享thread()内部的所有变量，那只要下列语句执行得够快同时thread()自身的执行速度够慢，那岂不是新的线程传进来的i又会覆盖还没来得及执行的myid？

当时我还去问了问GPT到底怎么回事。可惜3.5版本的GPT终究是不够强大，还是被我绕进去了。

直到这次，我终于是大彻大悟了。先来看这段内容：

共享内容

1. 全局变量：所有线程都可以访问和修改全局变量。这些变量在程序的全局地址空间中定义，对所有线程可见。
2. 静态变量：静态变量在程序的全局地址空间中定义，因此它们对所有线程都是可见的。
3. 堆内存：通过 malloc、calloc、realloc 等函数动态分配的内存块在所有线程之间共享。任何线程都可以访问和修改这些内存块。
4. 文件描述符和网络连接：线程共享打开的文件描述符和网络连接，这些资源是进程级别的。

不共享内容

1. 线程栈内存：每个线程都有自己的栈空间，这意味着每个线程的局部变量、函数调用栈和函数参数都是线程私有的，不会被其他线程直接访问或修改。
2. 函数局部变量：在函数内定义的局部变量存储在该线程的栈帧中，因此每个线程的局部变量是独立的。

刚才ppt中的代码之所以会产生race现象，是因为在我们创建线程时，所有线程都接收到同一个 int 变量的地址 &i。由于这个地址在所有线程中都是相同的，因此每个线程实际上都在访问和修改相同的内存位置。

也就是说如果线程执行得较慢，例如i=1即将等于时但是thread0还没开始执行，现在i=1了，thread0期望得到的myid=0就永远丢失了。举一个更极端的例子，我们令i=9999，但是thread0~thread9999都因为某种情况没开始执行。现在i=10000了，thread0~thread9999存储的myid都会变成10000。

通过为每个线程分配自己独立的 id 值，这些值被存储在不同的内存位置上。线程访问的是自己创建时分配的内存区域，避免了对共享内存的竞态条件。

Goroutine和线程类似。但是要注意一点，匿名线程创建时会默认共享主函数体的变量。所以下列代码也存在RACE现象。解决的方法是向匿名线程传入变量i，这样每个匿名线程都会有属于自己的局部变量，故不会发生RACE现象。