第七页笔记开始通过另一个示例来演示Paxos算法是如何处理不同Proposer提出相同编号提案的问题,也是这个算法容错性的一种体现,同时会讲述一些细节。
关键词:Proposer、Acceptor、Proposal和两个阶段。
由于隐含约束2的存在,Acceptor收到的提案编号会产生重复,这点在第四页笔记中已经介绍了获取提案编号的方式。
提案编号可以由Proposer自己产生,但是考虑到分布式环境中一定存在不止一个Proposer,所以如果每个Proposer都自顾自的生成编号,那么产生冲突的概率就会很高。虽然是用一致的策略进行编号生成,但是如果没有通过协商就进行编号生成,会显得比较随意,所以在每次编号生成前,可以选择咨询多数的Acceptor(s),由此来确定一个合适的编号。
假设在一个多Proposer的环境中,如果相同提案编号的Prepare请求发送到Acceptor会有什么效果呢?这里就要详细的讨论一下第四页笔记中遗留的M = N
的问题了。
先要明确一个前提,每个Proposer都会给多数的Acceptor(s)发送Prepare请求,所以一定存在一个Acceptor集合,它们会接受到多于两次的Prepare请求,只是在绝对时间的一前一后而已。
考虑如下场景:存在2个Proposer和5个Acceptor,Proposer会将Prepare请求发往多数(示例中为3个)Acceptor(s),这个交集就是A3。我们考虑A1的Prepare请求先到达A3,然后当先收到的提案已经被批准为提案时,如下图:
可以看到A3时间线上的蓝点是一个关键点,这个点之后,相同编号的提案,先前A3收到的(A1的提案),已经成为了决议。此时,如果收到了A5的Prepare请求,按照原有算法描述,可以直接忽略,不回复,但是出于效率,不应该这么做。
如果不进行回复,A1的提案已经成为决议,多数Acceptor(s)认可,但是A4和A5并不知晓,A5作为Proposer只会在那里傻等。要解决这种死锁,就需要Proposer具备一种自我超时机制,如果提案经过一段时间还没有收到足够的反馈,就查询一下多数**Acceptor(s)**的提案状况,如果发现已经在讨论更新的提案了,就废弃掉当前提案,然后重新发起提案。
默认的算法逻辑只能如此处理,但是如果假设允许A3返回一个Promise,其值是Ignore,则会使得该过程的活性得以提升,同时这部分逻辑不用依靠超时机制。
这是在决议形成之后,也就是已经收到了来自A1的Accept请求后,收到来自A5的Prepare请求。如果在A1的提案还没有变为决议前收到呢?如下图:
可以看到,A3依旧会采纳A1的提案,原因是约束1的存在。A3会回复A1和A5值为Suggest的Promise,建议双方使用已有的提案,也就是A1的提案。
对于Acceptor其实做法比较简单,如果存在了这个提案编号,则拿出已有的提案,同时通知当前提案的A5和已有提案者A1,通知两位相关的建议。如果A1和A5的两个Prepare请求很近,则需要Acceptor支持事务性,一定能够确保一个时刻,只能添加一个相同编号的提案。
对于Acceptor接收到Prepare请求,如果M = N
的场景就应该这么多了,现在我们可以完整的描述一下这块逻辑了。假设:Acceptor存在proposalDAO
和resolutionDAO
用于访问它的提案列表和决议列表,Proposal.no
表示提案编号,Proposal.proposer
表示提案的Proposer,Resolution.proposalNO
表示决议对应的提案编号。
Acceptor接收Prepare请求的步骤如下:
Promise receiveProposal(Proposal p) {
// 拿到最新的决议
Resolution localResolution = resolutionDAO.findLasted();
// 提案已经是决议了
if (localResolution.proposalNO >= p.no) {
return Promise.of(Ignore);
}
Proposal localProposal = proposalDAO.findLasted();
if (localProposal.no > p.no) { // 本地提案新,需要提醒中止
return Promise.of(Abort);
} else if (localProposal.no == p.no) { // 相同给出建议
return Promise.of(Suggest);
} else {
// 考虑并发控制,如果冲突,则重试
boolean result = proposalDAO.insert(p);
if (result) {
return Promise.of(Agree);
} else {
return receiveProposal(p);
}
}
}
对于Acceptor的提案列表控制,如果出现插入失败,表明已经有相同编号的提案插入成功,则需要进行重试。