分布式一致性如何实现？- Raft 算法
介绍
Raft 是一种管理复制日志的一致性算法，它比 Paxos 更容易理解和实现。Raft 为了更加容易理解和实现，做了算法拆解，Raft 将一致性算法抽象为几个关键模块，例如：领导人选举、日志复制、安全等。
Raft 算法的产生不仅是为了解决分布式共识问题，还为了方便使用的他的人能够清楚的明白它为什么能工作。也就是可理解性、可实现上更加的简单。
Raft 算法特性：
强领导人：和其他算法相比，Raft 算法使用一种更强的领导力形式。比如日志条目只能通过领导人复制给其他跟随者。这种方式简化的对日志复制的管理。
领导人选举：Raft 算法使用一个随机计时器的方式进行选举，当计时器结束后节点状态就会由跟随者变成候选人状态，立即发送选举请求。
成员变更：Raft 使用一种共同一致的方法来处理集群成员变更问题。
日志复制：领导人必须从客户端接收日志条目，然后复制到集群中的其他节点，并强制要求其他节点的日志和自己保持一致。
复制状态机
在计算机科学领域，状态机复制是实现容错服务的一种常规方法，主要通过复制服务器，并协调客户端和这些服务器镜像间的交互来达到目标。这个方法也同时提供了理解和设计复制管理协议的一套基本框架。
一致性算法是从复制状态机的背景下提出的（参考英文原文引用 37）。在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。
复制状态机的结构。一致性算法管理着来自客户端指令的复制日志。状态机从日志中处理相同顺序的相同指令，所以产生的结果也是相同的。
复制状态机通常都是基于复制日志实现的，如上图。每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序包含相同的指令，所以每一个服务器都执行相同的指令序列。因为每个状态机都是确定的，每一次执行操作都产生相同的状态和同样的序列。
一致性算法的任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求，即使有些服务器发生故障。一旦指令被正确的复制，每一个服务器的状态机按照日志顺序处理他们，然后输出结果被返回给客户端。因此，服务器集群看起来形成了一个高可靠的状态机。
Raft 有哪几种状态？
Raft 算法支持三种节点状态，分别是跟随者、候选人、领导者，所以节点初始化的时候都默认是跟随者状态。
跟随者（Follower）
响应来自候选人或者领导人的请求（选举、心跳、日志）。
如果超过随机计时器时间没有接到领导人日志或心跳，就会变更为候选人状态。
候选人（Candidate）
候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票：
增加自己的任期号
给自己投票
重置选举超时时间
发送投票请求给其他节点
如果得到了半数以上的票，就晋升为领导人状态。
如果选举期间接收到来自新的领导人的附加日志或心跳 RPC，则立即转变为跟随者状态。
如果选举过程超时，则发起新一轮的选举。
领导人（Leader）
领导人状态下就要每隔一段时间不停地给跟随者发送心跳，来维护领导人的地位。
接收并处理来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端。
管理日志复制，将日志同步到其他跟随者节点中。
选举分析
选举是什么？
选举就是在一个集群多个节点中选出一个节点来担任领导人的角色，负责和外部通信，管理集群中其他节点。
选举过程
首先假设我们有一个 3 个节点的集群，分别是节点 A、节点 B、节点 C。初始化的时候 3 个节点的状态全部都是跟随者（follower）状态，节点 A 的任期编号是 0 ，超时时间是 100 ms 。节点 B 的任期编号是 0 ，超时时间是 200 ms。节点 C 的任期编号是 0 ，超时时间是 300 ms。
任期编号可以理解为是某一个节点当选领导人的时间段，并且也是选举过程中的重要判断依据。类似版本号。
Raft 算法实现了随机超时时间，在没有领导人的情况下，最先超时的是节点 A，此时节点 A 会先增加自己的任期编号，设置为 1 。再给自己投一票，同时变更自己的状态为候选人（candidate）状态，并向其他节点发送选举投票请求，请求其他节点选自己为领导人。
此时其他节点收到了节点 A 的投票请求，对比下任期编号是否小于自己的任期编号，如果小于就拒绝投票，反之如果在此任期编号上还没有进行过投票，就会把票投给节点 A。并更新自己的任期编号。
每个任期编号下只有一次投票的机会
如果节点 A 在超时时间内得到了节点半数以上的票数，那么它就会成为新的领导人。
当节点 A 变成领导人以后，就会每隔一段时间发送心跳给节点 B 和节点 C，证明自己还存活着，不需要再次发起选举，只有当领导人不能正常工作了才需要发起选举操作。节点 B、C 接到心跳请求后会刷新自己的随机超时时间。
选举规则
为了解决选举无效或者规定时间内没有达到指定票数，Raft 实现了一种随机选举超时时间的方式。
跟随者等待领导者的心跳时间是随机的。
选举的超时时间间隔是随机的。
领导者需要周期性的向跟随者发送心跳，证明自己还活着，否则将会触发选举。第一个等待心跳超时的节点会推荐自己为候选人，向其他节点请求投票。
同一个任期编号只有一次投票的机会。按照先来后到原则进行投票。
在一次选举中得到全部节点半数以上票的节点，当选新的领导人。
在一个任期能只能有一个领导者，直到这个领导自身出现问题，才会发生下一个任期的选举。
日志完整性高的跟随者拒绝投票给日志完整性低的候选人。
比如当节点 A 的任期编号是 5 ，并且已经复制了 5 个日志，节点 B 的任期编号是 6，目前复制了 4 个日志，此时节点 B 当候选人，请求节点 A 给它投票，就会被节点 A 拒绝。
日志复制
日志是什么？
Raft 是一种管理复制日志的一致性算法，所以在 Raft 中管理的是日志，日志可以理解为系统中需要进行同步的副本数据。副本数据在 Raft 中是以日志的形式存在的，日志由日志项组成。
日志项包含任期编号、日志索引、用户指定的数据等：
指令：一条由客户端请求的、状态机需要执行的指令，可以理解为要同步给其他节点的数据。
索引值：日志项对应的整数索引值，用来标识唯一的日志项，是一个连续的、单调递增的号码
任期编号：对应创建这条日志的领导人的任期编号。
复制过程
假设一个 Raft 集群已经选举完毕，此时客户端发来一个请求指令 Set x=3，领导人会根据请求创建一个新的日志项，然后附加到本地日志中。
然后领导人通过日志复制 RPC ，将新的日志项复制到其他的节点上。当收到大多数节点响应以后，领导人就认为复制成功了，然后就提交本地日志，给客户端返回执行结果。
在领导人提交以后，是不需要告诉跟随者日志已提交的，因为在领导人发给跟随者的心跳请求中就包含当前领导人已提交的日志索引，跟随者会根据提交索引判断自己应该提交哪些日志。
领导人通过日志复制 RPC 一致性检查保证日志的一致，找到跟随者节点上与自己相同日志项的最大索引值，然后复制并更新覆盖该索引值之后的日志项，实现了各个节点日志的一致。
首先领导人会发日志复制 RPC 给跟随者，跟随者发现自己本地的日志和发过来的日志对不上，就会拒绝新的日志项，返回失败信息给领导人。这时领导人会递减要复制的日志项索引，并再次发送日志复制消息给跟随者，循环此步骤直到找到跟随者和自己日志相同的日志索引，复制并更新覆盖该索引值之后的日志项，实现集群节点的日志一致。
Raft 是领导人主导，所以跟随者中和领导人不一样的日志会被领导人的日志覆盖，而领导人不会覆盖或者删除自己的日志，只做增加操作。
成员节点变更
受动态扩缩容的影响，我们的系统集群可能会增加节点或者删除节点。在 Raft 中对集群成员变更可能会产生分区问题。这样就会导致集群分裂，一个集群可能会出现两个领导人。
因为 Raft 的领导人选举，建立在“大多数”的基础之上，那么当成员变更时，集群成员发生了变化，就可能同时存在新旧配置的 2 个“大多数”，出现 2 个领导者，破坏了 Raft 集群的领导人唯一性，影响了集群的运行。
最初实现成员变更的是联合共识（Joint Consensus），但这个方法实现起来难，后来 Raft 的作者就提出了一种改进后的方法，单节点变更（single-server changes）。
单节点变更就是通过一次变更一个节点来实现成员节点变更，如果需要添加多个节点，那就需要执行多次单节点变更。比如将 3 节点集群扩容到 6 节点集群，就需要先将 3 个节点 变更为 4 个节点，然后再将 4 个节点变更为 5 个节点，最后在将 5 个节点变更为 6 个节点。
第一步领导人向新节点同步日志数据。
第二步领导人将新配置作为一个日志项复制到新配置中的所有节点上，然后将新配置的日志项应用到本地状态机，完成单节点变更。
本文只对 Raft 的几个关键模块原理进行简单介绍，实际 Raft 在每一个模块都有详细的规则和设计，对 Raft 感兴趣的朋友可以查看参考中的资料进行深入的研究。
后续计划用 Java 实现下 Raft 算法，感兴趣的朋友可以关注 Service Plus 这个项目
参考
版权声明: 本文为 InfoQ 作者【晓双】的原创文章。
原文链接:【http://xie.infoq.cn/article/2e0cc9fbd5e5a734c030b12eb】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
🏆 InfoQ签约作者 2019.03.26 加入
还未添加个人简介
评论