A-A+

重新审视Paxos协议的Quorum问题

2017年01月05日 分布式系统 暂无评论 阅读 213 次
摘要:

Flexible Paxos: Quorum intersection revisited 这篇论文重新审视了Paxos中关于Quorum的问题。在Basic Paxos中,要求任何quorum都有交集(通常选择多数派作为quorum)。事实上,这个要求可以放宽到Paxos的两个阶段prepare/accept阶段的quorum有交集即可。文中描述了majority, simple, grid三种quorum system。

Flexible Paxos: Quorum intersection revisited 这篇论文重新审视了Paxos中关于Quorum的问题。在Basic Paxos中,要求任何quorum都有交集(通常选择多数派作为quorum)。事实上,这个要求可以放宽到Paxos的两个阶段prepare/accept阶段的quorum有交集即可。

我们从Basic Paxos证明过程简单描述为什么放宽后算法依然正确(原论文最后给了一个TLA+的形式化证明)。

在前文Basic Paxos证明过程中,我们看到,Theorem 1的证明关键点在于\exists B\triangle\in (C_{qrm} \cap B_{vot}) B\triangle 的存在,使得如果后续的Ballot C想投票,则在prepare阶段,一定会通过MaxVote(C_{bal}, C_{qrm}, \mathcal{B}) 问到Ballot B投的dec。

那么,在Basic Paxos协议中,\exists B\triangle\in (C_{qrm} \cap B_{vot})条件之所以成立,是因为  B_{qrm} \subseteq B_{vot} 并且  B_{qrm} \cap C_{qrm}\neq \emptyset

由此我们可以知道,Basic Paxos协议要求任何quorum都是有交集是保证Paxos协议正确性的充分不必要条件。我们可以把约束放宽到 C_{qrm} \cap B_{vot} \neq \emptyset 即可。

 

这个条件表达的意思是,prepare阶段和accept阶段的quorum交集不空即可。文中称这种协议为Flexible Paxos。

放宽的方式可以多种多样。论文描述了几种可能的方式。为行文描述方便,prepare阶段的quorum记为Q1,accept阶段的则记为Q2。

第一种,Majority quorums

也是多数派的约束,但是跟Basic Paxos略有差别。在Basic Paxos中,要求两个阶段的quorum都至少是n/2+1。这里可以放宽为,如果n是偶数,Q1为至少是n/2+1,Q2至少是n/2。n是奇数的话,不能按这种方式放宽。

如果正好n/2的机器宕机了,Multi Paxos中,只要leader仍然活着,accept阶段可以继续progress(注,Multi Paxos协议中,prepare请求为从某个instance之后的所有的无穷多个instance做prepare)。不过如果leader宕机了,Mutli Paxos需要重新执行prepare阶段时,也是无法进行下去的。

 

第二种,Simple quorums

在第一种majority quorumns基础上继续的一个泛化,把条件改为 |Q1| + |Q2| > N。

这种方式下,Q1如果设大,Q2就可设小一点。那么,accept阶段就可以减少需要同步的节点数,只是leader宕机后重新prepare时就只能容忍较少的节点宕机。反之,accept阶段需要同步的节点更多,但重新prepare时只需要较少的节点在线。

这种quorum跟Dynamo的NRW方案很像:数据被冗余N份,写操作只写其中的W份,读操作只读取R份,如果W+R>N,则一定能不会漏掉早于读取前完成的写结果。Paxos也是类似,在prepare阶段也一定要获取到可能已经被确认的决议的值。

 

第三种 Grid quorum

Grid quorum system:将N个节点分为N=N1*N2的矩阵。

Paxos要求任意两个quorum都有交集。因此在grid quorum system里,Paxos可以选择quorum为一行加一列。任意两个quorum都有交集,如左图。这种选择最多允许任意MIN(N1,N2)个节点宕机,即宕机一整行或者一整列就会导致协议走不下去。假设蓝色表示Q1,绿色表示Q2。

grid

在Flexible Paxos协议下,根据Q1和Q2交集不空的约束,Q1可以为一行大小N1,Q2可以为一列大小N2。这样,正常运行无宕机时,只需要同步N2个节点即可。

需要指出的是,与simple quorum system不一样,grid quorum system下,节点本身不再是完全对等的。例如在上图中,4个节点宕机,左图prepare和accept阶段都无法推进,但是右图中,如果4个节点在同一列,则accept阶段可以继续推进,只要不需要进行prepare阶段,系统仍可持续服务。

 

 

给我留言