# Raft

## 引入

分布式系统中很重要的一个基本问题就是**共识（consensus）**问题，即如何让多个进程（process）达成共识。通常进程会因为某种原因进入不可靠的状态，这对解决方案的容错性提出了更高的挑战。共识问题难度很大，凝聚了许多研究者数十年的心血。本课所涉及的 Raft 就是共识算法（consensus algorithms）中的佼佼者。

Part 1 将涉及以下两个话题：

* 选举（Leader Election）
* 日志（Log Handling）

Part 2 将涉及剩下的话题：

* 持久化（Persistence）
* 客户端（Client Behavior）
* 快照（Snapshots)

有了共识算法，我们就能够使用 replicated state machines (RSM) 打造具有容错能力的服务，如：

* 配置服务器（configuration server），如 GFS 与 MapReduce 的 Master
* K/V 存储服务器，如 lab3 中的存储服务

## 共识算法的目标与挑战

理想状态下，共识算法的目的是让服务的使用者无需关心服务是分布式部署还是单机部署。但问题是：

1. 服务器可能随时崩溃。在成千上万个节点构成的分布式系统中，这是很常见的现象
2. 网络可能出现分区，不同区之间的机器可能出现网络阻隔（split brain）
3. 作为进程本身，无法判断一个进程失去联系是因为自身崩溃还是网络分区

为此，我们需要一个 RSM 能够做到：

1. 在少量进程故障时仍然可用
2. 出现网络分区时能避免 split brain
3. 如果出现大量进程故障，等待修复重启

### 解决 split brain 的利剑：少数服从多数（majority vote）

2f+1 服务器可以容忍 f 个服务器出现故障，即只要大多数机器能达成共识，分布式系统就可以继续提供服务。为什么如此简单的方法能够解决 split brain 问题？

* 至多只有一个网络分区可以拥有大多数选民
* 达成共识的机器都葆有过去做过的历史决定，它可以阻止信息落后的机器参选成功

## Raft Overview

### State Machine Replication With Raft -- 以 Lab 3 为例

![图 1 - architecture of lab 3 : k/v store with raft](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSUqTgRYidoA6HAYn6t%2F-LSUqh_jQxsxGWpopUC_%2FScreen%20Shot%202018-11-29%20at%201.54.09%20PM.jpg?alt=media\&token=55461279-7bec-4c4a-a839-12805b7489ec)

如图 1 所示：整个 k/v store 服务由 3 个 replicas 构成，每个 replica 分为 k/v 层和 raft 层。

1. clients 发送 RPC 请求到 leader 的 k/v 层
2. leader 的 k/v 层将 clients 想要执行的 command 发送至 leader 的 raft 层
3. leader 的 raft 层将 command 存到本地 logs 中，并通过 AppendEntries RPC 将 command 发送至所有 replicas，以获得共识
4. 每个收到 command 并同意的 replica 将 command 存到本地 logs 中，然后回复 leader
5. 当 leader 的 raft 层发现自己获得多数票时，即达成共识，于是将包含 command 的 log 确认为 committed 状态
6. leader 的 raft 层告诉 k/v 层 command log 已经 committed，k/v 层就可以执行该命令。在后续的 AppendEntries RPC 请求中（心跳或接收新的 command），其它 replicas 会得知该信息，继而 commit 并通知自己的 k/v 层执行命令
7. leader 的 k/v 层回复 client 命令执行结果

### 为什么需要日志（logs）？

我们的服务已经有了 state，如 k/v DB，为什么还需要日志？

* 我们需要给接收到的命令编号
  * 帮助所有 replicas 对命令执行顺序达成共识
  * 帮助 leader 确认所有的 followers 都有一模一样的 logs
* replicas 使用 logs 存储命令
  * 当发现 leader commits 命令后，可以根据 logs 信息执行这些命令
  * leader 可以根据 followers 缺失的命令补发 logs
  * 可以做持久化，同时在崩溃或者重启之后重放

## Leader Election

Leader 的作用就在于保持所有 followers 的步调一致，按相同的顺序执行某个命令，从而达到复制状态的目的。

### Terms & Leader

Term 就是 Raft 中的选举周期，一个 Term 选举一次，最多产生一名 Leader。Term 就如时间一般永远单调递增，因此可以利用 Term 的编号来帮助大家选举正确的 Leader。

### 在什么时候举办新一轮选举

如图 2 所示，当 Follower 在一定时间内没有收到来自 Leader 的消息，新的选举就会开始。当选举开始时，Follower 会自增当前的 Term，转化为 Candidate，开启选举，向其它选民索要选票。当然，选举有时候会因为网络延迟或分区而被迫产生，这时候就要处理新旧 Leader 的矛盾问题。 

![图 2 - state transition diagram](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSXs9Gh53JlZ8CLpTSN%2F-LSXxpaXfluQYLrfb0XF%2FScreen%20Shot%202018-11-30%20at%2012.53.36%20PM.jpg?alt=media\&token=76f4bf11-b595-4fb8-bed6-89258afc9c01)

### 参选人（Candidate）有哪些下场

1. 获得多数选民的选票，成为 Leader
2. 未获得多数选民的选票，收到其它 Leader 的消息，成为 Follower
3. 未获得多数选民的选票，未收到其它 Leader 的消息，继续开启下一轮选举

在第三种情况下，有可能出现 Term 在不断增加的情况：

* 不断出现平局的选举：可以通过随机生成 election timeout 解决
* 出现网络分区时，处在少数选民分区中的节点会不断进行新的选举，导致 Term 不断增加。当网络恢复通信后，无论多数选民分区中的节点是否有推进，都会发现存在 Term 更新的节点，从而进行新的选举。不过这不会影响服务的正确性，因为只有拥有最新 commited 日志的选民才会获得投票。

### 如何保证一个 Term 最多只产生一个 Leader

获胜者必须获得多数选票，每个选民只能投一票。少量节点出现故障不会影响选举的进行，也不会影响系统的服务。

### Leader 如何确认自己的无上地位

当得知自己获得多数选票后，立即发送 AppendEntries RPC，通知大家别选了；之后还会继续每隔一段时间发送心跳信息给 Followers，告诉大家自己还活着。

### 选举未产生 Leader 的两个原因

* 运作正常的节点不到多数 => 继续选举但不会有结果，Term 不断增加
* 平票，重选 => 继续选举，通过合适的 election timeout 设置提高选举成功的概率

### 如何设置 Election Timeout

* 每个节点在一定范围内选择一个随机的 Election Timeout
* Election Timeout 至少要足以让选举在正常的网络状况下完成
* 在满足第二点的情况下又要小一些，减少选举所花费的时间

## Raft log

### Replicated vs. Committed Entries

每个 log entry 都会先被 replicated，直到 leader commit 以后才会被 committed。committed entries 永远不会被删除，而 uncommitted entries 是有可能被删除的。

### 是否每个 replica 的 logs 都完全相同？

并不是，可能出现落后的情况，但它们最终会收敛，而我们的 commit 机制会保证 replica 只执行已经被 committed 的命令。

### Leader cannot simply replicate and commit old term's entries

paper 的 figure 8 提出在特殊情况下，Leader 有可能覆盖之前已经被复制到多数节点上的 log entry。因此 Raft 要求 Leader 只能 commit 当前 Term 的 log entry，对于过去的 uncommitted log entries 将直接重写。

![图 3 - raft-extended paper figure 8](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSXs9Gh53JlZ8CLpTSN%2F-LSXyAtTtShbIj985H6x%2FScreen%20Shot%202018-11-30%20at%2012.55.19%20PM.jpg?alt=media\&token=7f943693-1e0e-41ae-8000-a87a950d1ea7)

### 什么时候 Raft 可以重写 log entries?

当 Leader 1 接收命令时出现网络分区，自己本地的 log entries 已经很多，但都是 uncommitted。而其它分区的 replicas 可能选举出新的 Leader 2，接收并 commit 新的命令。当网络恢复时，Leader 1 可能发现自己的 log entries 比别人的多或者少，但是无论如何它还是得跟新的 Leader 保持一致，重写自己的 logs。

### 只要 Leader 尚在

* clients 只与 Leader 通信
* clients 对 followers 的行为不受影响

### 当 Leader 故障时

我们如何能够做到让 clients 不察觉到这些异常？

* 读到过时的结果
* 命令重复执行
* 得到命令执行成功的相应但发现实际上并非如此
* 命令执行的顺序有误
* ...

### Election Restriction

在投票的过程中，选民只会给与**至少与自己一样与时俱进**的候选人：

* 候选人最后一个 log entry 的 term 大于自己最后一个 log entry 的 term
* 候选人最后一个 log entry 的 term 等于自己最后一个 log entry 的 term，同时候选人的 logs 长度大于或等于自己的 logs 长度

设置 election restriction 的目的在于保证 Leader 的 logs 必须要包含所有可能被 committed 的 log entries，从而阻止新的 Leader 回滚已经 committed 的 log entries。

> 所有可能被 committed 的 log entries: 这里并不仅仅指已经被 committed 的 log entries，有时候 log entry 尚未被复制到大多数节点上，Leader 就故障了。但在 Election Restriction 的保证下，只有已经获取最新 log entry 的 followers 才有可能被选举为新 Leader，因此只要剩下的一切顺利进行，新的 Leader 会帮助旧的 Leader 完成使命，并返回消息给 Client

### 如何快速回滚

当 Follower 发现 Leader 的给的 previous log entry 信息不对时，会告知 Leader AppendEntries 失败，Leader 发现后需要通过调整 nextIndex 来找到正确的 previous log entry。

Raft 论文 Figure 2 给出的方法是，每当 Leader 发现 AppendEntries 失败时，nextIndex 递减 1，最终必然能找到正确的 previous log entry。显而易见，该方法的效率较低；Raft 论文同时也提出一种优化方案框架但没有详细描述，下面是导师的猜想：即每当 Follower 发现 previous log entry 信息不对时，在返回消息中加入两条信息：

* Follower 与 Leader 相矛盾的 log entry 的 Term
* Follower 在上述 Term 中的第一个 log entry 的位置（index）

Leader 获得这些消息后：

* 如果 Leader 有相应的 Term 的 log entry，那么将 nextIndex 移动到该 Term 的最后一个 log entry 的位置上
* 如果 Leader 没有相应的 Term 的 log entry，那么将 nextIndex 移动到返回的 Index 上

## Persistence

当 server 崩溃时，虽然 Raft 可以在崩溃的 server 数量不大的前提下继续工作，但我们必须尽快修复防止问题恶化。通常有以下两种策略：

* 当 server 的崩溃是永久性的时候，我们需要替换 server，同时将所有日志、快照信息转移。
* 当 server 的崩溃是暂时性的时候，我们需要快速恢复到可以在集群中正常工作的状态。

后者就是本节要探讨的 Persistence 话题。

### Raft Server 崩溃前，需要记住哪些状态？

Raft 论文 Figure 2 以及列出相关状态：log\[], votedFor, currentTerm

#### Why log\[] ?

server 的 log\[] 记录着 committed log entry 的历史信息，有了它可以保证这一信息不丢失。

#### Why votedFor ?

为了防止一个节点在同一次选举的过程中崩溃重启，从而获取两次投票机会的情况。

#### why currentTerm ？

保证 currentTerm 单调递增特性，同时能帮助 server 甄别过时的消息。

### 建立在 Raft 之上的服务如何在崩溃重启后恢复到工作状态？

从空状态开始，在重建 commitIndex 和 lastApplied 的过程中重播（replay）所有命令。

## Log Compaction and Snapshots

\[TODO]

## Configuration change

\[TODO]

## Performance

\[TODO]

## 参考

[lecture note](http://nil.csail.mit.edu/6.824/2018/notes/l-raft.txt), [paper](http://nil.csail.mit.edu/6.824/2018/papers/raft-extended.pdf), [another gitbook](https://wizardforcel.gitbooks.io/distributed-systems-engineering-lecture-notes/content/l06-raft.html), [raft Q\&A from teaching assistant](https://thesquareplanet.com/blog/raft-qa/), [students' guide to raft](https://thesquareplanet.com/blog/students-guide-to-raft/), [animation](http://thesecretlivesofdata.com/raft/)