QCon北京「鸿蒙专场」火热来袭!即刻报名,与创新同行~ 了解详情
写点什么

如何解决分布式系统中的“幽灵复现”?

  • 2020-03-15
  • 本文字数:5001 字

    阅读完需:约 16 分钟

如何解决分布式系统中的“幽灵复现”?

1、“幽灵复现”问题

我们知道,当前业界有很多分布式一致性复制协议,比如 Paxos,Raft,Zab 及 Paxos 的变种协议,被广泛用于实现高可用的数据一致性。Paxos 组通常有 3 或 5 个互为冗余的节点组成,它允许在少数派节点发生停机故障的情况下,依然能继续提供服务,并且保证数据一致性。作为一种优化,协议一般会在节点之间选举出一个 Leader 专门负责发起 Proposal,Leader 的存在,避免了常态下并行提议的干扰,这对于提高 Proposal 处理的效率有很大提升。


但是考虑在一些极端异常,比如网络隔离,机器故障等情况下,Leader 可能会经过多次切换和数据恢复,使用 Paxos 协议处理日志的备份与恢复时,可以保证确认形成多数派的日志不丢失,但是无法避免一种被称为“幽灵复现”的现象。考虑下面一种情况:



如上表所示,在第一轮中,A 成为指定 Leader,发出 1-10 的日志,不过后面的 6-10 没有形成多数派,随机宕机。随后,第二轮中,B 成为指定 Leader,继续发出 6-20 的日志(B 没有看到有 6-10 日志的存在),这次,6 以及 20 两条日志形成了多数派。随机再次发生切换,A 回来了,从多数派拿到的最大 LogId 为 20,因此决定补空洞,事实上,这次很大可能性是要从 6 开始,一直验证到 20。我们逐个看下会发生什么:


  1. 针对 Index 6 的日志,A 重新走一轮 basic paxos 就会发现更大 proposeid 形成决议的 6,从而放弃本地的日志 6,接受已经多数派认可的日志;

  2. 针对 Index 7 到 Index 10,因为多数派没有形成有效落盘,因此 A 随机以本地日志发起提议并形成多数派;

  3. 针对 Index 11 到 Index 19,因为均没有形成有效落盘数据,因此,以 noop 形成补空洞;

  4. 针对 Index 20,这个最简单,接受已经多数派认可的日志;


在上面的四类情况分析中,1,3,4 的问题不大。主要在场景 2,相当于在第二轮并不存在的 7~10,然后在第三列又重新出现了。按照 Oceanbase 的说法,在数据库日志同步场景的情况,这个问题是不可接受的,一个简单的例子就是转账场景,用户转账时如果返回结果超时,那么往往会查询一下转账是否成功,来决定是否重试一下。如果第一次查询转账结果时,发现未生效而重试,而转账事务日志作为幽灵复现日志重新出现的话,就造成了用户重复转账。

2、基于 Multi-Paxos 解决“幽灵复现”问题

为了处理“幽灵复现”问题,基于 Multi-Paxos 实现的一致性系统,可以在每条日志内容保存一个 epochID,指定 Proposer 在生成这条日志时以当前的 ProposalID 作为 epochID。按 logID 顺序回放日志时,因为 leader 在开始服务之前一定会写一条 StartWorking 日志,所以如果出现 epochID 相对前一条日志变小的情况,说明这是一条“幽灵复现”日志,要忽略掉这条日志(说明一下,我认这里顺序是先补空洞,然后写 StartWorkingID,然后提供服务)。



以上个例子来说明,在 Round 3,A 作为 leader 启动时,需要日志回放重确认,index 1~5 的日志不用说的,epochID 为 1,然后进入 epochID 为 2 阶段,index 6 会确认为 epochID 为 2 的 StartWorking 日志,然后就是 index 7~10,因为这个是 epochID 为 1 的日志,比上一条日志 epochID 小,会被忽略掉。而 Index 11~19 的日志,EpochID 应该是要沿袭自己作为 Leader 看到的上上一轮 StartWorkingID(当然,ProposeID 还是要维持在 3 的),或者因为是 noop 日志,可以特殊化处理,即这部分日志不参与 epochID 的大小比较。然后 index 20 日志也会被重新确认。最后,在 index 21 写入 StartWorking 日志,并且被大多数确认后,A 作为 leader 开始接收请求。

3、基于 Raft 解决“幽灵复现”问题

3.1 关于 Raft 日志恢复

首先,我们聊一下 Raft 的日志恢复,在 Raft 中,每次选举出来的 Leader 一定包含已经 Committed 的数据(抽屉原理,选举出来的 Leader 是多数中数据最新的,一定包含已经在多数节点上 Commit 的数据),新的 Leader 将会覆盖其他节点上不一致的数据。虽然新选举出来的 Leader 一定包括上一个 Term 的 Leader 已经 Committed 的 Log Entry,但是可能也包含上一个 Term 的 Leader 未 Committed 的 Log Entry。这部分 Log Entry 需要转变为 Committed,相对比较麻烦,需要考虑 Leader 多次切换且未完成 Log Recovery,需要保证最终提案是一致的,确定的,不然就会产生所谓的幽灵复现问题。


因此,Raft 中增加了一个约束:对于之前 Term 的未 Committed 数据,修复到多数节点,且在新的 Term 下至少有一条新的 Log Entry 被复制或修复到多数节点之后,才能认为之前未 Committed 的 Log Entry 转为 Committed。


为了将上一个 Term 未 Committed 的 Log Entry 转为 Committed,Raft 的解决方案如下:


Raft 算法要求 Leader 当选后立即追加一条 Noop 的特殊内部日志,并立即同步到其它节点,实现前面未 Committed 日志全部隐式提交。


从而保证了两个事情:


  • 通过最大 Commit 原则保证不会丢数据,即是保证所有的已经 Committed 的 Log Entry 不会丢;

  • 保证不会读到未 Committed 的数据,因为只有 Noop 被大多数节点同意并提交了之后(这样可以连带往期日志一起同步),服务才会对外正常工作;Noop 日志本身也是一个分界线,Noop 之前的 Log Entry 被提交,之后的 Log Entry 将会被丢弃。

3.2 Raft 解决“幽灵复现”问题


针对第一小节的场景,Raft 中是不会出现第三轮 A 当选 leader 的情况,首先对于选举,候选人对比的是最后一条日志的任期号(lastLogTerm)和日志的长度(lastLogIndex)。B、C 的 lastLogTerm(t2)和 lastLogIndex(20)都比 A 的 lastLogTerm(t1)和 lastLogIndex(10)大,因此 leader 只能出现在 B、C 之内。假设 C 成为 leader 后,Leader 运行过程中会进行副本的修复,对于 A 来说,就是从 log index 为 6 的位置开始,C 将会把自己的 index 为 6 及以后的 log entry 复制给 A,因此 A 原来的 index 6-10 的日志删除,并保持与 C 一致。最后 C 会向 follower 发送 noop 的 log entry,如果被大多数都接收提交后,才开始正常工作,因此不会出现 index 7-10 能读到值的情况。


这里考虑另一个更通用的幽灵复现场景。考虑存在以下日志场景:



1)Round 1,A 节点为 leader,Log entry 5,6 内容还没有 commit,A 节点发生宕机。这个时候 client 是查询不到 Log entry 5,6 里面的内容。


2)Round 2,B 成为 Leader, B 中 Log entry 3, 4 内容复制到 C 中, 并且在 B 为主的期间内没有写入任何内容。


3)Round 3,A 恢复并且 B、C 发生重启,A 又重新选为 leader, 那么 Log entry 5, 6 内容又被复制到 B 和 C 中,这个时候 client 再查询就查询到 Log entry 5, 6 里面的内容了。



Raft 里面加入了新 Leader 必须写入一条当前 Term 的 Log Entry 就可以解决这个问题, 其实和 MultiPaxos 提到的写入一个 StartWorking 日志是一样的做法, 当 B 成为 Leader 后,会写入一个 Term 3 的 noop 日志,这里解决了上面所说的两个问题:


  • Term 3 的 noop 日志 commit 前,B 的 index 3,4 的日志内容一定会先复制到 C 中,实现了最大 commit 原则,保证不会丢数据,已经 commit 的 log entry 不会丢。

  • 就算 A 节点恢复过来, 由于 A 的 lastLogTerm 比 B 和 C 都小,也无法成了 Leader, 那么 A 中未完成的 commit 只是会被 drop,所以后续的读也就不会读到 Log Entry 5,6 里面的内容。

4、基于 Zab 解决“幽灵复现”问题

4.1 关于 Zab 的日志恢复

Zab 在工作时分为原子广播和崩溃恢复两个阶段,原子广播工作过程也可以类比 raft 提交一次事务的过程。


崩溃恢复又可以细分为 Leader 选举和数据同步两个阶段。


早期的 Zab 协议选举出来的 Leader 满足下面的条件:


a) 新选举的 Leader 节点含有本轮次所有竞选者最大的 zxid,也可以简单认为 Leader 拥有最新数据。该保证最大程度确保 Leader 具有最新数据。


b) 竞选 Leader 过程中进行比较的 zxid,是基于每个竞选者已经 commited 的数据生成。 zxid 是 64 位高 32 位是 epoch 编号,每经过一次 Leader 选举产生一个新的 leader,新的 leader 会将 epoch 号+1,低 32 位是消息计数器,每接收到一条消息这个值+1,新 leader 选举后这个值重置为 0。这样设计的好处在于老的 leader 挂了以后重启,它不会被选举为 leader,因此此时它的 zxid 肯定小于当前新的 leader。当老的 leader 作为 follower 接入新的 leader 后,新的 leader 会让它将所有的拥有旧的 epoch 号的未被 commit 的 proposal 清除。



选举出 leader 后,进入日志恢复阶段,会根据每个 Follower 节点发送过来各自的 zxid,决定给每个 Follower 发送哪些数据,让 Follower 去追平数据,从而满足最大 commit 原则,保证已 commit 的数据都会复制给 Follower,每个 Follower 追平数据后均会给 Leader 进行 ACK,当 Leader 收到过半 Follower 的 ACK 后,此时 Leader 开始工作,整个 zab 协议也就可以进入原子广播阶段。

4.2 Zab 解决“幽灵复现”问题

对于第 1 节的场景,根据 ZAB 的选举阶段的机制保证,每次选举后 epoch 均会+1,并作为下一轮次 zxid 的最高 32 位。所以,假设 Round 1 阶段,A,B,C 的 EpochId 是 1,那么接下来的在 Round 2 阶段,EpochId 为 2,所有基于这个 Epoch 产生的 zxid 一定大于 A 上所有的 zxid。于是,在 Round 3,由于 B, C 的 zxid 均大于 A,所以 A 是不会被选为 Leader 的。A 作为 Follower 加入后,其上的数据会被新 Leader 上的数据覆盖掉。可见,对于情况一,zab 是可以避免的。



对于 3.2 节的场景,在 Round 2,B 选为 leader 后,并未产生任何事务。在 Round 3 选举,由于 A,B,C 的最新日志没变,所以 A 的最后一条日志 zxid 比 B 和 C 的大,因此 A 会选为 leader,A 将数据复制给 B,C 后,就会出现”幽灵复现“现象的。


为了解决“幽灵复现”问题,最新 Zab 协议中,每次 leader 选举完成后,都会保存一个本地文件,用来记录当前 EpochId(记为 CurrentEpoch),在选举时,会先读取 CurrentEpoch 并加入到选票中,发送给其他候选人,候选人如果发现 CurrentEpoch 比自己的小,就会忽略此选票,如果发现 CurrentEpoch 比自己的大,就会选择此选票,如果相等则比较 zxid。因此,对于此问题,Round 1 中,A,B,C 的 CurrentEpoch 为 2;Round 2,A 的 CurrentEpoch 为 2,B,C 的 CurrentEpoch 为 3;Round 3,由于 B,C 的 CurrentEpoch 比 A 的大,所以 A 无法成为 leader。

5、 进一步探讨

在阿里云的女娲一致性系统里面,做法也是类似于 Raft 与 Zab,确保能够制造幽灵复现的角色无法在新的一轮选举为 leader,从而避免幽灵日志再次出现。从服务端来看“幽灵复现”问题,就是在 failover 情况下,新的 leader 不清楚当前的 committed index,也就是分不清 log entry 是 committed 状态还是未 committed 状态,所以需要通过一定的日志恢复手段,保证已经提交的日志不会被丢掉(最大 commit 原则),并且通过一个分界线(如 MultiPaxos 的 StartWorking,Raft 的 noop,Zab 的 CurrentEpoch)来决定日志将会被 commit 还是被 drop,从而避免模糊不一的状态。“幽灵复现”的问题本质属于分布式系统的“第三态”问题,即在网络系统里面, 对于一个请求都有三种返回结果:成功,失败,超时未知。对于超时未知,服务端对请求命令的处理结果可以是成功或者失败,但必须是两者中之一,不能出现前后不一致情况。在客户端中,请求收到超时,那么客户端是不知道当前底层是处于什么状况的,成功或失败都不清楚,所以一般客户端的做法是重试,那么底层 apply 的业务逻辑需要保证幂等性,不然重试会导致数据不一致。


参考文章:


  1. In Search of an Understandable Consensus Algorithm - Diego Ongaro and John Ousterhout

  2. https://raft.github.io/raft.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=raft.pdf

  3. Paxos Made Simple – Leslie Lamport

  4. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf?spm=ata.13261165.0.0.337d6f55qtohyc&file=paxos-simple.pdf

  5. Oceanbase 列传 – 郁白

  6. http://oceanbase.org.cn/?spm=ata.13261165.0.0.337d6f55qtohyc&p=111

  7. 关于 Paxos "幽灵复现"问题看法 – 陈宗志

  8. https://zhuanlan.zhihu.com/p/40175038?spm=ata.13261165.0.0.337d6f55qtohyc

  9. zookeeper 原理解析

  10. https://www.cnblogs.com/wxd0108/p/6251729.html?spm=ata.13261165.0.0.337d6f55qtohyc


本文转载自公众号阿里技术(ID:ali_tech)。


原文链接


https://mp.weixin.qq.com/s/0D2vwh5jW29ZH0Fio-eqqg


2020-03-15 10:153659

评论

发布
暂无评论
发现更多内容

【课程汇总】OpenHarmony全场景Demo数字管家系列课(附链接)

OpenHarmony开发者

OpenHarmony 数字管家

如何保证同事的代码不会腐烂?一文带你了解 阿里巴巴 COLA 架构

Zhendong

Java 架构 4月月更

手绘模型图带你认识Kafka服务端网络模型

华为云开发者联盟

kafka 多线程 网络模型 Reactor多线程 Processor

关于防御性编程,你应该知道的事

架构精进之路

编程 4月月更

国内20家优秀一线低代码平台推荐,经典收藏

J2PaaS低代码平台

低代码 开发工具 低代码平台 J2PaaS低代码

GPU时代来临!

Finovy Cloud

人工智能 gpu GPU服务器

压测做的不对,等于白做

基调听云

性能测试 压测 全链路压测

整机生产制造头部厂商雷神科技加入龙蜥社区

OpenAnolis小助手

Linux 开源 整机

Vue DevTools 使用指南 - 如何安装和使用 Vue DevTools 调试 Vue 组件

蒋川

Vue vue devtools

Kubernetes官方java客户端之五:proto基本操作

程序员欣宸

4月月更

科学防控 云天励飞打造抗疫全场景方案

科技新消息

蒙牛2021年报:数智化大脑为乳业插上腾飞翅膀

科技新消息

Linux 管道操作符详解

CRMEB

天翼云新一代V5云主机,Kvm之生,Xen之死!

天翼云开发者社区

实战异地多活架构之王者荣耀商城

晨亮

「架构实战营」

VMware Workstation Pro虚拟机网络设置

DS小龙哥

4月月更

书单 | 一季度重磅级上榜新书!

博文视点Broadview

制造业企业数据平台建设最佳实践分享

华为云开发者联盟

数字化转型 数据平台 制造业 华为工业云平台 数据应用

大数据培训程序员面试屡次碰壁怎么办

@零度

面试 大数据开发

程序员不好招了吗,web前端培训应该怎么学习

@零度

前端开发

实施知识管理过程中存在的问题(内附解决方案)

小炮

知识管理

云天励飞全场景方案助力科技防疫

科技新消息

洞见科技荣获隐私计算新势力奖!创始人姚明出席华夏时报「2022智能数据论坛」

洞见科技

隐私计算 数据智能

人工智能融合赋能平台,赋能智慧城市智能化升级

脑极体

PolarDB-X 正式发布2.1.0版本,Paxos 重磅开源

阿里云数据库开源

数据库 阿里云 开源 分布式 PolarDB-X

深入理解 Page Cache

mazhen

Linux Performance Linux Kenel PageCache

【PIMF】OpenHarmony啃论文成长计划——浅谈中间件

离北况归

中间件 OpenHarmony 啃论文

TDengine 应用实录:存储缩减超过 60%,HBase 等集群指数级下线

TDengine

数据库 tdengine 物联网

java培训浅谈程序员怎么避免面试过程中碰壁

@零度

面试 JAVA开发

深圳“摘星”!但常态化疫情防控工作不可松

科技新消息

领域驱动设计入门与实践[下]

LigaAI

团队管理 DDD 领域驱动设计思想 LigaAI

如何解决分布式系统中的“幽灵复现”?_数据库_剑翃_InfoQ精选文章