白话一致性协议 - Paxos、Raft和PacificA[0]

一致性协议 - Paxos

在分布式系统当中，我们往往需要保持节点之间的一致性。在绝大多数情况下，我们需要让系统中的节点相互协调通力合作，才能尽可能的让系统保持正确、可用。在这种场景下，我们可以忍受数据的丢失，但是需要在系统从异常状态下恢复后，可以尽快的 重新达成一致 。

但是，由于分布式系统本身的特性，需要我们在不可靠的硬件上尽可能的构建可靠的系统。所以，看似简单的一致性问题成为了分布式系统领域的一个重要的课题。

Paxos算法是Leslie Lamport于1990年提出的一种一致性算法。也是目前公认解决分布式一致性问题最有效的算法之一。

Paxos算法的目标是在一个不可靠的分布式系统内，只利用网络通信，能够快速且正确地在集群内部对某个数据的值达成一致。并且保证不论发生任何异常，都不会破坏系统的一致性。

Paxos算法

另一种（简化了的）形象的问题描述 - 抢车位

某小区的一些居民在抢车位，而车位只有一个。居民们达成协议，只要一个报价获得半数以上居民认可，那么提出这个出价的居民则获得了车位的所有权。所有权是临时的，所以如果有另一个居民提出了更高的报价并且获得认可，所有权则会被转移。

居民们都是遵纪守法的好公民，在整个过程中都只会如实的与其它用户分享信息。信息的分享是在网上，通过一对一的私密聊天进行。但是小区的手机信号非常差，我们不能保证通信的质量，一些信息可能会丢失，有的居民可能会掉线，有的居民甚至可能失忆。但是通信的内容是完整的，不会被篡改的。

划重点： 1. 车位有且只有一个，所以一个车位不能同时有两个拥有者 2. 车位可以暂时没有拥有者，但是需要尽快选出一个 3. 车位的所有权不是一成不变的，只要你的新报价获得了居民的认可，就可以更新所有权 4. 通信是不可靠的(not-reliable)，但是正确性(integrity)可以保证

如何选出最终的买家

由于通信是一对一的，对于所有参与者来说，他们对整个系统的了解都是片面的、过时的。但是参与者会通过与其它参与者进行通信，不断获得更及时的信息，从而最终达成一致。

对于普通居民，会记录“已知最高报价”和“已确认报价”两个状态。会处理两种请求： 1. 询价：如果询价小于当前居民已知最高报价，则拒绝请求，并返回当前最高报价。否则会更新本地的已知最高已有报价 2. 报价：居民会将请求中的报价与自己已知的最高报价进行比较，如果高于或等于本地已确认的报价，就确认这个报价，并同时更新两个状态

而对于买家，会发出两种不同的信息： 1. 询价：以某一个报价问询所有的居民，如果这个报价低于居民已知的报价，则更新报价 2. 报价：如果报价获得了多数居民的认可，即可以认为所有权已经更新

一致性的直观证明

报价阶段，除了保证正确性之外，对于居民和买家并没有任何约束。其本质参与者之间同步信息的过程。

而一致性在报价阶段可以被很好的保证。假设当前用户A已经声明以价格P买入车位（记为 (P, A) ），此时必有多数居民已经认可 (P, A) 。如果用户B想要声明以价格Q(Q >= P)买入车位，他仍需要获得半数以上居民的认可才可以获得所有权。

Paxos如何解决活锁问题

假设居民里有买家A、B，同时向其它居民提出询价/报价。如果他们的询价/报价顺序排列如下，会出现什么状况呢？

A: 询价，1块
众居民：好的，最高价为1块
B：加钱，2块
众居民：收到，最高价为2块
（此时A仍旧认为1块是最高报价）
A：最终报价，1块
众居民：不行不行，B已经加到两块钱了
A：（内心mmp）询价，3块
（B对A提高了报价也毫无准备）
B：最终报价，2块
众居民：滚粗，A已经报价3块了
B：我加钱
A：我再加
B：我加钱
A：我再加
众居民：。。。（你们玩个球啊）

震惊，这帮无聊的人居然为了这几块钱可以玩一天！

以这样的流程进行下去，系统会陷入活锁，几乎不能达成一致了。想要解决这个问题，可以将A和B的询价重试时间加入随机化因子，这样可以帮助更快的让居民们达成一致。

Paxos如何解决投票分裂问题

![5]

如图所示，居民们的投票可能会发生分裂，即没有一个值达到了半数。这里的解决方案是让买家重新进行询价，同时加入随机化因子，使得投票达成半数以上的概率更大。

说正经的

对于Paxos算法的官方描述和正确性的详细证明可以参考 原论文 。这里就不搬运了，只是把我的例子和官方通用术语进行一下讲解，避免把大家带跑偏了。

在上面的例子中，“车位”的通用术语被称为“共识”，整个系统中最多有一个共识。而“询价请求”被称为“prepare请求”，“报价请求”被称为“accept请求”。

每个请求的价格被称为“编号”，编号大的请求可以覆盖编号小的请求，和“价高者得”是一个道理。请求中所带的信息被称为“value”，在我们的例子中，代表着购买者的身份信息。

Basic Paxos和Multi Paxos

上面我们描述的Paxos算法又被称为Basic Paxos，因为每一轮流程执行完，所有的参与者都会（且只会）达成一个共识。而在实际的应用中，我们需要连续不断的对多个值达成共识。这时Basic Paxos算法就力不能及了，一来每一个值的共识都至少需要两次网络请求，性能太低，二来同时存在的多个提案会互相竞争，使得通信的效率下降。

所以为了解决这个问题，Multi Paxos算法应运而生，即一种可以高效的、连续不断的对多个值达成共识的算法。

下一篇文章中，我们会介绍一种被普遍认可，以及已经被工业界应用的Multi Paxos的实现 —— Raft算法。

参考链接

• Paxos Made Simple
• 从Paxos到Zookeeper
• 知乎：Paxos算法详解