分布式一致性算法:Paxos

2019-05-22 20:15:53

阅读次数 - 410

架构 分布式 一致性

Paxos算法是分布式系统中非常重要的一个算法。Paxos算法莱斯利·兰伯特(英语:Leslie Lamport,LaTeX中的“La”)于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

主要有两篇论文:

  • The Part-Time Parliament:Lamport于1998年发表在ACM Transactions on Computer Systems。第一次公开发表
  • Paxos Made Simple:2001年。Lamport觉得同行无法接受他的幽默感,于是用容易接受的方法重新表述了一遍。

Paxos算法其实理解起来有一些晦涩,本文试图通过一些图解和例子结合,尽量让它通俗易懂。

为什么需要分布式一致性算法?

分布式系统中的节点通信存在两种模型:共享内存(Shared memory)和消息传递(Messages passing)。

在分布式系统中,各结点是相对独立的,很难使用“共享内存”。

基于消息传递通信模型的分布式系统,不可避免的会发生以下错误:进程可能会慢、被杀死或者重启,消息可能会延迟、丢失、重复。

所以我们需要一个方法来保证基于“消息传递”通信模型的分布式系统能够达成一致的算法。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。

Paxos算法就是解决这个问题的。举个通俗的例子:

  • 假如我们有5个游客,3个导游,他们要决定接下来去哪个城市旅游
  • 如果可以拉一个微信群商量,那就相当于“共享内存”模型了,我们这里假定不能“拉群”
  • 每个游客和导游之间互相可以通过“私聊”交流,这就相当于“消息传递”模型
  • 每个导游想去的城市不一样
  • 每个导游给游客发短信的时间是不固定的
  • 游客可能会延迟收到每个导游的消息,也可能根本收不到
  • 少数服从多数,如果大多数游客同意去一个城市,那就可以去那个城市

我们期望达到的目标是:最终所有人达成共识:去同一个城市旅游

导游和游客

算法描述

我们先来看一下角色。在这个系统中,主要有两个角色:

  • 提议者 Proposer:提出决议的人,在这里就是“导游”的角色。
  • 批准者 Acceptor:批准决议的人,这这里就是“游客”的角色。

具体怎么操作呢?我们以一个导游和一个游客为例,Paxos算法分为两阶段,共4步。如图:

两阶段

两阶段

例子

下面我们以“游客”和“导游”为例,来讲述这个算法的原理。

第一阶段(占坑阶段)

导游发出占坑请求

导游1(给所有游客发送短信):大家好,我是导游1,我想发出一个提议,我这个提议的编号是4,你同意吗?

可能发生以下几种情况:

游客1:我之前没有收到过其它短信,同意!(并记录下来当前最大编号是4);

游客2:(看了看,之前收到过的最大编号是3)同意!(并记录下来当前最大编号是4);

游客3:(看了看,之前收到过的最大编号是5,想了想,不理他);

游客4:(看了看,之前已经接受了其它导游的提议了,已经进行到了第二阶段,编号是3,想去的城市是重庆)同意!我之前收到的最大编号是3,他想去的城市是重庆;(并记录下来当前最大编号是4);

其他游客也根据自己的情况去回复。。。

第二阶段

P2a:导游根据收到的回复进行下一步私聊

经过一段时间后,导游收到了一些回复。有以下几种情况:

超过半数的人都回复了OK,且没人回复已经accepted的城市,则导游发出accept请求,并带上自己的N和V:

导游:很好,我的提议的编号还是4,我提议去成都!

超过半数的人都回复了OK,但有些人已经accepted了城市,其中最大的已经accept的编号是3,想去的城市是重庆,则导游发出accept请求,并带上自己的N和回复中N最大的V:

导游:很好,我的提议的编号还是4,我提议去重庆!

回复数量小于一半,尝试生成更大的N,再转到阶段一。

导游1(给所有游客发送短信):大家好,我是导游1,我想发出一个提议,我这个提议的编号是7,你同意吗?

P2b:游客应答导游的accept请求

游客收到了导游的提议编号N和城市V。比较本地保存的最大编号MaxN:

导游:我的提议编号是4,我提议去成都!

游客1:(看了一下,本地最大编号是3)好啊,那就去成都!(并记下最大编号是3,想去的城市是成都);

游客2:(看了一下,本地最大编号是5,不理他);

其他游客也根据自己的情况去回复。。。

P2c:导游收集所有结果,进行下一步处理

超过半数的人回复提议成功,就广播给所有游客,通知他们这个提议:

导游1:行程已经确认了,去成都!大家记得保留在你们的记事本里面!

游客1:好的!

游客2:好的!

。。。

否则,生成更大的N,重复第一阶段:

导游1(给所有游客发送短信):大家好,我是导游1,我想发出一个提议,我这个提议的编号是7,你同意吗?

相关问题

如何产生一个递增的唯一编号?

根据Lamport的论文,可以使用(n + i * m)来产生一个递增的唯一编号。

其中n为提议者的编号。比如导游1的n就是1,导游2的n就是2。

m是总共有多少个提议者,比如我们一个有三个导游,那m就是3。

i是轮次,可以从1开始递增。

所以导游1的编号就是:4,7,10,13…

为什么要“过半数”?

试想一下,如果没有这个要求。假如一共10个游客,其中五个达成协议去重庆,另外5个达成协议去成都,那怎么进行最终的商定?

所以我们在使用Paxos算法搭建分布式集群的时候,会尽量让Acceptor的数量为奇数。

陷入死循环了怎么办?

这是一种极端的情况,导游1进行完了第一阶段,编号为N1,准备发送accept请求。但与此同时,导游2发送了一个更大的编号N2,会让所有的游客替换本地的MaxN为N2,这样就会导致导游1发送的accept请求全部被拒绝,然后导游1会重新进入第一阶段,发送一个更大的编号,这又可能会导致所有游客拒绝导游2的accept请求,进入了一个死循环。

Lamport的第二篇论文提出了一种解决方案:制定一个特定的Proposer,是他作为唯一一个可以提案的Proposer。这样一来,只要这个Proposer能与过半的Acceptor进行通信,该提案终将会被批准。

Paxos算法到底有什么用?

Paxos算法是一个“分布式一致性状态”的理论算法。它有许多改进版本和具体的技术实现。比如做分布式锁、元数据存储、master选举等。

Chubby(分布式锁服务)是基于Paxos算法的,Hypertable(分布式存储)底层也用到了Paxos来保证元数据的分布式一致性。

Zookeeper是基于ZAB协议的,ZAB协议和Paxos算法有些不同,但是由Paxos算法发展而来。

我们可以把上面“导游”和“游客”的例子类比成数据库的结点。把“去某个城市旅游”的提议改为“我想成为主结点”,就成为了典型的“分布式主结点选举问题”。

感谢阅读


觉得文章还不错?点击下方按钮分享吧!

评论

快来占个沙发吧~


TO: