Memory Abstractions for Data Transactions

This thesis presents STO, a software transactional memory (STM) based not on low-level reads and writes on memory, but on datatypes—arrays, lists, queues, hash tables, and so forth—that explicitly support transactional operations. Conventional STMs allow programmers to write concurrent code in much the same way as sequential code—thereby more easily taking advantage of multiple CPU cores. However, these conventional STMs track every memory word accessed during a transaction, so even simple operations can perform many more memory accesses for synchronization than is strictly required for transactional correctness. Our insight is that concurrent data structures can generate fewer superfluous accesses, and use more efficient concurrency protocols, when transaction bookkeeping tracks high-level operations like “insert node into tree.” We test our ideas on the STAMP benchmark suite for STM applications, on a high-performance in-memory database, and on a previously single-threaded program that we extend to multithreaded operation. We find that datatypes can support transactional operations without too much trouble; that relatively naive users can build simple transaction support into their own data structures; and that our typed STM can outperform and outscale conventional, untyped STM, and even outperform world-class, hand-rolled transactional implementations for databases. This thesis also includes a full implementation of the system, which will be made open source and is currently available on request