## 简介

### 如何多快好省的对大规模数据集进行存储和计算？

#### 解决

1. 更好的机器
2. 更多的机器

#### 问题

1. 不断垂直扩展机器，升到一定配置之后就不能升级了。升级机器的配置带来的提升与付出的价格不匹配。瓶颈是在与硬件和对成本的控制
2. MapReduce 中使用一些廉价的机器组成一个集群处理大规模的数据，这也会引出一个问题。如何保证多个机器之间的同步，如何解决机器间的网络问题。对于网络通信有三种：写入成功，写入失败，消息丢掉（无法判断消息丢失还是延迟）

### 如何让跨网络的机器之间协调工作？

1. 状态立即一致
2. 状态的最终一致

### 如何应对网络不可靠以及节点的实效？

1. 可读写
2. 可读
3. 不可用

- 组织机器使其状态最终一致性并允许局部失败的算法称为一致性算法。（共识算法）
- Paxos 算法由来已久，目前是功能和性能最完善的一致性算法，然而他难以理解和实现。raft 简化了 Paxos，它是以易于理解为首要目标，尽量提供与 Paxos 一样的功能与性能  [Paxos Raft ZAB 的比较](https://zhuanlan.zhihu.com/p/130332285)
- 保证最终一致性 三个结点，ABC，A 结点依次应用 3456，BC 结点也要依次应用 3456。

### 复制状态机

![图 1](https://jimyag.com/posts/raft-paper-consensus-distribution/index/pic_1673715875956.png)  

1. Client 将操作发送到 Leader 结点，
2. Leader 将同步请求发送到其余的结点，将操作记录到日志中
3. 专门的状态机会将日志应用到 server

- 每一个日志都按照相同的顺序包含相同指令，所有的服务器都执行相同的指令序列。状态机是确认的，每一次执行操作都产生相同的状态和序列。
- 任务就变成了保证日志复制的一致性。
- 一致性算法的目标就是保证集群中所有的状态一致，节点要执行的指令可以分为两种，**读和写**。只有写的指令才会改变结点的状态，因此为了保证集群各个节点状态的一致，就必须将写指令同步给所有节点。
- 理想状态下，我们期望任意节点发生写命令都会立即在其他节点上变更状态，这其中没有任何时延，所有节点都好像是同一个节点（像单机）一样被变更状态。
- 网络延迟要远远慢于内存操作，写入命令不可能被同时执行，因此如果在不同节点发生不同写命令，那么早其他节点上这些写命令被应用的顺序很可能完全不同。
- 如果我们不要所有节点的写命令立即被执行，而仅仅是保证所有的写命令在所在节点上按照相同的顺序最终被执行？仅允许一个节点处理写命令，所有节点维护一份顺序一致的日志。
- 日志的顺序以及对应对应序号的日志操作都是相同的。

### 一致性要解决的问题

1. 输入：写入命令
2. 输出：所有节点最终处于相同的状态
3. 约束
1. 网络不确定性：在[非拜占庭情况](http://zhangtielei.com/posts/blog-consensus-byzantine-and-blockchain.html)下 (非受信网络)，出现网络 分区、冗余、丢失、乱序 等问题下要保证正确。
2. 基本可用性：集群大部分节点能够保持相互通信，那么集群就应该能够正确响应客户端
3. 不依赖时序：不依赖物理时钟或者极端的消息延迟来保证一致性。不能依靠给消息时间戳来保证消息的顺序。[零点飘逸](https://juejin.cn/post/6844903788822659086)
4. 快速响应：对客户端请求的响应不能依赖集群中最慢的节点

### 一个可行解

- 初始化时候有一个 leader 节点，负责发送日志到其他追随者，并决定日志的顺序
- 读请求到来时，任意节点都可读，写请求需要重定向到 leader 节点
- 领导者先写入自己的日志，然后同步给半数以上节点，跟随者表示 ok 了，领导者才提交日志。（有点类似先 commit 再 push）
- 日志最终由领导者先按照顺序应用于状态机，其他跟随者随机应用到状态机
- 当领导者崩溃之后，其他跟随者通过心跳感知并选举出新的 leader 继续集群的正常运转
- 当有新节点加入或者退出集群，需要将配置信息同步给整个集群

## Raft 的详细实现

### 状态机

![图 2](https://jimyag.com/posts/raft-paper-consensus-distribution/index/pic_1673715799344.png)  

raft 中有三个角色 (状态)，三个角色可以进行一些切换，每一个状态都有不同的数据结构
所有的节点在启动的时候都是 Follower，会启动一个心跳计时器，如果心跳计时器超时了，那么就会变为 Candiate 状态，变成之后会立即向其他结点发送投票请求进行投票，同时也会启动一个选举超时计时器。
如果收到半数以上人数的票就会变为 leader，成为 leader 之后发送心跳和同步日志，启动一个定时器，每隔一段时间给 follower 发送心跳。
如果始终没有收到足够的选票，这时候选举定时器超时，就会更新自己的状态为候选人重新发起一轮新的投票过程
如果在等待选票的过程中，收到了 leader 的心跳请求，就会退回到 follower 状态。
由于网络分区，集群中又出现了一个 leader，这时候网络中就有两个 leader，这是分布式系统中一个常见的问题 - 脑裂。如何避免这个问题呢？给每一个 leader 都有一个任期 term（在心跳中就会同步任期数），如果有两个 leader 之后就后根据 term 较大的一个作为新的 leader，较小的 term 的 leader 就会退回为 follower
选举的过程中，超时计时器的时间是固定的，所有的 follower 变为 candidate 同时请求选举，可能会有瓜分选票的问题，三个人手上都只有一张选票，没有超过半数，一直选举，一直都没有 leader 出现，一直都不可写。raft 为了避免这个问题，给每个结点选举超时时间设定了一个随机范围，尽量在一次选举中就可以选出 leader

### 数据结构

#### 通用持久性数据（三个状态都有）

| 参数        | 解释                                                                                             |
| ----------- | ------------------------------------------------------------------------------------------------ |
| currentTerm | 服务器已知的最新的任期，首次启动的时候为 0。通过心跳更新                                         |
| votedFor    | 当期任期内收到选票的候选者的 ID，如果没有投给任何人，则为空，就是把票投给了谁                    |
| log[]       | 日志的条目，每个条目包含了用于应用状态机的命令，以及 leader 接受到该条目时的 term，索引从 1 开始 |

- raft 在一个 term 中一个 follower 只会投一次票
- log 中包含操作（set，add，是复制状态机可接受的操作），term（写入这个操作的 leader 的所处的 term），以及对应的 index
  
#### 通用易失性数据

| 参数        | 解释                                                 |
| ----------- | ---------------------------------------------------- |
| commitIndex | 已知已提交的最高的日志条目的索引，初始值为 0         |
| lastApplied | 已经被应用到状态机的最高的日志条目的索引，初始值为 0 |

- commitIndex 的左边的日志是这个 server 已经提交的日志（已经提交给集群中半数以上的节点）
- lastAppliApplied <= commitIndex ,他们中间可能还有一部分 log 处于可以应用但是还没有应用的状态。
- raft 只保证已提交日志的一致性。lastApplied 和 commitIndex 之间的可能是不一致的。

#### leader 的易失性数据

| 参数         | 解释                                                                                               |
| ------------ | -------------------------------------------------------------------------------------------------- |
| nextIndex[]  | 每一个 follower，发送到改 follower 的下一个日志条目的索引，初始值为 leader 的最后日志条目的索引 +1 |
| matchIndex[] | 每一个 follower，已知的已经复制到该 follower 的最高日志条目的索引，初始值为 0                      |

- 标识同步的状态，还有多少 log 没有被同步

对于每一个角色，都有不同的定时器，leader 是发送心跳的计时器，follower 是心跳超时的计时器，candidate 是选举超时的计时器

### RPC

RPC 的发起者是谁，由谁接受处理它？

- candidate 发起投票选举的 RPC 到 follower 或者 candidate
- leader 发起的 RPC 到 follower
  - 日志追加
  - 心跳通知
candidate 会将投票选举的 RPC 发送给它知道的所有的结点

#### 请求投票

##### 什么时候触发？

1. follower 变为 candidate(follower 的心跳计时器超时了)
2. 选举超时

##### 请求 (核心) 参数

| 参数         | 说明                               |
| ------------ | ---------------------------------- |
| term         | 候选人的任期号                     |
| candidateID  | 候选人的 ID                        |
| lastLogIndex | 候选人的最后 (新) 日志条目的 index |
| lastLogTerm  | 候选人最后日志条目的任期号         |

##### 返回值

| 参数        | 说明                                      |
| ----------- | ----------------------------------------- |
| term        | 当期任期号                                |
| voteGranted | 候选人获得这张选票时为 true，否则为 false |
返回 term 是集群中已经有新的 leader 出现了，把当前 term 给候选人，让它切换状态

##### 投票逻辑（候选人）

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

##### 选举的规则（接受到 RPC 方）

1. 如果 term＜ currentTerm 返回 false，currentTerm
2. （判断候选人已经提交的的日志是否是足够新的，候选人应该拥有所有的已提交，从建立之初到现在的所有的日志）如果 votedFor 为空 或者 等于 candidateld(可能是新一轮投票)，并且比较 lastLogTerm 和 currentTerm
1. lastLogTerm>currentTerm 则直接投票
2. 小于则拒绝
3. 等于则比较 lastLogIndex 和 log[len(log)-1].idx

#### 日志追加&心跳

##### 触发

1. 客户端发起写请求时
2. 发送心跳时
3. 日志匹配失败时

##### 请求参数

| 参数         | 说明                                     |
| ------------ | ---------------------------------------- |
| term         | 当前 leader 的任期号                     |
| lederID      | 领导者的 ID                              |
| preLogIndex  | leader 紧邻新日志之前的那个日志的 index  |
| preLogTerm   | leader 紧邻新日志之前的那个日志的 term   |
| entries      | 需要被提交的日志的条目                   |
| leaderCommit | 领导者的已知已提交的最高的日志条目的索引 |

##### 响应值

| 参数    | 说明                                                                         |
| ------- | ---------------------------------------------------------------------------- |
| term    | 当前任期，对于 leader 而言，它会更新自己的 Term                              |
| success | 如果 follower 所含有的条目和 preLogIndex 以及 preLogTerm 匹配上了，返回 true |
第一个分区得不到半数确认，会处于为提交的状态

##### 日志追加（leader）

1. 一旦成为 leader：发送空的附加日志 RPC(心跳) 给所有的 follower，在一定空余时间之后不停的重复发送，阻止 follower 超时
2. 如果接受到来自 client 的写请求：附加本条目到本地日志中，在条目被应用到状态机后响应 client（可选，如果是强一致的，就这样做，如果不是强一致附加到本地日志就可以返回了）
3. 对于 follwer，如果 leader 的最后日志条目的索引值>=nextIndex，那么发送从 nextIndex 开始的所有日志条目：
1. 如果成功，更新相应追随者的 nextIndex 和 matchIndex
2. 如果因为日志不一致而失败，减少 nextIndex 重试 (每次减 1 进行尝试，直到找到和 preLogIndex，term 匹配的就停止，就可以发送日志了。为什么只匹配到这个就可以认为之前的也一样呢？只要不匹配就往后退，就删除，最后肯定会当 index=0 的时候一定匹配，那么这时候 1 也匹配，2 也配)
4. 如果存在一个满足 N>commitIndex 的 N，并且大多数的 matchIndex[i]>=N 成立，并且 log[N].term == currentTerm 成立，那么 commitIndex = N (matchIndex 是当前集群同步的进度，N 就是超过一半的节点都提交到这个点了，中位数，那么就满足了法定人数，此时更新这个 commit 就是安全的)

##### 接受日志 (follower)

1. 如果 leader 的 term < follower 当前的 term，返回 false,currentTerm
2. 在接受者的日志中，如果能找到一个和 preLogIndex 以及 preLogTerm 一样的索引和任期的日志条目，则执行下面操作，否则返回 false，
3. 如果一个已经存在的条目和新的条目发生冲突 (索引相同，任期不同)，那么就删除这个已经存在的条目以及它之后的所有条目。(五个结点旧的 leader 和其中一个结点与其他三个结点分区了，网络恢复后，结点 A 有可能存在没有提交的 logEntry)，leader 会让删除不是自己任期内的为提交的日志。当前日志未提交，可以强制使 follower 复制日志和 leader 一样。
4. 追加日志中尚未存在的任何新条目
5. 如果领导者的 (commitIndex)leaderCommit 大于 接收者的 commitlndex 则把接收者的 commitlndex 重置为 ( leaderCommit 或者是 发来的最新日志条目的索引值取两者 的最小值) ？？？

## 算法证明

### 五条公理

| 特性              | 说明                                                                                                                 |
| ----------------- | -------------------------------------------------------------------------------------------------------------------- |
| 选举安全特性      | 给定一个 term，最多只有一个 leader                                                                                   |
| leader 只附加原则 | leader 绝对不会删除或者覆盖自己的日志，只会增加                                                                      |
| 日志匹配原则      | 如果两个日志在相同 index 的 term 也相同，那么我们认为日志从头到 index 之间都完全相同                                 |
| leader 完全特性   | 某条日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大的 term 的所有 leader 人中                           |
| 状态机安全特性    | 如果一个 leader 已经将给定 index 的日志条目应用到状态机中，那么其他任何 follower 在这个 index 不会应用一个不同的日志 |

### 选举安全特性

![1](https://jimyag.com/posts/raft-paper-consensus-distribution/index/pic_1673765814328.png)  
> 在一个任期内半数以上选票才可以当选，保证每个任期要么 0 个领导要么 1 个领导。
> normal operation 是有 leader 的时候
> 一个 term 可能也没有 leader 被选举出来，那么这时候 term++，继续选举

### 日志复制过程的完全匹配

1. 因为 集群在任意时刻最多只能有一个 leader 存在，leader 在一个任期内只会在同一个索引处写入一次日志
2. 又因为 领导者从来不会删除或者覆盖自己的日志，并且日志一旦写入就不允许修改
3. 所以 只要任期和索引相同，那么在任何节点上的日志也都相同
4. 因为 跟随者每次只会从与 leader 的 PreLog 匹配处追加日志，如果不匹配 则 nextindex -1 重试
5. 所以 由递归的性质可知一旦跟随者和 leader 在 PreLog 处匹配，那么之前的所有日志就都是匹配的 (0 就是空 log，是起点，所有的结点都相同)
6. 所以只要把 preLog 之后的日志全部按此次 Leader 同步 RPC 的日志顺序覆盖即可保证 二者的一致性

### 安全性

每一任的领导者一定会有所有任期内领导者的全部已提交日志吗？

#### 选举限制

选民只会投票给任期比自己大，最后一条日志比自己新 (任期大于或者等于时索引更大) 的候选人。
但这真的正确吗？
![图 4](https://jimyag.com/posts/raft-paper-consensus-distribution/index/pic_1673765851520.png)  

> 1. 时刻 a，S1 是任期 2 的领导人并且向部分节点（S1 和 S2）复制了 2 号位置的日志条目，然后宕机​
> 2. 时刻 b，S5 获得了 S3、S4( S5 的日志与 S3 和 S4 的一样新，最新的日志的任期号都是 1）和自己的选票赢得了选举，成了 3 号任期的领导人，并且在 2 号位置上写人了一条任期号为 3 的日志条目。在新日志条目复制到其他节点之前，S5 若机了​
> 3. 时刻 c，S1 重启，并且通过 S2、S3、S4 和自己的选票赢得了选举，成了 4 号任期的领导人，并且继续向 S3 复制 2 号位置的日志。此时，任期 2 的日志条目已经在大多数节点上完成了复制​ （s3 的 4 可能还没有提交）
> 4. 时刻 d，S1 发生故障，S5 通过 S2、S3 的选票再次成为领导人（因为 S5 最后一条日志条目的任期号是 3，比 S2、S3、S4 中任意一个节点上的日志都更加新），任期号为 5。然后 S5 用自己的本地日志夜写了其他节点上的日志​
> 5. 上面这个例子生动地说明了，即使日志条目被半数以上的节点写盘（复制）了，也并不代表它已经被提交（commited）到 Raft 集群了——因为一旦某条日志被提交，那么它将永远没法被删除或修改。这个例子同时也说明了，领导人无法单纯地依靠之前任期的日志条目信息判断它的提交状态​
> 6. 因此，针对以上场景，Raft 算法对日志提交条件增加了一个额外的限制：要求 Leader 在当前任期至少有一条日志被提交，即被超过半数的节点写盘
> 7. 正如上图中 e 描述的那样，S1 作为 Leader，在崩溃之前，将 3 号位置的日志（任期号为 4）在大多数节点上复制了一条日志条目（指的是条目 3，term 4），那么即使这时 S1 若机了，S5 也不可能赢得选举一一因为 S2 和 S3 最新日志条目的任期号为 4，比 S5 的 3 要大，S3 无法获得超过半数的选票。无法赢得选举，这就意味着 2 号位置的日志条目不会被覆写

所以新上任的领导者在接受客户端写入命令之前 需要提交一个 no-op(空命令)，携带自己任期号的日志复制到大多数集群节点上才能真正的保证选举限制的成立。（相当于不会单独同步 Term 2，而是把同步 Term2 与 Term4 原子化，不然 Term2 会被覆盖）

#### 状态机安全性证明（三段论）

1. 定义 A 为上个任期最后一条已提交日志，B 为当前任期的 leader​
2. 因为 A 必然同步到了集群中的半数以上节点​
3. 又因为 B 只有获得集群中半数以上节点的选票后才能成为 leader​
4. 所以 B 的选民中必然存在拥有 A 日志的节点​
5. 又因为 选举限制，B 成为 leader 的前提是比给它投票的所有选民都要新​
6. 所以 B 的日志中必然要包含 A​
7. 又因为 日志完全匹配规则 如果 A 被 B 包含，那么比 A 小的所有日志都被 B 包含​
8. 因为 lastApplied <= commitIndex​
9. 又因为 raft 保证已提交日志在所有集群节点上的顺序一致​
10. 所以 应用日志必然在在所有节点上顺序一致​
11. 因为 状态机只能按序执行应用日志部分​
12. 得证 状态机在整个集群所有节点上必然 最终一致

#### 状态机安全性证明（反证法）

1. 当日志条目 L 被同步给半数以上节点时，leaderA 会移动 commitIndex 指针提交日志，此时的日志被提交​
2. 当 leader 崩溃后，由一个新节点成为 leaderB，假设 leaderB 是第一个未包含 leaderA 最后已提交日志的领导者​
3. 选举过程中，只有获得半数以上节点认可才能成为 leader，因此至少有一个投票给当前 leaderB 的节点中含有已经提交的那条日志 L。​
4. 那么根据选举限制，节点只会将选票投给至少与自己一样新的节点​
1. 节点 C 作为包含 leaderA 最后提交日志条目的投票者，如果 leaderB 与节点 C 的最后一条日志的任期号一样大时，节点 C 的条目数一定大于 leaderB，因为 leaderB 是第一个未包含最后一条 LeaderA 日志的领导者。这与选举限制相矛盾，节点 C 不会投票给 leaderB
2. 如果 leaderB 最后一条日志的任期号大于节点 C 最后一条日志的任期号，那么 leaderB 的前任领导中必然包含了 leaderA 已经提交的日志 (leaderB 是第一个不包含 leaderA 已提交日志的领导者 这一假设) 根据 日志匹配特性 leaderB 也必须包含 leaderA 最后的已提交日志，这与假设矛盾。​
5. 所以证明 未来所有的领导者必然包含过去领导者已提交的日志，并且日志匹配原则，所有已提交日志的顺序一定是一致的。
6. 又因为 任意节点仅会将已提交日志按顺序应用于自身的状态机，更新 lastApplied 指针，因此所有节点的状态机都会最终顺序一致。
7. 得证 raft 算法能够保证节点之间的协同工作。

## 一些额外的资料

### 一致性介绍

- 弱一致性。在写入之后，访问可能看到，也可能看不到（写入数据）。尽力优化之让其能访问最新数据。这种方式可以 memcached 等系统中看到。弱一致性在 VoIP，视频聊天和实时多人游戏等真实用例中表现不错。打个比方，如果你在通话中丢失信号几秒钟时间，当重新连接时你是听不到这几秒钟所说的话的。  
  - 最终一致性。在写入后，访问最终能看到写入数据（通常在数毫秒内）。数据被异步复制。DNS 和 email 等系统使用的是此种方式。最终一致性在高可用性系统中效果不错。  
  - 强一致性。在写入后，访问立即可见。数据被同步复制。文件系统和关系型数据库（RDBMS）中使用的是此种方式。强一致性在需要记录的系统中运作良好。

### 脑裂 (split-brain)

**原本一个集群，被分成了两个集群，同时出现了两个“大脑”，这就是所谓的“脑裂”现象**。这里的大脑都是被选举出来的，可能由于网络分区的原因，选举的时候。由于原本的一个集群变成了两个，都对外提供服务。一段时间之后，两个集群之间的数据可能会变得不一致了。当网络恢复时，就面临着谁当 Leader，数据怎么合并，数据冲突怎么解决等问题。

### 网络分区

在分布式环境下，有时由于网络通讯故障，而不是服务器上的应用故障，导致一些节点认为应用不可用，另外一些节点认为应用仍可用。导致，整个系统在提供服务时，造成了不一致性。由于故障将网络划分为多个区域了。