A-A+

SDPaxos 优雅的折中

2018年10月27日 分布式系统 暂无评论 阅读 62 次
摘要:

SDPaxos在Strong Leader和Leaderless中间做了一个优雅的折中,使得协议远比EPaxos清晰,但又支持了损失很小的多点并发复制。

// 大半夜on-call没事干,写点东西。

SDPaxos: Building Efficient Semi-Decentralized Geo-replicated State Machines (SOCC18')

有幸跟作者赵汉宇博士做了一次交流,我也仔细读了一遍论文原文,读完最大的感受是,SDPaxos在Strong Leader和Leaderless中间做了一个优雅的折中,使得协议远比EPaxos清晰,但又支持了损失很小的多点并发复制。

这里仅描述下SDPaxos的设计选择。协议的细节和大量的分析,有感兴趣的同学,可以直接看原始论文,论文写得很清晰(真是比EPaxos写得清晰太多了),读完应当很有收获。

sdpaxos

从对Leader的依赖这个角度看,SDPaxos在Design Space/Spectrum中选择了中间的一个折中位置。

左起Raft强依赖leader,例如在选举时必须选择在某个多数派中拥有最新日志的节点。左二Multi-Paxos的liveness/progress依赖stable leader,但协议正确性不依赖。跳过SDPaxos,右二Mencius让每个节点轮流propose command,例如三副本configuration下,replica 0 propose slot 1,4,7...3x+1...的command。最右EPaxos最为极端,任意节点propose command,冲突的command在replication过程中检测并确定顺序。

 

SDPaxos的折中是,command order仍由单点确定,但各副本都可以propose和replicate command。

20181027225642

做个比喻,Raft就像是苏联的社会主义计划经济,ordering/replicating都由中心节点来管理,EPaxos就像资本主义市场经济,各个replica充分竞争,自行解决ordering问题。SDPaxos就像是社会主义市场经济,ordering由单点的sequencer来确定,replicating由各个副本来做。

 

SDPaxos相比EPaxos的优点,简单地说,SDPaxos相比EPaxos清晰太多,因此优势非常显著:

(1) 协议可理解性:SDPaxos清晰的多。举几个EPaxos中很不直观的地方:EPaxos fast quorum是\mathcal{F} = F+\lfloor \frac{F+1}{2}\rfloor;采用的是thrifty模式,只能向特定几个replica发送accept request;accept request要携带dependency信息。

(2) 协议CPU开销:SDPaxos CPU开销低,基本跟Raft/Multi-Paxos所需的开销接近。EPaxos有大量处理dependency的key检测,会消耗大量的CPU。

(3) 落地实现难度:同样是因为复杂性,EPaxos协议在工程上很难落地,就EPaxos的recovery逻辑,几乎很难实现一个生产环境可用的正确版本,但SDPaxos就容易的多。

(4) 正确性直觉:虽然EPaxos也经过了论证和TLA+证明,但考虑到TLA+证明过程本身的可靠性,要说EPaxos协议没有正确性bug,并不能容易结接受。相反,受益于SDPaxos协议的清晰,接受SDPaxos正确性在直觉上容易的多。

 

给我留言