SCert: Speculative Certification in Replicated Software Transactional Memories

N. Carvaho, P. Romano and L. Rodrigues

Selected sections of this report were published in the Proceedings of the 4th Annual International Systems and Storage Conference (SYSTOR 2011), Haifa, Israel, June 2011.

Abstract

Being much simpler to compose and verify than classical lock based synchronization schemes, Software Transactional Memories (STMs) have emerged as an attractive paradigm for supporting concurrent access to in-memory storage systems. This paper is focused on the issue of how to replicate STMs to enhance both their performance and dependability. This is an extremely challenging problem, since the communication/processing ratio in STMs is typically several orders of magnitude higher than in conventional database systems, thus amplifying the relative cost of replication.

We present SCert (Speculative Certification), a novel replication protocol for STMs that exploits early knowledge about message ordering in the underlying atomic broadcast layer to propagate, in a speculative fashion, the updates of transactions before there is an agreement on the final serialization order. This speculative approach brings the two following key benefits. On one hand, it lowers the chances that transactions access stale snapshots, thus minimizing the probability of later incurring in an abort. On the other hand, it provides early conflict detection, thus reducing the amount of wasted computation and/or waiting time from transactions doomed to abort. An experimental study of SCert, based on a fully fledged distributed STM prototype and heterogeneous benchmarks, has shown performance gains of up to 4.5x when compared with previous certification based schemes.

Also available extended report (pdf)

Luís Rodrigues