一致性协议 - Paxos

在分布式系统当中,我们往往需要保持节点之间的一致性。在绝大多数情况下,我们需要让系统中的节点相互协调通力合作,有可能的让系统正确的工作。但是,由于分布式系统本身的特性,需要我们在不可靠的硬件上尽可能的构建可靠的系统。所以,看似简单的一致性问题成为了分布式系统领域的一个重要的课题。

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

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

Paxos算法

另一种(简化了的)形象的问题描述 - 买车位

某小区的一些居民在抢车位,而车位只有一个。居民们达成协议,只要一个报价获得半数以上居民认可,那么提出这个出价的居民则获得了车位的所有权。

居民之间非常友善,如果知道了车位已经有了买家,就不会继续出价购买,并且会帮忙传播这个信息。

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

划重点:

  1. 车位有且只有一个,所以一个车位不能同时有两个拥有者
  2. 车位可以暂时没有拥有者,但是需要尽快选出一个
  3. 需要半数以上居民的认可,才能声称拥有车位
  4. 通信是不可靠的(not-reliable),但是正确性(integrity)和可持久性(durability)是可以保证的
  5. 整个流程的目标是确定车位的拥有者。流程的参与者不会以自己拥有车位为最终目标

如何选出最终的买家

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

对于普通居民,会记录“已知最高报价”和“已确认报价”两个状态。会处理两种请求:

  1. 询价:如果居民已确认了某个报价,则返回这个报价。否则会尝试更新已知最高报价,并报告买家当前的最高报价
  2. 报价:居民会将请求中的报价与自己已知的最高报价进行比较,如果高于或等于本地已经报价,无论是否已经有已确认报价,都会确认这个报价

而对于买家,会发出两种不同的信息:

  1. 询价:以某一个报价问询多数居民,如果有已确认的报价,则放弃自己的报价。如果这个报价低于居民已知的报价,则提高报价。
  2. 报价:如果询价过程中收到了已确认的报价,则帮忙转发这个报价。否则发送自己的报价,如果报价获得了多数居民的认可,即可以认为所有权已经更新

一致性的直观证明

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

而一致性在报价阶段可以被很好的保证

  • 如果车位还没有主人,那么大家就拼一拼运气和手速,直到有一个买家获得了半数居民的认可。
  • 如果用户A已经声明以价格P买入车位(记为(P, A)),此时必有多数居民已经认可(P, A)。如果用户B想要声明以价格Q(Q >= P)买入车位,首先需要向多数居民询价,在询价的过程中,一定会收到用户A已经拥有车位的信息,此时B只会帮A扩散信息,而不会去争夺拥有权。系统最终会达到一个稳定的状态。

失忆 - 放松可持久性要求

如果我们放松可持久性的限制。即居民可以清空自己的状态。那此时最差情况是多数已经确认报价的居民不再承认报价,那么系统就有可能退化到“仍没有人拥有车位”的状态。此时我们只需要再进行一轮选举,选出车位新的主人即可。这并不会破坏整个系统的一致性。

旁观者视角

假如我们做为旁观者,想要观察是谁最终拥有了车位。可以有以下两种方法:

  1. “推”模型

当新的买家被选举出来时,新买家会通知所有旁观者车位的拥有者发生了变化。这样观察者们可以实时的获得状态的变化,但是由于通信是不可靠的,旁观者可能会错过状态变化的信息。如果这种情况出现,观察者只能等待下次状态变化,才能更新自己的状态。

  1. “拉”模型

旁观者可以假装自己是一个买家,向多数居民进行询价。如果最终买家已经确定,那么询价的响应中一定包含着最新的拥有者信息。

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如何解决投票分裂问题

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

说正经的

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

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

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

Basic Paxos和Multi Paxos

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

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

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

参考链接


Comments

comments powered by Disqus