# Raft

**Repository Path**: Codebells/Raft

## Basic Information

- **Project Name**: Raft
- **Description**: 一个Raft共识算法的C++版本实现
https://codebells.github.io/
- **Primary Language**: C++
- **License**: Not specified
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2022-10-09
- **Last Updated**: 2024-06-07

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Raft
一个Raft共识算法的C++版本实现

几个相对于paxos的新特点

- Strong leader：日志只能从leader发给其他节点
- Leader election：使用随机计时器选举leader,
- Membership change：使用联合一致性的方法实现成员变更，保证服务再成员变更期间正常执行

## 复制状态机

复制状态机通常用来解决分布式系统中容错问题，通常使用复制日志实现，如图，一个客户端发送命令给服务器集群，通过共识模块，将其存储在日志中并且同步到其他服务器中，这样每个服务器都会存储一份日志，每个服务器的日志存储的都是客户端发来的相同一系列操作，进而通过状态机以一个相同的规则来执行这些相同的操作，这样最终的输出也是一样的。

![Replication state machine architecture](README/image-20220602152024162.png)

保证日志的一致性就是共识算法要做的事，如上图中的共识模块，做的就是接收客户端的请求，并且把他们添加到日志中。共识模块会和其他服务器上的共识模块进行通信，确保日志最终是以相同的顺序包含相同的请求。

共识算法有以下的特性

- 在非拜占庭模型中保证安全，也就是不返回错误结果
- 高可用，只要大部分服务器可用就可以保证系统可用，一般是需要半数以上服务器可用
- 不依赖时钟顺序保证日志一致性。
- 通常只需要集群中大部分服务器对远程调用响应即可完成命令，少数速度较慢的服务器不影响总体性能

## Raft共识算法

分为三个子问题

- Leader election：领导节点选取
- Log replication：日志复制
- Safety：保证日志的一致状态

### 基础概念

#### 节点状态

- leader：整个集群一般只有一个leader，剩余全为follower，负责接收所有client请求。定期发送心跳包(通常小于选举超时)，如果发现更新Term指令，立刻转为follower
- follower：是被动的，不会主动发出请求，只会回应leader和candidate的请求。在一个随机的超时时间内没有收到投票或者日志复制或心跳包的RPC，就会变成Candidate状态
- candidate：当集群处于选举状态时会出现candidate，用于选取领导节点。处于Candidate状态的节点会立马开始选举阶段，并且投自己一票，然后向其他节点发送投票。如果获得了半数以上的节点投票，那么就转为Leader状态。如果投票给了别的节点，或者发现新的Term时，转为Follower状态。如果选举超时时没有得到半数以上投票，那么则保持Candidate状态，开始新的投票。

![各状态转换示意图](README/image-20220602162230510.png)

#### Term

每个Term不确定，对term进行连续编号。每次选举阶段开始时，会对Term序号进行推进，Term存在两个阶段，第一个是选举阶段，第二个为选举阶段选出的leader的作用阶段，即一直到触发下次选举领导节点。如果选举阶段出现选出两个leader的情况，直接进行下一个选举阶段，Term也推进。

除此之外，Term还可以作为检查过时领导者的信息，例如网络分区情况下，可能会存在现任leader和旧的无用leader

![Term示意](README/image-20220602162158726.png)

#### RPCs(Remote Procedure Calls)

- RequestVote RPCs：由候选节点在选举leader时发起
- AppendEntries RPCs：由领导节点在同步日志时发起

![RAFT保证](README/image-20220602194822669.png)

### 领导节点选取

使用心跳机制触发领导节点选取

当follower一段时间后没收到心跳包，就会假设没有leader，开始选举阶段，推进Term，并且变为candidate状态，然后开始投票阶段，向所有节点并行发送RequestVoteRPCs，请求自己成为leader此时存在三种情况

#### 该节点成为leader

收取到半数以上的投票，即成为leader，每个Server只能投票一次，先到先得的原则。一旦赢得选举，就向其他所有节点发送心跳，并建立权限阻止新的选举。

#### 别的节点成为leader

当等待投票结果时，收到了一个领导节点发起的AppendEntriesRPC，如果leader的Term不小于该节点的Term，那就认为其合法，自动变为follower，否则拒绝该RPC，继续选举阶段。

#### 该Term没有leader

可能存在很多candidate，选票可能被分成了很多部分，但是每个部分都不超过半数以上，此时等到选举超时，进行下一次选举，并推进Term。采用随机的选举超时，一般为150-300ms。每次candidate在选举开始时都会重新选择这个超时时间。

### 日志复制

![日志结构示意](README/image-20220602200354325.png)

存在Leader时，会响应客户端请求，将客户端传来的命令附加到日志中，然后向其他所有节点并行发送AppendEntriesRPCs来达到复制这个命令的效果。当这条数据被安全复制后，这个leader就会应用所有的数到状态机并返回结果给client。

![log replication示例](README/image-20220602183925889.png)

#### 日志复制流程

1. 客户端发送请求给leader
2. leader接收client请求，先将请求作为一个logEntry添加到log中
3. 然后leader再最近的一个心跳包中发送AppendEntriesRPC给Follower节点
4. 一旦日志提交成功
   - 此时日志处于Uncommitted状态，当超过半数节点添加log成功后，则Leader提交该日志给状态机，返回给客户端写入成功
   - 在接下来的AppendEntriesRPC中通知其他节点提交该日志
   - Follower节点提交日志到自己的状态机
5. 如果Leader挂了，其他Follower节点超时后重新选取Leader。如果由宕机或者太慢的Follower节点，则会不断重试选举过程

#### 日志复制的要点

- 不同节点提交的相同的索引和Term的日志项的Command一定相同，并且之前的日志项也都相同
- 如果一个日志项被提交，则它之前索引的所有日志项也都被提交
- Leader不会覆盖自己的日志。其他状态节点如果出现与当前Leader日志不一致，则需要更新日志，包括写入新的日志和删除不一致的日志。
- Leader提交过的日志一定会出现将来新的Leader中
- Leader要保证安全的提交日志，必须满足一下两个提交规则
  - 日志条目已经复制到超过半数以上的Follower节点
  - Leader当前Term的新日志条目至少有一个复制到了大多数Follower节点

#### 时序性和可用性

Raft的一个特点就是安全性不依赖时序，系统不会因为时序问题而导致错误发生，但是系统的可用性不可避免的会对时序有所依赖。如果服务器崩溃会导致Candidate节点选举不成功而不停的发起选举，而Raft必须有一个稳定的Leader，否则无法工作。领导选举是Raft中对时序要求最关键的地方，Raft能够选举出并保持一个稳定的Leader需要系统满足如下时序要求：

```
broadcastTime << electionTimeout << MTBF
```

其中broadcastTime是指一台服务器并行地向集群其他服务器发送RPC并接收到响应的平均时间，而electionTimeout是选举超时时间，MTBF则是指单个服务器发生故障的平均间隔时间。broadcastTime远小于electionTimeout可以保证Leader持续发送心跳包给Follower节点以防止Follower节点发起选举，electionTimeout远小于MTBF是为了保证系统的稳定运行。Leader崩溃后，理论上大约只有electionTimeout的时间内服务不可用。

根据存储方式的不同，broadcastTime一般设置为0.5ms到20ms(实验中设置心跳间隔略有不同，推荐是100ms左右，我设置的50ms)，而electionTimeout一般是10-500ms(实验设置的是300+ms)。通常服务器的MTBF一般是几个月甚至几年，很容易符合这个要求。

### 安全性

#### 选举条件

- 包含之前所有提交数据的节点才能作为Candidate
- 如果follower的日志比Candidate更新，就会拒绝投票

新旧定义为比较最后一个数据条目的index和Term，Term大的优先

#### 提交旧Term的数据(不安全)

Leader试图从一个较老的任期提交日志，如图所示，在8-c中，S1为Leader，此时为Term4但是仍在提交Term为2的第二条数据，虽然也提交了半数以上的节点，但这是不安全的，因为如果此时S1宕机，S5被选为Leader，那么Term3的数据会将Term2的数据覆盖。

![覆盖问题](README/image-20220602192605791.png)

#### 安全提交

**条件**

前一条日志相同才能复制成功，leader最新的Term有日志已经复制到过半数节点



# 总结

![image-20220605145059767](README/image-20220605145059767.png)

![image-20220605145113835](README/image-20220605145113835.png)

![image-20220605145121785](README/image-20220605145121785.png)

![image-20220605145130154](README/image-20220605145130154.png)

参考：

[1] Diego Ongaro and John Ousterhout，In Search of an Understandable Consensus Algorithm 

[2] Raft算法分析与实现 https://juejin.cn/post/6844903657540943880