SNOW Revisited: Understanding When Ideal READ Transactions Are Possible
SNOW Revisited: Understanding When Ideal READ Transactions Are Possible
复制标题
重温 SNOW：了解何时可以实现理想的 READ 事务
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Lynch
中科院分区：
文献类型：
--
作者：
K. Konwar;Wyatt Lloyd;Haonan Lu;N. Lynch
读取分布在服务器上的数据的READ事务在实际分布式存储系统的工作负载中占主导地位。SNOW定理[13]指出，具有最佳延迟和最强延迟的理想READ事务-即，“SNOW”READ事务-在需要三个或更多客户端的特定设置中是不可能的：至少两个读取器和一个写入器。然而，它留下了许多悬而未决的问题。我们用新的不可能性结果和新的算法来解决所有这些悬而未决的问题。首先，我们严格证明了[13]的结果，即不可能有一个满足三个或更多客户端的SNOW属性的READ交易系统。我们从这个证明中获得的洞察力导致梳理出陈述结果所需的隐含假设，并解决了关于两个客户端的SNOW可能性的开放问题。我们表明，它是可能的设计一个算法，其中雪是可能的在一个多作家，单读者（MWSR）设置时，客户端可以向其他客户端发送消息;另一方面，我们证明了它是不可能实现雪在一个多作家，单读者（MWSR）设置，这是更一般的两个客户端设置时，客户端到客户端的通信是不允许的。我们还纠正了[13]中的先前声明，即错误地将一个现有系统Eiger [12]识别为支持最强保证（SW）并且其只读事务具有有限延迟。因此，没有以前的算法提供最强的保证和有限的延迟。最后，我们介绍了前两个算法，以提供最强的保证有限的延迟。
READ transactions that read data distributed across servers dominate the workloads of real-world distributed storage systems. The SNOW Theorem [13] stated that ideal READ transactions that have optimal latency and the strongest guarantees—i.e., “SNOW” READ transactions–are impossible in one specific setting that requires three or more clients: at least two readers and one writer. However, it left many open questions. We close all of these open questions with new impossibility results and new algorithms. First, we prove rigorously the result from [13] saying that it is impossible to have a READ transactions system that satisfies SNOW properties with three or more clients. The insight we gained from this proof led to teasing out the implicit assumptions that are required to state the results and also, resolving the open question regarding the possibility of SNOW with two clients. We show that it is possible to design an algorithm, where SNOW is possible in a multi-writer, single-reader (MWSR) setting when a client can send messages to other clients; on the other hand, we prove it is impossible to implement SNOW in a multi-writer, single-reader (MWSR) setting-which is more general than the two-client setting-when client-to-client communication is disallowed. We also correct the previous claim in [13] that incorrectly identified one existing system, Eiger [12], as supporting the strongest guarantees (SW) and whose read-only transactions had bounded latency. Thus, there were no previous algorithms that provided the strongest guarantees and had bounded latency. Finally, we introduce the first two algorithms to provide the strongest guarantees with bounded latency.