分布式一致性算法 — Raft

2020年2月13日 | 作者 Siran | 8000字 | 阅读大约需要16分钟
归档于 分布式 | 标签 #分布式

Raft

Raft 是一种为了管理复制日志的一致性算法。它提供了和 Paxos 算法相同的功能和性能，但是比 Paxos 更容易理解并且更容易实现。

Raft 为了便于理解和实现归结为以下几个原因：

  • 将一致性算法分解成几个关键模块，例如：Leader 选举、日志复制、 MemberShip 变更(节点变化)、日志压缩等。
  • 设计简化：比如不允许类似 Paxos 算法的乱序提交、使用强领导者只有 leader 可以处理客户端请求，通过 Randomization 算法设计 Leader Election，简化状态：只有 Leader、Follower、Candidate

基础

首先先明确几个概念，便于下面算法的理解：

  • 整个 Raft 算法只有三种状态： Leader、Follower、Candidate
  • Raft 算法是强领导人模式，只有 leader 节点才能接收客户端请求
  • 在整个 Raft 算法中节点之间的通信只有三种RPCs
    1. VoteRequest RPC: 发起投票，只有在 Candidate 状态才能发起这个投票用于竞选成为 Leader
    2. AppendEntries RPC: 复制日志也是心跳，只有在 Leader 状态才能发起这个请求。
    3. InstallSnapShot RPC: 快照，只有在 Leader 状态才能发起这个请求用于压缩日志
  • 复制状态机

Raft 是基于复制状态机来实现一致性算法的。

复制状态机都是基于复制日志来实现，如上图所示：每一个服务器都存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。

保证复制日志相同就是一致性算法的工作了。在一台服务器上，一致性模块接收客户端发送来的指令然后增加到自己的日志中去。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，尽管有些服务器会宕机。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成一个高可靠的状态机。

如上图再来解释一下：

  1. 客户端发送请求给服务端的Leader节点，Leader节点中的一致性模块把这条请求首先复制到本地日志中，然后把这条日志在发送给所有节点。
  2. 此时这条日志还不是已提交的日志，等大部分节点都把这条日志复制到本地的日志中时，这条日志才为称为已提交的日志。
  3. 把已提交的日志插入状态机中，这个状态机可以理解为执行客户端发送请求里的操作。
  4. 返回ack给客户端
  • 任期：

Raft 把时间分割成任意长度的任期，如上图。任期用连续的整数标记。每一段任期从一次选举开始，一个或者多个Candidate尝试成为Leader。如果一个Candidate赢得选举，然后他就在接下来的任期内充当Leader的职责。在某些情况下，一次选举过程会造成选票的瓜分。在这种情况下，这一任期会以没有Leader结束；一个新的任期（和一次新的选举）会很快重新开始。Raft 保证了在一个给定的任期内，最多只有一个Leader。 在每个RPCs 请求中都会带有任期号，来判断此节点是否之前宕机或者处理过慢，如果某个节点任期比较陈旧，那么不管这个节点是什么角色立即成为Follower 与 Leader节点进行同步

核心

Leader Election

所有节点初始化都是 Follower 状态，然后等待超时，超时后成为 Candidate 状态。然后 Candidate 发送投票请求进行竞选。如果获得大部分的支持那么成为 Leader，随后定时发送心跳给其他节点，来确定自己的地位。如下图所示：

  • 心跳
  1. 当有节点成为 Leader 后，定时发送心跳来维持自己的权威
  2. 通过AppendEntries RPC(日志条目为null) 作为心跳。
  3. 如果Follower 在一段时间内，没有接受到任何消息，也就是选举超时，那么它就会认为系统中没有可用的 Leader， 并发起选举以选出新的Leader
  • 选举过程
  1. 增加自己的任期号，然后转入 Candidate 状态
  2. 然后向其他服务器发送投票请求来给自己投票，会发生三种情况：
    • 自己赢得这次选举，成为 Leader
    • 其他节点成为 Leader，那么它会接受到心跳请求，当他收到心跳请求的时候，放弃选举转换为 Follower
    • 没有任何一个节点获胜，比如多个Follower 同时成为 Candidate 同时发起选举，没有人能获得大部分的投票。如果不进行限制，那么会进入无限循环。为了解决这个问题，Raft 增加了一个 Randomization 算法，在固定的一个时间段中，随机获取作为选举超时时间，这样就可以避免同时有多个节点发送选举请求。
  • 选举的规则
  1. 当一个 Candidate 获得了同一个任期号内的大多数选票，就成为领导人。
  2. 每个节点最多在一个任期内投出一张选票。并且按照先来先服务的原则。
  3. 一旦候选人赢得选举，立刻成为领导，并发送心跳维持权威，同时阻止新leader的诞生。

Log Replication

保证日志复制相同，才是分布式一致性算法的最终任务。 而上面说的 Leader 选举，只是为了辅助日志复制。其实在 Paxos 中是没有 Leader 的概念的。

  • 日志复制过程
  1. 客户端的每一个请求都包含被复制状态机执行的指令。
  2. Leader 把这个指令作为一条新的日志条目添加到日志中，然后并行发起 RPC 给其他的服务器，让他们复制这条信息。
  3. 假如这条日志被安全的复制(大部分节点成功添加到自己的日志中)，Leader 就应用这条日志到自己的状态机中，并返回给客户端。
  4. 如果 Follower 宕机或者运行缓慢或者丢包，领导人会不断的重试，直到所有的 Follower 最终都存储了所有的日志条目。

如下图所示：

  • 日志的组成
  1. 有序序号标记的条目组成
  2. 每个条目都包含创建时的任期号（图中框中的数字）
  3. 状态机需要执行的指令

每一个日志条目存储一条状态机指令和从领导人收到这条指令时的任期号。日志中的任期号用来检查是否出现不一致的情况。每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置。

  • 日志的一致性
  1. Raft 保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行
  2. Leader 把指令作为一条新的日志条目添加到日志中后，将并行的发送 RPC 给 Follower，让他们复制这条信息。
  3. Leader 将会跟踪最大的且即将被提交的日志条目的索引，并且这个索引会被包含在未来的所有附加日志 RPC 请求中，这样就能保证其他的服务器知道 Leader 的索引提交位置。
  4. 一旦 Follower 知道一条日志条目已经被提交，那么他也会将这条日志应用到自己的状态机中（按照日志的顺序）

在1中提到的"已提交” 是指：被大部分节点都添加到本地日志中的条目叫做已提交条目。

  • 日志匹配特性
  1. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。(Leader最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变)
  2. 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。(每次 RPC 发送附加日志时，Leader 会把这条日志条目的前面的日志的下标和任期号一起发送给 Follower，如果 Follower 发现和自己的日志不匹配，那么就拒绝接受这条日志，这个称之为一致性检查)
  • 异常情况

Leader 崩溃的情况会使得日志处于不一致的状态（老的Leader可能还没有完全复制所有的日志条目）。Follower 可能会丢失一些在新的Leader中有的日志条目，他也可能拥有一些Leader没有的日志条目，或者两者都发生。丢失或者多出日志条目可能会持续多个任期。

当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。

跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。

例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；

很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

Raft的解决方案：

Leader处理不一致是通过强制Follower直接复制自己的日志来解决。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖。

要使得 follower 的日志和 leader 进入一致状态，leader 必须找到 follower 最后一条和 leader 匹配的日志，然后把那条日志后面的日志全部删除。

依据这个限制，上图中的 a follower 不需要删除任何条目，b 也不需要删除，c follower 需要删除最后一个条目，d follower 需要删除最后 2 个任期为 7 的条目，e 需要删除最后 2 个任期为 4 的条目，f 则比较厉害，需要删除 下标为 3 之后的所有条目。

Raft的实现：

  1. Leader 针对每一个 Follower 维护了一个 nextIndex，这表示下一个需要发送给 Follower 的日志条目的索引地址。
  2. 当一个Leader 刚获得权力的时候，他初始化所有的 nextIndex 值为自己的最后一条日志的index加1。
  3. 如果一个 Follower 的日志和 Leader 不一致，那么在下一次的附加日志 RPC 时的一致性检查就会失败。
  4. 在被 Follower 拒绝之后，Leader 就会减小 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得 Leader 和 Follower 的日志达成一致。
  5. 当这种情况发生，附加日志 RPC 就会成功，这时就会把Follower 冲突的日志条目全部删除并且加上Leader的日志。
  6. 一旦附加日志 RPC 成功，那么 Follower 的日志就会和 Leader 保持一致，并且在接下来的任期里一直继续保持。

Safety

根据两个限制来完善 Raft 算法

1. 选举限制

Raft 保证所有之前的任期号中已经提交的日志条目在选举的时候，都会出现在新的Leader中。不需要额外传送这些日志给Leader —— 这意味了保证了数据的单向流动，即只从Leader传给Follower， 并且Leader从不会覆盖自身本地日志已经存在的日志条目。

实现过程：

  • Raft 使用投票的方式，来阻止一个Candidate 赢得选举，除非这个Candidate包含了所有已经提交的日志条目。
  • 如果想成为Leader，该节点必须包含所有已经提交的日志条目。
  • 当候选者发送 RPC 给投票者时，RPC 中包含了Candidate的日志信息，然后投票人会拒绝掉那些日志没有自己新的投票请求。

如何判断是新的投票请求：

  • 首先比较任期号，谁都任期号大，谁就新。
  • 如果任期号相同，那谁的日志长，谁就新。

2. 提交之前任期内的日志条目

Leader 知道一条当前任期内的日志记录是可以被提交的，只要它被存储到了大多数的服务器上。如果一个Leader在提交日志条目之前崩溃了，未来后续的Leader会继续尝试复制这条日志记录。然而，一个Leader不能断定一个之前任期里的日志条目被保存到大多数服务器上的时候就一定已经提交了。如下图展示了一种情况，一条已经被存储到大多数节点上的老日志条目，也依然有可能会被未来的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 就不可能选举成功）。

这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

注意：这两种情况在目前的规则下，都是会发生的

但是，d1 的状态是错误的

为什么？因为 d1 覆盖了 (c) 的日志！！！要知道，当 （c）将日志复制到了大多数机器上，虽然 leader 没提交，但 follower 是有可能提交的。但是 d1 却将日志覆盖了，这将会导致 S2 和 S3 的状态机和日志不一致！！！

为什么会发生这个问题？

在之前的选举规则中：首先比较任期号，谁的任期号大，谁就新。如果任期号相同，那谁的日志长，谁就新。

最后，需要回顾一下 leader 选举的目标：Raft 使用投票的方式，来阻止一个候选人赢得选举 —— 除非这个候选人包含了所有已经提交的日志条目。 也就是说，如果想成为领导人，该节点必须包含所有已经提交的日志条目

在 c 中，S5 满足这两个条件吗？答案是满足的，因为他的任期号（任期 2）确实比 follower（任期 1） 新。

但是，他达到 leader 的选举目标了吗？显然，在 c 中，S5 不包含所有已经提交的日志条目，所以没达到。

为什么？因为 c 中，S1 提交了他的上一个任期的日志。导致任期号的生成和任期日志的提交不是原子的。 不是原子的会有什么影响？

这将会导致: 新 leader 如果提交“之前的任期日志”崩溃了，后面的 leader 的任期将大于刚刚提交的任期，这将让他成为 leader ，并覆盖日志。

如果是原子的: 新 leader 不可能不包含上一个任期的日志。因为要想成为 leader，必须满足任期 + 下标的条件。

我们假设一下，如果 c 中，S1 不提交上个任期的日志，会怎么样？他不会将日志 2 发送到 follower 上，而是应该优先将日志 4提交，顺便提交之前的日志 2，当成功提交日志 4，即使崩溃，S5 也无法成功获取选举（任期号过小）。

所以，Raft 又加了一条限制：leader 只能在自己当前任期的日志满足多数规则时，才能提交。历史时期的日志默认提交，类似上图的 d2 阶段，即，提交 日志4 时，一起提交 日志2（日志匹配特性的作用） ，可防止这种情况发生。

但如果没有日志可以提交怎么办？

提交一条空白日志，利用日志匹配特性，提交上个任期的日志。

所以，提交之前任期内的日志条目是可行的，但必须是新的 leader 提交一条日志（可以是空白的）间接提交。

但，如果直接提交之前的日志，将会导致非原子操作，之前的任期将可能会被后面的 leader 覆盖日志，导致状态机和日志不一致。

Cluster Membership Change

到目前为止，我们都假设集群的配置（加入到一致性算法的服务器集合）是固定不变的。但是在实践中，偶尔是会改变集群的配置的，例如替换那些宕机的机器或者改变复制级别。尽管可以通过暂停整个集群，更新所有配置，然后重启整个集群的方式来实现，但是在更改的时候集群会不可用。另外，如果存在手工操作步骤，那么就会有操作失误的风险。

直接从一种配置转到新的配置是十分不安全的，因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的Leader在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。

Raft 解决方案：两阶段方法，如图所示：

  • 第一阶段：

发送新配置到旧服务器的 leader。leader 不会直接存储新配置，而是存储旧配置 + 新配置。同时，一旦这个配置被提交（成功同步到新旧集群的大部分跟随者中），那么，所有服务器必须用这个配置来做决定。也就是说，旧配置失效了，不能拿旧配置做任何决定，同时，此时的系统状态是一致的。这个状态称之为共同一致

  • 第二阶段：

当 旧配置 + 新配置 被成功提交，这个时候，leader 会创建一条新配置 复制到 followers 中。从而完成配置变更。

Raft 提出了三个问题:

  1. 新的服务器在初始化时，没有存储任何日志条目。

当这些服务器以这种状态加入到集群中，那么他们需要一段时间来更新追赶，这时还不能提交新的日志条目。为了避免这种可用性的间隔时间，Raft 在配置更新之前使用了一种额外的阶段，在这个阶段，新的服务器以没有投票权身份加入到集群中来（Leader 复制日志给他们，但是不考虑他们是大多数）。一旦新的服务器追赶上了集群中的其他机器，重新配置可以像上面描述的一样处理。

  1. 集群的Leader可能不是新配置的一员

Leader就会在提交了 C-new 日志之后退位（回到Follower状态）。这意味着有这样的一段时间，Leader管理着集群，但是不包括他自己；他复制日志但是不把他自己算作是大多数之一。当 C-new 被提交时，会发生Leader过渡，因为这时是最早新的配置可以独立工作的时间点（将总是能够在 C-new 配置下选出新的Leader）。在此之前，可能只能从 C-old 中选出Leader。

  1. 移除不在 C-new 中的服务器可能会扰乱集群

当移除他们时，他们会重新进行选举，导致当前 leader 回退到 follower 状态。虽然新的 leader 会被选出来，但被移除的服务器会再次请求重新选举，循环反复，影响可用性。

当服务器确认当前Leader存在时，服务器会忽略请求投票 RPCs。特别的，当服务器在当前最小选举超时时间内收到一个请求投票 RPC，他不会更新当前的任期号或者投出选票。这不会影响正常的选举，每个服务器在开始一次选举之前，至少等待一个最小选举超时时间。然而，这有利于避免被移除的服务器扰乱：如果Leader能够发送心跳给集群，那么他就不会被更大的任期号废黜。

Log Compact

Raft 的日志在正常操作中不断的增长，但是在实际的系统中，日志不能无限制的增长。随着日志不断增长，他会占用越来越多的空间，花费越来越多的时间来重置。如果没有一定的机制去清除日志里积累的陈旧的信息，那么会带来可用性问题。

一个服务器用新的快照替换了从 1 到 5 的条目，快照值存储了当前的状态。快照中包含了最后的索引位置和任期号。

Raft 中的快照思想：

  1. 每个服务器独立创建快照，只包含已经被提交的日志。主要的工作包括将状态机的状态写入到快照中。
  2. 最后被包含索引指的是被快照取代的最后的条目在日志中的索引值（状态机最后应用的日志）
  3. 最后被包含的任期指的是该条目的任期号。保留这些数据是为了支持快照后紧接着的第一个条目的附加日志请求时的一致性检查，因为这个条目需要前一日志条目的索引值和任期号
  4. 为了支持集群成员更新，快照中也将最后的一次配置作为最后一个条目存下来。一旦服务器完成一次快照，他就可以删除最后索引位置之前的所有日志和快照了。

Raft 实现:

为了便于传输，快照都是被分成分块的；每个分块都给了Follower生命的迹象，所以Follower可以重置选举超时计时器。

  1. Leader 会发送 InstallSnapShot RPC 给落后的Follower
  2. 当Follower接收到后，如果快照中的信息在Follower中没有，那么会丢弃整个日志，被快照取代。
  3. 包含与快照冲突的日志，如果接收到的快照是自己日志的前面部分（由于网络重传或者错误），那么被快照包含的条目将会被全部删除，但是快照后面的条目仍然有效，必须保留。
  4. Follower 可以不知道Leader的情况下自己创建快照。虽然这会打破Raft的强领导原则，但是在创建快照的时候，一致性已经达成，这时不存在冲突了，所以没有Leader也是可以的。数据依然是从Leader传给Follower，只是Follower可以重新组织他们的数据了。

影响快照性能的两个问题：

  1. 服务器必须决定什么时候应该创建快照。如果快照创建的过于频繁，那么就会浪费大量的磁盘带宽和其他资源；如果创建快照频率太低，他就要承受耗尽存储容量的风险，同时也增加了从日志重建的时间。

一个简单的策略就是当日志大小达到一个固定大小的时候就创建一次快照。如果这个阈值设置的显著大于期望的快照的大小，那么快照对磁盘压力的影响就会很小了。

  1. 写入快照需要花费显著的一段时间，并且不希望影响到正常操作

通过写时复制的技术，这样新的更新就可以被接收而不影响到快照。例如，具有函数式数据结构的状态机天然支持这样的功能。另外，操作系统的写时复制技术的支持（如 Linux 上的 fork）可以被用来创建完整的状态机的内存快照（Raft的实现）。

总结

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

下面是本人使用Java 对Raft的实现，以及Raft作者的论文，和一些参考资料。

本人对Raft的实现

In Search of an Understandable Consensus Algorithm (Extended Version)

寻找一种易于理解的一致性算法（扩展版）

Raft 一致性协议

莫那.鲁道博客

相关文章

分类