Composition vs Concurrency

Vincent Gramoli, Rachid Guerraoui, Mihai LeţiaInfoscience 2010

Abstract

Composing software is notoriously difficult, especially when it is concurrent. Two fine-grained locked operations may for instance easily deadlock upon composition. One of the most appealing features of transactions is, on the other hand, that they compose. Indeed they do so, but only in their original, orthodox, form. As we discuss in the paper, as soon as we slightly relax the model to enable more concurrency, we incur the risk of breaking encapsulation.

Introduction

In modern software engineering, composition is considered a fundamental requirement: the ability to combine simple, modular operations into complex ones without needing to understand their internal implementations. In a sequential environment, this is straightforward. However, in a concurrent environment, composition becomes a significant challenge. When multiple threads access shared data, the simple act of wrapping two thread-safe operations into a third often leads to race conditions or deadlocks.

This paper explores the fundamental tension between composition—the holy grail of modularity—and concurrency—the necessity of parallel performance. While traditional transactional memory (TM) was designed to solve this tension, modern performance-oriented optimizations often inadvertently destroy the very composability that made transactions attractive in the first place.

The Problem: The Composition Minefield

Consider a simple example: an operation $\pi_1$ that removes item $x$ from a set, and an operation $\pi_2$ that inserts item $y$. If we wish to create a composed "move" operation $\pi_3$, it must be atomic. No other thread should ever observe a state where $x$ has been removed but $y$ has not yet been inserted.

Using traditional locking mechanisms to achieve this is fraught with peril. If $\pi_1$ and $\pi_2$ use internal locks, a naive composition might lead to deadlocks if another thread attempts a similar operation in a different order. Transactional memory was proposed as a solution because transactions are, by definition, composable. However, "orthodox" transactions—those that track every individual memory read and write—often suffer from "false conflicts," where transactions are aborted due to low-level memory overlaps even if they are logically compatible. This leads to poor performance in high-concurrency scenarios.

Analysis of High-Concurrency Models

To address the performance limitations of orthodox transactions, researchers developed "relaxed" transactional models. This paper performs a qualitative analysis of three major categories of these models to determine if they preserve atomicity and deadlock-freedom during composition:

  1. Inversion-based Transactions: These models (such as Transactional Boosting) use semantic information to detect conflicts. Instead of locking memory, they use "undo" operations (e.g., an insert to undo a remove) to handle aborts. This allows for much higher concurrency.
  2. Escaped Transactions: These models allow a transaction to "release" or "escape" certain memory locations before the transaction actually commits, allowing other threads to access that data earlier.
  3. Mixed-granularity Transactions: These use varying sizes of metadata to manage conflicts—for example, locking an entire table for a bulk operation while using row-level locks for simple updates.

Key Insights: The Breakdown of Encapsulation

The authors find that while these models improve performance, they frequently break encapsulation—the "black box" nature of software components.

  • The Inverse Problem: Inversion-based models fail when an operation lacks a natural or efficient inverse. For instance, a complex moveAll operation cannot be easily composed if the underlying system cannot "un-move" the data without exposing intermediate, inconsistent states to the rest of the system.
  • State Leakage: Escaped transactions break atomicity during composition. If a nested transaction releases a variable $x$ early, a larger composed operation might leave the system in an inconsistent state that a standard transaction would have prevented. The internal "escape" leaks through the abstraction layer.
  • Metadata Mismatch: Mixed-granularity models often fail because different operations use different "languages" to track conflicts. A simple put might use a boolean flag, while a composed putAll might use a counter. Because these mechanisms do not communicate, the system fails to detect conflicts between simple and composed operations.

Proposed Solution: Elastic Transactions

To bridge the gap between performance and composability, the authors introduce Elastic Transactions. This model is designed to adapt based on the execution context.

In the Elastic model, an operation behaves "elastically" (optimizing for maximum concurrency) when it runs as a standalone operation. However, if that same operation is nested inside a larger, composed transaction, it automatically switches to "orthodox" transactional behavior. This ensures that the safety of the outer "black box" is maintained at all costs, even if it means sacrificing the performance gains of the relaxed model for that specific execution.

Conclusion and Future Work

The primary takeaway is that most modern attempts to "fix" transactional performance actually destroy the primary reason to use transactions: encapsulation. While Elastic Transactions provide a promising path forward by maintaining safety during composition, they face a performance penalty when deeply nested.

The authors suggest that multiversioning—maintaining multiple versions of data in memory—could be the key to maintaining high concurrency even within composed Elastic Transactions. Current research is focused on integrating multiversioning into the elastic framework to ensure that composition does not have to come at the expense of speed.

Summary updated

Abstract

Composing software is notoriously difficult, especially when it is concurrent. Two fine-grained locked operations may for instance easily deadlock upon composition. One of the most appealing features of transactions is, on the other hand, that they compose. Indeed they do so, but only in their original, orthodox, form. As we discuss in the paper, as soon as we slightly relax the model to enable more concurrency, we incur the risk of breaking encapsulation. 1
BibTeX
@inproceedings{gramoli2010composition,
  author = {Vincent Gramoli and Rachid Guerraoui and Mihai Leţia},
  title = {{Composition vs Concurrency}},
  booktitle = {Infoscience},
  year = {2010},
}
Figure