NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall
NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall
复制标题
DOI：
10.48550/arxiv.2305.14270
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Haonan Lu;Shuai Mu;S. Sen;Wyatt Lloyd
中科院分区：
文献类型：
--
作者：
Haonan Lu;Shuai Mu;S. Sen;Wyatt Lloyd
严格可序列化的数据存储通过提供强大的一致性保证极大地简化了正确应用程序的开发。然而，现有技术为自然一致的事务付出了不必要的代价，这些事务以已经严格可序列化的顺序到达服务器。我们发现这些事务在数据中心工作负载中很普遍。我们利用这种自然的到达顺序，以最小的成本执行事务请求，同时乐观地假设它们是自然一致的，然后利用基于时间戳的技术来有效地验证执行是否确实一致。在设计这样一个基于时间戳的技术的过程中，我们确定了一个基本的陷阱，依赖于时间戳提供严格的串行化，并将其命名为时间戳反转陷阱。我们发现时间戳反演已经影响了一些现有的工作。我们提出了自然并发控制（NCC），一种新的并发控制技术，保证严格的串行化，并确保最小的成本-即，一轮延迟、无锁和非阻塞执行--在最好（和常见）的情况下，通过利用自然一致性。NCC由三个关键组件实现：非阻塞执行、解耦响应控制和基于时间戳的一致性检查。NCC通过一种新的技术：响应定时控制来避免时间戳反转，并提出了两种优化技术，即安全感知时间戳和智能重试，以减少错误中止。此外，NCC为只读事务设计了一个专门的协议，这是第一个实现最佳性能的协议，同时确保严格的可串行性，而不依赖于同步时钟。我们的评估表明，NCC在许多工作负载上的性能都超过了最先进的解决方案。
Strictly serializable datastores greatly simplify the development of correct applications by providing strong consistency guarantees. However, existing techniques pay unnecessary costs for naturally consistent transactions, which arrive at servers in an order that is already strictly serializable. We find these transactions are prevalent in datacenter workloads. We exploit this natural arrival order by executing transaction requests with minimal costs while optimistically assuming they are naturally consistent, and then leverage a timestamp-based technique to efficiently verify if the execution is indeed consistent. In the process of designing such a timestamp-based technique, we identify a fundamental pitfall in relying on timestamps to provide strict serializability, and name it the timestamp-inversion pitfall. We find timestamp-inversion has affected several existing works. We present Natural Concurrency Control (NCC), a new concurrency control technique that guarantees strict serializability and ensures minimal costs -- i.e., one-round latency, lock-free, and non-blocking execution -- in the best (and common) case by leveraging natural consistency. NCC is enabled by three key components: non-blocking execution, decoupled response control, and timestamp-based consistency check. NCC avoids timestamp-inversion with a new technique: response timing control, and proposes two optimization techniques, asynchrony-aware timestamps and smart retry, to reduce false aborts. Moreover, NCC designs a specialized protocol for read-only transactions, which is the first to achieve the optimal best-case performance while ensuring strict serializability, without relying on synchronized clocks. Our evaluation shows that NCC outperforms state-of-the-art solutions by an order of magnitude on many workloads.