冰激凌和分布式系统

jopen 10年前

英文原文：Ice Cream and Distributed Systems

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

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

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

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

　　假定网络由至少两个节点组成，这样网络可以被分为两个不相交的、非空集合：{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 的论文，它指出了玛丽需要知道的条件。只要玛丽发送短信，就没有比她的协议更好的办法了。

  • 注1：交换律是被普遍使用的一个数学名词，意指能改变某物的顺序而不改变其最 终结果。交换律是大多数数学分支中的基本性质，而且许多的数学证明需要倚靠交换律。简单运算的交换律许久都被假定存在，且没有给定其一特定的名称，直到 19 世纪，数学家开始形式化数学理论之后。http://zh.wikipedia.org/wiki/交換律
  • 注2：二阶段提交(Two-phase Commit)是指，在计算机网络以及数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法 (Algorithm)。二阶段提交的算法思路可以概括为： 参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。http://zh.wikipedia.org/wiki/二阶段提交