EPaxos 恢复场景

EPaxos 恢复场景

EPaxos是一个无领导的Paxos变体,它试图通过使客户端使用具有最低往返延迟的副本作为操作领导,并通过操作间冲突检测优化地跳过一轮副本通信,从而减少地理分布式副本组的延迟。

在这篇文章中,我将不解释EPaxos,而是通过一个例子来说明恢复协议是如何工作的。这个例子让我困惑了一阵子,因为它实际上并没有在SOSP'13论文中得到解决--完整的恢复协议在技术报告中。因此,我建议你在开始用例子理解EPaxos之前,先阅读技术报告中的恢复协议。

Failure and recovery scenario

考虑一个由五个节点组成的复制组。五个副本的快速路径法定人数是3(F+⌊(F+1)/2⌋),使得EPaxos的快速路径法定人数( fast-path quorum)与简单多数人数(majority)相同。让我们这样来命名这些复制体。

  A   B
C   D   E

一种可能出现问题的情况是,当客户端成功完成一个操作(有副作用,即写操作),然后发出另一个操作,但在第二个操作完成之前发生了一些故障,恢复协议错误地将第二个操作排序在第一个操作之前。

假设第一个操作使用A作为领导者,C和D组成其他快速路径的法定成员,而第二个操作使用B作为领导者,D和E作为法定成员。此外,假设A快速路径提交了操作1,向客户端回应成功,但在向C和D发送 "提交 "消息之前崩溃了。然后,B向D和E发送了预接受(在deps中没有操作1,因为B不知道操作1),也崩溃了。系统遭受了两次故障,但必须恢复并继续运行,因为在EPaxos中五个副本可以容忍两次故障。然而,其余的复制体看起来是这样的(下标代表复制体在其日志中预先接受了哪项操作)。

  X   X
C_1 D_1 E_2

此时,每个副本只知道两个操作中的一个,但不知道它是否被提交,而且这两个操作相互冲突(关于 "冲突 "的确切含义,见技术报告第6.2节第6号)。但当C、D或E启动恢复操作1和2时,它怎么知道哪个操作(如果有的话)是快速路径提交的,而且是以什么顺序提交的呢?

事实证明,如果我们知道两个操作的领导者,我们就可以弄清楚这个混乱的局面--这正是EPaxos在这种情况下的做法。如果一个操作的领导者,alpha,在另一个操作,beta的快速路径法定人数中,那么beta不可能被快速路径提交,如果alpha的预接受信息中不包含beta。

恢复工作将按以下方式进行。假设C启动了操作1的恢复。首先,它询问快速路径的法定人数,他们的日志包含什么。C观察到至少有⌊(F+1)/2⌋个复制体(C和D)已经预先接受了一个具有相同默认属性的操作,然后试图说服其他复制体接受该操作,直到至少有F+1个复制体接受它。当C要求E接受操作1时,E拒绝了,因为操作1与操作2冲突,而E已经预先接受了操作2。因此,C将推迟恢复操作1(第6.2节,步骤7-e),转而尝试恢复与之冲突的操作,即操作2。

对于操作2的恢复,复制体C和D将不接受操作2,并将回应冲突的操作和冲突操作的领导者的身份。正在恢复的副本现在将观察到操作1的领导者,副本A,在操作2的快速路径法定人数中,但A显然不知道操作2;否则它将在预接受消息中把操作2列为操作1的依赖。因此,操作2不可能被快速路径接受。然后,操作2将被填充为no-op,操作1的恢复将被解决,从而得出结论,操作1被快速路径提交了(注意,如果没有冲突,即使有关操作没有被提交,得出操作被快速路径提交的结论总是安全的)。

给TA打赏
共{{data.count}}人
人已打赏
分布式

强一致性模型

2021-5-18 15:53:30

分布式

epaxos 相关

2021-5-27 16:18:13

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索