【论文阅读】Raft

论文链接 In Search of an Understandable Consensus Algorithm (Extended Version)

1、背景

共识算法是指能够让一组机器在一起协作并且能够容忍部分机器的故障。过去几十年，Paxos是最主流的共识算法，但是它较难理解，在现实中使用需要考虑到很多复杂的变化。于是提出了一种Raft的共识算法，其用于教学和实现更加简单。经过实验测试，在两个大学中对43个学生进行教学，有33个能够较好的理解并回答关于Raft的问题。

作者介绍了三个特性：

强领导机制：相比于其他共识算法，Raft具有更强领导者角色。意思是在一组机器中，选出一个领带者，所有的日志数据流由这个领导者发送给其他机器

领导选举：Raft使用随机计时器来选举领导，这个方法只是在心跳包机制中引入了一个小改动，能够更简单快速的解决冲突

成员变动：Raft在处理集群成员变动中使用了联合共识的方法，在调整过程中两组不同配置的大多数集群都会重叠，这样能够在配置变动中能够正常运行。

2、复制状态机

复制状态机是用来解决分布式系统中故障容错性，通常用来管理领导者选举和保存配置信息，使其在出现领导者宕机也能恢复存活。具体的例子有Chubby和Zookeeper。

如下图所示，client提交信息给Server，通常为leader，leader通过共识模块将数据转发给其他client，确保所有的机器的日志最终都保存了相同的请求和顺序，同时把执行的命令写入各自日志条目。当大多数节点确认后，将其标注为已提交。所有的节点将更改保存到各自的状态机，一旦命令被每个机器完整的复制，将输出结果发送给client。

复制状态极通常用复制日志来实现，每个服务器保存一组包含指令的日志，能够按照顺序执行。同时保证每个状态机执行的顺序和结果是一致的，内容也是相同。

共识算法的任务正是维护这种复制状态机，由以下特性：

安全性：在出现非拜占庭情况（恶意节点），如网络延迟，数据包丢失，重复等异常情况，不返回错误结果。

可用性：服务器之间能互相通信，在经典的五台服务区中可以允许任意2台故障。故障恢复后能重新加入集群。

容错性：不依赖时序，能处理时钟错误和消息延迟

及时性：一般情况，指令在收到大多数集群相应后快速完成，少速慢节点不影响系统性能。

3、Raft共识算法

中间有大篇幅批判Paxos，就此跳过。

Raft是一个管理复制日志的算法，通过选举领导者来实现数据一致性。当领导者收到来自客户端日志条目，会把日志复制给其他服务器，并告诉其他服务器什么时候可以把日志安全的保存在状态机中。总的来说，就是一个领导者管理整个系统，如果领导者挂了，再由新的服务器重新选举。

Raft可以将问题拆分为以下三个独立的子问题，

领导选举：当领导者发生故障的时候，一个新的领导者需要被选举出来，确保系统的连续性和稳定性

日志复制：领导者必须从客户端接收日志条目然后复制到集群中的其他节点，并强制要求其他节点的日志和自己保持一致。

安全性：通过状态机来保证安全，如果日志进入了状态机，那么其他服务器就不能在同样的日志索引使用相同命令

3.1 Raft基础概念

raft集群中的服务器在任何时候都包含三种状态，领导者，跟随者，候选者。正常的系统中，有一个领导者，其他跟随者是被动的，不能发起请求，只能被动回应领导者和候选者。领导者负责所有的请求，如果客户端向追随者发起请求则会转发给领导者。跟随者在收不到消息时，变为候选者启动选举，获得多数选票的候选者成为领导者。当领导者宕机，则降级为跟随者。

Raft将时间划分为任意长度的term，每个term开始于选举，选举出领导者管理集群直到任期结束。理论来说领导者只要一切正常，就能够一直继任。Term充当了逻辑始终的作用，序号随着时间递增。由于服务器之间保存的Term周期会不一致，服务器之间会通过交换term信息，小term会被大term覆盖。

Raft服务器之间使用RPC进行通信，仅需要两种类型。RequestVote RPC和AppendEntry RPC，分别用于投票和更新状态机

3.2 领导者选举

Raft使用心跳机制来触发领导者选举。服务启动初始状态为跟随者，跟随者永远是跟随者只要它能一直收到来自领导者和候选者的合法RPC。

追随者在一段时间（选举超时）没有收到消息后，开始发起选举。首先会增加它的周期然后变为竞选状态，然后投自己一票，再调用其他服务器的RequestVote，将一直保持这个状态直到出现，

1. 赢得选举
2. 另一个服务器赢得选举
3. 一段时间没有决出胜负

一个服务器每个周期内只能投一票，先进先出原则，先看到谁的拉票就投谁。如果在投票中收到了领导者消息，观察它Term序号是否比自己的序号大，如果是则认可，如果不是则不予理会。

有种特殊情况，所有的跟随者同时都变成了候选者，选票就会分散，没有赢家。这时就会开启新一轮投票，Raft使用了随机延迟机制，每个服务器的选举会随机延迟（150-300ms），这样就能解决问题。

3.3 日志复制

选出领导者后开始处理客户端请求，每个请求携带一条被复制状态机执行的指令。领导者将指令作为新日志条目追加至日志中，并并行发起附加条目 RPC 给其他服务器复制，当日志条目被安全复制后，领导者将其状态机执行结果返回给客户端，如果跟随者宕机、延迟或网络丢包，领导者也会持续重试 RPC直至所有跟随者存储所有日志条目。（这里论文没说清楚，如果跟随者下线，一直重发太耗费资源了）

日志条目按序编号，包含创建时的任期号及待执行指令。日志条目在满足一定条件时变为可提交状态，即安全地应用到状态机中。领导者决定何时提交日志条目，Raft 算法保证所有提交条目持久化并最终被执行。日志条目在被复制到多数服务器时即被提交，包括前任领导者创建的条目。领导者追踪最大已提交条目索引，并在附加条目 RPC 中包含该索引，使跟随者同步应用已提交条目。通过两种方式保证日志的一致性，一是在一个日志索引对应一个条目，且内容和位置不会更改。二是使用AppendEntry RPC时，领导者会携带之前的条目索引和任期编号，如果跟随者找不到这条索引和任期编号就会拒绝日志条目。

下图展示了一个特殊的情况，a-b丢失了一些日志条目，c-d或者e有多余未提交的条目。f情况特殊，在term2中当选领导者，刚提交到日志就崩溃了，竞选到term3后提交了一些信息又崩溃了。Raft的处理办法是， 当AppendEntries RPC失败，领导者可以强制覆盖跟随者的日志，领导者为每个追随者维护一个尾指针，表示即将写入的位置。如果出现一致性检查失败，尾指针减一，直到和领导者一致，然后会删除冲突条目，追加领导者条目。

文中提出了一个没什么必要的优化方法，发生AppendEntries RPC冲突时，跟随者主动发送这个冲突任期内的第一个条目，直至不冲突，这样减小比对的次数。

3.4 安全性

上面的只谈及领导者选举和添加日志，尚未讨论状态机执行的命令和顺序相同。例如跟随者出现故障导致错过了一些日志，然而又不小心当上了领导者，导致指令执行混乱。接下来会完善机制，保证每个term的新任领导者会拥有之前已提交的完整日志条目。

3.4.1 选举限制

Raft使用了一个简单的机制，保证领导者在选举阶段必须拥有所有已提交的日志，维护日志条目只能领导者流向跟随者这个原则。候选者选举必须通知集群大多数节点，展示其日志最新条目。投票节点如果发现候选者日志最新消息和自己的相比是旧的，那么可以拒绝执行RequestVote RPC。

3.4.2 提交前任日志条目

领导者任期的日志条目被复制到大多数节点则被认为可提交，但是考虑一种情况，领导者在提交前刚好宕机，但是大多数节点已经复制了这个条目，这时一个没有复制这个条目的服务器当选了领导者，不能通过这条日志被复制的数量来决定是否已经提交。Raft原则是领导者不能从跟随者复制数据，一旦成为领导者就只能复制给别者。所以处理方案是，如果领导者保留了前任的日志条目，可以在当前任期内连同旧日志条目一起提交。

假设任期U（U>T），那么领导者中必定包含T任期内的已提交日志，日志匹配原则保证未来领导者同样也会保留最新日志。一句话总结，拥有最新最长日志条目的服务器拥有更高的优先级。

3.4.3 安全性讨论

这里面有几个关键时间点，只有当领导者复制日志给大多数节点才会触发commit，这个commit索引再转发给其他节点表示已提交。考虑两个特殊情况，一、领导者已经把日志复制到大多数节点但尚未提交就宕机了，那么新来的领导者必然包含这个日志的复制，在任期内使用日志一致性检查再一同提交。二、领导者刚复制到少量节点就宕机了，那么这里再包含两种情况，其一，具有最新日志的少量的节点当选领导者，那么可以继续继承日志没有数据丢失。其二，未包含最新日志的节点当选领导者，那么触发强制覆盖，所有节点会和它保持一致，这样就会导致日志丢失。

目前文中并没有说解决方案，谈此处理结果会增加系统的复杂度，所以允许未提交的日志丢失是可接受的。

3.5 跟随者和候选者宕机

RPC操作是幂等性的，即同一条命令触发多次的结果不变。所以这两个宕机最简单的处理方法就是无限调用RPC直到响应。

3.6 时间和可用性

Raft的安全性之一就是不依赖于时钟，执行快慢不会产生错误结果。具体是使用Term序列来表示逻辑时钟。领导者选举时间是最为重要的，要求领导者响应时间要快。保证，

\begin{equation} \text{Broadcast Time} \ll \text{Election Timeout} \ll \text{MTBF} \end{equation}

广播时间在[0.5ms,20ms]，选举时间可以在[10ms,500ms]，故障时间不设限制。

4 集群成员变化

目前假设成员配置是固定的，实际上我们需要动态改变配置。这里提出了一个二阶段方案，第一阶段禁用所有旧配置节点，第二阶段切换配置上线，具体使用联合共识方法。

• 日志条目会备份到两种配置的服务器
• 任一种配置的服务器都可以做领导者
• 选举和提交日志必须同时获得旧配置和新配置的多数确认

领导者接收（new）请求，会把它看作是一个日志条目打包成（old, new）进行复制，正常来说可以和日志一样复制到整个集群。如果领导者提交后中途宕机，具有只有同时拥有（old,new）的服务器才能当领导者，新领导者就会把（new）复制给整个集群。

5 日志压缩

随着时间增长，日志会越来越大开始占用大量内存，以致会丢弃信息。Raft使用快照来解决这个方案，如下图所示，压缩的快照包含日志条目的数量，种类，最终值。每个服务器自己创建一个独立的快照。有时领导者会直接向跟随者（新加入或落后的跟随者）发送快照，通过调用InstallSnapshotRPC 调用。

作者考虑到另一种方式，弃用AppendEntry RPC，全部使用领导者发送快照的模式。这样做的缺点是太占用网络了。快照一般都比较大，每次发送都会大幅影响I/O速度。而且每个服务器在本地创建快照的开销远小于通过网络发送接收的开销。

6 客户端交互

客户端怎样和raft交互？服务器怎样发现领导者？Raft如何保证线性化一致性？

客户端首次启动会随机选一个服务器连接，如果它不是领导者，则拒绝请求，然后返回一个最新领导者的信息。如果这时候领导者宕机，服务器则表现为超时。

如果客户端发送命令后，领导者宕机，那么会重新再发送一次。每个命令会分配一个唯一序列号。如果状态机检测到重复的命令，那么就不会再执行。假如客户端执行只读命令，有可能会获取到过期数据。例如领导者已经被淘汰了但不自知，而新的领导者已经更新了最新数据。所以领导者在回复消息前会通过心跳包问集群的大多数节点它是不是领导者，再处理客户端的消息。

7 实现和评价

作者只用了2000行C++代码（不包括测试）就完成了Raft。在斯坦福大学的分布式系统授课，最终表现的教学效果不错。

Raft是在所有节点可信条件下的共识算法，假如黑客要攻击很简单。首先控制一个节点，伪造多余的日志条目，同时发起投票竞选，这样所有的节点会误认为这个坏节点保存最新的日志条目，从而投票给它。这样就轻易地当选领导者，然后利用领导者的强权直接修改覆盖所有节点日志。现实不太可能发生，因为raft集群用于生产环境下服务提供者，一般不涉及什么机密信息。