Efficiently Supporting Adaptive Multi-Level Serializability Models in Distributed Database Systems .pdf

onboard

175

3页

3次

2021-11-29

免费下载

Eiciently Supporting Adaptive Multi-Level Serializability

Models in Distributed Database Systems

Zhanhao Zhao

∗

Renmin Univerisity of China

zhanhaozhao@ruc.edu.cn

ABSTRACT

Informally, serializability means that transactions appear to have

occurred in some total order. In this paper, we show that only the se-

rializability guarantee with some total order is not enough for many

real applications. As a complement, extra partial orders of transac-

tions, like real-time order and program order, need to be introduced.

Motivated by this observation, we present a framework that mod-

els serializable transactions by adding extra partial orders, namely

multi-level serializability models. Following this framework, we pro-

pose a novel concurrency control algorithm, called bi-directionally

timestamp adjustment (BDTA), to supporting multi-level serializ-

ability models in distributed database systems. We integrate the

framework and BDTA into Greenplum and Deneva to show the

benets of our work. Our experiments show the performance gaps

among serializability levels and conrm BDTA achieves up to 1.7

better than state-of-the-art concurrency control algorithms.

ACM Reference Format:

Zhanhao Zhao. 2021. Eciently Supporting Adaptive Multi-Level Serial-

izability Models in Distributed Database Systems. In Proceedings of the

2021 International Conference on Management of Data (SIGMOD ’21), June

20–25, 2021, Virtual Event , China. ACM, New York, NY, USA, 3 pages.

https://doi.org/10.1145/3448016.3450579

1 INTRODUCTION

Thus far, almost every major RDBMS is multi-version concurrency

control based to achieve serializability. However, recent studies en-

gendered by decentralized database systems under multi-version

concurrency control show that serializability guarantee could still

lead to stale reads. Take transactions shown in the top part of Fig-

ure 1 as an example. Transaction

starts after

commits, and

creates a new version

of tuple

. A stale read happens since the

read of

returns

but not

. This is possible, due to a lack of a

globally synchronized clock, for a database system to execute

over a state of the database before

exists (e.g.,

’s write cannot

be seen by

since the snapshot of

is less than the commit times-

tamp of

). Strict serializability, in essence, adds a simple additional

constraint, i.e., linearizable consistency [

], which preserves the

real-time order,

≺

, of non-concurrent operations (i.e.,

≺ op

∗

I would like to thank Wei Lu, Haixiang Li and Xiaoyong Du for advising this work

and the following grants: National Natural Science Foundation of China 61972403, and

Tencent Rhino-Bird Joint Research Program.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored.

For all other uses, contact the owner/author(s).

SIGMOD ’21, June 20–25, 2021, Virtual Event , China

ACM ISBN 978-1-4503-8343-1/21/06.

https://doi.org/10.1145/3448016.3450579

Process P

)

Time

)

History

)

Projection

H | T0

)

H | T1

)

H | T2

)

H | T3

)

Equivalent

Sequential History

)

Figure 1: Formulation of Multi-level Serializability

if operation

starts after operation

completes), on top of

serializability to prevent stale reads. That is, strict serializability

guarantees the properties of both serializability and linearizable

consistency hold during the entire execution of transactions.

Except Spanner [

], the majority of NewSQL systems, includ-

ing CockroachDB [

], TiDB [

] and MongoDB [

], do not sup-

port strict serializability. The reason behind this is not the diculty

of the implementation, but the costly overhead to request glob-

ally ordered timestamps to preserve real-time order. Consider that

linearizable consistency is the strongest consistency model in dis-

tributed systems, while a weaker consistency model yields higher

performance. We are therefore motivated to provide a framework to

optimize between the performance and consistency in distributed

database systems based on the requirements of applications.

In this paper, we aim to address the issue of serializability with

multi-level consistency models, which include linearizable consis-

tency (LC), sequential consistency (SC) [

], and causal consistency

(CC) [

], etc. Based on the observation that the consistency model

is dened by selectively preserving certain kind of partial orders

among operations and serializability is dened by preserving certain

kind of total orders among transactions, We rst propose a framework

by re-dening the consistency models in terms of the transaction

granularity rather than the operation granularity. We theoretically

analyze that all possible combinations are limited to serializability

& LC (namely strict serializability), and serializability & SC (namely

sequential serializability), while the other combinations are reduced

to sequential serializability.

Based on the framework, we propose a unied concurrency con-

trol algorithm with various optimizations. We attach each transac-

tion with a timestamp interval (denoted as [LB, UB]), and propose

the bi-directionally timestamp adjustment (BDTA) algorithm to

dynamically tracking the order of transactions by comparing and

coordinating timestamp intervals of transactions. We then integrate

the framework and BDTA into Greenplum [

] to study the system

performance under multi-level serializability models. Besides, we

implement BDTA and state-of-the-art concurrency control algo-

rithms in Deneva [

] to compare BDTA with other algorithms.

The results show BDTA achieves up to 1.7× performance gain.

Graduate Student Research Competition Track Abstract

SIGMOD ’21, June 20–25, 2021, Virtual Event, China

2908

2 FRAMEWORK

We propose a framework to model serializability transactions by

integrating consistency models in distributed systems. Most exist-

ing works [

] focus on the combinations between a weak

isolation level [

] and a weak consistency model [

]. A few works

discuss strict serializability and serializability [

]. Diering

from existing works, we make a systematic analysis of possible

combinations between serializability with consistency models. We

dene multi-level serializability below:

Sequential History.

A history

is sequential if for any two trans-

actions

and

, either the last event of

H |T

precedes the

rst event of

H |T

or the last event of

H |T

precedes the rst event

of H |T

∗

We denote T

→ T

if T

precedes T

in H.

Write Legal.

A sequential history

is write legal if for any

H |x

†

any read of

(

version of

) must immediately follow the

write of x

when excluding all other read events of x in H |x.

Partial Order.

We extend the partial orders introduced by consis-

tency models from the operation granularity to transaction gran-

ularity. Formally, given two transactions

and

, Program

order

≺

if transactions

and

are in the same

process

and the last event of

precedes the rst event of

;

Write-read order

≺

if there exists an operation

and another operation

such that

reads a version

written by

; Casual-related order

≺

if (a)

≺

or (b)

≺

, or they are related by a transitive closure leverag-

ing (a) and/or (b); Real-time order

≺

r t

≺

r t

if the last event

of T

precedes the rst event of T

Multi-level Serializability Modeling.

As shown in Figure 1, given

a history

, we check whether an equivalent history

‡

can be

sequential, write-legal, and can preserve the partial orders required

by a specic serializability level. Following these rules, we propose

the framework by dening strict serializability (SER-L), sequential

serializability (SER-S), and serializability (SER) levels below. Given

a history H, H satises

• SER-L level

is equivalent to some sequential history

which is write legal, with ≺

⊆≺

and ≺

r t

⊆≺

r t

• SER-S level

is equivalent to some sequential history

which is write legal, with ≺

⊆≺

• SER level

if there is a sequential history

, with

|T = H |T

for each T in H, and S

is write legal, with ≺

⊆≺

3 CONCURRENCY CONTROL PROTOCOL

Our BDTA algorithm is multi-version based, and follows the op-

timistic way enhanced with bi-directionally dynamic timestamp

adjustment to do concurrency control.

The main idea of BDTA is described as follows. Firstly, a trans-

action

should preserve partial orders required by the specic

serializability level when

starts. In our algorithm, this property

is guaranteed by snapshot isolation. We generate a snapshot from

either Timestamp Oracle [

] or HLC [

] to preserve the partial

∗

A history

is a nite sequence of operation events generated by transactions. We

assume each process executes transactions sequentially.

H |T

represents the projection

of T

in H , i.e., a sequence of all events in H whose operations are from T

†

H |x

denotes a subsequence of all events in

whose operations executed on item

‡

and

′

are said to be equivalent if for every process

H |P = H

′

H |P

denotes

a subsequence of all events in H whose process names are P .

8 16 32 64 128 256 512

Throughput (10

Txns/s)

# of Threads

SER-L

SER-S

SER-L(1.5ms)

SER-L(5ms)

RC(Default)

(a) Multi-level Serializability

0 20 40 60 80 100

Throughput (10

Txns/s)

% of Read-Write Transactions

MAAT

MVCC

SILO

T/O

SUNDIAL

BDTA

(b) Concurrency Control Evaluations

Figure 2: Verication on Greenplum and Deneva

order required by SER-L or SER-S, respectively. Secondly, a trans-

action

guarantees a total order for timestamp intervals with all

concurrent transactions

when

commits, i.e., for any two con-

current transactions

, T

, we can have either

.U B < T

.LB

.U B < T

.LB

, leading to an order of

→ T

, or

→ T

, respec-

tively. A transaction

aborts if no legal timestamp interval exists,

i.e.,

T .U B < T .LB

. We shall give an example shown in Figure 1

to elaborate on the BDTA mechanism. Focused on transaction

when

enters the validation phase, it detects

has read tuple

with version

, and hence

actively adjusts its timestamp interval

with

to let

.U B < T

.LB

, indicating that

is ordered before

This adjustment is bi-directional, which renes timestamp intervals

of both

and

, to preserve the partial order

→ T

, causing

.U B < T

.LB

. After

passing the validation phase, the commit

timestamp of T

and x

will be assigned with T

.LB.

BDTA algorithm brings the following benets. First, validations

for read-only transactions are eliminated, which bring performance

gain in read-intensive workload compared with single-version

based [

] and other timestamp interval based [

] algo-

rithms. We use timestamp intervals to maintain the order of trans-

actions, which signicantly reduces the network transferring over-

head against dependency graph based algorithms that shue read-

/write set instead [

]. Further, databases equipped with BDTA

can uniformly support SER-L, SER-S, and SER level, which is capa-

ble of running at an appropriate level according to the requirements

of applications.

4 VERIFICATION

As shown in Figure 2(a), we rst verify the performance of multi-

level serializability models. We use the workload-a in YCSB [

] and

vary the network latency when communicating with Timestamp

Oracle. There is an obvious performance gap among dierent net-

works between SER-L (when RTT is set to 1

or 5

) and SER-S

since SER-S does not suer from the increasing network latency.

Besides, BDTA outperforms the default lock-based concurrency

control algorithm which provide the read commited in Greenplum.

In Figure 2(b), we then conrm that BDTA performs up to 1.7

better than the next-best concurrency control algorithm. We use

the same settings provided in [

] and vary the percentage of read-

write transactions. Benets with the transaction reordering ability,

transactions should be aborted in the other algorithms [

31], can be successfully committed in some cases by BDTA.

A transaction

′

is said to be concurrent to

′

starts before

commits and

commits after T starts.

Graduate Student Research Competition Track Abstract

SIGMOD ’21, June 20–25, 2021, Virtual Event, China

2909