raft是用来管理复制日志一致性的算法 类似paxos, 但是是比paxos更容易让人明白和实现 raft算法允许一组服务器程序保持他们的状态或者数据的一致, 并且允许个别服务器程序挂掉, 所以很多大型程序都使用了raft算法来构建高可用特性
raft利用心跳机制来触发选主 集群中服务器启动的时候是以follower的角色启动的 leader定时发送心跳包给follower(AppendEntries RPCs)来维持主从之间的关系 当follower超过一定时间(election timeout)还没收到交互消息(除了leader发的消息还包括candidate给从发的消息), 从认为没有主, 触发新的选主流程
选主开始的时候, follower增加它的term, 并且从follower转变为candidate状态 然后先给自己投票, 再并行的发送RequestVote RPC消息给集群中的其它节点 candidate将保持当前状态, 一直到一下几件事发生: candidate赢得选举; 其它节点赢得选举;超过一定时间上述两个事件都没发生
上篇讲到了「拜占庭将军问题」：多个拜占庭将军要如何在可能有叛徒、信使可能被策反或者暗杀的情况下达成是否要进攻的一致性决定？还不了解的先看看上一篇 《拜占庭将军问题》 。这篇主要是介绍简化版拜占庭将军问题的解决方案：Raft 共识算法。
所以将拜占庭将军问题根据常见的工作上的问题进行简化： 假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？
对于这个简化后的问题，有许多解决方案，第一个被证明的共识算法是 Paxos，由拜占庭将军问题的作者 Leslie Lamport 在1990年提出，最初以论文难懂而出名，后来这哥们在2001重新发了一篇简单版的论文 Paxos Made Simple ，然而还是挺难懂的。
因为 Paxos 难懂，难实现，所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比，Raft 有着基本相同运行效率，但是更容易理解，也更容易被用在系统开发上。
我们还是用拜占庭将军的例子来帮助理解 Raft。
Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军，所有的决定由大将军来做。 选举环节 ：比如说现在一共有3个将军 A, B, C，每个将军都有一个 随机时间 的倒计时器，倒计时一结束，这个将军就会把自己当成大将军候选人，然后派信使去问其他几个将军，能不能选我为总将军？假设现在将军A倒计时结束了，他派信使传递选举投票的信息给将军B和C，如果将军B和C还没把自己当成候选人（倒计时还没有结束），并且没有把选举票投给其他，他们把票投给将军A，信使在回到将军A时，将军A知道自己收到了足够的票数，成为了大将军。在这之后，是否要进攻就由大将军决定，然后派信使去通知另外两个将军，如果在一段时间后还没有收到回复（可能信使被暗杀），那就再重派一个信使，直到收到回复。
故事先讲到这里，希望不做技术方面的朋友可以大概能理解 Raft 的原理，下面从比较技术的角度讲讲 Raft 的原理。
从拜占庭将军的故事映射到分布式系统上，每个将军相当于一个分布式网络节点，每个节点有 三种状态：Follower，Candidate，Leader ，状态之间是互相转换的，可以参考下图，具体的后面说。
每个节点上都有一个倒计时器 (Election Timeout)，时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout：
在 Raft 运行过程中，最主要进行两个活动：
假设现在有如图5个节点，5个节点一开始的状态都是 Follower。
在一个节点倒计时结束 (Timeout) 后，这个节点的状态变成 Candidate 开始选举，它给其他几个节点发送选举请求 (RequestVote)
其他四个节点都返回成功，这个节点的状态由 Candidate 变成了 Leader，并在每个一小段时间后，就给所有的 Follower 发送一个 Heartbeat 以保持所有节点的状态，Follower 收到 Leader 的 Heartbeat 后重设 Timeout。
这是最简单的选主情况， 只要有超过一半的节点投支持票了，Candidate 才会被选举为 Leader ，5个节点的情况下，3个节点 (包括 Candidate 本身) 投了支持就行。
一开始已经有一个 Leader，所有节点正常运行。
Leader 出故障挂掉了，其他四个 Follower 将进行重新选主。
4个节点的选主过程和5个节点的类似，在选出一个新的 Leader 后，原来的 Leader 恢复了又重新加入了，这个时候怎么处理？在 Raft 里，第几轮选举是有记录的，重新加入的 Leader 是第一轮选举 (Term 1) 选出来的，而现在的 Leader 则是 Term 2，所有原来的 Leader 会自觉降级为 Follower
假设一开始有4个节点，都还是 Follower。
有两个 Follower 同时 Timeout，都变成了 Candidate 开始选举，分别给一个 Follower 发送了投票请求。
两个 Follower 分别返回了ok，这时两个 Candidate 都只有2票，要3票才能被选成 Leader。
两个 Candidate 会分别给另外一个还没有给自己投票的 Follower 发送投票请求。
但是因为 Follower 在这一轮选举中，都已经投完票了，所以都拒绝了他们的请求。所以在 Term 2 没有 Leader 被选出来。
这时，两个节点的状态是 Candidate，两个是 Follower，但是他们的倒计时器仍然在运行，最先 Timeout 的那个节点会进行发起新一轮 Term 3 的投票。
两个 Follower 在 Term 3 还没投过票，所以返回 OK，这时 Candidate 一共有三票，被选为了 Leader。
如果 Leader Heartbeat 的时间晚于另外一个 Candidate timeout 的时间，另外一个 Candidate 仍然会发送选举请求。
两个 Follower 已经投完票了，拒绝了这个 Candidate 的投票请求。
Leader 进行 Heartbeat， Candidate 收到后状态自动转为 Follower，完成选主。
以上是 Raft 最重要活动之一选主的介绍，以及在不同情况下如何进行选主。
总结：
1每个节点一直有一个timeout，timeout结束就开始选自己为主节点；
2主节点会轮询从节点，从节点更新timeout；
3选举等级机制；
Raft 在实际应用场景中的一致性更多的是体现在不同节点之间的数据一致性，客户端发送请求到任何一个节点都能收到一致的返回，当一个节点出故障后，其他节点仍然能以已有的数据正常进行。在选主之后的复制日志就是为了达到这个目的。
一开始，Leader 和 两个 Follower 都没有任何数据。
客户端发送请求给 Leader，储存数据 “sally”，Leader 先将数据写在本地日志，这时候数据还是 Uncommitted (还没最终确认，红色表示)
Leader 给两个 Follower 发送 AppendEntries 请求，数据在 Follower 上没有冲突，则将数据暂时写在本地日志，Follower 的数据也还是 Uncommitted。
Follower 将数据写到本地后，返回 OK。Leader 收到后成功返回， 只要收到的成功的返回数量超过半数 (包含Leader) ，Leader 将数据 “sally” 的状态改成 Committed。( 这个时候 Leader 就可以返回给客户端了)
Leader 再次给 Follower 发送 AppendEntries 请求，收到请求后，Follower 将本地日志里 Uncommitted 数据改成 Committed。这样就完成了一整个复制日志的过程，三个节点的数据是一致的，
在 Network Partition 的情况下，部分节点之间没办法互相通信，Raft 也能保证在这种情况下数据的一致性。
一开始有 5 个节点处于同一网络状态下。
Network Partition 将节点分成两边，一边有两个节点，一边三个节点。
两个节点这边已经有 Leader 了，来自客户端的数据 “bob” 通过 Leader 同步到 Follower。
因为只有两个节点，少于3个节点，所以 “bob” 的状态仍是 Uncommitted。所以在这里， 服务器会返回错误给客户端
另外一个 Partition 有三个节点，进行重新选主。客户端数据 “tom” 发到新的 Leader，通过和上节网络状态下相似的过程，同步到另外两个 Follower。
因为这个 Partition 有3个节点，超过半数，所以数据 “tom” 都 Commit 了。
网络状态恢复，5个节点再次处于同一个网络状态下。但是这里出现了数据冲突 “bob" 和 “tom"
三个节点的 Leader 广播 AppendEntries
两个节点 Partition 的 Leader 自动降级为 Follower，因为这个 Partition 的数据 “bob” 没有 Commit，返回给客户端的是错误，客户端知道请求没有成功，所以 Follower 在收到 AppendEntries 请求时，可以把 “bob“ 删除，然后同步 ”tom”，通过这么一个过程，就完成了在 Network Partition 情况下的复制日志，保证了数据的一致性。
Raft 是能够实现分布式系统强一致性的算法，每个系统节点有三种状态 Follower，Candidate，Leader。实现 Raft 算法两个最重要的事是：选主和复制日志
参考链接：
Raft 官网： >本文为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条）