Paxos与“幽灵复现”

Paxos被公认是难度很高的分布式共识算法,一方面是体现在理解其算法正确性的难度上,而另一方,体现在工程实现的复杂度上。在将Paxos算法运用在工程实践的过程会遇到各种各样的问题,本文要探讨的“幽灵复现”问题,就是其中一例。

什么是“幽灵复现”


据我所知,所谓的“幽灵复现”问题是Oceanbase团队在实现Multi-Paxos过程中自己提出的,并随着郁白的一篇知名博文的传播被大家所知晓。这里先简单介绍一下问题场景:

使用有Leader lease(避免活锁,leader读写提供线性一致性)的Multi-Paxos来实现复制状态机,刚开始A是Leader,客户端执行操作写1-10号日志,1-5号日志形成多数派,但是6-10号日志没有同步到其他副本,客户端超时。

之后A宕机,B成为新的Leader,由于联系不到A,B和C作为多数派从6号日志开始工作,此时查询不到先前客户端在A上写的结果(6-10号日志没有同步成功)。

最后A再次成为Leader,并成功把之前的6-10号日志同步到多数派,此时再查询,就可以查询到之前客户端写入的结果了。

继续阅读: