最近看了paxos算法。从发明者本人开始，到网上各种介绍算法的文章，都是在通过各种例子说明这个算法。但我觉得，似乎大部分的例子在让人理解的时候都会引入歧义。比如发明者本人以一个虚构的希腊城邦为例，我看了例子后很长时间都没有搞明白一点：当提案通过之后，是不是还能够继续修订提案？比如这次会议决定了拦路抢劫判10年，通过之后是不是可以再重新提案修改为判20年？当我最终弄明白这个算法之后，自己想了下面一个例子。我认为，我这个例子可以避免误解，让人直接明白paxos算法究竟要解决的是什么问题。
假设这样的一个场景：你和另外四个人被一个性格古怪的恐怖分子劫持了，他要求和你们五个人做一个游戏。游戏规则是，他会把你们五个人分别放进五个房间，每个房间都有一张桌子和一个窗户。你们互相之间都看不到其他人的房间或窗户。桌子上放着三样东西，这三样东西各不相同，但每人桌子上的东西是相同的。比如，你的桌子上是铅笔，橡皮，绳子，其他人的桌子上也都是铅笔，橡皮，绳子。但摆放的位置可能不同。你们每人需要从桌子上选择一件东西扔到窗户外面。如果有三个或更多的人将同样的东西扔到了窗户外面，就算你们赢了，你们每人会得到1千万元的奖励，如果没有三个人扔出同样的东西，比如两个人扔了橡皮，两个人仍了铅笔，一个人扔了绳子，那么你们就输了。输了就全都被枪毙。在游戏分出输赢之前，你们五个人会被一直关在屋子里，不许出来，你们有吃有喝，不会饿死。
接下来是关键的条件：你们每人都可以拿着一部手机，用来互相通信。这个手机的功能被做了如下限制：不能打电话，只能发短信，且每个人只能发送短信给其他四个人。手机通讯录上记录了其他四个人的联系方式。但这个手机短信的收发功能不大可靠，你发送的一条短信，可能丢失，最终没有人收到，也可能延迟很久才被人收到。而且，还有一点不利的条件，你们中最多可能有两个人完全无法和别人联络，也就是说，可能有0到2个人，发出去的短信别人永远无法接到，也永远受不到别人的短信。
前提条件已经讲完了，实际上问题就是，你们五个人进入屋子后，要通过手机短信协商出把哪件东西扔出窗外，并且这个手机短信的传输信道很不靠谱，可能会丢失短信，或者让短信延迟很长时间才会收到。甚至，可能会有１到２部手机从一开始或者从某个时间点开始，永远都联系不上其他三部手机。现在，在分别被关进屋子之前，你们五个人被聚集在一起，可以一起商量一个办法，商量进入屋子后，如何才能让至少三个人把同一件东西扔出窗外。
我尝试分别问了两个人，这两个人的第一反应是相似的，都提出了这样的办法：选定一个人，由这个人发短信给其他人，告诉其他人该扔哪件东西。我反驳说：按照前面提到的条件，最多可能有两个人可其他人完全无法通讯，如果恰好是开始选出的人，岂不是永远都无法做出决定了？这两个人接下来的反应也大同小异：那就给五个人编号，分别为1，2，3，4，5，如果1发出去的消息别人收不到，那就由2发，如果2发出去的别人还收不到，那就由3发。我会反问：由于消息可能会延迟也可能会丢失，假设1和2的消息都延误了很久，3开始发消息了，结果最终只有5收到了1的消息，1发给其他人的消息都丢失了，4收到了3的消息，3发给其他人的消息也都丢失了。而2没有收到任何人的消息，2发出去的消息也都丢失了。这时1，5扔出去了一样的东西，3，4扔出去了一样的东西，2自己扔出去了一件东西，结果没有3个人扔一样的东西，你们就输了。所以，这样的思路是行不通的。
Paxos算法是一个可行的思路。按照paxos算法，我们可以为每个人都定下这样的规则：
进入屋子之后，随机等待一段时间，开始和别人联系，联系的内容就是提议将某件物品扔出窗外。提议分两步进行，第一步是发送短信联系5个人中的任意3个人（可以包括自己），短信包含如下内容：
我是xxx，我想进行提议，本次提议的序列号SN
我们把这条短信叫做“短信1”
注意，这条短信中不包括提议仍哪件东西的具体内容，只表明你想进行提议，SN是一个全局唯一的序列号，并且单调递增。这里我们可以先假设SN就是时间戳，每个人打算提议时就记下当前的时间，把时间戳发出去。当然，题目中并没有说关在屋子里的人可以看时间，而且在两个人同时进行提议的时候，时间戳也可能相同，不能保证全局唯一性。在讲完paxos算法后，我会说明如何在不借助任何外部工具的情况下构建出这样一个全局唯一并且单调递增的SN号。但目前，为了简单起见，我们先假设SN号就是时间戳。
大家都是随机等待一段时间开始发“短信1”的，随机的目的是为了让大家把发短信的时间岔开。但有可能两个人在很接近的时间内发送了“短信１”给同一个人，这样有人就接连收到了两条“短信１”，我们给接收到短信的人指定这样一个规则：他如果同时收到了多条“短信１”，就比较SN号，只回复SN号最大的那个人发来的短信，其他SN号比较小的，就都不理会。
对于回复“短信１”的人，如果他之前还没同意过任何提议，则回复内容如下：
我是xxx，我收到序列号为SN的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
如果回复“短信１”的人之前同意过其他人的提议（我们稍候会介绍如何同意其他人的提议），那么他选出所有他同意的提议里面，SN号最大的那个提议，并回复内容如下：
我是xxx，我收到序列号为SN的提议请求，我同意你进行提议，并且，我之前同意过的最新的提议为"扔出xx"，该提议的序列号为SN1。
对于发送“短信１”的人，他等待一段固定的时间，比如说十分钟，如果在十分中内没有收到３个人对“短信１”的回复，比如只收到了２个人的回复，或者也可能一个回复都没有收到，那么他就再随机等待一段时间，然后再尝试找３个人发“短信１”，每次找的３个人最好都有变化，别总是找固定的３个人，因为如一开始的假设，可能有最多两个人和其他人是完全失联的，如果总找完全失联的人，就可能永远集不齐３个回复。
当某个人在某次发了“短信１”之后，如果收到了３个人对“短信１”的回复，那么他开始发送“短信２”。“短信2”的内容视他收到的对“短信1”的回复而定。假如他收到的3个对“短信1”的回复都说“我之前没有同意过任何提议”，那么，他就任选一个桌子上的物品，比如说橡皮，然后发送“短信２”的内容如下：
我提议把橡皮扔出窗外，我的序列号是SN。
这个SN依然是发送短信1时使用的序列号，不是新生成一个序列号。
如果他收到的三个对短信1的回复中有一个或多个人回复说“我之前同意过的最新的提议为"扔出xx"，该提议的序列号为SN1”，那么他就从这些回复中选出序列号最大的那个提议，看看那个提议是建议扔出什么东西，然后他也提议仍同样的东西。比如，他看到3条对“短信1”的回复里面，序列号最大的提议是扔出铅笔，那么他就发送“短信2”的内容如下：
我提议把铅笔扔出窗外，我的序列号是SN。
注意，扔出铅笔是对“短信1”的回复里面序列号最大的那个提议的内容，但序列号SN依然是他自己发出“短信1”时确定的序列号。
他把“短信2”发送给任意3个人，可以和之前发给“短信1”的三个人相同，也可以不相同。然后他等待其他人的回复，如果他收到了3条回复，并且内容如下：
同意你的序列号为SN的提议
那么他就把他提议的东西扔出窗外。如果等了一段固定的时间，没有集齐3个回复，那么他就再随机等待一段时间，然后重新从“短信1”开始发送。
接下来我们说收到“短信2”的人如何回应。如果一个人收到了“短信2”，他首先看看有没有收到序列号更大的"短信1"或者“短信2”，如果有的话，就回复序列号最大的那条“短信1”或者“短信2”，忽略这条最新收到的“短信2”。注意，由于发送信息可能会有延迟，最新收到的短信的序列号不一定是最大的，因此，他可能会忽略最新收到的短信。如果这个人发现他收到的这条“短信2”是他所有收到的短信里面序列号最大的（或者并列最大的），那么他就回复说：
同意你的序列号为SN的的提议
关于并列最大的序列号，我们说序列号全局唯一，并且单调递增，但同一个序列号即要被用于”短信１“也要被用于”短信２“，可能这个人收到过序列号为SN1的“短信１”，然后他又收到了序列号为SN1的“短信２”，因此，可能出现并列最大的序列号。
当收到“短信2”的人做出了这样的回复之后，他就记录下这是他最新同意的提议，如果接下来他又收到序列号更新的“短信1”的时候，他就回复说他同意了这个提议。当他回复了“短信2”之后，他可能又收到一个序列号为SN1的“短信2”，这个SN1比SN更大，这时，他也会做如下回复：
同意你的序列号为SN1的的提议
同时，他也会记录下，SN1以及其对应的提议是他同意过的最新的提议，再收到“短信1”的时候，他会把SN1以及SN1对应的提议返回给发送“短信1”的人。
每个人都按照上述规则发送“短信1”和“短信2”，并且处理别人发来的“短信1”和“短信2”。最终，这5个人会达成一致，把同一件东西扔出窗外，或者，假设有1或2个人处于完全失联的状态的话，其余的人会达成一致，把同一件东西扔出窗外。
算法的正确性有严格的证明，可以在网上搜到。我写这篇文章的目的是方便大家理解paxos算法，对于算法的正确性，我就不作证明了。下面我们通过具体的例子来感受一下算法的运行：
按照本文开头假设的场景，有A,B,C,D,E五个人，他们被分别关进了5个屋子，每个屋子里面的桌子上，都摆放着铅笔，橡皮，绳子。现在，他们要通过可能会丢包/延迟的手机短信，对把哪个东西扔出窗外这个问题达成一致。
进入屋子之后，过了一段时间，A决定发送“短信1”了，Ａ编辑如下短信内容：
我是A，我想进行提议，本次提议的时间戳是02:15
如前所述，我们暂时用时间戳代替序列号，并假设不会有两个人使用相同的时间戳。
A决定把“短信１”发给A,B,C三个人。A发给自己就不用真的发送了，他马上就知道了自己发送的内容。然后A,B,C三个人按照前面所述的规则对“短信１”做出回应。A刚刚发出“短信１”，E也决定发送“短信１”，E编辑如下短信内容：
我是E，我想进行提议，本次提议的时间戳是02:20
然后，E决定把他的"短信１"发送给C,D,E三个人。我们假设这些短信都在短时间内被接收到了。于是A,B,C收到了A的“短信１”，C,D,E收到了E的“短信１”，A和B马上给A做出回应：
我收到时间戳为02:15的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
D和E也马上对E做出回应：
我收到时间戳为02:20的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
C会收到A和E两个人的短信１，C具体怎么做，取决于收到短信的顺序。
情况１：Ｃ先收到了E的“短信１”或者C正在回复A的短信１但还没发送的时候收到了E的“短信１”，C都会决定不再理会A，只对E回复：
我收到时间戳为02:20的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
在这种情况下，E会收到C,D,E三个人对“短信１”的回复，并开始发送“短信２”，而A不会收到３分对“短信１”的回复，于是等待一段时间后，A会发送一个时间戳更新的“短信１”。Ａ可能只等待了一分钟，就迫不及待的发送了一个时间戳为02:16的“短信１”，如果C收到了的话，依然是不与理会，直到A发送的“短信１”的时间戳大于02:20，C才会理会A。
情况２：C先收到了A的“短信１”，并且，直到C回复A之前，都没有收到E的短信，C会回复A：
我收到时间戳为02:15的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
然后，等C收到了E的“短信１”，C也会回复E：
我收到时间戳为02:20的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
虽然C对A和E都进行了回复，但C回复的最新的时间戳是02:20，因此当C再收到A发来的时间戳为02:15的“短信２”的时候，C不会理会A的“短信２”。由于D和E回复了E的“短信１”，他们会记住他们接收的最新的时间戳是02:20，因此D和E收到A的时间戳为02:15的“短信２”时，也不会理会。C,D,E都不会理会A的“短信２”，所以A不可能收齐三个人对“短信２”的回复，因此，A的时间戳为02:15的提议，是不会得到通过的，A最终会由于很长时间都没有收齐3个对“短信２”的回复，而使用新的时间戳重新发送“短信１”
我们看，无论是情况１还是情况２，A的时间戳为02:15的提议都不会得到通过。而假如一切顺利的话，E收到３个对“短信１”的回复后，编辑“短信２”如下：
我提议把铅笔扔出窗外，我的时间戳是02:20。
然后，E决定把“短信２”发送给A,B,C。A和B在接收到E的“短信２”之前，接收到的最新的时间戳是A发出来的02:15，因此，A和B会发现他们收到的这条来自E的“短信２”的时间戳比他们以前收到的都新，按照前面约定好的规则，A和B会回复E：
同意你的时间戳为02:20的提议
并且，A和B都会记下：我最新同意的是时间戳为02:20的提议，提议的内容是仍铅笔。
对于C来说，他收到最大时间戳是02:20的“短信１”，这次他又收到了时间戳为02:20的“短信２”，按照前面规定的规则，出现并列最大的序列号时，需要对短信２做出回应，于是C回复E：
同意你的时间戳为02:20的提议
并且C会纪录下：我最新同意的是时间戳为02:20的提议，提议的内容是仍铅笔。
当A,B,C都决定同意E发出来的“短信２”之后，仍铅笔这个决定就已经被确定下来了。尽管A,B,C,D,E五个人还没有一个人知道这件事，但仍铅笔这件事已经确定了。比如，在A,B,C都回复C的“短信２”之后，B的回复由于通讯链路故障丢失了，E没有受到B的回复。这样，E就只收到了２个对“短信２”的回复。E会过一段时间重新发送“短信１”。
我们假设E在收到了两个A和C的两个“短信２”之后，还在等待B的回复。这时，C又发起了新一轮的提议，C编辑“短信１”如下：
我是C，我想进行提议，本次提议的时间戳是02:30
C决定把"短信１"发送给A,D,E，
按照规则，A会回复Ｃ：
我收到时间戳为02:30的提议请求，我同意你进行提议，并且，我之前同意过的最新的提议为"扔出铅笔"，该提议的时间戳为02:20。
D和E都会回复E：
我收到时间戳为02:30的提议请求，我同意你进行提议，并且，我之前没有同意过任何提议。
C收到了A,D,E对“短信１”的回复之后，发现回复中提到的最新的提议是扔出铅笔，于是，C编辑“短信２”如下：
我提议把铅笔扔出窗外，我的时间戳是02:３0。
C把“短信２”发送给任意３个人，比如A,B,D，假设运气好的话，他会收到３个这样的回复：
同意你的时间戳为02:３0的提议
C自己知道他同意过的02:30的提议是扔出铅笔，于是C安心的把铅笔扔出窗外。为了加快达成一致的速度，C可以更新记录下：
我最新同意的是时间戳为02:３0的提议，提议的内容是仍铅笔。
C也可以不更新上面这条记录，依然保持自己的记录为：
我最新同意的是时间戳为02:20的提议，提议的内容是仍铅笔。
回顾一下前面的流程，02:20这个记录内容是C回复E的短信２时记录下的。
C扔出去铅笔之后，就不再发送“短信１”或是“短信２”了，但会按照规则并依据自己收到的时间戳回复别人的“短信１”和“短信２”。最终，除去永远失联的０到２个人之外，其他人都会把铅笔扔出窗外。
接下来我们简单说说序列号的问题，paxos要求每个节点都能够生成全局唯一并且单调递增的序列号，当我一开始看paxos算法的时候，就在思考这个序列号如何生成。首先我想到的是时间戳，但两个不同节点上的时间戳可能是相同的，解决办法是给每个节点分配一个唯一的编号，比如上面的例子中，A,B,C,D,E五个人的编号分别为0,1,2,3,4，每个人想进行提案的时候，都获取一个时间戳，把这个时间戳转换为epoch（从1970年１月１日到现在的毫秒数），用这个epoch作为序列号的最高位，把自己的编号作为序列号的最低位。这样由于时间戳始终在不停的增长，序列号一定是单调递增的，当两个人在同一时间获取序列号时，由于每个人的编号不同，最低位不会相同，因此可以两个人的序列号不会一样。注意，我们要让epoch作为高位，每个人的编号作为低位，反过来是不行的。假如用每个人的编号作为高位，而epoch作为低位的话，一个人的序列号就永远无法超过另一个人的序列号了，而每个节点只要收到了一个大的序列号，就不会再处理小序列号的请求了，因此这会造成算法永远无法收敛。
进一步的，我们还可以得到一个更紧凑的序列号，假设一共有n个节点（在我们的例子中，n=5），每个节点的编号为i，i是从0到n-1的整数，epoch为时间戳。那么可以用如下公式得到序列号：
sn = epoch * n + i
比如n等于５的时候，如果按照一开始提出的序列号方案，sn号的低位只能用到了0,1,2,3,4，sn号永远不可能为5,6,7,8,9，这对于sn号的取值空间来说也是一种浪费，后面提出的这个公式可以让sn号的取值空间没有浪费。想到这里，我觉得我已经解决序列号的问题了，于是不再考虑生成序列号的问题。直到我无意中发现，google在Chubby的论文中提出了一个更简洁的方案：
系统中的每个节点都维护一个计数器，从０开始计数，每当这个节点打算新提出一个提议的时候，就把这个计数器加１，系统的总节点个数是n，每个节点都有一个唯一编号，从０到n-1，假设当前计数器的值为m，那么序列号为：
sn = m * n + i
对比我自己想的那个公式，把epoch换成了m，不需要用真实的时间了，只要每个节点维护一个单调递增的计数器就行。至此，序列号的问题算是完美的解决了。
说句题外话，raft算法所用的虚拟时钟相对于paxos lease算法的真实timer，看起来和chubby论文对我设想的序列号公式的简化非常神似。
基本的paxos算法 + paxos lease + multi paxos可以实现一个分布式的状态机系统。近些年提出来的raft算法号称可以实现paxos同样的功能，但更好理解。在我看来，raft本质和paxos是相通的，我倾向于认为raft就是进化到极致的paxos。
