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之后，这并没有违背线性一致性的要求。

“幽灵复现”问题其实是由于Oceanbase对复制状态机的实现方式导致的问题，郁白的文章中没有介绍全部的背景，所以让读者有些难以理解了。Oceanbase使用Multi-Paxos来同步数据库的redo log，事务修改持有行锁，但加行锁并不会生成redo log。

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

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

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

所以，问题的原因在于Oceanbase不是一个标准的复制状态机的实现，复制状态机在日志同步成功后才会应用日志修改状态机，这样保证了 切主后状态机一定不会回退 。但Oceanbase的实现中加行锁是没有写redo log的，但行锁也是一种状态，所以才导致切主后行锁丢失，引发了问题。

交错Leader

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

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

参考资料

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

浏览: 2