搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > 李博洋的杂货铺 > paxos 协议更新日志流程

paxos 协议更新日志流程

李博洋的杂货铺 2017-11-01
举报

基于Paxos协议的数据同步与传统主备方式最大的区别在与Paxos只需任意超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。

Basic paxos协议更新日志

我们将数据持久化的需求抽象为:在N个server的机群上,持久化数据库或者文件系统的操作日志,并且为每条日志分配连续递增的logID,我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。

将每条日志的持久化流程都看作一个“Paxos Instance”,不同的logID代表不同的Paxos Instance形成的“决议(decision)”。即每一个logID标识着一轮完整paxos协议流程的执行,最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。

获取LogID

Server收到客户端的持久化日志请求后,因此向所有acceptor查询它们本地目前已写盘的最大logID,而只需收集到majority返回的结果,并选择其中最大的logID+1作为本次待持久化日志的logID。

从上面的描述可以看出,这里并不能保证并发提交的两条日志一定被分配到不同的logID,而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。

产生ProposalID

这里我们使用server的timestamp联合ip作为proposalID,其中timestamp在高位,ip在低位。(为了唯一卫衣proposalID,只要要求时钟的误差范围小于server重启的时间)

Prepare阶段

只有在这个Paxos Instance内(即针对这个logID)没有response过proposalID大于等于当前proposal的,并且也没有“接受(accept)”过proposalID大于当前proposal的,才可以response,并承诺不再accept那些proposalID小于当前proposal的。

上面Prepare阶段的处理流程暗示,对于分配到相同logID的不同日志,由于他们的proposalID不同,acceptor在response一个较小proposalID后,是允许继续response后来的较大的proposalID的。

Accept请求阶段

如果majority的response中的日志内容都为空,那么可以向所有acceptor发出accept request并携带上当前日志内容;而如果有任意的response中的日志内容有效,那么说明当前logID已经别其他日志占用,因此需要回退,回到第一步“获取logID”重新执行。

Accept执行阶段

而如果ProposalID小于当前最大minProposal的,则说明有logID切proposalID更大的proposal在并发执行,当前proposal会被覆盖,因此回复proposer要求回退到第一步“获取logID”重新执行。

这里的流程暗示,针对一个logID,如果之前已经有日志内容持久化成功,那么这条日志一定会被选为accept request;而如果之前日志内容仅仅在小于半数的server上写到磁盘,那么最终这条logID的内容有可能是有效日志,也有可能内容为空。(本例中可能两个提议者竞争一个logID,然后本例中为了加快收敛,其中一个自动放弃,选择更大的logID)

日志内容读取

在读取的时候也需要回放一遍paxos协议,防止读到未提交的日志(相当于raft的提交阶段?)。

为什么需要comfirm日志

假设有a, b, c 3个节点, 刚开始的时候, 3个节点的值是一致的, 都是v1. 这时候一个proposer发起一轮paxos请求, 希望将值设置成v2. 那么可能出现两种情况, 一种是paxos成功了, a, b, c的多数派中value设置成了v2, 也就是说v2被批准了(假设a, b, c的值分别是v1, v2, v2). 另外一种是失败了, a, b, c的多数派中value仍然是v1, 也就是说v2没有被批准, 但是a, b, c中可能存在少数派节点的值是v2(假设a, b, c的值分别是v1, v1, v2). 按照p2a的流程, 选取proposal的原则是选取多数派中, proposal号最大的作为期望被批准的value. 在上述两种情况下, 当reader读取数据时, 按照p2a的逻辑, 既可能读到v1, 也可能读到v2, 那这样的话, 如果有一个acceptor故障了, 其实reader就无法准确知道之前被批准的value了吧? 我看paxos made simple的论文中也提到, 如果有一个acceptor故障了, 也不可能找出被批准的value了, 唯一的办法就是issue a proposal, 然后运行一轮新的paxos算法了。这是不是说, 不管reader读到的是v1还是v2, 仍然发起一轮paxos协议, 保证一致性就ok了

Multi-paxos更新日志

Leader的产生

通过Multi-paxos,我们可以简化掉产生logID阶段和prepare阶段,而是由唯一的leader产生logID,然后直接执行accept,得到多数派确认即表示redolog同步成功。

首先,需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志,它允许有多个“自认为是leader的server”来并发生成日志,这样的场景即退化为Basic-Paxos。

Leader产生并不是走完一个完整的basic paxos流程,而是只走了proposal prepare阶段,所以可能同时产生多个leader。因此,我们需要先写一条StartWorking日志,成功写下这条日志升级为唯一leader

confirm日志优化

因为在读取日志的时候,需要再进行一次basic paxos协议。因此引入confirm日志,针对刚刚提交的日志写入一条confirm日志。出于性能考虑,实际操作中,批量发送confirm日志,因此,读到未确认的日志,还是需要走一遍paxos协议

新任leader对日志的重确认

新任leader可能保存的日志落后于前任leader,因此需要对小于当前集群中max log id的日志都进行。这样的结果可能超越了前任已经accept的日志记录,称为最大commit原则。

“幽灵复现”日志的处理

使用Paxos协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象,如下图所示:

x Leader A B C
第一轮 A 1-10 1-5 1-5
第二轮 B 宕机 1-6,20 1-6,20
第三轮 A 1-20 1-20 1-20
  1. 第一轮中A被选为Leader,写下了1-10号日志,其中1-5号日志形成了多数派,并且已给客户端应答,而对于6-10号日志,客户端超时未能得到应答。

  2. 第二轮,A宕机,B被选为Leader,由于B和C的最大的logID都是5,因此B不会去重确认6-10号日志,而是从6开始写新的日志,此时如果客户端来查询的话,是查询不到6-10号日志内容的,此后第二轮又写入了6-20号日志,但是只有6号和20号日志在多数派上持久化成功。

  3. 第三轮,A又被选为Leader,从多数派中可以得到最大logID为20,因此要将7-20号日志执行重确认,其中就包括了A上的7-10号日志,之后客户端再来查询的话,会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。

对于将Paxos协议应用在数据库日志同步场景的情况,“幽灵复现”问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。

为了处理“幽灵复现”问题,我们在每条日志的内容中保存一个generateID,leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时,因为leader在开始服务之前一定会写一条StartWorking日志(先同步再写StarWorking日志),所以如果出现generateID相对前一条日志变小的情况,说明这是一条“幽灵复现”日志(它的generateID会小于StartWorking日志),要忽略掉这条日志。

 其中,log1和log6分别是第一轮和第二轮的start working log。

本质上是通过在发生leader权抢占的时候,ProposalID的递增性质保证了不会回放以前的logID。

multi-paxos和raft对比

以下是我自己的观点,不保证正确性

  1. raft logID递增,multi_paxos并不需要

  2. multi_paxos为了保证读到的日志已经提交,需要再走一边paxos确认日志;raft每次获得多数派的认可后,也需要向参与者发送提交命令(相当于读取命令)。

  3. 因为multi-paxos的logID不连续,在leader权抢占的时候,所以有了最大commit原则,最大commit原则可能产生幽灵日志,如果epochID小于上一条,就不回放,所以有了不回放上一个任期的日志。


版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《paxos 协议更新日志流程》的版权归原作者「李博洋的杂货铺」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注李博洋的杂货铺微信公众号

李博洋的杂货铺微信公众号:liboyang0730

李博洋的杂货铺

手机扫描上方二维码即可关注李博洋的杂货铺微信公众号

李博洋的杂货铺最新文章

精品公众号随机推荐

举报