Raft 是一种用于管理日志复制的一致性算法，它与 Paxos 算法在效果和性能上相近。但得益于其独特的结构，Raft 比 Paxos 更易于理解，且更易于在实际项目中落地。为了便于理解，Raft 将一致性算法的关键部分分为：leader 选取，日志复制，安全性。并且，Raft 通过使用更强的一致性以减少必须考虑的状态。因此，对于学生群体，Raft 比 Paxos 更易于学习，这在一项用户调查研究中得到了印证。此外，Raft 引入了新的机制——重叠多数（overlapping majorities）原则来保证安全地动态调整集群成员。
一致性算法保证一组机器像一个整体一样工作，即使其中一些机器出现故障。因此，一致性算法是建立可靠的大规模软件系统的关键。在过去的十年中 Paxos 一直主导着有关一致性算法的讨论：大多数一致性算法的实现都基于它或者受它影响，并且 Paxos 也成为了教学中关于一致性知识的主要工具。
然而，尽管研究人员在降低它的复杂性方面做了许多努力，Paxos 依旧很难理解。并且，Paxos 需要经过复杂的修改才能应用于实际系统中。这些导致了系统构建者和学生都对 Paxos 十分头疼。
在被 Paxos 折磨之后，我们开始寻找一种新的在系统构建和教学上更好的一致性算法。与常规方法不同，我们的首要目标是让一致性算法易于理解：我们能不能定义一种面向实际系统的、比 Paxos 更容易学习的一致性算法呢？此外，我们希望这种算法直观易懂，这对一个系统构建者来说是十分必要的。对于一个算法，不仅要能够实现并且正常工作，还要清楚地明白其中的原理。
这项工作的结果是一种新的一致性算法，叫做 Raft。在设计 Raft 的过程中我们应用了许多专门的技巧来便于理解，包括算法分解（分为领导选取，日志复制和安全性）和约简状态空间（state space reduction，相对于 Paxos，Raft 减少了非确定性的程度和导致服务器之间不一致的可能）。在针对两所大学43名学生的用户调查中发现，Raft 比 Paxos 更易于理解：在学习了两种算法之后，回答问题时，其中的33个学生对 Raft 的问题回答的更好。
Raft 算法与现在一些已有的算法在某些地方很相似（主要是 Oki 和 Liskov 的 Viewstamped Replication），但是 Raft 有如下新特性：
我们认为，在教学和实际实现方面，Raft 比 Paxos 和其他算法更优秀。Raft 比其他算法更简单，更易于理解；它能满足一个实际系统的需求；它拥有许多开源的实现并且被许多公司使用；它的安全特性已经被证明；并且它的效率和其他算法相比也具有竞争力。
这篇论文剩下的部分会讲如下内容：复制状态机（replicated state machine）问题（第2节），讨论 Paxos 的优缺点（第3节），讨论为了使算法更便于理解所用的方法（第4节），陈述 Raft 一致性算法（第5~8节），评价 Raft 算法（第9节），对相关工作的讨论（第10节）。
一致性算法是在复制状态机的背景下提出来的。在这个方法中，一组服务器的状态机计算产生相同状态的副本，即使其中一些服务器崩溃，这组服务器也还能继续运行。复制状态机用于解决分布式系统中多种容错相关的问题。例如，GFS，HDFS和 RAMCloud 之类大规模系统都是用独立的复制状态机来管理 leader 选取，以及存储配置信息来应对 leader 崩溃的情况。 Chubby 和 ZooKeeper 就是使用复制状态机的例子。
如图1所示，复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机通过计算得到相同的状态，最后的输出结果也就一致了。
一致性算法的工作就是保证复制的日志一致。在一台服务器上，一致性模块接收到客户端的指令后把指令写入到日志中，并与其他服务器上的一致性模块通信，以确保每一个日志最终包含一致的请求序列，即使有某些服务器宕机。一旦这些指令被正确的复制了，每一个服务器的状态机都会按同样的顺序去执行它们，然后将结果返回给客户端。最终，这些服务器看起来就像一台可靠的状态机。在实际系统中应用的一致性算法一般有以下特性：
在分布式系统中，一致性算法至关重要。在所有一致性算法中，Paxos 最负盛名，它由莱斯利·兰伯特（Leslie Lamport）于 1990 年提出，是一种基于消息传递的一致性算法，被认为是类似算法中最有效的。
Paxos 算法虽然很有效，但复杂的原理使它实现起来非常困难，截止目前，实现 Paxos 算法的开源软件很少，比较出名的有 Chubby、LibPaxos。此外，Zookeeper 采用的 ZAB（Zookeeper Atomic Broadcast）协议也是基于 Paxos 算法实现的，不过 ZAB 对 Paxos 进行了很多改进与优化，两者的设计目标也存在差异——ZAB 协议主要用于构建一个高可用的分布式数据主备系统，而 Paxos 算法则是用于构建一个分布式的一致性状态机系统。
由于 Paxos 算法过于复杂、实现困难，极大地制约了其应用，而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法，在此背景下，Raft 算法应运而生。
Raft 算法在斯坦福 Diego Ongaro 和 John Ousterhout 于 2013 年发表的《In Search of an Understandable Consensus Algorithm》中提出。相较于 Paxos，Raft 通过逻辑分离使其更容易理解和实现，目前，已经有十多种语言的 Raft 算法实现框架，较为出名的有 etcd、Consul 。
根据官方文档解释，一个 Raft 集群包含若干节点，Raft 把这些节点分为三种状态：Leader、 Follower、Candidate，每种状态负责的任务也是不一样的。正常情况下，集群中的节点只存在 Leader 与 Follower 两种状态。
• Leader（领导者） ：负责日志的同步管理，处理来自客户端的请求，与Follower保持heartBeat的联系；
• Follower（追随者） ：响应 Leader 的日志同步请求，响应Candidate的邀票请求，以及把客户端请求到Follower的事务转发（重定向）给Leader；
• Candidate（候选者） ：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发起选举，选举胜出（获得超过半数节点的投票）后，从Candidate转为Leader状态。
通常，Raft 集群中只有一个 Leader，其它节点都是 Follower。Follower 都是被动的，不会发送任何请求，只是简单地响应来自 Leader 或者 Candidate 的请求。Leader 负责处理所有的客户端请求（如果一个客户端和 Follower 联系，那么 Follower 会把请求重定向给 Leader）。
为简化逻辑和实现，Raft 将一致性问题分解成了三个相对独立的子问题。
• 选举（Leader Election） ：当 Leader 宕机或者集群初创时，一个新的 Leader 需要被选举出来；
• 日志复制（Log Replication） ：Leader 接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点，并且强制要求其它节点的日志和自己保持一致；
• 安全性（Safety） ：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其它服务器节点不能在同一个日志索引位置应用一个不同的指令。
根据 Raft 协议，一个应用 Raft 协议的集群在刚启动时，所有节点的状态都是 Follower。由于没有 Leader，Followers 无法与 Leader 保持心跳（Heart Beat），因此，Followers 会认为 Leader 已经下线，进而转为 Candidate 状态。然后，Candidate 将向集群中其它节点请求投票，同意自己升级为 Leader。如果 Candidate 收到超过半数节点的投票（N/2 + 1），它将获胜成为 Leader。
第一阶段：所有节点都是 Follower。
上面提到，一个应用 Raft 协议的集群在刚启动（或 Leader 宕机）时，所有节点的状态都是 Follower，初始 Term（任期）为 0。同时启动选举定时器，每个节点的选举定时器超时时间都在 100~500 毫秒之间且并不一致（避免同时发起选举）。
第二阶段：Follower 转为 Candidate 并发起投票。
没有 Leader，Followers 无法与 Leader 保持心跳（Heart Beat），节点启动后在一个选举定时器周期内未收到心跳和投票请求，则状态转为候选者 Candidate 状态，且 Term 自增，并向集群中所有节点发送投票请求并且重置选举定时器。
注意，由于每个节点的选举定时器超时时间都在 100-500 毫秒之间，且彼此不一样，以避免所有 Follower 同时转为 Candidate 并同时发起投票请求。换言之，最先转为 Candidate 并发起投票请求的节点将具有成为 Leader 的“先发优势”。
第三阶段：投票策略。
节点收到投票请求后会根据以下情况决定是否接受投票请求（每个 follower 刚成为 Candidate 的时候会将票投给自己）：
请求节点的 Term 大于自己的 Term，且自己尚未投票给其它节点，则接受请求，把票投给它；
请求节点的 Term 小于自己的 Term，且自己尚未投票，则拒绝请求，将票投给自己。
第四阶段：Candidate 转为 Leader。
一轮选举过后，正常情况下，会有一个 Candidate 收到超过半数节点（N/2 + 1）的投票，它将胜出并升级为 Leader。然后定时发送心跳给其它的节点，其它节点会转为 Follower 并与 Leader 保持同步，到此，本轮选举结束。
注意：有可能一轮选举中，没有 Candidate 收到超过半数节点投票，那么将进行下一轮选举。
在一个 Raft 集群中，只有 Leader 节点能够处理客户端的请求（如果客户端的请求发到了 Follower，Follower 将会把请求重定向到 Leader） ，客户端的每一个请求都包含一条被复制状态机执行的指令。Leader 把这条指令作为一条新的日志条目（Entry）附加到日志中去，然后并行得将附加条目发送给 Followers，让它们复制这条日志条目。
当这条日志条目被 Followers 安全复制，Leader 会将这条日志条目应用到它的状态机中，然后把执行的结果返回给客户端。如果 Follower 崩溃或者运行缓慢，再或者网络丢包，Leader 会不断得重复尝试附加日志条目（尽管已经回复了客户端）直到所有的 Follower 都最终存储了所有的日志条目，确保强一致性。
第一阶段：客户端请求提交到 Leader。
如下图所示，Leader 收到客户端的请求，比如存储数据 5。Leader 在收到请求后，会将它作为日志条目（Entry）写入本地日志中。需要注意的是，此时该 Entry 的状态是未提交（Uncommitted），Leader 并不会更新本地数据，因此它是不可读的。
第二阶段：Leader 将 Entry 发送到其它 Follower
Leader 与 Followers 之间保持着心跳联系，随心跳 Leader 将追加的 Entry（AppendEntries）并行地发送给其它的 Follower，并让它们复制这条日志条目，这一过程称为复制（Replicate）。
有几点需要注意：
1 为什么 Leader 向 Follower 发送的 Entry 是 AppendEntries 呢？
因为 Leader 与 Follower 的心跳是周期性的，而一个周期间 Leader 可能接收到多条客户端的请求，因此，随心跳向 Followers 发送的大概率是多个 Entry，即 AppendEntries。当然，在本例中，我们假设只有一条请求，自然也就是一个Entry了。
2 Leader 向 Followers 发送的不仅仅是追加的 Entry（AppendEntries）。
在发送追加日志条目的时候，Leader 会把新的日志条目紧接着之前条目的索引位置（prevLogIndex）， Leader 任期号（Term）也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么它就会拒绝接收新的日志条目，因为出现这种情况说明 Follower 和 Leader 不一致。
3 如何解决 Leader 与 Follower 不一致的问题？
在正常情况下，Leader 和 Follower 的日志保持一致，所以追加日志的一致性检查从来不会失败。然而，Leader 和 Follower 一系列崩溃的情况会使它们的日志处于不一致状态。Follower可能会丢失一些在新的 Leader 中有的日志条目，它也可能拥有一些 Leader 没有的日志条目，或者两者都发生。丢失或者多出日志条目可能会持续多个任期。
要使 Follower 的日志与 Leader 恢复一致，Leader 必须找到最后两者达成一致的地方（说白了就是回溯，找到两者最近的一致点），然后删除从那个点之后的所有日志条目，发送自己的日志给 Follower。所有的这些 *** 作都在进行附加日志的一致性检查时完成。
Leader 为每一个 Follower 维护一个 nextIndex，它表示下一个需要发送给 Follower 的日志条目的索引地址。当一个 Leader 刚获得权力的时候，它初始化所有的 nextIndex 值，为自己的最后一条日志的 index 加 1。如果一个 Follower 的日志和 Leader 不一致，那么在下一次附加日志时一致性检查就会失败。在被 Follower 拒绝之后，Leader 就会减小该 Follower 对应的 nextIndex 值并进行重试。最终 nextIndex 会在某个位置使得 Leader 和 Follower 的日志达成一致。当这种情况发生，附加日志就会成功，这时就会把 Follower 冲突的日志条目全部删除并且加上 Leader 的日志。一旦附加日志成功，那么 Follower 的日志就会和 Leader 保持一致，并且在接下来的任期继续保持一致。
第三阶段：Leader 等待 Followers 回应。
Followers 接收到 Leader 发来的复制请求后，有两种可能的回应：
写入本地日志中，返回 Success；
一致性检查失败，拒绝写入，返回 False，原因和解决办法上面已做了详细说明。
需要注意的是，此时该 Entry 的状态也是未提交（Uncommitted）。完成上述步骤后，Followers 会向 Leader 发出 Success 的回应，当 Leader 收到大多数 Followers 的回应后，会将第一阶段写入的 Entry 标记为提交状态（Committed），并把这条日志条目应用到它的状态机中。
第四阶段：Leader 回应客户端。
完成前三个阶段后，Leader会向客户端回应 OK，表示写 *** 作成功。
第五阶段，Leader 通知 Followers Entry 已提交
Leader 回应客户端后，将随着下一个心跳通知 Followers，Followers 收到通知后也会将 Entry 标记为提交状态。至此，Raft 集群超过半数节点已经达到一致状态，可以确保强一致性。
需要注意的是，由于网络、性能、故障等各种原因导致“反应慢”、“不一致”等问题的节点，最终也会与 Leader 达成一致。
前面描述了 Raft 算法是如何选举 Leader 和复制日志的。然而，到目前为止描述的机制并不能充分地保证每一个状态机会按照相同的顺序执行相同的指令。例如，一个 Follower 可能处于不可用状态，同时 Leader 已经提交了若干的日志条目；然后这个 Follower 恢复（尚未与 Leader 达成一致）而 Leader 故障；如果该 Follower 被选举为 Leader 并且覆盖这些日志条目，就会出现问题，即不同的状态机执行不同的指令序列。
鉴于此，在 Leader 选举的时候需增加一些限制来完善 Raft 算法。这些限制可保证任何的 Leader 对于给定的任期号（Term），都拥有之前任期的所有被提交的日志条目（所谓 Leader 的完整特性）。关于这一选举时的限制，下文将详细说明。
在所有基于 Leader 机制的一致性算法中，Leader 都必须存储所有已经提交的日志条目。为了保障这一点，Raft 使用了一种简单而有效的方法，以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的 Leader 中。换言之，日志条目的传送是单向的，只从 Leader 传给 Follower，并且 Leader 从不会覆盖自身本地日志中已经存在的条目。
Raft 使用投票的方式来阻止一个 Candidate 赢得选举，除非这个 Candidate 包含了所有已经提交的日志条目。Candidate 为了赢得选举必须联系集群中的大部分节点。这意味着每一个已经提交的日志条目肯定存在于至少一个服务器节点上。如果 Candidate 的日志至少和大多数的服务器节点一样新（这个新的定义会在下面讨论），那么它一定持有了所有已经提交的日志条目（多数派的思想）。投票请求的限制中请求中包含了 Candidate 的日志信息，然后投票人会拒绝那些日志没有自己新的投票请求。
Raft 通过比较两份日志中最后一条日志条目的索引值和任期号，确定谁的日志比较新。如果两份日志最后条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。
如同 41 节介绍的那样，Leader 知道一条当前任期内的日志记录是可以被提交的，只要它被复制到了大多数的 Follower 上（多数派的思想）。如果一个 Leader 在提交日志条目之前崩溃了，继任的 Leader 会继续尝试复制这条日志记录。然而，一个 Leader 并不能断定被保存到大多数 Follower 上的一个之前任期里的日志条目 就一定已经提交了。这很明显，从日志复制的过程可以看出。
鉴于上述情况，Raft 算法不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有 Leader 当前任期里的日志条目通过计算副本数目可以被提交；一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。在某些情况下，Leader 可以安全地知道一个老的日志条目是否已经被提交（只需判断该条目是否存储到所有节点上），但是 Raft 为了简化问题使用了一种更加保守的方法。
当 Leader 复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号，这在提交规则上产生了额外的复杂性。但是，这种策略更加容易辨别出日志，即使随着时间和日志的变化，日志仍维护着同一个任期编号。此外，该策略使得新 Leader 只需要发送较少日志条目。
raft 的读写都在 leader 节点中进行，它保证了读的都是最新的值，它是符合强一致性的（线性一致性），raft 除了这个还在客户端交互那块也做了一些保证，详情可以参考论文。但是 zookeeper 不同，zookeeper 写在 leader，读可以在 follower 进行，可能会读到了旧值，它不符合强一致性（只考虑写一致性，不考虑读一致性），但是 zookeeper 去 follower 读可以有效提升读取的效率。
对比于 zab、raft，我们发现他们选举、setData 都是需要过半机制才行，所以他们针对网络分区的处理方法都是一样的。
一个集群的节点经过网络分区后，如一共有 A、B、C、D、E 5个节点，如果 A 是 leader，网络分区为 A、B、C 和 D、E，在A、B、C分区还是能正常提供服务的，而在 D、E 分区因为不能得到大多数成员确认（虽然分区了，但是因为配置的原因他们还是能知道所有的成员数量，比如 zk 集群启动前需要配置所有成员地址，raft 也一样），是不能进行选举的，所以保证只会有一个 leader。
如果分区为 A、B 和 C、D、E ，A、B 分区虽然 A 还是 leader，但是却不能提供事务服务（setData），C、D、E 分区能重新选出 leader，还是能正常向外提供服务。
1）我们所说的日志（log）与状态机（state machine）不是一回事，日志指还没有提交到状态机中的数据。
2）新 leader 永远不会通过计算副本数量提交旧日志，他只能复制旧日志都其他 follower 上，对于旧日志的提交，只能是新 leader 接收新的写请求写新日志，顺带着把旧日志提交了。
Raft将共识问题分解成了三个相对独立的子问题，
选举安全：在给定的一个时期内至多一个leader被选举出来
leader仅追加：leader从来不在他的log里重写或删除条目，从来都只追加新条目
日志匹配：如果两个日志个包含了一个条目带有相同index和term，那就说明通过给定的index所指定的所有条目都是相同的。
leader完整性：如果一个日志条目在给定的时期中被确认提交了，那该条目会出现在所有高编号时期的leaders中的log里。
状态机安全：如果一个server通过给定index申请了一条日志到他的状态机中，不会有其他的server用相同的index申请不同的日志条目
Raft必须全程保证这些状态为真。
一个Raft集群包含众多服务器，5个服务器就可组成经典raft模型，有两个服务器宕机的容错，在集群运行的时间当中，每一个服务器都会是以下三种状态之一，leader，follower，或candidate，在正常 *** 作下，绝对只有一个leader，其余的节点为follower，follower们是被动的。他们不通过自己处理请求，但会简单的响应来自leader或者candidates的请求，leader处理所有follower的请求（如果一个客户端联系了一个follower，那么follower会将改请求重定向到leader处理），candidate用于选出新的leader。
Raft将时间划分为不定的长度，时刻会被连续的整数编号，每一个时刻由一次选举开始，在这一时刻一个或多个的candidates企图变成leader。如果candidate赢下选举，他将会变成leader服务大家，在一些情况下，选举将会造成分票，在这种情况下，该时期将会结束以没有选举出leader的原因。一个新的时间段，将会带着新的选举一起到来。
raft必须确保一个时间段下，leader最多只有一个。
不同的服务器可能会发现在时刻之间做角色的转变（你无法想象论文中的这句话有多绕，我真服了），换句话说就是，每个服务器都可能在过程中发生身份的变化，可能你在此时为leader，在下一个周期中就变成了follower。在一些特殊情况下，一个server甚至可能根本都观察不到这些状态发生改变，可能断连了。Terms由该文章引入的词汇，被看成是系统进程的逻辑时钟，像是计时器，每一个服务器都存储着当前的term数字，该数字会在过程中持续单调增加。当前的term会在server沟通的时候交换。如果一个服务器中的term小于了其他服务器，那他会更新他当前的term，变成更大的term，如果一个candidate或者leader发现自己的term过期了，他会立刻变成follower状态，如果一个服务器接收到了老的term数字，他会回绝这次请求。
raft服务器通过RPC彼此联系，为什么不是>
木筏求生raft中的剧情岛上基本都有被锁住的门，这时我们需要找到对应的钥匙来开门，我为大家整理了常见的会让玩家卡关的钥匙，希望能帮到大家。
木筏求生raft全钥匙获得方法：
1医务室钥匙
木筏求生Raft游戏中医务室钥匙的位置在海底的一个集装箱里，沿着换气装置下到海底可以看到一个集装箱，在集装箱里就能找到医务室的钥匙，还有滑索部件和金属探测器蓝图。
2大仓库钥匙
在终章第一个岛遇到大鲨鱼前会先需要找到大仓库钥匙，先在水下公寓寻找聚光灯部件，完成前置修复聚光灯的任务，聚光灯修复完成后进入到一个有水母堵着的另一个管道，里面会有一些陷阱，走到里面能够找到大仓库钥匙还有字条。
3雪岛反应堆钥匙
雪岛反应堆在天文台，通过解锁密码获得核反应基地大门钥匙，穿防护服进入右边第二个门，中途捡控制杆再到入口大厅处拉闸门，就可以获得反应堆钥匙。
4起重机钥匙
起重机钥匙需要击杀鲨鱼后才能够获取到，正确的打法是用炸药，先让鲨鱼顶柱子，让柱子露出钢筋然后下面有炸d，放上炸d在让鲨鱼撞，一层层向上撞,就有钥匙了。
这是一篇学习raft论文的总结，主要是对看论文过程中难以理解的几个问题的记录。系统性的讲解还是得看raft论文，论文原文是最好的材料。
引用论文中的第一句话--“Raft 是一种为了管理复制日志的一致性算法”。从两个角度来理解raft算法，第一部分是raft的基本规则，第二部分是raft的异常情况处理。下面放一张raft论文中的经典图来了解一下raft是怎么在一个系统中工作的。下图中一致性模块Consensus Module执行的就是raft算法，它保证拷贝到所有server上的每一条日志是一致的。State Machine状态机对应我们的业务逻辑，日志作为状态机的输入，输入一致就能保证输出是一致的。
基本规则
raft的工作模式是一个Leader和多个Follower模式，即我们通常说的领导者-追随者模式。这种模式下需要解决的第一个问题就是Leader的选举问题。其次是如何把日志从Leader复制到所有Follower上去。这里先不关心安全和可靠性，只理解raft运行起来基本规则。raft中的server有三种状态，除了已经提到的Leader和Follower状态外，还有Candidate状态，即竞选者状态。下面是这三种状态的转化过程。
1、Leader的选举过程
raft初始状态时所有server都处于Follower状态，并且随机睡眠一段时间，这个时间在0~1000ms之间。最先醒来的server A进入Candidate状态，Candidate状态的server A有权利发起投票，向其它所有server发出requst_vote请求，请求其它server给它投票成为Leader。当其它server收到request_vote请求后，将自己仅有的一票投给server A，同时继续保持Follower状态并重置选举计时器。当server A收到大多数（超过一半以上）server的投票后，就进入Leader状态，成为系统中仅有的Leader。raft系统中只有Leader才有权利接收并处理client请求，并向其它server发出添加日志请求来提交日志。
2、日志复制过程
Leader选举出来后，就可以开始处理客户端请求。Leader收到客户端请求后，将请求内容作为一条log日志添加到自己的log记录中，并向其它server发送append_entries(添加日志)请求。其它server收到append_entries请求后，判断该append请求满足接收条件（接收条件在后面安全保证问题3给出），如果满足条件就将其添加到本地的log中，并给Leader发送添加成功的response。Leader在收到大多数server添加成功的response后，就将该条log正式提交。提交后的log日志就意味着已经被raft系统接受，并能应用到状态机中了。
Leader具有绝对的日志复制权力，其它server上存在日志不全或者与Leader日志不一致的情况时，一切都以Leader上的日志为主，最终所有server上的日志都会复制成与Leader一致的状态。
以上就是raft允许的基本规则，如果不出现任何异常情况，那么只要上面两个过程就能使raft运行起来了。但是现实的系统不可能这么一帆风顺，总是有很多异常情况需要考虑。raft的复杂性就来源于对这些异常情况的考虑，下面一小节就以问答的方式来总结raft是怎么保证安全性的。
安全性保证
1、Leader选举过程中，如果有两个serverA和B同时醒来并发出request_vote请求怎么办？
由于在一次选举过程中，一个server最多只能投一票，这就保证了serverA和B不可能同时得到大多数（一半以上）的投票。如果A或者B中其一幸运地得到了大多数投票，就能顺利地成为Leader，raft系统正常运行下去。但是A和B可能刚好都得到一半的投票，两者都成为不了Leader。这时A和B继续保持Candidate状态，并且随机睡眠一段时间，等待进入到下一个选举周期。由于所有server都是随机选择睡眠时间，所以连续出现多个server竞选的概率很低。
2、Leader挂了后，如何选举出新的Leader？
Leader正常运作时，会周期性地发出append_entries请求。这个周期性的append_entries除了可以更新其它Follower的log信息，另外一个重要功能就是起到心跳作用。Follower收到append_entries后，就知道Leader还活着。如果Follower经过一个预定的时间(一般设为2000ms左右)都没有收到Leader的心跳，就认为Leader挂了。于是转入Candidate状态，开始发起投票竞选新的Leader。每个新的Leader产生后就是一个新的任期，每个任期都对应一个唯一的任期号term。这个term是单调递增的，用来唯一标识一个Leader的任期。投票开始时，Candidate将自己的term加1，并在request_vote中带上term；Follower只会接受任期号term比自己大的request_vote请求，并为之投票。这条规则保证了只有最新的Candidate才有可能成为Leader。
3、Follower在收到一条append_entries添加日志请求后，是否立即保存并将其应用到状态机中去？如果不是立即应用，那么由什么来决定该条日志生效的时间？
Follower在收到一条append_entries后，首先会检查这条append_entries的来源信息是否与本地保存的leader信息符合，包括leaderId和任期号term。检查合法后就将日志保存到本地log中，并给Leader回复添加log成功，但是不会立即将其应用到本地状态机。Leader收到大部分Follower添加log成功的回复后，就正式将这条日志commit提交。Leader在随后发出的心跳append_entires中会带上已经提交日志索引。Follower收到Leader发出的心跳append_entries后，就可以确认刚才的log已经被commit(提交)了，这个时候Follower才会把日志应用到本地状态机。下表即是append_entries请求的内容，其中leaderCommit即是Leader已经确认提交的最大日志索引。Follower在收到Leader发出的append_entries后即可以通过leaderCommit字段决定哪些日志可以应用到状态机。
4、假设有一个server A宕机了很长一段时间，它的日志已经落后很多。如果A重新上线，而且此时现有Leader挂掉，server A刚好竞选成为了Leader。按照日志都是由Leader复制给其它server的原则，server A会把其它Follower已经提交的日志给抹掉，而这违反了raft状态机安全特性，raft怎么解决这种异常情况？
所谓的状态机安全特性即是“如果一个***已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志”。如果server在竞选Leader的过程中不加任何限制的话，携带旧日志的server也有可能竞选成为Leader，就必然存在覆盖之前Leader已经提交的日志可能性，从而违反状态机安全特性。raft的解决办法很简单，就是只有具有最新日志的server的才有资格去竞选当上Leader，具体是怎么做到的呢？首先任何server都还是有资格去发起request_vote请求去拉取投票的，request_vote中会带上server的日志信息，这些信息标明了server日志的新旧程度，如下表所示。
其它server收到request_vote后，判断如果lastLogTerm比自己的term大，那么就可以给它投票；lastLogTerm比自己的term小，就不给它投票。如果相等的话就比较lastLogIndex，lastLogIndex大的话日志就比较新，就给它投票。下图是raft日志格式，每条日志中不仅保存了日志内容，还保存了发送这条日志的Leader的任期号term。为什么要在日志里保存任期号term，由于任期号是全局单调递增且唯一的，所以根据任期号可以判断一条日志的新旧程度，为选举出具有最新日志的Leader提供依据。
5、存在如下图一种异常情况，server S5在时序(d)中覆盖了server S1在时序(c)中提交的index为2的日志，方框中的数字是日志的term。这违反了状态机的安全特性--“如果一个***已经在给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会提交一个不同的日志”，raft要如何解决这个问题？
出现这个问题的根本原因是S1在时序(c) 的任期4内提交了一个之前任期2的log，这样S1提交的日志中最大的term仅仅是2，那么一些日志比较旧的server，比如S5(它最日志的term为 3)，就有机会成为leader，并覆盖S1提交的日志。解决办法就是S1在时序(c)的任期term4提交term2的旧日志时，旧日志必须附带在当前term 4的日志下一起提交。这样就把S1日志的最大term提高到了4，让那些日志比较旧的S5没有机会竞选成为Leader，也就不会用旧的日志覆盖已经提交的日志了。
简单点说，Leader如果要提交之前term的旧日志，那么必须要提交一条当前term的日志。提交一条当前term的日志相当于为那些旧的日志加了一把安全锁，让那些日志比较旧的server失去得到Leader的机会，从而不会修改那些之前term的旧日志。
怎么具体实现旧日志必须附带在当前term的日志下一起提交呢？在问题3中有给出append_entries请求中的字段，其中有两个字段preLogIndex和preLogTerm的作用没有提到，这两个字段就是为了保证Leader和Followers的历史日志完全一致而存在的。当Leader在提交一条新日志的时候，会带上新日志前一条日志的index和term，即preLogIndex和preLogTerm。Follower收到append_entries后，会检查preLogIndex和preLogTerm是否和自己当前最新那条日志的index和term对得上，如果对不上就会给Leader返回自己当前日志的index和term。Leader收到后就将Follower返回的index对应的日志以及对应的preLogIndex和preLogTerm发送给Follower。这个过程一直重复，直到Leader和Follower找到了第一个index和term能对得上的日志，然后Leader从这条日志开始拷贝给Follower。回答段首的问题，Leader在提交一条最新的日志时，Follow会检验之前的日志是否与Leader保持了一致，如果不一致会一直同步到与Leader一致后才添加最新的日志，这个机制就保证了Leader在提交最新日志时，也提交了之前旧的日志。
6、向raft系统中添加新机器时，由于配置信息不可能在各个系统上同时达到同步状态，总会有某些server先得到新机器的信息，有些server后得到新机器的信息。比如下图raft系统中新增加了server4和server5这两台机器。只有server3率先感知到了这两台机器的添加。这个时候如果进行选举，就有可能出现两个Leader选举成功。因为server3认为有3台server给它投了票，它就是Leader，而server1认为只要有2台server给它投票就是Leader了。raft怎么解决这个问题呢？
产生这个问题的根本原因是，raft系统中有一部分机器使用了旧的配置，如server1和server2，有一部分使用新的配置，如server3。解决这个问题的方法是添加一个中间配置(Cold, Cnew)，这个中间配置的内容是旧的配置表Cold和新的配置Cnew。还是拿上图中的例子来说明，这个时候server3收到添加机器的消息后，不是直接使用新的配置Cnew，而是使用(Cold, Cnew)来做决策。比如说server3在竞选Leader的时候，不仅需要得到Cold中的大部分投票，还要得到Cnew中的大部分投票才能成为Leader。这样就保证了server1和server2在使用Cold配置的情况下，还是只可能产生一个Leader。当所有server都获得了添加机器的消息后，再统一切换到Cnew。raft实现中，将Cold，(Cold,Cnew)以及Cnew都当成一条普通的日志。配置更改信息发送Leader后，由Leader先添加一条 (Cold, Cnew)日志，并同步给其它Follower。当这条日志(Cold, Cnew)提交后，再添加一条Cnew日志同步给其它Follower，通过Cnew日志将所有Follower的配置切换到最新。
有的raft实现采用了一种更加简单粗暴的方法来解决成员变化的问题。这个办法就是每次只更新一台机器的配置变化，收到配置变化的机器立马采用新的配置。这样的做法为什么能确保安全性呢？下面举例说明。比如说系统中原来有5台机器A,B,C,D,E，现在新加了一台机器F，A,B,C三台机器没有感知到F的加入，只有D,E两台机器感知到了F的加入。现在就有了两个旧机器集合X｛A, B, C, D, E}和新机器集合Y｛F｝。假设A和D同时进入Candidate状态去竞选Leader，其中D要想竞选成功，必须得有一半以上机器投票，即6/2+1=4台机器，就算Y集合中的F机器给D投了票，还得至少在集合X中得到3票；而A要想竞选成功，也必须得到5/2+1 = 3张票，由于A只知道集合X的存在，所以也必须从集合X中获得至少3票。而A和D不可能同时从集合X同时获得3票，所以A和D不可能同时竞选成为Leader，从而保证了安全性。可以使用更加形式化的数学公式来证明一次添加一台机器配置不会导致产生两个Leader，证明过程就暂时省略了。
raft论文中文翻译： >
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）