本篇论文主要进行的是对quorum的研究工作,主要借鉴了Fpaxos、和Wpaxos,解决的是跨区域复制、边缘网络中需要频换更换领导权的场景。本论文我分为了以下部分:
1、Zone-Centric Quorums(论文Wpaxos的思想)
2、Expanding Quorums
2.1Delegate Quorums
2.2Leader Zone Quorums
实际上,第二点都属于对paxos第一阶段——leader election的改动。
本文章已经默认掌握了Fpaxos、Wpaxos
1、Zone-Centric Quorums
第一点不讲了,可以去看Wpaxos的论文,比较好理解
2、Expanding Quorums
与之前的paxos不同,Dpaxos中如果一个节点想当leader,它会声明将要使用的Replication quorums(也就是第二阶段的quorum),通常来说会选择本地的节点作为Replication quorums(因为写入操作都在本地,不需要跨区域通信,延迟小)
论文中给出了一条规则
Definition: any two Leader Election quorums must intersect.
个人理解:通过q1的相交(q1中包含将要使用q2的意图),来达成q2的相交
2.1、Delegate Quorums
Delegate Quorums由大多数zone的大多数节点构成,如下图
但是,之所以叫expanding quorum,是因为这个q1是会变化的,请看下面的例子:
具有八个区域,每个区域三个节点,fd = 1 和 fz = 0(fd:区域内容错,fz:所有区域的容错)。最初,区域 1 中的节点成为slot i 中的领导者通过从大多数区域获得选票,然后在区域 1 内复制,直到slot i + 4。然后,区域 4 中的节点通过轮询大多数区域的选票来尝试成为slot i + 5 中的领导者。大多数人碰巧不包括区域 1。但是,它们与在slot i 中启动的Delegate Quorums相交。因此,他们收到了在区域 1 中使用Replication quorums的意图。因此,区域 4 中的有抱负的领导者开始另一轮通信以获得区域 1 中节点的投票。只有与意图的Replication quorums相交的节点的投票足够了。之后,假设收集到了赞成票,则区域 4 中的节点成为领导者并开始决定未来时隙的值,直到选出新的领导者。
2.2、Leader zone quorums
因为Delegate Quorums由与大多数zone构成,需要大量跨区域的通信,而Leader zone quorums则是将所有的q1都放到了一个zone里,这个zone就叫做leader zone,如果leader zone距离leader的距离过远,是可以转移到leader所在区域的(ideally, the zone hosting the current leader)ps:具体什么情况发生转移文章没提。让不同的leader在这一个zone里进行投票选举,这样就可以确保一定有交集
具体看下面的例子:
有八个区域,fd = 1 和 fz = 0。最初,区域 1 是Leader Zone。考虑区域 2 中的节点 i 想要成为领导者。它向区域 1 中的大多数节点发送 prepare() 消息,目的是使用区域 2 中的Replication quorums。区域 1 中的大多数节点向节点 i 回复 promise() 消息。在这种情况下没有先前的意图。因此,节点 i 使用区域 2 中的Replication quorums进入复制阶段,并决定slot 1 到 6 的值。之后,区域 4 中的节点 j 尝试通过向Leader Zone,Zone 1中的大多数节点发送 prepare() 消息来成为领导者。区 1 中的大多数响应 promise() 消息,其中包含节点 i(区 2 中的Replication quorums)的意图。因此,Leader Election quorum 扩展为包括 Zone 2 中的 Replication quorum。节点 j 向 Zone 2 中的节点发送 prepare() 消息。然后,足够多的节点与 Zone 2 中的节点 i 的意图相交以 promise() 消息响应。此时,节点 j 进入复制阶段并决定slot 7 到 10 中的值。slot 10 决定后,节点 j 决定将Leader Zone转移到区 4。首先,节点 j 注册区域 4 是下一个领袖区。它通过在为此目的而指定的 Zone 1 中的单独 Paxos 进程中决定“Zone 4”的值来实现。这需要经历单独的 Paxos 实例的 Leader Election 和 Replication 阶段,如图所示为 Zone 4 和 Zone 1 之间的两轮通信。 然后,节点 j 向 Zone 1 中的大多数节点发送请求以开始转换阶段(意图从区域 1 发送到区域 4,有关转换的信息搭载在来自区域 1 的 promise() 消息中,并且新传入的意图不在区域 1 中维护。)在此期间,有抱负的领导者(未显示在区域 1 中)图) 必须获得区域 1 和区域 4 中多数人的选票。他们将通过接收来自区域 1 的 promise() 消息的捎带信息来了解处于过渡阶段。为了完成转换,节点 j 向所有节点发送公告消息,宣布区域 4 为新的Leader Zone。此时,有抱负的领导者(未显示)只需要在领导者选举阶段从区域 4 中获得多数选票即可。不知道转换的有抱负的领导者(例如,由于放弃或延迟公告)将他们的 prepare() 消息发送到区域 1,然后通知他们新的Leader Zone。
当然本篇论文还有一些其他的优化,但对于quorum的改变是本篇文章的核心。
至于实验方面,比如和无领导者协议比较,并没有说明是哪一种无领导者协议。如果是epaxos,而epaxos的最佳性能是3或5节点的集群,本文章使用的是21节点,这样epaxos的quorum会处于不利的位置,不能发挥最好的性能。
一点思考:本文章的场景是leader所有权经常发生变更,但每一次leader变更如果都要对leader zone进行变更的话,需要很大的开销。
个人浅薄理解,如有问题欢迎交流讨论