HAT, not CAP: Highly Available Transactions

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 pbailis@cs.berkeley.edu 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).