因果一致性的潜在危险和解决方案

论文地址：因果一致性的潜在危险和解决方案——Bailis等人。2012年

昨天我们看到了如何通过从最终一致性升级到因果一致性来获得更好的性能和更强的一致性。我们自问一下这个框架有什么缺点吗？
因果一致性具有有用的语义、较低的延迟、分区容忍度以及最近一种明显有效的体系结构，是未来广域分布式数据存储的理想模型。然而，因果一致性的实现面临严重的可伸缩性挑战。在本文中，我们确定了写吞吐量和可见性延迟之间的一个关键权衡，即由于缺少依赖关系，每个写操作对数据读取方有一定隐藏的时间消耗量。

可见性延迟是指系统收到写操作的时间与可以应用写操作的时间之间的延迟。两者之间的延迟是写入依赖项到达所需时间的函数。本文的重点是研究全球因果+一致性-需要跨数据中心协调的全球一致性，以及表示我们关心收敛性的“+”。
直观地说，可见性延迟和吞吐量是相互竞争的目标。如果超过了跨数据中心的聚合（全局）吞吐量限制，并且生成新版本的速度快于可以应用的速度，则由于形成不稳定的队列，可见性延迟将无限期地增加。这种权衡的效果被这样一个事实所放大：收敛因果一致性实际上要求所有数据中心在本地应用所有写操作：全局吞吐量限制为跨数据中心的最小应用容量。
较弱的一致性模型通常可以部分复制，这对于因果+一致性来说要困难得多。
收敛因果一致性需要限制全局写吞吐量的全对全复制。假设我们有两个数据中心，每个数据中心的应用容量为A。为了防止不稳定的队列，即以比远程应用更快的速度生成写操作，新的总写吞吐量必须限制为A；如果我们在数据中心之间平均分配新吞吐量，每一个都可以以a/2的速率在本地生成新的写操作。添加第三个同样强大的数据中心并不能改善这种情况：总的全局写吞吐量仍然是a，每个数据中心现在可以以a/3的速率生成写操作。在N个数据中心中，每个数据中心可以以a/N的速率写入数据。在异构的强大数据中心中，可持续的总写入速率仅限于最弱数据中心的本地应用容量。

听起来不是很好！特别是当你考虑到数据中心的增加往往是为了应对现有数据中心的有限容量——然而，由于因果关系趋同，增加另一个数据中心需要升级所有现有数据中心的容量。网络分区（和数据中心故障）使最小本地应用容量为零。
我们之所以陷入这种混乱，主要是因为已经研究过的主要因果一致性系统使用了潜在的因果关系：我们对应用程序逻辑一无所知，所以我们只能假设您看到的任何东西都是潜在的原因。
因果图扇出（degree）决定了所需的依赖项检查的数量，而其深度和连接性决定了执行检查时并发的程度。在实际环境中，潜在的因果关系图的数量大约是数亿次。经典因果一致性跟踪每个数据项的潜在依赖关系。在社交网络上，如果用户在查看了10个其他更新后发布了状态更新，则新更新可能依赖于所有更新。这将导致图的顶点度（或扇出）为10。在存储系统的级别上，考虑到许多现代应用程序都是以读为主的，因此在成百上千个依赖项中，这个数字可能要高得多。对于许多现代web服务来说，如果不查看更新可能依赖的数十个或数百个数据项，就很少或不可能发布更新。每个更新的依赖项的依赖项都包含在图中，并且这些更新的依赖项的依赖项是无限的，直到到达（一组）终端源事件为止。
这些大型图限制了本地应用容量，从而限制了最大的全局吞吐量。
正如我们昨天看到的，解决这一问题的一个有希望的办法是明确的因果关系：
与其跟踪所有潜在的依赖关系，不如只跟踪那些重要的依赖关系？……为了解决这些问题，我们考虑明确的因果关系，或应用程序指定的因果依赖关系。我们没有在happernbefore关系中包含所有可能的影响，而是遵从应用程序来告诉数据存储哪些依赖关系很重要。每个新的写操作都伴随着一组依赖项，这些依赖项决定了它发生在关系之前。因果一致的数据存储仍然强制所提供的在关系之前发生的传递，但不强制程序顺序或从关系中读取，除非应用程序明确指示这样做。这种明显的因果关系并不能解决所有对所有复制的问题，但它对吞吐量和延迟可见性之间的权衡具有重要意义。

对Twitter和Facebook中显式因果关系的研究表明，跨操作传递的显式因果关系很小：长度通常在数十个事件中，最多可达数千个事件。
对于像Twitter这样的主要服务，即使是一年的运营，潜在的因果关系链也比悲观的显式因果关系链大大约9个数量级（例如3400米*365比100）。

• 这些更小的链意味着更快的依赖性检查，增加容量和降低可见性延迟。（它们还增加了数据中心已经拥有所有依赖项的可能性——这一点在本文中没有直接指出）。
• 每次写入的扇出减少减少了元数据开销，远远低于对潜在因果关系的要求。“虽然在正常操作期间，由于垃圾收集，可能会减少潜在的因果关系开销，但我们不再需要依赖此机制来保持元数据的小型化。”
• 小的因果关系图给我们更多的独立写作集。“显式因果关系图不是所有更新之间具有高度连通性的潜在因果关系图（可能完全连通），而是生成几个较小的不相交图。”对每个独立图的写入可以并行应用。

这就是为什么固定因果一致性使用明确的因果关系。
在显式因果关系下，每个应用程序都定义了自己的发生在关系之前。这意味着对数据存储的每次写入都必须附带一组由程序员提供的依赖项（可能是空的）……例如，最近的工作经常提到更新个人隐私设置并随后在社交网络上发布敏感更新的示例。如果隐私设置的复制速度慢于新更新，则新更新可能会显示给意外的访问者。在显式因果关系下，应用程序将确保每个用户的最新隐私策略在每次写入之前发生。
收敛显式因果关系仍然面临着所有对所有复制的峰值吞吐量问题，尽管最小数据中心吞吐量可能由于较小的链而增加。
自发性的API最适合用于因果关系易于理解且捕获成本较低的系统层。这些层可能位于比存储或通信库更高的级别；在我们的讨论中，我们重点讨论了应用程序级别的因果关系。

作者的结论是：
如果收敛因果一致性是未来弱一致分布数据存储的首选模型，则必须对这些危险进行更详细的研究。显式因果关系降低了因果一致性的价格，但即使是这种降低的成本，是否也被因果关系相对于较弱形式的收敛一致性所提供的好处所抵消，尚不得而知。一个严肃的正面建议需要进一步考虑应用程序语义、实际工作负载以及预期和最坏情况下的操作条件。