Rzen soub ezn eho prov ad en transakc

Osnova p redna sky

Sprava soubez neho provad en transakc v prostred bez poruch

zen soube R zneho provad en transakc

2 2

PA 150 Principy operacn ch system u

2

Jan Staudek t http://www. .muni.cz/usr/staudek/vyuka/

2 2 2

}

pesimisticke vs. optimisticke planova ce zamky protokol na bazi zamykan polozek dat protokol na bazi znalosti postupu zpracovan dat (grafovy) protokol na bazi c asovych raztek (porad transakc) protokol na bazi over ovan zachovan serializovatelnosti

Obnovam po poruchach se venuje nasleduj c predna ska

w A| y < 5 4 23 1 0 / -. , )+ ( %&' $ # !"

Æ

Verze : podzim 2016 Jan Staudek, FI MU Brno

Planov an behu soube znych transakc

2

Fakta:

2

Implicitne lze zajistit serializovatelnost soubez nych transakc (presneji plnou seriovost, bohuzel) pouze jejich r esenm formou kritickych sekc

2

X vzajemn a vylu cnost celych transakc { tj. vesmes neefektivn r esen

|

zen soube PA150 { R zneho provad en transakc

1

Soucast TPM je planova c, ktery X X X X

baze dat v prpadech, kdy prslusny plan je kon iktove serializovatelny X izolovanost soubez ne r esenych transakc sdlejcch objekty se mus zajistit explicitne { schematy r zen soubez nosti

Jan Staudek, FI MU Brno


Planov an behu soube znych transakc

X seriov e proveden validnch transakc zachova konzistentnost baze dat X fundamentaln vlastnost transakce je izolovanost X soubez ne proveden (validnch) transakc zachova konzistentnost

2

|

povoluje provad en transakc pouze podle serializovatelnych plan u v prostred s poruchami/vypadky navc podle obnovitelnych plan u a idealn m prpade podle plan u bez kaskadn ho vracen serializovatelnost planu zajist'uje za pochodu (on-line) a pritom mus byt garantovana co nejvyss propustnost (v soubez ne provad enych transakc / jednotku c asu)

Planova ce TPM zajist'uj, z e operace read, write v soubez ne provad enych transakcch se provad ej pouze v prpustnem porad { podle nektereho serializovatelneho planu X bez ohledu na to, jak OS procesum c i vlakn um vyvolavaj cm transakce

prideluje zdroje (napr. CPU)

2


|


3

Metody zajist 'ovan izolovanosti soube znych transakc


2 2 2 2

schemat r zen soubez nosti je vce, z adn e nen NEJLEPS I uzamcen cele DB pro jednu transakci je aplikacne neakceptovatelne Stnove kopie (cast ) DB { zmnme se pouze okrajove Predmetem studia jsou c tyri schemata r zen soubez nosti vybudovana na bazi { zamk u sdlenych promennych { c asoveho r azen transakc pomoc c asovych raztek { omezen porad prstupu ke sdlenym promennym { grafovy protokol zajist'ujc acyklicnost precendence behu transakc { detekce kolize a obnoven behu transakc Jan Staudek, FI MU Brno

|


2

X zamky jsou dvojho typu

{ sdlene, pripoustej nasobnost operac read s vyloucenm operac write do sdlene polozky { exkluzivn { zajist'uj vylu cny prstup transakce k polozce 2

v porad c asovych raztek

X pokud toto porad nelze zajistit

(doslo by napr. ke v c ase zpetnemu zapisu hodnoty polozky) kon iktn transakce krachuje a restartuje se v pozdejsm c ase, s novym c asovym raztkem

4


|


5

Typy planova c u soubehu transakc

Grafovy protokol

2

pesimisticke planova ce, konzervativn prstup X predpokladaj hodne kon iktu, predchaz jim silnou serializac

X aplikovatelna metoda v prpadech, kdy je akceptovatelne

apriori de novat hierarchicke usporad an sdlenych objektu

2

Casov a raztka X kazda transakce ma jedinecne c asove raztko dane dobou jejho vzniku X pri vzniku kon iktu transakce pristupuj ke sdlenym promennym


2

Zamky { zajist'uj pridelen sdlene polozky transakci po dobu nutnou pro zajisten serializovatelnosti

{ stanovenm prpustnych porad prstupu k objektum X zamykac protokoly { typicky 2-fazov e zamykan (zjevne nejpopularn ejs protokol) X protokoly na bazi c asovych raztek (casove r azen bez zamykan ) X grafovy protokol (hierarchicke zamykan)

Detekce kolize a obnova behu X akceptovatelna metoda v prpadech, kdy bez HODNE transakc s prevazujcmi operacemi read a MALO transakc s operacemi write

2

optimisticke planova ce, liberaln ejs prstup X predpokladaj , z e kon iktu je malo, tj. malo transakc zapisuje X malo blokuj behy transakc, ,,nechavaj veci bez et" X kdyz dojde ke kon iktu, tj. zjist se, z e plan nen serializovatelny,

problem kon iktu se r es rusenm a opakovan m kon iktnch transakc X protokol na bazi validace serializovatelnosti planu Jan Staudek, FI MU Brno

|


6


|


7

Zamky, transakcn protokol na bazi zamykan


X nejcastejs forma implementace planova ce transakc 2

2

zamek, lock

X mnozina pravidel vymezujc chovan transakc

zamek { blokovac prvek udrzovany ke kazde datove polozce zamky spravuje spravce zamk u { proces/sluzba TPM zamek lze zamknout a odemknout k datove polozce ma povolen prstup ta transakce, ktera zamkne jej zamek X zamky jsou dvojho typu { sdleny pro read, exkluzitivn pro write a existuj pravidla, kdy lze ten ktery typ zamku zamknout X transakce jsou pomoc zamykan a odemykan zamk u synchronizovane tak, aby jejich u cinky na sdlena data byly ekvivalentn nekteremu jejich seriov emu zpracovan X X X X

2

pri zamykan a odemykan zamk u X omezuje mnozinu moznych plan u na kon iktove serializovatelne plany X zarucuje kon iktovou serializovatelnost, pokud vsechny plany, ktere determinuje, jsou kon iktove serializovatelne 2

X zamknut zamku, zskan zamku, vlastnen zamku, ... X odemknut zamku, vracen zamku, uvolnen zamku, ... |


8



pristupujc k Q mus pred prstupem ke Q zskat od spravce zamk u zamek polozky Q relevantn forme prstupu Ti zamek polozky mu ze uvolnit, tj. vratit ho spravci, po te, co uz nema potrebu prstupu k dane polozce

2

pri ukoncovan nebo krachu transakce

2

roli spravce zamk u pln TPM operace dostupne na API TPM: 2

X lock-S(. . . ) operace zskan sdleneho zamku polozky . . . X lock-X (. . . ) operace zskan exkluzivitnho zamku polozky . . . X unlock(. . . ) operace uvolnen zamku polozky . . .


|



9

10

De facto se jedna o ulohu c tena ri-psari X z ad a-li Ti zajistit pomoc zskan zamku lock-X exkluzivn prstup k Q a jina transakce uz zskala jakykoliv zamek polozky Q, Ti mus c ekat na uvolnen tohoto zamku X z ad a-li Ti provest pomoc zskan zamku lock-S sdleny prstup ke Q a jina transakce uz zskala zamek lock-X polozky Q, Ti mus c ekat na uvolnen tohoto zamku lock-X X z ad a-li Ti provest pomoc zskan zamku lock-S sdleny prstup ke Q a zamek lock-S polozky Q uz zskala jina transakce, Ti zska zamek lock-S te z

X zamky mu ze implicitne uvolnit rovnez TPM 2

|


2 Ti 2

Typy zamk u, rezimy prstupu k datum X Sdleny zamek { (rezim shared, lock − S ) pokud Ti vlastn lock-S polozky Q, mu ze obsah polozky Q c st, ale nesm do polozky Q zapisovat X Exkluzivitn zamek { (rezim exclusive, lock − X ) pokud Ti vlastn lock-X polozky Q, mu ze obsah polozky Q c st a rovnez sm do polozky Q zapisovat

c asto pouzvana synonyma


transakcn protokol na bazi zamykan

Kdyz se transakce stane provedena c i zkrachovala, server (TPM) odemkne transakc explicitne neodemcene zamky


|


11

Transakce s (exkluzivitnmi) zamky


|


Transakce s (exkluzivitnmi) zamky, jiny mo zny plan

12


T1 : lock-X (B); read (B); B:=B–50; write (B); unlock(B);

X mejme 2 transakce T1 a T2 a necht' je inicialn e A=100 a B=200 X T1: read (B); B:=B–50; write (B); read (A); A:=A+50; write (A); T2: read (A); read (B); display(< A + B >); X pri seriov em proveden T1, T2 , resp. T2, T1 bude transakce T2 na konci zobrazovat 300 X Necht' texty programu T1, T2 zajist'uj, z e transakce k datove polozce

pristupuj pouze po zskan jejho prslusneho zamku, napr. : T2 : T1 : lock-S(A); lock-X (B); read (A); read (B); B:=B–50; write (B); unlock(A); unlock(B); lock-S(B); lock-X (A); read (B); read (A); A:=A+50; write (A); unlock(B); unlock(A); display(< A + B >); |



13

Zamky, kdy uvolnit zamek ?



|

14

T2 :

Spravce zamk u: grant-X (B, T1)

lock-S(A); grant-S (A, T2) read (A); unlock(A); lock-S(B); grant-S (B, T2) read (B); unlock(B); display(< A + B >); pokr. na dalsm


|

snmku


15



lock-X (A); read (A); A:=A+50; write (A); unlock(A);

grant-X

2

(A, T1)

X transakce T2 ovsem nezobrazila 300, ale 250 X zamykan polozek pouze na dobu individualn ch prstupu k polozkam

dat neodstran hrozbu nekonzistentnosti, povol plan, ktery nen serializovatelny X problem nekonzistence trivialn e vyres napr. presunut uvolnen zamk u v obou transakcch na konec kodu, tj. na pri prechodu hotove transakce na provedenou povolene plany jsou serializovatelne (viz dals snmek) Jan Staudek, FI MU Brno

|


X Ovsem po pocate cnm soubehu T1 s T2, bude muset T2 c ekat na

uvolnen B (tj. na konec T1) a T1 na uvolnen A (tj. na konec T2)

X v teto aplikaci zskav an /uvolnov an zamk u se skryv a hrozba uvaznut Jan Staudek, FI MU Brno

16

T2 :

2 2

lock-S(A); read (A); lock-S(B);

2 2

lock-X (A); 2

2

2

r esen uvaznut { jedna z transakc mus byt vracena (roll-back) a jej zamky uvolneny (vracen v sobe skryv a hrozbu starnut ) starnut lze zabranovat tm, z e pozadavky na zamky jedne polozky uspokojujeme porad FIFO Jan Staudek, FI MU Brno

|


|


17

Transakcn zamykac protokol

Ilustrace uvaznut

T1 : lock-X (B); read (B); B:=B–50; write (B);

pokrac. { presunut uvolnen zamk u v obou transakcch na konec kodu problem nekonzistence odstran T1 : lock-X (B); T2 : read (B); lock-S(A); B:=B–50; read (A); write (B); lock-S(B); lock-X (A); read (B); read (A); display(A+B); A:=A+50; unlock(A); write (A); unlock(B); unlock(A); unlock(B);

Zamykan polozek pouze na dobu individualn ch prstupu k polozkam dat neodstran hrozbu nekonzistentnosti Potrebujeme protokol r zen soubez nosti transakc indikujc kdy transakce mu ze zamknout a odemknout datovou polozku, aby se dosahlo izolovanosti soubez nych transakc Transakcn zamykac protokol omez pocet moznych plan u Mnozina techto plan u je podmnozinou vsech moznych plan u Nas zajmaj pouze ty transakcn zamykac protokoly, ktere povoluj pouze kon iktove serializovatelne plany, ktere X jsou ekvivalentn nekteremu z jejich seriovych plan u X vzajemn e se se lis pouze poradm proveden nekon iktnch operac

plat, z e operace jsou kon iktn, pokud operuj se stejnou polozkou a alespon jedna z nich je write 18


|


19

Dvoufazov y transakcn protokol na bazi zamykan


2 Two-Phase Locking Protocol, 2

2PLP Jeden z protokolu, ktery zajist'uje kon iktovou serializovatelnost

2

X zskav an zamk u, serializovan transakc podle pravidel:

a) pokud objekt nen zamknuty, zamkne se a transakce pokracuje b) pokud je objekt uzamknuty kon iktnm zamkem jinou transakc, transakce c eka na jeho odemknut c) pokud je objekt uzamknuty nekon iktnm zamkem jinou transakc, objekt se sdl, transakce zska zamek a pokracuje d) pokud je objekt jiz zamknuty stejnou transakc, zamknut se uplatn a transakce pokracuje. (Pokud uplatnen bran kon iktn zamek, pouzije se pravidlo b)

X Pokud nen znam a z adn a dals informace o zpusobu zpracovan dat je

2PLP nutny a postacujc protokol pro zajisten kon iktove serializovatelnosti

2 2

Princip 2PLP { jakmile transakce odemkne nektery zamek, nesm uz zamknout z adn y dals zamek Transakce proto vydav a zamykac a odemykac pozadavky ve 2 faz ch, v zamykac (rustov e) fazi a v odemykac /couvac) fazi


|


2 2

2


21

kaskadn mu vracen lze zabranit tm, z e transakce uvolnuj exkluzivitn zamky az jsou provedene { striktn (strict) dvoufazov y protokol na bazi zamykan X data zapsana neprovedenou transakc jsou exkluzivne zamcena do doby uplatnen commit, takze jine transakce je nemohou c st X jakmile se transakce stane provedena nebo se zrus, TPM odemkne

vsechny objekty dosud zamknute touto transakc

2

pokud se vsechny zamky uvolnuj az pri commit transakce, pak se jedna o prsny (rigorous) dvoufazov y protokol na bazi zamykan X transakce mohou byt serializovane v porad uplatnov an commit

2 zen soube PA150 { R zneho provad en transakc

|


X rustov a faze X couvac faze |

Uvaznut 2PLP neres { zamezen uvaznut lze dosahnout napr. vnucenm pevneho r azen zprstupnovan ych dat Jan Staudek, FI MU Brno

20

vnucenm pevneho r azen zprstupnovan ych dat T1 : T2 : lock-S(B); lock-X (B); read (B); read (B); B:=B–50; lock-S(A); write (B); read (B); display(A+B); lock-X (A); unlock(B); read (A); A:=A+50; unlock(A); write (A); unlock(B); unlock(A);


couvac faze X uvolnov an zamk u { lze provad et POUZE PO poslednm zskan zamku


2

rustov a faze

22

obe tyto verze 2PLP se c asto pouzvaj v komercnch DBS Jan Staudek, FI MU Brno

|


23

2PLP, automaticke generovan zamk u


2

2

Pokud by se exkluzivitn zamky uvolnovaly po proveden posledn operace ale pred prechodem transakce do stavu provedena, plan by byl neobnovitelny:

2

X Drvejs transakce T uvoln sve zamky a zatm neprovede commit. X Mezitm pozdejs transakce U pouzije odemcene objekty a

2

stane se provedenou. X Pote T zkrachuje ale U je jiz provedena a provedla neferov e c ten a nemu ze byt obnovena, ponevadz je jiz provedena


|


if Ti drz zamek D then read(D) else begin je-li to nutne vycka se az z adn a jina transakce nedrz lock-X (D); Ti zska lock-S (D); read(D) end

24

Racionaln potreba konverze sdlenych zamk u na exkluzivitn zamky T2 : T1 : read (A); read (A); read (B); read (B); display(A+B); read (C); write (A); 2 2 2

c isty 2PLP nut T 1 na zacatku zamknout A exkluzivne 2PLP umozn uvolnit zamek A v T 1 po zapisu A T 1 a T 2 nemaj s anci na soubez nost r esenm je umoznit T 1 zamknout A pro read sdlene a posleze pro write povy sit zamek A na exkluzivn Jan Staudek, FI MU Brno

|



|


25

2PLP, konverze zamk u

2PLP, konverze zamk u

2

transakce mohou vydavat instrukce read/write bez z adost o zskan zamk u, pokud proveden instrukc read/write zajist'uje spravce zamk u po implicitn alokaci zamk u vsechny automaticky zskavan e zamky se vrac po proveden/zrusen transakce (prsny protokol) proveden operace read (D): (system provede lock-S(D) az mu ze a pote provede read(D))

26

Ilustrace konverze zamk u { mozny plan (jen locks) T2 : T1 : lock-S (A); lock-S (A); lock-S (B); lock-S (B); lock-S (C); unlock (A); lock-X (A); unlock (B); unlock (A); unlock (B); unlock (C); X navy sen lockS → lockX lze provad et pouze v rustov e fazi, ponz en lockX → lockS pouze v couvac fazi Jan Staudek, FI MU Brno

|


27

2PLP, automaticke generovan zamk u

2

2PLP, ochrana p red kaskadn m vracenm p ri obnove

proveden operace write (D):

2

(system provede lock-X (D), resp. men lock-S(D) na lock-X (D) az mu ze a pote provede write (D)) if Ti drz lock-X (D) then write(D) else begin je-li to nutne vyckan az z adn a jina transakce nedrz z adn y zamek polozky D; if Ti drz lock-S(D) then zmen se lock-S(D) na lock-X (D) else Ti zska lock-X (D); write(D) end


|


X Pro podporu tohoto pravidla, transakce postupne zskavan e zamky

drz az do prechodu do stavu provedena nebo zrusena az do doby, X Pokud se stav a provedena (po t commit), drz si zamky nez se objekty zaps do trvale pameti


28

Kritika zamykan

2

2

X Zamykat se mus i c iste dotazy, aby si zajistilo,

z e transakce nectou data prav e modi kovana jinymi transakcemi X Dals prklad vysoke rezie zamykan { Dva klientske procesy bez c soubez ne postupne zvysuj hodnoty n objektu. Necht' jsou spustene ve stejnou dobu a bez stejne dlouho a nezavisle samostatnymi transakcemi inkrementuj kazdy z n objektu. Pravdepodobnost, z e se soucasne pokus o prstup ke stejnemu objektu je v prum eru 1/n, zamykan je opravdu potreba pouze jednou za n proveden transakc.

|


|


29

Kritika zamykan

Sprava zamk u predstavuje zvy sen rezie


Princip 2PLP se zajistenm obnovitelnosti bez kaskadn ho vracen { transakce, ktera c te nebo zapisuje jisty objekt, se mus pozastavit do doby az se jina transakce, ktera jiz zapsala do teho z objektu, stane provedenou nebo zrusenou.

30

Neregulovane zamykan mu ze zpusobit uvaznut X Prevence uvaznut serializac moznych alokac omezuje soubez nost X Detekce uvaznut nen vhodna pro interaktivn programy

2

Aby se zamezilo kaskadn mu vracen transakc, zamky se uvolnuj az v okamziku commit transakce X Vyrazn e se tm snizuje potencialn soubez nost


|


31

P r klad 1

2

P r klad 1, pokracov an

Server spravuje objekty a1, a2, . . . , an, API pro klienty poskytuje operace read(i), write (i, hodnota) a server r es transakce T : x = read(i); write(j, 44); U : write(i, 55); write(j, 66)

2

Pro prpad, kdy jsou zamky v T uvolnovan e okamzite po zprstupnen datove polozky, ilustrujte prolozen U a T s dopadem, z e vysledn y plan nen serializovatelny 2 2 2


|



32

P r klad 2

|


33

P r klad 3

X Server spravuje objekty a1, a2, . . . , an, API pro klienty poskytuje operace read(i), write (i, hodnota)

2

a server r es transakce T : x = read(i); write(j, 44); U : write(i, 55); write(j, 66) Ktere z nasleduj cch plan u jsou serializovatelne a ktere se mohou c i nemohou vyskytnout pri 2-fazov em zamykan ?

2 2 2 2

|


Server spravuje objekty a1, a2, . . . , an, API pro klienty poskytuje operace read(i), write (i, hodnota) a server r es transakce T : x = read(i); read(j); U : write(i, 55); write(j, 66)

2


T je v kon iktu s U pri prstupu k ai, porad je T pak U T je v kon iktu s U pri prstupu k aj , porad je U pak T plan nen serializovatelny

34

Necht' incialn hodnoty ai a aj jsou 10 a 20 Necht' read-only transakce T uvolnuje zamky okamzite Necht' transakce U pouzva 2-fazov e zamykan Bude transakce T zskavat konzistentn hodnoty ? Budou objekty na disku nekonzistentn ?


|


35

P r klad 3, pokrac.

P r klad 3, pokrac.

X T je read-only a je v kon iktu s U: ai zskav a T pred U, aj zskav a U pred T X Prolozen nen serializovatelne X Hodnoty zskane T jsou x = 10, y = 66, vysledn e hodnoty objektu jsou ai = 55, aj = 66 X Seriov e proveden T pred U dav a x = 10, y = 20, ai = 55, aj = 66 X Seriov e proveden U pred T dav a x = 55, y = 66, ai = 55, aj = 66 Jan Staudek, FI MU Brno

|


2

2

36


Grafovy (stromovy) protokol r zen soubehu transakc

2

2

Neexistuje z adn a zaruka konzistentnho zskav an , protoze prekryv an transakc mu ze objekty, pote, co jsou odemcene, zmenit Objekty na disku nekonzistentn nebudou

|


37


Zamykac pravidla protokolu 2PLP jsou zalozena na kon iktech mezi operacemi read a write na nejmens mozne granularite Moznost vzniku uvaznut transakc 2PLP neres. Preventivn ochranou pred vznikem uvaznut je napr. vnucen porad zprstupnov an dat Pokud lze apriori de novat mozna porad zprstupnov an datovych polozek zachovavaj c ve vsech prpadech linearitu postupu, pak lze pouzt pro apriorn zajisten kon iktove serializovatelnosti

2 2

2 2

Necht' ex. mnozina datovych objektu D = {d1, d2, . . . , dn} Necht' ve vsech transakcch zprstupnuj cch di i dj plat, z e se mus di i dj zprstupnovat ve shodnem porad, tj. pokud se de nuje relace di → dj , pak plat, z e transakce si di mus zamknout drve, nez dj relaci lze modelovat acyklickym grafem { stromem Omezme se na exkluzivn prstup, X jsou povoleny pouze instrukce lock-X

grafovy (stromovy) protokol r zen soubehu transakc ktery vrozene vzniku uvaznut zamezuje Jan Staudek, FI MU Brno

|


38


|


39



mu ze inicialn e (tj. nedrz-li z adn y zamek) zamknout kteroukoliv polozku dat nasledn e Ti mu ze zamknout Q pouze tehdy, kdyz uz zamkla rodice Q zamek mu ze transakce uvolnit kdykoliv jedna T mu ze zamknout{odemknout tute z datovou polozku pouze 1x plat, z e vsechny plany vyhovujc stromovemu protokolu jsou kon iktove serializovatelne (bez dukazu)

2 Ti 2 2 2 2


|


2

X vysledek logicke organizace dat, napr. hierarchicke usporad an objektu X vysledek fyzicke organizace dat X vlozeno vyhradn e pro u cely r zen soubez nosti, . . . 2

40

prklad stromu prstupu pro skupinu transakc T1, . . . , T4: T1: lock-X(B);lock-X(E);lock-X(D); unlock-X(B);unlock-X(E);lock-X(G); unlock-X(D);unlock-X(G); T2: lock-X(D);lock-X(H); unlock-X(D);unlock-X(H); T3: lock-X(B);lock-X(E); unlock-X(E);unlock-X(B); T4: lock-X(D);lock-X(H); unlock-X(D);unlock-X(H); Jan Staudek, FI MU Brno

|


41



2

de nice porad zprstupnov an

2 2 2

prklad planu povoleneho tmto stromovym protokolem

2

zajist'uje kon iktovou serializaci zabranuje uvaznut , transakce se nemus vracet (roll-back) zamky lze uvolnovat drve nez v 2PLP, doby c ekan jsou krats, zvysuje se soubez nost nedostatky: X vysledn y plan nezarucuje obnovitelnost X vysledn y plan nezarucuje vyloucen kaskadn ch vracen X transakce si mus formaln e zamykat data, ke kterym nepristupuj

{ zbytecna rezie zamykan { potencialn zdroj snizovan soubez nosti

2

2


|


42

plat (bez dukazu) { pro danou mnozinu transakc mohou existovat kon iktove serializovatelne plany, ktere nelze zskat stromovym protokolem dale plat (bez dukazu) { existuj plany zskatelne 2PLP a nezskatelne stromovym protokolem a naopak Jan Staudek, FI MU Brno

|


43

Protokol r zen soubehu transakc s casov ymi raztky

2


zen soubez nosti transakc zalozene na jejich c asovem R r azen

2

X TPM zaznamenav a pro kazdy sdleny objekt dobu poslednho c ten

a zapisu pri kazde operaci s objektem X na bazi c asovych raztek transakc danych okamzikem jejich vzniku rozhoduje, zda { lze operaci provest bezprostredne, { lze operaci provest pozdeji (transakce bude c ekat) nebo { se mus operace odmtnout (transakce krachuje, klient ji mu ze restartovat) X pozadavek transakce na zapis je validn pouze kdyz objekt byl naposledy c teny nebo zapisovany drvejs transakc nebo nebyl dosud zprstupneny X pozadavek transakce na c ten je validn pouze kdyz objekt byl naposledy zapisovany drvejs transakc nebo nebyl dosud zprstupneny Jan Staudek, FI MU Brno

|


X Porad kon iktnch operac mus respektovat porad transakc v c ase X Jestlize jista transakce preps e v databazi hodnotu

promenne X, vu ci n stars transakce jiz nemu ze tuto hodnotu c st X Jestlize jista transakce preps e v databazi hodnotu promenne X, vu ci n stars transakce jiz nemu ze tuto hodnotu prepsat X Jestlize jista transakce precte v databazi hodnotu promenne X, vu ci n stars transakce jiz nemu ze tuto hodnotu prepsat X Jestlize k pozitivn validaci c asoveho porad kon iktn operace transakce nedojde, transakce krachuje, rus se (roll-back) a bude se (klientem) restartovat v novem (pozdejsm) c ase (zmnena stars transakce se stane vu ci zmnene jiste transakci mlads)

44


Pri startu transakce Ti se Ti prideluje c asove raztko, T Si

2

{ transakce Ti predchaz transakci Tj , je stars T Si > T Sj { transakce Ti nasleduje po transakci Tj , je mlads Pozadavky transakc se totaln e r ad podle prslusnych c asovych raztek transakc

2 T Si < T Sj 2


45

Casov e raztko T S se mu ze odvozovat X ze systemov ych hodin (nejsme zatm v distribuovanem prostred) X z logickeho c tace inkrementovaneho kazdym spustenm transakce

X T Si je jedinecne, v jednom okamziku dochaz k jedine udalosti X T Si de nuje pozici transakce Ti na c asove ose

2

|



2

Kazda operace transakce s databazovou promennou je pri provad en c asove validovana

2

Casov a raztka urcuj porad serializovatelnosti X pokud T Si < T Sj , protokol mus zajistit realizaci planu, ktery je ekvivalentn seriov emu planu, ve kterem Ti predchaz Tj

X pozadavek transakce na write objektu je validn pouze kdyz objekt byl

naposled c teny / zapisovany drvejs (stars) transakc a nebo nebyl dosud zprstupneny vubec X pozadavek transakce na read objektu je validn pouze kdyz objekt byl naposled zapisovany drvejs (stars) transakc a nebo nebyl dosud modi kovany Jan Staudek, FI MU Brno

|


46


|


47



|



48



2

2

Datove polozce Q se pridel dve c asova raztka

2

|


49

Necht' Ti provad read(Q): X Jestlize T Si < WQ, { stars Ti potrebuje c st hodnotu Q, ktera byla prepsana mlads T { operace read(Q) v Ti se odmta a { Ti se vrac (roll-back) vracen e Ti se pridel nove c asove raztko a Ti se spust znovu X Jestlize T Si ≥ WQ, { pak Ti potrebuje c st hodnotu Q jiz de novanou stars T nebo Ti { read(Q) v Ti se provede a RQ se nastav na max(RQ, T Si) pokud je v dobe testu transakce T , ktera provedla zapis,

Tato c asova raztka se koriguj pri kazdem read(Q) nebo write(Q) Protokol pomoc c asovych raztek zajist'uje, z e kon iktn operace read a write se provedou v porad danem c asovymi raztky transakc




X WQ { nejvets c asove raztko z transakc, ktere usp es ne provedly write(Q) X RQ { nejvets c asove raztko z transakc, ktere usp es ne provedly read(Q) 2

|

provedena { pokud T provedena nen, Ti pocka dokud se T nestane provedenou nebo zkrachuje a test se zopakuje 50


|


51


2


Necht' Ti provad write(Q):

X Predpoklad { transakcm se pridel TS pred provedenm 1. instrukce, takze T S2 < T S3

X Jestlize T Si < RQ, { pak hodnota Q vytva rena v Ti byla potrebna uz drve { Ti predpoklad a, z e tato hodnota uz nema byt vytva rena, { operace write se odmta a Ti se vrac (roll back) X Jestlize T Si < WQ, { pak Ti predpoklad a, z e zapisuje ,,uz starou"hodnotu Q, { operace write se odmta a Ti se vrac (roll back), . . . X V ostatnch prpadech se write provede a oprav se WQ 2 2

Pouzity algoritmus zarucuje kon iktovou serializaci (kon iktn operace se provedou v porad TS transakc ) Pouzity algoritmus nezpusobuje uvaznut (zadn a transakce neceka) Jan Staudek, FI MU Brno

|


X Plan je realizovatelny i 2-fazov ym zamykacm protokolem. X Ex. plany pro 2-fazov y zamykac protokol nevyhovujc

protokolu s c asovymi raztky a naopak

52



|


53


2

zajist'uje kon iktovou serializovatelnost X kon ikty jsou r eseny v c asovem porad podle c asovych raztek

2

zamezuje uvaznut X z adn a transakce trvale neceka

2

nevylucuje moznost starnut X ke starnut dojde kdyz posloupnost kratk ych kon iktnch transakc

opakovane zpusobuje opakovan dlouhe transakce X pokud se zjist existence opakovane restartovane transakce, kon iktn transakce by mely byt docasne zablokovane


|


54


|


55

Protokol r zen soubehu transakc na bazi validace


2

determinovane plany mohou byt neobnovitelne

2

X Ti zkrachuje, ale Tj pred zkrachovan m Ti precetla data zapsana Ti. X Tj mus tudz zkrachovat te z. Pokud je ale uz provedena (commit),

2

X male pravdepodobnosti kon iktu =

majorita transakc provad vetsinou pouze operace read

plan je neobnovitelny. X Pokud dals transakce c etly data zapsana Tj , vysledkem je kaskadov e vracen.

2

X efektivn = dosahuje vysoky stupen mozneho soubehu X porad serializace se nepredurcuje X vracet se mus pomerne malo (kon iktnch) transakc

(jedno) mozne r esen zajisten obnovitelnosti a zamezen kaskadov emu vracen:

2

X vsechny zapisy se provedou najednou na konci transakce

2

(zapisuje pouze nezkrachovana transakce) X zapisy mus byt vzajemn e vylouceny s ostatnmi prstupy k temto datum z jinych transakc X zkrachovala transakce se restartuje s novym c asovym raztkem Jan Staudek, FI MU Brno

|


2 2 2 2 2

(do doby testu uchovavan e ve vnitrn pameti) do baze dat, aniz by tm porusila podmnky serializovatelnosti planu soubez ne r esenych transakc?

56


|


|


57


Predpoklad { ve vetsine aplikac je mala pravdepodobnost, z e dve transakce kon iktne pristupuj ke stejnemu objektu Transakcm se umozn bez et soubez ne a predpoklad a se, z e ke kon iktum dojde vyjime cne Transakce c tou kopie (,,commitnutych") objektu vytva rene v RAM, neferov e c ten nevznika Pri r esen commit transakce se testem validnosti soubehu over , zda doslo ke kon iktu Pokud test odhal, z e kon ikt vznikl, kon iktn transakce se abortuj a provedou znovu Hroz nebezpec starnut transakc Jan Staudek, FI MU Brno

test validace se provad pri vydan pozadavku na commit transakce cl validacnho testu X mu ze transakce zapsat transakc zpracovane hodnoty dat


2

optimisticky protokol r zen soubehu transakc efektivn protokol v prpade male pravdepodobnosti kon iktu

58

2

Pokud test odhal, z e kon ikt provedenm testujc transakce nevznikl: { Transakce bez zapis u se stane provedena po validaci. { Transakce se zapisy se stane provedena az po korekci DB


|


59


2

implementace { kazda transakce sestav a ze 3 faz

2

operacn faze, T c te hodnoty z databaze, uklad a je do svych lokaln ch kopi a modi kuje (write) pouze odpovdajc lokaln promenne


2

Neferov e c ten se neuplatn, c ten se provad z permanentne ulozenych objektu, resp. z jejich kopi v RAM Pro kazdou transakci TPM udrzuje dva seznamy { seznam objektu c tenych danou transakc { seznam objektu modi kovanych danou transakc


|


2

60



2

|


61

Zpetn a a dop redna validace

Princip validacnho testu pro Tj (reseneho jako kriticka sekce v TPM)

2

Zpetna validace X validujc transakce se over uje vu ci transakcm,

ktere se s n prekryvaj a fazi validace zahajily pred n

X kon ikt nevznika, pokud, plat jedna z nasleduj cch dvou vztahovych podmnek vu ci vsem transakcm Ti starsm nez Tj (T Si < T Sj ): { transakce stars nez Tj je pred startem Tj uz provedena

2

(tj. provedla aktualizaci bazi dat podle svych vysledk u ulozenych ve vnitrn pameti) { transakce stars nez Tj je pred startem validace Tj jeste aktivn, a { Ti necetla objekty zapisovane Tj , (read x write) { Tj necetla objekty zapisovane Ti, (write x read) { Ti nemodi kovala objekty zapisovane Tj , (write x write) a { Tj nemodi kovala objekty zapisovane Ti, (write x write)

2

validacn faze (podrobny popis testu viz dale) { spoust ji prkaz pro commit transakce { transakce nemodi kujc bazi dat, se stane provedenou okamzite po pozitivnm ukoncen validace { transakce modi kujc bazi dat, mu ze sve lokaln promenne zapsat do baze dat pouze kdyz tm neporus podmnky serializovatelnosti, a pote se stane provedenou { viz dals faze nesplnen validace transakci krachuje a transakce se zopakuje faze zapisu do baze dat, baze dat se aktualizuje a transakce se stane provedenou, jen kdyz byl test validace usp es ny a transakce zapisovala

Dopredna validace X validujc transakce se over uje vu ci transakcm,

ktere jsou v okamziku validace aktivn, tj. jsou v operacn fazi

Pokud se validace a zapis do DB r es jako kriticka sekce v TPM, pak stac testovat pouze kombinace read/write Jan Staudek, FI MU Brno

|


62


|


63

Zpetn a validace transakc

Zpetn a validace transakc

X validuje se Tv ,

X zpetna validace { vu ci prekryvaj cm se transakcm Ti

startT n=T1 ,

posledn provedena T pred startem Tv prvn provedena T po startu Tv f inishTn =T3 , posledn provedena T po startu Tv

s drvejsm zahajen m validace a zapisu dat do DB X malo c ten v jedne Tv se porovnav a se mnoha zapisy ve vce Ti, vznikaj rezijn naklady uchovav an m starych zapisov ych mnozin po dobu co mohou byt potreba X pri kon iktu krachuje Tv , protoze Ti jsou jiz provedene Jan Staudek, FI MU Brno

|


startT n+1=T2 ,

X

f or(int Ti =startT n+1;Ti <=f inishTn ;Ti ++){ if (read set of Tv intersects write set of Ti ) valid=f alse; }

64

Dop redna validace transakc

transakcm, pri kon iktu lze zrusit validujc se transakci nebo validovane transakce X Malo zapis u v jedne Tv se porovnav a s mnoha c tenmi ve vce activei. POZOR: behem validace mohou vznikat dals transakce X pouze ps c transakce activei se kontrolovat nemus, read-only transakce Tv validac projde vzdy |



|


65

Dop redna validace transakc

X dopredna validace { vu ci dosud aktivnm, dosud nevalidujcm se


boolean valid=true;

66

X validuje se Tv , X boolean valid=true;

f or(int Tid =active1 ;Tid <=activeN ;Ti ++){ if (write set of Tv intersects read set of Tid ) valid=f alse; }

X krachovat mu ze Tv nebo vsechny kon iktn activei Jan Staudek, FI MU Brno

|


67


2


Validacn schema automaticky bran kaskadn m navrat um

2

X skutecny zapis se provede az je transakce provedena 2

X transakce se r es s optimistickym predpokladem dokoncen sveho

behu a pozitivn validace na zav er

Dlouhe transakce mohou starnout dky c astemu vyskytu kratk ych transakc

2

X dlouhe transakce se c asto r es opakovane X ochrana: docasne se povol beh pouze starnouc m transakcm 2

|


a to i v prpadech, kdy by mohla byt s ance, z e plan by mohl byt kon iktove serializovatelny

68


|


69

P r klad 4, pokrac.

P r klad 4

2

zamykan a c asove raztkovan jsou pesimisticka r zen soubez nosti X prosazuj c ekan /navrat pri detekci kazdeho kon iktu,

Ke starnut ma validacn protokol stejnou naklonnost jako protokol na bazi c asovych raztek


Validacn schema r zen je optimisticke r zen soubez nosti

Server spravuje objekty a1, a2, . . . , an, API pro klienty poskytuje operace read(i), write (i, hodnota) a server r es transakce T : x = read(i); write(j, 44); U : write(i, 55); write(j, 66)

2 2

Transakce T a U jsou r esene soubez ne Popiste vysledky nasleduj cch prpadu X X X X

2

T pozaduje provest commit prvn a pouzva se zpetna validace T pozaduje provest commit prvn a pouzva se dopredna validace U pozaduje provest commit prvn a pouzva se zpetna validace U pozaduje provest commit prvn a pouzva se dopredna validace

Prpomnka { zapisy lze delat po usp es ne validaci Jan Staudek, FI MU Brno

|


70


|


71

Operace INSERT a DELETE v transakcch

2

Porovnan metod r zen soubehu transakc

V transakcch se obecne mohou vyskytnout i operace INSERT a DELETE polozek v DB, X odstranov an neexistujc polozky se chape jako logicka chyba X c ten dosud neexistujc polozky se chape jako logicka chyba, . . .

2

2 2

DELETE

X X X X X

X Pri 2PL protokolu si mus transakce rusenou polozku exkluzivne

zamknout X V protokolu s TS se provad test podobny testu pro write jestlize mlads transakce jiz precetla nebo zapsala hodnotu, kterou chce stars transakce rusit, stars transakce zkrachuje a zopakuje se 2

2

INSERT exkluzivn zamek X Protokol s c asovymi raztky zapisov a a c tec c asova raztka polozky nastav na c as startu transakce |


72

Porovnan metod r zen soubehu transakc

2

optimisticka metoda, validace, r dke kon ikty

X transakce bez bez omezen, validuj se pri dokoncen X transakce mu ze krachovat pri pokusu o prevod do stavu provedena

nebo i drve (pri tzv. dopredne validaci)

2

dals optimisticke metody, nic se nerus, r es se kon ikt X Dropbox

{ cloudova sluzba, archivace souboru, umoznuj c i sdlen souboru { pokud 2 uzivatele soucasne nahrazuj stejny soubor, prvn ulozen se provede, druhe se odmtne X Google Apps { cloudova sluzba poskytujc webove orientovane aplikace { pokud 2 uzivatele soucasne pracuj s jednou aplikac, vid aktualn sdleny stav a uplatn se posledn korekce X Wikipedia { akceptuje se prvn zapis sdlene webovske stranky a nasledn y zapis se oznam jako kon ikt a z ad a se r esit kon ikt Jan Staudek, FI MU Brno

|


74

dynamicke r azen podle porad prstupu k objektum vhodne pri dominanci zapis u transakce se prpadne pozdrzuj, rus se jen pri uvaznut hlavn oblast pouzit { distribuovane systemy (CORBA, . . . ) pouzvaj souborove servery

c asove r azen, pesimismus, c aste kon ikty X X X X

X 2PL protokol: transakce dostane na vkladanou polozku


vsechny zpusobuj rezijn ztraty a omezuj potencionaln soubez nost stritkn 2-fazov e zamykan , pesimismus, c aste kon ikty

staticke r azen, pri startu transakce vhodne pri dominanci c ten transakce se r es okamzite, pozdrzuj se i rus, zabranuje se uvaznut pouzvaj souborove servery Jan Staudek, FI MU Brno

|


73

Rzen soub ezn eho prov ad en transakc

Recommend Documents