五分钟了解一致性算法 -- Raft算法

前言

之前的文章《五分钟了解一致性哈希算法》受到了不少朋友的喜欢，今天分享分布式一致性算法之 -- Raft算法，同样用分钟的方式，不过这次估计五分钟看不完！

没事多两站地铁而已，不过别入迷，坐过站了哦！😆😆

分布式一致性

在分布式环境中，一致性是指数据在多个副本之间是否能够保持一致的特性。

分布式一致性算法

比较常见的一致性算法包括Paxos算法，Raft算法，ZAB算法等

• Paxos是Leslie Lamport提出的一种基于消息传递的分布式一致性算法。很多分布式一致性算法都由Paxos演变而来，但是最大特点就是难，不仅难以理解，更难以实现。
• Raft 是一种相对较新的分布式一致性算法，是一种更易于理解和实现的算法，在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。
• ZAB 协议全称：Zookeeper Atomic Broadcast（Zookeeper 原子广播协议）,是为 Zookeeper 设计的分布式一致性协议！

Raft算法使用场景

一般用做两种场景： 元数据管理：比如etcd，特点是数据规模小，主要保证数据一致性和集群的高可用（raft选主）,所以一套raft集群就够了。 分布式数据库：这种会用partition group，每个group有一个raft集群，当数据变大的时候会做扩展。

🚩 Raft只是个共识算法来保证数据的一致性，与数据库、客户端、事务没有关系

Raft算法基础

Raft把算法流程分为三个子问题：领导选举（Leader election）、日志复制（Log replication）、安全性（Safety）。

角色

• 领导者 Leader：接收处理客户端请求、向Follower进行日志同步、同一时刻最多只能有一个可行的 Leader
• 追随者 Follower：接受并持久化Leader同步的日志，在Leader告之日志可以提交之后，提交日志，处在完全被动状态
• 候选人 Candidate：临时角色，处于 Leader 和 Follower 之间的暂时状态

Raft算法中在任意时刻最多只有一个Leader，正常工作期间只有Leader和Followers。

状态转换

状态切换流程：

1. Raft刚启动的时候，所有节点初始状态都是Follower
2. 超时时间内如果没有收到Leader的请求则转换为Candidate角色并发起Leader选举
3. 如果Candidate收到了多数节点的选票则转换为Leader
4. 如果在发起选举期间发现已经有Leader了，或者收到更高任期的请求则转换为Follower
5. Leader在收到更高任期的请求后转换为Follower

任期

任期：可以理解为是节点担任Leader职务的时间期限。

Raft 将时间划分为一个一个的任期（term），每个任期由单调递增的数字（任期编号）标识，工作期可长可短也可能不存在

🚩 任期时间 = 选举时间 + 正常运行时间

通信

Raft 中服务器节点之间通信通过两个 RPC 调用：

• 请求投票 RequestVote：候选人(Candidate) 选举期间发起
• 日志复制 AppendEntries：领导人(Leader)发起，用于复制 log 和发送心跳

Leader选举

初始状态

初始状态时，每个节点的角色都是 Follower(跟随者)，Term任期编号为 1(假设任期编号从1开始)

不过这两种情况会触发选举：

• Raft 初次启动时，不存在Leader，这时候会触发Leader选举
• Follower在自己的超时时间内没有接收到Leader的心跳heartBeat，触发选举超时，从而Follower的角色切换成Candidate，Candidate会发起选举

选举

既然有两种情况下会触发选举，一个是初次启动，一个是Leader故障未发送心跳给Follower，那么我们假设有五个节点，然后分别用图来看下是如何选举的！

🚩为了画图是不会显得很占空间，暂时用三个节点表示， 并且用 ‘...’表示剩余节点

初次启动时：

初次启动节点都是正常流程如下：

Leader故障时：

Node2此时是Leader 节点，结果故障了，剩下四个节点参与选举。

当选条件

在一个任期（Term）内只可以投票给一个结点，得到超过半数的投票才可成为 Leader，从而保证了一个任期内只会有一个 Leader 产生。

日志同步

概括成一句话就是：保证Leader上日志能完全相同地复制到多台Follower服务器上。

OK！我们看下是如何进行同步的

日志结构

Raft算法中，每个节点维护着一份日志，其中包含了系统中所有状态变更的记录，每一次状态变更被称为一个日志条目。

我们先看日志结构和右侧说明：

图中每个节点存储自己的日志副本(log[])，每条日志记录包含：

• 索引 (log index)：记录在日志中的位置，是一个连续单调递增整数
• 任期号 (term)：日志记录被创建时Leader的任期号，上图中有三个任期
• 命令 (command)：客户端请求指定的、状态机需要执行的指令

执行流程

了解完日志结构后，我们来看日志是如何发起同步的。

日志持久化存储的条件

Follower节点必须先将记录安全写到磁盘，才能向Leader节点返回写入成功响应。

如果一条日志记录被存储在超过半数的节点上，我们认为该记录已提交(committed)——这是 Raft 非常重要的特性！如果一条记录已提交，意味着状态机可以安全地执行该记录

流程如下图：

1. 客户端向 Leader 发送命令，希望该命令被所有状态机执行；
2. Leader 先将该命令追加到自己的日志中；
3. Leader 并行地向其它节点发送AppendEntries RPC，等待响应；
4. 收到超过半数节点的响应，则认为新的日志记录是被提交的：
5. Leader 将命令传给自己的状态机，然后向客户端返回响应
6. 此外，一旦 Leader 知道一条记录被提交了，将在后续的AppendEntries RPC中通知已经提交记录的 Followers
7. Follower 将已提交的命令传给自己的状态机
8. 如果 Follower 宕机/超时：Leader 将反复尝试发送 RPC；

🚩 注：Leader 不必等待每个 Follower 做出响应，只需要超过半数的成功响应（确保日志记录已经存储在超过半数的节点上），一个很慢的节点不会使系统变慢，因为 Leader 不必等待

一致性检查

Raft 通过 AppendEntries RPC 消息来检测。

• 每个AppendEntries RPC包含新日志记录之前那条记录的索引 (prevLogIndex) 和任期 (prevTerm)；
• Follower接收到消息后检查自己的 log index 、 term 与 prevLogIndex 、 prevTerm 进行匹配
• 匹配成功则接收该记录，添加最新log，匹配失败则拒绝该消息

日志一致性

Raft算法的目的是保证所有节点的一致性，即一个日志条目在某个节点被提交，那么这个日志条目也必须在所有节点上被提交。

🚩 通过【一致性检查】就保证了日志一致性的这两点内容。

• 如果两个节点的日志在相同的索引位置上的任期号相同，则认为他们具有一样的命令，从头到这个索引位置之间的日志完全相同
• 如果给定的记录已提交，那么所有前面的记录也已提交