Transakce
Transakcí se rozumí sekvence operací nad daty, která má začátek a konec
Transakce je sekvenční provádění operací čtení a zápisu. Konec transakce může být buď uložení změn (potvrzení, commit) nebo zrušení změn (rollback). V kontextu databází je transakce několik dotazů, které jsou chápány jako jeden dotaz.
Transakce musí splňovat vlastnosti ACID
Atomarita. Transakce buď proběhne celá, nebo vůbec neproběhne.
Konzistence. Při ukončení transakce nesmí být porušena omezení uložená na data (například constraints v databázi). Konzistence znamená, že systém bude převeden z jednoho správného stavu do druhého správného.
Izolovanost. Paralelně prováděné transakce by neměly mít vliv jedna na druhou, například měnit data, která používá jiná transakce. Výsledek provádění paralelních transakcí by měl být takový, jako by transakce probíhaly sekvenčně.
Trvanlivost. Po potvrzení nesmí být změny ztraceny.
Žurnál transakcí
Žurnál uchovává změny provedené transakcemi a zajišťuje atomaritu a trvanlivost dat v případě selhání systému.
Žurnál obsahuje hodnoty, které data měly před a po jejich změně transakcí. Strategie Write-ahead log vyžaduje, aby se do žurnálu přidávaly záznamy o předchozích hodnotách před začátkem, a o koncových po dokončení transakce. V případě náhlého zastavení systému čte databáze log v obráceném pořadí a ruší změny provedené transakcemi. Pokud databáze narazí na přerušenou transakci, provede ji a zaznamená její změny do žurnálu. Když se nachází ve stavu v době selhání, databáze čte log v přímém pořadí a vrací změny provedené transakcemi. Tímto způsobem se zachovává trvanlivost transakcí, které již byly potvrzeny, a atomarita přerušené transakce.
Jednoduché opakování chybových transakcí nestačí k obnovení.
Příklad. Na účtu uživatele je 500 $ a uživatel se rozhodne je vybrat přes bankomat. Dochází k dvěma transakcím. První čte hodnotu zůstatku a pokud je na zůstatku dostatek prostředků, vydá peníze uživateli. Druhá část odečítá potřebnou částku ze zůstatku. Předpokládejme, že došlo k selhání systému a první operace neproběhla, zatímco druhá proběhla. V takovém případě nemůžeme uživateli znovu vydat peníze, aniž bychom vrátili systém do původního stavu s kladným zůstatkem.
Úrovně izolace
Čtení potvrzených dat (Read Committed)
Problém špinavého čtení (Dirty Read) spočívá v tom, že transakce může přečíst mezivýsledek práce jiné transakce.
Příklad. Počáteční hodnota zůstatku 0 $. T1 přidává k zůstatku 50 $. T2 čte hodnotu zůstatku (50 $). T1 ruší změny a končí. T2 pokračuje v provádění s neplatnými daty o zůstatku.
Řešením je čtení potvrzených dat (Read Committed), které zakazuje číst data, změněná transakcí. Pokud transakce A změnila nějakou sadu dat, musí transakce B při přístupu k těmto datům čekat na dokončení transakce A.
Opakované čtení (Repeatable Read)
Problém ztracených změn (Lost Updates). T1 ukládá změny na vrcholu změn T2.
Příklad. Počáteční hodnota zůstatku 0 $ a dvě transakce zároveň doplňují zůstatek. T1 a T2 čtou zůstatek rovný 0 $. Poté T2 přidává 200 $ k 0 $ a ukládá výsledek. T1 přidává 100 $ k 0 $ a ukládá výsledek. Konečný výsledek je 100 $ místo 300 $.
Problém nepř repeatelného čtení (Unrepeatable read). Opakované čtení stejných dat vrací různé hodnoty.
Příklad. T1 čte hodnotu zůstatku rovnou 0 $. Poté T2 přidává k zůstatku 50 $ a končí. T1 znovu čte data a zjišťuje nesoulad s předchozím výsledkem.
Opakované čtení (Repeatable Read) zaručuje, že opakované čtení vrátí stejný výsledek. Data přečtená jednou transakcí nesmějí být měněna v jiných až do dokončení transakce. Pokud transakce A přečetla nějakou sadu dat, musí transakce B při přístupu k těmto datům čekat na dokončení transakce A.
Uspořádané čtení (Serializable)
Problém phantomového čtení (Phantom Reads). Dva dotazy vybírající data podle určitého kritéria vracejí různé hodnoty.
Příklad. T1 dotazuje počet všech uživatelů, jejichž zůstatek je větší než 0 $ ale menší než 100 $. T2 odečítá 1 $ od uživatele se zůstatkem 101 $. T1 vykonává dotaz znovu.
Uspořádané čtení (Serializable). Transakce probíhají jako zcela sekvenční. Je zakázáno aktualizovat a přidávat záznamy, které spadají pod podmínky dotazu. Pokud transakce A vyžádala data z celé tabulky, je tabulka pro ostatní transakce zcela zmrazena, dokud transakce A nedokončí.
Plánovač (Scheduler)
Stanovuje pořadí, ve kterém mají být operace prováděny při paralelních transakcích.
Zajišťuje danou úroveň izolace. Pokud výsledek provedení operací nezávisí na jejich pořadí, jsou takové operace komutativní (Permutable). Komutativní jsou operace čtení a operace nad různými daty. Operace čtení-zápisu a zápisu-zápisu nejsou komutativní. Úkolem plánovače je střídat operace prováděné paralelními transakcemi tak, aby výsledek byl ekvivalentní sekvenčnímu provádění transakcí.
Mechanismy řízení paralelních úloh (Concurrency Control)
Optimistický se zakládá na odhalování a řešení konfliktů, pesimistický na prevenci vzniku konfliktů.
Při optimistickém přístupu získává několik uživatelů kopie dat. První, kdo dokončí úpravy, ukládá změny, zatímco ostatní musí provést sloučení změn. Optimistický algoritmus umožňuje vznik konfliktu, ale systém se musí po konfliktu zotavit.
Při pesimistickém přístupu první uživatel, který si data zajistí, brání ostatním v přístupu k datům. Pokud jsou konflikty vzácné, je rozumné zvolit optimistickou strategii, protože ta zajišťuje vyšší úroveň paralelismu.
Zamykání (Locking)
Pokud jedna transakce zablokovala data, zbývající transakce musí při přístupu k datům čekat na jejich odemknutí.
Blok může být aplikován na databázi, tabulku, řadu nebo atribut. Sdílená zámek (Shared Lock) může být aplikován na stejná data několika transakcemi, umožňuje všem transakcím (včetně té, která zámek aplikovala) čtení, ale zakazuje modifikaci a exkluzivní zámek. Exkluzivní zámek (Exclusive Lock) může být aplikován pouze jednou transakcí, umožňuje jakoukoli činnost aplikované transakce, zakazuje jakékoli činnosti ostatním.
Vzájemné blokování se považuje za situaci, kdy transakce jsou v režimu čekání, který trvá nekonečně dlouho.
Příklad. První transakce čeká na uvolnění dat, která byla zachycena druhou, zatímco druhá čeká na uvolnění dat, která byla zachycena první.
Optimistické řešení problému vzájemného blokování umožňuje vzájemné blokování nastat, ale poté obnovuje systém vrácením jedné z transakcí, které se podílejí na vzájemném blokování.
S určitou pravidelností se provádí hledání vzájemného blokování. Jeden ze způsobů detekce — podle času, což znamená považovat za vzájemné blokování, pokud transakce trvá příliš dlouho. Když je vzájemné blokování nalezeno, jedna z transakcí se vrátí, což umožní ostatním transakcím, které se podílejí na vzájemném blokování, dokončit. Výběr oběti může být založen na nákladech transakcí nebo jejich stáří (schemata Wait-Die a Wound-wait).
Každé transakci T se přiřazuje časová značka TS obsahující čas začátku provádění transakce.
Wait-Die.
Pokud TS(Ti) < TS(Tj), pak Ti čeká, jinak Ti se vrací a začíná znovu se stejnou časovou značkou.
Pokud mladší transakce zachytila zdroj, a starší transakce žádá o stejný zdroj, pak starší transakce může čekat. Pokud starší transakce zachytila zdroj, pak mladší transakce žádající o tento zdroj bude zrušena.
Wound-wait.
Pokud TS(Ti) < TS(Tj), pak Tj se vrací a začíná znovu se stejnou časovou značkou, jinak Ti čeká.
Pokud mladší transakce zablokuje zdroj a starší transakce se pokusí o tento stejný zdroj, mladší transakce bude zrušena. Pokud starší transakce zablokuje zdroj, mladší transakce, která se pokouší o tento zdroj, má povoleno čekat. Výběr oběti na základě stáří zabraňuje vzniku vzájemného zablokování, ale vrací transakce, které nejsou ve stavu vzájemného zablokování. Problém spočívá v tom, že transakce mohou být opakovaně rušeny, protože starší transakce může dlouho držet zdroj.
Pesimistické řešení problému vzájemného zablokování neumožňuje transakcím zahájit provádění, pokud existuje riziko vzniku vzájemného zablokování.
Pro detekci vzájemného zablokování se vytváří graf (graf čekání, wait-for-graph), jehož vrcholy představují transakce a hrany jsou směrovány od transakcí čekajících na uvolnění dat k transakcím, které tato data zabraly. Předpokládá se, že k vzájemnému zablokování došlo, pokud má graf cykly. Vytváření grafu čekání, zejména v distribuovaných databázích, je nákladný proces.
Dvoufázové zamykání – prevence vzájemného zablokování tím, že transakce zabere všechny zdroje vyžadované na začátku transakce a uvolní je na konci.
Všechny blokující operace musí předcházet první uvolňující operaci. Má dvě fáze – fázi Růst (Growing Phase), během níž dochází k akumulaci zámků, a fázi Snížení (Shrinking Phase), při níž dochází k uvolňování zámků. Pokud nelze zabrat některý ze zdrojů, transakce začíná znovu. Může nastat situace, kdy transakce nebude moci získat požadované zdroje, například pokud několik transakcí soutěží o stejné zdroje.
Dvoufázový závazek zajišťuje provedení závazku na všech replikách databáze.
Každá databáze vloží informace o datech, která budou změněna, do protokolu a odpoví koordinátorovi OK (Voting Phase). Po obdržení všech odpovědí OK koordinátor odešle signál, který zavazuje všechny provést závazek. Po závazku serveru odpovídají OK, pokud alespoň jeden neodpoví OK, koordinátor odešle signál zrušení změn všem serverům (Completion Phase).
Metoda časových razítek
Starší transakce se vrací při pokusu o přístup k datům, na kterých se podílí mladší transakce.
Každé transakci je přiřazena časová značka TS odpovídající času zahájení provádění. Pokud Ti je starší Tj, pak TS(Ti) < TS(Tj).
Když je transakce zrušena, je jí přiřazena nová časová značka. Každý datový objekt Q označený transakcí je označen dvěma značkami. W-TS(Q) — časová značka nejmladší transakce, která úspěšně provedla zápis nad Q. R-TS(Q) — časová značka nejmladší transakce, která provedla čtení zápisu nad Q.
Když transakce T žádá o čtení dat Q mohou nastat dvě varianty.
Pokud TS(T) < W-TS(Q), tedy pokud byla data aktualizována mladší transakcí, pak transakce T se zruší.
Pokud TS(T) >= W-TS(Q), pak se čtení provádí a R-TS(Q) stává se MAX(R-TS(Q), TS(T)).
Když transakce T žádá o změnu dat Q mohou nastat dvě varianty.
Pokud TS(T) < R-TS(Q), tedy data již byla přečtena mladší transakcí a pokud dojde ke změně, vznikne konflikt. Transakce T se zruší.
Pokud TS(T) < W-TS(Q), tedy transakce se snaží přepsat novější hodnotu, transakce T se ruší. V ostatních případech se změna provede a W-TS(Q) stává se rovno TS(T).
Není nutná nákladná konstrukce grafu čekání. Starší transakce závisí na novějších, takže v grafu čekání nejsou cykly. Nejsou vzájemné blokace, protože transakce nečekají, ale ihned se ruší. Mohou nastat kaskádové rušení. Pokud Ti se zrušila, a Tj přečetla data, která změnila Ti, pak Tj také musí být zrušena. Pokud byla v této době Tj již zkomitována, dojde k porušení principu udržitelnosti.
Jedním z řešení kaskádových rušení. Transakce provádí všechny operace zápisu na konci, přičemž ostatní transakce musí počkat na dokončení této operace. Transakce čekají na potvrzení před čtením.
Thomasovo pravidlo zápisu — variace metody časových značek, při které je zakázáno přepisovat data aktualizovaná mladší transakcí staršími
Transakce T žádá o změnu dat Q. Pokud TS(T) < W-TS(Q), tedy transakce se snaží přepsat novější hodnotu, transakce T se neanuluje jako v metodě časových značek.
Zdroj: habr.com
