Approximate Consistency in Transactional Memory

Abstract

In Transactional Memory each shared object can be accessed by concurrent transactions which may cause conflicts and aborts. Opacity is a precise consistency property which maps a concurrent execution to a legal sequential execution that preserves the real time order of events. However, having precise consistency in large scale network and database applications may result in a large rate of aborts, especially in systems that have frequent memory updates. Actually, high rate of aborts causes huge negative performance impact. In real applications, there are systems that do not require precise consistency especially when the data is not sensitive. Thus, we introduce here the notion of approximate consistency in transactional memory. We define K-opacity as a relaxed consistency property where transactions are allowed to read one of the K most recent written values to the objects (and not just the latest value only). This increases the throughput and reduces the abort rate by reducing the chance of conflicts. In multi-version transactional memory, the relaxed consistency allows to save a new object version once every K object updates, and hence, reduces space requirements by a factor of K. In fact, we apply the concept of K-opacity to regular read/write, count, and queue objects, which are common objects used in typical concurrent programs. We use the technique of writer lists to keep track of the transactions and the data being written to the system, in order to control the error rate and to prevent error propagation. We illustrate with an experimental analysis the positive impact of our approach on performance, where higher opacity relaxation (higher values of K) increases the throughput and decreases the aborts rate significantly.