背景图

Paxos协议详解

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢?

<分布式系统的事务处理>

  • Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

<大规模分布式存储系统>

  • 理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。

前言

记得一年前去看Paxos的算法,那真是云里雾里根本不知道在讲什么,后来看了网上的一个视频(知行学社的分布式系统与Paxos算法视频课程)终于记住了。但是时间一长又忘记了,但是永远记住了两个规则,我觉得总结的很好。这个视频讲解的也十分到位。

  1. Prepare阶段喜新厌旧
  2. Commit阶段后者认同前者
  3. 最终少数服从多数

算法的说明

首先将议员的角色分为proposers,acceptors,和learners(允许身兼数职)。proposers提出提案,提案信息包括提案编号和提议的value;acceptor收到提案后可以接受(accept)提案,若提案获得多数acceptors的接受,则称该提案被批准(chosen);learners只能“学习”被批准的提案。划分角色后,就可以更精确的定义问题:

  • 决议(value)只有在被proposers提出后才能被批准(未经批准的决议称为“提案(proposal)”);
  • 在一次Paxos算法的执行实例中,只批准(chosen)一个value;
  • learners只能获得被批准(chosen)的value。

另外还需要保证progress。这一点以后再讨论。作者通过不断加强上述3个约束(主要是第二个)获得了Paxos算法。

1
P1:一个acceptor必须接受(accept)第一次收到的提案。

这个比较好理解。(但是这里忽略了预提交阶段的事情了)。然后下面就是后者认同前者了:

1
P2:一旦一个具有value v的提案被批准(chosen),那么之后批准(chosen)的提案必须具有value v。

这个是对接收者后者认同前者的说明,但是貌似只是对一个acceptor有约束,所以必须成为所有acceptors的共识,于是有了P2a。

1
P2a:一旦一个具有value v的提案被批准(chosen),那么之后任何acceptor再次接受(accept)的提案必须具有value v。

之前说的后者认同前者都是针对acceptor,但如果对于Proposer呢?于是又出现了P2b:

1
P2b:一旦一个具有value v的提案被批准(chosen),那么以后任何proposer提出的提案必须具有value v。

但是根据P2b难以提出实现手段。因此需要进一步加强P2b。虽然以上规则很美好,但是总会出现各种异常的情况,但总会出现被大多数人接收的提案(少数服从多数原则)

1
2
P2c:如果一个编号为n的提案具有value v,那么存在一个多数派,要么他们中所有人都没有接受(accept)编号小于n
的任何提案,要么他们已经接受(accept)的所有编号小于n的提案中编号最大的那个提案具有value v。

最后这一条可能大家都不太明白,其实大概是这样的,当一个Proposer发现自己已经获得超过半数的之后后,就会进行广播说“我的提案通过啦,新的提案就不要再提出来啦”,于是众人开始学习(有点像区块链中挖出矿的幸运儿有木有)。对于掉队的孩子又找到队伍了,发起的旧协议终于到了“我提出一个提案,xxx”,于是其他人对他说“还提这些陈芝麻烂谷子干嘛,我们已经通过这个问题的提案了,就是XXX”,于是新人说那是晚到的邮件啊,我其实早就收到消息了呀!不知你看懂没有,这就是Paxos协议。

解释

以上就是理解这个Paxos算法的思路,如果你想具体了解这个算法的过程,可以查看视频,也可以看wiki百科里面关于Paxos的示例,写得已经很明白了,只有按照前言中的三条规则向下面走,你一定会明白,这个应该不是特别难于理解。

决议的发布(主acceptor)

一个显而易见的方法是当acceptors批准一个value时,将这个消息发送给所有learner。但是这个方法会导致消息量过大。

由于假设没有Byzantine failures,learners可以通过别的learners获取已经通过的决议。因此acceptors只需将批准的消息发送给指定的某一个learner,其他learners向它询问已经通过的决议。这个方法降低了消息量,但是指定learner失效将引起系统失效。

因此acceptors需要将accept消息发送给learners的一个子集,然后由这些learners去通知所有learners。

但是由于消息传递的不确定性,可能会没有任何learner获得了决议批准的消息。当learners需要了解决议通过情况时,可以让一个proposer重新进行一次提案。注意一个learner可能兼任proposer。

Progress的保证(主Proposer)

根据上述过程当一个proposer发现存在编号更大的提案时将终止提案。这意味着提出一个编号更大的提案会终止之前的提案过程。如果两个proposer在这种情况下都转而提出一个编号更大的提案,就可能陷入活锁,违背了Progress的要求。这种情况下的解决方案是选举出一个leader,仅允许leader提出提案。但是由于消息传递的不确定性,可能有多个proposer自认为自己已经成为leader。

参考和引用

paxos和分布式系统
Paxos算法
图解分布式一致性协议Paxos
图解 Paxos 一致性协议

0%