分类: 分布式系统

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号日志同步到多数派,此时再查询,就可以查询到之前客户端写入的结果了。

问题出在哪?


“幽灵复现”这个现象在工程实践中毫无疑问是一个需要注意的问题,但我认为这个问题并不是分布式共识(Consensus)本身的问题,而是上层逻辑导致的一致性(Consistency)问题。

让我们重温Paxos算法的正确性条件:

  • 只有被提出(propose)的值才可能被最终选定(chosen)
  • 只有一个值会被选定(chosen)
  • 进程只会获知到已经确认被选定(chosen)的值

在前面描述的问题场景中,虽然存在“幽灵复现”的Paxos instance,但实际上这些instance在“复现”之前从来没有达成共识(chosen),也就是说,不论查询这些日志是“消失”还是“复现”,都没有违背分布式共识算法的safety属性。

那么是复制状态机的问题么?也不是。按照上例分析并发操作的一致性表现:刚开始客户端在A上写操作w1超时,但并没有返回客户端执行成功,之后在B上执行读操作r2看不到w1的执行结果,说明r2的生效时间排在了w1前面,最后在A上发起的读操作r3看到了w1的执行结果,说明r3的生效时间在w1之后,这并没有违背线性一致性的要求。

“幽灵复现”其实是在使用Multi-Paxos来同步数据库redo log的场景下产生的问题,郁白的文章中没有介绍全部的背景,所以让读者有些难以理解了。Oceanbase是一个关系型数据库系统,使用Multi-Paxos来同步数据库的redo log,使用的是WAL(Write Ahead Logging),即保证在持久化数据修改前,对应的redo log要先持久化完成。

基于关系数据库的场景,我们重新解释前面的例子。

刚开始A是Leader,客户端发起事务trx1,先显式对数据x加锁(for update)并收到数据库响应成功,再修改数据x为1,但在redo log同步到多数派之前宕机。之后B当选为Leader,客户端发起事务trx2查询x(for update),读出x为0(意味着没有读到行锁),因此客户端认为trx1的结果是失败回滚。最后A再次成为Leader并完成redo log的同步,此时再客户端发起事务trx3查询x,读出x为1,trx1的结果又变成了成功提交。

显然,这个执行结果违背了线性一致性的要求,并且这样的行为会导致数据库非常难以使用。

所以,问题的原因在于关系型数据库redo log的同步模式和复制状态机的日志同步模式是不同的,复制状态机在日志同步成功后才会应用日志修改状态机,这样保证了切主后状态机一定不会回退。但关系型数据库的WAL实际上是先修改“状态”后持久化redo log的,所以才导致切主后行锁丢失,引发了问题。

交错Leader


文章开头的例子和郁白原文中例子略有不同,原文中在B成为新的Leader后重写了6号和20号日志,A再次成为Leader后同步了7-10号日志,这个实际上是被我们称为“交错Leader”的问题,即虽然每个Paxos instance都没有违背共识,但在数据库场景中使用redo log的上层逻辑来看,日志却变成了没有意义的:如果1-10号日志是同一个事务的日志,达成共识的日志序列中6号日志却被修改了。

“交错Leader”和“幽灵复现”问题都可以通过提高EpochId,写StartWorking日志过滤的方法解决。

参考资料


  • 《架构师需要了解的Paxos原理、历程及实战》 李凯