Transactional Boosting: A Methodology for Highly-Concurrent Transactional Objects

5 minute read

Published:

Software transactional memory (STM) is an emergent alternative to mutual exclusion. In STM, the activities are organised as transactions which can commit or abort. Most transactional memory systems synchronise on the basis of read/write conflicts. Two transactions are said to be in conflict if they modify at-least one same object. When conflicting transactions need to commit, we need some mechanism to resolve this conflict. This can be done by forcing either transaction to abort. The benefit of this type of conflict detection and resolution is that the overhead of managing conflicts does not fall to the programmer. But at the same time, this method also severely restricts the concurrency for shared objects which come under contention very often.

The paper presents a methodology for transforming a large class of highly linearizable objects into highly-concurrent objects. Transactional boosting considers each object to be a black box. Only a specification, specifying the objects state and the methods that affect it, are required to successfully create a boosted object.

Background

Informally, two operations are commutative if the application order of these operations on the same state does not affect the final outcome. For example, in a set, two operations add(x) and add(y) commute if x =/= y.

In this situation, an abstract lock is associated with each invocation of the boosted object. Abstract locks prevent non-commutative operations from executing concurrently.

For any method m, it’s inverse m’ is sound if applying m’ immediately after m undoes the effect of m. In this way if method inverses are known, then the recovery can be performed at a granularity level of method calls.

Boosted Transactions

In a boosted transaction, every method call has an inverse. When a transaction executes, it logs the inverses of the operations that take effect. If there is no conflict and the transaction can commit, the log generated by the transaction is discarded. If the transaction has to abort, the log entries are visited in reverse and executed.

Correctness rules for a transactional boosting system

  • Commutativity Isolation - “For any non-commutative method calls I1, R1 ∈ T1 and I2 , R2 ∈ T2 ; either T1 commits or aborts before any additional method calls from T<sub?2</sub> are invoked, or vice-versa”.
  • Compensating Actions - “For any history h and transaction T, if <T, aborted> ∈ h, then it must be the case that h | T = <T, init> . I0 . R0 ….. Ii . Ri . <T, aborted> Ii-1 . Ri-1 ….. I0-1 . R0-1 . <T, aborted> where i indexes the last successfully completed method call. “
  • Disposable method calls - “For any history h and Transaction T, any method call <T, xm(v)> . <T, r> that occurs after <T, commit> or <T, abort> must be disposable.”