前言

最近开始研究起一致性算法，一入算法深似海，已经研究了长达四天的我敏锐地感觉到这个领域的错综复杂。一致性算法或者说共识算法多之又多，且似乎都多少有些关联。作为初学者，我还是决定用场景模拟的方式来逼迫自己思考记忆，因此就边学边编故事。这几篇故事算得上一些算法的通俗理解，大家看一乐呵就成，千万别较真，毕竟分布式节点的特性和工程细节肯定和生活中的场景不尽相同，只要能稍微帮助理解公式机制和一致性算法，就算达到目的了。话不多说，开始乱谈！

1、 水厂和编辑部

在最开始，研究分布式的学者少之又少，而分布式期刊《分布式学报》也只是个默默无名的小刊物，水厂作为这个领域的先锋研究者，愿意共享自己的科研精力来为这个领域提出新的理论。

他用邮件联系了分布式学报唯一的审稿人A，并直接把自己写好的第一篇paper-a1发送给A。A收到了他的paper就立即在分布式学报第一期刊登了paper-a1。（朴素的客户端/服务器算法）

过了不久，A收到了水厂的邮件，邮件表示为啥自己的paper-a2没有发表。A很震惊，表示没有收到paper-a2，后来询问了邮箱维护阿呆，才知道这条邮件发送的时候邮箱出了问题，发送失败了。（消息丢失Massage Loss）

水厂表示这样太耽误事情了，既然邮箱短时间内也没法变得完全好用毫无差错，那每次编辑收到了我的paper，给个收到的消息，我好心里有底。要是我没收到你的回复，那我就再发一遍。审稿人A很赞同。但A提议，如果我的回复消息也被邮箱吞没了，你再发给我一篇一样的paper，我糊里糊涂又给你发表出去了岂不是被读者喷，这样，每次你给我发文章的时候，都带一个标识符，我要是看标识符一样了，就不管新发过来的了，顺便再给你回一个收到。水厂虽然感觉这样有点傻，但是又没想明白傻在哪里，就同意了。（带确认Acknowledgements的客户端/服务器算法）

2、小白

paper-a2发表以后，关注学报的人越拉越多，水厂还是厉害，写的文章颇有深度，因此编辑部又招了个审稿人B。小白学者也准备加入研究分布式的行列中。编辑部是个神奇的地方，审稿人之间竟然不给联系方式，又要求审稿人给出的意见要统一…比如要是收到了两份稿件，那必须要求两个审稿人对发表顺序有个统一，否则编辑部也不知道咋办。（状态复制State Replication）

邮箱维护员阿呆也很郁闷，他发现无论发送内容和用户是不是一样的，邮件发送的速度每次都不一样。（可变消息延迟Variable Message Delay）

因为这个原因，就算水厂和小白同时发送自己的paper邮件给AB，AB收到邮件的顺序也可能不一样，而编辑部规定是谁先发过来邮件，就先发表谁的paper。阿呆冥思苦想，想到了个好办法，每次收到大家的邮件后，不马上转发，而是收进一台单独的服务器，一条一条发，确定已经发给了一个收件人，才继续转发下一条。（主——从复制Master-Slave Replication）

水厂听到阿呆这么说，立马表示，如果你的服务器坏了咋办 （Single Point of Failure）

阿呆蒙了，表现出和他的名字一样的表情。这时，新来的学者小白发表了他的看法，“我们要是保证一段时间内只有一个人向审稿人发邮件，岂不就不难为审稿人了，咱俩顺序肯定一样”，水厂虽然心里想，你这是想后来居上先我之前发文章啊，嘴上却说，不错的想法，说说看，咱们怎么实施呢？（互斥Mutual Exclusion&各自加锁Respectively Locking）

小白不紧不慢地说：“我们向两个审稿人发邮件，获取一个发稿权，如果两个审稿人都回复了邮件给予发稿权，那就可以直接给他们发paper，要是一小时内只有一个人或没人回，那就给那个给自己发稿权的人回一封邮件，放弃审稿权，那就再等一小时后重新请求发稿权。”“那审稿人怎么回复邮件呢？”水厂问道。“很简单，谁先发来邮件，就给谁审稿权，最后就是谁的paper先发来，就先发表谁的paper呗”。（两阶段锁Two-Phase locking）

水厂想了一会，说“那照你这么说，我给A发邮件，你给B发邮件，那AB的审稿权就分散给咱俩了，咱俩就得等两小时，下此要是还是这样操作，又得等两小时，这样下去啥时候到头？”（死锁）

3、水厂的点子

“我倒有个想法，不过这需要两个审稿人能互相发邮件联系。”水厂说。

“？？要是能联系还有咱这么绞尽脑汁吗？”小白感觉自己被耍了一样。

“那可说不准，你说要是能联系你准备咋办？”

“那就咱俩都发paper过去，AB都收到以后，谁先收到谁就给对方发个信息，说说自己的排序方案呗。”

“那要是A给B发消息，邮件丢了咋办？”

“那就等一段时间，没回信就再发一遍。”

“那…”A没等小白说话，就抢先说“我怎么感觉问题又回到了只有我和水厂的那段时光了，要是过段时间编辑部又扩招，招了十个审稿人，还能这么搞吗？”小白顿时没话说了。

“咋样，听听我的意见吧！”水厂笑道“咱假设编辑部有五个审稿人吧，我这方法一样好使。这五个人互相都能联系。”“所以呢？”

“首先，五个审稿人要定一个老大，比如老资格审稿人A吧 （事务协调者TC）。咱俩要发的文章直接发给他，他按照接收的顺序定下来咱俩谁先发表谁后发表。但是因为编辑部的规定，必须五个审稿人上报的顺序是一样的，必须保持一致才行。”

“那就A给BCDE直接发个邮件呗，多简单的事情！”小白不屑。

“因为五个审稿人收到消息后就会给编辑部汇报，假如A的邮件有一个没发成功，那岂不是就会有不知道咋回事的审稿人，那编辑部还不得炒了他，编辑部不允许五个人的意见不统一。所以就得这样，A先给大家发一个调查邮件 （prepare），看看大家都在不在线，自己那边方不方便联系编辑部，这样就会有<方便 （Yes） >和<不方便 （No） >两种回复。要是全都回复了方便，那A就把发表顺序 （提交commit） 挨个发给大家，然后自己也直接提交给编辑部，其余大伙收到邮件后也都跟编辑部汇报；要是但凡有一个人发送了不方便，那A就给大家再发个邮件，表示暂时不公布顺序 （废止aboort） ，因为有人现在有事。”

“不是，你这方案听起来也就那回事吧，很厉害吗？”小白白了下眼。“那你看看这中间要是出现了啥错误，这个方案能不能很好的解决，你随便提！”

“行！我问你，A发完了询问的邮件后，要是有人没回复咋办，或者回复的邮件也丢了咋办？”“简单，A会有个等待的限度，超时了就直接给大家发那封废止邮件。”

“行！要是B回复了方便，但是却一直没收到paper顺序的邮件咋办？”“简单！这种情况有两种情况，一种是A发的那个顺序邮件丢了，一种是A发的废止邮件丢了，B没法判断到底是哪种情况，这个时候B要是等待了很长时间，就可以自己行动起来了。”

“咋？”

“B给其他人，比如E，发个邮件问问呗 （终止协议Termination Protocol） 。要是E已经收到了顺序，就发给B，因为大家的顺序都一样；要是E说还没回复方不方便呢，就说明B还得再等等；要是E说我不方便，那B就不用等A了，直接干别的事；要是E说我刚回复方便呢，但是也没收到A的回信，这情况就麻烦了。”

水厂喝了口水继续说“这时，或许A已经给大家发了顺序，但是这些邮件都丢了，A可能不知道，自己给编辑部发了结果；另一种情况，A一直没等到咱们的回复邮件，等超时了，就放弃了这个时间段的协调，去逛街了！最后的情况，就需要给A发一封邮件问问咋回事，我和E都没收到啥消息。这时A就给BE回复一下到底是顺序表，还是有人不方便，过段时间再说。”

小白挠挠头，觉得这方法也就这样吧，但是也确实能避免不少问题，跟各位审稿人说了这个方案后，就用了这个方案成功刊登了水厂的第三篇paper-a3和小白的处女作paper-b1。（两阶段提交协议Two-Phase Commit）

未完待续

附录

可参考博文资料：
正确理解二阶段提交（Two-Phase Commit）