Implementace databázových systémů/Transakce
Obsah
Modely a vlastnosti transakcí[editovat | editovat zdroj]
Transakce je posloupnost akci (r, w, vypocet,..) nad persistentními daty se kterou se zachazi jako s celkem.
Zacatek transakce se oznacuje obvykle BEGIN, konec COMMIT/ABORT,ROLLBACK. V pripade neuspesneho zakonceni transakce se system vrati do stavu pred zapocetim te transakce.
- Databázové transakce musí splňovat tzv. vlastnosti ACID (viz wen:ACID)
- Atomicity - Transakce proběhne celá, nebo vůbec.
- Consistency - Při provádění transakcí se DB převádí z jednoho konzistentního stavu do jiného.
- Isolation - Transakce o sobe navzájem nevědí, jako by běžela jen jedna.
- Durability - Změny commitnuté transakce jsou trvalé.
Flat Model (FM)[editovat | editovat zdroj]
Omezení transakčního modelu flat transactions, která mohou bránit jeho praktickému využití v některých transakčních systémech:
- Mají příliš velký rozsah. Abortu po stotisící operaci se nedá nijak zabránit. To se dá přičíst tomu, že nemají žádnou vnitřní strukturu.
- Žádný dílčí neúspěch není tolerován. Pokud je špatně jediné číslo konta u deseti tisíc zaměstnanců nějakého podniku, pak transakce odeslání mezd všem zaměstnancům kvůli této chybě abortuje.
- Flat transakce nemohou spolupracovat s jinými transakcemi. Nemohou s nimi sdílet data (pro sdílení dat neexistují žádná primitiva nebo pravidla), nemohou být vzájemně propojeny přes signifikantní události.
- Neřeší přirozený problém vnoření do sebe. Běžné programovací jazyky umožňují vnořovat volání procedur, take se může stát, že zavoláme v transakci proceduru, která zahájí novou vnořenou transakci.
Savepointy (SP)[editovat | editovat zdroj]
- podporuje MS SQL Server 2008 a Oracle také commitovány.
- rollbacky se neprovadi az na zacatek, ale k jiz ulozenym savepointum (první SP většinou po startu transakce).
- dopředný rollback
- rollback k rollbacknutým stavům
- rollbacky se pak stávají součástí historie
- neřeší tvrdé výpadky systemu ⇒ po opetovnem nabehnuti systemu se musi transakce provest znovu, ne od posledniho savepointu, persistetní savepointy zase nemusí odpovídat stavu kódu transakce
Dopředný rollback detailně |
---|
Dopředný rollback u SP si představuju jako akci zpět a dopředu u prohlížečů. Akce zpět způsobí klasický rollback k danému SP (tj. v prohlížeči se vrátit o X stránek zpět). Akce dopředu způsobí, že se zruší rollback a vrátíš se k původně smazanému SP (tj. v prohlížeči jít o X stránek dopředu). V praxi si myslím, že to funguje následovně (předpoklad: těsně před zavolání rollbacku se vytvoří SP): SP1 ... SP2 ... SP3 ... SP4 ... SP5 + Rollback(SP2) ... SP6 ... Rollback(SP5) Vyzvětlivky: - Rollback(SP2) způsobí vytvoření SP5 a zrušení efektu akcí mezi SP2 a SP5; - Rollback(SP5) funguje jako dopředný rollback - tj. smaže se efekt akcí mezi SP2 a SP6 a znovu se projeví efekt akcí mezi SP2 a SP5. Ale tadyto jsem nikde nevyčetl, je to spíš moje představa o tom, jak by to mohlo fungovat. |
Zřetězené transakce (Chained Transactions - CT)[editovat | editovat zdroj]
- Programátor se po části výpočtu vzdá možnosti rollbacku nad touto částí, tj. komituje
- Nechce ale ztratit kontext, kurzory, atp.
- Tj. je potřeba zavést atomickou operaci Chain work = Commit + Begin
Hnízděné transakce (Nested Transactions - NT)[editovat | editovat zdroj]
výpočet jako hierarchie transakcí, zobecnění SP
Pravidla pro podtransakce:
- COMMIT pravidlo - po potvrzení podtransakce jsou výsledky dostupné jen v rodičovské transakci, podtran. skutečně potvrdí až s potvrzením kořenové transakce
- ROLLBACK pravidlo - pokud je podtransakce zrušena, bere sebou všechny své potomky (i když už lokálně potvrdili), když je zrušena kořenová transakce
- pravidlo viditelnosti změn - zmeny v podtransakci jsou po lokálním COMMITu vidět jen v rodiči, objekty držené rodičem jsou přístupné potomkům, potomci jsou izolovaní v případě souběžného spuštění
- rodič rozhoduje o řešení zrušení potomka (restartovat, zvolit alternativní výpočet, abortovat)
ACID vlastnosti podtransakci jsou splnene jen částečně: A - podtr. jsou A jen z rodiče, C - podtr. jsou C vzhledem lok.fci., I - silná, D - neplatí kvuli commit pravidlu
Distribuované Transakce - DT (🎓)[editovat | editovat zdroj]
příklad DT - převod peněz |
---|
|
Zážitky ze zkoušek |
---|
|
- jsou to transakce, které pracují s více uzly najednou / s více databázemi v síti apod. (říká se jim také globální transakce)
- musejí splňovat ACID (jako jakékoliv jiné transakce) nezávisle na fragmentaci a replikaci dat
- celkem jednoduchý algoritmus, který problém řeší je "Dvoufázový commit"
Zamykaní v DT - centralizované/decentralizované[editovat | editovat zdroj]
V distribuovanych systemech muze byt sprava zamku bud centralni nebo v kazdem uzlu pro lokalni data.
- centralni - uviznuti je mozne detekovat pomoci konstrukce grafu vzajemnych zavislosti, nevyhodou jsou vysoke komunikacni naklady a zranitelnost systemu vypadkem uzlu spravujiciho zamky.
- lokalni (decentralizované) - obvykle vsak lze graf vzajemnych zavislosti konstruovat bez prilisnych pridavnych nakladu alespon pro lokalni podtransakce (lokální waits-for graf na každém uzlu ale nezachycuje globální závislosti). Pro globalni transakce se casto urcuje casovy limit, jehoz vyprseni se povazuje za uviznuti.
2PC | |
---|---|
1. commit-request phase: QUERY TO COMMIT -------------------------> VOTE Y/N <------------------------- 2. commit phase: COMMIT (a = b = Y) ABORT (a = N ∨ b = N) -------------------------> ACKNOWLEDGMENT <------------------------- příklad 2PC na svatbě [1] |
Dvoufázový Commit 2PC (two-phase commit)[editovat | editovat zdroj]
- commit-request phase
- kordinátor (transakční manažer) pošle všem uzlům dotaz → oni ho vykonají až do stavu před COMMIT/ABORT
- každý uzel pošle svůj výsledek koordinátorovi (YES - COMMIT/NO - ABORT)
- commit phase
- pokud koordinátor dostal od všech uzlů odpověď YES (COMMIT)
- koordinátor pošle COMMIT zprávu všem uzlům
- všechny uzly uvolní své zdroje a zámky
- všechny uzly pošlou koordinátorovi výsledek dotazu
- koordinátor vše skompletuje
- pokud koordinátor dostal alespoň jedno NO (ABORT)
- koordinátor všem uzlům pošle ABORT zprávu
- každý z uzlů udělá vlastní abort a uvolní zámky a zdroje
- všechny uzly pošlou koordinátorovi výsledek dotazu
- poté co koordinátor obdrží výsledky abortuje celou transakci
- pokud koordinátor dostal od všech uzlů odpověď YES (COMMIT)
💡 read-only DT nemusi ucastnik cekat na vysledek hlasovani (staci jen 1. faze) a po 1. fazi uz uvolni zamky. Koordinator nemusi ucastnikovi zasilat vysledek hlasovani
Problémem 2PC protokolu je, že každý z uzlů čeká, až dodělá práci poslední z uzlů, čímž dost dlouho blokuje.
další zdroje |
---|
|
Izolace transakcí, alokace prostředků. Uzamykací protokoly, časová razítka. (🎓🎓)[editovat | editovat zdroj]
Zážitky ze zkoušek |
---|
|
Rozvrhy (VSR ⊃ CSR a RC ⊃ ACA ⊃ ST)[editovat | editovat zdroj]
Rozvrh (historie) - stanovene poradi provadeni akci vice transakci
Rozvrh muze byt (formalne viz Soubor:Transakce-typy historii.pdf):
- Zotavitelny (RC) - když T₂ čte hodnoty z T₁ , pak COMMIT₁ < COMMIT₂ (💡 ABORT neovlivní data potvrzených transakcí)
- Proti kaskadovemu abortu (ACA) - pokud transakce čte data, museji byt potvrzena (po COMMITu)
- Striktni (ST) - pokud T₁ zapíše data, T₂ může později číst/přepsat tyto data pouze pokud T₁ skoncila (COMMIT/ABORT)
- Proti kaskadovemu abortu (ACA) - pokud transakce čte data, museji byt potvrzena (po COMMITu)
- Pohledove uspořadatelný (VSR), pokud je pohledove ekvivalentni se seriovym rozvrhem na stejnych transakcich
- (💡 čtou se stejná data jako v nějakém sériovém r.)
- Rozvrhy S₁, S₂ jsou pohledove ekvivalentni (NP-úplný problém), pokud splnuji nasledujici:
- Pokud transakce Tᵢ čte počátecni hodnotu v S₁, čte ji i v S₂
- Pokud transakce Tᵢ čte hodnotu zapsanou Tⱼ v S₁, čte ji i v S₂
- Pokud transakce Tᵢ provede poslední zápis hodnoty v S₁, provede jej i v S₂
- Konfliktove uspořadatelný (CSR) - když precedencni graf neobsahuje cykly.
- Precedenční graf historie H nad množinou transakcí {T₁, .., Tₙ} je orientovaný graf
- Kde uzly jsou transakce z COMMITované projekce historie H
- Hrana mezi uzlem Tᵢ a Tⱼ existuje prave tehdy, kdyz operace z Tᵢ předchází a je v konfliktu s nějakou operací z Tⱼ (v konfliktu jsou operace RW (read-write), WR (write-read) a WW (write-write))
- Uspořadatelný (či Serializovatelný) pokud jeho vykonani vede ke konzistentnimu stavu databaze
- (💡 výsledný stav odpovídá nějakému sériovému r.)
- Pozor, nyní uvažujeme pouze potvrzené (committed) transakce a statickou databázi (neexistuje vkládání a mazání objektů, pouze čtení a aktualizace)
- Zcela obecně (včetně akce abort a dynamické povahy DB) se pak definuje konzistence zachovávající uspořádatelnost jako pohledová uspořádatelnost
- Precedenční graf historie H nad množinou transakcí {T₁, .., Tₙ} je orientovaný graf
Testování uspořádatelnosti pro pohledovou ekvivalenci je NP-úplný problém, takže se v praxi nepoužívá - lze nahradit CSR a RC rozvrhy
Izolace transakcí[editovat | editovat zdroj]
Chceme aby současný běh více transakcí změnil DB stejně jako seriový běh transakcí (tedy aby mu byl ekvivalentní).
Úrovně isolace transakcí, obecne jsou 4 druhy (definovane standardem SQL92). Jsou to:
Stupeň izolace / fenomén | Řešení pomocí zámků | DIRTY READ (WR) | NON-REPEATABLE READ (RW) | PHANTOM |
READ UNCOMMITTED zabranuje přepsání nepotvrzených dat | nejsou nutné žádné zámky na čtení, S2PL na zápis | může nastat | může nastat | může nastat |
READ COMMITTED zabraňuje navíc čtení nepotvrzených dat | zámky na čtení (shared), S2PL na zápis | nemůže nastat | může nastat | může nastat |
REPEATABLE READ nestane se že 2 stejna cteni vrati ruzne hodnoty | S2PL | nemůže nastat | nemůže nastat | může nastat |
SERIALIZABLE zabraňuje navíc fantomům | S2PL + prevence fantoma (predikátové/intervalové/granulované zámky) | nemůže nastat | nemůže nastat | nemůže nastat |
Fenomény zdroj |
---|
|
Ne vždy je potřeba uroven SERIALIZABLE, např. pro statistické dotazy (pro vypocet průměrneho platu z 1000 zaměstannců mi nevadí neopakovatelné čtení), pro účetnictví už by to byl problém
Existuje více strategií, jak zajistit izolaci transakcí
další zdroje |
---|
Zámky[editovat | editovat zdroj]
Transakce, která chce přistoupit k datům musí nejdříve tyto data zamknout
zámek - atomická a levná operace
- shared - čtení dat (rl/ru)
- exclusive - zápis dat (wl/wu)
- Konkrétní implementace DB obsahují mnoho dalších typů zámku, MSSQL např. implementuje tzv. range lock, intent lock, schema lock, …
- 💡 Platí, že exkluzivní zámek je vzdy konfliktní s jinym (sdilenym/exkluzivnim). Jen dva sdilene zamky jsou v poradku
- intention - pro hierarchické struktury
- irl – v podstromu bude požadován rl
- iwl – v podstromu bude požadován wl
- riwl – uzel uzamčen pro čtení, v podstromu bude požadován wl
Legální rozvrh - Transakce dostane zámek objektu jen když je k dispozici (podle tabulky konfliktů)
- Příklad: wl2 [x] w2 [x] wu2 [x] rl1 [x] r1 [x] ru1 [x]
- 💡 samotná legálnost rozvrhu nezaručuje uspořádatelnost
Dobře formovaná transakce - Před r[x] je vždy (právě jeden) rl[x] a před w[x] je vždy (právě jeden) wl[x]
- Příklad: rl[x] r[x] wl[y] w[y] ru[x] wu[y] c
Dvoufázová transakce - Dvě fáze – 1. pouze zamykání a 2. pouze odemykání
- Příklad: rl[x] r[x] wl[y] ru[x] w[y] wu[y] c
Uzamykací protokoly[editovat | editovat zdroj]
2PL protokol (dvoufázové zamykání)
popis | konfliktová uspořadatelnost (CSR) | zotavitelnost rozvrhu (RC) | proti kask. abortům (ACA) | zabraňuje deadlocku | |
---|---|---|---|---|---|
2PL | nejdrive T jenom zamyká, pak jenom odemyká | ANO | NE | NE | NE |
S2PL | uvolňuje zámky až po konci T (COMMIT / ABORT) | ANO | ANO | ANO | NE |
K2PL (SSPL) | uzamykání pouze na začátku T, odem. na konci | ANO | ANO | ANO | ANO |
- 'Klasicky' 2PL protokol
- pokud už transakce o nějaký zámek požádala a uvolnila ho, nesmí o žádný požádat znovu (💡 stav kdy nepotřebuje žádné dálší zámky = lock point)
- ⇒ 2 fáze: zamykání a odemykání (tyto 2 faze se tykaji vzdy kazde transakce zvlast, ne celeho rozvrhu)
- takovýto rozvrh je konfliktově uspořádatelný (CSR), ale negarantuje zotavitelnost rozvrhu (RC) a tim padem ani ACA a ST (=> striktní 2PL)
- Striktní 2PL protokol (S2PL)
- všechny zámky jsou uvolněny až při ukončení transakce
- generuje striktni rozvrh (ST - tim padem predchazi kaskádovému rušení transakcí ACA a je i zotavitelny RC)
- rozvrh je konfliktově uspořádatelný (CSR - jako klasicky 2PL)
- je implementován v každém větším db systému
- Konzervativní 2PL protokol
- implementace S2PL s prevencí deadlocku: všechny zámky které bude potřebovat si vyžádá hned na začátku
- není používán protože: neví se co za zámky se bude potřebovat, vysoká režie uzamykání a limituje (potencionální) současný běh dlouhých transakcí
💡 Vztahy:
- Gen(K2PL)⊂Gen(S2PL)⊂Gen(2PL)
- Gen(S2PL) ⊆ CSR∩ST
další zdroje |
---|
Deadlock (uváznutí)[editovat | editovat zdroj]
transakce na sebe čekají v kruhu (čekají navzájem na nějaký zdroj a nechtějí si dát ten svuj)
podmínky pro vznik Deadlock (musí být splněny všechny)
- vzájemné vyloučení - prostředek může být přidělen pouze jednomu procesu
- držení prostředků
- neodnímatelnost
- čekání v kruhu
Detekce, řešení
- detekce: cyklus v grafu waits-for
- abort + restart transakce z cyklu podle nějakého kriteria (např. nejnovější)
snížení frekvence uváznutí (ne její řešení)
- lock downgrade - pokud už nepotřebuji výhradní zámek, snížím na sdílený
- lock upgrade - pokud potřebuju výhradní a mám sdílený, mám větší právo, než ten co nemá nic a chce výhradní
prevence deadlocku
- konzervativní 2PL
- časové razítko (klasicke nebo striktni, asi ne konzervativni)
- prioritizování/timestamp (pro 2PL)
- každá transakce dostane nějakou prioritu (např. časové razítko - čím starší, tím vyšší priorita)
- dvě možnosti řešení za použití priorit
- wait-die: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, čeká, jinak zemře
- wounds-wait: pokud chce transakce T1 zámek a už ho má někdo jiný (T2), pokud má T1 vyšší prioritu, T2 zemře, jinak T1 čeká
- rušeným transakcím je třeba zvyšovat prioritu aby nebyly pořád utiskované
Časová razítka - Time Ordering (TO)[editovat | editovat zdroj]
konfliktní operace jsou seřazeny dle odpovídajících časových razítek (TO pravidlo), a tedy nepoužívá zámky (zatím se v komerčních systémech moc neujalo)
- Každá transakce má přiřazeno unikátní časové razítko ts(Ti)
- Pro každé dvě různé transakce platí $ ts(T_i) < ts(T_j) $ nebo $ ts(T_j) < ts(T_i) $
- Každá operace $ p_i[x] $ je označena pomocí $ ts(T_i) $
💡 Pokud je H historie reprezentující výpočet plánovaná pomocí TO pravidla, pak je H uspořádatelná. H je dokonce CSR (viz odkaz), z cehoz plyne usporadatelnost
Zakladni TO pravidlo - jednoduchá agresivní impl. TO pravidla
- plánovač posílá op. všech transakcí do db (FIFO)
- pokud nejaka op. prijde pozdě (s nižším $ ts $ než předchozí) dojde k ABORTu její transakce a musí dostat novou $ ts $
💡 Nezajistuje zotavitelnost. Pro dosažení zotavení je potřeba implementovat bufferování všech zápisů dokud transakce nepotvrdí.
- Striktní TO pravidlo
- Kazda transakce pred zapisem danou polozku zamkne (pro zapis i cteni), aby se soucasne nesahalo do DB, a odemkne az skonci (COMMITem/ABORTem)
💡 Zajistuje zotavitelnost (vysledny rozvrh je striktni z cehoz vyplyva, ze je zotavitelny)
💡 Nemuze nastat deadlock (cekaji vzdy transakce s vyssim razitkem). Pri zakladnim TO pravidle deadlock take nenastava - neblokuje se nic (jen objekt pro rychle precteni z DB)
- Konzervativní TO pravidlo
- Pozdržet některé operace (čekat na operace starších transakcí), aby nedochazelo k restartovani transakci.
- 💡 Pry muze nastat deadlock (viz zde) kvuli temto zdrzenim - zvlastni, kdyz cekaji novejsi transakce na ty starsi (starsi by nemela cekat na novejsi)
další zdroje |
---|
|
Pomocí precedenčního grafu (PG)[editovat | editovat zdroj]
- nepoužívá zámky, zatím se v komerčních systémech moc neujalo
- je postaveno na udržování lehce modifikovaného precedenčního grafu, ve kterém se hlídá acykličnost
- modifikovaný precedenční graf (MPG)
- neobsahuje všechny komitované transakce (jsou odebrány takové, které byly dávno ukončené)
- obsahuje uzly všech aktivních transakcí (až na ABORTbortované a COMMITované)
- existuje základní a konzervativní plánování pomocí PG. Vytváří uspořádatelné historie, které ale nejsou RC (tedy ani nejsou ACA a ST)
Certifikace (optimistické řešení)[editovat | editovat zdroj]
- korektnost se testuje až při pokusu o COMMIT - použitelná pokud dochází velmi zřídka k jakýmkoliv konfliktům (snižuje režii) jinak totiž zbytečně moc často ABORTuje
- 💡příklad: ukládání článků zde na wiki, wikipedii,...
- může být založena na různých algoritmech – 2PL, TO, PG certifikátory
- skládá se ze tří fází
- Modify - transakce čte z databáze, provádí různé operace, ale vše zapisuje do svého prostoru (databázi nemění)
- Validate - transakce předloží co vytvořila a SŘBD zkontroluje, zda to není v konfliktu s jinou transakcí (pomocí 2PL,TO,MPG)
- COMMIT/ROLLBACK - pokud je vše ok COMMIT jinak ABORT
Multiversion data[editovat | editovat zdroj]
- existuje vice verzi hodnot nejakeho objektu, takze prepsanim nejake hodnoty se neztrati ta minula, ale jsou znamy obe verze. Přestávají být konfliktní w/w dvojice – nejsou nad stejnou proměnnou
- s tím jsou ale spojené nové problémy - plánovač musí doplnit operaci čtení o informaci, jakou verzi číst (od toho by měl být uživatel odstíněn)
- může být založena na různých algoritmech – 2PL, TO, PG
- std používá Oracle v SQL Serveru se může zapnout
další metody izolace |
---|
|
Zotavení z chyb, žurnály (🎓🎓)[editovat | editovat zdroj]
Zážitky ze zkoušek |
---|
|
Zotavení po havárii systému provádí recovery manager, zajišťuje:
- atomicitu (odvolání akcí, pokud byla transakce zrušena - undo)
- trvanlivost (zapsání potvrzených akcí i když systém havaroval)
💡 Datové položky se nezapisují přímo na disk a záznamy logu se nezapisují okamžitě do stabilní paměti - jak DB tak log mají buffer.
ARIES (Algorithms for Recovery and Isolation Exploiting Semantics)[editovat | editovat zdroj]
spustí se po restartu havarovaného systému - implementovan napr. IBM DB2, MS SQL, Informix, Sybase, Oracle
- Zotavení probíhá ve třech fázích
- Analysis - identifikují se dirty pages (stránky modifikované, ale nezapsané v okamžiku havárie) v bufferu a transakce, které byly aktivní v okamžiku havárie
- Redo - zopakují se všechny akce od posledního uložení na disk (checkpoint) tak aby se databáze dostala do stavu před havárií
- Undo - odvolají se všechny akce těch transakcí, které nebyly potvrzeny (commitnuty), tedy databáze obsahuje pouze potvrzené transakce
Hlavní principy ARIES
- Write Ahead Logging – do logu by se mělo zapsat vždy dříve, než se provede a uloží samotná změna objektu do perzistentní paměti
- Opakování historie během REDO - při restartu po pádu ARIES znovu projede akce před pádem a vrátí systém do stavu před pádem, pak udělá UNDO na transakce aktivní během pádu (nestihly se potvrdit)
- Logování změn během UNDO (neopakování undo operací během opakovaného pádu systému) - zmeny v databázi během undování transakcí se logují aby se neopakovaly při případných opakovaných restartech
Log ARIES = žurnál (journal), každá změna databáze je nejdříve uložena zde (právě kvůli možné havárii).
- Po restartu algoritmus vystopuje všechny akce před havárií a znovu je provede tak, aby se db dostalo do stavu před havárií.
- Nepotvrzené akce jsou zrušeny. Při rušení je opět vše logováno pro případ opětovné havárie při provádění ABORT.
- záznam v logu je identifikován(log sequence number - LSN)
- Take se zalohuji zurnaly. Predpokladame zalohovani v dobe nerozjetych transakci a tudiz kdyz se DB zotavuje ze zalohy zurnalu (neco se s puvodnim zurnalem stalo), nedela se faze Undo.
další zdroje |
---|
Transakce - uzamykací protokoly, zotavení (Databázové systémy) |
- ↑ Gray: Transaction Processing: Concepts and Techniques, p.574