在哪里购买虚拟空间建设网站,网站建设策划书模板下载,公众号开发用什么语言,怎么做网站模块Paxos是出了名的难懂#xff0c;而Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解#xff0c;所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。推荐阅读提示强烈推荐通过如下资料学习raft。 raft.github.io这里面有一个…Paxos是出了名的难懂而Raft正是为了探索一种更易于理解的一致性算法而产生的。它的首要设计目的就是易于理解所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。推荐阅读提示强烈推荐通过如下资料学习raft。 raft.github.io这里面有一个Raft Visualization:In Search of an Understandable Consensus Algorithm动画理解Raft神器Raft算法简介不同于Paxos算法直接从分布式一致性问题出发推导出来Raft算法则是从多副本状态机的角度提出用于管理多副本状态机的日志复制。Raft实现了和Paxos相同的功能它将一致性分解为多个子问题: Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等。同时Raft算法使用了更强的假设来减少了需要考虑的状态使之变的易于理解和实现。角色Raft将系统中的角色分为领导者(Leader)、跟从者(Follower)和候选人(Candidate):Leader: 接受客户端请求并向Follower同步请求日志当日志同步到大多数节点上后告诉Follower提交日志。Follower: 接受并持久化Leader同步的日志在Leader告之日志可以提交之后提交日志。Candidate: Leader选举过程中的临时角色。Raft要求系统在任意时刻最多只有一个Leader正常工作期间只有Leader和Followers。角色状态转换Follower只响应其他服务器的请求。如果Follower超时没有收到Leader的消息它会成为一个Candidate并且开始一次Leader选举。收到大多数服务器投票的Candidate会成为新的Leader。Leader在宕机之前会一直保持Leader的状态。Raft算法将时间分为一个个的任期(term)每一个term的开始都是Leader选举。在成功选举Leader之后Leader会在整个term内管理整个集群。如果Leader选举失败该term就会因为没有Leader而结束。Raft算法子问题Raft实现了和Paxos相同的功能它将一致性分解为多个子问题: Leader选举(Leader election)、日志同步(Log replication)、安全性(Safety)、日志压缩(Log compaction)、成员变更(Membership change)等Leader选举Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时初始化为Follower。Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat就会等待一段随机的时间后发起一次Leader选举。Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC (RPC细节参见八、Raft算法总结)。结果有以下三种情况:赢得了多数的选票成功选举为Leader收到了Leader的消息表示有其它服务器已经抢先当选了Leader没有服务器赢得多数的选票Leader选举失败等待选举时间超时后发起下一次选举。选举出Leader后Leader通过定期向所有Followers发送心跳信息维持其统治。若Follower一段时间未收到Leader的心跳则认为Leader可能已经挂了再次发起Leader选举过程。Raft保证选举出的Leader上一定具有最新的已提交的日志这一点将在四、安全性中说明。日志同步Leader选出后就开始接收客户端的请求。Leader把请求作为日志条目(Log entries)加入到它的日志中然后并行的向其他服务器发起 AppendEntries RPC (RPC细节参见八、Raft算法总结)复制日志条目。当这条日志被复制到大多数服务器上Leader将这条日志应用到它的状态机并向客户端返回执行结果。某些Followers可能没有成功的复制日志Leader会无限的重试 AppendEntries RPC直到所有的Followers最终存储了所有的日志条目。日志由有序编号(log index)的日志条目组成。每个日志条目包含它被创建时的任期号(term)和用于状态机执行的命令。如果一个日志条目被复制到大多数服务器上就被认为可以提交(commit)了。Raft日志同步保证如下两点:如果不同日志中的两个条目有着相同的索引和任期号则它们所存储的命令是相同的。如果不同日志中的两个条目有着相同的索引和任期号则它们之前的所有条目都是完全一样的。第一条特性源于Leader在一个term内在给定的一个log index最多创建一条日志条目同时该条目在日志中的位置也从来不会改变。第二条特性源于 AppendEntries 的一个简单的一致性检查。当发送一个 AppendEntries RPC 时Leader会把新日志条目紧接着之前的条目的log index和term都包含在里面。如果Follower没有在它的日志中找到log index和term都相同的日志它就会拒绝新的日志条目。一般情况下Leader和Followers的日志保持一致因此 AppendEntries 一致性检查通常不会失败。然而Leader崩溃可能会导致日志不一致: 旧的Leader可能没有完全复制完日志中的所有条目。上图阐述了一些Followers可能和新的Leader日志不同的情况。一个Follower可能会丢失掉Leader上的一些条目也有可能包含一些Leader没有的条目也有可能两者都会发生。丢失的或者多出来的条目可能会持续多个任期。Leader通过强制Followers复制它的日志来处理日志的不一致Followers上的不一致的日志会被Leader的日志覆盖。Leader为了使Followers的日志同自己的一致Leader需要找到Followers同它的日志一致的地方然后覆盖Followers在该位置之后的条目。Leader会从后往前试每次AppendEntries失败后尝试前一个日志条目直到成功找到每个Follower的日志一致位点然后向后逐条覆盖Followers在该位置之后的条目。安全性Raft增加了如下两条限制以保证安全性:拥有最新的已提交的log entry的Follower才有资格成为Leader。这个保证是在RequestVote RPC中做的Candidate在发送RequestVote RPC时要带上自己的最后一条日志的term和log index其他节点收到消息时如果发现自己的日志比请求中携带的更新则拒绝投票。日志比较的原则是如果本地的最后一条log entry的term更大则term大的更新如果term一样大则log index更大的更新。Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。之所以要这样是因为可能会出现已提交的日志又被覆盖的情况:在阶段aterm为2S1是Leader且S1写入日志(term, index)为(2, 2)并且日志被同步写入了S2在阶段bS1离线触发一次新的选主此时S5被选为新的Leader此时系统term为3且写入了日志(term, index)为(3 2);S5尚未将日志推送到Followers就离线了进而触发了一次新的选主而之前离线的S1经过重新上线后被选中变成Leader此时系统term为4此时S1会将自己的日志同步到Followers按照上图就是将日志(2 2)同步到了S3而此时由于该日志已经被同步到了多数节点(S1, S2, S3)因此此时日志(22)可以被提交了。在阶段dS1又下线了触发一次选主而S5有可能被选为新的Leader(这是因为S5可以满足作为主的一切条件: 1. term 5 42. 最新的日志为(32)比大多数节点(如S2/S3/S4的日志都新)然后S5会将自己的日志更新到Followers于是S2、S3中已经被提交的日志(22)被截断了。增加上述限制后即使日志(22)已经被大多数节点(S1、S2、S3)确认了但是它不能被提交因为它是来自之前term(2)的日志直到S1在当前term(4)产生的日志(4 4)被大多数Followers确认S1方可提交日志(44)这条日志当然根据Raft定义(44)之前的所有日志也会被提交。此时即使S1再下线重新选主时S5不可能成为Leader因为它没有包含大多数节点已经拥有的日志(44)。日志压缩在实际的系统中不能让日志无限增长否则系统重启时需要花很长的时间进行回放从而影响可用性。Raft采用对整个系统进行snapshot来解决snapshot之前的日志都可以丢弃。每个副本独立的对自己的系统状态进行snapshot并且只能对已经提交的日志记录进行snapshot。Snapshot中包含以下内容:日志元数据。最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。系统当前状态。当Leader要发给某个日志落后太多的Follower的log entry被丢弃Leader会将snapshot发给Follower。或者当新加进一台机器时也会发送snapshot给它。发送snapshot使用InstalledSnapshot RPC。做snapshot既不要做的太频繁否则消耗磁盘带宽 也不要做的太不频繁否则一旦节点重启需要回放大量日志影响可用性。推荐当日志达到某个固定的大小做一次snapshot。做一次snapshot可能耗时过长会影响正常日志同步。可以通过使用copy-on-write技术避免snapshot过程影响正常日志同步。成员变更成员变更是在集群运行过程中副本发生变化如增加/减少副本数、节点替换等。成员变更也是一个分布式一致性问题既所有服务器对新成员达成一致。但是成员变更又有其特殊性因为在成员变更的一致性达成的过程中参与投票的进程会发生变化。如果将成员变更当成一般的一致性问题直接向Leader发送成员变更请求Leader复制成员变更日志达成多数派之后提交各服务器提交成员变更日志后从旧成员配置(Cold)切换到新成员配置(Cnew)。因为各个服务器提交成员变更日志的时刻可能不同造成各个服务器从旧成员配置(Cold)切换到新成员配置(Cnew)的时刻不同。成员变更不能影响服务的可用性但是成员变更过程的某一时刻可能出现在Cold和Cnew中同时存在两个不相交的多数派进而可能选出两个Leader形成不同的决议破坏安全性。由于成员变更的这一特殊性成员变更不能当成一般的一致性问题去解决。为了解决这一问题Raft提出了两阶段的成员变更方法。集群先从旧成员配置Cold切换到一个过渡成员配置称为共同一致(joint consensus)共同一致是旧成员配置Cold和新成员配置Cnew的组合Cold U Cnew一旦共同一致Cold U Cnew被提交系统再切换到新成员配置Cnew。Raft两阶段成员变更过程如下:Leader收到成员变更请求从Cold切成Cneweader在本地生成一个新的log entry其内容是Cold∪Cnew代表当前时刻新旧成员配置共存写入本地日志同时将该log entry复制至Cold∪Cnew中的所有副本。在此之后新的日志同步需要保证得到Cold和Cnew两个多数派的确认Follower收到Cold∪Cnew的log entry后更新本地日志并且此时就以该配置作为自己的成员配置如果Cold和Cnew中的两个多数派确认了Cold U Cnew这条日志Leader就提交这条log entry接下来Leader生成一条新的log entry其内容是新成员配置Cnew同样将该log entry写入本地日志同时复制到Follower上Follower收到新成员配置Cnew后将其写入日志并且从此刻起就以该配置作为自己的成员配置并且如果发现自己不在Cnew这个成员配置中会自动退出Leader收到Cnew的多数派确认后表示成员变更成功后续的日志只要得到Cnew多数派确认即可。Leader给客户端回复成员变更执行成功。异常分析:如果Leader的Cold U Cnew尚未推送到FollowerLeader就挂了此后选出的新Leader并不包含这条日志此时新Leader依然使用Cold作为自己的成员配置。如果Leader的Cold U Cnew推送到大部分的Follower后就挂了此后选出的新Leader可能是Cold也可能是Cnew中的某个Follower。如果Leader在推送Cnew配置的过程中挂了那么同样新选出来的Leader可能是Cold也可能是Cnew中的某一个此后客户端继续执行一次改变配置的命令即可。如果大多数的Follower确认了Cnew这个消息后那么接下来即使Leader挂了新选出来的Leader肯定位于Cnew中。两阶段成员变更比较通用且容易理解但是实现比较复杂同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性因此我们期望增强成员变更的限制以简化操作流程。两阶段成员变更之所以分为两个阶段是因为对Cold与Cnew的关系没有做任何假设为了避免Cold和Cnew各自形成不相交的多数派选出两个Leader才引入了两阶段方案。如果增强成员变更的限制假设Cold与Cnew任意的多数派交集不为空这两个成员配置就无法各自形成多数派那么成员变更方案就可能简化为一阶段。那么如何限制Cold与Cnew使之任意的多数派交集不为空呢? 方法就是每次成员变更只允许增加或删除一个成员。可从数学上严格证明只要每次只允许增加或删除一个成员Cold与Cnew不可能形成两个不相交的多数派。一阶段成员变更:成员变更限制每次只能增加或删除一个成员(如果要变更多个成员连续变更多次)。成员变更由Leader发起Cnew得到多数派确认后返回客户端成员变更成功。一次成员变更成功前不允许开始下一次成员变更因此新任Leader在开始提供服务前要将自己本地保存的最新成员配置重新投票形成多数派确认。Leader只要开始同步新成员配置即可开始使用新的成员配置进行日志同步。Raft与Multi-Paxos对比Raft与Multi-Paxos都是基于领导者的一致性算法乍一看有很多地方相同下面总结一下Raft与Multi-Paxos的异同。Raft与Multi-Paxos中相似的概念:Raft与Multi-Paxos的不同:整理好的Java面试资料推荐阅读下载最全的java面试题库Java核心知识点整理
