Advanced Transaction Models

'LGLHU'RQVH]
8QLYHUVLWp-RVHSK)RXULHU *UHQREOH
,0$,0$*/65$'(/(
'LGLHU'RQVH]#LPDJIU
'LGLHU'RQVH]#LHHHRUJ

Donsez, 1997-2004,Advanced Transaction Models 1

 
2

Summary

■ Flat Transaction Model

■ Advanced Transaction Models
• Close Nested Transactions
• Open Nested Transactions
• Long-Lived Transactions
• ACTA
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• ASSET
 
3

Flat Transactions

■ Supports ACID Properties

• Atomicity – all-or-nothing process
• Consistency – system in consistent state
• Isolation – not affected by other
• Durability – once committed, effects persist
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ One transaction level

 
4
Flat Transactions
One transaction level

T1

A1 A2 A3 A4 A6 A7
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

T1

A1 A2 A3 A4 A6 A7
 
5

Flat Transactions Problems

■ Long transaction’s work lost on failure before EOT

■ Long transaction cause concurrency conflicts
■ Collaboration between transactions not supported
■ ACID transaction recover data, but not activities
(appl. state)
■…
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV
 
6
Cooperation
in building and civil engineering

recomm
endation
City planner
architect

map window
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

security
engineer

thermic
structur engineer
engineer
 
7

MultiPurpose Internet Shopping Cart

■ MultiPurpose Internet Shopping Cart

• Multiple purchases in several Web stores
• 1 sombr er o @ www.hat .com
• 1 poncho @ www.coat .com

■ Purchase rules
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• All baskets are managed by a client application

• No shared baskets between
www.hat.com and www.coat.com
• No Global TPM (since Multi Vendor, …)
• All or None items are purchased
 
8

MultiPurpose Internet Shopping3XUFKDVH

Cart

www.hat .com

<RXU%DVNHW
1 sombr er o
W#ZZZKDWFRP
1 poncho
W#ZZZFRDWFRP
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

3XUFKDVH
%X\7ZR
www.coat .com
3XUFKDVH
RUQRQH

3XUFKDVH 
 
9

MultiPurpose Internet Shopping Cart

3XUFKDVH 
Embedded (SmartCard) Transaction Monitor
www.hat .com
At Of f ice

At Home
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

<RXUV6KRSSLQJ%DVNHWV www.coat .com

3XUFKDVH
%X\7ZR  1 sombr er o
3XUFKDVH
RUQRQH W#ZZZKDWFRP
1 poncho
W#ZZZFRDWFRP

3XUFKDVH 
 
10

Embedded Transaction Monitor

■ Multi-Basket application is embedded in the SC

• Requires secure transactional completion
• avoid repudiation
• Need of trust (holder point of view)
☞ Transactional Monitor embedded in SC
• Commit if all products are available
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• abort and rollback else

■ Since 2PC may blocked the resources
• BTP completion protocol
 
11

Advanced Transaction Models (ATM)

■ Models
• Close Nested Transactions (in PEPiTA)
• Open Nested Transactions (in PEPiTA)
• Long-Lived Transactions
• Sagas
• Split
• DOM
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• Contract, …
■ Formalism
• ACTA
■ TM
• ASSET, …
 
12

Close Nested Transactions

■ Hierarchy of Transactions T1 Top-level

(Multi-Level) trans
• a parent tran can spawn T12
T11 sub trans
any # of child tran Operation
• any # of children may T111 T112
be active concurrently
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ Top-level transaction
guarantees ACID properties
■ Child transaction
guarantees AI properties
inside the top-level transaction
 
13

Close Nested Transactions

❚ Validation rules for a nested transaction

❙ A child is fired after start of parent trans start and stop
before the parent trans termination
❙ Commit of child relative to parent
❘ On parent abort, even updates of committed children undone
❘ Updates persist only if all ancestors commit
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

❙ Parent can commit only after all its children terminate

(commit/ abort)
❚ About resources
❙ Parent can’t access data when its children are alive
❙ A child can inherit a lock held by any ancestor
 
14

CNT - Example

T111 T112

T11 T12

T1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

A1 A2 A3 A4 A5 A6 A7 A8
 
15

CNT in OTS

LQWHUIDFH,$FFRXQW ^
LQWJHW%DODQFH 
YRLGFUHGLW LQW DPRXQW 
YRLGGHELW LQWDPRXQW 
`
FODVV$FFRXQWLPSOHPHQWV,$FFRXQW ^
LQWQXP
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

LQW EDODQFH
LQWJHW%DODQFH ^UHWXUQEDODQFH`
YRLGFUHGLW LQWDPRXQW ^EDODQFH DPRXQW`
YRLGGHELW LQWDPRXQW ^EDODQFH DPRXQW`
`
 
16

CNT in OTS

FXUUHQWEHJLQ  EHJLQDWRSOHYHO7
DFF7UJFUHGLW   FDOOHGZLWKLQ7
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
DFF6UFGHELW   FDOOHGZLWKLQWKHQHVWHG7
LI  ^
FXUUHQWFRPPLW  FRPPLWWKHQHVWHG7
`HOVH^
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

FXUUHQWDERUW  DERUWWKHQHVWHG7
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
DFF6UFGHELW   FDOOHGZLWKLQWKHQHVWHG7
FXUUHQWFRPPLW  FRPPLWWKHQHVWHG7
`
FXUUHQWFRPPLW  FRPPLWWKHWRSOHYHO7
 
17

Open Nested Transactions

■ Relax the Isolation requirements

• Update of committed subtrans are visible by all transactions
even the top-level transaction is not completed (commit or
abort)

■ Usages
• Improves concurrency
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• No XA Resource Manager (RPC, Legacy DBMS, Web Site

…)
• No global 2PC coordinator (BWTP)
• Risk of blocking phase in 2PC (Nomadic)
• …
 
19

Open Nested Transactions

■ Multi-Level Transaction Model

• Each level does its own logging and concurrency control
• Rule of an ONT commitment
• After ONT commitment, all update are globally visible by top-Level
Transactions.
• Rule of an ancestor’ abort
• A compensating operation is fired to undo semantically the ONT
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

effects
A compensation operation can be null
A compensation operation can be done in a transactional scope
» one transaction
» or several transactional until commit (cf SAGA)
 
20

ONT - Example

Operation to compensate
OT111 is fired
OT111 NT112

NT11 NT12
25
TopT1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

A1 A2 A3 A4 A5 A6 A7 A8
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV


ONT
21
 
22
ONT
Questions about Compensation
■ When compensation operation C1.1.1 is fired
• At T1.1 abort
■ Is compensation a blocking or non-blocking
operation
• Is the T1.1 abort complete until the C111 completion ?
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• If C111 is in the scope of a transaction,

• C111 completion may be a commitment ?
• C111 completion may be an abort ?
 
23

ONT - Blocking Compensation

Operation to compensate
OT111 is fired
OT111 NT112

NT11 NT12

TopT1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

A1 A2 A3 A4 A5 A6 A7 A8
 
24

ONT - Non-Blocking Compensation

Operation to compensate
OT111 is fired
OT111 NT112
Compensation is
completed
NT11 NT12

TopT1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

A1 A2 A3 A4 A5 A6 A7 A8
 
25
ONT
Questions about Lock Releasing (in RM)

• Locks on R are granted to T1.1

• When locks granted to T1.1.1 are released ?
• S(hared) or e(X)clusive locks on a resource R
• Then what’s happen : Several hypothesis

T1.1.1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

T1.1 None Shared eXclusive

None T1 keeps S? N? T1 keeps X? S? N?
Shared T1 keeps S T1 keeps S T1 keeps X? S?
eXclusive T1 keeps X T1 keeps X? S? T1 keeps X
 
26
ONT in MAAO
(INRIA, Sedillot Team)

■ Begin as a nested transaction

■ Commit with the ONT semantic
• operation definite_commit(
in boolean report_heuristics,
in Compensator c
)
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• interface Compensator {
void compensate();
}
 
27

ONT in MAAO

FRPSHQVDWHWKH'HELWRSHUDWLRQ

FODVV'HELWB&RPSHQVDWRULPSOHPHQWV&RPSHQVDWRU^
$FFRXQWDFFRXQW
LQW DPRXQW
'HELWB&RPSHQVDWRU $FFRXQWDFFRXQWLQW DPRXQW ^
WKLV!DFFRXQW DFFRXQWWKLV!DPRXQW DPRXQW`
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

YRLGFRPSHQVDWH ^$FFRXQWDFF «
DFF!EDODQFH DPRXQW`
`
 
28

ONT in MAAO

FXUUHQWEHJLQ  EHJLQDWRSOHYHO7
DFFWUJFUHGLW   FDOOHGZLWKLQ7
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
DFF6UFGHELW   FDOOHGZLWKLQWKHQHVWHG7

&RPSHQVDWRUFRPS QHZ'HELWB&RPSHQVDWRU DFF6UF 

FUHDWLRQRIDFRPSHQVDWLRQREMHFW
FXUUHQWGHILQLWHBFRPPLW QLOFRPS 
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

FRPPLWWKHQHVWHG7ZLWK217FRPPLWVHPDQWLF
LI  ^
FXUUHQWFRPPLW  FRPPLWWKHWRSOHYHO7
`HOVH^
FXUUHQWDERUW  DERUWWKHWRSOHYHO7
DQGFRPSHQVDWHWKHFRPPLWWHG217
`
 
29

Cascade of ONT

FXUUHQWEHJLQ  EHJLQDWRSOHYHO7
«
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
DFF7UJFUHGLW   FDOOHGZLWKLQ7

FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
DFF6UFGHELW   FDOOHGZLWKLQWKHQHVWHG7
&RPSHQVDWRUFRPS QHZ'HELWB&RPSHQVDWRU DFF6UF 
FXUUHQWGHILQLWHBFRPPLW QLOFRPS FRPPLW7DVDQ217
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

&RPSHQVDWRUFRPS QHZ&UHGLWB&RPSHQVDWRU DFF7UJ 

FXUUHQWGHILQLWHBFRPPLW QLOFRPS FRPPLW7DVDQ217
«
FXUUHQWDERUW  DERUWWKHWRSOHYHO7
DQGFRPSHQVDWHWKHFRPPLWWHG217 DQGWKHQ217"
 
30

Cascade of ONT

■ Scheduling of Compensation
• Which scheduling rules are used to compensate OT1.1 and
OT1.1.1 ?
■ Compensation effect
• Credit_Compensate compensates the whole effects of T1.1 ?
• i.e acctrg.debit(1000) and accsrc.credit(1000)
• or only the effects of T1.1 and CNT without T1.1.1 ones ?
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV
 
31
Ordering and Scheduling of ONT
Compensation
■ Problem
• Parallel/Distributed OTs in a transaction (top-level or sub)
• OT1.1 and OT1.2 in T1
■ Scheduling of Compensation
• OT1.1 begins before OT1.2
• but OT1.1 can commit before OT1.2
• but OT1.2 can complete before OT1.1
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• Which scheduling rules are used to compensate OT1.1 et

OT1.2 ?
• C1.1 and C1.2 are fired together
• or C1.1 (resp C1.2) is fired after the C1.2 (resp 1.1) completion
• or C1.1 (resp C1.2) is fired after the C1.2 (resp 1.1) commitment
if C1.1 aborts, C1.1 is restarted until commitment ?
 
32

Sagas with ONT

■ Questions
• Ordering and Scheduling of Compensating transactions
• must be kept in the OTS’ mind
• Global time begins order, Global time ends order, other ordering (bean
developer decides)?

• Does it done in MAAO ?

'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV
 
33

Sagas

■ Sequence of n flat transactions

• S1, S2, … , Sn
■ with n-1 compensating transactions
• C1, C2, … , Cn-1

■ Sk is fired after the Sk-1 commit.

'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ If Sk aborts, the TM fires the sequence of

transactions Ck-1 then … then C2 then C1
 
34

Sagas with ONT

■ Proposition
• A top-level transaction T1 and a sequence of open-nested
transactions
T1.1, T1.2, … , T1.n-1
with compensator C1, C2, … Cn-1.

■ Remarks
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• T1.1, … , T1.n-1 plays as S1, … , Sn-1

• T1 plays as Sn
 
35

Sagas with ONT

• A top-level transaction T1 and a sequence of open-nested

&RPSHQVDWRUFRPS
FXUUHQWEHJLQ 
transactions T1.1, T1.2,EHJLQDWRSOHYHO7
… , T1.n
with compensator C1, C2, … Cn.
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
7LVHTXLYDOHQWWR6ZKRVHSDUHQWLV7
DFFWUJFUHGLW   FDOOHGZLWKLQ7
FRPS QHZ&UHGLWB&RPSHQVDWRU DFFWUJ  FRPSHQVDWRU&
FXUUHQWGHILQLWHBFRPPLW QLOFRPS  FRPPLW217
FXUUHQWEHJLQ  EHJLQDQHVWHG7ZKRVHSDUHQWLV7
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

7LVHTXLYDOHQWWR6ZKRVHSDUHQWLV7
DFFVUFGHELW   FDOOHGZLWKLQWKHQHVWHG7
FRPS QHZ'HELWB&RPSHQVDWRU DFFVUF  FRPSHQVDWRU&
FXUUHQWGHILQLWHBFRPPLW QLOFRPS  FRPPLW217
EHJLQQLQJRI6Q LQ7
DFFVUFGHELW   FDOOHGZLWKLQWKHWRSOHYHO7
FXUUHQWFRPPLW  FRPPLW7HTXLYDOHQWWR6QFRPPLW
 
36

Sagas with ONT

■ Questions
• Ordering and Scheduling of Compensating transactions
• must be kept in the OTS’ mind
• Global time begins order, Global time ends order, other ordering (bean
developer decides)?

• Does it done in MAAO ?

'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV
 
37

Long-Lived Transactions

• Long-duration computation, CWCS

• nomadic and mobile computing
■ Principles of SavePoints (SyncPoint)
• rollback to the last savepoint
• but in case of crash, rollback to the transaction beginning
■ Persistent SavePoints
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• in case of crash, rollback to the last savepoint

• locks are not released by the crash
 
39

ACTA

■ ATM description formalism

• to define effects on transactions and on objects

Effects

on Objects On Transactions
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

visibility conflicts delegation dependency

validation, strong
validation, abort, weak
abort, precedence
 
40
The transaction toolkit
ASSET (ATT & UMASS)
■ Flexible Transaction Framework

■ based on the ACTA formalism

■ Supported ATM
• Nested, Open Nested, Split/Join, SAGA, ...
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ Reference
• A. Billiris, D. Gehani, H. Jagadish, and K. Ramamritham, "ASSET: A System for Supporting Extended
Transactions," Proc. ACM SIGMOD Conf. Management of Data, 1994.
 
41
ASSET
Basic Primitives
■ tid initiate(func,args)
■ begin(tid)
■ boolean commit(tid)
■ wait(tid)
■ abort(tid)
■ tid self()
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ tid parent()
 
42
ASSET
Specific Primitives
■ delegate(WLGBL WLGBM REMBVHW), delegate(WLGBL WLGBM)
• tid_i tranfers to tid_j the responsibility of obj_set (commit)

■ permit(WLGBL WLGBM REMBVHWRSHUDWLRQV), permit(WLGBL WLGBM REMBVHW)

• tid_i allows tid_j to perform operations that conflict
with tid_i operations without forcing tid_j to wait

■ form_dependency(W\SH WLGBL WLGBM)

'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• type = CD (Commit Dep.)

• if both commit, tid_j cannot commit before tid_i
• type = AD (Abort Dep.)
• if tid_i aborts, tid_j must abort
• type = GC (Group Dep.)
• either both tid_i and tid_j commit or neither commits
 
43
ASSET - Example
Flat Transaction

tid t = trans { f(args); }

tid t;
if((t=initiate(f,args)) !=NULL) {
if(begin(t)){
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

commit(t);
}
}
 
44
ASSET - Example
Nested Transaction

tid t = trans { trans { makeairlineresa(); }

trans { makehotelresa(); } }

tid t = initiate(trip); begin(t);commit(t);

void trip(){
tid t1=initiate(makeairlineresa);
permit(self(),t1); begin(t1); if(!wait(t1)) abort(self());
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

delegate(t1,self()); commit(t1);
tid t2=initiate(makehotelresa);
permit(self(),t2); begin(t2); if(!wait(t2)) abort(self());
delegate(t2,self()); commit(t2);
}
 
45
ASSET - Example
SAGA

tid t = trans { trans { f1() } compensating trans { cf1() }

trans { f2() } compensating trans { cf2() }
trans { f3() } }

tid t1, t2,t3; int i=0;

{
t1= initiate(f1); begin(t1); if(!commit(t1)) break; i++;
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

t2= initiate(f2); begin(t2); if(!commit(t2)) break; i++;

t3= initiate(f3); begin(t3); if(!commit(t3)) break; i++;
}
...
 
46
ASSET - Example
SAGA

tid t1, t2,t3; int i=0;

{ t1= initiate(f1); begin(t1); if(!commit(t1)) break; i++;
t2= initiate(f2); begin(t2); if(!commit(t2)) break; i++;
t3= initiate(f3); begin(t3); if(!commit(t3)) break; i++;
}
tid ct1, ct2;
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

switch(i){
case 2: do ct2= initiate(cf2); begin(ct2); while(!commit(ct2));
case 1: do ct1= initiate(cf1); begin(ct1); while(!commit(ct1));
default;
}
 
47

The H-Transaction toolkit

■ Flexible Transaction Framework

• extends ASSET with foolowing primitives
■ sid savework()
■ rollback(sid)
■ restart(tid_i)
■ commit(tid_1, … , tid_n) / abort(tid_1, … , tid_n)
■ cobegin … coend
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ end_trans(tid_i)
■ call_support(tid_j, … , tid_m), permit(tid_i, tid_j, obj_set)
■ thread
■ ...
 
48

The Bourgogne Transaction Model

■ University of Charles (Pragues)

• Presentation 12/12/2000 by Marek Prochazka
■ BTM Extends low level operations to specify
• Abort/Commit Dependency between Transactions
• Resource Sharing
• Resource Delegation
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV
 
49

Bibliography (i)

■ P.A. Bernstein, V. Hadzilacos, and N. Goodman, Concurrency Control

and Recovery in Database Systems. Addison-Wesley, 1987.
• panorama des techniques de contrôle de concurrence et de reprise sur panne
■ J. Gray and A. Reuter, Transaction Processing: Concepts and
Techniques. Morgan-Kaufmann, 1993.
• un autre panorama
■ P. Chrysanthis and K. Ramamritham, "ACTA: A Framework for
Specifying and Reasoning About Transaction Structure and Behavior,"
Proc. ACM SIGMOD Conf. Management of Data, 1990.
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

• la description du formalisme ACTA : des TR plus complets existent

■ E. Moss, Nested Transactions. Cambridge, Mass.: MIT Press, 1985.
• la thèse d’Elliot Moss, un précurseur
 
50

Bibliography (ii)

■ A. Elmagarmid (éditeur), « Advanced Transaction Models for New

Applications », ed. Morgan-Kaufmann, 1992.
• la compilation des travaux majeurs sur les transactions étendues
■ Sushil Jajodia (Editor), Larry Kerschberg (Editor), « Advanced
Transaction Models and Architectures », Ed Kluwer Law International,
June 1997, 1997, ISBN 0-7923-9880-7.
■ "Special Issue on Workflow and Extended Transaction Systems," Data
Engineering, M. Hsu, ed., vol. 16, no. 2, June 1993.
• une autre moins consequente en revue
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV

■ A. Billiris, D. Gehani, H. Jagadish, and K. Ramamritham, "ASSET: A

System for Supporting Extended Transactions," Proc. ACM SIGMOD
Conf. Management of Data, 1994.
• une implantation d’un système transactionnel étendu générique
 
51

Bibliography (iii)
❚ C. Mohan, « Tutorial: Advanced Transaction Models – Survey and
Critique », IBM Almaden Research Center 1995

❚ J. Besancourt, M. Cart, J. Ferrié, R. Guerraoui, P. Pucheral, B.

Traverson, « Les systèmes transactionnels. Concepts, normes et
produits ». Edition HERMES, Paris, 1997
'RQVH]$GYDQFHG7UDQVDFWLRQ0RGHOV