paxos Paxos的通俗理解以及在数据库高可用上的使用

最近大家都在讨论Paxos算法。看了很多网上的文章，总觉得有点晦涩。经过一段时间的研究，对Paxos有了一些了解。这里想总结一下，希望抛砖引玉。

1.你为什么需要帕克斯

Paxos要解决的问题是分布式系统中的一致性问题。那么“分布式系统中的一致性问题”到底是什么呢？在分布式系统中，为了保证数据的高可用性，我们通常会保留多个数据副本，这些副本将被放置在不同的物理机器上。为了保持副本一致，所有副本的更新顺序应该一致。因为数据的增加、删除、修改、查询操作一般涉及多个客户端的并发操作，哪个客户端先做，哪个客户端后做，更新顺序要有保证。如果不是分布式的，可以加锁，谁申请加锁谁先操作，但是有一个单点问题。Paxos协议主要有两个用途:一个是实现全局锁服务或者命名和配置服务，比如Google Chubby和Apache ZooKeeper。另一种用法是用它把用户数据复制到多个数据中心，比如Google Megastore和Google扳手。

以一个分布式KV数据库为例，假设数据库提供Put和Get两种操作。具体架构如下:

在这样的架构下，多个服务器可以组成一个集群，以避免单点问题。我们需要解决的是三个服务器必须同步，也就是说如果请求put ("a "，1)发送到集群并成功，那么整个集群中的任何一个服务器都必须包含(" a "，1)。另外，假设多个客户端并发访问集群，来自不同客户端的请求可能会落在不同的服务器机器上，比如put ("b "，2)和put ("c "，3)，我们需要保证哪些客户端请求先做，哪些客户端请求后做，并保证更新顺序，这是Paxos算法需要解决的问题。

2.Paxos算法

先简单描述一下Paxos算法，对算法本身有一个直观的认识，然后结合下面的例子进一步了解。

Paxos算法中有三个主要角色:

提议者:提议者

接受者:决策者

学习者:最终的决策学习者

实施时往往采用一套固定数量的服务器，每台服务器同时扮演上述三个角色。

Paxos算法分为以下三个阶段:

1.准备阶段

(1)发起人向多数承兑人发起1)提议人(纪元号，值)的准备请求。

(2)2)接受者收到准备请求，如果epochNo小于之前收到的，则直接拒绝；如果电子方案号大于收到的电子方案号，则将电子方案号最大的方案返回给提案人。

(3)由3)提议者发起的提议在进入下一个接受阶段之前，必须至少收到来自多于大多数接受者的准备响应；否则，有必要在准备阶段再次向大多数接受者发出准备请求。

2.接受阶段:

(1)演示者收到大多数接受者的“准备”响应后，查看接受者是否接受了1)提议者。如果没有已接受的建议，则提出建议并启动接受请求；如果已经有一个接受建议，从其中选择具有最大电子技术号的建议，并启动对此建议的接受请求。

(2)接受方收到请求后，如果建议书的电子技术号大于其上次响应准备请求的电子技术号，则接受方接受该请求；否则，请求将被拒绝。

3.学习阶段:

接受者接受的所有建议都应不断通知学习者，或者学习者应主动询问。一旦学习者确认建议书被大多数接受者接受，这意味着建议书的价值被选择，学习者可以了解建议书的价值，同时，他自己的服务器将不再接受建议书的请求。

我喜欢通过例子来理解理论，理论来源于生活。我会用生活中的例子来描述算法。

假设一群驴友决定端午节去旅游。全国有10个驴友。为了达成协议，这10个人又找了5个队长。5个队长互不交流，只给10个驴友发短信。

第一阶段(申请阶段)，驴友给五个队长发短信申请和他们沟通。队长任何时候只能和一个驴友交流。每条信息都有时间。组长采取的原则是同意用最新的消息发送时间和驴友沟通。如果有更新的消息，就用更新的消息和驴友沟通。至少大部分队长同意沟通，让驴友进入实质性沟通的第二阶段。

第二阶段(交流阶段)，获得交流权的驴友A收到队长发给他的旅游目的地，可能有几种情况。

第一种情况:所有通信队长都还没决定去哪里旅行。这时，驴友a会把他想去的目的地发给船长(比如马尔代夫)。因此，大多数船长可能会同意。整个过程完成后，他将前往马尔代夫，其他驴友迟早会知道。另外，意味着失败。可能是队长没回复(打电话给女朋友)，也可能是其他驴友抢了交流权(上面说队长只和最新的短信交流)。如果失败，A需要重启第一阶段申请，并向组长发送短信申请通信权限。

第二种情况:至少有一个船长决定了目的地。这时A会收到不同队长决定的多个目的地，这些目的地是不同队长和不同驴友在不同时间决定的。a将首先检查一些旅游目的地是否得到了大多数(超过一半)团队领导的同意。如果有(假设三个领队决定去三亚，一个去拉萨，可能因为某种原因没有照顾)，证明整个决定过程已经达成一致。a收拾东西去三亚，结束！

如果没有一个达到一半(比如两个去三亚，一个去拉萨，一个去昆明，一个没管)，A这个时候可能想去马尔代夫，但是并没有按照自己的意愿乱来(这是Paxos的关键，后者认可前者，否则整个过程没完没了)， a会根据所有接待队长的旅游目的地找到最新的决定地点(比如去昆明是队长一分钟前决定的，这时候去昆明的决定更新了，这样下一个抢到交流权的驴友很可能会去昆明，越来越多的队长决定去昆明。

一旦大部分(超过一半)队长同意在某个时刻去某个地方，比如昆明，后续得到交流权的驴友B会发现大部分队长都决定去昆明了，它会服从，最后所有的驴友都达成了去昆明的协议。

Paxos的基本思路大致就是上面这个过程。Paxos用的是少数服从多数的思想。只要n (n为奇数，至少大于等于3)个节点中有[N/2]+1(其中N/2向下舍入)个或更多个节点与某个决策一致，那么系统就被认为是一致的。在这种情况下，客户端不需要与所有的服务器通信，而是选择其中的大部分。不需要所有服务器都处于工作状态，有些服务器是挂起的。只有半数以上存活下来，整个过程才能继续，容错性相当好。

帕克斯里的接受者相当于上面的船长，提议者相当于上面的驴友，而epochNo。相当于示例中申请短信的发送时间。Paxos最费时间的地方是，需要他们一半以上的人同意沟通，才能进入第二步。试想一下，刚开始的时候，所有的驴友都给队长发疯狂短信，每个队长都收到不同驴友的最新短信，很难达到一半以上同意和一个驴友交流的状态。为了减少这个时间，这里不详述Paxos和Fast Paxos的改进。另外，paxos不是指一个协议，而是一类协议的总称。比较常见的paxos协议有基本paxos和多paxos。这里的例子是基本的paxos。基本的paxos协议比较复杂，效率相对较低，所以现在所有的paxos相关协议的系统，一般都是基于多paxos的。如果你感兴趣，你可以参考https://zhuanlan.zhihu.com/p/25664121的文章

3.Paxos在数据库高可用性中的应用

作为dba，为了实现高可用性，最常用的高可用性模式是主从模式，以mysql为例，主要有几种方式

(1)强同步复制，binlog同步到从库后，从库可以返回到主库，然后提交给客户端成功。这有一个问题。一旦主库和从库之间的网络紧张，甚至从库关闭，主库就不能再提供服务。这种模式实现了强大的数据一致性，但牺牲了服务的可用性。

(2)异步复制:主库本地写成功后，立即返回客户端说成功，不用等待从库回复。这样，一旦主库关闭，少量日志可能无法与从库同步，从而导致部分数据丢失。这种模式有很好的可用性，但代价是数据的一致性。

(3)半同步复制，这是一种折衷，主要是指从库节点收到的至少一个日志返回到主库ok后，可以返回到客户端成功提交，在网络环境不好的时候可能退化为异步复制。

另外，主从模式还有一个不可避免的问题，就是选择主。对于主从模式，很多高可用的方案，比如MMM、MHA、中间层等等，都诞生了很久，但显然理论和思路都不是最先进的。

综上所述，主从模式下处理数据库高可用性存在很多缺陷。为了改进这种数据同步模式，我们可以对数据库的高可用性提出几个要求:

(1)数据没有丢失

(2)服务的持续可用性

(3)自动选择主控形状

(4)自动容错

以上三个需求可以通过使用paxos协议的日志同步来实现。当然，paxos协议需要依赖一个基本假设，即主备之间的大部分机器(N/2+1)是活的，它们之间的网络通信是正常的。如果不满足此条件，服务将无法启动，数据也无法写入或读取。