Repairing serializability bugs in distributed database programs via automated schema refactoring

Kia Rahmani, Kartik Nagar, Benjamin Delaware, Suresh Jagannathan

TL;DR

Distributed databases often trade off "serializability" (the guarantee that transactions happen in a predictable, sequential order) for performance, leading to subtle concurrency bugs. This paper introduces Atropos, a tool that automatically repairs these bugs not by adding slow locks, but by refactoring the database schema. By reorganizing how data is laid out—such as merging related fields into a single row to exploit row-level atomicity—Atropos eliminates 74% of identified bugs while achieving 120% higher throughput than traditional serialization.

What Problem Does This Paper Address?

In a perfect world, every database would be "serializable," meaning even if a thousand users hit the database at once, the result is the same as if they had lined up one by one. In the real world of distributed systems, enforcing this requires massive coordination between servers, which kills performance.

To stay fast, developers often use "weak consistency" models. This leads to serializability anomalies:

  • Dirty Reads: Seeing data from a transaction that hasn't finished yet.
  • Lost Updates: Two people try to update a counter at the same time, and one update simply vanishes.
  • Non-repeatable Reads: Reading the same row twice and getting different results because someone else changed it in between.

Traditionally, fixing these bugs meant adding heavy-duty locks or "strengthening" the isolation level, both of which slow the system down. The authors ask: Can we fix the bug by changing the data's "home" rather than the code's logic?

Methods

The authors present a sound, automated procedure implemented in a tool called Atropos. The workflow follows these steps:

  1. Static Anomaly Detection: Atropos uses an SMT solver (Z3) to analyze the program's transactions and identify "anomalous access pairs"—specific points where concurrent execution could lead to a bug.
  2. Schema Refactoring Rules: Instead of adding locks, Atropos applies formal transformation rules to the data layout:
  3. Fusing/Aggregation: If a transaction updates two different tables non-atomically, Atropos might merge those fields into a single row in a new table. Since most databases guarantee row-level atomicity, the update becomes "all-or-nothing" by default.
  4. Logging (Append-only): To fix "lost updates" on a counter, Atropos can transform an UPDATE into an INSERT into a logging table. Instead of overwriting a value, the system records a new "event," and the final value is calculated by summing the log.
  5. Program Rewriting: Atropos automatically updates the application code (SQL queries) to match the new schema, ensuring the original program logic remains intact.

Datasets

The authors evaluated Atropos using a corpus of nine realistic database benchmarks, including:

  • TPC-C: The industry standard for online transaction processing.
  • SmallBank: A banking application benchmark.
  • Twitter & Wikipedia: Benchmarks simulating social media and content management workloads.
  • SEATS: An airline ticketing system.
  • Killrchat: A scalable chat application.

Key Insights and Ideas

  • Data Layout as a Concurrency Primitive: The most striking insight is that the physical organization of data is a valid tool for concurrency control. We usually think of schemas as being about "data modeling" and locks as being about "concurrency," but this paper blurs that line.
  • Exploiting Row-Level Atomicity: Almost every modern distributed database (like MongoDB or Cassandra) guarantees that updates to a single row/document are atomic. Atropos "hacks" this guarantee by moving conflicting data into the same row, getting "free" atomicity without the overhead of a global lock.
  • Functional Updates: By turning updates into inserts (the logging rule), the authors move from a mutable state model to a functional/event-sourced model, which is inherently more resistant to race conditions.

Key Results

  • Bug Suppression: Atropos successfully eliminated an average of 74% of all identified serializability anomalies across the benchmarks.
  • Massive Performance Gains: Compared to a "serialized baseline" (the traditional way to fix these bugs), refactored programs showed:
  • 120% higher throughput (more transactions per second).
  • 45% lower latency (faster response times).
  • 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.

Limitations and Future Work

  • The 26% Gap: Atropos couldn't fix all bugs. Some anomalies involve complex dependencies across many records that cannot be easily fused into a single row without creating a "mega-table" that ruins performance.
  • Storage and Read Trade-offs: The "logging" refactoring fixes lost updates but makes reads more expensive (you have to sum the log) and uses more storage. The authors suggest future work could involve automated "compaction" to clean up these logs.
  • DSL Constraints: Currently, the tool works on a Domain Specific Language (DSL). While the authors claim it could be extended to JDBC or Python DB-APIs, the current implementation requires the program to be expressed in their specific format.

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, this paper presents a sound fully-automated schema refactoring procedure that refactors 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 realistic 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 a serialized baseline.
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},
}

Loading related content...

Figure