Transaction
processing techniques play a major role in preserving data consistency in
critical areas of computing, from hospital information systems to trading
systems. A transaction maps a database from one consistent state to another by
executing a sequence of operations atomically. Effects of concurrency are
automatically hidden, and failures recovered. Transactions are therefore
appropriate building blocks for structuring reliable systems. The reliability
provided through transactional guarantees are required in many types of
applications, found in for instance workflow systems, mobile systems, web
services based systems, and multidatabase systems.
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.
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. An approach to solve this problem has been to develop transaction models where transactions are structured into sub-transactions, early commit of sub-transaction are allowed, and compensating transaction are provide for recovery purposes.
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.
Our research activity on advanced transaction management includes work on both coordination of distributed transactions, recovery through use of compensation and advanced concurrency control. The most recent work in this project focus on how to provide adaptable transaction services, that can be configured and reconfigured according to the needs of both users and underlying systems.
Current research activities:
Previous research activities:
The characteristics of advanced applications vary a lot and the transaction concept must adapt to fulfil the varying transactional requirements. Required execution guarantees are not limited to traditional ACID properties, and may include for instance timely constraints, execution flexibility and mobile transaction executions. Requirements may not only vary between applications but also between transactions within an application, depending on properties of the transactional task, user preferences and available system resources. Transactional requirements may also change during the lifetime of an application, and the required transaction service will consequently not be fully known at application design time.
We believe that the need for transaction service
flexibility can be supported through reflection, which enables inspection and
modification of system structure and behaviour. We have developed a framework
for such a reflective transactional system,
called Transaction service execution environment (TSenvironment), in
which different transaction services can be deployed and modified, and from
where suitable transaction services can be chosen and concurrently used
according to the needs of the transactions. We have chosen a component-based
approach when describing this framework.
This part of the AdTrans project overlap with the Arctic
Beans Project.
Compensation in web transaction processing
Several transaction models, including web service transaction models, assume transactions that consist of a number of sub-transactions executed at different nodes. In order to preserve autonomy requirements of web services, existing web service transaction models use compensation as a component of recovery. In these models, individual web service invocations may commit early without further coordination, provided that the effect of the invocation can be semantically reversed at some later point by executing a compensating transaction. However, compensating transactions are not focused in the design of web service transaction models or any other transaction model relying on compensating transactions. Providing support for compensating transactions is the topic of this research activity.
We assert that the trigger mechanism, more formally known as Event-Condition-Action rules, may be used to implement support for compensating transactions in an efficient and uniform manner. By building transaction compensation on the trigger mechanism, we allow a web service designer to specify compensation rules, which are used to dynamically generate compensating transactions during runtime. This approach supports both easy and consistent compensation and semi-automatic compensation as seen from the service user.
In this project, we describe a new non-serializable correctness criterion, called ACC. 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, T1 and T2, may well be different.
The motivation behind ACC is the fact that the notion of consistency may be 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.
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 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.
A 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. The simulation study supports
our assumption that Two-dimensional locking provides lower response time and
higher throughput then 2PL.
Transaction processing in multidatabase systems
Multidatabase systems 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 a multidatabases.
Because of the local autonomy requirement, we can not assume any coordination of transaction management between global and local transaction managers. This makes concurrency control in a multidatabase extremely difficult. Also, subtransactions must be allowed to commit independently, and compensation is needed as recovery mechanism. Advanced transaction management is therefore needed for both commit, recovery, and concurrency control of multidatabase transactions.
The main focus of this activity was concurrency control for multidatabase systems. 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 a multidatabase system 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.
A Reflective Transaction Service Framework for Open Applications
Jakobsen, A.B., Karlsen, R., ReflecTS, Technical Report 200451, Department of Computer Science, University of Tromsø, August 2004.An Adaptive Transactional System - framework and service synchronization
Karlsen, R., Proc. of the International Symposium on Distributed Objects and Applications (DOA), Catania, Sicily, November 2003.Towards a Reflective Transactional Middleware Platform for Advanced Applications
Jakobsen, A.B., Karlsen, R., Proceedings of NIK, Norwegian Informatics Conference'2003,
Oslo, November, 2003.Transaction Service Management - An approach towards a reflective transactional service
Karlsen, R., Jakobsen, A.B., Proceedings of the 2nd Workshop on Reflective and Adaptive Middleware,
Rio de Janeiro, Brazil, 2003.Triggger-based compensation in Web Service Environments
Karlsen, R., Strandenæs, T., Proceedings of the 5th International Conference on Enterprise Information Systems,
Anger, France, 23-26 April 2003.Transaction Compensation in Web Services
Strandenæs, T., Karlsen R., Proceedings of NIK, Norwegian Informatics Conference'2002,
Kongsberg, November, 2002.Work in Progress: Arctic Beans, Configurable and Re-configurable Enterprise Component Architectures
Andersen, A., Blair, G., Goebel, V., Karlsen, R., Stabell-Kulø, T., Yu, W., IFIP/ACM International Conference on Distributed Systens Platforms, Middleware 2001, Heidelberg, Germany, November 12-16, 2001.
Also in IEEE Distributed Systems Online, Volume 2, 2001, http://dsonline.computer.org.Arctic Beans: Flexible and Open Enterprise Component Architectures
Andersen, A., Blair, G., Goebel, V., Karlsen, R., Stabell-Kulø, T., Yu, W., Proceedings of NIK, Norwegian Informatics Conference'2001, Tromsø, November 26-28, 2001.Performance of an Adaptable Synchronization Method
Karlsen, R., Hassen, M., Proceedings of NIK, Norwegian Informatics Conference’2000,
Bodø, November 20 - 22, 2000.Reflective Transaction Service
W.Yu , R. Karlsen, Proceedings of Workshop on Reflective Middleware, New York, USA, April 7-8, 2000.Supporting Partial Isolation in Flat Transactions
Karlsen, R., Proceedings of the International Conference on Database and Expert Systems Applications, (DEXA)
T. Bench-Capon, G. Soda, A. Tjoa (eds.), Lecture Notes on Computer Science, LNCS 1677, Springer, 1999.Concurrency Control and Recovery for Partially Isolated Transactions.
Karlsen, R., Proceedings of NIK, Norwegian Informatics Conference’98, Kristiansand,
November 23 - 25, 1998Adaptable correctness through Two-dimensional locking
Karlsen, R., DEXA’97 Workshop, 8th International Conference and Workshop on Database and Expert Systems Applications, Toulouse, France, Sept. 1-5, 1997.Two-dimentional locking, A concurrency control method supporting adaptable correctness
Karlsen, R., Proceedings of NIK, Norwegian Informatics Conference’97, Voss, November 24 - 26, 1997.Flexible Transaction Management in Federated Database Systems
Karlsen, R., Ph.D. thesis, University of Tromsø, Computer Science Department, 1995.Partitioning Global Object Spaces for Multidatabase Concurrency Control
Karlsen, R., Eliassen, F., Proceedings of the ISMM International Conference on Intelligent Information Management Systems, Washington, DC USA, June 1-3, 1994.Application of Partition Serializability in Software Engineering Databases
Larsen, J. O., Eliassen, F., Karlsen, R., Yu, W., Proceedings of NIK, Norwegian Informatics Conference’94, November 14 - 16, 1994.Parameterized Partition Serializability: An Adaptable Correctness Criterion for Federative Transactions
Karlsen, R., Eliassen, F., CS Research Report 94-13, University of Tromsø, 1994.Parameterizing Correctness for Federative Transactions
Karlsen, R., Eliassen, F., Proceedings of NIK, Norwegian Informatics Conference ’93, 1993.Interoperability and Object Identity
Eliassen, F., Karlsen, R., ACM SIGMOD Record, Vol.20, No.4, Dec 1991.Interoperability using Functional and Object-Oriented Programming Concepts: Problems and Solutions
Eliassen, F., Karlsen, R., Proceedings of NIK, Norwegian Informatics Conference ’91, 1991
(also CS Research Report 91-13).Providing Application Interoperability using Functional Programming Concepts
Eliassen, F., Karlsen, R., Proceedings EurOpen Spring Conference 1991, pp. 249-266
(also CS Research Report 90-06).Distributed Exception Handling for Flexible Transactions
Eliassen, F., Karlsen, R., Computer Science (CS) Research Report 90-07, University of Tromsø, 1990.
For more information about the project, contact Randi Karlsen, Department of Computer Science, University of Tromsø, Norway