分布式系统的一致性协议之 Multi-Paxos 算法
前言
在上文《分布式系统的一致性协议之 Paxos 算法的应用场景》中，我们为了实现状态机，以多个Instance的方式来达到不同阶段状态输入的工作，而这种方式再加以优化则形成了一个Paxos的变种，也就是Multi-Paxos算法。
Multi-Paxos是通过Paxos算法来确定很多个值，而且这些值的顺序在各个节点完全一致。概括来讲就是确定一个全局顺序。下面我们跳出之前的文章，来重新认识一下Multi-Paxos算法。
Multi-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。这种情况并未能找到任何的优化突破口。
在classic-Paxos算法中，允许任意Preparer发起Proposal，并提交给其他节点的，也就是会在Instance的不同时刻，在Promised阶段会有接收到不同的Proposal。这样就会导致在Accept阶段，大概率的出现冲突/拒绝情况。
下图描述了只有A节点提交的演进过程：
这种情况我们会立刻发现，在没有其他节点提交的干扰下，每次Prepare的编号都是一样的。于是乎我们想，为何不把Promised(b)变成全局的？来看下图：
假设我们在Instance i进行Prepare(b)，我们要求对这个b进行Promise的生效范围是Instance[i, ∞)，那么在i之后我们就无需在做任何Prepare了。可想而知，假设上图Instance 1之后都没有任何除NodeA之外其他节点的提交，我们就可以预期接下来Node A的Accept都是可以通过的。
我们就可以预期接下来Node-A的Porposal在Accept都是可以通过的。注意，这里的Proposal的序号不再增加，一直沿用，直到被打破这个状态，之后Instance序号会增加。
那么这个去Prepare状态什么时候打破？我们来看有其他节点进行提交的情况：
Instance 4出现了B的提交，使得Promised(b)变成了2(B), 从而导致Node A的Accept被拒绝。而NodeA如何继续提交？必须得提高自己的Prepare编号从而抢占Promised(b)。这里出现了很明显的去Prepare的窗口期Instance[1,3]，而这种期间很明显的标志就是只有一个节点在提交。
假设“实例”持续到了Instance-3，一直是这个状态。当在Instance-4时刻的Promised(b)阶段，假设出现2(B)【因为允许其他节点提出Proposal、其他client通过nodeB发起提案】，则会导致在Accept阶段1(A)会被拒绝【因为发现新的、大于NodeA的序号的Proposal出现，根据Paxos约束会被预批准】，进而A需要提升自己的编号3(A)从而抢占Promised(b)。而在这之前，在Instance[1,3]期间，是无需提出Proposal的，而这种期间很明显的标志就是只有一个节点A在提交。
换个思路来理解，也就是当出现一个Node得到Promised并且被Accept时，可以认为这个Node临时获得去Prepare的效果（不需要提出Proposal），可以直接进行Accept。只有当其他节点再次获得Promised(b)时，在Accept阶段会产生冲突，再进入classic-Paxos初始流程（注意任何算法都会在Accept阶段产生冲突），先进行Prepare阶段。
重点：不Prepare直接Accept为啥是安全的？因为Accept的b已经被Promise过。
总结
Multi-Paxos通过改变Promised(b)的生效范围至全局的Instance，从而使得一些唯一节点的连续提交获得去Prepare的效果。
题外话：这里提一下我所观察到的Multi-Paxos的一个误区，很多人认为Multi-Paxos是由leader驱动去掉Prepare的，更有说在有Leader的情况下才能完成Multi-Paxos算法，这都是理解有误。大家看到这里也应该明白这里的因果关系，Multi-Paxos是适应某种请求特征情况下的优化，而不是要求请求满足这种特征。所以Multi-Paxos接受并行提交。
综上所述，Multi-Paxos其实是为了适应某种请求特征情况下的优化（这种优化思维中并不包含Leader的角色）（将原来2-Phase过程简化为了1-Phase，从而加快了提交速度）。
显然我们希望Multi-Paxos的优化效果能持续时间长一些，这样才能最大发挥Mulit-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的角色很模糊，并不实际存在。
题外话：为何网上出现很多非常复杂的选举Leader算法，有的甚至利用Paxos算法去选举Leader，我觉的他们很有可能是没有完全理解Multi-Paxos，走入了必须有Leader这个误区。
用Paxos算法来进行选举是有意义的，但不应该用在Leader上面。
以上流程以及举例都是针对写操作，而读操作流程，是希望读到Latest（最后一个确认的值），通常的做法就是选举出一个Master。Master含义是在任一时刻只能有一个节点认为自己是Master，在这种约束下，读写我都在Master上进行，就可以获得Latest的效果。Master与Leader有本质上的区别，要达到Master这种强一致的唯一性，必须得通过强一致性算法才能选举出来（而Multi-Paxos中的Leader是根据先拿到Accept来产生的）。而当我们实现了Paxos算法后，选举Master也就变得非常简单了。
另外，展示一下Multi Paxos协议的决议过程：
phase1a: leader提交提议给acceptor
phase1b: acceptor返回最近一次接受的提议(即曾接受的最大的提议ID和对应的value)，未接受过提议则返回空phase2a: leader收集acceptor的应答，分两种情况处理
phase2a.1: 如果应答内容都为空，则自由选择一个提议value
phase2a.2: 如果应答内容不为空，则选择应答里面ID最大的提议的valuephase2b: acceptor将决议同步给learner
Multi Paxos中leader用于避免活锁，但leader的存在会带来其他问题，一是如何选举和保持唯一leader(虽然无leader或多leader不影响一致性，但影响决议进程progress)，二是充当leader的节点会承担更多压力，如何均衡节点的负载。Mencius[1]提出节点轮流担任leader，以达到均衡负载的目的；租约(lease)可以帮助实现唯一leader，但leader故障情况下可导致服务短期不可用。
Multi Paxos算法的应用
腾讯公司的微信后台团队，基于Paxos协议以及Mulit Paxos协议，研发了一套多机状态拷贝类库。它以库函数的方式嵌入到开发者的代码当中， 使得一些单机状态服务可以扩展到多机器，从而获得强一致性的多副本以及自动容灾的特性。是一套很完整、考虑很周密的类库，有兴趣可以了解一下：https://github.com/Tencent/phxpaxos
参考：