Paxos 理论介绍 (2): Multi-Paxos 与 Leader
前文:Paxos理论介绍(1): 朴素Paxos算法理论推导与证明
理解朴素 Paxos 是阅读本文的前提。
Multi-Paxos
朴素 Paxos 算法通过多轮的 Prepare/Accept 过程来确定一个值,我们称这整个过程为一个 Instance。Multi-Paxos 是通过 Paxos 算法来确定很多个值,而且这些值的顺序在各个节点完全一致。概括来讲就是确定一个全局顺序。
多个 Instance 怎么运作?首先我们先构建最简易的模式,各个 Instance 独立运作。
每个 Instance 独立运作一个朴素 Paxos 算法,我们保证仅当 Instance i 的值被确定后,方可进行 i+1 的 Paxos 算法,这样我们就保证了 Instance 的有序性。
但这样效率是比较差的,众所周知朴素 Paxos 算法的 Latency 很高,Multi-Paxos 算法希望找到多个 Instance 的 Paxos 算法之间的联系,从而尝试在某些情况去掉 Prepare 步骤。
下面我尝试描述一个 Sample 的演进情况来阐述这个算法,因为这个算法的要点其实非常简单,而且无需更多证明。
首先我们定义 Multi-Paxos 的参与要素:
3 个参与节点 A/B/C.
Prepare(b) NodeA 节点发起 Prepare 携带的编号。
Promise(b) NodeA 节点承诺的编号。
Accept(b) NodeA 节点发起 Accept 携带的编号。
1(A)的意思是 A 节点产生的编号 1,2(B)代表编号 2 由 B 节点产生。绿色表示 Accept 通过,红色表示拒绝。
下图描述了 A/B/C 三个节点并行提交的演进过程:
这种情况下 NodeA 节点几乎每个 Instance 都收到其他节点发来的 Prepare,导致 Promise 编号过大,迫使自己不断提升编号来 Prepare。这种情况并未能找到任何的优化突破口。
下图描述了只有 A 节点提交的演进过程:
这种情况我们会立刻发现,在没有其他节点提交的干扰下,每次 Prepare 的编号都是一样的。于是乎我们想,为何不把 Promised(b)变成全局的?来看下图:
假设我们在 Instance i 进行 Prepare(b),我们要求对这个 b 进行 Promise 的生效范围是 Instance[i, ∞),那么在 i 之后我们就无需在做任何 Prepare 了。可想而知,假设上图 Instance 1 之后都没有任何除 NodeA 之外其他节点的提交,我们就可以预期接下来 Node A 的 Accept 都是可以通过的。那么这个去 Prepare 状态什么时候打破?我们来看有其他节点进行提交的情况:
Instance 4 出现了 B 的提交,使得 Promised(b)变成了 2(B), 从而导致 Node A 的 Accept 被拒绝。而 NodeA 如何继续提交?必须得提高自己的 Prepare 编号从而抢占 Promised(b)。这里出现了很明显的去 Prepare 的窗口期 Instance[1,3],而这种期间很明显的标志就是只有一个节点在提交。
重点:不 Prepare 直接 Accept 为啥是安全的?因为 Accept 的 b 已经被 Promise 过。
总结
Multi-Paxos 通过改变 Promised(b)的生效范围至全局的 Instance,从而使得一些唯一节点的连续提交获得去 Prepare 的效果。
题外话:这里提一下我所观察到的 Multi-Paxos 的一个误区,很多人认为 Multi-Paxos 是由 leader 驱动去掉 Prepare 的,更有说在有 Leader 的情况下才能完成 Multi-Paxos 算法,这都是理解有误。大家看到这里也应该明白这里的因果关系,Multi-Paxos 是适应某种请求特征情况下的优化,而不是要求请求满足这种特征。所以 Multi-Paxos 接受并行提交。
Leader
为何还要说 Leader,虽然 Multi-Paxos 允许并行提交,但这种情况下效率是要退化到朴素 Paxos 的,所以我们并不希望长时间处于这种情况,Leader 的作用是希望大部分时间都只有一个节点在提交,这样才能最大发挥 Mulit-Paxos 的优化效果。
怎么得到一个 Leader,真的非常之简单,Lamport 的论文甚至的不屑一提。我们观察 Multi-Paxos 算法,首先能做 Accept(b)必然是 b 已经被 Promised 了,而连续的 Accept(b)被打断,必然是由于 Promised(b)被提升了,也就是出现了其他节点的提交(提交会先 Prepare 从而提升 b)。那么重点来了,如何避免其他节点进行提交,我们只需要做一件事即可完成。
收到来自其他节点的 Accept,则进行一段时间的拒绝提交请求。
这个解读起来就是各个节点都想着不要去打破这种连续的 Accept 状态,而当有一个节点在连续的 Accept,那么其他节点必然持续不断的拒绝请求。这个 Leader 就这样无形的被产生出来了,我们压根没有刻意去“选举”,它就是来自于 Multi-Paxos 算法。
题外话:为何网上出现很多非常复杂的选举 Leader 算法,有的甚至利用 Paxos 算法去选举 Leader,我觉的他们很有可能是没有完全理解 Multi-Paxos,走入了必须有 Leader 这个误区。
用 Paxos 算法来进行选举是有意义的,但不应该用在 Leader 上面。Paxos 的应用除了写之外,还有很重要的一环就是读,很多时候我们希望要读到 Latest,通常的做法就是选举出一个 Master。Master 含义是在任一时刻只能有一个节点认为自己是 Master,在这种约束下,读写我都在 Master 上进行,就可以获得 Latest 的效果。Master 与 Leader 有本质上的区别,要达到 Master 这种强一致的唯一性,必须得通过强一致性算法才能选举出来。而当我们实现了 Paxos 算法后,选举 Master 也就变得非常简单了,会涉及到一些租约的东西,后面再分享。
说的再多不如阅读源码,猛击进入我们的开源 Paxos 类库实现:https://github.com/tencent-wechat/phxpaxos
OpenIMgithub 开源地址:
https://github.com/OpenIMSDK/Open-IM-Server
OpenIM 官网 : https://www.rentsoft.cn
OpenIM 官方论坛: https://forum.rentsoft.cn/
更多技术文章:
开源 OpenIM:高性能、可伸缩、易扩展的即时通讯架构https://forum.rentsoft.cn/thread/3
【OpenIM 原创】简单轻松入门 一文讲解 WebRTC 实现 1 对 1 音视频通信原理https://forum.rentsoft.cn/thread/4
评论