10. Transakce, řízení konkurenčních přístupů. Jedním kritériem klasifikace databázových systémů je počet uživatelů, kteří současně využívají systém. Jednouživatelský systém SŘBD - v daném okamžiku může nejvýše jeden uživatel používat systém. Víceuživatelský systém SŘBD - současné užívání systému více uživateli najednou (letecké rezervační systémy, bankovní a pojišťovací systémy…) Poznámka: Díky koncepci multiprogramování, která dovoluje spustit na počítači více programů najednou, může obecně také více uživatelů používat počítačový systém, v tomto případě se ovšem jedná o sdílení procesoru (CPU), kdežto v případě SŘBD jde především o sdílení dat.
10.1. Transakce Posloupnost operací, které se chápou jako nedělitelný celek tj. buďto úspěšně proběhnou všechny operace nebo se vše vrátí do původního stavu (všechno nebo nic). Databázová transakce se chápe jako vykonání programu, který přistupuje či mění data uložená v databázi.
Použití transakcí Řízení konkurenčních přístupů Obnova (rekonstrukce dat) Zajištění datové konzistence – zajištění korektního provedení posloupnosti závislých operací s daty
V souvislosti s prováděním transakcí a řízením konkurenčních přístupů k datům a obnově (rekonstrukci, záchraně) dat se nyní budeme zabývat transakcemi na úrovni datových položek a diskových bloků.
10. 1.1. Operace v transakcích read_item(X) - načte databázovou položku X do programové proměnné. Pro zjednodušení předpokládejme, že příslušná programová položka se jmenuje také X write_item(X) - zapíše hodnotu programové proměnné X do databázové proměnné X
Základní jednotkou přenosu dat mezi diskem a pamětí je pochopitelně jeden blok. Obecně datová položka: jedna položka z nějakého záznamu databáze celý záznam celý blok
Provedení operace read_item(X) zahrnuje následující kroky: 1. Najít adresu diskového bloku obsahujícího položku X 2. Nakopírovat tento blok do bufferu (za předpokladu, že už tam jmenovaný blok není uložen) 3. Nakopírovat položku X do příslušné programové proměnné
Provedení operace write_item(X) zahrnuje tyto kroky: 1. Najít adresu diskového bloku obsahujícího položku X 2. Nakopírovat tento blok do bufferu (za předpokladu, že už tam jmenovaný blok není uložen) 3. Nakopírovat položku X z programové proměnné na správné místo do bufferu 4. Uložit aktualizovaný blok z bufferu zpět na disk (buď okamžitě, nebo až později) Čtvrtý krok aktualizuje databázi na disku. Pokud není bezprostředně uložen blok na disk, může dojít ještě k dalším změnám v bufferu. Rozhodnutí, zda provést zpětné uložení bloku na disk okamžitě či později, záleží na operačním systému nebo na manažeru (správci) transakcí. Transakce může zahrnovat jak operace read_item, tak i operace write_item. Řízení konkurenčního přístupu a obnovující (rekonstruující) mechanismus se hlavně zaměřuje právě na ty příkazy v transakcích, které realizují přístup do databáze. Transakce prováděné různými uživateli mohou být prováděny současně a mohou přistupovat a aktualizovat tytéž databázové položky. Pokud by nebyl tento konkurenční přístup regulován, mohlo by to vést k takovým problémům, jako je např. nekonzistence databáze. Pokud transakce neprovádí žádné aktualizace dat, ale jen výběr údajů z databáze, pak hovoříme o read-only transakci. Příklad 10.1:
čas
Transakce T1
Transakce T2
read_item(X) ;
read_item(X) ;
X := X - N ;
X := X + M ;
write_item(X) ;
write_item(X) ;
read_item(Y) ; Y := Y + N ; write_item(Y) ;
Na uvedeném příkladu jednoduchých transakcí si ukážeme problémy, které mohou nastat, pokud budou tyto transakce probíhat nekontrolovaným způsobem. Představme si, že uvedený problém se týká rezervace letenek v jednoduchém leteckém rezervačním systému, kdy každý záznam obsahuje kromě jiných informací počet rezervovaných sedadel na určitý let. Uvažovaná transakce T 1 by tedy zrušila rezervaci N míst na určitý let „X“ a tentýž počet míst by rezervovala pro jiný let „Y“. Transakce T2 pouze rezervovala M míst na první let „X“, na který se ovšem obracela i transakce T 1. Pro zjednodušení situace se pochopitelně nezabýváme otázkou, zda je uvedený počet míst k dispozici.
10.1.2 Problémy Ztráta aktualizovaných dat Problém dočasné aktualizace (tzv. nečisté čtení – dirty read) Problém nesprávného součtu Problém neopakovatelného čtení Ztráta aktualizovaných dat Tento problém se vyskytne, pokud dvě (obecně více) transakcí přistupují ke stejným datovým položkám tak, že dílčí operace transakcí se provádějí prokládaně, což způsobí, že hodnoty některých datových položek jsou chybné. Příklad 10.2 : Ztráta aktualizovaných dat T1
T2
read_item(X) X := X – N ; read_item(X) ; X := X + M ; čas
write_item(X) ; read_item(Y) ; write_item(X) ; Y := Y + N ; write_item(Y) ; provedenou v T1
hodnota X je chybná, neboť transakce T2 přepsala aktualizaci
Předpokládejme výchozí hodnoty X = 80 , N = 5 , M = 4 . Konečná hodnota X by měla být X = 79, ale podle výše uvedeného schématu vychází 84.
Problém dočasné aktualizace Tento problém nastane, pokud jedna transakce provede aktualizaci datové položky a poté tato transakce z nějakého důvodu selže (nedokončí se). Vzápětí mohou být aktualizovaná data čtena jinou transakcí, aniž došlo k jejich změně na původní hodnotu, (což by se mělo provést, neboť transakce neproběhla korektně - nebyla dokončena). Tj. jiná transakce čte vlastně „špinavá data“, která byla zapsána nedokončenou a nepotvrzenou transakcí.
Příklad 10.3: Dirty read T1 read_item(X) X := X – N ; write_item(X) ; čas
T2
read_item(X) ; X := X + M ; write_item(X) ;
hodnota X je chybná, neboť transakce T1 změnila hodnotu X, se kterou poté pracovala T2, přičemž T1 pak ale selhala, takže T2 pracovala s nečistými daty
read_item(Y) ; selhání !! Problém nesprávného součtu Pokud jedna transakce provádí nějaké agregační výpočty zpracovávající hodnoty v záznamech, zatímco jiná transakce aktualizuje hodnoty z některých sumarizovaných záznamů, může dojít k tomu, že budou sečteny některé hodnoty aktualizované s jinými dosud neaktualizovanými. Příklad 10.4: Chybný součet T1
T3 sum := 0 ; read_item(A) ; sum := sum + A ;
čas
read_item(X) ; X := X - N ; write_item(X) ; read_item(X) ; sum := sum + X ; read_item(Y) ; sum := sum + Y ; read_item(Y) ; Y := Y + N ; write_item(Y) ;
hodnota sum je chybná, neboť v součtu jsou zahrnuty některé položky již aktualizované a jiné neaktualizované
Problém neopakovatelného čtení Jedna transakce může opakovaně číst určitou datovou položku, zatímco jiná transakce provede změnu této položky mezi těmito dvěmi čteními, takže se vlastně pokaždé přečte jiná hodnota.
10.3. Žádoucí vlastnosti transakcí – ACID atomicita (Atomicity) - transakce je atomická nedělitelná jednotka
schopnost zachovat konzistenci (Consistency) databáze – transakce musí převádět databázi z jednoho konzistentního stavu do druhého izolace (Isolation) – změny, které transakce provádí, jsou izolovány od ostatních transakcí, jsou neviditelné, dokud nejsou schváleny trvanlivost (Durability) – jakmile transakce provede změny a tyto jsou potvrzeny, nemůže nikdy dojít k jejich ztrátě – změny trvají
10.3.1. Stupeň izolace transakcí 0.
transakce nepřepíše "dirty read" transakci s vyšším stupněm
1.
transakce nemá ztracené aktualizace
2.
stupeň 0 a stupeň 1 dohromady
3.
pravá izolace – oproti stupni 2 nemá problémy s opakovaným čtením
10.4. Obnovovací systém SŘBD je při provádění transakcí zodpovědný za kompletní úspěšné provedení všech operací trvalý zápis všech změn do databáze Nastane-li chyba transakce se vůbec neprovede tj. všechny operace a data jsou vrácena do původního stavu, ať se stane cokoliv SŘBD nesmí dopustit, aby se některé operace na datových položkách provedly, zatímco jiné neproběhnou. zásada "všechno nebo nic"
10.4.1. Druhy chyb 1. Selhání počítače (system crash) - hardwarová či softwarová chyba během provádění transakce.
V řadě případů je ztracen obsah operační paměti. 2. Transakční či systémová chyba - některé operace v transakci mohou způsobit selhání transakce
- např. dělení nulou, přetečení v pevné řádové čárce, chybné parametry (i typy), logická chyba programu. 3. Lokální chyby nebo nesplnění podmínek nutných pro korektní průběh transakce - během
provádění transakce může nastat taková situace, že je nezbytné transakci zrušit - např. nebyl nalezen soubor s daty, v bankovních transakcích není dostatečná částka na účtu klienta, takže není možné provést převod peněz z jednoho účtu na druhý. Toto zrušení transakce se dá provést programově příkazem ABORT. 4. Chyba vynucená řízením konkurenčního přístupu - transakce může být přerušena a později
odstartována, protože narušuje tzv. pravidlo sériovosti transakcí nebo některé transakce jsou ve stavu „dead-lock“. 5. Disková chyba - došlo k chybě při čtení či zápisu bloku na disk např. z důvodů selhání (zničení)
čtecí/záznamové hlavy 6. Fyzikální problémy a katastrofy - nekonečný seznam problémů, které zahrnují výpadek
proudu, selhání klimatizace, požár, krádež, sabotáž, omylem přepsaná či smazaná data ...
Chyby 1 - 4 jsou častější, takže systém musí uchovávat dostatek informací k možnému obnovení vzpamatování se z chyby
10.5. Transakční stavy a další operace Transakce je atomická (základní) jednotka, která se buďto provede celá, nebo se vůbec neprovede. Pro účely rekonstrukce systém sleduje start transakce, její ukončení, potvrzení (odeslání) nebo přerušení. BEGIN_TRANSACTION - značka zahájení provádění transakce READ nebo WRITE - čtení nebo zápis datových položek END_TRANSACTION - tato operace signalizuje, že došlo k ukončení operací READ a WRITE a zaznamenává ukončení transakce. V tomto momentu by bylo nutné zkontrolovat, zda změny představované transakcí se trvale promítly do databáze (odevzdání transakce) nebo zda se má transakce přerušit, protože je narušen konkurenční přístup nebo nastaly jiné důvody vynucující si přerušení transakce. COMMIT_TRANSACTION - signál úspěšného ukončení transakce – všechny změny provedené transakcí byly úspěšně provedeny a zaznamenány do žurnálu, a tedy mohou být bezpečně zaznamenány do databáze a nic se nemusí vracet. ROLLBACK (ABORT) - signál neúspěšného ukončení transakce, takže vše se musí vrátit do původního stavu
Další operace UNDO - podobná operace jako ROLLBACK, která se ale týká spíše jednoduché operace, než celé transakce - tj. ROLLBACK je vlastně posloupnost UNDO REDO -tato operace zajišťuje, že jistá činnost musí být zopakována, aby se zajistilo, že všechny operace odeslané transakce se úspěšně promítnou do databáze. Obrázek 10.1 – stavový diagram provádění transakce Aktivní Částečně potvrzená Potvrzená Chybový stav – selhání Přerušená – nastane rollback
Bezprostředně po startu se transakce dostává do aktivního stavu, kdy může provádět operace READ a WRITE. Když transakce skončí, je ve stavu částečně potvrzeném (odeslaném), protože se vlastně ještě musí zkontrolovat, jestli nedošlo ke konfliktu s jinými právě probíhajícími transakcemi. Obnovující protokoly se potřebují ujistit, že eventuální systémové selhání nebude mít za následek nemožnost zapsat provedené změny do databáze. (K tomu účelu se do systémového žurnálu zapisují průběžně změny). Pokud úspěšně proběhnou obě tyto kontroly, transakce se dostává do stavu potvrzení. Jakmile transakce dosáhne stavu potvrzení, je chápána jako úspěšně provedená. Pokud jedna z kontrol selže nebo došlo k přerušení transakce během jejího aktivního stavu, dostává se do stavu selhání (chybový stav), transakce je poté zpětně vracena v podstatě do původního výchozího stavu. Stav ukončení odpovídá stavu, kdy transakce opouští systém. Přerušené transakce nebo transakce, které selhaly, mohou být později restartovány nebo odeslány jako část nové transakce.
10.5.1. Transakce na MS SQL serveru 2008 Každý SQL příkaz se bere jako atomický Zahájení lokální transakce BEGIN TRANSACTION název_transakce [WITH MARK] zvýší systémovou proměnnou @@TRANCOUNT o 1 je-li použito WITH MARK, zapisuje se do transakčního logu (žurnálu) Potvrzení transakce COMMIT TRANSACTION název_transakce Zpětný chod transakce (vrácení do původního stavu) ROLLBACK TRANSACTION název_transakce Příklad 10.5 BEGIN TRANSACTION T1 WITH MARK UPDATE Mzdy SET priplatek = 0.75 * priplatek BEGIN TRANSACTION T2 IF (SELECT SUM(prescasy) from Hodiny WHERE Oddeleni = 5 and mesic = 10) > 300 BEGIN UPDATE Mzdy SET Priplatek = 0 WHERE Id_zam = (SELECT vedouci FROM Oddeleni WHERE Oddeleni = 5) END COMMIT TRAN T2 UPDATE Hodiny ... … COMMIT TRANSACTION T1
10.6. Transakční žurnál je udržován systémem zaznamenává informace nutné pro zpětnou rekonstrukci (obnovení) po neúspěšně provedených transakcích. bývá uložen na disku a pravidelně zálohován na pásky.
10.6.1. Položky transakčního žurnálu [start_transaction, T] zaznamená start transakce [write_item,T, X, old_value, new_value] zaznamená, že transakce změnila hodnotu položky X [read_item, T, X] zaznamená, že transakce čte položku X [commit, T] zaznamená, že transakce proběhla úspěšně a potvrzuje, že všechny změny mohou být trvale promítnuty do databáze, vynutí též zápis samotného žurnálu na disk [abort, T] zaznamená, že transakce byla přerušena [check point] zapisuje se periodicky do žurnálu, zajistí provedení zápisu veškerých změn hodnot položek potvrzených transakcí na disk (tj permanentní promítnutí veškerých potvrzených změn do databáze), vynutí též zápis samotného žurnálu na disk Poznámka: Dojde-li k systémovému selhání, všechny transakce, které nemají zapsaný svůj potvrzovací bod v žurnálu, musí být stornovány a odrolovány zpět do výchozího stavu. Transakce se zapsaným commit pointem se nestornují, ale v případě, že nebylo dosaženo checkpointu, musí se vynutit znovu zápis veškerých změn (výsledků write_item) do databáze Poznámka: Předpokládáme, že transakce nemohou být do sebe vnořeny ! ! !
10.7. Transakční scénáře jedná se vlastně o historii (pořadí) zaznamenávající posloupnost jednotlivých dílčích operací současně probíhajících transakcí. Dvě operace jsou konfliktní, pokud patří každá z nich do jiné transakce, přistupují k téže datové položce X a jedna z nich je write_item(X). Scénář je úplný, pokud: 1. zahrnuje všechny operace jednotlivých transakcí od první operace až do poslední operace (commit nebo abort) 2. každé dvě operace z jedné transakce jsou zapsány v tom pořadí, v jakém skutečně probíhají 3. pro každé dvě konfliktní operace musí platit, že jedna z nich musí proběhnout před druhou (tj. nemohou nastat současně) Poznámka: z bodu 3 vyplývá, že nekonfliktní operace nemusí mít stanoveno pořadí Scénář je obnovitelný, pokud žádná transakce T nedosáhne svého potvrzení (commit point), dokud všechny další transakce T’, které zapisovaly položky, které četly transakce T, nedosáhnou svého bodu potvrzení Scénář může být sériový (všechny operace jedné transakce proběhnou před operacemi druhé transakce) nebo prokládaný
Příklad 10.6. Bankovní transakce Předpokládejme, že na účtu A je 35 000 Kč, na účtu B 110 000 Kč Transakce T1 read(A) A := A – 5000 write(A) read(B) B := B + 5000 write(B)
Transakce T2 read(A) tmp := A* 0.1 A := A – tmp write(A) read(B) B := B + tmp write(B)
Uvažujme různé scénáře provádění transakcí
Řešení 10.6.a: Nejdřív transakce T1, pak T2 Transakce T1
čas
Transakce T2
read(A) A := A – 5000 write(A) read(B) B := B + 5000 write(B)
sériový scénář
read(A) tmp := A* 0.1 A := A – tmp write(A) read(B) B := B + tmp write(B)
Před zahájením transakcí je na účtu A 35 000, na účtu B 110 000, celkem tedy 145 000 po provedení je na účtu A 27 000, na účtu B 118 000, celkem 145 000
Řešení 10.6.b: Nejdřív transakce T2, pak T1
Transakce T1
Transakce T2 read(A) tmp := A* 0.1 A := A – tmp write(A) read(B) B := B + tmp write(B)
čas
read(A) A := A – 5000 write(A) read(B) B := B + 5000 write(B)
sériový scénář
Před zahájením transakcí je na účtu A 35 000, na účtu B 110 000, celkem tedy 145 000 po provedení je na účtu A 26 500, na účtu B 118 500, celkem 145 000
Řešení 10.6.c: Současně T1, pak T2 Transakce T1
Transakce T2
read(A) A := A – 5000 write(A) read(A) tmp := A* 0.1 A := A – tmp write(A)
čas
read(B) B := B + 5000 write(B) read(B) B := B + tmp write(B)
scénář ekvivalentní variantě a
Před zahájením transakcí je na účtu A 35 000, na účtu B 110 000, celkem tedy 145 000 po provedení je na účtu A 27 000, na účtu B 118 000, celkem 145 000
Řešení 10.6.d: Současně T1, pak T2 Transakce T1
Transakce T2
read(A) A := A – 5000 read(A) tmp := A* 0.1 A := A – tmp write(A) read(B)
čas
CHYBA ztratilo se 1 500 Kč
write(A) read(B) B := B + 5000 write(B) B := B + tmp write(B)
Před zahájením transakcí je na účtu A 35000, na účtu B 110000, celkem tedy 145000 po provedení je na účtu A 30000, na účtu B 113500, celkem 143500
10.7.1.Posloupnost (řazení) konfliktních operací Uvažujme transakce T1 a T2 a jejich operace O1 a O2. Nastanou případy: O1 = read(A) ; O2 = read(A)
na pořadí operací nezáleží,
O1 = read(A) ; O2 = write(A) na pořadí operací záleží, pokud O1 proběhla dříve než O2, transakce T1 nepracovala s korektní hodnotou A O1 = write(A) ; O2 = read(A) na pořadí operací záleží, pokud O1 proběhla dříve než O2, je to v pořádku, pokud naopak O1 proběhla později než O2, pak transakce T2 nepracovala s korektní hodnotou A O1 = write(A) ; O2 = write(A) na pořadí operací nezáleží, jedna transakce vždy přepíše data té druhé
10.8. Techniky řízení konkurenčních přístupů zamykání dat - zabrání vícenásobnému současnému přístupu k datům časové známky - zajišťují sériovost transakčních scénářů multiverze - používání více verzí dat optimistické protokoly - koncepce validace nebo certifikace transakcí po provedení operací
10.8.1. Zamykání dat Zámek je proměnná svázaná s datovou položkou popisující její status z ohledem na možné operace, které se s položkou mohou provádět. Binární zámek – nabývá dvou hodnot nebo stavů (např. 0 odemknuto, 1 zamknuto). LOCK(X)
hodnota (stav) zámku patřícího k proměnné X
lock_item(X) operace uzamčení položky X ZAMEK :
if LOCK(X) = 0 ; then LOCK(X) := 1 ; else begin {čekej, dokud není LOCK(X)=0 a správce zámků neaktivuje transakci} goto ZAMEK ; end ;
unlock_item
odemkne položku LOCK(X) := 0 ; {pokud nějaká transakce čeká ve frontě, tak se aktivuje}
10.8.1.1. Manažer zámků SŘBD v sobě zahrnuje jako subsystém manažera zámků, který sleduje a řídí zamykání. Každá transakce používající tento binární způsob zamykání musí splňovat následující pravidla před každým čtením nebo zápisem X se musí použít lock_item(X) jakmile je čtení nebo zápis dokončen, musí se použít unlock_item(X) transakce nepoužije lock_item(X) na položku, kterou sama uzamkla transakce nepoužije unlock_item(X), pokud nezamkla položku X Tyto binární zámky se dají jednoduše implementovat jako jednoduché záznamy obsahující dvě položky - jméno datové položky a dvouhodnotovou proměnnou signalizující stav zámku. Systém spravuje tyto záznamy v tabulce zámků.
10.8.1.2. Sdílené a výhradní výlučné zámky Operace čtení – může být prováděna více transakcemi najednou – vícenásobný (sdílený) zámek Operace zápis – jen jediná transakce může zapisovat – výhradní zámek
read_lock(X) ZAMEK :
write_lock(X) ZAMEK :
unlock(X)
if LOCK(X) = "unlocked" then begin LOCK(X) := "read-locked" ; no_of_reads(X) := 1 ; end ; else if LOCK(X)= "read-locked" then inc(no_of_reads(X)) else begin {čekej, dokud LOCK(X)= "unlocked" a správce zámků aktivuje trans. } go to ZAMEK ; end ;
if LOCK(X) = "unlocked" then LOCK(X) := "write-locked" else begin {čekej, dokud LOCK(X)= "unlocked" a správce zámků aktivuje trans. } go to ZAMEK ; end ; if LOCK(X) ="write-locked" then begin LOCK(X) = "unlocked" ; {aktivuj čekající transakci, pokud je nějaká ve frontě} end else if LOCK(X) = "read-locked" then begin dec(no_of_reads(X)) ; if no_of_reads(X) = 0 then begin LOCK(X) := "unlocked" ; {aktivuj čekající transakci, pokud je nějaká ve frontě} end end ;
Všechny tyto operace se chápou jako nedělitelné, není povoleno prokládání jednotlivých dílčích činností. Používáme-li tento systém zamykání, musí být dodržena následující pravidla : před každým čtením X se musí provést read_lock(X) nebo write_lock(X) před každým zápisem X se musí provést write_lock(X) po ukončení čtení nebo zápisu se musí provést unlock(X) transakce nesmí použít znovu read_lock(X), pokud sama zamkla X transakce nesmí použít znovu write_lock(X), pokud sama zamkla X transakce nesmí použít unlock(X) , pokud sama neuzamkla nad X
Poznámka: Čtvrté a páté pravidlo nemusí být vždy dodrženo - read_lock se dá povýšit na write_lock a opačně write_lock se dá ponížit na read_lock. Pokud toto je přípustné, pak samozřejmě je nutné u každého zámku ještě zavést identifikátor pro transakci, která tento zámek provedla. Spolu s technikami zamykání se dále ještě používají další protokoly, aby se zajistila tzv. sériovost transakčních scénářů - nejlepší je protokol dvoufázového zamykání. Transakce dodržuje tento protokol, pokud všechna zamykání předcházejí prvnímu odemykání v transakci. Taková transakce může být rozdělena do dvou fází expanzní (rozpínající se) fáze, kdy se postupně zamyká, ale nic se neuvolňuje redukující se fáze , kdy se zámky uvolňují a už se nezamyká Příklad 10.8: Předpokládejme, že X = 20, Y = 30 Transakce T1 read_lock(Y) ; read_item(Y) ; unlock(Y) ; write_lock(X) read_item(X) ; X := X + Y; write_item(X); unlock(X);
Transakce T2 read_lock(X); read_item(X); unlock(X) ; write_lock(Y); read_item(Y) ; Y := Y + X ; write_item(Y) ; unlock(Y) ; )
Řešení 10.7a: Proběhne-li nejprve T1, pak T2, je X = 50 a Y = 80 Řešení 10.7b: Proběhne-li nejprve T2, pak T1, je X = 70 a Y = 50
Příklad 10.7c: Transakční scénář T1
(předp. X = 20, Y = 30) T2
read_lock(Y) ; read_item(Y) ; unlock(Y) ; read_lock(X) ; read_item(X) ; unlock(X) ; write_lock(Y) ; read_item(Y) ; Y := Y + X ; write_item(Y) ; unlock(Y) ;
čas
write_lock(X) ; read_item(X) ; X := X +Y ; write_item(X) ; unlock(X) ;
,
nejde o sériový transakční scénář, výsledek je X = 80, Y = 50
Příklad 10.7d :Transakční scénář podle protokolu dvoufázového zamykání T1 ’
čas
read_lock(Y) ; read_item(Y) ; write_lock(X) ; unlock(Y) ; read_item(X) ; X := X +Y ; write_item(X) ; unlock(X) ;
T2’ read_lock(X) ; read_item(X) ; write_lock(Y) ; unlock(X) ; read_item(Y) ; Y := Y + X ; write_item(Y) ; unlock(Y) ;
Dodržen protokol dvoufázového zamykání X = 50, Y = 50
10.8.1.3. Druhy dvoufázového zamykání -
základní – viz výše popsaný postup, tj. průběžně podle potřeby se zamyká, provádějí se operace čtení, zápis a další a pak se postupně odmyká – všechny operace zamykání jsou časově před odemykacími operacemi
-
konzervativní – předem se stanoví množiny položek, které se mají zamknout – množina zámků pro čtení a množina pro zápis, pokud se nepodaří zamknout všechny potřebné položky, nezamkne se žádná
-
striktní – žádný zámek není uvolněn, pokud není transakce potvrzena – může snadno způsobit deadlock na rozdíl od konzervativního zamykání
Deadlock - nastane tehdy, pokud dvě transakce čekají na sebe navzájem Příklad 10.8: T1
T2
read_lock(Y) ; read_item(Y) ; read_lock(X) ; read_item(X) ;
Deadlock
write_lock(X) ; write_lock(Y) ;
Dead-lock techniky Jedná se o techniky, jejichž prostřednictvím se zajišťuje, že nedojde k dreadlocku. Technika používající časové známky (timestamp) – Každé transakci je v okamžiku startu přiděleno číslo (časová značka TS – časové razítko), transakce jsou seřazeny podle těchto známek.
wait-die :
je-li TS(Ti) < TS(Tj) tj. Ti je starší Tj pak starší transakce Ti čeká, než mladší transakce Tj uvolní zámek nad položkou, kterou starší transakce potřebuje zamknout. V opačném případě Ti „zahyne“ – je stornována. V tomto případě je Ti mladší transakce, neboť má větší časovou známku, přičemž je později restartována se stejnou TS
wound-wait : je-li TS(Ti) < TS(Tj) tj. Ti je starší Tj pak Ti zruší mladší transakci Tj Jinak Ti smí čekat (vlastně teď čeká mladší transakce), až starší transakce uvolní zámek Poznámka: Může nastat též livelock – jedna transakce nemůže pokračovat – čeká a čeká a čeká (nekonečný cyklus abortů a restartů) a není to nic platné, zatímco ostatní transakce běží normálně. Tento problém může být způsoben například špatnou prioritou obsluhy transakcí – stačí použít třeba metodu first-come – first-serve
10.8.2. Časové známky (značky) Jedná se vlastně o jednoznačnou proměnnou přidělenou každé transakci, jejíž hodnota se mění podle toho, jak transakce probíhá (vlastně něco jako čítač). Základní idea je uspořádat transakce podle jejich hodnot TS. read_TS(X) - hodnota největší TS ze všech transakcí, které úspěšně četly X write_TS(X) - hodnota největší TS ze všech transakcí, které úspěšně zapsaly X Kdykoliv se transakce snaží číst nebo psát položku, algoritmus TU (transakční uspořádání) porovnává TS transakce a read_TS(X) eventuelně write_TS(X) a kontroluje, zda není narušeno pořadí TS (což má za následek pozastavení a novou TS nebo ukončení a rollback ).
Základní algoritmus provedení read_item(X) 1. je-li write_TS(X) > TS(T) , nastane ABORT a ROLLBACK (nějaká transakce s vyšším TS může
ještě zapisovat) 2. jinak se povolí čtení a read_TS(X) := max( TS(T), read_TS(X) )
provedení write_item(X) 1. je-li read_TS(X) > TS(T) nebo write_TS(X) > TS(T), nastane ABORT a ROLLBACK (nějaká
transakce s vyšším TS může ještě zapisovat nebo číst) 2. jinak se povolí zápis a write_TS(X) := TS(T)
10.8.3. Techniky multiverzního řízení konkurenčního přístupu pomocí časových značek
pomocí dvoufázového zamykání
10.8.3.1. Časové značky V systému je udržováno více verzí X1 ,X2 , X3 , X4 , … – každá položka Xi má svou hodnotu read_TS( Xi ) i write_TS( Xi ) . Pokud se transakce snaží zapisovat Xi , je vytvořena nová verze Xi+1 , pro níž je nastaveno read_TS( Xi+1 ) = write_TS( Xi+1 ) = TS(T) . Pravidla pro provádění operací write_item a read_item jsou následující:
operace write_item(X) pokud transakce T použije operaci write_item(X) a i.tá verze X má nejvyšší hodnotu write_TS ( X i) ze všech verzí X takovou, že je současně menší nebo rovna TS(T), a současně TS(T) < read_TS ( X i), nastane abort a rollback jinak se vytvoří nová verze Xj s read_TS( Xj ) = write_TS( Xj ) = TS(T) operace read_item(X) v tomto případě se najde verze Xi s nevyšší hodnotou write_TS ( Xi) ze všech takovou, že současně platí write_TS ( X i) < = TS(T) a transakci T se vrátí jako výsledek čtení právě tato hodnota X a nastaví se read_TS( Xi ) = max (read_TS( Xi ) , TS(T) )
10.8.4. Validace – optimistické řízení konkurenčního přístupu V průběhu transakce se neprovádějí žádné kontroly, používá se tzv. validační technika. Aktualizace se neprovádějí přímo na datech, ale na jejich lokálních kopiích. Na závěr validační fáze se kontroluje, zda transakce nenarušuje sériovost. Fáze řídícího protokolu 1. read fáze – čtou se data z databáze a aktualizace se provedou na lokálních kopiích položek 2. validační fáze – kontrola sériovosti 3. write fáze – provede se, pokud dopadla dobře validační fáze
Literatura: [1] ELMASRI, R., NAVATHE, S., B. Fundamentals of Database Systems, 5th edition. AddisonWesley, 2007. ISBN 978-03-213-6957-4. [2] SILBERSCHATZ, A., KORTH H. F., SUDARSHAN S. Database System Concepts, 5th edition, New York: McGraw-Hill, 2006. ISBN 978-0-07-295886-7 [3] CONOLLY, T., BEGG, C., HOLOWZAK R. Profesionální průvodce tvorbou databází. Praha: Computer Press, a. s., 2009. ISBN 978-80-251-2328-7. [4] HERNANDEZ, M., J. Návrh databází. Praha: Grada, 2006. ISBN 80-247-0900-7. [5] POKORNÝ, J. Databázová abeceda. Veletiny: Science, 1998, ISBN 80-86083-02-2. [6] POKORNÝ, J., HALAŠKA, I. Databázové systémy, 2. vydání. Praha Vydavatelství ČVUT, 2003, ISBN 80-01-02789-9.
