MIT 6.824: Distributed Systems- 实现Raft Lab2A

MIT 6.824: Distributed Systems是麻省理工大学的研究生公开课,主讲分布式系统。

该课程一共包含Lab1-4共4个大作业,Lab1是实现Mapreduce原型,Lab2-4是实现Raft以及基于Raft实现分布式KV存储。

我正在实现Lab2,也就是Raft核心算法,它被划分成了Lab2A、Lab2B、Lab2C三个子任务:

  • Lab2A:实现leader election、heartbeat。
  • Lab2B:实现Log replication。
  • Lab2C:实现state persistent。

这个拆解符合Raft算法的描述,也就是选主、日志同步、状态存储,是可以分开实现的,最终凑出一个完整的Raft实现。

学习资料

以MIT课程教案与视频为主:

中英文对照学习Raft论文:

实现Raft的时候基本就盯着Figure2的图片即可:

Lab2A实现

因为课程分为Lab2A、Lab2B、Lab2C,为了能留住每个子任务的代码状态,我决定把每个子Lab的代码实现贴到博客上,方便拆分回看,我不会讲解代码细节。

下面是我的Lab2A实现,已经通过了课程的单元测试:

结构体定义

Make 程序入口

GetState(单元测试会调用)

RequestVote相关

AppendEnties(仅心跳)

总结Lab2A

  • 一把大锁保护好状态,RPC期间释放锁,RPC结束后注意状态二次判定
  • request/response都要先判断term > currentTerm,转换follower
  • 一个currentTerm只能voteFor其他节点1次
  • 注意candidates请求vote的时间随机性
  • 注意requestVote得到大多数投票后立即结束等待剩余RPC
  • 注意成为leader后尽快appendEntries心跳,否则其他节点又会成为candidates
  • 注意几个刷新选举超时时间的逻辑点

其他了解:

  • 虽然Lab2A不要求关注persist状态的落地(currentTerm,voteFor,[]log),但是我稍微扫了一眼代码,发现它的persist其实还是写在内存里,供单元测试去check结果,因此猜测这门课可能不会真的实现raft如何持久化log这个存储部分(从目前来看的确是这样的)。

如果文章帮助您解决了工作难题,您可以帮我点击屏幕上的任意广告,或者赞助少量费用来支持我的持续创作,谢谢~

MIT 6.824: Distributed Systems- 实现Raft Lab2A》有9个想法

  1. Pingback引用通告: MIT 6.824: Distributed Systems- 实现Raft Lab2B | 鱼儿的博客

  2. 路人2021

    你好我想請教一下, 為何在 appendEntriesLoop() 這個 function 裡面我們不需要在 78行 之前 Unlock()?

    因為,我看到你在 electionLoop() 這個 function 裡面, 有實現提前 Unlock 這功能。

    而且,你在最後的總結裡提到我們應該要在RPC期間釋放鎖,照這樣說的話我們在 appendEntriesLoop() 這個 function 裡面實行傳送RPC功能之前應該也要先 Unlock() 對吧?

    回复
    1. yuer 文章作者

      RPC期间不能lock,否则性能就不行了。

      既然不能悲观锁,那就只能活锁,也就是RPC完成后lock住做state的再次检查,确保还是之前的状态。

      回复
  3. 匿名

    您好,我有个问题想请教。我们在做leader选举的时候,各个节点应该是分布在一段时间区域内的不同时间点开始选举。那么为什么在make函数里,我们需要 go electionLoop()呢?这点我有点想不明白,能解答一二吗?

    回复
    1. yuer 文章作者

      因为随时都可能网络分区,然后其他小团伙就选出新leader,然后网络分区恢复,然后你收到新leader的心跳,然后你臣服为follower,然后又网络分区了,你发现收不到leader心跳了,于是自告奋勇宣告相当leader让大家投票,所以electionLoop一定是要持续监测的呀。

      回复
  4. 匿名

    在选举投票的阶段是不是假设机器不会崩溃,以及rpc的往返时间要小于投票的超时时间,要不然会一直卡在for{}这个循环里面吧

    回复

发表评论

您的电子邮箱地址不会被公开。