冰激凌和分布式系统

本文是翻译,版权归原作者所有


我们能够处理好冰激凌的总量吗?

在我小时候,我真的喜欢吃冰激凌。它现在还是不错,只是回到那个时候我对它多少有些狂热。我父母知道脂肪和糖的美味混合物最好偶尔食用,因此要小心地限制量。当然,我找到了系统中的方法。首先,我找到妈妈,问问是不是可以吃冰激凌了,她将给出答案。如果她不同意,我再去找爸爸问同样的问题。这个策略增加了获得同意的机会,因为我父母的决定不是一致的。少数情况下,我甚至能吃到妈妈同意的冰激凌,然后找爸爸尝试图吃到第二碗。

这种诡计持续了一段时间后,我父母明白过来了。他们决定有必要给我提供一致的答案,唯一的方式就是在我询问吃冰激凌时,他们每次都要彼此沟通一下。他们的协调方法非常有效。它确保了一致性的答案,只不过让我等待问题答案的时间稍微长了些。

当我父母上班时,这种方法就不管用了。做为一个孩子,我能够找到好借口在任何时候与其中一个家长说话,但是他们的工作会妨碍他们彼此沟通。再一次,我可以把这种情况用在了丰富的、甜甜的、奶油优势上。由于我父母无法交流,我能够强迫得到不一致的决定。我父母让他们做出是否购买冰激凌的一致性决定,却不能彼此沟通,这是他们的失误?

假定网络由至少两个节点组成,这样网络可以被分为两个不相交的、非空集合:{G1,G2}。证实的基本思想就是假定G1和G2之间的所有信息都丢失了。如果G1发生了一个写操作,随后G2发生了一个读操作,那么读操作不能返回之前写操作的结果。

假定我父母没有手表,他们做出的决定只能根据他们收到的信息和内部状态,Glibert和Lynch证实了他们通常不能做出一致性的决定。这是关于写和读的通常结果。他们在某些特定情况下可以做得更好吗?

灵活使用时钟

在时间上,我父母的冰激凌策略是我一周得到一碗。他们每天上班之前商量一下,在我还没有得到每周配额的时候,决定在接下来的八个小时内,只有他们其中一个可以发出冰激凌的决定。如果轮到我妈妈负责,我给爸爸打电话要决定,他就告诉我,他不能给我决定。只要我能够联系到妈妈,我就能得到一致性的答案。如果我不能联系到妈妈,我就运气不佳了。尽管如此,补救措施就是如果妈妈加班,爸爸会注意到超过八个小时了,然后做出决定。

很快,我这个灵巧的小家伙,就意识到爸爸的手表比妈妈的表走得快些。当他到家时,我就去找爸爸要一个香草味儿的。他看看他的手表,发现八个小时过了,就认为妈妈已经失去了做决定的授权。在检查了冰箱里的碗仍然是空着的,以确保妈妈没有在白天决定,那么他就让我吃。我将狼吞虎咽地吃完,然后给我妈妈打电话。她的手表告诉她,还没有过八个小时,她就给我第二碗了。我打败了这个系统!

[客户的租约时间]被限额E因为始终偏移缩短了。至少,租约的正确功能只需要始终有一个已知的、有界限的偏移。

如果我父母读过Gray和Sheraton,他们将知道如何修复他们的租约协议。我妈妈和爸爸将不得不测出两个手表速率之间的偏差,在假定我妈妈不再拥有租约之前,要加上一些时间(E)到我爸爸的时间上。

把结果汇总

由于时尚饮食横扫全国,我父母认为冰激凌没有他们想象的那样糟。做为负责任的父母,他们仍然想追踪我的消费来检查他们的假设。在工作时间,我妈妈和爸爸退回到了做不一致的决定,每个人只是保持了他们自己同意的频率的记录。一旦他们再次回到家里,他们就累加各自数量,以得到精确的总数。

追踪口味有点儿难度。每次我提出一勺子的量,他们都要写下我被许可的口味。偶尔地,我打开冰箱发现那种口味没有了,然后我在打电话请求减少我的总数。由于我是个小孩子,不记事,我记不住妈妈或爸爸是否记录了“同意”,因此我随机给其中一人打电话记录“不同意”。这没有关系,因为他们仍然能够累加各自独立的数量,在一天结束后再汇总出精确的总数。精确的总数,也就是说,直到灾难发生才出现。

我从妈妈那里收到了吃草莓味冰激凌的许可,但是在制冰盒和冰冻果子之间的普通地方没有找到。我就回拨过去报告没找到,但是在我说再见之前电话断了。由于不能联系到妈妈而带来的焦躁,我向爸爸报告了同样的情况。当总数在一天结束被汇总出来时,我父母被负的总数搞晕了。我们发明了“负冰激凌”吗?

不幸的是,我父母没有追踪无冲突复制数据类型的开发。如果他们知道,他们将用OR set解决这个问题,用单标签(unique tags)追踪增加和移除。如果被那篇论文武装了,研究了CRDT新的和旧的,那么他们就会退回去限制我的配额吗?意图很明显:如果我们能够独立计算一些东东,如果我们能够独立管理一个set,那么我们能够每天独立地强制同一个碗吗?非常不幸,做不到。重要的不同在于,增加一个和增加到set是可交换的【注1】,然而如果总数大于零,减少一个就不是可交换的。

让每个人同意

根据他们对于口味追踪的、令人沮丧的战争,我父母让他们的兼职管家玛丽协助处理这个问题。在失去对时尚饮食书籍的信任之后,我父母都腾出一部分工作时间去调查冰激凌的健康属性,也经常改变他们的观点。他们想仔细地追踪我吃了多少,尤其是剂量对于我的健康非常重要。妈妈和爸爸决定,只有他们都同意了,玛丽才能允许我吃一些。玛丽乐于接受这个任务,但是存在一个大问题:他不喜欢打电话。幸运的是,她喜欢发短信。不幸的是,信息仍然有着奇怪的、昂贵的回复。

玛丽、妈妈和爸爸坐在一起,尽量搞清楚如何用最少的消息数量来通过这个问题。玛丽发明了一个简单的方法:当我问她是否可以吃冰激凌时,她同时给我的爸爸和妈妈发短信以征求他们的意见,在收到玛丽短信之前他们是不会改变意见的。如果他们都同意,她将继续并让他们知道她将准备甜点了。如果有一个人说不同意,她将让他们知道碗里仍然是空的。这个协议,他们称之为冰激凌处于凝固和液体阶段后面的、二阶段提交(Two-phase Commit),需要4条信息才能完成。玛丽可以做得更好些,并节约一些短信上的花费吗?

在不考虑中央处理器故障的情况下,任何提交协议……需要至少 2(N-1)条消息才能完成一个事务。

他们比较幸运,我父母没有浪费太多时间去思考这个问题。玛丽偶然碰到了Cynthia Dwork和Dale Skeen的论文,它指出了玛丽需要知道的条件。只要玛丽发送短信,就没有比她的协议更好的办法了。

译文:冰激凌和分布式系统 》| 腊八粥