Raft
在 Raft算法 这篇博客中，我们初步学习了Raft算法，但是介绍的不够详细，我会在原来的基础上增加一部分内容
在介绍Raft算法前，我们首先要知道Paxos算法，但是它难以理解，状态空间十分复杂，因此没有构建显示系统的统一基础。由此才提出了Raft算法。
- Raft算法的应用：
- 分布式KV系统，etcd
- 微服务基础设施，consul
简介
raft是一个共识算法（consensus algorithm），所谓共识，就是即使在部分节点故障、网络延时、网络分割的情况下，多个节点对某个事情达成一致的看法
而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication），在 带着问题学习分布式系统之中心化复制集 一文中介绍了中心化复制集的相关知识。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。
简单概括算法就是：raft会先选举出leader，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followes会重新选举出新的leader。
基本知识
在正式介绍方法前，我们先来介绍一些基本知识
复制状态机
共识算法的实现一般是基于复制状态机（Replicated state machines），何为复制状态机：
If two identical, deterministic processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.
简单来说：相同的初识状态 + 相同的输入 = 相同的结束状态。引文中有一个很重要的词deterministic，就是说不同节点要以相同且确定性的函数来处理输入，而不要引入一些不确定的值，比如本地时间等。如何保证所有节点 get the same inputs in the same order，使用replicated log是一个很不错的注意，log具有持久化、保序的特点，是大多数分布式系统的基石。
因此，可以这么说，在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用log entry中的command，则状态肯定是一致的。
如上图，在这个server中记录了日志 x<-3,y<-1,y-9(第二步)，那么日志发送给其他server之后(第二步)，其他server的状态也会和这个一致(第三步).
结合数据库来看，数据库会产生日志，实际上就是状态机中的log模块，数据库之间同步的时候，会先把日志部分同步到其他机器上，通过raft协议认证过日志之后(主要是在第二步)，就可以应用到数据库当中。
任期
在Raft算法中，哪个节点做leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。这根民主社会的选举很像，每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。
如下图所示，是一个时间轴上的几种任期的情况
第1、2、4是正常的任期，即先进行选举，然后是常规操作(复制日志等)
第3个任期没有产生leader，说明选举失败了，那么会直接开始下一个任期，发起新的选举，没有常规操作。后面会解释这种 split vote 的情况。
- 时间按任期划分，通过任期识别过时消息等
- 每个任期从Leader选举开始，选举结束后才正常处理客户端请求
- 存在某些选票被瓜分的情况，没有Leader产生，开始下一个任期
term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；
为什么要设置term？term就相当于把系统时间切成不规则的一片一片，每个term的作用就是确保一段时间内只能有一个leader。因为在分布式系统中，很容易出现脑裂的问题(出现多个leader)，那么这时候两个leader之间很容易出现矛盾，无法保证系统的一致性。Raft采用Term的方法，确保当前任期内只会选举出一个leader，且上一个term的leader不能管理下一个term。
三种角色
- Leader: 响应客户端的请求，同步数据
- Candidate: Leader选举时的状态，获得多数选票可担任Leader
- Follower: 初始启动状态，接收日志同步请求并响应
三种远程过程调用(RPC):
- RequestVote RPC : 用于Candidate收集选票
- AppendEntries RPC: Leader日志复制或发送心跳(不含日志项)
- InstallSnapshot RPC: Leader通过此RPC发送快照给Follower
Leader election
在raft协议中，一个节点任意时刻都处于以下三个状态之一：
- Leader
- Follower
- Candidate
给出状态转移图能很直观的知道这三个状态的区别：
什么时候会发起选举？
首先，所有节点启动时都是follower状态
如果在一段时间内如果没有收到来自leader的心跳，此时leader可能出错/挂了，此时节点从follower切换到candidate，发起选举
如果收到大多数节点的票（含自己的一票），节点会切换到leader状态
- 如果节点发现有一个节点比自己先更新，则主动从candidate 切换到follower。如果上一个Leader收到下一个任期的Leader发送的消息，也会从leader切换到follower
总之，系统中最多只有一个leader，如果在一段时间里发现没有leader，则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息，表明自己的存活状态。如果leader故障，那么follower会转换成candidate，重新选出leader。
选举过程
一个Follower在随机的选举超时时间内(election timeout)内没有收到来自Leader的心跳（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），就会发起选举，选出新Leader
步骤如下：
- 增加节点本地的 current term ，切换到candidate状态
- 投自己一票
- 并行给其他节点发送 RequestVote RPCs
等待其他节点的回复
在这个过程中，根据来自其他节点的消息，可能出现三种结果
结果1
- 收到majority的投票（含自己的一票），则赢得选举，成为leader
第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。在这里，先回到投票者的视角，投票者如何决定是否给一个选举请求投票呢，有以下约束：
- 在任一任期内，单个节点最多只能投一票
- 候选人知道的信息不能比自己的少（这一部分，后面介绍log replication和safety的时候会详细介绍）
- first-come-first-served 先来先得
结果2
- 被告知别人已当选，那么自行切换到follower
第二种情况，比如有三个节点A B C。A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower。
例子-初始状态
正如下面这个gif所展示的。
- 一开始处于橘黄色阶段，大家都是Follower
- S4和S5的等待时间相继结束，S4快一点，S5结束的时候因为没有收到来自S4发送的选举消息，还以为没人发起选举，于是也开始发送。
- S4和S5首先把第一票都投给自己了，然后向其他节点发送选举信息，其他节点收到信息后会给发送者投票。每个节点只能投一票，先到先得。投票显示为
+号，如果已经投给别人了，再收到选举信息，则会返回-号- 我们看到：S1先收到S4的选举信息，然后收到S5的选举信息，因此给S4返回+，给S5返回-
- S2先收到来自S5的选举信息，然后收到S4的选举信息，因此给S5返回+，给S4返回-
- S3先收到来自S4的消息，然后收到来自S5的消息，因此给S4返回+，给S5返回-
- S4、S5收到来自对方的消息后，由于已经把票给了自己，所以都回给对方 -
- 最终，S4收到了S4、S1、S3的票, 是大多数，由此称为Leader
结果3
- 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
例子-server挂了
如下图所示，在第二个任期中，S2是Leader，然后我们手动让S2挂机
- 此时只剩下四个节点了，S1和S3因为收不到来自Leader的心跳，term结束后便发起了投票。
- 由于只剩下4个节点，S1和S3由于发送的消息过于同步，导致每个节点都获得了两票，由此在term3中无法选出leader
- 因此某个节点term3结束后，会立即进入term4，并向外发送选举信号，开启新一轮选举。
因此raft引入了randomized election timeouts来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
重要保证
- 随机的选举超时时间(150-300ms) ，减少3.3中瓜分选票的情况
- 每个人起内最多一个Leader，任何节点收到之前任期的消息都不会影响现在的状态
- 选票先到先得，只要请求消息满足要求(任期+日志)则投票
- 大多数选票原则，这也要求每个节点在每个任期内有且只有一张选票
日志复制
当有了leader，系统应该进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
日志复制
每个节点上的日志复制流程有是怎么样的呢？
- 复制： 某个日志把写入到Follower的日志中
- 提交：如果当前任期内的日志项被多数节点写入，则可以变为提交状态。此状态下日志项不再被修改
- 应用： 将已经提交的日志项应用到状态机，会真正影响节点状态
不难看到，logs由顺序编号的log entry组成 ，每个log entry除了包含command，还包含产生该log entry时的leader term。从上图可以看到，五个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性，leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。
复制过程
当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤
- 客户端将包含一条指令的请求发送到Leader上
- Leader把这条指令作为日志项附加到本地的日志中，并发送AppendEntriesRPC给其他服务器，复制日志项
- Follower返回复制结果给Leader
- 当Leader认为这个日志项已经被多数节点复制，那么在提交此日志项并将这条日志项应用到状态机后，会返回给客户端
可以看到日志的提交过程有点类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。
示意图如下：
例子-复制
- 首先，我在S2节点发起request(只能对leader发起request)。这时候Leader会把这条指令附加到本地的日志中，但并未提交(虚线框)
- 然后，S2向其他节点发送者条日志，其他节点收到之后，都把这条日志加到本中，但是没有提交(虚线框)
- Follower把成功复制的结果返回给Leader，Leader收到了4票，认为这个日志项已经被多数节点复制
- Leader把这项日志应用到状态机(变成实线框)，并将结果返回给客户端。
- Leader给Folloer发信息，意思是说我已经提交成功并应用了，你们也可以提交了，因此Folloer也相继提交并应用了
日志复制的保证
- 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的
- 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前所有条目都是完全一样的。
- 在复制日志项的时候，会携带上一个日志项的index和term序号，如果不匹配，会一直查找，直到匹配了才把日志复制过来
可能出现不一致的场景
我们举几个例子，下图 a-f是follower可能出现的场景(不是说有6个follower)
日志项缺失
a在收到(6,9)之后宕机 , 示意图如下图所示(不是完全匹配)
b在收到(4,4)之后宕机，后面几个term一直没有恢复
日志项多余
c作为follower收到了来自leader的(6,11)日志之后，Leader宕机，而此时其他节点可能还没收到
d可能本来就是Leader，接收了来自客户端的两次请求之后，还没把信息传递出去，就宕机了，再次选举得到的新Leader已经不是它了，因此不会有Term7的信息
示意图如下:
日志项不匹配
- e收到(4,6)(4,7)之后宕机，示意图如下所示：
- F多收到任期2,3的日志项，但是都没有提交成功。这时候f宕机，系统选取了新的leader，开启term4。由于之前term2、3没有提交成功，导致该term的日志没有写入多数节点，导致term4的leader没有term2、3的日志项
那么如果出现了不一致的情况，此时Leader首先会进行要如何解决？首先要知道的一个原则：Leader不会覆盖或者删除自己的日志
- 日志项缺失
- Leader会从最新的日志开始发起，因为每条日志都会保留上一条日志的index和term序号，因此可以和上一条做比较。如果Folloer没有找到对应的日志项，就会拒绝。
- Leader发现拒绝接受的消息，就会向前逐个排查，直到Follower最终找到与Leader对应的相同位置，
- 然后，Leader把条该日志之后的所有日志全部发送给follow，让其同步，覆盖掉不匹配的日志项
- 日志项多余
- Leader发现follower的日志项比自己多，会发送信息给follower让他同步我自己的日志项。这是一个强制性的同步，既然选择了leader，就一定要让folloer和leader一致
- 日志项不匹配的操作逻辑和日志项缺失一样
可能有人说一个一个找会比较麻烦，那么可以进行一些优化，比如三个三个找，或者按照任期向前搜索
最终的结果是日志必须按照顺序记录的如下图：
Safety
在上面提到只要日志被复制到majority节点，就能保证不会被回滚，即使在各种异常情况下，这根leader election提到的选举约束有关。在这一部分，主要讨论raft协议在各种各样的异常情况下如何工作的。
衡量一个分布式算法，有许多属性，如
- safety：nothing bad happens,
- liveness： something good eventually happens.
任何系统模型下，都需要满足safety属性，即在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。比如，raft保证被复制到大多数节点的日志不会被回滚，那么就是safety属性。而raft最终会让所有节点状态一致，这属于liveness属性。
raft协议 会保证以下属性
| 性质 | 描述 | 问题 | 解决 |
|---|---|---|---|
| 选举安全原则(Election Safty) | 一个任期内最多允许一个Leader | Split Vote | 随机选举时间，多次选举 |
| Leader只追加原则(Leader Apeend-Only) | Leader永远不会覆盖或者删除自己的日志，它只会增加日志项 | 日志不一致 | 强制Follower与其一致 |
| 日志匹配原则(Log Match) | 如果两个日志在相同的索引位置上的日志项的任期号相同，那么就认为这个日志项索引位置之前的日志也完全相同 | 日志不一致 | 日志复制，一致性检验 |
| Leader完全原则(Leader Completeness) | 如果一个日志项在一个给定任期内被提交，那么这个日志项一定会出现在所有任期号更大的Leader中 | 无法判断某个entry是否被提交 | 选举限制+推迟提交 |
| 状态机安全原则(State Machine Safety) | 如果一个节点已经将给定索引位置的日志项应用到状态机中，则所有其他节点不会再该索引位置应用不同的日志项 | 反证法 | 反证法 |
前三点我在Leader election和日志复制的保证 章节都已经谈到了,因此着重来说说后面：
leader completeness vs elcetion restriction
Leader完全原则是说：如果一个日志项在一个给定任期内被提交，那么这个日志项一定会出现在所有任期号更大的Leader中 。
要满足这个原则，就要在选举的时候加入一些判断——如何保证日志项一定会出现在任期更大的Leader当中呢？
选举时判断最新的日志项
如上面这个情况：
- S3、S4处于宕机状态，不去考虑
- S1、S2、S5 由于没有Leader，因此投票选举，此时S1正处于Candidate状态。
- 但是，我们看到S2和S5并没有投票给S1，这是因为S2、S5比S1多了一个Term6日志项 。因为对于S2、S5来说，Term6的日志并没有在本地提交，但是它并不知道Term6的Leader是否已经提交了这个日志。因为从复制过程我们也可以看出，Leader提交日志的时候，实际上Follower是还没有提交的。S2、S5看到S1的日志项并不是最新的，因此会拒绝投票
破解这个问题，就会使用到随机选举时间，下次可能是S2、S5发起选举，从而避免选举失败的问题
可能触发安全性隐患的问题
宕机异常
- Leader 宕机： 其余节点超时后重新选举，选出新的Leader。当此节点重新进入集群之后，接收心跳信息
- Candidate/Follower 宕机：集群没有出现故障问题，重启后恢复为Follower节点加入集群
网络分区
问题：某一节点再次加入集群之后，增大的任期会打断当前系统的执行
解决方法：Pre-Vote方案就像是一次Leader选举，不过不改变节点状态。如果能够获取多数选票，则可以发起新一轮选举。如下图所示：
- 当前集群中，可能网络突然出现了问题，五个节点变分为了两组：AB可以互相通信、CDE可以相互通信，但是他们之间没有办法相互通信
- 因此，对A、B来说，A本来就是Leader，状态不会发生改变，B会收到来自Leader的信号，也不会发起选举；C D E收不到来自Leader的信息，因此发起选举，选出了他们的Leader C
- 对于C来说，它可以达到多数派要求(多余一半的节点会投票给它)，它会为C、D、E这组节点提供服务。但是对于旧的Leader A,它不能得到多数票，因为联系不到其他节点，而且也不知道当前实际上有一个新的Leader可以提供服务。
在这种情况下，如果网络被修复之后，旧的Leader A 会接收到来自Leader C发送的消息，从中发现对方的Term 比自己的更大，因此从Leader转换为Follower
还有一种网络分区导致的情况：
- 网络突然出现了问题，C、D被隔开，A虽然找不到CD，但是仍能获得多数选票，为A、B、E提供服务
- C、D由于没办法取得Leader心跳，因此转变为Candidate发送选举请求，但是都无法获得多数选票，因此始终在选举当中，term号一直在增加
因此当网络分区消失之后，C、D重新加入集群，此时A就会发现：自己Term号要远远小于C的Term号，按照道理自己必须变成Follower，把Leader位置禅让给C。但是C又没有A、B、E在网络分区时间段记录下的日志。此时C、D的加入就会打断当前系统的执行。
由于C和D的日志项是落后于A、B、E的，所以它发送的消息，别人都是不认可的，因此最终A、B、E中的某个节点会发起选举，抢夺C的Leader。
为了解决这个问题，有 Pre-Vote 的解决方案。对于C和D节点来说，在网络分区结束之后加入集群，会进行一轮预投票，这个阶段与Leader选举类似，但是不会改变节点的状态。如果在这轮预投票中可以获得多数票，那么就可以增加任期，发起新一轮选举。而显然，C和D并不会在这轮选举中获取大多数票
线性一致性
- 定义：数据像只有一个副本一样，在各节点上写生效顺序相同，写写全局的先后一致，能读到最新的写
而Raft并不等于线性一致，但可以基于Raft实现线性一致性。但这是较弱的一致性，在上面我们也说到了，在网络分区的时候，有可能读取到旧的数据
我们看到，从用户看到的情况看：
S1节点先写入W(x=1); S2节点再写入W(x=2), 但是读取的时候，先读取得到R(x=2),再读取R(x=1)。可能认为出现了线性不一致。
其实这是被允许的，只要能在时间轴上，每一个事务(读、写)都能抽象成一个点，就可以满足若线性一致性了
强一致性
实现强一致性的三种读方法
Read Log
这种方式，读写都会经过Leader，通过日志应用到复制状态机以获得正确的结果
- 优点： 读写操作采用相同 的处理方法，容易实现线性一致性
- 缺点：读操作不改变状态机的状态，但还要写日志，开销大
Read Index
读操作不经过复制状态机，通过索引判断当前最新日志项写入位置。为了防止从旧Leader获取信息，因此需要一轮心跳来确认当前的Leader。
当Leader接收到读请求的时候，需要通过一轮心跳来确保当前自己仍然是Leader，并记录当前的Commit index为Read index，然后等到apply >= read index 再提供读服务
如果客户端是从Follower处读取x的值，那么Follower会去Leader问询，Leader会执行上述操作并返回值。相比直接询问Leader多了一次访问开销
优点： 省掉了同步日志的开销，能够大幅提升读的吞吐量，并且在一定程度上降低了读的时延
例子
CDE一开始出现了网络分区，因此独立出来，选择了C作为Leader。然后，有一个客户端在新Leader这边发起了 W(x=1)的请求，由于得到大多数节点支持，该操作可以顺利通过。
此时，如果有客户端向老的Leader A发送读取请求——如果有了Read Index机制，Leader A会发送一轮消息，来确认自己是否仍然是Leader，现实是他并不是，因此客户端无法从A节点读取x的值。
Lease Read
前提：已经确定了当前的Leader就是全局唯一的Leader, 要实现这个方法可以规定一段时间内，保证各节点不会发生选举
那么，当Leader接收到读请求的时候，由于可以保证Leader是唯一Leader， apply >= read index ，可以直接提供读服务。
- 优点： 与Read Index相比，Lease Read 进一步省去了网络交互开销，因此更能显著降低读的时延
- 缺点：由于使用的是每个服务器各自的时钟，存在着时钟飘逸现象(比如，A节点1秒等于B节点2秒)，那么如果误差过大可能线性化的保证就丢失了