您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

时间:2020-01-03 11:22:26  来源:  作者:

paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点:1.难以理解 2.工程实现更难。

网上有很多讲解Paxos算法的文章,但是质量参差不齐。看了很多关于Paxos的资料后发现,学习Paxos最好的资料是论文《Paxos Made Simple》,其次是中、英文版维基百科对Paxos的介绍。本文试图带大家一步步揭开Paxos神秘的面纱。

Paxos是什么

Paxos算法是基于消息传递且具有高度容错特性一致性算法,是目前公认的解决分布式一致性问题最有效的算法之一。

google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品

虽然Mike Burrows说得有点夸张,但是至少说明了Paxos算法的地位。然而,Paxos算法也因为晦涩难懂而臭名昭著。本文的目的就是带领大家深入浅出理解Paxos算法,不仅理解它的执行流程,还要理解算法的推导过程,作者是怎么一步步想到最终的方案的。只有理解了推导过程,才能深刻掌握该算法的精髓。而且理解推导过程对于我们的思维也是非常有帮助的,可能会给我们带来一些解决问题的思路,对我们有所启发。

问题产生的背景

在常见的分布式系统中,总会发生诸如机器宕机网络异常(包括消息的延迟、丢失、重复、乱序,还有网络分区)等情况。Paxos算法需要解决的问题就是如何在一个可能发生上述异常的分布式系统中,快速且正确地在集群内部对某个数据的值达成一致,并且保证不论发生以上任何异常,都不会破坏整个系统的一致性。

注:这里某个数据的值并不只是狭义上的某个数,它可以是一条日志,也可以是一条命令(command)。。。根据应用场景不同,某个数据的值有不同的含义。

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

相关概念

在Paxos算法中,有三种角色:

Proposer

Acceptor

Learners

在具体的实现中,一个进程可能同时充当多种角色。比如一个进程可能既是Proposer又是Acceptor又是Learner

还有一个很重要的概念叫提案(Proposal)。最终要达成一致的value就在提案里。

注:

暂且认为『提案=value』,即提案只包含value。在我们接下来的推导过程中会发现如果提案只包含value,会有问题,于是我们再对提案重新设计

暂且认为『Proposer可以直接提出提案』。在我们接下来的推导过程中会发现如果Proposer直接提出提案会有问题,需要增加一个学习提案的过程。

Proposer可以提出(propose)提案;Acceptor可以接受(accept)提案;如果某个提案被选定(chosen),那么该提案里的value就被选定了。

回到刚刚说的『对某个数据的值达成一致』,指的是Proposer、Acceptor、Learner都认为同一个value被选定(chosen)。那么,Proposer、Acceptor、Learner分别在什么情况下才能认为某个value被选定呢?

Proposer:只要Proposer发的提案被Acceptor接受(刚开始先认为只需要一个Acceptor接受即可,在推导过程中会发现需要半数以上的Acceptor同意才行),Proposer就认为该提案里的value被选定了。

Acceptor:只要Acceptor接受了某个提案,Acceptor就任务该提案里的value被选定了。

Learner:Acceptor告诉Learner哪个value被选定,Learner就认为那个value被选定。

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

问题描述

假设有一组可以提出(propose)value(value在提案Proposal里)的进程集合。一个一致性算法需要保证提出的这么多value中,只有一个value被选定(chosen)。如果没有value被提出,就不应该有value被选定。如果一个value被选定,那么所有进程都应该能学习(learn)到这个被选定的value。对于一致性算法,安全性(safaty)要求如下:

只有被提出的value才能被选定。

只有一个value被选定,并且

如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个。

我们不去精确地定义其活性(liveness)要求。我们的目标是保证最终有一个提出的value被选定。当一个value被选定后,进程最终也能学习到这个value。

Paxos的目标:保证最终有一个value会被选定,当value被选定后,进程最终也能获取到被选定的value。

假设不同角色之间可以通过发送消息来进行通信,那么:

每个角色以任意的速度执行,可能因出错而停止,也可能会重启。一个value被选定后,所有的角色可能失败然后重启,除非那些失败后重启的角色能记录某些信息,否则等他们重启后无法确定被选定的值。

消息在传递过程中可能出现任意时长的延迟,可能会重复,也可能丢失。但是消息不会被损坏,即消息内容不会被篡改(拜占庭将军问题)。

推导过程

最简单的方案——只有一个Acceptor

假设只有一个Acceptor(可以有多个Proposer),只要Acceptor接受它收到的第一个提案,则该提案被选定,该提案里的value就是被选定的value。这样就保证只有一个value会被选定。

但是,如果这个唯一的Acceptor宕机了,那么整个系统就无法工作了!

因此,必须要有多个Acceptor

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

多个Acceptor

多个Acceptor的情况如下图。那么,如何保证在多个Proposer和多个Acceptor的情况下选定一个value呢?

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

下面开始寻找解决方案。

如果我们希望即使只有一个Proposer提出了一个value,该value也最终被选定。

那么,就得到下面的约束:

P1:一个Acceptor必须接受它收到的第一个提案。

但是,这又会引出另一个问题:如果每个Proposer分别提出不同的value,发给不同的Acceptor。根据P1,Acceptor分别接受自己收到的value,就导致不同的value被选定。出现了不一致。如下图:

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

刚刚是因为『一个提案只要被一个Acceptor接受,则该提案的value就被选定了』才导致了出现上面不一致的问题。因此,我们需要加一个规定:

规定:一个提案被选定需要被半数以上的Acceptor接受

这个规定又暗示了:『一个Acceptor必须能够接受不止一个提案!』不然可能导致最终没有value被选定。比如上图的情况。v1、v2、v3都没有被选定,因为它们都只被一个Acceptor的接受。

最开始讲的『提案=value』已经不能满足需求了,于是重新设计提案,给每个提案加上一个提案编号,表示提案被提出的顺序。令『提案=提案编号+value』。

虽然允许多个提案被选定,但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致。

于是有了下面的约束:

P2:如果某个value为v的提案被选定了,那么每个编号更高的被选定提案的value必须也是v。

一个提案只有被Acceptor接受才可能被选定,因此我们可以把P2约束改写成对Acceptor接受的提案的约束P2a。

P2a:如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v。

只要满足了P2a,就能满足P2。

但是,考虑如下的情况:假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案,Acceptor2~5(半数以上)均接受了该提案,于是对于Acceptor2~5和Proposer2来讲,它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来(之前Acceptor1没有收到过任何提案),此时Proposer1向Acceptor1发送了[M2,V2]的提案(V2≠V1且M2>M1),对于Acceptor1来讲,这是它收到的第一个提案。根据P1(一个Acceptor必须接受它收到的第一个提案。),Acceptor1必须接受该提案!同时Acceptor1认为V2被选定。这就出现了两个问题:

Acceptor1认为V2被选定,Acceptor2~5和Proposer2认为V1被选定。出现了不一致。

V1被选定了,但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2,且V2≠V1。这就跟P2a(如果某个value为v的提案被选定了,那么每个编号更高的被Acceptor接受的提案的value必须也是v)矛盾了。

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

所以我们要对P2a约束进行强化!

P2a是对Acceptor接受的提案约束,但其实提案是Proposer提出来的,所有我们可以对Proposer提出的提案进行约束。得到P2b:

P2b:如果某个value为v的提案被选定了,那么之后任何Proposer提出的编号更高的提案的value必须也是v。

由P2b可以推出P2a进而推出P2。

那么,如何确保在某个value为v的提案被选定后,Proposer提出的编号更高的提案的value都是v呢?

只要满足P2c即可:

P2c:对于任意的N和V,如果提案[N, V]被提出,那么存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:

S中每个Acceptor都没有接受过编号小于N的提案。

S中Acceptor接受过的最大编号的提案的value为V。

Proposer生成提案

为了满足P2b,这里有个比较重要的思想:Proposer生成提案之前,应该先去『学习』已经被选定或者可能被选定的value,然后以该value作为自己提出的提案的value。如果没有value被选定,Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的。

于是我们得到了如下的提案生成算法

Proposer选择一个新的提案编号N,然后向某个Acceptor集合(半数以上)发送请求,要求该集合中的每个Acceptor做出如下响应(response)。

(a) 向Proposer承诺保证不再接受任何编号小于N的提案

(b) 如果Acceptor已经接受过提案,那么就向Proposer响应已经接受过的编号小于N的最大编号的提案

我们将该请求称为编号为NPrepare请求

如果Proposer收到了半数以上的Acceptor的响应,那么它就可以生成编号为N,Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案,那 么此时V就可以由Proposer自己选择

生成提案后,Proposer将该提案发送给半数以上的Acceptor集合,并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。(注意:此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合)

Acceptor接受提案

Acceptor可以忽略任何请求(包括Prepare请求和Accept请求)而不用担心破坏算法的安全性。因此,我们这里要讨论的是什么时候Acceptor可以响应一个请求。

我们对Acceptor接受提案给出如下约束:

P1a:一个Acceptor只要尚未响应过任何编号大于NPrepare请求,那么他就可以接受这个编号为N的提案

如果Acceptor收到一个编号为N的Prepare请求,在此之前它已经响应过编号大于N的Prepare请求。根据P1a,该Acceptor不可能接受编号为N的提案。因此,该Acceptor可以忽略编号为N的Prepare请求。当然,也可以回复一个error,让Proposer尽早知道自己的提案不会被接受。

因此,一个Acceptor只需记住:1. 已接受的编号最大的提案 2. 已响应的请求的最大编号。

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

Paxos算法描述

经过上面的推导,我们总结下Paxos算法的流程。

Paxos算法分为两个阶段。具体如下:

阶段一:

(a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求

(b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案

阶段二:

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案Accept请求半数以上的Acceptor。注意:V就是收到的响应编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于NPrepare请求做出过响应,它就接受该提案

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

Learner学习被选定的value

Learner学习(获取)被选定的value有如下三种方案:

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

如何保证Paxos算法的活性

Paxos算法为什么说是Raft,Zab协议的鼻祖,及原理解析

 

通过选取主Proposer,就可以保证Paxos算法的活性。至此,我们得到一个既能保证安全性,又能保证活性分布式一致性算法——Paxos算法

 

专注于技术热点大数据,人工智能JAVAPython、 C 、GO、JavaScript等语言最新前言技术,及业务痛点问题分析,请关注【编程我最懂】共同交流学习。



Tags:Paxos算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
分布式共识系列文章: 《解决分布式一致性问题,不得不了解的Paxos算法》 《基本Paxos协议是如何实现分布式数据一致性的?》 《可用于实际应用场景中的Multi Paxos实用算法》前面...【详细内容】
2021-06-04  Tags: Paxos算法  点击:(173)  评论:(0)  加入收藏
paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点:1.难以理解 2.工程实现更难。网上有很多讲解Paxos算法的文章,但是质量参差不齐。看了很多关于...【详细内容】
2020-01-03  Tags: Paxos算法  点击:(81)  评论:(0)  加入收藏
前言在文章2PC/3PC到底是啥中介绍了2PC这种一致性协议,从文中了解到2PC更多的被用在了状态一致性上(分布式事务),在数据一致性中很少被使用;而Paxos正是在数据一致性中被广泛使...【详细内容】
2019-10-18  Tags: Paxos算法  点击:(104)  评论:(0)  加入收藏
概述Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的"La",此人在微软研究院)1990年提出的一种基于消息传递的一致性算法。[1] 这个算法被认为是类似算法中最有...【详细内容】
2019-09-27  Tags: Paxos算法  点击:(89)  评论:(0)  加入收藏
Paxos算法在分布式领域具有非常重要的地位。但是Paxos算法有两个比较明显的缺点:1.难以理解 2.工程实现更难。网上有很多讲解Paxos算法的文章,但是质量参差不齐。看了很多关于...【详细内容】
2019-08-15  Tags: Paxos算法  点击:(161)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条