书接上文 - Multi Paxos

在上一篇文章中，我们提到了Basic Paxos和Multi Paxos的异同。在Paxos Made Simple论文中，作者提到了Multi Paxos的一种实现。这个实现允许我们对一个连续的数据流（也可以称为复制日志，replicated log）达成共识，从而实现节点状态的一致性复制。

确定性状态机

我们可以将系统中的每一个节点抽象为一个有着确定性状态机，即给定多个状态一致的状态机，在执行同一个命令之后，其状态仍保持一致。（可以想一想编译原理里面的DFA）

Leader - 系统中唯一的proposer

如果系统中存在有多个proposer，那么就很可能会出现多个提案相互干扰的情况。虽然根据证明，最终这些提案都会收敛到一致，但是性能会非常低下。所以我们可以在系统中通过选举，选出一个leader做为主proposer（distinguishied proposer），所有的提案都由leader提出。

这样一来，在绝大多数情况下都不会出现提案相互干扰的情况。只有在leader切换的瞬间，可能会出现相同编号的不同提案，但是我们的算法可以很好的处理这种情况。

分布式系统中的“TCP”

类似于TCP协议中序列号，Multi Paxos中的每一个命令都有一个递增的编号。即我们前一个执行的命令是100号，那么下一个执行的命令一定是101号 …

一致性协议 - Paxos

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

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

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

Paxos算法

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

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

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

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

划重点：

1. 需要半数以上居民的认可，才能声称拥有车位。这个居民被称为车位的“公认拥有者 …