Source-linked AI summary
Highly Available Transactions: Virtues and Limitations (Extended Version)
Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica
TL;DR
Distributed stores often sacrifice transactions to stay available and reduce latency during failures and partitions. This paper classifies which transactional and consistency guarantees can be highly available, using impossibility results, constructive algorithms, and empirical analysis. It finds a broad HAT design space with low-latency, always-on operation, while identifying fundamental limits around recency and concurrent updates.
Problem
The paper asks which transactional semantics can remain available and low-latency during network partitions, given that existing systems often sacrifice transactions.
Method
It builds a taxonomy of highly available systems and analyzes ACID isolation and distributed consistency guarantees using impossibility results and constructive algorithms.
Results
HATs provide a broad family of transactional isolation and replica semantics with always-on operation and often orders-of-magnitude lower latency than non-compliant systems.
Takeaways & Limitations
HATs can support many weak consistency and ACID guarantees, including transactional snapshot combinations, while applications with monotonic logic and commutative updates are especially suitable.
Takeaways & Limitations
HAT systems cannot prevent concurrent updates or guarantee read recency, so some concurrency-sensitive applications require unavailable semantics.
Abstract
from arXiv · showhide
To minimize network latency and remain online during server failures and network partitions, many modern distributed data storage systems eschew transactional functionality, which provides strong semantic guarantees for groups of multiple operations over multiple data items. In this work, we consider the problem of providing Highly Available Transactions (HATs): transactional guarantees that do not suffer unavailability during system partitions or incur high network latency. We introduce a taxonomy of highly available systems and analyze existing ACID isolation and distributed data consistency guarantees to identify which can and cannot be achieved in HAT systems. This unifies the literature on weak transactional isolation, replica consistency, and highly available systems. We analytically and experimentally quantify the availability and performance benefits of HATs--often two to three orders of magnitude over wide-area networks--and discuss their necessary semantic compromises.
1 Introduction
The paper asks which transactional isolation and consistency guarantees can remain highly available during partitions. It classifies achievable HAT semantics and identifies their benefits and fundamental compromises.
- Most deployed databases expose weak isolation, which is often accepted despite application-level anomalies and is stronger than semantics in current highly available systems.
- The paper relates database isolation and replica consistency models to high availability, classifying achievable guarantees as Highly Available Transactions.It also argues that some non-HAT implementations reflect implementation limitations rather than inherent semantic impossibility.
- Snapshot Isolation and Repeatable Read are not HAT-compliant, while most other isolation levels are achievable with high availability.
- Impossibility results and constructive proof-of-concept algorithms establish which guarantees are achievable.Achievable algorithms use multi-versioning and limited client-side caching; some guarantees require sticky client-server affinity.
- The paper surveys practitioner and academic accounts, evaluates cloud-infrastructure performance, and analyzes representative applications to assess HAT semantics.
- HATs provide guaranteed responses, horizontal scale-out, and one to three order of magnitude lower latencies, but cannot prevent concurrent modifications.Applications may therefore need HAT and, ideally sparingly used, non-HAT isolation levels.
2 Why High Availability?
High availability matters because partitions occur in modern networks and wide-area communication is costly. HAT designs address these conditions by avoiding coordination, trading strong semantics for continued responses and lower latency.
- Operators and practitioners identify partition management as an important operational concern, with systems adding weaker highly available modes for partitioned conditions.
- 13,300 network failures with end-user impact were observed across several Microsoft datacenters, with a mean of 40.8 link failures per day.Median repair time was around five minutes, reaching up to one week; redundant networks reduced failure impact by up to 40%.
- Network partitions occur within and across modern datacenters, forcing systems to choose between server unavailability and relaxed semantic guarantees.
- EC2 measurements sampled ping RTTs among seven geographic regions, three availability zones, and hosts within a single availability zone.
- Intra-datacenter communication was 40 to 647 times faster than communication across geographically distributed datacenters.Across co-located datacenters, intra-datacenter communication was 1.82 to 6.38 times faster.
- 362.8ms average RTT between São Paulo and Singapore exceeded the 106.7ms speed-of-light RTT, reaching 649ms at the 95th percentile.
3 ACID in the Wild
Weak isolation is widespread in ACID and NewSQL databases, yet its relationship to high availability has been unclear. The paper frames this gap against serializability’s coordination costs and existing single-node assumptions.
- Serializability is not achievable in a highly available system, creating a choice between availability and strong semantics.
- Weak isolation is commonly used for concurrency and performance benefits, despite allowing consistency anomalies.
- Only three of 18 surveyed databases provided serializability by default, while eight did not provide serializability as an option.The survey covered default and maximum isolation guarantees in databases claiming ACID or NewSQL functionality.
- It was unknown which weak isolation and consistency guarantees could be provided with high availability.Existing weak-isolation algorithms often assumed single-node locking mechanisms that are not resilient to partial failure.
4 High Availability
The paper defines availability models for transactions, including replica, transactional, and sticky availability. Transactional availability requires eventual commit or internal abort when every accessed item has an available replica.
- Highly available algorithms guarantee responses without synchronous communication, which also provides low latency by avoiding cross-datacenter waits.
- Traditional high availability requires every user contacting a correct server to eventually receive a response despite indefinitely long network partitions.
- Sticky availability lets clients preserve continuity across operations by repeatedly contacting the same logical replica or replicas.
- High availability is insufficient by itself for transactional guarantees because traditional definitions address single-object operations rather than multi-object transactions.
- Availability definitions may exclude systems requiring server majorities or only probabilistic responses, reflecting stringent CAP-style assumptions.
- Replica availability means a transaction can contact at least one replica for every item it accesses.This may be lower than non-transactional availability because transactions span multiple items.
- Transactional availability requires eventual commit or internal abort when every transaction item has replica availability.The system must not indefinitely abort transactions itself; client retries are permitted.
5 Highly Available Transactions
HAT systems provide transactional or sticky transactional availability, offering selected ACID, replica-consistency, and session guarantees while excluding guarantees that require preventing certain anomalies or ensuring recency.
- HAT systems offer transactional availability or sticky transactional availability, with latency and availability benefits over traditional distributed databases.
- Achievable guarantees include Read Committed isolation, variants of Repeatable Read, atomic reads, and many session guarantees.
- Sticky availability enables read-your-writes, PRAM, and causal consistency, while HAT systems cannot prevent Lost Update or Write Skew or guarantee recency.
- The paper unifies database and distributed-systems terminology by informally explaining existing properties and supplying formal definitions in an appendix.
5.1 Achievable HAT Semantics
The paper identifies several transaction and consistency semantics achievable with high availability, using proof-of-concept algorithms based on techniques such as timestamps, buffering, caching, and multi-versioning.
- Achievable HAT Semantics: Proof-of-concept algorithms establish feasibility of highly available semantics without necessarily optimizing performance or efficiency.The paper’s primary goal in this section is to prove that algorithms providing high availability exist.
- Read Uncommitted: Read Uncommitted can use transaction-wide timestamps and last-writer-wins reconciliation at each replica.
- Read Committed: Read Committed prevents Dirty Reads by buffering writes until commit or withholding uncommitted values from other readers.
- Cut Isolation: Item Cut Isolation and Predicate Cut Isolation can be achieved through client-side caching, sticky replicas, or multi-versioning.
- Monotonic Atomic View: MAV ensures that once a transaction’s effects are observed, later reads observe all its effects, supporting uses such as foreign keys and derived data.
- Monotonic Atomic View: The efficient MAV algorithm remains master-less and avoids operation blocking from replica coordination by using pending-stable writes and read lower bounds.
- Session Guarantees: Read-your-writes, causality, and PRAM require stickiness; dependent writes are revealed only after their relevant dependencies have been revealed.
- Application-Level Consistency: HAT systems can often execute commutative and logically monotonic operations safely and maintain limited application-level criteria such as foreign keys via MAV.
5.2 Unachievable HAT Semantics
The paper shows that several isolation and consistency guarantees are unachievable with high availability because partitions prevent conflict detection, recency enforcement, or sufficient replica contact.
- Unachievable ACID Isolation: Lost Update and Write Skew cannot be prevented in HAT systems, making Snapshot Isolation, Repeatable Read, and one-copy serializability unachievable.
- Lost Update: A Lost Update can leave x at 120 or 130 even though neither state could result from a serial execution of the two transactions.
- Lost Update: Preventing Lost Update would require rejecting one transaction or detecting the latest version, a requirement tied to linearizability and incompatible with high availability.
- Write Skew: Write Skew can violate integrity constraints across multiple keys, and its prevention is likewise unavailable to HAT systems.
- Unachievable ACID Isolation: Consistent Read, Snapshot Isolation, Cursor Stability, Repeatable Read, and One-Copy Serializability are unavailable because they require preventing Lost Update or Write Skew.
- Recency Guarantees: Indefinitely long partitions prevent HAT systems from enforcing any fixed recency bound on reads.
- Fault Tolerance: Surviving F server faults requires contacting at least F + 1 non-failing replicas before commit, so F > 1 fault tolerance is not highly available under the adopted definition.
5.3 Summary
HAT systems support a broad range of transactional and consistency guarantees, but stronger models remain unavailable when they require preventing concurrent-update anomalies or recency violations. The taxonomy organizes these models by strength and availability, including combinations whose availability is limited by their least available component.
- Read Committed, transactional atomicity, and many other consistency models are achievable with high availability, while Snapshot Isolation and Repeatable Read are not.The unavailable models require detecting conflicts to prevent Lost Updates or Write Skew.
- Sticky availability supports Read Your Writes, PRAM, and causal consistency guarantees.
- Combining HAT and sticky guarantees yields transactional, causally consistent snapshot reads called Causal Transactional Predicate Cut Isolation.
- The taxonomy unifies transactional isolation, distributed consistency, and session guarantee models, depicting 144 possible HAT combinations.The authors describe it as non-exhaustive while arguing that it clarifies relationships among many prominent models.
- HATs may expose more anomalies than single-site weak-isolation databases during partitions, and their visibility and concurrent-update limitations are fundamental.User-level compensation and per-statement isolation upgrades remain possible but may compromise availability.
6 HAT Implications
HAT implications depend on application semantics and deployment conditions: many TPC-C operations are supported, while non-monotonic updates require stronger guarantees or compensation. Experiments show that HAT prototypes avoid WAN coordination costs and can retain competitive throughput, with overheads driven by transaction size, write intensity, and geo-replication.
- 6.2 Application Requirements: Four of five TPC-C transactions can execute via HATs, while the fifth requires unavailability.The problematic cases involve requirements that HATs cannot satisfy without stronger semantics.
- 6.2 Application Requirements: TPC-C New-Order cannot provide sequential district-local order numbers because that requirement requires preventing Lost Update, though uniqueness can be maintained.
- 6.2 Application Requirements: TPC-C integrity constraints spanning two tables can be maintained atomically via MAV, and many TPC-E isolation tests are also achievable with HATs.
- 6.3 Experimental Costs: Across five servers per cluster, mastering each item gives approximately half the throughput and double the latency of eventual within one datacenter, while WAN deployment makes master latency 300ms.HAT models can use replicas in both clusters instead of contacting a single master.
- 6.3 Experimental Costs: With five geo-distributed clusters, MAV throughput peaks at around half of eventual because remote replica writes increase anti-entropy, garbage collection, and IOPS.
- 6.3 Experimental Costs: MAV throughput decreases linearly with transaction length, reaching within 60% of eventual at 128 operations versus within 18% at one operation.The algorithm’s metadata grows with transaction length and consumes IOPS and network bandwidth.
- 6.3 Experimental Costs: At 99.8% reads, MAV incurs a 7% overhead, while all writes place it within 33% of eventual and all reads within 4.8%.
- 6.3 Experimental Costs: HAT algorithms provide useful semantics without substantial performance penalties, with MAV competitive with eventual consistency and shared-nothing algorithms scaling linearly.The trade-off is increased disk and network utilization, while HATs avoid WAN latencies inherent in non-HAT implementations.
7 Related Work
Related work spans highly available semantics, concurrency control, scalable distributed operations, and distributed multi-object transactions. HATs position transactional semantics as an alternative to systems that trade availability and latency for stronger consistency.
- Prior work studies weak consistency, high availability, weak isolation, optimistic replication, and stickiness, but this paper connects these areas to transactional semantics.
- The paper extends prior work by exploring connections among transactional semantics, data consistency, and availability.
- Strong ACID systems such as Spanner provide serializable transactions, but their design incurs fundamental penalties in availability and latency during partitions.
- Swift, Eiger, and Bolt-on Causal Consistency propose transactional causal guarantees with varying availability and represent sticky HAT systems.
8 Conclusions and Future Work
The paper argues that Highly Available Transactions offer a broad design space for combining partition availability and low-latency operation with transactional semantics. It also identifies substantial opportunities to improve the programmability of highly available systems.
- Highly Available Transactions (HATs) expose a broad design space for combining transactional semantics with highly available distributed-system benefits.These benefits include “always on” operation during partitions and low-latency operation.
- The authors argue that current database software presents unnecessary choices between availability and transactional semantics.
- Improving the programmability of highly available systems remains considerable unfinished work.The paper largely focuses on previously defined isolation and data-consistency models because their utility to end-users is suggested by prior definitions and adoption.
- HATs represent a large and useful design space for future exploration.
A Formal Definitions
This section formalizes HAT transactional semantics by combining transactional models with distributed-systems semantics. It defines histories, sessions, dependency graphs, anomalies, and isolation levels using extensions of Adya’s framework.
- A Formal Definitions: The formalism combines transactional models with distributed-systems semantics and clarifies the paper’s definitions.
- A.1 Model: The database model contains multiple object versions, with transactions composed of reads and writes; predicate operations select a version set Vset(P).
- A.1 Model: A history records a partial order of transaction events and a total version order on committed object versions.
- A.1 Model: Sessions add a partial order over committed transactions, with each transaction appearing in at most one session.
- A.2 Conflict and Serialization Graphs: The Directed Serialization Graph represents item, predicate, and session dependencies, while the Unfolded Serialization Graph splits the transaction of interest into event nodes connected by relevant and order edges.The framework extends Adya’s definitions with per-item dependencies and session dependencies.
- A.2 Conflict and Serialization Graphs: Read, anti-, write-, and session-dependency definitions specify how transactions relate through versions, predicate-match changes, overwrites, and session order.
- A.2 Conflict and Serialization Graphs: Direct anti-dependencies capture later writes after reads, while write-dependencies capture successive versions of an item.
- A.3 Transactional Anomalies and Isolation Levels: Isolation levels are defined by prohibited serialization-graph anomalies: Read Uncommitted prohibits G0, whereas Read Committed additionally prohibits G1a, G1b, and G1c.The anomaly definitions cover write cycles, aborted reads, intermediate reads, and circular information flow.
B Monotonic Atomic View Isolation
The section describes an implementation of Monotonic Atomic View isolation using pending and good write sets, acknowledgments, timestamps, and required-read metadata. It also discusses batching, alternative acknowledgment schemes, and the resulting overheads and implementation limitations.
- The implementation remains a work in progress: pull-based efficiency and the visibility effect of side-channel notifications were not experimentally determined.
- Monotonic Atomic View requires writes to become stable across replicas before they move from pending to good.Replicas count acknowledgments for writes from other replicas to determine pending stability.
- A two-replica example shows each replica placing transaction writes in pending and exchanging acknowledgments before stability is established.
- MAV adds client vector state and per-write metadata proportional to transaction size, increasing value sizes for longer transactions.
- Push-based notifications may waste transfers, motivating pull-based polling and invalidation of obsolete pending writes.
- Batching acknowledgments, notifications, and anti-entropy operations can reduce communication overhead.
- The algorithm uses transaction timestamps and sibling-key metadata to coordinate writes belonging to the same transaction.
- Reads select the highest-timestamped good write that satisfies the required timestamp, while client-side required metadata tracks visibility constraints.