分布式选举算法Paxos

什么是Paxos算法？

Paxos算法是分布式计算领域中一个非常重要的算法，主要解决分布式系统如何就某个值（决议）达成一致的问题。一个典型的场景是分布式数据库的一致问题：如果分布式数据库的各个节点初始状态一致，又能执行相同的操作序列，那么最后能达到一个一致的状态。但是如何保证在每个节点上执行相同的命令序列呢？这就需要在每条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。Paxos算法便是这样一种一致性算法，它由大牛Lamport于1990年提出，在Lamport的论文中，他虚拟了一个叫“Paxos”的城邦并以讲故事的方式阐述算法，因此叫做Paxos算法。

1.应用场景

（1）分布式中的一致性

Paxos算法主要是解决一致性问题，关于“一致性”，在不同的场景有不同的解释：

NoSQL领域：一致性更强调“能读到新写入的”，就是读写一致性

数据库领域：一致性强调“所有的数据状态一致”，经过一个事务后，如果事务成功，所有的表数据都按照事务中的SQL进行了操作，该修改的修改，该增加的增加，该删除的删除，不能该修改的修改了，该删除的没删掉；如果事务失败，所有的数据还是在初始状态；

状态机：在状态机中的一致性更强调在每个初始状态一致的状态机上执行一串命令后状态都必须相互一致，也就是顺序一致性。Paxos算法中的一致性指的就是这种情况，接下来我们会对这种场景进一步讨论。

（2）MQ

假如所有系统的Log信息都写入一个MQ Server，然后通过MQ把每条Log指令发异步送到多个Log Server写入文件（写入多个Log Server的原因是对Log文件做备份以防数据丢失），则所有Log Server上的数据肯定是一致的（Log内容及顺序完全相同），因为MQ本身就有排序功能，只要进了Q数据也就有了序，相当于编了全局唯一的号，无论把这些数据写入多少个文件，只要按编号，各文件的内容必定是一致的，但一个MQ Server显然是一个单点，如果宕机，会影响整个系统的可用性。

（3）多MQ

要解决MQ单点问题，首选方案是采用多个MQ Server，即使用一个MQ Cluster，客户端可以访问任意MQ Server，不同的客户端可能访问不同MQ Server，不同MQ Server上的数据内容、顺序可能不一致，如果不解决这个问题，每个MQ Server写入Log Server的内容就不一致，这显然不是我们期望的结果。

（4）NoSQL中的数据更新

一般的NoSQL都会通过数据复制的形式保证其可用性，但客户端对多数据进行操作时，可能会有很多对同一数据的操作发送的某一台或几台Server，有可能执行：Insert、Update A、Update B....Update N，就一次Insert连续多次Update，最终复制Server上也必须执行这一的更新操作，如果因为线程池、网络、Server资源等原因导致各复制Server接收到的更新顺序不一致，这样的复制数据就失去了意义，如果在金融领域甚至会造成严重的后果。

上面这些不一致问题性正是Paxos算法要解决的，当然这些问题也不是只有Paxos能解决，在没有Paxos之前这些问题也得到了解决，比如通过使用双Master模式的MQ解决MQ单点问题；通过使用Master Server解决NoSQL的复制问题，但这些解决方法都存在一些缺陷，要么难水平扩展，要么影响可用性。当然除了Paxos算法还有其他一些算法也试图解决这类问题，比如：Viewstamped Replication算法。

2.Paxos如何解决这类问题

Paxos对这类问题的解决就是试图对各Server上的状态进行全局编号，如果能编号成功，那么所有操作都按照编号顺序执行，一致性就不言而喻。当Cluster中的Server都接收了一些数据，如何进行编号？就是表决，让所有的Server进行表决，看哪个Server上的哪个数据应该排第一，哪个排第二...，只要多数Server同意某个数据该排第几，那就排第几。

很显然，为了给每个数据唯一编号，每次表决只能产生一个数据，否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步，我们称表决的数全可以得出最终结果。