一个网站的欢迎页怎样做,企业网站做的好,南京市高淳区住房与城乡建设局网站,镇江网站制作咨询1 介绍
分布式一致性共识算法指的是在分布式系统中#xff0c;使得所有节点对同一份数据的认知能够达成共识的算法。且算法允许所有节点像一个整体一样工作#xff0c;即使其中一些节点出现故障也能够继续工作。之前的大部分一致性算法实现都是基于Paxos#xff0c;但Paxos…1 介绍
分布式一致性共识算法指的是在分布式系统中使得所有节点对同一份数据的认知能够达成共识的算法。且算法允许所有节点像一个整体一样工作即使其中一些节点出现故障也能够继续工作。之前的大部分一致性算法实现都是基于Paxos但Paxos难以理解和实现为此作者开始寻找一种新的易于理解的一致性算法Raft则是作者工作的产出。
在设计Raft的过程中作者采用了一系列策略来增强其可理解性包括
算法分解Raft将核心功能模块化分离出领导人选举、日志复制和安全性三个关键部分使每个部分的逻辑更加清晰。状态空间缩减相比于PaxosRaft减少了不确定性和服务器间的不一致性状态简化了状态机模型从而降低了理解和实现的难度。
Raft 算法在许多方面和现有的一致性算法都很相似但是它也有一些特性
强领导人机制Raft采用了更强的领导人角色所有日志条目仅由领导人发送给其他服务器这种集中控制方式简化了日志管理增强了算法的直观性。领导人选举Raft使用随机计时器来触发领导人选举这种机制在心跳机制的基础上增加了少许复杂性但有效地解决了选举冲突实现了快速而简单的决策过程。成员关系调整Raft 使用一种联合共识的方法来处理集群成员变换的问题在这种方法下处于调整过程中的两种不同的配置集群中大多数机器会有重叠这就使得集群在成员变换的时候依然可以继续工作。
2 复制状态机
复制状态机是共识算法的核心应用背景它是指一组服务器上的状态机生成相同状态的副本即使部分服务器宕机也能持续运行。这种架构在大规模分布式系统中尤其重要因为它能够解决一系列容错问题。例如大规模的系统中通常都有一个集群领导人像 GFS、HDFS 和 RAMCloud典型应用就是一个独立的复制状态机去管理领导人选举和存储配置信息并且在领导人宕机的情况下也要存活下来。比如 Chubby 和 ZooKeeper。
复制状态机通常都是基于复制日志实现的如图 1。每个服务器存储一个包含一系列指令的日志并且按照日志的顺序进行执行。所有日志都包含相同的指令序列确保状态机一致因为每个状态机都是确定的每一次执行操作都产生相同的状态和同样的序列。 一致性算法的任务是保证复制日志的一致性。服务器上的一致性模块接收客户端发送的指令然后添加到自己的日志中。它和其他服务器上的一致性模块进行通信来保证每一个服务器上的日志最终都以相同的顺序包含相同的请求即使有些服务器发生故障。一旦指令被正确的复制每一个服务器的状态机按照日志顺序处理他们然后输出结果被返回给客户端。因此服务器集群看起来形成了一个高可靠的状态机。
实际系统中使用的一致性算法主要有以下特性
安全性保证绝对不会返回一个错误的结果。即使部分服务器失败只要多数服务器运行系统依然可用。不依赖于时序能够应对时钟错误和消息延迟。大多数情况下指令可以在一轮远程过程调用后完成不受少数慢节点影响。
3 Paxos的问题 Paxos极其难以理解。 没有为构建实际系统实现提供良好的基础。
4 为了可理解性的设计
设计Raft算法的初衷 必须提供一个完整的实际的系统实现基础减少开发者工作量 必须在任何情况下都是安全的并且在大多数的情况下都是可用的 它的大部分操作必须是高效的 可理解性它必须保证对于普遍的人群都可以十分容易的去理解 便于系统构建者形成直观理解便于实际应用和扩展
Raft设计原则 问题分解将复杂问题拆解为独立、易于理解和解决的子问题。例如Raft 的领导人选举、日志复制、安全性和成员变更。 状态空间简化减少状态数量降低系统复杂性并在可能的时候消除不确定性。确保日志无空洞限制日志不一致的可能性。 随机化应用在领导人选举中使用随机化简化机制快速解决冲突。
5 Raft一致性算法
Raft 是一种管理复制日志的一致性算法通过选举领导人并由其管理日志来实现一致性。领导人从客户端接收日志条目把日志条目复制到其他服务器上并告诉其他的服务器什么时候可以安全地将日志条目应用到他们的状态机中。这一决策过程无需与其他服务器进行商议从而简化了整个复制日志的管理流程并且数据都从领导人流向其他服务器。一个领导人可能会发生故障或者和其他服务器失去连接在这种情况下一个新的领导人会被选举出来。
Raft算法的一致性问题被巧妙地分解为三个关键子问题
领导选举当领导人发生故障的时候, 一个新的领导人需要被选举出来确保系统的连续性和稳定性5.2日志复制领导人必须从客户端接收日志条目然后复制到集群中的其他节点并强制要求其他节点的日志和自己保持一致。安全性Raft通过特定的机制5.4确保一旦日志条目被应用到某个服务器的状态机中其他服务器不会在同一日志索引位置应用不同的指令从而保障了系统状态的一致性和安全性。
5.1 Raft基础
一个 Raft 集群由若干个服务器节点构成如常见的 5 节点配置能容忍最多 2 个节点失效。节点有以下三种状态 领导人唯一决策者处理所有客户端请求并且管理复制日志。 跟随者被动角色仅响应领导人和候选人的请求。 候选人竞选状态用于选举新领导人
跟随者在收不到消息时升级为候选人启动选举获得多数票的候选人成为领导人领导人宕机或发现任期过期降级为跟随者。
Raft 通过任期来划分时间每个任期都始于一次选举。任期用整数标记每段任期有其选举过程。如果选举成功选出的领导人将负责管理集群直到该任期结束。任期在Raft中充当逻辑时钟的作用帮助节点检测过期信息如过期的领导人。 每个节点维护一个当前任期号通信时交换任期号节点自动更新至较大值领导人或候选人如果发现任期号过期会恢复为跟随者节点拒绝过期任期请求。
在 Raft 算法中节点间的通信依赖于RPC。基本的一致性算法主要使用两种类型的 RPCs 请求投票RPC候选人发起用于选举。 附加条目RPC领导人发起复制日志和提供心跳机制。 安装快照PRC领导人发起安装快照。为了提高性能服务器在未及时收到响应时会重试 RPC并且能够并行发起 RPC。
5.2 领导人选举
Raft 算法采用心跳机制来触发领导人选举过程。服务器启动时默认处于跟随者状态仅当接收到来自领导人或候选人的有效 RPC 时才保持这一状态。领导人定期向所有跟随者发送心跳包即不含日志项的附加条目RPC以此维护其领导地位。若跟随者在设定的选举超时时间内未收到任何消息它将假定无有效领导人并发起选举以选出新的领导人。
选举流程开始时跟随者增加自己的当前任期号并转换为候选人状态然后向集群中其他服务器节点发送请求投票RPC来给自己投票。候选人保持该状态直至出现以下三种情况之一 赢得选举。 其他服务器成为领导人。 在一定时间内无明确获胜者。
赢得选举的条件是获得集群大多数服务器节点的选票每台服务器对同一任期号的投票遵循先来先服务原则并有额外限制5.4以确保选举安全性避免了脑裂同一人气集群出现两个领导人。一旦当选候选人即刻转变为领导人通过发送心跳消息确立领导地位并阻止发起新选举。
在等待投票的过程中候选人可能接收到领导人发送的附加条目RPC如果该领导人任期号不低于候选人的任期号候选人将认可其合法性回归跟随者状态反之候选人将拒绝RPC继续竞选。若多个候选人同时发起选举选票分散可能导致无人胜出所有候选人均会因超时而重新开始选举但任期号会递增。
为防止选票分散Raft算法引入了随机化选举超时时间策略。各服务器在固定时间范围内例如 [ 150 , 200 ] [150,200] [150,200]随机选取超时值使得通常情况下仅有一台服务器超时进而顺利赢得选举并在其他服务器超时前发送心跳。即使发生选票分散随机化的超时机制也降低了下一轮选举中再次分散的可能性。
作者最初设计考虑过引入排名系统以决定优先级但发现这可能导致高排名服务器故障时的可用性问题且算法调整复杂难以确保没有副作用。经过多次调整最终确定随机重试方法更为直观易懂且避免了排名系统带来的复杂性和潜在问题。
5.3 日志复制
一旦选举产生领导人它便开始处理客户端请求每个请求携带一条被复制状态机执行的指令。领导人将此指令作为新日志条目追加至日志中并并行发起附加条目RPC给其他服务器复制日志条目在被安全复制后领导人将其应用到状态机并将执行结果返回给客户端即使面对跟随者崩溃、延迟或网络丢包领导人也会持续重试RPC尽管已经回复了客户端直至所有跟随者存储所有日志条目。
日志结构如下图所示条目按序编号包含创建时的任期号及待执行指令。日志条目在满足一定条件时变为可提交状态即安全地应用到状态机中。领导人决定何时提交日志条目Raft算法保证所有提交条目持久化并最终被执行。日志条目在被复制到多数服务器时即被提交包括前任领导人创建的条目。领导人追踪最大已提交条目索引并在附加条目RPC中包含该索引使跟随者同步应用已提交条目。 Raft的日志机制维持不同服务器日志之间的高层次一致性简化系统行为并增强可预测性是安全性的重要组成部分。关键特性是若两日志条目索引和任期号相同则它们存储相同指令并且前序条目也相同。。这是因为日志匹配特性领导人最多在一个任期内特定索引创建日志条目且日志条目位置固定不变。附加条目RPC包含前一条目的索引和任期号若跟随者找不到匹配条目则拒绝确保日志匹配特性。
正常运行时领导人与跟随者日志一致但在领导人崩溃后可能出现不一致如图7所示。领导人通过强制跟随者复制自己的日志解决不一致覆盖冲突条目。领导人维护nextIndex记录每个跟随者下一个待发送条目索引初始化为自身最后条目索引1。当一致性检查失败领导人就会减小nextIndex直至找到共同点删除跟随者冲突条目并发送自身条目。成功后跟随者日志与领导人保持一直。 算法可优化减少拒绝次数跟随者可返回冲突条目任期号及对应最小索引领导人据此一次性跳过冲突任期所有条目。但实践中这种优化可能非必需因不一致性罕见且涉及条目不多。 通过日志复制机制领导人无需特殊操作即可恢复一致性只需执行常规流程日志在响应一致性检查失败时自动对齐。领导人从不覆盖或删除自身日志确保一致性。日志复制机制体现了高可用性、快速复制及对慢跟随者的容忍度。
5.4 安全性
在 Raft 算法中尽管已经描述了领导人的选举和日志的复制过程但这些机制本身并不足以保证所有状态机按照相同的顺序执行相同的指令。存在一种情况即一个跟随者在领导人提交了若干日志条目后变得不可用之后这个跟随者可能被选举为新的领导人并可能覆盖这些已提交的日志条目导致不同状态机可能执行不同的指令序列。
为了解决这个问题Raft 算法在领导选举时增加了限制确保任何给定任期的领导人都拥有之前任期的所有已提交的日志条目即领导人完整特性。这一限制简化了提交规则并为复制状态机的正确行为提供了证明。
5.4.1 选举限制
在基于领导人的一致性算法中领导人都必须存储所有已提交的日志条目。Raft 算法通过简单的方法确保新选举的领导人拥有之前任期中所有已提交的日志条目避免了额外的日志传输机制和复杂性。
Raft 使用投票机制来阻止未包含所有已提交日志条目的候选人赢得选举。候选人必须获得集群中大多数节点的同意这确保了所有已提交的日志条目至少存在于一个节点上。如果候选人的日志至少和大多数的服务器节点一样新那么他一定持有了所有已经提交的日志条目。请求投票RPC 实现了这样的限制RPC 中包含了候选人的日志信息然后投票人会拒绝掉那些日志没有自己新的投票请求。
Raft通过比较日志中最后一条条目的任期号和索引来判断哪个日志更“新”。
如果任期号不同任期号更大的日志更“新”。如果任期号相同则条目更多索引值更大的日志更“新”。
5.4.2 提交之前任期内的日志条目
领导人在当前任期内创建的日志条目当被复制到大多数服务器上时则可认为是可提交的。如果一个领导人在提交日志条目之前崩溃了未来后续的领导人会继续尝试复制这条日志记录。然而对于之前任期中的日志条目即使它们已经被复制到大多数服务器上也不能简单地通过副本数量来确定它们是否已提交如图8所示。这是因为在领导人崩溃和重新选举的过程中可能会出现新的领导人并不包含所有之前任期的日志条目这可能导致已复制的日志被覆盖。 为了避免这种情况Raft不会通过副本数目去提交一个之前任期内的日志条目只有当前任期的日志条目才能通过复制到大多数服务器来提交。一旦当前任期的日志条目被提交根据日志匹配特性之前任期的日志条目也会被间接的提交。
Raft 在处理日志时保留了原始的任期号这虽然增加了提交规则的复杂性但简化了日志的识别和管理。与其它算法不同Raft 在复制之前任期日志不需要使用新的任期号在提交前不用发送冗余的日志条目来重新编号
5.4.3 安全性论证
在 Raft 算法中领导人完整性特性是确保一致性的关键。这一特性保证了在任期 T 的领导人提交的日志条目必须被存储在未来任期的领导人日志中。
设任期UT的领导人U缺失该条目如下图所示在U的选举中至少存在一个节点如S3同时持有T任期的日志并投票给U。 关键点此节点在投票前接受T任期已提交日志且在投票时仍保存该条目。矛盾一此节点把自己选票投给领导人 U 时说明领导人 U 的日志必须和投票者自己一样新。但假设U不包含T任期提交的日志。矛盾二若U最后日志任期大于此节点则前领导人必含提交日志由日志匹配特性知U亦应含该日志产生矛盾。
故所有大于T任期的领导人必定包含T任期中所有已提交日志条目。日志匹配原则确保未来领导人同样包含间接提交的条目。领导人完整性特性支撑状态机安全特性防止不同日志在相同索引值上被应用。
5.5 追随者和候选人崩溃
崩溃影响崩溃导致后续RPC失败影响通信和一致性。处理机制 无限重试系统通过持续重试RPC来处理这类失败。重启恢复当崩溃服务器重启未完成的RPC能够继续执行至成功。 RPC幂等性保障指多次执行相同操作产生的效果等同于一次执行故重复执行RPC也不会引起不一致或错误状态。
5.6 时间和可用性
Raft 算法的一个核心要求是安全性不应依赖于时间即系统不应因为事件的快慢而产生错误的结果。然而系统的可用性即及时响应客户端的能力不可避免地依赖于时间因素。特别是在领导人选举过程中时间要求尤为关键。
关键的时间因素有
广播时间 (Broadcast Time)服务器向集群成员并行发送RPC并接收响应的平均时间。选举超时时间 (Election Timeout)跟随者等待领导人心跳的最长时限过期则发起选举。平均故障间隔时间 (Mean Time Between Failures, MTBF)服务器两次故障之间的平均时间。
Raft 要求满足以下时间不等式以保证系统正常运行 Broadcast Time ≪ Election Timeout ≪ MTBF \text{Broadcast Time}\ll\text{Election Timeout}\ll\text{MTBF} Broadcast Time≪Election Timeout≪MTBF
广播时间和平均故障间隔时间是由系统决定的但是选举超时时间是我们自己选择的。广播时间受存储技术影响范围约为 [ 0.5 , 20 ] ms [0.5,20]\text{ ms} [0.5,20] ms选举超时时间基于广播时间设置要比广播时间大几个数量级一般在 [ 10 , 500 ] ms [10,500]\text{ ms} [10,500] ms而MTBF通常数月以上远大于选举超时时间满足系统稳定运行需求。
6 集群成员变化
Raft 算法在设计时假设集群配置是固定的但在实际应用中集群配置需要动态调整如替换宕机的机器或改变复制级别。直接更改集群配置存在风险可能导致同一任期内两个领导人同时存在因此需要一种安全的配置变更机制。为了确保配置变更的安全性必须采用两阶段方法。在Raft中集群切换到一个过渡配置称为联合共识结合了新旧配置
日志条目被复制给新旧配置的所有服务器。新旧配置的服务器都可以成为领导人。达成一致选举和提交需要分别在新旧配置上获得大多数支持。
联合共识允许独立的服务器在不影响安全性的前提下在不同的时间进行配置转换过程。此外联合共识可以让集群在配置转换的过程中依然响应客户端的请求。配置变更过程如下图所示 请求接收领导人接收到从 C old C_\text{old} Cold 到 C new C_\text{new} Cnew 的配置变更请求。联合共识日志条目领导人创建 C old,new C_\text{old,new} Cold,new 配置条目并将其作为日志条目存储和复制。提交联合共识一旦 C old,new C_\text{old,new} Cold,new 被提交新旧配置都不能单方面做出决定只有拥有 C old,new C_\text{old,new} Cold,new 日志条目的服务器才能成为领导人。新配置日志条目这个时候领导人创建 C new C_\text{new} Cnew 配置条目并复制给集群最终在 C new C_\text{new} Cnew 规则下提交旧的配置变得无关紧要。
7 日志压缩
Raft 算法通过复制日志来维护一致性但随着时间的推移日志会不断增长占用大量空间并影响性能。为了解决这个问题Raft 使用快照技术压缩日志通过存储系统状态至持久化存储随后丢弃先前日志。
下图展示了快照的基本思想每个服务器独立创建快照只包含已提交的日志条目主要的工作包括将状态机的状态写入快照中。Raft也包含一些少量元数据到快照中最后索引和任期号。保留这些数据是为了支持一致性检查允许服务器清除过期日志。 领导人偶尔也需要通过安装快照RPC将快照分块发送给一些落后的追随者追随者收到快照后他必须自己决定对于已经存在的日志该如何处理一般来说是覆盖冲突日志保留后续未冲突日志。
在快照时有两个性能相关的因素需要考虑
创建时机服务器需要决定何时创建快照以避免频繁写入或存储空间耗尽。Raft 的策略是当日志大小达到一个阈值之后就开始快照。写入时间写入快照可能需要显著时间为了不影响正常的操作应通过写时复制技术避免影响正常操作。
8 客户端交互
Raft中的客户端发送所有请求给领导人。客户端初始化时随机选择服务器非领导人服务器会拒绝客户端请求并提供最近接收到的领导人信息。如果领导人崩溃后客户端请求超时重启随机选择过程直至找到新领导人。
Raft目标是要实现线性化语义由于Raft是可能同时执行同一条命令多次的为了解决这个问题客户端为每条指令分配唯一序列号状态机跟踪每个客户端的最新序列号和相应响应。如果接收到的指令序列号已经被执行状态机直接返回结果而不重新执行。
只读操作可以不写入日志直接处理。但不记录日志可能导致返回脏数据即领导人在不知情的情况下被新领导人取代。线性化的读操作必须不能返回脏数据Raft 需要使用两个额外的措施在不使用日志的情况下保证这一点。 最新提交日志信息领导人需要知道任期内所有被提交的日志条目。Raft 通过让领导人在任期开始时提交一个空白日志条目来实现。 领导人状态检查在处理只读请求前领导人必须检查自己是否已被废黜。Raft 通过让领导人在响应只读请求前与集群大多数节点交换心跳信息来处理这个问题。
9 总结
Raft 是一种用于管理复制日志的一致性算法旨在解决分布式系统中的一致性问题。它通过领导人选举、日志复制和安全性保证来实现系统的高可用性和一致性。
Raft 的五大保证 选举安全性在任一给定任期内最多只能有一个领导人被选举出来。 领导人只追加领导人不会覆盖或删除其日志中的条目它只追加新的条目。 日志匹配如果两个日志在相同索引和任期号处含有相同的条目则在该索引之前的所有条目都是相同的。 领导人完整性如果一个日志条目在给定任期被提交那么该条目将出现在所有更高编号任期的领导人的日志中。 状态机安全性如果一个服务器将某个索引的日志条目应用到其状态机中其他服务器不会对该索引应用不同的日志条目。
