一致性算法/共识机制乱谈2——Basic Paxos
前言
这是编故事理解算法的第二篇，第一篇请戳一致性算法/共识机制乱谈1——从朴素的C/S算法到2PL算法
Paxos算法被大家宣传的又难又生涩，我阅读了《Paxos Made Simple》也有同样的感觉。参考了众多网上的博文加上自己的头发，对算法流程有了比较清晰的认识，但是暂时还是无法完全明白其合理性。
4、新来的二又
分布式学报搞的越来越好了，有更多的学者们参与到论文写作中，因此编辑部不得不开始筛选稿件，学者们也开始倍感压力。
在新的一期要发表之前，审稿人们坐下来开会，表示从这期开始，我们一次接受一堆候选文章，然后只选出来一篇文章发表， （问题定义1：决议（value）只有在被 proposers 提出后才能被批准（未经批准的决议称为“提案（proposal）”）） 得保证我们最后只确认选择一篇paper。因为现在签约的作者水平可以保证，因此可以相信他们的paper水平，只不过会有很多paper发过来，我们用什么方法只要一篇呢？ （问题定义2：在一次 Paxos 算法的执行实例中，只批准(chosen)一个 value） 当然，没有签约的读者只能读我们刊登的文章，不能来投稿。 （问题定义3：learners 只能获得被批准（chosen）的 value）
于是审稿人大哥A去找水厂和小白和新签约的二又商量。
水厂觉得，这个问题颇为复杂，先一点一点去设计，然后再串起来，梳理一下流程。大家点头。
首先，写好的候选文章是肯定要邮件发给审稿人的，审稿人会收到不少的邮件，那么就得保证，只有大多数审稿人 （多数派majority） 都批准 （chosen） 的文章，才可以发表。
既然最后只能决定一篇paper，那几个审稿人在同一个时间只能认准 （接受accept） 一篇paper，不能同时手里拿着好几篇paper。如果有一篇paper被大多数审稿人都同时认准了，那这篇paper就算成功批准 （choose） ，那其余小于一半的人就需要服从大多数意见，只能批准这篇paper。 （P2：一旦一个具有 value v 的提案被批准（chosen），那么之后批准（chosen）的提案必须具有 value v）
“哦~ 也就是说，只要有一篇paper被批准了，之后审稿人接受的邮件里的paper必须还得是这篇，要是其他paper就拒收！”小白露出了大聪明的表情。 （P2a：如果一个值为v的议案被选定了，那么Acceptor接受的更大编号的议案，它的值必须也是v）
审稿人A现在非常疑惑，除了这篇文章的作者，还有别人会发一样内容的paper给我吗？那人家作者第一次都没给我发，还能真正批准以后才给我发？
“那审稿人之间又不联系，谁知道哪篇真正被批准了啊？”新来的二又疑惑。
“别急，还得继续设计，咱一步一步看。”水厂笑嘻嘻。
因为邮件发到审稿人手里是有显示收到时间的 （之后：编号更大的提案） ，所以就看到底是哪个审稿人认准了能构成超过半数的最后一个，从这个时间之后就其他人就必须认准而且批准这同一篇paper了。
咳咳，重点来了，刚刚二又说的很关键，审稿人之间又没办法马上知道是哪篇文章已经被批准了，那倒不如只要有已经被批准的文章，那所有学者都把一样的paper发邮件给审稿人，这样审稿人就能保持一致了！ （P2b：如果一个值为v的议案被选定了，那么Proposer提出的更大编号的议案，它的值必须也是v）
众人都很震惊，水厂为啥这么思路清奇，为他人着想，不按常理出牌，奇奇怪怪，为啥不是审稿人们互相联系，为啥让自己发别人的文章，自己的文章没选上还得帮别人！
为了大局，为了大局，大家都是学者，都为了学术界发展，就多担待担待！
“所以我们怎么知道谁的文章已经被选中了？”小白又开始疑惑起来。
是这样，我们发啥内容多少需要根据审稿人那边的情况来决定，随便指定半数以上的审稿人，假如这些人都还没收到邮件，那我们的邮件就随意发；要是这些审稿人但凡有一个已经收到过邮件，那就只能发这些审稿人最近收到的邮件的那篇paper。 （P2c：在所有Acceptor中，任意选取半数以上的Acceptor集合，我们称这个集合为S。Proposal新提出的议案（简称Pnew）必须符合下面两个条件之一：①如果S中所有Acceptor都没有接受过议案的话，那么Pnew的编号保证唯一性和递增即可，Pnew的值可以是任意值。②如果S中有一个或多个Acceptor曾经接受过议案的话，要先找出其中编号最大的那个议案，假设它的编号为N，值为V。那么Pnew的编号必须大于N，Pnew的值必须等于V。）
众人继续惊呆，除了刚刚那种我为啥发别人的东西的那种震惊，现在又多了一种，自己好像没啥机会发自己的东西，只能发的越早越有优势。
“我还是那个问题，你咋知道审稿人那边的情况？”二又抠了抠牙。
水厂闭了会眼睛，联想到前段时间邮件发两遍的设计，灵机一动，想到了更好的表达方式。
我刚刚说的流程大体不变，但是加入一轮确认的机制，就能解决，只不过第一轮发邮件我们需要申请一个发文权限，这个权限其实就是一个时间编号 （Proposal ID） ，比如我下午两点十五申请了权限，那我的编号就是1415，而我们第二轮的邮件需要用到这个编号。
整体流程呢，分为两轮。
第一轮，为了获得一个发文权限，要让超过半数的审稿人给予我权限才行，比如我给了ABC发过去。而他们都给我回馈了许可发文的邮件，那我的paper离被发出去就近了一步。如果并没有半数以上的人给我许可，那我只好再重新根据时间生成一个编号，继续给大部分审稿人发请求权限的邮件。
第二轮，现在假如我获得了发文权限，我就会将自己的paper发送给超过半数的审稿人。只要审稿人给我回复的邮件表示，当前最大编号没有超过我刚刚发过去的编号，那这篇文章就算真正可以发表了！
上面的情况就是最好的情况，下面来说一说这中间会出现的问题。
第一轮发编号邮件后，审稿人可能会发回来其他内容的邮件：
第一种：表示不接受你提出的编号，因为有别人的编号比你的大。 （第一阶段Promise：不再接受Proposal ID小于等于当前请求的Prepare请求）
这个时候，就需要重新根据时间，生成新的编号，为了能挤掉别人已经发过的编号大小，从而获得发文权。
第二种：表示允许你的编号，但是很可惜，已经有别人比你先把自己的文章发给我了，所以你虽然获得了发文权，但只能发别人写好的文章。
这个时候，就很痛苦了，自己得为了审稿人们的统一而不得不费一次力气发一遍人家写好的内容，但是毕竟大家都是学者，为了大局，为了大局。
第二轮发那个带paper的邮件后，审稿人的回执邮件也有可能出现这种情况：你刚刚发的这个发文请求的编号太旧了，还有比你大的，重新来过吧小伙儿~ （第二阶段的Promise：不再接受Proposal ID小于当前请求的Propose请求）
没办法，遇到这种情况只能重新去申请一个编号，要是刚刚发的是自己的paper还好说，这要是别人的，得多郁闷。
水厂喝了口水，伸了伸胳膊腿儿，继续说。
咱写文章这块的规则就说完了，接下来是审稿人这面的规则。因为咱刚刚说过，审稿人一次只保留一篇paper作为可能达成大部分人同意的备选，所以为了不忘，各位大哥们最好准备个小本本，有三个东西要记，一个是现在的备选paper （AcceptV） ，一个是当前发过来的最大的编号 （ResN） ，一个是用作最终拍板的编号 （AcceptN） 。
首先，如果自己啥paper或者编号 （ResN） 也没记，那谁发过来啥就记啥。 （P1：一个 acceptor 必须接受（accept）第一次收到的提案）
如果有人发来了仅仅是编号 （N） 请求，那就和小本上的编号 （ResN） 比一下，若小本的大，就直接拒绝这个请求 （Acceptor收到一个新的编号n，在确认n比自己之前收到的编号大时，必须做出承诺（Promise）：不再接受比n小的议案） ；若小本的小，就把小本上的改成刚发过来的 （ResN=N） ，然后看看小本上有没有记候选paper和拍板编号 （AcceptN） ，要是没有就仅仅回复邮件表示你可以给我们发paper了，编号就用你刚刚发过来的那个 （return(Pok, null, null)） ，并且文章就用你自己的；要是有的话就连着候选paper和拍板编号一起发回去 （return(Pok, AcceptN, AcceptV)） ，因为这个时候，这俩内容肯定同时记录过。
如果有人发来的邮件既有编号，又有paper （一个(N, V)提案proposal） ，就说明发过来的人在经历第二轮。如果新来的编号大于小本上的编号（N>ResN），那就更新小本上的拍板编号和备选paper （AcceptV=V，AcceptN=N） ，并且回一封邮件表明妥妥了；如果新的编号小 （N<=ResN） ，那就回复个对不起，你的编号还是太旧了。
最后呢，假如回复妥妥了的邮件数量过半了，那就这篇文章石锤了 （choose） ，就等着剩下的人进行完全部流程，就能保证所有审稿人确定的paper是同一篇了。
水厂长舒一口气，感觉自己好像一不小心想出了个能获图灵奖的好办法，脸上洋溢着笑容，毕竟解决了哥们几个发文章的问题。
在众人的惊呼声中，小白自言自语道：
假如我给ABC发了请求编号1，ABC因为第一次收到请求，肯定会反馈给我请求成功的邮件，这个时候我准备复制我的paper；与此同时水厂发了请求编号2，ABC发现这个编号更大，就更新了小本本上的记录，并给水厂发了个请求成功的邮件。这个时候我写好paper了，用编号1发了过去，但是小本本记得是2，我就被告知编号太旧了，我只能发个编号是3的请求，我刚发完，水厂就用编号2发了他的paper，又会被拒绝，这么一来，肯定没有头啊… （活锁）
水厂其实全都听到了，他一边默默赞扬着小白的反应速度，一边朗声说道：
刚刚我说的办法呢，因为还没试过，所以说不定有啥问题，先定一个规则，说不定能防止一些问题。所有人在第二轮收到了被拒的邮件后，要等待五分钟再重新从第一轮来过，要是还被拒，那就等十分钟，以此类推… （活锁的工程解决办法）
小白呆住了，觉得这可能就是大佬吧，新时代的领跑者，自己也要多下功夫多掉头发，争取早日也能相出这么精巧的办法。（Basic Paxos）
正是因为用了这个办法，审稿五人在新的一期分布式学报里共同确定了应该发表的文章，正是二又写的《Paxos Made Difficult》…
未完待续
附录
可以参考的优秀Paxos讲解
分布式系列文章——Paxos算法原理与推导
Paxos算法论文翻译
*解释Paxos
分布式理论：深入浅出Paxos算法
分布式理论之一：Paxos算法的通俗理解