ROLA: A New Distributed Transaction Protocol and Its Formal Analysis

Si Liu, Peter Csaba Ölveczky, Keshav Santhanam, Qi Wang, Indranil Gupta, José MeseguerFASE 2018 · OpenReview

Abstract

Designers of distributed database systems face a persistent choice between stronger consistency guarantees and system performance. While many applications require Read Atomicity (RA) and Prevention of Lost Updates (PLU), existing systems that provide these often include additional, stronger guarantees like Causal Consistency (CC), which incur significant performance penalties. This paper introduces ROLA, a distributed transaction protocol specifically designed for applications where only RA and PLU are necessary. By formally modeling ROLA in Maude and employing statistical model checking, the authors demonstrate that ROLA ensures correctness while significantly outperforming the well-known Walter protocol in both throughput and latency.

The Consistency-Performance Trade-off

In distributed database architecture, the "hierarchy of consistency" dictates that stronger guarantees—which simplify application development—typically come at the cost of increased coordination overhead and reduced performance. The authors identify a specific niche for applications, such as social media interactions, that require:

  1. Read Atomicity (RA): Ensuring that a transaction sees either all effects of another transaction or none of them.
  2. Prevention of Lost Updates (PLU): Ensuring that concurrent writes to the same data item do not result in one update being silently overwritten.

While the Walter protocol provides these guarantees, it also enforces Causal Consistency (CC). Maintaining CC requires the propagation of complex vector timestamps across data centers, creating a performance bottleneck. ROLA was designed to provide RA and PLU while intentionally omitting CC to achieve higher efficiency.

Protocol Design and Formal Modeling

ROLA builds upon the RAMP (Read-Atomic Multi-Partition) protocol. To prevent lost updates, ROLA introduces a local sequence counter (sqn) and a mapping of timestamps to sequence numbers on each partition. This mechanism allows the system to detect and abort conflicting writes during a two-phase commit process.

The authors utilized a "formal-methods-first" approach, using the Maude high-performance language to create an executable specification of the protocol. This allowed for rigorous verification before any production implementation.

Maude class definition for a Partition in the ROLA protocol.

The formal model defines the state of each partition, including its local datastore, transaction lists (executing, committed, aborted), and the metadata required for the two-phase commit and sequence number tracking.

Verification and Performance Analysis

The research employed two distinct types of formal analysis:

  • Correctness Checking: Standard model checking (reachability analysis) verified that ROLA satisfies RA and PLU. Crucially, the analysis also confirmed that ROLA does not satisfy Causal Consistency, validating that the protocol successfully shed the intended overhead.
  • Statistical Model Checking (SMC): Using the PVeStA tool, the authors performed performance forecasting. By sampling message delays from lognormal distributions to simulate real-world network jitter, they ran thousands of simulations to estimate throughput and latency under various workloads (Uniform and Zipfian distributions).

Key Results

The comparative analysis against the Walter protocol yielded several key insights:

  • Throughput: ROLA consistently achieved higher throughput. As the number of partitions increased, ROLA scaled effectively due to its lower coordination requirements, whereas Walter's performance was hampered by the overhead of advancing vector timestamps.
  • Latency: ROLA exhibited significantly lower average transaction latency, particularly in write-heavy scenarios. By replacing global vector timestamps with local sequence numbers and a streamlined two-phase commit, ROLA eliminates the "background propagation" delays inherent in Walter.

Conclusion

ROLA demonstrates that by carefully selecting the minimum necessary consistency guarantees for a target application, designers can achieve substantial performance gains. The use of formal methods like Maude and statistical model checking provides a powerful framework for both proving correctness and predicting performance early in the system design lifecycle. Future work will involve implementing ROLA in production environments and exploring its resilience under node failures and network partitions.

Summary updated

Abstract

Designers of distributed database systems face the choice between stronger consistency guarantees and better performance. A number of applications only require read atomicity (RA) and prevention of lost updates (PLU). Existing distributed database systems that meet these requirements also provide additional stronger consistency guarantees (such as causal consistency), and therefore incur lower performance. In this paper we define a new distributed transaction protocol, ROLA, that targets applications where only RA and PLU are needed. We formally model ROLA in Maude. We then perform model checking to analyze both the correctness and the performance of ROLA. For correctness, we use standard model checking to analyze ROLA’s satisfaction of RA and PLU. To analyze performance we: (a) use statistical model checking to analyze key performance properties; and (b) compare these performance results with those obtained by analyzing in Maude the well-known protocol Walter. Our results show that ROLA outperforms Walter.
BibTeX
@inproceedings{liu2018rola,
  author = {Si Liu and Peter Csaba Ölveczky and Keshav Santhanam and Qi Wang and Indranil Gupta and José Meseguer},
  title = {{ROLA: A New Distributed Transaction Protocol and Its Formal Analysis}},
  booktitle = {FASE},
  year = {2018},
  url = {https://openreview.net/forum?id=9Pl72RXpuas},
}
Figure