知识分享 – paxos选举出一个leader解决活锁,可是如果在存在leader为什么要使用paxos?

解答题主的疑惑,需要先了解引入Leader的推导过程(即multi-paxos的推导过程),跟题主明确两个概念,basic-paxos(存在活锁)、multi-paxos(引入Leader)。

推导过程

我们知道basic-paxos存在活锁,并且需要两个阶段才能达成共识。因为这两个局限,我们推导出multi-paxos。

活锁(引入Leader)

活锁导致原因是因为,存在多个proposer发起提案,导致多个提案之间互相干扰,使得最终没有任何提案达成共识。

解决这个问题,最简单的方案,自然是引入(并非一个)权威的成员,即Leader,只允许权威的成员发起提案。减少了发起提案成员的数量,提案相互干扰的概率自然也会降低。

而这里提到的Leader,并非是一个全局唯一的强Leader,与题主理解的Leader稍有不同,在multi-paxos中允许存在同时存在多个Leader,如果引入一个强Leader,那确实有其他的算法可以替代,例如:Raft。所以在multi-paxos中,Leader是一个集合,它是Proposer的子集。

因为多个Leader同时存在的缘故,Leader仅仅是为了降低活锁的概率,因此并不能完全规避活锁。

另外,同时存在多个Leader会不会影响算法的正确性?不会,只要每个Leader按照preare → accept执行协商过程,最终正确性仍然可以保证,因为拥有最高的提案编号的多数派最多只会有一个,而其他更低提案编号的提案将不会达成共识。

需要两个阶段才能达成共识(省略prepare)

引入Leader后,我们可以很快的观察到,当没有提案干扰(即:只存在一个Leader)的情况,prepare阶段是非必须的。

因为prepare阶段是用来协商提案编号的,而协商提案编号的目的是为了争取该提案编号发起提案的所有权。当只有一个Leader A存在的情况,没有其他成员和该Leader A争取发起提案的所有权,所以Leader A可以直接进入accept阶段,而跳过prepare阶段。当其他Leader B获取下一个提案编号的所有权后,那么Leader A的accept阶段,就不会获取到多数派的支持,从而重新进入prepare阶段。

而这就是multi-paxos的协商过程。

正文完