Raft 算法原理 | 程序锅

Raft 简介

复制状态机（Replicated State Machine）是一种分布式系统架构模式，系统由一组相同的状态机组成，它们在多个服务器（节点）上运行，并确保即使在出现故障的情况下也能够保持一致的状态。

复制状态机确保数据一致性的核心思想是：相同的初始化状态+相同的输入=相同的结束状态。它通过复制日志到所有节点上，每个状态机都顺序执行相同的日志，那么最终的状态是一致的。可以看到，复制状态机强调的是最终一致性。

下面是复制状态机的的结构，主要由共识模块、日志模块、状态机组成。

共识模块：负责处理选举，并选举出 Leader；Leader 会负责处理客户端请求，并进行日志复制（将请求处理成一个包含状态机操作的日志条目，再将日志条目复制到集群中的其他节点）。Raft 或 Paxos 等算法就被用于实现共识模块。
日志模块：记录状态变化（日志条目）的结构，是一个有序的序列；同时追踪哪些日志条目已被提交（commited），并可以被应用（apply）到状态机。
状态机：当日志条目被标记为已提交时，负责应用该日志条目，更改状态机中的状态。

Raft 是一种共识算法（也叫一致性算法），可以看到 Raft 要解决的问题（共识模块的职责），其实就两个，

Leader 选举。如何快速选出 Leader，包括集群启动或 Leader crash 之后的重新选举。同时确保集群中只有一个 leader，避免出现脑裂现象。
日志复制。Leader 负责复制日志到 Follower 节点。同时确保已 commited 的日志不会被删除和覆盖，并且各个节点上相同位置的日志条目内容是一样。

Paxos 也是一种共识算法，但是它的设计过于复杂，难于理解，工程实践上也比较难落地，导致在工程界落地较慢。

Leader 选举

Raft 协议中有 Follower、Candidate、Leader 三种状态，Raft 4.2.1 引入了 Learner 状态：

Follower：不会主动发出请求，仅仅对来自 leader 和 candidata 的请求作出相应回应。如果在 election timeout 时间未收到 leader 的请求，则会进入 Candidate 状态。
Candidate：是 Follower 到 Leader 的中间态。它会主动发出 request vote 请求，在 election timeout 内收到集群半数节点的票数的情况下，变成 Leader 状态。
Leader：处理来自客户端的所有写请求，并且正常情况下，集群内只有一个 leader。leader 会主动定时给其他节点发送 heartbeat，以维持自己 leader 的身份。**需要注意的是，在没有 leader 的情况下，数据是没办法写入的。**如果 leader 故障，follower 会进行重新选举。
Learner：Raft 4.2.1 引入的新角色，它只会从 leader 中接受数据，不会参与投票。因此，增加 learner 节点并不会改变集群的 quorum（一致性数量），也就是参与协商的节点数。这是因为当 etcd 集群需要增加节点时，由于新节点与 leader 的数据差异较大，需要较多数据同步才能跟上 leader 的最新的数据。但是，此时 leader 的网络带宽很可能被用尽，进而使得 leader 无法正常保持心跳，导致 follower 重新发起投票，引发 etcd 集群不可用。因此，如果让新加入的节点不参与投票，不是 follower 的角色的话，可以将发起选举行为的节点数降低。

上述三种主要状态的转化如下所示，

每个节点启动之后，都是 follower。follower 状态下会随机选取一个 election timeout，follower 状态下接受到的数据只有从 candidate、leader 发出两种。
- 如果在 election timeout 内收到了 leader 的 heartbeat。它则会继续保持 follower 状态，并且重新随机选择一个 election timeout。
- 如果在 election timeout 内收到了 candidate 的 request vote 请求。它会先检查，
  - candidate 中的数据状态是否至少和自己一样新，candidate 中的已提交日志的索引是否大于等于自己的。
  - candidate 的 term 是否大于自己。
  - 自己未将票投给其他候选者。
  如果上述条件均满足，它则会将票投给 candidate，并且会继续保持 follower 状态，同时重新随机选择一个 election timeout。
- 如果在 election timeout 超时，它则会从 follower 切换到 candidate，并且将 term+1，然后发起选举。
candidate 状态下，它也会随机选取一个 election timeout，然后向集群中的其他节点发起 request vote 请求。candidate 状态下接受到的数据会有 follower（回复）、candidate、leader 发出的三种。
- 如果在 election timeout 内发现了 Leader，或者发现有比自己大的 term 且数据状态至少和自己一样新，则会变为 follower 状态（参考上面）。比如 candidate 状态下收到了其他 candidate 的 request vote 请求，它发现其他 candidate 的 term 大于自己，则会将自己转为 follower 状态，同时给它投票。如果小于等于自己的 term 就不会给它投票。
- 如果在 election timeout 内未发现 Leader，且未发现有比自己大的 term，且获取到了集群中超过半数的票，则会转为 leader 状态。
- 如果在 election timeout 内未发现 Leader，且未发现有比自己大的 term，且未获取到了集群中超过半数的票，则给自己的 term+1，然后继续发起竞选。
leader 状态下，它会定时给其他节点发送 heartbeat 数据包，以维持自己的 leader 状态。leader 状态下接受到的数据会有 follower（回复）、candidate、leader 发出的三种。
- 如果在这个过程中发现比自己大的 term，则会变为 follower 状态，不会继续发送 heartbeat 数据包了。

其中，term 相当于 Raft 中的逻辑时钟。Raft 将时间划分为一个个 term（任期），term 都是用连续的整数表示。每个 term 都是从一次选举开始，赢得选举的节点，在该 term 内充当了 leader 的职责，一个 term 内最多只有一个 leader。如果发生了新的选举，则集群的 term 会单调递增。通过 term，可以比较各个节点的数据新旧、识别过期的 leader 等。term 类似于第几届的意思，比如某班级第一届（term 为 1）班委中只会有一个班长（leader），第二届（term 2）会发生重新选举，然后产生新的一个班长。

选举过程概述

以三个节点的选举为例，

一开始 3 个节点的状态都是 follower，每个节点会随机设置一个 election timeout，该值会在一个固定区间内随机的选取(比如150-300ms)。

随机的 election timeout 使得大部分情况下，仅会有一个节点先超时，使得它会在其他节点 election timeout 之前发起选举，从而有很大的概率赢得选举。如果 election timeout 时间一致的话，则可能会容易导致 3 个节点同时进入 candidate 状态，然后 3 个节点都拿不到其他节点的 vote，结果不断循环这种现象，陷入竞选活锁。

当 Node A（follower）的 election timeout 到点之后，那么它就会变成 candidate，然后 election term+1。

Node A 成为 cadidate 之后，它会给自己投一票。同时，会向其他节点发送 request vote 的消息，以获取 votes。此时也有相应的 election timeout，需要在 election timeout 内获得半数以上的 votes。
此时 Node B、C 会将自己的 vote 投给这个 candidate。同时这些 node 会重新设置它的 election timeout。
如果 Node A（candidate）收到了 Node B、C 中至少一个的投票，也就是获取到集群半数以上的票了，它就会变成 leader。之后，正常情况下 Node A（leader）会按照心跳间隔时间，不断发送 heartbeat 给 follower 节点以确保自己的 leader 身份。
Node B、C（follower）节点收到之后都会回复 heartbeat 应答包给 leader。与此同时，follower 在接受到 heartbeat 之后会将自己的 election timeout 重置。

Node A crash 之后的重新选举，

如果此时 Node A（leader）异常。follower 节点接收 leader 的 heartbeat 超时，当超过 election timeout 之后还没收到 leader 的 heartbeat 的时候，follower 节点就会进入 Candidate 状态。
假设 Node B 的 election timeout 先到，此时 Node B 会先进入 Candidate 状态。然后发起选举流程，自增 term（任期号），并投票给自己，同时向其他节点发送竞选 Leader 的投票消息。
Node C 收到 Node B 节点的竞选消息后，可能会出现上述提到的两种情况:
- 第一种情况，Node C 处于 follower 状态，Node C 判断 Node B 的数据至少和自己一样新，且 Node B 的 term 大于 Node C 的 term，且 Node C 未投票给其他 Candidate，此时就可投票给 Node B。
- 第二种情况，Node C 处于 candidate 状态，也就是恰好 Node C 也超过了 election timeout，它也发起了选举，并投票给了自己，那么它将拒绝投票给 B（因为 term 都是 2），此时谁也无法获取集群多数支持，只能等待竞选超时，开启新一轮选举。

Node A 假如重新起来，此时它会发现 Node B 节点的 term 大于自己的 term，因此它会变为 follower 节点。
Node A、C 假如是 follower 节点的情况下。如果此时 Node A 与 Node B/C 网络都是不通的，由于它会不断超过 election timeout，因此 Node A 会不停地自增任期号，发起选举。当 Node A 网络恢复之后，由于 Node B/C 发现 Node A 的 term 值更大，但是 Node A 并不是 leader，此时会进行重新选举。但是，此时 Node A 的状态是远远落后于 Node B/C 的，是无法获得 leader 的，此次的选举相当于是无效的。

选举规则

一个节点在一个任期内，只能为一个节点投票。节点会记录下它们在每个任期内投票给了哪个候选者，以确保不会给多个候选者投票。
一个节点在收到选举投票的时候，会检查 candidate 的最后一条 commited 日志条目中的 term 号。
- 如果小于等于自己的 term 则拒绝投票。
- 如果大于自己的 term，但是 candidate 中已提交（commited）的日志条目序号比自己 commited 的日志条目序号小，同样拒绝投票。通过这个规则，可以确保已提交的日志条目，也就是经过集群认可的日志被删除或覆盖。
  
  比如，leader S1 在 2 log 变成 commited 之后变得不可用了，那么被选为 leader 的只能是已经复制了该日志的节点 S2。避免了 S3 成为 leader 之后，S3 后面新增 4 log 之后，会用 4 log 覆盖 2 log，从而避免了回滚的情况出现。
  
  S1：1、2、3；
  
  S2：1、2；
  
  S3：1；
只有获得超过半数投票的节点才会成为 leader。

注意事项

在没有 leader 的情况下，数据是没办法写入的。
**Etcd 集群中 etcd 节点数最好都为奇数，偶数个的话可能会导致选举失败。**比如，下面有两个节点同时变成了 candidate，之后每一个 candidate 都仅收到了其中一个节点的 vote，那么每个 candidate 都会有 2 votes，但是在这轮 terms 中不能再获取更多的 votes 了。那么，这轮 term 就会以没有 leader 结束，接下去会重新开始一轮新的 term（term+1）。

日志复制

Raft 协议选举出 leader 后，etcd 集群就可以对外提供服务了（没有 leader 的话是不能对外提供服务的）。leader 会负责接收所有客户端的写入请求，并完全负责 log replicated。

整个 log replicated 的过程大致所示，

客户端发起写请求，写请求包含了一个待状态机执行的命令。
leader 收到写请求后，将这条命令作为新的一条日志追加到自己的日志模块中，日志中同时添加上 leader 接收到该请求时的 term 号，并且该日志会有相应的序号。类似如下所示的结构，

如果是 follower 接收到的，则这个请求会转发给 leader。
与此同时，leader 并行地向其他 follower 节点发送添加日志的请求，让这条日志在其他 follower 节点上也得到复制。
leader 会等待其他节点的回复，如果超过半数的 follower 都回复了，leader 会将该日志标记为已提交（commited）。
当日志被标记为已提交后，leader 会将该条日志 apply 到自己的状态机，并给客户端回复。这里无需关注其他 follower 节点有没有 apply，因为有相应的日志了，通过日志可以最终达成一致。
同时，leader 也会发消息告诉其他 follower 节点，自己已 applied 该条日志了。如果 follower 宕机或者运行很慢，甚至丢包，leader 会无限的重试，直到所有的 followers 都存储了相同的日志。
其他 follower 节点也会 apply 该条日志。

日志复制规则

只附加原则

一旦日志条目被认定为已提交（committed），该日志条目就不会被删除或覆盖，只能追加日志条目。
日志匹配

是指两个节点上的某个日志条目的 index 和 term 相同，那么在该 index 之前的所有日志条目都应该相同。

Leader 在发送追加日志条目的消息时，会把该日志条目之前的日志条目的索引位置和任期号也包含在发送的消息里面。Follower 节点在收到之后，会检查相同索引位置的任期号是否与 Leader 一致，一致才能追加新的日志条目。否则步步回退，直到相同索引位置的任期号与 Leader 一致，才开始继续慢慢增加 Leader 中的后续日志条目。由于每次增加一个日志条目的时候，都要求上一个日志条目和 leader 一致，所以最终整个日志条目序列也是一致的。

比如下图中，假设 leader 中已 commited 的日志条目最大的 index 是 9，此时 leader 向其他节点发送追加 index 为 10 的日志条目的消息时，会把 index 为 9，term 为 6 的信息也发送过去。假设发送了 follower a，follower 经过一致性检查发现自己 index 为 9 的地方，term 也是 6，则会追加 index 为 10 的日志条目。假设发送给了 follower f，follower f 经过一致性检查，发现 index 为 9 的地方，term 为 3，此时会拒绝添加，leader 收到这个消息。leader 之后给 follower f 发送追加 index 为 9 的日志条目，同样拒绝。以此类推，直至回退到发送 index 为 4 的日志条目时，一致性检查通过，然后 follower 会覆盖 index 为 4及之后的日志条目。