Paxos算法

Paxos算法在分布式领域中起着非常重要的作用。但是Paxos算法有两个明显的缺点:1。很难理解。2.在工程上更难实现。

网上有很多解释Paxos算法的文章，但是质量参差不齐。看了很多关于Paxos的资料，发现学习Paxos最好的资料是Paxos制作简单的那张纸，其次是中英文维基百科对Paxos的介绍。本文试图带你一步步揭开Paxos神秘的面纱。

Paxos是什么？

Paxos算法是一种基于消息传递的一致性算法，具有高度容错性。目前公认的是解决分布式一致性问题。最有效的算法之一。

Google Chubby的作者Mike Burrows说，世界上只有一种一致性算法，那就是Paxos，其他所有算法都是有缺陷的。

虽然Mike Burrows有点夸张，但至少说明了Paxos算法的地位。然而，Paxos算法也因其晦涩而臭名昭著。本文的目的是带领大家深入浅出地了解Paxos算法，不仅要了解它的执行过程，还要了解算法的推导过程，以及作者是如何一步步想出最终方案的。只有了解推导过程，才能深刻把握算法的本质。而且了解推导过程对我们的思考也很有帮助，可能会给我们带来一些解决问题的思路，给我们启发。

问题的背景。

在常见的分布式系统中，像机器停机或网络异常(包括消息延迟、丢失、重复、无序和网络分割)这样的事情总是会发生。Paxos算法需要解决的问题是，在分布式系统中，如何在集群内部快速、正确地检查可能出现上述异常的地方。某个数据的值是一致的，保证无论发生上述任何一种异常，整个系统的一致性都不会被破坏。

注意:这里某个数据的值不仅仅是狭义上的某个数字，可以是日志，也可以是命令。。。根据不同的应用场景，某个数据的值有不同的含义。

相关概念

在Paxos算法中，有三个角色:

申请人

接受者

学习者

在具体实现中，一个流程可能同时扮演多个角色。例如，一个过程可能既是提议者，又是接受者和学习者。

还有一个很重要的概念叫提案。要达成一致的最终价值在提案中。

注:-我们假设“提议=价值”是指提议只包含价值。在我们接下来的推导中，会发现如果提议只包含价值，就会有问题，所以我们再来讨论一下提议。重新设计。——暂且“提议者可直接提出提议”。在我们接下来的推导中，会发现如果提议者直接提出提议会有问题，需要增加一个学习提议的过程。

提案人可以提出提案；承兑人可以接受建议；如果选择了建议，则选择建议中的值。

回到刚才说的“对某个数据的值达成一致”，是指命题者、接受者、学习者都认为选择了相同的值。那么，在什么情况下，命题者、接受者和学习者才能认为某个值是被选择的呢？

提议者:只要提议者发出的提议被接受者接受(起初认为只需要一个接受者，在推导过程中会发现超过一半的接受者同意)，提议者认为提议中的值被选中。

Acceptor:只要Acceptor接受建议，Acceptor就会选择建议中的值。

学习者:接受者告诉学习者选择了哪个值，学习者认为选择了那个值。

问题描述

假设有一组流程可以提议)value(值(值在提议中)。一致性算法需要确保在如此多的建议值中，只选择一个值。如果未提议任何值，则不应选择任何值。如果选择了一个值，那么所有进程都应该能够？学习这个选定的值。对于一致性算法，安全性要求如下:

只能选择建议的值。

只选择了一个值，并且

如果一个进程认为某个值被选中，那么这个值一定是真正被选中的那个值。

我们没有精确地定义它的活性需求。我们的目标是确保最终选择一个建议值。当选择了一个值时，该过程最终可以学习这个值。

Paxos的目标:确保最终会选择一个值，并且在选择该值时，流程最终可以得到选择的值。

假设不同的角色可以通过发送消息进行通信，那么:

每个角色以任意速度执行，并且可能由于错误而停止或重新启动。选择值后，所有角色可能会失败，然后重新启动。除非那些失败后重启的角色可以记录一些信息，否则重启后无法确定选择的值。

消息在传输过程中可能会延迟任意长的时间，并且可能会重复或丢失。但是消息不会被破坏，也就是消息的内容不会被篡改(拜占庭一般问题)

演绎过程

最简单的解决方案——只有一个受体

假设只有一个接受者(可以有多个提议者)，只要接受者接受其收到的第一个提议，该提议就被选中，提议中的值就是选中值。这确保了只选择一个值。

但是，如果这个唯一的接受者倒下了，那么整个系统就不行了！

因此，必须有多个接受者！

多重受体

多个接受者的情况如下所示。那么，在多个提议者和多个接受者的情况下，如何保证选择一个值呢？

让我们开始寻找解决方案。

如果我们希望哪怕只有一个提议者提出一个值，这个值最终会被选中。

然后，获得以下约束:

P1:接受者必须接受它收到的第一个建议。

但是，这会导致另一个问题:如果每个提议者提出一个不同的值并发送给不同的接受者。根据P1，Acceptor分别接受它接收到的值，这导致选择不同的值。有不一致的地方。如下图所示:

只是因为“只要一个建议被接受者接受，该建议的价值就被选定”才出现了上述不一致的问题。因此，我们需要增加一条规定:

规定:一个被选中的提案需要被半数以上的接受者接受。

这一规定还意味着:“接受人必须能够接受一个以上的提议！否则可能导致最后没有值被选中。比如上图的情况。V1、v2和v3未被选择，因为它们都只被一个接受者接受。

当初的提议=价值已经不能满足需求，所以我们重新设计了提议，在每个提议上加了一个提议号，表示提议提出的顺序。订单“建议书=建议书编号+价值”。

虽然允许选择多个建议，但必须确保所有选择的建议具有相同的值。否则，就会出现不一致的情况。

所以有以下限制:

P2:如果选择了值为V的建议，则每个具有较高编号的选定建议的值也必须为V..

一个建议只有被接受者接受时才能被选择，因此我们可以将接受者接受的建议的P2约束重写为P2a约束。

P2a:如果选择了值为V的建议，则Acceptor接受的每个编号较高的建议的值也必须为V..

只要P2a满意，P2就能满意。

但是，考虑以下情况:假设总共有5个接受者。提议者2提出了[M1，V1]的提议，接受者2 ~ 5(超过半数)接受了该提议，所以对于接受者2 ~ 5和提议者2来说，都认为选择了V1。Acceptor1刚刚从停机中恢复过来(Acceptor1之前没有收到任何提案)，此时提案人1将【M2，V2】的提案发送给Acceptor1 (V2≠V1和m2 >: M1)，对于Acceptor1来说，这是其收到的第一个提案。根据P1(承兑人必须接受其收到的第一个建议。)，Acceptor1必须接受提议！同时，Acceptor1认为V2被选中了。这提出了两个问题:

接受者1认为V2被选中，而接受者2 ~ 5和提议者2认为V1被选中。有不一致的地方。？

V1被选中，但是Acceptor1接受的数值较高的建议【M2，V2】的数值是V2，V2≠V1。这与P2a是矛盾的(如果选择了一个值为V的建议，那么Acceptor接受的每个编号较高的建议的值也必须是V)。

所以我们需要加强P2a约束！

P2a是对接受者接受的提议的约束，但实际上提议是提议者提出的，所以我们可以对提议者提出的提议进行约束。获取P2b:

P2b:如果选择了价值为V的提案，则提案人提出的任何编号较高的提案的价值也必须为V..

从P2b可以推导出P2a，然后可以推导出P2。

那么，如何保证一个值为V的提案被选中后，提案人提出的所有编号较高的提案都具有V的值呢？

只要满足P2c:

P2c:对于任意N和V，如果提出了提议[N，V],那么存在一个由超过一半的接受者组成的集合S，它满足以下两个条件中的任意一个:-S中的每个接受者都从未接受过一个数目小于N的提议..接受者在-S中接受的数量最多的建议的值为v。

提议者产生提议。

为了满足P2b，这里有一个重要的思想:提议者在生成提议之前，首先要“学习”已经被选择或者可能被选择的值，然后把这个值作为自己提议的值。如果没有选择值，提议者可以自己决定值的值。只有这样我们才能达成协议。该学习阶段通过“准备请求”实现。

因此，我们得到了以下建议生成算法:

提议者选择一个新的提议号n，然后向一个接受者集合(超过一半)发送请求，要求集合中的每个接受者做出如下响应。(a)向提议者作出承诺？将不再接受数量少于n的提案。(b)如果接受者接受了建议，它将以小于n的最大数量响应提议者接受的建议..

我们称这个请求为编号为n的准备请求。

如果提议者收到一半以上接受者的响应，它可以生成一个数目为N，值为v [N，V]的提议。这里的v是所有回答中的一个。编号最高的建议的价值。如果所有回答中没有提议，那么V可以由提议者选择。提案生成后，提案人将其发送至？半数以上的接受者集合，预计这些接受者能够接受提议。我们称这个请求为接受请求。(注意:此时接受接受请求的接受者集合不一定是先前响应准备请求的接受者集合。)

接受者接受建议

接受者可以忽略任何请求(包括准备请求和接受请求)，而不用担心破坏算法的安全性。因此，我们这里要讨论的是，什么时候Acceptor可以响应一个请求。

我们对承兑人接受建议有以下限制:

P1a:只要接受者没有用大于N的数字响应任何准备请求，那么他可以？接受这个编号为n的提议。

如果Acceptor收到一个编号为n的准备请求，那么它之前已经响应了一个编号大于n的准备请求。根据P1a，接受者不可能接受编号为n的提议，因此，接受者可以忽略编号为n的准备请求，当然，你也可以回复一个错误，让提议者尽快知道他的提议不会被接受。

所以一个承兑人只需要记住:1。人数最多的提议被接受了。请求响应的最大数量。

Paxos算法分为两个阶段。详情如下:

(a)提议者选择一个提议编号n，然后向半数以上的接受者发送一个编号为n的准备请求。

(b)如果接受者接收到数量为n的准备请求，并且n大于接受者已经响应的所有准备请求的数量，那么它将把它发送到？编号最高的被接受的提议(如果有的话)被反馈给提议者作为响应，接受者承诺不接受任何编号小于n的提议。

(a)如果提议人收到一半以上接受人对其N号准备请求的回复，则提议人将针对[N，V]发送提议？接受超过半数接受者的请求。注:V是收到的答复中编号最高的建议的价值。如果响应正在进行中？不包含任何提议，那么v由提议者自己决定。

(b)如果接受者收到一个n号建议的接受请求，只要接受者没有作出一个n号以上的准备请求？作为回应，它接受该提议。

学习者学习选定的值。

有三种方案可供学习者学习(获取)选定的值:

如何保证Paxos算法的活性

通过选择主提议者，可以保证Paxos算法的活性。至此，我们得到了一个既能保证安全性又能保证活性的分布式一致性算法。Paxos算法。

参考数据

纸质Paxos帕克索变得简单

论文《兼职议会》

英语维基百科中的Paxos

中文维基百科

从帕克斯到动物园管理员的书