Repairing Serializability Bugs in Distributed Database Programs via Automated Schema Refactoring

Kia Rahmani, Kartik Nagar, Benjamin Delaware, Suresh Jagannathan

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.

Visualization of anomalous access pairs in concurrent transactions.

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 system architecture pipeline.

The Atropos Workflow

The Atropos pipeline consists of several key stages:

  1. 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.
  2. 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.
  3. 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

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, requiring them to (a) reason about subtle concurrent interactions among potentially interfering transactions, (b) determine when such interactions would violate desired invariants, and (c) then identify the minimum number of transactions whose executions should be serialized to prevent these violations. To mitigate this burden, in this paper 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.
BibTeX
@inproceedings{rahmani2021repairing,
  author = {Kia Rahmani and Kartik Nagar and Benjamin Delaware and Suresh Jagannathan},
  title = {{Repairing Serializability Bugs in Distributed Database Programs via Automated Schema Refactoring}},
  booktitle = {PLDI},
  year = {2021},
  url = {https://openreview.net/forum?id=vtvnDgzTNiw},
}
Figure