架构设计:系统存储(24)——数据一致性与Paxos算法(中)-程序员宅基地

技术标签: 最终一致性  系统存储  架构设计  系统架构  Paxos  

(接上文《架构设计:系统存储(23)——数据一致性与Paxos算法(上)》)

2-1-1. Prapare准备阶段

这里写图片描述

首先需要介绍几个在Acceptor角色上需要被持久化保存的数据属性:

  • PrepareVote保存了当前Acceptor接收到的已完成投票授权的最大投票轮次
  • AcceptedVote保存了当前Acceptor在赋值阶段完成投票赋值的投票轮次
  • AcceptedValue保存了当前Acceptor在赋值阶段被赋予的值

1、第一个阶段Proposer和Acceptor至少要完成一次网络通讯,其主要目的是确定针对提议X的当前投票轮次是否能被授权。换句话说,根据Acceptor在准备阶段的工作原则,即使确定当前投票轮次的编号值是大于Acceptor中记录的PrepareVote的值。处理过程很简单,即Proposer向所有Acceptor发出关于发起提议X的新一轮投票的申请,并等待各个Acceptor进行响应。当然会有一个超时时间,如果超过这个时间还没有得到Acceptor的响应,则认为已经被拒绝。如果有超过N/2 + 1个节点在规定的时间内没有回复响应,那就说明整个选举系统发现了问题,则终止操作抛出错误,向客户端反馈异常信息

2、收到这个发起新的一轮投票操作的授权请求后,各个Acceptor开始判断是否可以进行授权。判断的原则只与PrepareVote有关,既是如果当前申请的投票轮次小于等于PrepareVote的赋值,则拒绝授权;其它情况都要接受授权,并更改PrepareVote属性为当前新的投票伦次编号。这里有一个隐藏含义,即这个Acceptor新授权的投票轮次编号,一定大于之前PrepareVote的值。

3、Proposer将负责汇总所有Acceptor的响应情况,并根据汇总的情况判断下一步的操作。无论Acceptor是授权这次投票还是拒绝这次投票,给出的响应信息中都最好包括当前Acceptor所记录的PrepareVote、AcceptedVote和AcceptedValue信息,这样有利于Proposer分析为什么会被Acceptor拒绝。下图展示了Proposer在汇总所有Acceptor的响应时可能出现的各种情况:

这里写图片描述

当然还有一种情况三,就是超过(包括)N/2 + 1个Acceptor节点在规定的时间内没有反馈结果,这种情况直接判定Paxos系统崩溃,所以就不做进一步讨论了。请注意,无论是上图的哪种情况,只要至少N/2 + 1个Acceptor节点的AcceptedValue为同一个值,就认为提议X的结果达到了最终一致,整个Paxos算法过程也结束。

3.1、在Proposer得到的响应情况一中,至少N/2 + 1个Acceptor允许这轮投票。这些Acceptor就形成了一个集合Q,这个集合Q将继续下一步骤的操作。这时集合Q中的Acceptor是否已有AcceptedValue就很重要了:如果集合Q中没有任何一个Acceptor的AcceptedValue属性有值,则当前Proposer会在下一步提议自己的值为集合Q中每一个Acceptor的赋值目标;如果集合Q中至少存在一个Acceptor的AcceptedValue属性有值,则Proposer会选择一个AcceptedVote最大的AcceptedValue属性值,作为当前Proposer会在下一步进行Acceptor赋值的目标。

3.2、在Proposer得到的响应情况二中,始终未达到N/2 + 1个Acceptor允许这轮投票——无论是不满足Acceptor的授权原则还是Acceptor超时未响应。只要至少N/2 +1个Acceptor所回复的AcceptedValue属性值相同,则表示针对提议X已经形成了最终一致的结果,无需再进行投票了。否则,Proposer会将自己的投票轮次编号进行增加后,再发起投票——这个增加规则后续再讨论,读者目前可以认为是+1。

2-1-2. Accept赋值阶段

一旦有N/2 + 1个Acceptor节点授权了本轮投票,Proposer就可以进入第二阶段——赋值阶段,第二阶段将以上一阶段形成的多数派集合Q作为操作目标。如下图所示:

这里写图片描述

1、Proposer将会以上一阶段3.1步骤中所确定的value和自己的vote一起发送给集合Q中的每一个Acceptor,并等待回复。

2、Acceptor收到赋值请求后,将会按照判断原则确认是否进行赋值。这个判断原则上文已经说过了,这里再说一次。如果当前收到的vote小于当前Acceptor的PrepareVote属性值,则不会进行赋值。为什么Acceptor上的PrepareVote会发生变化呢?这是因为在这个Proposer从第一阶段到第二阶段的操作间隙,另一个或者多个Proposer使用编号更大的vote发起了更新一轮的投票,并得到当前Acceptor的授权。如果当前收到的vote等于当前Acceptor的PrepareVote属性值则接受这次赋值,这时Acceptor将更改其AcceptedVote属性为vote,更改其AcceptedValue属性为value。

注意一种情况,Acceptor会不会在第二阶段操作时收到一个vote大于当前PrepareVote的赋值请求呢?这是不会的,因为任何Acceptor要更换PrepareVote,只可能更换比当前PrepareVote更大的值,所以之前被Acceptor同意授权的vote一定会小于或者等于当前Acceptor的PrepareVote属性值。

3、赋值操作完成后,Acceptor将向Proposer返回赋值操作后的AcceptedValue属性和AcceptedVote属性。换句话说就是,即使Acceptor拒绝了第二阶段的赋值操作,也要向Proposer返回AcceptedValue属性值。以下为Proposer端汇总统计时,可能出现的情况:

这里写图片描述

3.1、Acceptor收到集合Q中所有Acceptor的赋值结果后,就会进行汇总判断。如果发现所有赋值结果都是一样的value,则认为针对议题X形成了最终一致的结果。整个投票过程结束,value就是达成的最终值。

3.2、如果收到集合Q中所有Acceptor的赋值结果,并进行比较的过程中,发现任何一个赋值结果不一致,则认为赋值操作失败。这时Proposer会将自己的投票轮次编号进行增加后,再回到第一阶段重新发起投票。

2-1-3. 分析一种极端情况

Paxos算法的一个核心思路在于形成多数派决议,要形成核心思路Acceptor就必须按照自己的两个工作原则进行授权操作和赋值操作。这就是为什么我们在介绍Paxos算法时经常提到N/2 + 1的边界节点数量的原因。因为一旦形成多数派,决定最终一致性的关键表决就可以落在唯一一个节点上,也就是说如果第X1轮投票和第X2轮投票如果都同时拿到了多数派Acceptor的授权,那么它们的核心战略点就是要去抢占授权X1投票的Acceptor集合和授权X2投票的Acceptor集合求交集后至少存在一个的Acceptor节点。好消息是赋值阶段X1轮投票的编号和X2轮投票的编号总是不同的,也总有大小差异的,而Acceptor的工作方式决定了它只会接受编号更大的投票操作的赋值。

这个原理可以扩展到任意多个Proposer,那么有的读者会问了,会不会出现一种每个Acceptor的AcceptedValue属性都被赋值,且都没有达到多数派的特殊情况呢(如下图所示)?

这里写图片描述

答案是不会的,本小节我们将使用反向论证证的方式来进行阐述。首先要出现三个X1的赋值结果Proposer1便不能继续赋值这样的现象,只可能是一种情况即Proposer1在经过两阶段操作,并在进行Acceptor1~Acceptor3赋值的时候,后者三个节点上PrepareVote等于Proposer1的Vote,而在Proposer1准备进行后续三个节点赋值时,却发现Acceptor4~Acceptor6的PrepareVote改变了。如下图所示:

这里写图片描述

这时发起V2轮次投票的ProposerB,有两种情况,如下图所示:

第一种情况ProposerB还没有接收到至少N/2 + 1个Acceptor节点的授权结果,还处于第一阶段(这里Acceptor节点个数为6个,所以至少应该收到4个Acceptor的授权结果),这时ProposerB会一直等待汇总,如果等待超时都没有收到必要数量的结果,那么ProposerB继续增加它的投票编号,并重新发起。这时同样能够保证Acceptor集合不被之前的Proposer继续赋值——因为投票编号仍然最大。

如果是上图所示的第二种情况,就更简单了。ProposerB节点已经收到了至少4个Acceptor节点的授权结果,而这4个Acceptor节点,至少有一个节点携带了AcceptedValue为X1的值——因为目前被赋予X1的Acceptor节点个数,刚好为一半3个节点,和N/2 + 1个节点求交集后,至少有一个重叠的Acceptor节点(注意,基数为偶数,如果为奇数就更不会出现我们现在讨论的极端情况了)。也就是说当ProposerB节点进入第二阶段赋值操作时,向剩余Acceptor节点传递的值同样为X1,而不是自身原始提议的X2,所以最终本小节最初所述的极端情况不会出现。

2-1-4、一种投票轮次的初始和增加规则

在目前我们讨论的设计中,提到一个投票轮次的确定问题。不同Proposer发起的投票可以不一定全局递增,而同一个Proposer必须保证自己的发起的新一轮投票编号vote,一定是递增的(增量必须为1吗?这个不一定)。这是因为Acceptor在第一阶段的工作原则是,只接受vote大于当前PrepareVote的新一轮投票授权,那么对于某个Proposer而言,最不济的情况就是无论自己本身如何发起新一轮的投票,都不会得到Acceptor的授权,而最终结果只能听命于别的Proposer所提议的值

这里写图片描述

很显然上图中无论ProposerB如何发起新一轮投票,都会在第一阶段被Acceptor拒绝掉,因为至少有一个Proposer的投票轮次编号一直比他的大。这种算法的简便处理方式虽然一定程度上降低了代码的编写难度,但是只能算作伪算法实现(目前很多系统为了平衡性能、维护性和实现难易度,都会采用这种方式),因为所有投票轮次的发起和赋值只会听从于唯一一个Proposer,在算法的执行过程中根本就不会出现投票冲突的情况;另一个方面,对并发状态下无法最终确认选值的Client来说也不公平,因为所有Client对最终赋值的选择也只会听命于唯一一个Client(忘了说了,Client是整个Paxos中另一个角色,这个角色负责向对应的Proposer提交需要进行表决的提案)。所以我们需要一种投票轮次编号递增的方式,来保证不同轮次的投票请求真正的竞争起来。

有的读者可能第一个想到的就是zookeeper这样的分布式协调器来生成编号,保证编号的唯一性和递增性,甚至很多学术资料、网络文章上都有提到使用这样的方式。拜托!要是能够使用zookeeper解决这个问题,那我们还实现Paxos算法干什么?所有解决冲突的工作都交给zookeeper就好了嘛。之所以要实现Paxos算法,就是因为要建造一个和ZK同属一个工作层的协调组件,所以关于编号的问题就只能自己想办法了。

这里介绍一种对投票轮次的编号方式,可以有效减少编号冲突,并在针提案X的投票过程中真正产生竞争。这个编号方式的前提条件是,各个Proposer工作在局域网环境下,并能通过组播的方式发现对方。在各个Proposer内部有一个使用Proposerid进行排序后的Proposer集合列表。这时就可以通过余数原则进行编号了:

这里写图片描述

(N × V) + index + 1,这个公式中,N表示集合大小,V表示投票轮次(从0开始),index表示当前Proposer所在集合的位置索引。例如,设N==4时,id为1的存在于这个有序集合列表第一个索引位置的Proposer,可以使用的投票编号就是1、5、9、13……,存在于这个有序集合列表第二个索引位置的Proposer,可以使用的投票编号就是2、6、10、14、18……,存在于这个有序集合列表第三个索引位置的Proposer,可以使用的编号就是3、7、11、15、19……

那么这样的编号设计就不会重复了吗?当然会,特别是在整个Paxos算法系统的启动阶段。例如整个Paxos算法中所有N个节点的Proposer都已经启动了,但是某个Proposer上还暂时只发现了N-2个Proposer节点,这样该Proposer计算得出的自己所使用的编号,就可能和另外某个Proposer所计算得出的自己使用的编号重复。而且这个差异还与使用的不同节点发现方式而不同,例如在后续文章中给出的Basic-Paxos算法实现代码中,就使用组播方式进行Proposer节点发现,而这种节点发现方式就会使每个Proposer节点上的节点发现进度在Paxos算法系统启动之初出现不一致。

不过好消息是,Acceptor在第一阶段的工作原则中,只会授权大于当前AcceptedVote的投票申请(此时AcceptedVote <= PrepareVote)。也就是说当两个或者多个持有相同投票伦次的Proposer向同一个Acceptor申请投票授权时,Acceptor只会授权其中一个,另一个的授权申请将被Acceptor拒绝,这就保证了有相同投票轮次编号的授权请求在同一个Acceptor上不会被重复同意,那么这些有同样投票轮次编号的Proposer就可以决定自己是否拿到了授权多数派。如果没有拿到授权,当Proposer集合稳定存在后,就会有新的且更大的投票轮次编号了。

===============
(接下文)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yinwenjie/article/details/61933266

智能推荐

Laravel设置timezone时区_laravel timezone-程序员宅基地

文章浏览阅读1.5w次。Laravel设置timezone时区Laravel框架默认时区是UTC。科普:协调世界时(UTC, Universal Time Coordinated),又称世界统一时间,世界标准时间,国际协调时间。UTC可以简单地理解为伦敦时间。如果想使用北京时间,则找到config/app.php文件`'timezone' => 'PRC',` //将UTC改成PRC_laravel timezone

17个你必须牢记的Win7快捷键_win7智能影像键-程序员宅基地

文章浏览阅读435次。原文地址:http://www.cnblogs.com/xfiver/archive/2010/12/08/1899905.html电脑初学者掌握了盲打技术,可以提高录入速度;游戏玩家掌握了快捷键,可以在瞬息百变的对战中提高生存的机会;而Windows玩家掌握了快捷键,不但可以提高电脑操作速度,更能享受到初级玩家望着你那仰慕的眼神……Top 17 常规快捷键在开始使用Win_win7智能影像键

c盘清理-程序员宅基地

文章浏览阅读140次。C:\ProgramData\Microsoft\Search\Data\Applications\Windows\Windows.edb 必删,Windows search日志 360 清理虽然显示清理,但是无法清理。我的一没留意就29.2G hold不住。彻底删除Windows.edb的方法找到“服务”,将里面的WindowsSearch服务禁用即可。然后删除Windows..._windows search日志 清理

西西弗斯式的命运_西西弗斯式是什么意思-程序员宅基地

文章浏览阅读2.2k次。http://acm.sjtu.edu.cn/OnlineJudge/problem/1004Description古希腊有个关于西西弗斯的神话:西西弗斯被众神判决推运一块石头至山顶。由于巨石本身的重量,它被推到山顶却又总要滚下山脚。于是西西弗斯又得把石块推上山去。如此反复,永无止境,没有尽头。众神认为,让西西弗斯服这永恒的劳役是最严酷的惩罚。二哥被_西西弗斯式是什么意思

【JMeter】总结 jmeter 中各种函数_jmeter中函数-程序员宅基地

文章浏览阅读1.7w次,点赞14次,收藏122次。JMeter 提供了很多函数,可以很方便的实现一些小功能,可以用于测试计划中的任何元件。函数调用的格式如下所示:${__functionName(var1,var2,var3)}其中,__functionName 为函数名,括号内是函数的参数,无参数时可以不用括号,如 ${__UUID}。Tips:如果参数包含逗号,那么一定要使用 \ 来转义,否则 JMeter 会把它当作一个参数分..._jmeter中函数

scikit-learn机器学习(三)--逻辑回归和线性判别分析LDA_lda与逻辑回归-程序员宅基地

文章浏览阅读5.8k次。scikit-learn机器学习(一)–多元线性回归模型 scikit-learn机器学习(二)–岭回归,Lasso回归和ElasticNet回归 scikit-learn机器学习(三)–逻辑回归和线性判别分析LDA前面的线性回归模型是解决预测问题的,根据样本的多个特征,推测其目标值,但是现实生活中除了这种预测问题之外,还有一种问题就是分类问题,比如这个人是否得病,邮件是否为垃圾邮件等..._lda与逻辑回归

随便推点

ext 写的超炫 app 应用管理界面 另一种grid 的实现代码700行 -程序员宅基地

文章浏览阅读77次。全部代码 只有700行 包括树的点击改变应用 应用的过滤 排序 添加 删除 修改 和展示 Q:449237205_手机实现的grid页面

warning: function returns address of local variable详解-程序员宅基地

文章浏览阅读1.4w次,点赞5次,收藏25次。警告:函数返回局部变量.当自己动手写一个局部函数时,如果函数类型有返回值的话,如果返回的是局部变量,则会弹出该警告.因为执行玩该函数,就会释放内存.三种变量的解释:@interface Person : NSObject { // 成员变量: // 写在类声明的大括号中的变量, 我们称之为 成员变量(属性, 实例变量) // 成员变量只能通过对象来访问 ..._function returns address of local variable

SpringBoot集成ElasticSearch对API的实际应用封装(七)_springboot elasticsearch 实际应用-程序员宅基地

文章浏览阅读1.5k次。第一步.添加配置文件在resources创建elasticsearch.yml配置文件并添加一下配置:#elasticsearch集群名称,默认是elasticsearchspring.data.elasticsearch.cluster.name=wali#节点的地址,注意api模式下的端口号是9300,千万不要写成9200等spring.date.elasticsearch.clu..._springboot elasticsearch 实际应用

互联网界产品经理和项目经理_互联网为什么要有项目经理-程序员宅基地

文章浏览阅读4k次。前几日写了一篇博文《》,没想到写了之后很快被广泛转载,也有很多人表达了对文章观点的赞许之意。我想很多看过的(没看过的建议先看一下)网友一定会接下去关心另外一个问题:既然这种产品经理+项目经理的组织结构设置具备很好的优势,如何才能打造这种黄金组合呢?应该说在“如何”这个问题上,还是有很多学问可以展开来说的。不过我忽然想起前几天和原来的一个领导在争论我原来的一个同事能力的问题。我们都一直认为这_互联网为什么要有项目经理

如何让不懂信息化的甲方客户看懂需求文档,并确认签字?_需求规格书确认-程序员宅基地

文章浏览阅读2.6k次。需求规格书编写完成后如何让客户快速、顺利地确认签字?这是个常见问题,每个软件项目经理和需求工程师都遇到过,要解决这个问题要从甲方客户与软件工程师两个方面进行分析和找答案。从客户方面看,存在两个问题:一是要看得懂需求文档、二是要能放心地签字。提出需求的客户可能不是软件方面的专家,他是从自己熟悉的业务视角提出的需求,但他可能不清楚这个需求实现后的应用模式(原型、操作等),担心自己考虑不周签了字,待开发完成后与设想不同时要担责任,所以迟迟不肯签字(人之常情)。_需求规格书确认

1.8-Sentinel系统规则_rt 阀值类型-程序员宅基地

文章浏览阅读767次。1、系统规则设置通过Sentinel Dashboard控制台左侧菜单【系统规则】管理,新增系统保护规则如下所示:2、四种阈值类型说明Load-阈值类型当系统load1(1分钟平均负载)超过阈值,且并发线程数超过系统容量时触发,建议设置为系统CPU核心数 * 2.5;仅对Linux/Unix系统有效。其中的load1,可以在Linux系统上通过命令 uptime 查看:这个命令返回3个值,分别为load1、load5、load15,表示系统1分钟的平均负载、5分钟的平均负载、1_rt 阀值类型