2、、游戏系统问题，游戏系统出现问题，画面一直跳转不出来，玩家可以退出游戏，等待官方解决。
3、《木筏求生》是以木筏为核心的一款生存类游戏，游戏伊始玩家会被安排在一个2乘2的小木筏之中，面临生存的威胁，需要发挥自己的聪明才智和利用这个世界的物资想办法生存下去。
在分布式系统中，一致性算法至关重要。在所有一致性算法中，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 接收新的写请求写新日志，顺带着把旧日志提交了。
所谓分布式共识（consensus），与 CAP理论 中的一致性（consistency）其实是异曲同工，就是在分布式系统中，所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法，它与一致性协议这个词也经常互相通用。
当今最著名的共识算法就是Paxos算法。它由Leslie Lamport在1990年提出，很长时间以来都是一致性的事实标准。但是它有两个不小的缺点：难以理解和证明，难以在实际工程中实现。Google Chubby的工程师就曾有以下的评论：
于是2014年，来自斯坦福的两位大佬Diego Ongaro与John Ousterhout通过论文 《In Search of an Understandable Consensus Algorithm》 提出了一个新的共识算法Raft。从题目就可以看出，Raft的特点就是容易理解，在此基础上也容易实现，因此在real world中，它的应用也比Paxos要广泛，比较有名的如etcd、Kudu等。
Raft为了达到易懂易用的目标，主要做了两件事：一是分解问题（decomposition），即将复杂的分布式共识问题拆分为 领导选举 （leader election）、 日志复制 （log replication）和 安全性 （safety）三个子问题，并分别解决；二是压缩状态空间（state space reduction），相对于Paxos算法而言施加了更合理的限制，减少因为系统状态过多而产生的不确定性。
下面先简要介绍共识算法的基础——复制状态机，然后就来按顺序研究Raft是如何解决三个子问题的。
在共识算法中，所有服务器节点都会包含一个有限状态自动机，名为复制状态机（replicated state machine）。每个节点都维护着一个复制日志（replicated logs）的队列，复制状态机会按序输入并执行该队列中的请求，执行状态转换并输出结果。可见，如果能保证各个节点中日志的一致性，那么所有节点状态机的状态转换和输出也就都一致。共识算法就是为了保障这种一致性的，下图示出简单的复制状态机及其相关架构。
根据分布式系统的 Quorum机制 与NRW算法，集群中半数以上节点可用时，就能正确处理分布式事务，因此Raft集群几乎都使用奇数节点，可以防止脑裂并避免浪费资源。采用ZAB协议的ZooKeeper集群也是如此。
在Raft集群中，任意节点同一时刻只能处于领导者（leader）、跟随者（follower）、候选者（candidate）三种状态之一。下图示出节点状态的转移规则。
可见，集群建立时所有节点都是跟随节点。如果在一定时间过后发现没有领导节点，就会切换到候选状态，发起选举。得到多数票的候选者就会成为领导节点。如果候选节点或当前领导节点发现了更新的领导者，就会主动退回跟随状态。
领导节点全权负责管理复制日志，也就是从客户端接收请求，复制到跟随节点，并告诉跟随节点何时可以处理这些请求。如果领导节点故障或断开连接，就会重新进行选举。可见，领导节点的存在大大简化了共识算法的设计。
在上面的图中出现了任期（term）这个词。领导者并不是一直“在位”的，工作一段时间之后，就会选举出新的领导者来接替它。
由上图可见，蓝色表示选举时间段，绿色表示选举出的领导者在位的时间段，这两者合起来即称作一个任期，其计数值是自增的。任期的值就可以在逻辑上充当时间戳，每个节点都会保存一份自己所见的最新任期值，称为currentTerm。另外，如果因为票数相同，没能选出领导，就会立即再发起新的选举。
如果一个或多个跟随节点在选举超时（election timeout）内没有收到领导节点的心跳（一个名为AppendEntries的RPC消息，本意是做日志复制用途，但此时不携带日志数据），就会发起选举流程：
根据其他节点回复的消息，会出现如下三种结果：
获得多数票的节点只要当选，就会立即给其他所有节点发送AppendEntries，避免再次选举。另外，在同一任期内，每个节点只能投一票，并且先到先得（first-come-first-served），也就是会把票投给RequestVote消息第一个到达的那个节点。
至于上面的第三种情况，也就是所谓“split vote”现象，容易在很多跟随者变成候选者时出现，因为没有节点能得到多数票，选举有可能无限继续下去。所以，Raft设置的选举超时并不是完全一样的，而是有些许随机性，来尽量使得投票能够集中到那些较“快”的节点上。
领导节点选举出来后，集群就可以开始处理客户端请求了。前面已经说过，每个节点都维护着一个复制日志的队列，它们的格式如下图所示。
可见，日志由一个个按序排列的entry组成。每个entry内包含有请求的数据，还有该entry产生时的领导任期值。在论文中，每个节点上的日志队列用一个数组log[]表示。
当客户端发来请求时，领导节点首先将其加入自己的日志队列，再并行地发送AppendEntries RPC消息给所有跟随节点。领导节点收到来自多数跟随者的回复之后，就认为该请求可以提交了（见图中的commited entries）。然后，领导节点将请求应用（apply）到复制状态机，并通知跟随节点也这样做。这两步做完后，就不会再回滚。
这种从提交到应用的方式与最基础的一致性协议——两阶段提交（2PC）有些相似，但Raft只需要多数节点的确认，并不需要全部节点都可用。
注意在上图中，领导节点和4个跟随节点的日志并不完全相同，这可能是由于跟随节点反应慢、网络状况差等原因。领导节点会不断地重试发送AppendEntries，直到所有节点上的日志达到最终一致，而不实现强一致性。这就是CAP理论中在保证P的情况下，C与A无法兼得的体现。
日志复制的过程仍然遗留了一个问题：如果领导或者跟随节点发生异常情况而崩溃，如何保证日志的最终一致性？它属于下面的安全性问题中的一部分，稍后会解答它。
安全性是施加在领导选举、日志复制两个解决方案上的约束，用于保证在异常情况下Raft算法仍然有效，不能破坏一致性，也不能返回错误的结果。所有分布式算法都应保障安全性，在其基础上再保证活性（liveness）。
Raft协议的安全性保障有5种，分别是：选举安全性（election safety）、领导者只追加（leader append-only）、日志匹配（log matching）、领导者完全性（leader completeness）、状态机安全性（state machine safety） 。下面分别来看。
选举安全性是指每个任期内只允许选出最多一个领导。如果集群中有多于一个领导，就发生了脑裂（split brain）。根据“领导选举”一节中的描述，Raft能够保证选举安全，因为：
在讲解日志复制时，我们可以明显地看出，客户端发出的请求都是插入领导者日志队列的尾部，没有修改或删除的 *** 作。这样可以使领导者的行为尽量简单化，使之没有任何不确定的行为，同时也作为下一节要说的日志匹配的基础。
日志匹配的具体描述如下。
如果两个节点的日志队列中，两个entry具有相同的下标和任期值，那么：
第一点自然由上一节的“领导者只追加”特性来保证，而第二点则由AppendEntries RPC消息的一个简单机制来保证：每条AppendEntries都会包含最新entry之前那个entry的下标与任期值，如果跟随节点在对应下标找不到对应任期的日志，就会拒绝接受并告知领导节点。
有了日志匹配特性，就可以解决日志复制中那个遗留问题了。假设由于节点崩溃，跟随节点的日志出现了多种异常情况，如下图。
注意图中不是6个跟随节点，而是6种可能的情况。比如a和b是丢失了entry，c和d是有多余的未提交entry，e和f则是既有丢失又有冗余。这时领导节点就会找到两个日志队列中最近一条匹配的日志点，将该点之后跟随节点的所有日志都删除，然后将自己的这部分日志复制给它。例如对于上图中的情况e来说，最近一条匹配的日志下标为5，那么5之后的所有entry都会被删除，被替换成领导者的日志。
领导者完全性是指，如果有一条日志在某个任期被提交了，那么它一定会出现在所有任期更大的领导者日志里。这也是由两点来决定的：
根据这两个描述，每次选举出的领导节点一定包含有最新的日志，因此只存在跟随节点从领导节点更新日志的情况，而不会反过来，这也使得一致性逻辑更加简化，并且为下面的状态机安全性提供保证。
状态机安全性是说，如果一个节点已经向其复制状态机应用了一条日志中的请求，那么对于其他节点的同一下标的日志，不能应用不同的请求。这句话就很拗口了，因此我们来看一种意外的情况。
这里就有问题了，在时刻c的日志与新领导者的日志发生了冲突，此时状态机是不安全的。
为了解决该问题，Raft不允许领导者在当选后提交“前任”的日志，而是通过日志匹配原则，在处理“现任”日志时将之前的日志一同提交。具体方法是：在领导者任期开始时，立刻提交一条空的日志，所以上图中时刻c的情况不会发生，而是像时刻e一样先提交任期4的日志，连带提交任期2的日志。就算此时S1再崩溃，S5也不会重新被选举了。
如果想要更直观地理解Raft，建议参考 这里 ，是一个用动画来描述该算法的网页，形象生动。
这是一篇学习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论文中文翻译： >可以先确认您输入的宽带帐号和密码是否正确，错误的帐号和密码是不能正常联网的。
如果帐号和密码正确显示连接超时请您查看宽带猫的指示灯是否有los红灯闪烁，如果有就是宽带故障导致无法正常联网，用户可以致电运营商客服进行报障处理，报障后会有工作人员上门排障的。
除非服务器维护，否则基本都是你自己网络的锅，这游戏我没玩过，但我想说的是steam上大部分联机都需要挂个加速。Raft是一个 一致性算法 ，旨在易于理解。它提供了Paxos的容错和性能。不同之处在于它被分解为相对独立的子问题，它清楚地解决了实际系统所需的所有主要部分。我们希望Raft能够为更广泛的受众提供共识，并且这个更广泛的受众将能够开发出比现在更多的高质量共识系统。
Raft是一个通过管理一个副本日志的一致性算法。它提供了跟(multi-)Paxos一样有效的功能，但是它的架构和Paxos不一样；它比Paxos更加容易理解，并且能用于生产环境中。为了加强理解，raft把一致性的问题分成了三个子问题，例如 leader election, log replication, and safety,
Role
Leader，Follower，candidate
在Raft集群中，有且仅有一个Leader，在Leader运行正常的情况下，一个节点服务器要么就是Leader，要么就是Follower。Follower直到Leader故障了，才有可能变成candidate。
Leader负责把client的写请求log复制到follower。它会和follower保持心跳。每个follower都有一个timeout时间（一般为150ms~300ms），在接受到心跳的时候，这个timeout时间会被重置。如果follower没有接收到心跳，这些follower会把他们的状态变为candidate，并且开启新的一轮leader election。
term逻辑时钟
Term相当于paxos中的proposerID，相当于一个国家的朝代。term是一段任意的时间序号。每一任Leader都有一个与之前不同的term。
当Leader选举成功之后，一个节点成为了Leader，就会产生一个新的term，并且直到Leader故障，整个集群都会一直在这个term下执行 *** 作。
如果leader选举失败了，则会再生成出一个term，再开启一轮leader选举。
Quorums：
多数派，意思是超过一半的机器存活，则这个机器可用，这个Quorums指的就是集群可用的指标。例如：集群中的节点数为2N，如果有N+1的机器存活，则代表集群可用，可接受请求，写入log，应用到state machine中去，执行 *** 作。如果少于N+1个机器存活，则代表集群可用，可接受请求，可写入log，但不应用到state machine中去，不执行 *** 作。
Leader Election
只有在下列两种情况下才会进行leader election：
在第一次启动raft集群的时候
在一个已存在的Leader故障的时候
选举流程：
如果以上两种任何一种发生了，所有的Follower无法再和Leader保持心跳，则它们都会等待一个（选举）timeout，如果其中一个Follower的timeout最先到时，则这个Follower变成candidate开始选举，
第一，增加term计数器，
第二，给自己投票并向所有其他的节点服务器请求投自己一票。
如果一个Follower在接受到投票请求时，接受到两个term相同的投票请求时（也就是说，产生了两个candidate），则在多个相同term的投票请求中，这个Follower只能给投给其中一个请求，只能投一票，并且按照先来先服务的原则投票。
如果这个candidate收到另外一个节点服务器的消息，并且这个节点服务器的term序号和当前的term序号一样大，甚至更大的话，则这个candidate选举失败，从而它的状态变成Follower，并且接受新的Leader。
如果一个candidate获得了 Quorums 选票N+1(2N为集群中节点的数目)，则它变成新的leader。
如果多个candidate和多个Follower投完票之后，有多个candidate获得了相同的票数，则会产生split vote，则新的term产生，重新选举。Raft用随机选举timeout迅速地解决split vote问题，这个方法就是对于产生spit vote的candidates各自随机生成一个选举timeout，谁先到时，谁当leader，其他candidate都变为Follower。
当一个leader被选举出来之后，就在Follower timeout到时变为candidate之前，发心跳信息给所有Followers。
Log Replication（Raft协议具体过程）
Leader负责把client的请求日志复制给其他Followers。
Raft协议具体过程就是通过复制状态机的架构实现的，如下：
步骤：
Client发送请求给Leader，其中每个请求都是一条 *** 作指令。
Leader接受到client请求之后，把 *** 作指令(Entry)追加到Leader的 *** 作日志中。紧接着对Follower发起AppendEntries请求、尝试让 *** 作指令(Entry)追加到Followers的 *** 作日志中，即落地。如果有Follower不可用，则一直尝试。
一旦Leader接受到多数（ Quorums ）Follower的回应，Leader就会进行commit *** 作，每一台节点服务器会把 *** 作指令交给状态机处理。这样就保证了各节点的状态的一致性。
各服务器状态机处理完成之后，Leader将结果返回给Client。
Saftety
Raft的安全性，体现在如下几个方面：
Election safety: 在一个term下，最多只有一个Leader。
Leader Append-Only: 一个Leader只能追加新的entries，不能重写和删除entries
Log Matching: 集群中各个节点的log都是相同一致的
Leader Completeness: 如果一个log entry被committed了，则这个entry一定会出现在Leader的log里。
State Machine Safety: 如果一个节点服务器的state machine执行了一个某个log entry命令，则其他节点服务器，也会执行这个log entry命令，不会再执行其他命令
之前四条，在前面都有所提及，而 State Machine Safety 是在Leader election过程中用到过。
State Machine Safety
一个candidate在选举的时候，它会向其他节点服务器发送包含他的log的消息，获取票数，如果它的log是最新的，则会获取选票，如果它的log不是最新的，其他节点服务器还有更加新的log，则会拒绝给这个candidate投票。这就保证了State Machine Safety。
所以State Machine Safety保证的就是一个candidate必须拥有最新的log，才能获取票数，才有机会赢得Leader选举，才有机会成为Leader。
Follower crashes
如果一个follower故障了，则不会再接受 AppendEntries and vote requests，并且Leader会不断尝试与这个节点保持心跳。
如果这个节点恢复了，则会接受Leader的最新的log，并且将log应用到state machine中去，执行log中的 *** 作
方格指的是client发出的一条请求。
方格虚线，说明一条log entry写入了log。
方格实线，说明一条log entry应用到state machine中
Leader crashes
则会进行Leader election。
如果碰到Leader故障的情况，集群中所有节点的日志可能不一致。
old leader的一些 *** 作日志没有通过集群完全复制。new leader将通过强制Followers复制自己的log来处理不一致的情况，步骤如下：
对于每个Follower，new leader将其日志与Followers的日志进行比较，找到他们的达成一致的最后一个log entry。
然后删除掉Followers中这个关键entry后面的所有entry，并将其替换为自己的log entry。该机制将恢复日志的一致性。
下面这种情况集群中所有节点的日志可能不一致：
总结
Raft要求具备唯一Leader，并把一致性问题具体化为保持日志副本的一致性，以此实现相较Paxos而言更容易理解、更容易实现的目标。Raft是state machine system，Zab是primary-backup system。本文为RAFT一致性算法论文的译文，原文是《In search of an Understandable Consensus Algorithm (Extended Version)》，作者为 Diego Ongaro 和 John Ousterhout 。
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所示，复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机通过计算得到相同的状态，最后的输出结果也就一致了。
一致性算法的工作就是保证复制的日志一致。在一台服务器上，一致性模块接收到客户端的指令后把指令写入到日志中，并与其他服务器上的一致性模块通信，以确保每一个日志最终包含一致的请求序列，即使有某些服务器宕机。一旦这些指令被正确的复制了，每一个服务器的状态机都会按同样的顺序去执行它们，然后将结果返回给客户端。最终，这些服务器看起来就像一台可靠的状态机。在实际系统中应用的一致性算法一般有以下特性：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）