知行学社 paxos_fast paxos_知行学社

四:分布式事务一致性协议paxos通俗理解

转载地址：

维基的简介：Paxos算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。

Paxos算法目前在Google的Chubby、MegaStore、 Spanner等系统中得到了应用，Hadoop中的ZooKeeper也使用了Paxos算法，在上面的各个系统中，使用的算法与Lamport提出的 原始Paxos并不完全一样，这个以后再慢慢分析。本博文的目的是，如何让一个小白在半个小时之内理解Paxos算法的思想。小白可能对数学不感兴趣，对 分布式的复杂理论不熟悉，只是一个入门级程序员。之所以想写这篇博文，是因为自己看了网上很多介绍Paxos算法的文章，以及博客，包括Lamport的论文，感觉还是难以理解，大多过于复杂，本人一直认为，复杂高深的理论背后一定基于一些通用的规律，而这些通用的规律在生活中其实我们早就遇到过，甚至用过。所以，我们先忽略Paxos算法本身，从生活中的小事开始谈起。

假如有一群驴友要决定中秋节去旅游，这群驴友分布在全国各地，假定一共25个 人，分别在不同的省，要决定到底去、昆明、三亚等等哪个地点（会合时间中秋节已经定了，此时需要决定旅游地）。最直接的方式当然就是建一个QQ群，大 家都在里面投票，按照少数服从多数的原则。这种方式类似于“共享内存”实现的一致性，实现起来简单，但Paxos算法不是这种场景，因为Paxos算法认 为这种方式有一个很大的问题，就是QQ服务器挂掉怎么办？Paxos的原则是容错性一定要很强。所以，Paxos的场景类似于这25个人相互之间只能发短 信，需要解决的核心问题是，哪怕任意的一部分人（Paxos的目的其实是少于半数的人）“失联”了，其它人也能够在会合地点上达成一致。好了，怎么设计 呢？

这25个人找了另外的5个人（当然这5个人可以从25个人中选，这里为了描述方 便，就单拿出另外5个人），比如北京、上海、广州、深圳、成都的5个人，25个人都给他们发短信，告诉自己倾向的旅游地。这5个人相互之间可以并不通信， 只接受25个人发过来的短信。这25个人我们称为驴友，那5个人称为队长。

先来看驴友的逻辑。驴友可以给任意5个队长都发短信，发短信的过程分为两个步骤：

第一步（申请阶段）：询问5个队长，试图与队长沟通旅游地。因为每个队长一直会收 到不同驴友的短信，不能跟多个驴友一起沟通，在任何时刻只能跟一个驴友沟通，按照什么原则才能做到公平公正公开呢？这些短信都带有发送时间，队长采用的原 则是同意与短信发送时间最新的驴友沟通，如果出现了更新的短信，则与短信更 新的驴友沟通。总之，作为一个有话语权的人，只有时刻保持倾听最新的呼声，才能做出最明智的选择。在驴友发出短信后，等着队长。某些队长可能会说，你这条 短信太老了，我不与你沟通；有些队长则可能返回说，你的短信是我收到的最新的，我同意跟你沟通。对于后面这些队长，还得返回自己决定的旅游地。关于队长是 怎么决定旅游地的，后面再说。

对于驴友来说，第一步必须至少有半数以上队长都同意沟通了，才能进入下一步。否则，你连沟通的资格都没有，一直在那儿狂发吧。你发的短信更新，你获得沟通权的可能性才更大。。。。。。

因为至少有半数以上队长（也就是3个队长以上）同意，你才能与队长们进行实质性的沟通，也就是进入第二步；而队长在任何时候只能跟1个驴友沟通，所以，在任何时候，不可能出现两个驴友都达到了这个状态。。。当然，你可以通过狂发短信把沟通权抢了。。。。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-29392-1.html