Raft共识算法

最常用的共识算法

Raft 算法属于 Multi-Paxos 算法，它是在兰伯特 Multi-Paxos 思想的基础上，做了一些简化和限制，比如增加了日志必须是连续的，只支持领导者、跟随者和候选人三种状态。

Raft 算法是现在分布式系统开发首选的共识算法。之前的系统可以用Paxos算法，比如Cubby、Spanner，而现在的分布式系统大多选择Raft算法，如 Etcd、Consul、CockroachDB。从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

假设我们有一个由节点 A、B、C 组成的 Raft 集群，因为 Raft 算法一切以领导者为准，所以如果集群中出现了多个领导者，就会出现不知道谁来做主的问题。在这样一个有多个节点的集群中，在节点故障、分区错误等异常情况下，Raft 算法如何保证在同一个时间，集群中只有一个领导者呢？

一. 领导者选举

成员身份，又叫做服务器节点状态，Raft 算法支持领导者（Leader）、跟随者（Follower）和候选人（Candidate） 3 种状态。

跟随者：默默地接收和处理来自领导者的消息，当等待领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。
候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者。
领导者：一切以领导者为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息。

Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。Raft 算法还实现了领导者任期（Leader Lease）的特性。

节点间是如何通讯的？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举中，需要用到这样两类的 RPC：

请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；
日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

什么是任期？

Raft 算法中的领导者也是有任期的，每个任期由单调递增的数字（任期编号）标识。任期编号是随着选举的举行而变化的：

跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号；
如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。

Raft 算法中的任期不只是时间段，而且任期编号的大小，会影响领导者选举和请求的处理：

Raft 算法约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态；
Raft 算法约定，如果一个节点接收到一个包含较小的任期编号值的请求，那么它会直接拒绝这个请求。

选举有哪些规则？

在 Raft 算法中，约定了以下这些选举规则：

领导者周期性地向所有跟随者发送心跳消息（即不包含日志项的日志复制 RPC 消息），通知大家我是领导者，阻止跟随者发起新的选举;
如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，推举自己为候选人，发起领导者选举;
在一次选举中，赢得大多数选票的候选人 (大多数选票是指集群成员半数以上的选票)，将晋升为领导者;
在一个任期内，领导者一直都会是领导者，直到它自身出现问题（比如宕机），或者因为网络延迟，其他节点发起一轮新的选举;
在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票;
日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。

随机超时时间是什么？

除了选举规则外，有时还需要避免一些会导致选举失败的情况，比如同一任期内，多个候选人同时发起选举，导致选票被瓜分，选举失败。Raft 算法是通过随机超时时间来避免这个问题的。

Raft 算法巧妙地使用随机选举超时时间的方法，把超时时间都分散开来，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，这样就能减少因选票瓜分导致选举失败的情况。这里的随机超时时间有2种含义：

跟随者等待领导者心跳信息超时的时间间隔，是随机的；
如果候选人在一个随机时间间隔内，没有赢得过半票数，那么选举无效了，然后候选人发起新一轮的选举，也就是说，等待选举超时的时间间隔，是随机的。

小结

Raft 算法和兰伯特的 Multi-Paxos 不同之处，主要有 2 点。首先，在 Raft 中，不是所有节点都能当选领导者，只有日志较完整的节点（也就是日志完整度不比半数节点低的节点），才能当选领导者；其次，在 Raft 中，日志必须是连续的；
Raft 算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导，也极大地减少了选举失败的情况；
本质上，Raft 算法以领导者为中心，选举出的领导者，以“一切以我为准”的方式，达成值的共识，和实现各节点日志的一致。

二. 日志复制

在 Raft 算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端写请求后，处理写请求的过程就是一个复制和应用（Apply）日志项到状态机的过程。

日志项是一种数据格式，它主要包含用户指定的数据，也就是指令（Command），还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。

指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端指定的数据。
索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单调递增的整数号码。
任期编号：创建这条日志项的领导者的任期编号。

如何复制日志？

可以把 Raft 的日志复制理解成一个优化后的二阶段提交（将二阶段优化成了一阶段），减少了一半的往返消息，也就是降低了一半的消息延迟。日志复制的具体过程是：

首先，领导者接收到客户端的写请求，进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上；
接着，如果领导者接收到大多数的“复制成功”响应后，它将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的“复制成功”响应，那么就返回错误给客户端（半同步复制）；
然后是 Raft 中的一个优化，领导者不直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交（Commit）的日志项索引值。所以通过心跳消息或新的日志复制 RPC 消息，跟随者就可以知道领导者的日志提交位置信息，就会将这条日志项应用到它的状态机。

不管是领导者还是跟随者，最终日志项的应用，都是分为先记录再提交两个阶段。且上面是一个理想状态下的日志复制过程。

如何实现日志的一致？

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。具体也分为2个步骤：

首先，领导者通过日志复制 RPC 的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值;
然后，领导者强制跟随者更新覆盖不一致日志项，实现日志的一致。

领导者通过日志复制 RPC 一致性检查，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各节点日志的一致。需要注意的是，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。

小结

在 Raft 中，副本数据是以日志的形式存在的，其中日志项中的指令表示用户指定的数据。
兰伯特的 Multi-Paxos 不要求日志是连续的，但在 Raft 中日志必须是连续的。而且在 Raft 中，日志不仅是数据的载体，日志的完整性还影响领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者。
Raft 是通过以领导者的日志为准，来实现日志的一致的。

三. 成员变更

成员变更，不仅是 Raft 算法中比较难理解的一部分，非常重要，也是 Raft 算法中唯一被优化和改进的部分。最初实现成员变更的是联合共识（Joint Consensus），但这个方法实现起来难，后来 Raft 的作者就提出了一种改进后的方法单节点变更（single-server changes）。

配置（Configuration）是成员变更中一个非常重要的概念，它是说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合。

成员变更的问题

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者（脑裂split-brain）。如果出现了 2 个领导者，那么就违背了“领导者的唯一性”的原则，进而影响到集群的稳定运行。

通过单节点变更解决成员变更的问题

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。

例如，起初集群的配置为[A, B, C]，我们先向集群中加入节点 D，这意味着新配置为[A, B, C, D]。成员变更，是通过这么两步实现的：

第一步，领导者（节点 A）向新节点（节点 D）同步数据；
第二步，领导者（节点 A）将新配置[A, B, C, D]作为一个日志项，复制到新配置中所有节点（节点 A、B、C、D）上，然后将新配置的日志项应用（Apply）到本地状态机，完成单节点变更。

在正常情况下，不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。也就是说，不会同时存在旧配置和新配置 2 个“大多数”。

不管集群是偶数节点，还是奇数节点，不管是增加节点，还是移除节点，新旧配置的“大多数”都会存在重叠。

需要注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，导致集群出现 2 个领导者的情况。如果遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项应用后，再执行成员变更请求。具体的实现可以参考 Hashicorp Raft 的源码中的是 runLeader() 函数中：

noop := &logFuture{
        log: Log{
               Type: LogNoop,
        },
}
r.dispatchLogs([]*logFuture{noop})

绝大多数 Raft 算法的实现，采用的都是单节点变更的方法（比如 Etcd、Hashicorp Raft）。其中，Hashicorp Raft 单节点变更的实现，是由 Raft 算法的作者迭戈·安加罗（Diego Ongaro）设计的，很有参考价值。

总结

Raft 不是一致性算法而是共识算法，是一个 Multi-Paxos 算法，实现的是如何就一系列值达成共识。并且，Raft 能容忍少数节点的故障。虽然 Raft 算法能实现强一致性，也就是线性一致性（Linearizability），但需要客户端协议的配合。在实际场景中，我们一般需要根据场景特点，在一致性强度和实现复杂度之间进行权衡。比如 Consul 实现了三种一致性模型：

default：客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时（在 leader leasing 时间内），返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端是可能读到旧数据的，比如此时发生了网络分区错误；
consistent：客户端访问领导者节点执行读操作，领导者在和大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况下，客户端读到的都是最新数据；
stale：从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据。

一般而言，在实际工程中，Consul 的 consistent 就够用了，可以不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值就可以了。

比如为了实现幂等操作，我们使用一个编号 (ID) 来唯一标记一个操作，并使用一个状态字段（nil/done）来标记操作是否已经执行，那么只要我们能保证设置了 ID 对应状态值为 done 后，能立即和一直读到最新状态值就可以了，也就通过防止操作的重复执行，实现了冥等性。

又比如 QQ 后台的海量服务分布式系统，其中配置中心、名字服务以及时序数据库的 META 节点，采用了 Raft 算法。在设计时序数据库的 DATA 节点一致性时，基于水平扩展、性能和数据完整性等考虑，就没采用 Raft 算法，而是采用了 Quorum NWR、失败重传、反熵等机制。这样安排不仅满足了业务的需求，还通过尽可能采用最终一致性方案的方式，实现系统的高性能，降低了成本。