Unified Theory For Classical and Advanced Transaction Models Haiyan Hasse, Hans-Jörg Scheck in Object Orientation with Parallelism and Persistence, BurkHard Freitag, Cliff B. Jones, Christian Lengauer, Hans-Jörg Scheck (editors), Kluwer Academic Publishers, 1996
1. Concurrency Control Chceme: − −
Soucasné vykonávání nekolika akcí by nemelo zpusobovat žádná selhání. Soucasné vykonávání nekolika akcí by nemelo být o mnoho pomalejší než jejich postupné vykonávání. Rešíme pomocí zamykání.
1.1 Závislosti Statické zamykání – na zacátku každé transakce se zkontroluje, jestli její vstupy nekolidují s výstupy bežících transakcí, a pokud ano, pocká se. Dynamické zamykání – transakce si za behu zamyká a odemyká co potrebuje a nepotrebuje. Každá transakce je posloupnost operací READ a WRITE. Závislosti mezi transakcemi: READ1(X)-WRITE2(X) 1
WRITE1(X)-READ2(X) WRITE1(X)-WRITE2(X) − − −
Lost update: Udelám zápis, ale nekdo ho prepíše svým zápisem postaveným na datech, která jsem já svým zápisem zneplatnil. Dirty read: Podarí se mi precíst pracovní verzi nejakých dat. Unrepeatable read: Prectu nejakou verzi která je sice platná, ale zatímco s ní budu pocítat, nekdo mi jí prepíše.
1.2 Formálneji Mejme akce READ, WRITE, RLOCK, RWLOCK, UNLOCK, BEGIN, COMMIT, ABORT. Z nich budou složené všechny transakce. Transakce je dobre formovaná (well-formed), pokud jsou všechny akce pokryté odpovídajícími zámky, a pokud je dodržené správné párování operací LOCK a UNLOCK. Transakce je dvoufázová (two-phase) (Pozor! Neplést s dvoufázovým commitem!), pokud jsou všechny operace LOCK pred všemi operacemi UNLOCK. Definujme historii (nekdy se také používá oznacení rozvrh) jako posloupnost trojic
. Historie popisuje možný zpusob soucasného vykonání zúcastnených transakcí. Sériová historie (serial history) je historie, která vznikla prostým serazením transakcí za sebou. Taková historie je zjevne bezproblémová vzhledem k paralelismu. Historie je legální (legal history), pokud popisuje proveditelný postup zamykání (tedy nejsou v ní konflikty zámku podle tabulky kolizí zámku). Definujme závislosti (dependencies) historie jako množinu trojic , kde T2 bezprostredne závisí na hodnote daného objektu zapsané T1, nebo kde T1 cte hodnotu bezprostredne pred její zmenou T2 (formálne: existuje i, j takové, že T1 je v kroku i, T2 v kroku j, v historii není zápis do objektu mezi kroky i a j, a operace T1[i] a T2[j] jsou bud WRITE a WRITE, WRITE a READ, nebo READ a WRITE objektu). Pokud mají dve historie stejné závislosti, jejich transakce zjevne operují s týmiž verzemi dat, a tedy skoncí se stejným výsledkem – v takovém prípade se rekne, že historie jsou ekvivalentní. Historie je izolovaná (isolated), pokud je ekvivalentní sériové historii. Takové historie nás zjevne zajímají – nejsou v nich žádné cykly v grafu závislostí a tudíž ani žádné konflikty.
2
Relace "casového usporádání" nad transakcemi: T1 <<< T2 práve když EX obj: IN DEP(H), nebo totéž tranzitivne. Polopaticky, T1 <<< T2 pokud T2 závisí na T1. Hodí se ješte BEFORE(T): {TT, TT <<< T} a AFTER(T): {TT, T <<< TT} (což v podstate intuitivne vyjadruje význam relace <<<). A definujeme wormhole jako takový pár transakcí, kde T <<< TT a TT <<< T. Zjevne wormholes porušují izolaci transakcí. Zajímavá tvrzení: 1. Historie je izolovaná práve pokud neobsahuje wormholes (Chyba! Nenalezen zdroj odkazu. - Wormholes). 2. Pokud jsou transakce dobre formované a dvoufázové, jakákoliv legální historie z nich sestavená bude izolovaná (Chyba! Nenalezen zdroj odkazu. - Locking). 3. Pokud transakce není dobre formovaná, nebo není dvoufázová, pak je možné k ní napsat jinou dobre formovanou dvoufázovou transakci a sestavit historii s wormhole (krome degenerovaných transakcí) (Chyba! Nenalezen zdroj odkazu. - Converse Locking).
2. Unifikovaná teorie pro concurrency a recovery 2.1 Tradicní pohled jinými slovy −
Databáze je soubor objektu, se kterými se muže manipulovat pomocí operací, které jsou soucástí nejakých transakcí.
−
Transakce Ti je cástecne usporádaná množina operací relací
−
Operace jsou konfliktní, pokud patrí ruzným transakcím, manipulují se stejným objektem v databázi a jedna z nich je write.
−
Historie (nebo rozvrh) je cástecné usporádání S s relací <S operací v transakcích patrících do tohoto rozvrhu; usporádání každé transakce je podmnožinou usporádání rozvrhu, neboli
−
Rozvrh je sériový, pokud se neprokládají operace jednotlivých transakcí, tedy pro každé dve transakce Ti a Tj platí, že pro každé dve operace oi ∈ Ti, oj ∈ Tj platí oi <S oj.
3
−
Dva rozvrhy jsou konflikt-ekvivalentní, pokud jsou definovány nad stejnými transakcemi a operacemi a mají stejnou množinu konfliktních operací.
−
Commitovaná projekce rozvrhu obsahuje pouze transakce, které koncí operací commit.
−
Rozvrh je serializovatelný (SR), pokud jeho commitovaná projekce je konfliktekvivalentní nejakému sériovému rozvrhu. Je známo, že rozvrh je serializovatelný, práve když jeho závislostní graf je acyklický.
−
Transakce Ti cte x z jiné transakce Tj, pokud wj(x) <S ri(x) a neexistuje wk(x) takové, že wj(x) <S wk(x) <S ri(x).
−
Rozvrh je recoverable (RC), pokud pro každé dve transakce Ti a Tj takové, že Ti cte x z Tj a Ti commituje, pak Tj commituje pred Ti.
−
Rozvrh predchází kaskádovým abortum (ACA), pokud pro každé dve transakce Ti a Tj takové, že Ti cte x z Tj, pak cj <S ri(x).
−
Rozvrh je striktní (ST), pokud kdykoliv wj(x) <S oi(x), i ≠ j, bud aj <S oi(x) nebo cj <S oi(x), kde oi(x) je ri(x) nebo wi(x).
−
Rozvrh je rigorózní (RG), pokud je striktní a navíc žádný objekt nemuže být prepsán, dokud transakce, který ho predtím cetla, neskoncí (tj. provede commit nebo abort), tj. když rj(x) <S wi(x), i ≠ j, pak bud aj <S wi(x) nebo cj <S wi(x).
−
Platí RG ⊂ ST ⊂ ACA ⊂ RC. Trída SR není s temito trídami porovnatelná a pouze se ví, že RG ⊂ SR.
2.2 Strucný úvod do semantics-based concurrency control
2.3 Unifikovaný model Unifikovaný model transakcí navržený v [2] stojí na techto základních principech: − − −
Operace jsou definovány na abstraktních datových typech (ADT) a ke každé do operaci existuje undo operace, která vrátí zpet efekty zpusobené operací do. Všechny operace související se zotavením (recovery) jsou v transakci prítomné (tedy i v rozvrhu) ve forme príslušných undo operací. Serializovatelnost rozvrhu se zkoumá vzhledem ke komutativite do a undo operací, neboli zkoumá se soucasne schopnost zotavení.
4
2.3.1 Operace Databáze DB je množina abstraktních datových typu D a množina operací O nad temito datovými typy (ríkame jim forward operace). Existují dve speciální operace – commit a abort (znacíme c a a). Pro každou operaci o (vyjma c a a) existuje undo nebo backward operace o-1, tedy existuje množina O-1 všech undo operací k operacím z O. Operace vracejí hodnotu, která je funkcí zmeny, takže napr. read(x) vrací hodnotu x a write(x) vrací hodnotu, která byla prepsána hodnotou x. α = p1p2p3… pn je sekvence operací. Undo operace by mela následovat jedine za príslušnou do operací. Ríkáme, že sekvence operací nad O ∩ O-1je dobre formovaná, pokud každá undo operace následuje až za príslušnou do operací. Pokud je s0 iniciální stav databáze, pak každý další stav s je generován sekvencí operací α, neboli s = s0α. Dva stavy s1 = s0α1a s2= s0α2 sou ekvivalentní, práve když pro každou dobre formovanou sekvenci operací β jsou návratové hodnoty operací z β aplikované na s1stejné jako když jsou aplikované na s2. Sekvence operací σ je effect-free, pokud pro všechny sekvence α a β takové, že sekvence ασβ i αβ jsou dobre formované, platí že návratové hodnoty operací v sekvenci β jsou stejné v sekvenci ασβ a v sekvenci αβ.
2.3.2 Komutativita Dve operace p a q z O ∩ O-1 komutují, práve když pro všechny sekvence α a β z O ∩ O-1 takové, že αpqβ a αqpβ jsou dobre formované, jsou návratové hodnoty operací z β v sekvenci αpqβ stejné jako v sekvenci αqpβ. read
write
Read-1
Write-1
read
+
-
+
-
write
-
-
+
-
read-1
+
+
+
+
write-1
-
-
+
-
Tabulka 1: Tabulka komutativity pro klasický read/write model insert
delete
test
Insert-1
Delete-1
test-1
insert
-
-
-
-
-
+
delete
-
-
-
-
-
+
test insert
-
-
+
-
-
+
-1
-
-
-
+
-
+
-1
-
-
-
-
+
+
+
+
+
+
+
+
delete -1
test
5
Tabulka 2: Tabulka komutativity sémanticky bohatých operací
2.3.3 Rozvrhy Dve operace p a q jsou konfliktní, práve když p a q nekomutují a patrí ruzným transakcím. Rozvrh je serializovatelný pokud jeho commitovaná projekce je konflikt-ekvivalentní nejakému sériovému rozvrhu.
2.3.4 Rozšírené rozvrhy Necht S = (A, <S) je rozvrh, kde A množina operací a <S je cástecné usporádání techto operací. Rozšírením rozvrhu budeme nazývat takový rozvrh S' = (A', <S'), že: 1. A' je množina operací odvozených z A takto: − Pro každou transakci Ti ∈ A, pokud oi ∈ Ti a oi není abort, pak oi ∈ A'. − S aktivními transakcemi je nakládáno jako s abortovanými, jsou abortovány pridaným skupinovým abortem a(Ti1, … , Tik), který je maximálním prvkem A'. − Pro každou abortovanou transakci Tj ∈ A a všechny operace oj ∈ Tj existují undo operace oj-1 ∈ A'. Abort operace aj ∈ A je zmenen na c ∈ A'. Operace a(Ti1, … , Tik) je nahrazena sekvencí ci1, … , cik. 2. Cástecné usporádání <S' je definováno následujícím zpusobem: − Pro každé dve operace oi a oj, pokud oi <S oj, pak oi <S' oj. − Když transakce Ti a Tj abortují v S, a jejich aborty nejsou usporádané relací <S, pak každé dve konfliktní undo operace transakce Ti jsou usporádané <S' v opacném poradí než jejich príslušné do operace v S. Pokud do operace nejsou usporádané relací <S, pak jsou tyto dve undo operace v libovolném poradí, neboli nejsou usporádané <S'. − Všechny undo operace transakce Ti, která necommituje v A, následují puvodní operace z transakce a musí predcházet pred commitem transakce Ti podle relace <S'. − Pokud on <S a(Ti1, … , Tik) a nekterá undo operace oj-1 (j ∈ i1, … ., ik) je konfliktní s on, pak on <S' oj-1. − Když ai <S aj pro i ≠ j a oi-1 je konfliktní s oj-1, pak oi-1 <S' oj-1.
2.3.5 RED a PRED Rozvrh je reducibilní (RED), pokud k nemu existuje alespon jeden rozšírený rozvrh S' takový, že muže být transformován do serializovatelného rozvrhu pomocí jednoho ze dvou následujících pravidel: 1. Pravidlo komutativity: Když jsou oi a oj operace v S' z ruzných transakcí takové, že oi <S' oj, oi komutuje s oj a neexistuje žádná operace p taková, že oi <S' p <S' oj, pak muže být usporádání oi <S' oj nahrazeno usporádáním oj <S' oi. 2. Pravidlo undo: Když jsou o a o-1 operace v S' takové, že neexistuje žádná operace p taková, že oi <S' p <S' oj, pak mohou být o a o-1 vymazány z rozvrhu S'.
6
Poznámka: V rozšírených rozvrzích tedy nejsou operace abort, všechny transakce jsou commitovány. Pravidla 1 a 2 platí pro všechny operace krome operace commit. Príklad: Uvažujme rozvrh S1: delete1(x) insert2(x) test3(x) c2 a3. Jeho expanze v S1': delete1(x) insert2(x) test3(x) c2 test3-1(x) c3 delete1-1(x) c1 není reducibilní, protože delete1(x) <S' insert2(x) <S' delete1-1(x), takže je v rozšíreném rozvrhu cyklická závislost, které se nelze zbavit. Rozvrh S2: delete1(x) insert2(x) test3(x) c2 c1 a3 s expanzí S2': delete1(x) insert2(x) test3(x) c2 c1 -1 test3 (x) c3 je reducibilní, protože v rozšíreném rozvrhu není cyklická závislost. Rozvrh S = (A, <S) je prefix reducibilní (PRED) pokud je každý prefix S reducibilní. Príklad: S2 z predchozího príkladu není prefix reducibilní (protože prefix delete1(x) insert2(x) test3(x) c2 není reducibilní). Oproti tomu rozvrh S3: delete1(x) insert2(x) test3(x) c1 c2 a3 je prefix reducibilní. Trídu prefix reducibilních rozvrhu považujeme za trídu rozvrhu zajištujících atomicitu transakce a serializovatelnost transakcí.
2.4 Unifikovaný model pro READ/WRITE operace 2.4.1 Vztahy ke klasické teorii Je zjevné, že platí PRED ⊂ RED. Dále platí RG ⊂ SR-ST ⊂ PRED Platí PRED ⊂ SR-RC.
2.4.2 PRED = SOT Rozvrh S je SOT (serializable with ordered termination) pokud je 1. serializovatelný, 2. recoverable a pro každou dvojici konfliktních operací oi(x) <S oj(x), oj(x) <S ti, ti ∈ {a,c} platí, že − když Tj(x) commituje, pak commituje po Ti(x) − když Ti abortuje, pak abortuje poté co abortuje Tj, nebo S obsahuje skupinový abort a(..., Ti, ..., Tj, ...). Výše uvedená definice má dve cásti. První z nich je o serializovatelnosti – tedy garantuje korektní provedení commitovaných transakcí v rozvrhu. Druhá cást – o isoloted recovery – zavádí restrikce toho, v jakém poradí mohou transakce skoncit. Tyto restrikce se použijí jen pokud nastává konflikt v read/write modelu, tj. jeden z konfliktu rw, ww, wr. S1 = w1(x) w2(x)
S2 = w1(x) r2(x)
1
w1(x) w2(x) a1 a2 ∉ PRED
1
w1(x) r2(x) a1 a2
∈ PRED
2
w1(x) w2(x) a1 c2 ∉ PRED
2
w1(x) r2(x) a1 c2
∉ PRED
3
w1(x) w2(x) c2 c1 ∉ PRED
3
w1(x) r2(x) c2 c1
∉ PRED
7
4
w1(x) w2(x) c2 a1 ∉ PRED
4
w1(x) r2(x) c2 a1
∉ PRED
5
w1(x) w2(x) a2 a1 ∈ PRED
5
w1(x) r2(x) a2 a1
∈ PRED
6
w1(x) w2(x) a2 c1 ∈ PRED
6
w1(x) r2(x) a2 c1
∈ PRED
7
w1(x) w2(x) c1 c2 ∈ PRED
7
w1(x) r2(x) c1 c2
∈ PRED
8
w1(x) w2(x) c1 a2 ∈ PRED
8
w1(x) r2(x) c1 a2
∈ PRED
Tabulka 3: Možné kombinace ukoncovacích operací rozvrhu S1 a S2 Z toho plyne, že SOT = PRED.
2.5 Unifikovaný model pro sémanticky bohaté operace 2.5.1 Reducibilní rozvrhy Necht S je rozvrh a S' jeho rozšírení. Pro popis reducibility rozvrhu S vytvoríme graf reducibility RG(S') následujícím zpusobem: Uzly grafu jsou všechny operace z S'. Pokud oi ∈ Ti <S – predchází oi z Tj (i ≠ j) a oi je konfliktní s oj, pak RG(S') obsahuje hranu . Platí: Dve operace oi, oi-1 mohou být vypušteny z rozšíreného rozvrhu S' pomocí pravidla komutativity práve když neexistuje mezi nimi cesta v RG(S').
1. Pro S' sestroj RG(S'). 2. Najdi v RG(S') dvojici uzlu oi a oi-1 takovou, že mezi nimi není cesta. 3. Když taková dvojice neexistuje a S' obsahuje nekteré zpetné operace, pak není rozvrh S reducibilní a procedura koncí. Pokud dvojice neexistuje a S' neobsahuje zpetné operace, pak procedura koncí. 4. Když taková dvojice existuje, smaž dvojici uzlu spolu se všemi incidencními hranami z RG(S') a smaž dvojici z S'. 5. Pokracuj podle 2. Pokud jako výsledek procedury získáme serializovatelný rozvrh s pouze doprednými operacemi, pak je S reducibilní. V opacném prípade není S reducibilní. Príklad: Uvažujme rozvrh S3: insert1(x) delete2(x) insert3(x) a1 a2 a3. Jeho rozšírením je S3' = insert1(x) delete2(x) insert3(x) insert1-1 (x) delete2-1 (x) insert3-1 (x) c1 c2 c3. Pokud bereme postupne všechny dvojice po sobe jdoucích operací, jsou vždy konfliktní. Graf reducibility pro S3' obsahuje cestu (insert1(x) delete2(x) insert3(x) insert1-1 (x) delete2-1 (x)), což je cesta mezi doprednou a k ní zpetnou operací a tudíž není S3 reducibilní. Jiný príklad: Uvažujme rozvrh S4: delete1(x) delete2(x) delete3(x) a1 a2 a3. Jeho rozšírením je S4' = delete1(x) delete2(x) delete3(x) delete1-1 (x) delete2-1 (x) delete3-1 (x) c1 c2 c3. delete1(x) je konfliktní s delete2(x), delete2(x) je konfliktní s delete3(x), delete3(x) je konfliktní s delete1-1. Graf reducibility S4' neobsahuje cestu mezi delete3(x) a delete(x)3-1 protože delete(x)-1 komutuje sama se sebou. delete3(x) a delete(x)3-1 tedy mohou být eliminovány z grafu. Zbylé 8
dva páry (delete1(x) a delete(x)1-1 delete2(x) a delete(x)2-1) mohou být z grafu eliminovány podobne. Proto je S4 reducibilní.
2.5.2 PRED ≠ SOT Definujme SOT pro množinu sémanticky bohatých operací O: Rozvrh S je SOT (serializable with ordered termination) pokud je serializovatelný a pokud pro každé dve transakce Ti a Tj a každé dve operace oi ∈ Ti, oj ∈ Tj, takové, že oi <S oj, ai nepredchází oj v S, oi je konfliktní s oj a oi-1 je konfliktní s oj a platí: 1. Když Tj commituje v S pak Ti také commituje v S a ci <S cj. 2. Pokud je oi-1 je konfliktní s oj -1 a Ti abortuje v S pak Tj také abortuje v S a bud aj <S ai nebo a(...,Ti, ..., Tj, ...) ∈ S. Platí PRED ⊂ SOT.
2.5.3 Bezpecné rozvrhy − −
Operace o2, ..., ok nejsou konfliktní s o1 a tedy jejich efekt není ovlivnen návratovou hodnotou o1. Pak muže o1 být presunuta k o1-1 a celá dvojice muže být odstranena z rozvrhu pomocí pravidla undo. Operace o1-1 komutuje s každou operací z o2, ..., ok. Pak muže o1-1 být presunuta k o1 a celá dvojice muže být odstranena z rozvrhu pomocí pravidla undo.
Rozvrh je dopredne bezpecný (forward safe, FSF) (zpetne bezpecný (backward safe, BSF)) práve když pro každé dve transakce Ti a Tj a každé dve operace oi ∈ Ti, oj ∈ Tj, takové, že oi <S oj, ai nepredchází oj v S, oi (oi-1) je konfliktní s oj platí: 1. Když Tj commituje v S pak Ti také commituje v S a ci <S cj. 2. Pokud Ti abortuje v S a oj-1 ≠ λ, pak Tj také abortuje v S a bud aj <S ai nebo a(...,Ti, ..., Tj, ...) ∈ S.
Existují dopredne bezpecné rozvrhy, které nejsou zpetne bezpecné a naopak. Príklad: Uvažujme rozvrh S1: test1(x) insert2(x) a2 a1. Protože insert(x) je konfliktní s test(x), ale test1-1(x) komutuje s insert(x), rozvrh je zpetne bezpecný, ale není dopredne bezpecný. S: test1(x) insert2(x) test2(x) insert1(x) c1 c2 je zpetne bezpecný, ale není serializovatelný. Naopak, každý dopredne bezpecný rozvrh je serializovatelný. Trída dopredne bezpecných rozvrhu FSF a trída serializovatelných zpetne bezpecných rozvrhu BSF-SR jsou vlastními podtrídami PRED, neboli FSF ⊂ PRED, BSF-SR ⊂ PRED.
9
2.5.4 Perfektní komutativita Relace komutativity je perfektní, pokud pro každé dve operace p a q bud pα komutuje s qβ provšechny možné kombinace α, β ∈ {-1, 1} nebo pα nekomutuje s qβ pro všechny možné kombinace α, β ∈ {-1, 1} s výjimkou zpetných operací λ, které komutují se vším. Platí: Necht je relace komutativity perfektní. Pak. je rozvrh prefix reducibilní práve když je SOT.
3. Použitá literatura [1] Jim Gray, Andreas Reuter, Transaction Procesing: Concepts and Techniques, Morgan Kaufmann Publishers, 1993 [2] Haiyan Hasse, Hans-Jörg Scheck, Unified Theory For Classical and Advanced Transaction Models, in Object Orientation with Parallelism and Persistence, BurkHard Freitag, Cliff B. Jones, Christian Lengauer, Hans-Jörg Scheck (editors), Kluwer Academic Publishers, 1996 [3] Hans-Jörg Scheck, G. Weikum, H. Ye: Towards A Unified Theory of Concurrency Control and Recovery, Proc. ACM Principles of Database Systems, 1993
10
