简介

Raft 是一种共识算法，被设计用来替代 Paxos 算法。

什么是共识算法？

共识问题是分布式容错系统中的基础问题。共识就是多个服务器（servers）对一个值（values）达成一致。一旦决定一个值，那么这个值就是最终值，不允许改变。

典型的共识算法只要当集群中的任意大多数服务可用，就可达到共识状态。

如果有5台服务器，最多允许2台服务器 fail。

Raft 算法基本流程

术语

在一个 Raft 集群中，一个 server 可能是以下三种角色：

  • leader: 同步日志到 follower
    • 通常通过心跳机制通知 follower
  • follower:
    • 每个 follower 通常有一个随机的超时时间（150-300ms）
    • 如果在超时时间内，没有收到 leader 的心跳包，就会进入 candidate 状态，并发起一次 leader election
  • candidate: 仅在选举过程中存在此角色
  • Term（任期）
    • candidate 选举时，会增加一个 Term
  • election（选举）
    • follower 超时未收到 leader 的心跳包时，会增加一个 Term 并发起一次选举
  • vote（投票）
    • 选举过程中，一个 node 同意或不同意另一个 node 成为 leader

      算法初始化

  1. 所有 node 在初始化时都是 follower 状态；
  2. 当一个 node 超时未收到 leader 的心跳包时，它就成为 candidate，并发起一次选举，同时投票给自己；
  3. 其他 node 收到并回复 vote；
  4. 如果该 node 收到了集群中大多数 node 的 vote，它就成为了 leader；
  5. 之后该集群中，所有的改变都需要通过 leader 进行。

以上过程就是一次选举过程。

日志复制（Log replication）

  1. leader 接收到一个新的修改数据请求；
  2. leader 将这个请求添加为节点的 log，此时这个数据不会被更新；——uncommitted。
  3. 为了 commit 这个数据，leader 将这个请求复制给集群中其他的 follower 节点；
    1. follower 节点收到请求后，也记录该数据，并回复leader——uncommitted
  4. 当 leader 收到集群中大多数的回复后，就回复客户端，然后通知 follower 这个 log 可以被 commit 了
    1. 此时，集群就达到了共识状态。

以上过程就是 日志复制。

整个生命周期中集群的状态

image.png

选举（Leader Election）

Raft 算法中有两个超时设置控制着选举。

  • 选举（election）超时——leader 心跳超时
    • follower 等待 leader 心跳包超时
    • 超时时间在 150ms~300ms 中随机选择
    • 超时之后 follower 成为 candidate 然后增加一个 Term 并启动一个新的选举，同时投票给自己
    • 该 candidate 发送一个 Request Vote 信息给其他节点
    • 如果其他节点的 Term 小于该 candidate 的 Term，则 同意这次选举，然后重置自己的超时时间和Term
    • 如果 candidate 获得了大多数的投票，就成为 leader
    • 新的 leader 发送 Append Entries 信息给它的 follower
    • 直到一个 follower 没有收到心跳，然后成为 candidate，这届任期才

candidate 启动一次选举后，有三个可能的结果

  1. 它被选举为 leader
    1. 发送一个 心跳给其他 node
  2. 另一个 node 被选举为 leader
    1. 收到 leader 的心跳
  3. 没有 node 被选举为 leader - 平票
    1. 下一个选举超时后，重新发起下一轮选举
    2. Raft 通过 上述的 随机选择超时时间 的方式，减少平票的发生。

Raft 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

split vote

原因：两（多）个节点同时发生选举超时，然后同时成为 candidate 并启动一个新的选举。

此时，其他的节点按照流程（仅响应 Term 比它小的），进行响应。这两个节点获得了相同的 vote。

此时没有人成功成为 leader，则等到下一个超时后会开始下一轮的选举。

Log Replication——Append Entries

Raft 使用 Append Entries（在心跳包中使用相同的接口）进行 Log Replication。

  1. 客户端发送一个 change 给leader
  2. leader 将这个改变追加到 log 中，这个改变在下一次 headerbeat 包中被发送给 follower
  3. 在大多数 follower 收到这个 log 之后，这个 log 就会被 commit，然后 leader 回复客户端

如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导人会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

日志复制问题

在分布式系统中，日志同步可能会产生以下问题：
image.png
当一个领导人成功当选时，跟随者可能是任何情况（a-f）。每一个盒子表示是一个日志条目；里面的数字表示任期号。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。

例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

在 Raft 算法中，是如何处理这个问题的呢？——强制（follower 重新启动后）同步 leader 的日志。

network partition - 脑裂

Raft 算法在发生网络分区时，也可以正常工作。
image.png
如上图所示，发生网络分区时，会同时产生两（多）个leader。但是由于 Node B 没有获得大多数，所以他收到的信息不会被 commit，即 Node B 无法成功响应 client。
image.png
等到网络分区被修复后，Node B 和 Node A 发现自己的 Term 小于 Node C，因此同意 Node C 为Leader，然后回滚他们 uncommitted 的 log，然后同步 Node C 的 log。

最终，集群回到了一致性的状态。

preVote

如果是 Node B 的 Term 为 3 - 即少部分节点发生了新的选举。此时，由于 Node B 的 Term 比较大，因此 Node B 应该成为恢复后的 leader。要怎么解决这个问题呢？——Raft 使用 preVote 来解决这个问题。

在PreVote算法中，Candidate 首先要确认自己能赢得集群中大多数节点的投票，这样才会把自己的term增加，然后发起真正的投票。其他投票节点同意发起选举的条件是（同时满足下面两个条件）：

  • 没有收到有效领导的心跳，至少有一次选举超时。
  • Candidate 的日志足够新（Term更大，或者Term相同raft index更大）。

PreVote算法解决了网络分区节点在重新加入时，会中断集群的问题。在PreVote算法中，网络分区节点由于无法获得大部分节点的许可，因此无法增加其Term。然后当它重新加入集群时，它仍然无法递增其Term，因为其他服务器将一直收到来自Leader节点的定期心跳信息。一旦该服务器从领导者接收到心跳，它将返回到Follower状态，Term和Leader一致。

Log Compaction

在 Raft 算法运行过程中，Log 是无限增长的，但是我们的容量却是有限的。

论文中建议使用 snapshotting，通过复制整个系统的状态，然后 commit 作为一条 log，之后就可以安全删除被压缩的 log 了。

image.png

为了避免 snapshotting 过程中占用资源过多，最好的实践是通过为节点日志配置固定的大小来进行摊销。

时间和可用性

Raft 可以选举并维持一个稳定的领导人,只要系统满足下面的时间要求：

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

  • broadcastTime - 从一个节点发送请求给其他节点然后接受到响应的平均时间
  • electionTimeout - 超时机制
  • MTBF - 对一个节点而言，两次故障之间的平均时间

广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。

选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

广播时间和平均故障间隔时间是由系统决定的，但是选举超时时间是我们自己选择的。Raft 的 RPCs 需要接收方将信息持久化的保存到稳定存储中去，所以广播时间大约是 0.5 毫秒到 20 毫秒，取决于存储的技术。因此，选举超时时间可能需要在 10 毫秒到 500 毫秒之间。大多数的服务器的平均故障间隔时间都在几个月甚至更长，很容易满足时间的需求。

客户端交互

Raft 中的客户端发送所有请求给 Leader。当客户端启动的时候，随机挑选一个服务器进行通信。如果客户端第一次挑选的服务器不是领导人，那么那个服务器会拒绝客户端的请求并且提供他最近接收到的领导人的信息。如果领导人已经崩溃了，那么客户端的请求就会超时；客户端之后会再次重试随机挑选服务器的过程。

写

Raft 的目标是要实现线性化语义（每一次操作立即执行，只执行一次，在他调用和收到回复之间）。但是，如上述，Raft 是可以执行同一条命令多次的：例如，如果领导人在提交了这条日志之后，但是在响应客户端之前崩溃了，那么客户端会和新的领导人重试这条指令，导致这条命令就被再次执行了。解决方案就是客户端对于每一条指令都赋予一个唯一的序列号。然后，状态机跟踪每条指令最新的序列号和相应的响应。如果接收到一条指令，它的序列号已经被执行了，那么就立即返回结果，而不重新执行指令。

读

只读的操作可以直接处理而不需要记录日志。但是，在不增加任何限制的情况下，这么做可能会冒着返回脏数据的风险，因为领导人响应客户端请求时可能已经被新的领导人作废了，但是他还不知道。线性化的读操作必须不能返回脏数据，Raft 需要使用两个额外的措施在不使用日志的情况下保证这一点。

首先，领导人必须有关于被提交日志的最新信息。领导人完全特性保证了领导人一定拥有所有已经被提交的日志条目，但是在他任期开始的时候，他可能不知道哪些是已经被提交的。为了知道这些信息，他需要在他的任期里提交一条日志条目。Raft 中通过领导人在任期开始的时候提交一个空白的没有任何操作的日志条目到日志中去来实现。

第二，领导人在处理只读的请求之前必须检查自己是否已经被废黜了（他自己的信息已经变脏了如果一个更新的领导人被选举出来）。Raft 中通过让领导人在响应只读请求之前，先和集群中的大多数节点交换一次心跳信息来处理这个问题。可选的，领导人可以依赖心跳机制来实现一种租约的机制，但是这种方法依赖时间来保证安全性（假设时间误差是有界的）。

参考

http://thesecretlivesofdata.com/raft/ —— 必看
https://en.wikipedia.org/wiki/Raft_(algorithm))
https://raft.github.io/
https://deathbytape.com/articles/2015/09/03/raft-consensus.html
https://github.com/etcd-io/etcd/tree/master/raft —— etcd raft 源码
https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md —— raft 论文
https://blog.csdn.net/cyq6239075/article/details/108984968 —— 一个有意思的网络分区问题
https://www.jianshu.com/p/1496228df9a9 —— preVote，上个链接问题的解决方案