Paxos算法的通俗理解

Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。这个算法被认为是同类算法中最有效的。Paxos与MySQL相结合可以实现在分布式的MySQL数据的强一致性。

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

在Paxos算法中，主要有3种角色：
Proposer：提议者
Acceptor：决策者
Learner：最终决策学习者
实现的时候往往采用一组固定数目的Server，每个Server同时担任上述三个角色。
Paxos算法分为以下三个阶段：
1、Prepare阶段
(1)Proposer向大多数Acceptor发起Proposal(epochNo,value)的Prepare请求。
(2)Acceptor收到Prepare请求，如果epochNo比之前接收到的小，直接拒绝；如果epochNo比之前已经接收的大，就将已经接收到的epochNo最大的Proposal返回到Proposer。
(3)Proposer发起的Proposal至少要收到大多数以上的Acceptor的Prepare应答后，才能进入接下来的Accept阶段，否则需要重新进行Prepare阶段向大多数Acceptor发起Prepare请求。
2、Accept阶段：
(1)Proposer收到大多数的Acceptor的Prepare应答后，看Acceptor是否已经有被接受的Proposal。如果没有已经接受的Proposal，就自己提出一个Proposal，发起Accept请求；如果已经有被接受的Proposal，就从中选出epochNo最大的Proposal，发起对该Proposal的Accept请求。
(2)Acceptor收到请求后，如果该Proposal的epochNo比它最后一次应答Prepare请求的epochNo要大，那么就接受该请求；否则拒绝该请求。
3、Learn阶段：
所有Acceptor接受的Proposal要不断通知Learner，或者Learner主动去查询，一旦Learner确认Proposal被大多数的Acceptor接受，那么表示这个Proposal的Value被Chosen，Learner就可以学习这个Proposal的Value，同时自己的Sever上就不再受理Proposor的请求。

Paxos协议数据同步方式相对于基于传统1主N备的同步方式有啥区别？
一般情况下，传统数据库的高可用都是基于主备来实现，1主1备2个副本，主库crash后，通过HA工具来进行切换，提升备库为主库。在强一致场景下，复制可以开启强同步，Oracle和Mysql都是类似的复制模式。但是如果备库网络抖动，或者crash，都会导致日志同步失败，服务不可用。为此，可以引入1主N备的多副本形式，我们对比都是3副本的情况，一个是基于传统的1主2备，另一种基于paxos的1主2备。传统的1主两备，进行日志同步时，只要有一个副本接收到日志并就持久化成功，就可以返回，在一定程度上解决了网络抖动和备库crash问题。但如果主库出问题后，还是要借助于HA工具来进行切换，那么HA切换工具的可用性如何来保证又成为一个问题。基于Paxos的多副本同步其实是在1主N备的基础上引入了一致性协议，这样整个系统的可用性完全有3个副本控制，不需要额外的HA工具。而实际上，很多系统为了保证多节点HA工具获取主备信息的一致性，采用了zookeeper等第三方接口来实现分布式锁，其实本质也是基于Paxos来实现的。