NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall

Haonan Lu, Shuai Mu, Siddhartha Sen, Wyatt Lloyd

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

Strictly serializable datastores greatly simplify application development. However, existing techniques pay unnecessary costs for naturally consistent transactions, which arrive at servers in an order that is already strictly serializable. We exploit this natural arrival order by executing transactions 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 this design, we identify a fundamental pitfall in relying on timestamps to provide strict serializability and name it the timestamp-inversion pitfall. We show that timestamp inversion has affected several existing systems. 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 common case by leveraging natural consistency. NCC is enabled by three components: non-blocking execution, decoupled response management, and timestamp-based consistency checking. NCC avoids the timestamp-inversion pitfall with 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 optimal best-case performance while guaranteeing strict serializability without relying on synchronized clocks. Our evaluation shows NCC outperforms state-of-the-art strictly serializable solutions by an order of magnitude on many workloads.

Original languageEnglish (US)
Title of host publicationProceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023
PublisherUSENIX Association
Pages305-323
Number of pages19
ISBN (Electronic)9781939133342
StatePublished - 2023
Event17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023 - Boston, United States
Duration: Jul 10 2023Jul 12 2023

Publication series

NameProceedings of the 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023

Conference

Conference17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023
Country/TerritoryUnited States
CityBoston
Period7/10/237/12/23

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Information Systems

Fingerprint

Dive into the research topics of 'NCC: Natural Concurrency Control for Strictly Serializable Datastores by Avoiding the Timestamp-Inversion Pitfall'. Together they form a unique fingerprint.

Cite this