Paxos算法【下】
队长的逻辑比较简单。
在申请阶段，队长只会选择与最新发申请短信的驴友沟通，队长知道自己接收到最新短信的时间，对于更老的短信，队长不会搭理；队长同意沟通了的话，会把自己决定的旅游地（或者还没决定这一信息）发给驴友。
在沟通阶段，驴友C会把自己希望的旅游地发过来（同时会附加上自己申请短信的时间，比如3分钟前），所以队长要检查一下，如果这个时间（3分钟前）确实是当前自己最新接收到申请短信的时间（说明这段时间没有驴友要跟自己沟通），那么，队长就同意驴友C的这个旅游地了（比如昆明，哪怕自己1个小时前已经做过去三亚的决定，谁让C更新呢，于是更新为昆明）；如果不是最新的，说明这3分钟内又有其它驴友D跟自己申请了，因为自己是个喜新厌旧的家伙，同意与D沟通了，所以驴友C的决定自己不会同意，等着D一会儿要发过来的决定吧。
?
Paxos的基本思想大致就是上面的过程。可以看出，其实驴友的策略才是Paxos的关键。让我们来跟理论对应一下。
Paxos主要用于保证分布式存储中副本（或者状态）的一致性。副本要保持一致，那么，所有副本的更新序列就要保持一致。因为数据的增删改查操作一般都存在多个客户端并发操作，到底哪个客户端先做，哪个客户端后做，这就是更新顺序。如果不是分布式，那么可以利用加锁的方法，谁先申请到锁，谁就先操作。但是在分布式条件下，存在多个副本，如果依赖申请锁+副本同步更新完毕再释放锁，那么需要有分配锁的这么一个节点（如果是多个锁分配节点，那么又出现分布式锁管理的需求，把锁给哪一个客户端又成为一个难点），这个节点又成为单点，岂不是可靠性不行了，失去了分布式多副本的意义，同时性能也很差，另外，还会出现死锁等情况。
所以，说来说去，只有解决分布式条件下的一致性问题，似乎才能解决本质问题。
如上面的例子，Paxos解决这一问题利用的是选举，少数服从多数的思想，只要2N+1个节点中，有N个以上同意了某个决定，则认为系统达到了一致，并且按照Paxos原则，最终理论上也达到了一致，不会再改变。这样的话，客户端不必与所有服务器通信，选择与大部分通信即可；也无需服务器都全部处于工作状态，有一些服务器挂掉，只有保证半数以上存活着，整个过程也能持续下去，容错性相当好。因此，以前看有的博客说在部署ZooKeeper这种服务的时候，需要奇数台机器，这种说法当然有一定来源背景，比如如果是5台，那么任意客户端与任意其中3台达成一致就相当于投票结束，不过6台有何不可？只是此时需要与4台以上达成一致。
Paxos中的Acceptor就相当于上面的队长，Proposer就相当于上面的驴友，epoch编号就相当于例子中申请短信的发送时间。关于Paxos的正式描述已经很多了，这里就不复述了，关于Paxos正确性的证明，因为比较复杂，以后有时间再分析。另外，Paxos最消耗时间的地方就在于需要半数以上同意沟通了才能进入第二步，试想一下，一开始，所有驴友就给队长狂发短信，每个队长收到的最新短信的是不同驴友，这样，就难以达到半数以上都同意与某个驴友沟通的状态，为了减小这个时间，Paxos还有FastPaxos的改进等等，有空再分析。
倒是有一些问题可以思考一下：在Paxos之前，或者说除了Chubby，ZooKeeper这些系统，其它分布式系统同样面临这样的一致性问题，比如HDFS、分布式数据库、Amazon的Dynamo等等，解决思路又不同，有空再进行对比分析。
最后谈谈一致性这个名词。
关于Paxos说的一致性，个人理解是指冗余副本（或状态等，但都是因为存在冗余）的一致性。这与关系型数据库中ACID的一致性说的不是一个东西。在关系数据库里，可以连副本都没有，何谈副本的一致性？按照经典定义，ACID中的C指的是在一个事务中，事务执行的结果必须是使数据库从一个一致性状态变到另一个一致性状态。那么，什么又是一致性状态呢，这跟业务约束有关系，比如经典的转账事务，事务处理完毕后，不能出现一个账户钱被扣了，另一个账户的钱没有增加的情况，如果两者加起来的钱还是等于转账前的钱，那么就是一致性状态。
从很多博文来看，对这两种一致性往往混淆起来。另外，CAP原则里面所说的一致性，个人认为是指副本一致性，与Paxos里面的一致性接近。都是处理“因为冗余数据的存在而需要保证多个副本保持一致”的问题，NoSQL放弃的强一致性也是指副本一致性，最终一致性也是指副本达到完全相同存在一定延时。
当然，如果数据库本身是分布式的，且存在冗余副本，则除了解决事务在业务逻辑上的一致性问题外，同时需要解决副本一致性问题，此时可以利用Paxos协议。但解决了副本一致性问题，还不能完全解决业务逻辑一致性；如果是分布式数据库，但并不存在副本的情况，事务的一致性需要根据业务约束进行设计。
另外，谈到Paxos时，还会涉及到拜占庭将军问题，它指的是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。Paxos本身就是利用消息传递方式解决一致性问题的，所以它的假定是信道必须可靠，这里的可靠，主要指消息不会被篡改。消息丢失是允许的。
|
|
