HAT, not CAP: Highly Available Transactions

Description

HAT, not CAP: Highly Available Transactions † ⋄ †,‡ † †Peter Bailis , Alan Fekete , Ali Ghodsi , Joseph M. Hellerstein , Ion Stoica † ⋄ ‡UC Berkeley University of Sydney KTH/Royal Institute of Technology [e-mail] Abstract vestigate whether it is possible to provide transactions To provide high availability, many scalable data stores that are available in partitioned environments (e.g., geo- abandon traditional database functionality, often offer- replicated systems), and, by proxy, achievable with low ing operations limited to single objects (or groups of latency—two increasingly common requirements [32, co-located objects) with limited consistency. However, 48, 49, 55, 60]. While the strongest form of ACID, seri- many applications benefit from transactions, or larger alizability, is not highly available [37], we show that the units of arbitrary combinations of multiple operations on most common forms of transactions in today’s databases multiple objects. While the CAP theorem is often in- can be made available. These ACID transactions per- terpreted to preclude the availability of transactions in a mit weaker forms of isolation than serializability but are provided by default by most “ACID” and “NewSQL”partition-prone environment, we show that highly avail- databases, many of which do not support serializabilityable systems can provide transactional guarantees match- at all (§2).

Sujets

• Informatique
• Marketing et communication

Informations

• Publié par: kyann
• Publié le: 03 mai 2013
• Nombre de lectures: 147
• Langue: English

Extrait

HAT, not CAP: Highly Available Transactions †⋄†,†‡ † Peter Bailis , Alan Fekete , Ali Ghodsi , Joseph M. Hellerstein , Ion Stoica †⋄‡ UC Berkeley University of Sydney KTH/Royal Institute of Technology [e-mail]

Abstract To provide high availability, many scalable data stores abandon traditional database functionality, often offer- ing operations limited to single objects (or groups of co-located objects) with limited consistency. However, many applications benefit from transactions, or larger units of arbitrary combinations of multiple operations on multiple objects. While the CAP theorem is often in- terpreted to preclude the availability of transactions in a partition-prone environment, we show that highly avail- able systems can provide transactional guarantees match- ing the majority of today's ACID databases. We propose Highly Available Transactions (HATs) that support many desirable semantic guarantees for arbitrary transactional sequences of read and write operations, execute with low latency, and remain available during partitions.

1 Introduction To provide high availability and low latency, many recent distributed data stores eschew strongly consistent seman- tics. The CAP theorem stipulates that it is impossible simultaneously provide single-key linearizable [43] se- mantics (“consistency”) and available operation (avail- ability) in the presence of arbitrary partitions between servers [40]. The implications of the CAP theorem on distributed system design are relatively well understood, and systems desiring “always on” operation must choose between one of several weak consistency models. There has been little investigation of how traditional ACID database semantics [42] and the CAP theorem [40] interact. While transactions are grounded in decades of database tradition [27, 28, 41], many low-latency, highly available stores completely eschew transactional, multi-object semantics under the impression that CAP applies to transactions, that it is impossible to provide highly available general-purpose transactional semantics in the presence of partitions. This common belief under- lies the NoSQL movement's rejection of ACID transac- tions [39] and, when today's users require multi-object operations, they must often settle for operations over re- stricted data types (e.g., commutative and monotonic op- erations) [22, 46, 60] or with restricted semantics (e.g., read-only operations, entity groups) [25, 48, 49] or in- stead face unavailability and high latency [29, 30, 33, 34, 35, 44, 46, 55, 57]. Our goal is to understand the relationship between the CAP theorem and transactions. In particular, we in-

1

vestigate whether it is possible to provide transactions that are available in partitioned environments (e.g., geo- replicated systems), and, by proxy, achievable with low latency—two increasingly common requirements [32, 48, 49, 55, 60]. While the strongest form of ACID, seri- alizability, is not highly available [37], we show that the most common forms of transactions in today's databases canThese ACID transactions per-be made available. mit weaker forms of isolation than serializability but are provided by default by most “ACID” and “NewSQL” databases, many of which do not support serializability at all (§primary problem is that these isolation2). The guarantees are notimplementedin an available manner: lock-based [41], mastered [27], and several other dis- tributed transaction implementations [28] all suffer from unavailability. We show that this need not be the case.

We provide a semantics for and sample implementa- tions ofHighly Available Transactions(HATs) that are achievable in partitioned environments and with low la- tency (§3). These HATs match the semantics provided by today's databases without compromising low latency and “always on” operation. Most notably, first, we provide transactional atomicity across arbitrary data items (“A” in “ACID”). Second, we provide ANSI-compliant Read Committed and Repeatable Read isolation. Third, we enforce partial ordering between transactions, allowing us to provide several inter- and intra-transaction session guarantees including monotonic reads, read-your-writes, and causal consistency. We also discuss semantics that arenotachievable, including recency bounds and glob- ally enforced correctness criteria (§4).

Our primary contribution in this report is to provide semantics for general-purpose, read/write transactions achievable in a highly available environment that areuse- fully strongerthan any we have previously seen (§5). In doing so, we demonstrate that we can provide the guarantees of today's traditional ACID databaseswith- outcompromising availability, low latency, or scalabil- ity. This requires new, highly available implementations of these guarantees, but our goal here is not to provide high-performance algorithms or a design space explo- ration (§Ac-6); rather, we provide a feasibility proof. cordingly, HAT semantics form the basis of a new gold standard for highly available distributed data stores, sup- plying powerful transactional functionality to users who demand high availability and low latency.