Hexo

6.824 lab2A思考

Posted on Edited on In
Symbols count in article: 3k Reading time ≈ 3 mins.

Raft2A

本文进行简短的6.824中lab2的简单实现梳理，以及对应的注意事项

实现目标

image-20250723155619423

lab2A中需要实现的基础目标为以下几点:

  • 实现基础的选举行为，需要能在无网络故障下选举出一个Leader，也需要在网络不可靠环境下成功选举并且能够在Leader死亡时重新选举出一个Leader
  • 实现基础的心跳行为，需要Leader能够维护其的基本心跳行为，能够维护其的Leader的地位

Election

​ 选举操作是一个由基础的相互投票行为组成的，具体的RPC定义在论文的Figure2有详细的解释，如下

image-20250723155931141

​ 其中，我们本次lab2A中需要实现的是基础的投票行为，即不存在日志的投票参数，但是，为了后续的可扩展性，我们需要将对应的日志信息一并管理，否则会导致后续需要实现时会出现Review地狱。

​ 关于election的实现，我们需要分为俩个方面来考虑，一方面是接收方，一方是发起方，更清晰的，一方是收到一个服务器的投票请求的情况，另外一方是发起投票请求的。在实际的代码实现中，抽象出来实际上就是RPC的客户端(发起方)和服务器方(接受方)的俩个处理实现。我们可以隔离出来分析实现。

接收方

​ 对于Election的投票来说，其接收方的结果只有俩种，无非是投或者不投。表现在RPC中，即是最终的Result中的voteGranted为true/false。但是这样分析时无趣的，我们需要关注实际的场景，即论文中分析到的，来详细列出实际的什么参数的状态会导致true，什么的参数情况会导致false。在这个过程中，我们势必需要牵扯到接收端和发送方上的各自状态，该系列状态在Figure2中也存在详细的介绍，如下

image-20250723161100200

投票规则

下面给出关于投票逻辑的部分分析，其中大多是关于论文5.2 Leader election,5.4中的一些总结

  • at most one candidate in a given term

​ 只投一票原则，在一个Term(任期)中，一个接收方至多将其的选票投给一个RequestVote RPC

  • first-come-first-served basis

​ 先到先得原则，在一个Term(任期)中，一个接收方总是会优先投给首个到来的RequestVote RPC

  • returns to follower state whenever needed

​ 在任何时候，只要需要，一个候选者接收方都应该回退为Follower，具体的，在投票阶段，如果其收到一个来自一个合法的 Leader的AppendEntries RPC，那么无论当前选举进度如何，其需要立刻放弃选举并且更新本身的状态并跟上该Leader

  • update status whenever needed

​ 在任何时候，只要需要，无论当前服务器处于什么状态，其都需要回退为Follower

  • no Leader state globally

​ 对于一次选举，算法不必保证其一定会选出一个Leader，系统中可以存在实际上不存在Leader的Term状态，但需要保证该种状态不 会频繁出现。具体的，通过随机化选举超时时间来实现

  • more up-to-date guide

​ 最新者当选原则，算法需要保证系统具有一定的FT，不能在一个服务崩溃后数据丢失的过于严重，因此需要使用up-to-date判断当 前的候选者中的具有最多上次任期中的信息的当选Leader，具体的可以参考5.4的分析。至于more up-to-date的判断，其在5.4一节 中也有分析

发送方

​ 一个发送方是一个选举操作的状态起始点，一系列的选举行为都要基于一个发送方开启一轮属于其的选举周期的动作。表现在RPC中，即是一个服务器通过一系列逻辑启动一轮RPC发送请求接收方投票。我们此处需要来分析整个基础流程，即一个发送方需要什么时候触发选举，触发之后需要进行什么行为完成选举，完成一轮选举之后的行为

选举要求

  • one election one term

​ 在Raft中，一次选举是基于一个Term(任期)的，一个服务器每发起一次选举，需要更新其的任期及一些附带的状态，其才有资格开 启一次选举

  • limited election time

​ 为了保证系统具有一定的FT，一次选举流程不能持久存在，若一次选举使用了过多时间，Raft中要求终止这次选举，避免一些麻烦的 错误条件发送

  • call elections whenever possible

​ 只要可能，Raft中的服务器都会发起选举，具体的，包括上一次选举初次停止，定时器到期等等，其在论文中有完整的描述

  • stop elections whenever possible

​ 只要需要，一个服务器就会停止当前的选举，其可能是收到一个Leader的心跳或者前文提到的选举超时等

  • become a leader whenever possible

​ 只要可能，一个服务器就会尝试成为系统中的Leader，在Raft中，只有一种情况可以成为Leader，即在一次选举流程中收到了超过 半数的投票

为了实现上述几个要求，在Raft中，还要求了几个额外的机制来辅助完成

  • random election timeout

​ 随机化选举超时时间，通过随机化超时时间，使得每个Leader可以错峰开启一次Election，使得non-Leader状态不会在系统中频繁 出现

  • send a heartbeat immediately when first become Leader in one term

    一个服务器成为Leader之后，其需要立刻发送一次广播心跳，用来压制其他的服务器成为Leader来维护唯一Leader状态

项目结构

为了能够较好的完成本lab，我们在开始实现之前需要注意一件事，就是本次lab中我们需要如何管理我们的代码实现，全部耦合在一个raft.go中是难以接受的，后续的review是非常麻烦的，由于后续的lab2剩余部分甚至于lab3等都需要使用到该文件，所以我们必须以一种较为优雅的方法来维护本项目，把其按照一种较为优雅以及可维护的方法进行拆分。

  • small and complete

​ 关于实现代码的拆分，我们考虑每个文件中的内容应当小而完整，一个选举操作会涉及到接收方和发送方的操作，那么关于接受方和 发起方的election，我们就需要拆开来实现。在我个人的构想中，可以使用一个文件来承接RPC的发起方的实现，一个文件来承接 RPC发送方的实现。

​ 实际上，借用本人关于C++中使用grpc的经验来看，倾向与将客户端的逻辑和服务器端的逻辑分开实现，使得各自独立维护。同时， 存在一个额外的文件储存类似的RPC定义，就类似于grpc中的protoc文件

  • high cohesion

​ 一个代码实现文件应该尽可能只依赖于本文件中的内容，不需要经常跳转别的文件中查找，当然，在本次lab中，关于raft.go没有办 法，势必会大量涉及到关于其他文件的使用，这个无可厚非

综上，个人倾向于将项目结构划分为以下几个大块

  • rpc.go

​ 储存本项目中使用到的RPC定义

  • request_vote.go

​ 储存本项目中投票的RPC的服务器端实现

  • leader_election.go

    储存本项目中投票的RPC客户端实现

  • raft.go

​ 整合整个lab逻辑的实现

后续可能存在日志推送等的逻辑实现，但是大多与此类大差不差，在这骨架之上适当补充文件即可

-------------本文结束 感谢阅读-------------