分布式共识算法Raft

Raft 算法

Raft 是一种旨在易于理解的共识算法。它在容错性和性能上与 Paxos 相当。不同之处在于它被分解为相对独立的子问题，并且清晰地解决了实际系统所需的所有主要部分。

什么是共识？
共识是容错分布式系统中的一个基本问题。共识涉及多个服务器就值达成一致。一旦他们就某个价值做出决定，该决定就是最终决定。当大多数服务器可用时，典型的共识算法会取得进展；例如，一个由 5 台服务器组成的集群即使有 2 台服务器发生故障，也可以继续运行。如果更多服务器出现故障，它们将停止前进（但永远不会返回不正确的结果）。

共识通常出现在复制状态机的上下文中，这是构建容错系统的一般方法。每个服务器都有一个状态机和一个日志。状态机是我们想要容错的组件，比如哈希表。即使集群中的少数服务器出现故障，客户端也会认为它们正在与单个可靠的状态机进行交互。每个状态机都从其日志中获取输入命令。在我们的哈希表示例中，日志将包含诸如将 x 设置为 3 之类的命令。共识算法用于就服务器日志中的命令达成一致。共识算法必须确保如果任何状态机将 set x to 3 作为第 n 个命令应用，则没有其他状态机将应用不同的第 n 个命令。结果，每个状态机处理相同系列的命令，从而产生相同系列的结果并到达相同系列的状态。

特性

Raft 算法在许多方面和现有的共识算法相似，但它也有自己的特性：

强领导人：和其他一致性算法相比，Raft 使用一种更强的领导能力形式。比如，日志条目只从领导人发送给其他的服务器。这种方式简化了对复制日志的管理并且使得 Raft 算法更加易于理解。
领导选举：Raft 算法使用一个随机计时器来选举领导人。这种方式只是在任何一致性算法都必须实现的心跳机制上增加了一点机制。在解决冲突的时候会更加简单快捷。
成员关系调整：Raft 使用一种共同一致的方法来处理集群成员变换的问题，在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠，这就使得集群在成员变换的时候依然可以继续工作。

实际应用

Etcd 使用Go语言编写，kubernetes 就应用etcd 实现。

Consul 使用Go语言编写

Kafka3

TiKV

知识体系

主题	分类
Leader选举	Leader选举过程
	Leader宕机
	多期选举
日志复制	日志复制流程
	网络分区
安全性	选举限制
	提交之前任期的日志
成员变更	集群成员变更的问题
	单节点变更策略及问题
	联合共识算法
日志压缩

领导者选举

Raft 使用一种心跳机制来触发领导人选举。当服务器程序启动时，他们都是跟随者身份。一个服务器节点继续保持着跟随者状态直到以下两种情况发生：

他从领导人或者候选人处接收到有效的 RPC请求。自己重置选举超时时间，依旧保持追随者身份。
如果一个跟随者在一段时间里没有接收到任何消息，也就是选举超时，那么他就会认为系统中没有可用的领导人,将会自己成为候选人并发起选举以选出新的领导人。

领导者选举

系统中所有的节点都以追随者状态开始。如果追随者没有收到领导者的来信，那么他们可以成为候选人。

然后，候选人为自己投票并且请求其他节点投票。节点将回复他们的投票。如果候选人从大多数节点获得选票，则该候选人将成为领导者。此过程称为领导者选举。

一个节点会处于三种状态中的一种：

Follower 追随者：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志。
Candidate 候选者：Leader选举过程中的临时角色。
Leader 领导者：接受客户端请求，并向Follower同步请求日志，当日志同步到大多数节点上后告诉Follower提交日志。

下面是三种状态的转换过程：

服务器状态。跟随者只响应来自其他服务器的请求。如果跟随者接收不到消息，那么他就会变成候选人并发起一次选举。获得集群中大多数选票的候选人将成为领导人。在一个任期内，领导人一直都会是领导人，直到自己宕机了。

时间被划分成一个个的任期，每个任期始于一次选举。在选举成功后，领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导人而结束。任期之间的切换可以在不同的时间不同的服务器上观察到。

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

所有服务器：

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

跟随者：

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

候选者：

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

领导者：

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

Leader选举：

在 Raft 中，有两个控制选举的超时设置。

首先是选举超时。

选举超时是追随者在成为候选人之前等待的时间。

选举超时随机化为 150 毫秒和 300 毫秒之间。

选举超时后，追随者成为候选人并开始新的选举任期…为自己投票。

并向其他节点发送请求投票消息。

如果接收节点在此期限内尚未投票，则它将投票给候选人…节点将重置其选举超时。

一旦候选人获得多数票，它就成为领导者。

领导者开始向其关注者发送“追加条目”消息。

这些消息按检测信号超时指定的时间间隔发送。

然后，关注者响应每个“追加条目”消息。

此选举任期将持续到关注者停止接收检测信号并成为候选人。

领导者会定时发送心跳（heartbeat）给所有追随者，让追随者知道集群的领袖还在运作，而每个追随者都会设计超时机制（一般为150-300ms），当超过一定时间没有收到心跳，集群就会进入选举状态。

日志复制

一旦选出了领导者，我们需要将对系统的所有更改复制到所有节点。这是通过使用用于心跳的相同附加条目消息来完成的。让我们来看看这个过程。

选举Leader后，对系统的所有更改都通过领导者进行。每个更改都作为条目添加到节点的日志中。首先，客户端向领导者发送更改。更改追加到领导者的日志中，现在当前的日志条目还未提交，因此不会更新节点的值。要提交条目，节点首先将其复制到追随者节点，然后，领导者等待，直到大多数节点都写入了条目。该条目现在在领导节点上提交，然后领导者通知追随者该条目已提交。并向客户端发送响应。群集现在已经就系统状态达成共识。此过程称为日志复制。

网络分区下的处理：

Raft 可以在网络分区时保持共识，我们知道网络分区容易使一个分布式系统产生脑裂，我们看一下Raft是如何避免的？

让我们添加一个分区将 A、B 与 C、D 、E 分开。由于我们的分区，我们现在有两位不同任期的领导人。让我们添加另一个客户端并尝试更新两个领导者。一个客户端将尝试将节点 B 的值设置为“3”。节点 B 无法复制到多数，因此它的日志条目保持未提交状态。

另一个客户端将尝试将节点 C 的值设置为“8”。这会成功，因为它可以复制到大多数。现在让我们修复网络分区。节点 B 将看到更高的选举任期并下台。节点 A 和 B 都将回滚它们未提交的条目并匹配新领导者的日志。我们的日志现在在整个集群中是一致的。

安全性

选举限制

Raft 使用了一种更加简单的方法，它可以保证选举出的新Leader拥有所有之前任期中已经提交的日志，而不需要传送这些日志条目给领导人。这意味着日志条目的传送是单向的，只从领导人传给跟随者，并且领导人从不会覆盖自身本地日志中已经存在的条目。

拒绝投票

简单说：在候选人选举过程中，如果追随者受到一个候选人的投票请求，那么追随者会检查候选人的日志信息，如果日志比自己的更新或者相同，则投票给它，反之如果日志信息都没有自己的新，那么追随者就没有理由投票给该候选人，就会拒绝投票。

设计细节：

请求投票的RPC请求中包含了候选人的日志信息。
Raft 通过比较两份日志的任期号和最后一条日志条目的索引值来定义谁的日志比较新。如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志索引号大的的那个就更加新。

提交之前任期的日志

注意，本话题要讨论的是：如果允许提交之前任期的日志，将导致什么问题？然后再讲Raft的正确做法。

a图中，S1节点为Leader，在日志索引项为2的位置写入数值2，然后复制日志到其他节点，当只有S2 同步后，S1就宕机了，（此时并没有超半数节点同步了数据2）；

b图中，S5经过选举后成为Leader（S3、S4、S5投票同意），在日志索引项为2的位置写入数值3，然后宕机。

c 图中，S1再次成为Leader，（注意这是错误示范）它将之前任期的未提交的日志数据进行同步，现在S1、S2、S3 节点在日志索引2的位置都有了数值2，超半数节点同步完成，S1提交本地日志，然后继续在日志索引3的位置写入新数据4。然后宕机。

d1图中，S5再次成为Leader，然后同步往期未提交的日志，也就是索引2位置的数据3，最后的结果是所有节点的索引2位置的数据被修改了，而之前数据2已经被超半数节点写入日志，现在却被覆盖掉了，这和Raft的规则设计是违背的！所以Leader节点直接同步往期未提交的日志这种策略是有问题的。

d2图中，我们假设不按照c图的做法运行，当S1成为Leader后，不着急同步往期日志数据，而是去同步最新的当期日志数据4，那么按照Raft日志的匹配规则：日志4如果能提交，它前面的日志也会自动提交。所以S2、S3在同步数据4的同时会自动同步数据2，这样的话就不会出现d1图中的现象。而在后续如果S1再次宕机，S5、S4是不可能成为Leader的，因为他们的日志数据不如S2、S3新，S2或S3成为Leader后会把这些数据同步到S4和S5，此时系统的数据就达成一致性了。

成员变更

集群节点变更问题

要保证Raft协议的安全性，就是要保证任意时刻，集群中只有唯一的leader节点。如果不加限制条件，动态向集群增删节点，有可能会导致存在多个leader的情况。如下图所示：

图中有两种颜色的配置，绿色表示旧的集群配置（C_old），蓝色表示新的集群配置（C_new），如果不加任何限制，直接将配置启用，由于不同的集群节点之间，存在时间差，那么可能出现这样的情况：

Server{1,2}：当前都使用旧的集群配置，所以可能选出server1为集群的leader。
Server{3,4,5}：当前都使用新的集群配置，可能选出server3为集群的leader。

由上图可以看到：如果不加任何限制，直接应用新的集群配置，由于时间差的原因，可能导致集群中出现两个不同leader的情况。

raft 解决成员变更问题提供了两种方法：

联合共识变更（Joint Consensus）
单步成员变更（One Server ConfChange）

单节点成员变更

单节点成员变更，指的是每次只添加或删除一个节点，这样就能保证集群的安全性，不会在同一时间出现多个leader的情况。之所以能有这个保证，是因为每次变更一个节点，那么新旧两种配置的半数节点肯定存在交集。以下图来说明：

上图演示了向偶数或奇数的集群增删一个节点的所有可能情况。不论哪种情况，新旧配置都有交集，在每个任期只能投出一张票的情况下，是不会出现多leader情况的。

有了上面的理论基础，下面来看单节点集群变更的全流程，当下发集群节点变更配置时，新的配置会以一种特殊的日志方式进行提交：

普通日志：半数通过，提交成功时，会传给应用层的状态机。
配置变更类日志：半数通过，提交成功时，集群节点将以新的集群配置生效。

其流程如下：

将集群配置变更数据，序列化为日志数据，需要将日志类型标记为集群配置变更类的日志，提交给leader节点。
leader节点收到日志后，需要存储该日志的索引为未完成的集群配置变更索引，像其它正常日志一样处理：先写本地的日志，再广播给集群的其他节点，半数应答则认为日志达成一致可以提交了。如果提交了这类日志，可以将前面保存的未完成的集群配置变更索引置为空了。
集群配置变更日志提交之后，对照新旧的集群变更数据，该添加到集群的添加到集群，该删除的节点停机。

问题

Raft集群的单步变更算法，虽然看起来”简单“，但是实践起来有不少细节需要注意。
虽然论文里提到单步变更算法比之Joint Consensus算法更为简单，很多开源的Raft实现都已经以Joint Consensus算法做为默认的实现了。

联合共识变更

除了上面的单节点变更，有时候还需要一次提交多个节点的变更。但是按照前面的描述，如果一次提交多个节点，很可能会导致集群的安全性被破坏，即同时出现多个leader的情况。因此，一次提交多节点时，就需要联合共识（Joint Consensus）。

所谓联合共识，就是将新旧配置的节点一起做为一个节点集合，只有该节点集合达成半数一致，才能认为日志可以提交，由于新旧两个集合做了合并，那么就不会出现多leader的情况了。具体流程如下：

leader收到成员变更请求，新集群节点集合为C_new，当前集群节点集合为C_old，此时首先会以新旧节点集合的并集C_{old,new}做为一个集群配置变更类的日志，走正常的日志提交流程。注意，这时候的日志，需要提交到C_{old,new}中的所有节点。
当C_{old,new}集群变更日志提交之后，leader节点再马上创建一个只有C_new节点集合的集群配置变更类日志，再次走正常的日志提交流程。这时候的日志，只需要提交到C_new中的所有节点。
当C_new日志被提交之后，集群的配置就能切换到C_new对应的新集群配置下了。而不在C_new配置内的节点，将被移除。

可以看到，多节点联合共识的提交流程分为了两次提交：

先提交新旧集合的交集C_{old,new}。
再提交新节点集合C_new。

以下图来说明，这几个阶段中，集群的安全性都得到了保证：

多节点联合共识

C_{old,new}配置提交之前：在这个阶段，集群中的节点，要么处于C_old配置下，要么处于C_new,old配置之下。此时，如果集群的leader节点宕机，那么将会基于C_old或者C_new,old配置来选出新的leader，而不会仅仅基于C_new，因此不会选出不同的leader。
C_{old,new}配置提交之后，C_new下发之前：如果这时候leader宕机，只会基于C_{old,new}的配置选出leader，因此也不会选出不同的leader。
C_new下发但还未提交时：如果这时候leader宕机，只会基于C_{old,new}或者C_new的配置选出leader，同时也不再会发给仅仅在C_old中的节点了，所以无论是哪个配置，都需要得到C_new的半数同意，因此不会选出不同的leader。
C_new提交之后：此时集群中只有一种配置了，安全性得到了保证。