Raft是什么
分布一致性算法允许一组机器像一个整体一样工作，即使其中的一些机器出了错误也能正常工作，是建立大规模可靠的软件系统的关键角色。Raft 则是分布式一致性复制协议中的一种，它将一致性分解为多个子问题：Leader选举（Leader election）、日志同步（Log replication）、安全性（Safety）、日志压缩（Log compaction）、成员变更（Menbership change）等。同时，Raft算法使用了更强的假设来减少了需要考虑的状态，使之变的易于理解和实现。
Raft特性
Strong Leader：Raft 使用一种比其他算法更强的领导形式。例如，日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理，使得 Raft 更易于理解。
Leader election：Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。
Membership changes：Raft 为了调整集群中成员关系使用了新的联合一致性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交迭（overlap）。这使得在集群配置改变的时候，我们能够继续操作集群。
基本概念
节点角色
Raft算法中节点的角色可以划分为领导者(Leader)，跟随者(Follower)和候选者（Candidate）；在任意的时间，每一个节点一定会处于这三种角色中的一个，不同的角色在系统中承担着不同的任务。
Leader：接收客户端请求，并向Follower同步客户端的请求日志，当leader发现当前日志已经同步到大多数节点上时，则通知集群中所有节点将日志进行提交。需要注意的是，在正常情况下，每一个集群中都只有一个节点是Leader，剩下的节点是追随者；
Follower：Follower是被动的，并不会主动产生请求，只会对来自Leader和Candidate的请求进行反馈；
Candidate：当集群中不存在领导者时，Follower会转换为Candidate，参与领导选举，如果Candidate获得集群中大多数节点的支持，则转换为Leader；
状态转换
节点间的角色转换规律如下图所示：
如图所示，所有节点在刚启动时都处于 Follower 状态，Follower只响应其他服务器的请求。如果Follower在一段时间内没有收到任何消息，它会成为一个Candidate并且开始一次选举(Leader Election)。收到大多数节点投票的Candidate会成为新的Leader 。Leader 在它们宕机之前会一直保持Leader 状态。
Term(任期)
整个系统在运行过程中被划分为一个个Term(任期)，这是一个单调递增的字段。每一个任期都开始于一次领导选举，如果Candidate当选成功成为leader，会在当前任期内管理整个集群直至任期结束（比如leader节点宕机了）；如果Candidate当选失败，则任期加1，重新发起选举（该情况主要出现在有多个candidate同时发起选举）。
任期在 Raft 中充当逻辑时钟的角色，可以协助节点检测过期的信息，比如过时的Leader。每一个节点都存储着当前节点所知道的任期字段，该字段是单调递增的。当节点间进行通信时，会互相检查对方的当前的任期；
如果一个节点的当前任期比其它节点小，则更新为较大的任期。
如果一个Candidate或者Leader意识到它的任期过时了，它会立刻转换为Follower状态。
如果一个节点收到的请求的任期是过时的（即比自己当前的任期小），那么它会拒绝该请求。
RPC请求
在raft协议中，节点间主要是基于两种RPC请求来进行通信和保持信息的一致性的，这两种请求分别是：
Raft的安全属性
选举安全原则
领导人只增加原则
日志匹配原则
领导人完全原则
状态机安全原则
主要内容
领导选举leader election
Raft应用一种心跳（heartbeat）机制来触发领导选举。当系统开始运行时，每个节点都会初始化为Follower状态。
Follower状态下的节点只要能及时收到RPCs请求就会保持状态不做变化；但如果在一段超时时间内没收到任何请求，就会选择开始一轮新的选举；
如上述状态转换图示所述，Follower开始一轮新的选举，先是将自己当前的Term加1，其次转为candidate状态；此时Candidate会等待一段随机的选举超时时间（Election Timeout），接着candidate会给自己投票的同时发送RequestVote RPCs广播请求投票，接到投票的Follower会响应RPCs并给对应的candidate投票。此时节点会一直保持在candidate状态，以应对以下三种情况的出现：
Candidate获取集群中超过半数节点的投票支持，赢得选举，变成Leader，开始定时发送心跳，并接收客户端请求和进行日志复制(Log replication)
- 每个节点在给定的任期内最多只能投票给一位Candidate，以先到先得为原则
- Leader定时向其他节点发送心跳消息，是为了建立其权威并防止Followers长时间没收到消息而触发新的领导选举
Candidate在等待过程中，另外有节点成为Leader
一段时间过去了，依旧没有人赢得选举
出现这种情况可能是因为在此时有多个Follower成为了Candidate，出现了票数平分情况，都发生了超时，此时Candidate会将Term加1并重新开始新一轮的选举
值得注意的是，Raft为避免票数平分情况的不断出现，提出了随机的选举超时时间（Election Timeout）。即每一个Candidate在发送RequestVote RPCs广播请求之前，会先随机等待一段选举超时时间，该随机时间是在一个固定的间隔内随机选出来的（例如，150~300ms）。这种机制使得在大多数情况下只有一个Candidate会率先超时，它会在其它Candidate超时之前赢得选举并且向其它节点发送心跳信息(其他节点还没发送RequestVote RPCs就已经发现有新的Leader了，又变回了Follower)。该机制减小在新的选举中一开始选票就被瓜分的可能性
日志复制log replication
Leader的主要任务之一便是接收客户端命令，每个请求都会包含一条需要由复制状态机执行的命令，Leader将该命令封装成为一条新的日志记录(Log Entry)，并行发送给集群中的其余节点进行日志的复制（基于AppendEntries RPC）。
日志记录的结构如图所示：
每一条Log Entry均主要包含了当前的任期Term和日志索引Log Index，如果一个日志记录的 Term与 Log Index 与另外一个日志记录相同，那么这两个日志记录就是相同的。同时，raft协议的安全性决定了，如果两个节点的某两个日志记录具有相同的Term和Log Index，那么在这两条记录之前的所有日志记录也一定是完全一致的。
当一个Log Entry被安全复制后（即大多数Follower都回复Leader说已经复制了），Leader把该Log Entry应用到它的状态机，并记录日志的状态为committed，然后返回执行结果给客户端；需要注意的是，如果Follower出现问题，比如节点崩溃或者运行的慢，或者丢包，Leader会一直重试AppendEntries RPC，直到所有Follower都存储了该Log Entry。
Leader会跟踪它所知道的可以被提交的最高日志索引(committed index)，并将该索引包含在未来要发送的AppendEntries RPCs中，以便其他节点最终发现。一旦Follower得知某个日志已经被Leader标记为committed了，它就将该条目应用到其本地状态机，这有利于不同节点上的日志保持高度一致性。
安全性
之前的章节中讨论了 Raft 算法是如何进行领导选取和复制日志的。然而，这个机制还不能保证每一个状态机能按照相同的顺序执行同样的指令。例如，当Leader提交了若干日志条目的同时一个Follower可能宕机了，之后它又被选为了领导人然后用新的日志条目覆盖掉了旧的日志，最后，不同的状态机可能执行不同的命令序列。基于此，Raft协议加入了选举限制来完善算法，这个限制能够保证对于固定的任期，任何的Leader都拥有之前任期提交的全部日志条目
选举限制-Election restriction
该限制主要基于RequestVote RPC实现，Candidate发送RequestVote RPC时，会在RPC中携带关于Candidate日志的信息；投票人接收到RequestVote RPC后，如果投票人本地的日志比Candidate的日志更新，投票人将拒绝该请求。
日志比较的原则是，如果当前节点的最后一条Log Entry的Term更大，则Term大的更新，如果Term一样大，则比较日志的Log Index，哪个日志长度更长，哪个日志则更新。
通过这种机制，我们可以确保最终选出来的Leader所包含的日志记录是集群中最新的，即拥有最新的已提交的Log Entry的Candidate才有能成为Leader
提交之前任期的日志记录
对于Leader来说，当客户端发送一个日志请求时，前面说到过会根据该日志是否已经同步到在集群中大多数节点上的方式，以判断是否要提交该日志（即将该日志进行committed，应用到状态机）。但这种判断机制，只适用于日志中的任期字段与Leader所处的任期相等的情况。
而对于之前任期中的尚未提交的日志，Leader将在提交当前 任期的日志时一并进行提交处理。基于该机制，可以避免节点中已经提交的日志又被覆盖的情况。
参考
