Natto：Providing Distributed Transaction Prioritization for High-Contention Workloads.pdf

Bigbig

257

15页

3次

2022-07-20

免费下载

Nao: Providing Distributed Transaction Prioritization for

High-Contention Workloads

Linguan Yang

l69yang@uwaterloo.ca

University of Waterloo

Xinan Yan

xinan.yan@uwaterloo.ca

University of Waterloo

Bernard Wong

bernard@uwaterloo.ca

University of Waterloo

ABSTRACT

This paper introduces Natto, a geo-distributed database system that

supports transaction prioritization. Instead of having each shard

process transactions in their arrival order, Natto leverages network

measurements to estimate the transaction arrival time at each shard,

and assigns a timestamp to the transaction based on its arrival time

to the furthest shard. These timestamps establish a global ordering

of transactions, and introduces opportunities to selectively abort

pending low-priority transactions that conict with a high-priority

transaction, or even preempt transactions that are already partially

prepared. Our experiments on both Microsoft Azure and a local

cluster show that Natto’s tail latency for high-priority transactions

are signicantly lower than the tail latencies of Carousel and TAPIR,

which are the current state-of-the-art in geo-distributed transaction

processing systems.

CCS CONCEPTS

• Information systems → Distributed database transactions.

KEYWORDS

transaction prioritization, geo-distributed transactions

ACM Reference Format:

Linguan Yang, Xinan Yan, and Bernard Wong. 2022. Natto: Providing Dis-

tributed Transaction Prioritization for High-Contention Workloads. In Pro-

ceedings of the 2022 International Conference on Management of Data (SIG-

MOD ’22), June 12–17, 2022, Philadelphia, PA, USA. ACM, New York, NY,

USA, 15 pages. https://doi.org/10.1145/3514221.3526161

1 INTRODUCTION

Priority-based scheduling is critically important for database sys-

tems that process dierent classes of transactions. By assigning

a high priority to a time-sensitive transaction, the transaction’s

completion time should largely be unaected by concurrent low-

priority batch transactions. In a single-server database system, pri-

ority scheduling is relatively straightforward to implement. Most

implementations create a separate queue per priority level and

process transactions starting from the highest priority queue. In-

progress transactions can optionally be preempted to further reduce

the wait time for a high-priority transaction.

Permission to make digital or hard copies of all or part of this work for personal or

classroom use is granted without fee provided that copies are not made or distributed

for prot or commercial advantage and that copies bear this notice and the full citation

on the rst page. Copyrights for components of this work owned by others than the

author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or

republish, to post on servers or to redistribute to lists, requires prior specic permission

and/or a fee. Request permissions from permissions@acm.org.

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

ACM ISBN 978-1-4503-9249-5/22/06.. . $15.00

https://doi.org/10.1145/3514221.3526161

However, this single-server approach for providing priority sche-

duling cannot be easily extended to distributed database systems,

such as Spanner [

] and CockroachDB [

], that process geo-

distributed data. In these systems, data is partitioned and replicated

across datacenters in dierent geographic locations, and transac-

tions are scheduled independently at each data partition. Without

a global view of concurrent transactions, the eectiveness of pri-

ority scheduling is fairly limited. This is because the arrival order

of transactions will often be dierent at each partition. A high-

priority transaction may only be scheduled ahead of a conicting

low-priority transaction for some partitions, resulting in a potential

distributed deadlock that has to be resolved by aborting one or both

transactions. Preemption of partially-prepared transactions is also

generally not supported in these systems due to both the complex-

ity of performing distributed preemption, and the high latency to

conrm that a transaction has successfully been preempted. A high-

priority transaction must wait until conicting partially-prepared

transactions are complete before it can be processed.

Systems with a logically centralized transaction sequencer, such

as Calvin [

] and FaunaDB [

], can be extended to support prior-

ity scheduling as their schedulers are given a complete global view

of the transactions in the system by their sequencers. However,

employing such a sequencer introduces an extra wide-area network

round trip to process a transaction, which is unacceptable for some

time-sensitive transactions. These systems also introduce other

restrictions, such as requiring transactions to be non-interactive

and deterministic, making them unsuitable for certain classes of

transactions.

In this paper, we introduce Natto, a geo-distributed database

system that can signicantly reduce the tail latency of high-priority

transactions through transaction prioritization. Natto builds on the

Carousel [

] database system in which data is partitioned and

stored at the datacenter where it will most frequently be used. Parti-

tions are also replicated using Raft [

] to additional datacenters to

provide fault tolerance. Similar to Carousel, Natto targets 2-round

Fixed-set Interactive (2FI) transactions, where each transaction con-

sists of a read round followed by a write round, the read and write

sets are known at the start of the transaction but the write values

can depend on the read results, and users can choose to abort their

transactions after the rst round.

Natto introduces or extends several techniques that build on

each other to provide eective and ecient transaction prioritiza-

tion. First, it uses network measurements from clients to servers

to accurately estimate the arrival time of a transaction at the par-

ticipating Natto servers. Each transaction is assigned a timestamp

based on its estimated arrival time at the furthest participanting

server, and the transaction is not processed on any server until that

time. This approach was rst introduced in Domino [

] for use

Session 10: Distributed and Parallel Databases

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

715

in state machine replication. Natto extends it to establish a global

ordering of transactions without the need for a logically centralized

sequencer or coordination messages between servers. Even though

a transaction is not processed immediately on nearby servers, its

completion time does not increase since the second round of the

transaction cannot start until the client receives all of the results

from the rst round, including the result from the furthest server.

Using this approach, Natto does not acquire resources prematurely,

and its transactions cannot deadlock as the global ordering prevents

cyclic dependencies.

Although the Natto servers agree on the ordering of transactions,

each server only receives transactions that read and/or write to

its partition. Therefore, they cannot unilaterally schedule a high-

priority transaction ahead of a low-priority transaction without

potentially introducing a distributed deadlock. However, for a given

transaction, all servers other than the furthest one from the client

will receive the transaction before its execution time. This creates

an abort window at these servers during which time the transaction

has been received but may still be aborted if it conicts with a

new high priority transaction. This abort window comes out of our

use of arrival time-based execution timestamps, and gives Natto

an opportunity to perform a priority abort of a low priority trans-

actions that can interfere with high priority transactions without

introducing any delays when there are no conicts.

Additionally, each Natto transaction embeds its estimated trans-

action arrival time to all of the participating servers. Without this

information, if a high priority transaction arrives at a Natto server

that conicts with an already prepared low priority transaction,

the high priority transaction must wait until the low priority trans-

action completes even if the low priority transaction is eventually

aborted. However, by having the arrival time information to all

participating servers for its received transactions, a Natto server

can in some cases know that a prepared low-priority transaction

will likely be aborted. With this knowledge, it can send a condi-

tional prepare message to the 2PC coordinator, which prepares the

high-priority transaction before the server receives an abort ac-

knowledgement for the conicting transaction. This conditional

prepare will be successful if the conicting low-priority transac-

tion is aborted. Otherwise, Natto will safely discard the conditional

prepare results and prepare the high-priority transaction after the

conicting transaction completes successfully.

Finally, in the Carousel protocol, results from a committed trans-

action are not visible to other transactions until they have been

replicated to a majority of the replicas. This is necessary since, in

the event of a replication group failure, committed transactions

that have not been replicated must be replayed, and a Carousel

server cannot determine the ordering of multiple transactions in

this state. With the availability of transaction timestamps, Natto

can determine the order of transactions in the committed but not

yet replicated state. This allows Natto to introduce Early Committed

State Forwarding (ECSF) that allows a transaction to read committed

results that have not been replicated. ECSF signicantly reduces

lock contention by reducing the amount of time that a transaction

needs to hold a lock by one wide-area network roundtrip. This

signicantly reduces the latency of both high and low-priority

transactions for high-contention workloads.

This paper makes three main contributions:

•

We describe the use of network measurements to establish a

global ordering of transactions based on transaction arrival

time. We use this ordering to identify and selectively abort

low-priority transactions that would delay the processing of

a high-priority transaction.

•

We introduce conditional prepare and early committed result

forwarding, which allow Natto to further overlaps operations

that are performed sequentially in previous systems.

•

We evaluate Natto using the Smallbank [

], Retwis [

] and YCSB+T [

] on both an Microsoft Azure deploy-

ment and a local cluster. Our results show that Natto has

signicantly lower tail latency for high-priority transactions

compared to Carousel [53] and TAPIR [54].

2 BACKGROUND

We design Natto on top of Carousel [53], a transaction processing

system for globally distributed data. Unlike Carousel that processes

transactions in their arrival order, Natto introduces a timestamp-

based ordering to support transaction prioritization. Natto assigns a

timestamp to each transaction, where the timestamp indicates when

the transaction should have arrived at all participants. To estimate

a transaction’s arrival time at participants, Natto uses techniques

introduced in Domino [

]. This section will rst briey review

Carousel, and then describe the techniques that Natto borrows from

Domino for estimating a transaction’s arrival time at participants.

2.1 Carousel

Similar to many other geo-distributed database systems, such as

Google Spanner [

] and CockroachDB [

], Carousel shards data

into partitions to achieve scalability, and replicates each partition

in dierent datacenters to tolerate datacenter-wide failures. Un-

like other systems, Carousel targets a specic type of read-write

transactions, 2-round Fixed-set Interactive (2FI) transactions [53].

A 2FI transaction consists of one round of reads followed by a

round of writes. Both read and write keys are pre-dened at the

start of a 2FI transaction. However, a client can decide the write

values based on the read results and does not need to modify all

of the keys in the write set. This interactive read-write pattern

between clients and servers is preferred by many applications [

especially in rapid development [

]. The 2FI model can directly

implement common read-modify-write patterns in transactions,

such as reading, incrementing, and updating one or more counter

values. This allows many transactions to t in the 2FI model, in-

cluding transferring balance between user accounts and updating

user proles in web applications.

In order to have low transaction completion time, Carousel lever-

ages the pre-dened read and write keys in 2FI transactions to

overlap transaction processing (i.e., reads and writes) with 2PC

and replication. Figure 1 shows an example of Carousel’s basic

protocol (known as Carousel Basic). In this example, a transaction

accesses two data partitions in dierent datacenters. We only show

the leader of each partition’s replica group for clarity. The client

starts executing the transaction by sending (

○

) read-and-prepare

requests to the two partition leaders. A read-and-prepare request

includes both the read and write keys that the transaction accesses

Session 10: Distributed and Parallel Databases

SIGMOD ’22, June 12–17, 2022, Philadelphia, PA, USA

716

of 15

免费下载

关注

评论