Abstract
Serializability is a well-understood concurrency control mechanism that eases reasoning about highly-concurrent database programs. Unfortunately, enforcing serializability has a high-performance cost, especially on geographically distributed database clusters. Consequently, many databases allow programmers to choose when a transaction must be executed under serializability, with the expectation that transactions would only be so marked when necessary to avoid serious concurrency bugs. However, this is a significant burden to impose on developers. To mitigate this burden, we present a sound and fully automated schema refactoring procedure that transforms a program's data layout—rather than its concurrency control logic—to eliminate statically identified concurrency bugs, allowing more transactions to be safely executed under weaker and more performant database guarantees. Experimental results over a range of database benchmarks indicate that our approach is highly effective in eliminating concurrency bugs, with safe refactored programs showing an average of 120% higher throughput and 45% lower latency compared to the baselines.
Introduction
Distributed databases are the backbone of modern global-scale applications. To maintain high performance and low latency, these systems often relax consistency guarantees, moving away from strict serializability. While this improves speed, it introduces the risk of subtle concurrency bugs—anomalies like lost updates or dirty reads that are notoriously difficult for developers to debug and fix manually.
The Problem: Serializability Anomalies
Enforcing serializability requires coordination across distributed nodes, which significantly impacts throughput. Developers are often forced to manually identify which transactions require stronger isolation, a process that is error-prone and requires deep reasoning about complex, non-deterministic interactions. These interactions can be modeled as dependency graphs where cycles indicate potential serializability violations.
Traditionally, fixing these bugs meant adding heavy-duty locks or "strengthening" the isolation level, both of which slow the system down. The core question addressed by this research is whether these bugs can be fixed by changing the data's "home" rather than the code's logic.
Automated Repair via Atropos
This paper introduces Atropos, a tool designed to automatically repair serializability bugs. Unlike traditional approaches that strengthen isolation levels or add locks, Atropos employs a novel strategy: automated schema refactoring. By reorganizing the physical layout of data, Atropos leverages the row-level atomicity guarantees provided by most modern distributed databases to eliminate concurrency bugs without the overhead of global synchronization.
The Atropos Workflow
The Atropos pipeline consists of several key stages:
- Static Anomaly Detection: Using an SMT solver (Z3), the tool analyzes transaction code to identify "anomalous access pairs"—specific operations that, when executed concurrently, could lead to a bug.
- Refactoring Engine: Atropos applies formal transformation rules to the schema. For instance, Fusing merges related fields from different tables into a single row to ensure atomic updates. Logging transforms updates into append-only inserts to prevent lost updates on counters.
- Program Rewriting: Finally, the tool automatically updates the application's SQL queries to interact correctly with the new schema, ensuring the original program logic remains intact.
Key Insights
The core innovation lies in treating data layout as a concurrency primitive. By exploiting the fact that most modern distributed databases (like MongoDB or Cassandra) guarantee that updates to a single row or document are atomic, Atropos "hides" concurrency issues within the database's own internal consistency mechanisms. This allows developers to get "free" atomicity without the overhead of a global lock.
Evaluation and Results
The authors evaluated Atropos across nine industry-standard benchmarks, including TPC-C, SmallBank, and Twitter. The results demonstrate that Atropos is highly effective:
- Bug Suppression: It successfully eliminated an average of 74% of all identified serializability anomalies.
- Performance Gains: Refactored programs showed 120% higher throughput and 45% lower latency compared to a serialized baseline.
- Minimal Overhead: Running the refactored code under weak consistency resulted in less than a 3% performance hit compared to the original (buggy) weakly-consistent version.
Conclusion and Future Work
Atropos represents a significant shift in how we approach distributed database safety. By moving the "fix" from the logic layer to the data layer, it provides a path toward high-performance, bug-free distributed applications. Future work includes addressing the remaining 26% of bugs that involve complex cross-record dependencies and optimizing the storage overhead associated with logging-based refactoring.
Summary updated