Albert's Blog
所有文章 标签 分类 Wiki 收藏夹 关于
Albert's Blog

学习分布式一致性协议：自己实现一个 Raft 算法

本文由 简悦 SimpRead 转码， 原文地址 zhuanlan.zhihu.com

前言

MIT6.824 是麻省理工学院开设的一个很棒的分布式系统公开课程，课程的 Schedule 在这里 ，这门课程的学习方式主要是通过教授的 lecture 讲解、Paper 阅读、FAQ 答疑，以及实践 lab 来完成的，是一个学习理论知识，然后动手实践的过程，个人认为是很好的学习方式，而 MIT6.824 公开课让更多不是麻省理工的学生也能很好的学习分布式系统知识，免费学习 MIT 课程学到就是赚到！

MIT6.824 主要围绕以下 4 个 lab 进行学习

  • lab1->MapReduce：实现一个 MapReduce 系统，其是一个具有 Map 和 Reduce 功能的分布式计算系统
  • lab2->Raft：实现 Raft 算法，其是一个分布式一致性协议，分为以下 3 个部分
  • 2A：Leader 选举
  • 2B：日志复制
  • 2C：持久化数据
  • lab3-> 分布式容错的 Key/Value 存储服务：搭建一个容错的 Key-Value 分布式服务，其是建立在 lab2-Raft 的一个上层建筑，需要在 lab2 的基础上实现日志快照等功能，对外可以提供 K-V 存储服务
  • lab4->Shared Key/Value 服务：一个分片的存储服务

而本篇文章讨论的是如何学习 lab2 的部分，也就是实现一个 Raft 算法，本文会指出学习方式，以及你需要做到的一些要点、常见的坑、资料等等。你可以将本文作为一个 lab2 的 Guide 来进行阅读。 如果读者对其他 lab 有兴趣，也可以参照本文差不多的方式进行其他 lab 的学习。

首先放一张 lab2A、2B、3C 的 3pass 图（做完还是有满满的成就感的）

https://pic4.zhimg.com/v2-08b10ca071a6c1d15758576590401bf7_r.jpg

前段时间花了一周左右的时间动手写代码完成了 MIT6.824 课程中的 lab2，达到 bug-free 属实不易，在做的过程中踩过许多坑，发现做 lab 的时候交流、沟通代码中的一些问题很重要，交流会开拓了我们的思路、解决方法，如果没人交流，就比较容易出现一个疑难杂症会卡好几个小时甚至几天的情况，比较容易产生气馁、想放弃的情绪，我在做 lab2C 部分的最后一个具有挑战性的 unreliable test 的时候有一个 bug 硬找了快两天，中途有几次想过放弃，但意志力和对技术的热情驱使我不能将就，所以坚持下来，最终会找到解决方法的思路的。

学习 MIT6.824 课程，我们不像 MIT 学生那样，学生之间可以进行讨论，有问题可以询问助教、教授，我们在做的时候只是一个人，你最多可以找到 MIT6.824 的交流群，但群里真正能帮助你解决一些问题的人不多，最终靠自己的比重还是比较大的，所以一些学习资料就显得比较重要，这也是本文创作的初衷，想让更多人学习到 MIT6.824 这门课程，学习 Raft 算法不止是阅读 paper 和一些理论知识，没有什么比直接实现一个 Raft 还能够深刻学习分布式一致性协议的了。其次自己实现一个 Raft，想想就很有意思。

学习 lab2，我希望至少需要有 CAP 和分布式一致性相关知识基础，起码要了解他们，知道 Raft 是干嘛用的，为什么需要使用 Raft。这里推荐自己的一篇文章，从 CAP 理论延伸来讲讲分布式一致性

林林林：从 CAP 理论到分布式一致性协议

1. Lab 前的预备工作

1.1 如何检验 Raft 算法的正确性

感觉这个是大多数人首先都比较关心的问题，这个 Raft 算法做出来之后我怎么知道它能 work 呢？lab 中首先会给你一个代码大致骨架，骨架中附带了很多单元测试可以测试你的代码的正确性，所以按照一定规则去实现你的算法之后 run 一遍单元测试就行了。

1.2 编程语言

MIT6.824 中 lab 使用的语言均为 Go 语言，不会 Go 语言的同学不要就这么打退堂鼓了，我在做 lab 之前也不会 Go 语言，但这个语言简单高效，如果有 Java 或者 C++ 的基础的话上手会非常快，实际做 lab 的话只用到了少数并发的 Go 库函数，所以库函数的学习成本也不会特别高，Go 的语法与 Java、C++ 类似，熟悉几天就能上手，关于 IDE 我个人使用的是 GoLand 30 天免费体验，也可以使用比较强大的 Vim -> vim 使用文档，用熟练之后效率不亚于 GoLand。

在 Go 中使用的一些特定的 Go 的库函数、一些比如定时器的做法在下面介绍 lab 的时候会具体涉猎

1.3 阅读论文

做 lab 之前，首当其冲的当然就是阅读 Paper

建议先读一遍 paper，大概了解了解 Raft 算法的具体构思，看不懂的先跳过，第一遍不求甚解，有个大致思想即可。

1.4 Lecture

此时你大致已经对 Raft 有一定的想法了，相当于预习了一遍课程，这时候就可以开始上课了，如果只做 lab2 的话，你需要关注以下几个 lecture：

  1. Lecture 5: Go, Threads, and Raft
  2. Lecture 6: Fault Tolerance: Raft (1)
  3. Lecture 7: Fault Tolerance: Raft (2)

其中第一个 lecture 讲的是在使用 Go 语言实现 Raft 时会出现的几个问题，有参考价值，第二个和第三个 lecture 讲的是 Raft 算法的一些细节，这几个 lecture 建议都要看，对实现 lab 有一定的帮助。

以下是我找到的有三个课程资源：

1.5 回顾论文

可以动手做 lab 之前我认为有一个指标就是你至少需要懂论文中的 Figure2 中的每一个字的意思，知道为什么这样子设计，Raft 算法由简单易懂著称，其只有两个 RPC 方法，一个是 AppendEntries 日志复制，一个是 RequestVote 请求投票，以及一系列的 Raft 属性都在 Figure2 中，同时有一系列 Follower、Candidate、Leader、AllServer 需要遵循的规则，理解这些规则并且做 lab 的时候一定要按照论文中的这些规则说的去做。

当你对某个 Figure2 中的规则产生疑惑，请多回顾多读几遍论文，这是做 lab 时 bug-free 的关键。做之前务必保证理解了 Figure2。

1.6 参考资料

最后总结几个参考资料，做 lab 时应该能帮到你：

2. 开始 lab2 实现 Raft

6.824 Home Page: Spring 2020

务必遵循 paper 中的 Figure2 的每条规则来实现你的 lab

现在就开始着手做 lab 了，进入课程主页，左边的导航中进入 lab2 ，开始动手之前务必保证读一遍教授说的话，以及仔细阅读每个 Task 下面的 Hint 提示（我做的时候进的是 2018 的网页，提示相当少，做完才发现有 2020 年的网页，提示变多了好几条）

2.1 Lab2A

首先是 2A，实现 Leader 选举，刚开始 2A 里的两个测试个人认为是最简单的，因为 leader 选举在下面的 2B、2C 都会迎来更大的挑战，如果你能 pass2A，并不能代表 Leader 选举的逻辑就一定 ok，也就是说在 2B、2C 中如果出现 BUG 还是有可能因为你的 Leader 选举逻辑有问题导致的。

下面就提几个要点帮助你快速上手实现 Raft

要点只会涉及一些 Raft 算法无关的东西，比如语言这块，初衷是希望算法之外的东西不要浪费大家太多时间，更多关注算法的实现

2.1.1 加锁建议

一个原则，不要考虑锁性能（锁的粒度）问题，我们更关注的是算法的正确性，有可能 data-race 的时候请毫不犹豫加上一把大锁

可见性与原子性

由于算法中很多地方都需要并发编程，比如 Candidate 发起投票请求 RPC，要同时给所有节点发送 RPC，此时就开多个 goroutine 进行 RPC，一旦涉及并发编程，就会有 data-race、数据可见性的问题，参照 Happen-before 原则，在所有有 data-race 的地方都加一把锁，为了可见性也为了原子性。

1
2
3
4
5
6

func (rf *Raft) GetState() (int, bool) {
    // 为了可见性
    rf.mu.Lock()
    defer rf.mu.Unlock()
    return rf.currentTerm, rf.state == Leader
}

这里获取节点中的当前 Term 和节点的 state 属性的时候加锁是为了可见性，currentTerm、state 这两个属性明显会有 data-race，所以这里一定注意可见性，不然 Agoroutine 修改了 currentTerm，Bgoroutine 调用上面的 GetState 方法有可能看不到最新的 currentTerm 值

同时有些方法需要加一把大锁，有些方法需要你读取 currentTerm，然后又要根据某个值去修改 currentTerm，请毫不犹豫加上一把大锁。

死锁

如何避免死锁？大部分死锁是由于锁获取顺序问题，比如有两把锁 X 和 Y，同时有两个线程 A 和 B，A 先获取 X 锁后再去请求 Y 锁，B 先获取 Y 锁后再去请求 X 锁造成死锁。这里锁获取顺序一个是先 X 后 Y，一个是先 Y 后 X，有这种锁获取顺序的时候务必注意死锁问题。

也就是说，我们避免锁上加锁的问题就可以避免死锁，所以一个原则，在 RPC 调用的时候不要持有锁，为什么呢？举一个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func (rf *Raft) TimeoutAndVote() {
  rf.mu.Lock()
  // 节点的选举计时器超时，开始发起选举投票RPC
  for i := 0; i < peersCount; i++ {
    go func(server int) {
      // 发送RPC投票请求
      rf.sendRequestVote(server, &request, reply)          
    }
  }
  rf.mu.Unlock()
}

func (rf *Raft) RequestVote(args *RequestVoteArgs, reply *RequestVoteReply) {
  rf.mu.Lock()
  // 节点收到请求投票RPC后的处理函数
  rf.mu.Unlock()
}

每一个节点都是不同的 Raft 实例，也就是说每个节点都是不同的锁，集群 3 个节点就总共有 3 把锁

假设集群两个节点 A 和 B，A、B 同时选举超时，发起选举投票，所以 A、B 同时进入 TimeoutAndVote 函数发起选举投票，A 获取了 A 锁，B 获取了 B 锁，此时 A 发送 RPC 给 B，进入 RequestVote 函数，需要获取到 B 锁，同时 B 发送 RPC 给 A，进入 RequestVote 函数，需要获取到 A 锁，锁获取顺序一个是先 A 后 B，一个是先 B 后 A，所以发生了死锁。

如果我在调用 RPC 之前释放了锁，然后 RPC 结束之后重新获取锁，这样的话就避免了锁上加锁的情况，没有了多锁场景自然就没有死锁问题。所以一个原则，调用 RPC 过程不要持有锁。个人在做 lab 的时候遵循这个原则死锁就不会出现。

死锁调试

为了死锁能方便调试，你可以选择性把加锁函数封装起来，打上日志

1
2
3
4
5
6
7
8
9

func (rf *Raft) lock(where string) {
  // DPrintf是src/raft/util.go的一个日志工具函数，通过修改其Debug值方便选择是否开启日志
  DPrintf("%s lock", where)
  rf.mu.Lock()
}
func (rf *Raft) unlock(where string) {
  DPrintf("%s unlock", where)
  rf.mu.Lock()
}

当然我是没用到这种技巧，如果你遵循上面原则，并且在 Lock 的地方都记得 Unlock 了，基本不会有死锁（我在做的时候死锁都是出现在忘记 unlock 上了。。。）如果打上日志，在程序死锁的时候会比较方便排查问题

2.1.2 定时器实现

节点有一段时间收不到 Leader 的心跳或 AE（AppendEntries，下文称 AE）的时候，就会变为 Candidate 并发起投票选举，这是 2A 中需要实现的，实现这个功能就需要一个定时器，那么你可以这样做：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 设置一个时间值
const CandidateDurationMin = time.Duration(time.Millisecond * 200)
// 初始化定时器
rf.electionTimer = time.NewTimer(CandidateDuration)

// 另外开一个线程进行不断循环
for !rf.isKilled {

  // 阻塞
  <-rf.electionTimer.C
  // timeout之后往下走

  if rf.isKilled {
    break
  }

  // here 2A...
  // 重新倒计时
  rf.electionTimer.Reset(time.Duration(CandidateDuration))
}

timer 的实现是依靠 Go 中的 channel 管道来做的，可以理解为一个阻塞队列，等你设置的 timeout 之后就会往阻塞队列里面放值， <-rf.electionTimer.C 这行代码在 timeout 之前会被阻塞，这样就实现了定时器的功能。在收到心跳或者 AE 的时候就像最后一行调用 Reset 函数那样重置定时器，这样就能保证 Follower 收到 RPC 就永远不会发起一个投票选举。若想马上开始走定时器逻辑：

1

rf.electionTimer.Reset(time.Duration(0))

2.1.3 等待 RPC 建议

一个节点变为 Candidate 后，会发起投票选举，向其余所有节点发送 RPC，此时若获取到大多数选票（3 个节点就只需要获取到 1 票，和自己的一票一共两票）就可以返回并声明自己是 Leader，换句话说，3 个节点发送 2 次 RPC 的情况下，收到其中一个 RPC 投票 OK 的响应，主线程就可以继续往下做 Leader 的逻辑了，不需要等待另一个 RPC 投票响应。那么这种逻辑怎么做呢？

WaitGroup

我使用了比较取巧的 waitGroup 的方式（个人浅显理解感觉很像 Java 的 CountDownLatch，就直接拿来当 CountDownLatch 来用了）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

var wg sync.WaitGroup
wg.Add(1)

for i := 0; i < peersCount; i++ {

  go func(server int) {
    // RPC
    rf.sendRequestVote(server, &request, &reply);

    // if 大多数ok 或 全部节点RPC都结束
    if reply.xxx {

      defer func() {
        if err := recover(); err != nil {
        }
      }()
      // 如果满足了大多数，唤醒主线程
      wg.Done()
    }
  }
}(i)
}
// 阻塞主线程，直到得到大多数节点的选票或者全部节点
wg.Wait()

因为调用 Done 方法的时候有可能被调用两次（一次是满足了大多数，一次是全部 RPC return），所以这里我使用 recover 方法吞掉异常。。比较取巧。个人会比较建议用下面助教推荐的方式来做，看自己喜好了。

Condition

这个方法也是 lecture5 里助教说的方法，类似 Java 里的 Object.wait(), Object.notify()，主要思路是在主线程 for 循环一直检查条件，大多数或全部 RPC 结束，然后调用 wait()，每次 goroutine 的 RPC 返回后都调用 notifyall() 方法唤醒主线程去检查条件。这里不多说，主要看 lecture5 我记得是第一个助教在说的。

2.1.4 Debug 调试建议

做 lab 的过程中出了问题，我基本都是通过打日志的方式来调试，不断在关键地方打 Log，不断 Run 你的 Test，到后面 2C 的时候有几个测试比较复杂，我建议你在脑子过一下你的实现，review 你刚刚写的代码是很重要的，我出的大部分 bug 都是由于代码粗心，有几个小错误，经过 review，在脑子里跑一下自己的代码会比较能看出来。如果问题实在复杂，建议查看 test 源码，看看 test 到底以什么方式跑的。所以总结我用的调试方法有如下三点：

  • 在关键地方打日志看数据变化
  • 在脑子里跑一遍自己的代码实现，review 你的 code
  • 看看 test code 的工作原理，从而明白错误为什么会产生

2.1.5 其他的小 Tips

1
2
3
4
5
6
7
8
9

func (rf *Raft) sendAppendEntries(server int, args *AppendEntriesArgs, reply *AppendEntriesReply) bool { 
  // Call方法第一个参数是RPC接收方会被调用的方法    
  ok := rf.peers[server].Call("Raft.AppendEntries", args, reply)  
  return ok 
} 
// RPC会被调用到这里来 
func (rf *Raft) AppendEntries(args *AppendEntriesArgs, reply *AppendEntriesReply) {   
  // ... 
}
  • test 会实现 RPC 超时的逻辑，一般来说你不需要去实现超时判断，除非你会想要精确控制 RPC 超时时间，那么你可以利用 channel 和 select 去做：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// channel，相当于阻塞队列里面是布尔值 
rstChan := make(chan bool) ok := false 
// 不阻塞，在下面select中阻塞 
go func() {   
  rst := rf.peers[server].Call("Raft.AppendEntries", args, reply)   
  // 返回的结果给到channel阻塞队列   
  rstChan <- rst }() 
  // select会轮询（应该是？不是特别了解） 
  // 直到两个channel哪个ok就return，如果timer.C的channel先return了，就是超时了 
  // 同时返回ok的默认值false，表示RPC超时，请求失败 
  select {   
    case ok = <-rstChan:
    case <-time.After(TimeoutDuration):
  }
  return ok
}
  • 随机数怎么做？
1
2
3
4

// 以rf.me做随机种子，保证每个节点种子不一样，足够随机 
rf.random = rand.New(rand.NewSource(time.Now().UnixNano() + int64(rf.me))) 
// 获取随机值 
randomVal := rf.random.Intn(200)

2.2 Lab2B

2.2.1 提交 log

在入口方法 Make 方法中有一个 channel 参数为 applyCh chan ApplyMsg ，将被视作已提交的日志放到这个 channel 中

1
2
3
4
5
6
7

msg := ApplyMsg{
  CommandValid: true,
  Command:      logEntry.Command,
  CommandIndex: logEntry.Index,
}
// 提交log
applyCh <- msg

new 一个 ApplyMsg 对象然后 put 到 channel 中，这样 test 才会知道这个节点的这段日志被提交了。

其中 Leader 会确保日志在半数以上节点被复制完成，才会提交这条 log 到 channel，然后更新自己的 commitIndex，表示这条日志被提交，随着 AE 心跳或者日志复制，leader 会告诉 follower 这条日志被提交，然后 follower 也需要做一个提交动作，将 leader 告诉自己的这条 log 提交到 channel 中。

我曾经以为只需要在 leader 中 put channel 就可以了，但这样 test 会认为你的 follower 这条日志没有被提交，某些 test 需要检测日志在所有节点已经被提交，从而无法 pass test。所以注意 follower 也需要 put log 到 channel

2.2.2 两个优化建议

加速日志同步

在下面几个测试中节点会大量的宕机，日志会大量的乱序，当 follower 从宕机中恢复，需要与 leader 通信日志 Index，此时就需要同步日志，将 follower 日志与 leader 日志同步起来，此时 follower 需要找到最后一个与 leader 一样的日志（相同 Index 处的 log 的 Term 也相同被视作相同的日志），从这条日志往后开始进行复制，也就是 paper 中提到的 prevLogIndex、prevLogTerm 的作用，笨方法是 leader 与 follower 一条一条从最后往前开始对比日志哪条一样，但如果日志比较长，会造成有一条不同的日志就需要一次 RPC，非常耗时，你需要优化加速这一过程，不是每条日志都进行比较，而是会跨过整个 Term 进行比较。

至于优化方式为了 lab 效果这里不多聊。可以参考 lecture7 教授会讲到 3 个 case，和助教的 blog 中的 An aside on optimizations 也有提到。

批量提交日志

这条的必要性有待考究，我在做 lab 的时候潜意识就将实现做成批量提交的方式，所以不知道这项优化是否会影响 test，个人建议还是做成批量提交的比较好。下面的某些 test 的 log 有可能会达到几百几千条，如果一条一条日志慢慢提交，慢慢 check 大多数条件然后 apply，个人感觉会比较慢，而每个 test 都有时间限制，也出于自己对代码的严格要求，不将就，建议做成批量提交的比较优雅。

2.3 Lab2C

lab 中持久化不是持久化到硬盘，而是将数据 Encode 之后变为 byte 数组存在内存中。服务器重启之后会读取这部分内存中的 byte 数组到 Raft 实例这部分内存中使用。code 骨架中有持久化例子，在 persist 和 readPersist 方法中，分别有 Decode 与 Encode 的方式与事先准备好的持久化方法 rf.persister.SaveRaftState(data)

这个 lab 的目标外表看上去是持久化（我做到 2C 时已经觉得做完了 lab，觉得 2C 不会花多少时间，实际上这部分出现的 BUG 是我调试最久的。。），但其实重点难点并不在持久化怎么做，而是在什么时机持久化，以及更有挑战性的 test，大概率会导致你的 leader 选举与 AE 日志复制出现 BUG，所以 2C 在我看来是对日志复制与 Leader 选举更大的挑战，如果你没做好上面一节说的优化建议，很有可能无法 PASS 2C 的 test。所以这里我没什么好建议给你，加油干就完事了，坚持不懈不要被 BUG 击退。

分布式一致性算法中相对于 Paxos，Raft 还是比较简单易懂的，实现一个 Raft 对于学习分布式一致性还是很有帮助的，Raft 真正的难点在于工业级的优化，论文中只是教你如何实现，但粗略的实现在生产环境上性能并不是那么的理想，所以优化是难点也是一个重点。对优化感兴趣的读者可以参考 Raft 的工业级实现比如 etcd

3. 最后

如果你完成了 lab，请不要将你的 lab 上传到例如 GitHub 这样的公开代码库，如果学习 lab 的同学直接参考源码那学习效果将会大打折扣。同时这也是 MIT6.824 的教授 Morris 所要求的，如果要上传到代码库给特定的人参考或是其他用途，最好将仓库设置为 Private 权限访问。

更多深度技术文章，可以瞅瞅本人的博客

[|-| - |_ |_ ()_Static_lin_CSDN 博客 - spring, 设计模式, 分布式领域博主