分布式系统之Paxos选举协议
分布式系统之Paxos选举协议
本来洋洋洒洒写了一大堆关于分布式存储系统的数据分布，复制节点，负载均衡，容错机制。但通读之后，感觉毫无章法，乱七八糟，不适合阅读。特别对于技术，我觉得还是要解释清楚，所以本文主要介绍分布式系统中的两个重要协议之一，Paxos选举协议，后续的再持续进展吧。提一下，另一个是：两阶段提交协议。
之所以最后选择先写协议的原因在于整个分布式系统中，理解了两个分布式协议之后，学习其他分布式协议会变得相当容易。
Paxos选举协议
先简单介绍：Paxos协议用于多个节点之间达成一致，往往用于实现总控节点选举。是一个基于消息传递的一致性算法。
Google的Chubby，Apache的Zookeeper都是基于它的理论来实现的，Paxos还被认为是到目前为止唯一的分布式一致性算法，其它的算法都是Paxos的改进或简化。有个问题要提一下，Paxos有一个前提：没有拜占庭将军问题。就是说Paxos只有在一个可信的计算环境中才能成立，这个环境是不会被入侵所破坏的。
这里我们根据ZK来解释Paxos协议。
Paxos描述了这样一个场景，有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)。议员的总数(Senator Count)是确定的，不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。
好，现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：取消对中国的敌视。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他给所有议员发消息：1号提议，取消对中国的敌视。其他议员收到消息以后查了一下记事本，哦，当前提议编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他最新法令时，他会查看法令并告诉对方：取消对中国的敌视。
现在看冲突的解决：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1想取消对中国的敌视, S2加强对中国敌视。结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。
好，我觉得Paxos的精华就这么多内容。现在让我们来对号入座，看看在ZK Server里面Paxos是如何得以贯彻实施的。
小岛(Island)——ZK Server Cluster
议员(Senator)——ZK Server
提议(Proposal)——ZNode Change(Create/Delete/SetData…)
提议编号(PID)——Zxid(ZooKeeper Transaction Id)
正式法令——所有ZNode及其数据
貌似关键的概念都能一一对应上，但是等一下，Paxos岛上的议员应该是人人平等的吧，而ZK Server好像有一个Leader的概念。没错，其实Leader的概念也应该属于Paxos范畴的。如果议员人人平等，在某种情况下会由于提议的冲突而产生一个“活锁”（所谓活锁我的理解是大家都没有死，都在动，但是一直解决不了冲突问题）。Paxos的作者Lamport在他的文章”The Part-Time Parliament“中阐述了这个问题并给出了解决方案——在所有议员中设立一个总统，只有总统有权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。好，我们又多了一个角色：总统。
最后正式的官方语言解释一下Paxos协议：
Paxos协议用于解决多个节点之间的一致性问题。多个节点之间通过操作日志同步数据，如果只有一个节点为主节点，那么，很容易确保多个节点之间操作日志的一致性。考虑到主节点可能出现故障，系统需要选举出新的主节点。Paxos 协议正是用来实现这个需求。只要保证了多个节点之间操作日志的一致性，就能够在这些节点上构建高可用的全局服务，例如分布式锁服务，全局命名和配置服务等。为了实现高可用性，主节点往往将数据以操作日志的形式同步到备节点。如果主节点发生故障，备节点会提议自己成为主节点。这里存在的问题是网络分区的时候，可能会存在多个备节点提议( Proposer,提议者)自己成为主节点。Paxos 协议保证，即使同时存在多个proposer, 也能够保证所有节点最终达成一致，即选举出唯一的主节点。大多数情况下，系统只有一个proposer,他的提议也总是会很快地被大多数节点接受。Paxos协议执行步骤如下:
1)批准( accept): Proposer发送accept消息要求所有其他节点( acceptor, 接受者)接受某个提议值，acceptor可以接受或者拒绝。
2)确认( acknowledge):如果超过一半的acceptor接受，意味着提议值已经生效，proposer发送acknowledge消息通知所有的acceptor提议生效。当出现网络或者其他异常时，系统中可能存在多个proposer,他们各自发起不同的提议。这里的提议可以是一个修改操作，也可以是提议自己成为主节点。如果proposer第一次发起的accept请求没有被acceptor中的多数派批准(例如与其他proposer的提议冲突)，那么，需要完整地执行一轮Paxos协议。过程如下:
1)准备( prepare): Proposer首先选择一个提议序号n给其他的acceptor节点发送prepare消息。Acceptor 收到prepare消息后，如果提议的序号大于他已经回复的所有prepare消息，则acceptor将自己.上次接受的提议回复给proposer,并承诺不再回复小于n的提议。
2)批准( accept): Proposer 收到了acceptor 中的多数派对prepare的回复后，就进入批准阶段。如果在之前的prepare阶段acceptor回复了，上次接受的提议，那么，proposer选择其中序号最大的提议值发给acceptor批准;否则，proposer 生成一个新的提议值发给acceptor批准。Acceptor在不违背他之前在prepare阶段的承诺的前提下，接受这个请求。
3)确认( acknowledge):如果超过一半的acceptor接受,提议值生效。Proposer发送acknowledge消息通知所有的acceptor提议生效。Paxos协议需要考虑两个问题:正确性，即只有一一个提议值会生效;可终止性，即最后总会有一个提议值生效。Paxos 协议中要求每个生效的提议被acceptor中的多数派接受，并且每个acceptor不会接受两个不同的提议，因此可以保证正确性。Paxos 协议并不能够严格保证可终止性。但是，从Paxos协议的执行过程可以看出，只要超过一个acceptor接受了提议，proposer 很快就会发现，并重新提议其中序号最大的提议值。因此，随着协议不断运行，它会往“某个提议值被多数派接受并生效”这一最终目标靠拢。
至于两阶段提交协议，且听下回分解！！！