# Raft论文阅读记录


# 摘要
Raft是一种用于管理复制日志的共识算法。它的结果等价与Paxos，并且效率相当，但它的结构更容易理解。为了增强可理解性，Raft将共识的关键要素（例如领导者选举、日志复制和安全性）分离开来，并强制执行更强的一致性要求，从而减少了需要考虑的状态数量。此外，Raft 还引入了一种新的集群成员变更机制，该机制通过使用重叠的多数派来保证安全性。

## 1 介绍
论文先讲Paxos太难理解了blabla，所以想要设计一个更让人容易接受的方法，也就是Raft。Raft与其他共识算法类似，但它有几个新特征：
* **更强大的领导者**：领导力的形式更强，比如日志条目仅从领导者流向其他服务器，这简化了复制日志的管理。
* **领导者选举**：使用随机定时器来选举领导者。这只在其他共识算法所需的心跳机制增加了很小的一部分，但是却可以简单而迅速地解决冲突。
* **集群成员变更**：Raft的joint consensus方法通过在成员变更期间维护旧配置（参与算法的服务器集合）和新配置的多数派，确保了系统的高可用性和一致性，这种方法允许集群更换配置时继续正常操作，无需中断。

## 2 复制状态机
在这种方法中，一组服务器上的状态机计算相同状态的完全一致副本，即使某些服务器宕机，这些状态机仍能继续运行。状态机是用来解决分布式系统中的故障容忍问题，比如管理领导者选举，并存储那些可以拯救领导者崩溃的信息。复制状态机的例子包括Chubby和ZooKeeper。
![](./pics/replicated_state_machines.jpg)

复制状态机的实现就是用图1中的复制日志，每个服务器存储一个包含一些列指令的日志，然后所有状态机按顺序执行，每个都有相同顺序的输出结果。

保持复制日志的一致性是共识算法的职责。服务器上共识模块接收到客户的命令后添加到日志中，它与其他服务器的共识模块通信，确保即使某些服务器发生故障，每个日志最终都包含相同顺序的请求，因此这些服务器看起来形成了一台单一、可靠的状态机。

实际系统的共识算法有以下特性：
* 安全性：在所有非拜占庭条件（没有叛徒）下不会返回错误结果。
* 可用性：只要大多数服务器正常，就可以保持功能可用。
* 不依赖事件来确保日志一致性，故障的时钟和极端消息延迟只会导致可用性问题。
* 一条指令可以在集群的大多数节点对一轮RPC响应后立即完成，少数慢的节点不影响性能。

## 3 Paxos有什么问题？
1. 作者再次吐槽Paxos尤其难以理解，blabla
1. Paxos架构不适合构建实际系统，主要由于单决策分解（我就不尝试理解了）。

## 4 为了更好理解而设计
基于对Paxos的槽点，作者选择了两种普遍使用的技术：
1. 问题分解。将问题划分为可以相对独立解决、解释和理解的单独部分。
1. 通过减少需要考虑的状态数量来简化状态空间，使系统更加一致，并尽可能消除不确定性。

## 5 Raft共识算法
Raft是一种管理复制日志（如第二节讲述的形式）的算法。图2以浓缩形式总结了该算法，图3列出了该算法的关键属性。
![](./pics/2.png)
![](./pics/3.jpg)

Raft实现共识，先第一步选举一个领导者，然后将管理复制日志的全部责任交给它。领导者从客户那边接收日志，复制他们到其他服务器，然后告知这些服务器何时才能安全的把日志条目应用到状态机。拥有一个领导者可以简化复制日志的管理，比如领导者可以在不咨询其他服务器的情况下决定新条目在日志中的存放位置，并且数据以简单的方式从领导者流向其他服务器。如果领导者发生故障或与其余服务器断开连接，则选举一个新的领导者。

根据领导者方法，Raft把共识问题拆解为三个相对独立的子问题：
* 领导者选举
* 日志复制
* 安全性

### 5.1 Raft基础知识
一个Raft集群一般有五个服务器，容错能力是两台崩溃。任何时刻，每个服务器的状态是这三种之一：**领导者、跟随者、候选者**。正常情况下一个是领导者，其他服务器都是跟随者。跟随者是被动的：它们只会响应请求。领导者处理所有客户请求（如果客户联系跟随者，跟随者会重定向给领导者）。候选者是用来选举新领导者的。图4描述了状态和它们的转换。

![](./pics/4.jpg)

Raft把时间划分为任意长度的任期，如图5。每个任期从一次选举开始，一个或多个候选者尝试成为领导者，具体见5.2。某些情况下，选举可能导致票选分散，这个任期会没有领导者，马上一个新的选举会开始，Raft会保证每个任期只有最多一个领导者。

![](./pics/5.jpg)

任期在Raft中充当逻辑是中，并允许服务器检测过时的信息，例如旧领导者。每个服务器存储了一个***当前任期变号***，随时间单调增长。服务器通信时会交换该值，若是发现该值不一样，则会更新为更大的那个。如果领导者或者候选者发现自己的当前任期编号过期了，就会立即恢复为跟随者状态。如果服务器收到带有过期任期编号的请求，会拒绝该请求。

Raft服务器通信使用远程程序调用（RPCs），基本的共识算法只需要两种RPCs。***RequestVote RPCs***由候选者在选举时发起的，还有***AppendEntries RPCs***是由领导者发起的，用来复制日志条目和提供一种心跳的形式（5.3）。服务器在一段时间没收到回应时会重发RPCs，它们并行发送RPCs以提高性能。

### 5.2 领导者选举

Raft使用一种心跳机制来触发领导者选举。服务器刚开始都是跟随者，直到收到了来自领导者或者候选者的RPCs。领导者会定期发送心跳（不携带日志条目的AppendEntries RPCs）给所有跟随者来维持它的权威。如果一个跟随者一段时间没有收到通信，也叫做选举超时时间，那么它就会认为没有有效领导者并发起一个新的选举。

用来开启选举，一个跟随者增加当前任期编号并转换为候选者。然后它为自己投票，并行发送RequestVote RPCs给集群中所有其他服务器。一个候选者保持它的状态直到以下三种情况之一发生：

* （a）它赢得选举。一器一票，在同一任期获得大多数服务器选票就赢得选举。一旦候选者赢得选举，它就成为领导者并发送心跳信息确立权威，防止新的选举发生。

* （b）另一个服务器赢得选举。等待投票时，候选者可能收到心跳信息，如果包含在RPC中的任期编号至少和自己一样大，他就认为是合法的新领导者并切换回跟随者。如果RPC中的任期编号比自己小，该候选者就拒绝该RPC，保持候选者状态。

* （c）选举超时。如果同时有很多候选者，投票可能很分散，导致没有候选者获得大多数票。当这种情况发生时，每个候选者都会超时，通过增加任期编号并发起新一轮的RequestVote RPC来启动新的选举。然而，如果没有额外的措施，选票分散的情况可能会无限重复下去。

Raft使用**随机化的选举超时时间**来确保选票分散的情况很少发生并能被快速解决，这样大部分情况下只有一个服务器会超时。刚开始的时候，第一个超时的服务器会发起选举并赢得选举，发送心跳，在其他服务器超时之前确立领导地位。

### 5.3 日志复制
领导者一经确定就开始处理客户端请求。每个客户请求包含一个状态机执行的命令，领导者把这个命令加入到自己的日志下面作为新条目，然后并行发送AppendEntries RPCs给其他服务器来复制条目。当条目被安全复制后，领导者把条目应用到自己的状态机，返回结果给客户端。如果跟随者发生崩溃、运行缓慢或者数据包丢失，领导者会无限重试AppendEntries RPCs，直到条目被复制成功。

日志的组织如图6，每个日志条目都存储一个状态机命令加上收到条目时的任期编号。在日志条目中的任期编号用来检测日志间的非一致性，确保图3中的一些特性。每个日志条目也有一个整型索引来标志他在日志中的位置。
![](./pics/6.jpg)

领导者决定何时可以将日志条目安全地应用到状态机上，这样的条目被称为***已提交committed***。Raft保证已提交的条目是持久化的，并且最终会被所有可用的状态机执行。当创建该条目的领导者已经在**大多数服务器上复制了该条目时，日志条目就被视为已提交**，这也会提交所有先前的条目。领导者会跟踪其已知最高的已提交索引，并在未来的AppendEntries RPC（包括心跳消息中包含该索引，以便其他服务器最终也能获知这一信息。**一旦跟随者得知某个日志条目已被提交，它就会按照日志顺序将其应用到本地状态机上。**

设计这个日志机制是为了在不同的服务器上保持高度的一致性，简化系统操作、更加可预测而且是确保安全性的关键部分。Raft维护了以下属性，这些属性共同构成了图3中的日志匹配属性（Log Matching Property）：
* 如果两个不同日志中的条目具有相同的索引和任期号，那么它们**存储的是相同的命令**。（由于领导者在给定的任期内，对于一个给定的日志最多创建一个条目，且条目在日志上的位置永远不会改变）
* 如果两个不同日志中的条目具有相同的索引和任期号，那么这**两个日志在所有先前的条目上都是完全相同的**。（因为领导者发送RPC时会有一致性检查，跟随者接收新条目的RPC时会检查日志中是否找得到前一条目，否则会拒绝新条目）

因此，每当AppendEntries RPC成功返回时，领导者就知道跟随者的日志在新条目范围内与自身的日志完全一致了。

**然而，领导者崩溃可能导致日志不一致**，这些不一致可能会在一系列领导者和跟随者崩溃过程中加剧。图7展示了不一致性的各种方式。目录的缺失条目或多余条目可能跨越多个任期。

![](./pics/7.jpg)

Raft中，领导者通过强制跟随者的日志复制自己的日志来处理不一致性，即被领导者覆盖。5.4节将展示，当结合一个额外的限制时，这样子是安全的。

为了做到这一覆盖，领导者必须找到两者最后保持一致的那个条目，然后把该条目之后的所有条目发给跟随者。领导者为每个跟随者维护一个`nextIndex`，表示将发送给它的下一个条目索引。每次发送AppendEntries RPC时执行一致性检查，如果不一致则会被拒绝，领导者会**递减**`nextIndex`并重试AppendEntries RPC直到一致为止。之后追加的条目会覆盖原先任何冲突的条目。

通过这种机制，领导者在上任时不需要采取任何特殊措施来恢复日志的一致性。它只需开始正常操作，日志会在AppendEntries一致性检查失败时自动收敛。领导者从不覆盖或删除其自身日志中的条目（如图3中的 Leader Append-Only Property 所述）。

### 5.4 安全性
然而截止目前描述的来看，这些机制并不能确保每个状态机以正确的顺序执行相同的命令。比如一个跟随者可能在领导者提交了几个日志目录后变得不可用，然后它可能被选举为领导者并用新条目覆盖这些已提交的条目。导致不同状态机可能执行不同序列。

#### 5.4.1 选举限制
在任何基于领导者的共识算法中，领导者都要最终存储全部已提交的日志条目，这些算法开发了额外的机制来找出那些丢失条目并传递给新领导。但可惜这带来了巨大的额外复杂度。Raft用了一种更简单的方式，**它保证从选举开始，先前领导者的所有日志条目都会出现在新领导者上**，不需要额外的传递。这意味着日志条目单向流动，从领导者到跟随者，领导者永远不会重写已有的日志。

为了得到选举，候选者必须按顺序联系大部分服务器，意味着每个已提交的条目必须出现在它们其中一个服务器上。如果候选者的日志已经是这大部分服务器中**最新**的了，那么就代表它已经包含了所有已提交条目。RequestVote RPC实现了这一限制：RPC包含了候选者的日志信息，投票者若发现自己日志比它新，就会拒绝该投票。

#### 5.4.2 提交前一个任期的条目
如果领导者在提交条目之前就崩溃了，那么未来的领导者会尝试完成条目复制。然而，**领导者不能认为只要之前的条目被大多服务器存储，这个条目就是已提交了**。图8描述了一个情况，就是一个旧的日志条目已经被大多服务器存储，但仍然可以被未来的领导覆盖。

![](./pics/8.jpg)

为了消除如图8中所示的问题，**Raft从不通过计算副本数量来提交之前任期的日志条目。只有当前领导者任期内的日志条目可以通过计算副本数量来确认提交**。一旦当前任期的某个日志条目以这种方式被确认提交，那么所有之前的日志条目都会因为**日志匹配属性**（Log Matching Property）而被间接提交，实现图8中（e）的效果。

#### 5.4.3 安全性论证

论文中Raft协议的安全性保证是指：一旦某个节点将某一日志条目应用于自己的状态机，则其他节点不可能在此日志索上应用其他不同的日志条目。

李龙海老师的更简单一些的解释：一旦某个节点将日志中的某条指令应用于自己的状态机之后，它确信其他节点（如果还活着）迟早会将同样的指令（在日志中相同的位置）应用到它们自己的状态机。

思考：为什么Leader收到半数以上Follower已经把某个日志存储到本地日志的ACK消息之后，就可以通知大家可以安全地应用（commit）该日志指令了？

答：***伏地魔思想***（李老师说伏地魔死后把自己的灵魂放入七个圣器遍布世界各地，被后人捡起来就灵魂附体，得以复活。。。）。其实这里就是指如果大多数跟随者已经复制了Leader的日志，然后即使此时Leader崩溃，也会有其中一个已经复制日志了的节点来竞选成为新Leader，继承老Leader的意志。

### 5.5 跟随者和候选者崩溃
跟随者和候选者的崩溃要容易的多，如果他们崩溃了，那么未来发送过来的RequestVote RPCs和AppendEntries RPCs就会失败，Raft处理失败的办法是**无限重试**。如果崩溃的服务器重启了，RPC就会成功完成。Raft的RPCs是**幂等**（幂等性意味着多次执行同一操作与执行一次该操作的效果相同）的，因此不会造成问题。例如，如果一个跟随者接收到一条AppendEntries请求，而该请求中包含的日志条目已经存在于其日志中，那么它会忽略这些在新请求中的重复条目。

### 5.6 时序和可用性
我们对Raft的要求之一是安全性不能依赖于时序，系统不能仅仅因为某件事情发生的比预期快或慢产生错误结果。然而，可用性不可避免的依赖于时序。例如，如果消息交换所需要的时间超过了服务器崩溃之间能容忍的时间，那么候选者就没有足够时间来赢得选举，如果没有一个稳定的领导者，Raft就无法正常运行。

在Raf 中，领导者选举是最与时序密切相关的一部分。只要系统满足以下时序要求，Raft就能够成功选举并维持一个稳定的领导者：

***broadcastTime << electionTimeout << MTBF(单个服务器失败之间的平均时间)***

## 6 集群成员更换
有时候集群配置需要改变，比如替换失败的服务器或者改变复制的程度。且存在任何手动的步骤都会带来操作出错的风险，所以Raft将自动化配置变更纳入共识算法中。

为了配置更换机制的安全，不允许存在某个任期有同时两个领导者存在的可能。然而，任何服务器的交换方法都不安全，不可能一次性交换所有服务器，因此在转换过程中，集群有可能分裂为两个独立的多数派。
![](./pics/10.jpg)

为保证安全，配置更换必须采用两阶段的方法。在Raft中，集群首先切换到我们称为 ***联合共识***（joint consensus）的过渡配置；一旦联合共识被提交，系统随后切换到新配置。联合共识将旧配置和新配置结合起来：

* 日志条目被复制到两个配置的所有服务器。
* 两个配置中的任何一个服务器都可以成为领导者。
* 共识（针对选举和条目提交）需要分别从新旧配置中独立的获得多数同意。

集群配置的保存和交换是通过复制日志中的特殊条目实现的，图11描述了配置改变的过程。其中**没有任何时刻是新旧集群同时做单边决策的**，保证了安全性。

![](./pics/11.jpg)

重新配置过程中还要解决三个问题：
1. **新服务器可能最初不存储任何日志条目**。这种情况的服务器加入时，可能需要相当长的时间才能赶上其他节点，这段时间可能无法提交新的日志条目。为避免可用性的中断，Raft在配置变更之前引入了一个额外阶段，新服务器以非投票者加入集群，领导者向他们复制日志条目，但他们计入多数派，直到赶上其他节点。
1. **集群当前的领导者可能不在新的配置中**。在这种情况下，一旦领导者提交了Cnew日志条目，它就会退位（返回到跟随者状态）。这意味着在提交 Cnew 的过程中，领导者将管理一个不包含自身的集群：**它会继续复制日志条目，但不会将自己计入多数派中**。领导者的切换发生在Cnew被提交时，因为这是新配置能够独立运行的第一个时刻（此时总是可以从Cnew中选出一个领导者）。在此之前，可能只有Cold中的服务器能够被选为领导者。
1. **被移除的服务器（即不在Cnew中的服务器）可能会干扰集群的正常运行**。这些服务器将不会接收到心跳消息，因此它们会因超时而启动新的选举。随后，它们会发送带有新任期号的 RequestVote RPC，这将导致当前领导者退回到跟随者状态。最终虽然会选出一个新的领导者，但被移除的服务器会再次超时，这一过程会不断重复。**为了解决这个问题，服务器在认为当前领导者存在时会忽略 RequestVote RPC 请求**。具体来说，如果服务器在从当前领导者接收到消息后的**最小选举超时时间**内收到了 RequestVote RPC，它不会更新自己的任期号或投出选票

## 7 日志压缩
在正常运行期间，Raft的日志会不断增长以纳入更多的客户端请求。但实际中需要某些机制来丢弃过时信息。快照技术是最简单的日志压缩方法。将整个当前系统的状态写入到稳定存储介质的快照中，然后日志中到该点的内容全都被删除。

图12展示了Raft快照的基本思想。每个服务器独立的进行快照，只涵盖日志中已提交的条目。大部分工作是状态机把当前状态写入快照。

![](./pics/12.jpg)

尽管正常情况下服务器各自独立使用快照，但领导者还是要偶尔向拖后腿的跟随者发送快照，这会发生在领导者已经删除了下一条将要发送给跟随者的条目时。这种情况很少出现，但对于一些极慢的跟随者和刚加入的服务器，这是一种方式可以让他们跟上队伍。

如图13，领导者会发送一个叫InstallSnapshot的RPC给拖后腿的跟随者。当跟随者收到这个RPC时，一般会丢弃整个日志，因为日志中的所有内容都会被快照取代。

还有一种方法就是可以只允许领导者创建快照，然后发送给跟随者。但这会带来两个缺点：第一，发送快照给每个跟随者将浪费网络带宽，每个跟随者已经具备自己快照的能力且本地快照往往比通过网络接收一个快照开销更小；第二，领导者的实现更加复杂，比如你发送的同时要携带新的日志条目，避免阻塞新的客户需求。

然后还有两个问题会影响快照性能：
* 服务器必须决定何时生成快照。过于频繁会浪费磁盘带宽和能量，过于稀疏会耗尽存储容量，且重启时增加重放日志的时间。一种简单的策略是当日志达到固定字节大小时生成快照。如果将该大小设置为显著大于预期快照的大小，那么快照生成对磁盘带宽的开销将会很小。

* 写入快照可能需要很长时间，而我们不希望这会延迟正常操作。解决方案时写时复制技术，以便新的更新可以被接受且不影响正在写入的快照。例如，使用函数式数据结构构建的状态机天然支持这一特性。或者，也可以利用操作系统提供的写时复制支持（例如，Linux上的fork），来创建整个状态机的内存快照。

## 8 客户端交互
这一节讲的是客户如何与Raft交互，包括客户如何找到集群领导者，以及Raft如何支持线性化语义。

客户只给领导者发送请求，一开始客户先随机选一个服务器，如果不是领导者，这个服务器就会拒绝请求然后提供最近的领导者信息。如果领导者崩溃，客户请求会超时，再次尝试还是随机的服务器。

我们的目标是让Raft实现**线性化语义**。然而，Raft可能会多次执行一个命令，比如领导者在提交条目之后返回给客户之前崩溃，客户就会重新尝试命令给一个新领导者，导致命令重复执行。**解决办法是给每个命令分配一个唯一线性数字**，然后状态机追踪给每个客户最新处理的命令数字，带上相关联的回应。如果它收到已经被执行的命令数字，就立刻回应但不执行。

只读操作可以无需写入日志来处理，但没有额外措施，可能会导致返回陈旧数据。因为响应请求的领导者可能被取代，但它并不知情。线性化的读操作必须避免返回陈旧数据，Ratf采取额外两种预防措施，在不使用日志的情况下保证这一点：

1. 确保领导者拥有最新的已提交条目。领导者完整性属性保证领导者拥有所有已提交条目，但是在任期开始时它可能不知道哪些条目已提交，为了确定这一点，**领导者需要在任期内提交一个空白的条目**来实现。

1. 检查领导者是否已被取代。在处理只读请求之前，领导者必须确认自己是否仍然有效。Raft要求领导者与集群中大多数节点交换心跳信息来确保自己仍然是当前有效的领导者。