分布式理论——Raft算法学习总结
分布式理论——Raft算法学习总结
Raft算法是分布式系统中一种重要的共识算法，由斯坦福大学的Diego Ongaro和John Ousterhout在2013年提出。它通过将分布式一致性问题拆分为领导者选举、日志复制、安全性、节点变更四个独立子问题，使得算法易于理解和实现。目前，Raft算法已经在多个实际场景中得到广泛应用，如Redis集群、分布式数据库等。本文将对Raft算法的重要概念和实现细节进行详细讲解。
前言
Raft作为目前市面上重要分布式理论背景，有较多实际场景，比如redis集群、分布式数据库，都有Raft算法影子。
一、Raft是什么？
Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout在2013 年发表的《InSearch of an Understandable Consensus Algorithm》中提出。Raft 算法是一类基于日志复制的分布式共识算法，由于Raft 算法易于理解和实现，在提出后，迅速获得了广泛关注，并成为了分布式系统中实际应用最广泛的一致性算法之一。目前，已经有十多种语言的 Raft 算法实现框架，比较有代表性的有 etcd、Consul，CockroachDB等所以说掌握了 Raft算法，就能比较轻松地处理绝大部分的一致性场景和需求
二、Raft重要概念
Raft算法，将分布式一致性问题拆分为四个独立子问题。领导者选举、日志复制、安全性、节点变更
1.领导者选举
1.1 角色
和redis中领导者选举类似，每个节点分为三种状态（角色）
领导者（leader）：
处理客户端请求
管理日志同步
发送心跳包，表明自己存活
跟随者（follower）：
被动响应请求
给候选者投票
将follower接收到的请求转发给leader
候选者（Candidate）：
在集群刚启动或 Leader 容机时，Follower 节点可以转换为 Candidate 并发起选
当 Follower 长时间未接收到 Leader 的心跳信号时，会认为 Leader 可能已经失效，从自己 状态转换为 Candidate 并发起选举。Candidate 向其他节点请求选票，若获得超过半数节点 的投票，它就会成为新的Leader
如果选举胜出，Candidate 转变为 Leader;否则，如果有其他节点当选为Leader， Candidate 会返回到Follower 状态
1.2任期
一种数据结构，用于记录raft集群工作时间段
任期作用如下：
- 每个节点都会保存当前的任期(即一个标识时间段的整数)，并随着集群状态的变化进行更新
- Follower等待Leader的心跳超时后，会推举自己为Candidate发起投票，此时会将当前任期编号加1。比如当前该Follower保存的任期为1，在推举自己为候选人邀票时，会将任期编号增加到2
- 当一个节点发现自己保存的任期编号比另一个节点的任期编号小，它会主动更新自己的任期编号到最新的较大的任期编号，比如节点 A当前的任期编号是1，当收到来自节点 B 的请求投票 的RPC 消息时，因为消息中包含了节点 B的任期编号，且编号为2，那么节点A将把自己的任期编号更新为2
- 如果一个节点接收到一个比自己任期编号小的 RPC 请求，该节点会立即拒绝这个RPC 请求(无论是投票请求还是日志追加请求)。这是因为这个请求的任期编号已经过时，代表着发出请求的节点拥有的是旧任期，不再被视为合法的领导者或候选者
- 如果一个Leader或者是Candidate发现自己的任期编号比其他节点小，该节点会立即退回到Follower，假设由于网络分区错误，集群中出现了两个Leader，LeaderA任期编号为4，LeaderB任期编号为5，当网络分区错误恢复后，LeaderA收到了来自LeaderB的心跳信息，LeaderA将回退为Follower，接收LeaderB成为Leader
1.3超时机制
Raft算法中的随机超时有以下两种情况:
- Follower 等待 Leader 心跳信息的超时间隔是随机的这里的随机化的超时机制可以防止 Follower 同时转换为 Candidate，减少选举冲突
- Candidate 等待选举结果的超时间隔是随机的当一个节点转换为 Candidate 并发起选举 后，会等待其他节点的投票结果，这个等待时间是随机的。如果在这个等待的时间段内，没 有获得大多数选票，将再次随机设置一个等待时间，发起新一轮投票。这里的随机化的超时 机制降低了多个Candidate 同时发起选举的可能性总的来说，在 Raft 算法中，随机超时机制 是一个关键设计保证在大多数情况下只有个节点发起选举，避免多Candidate选举带来的性能 问题
1.4选举流程
1.5脑裂问题
前面所说的情况是在集群完全正常的情况下，一个集群中只会存在一个Leader。假设在-个集群内发发生了网络分区，形成了两个分区，选举情况将会怎样进行呢?这里以5个节点的集群为例，集群节点A,B,C,D,E，节点A为集群Leader。假设发生了网络分区，[A,B,C]为一个分区，节点[D,E]为一个分区，由于A本身就是原集群的Leader所以[A,B,C]分区内还是按照以前的集群模式A为Leader，向B，C节点发送心跳。而[D,E]由于发生了网络分区，收不到A节点的心跳信息了，假设D节点设置的随机超时时间较短，那么到时间后，会成为Candidate，发起投票，成为D,E]这个分区的Leader由于经过了一轮选举，那么[D,E]这个分区的任期将会比[A,B,C]分区的任期大1。这个时候在整个集群[A,B,C,D,E]中就有了两个Leader A和D，这就是“脑裂问题”脑裂问题如何解决?
其实在网络恢复后，虽然有了两个Leader，Leader都会向其他的节点发送心跳信息，这里A和C会互相收到对方发送的心跳信号，但是在A节点收到C节点发送的心跳之后，会发现携带的任期比自身保存的任期要大，所以A节点会会退成Follower，集群会再次恢复成只有一个Leader的状态
2.日志复制
raft算法中第二个很重要的字问题就是日志复制，日志复制(Log Replication)是保证整个集群中的所有节点(follower)一致地存储相同状态的核心机制。它的主要目标是通过将客户端提交的指令(通常是状态变化操作)复制到每个节点的日志中，确保所有节点都达成一致的状态，即一致性
2.1日志
在raft日志其实是一种数据格式，主要用于存储客户端的一些列操作指令，日志由三部分组成，分别是:索引值(Logindex)、任期编号(Term)、指令(Command)
- 索引值:日志条目对应的索引值，用来标识第几条日志，是一个连续单调递增的整数
- 任期编号:创建这条日志条目的 Leader(领导者)的任期编号;
- 指令:客户端发起请求需要执行的指令，例如指令 X-<2 表示将 X变量赋值为 2一条日志也叫日志项，从上图可以看出，在一个Leader的任期内，可以有多个日志项比如任期1内有3个日志项，任期3内有4个日志项
- 日志还对应有两个状态:committed(已提交)和applied(已应用)
- committed:针对的是日志，对应于某个日志项被成功复制到集群的大多数节点之后，这个日 志项就处于committed状态，比如索引值1-7所对应的日志项均处于committed状态，因为他 们都被复制到了大多数节点
- applied:针对的是状态机即节点，节点要将日志真正应用到状态机，即真正改变2.了节点上对 应变量的值
2.2日志复制过程
发起leadRPC请求，将日志想标记为uncommit，在半数以上节点确认复制成功后，标记为committed，之后再将其应用到自己的状态机修改执行指令
2.3日志一致性检查
从前面的日志复制过程可以看出，在日志复制过程中，只要有半数以上的处于正常工作的状态，整个系统就可用，假如在复制日志的过程中，出现了节点宕机、进程中断等问题，可能导致日志不一致，这种情况会怎么处理，怎么来保证各个节点日志的一致性呢
首先看下raft日志的特点，Raft日志具体如下两个特性
- 如果不同日志中的两个日志项有相同的任期编号和索引值，那么这两个日志项一定有相同的指令
- 如果不同日志中的两个日志项有相同的任期编号和索引值，那么这两个日志项之前的所有日志项也全部都相同
通过这两个特征其实可以看出，只要同步到位的日志都是一致的，在raft算法中，其实是以领导者日志为准来实现日志的一致性的，主要包括两个步骤:
- Leader通过日志复制 RPC请求的一致性检查，找到 Follower节点上与自己具有相同日志项的最大索引值(在该索引值之前的日志项，Leader和Follower是一致的，之后不一致)
- Leader强制 Follower更新不一致日志条目，Leader强制Follower将该索引值之后的所有日志项删除，并将Leader该索引值之后的所有日志项同步给Follower
3.安全性
3.1对选举的限制
未防止旧日志覆盖新日志，在进行选举时，会对候选者日志索引、任期进行效验，如果低于本机则不会进行进行投票，以防止旧数据覆盖
3.2对日志提交安全限制
只允许对自己任期内的数据进行进行commit
4.节点变更问题
4.1节点配置
在介绍节点变更过程之间，需要先明确一个概念:配置(configuration)在raft算法中，使用用配置(configuration)来表示集群的节点集合，比如某个集群由A、B、C 三个节点构成，那么集群的配置就是[A,B,C]，在稳定的状态下，所有节点的配置都相同。从这里就可以知道，每个节点是通过这个配置信息来获取集群状态的，比如在选举，日志同步过程中，集群中有哪几个Follower，Leader需要向哪几个节点发送RPC通信都需要通过配置(configuration)来获取
4.2节点变更导致脑裂问题
集群中节点的变更很有可能给集群的一致性带来影响，主要是会影响集群的多数派。我们知道在raft中很多场合都需要多数派的支持，比如在投票中，只有当一个节点收到多数派投票(超过半数)才会成为Leader，在日志同步中，只有当Leader确认将日志项成功复制到多数派(超过半数)节点后，会将该日志项标记为committed，类似的场景还有很多。
而集群节点的变更最主要的就是会影响到多数派，比如在一个三个节点的集群中原本只要2个节点就可以达到多数派，假设现在往集群新增两个节点，则需要三个节点才能达到多数派。
在raft集群中，同样是由Leader 节点负责同步集群的配置信息，当集群中出现节点变更，几平不能保证所有节点同时进行配置的变更，由于网络先后等因素导致一部分节点配置已变更，另一部分没有变更在所难免，所以就会导致集群中部分节点使用的新的配置信息C new，而有的节点使用老的配置信息Cold。
假设有如下场景中，原来集群有三个节点[server1,server2,server3]，现在向集群新增了两个节点server4和server5.
当处于画框的时间点时，假如此时出发了选举，server1和server2用的是旧的配置文件C_old，因此他们会从节点[server1,server2]中选出Leader;而节点server3，server4和server5已经是新的配置文件Cnew了，他们会从节点[server3,server4,server5]中选出新的Leader。此时集群就可能会有两个Leader，出现脑裂问题。
4.3节点变更
采用联合共识算法，类似于mysql中两阶段提交
具体流栏如下:
1.阶段一
a. 客户端将新配置C_new发送给Leader，Leader取旧配置C_old和新配置C_new的并集(称 为联合配置(表示为C_old,new))并立即apply即生效
b. Leader将配置C_old,new包装成日志通过AppendEntries请求复制到Follower节点
c. Follower收到C old,new后立即生效，立刻应用该配置作为当前节点的配置，当 C-old,new 的大多数节点C.(即 C_old 的大多数节点和 C_new 的大多数节点)都切换后，leader 将 commit该日志
2.阶段二
a.紧接着Leader将新配置C_new包装成日志通过AppendEntries请求复制到Follower节点 b.Follower收到 C-new后立即生效，如果此时发现自己不在 C-new 列表，则主动退出集群 c.Leader 确认 C-new 的大多数节点都切换成功后，给客户端发送执行成功的响应
几个概念详细解释一下:
- C_old,new:比如C_old为[A,B,C]，C_new为[B,C,D]，那么C_old,new就为他们的并集[A, B,C, D]
- C_old,new的大多数节点:是指C_old中的大多数和C_new中的大多数，如下表所示，第一列因为C，D节点还没有被复制到日志，导致Cnew的多数派不能达成，所以该日志不能被commit
总结
Raft算法将共识问题分解成了多个相对独立的子问题，从而简化了共识的实现。其主要流程包括领导者选举以及日志复制，集群先选举出leader，然后leader负责复制、提交日志。当然为了在任何异常情况下系统不出错，还需要满足一定的安全性，几需要对Leader Election，Log Replication两个子问题加一些限制条件。最后集群都是动态变化的，所以raft算法也应用了单节点变更以及联合共识机制来保证集群节点安全的变更