Armin Feßler in cooperation with the I&K Systems Research Group.
We propose a new model and correctness criterion, conflict consistency, for composite transactional systems. Existing theory limits the degree of parallelism, and makes a number of simplifying assumptions which cannot be taken for granted in practice. The main contribution of our new model is to establish the correctness conditions under which higher degrees of parallelism can be achieved between operations of the same transaction, as well as between conflicting operations of different transactions, in a uniform way. This possibility has not yet been exploited in practical composite systems. Hence, we hope to improve the practical impact of many key results in this area.
Unlike most existing systems, where concurrent executions are controlled by a centralized scheduler, we will assume that each element in the system has its own independent scheduler receiving input from the schedulers of other elements and producing output for the schedules of yet other elements in the system. We analyze basic configurations of such composite systems and develop correctness criteria for each case. Moreover, we also show how these ideas can be used to characterize and improve different transaction models such as distributed transactions, sagas, and federated database transactions.
When executing transactions, a scheduler restricts parallelism because it must, first, observe the order constraints between the operations of each transaction and, second, impose order constraints between conflicting operations of different transactions. The restriction in parallelism occurs because, in a conventional scheduler, ordered operations are executed sequentially. This is too restrictive: It is often possible to parallelize concurrent operations even when they conflict as long as the overall result is the same as if they were executed sequentially. This requires to relax some of the ordering requirements of traditional schedulers. In addition, when several schedulers are involved, a mechanism is needed to specify to a scheduler what is a correct execution from the point of view of the invoking scheduler. For these two purposes we use the notion of weak and strong orders (let A and B denote any tasks, i.e., actions or transactions):
Sequential (strong) order: A << B, A has to complete before B starts.
Unrestricted parallel execution: A || B, A and B can execute concurrently equivalent to any order, i.e., A << B or B << A.
Restricted parallel (weak) order: A < B, A and B can be executed concurrently but the net effect must be equivalent to executing A << B.
It follows that turning a weak order into a strong one leads to correct execution since this implies sequential execution. In fact, traditional flat schedulers with only one level of abstraction, do just this, if two tasks conflict they impose a strong order between them. When moving to a composite system with several schedulers, it is often possible to impose a weak order instead of a strong one, thereby increasing the possibility of parallelizing operations. Thus, the aim will be to impose either no orders or only weak orders while still preserving global correctness and characterize the exchange of information between schedulers in terms of these orders.
Consider, for instance, the example in the figure. One transaction is illustrated in which all employees are first awarded a bonus, and then the new average salary is computed. The ordering of these two operations matters. Existing transaction models require ordered operations to be executed serially, the second must wait for the first to complete. However, as illustrated in the example, executions can in this case be interleaved, so long as the serialisation graph is respected at all levels. Hence, transaction t specifies a weak order from Sal-Bonus() to GetNewAverage(), which assures that the serialisation graph will not come out the other way round.
References
Alonso, G., Blott, S., Fessler, A., Schek, H.-J., Correctness and Parallelism in Composite Systems. In: Proc. of the 16th Symp. on Principles of Database Systems (PODS'97), Tucson, Arizona, May 1997.
Gustavo Alonso and Armin Feßler and Guy Pardon and Hans-Jörg Schek, Transactions in Stack, Fork, and Join Composite Systems. In: Proceedings of the ICDT`99, Jerusalem, January 1999.
Armin Feßler, Konfliktkonsistente Serialisierbarkeit für hohe Parallelität. In: 10. Workshop "Grundlagen von Datenbanken", Konstanz, Germany, June 1998.
G. Alonso, A. Fessler, G. Pardon, and H.-J. Schek, Correctness in General Configurations of Transactional Components. In: Proceedings of the ACM Symposium on Principles of Database Systems (PODS'99), Philadelphia, Pennsylvania, USA, May 31 - June 2 1999.
Armin Feßler, Hans-Jörg Schek, A Generalized Transaction Theory for Database and Non-Database Tasks. Europar 99, Toulouse (F), August 1999.
H.-J. Schek, K. Böhm, T. Grabs, U. Röhm, H. Schuldt, and R. Weber, Hyperdatabases. In: Proc. of the 1st Int. Conf. on Web Information Systems Engineering (WISE'00), Hong Kong, China, June 2000.
