关于Paxos 幽灵复现问题的看法

34次阅读

共计 3136 个字符,预计需要花费 8 分钟才能阅读完成。

由于郁白之前写的关于 Multi-Paxos 的文章流传非常广, 具体地址: http://oceanbase.org.cn/?p=111 原文提出了一个叫 ” 幽灵复现 ” 的问题, 认为这个是一个很诡异的问题, 后续和很多人交流关于一致性协议的时候, 也经常会提起这个问题, 但是其实这个问题我认为就是常见的 ” 第三态 ” 问题加了一层包装而已.
幽灵复现问题
来自郁白的博客:
使用 Paxos 协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象,如下图所示:

Leader
A
B
C

第一轮
A
1-10
1-5
1-5

第二轮
B
宕机
1-6,20
1-6,20

第三轮
A
1-20
1-20
1-20

第一轮中 A 被选为 Leader,写下了 1 -10 号日志,其中 1 - 5 号日志形成了多数派,并且已给客户端应答,而对于 6 -10 号日志,客户端超时未能得到应答。
第二轮,A 宕机,B 被选为 Leader,由于 B 和 C 的最大的 logID 都是 5,因此 B 不会去重确认 6 -10 号日志,而是从 6 开始写新的日志,此时如果客户端来查询的话,是查询不到 6 -10 号日志内容的,此后第二轮又写入了 6 -20 号日志,但是只有 6 号和 20 号日志在多数派上持久化成功。
第三轮,A 又被选为 Leader,从多数派中可以得到最大 logID 为 20,因此要将 7 -20 号日志执行重确认,其中就包括了 A 上的 7 -10 号日志,之后客户端再来查询的话,会发现上次查询不到的 7 -10 号日志又像幽灵一样重新出现了。

对于将 Paxos 协议应用在数据库日志同步场景的情况,幽灵复现问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。
为了处理“幽灵复现”问题,我们在每条日志的内容中保存一个 generateID,leader 在生成这条日志时以当前的 leader ProposalID 作为 generateID。按 logID 顺序回放日志时,因为 leader 在开始服务之前一定会写一条 StartWorking 日志,所以如果出现 generateID 相对前一条日志变小的情况,说明这是一条“幽灵复现”日志(它的 generateID 会小于 StartWorking 日志),要忽略掉这条日志。

第三态问题
第三态问题也是我们之前经常讲的问题, 其实在网络系统里面, 对于一个请求都有三种返回结果

成功
失败
超时未知

前面两种状态由于服务端都有明确的返回结果, 所以非常好处理, 但是如果是第三种状态的返回, 由于是超时状态, 所以服务端可能对于这个命令是请求是执行成功, 也有可能是执行失败的, 所以如果这个请求是一个写入操作, 那么下一次的读取请求可能读到这个结果, 也可能读到的结果是空的
就像在 raft phd 那个论文里面说的, 这个问题其实是和 raft/multi-paxos 协议无关的内容, 只要在分布式系统里面都会存在这个问题, 所以大部分的解决方法是两个

对于每一个请求都加上一个唯一的序列号的标识, 然后 server 的状态机会记录之前已经执行过序列号. 当一个请求超时的时候, 默认的 client 的逻辑会重试这个逻辑, 在收到重试的逻辑以后, 由于 server 的状态机记录了之前已经执行过的序列号信息, 因此不会再次执行这条指令, 而是直接返回给客户端
由于上述方法需要在 server 端维护序列号的信息, 这个序列号是随着请求的多少递增的, 大小可想而知(当然也可以做一些只维护最近的多少条序列号个数的优化). 常见的工程实现是让 client 的操作是幂等的, 直接重试即可, 比如 floyd 里面的具体实现

那么对应于 raft 中的第三态问题是, 当最后 log Index 为 4 的请求超时的时候, 状态机中出现的两种场景都是可能的

所以下一次读取的时候有可能读到 log Index 4 的内容, 也有可能读不到, 所以如果在发生了超时请求以后, 默认 client 需要进行重试直到这个操作成功以后, 接下来才可以保证读到的写入结果. 这也是工程实现里面常见的做法
对应于幽灵问题, 其实是由于 6 -10 的操作产生了超时操作, 由于产生了超时操作以后, client 并没有对这些操作进行确认, 而是接下来去读取这个结果, 那么读取不到这个里面的内容, 由于后续的写入和切主操作有重新能够读取到这个 6 -10 的内容了, 造成了幽灵复现, 导致这个问题的原因还是因为没有进行对超时操作的重确认.
回到幽灵复现问题
那么 Raft 有没有可能出现这个幽灵复现问题呢?
其实在早期 Raft 没有引入新的 Leader 需要写入一个包含自己的空的 Entry 的时候也一样会出现这个问题
Log Index 4,5 客户端超时未给用户返回, 存在以下日志场景

然后 (a) 节点宕机, 这个时候 client 是查询不到 Log entry 4, 5 里面的内容

在 (b) 或(c) 成为 Leader 期间, 没有写入任何内容, 然后(a) 又恢复, 并且又重新选主, 那么就存在一下日志, 这个时候 client 再查询就查询到 Log entry 4,5 里面的内容了

那么 Raft 里面加入了新 Leader 必须写入一条当前 Term 的 Log Entry 就可以解决这个问题, 其实和之前郁白提到的写入一个 StartWorking 日志是一样的做法, 由于(b), (c) 有一个 Term 3 的日志, 就算(a) 节点恢复过来, 也无法成了 Leader, 那么后续的读也就不会读到 Log Entry 4, 5 里面的内容

那么这个问题的本质是什么呢?
其实这个问题的本质是对于一致性协议在 recovery 的不同做法产生的. 关于一致性协议在不同阶段的做法可以看这个文章 http://baotiao.github.io/2018/01/02/consensus-recovery/
也就是说对于一个在多副本里面未达成一致的 Log entry, 在 Recovery 需要如何处理这一部分未达成一致的 log entry.
对于这一部分 log entry 其实可以是提交, 也可以是不提交, 因为会产生这样的 log entry, 一定是之前对于这个 client 的请求超时返回了.
常见的 Multi-Paxos 在对这一部分日志进行重确认的时候, 默认是将这部分的内容提交的, 也就是通过重确认的过程默认去提交这些内容
而 Raft 的实现是默认对这部分的内容是不提交的, 也就是增加了一个当前 Term 的空的 Entry, 来把之前 leader 多余的 log 默认不提交了, 幽灵复现里面其实也是通过增加一个空的当前 Leader 的 Proposal ID 来把之前的 Log Entry 默认不提交
所以这个问题只是对于返回超时, 未达成一致的 Log entry 的不同的处理方法造成的.
在默认去提交这些日志的场景, 在写入超时以后读取不到内容, 但是通过 recovery 以后又能够读取到这个内容, 就产生了幽灵复现的问题
但是其实之所以会出现幽灵复现的问题是因为在有了一个超时的第三态的请求以后, 在没有处理好这个第三态请求之前, 出现成功和失败都是有可能的.
所以本质是在 Multi-Paxos 实现中, 在 recovery 阶段, 将未达成一致的 Log entry 提交造成的幽灵复现的问题, 本质是没有处理好这个第三态的请求。
一站式开发者服务,海量学习资源 0 元起!
阿里热门开源项目、机器学习干货、开发者课程 / 工具、小微项目、移动研发等海量资源;更有开发者福利 Kindle、技术图书幸运抽奖,100% 中 –》https://www.aliyun.com/acts/product-section-2019/developer?utm_content=g_1000047140

本文作者:陈宗志阅读原文
本文为云栖社区原创内容,未经允许不得转载。

正文完
 0