记录学习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。如果此时随意指定值,就会破坏已经达成的共识。
暂无评论内容