The DB group

Advanced Transaction Management

Background - Research activities - Publications

AdTrans is a project of the Open Distributed Systems (ODS) group at Department of Computer Science, University of Tromsø.

For more information about the project, contact Randi Karlsen.

Background

Databases are being used for more and more advanced types of applications to store and manipulate information. These new types of database applications include CAD/CASE (Computer-Aided Design/Computer-Aided Software Engineering), workflows, multimedia, financial trading, federated database systems, and others. It is widely recognized that such advanced applications stresses the limits of the functionality and performance of traditional transaction management, and that advanced transaction management is needed.

This project has studied advanced transaction management for both open nested and flat transactions. A main focus has been on advanced concurrency control. To support this activity, we also study transaction decomposition and recovery for open nested transactions.

When two or more transactions execute concurrently, their operations execute in an interleaved fashion that may cause concurrency problems. These problems have traditionally been avoided by guaranteeing serializable executions of transactions. However, there are in many applications a need for more concurrency and thereby non-serializable executions.

One particular problem in many advanced applications, is a need to support long-lasting transactions. The length of duration of a long-lasting transaction may cause serious performance problems if it is allowed to lock resources until it commits. This may either force other transactions to wait for resources for an unacceptable long time, or it may increase the likelihood of transaction abort.

Research activities

Our research activities on advanced concurrency control have followed an approach where serializability is abandoned in favour of new and more relaxed correctness criteria. We have developed a new correctness criterion and a new concurrency control method that we believe can be used for both flat transactions and for open nested transactions. The correctness criterion and control method are adaptable in that they allow different correctness requirements both between transactions and within a single transaction.

We are also studying open nested transactions, where a top-level transaction is decomposed into a number of subtransactions which are executed independently. We are studying how this transaction structure effects both concurrency and recovery.

Current research activities:

Previous research activities:

 

New correctness criteria for flat transactions

In this project, we describe a new non-serializable correctness criterion, called ACC, intended for flat transactions. ACC is an adaptable correctness criterion, which determines legal interleaving of transactions in an environment where transactions may have different correctness requirements. ACC allows users of the database to attach correctness requirements to individual transactions. A correctness requirement for a transaction T may specify that isolation is required for some parts of T, while a higher degree of interleaving is allowed for other parts of T. Also, the specified correctness requirements for two transactions, T and T’, may well be different. We do not assume any decomposition of transactions, but use semantic information in flat transactions to allow non-serializable executions.

The motivation behind ACC is a belief that the notion of consistency is situation dependent. In particular, we find that the concurrency problem known as "the inconsistent retrieval problem" need not always be a problem. An execution that causes a so-called "inconsistent retrieval" may, under certain circumstances, reflect a consistent execution. This depends on the transaction semantics and on the environment where the transaction is executed.

Depending on transaction semantics, two different transactions executing in the same environment, may well have different correctness requirements. We also find that different correctness requirement may be used within the same transaction. This implies that a transaction may access some objects using a weak requirement, while other objects are accessed using a strong requirement.

ACC is a correctness criterion that guarantees correctness for individual objects by protecting against problems like "lost update", "dirty read", and "unrepeatable read". Additionally, ACC allows each transaction to determine, based on transaction semantics, where "inconsistent retrieval" may be a problem. This will implicitly determine where a group of objects must be used in isolation. ACC guarantees isolation where this is required, while it allows more interleaving for transactions/transaction parts with a weaker correctness requirement.

Two-dimensional locking

Two-dimensional locking is a concurrency control mechanism that supports the ACC correctness criterion. It controls synchronization of transactions in an environment where there may be different correctness requirements both between transactions and within a single transaction. The resulting histories are guaranteed to be correct according to the ACC criterion.

This mechanism introduces some novel features. Firstly, it offers a new type of isolation level, called "Interleave", which allows controlled access to a partially updated database. Isolation level "Interleave" may be used for the whole transaction or for parts of a transaction, and it allows a relatively high degree of interleaving. Choosing "Interleave" means that "inconsistent retrieval" is not a problem, and that access to a partially updated database may consequently be allowed. A stronger isolation level, called "Isolate", is also available. This is used when "inconsistent retrieval" is a problem, and isolation is consequently requested.

Secondly, each lock consists of two separate lock components, which describes different transaction properties. One component reflects the correctness requirement of the transaction, while the second component reflects the effect the transaction has on a particular object. By using lock components for holding different transaction properties, we introduce a new dimension to the locking mechanism. The locks will thus include more information about the transaction, which we utilize to allow early release of locks and possibly a higher degree of concurrency.

Two-dimensional locking allows for a flexible and customized execution of transactions. The user can either choose "Isolate" for the whole transaction, or she can choose to give the transaction a customized correctness requirement which is weaker then the "Isolate" requirement. A relaxed correctness requirement may increase concurrency.

The costs of using Two-dimensional locking is, at least compared to traditional Two-phase locking, more complex locking and recovery methods. Also, by allowing the users to specify correctness requirements for the transaction, we make the user (partly) responsible for database consistency and correctness.

Simulation of Two-dimensional locking

We are currently doing a simulation study that investigates the possible performance gains obtained through the use of Two-dimensional locking. The simulation study compares the performance of Two-dimensional locking with performance of Two-Phase locking (2PL).

When simulating 2PL, every transaction has a strong correctness requirement, and the executions are serializable. For the simulation of Two-dimensional locking, half of the transactions follow a weak correctness requirement, while the others follow a strong requirement. Simulations are done both with short transactions only, and with a combination of long and short transactions. SES/Workbench is used as the simulation tool.

The preliminary results of the simulation study supports our assumption that Two-dimensional locking provides lower response time and higher throughput then 2PL.

Decomposition of transactions

Several transaction models assume decomposition of transactions to a number of subtransactions. This gives a transaction structure that suites some of the new types of applications. A subtransaction is executed atomically, and can be committed or aborted independently of the top-level transaction and other subtransactions. An aborted subtransaction may be re-executed or an alternative subtransaction may be executed. The top-level transaction may thus commit, despite the subtransaction abort.

The subtransaction structure may be used to allow a higher degree of concurrency. In a flat transaction, results of the transaction execution is normally hidden until the final commit of the transaction. In an open nested transaction, a subtransaction may commit and reveal its results to other transactions before the top-level transaction is ready to commit.

We are currently implementing a decomposition algorithm that splits a transaction into a number of subtransactions. The transaction is decomposed before the subtransactions are submitted for execution to an underlying database system. The consequences of decomposing a transaction, with respect to performance, complexity, recovery problems, and others, will be studied.

Compensation of transactions

In case of failure, recovery of transactions are needed. In advanced type of transactions, we often find that compensation is assumed to be one component of the recovery mechanism. A failure during execution of a decomposed transaction T, will often result in a situation where some of the subtransactions are committed, while others are executing or have not started execution yet. To (semantically) undo a committed subtransaction without having cascading abort, a compensating transaction is needed.

We are currently studying how compensating transactions can be specified and implemented as part of an advanced recovery mechanism.

Transaction processing in federative database systems

Federated database systems (FeDBs) facilitate interoperation among heterogeneous and autonomous database systems. In such environments, transaction management is normally performed in two different layers. A local transaction manager is used to control execution of every transaction within one component database. Additionally, a global transaction manager is used for controlling global transactions submitted to the federation, and executed by a number of component databases.

Guaranteeing local autonomy is a difficult problem that effects transaction processing. We can not assume any coordination of transaction management between global and local transaction managers. This makes concurrency control in an FeDB extremely difficult. Also, subtransactions must be allowed to commit independently, and compensation is needed as recovery mechanism. Therefore, advanced transaction management is needed for both commit, recovery, and concurrency control of transactions in an FeDB.

In the AdTrans project, the research activity in this field is now completed. It was the earliest activity of the project, and has lead to the other activities described earlier.

The main focus of this activity was concurrency control for FeDBs, while a second topic was atomic execution of transactions within an FeDB. A new generic correctness criterion, called Partition Serializability (PSR), was proposed. It allows for the specification of a number of non-serializable correctness criteria, where each criterion can be used as a global correctness criterion. PSR supports a location independent partitioning of the object space in an FeDB into consistency units. There are mutual consistency requirements between objects within a consistency unit, while there are no such requirements between objects in different units. To support this, PSR guarantees a strong correctness requirement within a consistency unit, and a weaker correctness requirement between units.

To support PSR, a concurrency control method, called PSR Locking, was described. The correctness of both PSR and PSR Locking was proven. Additionally, several extensions to PSR was presented. Each PSR extension was in it self a generic correctness criterion that could express a variety of specific correctness criteria through instantiations with one or a number of consistency partitions.

 

Related publications