分布式系统-一致性算法-Raft算法

偏执的太偏执、 2021-09-18 03:54 609阅读 0赞

# Raft算法介绍 #

raft是一个协议，可以用来实现分布式系统的一致性。

## raft算法中节点的三种状态 ##

Leader：处理所有客户端交互，日志复制等，一般一次只有一个Leader

Follower：随从，完全被动

Candidate：候选者

## 一个简单的工作流程 ##

### 1.领导的选举过程 ###

这三种状态可以通过选举机制互相转换。所有节点在初始状态下都是以随从份出现，如果follower没有听到领导者的指令，他就会变成候选者，给所有的其他节点发送投票，其他节点回复候选者的投票，如果一个节点受到大多数节点（包括自己投自己）的投票，那么该节点从候选者变成领导者。

#### **初始状态** ####

![18721752-1491ac8c0726e57a.png][]

image.png

#### **候选者状态，并给所有节点发送投票请求** ####

![18721752-82b116841568cba3.png][]

image.png

#### 变成领导者 ####

![18721752-1286bc3b13d5e63b.png][]

image.png

### 2.主节点数据同步过程（日志复制） ###

#### 客户端数据提交 ####

所有对于系统的改变都必须通过领导。

**客户端更新数据5，发送给领导**

![18721752-22d5f1624d2795d4.png][]

image.png

每一个改变命令都会变为节点日志，此时领导者没有提交数据5。

#### 主节点复制数据发给随从节点 ####

![18721752-cbd77f4bef5d508c.png][]

image.png

随从节点收到数据后，响应领导，同时领导节点等待大多数节点的响应，如果领导节点受到大多数节点的响应，就提交数据

#### 领导提交数据，提交成功后，通知随从节点提交数据 ####

![18721752-f82fecc87c5b1f40.png][]

image.png

#### 随从节点提交数据 ####

![18721752-062bdd111344bca1.png][]

image.png

主节点响应客户端数据提交成功。

## Raft算法包括两个部分 ##

Leader Election & Log Replication

## Leader Election ##

### 选举超时(Election timeout) ###

随从变为候选者的过程，这个时间一般为150ms到300ms。

![18721752-de04c150b46a603c.png][]

image.png

先结束自旋的节点变成候选人。

![18721752-4feb6e8a14f883bb.png][]

image.png

term:1 第一轮

vote count : 1 首先自己投自己一票

#### 发起投票请求 ####

![18721752-3a68c0bccf872530.png][]

image.png

#### 其他节点收到投票请求，进行投票 ####

![18721752-9ed4562e99b56052.png][]

image.png

在同一轮中，如果收到投票请求的节点，还没有投票则可以允许他进行投票，但是如果他已经投过票了，则不允许继续投票，即同一轮中同一个节点只能投一票。

#### 同时投完票的节点重新进入自旋状态 ####

重新进入选举超时，防止领导节点挂了

![18721752-a9c6baf99e5c022b.png][]

image.png

#### 领导为随从发送日志 ####

![18721752-af4ec5dcf67b8fc3.png][]

image.png

### heartbeat timeout ###

消息发送也有超时时间即心跳超时。

领导者和随从维持心跳检查，如果超时则随从节点满足选举超时，重新进入选举过程。

所以heartbeat timeout<vote timeout

![18721752-1b79be251fedde23.png][]

image.png

这一届领导班子一直会维系到一个随从节点停止接收心跳并且成为了一个候选者。

### 领导节点故障 ###

#### 其中一个节目率先变成候选者 ####

![18721752-e44aa586715701ee.png][]

image.png

#### 进行第二轮投票 ####

![18721752-01b40f1ee00ce6c7.png][]

image.png

自己一票，B节点一票，虽然受不到节点A的投票，但是期已经获得了大多数投票，所以此时C胜利当选。一轮投票只能产生一个领导。

### 投票分离 ###

某一轮选举过程中出现多个候选者

#### A,D节点同时变成候选者，向随从节点发送投票请求 ####

![18721752-9c3746a6ed99359a.png][]

image.png

随从节点将票投给先到达该节点的投票请求的一方，同时拒收其他节点的投票请求。

![18721752-3578b62955ff77c1.png][]

image.png

图中，B节点先收到A的投票请求，投票给A，同时拒收D的投票请求。同时C投票给D，那么本轮投票A,D票数相同，那么所有节点重新进入自旋。

#### 所有节点重新进入选举超时（自旋） ####

等待节点重新变成候选者，并且重新进行选举，直到选出新的领导人。

![18721752-5838d3a58463a51e.png][]

image.png

## Log Replication ##

日志复制，每次同步数据都必须在心跳时间内将数据同步请求发送出去

![18721752-7c6b132e83f32405.png][]

image.png

### 客户端请求领导节点 ###

![18721752-e2eb1c7c4c760242.png][]

image.png

### 领导节点在下一次心跳中，将日志同步给随从节点 ###

![18721752-c7202b0a02a047e4.png][]

image.png

### 大多数节点都回复领导节点 ###

![18721752-91734de1dd66d1bb.png][]

image.png

### 此时领导节点可以提交数据，同时领导节点响应给客户端 ###

此时不通知随从节点提交数据

![18721752-2d22b63e410cd7f8.png][]

image.png

### 领导节点在下一次心跳中，通知随从节点提交数据 ###

同时随从节点提交后，响应给领导节点

![18721752-4964d242446049b2.png][]

image.png

## Raft算法在网络分区中如何保证一致性 ##

在Raft算法中，如果出现网络分区，会有一个区域分得当前领导节点，该节点因为收不到大多数请求的响应而拒绝提交数据，而其他区域重新选举，等到网络分区结束，统一听最新选举产生的领导节点，老领导退位回滚网络分区过程中未提交的数据，然后同步最新领导的数据。

### 网络分区过程中Raft算法保持一致性的过程 ###

![18721752-fec8ef7adff4be9c.png][]

image.png

#### network partition(网络分区) ####

![18721752-6cc92782bd76d57d.png][]

image.png

#### 原领导节点不在的区域重新进行选举 ####

此时B节点作为领导节点分给了下半个区域，其所在的区域不用重新选举，而上半个区域没有领导则需要重新进行选举

![18721752-907762ecfbf79a99.png][]

image.png

#### 客户端请求（下半区） ####

因为网络分区了，所以此时分出了两个客户端，每个客户端只能访问自己所有区域的领导者。

![18721752-e6ef0b852cb27966.png][]

image.png

#### uncommitted ####

此时无论客户端请求B节点保存任何数据，B节点都会回复客户端保存失败，因为B节点作为原先的领导，此时只收到了节点A的同步回复，并没有收到大多数的回复，所以此时节点B不能提交数据，回复客户端提交失败

![18721752-71e79896d8cee566.png][]

image.png

#### 客户端请求（上半区） ####

![18721752-547c06cabd8f5c7a.png][]

image.png

因为上半区是新选举出来的领导，可以获得大多数同步回复，所以可以正常提交数据。

#### 网络恢复 ####

此时B(Term:1)要听更高一轮选举（C term:2）的命令，所以B要退位,然后A,B两个节点没有提交的日志（数据）回滚，然后接收新领导的数据。

![18721752-18ce97a655e929c7.png][]

image.png

![18721752-7accf53332df3813.png][]

image.png

从而达到节点数据一致。

[18721752-1491ac8c0726e57a.png]: /images/20210918/2119f81c23e340bf8f8085f1ea4acc6d.png
[18721752-82b116841568cba3.png]: /images/20210918/e61e42639741451caf4f7f0423730953.png
[18721752-1286bc3b13d5e63b.png]: /images/20210918/4c4084e8250142d5b2a1d8f91a42b743.png
[18721752-22d5f1624d2795d4.png]: /images/20210918/8dd0f0c09868475d92b7b9a92fa00891.png
[18721752-cbd77f4bef5d508c.png]: /images/20210918/37f3460fba6145a3abfa2dcd0c34b948.png
[18721752-f82fecc87c5b1f40.png]: /images/20210918/8ff02ef512e94eaf8118e3ed83275864.png
[18721752-062bdd111344bca1.png]: /images/20210918/a329db3da6ee49d78e9e26b55d011963.png
[18721752-de04c150b46a603c.png]: /images/20210918/7ae07e158af64ee1aa8833924e3776e8.png
[18721752-4feb6e8a14f883bb.png]: /images/20210918/3be8516ea95b4c188731aeded07e8d90.png
[18721752-3a68c0bccf872530.png]: /images/20210918/89b5d1413c204dc1ba009e50ac2c6c77.png
[18721752-9ed4562e99b56052.png]: /images/20210918/03d615b9c46e4940b6e816e0fc869af3.png
[18721752-a9c6baf99e5c022b.png]: /images/20210918/c2a7d45f1a254addbabba31788145002.png
[18721752-af4ec5dcf67b8fc3.png]: /images/20210918/7c2cf3cfd8e844ba948208248d418497.png
[18721752-1b79be251fedde23.png]: /images/20210918/26ad19c6f9c64b9aaa5e5f200fd5127f.png
[18721752-e44aa586715701ee.png]: /images/20210918/615f6e89b4dd49e1a089282d85a6b7b8.png
[18721752-01b40f1ee00ce6c7.png]: /images/20210918/1d79f0ac457f483892d63dc32a01391f.png
[18721752-9c3746a6ed99359a.png]: /images/20210918/cb7a7e05ab6141c59f5ea9180ac0f126.png
[18721752-3578b62955ff77c1.png]: /images/20210918/519263759e504fd2ba0b98a10e0e07be.png
[18721752-5838d3a58463a51e.png]: /images/20210918/1a8ed5d5baf14962b9ddc397ab7912a5.png
[18721752-7c6b132e83f32405.png]: /images/20210918/5bf573f0062b4d63877da4224b36a0bf.png
[18721752-e2eb1c7c4c760242.png]: /images/20210918/c8f9d92625434f2b938b0318e6bc9bf9.png
[18721752-c7202b0a02a047e4.png]: /images/20210918/c1091144566b430bb8b21acf838f0cf6.png
[18721752-91734de1dd66d1bb.png]: /images/20210918/3bc6d0c1bdf8441a93d548e3168fd04a.png
[18721752-2d22b63e410cd7f8.png]: /images/20210918/e402e5102436430ab89704941818a83d.png
[18721752-4964d242446049b2.png]: /images/20210918/63de3bd6df5c467d8fcff4e85511cae8.png
[18721752-fec8ef7adff4be9c.png]: /images/20210918/1b7362b37d2a4528ade0582c9cde8849.png
[18721752-6cc92782bd76d57d.png]: /images/20210918/6fd5ee92d87e4f99ae577a5cdd1f37a9.png
[18721752-907762ecfbf79a99.png]: /images/20210918/fb2e80a2e6a74ea7a22df37e29b43103.png
[18721752-e6ef0b852cb27966.png]: /images/20210918/4ecdc82b9a6c4de7ad4d6436f1fcf17d.png
[18721752-71e79896d8cee566.png]: /images/20210918/670f5cdf4b2348b697a9b7c53aa26695.png
[18721752-547c06cabd8f5c7a.png]: /images/20210918/0fbe5065459741299bc5507e2b183cae.png
[18721752-18ce97a655e929c7.png]: /images/20210918/1aa09ed541414283b28277552c4d529f.png
[18721752-7accf53332df3813.png]: /images/20210918/447809b9472948ceb70746ad5f248902.png