SLOG - Serializable, Low-latency, Geo-replicated Transactions.pdf

上善若水

163

15页

7次

2022-05-30

免费下载

SLOG: Serializable, Low-latency, Geo-replicated

Transactions

Kun Ren

eBay Inc

kuren@ebay.com

Dennis Li

UMD College Park

dli12348@umd.edu

Daniel J. Abadi

UMD College Park

abadi@cs.umd.edu

ABSTRACT

For decades, applications deployed on a world-wide scale have

been forced to give up at least one of (1) strict serializability (2)

low latency writes (3) high transactional throughput. In this pa-

per we discuss SLOG: a system that avoids this tradeoff for work-

loads which contain physical region locality in data access. SLOG

achieves high-throughput, strictly serializable ACID transactions

at geo-replicated distance and scale for all transactions submitted

across the world, all the while achieving low latency for transac-

tions that initiate from a location close to the home region for data

they access. Experiments ﬁnd that SLOG can reduce latency by

more than an order of magnitude relative to state-of-the-art strictly

serializable geo-replicated database systems such as Spanner and

Calvin, while maintaining high throughput under contention.

PVLDB Reference Format:

Kun Ren, Dennis Li, and Daniel J. Abadi. SLOG: Serializable, Low-latency,

Geo-replicated Transactions. PVLDB, 12(11): 1747-1761, 2019.

DOI: https://doi.org/10.14778/3342263.3342647

1. INTRODUCTION

Many modern applications replicate data across geographic re-

gions in order to (a) achieve high availability in the event of region

failure and (b) serve low-latency reads to clients spread across the

world. Existing database systems that support geographic replica-

tion force the user to give up one at least one of the following essen-

tial features: (1) strict serializability (2) low-latency writes (3) high

throughput multi-region transactions — even under contention.

(1) Strict serializability [16, 17, 41, 64], in the context of dis-

tributed database systems, implies both strong isolation (one-copy

serializable [10]) and real-time ordering guarantees. More pre-

cisely, concurrent transaction processing must be equivalent to exe-

cuting transactions in a one-copy serial order, S, such that for every

pair of transactions X and Y, if X starts after Y completes, then X

follows Y in S. This implies that all reads within a transaction must

see the value of any writes that committed before the transaction

began, no matter where that write was performed world-wide. Fur-

thermore, if a transaction, A, begins after (in real time) transaction

B completes, no client can see the effect of A without the effect

This work is licensed under the Creative Commons Attribution-

NonCommercial-NoDerivatives 4.0 International License. To view a copy

of this license, visit http://creativecommons.org/licenses/by-nc-nd/4.0/. For

any use beyond those covered by this license, obtain permission by emailing

info@vldb.org. Copyright is held by the owner/author(s). Publication rights

licensed to the VLDB Endowment.

Proceedings of the VLDB Endowment, Vol. 12, No. 11

ISSN 2150-8097.

DOI: https://doi.org/10.14778/3342263.3342647

of B. Strict serializability reduces application code complexity and

bugs, since it behaves like a system that is running on a single ma-

chine processing transactions sequentially [4, 5].

By giving up strict serializability, it is straightforward to achieve

the other two properties mentioned above (low-latency writes and

high multi-region transactional throughput). If reads are allowed

to access stale data, then reads can be served by any replica (which

improves read latency) and replication can be entirely asynchronous

(which improves write latency) . Furthermore, avoiding the multi-

region coordination necessary to enforce strict serializability facil-

itates throughput scalability of distributed database systems [11].

Much research effort has been spent in designing systems that

reduce the consistency level below strict serializability, while still

providing useful guarantees to the application. For example, Dy-

namo [26], Cassandra [47], and Riak [3] use eventual consistency;

PNUTs [20] supports timeline consistency; COPS [51], Eiger [52],

and Contrarian [27] support a variation of causal consistency; Lynx

(Transaction Chains) [95] supports non-strict serializability with

read-your-writes consistency [81]; Walter [77], Jessy [8], and Blot-

ter [56] support variations of snapshot consistency.

(2) Low latency writes. Despite the suitability of these weaker

consistency models for numerous classes of applications, they of-

ten expose applications to potential race condition bugs, and typi-

cally require skilled application programmers. Thus, the demand

for systems that support strict serializability has only increased.

Many recent geo-replicated data stores, including from two of the

three major cloud vendors (Google with several systems [12, 22,

76] and Microsoft with Cosmos DB) support strong consistency

models at least under some conﬁgurations. Spanner [22] is widely

used throughout Google, and is now available in the Google Cloud

for anybody to use. Other examples in industry include TiDB,

comdb2, FaunaDB, and (with a few caveats) CockroachDB and

YugaByte. Examples from the research community include Helios

[59], MDCC [46], Calvin [87], Carousel [93], and TAPIR [94].

Every single one of these above cited strictly serializable systems

pays at least one cross-region round trip (coordination) message to

commit a write transaction. This type of coordination enables strict

serializability, but increases the latency of every write. The farther

apart the regions, the longer it takes to complete a write.

(3) High transaction throughput Cross-region coordination on

every write is not necessary to guarantee strict serializability. If ev-

ery read of a data item is served from the location of the most recent

write to that data item, then there is no need to synchronously repli-

cate writes across regions. For example, if one region is declared

as the master region for a data item ([20, 23, 38, 61, 66, 67]), and

all writes and consistent reads of that data item are directed to this

region, such as done by NuoDB [66, 67] and G-Store [23], then it

is possible to achieve strict serializability along with low latency

1747

10000

20000

30000

40000

50000

60000

70000

80000

90000

0 1 5 10 20 50 100

throughput (txns/sec)

% cross-region transactions

Low contention

High contention

Figure 1: Single-master throughput under contention.

reads and writes — as long as those reads and writes initiate from

a region near the master region for the data being accessed.

Many workloads have a locality in their access patterns. For

example, for applications that revolve around users, the data as-

sociated with a user is heavily skewed to being accessed from the

physical location of that user. Thus, for these workloads, it is possi-

ble to achieve strict serializability and low latency writes. However,

arbitrary transactions may access multiple data items, where each

data item is mastered at a different region. For such transactions,

achieving strict serializability requires coordination across regions.

Existing approaches prevent conﬂicting transactions from running

during this coordination. Cross-region coordination is time con-

suming since messages must be sent over a WAN. Thus, the time

window that conﬂicting transactions cannot run is large, which re-

duces system throughput. For example, we implemented a version

of NuoDB

, and ran some benchmarks (see Section 4) where we

varied the contention level and percentage of multi-region transac-

tions. As shown in Figure 1, under high contention, the through-

put of the system dropped dramatically at even low percentages

of multi-region transactions, and also fell (although less dramati-

cally) at low contention. For this reason, many systems that allow

different data to be controlled by different regions do not support

multi-region transactions, such as PNUTS [20] and DPaxos [58].

In this paper, we present the design of a system, SLOG, that is

the ﬁrst (to the best of our knowledge) to achieve all three: (1)

strict serializability (2) low-latency reads and writes (on at least

some transactions) and (3) high throughput. SLOG uses locality in

access patterns to assign a home region to each data granule. Reads

and writes to nearby data occur rapidly, without cross-region com-

munication. However, reads and writes to remote data, along with

transactions that access data from multiple regions, must pay cross-

region communication costs. Nonetheless, SLOG uses a determin-

istic architecture to move most of this communication outside of

conﬂict boundaries, thereby enabling these transactions to be pro-

cessed at high throughput, even for high contention workloads.

SLOG supports two availability levels: one in which the only

synchronous replication is internally within a home region (which

is susceptible to unavailability in the event of an entire region fail-

ure), and one in which data is synchronously replicated to one or

more nearby regions (or availability zones) to achieve an availabil-

NuoDB declined to give us their software, so we implemented our

own version. NuoDB uses a MVCC protocol that is susceptible to

write skew anomalies. Our version used locking instead in order to

guarantee strict serializability.

ity similar to Amazon Aurora [89, 90] where the system remains

available even in the event of a failure of an entire region. Unlike

Spanner, Cosmos DB, Aurora, or the other previously cited systems

that support synchronous cross-region replication, SLOG’s deter-

ministic architecture ensures that its throughput is unaffected by

the presence of synchronous cross-region replication.

2. BACKGROUND

SLOG supports strictly serializable transactions that access data

mastered in multiple regions. Unlike systems such as L-Store [49]

and G-Store [23], which remaster data on the ﬂy so that all data

accessed by a transaction becomes mastered at the same physical

location, SLOG does not remaster data as part of executing a trans-

action. Instead, it utilizes a coordination protocol across regions to

avoid data remastership. One important technique used by SLOG

to overcome the scalability and throughput limitations caused by

coordination across partitions is to leverage a deterministic execu-

tion framework. Our technique is inspired by the work on Lazy

Transactions [30], Calvin [87, 88], T-Part [92], PWV [31], and Fau-

naDB [1] which use determinism to move coordination outside of

transactional boundaries, thereby enabling conﬂicting transactions

to run during this coordination process.

In the above-cited deterministic systems, all nodes involved in

processing a transaction — all replicas and all partitions within a

replica — run an agreement protocol prior to processing a batch

of transactions that plans out how to process the batch. This plan

is deterministic in the sense that all replicas that see the same plan

must have only one possible ﬁnal state after processing transactions

according to this plan. Once all parties agree to the plan, processing

occurs (mostly) independently on each node, with the system rely-

ing on the plan’s determinism in order to avoid replica divergence.

This approach prevents the dramatic reductions in throughput under

data contention that are observed in systems such as NuoDB [66,

67] and the strictly serializable transaction implementation on top

of FuzzyLog [53] that perform coordination inside transactional

boundaries, and G-Store and L-Store which prevent contended data

access during the remastering operations.

Determinism also reduces latency and improves throughput by

eliminating any possibility of distributed and local deadlock [7, 70,

78, 79, 87], and reducing (or eliminating) distributed commit pro-

tocols such as two-phase commit [7, 83, 84, 86, 87].

Unfortunately, in order to create a deterministic plan of execu-

tion, more knowledge about the transaction is needed prior to pro-

cessing it relative to traditional nondeterministic systems. Most

importantly, the entire transaction must be present during this plan-

ning process. This makes deterministic database systems a poor ﬁt

for ORM tools and other applications that submit transactions to

the database in pieces.

Second, advanced planning usually requires knowledge regard-

ing which data will be accessed by a transaction [33, 34, 83, 87].

Most deterministic systems do not require the client to specify this

information when the transaction is submitted. Instead they at-

tempt to statically derive this knowledge from inspecting the trans-

action code [87], make conservative estimates [31], and/or specu-

latively execute parts of the transaction, such as the OLLP protocol

in Calvin or the multi-stage execution process in FaunaDB.

SLOG’s use of determinism causes it to inherit both of these re-

quirements. As we will describe in Section 4, we implement SLOG

inside the open source version of Calvin’s codebase. Since Calvin

uses a combination of static analysis and OLLP to determine read

and write sets prior to transaction execution, our implementation

also uses these techniques.

1748

of 15

免费下载

tidb

关注

评论