Paxos算法学习疑问记录

记录学习Paxos算法时遇到的疑问和思考。
相关笔记: Paxos算法学习笔记 Paxos算法的数学归纳法证明

概念

为什么说Paxos是唯一的共识算法

There is only one consensus protocol, and that's "Paxos"
all other approaches are just broken versions of Paxos

我想这不是因为Paxos复杂,而是因为Paxos最为简单。
1. Paxos只管达成共识,而且只达成一个。
2. Paxos不关心状态机,日志状态机等业务问题。(我想,加上日志状态机后才属于分布式一致性算法)
3. Paxos是原生多点写,不需要考虑选主。
相比之下,Mulit-Paxos,Raft等工程化的算法,都加入了某些条件和假设。所以可以认为其它算法是它的派生。

多点写的问题

有一些工程上的实现,把多个Leader分摊到不同节点,实现多点写。严格来说,需要唯一Leader的设计中,Leader就是单点
Paxos中并没有Leader的存在,Acceptor是同等的,因此它不存在单点,是真正的多点写。

Paxos的麻烦

多点写同样是Paxos的麻烦,多个Proposal的提案会存在争抢,所以不得不设计成2阶段提交。
如果Proposor只有一个,就不需要做Prepare的动作,可以一阶段提交。

算法

一个错误的共识读取方法分析

描述

# 错误方法
既然分布式共识最终的要求是决议形成多数派,何不直接广播所有Acceptor,找出多数派的决议,这个决议肯定就是共识。
错误方法(广播读取共识)的流程

Proposor广播读取请求给所有Acceptor,Acceptor返回当前提案,Proposor从返回信息中找出多数派。如果没有多数派,则还未形成决议。

分析

正常情况下,这个方法是正确的,但存在一个问题场景。假设5个Acceptor节点。
1. 一个Proposor走完Prepare阶段,在Accept阶段时挂了
2. 此时3个Acceptor已经批准提案,假设是1-3号节点。

首先,对于Client来说,共识没有达成。无论后面达成什么共识,都是合理的。因为这个时候失败了,有可能是达成了决议但返回决议内容时失败,可重新读取确认。

直接广播读取共识

这种读取方式存在问题。
1. 假设读取时,节点没宕机,共识读取成功。
2. 马上服务器宕机了。
3. 再次读取共识,发现共识没有达成。
4. 也可能再次读取时,达成别的共识了。

这是不能容忍的错误。

使用Paxos流程读取共识为什么是可靠的

因为走了Paxos完整流程,Paxos流程已经被证明达成的共识不会被改变。
如果Prepare阶段返回的多数派Promise中共识内容相同,则可以省略Accept阶段直接返回。相比广播读取的方式,在Accept阶段可以保证部分节点异常时,依然可以读出共识

算法中Prepare阶段的作用

Paxos的第一阶段就像是去上一个可以被抢占的锁
如果这个锁不能被随意抢占呢。假设第一阶段Acceptor接收到ProposalID后,Accptor只接受这个ProposalID的提案,Prepare阶段的锁只能超时释放。这样就可以避免活锁。
Mulit-Paxos是类似的做法,Leader就好像一个手持锁的Proposor。

为什么如果proposalValue不是NULL,就不能随意指定值

因为Paxos算法中,即使已经形成多数派,如果提案的PrposalID更大,Acceptor依然会接受新的PrposalID
显然,多数派的ProposalID会小于当前的ProposalID。如果此时随意指定值,就会破坏已经达成的共识。

© 版权声明
THE END
广告
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情

    暂无评论内容