Transactional Data Structure Programming Systems (TDSPSs) allow programmers to compose sequences of method invocations on concurrent data structures (CDSs) into coarse-grained, isolated ``transactions''. To do this, they must be able to detect and recover from situations where method invocations from concurrent transactions do not commute. Thus they typically must impose rules about how data structure methods interact with synchronization metadata, transaction metadata, and program state. A system’s rules can impact latency, throughput, generality, and ease of use.

This paper explores a new design point for TDS systems, called Harmony. Harmony carefully orchestrates two categories of metadata: one for synchronization, another for transaction management. This avoids false conflicts among transactions, while avoiding unnecessary coupling within the TDSPS implementation.

Harmony enables programmers to implement a broad set of data structures, including skip lists, resizable arrays, deques, and resizable hash tables. These data structures easily support complex features, such as read-only and mutating range queries. In evaluation on microbenchmarks and the TPC-C benchmark suite, Harmony significantly outperforms the current state of the art.