Raft共识算法

为了想点好玩的毕设，重温了raft，以及看了个视频

复制状态机

replicated state mechine

相同的初始状态+相同的输入=相同的结束状态

leader将command通过封装到log entry中，将这些log entries复制到所有的follower节点，然后按照相同的顺序应用其中的command,得到相同的结束状态。

使用共识算法，就是为了实现复制状态机，各节点间通过共识算法来保证命令序列的一致，从而保持状态的一致。

状态简化

状态：leader,follower,candidate

相比起paxos,raft只需要关系状态的转换，而不是考虑状态的共存和相互影响

时间被分割为任意长度的任期（term），任期用连续的整数标记

领导者选举

心跳机制

如果存在leader,它会向所有follower周期性的发送心跳，如果follower在一段时间内没有收到心跳，它会认为系统中没有可用的leader，然后开始选举。

领导人周期性的向所有跟随者发送心跳包（即不包含日志项内容的附加条目（AppendEntries） RPCs）来维持自己的权威
选举机制

开始一个选举后，follower先增加自己的任期号，然后切换到candidate状态，然后投票给自己，并并行地对其他节点发送投票请求（RequestVote RPC）

选举会有三种结果
1. 获得了超过半数（N/2+1）的票数，成为leader并开始发送heartbeat
2. 其他节点赢得选举：收到一个leader的心跳，如果新leader的任期号不小于自己当前的任期号，就从candidate回到follower状态
  
  由于leader先收到了超过半数的选票，可以某种程度上证明它是「更优」的节点。
  
  在等待投票的时候，候选人可能会从其他的服务器接收到声明它是领导人的附加条目（AppendEntries）RPC。如果这个领导人的任期号（包含在此次的 RPC中）不小于候选人当前的任期号，那么候选人会承认领导人合法并回到跟随者状态。如果此次 RPC 中的任期号比自己小，那么候选人就会拒绝这次的 RPC 并且继续保持候选人状态。
3. 没有获胜者：每个candidate在自己的随机选举超时时间后增加任期号并开始新的一轮投票
  
  为什么没有获胜者？：比如多个follower同时成为candidate，得票过于分散，没有任何一个candidate得票超过半数
  
  一个服务器最多会对一个任期号投出一张选票，按照先来先服务的原则
  
  随机选举超时时间：150~300ms （这个时间对于oltp系统来说还是比较长的）
  
  随机选举超时时间的方法来确保很少会发生选票瓜分的情况，就算发生也能很快的解决。为了阻止选票起初就被瓜分，选举超时时间是从一个固定的区间（例如 150-300 毫秒）随机选择。这样可以把服务器都分散开以至于在大多数情况下只有一个服务器会选举超时；然后他赢得选举并在其他服务器超时之前发送心跳包。同样的机制被用在选票瓜分的情况下。每一个候选人在开始一次选举的时候会重置一个随机的选举超时时间，然后在超时时间内等待投票的结果；这样减少了在新的选举中另外的选票瓜分的可能性

请求投票（RequestVote）RPC：

Request (arguments)

term // 候选人的任期号
candidateId // 请求选票的候选人的 ID
lastLogIndex // 候选人的最后日志条目的索引值
lastLogTerm  // 候选人最后日志条目的任期号

Response (results)

1 2	term // 当前任期号，以便于候选人去更新自己的任期号 voteGranted // 候选人赢得了此张选票时为真

日志复制

leader被选举后，为客户端提供服务

client如何找到leader的节点：

节点是leader：直接提供服务
节点不是leader：节点通过心跳得到leader的id
节点无相应：去找另一个节点

leader接收到client的指令后，将指令作为一个新的日志条目，附加到日志中

一条日志需要具有三个信息：

状态机指令：y<-1
任期，leader的term：可以用于检测日志副本的不一致情况，判定节点状态。
日志号log index（日志索引）：递增

日志号和任期号才能唯一确定一条日志。

leader并行发送AppendEntries RPC给follower，follower复制该日志条目，当条目被半数以上的follower复制后，leader就可以在本地执行该指令并把结果给client

本地指令指令，也就是leader应用日志和状态机，称作提交（图中可以提交的日志是7）

为了保证所有节点的日志都是完整且顺序一致的：

follower缓慢：leader重复尝试重发

如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导人会不断的重复尝试附加日志条目 RPCs （哪怕已经回复了client）直到所有的跟随者都最终存储了所有的日志条目
follower宕机：follower崩溃后恢复，raft的追加条目一致性检查生效，保证follower能按照顺序恢复崩溃后的缺失的日志

一致性检查：leader会在追加条目rpc中放入前一个日志条目的索引和任期号，如果follower在它的日志中找不到前一个日志，那它就会拒绝该日志，leader受到拒绝后，会发送前一个日志条目，直到发送了follower缺失的第一个条目。

如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致
leader宕机：崩溃的leader可能存在已经复制到了部分follower但是未提交的日志，而新选举出来的leader并不存在这些日志。

leader会强制follower复制它的日志来解决不一致的问题，这意味着follower中与leader冲突的日志会新leader的条目被覆盖，因为没有提交，所以不影响外部的一致性。

AppendEntries RPC:

Request (arguments)

term // 候选人的任期号
leaderId // 领导人 ID 因此跟随者可以对客户端进行重定向（译者注：跟随者根据领导人 ID 把客户端的请求重定向到领导人，比如有时客户端把请求发给了跟随者而不是领导人）
prevLogIndex // 紧邻新日志条目之前的那个日志条目的索引
prevLogTerm // 紧邻新日志条目之前的那个日志条目的任期
entries[] // 需要被保存的日志条目（被当做心跳使用时，则日志条目内容为空；为了提高效率可能一次性发送多个）
leaderCommit // 领导人的已知已提交的最高的日志条目的索引

Response (results)

1 2	term // 当前任期号，以便于候选人去更新自己的任期号 success // 如果跟随者所含有的条目和 prevLogIndex 以及 prevLogTerm 匹配上了，则为 true

对于follower宕机时的优化：

安全性

选举限制

如果一个follower落后了leader的若干日志，它依旧可能当选leader,在当选后就不会补上缺失的日志部分，因此需要限制保证leader一定包含了之前各任期所有的被提交的日志条目

在RequestVote RPC中，如果投票者自己的日志比candidate的还新，那他就会拒绝该投票请求
1. 如果日志任期号不同，任期号大的更新
2. 如果任期号相同，日志号大的更新
提交：在AppendEntries中，follower可以通过leaderCommit确定自己应该提交到哪个日志

事实上，在leader提交后，并返回客户端success后，但follower还没提交时，也就是leaderCommit还没给大多数的follower，在这一个心跳内的时间内，leader挂了，这个时候就会出现不一致的情况。

应用可以设置一个集群提交的概念，在集群中超过半数的节点提交后，才认为集群提交完成（复杂的场景在precolator事务模型）

leader可以通过AppendEntries RPC中的success判断这个follower是否完成了提交

新leader是具有老leader的日志的，老日志在新leader中可能还没有提交，新leader会将这个日志复制给所有的follower,但它不会提交这个日志，上图中，日志二会被复制到集群的大多数节点，但它作为一个之前任期内的日志不应该被提交。

图 8：如图的时间序列展示了为什么领导人无法决定对老任期号的日志条目进行提交。在 (a) 中，S1 是领导人，部分的(跟随者)复制了索引位置 2 的日志条目。在 (b) 中，S1 崩溃了，然后 S5 在任期 3 里通过 S3、S4 和自己的选票赢得选举，然后从客户端接收了一条不一样的日志条目放在了索引 2 处。然后到 (c)，S5 又崩溃了；S1 重新启动，选举成功，开始复制日志。在这时，来自任期 2 的那条日志已经被复制到了集群中的大多数机器上，但是还没有被提交。如果 S1 在 (d) 中又崩溃了，S5 可以重新被选举成功（通过来自 S2，S3 和 S4 的选票），然后覆盖了他们在索引 2 处的日志。反之，如果在崩溃之前，S1 把自己主导的新任期里产生的日志条目复制到了大多数机器上，就如 (e) 中那样，那么在后面任期里面这些新的日志条目就会被提交（因为 S5 就不可能选举成功）。这样在同一时刻就同时保证了，之前的所有老的日志条目就会被提交。

为了避免这种情况，Raft 永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目

时间与可用性

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

在这个不等式中，广播时间指的是从一个服务器并行的发送 RPCs 给集群中的其他服务器并接收响应的平均时间；选举超时时间就是在 5.2 节中介绍的选举的超时时间限制；然后平均故障间隔时间就是对于一台服务器而言，两次故障之间的平均时间。广播时间必须比选举超时时间小一个量级，这样领导人才能够发送稳定的心跳消息来阻止跟随者开始进入选举状态；通过随机化选举超时时间的方法，这个不等式也使得选票瓜分的情况变得不可能。选举超时时间应该要比平均故障间隔时间小上几个数量级，这样整个系统才能稳定的运行。当领导人崩溃后，整个系统会大约相当于选举超时的时间里不可用；我们希望这种情况在整个系统的运行中很少出现。

集群成员变化

为了让配置修改机制能够安全，那么在转换的过程中不能够存在任何时间点使得两个领导人在同一个任期里同时被选举成功

任何服务器直接从旧的配置直接转换到新的配置的方案都是不安全的。一次性原子地转换所有服务器是不可能的。

为了让配置修改机制能够安全，那么在转换的过程中不能够存在任何时间点使得两个领导人在同一个任期里同时被选举成功。：脑裂问题

配置采用两阶段的方法，先切换到一个过度的配置，称为联合一致（joint consensus）

第一阶段，leader发起$C_{old,new}$。这时leader崩溃，集群依旧可以按照老配置来选出新leader，新rpc在旧配置中都达到大多数就可以生效

当达到大多数后，leader提交$C_{old,new}$，集群进入联合一致，这时，新rpc在新旧两个配置中都达到大多数才可以生效

第二阶段，leader发起$C_{new}$，使集群进入新配置状态。这时，新rpc在新配置中都达到大多数就可以生效。

假设leader在发起$C_{new}$时崩溃，已经复制了$C_{new}$的节点会按照$C_{new}$进行选举，而没有复制$C_{new}$的节点会按照$C_{old}$或者$C_{old,new}$进行选举，这依旧能保证选举得到的leader至少是复制了$C_{old,new}$的节点，如果是$C_{old,new}$的节点，由于$C_{old,new}$已经提交，它依旧会发起$C_{new}$，使得节点最终达到$C_{new}$的配置

当缩减节点时，leader崩溃，由于复制了$C_{old,new}$没有复制$C_{new}$的节点必须要在两个配置中都达到大多数才能生效（选举和提交），因此选举得到的leader一定会是复制了$C_{new}$的节点。

联合一致可以让集群在配置转换的过程中依然响应客户端的请求，但是需要在两种配置中都达到大多数才能生效。

一旦一个服务器将新的配置日志条目增加到它的日志中，他就会用这个配置来做出未来所有的决定（服务器总是使用最新的配置，无论他是否已经被提交）。这意味着领导人要使用 C-old,new 的规则来决定日志条目 C-old,new 什么时候需要被提交。如果领导人崩溃了，被选出来的新领导人可能是使用 C-old 配置也可能是 C-old,new 配置，这取决于赢得选举的候选人是否已经接收到了 C-old,new 配置。在任何情况下， C-new 配置在这一时期都不会单方面的做出决定。

一旦 C-old,new 被提交，那么无论是 C-old 还是 C-new，如果不经过另一个配置的允许都不能单独做出决定，并且领导人完全特性保证了只有拥有 C-old,new 日志条目的服务器才有可能被选举为领导人。这个时候，领导人创建一条关于 C-new 配置的日志条目并复制给集群就是安全的了。再者，每个服务器在见到新的配置的时候就会立即生效。当新的配置在 C-new 的规则下被提交，旧的配置就变得无关紧要，同时不使用新的配置的服务器就可以被关闭了。如图 11，C-old 和 C-new 没有任何机会同时做出单方面的决定；这保证了安全性。

这种方案使得不会出现脑裂现象。

对于第一点，让未完成同步日志的节点不具有投票权，也不参与大多数的计数即可。如何判断

这种方法又称为多节点变更，实际上边界情况很多，实现起来非常复杂，现在多使用单节点变更

日志压缩

快照是最简单的压缩方法。在快照系统中，整个系统的状态都以快照的形式写入到稳定的持久化存储中，然后到那个时间点之前的日志全部丢弃。

增量压缩的方法，例如日志清理或者日志结构合并树，都是可行的。这些方法每次只对一小部分数据进行操作，这样就分散了压缩的负载压力。首先，他们先选择一个已经积累的大量已经被删除或者被覆盖对象的区域，然后重写那个区域还活跃的对象，之后释放那个区域。和简单操作整个数据集合的快照相比，需要增加复杂的机制来实现。状态机可以实现 LSM tree 使用和快照相同的接口，但是日志清除方法就需要修改 Raft 了。

扩展

no-op

在leader刚选举成功的时候，leader首先发送一个no-op log entry。从而保证之前term的log entry提交成功。并且通过no-op，新当选的leader可快速确认自己的CommitIndex，来保证系统迅速进入可读状态

(a):S1是Term2的leader，选为主后，将no-op LogEntry复制到S1和S2之后crash。
(b):S5被S3、S4和S5选为Term3的leader，并只写入一条no-op LogEntry到本地后crash。
(c):S1被S1、S2和S3选为Term4的leader。
后面有两种可能:
1. (c1):S1作为leader，继续做了以下几件事：
  1. 写一条no-op LogEntry
  2. 在写no-op的过程中间接提交Term2的no-op，对S5而言，会覆盖Term3的no-op日志。
  3. 提交新的日志4
  4. 最终整个系统达成状态(c2)，所有的节点对日志达成一致
2. (d2):S1写入一条no-op LogEntry之后就crash了。S5被S3、S4和S5选为Term5的leader。
  1. 写一条no-op LogEntry
  2. 在no-op提交的过程中间接提交Term3提交的no-op，对S1、S2和S3而言，会覆盖不一致的日志。
  3. 提交新的日志3
  4. 最终整个系统达成状态(d2)，所有节点对日志达成一致。

引入no-op之前，如博士论文所述，包含value信息的LogEntry有可能被覆盖掉。
引入no-op之后，如果当前leader已经开始提交含有value信息的LogEntry，那么它一定将之前的LogEntry全部提交了，就算它crash了：
- 系统也会选拥有最新最全日志的candidate为leader，比如上图，S5就不可能像之前一样成为leader
- 就算有日志覆盖，覆盖的也是no-op，或者没有复制到多数节点的LogEntry。不会是已经复制到多数节点的包含value的LogEntry。

单一节点变更（single-server change）

这种方法保证了一次只能选出新配置或者旧配置的leader,而不会有两个leader,避免了脑裂问题

实际上这样也会遇到问题，正如上面的安全性问题一样，在边界情况下导致一个节点的已提交的变更日志被覆盖，但使用no-op就可以解决：新 leader 必须提交一条自己的 term 的 no-op 日志, 才允许接着变更日志。

新节点日志同步

比如，在第一轮同步数据时，leader的最大数据索引为10，那么第一轮就同步10之前的数据。而在同步第一轮数据的同时，leader还能继续接收新的数据，假设当同步第一轮完毕时，最大数据索引变成了20，那么第二轮将继续同步从10到20的数据。以此类推。

这个同步的轮次并不能一直持续下去，一般会有一个限制的轮次数量，比如最多同步10轮。

之后再进行成员变更

一致性读

对于最后一点，由于安全性，leader无法提交之前任期的日志，只能提交自己任期内产生的日志，所以需要加入no-op来提交自己任期的日志。安全性只保证了选举出来的leader具有已提交的所有日志，但是leader可能具有未提交的日志，如果这个日志不属于自己的任期，leader不能去提交它，leader也不能确定哪些日志到底被提交了（比如3），当发送no-op并成功提交no-op后，此时3一定被提交了，leader便可以返回结果给client