- Raft一致性算法笔记: 基本概念介绍
在Raft中，问题分解为：领导选取、日志复制、安全和成员变化。
每台服务器一定会处于三种状态：
- 领导者
- 候选人
- 追随者
RPC有三种：
- RequestVote RPC：候选人在选举期间发起
- AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成
- InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者。
超时设置：
- BroadcastTime : 领导者的心跳超时时间
- Election Timeout: 追随者设置的候选超时时间
- MTBT :指的是单个服务器发生故障的间隔时间的平均数
BroadcastTime << ElectionTimeout << MTBF
两个原则：
- BroadcastTime应该比ElectionTimeout小一个数量级，为的是使领导人能够持续发送心跳信息（heartbeat）来阻止追随者们开始选举；
- ElectionTimeout也要比MTBF小几个数量级，为的是使得系统稳定运行。 一般BroadcastTime大约为0.5毫秒到20毫秒，ElectionTimeout一般在10ms到500ms之间。大多数服务器的MTBF都在几个月甚至更长。
触发条件：
- 一般情况下，追随者接到领导者的心跳时，把ElectionTimeout清零，不会触发；
- 领导者故障，追随者的ElectionTimeout超时发生时，会变成候选者，触发领导人选取；
候选操作过程：
追随者自增当前任期，转换为Candidate，对自己投票，并发起RequestVote RPC，等待下面三种情形发生；
- 获得超过半数服务器的投票，赢得选举，成为领导者；
- 另一台服务器赢得选举，并接收到对应的心跳，成为追随者；
- 选举超时，没有任何一台服务器赢得选举，自增当前任期，重新发起选举；
注意事项：
- 服务器在一个任期内，最多能给一个候选人投票，采用先到先服务原则；
- 候选者等待投票时，可能会接收到来自其它声明为领导人的的AppendEntries RPC。如果该领导人的任期（RPC中有）比当前候选人的当前任期要大，则候选人认为该领导人合法，并转换成追随者；如果RPC中的任期小于候选人的当前任期，则候选人拒绝此次RPC，继续保持候选人状态；
- 候选人既没有赢得选举也没有输掉选举：如果许多追随者在同一时刻都成为了候选人，选票会被分散，可能没有候选人能获得大多数的选票。当这种情形发生时，每一个候选人都会超时，并且通过自增任期号和发起另一轮 RequestVote RPC 来开始新的选举。然而，如果没有其它手段来分配选票的话，这种情形可能会无限的重复下去。所以Raft使用的随机的选举超时时间（150~300ms之间），来避免这种情况发生。
接受命令的过程：
- 领导者接受客户端请求；
- 领导者把指令追加到日志；
- 发送AppendEntries RPC到追随者；
- 领导者收到大多数追随者的确认后，领导者Commit该日志，把日志在状态机中回放，并返回结果给客户端；
提交过程：
- 在下一个心跳阶段，领导者再次发送AppendEntries RPC给追随者，日志已经commited；
- 追随者收到Commited日志后，将日志在状态机中回放。
-
领导者追加日志（Append-Only)
-
选举限制：投票阻止没有全部日志条目的服务器赢得选举
-
永远不提交任期之前的日志条目（只提交任期内的日志条目）
-
候选者和追随者崩溃
如果允许提交任期之前的日志条目，那么在步骤c中，我们就会把之前任期为2的日志提交到其他服务器中去，并造成了大多数机器存在了日志为2的情况。所以造成了d中S5中任期为3的日志条目会覆盖掉已经提交的日志的情况。
Raft 从来不会通过计算复制的数目来提交之前任期的日志条目。只有领导人当前任期的日志条目才能通过计算数目来进行提交。一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配原则（Log Matching Property），之前的日志条目也都会被间接的提交。
论文中的这段话比较难理解，更加直观的说：由于Raft不会提交任期之前的日志条目，那么就不会从b过渡到c的情况，只能从b发生S5down机的情况下直接过渡到e，这样就产生的更新的任期，这样S5就没有机会被选为领导者了。
讲述了应该避免c状态的出现。（只有领导人当前任期的日志条目才能通过计算数目来进行提交）
任期4的时间，不会把旧的任期2的数据同步后计算过半条数来表示提交，而是一定会等到大家的过半节点都变成任期4的最新才会提交。
集群成员的变更和成员的宕机与重启不同，因为前者会修改成员个数进而影响到领导者的选取和决议过程，因为在分布式系统这对于majority这个集群中成员大多数的概念是极为重要的。
简单的做法是，运维人员将系统临时下线，修改配置，重新上线。但是这种做法存在两个缺点：
- 更改时集群不可用
- 人为操作失误风险
因为各个机器可能在任何的时候进行转换。在这个例子中，集群配额从 3 台机器变成了 5 台。不幸的是，存在这样的一个时间点，两个不同的领导人在同一个任期里都可以被选举成功。一个是通过旧的配置，一个通过新的配置。
为了保证安全性，配置更改必须使用两阶段方法。在 Raft 中，集群先切换到一个过渡的配置，我们称之为共同一致；一旦共同一致已经被提交了，那么系统就切换到新的配置上。共同一致是老配置和新配置的结合。
共同一致允许独立的服务器在不影响安全性的前提下，在不同的时间进行配置转换过程。此外，共同一致可以让集群在配置转换的过程人依然响应服务器请求。
一个领导人接收到一个改变配置从 C-old 到 C-new 的请求，他会为了共同一致存储配置（图中的 C-old,new），以前面描述的日志条目和副本的形式。一旦一个服务器将新的配置日志条目增加到它的日志中，他就会用这个配置来做出未来所有的决定。领导人完全特性保证了只有拥有 C-old,new 日志条目的服务器才有可能被选举为领导人。当C-old,new日志条目被提交以后，领导人在使用相同的策略提交C-new，如下图所示，C-old 和 C-new 没有任何机会同时做出单方面的决定，这就保证了安全性。
一个配置切换的时间线。虚线表示已经被创建但是还没有被提交的条目，实线表示最后被提交的日志条目。领导人首先创建了 C-old,new 的配置条目在自己的日志中，并提交到 C-old,new 中（C-old,new 的大多数和 C-new 的大多数）。然后他创建 C-new 条目并提交到 C-new 中的大多数。这样就不存在 C-new 和 C-old 可以同时做出决定的时间点。
日志会随着系统的不断运行会无限制的增长，这会给存储带来压力，几乎所有的分布式系统(Chubby、ZooKeeper)都采用快照的方式进行日志压缩，做完快照之后快照会在稳定持久存储中保存，而快照之前的日志和快照就可以丢弃掉。
与Raft其它操作Leader-Based不同，snapshot是由各个节点独立生成的。除了日志压缩这一个作用之外，snapshot还可以用于同步状态：slow-follower以及new-server，Raft使用InstallSnapshot RPC完成该过程，不再赘述。
- Raft算法原理: 比较详细
有一个nextIndex、matchIndex的讲解，日志同步是置0进行重新同步的？性能问题？
跟这篇文章 描述不一样。
Leader通过强制Followers复制它的日志来处理日志的不一致，Followers上的不一致的日志会被Leader的日志覆盖。
Leader为了使Followers的日志同自己的一致，Leader需要找到Followers同它的日志一致的地方，然后覆盖Followers在该位置之后的条目。
Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。
随机选举超时时间对比图表Paxos
以下引自： https://zhuanlan.zhihu.com/p/32052223
Raft日志同步保证如下两点：
- 如果不同日志中的两个条目有着相同的索引和任期号，则它们所存储的命令是相同的。
- 如果不同日志中的两个条目有着相同的索引和任期号，则它们之前的所有条目都是完全一样的。
Leader会从后往前试，每次AppendEntries失败后尝试前一个日志条目，直到成功找到每个Follower的日志一致位点，然后向后逐条覆盖Followers在该位置之后的条目。
Raft增加了如下两条限制以保证安全性：
-
拥有最新的已提交的log entry的Follower才有资格成为Leader。
这个保证是在RequestVote RPC中做的，Candidate在发送RequestVote RPC时，要带上自己的最后一条日志的term和log index，其他节点收到消息时，如果发现自己的日志比请求中携带的更新，则拒绝投票。日志比较的原则是，如果本地的最后一条log entry的term更大，则term大的更新，如果term一样大，则log index更大的更新。
-
Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志，旧term日志的提交要等到提交当前term的日志来间接提交（log index 小于 commit index的日志被间接提交）。
- Raft算法原理: 比较详细
任期号在raft算法中更像一个“逻辑时钟（logic clock）”的作用
如果一个节点的当前任期号小于其他节点的当前任期号，将更新其当前任期号到最新的任期号。如果一个candidate或者leader状态的节点发现自己的当前任期号已经小于其他节点了，那么将切换到follower状态。反之，如果一个节点收到的消息中带上的发送者的任期号已经过期，将拒绝这个请求。
RequestVote RPC用于candidate状态的节点进行选举之用，而AppendEntries RPC由leader节点向其他节点复制日志数据以及同步心跳数据的。
leader节点通过周期性的发送心跳请求（一般使用带有空数据的AppendEntries RPC来进行心跳）来维持着leader节点状态。每个follower同时还有一个选举超时（election timeout）定时器，如果在这个定时器超时之前都没有收到来自leader的心跳请求，那么follower将认为当前集群中没有leader了，将发起一次新的选举。
发起选举时，follower将递增它的任期号然后切换到candidate状态。然后通过向集群中其它节点发送RequestVote RPC请求来发起一次新的选举。一个节点将保持在该任期内的candidate状态下，直到以下情况之一发生。
- 该candidate节点赢得选举，即收到超过半数以上集群中其它节点的投票。
- 另一个节点成为了leader。
- 选举超时到来时没有任何一个节点成为leader。
详细流程看链接
当leader节点收到集群半数以上节点的AppendEntries请求的应答消息时，认为SET a=1命令成功复制，可以进行提交，于是修改了本地committed日志的索引指向最新的存储SET a=1的日志，而appliedIndex还是保持着上一次的值，因为还没有应用该命令到状态机中。
提交命令完成，给应用层说明这条命令已经提交。此时修改appliedIndex与committedIndex一样了。
leader节点在下一次给follower的AppendEntries请求中，会带上当前最新的committedIndex索引值，follower收到之后同样会修改本地日志的committedIndex索引。
- 如果两个日志条目有相同的索引号和任期号，那么这两条日志存储的是同一个指令。
- 如果在两个不同的日志数据中，包含有相同索引和任期号的日志条目，那么在这两个不同的日志中，位于这条日志之前的日志数据是相同的。
链接有详细的各种情况的日志对比和处理情况，但matchIndex有些问题？
-
这个进行选举的节点的日志，比本节点的日志更新
这通过对比日志的最后一个日志条目数据来决定，首先将对比条目的任期号，任期号更大的日志数据更新；如果任期号相同，那么索引号更大的数据更新。
-
对于当前任期之前任期提交的日志，并不通过判断是否已经在半数以上集群节点写入成功来作为能否提交的依据。只有当前leader任期内的日志是通过比较写入数量是否超过半数来决定是否可以提交的。
对于任期之前的日志，Raft采用的方式，是只要提交成功了当前任期的日志，那么在日志之前的日志就认为提交成功了。这也是为什么etcd-Raft代码中，在成为leader之后，需要再提交一条dummy的日志的原因–只要该日志提交成功，leader上该日志之前的日志就可以提交成功。
如果给候选节点投票了，要记录下被投票的候选节点ID。如果节点在选举期间给了一个候选人投票后突然宕机重启了，如果没有记下这个值，就很可能会重复投票，又给另一个节点投票去了。这就会导致集群存在多个Leader，也就是集群分裂。
Leader当选后进行第一次日志复制时，会和Follower进行若干次日志的匹配过程，最终可以得到Leader和各自Follower的日志匹配的matchIndex值。处于majority节点列表的matchIndex的最小值就是当前Leader的commitIndex。
3 日志同步需要携带Leader的日志提交索引值，如果这个值比本地日志的提交索引值要大，那就将本地的这个值往前进。提交索引值之前的所有日志就可以安全的apply到状态机了。
5 如果Follower本地日子的prevLogIndex位置处没有日志或者对应的term不匹配，那就拒绝同步。同时将日志在不匹配的位置处进行截断，后面的所有日志统统剁掉。
6 Leader收到了Follower的拒绝时，如果响应的任期号比Leader本身还大，那么Leader理解退职变身Follower。如果响应的任期号不超过Leader，Leader就将同步的日志列表往前挪一个位置，再重试同步请求。
7 Follower如果在prevLogIndex处日志的term和请求消息中的prevLogTerm匹配，那么就将消息中的日志追加到自身的日志序列上，这个时候就可以向Leader响应成功了。
8 Leader收到成功响应后，更新内部记录节点的matchIndex值，然后再前进全局的commitIndex值，并将最近刚刚成功提交的日志应用到状态机中。
9 Leader一旦当选，立即向其它节点同步一个心跳消息(no-op)。这是为了确保当前没有提交的日志也能尽快得到提交。Leader只会追加日志序列，刚当选时已经存在的日志序列，Leader会努力将它们同步到所有节点，如果Follower存在的日志和Leader有冲突，就会被抹平。最终Leader和Follower的日志就会完全一致。
13 如果Follower失败响应，那么递减nextIndex值重新同步。这是Leader采用后退重试法进行日志同步的细节。
14 如果存在majority的matchIndex前进了，Leader的本地日志序列的commitIndex和applyIndex也要跟着前进。
为了解决这一问题，Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置，称为共同一致（joint consensus），共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew，一旦共同一致Cold U Cnew被提交，系统再切换到新成员配置Cnew。
详细过程看链接
两阶段成员变更，之所以分为两个阶段，是因为对Cold与Cnew的关系没有做任何假设，为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader，才引入了两阶段方案。
如果增强成员变更的限制，假设Cold与Cnew任意的多数派交集不为空，这两个成员配置就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。
那么如何限制Cold与Cnew，使之任意的多数派交集不为空呢？方法就是每次成员变更只允许增加或删除一个成员。
一阶段成员变更：
- 成员变更限制每次只能增加或删除一个成员（如果要变更多个成员，连续变更多次）。
- 成员变更由Leader发起，Cnew得到多数派确认后，返回客户端成员变更成功。
- 一次成员变更成功前不允许开始下一次成员变更，因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。
- Leader只要开始同步新成员配置，即可开始使用新的成员配置进行日志同步
分布式系统的一个非常头疼的问题就是同样的动作发生的时间却不一样。比如上图的集群从3个变成5个，集群的配置从OldConfig变成NewConfig，这些节点配置转变的时间并不完全一样，存在一定的偏差，于是就形成了新旧配置的叠加态。
在图中红色剪头的时间点，旧配置的集群下Server[1,2]可以选举Server1为Leader，Server3不同意没关系，过半就行。而同样的时间，新配置的集群下Server[3,4,5]则可以选举出Server5为另外一个Leader。这时候就存在多Leader并存问题。
如图所示，蓝色圈圈代表旧配置的大多数(majority)，红色圈圈代码新配置的带多数。新旧配置下两个集群的大多数必然会重叠(旧配置节点数2k的大多数是k+1，新配置节点数2k+1的大多数是k+1，两个集群的大多数之和是2k+2大于集群的节点数2k+1)。这两个集群的term肯定不一样，而同一个节点不可能有两个term。所以这个重叠的节点只会属于一个大多数，最终也就只会存在一个集群，也就只有一个Leader。
A B C D E 5个节点，假如当前B是Leader，其他的节点是Follower。现在A B 两个节点、C D E三个节点割裂成2个网络。
假设客户端连接的是A B网络，那么客户端在写入的时候，由于大多数节点无法进行commit所以会导致写入失败。
假设客户端连接的是C D E网络（此时C D E已经选举出新的Leader），那么客户端在写入的时候，由于存在3个节点，能够写入成功。
此时相当于A B网络的节点一直保持着原有的状态，没有任何写入。相当于一直等待着被连进网络。
当两个网络又重新被打通的时候，由于C D E的任期序号要高于 A B网络，所以 A B 节点中的数据会进行回滚，同时从Leader中重新拉取数据，此时，集群节点的状态重新达到一致。
- Raft一致性算法笔记: 基本概念介绍
- Raft算法原理: 比较详细
- Raft协议精解
- Raft算法详解
- 别再怀疑自己的智商了，Raft协议本来就不好理解
- RAFT算法详解: 有比较详细的面试题