分布式系统 共识算法Raft

前提

设备限制 ：

单台设备的核心数/内存/存储存在最大上限，随着单台设备的性能越高，设备的成本也就快速增加

一致性：

立即一致性

最终一致性

应对网络的不可靠以及节点的失败：

可读写

可读

不可用

组织机器使其状态最终一致并允许局部失败的算法称之为一致性算法

复制状态机

一致性算法的目标就是保证集群上所有节点的状态一致，节点要执行的指令可以分为两种，读和写，只有写指令会改变节点状态，因此为了保证集群各个节点的状态一致，那就必须将写指定同步给所有节点。

理想状态下，我们期望任意节点发生写命令都会立即的在其他节点上变更状态，这其中没有任何时延，所有节点都好像是单机一样被变更状态。

网络延迟要远远慢于内存操作，写入命令不可能被同时执行，因此如果在不同节点发生不同的写命令，那么在其他节点上这些写命令被应用的顺序很可能完全不同。

如果我们不要求所有节点的写命令立即被执行，而仅仅是保证所有的写命令在所有节点上按同样的顺序最终被执行，则可以进行1.允许一个节点处理写命令，2.所有的节点维护一份顺序一致的日志

每个节点上的状态机按照自己的节奏，逐条应用日志上的写命令来变更状态

定义问题

1. 输入:写入命令
2. 输出: 所有节点最终处于相同的状态
3. 约束
   1. 网络不确定性： 在非拜占庭情况下，出现网络分区/冗余/丢失乱序等问题下要保证正确
   2. 基本可用性： 集群中大部分节点能够保持相互通信，那么集群就应该能够正确响应客户端
   3. 不依赖时序：不依赖物理时钟或极端的消息延迟来保持一致性
   4. 快速响应：对客户端请求的响应不能依赖集群中最慢的节点

一个可行解

1.初始化的时候有一个领导者节点，负责发送日志到其他跟随者，并决定日志的顺序

2.当读请求到来时，在任意节点都可以读，而写请求只能重定向到领导者进行

3. 领导者先写入自己的日志，然后同步给半数以上节点，跟随者表示都Ok，领导者才提交日志
4. 日志最终由领导者先按顺序应用于状态机，其他跟随者随机应用到状态机
5. 当领导者崩溃后，其他跟随着通过心跳感知并选举出新的领导者继续集群的正常运转
6. 当有新的节点加入或退出集群，需要将配置信息同步给整个集群

Raft实现

状态:

1 Follower : 接收来自Leader 的保活报文，当定时器超时后，角色变更为Candidate, 发起竞选过程，作为Follower, 可以参与竞选阶段，但是票只能投给Candidate

2 Candidate : 作为竞选者，参与竞选，触发竞选过程，先给自己投一票，然后发起请求给其他节点，请求为该节点投票，当所得票数超过一半的节点数后，变更为Leader。而当竞选计时器超时后，重新发起选举。而如果这期间收到了Leader的保活报文/收到了更高任期的请求，则变更为Follower状态

3 Leader : 作为领导者，负责发送心跳报文，确保自己和其他节点的保活状态。通过会发送请求要求其他节点复制它所记录的日志信息

1. 启动阶段 ：所有节点都被设置为Follower状态
2. Follower 启动心跳计时器，监听是否能接收到来自领导者的保活信息
3. 监听一段时间后未能收到保活信息后，将自身设置为竞选者，参与竞选，这时竞选者会向其他节点发送投票请求
   1. 投票成功 变更为Leader,发送心跳报文给其他节点
   2. 投票失败 更新任期，重新发起竞选
   3. 收到 Leader的保活信息，状态变更为Follower
   4. 当存在多个领导者时，比较任期大小，任期更大的作为新的领导者
4. 设置 心跳计时器 和 选举计时器 为区间内的随机值，这样避免选票瓜分问题

不同状态的数据结构

共同结构

currentTerm	服务器已知最新的任期（在服务器首次启动的时候初始化为0，单调递增）
voteFor	当任期内收到选票的候选者id,如果没有投给任何候选者，则为空
log[]	日志条目；每个条目包含了用于状态机的命令，以及领导者接收到该条目的任期

通用容失性状态

LastApplied	已经被应用到状态机的最高的日志条目索引
CommitIndex	已知已提交的最高的日志条目的索引

领导者的易失性状态

nextIndex[]	对于每一台服务器，发送到该服务器的下一个日志条目索引(初始值为领导者最后的日志条目的索引+1)
matchIndex[]	对于每一台服务器，已知的已经复制到该服务器的最高日志条目的索引 （初始值为0）

RPC

选举人发起选举投票RPC到跟随者或选举人

领导者发起RPC到跟随者 ： 日志追加 / 心跳通知

请求投票

1. 跟随着变更为候选人后
2. 选举超时后

请求参数

参数	解释
term	候选人的任期号
candidateId	请求选票的候选人的id
lastLogindex	选举人的最后日志条目的索引值
lastLogTerm	选举人最后日志条目的任期号

返回值

返回值	解释
term	当前任期号，以便于候选人去更新自己的任期号
voteGranted	候选人赢得了此张选票时为真

选举规则

1. 如果领导者的任期 小于 接收者的当前任期，则直接返回假
2. 在接收者日志中，如果能找到一个和preLogIndex以及prevlogTerm 一样的索引和任期的条目 则继续执行下面的步骤，否则返回假
3. 如果一个已经存在的条目和新条目发生了冲突（索引相同，任期不同），那么就删除这个已经存在的条目以及它之后的条目
4. 追加日志中常委存储任何新的条目
5. 如果领导者的已知已经提交的最高的日志条目的索引leaderCommit大于接收者的已知已提交的最高的日志条目CommitIndex，则把接收者的日志条目的索引commitIndex重置为领导者的已知已经提交的最高的日志条目索引，或最新日志条目的索引 取两者最小值

追加日志&心跳

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

请求参数

参数	解释
term	当前领导者的任期
leaderId	领导者ID 因此跟随者可以对客户端进行重定向
prevLogIndex	紧邻新日志条目之前的那个日志条目的索引
prevLogTerm	紧邻新日志条目之前的那个日志条目的任期
entries[]	需要被保存的日志条目（被当作心跳使用时，则日志条目内容为空；）
leaderCommit	领导者的已知已提交的最高的日志条目的索引

返回值

返回值	解释
term	当前任期，对于领导者而言，它会更新自己的任期
success	结果为真，如果跟随者所含有的条目和prevLogIndex以及prevLogTerm匹配上了

日志追加

1. 一旦成为领导人： 发送空的附加日志RPC 给其他所有的服务器，在一定的空余时间之后不停的重复发送，以阻止跟随者超时
2. 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端
3. 如果对于一个跟随着，最后日志条目的索引值大于等于nextIndex，那么：发送从nextIndex开始的所有日志条目
   1. 如果成功，更新响应跟随着的nextIndex和matchIndex
   2. 如果因为日志不一致而失败，减少nextIndex重试
4. 如果存在一个满足N>commitIndex的N，并且大多数的matchIndex[i] ≥ N成立，并且log(N).term == currentTerm 成立，那么令commitIndex等于这个N

安全性证明

特性	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来
领导人只附加原则	领导人绝对不会删除或者覆盖自己的日志，只会追加
日志匹配规则	如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们旧认为整个日志从头到这个索引位置之间完全相同
领导人完全特性	如果某个日志条目在某个任期号中已经被提交，那么整个条目必然出现在更大任期号的所有领导人中
状态机安全特性	如果一个领导人已经将给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在整个索引位置不会应用一个不同的日志

日志复制过程的完全匹配

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

安全性

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

工程优化

容错性

1. 领导者崩溃通过选举可以解决，但跟随着与候选者？

基础raft算法，通过无限次幂等的附加复制rpc进行重试来解决

1. 当平均故障时间大于信息交换时间，系统将没有一个稳定的领导者，集群无法工作

广播时间<< 心跳超时时间 << 平均故障时间

1. 客户端如何连接raft的server节点

客户端随机选择一个节点取访问，如果是跟随着，跟随着会把自己知道的领导者告知客户端

1. 领导者提交后返回时崩溃，客户端重试不就导致相同的命令反复执行？

客户端为每次请求标记唯一序列号，服务端在状态中维护客户端最新啊的序列号标记，进行幂等处理

1. 客户端给领导者set a=3 并进行了提交，此时客户端如果从一个未被同步的节点读取a读不到写后的值

每个客户端应该维持一个lastestldx值，每个节点在接收读请求的时候与自己的lastApplied值比较，如果这个值大于自己的lastApplied，则拒绝此次请求，客户端重定向到一个lastApplied大于等于自己laststIdx的请求，并且每次读取请求都会返回这个节点的lastApplied值，客户端将latestIdx更新为此值，保证读取的线性一致。

1. 如果leader被孤立，其他跟随着选出leader，但是当前leader还是向外提供脏数据怎么办？

写入数据由于无法提交，因此会立即失败，但无法防止读到脏数据

解决办法： 半数心跳失败，leader感知自己处于少数分区而被孤立进而拒绝提供读写服务

1. 当出现网络分区后，被孤立少数集合的节点无法选举，只会不断的增加自己的任期，分区恢复后由于失联的节点任期更大，会强行更新所有节点的任期，触发一次重新选举，而又因为其日志不够新，被孤立的节点不可能成为新的leader所以其状态机是安全的，只是触发了一次重新选举，使得集群有一定时间的不可用

在跟随者成为候选人时，先发送一轮pre-vote rpc 来判断自己是否在大多数分区内，如果是则任期加1进行选举，否则的话就不断尝试pre-vote请求

扩展性

向集群中新增节点

会存在某一个时刻新老配置同存，进而有选举出两个领导者的可能性

1. 新集群节点在配置变更期间必须获得老配置的多数派投票才能成为leader
2. 发送新配置c-new给集群的领导者
3. 领导者将自己的c-old配置与c-new合并为一个c-old-new 配置
4. 然后下发给其他所有跟随者
   1. 当c-old-new 被同步给半数以上节点后，那么此配置已经提交，遵循raft安全机制
   2. 当leader在将c-old-new写入半数跟随者之前崩溃了，那么选举出来的新leader会退回到老的配置，此时重试更新配置即可
5. 当c-old-new被提交之后，leader会真正的提交c-new配置
   1. 如果提交给了半数节点，则c-new真正的被提交
   2. 如果未提交给半数节点时崩溃，则选举新的leader，必定包含c-old-new，更新配置即可

2 单节点变更时，如果leader挂了，造成一致性问题如何处理

新节点先发一条no-op日志再开始配置变更

Raft成员变更的工程实践

1. 单节点变更时，偶数节点遇到网络分区，则没办法选举leader了怎么办

重新定义偶尔节点情况下的法定人数模型下的大多数情况

1. 新服务器没有任何存储日志，需要复制很长时间不能参加选举否则会使得整体不可用

新加入节点设置一个保护器，在此把耦合器内不会参加选举与日志提交决策，只会用来同步日志

1. 如果集群中的领导不是集群中的一员，该如何处理

在提交c-new时，不将自己算作半数提交，并且在提交后要主动退位

1. 被移除的节点如果不即时关闭，会导致选举超时后强行发起投票请求干扰在线集群

每个节点如果未达到最小心跳超时事件，则不会进行投票

性能

1. 生成快照

日志如果无限增长会将本地磁盘打满，会造成可用性问题。

定时将状态机种的状态生成快照，而将之前的日志全部删除，是一种常见的压缩方式

1. 将节点的状态保存为LSM Tree，然后存储最后应用日志的索引和任期，以保证日志匹配特性
2. 为支持集群的配置更新，快照中也要讲最后一你个用的集群配置也当作状态保存下来
3. 当追随者需要的日志已经在领导者上面被删除时（nextIndex—）需要讲快照通过RPC发送

参数

参数	解释
term	领导人的任期号
leaderId	领导人的id，以便于跟踪者重定向请求
lastIncludeIndex	快照中包含的最后日志条目的索引值
lastIncludeTerm	快照中包含的最后日志条目的任期号
offset	分块在快照中的字节偏移量
data[]	从偏移量开始的快照分块的原始字节
done	如果这是最后一个分块则为true

返回

结果	解释
term	当前任期号，便于领导人更新自己

跟随者创建快照

1. 如果term < currentTerm
2. 如果是第一个分块 （offset 为 0 ） 就创建一个新的快照
3. 在指定偏移量写入数据
4. 如果done是false，则继续等待更多的数据ack
5. 保存快照文件，丢弃具有较小索引的任何现有或部分快照
6. 如果保存的日志条目与快照中最后包含的日志条目具有相同的索引值和任期号，则保留其后的日志并
7. 否则，丢弃整个日子hi
8. 使用快照重置状态机

调节

参数

1. 心跳的随机时间，过快会增加网络负载，过慢则会导致感知领导者崩溃浪费的事件更长（100-300ms）
2. 选举的随机时间，如果大部分跟随者同时变为候选人则会导致选票被瓜分

流批结合

并行追加

异步应用

总结

Raft 共识算法的 核心点在于通过算法，可以保持多个节点上的存储一致性。

它定义了三个角色：

Follower ： 跟随者

接收来自Leader的心跳保活和日志追加请求；

当心跳保活超时后，会尝试转换为Candidate；

作为Follower的节点在选举流程中只能进行投票；

Candidate ： 候选人

当集群环境失去Leader角色时，由Follower转换为Candidate 发起选举

保留一个选举超时计时器，当计时器超时仍未成功选举时，将任期+1，继续尝试发起选举

选举时会先为自己投票，之后向其他节点发送投票的远程调用

当发起选举请求的过程中收到了来自Leader的心跳保活，切换状态回Follower

Leader ：领导者

当投票流程结束后，自己所获选票超过集群的半数节点以上，该节点自动转换为Leader

Leader 负责处理集群中日志的写操作，以及发送心跳保活和日志追加数据到其他跟随者节点

关键定义

对于 Raft中的角色来说，存在以下关键属性

属性名	定义	用途
currentTerm	节点自身持有的任期信息，从服务器启动后开始计数	提供了一个计数器，用于快速比较节点间的“领导性”
voteFor	任期内收到选票的候选者id,如果没有投给任何候选者，则为空	用于标记当前服务器的投票状态，每个节点只能投一票
log[]	日志条目；每个条目包含了用于状态机的命令，以及领导者接收到该条目的任期
LastApplied	已经被应用的日志索引条目	确认哪些信息是已经通过共识协议应用的 (大部分节点认为已应用)
CommitIndex	已知已提交的最高的日志条目	确定哪些信息是已经提交的（大部分节点认为已提交）
nextIndex[]	当前服务器期望接收的下一条日志索引	用于通知/校验其他节点，保证消息的顺序性
matchIndex[]	已知的已经复制到该服务器的最高日志条目索引	用于在追加日志时，记录当前同步信息的位置

选举过程

Raft 中使用了3种 计时器：

1. 选举计时器 ： 用于选举者选举超时时，重置选举请求 。 通常为一个随机时间（100-300ms）
2. 心跳保活计时器 ： 用于领导者向跟随者请求，相互检查对方的存货状态，超时后意味着节点状态异常，触发其他节点的选举过程。
3. 心跳保活超时计时器： 用于追随者等待领导者心跳的最大时长，超时后变更状态，发起选举过程。

投票策略

作为Candidate， 会先为自己投票，再想其他节点发送RPC请求

作为Follower，接收到RPC请求后，会进行以下处理：

1. 检查任期长度

当请求中描述的任期小于当前节点的任期时，直接拒绝投票给该Candidate

1. 检查自身是否已经进行过投票

当自身已经进行过投票了，直接拒绝投票给该Candidate

1. 比较收到的最后一条日志的索引

• 首先比较最后一条日志的任期 ：任期更大的日志更新
• 任期相同时才比较索引 ：索引更大的日志更新

投票过程

1. 集群失效后，某个节点，优先心跳超时计时器超时，将自身状态变更为Candidate。先为自己投一票，然后包装自己的任期，和ID，以及最后条目索引和最后条目的任期号属性，发送RPC调用给其他集群中的节点
2. 其他节点接收到该请求后，启动投票流程，检查该节点的任期，和自己投票状态，比较双方的索引长度， 最终确认投票
3. 竞选节点 接收到 超过半数的投票后，切换状态到领导者，定时向其他节点发送保活报文，并且发起PRC请求，向其他节点追加日志记录最终达成共识

日志追加

1. 完成选举后，由Leader发起日志追加请求
2. 对于Leader来说，最终的追加目的是在当前任期内，所有跟随者都依据Leader的索引顺序进行提交/应用过程。所以这里会做的是在日志追加过程中比较Leader 的prevLogIndex和prevLogTerm , 如果不一致则回溯到两者的一致索引位置，之后由Leader完成日志追加过程。

基于实际情况的讨论

现在我们从现实情况下讨论共识性算法的安全性问题。

共识性算法保证最终一致性的组件 ：

通过监听保活的失效触发选举过程 → 保证系统绝大部分时间内处于Leader/选举过程当中。

通过任期比较，选择具有更长任期的候选者/通过lastcommit 比较，选择lastcommit 索引最长的候选者作为领导者。

那么结果就是我们最终会选择一个最早发现心跳失效，且具备日志最长的应用记录的节点作为合适的领导者。又因为应用需要半数以上节点确认后才会被应用，所以具有最长任期，最长日志应用记录的节点必然是具备最完整日志记录信息的节点。