Readings - In Search of an Understandable Consensus Algorithm (Extended Version) (to end of Section 5)论文

Introduction

共识算法（Consensus algorithms）允许一组机器作为一个一致的组工作，这个组可以在某些成员失败的情况下存活。Paxos是过去10多年最常被讨论的共识算法，但是难以理解且不便于实现。提出Raft的主要目标是可理解性。通过解耦leader选举、log复制和安全，以及减少状态空间，来增加可理解性。

多副本状态机（Replicated state machine）与共识算法 共识算法常常出现在多副本状态机的讨论中。

多副本状态机常用于解决分布式系统中的各种容错问题，使用复制log来实现，每个状态机以相同的顺序执行相同的命令，最终算出相同的状态和结果。保证replicated log的一致是由共识算法来实现的。

共识算法一般有以下几个特征：

• 安全：非拜占庭条件（网络问题、丢包、乱序）下，不返回任何错误的结果。
• 可用性：大多数server可用，则系统整体可用。
• 不依赖时间来保证日志的一致性。
• 大多数server执行完毕则返回，少量慢server不影响系统性能。

Raft

raft的工作过程是，首先选举leader，leader会负责管理replicated log。leader接受来自client的log，复制到其他机器，并在安全的时候通知其他机器把log输入状态机。

raft可以解耦为以下三个部分：

1. leader选举（Leader election）
2. 日志复制（Log replication）
3. 安全（Safety）

在理解这三个部分前，有几个基本概念需要知道， server 状态

• leader：只能有一个leader
• follower：只响应来自其他server的请求
• candidate：用于选举

时间 raft把时间分为terms，term由一个递增的数字标识，表示current term。每个term以leader选举作为起始，如果未选举出leader，那么下一个term继续选。term内选举出的leader管理集群直到term结束。

不同的server可能观察到不同的term转换，server使用current term（在server通信的时候发送）作为逻辑时钟，来确保能够探测到过期的信息。

通信 使用rpc。基本的共识算法使用两种rpc，

1. RequestVote RPCs：candidates调用，来进行拉票，用于选主。
2. AppendEntries RPCs：leader发起，用于复制日志和心跳。

leader选举（Leader election）

选举过程为，follower在election timeout内都没有收到leader的通信，则转换为candidate状态，并自增当前term、为自己投票、向其他server发送RequestVote RPCs。candidate维持在这个状态，直到下列情况出现：

1. 获得了相同term的多数派的投票，赢得选举。 一旦candidate赢得选举，就转换为leader，并向其他server发送heartbeat，宣告leadership。
2. 收到AppendEntries RPCs，其他candidate赢得了选举，成为leader。
   1. 如果leader的term >= 自己的term，那么这个leader是合法的，自己转换为follower状态。
   2. 如果leader的term < 自己的term，那么拒绝这个rpc，自己维持在candidate状态。
3. election timeout后，未获得足够的选票。 多个candidate可能同时发起选举，发生了split vote，导致任何一个都无法获得多数派的投票。自增term，开始下一次选举。

在下面的状态图中，状态转换的上方表示触发转换的event，下方表示发生转换时执行的action。

选举安全性：

• 在每个term内，每个server只能至多为一个candidate投票。

在选举过程中，raft使用随机election timeout来保证，

• split votes（没有任何candidate能获得大多数投票）会很少出现。 比较常见的是，C先timeout，然后投票给自己，并发送RequestVote RPCs，最终win。
• 且split votes能够被快速解决。如果出现split votes，candidate先等待随机election timeout。

日志复制（Log replication）

如何复制

1. leader追加log entry。
2. AppendEntries RPC。
3. 当log entry被安全复制（成为committed log entry，leader更新commit index），
   • leader apply log entry，然后返回结果到client。
   • leader AppendEntries RPC通知follower committed entry，follower apply log entry。

如果follower失败、运行缓慢、丢包，leader重试AppendEntries RPC（就算leader已经返回client结果），直到所有follower最终收到所有log entry。raft保证了committed entry是持久化的，且最终能被所有可用的状态机执行。

那什么时候才算log entry被安全复制？当创建log entry的leader把entry复制到大多数server上以后。这同时也提交了在leader中所有先前的log，包括被前leader创建的log。

应对出错 raft在复制log时会维护如下性质来保证Log Matching Property（log consistency），

• 如果两个entry在不同的log中有相同的index和term，那么它们的cmd是相同的。 因为leader至多只创建一个带有相同index和term的entry，且entry不会在log中改变位置。
• 如果两个entry在不同的log中有相同的index和term，那么所有先前的log都是相同的。 consistency check：AppendEntries RPC发送新的entry时，会包含前一个entry，如果follower没有找到与前一个entry相同的index和term，那么follower不会写入新的entry。

根据以上两点，结合数学归纳法可知，Log Matching Property可以被满足。在正常情况下，leader和follower的log是保持一致的。

如果leader或follower崩溃引起了log不一致，如何恢复一致性？leader会强制follower复制自己的log，

1. leader维护了{follower: nextIndex}，表示下一个将会发送到follower的entry。
2. leader启动时，将nextIndex置为max(self log index) + 1。
3. 如果follower的日志不一致，那么接下来的AppendEntries RPC consistency check会失败。leader会将nextIndex - 1并重试，直到成功。

安全（Safety）

任何实现了日志复制的系统，都必须满足：一旦entry已经applied到状态机，那么任何其他状态机都不能为这条entry apply一个不同的值。

截止目前所描述的leader选举，存在的问题是，如果follower未收到leader的提交，那么当它成为leader以后，就会用自己的log覆盖其他server的。

选举约束 任何基于leader的共识算法，leader必须最终包含所有committed entry。raft需要保证所有committed entry，都出现在后续每个新的leader中，而这个保证确保了本节内容开头的安全性要求。

在选举的时候，使用voting process来避免未包含所有committed entry的candidate赢得选举。由于candidate在选举的时候需要联系大多数server，即只需要求每个committed entry必须出现在至少一个server（选举时联系的server）里面即可（抽屉原理）。

如果candidate包含的日志与大多数server包含的log至少一样新，那么这个candidate就包含了所有的log。具体判断方法是，

1. 在RequestVote RPC进行投票时，rpc包含了candidate最后一个entry的index和term。
2. 如果voter（收到rpc call的一方）的log是更新的，即， $$(lastTerm_v > lastTerm_c) || ((lastTerm_v == lastTerm_c) \\&\\& (lastIndex_v > lastIndex_c))$$ 那么voter拒绝此次投票。

提交上一个term的entry 新leader能否直接提交上一个term的entry？

c中s1成为term4的leader后继续复制term2的日志index2，此时日志已经复制到大多数机器上。按照之前的规则，s1可以认为日志已经是committed。但如果接着s5成为了leader（接受s3和s4的投票），s5会覆盖s1已经commit的日志。

因此不能仅通过副本数判断先前term的日志是不是committed，还需要满足至少有一个属于当前term的log也复制到大多数server，才能认为是。

follower和candidate崩溃

raft rpc是幂等的，leader无限重试。

时间和可用性

raft的安全性不依赖时间。但是系统的可用性依赖时间，这里有尤其指的是leader选举。election timeout需要满足下面的要求，raft才能选举并保持一个稳定的leader，

Leadership transfer

本质上还是使用leader选举的机制，通过主动触发目标server进行选举来实现来迁移，与后面的配置变更不同。过程如下：

1. 旧leader暂停服务。
2. 旧leader进行正常的日志复制过程，把log复制到目标server。
3. 旧leader发送TimeoutNow到目标server，触发目标server开始选举（相当于调快了timer，触发了election timeout）。
4. 目标server大概率会比其他server先发起选举，并成为下一个term的leader。
5. 选举成功后，旧leader收到heartbeat，出让leadership，至此transfer完成。

如果迁移过程未在一个election timeout内完成，那么终止迁移。如果迁移成功了，但是旧leader误以为失败了，那最坏情况是进行一次额外的选举。

问题

1. 日志复制时每个步骤都有可能出现错误，如何处理？ raft并不允许“false positives”的出现（返回client执行成功了，但实际上没有成功），但是可能会有“false negatives”的出现，告知client失败了，但实际上是成功了。为了避免false negatives，client必须重试直到成功，且每次只能有一个未完成的command，相应地，raft也必须提供去重机制。

2. 为什么不能直接复制上一个term未committed的entry？

3. raft为何能够防止脑裂？ 2f+1个server，成为leader需要获得大多数server（f+1个）的投票。如果发生网络分区，必然有一个partition的分区少于f+1个。这个分区里面，

   • 如果没有leader，那么也不可能选举出leader。
   • 如果有leader，由于日志无法被安全复制，因此不会对client做出任何承诺（不会成为committed entry，也不会被apply到状态机）。

4. 为什么需要leader？

   • 简化复制日志的过程。
   • 保证所有的副本都以相同的顺序执行相同的命令。

5. server变为candidate后会发生什么？ 开始选举：inc term，vote self，发送RequestVote RPC。可能结果如下，

   • 赢得选举。 变为leader。
   • 选举失败，收到来自其他leader的AppendEntries RPC。 变为follower。
   • 既没有赢得选举，也没有收到来自其他leader的AppendEntries RPC。 维持candidate。election timeout，开始下一次选举。 如果一直无法获得大多数server的投票，这个过程会一直重复，term会一直增加。 此时，如果client有请求会发生什么？

6. 如何保证同一个term内只有一个leader？

   • leader需要获得来自大多数server的投票。
   • 在同一个term内，每个candidate只能投票一次。
   • 在同一个term内，至多只有一个server能获得大多数server的投票（即使出现网络分区）。

7. 什么情况下选举会失败？

   • 大多数server都失败了。
   • 两个server获得了相同票数（例如：2f+1个server，挂了一个server）。

8. 选举失败会发生什么？ election timeout，开始下一次选举。

9. 如何设置election timeout？

   • $broadcastTime \ll electionTimeout \ll MTBF$
   • random
   • 至少是几个heartbeat间隔

10. replicated和committed entry的区别？

    • replicated是做了复制，可能被覆盖。
    • committed，已提交，不会丢失。

11. 每个副本的日志会完全一致吗？ 不会，可能落后，可能会有临时的不一致。但最终会一致，且状态机执行的命令是一致的。

12. 为什么leader不能直接提交上一个term的entry？以及如何避免直接提交带来的问题？ 提交时，需要等到至少一个当前term的entry也安全复制以后。

13. leader在什么时候覆盖follower的entry是合法的？ uncommitted entry。

14. leader覆盖follower的entry时，可能会覆盖committed entry吗？ 不会。

    1. 先看entry成为committed时，发生了什么。log entry需要安全复制，即发送到大多数server上。
    2. candidate成为leader，需要联系大多数server，以保证自身的log与大多数server的一样新（选举约束）。因此成为leader的candidate一定包含了所有committed entry。

15. 如果下图中的leader（for term 8）挂了，a、d和f，哪个会被选举为leader？谁投的票？新leader产生后，哪些entry一定会保留下来？

    a-f每个server最多可能获得投票的情况如下： a：a，b，e，f b：b，f c：a，b，c，e，f d：a，b，c，d，e，f e：b，e f：f

    所以a或d可能成为leader，一定会保留下的log是111445566。

16. 如果server刚开始选举，此时收到了来自leader的AppendEntries RPC（假设leader与这个server都是处于同一个term），此时要怎么处理？

    • candidate成为leader后，应该立即发送心跳来避免发生多余的选举。
    • 如果发生这个情况，由于term一样，leader会忽略RequestVote RPC。

17. 如果leader完成复制，更新自身的commit index，且完成了apply，但在通知follower commit index前挂了（或丢失了leader资格），这个entry最终会丢失吗？

18. lastApplied是否应该做持久化？ 这个地方有点争议。在ongardie/dissertation的Errata中，指明了lastApplied是否做持久化应该与状态机一致。但在Raft Q&A中的说法是，状态机如果做持久化，那么也应该负责记住执行了哪些log。

19. follower拒绝AppendEntries RPC时，如何快速的解决冲突？ follower拒绝时，返回冲突entry的term，以及这个term首个entry的index。

    • 如果leader有这个entry，那么移动nextIndex到冲突的那个entry。
    • 如果leader没有这个entry，那么移动nextIndex到那个term的首个index。

    还可以使用二分法，查找首个冲突的entry，这可以实现在最坏情况下的最佳时间复杂度。

Lab 2A: Raft

锁的使用建议

这个lecture说了几点关于锁的建议，我觉得最重要的一点是，

Be careful about assumptions across a drop and re-acquire of a lock. One place this can arise is when avoiding waiting with locks held.

在减少锁的粒度的时候，可能也把变量的write和read分开了，进而导致在read的时候，变量已经被其他线程改变了。

References

1. Why Raft never commits log entries from previous terms directly
2. raft之 为什么不能直接commit 上一个term的entry
3. raft本质理解
4. Raft user study lectures
5. The Raft Consensus Algorithm
6. ongardie/dissertation
7. ongardie/runway-model-raft
8. Raft Q&A