Transakce
Transakce je posloupnost operací s daty, která má začátek a konec.
Transakce je sekvenční provádění operací čtení a zápisu. Koncem transakce může být buď uložení změn (commit) nebo zrušení změn (rollback). Ve vztahu k databázi se transakce skládá z několika požadavků, které jsou považovány za jeden požadavek.
Transakce musí splňovat vlastnosti ACID
Atomicita. Transakce je buď dokončena úplně, nebo vůbec.
Konzistence. Při dokončení transakce nesmí být porušena omezení uložená na data (například omezení v databázi). Konzistence znamená, že systém bude převeden z jednoho správného stavu do jiného správného stavu.
Izolace. Paralelně probíhající transakce by se neměly vzájemně ovlivňovat, např. měnit data použitá jinou transakcí. Výsledek provádění paralelních transakcí by měl být stejný, jako kdyby byly transakce prováděny postupně.
Udržitelnost. Jakmile provedete změny, neměly by být ztraceny.
Transakční protokol
Log uchovává změny provedené transakcemi, zajišťuje atomicitu a stabilitu dat v případě selhání systému
Protokol obsahuje hodnoty, které měla data před a po změně transakcí. Strategie zápisu dopředu vyžaduje přidání položky protokolu o předchozích hodnotách před zahájením a o konečných hodnotách po dokončení transakce. V případě náhlého zastavení systému databáze načte protokol v obráceném pořadí a zruší změny provedené transakcemi. Po zjištění přerušené transakce ji databáze provede a provede změny v protokolu. Databáze je ve stavu v době selhání, čte protokol v dopředném pořadí a vrací změny provedené transakcemi. Tímto způsobem je zachována stabilita transakcí, které již byly potvrzeny, a atomicita přerušené transakce.
Pouhé opětovné provedení neúspěšných transakcí k obnovení nestačí.
Příklad. Uživatel má na svém účtu 500 USD a uživatel se rozhodne je vybrat z bankomatu. Probíhají dvě transakce. První načte hodnotu zůstatku a pokud je na zůstatku dostatek prostředků, vydá peníze uživateli. Druhý odečte požadovanou částku od zůstatku. Řekněme, že se systém zhroutil a první operace se nezdařila, ale druhá ano. V tomto 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
Přečtěte si Odhodlání
Problém špinavého čtení spočívá v tom, že transakce může číst mezivýsledek jiné transakce.
Příklad. Počáteční hodnota zůstatku je 0 USD. T1 přidá 50 $ k vašemu zůstatku. T2 přečte hodnotu zůstatku (50 $). T1 zruší změny a ukončí se. T2 pokračuje v provádění s nesprávnými údaji o zůstatku.
Řešením je čtení pevných dat (Read Committed), které zakazuje čtení dat změněných transakcí. Pokud transakce A změnila určitý soubor dat, je transakce B při přístupu k těmto datům nucena čekat na dokončení transakce A.
Opakovatelné čtení
Problém se ztrátou aktualizací. T1 ukládá změny nad změny T2.
Příklad. Počáteční hodnota zůstatku je 0 $ a dvě transakce současně doplní zůstatek. T1 a T2 přečetly zůstatek 0 $. T2 pak přidá 200 $ k 0 $ a uloží výsledek. T1 přidá 100 $ k 0 $ a uloží výsledek. Konečný výsledek je 100 USD místo 300 USD.
Neopakovatelný problém se čtením. Opakované čtení stejných dat vrací různé hodnoty.
Příklad. T1 čte zůstatkovou hodnotu 0 $. T2 pak přidá 50 $ k zůstatku a končí. T1 přečte data znovu a najde nesoulad s předchozím výsledkem.
Opakovatelné čtení zajišťuje, že druhé čtení vrátí stejný výsledek. Data načtená jednou transakcí nelze změnit v jiných, dokud není transakce dokončena. Pokud transakce A přečetla určitou sadu dat, je transakce B při přístupu k těmto datům nucena čekat na dokončení transakce A.
Objednané čtení (serializovatelné)
Problém s fantomovým čtením. Dva dotazy, které vybírají data na základě určité podmínky, vracejí různé hodnoty.
Příklad. T1 požaduje počet všech uživatelů, jejichž zůstatek je větší než 0 USD, ale menší než 100 USD. T2 odečte 1 $ od uživatele se zůstatkem 101 $. T1 znovu zadá požadavek.
Objednané čtení (serializovatelné). Transakce jsou prováděny jako zcela sekvenční. Je zakázáno aktualizovat nebo přidávat záznamy, které spadají do podmínek požadavku. Pokud transakce A požaduje data z celé tabulky, pak je celá tabulka zmrazena pro další transakce, dokud transakce A nebude dokončena.
Plánovač
Nastavuje pořadí, ve kterém se mají operace provádět během paralelních transakcí.
Poskytuje určitou úroveň izolace. Pokud výsledek operací nezávisí na jejich pořadí, pak jsou takové operace komutativní (Permutable). Operace čtení a operace s různými daty jsou komutativní. Operace čtení-zápis a zápis-zápis nejsou komutativní. Úkolem plánovače je prokládat operace prováděné paralelními transakcemi tak, aby výsledek provádění byl ekvivalentní sekvenčnímu provádění transakcí.
Mechanismy pro řízení paralelních úloh (Concurrency Control)
Optimistický je založen na odhalování a řešení konfliktů, pesimistický na předcházení vzniku konfliktů.
V optimistickém přístupu má více uživatelů k dispozici kopie dat. První osoba, která dokončí úpravy, uloží změny, zatímco ostatní musí změny sloučit. Optimistický algoritmus umožňuje vznik konfliktu, ale systém se musí z konfliktu vzpamatovat.
Při pesimistickém přístupu první uživatel, který zachytí data, zabrání ostatním v přijímání dat. Pokud jsou konflikty vzácné, je moudré zvolit optimistickou strategii, protože poskytuje vyšší úroveň souběžnosti.
Zamykání
Pokud má jedna transakce zamčená data, pak ostatní transakce musí při přístupu k datům počkat, až bude odemčena.
Blok může být překryt v databázi, tabulce, řádku nebo atributu. Sdílený zámek může být uplatněn na stejná data několika transakcemi, umožňuje čtení všech transakcí (včetně té, která jej uložila), zakazuje úpravy a výhradní zachycení. Exkluzivní zámek může být uložen pouze jednou transakcí, umožňuje jakékoli akce uvalující transakce, zakazuje jakékoli akce ostatních.
Zablokování je situace, kdy transakce skončí v nevyřízeném stavu, který trvá neomezeně dlouho.
Příklad. První transakce čeká na uvolnění dat zachycených druhou, zatímco druhá čeká na uvolnění dat zachycených první.
Optimistické řešení problému zablokování umožňuje, aby došlo k uváznutí, ale poté obnoví systém vrácením jedné z transakcí, které se zablokování účastní.
V určitých intervalech se hledají uváznutí. Jednou z metod detekce je podle času, to znamená vzít v úvahu, že došlo k uváznutí, pokud dokončení transakce trvá příliš dlouho. Když je nalezena zablokování, jedna z transakcí je vrácena zpět, což umožňuje dokončení ostatních transakcí zapojených do uváznutí. Výběr oběti může být založen na hodnotě transakcí nebo jejich senioritě (systémy Wait-Die a Wound-wait).
Každá transakce T je přiřazeno časové razítko TS obsahující čas zahájení transakce.
Počkejte, zemřete.
Jestliže TS (Ti) < TS(Tj)pak Ti čeká, jinak Ti vrátí zpět a začne znovu se stejným časovým razítkem.
Pokud mladá transakce získala zdroj a starší transakce požaduje stejný zdroj, může starší transakce čekat. Pokud starší transakce získala zdroj, bude mladší transakce požadující tento zdroj vrácena zpět.
Počkejte na ránu.
Jestliže TS (Ti) < TS(Tj)pak Tj vrátí zpět a začne znovu se stejným časovým razítkem, jinak Ti čekání.
Pokud mladší transakce získala zdroj a starší transakce požaduje stejný zdroj, bude mladší transakce vrácena zpět. Pokud starší transakce získala zdroj, pak mladší transakce požadující tento zdroj může čekat. Výběr obětí na základě priority zabraňuje uváznutí, ale vrací zpět transakce, které uvázlé nejsou. Problém je v tom, že transakce lze mnohokrát vrátit zpět, protože... starší transakce může držet zdroj po dlouhou dobu.
Pesimistické řešení problému uváznutí neumožňuje zahájení provádění transakce, pokud existuje riziko uváznutí.
Pro detekci uváznutí je sestrojen graf (waiting graph, wait-for-graph), jehož vrcholy jsou transakce a hrany jsou směrovány z transakcí čekajících na uvolnění dat k transakci, která tato data zachytila. Má se za to, že došlo k uváznutí, pokud má graf smyčku. Vytvoření čekacího grafu, zejména v distribuovaných databázích, je nákladný postup.
Dvoufázové zamykání – zabraňuje uváznutí tím, že zabaví všechny zdroje používané transakcí na začátku transakce a uvolní je na konci
Všechny blokovací operace musí předcházet prvnímu odblokování. Má dvě fáze – Rostoucí fázi, během které se úchopy hromadí, a Stahovací fázi, během které se úchopy uvolňují. Pokud není možné zachytit jeden ze zdrojů, transakce začne znovu. Je možné, že transakce nebude schopna získat požadované zdroje, například pokud několik transakcí soutěží o stejné zdroje.
Dvoufázové potvrzení zajišťuje, že potvrzení bude provedeno na všech replikách databáze
Každá databáze zapíše do logu informace o datech, která budou změněna, a odpoví koordinátorovi OK (Fáze hlasování). Poté, co všichni odpověděli OK, koordinátor vyšle signál, který každého zavazuje, aby se zavázal. Po potvrzení servery odpoví OK, pokud alespoň jeden neodpoví OK, pak koordinátor vyšle signál ke zrušení změn všem serverům (Fáze dokončení).
Metoda časového razítka
Starší transakce je vrácena zpět při pokusu o přístup k datům zahrnutým mladší transakcí
Každé transakci je přiřazeno časové razítko TS odpovídající času zahájení provádění. Li Ti přes Tjpak TS (Ti) < TS(Tj).
Když je transakce vrácena zpět, je jí přiřazeno nové časové razítko. Každý datový objekt Q zapojené do transakce je označeno dvěma štítky. W-TS(Q) — časové razítko nejmladší transakce, která úspěšně dokončila záznam přes Q. R-TS(Q) — časové razítko nejmladší transakce, která provedla načtený záznam Q.
Když transakce T požadavky na čtení dat Q Jsou dvě možnosti.
Jestliže TS(T) < W-TS(Q), to znamená, že data byla aktualizována mladší transakcí, než je transakce T odvaluje zpět.
Jestliže TS(T) >= W-TS(Q), poté se provede čtení a R-TS(Q) se stává MAX(R-TS(Q), TS(T)).
Když transakce T požaduje změny údajů Q Jsou dvě možnosti.
Jestliže TS(T) < R-TS(Q), to znamená, že data již byla načtena mladší transakcí a pokud dojde ke změně, dojde ke konfliktu. Transakce T odvaluje zpět.
Jestliže TS(T) < W-TS(Q), to znamená, že se transakce pokusí přepsat novější hodnotu, transakce T je odvolána. V ostatních případech se změna provádí a W-TS(Q) se stává rovným TS(T).
Není nutná žádná nákladná konstrukce čekacího grafu. Starší transakce závisí na novějších, takže v grafu čekání nejsou žádné cykly. Neexistují žádná uváznutí, protože transakce nejsou čekány, ale okamžitě vráceny zpět. Kaskádové vrácení je možné. Li Ti odvalil se a Tj Přečetl jsem data, která jsem změnil Tipak Tj by se měl také vrátit zpět. Pokud ve stejnou dobu Tj již spáchán, pak dojde k porušení principu stability.
Jedno z řešení kaskádových rollbacků. Transakce dokončí všechny operace zápisu na konci a ostatní transakce musí čekat na dokončení této operace. Transakce před čtením čekají na potvrzení.
Thomas write rule – varianta metody časového razítka, ve které je zakázáno přepisovat data aktualizovaná mladší transakcí starší transakcí
Transakce T požaduje změny údajů Q. Pokud TS(T) < W-TS(Q), tj. transakce se pokusí přepsat novější hodnotu, transakce T není vrácena zpět jako u metody časového razítka.
Zdroj: www.habr.com