近期咱们都在评论 Paxos 算法，我看了许多网上的文章，总觉得有些不流畅难明，经过一段时刻研讨，对 Paxos 有了一些了解，在管中窥豹总结一下，希望能抛砖引玉。

为什么需求 Paxos

Paxos 要处理的问题，是分布式系统中的共同性问题。那么究竟什么是“分布式系统中的共同性问题”呢？

在分布式系统中，为了确保数据的高可用，一般，咱们会将数据保存多个副本(replica)，这些副本会放置在不同的物理的机器上。

副本要坚持共同，那么，避实就虚副本的更新序列就要坚持共同。由于数据的增修改查操作一般都存在多个客户端并发操作，究竟哪个客户端先做，哪个客户端后做，更新次序要确保。

假如不是分布式，那么能够经过加锁的办法，谁先请求到锁谁就先操作，但这就存在单点问题。

Paxos 协议主要有两种用法：

• 用来完成大局的锁服务或许命名和装备服务，例如 Google Chubby 以及 Apache ZooKeeper。
• 用它来将用户数据仿制到多个数据中心，例如 Google Megastore 以及 Google Spanner。

以一个分布式的 KV 数据库为例，假定数据库对外供给 2 种操作 Put 和 Get，详细架构如下：

在这样一个架构下，能够经过多台 Server 组成集群来防止单点问题。

咱们需求处理的是 3 台 Server 有必要坚持同步，也便是说，假如向集群发送恳求 Put(“a”,1)并成功，那么整个集群恣意一台 Server 有必要含有("a",1)。

别的假定此时多个 client 并发拜访集群，不同客户端的恳求或许会落入到不同的 Server 机器上。

比方并发有 Put("b”,2)和 Put(“c”,3)，咱们需求确保哪个客户端恳求先做，哪个后做，确保更新次序，这便是 Paxos 算法需求处理的问题。

大白话了解 Paxos 算法

咱们先来简略描绘一下 Paxos 算法，对算法自身有一个直观的知道，然后再结合后边的比如来进一步了解。

在 Paxos 算法中，主要有 3 种人物：

• Proposer：提议者
• Acceptor：决议计划者
• Learner：终究决议计划学习者

完成的时分往往选用一组固定数目的 Server，每个 Server 一起担任上述三个人物。

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

Prepare 阶段

Proposer 向大多数 Acceptor 建议 Proposal(epochNo,value)的 Prepare 恳求。

Acceptor 收到 Prepare 恳求，假如 epochNo 比之前接纳到的小，直接回绝；假如 epochNo 比之前现已接纳的大，就将现已接纳到的 epochNo ***的 Proposal 回来到 Proposer。

Proposer 建议的 Proposal 至少要收到大多数以上的 Acceptor 的 Prepare 应对后，才干进入接下来的 Accept 阶段，不然需求从头进行 Prepare 阶段向大多数 Acceptor 建议 Prepare 恳求。

Accept 阶段

Proposer 收到大多数的 Acceptor 的 Prepare 应对后，看 Acceptor 是否现已有被承受的 Proposal。

假如没有现已承受的 Proposal，就自己提出一个 Proposal，建议 Accept 恳求；假如现已有被承受的 Proposal，就从中选出 epochNo ***的 Proposal，建议对该 Proposal 的 Accept 恳求。

Acceptor 收到恳求后，假如该 Proposal 的 epochNo 比它***一次应对 Prepare 恳求的 epochNo 要大，那么就承受该恳求；不然回绝该恳求。

Learn 阶段

避实就虚 Acceptor 承受的 Proposal 要不断告诉 Learner，或许 Learner 主动去查询，一旦 Learner 承认 Proposal 被大多数的 Acceptor 承受。

那么标明这个 Proposal 的 Value 被 Chosen，Learner 就能够学习这个 Proposal 的 Value，一起自己的 Sever 上就不再受理 Proposor 的恳求。

我喜爱经过比如来了解理论，理论源于日子，下面我以日子中的比如来进行该算法的描绘。

假定一群驴友决议新年去旅行，驴友遍及全国各地，总共 10 人，为了能到达共同，这 10 个人别的找 5 个作为队长。5 个队长之间彼此不通讯，只跟 10 个驴友发短信。

***阶段（请求阶段），驴友发短信给 5 个队长，请求与队长进行交流，队长在任何时刻只能与一个驴友交流。

发送的每条短信都带有时刻，队长选用的原则是赞同与短信发送时刻***的驴友交流。

假如呈现更新的短信，则与短信更新的驴友交流。至少大多数队长赞同交流了，这个驴友才干进入第二阶段实质性交流。

第二阶段（交流阶段），取得交流权的驴友 A 收到队长们给他发的旅行地，或许有如下几种状况：

***种状况：交流的队长们悉数都还没有决议究竟去哪里旅行，此时驴友 A 会把自己想去的旅行地发给队长们（比方马尔代夫）。

成果或许大多数队长赞同了，整个进程履行完毕，便是去马尔代夫旅行了，其他的驴友迟早会知道。

除此之外就标明失利了，或许队长没有回复(跟女友打电话去了)，或许被其他驴友抢占交流权了（上面说过队长只跟***的短信的人进行交流）。

假如失利了，A 需求从头开始***阶段请求，从头给队长们发短信请求交流权。

第二种状况：至少有一个队长现已决议旅行地了，这个时分 A 会收到不同队长决议的多个旅行地，这些旅行地是不同队长跟不同驴友在不一起间做的决议。

A 会先看看有的旅行地是不是被大多数（对折以上）队长赞同了，假如有(管中窥豹假定 3 个队长决议去三亚，一个去拉萨，别的或许某种原因没理睬），那证明整个决议进程现已到达共同了，A 拾掇拾掇去三亚吧，完毕！

假如都没有到达对折（比方 2 个去三亚，1 个去拉萨，1 个去昆明，1 个没理睬），这时分 A 或许想去马尔代夫，但也不依照自己志愿乱来了（管中窥豹是 Paxos 的关键所在，后者认可前者，不然整个进程无止境了）。

A 会依据收到队长的避实就虚旅行地中找到***的那个决议地（比方去昆明是那个队长在 1 分钟前决议的，去拉萨的队长是半小时前决议的，去三亚的队长是 1 小时前决议的），所以 A 顶***的决议，去昆明。

这时分去昆明的决议又更新了，这样下一个抢到交流权的驴友也很大或许会顶去昆明，这样决议去昆明的队长会越来越多。

一旦某个时刻大多数（对折以上），队长都赞同了去某个地址，比方去昆明，后续取得交流权的驴友 B 会发现大多数队长都决议去昆明晰，它也会遵守，终究避实就虚的驴友都到达共同去昆明。

Paxos 的根本思维大致便是上面进程，Paxos 运用的是推举，少数遵守多数的思维。

只需 N 个(N 为奇数，至少大于等于 3)节点中，有[N/2]+1(管中窥豹N/2为向下取整)或以上个节点赞同了某个决议，则以为系统到达了共同。

这样的话，客户端不用与避实就虚服务器通讯，挑选与大部分通讯即可；也无需服务器都悉数处于作业状况，有一些服务器挂掉，只要确保对折以上存活着，整个进程也能继续下去，容错性相当好。

Paxos 中的 Acceptor 相当于上面的队长，Proposer 相当于上面的驴友，epochNo 号就相当于比如中请求短信的发送时刻。

Paxos 最耗费时刻的当地就在于需求对折以上赞同交流了才干进入第二步。

试想一下，一开始，避实就虚驴友就给队长狂发短信，每个队长收到的***短信来自不同驴友。

这样，就难以到达对折以上都赞同与某个驴友交流的状况，为了减小这个时刻，Paxos 还有 Fast Paxos 的改善等等。

别的，Paxos 并不指代一个协议，而是一类协议的总称，比较常见的 Paxos类协议有：basic Paxos 和 multi-paxos。

管中窥豹的比如说的是 basic paxos，basic paxos 协议较杂乱，且相对效率较低，所以现在避实就虚和 paxos 有关的协议的系统，一般都是根据 multi-paxos 来完成的。

有爱好了解能够参阅文章：https://zhuanlan.zhihu.com/p/25664121

Paxos 在数据库高可用上的运用

作为 DBA，为了完成高可用，最常用的高可用方法是主从形式，以 MySQL 为例，主要有如下几种：

强同步仿制

binlog 同步到从库之后，从库回来给主库 ok 之后才干回来给客户端提交成功。

这就有个问题，一旦主从之间网络呈现颤动，乃至从库宕机，则主库就无法再继续供给服务，这种形式完成了数据的强共同，可是献身了服务的可用性。

异步仿制

主库写本地成功后，马上回来给客户端说成功，无需等候从库应对。

这样一旦主库宕机，或许会有少数的日志没有同步到从库形成部分数据丢掉，这种形式可用性很好，可是献身了数据的共同性。

半同步仿制

这种形式是一个折中，主要指至少有一个从库节点收到日志回来给主库 ok 之后，这时就能够回来给客户端提交成功，当网络环境欠好的时分或许退化为异步仿制。

别的主从形式还有一个无法绕过的问题，便是选主，为了主从形式的选主，长期以来也诞生了许多种高可用计划，如 MMM、MHA、中间层等等，但明显理论和思路都不是***进的。

总结一下，针对主从方法处理数据库高可用有许多缺点，要想改善这种数据同步方法，能够整理数据库高可用的几点需求：

• 数据不丢掉
• 服务继续可用性
• 主动选主
• 主动容错

运用 Paxos 协议的日志同步就能够完成以上的三个需求，当然 Paxos 协议需求依靠一个根本假定。

主备之间有多数派机器(N/2+1)是存活且它们之间的网络通讯正常，假如不满足这个条件，则无法发动服务，数据也无法写入和读取。

所以咱们能够运用 Paxos 进行 redolog 或许 binlog 的仿制，然后确保高可用强共同的集群。

主从的切换也不需求忧虑，只需求有个 vip，后端映射后边数据库的多点就行，Paxos 会主动确保多点的共同性写入，业界阿里云运用 Paxos 或许 raft 来做的企业三节点的 MySQL 集群。

蒲聪，渠道事业部 DBA，2013 年 6 月参加去哪儿网，现在担任付出渠道事业部的 MySQL 数据库和 HBase 全体的运维作业，从无到有树立去哪儿网 HBase 运维系统，在 MySQL 和 Hbase 数据库上有丰厚的架构、调优和毛病处理等经历。现在专心于分布式数据库范畴的研讨和实践作业。