Zen and the Art of Concurrency Control: An Exploration of TM Safety Property Space with Early Release in Mind
Konrad Siek · 2014
Transaction Memory (TM) [9, 12] is a concurrency control abstraction that allows the programmer to specify blocks of code to be executed atomically (or with particular guarantees). However, since transactional code can contain just about any operation, rather than just reads and writes of TM’s database predecessors, a greater attention must be payed to the state of shared variables at any given time. E.g., if a database transaction reads a stale value, it must simply abort and retry, and no harm is done. Whereas, if a TM transaction reads a stale value it may execute dangerous operations, like attempt to divide by zero, access an illegal memory address, or enter an infinite loop. Thus strong safety properties are considered important in TM, such as opacity [6] which regulate what values can be read, even by transactions that abort. In comparison to these, standard database consistency conditions such as serializability [11] are relatively weak. However, such strong properties preclude (or virtually preclude) using early release as a technique for optimizing TM (see [5, 13]). Early release is a mechanism by which transactions forgo exclusive access to shared variables in return for increased parallelism of operations between transactions. In order to maintain the correctness of the global state, transactions which read an inconsistent value are aborted, but this does not prevent them from viewing at least some inconsistent data. Hence, they cannot satisfy standard properties like opacity, etc. On the other hand, serializability does not describe the TM’s guarantees adequately, since the TM can preclude some, if not all, inconsistent views, and therefore be much more safe and practical than a serializable TM. Hence, in this paper we explore the TM safety property space: serializability, opacity virtual world consistency [10], and the TMS family [4], and consider whether they support early release and to what extent. We do this in Section 3, but define our terms beforehand in Section 2. In the latter part of Section 3, we take a look at some database consistency properties designed for transactional processing in databases. We consider them pertinent, since database transactions have many similarities to TM. Finally, in Section 4, we specify how serializability can be combined with some database properties to create a broader spectrum of useful early release supporting TM safety properties. We fill the remaining gap by proposing Last-use consistency, a consistency property that excludes those inconsistent views which are the most troublesome, but allows others. 2. Definitions