天津都有哪些制作网站,网站建设完整步骤,建网站兴田德润,网站制作需要多少钱?前言 相关系列
《分布式 目录》《分布式 Raft算法 总结》《分布式 Raft算法 问题》 参考文献
《Raft一致性算法论文译文》《深入剖析共识性算法 Raft》
简介 Raft 木筏是一种基于日志复制实现的分布式容错一致性算法。在Raft算法…前言 相关系列
《分布式 目录》《分布式 Raft算法 总结》《分布式 Raft算法 问题》 参考文献
《Raft一致性算法论文译文》《深入剖析共识性算法 Raft》
简介 Raft 木筏是一种基于日志复制实现的分布式容错一致性算法。在Raft算法之前Paxos 帕克索斯算法一直是分布式容错一致性算法的标准代表。但Paxos算法的缺点也是十分明显的即难以理解实现。而Raft算法的设计目标便是为了简化Paxos算法使得分布式容错一致性算法能够以更加简洁易懂的方式呈现在开发者的面前。 容错性一致性 保证分布式一致性是Raft算法的核心诉求。什么是分布式一致性呢在分布式系统的CAP理论中所谓一致性是指系统中的所有节点在同一时间可以看到相同的数据/状态。这个数据/状态是一个比较抽象的概念但我们可以这样理解对于一个在所有节点中都存在的任意变量而言如果在同一时刻其各个副本值都是相同的那么就说明该分布式系统实现了一致性并且是强一致性。 那什么是容错性呢在CAP理论中容错性的全称是分区容错性是特指在发生“网络分区”而导致部分节点不可用的情况下分布式系统依然可对外提供服务的特性。而又因为Raft算法的核心追求的是一致性因此这个概念就自然转变为了在发生网络分区的情况下依然可对外提供强一致性服务。Raft算法通过允许部分节点不一致的方式实现了这一点即从原本对一致性的完全追求转变为了多数追求。从而使得只要半数/自定义数量以上的节点达成了一致那么分布式系统就会允许流程完整执行以提供服务。在这种设计下分布式系统最多可以允许 半数/自定义数量的节点不可用。 状态机复制状态机 State Machines 状态机是无实物的抽象概念用于描述系统/服务在生命周期内的各类状态例如各变量在某时刻的值及变化例如各变量值在某时段内的变化。在Raft算法中每个节点都存在相应的状态变化因此每个节点都可以视为/拥有状态机。状态机会通过一系列的变量来保存状态并且变量只能通过外部指令来改变。这些指令在被节点接收后会被顺序地记录在日志中随后再被“逐条/串行”地执行/应用到状态机中。 Raft算法通过Replicated State Machines 复制状态机来达成一致性。复制状态机的本质其实就是主从同步/复制即只要确保主状态机的数据/状态能够完整顺序地复制到从状态机上那么就能够保证主/从状态机达成一致。而由于状态机保存了节点所有的状态/数据变量因此状态机一致就等价于数据达成了一致。复制状态机还为Raft算法实现容错性提供了基础即即使部分状态机因为各类原因例如网络分局未能及时达成一致但Raft算法也可基于多数判定的方式强制认定其已达成一致从而实现容错性。 Raft算法基于复制日志实现复制状态机。如上图所示分布式系统的主节点会先通过一致性模块接收客户端请求/指令随后将之追加/复制到自身日志/从节点中。这里需要注意的是指令的日志追加节点复制是并发执行的因此想要保证指令在各个节点上的完整顺序需要通过一些机制来保证该知识点会在下文讲解日志复制时详述。此处只需知道的是Raft算法会保证日志/指令复制的完整顺序性即使部分节点暂时不可用也是如此。而一旦日志被正确复制那么各节点的依次执行/引用就必然会使得各状态机达成一致。
基础 Raft算法将容错一致性问题分解成了三个子问题领导者选举日志复制安全性。 角色 在Raft算法中分布式系统的节点在任何时间都处于以下三个角色之一
Leader 领导者负责接收封装客户端请求/指令并将之正确复制到跟随者中。一个分布式系统通常只有一个领导者而该领导者也需要持续向跟随者发送心跳信息以防止其转变为候选者并成为新领导者Follower 跟随者负责接收领导者候选者发送的请求并给予相应的回应从而参与领导者选举日志复制等流程Candidate 候选者负责在无领导者时竞选升级为新领导者由超过指定时间未收到领导者心跳消息的跟随者转变而来。 任期 Term 任期是领导者从任职到离职的完整时段。所谓任职是指领导者从选举到对分布式系统的管理期间而所谓离职则是指领导者由于各项原因而不可用的情况。当跟随者在指定时间内未能接收到来自领导者的心跳消息时其会自增自身的任期编号以开启新任期而转变为候选者并同步开启选举以试图将自身晋升为领导者。因此虽说所有节点都维护有各自的任期但分布式系统的整体任期却由最终选举胜出的领导者决定。而在领导者确定之后其它跟随者/候选者的任期则会随接收到的心跳信息而与之达成一致直至当前领导再度由于各类原因而不可用。因此在Raft算法中分布式系统的整个生命周期是由一个个任期组成的而Raft算法也会保证在一个给定的任期内最多只有一个领导者。但注意任期最多只有一个领导者并不代表其必然存在领导者因为多候选者的并发选举可能会出现无领导者胜出的情况。这种情况下个候选者便会再度递增任期编号以重新开始选举…该知识点会在下文讲解选举时详述。 任期在Raft算法中充当了逻辑时钟的作用使得节点可以查明一些过往信息例如旧领导者。此外由于节点间的各类通讯都会携带自身的任期编号因此消息的接收者可能出现/执行以下三类情况/操作
如果某节点的任期编号小于领导者的任期编号那么它会随心跳消息更新自己的任期编号到较大值如果候选者旧领导者发现自身的任期编号已过期那么它会立即转变为跟随者如果某节点接收到的请求中包含小于自身的任期编号那么它会直接拒绝这个请求。 RPC Raft算法中的节点间使用RPC 远程过程调用进行通信。基本的一致性算法只需要两种RPC
RequestVote RPC 请求投票RPC由候选者在开启选举时向所有跟随者发起目的是获取选票以令自身成为领导者AppendEntries RPC 附加条目RPC由领导者向所有跟随者发起用于发送日志心跳消息。
选举 规则 Raft算法使用心跳机制来触发领导者的选举。在Raft算法中领导者需要周期性地向所有跟随者发送心跳消息来维持自身权威即阻止新领导者的产生。每个跟随者都随机设置了竞选超时时间一般为150ms ~ 300ms。如果在竞选超时时间内没有收到领导者的心跳消息那么跟随者就会认为当前任期没有可用的领导者而发起选举目的是令自身成为新领导者。 在一次选举过程中跟随者会先增加自己的任期编号并转换为候选者随后携带任期编号向所有其它节点广播请求投票RPC直至发生以下三种情况
自身成为领导者当候选者基于当前任期编号获取到半数以上的节点选票时它就赢得了此次选举并成为了新领导者此时其会向其它所有节点发送心跳消息来阻止新领导者的产生。每个节点对于一个任期最多只能投出一张选票通常会按照先到先得的原则进行选择但也可能因为收到的任期编号较小而拒绝投票。要求半数以上选票的规则确保了最多只会有一个候选者能够赢得选举其它候选者成为领导者在等待投票期间候选者可能会收到新领导者的条目追加RPC。在这种情况下当前候选者会判断该领导者的任期编号是否 自身任期编号是则承认其为新领导并转换为追随者否则拒绝该请求并继续保持选举状态无领导者产生选举的发起往往是并发的因为未接收到心跳消息而转变为候选者的跟随者可能不止一个。而由于这些候选者又都会向其它节点广播请求投票RPC因此瓜分就可能导致没有任何候选者获得半数以上票数的情况发生并进一步造成选举超时而无新领导者产生的情况。在这种情况下候选者虽然会再次增长任期编号来开启新选举但是在没有相关机制来特意避免的情况下选票可能会被无限的重复瓜分。 Raft算法使用随机选举超时时间的方法来缓解选票瓜分的情况。为了减少选票被瓜分的情况Raft算法将跟随者等待心跳消息的超时时间设定为了随机值即在一个固定的区间例如150 ~ 300毫秒内随机选择这样就可以分散候选者发起选举的请求时机从而减少选票被集中瓜分的情况。 因此在正常情况下当有其它候选者并发发起选举时最初的候选者往往已成功获得半数选票而成为新领导者。 随机超时机制还被用在了等待选票的场景中即各候选者等待投票超时的时间也是不同的因此其重新发起选举的时间也是不同的这同样有助于避免下轮的选举并发/选票瓜分。 单候选者选举 分布式系统的最初阶段只有跟随者而没有领导者。跟随者A在等待心跳消息超时后会将自身任期编号由0增加为1从而转变为候选者以发起选举请求。 候选者A向所有其他节点广播请求投票RPC。 其它节点在收到请求投票RPC后会根据“任期编号的大小/先到先得”的规则给予投票回复如果候选者A获得了半数以上的节点选票那么其便会自动转变为领导者。 成为领导者后的节点A会周期性地向哥跟随者广播心跳信息而跟随者接收到心跳信息后则会重置计时以阻止自身转变为候选者。 多候选者选举 如果有多个跟随者因为等待超时而成为候选者并且在并发开启选举后因为票数瓜分而导致未获得半数以上的选票那么这些候选者就会在此递增自身任期编号以开启选举。例如下图中候选者B/D都发起了任期编号为4的选举并且因为各自只获得了两张选票而重新发起了请求投票RPC。 当重新开始投票时由于每候选者节点设置的随机竞选超时时间不同因此能下次再出现多个候选者并获得同样票数的概率就很低了。 日志复制 格式 日志由log entry 日志条目组成。日志条目的本质是领导者对客户请求的封装主要包含了log index 日志索引/领导者任期编号执行指令三个部分这其中日志索引用于“准确”定位日志条目在日志中的位置。当某日志条目被成功复制到半数以上的节点时领导者会判定众跟随者已对该日志条目达成共识因此该日志条目便可以被Commit 提交了即其内部包含的指令可以被正式执行/应用至状态机了。 Raft算法通过日志索引来保证日志的正确复制因为日志复制具备以下两个特性
唯一性如果不同节点日志中的两个日志条目拥有相同的日志索引任期编号那么它们所存储的指令必然是相同的。因为领导者在指定任期编号的指定日志索引上只能创建一个日志条目并且日志条目在日志中的位置也不会发生变化全局性如果不同节点日志中的两个日志条目拥有相同的日志索引任期编号那么它们之前的日志条目必然完全相同。因为领导者再将新日志条目复制到各跟随者上时会携带上个日志条目的任期编号日志索引而如果某跟随者的日志并无法与之达成匹配即不存在上个日志条目那么新日志条目是无法被成功复制到该跟随者中的该行为在Raft算法中被称为一致性检查。 流程 领导者接收封装客户端的请求为日志条目 并将日志条目加入自身日志中领导者向各跟随者发送条目追加RPC以复制当前日志条目各跟随者在通过一致性检查后将当前日志条目追加至自身日志中并返回成功回应。而领导者在接收到半数以上的成功回应后判定各跟随者一堆当前日志条目达成共识因此正式提交/执行当前日志条目/指令以修改状态机并向客户端返回请求的执行结果在领导者后续发送的心跳信息中其会通知各跟随者提交当前日志条目以修改状态机从而令各节点的状态机都达成一致。 注意如果某跟随者因为各项原因而未能给予回应/给予失败回应那么领导者就会重复对其发送条目追加RPC直至其成功复制所有日志条目为止即使领导者已经对客户端回应了当前日志条目的执行结果也是如此。 下文展示整个日志复制的完整动态流程 领导者接收封装客户端的请求为日志条目 并将日志条目加入自身日志中。 领导者向各跟随者发送条目追加RPC以复制当前日志条目。 各跟随者在通过一致性检查后将当前日志条目追加至自身日志中并返回成功回应。而领导者在接收到半数以上的成功回应后判定各跟随者一堆当前日志条目达成共识因此正式提交/执行当前日志条目/指令以修改状态机并向客户端返回请求的执行结果。 在领导者后续发送的心跳信息中其会通知各跟随者提交当前日志条目以修改状态机从而令各节点的状态机都达成一致。 一致性 一致性检查的存在保证了跟随者必然会完整顺序的复制日志只是会在时机上有所延迟因此在正常情况下领导者跟随者的日志最终应当是一致的即使部分跟随者暂时宕机也是如此因为其恢复运行后依然会因为领导者的持续通讯而达成同步。但遗憾的是这并不意味着两者的日志必然会绝对一致因为如果发生旧领导者宕机/网络分区等情况而导致有新领导者诞生那么新领导者的日志就未必与跟随者旧领导者一致了…不一致的情况具体如下 跟随者旧领导者缺少新领导者拥有的日志条目ab这种情况的产生源于新领导者对旧领导者日志的复制进度大于其它跟随者并且这种情况无法像正常情况一样直接通过重复通讯来处理因为新领导者在作为跟随者期间并不与其它跟随者进行通讯故而其并不知道其它跟随者的复制进度因此也就无法得知即使应当增量复制的日志起点跟随者旧领导者拥有新领导者缺少的日志条目cd这种情况的产生源于新领导者对旧领导者的复制进度 其它跟随者并且中途还可能掺杂了其它新领导者的存在例如上图跟随者d的日志就符合这样的情况。对于当前日期编号为8的新领导者任期编号为6的旧领导者而言跟随者d显然在短期内担任过任期编号为7的领导者并接收封装了部分日志条目只不过该领导者很快就因为宕机等原因被任期编号为8的更新领导者给替代了以上两者皆存在ef这种情况就相对复杂这里以上图的跟随者f为例其可能会以这样的场景发生跟随者f在任期编号为1的旧领导者宕机后成为了任期编号为2的新领导者并接收封装了部分日志条目然后又宕机并很快恢复成为任期编号为3的新领导者并在接收封装了部分日志条目后再次宕机且始终未曾恢复… Raft算法通过“日志覆盖”来处理日志不一致问题。我们已知的是新领导者的产生会对旧领导者的日志复制造成干扰并大概率会破坏领导者跟随者日志的最终一致性。而在这种情况下新领导者则会采用“日志覆盖”的方式来处理该问题即使用新领导者的日志来覆盖各跟随者的日志以使之达成一致。为了做到这一点新领导者必须找到两者最后达成一致的日志条目然后删除跟随者该位置之后所有日志条目最后再发送该位置之后所有日志条目给跟随者。 领导者会为所有跟随者维护nextIndex 下个索引用于记录下个需要发送至该跟随者的日志条目的所在位置。当新领导者刚诞生的时候他会初始化所有“下个索引”为自己的最后一条日志条目的索引 1即上图中的11。而在跟随者领导者日志不一致的情况下领导者对其条目追加RPC必然是失败的由此领导者就会减小“下个索引”并进行重试直至找到相同的日志条目/无日志条目为止。而当这种情况发生时领导者的条目追加RPC就会促使跟随者在相应位置删除后续所有的原有日志条目并追加新日志条目以完成覆盖以支持后续运行的持续正常追加。
安全性 安全性是令所有节点按相同顺序执行相同指令以保证状态机一致的特性。在上文中我们虽然已经讲述了领导者选举日志复制的相关内容但直至目前为止关于安全性依然是无法保证的因为各节点依然可能执行不同的指令。例如对于一个拥有新领导者缺失日志条目的跟随者来说虽然其日志最终会被新领导者日志覆盖而达成一致但在正式覆盖前这些被新领导者缺失的指令就可能已经被提交/执行了… Raft算法通过Leader Completeness Property 领导者完整性来保障状态机安全性。所谓领导者完整性是指对于任何指定任期编号的领导者而言其都必然拥有旧任期的所有“已提交”日志条目。而只要领导者的日志是完整的那么状态机的安全性就自然得以保证了因为在各跟随者上已提交的日志条目必然也存在于领导者上。此外Raft算法还要求节点按顺序应用/执行日志条目。因此和状态机安全性结合起来看这就意味着所有的节点都会按相同的顺序应用相同的日志序列集到自己的状态机中。 选举限制 Raft算法通过在领导者选举时添加限制来保证领导者完整性。任何存在领导者身份/机制的一致性算法都要求领导者必须存有所有已提交的日志条目因为只有这样才能保证跟随者执行与“新”领导者完全相同的指令即保证状态机安全性。以Viewstamped Replication算法为例其虽然允许在选举过程中令未完整包含已提交日志条目的候选者成为领导者但在这之后也会有相应的机制从各跟随者中识别出这部分缺失的日志并补充至新领导者。不过由于这种方法会导致算法的复杂度大幅增加因此Raft算法选择采用更加简单的方式处理这一点即直接在选举时令拥有完整日志的候选者成为领导者从而略去后续繁复的日志识别传输机制使得Raft算法的日志复制只有领导者至跟随者的单向传输。 Raft算法通过拒绝投票来阻止候选者赢得选举。请求投票RPC存在这样的限制如果候选者的日志没有请求的目标节点“新”那么目标节点就会拒绝向该候选者投出选票从而阻止日志不完整的候选者成为领导者。该机制的原理在于候选者必须获得大部分节点选票才能引得选举而已提交的日志条目至少会存在于其中一个节点上因为日志条目提交的前提是其已被复制到大部分节点上。而只要这个具有已提交日志条目的节点能够正常投票那么就说明当前候选者的日志足够即完整包含了所有已提交日志条目因此可以正式成为领导者否则候选人是无法收集到足够用数量的选票的…关于日志“新”的概念如下
如果两份日志的最后条目的任期编号相同那么长度更长的那个日志更新如果两份日志的最后条目的任期编号不同那么任期编号更大的日志更新后续有详解。 论证 我们以假设领导者不存在完整性并将之推翻的方式来证明安全性。假设任期T的领导者在任期内提交了某日志条目但该条日志条目并未被复制到未来某个任期的领导者日志中即设任期编号大于T的领导者U没有这条日志条目。 假设领导者U在选举时不包含指定的已提交日志条目由于该已提交日志条目必然已被领导者T复制到了系统中的大多数节点上而领导者U又必须获得系统中的大多数节点的选票才能赢得选举因此这些节点中至少有一个下文简称投票者例如上图中的S3即接收了领导者T的日志条目又为给领导者U提供了选票。而这个投票者就是领导者U能否在成为新领导者的同时拥有所有已提交日志条目的关键投票者接收已提交日志条目的时间必然在给领导者U投票之前因为其任期编号会因为接收了领导者U的请求投票RPC而与之等同而这就会导致其拒绝领导者T的条目追加RPC因为投票者的任期编号已 领导者T的任期编号投票者在给领导者U投票时会持续存有这条日志条目因为任何中间领导者即与领导者U并发选举并先一步成为领导者的节点都包含该日志条目如果投票者要把选票投给领导者U那就要求领导者U的日志至少要和投票者一样新即要么两者最后一条日志条目的任期编号相同且领导者U的日志长度 投票者要么领导者U最后一条日志条目的任期编号 投票者。对于前者而言领导者U是必然包含指定已提交日志条目的因为日志的匹配特性保证了这一点而对于后者而言情况则相对要难以理解一些。首先我们要知道的是这最后一条任期编号 投票者的日志条目不可能由领导者U自己接收封装而来因为此时其还在等待投票者的选票以成为正式的领导者。因此如果该日志条目真的存在那么其只能是由中间领导者产生复制而来的。但对于这些中间领导者而言其实际面临着与领导者U相同的局面即自身的日志要够新才能成为领导者因此领导者T后的首个新领导者必然是因为前种情况赢得的选举也因此后种情况其实是基于前种情况才可能存在的。故而如果领导者U是因为后种情况而赢得的选举那么其必然就会存在指定的已提交日志条目因为日志匹配原则保证了中间领导者只有在已复制指定已提交日志条目的情况下才能复制新接收封装的日志条目。因此任期编号比T大的领导者一定包含了所有任期T的已提交日志条目。 提交旧任期的日志条目 旧任期的日志条目可能在新任期中达成提交条件。领导者完整性并不保证新领导者拥有旧任期中未提交的日志条目这是非常合理的设计因为未提交就意味着这些日志条目未曾被应用至状态机中因此即使被新领导者的日志覆盖也不会破坏安全性。但需要注意的的是由于实际场景的复杂性未提交的旧日志条目可能会在新领导者产生后覆盖前达成提交条件而在这种情况下Raft算法就需要合理地提交这些旧日志条目。为什么要特别强调“合理”呢这是因为如果新领导者按常规计算副本数目的方式来直接提交这些旧副本条目那么就可能导致领导者完整性被破坏的情况发生…具体场景如下 上图的时间序列展示了为什么新领导者不能直接提交旧日志条目。
(a) – S1是任期2的领导者并向S1复制了日志条目2(b) – S1崩溃S5在任期3中通过S3S4S5的选票赢得选举并从客户端接收封装了日志条目3放在索引2处© – S5崩溃S1重新启动在任期4中赢得选举并从客户端接收封装了日志条目4放在索引3处。随后继续日志复制并把任期2的日志条目成功复制到S2S3节点随后按常规方式进行了直接提交(d) – S1崩溃S5重新启动在任期5图中未展示因为没有接收封装新的日志条目中通过S2S3S4的选票赢得选举并覆盖了其它节点在索引2后的日志从而出现已经被复制到大多数节点上日志条目被新领导者覆盖的情况。对于这种情况而言如果日志条目2尚未提交那么覆盖便不会造成异常影响。但如果已经提交那么就会出现破坏状态机安全性的情况(e) – 假设S1崩溃前已将日志条目4复制到大多数节点那么在后续任期中这些新日志条目就会被成功提交因为S5无法选举成功。 这样就同时保证了新旧日志条目的整体提交。 Raft算法会通过直接提交新任期日志条目的方式来间接提交旧日志条目。如在上图中的情况e所示如果领导者S1在任期4时不直接递交日志条目2而是等到后续达成条件时直接提交日志条目4那么就能在避免违法覆盖的同时间接提交日志条目2。这是因为日志具有匹配性因此日志条目4被提交就相当于上游的所有日志条目也被提交了。诚然这种做法会导致本可以立即提交的旧日志条目被延后乃至无法提交但相对比破坏状态机安全性这种情况而言显然是可以被接收的。此外关于这一点也并非不能优化例如领导者可以直接提交一条空指令的新日志条目来快速完整这一点…甚至无需先复制。 时间和可用性 Raft算法的安全性不能依赖时间即整个系统不能因为某些事件运行的比预期快/慢就产生错误的结果。遗憾的是可用性系统可以及时的响应客户端会不可避免的依赖于时间例如如果消息交互时间 节点故障间隔时间那么候选者将没有足够长的时间来赢得选举而没有一个稳定领导者的Raft算法是无法正常工作的。领导者选举是Raft算法对时间要求最为关键的方面为了选举并维持一个稳定的领导者系统需要满足以下时间要求
broadcastTime 广播时间 electionTimeout 选举超时时间 MTBF 平均故障间隔时间 在上述不等式中广播时间具体指节点向系统中其它节点并行发送RPC并接收响应的平均时间而选举超时时间则是上文所说的候选者可等待选票的最长时间而平均故障间隔时间则是指一个节点两次故障间的平均时间。广播时间必须比选举超时时间小一个量级因此只有这样领导者才能够发送稳定的心跳消息来阻止跟随者成为候选者。而通过随机化选举超时时间的方法这个不等式也可使选票瓜分的情况变得近乎不可能。此外选举超时时间还应该要比平均故障间隔时间小上多个量级这样整个系统才能稳定的运行。毕竟当领导者崩溃后整个系统会在大约相当于选举超时的时间里不可用…虽说这种情况通常是很少见的。 广播时间平均故障间隔时间由系统自行决定但选举超时时间则是人为决定的。Raft算法的节点需要将接收到的RPC信息持久化保存因此广播时间通常会在0.5 ~ 20毫秒左右这具体与存储硬件有关故而选举超时时间则通常在10 ~ 500毫秒之间。而大多数节点的平均故障间隔时间通常都为几个月甚至更长因此很容易满足时间的需求。
日志压缩 日志不可能在现实情况中无限增长。Raft算法的日志会随程序的持续运行而无限增长但在现实场景中这显然是不允许的因为无限增长的日志不但会占用大量的磁盘空间还会导致节点重启时需要花费大量时间重演指令序列来还原状态机。因此如果没有相应的机制来对日志进行缩容那么Raft算法就会存在很严重的可用性问题。 Raft算法采用快照来压缩日志。快照是现实中最简单常用的数据压缩方式系统可以将某个时间点的状态机以快照的形式持久化储存从而便可将该时间点前的日志全部丢弃。这么做不但大幅缩减了磁盘的使用空间还有助于状态机的快速还原因为快照作为二进制文件加载速度是非常快的。快照技术被广泛引用在Chubby/ZooKeeper/Redis等各类程序中而Raft算法也同样如此。 快照只包含已提交日志条目的内容。Raft快照用于保存状态机某个时间点的状态具体表现为将该时间点前的所有已提交日志条目的内容经过筛选去重等过滤手段后保存。因为只有已提交的日志条目才会被应用到状态机中并且这些日志条目的内容还可能存在覆盖等情况。而除此以外Raft算法日志还包含了一些必要的元数据例如用于进行一致性检查的最后包含日志条目索引任期…具体可参考上图所示样例。而一旦节点完成了对相应时间点的快照创建那么对应的日志条目序列段就可以被全部删除了。 Raft算法允许各节点独立创建快照。这种快照创建方式本质上背离了Raft算法的强领导者原则因为跟随者可以在与领导者完全解耦的情况下创建快照。但Raft算法的设计者认为这种背离是值得的因为领导者的存在本意是为了解决一致性达成过程中的冲突但是在各节点创建快照期间一致性是已经达成的因此没有领导者也是完全可以。此外快照创建的独立性并没有改变数据来源依然是领导者的本质跟随者只不过是可以重新组织自身数据的结构而已。 在创建快照的过程中有两个问题会对性能造成较大影响一是快照的生成频率二是生成期间对正常流程的阻塞。对于前者各节点必须自行决定快照的创建时机频率过高会浪费大量的磁盘带宽和其他资源而过低又会有耗尽磁盘空间的风险还会增加日志重建的时间。对此一个简单的策略是当日志大小达到固定大小再触发创建快照因为只要该阈值显著大于快照的期望大小那么快照对磁盘压力的影响就很小了。而对于后者可以采用COW 写时拷贝技术进行处理这样节点就可以在创建快照的同步不阻塞正常流程了并且操作系统自带写时拷贝功能也可以很轻松地支持实现这一点。 Raft算法的设计者考虑过一种基于领导者的快照方案即只由领导者创建快照并发送给各跟随者。但是这样做有两个缺点一是发送快照会浪费网络带宽并延缓快照处理的时间毕竟每个跟随者都拥有创建快照的所需条件而直接从本地状态中创建快照显然要比通过网络接收要更加经济二是领导者的实现会更加复杂例如领导者需要在发送快照的同时并行复制日志这样才不会阻塞新的客户端请求。 领导者可能会向跟随者发送快照。虽说领导者是通过日志复制的方式向跟随者发送数据的但在某些情况下其也会通过发送日志的方式来同步数据。因为对于运行非常缓慢/新加入系统的节点而言领导者可能已经因为成功生成快照而删除了对应发送的日志条目那么在这种情况下领导者便只能通过发送快照的方式来进行弥补了。领导者会使用一种名为“安装快照”的新RPC来发送快照给同步进度过于落后的跟随者而当跟随者通过安装快照RPC接收到快照时它需要根据自身的日志复制情况来决定如何使用这份快照。一般来说快照中的数据量一般是 跟随者本身日志所包含的数据量的这种情况下跟随者就会全量删除自身以直接采纳快照而如果因为网络重传/错误出现了少见的快照数据量 跟随者日志数据量的情况那么跟随者便会删除快照包含部分的日志但不包含的的部分日志则会继续保留。
客户端交互 Raft算法通过“重定向”找到实际领导者。当客户端启动时其会在系统中随机挑选节点来进行首次通信。如果客户端首次挑选/请求的不是领导者那么该节点便会拒绝客户端请求并提供其最近接收到的条目追加RPC中携带的领导者信息从而令客户端可以重定向至领导者。而如果该领导者实际已经宕机了那么客户端的重定向请求就会因为超时而失败从而再次重试随机挑选节点的过程。 Raft算法通过幂等间接实现了线性化语义。Raft算法设计者的本意是要直接实现线性化语义即每个客户端请求都会立即执行且在其请求回应之间只执行一次实际操作。但现实情况是Raft算法依然可能会不可避免地在一次请求中将一条指令执行多次…例如如果领导者在提交了某日志条目后还未响应客户端前就崩溃了那么客户端和新领导者就会重试这条指令而导致再次执行。该问题的常规解决方案是客户端对于每条指令都赋予唯一的序列号随后状态机记录每条指令的序列号响应。当领导者接收到一条指令时如果它的序列号显示已经被执行了那么就领导者就会立即返回结果而不执行正常流程。 读操作可不记录于日志。对于不会影响状态机的读操作而言其理论上可以直接处理而不记录于日志。但是在不增加任何限制的情况下这么做可能会有返回脏数据的风险因为响应客户端请求的领导者可能在自身未知的情况下经被新领导者取代而新领导者则可能返回截然不同的结果。由于线性化的读操作并不允许返回脏数据因此Raft算法需要添加两个额外措施来在不使用日志的情况下保证这一点
领导者在执行读操作时必须检查自己是否已被废黜Raft算法通过让领导者在执行指令后响应请求前先和系统中的大多数节点通讯来处理这个问题。如果在通讯后发现有新的领导者存在那么就需要由新领导者重新执行该读指令刚上任的领导者需要提交一条空白指令的日志条目以达成已有日志条目的全量提交因为这时的领导者可能含有可提交的旧任期日志条目这保证了读指令执行的正确性。
