Raft论文笔记

引言

本文是Raft分布式协议论文的阅读笔记。

介绍

1. Paxos奠定了基础，但是难以理解，Raft的首要目标是可理解性。
2. Raft算法有一些独特特性：
   1. 强Leader：Raft的Leader相比于其他算法更强，比如日志只从Leader发送给其他server。简化了日志管理且更易理解。
   2. 领导选举：Raft使用随机计时器来选举Leader，是在心跳机制上增加的机制，更加快捷。
   3. 成员关系调整：Raft使用一致的方法来处理成员变换的问题。在调整前后的两种配置大多数机器会重叠，所以集群在成员变换的时候依然可以继续工作。
3. Raft的安全性被定义和证明，效率与其他算法不相上下。

RSM（复制状态机）

• RSM：一组服务器上的状态机产生相同状态的副本，并且在一些机器宕机的情况下继续运行。

• 典型应用为独立的RSM管理领导选举和存储配置信息，并且在Leader宕机的情况下也要存活。

• 每个状态机按照相同的复制日志执行相同的指令序列，所以产生相同的状态和同样的序列。

• 因此一致性算法是为了保证复制日志的一致性。

一致性算法的特性

• 安全性：在非拜占庭错误的情况下（延迟，分区，丢包，重复，乱序）可保证正确。
• 可用性：集群中只要有大多数机器可运行并可以互相通信、和客户端通信，就可以保证可用。
• 不依赖时序保证一致性：物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。

Paxos算法的问题

1. 难以理解。
2. 没有提供足够好的用来构建显示系统的基础。

Raft算法

• Raft算法选举一个Leader。
• Leader具有全部的管理复制log的责任。
• Leader从Client接收Log Entries，并复制到其他服务器上，并告诉其他服务器什么时候可以安全地将日志条目应用到RSM中。
• Leader的设计简化了对于复制日志的管理，e.g. Leader可以决定Log Entry放在log中的什么位置而无需商议。
• 如果Leader发生故障或是失去连接，新的Leader会被选举出来。

由此，Raft算法被拆分为三个部分：

1. Leader选举。
2. 日志复制。
3. 安全性。

以下是算法的浓缩总结：

以下是Raft算法在任何时候都保证的特性：

这里绘图梳理一下：

注意，Leader的易失性状态选举后重新初始化。

修改：如果有冲突，则删除与存在条目和后续所有条目后继续推进（追加新条目）。图片这里没有表示清楚。

特性：

特性	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来
领导人只附加原则	领导人绝对不会删除或者覆盖自己的日志，只会增加
日志匹配特性	如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致
领导人完整特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中
状态机安全特性	如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目

所有服务器需遵守的规则：

1. 所有服务器：

   • 如果commitIndex > lastApplied，则 lastApplied 递增，并将log[lastApplied]应用到状态机中。
   • 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，则令 currentTerm = T，并切换为跟随者状态。

2. 跟随者：

   • 响应来自候选人和领导人的请求。
   • 如果在超过选举超时时间的情况之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，就自己变成候选人。

3. 候选人：

   • 在转变成候选人后就立即开始选举过程。
     • 自增当前的任期号（currentTerm）。
     • 给自己投票。
     • 重置选举超时计时器。
     • 发送请求投票的 RPC 给其他所有服务器。
   • 如果接收到大多数服务器的选票，那么就变成领导人。
   • 如果接收到来自新的领导人的附加日志（AppendEntries）RPC，则转变成跟随者。
   • 如果选举过程超时，则再次发起一轮选举。

4. 领导人：

   • 一旦成为领导人：发送空的附加日志（AppendEntries）RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以防止跟随者超时。
   • 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端。
   • 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex（lastLogIndex ≥ nextIndex），则发送从 nextIndex 开始的所有日志条目：
     • 如果成功：更新相应跟随者的 nextIndex 和 matchIndex。
     • 如果因为日志不一致而失败，则 nextIndex 递减并重试。
   • 假设存在 N 满足N > commitIndex，使得大多数的 matchIndex[i] ≥ N以及log[N].term == currentTerm 成立，则令 commitIndex = N。

基础

• 一个集群包含若干节点。
• 一个节点处于三个状态之一：Leader，Candidate，Follower。
• 通常情况下一个集群有一个Leader，其他都为Follower。
• Follower被动，不会发送请求，只会响应Leader和Candidate请求。
• Leader处理所有Client请求，如果Client发送请求给了Follower，Follower负责重定向。

• term在算法中充当逻辑时钟，使服务器可以检测到过期的信息。
• 每个服务器都会存储当前term，并在通信时交换。
  • 如果当前term比别人小，则会更新自己的term到较大值。
  • 如果Candidate/Leader发现自己的term过期，则会恢复为Follower。
  • 如果节点接收到包含过期term的请求，会拒绝。
• 最基础的算法只有两个RPC（如上文所述）。

Leader Election

如下图所示：

特殊情况：多个Follower同时成为Candidate，选票可能被瓜分，导致每个Candidate超时，然后开启新的一轮，导致无限瓜分。

解决方案：超时时间从一个固定区间随机选择（e.g. 150-300 ms），这样大部分情况下只有一个服务器选举超时，然后它新开一轮并胜出。

原本的方案是使用排名系统，每个Candidate有唯一的排名，如果Candidate发现另一个Candidate有更高的排名，则会退回Follower状态。问题是如果高排名Candidate宕机，底排名的服务器会不断发起选举，但是总是会发现有更高排名的服务器，又会退回Follower，导致过程被频繁重置，且难以理解。

日志复制

日志以如下方式组织：

每一个条目包含：

1. 状态机指令。
2. Leader收到指令时的term。
3. 整数index表示在日志中的位置。

日志复制序列图：

已提交

1. Leader决定什么时候将日志应用到状态机安全。
2. 这种日志条目被称为已提交。当Leader创建的条目复制到大多数服务器上时，条目就会被提交。同时Leader日志之前的所有log也都会被提交，包括由其他Leader创建的条目。
3. 算法保证所有已提交的日志条目都是持久化且最终会被所有可用的状态机执行。
4. Leader跟踪最大的将会被提交的条目的索引，并且索引值会被包含在未来所有appendLog rpc（包括心跳），所以其他服务器能最终知道Leader的提交位置。
5. 一旦Follower知道一个条目已被提交，它也会将这个条目应用到本地状态机（按照日志顺序）。

日志匹配特性（Log Matching Property）

如上文所说，Raft时刻保证以下特性：

• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
• 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

证明：

• 第一个特性：Leader最多在一个term中在一个指定的日志索引位置创建一条条目，同时这个条目在日志中的位置从来不变。
• 第二个特性：在发送appendLog rpc时，Leader会把新的条目前面紧挨着的索引位置和term包含在log内。如果Follower找不到相同索引位置和term的条目，就会拒绝接受新的日志。所以可以通过归纳证明。

一致性检查（如上所述）是在Leader和Follower崩溃时起作用。下图是可能发生的情况：

这里引用原文解释：

当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

Raft算法采取强制复制来处理，即Follower中的冲突项会被Leader日志强制覆盖（如先前的流程图所示）。

• Leader在获得权力时对每一个Follower维护了一个nextIndex（参见上文），表示下一个要发送给Follower的log条目地址。初始为自己最后一个日志index+1。
• 如果Follower的日志不一致，那么下次appendEntry时一致性检查便会失败。
• 失败，也就是Leader被拒绝后，Leader会减小nextIndex并重试。
• 最终nextIndex会在某个位置使得Leader和Follower的日志一致，即最后达成一致的地方。
• 此时appendEntry成功，Follower的冲突日志被删除并加上Leader的日志。

综上所述，Leader并不需要特殊操作来恢复一致性。日志会在回复appendEntry的一致性检查时自动趋于一致。Leader不会覆盖/删除自己的日志（参见上文Leader只附加特性）。

安全性

安全性上仍有问题，比如一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目。也就是不同的状态机执行了不同的指令序列。

因此需要在领导选举时增加限制来完善算法，也就是保证先前提到的领导人完整特性（Leader Completenes Property）。

选举限制

Raft需要一个机制保证选举的时候Leader拥有之前term中所有已提交的日志，且不需要其他节点传递给Leader（降低复杂性），也就是日志的传送只能从Leader到Follower，而不能反过来。Leader也从不会覆盖本身日志中已存在的条目。

1. Candidate需要联系大部分节点以赢得选举。
2. 已提交的日志条目会在大部分节点上。
3. 所以之间必然有重合（与Paxos使用到的机制类似）。
4. RequestVote RPC中包含了Candidate的日志信息，投票人会拒绝日志没有自己新的投票请求。果Candidate的日志至少和大多数的服务器节点一样新，那么它一定持有了所有已经提交的日志条目。
5. Raft通过比较两个日志中的最后一条日志条目的index和term定义“新”。term不同时term更大的新；term相同时日志更长的新。

提交之前term内的日志条目

Raft不会通过计算副本数目的方式提交一个之前term内的条目，因为Leader不能断定一个存储到大多数节点上的日志条目就一定已经提交了，如下图所示：

引用原文：如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中，S1 是领导人，部分的(跟随者)复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为 S5 就不可能选举成功）。 这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

因此，只有Leader当前term内的条目通过计算数目可以被提交，一旦当前term的日志条目被提交，由于日志匹配特性，之前的日志条目也都会被简介提交。

安全性论证

这里直接放原文更容易理解。

假设任期 T 的领导人（领导人 T）在任期内提交了一条日志条目，但是这条日志条目没有被存储到未来某个任期的领导人的日志中。设大于 T 的最小任期 U 的领导人 U 没有这条日志条目。

1. 在领导人 U 选举的时候一定没有那条被提交的日志条目（领导人从不会删除或者覆盖任何条目）。
2. 领导人 T 复制这条日志条目给集群中的大多数节点，同时，领导人 U 从集群中的大多数节点赢得了选票。因此，至少有一个节点（投票者、选民）同时接受了来自领导人 T 的日志条目，并且给领导人 U 投票了，如图 9。这个投票者是产生这个矛盾的关键。
3. 这个投票者必须在给领导人 U 投票之前先接受了从领导人 T 发来的已经被提交的日志条目；否则他就会拒绝来自领导人 T 的附加日志请求（因为此时他的任期号会比 T 大）。
4. 投票者在给领导人 U 投票时依然保存有这条日志条目，因为任何中间的领导人都包含该日志条目（根据上述的假设），领导人从不会删除条目，并且跟随者只有在和领导人冲突的时候才会删除条目。
5. 投票者把自己选票投给领导人 U 时，领导人 U 的日志必须和投票者自己一样新。这就导致了两者矛盾之一。
6. 首先，如果投票者和领导人 U 的最后一条日志的任期号相同，那么领导人 U 的日志至少和投票者一样长，所以领导人 U 的日志一定包含所有投票者的日志。这是另一处矛盾，因为投票者包含了那条已经被提交的日志条目，但是在上述的假设里，领导人 U 是不包含的。
7. 除此之外，领导人 U 的最后一条日志的任期号就必须比投票人大了。此外，他也比 T 大，因为投票人的最后一条日志的任期号至少和 T 一样大（他包含了来自任期 T 的已提交的日志）。创建了领导人 U 最后一条日志的之前领导人一定已经包含了那条被提交的日志（根据上述假设，领导人 U 是第一个不包含该日志条目的领导人）。所以，根据日志匹配特性，领导人 U 一定也包含那条被提交的日志，这里产生矛盾。
8. 这里完成了矛盾。因此，所有比 T 大的领导人一定包含了所有来自 T 的已经被提交的日志。
9. 日志匹配原则保证了未来的领导人也同时会包含被间接提交的条目。

通过领导人完全特性，我们就能证明图 3 中的状态机安全特性，即如果服务器已经在某个给定的索引值应用了日志条目到自己的状态机里，那么其他的服务器不会应用一个不一样的日志到同一个索引值上。在一个服务器应用一条日志条目到他自己的状态机中时，他的日志必须和领导人的日志，在该条目和之前的条目上相同，并且已经被提交。现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期；日志完全特性保证拥有更高任期号的领导人会存储相同的日志条目，所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此，状态机安全特性是成立的。

意味着所有的服务器会应用相同的日志序列集到自己的状态机中，并且是按照相同的顺序。

Follower/Candidate崩溃

1. 如果Follower/Candidate崩溃，后续的RPC都会失败。
2. Raft会无限重试，由于请求幂等，所以不会造成问题。
3. 如果Follower收到appendEntry请求但是已经包含该日志，则会忽略该请求。

时间&可用性

1. 系统的安全性不能依赖时间，但是可用性不可避免地依赖于时间。
2. Raft可以选举&维持一个稳定的Leader，只要系统满足如下时间要求：

广播时间（Broadcast Time） << 选举超时时间（Election Timeout）<< 平均故障间隔时间（MTBF）

• 广播时间：从一个服务器并行的发送RPC给集群中其他服务器并接收响应的平均时间。
• 选举超时时间：如上文所述。
• 平均故障间隔时间：对于一个服务器而言两次故障之间的平均时间。
• 此处的小于指的是小一个量级。
• 广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态。
• 选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用。

集群成员变化

一次性原子地转换所有服务器是不可能的，所以在转换期间整个集群存在划分成两个独立的大多数群体的可能性。

为了保证安全性，需要使用两阶段方法。在raft中集群会先切换到一个过渡配置，称为共同一致（Joint Concensus，下文成为JC）。一旦JC被提交，系统会切换到新的配置上。 JC是老配置和新配置的集合：

• 条目被复制给集群中新老配置的所有机器。
• 新老配置的机器都可以成为Leader。
• 达成一致（选举、提交）需要分别在两种配置上获得大多数支持。

配置切换过程

1. 领导人收到从 C-old 切换到 C-new 的请求。
2. 写入并复制一条 C-old,new 日志条目。
3. 当 C-old,new 条目被新旧多数共同提交后，就进入 共同一致阶段。
4. 领导人再写入 C-new 日志条目并复制。
5. C-new 被提交后，旧配置作废，集群正式使用新配置。

• 一旦服务器将新的配置增加到日志，就会用这个配置做出未来决定。服务器永远用最新的配置，无论是否已经被提交。
• 所以Leader会使用C-old,new来决定C-old,new日志条目什么时候被提交。
• 如果Leader崩溃了，新选出来的Leader可能使用C-old或者C-old,new取决于是否接收到了C-old,new。
• 在任何情况下，C-new在这一时期都不会单方面做决定。

额外问题

1. 新服务器没有日志

   • 新服务器加入时可能是空白的，需要时间追上日志。
   • 为避免在此期间影响可用性，Raft 先把新服务器作为无投票权成员加入，领导人会给它们复制日志。
   • 等它们追上进度后，再正式赋予投票权。

2. 领导人不在新配置中

   • 可能出现领导人不是 C-new 成员。
   • 这种情况下，领导人会在提交 C-new 日志后主动退位（转为 follower）。
   • 之后集群会在 C-new 配置下重新选举一个新领导人。

3. 被移除的服务器捣乱

   • 被移除的服务器收不到心跳，会误以为集群没有领导人，从而发起选举并带着更大任期号。
   • 这会导致现任领导人被迫降级，频繁切换降低可用性。
   • 解决方法：Raft 规定如果某台服务器在最小选举超时时间内收到了领导人的心跳，就忽略其他的投票请求，不会更新任期或投票。
   • 这样，活跃领导人的存在可以抵消被移除节点的干扰。

日志压缩

• 增量（如LSM-tree）：只对部分数据区域清理，分散负载。找到被覆盖/删除数据多的区域->重写活跃对象->释放区域。但是实现复杂，可能需要修改Raft。

• 快照：最简单的方法，整个系统状态写到持久化存储后丢弃时间点之前的日志（Chubby，Zookeeper使用）。

• 每个服务器独立创建快照，只包含已经提交的日志。
• 快照内容：
  • 状态机状态
  • 元数据：
    • lastIncludedIndex（最后应用的日志索引）
    • lastIncludedTerm（对应的任期号）
    • 最后一条配置（支持集群配置变更）
• 保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查。
• 完成快照后，可安全丢弃之前的日志。

Leader向落后Follower发送快照

• 原因：当领导人已经删除了某条日志，而跟随者仍需该日志时，只能通过发送快照来追赶。
• 场景：
  • 新加入的服务器
  • 非常落后的服务器

安装快照 RPC

• 作用：领导人分块（chunk）发送快照给落后者。
• 参数：
  • term：领导人任期
  • leaderId：领导人 ID
  • lastIncludedIndex & lastIncludedTerm：快照元数据
  • offset：分块的字节偏移
  • data[]：快照分块
  • done：是否为最后一个分块
• 接收者逻辑：
  1. 若 term < currentTerm → 直接拒绝
  2. 如果 offset=0 → 创建新快照文件
  3. 写入分块，若 done=false → 等待更多分块
  4. 完成时 → 保存快照，丢弃旧日志
  5. 保留快照之后仍然有效的日志
  6. 重置状态机并加载快照配置
• 特点：每个分块都是“心跳”，可重置选举超时。

以下是主要概述：

选择设计/折中

• Raft 的做法：跟随者本地创建快照，领导人只在必要时下发快照。
• 替代方案：只有领导人创建快照并下发所有跟随者（缺点：带宽浪费、实现复杂）。
• 折中理由：
  • 本地创建更高效（无需重复传输）。
  • 领导人无需阻塞客户端请求。

性能优化

1. 何时创建快照？

   • 太频繁：浪费磁盘带宽和资源
   • 太稀疏：日志过大，占用空间，恢复耗时
   • 简单策略：日志大小超过阈值时创建一次快照。

2. 快照写入开销大

   • 目标：不阻塞正常操作
   • 优化方法：写时复制（Copy-on-Write）
     • 函数式数据结构天然支持
     • OS 支持：Linux fork 可创建进程内存快照

客户端交互

1. 客户端如何发现领导人

• 客户端所有请求都必须发给 领导人。
• 客户端启动时：随机挑选一个服务器通信。
  • 如果该服务器不是领导人：拒绝请求并返回最新领导人信息。
  • 如果领导人已崩溃：请求会超时，客户端重试并随机挑选新的服务器。

2. 线性化语义（Linearizability）

• 目标：每次操作都满足线性化，即：
  • 立即执行
  • 只执行一次
  • 保证在调用与响应之间的原子性

问题：命令可能被执行多次

• 场景：领导人在提交日志后但未响应客户端前崩溃，客户端会重试，可能导致命令被重复执行。

解决方案：序列号机制

• 每条指令由客户端赋予唯一 序列号。
• 状态机维护：
  • 每条指令的最新序列号
  • 对应的响应结果
• 如果收到已执行过的序列号 → 直接返回结果，不重复执行。

3. 只读操作的处理

风险

• 直接执行只读请求可能返回脏数据，因为领导人可能已被替换但自己未察觉。

保证线性化的措施

1. 提交空日志
   • 在任期开始时，领导人提交一条空日志，确保他知道已提交日志的最新信息。
2. 多数确认机制
   • 领导人在处理只读请求前，先与集群多数节点交换一次心跳，确认自己仍是合法领导人。

可选方法：租约机制

• 领导人利用心跳维持租约（lease），在租约期内认为自己仍然是合法领导人。
• 缺点：依赖时间同步（假设时钟误差有界），不如心跳确认安全。