MIT-6.824 Distributed Systems-LEC 7 Fault Tolerance-Raft-2

MIT-6.824（Spring 2022）LEC 7 Fault Tolerance-Raft-2

Raft

Leader选举规则

1. 获得大多数的投票
2. 至少是最新的-最后一个term相同就可以给选票
3. 任期号相同则最长的一个获得Leader
4. 如果存在最后一个term号比当前发起选举的Candidate大，则Candidate自动放弃选举

日志追赶

1. Leader发送心跳信号，连带自己的前一个term和前一个日志达到的索引号
2. follower查看自己的前一个term，如果小于Leader的term，返回不允许追加的信息，因为自己落后了
3. Leader的nextIndex减1，然后与Follower反复迭代，直到找到了两者第一个相同的位置
4. 然后Leader更新自己与这个Follower的matchIndex。可以认为nextIndex是乐观的，从最后一个开始往前遍历，而matchIndex是悲观的，最开始的时候直接设置为0
5. Leader与Follower进行日志同步

日志擦除可能会带来一些问题，论文中的Figure 8 说明了这个问题，因此需要有日志提交条件的额外限制： Leader 在当前任期至少有一条日志被提交

前面的协议中一直是减1操作，因此如果Follower落后过多，通信开销会很大

追赶更快的优化算法：并不按照索引后退，而是按照term后退，然后再扫描相同的位置

此时Follower并不只是拒绝，而是返回前一个term以及这个term开始的索引

持久化

重启机器会发生什么？

• 看成一台新机器加入，可能会复制大量的日志
• 从自己的最后的持久化状态开始追赶

需要持久化什么信息？我们应该尽量不保存信息，因为需要存入磁盘，开销很大，只需要保留必要的信息

• 投票的信息
• 日志信息：承诺Leader这些条目都是已经提交过的
• 当前的term：term不可以下降，需要监控term上升，获得自己的投票信息

服务恢复

• 根据全部日志重建状态，一定会获得与之前完全相同的状态，太长了可能开销过大
• 周期性进行快照操作，持久化到磁盘上，可以通过快照对日志进行裁剪，开销不会过大

状态机通过apply channel获得一个快照，然后使用它来进行恢复

使用Raft

步骤：

1. 客户端发送操作给Leader的K/V服务器
2. K/V服务器将操作传递给Raft
3. Raft写入日志
4. Raft与其他服务器通信传送日志
5. 其他服务器发送响应给Leader
6. Leader提交操作（其他的Followers需要等到下一次交互才确认前面的操作并提交）
7. 操作按照顺序传送到K/V服务器
8. K/V服务器执行操作
9. Leader返回操作结果给客户端

客户端也需要保存Raft的Leader和Follower的信息，可以切换它的通信对象

客户端如果没有接收到服务器的响应会进行重试，而服务器可鞥已经执行过这些操作了，因此需要对这些重复的操作进行检测。

一种实现方法：客户端的每一个操作都带有一个id，通过id对重复的操作进行过滤

正确性

模糊定义：多台机器的行为如同单独的一台机器一样

精确定义：

线性一致性：

• 有一个整体的顺序，操作按照顺序逐步执行
• 实时匹配
• 读取操作应该始终返回最后一次写入的值

查看历史操作，即使是并行的程序是否可以在一台机器上执行相同的结果，从而判断是否满足线性一致性。