微网站的链接怎么做,哪种语言做网站最快,做网站入什么科目,如何去掉Wordpress访问网站Paxos算法是莱斯利兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。Paxos算法解决的问题是一个分布式系统如何就某个值#xff08;决议#xff09;达成一致。在工程实践意义上来说#xff0c;就是可以通过Paxos实现多副本一致性#xff0c;分布式锁… Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法。Paxos算法解决的问题是一个分布式系统如何就某个值决议达成一致。在工程实践意义上来说就是可以通过Paxos实现多副本一致性分布式锁名字管理序列号分配等。比如在一个分布式数据库系统中如果各节点的初始状态一致每个节点执行相同的操作序列那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。本文首先会讲原始的Paxos算法(Basic Paxos)主要描述二阶段提交过程然后会着重讲Paxos算法的变种(Multi Paxos)它是对Basic Paxos的优化而且更适合工程实践最后我会通过QA的方式给出我在学习Paxos算法中的疑问以及我对这些疑问的理解。 概念与术语 Proposer提议发起者处理客户端请求将客户端的请求发送到集群中以便决定这个值是否可以被批准。 Acceptor提议批准者负责处理接收到的提议他们的回复就是一次投票会存储一些状态来决定是否接收一个值。 replica节点或者副本分布式系统中的一个server一般是一台单独的物理机或者虚拟机同时承担paxos中的提议者和接收者角色。 ProposalId每个提议都有一个编号编号高的提议优先级高。 Paxos InstancePaxos中用来在多个节点之间对同一个值达成一致的过程比如同一个日志序列号logIndex不同的logIndex属于不同的Paxos Instance。 acceptedProposal在一个Paxos Instance内已经接收过的提议 acceptedValue在一个Paxos Instance内已经接收过的提议对应的值。 minProposal在一个Paxos Instance内当前接收的最小提议值会不断更新 Basic-Paxos算法 基于Paxos协议构建的系统只需要系统中超过半数的节点在线且相互通信正常即可正常对外提供服务。它的核心实现Paxos Instance主要包括两个阶段:准备阶段(prepare phase)和提议阶段(accept phase)。如下图所示 1.获取一个ProposalId,为了保证ProposalId递增可以采用时间戳serverId方式生成 2.提议者向所有节点广播prepare(n)请求 3.接收者比较n和minProposal如果nminProposal,表示有更新的提议minProposaln否则将(acceptedProposal,acceptedValue)返回 4.提议者接收到过半数请求后如果发现有acceptedValue返回表示有更新的提议保存acceptedValue到本地然后跳转1生成一个更高的提议 5.到这里表示在当前paxos instance内没有优先级更高的提议可以进入第二阶段广播accept(n,value)到所有节点 6.接收者比较n和minProposal如果nminProposal,则acceptedProposalminProposalnacceptedValuevalue本地持久化后返回 否则返回minProposal 7.提议者接收到过半数请求后如果发现有返回值n表示有更新的提议跳转1否则value达成一致。 从上述流程可知并发情况下可能会出现第4步或者第7步频繁重试的情况导致性能低下更严重者可能导致永远都无法达成一致的情况就是所谓的“活锁”如下图所示 1.S1作为提议者发起prepare(3.1),并在S1,S2和S3达成多数派 2.随后S5作为提议者 发起了prepare(3.5)并在S3,S4和S5达成多数派 3.S1发起accept(3.1,value1)由于S3上提议 3.53.1,导致accept请求无法达成多数派S1尝试重新生成提议 4.S1发起prepare(4.1),并在S1S2和S3达成多数派 5.S5发起accpet(3.5,value5)由于S3上提议4.13.5导致accept请求无法达成多数派S5尝试重新生成提议 6.S5发起prepare(5.5),并在S3,S4和S5达成多数派导致后续的S1发起的accept(4.1,value1)失败 ...... prepare阶段的作用 从Basic-Paxos的描述可知需要通过两阶段来最终确定一个值由于轮回多导致性能低下至少两次网络RTT。那么prepare阶段能否省去如下图所示 1.S1首先发起accept(1,red)并在S1,S2和S3达成多数派red在S1S2S3上持久化 2.随后S5发起accept(5,blue)对于S3而言由于接收到更新的提议会将acceptedValue值改为blue 3.那么S3S4和S5达成多数派blue在S3S4和S5持久化 4.最后的结果是S1和S2的值是red而S3S4和S5的值是blue没有达成一致。 所以两阶段必不可少Prepare阶段的作用是阻塞旧的提议并且返回已经接收到的acceptedProposal。同时也可以看到的是假设只有S1提议则不会出现问题这就是我们下面要讲的Multi-Paxos。 Multi-paxos算法 Paxos是对一个值达成一致Multi-Paxos是连续多个paxos instance来对多个值达成一致这里最核心的原因是multi-paxos协议中有一个Leader。Leader是系统中唯一的Proposal在lease租约周期内所有提案都有相同的ProposalId可以跳过prepare阶段议案只有accept过程一个ProposalId可以对应多个Value所以称为Multi-Paxos。 选举 首先我们需要有一个leader其实选主的实质也是一次Paxos算法的过程只不过这次Paxos确定的“谁是leader”这个值。由于任何一个节点都可以发起提议在并发情况下可能会出现多主的情况比如AB先后当选为leader。为了避免频繁选主当选leader的节点要马上树立自己的leader权威(让其它节点知道它是leader)写一条特殊日志(start-working日志)确认其身份。根据多数派原则只有一个leader的startworking日志可以达成多数派。leader确认身份后可以通过了lease机制(租约)维持自己的leader身份使得其它proposal不再发起提案这样就进入了leader任期由于没有并发冲突因此可以跳过prepare阶段直接进入accept阶段。通过分析可知选出leader后leader任期内的所有日志都只需要一个网络RTT(Round Trip Time)即可达成一致。 新主恢复流程 由于Paxos中并没有限制任何节点都可以参与选主并最终成为leader这就无法保证新选出的leader包含了所有日志可能存在空洞因此在真正提供服务前还存在一个获取所有已提交日志的恢复过程。新主向所有成员查询最大logId的请求收到多数派响应后选择最大的logId作为日志恢复结束点这里多数派的意义在于恢复结束点包含了所有达成一致的日志当然也可能包含了没有达成多数派的日志。拿到logId后从头开始对每个logId逐条进行paxos协议因为在新主获得所有日志之前系统是无法提供服务的。为了优化引入了confirm机制就是将已经达成一致的logId告诉其它acceptoracceptor写一条confirm日志到日志文件中。那么新主在重启后扫描本地日志对于已经拥有confirm日志的log就不会重新发起paxos了。同样的在响应客户端请求时对于没有confirm日志的log需要重新发起一轮paxos。由于没有严格要求confirm日志的位置可以批量发送。为了确保重启时不需要对太多已提价的log进行paxos需要将confirm日志与最新提交的logId保持一定的距离。 性能优化 Basic-Paxos一次日志确认需要至少2次磁盘写操作(prepare,promise)和2次网络RTT(prepare,promise)。Multi-Paxos利用一阶段提交(省去Prepare阶段)将一次日志确认缩短为一个RTT和一次磁盘写通过confirm机制可以缩短新主的恢复时间。为了提高性能我们还可以实现一批日志作为一个组提交要么成功一批要么都不成功这点类似于group-commit通过RT换取吞吐量。 安全性(异常处理) 1.Leader异常 Leader在任期内需要定期给各个节点发送心跳已告知它还活着(正常工作)如果一个节点在超时时间内仍然没有收到心跳它会尝试发起选主流程。Leader异常了则所有的节点先后都会出现超时进入选主流程选出新的主然后新主进入恢复流程最后再对外提供服务。我们通常所说的异常包括以下三类 (1).进程crash(OS crash) Leader进程crash和Os crash类似只要重启时间大于心跳超时时间都会导致节点认为leader挂了触发重新选主流程。 (2).节点网络异常(节点所在网络分区) Leader网络异常同样会导致其它节点收不到心跳但有可能leader是活着的只不过发生了网络抖动因此心跳超时不能设置的太短否则容易因为网络抖动造成频繁选主。另外一种情况是节点所在的IDC发生了分区则同一个IDC的节点相互还可以通信如果IDC中节点能构成多数派则正常对外服务如果不能比如总共4个节点两个IDC发生分区后会发现任何一个IDC都无法达成多数派导致无法选出主的问题。因此一般Paxos节点数都是奇数个而且在部署节点时IDC节点的分布也要考虑。 (3).磁盘故障 前面两种异常磁盘都是OK的即已接收到的日志以及对应confirm日志都在。如果磁盘故障了节点再加入就类似于一个新节点上面没有任何日志和Proposal信息。这种情况会导致一个问题就是这个节点可能会promise一个比已经promise过的最大proposalID更小的proposal这就违背了Paxos原则。因此重启后节点不能参与Paxos Instance它需要先追上Leader当观察到一次完整的paxos instance时该节点结束不能promise/ack状态。 2.Follower异常(宕机磁盘损坏等) 对于Follower异常则处理要简单的多因为follower本身不对外提供服务(日志可能不全)对于leader而言只要能达成多数派就可以对外提供服务。follower重启后没有promise能力直到追上leader为止。 QA 1.Paxos协议数据同步方式相对于基于传统1主N备的同步方式有啥区别 一般情况下传统数据库的高可用都是基于主备来实现1主1备2个副本主库crash后通过HA工具来进行切换提升备库为主库。在强一致场景下复制可以开启强同步Oracle和Mysql都是类似的复制模式。但是如果备库网络抖动或者crash都会导致日志同步失败服务不可用。为此可以引入1主N备的多副本形式我们对比都是3副本的情况一个是基于传统的1主2备另一种基于paxos的1主2备。传统的1主两备进行日志同步时只要有一个副本接收到日志并就持久化成功就可以返回在一定程度上解决了网络抖动和备库crash问题。但如果主库出问题后还是要借助于HA工具来进行切换那么HA切换工具的可用性如何来保证又成为一个问题。基于Paxos的多副本同步其实是在1主N备的基础上引入了一致性协议这样整个系统的可用性完全有3个副本控制不需要额外的HA工具。而实际上很多系统为了保证多节点HA工具获取主备信息的一致性采用了zookeeper等第三方接口来实现分布式锁其实本质也是基于Paxos来实现的。 我这里以MySQL的主备复制一套体系为例来具体说明传统的主备保持强一致性的一些问题。整个系统中主要包含以下几种角色MasterSlaveZookeeper-Service(zk)HA-Console(HA)Zookeeper-Agent(Agent) Master,Slave:分别表示主节点和备节点,主节点提供读写服务备节点可以提供读服务或者完全用于容灾。 Zookeeper-Service(zk):分布式一致性服务负责管理Master/Slave节点的存活信息和切换信息。zk基于zab协议zab协议是一种一致性协议与paxosraft协议类似它主要有两种模式包括恢复模式(选主)和广播模式(同步)。一般zk包含N个节点(zk-node)只要有超过半数的zk-node存活且相互连通则zk可以对外提供一致性服务。 HA-Console:切换工具负责具体的切换流程 Zookeeper-Agent(Agent):Master/Slave实例上的监听进程与监听的实例保持心跳维护Master/Slave的状态每个实例有一个对应的Agent。大概工作流程如下 (1).Master/Slave正常启动并搭建好了复制关系对应的Agent会调用zk接口去注册alive节点信息假设分别为A和B。 (2).如果此时Master Crash则实例对应的Agent发现心跳失败如果重试几次后仍然失败则将调用zk接口注销掉A节点信息。 (3).HA工具通过zk接口比较两次的节点信息发现少了A节点表示A可能不存在了需要切换尝试连接A如果仍然不通注册A的dead节点并开始切换流程。 (4).HA工具读取配置信息找到对应的Slave节点B(更改读写比配置信息设置B提供写)打开写。 (5).应用程序通过拉取最新的配置信息得知新主B新的写入会写入B。 前面几部基本介绍了MySQL借助zk实现高可用的流程由于zk-node可以多地部署HA无状态因此可以很容易实现同城或者是异地的高可用系统并且动态可扩展一个HA节点可以同时管理多个Master/Slave的切换。那么能保证一致性吗前面提到的Agent除了做监听还有一个作用是尽可能保持主备一致并且不丢数据。 (6).假设此时A节点重启Agent检测到通过zk接口发现A节点在dead目录下表示被切换过需要kill上面的所有连接并回滚crash时A比B多的binlog为了尽可能的少丢数据然后再开启binlog后将这部分数据重做。这里要注意rollback和replay都在old-Master上面进行rollback时需要关闭binlog而replay需要开启binlog保证这部分数据能流向new-Master。 (7).从第6步来看可以一定程度上保证主备一致性但是进行rollback和replay时实际上是往new-Slave上写数据这一定程度上造成了双写如果此时new—Master也在写同一条记录可能会导致写覆盖等问题。 (8).如果开启半同步呢old-Master crash时仍然可能比old-Slave多一个group的binlog所以仍然需要借助于rollback和replay依然避免不了双写所以也不能做到严格意义上的强一致。 2.分布式事务与Paxos协议的关系 在数据库领域提到分布式系统就会提到分布式事务。Paxos协议与分布式事务并不是同一层面的东西。分布式事务的作用是保证跨节点事务的原子性涉及事务的节点要么都提交(执行成功)要么都不提交(回滚)。分布式事务的一致性通常通过2PC来保证(Two-Phase Commit, 2PC)这里面涉及到一个协调者和若干个参与者。第一阶段协调者询问参与者事务是否可以执行参与者回复同意(本地执行成功)回复取消(本地执行失败)。第二阶段协调者根据第一阶段的投票结果进行决策当且仅当所有的参与者同意提交事务时才能提交否则回滚。2PC的最大问题是协调者是单点(需要有一个备用节点)另外协议是阻塞协议任何一个参与者故障都需要等待(可以通过加入超时机制)。Paxos协议用于解决多个副本之间的一致性问题。比如日志同步保证各个节点的日志一致性或者选主(主故障情况下)保证投票达成一致选主的唯一性。简而言之2PC用于保证多个数据分片上事务的原子性Paxos协议用于保证同一个数据分片在多个副本的一致性所以两者可以是互补的关系绝不是替代关系。对于2PC协调者单点问题可以利用Paxos协议解决当协调者出问题时选一个新的协调者继续提供服务。工程实践中Google SpannerGoogle Chubby就是利用Paxos来实现多副本日志同步。 3.如何将Paxos应用于传统的数据库复制协议中 复制协议相当于是对Paxos的定制应用通过对一系列日志进行投票确认达成多数派就相当于日志已经在多数派持久化成功。副本通过应用已经持久化的日志实现与Master节点同步。由于数据库ACID特性本质是由一个一致的状态到另外一个一致的状态每次事务操作都是对应数据库状态的变更并生成一条日志。由于client操作有先后顺序因此需要保证日志的先后的顺序在任何副本中不仅仅要保证所有日志都持久化了而且要保证顺序。对于每条日志通过一个logID标示logID严格递增(标示顺序)由leader对每个日志进行投票达成多数派如果中途发生了leader切换对于新leader中logID的“空洞”需要重新投票确认日志的有效性。 4.Multi-Paxos的非leader节点可以提供服务吗 Multi-Paxos协议中只有leader确保包含了所有已经已经持久化的日志当然本地已经持久化的日志不一定达成了多数派因此对于没有confirm的日志需要再进行一次投票然后将最新的结果返回给client。而非leader节点不一定有所有最新的数据需要通过leader确认所以一般工程实现中所有的读写服务都由leader提供。 5.客户端请求过程中失败了如何处理 client向leader发起一次请求leader在返回前crash了。对于client而言这次操作可能成功也可能失败。因此client需要检查操作的结果确定是否要重新操作。如果leader在本地持久化后并没有达成多数派时就crash新leader首先会从各个副本获取最大的logID作为恢复结束点对于它本地没有confirm的日志进行Paxos确认如果此时达成多数派则应用成功如果没有则不应用。client进行检查时会知道它的操作是否成功。当然具体工程实践中这里面涉及到client超时时间以及选主的时间和日志恢复时间。
