海量存储之十八--一致性和高可用专题

PS 广告插播 : 淘宝java中间件团队，你值得拥有:)

----PAXOS------

好，我们回顾一下上下文，我们在上篇文章中谈到，当机器变得更多的时候Observer不能只有一个。必须有更多个Observer，但Observer多了，到底听谁的又成了问题。你一言我一语，大家都觉得自己是老大，谁也不服谁。咋办捏？

这时候就得有人站出来，说：那我们少数服从多数吧！制定一套策略，在各种情况下都能够选出一个决议不就行了！

这其实就是paxos协议的核心想法之一，我们来看一下他是怎么做到的。在这里，我不想去做那个繁琐的证明过程，那个过程如果你感兴趣，可以去看paxos made simple这篇文章，有中文，这里给出http://blog.csdn.net/sparkliang/article/details/5740882 ，数星星同学也翻译过。可以直接google.

我在这里只说结论，因为结论更容易理解一些。

我们假定有A,B,C,D,E五台机器。kv系统需要put一个数据[key=Whisper -> val=3306]到我们这5台机器上，要保证只要反馈为真，任意两台机器挂掉都不会丢失数据，并且可以保证高可用。怎么做：

1.首先,客户端随机选择一个节点，进行写入提交，这里我们随机选择了C这个节点，这时候C节点就是这次提议的发起人【也叫proposer，在老的2pc协议里也叫做coodinator】，当C收到这个提议的时候，C首先要做的事情是根据当前节点的最新全局global id，做一次自增操作，我们假定，在当时全局id,Global ID是0,所以，这个议案就被对应了一个编号，1--->[key=Whisper -> val=3306]。

【【这里有两个我们经常犯的错误，下面做一个解说：

1.global id问题，在老的论文里，Lamport没有描述这个自增id是怎么生成的，所以大家的第一个疑问一般是问id怎么生成，从我目前能够看到的所有实现里面，基本上就是选择哪一台机器，就是以那台机器当前所保持的全局id(snapshot，可能不是全局来看的最高值，但没关系，只要是自己这台机器的最高值就行了)，然后做一下自增就行了。我们后面会看到协议如何保证非全局最高值的globalID提议会被拒绝以至于不能够形成决议。

2.global id --->[key=Whisper -> val=3306] . 这也是个会让人困惑的问题，在原文中，他被表示为一个key-value的形式，比如proposal[0->value] 。这会让人自然的联想到与数据库的kv相对应，key是0，value是value。然后就会困惑，这个数据是怎么和数据库对应起来的呢？这是我当时的困惑，现在也把他列在这里。其实很简单，这里的global id对应value.global id只是对paxos协议有意义，对于数据库，其实只需要关心value里面的数据即可，也即将global id --->[key=Whisper -> val=3306]里面的value: [key=Whisper-> val=3306] 作为数据库构建映射时所需要的redoLog就行了，global id的作用只是告诉你这些数据的顺序是按照global id来排列的，其他无意义。    】】

我们回到文中，我们已经将这个新的议案标记了从C这台机器看起来最大的global id : 1--->[key=Whisper -> val=3306]。然后，他会尝试将这个信息发送给其余的A,B,D,E这几台机器。

我们来看这些机器的操作流程。 在这个过程中，Paxos将A,B,D,E叫做accepter【老的协议里没有区分，管这些都叫做参与者，cohorts】，他们的行为模式如下：

如果A,B,D,E这几台机器的globalID 小于C给出的决议的GID(1--->[key=Whisper -> val=3306])，那么就告诉C，这个决议被批准了。而如果A,B,D,E这几台机器的GlobalID 大于或等于C给出决议的GID.那么就告知C 这个决议不能够被批准。

我们假定A,B两台机器当时的Max(GID)是0 ，而D,E的Max(GID)是1.那么，A,B两台机器会反馈给C说协议被接受，这时候我们算算，C的议案有几票了？A+B+!C!，一定要算自己哦:) 。所以，这个议案有三票，5台机器的半数是3.超过法定人数，于是决议就被同意了。

我们保持这个上下文，来看看D,E这边的情况。首先，要思考的问题是，为什么D,E的Max(GID)是1呢？

其实很简单，D可能在C发起决议的同时，也发起了一个决议，我们假定这个决议是由D发起的，决议是 1--->[key=taobao ->val=1234]。既然D,E的Max(GID)是1，那么意味着E已经告知D,它同意了他的决议，但D马上会发现，A,B,C里面的任意一个都返回了D不同意。他的议案只拿到两票，没有通过，它虽然有点不爽，但也是没办法的事情啊。。

这时候C的决议已经被多数派接受，所以他需要告知所有人，我的议案1--->[key=Whisper -> val=3306]已经被接受，你们去学习吧。

这时候还有一个问题是需要被考虑的，如果在C已经得知决议已经达到法定人数，在告知所有人接受之前，C挂了，应该怎么办呢？

我之所以没有将这个放到开始的描述里，主要原因是觉得这是个独立因素，不应该影响议案被接受时候的清晰度。

为了解决这个问题，需要要求所有的accepter在接受某个人提出的议案之后，额外的记录一个信息：当前accepter接受了哪个提议者的议案。

为什么要记录这个？很简单，我们看一下上面出现这个情况时候的判断标准。

A 机器:角色-accepter 。 批准的议案 1--->[key=Whisper-> val=3306] 。提议人：C

B 机器:角色-accepter 。 批准的议案 1--->[key=Whisper-> val=3306] 。提议人：C

C机器:角色-proposer 。 挂了。。不知道他的情况。

D 机器:角色-accepter 。 批准的议案 1--->[key=taobao->val=1234] 。提议人：自己

E 机器:角色-proposer。 “提议的”议案 1--->[key=taobao->val=1234] 。提议人：D。

因为有了提议人这个记录，所以在超时后很容易可以判断，议案1--->[key=Whisper -> val=3306] 是取得了多数派的议案，因为虽然D,E两台机器也是可以达成一致的议案的。但因为有个人本身是提议者，所以可以算出这个议案是少数派。

就可以知道哪一个议案应该是被接受的了。

在这之后，提议者还需要做一件事，就是告知D,E，被决定的决议已经是什么了。即可。

这个过程在文章中叫Learn. D,E被称为Learner.

别看写的简单，这个过程也是变数最大的过程，有不少方法可以减少网络传输的量，不过不在这里讨论了。

下面，我们讨论一下我们在2pc/3pc中面临的问题，在paxos里面是怎么被解决的。

2pc最主要的问题是脑裂，死等。两个问题。

对于脑裂，paxos给出的解决方案是，少数服从多数，决议发给所有人，尽一切努力送达，总有一个决议会得到多数派肯定，所以，不在纠结于某一台机器的反馈，网络无响应？没有就没有吧，其他人有反馈就行了。

所以，如果出现了机房隔离的情况，比如A,B,C在机房1，D,E在机房2，机房1和机房2物理隔离了，那么你会发现，D,E永远也不可能提出能够得到多数派同意的提案。

所以，少数派的利益被牺牲了。。换来了多数派的可用性。我们分析过，这是唯一能够既保证数据的一致性，又尽可能提高可用性的唯一方法。

而对于死等问题，解决的方法也是一样的，对于某一台机器的无响应，完全不用去管，其他机器有相应就行了，只要能拿到多数，就不怕一小撮别有用心的反对派的反攻倒算~。

---------------------------------paxos就是这样一个协议----------

休息一下

----------------------------------------------------------------------------------------

那么Paxos有没有什么值得改进的地方？有的，很简单，你会发现，如果在一个决议提议的过程中，其他决议会被否决，否决本身意味着更多的网络io，意味着更多的冲突，这些冲突都是需要额外的开销的，代价很大很大。

为了解决类似的问题，所以才会有zoo keeper对paxos协议的改进。zk的协议叫zab协议，你可以说zab协议不是paxos,但又可以说是paxos.但将paxos和zab协议之间做直接的等同关系，无疑是【错误】的。

其实，这也是在我们的现实生活中经常能够发现的，如果每个议案都要经过议会的讨论和表决，那么这个国家的决策无疑是低效的，怎么解决这个问题呢？弄个总统就行了。zab协议就是本着这个思路来改进paxos协议的。

---------paxos 改进----zab协议讨论-----------------

zab协议把整个过程分为两个部分，第一个部分叫选总统，第二个部分叫进行决议。

选总统的过程比较特殊，这种模式，相对的给人感觉思路来源于lamport的面包房算法，这个我们后面讲。，选择的主要依据是：

1.如果有gid最大的机器，那么他是主机。

2.如果好几台主机的gid相同，那么按照序号选择最小的那个。

所以，在开始的时候，给A,B,C,D,E进行编号，0,1,2,3,4。 第一轮的时候，因为大家的Max(gid)都是0，所以自然而然按照第二个规则，选择A作为主机。

然后，所有人都知道A是主机以后，无论谁收到的请求，都直接转发给A,由A机器去做后续的分发，这个分发的过程，我们叫进行决议。

进行决议的规则就简单很多了，对其他机器进行3pc 提交，但与3pc不同的是，因为是群发议案给所有其他机器，所以一个机器无反馈对大局是没有影响的，只有当在一段时间以后，超过半数没有反馈，才是有问题的时候，这时候要做的事情是，重新选择总统。

具体过程是，A会将决议precommit给B,C,D,E。然后等待，当B,C,D,E里面的任意两个返回收到后，就可以进行doCommit().否则进行doAbort().

为什么要任意两个？原因其实也是一样的，为了防止脑裂，原则上只能大于半数，不能少于半数，因为一旦决议成立的投票数少于半数，那么就存在另立中央的可能，两个总统可不是闹着玩的。

定两个，就能够保证，任意“两台”机器挂掉，数据不丢:)，能够做到quorum。。

然后是我的个人评述，写zab协议的人否认自己的协议是paxos.变种 其实我也是有些认同的。不过，他们是针对一个问题的两种解决方法：

因为他们解决的问题的领域相同

解决网络传输无响应这个问题的方法也一样：也即不在乎一城一池的得失，尽一切努力传递给其他人，然后用少数服从多数的方式，要求网络隔离或自己挂掉的机器，在恢复可用以后，从其他主机那里学习和领会先进经验。

并且也都使用了quorum方式来防止脑裂的情况。

核心思路是类似的，但解决问题的方法完全是两套。 paxos在其他公司的实现里面也对paxos进行了这样，那样的改进。不过核心思路都是这个。

我们对paxos协议的讲解，就到这里。

也留下一个问题，zab协议，如果我们用在google 全球数据库spanner上，会不会有什么问题呢？请大家思考哈 

后记，抱歉，这篇文章一个图都没有。。我已经尽可能用简单的方式来描述paxos和他的变种协议了（当然有一个作为了问题）。如果有哪个地方不明白，也还请在后面留言吧。友情提示这篇文章不适于跳跃性阅读，想要理解，必须从第一行开始读到最后。。。。

google的工程师说，所有的一致性协议都是paxos的特例，我表示不置可否吧。。。。下一篇我们要讨论另外一系的实现，gossip模型的实现。我个人感觉：把gossip归类到paxos模型，似乎也不是很合适。gossip协议的两个主要的实现方式，是dynamo和cassandra.我们在下一篇里面进行讨论