# NCC: Natural Concurrency Control for Strictly Serializable Datastores by
Avoiding the Timestamp-Inversion Pitfall
Extended Version††thanks: This version is a preliminary draft. Complete
technical reports will be available in subsequent versions.

Haonan Lu⋆, Shuai Mu†, Siddhartha Sen‡, Wyatt Lloyd⋄
⋆University at Buffalo, †Stony Brook University,
‡Microsoft Research, ⋄Princeton University

###### Abstract

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.

##  1 Introduction

Strictly serializable datastores have been advocated by many recent works [12,
19, 32, 49, 56, 66, 18] because they provide a powerful abstraction of
programming in a single-threaded, transactionally isolated environment, which
greatly simplifies application development and prevents consistency anomalies
[9]. However, only a few concurrency control techniques can provide such
strong guarantees, i.e., they enforce strict serializability, and these
existing techniques are expensive.

Common techniques include distributed optimistic concurrency control (dOCC),
distributed two-phase locking (d2PL), and transaction reordering (TR). They
incur high overheads which manifest in extra rounds of messages (e.g., ones
for dOCC’s validation), distributed lock management (e.g., it is required by
d2PL), blocking (e.g., it is required by TR to exchange ordering information),
and excessive aborts (e.g., they happen to dOCC and d2PL). These overheads
severely degrade the system’s performance.

These costs are paid to (1) prevent transactions from interleaving, and (2)
ensure that later-issued transactions take effect after those finished ones
(i.e., in their real-time order), which are the two requirements of strict
serializability. However, we find that these costs are unnecessary for many
datacenter workloads where a transaction is executed within a datacenter and
then replicated within/across datacenters.

Many datacenter transactions do not interleave: First, many of them are
dominated by reads [12], and the interleaving of reads returning the same
value does not affect correctness. Second, many of them are short [24, 49, 39,
69, 27, 62], and short lifetimes reduce the likelihood of interleaving. Third,
the advances in datacenter networking techniques reduce the variance in
delivery times of concurrent requests [22, 14, 6], which results in less
interleaving.

Many datacenter transactions arrive at servers in an order that trivially
satisfies their real-time order relationship. That is, if a transaction is
issued in real-time after another one was committed, then the later
transaction must arrive at the servers after the other arrived.

Because many transactions do not interleave and their arrival order satisfies
the real-time order constraints, intuitively, simply executing their requests
in the order servers receive them (i.e., treating them as if non-transactional
simple operations) would naturally satisfy strict serializability. We call
these transactions naturally consistent.

Natural consistency unleashes opportunities for low-cost, strictly
serializable concurrency control, because, ideally, naturally consistent
transactions could be safely executed without any concurrency control,
incurring zero costs. However, existing techniques pay unnecessary overheads.
For instance, dOCC still requires extra rounds of messages for validation,
d2PL still acquires locks, and TR still blocks transactions for the exchange
of ordering information, even if validation always succeeds, locks are always
available, and nothing needs to be reordered. Therefore, this paper strives to
make naturally consistent transactions, which are prevalent in datacenter
workloads, as cheap as possible.

In this paper, 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. NCC’s design insight is to execute naturally
consistent transactions in the order they arrive as if they were non-
transactional operations while guaranteeing correctness without interfering
with transaction execution.

NCC is enabled by three key components. Non-blocking execution ensures that
servers execute transaction requests to completion without acquiring locks and
make their results immediately visible to avoid blocking subsequent
transactions, making transaction execution as cheap as that of non-
transactional operations. Decoupled response control separates the non-
blocking execution of requests from the sending of their responses,
guaranteeing that only correct (consistent) results are returned and there is
no risk of cascading aborts. Timestamp-based consistency check uses timestamps
to reflect requests’ execution order and ensures that transactions are
consistent by examining the timestamps.

In the process of designing the timestamp-based consistency check, we
identified a correctness pitfall in timestamp-based, strictly serializable
techniques. Specifically, these techniques sometimes fail to guard against an
execution order that is serializable but non-strict. Consequently, executing
transactions in such an order following the timestamps may incorrectly invert
the real-time order relationship between transactions and thus violates strict
serializability. We call this pitfall timestamp-inversion. Timestamp-inversion
is subtle because it possibly happens only if a transaction interleaves with a
set of non-conflicting transactions that have real-time order relationships.
The pitfall is fundamental as we find that it has affected multiple prior
works.

NCC handles timestamp-inversion with a novel technique, response timing
control, which is an integral part of decoupled response control. Response
timing control enforces real-time order constraints, without interfering with
the non-blocking execution or relying on synchronized clocks. NCC also
proposes two timestamp optimization techniques, asynchrony-aware timestamps
and smart retry, which reduce false aborts by controlling the timestamps.
Moreover, NCC designs a specialized protocol for read-only transactions,
which, to the best of our knowledge, is the first to achieve the optimal
performance [39] in the best case while ensuring strict serializability,
without having to rely on synchronized clocks.

We compare NCC with common strictly serializable techniques: dOCC, d2PL, and
TR, and two serializable protocols, TAPIR [69] and MVTO [53]. We use three
workloads: Google-F1, Facebook-TAO, and TPC-C (§5). The Google-F1 and
Facebook-TAO workloads synthesize production-like workloads for Google’s
Spanner [12, 57] and Facebook’s TAO [11], respectively. Both workloads are
read-dominated. TPC-C [61] consists of few-shot transactions that are write-
intensive. We further explore the workload space by varying the write
fractions in Google-F1. NCC significantly outperforms dOCC, d2PL, and TR with
$2$–$10\times$ lower latency and $2$–$20\times$ higher throughput. NCC
outperforms (serializable) TAPIR with $2\times$ higher throughput and
$2\times$ lower latency, and closely matches the performance of (serializable)
MVTO.

In summary, this work makes the following contributions:

  * •

Identifies timestamp-inversion, a fundamental correctness pitfall in
timestamp-based, strictly serializable concurrency control techniques.

  * •

Proposes NCC, a new concurrency control technique that provides strict
serializability and achieves minimal overhead in the best and common case by
exploiting natural consistency in datacenter workloads.

  * •

A strictly serializable read-only protocol with optimal best-case performance
that does not rely on synchronized clocks.

  * •

An implementation and evaluation that shows NCC outperforms existing strictly
serializable systems by an order of magnitude, and closely matches the
performance of systems that provide weaker consistency.

##  2 Background

This section provides the necessary background on transactional datastores,
strict serializability, and the general strictly serializable techniques.

Figure 1: An overview of system architecture and transaction execution. NCC
follows two-phase commit and is enabled by three design pillars: non-blocking
execution, decoupled response control, and timestamp-based consistency check.

###  2.1 Transactional Datastores

Transactional datastores are the back-end workhorse of many web applications.
They typically consist of two types of machines as shown in Figure 1. Front-
end client machines receive users’ requests, e.g., managing a web page, and
execute these requests on behalf of users by issuing transactions to the
storage servers that store the data. Servers are fault-tolerant, e.g., the
system state is made persistent on disks and replicated via replicated state
machines (RSM), e.g., Paxos [29].

Transactions are managed by coordinators, which can be co-located either with
a server or the client. This paper adopts the latter approach to avoid the
delays caused by shipping the transaction from the client to a server, if
servers were used as coordinators, while explicitly handling client failures.
The coordinator issues read/write operations to relevant servers, called
participants, following the transaction’s logic, which can be _one-shot_ ,
i.e., it knows a priori which data to read/write and can send all requests in
one step, or _multi-shot_ , i.e., it takes multiple steps as the data read in
one step determines which data to read/write in later steps. The system
executes transactions following a concurrency control protocol, which ensures
that transactions appear to take effect in an order that satisfies the
system’s consistency requirements. The stronger the consistency provided by
the system, the easier it is to develop correct applications.

###  2.2 Strict Serializability

_Strict serializability_ [23, 51], also known as external consistency [21], is
often considered the strongest consistency model.111“Consistency” in this
paper maps to the “I” (isolation level) in ACID. It requires that (1) there
exists a total order of transactions, and (2) the total order must respect the
real-time order, which means if transaction $\textit{tx}_{1}$ ends before
$\textit{tx}_{2}$ starts, then $\textit{tx}_{1}$ must appear before
$\textit{tx}_{2}$ in the total order. As a result, transactions appear to take
effect one at a time in the order the system receives them.

#### Formal definition.

We use Real-time Serialization Graphs (RSG) [1] to formalize the total order
and real-time order requirements. An RSG is a directed graph that captures the
order in which transactions take effect. A vertex in the graph is a committed
transaction. There are two types of edges. An execution edge
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{2}$
indicates that $\textit{tx}_{1}$ “affects” $\textit{tx}_{2}$, meaning that any
of the following happens: $\textit{tx}_{1}$ creates some data version $v_{i}$
and $\textit{tx}_{2}$ reads $v_{i}$; $\textit{tx}_{1}$ reads some data version
$v_{j}$ and $\textit{tx}_{2}$ creates $v$’s next version that is after
$v_{j}$; or $\textit{tx}_{1}$ creates some data version $v_{k}$ and
$\textit{tx}_{2}$ creates $v$’s next version that is after $v_{k}$. A chain of
execution edges constructs a directed path between two vertices, denoted by
$\textit{tx}_{1}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{2}$,
meaning that $\textit{tx}_{1}$ “transitively” affects $\textit{tx}_{2}$
through some intermediary transactions. A real-time edge
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2}$
captures the real-time order between $\textit{tx}_{1}$ and $\textit{tx}_{2}$,
meaning that $\textit{tx}_{1}$ commits before $\textit{tx}_{2}$’s client
issues $\textit{tx}_{2}$’s first request.

There exists a total order if and only if transactions do not circularly
affect each other. That is, the subgraph that comprises all vertices and only
execution edges is acyclic, meaning that the following invariant holds:

Invariant 1:
$\forall\textit{tx}_{1},\,\textit{tx}_{2}\,(\textit{tx}_{1}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{2}\implies\neg(\textit{tx}_{2}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{1}))$

The (total) execution order respects the real-time order if and only if the
execution edges (paths) do not invert the real-time edges, meaning that the
following invariant holds:

Invariant 2:
$\forall\textit{tx}_{1},\,\textit{tx}_{2}\,(\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2}\implies\neg(\textit{tx}_{2}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{1}))$

These invariants correspond to the total order and real-time order
requirements, respectively. Therefore, a system is strictly serializable if
and only if for any history of its execution, both invariants hold.

By enforcing a total order and the real-time order, strictly serializable
systems provide application programmers with the powerful abstraction of
programming in a single-threaded, transactionally isolated environment, and
thus they greatly simplify application development and eliminate consistency
anomalies. For example, a web application typically comprises many internal
services [50, 5]. If one service pushes a commit to production code that
triggers a message notifying another service to commit a patch, then any
service that uses a version of the code with the patch must also include the
original commit, enforcing the real-time order denoted by
$\textit{commit}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{patch}$.
As another example, if an admin removes Alice from a shared album and then
notifies Bob of the change (via a channel external to the system, e.g., a
phone call), who then uploads a photo he does not want Alice to see, then
Alice must not see Bob’s photo, since
$\textit{remove\\_Alice}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{new\\_photo}$.
Such guarantees cannot be enforced by weaker consistency models, e.g.,
serializability, because they do not enforce the real-time order that happens
externally to the system.

###  2.3 dOCC, d2PL, & Transaction Reordering

Due to the real-time order requirement, only a few general techniques provide
strict serializability. They are dOCC, d2PL, and transaction reordering (TR).
dOCC and d2PL typically require three round trips, one for each phase:
execute, prepare, and commit. In the execute phase, the coordinator reads the
data from the servers while writes are buffered locally at the coordinator.
d2PL acquires read locks in this phase while dOCC does not. In the prepare
phase, the coordinator sends prepare messages and the buffered writes to the
participant servers. d2PL locks all participants while dOCC only locks the
written data. dOCC must also validate that values read in the execute phase
have not changed. If all requests are successfully prepared, i.e., locks are
available and/or validation succeeds, the coordinator commits the transaction
by applying writes and notifying the participants of the commitment;
otherwise, the transaction is aborted and retried.

Transaction reordering typically requires two steps. In the first step, the
coordinator sends the requests to the servers, which make requests wait while
recording their arrival order relative to those of concurrent transactions,
i.e., constructing the execution and real-time edges in an RSG. This ordering
information usually increases linearly in size with respect to the number of
concurrent transactions. In the second step, the coordinator collects the
ordering information from participants, sorts the requests to eliminate
cycles, and servers execute the transactions in the sorted order.

These techniques are expensive, e.g., they require multiple rounds of
messages, locking, waiting, and aborts. We find that these overheads are
unnecessary for most of the transactions in many datacenter workloads, and
this observation has inspired the design in this paper.

##  3 Design Insight & Overview

This section explains natural consistency, which inspires our design, and
overviews the key design components.

(a) dOCC falsely aborts $\textit{tx}_{2}$

(b) Timestamp refinement examples

(c) NCC commits both $\textit{tx}_{1}$ and $\textit{tx}_{2}$

Figure 2: $\textit{tx}_{1}$ and $\textit{tx}_{2}$ are naturally consistent.
dOCC incurs unnecessary validation costs, and $\textit{tx}_{2}$ could be
falsely aborted due to lock unavailability. NCC can commit both transactions
with timestamp pre-assignment, refinement, and the safeguard check (denoted by
SG). These techniques are detailed in Section 4.1. Each version in NCC has a
($t_{w}$, $t_{r}$) pair which is included in server responses. RTC means
response timing control, detailed in Section 4.2.

###  3.1 Exploiting Natural Consistency

For many datacenter transactions, simply executing their requests in the order
servers receive them, as if they were non-transactional read/write operations,
would naturally satisfy strict serializability. In other words, they arrive at
servers in an order that is already strictly serializable. We call these
transactions _naturally consistent_. Key to natural consistency is the arrival
order of transaction requests.

Executing requests in the order they arrive trivially satisfies the real-time
order between transactions because a transaction that happens later in real-
time, i.e., it starts after another transaction has been committed, must
arrive at servers after the committed transaction have arrived.

Many requests in datacenter workloads arrive in an order that is total, i.e.,
transactions do not circularly affect each other, due to the following
reasons. First, many requests in real-world workloads are reads [12, 11], and
reads do not affect other reads. For instance, the reads that return the same
value can be executed in any order, without introducing cycles to their
serialization graph (§2.2), and thus servers can safely execute them in their
arrival order. Second, many transactions are short, e.g., they are one-shot
[24, 49, 39, 69, 27, 62] or can be made one-shot using stored procedures [48,
65, 33, 20, 58], and thus their requests are less likely to interleave with
others’. Third, the advances in datacenter networks reduce the variance of
message delivery times [47, 52, 46], and thus further reduces the likelihood
of request interleaving.

Naturally consistent transactions present room for improvement in existing
techniques. For instance, dOCC still requires validation messages while
executing these transactions; however, these messages are not only unnecessary
(e.g., they validate the transactions that are meant to be consistent), but
even worse, create a contention window (e.g., they lock the data between
prepare and commit) which could cause consistent transactions to falsely
abort, as shown in Figure 2(a). Ideally, the system could treat naturally
consistent transactions as non-transactional operations and execute them in
the order they arrive without any concurrency control, and strict
serializability is still guaranteed. Although this ideal case would be
impossible in general (e.g., we cannot differentiate transactions that are
naturally consistent from those that are not before they arrive and apply
concurrency control accordingly), our design is inspired by the prevalence of
naturally consistent transactions, and aims to minimize costs for as many of
these transactions as possible.

###  3.2 Three Pillars of Design

To achieve minimal overheads for naturally consistent transactions, our design
executes them in a manner that closely resembles non-transactional operations.
This is made possible through three key components.

#### Non-blocking execution.

Assuming transactions are naturally consistent, servers execute requests in
the order they arrive, ensuring that if two transactions have a real-time
order relationship, then they must be executed in their real-time order.
Requests are executed “urgently” to completion without acquiring locks, and
their results are immediately made visible to prevent blocking subsequent
requests. As a result, transactions are executed as cheaply as non-
transactional operations, without incurring contention windows.

#### Decoupled response control.

Because not all transactions are naturally consistent, servers must prevent
returning inconsistent results to clients and ensure there are no cascading
aborts. This is achieved by decoupling requests’ responses from their
execution, and responses are sent asynchronously only when it is verified
consistent. Inconsistent results are discarded and their requests are re-
executed.

#### Timestamp-based consistency check.

Consistency check must be as lightweight as possible, without interfering with
server-side execution. We leverage timestamps to capture the arrival order
(thus the execution order) of requests and design a client-side checker that
verifies if requests were executed in a total order, without incurring
overheads such as messages (as in dOCC and TR) and locks (as in dOCC and
d2PL).

Figure 1 shows at a high level how these three pillars support our design and
depicts the life cycle of transactions:

  * ➊

The user submits application requests to a client, which translates the
requests into transactions.

  * ➋

The (client) coordinator sends operations to the relevant servers, following
the transaction’s logic. The servers execute requests in their arrival order.
Their responses are inserted into a queue and sent asynchronously. The
responses include timestamps that capture requests’ execution order.

  * ➌

Responses are sent to the client when it is safe, determined by response
timing control (RTC).

  * ➍

The safeguard checks if transactions were executed in a total order by
examining the timestamps in responses. The coordinator sends commit/abort
messages to the servers and returns the results of committed transactions to
the user in parallel, without waiting for servers’ acknowledgments. x– z
explicitly handle client failures by leveraging a server as a backup
coordinator.

#### Limitations.

First, our design leverages natural consistency, which is often observed in
short (e.g., one or few shots) datacenter transactions; thus, many-shot long-
lasting transactions that are more likely to interleave might not benefit from
our design, while we support arbitrary-shot transactions. Second, the
timestamps associated with each request, including both reads and writes, must
be replicated to correctly handle failures, which could lead to additional
replication overhead, which we detail in Section 4.6.

Key to the correctness of our design is leveraging timestamps to verify a
total order that respects the real-time order. Yet, we identify a correctness
pitfall in relying on timestamps to ensure strict serializability, and this
pitfall has affected multiple existing works.

##  4 Natural Concurrency Control

This section presents the basic components of NCC, explains how NCC avoids the
timestamp-inversion pitfall, introduces two timestamp optimization techniques
and a specialized algorithm for read-only transactions, and concludes with
discussions of failure handling and correctness.

1 Function  _ExecuteRWTransaction(tx)_ :

$\textit{results}\leftarrow\\{\\}$; $\textit{t\\_pairs}\leftarrow\\{\\}$ //
server responses

t $\leftarrow$ AsynchronyAwareTS(tx) // §4.3

2 for  _req in __tx_ do

// send requests shot by shot,

// following tx’s logic

3 res, t_pair $\leftarrow$ NonblockingExecute(req, t)

4 $\textit{results}\leftarrow\textit{results}\,\cup\,\textit{res}$

5 $\textit{t\\_pairs}\leftarrow\textit{t\\_pairs}\,\cup\,\textit{t\\_pair}$

// all shots done, tx’s logic complete

6 ok, $t^{\prime}$ $\leftarrow$ SafeguardCheck(t_pairs)

7 if  _not ok_ then

ok $\leftarrow$ SmartRetry(tx, $t^{\prime}$) // §4.4

8

9 if  _ok_ then

10 AsyncCommitOrAbort(tx, “committed”)

11 return results

12

13 else

14 AsyncCommitOrAbort(tx, “aborted”)

go to 4.1 // abort, and retry from scratch

15

16

17

18 Function  _SafeguardCheck(t_pairs)_ :

19 $t_{w}\textit{\\_set}\leftarrow\\{\\}$;
$t_{r}\textit{\\_set}\leftarrow\\{\\}$

20 for  _t_pair in __t_pairs_ do

21 $t_{w}\textit{\\_set}\leftarrow
t_{w}\textit{\\_set}\,\cup\,\textit{t\\_pair.left}$

22 $t_{r}\textit{\\_set}\leftarrow
t_{r}\textit{\\_set}\,\cup\,\textit{t\\_pair.right}$

23 $t_{w}\textit{\\_max}\leftarrow\max\\{t_{w}\textit{\\_set}\\}$;
$t_{r}\textit{\\_min}\leftarrow\min\\{t_{r}\textit{\\_set}\\}$

24 if  _$t_{w}\textit{\\_max}\leq t_{r}\textit{\\_min}$_ then

// t_pairs overlap, $\exists$ a snapshot

25 return true, $t_{w}\textit{\\_max}$

26

27 else

28 return false, $t_{w}\textit{\\_max}$

29

30

Algorithm 4.1 Client (transaction coordinator) logic

1

2Multi-versioned data store:

$\textit{DS}[\textit{key}][\textit{ver}]$

// indexed by key, vers sorted by $t_{w}$

// ver is either committed or undecided

3 Response queue:

resp_qs[key][resp_q]

// resp queues for each key

4

5 Function  _NonblockingExecute(req, t)_ :

resp $\leftarrow$ [ ] // response message

6
$\textit{curr\\_ver}\leftarrow\textit{DS}[\textit{req.key}].\textit{most\\_recent}$

7 if  _req is __write_ then

8 $t_{w}\leftarrow\max\\{t,\,\textit{curr\\_ver}.t_{r}+1\\}$; $t_{r}\leftarrow
t_{w}$

9 new_ver $\leftarrow$ [req.value, ($t_{w}$, $t_{r}$), “undecided”]

10
$\textit{DS}[\textit{req.key}]\leftarrow\textit{DS}[\textit{req.key}]+\textit{new\\_ver}$

11 resp $\leftarrow$ [“done”, ($t_{w}$, $t_{r}$)]

12

13 else

14
$\textit{curr\\_ver}.t_{r}\leftarrow\max\\{t,\,\textit{curr\\_ver}.t_{r}\\}$

15 resp $\leftarrow$ [curr_ver.value, ($\textit{curr\\_ver}.t_{w}$,
$\textit{curr\\_ver}.t_{r}$)]

16

17 resp_qs[req.key].enqueue(resp, req, t, “undecided”)

RespTimingControl(resp_qs[req.key]) // §4.2

18

19

20 Function  _AsyncCommitOrAbort(tx, decision)_ :

21 foreach  _ver created by tx_ do

22 if  _decision $=$ “committed”_ then

23 ver.status $\leftarrow$ decision

24

25 else

26 DS.remove(ver)

27

28 foreach  _resp_q in __resp_qs_ do

29 foreach  _resp in __resp_q_ do

30 if  _resp.request $\in$ tx_ then

31 resp.q_status $\leftarrow$ decision

32

RespTimingControl(resp_q) // §4.2

33

34

Algorithm 4.2 Server execution and commitment

###  4.1 Protocol Basics

We build NCC on the three design pillars (§3.2) to minimize the costs for
naturally consistent transactions.

#### Pre-timestamping transactions.

NCC processes a transaction in two phases: execute and commit. Figure 4.1
shows the client (coordinator)’s logic. The coordinator starts a transaction
tx by pre-assigning it a timestamp t, which is a combination of the client’s
physical time and client identifier, uniquely identifying tx (line 4.1). When
two timestamps have the same value for the physical time, NCC breaks the tie
by comparing their client identifiers, i.e., timestamps are unique. t is
included in all of tx’s requests that are sent to servers shot by shot,
following tx’s application logic (lines 4.1 and 4.1). These timestamps
accompany tx throughout its life cycle and will be used to verify if the
results are consistent.

#### Refining timestamps to match execution order.

Figure 4.2 details the server-side logic for request execution and commitment.
Each key stores a list of versions in the order of the server creating them. A
version has three fields: value, a pair of timestamps ($t_{w},\,t_{r}$), and
status. value stores the data; $t_{w}$ is the timestamp of the transaction
that created the version; $t_{r}$ is the highest timestamp of transactions
that read the version; and status indicates the state of the transaction that
created the version: either (initially) undecided, or committed. An aborted
version is removed immediately.

The server always executes a request against the most recent version curr_ver,
which is either undecided or committed (line 4.2). Specifically, the server
executes a write by creating a new undecided version new_ver, which is now the
most recent version of the key, ordered after curr_ver (lines 4.2 and 4.2),
and executes a read by reading the value of curr_ver (line 4.2). Apparently,
NCC’s basic protocol can work with a single-versioned data store, while multi-
versioning is required only for smart retry, a timestamp optimization
technique (§4.4). The server refines the most recent version’s timestamp pair
to match the order in which requests are executed. Specifically, a write
request initializes new_ver’s $t_{w}$ and $t_{r}$ to the same value which is
no less than the write’s timestamp $t$ and curr_ver’s $t_{r}$ (line 4.2).
Similarly, a read request updates curr_ver’s $t_{r}$ if needed (line 4.2).
Figure 2(b) shows examples for how timestamps are refined for reads
($\textit{tx}_{1}$–$\textit{tx}_{3}$) and writes ($\textit{tx}_{4}$ and
$\textit{tx}_{5}$). These refined timestamps match requests’ arrival order
(thus the execution order) and are used to verify if the order is total.

#### Non-blocking execution and response queues.

The server executes requests in a non-blocking manner and decouples their
execution from responses. Specifically, a write creates a version and
immediately makes it visible to subsequent transactions; a read fetches the
value of the most recent version whose status could be undecided, without
waiting for it to commit; the server prepares the response (lines 4.2, 4.2,
and 4.2), inserts it into a response queue (lines 4.2 and 4.2), which
asynchronously sends the responses to clients when it is safe. (Section 4.2
will detail response timing control, which determines when a response is safe
to be sent so the real-time order is guaranteed.) Unlike d2PL and dOCC that
lock the data for at least one round-trip time in the execute and prepare
phases (i.e., the contention window), non-blocking execution ensures that a
transaction never exclusively owns the data without performing useful work. As
a result, the server never stalls, and thus CPUs are fully utilized to execute
requests. Moreover, non-blocking execution eliminates the contention window
completely and thus reduces false aborts.

#### Client-side safeguard.

A server response includes the timestamp pair ($t_{w},\,t_{r}$) of the most
recent version, e.g., new_ver for a write and curr_ver for a read. When the
transaction has completed its logic (i.e., all shots are executed) and the
client has received responses to all its requests, the safeguard checks if
there exists a consistent snapshot that intersects all ($t_{w},\,t_{r}$) pairs
in server responses, as shown in Figure 4.1. This intersecting snapshot
identifies the transaction’s synchronization point. The safeguard commits a
transaction if the timestamp pairs overlap (lines 4.1, 4.1–4.1). Figure 2(c)
shows an example execution where NCC executes the same transactions in Figure
2(a). The safeguard enables NCC to commit both transactions without
unnecessary overhead such as dOCC’s validation cost and false aborts.

When the client has decided to commit or abort the transaction, the protocol
enters the commit phase by sending the commit/abort messages to the
participant servers. If the transaction is committed, the server updates the
status of the versions created by the transaction from undecided to committed;
otherwise, the versions are deleted (lines 4.2–4.2, Figure 4.2). The client
retries the aborted transaction. The client sends the results of the committed
transaction to the user in parallel with the commit messages, without waiting
for servers’ acknowledgments (lines 4.1–4.1, Figure 4.1).

NCC achieves minimal costs by urgently executing transactions in a non-
blocking manner and by ensuring a total order with the light-weight timestamp-
based safeguard. Yet, in order to provide strict serializability, NCC must
enforce the real-time order between transactions by handling the timestamp-
inversion pitfall, which we detail next.

###  4.2 Response Timing Control

NCC avoids timestamp-inversion by disentangling the subtle interleaving, e.g.,
a transaction interleaves with a set of non-conflicting transactions that have
real-time order dependencies (e.g., Figure LABEL:fig:challenge), without
relying on specialized clocks. To untangle the transactions, NCC proposes
response timing control (RTC), which controls the sending time of responses.
It is safe to send the response of a request $\textit{req}_{1}$ when the
following dependencies are satisfied:

  1. D1

If $\textit{req}_{1}$ reads a version created by $\textit{req}_{2}$ of another
transaction, then $\textit{req}_{1}$’s response is not returned until
$\textit{req}_{2}$ is committed and is discarded ($\textit{req}_{1}$ will be
re-executed) if $\textit{req}_{2}$ is aborted.

  2. D2

If $\textit{req}_{1}$ is a write and there are reads that read the version
which immediately precedes the one created by $\textit{req}_{1}$, then
$\textit{req}_{1}$’s response is not returned until the reads are
committed/aborted.

  3. D3

If $\textit{req}_{1}$ is a write that creates a version immediately after the
version created by $\textit{req}_{2}$ of another transaction, then
$\textit{req}_{1}$’s response is not returned until $\textit{req}_{2}$ is
committed/aborted.

By enforcing the above dependencies, NCC controls the sending of responses so
that the transactions which form the subtle interleaving are serialized in
their real-time order. For instance, in Figure LABEL:fig:challenge, server $A$
cannot send the response of $\textit{tx}_{1}$ until $\textit{tx}_{3}$ has been
committed (assuming at least one of them writes to $A$). As a result, any
transaction $\textit{tx}_{2}$ that begins after $\textit{tx}_{1}$ receives its
response, i.e.,
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2}$,
must be executed after $\textit{tx}_{1}$, and thus after $\textit{tx}_{3}$ as
well because all requests of $\textit{tx}_{3}$ have at least been executed
when any of $\textit{tx}_{2}$’s requests arrive and the server always execute
transactions in their arrival order. This results in a total order,
$\textit{tx}_{3}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{2}$,
which respects the real-time order, enforcing section 2.2, as shown in Part
III of Figure LABEL:fig:challenge.

NCC controls response timing by managing response queues, independently from
request execution. NCC maintains one response queue per key. A queue item
consists of four fields: response that stores the response message of a
request, the request itself, ts which is the pre-assigned timestamp of the
request, and q_status that indicates the state of the request, which is
initially undecided, and updated to either committed or aborted when the
server receives the commit/abort message for this request (lines 4.2–4.2,
Figure 4.2).

1

2Function  _RespTimingControl(resp_q)_ :

head $\leftarrow$ resp_q.head() // the oldest response

3 while  _head.q_status $\neq$ “undecided”_ do

resp_q.dequeue() // pop the head

4 new_head $\leftarrow$ resp_q.head()

5 new_req $\leftarrow$ new_head.request; t $\leftarrow$ new_head.ts

_6_ _ _ if  _head.q_status $=$ “aborted” _

7  __ and head.request is __write and new_req is __read then

// fix read locally

8 resp_q.dequeue()

9 NonblockingExecute(new_req, t)

10

11 head $\leftarrow$ resp_q.head()

12 curr_item $\leftarrow$ head

13 repeated loop  __

14 resp $\leftarrow$ curr_item.response

15 if  _resp $\neq$ nil_ then

sys_call __.send( resp) // send to client

16 curr_item.delete(resp)

17 next_item $\leftarrow$ curr_item.next()

_18_ _ _ if  _curr_item.request is not __read_

19  __ or next_item.request is not __read then

20 break repeated loop __

21 curr_item $\leftarrow$ next_item

22

23

Algorithm 4.3 Response timing control

#### Managing response queues.

Figure 4.3 details how NCC manages response queues. NCC iterates over the
queue items from the head (i.e., the oldest response) until it finds the first
response whose q_status is undecided. This response satisfies the three
dependencies because all responses before it have been decided, i.e., the
requests it depends on are committed/aborted (lines 4.3–4.3). The server sends
this response message to the client (lines 4.3–4.3). If this response is to a
read request, then the server also sends all consecutive read responses that
follow it, because all these read responses satisfy Dependency D1 (lines
4.3–4.3).

#### Fixing reads locally.

When the server receives an abort message for a write request, it must
invalidate the responses of any reads that have fetched the value of the
aborted write. This is necessary to avoid returning invalid results to the
client and to prevent cascading aborts. Specifically, the server removes the
response of such a read from the response queue and re-executes the read
request, e.g., it fetches the current most recent version, prepares a new
response, and inserts the new response to the tail of the queue (lines
4.3–4.3).

#### Avoiding indefinite waits.

To avoid responses from circularly waiting on dependencies across different
keys, NCC early aborts a request (thereby aborting the transaction to which it
belongs) if its pre-assigned timestamp is not the highest the server has seen
and if its response cannot be sent immediately, i.e., it is not the head of
the queue. Specifically, the server sends a special response to the client
without executing the request. The special response includes a field
early_abort which allows the client to bypass the safeguard and abort the
transaction. We omit the details from the pseudocode for simplicity and
clarity.

Response timing control (RTC) is a general solution to timestamp-inversion,
without the need for specialized clocks. It does not incur more aborts even
when responses are not sent immediately, because response management is
decoupled from request execution. That is, whether a transaction is committed
or aborted is solely based on timestamps, and RTC does not affect either pre-
assignment or refinement of timestamps. Yet, NCC’s performance also depends on
how well timestamps capture the arrival order of (naturally consistent)
transactions. That is, timestamps that do not match transactions’ arrival
order could cause transactions to falsely abort even if they are naturally
consistent. In the next two subsections, we will discuss optimization
techniques that enable timestamps to better match the arrival order.

###  4.3 Asynchrony-Aware Timestamps

NCC proposes two optimizations: a proactive approach that controls how
timestamps are generated before transactions start and a reactive approach
that updates timestamps to match the naturally consistent arrival order after
requests are executed. This subsection discusses the proactive approach.

The client pre-assigns the same timestamp to all requests of a transaction;
however, these requests may arrive at their participant servers at very
different physical times, which could result in a mismatch between timestamp
and arrival order, as shown in Figure 3(a). Transactions $\textit{tx}_{1}$ and
$\textit{tx}_{2}$ start around the same time and thus are assigned close
timestamps by their clients, e.g., $t_{1}=1004$ and $t_{2}=1005$,
respectively. Because the latency between $B$ and $\textit{CL}_{1}$ is greater
than that between $B$ and $\textit{CL}_{2}$, $\textit{tx}_{1}$ may arrive at
$B$ later than $\textit{tx}_{2}$, but $\textit{tx}_{1}$ has a smaller
timestamp. As a result, the safeguard may falsely reject $\textit{tx}_{1}$,
e.g., server $B$ responds with a refined timestamp pair ($1006,\,1006$) which
does not overlap with ($1004,\,1004$), the timestamp pair returned by server
$A$. However, aborting $\textit{tx}_{1}$ is unnecessary because
$\textit{tx}_{1}$ and $\textit{tx}_{2}$ are naturally consistent.

To tackle this challenge, NCC generates timestamps while accounting for the
time difference, $t_{\Delta}$, between when a request is sent by the client
and when the server starts executing the request. Specifically, the client
records the physical time $t_{c}$ before sending the request to the server;
the server records the physical time $t_{s}$ before executing the request and
piggybacks $t_{s}$ onto the response sent back to the client; and the client
calculates $t_{\Delta}$ by finding the difference between $t_{c}$ and $t_{s}$,
i.e., $t_{\Delta}=t_{c}-t_{s}$. By measuring the end-to-end time difference,
$t_{\Delta}$ effectively masks the impact of queuing delays and clock skew.
The client maintains a $t_{\Delta}$ for each server it has contacted. An
asynchrony-aware timestamp is generated by adding the client’s current
physical time and the greatest $t_{\Delta}$ among the servers this transaction
will access. For instance, given the values of $t_{\Delta}$ shown in Figure
3(a), $\textit{CL}_{1}$ assigns $\textit{tx}_{1}$ timestamp $1014$ (i.e.,
$1004+10$) and $\textit{CL}_{2}$ assigns $\textit{tx}_{2}$ $1010$ (i.e.,
$1005+5$), and both transactions may successfully pass their safeguard check,
capturing natural consistency.

(a) Asynchrony-aware timestamps

(b) Safeguard false rejects

(c) Smart retry reduces false rejects

Figure 3: Optimizations that match the timestamps with transactions’ arrival
order. Asynchrony-aware timestamps proactively controls the pre-assigned
timestamps before execution. Smart retry reactively fixes false rejects by the
safeguard after execution thus avoids aborting and re-executing transactions.

###  4.4 Smart Retry

1

2Function  _SmartRetry(tx, $t^{\prime}$)_ :

3 foreach  _ver accessed by __tx_ do

// next version of the same key

4 next_ver $\leftarrow$ ver.next()

5 if  _next_ver. $t_{w}$ $\leq$ $t^{\prime}$_ then

6 return false

7

8 if  _ver created by __tx and ver.$t_{w}$ $\neq$ ver.$t_{r}$_ then

9 return false

10

11 if  _ver created by __tx_ then

12 ver.$t_{w}$ $\leftarrow$ $t^{\prime}$; ver.$t_{r}$ $\leftarrow$
$t^{\prime}$

13

14 else

15 ver.$t_{r}$ $\leftarrow$ $max\\{\textit{ver}.t_{r},\,t^{\prime}\\}$

16

17

18 return true

19

Algorithm 4.4 Smart retry

NCC proposes a reactive approach to minimizing the performance impact of the
safeguard’s false rejects, which happen when timestamps fail to identify the
naturally consistent arrival order, as shown in Figure 3(b). Initially,
version $A_{0}$ has a timestamp pair ($t_{w}=0$, $t_{r}=0$), and $B_{0}$ has
($t_{w}=0$, $t_{r}=5$). The same transactions $\textit{tx}_{1}$ and
$\textit{tx}_{2}$ as those in Figure 2(c) access both keys. Following NCC’s
protocol, $\textit{tx}_{1}$’s responses contain the timestamp pairs ($0,\,4$)
and ($6,\,6$) from $A$ and $B$, respectively, which will be rejected by the
safeguard because they do not overlap. However, aborting $\textit{tx}_{1}$ is
unnecessary because $\textit{tx}_{1}$ and $\textit{tx}_{2}$ are naturally
consistent.

Instead, NCC tries to “reposition” a rejected transaction with respect to the
transactions before and after it to construct a total order instead of
aborting and re-executing the rejected transaction from scratch, which would
waste all the work the server has done for executing it. Specifically, NCC
chooses a time that is nearest “in the future” and hopes the rejected
transaction can be re-committed at that time. This is possible if the chosen
time has not been taken by other transactions.

Figure 4.4 shows the pseudocode for smart retry. When the transaction fails
the safeguard check, NCC suggests a new timestamp $t^{\prime}$, which is the
maximum $t_{w}$ in the server responses. The client then sends smart retry
messages that include $t^{\prime}$ to the participant servers, which then
attempt to reposition the transaction’s requests at $t^{\prime}$. The server
can reposition a request if there has not been a newer version that was
created before $t^{\prime}$ (lines 4.4–4.4) and, if the request is a write,
the version it created has not been read by any transactions (lines 4.4 and
4.4). The server updates the timestamps of relevant versions if smart retry
succeeds, e.g., the created version has a new timestamp pair
($t^{\prime},\,t^{\prime}$), and $t_{r}$ of read version is updated to
$t^{\prime}$ if $t^{\prime}$ is greater (lines 4.4–4.4). The client commits
the safeguard-rejected transaction if all its smart retry requests succeed,
and “truly” aborts it, otherwise (lines 4.1 and 4.1, Figure 4.1).

Not only does smart retry avoid unnecessary “true” aborts, it also unleashes a
higher degree of concurrency, as shown in Figure 3(c). The servers have
executed a newer transaction $\textit{tx}_{2}$ when $\textit{tx}_{1}$’s smart
retry (SR) messages arrive, and both transactions can be committed even if the
messages interleave, e.g., $\textit{tx}_{1}$’s smart retry succeeds and
$\textit{tx}_{2}$ passes its safeguard check, because $\textit{tx}_{2}$’s pre-
assigned timestamps have left enough room for repositioning
$\textit{tx}_{1}$’s requests. In contrast, validation-based techniques would
unnecessarily abort $\textit{tx}_{1}$ (considering SR as dOCC’s validation
messages) due to the presence of a conflicting transaction $\textit{tx}_{2}$.

#### Garbage collection.

Old versions are temporarily stored and quickly garbage collected as soon as
they are no longer needed by undecided transactions for smart retry. Only the
most recent versions are used to serve new transactions.

###  4.5 Read-Only Transactions

NCC designs a specialized read-only transaction protocol for those read-
dominated workloads [11, 12, 42, 39, 26]. Similar to existing works, NCC
optimizes read-only transactions by eliminating their commit phase because
they do not modify the system state and have nothing to commit. By eliminating
commit messages, read-only transactions achieve the optimal performance in the
best case, i.e., one round of non-blocking messages with constant metadata
[39, 40, 41].

Eliminating commit messages brings a new challenge to response timing control:
write responses can no longer track their dependencies on preceding read-only
transactions, as they do not know if and when those reads are
committed/aborted (§4.2). To tackle this challenge, NCC aborts a read-only
transaction if its requests could possibly cause the subtle interleaving that
leads to timestamp-inversion.

Specifically, each client tracks $t_{ro}$ which is the $t_{w}$ of the version
created by the most recent write on a server, and the client maintains a map
of $t_{ro}$ for each server this client has contacted. A read-only transaction
is identified by a Boolean field in the API, IS_READ_ONLY. The client pre-
assigns the transaction a timestamp $t$ and sends each read request to the
participant server together with the $t_{ro}$ of the server. To execute a read
request, the server checks the version at $t_{ro}$. If the version is still
the most recent, the server continues to execute the read following the basic
protocol; otherwise, the server sends a special response that contains a field
ro_abort immediately without executing the request. If any of the responses
contain ro_abort, the client aborts this read-only transaction; otherwise, the
client continues with the safeguard check and, if needed, smart retry, after
which the client does not send any commit/abort messages. If the client can
make the pre-assigned timestamp $t$ no less than the greatest $t_{ro}$ across
participant servers, then the read-only transaction is guaranteed to commit as
long as there are not ro_abort responses.

This protocol pays more aborts in the worst case in exchange for reduced
message overhead in the normal case, a trade-off that is worthwhile for read-
dominated workloads where writes are few so aborts are rare, and read-only
transactions are many so the savings in message cost are significant. This
protocol also expedites the sending of responses to read-write transactions
because read-only transactions do not insert responses into the response
queue, i.e., a write response depends only on the reads of preceding read-
write transactions in Dependency D2, not those of read-only transactions.

###  4.6 Failure Handling

#### Tolerating server failures.

NCC can assume servers never fail as their state is typically made persistent
on disks and replicated via state machine replication such as Paxos [28]. All
state changes incurred by a transaction in the execute phase (e.g., $t_{w}$
and $t_{r}$ of each request) must be replicated for correctness. For instance,
after a request is executed, the server inserts its response into the response
queue and, in parallel, replicates the request to other replicas. Its response
is sent back to the client when it is allowed by response timing control and
when its replication is finished. Commit/abort and smart retry messages are
also replicated. This basic scheme ensures correctness but incurs high
overhead. We will investigate possible optimizations in future work, e.g., NCC
could defer replication to the last shot of a transaction where all state
changes are replicated once and for all, without having to replicate each
request separately. Server replication inevitably increases latency but does
not introduce more aborts, because whether a transaction is committed or
aborted is solely based on its timestamps which are decided during request
execution and before replication starts.

#### Tolerating client failures.

NCC must handle client failures explicitly because clients are not replicated
in most systems and NCC co-locates coordinators with clients. NCC adopts an
approach similar to that in Sinfonia [4] and RIFL [30]. We briefly explain it
as follows. For a transaction tx, one of the storage servers tx accesses is
selected as the backup coordinator, and the other servers are cohorts. In the
last shot of the transaction logic, which is identified by a field
IS_LAST_SHOT in the requests, the client notifies the backup coordinator of
the identities of the complete set of cohorts. Cohorts always know which
server is the backup coordinator. When the client crashes, e.g., unresponsive
for a certain amount of time, the backup coordinator reconstructs the final
state of $tx$ by querying the cohorts for how they executed $tx$ and
commits/aborts tx following the same safeguard and smart retry logic. Because
computation is deterministic, the backup coordinator always makes the same
commit/abort decision as the client would do if the client did not fail. To
tolerate one client failure, NCC needs one backup coordinator which is a
storage server replicated in a usual way.

###  4.7 Correctness

This section provides proof intuition for why NCC is safe and live. At a high
level, NCC guarantees a total order, the real-time order, and liveness, with
the mechanisms (M1) the safeguard, (M2) non-blocking execution with response
timing control, and (M3) early aborts, respectively. We provide a formal proof
of correctness in a technical report [tech].

#### NCC is safe.

We prove that NCC guarantees strict serializability by demonstrating that both
sections 2.2 and 2.2 are upheld. These two invariants correspond to the total
order and real-time order requirements, respectively. We present a simplified
version of our proof by reasoning about real-time and execution edges in the
RSGs while our arguments can be applied to execution paths by leveraging the
transitivity of execution edges (§2.2).

Intuitively, NCC commits all requests of a transaction at the same
synchronization point, and the synchronization points of all committed
transactions construct a total order. The synchronization point is identified
by the safeguard searching for a timestamp $t_{c}$ that intersects the
($t_{w},\,t_{r}$) pairs in server responses, and $t_{c}$ is the commit
timestamp (synchronization point) that uniquely identifies the transaction.
Specifically, we prove that the safeguard enforces section 2.2, by
contradiction. Assume 1 both $\textit{tx}_{1}$ and $\textit{tx}_{2}$ are
committed, 2
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{2}$,
and 3
$\textit{tx}_{2}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{1}$.
Then, by the definition of execution edges (§2.2) and 3, we can derive that 4
there must exist requests $\textit{req}_{2}$ and $\textit{req}_{1}$ from
$\textit{tx}_{2}$ and $\textit{tx}_{1}$, respectively, such that any of the
following happens: $\textit{req}_{1}$ reads the version written by
$\textit{req}_{2}$, $\textit{req}_{1}$ creates a version ordered after the
version read by $\textit{req}_{2}$, or $\textit{req}_{1}$ creates a version
ordered after the version created by $\textit{req}_{2}$. Then, by NCC’s
timestamp refinement logic, we must have $t_{r2}<t_{w1}$ where $t_{r2}$ is
$t_{r}$ in $\textit{req}_{2}$’s response and $t_{w1}$ is $t_{w}$ in that of
$\textit{req}_{1}$’s.222$t_{r2}=t_{w1}$ if and only if $\textit{req}_{1}$
reads the version created by $\textit{req}_{2}$, and we break the tie by
following the requests’ execution order, for simplicity. Let $t_{c2}$ and
$t_{c1}$ denote the commit timestamp $t_{c}$ of $\textit{tx}_{2}$ and
$\textit{tx}_{1}$, respectively. By the safeguard’s logic, $t_{w}\leq
t_{c}\leq t_{r}$ for any ($t_{w},\,t_{r}$) pair. Thus, $t_{c2}\leq t_{r2}$ and
$t_{w1}\leq t_{c1}$, which implies $t_{c2}<t_{c1}$ because $t_{r2}<t_{w1}$. By
applying the same arguments to the assumption 2, we can derive
$t_{c1}<t_{c2}$, which, however, contradicts $t_{c2}<t_{c1}$. Therefore, we
have proved that NCC enforces a simplified version of section 2.2.

We prove that NCC enforces section 2.2 by considering two cases while assuming
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2}$.
Case 1, $\textit{tx}_{1}$ and $\textit{tx}_{2}$ access some common data items.
Then, we must have 5
$\textit{tx}_{1}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{2}$,
because the servers must execute $\textit{tx}_{1}$’s requests before
$\textit{tx}_{2}$’s on the overlapping data by NCC’s protocol, i.e., the
server executes requests in their arrival order. Then, it must be true that
$\neg(\textit{tx}_{2}\overset{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}{\longmapsto}\textit{tx}_{1})$,
by section 2.2 and 5. Case 2, $\textit{tx}_{1}$ and $\textit{tx}_{2}$ access
disjoint data sets. Then, we prove the claim by contradiction. Assume
$\textit{tx}_{2}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{exe}}}\textit{tx}_{1}$,
then there must exist $\textit{req}_{2}$ and $\textit{req}_{1}$ in
$\textit{tx}_{2}$ and $\textit{tx}_{1}$, respectively, such that
$\textit{req}_{2}$ and $\textit{req}_{1}$ satisfy 4, by the definition of
execution edges. $\textit{req}_{1}$’s response is not returned until
$\textit{req}_{2}$ is committed or aborted, by response timing control (§4.2).
Then, $\textit{req}_{2}$ is issued before $\textit{req}_{1}$’s client receives
$\textit{req}_{1}$’s response because a request, e.g., $\textit{req}_{2}$, can
be committed or aborted only after it is issued and executed. Thus, we can
derive
$\neg(\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2})$
because $\textit{tx}_{2}$ has at least one request, e.g., $\textit{req}_{2}$,
which starts before $\textit{tx}_{1}$ receives all its responses. That is,
$\textit{tx}_{2}$ starts before $\textit{tx}_{1}$ is committed, which
contradicts our assumption
$\textit{tx}_{1}\xrightarrow{\text{\raisebox{-1.86002pt}[0.0pt][-3.09999pt]{rto}}}\textit{tx}_{2}$.
Therefore, section 2.2 must hold.

Workload | Write fraction | Assoc-to-obj | # keys/RO | # keys/RW | Value size | # cols/key | Zipfian
---|---|---|---|---|---|---|---
Google-F1 |  $0.3\%$ [$0.3\%$–$30\%$] | — |  $1$–$10$ |  $1$–$10$ | $1.6\,\textrm{KB}\pm 119\,\textrm{B}$ | $10$ | $0.8$
Facebook-TAO | $0.2\%$ | $9.5:1$ |  $1$–$1\,\textrm{K}$ | $1$ |  $1$–$4\,\textrm{KB}$ |  $1$–$1\,\textrm{K}$ | $0.8$
TPC-C | New-Order | Payment | Delivery | Order-Status | Stock-Level | Dist/WH | WH/svr
$44\%$ | $44\%$ | $4\%$ | $4\%$ | $4\%$ | $10$ | $8$
|  |  |  |  |  |  |
Figure 4: Workload parameters. RO and RW mean read-only and read-write
transactions, respectively. TPC-C has a scaling factor of $10$ districts per
warehouse and $8$ warehouses per server.

#### NCC is live.

NCC’s non-blocking execution guarantees that requests are always run to
completion, i.e., execution never stalls (§4.1). Blocking possibly happens
only to the sending of responses due to response timing control, and NCC
avoids circular waiting with early aborts (§4.2). Thus, NCC guarantees that
transactions finish eventually.

NCC’s specialized read-only transaction protocol and optimization techniques
such as asynchrony-aware timestamps and smart retry do not affect correctness,
because transactions are protected by the three mechanisms (i.e., M1, M2, and
M3 summarized at the beginning of this subsection) no matter if optimizations
or the specialized protocol is used.

##  5 Evaluation

This section answers the following questions:

  1. 1.

How well does NCC perform, compared to existing strictly serializable
techniques dOCC, d2PL, and TR?

  2. 2.

How well does NCC perform, compared to state-of-the-art serializable (weaker
consistency) techniques?

  3. 3.

How well does NCC recover from client failures?

Workload | Contention | # shots | Natural consistency | NCC takeaway
---|---|---|---|---
Facebook-TAO | Low | $1$ | Read-dominated | Least-cost reads by novel RO protocol
Google-F1 | Low | $1$ | Read-dominated | Least-cost reads by novel RO protocol
TPC-C |  Medium$\rightarrow$High | Multi-shot | Write-intensive | TO captures in-order delivery, minimizes false aborts
Google-WF |  Low$\rightarrow$High | $1$ | Write-intensive | TO captures in-order delivery, minimizes false aborts
|  |  |  |
Figure 5: Two categories of natural consistency: Facebook-TAO and Google-F1
have low contention, TPC-C and Google-WF (varying write fractions) are write-
intensive but arrive in order. TPC-C Payment and Order-Status are multi-shot.

#### Implementation.

We developed NCC on Janus’s framework [49]. We improved the framework by
making it support multi-shot transactions, optimizing its baselines, and
adding more benchmarks. NCC’s core protocols have $\sim$3 K lines of C++ code.
We also show the results of NCC-RW, a version without the read-only
transaction protocol, i.e., all transactions are executed as read-write
transactions.

#### Baselines.

The evaluation includes three strict serializable baselines (dOCC, d2PL, and
Janus) and two non-strict serializable baselines (MVTO and TAPIR). We choose
d2PL and dOCC because they are the most common strictly serializable
techniques. We choose Janus because it is the only open-source TR-based
strictly serializable system we can find. We choose MVTO because it has the
highest best-case performance among all (weaker) serializable techniques,
presenting a performance upper bound. We choose TAPIR because it utilizes a
timestamp-based concurrency control.

Our evaluation focuses on concurrency control and assumes servers never fail.
Janus and TAPIR are unified designs of the concurrency control and replication
layers, so we disabled their replication and only compare with their
concurrency control protocols, shown as Janus-CC and TAPIR-CC, to make
comparisons fair. We compare with two variants of d2PL. d2PL-no-wait aborts a
transaction if the lock is not available. d2PL-wound-wait makes the
transaction wait if it has a larger timestamp and aborts the lock-holding
transaction otherwise. All baselines are fully optimized: we co-locate
coordinators with clients (even if baselines cannot handle client failures),
combine the execute and prepare phases for d2PL-no-wait and TAPIR-CC, and
enable asynchronous commitment, i.e., the client replies to the user without
waiting for the acknowledgments of commit messages.

###  5.1 Workloads and Experimental Setup

We evaluate NCC under three workloads that cover both read-dominated “simpler”
transactions and many-write more “complex” ones. Google-F1 and Facebook-TAO
synthesize real-world applications and capture the former. They are one-shot
and read-heavy. TPC-C has multi-shot transactions and is write-intensive,
capturing the latter. We also vary write fractions in Google-F1 to further
explore the latter. Table 4 shows the workload parameters.

Google-F1 parameters were published in F1 [57] and Spanner [12]. Facebook-TAO
parameters were published in TAO [11]. TPC-C’s New-Order, Payment, and
Delivery are read-write transactions. Its Order-Status and Stock-Level are
read-only. Janus’s original implementation of TPC-C is one-shot, and we
modified it to make Payment and Order-Status multi-shot, to demonstrate NCC is
compatible with multi-shot transactions and evaluate its performance beyond
one-shot transactions (yet still relatively short).

#### Experimental setting.

We use Microsoft Azure [45]. Each machine has $4$ CPUs ($8$ cores),
$16\,\textrm{GB}$ memory, and a $1\,\textrm{Gbps}$ network interface. We use
$8$ machines as servers and $16$–$32$ machines as clients that generate open-
loop requests to saturate the servers. (The open-loop clients back off when
the system is overloaded to mitigate queuing delays.) Google-F1 and Facebook-
TAO have $1\,\textrm{M}$ keys with the popular keys randomly distributed to
balance load. We run $3$ trials for each test and $60$ seconds for each trial.
Experiments are CPU-bound (i.e., handling network interrupts).

(a) Google-F1 Workload

(b) Facebook-TAO Workload

(c) TPC-C Workload

Figure 6: NCC achieves much lower latency under read-dominated workloads with
its specialized read-only transaction algorithm, 50% lower latency under
write-intensive workload, and at least $\mathbf{80\%}$ higher throughput
across workloads.

###  5.2 Result Overview

NCC outperforms strictly serializable protocols dOCC, d2PL, and TR (Janus-CC)
by $80\%$–$20\times$ higher throughput and $2$–$10\times$ lower latency under
various workloads (Figure 6) and write fractions (Figure 7(a)). NCC
outperforms and closely matches serializable systems, TAPIR-CC and MVTO,
respectively (Figure 7(b)). NCC recovers from client failures with minimal
performance impact (Figure 7(c)). Please note that Figure 6 and Figure 7(b)
have log-scale axes. Figure 5 summarizes the takeaway of performance
improvements.

###  5.3 Latency vs. Throughput Experiments

Figure 6 shows NCC’s overall performance is strictly better than the
baselines, i.e., higher throughput with the same latency and lower latency
with the same throughput.

#### Google-F1 and Facebook-TAO.

Figure 6(a) shows the results under Google-F1. X-axis is the system
throughput, and y-axis shows the median read latency in log scale. A
horizontal line (O.P.) marks the operating point with reasonably low latency
($<10\,\textrm{ms}$). At the operating point, NCC has a $2$–$4\times$ higher
throughput than dOCC and d2PL. We omit the results for Janus-CC to make the
graph clearer as we found that Janus-CC’s performance is incomparable
(consistently worse) with other baselines, because Janus-CC is designed for
highly contended workloads by relying on heavy dependency tracking, which is
more costly under low contention.

NCC has better performance because Google-F1 and Facebook-TAO are read-
dominated and thus have few conflicts, making most of their transactions
naturally consistent. NCC enables low overhead by leveraging natural
consistency. In particular, its read-only transaction protocol executes the
dominating reads with the minimum costs (Figure 5). For instance, at the
operating point, NCC has about $99\%$ of the transactions that passed their
safeguard check and finished in one round trip. $99.1\%$ of the transactions
did not delay their responses, i.e., the real-time order dependencies were
already satisfied when they arrived. That is, $99\%$ of the transactions were
finished by NCC within a single RTT without any delays. For the $1\%$ of the
transactions that did not pass the safeguard check initially, $70\%$ of them
passed the smart retry. Only $0.2\%$ of the transactions were aborted and
retried from scratch. All of them were committed eventually.

As a result, NCC can finish most transactions with one round of messages (for
the read-only ones) and a latency of one RTT (for both read-only and read-
write) while dOCC and d2PL-wound-wait require three rounds of messages and a
latency of two RTTs (asynchronous commitment saves one RTT). NCC has much
higher throughput than d2PL-no-wait due to its novel read-only protocol that
requires one round of messages, while d2PL-no-wait requires two. The fewer
messages of NCC translate to much lower latency under medium and high load due
to lower queuing delay. d2PL-no-wait performs similar to NCC-RW because NCC-RW
executes read-only transactions by following its read-write protocol. However,
NCC-RW outperforms d2PL-no-wait under higher load because conflicts cause
d2PL-no-wait to abort more frequently while NCC-RW has fewer false aborts by
leveraging the natural arrival order. This is more obvious in the Facebook-TAO
results as shown in Figure 6(b) because Facebook-TAO has much larger read
transactions that are more likely to conflict with writes. The results of
Facebook-TAO demonstrate similar takeaways.

(a) Varying Write Fractions

(b) Weaker Serializability

(c) Failure Recovery

Figure 7: NCC performance with different write fractions (Google-WF), compared
to serializable protocols (TAPIR-CC and MVTO), and under failures for the
Google-F1 workload.

#### TPC-C.

Each experiment ran all five types of TPC-C transactions, and Figure 6(c)
shows the latency and throughput (both in log scale) of New-Order while the
throughput of the other four types is proportional. NCC and NCC-RW have
$\sim$$20\times$ higher peak throughput with $\sim$$10\times$ lower latency
compared to dOCC. dOCC and d2PL-no-wait have many false aborts when load
increases due to conflicting writes. NCC and NCC-RW can execute most naturally
consistent transactions with low costs, even if they conflict. For instance,
NCC-RW has more than $80\%$ of the transactions that passed the safeguard
check and fewer than $10\%$ of the transactions that were aborted and retried
from scratch. NCC-RW has a $50\%$ higher peak throughput than d2PL-wound-wait
because NCC-RW requires only two rounds of messages, while d2PL-wound-wait
requires three. NCC-RW has higher peak throughput than NCC because TPC-C has
very few read-only transactions, which are also more likely to abort in NCC
due to conflicting writes. Janus-CC’s performance benefits mostly come from
unifying the transaction and replication layers and are less significant in a
single-datacenter setting, especially after we made some TPC-C transactions
multi-shot.

###  5.4 Additional Experiments

We show more experiments with Google-F1. We choose Google-F1 because it has
both read-write and read-only transactions while Facebook-TAO only has read-
only transactions.

#### Varying write fractions.

Figure 7(a) shows the throughput when we increase the write fraction up to
$30\%$. Each system is ran at $\sim$$75\%$ load according to Figure 6(a). The
y-axis is the throughput normalized to the maximum throughput of each system
during the experiment. The higher write fraction, the more conflicts in the
system. The results show that the NCC-RW is most resilient to conflict
increases because NCC-RW can exploit more concurrency in those conflicting but
naturally consistent transactions, i.e., NCC has fewer aborts. In contrast,
other protocols may falsely abort transactions due to failed validation (dOCC)
or lock unavailability (d2PL variants). NCC’s read-only transactions are more
likely to abort when writes increase because frequent writes cause the client
to have stale knowledge of the most recently executed writes on each server;
as a result, NCC must abort the reads to avoid timestamp-inversion.

#### Comparing with serializable systems.

Figure 7(b) compares NCC with MVTO and TAPIR-CC which provide serializability,
under Google-F1. NCC outperforms TAPIR-CC because NCC has fewer messages with
its read-only transaction protocol. MVTO and NCC have similar performance
under low and medium load because they have the same number of messages and
RTTs. Under high load, MVTO outperforms NCC when many read-only transactions
in NCC are aborted, while MVTO never aborts reads because it is allowed to
read stale versions while NCC must read the most recent version and handle
timestamp-inversion. That is, MVTO presents a performance upper bound for
strictly serializable systems, and NCC closely matches the upper bound.

#### Failure recovery.

Figure 7(c) shows how well NCC-RW handles client failures under Google-F1. We
inject failures after $10$ seconds into the experiment by forcing _all_
clients to stop sending the commit messages of ongoing transactions and keep
issuing new transactions. Undelivered commit messages cause servers to delay
the responses of later transactions due to response timing control until the
recovery mechanism is triggered after a timeout. We show two timeout values,
$1$ and $3$ seconds. NCC-RW recovers quickly after failures are detected,
which have limited impact on throughput. In many realistic settings, failures
on one or a few clients would have negligible impact because uncommitted reads
do not block other reads. Similarly, NCC is minimally impacted by client
failures because its read-only transactions do not send commit messages and
thus never delay later writes.

##  6 Related Work

NCC proposes a new strictly serializable distributed protocol. Thus, this
section places it in the context of existing strictly serializable techniques,
single-machine concurrency control, and techniques that provide weaker
consistency. At a high-level, NCC provides better performance, addresses a
different problem setting, and provides stronger guarantees, compared to these
categories of work, respectively.

System | Consistency | Technique | Latency (RTT) | Lock-free | No-Waiting | False Abort
---|---|---|---|---|---|---
NCC | Strict Ser. | NaC+TS | $1$ | Yes | Yes | Low
Spanner [12] | Strict Ser. | d2PL+TrueTime |  RO: $1$, RW: $2$ |  RO: Yes, RW: No | No |  RO: None, RW: Med
d2PL-NoWait | Strict Ser. | d2PL | $1$ | No | Yes | High
AOCC [2] | Strict Ser. | dOCC | $2$ | Yes | Yes | High
Janus [49] | Strict Ser. | TR | $2$ | Yes | No | None
dOCC | Strict Ser. | dOCC | $2$ | No | Yes | High
d2PL-WoundWait | Strict Ser. | d2PL | $2$ | No | Yes | Med
FaRMv2 [56] | Strict Ser. | dOCC | $2$ | No | No | Med
TAPIR [70] | Ser. | dOCC+TS | $1$ | Yes | Yes | Med
DrTM [64] | Ser. | RO: TS, RW: d2PL |  RO: $2$, RW: $3$ |  RO: Yes, RW: No | Yes | Med
TO [8] | Ser. | TS | $1$ | Yes | Yes | Med
MVTO [53] | Ser. | TS | $1$ | Yes | Yes | Low
Figure 8: The consistency and best-case performance of representative
distributed protocols for naturally consistent workloads, processing one-shot
transactions with all possible optimizations considered, e.g., asynchronous
commitment and phase combination. NC means natural consistency, and TS means
timestamp-based technique. NCC has the lowest performance costs while
providing strict serializability.

#### General strictly serializable protocols.

As discussed in Section 2.3, existing general strictly serializable protocols
are d2PL, dOCC, TR, or their variants, suffering extra costs when transactions
are naturally consistent. For instance, Spanner’s read-write transactions
[12], Sinfonia [4], and Carousel [66] are variants of d2PL that must acquire
locks. FaRM [15], FaRMv2 [56], RIFL [30] are variants of dOCC that suffer
extra validation costs, even if they use timestamp-based techniques to reduce
validation aborts. AOCC [2] is a variant of dOCC and employs a data-shipping
model to improve performance, e.g., it periodically sends data from servers to
client caches, which is different from NCC’s function-shipping model, e.g., it
only controls the execution and does not migrate data. Rococo [48] and its
descendant Janus [49] reorder transactions to minimize aborts. Similarly,
Granola [13] requires an all-to-all exchange of timestamps between servers,
incurring extra messages and RTTs. Our evaluation shows that NCC outperforms
these techniques for real-world workloads where natural consistency is
prevalent. When transactions are not naturally consistent, however, these
techniques could outperform NCC. NCC achieves better performance by exploiting
natural consistency. Figure 8 summarizes performance and consistency
properties of NCC and some representative distributed systems.

#### Special strictly serializable techniques.

Some work utilizes a centralized sequencer to enforce strict serializability
[32, 60, 19, 7, 43, 35, 54, 71]. Because all transactions must contact the
sequencer before execution (e.g., Eris [32]), besides the extra latency, the
sequencer often becomes a single point of failure and scalability bottleneck.
Scaling out sequencers incurs extra costs, e.g., Calvin [60] requires all-to-
all messages among sequencers for each transaction (epoch). Some ensure strict
serializability by moving all data a transaction accesses to the same machine,
e.g., LEAP [34]. Some rely on program analysis and are application-dependent,
e.g., the homeostasis protocol [55]. Some rely on extensive gossip messages
for liveness, which lower throughput and increase latency, e.g., Ocean Vista
[18] whose latency of a transaction cannot be lower than the gossiping delay
of the slowest server even if this server is not accessed by the transaction.
General techniques such as NCC do not have the above limitations.

#### Strictly serializable read-only transaction protocols.

To the best of our knowledge, the only existing strictly serializable read-
only transaction protocol that has the optimal best-case performance (e.g.,
one-round of non-blocking messages with constant metadata) is Spanner [12].
Spanner ensures strict serializability by using d2PL for read-write
transactions and by using synchronized clocks (TrueTime) for read-only
transactions. TrueTime must be tightly bounded for both correctness and
performance, which is achieved by Google’s infrastructure using special
hardware, e.g., GPS and atomic clocks [10] that are not generally available.
For instance, CockroachDB [59], which began as an external Spanner clone,
chose not to support strict serializability because it does not have access to
such infrastructure [25]. In contrast, NCC’s read-only transactions achieve
optimal best-case performance and provide strict serializability, without
requiring synchronized clocks.

#### Single-machine concurrency control.

Concurrency control for single-machine databases is different from the
distributed setting on which this paper focuses. First, some techniques are
not feasible in a distributed setting. For instance, Silo [62] relies on
atomic instructions, and MVTL [3] relies on shared lock state, which are
challenging across machines. Second, most techniques, e.g., Silo [62] and
TicToc [67], follow a multi-phase design and would be expensive if made
distributed, e.g., they need one round of inter-machine messages for each
phase and distributed lock management, which would be unnecessary costs for
naturally consistent transactions.

#### Protocols for weaker consistency.

Many systems trade strong consistency for better performance. For instance,
some settle for restricted transaction APIs, e.g., read-only and/or write-only
transactions [37, 36, 16]. Some choose to support weaker consistency models,
e.g., causal consistency and serializability [37, 59, 17, 63, 68, 44, 38, 31].
In contrast, NCC provides stronger consistency and supports general
transactions, greatly simplifying application development.

##  7 Conclusion

Strictly serializable datastores are advocated for simplifying application
development and reducing consistency anomalies. This paper presents NCC, a new
design that provides strict serializability with minimal overhead by
leveraging natural consistency in datacenter workloads. NCC identifies
timestamp-inversion, a fundamental correctness pitfall into which several
existing works have fallen. NCC significantly outperforms existing strictly
serializable techniques and closely matches the performance of serializable
systems.

## References

  * [1] Atul Adya.  Weak consistency: a generalized theory and optimistic implementations for distributed transactions.  PhD thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 1999.
  * [2] Atul Adya, Robert Gruber, Barbara Liskov, and Umesh Maheshwari.  Efficient optimistic concurrency control using loosely synchronized clocks.  ACM SIGMOD Record, 24(2):23–34, 1995.
  * [3] Marcos K Aguilera, Tudor David, Rachid Guerraoui, and Junxiong Wang.  Locking timestamps versus locking objects.  In ACM Symposium on Principles of Distributed Computing (PODC), 2018\.
  * [4] Marcos K. Aguilera, Arif Merchant, Mehul Shah, Alistair Veitch, and Christos Karamanolis.  Sinfonia: A new paradigm for building scalable distributed systems.  In ACM Symposium on Operating System Principles (SOSP), 2007.
  * [5] Phillipe Ajoux, Nathan Bronson, Sanjeev Kumar, Wyatt Lloyd, and Kaushik Veeraraghavan.  Challenges to adopting stronger consistency at scale.  In Workshop on Hot Topics in Operating Systems (HotOS), May 2015\.
  * [6] InfiniBand Trade Association.  Infiniband architecture specification, release 1.0, october 2000.  http://www.infinibandta.org/, 2000.
  * [7] Mahesh Balakrishnan, Dahlia Malkhi, Vijayan Prabhakaran, Ted Wobbler, Michael Wei, and John D Davis.  CORFU: A shared log design for flash clusters.  In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2012.
  * [8] Philip A Bernstein and Nathan Goodman.  Concurrency control in distributed database systems.  ACM Computing Surveys (CSUR), 13(2):185–221, 1981.
  * [9] Google Cloud Blog.  Why you should pick strong consistency, whenever possible.  https://cloud.google.com/blog/products/databases/why-you-should-pick-strong-consistency-whenever-possible, 2018\.
  * [10] Eric Brewer.  Spanner, TrueTime and the CAP theorem.  Technical report, Google Research, 2017.
  * [11] Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani.  TAO: Facebook’s distributed data store for the social graph.  In USENIX Annual Technical Conference (ATC), Jun 2013.
  * [12] James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman andSanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford.  Spanner: Google’s globally-distributed database.  In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2012.
  * [13] James Cowling and Barbara Liskov.  Granola: Low-overhead distributed transaction coordination.  In USENIX Annual Technical Conference (ATC), Jun 2012.
  * [14] DPDK.  DPDK.  http://dpdk.org/, 2020.
  * [15] Aleksandar Dragojevic, Dushyanth Narayanan, Edmund B. Nightingale, Matthew Renzelmann, Alex Shamis, Anirudh Badam, and Miguel Castro.  No compromises: distributed transactions with consistency, availability, and performance.  In ACM Symposium on Operating System Principles (SOSP), Oct 2015\.
  * [16] Jiaqing Du, Sameh Elnikety, Amitabha Roy, and Willy Zwaenepoel.  Orbe: Scalable causal consistency using dependency matrices and physical clocks.  In ACM Symposium on Cloud Computing (SoCC), 2013.
  * [17] Amazon DynamoDB.  Amazon DynamoDB :: Fast and flexible NoSQL database service for any scale.  http://aws.amazon.com/dynamodb/, 2021.
  * [18] Hua Fan and Wojciech Golab.  Ocean Vista: Gossip-based visibility control for speedy geo-distributed transactions.  Proceedings of the VLDB Endowment (PVLDB), 12(11):1471–1484, 2019\.
  * [19] FaunaDB.  FaunaDB :: The data API for your client-serverless applications.  https://fauna.com/, 2021.
  * [20] Hector Garcia-Molina and Kenneth Salem.  Main memory database systems: An overview.  IEEE Transactions on knowledge and data engineering, 4(6):509–516, 1992.
  * [21] David K. Gifford.  Information storage in a decentralized computer system.  PhD thesis, Stanford University, Department of Electrical Engineering, 1981.
  * [22] Matthew P Grosvenor, Malte Schwarzkopf, Ionel Gog, Robert NM Watson, Andrew W Moore, Steven Hand, and Jon Crowcroft.  Queues don’t matter when you can JUMP them!  In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2015.
  * [23] Maurice P. Herlihy and Jeannette M. Wing.  Linearizability: A correctness condition for concurrent objects.  ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463–492, 1990.
  * [24] Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alexander Rasin, Stanley Zdonik, Evan PC Jones, Samuel Madden, Michael Stonebraker, Yang Zhang, John Hugg, and Daniel J. Abadi.  H-store: A high-performance, distributed main memory transaction processing system.  Proceedings of the VLDB Endowment (PVLDB), 1(2):1496–1499, 2008\.
  * [25] Spencer Kimball and Irfan Sharif.  Living without atomic clocks.  https://www.cockroachlabs.com/blog/living-without-atomic-clocks/, 2021.
  * [26] Kishori M Konwar, Wyatt Lloyd, Haonan Lu, and Nancy Lynch.  SNOW revisited: Understanding when ideal read transactions are possible.  In IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2021.
  * [27] Tim Kraska, Gene Pang, Michael J Franklin, Samuel Madden, and Alan Fekete.  MDCC: Multi-data center consistency.  In ACM SIGOPS European Conference on Computer Systems (EuroSys), 2013.
  * [28] Leslie Lamport.  The part-time parliament.  ACM Transactions on Computer Systems (TOCS), 16(2):133–169, 1998\.
  * [29] Leslie Lamport.  Paxos made simple.  ACM SIGACT News, 32(4):18–25, 2001.
  * [30] Collin Lee, Seo Jin Park, Ankita Kejriwal, Satoshi Matsushitay, and John Ousterhout.  Implementing linearizability at large scale and low latency.  In ACM Symposium on Operating System Principles (SOSP), 2015.
  * [31] Justin Levandoski, David Lomet, Sudipta Sengupta, Ryan Stutsman, and Rui Wang.  High performance transactions in deuteronomy.  In Conference on Innovative Data Systems Research (CIDR), 2015.
  * [32] Jialin Li, Ellis Michael, and Dan RK Ports.  Eris: Coordination-free consistent transactions using in-network concurrency control.  In ACM Symposium on Operating System Principles (SOSP), 2017.
  * [33] Kai Li and Jeffrey F Naughton.  Multiprocessor main memory transaction processing.  In Proceedings International Symposium on Databases in Parallel and Distributed Systems, pages 177–178. IEEE Computer Society, 1988.
  * [34] Qian Lin, Pengfei Chang, Gang Chen, Beng Chin Ooi, Kian-Lee Tan, and Zhengkui Wang.  Towards a non-2PC transaction management in distributed database systems.  In ACM Special Interest Group on Management of Data (SIGMOD), 2016\.
  * [35] Yu-Shan Lin, Shao-Kan Pi, Meng-Kai Liao, Ching Tsai, Aaron Elmore, and Shan-Hung Wu.  MgCrab: Transaction crabbing for live migration in deterministic database systems.  Proceedings of the VLDB Endowment (PVLDB), 12(5):597–610, 2019\.
  * [36] Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen.  Don’t settle for eventual: Scalable causal consistency for wide-area storage with COPS.  In ACM Symposium on Operating System Principles (SOSP), 2011.
  * [37] Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen.  Stronger semantics for low-latency geo-replicated storage.  In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2013.
  * [38] David Lomet, Alan Fekete, Rui Wang, and Peter Ward.  Multi-version concurrency via timestamp range conflict management.  In IEEE International Conference on Data Engineering (ICDE), 2012\.
  * [39] Haonan Lu, Christopher Hodsdon, Khiem Ngo, Shuai Mu, and Wyatt Lloyd.  The SNOW theorem and latency-optimal read-only transactions.  In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2016.
  * [40] Haonan Lu, Siddhartha Sen, and Wyatt Lloyd.  Performance-optimal read-only transactions.  In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020.
  * [41] Haonan Lu, Siddhartha Sen, and Wyatt Lloyd.  Performance-optimal read-only transactions (extended version).  Technical report, TR-005-20 v1, Princeton University, Department of Computer Science, 2020.
  * [42] Haonan Lu, Kaushik Veeraraghavan, Philippe Ajoux, Jim Hunt, Yee Jiun Song, Wendy Tobagus, Sanjeev Kumar, and Wyatt Lloyd.  Existential consistency: Measuring and understanding consistency at Facebook.  In ACM Symposium on Operating System Principles (SOSP), Oct 2015\.
  * [43] Yi Lu, Xiangyao Yu, Lei Cao, and Samuel Madden.  Aria: A fast and practical deterministic OLTP database.  Proceedings of the VLDB Endowment (PVLDB), 13(12):2047–2060, 2020\.
  * [44] Hatem A Mahmoud, Vaibhav Arora, Faisal Nawab, Divyakant Agrawal, and Amr El Abbadi.  MaaT: Effective and scalable coordination of distributed transactions in the cloud.  Proceedings of the VLDB Endowment (PVLDB), 7(5):329–340, 2014.
  * [45] Microsoft.  Microsoft Azure :: New challenges need agile solutions. Invent with purpose.  https://azure.microsoft.com/en-us/, 2020.
  * [46] Radhika Mittal, Vinh The Lam, Nandita Dukkipati, Emily Blem, Hassan Wassel, Monia Ghobadi, Amin Vahdat, Yaogong Wang, David Wetherall, and David Zats.  Timely: RTT-based congestion control for the datacenter.  ACM SIGCOMM Computer Communication Review, 45(4):537–550, 2015\.
  * [47] Behnam Montazeri, Yilong Li, Mohammad Alizadeh, and John Ousterhout.  Homa: A receiver-driven low-latency transport protocol using network priorities.  In ACM Special Interest Group on Data Communication (SIGCOMM), 2018\.
  * [48] Shuai Mu, Yang Cui, Yang Zhang, Wyatt Lloyd, and Jinyang Li.  Extracting more concurrency from distributed transactions.  In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2014.
  * [49] Shuai Mu, Lamont Nelson, Wyatt Lloyd, and Jinyang Li.  Consolidating concurrency control and consensus for commits under conflicts.  In USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2016.
  * [50] Ruoming Pang, Ramon Caceres, Mike Burrows, Zhifeng Chen, Pratik Dave, Nathan Germer, Alexander Golynski, Kevin Graney, Nina Kang, Lea Kissner, Jeffrey L. Korn, Abhishek Parmar, Christina D. Richards, and Mengzhi Wang.  Zanzibar: Google’s consistent, global authorization system.  In USENIX Annual Technical Conference (ATC), 2019.
  * [51] Christos H. Papadimitriou.  The serializability of concurrent database updates.  Journal of the ACM, 26(4), 1979.
  * [52] Costin Raiciu and Gianni Antichi.  NDP: Rethinking datacenter networks and stacks two years after.  ACM SIGCOMM Computer Communication Review, 49(5):112–114, 2019\.
  * [53] David P Reed.  Implementing atomic actions on decentralized data.  ACM Transactions on Computer Systems (TOCS), 1(1):3–23, 1983.
  * [54] Kun Ren, Dennis Li, and Daniel J Abadi.  SLOG: Serializable, low-latency, geo-replicated transactions.  Proceedings of the VLDB Endowment (PVLDB), 12(11):1747–1761, 2019\.
  * [55] Sudip Roy, Lucja Kot, Gabriel Bender, Bailu Ding, Hossein Hojjat, Christoph Koch, Nate Foster, and Johannes Gehrke.  The homeostasis protocol: Avoiding transaction coordination through program analysis.  In ACM Special Interest Group on Management of Data (SIGMOD), 2015\.
  * [56] Alex Shamis, Matthew Renzelmann, Stanko Novakovic, Georgios Chatzopoulos, Aleksandar Dragojević, Dushyanth Narayanan, and Miguel Castro.  Fast general distributed transactions with opacity.  In ACM Special Interest Group on Management of Data (SIGMOD), 2019\.
  * [57] Jeff Shute, Radek Vingralek, Bart Samwel, Ben Handy, Chad Whipkey, Eric Rollins, Mircea Oancea, Kyle Littlefield, David Menestrina, Stephan Ellner, John Cieslewicz, Ian Rae, Traian Stancescu, and Himani Apte.  F1: A distributed SQL database that scales.  Proceedings of the VLDB Endowment (PVLDB), 2013.
  * [58] Michael Stonebraker, Samuel Madden, Daniel J Abadi, Stavros Harizopoulos, Nabil Hachem, and Pat Helland.  The end of an architectural era: It’s time for a complete rewrite.  In Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker, pages 463–489. 2018.
  * [59] Rebecca Taft, Irfan Sharif, Andrei Matei, Nathan VanBenschoten, Jordan Lewis, Tobias Grieger, Kai Niemi, Andy Woods, Anne Birzin, Raphael Poss, Paul Bardea, Amruta Ranade, Ben Darnell, Bram Gruneir, Justin Jaffray, Lucy Zhang, and Peter Mattis.  CockroachDB: The resilient geo-distributed SQL database.  In ACM Special Interest Group on Management of Data (SIGMOD), 2020\.
  * [60] Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, and Daniel J. Abadi.  Calvin: Fast distributed transactions for partitioned database systems.  In ACM Special Interest Group on Management of Data (SIGMOD), 2012\.
  * [61] TPC.  TPC-C: An on-line transaction processing benchmark.  http://www.tpc.org/tpcc/, 2020.
  * [62] Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden.  Speedy transactions in multicore in-memory databases.  In ACM Symposium on Operating System Principles (SOSP), 2013.
  * [63] Xingda Wei, Rong Chen, Haibo Chen, Zhaoguo Wang, Zhenhan Gong, and Binyu Zang.  Unifying timestamp with transaction ordering for MVCC with decentralized scalar timestamp.  In USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2021.
  * [64] Xingda Wei, Jiaxin Shi, Yanzhe Chen, Rong Chen, and Haibo Chen.  Fast in-memory transaction processing using RDMA and HTM.  In ACM Symposium on Operating System Principles (SOSP), 2015.
  * [65] Arthur Whitney, Dennis Shasha, and Stevan Apter.  High volume transaction processing without concurrency control, two phase commit, SQL or C++, 1997.
  * [66] Xinan Yan, Linguan Yang, Hongbo Zhang, Xiayue Charles Lin, Bernard Wong, Kenneth Salem, and Tim Brecht.  Carousel: Low-latency transaction processing for globally-distributed data.  In ACM Special Interest Group on Management of Data (SIGMOD), 2018\.
  * [67] Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas.  TicToc: Time traveling optimistic concurrency control.  In ACM Special Interest Group on Management of Data (SIGMOD), 2016\.
  * [68] Xiangyao Yu, Yu Xia, Andrew Pavlo, Daniel Sanchez, Larry Rudolph, and Srinivas Devadas.  Sundial: Harmonizing concurrency control and caching in a distributed OLTP database management system.  In Proceedings of the VLDB Endowment (PVLDB), 2018.
  * [69] Irene Zhang, Naveen Kr. Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan R. K. Ports.  Building consistent transactions with inconsistent replication.  In ACM Symposium on Operating System Principles (SOSP), 2015.
  * [70] Irene Zhang, Naveen Kr Sharma, Adriana Szekeres, Arvind Krishnamurthy, and Dan RK Ports.  Building consistent transactions with inconsistent replication.  ACM Transactions on Computer Systems (TOCS), 35(4):1–37, 2018.
  * [71] Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton, Andrew J Beamon, Rusty Sears, John Leach, Dave Rosenthal, Xin Dong, Will Wilson, Ben Collins, David Scherer, Alec Grieser, Young Liu, Alvin Moore, Bhaskar Muppana, Xiaoge Su, and Vishesh Yadav.  FoundationDB: A distributed unbundled transactional key value store.  In ACM Special Interest Group on Management of Data (SIGMOD), 2021\.