Raft算法(raft算法选举流程)
raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。在这里强调了是在工程上，因为在学术理论界，最耀眼的还是大名鼎鼎的Paxos。但Paxos是：少数真正理解的人觉得简单，尚未理解的人觉得很难，大多数人都是一知半解。
raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication）。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。
Raft 算法概览
Raft算法的头号目标就是容易理解（UnderStandable）。当然，Raft增强了可理解性，在性能、可靠性、可用性方面是不输于Paxos的。
为了达到易于理解的目标，raft做了很多努力，其中最主要是两件事情：
问题分解
状态简化
raft会先选举出leader，leader完全负责replicated log的管理。leader负责接受所有客户端更新请求，然后复制到follower节点，并在“安全”的时候执行这些请求。如果leader故障，followes会重新选举出新的leader。
这就涉及到raft最新的两个子问题： leader election和log replication
leader election
raft协议中，一个节点任一时刻处于以下三个状态之一：
leader
follower
candidate
下图可以很直观的看到这三个状态的区别
所有节点在启动的时候都是follower状态；在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举；如果收到majority的造成票（含自己的一票）则切换到leader状态；如果发现其他节点比自己更新，则主动切换到follower。
总之，系统中最多只有一个leader，如果在一段时间里发现没有leader，则大家通过选举-投票选出leader。leader会不停的给follower发心跳消息，表明自己的存活状态。如果leader故障，那么follower会转换成candidate，重新选出leader。
term 任期
我们知道leader是大家投票选举出来的，每个leader工作一段时间，然后选出新的leader继续负责。每一届新的履职期称之为一届任期，在raft协议中，也是这样的，对应的术语叫term。
term（任期）以选举（election）开始，然后就是一段或长或短的稳定工作期（normal Operation）。从上图可以看到，任期是递增的，这就充当了逻辑时钟的作用；另外，term 3展示了一种情况，就是说没有选举出leader就结束了，然后会发起新的选举。
选举过程
我们知道如果follower在 election timeout 内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。步骤如下：
增加节点本地的 current term ，切换到candidate状态
投自己一票
并行给其他节点发送 RequestVote RPCs
等待其他节点的回复
在这个过程中，根据来自其他节点的消息，可能出现三种结果
收到majority的投票（含自己的一票），则赢得选举，成为leader
被告知别人已当选，那么自行切换到follower
一段时间内没有收到majority投票，则保持candidate状态，重新发出选举
第一种情况，赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举。在这里，先回到投票者的视角，投票者如何决定是否给一个选举请求投票呢，有以下约束：
在任一任期内，单个节点最多只能投一票
候选人知道的信息不能比自己的少
first-come-first-served 先来先得
第二种情况，比如有三个节点A B C。A B同时发起选举，而A的选举消息先到达C，C给A投了一票，当B的消息到达C时，已经不能满足上面提到的第一个约束，即C不会给B投票，而A和B显然都不会给对方投票。A胜出之后，会给B,C发心跳消息，节点B发现节点A的term不低于自己的term，知道有已经有Leader了，于是转换成follower。
第三种情况，当存在双数节点的时候，可能出现没有任何节点获得majority投票，比如下图这种情况：
如果出现平票的情况，那么就延长了系统不可用的时间（没有leader是不能处理客户端写请求的），因此raft引入了randomized election timeouts来尽量避免平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。
log Replication
当有了leader，系统应该进入对外工作期了。客户端的一切请求来发送到leader，leader来调度这些并发请求的顺序，并且保证leader与followers状态的一致性。raft中的做法是，将这些请求以及执行顺序告知followers。leader和followers以相同的顺序来执行这些请求，保证状态一致。
Replicated state machines
共识算法的实现一般是基于复制状态机（Replicated state machines）。
简单来说：相同的初识状态 + 相同的输入 = 相同的结束状态。replicated log 具有持久化、保序的特点，是大多数分布式系统的基石。
因此，可以这么说，在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，则状态肯定是一致的。
下图形象展示了这种log-based replicated state machine
请求完成流程
当系统（leader）收到一个来自客户端的写请求，到返回给客户端，整个过程从leader的视角来看会经历以下步骤：
leader 追加log Entry
leader 将log Entry通过RPC并行的分发给follower
leader 等待大多数节点复制成功的响应
leader 将entry应用到状态机上
leader 对客户端进行响应
leader 通知follower应用日志
可以看到日志的提交过程有点类似两阶段提交(2PC)，不过与2PC的区别在于，leader只需要大多数（majority）节点的回复即可，这样只要超过一半节点处于工作状态则系统就是可用的。
那么日志在每个节点上是什么样子的呢
每个log entry都存储着一条用于状态机的指令，同时保存从leader收到该entry时的 term 号以及一个 index 指明自己在log中的位置。
Raft的日志机制提供两个保证，统称为Log Matching Property：
不同机器的日志中如果有两个
entry有相同的偏移和term号，那么它们存储相同的指令。如果不同机器上的日志中有两个相同偏移和term号的
entry，那么日志中这个entry之前的所有entry保持一致。
这个一致性检查以一种类似归纳法的方式进行：初始状态大家都没有日志，不需要进行Log Matching Property检查，但是无论何时followers只要日志要追加都要进行此项检查。因此，只要AppendEntries返回成功，leader就知道这个follower的日志一定和自己的完全一样。
在正常情形下，leader和follower的日志肯定是一致的，所以AppendEntries一致性检查从不失败。然而，如果leader crash，那么它们的日志很可能出现不一致。这种不一致会随着leader或者followers的crash变得非常复杂。下图展示了所有日志不一致的情形：
如上图(a)(b)followers可能丢失日志，(c)(d)有多余的日志，或者是(e)(f)跨越多个terms的又丢失又多余。在Raft里，leader强制followers和自己的日志严格一致，这意味着followers的日志很可能被leader的新推送日志所覆盖。
leader为了强制它人与自己一致，势必要先找出自己和follower之间存在分歧的点，然后令followers删掉那个分歧点之后的日志，再将自己在那个点之后的日志同步给followers。这个实现也是通过AppendEntries RPCs的一致性检查来做的。leader会把发给每一个follower的新日志的偏移nextIndex也告诉followers。当新leader刚开始服务时，它把所有follower的nextIndex都初始化为它最新的log entry的偏移+1（如上图中的11）。如果一个follower的日志和leader的不一致，AppendEntries RPC会失败，leader就减小nextIndex然后重试，直到找到分歧点，剩下的就好办了，移除冲突日志entries，同步自己的。
safety
之前了解了Raft如何选主和如何进行日志复制，然而这些还不足以保证不同节点能执行严格一致的指令序列，需要额外的一些安全机制。比如，一个follower可能在当前leader commit日志时不可用，然而过会它又被选举成了新leader，这样这个新leader可能会用新的entries覆盖掉刚才那些已经committed的entries。结果不同的复制状态机可能会执行不同的指令序列，产生不一致的状况。这里Raft增加了一个可以确保新leader一定包含任何之前commited entries的选举机制。
选举限制
一个candidate为了选举成功必须联系大多数节点，假设它们的集合叫A，而一个entry如果能commit必然存储在大多数节点，这意味着对于每一个已经committed的entry，A集合中必然有一个节点持有它。如果这个candidate的Log不比A中任何一个节点旧才有机会被选举为leader，所以这个candidate如果要成为leader一定已经持有了所有commited entries。
提交早期terms的entries
某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了，具体怎么实现了，在log matching部分有详细介绍。那么问题来了，如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log。
因此，在上图中，不会出现（C）时刻的情况，即term4任期的leader s1不会复制term2的日志到s3。而是如同(e)描述的情况，通过复制-提交 term4的日志顺便提交term2的日志。如果term4的日志提交成功，那么term2的日志也一定提交成功，此时即使s1crash，s5也不会重新当选。
调解过期leader
在Raft中有可能同一时刻不只一个server是leader。一个leader突然与集群中其他servers失去连接，导致新leader被选出，这时刚才的老leader又恢复连接，此时集群中就有了两个leader。这个老leader很可能继续为客户端服务，试图去复制entries给集群中的其它servers。但是Raft的term机制粉碎了这个老leader试图造成任何不一致的行为。每一个RPC servers都要交换它们的当前term号，新leader一旦被选举出来，肯定有一个大多数群体包含了最新的term号，老leader的RPC都必须要联系一个大多数群体，它必然会发现自己的term号过期，从而主动让贤，退变为follower状态。
然而有可能是老leader commit一个entry后失去连接，这时新leader必然有那个commit的entry，只是新leader可能还没commit它，这时新leader会在初次服务客户端前先把这个entry再commit一次，followers如果已经commit过直接返回成功，没commit就commit后返回成功而已，不会造成不一致。
Follower 或者candidate crash
Followers和candidate的crash比起leader来说处理要简单很多，它们的处理流程是相同的，如果某个follower或者candidate crash了，那么未来发往它的RequestVote和AppendEntries RPCs 都会失败，Raft采取的策略就是不停的重发，如果crash的机器恢复就会执行成功。另外，如果server crash是在完成一个RPC但在回复之前，那么在它恢复之后仍然会收到相同的RPC（让它重试一次），Raft的所有RPC都是幂等操作，如果follower已经有了某个entry，但是leader又让它复制，follower直接忽略即可。
集群扩容
扩容最大的挑战就是保证一致性很困难，因为扩容不是原子的，有可能集群中一部分机器用老配置信息，另一部分用新配置信息，开始只有Server1-3，这时候我们添加2个节点，但是配置变更不可能在所有节点上同时生效。如果在箭头所在的时间点刚好触发选举，server1 和server 2的保存的配置还是只有3个节点的集群，所以server1可以通过自己和server 2的选票成为Leader。而Server5通过3、4、5的选票也超过半数，也可以成为Leader。造成存在2个Leader的错误。
Raft的解决方案
Raft协议通过在新旧配置变更中间添加过渡阶段来处理这个问题，称之为联合共识（joint consensus）阶段。在联合共识阶段，集群会做如下的约束：
日志条目被复制给集群中新、老配置的所有节点
新加入节点和原有节点都可以成为 leader
达成一致（针对选举和提交）需要分别在两种配置上都超过半数
满足了上面的条件，集群就可以在切换的同时仍然对外提供服务。下面用具体场景来看下Raft的解决方案。
添加节点
当前有一个3个节点的集群，现在要往集群中添加2个节点。Raft通过发送日志的方式来发送配置变更日志指令。
发送联合共识日志
第一阶段，Leader首先向集群中的节点发送一条新的日志，日志内的指令就是配置变更。这条日志跟普通的日志一样复制给Follower节点，但是提交后不会对状态机的数据有任何改动，因为它不是数据操作指令。当前的状态如下图：
上图中C(o+n)的日志就是配置变更日志，告诉其它几点集群需要进入old和new共存的联合共识阶段。跟处理普通的日志条目不一样，节点在收到C(o+n)的日志后，立马就进入联合共识阶段，而不需要等到Leader提交这条日志。也就是说，上图中S1，S4和S5进入联合共识阶段，而S2,S3因为还没收到日志，所以还处于旧配置阶段。
按照前面讲的，进入联合共识阶段后，Raft要求任何决议的达成必须在新老配置中都达成半数。对于上图中的S1来说，因为它已经处于联合共识阶段，所以如果它要将配置变更的日志提交，必须在老的集群（S1，S2，S3）中超过半数，在新的5个节点的集群中也要超过半数。上图中日志已经复制到3个节点，满足新集群中超过半数的要求，但是在老的3个节点的集群中未超过半数，所以这条日志现在还不能提交。
提交联合共识日志
如上图，进入第二阶段，Leader提交了C(o+n)日志，现在超过半数节点都运行在联合共识阶段，即使Leader崩溃，新选出Leader的集群也仍然会运行在联合共识阶段。这时，Leader会复制一条新集群生效（图中的C(new)）的日志到集群中，告诉Follower节点现在可以切换到新的集群模式下运行了。跟C(o+n)一样，Follower也不需要等到Leader提交C(new)，只要一收到日志，可以立刻切换到新集群。这里有一点需要注意，在C(o+n)提交和复制C(new)日志的这一阶段，集群仍然是正常对外提供服务的，就是说在C(new)日志发出之前，客服端发给Leader的指令可以正常提交，只是提交的条件是日志被复制到新老两个集群的超过半数节点。
提交新集群日志
第三阶段，在开始复制C(new)日志后，Leader已经运行于新的集群中，所以只要C(new)被复制到不少于3个节点，就可以提交了。之后整个集群的扩容就完成了。
扩容安全性
在上面的阶段1，如果Leader崩溃了，会不会出现多个Leader？
Raft协议中规定，对于配置变更的日志，不需要等到提交，各个节点只要收到了就按新的配置运行。在Phase 1阶段，如果S1崩溃了，S2和S3处于旧配置阶段，假设它们中的S2变成候选人，收到S3的选票即超过半数，当选Leader。S4和S5处于联合共识阶段，假设S4变成候选人，那么它必须同时在新旧两个集群超过半数。假设现在S1崩溃后迅速重启并加入集群，那么在新集群中，S4可以收到S1和S5的选票，超过半数；在旧集群中，收到S1的选票，但是无法收到S2或者S3的选票，因为在同一轮选举中，S2和S3已经把票投给了S2。所以，S4无法赢得旧集群的选举，不会出现两个Leader的情况。
在阶段1，如果Leader崩溃，新当选的Leader会继续提交C(o+n)吗？
答案是不一定。如果是S2当选Leader，因为它没有C(o+n)的日志，按照上篇文章讲到的日志复制规范，S4和S5上的C(o+n)会被删除，所以不会提交。客户端必须重新发送配置变更指令。如果是S4当选Leader，会继续复制C(o+n)的日志，配置变更流程会继续进行。这两种情况都是符合Raft规范的。
在阶段2Leader崩溃了，已经提交的C(o+n)会受到影响吗？
不会。Raft协议承诺已提交的日志永久生效。S1在Phase 2崩溃，在老的集群节点中，因为S2有最新的日志，所以只有S2可以当选新的Leader。在新加到集群的节点中，无论是S4还是S5成为新的Leader，都会继续复制和提交C(o+n)
可用性
Raft在集群配置变更时，为了提高可用性，还有以下两个问题需要解决：
新节点同步数据期间无法提交新日志，造成集群短时间不可用？
Raft规定在新节点同步数据期间，可以以没有投票权的方式加入进来（这里类似于ZooKeeper中的Observer节点），比如一共5个节点，有2个节点在同步数据阶段，那Leader可以按3个节点的集群来组织投票。等到数据同步完成后，再正式按正常节点来处理。
被删除的服务器在Leader进入C-new阶段后将不再收到心跳，会触发选举使Leader失效？
为了避免这个问题，Raft规定，当节点确认当前领导人存在时，服务器会忽略请求投票的 RPCs。确认领导人存在的方法就是，收到投票RPC的时间距离上次收到Leader心跳或日志的时间还不到最小选举超时时间，那可以拒绝这个请求。
作者：fjian_fresh
链接：https://juejin.cn/post/7031093358286077983