一步一步理解paxos算法

Shiftyman      2022-02-12     540

关键词:

转自:http://www.open-open.com/lib/view/open1420635646984.html


背景

Paxos 算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视,使Lamport在八年后重新发表到 TOCS上。即便如此paxos算法还是没有得到重视,2001年Lamport用可读性比较强的叙述性语言给出算法描述。可见Lamport对 paxos算法情有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪,其中的chubby锁服务使用paxos作为chubby cell中的一致性算法,paxos的人气从此一路狂飙。


Paxos什么

Paxos 算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致,是分布式计算中的重要问题。


Paxos两个原则

安全原则---保证不能做错的事

1. 只能有一个值批准,能出现第二个把第一个覆盖情况

2. 每个节点只能学习到已经批准的值,不能学习没有被批准的值

存活原则---只要多数服务器存活并且彼此间可以通信最终都要做到的

1. 最终批准某个提议的值

2. 一个值批准了,其他服务器最终会学习到这个


Paxos两个组件

Proposer

提议发起者,处理客户端请求,客户端的请求发送到集群中以便决定这个值是否可以被批准

Acceptor

提议批准者,负责处理接收到的提议他们的回复就是一次投票会存储一些状态来决定是否接收一个值


Paxos定义

接下来用举例的方式一步一步解释Paxos为了完成一致性必须要解决的一些问题。这里为了方便解释,假设每一服务器都一个Proposer,也是一个Acceptor

一个Acceptor

首先从最简单的方式开始,假设只有一个Acceptor它做决定是否批准一个值

技术分享

如上每一个proposer提议一个给Acceptor来批准然后Acceptor批准一个值作为最终的值

但是这种简单方式,没有办法解决Acceptor crash的问题如果唯一的Acceptor crash了,就没有办法知道哪个值被选择了,就需要等待重启,这一条违反了存活原则,这个时候有4台服务器存活,但已经没有办法工作了。


多个Acceptor

为了解决这个问题,就必须要用到一种多数选择的方法使用一个Acceptor的集合。然后只有其中的多数批准了一个值,这个值才可以确实是被最终被批准为了达到目的也需要一些技巧


批准第一个达到的值

首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值

技术分享

但是有一个问题,比如上图,因为没有值被多数批准,无法批准一个最终的值出来这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值


批准每个提议的值

接下来规定Acceptor批准每个提议的值,但是这也会带来一个问题,可能批准出多个值

技术分享

如图S1发出提议S1,S2,S3批准 red最终批准的值S5随后发出提议,s3S4,S5批准,blue为最终批准的值。此时S1,S2最终批准red,S3,S4,S5最终批准blue,这就违背了我们的一致性原则,最终只有一个值选择


二段提交原则

解决这个问题,就要S5在发送自己的提议之前,优先检查有没有已经被批准的值,如果有应该提议已经被批准的值而放弃自己的值也就是放弃自己的blue改为提议red这样最终只有一个值被批准就是red这个就是经典的二段提交原则

不幸的是,二段提交还是存在另一个问题。

技术分享

如图S1在发送提议之前,检查没有批准,因此提议red同时在所有Acceptor批准之前,S5也要进行提议,这个时候也检查出没有值被批准,所以自己的blue作为提议发送acceptor。接下来S5的提议优先到达S3,S4,S5,这些Acceptor先批准了blue,达到多数所以blue最终批准了。但是随后S1S2,S3接收到了red进行批准所以又出现批准出多个值问题


提议排序

这个问题要解决,就需要一旦Acceptor批准了某个值其他冲突的值都应该被拒绝。也就是说S3随后到达的red应该被拒绝为了做到这一点。需要对Proposer进行排序,将排序在前的赋予高优先级,Acceptor批准优先级高的值,拒绝排序在后的值

为了将提议进行排序,可以为每个提议赋予一个唯一ID,规定这个ID越大,优先级越高

提议者发送提议之前,需要生成一个唯一的ID,而且需要比之前使用的或者生成的都要大


提议ID生成算法

在Google的Chubby论文中给出了这样一种方法:假设有n个proposer,每个编号为ir(0<=ir<n),proposor编号的任何值s都应该大于它已知的最大值,并且满足:s %n = ir => s = m*n + ir

proposer已知的最大值来自两部分:proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值

以3个proposer P1、P2、P3为例,开始m=0,编号分别为0,1,2

1. P1提交的时候发现了P2已经提交,P2编号为1 > P1的0,因此P1重新计算编号:new P1 = 1*3+0 = 4

2. P3以编号2提交,发现小于P1的4,因此P3重新编号:new P3 = 1*3+2 = 5


Paxos算法

此阶段,要保证Paxos的两个原则已经都满足了,Paxos也就顺利的实现了


二段提交

prepare 阶段:

1. Proposer 选择一个提案编号 n 并将 prepare 请求发送给 Acceptors 中的一个多数派;

2. Acceptor 收到 prepare 消息后,如果提案的编号大于它已经回复的所有 prepare 消息,则 Acceptor 将自己上次接受的提案回复给 Proposer,并承诺不再回复小于 n 的提案;


acceptor阶段:

1. 当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后,就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求,包括编号 n 和根据 prepare阶段 决定的 value(如果根据 prepare 没有已经接受的 value,那么它可以自由决定 value)。

2. 在不违背自己向其他 Proposer 的承诺的前提下,Acceptor 收到 accept 请求后即接受这个请求。

prepare阶段两个目的,第一检查是否有被













一步一步学jvm-垃圾回收算法

标记-清除算法        算法分为标记和清除两个阶段:首先标记所有需要回收的对象,在标记完成后统一回收所有被标记的对象。        该算法存在的缺点:  1、 ... 查看详情

转载一步一步理解线段树

目录一、概述二、从一个例子理解线段树  创建线段树  线段树区间查询  单节点更新  区间更新三、线段树实战--------------------------一概述线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),... 查看详情

一步一步理解线段树——转载自justdoit

目录一、概述二、从一个例子理解线段树  创建线段树  线段树区间查询  单节点更新  区间更新三、线段树实战--------------------------一概述线段树,类似区间树,它在各个节点保存一条线段(数组中的一段子数组),... 查看详情

一步一步理解java企业级应用的可扩展性

摘要:本文主要介绍如何理解Java应用的扩展方式以及不同类型的扩展技术和具体技巧,介绍一些有关Java企业级应用的一般扩展策略。老实说,“可扩展性”是个全面且详尽的话题,而且往往得不到充分理解。人们通常认... 查看详情

由浅入深理解latentdiffusion/stablediffusion:一步一步搭建自己的stablediffusionmodels

...和读者一起遨游diffusionmodels的世界!本文主要介绍带大家一步步搭建自己的stablediffusi 查看详情

一步一步学vue

为了提升代码的逼格,之后代码改为Vue文件组件,之前代码虽然读起来容易理解,而且适合在小的项目中使用,但是有如下缺点:全局定义(Globaldefinitions) 强制要求每个component中的命名不得重复字符串模板(Stringtemplates) 缺... 查看详情

oracle一步一步学习(代码片段)

1.oracle的组成(A)实例:理解为对象,看不见的(B)数据库:理解为类,看得见的,E:\\app\\Administrator\\oradata\\orcl\\*.DBF2.oracle服务器与orcl数据库的关系一个oracle数据库服务器中包括多个数据库,... 查看详情

一步一步实现一个promisea+规范的promise

...分为三个部分,每个部分实现Promise的一部分特性,最终一步一步的实现一个完整的、遵循promiseA 查看详情

快速排序一步一步优化

一、快速排序介绍  快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)。  算法思想:1.先从数组中取出一个数组作为枢轴,一般情况下选取数组的第一... 查看详情

一步一步学jvm-垃圾回收器

Serial收集器        Serial收集器是最基本、历史最悠久的收集器。这个收集器是一个单线程的收集器。它在进行垃圾收集时,必须暂停其他所有的工作线程,直到它收集结束。Serial收集器是新生代的收... 查看详情

ganstepbystep(一步一步学习gan)(代码片段)

...pByStep心血来潮GSBS,顾名思义,我希望我自己能够一步一步的学习GAN。GAN又名生成对抗网络,是最近几年很热门的一种无监督算法,他能生成出非常逼真的照片,图像甚至视频。GAN是一个图像的全新的领域࿰... 查看详情

ganstepbystep(一步一步学习gan)(代码片段)

...pByStep心血来潮GSBS,顾名思义,我希望我自己能够一步一步的学习GAN。GAN又名生成对抗网络,是最近几年很热门的一种无监督算法,他能生成出非常逼真的照片,图像甚至视频。GAN是一个图像的全新的领域࿰... 查看详情

一步一步教你反向传播的样例

背景反向传播(Backpropagation)是训练神经网络最通用的方法之中的一个,网上有很多文章尝试解释反向传播是如何工作的,可是非常少有包括真实数字的样例,这篇博文尝试通过离散的数据解释它是如何工作的。Python实现的反向传... 查看详情

一步一步实现基于gpu的pathtracer:基础

出于3D计算机图形学和图形渲染方面的个人兴趣,脑子里便萌生出了自己实现一个渲染器的想法,主要是借助pathtracing这种简单的算法,外加GPU加速来实现,同时也希望感兴趣的朋友们能够喜欢,也欢迎提出一些更好的看法~~。(... 查看详情

读懂源码:一步一步实现一个vue

源码阅读:究竟怎样才算是读懂了?市面上有很多源码分析的文章,就我看到的而言,基本的套路就是梳理流程,讲一讲每个模块的功能,整篇文章有一大半都是直接挂源码。我不禁怀疑,作者真的看懂了吗?为什么我看完后还... 查看详情

带你一步一步理解c语言指针!(代码片段)

一直觉得C语言较其他语言最伟大的地方就是C语言中的指针,有些人认为指针很简单,而有些人认为指针很难,当然这里的对简单和难并不是等价于对指针的理解程度。为此作者在这里对C语言中的指针进行全面的总结... 查看详情

面向对象的个人理解

...面向过程和面向对象;面向过程:要想得到一个结果需要一步一步的去设计出来,一步一步的敲代码去实现这是一个过程。比如说要比较两个数的大小有以下程序:inta=3;intb=4;intmax=a;if(a<b)max=b;总之要得的max这个结果就必须一行... 查看详情

从零开始带你一步一步使用yolov3训练自己的数据(代码片段)

...测(ObjectDection)算法。今天给大家介绍一下如何一步一步使用Y 查看详情