由于郁白之前写的关于Multi-Paxos 的文章流传非常广, 具体地址: http://oceanbase.org.cn/?p=111 原文提出了一个叫"幽灵复现" 的问题, 认为这个是一个很诡异的问题, 后续和很多人交流关于一致性协议的时候, 也经常会提起这个问题, 但是其实这个问题我认为就是常见的"第三态"问题加了一层包装而已.
来自郁白的博客:
使用Paxos协议处理日志的备份与恢复,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为「幽灵复现」的现象,如下图所示:
对于将Paxos协议应用在资料库日志同步场景的情况,幽灵复现问题是不可接受,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。
为了处理「幽灵复现」问题,我们在每条日志的内容中保存一个generateID,leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时,因为leader在开始服务之前一定会写一条StartWorking日志,所以如果出现generateID相对前一条日志变小的情况,说明这是一条「幽灵复现」日志(它的generateID会小于StartWorking日志),要忽略掉这条日志。
第三态问题也是我们之前经常讲的问题, 其实在网路系统里面, 对于一个请求都有三种返回结果
前面两种状态由于服务端都有明确的返回结果, 所以非常好处理, 但是如果是第三种状态的返回, 由于是超时状态, 所以服务端可能对于这个命令是请求是执行成功, 也有可能是执行失败的, 所以如果这个请求是一个写入操作, 那么下一次的读取请求可能读到这个结果, 也可能读到的结果是空的
就像在 raft phd 那个论文里面说的, 这个问题其实是和 raft/multi-paxos 协议无关的内容, 只要在分散式系统里面都会存在这个问题, 所以大部分的解决方法是两个
那么对应于raft 中的第三态问题是, 当最后log Index 为4 的请求超时的时候, 状态机中出现的两种场景都是可能的
对应于幽灵问题, 其实是由于6-10 的操作产生了超时操作, 由于产生了超时操作以后, client 并没有对这些操作进行确认, 而是接下来去读取这个结果, 那么读取不到这个里面的内容, 由于后续的写入和切主操作有重新能够读取到这个6-10 的内容了, 造成了幽灵复现, 导致这个问题的原因还是因为没有进行对超时操作的重确认.
那么Raft 有没有可能出现这个幽灵复现问题呢?
其实在早期Raft 没有引入新的Leader 需要写入一个包含自己的空的Entry 的时候也一样会出现这个问题
Log Index 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
本文作者:陈宗志
原文链接
更多技术干货敬请关注云栖社区知乎机构号:阿里云云栖社区 - 知乎
本文为云栖社区原创内容,未经允许不得转载。