为什么需要分布式

使用分布式的原因大体有两个，一个是性能，一个是高可用。

提升性能的话，可以用更好的机器，或者用更多的机器。

一般科学研究的更倾向于用更好的机器，因为这样的架构更简单。

但工程中，多数的时候需要考虑成本（穷），一般会通过使用更多的机器提升性能。

在高可用方面，因为服务器有一定的概率会挂掉，如果只有一体服务器，一旦挂掉，服务就不可用了。

为了提高可用性，会使用多台服务器，这样有服务器挂掉的话，其他服务器还可以继续提供服务。

分布式及 Paxos 所解决的问题

分布式和常见的编程所需要考虑的问题有很大的不同。

比如我们设置一个变量，a = 1，一般可以认为，这个语句在执行完之后，内存中 a 存的就是 1（并发的时候，有 cache 的存在，需要加 memory_barrier）。

但在分布式中，有多个节点存在，之间的通信只能依赖网络。但网络是不稳定的。

所以消息发出去后，在没有响应的时候，我们不知道这个节点，是否还活着，是否收到了消息，是否有处理消息。

Paxos 所做的事，就是在这种情况下，让多个节点达成对于某件事，达成一致。比如在多个节点中选出唯一的 master 节点。

Paxos 在真实世界中的模拟

所谓共识，就是所有人对某件事情达成一致。比如所有人都认为 PHP 是世界上最好的语言，那么这个就是一个共识。

但每个人都有不同的想法，Paxos 要做的是让这些不同的想法最终变成一个。

为了达成一致，我们首先规定，多数人所认可的事情，就是事实。就好比投票，多数人同意的，就是大家必须接受的事实。

这个过程，有两个行为，提议和接受提议。为了方便讨论，我们把人按照功能分为两类，提议者和接受者。

我们所要做的事情就变成了让多数提议者接收某个事情，最终让这件事成为所有人都接受的事情。

提议者会通过对话 (message passing) 的方式，把提议告诉接受者。

这里的对话，和现实中的对话一样，比如 A 问 B：你吃了吗。

B 可能没听到，可能听到不回，可能答非所问，可能突然间挂掉。也有可能 A 先问 C，然后 B 也问 C。但 C 先回答了 B，之后再回答 A。

为了方便讨论，我们现在假设，有三个提议者和三个接受者。这三个提议者，最开始，分别认为，Ruby、Python、PHP 是最好。

提议者，为了让更多的接受者接受自己的想法，就会跟所有的接受者说，xxx 是最好的。

如果接受者不接受提议，那么肯定无法达成共识。所以接受者必须要能接受提议，我们先假设只接受一条。也就是，接受了 Ruby 是最好的，就不能接收其他的了。

这个时候会出现，Ruby、Phthon、PHP 各有一个接受者。这样显然无法达成共识。那么可以推导出，接受者，必须可以更改自己所接受的东西。

所以，接受者需要可以接受新提议。既，假设某个接受者，先听到 Ruby 是最好的，后来又听到 PHP 是最好的，这个时刻，就需要认为 PHP 是最好的。

在这种条件下，如果提议者，每次都坚持自己第一次的提议，依旧可能无法达成共识。

为了达成一致，我们规定，提议者只能在已经接受的提议中选，如果没有被接受的提议，才能自己提出一个。

那么，现在流程就变成了，准备提议 (获取当前情况) 和提出提议。

因为只能在接受了的提议中选，多次准备、提议之后，可被接受的提议会越来越少，最终会变成一个，既达成共识。

我们在这个基础上进行进一步优化。

在准备这个过程中，我们向所有接受者询问，因为我们只需要争取大多数人的意见，所以我们不需要等所有接受者的返回，只要等到大部接受者的返回即可。

当获取到多数接受者的返回时，为了更快收敛，我们选取最新的那个提议（最后获得的）。

这个流程会不会出现没有进展的情况？会。

假设提议者 P1 从多数接受者获得的最新提议是 p1，P2 从多数接受者获得的最新提议是 p2。之后 P1、P2 将提议发给接受者。

两个人，都需多数接受者接受提议，两组接受者为 S1、S2，因为 S1、S2 都是大多数，所以有一个人都在这两个集合里。假设这个人为 A0。

我们再来看时序，P1 向所有人提议 p1，P2 向所有人提议 p2。A0 这个时候接受 p1 或者 p2。

之后 P1、P2 进行询问。依旧假设是 S1、S2 返回了结果。我们假设 P1 和 P2 最后接收到消息的接受者，不是 A0。则 P1 依旧会提议 p1，

P2 依旧会提议 p2，既没有进展。

但我们知道，这种情况，只有在符合一定条件的情况下，才会出现。所以从概率的角度来讲，多次进行准备、提议后，最终会收敛到唯一结果。

从模拟到算法

在模拟情景中，接受者和提议者，都是根据自己接受到的消息新旧程度进行更新，也就是新信息会替换掉旧信息。

但在分布式的场景里，主机会被部署在不同的地点。节点和节点间的延迟不一样。会出现 A 先发，B 后发，但 B 先到的情况。

如果按照接收到的时间，显然是不公平的。

也不能用发消息的时间戳，因为多个机器的时间可能是不一样的（开 NTP 也会有问题）。

所以在发消息的时候，附带一个数字，当接收消息的人，收到消息的时候。按照这个数字的大小顺序来判断新旧。而每个节点，递增生成这个数据。

算法描述

定义

最新提议：提议者，每次发提议的时候，会带上生成的数字，提议对应对应数字最大的，就是最新的提议。

两个阶段

准备阶段

提议者，生成数字 n，并将这个数字发送给多数接受者。

接受者，接受到这个数字 n，如果该接受者，之前收到比 n 大的数字，则忽略这条消息。

如果这个数字是接收到的消息中最大的，则回复提议者，自己最新接受的提议。

提议阶段

提议者，从多数接受者那，接收到之前准备消息的返回。

如果接受者没有返回任何提议，则提议者可以随意提提议。

如果有提议返回，则需要用最新的提议进行提议。

提议者需要将选择的提议和之前数字 n 发送给接受者。

接受者，接收到提议者发来的提议请求，如果之前没有收到过比 n 大的请求，则接受提议。

最后

经过多次讨论和交流意见，大家愉快的一致同意 PHP 才是世界上最好的语言。

参考

• The Paxos Algorithm
• Paxos Made Simple - Leslie Lamport
• Paxos (computer science) - Wikipedia
• 如何浅显易懂地解说 Paxos 的算法？