看到了一些描述paxos协议的文章，但是始终都似懂非懂的样子，感觉是自己没有get到点，可能大多数文章描述的都是理论上的一些过程，没有清楚的描述来龙去脉吧；另外号称是最难懂的一致性算法，可能也让我产生了理解障碍；；；在这篇博客中，我尝试着去梳理一下吧，能弄懂一点是一点；；可能带着问题去理解会是一个比较好的方式吧

我的问题

什么是分布式系统中的一致性场景

  谈起分布式系统中有一个分布式事务的场景，分布式事务是在多台机器上实现一个原子操作，相比单个数据库事务，分布式事务要考虑更多的问题例如网络环境，目前听的比较多的分布式事务协议就是2PC了，这是一类一致性问题（这是强一致性的情况，由于CAP定理的限制，要实现强一致性那么就要牺牲掉高可用，这对分布式系统是致命的，所以目前追求的比较多的是最终一致性的解决方案例如异步消息--这应该不再属于事务的范畴了），这是针对分布式事务而言的。
  另一类一致性场景，我是这么理解的，在分布式系统中，为了解决单点故障，数据必须做冗余，比较典型的例如数据库复制，log复制，姑且称之为副本一致性，副本间的数据一致性也可以分为强一致性和最终一致性；当然除了强一致性和最终一致性中间还有其他级别的一致性，我没有详细的了解。
  以上是分布式系统中常见的两类关于一致性的实际场景；除了事务和一致性场景，分布式系统中还存在例如选主、分布式锁等共识场景；说白了，只要是涉及到多节点协作，就需要一致性协议的参与；
  基于一致性协议，我们就能够保障集群中多个节点的数据或状态一致性，这一点对于分布式系统至关重要，因为分布式系统中的节点可能随时会发生任意故障，有了一致性集群之后就意味着我们有了一个可用性极高的系统。
  在英语中，consistency(transaction) 与 consensus(paxos) 都有一致性的意思，两者的区别可以理解为consensus主要在达成共识上，然后consistency可以理解为执行上；

一致性问题与分布式事务

  上一个问题已经说到，分布式事务可以理解为一类一致性场景，但是这个和paxos其实是两回事，我的理解是paxos要解决的是比分布式事务更一般的问题；在分布式系统中，为了应对可能出错的场景例如进程崩溃或者网络延迟等，从而使系统更加的可靠，需要进程间对某个值达成一致(我们称之为共识问题)，例如'多节点事务提交'，'选主问题'，'状态机复制'，原子广播；
  上面说到paxos要解决比分布式事务更一般的问题，那么分布式事务中是否有paxos的用武之地呢？ 答案是肯定的，上面说到目前的分布式事务的主流解决方案有2pc和3pc，2pc会有单点故障的问题，并且会造成数据的不一致(当commit消息发送一半失败)，3pc解决了2pc的一部分问题，但还是会有不一致的情况；关于paxos与事务的讨论参见Gray和Lamport大神合著的'Consensus on Transaction Commit'一文；
  想象一个场景，在一次分布式事务中，我们需要保证的是所有的子事务要么都成功，要么都不成功，假设我们有一个paxos集群，这个集群保证其中的数据是强一致的（客户端调用put(x) = y, 一旦写入成功，则x的值在集群存在且能提供服务的情况下，一定会返回get(x) = y），那么每个子事务之需要上报paxos集群所有子事务的状态，那么所有的子事务节点就可以根据其他子事务的状态来决定自己是否需要回滚。

Paxos不是完美的

  Paxos并不是一个完美的解决一致性问题的协议；FLP结果已经指出了这一点（即使系统中只有一个进程失败，也不存在一个可以使其他的进程达成一致的协议或者算法）；

Paxos要解决的问题

  简单说来，Paxos的目的是让整个集群的结点对某个值的变更达成一致。Paxos算法基本上来说是个民主选举的算法——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案，是否通过这个提案取决于这个集群中是否有超过半数的结点同意（所以Paxos算法需要集群中的结点是单数）

Paxos在工程中的应用

  其实看到paxos的第一眼，我就在想这玩意儿到底能干嘛，能够用来解决哪一类问题？工程中如何使用?它能做分布式的事务吗？如果是保证多个集群中的节点一致的话又有什么用呢？ 它能被用于工程上的那些领域呢？它与现在的例如mysql主从同步又有什么关系呢？
  其实在弄清楚一些基本的概念性的东西之后，对paxos就会有基本的认识，例如paxos要解决的基本问题，结合分布式系统的中的一些问题以及目前的解决方案，对paxos就会有一个大致的轮廓；
  具体来说Paxos在工程中的应用主要有：多节点复制（状态及复制问题，也是paxos最大的用途）-- 可以保证各个节点看到的消息顺序相同；选主操作；naming service； config service；

业界实现

比特币 chubby zookeeper 腾讯phxpaxos 阿里X-Paxos raft 2pc etcd
  比特币的共识算法比较奇特，它使用一个叫做PoW(proof of Work，工作量证明)的东西来提高节点提出提议的门槛(计算hash，目前靠电力去算)，据说这样可以有效减少恶意的参与；另外还有PoS/PBFT等共识协议；
chubby是google的一个分布式锁服务，由于需要解决单点的问题引入了multi-paxos的实现；对于chubby来说，对应的锁服务的实现才是其重点，不过底层的一致性保障协议也是非常重要的；
  zookeeper采用了一个在Paxos上改进的ZAB(zookeeper atomic broadcast)协议，ZAB协议设计了支持崩溃恢复；需要提出的是chubby和zk使用的协议都是没有经过理论证明的，但是在工程中已经证明了没有什么太大的问题了；
  2pc全称两阶段提交协议，对应的还有3阶段提交协议；是分布式事务业界的主流实现，优点是简单明了，分为precommit和commit两个阶段，并且需要一个事务协调器，precommit对各个节点发送命令锁定相应的资源，全部成功之后发送commit命令，缺点是存在单点故障，并且会产生不一致的情况；
  raft协议可以理解为paxos的简化版本，没有详细了解；
  其他协议还有比如PoS、PoH、PoA、PBFT等等

实现分布式一致性协议

  大部分人基本上都不会有参与一致性协议工程实现的经历，不过了解工程实现中的技术要点有助于我们在自己的头脑中构建关于一致性协议更完整的知识网络。
  leader/follower/candidate
  时钟/逻辑时钟
  成员变更
  脑裂

关于Paxos的一些说法

  1. 要证明分布式容错算法的正确性通常比实现算法还困难
  2. paxos从理论到实际的巨大差距
  3. Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法，那就是Paxos，其它的算法都是残次品。

参考资料

[1]Paxos在大型系统中常见的应用场景
[2]强烈推荐:分布式系统架构经典资料
[3]wikipedia
[4]中文维基
[5]paxos 英文解释
[6]Consensus on Transaction Commit
[7]FLP不可能结果
[8]分布式系统的事务处理