一、什么是paxos算法
Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。
人们在理解paxos算法是会遇到一些困境,那么接下来,我们带着以下几个问题来学习paxos算法:
1、paxos到底在解决什么问题?
2、paxos到底如何在分布式存储系统中应用?
3、paxos的核心思想是什么?
二、paxos解决了什么问题
分布式的一致性问题其实主要是指分布式系统中的数据一致性问题。所以,为了保证分布式系统的一致性,就要保证分布式系统中的数据是一致的。
在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个"一致性算法"以保证每个节点看到的指令一致。
所以,paxos算法主要解决的问题就是如何保证分布式系统中各个节点都能执行一个相同的操作序列。
上图中,C1是一个客户端,N1、N2、N3是分布式部署的三个服务器,初始状态下N1、N2、N3三个服务器中某个数据的状态都是S0。
当客户端要向服务器请求处理操作序列:op1op2op3时(op表示operation)(这里把客户端的写操作简化成向所有服务器发送相同的请操作序列,实际上可能通过Master/Slave模式处理)。如果想保证在处理完客户端的请求之后,N1、N2、N3三个服务器中的数据状态都能从S0变成S1并且一致的话(或者没有执行成功,还是S0状态),就要保证N1、N2、N3在接收并处理操作序列op1op2op3时,严格按照规定的顺序正确执行opi,要么全部执行成功,要不就全部都不执行。
所以,针对上面的场景,paxos解决的问题就是如何依次确定不可变操作opi的取值,也就是确定第i个操作什么,在确定了opi的内容之后,就可以让各个副本执行opi操作。
三、Paxos算法详解
Paxos是一个十分巧妙的一致性算法,但是他也十分难以理解,就连他的作者Lamport都*对他做过多种讲解。我们先把前面的场景简化,把我们现在要解决的问题简化为如何确定一个不可变变量的取值(每一个不可变变量可以标识一个操作序列中的某个操作,当确保每个操作都正确之后,就可以按照顺序执行这些操作来保证数据能够准确无误的从一个状态转变成另外一个状态了)。
接下来,请跟我一步一步的学习paxos算法。
要学习paxos算法,我们就要从他要解决的问题出发,假如没有paxos算法,当我们面对如何确定一个不可变变量的取值这样一个问题的时候,我们应该如何解决呢?
问题抽象
我们把确定一个不可变变量的取值问题定义成:
设计一个系统,来存储名称为var的变量。
var的取值可以是任意二进制数
系统内部由多个Accepter组成,负责管理和存储var变量。
系统对外提供api,用来设置var变量的值
propose(var,V) => <ok,f> or <error>
将var的值设置为V,系统会返回ok和系统中已经确定的取值f,或者返回error。
外部有多个Proposer机器任意请求系统,调用系统API(propose(var,V) => <ok,f> or <error>)来设置var变量的值。
如果系统成功的将var设置成了V,那么返回的f应该就是V的值。否则,系统返回的f就是其他的Proposer设置的值。
系统需要保证var的取值满足一致性
如果var没有被设置过,那么他的初始值为null
一旦var的值被设置成功,则不可被更改,并且可以一直都能获取到这个值
系统需要满足容错特性
可以容忍任意proposer出现故障
可以容忍少数acceptor故障(半数以下)
暂时忽略网络分化问题和acceptor故障导致var丢失的问题。
到这里,问题已经抽象完成了,读者可以再仔细看看上面的系统描述。如果这样设置一个系统,是不是就可以保证变量var的不可变性了呢?
这里还是再简单讲解一下,上面的系统确实可以保证变量var的不可变性。
因为var的初始值为null,当有proposer请求接口propose(var,v)设置var的值的时候,系统会将var设置为v,并返回f(f==v)。
var变量被初始化以后,再有proposer请求propose(var,v)设置var的值的时候,系统会直接返回系统中已有的var的值f,而放弃proposer提供的v。
系统难点
要设计以上系统存在以下难点:
1、管理多个proposer并发执行
2、容忍var变量的不可变性
3、容忍任意Proposer的故障
4、容忍半数以下的acceptor的故障
解决方案一
先考虑整个系统由单个acceptor组成。通过类似互斥锁的方式来管理并发的proposer的请求。
proposer向acceptor申请acceptor的互斥访问权,当取得互斥访问权之后才能调用api给var变量赋值。
accepter向proposer发放互斥访问权,谁取得了互斥访问权,acceptor就接收谁的请求。
这样通过互斥访问的机制,proposer就要按照获取互斥访问权的顺序来请求系统。
一旦acceptor接收到一个proposer请求,并成功给var变量赋值之后,就不再允许其他的proposer设置var变量的值。每当再有proposer来请求设置var变量的值的时候,acceptor就会将var里面现有的值返回给他。
基于互斥访问权的acceptor的实现
acceptor会保存变量var的值和一个互斥锁Lock。
提供接口prepare()
加互斥锁,给予var的互斥访问权,并返回当前var的取值
提供接口release()
用于释放互斥访问权
提供接口accept(var, v)
如果已经加锁,并且当前var没有值,则将var的值设置成v,并释放锁。
proposer采用两阶段来实现
Step1、通过调用prepare接口来获取互斥性访问权和当前var的取值
如果无法获取到互斥性访问权,则返回,并不能进入到下一个阶段,因为其他proposer获取到了互斥性访问权。
Step2、根据当前var的取值f选择执行
1、如果f的取值为null,说明没有被设置过值,则调用接口accept(var ,v)来将var的取值设置成v,并释放掉互斥性访问权。
2、如果f的取值不为null,说明var已经被其他proposer设置过值,则调用release接口释放掉互斥性访问权。
总结:方案一通过互斥访问的方式来保证所有的proposer能够串行的访问acceptor,这样其实并没有解决多个proposer并发执行的问题。只是想办法绕开了并发执行。虽然可以在一定程度上保证var变量的取值是确定的。但是一旦获取到互斥访问权的proposer在执行过程中出现故障,那么就会导致所有其他proposer无法再获取到互斥访问权,就会发生死锁。。所以,方案一不仅效率低、而且还会产生死锁问题,不能容忍任意Proposer出现故障。
在之前提到的四个系统难点中,方案一可以解决难点1和难点2,但是无法解决难点3和难点4。
解决方案二
通过引入抢占式访问权来取代互斥访问权。acceptor有权让任意proposer的访问权失效,然后将访问权发放给其他的proposer。
在方案二中,proposer向acceptor发出的每次请求都要带一个编号(epoch),且编号间要存在全序关系。一旦acceptor接收到proposer的请求中包含一个更大的epoch的时候,马上让旧的epoch失效,不再接受他们提交的取值。然后给新的epoch发放访问权,让他可以设置var变量的值。
为了保证var变量取值的不变性,不同epoch的proposer之前遵守后者认同前者的原则:
在确保旧的epoch已经失效后,并且旧的epoch没有设置var变量的值,新的epoch会提交自己的值。
当旧的epoch已经设置过var变量的取值,那么新的epoch应该认同旧的epoch设置过的值,并不在提交新的值。
基于抢占式访问权的acceptor的实现
转载
分布式一致性算法——paxos的更多相关文章
-
分布式一致性算法--Paxos
Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法.Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致.在工程实践意义上来说, ...
-
分布式一致性算法 Paxos、Raft、Zab的区别与联系
什么是分布式系统? 拿一个最简单的例子,就比如说我们的图书管理系统.之前的系统包含了所有的功能,比如用户注册登录.管理员功能.图书借阅管理等.这叫做集中式系统.也就是一个人干了好几件事. 后来随着功能 ...
-
一致性算法--Paxos
分布式一致性算法--Paxos Paxos算法是莱斯利·兰伯特(Leslie Lamport)1990年提出的一种基于消息传递的一致性算法.Paxos算法解决的问题是一个分布式系统如何就某个值(决议) ...
-
分布式_理论_05_ 一致性算法 Paxos
一.前言 二.参考资料 1.分布式理论(五)—— 一致性算法 Paxos 2.分布式理论(五) - 一致性算法Paxos
-
分布式一致性算法 2PC 3PC Paxos
分布式一致性算法的目的是为了解决分布式系统 一致性算法可以通过共享内存(需要锁)或者消息传递实现,本文讨论后者实现的一致性算法,不仅仅是分布式系统中,凡是多个过程需要达成某种一致的场合都可以使用. 本 ...
-
分布式一致性算法:Raft 算法(论文翻译)
Raft 算法是可以用来替代 Paxos 算法的分布式一致性算法,而且 raft 算法比 Paxos 算法更易懂且更容易实现.本文对 raft 论文进行翻译,希望能有助于读者更方便地理解 raft 的 ...
-
分布式一致性算法2PC和3PC
为了解决分布式一致性问题,产生了不少经典的分布式一致性算法,本文将介绍其中的2PC和3PC.2PC即Two-Phase Commit,译为二阶段提交协议.3PC即Three-Phase Commit, ...
-
【转】Raft 为什么是更易理解的分布式一致性算法
编者按:这是看过的Raft算法博客中比较通俗的一篇了,讲解问题的角度比较新奇,图文并茂,值得一看.原文链接:Raft 为什么是更易理解的分布式一致性算法 一致性问题可以算是分布式领域的一个圣殿级问题了 ...
-
【转】分布式一致性算法:Raft 算法(Raft 论文翻译)
编者按:这篇文章来自简书的一个位博主Jeffbond,读了好几遍,翻译的质量比较高,原文链接:分布式一致性算法:Raft 算法(Raft 论文翻译),版权一切归原译者. 同时,第6部分的集群成员变更读 ...
随机推荐
-
mysql重置密码
1.首先停止正在运行的MySQL进程 复制代码代码如下: >net stop mysql 如未加载为服务,可直接在进程管理器或者服务中进行关闭. 2.以安全模式启动MySQL 进入mysql目 ...
-
iOS10 拍照崩溃问题
根据相对应得功能添加相关权限即可,没必要全部添加,后面的描述可以官方点,因为会以弹出框的形式访问的,比如相机权限后面的描述可以为:这个应用需要访问相机:后续如果发现其他iOS10上面的问题会及时更新的
-
CI 框架隐藏index.php-ubuntu
和朋友在做一个小网站,用到了CI框架,之前测试都是在windows上,隐藏index.php也相对比较简单.但服务器是ubuntu系统,需要配置一下,根据网上看到的一些教程,结合自己电脑的特点,记录步 ...
-
Shell脚本编程的常识
(这些往往是经常用到,但是各种网络上的材料都语焉不详的东西,个人认为比较有用) 七种文件类型 d 目录 ...
-
Redis各种数据结构性能数据对比和性能优化实践
很对不起大家,又是一篇乱序的文章,但是满满的干货,来源于实践,相信大家会有所收获.里面穿插一些感悟和生活故事,可以忽略不看.不过听大家普遍的反馈说这是其中最喜欢看的部分,好吧,就当学习之后轻松一下. ...
- 第六章&#160;图(a)概述
-
Ant运行build.xml执行服务器scp,异常解决jsch.jar
公司ant打包上线 一直出现这个问题. Ant运行build.xml执行服务器scp,异常解决jsch.jar BUILD FAILEDD:\eclipse\eclipse-jee-luna-SR2- ...
-
JavaScript - Scope of variables
It's important to note, especially if you have come to JavaScript from another language, that variab ...
-
oracle存储过程(返回列表的存储结合游标使用)总结 以及在java中的调用
这段时间开始学习写存储过程,主要原因还是因为工作需要吧,本来以为很简单的,但几经挫折,豪气消磨殆尽,但总算搞通了,为了避免后来者少走弯路,特记述与此,同时亦对自己进行鼓励. 以下是我在开发项目中第一次 ...
-
laravel基础课程---9、视图(lavarel的模板语法和tp相比怎样)
laravel基础课程---9.视图(lavarel的模板语法和tp相比怎样) 一.总结 一句话总结: lavarel的模板语法比thinkphp好用很多:和html代码配合的更好 lavarel比t ...