关于im:Paxos理论介绍2-MultiPaxos与Leader

3次阅读

共计 2694 个字符，预计需要花费 7 分钟才能阅读完成。

前文：Paxos 实践介绍 (1): 奢侈 Paxos 算法实践推导与证实

了解奢侈 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，尽管 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 也就变得非常简单了，会波及到一些租约的货色，前面再分享。